2.9BSD - /usr/src/lib/c/gen/malloc.c

   1: /*	@(#)malloc.c	2.1	SCCS id keyword	*/
   2: #ifdef debug
   3: #define ASSERT(p) if(!(p))botch("p");else
   4: botch(s)
   5: char *s;
   6: {
   7:     printf("assertion botched: %s\n",s);
   8:     abort();
   9: }
  10: #else
  11: #define ASSERT(p)
  12: #endif
  13: 
  14: /*	avoid break bug */
  15: #ifdef pdp11
  16: #define GRANULE 64
  17: #else
  18: #define GRANULE 0
  19: #endif
  20: /*	C storage allocator
  21:  *	circular first-fit strategy
  22:  *	works with noncontiguous, but monotonically linked, arena
  23:  *	each block is preceded by a ptr to the (pointer of)
  24:  *	the next following block
  25:  *	blocks are exact number of words long
  26:  *	aligned to the data type requirements of ALIGN
  27:  *	pointers to blocks must have BUSY bit 0
  28:  *	bit in ptr is 1 for busy, 0 for idle
  29:  *	gaps in arena are merely noted as busy blocks
  30:  *	last block of arena (pointed to by alloct) is empty and
  31:  *	has a pointer to first
  32:  *	idle blocks are coalesced during space search
  33:  *
  34:  *	a different implementation may need to redefine
  35:  *	ALIGN, NALIGN, BLOCK, BUSY, INT
  36:  *	where INT is integer type to which a pointer can be cast
  37: */
  38: #define INT int
  39: #define ALIGN int
  40: #define NALIGN 1
  41: #define WORD sizeof(union store)
  42: #define BLOCK 1024  /* a multiple of WORD*/
  43: #define BUSY 1
  44: #define NULL 0
  45: #define testbusy(p) ((INT)(p)&BUSY)
  46: #define setbusy(p) (union store *)((INT)(p)|BUSY)
  47: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  48: 
  49: union store { union store *ptr;
  50:           ALIGN dummy[NALIGN];
  51:           int calloc;   /*calloc clears an array of integers*/
  52: };
  53: 
  54: static  union store allocs[2];  /*initial arena*/
  55: static  union store *allocp;    /*search ptr*/
  56: static  union store *alloct;    /*arena top*/
  57: static  union store *allocx;    /*for benefit of realloc*/
  58: char    *sbrk();
  59: 
  60: char *
  61: malloc(nbytes)
  62: unsigned nbytes;
  63: {
  64:     register union store *p, *q;
  65:     register nw;
  66:     static temp;    /*coroutines assume no auto*/
  67: 
  68:     if(allocs[0].ptr==0) {  /*first time*/
  69:         allocs[0].ptr = setbusy(&allocs[1]);
  70:         allocs[1].ptr = setbusy(&allocs[0]);
  71:         alloct = &allocs[1];
  72:         allocp = &allocs[0];
  73:     }
  74:     nw = (nbytes+WORD+WORD-1)/WORD;
  75:     ASSERT(allocp>=allocs && allocp<=alloct);
  76:     ASSERT(allock());
  77:     for(p=allocp; ; ) {
  78:         for(temp=0; ; ) {
  79:             if(!testbusy(p->ptr)) {
  80:                 while(!testbusy((q=p->ptr)->ptr)) {
  81:                     ASSERT(q>p&&q<alloct);
  82:                     p->ptr = q->ptr;
  83:                 }
  84:                 if(q>=p+nw && p+nw>=p)
  85:                     goto found;
  86:             }
  87:             q = p;
  88:             p = clearbusy(p->ptr);
  89:             if(p>q)
  90:                 ASSERT(p<=alloct);
  91:             else if(q!=alloct || p!=allocs) {
  92:                 ASSERT(q==alloct&&p==allocs);
  93:                 return(NULL);
  94:             } else if(++temp>1)
  95:                 break;
  96:         }
  97:         temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
  98:         q = (union store *)sbrk(0);
  99:         if(q+temp+GRANULE < q) {
 100:             return(NULL);
 101:         }
 102:         q = (union store *)sbrk(temp*WORD);
 103:         if((INT)q == -1) {
 104:             return(NULL);
 105:         }
 106:         ASSERT(q>alloct);
 107:         alloct->ptr = q;
 108:         if(q!=alloct+1)
 109:             alloct->ptr = setbusy(alloct->ptr);
 110:         alloct = q->ptr = q+temp-1;
 111:         alloct->ptr = setbusy(allocs);
 112:     }
 113: found:
 114:     allocp = p + nw;
 115:     ASSERT(allocp<=alloct);
 116:     if(q>allocp) {
 117:         allocx = allocp->ptr;
 118:         allocp->ptr = p->ptr;
 119:     }
 120:     p->ptr = setbusy(allocp);
 121:     return((char *)(p+1));
 122: }
 123: 
 124: /*	freeing strategy tuned for LIFO allocation
 125: */
 126: free(ap)
 127: register char *ap;
 128: {
 129:     register union store *p = (union store *)ap;
 130: 
 131:     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
 132:     ASSERT(allock());
 133:     allocp = --p;
 134:     ASSERT(testbusy(p->ptr));
 135:     p->ptr = clearbusy(p->ptr);
 136:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
 137: }
 138: 
 139: /*	realloc(p, nbytes) reallocates a block obtained from malloc()
 140:  *	and freed since last call of malloc()
 141:  *	to have new size nbytes, and old content
 142:  *	returns new location, or 0 on failure
 143: */
 144: 
 145: char *
 146: realloc(p, nbytes)
 147: register union store *p;
 148: unsigned nbytes;
 149: {
 150:     register union store *q;
 151:     union store *s, *t;
 152:     register unsigned nw;
 153:     unsigned onw;
 154: 
 155:     if(testbusy(p[-1].ptr))
 156:         free((char *)p);
 157:     onw = p[-1].ptr - p;
 158:     q = (union store *)malloc(nbytes);
 159:     if(q==NULL || q==p)
 160:         return((char *)q);
 161:     s = p;
 162:     t = q;
 163:     nw = (nbytes+WORD-1)/WORD;
 164:     if(nw<onw)
 165:         onw = nw;
 166:     while(onw--!=0)
 167:         *t++ = *s++;
 168:     if(q<p && q+nw>=p)
 169:         (q+(q+nw-p))->ptr = allocx;
 170:     return((char *)q);
 171: }
 172: 
 173: #ifdef debug
 174: allock()
 175: {
 176: #ifdef longdebug
 177:     register union store *p;
 178:     int x;
 179:     x = 0;
 180:     for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
 181:         if(p==allocp)
 182:             x++;
 183:     }
 184:     ASSERT(p==alloct);
 185:     return(x==1|p==allocp);
 186: #else
 187:     return(1);
 188: #endif
 189: }
 190: #endif

Defined functions

Defined variables

Defined union's

Defined macros