2.11BSD#431 - /usr/src/lib/libc/gen/malloc.c

   1: /*	@(#)malloc.c	2.3	(2.11BSD) 1999/1/18 */
   2: 
   3: #include <unistd.h>
   4: 
   5: #ifdef debug
   6: #include <sys/types.h>
   7: #include <sys/uio.h>
   8: 
   9: #define ASSERT(p) if(!(p))botch("p")
  10: 
  11: /*
  12:  * Can't use 'printf' below because that can call malloc().  If the malloc
  13:  * arena is corrupt malloc() calls botch() which calls printf which calls malloc
  14:  * ... result is a recursive loop which underflows the stack.
  15: */
  16: 
  17: static botch(s)
  18: char *s;
  19: {
  20:     struct  iovec   iov[3];
  21:     register struct iovec *v = iov;
  22:     char    *ab = "assertion botched: ";
  23: 
  24:     v->iov_base = ab;
  25:     v->iov_len = strlen(ab);
  26:     v++;
  27:     v->iov_base = s;
  28:     v->iov_len = strlen(s);
  29:     v++;
  30:     v->iov_base = "\n";
  31:     v->iov_len = 1;
  32: 
  33:     writev(STDOUT_FILENO, iov, 3);
  34:     abort();
  35: }
  36: #else
  37: #define ASSERT(p)
  38: #endif	/* debug */
  39: 
  40: /*
  41:  * The origins of the following ifdef are lost.  The only comment attached
  42:  * to it, "avoid break bug", probably has something to do with a bug in
  43:  * an older PDP-11 kernel.  Maybe it's still a bug in the current kernel.
  44:  * We'll probably never know ...
  45:  */
  46: #ifdef pdp11
  47: #	define GRANULE 64
  48: #else
  49: #	define GRANULE 0
  50: #endif
  51: 
  52: /*
  53:  * C storage allocator
  54:  *
  55:  * Uses circular first-fit strategy.  Works with a noncontiguous, but
  56:  * monotonically linked, arena.  Each block is preceded by a ptr to the
  57:  * pointer of the next following block.  Blocks are exact number of words
  58:  * long aligned to the data type requirements of ALIGN.
  59:  *
  60:  * Bit 0 (LSB) of pointers is used to indicate whether the block associated
  61:  * with the pointer is in use.  A 1 indicates a busy block and a 0 a free
  62:  * block (obviously pointers can't point at odd addresses).  Gaps in arena
  63:  * are merely noted as busy blocks.  The last block of the arena (pointed
  64:  * to by alloct) is empty and has a pointer to first.  Idle blocks are
  65:  * coalesced during space search
  66:  *
  67:  * Different implementations may need to redefine ALIGN, NALIGN, BLOCK,
  68:  * BUSY, INT where INT is integer type to which a pointer can be cast.
  69:  */
  70: #define INT     int
  71: #define ALIGN       int
  72: #define NALIGN      1
  73: #define WORD        sizeof(union store)
  74: #define BLOCK       1024    /* a multiple of WORD */
  75: 
  76: #define BUSY        1
  77: 
  78: #define testbusy(p) ((INT)(p)&BUSY)
  79: #define setbusy(p)  (union store *)((INT)(p)|BUSY)
  80: #define clearbusy(p)    (union store *)((INT)(p)&~BUSY)
  81: 
  82: union store {
  83:     union store *ptr;
  84:     ALIGN       dummy[NALIGN];
  85:     int     calloc; /* calloc clears an array of integers */
  86: };
  87: 
  88: static union store  allocs[2];  /* initial arena */
  89: static union store  *allocp;    /* search ptr */
  90: static union store  *alloct;    /* arena top */
  91: static union store  *allocx;    /* for benefit of realloc */
  92: 
  93: extern char     *sbrk();
  94: 
  95: char *
  96: malloc(nbytes)
  97:     unsigned nbytes;
  98: {
  99:     register union store *p, *q;
 100:     register nw;
 101:     static int temp;    /* coroutines assume no auto */
 102: 
 103:     if (nbytes == 0)
 104:         return(NULL);
 105:     if (allocs[0].ptr == 0) {   /* first time */
 106:         allocs[0].ptr = setbusy(&allocs[1]);
 107:         allocs[1].ptr = setbusy(&allocs[0]);
 108:         alloct = &allocs[1];
 109:         allocp = &allocs[0];
 110:     }
 111:     nw = (nbytes+WORD+WORD-1)/WORD;
 112:     ASSERT(allocp >= allocs && allocp <= alloct);
 113:     ASSERT(allock());
 114:     for (p = allocp; ; ) {
 115:         for (temp = 0; ; ) {
 116:             if (!testbusy(p->ptr)) {
 117:                 while(!testbusy((q = p->ptr)->ptr)) {
 118:                     ASSERT(q > p && q < alloct);
 119:                     p->ptr = q->ptr;
 120:                 }
 121:                 if (q >= p+nw && p+nw >= p)
 122:                     goto found;
 123:             }
 124:             q = p;
 125:             p = clearbusy(p->ptr);
 126:             if (p > q)
 127:                 ASSERT(p <= alloct);
 128:             else if (q != alloct || p != allocs) {
 129:                 ASSERT(q == alloct && p == allocs);
 130:                 return(NULL);
 131:             } else if (++temp > 1)
 132:                 break;
 133:         }
 134:         q = (union store *)sbrk(0);
 135:         /*
 136: 		 * Line up on page boundry so we can get the last drip at
 137: 		 * the end ...
 138: 		 */
 139:         temp = ((((unsigned)q + WORD*nw + BLOCK-1)/BLOCK)*BLOCK
 140:             - (unsigned)q) / WORD;
 141:         if (q+temp+GRANULE < q)
 142:             return(NULL);
 143:         q = (union store *)sbrk(temp*WORD);
 144:         if ((INT)q == -1)
 145:             return(NULL);
 146:         ASSERT(q > alloct);
 147:         alloct->ptr = q;
 148:         if (q != alloct+1)
 149:             alloct->ptr = setbusy(alloct->ptr);
 150:         alloct = q->ptr = q+temp-1;
 151:         alloct->ptr = setbusy(allocs);
 152:     }
 153: found:
 154:     allocp = p + nw;
 155:     ASSERT(allocp <= alloct);
 156:     if (q > allocp) {
 157:         allocx = allocp->ptr;
 158:         allocp->ptr = p->ptr;
 159:     }
 160:     p->ptr = setbusy(allocp);
 161:     return((char *)(p+1));
 162: }
 163: 
 164: /*
 165:  * Freeing strategy tuned for LIFO allocation.
 166:  */
 167: free(ap)
 168:     register char *ap;
 169: {
 170:     register union store *p = (union store *)ap;
 171: 
 172:     ASSERT(p > clearbusy(allocs[1].ptr) && p <= alloct);
 173:     ASSERT(allock());
 174:     allocp = --p;
 175:     ASSERT(testbusy(p->ptr));
 176:     p->ptr = clearbusy(p->ptr);
 177:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
 178: }
 179: 
 180: /*
 181:  * Realloc(p, nbytes) reallocates a block obtained from malloc() and freed
 182:  * since last call of malloc() to have new size nbytes, and old content
 183:  * returns new location, or 0 on failure.
 184:  */
 185: char *
 186: realloc(p, nbytes)
 187:     register union store *p;
 188:     unsigned nbytes;
 189: {
 190:     register union store *q;
 191:     union store *s, *t;
 192:     register unsigned nw;
 193:     unsigned onw;
 194: 
 195:     if (testbusy(p[-1].ptr))
 196:         free((char *)p);
 197:     onw = p[-1].ptr - p;
 198:     q = (union store *)malloc(nbytes);
 199:     if (q == NULL || q == p)
 200:         return((char *)q);
 201:     s = p;
 202:     t = q;
 203:     nw = (nbytes+WORD-1)/WORD;
 204:     if (nw < onw)
 205:         onw = nw;
 206:     while (onw-- != 0)
 207:         *t++ = *s++;
 208:     if (q < p && q+nw >= p)
 209:         (q+(q+nw-p))->ptr = allocx;
 210:     return((char *)q);
 211: }
 212: 
 213: #ifdef  debug
 214: static allock()
 215: {
 216: #ifdef longdebug
 217:     register union store *p;
 218:     int x;
 219:     x = 0;
 220:     for (p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
 221:         if (p == allocp)
 222:             x++;
 223:     }
 224:     ASSERT(p == alloct);
 225:     return((x == 1) | (p == allocp));
 226: #else
 227:     return(1);
 228: #endif
 229: }
 230: #endif /* debug */

Defined functions

Defined variables

Defined union's

Defined macros