Return to malloc.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / lib / libc / stdlib

Annotation of 43BSDReno/lib/libc/stdlib/malloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1983 Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * Redistribution and use in source and binary forms are permitted
        !             6:  * provided that: (1) source distributions retain this entire copyright
        !             7:  * notice and comment, and (2) distributions including binaries display
        !             8:  * the following acknowledgement:  ``This product includes software
        !             9:  * developed by the University of California, Berkeley and its contributors''
        !            10:  * in the documentation or other materials provided with the distribution
        !            11:  * and in all advertising materials mentioning features or use of this
        !            12:  * software. Neither the name of the University nor the names of its
        !            13:  * contributors may be used to endorse or promote products derived
        !            14:  * from this software without specific prior written permission.
        !            15:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            16:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            17:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            18:  */
        !            19: 
        !            20: #if defined(LIBC_SCCS) && !defined(lint)
        !            21: static char sccsid[] = "@(#)malloc.c   5.9 (Berkeley) 6/1/90";
        !            22: #endif /* LIBC_SCCS and not lint */
        !            23: 
        !            24: /*
        !            25:  * malloc.c (Caltech) 2/21/82
        !            26:  * Chris Kingsley, kingsley@cit-20.
        !            27:  *
        !            28:  * This is a very fast storage allocator.  It allocates blocks of a small 
        !            29:  * number of different sizes, and keeps free lists of each size.  Blocks that
        !            30:  * don't exactly fit are passed up to the next larger size.  In this 
        !            31:  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
        !            32:  * This is designed for use in a virtual memory environment.
        !            33:  */
        !            34: 
        !            35: #include <sys/types.h>
        !            36: 
        !            37: #define        NULL 0
        !            38: 
        !            39: /*
        !            40:  * The overhead on a block is at least 4 bytes.  When free, this space
        !            41:  * contains a pointer to the next free block, and the bottom two bits must
        !            42:  * be zero.  When in use, the first byte is set to MAGIC, and the second
        !            43:  * byte is the size index.  The remaining bytes are for alignment.
        !            44:  * If range checking is enabled then a second word holds the size of the
        !            45:  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
        !            46:  * The order of elements is critical: ov_magic must overlay the low order
        !            47:  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
        !            48:  */
        !            49: union  overhead {
        !            50:        union   overhead *ov_next;      /* when free */
        !            51:        struct {
        !            52:                u_char  ovu_magic;      /* magic number */
        !            53:                u_char  ovu_index;      /* bucket # */
        !            54: #ifdef RCHECK
        !            55:                u_short ovu_rmagic;     /* range magic number */
        !            56:                u_int   ovu_size;       /* actual block size */
        !            57: #endif
        !            58:        } ovu;
        !            59: #define        ov_magic        ovu.ovu_magic
        !            60: #define        ov_index        ovu.ovu_index
        !            61: #define        ov_rmagic       ovu.ovu_rmagic
        !            62: #define        ov_size         ovu.ovu_size
        !            63: };
        !            64: 
        !            65: #define        MAGIC           0xef            /* magic # on accounting info */
        !            66: #define RMAGIC         0x5555          /* magic # on range info */
        !            67: 
        !            68: #ifdef RCHECK
        !            69: #define        RSLOP           sizeof (u_short)
        !            70: #else
        !            71: #define        RSLOP           0
        !            72: #endif
        !            73: 
        !            74: /*
        !            75:  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
        !            76:  * smallest allocatable block is 8 bytes.  The overhead information
        !            77:  * precedes the data area returned to the user.
        !            78:  */
        !            79: #define        NBUCKETS 30
        !            80: static union overhead *nextf[NBUCKETS];
        !            81: extern char *sbrk();
        !            82: 
        !            83: static int pagesz;                     /* page size */
        !            84: static int pagebucket;                 /* page size bucket */
        !            85: 
        !            86: #ifdef MSTATS
        !            87: /*
        !            88:  * nmalloc[i] is the difference between the number of mallocs and frees
        !            89:  * for a given block size.
        !            90:  */
        !            91: static u_int nmalloc[NBUCKETS];
        !            92: #include <stdio.h>
        !            93: #endif
        !            94: 
        !            95: #if defined(DEBUG) || defined(RCHECK)
        !            96: #define        ASSERT(p)   if (!(p)) botch("p")
        !            97: #include <stdio.h>
        !            98: static
        !            99: botch(s)
        !           100:        char *s;
        !           101: {
        !           102:        fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
        !           103:        (void) fflush(stderr);          /* just in case user buffered it */
        !           104:        abort();
        !           105: }
        !           106: #else
        !           107: #define        ASSERT(p)
        !           108: #endif
        !           109: 
        !           110: char *
        !           111: malloc(nbytes)
        !           112:        unsigned nbytes;
        !           113: {
        !           114:        register union overhead *op;
        !           115:        register int bucket, n;
        !           116:        register unsigned amt;
        !           117: 
        !           118:        /*
        !           119:         * First time malloc is called, setup page size and
        !           120:         * align break pointer so all data will be page aligned.
        !           121:         */
        !           122:        if (pagesz == 0) {
        !           123:                pagesz = n = getpagesize();
        !           124:                op = (union overhead *)sbrk(0);
        !           125:                n = n - sizeof (*op) - ((int)op & (n - 1));
        !           126:                if (n < 0)
        !           127:                        n += pagesz;
        !           128:                if (n) {
        !           129:                        if (sbrk(n) == (char *)-1)
        !           130:                                return (NULL);
        !           131:                }
        !           132:                bucket = 0;
        !           133:                amt = 8;
        !           134:                while (pagesz > amt) {
        !           135:                        amt <<= 1;
        !           136:                        bucket++;
        !           137:                }
        !           138:                pagebucket = bucket;
        !           139:        }
        !           140:        /*
        !           141:         * Convert amount of memory requested into closest block size
        !           142:         * stored in hash buckets which satisfies request.
        !           143:         * Account for space used per block for accounting.
        !           144:         */
        !           145:        if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
        !           146: #ifndef RCHECK
        !           147:                amt = 8;        /* size of first bucket */
        !           148:                bucket = 0;
        !           149: #else
        !           150:                amt = 16;       /* size of first bucket */
        !           151:                bucket = 1;
        !           152: #endif
        !           153:                n = -(sizeof (*op) + RSLOP);
        !           154:        } else {
        !           155:                amt = pagesz;
        !           156:                bucket = pagebucket;
        !           157:        }
        !           158:        while (nbytes > amt + n) {
        !           159:                amt <<= 1;
        !           160:                if (amt == 0)
        !           161:                        return (NULL);
        !           162:                bucket++;
        !           163:        }
        !           164:        /*
        !           165:         * If nothing in hash bucket right now,
        !           166:         * request more memory from the system.
        !           167:         */
        !           168:        if ((op = nextf[bucket]) == NULL) {
        !           169:                morecore(bucket);
        !           170:                if ((op = nextf[bucket]) == NULL)
        !           171:                        return (NULL);
        !           172:        }
        !           173:        /* remove from linked list */
        !           174:        nextf[bucket] = op->ov_next;
        !           175:        op->ov_magic = MAGIC;
        !           176:        op->ov_index = bucket;
        !           177: #ifdef MSTATS
        !           178:        nmalloc[bucket]++;
        !           179: #endif
        !           180: #ifdef RCHECK
        !           181:        /*
        !           182:         * Record allocated size of block and
        !           183:         * bound space with magic numbers.
        !           184:         */
        !           185:        op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
        !           186:        op->ov_rmagic = RMAGIC;
        !           187:        *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
        !           188: #endif
        !           189:        return ((char *)(op + 1));
        !           190: }
        !           191: 
        !           192: /*
        !           193:  * Allocate more memory to the indicated bucket.
        !           194:  */
        !           195: morecore(bucket)
        !           196:        int bucket;
        !           197: {
        !           198:        register union overhead *op;
        !           199:        register int sz;                /* size of desired block */
        !           200:        int amt;                        /* amount to allocate */
        !           201:        int nblks;                      /* how many blocks we get */
        !           202: 
        !           203:        /*
        !           204:         * sbrk_size <= 0 only for big, FLUFFY, requests (about
        !           205:         * 2^30 bytes on a VAX, I think) or for a negative arg.
        !           206:         */
        !           207:        sz = 1 << (bucket + 3);
        !           208: #ifdef DEBUG
        !           209:        ASSERT(sz > 0);
        !           210: #else
        !           211:        if (sz <= 0)
        !           212:                return;
        !           213: #endif
        !           214:        if (sz < pagesz) {
        !           215:                amt = pagesz;
        !           216:                nblks = amt / sz;
        !           217:        } else {
        !           218:                amt = sz + pagesz;
        !           219:                nblks = 1;
        !           220:        }
        !           221:        op = (union overhead *)sbrk(amt);
        !           222:        /* no more room! */
        !           223:        if ((int)op == -1)
        !           224:                return;
        !           225:        /*
        !           226:         * Add new memory allocated to that on
        !           227:         * free list for this hash bucket.
        !           228:         */
        !           229:        nextf[bucket] = op;
        !           230:        while (--nblks > 0) {
        !           231:                op->ov_next = (union overhead *)((caddr_t)op + sz);
        !           232:                op = (union overhead *)((caddr_t)op + sz);
        !           233:        }
        !           234: }
        !           235: 
        !           236: free(cp)
        !           237:        char *cp;
        !           238: {   
        !           239:        register int size;
        !           240:        register union overhead *op;
        !           241: 
        !           242:        if (cp == NULL)
        !           243:                return;
        !           244:        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        !           245: #ifdef DEBUG
        !           246:        ASSERT(op->ov_magic == MAGIC);          /* make sure it was in use */
        !           247: #else
        !           248:        if (op->ov_magic != MAGIC)
        !           249:                return;                         /* sanity */
        !           250: #endif
        !           251: #ifdef RCHECK
        !           252:        ASSERT(op->ov_rmagic == RMAGIC);
        !           253:        ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
        !           254: #endif
        !           255:        size = op->ov_index;
        !           256:        ASSERT(size < NBUCKETS);
        !           257:        op->ov_next = nextf[size];      /* also clobbers ov_magic */
        !           258:        nextf[size] = op;
        !           259: #ifdef MSTATS
        !           260:        nmalloc[size]--;
        !           261: #endif
        !           262: }
        !           263: 
        !           264: /*
        !           265:  * When a program attempts "storage compaction" as mentioned in the
        !           266:  * old malloc man page, it realloc's an already freed block.  Usually
        !           267:  * this is the last block it freed; occasionally it might be farther
        !           268:  * back.  We have to search all the free lists for the block in order
        !           269:  * to determine its bucket: 1st we make one pass thru the lists
        !           270:  * checking only the first block in each; if that fails we search
        !           271:  * ``realloc_srchlen'' blocks in each list for a match (the variable
        !           272:  * is extern so the caller can modify it).  If that fails we just copy
        !           273:  * however many bytes was given to realloc() and hope it's not huge.
        !           274:  */
        !           275: int realloc_srchlen = 4;       /* 4 should be plenty, -1 =>'s whole list */
        !           276: 
        !           277: char *
        !           278: realloc(cp, nbytes)
        !           279:        char *cp; 
        !           280:        unsigned nbytes;
        !           281: {   
        !           282:        register u_int onb;
        !           283:        register int i;
        !           284:        union overhead *op;
        !           285:        char *res;
        !           286:        int was_alloced = 0;
        !           287: 
        !           288:        if (cp == NULL)
        !           289:                return (malloc(nbytes));
        !           290:        op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
        !           291:        if (op->ov_magic == MAGIC) {
        !           292:                was_alloced++;
        !           293:                i = op->ov_index;
        !           294:        } else {
        !           295:                /*
        !           296:                 * Already free, doing "compaction".
        !           297:                 *
        !           298:                 * Search for the old block of memory on the
        !           299:                 * free list.  First, check the most common
        !           300:                 * case (last element free'd), then (this failing)
        !           301:                 * the last ``realloc_srchlen'' items free'd.
        !           302:                 * If all lookups fail, then assume the size of
        !           303:                 * the memory block being realloc'd is the
        !           304:                 * largest possible (so that all "nbytes" of new
        !           305:                 * memory are copied into).  Note that this could cause
        !           306:                 * a memory fault if the old area was tiny, and the moon
        !           307:                 * is gibbous.  However, that is very unlikely.
        !           308:                 */
        !           309:                if ((i = findbucket(op, 1)) < 0 &&
        !           310:                    (i = findbucket(op, realloc_srchlen)) < 0)
        !           311:                        i = NBUCKETS;
        !           312:        }
        !           313:        onb = 1 << (i + 3);
        !           314:        if (onb < pagesz)
        !           315:                onb -= sizeof (*op) + RSLOP;
        !           316:        else
        !           317:                onb += pagesz - sizeof (*op) - RSLOP;
        !           318:        /* avoid the copy if same size block */
        !           319:        if (was_alloced) {
        !           320:                if (i) {
        !           321:                        i = 1 << (i + 2);
        !           322:                        if (i < pagesz)
        !           323:                                i -= sizeof (*op) + RSLOP;
        !           324:                        else
        !           325:                                i += pagesz - sizeof (*op) - RSLOP;
        !           326:                }
        !           327:                if (nbytes <= onb && nbytes > i) {
        !           328: #ifdef RCHECK
        !           329:                        op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
        !           330:                        *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
        !           331: #endif
        !           332:                        return(cp);
        !           333:                } else
        !           334:                        free(cp);
        !           335:        }
        !           336:        if ((res = malloc(nbytes)) == NULL)
        !           337:                return (NULL);
        !           338:        if (cp != res)          /* common optimization if "compacting" */
        !           339:                bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
        !           340:        return (res);
        !           341: }
        !           342: 
        !           343: /*
        !           344:  * Search ``srchlen'' elements of each free list for a block whose
        !           345:  * header starts at ``freep''.  If srchlen is -1 search the whole list.
        !           346:  * Return bucket number, or -1 if not found.
        !           347:  */
        !           348: static
        !           349: findbucket(freep, srchlen)
        !           350:        union overhead *freep;
        !           351:        int srchlen;
        !           352: {
        !           353:        register union overhead *p;
        !           354:        register int i, j;
        !           355: 
        !           356:        for (i = 0; i < NBUCKETS; i++) {
        !           357:                j = 0;
        !           358:                for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
        !           359:                        if (p == freep)
        !           360:                                return (i);
        !           361:                        j++;
        !           362:                }
        !           363:        }
        !           364:        return (-1);
        !           365: }
        !           366: 
        !           367: #ifdef MSTATS
        !           368: /*
        !           369:  * mstats - print out statistics about malloc
        !           370:  * 
        !           371:  * Prints two lines of numbers, one showing the length of the free list
        !           372:  * for each size category, the second showing the number of mallocs -
        !           373:  * frees for each size category.
        !           374:  */
        !           375: mstats(s)
        !           376:        char *s;
        !           377: {
        !           378:        register int i, j;
        !           379:        register union overhead *p;
        !           380:        int totfree = 0,
        !           381:        totused = 0;
        !           382: 
        !           383:        fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
        !           384:        for (i = 0; i < NBUCKETS; i++) {
        !           385:                for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
        !           386:                        ;
        !           387:                fprintf(stderr, " %d", j);
        !           388:                totfree += j * (1 << (i + 3));
        !           389:        }
        !           390:        fprintf(stderr, "\nused:\t");
        !           391:        for (i = 0; i < NBUCKETS; i++) {
        !           392:                fprintf(stderr, " %d", nmalloc[i]);
        !           393:                totused += nmalloc[i] * (1 << (i + 3));
        !           394:        }
        !           395:        fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
        !           396:            totused, totfree);
        !           397: }
        !           398: #endif

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