| 1 | static char *sccsid = "@(#)alloc.c 4.1 10/9/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 |