Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | /* Copyright (C) 2010,2012,2016 Matthew Fluet. |
2 | * Copyright (C) 1999-2008 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 | /* Jonkers Mark-compact Collection */ | |
12 | /* ---------------------------------------------------------------- */ | |
13 | ||
14 | void copyForThreadInternal (pointer dst, pointer src) { | |
15 | if (FALSE) | |
16 | fprintf (stderr, | |
17 | "copyForThreadInternal dst = "FMTPTR" src = "FMTPTR"\n", | |
18 | (uintptr_t)dst, (uintptr_t)src); | |
19 | if (OBJPTR_SIZE > GC_HEADER_SIZE) { | |
20 | size_t count; | |
21 | ||
22 | assert (0 == (OBJPTR_SIZE % GC_HEADER_SIZE)); | |
23 | count = (OBJPTR_SIZE - GC_HEADER_SIZE) / GC_HEADER_SIZE; | |
24 | src = src + GC_HEADER_SIZE * count; | |
25 | ||
26 | for (size_t i = 0; i <= count; i++) { | |
27 | *((GC_header*)dst) = *((GC_header*)src); | |
28 | dst += GC_HEADER_SIZE; | |
29 | src -= GC_HEADER_SIZE; | |
30 | } | |
31 | } else if (GC_HEADER_SIZE > OBJPTR_SIZE) { | |
32 | size_t count; | |
33 | ||
34 | assert (0 == (GC_HEADER_SIZE % OBJPTR_SIZE)); | |
35 | count = (GC_HEADER_SIZE - OBJPTR_SIZE) / OBJPTR_SIZE; | |
36 | dst = dst + OBJPTR_SIZE * count; | |
37 | ||
38 | for (size_t i = 0; i <= count; i++) { | |
39 | *((objptr*)dst) = *((objptr*)src); | |
40 | dst -= OBJPTR_SIZE; | |
41 | src += OBJPTR_SIZE; | |
42 | } | |
43 | } else /* (GC_HEADER_SIZE == OBJPTR_SIZE) */ { | |
44 | *((GC_header*)dst) = *((GC_header*)src); | |
45 | } | |
46 | } | |
47 | ||
48 | void threadInternalObjptr (GC_state s, objptr *opp) { | |
49 | objptr opop; | |
50 | pointer p; | |
51 | GC_header *headerp; | |
52 | ||
53 | opop = pointerToObjptr ((pointer)opp, s->heap.start); | |
54 | p = objptrToPointer (*opp, s->heap.start); | |
55 | if (FALSE) | |
56 | fprintf (stderr, | |
57 | "threadInternal opp = "FMTPTR" p = "FMTPTR" header = "FMTHDR"\n", | |
58 | (uintptr_t)opp, (uintptr_t)p, getHeader (p)); | |
59 | headerp = getHeaderp (p); | |
60 | copyForThreadInternal ((pointer)(opp), (pointer)(headerp)); | |
61 | copyForThreadInternal ((pointer)(headerp), (pointer)(&opop)); | |
62 | } | |
63 | ||
64 | /* If the object pointer is valid, and points to an unmarked object, | |
65 | * then clear the object pointer. | |
66 | */ | |
67 | void updateWeaksForMarkCompact (GC_state s) { | |
68 | pointer p; | |
69 | GC_weak w; | |
70 | ||
71 | for (w = s->weaks; w != NULL; w = w->link) { | |
72 | assert (BOGUS_OBJPTR != w->objptr); | |
73 | ||
74 | if (DEBUG_WEAK) | |
75 | fprintf (stderr, "updateWeaksForMarkCompact w = "FMTPTR" ", (uintptr_t)w); | |
76 | p = objptrToPointer(w->objptr, s->heap.start); | |
77 | /* If it's unmarked, clear the weak pointer. */ | |
78 | if (isPointerMarked(p)) { | |
79 | if (DEBUG_WEAK) | |
80 | fprintf (stderr, "not cleared\n"); | |
81 | } else { | |
82 | if (DEBUG_WEAK) | |
83 | fprintf (stderr, "cleared\n"); | |
84 | *(getHeaderp((pointer)w - offsetofWeak (s))) = GC_WEAK_GONE_HEADER | MARK_MASK; | |
85 | w->objptr = BOGUS_OBJPTR; | |
86 | } | |
87 | } | |
88 | s->weaks = NULL; | |
89 | } | |
90 | ||
91 | void updateForwardPointersForMarkCompact (GC_state s, GC_stack currentStack) { | |
92 | pointer back; | |
93 | pointer endOfLastMarked; | |
94 | pointer front; | |
95 | size_t gap; | |
96 | GC_header header; | |
97 | GC_header *headerp; | |
98 | pointer p; | |
99 | size_t size, skipFront, skipGap; | |
100 | ||
101 | if (DEBUG_MARK_COMPACT) | |
102 | fprintf (stderr, "Update forward pointers.\n"); | |
103 | front = alignFrontier (s, s->heap.start); | |
104 | back = s->heap.start + s->heap.oldGenSize; | |
105 | gap = 0; | |
106 | endOfLastMarked = front; | |
107 | updateObject: | |
108 | if (DEBUG_MARK_COMPACT) | |
109 | fprintf (stderr, "updateObject front = "FMTPTR" back = "FMTPTR"\n", | |
110 | (uintptr_t)front, (uintptr_t)back); | |
111 | if (front == back) | |
112 | goto done; | |
113 | p = advanceToObjectData (s, front); | |
114 | headerp = getHeaderp (p); | |
115 | header = *headerp; | |
116 | if (GC_VALID_HEADER_MASK & header) { | |
117 | /* It's a header */ | |
118 | if (MARK_MASK & header) { | |
119 | /* It is marked, but has no forward pointers. | |
120 | * Thread internal pointers. | |
121 | */ | |
122 | thread: | |
123 | assert (GC_VALID_HEADER_MASK & header); | |
124 | assert (MARK_MASK & header); | |
125 | ||
126 | size_t metaDataBytes, objectBytes; | |
127 | GC_objectTypeTag tag; | |
128 | uint16_t bytesNonObjptrs, numObjptrs; | |
129 | ||
130 | assert (header == getHeader (p)); | |
131 | splitHeader(s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs); | |
132 | ||
133 | /* Compute the space taken by the header and object body. */ | |
134 | if ((NORMAL_TAG == tag) or (WEAK_TAG == tag)) { /* Fixed size object. */ | |
135 | metaDataBytes = GC_NORMAL_METADATA_SIZE; | |
136 | objectBytes = bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE); | |
137 | skipFront = 0; | |
138 | skipGap = 0; | |
139 | } else if (ARRAY_TAG == tag) { | |
140 | metaDataBytes = GC_ARRAY_METADATA_SIZE; | |
141 | objectBytes = sizeofArrayNoMetaData (s, getArrayLength (p), | |
142 | bytesNonObjptrs, numObjptrs); | |
143 | skipFront = 0; | |
144 | skipGap = 0; | |
145 | } else { /* Stack. */ | |
146 | bool current; | |
147 | size_t reservedNew, reservedOld; | |
148 | GC_stack stack; | |
149 | ||
150 | assert (STACK_TAG == tag); | |
151 | metaDataBytes = GC_STACK_METADATA_SIZE; | |
152 | stack = (GC_stack)p; | |
153 | current = currentStack == stack; | |
154 | ||
155 | reservedOld = stack->reserved; | |
156 | reservedNew = sizeofStackShrinkReserved (s, stack, current); | |
157 | objectBytes = sizeof (struct GC_stack) + stack->used; | |
158 | skipFront = reservedOld - stack->used; | |
159 | skipGap = reservedOld - reservedNew; | |
160 | } | |
161 | size = metaDataBytes + objectBytes; | |
162 | if (DEBUG_MARK_COMPACT) | |
163 | fprintf (stderr, "threading "FMTPTR" of size %"PRIuMAX"\n", | |
164 | (uintptr_t)p, (uintmax_t)size); | |
165 | if ((size_t)(front - endOfLastMarked) >= GC_ARRAY_METADATA_SIZE) { | |
166 | pointer newArray = endOfLastMarked; | |
167 | /* Compress all of the unmarked into one vector. We require | |
168 | * GC_ARRAY_METADATA_SIZE space to be available because that is | |
169 | * the smallest possible array. | |
170 | */ | |
171 | if (DEBUG_MARK_COMPACT) | |
172 | fprintf (stderr, "compressing from "FMTPTR" to "FMTPTR" (length = %"PRIuMAX")\n", | |
173 | (uintptr_t)endOfLastMarked, (uintptr_t)front, | |
174 | (uintmax_t)(front - endOfLastMarked)); | |
175 | *((GC_arrayCounter*)(newArray)) = 0; | |
176 | newArray += GC_ARRAY_COUNTER_SIZE; | |
177 | *((GC_arrayLength*)(newArray)) = | |
178 | ((size_t)(front - endOfLastMarked)) - GC_ARRAY_METADATA_SIZE; | |
179 | newArray += GC_ARRAY_LENGTH_SIZE; | |
180 | *((GC_header*)(newArray)) = GC_WORD8_VECTOR_HEADER; | |
181 | } | |
182 | gap += skipGap; | |
183 | front += size + skipFront; | |
184 | endOfLastMarked = front; | |
185 | foreachObjptrInObject (s, p, threadInternalObjptr, FALSE); | |
186 | goto updateObject; | |
187 | } else { | |
188 | /* It's not marked. */ | |
189 | size = sizeofObject (s, p); | |
190 | gap += size; | |
191 | front += size; | |
192 | goto updateObject; | |
193 | } | |
194 | } else { | |
195 | pointer new; | |
196 | objptr newObjptr; | |
197 | ||
198 | assert (not (GC_VALID_HEADER_MASK & header)); | |
199 | /* It's a pointer. This object must be live. Fix all the forward | |
200 | * pointers to it, store its header, then thread its internal | |
201 | * pointers. | |
202 | */ | |
203 | new = p - gap; | |
204 | newObjptr = pointerToObjptr (new, s->heap.start); | |
205 | do { | |
206 | pointer cur; | |
207 | objptr curObjptr; | |
208 | ||
209 | copyForThreadInternal ((pointer)(&curObjptr), (pointer)headerp); | |
210 | cur = objptrToPointer (curObjptr, s->heap.start); | |
211 | ||
212 | copyForThreadInternal ((pointer)headerp, cur); | |
213 | *((objptr*)cur) = newObjptr; | |
214 | ||
215 | header = *headerp; | |
216 | } while (0 == (1 & header)); | |
217 | goto thread; | |
218 | } | |
219 | assert (FALSE); | |
220 | done: | |
221 | return; | |
222 | } | |
223 | ||
224 | void updateBackwardPointersAndSlideForMarkCompact (GC_state s, GC_stack currentStack) { | |
225 | pointer back; | |
226 | pointer front; | |
227 | size_t gap; | |
228 | GC_header header; | |
229 | GC_header *headerp; | |
230 | pointer p; | |
231 | size_t size, skipFront, skipGap; | |
232 | ||
233 | if (DEBUG_MARK_COMPACT) | |
234 | fprintf (stderr, "Update backward pointers and slide.\n"); | |
235 | front = alignFrontier (s, s->heap.start); | |
236 | back = s->heap.start + s->heap.oldGenSize; | |
237 | gap = 0; | |
238 | updateObject: | |
239 | if (DEBUG_MARK_COMPACT) | |
240 | fprintf (stderr, "updateObject front = "FMTPTR" back = "FMTPTR"\n", | |
241 | (uintptr_t)front, (uintptr_t)back); | |
242 | if (front == back) | |
243 | goto done; | |
244 | p = advanceToObjectData (s, front); | |
245 | headerp = getHeaderp (p); | |
246 | header = *headerp; | |
247 | if (GC_VALID_HEADER_MASK & header) { | |
248 | /* It's a header */ | |
249 | if (MARK_MASK & header) { | |
250 | /* It is marked, but has no backward pointers to it. | |
251 | * Unmark it. | |
252 | */ | |
253 | unmark: | |
254 | assert (GC_VALID_HEADER_MASK & header); | |
255 | assert (MARK_MASK & header); | |
256 | ||
257 | size_t metaDataBytes, objectBytes; | |
258 | GC_objectTypeTag tag; | |
259 | uint16_t bytesNonObjptrs, numObjptrs; | |
260 | ||
261 | assert (header == getHeader (p)); | |
262 | splitHeader(s, header, &tag, NULL, &bytesNonObjptrs, &numObjptrs); | |
263 | ||
264 | /* Compute the space taken by the header and object body. */ | |
265 | if ((NORMAL_TAG == tag) or (WEAK_TAG == tag)) { /* Fixed size object. */ | |
266 | metaDataBytes = GC_NORMAL_METADATA_SIZE; | |
267 | objectBytes = bytesNonObjptrs + (numObjptrs * OBJPTR_SIZE); | |
268 | skipFront = 0; | |
269 | skipGap = 0; | |
270 | } else if (ARRAY_TAG == tag) { | |
271 | metaDataBytes = GC_ARRAY_METADATA_SIZE; | |
272 | objectBytes = sizeofArrayNoMetaData (s, getArrayLength (p), | |
273 | bytesNonObjptrs, numObjptrs); | |
274 | skipFront = 0; | |
275 | skipGap = 0; | |
276 | } else { /* Stack. */ | |
277 | bool current; | |
278 | size_t reservedNew, reservedOld; | |
279 | GC_stack stack; | |
280 | ||
281 | assert (STACK_TAG == tag); | |
282 | metaDataBytes = GC_STACK_METADATA_SIZE; | |
283 | stack = (GC_stack)p; | |
284 | current = currentStack == stack; | |
285 | ||
286 | reservedOld = stack->reserved; | |
287 | reservedNew = sizeofStackShrinkReserved (s, stack, current); | |
288 | if (reservedNew < stack->reserved) { | |
289 | if (DEBUG_STACKS or s->controls.messages) | |
290 | fprintf (stderr, | |
291 | "[GC: Shrinking stack of size %s bytes to size %s bytes, using %s bytes.]\n", | |
292 | uintmaxToCommaString(stack->reserved), | |
293 | uintmaxToCommaString(reservedNew), | |
294 | uintmaxToCommaString(stack->used)); | |
295 | stack->reserved = reservedNew; | |
296 | } | |
297 | objectBytes = sizeof (struct GC_stack) + stack->used; | |
298 | skipFront = reservedOld - stack->used; | |
299 | skipGap = reservedOld - reservedNew; | |
300 | } | |
301 | size = metaDataBytes + objectBytes; | |
302 | /* unmark */ | |
303 | if (DEBUG_MARK_COMPACT) | |
304 | fprintf (stderr, "unmarking "FMTPTR" of size %"PRIuMAX"\n", | |
305 | (uintptr_t)p, (uintmax_t)size); | |
306 | *headerp = header & ~MARK_MASK; | |
307 | /* slide */ | |
308 | if (DEBUG_MARK_COMPACT) | |
309 | fprintf (stderr, "sliding "FMTPTR" down %"PRIuMAX" to "FMTPTR"\n", | |
310 | (uintptr_t)front, (uintmax_t)gap, (uintptr_t)(front - gap)); | |
311 | GC_memmove (front, front - gap, size); | |
312 | gap += skipGap; | |
313 | front += size + skipFront; | |
314 | goto updateObject; | |
315 | } else { | |
316 | /* It's not marked. */ | |
317 | size = sizeofObject (s, p); | |
318 | if (DEBUG_MARK_COMPACT) | |
319 | fprintf (stderr, "skipping "FMTPTR" of size %"PRIuMAX"\n", | |
320 | (uintptr_t)p, (uintmax_t)size); | |
321 | gap += size; | |
322 | front += size; | |
323 | goto updateObject; | |
324 | } | |
325 | } else { | |
326 | pointer new; | |
327 | objptr newObjptr; | |
328 | ||
329 | assert (not (GC_VALID_HEADER_MASK & header)); | |
330 | /* It's a pointer. This object must be live. Fix all the | |
331 | * backward pointers to it. Then unmark it. | |
332 | */ | |
333 | new = p - gap; | |
334 | newObjptr = pointerToObjptr (new, s->heap.start); | |
335 | do { | |
336 | pointer cur; | |
337 | objptr curObjptr; | |
338 | ||
339 | copyForThreadInternal ((pointer)(&curObjptr), (pointer)headerp); | |
340 | cur = objptrToPointer (curObjptr, s->heap.start); | |
341 | ||
342 | copyForThreadInternal ((pointer)headerp, cur); | |
343 | *((objptr*)cur) = newObjptr; | |
344 | ||
345 | header = *headerp; | |
346 | } while (0 == (1 & header)); | |
347 | /* The unmarked header will be stored by unmark. */ | |
348 | goto unmark; | |
349 | } | |
350 | assert (FALSE); | |
351 | done: | |
352 | s->heap.oldGenSize = (size_t)((front - gap) - s->heap.start); | |
353 | if (DEBUG_MARK_COMPACT) | |
354 | fprintf (stderr, "oldGenSize = %"PRIuMAX"\n", | |
355 | (uintmax_t)s->heap.oldGenSize); | |
356 | return; | |
357 | } | |
358 | ||
359 | void majorMarkCompactGC (GC_state s) { | |
360 | size_t bytesHashConsed; | |
361 | size_t bytesMarkCompacted; | |
362 | GC_stack currentStack; | |
363 | struct rusage ru_start; | |
364 | ||
365 | if (detailedGCTime (s)) | |
366 | startTiming (&ru_start); | |
367 | s->cumulativeStatistics.numMarkCompactGCs++; | |
368 | if (DEBUG or s->controls.messages) { | |
369 | fprintf (stderr, | |
370 | "[GC: Starting major mark-compact;]\n"); | |
371 | fprintf (stderr, | |
372 | "[GC:\theap at "FMTPTR" of size %s bytes.]\n", | |
373 | (uintptr_t)(s->heap.start), | |
374 | uintmaxToCommaString(s->heap.size)); | |
375 | } | |
376 | currentStack = getStackCurrent (s); | |
377 | if (s->hashConsDuringGC) { | |
378 | s->lastMajorStatistics.bytesHashConsed = 0; | |
379 | s->cumulativeStatistics.numHashConsGCs++; | |
380 | s->objectHashTable = allocHashTable (s); | |
381 | foreachGlobalObjptr (s, dfsMarkWithHashConsWithLinkWeaks); | |
382 | freeHashTable (s->objectHashTable); | |
383 | } else { | |
384 | foreachGlobalObjptr (s, dfsMarkWithoutHashConsWithLinkWeaks); | |
385 | } | |
386 | updateWeaksForMarkCompact (s); | |
387 | foreachGlobalObjptr (s, threadInternalObjptr); | |
388 | updateForwardPointersForMarkCompact (s, currentStack); | |
389 | updateBackwardPointersAndSlideForMarkCompact (s, currentStack); | |
390 | bytesHashConsed = s->lastMajorStatistics.bytesHashConsed; | |
391 | s->cumulativeStatistics.bytesHashConsed += bytesHashConsed; | |
392 | bytesMarkCompacted = s->heap.oldGenSize; | |
393 | s->cumulativeStatistics.bytesMarkCompacted += bytesMarkCompacted; | |
394 | s->lastMajorStatistics.kind = GC_MARK_COMPACT; | |
395 | if (detailedGCTime (s)) | |
396 | stopTiming (&ru_start, &s->cumulativeStatistics.ru_gcMarkCompact); | |
397 | if (DEBUG or s->controls.messages) { | |
398 | fprintf (stderr, | |
399 | "[GC: Finished major mark-compact; mark compacted %s bytes.]\n", | |
400 | uintmaxToCommaString(bytesMarkCompacted)); | |
401 | if (s->hashConsDuringGC) | |
402 | printBytesHashConsedMessage(bytesHashConsed, | |
403 | bytesHashConsed + bytesMarkCompacted); | |
404 | } | |
405 | } |