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