X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/cc519405aa02e0c81019d551054642cf58e9e5e7..f5d4886d34b733fba3ca10a7250e6a03bc019a17:/usr/src/bin/csh/alloc.c diff --git a/usr/src/bin/csh/alloc.c b/usr/src/bin/csh/alloc.c index fc1c9faa17..de6ec89240 100644 --- a/usr/src/bin/csh/alloc.c +++ b/usr/src/bin/csh/alloc.c @@ -1,216 +1,515 @@ -static char *sccsid = "@(#)alloc.c 4.2 %G%"; +/*- + * Copyright (c) 1983, 1991 The Regents of the University of California. + * All rights reserved. + * + * %sccs.include.redist.c% + */ -#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(); -} +#ifndef lint +static char sccsid[] = "@(#)alloc.c 5.11 (Berkeley) %G%"; +#endif /* not lint */ + +/* + * tc.alloc.c from malloc.c (Caltech) 2/21/82 + * Chris Kingsley, kingsley@cit-20. + * + * This is a very fast storage allocator. It allocates blocks of a small + * number of different sizes, and keeps free lists of each size. Blocks that + * don't exactly fit are passed up to the next larger size. In this + * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long. + * This is designed for use in a program that uses vast quantities of memory, + * but bombs when it runs out. + */ + +#include +#include +#include +#if __STDC__ +# include #else -#define ASSERT(p) +# include #endif -/* avoid break bug */ -#ifdef pdp11 -#define GRANULE 64 -#else -#define GRANULE 0 +#include "csh.h" +#include "extern.h" + +char *memtop = NULL; /* PWP: top of current memory */ +char *membot = NULL; /* PWP: bottom of allocatable memory */ + +#ifndef SYSMALLOC + +#undef RCHECK +#undef DEBUG + + +#ifndef NULL +#define NULL 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*/ + + +/* + * The overhead on a block is at least 4 bytes. When free, this space + * contains a pointer to the next free block, and the bottom two bits must + * be zero. When in use, the first byte is set to MAGIC, and the second + * byte is the size index. The remaining bytes are for alignment. + * If range checking is enabled and the size of the block fits + * in two bytes, then the top two bytes hold the size of the requested block + * plus the range checking words, and the header word MINUS ONE. + */ + +#define ROUNDUP 7 + +#define ALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP) + +union overhead { + union overhead *ov_next; /* when free */ + struct { + u_char ovu_magic; /* magic number */ + u_char ovu_index; /* bucket # */ +#ifdef RCHECK + u_short ovu_size; /* actual block size */ + u_int ovu_rmagic; /* range magic number */ +#endif + } ovu; +#define ov_magic ovu.ovu_magic +#define ov_index ovu.ovu_index +#define ov_size ovu.ovu_size +#define ov_rmagic ovu.ovu_rmagic }; -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(); +#define MAGIC 0xfd /* magic # on accounting info */ +#define RMAGIC 0x55555555 /* magic # on range info */ +#ifdef RCHECK +#define RSLOP sizeof (u_int) +#else +#define RSLOP 0 +#endif + +/* + * nextf[i] is the pointer to the next free block of size 2^(i+3). The + * smallest allocatable block is 8 bytes. The overhead information + * precedes the data area returned to the user. + */ +#define NBUCKETS 30 +static union overhead *nextf[NBUCKETS]; -char * +static int findbucket __P((union overhead *, int)); +static void morecore __P((int)); + +/* + * nmalloc[i] is the difference between the number of mallocs and frees + * for a given block size. + */ +static u_int nmalloc[NBUCKETS]; + + +#ifdef DEBUG +#define CHECK(a, str, p) \ + if (a) { \ + (void) fprintfcsherr, (str, p); \ + (void) fprintf(csherr, "memtop = %lx membot = %lx.\n", memtop, membot);\ + abort(); \ + } \ + else +#else +#define CHECK(a, str, p) \ + if (a) { \ + (void) fprintf(csherr, str, p); \ + (void) fprintf(csherr, "memtop = %lx membot = %lx.\n", memtop, membot);\ + return; \ + } \ + else +#endif + +ptr_t malloc(nbytes) -unsigned nbytes; + register size_t 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)); +#ifndef lint + register union overhead *p; + register int bucket = 0; + register unsigned shiftr; + + /* + * Convert amount of memory requested into closest block size stored in + * hash buckets which satisfies request. Account for space used per block + * for accounting. + */ + nbytes = ALIGN(ALIGN(sizeof(union overhead)) + nbytes + RSLOP); + shiftr = (nbytes - 1) >> 2; + + /* apart from this loop, this is O(1) */ + while (shiftr >>= 1) + bucket++; + /* + * If nothing in hash bucket right now, request more memory from the + * system. + */ + if (nextf[bucket] == NULL) + morecore(bucket); + if ((p = (union overhead *) nextf[bucket]) == NULL) { + child++; +#ifndef DEBUG + stderror(ERR_NOMEM); +#else + showall(); + (void) fprintf(csherr, "nbytes=%d: Out of memory\n", nbytes); + abort(); +#endif + /* fool lint */ + return ((ptr_t) 0); + } + /* remove from linked list */ + nextf[bucket] = nextf[bucket]->ov_next; + p->ov_magic = MAGIC; + p->ov_index = bucket; + nmalloc[bucket]++; +#ifdef RCHECK + /* + * Record allocated size of block and bound space with magic numbers. + */ + if (nbytes <= 0x10000) + p->ov_size = nbytes - 1; + p->ov_rmagic = RMAGIC; + *((u_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC; +#endif + return ((ptr_t) (((caddr_t) p) + ALIGN(sizeof(union overhead)))); +#else + if (nbytes) + return ((ptr_t) 0); + else + return ((ptr_t) 0); +#endif /* !lint */ } -/* freeing strategy tuned for LIFO allocation -*/ -free(ap) -register char *ap; +#ifndef lint +/* + * Allocate more memory to the indicated bucket. + */ +static void +morecore(bucket) + register int bucket; { - 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); + register union overhead *op; + register int rnu; /* 2^rnu bytes will be requested */ + register int nblks; /* become nblks blocks of the desired size */ + register int siz; + + if (nextf[bucket]) + return; + /* + * Insure memory is allocated on a page boundary. Should make getpageize + * call? + */ + op = (union overhead *) sbrk(0); + memtop = (char *) op; + if (membot == NULL) + membot = memtop; + if ((int) op & 0x3ff) { + memtop = (char *) sbrk(1024 - ((int) op & 0x3ff)); + memtop += 1024 - ((int) op & 0x3ff); + } + + /* take 2k unless the block is bigger than that */ + rnu = (bucket <= 8) ? 11 : bucket + 3; + nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ + memtop = (char *) sbrk(1 << rnu); /* PWP */ + op = (union overhead *) memtop; + memtop += 1 << rnu; + /* no more room! */ + if ((int) op == -1) + return; + /* + * Round up to minimum allocation size boundary and deduct from block count + * to reflect. + */ + if (((u_int) op) & ROUNDUP) { + op = (union overhead *) (((u_int) op + (ROUNDUP + 1)) & ~ROUNDUP); + nblks--; + } + /* + * Add new memory allocated to that on free list for this hash bucket. + */ + nextf[bucket] = op; + siz = 1 << (bucket + 3); + while (--nblks > 0) { + op->ov_next = (union overhead *) (((caddr_t) op) + siz); + op = (union overhead *) (((caddr_t) op) + siz); + } + op->ov_next = NULL; } -/* 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 -*/ +#endif -char * -realloc(p, nbytes) -register union store *p; -unsigned nbytes; +void +free(cp) + ptr_t cp; { - 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 (ptr_t) memtop, "free(%lx) above top of memory.", cp); + CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp); + op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); + CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp); + +#ifdef RCHECK + if (op->ov_index <= 13) + CHECK(*(u_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, + "free(%lx) bad range check.", cp); +#endif + CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp); + size = op->ov_index; + op->ov_next = nextf[size]; + nextf[size] = op; + + nmalloc[size]--; + #else - *t++ = *s++; + if (cp == NULL) + return; #endif - if(q

=p) - (q+(q+nw-p))->ptr = allocx; - return((char *)q); } -#ifdef debug -allock() +ptr_t +calloc(i, j) + size_t i, j; { -#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); +#ifndef lint + register char *cp, *scp; + + i *= j; + scp = cp = (char *) xmalloc((size_t) i); + if (i != 0) + do + *cp++ = 0; + while (--i); + + return (scp); #else - return(1); + if (i && j) + return ((ptr_t) 0); + else + return ((ptr_t) 0); #endif } -#endif -#ifdef debug -showall(v) - char **v; +/* + * When a program attempts "storage compaction" as mentioned in the + * old malloc man page, it realloc's an already freed block. Usually + * this is the last block it freed; occasionally it might be farther + * back. We have to search all the free lists for the block in order + * to determine its bucket: 1st we make one pass thru the lists + * checking only the first block in each; if that fails we search + * ``realloc_srchlen'' blocks in each list for a match (the variable + * is extern so the caller can modify it). If that fails we just copy + * however many bytes was given to realloc() and hope it's not huge. + */ +#ifndef lint +int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ + +#endif /* lint */ + +ptr_t +realloc(cp, nbytes) + ptr_t cp; + size_t nbytes; { - 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; +#ifndef lint + register u_int onb; + union overhead *op; + char *res; + register int i; + int was_alloced = 0; + + if (cp == NULL) + return (malloc(nbytes)); + op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); + if (op->ov_magic == MAGIC) { + was_alloced++; + i = op->ov_index; + } + else + /* + * Already free, doing "compaction". + * + * Search for the old block of memory on the free list. First, check the + * most common case (last element free'd), then (this failing) the last + * ``realloc_srchlen'' items free'd. If all lookups fail, then assume + * the size of the memory block being realloc'd is the smallest + * possible. + */ + if ((i = findbucket(op, 1)) < 0 && + (i = findbucket(op, realloc_srchlen)) < 0) + i = 0; + + onb = ALIGN(nbytes + ALIGN(sizeof(union overhead)) + RSLOP); + + /* avoid the copy if same size block */ + if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2)))) + return ((ptr_t) cp); + if ((res = malloc(nbytes)) == NULL) + return ((ptr_t) 0); + if (cp != res) /* common optimization */ + bcopy(cp, res, nbytes); + if (was_alloced) + free(cp); + return (res); +#else + if (cp && nbytes) + return ((ptr_t) 0); + else + return ((ptr_t) 0); +#endif /* !lint */ +} + + + +#ifndef lint +/* + * Search ``srchlen'' elements of each free list for a block whose + * header starts at ``freep''. If srchlen is -1 search the whole list. + * Return bucket number, or -1 if not found. + */ +static int +findbucket(freep, srchlen) + union overhead *freep; + int srchlen; +{ + register union overhead *p; + register int i, j; + + for (i = 0; i < NBUCKETS; i++) { + j = 0; + for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { + if (p == freep) + return (i); + j++; } - printf("%d used, %d free, %ld end\n", used, free, clearbusy(alloct)); + } + return (-1); } + #endif + + +#else /* SYSMALLOC */ + +/** + ** ``Protected versions'' of malloc, realloc, calloc, and free + ** + ** On many systems: + ** + ** 1. malloc(0) is bad + ** 2. free(0) is bad + ** 3. realloc(0, n) is bad + ** 4. realloc(n, 0) is bad + ** + ** Also we call our error routine if we run out of memory. + **/ +char * +Malloc(n) + size_t n; +{ + ptr_t ptr; + + n = n ? n : 1; + + if ((ptr = malloc(n)) == (ptr_t) 0) { + child++; + stderror(ERR_NOMEM); + } + return ((char *) ptr); +} + +char * +Realloc(p, n) + ptr_t p; + size_t n; +{ + ptr_t ptr; + + n = n ? n : 1; + if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) { + child++; + stderror(ERR_NOMEM); + } + return ((char *) ptr); +} + +char * +Calloc(s, n) + size_t s, n; +{ + char *sptr; + ptr_t ptr; + + n *= s; + n = n ? n : 1; + if ((ptr = malloc(n)) == (ptr_t) 0) { + child++; + stderror(ERR_NOMEM); + } + + sptr = (char *) ptr; + if (n != 0) + do + *sptr++ = 0; + while (--n); + + return ((char *) ptr); +} + +void +Free(p) + ptr_t p; +{ + if (p) + free(p); +} + +#endif /* SYSMALLOC */ + +/* + * mstats - print out statistics about malloc + * + * Prints two lines of numbers, one showing the length of the free list + * for each size category, the second showing the number of mallocs - + * frees for each size category. + */ +void +/*ARGSUSED*/ +showall(v, t) + Char **v; + struct command *t; +{ +#ifndef SYSMALLOC + register int i, j; + register union overhead *p; + int totfree = 0, totused = 0; + + (void) fprintf(cshout, "csh current memory allocation:\nfree:\t"); + for (i = 0; i < NBUCKETS; i++) { + for (j = 0, p = nextf[i]; p; p = p->ov_next, j++); + (void) fprintf(cshout, " %4d", j); + totfree += j * (1 << (i + 3)); + } + (void) fprintf(cshout, "\nused:\t"); + for (i = 0; i < NBUCKETS; i++) { + (void) fprintf(cshout, "%4d", nmalloc[i]); + totused += nmalloc[i] * (1 << (i + 3)); + } + (void) fprintf(cshout, "\n\tTotal in use: %d, total free: %d\n", + totused, totfree); + (void) fprintf(cshout, + "\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n", + membot, memtop, (char *) sbrk(0)); +#else + (void) fprintf(cshout, "Allocated memory from 0x%lx to 0x%lx (%ld).\n", + membot, memtop = (char *) sbrk(0), memtop - membot); +#endif /* SYSMALLOC */ +}