summaryrefslogtreecommitdiff
path: root/rts/sm/NonMovingSweep.c
blob: 1a7c97b7e68ca4b56a8a7d1b717cf97c935b5ef5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team, 1998-2018
 *
 * Non-moving garbage collector and allocator: Sweep phase
 *
 * ---------------------------------------------------------------------------*/

#include "Rts.h"
#include "NonMovingSweep.h"
#include "NonMoving.h"
#include "NonMovingMark.h" // for nonmovingIsAlive
#include "Capability.h"
#include "GCThread.h" // for GCUtils.h
#include "GCUtils.h"
#include "Storage.h"
#include "Trace.h"
#include "StableName.h"
#include "CNF.h" // compactFree

// On which list should a particular segment be placed?
enum SweepResult {
    SEGMENT_FREE,     // segment is empty: place on free list
    SEGMENT_PARTIAL,  // segment is partially filled: place on active list
    SEGMENT_FILLED    // segment is full: place on filled list
};

// Determine which list a marked segment should be placed on and initialize
// next_free indices as appropriate. Additionally, we must clear the mark
// bitmap entries associated with swept blocks.
GNUC_ATTR_HOT static enum SweepResult
nonmovingSweepSegment(struct NonmovingSegment *seg)
{
    const nonmoving_block_idx blk_cnt = nonmovingSegmentBlockCount(seg);
    bool found_free = false;
    bool found_live = false;

    for (nonmoving_block_idx i = 0; i < blk_cnt; ++i)
    {
        if (seg->bitmap[i] == nonmovingMarkEpoch) {
            found_live = true;
        } else if (!found_free) {
            // This is the first free block we've found; set next_free,
            // next_free_snap, and the scan pointer.
            found_free = true;
            seg->next_free = i;
            nonmovingSegmentInfo(seg)->next_free_snap = i;
            Bdescr((P_)seg)->u.scan = (P_)nonmovingSegmentGetBlock(seg, i);
            seg->bitmap[i] = 0;
        } else {
            seg->bitmap[i] = 0;
        }

        if (found_free && found_live) {
            // zero the remaining dead object's mark bits
            for (; i < nonmovingSegmentBlockCount(seg); ++i) {
                if (seg->bitmap[i] != nonmovingMarkEpoch) {
                    seg->bitmap[i] = 0;
                }
            }
            return SEGMENT_PARTIAL;
        }
    }

    if (found_live) {
        return SEGMENT_FILLED;
    } else {
        ASSERT(seg->next_free == 0);
        ASSERT(nonmovingSegmentInfo(seg)->next_free_snap == 0);
        return SEGMENT_FREE;
    }
}

#if defined(DEBUG)

void nonmovingGcCafs()
{
    uint32_t i = 0;
    StgIndStatic *next;

    for (StgIndStatic *caf = debug_caf_list_snapshot;
         caf != (StgIndStatic*) END_OF_CAF_LIST;
         caf = next)
    {
        next = (StgIndStatic*)caf->saved_info;

        const StgInfoTable *info = get_itbl((StgClosure*)caf);
        ASSERT(info->type == IND_STATIC);

        StgWord flag = ((StgWord) caf->static_link) & STATIC_BITS;
        if (flag != 0 && flag != static_flag) {
            debugTrace(DEBUG_gccafs, "CAF gc'd at 0x%p", caf);
            SET_INFO((StgClosure*)caf, &stg_GCD_CAF_info); // stub it
        } else {
            // CAF is alive, move it back to the debug_caf_list
            ++i;
            debugTrace(DEBUG_gccafs, "CAF alive at 0x%p", caf);
            ACQUIRE_SM_LOCK; // debug_caf_list is global, locked by sm_mutex
            caf->saved_info = (const StgInfoTable*)debug_caf_list;
            debug_caf_list = caf;
            RELEASE_SM_LOCK;
        }
    }

    debugTrace(DEBUG_gccafs, "%d CAFs live", i);
    debug_caf_list_snapshot = (StgIndStatic*)END_OF_CAF_LIST;
}

static void
clear_segment(struct NonmovingSegment* seg)
{
    size_t end = ((size_t)seg) + NONMOVING_SEGMENT_SIZE;
    memset(&seg->bitmap, 0, end - (size_t)&seg->bitmap);
}

static void
clear_segment_free_blocks(struct NonmovingSegment* seg)
{
    unsigned int block_size = nonmovingSegmentBlockSize(seg);
    for (unsigned int p_idx = 0; p_idx < nonmovingSegmentBlockCount(seg); ++p_idx) {
        // after mark, so bit not set == dead
        if (nonmovingGetMark(seg, p_idx) == 0) {
            memset(nonmovingSegmentGetBlock(seg, p_idx), 0, block_size);
        }
    }
}

#endif

GNUC_ATTR_HOT void nonmovingSweep(void)
{
    while (nonmovingHeap.sweep_list) {
        struct NonmovingSegment *seg = nonmovingHeap.sweep_list;

        // Pushing the segment to one of the free/active/filled segments
        // updates the link field, so update sweep_list here
        nonmovingHeap.sweep_list = seg->link;

        enum SweepResult ret = nonmovingSweepSegment(seg);

        switch (ret) {
        case SEGMENT_FREE:
            IF_DEBUG(sanity, clear_segment(seg));
            nonmovingPushFreeSegment(seg);
            break;
        case SEGMENT_PARTIAL:
            IF_DEBUG(sanity, clear_segment_free_blocks(seg));
            nonmovingPushActiveSegment(seg);
            break;
        case SEGMENT_FILLED:
            nonmovingPushFilledSegment(seg);
            break;
        default:
            barf("nonmovingSweep: weird sweep return: %d\n", ret);
        }
    }
}

/* Must a closure remain on the mutable list?
 *
 * A closure must remain if any of the following applies:
 *
 *  1. it contains references to a younger generation
 *  2. it's a mutable closure (e.g. mutable array or MUT_PRIM)
 */
static bool is_closure_clean(StgClosure *p)
{
    const StgInfoTable *info = get_itbl(p);

#define CLEAN(ptr) (!HEAP_ALLOCED((StgClosure*) ptr) || Bdescr((StgPtr) ptr)->gen == oldest_gen)

    switch (info->type) {
    case MVAR_CLEAN:
    case MVAR_DIRTY:
    {
        StgMVar *mvar = ((StgMVar *)p);
        if (!CLEAN(mvar->head)) goto dirty_MVAR;
        if (!CLEAN(mvar->tail)) goto dirty_MVAR;
        if (!CLEAN(mvar->value)) goto dirty_MVAR;
        mvar->header.info = &stg_MVAR_CLEAN_info;
        return true;

dirty_MVAR:
        mvar->header.info = &stg_MVAR_DIRTY_info;
        return false;
    }

    case TVAR:
    {
        StgTVar *tvar = ((StgTVar *)p);
        if (!CLEAN(tvar->current_value)) goto dirty_TVAR;
        if (!CLEAN(tvar->first_watch_queue_entry)) goto dirty_TVAR;
        tvar->header.info = &stg_TVAR_CLEAN_info;
        return true;

dirty_TVAR:
        tvar->header.info = &stg_TVAR_DIRTY_info;
        return false;
    }

    case THUNK:
    case THUNK_1_0:
    case THUNK_0_1:
    case THUNK_1_1:
    case THUNK_0_2:
    case THUNK_2_0:
    {
        StgPtr end = (StgPtr)((StgThunk *)p)->payload + info->layout.payload.ptrs;
        for (StgPtr q = (StgPtr)((StgThunk *)p)->payload; q < end; q++) {
            if (!CLEAN(*q)) return false;
        }
        return true;
    }

    case FUN:
    case FUN_1_0:                       // hardly worth specialising these guys
    case FUN_0_1:
    case FUN_1_1:
    case FUN_0_2:
    case FUN_2_0:
    case CONSTR:
    case CONSTR_NOCAF:
    case CONSTR_1_0:
    case CONSTR_0_1:
    case CONSTR_1_1:
    case CONSTR_0_2:
    case CONSTR_2_0:
    case PRIM:
    {
        StgPtr end = (StgPtr)((StgClosure *)p)->payload + info->layout.payload.ptrs;
        for (StgPtr q = (StgPtr)((StgClosure *)p)->payload; q < end; q++) {
            if (!CLEAN(*q)) return false;
        }
        return true;
    }

    case WEAK:
        return false; // TODO

    case MUT_VAR_CLEAN:
    case MUT_VAR_DIRTY:
        if (!CLEAN(((StgMutVar *)p)->var)) {
            p->header.info = &stg_MUT_VAR_DIRTY_info;
            return false;
        } else {
            p->header.info = &stg_MUT_VAR_CLEAN_info;
            return true;
        }

    case BLOCKING_QUEUE:
    {
        StgBlockingQueue *bq = (StgBlockingQueue *)p;

        if (!CLEAN(bq->bh)) goto dirty_BLOCKING_QUEUE;
        if (!CLEAN(bq->owner)) goto dirty_BLOCKING_QUEUE;
        if (!CLEAN(bq->queue)) goto dirty_BLOCKING_QUEUE;
        if (!CLEAN(bq->link)) goto dirty_BLOCKING_QUEUE;
        bq->header.info = &stg_BLOCKING_QUEUE_CLEAN_info;
        return true;

dirty_BLOCKING_QUEUE:
        bq->header.info = &stg_BLOCKING_QUEUE_DIRTY_info;
        return false;
    }

    case THUNK_SELECTOR:
        return CLEAN(((StgSelector *) p)->selectee);

    case ARR_WORDS:
        return true;

    default:
        // TODO: the rest
        return false;
    }
#undef CLEAN
}

/* N.B. This happens during the pause so we own all capabilities. */
void nonmovingSweepMutLists()
{
    for (uint32_t n = 0; n < n_capabilities; n++) {
        Capability *cap = capabilities[n];
        bdescr *old_mut_list = cap->mut_lists[oldest_gen->no];
        cap->mut_lists[oldest_gen->no] = allocBlockOnNode_lock(cap->node);
        for (bdescr *bd = old_mut_list; bd; bd = bd->link) {
            for (StgPtr p = bd->start; p < bd->free; p++) {
                StgClosure **q = (StgClosure**)p;
                if (nonmovingIsAlive(*q) && !is_closure_clean(*q)) {
                    recordMutableCap(*q, cap, oldest_gen->no);
                }
            }
        }
        freeChain_lock(old_mut_list);
    }
}

/* A variant of freeChain_lock that will only hold the lock for at most max_dur
 * freed blocks to ensure that we don't starve other lock users (e.g. the
 * mutator).
 */
static void freeChain_lock_max(bdescr *bd, int max_dur)
{
  ACQUIRE_SM_LOCK;
  bdescr *next_bd;
  int i = 0;
  while (bd != NULL) {
    next_bd = bd->link;
    freeGroup(bd);
    bd = next_bd;
    if (i == max_dur) {
#if defined(THREADED_RTS)
        RELEASE_SM_LOCK;
        yieldThread();
        ACQUIRE_SM_LOCK;
#endif
        i = 0;
    }
    i++;
  }
  RELEASE_SM_LOCK;
}

void nonmovingSweepLargeObjects()
{
    freeChain_lock_max(nonmoving_large_objects, 10000);
    nonmoving_large_objects = nonmoving_marked_large_objects;
    n_nonmoving_large_blocks = n_nonmoving_marked_large_blocks;
    nonmoving_marked_large_objects = NULL;
    n_nonmoving_marked_large_blocks = 0;
}

void nonmovingSweepCompactObjects()
{
    bdescr *next;
    ACQUIRE_SM_LOCK;
    for (bdescr *bd = nonmoving_compact_objects; bd; bd = next) {
        next = bd->link;
        compactFree(((StgCompactNFDataBlock*)bd->start)->owner);
    }
    RELEASE_SM_LOCK;
    nonmoving_compact_objects = nonmoving_marked_compact_objects;
    n_nonmoving_compact_blocks = n_nonmoving_marked_compact_blocks;
    nonmoving_marked_compact_objects = NULL;
    n_nonmoving_marked_compact_blocks = 0;
}

// Helper for nonmovingSweepStableNameTable. Essentially nonmovingIsAlive,
// but works when the object died in moving heap, see
// nonmovingSweepStableNameTable
static bool is_alive(StgClosure *p)
{
    if (!HEAP_ALLOCED_GC(p)) {
        return true;
    }

    if (nonmovingClosureBeingSwept(p)) {
        return nonmovingIsAlive(p);
    } else {
        // We don't want to sweep any stable names which weren't in the
        // set of segments that we swept.
        // See Note [Sweeping stable names in the concurrent collector]
        return true;
    }
}

void nonmovingSweepStableNameTable()
{
    // See comments in gcStableTables

    /* Note [Sweeping stable names in the concurrent collector]
     * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     *
     * When collecting concurrently we need to take care to avoid freeing
     * stable names the we didn't sweep this collection cycle. For instance,
     * consider the following situation:
     *
     *  1. We take a snapshot and start collection
     *  2. A mutator allocates a new object, then makes a stable name for it
     *  3. The mutator performs a minor GC and promotes the new object to the nonmoving heap
     *  4. The GC thread gets to the sweep phase and, when traversing the stable
     *     name table, finds the new object unmarked. It then assumes that the
     *     object is dead and removes the stable name from the stable name table.
     *
     */

    // FIXME: We can't use nonmovingIsAlive here without first using isAlive:
    // a stable name can die during moving heap collection and we can't use
    // nonmovingIsAlive on those objects. Inefficient.

    stableNameLock();
    FOR_EACH_STABLE_NAME(
        p, {
            if (p->sn_obj != NULL) {
                if (!is_alive((StgClosure*)p->sn_obj)) {
                    p->sn_obj = NULL; // Just to make an assertion happy
                    freeSnEntry(p);
                } else if (p->addr != NULL) {
                    if (!is_alive((StgClosure*)p->addr)) {
                        p->addr = NULL;
                    }
                }
            }
        });
    stableNameUnlock();
}