2.9BSD - /usr/src/cmd/f77/malloc.c

   1: #define ASSERT(p) if(!(p))botch("p");else
   2: botch(s)
   3: char *s;
   4: {
   5:     printf("assertion botched: %s\n",s);
   6:     abort();
   7: }
   8: /*	C storage allocator
   9:  *	circular first-fit strategy
  10:  *	works with noncontiguous, but monotonically linked, arena
  11:  *	each block is preceded by a ptr to the (pointer of)
  12:  *	the next following block
  13:  *	blocks are exact number of words long; BUSY
  14:  *	bit in ptr is 1 for busy, 0 for idle
  15:  *	gaps in arena are merely noted as busy blocks
  16:  *	last block of arena (pointed to by alloct) is empty and
  17:  *	has a pointer to first
  18:  *	idle blocks are coalesced during space search
  19: */
  20: /*	all these defines must be powers of 2 */
  21: #define WORD sizeof(struct store)
  22: #define BLOCK 1024
  23: #define BUSY 1
  24: #define NULL 0
  25: #define testbusy(p) ((int)(p)&BUSY)
  26: #define setbusy(p) ((int)(p)+BUSY)
  27: #define clearbusy(p) ((int)(p)&~BUSY)
  28: 
  29: struct store { struct store *ptr; };
  30: 
  31: struct store allocs[] = {   /*initial arena*/
  32:     setbusy(&allocs[1].ptr),
  33:     setbusy(&allocs[0].ptr)
  34: };
  35: struct store *allocp = &allocs[1];  /*search ptr*/
  36: struct store *alloct = &allocs[1];  /*arena top*/
  37: struct store *allocx;       /*for benefit of realloc*/
  38: struct store *sbrk();
  39: 
  40: struct store *
  41: malloc(nbytes)
  42: unsigned nbytes;
  43: {
  44:     register struct store *p, *q;
  45:     register nw;
  46:     static temp;    /*coroutines assume no auto*/
  47: 
  48:     nw = (nbytes+2*WORD-1)/WORD;
  49:     ASSERT(allocp>allocs && allocp<=alloct);
  50:     for(p=allocp; ; ) {
  51:         for(temp=0; ; ) {
  52:             if(!testbusy(p->ptr)) {
  53:                 while(!testbusy((q=p->ptr)->ptr)) {
  54:                     ASSERT(q>p&&q<alloct);
  55:                     p->ptr = q->ptr;
  56:                 }
  57:                 if(q>=p+nw && p+nw>=p)
  58:                     goto found;
  59:             }
  60:             q = p;
  61:             p = clearbusy(p->ptr);
  62:             if(p>q)
  63:                 ASSERT(p<=alloct);
  64:             else if(q!=alloct || p!=allocs) {
  65:                 write(2,"corrupt arena\n",14);
  66:                 exit(0175);
  67:             } else if(++temp>1)
  68:                 break;
  69:         }
  70:         temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
  71:         q = sbrk(0);
  72:         if(q+temp < q)
  73:             return(NULL);
  74:         q = sbrk(temp*WORD);
  75:         if((int)q == -1)
  76:             return(NULL);
  77:         ASSERT(q>alloct);
  78:         alloct->ptr = q;
  79:         if(q!=alloct+1)
  80:             alloct->ptr = setbusy(alloct->ptr);
  81:         alloct = q->ptr = q+temp-1;
  82:         alloct->ptr = setbusy(allocs);
  83:     }
  84: found:
  85:     allocp = p + nw;
  86:     ASSERT(allocp<=alloct);
  87:     if(q>allocp) {
  88:         allocx = allocp->ptr;
  89:         allocp->ptr = p->ptr;
  90:     }
  91:     p->ptr = setbusy(allocp);
  92:     return(p+1);
  93: }
  94: /*	freeing strategy tuned for LIFO allocation
  95: */
  96: free(p)
  97: register struct store *p;
  98: {
  99:     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
 100:     allocp = --p;
 101:     ASSERT(testbusy(p->ptr));
 102:     p->ptr = clearbusy(p->ptr);
 103:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
 104: }
 105: struct { unsigned tag:4, vtype:4;};
 106: 
 107: 
 108: prbusy()
 109: {
 110:     register struct store *p, *q;
 111: 
 112:     ASSERT(allocp>allocs && allocp<=alloct);
 113:     for(p=allocs; ; ) {
 114:             if(testbusy(p->ptr))
 115:                 {
 116:                 printf("busy 0%o, tag %d, type %d, length %d\n",
 117:                     p, p[1].tag, p[1].vtype,
 118:                     clearbusy(p->ptr) - (int) p - 2 );
 119:                 }
 120:             q = p;
 121:             p = clearbusy(p->ptr);
 122:             if(p>q)
 123:                 ASSERT(p<=alloct);
 124:             else if(q!=alloct || p!=allocs)
 125:                 {
 126:                 write(2,"corrupt arena\n",14);
 127:                 exit(0175);
 128:                 }
 129:             else return;
 130:     }
 131: }

Defined functions

Defined variables

Defined struct's

Defined macros