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 }