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