Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | /* Copyright (C) 2009,2012 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 | void displayGenerationalMaps (__attribute__ ((unused)) GC_state s, | |
11 | struct GC_generationalMaps *generational, | |
12 | FILE *stream) { | |
13 | fprintf(stream, | |
14 | "\t\tcardMap = "FMTPTR"\n" | |
15 | "\t\tcardMapAbsolute = "FMTPTR"\n" | |
16 | "\t\tcardMapLength = %"PRIuMAX"\n" | |
17 | "\t\tcrossMap = "FMTPTR"\n" | |
18 | "\t\tcrossMapLength = %"PRIuMAX"\n" | |
19 | "\t\tcrossMapValidSize = %"PRIuMAX"\n", | |
20 | (uintptr_t)generational->cardMap, | |
21 | (uintptr_t)generational->cardMapAbsolute, | |
22 | (uintmax_t)generational->cardMapLength, | |
23 | (uintptr_t)generational->crossMap, | |
24 | (uintmax_t)generational->crossMapLength, | |
25 | (uintmax_t)generational->crossMapValidSize); | |
26 | if (DEBUG_GENERATIONAL and DEBUG_DETAILED) { | |
27 | GC_crossMapIndex i; | |
28 | ||
29 | fprintf (stderr, "crossMap trues\n"); | |
30 | for (i = 0; i < generational->crossMapLength; i++) | |
31 | unless (CROSS_MAP_EMPTY == generational->crossMap[i]) | |
32 | fprintf (stderr, "\t%"PRIuMAX" "FMTCME" %"PRIuMAX"\n", | |
33 | (uintmax_t)i, generational->crossMap[i], | |
34 | (uintmax_t)(CROSS_MAP_OFFSET_SCALE * generational->crossMap[i])); | |
35 | fprintf (stderr, "\n"); | |
36 | } | |
37 | } | |
38 | ||
39 | GC_cardMapIndex sizeToCardMapIndex (size_t z) { | |
40 | return (GC_cardMapIndex)z >> CARD_SIZE_LOG2; | |
41 | } | |
42 | size_t cardMapIndexToSize (GC_cardMapIndex i) { | |
43 | return (size_t)i << CARD_SIZE_LOG2; | |
44 | } | |
45 | GC_cardMapIndex pointerToCardMapIndexAbsolute (pointer p) { | |
46 | return (GC_cardMapIndex)p >> CARD_SIZE_LOG2; | |
47 | } | |
48 | GC_cardMapElem *pointerToCardMapAddr (GC_state s, pointer p) { | |
49 | GC_cardMapElem *res; | |
50 | ||
51 | res = &s->generationalMaps.cardMapAbsolute[pointerToCardMapIndexAbsolute (p)]; | |
52 | if (DEBUG_CARD_MARKING) | |
53 | fprintf (stderr, "pointerToCardMapAddr ("FMTPTR") = "FMTPTR"\n", | |
54 | (uintptr_t)p, (uintptr_t)res); | |
55 | return res; | |
56 | } | |
57 | ||
58 | GC_crossMapIndex sizeToCrossMapIndex (size_t z) { | |
59 | return (GC_crossMapIndex)z >> CARD_SIZE_LOG2; | |
60 | } | |
61 | ||
62 | #if ASSERT | |
63 | bool isCardMarked (GC_state s, pointer p) { | |
64 | return (*pointerToCardMapAddr (s, p) != 0x0); | |
65 | } | |
66 | #endif | |
67 | ||
68 | void markCard (GC_state s, pointer p) { | |
69 | if (DEBUG_CARD_MARKING) | |
70 | fprintf (stderr, "markCard ("FMTPTR")\n", (uintptr_t)p); | |
71 | if (s->mutatorMarksCards) | |
72 | *(pointerToCardMapAddr (s, p)) = 0x1; | |
73 | } | |
74 | ||
75 | void markIntergenerationalPointer (GC_state s, pointer *pp) { | |
76 | if (s->mutatorMarksCards | |
77 | and isPointerInOldGen (s, (pointer)pp) | |
78 | and isPointerInNursery (s, *pp)) | |
79 | markCard (s, (pointer)pp); | |
80 | } | |
81 | ||
82 | void markIntergenerationalObjptr (GC_state s, objptr *opp) { | |
83 | if (s->mutatorMarksCards | |
84 | and isPointerInOldGen (s, (pointer)opp) | |
85 | and isObjptrInNursery (s, *opp)) | |
86 | markCard (s, (pointer)opp); | |
87 | } | |
88 | ||
89 | void setCardMapAbsolute (GC_state s) { | |
90 | unless (s->mutatorMarksCards) | |
91 | return; | |
92 | /* It's OK if the subtraction below underflows because all the | |
93 | * subsequent additions to mark the cards will overflow and put us | |
94 | * in the right place. | |
95 | */ | |
96 | s->generationalMaps.cardMapAbsolute = | |
97 | s->generationalMaps.cardMap | |
98 | - pointerToCardMapIndexAbsolute (s->heap.start); | |
99 | if (DEBUG_CARD_MARKING) | |
100 | fprintf (stderr, "setCardMapAbsolute = "FMTPTR"\n", | |
101 | (uintptr_t)s->generationalMaps.cardMapAbsolute); | |
102 | } | |
103 | ||
104 | #if ASSERT | |
105 | pointer getCrossMapCardStart (GC_state s, pointer p) { | |
106 | /* The p - 1 is so that a pointer to the beginning of a card falls | |
107 | * into the index for the previous crossMap entry. | |
108 | */ | |
109 | return | |
110 | (p == s->heap.start) | |
111 | ? s->heap.start | |
112 | : (p - 1) - ((uintptr_t)(p - 1) % CARD_SIZE); | |
113 | } | |
114 | #endif | |
115 | ||
116 | size_t sizeofCardMap (GC_state s, size_t heapSize) { | |
117 | unless (s->mutatorMarksCards) { | |
118 | return 0; | |
119 | } | |
120 | assert (isAligned (heapSize, CARD_SIZE)); | |
121 | ||
122 | GC_cardMapIndex cardMapLength; | |
123 | size_t cardMapSize; | |
124 | ||
125 | cardMapLength = sizeToCardMapIndex (heapSize); | |
126 | cardMapSize = align (cardMapLength * CARD_MAP_ELEM_SIZE, s->sysvals.pageSize); | |
127 | ||
128 | return cardMapSize; | |
129 | } | |
130 | ||
131 | GC_cardMapIndex lenofCardMap (ARG_USED_FOR_ASSERT GC_state s, size_t cardMapSize) { | |
132 | GC_cardMapIndex cardMapLength; | |
133 | ||
134 | assert (isAligned (cardMapSize, s->sysvals.pageSize)); | |
135 | assert (isAligned (cardMapSize, CARD_MAP_ELEM_SIZE)); | |
136 | ||
137 | cardMapLength = (GC_cardMapIndex)(cardMapSize / CARD_MAP_ELEM_SIZE); | |
138 | ||
139 | return cardMapLength; | |
140 | } | |
141 | ||
142 | size_t sizeofCrossMap (GC_state s, size_t heapSize) { | |
143 | unless (s->mutatorMarksCards) { | |
144 | return 0; | |
145 | } | |
146 | assert (isAligned (heapSize, CARD_SIZE)); | |
147 | ||
148 | GC_crossMapIndex crossMapLength; | |
149 | size_t crossMapSize; | |
150 | ||
151 | crossMapLength = sizeToCrossMapIndex (heapSize); | |
152 | crossMapSize = align (crossMapLength * CROSS_MAP_ELEM_SIZE, s->sysvals.pageSize); | |
153 | ||
154 | return crossMapSize; | |
155 | } | |
156 | ||
157 | GC_crossMapIndex lenofCrossMap (ARG_USED_FOR_ASSERT GC_state s, size_t crossMapSize) { | |
158 | GC_crossMapIndex crossMapLength; | |
159 | ||
160 | assert (isAligned (crossMapSize, s->sysvals.pageSize)); | |
161 | assert (isAligned (crossMapSize, CROSS_MAP_ELEM_SIZE)); | |
162 | ||
163 | crossMapLength = (GC_crossMapIndex)(crossMapSize / CROSS_MAP_ELEM_SIZE); | |
164 | ||
165 | return crossMapLength; | |
166 | } | |
167 | ||
168 | void clearCardMap (GC_state s) { | |
169 | if (DEBUG_GENERATIONAL and DEBUG_DETAILED) | |
170 | fprintf (stderr, "clearCardMap ()\n"); | |
171 | memset (s->generationalMaps.cardMap, 0, | |
172 | s->generationalMaps.cardMapLength * CARD_MAP_ELEM_SIZE); | |
173 | } | |
174 | ||
175 | void clearCrossMap (GC_state s) { | |
176 | if (DEBUG_GENERATIONAL and DEBUG_DETAILED) | |
177 | fprintf (stderr, "clearCrossMap ()\n"); | |
178 | s->generationalMaps.crossMapValidSize = 0; | |
179 | memset (s->generationalMaps.crossMap, CROSS_MAP_EMPTY, | |
180 | s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE); | |
181 | } | |
182 | ||
183 | void clearCardMapAndCrossMap (GC_state s) { | |
184 | clearCardMap (s); | |
185 | clearCrossMap (s); | |
186 | } | |
187 | ||
188 | size_t sizeofCardMapAndCrossMap (GC_state s, size_t heapSize) { | |
189 | size_t totalMapSize; | |
190 | ||
191 | totalMapSize = sizeofCardMap (s, heapSize) + sizeofCrossMap (s, heapSize); | |
192 | ||
193 | assert (isAligned (totalMapSize, s->sysvals.pageSize)); | |
194 | ||
195 | return totalMapSize; | |
196 | } | |
197 | ||
198 | /* | |
199 | * heapSize = invertSizeofCardMapAndCrossMap (s, heapWithMapsSize); | |
200 | * implies | |
201 | * heapSize + sizeofCardMapAndCrossMap (s, heapSize) | |
202 | * <= heapWithMapsSize | |
203 | * < (heapSize + s->sysvals.pageSize) | |
204 | * + sizeofCardMapAndCrossMap (s, heapSize + s->sysvals.pageSize) | |
205 | */ | |
206 | size_t invertSizeofCardMapAndCrossMap (GC_state s, size_t heapWithMapsSize) { | |
207 | unless (s->mutatorMarksCards) { | |
208 | return heapWithMapsSize; | |
209 | } | |
210 | assert (isAligned (heapWithMapsSize, s->sysvals.pageSize)); | |
211 | ||
212 | size_t minHeapSize; | |
213 | if (heapWithMapsSize <= 3 * s->sysvals.pageSize) { | |
214 | minHeapSize = 0; | |
215 | } else { | |
216 | double minHeapSizeD; | |
217 | minHeapSizeD = | |
218 | (((double)(CARD_SIZE) | |
219 | / (double)(CARD_SIZE + CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE)) | |
220 | * (double)(heapWithMapsSize - 3 * s->sysvals.pageSize)) - | |
221 | (((double)(CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE) | |
222 | / (double)(CARD_SIZE + CARD_MAP_ELEM_SIZE + CROSS_MAP_ELEM_SIZE)) * | |
223 | (double)(s->sysvals.pageSize)); | |
224 | minHeapSize = alignDown ((size_t)minHeapSizeD, s->sysvals.pageSize); | |
225 | } | |
226 | ||
227 | size_t heapSize = minHeapSize; | |
228 | size_t nextHeapSize = heapSize + s->sysvals.pageSize; | |
229 | /* The termination condition is: | |
230 | * heapWithMapsSize >= nextHeapSize + sizeofCardMapAndCrossMap (s, nextHeapSize) | |
231 | * However, nextHeapSize + sizeofCardMapAndCrossMap (s, nextHeapSize) may overflow. | |
232 | */ | |
233 | while (heapWithMapsSize >= sizeofCardMapAndCrossMap (s, nextHeapSize) and | |
234 | heapWithMapsSize - sizeofCardMapAndCrossMap (s, nextHeapSize) >= nextHeapSize) { | |
235 | heapSize = nextHeapSize; | |
236 | nextHeapSize += s->sysvals.pageSize; | |
237 | } | |
238 | ||
239 | assert (isAligned (heapSize, s->sysvals.pageSize)); | |
240 | assert (heapSize + sizeofCardMapAndCrossMap (s, heapSize) <= heapWithMapsSize); | |
241 | assert (nextHeapSize == heapSize + s->sysvals.pageSize); | |
242 | assert (heapWithMapsSize < sizeofCardMapAndCrossMap (s, nextHeapSize) or | |
243 | heapWithMapsSize - sizeofCardMapAndCrossMap (s, nextHeapSize) < nextHeapSize); | |
244 | ||
245 | if (DEBUG_DETAILED) | |
246 | fprintf (stderr, "invertSizeofCardMapAndCrossMap(%s) = %s\n", | |
247 | uintmaxToCommaString(heapWithMapsSize), | |
248 | uintmaxToCommaString(heapSize)); | |
249 | ||
250 | return heapSize; | |
251 | } | |
252 | ||
253 | void setCardMapAndCrossMap (GC_state s) { | |
254 | unless (s->mutatorMarksCards) { | |
255 | s->generationalMaps.cardMapLength = 0; | |
256 | s->generationalMaps.cardMap = NULL; | |
257 | s->generationalMaps.cardMapAbsolute = NULL; | |
258 | s->generationalMaps.crossMapLength = 0; | |
259 | s->generationalMaps.crossMap = NULL; | |
260 | return; | |
261 | } | |
262 | ||
263 | GC_cardMapIndex cardMapLength; | |
264 | size_t cardMapSize; | |
265 | GC_crossMapIndex crossMapLength; | |
266 | size_t crossMapSize; | |
267 | ||
268 | cardMapSize = sizeofCardMap (s, s->heap.size); | |
269 | cardMapLength = lenofCardMap (s, cardMapSize); | |
270 | s->generationalMaps.cardMapLength = cardMapLength; | |
271 | ||
272 | crossMapSize = sizeofCrossMap (s, s->heap.size); | |
273 | crossMapLength = lenofCrossMap (s, crossMapSize); | |
274 | s->generationalMaps.crossMapLength = crossMapLength; | |
275 | ||
276 | /* The card map starts at the end of the heap. */ | |
277 | assert (s->heap.withMapsSize == s->heap.size + cardMapSize + crossMapSize); | |
278 | s->generationalMaps.cardMap = | |
279 | (GC_cardMap) (s->heap.start + s->heap.size); | |
280 | s->generationalMaps.crossMap = | |
281 | (GC_crossMap) (s->heap.start + s->heap.size + cardMapSize); | |
282 | setCardMapAbsolute (s); | |
283 | clearCardMapAndCrossMap (s); | |
284 | } | |
285 | ||
286 | #if ASSERT | |
287 | /* isCrossMapOk is a slower, but easier to understand, way of | |
288 | * computing the crossMap. updateCrossMap (below) incrementally | |
289 | * updates the crossMap, checking only the part of the old generation | |
290 | * that it hasn't seen before. isCrossMapOk simply walks through the | |
291 | * entire old generation. It is useful to check that the incremental | |
292 | * update is working correctly. | |
293 | */ | |
294 | bool isCrossMapOk (GC_state s) { | |
295 | static GC_crossMapElem *map; | |
296 | size_t mapSize; | |
297 | ||
298 | pointer front, back; | |
299 | GC_cardMapIndex cardIndex; | |
300 | pointer cardStart; | |
301 | ||
302 | if (DEBUG) | |
303 | fprintf (stderr, "isCrossMapOk ()\n"); | |
304 | mapSize = s->generationalMaps.crossMapLength * CROSS_MAP_ELEM_SIZE; | |
305 | map = GC_mmapAnon_safe (NULL, mapSize); | |
306 | memset (map, CROSS_MAP_EMPTY, mapSize); | |
307 | back = s->heap.start + s->heap.oldGenSize; | |
308 | front = alignFrontier (s, s->heap.start); | |
309 | loopObjects: | |
310 | assert (front <= back); | |
311 | cardStart = getCrossMapCardStart (s, front); | |
312 | cardIndex = sizeToCardMapIndex ((size_t)(cardStart - s->heap.start)); | |
313 | map[cardIndex] = (GC_crossMapElem)((front - cardStart) / CROSS_MAP_OFFSET_SCALE); | |
314 | if (front < back) { | |
315 | front += sizeofObject (s, advanceToObjectData (s, front)); | |
316 | goto loopObjects; | |
317 | } | |
318 | for (size_t i = 0; i < cardIndex; ++i) | |
319 | assert (map[i] == s->generationalMaps.crossMap[i]); | |
320 | GC_release (map, mapSize); | |
321 | return TRUE; | |
322 | } | |
323 | #endif | |
324 | ||
325 | void updateCrossMap (GC_state s) { | |
326 | GC_cardMapIndex cardIndex; | |
327 | pointer cardStart, cardEnd; | |
328 | ||
329 | pointer nextObject, objectStart; | |
330 | pointer oldGenEnd; | |
331 | ||
332 | if (DEBUG_GENERATIONAL) { | |
333 | fprintf (stderr, "updateCrossMap starting\n"); | |
334 | displayGenerationalMaps (s, &s->generationalMaps, stderr); | |
335 | } | |
336 | assert (isAligned (s->alignment, CROSS_MAP_OFFSET_SCALE)); | |
337 | if (s->generationalMaps.crossMapValidSize == s->heap.oldGenSize) | |
338 | goto done; | |
339 | oldGenEnd = s->heap.start + s->heap.oldGenSize; | |
340 | objectStart = s->heap.start + s->generationalMaps.crossMapValidSize; | |
341 | if (objectStart == s->heap.start) { | |
342 | cardIndex = 0; | |
343 | objectStart = alignFrontier (s, objectStart); | |
344 | } else | |
345 | cardIndex = sizeToCardMapIndex ((size_t)(objectStart - s->heap.start) - 1); | |
346 | cardStart = s->heap.start + cardMapIndexToSize (cardIndex); | |
347 | cardEnd = cardStart + CARD_SIZE; | |
348 | loopObjects: | |
349 | assert (objectStart < oldGenEnd); | |
350 | assert ((objectStart == s->heap.start or cardStart < objectStart) | |
351 | and objectStart <= cardEnd); | |
352 | nextObject = objectStart + sizeofObject (s, advanceToObjectData (s, objectStart)); | |
353 | if (DEBUG_GENERATIONAL) { | |
354 | fprintf (stderr, | |
355 | "\tloopObjects:\n" | |
356 | "\t cardIndex = %"PRIuMAX"\n" | |
357 | "\t cardStart = "FMTPTR"\n" | |
358 | "\t cardEnd = "FMTPTR"\n" | |
359 | "\tobjectStart = "FMTPTR"\n" | |
360 | "\t nextObject = "FMTPTR"\n", | |
361 | (uintmax_t)cardIndex, (uintptr_t)cardStart, (uintptr_t)cardEnd, | |
362 | (uintptr_t)objectStart, (uintptr_t)nextObject); | |
363 | } | |
364 | if (nextObject > cardEnd) { | |
365 | /* We're about to move to a new card, so we are looking at the | |
366 | * last object boundary in the current card. | |
367 | * Store it in the crossMap. | |
368 | */ | |
369 | size_t offset; | |
370 | ||
371 | offset = (size_t)(objectStart - cardStart) / CROSS_MAP_OFFSET_SCALE; | |
372 | assert (offset < CROSS_MAP_EMPTY); | |
373 | if (DEBUG_GENERATIONAL) | |
374 | fprintf (stderr, "crossMap[%"PRIuMAX"] = %"PRIuMAX"\n", | |
375 | (uintmax_t)cardIndex, (uintmax_t)offset); | |
376 | s->generationalMaps.crossMap[cardIndex] = (GC_crossMapElem)offset; | |
377 | cardIndex = sizeToCardMapIndex ((size_t)(nextObject - s->heap.start) - 1); | |
378 | cardStart = s->heap.start + cardMapIndexToSize (cardIndex); | |
379 | cardEnd = cardStart + CARD_SIZE; | |
380 | } | |
381 | objectStart = nextObject; | |
382 | if (objectStart < oldGenEnd) | |
383 | goto loopObjects; | |
384 | assert (objectStart == oldGenEnd); | |
385 | s->generationalMaps.crossMap[cardIndex] = | |
386 | (GC_crossMapElem)(oldGenEnd - cardStart) / CROSS_MAP_OFFSET_SCALE; | |
387 | s->generationalMaps.crossMapValidSize = s->heap.oldGenSize; | |
388 | done: | |
389 | assert (s->generationalMaps.crossMapValidSize == s->heap.oldGenSize); | |
390 | assert (isCrossMapOk (s)); | |
391 | if (DEBUG_GENERATIONAL) { | |
392 | fprintf (stderr, "updateCrossMap finished\n"); | |
393 | displayGenerationalMaps (s, &s->generationalMaps, stderr); | |
394 | } | |
395 | } |