Changes between Version 29 and Version 30 of Commentary/Rts/Storage/HeapObjects


Ignore:
Timestamp:
Jul 12, 2013 9:12:03 AM (10 months ago)
Author:
ezyang
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Rts/Storage/HeapObjects

    v29 v30  
    228228Thunks have pointers-first layout: 
    229229 
    230 || Header || Pointers... || Non-pointers... || 
     230|| Header || (empty) || Pointers... || Non-pointers... || 
    231231 
    232232As for function closures, the payload contains the free variables of 
     
    248248 
    249249 * {{{f_info}}} is f's info table. 
     250 
     251The empty padding is to allow thunk update code to overwrite the target of an indirection without clobbering any of the saved free variables. This means we can do thunk update without synchronization, which is a big deal. 
    250252 
    251253=== Selector thunks === 
     
    339341Since the payload is a chunk of stack, the GC can use its normal stack-walking code to traverse it. 
    340342 
    341 {{{AP_STACK}}} closures are built by {{{raiseAsync()}}} in [source:rts/RaiseAsync.c] when an [wiki:Commentary/Rts/AsyncExceptions asynchronous exception] is raised. 
     343{{{AP_STACK}}} closures are built by {{{raiseAsync()}}} in [source:rts/RaiseAsync.c] when an [wiki:Commentary/Rts/AsyncExceptions asynchronous exception] is raised. It's fairly typical for the end of an AP_STACK's payload to have another AP_STACK: you'll get one per update frame. 
    342344 
    343345=== Indirections === 
     
    375377{{{BLACKHOLE}}}, {{{CAF_BLACKHOLE}}} 
    376378 
    377 Black holes represent thunks which are under evaluation by another thread (that thread is said to have claimed the thunk).  Attempting to evaluate a black hole causes a thread to block until the thread who claimed the thunk either finishes evaluating the thunk or dies.  You can read more about black holes in the paper 'Haskell on a Shared-Memory Multiprocessor'. 
    378  
    379 Mysteriously enough, sometimes black holes act just like a normal indirection. The gory details are in `stg_BLACKHOLE_info`, but the short version is that if the indirectee has no tagged, then we assume that it is the TSO that has claimed the thunk; if the indirectee is tagged, then it is just a normal indirection. The moral of the story is you should enter a closure to be sure ;) 
     379Black holes represent thunks which are under evaluation by another thread (that thread is said to have claimed the thunk).   Attempting to evaluate a black hole causes a thread to block until the thread who claimed the thunk either finishes evaluating the thunk or dies.  You can read more about black holes in the paper 'Haskell on a Shared-Memory Multiprocessor'. Black holes have the same layout as indirections. 
     380 
     381|| Header || Target closure || 
     382 
     383Sometimes black holes are just ordinary indirection. Check `stg_BLACKHOLE_info` for the final word: if the indirectee has no tag, then we assume that it is the TSO that has claimed the thunk; if the indirectee is tagged, then it is just a normal indirection. (EZY: I think this optimization is to avoid having to do two memory writes on thunk update; we don't bother updating the header, only the target.) 
     384 
     385When eager blackholing is enabled, the black hole that is written is not a true black hole, but an eager black hole.  True black holes are synchronized, and guarantee that only one black hole is claimed (this property is used to implement non-dupable unsafePerformIO).  Eager black holes are not synchronized; eager black hole are converted into true black holes in ThreadPaused.c. Incidentally, this facility is also used to convert update frames to black holes; this is important for eliminating a space leak caused by the thunk under evaluation retaining too much data (overwriting it with a black hole frees up variable.) 
    380386 
    381387=== Arrays === 
     
    384390{{{MUT_ARR_PTRS_FROZEN}}} 
    385391 
     392Non-pointer arrays are straightforward: 
     393 
     394||| Header ||| Bytes ||| Array payload ||| 
     395 
     396Arrays with pointers are a little more complicated, they include a card table, which is used by the GC to know what segments of the array to traverse as roots (the card table is modified by the GC write barrier): 
     397 
     398||| Header ||| Ptrs ||| Size ||| Array payload + card table ||| 
     399 
     400You can access the card table by using `mutArrPtrsCard(array, element index)`, which gives you the address of the card for that index. 
     401 
    386402=== MVars === 
    387403 
    388404{{{MVar}}} 
    389405 
     406MVars have a queue of the TSOs blocking on them along with their value: 
     407 
     408|| Header || Head of queue || Tail of queue || Value || 
     409 
     410An MVar can be in several states. It can be empty (in which case the value is actually just a `stg_END_TSO_QUEUE_closure`) or it can be full. When it is full, the queue of TSOs are those waiting to put; when it is empty, the queue of TSOs are those waiting to read and take (with readers first). Like many mutable objects, MVars have CLEAN and DIRTY headers to avoid reapplying a write barrier when an MVar is already dirty. 
     411 
    390412=== Weak pointers === 
    391413 
     
    402424TSOs are ordinary objects that live in the heap, so we can use the existing allocation and garbage collection machinery to manage them.  This gives us one important benefit: the garbage collector can detect when a blocked thread is unreachable, and hence can never become runnable again.  When this happens, we can notify the thread by sending it the {{{BlockedIndefinitely}}} exception. 
    403425 
    404 GHC keeps stacks contiguous, there are no "stack chunk" objects.  This is simpler, but means that when growing a stack we have to copy the old contents to a larger area (see {{{threadStackOverflow()}}} in [source:rts/Schedule.c]). (EZY: I'm pretty sure this is not the case anymore, see http://hackage.haskell.org/trac/ghc/blog/stack-chunks) 
     426GHC keeps divides stacks into stack chunks, with logic to handle stack underflow and overflow: http://hackage.haskell.org/trac/ghc/blog/stack-chunks 
    405427 
    406428The TSO structure contains several fields.  For full details see [source:includes/rts/storage/TSO.h].  Some of the more important fields are: