![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / sml / src / runtime|
Return to gc.c CVS log | Up to [Research Unix] / researchv10no / cmd / sml / src / runtime |
1.1 ! root 1: /* Copyright 1989 by AT&T Bell Laboratories */ ! 2: #include "tags.h" ! 3: #include "descriptor.h" ! 4: ! 5: #ifdef GCDEBUG ! 6: #define chatarg chatting ! 7: #endif ! 8: ! 9: /* registers: ! 10: inside arenas: allocation is on word boundaries and in units a multiple ! 11: of a word (4 bytes) so words with odd contents are not pointers. ! 12: Conversely, if a word is pointed to by a pointer p (i.e., the word ! 13: is p[0], then p[-1] contains a descriptor of the record the word is in: ! 14: struct { ! 15: unsigned int flg:width_tags; least sig bits ! 16: int len:32-width_tags; ! 17: } mem; ! 18: flag is even: look in previous word for descriptor ! 19: flag is odd: this is the descriptor. ! 20: len gives the number of 4-byte words. (not incl. descriptor) ! 21: For any record in a collectable area, len>0 ! 22: when the gc isn't running: ! 23: flag=1 record containing pointers & integers ! 24: flag=5 record containing no pointers ! 25: flag=7 look in p[-len-1] for descriptor ! 26: when gc is running, descriptor in the TO space: ! 27: as above, but flag=3 not possible ! 28: when the gc is running, descriptor in the FROM space: ! 29: flag=1 unmoved record containing pointers & integers ! 30: flag=3 record has already been moved, in which case, ! 31: p[0] is the forwarding pointer. ! 32: flag=5 unmoved record containing no pointers ! 33: flag=7 look in p[-len-1] for descriptor ! 34: ! 35: In a record containing pointers & integers, ! 36: any even number is a pointer, any odd number is not a pointer. ! 37: ! 38: There are occasional pointers to places outside the GC arena; ! 39: these get copied intact. ! 40: ! 41: Format of linked list of stored-into ref cells: ! 42: p[0] = pointer to a ref or array cell that's been stored into. ! 43: p[1] = index within object of modified slot ! 44: p[2] = next object on list (1 for nil) ! 45: ! 46: */ ! 47: ! 48: int ** (*gmore)(); ! 49: static int **to_ptr, **to_lim, **to_lim0; ! 50: static int **lowest, **highest; ! 51: static int repair; ! 52: static int any_weak; ! 53: ! 54: extern int store_preserve, preserving; ! 55: ! 56: /*static ! 57: xgc(refloc) ! 58: register int *refloc;*/ ! 59: #define xgc(refloc)\ ! 60: {register int *m = *((int**)(refloc));\ ! 61: /* if refloc is not a pointer,\ ! 62: or is not in the allocated area, just leave it alone */\ ! 63: if(is_ptr(m) && (m >= (int*)lowest && m < (int*)highest))\ ! 64: { m--;\ ! 65: for(;;)\ ! 66: {\ ! 67: switch(get_tag(m)) {\ ! 68: case tag_backptr:\ ! 69: m -= get_len(m);\ ! 70: continue;\ ! 71: case tag_embedded:\ ! 72: m--; continue;\ ! 73: case tag_string:\ ! 74: case tag_bytearray:\ ! 75: {register int **i=(int**)m, **j=to_ptr, len1 = (get_len(m)+7)>>2;\ ! 76: if (j+len1 > to_lim) do {if (repair) \ ! 77: {repair=0; to_lim=to_lim0;} \ ! 78: else to_lim=gmore();}\ ! 79: while (j+len1 > to_lim);\ ! 80: do {*j++ = *i++;} while (--len1 > 0);\ ! 81: if (repair) \ ! 82: {if (to_ptr+5 < to_lim) \ ! 83: {* -- to_lim = ((int**)m)[1]; \ ! 84: * -- to_lim = m+1; \ ! 85: } \ ! 86: else {repair=0; to_lim=to_lim0;} \ ! 87: } \ ! 88: ((int**)m)[1]= 1+(int*)to_ptr;\ ! 89: to_ptr = j;\ ! 90: }\ ! 91: (*m) = tag_forwarded;\ ! 92: *(int*)(refloc) += ((int*)m)[1] - ((int)(m+1));\ ! 93: break;\ ! 94: case tag_array:\ ! 95: if (preserving) \ ! 96: {*to_ptr++ = (int*)(16*3+1); \ ! 97: *to_ptr++ = m+1; \ ! 98: *to_ptr++ = (int*)-1; \ ! 99: *to_ptr++ = (int*)store_preserve; \ ! 100: store_preserve = (int) (to_ptr-3); \ ! 101: } \ ! 102: case tag_record:\ ! 103: {register int **i=(int**)m, **j=to_ptr, len1 = get_len(m)+1;\ ! 104: if (j+len1 > to_lim) do {if (repair) \ ! 105: {repair=0; to_lim=to_lim0;} \ ! 106: else to_lim=gmore();}\ ! 107: while (j+len1 > to_lim);\ ! 108: do {*j++ = *i++;} while (--len1 > 0);\ ! 109: if (repair) \ ! 110: {if (to_ptr+5 < to_lim) \ ! 111: {* -- to_lim = ((int**)m)[1]; \ ! 112: * -- to_lim = m+1; \ ! 113: } \ ! 114: else {repair=0; to_lim=to_lim0;} \ ! 115: } \ ! 116: ((int**)m)[1]= 1+(int*)to_ptr;\ ! 117: to_ptr = j;\ ! 118: }\ ! 119: (*m) = tag_forwarded;\ ! 120: /* fall through */\ ! 121: case tag_forwarded: *(int*)(refloc) += ((int*)m)[1] - ((int)(m+1));\ ! 122: break;\ ! 123: case tag_suspension:\ ! 124: {register int **i=(int**)m, **j=to_ptr, len1 = 2;\ ! 125: if (j+len1 > to_lim) do {if (repair) \ ! 126: {repair=0; to_lim=to_lim0;} \ ! 127: else to_lim=gmore();}\ ! 128: while (j+len1 > to_lim);\ ! 129: do {*j++ = *i++;} while (--len1 > 0);\ ! 130: if (repair) \ ! 131: {if (to_ptr+5 < to_lim) \ ! 132: {* -- to_lim = ((int**)m)[1]; \ ! 133: * -- to_lim = m+1; \ ! 134: } \ ! 135: else {repair=0; to_lim=to_lim0;} \ ! 136: } \ ! 137: ((int**)m)[1]= 1+(int*)to_ptr;\ ! 138: to_ptr = j;\ ! 139: }\ ! 140: (*m) = tag_forwarded;\ ! 141: *(int*)(refloc) += ((int*)m)[1] - ((int)(m+1));\ ! 142: break;\ ! 143: default: /* function pointers */\ ! 144: m--; continue;\ ! 145: }\ ! 146: break;\ ! 147: }\ ! 148: }\ ! 149: } ! 150: ! 151: int target; ! 152: ! 153: gc(from_low, /* lowest address in space to be collected from */ ! 154: from_high, /* higher than any ... */ ! 155: to_low, /* lowest address in space to copy into */ ! 156: to_high, /* limit address to copy into */ ! 157: to_done, /* to-space is already copied into up to here */ ! 158: to_where, /* (by-ref) just past highest address copied into */ ! 159: misc_roots, /* vector (0-terminated) of ptrs to possible root words */ ! 160: store_list, /* head of linked list of store-pointers */ ! 161: get_more, /* procedure to call to increase to_lim */ ! 162: first_root /* (optional) address of interesting root to trace; ! 163: if present, then to_done must equal to_low */ ! 164: ) ! 165: int **from_low, **from_high, ***misc_roots, ! 166: **to_low, **to_high, **to_done, ! 167: ***to_where, **store_list; ! 168: int *first_root; ! 169: int ** (*get_more)(); ! 170: { ! 171: any_weak = 0; ! 172: gmore=get_more; ! 173: to_ptr = to_done; ! 174: to_lim0 = to_lim = to_high; ! 175: lowest=from_low; ! 176: highest=from_high; ! 177: ! 178: repair=0; ! 179: if (first_root) ! 180: {register int x; ! 181: int **blast_begin = to_low; ! 182: repair=1; ! 183: xgc(first_root); ! 184: x = (int) to_done; ! 185: while (x<(int)to_ptr) ! 186: {register int p = x+4; ! 187: {register int descr = *(int *)(x); ! 188: if (contains_no_ptrs(descr)) {x += ((get_len(x)+7)&~3); ! 189: continue;} ! 190: x += get_lenz(x) * 4 + 4; ! 191: } ! 192: do{xgc(p); p+=4;} while (p<x); ! 193: } ! 194: blast_write(blast_begin, x, *first_root); ! 195: if (repair) ! 196: {while(to_lim<to_lim0) ! 197: {int *loc = *to_lim++; ! 198: int *old = *to_lim++; ! 199: loc[-1] = ((int*)(loc[0]))[-1]; ! 200: loc[0] = (int)old; ! 201: } ! 202: return 0; ! 203: } ! 204: } ! 205: ! 206: ! 207: /* do the refs */ ! 208: #ifdef GCDEBUG ! 209: chatarg("\nto_ptr at %x... ",to_ptr); ! 210: chatting("beginning refs... "); ! 211: #endif ! 212: {register int **px; ! 213: #ifdef GCDEBUG ! 214: int count=0; ! 215: #endif ! 216: for(px=store_list; ((int)px)!=1; px= (int**) (px[2])) ! 217: {register int **r; ! 218: #ifdef GCDEBUG ! 219: count++; ! 220: #endif ! 221: r = (int**)(px[0])+(((int)(px[1]))>>1); ! 222: if (r>=from_low && r < from_high) continue; ! 223: if (preserving) ! 224: {*to_ptr++ = (int*)(16*3+1); ! 225: *to_ptr++ = px[0]; ! 226: *to_ptr++ = px[1]; ! 227: *to_ptr++ = (int*)store_preserve; ! 228: store_preserve = (int) (to_ptr-3); ! 229: } ! 230: xgc(r); ! 231: } ! 232: #ifdef GCDEBUG ! 233: chatting("(%d refs)\n",count); ! 234: #endif ! 235: } ! 236: ! 237: /* do misc. roots */ ! 238: #ifdef GCDEBUG ! 239: chatarg("to_ptr at %x... ",to_ptr); ! 240: chatting("beginning misc roots\n"); ! 241: #endif ! 242: { register int ***p; ! 243: for(p=misc_roots; *p; p++) xgc(*p); ! 244: } ! 245: ! 246: /* finish the new space */ ! 247: #ifdef GCDEBUG ! 248: chatarg("to_ptr at %x... ",to_ptr); ! 249: chatting("finishing new space\n"); ! 250: #endif ! 251: {register int x = (int)to_low; ! 252: while (x<(int)to_ptr) ! 253: {register int p = x+4; ! 254: {register int descr = *(int *)(x); ! 255: if (contains_no_ptrs(descr)) ! 256: {x += ((get_len(x)+7)&~3); ! 257: continue;} ! 258: x += get_lenz(x) * 4 + 4; ! 259: if (descr == tag_suspension + 2*power_tags) ! 260: {any_weak=1; continue;} ! 261: } ! 262: do{xgc(p); p+=4;} while (p<x); ! 263: } ! 264: } ! 265: #ifdef GCDEBUG ! 266: chatarg("to_ptr at %x... ",to_ptr); ! 267: #endif ! 268: if (any_weak) ! 269: {register int x = (int)to_low; ! 270: #ifdef GCDEBUG ! 271: chatting("doing weak pointers\n"); ! 272: #endif ! 273: while (x<(int)to_ptr) ! 274: {int *p = ((int*)x)+1; ! 275: int descr = *(int *)(x); ! 276: if (contains_no_ptrs(descr)) ! 277: {x += ((get_len(x)+7)&~3); ! 278: continue;} ! 279: x += get_lenz(x) * 4 + 4; ! 280: if (descr == tag_suspension + 2*power_tags) ! 281: {int *m = ((int*)*p)-1; ! 282: if ((!(((int)m)&1)) && m >= (int*)from_low && m <= (int*)from_high) ! 283: for(;;) ! 284: {switch(get_tag(m)) ! 285: {case tag_string: case tag_bytearray: ! 286: case tag_array: case tag_record: ! 287: case tag_suspension: ! 288: *p = 1; ! 289: p[-1]=tag_suspension+3*power_tags; ! 290: break; ! 291: case tag_forwarded: ! 292: *p += m[1] - (int) (m+1); ! 293: break; ! 294: case tag_backptr: m -= get_len(m); ! 295: continue; ! 296: case tag_embedded: ! 297: default: ! 298: m--; ! 299: continue; ! 300: } ! 301: break; ! 302: } ! 303: } ! 304: } ! 305: } ! 306: #ifdef GCDEBUG ! 307: chatarg("to_ptr at %x... ",to_ptr); ! 308: chatting("gc done\n"); ! 309: #endif ! 310: if (target) trace(to_low,target,target+4); ! 311: *to_where = to_ptr; ! 312: return 1; ! 313: } ! 314: ! 315: blockmove(from,to,words) register int * from, *to; register int words; ! 316: { ! 317: if (!words) return; ! 318: if (from<to && from+words >to) ! 319: {from+=words; to+=words; ! 320: do {*--to = *--from;} while (--words > 0); ! 321: } ! 322: else do {*to++ = *from++;} while (--words > 0); ! 323: } ! 324: ! 325: moveback ! 326: (from_low, /* lowest address in space to be collected from */ ! 327: from_high, /* higher than any ... */ ! 328: to_low, /* lowest address in space to copy into */ ! 329: misc_roots /* vector (0-terminated) of ptrs to possible root words */ ! 330: ) ! 331: int *from_low, *from_high, **misc_roots, ! 332: *to_low; ! 333: { register int *x, offset = sizeof(int)*(to_low-from_low); ! 334: ! 335: #define INRANGE(x) (((int)(x) >= (int)from_low) && \ ! 336: ((int)(x) < (int)from_high) ) ! 337: #define ADJUST1(x) (INRANGE(x)?(x)+=offset:0) ! 338: #define ADJUST(x) (is_ptr(x)?ADJUST1(x):0) ! 339: ! 340: /* do misc. roots */ ! 341: #ifdef GCDEBUG ! 342: chatting("misc roots... "); ! 343: #endif ! 344: { register int **p; ! 345: for(p=misc_roots; *p; p++) ADJUST(**p); ! 346: } ! 347: ! 348: /* finish the new space */ ! 349: #ifdef GCDEBUG ! 350: chatting("finishing... "); ! 351: #endif ! 352: x=from_low; ! 353: while (x<from_high) ! 354: if (contains_no_ptrs(*x)) ! 355: x += (get_len(x)+7)>>2; ! 356: else {register int i = get_lenz(x); ! 357: ++x; ! 358: do {ADJUST(*x); x++;} while (--i > 0); ! 359: } ! 360: blockmove(from_low,to_low,from_high-from_low); ! 361: #ifdef GCDEBUG ! 362: chatting("done\n"); ! 363: #endif ! 364: } ! 365: ! 366: relocate(start,end,stuff) ! 367: int start, end; int *stuff; ! 368: ! 369: {int *x=stuff, *done= stuff + (end-start)/4; ! 370: int adjust = ((int)stuff) - start; ! 371: while (x<done) ! 372: if (contains_no_ptrs(*x)) ! 373: x += (get_len(x)+7)>>2; ! 374: else {register int i = get_lenz(x); ! 375: ++x; ! 376: do {if ( (*x & 1) == 0 ! 377: && *x >= start && *x < end) ! 378: *x += adjust; ! 379: x++;} ! 380: while (--i > 0); ! 381: } ! 382: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.