rts/sm/GCUtils.c

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-2006
   4  *
   5  * Generational garbage collector: utilities
   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 "RtsFlags.h"
  16 #include "Storage.h"
  17 #include "GC.h"
  18 #include "GCUtils.h"
  19 #include "Printer.h"
  20 #include "Trace.h"
  21
  22 #ifdef THREADED_RTS
  23 SpinLock gc_alloc_block_sync;
  24 #endif
  25
  26 bdescr *
  27 allocBlock_sync(void)
  28 {
  29     bdescr *bd;
  30     ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
  31     bd = allocBlock();
  32     RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
  33     return bd;
  34 }
  35
  36 void
  37 freeChain_sync(bdescr *bd)
  38 {
  39     ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
  40     freeChain(bd);
  41     RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
  42 }
  43
  44 /* -----------------------------------------------------------------------------
  45    Workspace utilities
  46    -------------------------------------------------------------------------- */
  47
  48 bdescr *
  49 grab_todo_block (step_workspace *ws)
  50 {
  51     bdescr *bd;
  52     step *stp;
  53
  54     stp = ws->step;
  55     bd = NULL;
  56
  57     if (ws->buffer_todo_bd)
  58     {
  59         bd = ws->buffer_todo_bd;
  60         ASSERT(bd->link == NULL);
  61         ws->buffer_todo_bd = NULL;
  62         return bd;
  63     }
  64
  65     ACQUIRE_SPIN_LOCK(&stp->sync_todo);
  66     if (stp->todos) {
  67         bd = stp->todos;
  68         if (stp->todos == stp->todos_last) {
  69             stp->todos_last = NULL;
  70         }
  71         stp->todos = bd->link;
  72         stp->n_todos--;
  73         bd->link = NULL;
  74     }
  75     RELEASE_SPIN_LOCK(&stp->sync_todo);
  76     return bd;
  77 }
  78
  79 void
  80 push_scanned_block (bdescr *bd, step_workspace *ws)
  81 {
  82     ASSERT(bd != NULL);
  83     ASSERT(bd->link == NULL);
  84     ASSERT(bd->step == ws->step);
  85     ASSERT(bd->u.scan == bd->free);
  86
  87     if (bd->start + BLOCK_SIZE_W - bd->free > WORK_UNIT_WORDS)
  88     {
  89         // a partially full block: put it on the part_list list.
  90         bd->link = ws->part_list;
  91         ws->part_list = bd;
  92         ws->n_part_blocks++;
  93         IF_DEBUG(sanity,
  94                  ASSERT(countBlocks(ws->part_list) == ws->n_part_blocks));
  95     }
  96     else
  97     {
  98         // put the scan block on the ws->scavd_list.
  99         bd->link = ws->scavd_list;
 100         ws->scavd_list = bd;
 101         ws->n_scavd_blocks ++;
 102         IF_DEBUG(sanity,
 103                  ASSERT(countBlocks(ws->scavd_list) == ws->n_scavd_blocks));
 104     }
 105 }
 106
 107 StgPtr
 108 todo_block_full (nat size, step_workspace *ws)
 109 {
 110     bdescr *bd;
 111
 112     bd = ws->todo_bd;
 113
 114     ASSERT(bd != NULL);
 115     ASSERT(bd->link == NULL);
 116     ASSERT(bd->step == ws->step);
 117
 118     // If the global list is not empty, or there's not much work in
 119     // this block to push, and there's enough room in
 120     // this block to evacuate the current object, then just increase
 121     // the limit.
 122     if (ws->step->todos != NULL ||
 123         (ws->todo_free - bd->u.scan < WORK_UNIT_WORDS / 2)) {
 124         if (ws->todo_free + size < bd->start + BLOCK_SIZE_W) {
 125             ws->todo_lim = stg_min(bd->start + BLOCK_SIZE_W,
 126                                    ws->todo_lim + stg_max(WORK_UNIT_WORDS,size));
 127             debugTrace(DEBUG_gc, "increasing limit for %p to %p", bd->start, ws->todo_lim);
 128             return ws->todo_free;
 129         }
 130     }
 131
 132     gct->copied += ws->todo_free - bd->free;
 133     bd->free = ws->todo_free;
 134
 135     ASSERT(bd->u.scan >= bd->start && bd->u.scan <= bd->free);
 136
 137     // If this block is not the scan block, we want to push it out and
 138     // make room for a new todo block.
 139     if (bd != gct->scan_bd)
 140     {
 141         // If this block does not have enough space to allocate the
 142         // current object, but it also doesn't have any work to push, then
 143         // push it on to the scanned list.  It cannot be empty, because
 144         // then there would be enough room to copy the current object.
 145         if (bd->u.scan == bd->free)
 146         {
 147             ASSERT(bd->free != bd->start);
 148             push_scanned_block(bd, ws);
 149         }
 150         // Otherwise, push this block out to the global list.
 151         else
 152         {
 153             step *stp;
 154             stp = ws->step;
 155             trace(TRACE_gc|DEBUG_gc, "push todo block %p (%d words), step %d, n_todos: %d",
 156                   bd->start, bd->free - bd->u.scan, stp->abs_no, stp->n_todos);
 157             // ToDo: use buffer_todo
 158             ACQUIRE_SPIN_LOCK(&stp->sync_todo);
 159             if (stp->todos_last == NULL) {
 160                 stp->todos_last = bd;
 161                 stp->todos = bd;
 162             } else {
 163                 stp->todos_last->link = bd;
 164                 stp->todos_last = bd;
 165             }
 166             stp->n_todos++;
 167             RELEASE_SPIN_LOCK(&stp->sync_todo);
 168         }
 169     }
 170
 171     ws->todo_bd   = NULL;
 172     ws->todo_free = NULL;
 173     ws->todo_lim  = NULL;
 174
 175     alloc_todo_block(ws, size);
 176
 177     return ws->todo_free;
 178 }
 179
 180 StgPtr
 181 alloc_todo_block (step_workspace *ws, nat size)
 182 {
 183     bdescr *bd;
 184
 185     // Grab a part block if we have one, and it has enough room
 186     if (ws->part_list != NULL &&
 187         ws->part_list->start + BLOCK_SIZE_W - ws->part_list->free > (int)size)
 188     {
 189         bd = ws->part_list;
 190         ws->part_list = bd->link;
 191         ws->n_part_blocks--;
 192     }
 193     else
 194     {
 195         bd = allocBlock_sync();
 196         bd->gen_no = ws->step->gen_no;
 197         bd->step = ws->step;
 198         bd->u.scan = bd->start;
 199
 200         // blocks in to-space in generations up to and including N
 201         // get the BF_EVACUATED flag.
 202         if (ws->step->gen_no <= N) {
 203             bd->flags = BF_EVACUATED;
 204         } else {
 205             bd->flags = 0;
 206         }
 207     }
 208
 209     bd->link = NULL;
 210
 211     ws->todo_bd = bd;
 212     ws->todo_free = bd->free;
 213     ws->todo_lim  = stg_min(bd->start + BLOCK_SIZE_W,
 214                             bd->free + stg_max(WORK_UNIT_WORDS,size));
 215
 216     debugTrace(DEBUG_gc, "alloc new todo block %p for step %d",
 217                bd->free, ws->step->abs_no);
 218
 219     return ws->todo_free;
 220 }
 221
 222 /* -----------------------------------------------------------------------------
 223  * Debugging
 224  * -------------------------------------------------------------------------- */
 225
 226 #if DEBUG
 227 void
 228 printMutableList(generation *gen)
 229 {
 230     bdescr *bd;
 231     StgPtr p;
 232
 233     debugBelch("mutable list %p: ", gen->mut_list);
 234
 235     for (bd = gen->mut_list; bd != NULL; bd = bd->link) {
 236         for (p = bd->start; p < bd->free; p++) {
 237             debugBelch("%p (%s), ", (void *)*p, info_type((StgClosure *)*p));
 238         }
 239     }
 240     debugBelch("\n");
 241 }
 242 #endif /* DEBUG */