rts/sm/MarkWeak.c

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-2008
   4  *
   5  * Weak pointers and weak-like things in the GC
   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 "MarkWeak.h"
  18 #include "GC.h"
  19 #include "GCThread.h"
  20 #include "Evac.h"
  21 #include "Trace.h"
  22 #include "Schedule.h"
  23 #include "Weak.h"
  24 #include "Storage.h"
  25
  26 /* -----------------------------------------------------------------------------
  27    Weak Pointers
  28
  29    traverse_weak_ptr_list is called possibly many times during garbage
  30    collection.  It returns a flag indicating whether it did any work
  31    (i.e. called evacuate on any live pointers).
  32
  33    Invariant: traverse_weak_ptr_list is called when the heap is in an
  34    idempotent state.  That means that there are no pending
  35    evacuate/scavenge operations.  This invariant helps the weak
  36    pointer code decide which weak pointers are dead - if there are no
  37    new live weak pointers, then all the currently unreachable ones are
  38    dead.
  39
  40    For generational GC: we just don't try to finalize weak pointers in
  41    older generations than the one we're collecting.  This could
  42    probably be optimised by keeping per-generation lists of weak
  43    pointers, but for a few weak pointers this scheme will work.
  44
  45    There are three distinct stages to processing weak pointers:
  46
  47    - weak_stage == WeakPtrs
  48
  49      We process all the weak pointers whos keys are alive (evacuate
  50      their values and finalizers), and repeat until we can find no new
  51      live keys.  If no live keys are found in this pass, then we
  52      evacuate the finalizers of all the dead weak pointers in order to
  53      run them.
  54
  55    - weak_stage == WeakThreads
  56
  57      Now, we discover which *threads* are still alive.  Pointers to
  58      threads from the all_threads and main thread lists are the
  59      weakest of all: a pointers from the finalizer of a dead weak
  60      pointer can keep a thread alive.  Any threads found to be unreachable
  61      are evacuated and placed on the resurrected_threads list so we
  62      can send them a signal later.
  63
  64    - weak_stage == WeakDone
  65
  66      No more evacuation is done.
  67
  68    -------------------------------------------------------------------------- */
  69
  70 /* Which stage of processing various kinds of weak pointer are we at?
  71  * (see traverse_weak_ptr_list() below for discussion).
  72  */
  73 typedef enum { WeakPtrs, WeakThreads, WeakDone } WeakStage;
  74 static WeakStage weak_stage;
  75
  76 /* Weak pointers
  77  */
  78 StgWeak *old_weak_ptr_list; // also pending finaliser list
  79
  80 // List of threads found to be unreachable
  81 StgTSO *resurrected_threads;
  82
  83 // List of blocked threads found to have pending throwTos
  84 StgTSO *exception_threads;
  85
  86 static void resurrectUnreachableThreads (step *stp);
  87 static rtsBool tidyThreadList (step *stp);
  88
  89 void
  90 initWeakForGC(void)
  91 {
  92     old_weak_ptr_list = weak_ptr_list;
  93     weak_ptr_list = NULL;
  94     weak_stage = WeakPtrs;
  95     resurrected_threads = END_TSO_QUEUE;
  96     exception_threads = END_TSO_QUEUE;
  97 }
  98
  99 rtsBool
 100 traverseWeakPtrList(void)
 101 {
 102   StgWeak *w, **last_w, *next_w;
 103   StgClosure *new;
 104   rtsBool flag = rtsFalse;
 105   const StgInfoTable *info;
 106
 107   switch (weak_stage) {
 108
 109   case WeakDone:
 110       return rtsFalse;
 111
 112   case WeakPtrs:
 113       /* doesn't matter where we evacuate values/finalizers to, since
 114        * these pointers are treated as roots (iff the keys are alive).
 115        */
 116       gct->evac_step = 0;
 117
 118       last_w = &old_weak_ptr_list;
 119       for (w = old_weak_ptr_list; w != NULL; w = next_w) {
 120
 121           /* There might be a DEAD_WEAK on the list if finalizeWeak# was
 122            * called on a live weak pointer object.  Just remove it.
 123            */
 124           if (w->header.info == &stg_DEAD_WEAK_info) {
 125               next_w = ((StgDeadWeak *)w)->link;
 126               *last_w = next_w;
 127               continue;
 128           }
 129
 130           info = w->header.info;
 131           if (IS_FORWARDING_PTR(info)) {
 132               next_w = (StgWeak *)UN_FORWARDING_PTR(info);
 133               *last_w = next_w;
 134               continue;
 135           }
 136
 137           switch (INFO_PTR_TO_STRUCT(info)->type) {
 138
 139           case WEAK:
 140               /* Now, check whether the key is reachable.
 141                */
 142               new = isAlive(w->key);
 143               if (new != NULL) {
 144                   w->key = new;
 145                   // evacuate the value and finalizer
 146                   evacuate(&w->value);
 147                   evacuate(&w->finalizer);
 148                   // remove this weak ptr from the old_weak_ptr list
 149                   *last_w = w->link;
 150                   // and put it on the new weak ptr list
 151                   next_w  = w->link;
 152                   w->link = weak_ptr_list;
 153                   weak_ptr_list = w;
 154                   flag = rtsTrue;
 155
 156                   debugTrace(DEBUG_weak,
 157                              "weak pointer still alive at %p -> %p",
 158                              w, w->key);
 159                   continue;
 160               }
 161               else {
 162                   last_w = &(w->link);
 163                   next_w = w->link;
 164                   continue;
 165               }
 166
 167           default:
 168               barf("traverseWeakPtrList: not WEAK");
 169           }
 170       }
 171
 172       /* If we didn't make any changes, then we can go round and kill all
 173        * the dead weak pointers.  The old_weak_ptr list is used as a list
 174        * of pending finalizers later on.
 175        */
 176       if (flag == rtsFalse) {
 177           for (w = old_weak_ptr_list; w; w = w->link) {
 178               evacuate(&w->finalizer);
 179           }
 180
 181           // Next, move to the WeakThreads stage after fully
 182           // scavenging the finalizers we've just evacuated.
 183           weak_stage = WeakThreads;
 184       }
 185
 186       return rtsTrue;
 187
 188   case WeakThreads:
 189       /* Now deal with the step->threads lists, which behave somewhat like
 190        * the weak ptr list.  If we discover any threads that are about to
 191        * become garbage, we wake them up and administer an exception.
 192        */
 193   {
 194       nat g, s, n;
 195
 196       // Traverse thread lists for generations we collected...
 197       for (n = 0; n < n_capabilities; n++) {
 198           if (tidyThreadList(&nurseries[n])) {
 199               flag = rtsTrue;
 200           }
 201       }
 202       for (g = 0; g <= N; g++) {
 203           for (s = 0; s < generations[g].n_steps; s++) {
 204               if (tidyThreadList(&generations[g].steps[s])) {
 205                   flag = rtsTrue;
 206               }
 207           }
 208       }
 209
 210       /* If we evacuated any threads, we need to go back to the scavenger.
 211        */
 212       if (flag) return rtsTrue;
 213
 214       /* And resurrect any threads which were about to become garbage.
 215        */
 216       {
 217           nat g, s, n;
 218
 219           for (n = 0; n < n_capabilities; n++) {
 220               resurrectUnreachableThreads(&nurseries[n]);
 221           }
 222           for (g = 0; g <= N; g++) {
 223               for (s = 0; s < generations[g].n_steps; s++) {
 224                   resurrectUnreachableThreads(&generations[g].steps[s]);
 225               }
 226           }
 227       }
 228
 229       /* Finally, we can update the blackhole_queue.  This queue
 230        * simply strings together TSOs blocked on black holes, it is
 231        * not intended to keep anything alive.  Hence, we do not follow
 232        * pointers on the blackhole_queue until now, when we have
 233        * determined which TSOs are otherwise reachable.  We know at
 234        * this point that all TSOs have been evacuated, however.
 235        */
 236       {
 237           StgTSO **pt;
 238           for (pt = &blackhole_queue; *pt != END_TSO_QUEUE; pt = &((*pt)->_link)) {
 239               *pt = (StgTSO *)isAlive((StgClosure *)*pt);
 240               ASSERT(*pt != NULL);
 241           }
 242       }
 243
 244       weak_stage = WeakDone;  // *now* we're done,
 245       return rtsTrue;         // but one more round of scavenging, please
 246   }
 247
 248   default:
 249       barf("traverse_weak_ptr_list");
 250       return rtsTrue;
 251   }
 252 }
 253
 254   static void resurrectUnreachableThreads (step *stp)
 255 {
 256     StgTSO *t, *tmp, *next;
 257
 258     for (t = stp->old_threads; t != END_TSO_QUEUE; t = next) {
 259         next = t->global_link;
 260
 261         // ThreadFinished and ThreadComplete: we have to keep
 262         // these on the all_threads list until they
 263         // become garbage, because they might get
 264         // pending exceptions.
 265         switch (t->what_next) {
 266         case ThreadKilled:
 267         case ThreadComplete:
 268             continue;
 269         default:
 270             tmp = t;
 271             evacuate((StgClosure **)&tmp);
 272             tmp->global_link = resurrected_threads;
 273             resurrected_threads = tmp;
 274         }
 275     }
 276 }
 277
 278 static rtsBool tidyThreadList (step *stp)
 279 {
 280     StgTSO *t, *tmp, *next, **prev;
 281     rtsBool flag = rtsFalse;
 282
 283     prev = &stp->old_threads;
 284
 285     for (t = stp->old_threads; t != END_TSO_QUEUE; t = next) {
 286
 287         tmp = (StgTSO *)isAlive((StgClosure *)t);
 288
 289         if (tmp != NULL) {
 290             t = tmp;
 291         }
 292
 293         ASSERT(get_itbl(t)->type == TSO);
 294         if (t->what_next == ThreadRelocated) {
 295             next = t->_link;
 296             *prev = next;
 297             continue;
 298         }
 299
 300         next = t->global_link;
 301
 302         // This is a good place to check for blocked
 303         // exceptions.  It might be the case that a thread is
 304         // blocked on delivering an exception to a thread that
 305         // is also blocked - we try to ensure that this
 306         // doesn't happen in throwTo(), but it's too hard (or
 307         // impossible) to close all the race holes, so we
 308         // accept that some might get through and deal with
 309         // them here.  A GC will always happen at some point,
 310         // even if the system is otherwise deadlocked.
 311         //
 312         // If an unreachable thread has blocked
 313         // exceptions, we really want to perform the
 314         // blocked exceptions rather than throwing
 315         // BlockedIndefinitely exceptions.  This is the
 316         // only place we can discover such threads.
 317         // The target thread might even be
 318         // ThreadFinished or ThreadKilled.  Bugs here
 319         // will only be seen when running on a
 320         // multiprocessor.
 321         if (t->blocked_exceptions != END_TSO_QUEUE) {
 322             if (tmp == NULL) {
 323                 evacuate((StgClosure **)&t);
 324                 flag = rtsTrue;
 325             }
 326             t->global_link = exception_threads;
 327             exception_threads = t;
 328             *prev = next;
 329             continue;
 330         }
 331
 332         if (tmp == NULL) {
 333             // not alive (yet): leave this thread on the
 334             // old_all_threads list.
 335             prev = &(t->global_link);
 336         }
 337         else {
 338             // alive
 339             *prev = next;
 340
 341             // move this thread onto the correct threads list.
 342             step *new_step;
 343             new_step = Bdescr((P_)t)->step;
 344             t->global_link = new_step->threads;
 345             new_step->threads  = t;
 346         }
 347     }
 348
 349     return flag;
 350 }
 351
 352 /* -----------------------------------------------------------------------------
 353    The blackhole queue
 354
 355    Threads on this list behave like weak pointers during the normal
 356    phase of garbage collection: if the blackhole is reachable, then
 357    the thread is reachable too.
 358    -------------------------------------------------------------------------- */
 359 rtsBool
 360 traverseBlackholeQueue (void)
 361 {
 362     StgTSO *prev, *t, *tmp;
 363     rtsBool flag;
 364     nat type;
 365
 366     flag = rtsFalse;
 367     prev = NULL;
 368
 369     for (t = blackhole_queue; t != END_TSO_QUEUE; prev=t, t = t->_link) {
 370         // if the thread is not yet alive...
 371         if (! (tmp = (StgTSO *)isAlive((StgClosure*)t))) {
 372             // if the closure it is blocked on is either (a) a
 373             // reachable BLAKCHOLE or (b) not a BLACKHOLE, then we
 374             // make the thread alive.
 375             if (!isAlive(t->block_info.closure)) {
 376                 type = get_itbl(t->block_info.closure)->type;
 377                 if (type == BLACKHOLE || type == CAF_BLACKHOLE) {
 378                     continue;
 379                 }
 380             }
 381             evacuate((StgClosure **)&t);
 382             if (prev) {
 383                 prev->_link = t;
 384             } else {
 385                 blackhole_queue = t;
 386             }
 387                  // no write barrier when on the blackhole queue,
 388                  // because we traverse the whole queue on every GC.
 389             flag = rtsTrue;
 390         }
 391     }
 392     return flag;
 393 }
 394
 395 /* -----------------------------------------------------------------------------
 396    After GC, the live weak pointer list may have forwarding pointers
 397    on it, because a weak pointer object was evacuated after being
 398    moved to the live weak pointer list.  We remove those forwarding
 399    pointers here.
 400
 401    Also, we don't consider weak pointer objects to be reachable, but
 402    we must nevertheless consider them to be "live" and retain them.
 403    Therefore any weak pointer objects which haven't as yet been
 404    evacuated need to be evacuated now.
 405    -------------------------------------------------------------------------- */
 406
 407 void
 408 markWeakPtrList ( void )
 409 {
 410   StgWeak *w, **last_w, *tmp;
 411
 412   last_w = &weak_ptr_list;
 413   for (w = weak_ptr_list; w; w = w->link) {
 414       // w might be WEAK, EVACUATED, or DEAD_WEAK (actually CON_STATIC) here
 415       ASSERT(IS_FORWARDING_PTR(w->header.info)
 416              || w->header.info == &stg_DEAD_WEAK_info
 417              || get_itbl(w)->type == WEAK);
 418       tmp = w;
 419       evacuate((StgClosure **)&tmp);
 420       *last_w = w;
 421       last_w = &(w->link);
 422   }
 423 }
 424