| |
| BGET -- Memory Allocator |
| ========================== |
| |
| by John Walker |
| http://www.fourmilab.ch/ |
| |
| BGET is a comprehensive memory allocation package which is easily |
| configured to the needs of an application. BGET is efficient in both |
| the time needed to allocate and release buffers and in the memory |
| overhead required for buffer pool management. It automatically |
| consolidates contiguous space to minimise fragmentation. BGET is |
| configured by compile-time definitions, Major options include: |
| |
| * A built-in test program to exercise BGET and |
| demonstrate how the various functions are used. |
| |
| * Allocation by either the "first fit" or "best fit" |
| method. |
| |
| * Wiping buffers at release time to catch code which |
| references previously released storage. |
| |
| * Built-in routines to dump individual buffers or the |
| entire buffer pool. |
| |
| * Retrieval of allocation and pool size statistics. |
| |
| * Quantisation of buffer sizes to a power of two to |
| satisfy hardware alignment constraints. |
| |
| * Automatic pool compaction, growth, and shrinkage by |
| means of call-backs to user defined functions. |
| |
| Applications of BGET can range from storage management in ROM-based |
| embedded programs to providing the framework upon which a multitasking |
| system incorporating garbage collection is constructed. BGET |
| incorporates extensive internal consistency checking using the |
| <assert.h> mechanism; all these checks can be turned off by compiling |
| with NDEBUG defined, yielding a version of BGET with minimal size and |
| maximum speed. |
| |
| The basic algorithm underlying BGET has withstood the test of time; more |
| than 25 years have passed since the first implementation of this code. |
| And yet, it is substantially more efficient than the native allocation |
| schemes of many operating systems: the Macintosh and Microsoft Windows |
| to name two, on which programs have obtained substantial speed-ups by |
| layering BGET as an application level memory manager atop the underlying |
| system's. |
| |
| BGET has been implemented on the largest mainframes and the lowest of |
| microprocessors. It has served as the core for multitasking operating |
| systems, multi-thread applications, embedded software in data network |
| switching processors, and a host of C programs. And while it has |
| accreted flexibility and additional options over the years, it remains |
| fast, memory efficient, portable, and easy to integrate into your |
| program. |
| |
| |
| BGET IMPLEMENTATION ASSUMPTIONS |
| =============================== |
| |
| BGET is written in as portable a dialect of C as possible. The only |
| fundamental assumption about the underlying hardware architecture is |
| that memory is allocated is a linear array which can be addressed as a |
| vector of C "char" objects. On segmented address space architectures, |
| this generally means that BGET should be used to allocate storage within |
| a single segment (although some compilers simulate linear address spaces |
| on segmented architectures). On segmented architectures, then, BGET |
| buffer pools may not be larger than a segment, but since BGET allows any |
| number of separate buffer pools, there is no limit on the total storage |
| which can be managed, only on the largest individual object which can be |
| allocated. Machines with a linear address architecture, such as the |
| VAX, 680x0, Sparc, MIPS, or the Intel 80386 and above in native mode, |
| may use BGET without restriction. |
| |
| |
| GETTING STARTED WITH BGET |
| ========================= |
| |
| Although BGET can be configured in a multitude of fashions, there are |
| three basic ways of working with BGET. The functions mentioned below |
| are documented in the following section. Please excuse the forward |
| references which are made in the interest of providing a roadmap to |
| guide you to the BGET functions you're likely to need. |
| |
| Embedded Applications |
| --------------------- |
| |
| Embedded applications typically have a fixed area of memory dedicated to |
| buffer allocation (often in a separate RAM address space distinct from |
| the ROM that contains the executable code). To use BGET in such an |
| environment, simply call bpool() with the start address and length of |
| the buffer pool area in RAM, then allocate buffers with bget() and |
| release them with brel(). Embedded applications with very limited RAM |
| but abundant CPU speed may benefit by configuring BGET for BestFit |
| allocation (which is usually not worth it in other environments). |
| |
| Malloc() Emulation |
| ------------------ |
| |
| If the C library malloc() function is too slow, not present in your |
| development environment (for example, an a native Windows or Macintosh |
| program), or otherwise unsuitable, you can replace it with BGET. |
| Initially define a buffer pool of an appropriate size with |
| bpool()--usually obtained by making a call to the operating system's |
| low-level memory allocator. Then allocate buffers with bget(), bgetz(), |
| and bgetr() (the last two permit the allocation of buffers initialised |
| to zero and [inefficient] re-allocation of existing buffers for |
| compatibility with C library functions). Release buffers by calling |
| brel(). If a buffer allocation request fails, obtain more storage from |
| the underlying operating system, add it to the buffer pool by another |
| call to bpool(), and continue execution. |
| |
| Automatic Storage Management |
| ---------------------------- |
| |
| You can use BGET as your application's native memory manager and |
| implement automatic storage pool expansion, contraction, and optionally |
| application-specific memory compaction by compiling BGET with the BECtl |
| variable defined, then calling bectl() and supplying functions for |
| storage compaction, acquisition, and release, as well as a standard pool |
| expansion increment. All of these functions are optional (although it |
| doesn't make much sense to provide a release function without an |
| acquisition function, does it?). Once the call-back functions have been |
| defined with bectl(), you simply use bget() and brel() to allocate and |
| release storage as before. You can supply an initial buffer pool with |
| bpool() or rely on automatic allocation to acquire the entire pool. |
| When a call on bget() cannot be satisfied, BGET first checks if a |
| compaction function has been supplied. If so, it is called (with the |
| space required to satisfy the allocation request and a sequence number |
| to allow the compaction routine to be called successively without |
| looping). If the compaction function is able to free any storage (it |
| needn't know whether the storage it freed was adequate) it should return |
| a nonzero value, whereupon BGET will retry the allocation request and, |
| if it fails again, call the compaction function again with the |
| next-higher sequence number. |
| |
| If the compaction function returns zero, indicating failure to free |
| space, or no compaction function is defined, BGET next tests whether a |
| non-NULL allocation function was supplied to bectl(). If so, that |
| function is called with an argument indicating how many bytes of |
| additional space are required. This will be the standard pool expansion |
| increment supplied in the call to bectl() unless the original bget() |
| call requested a buffer larger than this; buffers larger than the |
| standard pool block can be managed "off the books" by BGET in this mode. |
| If the allocation function succeeds in obtaining the storage, it returns |
| a pointer to the new block and BGET expands the buffer pool; if it |
| fails, the allocation request fails and returns NULL to the caller. If |
| a non-NULL release function is supplied, expansion blocks which become |
| totally empty are released to the global free pool by passing their |
| addresses to the release function. |
| |
| Equipped with appropriate allocation, release, and compaction functions, |
| BGET can be used as part of very sophisticated memory management |
| strategies, including garbage collection. (Note, however, that BGET is |
| *not* a garbage collector by itself, and that developing such a system |
| requires much additional logic and careful design of the application's |
| memory allocation strategy.) |
| |
| |
| BGET FUNCTION DESCRIPTIONS |
| ========================== |
| |
| Functions implemented by BGET (some are enabled by certain of the |
| optional settings below): |
| |
| void bpool(void *buffer, bufsize len); |
| |
| Create a buffer pool of <len> bytes, using the storage starting at |
| <buffer>. You can call bpool() subsequently to contribute additional |
| storage to the overall buffer pool. |
| |
| void *bget(bufsize size); |
| |
| Allocate a buffer of <size> bytes. The address of the buffer is |
| returned, or NULL if insufficient memory was available to allocate the |
| buffer. |
| |
| void *bgetz(bufsize size); |
| |
| Allocate a buffer of <size> bytes and clear it to all zeroes. The |
| address of the buffer is returned, or NULL if insufficient memory was |
| available to allocate the buffer. |
| |
| void *bgetr(void *buffer, bufsize newsize); |
| |
| Reallocate a buffer previously allocated by bget(), changing its size to |
| <newsize> and preserving all existing data. NULL is returned if |
| insufficient memory is available to reallocate the buffer, in which case |
| the original buffer remains intact. |
| |
| void brel(void *buf); |
| |
| Return the buffer <buf>, previously allocated by bget(), to the free |
| space pool. |
| |
| void bectl(int (*compact)(bufsize sizereq, int sequence), |
| void *(*acquire)(bufsize size), |
| void (*release)(void *buf), |
| bufsize pool_incr); |
| |
| Expansion control: specify functions through which the package may |
| compact storage (or take other appropriate action) when an allocation |
| request fails, and optionally automatically acquire storage for |
| expansion blocks when necessary, and release such blocks when they |
| become empty. If <compact> is non-NULL, whenever a buffer allocation |
| request fails, the <compact> function will be called with arguments |
| specifying the number of bytes (total buffer size, including header |
| overhead) required to satisfy the allocation request, and a sequence |
| number indicating the number of consecutive calls on <compact> |
| attempting to satisfy this allocation request. The sequence number is 1 |
| for the first call on <compact> for a given allocation request, and |
| increments on subsequent calls, permitting the <compact> function to |
| take increasingly dire measures in an attempt to free up storage. If |
| the <compact> function returns a nonzero value, the allocation attempt |
| is re-tried. If <compact> returns 0 (as it must if it isn't able to |
| release any space or add storage to the buffer pool), the allocation |
| request fails, which can trigger automatic pool expansion if the |
| <acquire> argument is non-NULL. At the time the <compact> function is |
| called, the state of the buffer allocator is identical to that at the |
| moment the allocation request was made; consequently, the <compact> |
| function may call brel(), bpool(), bstats(), and/or directly manipulate |
| the buffer pool in any manner which would be valid were the application |
| in control. This does not, however, relieve the <compact> function of |
| the need to ensure that whatever actions it takes do not change things |
| underneath the application that made the allocation request. For |
| example, a <compact> function that released a buffer in the process of |
| being reallocated with bgetr() would lead to disaster. Implementing a |
| safe and effective <compact> mechanism requires careful design of an |
| application's memory architecture, and cannot generally be easily |
| retrofitted into existing code. |
| |
| If <acquire> is non-NULL, that function will be called whenever an |
| allocation request fails. If the <acquire> function succeeds in |
| allocating the requested space and returns a pointer to the new area, |
| allocation will proceed using the expanded buffer pool. If <acquire> |
| cannot obtain the requested space, it should return NULL and the entire |
| allocation process will fail. <pool_incr> specifies the normal |
| expansion block size. Providing an <acquire> function will cause |
| subsequent bget() requests for buffers too large to be managed in the |
| linked-block scheme (in other words, larger than <pool_incr> minus the |
| buffer overhead) to be satisfied directly by calls to the <acquire> |
| function. Automatic release of empty pool blocks will occur only if all |
| pool blocks in the system are the size given by <pool_incr>. |
| |
| void bstats(bufsize *curalloc, bufsize *totfree, |
| bufsize *maxfree, long *nget, long *nrel); |
| |
| The amount of space currently allocated is stored into the variable |
| pointed to by <curalloc>. The total free space (sum of all free blocks |
| in the pool) is stored into the variable pointed to by <totfree>, and |
| the size of the largest single block in the free space pool is stored |
| into the variable pointed to by <maxfree>. The variables pointed to by |
| <nget> and <nrel> are filled, respectively, with the number of |
| successful (non-NULL return) bget() calls and the number of brel() |
| calls. |
| |
| void bstatse(bufsize *pool_incr, long *npool, |
| long *npget, long *nprel, |
| long *ndget, long *ndrel); |
| |
| Extended statistics: The expansion block size will be stored into the |
| variable pointed to by <pool_incr>, or the negative thereof if automatic |
| expansion block releases are disabled. The number of currently active |
| pool blocks will be stored into the variable pointed to by <npool>. The |
| variables pointed to by <npget> and <nprel> will be filled with, |
| respectively, the number of expansion block acquisitions and releases |
| which have occurred. The variables pointed to by <ndget> and <ndrel> |
| will be filled with the number of bget() and brel() calls, respectively, |
| managed through blocks directly allocated by the acquisition and release |
| functions. |
| |
| void bufdump(void *buf); |
| |
| The buffer pointed to by <buf> is dumped on standard output. |
| |
| void bpoold(void *pool, int dumpalloc, int dumpfree); |
| |
| All buffers in the buffer pool <pool>, previously initialised by a call |
| on bpool(), are listed in ascending memory address order. If |
| <dumpalloc> is nonzero, the contents of allocated buffers are dumped; if |
| <dumpfree> is nonzero, the contents of free blocks are dumped. |
| |
| int bpoolv(void *pool); |
| |
| The named buffer pool, previously initialised by a call on bpool(), is |
| validated for bad pointers, overwritten data, etc. If compiled with |
| NDEBUG not defined, any error generates an assertion failure. Otherwise 1 |
| is returned if the pool is valid, 0 if an error is found. |
| |
| BGET CONFIGURATION |
| ================== |
| |
| #define TestProg 20000 /* Generate built-in test program |
| if defined. The value specifies |
| how many buffer allocation attempts |
| the test program should make. */ |
| |
| #define SizeQuant 4 /* Buffer allocation size quantum: |
| all buffers allocated are a |
| multiple of this size. This |
| MUST be a power of two. */ |
| |
| #define BufDump 1 /* Define this symbol to enable the |
| bpoold() function which dumps the |
| buffers in a buffer pool. */ |
| |
| #define BufValid 1 /* Define this symbol to enable the |
| bpoolv() function for validating |
| a buffer pool. */ |
| |
| #define DumpData 1 /* Define this symbol to enable the |
| bufdump() function which allows |
| dumping the contents of an allocated |
| or free buffer. */ |
| |
| #define BufStats 1 /* Define this symbol to enable the |
| bstats() function which calculates |
| the total free space in the buffer |
| pool, the largest available |
| buffer, and the total space |
| currently allocated. */ |
| |
| #define FreeWipe 1 /* Wipe free buffers to a guaranteed |
| pattern of garbage to trip up |
| miscreants who attempt to use |
| pointers into released buffers. */ |
| |
| #define BestFit 1 /* Use a best fit algorithm when |
| searching for space for an |
| allocation request. This uses |
| memory more efficiently, but |
| allocation will be much slower. */ |
| |
| #define BECtl 1 /* Define this symbol to enable the |
| bectl() function for automatic |
| pool space control. */ |
