Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


Merge branch 'devel' of newskysaw.cs.northwestern.edu:/home/palacios/palacios into...
[palacios.git] / 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