UNIX 7th Ed. - /usr/src/libI77/dballoc.c

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

Defined functions

Defined variables

Defined struct's

Defined macros