GCCompact.c 20.4 KB
Newer Older
1
2
3
4
5
6
7
8
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team 2001
 *
 * Compacting garbage collector
 *
 * ---------------------------------------------------------------------------*/

9
#include "PosixSource.h"
10
11
12
#include "Rts.h"
#include "RtsUtils.h"
#include "RtsFlags.h"
13
#include "OSThreads.h"
14
15
16
17
18
#include "Storage.h"
#include "BlockAlloc.h"
#include "MBlock.h"
#include "GCCompact.h"
#include "Schedule.h"
19
#include "Apply.h"
20

21
22
// Turn off inlining when debugging - it obfuscates things
#ifdef DEBUG
sof's avatar
sof committed
23
24
# undef  STATIC_INLINE
# define STATIC_INLINE static
25
26
#endif

27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/* -----------------------------------------------------------------------------
   Threading / unthreading pointers.

   The basic idea here is to chain together all the fields pointing at
   a particular object, with the root of the chain in the object's
   info table field.  The original contents of the info pointer goes
   at the end of the chain.

   Adding a new field to the chain is a matter of swapping the
   contents of the field with the contents of the object's info table
   field.

   To unthread the chain, we walk down it updating all the fields on
   the chain with the new location of the object.  We stop when we
   reach the info pointer at the end.

43
44
45
46
   We use a trick to identify the info pointer: when swapping pointers
   for threading, we set the low bit of the original pointer, with the
   result that all the pointers in the chain have their low bits set
   except for the info pointer.
47
48
   -------------------------------------------------------------------------- */

sof's avatar
sof committed
49
STATIC_INLINE void
50
51
52
thread( StgPtr p )
{
    StgPtr q = (StgPtr)*p;
53
54
    bdescr *bd;

55
56
57
58
    // It doesn't look like a closure at the moment, because the info
    // ptr is possibly threaded:
    // ASSERT(LOOKS_LIKE_CLOSURE_PTR(q));

59
    if (HEAP_ALLOCED(q)) {
60
61
62
63
64
65
	bd = Bdescr(q); 
	// a handy way to discover whether the ptr is into the
	// compacted area of the old gen, is that the EVACUATED flag
	// is zero (it's non-zero for all the other areas of live
	// memory).
	if ((bd->flags & BF_EVACUATED) == 0) {
66
67
68
	    *p = (StgWord)*q;
	    *q = (StgWord)p + 1;	// set the low bit
	}
69
70
71
    }
}

sof's avatar
sof committed
72
STATIC_INLINE void
73
74
unthread( StgPtr p, StgPtr free )
{
75
    StgWord q = *p, r;
76
    
77
78
79
80
    while ((q & 1) != 0) {
	q -= 1;	// unset the low bit again
	r = *((StgPtr)q);
	*((StgPtr)q) = (StgWord)free;
81
82
	q = r;
    }
83
    *p = q;
84
85
}

sof's avatar
sof committed
86
STATIC_INLINE StgInfoTable *
87
88
89
90
get_threaded_info( StgPtr p )
{
    StgPtr q = (P_)GET_INFO((StgClosure *)p);

91
92
    while (((StgWord)q & 1) != 0) {
	q = (P_)*((StgPtr)((StgWord)q-1));
93
    }
94
95

    ASSERT(LOOKS_LIKE_INFO_PTR(q));
96
97
98
99
100
    return INFO_PTR_TO_STRUCT((StgInfoTable *)q);
}

// A word-aligned memmove will be faster for small objects than libc's or gcc's.
// Remember, the two regions *might* overlap, but: to <= from.
sof's avatar
sof committed
101
STATIC_INLINE void
102
103
104
105
106
107
108
move(StgPtr to, StgPtr from, nat size)
{
    for(; size > 0; --size) {
	*to++ = *from++;
    }
}

sof's avatar
sof committed
109
STATIC_INLINE nat
110
111
112
113
114
115
116
117
obj_sizeW( StgClosure *p, StgInfoTable *info )
{
    switch (info->type) {
    case FUN_0_1:
    case CONSTR_0_1:
    case FUN_1_0:
    case CONSTR_1_0:
    case THUNK_0_1:
118
119
    case THUNK_1_0:
	return sizeofW(StgHeader) + 1;
120
121
122
123
124
125
126
127
128
    case THUNK_0_2:
    case FUN_0_2:
    case CONSTR_0_2:
    case THUNK_1_1:
    case FUN_1_1:
    case CONSTR_1_1:
    case THUNK_2_0:
    case FUN_2_0:
    case CONSTR_2_0:
129
	return sizeofW(StgHeader) + 2;
130
131
    case THUNK_SELECTOR:
	return THUNK_SELECTOR_sizeW();
132
133
134
    case AP_STACK:
	return ap_stack_sizeW((StgAP_STACK *)p);
    case AP:
135
136
137
138
139
140
    case PAP:
	return pap_sizeW((StgPAP *)p);
    case ARR_WORDS:
	return arr_words_sizeW((StgArrWords *)p);
    case MUT_ARR_PTRS:
    case MUT_ARR_PTRS_FROZEN:
141
    case MUT_ARR_PTRS_FROZEN0:
142
143
144
	return mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
    case TSO:
	return tso_sizeW((StgTSO *)p);
145
146
    case BCO:
	return bco_sizeW((StgBCO *)p);
147
148
149
150
151
152
153
154
    case TVAR_WAIT_QUEUE:
        return sizeofW(StgTVarWaitQueue);
    case TVAR:
        return sizeofW(StgTVar);
    case TREC_CHUNK:
        return sizeofW(StgTRecChunk);
    case TREC_HEADER:
        return sizeofW(StgTRecHeader);
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
    default:
	return sizeW_fromITBL(info);
    }
}

static void
thread_static( StgClosure* p )
{
  const StgInfoTable *info;

  // keep going until we've threaded all the objects on the linked
  // list... 
  while (p != END_OF_STATIC_LIST) {

    info = get_itbl(p);
    switch (info->type) {
      
    case IND_STATIC:
	thread((StgPtr)&((StgInd *)p)->indirectee);
174
175
	p = IND_STATIC_LINK(p);
	continue;
176
177
      
    case THUNK_STATIC:
178
179
	p = THUNK_STATIC_LINK(p);
	continue;
180
    case FUN_STATIC:
181
182
	p = FUN_STATIC_LINK(p);
	continue;
183
    case CONSTR_STATIC:
184
185
	p = STATIC_LINK(info,p);
	continue;
186
187
188
189
190
191
192
193
      
    default:
	barf("thread_static: strange closure %d", (int)(info->type));
    }

  }
}

sof's avatar
sof committed
194
STATIC_INLINE void
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
thread_large_bitmap( StgPtr p, StgLargeBitmap *large_bitmap, nat size )
{
    nat i, b;
    StgWord bitmap;

    b = 0;
    bitmap = large_bitmap->bitmap[b];
    for (i = 0; i < size; ) {
	if ((bitmap & 1) == 0) {
	    thread(p);
	}
	i++;
	p++;
	if (i % BITS_IN(W_) == 0) {
	    b++;
	    bitmap = large_bitmap->bitmap[b];
	} else {
	    bitmap = bitmap >> 1;
	}
    }
}

sof's avatar
sof committed
217
STATIC_INLINE StgPtr
218
219
220
221
222
223
224
thread_arg_block (StgFunInfoTable *fun_info, StgClosure **args)
{
    StgPtr p;
    StgWord bitmap;
    nat size;

    p = (StgPtr)args;
225
    switch (fun_info->f.fun_type) {
226
    case ARG_GEN:
227
228
	bitmap = BITMAP_BITS(fun_info->f.b.bitmap);
	size = BITMAP_SIZE(fun_info->f.b.bitmap);
229
230
	goto small_bitmap;
    case ARG_GEN_BIG:
231
232
	size = GET_FUN_LARGE_BITMAP(fun_info)->size;
	thread_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size);
233
234
235
	p += size;
	break;
    default:
236
237
	bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]);
	size = BITMAP_SIZE(stg_arg_bitmaps[fun_info->f.fun_type]);
238
239
240
241
242
243
244
245
246
247
248
249
250
251
    small_bitmap:
	while (size > 0) {
	    if ((bitmap & 1) == 0) {
		thread(p);
	    }
	    p++;
	    bitmap = bitmap >> 1;
	    size--;
	}
	break;
    }
    return p;
}

252
253
254
static void
thread_stack(StgPtr p, StgPtr stack_end)
{
255
    const StgRetInfoTable* info;
ken's avatar
ken committed
256
    StgWord bitmap;
257
    nat size;
258
259
260
261
262
    
    // highly similar to scavenge_stack, but we do pointer threading here.
    
    while (p < stack_end) {

263
	// *p must be the info pointer of an activation
264
265
266
	// record.  All activation records have 'bitmap' style layout
	// info.
	//
267
	info  = get_ret_itbl((StgClosure *)p);
268
	
269
	switch (info->i.type) {
270
271
272
	    
	    // Dynamic bitmap: the mask is stored on the stack 
	case RET_DYN:
273
274
275
276
277
	{
	    StgWord dyn;
	    dyn = ((StgRetDyn *)p)->liveness;

	    // traverse the bitmap first
278
	    bitmap = RET_DYN_LIVENESS(dyn);
279
	    p      = (P_)&((StgRetDyn *)p)->payload[0];
280
	    size   = RET_DYN_BITMAP_SIZE;
281
282
283
284
285
286
287
288
	    while (size > 0) {
		if ((bitmap & 1) == 0) {
		    thread(p);
		}
		p++;
		bitmap = bitmap >> 1;
		size--;
	    }
289
	    
290
	    // skip over the non-ptr words
291
	    p += RET_DYN_NONPTRS(dyn) + RET_DYN_NONPTR_REGS_SIZE;
292
293
	    
	    // follow the ptr words
294
	    for (size = RET_DYN_PTRS(dyn); size > 0; size--) {
295
296
297
		thread(p);
		p++;
	    }
298
	    continue;
299
	}
300
	    
ken's avatar
ken committed
301
	    // small bitmap (<= 32 entries, or 64 on a 64-bit machine) 
302
303
304
        case CATCH_RETRY_FRAME:
        case CATCH_STM_FRAME:
        case ATOMICALLY_FRAME:
305
306
307
308
309
	case UPDATE_FRAME:
	case STOP_FRAME:
	case CATCH_FRAME:
	case RET_SMALL:
	case RET_VEC_SMALL:
310
311
	    bitmap = BITMAP_BITS(info->i.layout.bitmap);
	    size   = BITMAP_SIZE(info->i.layout.bitmap);
312
	    p++;
313
314
315
	    // NOTE: the payload starts immediately after the info-ptr, we
	    // don't have an StgHeader in the same sense as a heap closure.
	    while (size > 0) {
316
317
318
319
320
		if ((bitmap & 1) == 0) {
		    thread(p);
		}
		p++;
		bitmap = bitmap >> 1;
321
		size--;
322
323
324
	    }
	    continue;

325
326
327
328
329
330
	case RET_BCO: {
	    StgBCO *bco;
	    nat size;
	    
	    p++;
	    bco = (StgBCO *)*p;
331
	    thread(p);
332
333
334
335
336
337
338
	    p++;
	    size = BCO_BITMAP_SIZE(bco);
	    thread_large_bitmap(p, BCO_BITMAP(bco), size);
	    p += size;
	    continue;
	}

ken's avatar
ken committed
339
	    // large bitmap (> 32 entries, or 64 on a 64-bit machine) 
340
341
342
	case RET_BIG:
	case RET_VEC_BIG:
	    p++;
343
344
	    size = GET_LARGE_BITMAP(&info->i)->size;
	    thread_large_bitmap(p, GET_LARGE_BITMAP(&info->i), size);
345
346
	    p += size;
	    continue;
347

348
349
350
351
352
	case RET_FUN:
	{
	    StgRetFun *ret_fun = (StgRetFun *)p;
	    StgFunInfoTable *fun_info;
	    
353
354
	    fun_info = itbl_to_fun_itbl(
		get_threaded_info((StgPtr)ret_fun->fun));
355
	         // *before* threading it!
356
357
	    thread((StgPtr)&ret_fun->fun);
	    p = thread_arg_block(fun_info, ret_fun->payload);
358
359
360
361
362
	    continue;
	}

	default:
	    barf("thread_stack: weird activation record found on stack: %d", 
363
		 (int)(info->i.type));
364
365
366
367
	}
    }
}

sof's avatar
sof committed
368
STATIC_INLINE StgPtr
369
370
371
372
373
374
thread_PAP (StgPAP *pap)
{
    StgPtr p;
    StgWord bitmap, size;
    StgFunInfoTable *fun_info;
    
375
    fun_info = itbl_to_fun_itbl(get_threaded_info((StgPtr)pap->fun));
376
377
378
379
380
    ASSERT(fun_info->i.type != PAP);

    p = (StgPtr)pap->payload;
    size = pap->n_args;

381
    switch (fun_info->f.fun_type) {
382
    case ARG_GEN:
383
	bitmap = BITMAP_BITS(fun_info->f.b.bitmap);
384
385
	goto small_bitmap;
    case ARG_GEN_BIG:
386
	thread_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size);
387
388
389
390
391
392
393
	p += size;
	break;
    case ARG_BCO:
	thread_large_bitmap((StgPtr)pap->payload, BCO_BITMAP(pap->fun), size);
	p += size;
	break;
    default:
394
	bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]);
395
396
397
398
399
400
401
402
403
404
405
406
    small_bitmap:
	size = pap->n_args;
	while (size > 0) {
	    if ((bitmap & 1) == 0) {
		thread(p);
	    }
	    p++;
	    bitmap = bitmap >> 1;
	    size--;
	}
	break;
    }
407
408

    thread((StgPtr)&pap->fun);
409
410
411
    return p;
}

sof's avatar
sof committed
412
STATIC_INLINE StgPtr
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
thread_AP_STACK (StgAP_STACK *ap)
{
    thread((StgPtr)&ap->fun);
    thread_stack((P_)ap->payload, (P_)ap->payload + ap->size);
    return (P_)ap + sizeofW(StgAP_STACK) + ap->size;
}

static StgPtr
thread_TSO (StgTSO *tso)
{
    thread((StgPtr)&tso->link);
    thread((StgPtr)&tso->global_link);

    if (   tso->why_blocked == BlockedOnMVar
	|| tso->why_blocked == BlockedOnBlackHole
	|| tso->why_blocked == BlockedOnException
#if defined(PAR)
	|| tso->why_blocked == BlockedOnGA
	|| tso->why_blocked == BlockedOnGA_NoSend
#endif
	) {
	thread((StgPtr)&tso->block_info.closure);
    }
    if ( tso->blocked_exceptions != NULL ) {
	thread((StgPtr)&tso->blocked_exceptions);
    }
    
440
441
    thread((StgPtr)&tso->trec);

442
443
444
445
446
    thread_stack(tso->sp, &(tso->stack[tso->stack_size]));
    return (StgPtr)tso + tso_sizeW(tso);
}


447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
static void
update_fwd_large( bdescr *bd )
{
  StgPtr p;
  const StgInfoTable* info;

  for (; bd != NULL; bd = bd->link) {

    p = bd->start;
    info  = get_itbl((StgClosure *)p);

    switch (info->type) {

    case ARR_WORDS:
      // nothing to follow 
      continue;

    case MUT_ARR_PTRS:
    case MUT_ARR_PTRS_FROZEN:
466
    case MUT_ARR_PTRS_FROZEN0:
467
468
469
470
471
472
473
474
475
476
477
478
      // follow everything 
      {
	StgPtr next;

	next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
	for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) {
	    thread(p);
	}
	continue;
      }

    case TSO:
479
480
481
482
483
	thread_TSO((StgTSO *)p);
	continue;

    case AP_STACK:
	thread_AP_STACK((StgAP_STACK *)p);
484
485
486
	continue;

    case PAP:
487
	thread_PAP((StgPAP *)p);
488
489
490
491
492
493
494
495
	continue;

    default:
      barf("update_fwd_large: unknown/strange object  %d", (int)(info->type));
    }
  }
}

sof's avatar
sof committed
496
STATIC_INLINE StgPtr
497
498
499
500
501
thread_obj (StgInfoTable *info, StgPtr p)
{
    switch (info->type) {
    case FUN_0_1:
    case CONSTR_0_1:
502
    case THUNK_0_1:
503
504
505
506
507
508
509
510
511
	return p + sizeofW(StgHeader) + 1;
	
    case FUN_1_0:
    case CONSTR_1_0:
	thread((StgPtr)&((StgClosure *)p)->payload[0]);
	return p + sizeofW(StgHeader) + 1;
	
    case THUNK_1_0:
	thread((StgPtr)&((StgClosure *)p)->payload[0]);
512
	return p + sizeofW(StgHeader) + 1;
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
	
    case THUNK_0_2:
    case FUN_0_2:
    case CONSTR_0_2:
	return p + sizeofW(StgHeader) + 2;
	
    case THUNK_1_1:
    case FUN_1_1:
    case CONSTR_1_1:
	thread((StgPtr)&((StgClosure *)p)->payload[0]);
	return p + sizeofW(StgHeader) + 2;
	
    case THUNK_2_0:
    case FUN_2_0:
    case CONSTR_2_0:
	thread((StgPtr)&((StgClosure *)p)->payload[0]);
	thread((StgPtr)&((StgClosure *)p)->payload[1]);
	return p + sizeofW(StgHeader) + 2;
	
532
533
534
535
536
537
538
539
540
    case BCO: {
	StgBCO *bco = (StgBCO *)p;
	thread((StgPtr)&bco->instrs);
	thread((StgPtr)&bco->literals);
	thread((StgPtr)&bco->ptrs);
	thread((StgPtr)&bco->itbls);
	return p + bco_sizeW(bco);
    }

541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
    case FUN:
    case THUNK:
    case CONSTR:
    case FOREIGN:
    case STABLE_NAME:
    case IND_PERM:
    case MUT_VAR:
    case CAF_BLACKHOLE:
    case SE_CAF_BLACKHOLE:
    case SE_BLACKHOLE:
    case BLACKHOLE:
    {
	StgPtr end;
	
	end = (P_)((StgClosure *)p)->payload + 
	    info->layout.payload.ptrs;
	for (p = (P_)((StgClosure *)p)->payload; p < end; p++) {
	    thread(p);
	}
	return p + info->layout.payload.nptrs;
    }
    
    case WEAK:
    {
	StgWeak *w = (StgWeak *)p;
	thread((StgPtr)&w->key);
	thread((StgPtr)&w->value);
	thread((StgPtr)&w->finalizer);
	if (w->link != NULL) {
	    thread((StgPtr)&w->link);
	}
	return p + sizeofW(StgWeak);
    }
    
    case MVAR:
    { 
	StgMVar *mvar = (StgMVar *)p;
	thread((StgPtr)&mvar->head);
	thread((StgPtr)&mvar->tail);
	thread((StgPtr)&mvar->value);
	return p + sizeofW(StgMVar);
    }
    
    case IND_OLDGEN:
    case IND_OLDGEN_PERM:
586
587
	thread((StgPtr)&((StgInd *)p)->indirectee);
	return p + sizeofW(StgInd);
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607

    case THUNK_SELECTOR:
    { 
	StgSelector *s = (StgSelector *)p;
	thread((StgPtr)&s->selectee);
	return p + THUNK_SELECTOR_sizeW();
    }
    
    case AP_STACK:
	return thread_AP_STACK((StgAP_STACK *)p);
	
    case PAP:
    case AP:
	return thread_PAP((StgPAP *)p);
	
    case ARR_WORDS:
	return p + arr_words_sizeW((StgArrWords *)p);
	
    case MUT_ARR_PTRS:
    case MUT_ARR_PTRS_FROZEN:
608
    case MUT_ARR_PTRS_FROZEN0:
609
610
611
612
613
614
615
616
617
618
619
620
621
622
	// follow everything 
    {
	StgPtr next;
	
	next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
	for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) {
	    thread(p);
	}
	return p;
    }
    
    case TSO:
	return thread_TSO((StgTSO *)p);
    
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
    case TVAR_WAIT_QUEUE:
    {
        StgTVarWaitQueue *wq = (StgTVarWaitQueue *)p;
	thread((StgPtr)&wq->waiting_tso);
	thread((StgPtr)&wq->next_queue_entry);
	thread((StgPtr)&wq->prev_queue_entry);
	return p + sizeofW(StgTVarWaitQueue);
    }
    
    case TVAR:
    {
        StgTVar *tvar = (StgTVar *)p;
	thread((StgPtr)&tvar->current_value);
	thread((StgPtr)&tvar->first_wait_queue_entry);
	return p + sizeofW(StgTVar);
    }
    
    case TREC_HEADER:
    {
        StgTRecHeader *trec = (StgTRecHeader *)p;
	thread((StgPtr)&trec->enclosing_trec);
	thread((StgPtr)&trec->current_chunk);
	return p + sizeofW(StgTRecHeader);
    }

    case TREC_CHUNK:
    {
650
        StgWord i;
651
652
653
654
655
656
657
658
659
660
661
        StgTRecChunk *tc = (StgTRecChunk *)p;
	TRecEntry *e = &(tc -> entries[0]);
	thread((StgPtr)&tc->prev_chunk);
	for (i = 0; i < tc -> next_entry_idx; i ++, e++ ) {
	  thread((StgPtr)&e->tvar);
	  thread((StgPtr)&e->expected_value);
	  thread((StgPtr)&e->new_value);
	}
	return p + sizeofW(StgTRecChunk);
    }

662
663
    default:
	barf("update_fwd: unknown/strange object  %d", (int)(info->type));
sof's avatar
sof committed
664
	return NULL;
665
666
667
    }
}

668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
static void
update_fwd( bdescr *blocks )
{
    StgPtr p;
    bdescr *bd;
    StgInfoTable *info;

    bd = blocks;

#if defined(PAR)
    barf("update_fwd: ToDo");
#endif

    // cycle through all the blocks in the step
    for (; bd != NULL; bd = bd->link) {
	p = bd->start;

	// linearly scan the objects in this block
	while (p < bd->free) {
687
	    ASSERT(LOOKS_LIKE_CLOSURE_PTR(p));
688
	    info = get_itbl((StgClosure *)p);
689
	    p = thread_obj(info, p);
690
691
692
693
694
695
696
697
	}
    }
} 

static void
update_fwd_compact( bdescr *blocks )
{
    StgPtr p, q, free;
698
#if 0
699
    StgWord m;
700
#endif
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
    bdescr *bd, *free_bd;
    StgInfoTable *info;
    nat size;

    bd = blocks;
    free_bd = blocks;
    free = free_bd->start;

#if defined(PAR)
    barf("update_fwd: ToDo");
#endif

    // cycle through all the blocks in the step
    for (; bd != NULL; bd = bd->link) {
	p = bd->start;

	while (p < bd->free ) {

	    while ( p < bd->free && !is_marked(p,bd) ) {
		p++;
	    }
	    if (p >= bd->free) {
		break;
	    }

#if 0
    next:
	m = * ((StgPtr)bd->u.bitmap + ((p - bd->start) / (BITS_IN(StgWord))));
	m >>= ((p - bd->start) & (BITS_IN(StgWord) - 1));

	while ( p < bd->free ) {

	    if ((m & 1) == 0) {
		m >>= 1;
		p++;
		if (((StgWord)p & (sizeof(W_) * BITS_IN(StgWord))) == 0) {
		    goto next;
		} else {
		    continue;
		}
	    }
#endif

	    // Problem: we need to know the destination for this cell
	    // in order to unthread its info pointer.  But we can't
	    // know the destination without the size, because we may
	    // spill into the next block.  So we have to run down the 
	    // threaded list and get the info ptr first.
	    info = get_threaded_info(p);

	    q = p;

753
	    p = thread_obj(info, p);
754
755
756

	    size = p - q;
	    if (free + size > free_bd->start + BLOCK_SIZE_W) {
757
758
759
760
761
		// unset the next bit in the bitmap to indicate that
		// this object needs to be pushed into the next
		// block.  This saves us having to run down the
		// threaded info pointer list twice during the next pass.
		unmark(q+1,bd);
762
763
		free_bd = free_bd->link;
		free = free_bd->start;
764
765
	    } else {
		ASSERT(is_marked(q+1,bd));
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
	    }

	    unthread(q,free);
	    free += size;
#if 0
	    goto next;
#endif
	}
    }
}

static nat
update_bkwd_compact( step *stp )
{
    StgPtr p, free;
781
#if 0
782
    StgWord m;
783
#endif
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
    bdescr *bd, *free_bd;
    StgInfoTable *info;
    nat size, free_blocks;

    bd = free_bd = stp->blocks;
    free = free_bd->start;
    free_blocks = 1;

#if defined(PAR)
    barf("update_bkwd: ToDo");
#endif

    // cycle through all the blocks in the step
    for (; bd != NULL; bd = bd->link) {
	p = bd->start;

	while (p < bd->free ) {

	    while ( p < bd->free && !is_marked(p,bd) ) {
		p++;
	    }
	    if (p >= bd->free) {
		break;
	    }

#if 0
    next:
	m = * ((StgPtr)bd->u.bitmap + ((p - bd->start) / (BITS_IN(StgWord))));
	m >>= ((p - bd->start) & (BITS_IN(StgWord) - 1));

	while ( p < bd->free ) {

	    if ((m & 1) == 0) {
		m >>= 1;
		p++;
		if (((StgWord)p & (sizeof(W_) * BITS_IN(StgWord))) == 0) {
		    goto next;
		} else {
		    continue;
		}
	    }
#endif

827
	    if (!is_marked(p+1,bd)) {
828
829
830
831
832
833
834
835
		// don't forget to update the free ptr in the block desc.
		free_bd->free = free;
		free_bd = free_bd->link;
		free = free_bd->start;
		free_blocks++;
	    }

	    unthread(p,free);
836
	    ASSERT(LOOKS_LIKE_INFO_PTR(((StgClosure *)p)->header.info));
837
838
839
	    info = get_itbl((StgClosure *)p);
	    size = obj_sizeW((StgClosure *)p,info);

840
841
842
	    if (free != p) {
		move(free,p,size);
	    }
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865

	    // relocate TSOs
	    if (info->type == TSO) {
		move_TSO((StgTSO *)p, (StgTSO *)free);
	    }

	    free += size;
	    p += size;
#if 0
	    goto next;
#endif
	}
    }

    // free the remaining blocks and count what's left.
    free_bd->free = free;
    if (free_bd->link != NULL) {
	freeChain(free_bd->link);
	free_bd->link = NULL;
    }
    stp->n_blocks = free_blocks;

    return free_blocks;
866
867
}

868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
void
compact( void (*get_roots)(evac_fn) )
{
    nat g, s, blocks;
    step *stp;

    // 1. thread the roots
    get_roots((evac_fn)thread);

    // the weak pointer lists...
    if (weak_ptr_list != NULL) {
	thread((StgPtr)&weak_ptr_list);
    }
    if (old_weak_ptr_list != NULL) {
	thread((StgPtr)&old_weak_ptr_list); // tmp
    }

885
886
    // mutable lists
    for (g = 1; g < RtsFlags.GcFlags.generations; g++) {
887
888
889
890
891
892
893
	bdescr *bd;
	StgPtr p;
	for (bd = generations[g].mut_list; bd != NULL; bd = bd->link) {
	    for (p = bd->start; p < bd->free; p++) {
		thread(p);
	    }
	}
894
    }
895
896
897
898

    // the global thread list
    thread((StgPtr)&all_threads);

899
900
901
902
903
904
905
906
907
908
909
    // any threads resurrected during this GC
    thread((StgPtr)&resurrected_threads);

    // the main threads list
    {
	StgMainThread *m;
	for (m = main_threads; m != NULL; m = m->link) {
	    thread((StgPtr)&m->tso);
	}
    }

910
911
912
913
914
915
    // the static objects
    thread_static(scavenged_static_objects);

    // the stable pointer table
    threadStablePtrTable((evac_fn)thread);

916
917
918
    // the CAF list (used by GHCi)
    markCAFs((evac_fn)thread);

919
920
921
922
    // 2. update forward ptrs
    for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
	for (s = 0; s < generations[g].n_steps; s++) {
	    stp = &generations[g].steps[s];
923
	    IF_DEBUG(gc, debugBelch("update_fwd:  %d.%d\n", stp->gen->no, stp->no););
924
925
926
927

	    update_fwd(stp->to_blocks);
	    update_fwd_large(stp->scavenged_large_objects);
	    if (g == RtsFlags.GcFlags.generations-1 && stp->blocks != NULL) {
928
		IF_DEBUG(gc, debugBelch("update_fwd:  %d.%d (compact)\n", stp->gen->no, stp->no););
929
930
931
932
933
934
		update_fwd_compact(stp->blocks);
	    }
	}
    }

    // 3. update backward ptrs
935
936
937
    stp = &oldest_gen->steps[0];
    if (stp->blocks != NULL) {
	blocks = update_bkwd_compact(stp);
938
	IF_DEBUG(gc, debugBelch("update_bkwd: %d.%d (compact, old: %d blocks, now %d blocks)\n", 
939
940
941
			     stp->gen->no, stp->no,
			     stp->n_blocks, blocks););
	stp->n_blocks = blocks;
942
943
    }
}