2.9BSD - /usr/src/ucb/oldcsh/alloc.c

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

Defined functions

Defined variables

Defined union's

Defined macros