1 #include "lib9.h"
2 #include "interp.h"
3 #include "pool.h"
4
5 enum
6 {
7 Quanta = 50, /* Allocated blocks to sweep each time slice usually */
8 MaxQuanta = 15*Quanta,
9 PTRHASH = (1<<5)
10 };
11
12 static int quanta = Quanta;
13 static int gce, gct = 1;
14
15 typedef struct Ptrhash Ptrhash;
16 struct Ptrhash
17 {
18 Heap *value;
19 Ptrhash *next;
20 };
21
22 int nprop;
23 int gchalt;
24 int mflag;
25 int mutator = 0;
26 int gccolor = 3;
27
28 ulong gcnruns;
29 ulong gcsweeps;
30 ulong gcbroken;
31 ulong gchalted;
32 ulong gcepochs;
33 uvlong gcdestroys;
34 uvlong gcinspects;
35
36 static int marker = 1;
37 static int sweeper = 2;
38 static Bhdr* base;
39 static Bhdr* limit;
40 Bhdr* ptr;
41 static int visit;
42 extern Pool* heapmem;
43 static Ptrhash *ptrtab[PTRHASH];
44 static Ptrhash *ptrfree;
45
46 #define HASHPTR(p) (((ulong)(p) >> 6) & (PTRHASH - 1))
47
48 void
ptradd(Heap * v)49 ptradd(Heap *v)
50 {
51 int h;
52 Ptrhash *p;
53
54 if ((p = ptrfree) != nil)
55 ptrfree = p->next;
56 else if ((p = malloc(sizeof (Ptrhash))) == nil)
57 error("ptradd malloc");
58 h = HASHPTR(v);
59 p->value = v;
60 p->next = ptrtab[h];
61 ptrtab[h] = p;
62 }
63
64 void
ptrdel(Heap * v)65 ptrdel(Heap *v)
66 {
67 Ptrhash *p, **l;
68
69 for (l = &ptrtab[HASHPTR(v)]; (p = *l) != nil; l = &p->next) {
70 if (p->value == v) {
71 *l = p->next;
72 p->next = ptrfree;
73 ptrfree = p;
74 return;
75 }
76 }
77 /* ptradd must have failed */
78 }
79
80 static void
ptrmark(void)81 ptrmark(void)
82 {
83 int i;
84 Heap *h;
85 Ptrhash *p;
86
87 for (i = 0; i < PTRHASH; i++) {
88 for (p = ptrtab[i]; p != nil; p = p->next) {
89 h = p->value;
90 Setmark(h);
91 }
92 }
93 }
94
95 void
noptrs(Type * t,void * vw)96 noptrs(Type *t, void *vw)
97 {
98 USED(t);
99 USED(vw);
100 }
101
102 static int markdepth;
103
104 /* code simpler with a depth search compared to a width search*/
105 void
markheap(Type * t,void * vw)106 markheap(Type *t, void *vw)
107 {
108 Heap *h;
109 uchar *p;
110 int i, c, m;
111 WORD **w, **q;
112 Type *t1;
113
114 if(t == nil || t->np == 0)
115 return;
116
117 markdepth++;
118 w = (WORD**)vw;
119 p = t->map;
120 for(i = 0; i < t->np; i++) {
121 c = *p++;
122 if(c != 0) {
123 q = w;
124 for(m = 0x80; m != 0; m >>= 1) {
125 if((c & m) && *q != H) {
126 h = D2H(*q);
127 Setmark(h);
128 if(h->color == propagator && --visit >= 0 && markdepth < 64){
129 gce--;
130 h->color = mutator;
131 if((t1 = h->t) != nil)
132 t1->mark(t1, H2D(void*, h));
133 }
134 }
135 q++;
136 }
137 }
138 w += 8;
139 }
140 markdepth--;
141 }
142
143 /*
144 * This routine should be modified to be incremental, but how?
145 */
146 void
markarray(Type * t,void * vw)147 markarray(Type *t, void *vw)
148 {
149 int i;
150 Heap *h;
151 uchar *v;
152 Array *a;
153
154 USED(t);
155
156 a = vw;
157 t = a->t;
158 if(a->root != H) {
159 h = D2H(a->root);
160 Setmark(h);
161 }
162
163 if(t->np == 0)
164 return;
165
166 v = a->data;
167 for(i = 0; i < a->len; i++) {
168 markheap(t, v);
169 v += t->size;
170 }
171 visit -= a->len;
172 }
173
174 void
marklist(Type * t,void * vw)175 marklist(Type *t, void *vw)
176 {
177 List *l;
178 Heap *h;
179
180 USED(t);
181 l = vw;
182 markheap(l->t, l->data);
183 while(visit > 0) {
184 l = l->tail;
185 if(l == H)
186 return;
187 h = D2H(l);
188 Setmark(h);
189 markheap(l->t, l->data);
190 visit--;
191 }
192 l = l->tail;
193 if(l != H) {
194 D2H(l)->color = propagator;
195 nprop = 1;
196 }
197 }
198
199 static void
rootset(Prog * root)200 rootset(Prog *root)
201 {
202 Heap *h;
203 Type *t;
204 Frame *f;
205 Module *m;
206 Stkext *sx;
207 Modlink *ml;
208 uchar *fp, *sp, *ex, *mp;
209
210 mutator = gccolor % 3;
211 marker = (gccolor-1)%3;
212 sweeper = (gccolor-2)%3;
213
214 while(root != nil) {
215 ml = root->R.M;
216 h = D2H(ml);
217 Setmark(h);
218 mp = ml->MP;
219 if(mp != H) {
220 h = D2H(mp);
221 Setmark(h);
222 }
223
224 sp = root->R.SP;
225 ex = root->R.EX;
226 while(ex != nil) {
227 sx = (Stkext*)ex;
228 fp = sx->reg.tos.fu;
229 while(fp != sp) {
230 f = (Frame*)fp;
231 t = f->t;
232 if(t == nil)
233 t = sx->reg.TR;
234 fp += t->size;
235 t->mark(t, f);
236 ml = f->mr;
237 if(ml != nil) {
238 h = D2H(ml);
239 Setmark(h);
240 mp = ml->MP;
241 if(mp != H) {
242 h = D2H(mp);
243 Setmark(h);
244 }
245 }
246 }
247 ex = sx->reg.EX;
248 sp = sx->reg.SP;
249 }
250
251 root = root->next;
252 }
253
254 for(m = modules; m != nil; m = m->link) {
255 if(m->origmp != H) {
256 h = D2H(m->origmp);
257 Setmark(h);
258 }
259 }
260
261 ptrmark();
262 }
263
264 static int
okbhdr(Bhdr * b)265 okbhdr(Bhdr *b)
266 {
267 if(b == nil)
268 return 0;
269 switch(b->magic) {
270 case MAGIC_A:
271 case MAGIC_F:
272 case MAGIC_E:
273 case MAGIC_I:
274 return 1;
275 }
276 return 0;
277 }
278
279 static void
domflag(Heap * h)280 domflag(Heap *h)
281 {
282 int i;
283 Module *m;
284
285 print("sweep h=0x%lux t=0x%lux c=%d", (ulong)h, (ulong)h->t, h->color);
286 for(m = modules; m != nil; m = m->link) {
287 for(i = 0; i < m->ntype; i++) {
288 if(m->type[i] == h->t) {
289 print(" module %s desc %d", m->name, i);
290 break;
291 }
292 }
293 }
294 print("\n");
295 if(mflag > 1)
296 abort();
297 }
298
299 void
rungc(Prog * p)300 rungc(Prog *p)
301 {
302 Type *t;
303 Heap *h;
304 Bhdr *b;
305
306 gcnruns++;
307 if(gchalt) {
308 gchalted++;
309 return;
310 }
311 if(base == nil) {
312 gcsweeps++;
313 b = poolchain(heapmem);
314 base = b;
315 ptr = b;
316 limit = B2LIMIT(b);
317 }
318
319 /* Chain broken ? */
320 if(!okbhdr(ptr)) {
321 base = nil;
322 gcbroken++;
323 return;
324 }
325
326 for(visit = quanta; visit > 0; ) {
327 if(ptr->magic == MAGIC_A) {
328 visit--;
329 gct++;
330 gcinspects++;
331 h = B2D(ptr);
332 t = h->t;
333 if(h->color == propagator) {
334 gce--;
335 h->color = mutator;
336 if(t != nil)
337 t->mark(t, H2D(void*, h));
338 }
339 else
340 if(h->color == sweeper) {
341 gce++;
342 if(0 && mflag)
343 domflag(h);
344 if(heapmonitor != nil)
345 heapmonitor(2, h, 0);
346 if(t != nil) {
347 gclock();
348 t->free(h, 1);
349 gcunlock();
350 freetype(t);
351 }
352 gcdestroys++;
353 poolfree(heapmem, h);
354 }
355 }
356 ptr = B2NB(ptr);
357 if(ptr >= limit) {
358 base = base->clink;
359 if(base == nil)
360 break;
361 ptr = base;
362 limit = B2LIMIT(base);
363 }
364 }
365
366 quanta = (MaxQuanta+Quanta)/2 + ((MaxQuanta-Quanta)/20)*((100*gce)/gct);
367 if(quanta < Quanta)
368 quanta = Quanta;
369 if(quanta > MaxQuanta)
370 quanta = MaxQuanta;
371
372 if(base != nil) /* Completed this iteration ? */
373 return;
374 if(nprop == 0) { /* Completed the epoch ? */
375 gcepochs++;
376 gccolor++;
377 rootset(p);
378 gce = 0;
379 gct = 1;
380 return;
381 }
382 nprop = 0;
383 }
384