2.11BSD#431 - /usr/src/bin/tcsh/alloc11.c

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

Defined functions

Defined variables

Defined union's

Defined macros