home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / server / ddx / ibm / common / ibmMalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-16  |  26.4 KB  |  1,014 lines
  1. /*
  2.  * $XConsortium: ibmMalloc.c,v 1.2 91/07/16 13:08:10 jap Exp $
  3.  *
  4.  * Copyright IBM Corporation 1987,1988,1989,1990,1991
  5.  *
  6.  * All Rights Reserved
  7.  *
  8.  * License to use, copy, modify, and distribute this software and its
  9.  * documentation for any purpose and without fee is hereby granted,
  10.  * provided that the above copyright notice appear in all copies and that
  11.  * both that copyright notice and this permission notice appear in
  12.  * supporting documentation, and that the name of IBM not be
  13.  * used in advertising or publicity pertaining to distribution of the
  14.  * software without specific, written prior permission.
  15.  *
  16.  * IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  17.  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS, AND 
  18.  * NONINFRINGEMENT OF THIRD PARTY RIGHTS, IN NO EVENT SHALL
  19.  * IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  20.  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  21.  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  22.  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  23.  * SOFTWARE.
  24.  *
  25. */
  26.  
  27. /*
  28.  *  malloc.c   memory allocator
  29.  */
  30.  
  31. /*
  32.  
  33.     author: WJHansen, CMU/ITC
  34.     (c) Copyright IBM Corporation, 1985, 1986
  35.  
  36.     Adapted from Algorithms 6.6(b) and 6.7 in
  37.         E. M. Reingold,  W. J. Hansen,
  38.         Data Structures in Pascal, 
  39.         Little, Brown, 1986
  40.  
  41.     Some details are also taken from the malloc
  42.     distributed with 4.1 BSD.
  43.  
  44.     The algorithm features a disordered free list which is
  45.     scanned with next-fit.  Allocation scans only the 
  46.     free blocks.  Freeing a block coalesces 
  47.     it with its free neighbors, if any, in time O(1).
  48.  
  49.     Every block has a one word header (4 bytes) with the
  50.     Size of the block (in bytes, counting header).
  51.     The low bits of size are Active and PreActive bits,
  52.     which indicate whether the block and its predecessor,
  53.     respectively, are free.  A free list block has Next and Prev
  54.     pointers and the last word of a free block is a Front pointer 
  55.     which points to its beginning.   The smallest allocatable
  56.     block is three pointers long.
  57.  
  58.     The arena may be composed of disjoint segments.  Each
  59.     segment ends with a free block having Active set true.
  60.     These blocks deal with the end condition for the last 
  61.     block of the arena segment.  They also serve to guarantee
  62.     that the free list will never be empty.
  63.  
  64. April 22, 1986, WJHansen
  65.     reduce botch messages to short strings
  66.     don't use stdio to avoid recursive malloc
  67.         don't test stdout->_base before dumping stats
  68.         always dump headers in addarena if CheckLevel>=5
  69.     implement the PendingFree/FlushFree kludge to allow "free(x);return(x->foo)"
  70.     save pointers to previous blocks in CheckSegment and malloc for debugging
  71.     install InProgress to prevent recursive mallocs (as during a signal handler)
  72.     move arena control to malloc.h; create malloc.h
  73.     check in the free routine to see if the candidate block is within the present arena
  74.     implement NewMallocArena and GetMallocArena
  75.     save caller's return address and a sequence number in each malloc'ed block
  76.     revise tail end of realloc to reduce amount of code
  77.     revise front end or realloc to eliminate the FRxxx stuff 
  78.         it now assumes that if previously freed, the freed block is in A.PendingFree
  79.     eliminate the extra copy of code within malloc and free
  80.     consolidate all testing into TestActive and TestFree
  81.  
  82. Sept 9, 1985, WJHansen
  83.     Add AbortFullMessage(nbytes)
  84.     add resetmstats()
  85.     add checklevel == 4
  86.  
  87. */
  88.  
  89. #define IDENTIFY
  90.  
  91. #include <stdio.h>
  92. #include "ibmMalloc.h"
  93. #include "ibmTrace.h"
  94.  
  95. #ifdef notdef
  96. static char msgbuf[200];
  97. #define ferr4(fmt, a, b, c, d) {sprintf(msgbuf, fmt, a, b, c, d); \
  98.                 write(2, msgbuf, strlen(msgbuf));}
  99. #define ferr3(fmt, a, b, c) {sprintf(msgbuf, fmt, a, b, c); \
  100.                 write(2, msgbuf, strlen(msgbuf));}
  101. #define ferr2(fmt, a, b) {sprintf(msgbuf, fmt, a, b); \
  102.                 write(2, msgbuf, strlen(msgbuf));}
  103. #define ferr1(fmt, a) {sprintf(msgbuf, fmt, a); \
  104.                 write(2, msgbuf, strlen(msgbuf));}
  105. #define ferr0(fmt) {sprintf(msgbuf, fmt); \
  106.                 write(2, msgbuf, strlen(msgbuf));}
  107. #else
  108. #define ferr4(fmt, a, b, c, d)    {ErrorF(fmt,a,b,c,d);}
  109. #define ferr3(fmt, a, b, c)    {ErrorF(fmt,a,b,c);}
  110. #define ferr2(fmt, a, b)    {ErrorF(fmt,a,b);}
  111. #define ferr1(fmt, a)        {ErrorF(fmt,a);}
  112. #define ferr0(fmt)        {ErrorF(fmt);}
  113. #endif /* notdef */
  114.  
  115.  
  116. static CheckLevel;
  117. /* at CheckLevel = 0, no checking is done
  118.     at 1, local reasonability tests are made
  119.     at 2, local tests are made and each free block is
  120.         checked as it is scanned searching
  121.         for a big enough one
  122.     at 3, the full free list is checked on every
  123.         malloc or free
  124.     at 4, a message is printed to stdout 
  125.         for every malloc, free, & realloc
  126.     at 5, mstats will print a complete list 
  127.         of all blocks in memory
  128. */
  129.  
  130. #define ASSERT(where,pr) if(!(pr))botch(where);else
  131.  
  132. static int DefaultM0Handler();   /* (below) */
  133.  
  134. static int (*M0Handler)() = DefaultM0Handler;
  135. /* the procedure SetM0Handler may be called to set this value
  136.     When malloc runs out of memory, it calls the M0Handler,
  137.     passing it the amount of the malloc request.  (It may also be 
  138.     called from within realloc.)
  139.     If the M0Handler returns, its value is used as the new 
  140.     amount to be allocated, but if zero, malloc just returns zero.
  141. */
  142.  
  143. /* A.InProgress is set on entry and cleared before exit.  It prevents a signal handler from 
  144. initiating a malloc or free while one is in progress.  The switch is set and tested with
  145.     if(A.InProgress++) {<error>}
  146. This is foolproof only where ++ to a variable is implemented as a test-and-set instruction;
  147. for instance, on an ibm032 there is a small chance of failure to detect recursive malloc 
  148. if the signal handler is invoked in the middle of the instructions that perform the ++
  149. */
  150.  
  151. #ifdef MSTATS
  152.     int Nscans, Nrequests, Nsbrk, Ncombines, Nfrees;
  153. #endif
  154.  
  155. /*    avoid break bug */
  156. #ifdef pdp11
  157. #define GRANULE 64
  158. #else
  159. #define GRANULE 0
  160. #endif
  161.  
  162. static struct arenastate A = {0, 0, 0, 0, 0, 0, 0, 0};
  163.  
  164. char    *sbrk();
  165. static struct freehdr *addarena ();
  166.  
  167. /* More kludgery:  Some programs assume that freed blocks can still be
  168. accessed for a while.  This fails because the contents of some words of freed
  169. blocks are overlaid with the chain pointers for the free list.  To simulate
  170. the expected behavior, this package does not actually perform free until the
  171. next operation to the package.  A pointer to the block to be freed is saved
  172. in PendingFree.  The actual free routine is called FlushFree.  The routines
  173. malloc, free, and realloc all begin with  
  174.     if (A.PendingFree) FlushFree(A.PendingFree);
  175. */
  176.  
  177.  
  178.  
  179.  
  180. /*
  181.     malloc
  182.  
  183.     Pascal version from Data Structures in Pascal
  184. type
  185.     block = record
  186.         Size: integer;           {size of this record}
  187.         Active: boolean;        {true when this record is in use}
  188.         PreActive: boolean;     {true when preceding record is in use}
  189.         case blockType of
  190.             freeBlock:(Next, Prev: ptr;    {link free list}
  191.                     {" . . . "}
  192.                     Front: ptr);  {last word points to start of record}
  193.             activeBlock: ({"contents, as required"} )
  194.     end;
  195.     ptr = ^block;
  196. var 
  197.     free: ptr;
  198.  
  199. function malloc(n: integer): ptr;
  200. var
  201.     p: ptr;
  202. begin
  203.     p := free;
  204.     {scan free list looking for a large enough record}
  205.     while (p<>free^.Prev) and (p^.Size<n) do
  206.         {Assert:  No record on list from (free) to (p)
  207.                 has size (n) or larger.}
  208.         p := p^.Next;
  209.     if p^.Size < n then
  210.         sbrk(rounded up number of bytes);
  211.     if p^.Size < n then
  212.         malloc := null;
  213.     else begin
  214.         free := p^.Next;    {set (free) for Next allocation}
  215.         if p^.Size - n < epsilon then begin
  216.             {allocate entire record; remove it from free list}
  217.             p^.Next^.Prev := p^.Prev;
  218.             p^.Prev^.Next := p^.Next
  219.         end
  220.         else begin
  221.             {split (p); allocate the right and free the left}
  222.             p^.Size := p^.Size - n;
  223.             {"(Front) pointer at end of (p)^"} := p;
  224.             p := {"(p)+(p)^.(Size)"};
  225.             p^.Size := n;
  226.             p^.PreActive := false
  227.         end;
  228.         {(p)^.(Size)>=(n) and a record of length (p)^.(Size) 
  229.         is allocated, beginning at (p)}
  230.         p^.Active := true;
  231.         {"((p)+(p)^.(Size))"}^.PreActive := true;
  232.         malloc := p    {return a pointer to the new record}
  233.     end
  234. end;
  235.  
  236. */
  237.  
  238. char *
  239. Xalloc(nbytes)
  240. unsigned nbytes;
  241. {
  242.     register siz;    /* # bytes to allocate */
  243.     register struct freehdr *p, *t;
  244.         char *tptr;
  245.  
  246.     
  247.     tptr = (malloc (nbytes));
  248.         return (tptr);
  249.  
  250.     if (A.InProgress++) {
  251.         botch("Program error.  Tried 'malloc' while in malloc package.");
  252.         A.InProgress--;
  253.         return 0;
  254.     }
  255.     if (A.PendingFree) FlushFree(A.PendingFree);
  256.  
  257. #ifdef MSTATS
  258. Nrequests++;
  259. #endif
  260.     if (A.allocp==0)     {  /*first time*/
  261.         /* start with 20K (rounded up in addarena) */
  262.         A.allocp = addarena(1<<14);  
  263.         if (A.allocp==0) 
  264.             DefaultM0Handler(1<<14); 
  265.     }
  266.  
  267.     if (CheckLevel > 0) {
  268.         if (CheckLevel>=3) CheckAllocs("in Malloc");
  269.         else ASSERT("m0", TestFree(A.allocp));
  270.     }
  271.  
  272.     siz = (nbytes+sizeof(struct hdr)+(WORD-1))/WORD*WORD;
  273.     if (siz<EPSILON) siz = EPSILON;
  274.     t = A.allocp->Prev;
  275.  
  276.     /* scan free list looking for a large enough record */
  277.     /* as an optimization we skip the clearbits() around p->Size,
  278.         assuming that ACTIVE and PREACTIVE are in the
  279.         low bits so they do not affect the size comparison */
  280.     if (CheckLevel!=2)  for (p=A.allocp; 
  281. #ifdef MSTATS
  282. Nscans++,
  283. #endif
  284.             p!=t && p->Size<siz; 
  285.             p = p->Next) {
  286.  
  287.     }
  288.     else    for (p=A.allocp;      /* CheckLevel == 2 */
  289. #ifdef MSTATS
  290. Nscans++,
  291. #endif
  292.             p!=t && p->Size<siz; 
  293.             p = p->Next) {
  294.         if (clearbits(p->Size)) {
  295.             ASSERT ("m1", ! testbit(p->Size,ACTIVE));
  296.             ASSERT ("m2", p == PREVFRONT(NEXTBLOCK(p)));
  297.         }
  298.         else 
  299.             ASSERT ("m3", testbit(p->Size, ACTIVE));
  300.         ASSERT("m4", p->Next->Prev==p);
  301.     }
  302.     if (p->Size<siz) {
  303.         p = addarena(siz);
  304.         if (p==NULL) {
  305.             if (A.RecurringM0)
  306.                 DefaultM0Handler(nbytes);
  307.             else {
  308.                 char *v;
  309.                 int (*h)() = M0Handler;
  310.                 int newsize;
  311.                 A.InProgress--;
  312.                 newsize = (*M0Handler)(nbytes);
  313.                 /* if newsize still too big and no new
  314.                     M0Handler is set, a failure
  315.                     to allocate newsize is an abort
  316.                 */
  317.                 if (h==M0Handler)
  318.                     A.RecurringM0 ++;
  319.                 v = (newsize) ? malloc(newsize) : NULL;
  320.                 A.RecurringM0 = 0;
  321. #ifdef IDENTIFY
  322.                 if (v) {
  323.                     struct hdr *t = ((struct hdr *)v)-1;
  324.                     t->caller = *(((char **)&nbytes) - RETADDROFF);
  325.                     t->seqno = A.SeqNo++;
  326.                 }
  327. #endif
  328.                 return v;
  329.             }
  330.         }
  331.     }
  332.  
  333.     if (CheckLevel > 0)  
  334.         ASSERT("m10", TestFree(p));
  335.  
  336.     A.allocp = p->Next;
  337.     if (clearbits(p->Size)-siz < EPSILON) {
  338.         /*allocate entire record; remove it from free list*/
  339.         p->Next->Prev = p->Prev;
  340.         p->Prev->Next = p->Next;
  341.         p->Size |= ACTIVE;
  342.     }
  343.     else {
  344.         /* split (p); allocate the right and free the left*/
  345.         p->Size -= siz;   /* doesn't change bits */
  346.         t = NEXTBLOCK(p);
  347.         PREVFRONT(t) = p;
  348.         p = t;
  349.         p->Size = siz | ACTIVE;
  350.     }
  351.     /* Some programs have code that assumes that newly 
  352.         malloc'ed memory is zero (Heavy SIGH): */
  353.     p->Next = 0;
  354.     p->Prev = 0;
  355.     t = NEXTBLOCK(p);
  356.     PREVFRONT(t) = 0;
  357.  
  358.     t->Size |= PREACTIVE;
  359.  
  360.     A.InProgress --;
  361.  
  362. #ifdef IDENTIFY
  363.     p->caller = *(((char **)&nbytes) - RETADDROFF);
  364.     p->seqno = A.SeqNo++;
  365. #endif
  366.     if (CheckLevel >=4) {
  367.         int *ap = (int *)&nbytes;
  368.         ferr3("malloc @ 0x%lx for %d bytes returns 0x%lx\n",
  369.             *(ap-RETADDROFF), *ap, 
  370.             ((char *)p) + sizeof(struct hdr));
  371.     }
  372.  
  373.     return ((char *)p) + sizeof(struct hdr);
  374. }
  375.  
  376. /* addarena */
  377. /* create a new or extended arena.  Two adjacent arenas will coallesce. */
  378. /* In a new arena segment, The first three words are a freehdr with
  379.     Size indicating all of block except last four words;  its Active
  380.     bit is false and its PreActive bit is true (so no coalesce off front
  381.     will be tried);  Next and Prev both point to a dummy free element
  382.     in last four words.  The dummy in the last four words of the segment
  383.     has Active true (so preceding block will not coalesce with it) and
  384.     PreActive set depending on the preceding block (initially false);
  385.     the Size field is zero; Next and Prev both point to the free
  386.     element at the beginning of the segment.  The Front field
  387.     in the last word of the segment points not to the dummy
  388.     free element at the end, but to the beginning of the segment
  389.     (so CheckAllocs can find segment.)
  390.  
  391.     The argument min gives the space needed.
  392.     Return value is NULL or a pointer to a big enough block.
  393. */
  394. static
  395. struct freehdr *
  396. addarena (min) {
  397.     register struct freehdr *new, *trlr;
  398.     struct freehdr *t;
  399.     int segbytes = ((min+2*EPSILON+(SEGGRAIN-1)) 
  400.             / SEGGRAIN) * SEGGRAIN;
  401.     int x;
  402. #ifdef pdp11
  403.     new = (struct freehdr *)sbrk(0);
  404.     if((INT)new+segbytes+GRANULE < (INT)new) {
  405.         return(NULL);
  406.     }
  407. #endif
  408. #ifdef MSTATS
  409. Nsbrk++;
  410. #endif
  411.     new = (struct freehdr *)sbrk(segbytes);
  412.     if((INT)new == -1) 
  413.         return(NULL);
  414.     if ((x=(INT)new % WORD)) {
  415.         new = (struct freehdr *)((INT)new+WORD-x);
  416.         segbytes -= WORD; 
  417.     }
  418.     trlr = (struct freehdr *)((INT)new+segbytes-EPSILON);
  419.     new->Size = setbits(segbytes - EPSILON, PREACTIVE);
  420.     new->Next = trlr;
  421.     trlr->Size = setbits(0, ACTIVE);
  422.     trlr->Prev = new;
  423.     PREVFRONT(trlr) = new;
  424.     /* trlr is the dummy block at the end of the arena
  425.         make its Front field point to arenastart */
  426.     PREVFRONT(((char *)trlr)+EPSILON) = new;
  427.     
  428.     if (A.arenaend) {
  429.         /* attach new arena into old free list */
  430.         new->Prev = A.arenaend;
  431.         trlr->Next = A.arenaend->Next;
  432.         A.arenaend->Next->Prev = trlr;
  433.         A.arenaend->Next = new;
  434.     }
  435.     else {
  436.         A.arenastart = new;
  437.         trlr->Next = new;
  438.         new->Prev = trlr;
  439.     }
  440.     if (new == (struct freehdr *)(((char *)A.arenaend)+EPSILON)) {
  441.         /* coallesce adjacent arenas */
  442.         PREVFRONT(((char *)trlr)+EPSILON) =
  443.             PREVFRONT(((char *)A.arenaend)+EPSILON);
  444.         t = A.arenaend;
  445.         t->Size = setbits(EPSILON, 
  446.                 testbit(t->Size, PREACTIVE)
  447.                 | ACTIVE);
  448.         t->Next->Prev = t->Prev;
  449.         t->Prev->Next = t->Next;
  450.         if (A.allocp==t)
  451.             A.allocp = t->Next;
  452.         A.arenaend = trlr;
  453.         FlushFree ((char *)t+sizeof (struct hdr));
  454.     }
  455.     else
  456.         A.arenaend = trlr;
  457.     if (CheckLevel>=5) 
  458.         printarena("addarena");
  459.     return (PREVFRONT(A.arenaend));
  460. }
  461.  
  462.  
  463. /*
  464.     free
  465.  
  466.     Pascal version from Data Structures in Pascal
  467.  
  468. procedure free(p: ptr);
  469. var
  470.     t: ptr;
  471. begin
  472.     t := {"(p)+(p)^.(Size)"};   {(t)^ is the next record in (word) after (p)^}
  473.     if not t^.Active then begin   {(t)^ is free}
  474.         {merge (p)^ and (t)^, removing (t)^ from free list}
  475.         t^.Next^.Prev := t^.Prev;
  476.         t^.Prev^.Next := t^.Next;
  477.         if t = free then
  478.             free := t^.Prev;
  479.         p^.Size := p^.Size + t^.Size;
  480.     end
  481.     else t^.PreActive := false;
  482.     if not p^.PreActive then begin
  483.         {merge (p)^ with physically preceding record, which is already
  484.         on the free list}
  485.         t := {"((p)-1)"}^.Front;
  486.         t^.Size := t^.Size + p^.Size;
  487.         {"(Front) pointer at end of (t)^"} := t;
  488.     end
  489.     else begin
  490.         {put (p) on free list}
  491.         p^.Active := false;
  492.         {"(Front) pointer at end of (p)^"} := p;
  493.         p^.Prev := free^.Prev;
  494.         p^.Next := free;
  495.         free^.Prev := p;
  496.         p^.Prev^.Next := p
  497.     end
  498. end
  499. */
  500.  
  501.  
  502. Xfree(ap)
  503. struct hdr *ap;
  504. {
  505.     return (free (ap));
  506.     if (!ap) return;
  507.     if (CheckLevel >= 4) {
  508.         int *app = (int *)≈
  509.         ferr3("free @ 0x%lx for block of %d bytes at 0x%lx enqueued\n",
  510.             *(app-RETADDROFF), 
  511.             clearbits(((struct freehdr *)(((char *)ap) - sizeof(struct hdr)))->Size), 
  512.             *app);
  513.     }
  514.     if (A.InProgress++) {
  515.         botch ("Program error.  Tried 'free' while in malloc package.");
  516.     }
  517.     if (A.PendingFree) FlushFree(A.PendingFree);
  518.     A.PendingFree = ap;
  519.     A.InProgress -- ;
  520. }
  521.  
  522. static
  523. FlushFree(ap)
  524. struct hdr *ap;
  525. {
  526.     register struct freehdr *p = (struct freehdr *)(((char *)ap) - sizeof(struct hdr));
  527.     register struct freehdr *t = NEXTBLOCK(p);
  528.     register int siz = clearbits(p->Size);  /* retain p->Size */
  529.     int preact = testbit(p->Size, PREACTIVE); /* retain p->PREACTIVE */
  530.  
  531.     A.PendingFree = 0;
  532.  
  533.     if (p < A.arenastart || t > A.arenaend) {
  534.         if ( ! A.arenahasbeenreset) 
  535.             botch("Program error.  Free non-malloc'ed block.");
  536.         return;
  537.     }
  538.  
  539. #ifdef MSTATS
  540. Nfrees++;
  541. #endif
  542.  
  543.     if (CheckLevel > 0) {
  544.         register struct freehdr *f = PREVFRONT(p);
  545.         ASSERT("f0", TestActive(p));
  546.         if (CheckLevel >= 3) CheckAllocs("in free");
  547.         else {
  548.             ASSERT("f1", TestFree(A.allocp));
  549.             if (!testbit(t->Size, ACTIVE)) 
  550.                 ASSERT("f2", TestFree(t));
  551.             else ASSERT("f3", TestActive(t));
  552.             if (!preact) 
  553.                 ASSERT("f4", TestFree(f));
  554.             else ASSERT("f5", TestActive(f));
  555.         }
  556.     }
  557.  
  558.     if (!testbit(t->Size, ACTIVE)) {  
  559.         /* coalesce *p and *t */
  560. #ifdef MSTATS
  561. Ncombines++;
  562. #endif
  563.         t->Next->Prev = t->Prev;
  564.         t->Prev->Next = t->Next;
  565.         if (t==A.allocp) 
  566.             A.allocp = t->Next;
  567.         siz += clearbits(t->Size);
  568.     }
  569.     else 
  570.         t->Size = clearbit(t->Size, PREACTIVE);
  571.  
  572.     if (!preact) {
  573.         /* merge *p with preceding free block */
  574. #ifdef MSTATS
  575. Ncombines++;
  576. #endif
  577.         t = PREVFRONT(p);
  578.         preact = testbit(t->Size, PREACTIVE);
  579.         siz += clearbits(t->Size);
  580.         p->Size = 0;  /* mark not active */
  581.         p = t;
  582.     }
  583.     else {
  584.         /* put *p on the free list */
  585.         p->Prev = A.allocp->Prev;
  586.         p->Next = A.allocp;
  587.         p->Prev->Next = A.allocp->Prev = p;
  588.     }
  589.  
  590.     p->Size = setbits(siz, preact);
  591.     PREVFRONT((char *)p + siz) = p;
  592. }
  593.  
  594. /*    realloc(p, nbytes) reallocates a block obtained from malloc()
  595.  *    and (possibly) freed since last call of malloc()
  596.  *    to have new size nbytes, and old content
  597.  *    returns new location, or 0 on failure
  598.  */
  599.  
  600. char *
  601. Xrealloc(ap, nbytes)
  602. struct hdr *ap;            /* block to realloc */
  603. unsigned nbytes;            /* desired size */
  604. {
  605.     register struct freehdr *h;
  606.     struct freehdr *f;
  607.     unsigned siz;        /* total size needed */
  608.     unsigned nw;        /* desired number of words */
  609.     register unsigned onw;    /* existing number of words */
  610.     char *msg;        /* reason for failure */
  611.  
  612.         char *tptr;
  613.  
  614.     
  615.         free(ap);
  616.     tptr = (realloc (ap, nbytes));
  617.         return (tptr);
  618.  
  619. /*    return (realloc (ap, nbytes)); */
  620.     if (!ap) {
  621.         ap= (struct hdr *)Xalloc(nbytes);
  622.     }
  623.  
  624.     h= (struct freehdr *)(((char *)ap) - sizeof(struct hdr));
  625.     f= NEXTBLOCK(h);
  626.  
  627.     if (A.InProgress++) {
  628.         botch ("Program error.  Tried 'realloc' while in malloc package.");
  629.         A.InProgress--;
  630.         return 0;
  631.     }
  632.     if (CheckLevel>=4) {
  633.         int *app = (int *)≈
  634.         ferr3 ("realloc @ 0x%lx changes size %d at 0x%lx . . .\n",
  635.             *(app-RETADDROFF), clearbits(h->Size), ap);
  636.     }
  637.     if (A.PendingFree) {
  638.         if (A.PendingFree == ap) 
  639.             A.PendingFree = NULL;
  640.         else FlushFree(A.PendingFree);    
  641.     }
  642.  
  643.     if (! TestActive(h)) {
  644.         msg = "rx1";
  645.     nope:    if (CheckLevel>=4)
  646.             ferr1(". . . fails at %s\n", msg);
  647.         A.InProgress--;
  648.         return NULL;
  649.     }
  650.     if (CheckLevel > 0) {
  651.         if (CheckLevel>=3) CheckAllocs("in realloc");
  652.         if (!testbit(f->Size, ACTIVE))
  653.             ASSERT("r0", TestFree(f));
  654.         ASSERT("r1", TestFree(A.allocp));
  655.     }
  656.     siz = (nbytes+sizeof(struct hdr)+(WORD-1))/WORD*WORD;
  657.     if (siz<EPSILON) siz = EPSILON;
  658.     if (!testbit(f->Size, ACTIVE) 
  659.             && clearbits(h->Size)+clearbits(f->Size) >= siz) {
  660.         /* combine active block h with following free block f */
  661.         f->Next->Prev = f->Prev;
  662.         f->Prev->Next = f->Next;
  663.         if (f==A.allocp) 
  664.             A.allocp = f->Next;
  665.         h->Size += clearbits(f->Size);   /* don't change bits in h->Size */
  666.         f = NEXTBLOCK(h);
  667.         f->Size = setbits(f->Size, PREACTIVE);
  668.     }
  669.  
  670.     /* the remainder does not affect the free list or arena, 
  671.         so InProgress protection is no longer needed 
  672.         (though the assigns to PendingFree may cause
  673.         a free operation to be skipped )      */
  674.     A.InProgress --;
  675.  
  676.     nw = (siz - sizeof(struct hdr))/WORD;
  677.     onw = (clearbits(h->Size)-sizeof(struct hdr))/WORD;
  678.     if (nw<=onw) {
  679.         /* is big enough;  can we release part? */
  680.         if (onw-nw>EPSILON/WORD) {
  681.             h->Size = setbits(siz, 
  682.                 ACTIVE | testbit(h->Size, PREACTIVE));
  683.             f = NEXTBLOCK(h);
  684.             f->Size = setbits((onw-nw)*WORD,
  685.                     ACTIVE | PREACTIVE);
  686.             A.PendingFree = ((struct hdr *)f) + 1;
  687.         }
  688.     }
  689.     else {
  690.         /* malloc a new one and copy */
  691.         register INT *s, *t;
  692.         s = (INT *)ap;
  693.         ap = (struct hdr *)malloc(nbytes);   /* ap pts to data, not hdr */
  694.         if (ap==NULL)
  695.             {msg = "rx5"; goto nope;}
  696.         A.PendingFree = (struct hdr *)s;
  697.         t = (INT *)ap;
  698.         while(onw-->0)
  699.             *t++ = *s++;
  700.     }
  701.     if (CheckLevel >= 4) 
  702.         ferr2 (". . . to size %d at 0x%lx\n", nbytes, ap);
  703. #ifdef IDENTIFY
  704.     (ap-1)->caller = *(((char **)&ap) - RETADDROFF);
  705.     (ap-1)->seqno = A.SeqNo++;
  706. #endif
  707.     return((char *)ap);
  708. }
  709.  
  710. /*
  711. char    *
  712. malloc(nbytes)
  713. int nbytes;
  714. {
  715.    return(Xalloc(nbytes));
  716. } */
  717.  
  718. /*
  719. free(ptr)
  720. char *ptr;
  721. {
  722.    return(Xfree((struct hdr *)ptr));
  723. } */
  724.  
  725. /*
  726. char *
  727. realloc(ptr,nbytes)
  728. char  *ptr;
  729. int    nbytes;
  730. {
  731.    return(Xrealloc((struct hdr *)ptr,nbytes));
  732. }*/
  733.  
  734.     static int
  735. TestFree (f)
  736.     register struct freehdr *f;
  737. {
  738.     if (testbit(f->Size,ACTIVE)) {
  739.         /* had better be a segment trailer */
  740.         register struct freehdr *t = ((struct segtrlr *)f)->Front;
  741.         return (f->Next->Prev == f
  742.             && f->Prev->Next == f
  743.             && testbit(t->Size, PREACTIVE)
  744.             && clearbits(f->Size) == 0
  745.             && t < f
  746.             && f <= A.arenaend
  747.             && t >= A.arenastart);
  748.     }
  749.     else {
  750.         /* test as a regular free block */
  751.         register struct freehdr *t = NEXTBLOCK(f);
  752.         return (f->Next->Prev == f
  753.             && f->Prev->Next == f
  754.             && testbit(f->Size, PREACTIVE)
  755.             && f == PREVFRONT(t)
  756.             && ! testbit(t->Size, PREACTIVE)
  757.             && f >= A.arenastart
  758.             && t <= A.arenaend
  759.             && f->Size >= EPSILON);
  760.     }
  761. }
  762.     static int
  763. TestActive (f) 
  764.     register struct freehdr *f;
  765. {
  766.     register struct freehdr *t = NEXTBLOCK(f);
  767.     return (testbit(f->Size, ACTIVE)
  768.         && f >= A.arenastart
  769.         && t <= A.arenaend
  770.         && testbit(t->Size, PREACTIVE)
  771.         && f->Size > EPSILON);
  772. }
  773.  
  774.  
  775.     static
  776. printarena (m)
  777.     char *m;
  778. {
  779.     int *x;
  780.     int i;
  781.     ferr4("%s:  arenastart %lx  arenaend %lx  allocp %lx\narena starts with", 
  782.             m, A.arenastart, A.arenaend, A.allocp);
  783.     for (x = (int *)A.arenastart, i=0; i<EPSILON/WORD; i++)
  784.         ferr1("   %lx", *(x+i));
  785.     ferr0 ("\nand ends with");
  786.     for (x = (int *)A.arenaend, i = -1; i<EPSILON/WORD; i++)
  787.         ferr1("   %lx", *(x+i));
  788.     ferr0("\n");
  789. }
  790.  
  791. #ifdef MSTATS
  792. int Nactive, Nfree, Nsegs;
  793. long int TotActive, TotFree;
  794. static DumpBlocks = 0;
  795. #endif
  796.  
  797. CheckAllocs(m) char *m;
  798. {
  799.     int nfree=0;
  800.     register struct freehdr *t;
  801.     if (A.allocp==0)  {    /*first time, use code from inside malloc */ 
  802.         /* start with 20K (rounded up in addarena) */
  803.         A.allocp = addarena(1<<14);  
  804.         if (A.allocp==0) 
  805.             DefaultM0Handler(1<<14); 
  806.     }
  807.  
  808. #ifdef MSTATS
  809.     Nactive = Nfree = Nsegs = 0;
  810.     TotActive = TotFree = 0;
  811.     if (DumpBlocks) {
  812.         struct hdr *x;
  813.         register struct freehdr *a, *olda;
  814.         int i;
  815.         printarena(m);
  816. #ifndef IDENTIFY
  817.         ferr0 ("\n    Front;       loc:      Size      Next      Prev\n");
  818. #else
  819.         ferr0 ("\n    Front;       loc:      Size      Caller   Seqno      Next      Prev\n");
  820. #endif
  821.         for (a = A.arenastart, olda = 0; 
  822.                 a>olda && a < A.arenaend; 
  823.                 a = (struct freehdr *)((char *)(olda=a) + clearbits(a->Size)) ) {
  824.             ferr3("   %10lx; %10lx: %10lx ", 
  825.                 (((struct freetrlr *)a)-1)->Front, a,a->Size);
  826. #ifdef IDENTIFY
  827.             ferr2("%10lx %10lx", a->caller, a->seqno);
  828. #endif
  829.             ferr2("%10lx %10lx\n", a->Next, a->Prev);
  830.         }
  831.         if (a<=olda) ferr1 ("Illegal pointer %lx\n", a);
  832.     }
  833. #endif
  834.     t = A.allocp;
  835.     do {
  836.         nfree++;
  837.         ASSERT("c1", t->Next->Prev==t);
  838.         if (testbit(t->Size, ACTIVE)) {
  839.             /* this is a segment trlr */
  840.             struct freetrlr *f 
  841.                 = (struct freetrlr *)(t+1);
  842.             ASSERT("c2", clearbits(t->Size)==0);
  843.             /* Segment must be a multiple
  844.                 of SEGGRAIN bytes: */
  845.             ASSERT("c3", ( (int)(f+1)-(int)(f->Front) )    /* \ */                %SEGGRAIN==0);
  846.             nfree -= (CheckSegment(m, f->Front, t));
  847.         }
  848.         else 
  849.             ASSERT("c4", t==PREVFRONT(NEXTBLOCK(t)));
  850.         t = t->Next;
  851.     } while (t!=A.allocp);
  852.     ASSERT("c5", nfree==0);
  853. #ifdef MSTATS
  854. return(TotFree+1);   /* an application may want to know this */
  855. #else
  856.     return(1);
  857. #endif     
  858. }
  859. static CheckSegment(m, f, t) 
  860. char *m;  
  861. register struct freehdr *f, *t; 
  862. {
  863.     register int nfree = 1;  /* count the trailer now */
  864.     register int wasactive = PREACTIVE;  /* value in first block */
  865.     register struct freehdr *pref=0;  /* for debugging */
  866. #ifdef MSTATS
  867. Nsegs++;
  868. #endif
  869.     for (; f<t; pref = f, 
  870.             f = (struct freehdr *)((char *)f 
  871.                 + clearbits(f->Size))) {
  872.         ASSERT("s1", clearbits(f->Size)>0);
  873.         ASSERT("s2", wasactive==testbit(f->Size, PREACTIVE));
  874.         if (!testbit(f->Size, ACTIVE)) 
  875.             nfree++, wasactive=0;
  876.         else 
  877.             wasactive = PREACTIVE;
  878. #ifdef MSTATS
  879.         if (!testbit(f->Size, ACTIVE)) {
  880.             Nfree++;
  881.             TotFree += clearbits(f->Size);
  882.         }
  883.         else {
  884.             Nactive++;
  885.             TotActive += clearbits(f->Size);
  886.         }
  887. #endif
  888.     }
  889.     ASSERT("s3", f==t);
  890.     return nfree;
  891. }
  892.  
  893. static
  894. botch(s)
  895. char *s;
  896. {
  897. /* don't want to use fprintf: it calls malloc! */
  898.     char *msg;
  899.     msg = "Malloc arena corruption discovered  at - "; 
  900.     if (stdout->_base) fflush(stdout);
  901.     if (stderr->_base) fflush(stderr);
  902.     write(2, msg, strlen(msg));
  903.     if (s) write(2, s, strlen(s));
  904.     write(2, "\n", 1);
  905.     abort();
  906. }
  907.  
  908.  
  909. #ifdef MSTATS
  910. mstats (m) char *m; {
  911.     double TotSpace;
  912.     long int TotHdrs;
  913.     int ActHdrs;
  914.  
  915.     ferr1("\nmstats - %s\n", m);
  916.  
  917.     if (CheckLevel>=5) DumpBlocks=1;
  918.     CheckAllocs("");  /* so Nsegs!=0 */
  919.     DumpBlocks = 0;
  920.     TotSpace = TotActive + TotFree + Nsegs*EPSILON;
  921.     ActHdrs = Nactive*sizeof(struct hdr);
  922.     TotHdrs = (TotActive ? TotFree * ActHdrs / TotActive : EPSILON);
  923.     TotFree -= TotHdrs;
  924.     TotActive -= ActHdrs;
  925.     TotHdrs += ActHdrs + Nsegs*EPSILON;
  926.  
  927.  
  928.     ferr4 ("%-10s%10s%10s%10s\n", "", "Active", "Free", "Segments");
  929.     ferr4 ("%-10s%10d%10d%10d\n", "requests", Nrequests, Nfrees, Nsbrk);
  930.     ferr4 ("%-10s%10d%10d%10d\n", "current", Nactive, Nfree, Nsegs);
  931.     ferr4 ("%-10s%10d%10d%10d\n",
  932.         "avg size", (Nactive ? TotActive/Nactive : 0), 
  933.         (Nfree ? TotFree/Nfree : 0), 
  934.         (int)TotSpace/Nsegs);
  935.     ferr3 ("%-10s%10.1f%10.3f\n",
  936.         "avg ops", 
  937.         (Nrequests ? ((float)Nscans)/Nrequests : 0.0),
  938.         (Nfrees ? ((float)Ncombines)/Nfrees : 0.0)); 
  939.     ferr3 ("%-10s%9.1f%%%9.1f%%\n",
  940.         "% space", 
  941.         100*TotActive/TotSpace,
  942.         100*TotFree/TotSpace);
  943.     ferr4 ("%s %d   %s%5.1f%%\n\n",
  944.         "total space", (int)TotSpace, 
  945.         "headers", 100*TotHdrs/TotSpace);
  946. }
  947. resetmstats() {
  948.     Nscans = Nrequests = Nsbrk = Ncombines = Nfrees = 0;
  949. }
  950. #else
  951. mstats() {}
  952. resetmstats() {}
  953. #endif
  954.  
  955.  
  956.  
  957. #include <sys/types.h>
  958. #include <sys/time.h>
  959.  
  960. AbortFullMessage (nbytes) 
  961. register unsigned int nbytes; 
  962. {
  963.     register siz, segbytes;
  964.     char buf[200];
  965.     char *maxBrk = (char *) ulimit( 3, 0 ) ;
  966.     char *oldBrk ;
  967.  
  968.     siz = (nbytes+sizeof(struct hdr)+(WORD-1))/WORD*WORD;
  969.     if (siz<EPSILON) siz = EPSILON;
  970.     segbytes = ((siz+2*EPSILON+(SEGGRAIN-1)) 
  971.             / SEGGRAIN) * SEGGRAIN;
  972.  
  973.     if ((int) (oldBrk = (char *) sbrk(0))+segbytes > maxBrk )
  974.         sprintf(buf, "Malloc abort.  Attempt to allocate %d bytes caused data segment to exceed its maximum of %d bytes.\n",
  975.             nbytes, maxBrk - oldBrk );
  976.     if (stdout->_base) fflush(stdout);
  977.     if (stderr->_base) fflush(stderr);
  978.     write(2, buf, strlen(buf));
  979.     return ;
  980. }
  981.  
  982. int (*
  983. SetM0Handler (p))() int (*p)(); {
  984.     int (*t)() = M0Handler;
  985.     M0Handler = (p==0) ? DefaultM0Handler : p;
  986.     return t;
  987. }
  988.  
  989. static int DefaultM0Handler (size) {
  990.     AbortFullMessage(size);
  991.     return (0);
  992. }
  993.  
  994.  
  995. SetMallocCheckLevel (level) int level; {
  996.     int old = CheckLevel;
  997.     CheckLevel = level;
  998.     return old;
  999. }
  1000.  
  1001. NewMallocArena() {
  1002.     A.arenastart = A.arenaend = A.allocp = 0;
  1003.     A.PendingFree = 0;
  1004.     A.InProgress = A.RecurringM0 = 0;
  1005.     A.arenahasbeenreset++;
  1006.     /* at present, it does not reset seqno */
  1007. }
  1008.  
  1009.     struct arenastate *
  1010. GetMallocArena () 
  1011. {
  1012.     return (&A);
  1013. }
  1014.