xref: /inferno-os/os/port/alloc.c (revision 7ef44d652ae9e5e1f5b3465d73684e4a54de73c0)
1 #include "u.h"
2 #include "../port/lib.h"
3 #include "mem.h"
4 #include "dat.h"
5 #include "fns.h"
6 #include "interp.h"
7 
8 #define left	u.s.bhl
9 #define right	u.s.bhr
10 #define fwd	u.s.bhf
11 #define prev	u.s.bhv
12 #define parent	u.s.bhp
13 
14 #define RESERVED	256*1024
15 
16 struct Pool
17 {
18 	char*	name;
19 	int	pnum;
20 	ulong	maxsize;
21 	int	quanta;
22 	int	chunk;
23 	ulong	ressize;
24 	ulong	cursize;
25 	ulong	arenasize;
26 	ulong	hw;
27 	Lock	l;
28 	Bhdr*	root;
29 	Bhdr*	chain;
30 	ulong	nalloc;
31 	ulong	nfree;
32 	int	nbrk;
33 	int	lastfree;
34 	int	warn;
35 	void	(*move)(void*, void*);
36 };
37 
38 static
39 struct
40 {
41 	int	n;
42 	Pool	pool[MAXPOOL];
43 	// Lock	l;
44 } table = {
45 	3,
46 	{
47 		{ "main",  0,	 4*1024*1024, 31,  128*1024, 15*256*1024 },
48 		{ "heap",  1,	16*1024*1024, 31,  128*1024, 15*1024*1024 },
49 		{ "image", 2,	 8*1024*1024, 31, 300*1024, 15*512*1024 },
50 	}
51 };
52 
53 Pool*	mainmem = &table.pool[0];
54 Pool*	heapmem = &table.pool[1];
55 Pool*	imagmem = &table.pool[2];
56 
57 static void _auditmemloc(char *, void *);
58 void (*auditmemloc)(char *, void *) = _auditmemloc;
59 static void _poolfault(void *, char *, ulong);
60 void (*poolfault)(void *, char *, ulong) = _poolfault;
61 
62 /*	non tracing
63  *
64 enum {
65 	Npadlong	= 0,
66 	MallocOffset = 0,
67 	ReallocOffset = 0
68 };
69  *
70  */
71 
72 /* tracing */
73 enum {
74 	Npadlong	= 2,
75 	MallocOffset = 0,
76 	ReallocOffset = 1
77 };
78 
79 int
80 memusehigh(void)
81 {
82 	return 	mainmem->cursize > mainmem->ressize ||
83 			heapmem->cursize > heapmem->ressize ||
84 			imagmem->cursize > imagmem->ressize;
85 }
86 
87 void
88 poolimmutable(void *v)
89 {
90 	Bhdr *b;
91 
92 	D2B(b, v);
93 	b->magic = MAGIC_I;
94 }
95 
96 void
97 poolmutable(void *v)
98 {
99 	Bhdr *b;
100 
101 	D2B(b, v);
102 	b->magic = MAGIC_A;
103 	((Heap*)v)->color = mutator;
104 }
105 
106 char*
107 poolname(Pool *p)
108 {
109 	return p->name;
110 }
111 
112 Bhdr*
113 poolchain(Pool *p)
114 {
115 	return p->chain;
116 }
117 
118 void
119 pooldel(Pool *p, Bhdr *t)
120 {
121 	Bhdr *s, *f, *rp, *q;
122 
123 	if(t->parent == nil && p->root != t) {
124 		t->prev->fwd = t->fwd;
125 		t->fwd->prev = t->prev;
126 		return;
127 	}
128 
129 	if(t->fwd != t) {
130 		f = t->fwd;
131 		s = t->parent;
132 		f->parent = s;
133 		if(s == nil)
134 			p->root = f;
135 		else {
136 			if(s->left == t)
137 				s->left = f;
138 			else
139 				s->right = f;
140 		}
141 
142 		rp = t->left;
143 		f->left = rp;
144 		if(rp != nil)
145 			rp->parent = f;
146 		rp = t->right;
147 		f->right = rp;
148 		if(rp != nil)
149 			rp->parent = f;
150 
151 		t->prev->fwd = t->fwd;
152 		t->fwd->prev = t->prev;
153 		return;
154 	}
155 
156 	if(t->left == nil)
157 		rp = t->right;
158 	else {
159 		if(t->right == nil)
160 			rp = t->left;
161 		else {
162 			f = t;
163 			rp = t->right;
164 			s = rp->left;
165 			while(s != nil) {
166 				f = rp;
167 				rp = s;
168 				s = rp->left;
169 			}
170 			if(f != t) {
171 				s = rp->right;
172 				f->left = s;
173 				if(s != nil)
174 					s->parent = f;
175 				s = t->right;
176 				rp->right = s;
177 				if(s != nil)
178 					s->parent = rp;
179 			}
180 			s = t->left;
181 			rp->left = s;
182 			s->parent = rp;
183 		}
184 	}
185 	q = t->parent;
186 	if(q == nil)
187 		p->root = rp;
188 	else {
189 		if(t == q->left)
190 			q->left = rp;
191 		else
192 			q->right = rp;
193 	}
194 	if(rp != nil)
195 		rp->parent = q;
196 }
197 
198 void
199 pooladd(Pool *p, Bhdr *q)
200 {
201 	int size;
202 	Bhdr *tp, *t;
203 
204 	q->magic = MAGIC_F;
205 
206 	q->left = nil;
207 	q->right = nil;
208 	q->parent = nil;
209 	q->fwd = q;
210 	q->prev = q;
211 
212 	t = p->root;
213 	if(t == nil) {
214 		p->root = q;
215 		return;
216 	}
217 
218 	size = q->size;
219 
220 	tp = nil;
221 	while(t != nil) {
222 		if(size == t->size) {
223 			q->prev = t->prev;
224 			q->prev->fwd = q;
225 			q->fwd = t;
226 			t->prev = q;
227 			return;
228 		}
229 		tp = t;
230 		if(size < t->size)
231 			t = t->left;
232 		else
233 			t = t->right;
234 	}
235 
236 	q->parent = tp;
237 	if(size < tp->size)
238 		tp->left = q;
239 	else
240 		tp->right = q;
241 }
242 
243 void
244 poolsummary(void)
245 {
246 	int x = 0;
247 	char buf[400];
248 
249 	print("\n");
250 	print("    cursize     maxsize       hw         nalloc       nfree      nbrk       max      name\n");
251 
252 	x=poolread( buf, sizeof buf - 1, x );
253 	buf[x] = 0;
254 	putstrn(buf, x);
255 	print("\n");
256 }
257 
258 void*
259 poolalloc(Pool *p, ulong asize)
260 {
261 	Bhdr *q, *t;
262 	int alloc, ldr, ns, frag;
263 	int osize, size;
264 	Prog *prog;
265 
266 	if(asize >= 1024*1024*1024)	/* for sanity and to avoid overflow */
267 		return nil;
268 	if(p->cursize > p->ressize && (prog = currun()) != nil && prog->flags&Prestricted)
269 		return nil;
270 	size = asize;
271 	osize = size;
272 	size = (size + BHDRSIZE + p->quanta) & ~(p->quanta);
273 
274 	ilock(&p->l);
275 	p->nalloc++;
276 
277 	t = p->root;
278 	q = nil;
279 	while(t) {
280 		if(t->size == size) {
281 			t = t->fwd;
282 			pooldel(p, t);
283 			t->magic = MAGIC_A;
284 			p->cursize += t->size;
285 			if(p->cursize > p->hw)
286 				p->hw = p->cursize;
287 			iunlock(&p->l);
288 			return B2D(t);
289 		}
290 		if(size < t->size) {
291 			q = t;
292 			t = t->left;
293 		}
294 		else
295 			t = t->right;
296 	}
297 	if(q != nil) {
298 		pooldel(p, q);
299 		q->magic = MAGIC_A;
300 		frag = q->size - size;
301 		if(frag < (size>>2) && frag < 0x8000) {
302 			p->cursize += q->size;
303 			if(p->cursize > p->hw)
304 				p->hw = p->cursize;
305 			iunlock(&p->l);
306 			return B2D(q);
307 		}
308 		/* Split */
309 		ns = q->size - size;
310 		q->size = size;
311 		B2T(q)->hdr = q;
312 		t = B2NB(q);
313 		t->size = ns;
314 		B2T(t)->hdr = t;
315 		pooladd(p, t);
316 		p->cursize += q->size;
317 		if(p->cursize > p->hw)
318 			p->hw = p->cursize;
319 		iunlock(&p->l);
320 		return B2D(q);
321 	}
322 
323 	ns = p->chunk;
324 	if(size > ns)
325 		ns = size;
326 	ldr = p->quanta+1;
327 
328 	alloc = ns+ldr+ldr;
329 	p->arenasize += alloc;
330 	if(p->arenasize > p->maxsize) {
331 		p->arenasize -= alloc;
332 		ns = p->maxsize-p->arenasize-ldr-ldr;
333 		ns &= ~p->quanta;
334 		if (ns < size) {
335 			if(poolcompact(p)) {
336 				iunlock(&p->l);
337 				return poolalloc(p, osize);
338 			}
339 
340 			iunlock(&p->l);
341 			if(p->warn)
342 				return nil;
343 			p->warn = 1;
344 			if (p != mainmem || ns > 512)
345 				print("arena too large: %s size %d cursize %lud arenasize %lud maxsize %lud, alloc = %d\n", p->name, osize, p->cursize, p->arenasize, p->maxsize, alloc);
346 			return nil;
347 		}
348 		alloc = ns+ldr+ldr;
349 		p->arenasize += alloc;
350 	}
351 
352 	p->nbrk++;
353 	t = xalloc(alloc);
354 	if(t == nil) {
355 		p->nbrk--;
356 		iunlock(&p->l);
357 		return nil;
358 	}
359 	/* Double alignment */
360 	t = (Bhdr *)(((ulong)t + 7) & ~7);
361 
362 	/* TBS xmerge */
363 	if(0 && p->chain != nil && (char*)t-(char*)B2LIMIT(p->chain)-ldr == 0){
364 		/* can merge chains */
365 		if(0)print("merging chains %p and %p in %s\n", p->chain, t, p->name);
366 		q = B2LIMIT(p->chain);
367 		q->magic = MAGIC_A;
368 		q->size = alloc;
369 		B2T(q)->hdr = q;
370 		t = B2NB(q);
371 		t->magic = MAGIC_E;
372 		p->chain->csize += alloc;
373 		p->cursize += alloc;
374 		iunlock(&p->l);
375 		poolfree(p, B2D(q));		/* for backward merge */
376 		return poolalloc(p, osize);
377 	}
378 
379 	t->magic = MAGIC_E;		/* Make a leader */
380 	t->size = ldr;
381 	t->csize = ns+ldr;
382 	t->clink = p->chain;
383 	p->chain = t;
384 	B2T(t)->hdr = t;
385 	t = B2NB(t);
386 
387 	t->magic = MAGIC_A;		/* Make the block we are going to return */
388 	t->size = size;
389 	B2T(t)->hdr = t;
390 	q = t;
391 
392 	ns -= size;			/* Free the rest */
393 	if(ns > 0) {
394 		q = B2NB(t);
395 		q->size = ns;
396 		B2T(q)->hdr = q;
397 		pooladd(p, q);
398 	}
399 	B2NB(q)->magic = MAGIC_E;	/* Mark the end of the chunk */
400 
401 	p->cursize += t->size;
402 	if(p->cursize > p->hw)
403 		p->hw = p->cursize;
404 	iunlock(&p->l);
405 	return B2D(t);
406 }
407 
408 void
409 poolfree(Pool *p, void *v)
410 {
411 	Bhdr *b, *c;
412 	extern Bhdr *ptr;
413 
414 	D2B(b, v);
415 
416 	ilock(&p->l);
417 	p->nfree++;
418 	p->cursize -= b->size;
419 
420 	c = B2NB(b);
421 	if(c->magic == MAGIC_F) {	/* Join forward */
422 		if(c == ptr)
423 			ptr = b;
424 		pooldel(p, c);
425 		c->magic = 0;
426 		b->size += c->size;
427 		B2T(b)->hdr = b;
428 	}
429 
430 	c = B2PT(b)->hdr;
431 	if(c->magic == MAGIC_F) {	/* Join backward */
432 		if(b == ptr)
433 			ptr = c;
434 		pooldel(p, c);
435 		b->magic = 0;
436 		c->size += b->size;
437 		b = c;
438 		B2T(b)->hdr = b;
439 	}
440 
441 	pooladd(p, b);
442 	iunlock(&p->l);
443 }
444 
445 void *
446 poolrealloc(Pool *p, void *v, ulong size)
447 {
448 	Bhdr *b;
449 	void *nv;
450 	int osize;
451 
452 	if(size >= 1024*1024*1024)	/* for sanity and to avoid overflow */
453 		return nil;
454 	if(size == 0){
455 		poolfree(p, v);
456 		return nil;
457 	}
458 	SET(osize);
459 	if(v != nil){
460 		ilock(&p->l);
461 		D2B(b, v);
462 		osize = b->size - BHDRSIZE;
463 		iunlock(&p->l);
464 		if(osize >= size)
465 			return v;
466 	}
467 	nv = poolalloc(p, size);
468 	if(nv != nil && v != nil){
469 		memmove(nv, v, osize);
470 		poolfree(p, v);
471 	}
472 	return nv;
473 }
474 
475 ulong
476 poolmsize(Pool *p, void *v)
477 {
478 	Bhdr *b;
479 	ulong size;
480 
481 	if(v == nil)
482 		return 0;
483 	ilock(&p->l);
484 	D2B(b, v);
485 	size = b->size - BHDRSIZE;
486 	iunlock(&p->l);
487 	return size;
488 }
489 
490 static ulong
491 poolmax(Pool *p)
492 {
493 	Bhdr *t;
494 	ulong size;
495 
496 	ilock(&p->l);
497 	size = p->maxsize - p->cursize;
498 	t = p->root;
499 	if(t != nil) {
500 		while(t->right != nil)
501 			t = t->right;
502 		if(size < t->size)
503 			size = t->size;
504 	}
505 	if(size >= BHDRSIZE)
506 		size -= BHDRSIZE;
507 	iunlock(&p->l);
508 	return size;
509 }
510 
511 int
512 poolread(char *va, int count, ulong offset)
513 {
514 	Pool *p;
515 	int n, i, signed_off;
516 
517 	n = 0;
518 	signed_off = offset;
519 	for(i = 0; i < table.n; i++) {
520 		p = &table.pool[i];
521 		n += snprint(va+n, count-n, "%11lud %11lud %11lud %11lud %11lud %11d %11lud %s\n",
522 			p->cursize,
523 			p->maxsize,
524 			p->hw,
525 			p->nalloc,
526 			p->nfree,
527 			p->nbrk,
528 			poolmax(p),
529 			p->name);
530 
531 		if(signed_off > 0) {
532 			signed_off -= n;
533 			if(signed_off < 0) {
534 				memmove(va, va+n+signed_off, -signed_off);
535 				n = -signed_off;
536 			}
537 			else
538 				n = 0;
539 		}
540 
541 	}
542 	return n;
543 }
544 
545 void*
546 malloc(ulong size)
547 {
548 	void *v;
549 
550 	v = poolalloc(mainmem, size+Npadlong*sizeof(ulong));
551 	if(v != nil){
552 		if(Npadlong){
553 			v = (ulong*)v+Npadlong;
554 			setmalloctag(v, getcallerpc(&size));
555 			setrealloctag(v, 0);
556 		}
557 		memset(v, 0, size);
558 	}
559 	return v;
560 }
561 
562 void*
563 smalloc(ulong size)
564 {
565 	void *v;
566 
567 	for(;;) {
568 		v = poolalloc(mainmem, size+Npadlong*sizeof(ulong));
569 		if(v != nil)
570 			break;
571 		tsleep(&up->sleep, return0, 0, 100);
572 	}
573 	if(Npadlong){
574 		v = (ulong*)v+Npadlong;
575 		setmalloctag(v, getcallerpc(&size));
576 		setrealloctag(v, 0);
577 	}
578 	memset(v, 0, size);
579 	return v;
580 }
581 
582 void*
583 mallocz(ulong size, int clr)
584 {
585 	void *v;
586 
587 	v = poolalloc(mainmem, size+Npadlong*sizeof(ulong));
588 	if(v != nil){
589 		if(Npadlong){
590 			v = (ulong*)v+Npadlong;
591 			setmalloctag(v, getcallerpc(&size));
592 			setrealloctag(v, 0);
593 		}
594 		if(clr)
595 			memset(v, 0, size);
596 	}
597 	return v;
598 }
599 
600 void
601 free(void *v)
602 {
603 	Bhdr *b;
604 
605 	if(v != nil) {
606 		if(Npadlong)
607 			v = (ulong*)v-Npadlong;
608 		D2B(b, v);
609 		poolfree(mainmem, v);
610 	}
611 }
612 
613 void*
614 realloc(void *v, ulong size)
615 {
616 	void *nv;
617 
618 	if(size == 0)
619 		return malloc(size);	/* temporary change until realloc calls can be checked */
620 	if(v != nil)
621 		v = (ulong*)v-Npadlong;
622 	if(Npadlong!=0 && size!=0)
623 		size += Npadlong*sizeof(ulong);
624 	nv = poolrealloc(mainmem, v, size);
625 	if(nv != nil) {
626 		nv = (ulong*)nv+Npadlong;
627 		setrealloctag(nv, getcallerpc(&v));
628 		if(v == nil)
629 			setmalloctag(v, getcallerpc(&v));
630 	}
631 	return nv;
632 }
633 
634 void
635 setmalloctag(void *v, ulong pc)
636 {
637 	ulong *u;
638 
639 	USED(v);
640 	USED(pc);
641 	if(Npadlong <= MallocOffset || v == nil)
642 		return;
643 	u = v;
644 	u[-Npadlong+MallocOffset] = pc;
645 }
646 
647 ulong
648 getmalloctag(void *v)
649 {
650 	USED(v);
651 	if(Npadlong <= MallocOffset)
652 		return ~0;
653 	return ((ulong*)v)[-Npadlong+MallocOffset];
654 }
655 
656 void
657 setrealloctag(void *v, ulong pc)
658 {
659 	ulong *u;
660 
661 	USED(v);
662 	USED(pc);
663 	if(Npadlong <= ReallocOffset || v == nil)
664 		return;
665 	u = v;
666 	u[-Npadlong+ReallocOffset] = pc;
667 }
668 
669 ulong
670 getrealloctag(void *v)
671 {
672 	USED(v);
673 	if(Npadlong <= ReallocOffset)
674 		return ((ulong*)v)[-Npadlong+ReallocOffset];
675 	return ~0;
676 }
677 
678 ulong
679 msize(void *v)
680 {
681 	if(v == nil)
682 		return 0;
683 	return poolmsize(mainmem, (ulong*)v-Npadlong)-Npadlong*sizeof(ulong);
684 }
685 
686 void*
687 calloc(ulong n, ulong szelem)
688 {
689 	return malloc(n*szelem);
690 }
691 
692 void
693 pooldump(Bhdr *b, int d, int c)
694 {
695 	Bhdr *t;
696 
697 	if(b == nil)
698 		return;
699 
700 	print("%.8lux %.8lux %.8lux %c %4d %lud (f %.8lux p %.8lux)\n",
701 		b, b->left, b->right, c, d, b->size, b->fwd, b->prev);
702 	d++;
703 	for(t = b->fwd; t != b; t = t->fwd)
704 		print("\t%.8lux %.8lux %.8lux\n", t, t->prev, t->fwd);
705 	pooldump(b->left, d, 'l');
706 	pooldump(b->right, d, 'r');
707 }
708 
709 void
710 poolshow(void)
711 {
712 	int i;
713 
714 	for(i = 0; i < table.n; i++) {
715 		print("Arena: %s root=%.8lux\n", table.pool[i].name, table.pool[i].root);
716 		pooldump(table.pool[i].root, 0, 'R');
717 	}
718 }
719 
720 void
721 poolsetcompact(Pool *p, void (*move)(void*, void*))
722 {
723 	p->move = move;
724 }
725 
726 int
727 poolcompact(Pool *pool)
728 {
729 	Bhdr *base, *limit, *ptr, *end, *next;
730 	int compacted, nb;
731 
732 	if(pool->move == nil || pool->lastfree == pool->nfree)
733 		return 0;
734 
735 	pool->lastfree = pool->nfree;
736 
737 	base = pool->chain;
738 	ptr = B2NB(base);	/* First Block in arena has clink */
739 	limit = B2LIMIT(base);
740 	compacted = 0;
741 
742 	pool->root = nil;
743 	end = ptr;
744 	while(base != nil) {
745 		next = B2NB(ptr);
746 		if(ptr->magic == MAGIC_A || ptr->magic == MAGIC_I) {
747 			if(ptr != end) {
748 				memmove(end, ptr, ptr->size);
749 				pool->move(B2D(ptr), B2D(end));
750 				compacted = 1;
751 			}
752 			end = B2NB(end);
753 		}
754 		if(next >= limit) {
755 			nb = (uchar*)limit - (uchar*)end;
756 			if(nb > 0){
757 				if(nb < pool->quanta+1)
758 					panic("poolcompact: leftover too small\n");
759 				end->size = nb;
760 				B2T(end)->hdr = end;
761 				pooladd(pool, end);
762 			}
763 			base = base->clink;
764 			if(base == nil)
765 				break;
766 			ptr = B2NB(base);
767 			end = ptr;	/* could do better by copying between chains */
768 			limit = B2LIMIT(base);
769 		} else
770 			ptr = next;
771 	}
772 
773 	return compacted;
774 }
775 
776 void
777 poolsize(Pool *p, int max, int contig)
778 {
779 	void *x;
780 
781 	p->maxsize = max;
782 	if(max == 0)
783 		p->ressize = max;
784 	else if(max < RESERVED)
785 		p->ressize = max;
786 	else
787 		p->ressize = max-RESERVED;
788 	if (contig && max > 0) {
789 		p->chunk = max-1024;
790 		x = poolalloc(p, p->chunk);
791 		if(x == nil)
792 			panic("poolsize: don't have %d bytes\n", p->chunk);
793 		poolfree(p, x);
794 		p->hw = 0;
795 	}
796 }
797 
798 static void
799 _poolfault(void *v, char *msg, ulong c)
800 {
801 	setpanic();
802 	auditmemloc(msg, v);
803 	panic("%s %lux (from %lux/%lux)", msg, v, getcallerpc(&v), c);
804 }
805 
806 static void
807 dumpvl(char *msg, ulong *v, int n)
808 {
809 	int i, l;
810 
811 	l = print("%s at %p: ", msg, v);
812 	for(i = 0; i < n; i++) {
813 		if(l >= 60) {
814 			print("\n");
815 			l = print("    %p: ", v);
816 		}
817 		l += print(" %lux", *v++);
818 	}
819 	print("\n");
820 	USED(l);
821 }
822 
823 static void
824 corrupted(char *str, char *msg, Pool *p, Bhdr *b, void *v)
825 {
826 	print("%s(%p): pool %s CORRUPT: %s at %p'%lud(magic=%lux)\n",
827 		str, v, p->name, msg, b, b->size, b->magic);
828 	dumpvl("bad Bhdr", (ulong *)((ulong)b & ~3)-4, 10);
829 }
830 
831 static void
832 _auditmemloc(char *str, void *v)
833 {
834 	Pool *p;
835 	Bhdr *bc, *ec, *b, *nb, *fb = nil;
836 	char *fmsg, *msg;
837 	ulong fsz;
838 
839 	SET(fsz, fmsg);
840 	for (p = &table.pool[0]; p < &table.pool[nelem(table.pool)]; p++) {
841 		ilock(&p->l);
842 		for (bc = p->chain; bc != nil; bc = bc->clink) {
843 			if (bc->magic != MAGIC_E) {
844 				iunlock(&p->l);
845 				corrupted(str, "chain hdr!=MAGIC_E", p, bc, v);
846 				goto nextpool;
847 			}
848 			ec = B2LIMIT(bc);
849 			if (((Bhdr*)v >= bc) && ((Bhdr*)v < ec))
850 				goto found;
851 		}
852 		iunlock(&p->l);
853 nextpool:	;
854 	}
855 	print("%s: %lux not in pools\n", str, v);
856 	return;
857 
858 found:
859 	for (b = bc; b < ec; b = nb) {
860 		switch(b->magic) {
861 		case MAGIC_F:
862 			msg = "free blk";
863 			break;
864 		case MAGIC_I:
865 			msg = "immutable block";
866 			break;
867 		case MAGIC_A:
868 			msg = "block";
869 			break;
870 		default:
871 			if (b == bc && b->magic == MAGIC_E) {
872 				msg = "pool hdr";
873 				break;
874 			}
875 			iunlock(&p->l);
876 			corrupted(str, "bad magic", p, b, v);
877 			goto badchunk;
878 		}
879 		if (b->size <= 0 || (b->size & p->quanta)) {
880 			iunlock(&p->l);
881 			corrupted(str, "bad size", p, b, v);
882 			goto badchunk;
883 		}
884 		if (fb != nil)
885 			break;
886 		nb = B2NB(b);
887 		if ((Bhdr*)v < nb) {
888 			fb = b;
889 			fsz = b->size;
890 			fmsg = msg;
891 		}
892 	}
893 	iunlock(&p->l);
894 	if (b >= ec) {
895 		if (b > ec)
896 			corrupted(str, "chain size mismatch", p, b, v);
897 		else if (b->magic != MAGIC_E)
898 			corrupted(str, "chain end!=MAGIC_E", p, b, v);
899 	}
900 badchunk:
901 	if (fb != nil) {
902 		print("%s: %lux in %s:", str, v, p->name);
903 		if (fb == v)
904 			print(" is %s '%lux\n", fmsg, fsz);
905 		else
906 			print(" in %s at %lux'%lux\n", fmsg, fb, fsz);
907 		dumpvl("area", (ulong *)((ulong)v & ~3)-4, 20);
908 	}
909 }
910 
911 char *
912 poolaudit(char*(*audit)(int, Bhdr *))
913 {
914 	Pool *p;
915 	Bhdr *bc, *ec, *b;
916 	char *r = nil;
917 
918 	for (p = &table.pool[0]; p < &table.pool[nelem(table.pool)]; p++) {
919 		ilock(&p->l);
920 		for (bc = p->chain; bc != nil; bc = bc->clink) {
921 			if (bc->magic != MAGIC_E) {
922 				iunlock(&p->l);
923 				return "bad chain hdr";
924 			}
925 			ec = B2LIMIT(bc);
926 			for (b = bc; b < ec; b = B2NB(b)) {
927 				if (b->size <= 0 || (b->size & p->quanta))
928 					r = "bad size in bhdr";
929 				else
930 					switch(b->magic) {
931 					case MAGIC_E:
932 						if (b != bc) {
933 							r = "unexpected MAGIC_E";
934 							break;
935 						}
936 					case MAGIC_F:
937 					case MAGIC_A:
938 					case MAGIC_I:
939 						r = audit(p->pnum, b);
940 						break;
941 					default:
942 						r = "bad magic";
943 					}
944 				if (r != nil) {
945 					iunlock(&p->l);
946 					return r;
947 				}
948 			}
949 			if (b != ec || b->magic != MAGIC_E) {
950 				iunlock(&p->l);
951 				return "bad chain ending";
952 			}
953 		}
954 		iunlock(&p->l);
955 	}
956 	return r;
957 }
958 
959 void
960 poolinit(void)
961 {
962 	debugkey('m', "memory pools", poolsummary, 0);
963 }
964