Return to malloc.c CVS log

Up to [MW Coherent from dump] / coherent / b / lib / libc / gen / malloc

Annotation of coherent/b/lib/libc/gen/malloc/malloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * libc/gen/malloc/malloc.c
        !             3:  * Memory allocation routines.
        !             4:  * The memory arena is a circular linked list rooted at __a_first.
        !             5:  * Each arena is subdivided into two or more blocks.
        !             6:  * The first word of each block gives its length,
        !             7:  * with the low order bit set if the block is free;
        !             8:  * block lengths are always multiples of 2 to allow free marking.
        !             9:  * A length word containing 0 marks the end of an arena;
        !            10:  * in this case the following pointer points to the next arena.
        !            11:  */
        !            12: 
        !            13: #include <stdio.h>
        !            14: #include <sys/malloc.h>
        !            15: 
        !            16: MBLOCK *__a_scanp = NULL;              /* start search here */
        !            17: MBLOCK *__a_first = NULL;              /* first arena */
        !            18: MBLOCK *__a_top = NULL;                /* end of last sbrk */
        !            19: unsigned __a_count = 0;                        /* number of blocks */
        !            20: 
        !            21: extern char *sbrk();
        !            22: 
        !            23: /*
        !            24:  * Get a new arena from sbrk() and hook it to the old list.
        !            25:  * Return 1 if there is any chance of malloc succeeding, else 0.
        !            26:  * Note that this assumes the argument to sbrk() is unsigned;
        !            27:  * bad news if sbrk() expects int and shrinks the break if negative.
        !            28:  */
        !            29: static
        !            30: int
        !            31: newarena(size) unsigned size;
        !            32: {
        !            33:        register MBLOCK *mp, *pmp, *linkmp;
        !            34:        register unsigned len, max;
        !            35:        static char failed = 0;
        !            36: 
        !            37:        if (failed)                     /* no more room */
        !            38:                return 0;
        !            39: 
        !            40:        /* Force sbrk() to alignment boundary. */
        !            41:        if ((len = ((unsigned)sbrk(0)) & (ALIGNMENT - 1)) != 0
        !            42:         && (sbrk(ALIGNMENT - len) == BADSBRK)) {
        !            43:                failed = 1;
        !            44:                return 1;
        !            45:        }
        !            46: 
        !            47:        /* Add space for end mblock, round up to 2^ARENASIZE */
        !            48:        len = roundup(size + sizeof(MBLOCK), ARENASIZE);
        !            49:        if (len < size)
        !            50:                len = size;
        !            51: 
        !            52:        __a_scanp = __a_first;          /* rescan from the begining */
        !            53: 
        !            54:        /*
        !            55:         * If there isn't enough space get what we can it may be enough.
        !            56:         * This means further calls to newarena must fail.
        !            57:         */
        !            58:        while ((mp = (MBLOCK *)sbrk(len)) == BADSBRK) {
        !            59:                if (failed == 0 && (max = ulimit(3)) != -1 && len > max)
        !            60:                        len = max;              /* use system limit as upper bound */
        !            61:                failed = 1;
        !            62:                if (len <= DECRSIZE)
        !            63:                        return 1;               /* even zero may be ok */
        !            64:                len -= DECRSIZE;
        !            65:                if (sizeof(MBLOCK) > len)
        !            66:                        len = sizeof(MBLOCK);
        !            67:        }
        !            68: 
        !            69:        if (__a_top == NULL) {                  /* first time through */
        !            70:                __a_count = 2;
        !            71:                __a_first = __a_scanp = linkmp = mp;
        !            72:        }
        !            73:        else if (__a_top == mp) {               /* new arena follows old */
        !            74:                /*
        !            75:                 * The following assumes that len + sizeof(MBLOCK)
        !            76:                 * will not be greater than the maximum unsigned value,
        !            77:                 * which will be true if 2^ARENASIZE > sizeof(MBLOCK).
        !            78:                 */
        !            79:                --mp;
        !            80:                len += sizeof(MBLOCK);
        !            81:                linkmp = mp->uval.next;
        !            82:                __a_count++;
        !            83:        }
        !            84:        else {                                  /* discontigous arenas */
        !            85:                pmp = __a_top - 1;
        !            86:                linkmp = pmp->uval.next;        /* save old pointer */
        !            87:                pmp->uval.next = mp;            /* old points to new */
        !            88:                __a_count += 2;
        !            89:        }
        !            90:        mp->blksize = (len - sizeof(MBLOCK)) | FREE;
        !            91:        __a_top = bumpp(mp, len);
        !            92:        pmp = __a_top - 1;
        !            93:        pmp->blksize = 0;
        !            94:        pmp->uval.next = linkmp;
        !            95:        return 1;
        !            96: }
        !            97: 
        !            98: /*
        !            99:  * Allocate memory.
        !           100:  * Successive free blocks are consolidated when found.
        !           101:  */
        !           102: char *
        !           103: malloc(size) unsigned size;
        !           104: {
        !           105:     register MBLOCK *mp, *prevmp;
        !           106:     register unsigned len, needed, counter;
        !           107:     static char msg[] = "Bad pointer in malloc.\r\n";
        !           108: 
        !           109:     if (size == 0)
        !           110:            return NULL;
        !           111:     needed = roundup(size + sizeof(unsigned), BLOCKSIZE);
        !           112:     if (needed < size)
        !           113:            return NULL;
        !           114: 
        !           115:     do { /* until we find enough or newarena fails */
        !           116:        for (counter = __a_count, mp = __a_scanp, prevmp = NULL; counter--; ) {
        !           117:                if (!isfree(len = mp->blksize)) { /* used block or pointer */
        !           118:                        mp = (len) ? bumpp(mp, len) : mp->uval.next;
        !           119:                        prevmp = NULL;
        !           120:                        continue;
        !           121:                }
        !           122: 
        !           123:                if (prevmp != NULL) {           /* consolidate free */
        !           124: #if    0
        !           125: /*
        !           126:  * The following assumes adjacent free blocks can be consolidated without
        !           127:  * overflow of the size.  The overflow test is conditionalized out here,
        !           128:  * but it may be required on some machines.  In i8086 LARGE model, the code
        !           129:  * works without the test but only barely.  When the memory arena gets larger
        !           130:  * than 64K, sbrk()  returns mp pointing to the same memory location as
        !           131:  * newarena()/__a_top, but with a different segment:offset representation;
        !           132:  * thus the "if (__a_top == mp)" test in newarena fails (even though they
        !           133:  * point to the same memory location) and newarena() leaves a 0 end marker
        !           134:  * between the arenas.
        !           135:  */
        !           136:                        if (prevmp->blksize + realsize(len) > len) {
        !           137:                                len = ((mp = prevmp)->blksize += realsize(len));
        !           138:                                __a_count--;
        !           139:                        }
        !           140: #else
        !           141:                        len = ((mp = prevmp)->blksize += realsize(len));
        !           142:                        __a_count--;
        !           143: #endif
        !           144:                }
        !           145: 
        !           146:                if (len < needed) {     /* free but too small */
        !           147:                        mp = bumpp(prevmp = mp, realsize(len));
        !           148:                        continue;
        !           149:                }
        !           150: 
        !           151:                if ((len -= needed) < LEASTFREE)
        !           152:                        /* grab the entire block */
        !           153:                        __a_scanp = bumpp(mp, mp->blksize = needed = realsize(mp->blksize));
        !           154:                else {
        !           155:                        /* split into used and free portions */
        !           156:                        mp->blksize = needed;
        !           157:                        __a_scanp = bumpp(mp, needed);
        !           158:                        __a_scanp->blksize = len;
        !           159:                        __a_count++;
        !           160:                }
        !           161:                return mp->uval.usera;
        !           162:        }
        !           163: 
        !           164:        /*
        !           165:         * There should have been __a_count blocks bringing us full circle.
        !           166:         */
        !           167:        if (mp != __a_scanp) {
        !           168:                write(2, msg, sizeof(msg) - 1);
        !           169:                abort();
        !           170:        }
        !           171: 
        !           172:     /* Not enough room in the current arena, allocate a new one. */
        !           173:     } while (newarena(needed));
        !           174:     return NULL;
        !           175: }
        !           176: 
        !           177: /*
        !           178:  * Free a block.
        !           179:  * Some sanity checking.
        !           180:  * Adjacent free block consolidation happens in malloc(), not here.
        !           181:  */
        !           182: void
        !           183: free(cp) char *cp;
        !           184: {
        !           185:        register MBLOCK *mp;
        !           186:        register unsigned len;
        !           187: 
        !           188:        if (NULL == cp)         /* ansi 4.10.3.2: free(NULL) has no effect */
        !           189:                return;
        !           190: 
        !           191:        mp = mblockp(cp);
        !           192:        len = mp->blksize;
        !           193:        if (len < LEASTFREE) { /* This can't exist */
        !           194:                static char msg[] = "Bad pointer in free.\r\n";
        !           195: 
        !           196:                write(2, msg, sizeof(msg) - 1);
        !           197:                abort();
        !           198:        }
        !           199:        mp->blksize |= FREE;                    /* mark free */
        !           200: 
        !           201:        /*
        !           202:         * If freed block precedes scan pointer reset the scan pointer.
        !           203:         */
        !           204:        if (bumpp(mp, realsize(len)) == __a_scanp)
        !           205:                __a_scanp = mp;
        !           206: }

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