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 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 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 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 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 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 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 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 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 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 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 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