usr/src/cmd/spell/malloc.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  23 /*        All Rights Reserved   */
  24
  25
  26 #ident  "%Z%%M% %I%     %E% SMI"        /* SVr4.0 1.3   */
  27 #ifdef debug
  28 #define ASSERT(p) if(!(p))botch("p");else
  29 botch(s)
  30 char *s;
  31 {
  32         printf("assertion botched: %s\n",s);
  33         abort();
  34 }
  35 #else
  36 #define ASSERT(p)
  37 #endif
  38
  39 /*      C storage allocator
  40  *      circular first-fit strategy
  41  *      works with noncontiguous, but monotonically linked, arena
  42  *      each block is preceded by a ptr to the (pointer of)
  43  *      the next following block
  44  *      blocks are exact number of words long
  45  *      aligned to the data type requirements of ALIGN
  46  *      pointers to blocks must have BUSY bit 0
  47  *      bit in ptr is 1 for busy, 0 for idle
  48  *      gaps in arena are merely noted as busy blocks
  49  *      last block of arena is empty and
  50  *      has a pointer to first
  51  *      idle blocks are coalesced during space search
  52  *
  53  *      a different implementation may need to redefine
  54  *      ALIGN, NALIGN, BLOCK, BUSY, INT
  55  *      where INT is integer type to which a pointer can be cast
  56 */
  57 #define INT int
  58 #define ALIGN int
  59 #define NALIGN 1
  60 #define WORD sizeof(union store)
  61 #define BLOCK 1024
  62 #define BUSY 1
  63 #define NULL 0
  64 #define testbusy(p) ((INT)(p)&BUSY)
  65 #define setbusy(p) (union store *)((INT)(p)|BUSY)
  66 #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  67
  68 union store {
  69               union store *ptr;
  70               ALIGN dummy[NALIGN];
  71               int calloc;       /*calloc clears an array of integers*/
  72 };
  73
  74 static  union store alloca;     /* initial arena */
  75 static  union store *allocb = &alloca;  /*arena base*/
  76 static  union store *allocp = &alloca;  /*search ptr*/
  77 static  union store *allocx;    /*for benefit of realloc*/
  78 extern  char *sbrk();
  79
  80 char *
  81 malloc(nbytes)
  82 unsigned nbytes;
  83 {
  84         register union store *p, *q;
  85         register nw;
  86         register temp;
  87         register union store *r = 0;
  88
  89         nw = (nbytes+WORD+WORD-1)/WORD + 1;     /*need one more than asked for*/
  90         ASSERT(allock(allocp));
  91         for(; ; ) {     /* done at most twice */
  92                 p = allocp;
  93                 if(alloca.ptr!=0)               /*C can't initialize union*/
  94                 for(temp=0; ; ) {
  95                         if(!testbusy(p->ptr)) {
  96                                 while(!testbusy((q=p->ptr)->ptr)) {
  97                                         ASSERT(q>p);
  98                                         p->ptr = q->ptr;
  99                                         allocp = p;
 100                                 }
 101                                 if(q>=p+nw && p+nw>=p)
 102                                         goto found;
 103                                 r = p;
 104                         }
 105                         q = p;
 106                         p = clearbusy(p->ptr);
 107                         if(p <= q) {
 108                                 ASSERT(p==allocb);
 109                                 if(p != allocb)
 110                                         return(NULL);
 111                                 if(++temp>1)
 112                                         break;
 113                         }
 114                 }
 115                 temp = nw;
 116                 p = (union store *)sbrk(0);
 117                 if (r && !testbusy(r->ptr) && r->ptr + 1 == p)
 118                         temp -= p - r - 1;
 119                 temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
 120                 if(p+temp <= p)
 121                         return(NULL);
 122                 for(; ; ) {
 123                         q = (union store *)sbrk(temp*WORD);
 124                         if((INT)q != -1)
 125                                 break;
 126                         temp -= (temp-nw+1)/2;
 127                         if(temp <= nw)
 128                                 return(NULL);
 129                 }
 130                 ialloc((char *)q, (unsigned)temp*WORD);
 131         }
 132 found:
 133         allocp = p + nw;
 134         if(q>allocp) {
 135                 allocx = allocp->ptr;
 136                 allocp->ptr = p->ptr;
 137         }
 138         p->ptr = setbusy(allocp);
 139         return((char *)(p+1));
 140 }
 141
 142 /*      freeing strategy tuned for LIFO allocation
 143 */
 144 free(ap)
 145 char *ap;
 146 {
 147         register union store *p = (union store *)ap;
 148
 149         allocp = --p;
 150         ASSERT(allock(allocp));
 151         ASSERT(testbusy(p->ptr));
 152         p->ptr = clearbusy(p->ptr);
 153         ASSERT(p->ptr > allocp);
 154 }
 155
 156 /* ialloc(q, nbytes) inserts a block that did not come
 157  * from malloc into the arena
 158  *
 159  * q points to new block
 160  * r points to last of new block
 161  * p points to last cell of arena before new block
 162  * s points to first cell of arena after new block
 163 */
 164 ialloc(qq, nbytes)
 165 char *qq;
 166 unsigned nbytes;
 167 {
 168         register union store *p, *q, *s;
 169         union store *r;
 170
 171         q = (union store *)qq;
 172         r = q + (nbytes/WORD) - 1;
 173         q->ptr = r;
 174         if(alloca.ptr==0)               /*C can't initialize union*/
 175                 alloca.ptr = &alloca;
 176         for(p=allocb; ; p=s) {
 177                 s = clearbusy(p->ptr);
 178                 if(s==allocb)
 179                         break;
 180                 ASSERT(s>p);
 181                 if(s>r) {
 182                         if(p<q)
 183                                 break;
 184                         else
 185                                 ASSERT(p>r);
 186                 }
 187         }
 188         p->ptr = q==p+1? q: setbusy(q);
 189         r->ptr = s==r+1? s: setbusy(s);
 190         if(allocb > q)
 191                 allocb = q;
 192         allocp = allocb;
 193 }
 194
 195 /*      realloc(p, nbytes) reallocates a block obtained from malloc()
 196  *      and freed since last call of malloc()
 197  *      to have new size nbytes, and old content
 198  *      returns new location, or 0 on failure
 199 */
 200
 201 char *
 202 realloc(pp, nbytes)
 203 char *pp;
 204 unsigned nbytes;
 205 {
 206         register union store *q;
 207         register union store *p = (union store *)pp;
 208         union store *s, *t;
 209         register unsigned nw;
 210         unsigned onw;
 211
 212         ASSERT(allock(p-1));
 213         if(testbusy(p[-1].ptr))
 214                 free((char *)p);
 215         onw = p[-1].ptr - p;
 216         q = (union store *)malloc(nbytes);
 217         if(q==NULL || q==p)
 218                 return((char *)q);
 219         ASSERT(q<p||q>p[-1].ptr);
 220         s = p;
 221         t = q;
 222         nw = (nbytes+WORD-1)/WORD;
 223         if(nw<onw)
 224                 onw = nw;
 225         while(onw--!=0)
 226                 *t++ = *s++;
 227         ASSERT(clearbusy(q[-1].ptr)-q==nw);
 228         if(q<p && q+nw>=p)
 229                 (q+(q+nw-p))->ptr = allocx;
 230         ASSERT(allock(q-1));
 231         return((char *)q);
 232 }
 233
 234 #ifdef debug
 235 allock(q)
 236 union store *q;
 237 {
 238 #ifdef longdebug
 239         register union store *p, *r;
 240         int x;
 241         x = 0;
 242         p = allocb;
 243         if(alloca.ptr==0)
 244                 return(1);
 245         for( ; (r=clearbusy(p->ptr)) > p; p=r) {
 246                 if(p==q)
 247                         x++;
 248         }
 249         return(r==allocb&(x==1|p==q));
 250 #else
 251         return(q>=allocb);
 252 #endif
 253 }
 254 #endif
 255