1 // Adapted for geekos: http://www.cs.umd.edu/~daveho/geekos/
2 // Original version of BGET downloaded from: http://www.fourmilab.ch/bget/
5 // GeekOS changes are (mostly) confined to #if defined (GEEKOS)
14 Designed and implemented in April of 1972 by John Walker, based on the
15 Case Algol OPRO$ algorithm implemented in 1966.
17 Reimplemented in 1975 by John Walker for the Interdata 70.
18 Reimplemented in 1977 by John Walker for the Marinchip 9900.
19 Reimplemented in 1982 by Duff Kurland for the Intel 8080.
21 Portable C version implemented in September of 1990 by an older, wiser
22 instance of the original implementor.
24 Souped up and/or weighed down slightly shortly thereafter by Greg
27 AMIX edition, including the new compaction call-back option, prepared
28 by John Walker in July of 1992.
30 Bug in built-in test program fixed, ANSI compiler warnings eradicated,
31 buffer pool validator implemented, and guaranteed repeatable test
32 added by John Walker in October of 1995.
34 This program is in the public domain.
36 1. This is the book of the generations of Adam. In the day that God
37 created man, in the likeness of God made he him;
38 2. Male and female created he them; and blessed them, and called
39 their name Adam, in the day when they were created.
40 3. And Adam lived an hundred and thirty years, and begat a son in
41 his own likeness, and after his image; and called his name Seth:
42 4. And the days of Adam after he had begotten Seth were eight
43 hundred years: and he begat sons and daughters:
44 5. And all the days that Adam lived were nine hundred and thirty
46 6. And Seth lived an hundred and five years, and begat Enos:
47 7. And Seth lived after he begat Enos eight hundred and seven years,
48 and begat sons and daughters:
49 8. And all the days of Seth were nine hundred and twelve years: and
51 9. And Enos lived ninety years, and begat Cainan:
52 10. And Enos lived after he begat Cainan eight hundred and fifteen
53 years, and begat sons and daughters:
54 11. And all the days of Enos were nine hundred and five years: and
56 12. And Cainan lived seventy years and begat Mahalaleel:
57 13. And Cainan lived after he begat Mahalaleel eight hundred and
58 forty years, and begat sons and daughters:
59 14. And all the days of Cainan were nine hundred and ten years: and
61 15. And Mahalaleel lived sixty and five years, and begat Jared:
62 16. And Mahalaleel lived after he begat Jared eight hundred and
63 thirty years, and begat sons and daughters:
64 17. And all the days of Mahalaleel were eight hundred ninety and
65 five years: and he died.
66 18. And Jared lived an hundred sixty and two years, and he begat
68 19. And Jared lived after he begat Enoch eight hundred years, and
69 begat sons and daughters:
70 20. And all the days of Jared were nine hundred sixty and two years:
72 21. And Enoch lived sixty and five years, and begat Methuselah:
73 22. And Enoch walked with God after he begat Methuselah three
74 hundred years, and begat sons and daughters:
75 23. And all the days of Enoch were three hundred sixty and five
77 24. And Enoch walked with God: and he was not; for God took him.
78 25. And Methuselah lived an hundred eighty and seven years, and
80 26. And Methuselah lived after he begat Lamech seven hundred eighty
81 and two years, and begat sons and daughters:
82 27. And all the days of Methuselah were nine hundred sixty and nine
84 28. And Lamech lived an hundred eighty and two years, and begat a
86 29. And he called his name Noah, saying, This same shall comfort us
87 concerning our work and toil of our hands, because of the ground
88 which the LORD hath cursed.
89 30. And Lamech lived after he begat Noah five hundred ninety and
90 five years, and begat sons and daughters:
91 31. And all the days of Lamech were seven hundred seventy and seven
93 32. And Noah was five hundred years old: and Noah begat Shem, Ham,
96 And buffers begat buffers, and links begat links, and buffer pools
97 begat links to chains of buffer pools containing buffers, and lo the
98 buffers and links and pools of buffers and pools of links to chains of
99 pools of buffers were fruitful and they multiplied and the Operating
100 System looked down upon them and said that it was Good.
106 BGET is a comprehensive memory allocation package which is easily
107 configured to the needs of an application. BGET is efficient in
108 both the time needed to allocate and release buffers and in the
109 memory overhead required for buffer pool management. It
110 automatically consolidates contiguous space to minimise
111 fragmentation. BGET is configured by compile-time definitions,
112 Major options include:
114 * A built-in test program to exercise BGET and
115 demonstrate how the various functions are used.
117 * Allocation by either the "first fit" or "best fit"
120 * Wiping buffers at release time to catch code which
121 references previously released storage.
123 * Built-in routines to dump individual buffers or the
126 * Retrieval of allocation and pool size statistics.
128 * Quantisation of buffer sizes to a power of two to
129 satisfy hardware alignment constraints.
131 * Automatic pool compaction, growth, and shrinkage by
132 means of call-backs to user defined functions.
134 Applications of BGET can range from storage management in
135 ROM-based embedded programs to providing the framework upon which
136 a multitasking system incorporating garbage collection is
137 constructed. BGET incorporates extensive internal consistency
138 checking using the <assert.h> mechanism; all these checks can be
139 turned off by compiling with NDEBUG defined, yielding a version of
140 BGET with minimal size and maximum speed.
142 The basic algorithm underlying BGET has withstood the test of
143 time; more than 25 years have passed since the first
144 implementation of this code. And yet, it is substantially more
145 efficient than the native allocation schemes of many operating
146 systems: the Macintosh and Microsoft Windows to name two, on which
147 programs have obtained substantial speed-ups by layering BGET as
148 an application level memory manager atop the underlying system's.
150 BGET has been implemented on the largest mainframes and the lowest
151 of microprocessors. It has served as the core for multitasking
152 operating systems, multi-thread applications, embedded software in
153 data network switching processors, and a host of C programs. And
154 while it has accreted flexibility and additional options over the
155 years, it remains fast, memory efficient, portable, and easy to
156 integrate into your program.
159 BGET IMPLEMENTATION ASSUMPTIONS
160 ===============================
162 BGET is written in as portable a dialect of C as possible. The
163 only fundamental assumption about the underlying hardware
164 architecture is that memory is allocated is a linear array which
165 can be addressed as a vector of C "char" objects. On segmented
166 address space architectures, this generally means that BGET should
167 be used to allocate storage within a single segment (although some
168 compilers simulate linear address spaces on segmented
169 architectures). On segmented architectures, then, BGET buffer
170 pools may not be larger than a segment, but since BGET allows any
171 number of separate buffer pools, there is no limit on the total
172 storage which can be managed, only on the largest individual
173 object which can be allocated. Machines with a linear address
174 architecture, such as the VAX, 680x0, Sparc, MIPS, or the Intel
175 80386 and above in native mode, may use BGET without restriction.
178 GETTING STARTED WITH BGET
179 =========================
181 Although BGET can be configured in a multitude of fashions, there
182 are three basic ways of working with BGET. The functions
183 mentioned below are documented in the following section. Please
184 excuse the forward references which are made in the interest of
185 providing a roadmap to guide you to the BGET functions you're
188 Embedded Applications
189 ---------------------
191 Embedded applications typically have a fixed area of memory
192 dedicated to buffer allocation (often in a separate RAM address
193 space distinct from the ROM that contains the executable code).
194 To use BGET in such an environment, simply call bpool() with the
195 start address and length of the buffer pool area in RAM, then
196 allocate buffers with bget() and release them with brel().
197 Embedded applications with very limited RAM but abundant CPU speed
198 may benefit by configuring BGET for BestFit allocation (which is
199 usually not worth it in other environments).
204 If the C library malloc() function is too slow, not present in
205 your development environment (for example, an a native Windows or
206 Macintosh program), or otherwise unsuitable, you can replace it
207 with BGET. Initially define a buffer pool of an appropriate size
208 with bpool()--usually obtained by making a call to the operating
209 system's low-level memory allocator. Then allocate buffers with
210 bget(), bgetz(), and bgetr() (the last two permit the allocation
211 of buffers initialised to zero and [inefficient] re-allocation of
212 existing buffers for compatibility with C library functions).
213 Release buffers by calling brel(). If a buffer allocation request
214 fails, obtain more storage from the underlying operating system,
215 add it to the buffer pool by another call to bpool(), and continue
218 Automatic Storage Management
219 ----------------------------
221 You can use BGET as your application's native memory manager and
222 implement automatic storage pool expansion, contraction, and
223 optionally application-specific memory compaction by compiling
224 BGET with the BECtl variable defined, then calling bectl() and
225 supplying functions for storage compaction, acquisition, and
226 release, as well as a standard pool expansion increment. All of
227 these functions are optional (although it doesn't make much sense
228 to provide a release function without an acquisition function,
229 does it?). Once the call-back functions have been defined with
230 bectl(), you simply use bget() and brel() to allocate and release
231 storage as before. You can supply an initial buffer pool with
232 bpool() or rely on automatic allocation to acquire the entire
233 pool. When a call on bget() cannot be satisfied, BGET first
234 checks if a compaction function has been supplied. If so, it is
235 called (with the space required to satisfy the allocation request
236 and a sequence number to allow the compaction routine to be called
237 successively without looping). If the compaction function is able
238 to free any storage (it needn't know whether the storage it freed
239 was adequate) it should return a nonzero value, whereupon BGET
240 will retry the allocation request and, if it fails again, call the
241 compaction function again with the next-higher sequence number.
243 If the compaction function returns zero, indicating failure to
244 free space, or no compaction function is defined, BGET next tests
245 whether a non-NULL allocation function was supplied to bectl().
246 If so, that function is called with an argument indicating how
247 many bytes of additional space are required. This will be the
248 standard pool expansion increment supplied in the call to bectl()
249 unless the original bget() call requested a buffer larger than
250 this; buffers larger than the standard pool block can be managed
251 "off the books" by BGET in this mode. If the allocation function
252 succeeds in obtaining the storage, it returns a pointer to the new
253 block and BGET expands the buffer pool; if it fails, the
254 allocation request fails and returns NULL to the caller. If a
255 non-NULL release function is supplied, expansion blocks which
256 become totally empty are released to the global free pool by
257 passing their addresses to the release function.
259 Equipped with appropriate allocation, release, and compaction
260 functions, BGET can be used as part of very sophisticated memory
261 management strategies, including garbage collection. (Note,
262 however, that BGET is *not* a garbage collector by itself, and
263 that developing such a system requires much additional logic and
264 careful design of the application's memory allocation strategy.)
267 BGET FUNCTION DESCRIPTIONS
268 ==========================
270 Functions implemented in this file (some are enabled by certain of
271 the optional settings below):
273 void bpool(void *buffer, bufsize len);
275 Create a buffer pool of <len> bytes, using the storage starting at
276 <buffer>. You can call bpool() subsequently to contribute
277 additional storage to the overall buffer pool.
279 void *bget(bufsize size);
281 Allocate a buffer of <size> bytes. The address of the buffer is
282 returned, or NULL if insufficient memory was available to allocate
285 void *bgetz(bufsize size);
287 Allocate a buffer of <size> bytes and clear it to all zeroes. The
288 address of the buffer is returned, or NULL if insufficient memory
289 was available to allocate the buffer.
291 void *bgetr(void *buffer, bufsize newsize);
293 Reallocate a buffer previously allocated by bget(), changing its
294 size to <newsize> and preserving all existing data. NULL is
295 returned if insufficient memory is available to reallocate the
296 buffer, in which case the original buffer remains intact.
298 void brel(void *buf);
300 Return the buffer <buf>, previously allocated by bget(), to the
303 void bectl(int (*compact)(bufsize sizereq, int sequence),
304 void *(*acquire)(bufsize size),
305 void (*release)(void *buf),
308 Expansion control: specify functions through which the package may
309 compact storage (or take other appropriate action) when an
310 allocation request fails, and optionally automatically acquire
311 storage for expansion blocks when necessary, and release such
312 blocks when they become empty. If <compact> is non-NULL, whenever
313 a buffer allocation request fails, the <compact> function will be
314 called with arguments specifying the number of bytes (total buffer
315 size, including header overhead) required to satisfy the
316 allocation request, and a sequence number indicating the number of
317 consecutive calls on <compact> attempting to satisfy this
318 allocation request. The sequence number is 1 for the first call
319 on <compact> for a given allocation request, and increments on
320 subsequent calls, permitting the <compact> function to take
321 increasingly dire measures in an attempt to free up storage. If
322 the <compact> function returns a nonzero value, the allocation
323 attempt is re-tried. If <compact> returns 0 (as it must if it
324 isn't able to release any space or add storage to the buffer
325 pool), the allocation request fails, which can trigger automatic
326 pool expansion if the <acquire> argument is non-NULL. At the time
327 the <compact> function is called, the state of the buffer
328 allocator is identical to that at the moment the allocation
329 request was made; consequently, the <compact> function may call
330 brel(), bpool(), bstats(), and/or directly manipulate the buffer
331 pool in any manner which would be valid were the application in
332 control. This does not, however, relieve the <compact> function
333 of the need to ensure that whatever actions it takes do not change
334 things underneath the application that made the allocation
335 request. For example, a <compact> function that released a buffer
336 in the process of being reallocated with bgetr() would lead to
337 disaster. Implementing a safe and effective <compact> mechanism
338 requires careful design of an application's memory architecture,
339 and cannot generally be easily retrofitted into existing code.
341 If <acquire> is non-NULL, that function will be called whenever an
342 allocation request fails. If the <acquire> function succeeds in
343 allocating the requested space and returns a pointer to the new
344 area, allocation will proceed using the expanded buffer pool. If
345 <acquire> cannot obtain the requested space, it should return NULL
346 and the entire allocation process will fail. <pool_incr>
347 specifies the normal expansion block size. Providing an <acquire>
348 function will cause subsequent bget() requests for buffers too
349 large to be managed in the linked-block scheme (in other words,
350 larger than <pool_incr> minus the buffer overhead) to be satisfied
351 directly by calls to the <acquire> function. Automatic release of
352 empty pool blocks will occur only if all pool blocks in the system
353 are the size given by <pool_incr>.
355 void bstats(bufsize *curalloc, bufsize *totfree,
356 bufsize *maxfree, long *nget, long *nrel);
358 The amount of space currently allocated is stored into the
359 variable pointed to by <curalloc>. The total free space (sum of
360 all free blocks in the pool) is stored into the variable pointed
361 to by <totfree>, and the size of the largest single block in the
362 free space pool is stored into the variable pointed to by
363 <maxfree>. The variables pointed to by <nget> and <nrel> are
364 filled, respectively, with the number of successful (non-NULL
365 return) bget() calls and the number of brel() calls.
367 void bstatse(bufsize *pool_incr, long *npool,
368 long *npget, long *nprel,
369 long *ndget, long *ndrel);
371 Extended statistics: The expansion block size will be stored into
372 the variable pointed to by <pool_incr>, or the negative thereof if
373 automatic expansion block releases are disabled. The number of
374 currently active pool blocks will be stored into the variable
375 pointed to by <npool>. The variables pointed to by <npget> and
376 <nprel> will be filled with, respectively, the number of expansion
377 block acquisitions and releases which have occurred. The
378 variables pointed to by <ndget> and <ndrel> will be filled with
379 the number of bget() and brel() calls, respectively, managed
380 through blocks directly allocated by the acquisition and release
383 void bufdump(void *buf);
385 The buffer pointed to by <buf> is dumped on standard output.
387 void bpoold(void *pool, int dumpalloc, int dumpfree);
389 All buffers in the buffer pool <pool>, previously initialised by a
390 call on bpool(), are listed in ascending memory address order. If
391 <dumpalloc> is nonzero, the contents of allocated buffers are
392 dumped; if <dumpfree> is nonzero, the contents of free blocks are
395 int bpoolv(void *pool);
397 The named buffer pool, previously initialised by a call on
398 bpool(), is validated for bad pointers, overwritten data, etc. If
399 compiled with NDEBUG not defined, any error generates an assertion
400 failure. Otherwise 1 is returned if the pool is valid, 0 if an
408 /*#define TestProg 20000*/ /* Generate built-in test program
409 if defined. The value specifies
410 how many buffer allocation attempts
411 the test program should make. */
413 #define SizeQuant 4 /* Buffer allocation size quantum:
414 all buffers allocated are a
415 multiple of this size. This
416 MUST be a power of two. */
418 /*#define BufDump 1*/ /* Define this symbol to enable the
419 bpoold() function which dumps the
420 buffers in a buffer pool. */
422 /*#define BufValid 1*/ /* Define this symbol to enable the
423 bpoolv() function for validating
426 /*#define DumpData 1*/ /* Define this symbol to enable the
427 bufdump() function which allows
428 dumping the contents of an allocated
431 /*#define BufStats 1*/ /* Define this symbol to enable the
432 bstats() function which calculates
433 the total free space in the buffer
434 pool, the largest available
435 buffer, and the total space
436 currently allocated. */
438 /*#define FreeWipe 1*/ /* Wipe free buffers to a guaranteed
439 pattern of garbage to trip up
440 miscreants who attempt to use
441 pointers into released buffers. */
443 #define BestFit 1 /* Use a best fit algorithm when
444 searching for space for an
445 allocation request. This uses
446 memory more efficiently, but
447 allocation will be much slower. */
449 /*#define BECtl 1*/ /* Define this symbol to enable the
450 bectl() function for automatic
451 pool space control. */
455 #include <geekos/string.h> // for memset()
457 // Provide an assert() macro
458 #include <geekos/kassert.h>
459 #define assert(exp) KASSERT(exp)
461 #else // define (GEEKOS)
466 #define NDEBUG /* Exits in asserts confuse lint */
467 /* LINTLIBRARY */ /* Don't complain about def, no ref */
468 extern char *sprintf(); /* Sun includes don't define sprintf */
474 #endif // defined (GEEKOS)
476 #ifdef BufDump /* BufDump implies DumpData */
486 /* Declare the interface, including the requested buffer size type,
489 #include <geekos/bget.h>
491 #define MemSize int /* Type for size arguments to memxxx()
492 functions such as memcmp(). */
497 struct bfhead *flink; /* Forward link */
498 struct bfhead *blink; /* Backward link */
501 /* Header in allocated and free buffers */
504 bufsize prevfree; /* Relative link back to previous
505 free buffer in memory or 0 if
506 previous buffer is allocated. */
507 bufsize bsize; /* Buffer size: positive if free,
508 negative if allocated. */
510 #define BH(p) ((struct bhead *) (p))
512 /* Header in directly allocated buffers (by acqfcn) */
515 bufsize tsize; /* Total size, including overhead */
516 struct bhead bh; /* Common header */
518 #define BDH(p) ((struct bdhead *) (p))
520 /* Header in free buffers */
523 struct bhead bh; /* Common allocated/free header */
524 struct qlinks ql; /* Links on free list */
526 #define BFH(p) ((struct bfhead *) (p))
528 static struct bfhead freelist; /* List of free buffers */
534 static bufsize totalloc = 0; /* Total space currently allocated */
535 static long numget = 0, numrel = 0; /* Number of bget() and brel() calls */
537 static long numpblk = 0; /* Number of pool blocks */
538 static long numpget = 0, numprel = 0; /* Number of block gets and rels */
539 static long numdget = 0, numdrel = 0; /* Number of direct gets and rels */
541 #endif /* BufStats */
545 /* Automatic expansion block management functions */
547 static int (*compfcn) _((bufsize sizereq, int sequence)) = NULL;
548 static void *(*acqfcn) _((bufsize size)) = NULL;
549 static void (*relfcn) _((void *buf)) = NULL;
551 static bufsize exp_incr = 0; /* Expansion block size */
552 static bufsize pool_len = 0; /* 0: no bpool calls have been made
553 -1: not all pool blocks are
555 >0: (common) block size for all
556 bpool calls made so far
560 /* Minimum allocation quantum: */
562 #define QLSize (sizeof(struct qlinks))
563 #define SizeQ ((SizeQuant > QLSize) ? SizeQuant : QLSize)
565 #define V (void) /* To denote unwanted returned values */
567 /* End sentinel: value placed in bsize field of dummy block delimiting
568 end of pool block. The most negative number which will fit in a
569 bufsize, defined in a way that the compiler will accept. */
571 #define ESent ((bufsize) (-(((1L << (sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))
573 /* BGET -- Allocate a buffer. */
575 void *bget(requested_size)
576 bufsize requested_size;
578 bufsize size = requested_size;
590 if (size < SizeQ) { /* Need at least room for the */
591 size = SizeQ; /* queue links. */
595 size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1));
599 size += sizeof(struct bhead); /* Add overhead in allocated buffer
603 /* If a compact function was provided in the call to bectl(), wrap
604 a loop around the allocation process to allow compaction to
605 intervene in case we don't find a suitable buffer in the chain. */
609 b = freelist.ql.flink;
615 /* Scan the free list searching for the first buffer big enough
616 to hold the requested size buffer. */
619 while (b != &freelist) {
620 if (b->bh.bsize >= size) {
621 if ((best == &freelist) || (b->bh.bsize < best->bh.bsize)) {
625 b = b->ql.flink; /* Link to next buffer */
630 while (b != &freelist) {
631 if ((bufsize) b->bh.bsize >= size) {
633 /* Buffer is big enough to satisfy the request. Allocate it
634 to the caller. We must decide whether the buffer is large
635 enough to split into the part given to the caller and a
636 free buffer that remains on the free list, or whether the
637 entire buffer should be removed from the free list and
638 given to the caller in its entirety. We only split the
639 buffer if enough room remains for a header plus the minimum
640 quantum of allocation. */
642 if ((b->bh.bsize - size) > (SizeQ + (sizeof(struct bhead)))) {
643 struct bhead *ba, *bn;
645 ba = BH(((char *) b) + (b->bh.bsize - size));
646 bn = BH(((char *) ba) + size);
647 assert(bn->prevfree == b->bh.bsize);
648 /* Subtract size from length of free block. */
650 /* Link allocated buffer to the previous free buffer. */
651 ba->prevfree = b->bh.bsize;
652 /* Plug negative size into user buffer. */
653 ba->bsize = -(bufsize) size;
654 /* Mark buffer after this one not preceded by free block. */
659 numget++; /* Increment number of bget() calls */
661 buf = (void *) ((((char *) ba) + sizeof(struct bhead)));
666 ba = BH(((char *) b) + b->bh.bsize);
667 assert(ba->prevfree == b->bh.bsize);
669 /* The buffer isn't big enough to split. Give the whole
670 shebang to the caller and remove it from the free list. */
672 assert(b->ql.blink->ql.flink == b);
673 assert(b->ql.flink->ql.blink == b);
674 b->ql.blink->ql.flink = b->ql.flink;
675 b->ql.flink->ql.blink = b->ql.blink;
678 totalloc += b->bh.bsize;
679 numget++; /* Increment number of bget() calls */
681 /* Negate size to mark buffer allocated. */
682 b->bh.bsize = -(b->bh.bsize);
684 /* Zero the back pointer in the next buffer in memory
685 to indicate that this buffer is allocated. */
688 /* Give user buffer starting at queue links. */
689 buf = (void *) &(b->ql);
693 b = b->ql.flink; /* Link to next buffer */
697 /* We failed to find a buffer. If there's a compact function
698 defined, notify it of the size requested. If it returns
699 true, try the allocation again. */
701 if ((compfcn == NULL) || (!(*compfcn)(size, ++compactseq))) {
706 /* No buffer available with requested size free. */
708 /* Don't give up yet -- look in the reserve supply. */
710 if (acqfcn != NULL) {
711 if (size > exp_incr - sizeof(struct bhead)) {
713 /* Request is too large to fit in a single expansion
714 block. Try to satisy it by a direct buffer acquisition. */
718 size += sizeof(struct bdhead) - sizeof(struct bhead);
719 if ((bdh = BDH((*acqfcn)((bufsize) size))) != NULL) {
721 /* Mark the buffer special by setting the size field
722 of its header to zero. */
724 bdh->bh.prevfree = 0;
728 numget++; /* Increment number of bget() calls */
729 numdget++; /* Direct bget() call count */
731 buf = (void *) (bdh + 1);
737 /* Try to obtain a new expansion block */
741 if ((newpool = (*acqfcn)((bufsize) exp_incr)) != NULL) {
742 bpool(newpool, exp_incr);
743 buf = bget(requested_size); /* This can't, I say, can't
750 /* Still no buffer available */
757 /* BGETZ -- Allocate a buffer and clear its contents to zero. We clear
758 the entire contents of the buffer to zero, not just the
759 region requested by the caller. */
764 char *buf = (char *) bget(size);
770 b = BH(buf - sizeof(struct bhead));
775 bd = BDH(buf - sizeof(struct bdhead));
776 rsize = bd->tsize - sizeof(struct bdhead);
778 rsize -= sizeof(struct bhead);
780 assert(rsize >= size);
781 V memset(buf, 0, (MemSize) rsize);
783 return ((void *) buf);
786 /* BGETR -- Reallocate a buffer. This is a minimal implementation,
787 simply in terms of brel() and bget(). It could be
788 enhanced to allow the buffer to grow into adjacent free
789 blocks and to avoid moving data unnecessarily. */
791 void *bgetr(buf, size)
796 bufsize osize; /* Old size of buffer */
799 if ((nbuf = bget(size)) == NULL) { /* Acquire new buffer */
805 b = BH(((char *) buf) - sizeof(struct bhead));
809 /* Buffer acquired directly through acqfcn. */
812 bd = BDH(((char *) buf) - sizeof(struct bdhead));
813 osize = bd->tsize - sizeof(struct bdhead);
816 osize -= sizeof(struct bhead);
818 V memcpy((char *) nbuf, (char *) buf, /* Copy the data */
819 (MemSize) ((size < osize) ? size : osize));
824 /* BREL -- Release a buffer. */
829 struct bfhead *b, *bn;
831 b = BFH(((char *) buf) - sizeof(struct bhead));
833 numrel++; /* Increment number of brel() calls */
838 if (b->bh.bsize == 0) { /* Directly-acquired buffer? */
841 bdh = BDH(((char *) buf) - sizeof(struct bdhead));
842 assert(b->bh.prevfree == 0);
844 totalloc -= bdh->tsize;
845 assert(totalloc >= 0);
846 numdrel++; /* Number of direct releases */
847 #endif /* BufStats */
849 V memset((char *) buf, 0x55,
850 (MemSize) (bdh->tsize - sizeof(struct bdhead)));
851 #endif /* FreeWipe */
852 assert(relfcn != NULL);
853 (*relfcn)((void *) bdh); /* Release it directly. */
858 /* Buffer size must be negative, indicating that the buffer is
861 if (b->bh.bsize >= 0) {
864 assert(b->bh.bsize < 0);
866 /* Back pointer in next buffer must be zero, indicating the
869 assert(BH((char *) b - b->bh.bsize)->prevfree == 0);
872 totalloc += b->bh.bsize;
873 assert(totalloc >= 0);
876 /* If the back link is nonzero, the previous buffer is free. */
878 if (b->bh.prevfree != 0) {
880 /* The previous buffer is free. Consolidate this buffer with it
881 by adding the length of this buffer to the previous free
882 buffer. Note that we subtract the size in the buffer being
883 released, since it's negative to indicate that the buffer is
886 register bufsize size = b->bh.bsize;
888 /* Make the previous buffer the one we're working on. */
889 assert(BH((char *) b - b->bh.prevfree)->bsize == b->bh.prevfree);
890 b = BFH(((char *) b) - b->bh.prevfree);
894 /* The previous buffer isn't allocated. Insert this buffer
895 on the free list as an isolated free block. */
897 assert(freelist.ql.blink->ql.flink == &freelist);
898 assert(freelist.ql.flink->ql.blink == &freelist);
899 b->ql.flink = &freelist;
900 b->ql.blink = freelist.ql.blink;
901 freelist.ql.blink = b;
902 b->ql.blink->ql.flink = b;
903 b->bh.bsize = -b->bh.bsize;
906 /* Now we look at the next buffer in memory, located by advancing from
907 the start of this buffer by its size, to see if that buffer is
908 free. If it is, we combine this buffer with the next one in
909 memory, dechaining the second buffer from the free list. */
911 bn = BFH(((char *) b) + b->bh.bsize);
912 if (bn->bh.bsize > 0) {
914 /* The buffer is free. Remove it from the free list and add
915 its size to that of our buffer. */
917 assert(BH((char *) bn + bn->bh.bsize)->prevfree == bn->bh.bsize);
918 assert(bn->ql.blink->ql.flink == bn);
919 assert(bn->ql.flink->ql.blink == bn);
920 bn->ql.blink->ql.flink = bn->ql.flink;
921 bn->ql.flink->ql.blink = bn->ql.blink;
922 b->bh.bsize += bn->bh.bsize;
924 /* Finally, advance to the buffer that follows the newly
925 consolidated free block. We must set its backpointer to the
926 head of the consolidated free block. We know the next block
927 must be an allocated block because the process of recombination
928 guarantees that two free blocks will never be contiguous in
931 bn = BFH(((char *) b) + b->bh.bsize);
934 V memset(((char *) b) + sizeof(struct bfhead), 0x55,
935 (MemSize) (b->bh.bsize - sizeof(struct bfhead)));
937 assert(bn->bh.bsize < 0);
939 /* The next buffer is allocated. Set the backpointer in it to point
940 to this buffer; the previous free buffer in memory. */
942 bn->bh.prevfree = b->bh.bsize;
946 /* If a block-release function is defined, and this free buffer
947 constitutes the entire block, release it. Note that pool_len
948 is defined in such a way that the test will fail unless all
949 pool blocks are the same size. */
951 if (relfcn != NULL &&
952 ((bufsize) b->bh.bsize) == (pool_len - sizeof(struct bhead))) {
954 assert(b->bh.prevfree == 0);
955 assert(BH((char *) b + b->bh.bsize)->bsize == ESent);
956 assert(BH((char *) b + b->bh.bsize)->prevfree == b->bh.bsize);
957 /* Unlink the buffer from the free list */
958 b->ql.blink->ql.flink = b->ql.flink;
959 b->ql.flink->ql.blink = b->ql.blink;
963 numprel++; /* Nr of expansion block releases */
964 numpblk--; /* Total number of blocks */
965 assert(numpblk == numpget - numprel);
966 #endif /* BufStats */
973 /* BECTL -- Establish automatic pool expansion control */
975 void bectl(compact, acquire, release, pool_incr)
976 int (*compact) _((bufsize sizereq, int sequence));
977 void *(*acquire) _((bufsize size));
978 void (*release) _((void *buf));
984 exp_incr = pool_incr;
988 /* BPOOL -- Add a region of memory to the buffer pool. */
994 struct bfhead *b = BFH(buf);
998 len &= ~(SizeQuant - 1);
1001 if (pool_len == 0) {
1003 } else if (len != pool_len) {
1007 numpget++; /* Number of block acquisitions */
1008 numpblk++; /* Number of blocks total */
1009 assert(numpblk == numpget - numprel);
1010 #endif /* BufStats */
1013 /* Since the block is initially occupied by a single free buffer,
1014 it had better not be (much) larger than the largest buffer
1015 whose size we can store in bhead.bsize. */
1017 assert(len - sizeof(struct bhead) <= -((bufsize) ESent + 1));
1019 /* Initialize Free list since compile time static initializations appear to be broken */
1020 freelist.bh.prevfree = 0;
1021 freelist.bh.bsize = 0;
1022 freelist.ql.flink = &freelist;
1023 freelist.ql.blink = &freelist;
1027 /* Clear the backpointer at the start of the block to indicate that
1028 there is no free block prior to this one. That blocks
1029 recombination when the first block in memory is released. */
1033 /* Chain the new block to the free list. */
1035 assert(freelist.ql.blink->ql.flink == &freelist);
1036 assert(freelist.ql.flink->ql.blink == &freelist);
1037 b->ql.flink = &freelist;
1038 b->ql.blink = freelist.ql.blink;
1039 freelist.ql.blink = b;
1040 b->ql.blink->ql.flink = b;
1042 /* Create a dummy allocated buffer at the end of the pool. This dummy
1043 buffer is seen when a buffer at the end of the pool is released and
1044 blocks recombination of the last buffer with the dummy buffer at
1045 the end. The length in the dummy buffer is set to the largest
1046 negative number to denote the end of the pool for diagnostic
1047 routines (this specific value is not counted on by the actual
1048 allocation and release functions). */
1050 len -= sizeof(struct bhead);
1051 b->bh.bsize = (bufsize) len;
1053 V memset(((char *) b) + sizeof(struct bfhead), 0x55,
1054 (MemSize) (len - sizeof(struct bfhead)));
1056 bn = BH(((char *) b) + len);
1057 bn->prevfree = (bufsize) len;
1058 /* Definition of ESent assumes two's complement! */
1065 /* BSTATS -- Return buffer allocation free space statistics. */
1067 void bstats(curalloc, totfree, maxfree, nget, nrel)
1068 bufsize *curalloc, *totfree, *maxfree;
1071 struct bfhead *b = freelist.ql.flink;
1075 *curalloc = totalloc;
1078 while (b != &freelist) {
1079 assert(b->bh.bsize > 0);
1080 *totfree += b->bh.bsize;
1081 if (b->bh.bsize > *maxfree) {
1082 *maxfree = b->bh.bsize;
1084 b = b->ql.flink; /* Link to next buffer */
1090 /* BSTATSE -- Return extended statistics */
1092 void bstatse(pool_incr, npool, npget, nprel, ndget, ndrel)
1094 long *npool, *npget, *nprel, *ndget, *ndrel;
1096 *pool_incr = (pool_len < 0) ? -exp_incr : exp_incr;
1104 #endif /* BufStats */
1108 /* BUFDUMP -- Dump the data in a buffer. This is called with the user
1109 data pointer, and backs up to the buffer header. It will
1110 dump either a free block or an allocated one. */
1119 b = BFH(((char *) buf) - sizeof(struct bhead));
1120 assert(b->bh.bsize != 0);
1121 if (b->bh.bsize < 0) {
1122 bdump = (uchar_t *) buf;
1123 bdlen = (-b->bh.bsize) - sizeof(struct bhead);
1125 bdump = (uchar_t *) (((char *) b) + sizeof(struct bfhead));
1126 bdlen = b->bh.bsize - sizeof(struct bfhead);
1132 char bhex[50], bascii[20];
1138 for (i = 0; i < l; i++) {
1139 V sprintf(bhex + i * 3, "%02X ", bdump[i]);
1140 bascii[i] = isprint(bdump[i]) ? bdump[i] : ' ';
1143 V printf("%-48s %s\n", bhex, bascii);
1146 while ((bdlen > 16) && (memcmp((char *) (bdump - 16),
1147 (char *) bdump, 16) == 0)) {
1154 " (%d lines [%d bytes] identical to above line skipped)\n",
1156 } else if (dupes == 1) {
1166 /* BPOOLD -- Dump a buffer pool. The buffer headers are always listed.
1167 If DUMPALLOC is nonzero, the contents of allocated buffers
1168 are dumped. If DUMPFREE is nonzero, free blocks are
1169 dumped as well. If FreeWipe checking is enabled, free
1170 blocks which have been clobbered will always be dumped. */
1172 void bpoold(buf, dumpalloc, dumpfree)
1174 int dumpalloc, dumpfree;
1176 struct bfhead *b = BFH(buf);
1178 while (b->bh.bsize != ESent) {
1179 bufsize bs = b->bh.bsize;
1183 V printf("Allocated buffer: size %6ld bytes.\n", (long) bs);
1185 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1191 if ((b->ql.blink->ql.flink != b) ||
1192 (b->ql.flink->ql.blink != b)) {
1193 lerr = " (Bad free list links)";
1195 V printf("Free block: size %6ld bytes.%s\n",
1198 lerr = ((char *) b) + sizeof(struct bfhead);
1199 if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1200 (memcmp(lerr, lerr + 1,
1201 (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1203 "(Contents of above free block have been overstored.)\n");
1204 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1208 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1211 b = BFH(((char *) b) + bs);
1214 #endif /* BufDump */
1218 /* BPOOLV -- Validate a buffer pool. If NDEBUG isn't defined,
1219 any error generates an assertion failure. */
1224 struct bfhead *b = BFH(buf);
1226 while (b->bh.bsize != ESent) {
1227 bufsize bs = b->bh.bsize;
1238 if ((b->ql.blink->ql.flink != b) ||
1239 (b->ql.flink->ql.blink != b)) {
1240 V printf("Free block: size %6ld bytes. (Bad free list links)\n",
1246 lerr = ((char *) b) + sizeof(struct bfhead);
1247 if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1248 (memcmp(lerr, lerr + 1,
1249 (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1251 "(Contents of above free block have been overstored.)\n");
1252 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1258 b = BFH(((char *) b) + bs);
1262 #endif /* BufValid */
1264 /***********************\
1266 * Built-in test program *
1268 \***********************/
1272 #define Repeatable 1 /* Repeatable pseudorandom sequence */
1273 /* If Repeatable is not defined, a
1274 time-seeded pseudorandom sequence
1275 is generated, exercising BGET with
1276 a different pattern of calls on each
1278 #define OUR_RAND /* Use our own built-in version of
1279 rand() to guarantee the test is
1283 #define PoolSize 300000 /* Test buffer pool size */
1285 #define PoolSize 50000 /* Test buffer pool size */
1287 #define ExpIncr 32768 /* Test expansion block size */
1288 #define CompactTries 10 /* Maximum tries at compacting */
1290 #define dumpAlloc 0 /* Dump allocated buffers ? */
1291 #define dumpFree 0 /* Dump free buffers ? */
1297 extern char *malloc();
1298 extern int free _((char *));
1300 static char *bchain = NULL; /* Our private buffer chain */
1301 static char *bp = NULL; /* Our initial buffer pool */
1307 static ulong_t int next = 1;
1309 /* Return next random integer */
1313 next = next * 1103515245L + 12345;
1314 return (uint_t) (next / 65536L) % 32768L;
1317 /* Set seed for random generator */
1326 /* STATS -- Edit statistics returned by bstats() or bstatse(). */
1328 static void stats(when)
1331 bufsize cural, totfree, maxfree;
1335 long totblocks, npget, nprel, ndget, ndrel;
1338 bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1340 "%s: %ld gets, %ld releases. %ld in use, %ld free, largest = %ld\n",
1341 when, nget, nfree, (long) cural, (long) totfree, (long) maxfree);
1343 bstatse(&pincr, &totblocks, &npget, &nprel, &ndget, &ndrel);
1345 " Blocks: size = %ld, %ld (%ld bytes) in use, %ld gets, %ld frees\n",
1346 (long)pincr, totblocks, pincr * totblocks, npget, nprel);
1347 V printf(" %ld direct gets, %ld direct frees\n", ndget, ndrel);
1352 static int protect = 0; /* Disable compaction during bgetr() */
1354 /* BCOMPACT -- Compaction call-back function. */
1356 static int bcompact(bsize, seq)
1362 int i = rand() & 0x3;
1365 V printf("Compaction requested. %ld bytes needed, sequence %d.\n",
1369 if (protect || (seq > CompactTries)) {
1371 V printf("Compaction gave up.\n");
1376 /* Based on a random cast, release a random buffer in the list
1377 of allocated buffers. */
1379 while (i > 0 && bc != NULL) {
1380 bc = *((char **) bc);
1386 fb = *((char **) bc);
1388 *((char **) bc) = *((char **) fb);
1395 V printf("Compaction bailed out.\n");
1397 #endif /* CompactTries */
1401 /* BEXPAND -- Expand pool call-back function. */
1403 static void *bexpand(size)
1407 bufsize cural, totfree, maxfree;
1410 /* Don't expand beyond the total allocated size given by PoolSize. */
1412 bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1414 if (cural < PoolSize) {
1415 np = (void *) malloc((unsigned) size);
1418 V printf("Expand pool by %ld -- %s.\n", (long) size,
1419 np == NULL ? "failed" : "succeeded");
1424 /* BSHRINK -- Shrink buffer pool call-back function. */
1426 static void bshrink(buf)
1429 if (((char *) buf) == bp) {
1431 V printf("Initial pool released.\n");
1436 V printf("Shrink pool.\n");
1443 /* Restrict buffer requests to those large enough to contain our pointer and
1444 small enough for the CPU architecture. */
1446 static bufsize blimit(bs)
1449 if (bs < sizeof(char *)) {
1450 bs = sizeof(char *);
1453 /* This is written out in this ugly fashion because the
1454 cool expression in sizeof(int) that auto-configured
1455 to any length int befuddled some compilers. */
1457 if (sizeof(int) == 2) {
1474 /* Seed the random number generator. If Repeatable is defined, we
1475 always use the same seed. Otherwise, we seed from the clock to
1476 shake things up from run to run. */
1481 V srand((int) time((long *) NULL));
1484 /* Compute x such that pow(x, p) ranges between 1 and 4*ExpIncr as
1485 p ranges from 0 to ExpIncr-1, with a concentration in the lower
1490 x = exp(log(4.0 * ExpIncr) / (ExpIncr - 1.0));
1493 bectl(bcompact, bexpand, bshrink, (bufsize) ExpIncr);
1494 bp = malloc(ExpIncr);
1496 bpool((void *) bp, (bufsize) ExpIncr);
1498 bp = malloc(PoolSize);
1500 bpool((void *) bp, (bufsize) PoolSize);
1503 stats("Create pool");
1504 V bpoolv((void *) bp);
1505 bpoold((void *) bp, dumpAlloc, dumpFree);
1507 for (i = 0; i < TestProg; i++) {
1509 bufsize bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1511 assert(bs <= (((bufsize) 4) * ExpIncr));
1513 if (rand() & 0x400) {
1514 cb = (char *) bgetz(bs);
1516 cb = (char *) bget(bs);
1527 fb = *((char **) bc);
1529 *((char **) bc) = *((char **) fb);
1536 *((char **) cb) = (char *) bchain;
1539 /* Based on a random cast, release a random buffer in the list
1540 of allocated buffers. */
1542 if ((rand() & 0x10) == 0) {
1544 int i = rand() & 0x3;
1546 while (i > 0 && bc != NULL) {
1547 bc = *((char **) bc);
1553 fb = *((char **) bc);
1555 *((char **) bc) = *((char **) fb);
1561 /* Based on a random cast, reallocate a random buffer in the list
1564 if ((rand() & 0x20) == 0) {
1566 int i = rand() & 0x3;
1568 while (i > 0 && bc != NULL) {
1569 bc = *((char **) bc);
1575 fb = *((char **) bc);
1579 bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1582 protect = 1; /* Protect against compaction */
1584 newb = (char *) bgetr((void *) fb, bs);
1589 *((char **) bc) = newb;
1595 stats("\nAfter allocation");
1597 V bpoolv((void *) bp);
1598 bpoold((void *) bp, dumpAlloc, dumpFree);
1601 while (bchain != NULL) {
1604 bchain = *((char **) buf);
1607 stats("\nAfter release");
1610 V bpoolv((void *) bp);
1611 bpoold((void *) bp, dumpAlloc, dumpFree);