Rts: Consistently use StgWord for sizes of bitmaps
[ghc.git] / rts / sm / Compact.c
index 44b5242..3731dd6 100644 (file)
@@ -1,28 +1,31 @@
 /* -----------------------------------------------------------------------------
  *
- * (c) The GHC Team 2001-2006
+ * (c) The GHC Team 2001-2008
  *
  * Compacting garbage collector
  *
  * 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
+ *   http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
  *
  * ---------------------------------------------------------------------------*/
 
 #include "PosixSource.h"
 #include "Rts.h"
+
+#include "GCThread.h"
+#include "Storage.h"
 #include "RtsUtils.h"
-#include "RtsFlags.h"
-#include "OSThreads.h"
 #include "BlockAlloc.h"
-#include "MBlock.h"
 #include "GC.h"
 #include "Compact.h"
 #include "Schedule.h"
 #include "Apply.h"
 #include "Trace.h"
+#include "Weak.h"
+#include "MarkWeak.h"
+#include "Stable.h"
 
 // Turn off inlining when debugging - it obfuscates things
 #ifdef DEBUG
@@ -83,11 +86,8 @@ thread (StgClosure **p)
     
     if (HEAP_ALLOCED(q)) {
        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)
+
+       if (bd->flags & BF_MARKED)
         {
             iptr = *q;
             switch (GET_CLOSURE_TAG((StgClosure *)iptr))
@@ -109,6 +109,12 @@ thread (StgClosure **p)
     }
 }
 
+static void
+thread_root (void *user STG_UNUSED, StgClosure **p)
+{
+    thread(p);
+}
+
 // This version of thread() takes a (void *), used to circumvent
 // warnings from gcc about pointer punning and strict aliasing.
 STATIC_INLINE void thread_ (void *p) { thread((StgClosure **)p); }
@@ -163,7 +169,7 @@ loop:
     case 1:
     {
         StgWord r = *(StgPtr)(q-1);
-        ASSERT(LOOKS_LIKE_INFO_PTR(UNTAG_CLOSURE((StgClosure *)r)));
+        ASSERT(LOOKS_LIKE_INFO_PTR((StgWord)UNTAG_CLOSURE((StgClosure *)r)));
         return r;
     }
     case 2:
@@ -177,7 +183,7 @@ loop:
 // 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.
 STATIC_INLINE void
-move(StgPtr to, StgPtr from, nat size)
+move(StgPtr to, StgPtr from, StgWord size)
 {
     for(; size > 0; --size) {
        *to++ = *from++;
@@ -219,9 +225,9 @@ thread_static( StgClosure* p )
 }
 
 STATIC_INLINE void
-thread_large_bitmap( StgPtr p, StgLargeBitmap *large_bitmap, nat size )
+thread_large_bitmap( StgPtr p, StgLargeBitmap *large_bitmap, StgWord size )
 {
-    nat i, b;
+    W_ i, b;
     StgWord bitmap;
 
     b = 0;
@@ -246,7 +252,7 @@ thread_arg_block (StgFunInfoTable *fun_info, StgClosure **args)
 {
     StgPtr p;
     StgWord bitmap;
-    nat size;
+    StgWord size;
 
     p = (StgPtr)args;
     switch (fun_info->f.fun_type) {
@@ -281,7 +287,7 @@ thread_stack(StgPtr p, StgPtr stack_end)
 {
     const StgRetInfoTable* info;
     StgWord bitmap;
-    nat size;
+    StgWord size;
     
     // highly similar to scavenge_stack, but we do pointer threading here.
     
@@ -295,43 +301,14 @@ thread_stack(StgPtr p, StgPtr stack_end)
        
        switch (info->i.type) {
            
-           // Dynamic bitmap: the mask is stored on the stack 
-       case RET_DYN:
-       {
-           StgWord dyn;
-           dyn = ((StgRetDyn *)p)->liveness;
-
-           // traverse the bitmap first
-           bitmap = RET_DYN_LIVENESS(dyn);
-           p      = (P_)&((StgRetDyn *)p)->payload[0];
-           size   = RET_DYN_BITMAP_SIZE;
-           while (size > 0) {
-               if ((bitmap & 1) == 0) {
-                   thread((StgClosure **)p);
-               }
-               p++;
-               bitmap = bitmap >> 1;
-               size--;
-           }
-           
-           // skip over the non-ptr words
-           p += RET_DYN_NONPTRS(dyn) + RET_DYN_NONPTR_REGS_SIZE;
-           
-           // follow the ptr words
-           for (size = RET_DYN_PTRS(dyn); size > 0; size--) {
-               thread((StgClosure **)p);
-               p++;
-           }
-           continue;
-       }
-           
-           // small bitmap (<= 32 entries, or 64 on a 64-bit machine) 
+            // small bitmap (<= 32 entries, or 64 on a 64-bit machine)
         case CATCH_RETRY_FRAME:
         case CATCH_STM_FRAME:
         case ATOMICALLY_FRAME:
        case UPDATE_FRAME:
-       case STOP_FRAME:
-       case CATCH_FRAME:
+        case UNDERFLOW_FRAME:
+        case STOP_FRAME:
+        case CATCH_FRAME:
        case RET_SMALL:
            bitmap = BITMAP_BITS(info->i.layout.bitmap);
            size   = BITMAP_SIZE(info->i.layout.bitmap);
@@ -350,7 +327,6 @@ thread_stack(StgPtr p, StgPtr stack_end)
 
        case RET_BCO: {
            StgBCO *bco;
-           nat size;
            
            p++;
            bco = (StgBCO *)*p;
@@ -375,7 +351,7 @@ thread_stack(StgPtr p, StgPtr stack_end)
            StgRetFun *ret_fun = (StgRetFun *)p;
            StgFunInfoTable *fun_info;
            
-           fun_info = FUN_INFO_PTR_TO_STRUCT(UNTAG_CLOSURE((StgClosure *)
+           fun_info = FUN_INFO_PTR_TO_STRUCT((StgInfoTable *)UNTAG_CLOSURE((StgClosure *)
                            get_threaded_info((StgPtr)ret_fun->fun)));
                 // *before* threading it!
            thread(&ret_fun->fun);
@@ -397,7 +373,7 @@ thread_PAP_payload (StgClosure *fun, StgClosure **payload, StgWord size)
     StgWord bitmap;
     StgFunInfoTable *fun_info;
 
-    fun_info = FUN_INFO_PTR_TO_STRUCT(UNTAG_CLOSURE((StgClosure *)
+    fun_info = FUN_INFO_PTR_TO_STRUCT((StgInfoTable *)UNTAG_CLOSURE((StgClosure *)
                         get_threaded_info((StgPtr)fun)));
     ASSERT(fun_info->i.type != PAP);
 
@@ -461,21 +437,24 @@ thread_AP_STACK (StgAP_STACK *ap)
 static StgPtr
 thread_TSO (StgTSO *tso)
 {
-    thread_(&tso->link);
+    thread_(&tso->_link);
     thread_(&tso->global_link);
 
     if (   tso->why_blocked == BlockedOnMVar
+        || tso->why_blocked == BlockedOnMVarRead
        || tso->why_blocked == BlockedOnBlackHole
-       || tso->why_blocked == BlockedOnException
-       ) {
+       || tso->why_blocked == BlockedOnMsgThrowTo
+        || tso->why_blocked == NotBlocked
+        ) {
        thread_(&tso->block_info.closure);
     }
     thread_(&tso->blocked_exceptions);
+    thread_(&tso->bq);
     
     thread_(&tso->trec);
 
-    thread_stack(tso->sp, &(tso->stack[tso->stack_size]));
-    return (StgPtr)tso + tso_sizeW(tso);
+    thread_(&tso->stackobj);
+    return (StgPtr)tso + sizeofW(StgTSO);
 }
 
 
@@ -487,6 +466,10 @@ update_fwd_large( bdescr *bd )
 
   for (; bd != NULL; bd = bd->link) {
 
+    // nothing to do in a pinned block; it might not even have an object
+    // at the beginning.
+    if (bd->flags & BF_PINNED) continue;
+
     p = bd->start;
     info  = get_itbl((StgClosure *)p);
 
@@ -502,18 +485,36 @@ update_fwd_large( bdescr *bd )
     case MUT_ARR_PTRS_FROZEN0:
       // follow everything 
       {
-       StgPtr next;
+          StgMutArrPtrs *a;
 
-       next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
-       for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) {
-           thread((StgClosure **)p);
-       }
-       continue;
+          a = (StgMutArrPtrs*)p;
+          for (p = (P_)a->payload; p < (P_)&a->payload[a->ptrs]; p++) {
+              thread((StgClosure **)p);
+          }
+          continue;
       }
 
-    case TSO:
-       thread_TSO((StgTSO *)p);
-       continue;
+    case SMALL_MUT_ARR_PTRS_CLEAN:
+    case SMALL_MUT_ARR_PTRS_DIRTY:
+    case SMALL_MUT_ARR_PTRS_FROZEN:
+    case SMALL_MUT_ARR_PTRS_FROZEN0:
+      // follow everything 
+      {
+          StgSmallMutArrPtrs *a;
+
+          a = (StgSmallMutArrPtrs*)p;
+          for (p = (P_)a->payload; p < (P_)&a->payload[a->ptrs]; p++) {
+              thread((StgClosure **)p);
+          }
+          continue;
+      }
+
+    case STACK:
+    {
+        StgStack *stack = (StgStack*)p;
+        thread_stack(stack->sp, stack->stack + stack->stack_size);
+        continue;
+    }
 
     case AP_STACK:
        thread_AP_STACK((StgAP_STACK *)p);
@@ -613,14 +614,13 @@ thread_obj (StgInfoTable *info, StgPtr p)
 
     case FUN:
     case CONSTR:
-    case STABLE_NAME:
-    case IND_PERM:
+    case PRIM:
+    case MUT_PRIM:
     case MUT_VAR_CLEAN:
     case MUT_VAR_DIRTY:
-    case CAF_BLACKHOLE:
-    case SE_CAF_BLACKHOLE:
-    case SE_BLACKHOLE:
+    case TVAR:
     case BLACKHOLE:
+    case BLOCKING_QUEUE:
     {
        StgPtr end;
        
@@ -635,6 +635,7 @@ thread_obj (StgInfoTable *info, StgPtr p)
     case WEAK:
     {
        StgWeak *w = (StgWeak *)p;
+       thread(&w->cfinalizers);
        thread(&w->key);
        thread(&w->value);
        thread(&w->finalizer);
@@ -654,8 +655,8 @@ thread_obj (StgInfoTable *info, StgPtr p)
        return p + sizeofW(StgMVar);
     }
     
-    case IND_OLDGEN:
-    case IND_OLDGEN_PERM:
+    case IND:
+    case IND_PERM:
        thread(&((StgInd *)p)->indirectee);
        return p + sizeofW(StgInd);
 
@@ -684,42 +685,40 @@ thread_obj (StgInfoTable *info, StgPtr p)
     case MUT_ARR_PTRS_FROZEN0:
        // follow everything 
     {
-       StgPtr next;
-       
-       next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p);
-       for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) {
+        StgMutArrPtrs *a;
+
+        a = (StgMutArrPtrs *)p;
+       for (p = (P_)a->payload; p < (P_)&a->payload[a->ptrs]; p++) {
            thread((StgClosure **)p);
        }
-       return p;
+
+       return (StgPtr)a + mut_arr_ptrs_sizeW(a);
     }
-    
-    case TSO:
-       return thread_TSO((StgTSO *)p);
-    
-    case TVAR_WATCH_QUEUE:
+
+    case SMALL_MUT_ARR_PTRS_CLEAN:
+    case SMALL_MUT_ARR_PTRS_DIRTY:
+    case SMALL_MUT_ARR_PTRS_FROZEN:
+    case SMALL_MUT_ARR_PTRS_FROZEN0:
+       // follow everything 
     {
-        StgTVarWatchQueue *wq = (StgTVarWatchQueue *)p;
-       thread_(&wq->closure);
-       thread_(&wq->next_queue_entry);
-       thread_(&wq->prev_queue_entry);
-       return p + sizeofW(StgTVarWatchQueue);
+        StgSmallMutArrPtrs *a;
+
+        a = (StgSmallMutArrPtrs *)p;
+       for (p = (P_)a->payload; p < (P_)&a->payload[a->ptrs]; p++) {
+           thread((StgClosure **)p);
+       }
+
+       return (StgPtr)a + small_mut_arr_ptrs_sizeW(a);
     }
     
-    case TVAR:
-    {
-        StgTVar *tvar = (StgTVar *)p;
-       thread((void *)&tvar->current_value);
-       thread((void *)&tvar->first_watch_queue_entry);
-       return p + sizeofW(StgTVar);
-    }
+    case TSO:
+       return thread_TSO((StgTSO *)p);
     
-    case TREC_HEADER:
+    case STACK:
     {
-        StgTRecHeader *trec = (StgTRecHeader *)p;
-       thread_(&trec->enclosing_trec);
-       thread_(&trec->current_chunk);
-       thread_(&trec->invariants_to_check);
-       return p + sizeofW(StgTRecHeader);
+        StgStack *stack = (StgStack*)p;
+        thread_stack(stack->sp, stack->stack + stack->stack_size);
+        return p + stack_sizeW(stack);
     }
 
     case TREC_CHUNK:
@@ -736,23 +735,6 @@ thread_obj (StgInfoTable *info, StgPtr p)
        return p + sizeofW(StgTRecChunk);
     }
 
-    case ATOMIC_INVARIANT:
-    {
-        StgAtomicInvariant *invariant = (StgAtomicInvariant *)p;
-       thread_(&invariant->code);
-       thread_(&invariant->last_execution);
-       return p + sizeofW(StgAtomicInvariant);
-    }
-
-    case INVARIANT_CHECK_QUEUE:
-    {
-        StgInvariantCheckQueue *queue = (StgInvariantCheckQueue *)p;
-       thread_(&queue->invariant);
-       thread_(&queue->my_execution);
-       thread_(&queue->next_queue_entry);
-       return p + sizeofW(StgInvariantCheckQueue);
-    }
-
     default:
        barf("update_fwd: unknown/strange object  %d", (int)(info->type));
        return NULL;
@@ -790,7 +772,7 @@ update_fwd_compact( bdescr *blocks )
 #endif
     bdescr *bd, *free_bd;
     StgInfoTable *info;
-    nat size;
+    StgWord size;
     StgWord iptr;
 
     bd = blocks;
@@ -838,7 +820,7 @@ update_fwd_compact( bdescr *blocks )
             // that if (p&BLOCK_MASK) >= (free&BLOCK_MASK), then we
             // definitely have enough room.  Also see bug #1147.
             iptr = get_threaded_info(p);
-           info = INFO_PTR_TO_STRUCT(UNTAG_CLOSURE((StgClosure *)iptr));
+           info = INFO_PTR_TO_STRUCT((StgInfoTable *)UNTAG_CLOSURE((StgClosure *)iptr));
 
            q = p;
 
@@ -846,15 +828,15 @@ update_fwd_compact( bdescr *blocks )
 
            size = p - q;
            if (free + size > free_bd->start + BLOCK_SIZE_W) {
-               // unset the next bit in the bitmap to indicate that
+               // set 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);
+               mark(q+1,bd);
                free_bd = free_bd->link;
                free = free_bd->start;
            } else {
-               ASSERT(is_marked(q+1,bd));
+               ASSERT(!is_marked(q+1,bd));
            }
 
            unthread(q,(StgWord)free + GET_CLOSURE_TAG((StgClosure *)iptr));
@@ -866,8 +848,8 @@ update_fwd_compact( bdescr *blocks )
     }
 }
 
-static nat
-update_bkwd_compact( step *stp )
+static W_
+update_bkwd_compact( generation *gen )
 {
     StgPtr p, free;
 #if 0
@@ -875,10 +857,11 @@ update_bkwd_compact( step *stp )
 #endif
     bdescr *bd, *free_bd;
     StgInfoTable *info;
-    nat size, free_blocks;
+    StgWord size;
+    W_ free_blocks;
     StgWord iptr;
 
-    bd = free_bd = stp->old_blocks;
+    bd = free_bd = gen->old_blocks;
     free = free_bd->start;
     free_blocks = 1;
 
@@ -913,7 +896,7 @@ update_bkwd_compact( step *stp )
            }
 #endif
 
-           if (!is_marked(p+1,bd)) {
+           if (is_marked(p+1,bd)) {
                // don't forget to update the free ptr in the block desc.
                free_bd->free = free;
                free_bd = free_bd->link;
@@ -923,7 +906,7 @@ update_bkwd_compact( step *stp )
 
             iptr = get_threaded_info(p);
            unthread(p, (StgWord)free + GET_CLOSURE_TAG((StgClosure *)iptr));
-           ASSERT(LOOKS_LIKE_INFO_PTR(((StgClosure *)p)->header.info));
+           ASSERT(LOOKS_LIKE_INFO_PTR((StgWord)((StgClosure *)p)->header.info));
            info = get_itbl((StgClosure *)p);
            size = closure_sizeW_((StgClosure *)p,info);
 
@@ -932,8 +915,8 @@ update_bkwd_compact( step *stp )
            }
 
            // relocate TSOs
-           if (info->type == TSO) {
-               move_TSO((StgTSO *)p, (StgTSO *)free);
+            if (info->type == STACK) {
+                move_STACK((StgStack *)p, (StgStack *)free);
            }
 
            free += size;
@@ -955,35 +938,45 @@ update_bkwd_compact( step *stp )
 }
 
 void
-compact(void)
+compact(StgClosure *static_objects)
 {
-    nat g, s, blocks;
-    step *stp;
+    W_ n, g, blocks;
+    generation *gen;
 
     // 1. thread the roots
-    GetRoots((evac_fn)thread);
+    markCapabilities((evac_fn)thread_root, NULL);
+
+    markScheduler((evac_fn)thread_root, NULL);
 
     // the weak pointer lists...
-    if (weak_ptr_list != NULL) {
-       thread((void *)&weak_ptr_list);
+    for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
+        if (generations[g].weak_ptr_list != NULL) {
+            thread((void *)&generations[g].weak_ptr_list);
+        }
     }
-    if (old_weak_ptr_list != NULL) {
-       thread((void *)&old_weak_ptr_list); // tmp
+
+    if (dead_weak_ptr_list != NULL) {
+        thread((void *)&dead_weak_ptr_list); // tmp
     }
 
     // mutable lists
     for (g = 1; g < RtsFlags.GcFlags.generations; g++) {
-       bdescr *bd;
-       StgPtr p;
-       for (bd = generations[g].mut_list; bd != NULL; bd = bd->link) {
-           for (p = bd->start; p < bd->free; p++) {
-               thread((StgClosure **)p);
-           }
-       }
+        bdescr *bd;
+        StgPtr p;
+        for (n = 0; n < n_capabilities; n++) {
+            for (bd = capabilities[n]->mut_lists[g];
+                 bd != NULL; bd = bd->link) {
+                for (p = bd->start; p < bd->free; p++) {
+                    thread((StgClosure **)p);
+                }
+            }
+        }
     }
 
     // the global thread list
-    thread((void *)&all_threads);
+    for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
+        thread((void *)&generations[g].threads);
+    }
 
     // any threads resurrected during this GC
     thread((void *)&resurrected_threads);
@@ -991,48 +984,50 @@ compact(void)
     // the task list
     {
        Task *task;
-       for (task = all_tasks; task != NULL; task = task->all_link) {
-           if (task->tso) {
-               thread_(&task->tso);
-           }
+        InCall *incall;
+        for (task = all_tasks; task != NULL; task = task->all_next) {
+            for (incall = task->incall; incall != NULL; 
+                 incall = incall->prev_stack) {
+                if (incall->tso) {
+                    thread_(&incall->tso);
+                }
+            }
        }
     }
 
     // the static objects
-    thread_static(gct->scavenged_static_objects /* ToDo: ok? */);
+    thread_static(static_objects /* ToDo: ok? */);
 
     // the stable pointer table
-    threadStablePtrTable((evac_fn)thread);
+    threadStableTables((evac_fn)thread_root, NULL);
 
     // the CAF list (used by GHCi)
-    markCAFs((evac_fn)thread);
+    markCAFs((evac_fn)thread_root, NULL);
 
     // 2. update forward ptrs
     for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
-       for (s = 0; s < generations[g].n_steps; s++) {
-           if (g==0 && s ==0) continue;
-           stp = &generations[g].steps[s];
-           debugTrace(DEBUG_gc, "update_fwd:  %d.%d", 
-                      stp->gen->no, stp->no);
-
-           update_fwd(stp->blocks);
-           update_fwd_large(stp->scavenged_large_objects);
-           if (g == RtsFlags.GcFlags.generations-1 && stp->old_blocks != NULL) {
-               debugTrace(DEBUG_gc, "update_fwd:  %d.%d (compact)",
-                          stp->gen->no, stp->no);
-               update_fwd_compact(stp->old_blocks);
-           }
+        gen = &generations[g];
+        debugTrace(DEBUG_gc, "update_fwd:  %d", g);
+
+        update_fwd(gen->blocks);
+        for (n = 0; n < n_capabilities; n++) {
+            update_fwd(gc_threads[n]->gens[g].todo_bd);
+            update_fwd(gc_threads[n]->gens[g].part_list);
+        }
+        update_fwd_large(gen->scavenged_large_objects);
+        if (g == RtsFlags.GcFlags.generations-1 && gen->old_blocks != NULL) {
+            debugTrace(DEBUG_gc, "update_fwd:  %d (compact)", g);
+            update_fwd_compact(gen->old_blocks);
        }
     }
 
     // 3. update backward ptrs
-    stp = &oldest_gen->steps[0];
-    if (stp->old_blocks != NULL) {
-       blocks = update_bkwd_compact(stp);
+    gen = oldest_gen;
+    if (gen->old_blocks != NULL) {
+       blocks = update_bkwd_compact(gen);
        debugTrace(DEBUG_gc, 
-                  "update_bkwd: %d.%d (compact, old: %d blocks, now %d blocks)",
-                  stp->gen->no, stp->no,
-                  stp->n_old_blocks, blocks);
-       stp->n_old_blocks = blocks;
+                  "update_bkwd: %d (compact, old: %d blocks, now %d blocks)",
+                  gen->no, gen->n_old_blocks, blocks);
+       gen->n_old_blocks = blocks;
     }
 }