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