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