BGET  --  Memory Allocator                      ==========================                            by John Walker                         kelvin@fourmilab.ch                       http://www.fourmilab.ch/BGET  is  a  comprehensive  memory  allocation  package  which is easilyconfigured to the needs of an application.  BGET is  efficient  in  boththe  time  needed  to  allocate  and  release  buffers and in the memoryoverhead  required  for  buffer  pool  management.    It   automaticallyconsolidates  contiguous  space  to  minimise  fragmentation.   BGET  isconfigured 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-basedembedded programs to providing the framework upon which  a  multitaskingsystem   incorporating   garbage   collection   is   constructed.   BGETincorporates  extensive  internal   consistency   checking   using   the<assert.h>  mechanism;  all  these checks can be turned off by compilingwith NDEBUG defined, yielding a version of BGET with  minimal  size  andmaximum speed.The basic algorithm underlying BGET has withstood the test of time; morethan 25 years have passed since the first implementation of  this  code.And  yet,  it is substantially more efficient than the native allocationschemes of many operating systems: the Macintosh and  Microsoft  Windowsto  name  two,  on which programs have obtained substantial speed-ups bylayering BGET as an application level memory manager atop the underlyingsystem's.BGET  has  been  implemented on the largest mainframes and the lowest ofmicroprocessors.  It has served as the core for  multitasking  operatingsystems,  multi-thread  applications,  embedded software in data networkswitching processors, and a host  of  C  programs.   And  while  it  hasaccreted  flexibility  and additional options over the years, it remainsfast, memory efficient,  portable,  and  easy  to  integrate  into  yourprogram.BGET IMPLEMENTATION ASSUMPTIONS===============================BGET  is  written  in  as portable a dialect of C as possible.  The onlyfundamental assumption about the  underlying  hardware  architecture  isthat  memory  is allocated is a linear array which can be addressed as avector of C "char" objects.  On segmented address  space  architectures,this generally means that BGET should be used to allocate storage withina single segment (although some compilers simulate linear address spaceson  segmented  architectures).   On  segmented architectures, then, BGETbuffer pools may not be larger than a segment, but since BGET allows anynumber  of separate buffer pools, there is no limit on the total storagewhich can be managed, only on the largest individual object which can beallocated.   Machines  with  a  linear address architecture, such as theVAX, 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 arethree basic ways of working with BGET.  The  functions  mentioned  beloware  documented  in  the  following  section.  Please excuse the forwardreferences which are made in the interest  of  providing  a  roadmap  toguide you to the BGET functions you're likely to need.Embedded Applications---------------------Embedded applications typically have a fixed area of memory dedicated tobuffer  allocation  (often in a separate RAM address space distinct fromthe ROM that contains the executable code).  To  use  BGET  in  such  anenvironment,  simply  call  bpool() with the start address and length ofthe buffer pool area in RAM,  then  allocate  buffers  with  bget()  andrelease  them  with brel().  Embedded applications with very limited RAMbut abundant CPU speed may  benefit  by  configuring  BGET  for  BestFitallocation (which is usually not worth it in other environments).Malloc() Emulation------------------If  the  C  library  malloc()  function is too slow, not present in yourdevelopment environment (for example, an a native Windows  or  Macintoshprogram),  or  otherwise  unsuitable,  you  can  replace  it  with BGET.Initially  define  a  buffer  pool   of   an   appropriate   size   withbpool()--usually  obtained  by  making  a call to the operating system'slow-level memory allocator.  Then allocate buffers with bget(), bgetz(),and  bgetr()  (the last two permit the allocation of buffers initialisedto  zero  and  [inefficient]  re-allocation  of  existing  buffers   forcompatibility  with  C  library  functions).  Release buffers by callingbrel().  If a buffer allocation request fails, obtain more storage  fromthe  underlying  operating  system, add it to the buffer pool by anothercall to bpool(), and continue execution.Automatic Storage Management----------------------------You can use  BGET  as  your  application's  native  memory  manager  andimplement  automatic storage pool expansion, contraction, and optionallyapplication-specific memory compaction by compiling BGET with the  BECtlvariable  defined,  then  calling  bectl()  and  supplying functions forstorage compaction, acquisition, and release, as well as a standard poolexpansion  increment.   All of these functions are optional (although itdoesn't make much  sense  to  provide  a  release  function  without  anacquisition function, does it?).  Once the call-back functions have beendefined with bectl(), you simply use bget() and brel() to  allocate  andrelease  storage  as before.  You can supply an initial buffer pool withbpool() or rely on automatic allocation  to  acquire  the  entire  pool.When  a  call  on  bget()  cannot  be  satisfied, BGET first checks if acompaction function has been supplied.  If so, it is  called  (with  thespace  required  to satisfy the allocation request and a sequence numberto allow the  compaction  routine  to  be  called  successively  withoutlooping).   If  the  compaction function is able to free any storage (itneedn't know whether the storage it freed was adequate) it should returna  nonzero  value, whereupon BGET will retry the allocation request and,if  it  fails  again,  call  the  compaction  function  again  with  thenext-higher sequence number.If  the  compaction  function  returns  zero, indicating failure to freespace, or no compaction function is defined, BGET next tests  whether  anon-NULL  allocation  function  was  supplied  to  bectl().  If so, thatfunction is called  with  an  argument  indicating  how  many  bytes  ofadditional space are required.  This will be the standard pool expansionincrement supplied in the call to bectl()  unless  the  original  bget()call  requested  a  buffer  larger  than  this;  buffers larger than thestandard pool block can be managed "off the books" by BGET in this mode.If the allocation function succeeds in obtaining the storage, it returnsa pointer to the new block and BGET  expands  the  buffer  pool;  if  itfails,  the allocation request fails and returns NULL to the caller.  Ifa non-NULL release function is supplied, expansion blocks  which  becometotally  empty  are  released  to  the global free pool by passing theiraddresses to the release function.Equipped with appropriate allocation, release, and compaction functions,BGET  can  be  used  as  part  of  very  sophisticated memory managementstrategies, including garbage collection.  (Note, however, that BGET  is*not*  a  garbage collector by itself, and that developing such a systemrequires much additional logic and careful design of  the  application'smemory allocation strategy.)BGET FUNCTION DESCRIPTIONS==========================Functions implemented by BGET  (some  are  enabled  by  certain  of  theoptional settings below):        void bpool(void *buffer, bufsize len);