Return to galloc.c CVS log

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

Annotation of researchv10no/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: #define STATICTOP end
        !            32: 
        !            33: static unsigned *gcmap;        /*bitmap of busy blocks, grows by powers of 2*/
        !            34: static unsigned gcsize;        /*number of bits in gcmap*/
        !            35: long gcmax = GCMAX;    /*max number of allocations between collections*/
        !            36: long gcmin = GCMIN;    /*min number*/
        !            37: extern cell end[];
        !            38: extern cell etext[];
        !            39: 
        !            40: char *
        !            41: galloc(n)
        !            42: unsigned n;
        !            43: {
        !            44:        static long count;      /*number of allocations since collection*/
        !            45:        register cell* q;
        !            46:        register unsigned d;
        !            47:        unsigned qd;
        !            48:        char *malloc();
        !            49:        while(++count >= gcmax ||
        !            50:              (q=(cell*)malloc(n)) == 0) {      /* at most twice*/
        !            51:                if(count <= gcmin)
        !            52:                        return(0);
        !            53:                garbage();
        !            54:                count = 0;
        !            55:        }
        !            56:        if(q < STATICTOP)       /* probably due to ialloc() */
        !            57:                return((char*)q);
        !            58:        qd = q - STATICTOP;
        !            59:        if(qd >= gcsize) {
        !            60:                unsigned *tgmap;
        !            61:                register unsigned bsize;
        !            62:                if(BPW != 1<<LOGBPW)
        !            63:                        abort();
        !            64:                if(gcsize==0) {
        !            65:                        bsize = 16384 QBPW;
        !            66:                        tgmap = (unsigned*)malloc(bsize*sizeof(*gcmap));
        !            67:                } else {
        !            68:                        bsize = (gcsize QBPW)*2;
        !            69:                        tgmap = (unsigned*)realloc((char*)gcmap,
        !            70:                                bsize*sizeof(*gcmap));
        !            71:                }
        !            72:                if(tgmap==0)
        !            73:                        return(0);
        !            74:                gcmap = tgmap;
        !            75:                for(d=gcsize QBPW; d<bsize; d++)
        !            76:                        gcmap[d] = 0;
        !            77:                gcsize = bsize*BPW;
        !            78:        }
        !            79:        setbit(gcmap, qd);
        !            80:        return((char *)q);
        !            81: }
        !            82: 
        !            83: /* pointer reversal algorithm
        !            84:  * gcmap bit is set for first word of each galloc'ed block
        !            85:  * make all galloc'd blocks appear idle and mark them busy as
        !            86:  * the garbage collector reaches them
        !            87: */
        !            88: garbage()
        !            89: {
        !            90:        cell fence;     /* must really be on the stack*/
        !            91:        register cell *p, *q;
        !            92:        register unsigned d;
        !            93:        register cell *s, *t, *u;       /* lots of regs to force full save */
        !            94:        register unsigned asize;
        !            95:        asize = (cell*)sbrk(0) - STATICTOP;
        !            96:        if(asize > gcsize)
        !            97:                asize = gcsize;
        !            98:        for(d=0; d<asize; d++)
        !            99:                if(testbit(gcmap,d))
        !           100:                        clearbusy(STATICTOP+d);
        !           101:        q = 0;
        !           102:        for(s=STATICBOT; s<STACKTOP; s=(s==STATICTOP-1?&fence:s+1)) {
        !           103:                p = s->ptr;
        !           104:                for(;;) {
        !           105:                        while(!((int)p&MASK) && /*is p a cell-aligned address?*/
        !           106:                              p>=STATICTOP &&           /* pointing within */
        !           107:                              (d=p-STATICTOP)<asize &&  /* bounds of arena? */
        !           108:                              testbit(gcmap, d) &&      /*to galloc-ed block?*/
        !           109:                              !testbusy(p)) {           /* not yet visited?*/
        !           110:                                setbusy(p);
        !           111:                                /* q,p,*p = p,*p,q */
        !           112:                                t = p;
        !           113:                                p = p->ptr;
        !           114:                                t->ptr = q;
        !           115:                                q = t;
        !           116:                        }
        !           117:                        while(q!=0) {
        !           118:                                for(d=q-STATICTOP; !testbit(gcmap,d); d--)
        !           119:                                        continue;
        !           120:                                if(q<endptr(t=STATICTOP+d)-1)
        !           121:                                        break;
        !           122:                                /* q,*q,p = *q,p,t */
        !           123:                                u = q;
        !           124:                                q = q->ptr;
        !           125:                                u->ptr = p;
        !           126:                                p = t;
        !           127:                        }
        !           128:                        if(q==0)
        !           129:                                break;
        !           130:                        /* *q,p,q[1] = p,q[1],*q; q++ */
        !           131:                        t = q->ptr;
        !           132:                        q->ptr = p;
        !           133:                        q++;
        !           134:                        p = q->ptr;
        !           135:                        q->ptr = t;
        !           136:                }
        !           137:        }
        !           138:        for(d=0; d<asize; d++) {
        !           139:                if(testbit(gcmap,d)&&!testbusy(STATICTOP+d))
        !           140:                        clrbit(gcmap,d);
        !           141:        }
        !           142: }
        !           143: 
        !           144: gfree(p)
        !           145: cell *p;
        !           146: {
        !           147:        free((char*)p);
        !           148:        clrbit(gcmap,p-STATICTOP);
        !           149: }

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