1 2 BGET -- Memory Allocator 3 ========================== 4 5 by John Walker 6 http://www.fourmilab.ch/ 7 8BGET is a comprehensive memory allocation package which is easily 9configured to the needs of an application. BGET is efficient in both 10the time needed to allocate and release buffers and in the memory 11overhead required for buffer pool management. It automatically 12consolidates contiguous space to minimise fragmentation. BGET is 13configured by compile-time definitions, Major options include: 14 15 * A built-in test program to exercise BGET and 16 demonstrate how the various functions are used. 17 18 * Allocation by either the "first fit" or "best fit" 19 method. 20 21 * Wiping buffers at release time to catch code which 22 references previously released storage. 23 24 * Built-in routines to dump individual buffers or the 25 entire buffer pool. 26 27 * Retrieval of allocation and pool size statistics. 28 29 * Quantisation of buffer sizes to a power of two to 30 satisfy hardware alignment constraints. 31 32 * Automatic pool compaction, growth, and shrinkage by 33 means of call-backs to user defined functions. 34 35Applications of BGET can range from storage management in ROM-based 36embedded programs to providing the framework upon which a multitasking 37system incorporating garbage collection is constructed. BGET 38incorporates extensive internal consistency checking using the 39<assert.h> mechanism; all these checks can be turned off by compiling 40with NDEBUG defined, yielding a version of BGET with minimal size and 41maximum speed. 42 43The basic algorithm underlying BGET has withstood the test of time; more 44than 25 years have passed since the first implementation of this code. 45And yet, it is substantially more efficient than the native allocation 46schemes of many operating systems: the Macintosh and Microsoft Windows 47to name two, on which programs have obtained substantial speed-ups by 48layering BGET as an application level memory manager atop the underlying 49system's. 50 51BGET has been implemented on the largest mainframes and the lowest of 52microprocessors. It has served as the core for multitasking operating 53systems, multi-thread applications, embedded software in data network 54switching processors, and a host of C programs. And while it has 55accreted flexibility and additional options over the years, it remains 56fast, memory efficient, portable, and easy to integrate into your 57program. 58 59 60BGET IMPLEMENTATION ASSUMPTIONS 61=============================== 62 63BGET is written in as portable a dialect of C as possible. The only 64fundamental assumption about the underlying hardware architecture is 65that memory is allocated is a linear array which can be addressed as a 66vector of C "char" objects. On segmented address space architectures, 67this generally means that BGET should be used to allocate storage within 68a single segment (although some compilers simulate linear address spaces 69on segmented architectures). On segmented architectures, then, BGET 70buffer pools may not be larger than a segment, but since BGET allows any 71number of separate buffer pools, there is no limit on the total storage 72which can be managed, only on the largest individual object which can be 73allocated. Machines with a linear address architecture, such as the 74VAX, 680x0, Sparc, MIPS, or the Intel 80386 and above in native mode, 75may use BGET without restriction. 76 77 78GETTING STARTED WITH BGET 79========================= 80 81Although BGET can be configured in a multitude of fashions, there are 82three basic ways of working with BGET. The functions mentioned below 83are documented in the following section. Please excuse the forward 84references which are made in the interest of providing a roadmap to 85guide you to the BGET functions you're likely to need. 86 87Embedded Applications 88--------------------- 89 90Embedded applications typically have a fixed area of memory dedicated to 91buffer allocation (often in a separate RAM address space distinct from 92the ROM that contains the executable code). To use BGET in such an 93environment, simply call bpool() with the start address and length of 94the buffer pool area in RAM, then allocate buffers with bget() and 95release them with brel(). Embedded applications with very limited RAM 96but abundant CPU speed may benefit by configuring BGET for BestFit 97allocation (which is usually not worth it in other environments). 98 99Malloc() Emulation 100------------------ 101 102If the C library malloc() function is too slow, not present in your 103development environment (for example, an a native Windows or Macintosh 104program), or otherwise unsuitable, you can replace it with BGET. 105Initially define a buffer pool of an appropriate size with 106bpool()--usually obtained by making a call to the operating system's 107low-level memory allocator. Then allocate buffers with bget(), bgetz(), 108and bgetr() (the last two permit the allocation of buffers initialised 109to zero and [inefficient] re-allocation of existing buffers for 110compatibility with C library functions). Release buffers by calling 111brel(). If a buffer allocation request fails, obtain more storage from 112the underlying operating system, add it to the buffer pool by another 113call to bpool(), and continue execution. 114 115Automatic Storage Management 116---------------------------- 117 118You can use BGET as your application's native memory manager and 119implement automatic storage pool expansion, contraction, and optionally 120application-specific memory compaction by compiling BGET with the BECtl 121variable defined, then calling bectl() and supplying functions for 122storage compaction, acquisition, and release, as well as a standard pool 123expansion increment. All of these functions are optional (although it 124doesn't make much sense to provide a release function without an 125acquisition function, does it?). Once the call-back functions have been 126defined with bectl(), you simply use bget() and brel() to allocate and 127release storage as before. You can supply an initial buffer pool with 128bpool() or rely on automatic allocation to acquire the entire pool. 129When a call on bget() cannot be satisfied, BGET first checks if a 130compaction function has been supplied. If so, it is called (with the 131space required to satisfy the allocation request and a sequence number 132to allow the compaction routine to be called successively without 133looping). If the compaction function is able to free any storage (it 134needn't know whether the storage it freed was adequate) it should return 135a nonzero value, whereupon BGET will retry the allocation request and, 136if it fails again, call the compaction function again with the 137next-higher sequence number. 138 139If the compaction function returns zero, indicating failure to free 140space, or no compaction function is defined, BGET next tests whether a 141non-NULL allocation function was supplied to bectl(). If so, that 142function is called with an argument indicating how many bytes of 143additional space are required. This will be the standard pool expansion 144increment supplied in the call to bectl() unless the original bget() 145call requested a buffer larger than this; buffers larger than the 146standard pool block can be managed "off the books" by BGET in this mode. 147If the allocation function succeeds in obtaining the storage, it returns 148a pointer to the new block and BGET expands the buffer pool; if it 149fails, the allocation request fails and returns NULL to the caller. If 150a non-NULL release function is supplied, expansion blocks which become 151totally empty are released to the global free pool by passing their 152addresses to the release function. 153 154Equipped with appropriate allocation, release, and compaction functions, 155BGET can be used as part of very sophisticated memory management 156strategies, including garbage collection. (Note, however, that BGET is 157*not* a garbage collector by itself, and that developing such a system 158requires much additional logic and careful design of the application's 159memory allocation strategy.) 160 161 162BGET FUNCTION DESCRIPTIONS 163========================== 164 165Functions implemented by BGET (some are enabled by certain of the 166optional settings below): 167 168 void bpool(void *buffer, bufsize len); 169 170Create a buffer pool of <len> bytes, using the storage starting at 171<buffer>. You can call bpool() subsequently to contribute additional 172storage to the overall buffer pool. 173 174 void *bget(bufsize size); 175 176Allocate a buffer of <size> bytes. The address of the buffer is 177returned, or NULL if insufficient memory was available to allocate the 178buffer. 179 180 void *bgetz(bufsize size); 181 182Allocate a buffer of <size> bytes and clear it to all zeroes. The 183address of the buffer is returned, or NULL if insufficient memory was 184available to allocate the buffer. 185 186 void *bgetr(void *buffer, bufsize newsize); 187 188Reallocate a buffer previously allocated by bget(), changing its size to 189<newsize> and preserving all existing data. NULL is returned if 190insufficient memory is available to reallocate the buffer, in which case 191the original buffer remains intact. 192 193 void brel(void *buf); 194 195Return the buffer <buf>, previously allocated by bget(), to the free 196space pool. 197 198 void bectl(int (*compact)(bufsize sizereq, int sequence), 199 void *(*acquire)(bufsize size), 200 void (*release)(void *buf), 201 bufsize pool_incr); 202 203Expansion control: specify functions through which the package may 204compact storage (or take other appropriate action) when an allocation 205request fails, and optionally automatically acquire storage for 206expansion blocks when necessary, and release such blocks when they 207become empty. If <compact> is non-NULL, whenever a buffer allocation 208request fails, the <compact> function will be called with arguments 209specifying the number of bytes (total buffer size, including header 210overhead) required to satisfy the allocation request, and a sequence 211number indicating the number of consecutive calls on <compact> 212attempting to satisfy this allocation request. The sequence number is 1 213for the first call on <compact> for a given allocation request, and 214increments on subsequent calls, permitting the <compact> function to 215take increasingly dire measures in an attempt to free up storage. If 216the <compact> function returns a nonzero value, the allocation attempt 217is re-tried. If <compact> returns 0 (as it must if it isn't able to 218release any space or add storage to the buffer pool), the allocation 219request fails, which can trigger automatic pool expansion if the 220<acquire> argument is non-NULL. At the time the <compact> function is 221called, the state of the buffer allocator is identical to that at the 222moment the allocation request was made; consequently, the <compact> 223function may call brel(), bpool(), bstats(), and/or directly manipulate 224the buffer pool in any manner which would be valid were the application 225in control. This does not, however, relieve the <compact> function of 226the need to ensure that whatever actions it takes do not change things 227underneath the application that made the allocation request. For 228example, a <compact> function that released a buffer in the process of 229being reallocated with bgetr() would lead to disaster. Implementing a 230safe and effective <compact> mechanism requires careful design of an 231application's memory architecture, and cannot generally be easily 232retrofitted into existing code. 233 234If <acquire> is non-NULL, that function will be called whenever an 235allocation request fails. If the <acquire> function succeeds in 236allocating the requested space and returns a pointer to the new area, 237allocation will proceed using the expanded buffer pool. If <acquire> 238cannot obtain the requested space, it should return NULL and the entire 239allocation process will fail. <pool_incr> specifies the normal 240expansion block size. Providing an <acquire> function will cause 241subsequent bget() requests for buffers too large to be managed in the 242linked-block scheme (in other words, larger than <pool_incr> minus the 243buffer overhead) to be satisfied directly by calls to the <acquire> 244function. Automatic release of empty pool blocks will occur only if all 245pool blocks in the system are the size given by <pool_incr>. 246 247 void bstats(bufsize *curalloc, bufsize *totfree, 248 bufsize *maxfree, long *nget, long *nrel); 249 250The amount of space currently allocated is stored into the variable 251pointed to by <curalloc>. The total free space (sum of all free blocks 252in the pool) is stored into the variable pointed to by <totfree>, and 253the size of the largest single block in the free space pool is stored 254into the variable pointed to by <maxfree>. The variables pointed to by 255<nget> and <nrel> are filled, respectively, with the number of 256successful (non-NULL return) bget() calls and the number of brel() 257calls. 258 259 void bstatse(bufsize *pool_incr, long *npool, 260 long *npget, long *nprel, 261 long *ndget, long *ndrel); 262 263Extended statistics: The expansion block size will be stored into the 264variable pointed to by <pool_incr>, or the negative thereof if automatic 265expansion block releases are disabled. The number of currently active 266pool blocks will be stored into the variable pointed to by <npool>. The 267variables pointed to by <npget> and <nprel> will be filled with, 268respectively, the number of expansion block acquisitions and releases 269which have occurred. The variables pointed to by <ndget> and <ndrel> 270will be filled with the number of bget() and brel() calls, respectively, 271managed through blocks directly allocated by the acquisition and release 272functions. 273 274 void bufdump(void *buf); 275 276The buffer pointed to by <buf> is dumped on standard output. 277 278 void bpoold(void *pool, int dumpalloc, int dumpfree); 279 280All buffers in the buffer pool <pool>, previously initialised by a call 281on bpool(), are listed in ascending memory address order. If 282<dumpalloc> is nonzero, the contents of allocated buffers are dumped; if 283<dumpfree> is nonzero, the contents of free blocks are dumped. 284 285 int bpoolv(void *pool); 286 287The named buffer pool, previously initialised by a call on bpool(), is 288validated for bad pointers, overwritten data, etc. If compiled with 289NDEBUG not defined, any error generates an assertion failure. Otherwise 1 290is returned if the pool is valid, 0 if an error is found. 291 292BGET CONFIGURATION 293================== 294 295#define TestProg 20000 /* Generate built-in test program 296 if defined. The value specifies 297 how many buffer allocation attempts 298 the test program should make. */ 299 300#define SizeQuant 4 /* Buffer allocation size quantum: 301 all buffers allocated are a 302 multiple of this size. This 303 MUST be a power of two. */ 304 305#define BufDump 1 /* Define this symbol to enable the 306 bpoold() function which dumps the 307 buffers in a buffer pool. */ 308 309#define BufValid 1 /* Define this symbol to enable the 310 bpoolv() function for validating 311 a buffer pool. */ 312 313#define DumpData 1 /* Define this symbol to enable the 314 bufdump() function which allows 315 dumping the contents of an allocated 316 or free buffer. */ 317 318#define BufStats 1 /* Define this symbol to enable the 319 bstats() function which calculates 320 the total free space in the buffer 321 pool, the largest available 322 buffer, and the total space 323 currently allocated. */ 324 325#define FreeWipe 1 /* Wipe free buffers to a guaranteed 326 pattern of garbage to trip up 327 miscreants who attempt to use 328 pointers into released buffers. */ 329 330#define BestFit 1 /* Use a best fit algorithm when 331 searching for space for an 332 allocation request. This uses 333 memory more efficiently, but 334 allocation will be much slower. */ 335 336#define BECtl 1 /* Define this symbol to enable the 337 bectl() function for automatic 338 pool space control. */ 339