![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to cmalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / trace|
Return to cmalloc.c CVS log | Up to [Research Unix] / researchv10no / cmd / trace |
1.1 ! root 1: #ifdef debug ! 2: #define ASSERT(p) if(!(p))botch("p");else ! 3: botch(s) ! 4: char *s; ! 5: { ! 6: printf("assertion botched: %s\n",s); ! 7: abort(); ! 8: } ! 9: #else ! 10: #define ASSERT(p) ! 11: #endif ! 12: ! 13: /* C storage allocator ! 14: * circular first-fit strategy ! 15: * works with noncontiguous, but monotonically linked, arena ! 16: * each block is preceded by a ptr to the (pointer of) ! 17: * the next following block ! 18: * blocks are exact number of words long ! 19: * aligned to the data type requirements of ALIGN ! 20: * pointers to blocks must have BUSY bit 0 ! 21: * bit in ptr is 1 for busy, 0 for idle ! 22: * gaps in arena are merely noted as busy blocks ! 23: * last block of arena is empty and ! 24: * has a pointer to first ! 25: * idle blocks are coalesced during space search ! 26: * ! 27: * a different implementation may need to redefine ! 28: * ALIGN, NALIGN, BLOCK, BUSY, INT ! 29: * where INT is integer type to which a pointer can be cast ! 30: */ ! 31: #define INT int ! 32: #define ALIGN int ! 33: #define NALIGN 1 ! 34: #define WORD sizeof(union store) ! 35: #define BLOCK 1024 ! 36: #define BUSY 1 ! 37: #define NULL 0 ! 38: #define testbusy(p) ((INT)(p)&BUSY) ! 39: #define setbusy(p) (union store *)((INT)(p)|BUSY) ! 40: #define clearbusy(p) (union store *)((INT)(p)&~BUSY) ! 41: ! 42: union store { ! 43: union store *ptr; ! 44: ALIGN dummy[NALIGN]; ! 45: int calloc; /*calloc clears an array of integers*/ ! 46: }; ! 47: ! 48: static union store alloca; /* initial arena */ ! 49: static union store *allocb = &alloca; /*arena base*/ ! 50: static union store *allocp = &alloca; /*search ptr*/ ! 51: static union store *alloct = &alloca; /*arena top; for speedier ialloc*/ ! 52: static union store allocx, allocy; /*for benefit of realloc*/ ! 53: extern char *sbrk(); ! 54: ! 55: /* a cache list of frequently-used sizes is maintained. From each ! 56: * cache entry hangs a chain of available blocks (marked busy ! 57: * to keep out of the first fit search) ! 58: */ ! 59: #define CACHEMAX 100 /* largest block to be cached (in words) */ ! 60: #ifndef pdp11 ! 61: #define CACHESIZ 13 /* number of entries (prime) */ ! 62: #else ! 63: #define CACHESIZ 0 ! 64: #endif ! 65: static struct cache { ! 66: int size; ! 67: union store *chain; ! 68: } cache[CACHESIZ]; ! 69: ! 70: char * ! 71: malloc(nbytes) ! 72: unsigned nbytes; ! 73: { ! 74: register union store *p, *q; ! 75: register nw; ! 76: register temp; ! 77: register struct cache *cp; ! 78: ! 79: ASSERT(allock(allocp)&1); ! 80: nw = (nbytes+WORD+WORD-1)/WORD; ! 81: if(CACHESIZ && nw<CACHEMAX && nw>2) { /* see note + below */ ! 82: cp = cache + nw%CACHESIZ; ! 83: p = cp->chain; ! 84: if(p && nw==cp->size) { ! 85: cp->chain = p[1].ptr; ! 86: ASSERT(testbusy(p->ptr)); ! 87: ASSERT(clearbusy(p->ptr)-p==nw); ! 88: return (char*)(p+1); ! 89: } ! 90: } ! 91: ASSERT(allock(allocp)&3); ! 92: for(; ; ) { /* done at most twice */ ! 93: p = allocp; ! 94: if(alloca.ptr!=0) /*C can't initialize union*/ ! 95: for(temp=0; ; ) { ! 96: if(!testbusy(p->ptr)) { ! 97: while(!testbusy((q=p->ptr)->ptr)) { ! 98: ASSERT(q>p); ! 99: p->ptr = q->ptr; ! 100: } ! 101: allocp = p; ! 102: if(q>=p+nw && p+nw>=p) /*room; no wrap*/ ! 103: goto found; ! 104: } ! 105: q = p; ! 106: p = clearbusy(p->ptr); ! 107: if(p <= q) { ! 108: ASSERT(p==allocb); ! 109: if(++temp>1) ! 110: break; ! 111: } ! 112: } ! 113: temp = nw; ! 114: p = (union store *)sbrk(0); ! 115: q = allocp->ptr; ! 116: if(!testbusy(q) && q+1 == p) ! 117: temp -= p - allocp; ! 118: temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD); ! 119: if(p+temp <= p) ! 120: return(NULL); ! 121: for( ; ; ) { ! 122: register s; ! 123: q = (union store *)sbrk(temp*WORD); ! 124: if((INT)q != -1) ! 125: break; ! 126: for(cp=cache; cp<cache+CACHESIZ; cp++) { ! 127: for(p=cp->chain; p; p=p[1].ptr) { ! 128: ASSERT(testbusy(p->ptr)); ! 129: p->ptr = clearbusy(p->ptr); ! 130: ASSERT(p->ptr-p==cp->size); ! 131: } ! 132: cp->chain = 0; ! 133: } ! 134: s = (temp-nw)/2; ! 135: if(s <= 0) ! 136: return(NULL); ! 137: temp -= s; ! 138: } ! 139: ialloc((char *)q, (unsigned)temp*WORD); ! 140: } ! 141: found: ! 142: q = p + nw; ! 143: if(p->ptr > q) { ! 144: allocx = *q; ! 145: q->ptr = p->ptr; ! 146: } ! 147: p->ptr = setbusy(q); ! 148: ASSERT(allock(allocp)&7); ! 149: return((char *)(p+1)); ! 150: } ! 151: /* + note CACHESIZ is tested for conditional compilation; nw>2 assumes there's ! 152: * no point in caching smaller sizes (they are rarely used and always ! 153: * can be allocated) and protects against the old storage compaction trick: ! 154: * free(p); free(dummy);dummy=malloc(1);realloc(p) ! 155: * (otherwise free(dummy) would destroy allocy, which pertains to p) ! 156: */ ! 157: ! 158: /* freeing strategy tuned for LIFO allocation ! 159: */ ! 160: free(ap) ! 161: char *ap; ! 162: { ! 163: register union store *p = (union store *)ap, *q; ! 164: register nw; ! 165: register struct cache *cp; ! 166: ! 167: --p; ! 168: ASSERT(allock(p)); ! 169: ASSERT(testbusy(p->ptr)); ! 170: nw = clearbusy(p->ptr) - p; ! 171: ASSERT(nw>0); ! 172: if(CACHESIZ && nw<CACHEMAX && nw>2) { ! 173: cp = cache + nw%CACHESIZ; ! 174: if(nw != cp->size) { ! 175: q = cp->chain; ! 176: if(q) { ! 177: ASSERT(testbusy(q->ptr)); ! 178: q->ptr = clearbusy(q->ptr); ! 179: ASSERT(q->ptr-q==cp->size); ! 180: cp->chain = q[1].ptr; ! 181: } ! 182: if(!q) ! 183: cp->size = nw; ! 184: else ! 185: goto nocache; ! 186: } ! 187: allocy = p[1]; ! 188: p[1].ptr = cp->chain; ! 189: cp->chain = p; ! 190: ASSERT(allock(allocp)&017); ! 191: return; ! 192: } ! 193: nocache: ! 194: allocp = p; ! 195: p->ptr = clearbusy(p->ptr); ! 196: ASSERT(allock(allocp)&037); ! 197: ASSERT(p->ptr<=alloct); ! 198: } ! 199: ! 200: /* ialloc(q, nbytes) inserts a block that did not come ! 201: * from malloc into the arena ! 202: * ! 203: * q points to new block ! 204: * r points to last of new block ! 205: * p points to last cell of arena before new block ! 206: * s points to first cell of arena after new block ! 207: */ ! 208: ialloc(qq, nbytes) ! 209: char *qq; ! 210: unsigned nbytes; ! 211: { ! 212: register union store *p, *q, *s; ! 213: union store *r; ! 214: ! 215: q = (union store *)qq; ! 216: r = q + (nbytes/WORD) - 1; ! 217: q->ptr = r; ! 218: if(alloca.ptr==0) /*C can't initialize union*/ ! 219: alloca.ptr = &alloca; ! 220: if(q > alloct) { ! 221: p = alloct; ! 222: alloct = r; ! 223: } else ! 224: allocp = p = allocb; ! 225: for( ; ; p=s) { ! 226: s = clearbusy(p->ptr); ! 227: if(s==allocb) ! 228: break; ! 229: ASSERT(s>p); ! 230: if(s>r) { ! 231: if(p<q) ! 232: break; ! 233: else ! 234: ASSERT(p>r); ! 235: } ! 236: } ! 237: p->ptr = q==p+1? q: setbusy(q); ! 238: r->ptr = s==r+1? s: setbusy(s); ! 239: if(allocb > q) ! 240: allocp = allocb = q; ! 241: } ! 242: ! 243: /* realloc(p, nbytes) reallocates a block obtained from malloc() ! 244: * and freed since last call of malloc() ! 245: * to have new size nbytes, and old content ! 246: * returns new location, or 0 on failure ! 247: */ ! 248: ! 249: char * ! 250: realloc(pp, nbytes) ! 251: char *pp; ! 252: unsigned nbytes; ! 253: { ! 254: register union store *q; ! 255: register union store *p = (union store *)pp; ! 256: register union store *s, *t; ! 257: register unsigned nw; ! 258: struct cache *cp; ! 259: unsigned onw; ! 260: ! 261: q = p-1; ! 262: ASSERT(allock(q)); ! 263: if(testbusy(q->ptr)) { ! 264: allocp = q; ! 265: q->ptr = clearbusy(q->ptr); ! 266: if(CACHESIZ) { ! 267: nw = q->ptr - q; ! 268: cp = cache + nw%CACHESIZ; ! 269: if(cp->chain==q) { ! 270: ASSERT(cp->size==nw); ! 271: cp->chain = p->ptr; /*p->ptr==q[1].ptr*/ ! 272: *p = allocy; ! 273: } else ! 274: ASSERT(notonchain(q,cp->chain)); ! 275: } ! 276: } ! 277: onw = q->ptr - p; ! 278: q = (union store *)malloc(nbytes); ! 279: if(q==NULL || q==p) ! 280: return((char *)q); ! 281: ASSERT(q<p||q>p[-1].ptr); ! 282: s = p; ! 283: t = q; ! 284: nw = (nbytes+WORD-1)/WORD; ! 285: if(nw<onw) ! 286: onw = nw; ! 287: while(onw--!=0) ! 288: *t++ = *s++; ! 289: ASSERT(clearbusy(q[-1].ptr)-q==nw); ! 290: if(q<p && q+nw>=p) ! 291: q[q+nw-p] = allocx; ! 292: ASSERT(allock(q-1)); ! 293: return((char *)q); ! 294: } ! 295: ! 296: #ifdef debug ! 297: ! 298: notonchain(p,q) ! 299: union store *p, *q; ! 300: { ! 301: for(;q; q=clearbusy(q->ptr)) ! 302: if(q==p) ! 303: return 0; ! 304: return 1; ! 305: } ! 306: ! 307: allock(q) ! 308: union store *q; ! 309: { ! 310: #ifdef longdebug ! 311: register union store *p, *r; ! 312: int x; ! 313: for(x=0; x<CACHESIZ; x++) { ! 314: p = cache[x].chain; ! 315: if(p==0) ! 316: continue; ! 317: for( ; p; p=p[1].ptr) { ! 318: ASSERT(testbusy(p->ptr)); ! 319: ASSERT(clearbusy(p->ptr)-p==cache[x].size); ! 320: } ! 321: } ! 322: x = 0; ! 323: p = allocb; ! 324: if(alloca.ptr==0) ! 325: return(1); ! 326: for( ; (r=clearbusy(p->ptr)) > p; p=r) { ! 327: if(p==q) ! 328: x++; ! 329: } ! 330: return(r==allocb&(x==1|p==q)); ! 331: #else ! 332: return(q>=allocb); ! 333: #endif ! 334: } ! 335: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.