rts/sm/GCUtils.c

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