Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | /* Copyright (C) 2012,2016 Matthew Fluet. |
2 | * Copyright (C) 1999-2007 Henry Cejtin, Matthew Fluet, Suresh | |
3 | * Jagannathan, and Stephen Weeks. | |
4 | * Copyright (C) 1997-2000 NEC Research Institute. | |
5 | * | |
6 | * MLton is released under a BSD-style license. | |
7 | * See the file MLton-LICENSE for details. | |
8 | */ | |
9 | ||
10 | /* ---------------------------------------------------------------- */ | |
11 | /* Depth-first Marking */ | |
12 | /* ---------------------------------------------------------------- */ | |
13 | ||
14 | bool isPointerMarked (pointer p) { | |
15 | return MARK_MASK & getHeader (p); | |
16 | } | |
17 | ||
18 | bool isPointerMarkedByMode (pointer p, GC_markMode m) { | |
19 | switch (m) { | |
20 | case MARK_MODE: | |
21 | return isPointerMarked (p); | |
22 | case UNMARK_MODE: | |
23 | return not isPointerMarked (p); | |
24 | default: | |
25 | die ("bad mark mode %u", m); | |
26 | } | |
27 | } | |
28 | ||
29 | /* dfsMarkByMode (s, r, m, shc, slw) | |
30 | * | |
31 | * Sets all the mark bits in the object graph pointed to by r. | |
32 | * | |
33 | * If m is MARK_MODE, it sets the bits to 1. | |
34 | * If m is UNMARK_MODE, it sets the bits to 0. | |
35 | * | |
36 | * If shc, it hash-conses the objects marked. | |
37 | * | |
38 | * If slw, it links the weak objects marked. | |
39 | * | |
40 | * It returns the total size in bytes of the objects marked. | |
41 | */ | |
42 | size_t dfsMarkByMode (GC_state s, pointer root, | |
43 | GC_markMode mode, | |
44 | bool shouldHashCons, | |
45 | bool shouldLinkWeaks) { | |
46 | GC_header mark; /* Used to set or clear the mark bit. */ | |
47 | size_t size; /* Total number of bytes marked. */ | |
48 | pointer cur; /* The current object being marked. */ | |
49 | pointer prev; /* The previous object on the mark stack. */ | |
50 | pointer next; /* The next object to mark. */ | |
51 | pointer todo; /* A pointer to the pointer in cur to next. */ | |
52 | GC_header header; | |
53 | GC_header* headerp; | |
54 | uint16_t bytesNonObjptrs; | |
55 | uint16_t numObjptrs; | |
56 | GC_objectTypeTag tag; | |
57 | uint32_t objptrIndex; /* The i'th pointer in the object (element) being marked. */ | |
58 | GC_header nextHeader; | |
59 | GC_header* nextHeaderp; | |
60 | GC_arrayCounter arrayIndex; | |
61 | pointer top; /* The top of the next stack frame to mark. */ | |
62 | GC_returnAddress returnAddress; | |
63 | GC_frameLayout frameLayout; | |
64 | GC_frameOffsets frameOffsets; | |
65 | ||
66 | if (isPointerMarkedByMode (root, mode)) | |
67 | /* Object has already been marked. */ | |
68 | return 0; | |
69 | mark = (MARK_MODE == mode) ? MARK_MASK : 0; | |
70 | size = 0; | |
71 | cur = root; | |
72 | prev = NULL; | |
73 | headerp = getHeaderp (cur); | |
74 | header = *headerp; | |
75 | goto mark; | |
76 | markNext: | |
77 | /* cur is the object that was being marked. | |
78 | * prev is the mark stack. | |
79 | * next is the unmarked object to be marked. | |
80 | * nextHeaderp points to the header of next. | |
81 | * nextHeader is the header of next. | |
82 | * todo is a pointer to the pointer inside cur that points to next. | |
83 | */ | |
84 | if (DEBUG_DFS_MARK) | |
85 | fprintf (stderr, | |
86 | "markNext" | |
87 | " cur = "FMTPTR" next = "FMTPTR | |
88 | " prev = "FMTPTR" todo = "FMTPTR"\n", | |
89 | (uintptr_t)cur, (uintptr_t)next, | |
90 | (uintptr_t)prev, (uintptr_t)todo); | |
91 | assert (not isPointerMarkedByMode (next, mode)); | |
92 | assert (nextHeaderp == getHeaderp (next)); | |
93 | assert (nextHeader == getHeader (next)); | |
94 | // assert (*(pointer*) todo == next); | |
95 | assert (fetchObjptrToPointer (todo, s->heap.start) == next); | |
96 | headerp = nextHeaderp; | |
97 | header = nextHeader; | |
98 | // *(pointer*)todo = prev; | |
99 | storeObjptrFromPointer (todo, prev, s->heap.start); | |
100 | prev = cur; | |
101 | cur = next; | |
102 | mark: | |
103 | if (DEBUG_DFS_MARK) | |
104 | fprintf (stderr, "mark cur = "FMTPTR" prev = "FMTPTR" mode = %s\n", | |
105 | (uintptr_t)cur, (uintptr_t)prev, | |
106 | (mode == MARK_MODE) ? "mark" : "unmark"); | |
107 | /* cur is the object to mark. | |
108 | * prev is the mark stack. | |
109 | * headerp points to the header of cur. | |
110 | * header is the header of cur. | |
111 | */ | |
112 | assert (not isPointerMarkedByMode (cur, mode)); | |
113 | assert (header == getHeader (cur)); | |
114 | assert (headerp == getHeaderp (cur)); | |
115 | header ^= MARK_MASK; | |
116 | /* Store the mark. In the case of an object that contains a pointer to | |
117 | * itself, it is essential that we store the marked header before marking | |
118 | * the internal pointers (markInNormal below). If we didn't, then we | |
119 | * would see the object as unmarked and traverse it again. | |
120 | */ | |
121 | *headerp = header; | |
122 | splitHeader (s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs); | |
123 | if (NORMAL_TAG == tag) { | |
124 | size += | |
125 | GC_NORMAL_METADATA_SIZE | |
126 | + bytesNonObjptrs | |
127 | + (numObjptrs * OBJPTR_SIZE); | |
128 | if (0 == numObjptrs) { | |
129 | /* There is nothing to mark. */ | |
130 | normalDone: | |
131 | if (shouldHashCons) | |
132 | cur = hashConsPointer (s, cur, TRUE); | |
133 | goto ret; | |
134 | } | |
135 | todo = cur + bytesNonObjptrs; | |
136 | objptrIndex = 0; | |
137 | markInNormal: | |
138 | if (DEBUG_DFS_MARK) | |
139 | fprintf (stderr, "markInNormal objptrIndex = %"PRIu32"\n", objptrIndex); | |
140 | assert (objptrIndex < numObjptrs); | |
141 | // next = *(pointer*)todo; | |
142 | next = fetchObjptrToPointer (todo, s->heap.start); | |
143 | if (not isPointer (next)) { | |
144 | markNextInNormal: | |
145 | assert (objptrIndex < numObjptrs); | |
146 | objptrIndex++; | |
147 | if (objptrIndex == numObjptrs) { | |
148 | /* Done. Clear out the counters and return. */ | |
149 | *headerp = header & ~COUNTER_MASK; | |
150 | goto normalDone; | |
151 | } | |
152 | todo += OBJPTR_SIZE; | |
153 | goto markInNormal; | |
154 | } | |
155 | nextHeaderp = getHeaderp (next); | |
156 | nextHeader = *nextHeaderp; | |
157 | if (mark == (nextHeader & MARK_MASK)) { | |
158 | if (shouldHashCons) | |
159 | shareObjptr (s, (objptr*)todo); | |
160 | goto markNextInNormal; | |
161 | } | |
162 | *headerp = (header & ~COUNTER_MASK) | (objptrIndex << COUNTER_SHIFT); | |
163 | goto markNext; | |
164 | } else if (WEAK_TAG == tag) { | |
165 | /* Store the marked header and don't follow any pointers. */ | |
166 | if (shouldLinkWeaks) { | |
167 | GC_weak w; | |
168 | ||
169 | w = (GC_weak)(cur + offsetofWeak (s)); | |
170 | if (DEBUG_WEAK) | |
171 | fprintf (stderr, "marking weak "FMTPTR" ", | |
172 | (uintptr_t)w); | |
173 | if (isObjptr (w->objptr)) { | |
174 | if (DEBUG_WEAK) | |
175 | fprintf (stderr, "linking\n"); | |
176 | w->link = s->weaks; | |
177 | s->weaks = w; | |
178 | } else { | |
179 | if (DEBUG_WEAK) | |
180 | fprintf (stderr, "not linking\n"); | |
181 | } | |
182 | } | |
183 | goto ret; | |
184 | } else if (ARRAY_TAG == tag) { | |
185 | /* When marking arrays: | |
186 | * arrayIndex is the index of the element to mark. | |
187 | * cur is the pointer to the array. | |
188 | * objptrIndex is the index of the pointer within the element | |
189 | * (i.e. the i'th pointer is at index i). | |
190 | * todo is the start of the element. | |
191 | */ | |
192 | size += | |
193 | GC_ARRAY_METADATA_SIZE | |
194 | + sizeofArrayNoMetaData (s, getArrayLength (cur), bytesNonObjptrs, numObjptrs); | |
195 | if (0 == numObjptrs or 0 == getArrayLength (cur)) { | |
196 | /* There is nothing to mark. */ | |
197 | arrayDone: | |
198 | if (shouldHashCons) | |
199 | cur = hashConsPointer (s, cur, TRUE); | |
200 | goto ret; | |
201 | } | |
202 | /* Begin marking first element. */ | |
203 | arrayIndex = 0; | |
204 | todo = cur; | |
205 | markArrayElt: | |
206 | assert (arrayIndex < getArrayLength (cur)); | |
207 | objptrIndex = 0; | |
208 | /* Skip to the first pointer. */ | |
209 | todo += bytesNonObjptrs; | |
210 | markInArray: | |
211 | if (DEBUG_DFS_MARK) | |
212 | fprintf (stderr, "markInArray arrayIndex = %"PRIxARRCTR" objptrIndex = %"PRIu32"\n", | |
213 | arrayIndex, objptrIndex); | |
214 | assert (arrayIndex < getArrayLength (cur)); | |
215 | assert (objptrIndex < numObjptrs); | |
216 | assert (todo == indexArrayAtObjptrIndex (s, cur, arrayIndex, objptrIndex)); | |
217 | // next = *(pointer*)todo; | |
218 | next = fetchObjptrToPointer (todo, s->heap.start); | |
219 | if (not (isPointer(next))) { | |
220 | markNextInArray: | |
221 | assert (arrayIndex < getArrayLength (cur)); | |
222 | assert (objptrIndex < numObjptrs); | |
223 | assert (todo == indexArrayAtObjptrIndex (s, cur, arrayIndex, objptrIndex)); | |
224 | todo += OBJPTR_SIZE; | |
225 | objptrIndex++; | |
226 | if (objptrIndex < numObjptrs) | |
227 | goto markInArray; | |
228 | arrayIndex++; | |
229 | if (arrayIndex < getArrayLength (cur)) | |
230 | goto markArrayElt; | |
231 | /* Done. Clear out the counters and return. */ | |
232 | *getArrayCounterp (cur) = 0; | |
233 | *headerp = header & ~COUNTER_MASK; | |
234 | goto arrayDone; | |
235 | } | |
236 | nextHeaderp = getHeaderp (next); | |
237 | nextHeader = *nextHeaderp; | |
238 | if (mark == (nextHeader & MARK_MASK)) { | |
239 | if (shouldHashCons) | |
240 | shareObjptr (s, (objptr*)todo); | |
241 | goto markNextInArray; | |
242 | } | |
243 | /* Recur and mark next. */ | |
244 | *getArrayCounterp (cur) = arrayIndex; | |
245 | *headerp = (header & ~COUNTER_MASK) | (objptrIndex << COUNTER_SHIFT); | |
246 | goto markNext; | |
247 | } else { | |
248 | assert (STACK_TAG == tag); | |
249 | size += | |
250 | GC_STACK_METADATA_SIZE | |
251 | + sizeof (struct GC_stack) + ((GC_stack)cur)->reserved; | |
252 | top = getStackTop (s, (GC_stack)cur); | |
253 | assert (((GC_stack)cur)->used <= ((GC_stack)cur)->reserved); | |
254 | markInStack: | |
255 | /* Invariant: top points just past the return address of the frame | |
256 | * to be marked. | |
257 | */ | |
258 | assert (getStackBottom (s, (GC_stack)cur) <= top); | |
259 | if (DEBUG_DFS_MARK) | |
260 | fprintf (stderr, "markInStack top = %"PRIuMAX"\n", | |
261 | (uintmax_t)(top - getStackBottom (s, (GC_stack)cur))); | |
262 | if (top == getStackBottom (s, (GC_stack)(cur))) | |
263 | goto ret; | |
264 | objptrIndex = 0; | |
265 | returnAddress = *(GC_returnAddress*) (top - GC_RETURNADDRESS_SIZE); | |
266 | frameLayout = getFrameLayoutFromReturnAddress (s, returnAddress); | |
267 | frameOffsets = frameLayout->offsets; | |
268 | ((GC_stack)cur)->markTop = top; | |
269 | markInFrame: | |
270 | if (objptrIndex == frameOffsets [0]) { | |
271 | top -= frameLayout->size; | |
272 | goto markInStack; | |
273 | } | |
274 | todo = top - frameLayout->size + frameOffsets [objptrIndex + 1]; | |
275 | // next = *(pointer*)todo; | |
276 | next = fetchObjptrToPointer (todo, s->heap.start); | |
277 | if (DEBUG_DFS_MARK) | |
278 | fprintf (stderr, | |
279 | " offset %u todo "FMTPTR" next = "FMTPTR"\n", | |
280 | frameOffsets [objptrIndex + 1], | |
281 | (uintptr_t)todo, (uintptr_t)next); | |
282 | if (not isPointer (next)) { | |
283 | objptrIndex++; | |
284 | goto markInFrame; | |
285 | } | |
286 | nextHeaderp = getHeaderp (next); | |
287 | nextHeader = *nextHeaderp; | |
288 | if (mark == (nextHeader & MARK_MASK)) { | |
289 | objptrIndex++; | |
290 | if (shouldHashCons) | |
291 | shareObjptr (s, (objptr*)todo); | |
292 | goto markInFrame; | |
293 | } | |
294 | ((GC_stack)cur)->markIndex = objptrIndex; | |
295 | goto markNext; | |
296 | } | |
297 | assert (FALSE); | |
298 | ret: | |
299 | /* Done marking cur, continue with prev. | |
300 | * Need to set the pointer in the prev object that pointed to cur | |
301 | * to point back to prev, and restore prev. | |
302 | */ | |
303 | if (DEBUG_DFS_MARK) | |
304 | fprintf (stderr, "return cur = "FMTPTR" prev = "FMTPTR"\n", | |
305 | (uintptr_t)cur, (uintptr_t)prev); | |
306 | assert (isPointerMarkedByMode (cur, mode)); | |
307 | if (NULL == prev) | |
308 | return size; | |
309 | next = cur; | |
310 | cur = prev; | |
311 | headerp = getHeaderp (cur); | |
312 | header = *headerp; | |
313 | splitHeader (s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs); | |
314 | /* It's impossible to get a WEAK_TAG here, since we would never | |
315 | * follow the weak object pointer. | |
316 | */ | |
317 | assert (WEAK_TAG != tag); | |
318 | if (NORMAL_TAG == tag) { | |
319 | todo = cur + bytesNonObjptrs; | |
320 | objptrIndex = (header & COUNTER_MASK) >> COUNTER_SHIFT; | |
321 | todo += objptrIndex * OBJPTR_SIZE; | |
322 | // prev = *(pointer*)todo; | |
323 | prev = fetchObjptrToPointer (todo, s->heap.start); | |
324 | // *(pointer*)todo = next; | |
325 | storeObjptrFromPointer (todo, next, s->heap.start); | |
326 | if (shouldHashCons) | |
327 | markIntergenerationalPointer (s, (pointer*)todo); | |
328 | goto markNextInNormal; | |
329 | } else if (ARRAY_TAG == tag) { | |
330 | arrayIndex = getArrayCounter (cur); | |
331 | todo = cur + arrayIndex * (bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE)); | |
332 | objptrIndex = (header & COUNTER_MASK) >> COUNTER_SHIFT; | |
333 | todo += bytesNonObjptrs + objptrIndex * OBJPTR_SIZE; | |
334 | // prev = *(pointer*)todo; | |
335 | prev = fetchObjptrToPointer (todo, s->heap.start); | |
336 | // *(pointer*)todo = next; | |
337 | storeObjptrFromPointer (todo, next, s->heap.start); | |
338 | if (shouldHashCons) | |
339 | markIntergenerationalPointer (s, (pointer*)todo); | |
340 | goto markNextInArray; | |
341 | } else { | |
342 | assert (STACK_TAG == tag); | |
343 | objptrIndex = ((GC_stack)cur)->markIndex; | |
344 | top = ((GC_stack)cur)->markTop; | |
345 | /* Invariant: top points just past a "return address". */ | |
346 | returnAddress = *(GC_returnAddress*) (top - GC_RETURNADDRESS_SIZE); | |
347 | frameLayout = getFrameLayoutFromReturnAddress (s, returnAddress); | |
348 | frameOffsets = frameLayout->offsets; | |
349 | todo = top - frameLayout->size + frameOffsets [objptrIndex + 1]; | |
350 | // prev = *(pointer*)todo; | |
351 | prev = fetchObjptrToPointer (todo, s->heap.start); | |
352 | // *(pointer*)todo = next; | |
353 | storeObjptrFromPointer (todo, next, s->heap.start); | |
354 | if (shouldHashCons) | |
355 | markIntergenerationalPointer (s, (pointer*)todo); | |
356 | objptrIndex++; | |
357 | goto markInFrame; | |
358 | } | |
359 | assert (FALSE); | |
360 | } | |
361 | ||
362 | void dfsMarkWithHashConsWithLinkWeaks (GC_state s, objptr *opp) { | |
363 | pointer p; | |
364 | ||
365 | p = objptrToPointer (*opp, s->heap.start); | |
366 | dfsMarkByMode (s, p, MARK_MODE, TRUE, TRUE); | |
367 | } | |
368 | ||
369 | void dfsMarkWithoutHashConsWithLinkWeaks (GC_state s, objptr *opp) { | |
370 | pointer p; | |
371 | ||
372 | p = objptrToPointer (*opp, s->heap.start); | |
373 | dfsMarkByMode (s, p, MARK_MODE, FALSE, TRUE); | |
374 | } |