Return to malloc.c CVS log

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

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

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

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