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