Return to malloc.c CVS log

Up to [CSRG BSD Unix] / 42BSD / lib / libc / gen

Annotation of 42BSD/lib/libc/gen/malloc.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)malloc.c   4.3 (Berkeley) 9/16/83";
        !             3: #endif
        !             4: 
        !             5: /*
        !             6:  * malloc.c (Caltech) 2/21/82
        !             7:  * Chris Kingsley, kingsley@cit-20.
        !             8:  *
        !             9:  * This is a very fast storage allocator.  It allocates blocks of a small 
        !            10:  * number of different sizes, and keeps free lists of each size.  Blocks that
        !            11:  * don't exactly fit are passed up to the next larger size.  In this 
        !            12:  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
        !            13:  * This is designed for use in a program that uses vast quantities of memory,
        !            14:  * but bombs when it runs out. 
        !            15:  */
        !            16: 
        !            17: #include <sys/types.h>
        !            18: 
        !            19: #define        NULL 0
        !            20: 
        !            21: /*
        !            22:  * The overhead on a block is at least 4 bytes.  When free, this space
        !            23:  * contains a pointer to the next free block, and the bottom two bits must
        !            24:  * be zero.  When in use, the first byte is set to MAGIC, and the second
        !            25:  * byte is the size index.  The remaining bytes are for alignment.
        !            26:  * If range checking is enabled and the size of the block fits
        !            27:  * in two bytes, then the top two bytes hold the size of the requested block
        !            28:  * plus the range checking words, and the header word MINUS ONE.
        !            29:  */
        !            30: union  overhead {
        !            31:        union   overhead *ov_next;      /* when free */
        !            32:        struct {
        !            33:                u_char  ovu_magic;      /* magic number */
        !            34:                u_char  ovu_index;      /* bucket # */
        !            35: #ifdef RCHECK
        !            36:                u_short ovu_size;       /* actual block size */
        !            37:                u_int   ovu_rmagic;     /* range magic number */
        !            38: #endif
        !            39:        } ovu;
        !            40: #define        ov_magic        ovu.ovu_magic
        !            41: #define        ov_index        ovu.ovu_index
        !            42: #define        ov_size         ovu.ovu_size
        !            43: #define        ov_rmagic       ovu.ovu_rmagic
        !            44: };
        !            45: 
        !            46: #define        MAGIC           0xff            /* magic # on accounting info */
        !            47: #define RMAGIC         0x55555555      /* magic # on range info */
        !            48: #ifdef RCHECK
        !            49: #define        RSLOP           sizeof (u_int)
        !            50: #else
        !            51: #define        RSLOP           0
        !            52: #endif
        !            53: 
        !            54: /*
        !            55:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
        !            56:  * smallest allocatable block is 8 bytes.  The overhead information
        !            57:  * precedes the data area returned to the user.
        !            58:  */
        !            59: #define        NBUCKETS 30
        !            60: static union overhead *nextf[NBUCKETS];
        !            61: extern char *sbrk();
        !            62: 
        !            63: #ifdef MSTATS
        !            64: /*
        !            65:  * nmalloc[i] is the difference between the number of mallocs and frees
        !            66:  * for a given block size.
        !            67:  */
        !            68: static u_int nmalloc[NBUCKETS];
        !            69: #include <stdio.h>
        !            70: #endif
        !            71: 
        !            72: #ifdef debug
        !            73: #define        ASSERT(p)   if (!(p)) botch("p"); else
        !            74: static
        !            75: botch(s)
        !            76:        char *s;
        !            77: {
        !            78: 
        !            79:        printf("assertion botched: %s\n", s);
        !            80:        abort();
        !            81: }
        !            82: #else
        !            83: #define        ASSERT(p)
        !            84: #endif
        !            85: 
        !            86: char *
        !            87: malloc(nbytes)
        !            88:        register unsigned nbytes;
        !            89: {
        !            90:        register union overhead *p;
        !            91:        register int bucket = 0;
        !            92:        register unsigned shiftr;
        !            93: 
        !            94:        /*
        !            95:         * Convert amount of memory requested into
        !            96:         * closest block size stored in hash buckets
        !            97:         * which satisfies request.  Account for
        !            98:         * space used per block for accounting.
        !            99:         */
        !           100:        nbytes += sizeof (union overhead) + RSLOP;
        !           101:        nbytes = (nbytes + 3) &~ 3; 
        !           102:        shiftr = (nbytes - 1) >> 2;
        !           103:        /* apart from this loop, this is O(1) */
        !           104:        while (shiftr >>= 1)
        !           105:                bucket++;
        !           106:        /*
        !           107:         * If nothing in hash bucket right now,
        !           108:         * request more memory from the system.
        !           109:         */
        !           110:        if (nextf[bucket] == NULL)    
        !           111:                morecore(bucket);
        !           112:        if ((p = (union overhead *)nextf[bucket]) == NULL)
        !           113:                return (NULL);
        !           114:        /* remove from linked list */
        !           115:        nextf[bucket] = nextf[bucket]->ov_next;
        !           116:        p->ov_magic = MAGIC;
        !           117:        p->ov_index= bucket;
        !           118: #ifdef MSTATS
        !           119:        nmalloc[bucket]++;
        !           120: #endif
        !           121: #ifdef RCHECK
        !           122:        /*
        !           123:         * Record allocated size of block and
        !           124:         * bound space with magic numbers.
        !           125:         */
        !           126:        if (nbytes <= 0x10000)
        !           127:                p->ov_size = nbytes - 1;
        !           128:        p->ov_rmagic = RMAGIC;
        !           129:        *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
        !           130: #endif
        !           131:        return ((char *)(p + 1));
        !           132: }
        !           133: 
        !           134: /*
        !           135:  * Allocate more memory to the indicated bucket.
        !           136:  */
        !           137: static
        !           138: morecore(bucket)
        !           139:        register bucket;
        !           140: {
        !           141:        register union overhead *op;
        !           142:        register int rnu;       /* 2^rnu bytes will be requested */
        !           143:        register int nblks;     /* become nblks blocks of the desired size */
        !           144:        register int siz;
        !           145: 
        !           146:        if (nextf[bucket])
        !           147:                return;
        !           148:        /*
        !           149:         * Insure memory is allocated
        !           150:         * on a page boundary.  Should
        !           151:         * make getpageize call?
        !           152:         */
        !           153:        op = (union overhead *)sbrk(0);
        !           154:        if ((int)op & 0x3ff)
        !           155:                sbrk(1024 - ((int)op & 0x3ff));
        !           156:        /* take 2k unless the block is bigger than that */
        !           157:        rnu = (bucket <= 8) ? 11 : bucket + 3;
        !           158:        nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
        !           159:        if (rnu < bucket)
        !           160:                rnu = bucket;
        !           161:        op = (union overhead *)sbrk(1 << rnu);
        !           162:        /* no more room! */
        !           163:        if ((int)op == -1)
        !           164:                return;
        !           165:        /*
        !           166:         * Round up to minimum allocation size boundary
        !           167:         * and deduct from block count to reflect.
        !           168:         */
        !           169:        if ((int)op & 7) {
        !           170:                op = (union overhead *)(((int)op + 8) &~ 7);
        !           171:                nblks--;
        !           172:        }
        !           173:        /*
        !           174:         * Add new memory allocated to that on
        !           175:         * free list for this hash bucket.
        !           176:         */
        !           177:        nextf[bucket] = op;
        !           178:        siz = 1 << (bucket + 3);
        !           179:        while (--nblks > 0) {
        !           180:                op->ov_next = (union overhead *)((caddr_t)op + siz);
        !           181:                op = (union overhead *)((caddr_t)op + siz);
        !           182:        }
        !           183: }
        !           184: 
        !           185: free(cp)
        !           186:        char *cp;
        !           187: {   
        !           188:        register int size;
        !           189:        register union overhead *op;
        !           190: 
        !           191:        if (cp == NULL)
        !           192:                return;
        !           193:        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        !           194: #ifdef debug
        !           195:        ASSERT(op->ov_magic == MAGIC);          /* make sure it was in use */
        !           196: #else
        !           197:        if (op->ov_magic != MAGIC)
        !           198:                return;                         /* sanity */
        !           199: #endif
        !           200: #ifdef RCHECK
        !           201:        ASSERT(op->ov_rmagic == RMAGIC);
        !           202:        if (op->ov_index <= 13)
        !           203:                ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
        !           204: #endif
        !           205:        ASSERT(op->ov_index < NBUCKETS);
        !           206:        size = op->ov_index;
        !           207:        op->ov_next = nextf[size];
        !           208:        nextf[size] = op;
        !           209: #ifdef MSTATS
        !           210:        nmalloc[size]--;
        !           211: #endif
        !           212: }
        !           213: 
        !           214: /*
        !           215:  * When a program attempts "storage compaction" as mentioned in the
        !           216:  * old malloc man page, it realloc's an already freed block.  Usually
        !           217:  * this is the last block it freed; occasionally it might be farther
        !           218:  * back.  We have to search all the free lists for the block in order
        !           219:  * to determine its bucket: 1st we make one pass thru the lists
        !           220:  * checking only the first block in each; if that fails we search
        !           221:  * ``realloc_srchlen'' blocks in each list for a match (the variable
        !           222:  * is extern so the caller can modify it).  If that fails we just copy
        !           223:  * however many bytes was given to realloc() and hope it's not huge.
        !           224:  */
        !           225: int realloc_srchlen = 4;       /* 4 should be plenty, -1 =>'s whole list */
        !           226: 
        !           227: char *
        !           228: realloc(cp, nbytes)
        !           229:        char *cp; 
        !           230:        unsigned nbytes;
        !           231: {   
        !           232:        register u_int onb;
        !           233:        union overhead *op;
        !           234:        char *res;
        !           235:        register int i;
        !           236:        int was_alloced = 0;
        !           237: 
        !           238:        if (cp == NULL)
        !           239:                return (malloc(nbytes));
        !           240:        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        !           241:        if (op->ov_magic == MAGIC) {
        !           242:                was_alloced++;
        !           243:                i = op->ov_index;
        !           244:        } else {
        !           245:                /*
        !           246:                 * Already free, doing "compaction".
        !           247:                 *
        !           248:                 * Search for the old block of memory on the
        !           249:                 * free list.  First, check the most common
        !           250:                 * case (last element free'd), then (this failing)
        !           251:                 * the last ``realloc_srchlen'' items free'd.
        !           252:                 * If all lookups fail, then assume the size of
        !           253:                 * the memory block being realloc'd is the
        !           254:                 * smallest possible.
        !           255:                 */
        !           256:                if ((i = findbucket(op, 1)) < 0 &&
        !           257:                    (i = findbucket(op, realloc_srchlen)) < 0)
        !           258:                        i = 0;
        !           259:        }
        !           260:        onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
        !           261:        /* avoid the copy if same size block */
        !           262:        if (was_alloced &&
        !           263:            nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
        !           264:                return(cp);
        !           265:        if ((res = malloc(nbytes)) == NULL)
        !           266:                return (NULL);
        !           267:        if (cp != res)                  /* common optimization */
        !           268:                bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
        !           269:        if (was_alloced)
        !           270:                free(cp);
        !           271:        return (res);
        !           272: }
        !           273: 
        !           274: /*
        !           275:  * Search ``srchlen'' elements of each free list for a block whose
        !           276:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
        !           277:  * Return bucket number, or -1 if not found.
        !           278:  */
        !           279: static
        !           280: findbucket(freep, srchlen)
        !           281:        union overhead *freep;
        !           282:        int srchlen;
        !           283: {
        !           284:        register union overhead *p;
        !           285:        register int i, j;
        !           286: 
        !           287:        for (i = 0; i < NBUCKETS; i++) {
        !           288:                j = 0;
        !           289:                for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
        !           290:                        if (p == freep)
        !           291:                                return (i);
        !           292:                        j++;
        !           293:                }
        !           294:        }
        !           295:        return (-1);
        !           296: }
        !           297: 
        !           298: #ifdef MSTATS
        !           299: /*
        !           300:  * mstats - print out statistics about malloc
        !           301:  * 
        !           302:  * Prints two lines of numbers, one showing the length of the free list
        !           303:  * for each size category, the second showing the number of mallocs -
        !           304:  * frees for each size category.
        !           305:  */
        !           306: mstats(s)
        !           307:        char *s;
        !           308: {
        !           309:        register int i, j;
        !           310:        register union overhead *p;
        !           311:        int totfree = 0,
        !           312:        totused = 0;
        !           313: 
        !           314:        fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
        !           315:        for (i = 0; i < NBUCKETS; i++) {
        !           316:                for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
        !           317:                        ;
        !           318:                fprintf(stderr, " %d", j);
        !           319:                totfree += j * (1 << (i + 3));
        !           320:        }
        !           321:        fprintf(stderr, "\nused:\t");
        !           322:        for (i = 0; i < NBUCKETS; i++) {
        !           323:                fprintf(stderr, " %d", nmalloc[i]);
        !           324:                totused += nmalloc[i] * (1 << (i + 3));
        !           325:        }
        !           326:        fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
        !           327:            totused, totfree);
        !           328: }
        !           329: #endif

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.