![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to galloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / libc / gen|
Return to galloc.c CVS log | Up to [Research Unix] / researchv10no / libc / gen |
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.