xref: /plan9/sys/src/ape/cmd/pdksh/alloc.c (revision 6b6b9ac8b0b103b1e30e4d019522a78c950fce74)
1 /*
2  * area-based allocation built on malloc/free
3  */
4 
5 #include "sh.h"
6 
7 
8 
9 # if DEBUG_ALLOC
10 void acheck ARGS((Area *ap));
11 #  define ACHECK(ap)	acheck(ap)
12 # else /* DEBUG_ALLOC */
13 #  define ACHECK(ap)
14 # endif /* DEBUG_ALLOC */
15 
16 #define	ICELLS	200		/* number of Cells in small Block */
17 
18 typedef union Cell Cell;
19 typedef struct Block Block;
20 
21 /*
22  * The Cells in a Block are organized as a set of objects.
23  * Each object (pointed to by dp) begins with the block it is in
24  * (dp-2)->block, then has a size in (dp-1)->size, which is
25  * followed with "size" data Cells.  Free objects are
26  * linked together via dp->next.
27  */
28 
29 #define NOBJECT_FIELDS	2	/* the block and size `fields' */
30 
31 union Cell {
32 	size_t	size;
33 	Cell   *next;
34 	Block  *block;
35 	struct {int _;} junk;	/* alignment */
36 	double djunk;		/* alignment */
37 };
38 
39 struct Block {
40 	Block  *next;		/* list of Blocks in Area */
41 	Block  *prev;		/* previous block in list */
42 	Cell   *freelist;	/* object free list */
43 	Cell   *last;		/* &b.cell[size] */
44 	Cell	cell [1];	/* [size] Cells for allocation */
45 };
46 
47 static Block aempty = {&aempty, &aempty, aempty.cell, aempty.cell};
48 
49 static void ablockfree ARGS((Block *bp, Area *ap));
50 static void *asplit ARGS((Area *ap, Block *bp, Cell *fp, Cell *fpp, int cells));
51 
52 /* create empty Area */
53 Area *
ainit(ap)54 ainit(ap)
55 	register Area *ap;
56 {
57 	ap->freelist = &aempty;
58 	ACHECK(ap);
59 	return ap;
60 }
61 
62 /* free all object in Area */
63 void
afreeall(ap)64 afreeall(ap)
65 	register Area *ap;
66 {
67 	register Block *bp;
68 	register Block *tmp;
69 
70 	ACHECK(ap);
71 	bp = ap->freelist;
72 	if (bp != NULL && bp != &aempty) {
73 		do {
74 			tmp = bp;
75 			bp = bp->next;
76 			free((void*)tmp);
77 		} while (bp != ap->freelist);
78 		ap->freelist = &aempty;
79 	}
80 	ACHECK(ap);
81 }
82 
83 /* allocate object from Area */
84 void *
alloc(size,ap)85 alloc(size, ap)
86 	size_t size;
87 	register Area *ap;
88 {
89 	int cells, acells;
90 	Block *bp = 0;
91 	Cell *fp = 0, *fpp = 0;
92 
93 	ACHECK(ap);
94 	if (size <= 0)
95 		aerror(ap, "allocate bad size");
96 	cells = (unsigned)(size + sizeof(Cell) - 1) / sizeof(Cell);
97 
98 	/* allocate at least this many cells */
99 	acells = cells + NOBJECT_FIELDS;
100 
101 	/*
102 	 * Only attempt to track small objects - let malloc deal
103 	 * with larger objects. (this way we don't have to deal with
104 	 * coalescing memory, or with releasing it to the system)
105 	 */
106 	if (cells <= ICELLS) {
107 		/* find free Cell large enough */
108 		for (bp = ap->freelist; ; bp = bp->next) {
109 			for (fpp = NULL, fp = bp->freelist;
110 			     fp != bp->last; fpp = fp, fp = fp->next)
111 			{
112 				if ((fp-1)->size >= cells)
113 					goto Found;
114 			}
115 			/* wrapped around Block list, create new Block */
116 			if (bp->next == ap->freelist) {
117 				bp = 0;
118 				break;
119 			}
120 		}
121 		/* Not much free space left?  Allocate a big object this time */
122 		acells += ICELLS;
123 	}
124 	if (bp == 0) {
125 		bp = (Block*) malloc(offsetof(Block, cell[acells]));
126 		if (bp == NULL)
127 			aerror(ap, "cannot allocate");
128 		if (ap->freelist == &aempty) {
129 			ap->freelist = bp->next = bp->prev = bp;
130 		} else {
131 			bp->next = ap->freelist->next;
132 			ap->freelist->next->prev = bp;
133 			ap->freelist->next = bp;
134 			bp->prev = ap->freelist;
135 		}
136 		bp->last = bp->cell + acells;
137 		/* initial free list */
138 		fp = bp->freelist = bp->cell + NOBJECT_FIELDS;
139 		(fp-1)->size = acells - NOBJECT_FIELDS;
140 		(fp-2)->block = bp;
141 		fp->next = bp->last;
142 		fpp = NULL;
143 	}
144 
145   Found:
146 	return asplit(ap, bp, fp, fpp, cells);
147 }
148 
149 /* Do the work of splitting an object into allocated and (possibly) unallocated
150  * objects.  Returns the `allocated' object.
151  */
152 static void *
asplit(ap,bp,fp,fpp,cells)153 asplit(ap, bp, fp, fpp, cells)
154 	Area *ap;
155 	Block *bp;
156 	Cell *fp;
157 	Cell *fpp;
158 	int cells;
159 {
160 	Cell *dp = fp;	/* allocated object */
161 	int split = (fp-1)->size - cells;
162 
163 	ACHECK(ap);
164 	if (split < 0)
165 		aerror(ap, "allocated object too small");
166 	if (split <= NOBJECT_FIELDS) {	/* allocate all */
167 		fp = fp->next;
168 	} else {		/* allocate head, free tail */
169 		Cell *next = fp->next; /* needed, as cells may be 0 */
170 		ap->freelist = bp; /* next time, start looking for space here */
171 		(fp-1)->size = cells;
172 		fp += cells + NOBJECT_FIELDS;
173 		(fp-1)->size = split - NOBJECT_FIELDS;
174 		(fp-2)->block = bp;
175 		fp->next = next;
176 	}
177 	if (fpp == NULL)
178 		bp->freelist = fp;
179 	else
180 		fpp->next = fp;
181 	ACHECK(ap);
182 	return (void*) dp;
183 }
184 
185 /* change size of object -- like realloc */
186 void *
aresize(ptr,size,ap)187 aresize(ptr, size, ap)
188 	register void *ptr;
189 	size_t size;
190 	Area *ap;
191 {
192 	int cells;
193 	Cell *dp = (Cell*) ptr;
194 	int oldcells = dp ? (dp-1)->size : 0;
195 
196 	ACHECK(ap);
197 	if (size <= 0)
198 		aerror(ap, "allocate bad size");
199 	/* New size (in cells) */
200 	cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
201 
202 	/* Is this a large object?  If so, let malloc deal with it
203 	 * directly (unless we are crossing the ICELLS border, in
204 	 * which case the alloc/free below handles it - this should
205 	 * cut down on fragmentation, and will also keep the code
206 	 * working (as it assumes size < ICELLS means it is not
207 	 * a `large object').
208 	 */
209 	if (oldcells > ICELLS && cells > ICELLS) {
210 		Block *bp = (dp-2)->block;
211 		Block *nbp;
212 		/* Saved in case realloc fails.. */
213 		Block *next = bp->next, *prev = bp->prev;
214 
215 		if (bp->freelist != bp->last)
216 			aerror(ap, "allocation resizing free pointer");
217 		nbp = realloc((void *) bp,
218 			      offsetof(Block, cell[cells + NOBJECT_FIELDS]));
219 		if (!nbp) {
220 			/* Have to clean up... */
221 			/* NOTE: If this code changes, similar changes may be
222 			 * needed in ablockfree().
223 			 */
224 			if (next == bp) /* only block */
225 				ap->freelist = &aempty;
226 			else {
227 				next->prev = prev;
228 				prev->next = next;
229 				if (ap->freelist == bp)
230 					ap->freelist = next;
231 			}
232 			aerror(ap, "cannot re-allocate");
233 		}
234 		/* If location changed, keep pointers straight... */
235 		if (nbp != bp) {
236 			if (next == bp) /* only one block */
237 				nbp->next = nbp->prev = nbp;
238 			else {
239 				next->prev = nbp;
240 				prev->next = nbp;
241 			}
242 			if (ap->freelist == bp)
243 				ap->freelist = nbp;
244 			dp = nbp->cell + NOBJECT_FIELDS;
245 			(dp-2)->block = nbp;
246 		}
247 		(dp-1)->size = cells;
248 		nbp->last = nbp->cell + cells + NOBJECT_FIELDS;
249 		nbp->freelist = nbp->last;
250 
251 		ACHECK(ap);
252 		return (void*) dp;
253 	}
254 
255 	/* Check if we can just grow this cell
256 	 * (need to check that cells < ICELLS so we don't make an
257 	 * object a `large' - that would mess everything up).
258 	 */
259 	if (dp && cells > oldcells && cells <= ICELLS) {
260 		Cell *fp, *fpp;
261 		Block *bp = (dp-2)->block;
262 		int need = cells - oldcells - NOBJECT_FIELDS;
263 
264 		/* XXX if we had a flag in an object indicating
265 		 * if the object was free/allocated, we could
266 		 * avoid this loop (perhaps)
267 		 */
268 		for (fpp = NULL, fp = bp->freelist;
269 		     fp != bp->last
270 		     && dp + oldcells + NOBJECT_FIELDS <= fp
271 		     ; fpp = fp, fp = fp->next)
272 		{
273 			if (dp + oldcells + NOBJECT_FIELDS == fp
274 			    && (fp-1)->size >= need)
275 			{
276 				Cell *np = asplit(ap, bp, fp, fpp, need);
277 				/* May get more than we need here */
278 				(dp-1)->size += (np-1)->size + NOBJECT_FIELDS;
279 				ACHECK(ap);
280 				return ptr;
281 			}
282 		}
283 	}
284 
285 	/* Check if we can just shrink this cell
286 	 * (if oldcells > ICELLS, this is a large object and we leave
287 	 * it to malloc...)
288 	 * Note: this also handles cells == oldcells (a no-op).
289 	 */
290 	if (dp && cells <= oldcells && oldcells <= ICELLS) {
291 		int split;
292 
293 		split = oldcells - cells;
294 		if (split <= NOBJECT_FIELDS) /* cannot split */
295 			;
296 		else {		/* shrink head, free tail */
297 			Block *bp = (dp-2)->block;
298 
299 			(dp-1)->size = cells;
300 			dp += cells + NOBJECT_FIELDS;
301 			(dp-1)->size = split - NOBJECT_FIELDS;
302 			(dp-2)->block = bp;
303 			afree((void*)dp, ap);
304 		}
305 		/* ACHECK() done in afree() */
306 		return ptr;
307 	}
308 
309 	/* Have to do it the hard way... */
310 	ptr = alloc(size, ap);
311 	if (dp != NULL) {
312 		size_t s = (dp-1)->size * sizeof(Cell);
313 		if (s > size)
314 			s = size;
315 		memcpy(ptr, dp, s);
316 		afree((void *) dp, ap);
317 	}
318 	/* ACHECK() done in alloc()/afree() */
319 	return ptr;
320 }
321 
322 void
afree(ptr,ap)323 afree(ptr, ap)
324 	void *ptr;
325 	register Area *ap;
326 {
327 	register Block *bp;
328 	register Cell *fp, *fpp;
329 	register Cell *dp = (Cell*)ptr;
330 
331 	ACHECK(ap);
332 	if (ptr == 0)
333 		aerror(ap, "freeing null pointer");
334 	bp = (dp-2)->block;
335 
336 	/* If this is a large object, just free it up... */
337 	/* Release object... */
338 	if ((dp-1)->size > ICELLS) {
339 		ablockfree(bp, ap);
340 		ACHECK(ap);
341 		return;
342 	}
343 
344 	if (dp < &bp->cell[NOBJECT_FIELDS] || dp >= bp->last)
345 		aerror(ap, "freeing memory outside of block (corrupted?)");
346 
347 	/* find position in free list */
348 	/* XXX if we had prev/next pointers for objects, this loop could go */
349 	for (fpp = NULL, fp = bp->freelist; fp < dp; fpp = fp, fp = fp->next)
350 		;
351 
352 	if (fp == dp)
353 		aerror(ap, "freeing free object");
354 
355 	/* join object with next */
356 	if (dp + (dp-1)->size == fp-NOBJECT_FIELDS) { /* adjacent */
357 		(dp-1)->size += (fp-1)->size + NOBJECT_FIELDS;
358 		dp->next = fp->next;
359 	} else			/* non-adjacent */
360 		dp->next = fp;
361 
362 	/* join previous with object */
363 	if (fpp == NULL)
364 		bp->freelist = dp;
365 	else if (fpp + (fpp-1)->size == dp-NOBJECT_FIELDS) { /* adjacent */
366 		(fpp-1)->size += (dp-1)->size + NOBJECT_FIELDS;
367 		fpp->next = dp->next;
368 	} else			/* non-adjacent */
369 		fpp->next = dp;
370 
371 	/* If whole block is free (and we have some other blocks
372 	 * around), release this block back to the system...
373 	 */
374 	if (bp->next != bp && bp->freelist == bp->cell + NOBJECT_FIELDS
375 	    && bp->freelist + (bp->freelist-1)->size == bp->last
376 	    /* XXX and the other block has some free memory? */
377 	    )
378 		ablockfree(bp, ap);
379 	ACHECK(ap);
380 }
381 
382 static void
ablockfree(bp,ap)383 ablockfree(bp, ap)
384 	Block *bp;
385 	Area *ap;
386 {
387 	/* NOTE: If this code changes, similar changes may be
388 	 * needed in alloc() (where realloc fails).
389 	 */
390 
391 	if (bp->next == bp) /* only block */
392 		ap->freelist = &aempty;
393 	else {
394 		bp->next->prev = bp->prev;
395 		bp->prev->next = bp->next;
396 		if (ap->freelist == bp)
397 			ap->freelist = bp->next;
398 	}
399 	free((void*) bp);
400 }
401 
402 # if DEBUG_ALLOC
403 void
acheck(ap)404 acheck(ap)
405 	Area *ap;
406 {
407 	Block *bp, *bpp;
408 	Cell *dp, *dptmp, *fp;
409 	int ok = 1;
410 	int isfree;
411 	static int disabled;
412 
413 	if (disabled)
414 		return;
415 
416 	if (!ap) {
417 		disabled = 1;
418 		aerror(ap, "acheck: null area pointer");
419 	}
420 
421 	bp = ap->freelist;
422 	if (!bp) {
423 		disabled = 1;
424 		aerror(ap, "acheck: null area freelist");
425 	}
426 
427 	/* Nothing to check... */
428 	if (bp == &aempty)
429 		return;
430 
431 	bpp = ap->freelist->prev;
432 	while (1) {
433 		if (bp->prev != bpp) {
434 			shellf("acheck: bp->prev != previous\n");
435 			ok = 0;
436 		}
437 		fp = bp->freelist;
438 		for (dp = &bp->cell[NOBJECT_FIELDS]; dp != bp->last; ) {
439 			if ((dp-2)->block != bp) {
440 				shellf("acheck: fragment's block is wrong\n");
441 				ok = 0;
442 			}
443 			isfree = dp == fp;
444 			if ((dp-1)->size == 0 && isfree) {
445 				shellf("acheck: 0 size frag\n");
446 				ok = 0;
447 			}
448 			if ((dp-1)->size > ICELLS
449 			    && !isfree
450 			    && (dp != &bp->cell[NOBJECT_FIELDS]
451 				|| dp + (dp-1)->size != bp->last))
452 			{
453 				shellf("acheck: big cell doesn't make up whole block\n");
454 				ok = 0;
455 			}
456 			if (isfree) {
457 				if (dp->next <= dp) {
458 					shellf("acheck: free fragment's next <= self\n");
459 					ok = 0;
460 				}
461 				if (dp->next > bp->last) {
462 					shellf("acheck: free fragment's next > last\n");
463 					ok = 0;
464 				}
465 				fp = dp->next;
466 			}
467 			dptmp = dp + (dp-1)->size;
468 			if (dptmp > bp->last) {
469 				shellf("acheck: next frag out of range\n");
470 				ok = 0;
471 				break;
472 			} else if (dptmp != bp->last) {
473 				dptmp += NOBJECT_FIELDS;
474 				if (dptmp > bp->last) {
475 					shellf("acheck: next frag just out of range\n");
476 					ok = 0;
477 					break;
478 				}
479 			}
480 			if (isfree && dptmp == fp && dptmp != bp->last) {
481 				shellf("acheck: adjacent free frags\n");
482 				ok = 0;
483 			} else if (dptmp > fp) {
484 				shellf("acheck: free frag list messed up\n");
485 				ok = 0;
486 			}
487 			dp = dptmp;
488 		}
489 		bpp = bp;
490 		bp = bp->next;
491 		if (bp == ap->freelist)
492 			break;
493 	}
494 	if (!ok) {
495 		disabled = 1;
496 		aerror(ap, "acheck failed");
497 	}
498 }
499 
500 void
aprint(ap,ptr,size)501 aprint(ap, ptr, size)
502 	register Area *ap;
503 	void *ptr;
504 	size_t size;
505 {
506 	Block *bp;
507 
508 	if (!ap)
509 		shellf("aprint: null area pointer\n");
510 	else if (!(bp = ap->freelist))
511 		shellf("aprint: null area freelist\n");
512 	else if (bp == &aempty)
513 		shellf("aprint: area is empty\n");
514 	else {
515 		int i;
516 		Cell *dp, *fp;
517 		Block *bpp;
518 
519 		bpp = ap->freelist->prev;
520 		for (i = 0; ; i++) {
521 			if (ptr) {
522 				void *eptr = (void *) (((char *) ptr) + size);
523 				/* print block only if it overlaps ptr/size */
524 				if (!((ptr >= (void *) bp
525 				       && ptr <= (void *) bp->last)
526 				      || (eptr >= (void *) bp
527 				         && eptr <= (void *) bp->last)))
528 					continue;
529 				shellf("aprint: overlap of 0x%p .. 0x%p\n",
530 					ptr, eptr);
531 			}
532 			if (bp->prev != bpp || bp->next->prev != bp)
533 				shellf(
534 	"aprint: BAD prev pointer: bp %p, bp->prev %p, bp->next %p, bpp=%p\n",
535 					bp, bp->prev, bp->next, bpp);
536 			shellf("aprint: block %2d (p=%p,%p,n=%p): 0x%p .. 0x%p (%ld)\n", i,
537 				bp->prev, bp, bp->next,
538 				bp->cell, bp->last,
539 				(long) ((char *) bp->last - (char *) bp->cell));
540 			fp = bp->freelist;
541 			if (bp->last <= bp->cell + NOBJECT_FIELDS)
542 				shellf(
543 			"aprint: BAD bp->last too small: %p <= %p\n",
544 					bp->last, bp->cell + NOBJECT_FIELDS);
545 			if (bp->freelist < bp->cell + NOBJECT_FIELDS
546 			    || bp->freelist > bp->last)
547 				shellf(
548 			"aprint: BAD bp->freelist %p out of range: %p .. %p\n",
549 					bp->freelist,
550 					bp->cell + NOBJECT_FIELDS, bp->last);
551 			for (dp = bp->cell; dp != bp->last ; ) {
552 				dp += NOBJECT_FIELDS;
553 				shellf(
554 				    "aprint:   0x%p .. 0x%p (%ld) %s\n",
555 					(dp-NOBJECT_FIELDS),
556 					(dp-NOBJECT_FIELDS) + (dp-1)->size
557 						+ NOBJECT_FIELDS,
558 					(long) ((dp-1)->size + NOBJECT_FIELDS)
559 						* sizeof(Cell),
560 					dp == fp ? "free" : "allocated");
561 				if ((dp-2)->block != bp)
562 					shellf(
563 					"aprint: BAD dp->block %p != bp %p\n",
564 						(dp-2)->block, bp);
565 				if (dp > bp->last)
566 					shellf(
567 				"aprint: BAD dp gone past block: %p > %p\n",
568 						dp, bp->last);
569 				if (dp > fp)
570 					shellf(
571 				"aprint: BAD dp gone past free: %p > %p\n",
572 						dp, fp);
573 				if (dp == fp) {
574 					fp = fp->next;
575 					if (fp < dp || fp > bp->last)
576 						shellf(
577 			"aprint: BAD free object %p out of range: %p .. %p\n",
578 							fp,
579 							dp, bp->last);
580 				}
581 				dp += (dp-1)->size;
582 			}
583 			bpp = bp;
584 			bp = bp->next;
585 			if (bp == ap->freelist)
586 				break;
587 		}
588 	}
589 }
590 
591 #endif
592