NonMoving: Add summarizing Note
[ghc.git] / rts / sm / NonMoving.c
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 1998-2018
4 *
5 * Non-moving garbage collector and allocator
6 *
7 * ---------------------------------------------------------------------------*/
8
9 #include "Rts.h"
10 #include "RtsUtils.h"
11 #include "Capability.h"
12 #include "Printer.h"
13 #include "Storage.h"
14 // We call evacuate, which expects the thread-local gc_thread to be valid;
15 // This is sometimes declared as a register variable therefore it is necessary
16 // to include the declaration so that the compiler doesn't clobber the register.
17 #include "GCThread.h"
18 #include "GCTDecl.h"
19 #include "Schedule.h"
20 #include "Stats.h"
21
22 #include "NonMoving.h"
23 #include "NonMovingMark.h"
24 #include "NonMovingSweep.h"
25 #include "NonMovingCensus.h"
26 #include "StablePtr.h" // markStablePtrTable
27 #include "Schedule.h" // markScheduler
28 #include "Weak.h" // dead_weak_ptr_list
29
30 struct NonmovingHeap nonmovingHeap;
31
32 uint8_t nonmovingMarkEpoch = 1;
33
34 static void nonmovingBumpEpoch(void) {
35 nonmovingMarkEpoch = nonmovingMarkEpoch == 1 ? 2 : 1;
36 }
37
38 #if defined(THREADED_RTS)
39 /*
40 * This mutex ensures that only one non-moving collection is active at a time.
41 */
42 Mutex nonmoving_collection_mutex;
43
44 OSThreadId mark_thread;
45 bool concurrent_coll_running = false;
46 Condition concurrent_coll_finished;
47 Mutex concurrent_coll_finished_lock;
48 #endif
49
50 /*
51 * Note [Non-moving garbage collector]
52 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
53 * The sources rts/NonMoving*.c implement GHC's non-moving garbage collector
54 * for the oldest generation. In contrast to the throughput-oriented moving
55 * collector, the non-moving collector is designed to achieve low GC latencies
56 * on large heaps. It accomplishes low-latencies by way of a concurrent
57 * mark-and-sweep collection strategy on a specially-designed heap structure.
58 * While the design is described in detail in the design document found in
59 * docs/storage/nonmoving-gc, we briefly summarize the structure here.
60 *
61 *
62 * === Heap Structure ===
63 *
64 * The nonmoving heap (embodied by struct NonmovingHeap) consists of a family
65 * of allocators, each serving a range of allocation sizes. Each allocator
66 * consists of a set of *segments*, each of which contain fixed-size *blocks*
67 * (not to be confused with "blocks" provided by GHC's block allocator; this is
68 * admittedly an unfortunate overlap in terminology). These blocks are the
69 * backing store for the allocator. In addition to blocks, the segment also
70 * contains some header information (see struct NonmovingSegment in
71 * NonMoving.h). This header contains a *bitmap* encoding one byte per block
72 * (used by the collector to record liveness), as well as the index of the next
73 * unallocated block (and a *snapshot* of this field which will be described in
74 * the next section).
75 *
76 * Each allocator maintains three sets of segments:
77 *
78 * - A *current* segment for each capability; this is the segment which that
79 * capability will allocate into.
80 *
81 * - A pool of *active* segments, each of which containing at least one
82 * unallocated block. The allocate will take a segment from this pool when
83 * it fills its *current* segment.
84 *
85 * - A set of *filled* segments, which contain no unallocated blocks and will
86 * be collected during the next major GC cycle
87 *
88 * Storage for segments is allocated using the block allocator using an aligned
89 * group of NONMOVING_SEGMENT_BLOCKS blocks. This makes the task of locating
90 * the segment header for a clone a simple matter of bit-masking (as
91 * implemented by nonmovingGetSegment).
92 *
93 * In addition, to relieve pressure on the block allocator we keep a small pool
94 * of free blocks around (nonmovingHeap.free) which can be pushed/popped
95 * to/from in a lock-free manner.
96 *
97 *
98 * === Allocation ===
99 *
100 * The allocator (as implemented by nonmovingAllocate) starts by identifying
101 * which allocator the request should be made against. It then allocates into
102 * its local current segment and bumps the next_free pointer to point to the
103 * next unallocated block (as indicated by the bitmap). If it finds the current
104 * segment is now full it moves it to the filled list and looks for a new
105 * segment to make current from a few sources:
106 *
107 * 1. the allocator's active list (see pop_active_segment)
108 * 2. the nonmoving heap's free block pool (see nonmovingPopFreeSegment)
109 * 3. allocate a new segment from the block allocator (see
110 * nonmovingAllocSegment)
111 *
112 * Note that allocation does *not* involve modifying the bitmap. The bitmap is
113 * only modified by the collector.
114 *
115 *
116 * === Snapshot invariant ===
117 *
118 * To safely collect in a concurrent setting, the collector relies on the
119 * notion of a *snapshot*. The snapshot is a hypothetical frozen state of the
120 * heap topology taken at the beginning of the major collection cycle.
121 * With this definition we require the following property of the mark phase,
122 * which we call the *snapshot invariant*,
123 *
124 * All objects that were reachable at the time the snapshot was collected
125 * must have their mark bits set at the end of the mark phase.
126 *
127 * As the mutator might change the topology of the heap while we are marking
128 * this property requires some cooperation from the mutator to maintain.
129 * Specifically, we rely on a write barrier as described in Note [Update
130 * remembered set].
131 *
132 * To determine which objects were existent when the snapshot was taken we
133 * record a snapshot of each segments next_free pointer at the beginning of
134 * collection.
135 *
136 *
137 * === Collection ===
138 *
139 * Collection happens in a few phases some of which occur during a
140 * stop-the-world period (marked with [STW]) and others which can occur
141 * concurrently with mutation and minor collection (marked with [CONC]):
142 *
143 * 1. [STW] Preparatory GC: Here we do a standard minor collection of the
144 * younger generations (which may evacuate things to the nonmoving heap).
145 * References from younger generations into the nonmoving heap are recorded
146 * in the mark queue (see Note [Aging under the non-moving collector] in
147 * this file).
148 *
149 * 2. [STW] Snapshot update: Here we update the segment snapshot metadata
150 * (see nonmovingPrepareMark) and move the filled segments to
151 * nonmovingHeap.sweep_list, which is the set of segments which we will
152 * sweep this GC cycle.
153 *
154 * 3. [STW] Root collection: Here we walk over a variety of root sources
155 * and add them to the mark queue (see nonmovingCollect).
156 *
157 * 4. [CONC] Concurrent marking: Here we do the majority of marking concurrently
158 * with mutator execution (but with the write barrier enabled; see
159 * Note [Update remembered set]).
160 *
161 * 5. [STW] Final sync: Here we interrupt the mutators, ask them to
162 * flush their final update remembered sets, and mark any new references
163 * we find.
164 *
165 * 6. [CONC] Sweep: Here we walk over the nonmoving segments on sweep_list
166 * and place them back on either the active, current, or filled list,
167 * depending upon how much live data they contain.
168 *
169 *
170 * === Marking ===
171 *
172 * Ignoring large and static objects, marking a closure is fairly
173 * straightforward (implemented in NonMovingMark.c:mark_closure):
174 *
175 * 1. Check whether the closure is in the non-moving generation; if not then
176 * we ignore it.
177 * 2. Find the segment containing the closure's block.
178 * 3. Check whether the closure's block is above $seg->next_free_snap; if so
179 * then the block was not allocated when we took the snapshot and therefore
180 * we don't need to mark it.
181 * 4. Check whether the block's bitmap bits is equal to nonmovingMarkEpoch. If
182 * so then we can stop as we have already marked it.
183 * 5. Push the closure's pointers to the mark queue.
184 * 6. Set the blocks bitmap bits to nonmovingMarkEpoch.
185 *
186 * Note that the ordering of (5) and (6) is rather important, as described in
187 * Note [StgStack dirtiness flags and concurrent marking].
188 *
189 *
190 * === Other references ===
191 *
192 * Apart from the design document in docs/storage/nonmoving-gc and the Ueno
193 * 2016 paper (TODO citation) from which it drew inspiration, there are a
194 * variety of other relevant Notes scattered throughout the tree:
195 *
196 * - Note [Concurrent non-moving collection] (NonMoving.c) describes
197 * concurrency control of the nonmoving collector
198 *
199 * - Note [Live data accounting in nonmoving collector] (NonMoving.c)
200 * describes how we track the quantity of live data in the nonmoving
201 * generation.
202 *
203 * - Note [Aging under the non-moving collector] (NonMoving.c) describes how
204 * we accomodate aging
205 *
206 * - Note [Large objects in the non-moving collector] (NonMovingMark.c)
207 * describes how we track large objects.
208 *
209 * - Note [Update remembered set] (NonMovingMark.c) describes the function and
210 * implementation of the update remembered set used to realize the concurrent
211 * write barrier.
212 *
213 * - Note [Concurrent read barrier on deRefWeak#] (NonMovingMark.c) describes
214 * the read barrier on Weak# objects.
215 *
216 * - Note [Unintentional marking in resurrectThreads] (NonMovingMark.c) describes
217 * a tricky interaction between the update remembered set flush and weak
218 * finalization.
219 *
220 * - Note [Origin references in the nonmoving collector] (NonMovingMark.h)
221 * describes how we implement indirection short-cutting and the selector
222 * optimisation.
223 *
224 * - Note [StgStack dirtiness flags and concurrent marking] (TSO.h) describes
225 * the protocol for concurrent marking of stacks.
226 *
227 * - Note [Static objects under the nonmoving collector] (Storage.c) describes
228 * treatment of static objects.
229 *
230 *
231 * Note [Concurrent non-moving collection]
232 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
233 * Concurrency-control of non-moving garbage collection is a bit tricky. There
234 * are a few things to keep in mind:
235 *
236 * - Only one non-moving collection may be active at a time. This is enforced by the
237 * concurrent_coll_running flag, which is set when a collection is on-going. If
238 * we attempt to initiate a new collection while this is set we wait on the
239 * concurrent_coll_finished condition variable, which signals when the
240 * active collection finishes.
241 *
242 * - In between the mark and sweep phases the non-moving collector must synchronize
243 * with mutator threads to collect and mark their final update remembered
244 * sets. This is accomplished using
245 * stopAllCapabilitiesWith(SYNC_FLUSH_UPD_REM_SET). Capabilities are held
246 * the final mark has concluded.
247 *
248 * Note that possibility of concurrent minor and non-moving collections
249 * requires that we handle static objects a bit specially. See
250 * Note [Static objects under the nonmoving collector] in Storage.c
251 * for details.
252 *
253 *
254 * Note [Aging under the non-moving collector]
255 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
256 *
257 * The initial design of the non-moving collector mandated that all live data
258 * be evacuated to the non-moving heap prior to a major collection. This
259 * simplified certain bits of implementation and eased reasoning. However, it
260 * was (unsurprisingly) also found to result in significant amounts of
261 * unnecessary copying.
262 *
263 * Consequently, we now allow aging. Aging allows the preparatory GC leading up
264 * to a major collection to evacuate some objects into the young generation.
265 * However, this introduces the following tricky case that might arise after
266 * we have finished the preparatory GC:
267 *
268 * moving heap ┆ non-moving heap
269 * ───────────────┆──────────────────
270 * ┆
271 * B ←────────────── A ←─────────────── root
272 * │ ┆ ↖─────────────── gen1 mut_list
273 * ╰───────────────→ C
274 * ┆
275 *
276 * In this case C is clearly live, but the non-moving collector can only see
277 * this by walking through B, which lives in the moving heap. However, doing so
278 * would require that we synchronize with the mutator/minor GC to ensure that it
279 * isn't in the middle of moving B. What to do?
280 *
281 * The solution we use here is to teach the preparatory moving collector to
282 * "evacuate" objects it encounters in the non-moving heap by adding them to
283 * the mark queue. This is implemented by pushing the object to the update
284 * remembered set of the capability held by the evacuating gc_thread
285 * (implemented by markQueuePushClosureGC)
286 *
287 * Consequently collection of the case above would proceed as follows:
288 *
289 * 1. Initial state:
290 * * A lives in the non-moving heap and is reachable from the root set
291 * * A is on the oldest generation's mut_list, since it contains a pointer
292 * to B, which lives in a younger generation
293 * * B lives in the moving collector's from space
294 * * C lives in the non-moving heap
295 *
296 * 2. Preparatory GC: Scavenging mut_lists:
297 *
298 * The mut_list of the oldest generation is scavenged, resulting in B being
299 * evacuated (aged) into the moving collector's to-space.
300 *
301 * 3. Preparatory GC: Scavenge B
302 *
303 * B (now in to-space) is scavenged, resulting in evacuation of C.
304 * evacuate(C) pushes a reference to C to the mark queue.
305 *
306 * 4. Non-moving GC: C is marked
307 *
308 * The non-moving collector will come to C in the mark queue and mark it.
309 *
310 *
311 * Note [Deadlock detection under the non-moving collector]
312 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
313 * In GHC the garbage collector is responsible for identifying deadlocked
314 * programs. Providing for this responsibility is slightly tricky in the
315 * non-moving collector due to the existence of aging. In particular, the
316 * non-moving collector cannot traverse objects living in a young generation
317 * but reachable from the non-moving generation, as described in Note [Aging
318 * under the non-moving collector].
319 *
320 * However, this can pose trouble for deadlock detection since it means that we
321 * may conservatively mark dead closures as live. Consider this case:
322 *
323 * moving heap ┆ non-moving heap
324 * ───────────────┆──────────────────
325 * ┆
326 * MVAR_QUEUE ←───── TSO ←───────────── gen1 mut_list
327 * ↑ │ ╰────────↗ │
328 * │ │ ┆ │
329 * │ │ ┆ ↓
330 * │ ╰──────────→ MVAR
331 * ╰─────────────────╯
332 * ┆
333 *
334 * In this case we have a TSO blocked on a dead MVar. Because the MVAR_TSO_QUEUE on
335 * which it is blocked lives in the moving heap, the TSO is necessarily on the
336 * oldest generation's mut_list. As in Note [Aging under the non-moving
337 * collector], the MVAR_TSO_QUEUE will be evacuated. If MVAR_TSO_QUEUE is aged
338 * (e.g. evacuated to the young generation) then the MVAR will be added to the
339 * mark queue. Consequently, we will falsely conclude that the MVAR is still
340 * alive and fail to spot the deadlock.
341 *
342 * To avoid this sort of situation we disable aging when we are starting a
343 * major GC specifically for deadlock detection (as done by
344 * scheduleDetectDeadlock). This condition is recorded by the
345 * deadlock_detect_gc global variable declared in GC.h. Setting this has a few
346 * effects on the preparatory GC:
347 *
348 * - Evac.c:alloc_for_copy forces evacuation to the non-moving generation.
349 *
350 * - The evacuation logic usually responsible for pushing objects living in
351 * the non-moving heap to the mark queue is disabled. This is safe because
352 * we know that all live objects will be in the non-moving heap by the end
353 * of the preparatory moving collection.
354 *
355 *
356 * Note [Live data accounting in nonmoving collector]
357 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
358 * The nonmoving collector uses an approximate heuristic for reporting live
359 * data quantity. Specifically, during mark we record how much live data we
360 * find in nonmoving_live_words. At the end of mark we declare this amount to
361 * be how much live data we have on in the nonmoving heap (by setting
362 * oldest_gen->live_estimate).
363 *
364 * In addition, we update oldest_gen->live_estimate every time we fill a
365 * segment. This, as well, is quite approximate: we assume that all blocks
366 * above next_free_next are newly-allocated. In principle we could refer to the
367 * bitmap to count how many blocks we actually allocated but this too would be
368 * approximate due to concurrent collection and ultimately seems more costly
369 * than the problem demands.
370 *
371 */
372
373 W_ nonmoving_live_words = 0;
374
375 #if defined(THREADED_RTS)
376 static void* nonmovingConcurrentMark(void *mark_queue);
377 #endif
378 static void nonmovingClearBitmap(struct NonmovingSegment *seg);
379 static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO **resurrected_threads);
380
381 static void nonmovingInitSegment(struct NonmovingSegment *seg, uint8_t block_size)
382 {
383 seg->link = NULL;
384 seg->todo_link = NULL;
385 seg->next_free = 0;
386 seg->next_free_snap = 0;
387 seg->block_size = block_size;
388 nonmovingClearBitmap(seg);
389 Bdescr((P_)seg)->u.scan = nonmovingSegmentGetBlock(seg, 0);
390 }
391
392 // Add a segment to the free list.
393 void nonmovingPushFreeSegment(struct NonmovingSegment *seg)
394 {
395 // See Note [Live data accounting in nonmoving collector].
396 if (nonmovingHeap.n_free > NONMOVING_MAX_FREE) {
397 bdescr *bd = Bdescr((StgPtr) seg);
398 ACQUIRE_SM_LOCK;
399 ASSERT(oldest_gen->n_blocks >= bd->blocks);
400 ASSERT(oldest_gen->n_words >= BLOCK_SIZE_W * bd->blocks);
401 oldest_gen->n_blocks -= bd->blocks;
402 oldest_gen->n_words -= BLOCK_SIZE_W * bd->blocks;
403 freeGroup(bd);
404 RELEASE_SM_LOCK;
405 return;
406 }
407
408 while (true) {
409 struct NonmovingSegment *old = nonmovingHeap.free;
410 seg->link = old;
411 if (cas((StgVolatilePtr) &nonmovingHeap.free, (StgWord) old, (StgWord) seg) == (StgWord) old)
412 break;
413 }
414 __sync_add_and_fetch(&nonmovingHeap.n_free, 1);
415 }
416
417 static struct NonmovingSegment *nonmovingPopFreeSegment(void)
418 {
419 while (true) {
420 struct NonmovingSegment *seg = nonmovingHeap.free;
421 if (seg == NULL) {
422 return NULL;
423 }
424 if (cas((StgVolatilePtr) &nonmovingHeap.free,
425 (StgWord) seg,
426 (StgWord) seg->link) == (StgWord) seg) {
427 __sync_sub_and_fetch(&nonmovingHeap.n_free, 1);
428 return seg;
429 }
430 }
431 }
432
433 unsigned int nonmovingBlockCountFromSize(uint8_t log_block_size)
434 {
435 // We compute the overwhelmingly common size cases directly to avoid a very
436 // expensive integer division.
437 switch (log_block_size) {
438 case 3: return nonmovingBlockCount(3);
439 case 4: return nonmovingBlockCount(4);
440 case 5: return nonmovingBlockCount(5);
441 case 6: return nonmovingBlockCount(6);
442 case 7: return nonmovingBlockCount(7);
443 default: return nonmovingBlockCount(log_block_size);
444 }
445 }
446
447 /*
448 * Request a fresh segment from the free segment list or allocate one of the
449 * given node.
450 *
451 * Caller must hold SM_MUTEX (although we take the gc_alloc_block_sync spinlock
452 * under the assumption that we are in a GC context).
453 */
454 static struct NonmovingSegment *nonmovingAllocSegment(uint32_t node)
455 {
456 // First try taking something off of the free list
457 struct NonmovingSegment *ret;
458 ret = nonmovingPopFreeSegment();
459
460 // Nothing in the free list, allocate a new segment...
461 if (ret == NULL) {
462 // Take gc spinlock: another thread may be scavenging a moving
463 // generation and call `todo_block_full`
464 ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
465 bdescr *bd = allocAlignedGroupOnNode(node, NONMOVING_SEGMENT_BLOCKS);
466 // See Note [Live data accounting in nonmoving collector].
467 oldest_gen->n_blocks += bd->blocks;
468 oldest_gen->n_words += BLOCK_SIZE_W * bd->blocks;
469 RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
470
471 for (StgWord32 i = 0; i < bd->blocks; ++i) {
472 initBdescr(&bd[i], oldest_gen, oldest_gen);
473 bd[i].flags = BF_NONMOVING;
474 }
475 ret = (struct NonmovingSegment *)bd->start;
476 }
477
478 // Check alignment
479 ASSERT(((uintptr_t)ret % NONMOVING_SEGMENT_SIZE) == 0);
480 return ret;
481 }
482
483 static inline unsigned long log2_floor(unsigned long x)
484 {
485 return sizeof(unsigned long)*8 - 1 - __builtin_clzl(x);
486 }
487
488 static inline unsigned long log2_ceil(unsigned long x)
489 {
490 unsigned long log = log2_floor(x);
491 return (x - (1 << log)) ? log + 1 : log;
492 }
493
494 // Advance a segment's next_free pointer. Returns true if segment if full.
495 static bool advance_next_free(struct NonmovingSegment *seg, const unsigned int blk_count)
496 {
497 const uint8_t *bitmap = seg->bitmap;
498 ASSERT(blk_count == nonmovingSegmentBlockCount(seg));
499 #if defined(NAIVE_ADVANCE_FREE)
500 // reference implementation
501 for (unsigned int i = seg->next_free+1; i < blk_count; i++) {
502 if (!bitmap[i]) {
503 seg->next_free = i;
504 return false;
505 }
506 }
507 seg->next_free = blk_count;
508 return true;
509 #else
510 const uint8_t *c = memchr(&bitmap[seg->next_free+1], 0, blk_count - seg->next_free - 1);
511 if (c == NULL) {
512 seg->next_free = blk_count;
513 return true;
514 } else {
515 seg->next_free = c - bitmap;
516 return false;
517 }
518 #endif
519 }
520
521 static struct NonmovingSegment *pop_active_segment(struct NonmovingAllocator *alloca)
522 {
523 while (true) {
524 struct NonmovingSegment *seg = alloca->active;
525 if (seg == NULL) {
526 return NULL;
527 }
528 if (cas((StgVolatilePtr) &alloca->active,
529 (StgWord) seg,
530 (StgWord) seg->link) == (StgWord) seg) {
531 return seg;
532 }
533 }
534 }
535
536 /* Allocate a block in the nonmoving heap. Caller must hold SM_MUTEX. sz is in words */
537 GNUC_ATTR_HOT
538 void *nonmovingAllocate(Capability *cap, StgWord sz)
539 {
540 unsigned int log_block_size = log2_ceil(sz * sizeof(StgWord));
541 unsigned int block_count = nonmovingBlockCountFromSize(log_block_size);
542
543 // The max we ever allocate is 3276 bytes (anything larger is a large
544 // object and not moved) which is covered by allocator 9.
545 ASSERT(log_block_size < NONMOVING_ALLOCA0 + NONMOVING_ALLOCA_CNT);
546
547 struct NonmovingAllocator *alloca = nonmovingHeap.allocators[log_block_size - NONMOVING_ALLOCA0];
548
549 // Allocate into current segment
550 struct NonmovingSegment *current = alloca->current[cap->no];
551 ASSERT(current); // current is never NULL
552 void *ret = nonmovingSegmentGetBlock_(current, log_block_size, current->next_free);
553 ASSERT(GET_CLOSURE_TAG(ret) == 0); // check alignment
554
555 // Advance the current segment's next_free or allocate a new segment if full
556 bool full = advance_next_free(current, block_count);
557 if (full) {
558 // Current segment is full: update live data estimate link it to
559 // filled, take an active segment if one exists, otherwise allocate a
560 // new segment.
561
562 // Update live data estimate.
563 // See Note [Live data accounting in nonmoving collector].
564 unsigned int new_blocks = block_count - current->next_free_snap;
565 unsigned int block_size = 1 << log_block_size;
566 atomic_inc(&oldest_gen->live_estimate, new_blocks * block_size / sizeof(W_));
567
568 // push the current segment to the filled list
569 nonmovingPushFilledSegment(current);
570
571 // first look for a new segment in the active list
572 struct NonmovingSegment *new_current = pop_active_segment(alloca);
573
574 // there are no active segments, allocate new segment
575 if (new_current == NULL) {
576 new_current = nonmovingAllocSegment(cap->node);
577 nonmovingInitSegment(new_current, log_block_size);
578 }
579
580 // make it current
581 new_current->link = NULL;
582 alloca->current[cap->no] = new_current;
583 }
584
585 return ret;
586 }
587
588 /* Allocate a nonmovingAllocator */
589 static struct NonmovingAllocator *alloc_nonmoving_allocator(uint32_t n_caps)
590 {
591 size_t allocator_sz =
592 sizeof(struct NonmovingAllocator) +
593 sizeof(void*) * n_caps; // current segment pointer for each capability
594 struct NonmovingAllocator *alloc =
595 stgMallocBytes(allocator_sz, "nonmovingInit");
596 memset(alloc, 0, allocator_sz);
597 return alloc;
598 }
599
600 void nonmovingInit(void)
601 {
602 #if defined(THREADED_RTS)
603 initMutex(&nonmoving_collection_mutex);
604 initCondition(&concurrent_coll_finished);
605 initMutex(&concurrent_coll_finished_lock);
606 #endif
607 for (unsigned int i = 0; i < NONMOVING_ALLOCA_CNT; i++) {
608 nonmovingHeap.allocators[i] = alloc_nonmoving_allocator(n_capabilities);
609 }
610 nonmovingMarkInitUpdRemSet();
611 }
612
613 void nonmovingExit(void)
614 {
615 #if defined(THREADED_RTS)
616 if (mark_thread) {
617 debugTrace(DEBUG_nonmoving_gc,
618 "waiting for nonmoving collector thread to terminate");
619 ACQUIRE_LOCK(&concurrent_coll_finished_lock);
620 waitCondition(&concurrent_coll_finished, &concurrent_coll_finished_lock);
621 }
622 closeMutex(&concurrent_coll_finished_lock);
623 closeCondition(&concurrent_coll_finished);
624 closeMutex(&nonmoving_collection_mutex);
625 #endif
626 }
627
628 /*
629 * Assumes that no garbage collector or mutator threads are running to safely
630 * resize the nonmoving_allocators.
631 *
632 * Must hold sm_mutex.
633 */
634 void nonmovingAddCapabilities(uint32_t new_n_caps)
635 {
636 unsigned int old_n_caps = nonmovingHeap.n_caps;
637 struct NonmovingAllocator **allocs = nonmovingHeap.allocators;
638
639 for (unsigned int i = 0; i < NONMOVING_ALLOCA_CNT; i++) {
640 struct NonmovingAllocator *old = allocs[i];
641 allocs[i] = alloc_nonmoving_allocator(new_n_caps);
642
643 // Copy the old state
644 allocs[i]->filled = old->filled;
645 allocs[i]->active = old->active;
646 for (unsigned int j = 0; j < old_n_caps; j++) {
647 allocs[i]->current[j] = old->current[j];
648 }
649 stgFree(old);
650
651 // Initialize current segments for the new capabilities
652 for (unsigned int j = old_n_caps; j < new_n_caps; j++) {
653 allocs[i]->current[j] = nonmovingAllocSegment(capabilities[j]->node);
654 nonmovingInitSegment(allocs[i]->current[j], NONMOVING_ALLOCA0 + i);
655 allocs[i]->current[j]->link = NULL;
656 }
657 }
658 nonmovingHeap.n_caps = new_n_caps;
659 }
660
661 static inline void nonmovingClearBitmap(struct NonmovingSegment *seg)
662 {
663 unsigned int n = nonmovingSegmentBlockCount(seg);
664 memset(seg->bitmap, 0, n);
665 }
666
667 /* Prepare the heap bitmaps and snapshot metadata for a mark */
668 static void nonmovingPrepareMark(void)
669 {
670 // See Note [Static objects under the nonmoving collector].
671 prev_static_flag = static_flag;
672 static_flag =
673 static_flag == STATIC_FLAG_A ? STATIC_FLAG_B : STATIC_FLAG_A;
674
675 // Should have been cleared by the last sweep
676 ASSERT(nonmovingHeap.sweep_list == NULL);
677
678 nonmovingBumpEpoch();
679 for (int alloca_idx = 0; alloca_idx < NONMOVING_ALLOCA_CNT; ++alloca_idx) {
680 struct NonmovingAllocator *alloca = nonmovingHeap.allocators[alloca_idx];
681
682 // Update current segments' snapshot pointers
683 for (uint32_t cap_n = 0; cap_n < n_capabilities; ++cap_n) {
684 struct NonmovingSegment *seg = alloca->current[cap_n];
685 seg->next_free_snap = seg->next_free;
686 }
687
688 // Update filled segments' snapshot pointers and move to sweep_list
689 uint32_t n_filled = 0;
690 struct NonmovingSegment *const filled = alloca->filled;
691 alloca->filled = NULL;
692 if (filled) {
693 struct NonmovingSegment *seg = filled;
694 while (true) {
695 n_filled++;
696 prefetchForRead(seg->link);
697 // Clear bitmap
698 prefetchForWrite(seg->link->bitmap);
699 nonmovingClearBitmap(seg);
700 // Set snapshot
701 seg->next_free_snap = seg->next_free;
702 if (seg->link)
703 seg = seg->link;
704 else
705 break;
706 }
707 // add filled segments to sweep_list
708 seg->link = nonmovingHeap.sweep_list;
709 nonmovingHeap.sweep_list = filled;
710 }
711
712 // N.B. It's not necessary to update snapshot pointers of active segments;
713 // they were set after they were swept and haven't seen any allocation
714 // since.
715 }
716
717 ASSERT(oldest_gen->scavenged_large_objects == NULL);
718 bdescr *next;
719 for (bdescr *bd = oldest_gen->large_objects; bd; bd = next) {
720 next = bd->link;
721 bd->flags |= BF_NONMOVING_SWEEPING;
722 dbl_link_onto(bd, &nonmoving_large_objects);
723 }
724 n_nonmoving_large_blocks += oldest_gen->n_large_blocks;
725 oldest_gen->large_objects = NULL;
726 oldest_gen->n_large_words = 0;
727 oldest_gen->n_large_blocks = 0;
728 nonmoving_live_words = 0;
729
730 // Clear large object bits
731 for (bdescr *bd = nonmoving_large_objects; bd; bd = bd->link) {
732 bd->flags &= ~BF_MARKED;
733 }
734
735
736 #if defined(DEBUG)
737 debug_caf_list_snapshot = debug_caf_list;
738 debug_caf_list = (StgIndStatic*)END_OF_CAF_LIST;
739 #endif
740 }
741
742 // Mark weak pointers in the non-moving heap. They'll either end up in
743 // dead_weak_ptr_list or stay in weak_ptr_list. Either way they need to be kept
744 // during sweep. See `MarkWeak.c:markWeakPtrList` for the moving heap variant
745 // of this.
746 static void nonmovingMarkWeakPtrList(MarkQueue *mark_queue, StgWeak *dead_weak_ptr_list)
747 {
748 for (StgWeak *w = oldest_gen->weak_ptr_list; w; w = w->link) {
749 markQueuePushClosure_(mark_queue, (StgClosure*)w);
750 // Do not mark finalizers and values here, those fields will be marked
751 // in `nonmovingMarkDeadWeaks` (for dead weaks) or
752 // `nonmovingTidyWeaks` (for live weaks)
753 }
754
755 // We need to mark dead_weak_ptr_list too. This is subtle:
756 //
757 // - By the beginning of this GC we evacuated all weaks to the non-moving
758 // heap (in `markWeakPtrList`)
759 //
760 // - During the scavenging of the moving heap we discovered that some of
761 // those weaks are dead and moved them to `dead_weak_ptr_list`. Note that
762 // because of the fact above _all weaks_ are in the non-moving heap at
763 // this point.
764 //
765 // - So, to be able to traverse `dead_weak_ptr_list` and run finalizers we
766 // need to mark it.
767 for (StgWeak *w = dead_weak_ptr_list; w; w = w->link) {
768 markQueuePushClosure_(mark_queue, (StgClosure*)w);
769 nonmovingMarkDeadWeak(mark_queue, w);
770 }
771 }
772
773 void nonmovingCollect(StgWeak **dead_weaks, StgTSO **resurrected_threads)
774 {
775 #if defined(THREADED_RTS)
776 // We can't start a new collection until the old one has finished
777 // We also don't run in final GC
778 if (concurrent_coll_running || sched_state > SCHED_RUNNING) {
779 return;
780 }
781 #endif
782
783 resizeGenerations();
784
785 nonmovingPrepareMark();
786
787 // N.B. These should have been cleared at the end of the last sweep.
788 ASSERT(nonmoving_marked_large_objects == NULL);
789 ASSERT(n_nonmoving_marked_large_blocks == 0);
790
791 MarkQueue *mark_queue = stgMallocBytes(sizeof(MarkQueue), "mark queue");
792 initMarkQueue(mark_queue);
793 current_mark_queue = mark_queue;
794
795 // Mark roots
796 markCAFs((evac_fn)markQueueAddRoot, mark_queue);
797 for (unsigned int n = 0; n < n_capabilities; ++n) {
798 markCapability((evac_fn)markQueueAddRoot, mark_queue,
799 capabilities[n], true/*don't mark sparks*/);
800 }
801 markScheduler((evac_fn)markQueueAddRoot, mark_queue);
802 nonmovingMarkWeakPtrList(mark_queue, *dead_weaks);
803 markStablePtrTable((evac_fn)markQueueAddRoot, mark_queue);
804
805 // Mark threads resurrected during moving heap scavenging
806 for (StgTSO *tso = *resurrected_threads; tso != END_TSO_QUEUE; tso = tso->global_link) {
807 markQueuePushClosure_(mark_queue, (StgClosure*)tso);
808 }
809
810 // Roots marked, mark threads and weak pointers
811
812 // At this point all threads are moved to threads list (from old_threads)
813 // and all weaks are moved to weak_ptr_list (from old_weak_ptr_list) by
814 // the previous scavenge step, so we need to move them to "old" lists
815 // again.
816
817 // Fine to override old_threads because any live or resurrected threads are
818 // moved to threads or resurrected_threads lists.
819 ASSERT(oldest_gen->old_threads == END_TSO_QUEUE);
820 ASSERT(nonmoving_old_threads == END_TSO_QUEUE);
821 nonmoving_old_threads = oldest_gen->threads;
822 oldest_gen->threads = END_TSO_QUEUE;
823
824 // Make sure we don't lose any weak ptrs here. Weaks in old_weak_ptr_list
825 // will either be moved to `dead_weaks` (if dead) or `weak_ptr_list` (if
826 // alive).
827 ASSERT(oldest_gen->old_weak_ptr_list == NULL);
828 ASSERT(nonmoving_old_weak_ptr_list == NULL);
829 nonmoving_old_weak_ptr_list = oldest_gen->weak_ptr_list;
830 oldest_gen->weak_ptr_list = NULL;
831
832 // We are now safe to start concurrent marking
833
834 // Note that in concurrent mark we can't use dead_weaks and
835 // resurrected_threads from the preparation to add new weaks and threads as
836 // that would cause races between minor collection and mark. So we only pass
837 // those lists to mark function in sequential case. In concurrent case we
838 // allocate fresh lists.
839
840 #if defined(THREADED_RTS)
841 // If we're interrupting or shutting down, do not let this capability go and
842 // run a STW collection. Reason: we won't be able to acquire this capability
843 // again for the sync if we let it go, because it'll immediately start doing
844 // a major GC, becuase that's what we do when exiting scheduler (see
845 // exitScheduler()).
846 if (sched_state == SCHED_RUNNING) {
847 concurrent_coll_running = true;
848 nonmoving_write_barrier_enabled = true;
849 debugTrace(DEBUG_nonmoving_gc, "Starting concurrent mark thread");
850 createOSThread(&mark_thread, "non-moving mark thread",
851 nonmovingConcurrentMark, mark_queue);
852 } else {
853 nonmovingConcurrentMark(mark_queue);
854 }
855 #else
856 // Use the weak and thread lists from the preparation for any new weaks and
857 // threads found to be dead in mark.
858 nonmovingMark_(mark_queue, dead_weaks, resurrected_threads);
859 #endif
860 }
861
862 /* Mark mark queue, threads, and weak pointers until no more weaks have been
863 * resuscitated
864 */
865 static void nonmovingMarkThreadsWeaks(MarkQueue *mark_queue)
866 {
867 while (true) {
868 // Propagate marks
869 nonmovingMark(mark_queue);
870
871 // Tidy threads and weaks
872 nonmovingTidyThreads();
873
874 if (! nonmovingTidyWeaks(mark_queue))
875 return;
876 }
877 }
878
879 #if defined(THREADED_RTS)
880 static void* nonmovingConcurrentMark(void *data)
881 {
882 MarkQueue *mark_queue = (MarkQueue*)data;
883 StgWeak *dead_weaks = NULL;
884 StgTSO *resurrected_threads = (StgTSO*)&stg_END_TSO_QUEUE_closure;
885 nonmovingMark_(mark_queue, &dead_weaks, &resurrected_threads);
886 return NULL;
887 }
888
889 // TODO: Not sure where to put this function.
890 // Append w2 to the end of w1.
891 static void appendWeakList( StgWeak **w1, StgWeak *w2 )
892 {
893 while (*w1) {
894 w1 = &(*w1)->link;
895 }
896 *w1 = w2;
897 }
898 #endif
899
900 static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO **resurrected_threads)
901 {
902 ACQUIRE_LOCK(&nonmoving_collection_mutex);
903 debugTrace(DEBUG_nonmoving_gc, "Starting mark...");
904 stat_startNonmovingGc();
905
906 // Do concurrent marking; most of the heap will get marked here.
907 nonmovingMarkThreadsWeaks(mark_queue);
908
909 #if defined(THREADED_RTS)
910 Task *task = newBoundTask();
911
912 // If at this point if we've decided to exit then just return
913 if (sched_state > SCHED_RUNNING) {
914 // Note that we break our invariants here and leave segments in
915 // nonmovingHeap.sweep_list, don't free nonmoving_large_objects etc.
916 // However because we won't be running mark-sweep in the final GC this
917 // is OK.
918
919 // This is a RTS shutdown so we need to move our copy (snapshot) of
920 // weaks (nonmoving_old_weak_ptr_list and nonmoving_weak_ptr_list) to
921 // oldest_gen->threads to be able to run C finalizers in hs_exit_. Note
922 // that there may be more weaks added to oldest_gen->threads since we
923 // started mark, so we need to append our list to the tail of
924 // oldest_gen->threads.
925 appendWeakList(&nonmoving_old_weak_ptr_list, nonmoving_weak_ptr_list);
926 appendWeakList(&oldest_gen->weak_ptr_list, nonmoving_old_weak_ptr_list);
927 // These lists won't be used again so this is not necessary, but still
928 nonmoving_old_weak_ptr_list = NULL;
929 nonmoving_weak_ptr_list = NULL;
930
931 goto finish;
932 }
933
934 // We're still running, request a sync
935 nonmovingBeginFlush(task);
936
937 bool all_caps_syncd;
938 do {
939 all_caps_syncd = nonmovingWaitForFlush();
940 nonmovingMarkThreadsWeaks(mark_queue);
941 } while (!all_caps_syncd);
942 #endif
943
944 nonmovingResurrectThreads(mark_queue, resurrected_threads);
945
946 // No more resurrecting threads after this point
947
948 // Do last marking of weak pointers
949 while (true) {
950 // Propagate marks
951 nonmovingMark(mark_queue);
952
953 if (!nonmovingTidyWeaks(mark_queue))
954 break;
955 }
956
957 nonmovingMarkDeadWeaks(mark_queue, dead_weaks);
958
959 // Propagate marks
960 nonmovingMark(mark_queue);
961
962 // Now remove all dead objects from the mut_list to ensure that a younger
963 // generation collection doesn't attempt to look at them after we've swept.
964 nonmovingSweepMutLists();
965
966 debugTrace(DEBUG_nonmoving_gc,
967 "Done marking, resurrecting threads before releasing capabilities");
968
969
970 // Schedule finalizers and resurrect threads
971 #if defined(THREADED_RTS)
972 // Just pick a random capability. Not sure if this is a good idea -- we use
973 // only one capability for all finalizers.
974 scheduleFinalizers(capabilities[0], *dead_weaks);
975 // Note that this mutates heap and causes running write barriers.
976 // See Note [Unintentional marking in resurrectThreads] in NonMovingMark.c
977 // for how we deal with this.
978 resurrectThreads(*resurrected_threads);
979 #endif
980
981 #if defined(DEBUG)
982 // Zap CAFs that we will sweep
983 nonmovingGcCafs();
984 #endif
985
986 ASSERT(mark_queue->top->head == 0);
987 ASSERT(mark_queue->blocks->link == NULL);
988
989 // Update oldest_gen thread and weak lists
990 // Note that we need to append these lists as a concurrent minor GC may have
991 // added stuff to them while we're doing mark-sweep concurrently
992 {
993 StgTSO **threads = &oldest_gen->threads;
994 while (*threads != END_TSO_QUEUE) {
995 threads = &(*threads)->global_link;
996 }
997 *threads = nonmoving_threads;
998 nonmoving_threads = END_TSO_QUEUE;
999 nonmoving_old_threads = END_TSO_QUEUE;
1000 }
1001
1002 {
1003 StgWeak **weaks = &oldest_gen->weak_ptr_list;
1004 while (*weaks) {
1005 weaks = &(*weaks)->link;
1006 }
1007 *weaks = nonmoving_weak_ptr_list;
1008 nonmoving_weak_ptr_list = NULL;
1009 nonmoving_old_weak_ptr_list = NULL;
1010 }
1011
1012 // Everything has been marked; allow the mutators to proceed
1013 #if defined(THREADED_RTS)
1014 nonmoving_write_barrier_enabled = false;
1015 nonmovingFinishFlush(task);
1016 #endif
1017
1018 current_mark_queue = NULL;
1019 freeMarkQueue(mark_queue);
1020 stgFree(mark_queue);
1021
1022 oldest_gen->live_estimate = nonmoving_live_words;
1023 oldest_gen->n_old_blocks = 0;
1024 resizeGenerations();
1025
1026 /****************************************************
1027 * Sweep
1028 ****************************************************/
1029
1030 traceConcSweepBegin();
1031
1032 // Because we can't mark large object blocks (no room for mark bit) we
1033 // collect them in a map in mark_queue and we pass it here to sweep large
1034 // objects
1035 nonmovingSweepLargeObjects();
1036 nonmovingSweepStableNameTable();
1037
1038 nonmovingSweep();
1039 ASSERT(nonmovingHeap.sweep_list == NULL);
1040 debugTrace(DEBUG_nonmoving_gc, "Finished sweeping.");
1041 traceConcSweepEnd();
1042 #if defined(DEBUG)
1043 if (RtsFlags.DebugFlags.nonmoving_gc)
1044 nonmovingPrintAllocatorCensus();
1045 #endif
1046
1047 // TODO: Remainder of things done by GarbageCollect (update stats)
1048
1049 #if defined(THREADED_RTS)
1050 finish:
1051 boundTaskExiting(task);
1052
1053 // We are done...
1054 mark_thread = 0;
1055 stat_endNonmovingGc();
1056
1057 // Signal that the concurrent collection is finished, allowing the next
1058 // non-moving collection to proceed
1059 concurrent_coll_running = false;
1060 signalCondition(&concurrent_coll_finished);
1061 RELEASE_LOCK(&nonmoving_collection_mutex);
1062 #endif
1063 }
1064
1065 #if defined(DEBUG)
1066
1067 // Use this with caution: this doesn't work correctly during scavenge phase
1068 // when we're doing parallel scavenging. Use it in mark phase or later (where
1069 // we don't allocate more anymore).
1070 void assert_in_nonmoving_heap(StgPtr p)
1071 {
1072 if (!HEAP_ALLOCED_GC(p))
1073 return;
1074
1075 bdescr *bd = Bdescr(p);
1076 if (bd->flags & BF_LARGE) {
1077 // It should be in a capability (if it's not filled yet) or in non-moving heap
1078 for (uint32_t cap = 0; cap < n_capabilities; ++cap) {
1079 if (bd == capabilities[cap]->pinned_object_block) {
1080 return;
1081 }
1082 }
1083 ASSERT(bd->flags & BF_NONMOVING);
1084 return;
1085 }
1086
1087 // Search snapshot segments
1088 for (struct NonmovingSegment *seg = nonmovingHeap.sweep_list; seg; seg = seg->link) {
1089 if (p >= (P_)seg && p < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1090 return;
1091 }
1092 }
1093
1094 for (int alloca_idx = 0; alloca_idx < NONMOVING_ALLOCA_CNT; ++alloca_idx) {
1095 struct NonmovingAllocator *alloca = nonmovingHeap.allocators[alloca_idx];
1096 // Search current segments
1097 for (uint32_t cap_idx = 0; cap_idx < n_capabilities; ++cap_idx) {
1098 struct NonmovingSegment *seg = alloca->current[cap_idx];
1099 if (p >= (P_)seg && p < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1100 return;
1101 }
1102 }
1103
1104 // Search active segments
1105 int seg_idx = 0;
1106 struct NonmovingSegment *seg = alloca->active;
1107 while (seg) {
1108 if (p >= (P_)seg && p < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1109 return;
1110 }
1111 seg_idx++;
1112 seg = seg->link;
1113 }
1114
1115 // Search filled segments
1116 seg_idx = 0;
1117 seg = alloca->filled;
1118 while (seg) {
1119 if (p >= (P_)seg && p < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1120 return;
1121 }
1122 seg_idx++;
1123 seg = seg->link;
1124 }
1125 }
1126
1127 // We don't search free segments as they're unused
1128
1129 barf("%p is not in nonmoving heap\n", (void*)p);
1130 }
1131
1132 void nonmovingPrintSegment(struct NonmovingSegment *seg)
1133 {
1134 int num_blocks = nonmovingSegmentBlockCount(seg);
1135
1136 debugBelch("Segment with %d blocks of size 2^%d (%d bytes, %lu words, scan: %p)\n",
1137 num_blocks,
1138 seg->block_size,
1139 1 << seg->block_size,
1140 ROUNDUP_BYTES_TO_WDS(1 << seg->block_size),
1141 (void*)Bdescr((P_)seg)->u.scan);
1142
1143 for (nonmoving_block_idx p_idx = 0; p_idx < seg->next_free; ++p_idx) {
1144 StgClosure *p = (StgClosure*)nonmovingSegmentGetBlock(seg, p_idx);
1145 if (nonmovingGetMark(seg, p_idx) != 0) {
1146 debugBelch("%d (%p)* :\t", p_idx, (void*)p);
1147 } else {
1148 debugBelch("%d (%p) :\t", p_idx, (void*)p);
1149 }
1150 printClosure(p);
1151 }
1152
1153 debugBelch("End of segment\n\n");
1154 }
1155
1156 void nonmovingPrintAllocator(struct NonmovingAllocator *alloc)
1157 {
1158 debugBelch("Allocator at %p\n", (void*)alloc);
1159 debugBelch("Filled segments:\n");
1160 for (struct NonmovingSegment *seg = alloc->filled; seg != NULL; seg = seg->link) {
1161 debugBelch("%p ", (void*)seg);
1162 }
1163 debugBelch("\nActive segments:\n");
1164 for (struct NonmovingSegment *seg = alloc->active; seg != NULL; seg = seg->link) {
1165 debugBelch("%p ", (void*)seg);
1166 }
1167 debugBelch("\nCurrent segments:\n");
1168 for (uint32_t i = 0; i < n_capabilities; ++i) {
1169 debugBelch("%p ", alloc->current[i]);
1170 }
1171 debugBelch("\n");
1172 }
1173
1174 void locate_object(P_ obj)
1175 {
1176 // Search allocators
1177 for (int alloca_idx = 0; alloca_idx < NONMOVING_ALLOCA_CNT; ++alloca_idx) {
1178 struct NonmovingAllocator *alloca = nonmovingHeap.allocators[alloca_idx];
1179 for (uint32_t cap = 0; cap < n_capabilities; ++cap) {
1180 struct NonmovingSegment *seg = alloca->current[cap];
1181 if (obj >= (P_)seg && obj < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1182 debugBelch("%p is in current segment of capability %d of allocator %d at %p\n", obj, cap, alloca_idx, (void*)seg);
1183 return;
1184 }
1185 }
1186 int seg_idx = 0;
1187 struct NonmovingSegment *seg = alloca->active;
1188 while (seg) {
1189 if (obj >= (P_)seg && obj < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1190 debugBelch("%p is in active segment %d of allocator %d at %p\n", obj, seg_idx, alloca_idx, (void*)seg);
1191 return;
1192 }
1193 seg_idx++;
1194 seg = seg->link;
1195 }
1196
1197 seg_idx = 0;
1198 seg = alloca->filled;
1199 while (seg) {
1200 if (obj >= (P_)seg && obj < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1201 debugBelch("%p is in filled segment %d of allocator %d at %p\n", obj, seg_idx, alloca_idx, (void*)seg);
1202 return;
1203 }
1204 seg_idx++;
1205 seg = seg->link;
1206 }
1207 }
1208
1209 struct NonmovingSegment *seg = nonmovingHeap.free;
1210 int seg_idx = 0;
1211 while (seg) {
1212 if (obj >= (P_)seg && obj < (((P_)seg) + NONMOVING_SEGMENT_SIZE_W)) {
1213 debugBelch("%p is in free segment %d at %p\n", obj, seg_idx, (void*)seg);
1214 return;
1215 }
1216 seg_idx++;
1217 seg = seg->link;
1218 }
1219
1220 // Search nurseries
1221 for (uint32_t nursery_idx = 0; nursery_idx < n_nurseries; ++nursery_idx) {
1222 for (bdescr* nursery_block = nurseries[nursery_idx].blocks; nursery_block; nursery_block = nursery_block->link) {
1223 if (obj >= nursery_block->start && obj <= nursery_block->start + nursery_block->blocks*BLOCK_SIZE_W) {
1224 debugBelch("%p is in nursery %d\n", obj, nursery_idx);
1225 return;
1226 }
1227 }
1228 }
1229
1230 // Search generations
1231 for (uint32_t g = 0; g < RtsFlags.GcFlags.generations - 1; ++g) {
1232 generation *gen = &generations[g];
1233 for (bdescr *blk = gen->blocks; blk; blk = blk->link) {
1234 if (obj >= blk->start && obj < blk->free) {
1235 debugBelch("%p is in generation %" FMT_Word32 " blocks\n", obj, g);
1236 return;
1237 }
1238 }
1239 for (bdescr *blk = gen->old_blocks; blk; blk = blk->link) {
1240 if (obj >= blk->start && obj < blk->free) {
1241 debugBelch("%p is in generation %" FMT_Word32 " old blocks\n", obj, g);
1242 return;
1243 }
1244 }
1245 }
1246
1247 // Search large objects
1248 for (uint32_t g = 0; g < RtsFlags.GcFlags.generations - 1; ++g) {
1249 generation *gen = &generations[g];
1250 for (bdescr *large_block = gen->large_objects; large_block; large_block = large_block->link) {
1251 if ((P_)large_block->start == obj) {
1252 debugBelch("%p is in large blocks of generation %d\n", obj, g);
1253 return;
1254 }
1255 }
1256 }
1257
1258 for (bdescr *large_block = nonmoving_large_objects; large_block; large_block = large_block->link) {
1259 if ((P_)large_block->start == obj) {
1260 debugBelch("%p is in nonmoving_large_objects\n", obj);
1261 return;
1262 }
1263 }
1264
1265 for (bdescr *large_block = nonmoving_marked_large_objects; large_block; large_block = large_block->link) {
1266 if ((P_)large_block->start == obj) {
1267 debugBelch("%p is in nonmoving_marked_large_objects\n", obj);
1268 return;
1269 }
1270 }
1271
1272 // Search workspaces FIXME only works in non-threaded runtime
1273 #if !defined(THREADED_RTS)
1274 for (uint32_t g = 0; g < RtsFlags.GcFlags.generations - 1; ++ g) {
1275 gen_workspace *ws = &gct->gens[g];
1276 for (bdescr *blk = ws->todo_bd; blk; blk = blk->link) {
1277 if (obj >= blk->start && obj < blk->free) {
1278 debugBelch("%p is in generation %" FMT_Word32 " todo bds\n", obj, g);
1279 return;
1280 }
1281 }
1282 for (bdescr *blk = ws->scavd_list; blk; blk = blk->link) {
1283 if (obj >= blk->start && obj < blk->free) {
1284 debugBelch("%p is in generation %" FMT_Word32 " scavd bds\n", obj, g);
1285 return;
1286 }
1287 }
1288 for (bdescr *blk = ws->todo_large_objects; blk; blk = blk->link) {
1289 if (obj >= blk->start && obj < blk->free) {
1290 debugBelch("%p is in generation %" FMT_Word32 " todo large bds\n", obj, g);
1291 return;
1292 }
1293 }
1294 }
1295 #endif
1296 }
1297
1298 void nonmovingPrintSweepList()
1299 {
1300 debugBelch("==== SWEEP LIST =====\n");
1301 int i = 0;
1302 for (struct NonmovingSegment *seg = nonmovingHeap.sweep_list; seg; seg = seg->link) {
1303 debugBelch("%d: %p\n", i++, (void*)seg);
1304 }
1305 debugBelch("= END OF SWEEP LIST =\n");
1306 }
1307
1308 void check_in_mut_list(StgClosure *p)
1309 {
1310 for (uint32_t cap_n = 0; cap_n < n_capabilities; ++cap_n) {
1311 for (bdescr *bd = capabilities[cap_n]->mut_lists[oldest_gen->no]; bd; bd = bd->link) {
1312 for (StgPtr q = bd->start; q < bd->free; ++q) {
1313 if (*((StgPtr**)q) == (StgPtr*)p) {
1314 debugBelch("Object is in mut list of cap %d: %p\n", cap_n, capabilities[cap_n]->mut_lists[oldest_gen->no]);
1315 return;
1316 }
1317 }
1318 }
1319 }
1320
1321 debugBelch("Object is not in a mut list\n");
1322 }
1323
1324 void print_block_list(bdescr* bd)
1325 {
1326 while (bd) {
1327 debugBelch("%p, ", (void*)bd);
1328 bd = bd->link;
1329 }
1330 debugBelch("\n");
1331 }
1332
1333 void print_thread_list(StgTSO* tso)
1334 {
1335 while (tso != END_TSO_QUEUE) {
1336 printClosure((StgClosure*)tso);
1337 tso = tso->global_link;
1338 }
1339 }
1340
1341 #endif