Return to galloc.c CVS log

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

Annotation of researchv9/libc/gen/galloc.c, revision 1.1

1.1     ! root        1: /* garbage collecting storage allocator; definition of
        !             2:  * cell is compatible with malloc, but slightly less portable
        !             3: */
        !             4: 
        !             5: typedef struct dummy { struct dummy *ptr;} cell;
        !             6: 
        !             7: #define GCMAX 5000
        !             8: #define GCMIN 50
        !             9: #define BPW (8*sizeof(*gcmap)) /*bits per word*/
        !            10: #define QBPW >>LOGBPW  /* quotient /BPW if BPW not power of 2 */
        !            11: #define RBPW &(BPW-1)  /* remainder %BPW if BPW not power of 2 */
        !            12: #define MASK (sizeof(cell)-1)  /*assumes cell aligned to power of 2*/
        !            13: #define testbit(b,n) ((b[(n) QBPW]>>((n) RBPW))&1)
        !            14: #define setbit(b,n) (b[(n) QBPW]|=1<<((n) RBPW))
        !            15: #define clrbit(b,n) (b[(n) QBPW]&=~(1<<((n) RBPW)))
        !            16: #define testbusy(p) (*(int*)((p)-1)&1)
        !            17: #define clearbusy(p) (*(int*)((p)-1)&=~1)
        !            18: #define setbusy(p) (*(int*)((p)-1)|=1)
        !            19: #define endptr(p) (cell*)(*(int*)((p)-1)&~1)
        !            20: 
        !            21: #ifdef pdp11
        !            22: #define STACKTOP (cell*)(-2)
        !            23: #define STATICBOT (cell*)2     /*appropriate for cc -i*/
        !            24: #define LOGBPW 4
        !            25: #endif
        !            26: #ifdef vax
        !            27: #define STACKTOP (cell*)0x7ffffffc
        !            28: #define STATICBOT etext
        !            29: #define LOGBPW 5
        !            30: #endif
        !            31: #ifdef sun
        !            32: #define STACKTOP (cell*)0x7ffffffc
        !            33: #define STATICBOT etext
        !            34: #define LOGBPW 5
        !            35: #endif
        !            36: #define STATICTOP end
        !            37: 
        !            38: static unsigned *gcmap;        /*bitmap of busy blocks, grows by powers of 2*/
        !            39: static unsigned gcsize;        /*number of bits in gcmap*/
        !            40: long gcmax = GCMAX;    /*max number of allocations between collections*/
        !            41: long gcmin = GCMIN;    /*min number*/
        !            42: extern cell end[];
        !            43: extern cell etext[];
        !            44: 
        !            45: char *
        !            46: galloc(n)
        !            47: unsigned n;
        !            48: {
        !            49:        static long count;      /*number of allocations since collection*/
        !            50:        register cell* q;
        !            51:        register unsigned d;
        !            52:        unsigned qd;
        !            53:        char *malloc();
        !            54:        while(++count >= gcmax ||
        !            55:              (q=(cell*)malloc(n)) == 0) {      /* at most twice*/
        !            56:                if(count <= gcmin)
        !            57:                        return(0);
        !            58:                garbage();
        !            59:                count = 0;
        !            60:        }
        !            61:        if(q < STATICTOP)       /* probably due to ialloc() */
        !            62:                return((char*)q);
        !            63:        qd = q - STATICTOP;
        !            64:        if(qd >= gcsize) {
        !            65:                unsigned *tgmap;
        !            66:                register unsigned bsize;
        !            67:                if(BPW != 1<<LOGBPW)
        !            68:                        abort();
        !            69:                if(gcsize==0) {
        !            70:                        bsize = 16384 QBPW;
        !            71:                        tgmap = (unsigned*)malloc(bsize*sizeof(*gcmap));
        !            72:                } else {
        !            73:                        bsize = (gcsize QBPW)*2;
        !            74:                        tgmap = (unsigned*)realloc((char*)gcmap,
        !            75:                                bsize*sizeof(*gcmap));
        !            76:                }
        !            77:                if(tgmap==0)
        !            78:                        return(0);
        !            79:                gcmap = tgmap;
        !            80:                for(d=gcsize QBPW; d<bsize; d++)
        !            81:                        gcmap[d] = 0;
        !            82:                gcsize = bsize*BPW;
        !            83:        }
        !            84:        setbit(gcmap, qd);
        !            85:        return((char *)q);
        !            86: }
        !            87: 
        !            88: /* pointer reversal algorithm
        !            89:  * gcmap bit is set for first word of each galloc'ed block
        !            90:  * make all galloc'd blocks appear idle and mark them busy as
        !            91:  * the garbage collector reaches them
        !            92: */
        !            93: garbage()
        !            94: {
        !            95:        cell fence;     /* must really be on the stack*/
        !            96:        register cell *p, *q;
        !            97:        register unsigned d;
        !            98:        register cell *s, *t, *u;       /* lots of regs to force full save */
        !            99:        register unsigned asize;
        !           100:        asize = (cell*)sbrk(0) - STATICTOP;
        !           101:        if(asize > gcsize)
        !           102:                asize = gcsize;
        !           103:        for(d=0; d<asize; d++)
        !           104:                if(testbit(gcmap,d))
        !           105:                        clearbusy(STATICTOP+d);
        !           106:        q = 0;
        !           107:        for(s=STATICBOT; s<STACKTOP; s=(s==STATICTOP-1?&fence:s+1)) {
        !           108:                p = s->ptr;
        !           109:                for(;;) {
        !           110:                        while(!((int)p&MASK) && /*is p a cell-aligned address?*/
        !           111:                              p>=STATICTOP &&           /* pointing within */
        !           112:                              (d=p-STATICTOP)<asize &&  /* bounds of arena? */
        !           113:                              testbit(gcmap, d) &&      /*to galloc-ed block?*/
        !           114:                              !testbusy(p)) {           /* not yet visited?*/
        !           115:                                setbusy(p);
        !           116:                                /* q,p,*p = p,*p,q */
        !           117:                                t = p;
        !           118:                                p = p->ptr;
        !           119:                                t->ptr = q;
        !           120:                                q = t;
        !           121:                        }
        !           122:                        while(q!=0) {
        !           123:                                for(d=q-STATICTOP; !testbit(gcmap,d); d--)
        !           124:                                        continue;
        !           125:                                if(q<endptr(t=STATICTOP+d)-1)
        !           126:                                        break;
        !           127:                                /* q,*q,p = *q,p,t */
        !           128:                                u = q;
        !           129:                                q = q->ptr;
        !           130:                                u->ptr = p;
        !           131:                                p = t;
        !           132:                        }
        !           133:                        if(q==0)
        !           134:                                break;
        !           135:                        /* *q,p,q[1] = p,q[1],*q; q++ */
        !           136:                        t = q->ptr;
        !           137:                        q->ptr = p;
        !           138:                        q++;
        !           139:                        p = q->ptr;
        !           140:                        q->ptr = t;
        !           141:                }
        !           142:        }
        !           143:        for(d=0; d<asize; d++) {
        !           144:                if(testbit(gcmap,d)&&!testbusy(STATICTOP+d))
        !           145:                        clrbit(gcmap,d);
        !           146:        }
        !           147: }
        !           148: 
        !           149: gfree(p)
        !           150: cell *p;
        !           151: {
        !           152:        free((char*)p);
        !           153:        clrbit(gcmap,p-STATICTOP);
        !           154: }

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