test/geekos_test_vm/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
 530
 531
 532
 533 #ifdef BufStats
 534 static bufsize totalloc = 0;          /* Total space currently allocated */
 535 static long numget = 0, numrel = 0;   /* Number of bget() and brel() calls */
 536 #ifdef BECtl
 537 static long numpblk = 0;              /* Number of pool blocks */
 538 static long numpget = 0, numprel = 0; /* Number of block gets and rels */
 539 static long numdget = 0, numdrel = 0; /* Number of direct gets and rels */
 540 #endif /* BECtl */
 541 #endif /* BufStats */
 542
 543 #ifdef BECtl
 544
 545 /* Automatic expansion block management functions */
 546
 547 static int (*compfcn) _((bufsize sizereq, int sequence)) = NULL;
 548 static void *(*acqfcn) _((bufsize size)) = NULL;
 549 static void (*relfcn) _((void *buf)) = NULL;
 550
 551 static bufsize exp_incr = 0;          /* Expansion block size */
 552 static bufsize pool_len = 0;          /* 0: no bpool calls have been made
 553                                          -1: not all pool blocks are
 554                                              the same size
 555                                          >0: (common) block size for all
 556                                              bpool calls made so far
 557                                       */
 558 #endif
 559
 560 /*  Minimum allocation quantum: */
 561
 562 #define QLSize  (sizeof(struct qlinks))
 563 #define SizeQ   ((SizeQuant > QLSize) ? SizeQuant : QLSize)
 564
 565 #define V   (void)                    /* To denote unwanted returned values */
 566
 567 /* End sentinel: value placed in bsize field of dummy block delimiting
 568    end of pool block.  The most negative number which will  fit  in  a
 569    bufsize, defined in a way that the compiler will accept. */
 570
 571 #define ESent   ((bufsize) (-(((1L << (sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))
 572
 573 /*  BGET  --  Allocate a buffer.  */
 574
 575 void *bget(requested_size)
 576   bufsize requested_size;
 577 {
 578     bufsize size = requested_size;
 579     struct bfhead *b;
 580 #ifdef BestFit
 581     struct bfhead *best;
 582 #endif
 583     void *buf;
 584 #ifdef BECtl
 585     int compactseq = 0;
 586 #endif
 587
 588     assert(size > 0);
 589
 590     if (size < SizeQ) {               /* Need at least room for the */
 591         size = SizeQ;                 /*    queue links.  */
 592     }
 593 #ifdef SizeQuant
 594 #if SizeQuant > 1
 595     size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1));
 596 #endif
 597 #endif
 598
 599     size += sizeof(struct bhead);     /* Add overhead in allocated buffer
 600                                          to size required. */
 601
 602 #ifdef BECtl
 603     /* If a compact function was provided in the call to bectl(), wrap
 604        a loop around the allocation process  to  allow  compaction  to
 605        intervene in case we don't find a suitable buffer in the chain. */
 606
 607     while (1) {
 608 #endif
 609         b = freelist.ql.flink;
 610 #ifdef BestFit
 611         best = &freelist;
 612 #endif
 613
 614
 615         /* Scan the free list searching for the first buffer big enough
 616            to hold the requested size buffer. */
 617
 618 #ifdef BestFit
 619         while (b != &freelist) {
 620             if (b->bh.bsize >= size) {
 621                 if ((best == &freelist) || (b->bh.bsize < best->bh.bsize)) {
 622                     best = b;
 623                 }
 624             }
 625             b = b->ql.flink;              /* Link to next buffer */
 626         }
 627         b = best;
 628 #endif /* BestFit */
 629
 630         while (b != &freelist) {
 631             if ((bufsize) b->bh.bsize >= size) {
 632
 633                 /* Buffer  is big enough to satisfy  the request.  Allocate it
 634                    to the caller.  We must decide whether the buffer is  large
 635                    enough  to  split  into  the part given to the caller and a
 636                    free buffer that remains on the free list, or  whether  the
 637                    entire  buffer  should  be  removed  from the free list and
 638                    given to the caller in its entirety.   We  only  split  the
 639                    buffer if enough room remains for a header plus the minimum
 640                    quantum of allocation. */
 641
 642                 if ((b->bh.bsize - size) > (SizeQ + (sizeof(struct bhead)))) {
 643                     struct bhead *ba, *bn;
 644
 645                     ba = BH(((char *) b) + (b->bh.bsize - size));
 646                     bn = BH(((char *) ba) + size);
 647                     assert(bn->prevfree == b->bh.bsize);
 648                     /* Subtract size from length of free block. */
 649                     b->bh.bsize -= size;
 650                     /* Link allocated buffer to the previous free buffer. */
 651                     ba->prevfree = b->bh.bsize;
 652                     /* Plug negative size into user buffer. */
 653                     ba->bsize = -(bufsize) size;
 654                     /* Mark buffer after this one not preceded by free block. */
 655                     bn->prevfree = 0;
 656
 657 #ifdef BufStats
 658                     totalloc += size;
 659                     numget++;             /* Increment number of bget() calls */
 660 #endif
 661                     buf = (void *) ((((char *) ba) + sizeof(struct bhead)));
 662                     return buf;
 663                 } else {
 664                     struct bhead *ba;
 665
 666                     ba = BH(((char *) b) + b->bh.bsize);
 667                     assert(ba->prevfree == b->bh.bsize);
 668
 669                     /* The buffer isn't big enough to split.  Give  the  whole
 670                        shebang to the caller and remove it from the free list. */
 671
 672                     assert(b->ql.blink->ql.flink == b);
 673                     assert(b->ql.flink->ql.blink == b);
 674                     b->ql.blink->ql.flink = b->ql.flink;
 675                     b->ql.flink->ql.blink = b->ql.blink;
 676
 677 #ifdef BufStats
 678                     totalloc += b->bh.bsize;
 679                     numget++;             /* Increment number of bget() calls */
 680 #endif
 681                     /* Negate size to mark buffer allocated. */
 682                     b->bh.bsize = -(b->bh.bsize);
 683
 684                     /* Zero the back pointer in the next buffer in memory
 685                        to indicate that this buffer is allocated. */
 686                     ba->prevfree = 0;
 687
 688                     /* Give user buffer starting at queue links. */
 689                     buf =  (void *) &(b->ql);
 690                     return buf;
 691                 }
 692             }
 693             b = b->ql.flink;              /* Link to next buffer */
 694         }
 695 #ifdef BECtl
 696
 697         /* We failed to find a buffer.  If there's a compact  function
 698            defined,  notify  it  of the size requested.  If it returns
 699            true, try the allocation again. */
 700
 701         if ((compfcn == NULL) || (!(*compfcn)(size, ++compactseq))) {
 702             break;
 703         }
 704     }
 705
 706     /* No buffer available with requested size free. */
 707
 708     /* Don't give up yet -- look in the reserve supply. */
 709
 710     if (acqfcn != NULL) {
 711         if (size > exp_incr - sizeof(struct bhead)) {
 712
 713             /* Request  is  too  large  to  fit in a single expansion
 714                block.  Try to satisy it by a direct buffer acquisition. */
 715
 716             struct bdhead *bdh;
 717
 718             size += sizeof(struct bdhead) - sizeof(struct bhead);
 719             if ((bdh = BDH((*acqfcn)((bufsize) size))) != NULL) {
 720
 721                 /*  Mark the buffer special by setting the size field
 722                     of its header to zero.  */
 723                 bdh->bh.bsize = 0;
 724                 bdh->bh.prevfree = 0;
 725                 bdh->tsize = size;
 726 #ifdef BufStats
 727                 totalloc += size;
 728                 numget++;             /* Increment number of bget() calls */
 729                 numdget++;            /* Direct bget() call count */
 730 #endif
 731                 buf =  (void *) (bdh + 1);
 732                 return buf;
 733             }
 734
 735         } else {
 736
 737             /*  Try to obtain a new expansion block */
 738
 739             void *newpool;
 740
 741             if ((newpool = (*acqfcn)((bufsize) exp_incr)) != NULL) {
 742                 bpool(newpool, exp_incr);
 743                 buf =  bget(requested_size);  /* This can't, I say, can't
 744                                                  get into a loop. */
 745                 return buf;
 746             }
 747         }
 748     }
 749
 750     /*  Still no buffer available */
 751
 752 #endif /* BECtl */
 753
 754     return NULL;
 755 }
 756
 757 /*  BGETZ  --  Allocate a buffer and clear its contents to zero.  We clear
 758                the  entire  contents  of  the buffer to zero, not just the
 759                region requested by the caller. */
 760
 761 void *bgetz(size)
 762   bufsize size;
 763 {
 764     char *buf = (char *) bget(size);
 765
 766     if (buf != NULL) {
 767         struct bhead *b;
 768         bufsize rsize;
 769
 770         b = BH(buf - sizeof(struct bhead));
 771         rsize = -(b->bsize);
 772         if (rsize == 0) {
 773             struct bdhead *bd;
 774
 775             bd = BDH(buf - sizeof(struct bdhead));
 776             rsize = bd->tsize - sizeof(struct bdhead);
 777         } else {
 778             rsize -= sizeof(struct bhead);
 779         }
 780         assert(rsize >= size);
 781         V memset(buf, 0, (MemSize) rsize);
 782     }
 783     return ((void *) buf);
 784 }
 785
 786 /*  BGETR  --  Reallocate a buffer.  This is a minimal implementation,
 787                simply in terms of brel()  and  bget().   It  could  be
 788                enhanced to allow the buffer to grow into adjacent free
 789                blocks and to avoid moving data unnecessarily.  */
 790
 791 void *bgetr(buf, size)
 792   void *buf;
 793   bufsize size;
 794 {
 795     void *nbuf;
 796     bufsize osize;                    /* Old size of buffer */
 797     struct bhead *b;
 798
 799     if ((nbuf = bget(size)) == NULL) { /* Acquire new buffer */
 800         return NULL;
 801     }
 802     if (buf == NULL) {
 803         return nbuf;
 804     }
 805     b = BH(((char *) buf) - sizeof(struct bhead));
 806     osize = -b->bsize;
 807 #ifdef BECtl
 808     if (osize == 0) {
 809         /*  Buffer acquired directly through acqfcn. */
 810         struct bdhead *bd;
 811
 812         bd = BDH(((char *) buf) - sizeof(struct bdhead));
 813         osize = bd->tsize - sizeof(struct bdhead);
 814     } else
 815 #endif
 816         osize -= sizeof(struct bhead);
 817     assert(osize > 0);
 818     V memcpy((char *) nbuf, (char *) buf, /* Copy the data */
 819              (MemSize) ((size < osize) ? size : osize));
 820     brel(buf);
 821     return nbuf;
 822 }
 823
 824 /*  BREL  --  Release a buffer.  */
 825
 826 void brel(buf)
 827   void *buf;
 828 {
 829     struct bfhead *b, *bn;
 830
 831     b = BFH(((char *) buf) - sizeof(struct bhead));
 832 #ifdef BufStats
 833     numrel++;                         /* Increment number of brel() calls */
 834 #endif
 835     assert(buf != NULL);
 836
 837 #ifdef BECtl
 838     if (b->bh.bsize == 0) {           /* Directly-acquired buffer? */
 839         struct bdhead *bdh;
 840
 841         bdh = BDH(((char *) buf) - sizeof(struct bdhead));
 842         assert(b->bh.prevfree == 0);
 843 #ifdef BufStats
 844         totalloc -= bdh->tsize;
 845         assert(totalloc >= 0);
 846         numdrel++;                    /* Number of direct releases */
 847 #endif /* BufStats */
 848 #ifdef FreeWipe
 849         V memset((char *) buf, 0x55,
 850                  (MemSize) (bdh->tsize - sizeof(struct bdhead)));
 851 #endif /* FreeWipe */
 852         assert(relfcn != NULL);
 853         (*relfcn)((void *) bdh);      /* Release it directly. */
 854         return;
 855     }
 856 #endif /* BECtl */
 857
 858     /* Buffer size must be negative, indicating that the buffer is
 859        allocated. */
 860
 861     if (b->bh.bsize >= 0) {
 862         bn = NULL;
 863     }
 864     assert(b->bh.bsize < 0);
 865
 866     /*  Back pointer in next buffer must be zero, indicating the
 867         same thing: */
 868
 869     assert(BH((char *) b - b->bh.bsize)->prevfree == 0);
 870
 871 #ifdef BufStats
 872     totalloc += b->bh.bsize;
 873     assert(totalloc >= 0);
 874 #endif
 875
 876     /* If the back link is nonzero, the previous buffer is free.  */
 877
 878     if (b->bh.prevfree != 0) {
 879
 880         /* The previous buffer is free.  Consolidate this buffer  with  it
 881            by  adding  the  length  of  this  buffer  to the previous free
 882            buffer.  Note that we subtract the size  in  the  buffer  being
 883            released,  since  it's  negative to indicate that the buffer is
 884            allocated. */
 885
 886         register bufsize size = b->bh.bsize;
 887
 888         /* Make the previous buffer the one we're working on. */
 889         assert(BH((char *) b - b->bh.prevfree)->bsize == b->bh.prevfree);
 890         b = BFH(((char *) b) - b->bh.prevfree);
 891         b->bh.bsize -= size;
 892     } else {
 893
 894         /* The previous buffer isn't allocated.  Insert this buffer
 895            on the free list as an isolated free block. */
 896
 897         assert(freelist.ql.blink->ql.flink == &freelist);
 898         assert(freelist.ql.flink->ql.blink == &freelist);
 899         b->ql.flink = &freelist;
 900         b->ql.blink = freelist.ql.blink;
 901         freelist.ql.blink = b;
 902         b->ql.blink->ql.flink = b;
 903         b->bh.bsize = -b->bh.bsize;
 904     }
 905
 906     /* Now we look at the next buffer in memory, located by advancing from
 907        the  start  of  this  buffer  by its size, to see if that buffer is
 908        free.  If it is, we combine  this  buffer  with  the  next  one  in
 909        memory, dechaining the second buffer from the free list. */
 910
 911     bn =  BFH(((char *) b) + b->bh.bsize);
 912     if (bn->bh.bsize > 0) {
 913
 914         /* The buffer is free.  Remove it from the free list and add
 915            its size to that of our buffer. */
 916
 917         assert(BH((char *) bn + bn->bh.bsize)->prevfree == bn->bh.bsize);
 918         assert(bn->ql.blink->ql.flink == bn);
 919         assert(bn->ql.flink->ql.blink == bn);
 920         bn->ql.blink->ql.flink = bn->ql.flink;
 921         bn->ql.flink->ql.blink = bn->ql.blink;
 922         b->bh.bsize += bn->bh.bsize;
 923
 924         /* Finally,  advance  to   the  buffer  that   follows  the  newly
 925            consolidated free block.  We must set its  backpointer  to  the
 926            head  of  the  consolidated free block.  We know the next block
 927            must be an allocated block because the process of recombination
 928            guarantees  that  two  free  blocks will never be contiguous in
 929            memory.  */
 930
 931         bn = BFH(((char *) b) + b->bh.bsize);
 932     }
 933 #ifdef FreeWipe
 934     V memset(((char *) b) + sizeof(struct bfhead), 0x55,
 935             (MemSize) (b->bh.bsize - sizeof(struct bfhead)));
 936 #endif
 937     assert(bn->bh.bsize < 0);
 938
 939     /* The next buffer is allocated.  Set the backpointer in it  to  point
 940        to this buffer; the previous free buffer in memory. */
 941
 942     bn->bh.prevfree = b->bh.bsize;
 943
 944 #ifdef BECtl
 945
 946     /*  If  a  block-release function is defined, and this free buffer
 947         constitutes the entire block, release it.  Note that  pool_len
 948         is  defined  in  such a way that the test will fail unless all
 949         pool blocks are the same size.  */
 950
 951     if (relfcn != NULL &&
 952         ((bufsize) b->bh.bsize) == (pool_len - sizeof(struct bhead))) {
 953
 954         assert(b->bh.prevfree == 0);
 955         assert(BH((char *) b + b->bh.bsize)->bsize == ESent);
 956         assert(BH((char *) b + b->bh.bsize)->prevfree == b->bh.bsize);
 957         /*  Unlink the buffer from the free list  */
 958         b->ql.blink->ql.flink = b->ql.flink;
 959         b->ql.flink->ql.blink = b->ql.blink;
 960
 961         (*relfcn)(b);
 962 #ifdef BufStats
 963         numprel++;                    /* Nr of expansion block releases */
 964         numpblk--;                    /* Total number of blocks */
 965         assert(numpblk == numpget - numprel);
 966 #endif /* BufStats */
 967     }
 968 #endif /* BECtl */
 969 }
 970
 971 #ifdef BECtl
 972
 973 /*  BECTL  --  Establish automatic pool expansion control  */
 974
 975 void bectl(compact, acquire, release, pool_incr)
 976   int (*compact) _((bufsize sizereq, int sequence));
 977   void *(*acquire) _((bufsize size));
 978   void (*release) _((void *buf));
 979   bufsize pool_incr;
 980 {
 981     compfcn = compact;
 982     acqfcn = acquire;
 983     relfcn = release;
 984     exp_incr = pool_incr;
 985 }
 986 #endif
 987
 988 /*  BPOOL  --  Add a region of memory to the buffer pool.  */
 989
 990 void bpool(buf, len)
 991   void *buf;
 992   bufsize len;
 993 {
 994     struct bfhead *b = BFH(buf);
 995     struct bhead *bn;
 996
 997 #ifdef SizeQuant
 998     len &= ~(SizeQuant - 1);
 999 #endif
1000 #ifdef BECtl
1001     if (pool_len == 0) {
1002         pool_len = len;
1003     } else if (len != pool_len) {
1004         pool_len = -1;
1005     }
1006 #ifdef BufStats
1007     numpget++;                        /* Number of block acquisitions */
1008     numpblk++;                        /* Number of blocks total */
1009     assert(numpblk == numpget - numprel);
1010 #endif /* BufStats */
1011 #endif /* BECtl */
1012
1013     /* Since the block is initially occupied by a single free  buffer,
1014        it  had  better  not  be  (much) larger than the largest buffer
1015        whose size we can store in bhead.bsize. */
1016
1017     assert(len - sizeof(struct bhead) <= -((bufsize) ESent + 1));
1018
1019     /* Initialize Free list since compile time static initializations appear to be broken */
1020     freelist.bh.prevfree = 0;
1021     freelist.bh.bsize = 0;
1022     freelist.ql.flink = &freelist;
1023     freelist.ql.blink = &freelist;
1024
1025
1026
1027     /* Clear  the  backpointer at  the start of the block to indicate that
1028        there  is  no  free  block  prior  to  this   one.    That   blocks
1029        recombination when the first block in memory is released. */
1030
1031     b->bh.prevfree = 0;
1032
1033     /* Chain the new block to the free list. */
1034
1035     assert(freelist.ql.blink->ql.flink == &freelist);
1036     assert(freelist.ql.flink->ql.blink == &freelist);
1037     b->ql.flink = &freelist;
1038     b->ql.blink = freelist.ql.blink;
1039     freelist.ql.blink = b;
1040     b->ql.blink->ql.flink = b;
1041
1042     /* Create a dummy allocated buffer at the end of the pool.  This dummy
1043        buffer is seen when a buffer at the end of the pool is released and
1044        blocks  recombination  of  the last buffer with the dummy buffer at
1045        the end.  The length in the dummy buffer  is  set  to  the  largest
1046        negative  number  to  denote  the  end  of  the pool for diagnostic
1047        routines (this specific value is  not  counted  on  by  the  actual
1048        allocation and release functions). */
1049
1050     len -= sizeof(struct bhead);
1051     b->bh.bsize = (bufsize) len;
1052 #ifdef FreeWipe
1053     V memset(((char *) b) + sizeof(struct bfhead), 0x55,
1054              (MemSize) (len - sizeof(struct bfhead)));
1055 #endif
1056     bn = BH(((char *) b) + len);
1057     bn->prevfree = (bufsize) len;
1058     /* Definition of ESent assumes two's complement! */
1059     assert((~0) == -1);
1060     bn->bsize = ESent;
1061 }
1062
1063 #ifdef BufStats
1064
1065 /*  BSTATS  --  Return buffer allocation free space statistics.  */
1066
1067 void bstats(curalloc, totfree, maxfree, nget, nrel)
1068   bufsize *curalloc, *totfree, *maxfree;
1069   long *nget, *nrel;
1070 {
1071     struct bfhead *b = freelist.ql.flink;
1072
1073     *nget = numget;
1074     *nrel = numrel;
1075     *curalloc = totalloc;
1076     *totfree = 0;
1077     *maxfree = -1;
1078     while (b != &freelist) {
1079         assert(b->bh.bsize > 0);
1080         *totfree += b->bh.bsize;
1081         if (b->bh.bsize > *maxfree) {
1082             *maxfree = b->bh.bsize;
1083         }
1084         b = b->ql.flink;              /* Link to next buffer */
1085     }
1086 }
1087
1088 #ifdef BECtl
1089
1090 /*  BSTATSE  --  Return extended statistics  */
1091
1092 void bstatse(pool_incr, npool, npget, nprel, ndget, ndrel)
1093   bufsize *pool_incr;
1094   long *npool, *npget, *nprel, *ndget, *ndrel;
1095 {
1096     *pool_incr = (pool_len < 0) ? -exp_incr : exp_incr;
1097     *npool = numpblk;
1098     *npget = numpget;
1099     *nprel = numprel;
1100     *ndget = numdget;
1101     *ndrel = numdrel;
1102 }
1103 #endif /* BECtl */
1104 #endif /* BufStats */
1105
1106 #ifdef DumpData
1107
1108 /*  BUFDUMP  --  Dump the data in a buffer.  This is called with the  user
1109                  data pointer, and backs up to the buffer header.  It will
1110                  dump either a free block or an allocated one.  */
1111
1112 void bufdump(buf)
1113   void *buf;
1114 {
1115     struct bfhead *b;
1116     uchar_t *bdump;
1117     bufsize bdlen;
1118
1119     b = BFH(((char *) buf) - sizeof(struct bhead));
1120     assert(b->bh.bsize != 0);
1121     if (b->bh.bsize < 0) {
1122         bdump = (uchar_t *) buf;
1123         bdlen = (-b->bh.bsize) - sizeof(struct bhead);
1124     } else {
1125         bdump = (uchar_t *) (((char *) b) + sizeof(struct bfhead));
1126         bdlen = b->bh.bsize - sizeof(struct bfhead);
1127     }
1128
1129     while (bdlen > 0) {
1130         int i, dupes = 0;
1131         bufsize l = bdlen;
1132         char bhex[50], bascii[20];
1133
1134         if (l > 16) {
1135             l = 16;
1136         }
1137
1138         for (i = 0; i < l; i++) {
1139             V sprintf(bhex + i * 3, "%02X ", bdump[i]);
1140             bascii[i] = isprint(bdump[i]) ? bdump[i] : ' ';
1141         }
1142         bascii[i] = 0;
1143         V printf("%-48s   %s\n", bhex, bascii);
1144         bdump += l;
1145         bdlen -= l;
1146         while ((bdlen > 16) && (memcmp((char *) (bdump - 16),
1147                                        (char *) bdump, 16) == 0)) {
1148             dupes++;
1149             bdump += 16;
1150             bdlen -= 16;
1151         }
1152         if (dupes > 1) {
1153             V printf(
1154                 "     (%d lines [%d bytes] identical to above line skipped)\n",
1155                 dupes, dupes * 16);
1156         } else if (dupes == 1) {
1157             bdump -= 16;
1158             bdlen += 16;
1159         }
1160     }
1161 }
1162 #endif
1163
1164 #ifdef BufDump
1165
1166 /*  BPOOLD  --  Dump a buffer pool.  The buffer headers are always listed.
1167                 If DUMPALLOC is nonzero, the contents of allocated buffers
1168                 are  dumped.   If  DUMPFREE  is  nonzero,  free blocks are
1169                 dumped as well.  If FreeWipe  checking  is  enabled,  free
1170                 blocks  which  have  been clobbered will always be dumped. */
1171
1172 void bpoold(buf, dumpalloc, dumpfree)
1173   void *buf;
1174   int dumpalloc, dumpfree;
1175 {
1176     struct bfhead *b = BFH(buf);
1177
1178     while (b->bh.bsize != ESent) {
1179         bufsize bs = b->bh.bsize;
1180
1181         if (bs < 0) {
1182             bs = -bs;
1183             V printf("Allocated buffer: size %6ld bytes.\n", (long) bs);
1184             if (dumpalloc) {
1185                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1186             }
1187         } else {
1188             char *lerr = "";
1189
1190             assert(bs > 0);
1191             if ((b->ql.blink->ql.flink != b) ||
1192                 (b->ql.flink->ql.blink != b)) {
1193                 lerr = "  (Bad free list links)";
1194             }
1195             V printf("Free block:       size %6ld bytes.%s\n",
1196                 (long) bs, lerr);
1197 #ifdef FreeWipe
1198             lerr = ((char *) b) + sizeof(struct bfhead);
1199             if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1200                 (memcmp(lerr, lerr + 1,
1201                   (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1202                 V printf(
1203                     "(Contents of above free block have been overstored.)\n");
1204                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1205             } else
1206 #endif
1207             if (dumpfree) {
1208                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1209             }
1210         }
1211         b = BFH(((char *) b) + bs);
1212     }
1213 }
1214 #endif /* BufDump */
1215
1216 #ifdef BufValid
1217
1218 /*  BPOOLV  --  Validate a buffer pool.  If NDEBUG isn't defined,
1219                 any error generates an assertion failure.  */
1220
1221 int bpoolv(buf)
1222   void *buf;
1223 {
1224     struct bfhead *b = BFH(buf);
1225
1226     while (b->bh.bsize != ESent) {
1227         bufsize bs = b->bh.bsize;
1228
1229         if (bs < 0) {
1230             bs = -bs;
1231         } else {
1232             char *lerr = "";
1233
1234             assert(bs > 0);
1235             if (bs <= 0) {
1236                 return 0;
1237             }
1238             if ((b->ql.blink->ql.flink != b) ||
1239                 (b->ql.flink->ql.blink != b)) {
1240                 V printf("Free block: size %6ld bytes.  (Bad free list links)\n",
1241                      (long) bs);
1242                 assert(0);
1243                 return 0;
1244             }
1245 #ifdef FreeWipe
1246             lerr = ((char *) b) + sizeof(struct bfhead);
1247             if ((bs > sizeof(struct bfhead)) && ((*lerr != 0x55) ||
1248                 (memcmp(lerr, lerr + 1,
1249                   (MemSize) (bs - (sizeof(struct bfhead) + 1))) != 0))) {
1250                 V printf(
1251                     "(Contents of above free block have been overstored.)\n");
1252                 bufdump((void *) (((char *) b) + sizeof(struct bhead)));
1253                 assert(0);
1254                 return 0;
1255             }
1256 #endif
1257         }
1258         b = BFH(((char *) b) + bs);
1259     }
1260     return 1;
1261 }
1262 #endif /* BufValid */
1263
1264         /***********************\
1265         *                       *
1266         * Built-in test program *
1267         *                       *
1268         \***********************/
1269
1270 #ifdef TestProg
1271
1272 #define Repeatable  1                 /* Repeatable pseudorandom sequence */
1273                                       /* If Repeatable is not defined, a
1274                                          time-seeded pseudorandom sequence
1275                                          is generated, exercising BGET with
1276                                          a different pattern of calls on each
1277                                          run. */
1278 #define OUR_RAND                      /* Use our own built-in version of
1279                                          rand() to guarantee the test is
1280                                          100% repeatable. */
1281
1282 #ifdef BECtl
1283 #define PoolSize    300000            /* Test buffer pool size */
1284 #else
1285 #define PoolSize    50000             /* Test buffer pool size */
1286 #endif
1287 #define ExpIncr     32768             /* Test expansion block size */
1288 #define CompactTries 10               /* Maximum tries at compacting */
1289
1290 #define dumpAlloc   0                 /* Dump allocated buffers ? */
1291 #define dumpFree    0                 /* Dump free buffers ? */
1292
1293 #ifndef Repeatable
1294 extern long time();
1295 #endif
1296
1297 extern char *malloc();
1298 extern int free _((char *));
1299
1300 static char *bchain = NULL;           /* Our private buffer chain */
1301 static char *bp = NULL;               /* Our initial buffer pool */
1302
1303 #include <math.h>
1304
1305 #ifdef OUR_RAND
1306
1307 static ulong_t int next = 1;
1308
1309 /* Return next random integer */
1310
1311 int rand()
1312 {
1313         next = next * 1103515245L + 12345;
1314         return (uint_t) (next / 65536L) % 32768L;
1315 }
1316
1317 /* Set seed for random generator */
1318
1319 void srand(seed)
1320   uint_t seed;
1321 {
1322         next = seed;
1323 }
1324 #endif
1325
1326 /*  STATS  --  Edit statistics returned by bstats() or bstatse().  */
1327
1328 static void stats(when)
1329   char *when;
1330 {
1331     bufsize cural, totfree, maxfree;
1332     long nget, nfree;
1333 #ifdef BECtl
1334     bufsize pincr;
1335     long totblocks, npget, nprel, ndget, ndrel;
1336 #endif
1337
1338     bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1339     V printf(
1340         "%s: %ld gets, %ld releases.  %ld in use, %ld free, largest = %ld\n",
1341         when, nget, nfree, (long) cural, (long) totfree, (long) maxfree);
1342 #ifdef BECtl
1343     bstatse(&pincr, &totblocks, &npget, &nprel, &ndget, &ndrel);
1344     V printf(
1345          "  Blocks: size = %ld, %ld (%ld bytes) in use, %ld gets, %ld frees\n",
1346          (long)pincr, totblocks, pincr * totblocks, npget, nprel);
1347     V printf("  %ld direct gets, %ld direct frees\n", ndget, ndrel);
1348 #endif /* BECtl */
1349 }
1350
1351 #ifdef BECtl
1352 static int protect = 0;               /* Disable compaction during bgetr() */
1353
1354 /*  BCOMPACT  --  Compaction call-back function.  */
1355
1356 static int bcompact(bsize, seq)
1357   bufsize bsize;
1358   int seq;
1359 {
1360 #ifdef CompactTries
1361     char *bc = bchain;
1362     int i = rand() & 0x3;
1363
1364 #ifdef COMPACTRACE
1365     V printf("Compaction requested.  %ld bytes needed, sequence %d.\n",
1366         (long) bsize, seq);
1367 #endif
1368
1369     if (protect || (seq > CompactTries)) {
1370 #ifdef COMPACTRACE
1371         V printf("Compaction gave up.\n");
1372 #endif
1373         return 0;
1374     }
1375
1376     /* Based on a random cast, release a random buffer in the list
1377        of allocated buffers. */
1378
1379     while (i > 0 && bc != NULL) {
1380         bc = *((char **) bc);
1381         i--;
1382     }
1383     if (bc != NULL) {
1384         char *fb;
1385
1386         fb = *((char **) bc);
1387         if (fb != NULL) {
1388             *((char **) bc) = *((char **) fb);
1389             brel((void *) fb);
1390             return 1;
1391         }
1392     }
1393
1394 #ifdef COMPACTRACE
1395     V printf("Compaction bailed out.\n");
1396 #endif
1397 #endif /* CompactTries */
1398     return 0;
1399 }
1400
1401 /*  BEXPAND  --  Expand pool call-back function.  */
1402
1403 static void *bexpand(size)
1404   bufsize size;
1405 {
1406     void *np = NULL;
1407     bufsize cural, totfree, maxfree;
1408     long nget, nfree;
1409
1410     /* Don't expand beyond the total allocated size given by PoolSize. */
1411
1412     bstats(&cural, &totfree, &maxfree, &nget, &nfree);
1413
1414     if (cural < PoolSize) {
1415         np = (void *) malloc((unsigned) size);
1416     }
1417 #ifdef EXPTRACE
1418     V printf("Expand pool by %ld -- %s.\n", (long) size,
1419         np == NULL ? "failed" : "succeeded");
1420 #endif
1421     return np;
1422 }
1423
1424 /*  BSHRINK  --  Shrink buffer pool call-back function.  */
1425
1426 static void bshrink(buf)
1427   void *buf;
1428 {
1429     if (((char *) buf) == bp) {
1430 #ifdef EXPTRACE
1431         V printf("Initial pool released.\n");
1432 #endif
1433         bp = NULL;
1434     }
1435 #ifdef EXPTRACE
1436     V printf("Shrink pool.\n");
1437 #endif
1438     free((char *) buf);
1439 }
1440
1441 #endif /* BECtl */
1442
1443 /*  Restrict buffer requests to those large enough to contain our pointer and
1444     small enough for the CPU architecture.  */
1445
1446 static bufsize blimit(bs)
1447   bufsize bs;
1448 {
1449     if (bs < sizeof(char *)) {
1450         bs = sizeof(char *);
1451     }
1452
1453     /* This is written out in this ugly fashion because the
1454        cool expression in sizeof(int) that auto-configured
1455        to any length int befuddled some compilers. */
1456
1457     if (sizeof(int) == 2) {
1458         if (bs > 32767) {
1459             bs = 32767;
1460         }
1461     } else {
1462         if (bs > 200000) {
1463             bs = 200000;
1464         }
1465     }
1466     return bs;
1467 }
1468
1469 int main()
1470 {
1471     int i;
1472     double x;
1473
1474     /* Seed the random number generator.  If Repeatable is defined, we
1475        always use the same seed.  Otherwise, we seed from the clock to
1476        shake things up from run to run. */
1477
1478 #ifdef Repeatable
1479     V srand(1234);
1480 #else
1481     V srand((int) time((long *) NULL));
1482 #endif
1483
1484     /*  Compute x such that pow(x, p) ranges between 1 and 4*ExpIncr as
1485         p ranges from 0 to ExpIncr-1, with a concentration in the lower
1486         numbers.  */
1487
1488     x = 4.0 * ExpIncr;
1489     x = log(x);
1490     x = exp(log(4.0 * ExpIncr) / (ExpIncr - 1.0));
1491
1492 #ifdef BECtl
1493     bectl(bcompact, bexpand, bshrink, (bufsize) ExpIncr);
1494     bp = malloc(ExpIncr);
1495     assert(bp != NULL);
1496     bpool((void *) bp, (bufsize) ExpIncr);
1497 #else
1498     bp = malloc(PoolSize);
1499     assert(bp != NULL);
1500     bpool((void *) bp, (bufsize) PoolSize);
1501 #endif
1502
1503     stats("Create pool");
1504     V bpoolv((void *) bp);
1505     bpoold((void *) bp, dumpAlloc, dumpFree);
1506
1507     for (i = 0; i < TestProg; i++) {
1508         char *cb;
1509         bufsize bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1510
1511         assert(bs <= (((bufsize) 4) * ExpIncr));
1512         bs = blimit(bs);
1513         if (rand() & 0x400) {
1514             cb = (char *) bgetz(bs);
1515         } else {
1516             cb = (char *) bget(bs);
1517         }
1518         if (cb == NULL) {
1519 #ifdef EasyOut
1520             break;
1521 #else
1522             char *bc = bchain;
1523
1524             if (bc != NULL) {
1525                 char *fb;
1526
1527                 fb = *((char **) bc);
1528                 if (fb != NULL) {
1529                     *((char **) bc) = *((char **) fb);
1530                     brel((void *) fb);
1531                 }
1532                 continue;
1533             }
1534 #endif
1535         }
1536         *((char **) cb) = (char *) bchain;
1537         bchain = cb;
1538
1539         /* Based on a random cast, release a random buffer in the list
1540            of allocated buffers. */
1541
1542         if ((rand() & 0x10) == 0) {
1543             char *bc = bchain;
1544             int i = rand() & 0x3;
1545
1546             while (i > 0 && bc != NULL) {
1547                 bc = *((char **) bc);
1548                 i--;
1549             }
1550             if (bc != NULL) {
1551                 char *fb;
1552
1553                 fb = *((char **) bc);
1554                 if (fb != NULL) {
1555                     *((char **) bc) = *((char **) fb);
1556                     brel((void *) fb);
1557                 }
1558             }
1559         }
1560
1561         /* Based on a random cast, reallocate a random buffer in the list
1562            to a random size */
1563
1564         if ((rand() & 0x20) == 0) {
1565             char *bc = bchain;
1566             int i = rand() & 0x3;
1567
1568             while (i > 0 && bc != NULL) {
1569                 bc = *((char **) bc);
1570                 i--;
1571             }
1572             if (bc != NULL) {
1573                 char *fb;
1574
1575                 fb = *((char **) bc);
1576                 if (fb != NULL) {
1577                     char *newb;
1578
1579                     bs = pow(x, (double) (rand() & (ExpIncr - 1)));
1580                     bs = blimit(bs);
1581 #ifdef BECtl
1582                     protect = 1;      /* Protect against compaction */
1583 #endif
1584                     newb = (char *) bgetr((void *) fb, bs);
1585 #ifdef BECtl
1586                     protect = 0;
1587 #endif
1588                     if (newb != NULL) {
1589                         *((char **) bc) = newb;
1590                     }
1591                 }
1592             }
1593         }
1594     }
1595     stats("\nAfter allocation");
1596     if (bp != NULL) {
1597         V bpoolv((void *) bp);
1598         bpoold((void *) bp, dumpAlloc, dumpFree);
1599     }
1600
1601     while (bchain != NULL) {
1602         char *buf = bchain;
1603
1604         bchain = *((char **) buf);
1605         brel((void *) buf);
1606     }
1607     stats("\nAfter release");
1608 #ifndef BECtl
1609     if (bp != NULL) {
1610         V bpoolv((void *) bp);
1611         bpoold((void *) bp, dumpAlloc, dumpFree);
1612     }
1613 #endif
1614
1615     return 0;
1616 }
1617 #endif