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