geekos/src/geekos/bget.c

   1 // Adapted for geekos: http://www.cs.umd.edu/~daveho/geekos/
   2 // Original version of BGET downloaded from: http://www.fourmilab.ch/bget/
   3 // $Revision: 1.1 $
   4
   5 // GeekOS changes are (mostly) confined to #if defined (GEEKOS)
   6 // sections.
   7
   8 /*
   9
  10                                B G E T
  11
  12                            Buffer allocator
  13
  14     Designed and implemented in April of 1972 by John Walker, based on the
  15     Case Algol OPRO$ algorithm implemented in 1966.
  16
  17     Reimplemented in 1975 by John Walker for the Interdata 70.
  18     Reimplemented in 1977 by John Walker for the Marinchip 9900.
  19     Reimplemented in 1982 by Duff Kurland for the Intel 8080.
  20
  21     Portable C version implemented in September of 1990 by an older, wiser
  22     instance of the original implementor.
  23
  24     Souped up and/or weighed down  slightly  shortly  thereafter  by  Greg
  25     Lutz.
  26
  27     AMIX  edition, including the new compaction call-back option, prepared
  28     by John Walker in July of 1992.
  29
  30     Bug in built-in test program fixed, ANSI compiler warnings eradicated,
  31     buffer pool validator  implemented,  and  guaranteed  repeatable  test
  32     added by John Walker in October of 1995.
  33
  34     This program is in the public domain.
  35
  36      1. This is the book of the generations of Adam.   In the day that God
  37         created man, in the likeness of God made he him;
  38      2. Male and female created he them;  and  blessed  them,  and  called
  39         their name Adam, in the day when they were created.
  40      3. And  Adam  lived  an hundred and thirty years,  and begat a son in
  41         his own likeness, and after his image; and called his name Seth:
  42      4. And the days of  Adam  after  he  had  begotten  Seth  were  eight
  43         hundred years: and he begat sons and daughters:
  44      5. And  all  the  days  that Adam lived were nine  hundred and thirty
  45         years: and he died.
  46      6. And Seth lived an hundred and five years, and begat Enos:
  47      7. And Seth lived after he begat Enos eight hundred and seven  years,
  48         and begat sons and daughters:
  49      8.  And  all the days of Seth were nine hundred and twelve years: and
  50          he died.
  51      9. And Enos lived ninety years, and begat Cainan:
  52     10. And Enos lived after he begat  Cainan eight  hundred  and  fifteen
  53         years, and begat sons and daughters:
  54     11. And  all  the days of Enos were nine hundred  and five years:  and
  55         he died.
  56     12. And Cainan lived seventy years and begat Mahalaleel:
  57     13. And Cainan lived  after he  begat  Mahalaleel  eight  hundred  and
  58         forty years, and begat sons and daughters:
  59     14. And  all the days of Cainan were nine  hundred and ten years:  and
  60         he died.
  61     15. And Mahalaleel lived sixty and five years, and begat Jared:
  62     16. And Mahalaleel lived  after  he  begat  Jared  eight  hundred  and
  63         thirty years, and begat sons and daughters:
  64     17. And  all  the  days  of Mahalaleel  were eight hundred  ninety and
  65         five years: and he died.
  66     18. And Jared lived an hundred sixty and  two  years,   and  he  begat
  67         Enoch:
  68     19. And  Jared  lived  after he begat Enoch  eight hundred years,  and
  69         begat sons and daughters:
  70     20. And all the days of Jared  were nine hundred sixty and two  years:
  71         and he died.
  72     21. And Enoch lived sixty and five years, and begat Methuselah:
  73     22. And  Enoch  walked   with  God  after  he  begat Methuselah  three
  74         hundred years, and begat sons and daughters:
  75     23. And all the days of  Enoch  were  three  hundred  sixty  and  five
  76         years:
  77     24. And Enoch walked with God: and he was not; for God took him.
  78     25. And  Methuselah  lived  an  hundred  eighty and  seven years,  and
  79         begat Lamech.
  80     26. And Methuselah lived after he  begat Lamech seven  hundred  eighty
  81         and two years, and begat sons and daughters:
  82     27. And  all the days of Methuselah  were nine hundred  sixty and nine
  83         years: and he died.
  84     28. And Lamech lived an hundred eighty  and two  years,  and  begat  a
  85         son:
  86     29. And  he called his name Noah, saying,  This same shall  comfort us
  87         concerning  our  work and toil of our hands, because of the ground
  88         which the LORD hath cursed.
  89     30. And  Lamech  lived  after  he begat Noah  five hundred  ninety and
  90         five years, and begat sons and daughters:
  91     31. And all the days of Lamech were  seven hundred seventy  and  seven
  92         years: and he died.
  93     32. And  Noah  was five hundred years old:  and Noah begat Shem,  Ham,
  94         and Japheth.
  95
  96     And buffers begat buffers, and links begat  links,  and  buffer  pools
  97     begat  links  to chains of buffer pools containing buffers, and lo the
  98     buffers and links and pools of buffers and pools of links to chains of
  99     pools  of  buffers were fruitful and they multiplied and the Operating
 100     System looked down upon them and said that it was Good.
 101
 102
 103     INTRODUCTION
 104     ============
 105
 106     BGET  is a comprehensive memory allocation package which is easily
 107     configured to the needs of an application.  BGET is  efficient  in
 108     both  the  time  needed to allocate and release buffers and in the
 109     memory  overhead  required  for  buffer   pool   management.    It
 110     automatically    consolidates   contiguous   space   to   minimise
 111     fragmentation.  BGET is configured  by  compile-time  definitions,
 112     Major options include:
 113
 114         *   A  built-in  test  program  to  exercise  BGET   and
 115             demonstrate how the various functions are used.
 116
 117         *   Allocation  by  either the "first fit" or "best fit"
 118             method.
 119
 120         *   Wiping buffers at release time to catch  code  which
 121             references previously released storage.
 122
 123         *   Built-in  routines to dump individual buffers or the
 124             entire buffer pool.
 125
 126         *   Retrieval of allocation and pool size statistics.
 127
 128         *   Quantisation of buffer sizes to a power  of  two  to
 129             satisfy hardware alignment constraints.
 130
 131         *   Automatic  pool compaction, growth, and shrinkage by
 132             means of call-backs to user defined functions.
 133
 134     Applications  of  BGET  can  range  from  storage  management   in
 135     ROM-based  embedded programs to providing the framework upon which
 136     a  multitasking  system  incorporating   garbage   collection   is
 137     constructed.   BGET  incorporates  extensive  internal consistency
 138     checking using the <assert.h> mechanism; all these checks  can  be
 139     turned off by compiling with NDEBUG defined, yielding a version of
 140     BGET with minimal size and maximum speed.
 141
 142     The  basic  algorithm  underlying  BGET  has withstood the test of
 143     time;  more  than  25  years   have   passed   since   the   first
 144     implementation  of  this  code.  And yet, it is substantially more
 145     efficient than the native allocation  schemes  of  many  operating
 146     systems: the Macintosh and Microsoft Windows to name two, on which
 147     programs have obtained substantial speed-ups by layering  BGET  as
 148     an application level memory manager atop the underlying system's.
 149
 150     BGET has been implemented on the largest mainframes and the lowest
 151     of  microprocessors.   It  has served as the core for multitasking
 152     operating systems, multi-thread applications, embedded software in
 153     data  network switching processors, and a host of C programs.  And
 154     while it has accreted flexibility and additional options over  the
 155     years,  it  remains  fast, memory efficient, portable, and easy to
 156     integrate into your program.
 157
 158
 159     BGET IMPLEMENTATION ASSUMPTIONS
 160     ===============================
 161
 162     BGET is written in as portable a dialect of C  as  possible.   The
 163     only   fundamental   assumption   about  the  underlying  hardware
 164     architecture is that memory is allocated is a linear  array  which
 165     can  be  addressed  as a vector of C "char" objects.  On segmented
 166     address space architectures, this generally means that BGET should
 167     be used to allocate storage within a single segment (although some
 168     compilers   simulate   linear   address   spaces   on    segmented
 169     architectures).   On  segmented  architectures,  then, BGET buffer
 170     pools  may not be larger than a segment, but since BGET allows any
 171     number of separate buffer pools, there is no limit  on  the  total
 172     storage  which  can  be  managed,  only  on the largest individual
 173     object which can be allocated.  Machines  with  a  linear  address
 174     architecture,  such  as  the VAX, 680x0, Sparc, MIPS, or the Intel
 175     80386 and above in native mode, may use BGET without restriction.
 176
 177
 178     GETTING STARTED WITH BGET
 179     =========================
 180
 181     Although BGET can be configured in a multitude of fashions,  there
 182     are  three  basic  ways  of  working  with  BGET.   The  functions
 183     mentioned below are documented in the following  section.   Please
 184     excuse  the  forward  references which are made in the interest of
 185     providing a roadmap to guide you  to  the  BGET  functions  you're
 186     likely to need.
 187
 188     Embedded Applications
 189     ---------------------
 190
 191     Embedded applications  typically  have  a  fixed  area  of  memory
 192     dedicated  to  buffer  allocation (often in a separate RAM address
 193     space distinct from the ROM that contains  the  executable  code).
 194     To  use  BGET in such an environment, simply call bpool() with the
 195     start address and length of the buffer  pool  area  in  RAM,  then
 196     allocate  buffers  with  bget()  and  release  them  with  brel().
 197     Embedded applications with very limited RAM but abundant CPU speed
 198     may  benefit  by configuring BGET for BestFit allocation (which is
 199     usually not worth it in other environments).
 200
 201     Malloc() Emulation
 202     ------------------
 203
 204     If the C library malloc() function is too  slow,  not  present  in
 205     your  development environment (for example, an a native Windows or
 206     Macintosh program), or otherwise unsuitable, you  can  replace  it
 207     with  BGET.  Initially define a buffer pool of an appropriate size
 208     with bpool()--usually obtained by making a call to  the  operating
 209     system's  low-level  memory allocator.  Then allocate buffers with
 210     bget(), bgetz(), and bgetr() (the last two permit  the  allocation
 211     of  buffers initialised to zero and [inefficient] re-allocation of
 212     existing buffers for  compatibility  with  C  library  functions).
 213     Release buffers by calling brel().  If a buffer allocation request
 214     fails, obtain more storage from the underlying  operating  system,
 215     add it to the buffer pool by another call to bpool(), and continue
 216     execution.
 217
 218     Automatic Storage Management
 219     ----------------------------
 220
 221     You can use BGET as your application's native memory  manager  and
 222     implement  automatic  storage  pool  expansion,  contraction,  and
 223     optionally application-specific  memory  compaction  by  compiling
 224     BGET  with  the  BECtl  variable defined, then calling bectl() and
 225     supplying  functions  for  storage  compaction,  acquisition,  and
 226     release,  as  well as a standard pool expansion increment.  All of
 227     these functions are optional (although it doesn't make much  sense
 228     to  provide  a  release  function without an acquisition function,
 229     does it?).  Once the call-back functions have  been  defined  with
 230     bectl(),  you simply use bget() and brel() to allocate and release
 231     storage as before.  You can supply an  initial  buffer  pool  with
 232     bpool()  or  rely  on  automatic  allocation to acquire the entire
 233     pool.  When a call on  bget()  cannot  be  satisfied,  BGET  first
 234     checks  if  a compaction function has been supplied.  If so, it is
 235     called (with the space required to satisfy the allocation  request
 236     and a sequence number to allow the compaction routine to be called
 237     successively without looping).  If the compaction function is able
 238     to  free any storage (it needn't know whether the storage it freed
 239     was adequate) it should return a  nonzero  value,  whereupon  BGET
 240     will retry the allocation request and, if it fails again, call the
 241     compaction function again with the next-higher sequence number.
 242
 243     If  the  compaction  function  returns zero, indicating failure to
 244     free space, or no compaction function is defined, BGET next  tests
 245     whether  a  non-NULL  allocation function was supplied to bectl().
 246     If so, that function is called with  an  argument  indicating  how
 247     many  bytes  of  additional  space are required.  This will be the
 248     standard pool expansion increment supplied in the call to  bectl()
 249     unless  the  original  bget()  call requested a buffer larger than
 250     this; buffers larger than the standard pool block can  be  managed
 251     "off  the books" by BGET in this mode.  If the allocation function
 252     succeeds in obtaining the storage, it returns a pointer to the new
 253     block  and  BGET  expands  the  buffer  pool;  if  it  fails,  the
 254     allocation request fails and returns NULL to  the  caller.   If  a
 255     non-NULL  release  function  is  supplied,  expansion blocks which
 256     become totally empty are released  to  the  global  free  pool  by
 257     passing their addresses to the release function.
 258
 259     Equipped  with  appropriate  allocation,  release,  and compaction
 260     functions, BGET can be used as part of very  sophisticated  memory
 261     management   strategies,  including  garbage  collection.   (Note,
 262     however, that BGET is *not* a garbage  collector  by  itself,  and
 263     that  developing  such a system requires much additional logic and
 264     careful design of the application's memory allocation strategy.)
 265
 266
 267     BGET FUNCTION DESCRIPTIONS
 268     ==========================
 269
 270     Functions implemented in this file (some are enabled by certain of
 271     the optional settings below):
 272
 273             void bpool(void *buffer, bufsize len);
 274
 275     Create a buffer pool of <len> bytes, using the storage starting at
 276     <buffer>.   You  can  call  bpool()  subsequently  to   contribute
 277     additional storage to the overall buffer pool.
 278
 279             void *bget(bufsize size);
 280
 281     Allocate  a  buffer of <size> bytes.  The address of the buffer is
 282     returned, or NULL if insufficient memory was available to allocate
 283     the buffer.
 284
 285             void *bgetz(bufsize size);
 286
 287     Allocate a buffer of <size> bytes and clear it to all zeroes.  The
 288     address of the buffer is returned, or NULL if insufficient  memory
 289     was available to allocate the buffer.
 290
 291             void *bgetr(void *buffer, bufsize newsize);
 292
 293     Reallocate a buffer previously allocated by bget(),  changing  its
 294     size  to  <newsize>  and  preserving  all  existing data.  NULL is
 295     returned if insufficient memory is  available  to  reallocate  the
 296     buffer, in which case the original buffer remains intact.
 297
 298             void brel(void *buf);
 299
 300     Return  the  buffer  <buf>, previously allocated by bget(), to the
 301     free space pool.
 302
 303             void bectl(int (*compact)(bufsize sizereq, int sequence),
 304                        void *(*acquire)(bufsize size),
 305                        void (*release)(void *buf),
 306                        bufsize pool_incr);
 307
 308     Expansion control: specify functions through which the package may
 309     compact  storage  (or  take  other  appropriate  action)  when  an
 310     allocation  request  fails,  and  optionally automatically acquire
 311     storage for expansion blocks  when  necessary,  and  release  such
 312     blocks when they become empty.  If <compact> is non-NULL, whenever
 313     a buffer allocation request fails, the <compact> function will  be
 314     called with arguments specifying the number of bytes (total buffer
 315     size,  including  header  overhead)  required   to   satisfy   the
 316     allocation request, and a sequence number indicating the number of
 317     consecutive  calls  on  <compact>  attempting  to   satisfy   this
 318     allocation  request.   The sequence number is 1 for the first call
 319     on <compact> for a given allocation  request,  and  increments  on
 320     subsequent  calls,  permitting  the  <compact>  function  to  take
 321     increasingly dire measures in an attempt to free up  storage.   If
 322     the  <compact>  function  returns  a nonzero value, the allocation
 323     attempt is re-tried.  If <compact> returns 0 (as  it  must  if  it
 324     isn't  able  to  release  any  space  or add storage to the buffer
 325     pool), the allocation request fails, which can  trigger  automatic
 326     pool expansion if the <acquire> argument is non-NULL.  At the time
 327     the  <compact>  function  is  called,  the  state  of  the  buffer
 328     allocator  is  identical  to  that  at  the  moment the allocation
 329     request was made; consequently, the <compact>  function  may  call
 330     brel(), bpool(), bstats(), and/or directly manipulate  the  buffer
 331     pool  in  any  manner which would be valid were the application in
 332     control.  This does not, however, relieve the  <compact>  function
 333     of the need to ensure that whatever actions it takes do not change
 334     things   underneath  the  application  that  made  the  allocation
 335     request.  For example, a <compact> function that released a buffer
 336     in  the  process  of  being reallocated with bgetr() would lead to
 337     disaster.  Implementing a safe and effective  <compact>  mechanism
 338     requires  careful  design of an application's memory architecture,
 339     and cannot generally be easily retrofitted into existing code.
 340
 341     If <acquire> is non-NULL, that function will be called whenever an
 342     allocation  request  fails.  If the <acquire> function succeeds in
 343     allocating the requested space and returns a pointer  to  the  new
 344     area,  allocation will proceed using the expanded buffer pool.  If
 345     <acquire> cannot obtain the requested space, it should return NULL
 346     and   the   entire  allocation  process  will  fail.   <pool_incr>
 347     specifies the normal expansion block size.  Providing an <acquire>
 348     function will cause subsequent bget()  requests  for  buffers  too
 349     large  to  be  managed in the linked-block scheme (in other words,
 350     larger than <pool_incr> minus the buffer overhead) to be satisfied
 351     directly by calls to the <acquire> function.  Automatic release of
 352     empty pool blocks will occur only if all pool blocks in the system
 353     are the size given by <pool_incr>.
 354
 355             void bstats(bufsize *curalloc, bufsize *totfree,
 356                         bufsize *maxfree, long *nget, long *nrel);
 357
 358     The amount  of  space  currently  allocated  is  stored  into  the
 359     variable  pointed  to by <curalloc>.  The total free space (sum of
 360     all free blocks in the pool) is stored into the  variable  pointed
 361     to  by  <totfree>, and the size of the largest single block in the
 362     free space  pool  is  stored  into  the  variable  pointed  to  by
 363     <maxfree>.   The  variables  pointed  to  by <nget> and <nrel> are
 364     filled, respectively, with  the  number  of  successful  (non-NULL
 365     return) bget() calls and the number of brel() calls.
 366
 367             void bstatse(bufsize *pool_incr, long *npool,
 368                          long *npget, long *nprel,
 369                          long *ndget, long *ndrel);
 370
 371     Extended  statistics: The expansion block size will be stored into
 372     the variable pointed to by <pool_incr>, or the negative thereof if
 373     automatic  expansion  block  releases are disabled.  The number of
 374     currently active pool blocks will  be  stored  into  the  variable
 375     pointed  to  by  <npool>.  The variables pointed to by <npget> and
 376     <nprel> will be filled with, respectively, the number of expansion
 377     block   acquisitions   and  releases  which  have  occurred.   The
 378     variables pointed to by <ndget> and <ndrel> will  be  filled  with
 379     the  number  of  bget()  and  brel()  calls, respectively, managed
 380     through blocks directly allocated by the acquisition  and  release
 381     functions.
 382
 383             void bufdump(void *buf);
 384
 385     The buffer pointed to by <buf> is dumped on standard output.
 386
 387             void bpoold(void *pool, int dumpalloc, int dumpfree);
 388
 389     All buffers in the buffer pool <pool>, previously initialised by a
 390     call on bpool(), are listed in ascending memory address order.  If
 391     <dumpalloc> is nonzero, the  contents  of  allocated  buffers  are
 392     dumped;  if <dumpfree> is nonzero, the contents of free blocks are
 393     dumped.
 394
 395             int bpoolv(void *pool);
 396
 397     The  named  buffer  pool,  previously  initialised  by  a  call on
 398     bpool(), is validated for bad pointers, overwritten data, etc.  If
 399     compiled with NDEBUG not defined, any error generates an assertion
 400     failure.  Otherwise 1 is returned if the pool is valid,  0  if  an
 401     error is found.
 402
 403
 404     BGET CONFIGURATION
 405     ==================
 406 */
 407
 408 /*#define TestProg    20000*/         /* Generate built-in test program
 409                                          if defined.  The value specifies
 410                                          how many buffer allocation attempts
 411                                          the test program should make. */
 412
 413 #define SizeQuant   4                 /* Buffer allocation size quantum:
 414                                          all buffers allocated are a
 415                                          multiple of this size.  This
 416                                          MUST be a power of two. */
 417
 418 /*#define BufDump     1*/                     /* Define this symbol to enable the
 419                                          bpoold() function which dumps the
 420                                          buffers in a buffer pool. */
 421
 422 /*#define BufValid    1*/                     /* Define this symbol to enable the
 423                                          bpoolv() function for validating
 424                                          a buffer pool. */
 425
 426 /*#define DumpData    1*/                     /* Define this symbol to enable the
 427                                          bufdump() function which allows
 428                                          dumping the contents of an allocated
 429                                          or free buffer. */
 430
 431 /*#define BufStats    1*/                     /* Define this symbol to enable the
 432                                          bstats() function which calculates
 433                                          the total free space in the buffer
 434                                          pool, the largest available
 435                                          buffer, and the total space
 436                                          currently allocated. */
 437
 438 /*#define FreeWipe    1*/                     /* Wipe free buffers to a guaranteed
 439                                          pattern of garbage to trip up
 440                                          miscreants who attempt to use
 441                                          pointers into released buffers. */
 442
 443 #define BestFit     1                 /* Use a best fit algorithm when
 444                                          searching for space for an
 445                                          allocation request.  This uses
 446                                          memory more efficiently, but
 447                                          allocation will be much slower. */
 448
 449 /*#define BECtl     1*/               /* Define this symbol to enable the
 450                                          bectl() function for automatic
 451                                          pool space control.  */
 452
 453 #if defined (GEEKOS)
 454
 455 #include <geekos/string.h> // for memset()
 456
 457 // Provide an assert() macro
 458 #include <geekos/kassert.h>
 459 #define assert(exp) KASSERT(exp)
 460
 461 #else // define (GEEKOS)
 462
 463 #include <stdio.h>
 464
 465 #ifdef lint
 466 #define NDEBUG                        /* Exits in asserts confuse lint */
 467 /* LINTLIBRARY */                     /* Don't complain about def, no ref */
 468 extern char *sprintf();               /* Sun includes don't define sprintf */
 469 #endif
 470
 471 #include <assert.h>
 472 #include <memory.h>
 473
 474 #endif // defined (GEEKOS)
 475
 476 #ifdef BufDump                        /* BufDump implies DumpData */
 477 #ifndef DumpData
 478 #define DumpData    1
 479 #endif
 480 #endif
 481
 482 #ifdef DumpData
 483 #include <ctype.h>
 484 #endif
 485
 486 /*  Declare the interface, including the requested buffer size type,
 487     bufsize.  */
 488
 489 #include <geekos/bget.h>
 490
 491 #define MemSize     int               /* Type for size arguments to memxxx()
 492                                          functions such as memcmp(). */
 493
 494 /* Queue links */
 495
 496 struct qlinks {
 497     struct bfhead *flink;             /* Forward link */
 498     struct bfhead *blink;             /* Backward link */
 499 };
 500
 501 /* Header in allocated and free buffers */
 502
 503 struct bhead {
 504     bufsize prevfree;                 /* Relative link back to previous
 505                                          free buffer in memory or 0 if
 506                                          previous buffer is allocated.  */
 507     bufsize bsize;                    /* Buffer size: positive if free,
 508                                          negative if allocated. */
 509 };
 510 #define BH(p)   ((struct bhead *) (p))
 511
 512 /*  Header in directly allocated buffers (by acqfcn) */
 513
 514 struct bdhead {
 515     bufsize tsize;                    /* Total size, including overhead */
 516     struct bhead bh;                  /* Common header */
 517 };
 518 #define BDH(p)  ((struct bdhead *) (p))
 519
 520 /* Header in free buffers */
 521
 522 struct bfhead {
 523     struct bhead bh;                  /* Common allocated/free header */
 524     struct qlinks ql;                 /* Links on free list */
 525 };
 526 #define BFH(p)  ((struct bfhead *) (p))
 527
 528 static struct bfhead freelist = {     /* List of free buffers */
 529     {0, 0},
 530     {&freelist, &freelist}
 531 };
 532
 533
 534 #ifdef BufStats
 535 static bufsize totalloc = 0;          /* Total space currently allocated */
 536 static long numget = 0, numrel = 0;   /* Number of bget() and brel() calls */
 537 #ifdef BECtl
 538 static long numpblk = 0;              /* Number of pool blocks */
 539 static long numpget = 0, numprel = 0; /* Number of block gets and rels */
 540 static long numdget = 0, numdrel = 0; /* Number of direct gets and rels */
 541 #endif /* BECtl */
 542 #endif /* BufStats */
 543
 544 #ifdef BECtl
 545
 546 /* Automatic expansion block management functions */
 547
 548 static int (*compfcn) _((bufsize sizereq, int sequence)) = NULL;
 549 static void *(*acqfcn) _((bufsize size)) = NULL;
 550 static void (*relfcn) _((void *buf)) = NULL;
 551
 552 static bufsize exp_incr = 0;          /* Expansion block size */
 553 static bufsize pool_len = 0;          /* 0: no bpool calls have been made
 554                                          -1: not all pool blocks are
 555                                              the same size
 556                                          >0: (common) block size for all
 557                                              bpool calls made so far
 558                                       */
 559 #endif
 560
 561 /*  Minimum allocation quantum: */
 562
 563 #define QLSize  (sizeof(struct qlinks))
 564 #define SizeQ   ((SizeQuant > QLSize) ? SizeQuant : QLSize)
 565
 566 #define V   (void)                    /* To denote unwanted returned values */
 567
 568 /* End sentinel: value placed in bsize field of dummy block delimiting
 569    end of pool block.  The most negative number which will  fit  in  a
 570    bufsize, defined in a way that the compiler will accept. */
 571
 572 #define ESent   ((bufsize) (-(((1L << (sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))
 573
 574 /*  BGET  --  Allocate a buffer.  */
 575
 576 void *bget(requested_size)
 577   bufsize requested_size;
 578 {
 579     bufsize size = requested_size;
 580     struct bfhead *b;
 581 #ifdef BestFit
 582     struct bfhead *best;
 583 #endif
 584     void *buf;
 585 #ifdef BECtl
 586     int compactseq = 0;
 587 #endif
 588
 589     assert(size > 0);
 590
 591     if (size < SizeQ) {               /* Need at least room for the */
 592         size = SizeQ;                 /*    queue links.  */
 593     }
 594 #ifdef SizeQuant
 595 #if SizeQuant > 1
 596     size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1));
 597 #endif
 598 #endif
 599
 600     size += sizeof(struct bhead);     /* Add overhead in allocated buffer
 601                                          to size required. */
 602
 603 #ifdef BECtl
 604     /* If a compact function was provided in the call to bectl(), wrap
 605        a loop around the allocation process  to  allow  compaction  to
 606        intervene in case we don't find a suitable buffer in the chain. */
 607
 608     while (1) {
 609 #endif
 610         b = freelist.ql.flink;
 611 #ifdef BestFit
 612         best = &freelist;
 613 #endif
 614
 615
 616         /* Scan the free list searching for the first buffer big enough
 617            to hold the requested size buffer. */
 618
 619 #ifdef BestFit
 620         while (b != &freelist) {
 621             if (b->bh.bsize >= size) {
 622                 if ((best == &freelist) || (b->bh.bsize < best->bh.bsize)) {
 623                     best = b;
 624                 }
 625             }
 626             b = b->ql.flink;              /* Link to next buffer */
 627         }
 628         b = best;
 629 #endif /* BestFit */
 630
 631         while (b != &freelist) {
 632             if ((bufsize) b->bh.bsize >= size) {
 633
 634                 /* Buffer  is big enough to satisfy  the request.  Allocate it
 635                    to the caller.  We must decide whether the buffer is  large
 636                    enough  to  split  into  the part given to the caller and a
 637                    free buffer that remains on the free list, or  whether  the
 638                    entire  buffer  should  be  removed  from the free list and
 639                    given to the caller in its entirety.   We  only  split  the
 640                    buffer if enough room remains for a header plus the minimum
 641                    quantum of allocation. */
 642
 643                 if ((b->bh.bsize - size) > (SizeQ + (sizeof(struct bhead)))) {
 644                     struct bhead *ba, *bn;
 645
 646                     ba = BH(((char *) b) + (b->bh.bsize - size));
 647                     bn = BH(((char *) ba) + size);
 648                     assert(bn->prevfree == b->bh.bsize);
 649                     /* Subtract size from length of free block. */
 650                     b->bh.bsize -= size;
 651                     /* Link allocated buffer to the previous free buffer. */
 652                     ba->prevfree = b->bh.bsize;
 653                     /* Plug negative size into user buffer. */
 654                     ba->bsize = -(bufsize) size;
 655                     /* Mark buffer after this one not preceded by free block. */
 656                     bn->prevfree = 0;
 657
 658 #ifdef BufStats
 659                     totalloc += size;
 660                     numget++;             /* Increment number of bget() calls */
 661 #endif
 662                     buf = (void *) ((((char *) ba) + sizeof(struct bhead)));
 663                     return buf;
 664                 } else {
 665                     struct bhead *ba;
 666
 667                     ba = BH(((char *) b) + b->bh.bsize);
 668                     assert(ba->prevfree == b->bh.bsize);
 669
 670                     /* The buffer isn't big enough to split.  Give  the  whole
 671                        shebang to the caller and remove it from the free list. */
 672
 673                     assert(b->ql.blink->ql.flink == b);
 674                     assert(b->ql.flink->ql.blink == b);
 675                     b->ql.blink->ql.flink = b->ql.flink;
 676                     b->ql.flink->ql.blink = b->ql.blink;
 677
 678 #ifdef BufStats
 679                     totalloc += b->bh.bsize;
 680                     numget++;             /* Increment number of bget() calls */
 681 #endif
 682                     /* Negate size to mark buffer allocated. */
 683                     b->bh.bsize = -(b->bh.bsize);
 684
 685                     /* Zero the back pointer in the next buffer in memory
 686                        to indicate that this buffer is allocated. */
 687                     ba->prevfree = 0;
 688
 689                     /* Give user buffer starting at queue links. */
 690                     buf =  (void *) &(b->ql);
 691                     return buf;
 692                 }
 693             }
 694             b = b->ql.flink;              /* Link to next buffer */
 695         }
 696 #ifdef BECtl
 697
 698         /* We failed to find a buffer.  If there's a compact  function
 699            defined,  notify  it  of the size requested.  If it returns
 700            true, try the allocation again. */
 701
 702         if ((compfcn == NULL) || (!(*compfcn)(size, ++compactseq))) {
 703             break;
 704         }
 705     }
 706
 707     /* No buffer available with requested size free. */
 708
 709     /* Don't give up yet -- look in the reserve supply. */
 710
 711     if (acqfcn != NULL) {
 712         if (size > exp_incr - sizeof(struct bhead)) {
 713
 714             /* Request  is  too  large  to  fit in a single expansion
 715                block.  Try to satisy it by a direct buffer acquisition. */
 716
 717             struct bdhead *bdh;
 718
 719             size += sizeof(struct bdhead) - sizeof(struct bhead);
 720             if ((bdh = BDH((*acqfcn)((bufsize) size))) != NULL) {
 721
 722                 /*  Mark the buffer special by setting the size field
 723                     of its header to zero.  */
 724                 bdh->bh.bsize = 0;
 725                 bdh->bh.prevfree = 0;
 726                 bdh->tsize = size;
 727 #ifdef BufStats
 728                 totalloc += size;
 729                 numget++;             /* Increment number of bget() calls */
 730                 numdget++;            /* Direct bget() call count */
 731 #endif
 732                 buf =  (void *) (bdh + 1);
 733                 return buf;
 734             }
 735
 736         } else {
 737
 738             /*  Try to obtain a new expansion block */
 739
 740             void *newpool;
 741
 742             if ((newpool = (*acqfcn)((bufsize) exp_incr)) != NULL) {
 743                 bpool(newpool, exp_incr);
 744                 buf =  bget(requested_size);  /* This can't, I say, can't
 745                                                  get into a loop. */
 746                 return buf;
 747             }
 748         }
 749     }
 750
 751     /*  Still no buffer available */
 752
 753 #endif /* BECtl */
 754
 755     return NULL;
 756 }
 757
 758 /*  BGETZ  --  Allocate a buffer and clear its contents to zero.  We clear
 759                the  entire  contents  of  the buffer to zero, not just the
 760                region requested by the caller. */
 761
 762 void *bgetz(size)
 763   bufsize size;
 764 {
 765     char *buf = (char *) bget(size);
 766
 767     if (buf != NULL) {
 768         struct bhead *b;
 769         bufsize rsize;
 770
 771         b = BH(buf - sizeof(struct bhead));
 772         rsize = -(b->bsize);
 773         if (rsize == 0) {
 774             struct bdhead *bd;
 775
 776             bd = BDH(buf - sizeof(struct bdhead));
 777             rsize = bd->tsize - sizeof(struct bdhead);
 778         } else {
 779             rsize -= sizeof(struct bhead);
 780         }
 781         assert(rsize >= size);
 782         V memset(buf, 0, (MemSize) rsize);
 783     }
 784     return ((void *) buf);
 785 }
 786
 787 /*  BGETR  --  Reallocate a buffer.  This is a minimal implementation,
 788                simply in terms of brel()  and  bget().   It  could  be
 789                enhanced to allow the buffer to grow into adjacent free
 790                blocks and to avoid moving data unnecessarily.  */
 791
 792 void *bgetr(buf, size)
 793   void *buf;
 794   bufsize size;
 795 {
 796     void *nbuf;
 797     bufsize osize;                    /* Old size of buffer */
 798     struct bhead *b;
 799
 800     if ((nbuf = bget(size)) == NULL) { /* Acquire new buffer */
 801         return NULL;
 802     }
 803     if (buf == NULL) {
 804         return nbuf;
 805     }
 806     b = BH(((char *) buf) - sizeof(struct bhead));
 807     osize = -b->bsize;
 808 #ifdef BECtl
 809     if (osize == 0) {
 810         /*  Buffer acquired directly through acqfcn. */
 811         struct bdhead *bd;
 812
 813         bd = BDH(((char *) buf) - sizeof(struct bdhead));
 814         osize = bd->tsize - sizeof(struct bdhead);
 815     } else
 816 #endif
 817         osize -= sizeof(struct bhead);
 818     assert(osize > 0);
 819     V memcpy((char *) nbuf, (char *) buf, /* Copy the data */
 820              (MemSize) ((size < osize) ? size : osize));
 821     brel(buf);
 822     return nbuf;
 823 }
 824
 825 /*  BREL  --  Release a buffer.  */
 826
 827 void brel(buf)
 828   void *buf;
 829 {
 830     struct bfhead *b, *bn;
 831
 832     b = BFH(((char *) buf) - sizeof(struct bhead));
 833 #ifdef BufStats
 834     numrel++;                         /* Increment number of brel() calls */
 835 #endif
 836     assert(buf != NULL);
 837
 838 #ifdef BECtl
 839     if (b->bh.bsize == 0) {           /* Directly-acquired buffer? */
 840         struct bdhead *bdh;
 841
 842         bdh = BDH(((char *) buf) - sizeof(struct bdhead));
 843         assert(b->bh.prevfree == 0);
 844 #ifdef BufStats
 845         totalloc -= bdh->tsize;
 846         assert(totalloc >= 0);
 847         numdrel++;                    /* Number of direct releases */
 848 #endif /* BufStats */
 849 #ifdef FreeWipe
 850         V memset((char *) buf, 0x55,
 851                  (MemSize) (bdh->tsize - sizeof(struct bdhead)));
 852 #endif /* FreeWipe */
 853         assert(relfcn != NULL);
 854         (*relfcn)((void *) bdh);      /* Release it directly. */
 855         return;
 856     }
 857 #endif /* BECtl */
 858
 859     /* Buffer size must be negative, indicating that the buffer is
 860        allocated. */
 861
 862     if (b->bh.bsize >= 0) {
 863         bn = NULL;
 864     }
 865     assert(b->bh.bsize < 0);
 866
 867     /*  Back pointer in next buffer must be zero, indicating the
 868         same thing: */
 869
 870     assert(BH((char *) b - b->bh.bsize)->prevfree == 0);
 871
 872 #ifdef BufStats
 873     totalloc += b->bh.bsize;
 874     assert(totalloc >= 0);
 875 #endif
 876
 877     /* If the back link is nonzero, the previous buffer is free.  */
 878
 879     if (b->bh.prevfree != 0) {
 880
 881         /* The previous buffer is free.  Consolidate this buffer  with  it
 882            by  adding  the  length  of  this  buffer  to the previous free
 883            buffer.  Note that we subtract the size  in  the  buffer  being
 884            released,  since  it's  negative to indicate that the buffer is
 885            allocated. */
 886
 887         register bufsize size = b->bh.bsize;
 888
 889         /* Make the previous buffer the one we're working on. */
 890         assert(BH((char *) b - b->bh.prevfree)->bsize == b->bh.prevfree);
 891         b = BFH(((char *) b) - b->bh.prevfree);
 892         b->bh.bsize -= size;
 893     } else {
 894
 895         /* The previous buffer isn't allocated.  Insert this buffer
 896            on the free list as an isolated free block. */
 897
 898         assert(freelist.ql.blink->ql.flink == &freelist);
 899         assert(freelist.ql.flink->ql.blink == &freelist);
 900         b->ql.flink = &freelist;
 901         b->ql.blink = freelist.ql.blink;
 902         freelist.ql.blink = b;
 903         b->ql.blink->ql.flink = b;
 904         b->bh.bsize = -b->bh.bsize;
 905     }
 906
 907     /* Now we look at the next buffer in memory, located by advancing from
 908        the  start  of  this  buffer  by its size, to see if that buffer is
 909        free.  If it is, we combine  this  buffer  with  the  next  one  in
 910        memory, dechaining the second buffer from the free list. */
 911
 912     bn =  BFH(((char *) b) + b->bh.bsize);
 913     if (bn->bh.bsize > 0) {
 914
 915         /* The buffer is free.  Remove it from the free list and add
 916            its size to that of our buffer. */
 917
 918         assert(BH((char *) bn + bn->bh.bsize)->prevfree == bn->bh.bsize);
 919         assert(bn->ql.blink->ql.flink == bn);
 920         assert(bn->ql.flink->ql.blink == bn);
 921         bn->ql.blink->ql.flink = bn->ql.flink;
 922         bn->ql.flink->ql.blink = bn->ql.blink;
 923         b->bh.bsize += bn->bh.bsize;
 924
 925         /* Finally,  advance  to   the  buffer  that   follows  the  newly
 926            consolidated free block.  We must set its  backpointer  to  the
 927            head  of  the  consolidated free block.  We know the next block
 928            must be an allocated block because the process of recombination
 929            guarantees  that  two  free  blocks will never be contiguous in
 930            memory.  */
 931
 932         bn = BFH(((char *) b) + b->bh.bsize);
 933     }
 934 #ifdef FreeWipe
 935     V memset(((char *) b) + sizeof(struct bfhead), 0x55,
 936             (MemSize) (b->bh.bsize - sizeof(struct bfhead)));
 937 #endif
 938     assert(bn->bh.bsize < 0);
 939
 940     /* The next buffer is allocated.  Set the backpointer in it  to  point
 941        to this buffer; the previous free buffer in memory. */
 942
 943     bn->bh.prevfree = b->bh.bsize;
 944
 945 #ifdef BECtl
 946
 947     /*  If  a  block-release function is defined, and this free buffer
 948         constitutes the entire block, release it.  Note that  pool_len
 949         is  defined  in  such a way that the test will fail unless all
 950         pool blocks are the same size.  */
 951
 952     if (relfcn != NULL &&
 953         ((bufsize) b->bh.bsize) == (pool_len - sizeof(struct bhead))) {
 954
 955         assert(b->bh.prevfree == 0);
 956         assert(BH((char *) b + b->bh.bsize)->bsize == ESent);
 957         assert(BH((char *) b + b->bh.bsize)->prevfree == b->bh.bsize);
 958         /*  Unlink the buffer from the free list  */
 959         b->ql.blink->ql.flink = b->ql.flink;
 960         b->ql.flink->ql.blink = b->ql.blink;
 961
 962         (*relfcn)(b);
 963 #ifdef BufStats
 964         numprel++;                    /* Nr of expansion block releases */
 965         numpblk--;                    /* Total number of blocks */
 966         assert(numpblk == numpget - numprel);
 967 #endif /* BufStats */
 968     }
 969 #endif /* BECtl */
 970 }
 971
 972 #ifdef BECtl
 973
 974 /*  BECTL  --  Establish automatic pool expansion control  */
 975
 976 void bectl(compact, acquire, release, pool_incr)
 977   int (*compact) _((bufsize sizereq, int sequence));
 978   void *(*acquire) _((bufsize size));
 979   void (*release) _((void *buf));
 980   bufsize pool_incr;
 981 {
 982     compfcn = compact;
 983     acqfcn = acquire;
 984     relfcn = release;
 985     exp_incr = pool_incr;
 986 }
 987 #endif
 988
 989 /*  BPOOL  --  Add a region of memory to the buffer pool.  */
 990
 991 void bpool(buf, len)
 992   void *buf;
 993   bufsize len;
 994 {
 995     struct bfhead *b = BFH(buf);
 996     struct bhead *bn;
 997
 998 #ifdef SizeQuant
 999     len &= ~(SizeQuant - 1);
1000 #endif
1001 #ifdef BECtl
1002     if (pool_len == 0) {
1003         pool_len = len;
1004     } else if (len != pool_len) {
1005         pool_len = -1;
1006     }
1007 #ifdef BufStats
1008     numpget++;                        /* Number of block acquisitions */
1009     numpblk++;                        /* Number of blocks total */
1010     assert(numpblk == numpget - numprel);
1011 #endif /* BufStats */
1012 #endif /* BECtl */
1013
1014     /* Since the block is initially occupied by a single free  buffer,
1015        it  had  better  not  be  (much) larger than the largest buffer
1016        whose size we can store in bhead.bsize. */
1017
1018     assert(len - sizeof(struct bhead) <= -((bufsize) ESent + 1));
1019
1020     /* Clear  the  backpointer at  the start of the block to indicate that
1021        there  is  no  free  block  prior  to  this   one.    That   blocks
1022        recombination when the first block in memory is released. */
1023
1024     b->bh.prevfree = 0;
1025
1026     /* Chain the new block to the free list. */
1027
1028     assert(freelist.ql.blink->ql.flink == &freelist);
1029     assert(freelist.ql.flink->ql.blink == &freelist);
1030     b->ql.flink = &freelist;
1031     b->ql.blink = freelist.ql.blink;
1032     freelist.ql.blink = b;
1033     b->ql.blink->ql.flink = b;
1034
1035     /* Create a dummy allocated buffer at the end of the pool.  This dummy
1036        buffer is seen when a buffer at the end of the pool is released and
1037        blocks  recombination  of  the last buffer with the dummy buffer at
1038        the end.  The length in the dummy buffer  is  set  to  the  largest
1039        negative  number  to  denote  the  end  of  the pool for diagnostic
1040        routines (this specific value is  not  counted  on  by  the  actual
1041        allocation and release functions). */
1042
1043     len -= sizeof(struct bhead);
1044     b->bh.bsize = (bufsize) len;
1045 #ifdef FreeWipe
1046     V memset(((char *) b) + sizeof(struct bfhead), 0x55,
1047              (MemSize) (len - sizeof(struct bfhead)));
1048 #endif
1049     bn = BH(((char *) b) + len);
1050     bn->prevfree = (bufsize) len;
1051     /* Definition of ESent assumes two's complement! */
1052     assert((~0) == -1);
1053     bn->bsize = ESent;
1054 }
1055
1056 #ifdef BufStats
1057
1058 /*  BSTATS  --  Return buffer allocation free space statistics.  */
1059
1060 void bstats(curalloc, totfree, maxfree, nget, nrel)
1061   bufsize *curalloc, *totfree, *maxfree;
1062   long *nget, *nrel;
1063 {
1064     struct bfhead *b = freelist.ql.flink;
1065
1066     *nget = numget;
1067     *nrel = numrel;
1068     *curalloc = totalloc;
1069     *totfree = 0;
1070     *maxfree = -1;
1071     while (b != &freelist) {
1072         assert(b->bh.bsize > 0);
1073         *totfree += b->bh.bsize;
1074         if (b->bh.bsize > *maxfree) {
1075             *maxfree = b->bh.bsize;
1076         }
1077         b = b->ql.flink;              /* Link to next buffer */
1078     }
1079 }
1080
1081 #ifdef BECtl
1082
1083 /*  BSTATSE  --  Return extended statistics  */
1084
1085 void bstatse(pool_incr, npool, npget, nprel, ndget, ndrel)
1086   bufsize *pool_incr;
1087   long *npool, *npget, *nprel, *ndget, *ndrel;
1088 {
1089     *pool_incr = (pool_len < 0) ? -exp_incr : exp_incr;
1090     *npool = numpblk;
1091     *npget = numpget;
1092     *nprel = numprel;
1093     *ndget = numdget;
1094     *ndrel = numdrel;
1095 }
1096 #endif /* BECtl */
1097 #endif /* BufStats */
1098
1099 #ifdef DumpData
1100
1101 /*  BUFDUMP  --  Dump the data in a buffer.  This is called with the  user
1102                  data pointer, and backs up to the buffer header.  It will
1103                  dump either a free block or an allocated one.  */
1104
1105 void bufdump(buf)
1106   void *buf;
1107 {
1108     struct bfhead *b;
1109     uchar_t *bdump;
1110     bufsize bdlen;
1111
1112     b = BFH(((char *) buf) - sizeof(struct bhead));
1113     assert(b->bh.bsize != 0);
1114     if (b->bh.bsize < 0) {
1115         bdump = (uchar_t *) buf;
1116         bdlen = (-b->bh.bsize) - sizeof(struct bhead);
1117     } else {
1118         bdump = (uchar_t *) (((char *) b) + sizeof(struct bfhead));
1119         bdlen = b->bh.bsize - sizeof(struct bfhead);
1120     }
1121
1122     while (bdlen > 0) {
1123         int i, dupes = 0;
1124         bufsize l = bdlen;
1125         char bhex[50], bascii[20];
1126
1127         if (l > 16) {
1128             l = 16;
1129         }
1130
1131         for (i = 0; i < l; i++) {
1132             V sprintf(bhex + i * 3, "%02X ", bdump[i]);
1133             bascii[i] = isprint(bdump[i]) ? bdump[i] : ' ';
1134         }
1135         bascii[i] = 0;
1136         V printf("%-48s   %s\n", bhex, bascii);
1137         bdump += l;
1138         bdlen -= l;
1139         while ((bdlen > 16) && (memcmp((char *) (bdump - 16),
1140                                        (char *) bdump, 16) == 0)) {
1141             dupes++;
1142             bdump += 16;
1143             bdlen -= 16;
1144         }
1145         if (dupes > 1) {
1146             V printf(
1147                 "     (%d lines [%d bytes] identical to above line skipped)\n",
1148                 dupes, dupes * 16);
1149         } else if (dupes == 1) {
1150             bdump -= 16;
1151             bdlen += 16;
1152         }
1153     }
1154 }
1155 #endif
1156
1157 #ifdef BufDump
1158
1159 /*  BPOOLD  --  Dump a buffer pool.  The buffer headers are always listed.
1160                 If DUMPALLOC is nonzero, the contents of allocated buffers
1161                 are  dumped.   If  DUMPFREE  is  nonzero,  free blocks are
1162                 dumped as well.  If FreeWipe  checking  is  enabled,  free
1163                 blocks  which  have  been clobbered will always be dumped. */
1164
1165 void bpoold(buf, dumpalloc, dumpfree)
1166   void *buf;
1167   int dumpalloc, dumpfree;
1168 {
1169     struct bfhead *b = BFH(buf);
1170
1171     while (b->bh.bsize != ESent) {
1172         bufsize bs = b->bh.bsize;
1173
1174         if (bs < 0) {
1175             bs = -bs;
1176             V printf("Allocated buffer: size %6ld bytes.\n", (long) bs);
1177             if (dumpalloc) {
1178                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1179             }
1180         } else {
1181             char *lerr = "";
1182
1183             assert(bs > 0);
1184             if ((b->ql.blink->ql.flink != b) ||
1185                 (b->ql.flink->ql.blink != b)) {
1186                 lerr = "  (Bad free list links)";
1187             }
1188             V printf("Free block:       size %6ld bytes.%s\n",
1189                 (long) bs, lerr);
1190 #ifdef FreeWipe
1191             lerr = ((char *) b) + sizeof(struct bfhead);
1192             if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1193                 (memcmp(lerr, lerr + 1,
1194                   (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1195                 V printf(
1196                     "(Contents of above free block have been overstored.)\n");
1197                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1198             } else
1199 #endif
1200             if (dumpfree) {
1201                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1202             }
1203         }
1204         b = BFH(((char *) b) + bs);
1205     }
1206 }
1207 #endif /* BufDump */
1208
1209 #ifdef BufValid
1210
1211 /*  BPOOLV  --  Validate a buffer pool.  If NDEBUG isn't defined,
1212                 any error generates an assertion failure.  */
1213
1214 int bpoolv(buf)
1215   void *buf;
1216 {
1217     struct bfhead *b = BFH(buf);
1218
1219     while (b->bh.bsize != ESent) {
1220         bufsize bs = b->bh.bsize;
1221
1222         if (bs < 0) {
1223             bs = -bs;
1224         } else {
1225             char *lerr = "";
1226
1227             assert(bs > 0);
1228             if (bs <= 0) {
1229                 return 0;
1230             }
1231             if ((b->ql.blink->ql.flink != b) ||
1232                 (b->ql.flink->ql.blink != b)) {
1233                 V printf("Free block: size %6ld bytes.  (Bad free list links)\n",
1234                      (long) bs);
1235                 assert(0);
1236                 return 0;
1237             }
1238 #ifdef FreeWipe
1239             lerr = ((char *) b) + sizeof(struct bfhead);
1240             if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1241                 (memcmp(lerr, lerr + 1,
1242                   (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1243                 V printf(
1244                     "(Contents of above free block have been overstored.)\n");
1245                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1246                 assert(0);
1247                 return 0;
1248             }
1249 #endif
1250         }
1251         b = BFH(((char *) b) + bs);
1252     }
1253     return 1;
1254 }
1255 #endif /* BufValid */
1256
1257         /***********************\
1258         *                       *
1259         * Built-in test program *
1260         *                       *
1261         \***********************/
1262
1263 #ifdef TestProg
1264
1265 #define Repeatable  1                 /* Repeatable pseudorandom sequence */
1266                                       /* If Repeatable is not defined, a
1267                                          time-seeded pseudorandom sequence
1268                                          is generated, exercising BGET with
1269                                          a different pattern of calls on each
1270                                          run. */
1271 #define OUR_RAND                      /* Use our own built-in version of
1272                                          rand() to guarantee the test is
1273                                          100% repeatable. */
1274
1275 #ifdef BECtl
1276 #define PoolSize    300000            /* Test buffer pool size */
1277 #else
1278 #define PoolSize    50000             /* Test buffer pool size */
1279 #endif
1280 #define ExpIncr     32768             /* Test expansion block size */
1281 #define CompactTries 10               /* Maximum tries at compacting */
1282
1283 #define dumpAlloc   0                 /* Dump allocated buffers ? */
1284 #define dumpFree    0                 /* Dump free buffers ? */
1285
1286 #ifndef Repeatable
1287 extern long time();
1288 #endif
1289
1290 extern char *malloc();
1291 extern int free _((char *));
1292
1293 static char *bchain = NULL;           /* Our private buffer chain */
1294 static char *bp = NULL;               /* Our initial buffer pool */
1295
1296 #include <math.h>
1297
1298 #ifdef OUR_RAND
1299
1300 static ulong_t int next = 1;
1301
1302 /* Return next random integer */
1303
1304 int rand()
1305 {
1306         next = next * 1103515245L + 12345;
1307         return (uint_t) (next / 65536L) % 32768L;
1308 }
1309
1310 /* Set seed for random generator */
1311
1312 void srand(seed)
1313   uint_t seed;
1314 {
1315         next = seed;
1316 }
1317 #endif
1318
1319 /*  STATS  --  Edit statistics returned by bstats() or bstatse().  */
1320
1321 static void stats(when)
1322   char *when;
1323 {
1324     bufsize cural, totfree, maxfree;
1325     long nget, nfree;
1326 #ifdef BECtl
1327     bufsize pincr;
1328     long totblocks, npget, nprel, ndget, ndrel;
1329 #endif
1330
1331     bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1332     V printf(
1333         "%s: %ld gets, %ld releases.  %ld in use, %ld free, largest = %ld\n",
1334         when, nget, nfree, (long) cural, (long) totfree, (long) maxfree);
1335 #ifdef BECtl
1336     bstatse(&pincr, &totblocks, &npget, &nprel, &ndget, &ndrel);
1337     V printf(
1338          "  Blocks: size = %ld, %ld (%ld bytes) in use, %ld gets, %ld frees\n",
1339          (long)pincr, totblocks, pincr * totblocks, npget, nprel);
1340     V printf("  %ld direct gets, %ld direct frees\n", ndget, ndrel);
1341 #endif /* BECtl */
1342 }
1343
1344 #ifdef BECtl
1345 static int protect = 0;               /* Disable compaction during bgetr() */
1346
1347 /*  BCOMPACT  --  Compaction call-back function.  */
1348
1349 static int bcompact(bsize, seq)
1350   bufsize bsize;
1351   int seq;
1352 {
1353 #ifdef CompactTries
1354     char *bc = bchain;
1355     int i = rand() & 0x3;
1356
1357 #ifdef COMPACTRACE
1358     V printf("Compaction requested.  %ld bytes needed, sequence %d.\n",
1359         (long) bsize, seq);
1360 #endif
1361
1362     if (protect || (seq > CompactTries)) {
1363 #ifdef COMPACTRACE
1364         V printf("Compaction gave up.\n");
1365 #endif
1366         return 0;
1367     }
1368
1369     /* Based on a random cast, release a random buffer in the list
1370        of allocated buffers. */
1371
1372     while (i > 0 && bc != NULL) {
1373         bc = *((char **) bc);
1374         i--;
1375     }
1376     if (bc != NULL) {
1377         char *fb;
1378
1379         fb = *((char **) bc);
1380         if (fb != NULL) {
1381             *((char **) bc) = *((char **) fb);
1382             brel((void *) fb);
1383             return 1;
1384         }
1385     }
1386
1387 #ifdef COMPACTRACE
1388     V printf("Compaction bailed out.\n");
1389 #endif
1390 #endif /* CompactTries */
1391     return 0;
1392 }
1393
1394 /*  BEXPAND  --  Expand pool call-back function.  */
1395
1396 static void *bexpand(size)
1397   bufsize size;
1398 {
1399     void *np = NULL;
1400     bufsize cural, totfree, maxfree;
1401     long nget, nfree;
1402
1403     /* Don't expand beyond the total allocated size given by PoolSize. */
1404
1405     bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1406
1407     if (cural < PoolSize) {
1408         np = (void *) malloc((unsigned) size);
1409     }
1410 #ifdef EXPTRACE
1411     V printf("Expand pool by %ld -- %s.\n", (long) size,
1412         np == NULL ? "failed" : "succeeded");
1413 #endif
1414     return np;
1415 }
1416
1417 /*  BSHRINK  --  Shrink buffer pool call-back function.  */
1418
1419 static void bshrink(buf)
1420   void *buf;
1421 {
1422     if (((char *) buf) == bp) {
1423 #ifdef EXPTRACE
1424         V printf("Initial pool released.\n");
1425 #endif
1426         bp = NULL;
1427     }
1428 #ifdef EXPTRACE
1429     V printf("Shrink pool.\n");
1430 #endif
1431     free((char *) buf);
1432 }
1433
1434 #endif /* BECtl */
1435
1436 /*  Restrict buffer requests to those large enough to contain our pointer and
1437     small enough for the CPU architecture.  */
1438
1439 static bufsize blimit(bs)
1440   bufsize bs;
1441 {
1442     if (bs < sizeof(char *)) {
1443         bs = sizeof(char *);
1444     }
1445
1446     /* This is written out in this ugly fashion because the
1447        cool expression in sizeof(int) that auto-configured
1448        to any length int befuddled some compilers. */
1449
1450     if (sizeof(int) == 2) {
1451         if (bs > 32767) {
1452             bs = 32767;
1453         }
1454     } else {
1455         if (bs > 200000) {
1456             bs = 200000;
1457         }
1458     }
1459     return bs;
1460 }
1461
1462 int main()
1463 {
1464     int i;
1465     double x;
1466
1467     /* Seed the random number generator.  If Repeatable is defined, we
1468        always use the same seed.  Otherwise, we seed from the clock to
1469        shake things up from run to run. */
1470
1471 #ifdef Repeatable
1472     V srand(1234);
1473 #else
1474     V srand((int) time((long *) NULL));
1475 #endif
1476
1477     /*  Compute x such that pow(x, p) ranges between 1 and 4*ExpIncr as
1478         p ranges from 0 to ExpIncr-1, with a concentration in the lower
1479         numbers.  */
1480
1481     x = 4.0 * ExpIncr;
1482     x = log(x);
1483     x = exp(log(4.0 * ExpIncr) / (ExpIncr - 1.0));
1484
1485 #ifdef BECtl
1486     bectl(bcompact, bexpand, bshrink, (bufsize) ExpIncr);
1487     bp = malloc(ExpIncr);
1488     assert(bp != NULL);
1489     bpool((void *) bp, (bufsize) ExpIncr);
1490 #else
1491     bp = malloc(PoolSize);
1492     assert(bp != NULL);
1493     bpool((void *) bp, (bufsize) PoolSize);
1494 #endif
1495
1496     stats("Create pool");
1497     V bpoolv((void *) bp);
1498     bpoold((void *) bp, dumpAlloc, dumpFree);
1499
1500     for (i = 0; i < TestProg; i++) {
1501         char *cb;
1502         bufsize bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1503
1504         assert(bs <= (((bufsize) 4) * ExpIncr));
1505         bs = blimit(bs);
1506         if (rand() & 0x400) {
1507             cb = (char *) bgetz(bs);
1508         } else {
1509             cb = (char *) bget(bs);
1510         }
1511         if (cb == NULL) {
1512 #ifdef EasyOut
1513             break;
1514 #else
1515             char *bc = bchain;
1516
1517             if (bc != NULL) {
1518                 char *fb;
1519
1520                 fb = *((char **) bc);
1521                 if (fb != NULL) {
1522                     *((char **) bc) = *((char **) fb);
1523                     brel((void *) fb);
1524                 }
1525                 continue;
1526             }
1527 #endif
1528         }
1529         *((char **) cb) = (char *) bchain;
1530         bchain = cb;
1531
1532         /* Based on a random cast, release a random buffer in the list
1533            of allocated buffers. */
1534
1535         if ((rand() & 0x10) == 0) {
1536             char *bc = bchain;
1537             int i = rand() & 0x3;
1538
1539             while (i > 0 && bc != NULL) {
1540                 bc = *((char **) bc);
1541                 i--;
1542             }
1543             if (bc != NULL) {
1544                 char *fb;
1545
1546                 fb = *((char **) bc);
1547                 if (fb != NULL) {
1548                     *((char **) bc) = *((char **) fb);
1549                     brel((void *) fb);
1550                 }
1551             }
1552         }
1553
1554         /* Based on a random cast, reallocate a random buffer in the list
1555            to a random size */
1556
1557         if ((rand() & 0x20) == 0) {
1558             char *bc = bchain;
1559             int i = rand() & 0x3;
1560
1561             while (i > 0 && bc != NULL) {
1562                 bc = *((char **) bc);
1563                 i--;
1564             }
1565             if (bc != NULL) {
1566                 char *fb;
1567
1568                 fb = *((char **) bc);
1569                 if (fb != NULL) {
1570                     char *newb;
1571
1572                     bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1573                     bs = blimit(bs);
1574 #ifdef BECtl
1575                     protect = 1;      /* Protect against compaction */
1576 #endif
1577                     newb = (char *) bgetr((void *) fb, bs);
1578 #ifdef BECtl
1579                     protect = 0;
1580 #endif
1581                     if (newb != NULL) {
1582                         *((char **) bc) = newb;
1583                     }
1584                 }
1585             }
1586         }
1587     }
1588     stats("\nAfter allocation");
1589     if (bp != NULL) {
1590         V bpoolv((void *) bp);
1591         bpoold((void *) bp, dumpAlloc, dumpFree);
1592     }
1593
1594     while (bchain != NULL) {
1595         char *buf = bchain;
1596
1597         bchain = *((char **) buf);
1598         brel((void *) buf);
1599     }
1600     stats("\nAfter release");
1601 #ifndef BECtl
1602     if (bp != NULL) {
1603         V bpoolv((void *) bp);
1604         bpoold((void *) bp, dumpAlloc, dumpFree);
1605     }
1606 #endif
1607
1608     return 0;
1609 }
1610 #endif