Return to malloc.c CVS log

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

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

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

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