The BGET Memory Allocator


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:

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 fifty 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

The following variables, defined at the top of bget.c, allow you to configure various features and operating modes for BGET.

#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.  */

Distribution

BGET is in the public domain. You can do anything you like with it.

  Download BGET Software

View BGET, Vintage 1972


by John Walker
August 21st, 1996