81a41182b19fc00cf8b178f3472fe7775b1db6d8
[ghc.git] / rts / sm / Sweep.c
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team 2008
4 *
5 * Simple mark/sweep, collecting whole blocks.
6 *
7 * Documentation on the architecture of the Garbage Collector can be
8 * found in the online commentary:
9 *
10 * http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
11 *
12 * ---------------------------------------------------------------------------*/
13
14 #include "PosixSource.h"
15 #include "Rts.h"
16
17 #include "BlockAlloc.h"
18 #include "Sweep.h"
19 #include "Trace.h"
20
21 void
22 sweep(generation *gen)
23 {
24 bdescr *bd, *prev, *next;
25 nat i;
26 nat freed, resid, fragd, blocks, live;
27
28 ASSERT(countBlocks(gen->old_blocks) == gen->n_old_blocks);
29
30 live = 0; // estimate of live data in this gen
31 freed = 0;
32 fragd = 0;
33 blocks = 0;
34 prev = NULL;
35 for (bd = gen->old_blocks; bd != NULL; bd = next)
36 {
37 next = bd->link;
38
39 if (!(bd->flags & BF_MARKED)) {
40 prev = bd;
41 continue;
42 }
43
44 blocks++;
45 resid = 0;
46 for (i = 0; i < BLOCK_SIZE_W / BITS_IN(W_); i++)
47 {
48 if (bd->u.bitmap[i] != 0) resid++;
49 }
50 live += resid * BITS_IN(W_);
51
52 if (resid == 0)
53 {
54 freed++;
55 gen->n_old_blocks--;
56 if (prev == NULL) {
57 gen->old_blocks = next;
58 } else {
59 prev->link = next;
60 }
61 freeGroup(bd);
62 }
63 else
64 {
65 prev = bd;
66 if (resid < (BLOCK_SIZE_W * 3) / (BITS_IN(W_) * 4)) {
67 fragd++;
68 bd->flags |= BF_FRAGMENTED;
69 }
70
71 bd->flags |= BF_SWEPT;
72 }
73 }
74
75 gen->live_estimate = live;
76
77 debugTrace(DEBUG_gc, "sweeping: %d blocks, %d were copied, %d freed (%d%%), %d are fragmented, live estimate: %ld%%",
78 gen->n_old_blocks + freed,
79 gen->n_old_blocks - blocks + freed,
80 freed,
81 blocks == 0 ? 0 : (freed * 100) / blocks,
82 fragd,
83 (unsigned long)((blocks - freed) == 0 ? 0 : ((live / BLOCK_SIZE_W) * 100) / (blocks - freed)));
84
85 ASSERT(countBlocks(gen->old_blocks) == gen->n_old_blocks);
86 }