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