GCUtils.c 7.8 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team 1998-2008
4 5 6
 *
 * Generational garbage collector: utilities
 *
7 8 9 10 11
 * Documentation on the architecture of the Garbage Collector can be
 * found in the online commentary:
 * 
 *   http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
 *
12 13
 * ---------------------------------------------------------------------------*/

Simon Marlow's avatar
Simon Marlow committed
14
#include "PosixSource.h"
15
#include "Rts.h"
Simon Marlow's avatar
Simon Marlow committed
16

Simon Marlow's avatar
Simon Marlow committed
17
#include "BlockAlloc.h"
18 19
#include "Storage.h"
#include "GC.h"
20
#include "GCThread.h"
Simon Marlow's avatar
Simon Marlow committed
21
#include "GCTDecl.h"
22
#include "GCUtils.h"
23
#include "Printer.h"
24
#include "Trace.h"
25 26 27
#ifdef THREADED_RTS
#include "WSDeque.h"
#endif
28 29 30 31 32 33 34 35 36 37 38 39 40 41

#ifdef THREADED_RTS
SpinLock gc_alloc_block_sync;
#endif

bdescr *
allocBlock_sync(void)
{
    bdescr *bd;
    ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
    bd = allocBlock();
    RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
    return bd;
}
42

43 44 45 46 47 48 49 50 51 52
static bdescr *
allocGroup_sync(nat n)
{
    bdescr *bd;
    ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
    bd = allocGroup(n);
    RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
    return bd;
}

53

54
#if 0
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
static void
allocBlocks_sync(nat n, bdescr **hd, bdescr **tl, 
                 nat gen_no, step *stp,
                 StgWord32 flags)
{
    bdescr *bd;
    nat i;
    ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
    bd = allocGroup(n);
    for (i = 0; i < n; i++) {
        bd[i].blocks = 1;
        bd[i].gen_no = gen_no;
        bd[i].step = stp;
        bd[i].flags = flags;
        bd[i].link = &bd[i+1];
        bd[i].u.scan = bd[i].free = bd[i].start;
    }
    *hd = bd;
    *tl = &bd[n-1];
    RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
}
76
#endif
77

78 79 80 81 82 83 84 85
void
freeChain_sync(bdescr *bd)
{
    ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync);
    freeChain(bd);
    RELEASE_SPIN_LOCK(&gc_alloc_block_sync);
}

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 99 100 101 102 103 104 105 106 107 108
    bd = ws->todo_overflow;
    if (bd != NULL)
    {
        ws->todo_overflow = bd->link;
        bd->link = NULL;
        ws->n_todo_overflow--;
	return bd;
    }

    bd = popWSDeque(ws->todo_q);
    if (bd != NULL)
109 110 111 112 113
    {
	ASSERT(bd->link == NULL);
	return bd;
    }

114 115 116
    return NULL;
}

Simon Marlow's avatar
Simon Marlow committed
117
#if defined(THREADED_RTS)
118
bdescr *
119
steal_todo_block (nat g)
120 121 122 123 124 125 126
{
    nat n;
    bdescr *bd;

    // look for work to steal
    for (n = 0; n < n_gc_threads; n++) {
        if (n == gct->thread_index) continue;
127
        bd = stealWSDeque(gc_threads[n]->gens[g].todo_q);
128 129
        if (bd) {
            return bd;
130
        }
131 132
    }
    return NULL;
133
}
Simon Marlow's avatar
Simon Marlow committed
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 143
    ASSERT(bd->u.scan == bd->free);

144
    if (bd->start + bd->blocks * BLOCK_SIZE_W - bd->free > WORK_UNIT_WORDS)
145 146 147 148
    {
        // a partially full block: put it on the part_list list.
        bd->link = ws->part_list;
        ws->part_list = bd;
149
        ws->n_part_blocks += bd->blocks;
150 151 152 153 154 155 156 157
        IF_DEBUG(sanity, 
                 ASSERT(countBlocks(ws->part_list) == ws->n_part_blocks));
    }
    else
    {
        // put the scan block on the ws->scavd_list.
        bd->link = ws->scavd_list;
        ws->scavd_list = bd;
158
        ws->n_scavd_blocks += bd->blocks;
159 160
        IF_DEBUG(sanity, 
                 ASSERT(countBlocks(ws->scavd_list) == ws->n_scavd_blocks));
161
    }
162 163
}

164
StgPtr
165
todo_block_full (nat size, gen_workspace *ws)
166
{
Simon Marlow's avatar
Simon Marlow committed
167
    StgPtr p;
168 169
    bdescr *bd;

Simon Marlow's avatar
Simon Marlow committed
170 171 172 173
    // todo_free has been pre-incremented by Evac.c:alloc_for_copy().  We
    // are expected to leave it bumped when we've finished here.
    ws->todo_free -= size;

174 175
    bd = ws->todo_bd;

176 177
    ASSERT(bd != NULL);
    ASSERT(bd->link == NULL);
178
    ASSERT(bd->gen == ws->gen);
179 180 181 182 183

    // If the global list is not empty, or there's not much work in
    // this block to push, and there's enough room in
    // this block to evacuate the current object, then just increase
    // the limit.
184
    if (!looksEmptyWSDeque(ws->todo_q) || 
185
        (ws->todo_free - bd->u.scan < WORK_UNIT_WORDS / 2)) {
186 187
        if (ws->todo_free + size < bd->start + bd->blocks * BLOCK_SIZE_W) {
            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);
Simon Marlow's avatar
Simon Marlow committed
190 191 192
            p = ws->todo_free;
            ws->todo_free += size;
            return p;
193 194 195
        }
    }
    
196 197 198
    gct->copied += ws->todo_free - bd->free;
    bd->free = ws->todo_free;

199 200 201 202
    ASSERT(bd->u.scan >= bd->start && bd->u.scan <= bd->free);

    // If this block is not the scan block, we want to push it out and
    // make room for a new todo block.
203
    if (bd != gct->scan_bd)
204 205 206 207 208 209 210 211 212 213 214 215 216
    {
        // If this block does not have enough space to allocate the
        // current object, but it also doesn't have any work to push, then 
        // push it on to the scanned list.  It cannot be empty, because
        // then there would be enough room to copy the current object.
        if (bd->u.scan == bd->free)
        {
            ASSERT(bd->free != bd->start);
            push_scanned_block(bd, ws);
        }
        // Otherwise, push this block out to the global list.
        else 
        {
217 218
            generation *gen;
            gen = ws->gen;
Simon Marlow's avatar
Simon Marlow committed
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 224 225 226

            if (!pushWSDeque(ws->todo_q, bd)) {
                bd->link = ws->todo_overflow;
                ws->todo_overflow = bd;
                ws->n_todo_overflow++;
227 228 229
            }
        }
    }
230

231 232 233
    ws->todo_bd   = NULL;
    ws->todo_free = NULL;
    ws->todo_lim  = NULL;
234

235
    alloc_todo_block(ws, size);
236

Simon Marlow's avatar
Simon Marlow committed
237 238 239
    p = ws->todo_free;
    ws->todo_free += size;
    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 249 250
    bd = ws->part_list;
    if (bd != NULL &&
        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 256
    else
    {
257 258
        // blocks in to-space get the BF_EVACUATED flag.

259
//        allocBlocks_sync(16, &hd, &tl, 
260 261 262 263
//                         ws->step->gen_no, ws->step, BF_EVACUATED);
//
//        tl->link = ws->part_list;
//        ws->part_list = hd->link;
264
//        ws->n_part_blocks += 15;
265 266 267
//
//        bd = hd;

268 269 270 271 272 273
        if (size > BLOCK_SIZE_W) {
            bd = allocGroup_sync((lnat)BLOCK_ROUND_UP(size*sizeof(W_))
                                 / BLOCK_SIZE);
        } else {
            bd = allocBlock_sync();
        }
274
        initBdescr(bd, ws->gen, ws->gen->to);
275 276
        bd->flags = BF_EVACUATED;
        bd->u.scan = bd->free = bd->start;
277
    }
278

279 280
    bd->link = NULL;

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 285
                            bd->free + stg_max(WORK_UNIT_WORDS,size));

286 287
    debugTrace(DEBUG_gc, "alloc new todo block %p for gen  %d", 
               bd->free, ws->gen->no);
288

289
    return ws->todo_free;
290 291
}

292 293 294 295 296 297
/* -----------------------------------------------------------------------------
 * Debugging
 * -------------------------------------------------------------------------- */

#if DEBUG
void
298
printMutableList(bdescr *bd)
299 300 301
{
    StgPtr p;

302
    debugBelch("mutable list %p: ", bd);
303

304
    for (; bd != NULL; bd = bd->link) {
305 306 307 308 309 310 311
	for (p = bd->start; p < bd->free; p++) {
	    debugBelch("%p (%s), ", (void *)*p, info_type((StgClosure *)*p));
	}
    }
    debugBelch("\n");
}
#endif /* DEBUG */