![[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] / researchv9 / libc / gen|
Return to galloc.c CVS log | Up to [Research Unix] / researchv9 / 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: #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.