Return to malloc.c CVS log

Up to [Research Unix] / researchv10no / libc / gen

Annotation of researchv10no/libc/gen/malloc.c, revision 1.1

1.1     ! root        1: /* compile-time features
        !             2:    IALLOC: use all blocks given to ialloc, otherwise ignore unordered blocks
        !             3:    MSTATS: enable statistics 
        !             4:    debug: enable assertion checking
        !             5:    longdebug: full arena checks at every transaction
        !             6: */
        !             7: #include <stdlib.h>
        !             8: 
        !             9: #ifdef longdebug
        !            10: #define debug 1
        !            11: #endif
        !            12: #ifdef debug
        !            13: #include <stdio.h>
        !            14: #define ASSERT(p) if(!(p))botch(__LINE__);else
        !            15: static void
        !            16: botch(int n)
        !            17: {
        !            18:        fprintf(stderr,"bad arena, malloc.c line %d\n" ,n);
        !            19:        abort();
        !            20: }
        !            21: #else
        !            22: #define ASSERT(p)
        !            23: #endif
        !            24: 
        !            25: /*     C storage allocator
        !            26:  *     Circular first-fit strategy
        !            27:  *     works with noncontiguous, but monotonically linked, arena.
        !            28:  *     Each block is preceded by a ptr to the (pointer of) 
        !            29:  *     the next following block.
        !            30:  *     Blocks are exact number of words long 
        !            31:  *     aligned to the data type requirements of ALIGN.
        !            32:  *     Pointers to blocks must have BUSY bit 0
        !            33:  *     bit in ptr is 1 for busy, 0 for idle.
        !            34:  *     Gaps in arena are merely noted as busy blocks.
        !            35:  *     Last block of arena is empty and
        !            36:  *     has a pointer to first.
        !            37:  *     Idle blocks are coalesced during space search.
        !            38:  *
        !            39:  *     A different implementation may need to redefine
        !            40:  *     ALIGN, NALIGN, BLOCK, BUSY, INT,
        !            41:  *     where INT is integer type to which a pointer can be cast.
        !            42:  *     Space is obtained from sbrk in multiples of BLOCK.
        !            43: */
        !            44: #define INT int
        !            45: #define ALIGN int
        !            46: #define NALIGN 1
        !            47: #define WORD sizeof(union store)
        !            48: #define BLOCK (1<<15)
        !            49: #define BUSY 1
        !            50: #define NULL 0
        !            51: #define testbusy(p) ((INT)(p)&BUSY)
        !            52: #define setbusy(p) (union store *)((INT)(p)|BUSY)
        !            53: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
        !            54: 
        !            55: union store {
        !            56:              union store *ptr;
        !            57:              ALIGN dummy[NALIGN];
        !            58:              int calloc;       /*calloc clears an array of integers*/
        !            59: };
        !            60: 
        !            61: /* alloca should have type union store.
        !            62:  * The funny business gets it initialized without complaint. */
        !            63: #define addr(a) (union store*)&a
        !            64: static char *alloca = (char*)&alloca + BUSY;   /* initial arena */
        !            65: static union store *allocb = addr(alloca);     /*arena base*/
        !            66: static union store *allocc = addr(alloca);     /*all prev blocks known busy*/
        !            67: static union store *allocp = addr(alloca);     /*search ptr*/
        !            68: static union store *alloct = addr(alloca);     /*top cell*/
        !            69: static union store *allocx;    /*for benefit of realloc*/
        !            70: extern void *sbrk(int);
        !            71: 
        !            72: /* A cache list of frequently-used sizes is maintained. From each
        !            73:  * cache entry hangs a chain of available blocks.
        !            74:  * Chains are located by hashing; a block is deleted from chain
        !            75:  * when another size collides; all blocks are cleared on sbrk.
        !            76: */
        !            77: #define CACHEMAX 50    /* largest block to be cached (in words) */
        !            78: #define CACHESIZ 13    /* number of entries (prime) */
        !            79: 
        !            80: static union store *cache[CACHESIZ];
        !            81: static union store *stdmalloc(size_t);
        !            82: static void stdfree(union store *);
        !            83: static draincache(void);
        !            84: int cached(union store *p);
        !            85: static int allock(union store *q);
        !            86: extern void ialloc(void *, size_t);
        !            87: 
        !            88: 
        !            89: #ifdef MSTATS
        !            90: #define Mstats(e) e
        !            91: static long nmalloc, nrealloc, nfree;  /* call statistics */
        !            92: static long walloc, wfree;             /* space statistics */
        !            93: static long chit, ccoll, cdrain, cavail;       /* cache statistics */
        !            94: #else
        !            95: #define Mstats(e)
        !            96: #endif
        !            97: 
        !            98: void *
        !            99: malloc(size_t nbytes)
        !           100: {
        !           101:        register union store *p;
        !           102:        register size_t nw;
        !           103:        register union store **cp;
        !           104: 
        !           105:        Mstats(nmalloc++);
        !           106:        nw = (nbytes+WORD+WORD-1)/WORD;
        !           107:        if(nw<CACHEMAX && nw>=2) {
        !           108:                cp = &cache[nw%CACHESIZ];
        !           109:                p = *cp;
        !           110:                if(p && nw==clearbusy(p->ptr)-p) {
        !           111:                        ASSERT(testbusy(p->ptr));
        !           112:                        *cp = (++p)->ptr;
        !           113:                        Mstats((chit++, cavail--));
        !           114:                        return (char*)p;
        !           115:                }
        !           116:        }
        !           117:        p = stdmalloc(nw);
        !           118:        Mstats(p && (walloc += nw));
        !           119:        return p;
        !           120: }
        !           121: 
        !           122: static union store *
        !           123: stdmalloc(register size_t nw)
        !           124: {
        !           125:        register union store *p, *q;
        !           126:        register size_t temp;
        !           127:        ASSERT(allock(allocp));
        !           128:        for(; ; ) {     /* done at most thrice */
        !           129:                p = allocp;
        !           130:                for(temp=0; ; ) {
        !           131:                        if(!testbusy(p->ptr)) {
        !           132:                                allocp = p;
        !           133:                                while(!testbusy((q=p->ptr)->ptr)) {
        !           134:                                        ASSERT(q>p);
        !           135:                                        p->ptr = q->ptr;
        !           136:                                }
        !           137:                                if(q>=p+nw && p+nw>=p)
        !           138:                                        goto found;
        !           139:                        }
        !           140:                        q = p;
        !           141:                        p = clearbusy(p->ptr);
        !           142:                        if(p <= q) {
        !           143:                                ASSERT(p==allocb&&q==alloct);
        !           144:                                if(++temp>1)
        !           145:                                        break;
        !           146:                                ASSERT(allock(allocc));
        !           147:                                p = allocc;
        !           148:                        }
        !           149:                }
        !           150:                p = (union store *)sbrk(0);
        !           151:                temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
        !           152:                do {
        !           153:                        if(p+temp > p) {        /*check wrap*/
        !           154:                                q = (union store *)sbrk(temp*WORD);
        !           155:                                if((INT)q != -1)
        !           156:                                        goto mextend;
        !           157:                        }
        !           158:                        temp -= (temp-nw)/2;
        !           159:                } while(temp-nw > 1);
        !           160:                if(draincache())
        !           161:                        continue;
        !           162:                return NULL;
        !           163: mextend:
        !           164:                draincache();
        !           165:                ialloc(q, temp*WORD);
        !           166:        }
        !           167: found:
        !           168:        allocp += nw;
        !           169:        if(q>allocp) {
        !           170:                allocx = allocp->ptr;
        !           171:                allocp->ptr = p->ptr;
        !           172:        }
        !           173:        p->ptr = setbusy(allocp);
        !           174:        if(p<=allocc) {
        !           175:                ASSERT(p==allocc);
        !           176:                while(testbusy(allocc->ptr)
        !           177:                     && (q=clearbusy(allocc->ptr))>allocc)
        !           178:                        allocc = q;
        !           179:        }
        !           180:        return p+1;
        !           181: }
        !           182: 
        !           183: void
        !           184: free(void *ap)
        !           185: {
        !           186:        register union store *p = ap, *q;
        !           187:        register size_t nw;
        !           188:        register union store **cp;
        !           189: 
        !           190:        if(p==NULL)
        !           191:                return;
        !           192:        --p;
        !           193:        ASSERT(allock(p));
        !           194:        ASSERT(testbusy(p->ptr));
        !           195:        ASSERT(!cached(p));
        !           196:        nw = clearbusy(p->ptr) - p;
        !           197:        Mstats((nfree++, wfree += nw));
        !           198:        ASSERT(nw>0);
        !           199:        if(nw<CACHEMAX && nw>=2) {
        !           200:                cp = &cache[nw%CACHESIZ];
        !           201:                q = *cp;
        !           202:                if(!q || nw==clearbusy(q->ptr)-q) {
        !           203:                        p[1].ptr = q;
        !           204:                        *cp = p;
        !           205:                        Mstats(cavail++);
        !           206:                        return;
        !           207:                } else Mstats(q && ccoll++);
        !           208:        }
        !           209:        stdfree(p+1);
        !           210: }
        !           211: 
        !           212: /*     freeing strategy tuned for LIFO allocation
        !           213: */
        !           214: static void
        !           215: stdfree(register union store *p)
        !           216: {
        !           217:        allocp = --p;
        !           218:        if(p < allocc)
        !           219:                allocc = p;
        !           220:        ASSERT(allock(allocp));
        !           221:        p->ptr = clearbusy(p->ptr);
        !           222:        ASSERT(p->ptr > allocp);
        !           223: }
        !           224: 
        !           225: static
        !           226: draincache(void)
        !           227: {
        !           228:        register union store **cp = cache+CACHESIZ;
        !           229:        register union store *q;
        !           230:        int anyfreed = 0;
        !           231:        while(--cp>=cache) {
        !           232:                while(q = *cp) {
        !           233:                        ASSERT(testbusy(q->ptr));
        !           234:                        ASSERT((clearbusy(q->ptr)-q)%CACHESIZ==cp-cache);
        !           235:                        ASSERT(q>=allocb&&q<=alloct);
        !           236:                        stdfree(++q);
        !           237:                        anyfreed++;
        !           238:                        *cp = q->ptr;
        !           239:                }
        !           240:        }
        !           241:        Mstats((cdrain+=anyfreed, cavail=0));
        !           242:        return anyfreed;
        !           243: }
        !           244: 
        !           245: /* ialloc(q, nbytes) inserts a block that did not come
        !           246:  * from malloc into the arena
        !           247:  *
        !           248:  * q points to new block
        !           249:  * r points to last of new block
        !           250:  * p points to last cell of arena before new block
        !           251:  * s points to first cell of arena after new block
        !           252: */
        !           253: 
        !           254: void
        !           255: ialloc(void *qq, size_t nbytes)
        !           256: {
        !           257:        register union store *p, *q, *s;
        !           258:        union store *r;
        !           259: 
        !           260:        q = qq;
        !           261:        r = q + (nbytes/WORD) - 1;
        !           262:        q->ptr = r;
        !           263:        if(q > alloct) {
        !           264:                p = alloct;
        !           265:                s = allocb;
        !           266:                alloct = r;
        !           267:        } else {
        !           268: #ifdef IALLOC  /* useful only in small address spaces */
        !           269:                for(p=allocb; ; p=s) {
        !           270:                        s = clearbusy(p->ptr);
        !           271:                        if(s==allocb)
        !           272:                                break;
        !           273:                        ASSERT(s>p);
        !           274:                        if(s>r) {
        !           275:                                if(p<q)
        !           276:                                        break;
        !           277:                                else
        !           278:                                        ASSERT(p>r);
        !           279:                        }
        !           280:                }
        !           281:                if(allocb > q)
        !           282:                        allocb = q;
        !           283:                if(allocc > q)
        !           284:                        allocc = q;
        !           285:                allocp = allocc;
        !           286: #else
        !           287:                return;
        !           288: #endif
        !           289:        }
        !           290:        p->ptr = q==p+1? q: setbusy(q);
        !           291:        r->ptr = s==r+1? s: setbusy(s);
        !           292:        while(testbusy(allocc->ptr))
        !           293:                allocc = clearbusy(allocc->ptr);
        !           294: }
        !           295: 
        !           296: /*     realloc(p, nbytes) reallocates a block obtained from malloc()
        !           297:  *     to have new size nbytes, and old content.
        !           298:  *     Returns new location, or 0 on failure
        !           299: */
        !           300: 
        !           301: void *
        !           302: realloc(void *pp, size_t nbytes)
        !           303: {
        !           304:        register union store *p = pp;
        !           305:        register union store *s, *t;
        !           306:        register union store *q;
        !           307:        register size_t nw;
        !           308:        size_t onw;
        !           309: 
        !           310:        Mstats(nrealloc++);
        !           311:        if(p==NULL)
        !           312:                return malloc(nbytes);
        !           313:        ASSERT(testbusy(p[-1].ptr));
        !           314:        ASSERT(allock(p-1));
        !           315:        stdfree(p);
        !           316:        onw = p[-1].ptr - p;
        !           317:        nw = (nbytes+WORD-1)/WORD;
        !           318:        q = stdmalloc(nw+1);
        !           319:        if(nw<onw) {
        !           320:                Mstats(wfree += q?onw-nw:onw+1);
        !           321:                onw = nw;
        !           322:        } else
        !           323:                Mstats(q && (walloc+=nw-onw) || (wfree+=onw+1));
        !           324:        if(q==NULL || q==p)
        !           325:                return (char*)q;
        !           326:        ASSERT(q<p||q>p[-1].ptr);
        !           327:        for(s=p, t=q; onw--!=0; )
        !           328:                *t++ = *s++;
        !           329:        ASSERT(clearbusy(q[-1].ptr)-q==nw);
        !           330:        if(q<p && q+nw>=p)
        !           331:                (q+(q+nw-p))->ptr = allocx;
        !           332:        ASSERT(allock(q-1));
        !           333:        return (char *)q;
        !           334: }
        !           335: 
        !           336: static int
        !           337: allock(union store *q)
        !           338: {
        !           339: #ifdef longdebug
        !           340:        register union store *p, *r;
        !           341:        register union store **cp;
        !           342:        int x, y;
        !           343:        for(cp=cache+CACHESIZ; --cp>=cache; ) {
        !           344:                if((p= *cp)==0)
        !           345:                        continue;
        !           346:                x = clearbusy(p->ptr) - p;
        !           347:                ASSERT(x%CACHESIZ==cp-cache);
        !           348:                for( ; p; p = p[1].ptr) {
        !           349:                        ASSERT(testbusy(p->ptr));
        !           350:                        ASSERT(clearbusy(p->ptr)-p==x);
        !           351:                }
        !           352:        }
        !           353:        x = 0, y = 0;
        !           354:        p = allocb;
        !           355:        for( ; (r=clearbusy(p->ptr)) > p; p=r) {
        !           356:                if(p==allocc)
        !           357:                        y++;
        !           358:                ASSERT(y||testbusy(p->ptr));
        !           359:                if(p==q)
        !           360:                        x++;
        !           361:        }
        !           362:        ASSERT(r==allocb);
        !           363:        ASSERT(x==1||p==q);
        !           364:        ASSERT(y||p==allocc);
        !           365: #else
        !           366:        ASSERT((unsigned)q/WORD*WORD==(unsigned)q);
        !           367:        ASSERT(q>=allocb&&q<=alloct);
        !           368: #endif
        !           369:        return 1;
        !           370: }
        !           371: 
        !           372: void
        !           373: mstats(void)
        !           374: {
        !           375: #ifdef MSTATS
        !           376: #ifndef stderr
        !           377: #include <stdio.h>
        !           378: #endif
        !           379:        fprintf(stderr, "Malloc statistics, including overhead bytes\n");
        !           380:        fprintf(stderr, "Arena: bottom %ld, top %ld\n",
        !           381:                (long)clearbusy(alloca), (long)alloct);
        !           382:        fprintf(stderr, "Calls: malloc %ld, realloc %ld, free %ld\n",
        !           383:                nmalloc, nrealloc, nfree);
        !           384:        fprintf(stderr, "Bytes: allocated or extended %ld, ",
        !           385:                walloc*WORD);
        !           386:        fprintf(stderr, "freed or cut %ld\n", wfree*WORD);
        !           387:        fprintf(stderr,"Cache: hits %ld, collisions %ld, discards %ld, blocks avail %ld\n",
        !           388:                chit, ccoll, cdrain, cavail);
        !           389: #endif
        !           390: }
        !           391: 
        !           392: #ifdef debug
        !           393: int
        !           394: cached(union store *p)
        !           395: {
        !           396:        union store *q = cache[(clearbusy(p->ptr)-p)%CACHESIZ];
        !           397:        for( ; q; q=q[1].ptr)
        !           398:                ASSERT(p!=q);
        !           399:        return 0;
        !           400: }
        !           401: #endif

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