![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to st_alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / streams / src|
Return to st_alloc.c CVS log | Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / streams / src |
1.1 root 1: /*
2: * Main C routines for the quick heap manager.
3: *
4: * This implementation is directly derived from the article in which this
5: * algorithm first appeared ;
6: *
7: * "Efficient Implementation of the First-Fit Strategy for Dynamic
8: * Storage Allocation"
9: * R. P. Brent, Australian National University
10: * ACM Transactions on Programming Languages and Systems
11: * Volume 11, No. 3, July 1989 pp 388-403.
12: */
13:
14: /*
15: *-IMPORTS:
16: * <common/ccompat.h>
17: * __CONST__
18: * __USE_PROTO__
19: * __ARGS ()
20: * <common/xdebug.h>
21: * __LOCAL__
22: * <stddef.h>
23: * NULL
24: */
25:
26: #include <common/ccompat.h>
27: #include <common/xdebug.h>
28: #include <stddef.h>
29:
30: #include <kernel/st_alloc.h>
31:
32:
33: /*
34: * Since this code can be used in an embedded environment, we may not want to
35: * use the C library version of assert () to report errors. On the other hand,
36: * in a hosted environment we might.
37: */
38:
39: #if _HOSTED
40:
41: #include <assert.h>
42:
43: #define ASSERT(x) assert (x)
44:
45: #else
46:
47: #include <sys/debug.h>
48:
49: #endif
50:
51:
52: /*
53: * In several places in the code we need to adjust pointer values by +1 or -1
54: * to account for the space taken up the by the links between adjacent
55: * blocks, allocated or not.
56: *
57: * Here we define some private macros to help deal with this. While it is
58: * correct and reasonably documented as it stands, we will likely want to
59: * implement a variant algorithm that does not keep allocated blocks on a
60: * list. This should reduce both search time and space overhead, with the
61: * expense of requiring the user to supply the original block size. For now,
62: * we pay both penalties.
63: */
64:
65: #define _ST_WORD_S sizeof (_ST_WORD_T)
66:
67: #define _ST_AHDR_SIZE 1 /* word size of an allocated header */
68:
69: #define _ST_BYTE2WORD(s) ((s + (1 + _ST_AHDR_SIZE) * _ST_WORD_S - 1) / _ST_WORD_S)
70: /*
71: * _ST_BYTE2WORD () converts a size
72: * passed in by a client into a block
73: * word size, which includes space
74: * for the allocated-block header.
75: */
76: #define _ST_WORD2BYTE(s) ((s - _ST_AHDR_SIZE) * _ST_WORD_S)
77: /*
78: * _ST_WORD2BYTE () reverses the
79: * mapping given by _ST_BYTE2WORD ().
80: */
81: #define _ST_ADDR2PTR(q,a) ((__VOID__ *) a)
82: /*
83: * Mapping from an _ST_ADDR_T to a
84: * user pointer to real memory.
85: */
86: #define _ST_PTR2ADDR(q,a) ((_ST_WORD_T *) a)
87: /*
88: * Mapping from a user pointer to
89: * an _ST_ADDR_T.
90: */
91:
92: #define _ST_BUCKET_BASE(q,b) (q->_arena_base + (b) * q->_words_per_bucket)
93:
94: /*
95: * This function does some general checks on the consistency of the contents
96: * of the _ST_HEAP_CONTROL block passed as "q". If the contents of the control
97: * block (and the auxiliary arrays which are part of it) do not pass muster,
98: * then the _qheap_error member of the control block is set, and the function
99: * returns an error indication.
100: *
101: * The return value is 0 if the control block tested OK, -1 if it did not.
102: */
103:
104: #if __USE_PROTO__
105: int (st_assert) (_ST_HEAP_CONTROL_P q)
106: #else
107: int
108: st_assert __ARGS ((q))
109: _ST_HEAP_CONTROL_P q;
110: #endif
111: {
112: _ST_ADDR_T scan;
113: int count, cntl, bucket;
114:
115: scan = _ST_BUCKET_BASE (q, 0);
116:
117: for (bucket = 0 ; bucket < q->_buckets_inuse ; bucket ++) {
118: _ST_ADDR_T end;
119: int max;
120:
121:
122: if ((end = _ST_BUCKET_BASE (q, bucket + 1)) > q->_arena_end)
123: end = q->_arena_end;
124:
125: /*
126: * Verify that _ST_HEAP_FIRST () points within the bucket,
127: * to the current value of scan if there are blocks in this
128: * bucket.
129: */
130:
131:
132: if (scan < end &&
133: _ST_HEAP_FIRST (q, bucket) != scan) {
134:
135: _ST_SET_ERROR (q, "Bad first block pointer in bucket");
136: return -1;
137: } else if (scan >= end && _ST_HEAP_FIRST (q, bucket) < end) {
138:
139: _ST_SET_ERROR (q, "First block pointer should be pointing past bucket end");
140: return -1;
141: }
142:
143:
144: /*
145: * Walk over the contents of the bucket to verify the maximum
146: * block size within the bucket. We also check here for
147: * consecutive unmerged free blocks.
148: */
149:
150: count = max = 0;
151:
152: while (scan < end) {
153:
154: cntl = _ST_BLOCK_CONTROL (q, scan);
155:
156: if (_ST_BLOCK_FREE (cntl)) { /* block is free */
157:
158: if (cntl > max)
159: max = cntl;
160:
161: if (++ count > 1) {
162:
163: _ST_SET_ERROR (q, "Adjacent free blocks not merged");
164: return -1;
165: }
166: } else /* block in use */
167: count = 0;
168:
169: scan = _ST_HEAP_NEXT (scan, cntl);
170: }
171:
172: if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) != max) {
173:
174: _ST_SET_ERROR (q, "Incorrect maximum free block size");
175: return -1;
176: }
177:
178:
179: /*
180: * Check for unmerged free blocks between bucket boundaries.
181: */
182:
183: if (count != 0 && scan < q->_arena_end &&
184: _ST_BLOCK_FREE (_ST_BLOCK_CONTROL (q, scan))) {
185:
186: _ST_SET_ERROR (q, "Unmerged free blocks between block boundaries");
187: return -1;
188: }
189: }
190:
191:
192: if (scan != q->_arena_end) {
193:
194: _ST_SET_ERROR (q, "Last block too large!");
195: return -1;
196: }
197:
198: return 0;
199: }
200:
201:
202: /*
203: * st_double () doubles the depth of the index heap, assuming that
204: * _buckets_inuse < _buckets_maximum / 2
205: *
206: * For internal use only.
207: */
208:
209: #if __USE_PROTO__
210: __LOCAL__ void (st_double) (_ST_HEAP_CONTROL_P q)
211: #else
212: __LOCAL__ void
213: st_double __ARGS ((q))
214: _ST_HEAP_CONTROL_P q;
215: #endif
216: {
217: int i,k;
218:
219: ASSERT (q->_buckets_inuse * 2 <= q->_buckets_maximum);
220:
221:
222: /*
223: * The new buckets don't have any blocks starting within them, so
224: * set the base address over the top.
225: */
226:
227: k = q->_buckets_inuse;
228: for (i = 0 ; i < k ; i ++)
229: q->_bucket_first [i + k] = q->_arena_end;
230:
231: /*
232: * The bucket size heap needs to be expanded by copying the maximum
233: * sizes down for the preexisting buckets, and inserting zeroes for
234: * the new buckets.
235: * eg max(b1,b2) b1 b2
236: * becomes max(b1,b2) max(b1,b2) 0 b1 b2 0 0
237: */
238:
239: for (; k > 0 ; k >>= 1)
240: for (i = 0 ; i < k ; i ++) {
241:
242: _ST_HEAP_BIGGEST (q, 2 * k + i) = _ST_HEAP_BIGGEST (q, k + i);
243: _ST_HEAP_BIGGEST (q, 3 * k + i) = 0;
244: }
245:
246: q->_buckets_inuse <<= 1;
247: }
248:
249:
250: /*
251: * st_reduced () does the housekeeping necessary if a block with control word
252: * at "a" has been allocated, or merged with a block on it's left in a
253: * different segment. Note that we count on a block having been freed/
254: * allocated and having a valid control word.
255: *
256: * It should be that case that the _ST_HEAP_FIRST () has already been updated
257: * in order for this routine to correctly calculate the sizes
258: *
259: * This implementation modifies this function, in that a test
260: * if (BlockIsFree && CurrentMaximum > SizeOfNewBlock)
261: * return;
262: * from the C transliteration of the published algorithm has been moved out
263: * to the callers of this function. This allows the callers to use a block
264: * size value cached in their locals to perform the calculation, rather than
265: * making this function fetch the control word for the block. This is NOT
266: * an important size/speed optimisation (although parts of the original test
267: * have been elided in the broken-out version), rather it allows algorithms
268: * like realloc () considerably more latitude in the order in which things
269: * are done.
270: *
271: * This function was called blfix1 () in the published algorithm. The original
272: * algorithm passed in the block address, but since we have moved the check
273: * discussed above outside, we only need the bucket number.
274: */
275:
276: #if __USE_PROTO__
277: __LOCAL__ void (st_reduced) (_ST_HEAP_CONTROL_P q, int bucket)
278: #else
279: __LOCAL__ void
280: st_reduced __ARGS ((q, bucket))
281: _ST_HEAP_CONTROL_P q;
282: int bucket;
283: #endif
284: {
285: _ST_ADDR_T first, next;
286: _ST_WORD_T max;
287:
288: #if 0 /* this test moved out to our callers */
289: /*
290: * if (BlockIsFree && CurrentMaximum > SizeOfNewBlock) then there
291: * is nothing to be done to segment "bucket".
292: */
293:
294: max = _ST_BLOCK_CONTROL (q, a);
295: if (_ST_BLOCK_FREE (max) &&
296: _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) > _ST_BLOCK_SIZE (max))
297: return;
298: #endif
299:
300: /*
301: * Work out address of first block in "current" bucket, and the
302: * base address of the "next" bucket. Note that we have to test to
303: * see if "next" winds up past the end of space because the total
304: * size of the arena may not divide evenly into buckets..
305: */
306:
307: first = _ST_HEAP_FIRST (q, bucket);
308: next = q->_arena_base + (bucket + 1) * q->_words_per_bucket;
309:
310: if (next >= q->_arena_end)
311: next = q->_arena_end;
312:
313: /*
314: * Calculate (by walking the block chain) the new maximum size free
315: * block in this bucket, which may now be empty.
316: */
317:
318: max = 0;
319: while (first < next) { /* There is a block starting in this bucket */
320: _ST_WORD_T cntl = _ST_BLOCK_CONTROL (q, first);
321:
322: ASSERT (cntl != 0);
323:
324: if (max < cntl)
325: max = cntl;
326:
327: first = _ST_HEAP_NEXT (first, cntl);
328: }
329:
330:
331: /*
332: * Now propagate the new maximum size information up the heap.
333: */
334:
335: bucket += q->_buckets_inuse;
336: _ST_HEAP_BIGGEST (q, 0) = 0; /* sentinel */
337:
338: while (_ST_HEAP_BIGGEST (q, bucket) > max) {
339: int temp;
340:
341: _ST_HEAP_BIGGEST (q, bucket) = max;
342:
343: temp = _ST_HEAP_BIGGEST (q, _ST_BUCKET_SIBLING (bucket));
344: if (max < temp)
345: max = temp;
346:
347: bucket = _ST_BUCKET_PARENT (bucket);
348: }
349: }
350:
351:
352: /*
353: * st_grown () does the housekeeping necessary after a block with control word
354: * at "a" is freed, or merged with a block on its right, or created by
355: * splitting (with "a" on the right of the split, in a different bucket than
356: * the start of the original block that was split)
357: *
358: * This function was called blfix2 () in the published algorithm.
359: */
360:
361: #if __USE_PROTO__
362: __LOCAL__ void (st_grown) (_ST_HEAP_CONTROL_P q, _ST_ADDR_T a, int bucket)
363: #else
364: __LOCAL__ void
365: st_grown __ARGS ((q, a, bucket))
366: _ST_HEAP_CONTROL_P q;
367: _ST_ADDR_T a;
368: int bucket;
369: #endif
370: {
371: int max;
372:
373: ASSERT (bucket == _ST_HEAP_BUCKET (q, a));
374:
375:
376: /*
377: * Expand the number of buckets in the heap if necessary.
378: */
379:
380: while (bucket >= q->_buckets_inuse)
381: st_double (q);
382:
383: /*
384: * This may be a new first free block.
385: */
386:
387: if (_ST_HEAP_FIRST (q, bucket) > a)
388: _ST_HEAP_FIRST (q, bucket) = a;
389:
390: /*
391: * Propagate changed block-size information upwards through heap.
392: */
393:
394: bucket += q->_buckets_inuse;
395: max = _ST_BLOCK_CONTROL (q, a);
396: _ST_HEAP_BIGGEST (q, 0) = max; /* sentinel */
397:
398: while (_ST_HEAP_BIGGEST (q, bucket) < max) {
399:
400: _ST_HEAP_BIGGEST (q, bucket) = max;
401:
402: bucket = _ST_BUCKET_PARENT (bucket);
403: }
404: }
405:
406:
407: /*
408: * Returns the predecessor block to "a", which is guaranteed to exist thanks
409: * to the dummy first block.
410: *
411: * If the address passed in does not belong to a valid block then the value
412: * returned is the same value that was passed in, ie "a".
413: */
414:
415: #if __USE_PROTO__
416: __LOCAL__ _ST_ADDR_T (st_pred) (_ST_HEAP_CONTROL_P q, _ST_ADDR_T a, int bucket)
417: #else
418: __LOCAL__ _ST_ADDR_T
419: st_pred __ARGS ((q, a, bucket))
420: _ST_HEAP_CONTROL_P q;
421: _ST_ADDR_T a;
422: int bucket;
423: #endif
424: {
425: _ST_ADDR_T prev, scan;
426:
427: ASSERT (bucket == _ST_HEAP_BUCKET (q, a));
428:
429:
430: /*
431: * If the passed-in block is the first in the bucket, then the
432: * predecessor lives in the rightmost non-empty bucket to the left.
433: */
434:
435: if (_ST_HEAP_FIRST (q, bucket) == a) {
436: /*
437: * We walk the heap to find the nearest bucket on the left
438: * that has a free block in it, as buckets that do not
439: * contain free blocks may not contain a valid "first block"
440: * entry, since due to block coalescence these entries may
441: * refer to blocks which have been combined with others.
442: *
443: * st_pred () is the only code which is affected by this.
444: */
445:
446: bucket += q->_buckets_inuse;
447:
448: _ST_HEAP_BIGGEST (q, 0) = 1; /* boundary */
449:
450: while (_ST_HEAP_BIGGEST (q, bucket - 1) == 0)
451: bucket = _ST_BUCKET_PARENT (bucket);
452:
453: /*
454: * Code here fixes two known "defects" in the original
455: * published algorithm.
456: * (i) In the case where "bucket" above could reach the root
457: * node (eg, every word of storage had been previously
458: * allocated), the "bucket" would go to zero and the
459: * descend code would loop indefinitely.
460: * (ii) In the case where storage in the left subtree of the
461: * heap relative to the initial point is completely
462: * allocated, the code to climb the heap will eventually
463: * look into the next higher level of the heap once
464: * "bucket" became a power of two (unless defect (i)
465: * occurred instead) and as a result would descend into
466: * the wrong part of the heap.
467: *
468: * We check here for "bucket" being a power of two, in which
469: * case we snap the result of the search to the lowest bucket
470: * on the left.
471: */
472:
473: #define IS_POWER_OF_TWO(n) (((n - 1) ^ n) >= n)
474:
475: if (! IS_POWER_OF_TWO (bucket)) {
476:
477: bucket --;
478:
479: while (bucket < q->_buckets_inuse) {
480:
481: bucket = 2 * bucket + 1;
482: if (_ST_HEAP_BIGGEST (q, bucket) <= 0)
483: bucket --;
484: }
485:
486: bucket -= q->_buckets_inuse;
487: } else
488: bucket = 0;
489: }
490:
491:
492: /*
493: * Either way, find the predecessor block by following the internal
494: * block linkage within this bucket.
495: */
496:
497: scan = _ST_HEAP_FIRST (q, bucket);
498: do {
499: prev = scan;
500: scan = _ST_HEAP_NEXT (scan, _ST_BLOCK_CONTROL (q, scan));
501:
502: ASSERT (prev != scan);
503: } while (scan < a);
504:
505: if (scan != a) {
506:
507: _ST_SET_ERROR (q, "Unable to find previous for block");
508: return a; /* flag error by returning same */
509: }
510:
511: return prev;
512: }
513:
514:
515: /*
516: * Returns the index of a block of at least "size" words, or 0 if no such
517: * block exists.
518: */
519:
520: #if __USE_PROTO__
521: __VOID__ * (st_alloc) (_ST_HEAP_CONTROL_P q, size_t size)
522: #else
523: __VOID__ *
524: st_alloc __ARGS ((q, size))
525: _ST_HEAP_CONTROL_P q;
526: size_t size;
527: #endif
528: {
529: int n, bucket, cntl;
530: _ST_ADDR_T scan;
531:
532: /*
533: * Before we begin, convert the size_t passed in into a word count.
534: * Note that we assume that the integer division of a size_t will
535: * be optimised by the compiler into an appropriate number of right-
536: * shifts (since a size_t is always unsigned, right?).
537: *
538: * We store the result into an integer because the free/used
539: * comparison means we involve the sign bit.
540: */
541:
542: n = _ST_BYTE2WORD (size); /* includes header size */
543:
544:
545: /*
546: * Since the node at the top of the size heap contains the size of
547: * the largest available block, quickly determine whether or not
548: * this request can be satisfied at all.
549: */
550:
551: if (_ST_HEAP_BIGGEST (q, 1) < n)
552: return 0;
553:
554:
555: /*
556: * Now traverse the heap to find the first bucket containing a block
557: * of sufficient size to satisfy the request.
558: */
559:
560: bucket = 1;
561:
562: while (bucket < q->_buckets_inuse) {
563:
564: bucket = 2 * bucket;
565: if (_ST_HEAP_BIGGEST (q, bucket) < n)
566: bucket ++;
567: }
568:
569: bucket -= q->_buckets_inuse;
570:
571:
572: /*
573: * Now traverse the internal linkage within the bucket to find the
574: * first block of the requisite size.
575: */
576:
577: scan = _ST_HEAP_FIRST (q, bucket);
578:
579: while ((cntl = _ST_BLOCK_CONTROL (q, scan)) < n) {
580:
581: ASSERT (cntl != 0);
582: scan = _ST_HEAP_NEXT (scan, cntl);
583: }
584:
585:
586: /*
587: * Now "scan" contains the index of the control word of the
588: * desired block.
589: */
590:
591: _ST_BLOCK_SET_USED (q, scan, n);
592:
593:
594: /*
595: * The published algorithm used a variable here to hold the result
596: * of a test on the basis that the call to st_grown () below might
597: * change the result. Actually, st_grown () would not change the
598: * result, but since st_grown () may call st_double () and alter
599: * the offset of the leaf layer of the block heap, that would
600: * invalidate his test. Since our "bucket" does not have that offset
601: * built into it, we perform the test when needed.
602: *
603: * Note that we still perform st_grown () before st_reduced (), as
604: * in the original. The reason for this was not explicated, but
605: * appears to be because doing it in this order may reduce the
606: * average number of heap nodes visited due to the particular heap
607: * update termination conditions.
608: */
609:
610: /*
611: * If necessary, split block; this may require a call to st_grown ()
612: * if the block created by the split is not in the same bucket.
613: */
614:
615: if (cntl > n) {
616: _ST_ADDR_T next = _ST_HEAP_NEXT (scan, n);
617: int next_bucket;
618:
619: _ST_BLOCK_SET_FREE (q, next, cntl - n);
620:
621: if ((next_bucket = _ST_HEAP_BUCKET (q, next)) > bucket)
622: st_grown (q, next, next_bucket);
623: }
624:
625: if (cntl == _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse))
626: st_reduced (q, bucket);
627:
628: return _ST_ADDR2PTR (q, _ST_HEAP_NEXT (scan, _ST_AHDR_SIZE));
629: }
630:
631:
632: /*
633: * Release a block of memory obtained using st_alloc (), where "a" is the
634: * memory word index that was returned by st_alloc ().
635: *
636: * Note that this function comes in two flavours, depending on whether you
637: * want clients to have to pass in the block-size.
638: */
639:
640: #if __USE_PROTO__
641: int (st_free) (_ST_HEAP_CONTROL_P q, __VOID__ * a ST_FREE_SIZE (size_t size))
642: #else
643: int
644: #ifdef USE_ST_SIZE
645: st_free __ARGS ((q, a, size))
646: size_t size;
647: #else
648: st_free __ARGS ((q, a))
649: #endif
650: _ST_HEAP_CONTROL_P q;
651: __VOID__ * a;
652: #endif
653: {
654: int bucket, cntl, temp;
655: _ST_ADDR_T prev, next, addr;
656: int reduce = 0; /* optimisation flag, see below */
657:
658: addr = _ST_HEAP_NEXT_RAW (_ST_PTR2ADDR (q, a), - _ST_AHDR_SIZE);
659:
660: cntl = _ST_BLOCK_CONTROL (q, addr);
661:
662: if (_ST_BLOCK_FREE (cntl))
663: return -1; /* Block already free */
664:
665: cntl = _ST_BLOCK_SIZE (cntl);
666:
667: #ifdef USE_ST_SIZE
668: /*
669: * As discussed in st_alloc (), we convert a passed-in byte count
670: * into a word count to isolate the clients from the notion of
671: * what we are using as a "word".
672: *
673: * The expression we want to test is
674: * cntl == ceil (size / sizeof (_ST_WORD_T)) + 1
675: * where the + 1 factor is for the block size header.
676: */
677:
678: if (cntl != _ST_BYTE2WORD (size))
679: return -2; /* Block size mismatch */
680: #endif
681:
682: bucket = _ST_HEAP_BUCKET (q, addr);
683:
684:
685: /*
686: * Locate the previous block. Note that we attempt this operation
687: * considerably earlier than we really need to; this is done since
688: * it is the only really reliable way of verifying that the address
689: * given to this routine really does belong to a block that was
690: * allocated with st_alloc ().
691: *
692: * (Note that the above statement is only true for versions of the
693: * algorithm that maintain allocated blocks on the block list)
694: */
695:
696: if ((prev = st_pred (q, addr, bucket)) == addr)
697: return -3; /* not a valid block */
698:
699: /*
700: * Now that we have performed some sanity checks, free the block.
701: */
702:
703: _ST_BLOCK_SET_FREE (q, addr, cntl);
704:
705:
706: /*
707: * Check the next rightmost block to see if we should merge with it.
708: */
709:
710: next = _ST_HEAP_NEXT (addr, cntl);
711:
712: if (next < q->_arena_end &&
713: _ST_BLOCK_FREE (temp = _ST_BLOCK_CONTROL (q, next))) {
714: /*
715: * Merge the new block with its immediate neighbour on the
716: * right. Note that we elide the _ST_BLOCK_SIZE () of temp
717: * immediately below because _ST_BLOCK_SET_FREE masks the
718: * third argument anyway.
719: */
720:
721: _ST_BLOCK_SET_FREE (q, addr, cntl += temp);
722:
723: temp = _ST_HEAP_BUCKET (q, next);
724:
725: /*
726: * Do we need to recalculate the maximum block size
727: * for the block that "next" is in ? Yes, iff
728: * heap_biggest (temp) == block_size (next).
729: * We elide the call to _ST_BLOCK_SIZE below since
730: * we know the block is free, hence needs no masking.
731: */
732:
733: reduce = _ST_HEAP_BIGGEST (q, temp + q->_buckets_inuse) ==
734: _ST_BLOCK_CONTROL (q, next);
735: ASSERT (_ST_HEAP_BIGGEST (q, temp + q->_buckets_inuse) >=
736: _ST_BLOCK_CONTROL (q, next));
737: if (temp > bucket) {
738:
739: _ST_HEAP_FIRST (q, temp) = _ST_HEAP_NEXT (addr, cntl);
740:
741: if (reduce) {
742:
743: st_reduced (q, temp);
744: reduce = 0;
745: }
746: } else
747: ASSERT (_ST_HEAP_FIRST (q, temp) != next);
748: }
749:
750:
751: /*
752: * Check the next leftmost block to see if we should merge with it.
753: */
754: /*
755: * Optimisation note: the published version of the algorithm
756: * does a normal call to st_reduced () below. However, since we
757: * are freeing a block, we note that the only circumstance where
758: * this will be at all necessary is when the block we are freeing
759: * was merged with a block on it's right which was the previous
760: * largest free block (or at least the same size). We can thus
761: * reduce the number of calls to st_reduced () by putting in an
762: * extra guard condition with a flag set above.
763: *
764: * Is this worth the effort? Let's profile it and see.
765: */
766:
767: if (_ST_BLOCK_FREE (temp = _ST_BLOCK_CONTROL (q, prev))) {
768:
769: _ST_BLOCK_SET_FREE (q, prev, cntl += temp);
770:
771: /*
772: * If we are merging with a block in a previous bucket, then
773: * we must adjust our "first block" and call st_reduced () to
774: * update the size heap.
775: */
776:
777: if (_ST_HEAP_FIRST (q, bucket) == addr) {
778:
779: _ST_HEAP_FIRST (q, bucket) = _ST_HEAP_NEXT (prev, cntl);
780:
781: /*
782: * As discussed above, we call st_reduced () iff
783: * we have merged with a block on the right of a
784: * size that indicates recomputing is necessary.
785: */
786:
787: if (reduce) {
788:
789: ASSERT (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) <=
790: _ST_BLOCK_CONTROL (q, addr));
791: st_reduced (q, bucket);
792: }
793:
794: /*
795: * We cannot incrementally update "bucket" since
796: * "prev" may refer to address a number of buckets
797: * prior to "addr".
798: */
799:
800: bucket = _ST_HEAP_BUCKET (q, prev);
801: }
802:
803: st_grown (q, prev, bucket);
804:
805: } else if (cntl > _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse)) {
806: /*
807: * The total size of the newly freed block exceeds the
808: * previous maximum block size of the current bucket, so call
809: * st_grown () to update the size heap.
810: *
811: * Note that st_alloc () calls st_grown () without performing
812: * the size test like we do, because st_alloc () may want the
813: * heap size doubled. Here, that cannot happen, so we avoid
814: * the call.
815: */
816:
817: st_grown (q, addr, bucket);
818: }
819:
820: return 0;
821: }
822:
823:
824: #ifndef _ST_BLOCK_COPY
825:
826: /*
827: * Helper function which supplies a default block-copy routine for the
828: * st_realloc () function in case there is no special-purpose copy routine
829: * in the target environment.
830: */
831:
832: #if __USE_PROTO__
833: __LOCAL__ void (st_copy) (_ST_WORD_T * dest, __CONST__ _ST_WORD_T * src,
834: size_t copywords)
835: #else
836: __LOCAL__ void
837: st_copy __ARGS ((dest, src, copywords))
838: _ST_WORD_T * dest;
839: _ST_WORD_T * src;
840: size_t copywords;
841: #endif
842: {
843: while (copywords --)
844: * dest ++ = * src ++;
845: }
846:
847: #define _ST_BLOCK_COPY(q,d,s,n) st_copy (_ST_HEAP_ADDR (q, d), _ST_HEAP_ADDR(q, s), n)
848:
849: #endif /* ! defined (_ST_BLOCK_COPY) */
850:
851:
852: /*
853: * Request that the block of memory at address "a" be grown (or shrunk) in
854: * size to "newsize" bytes (possibly from "oldsize" bytes). The returned
855: * value is the base address of the new block of memory, which may be
856: * different than the old address. If the block was moved, then the contents
857: * are guarenteed to be preserved bit-for-bit, but the client must take
858: * responsibility for relocating pointers.
859: *
860: * If it is not possible for the allocator to either grow or relocate the
861: * block due to a lack of space, st_realloc () returns 0, which for us can
862: * never be a valid return address. In this case, the original block has been
863: * left untouched.
864: *
865: * Note that this function comes in two flavours, depending on whether you
866: * want clients to have to pass in the block-size.
867: *
868: * --------------------------------------------------------------------------
869: *
870: * Design note: there are many, many ways that this function could be
871: * implemented, depending on how sensitive you are to issues of code size,
872: * execution speed, or arena space efficiency.
873: *
874: * The possible checks are (in order of execution time reduction)
875: * (i) Check to see if the block can be extended upwards,
876: * (ii) Find the previous block to see if it can be extended downwards,
877: * (iii) See if we can grow both down and up to fulfil the request,
878: * (iv) Find any other block of sufficient size to fulfil the request.
879: *
880: * The primary criterion I have set for this routine is that it must always
881: * succeed in finding memory to saisfy the request. Note that the number of
882: * cases that this produces as a result is extremely large, but that it seems
883: * better to fulfil a user's request than to fail it simply on the basis that
884: * we want the common case to be fast.
885: *
886: * For now, we'll prefer not to copy, and reduce our code size by just
887: * relying on st_alloc () and st_free () for the worst case... but be aware
888: * that it might be a good idea to set a "realloc mode" in the heap control
889: * block that specifies how we order operations in the case where we break
890: * out the details of new () and disp ().
891: */
892:
893: #if __USE_PROTO__
894: __VOID__ * (st_realloc) (_ST_HEAP_CONTROL_P q, __VOID__ * a, size_t newsize
895: ST_FREE_SIZE (size_t oldsize))
896: #else
897: __VOID__ *
898: #ifdef USE_ST_SIZE
899: st_realloc __ARGS ((q, a, newsize, oldsize))
900: size_t oldsize;
901: #else
902: st_realloc __ARGS ((q, a, newsize))
903: #endif
904: _ST_HEAP_CONTROL_P q;
905: __VOID__ * a;
906: size_t newsize;
907: #endif
908: {
909: int bucket, cntl, prev_reduce, next_bucket, next_first;
910: int delta; /* block size change in words */
911: _ST_ADDR_T prev, addr, next;
912:
913: addr = _ST_HEAP_NEXT_RAW (_ST_PTR2ADDR (q, a), -1);
914:
915: cntl = _ST_BLOCK_CONTROL (q, addr);
916:
917: if (_ST_BLOCK_FREE (cntl))
918: return (_ST_ADDR_T) -1; /* Block is free ! */
919:
920: cntl = _ST_BLOCK_SIZE (cntl); /* work with free units */
921:
922:
923: /*
924: * Before we begin, let's convert newsize (and optionally oldsize)
925: * to word counts from byte counts. This may mean that both round
926: * to the same word count and we don't need to do anything (big win!)
927: */
928:
929: newsize = _ST_BYTE2WORD (newsize);
930:
931: #ifdef USE_ST_SIZE
932: if (cntl != _ST_BYTE2WORD (oldsize))
933: return (_ST_ADDR_T) -2; /* Block size mismatch */
934: #endif
935: if ((delta = newsize - cntl) == 0)
936: return a; /* Already done! What service! */
937:
938: bucket = _ST_HEAP_BUCKET (q, addr);
939:
940:
941: /*
942: * Locate the previous block, so that we can see if we can grow
943: * down into it. Note that in the variant system where allocated
944: * blocks are not part of a chain (in order to save space) that by
945: * finding the previous free block we achieve an equivalent result,
946: * since we cannot grow down unless we have an adjacent free block.
947: *
948: * Note also that in the case where allocated blocks are not
949: * chained, finding the previous free block is a prerequisite to
950: * finding the subsequent free block.
951: */
952:
953: if ((prev = st_pred (q, addr, bucket)) == addr)
954: return (_ST_ADDR_T) -3; /* not a valid block */
955:
956:
957: /*
958: * Now that we have performed some sanity checks, look to see how
959: * we should grow the block.
960: */
961:
962: /*
963: * Check the next rightmost block to see if we can grow into it.
964: * If we are shrinking the allocation, this is trivially true.
965: *
966: * To save ourselves a local, we re-use "bucket" here as the amount
967: * of free space in the next rightmost block. We need to keep this
968: * value for the next test so that we can expand both up and down
969: * if necessary.
970: */
971:
972: bucket = 0;
973: prev_reduce = 0;
974:
975: if ((next = _ST_HEAP_NEXT (addr, cntl)) < q->_arena_end &&
976: _ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, next)))
977: bucket = cntl; /* available adjacent words */
978:
979: if (bucket >= delta) {
980: /*
981: * Whether we are growing or shrinking, we have enough room.
982: * Set the block's new size, and skip to the common code below
983: * which adjusts the right edge of a block by "delta" words.
984: */
985:
986: ASSERT (next < q->_arena_end ||
987: (next == q->_arena_end && delta < 0));
988:
989: _ST_BLOCK_SET_USED (q, addr, newsize);
990:
991:
992: /*
993: * Go to the common exit sequence for in-place adjustment,
994: * after setting "prev" to be the base of the block that we
995: * will return to the user.
996: */
997:
998: prev = addr;
999:
1000: goto adjust_right;
1001: }
1002:
1003:
1004: /*
1005: * Check the next leftmost block to see if we should move down. Note
1006: * that we add in the free size of the right block to the calculation
1007: * so that we can expand both down and up to fill space.
1008: *
1009: * Given that we have to copy, however, we'll drop to the bottom of
1010: * the available room.
1011: */
1012:
1013: if (_ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, prev)) &&
1014: (cntl + bucket) >= delta) {
1015: /*
1016: * Well, we have enough space. Now, let's make "delta" equal
1017: * to the amount by which we need to adjust the block on
1018: * the right.
1019: */
1020:
1021: delta -= cntl;
1022:
1023:
1024: /*
1025: * We set the "prev" block as used now for st_reduced ().
1026: */
1027:
1028: _ST_BLOCK_SET_USED (q, prev, newsize);
1029:
1030:
1031: /*
1032: * Since we are vaporising the original block at "addr", we
1033: * should deal with checking to see if it was the first block
1034: * in it's bucket, otherwise we may wind up with a dangling
1035: * pointer. For now, we just point it to the successor to
1036: * "addr", and if this this does not turn out to be correct,
1037: * the common code to move the LHS below will do the right
1038: * thing.
1039: */
1040:
1041: if (_ST_HEAP_FIRST (q, (bucket = _ST_HEAP_BUCKET (q, addr)))
1042: == addr)
1043: _ST_HEAP_FIRST (q, bucket) = next;
1044:
1045: /*
1046: * If we want to move the block down, then we should update
1047: * the heap information related to the block we are moving
1048: * into before we move into it.
1049: *
1050: * Everything relating to what happens to the right edge of
1051: * the block will be dealt with below, so all we have to do
1052: * here is determine whether to call st_reduced ().
1053: *
1054: * We don't actually call st_reduced () here, since until the
1055: * left edge has been dealt with there can be a temporary
1056: * loss of block connectivity.
1057: */
1058:
1059: bucket = _ST_HEAP_BUCKET (q, prev);
1060:
1061: if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
1062: prev_reduce = 1;
1063:
1064: /*
1065: * Now, copy the original data from the block at "addr". How
1066: * much to copy? Re-fetch the block size from the control
1067: * word for now, although this may have to change to use
1068: * "oldsize" if this is changed to use a variant algorithm
1069: * where allocated blocks are not part of a list.
1070: *
1071: * How to perform the copy? Each target system will probably
1072: * have it's own routine for performing a word-aligned, word-
1073: * counted, upward-only high-speed block copy. Here, we
1074: * request the services of that routine, with a default
1075: * provided just prior to this code in case there is no
1076: * special facility for that purpose.
1077: *
1078: * Note that we perform the move now because there is no way
1079: * that the move can invalidate the block header (if any) in
1080: * the rightmost block. We know this because the size that we
1081: * are copying by is the size of the original block, and we
1082: * are moving down, so we can't write over anything after the
1083: * original block.
1084: */
1085:
1086: _ST_BLOCK_COPY (q, _ST_HEAP_NEXT (prev, _ST_AHDR_SIZE),
1087: _ST_HEAP_NEXT (addr, _ST_AHDR_SIZE),
1088: _ST_BLOCK_SIZE (_ST_BLOCK_CONTROL (q, addr)) - _ST_AHDR_SIZE);
1089:
1090: /*
1091: * Now, do the common part.
1092: */
1093:
1094: ASSERT (_ST_HEAP_NEXT (next, delta) ==
1095: _ST_HEAP_NEXT (prev, newsize));
1096:
1097: goto adjust_right;
1098: }
1099:
1100:
1101: /*
1102: * We have tried to move the block more-or-less in place, and the
1103: * some of the block and both neighbours does not yield enough space,
1104: * so we try and realloc () the naive way, using st_alloc () and
1105: * st_free (). We re-use these routines and just adjust for the fact
1106: * that they measure sizes in bytes rather than duplicating the code.
1107: *
1108: * Please note that the "prev" returned by st_alloc () has already
1109: * had the adjustment by 1 word to skip over the control block.
1110: */
1111:
1112:
1113: if ((prev = _ST_PTR2ADDR (q, st_alloc (q, _ST_WORD2BYTE (newsize))))
1114: == 0)
1115: return 0;
1116:
1117:
1118: /*
1119: * Do the block copy of the original contents and release them.
1120: * See the discussion above on the block copier.
1121: *
1122: * Note that we pass the address "a" into st_free (), as "addr" is
1123: * adjusted to point at the control word.
1124: */
1125:
1126: _ST_BLOCK_COPY (q, prev, _ST_HEAP_NEXT (addr, _ST_AHDR_SIZE),
1127: _ST_BLOCK_SIZE (_ST_BLOCK_CONTROL (q, addr)) - _ST_AHDR_SIZE);
1128:
1129: if (st_free (q, a ST_FREE_SIZE (oldsize)) != 0) {
1130: /*
1131: * What the duece! Throw the bums out on their ears!
1132: */
1133:
1134: ASSERT (1 == 0);
1135: }
1136:
1137:
1138: return _ST_ADDR2PTR (q, prev);
1139:
1140:
1141: /*
1142: * Perform the necessary adjustments to the index heap for the
1143: * event that is happening on the right-hand side of the original
1144: * block. The block boundary on the right is being moved by "delta"
1145: * words from it's *original* location, ie the block at "next" is
1146: * being either grown by -delta or shrunk by delta, or remaining
1147: * unaffected. If next is being shrunk, then we know at this point
1148: * that "next" is free. If it's being grown, then "next" could be
1149: * either free or allocated, so we may have to create a new block.
1150: */
1151:
1152: adjust_right:
1153:
1154: /*
1155: * Common case: fetch the current statistics of the "next" block and
1156: * set us up so that we point at the location of the new block.
1157: */
1158:
1159: if (next < q->_arena_end) {
1160:
1161: cntl = _ST_BLOCK_CONTROL (q, next);
1162: bucket = _ST_HEAP_BUCKET (q, next);
1163:
1164: /*
1165: * We record whether or not "next" has an _ST_HEAP_FIRST ()
1166: * pointer looking at it so we can update it below depending
1167: * on how we move things around.
1168: */
1169:
1170: next_first = _ST_HEAP_FIRST (q, bucket) == next;
1171: } else {
1172: /*
1173: * Treat the end of the world as an allocated block.
1174: */
1175:
1176: cntl = -1;
1177: next_first = bucket = 0;
1178: }
1179:
1180: next = _ST_HEAP_NEXT (next, delta);
1181: next_bucket = _ST_HEAP_BUCKET (q, next);
1182:
1183:
1184: if (delta > 0) { /* eat into "next", which is free */
1185: /*
1186: * If we need to, make the _ST_HEAP_FIRST () pointer track
1187: * the block. Note that there is no harm in this if "next"
1188: * actually lives a few buckets along, in fact it's required
1189: * that if there's no blocks in the bucket, _ST_HEAP_FIRST ()
1190: * must point beyond the end of the bucket.
1191: */
1192:
1193: if (next_first)
1194: _ST_HEAP_FIRST (q, bucket) = next;
1195:
1196: /*
1197: * Grow up into our neighbour. This case is basically
1198: * identical to the regular allocation algorithm except that
1199: * we don't have to reserve space for a new control word.
1200: *
1201: * The comments in st_alloc () also apply here, see above.
1202: *
1203: * Note that since we know that "next" is free, we also know
1204: * that "cntl" is a positive integer and doesn't need masking.
1205: */
1206:
1207: if (cntl > delta) {
1208: /*
1209: * Create a free block, which may cause a call to
1210: * st_grown () if it begins in another bucket. Like
1211: * st_alloc (), we call st_grown () whether or not
1212: * it needs to propagate size information up the
1213: * index heap, because we may require that the size
1214: * of the index heap be doubled as a side-effect of
1215: * the overflow into the next bucket.
1216: */
1217:
1218: _ST_BLOCK_SET_FREE (q, next, cntl - delta);
1219:
1220: if (next_bucket > bucket)
1221: st_grown (q, next, next_bucket);
1222: } else {
1223: /*
1224: * In this case, "next" has been completely eaten
1225: * up, so we just let the common code below deal with
1226: * shrinking the "biggest free".
1227: *
1228: * I make lots of gratuitous assertions, don't I?
1229: */
1230:
1231: ASSERT (cntl == delta);
1232: }
1233:
1234:
1235: /*
1236: * Regardless of whether we have created a new block, we
1237: * should see whether we should adjust the "largest free"
1238: * for the bucket, according to the usual rules.
1239: */
1240:
1241: if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
1242: st_reduced (q, bucket);
1243: } else if (delta < 0) { /* "-delta" free words below "next" */
1244: /*
1245: * This code is the inverse of the above, except that we
1246: * may not be affecting the actual "next" block if it is
1247: * in use.
1248: *
1249: * Note that in this scenario, "next_bucket" has the inverse
1250: * of the normal relation to "bucket", since it may be below
1251: * "bucket".
1252: */
1253:
1254: _ST_BLOCK_SET_FREE (q, next, (_ST_BLOCK_FREE (cntl) ? cntl : 0)
1255: - delta);
1256:
1257: if (next_bucket < bucket) {
1258:
1259: _ST_HEAP_FIRST (q, bucket) =
1260: _ST_HEAP_NEXT (next, _ST_BLOCK_CONTROL (q, next));
1261:
1262: /*
1263: * We don't want to call st_reduced () if the original
1264: * "next" block wasn't free. It won't hurt things,
1265: * but it wastes time. However, since "cntl" is
1266: * negative in that case, the test below will always
1267: * fail in that situation.
1268: */
1269:
1270: if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
1271: st_reduced (q, bucket);
1272: }
1273:
1274:
1275: if (_ST_BLOCK_CONTROL (q, next) > _ST_HEAP_BIGGEST (q, next_bucket + q->_buckets_inuse))
1276: st_grown (q, next, next_bucket);
1277: }
1278:
1279: if (prev_reduce != 0)
1280: st_reduced (q, _ST_HEAP_BUCKET (q, prev));
1281:
1282:
1283: return _ST_ADDR2PTR (q, _ST_HEAP_NEXT (prev, 1));
1284: }
1285:
1286:
1287: /*
1288: * Initialise an arena.
1289: */
1290:
1291: #if __USE_PROTO__
1292: void (st_init) (_ST_HEAP_CONTROL_P q)
1293: #else
1294: void
1295: st_init __ARGS ((q))
1296: _ST_HEAP_CONTROL_P q;
1297: #endif
1298: {
1299: q->_heap_error = NULL;
1300: q->_buckets_inuse = 1;
1301: q->_words_per_bucket = (q->_arena_size + q->_buckets_maximum - 1)
1302: / q->_buckets_maximum;
1303:
1304: _ST_HEAP_BIGGEST (q, 1) = q->_arena_size;
1305:
1306: _ST_HEAP_FIRST (q, 0) = q->_arena_base;
1307:
1308: _ST_BLOCK_SET_FREE (q, q->_arena_base, q->_arena_size);
1309:
1310: /*
1311: * Create dummy sentinel block.
1312: */
1313:
1314: st_alloc (q, 0);
1315:
1316: return;
1317: }
1318:
1319:
1320: /*
1321: * As above, but a full construction.
1322: */
1323:
1324: #if __USE_PROTO__
1325: void (st_ctor) (_ST_HEAP_CONTROL_P q, int segs, size_t arensize,
1326: _ST_ADDR_T arenabase)
1327: #else
1328: void
1329: st_ctor __ARGS ((q, segs, arensize, arenabase))
1330: _ST_HEAP_CONTROL_P q;
1331: int segs;
1332: size_t arensize;
1333: _ST_ADDR_T arenabase;
1334: #endif
1335: {
1336: q->_buckets_maximum = segs;
1337: q->_arena_size = arensize;
1338: q->_arena_base = (_ST_ADDR_T) arenabase;
1339: q->_arena_end = _ST_HEAP_NEXT (arenabase, arensize);
1340:
1341: q->_bucket_biggest = (_ST_WORD_T *) (q + 1);
1342: q->_bucket_first = (_ST_ADDR_T *) (q->_bucket_biggest + segs * 2);
1343:
1344: /*
1345: * Perform regular initialisation.
1346: */
1347:
1348: st_init (q);
1349: }
1350:
1351:
1352: /*
1353: * Return a size suitable for requesting the largest currently available
1354: * block of memory.
1355: *
1356: * Thanks to the way the index heap is constructed, this is in fact
1357: * trivially implementable.
1358: */
1359:
1360: #if __USE_PROTO__
1361: size_t (st_maxavail) (_ST_HEAP_CONTROL_P q)
1362: #else
1363: size_t
1364: st_maxavail __ARGS ((q))
1365: _ST_HEAP_CONTROL_P q;
1366: #endif
1367: {
1368: return _ST_WORD2BYTE (_ST_HEAP_BIGGEST (q, 0));
1369: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.