From fc71ebc64de1740352d2ad3cfe21d99beac57f8c Mon Sep 17 00:00:00 2001 From: Bill Joy Date: Thu, 9 Oct 1980 20:39:55 -0800 Subject: [PATCH 1/1] date and time created 80/10/09 12:39:55 by bill SCCS-vsn: bin/csh/alloc.c 4.1 --- usr/src/bin/csh/alloc.c | 216 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 216 insertions(+) create mode 100644 usr/src/bin/csh/alloc.c diff --git a/usr/src/bin/csh/alloc.c b/usr/src/bin/csh/alloc.c new file mode 100644 index 0000000000..bf80f966a8 --- /dev/null +++ b/usr/src/bin/csh/alloc.c @@ -0,0 +1,216 @@ +static char *sccsid = "@(#)alloc.c 4.1 %G%"; + +#include "sh.local.h" +#ifdef debug +#define ASSERT(p) if(!(p))botch("p");else +botch(s) +char *s; +{ + printf("assertion botched: %s\n",s); + abort(); +} +#else +#define ASSERT(p) +#endif + +/* avoid break bug */ +#ifdef pdp11 +#define GRANULE 64 +#else +#define GRANULE 0 +#endif +/* C storage allocator + * circular first-fit strategy + * works with noncontiguous, but monotonically linked, arena + * each block is preceded by a ptr to the (pointer of) + * the next following block + * blocks are exact number of words long + * aligned to the data type requirements of ALIGN + * pointers to blocks must have BUSY bit 0 + * bit in ptr is 1 for busy, 0 for idle + * gaps in arena are merely noted as busy blocks + * last block of arena (pointed to by alloct) is empty and + * has a pointer to first + * idle blocks are coalesced during space search + * + * a different implementation may need to redefine + * ALIGN, NALIGN, BLOCK, BUSY, INT + * where INT is integer type to which a pointer can be cast +*/ +#define INT int +#define ALIGN int +#define NALIGN 1 +#define WORD sizeof(union store) +#define BLOCK 1024 /* a multiple of WORD*/ +#define BUSY 1 +#define NULL 0 +#define testbusy(p) ((INT)(p)&BUSY) +#define setbusy(p) (union store *)((INT)(p)|BUSY) +#define clearbusy(p) (union store *)((INT)(p)&~BUSY) + +union store { union store *ptr; + ALIGN dummy[NALIGN]; + int calloc; /*calloc clears an array of integers*/ +}; + +static union store allocs[2]; /*initial arena*/ +static union store *allocp; /*search ptr*/ +static union store *alloct; /*arena top*/ +static union store *allocx; /*for benefit of realloc*/ +char *sbrk(); + +char * +malloc(nbytes) +unsigned nbytes; +{ + register union store *p, *q; + register nw; + static temp; /*coroutines assume no auto*/ + + if(allocs[0].ptr==0) { /*first time*/ + allocs[0].ptr = setbusy(&allocs[1]); + allocs[1].ptr = setbusy(&allocs[0]); + alloct = &allocs[1]; + allocp = &allocs[0]; + } + nw = (nbytes+WORD+WORD-1)/WORD; + ASSERT(allocp>=allocs && allocp<=alloct); + ASSERT(allock()); + for(p=allocp; ; ) { + for(temp=0; ; ) { + if(!testbusy(p->ptr)) { + while(!testbusy((q=p->ptr)->ptr)) { + ASSERT(q>p&&qptr = q->ptr; + } + if(q>=p+nw && p+nw>=p) + goto found; + } + q = p; + p = clearbusy(p->ptr); + if(p>q) + ASSERT(p<=alloct); + else if(q!=alloct || p!=allocs) { + ASSERT(q==alloct&&p==allocs); + return(NULL); + } else if(++temp>1) + break; + } + temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD); + q = (union store *)sbrk(0); + if(q+temp+GRANULE < q) { + return(NULL); + } + q = (union store *)sbrk(temp*WORD); + if((INT)q == -1) { + return(NULL); + } + ASSERT(q>alloct); + alloct->ptr = q; + if(q!=alloct+1) + alloct->ptr = setbusy(alloct->ptr); + alloct = q->ptr = q+temp-1; + alloct->ptr = setbusy(allocs); + } +found: + allocp = p + nw; + ASSERT(allocp<=alloct); + if(q>allocp) { + allocx = allocp->ptr; + allocp->ptr = p->ptr; + } + p->ptr = setbusy(allocp); + return((char *)(p+1)); +} + +/* freeing strategy tuned for LIFO allocation +*/ +free(ap) +register char *ap; +{ + register union store *p = (union store *)ap; + + ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct); + ASSERT(allock()); + allocp = --p; +/* ASSERT(testbusy(p->ptr)); */ + p->ptr = clearbusy(p->ptr); + ASSERT(p->ptr > allocp && p->ptr <= alloct); +} + +/* realloc(p, nbytes) reallocates a block obtained from malloc() + * and freed since last call of malloc() + * to have new size nbytes, and old content + * returns new location, or 0 on failure +*/ + +char * +realloc(p, nbytes) +register union store *p; +unsigned nbytes; +{ + register union store *q; + union store *s, *t; + register unsigned nw; + unsigned onw; + + if(testbusy(p[-1].ptr)) + free((char *)p); + onw = p[-1].ptr - p; + q = (union store *)malloc(nbytes); + if(q==NULL || q==p) + return((char *)q); + s = p; + t = q; + nw = (nbytes+WORD-1)/WORD; + if(nw=p) + (q+(q+nw-p))->ptr = allocx; + return((char *)q); +} + +#ifdef debug +allock() +{ +#ifdef longdebug + register union store *p; + int x; + x = 0; + for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) { + if(p==allocp) + x++; + } + ASSERT(p==alloct); + return(x==1|p==allocp); +#else + return(1); +#endif +} +#endif + +#ifdef debug +showall(v) + char **v; +{ + register union store *p, *q; + int used = 0, free = 0, i; + + for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) { + q = clearbusy(p->ptr); + if (v[1]) + printf("%6o %5d %s\n", p, + ((unsigned) q - (unsigned) p), + testbusy(p->ptr) ? "BUSY" : "FREE"); + i = ((unsigned) q - (unsigned) p); + if (testbusy(p->ptr)) used += i; else free += i; + } + printf("%d used, %d free, %l end\n", used, free, clearbusy(alloct)); +} +#endif -- 2.20.1