Download BGET SoftwareBGET 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 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.
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 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.
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.)
Functions implemented by BGET (some are enabled by certain of the optional settings below):
void bpool(void *buffer, bufsize len);
bpool() subsequently to
contribute additional storage to the overall buffer pool.
void *bget(bufsize size);
NULL if insufficient memory was available to allocate the
buffer.
void *bgetz(bufsize size);
NULL if insufficient memory was
available to allocate the buffer.
void *bgetr(void *buffer, bufsize newsize);
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);
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);
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);
bget() and brel()
calls, respectively, managed through blocks directly allocated by the
acquisition and release functions.
void bufdump(void *buf);
void bpoold(void *pool, int dumpalloc, int dumpfree);
int bpoolv(void *pool);
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.
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. */
BGET is in the public domain. You can do anything you like with it.
Download BGET Software