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 "Rts.h"
  15 #include "Sweep.h"
  16 #include "Block.h"
  17 #include "Trace.h"
  18
  19 void
  20 sweep(step *step)
  21 {
  22     bdescr *bd, *prev, *next;
  23     nat i;
  24     nat freed, resid, fragd, blocks, live;
  25
  26     ASSERT(countBlocks(step->old_blocks) == step->n_old_blocks);
  27
  28     live = 0; // estimate of live data in this gen
  29     freed = 0;
  30     fragd = 0;
  31     blocks = 0;
  32     prev = NULL;
  33     for (bd = step->old_blocks; bd != NULL; bd = next)
  34     {
  35         next = bd->link;
  36
  37         if (!(bd->flags & BF_MARKED)) {
  38             prev = bd;
  39             continue;
  40         }
  41
  42         blocks++;
  43         resid = 0;
  44         for (i = 0; i < BLOCK_SIZE_W / BITS_IN(W_); i++)
  45         {
  46             if (bd->u.bitmap[i] != 0) resid++;
  47         }
  48         live += resid * BITS_IN(W_);
  49
  50         if (resid == 0)
  51         {
  52             freed++;
  53             step->n_old_blocks--;
  54             if (prev == NULL) {
  55                 step->old_blocks = next;
  56             } else {
  57                 prev->link = next;
  58             }
  59             freeGroup(bd);
  60         }
  61         else
  62         {
  63             prev = bd;
  64             if (resid < (BLOCK_SIZE_W * 3) / (BITS_IN(W_) * 4)) {
  65                 fragd++;
  66                 bd->flags |= BF_FRAGMENTED;
  67             }
  68         }
  69     }
  70
  71     step->live_estimate = live;
  72
  73     trace(DEBUG_gc|TRACE_gc, "sweeping: %d blocks, %d were copied, %d freed (%d%%), %d are fragmented, live estimate: %ld%%",
  74           step->n_old_blocks + freed,
  75           step->n_old_blocks - blocks + freed,
  76           freed,
  77           blocks == 0 ? 0 : (freed * 100) / blocks,
  78           fragd,
  79           (unsigned long)((blocks - freed) == 0 ? 0 : ((live / BLOCK_SIZE_W) * 100) / (blocks - freed)));
  80
  81     ASSERT(countBlocks(step->old_blocks) == step->n_old_blocks);
  82 }