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