Return to malloc.c CVS log

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

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

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