![[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.