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

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

Defined functions

Defined variables

Defined union's

Defined macros