What are the current rules about object duplication during GC?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

What are the current rules about object duplication during GC?

Ryan Newton
Is the status quo still the same as it was in this paper?

http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/par-gc-ismm08.pdf

That is, there is a low-probability that a race will result in immutable
objects being duplicated, but not mutable objects.  But that leaves me
wondering exactly which types are currently included in the duplicatable
vs. "take the lock" category [2].

The reason I'm asking is because *defeating GHC compile-time and runtime
optimizations* is precisely the goal of the recent work to make a
safe/reliable infrastructure for CAS-based lockfree data structures in GHC.
 For example, the atomic-primops package uses the Any kind and type
coercions to store objects (pointers) in a form that makes them opaque to
the compiler, preventing them from being unboxed and reboxed (changing
pointer identity).

Actually, the current policy of this library that false negatives (failing
CAS) must be tolerated, which is *usually* not an onerous obligation.  So
if the heap objects in question CAN be duplicated, that is still ok, but I
would like to know if it is the case, that is, if Any is treated any
differently than, say, Int.

My guess is *no, *but I'd like to confirm this.  That is, it seems
that Anyeffects the compiler (which promises
not to enter the
pointer<http://www.haskell.org/ghc/docs/7.6.3/html/libraries/ghc-prim-0.3.0.0/GHC-Prim.html#g:25>),
but the physical representation of a thunk or function doesn't change, and
thus the GC must treat those objects exactly as it would if they were
*not*coerced to
Any.  Sound right?

Cheers,
  -Ryan

[1] P.S. The places I checked before asking on this list were here:
  http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC

And here:  http://ghc.haskell.org/trac/ghc/wiki/GarbageCollectorNotes

If there is newer documentation for the GC, please let me know.

[2] One hint is on line 531 of
StgMiscClosures.cmm<https://github.com/ghc/ghc/blob/d61c623ed6b2d352474a7497a65015dbf6a72e12/rts/StgMiscClosures.cmm#L531>
:

// PRIM rather than CONSTR, because PRIM objects cannot be duplicated by
the GC.

Yet there are 62 different types of objects in ClosureTypes.hs, so I'm not
sure what all the rules are.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20130821/5000181e/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

What are the current rules about object duplication during GC?

Edward Z. Yang
That's right, 'Any' exists at the type level but the rules by which
locked or unlocked evacuation are based off of closure type.  The
relevant code is in rts/sm/Evac.c: look at copy_tag versus copy_tag_nolock.
Unlocked copy is only done for a small number of closure types, although
they do encompass quite a lot of what will be on the heap.

Edward

Excerpts from Ryan Newton's message of Wed Aug 21 14:10:24 -0700 2013:

> Is the status quo still the same as it was in this paper?
>
> http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/par-gc-ismm08.pdf
>
> That is, there is a low-probability that a race will result in immutable
> objects being duplicated, but not mutable objects.  But that leaves me
> wondering exactly which types are currently included in the duplicatable
> vs. "take the lock" category [2].
>
> The reason I'm asking is because *defeating GHC compile-time and runtime
> optimizations* is precisely the goal of the recent work to make a
> safe/reliable infrastructure for CAS-based lockfree data structures in GHC.
>  For example, the atomic-primops package uses the Any kind and type
> coercions to store objects (pointers) in a form that makes them opaque to
> the compiler, preventing them from being unboxed and reboxed (changing
> pointer identity).
>
> Actually, the current policy of this library that false negatives (failing
> CAS) must be tolerated, which is *usually* not an onerous obligation.  So
> if the heap objects in question CAN be duplicated, that is still ok, but I
> would like to know if it is the case, that is, if Any is treated any
> differently than, say, Int.
>
> My guess is *no, *but I'd like to confirm this.  That is, it seems
> that Anyeffects the compiler (which promises
> not to enter the
> pointer<http://www.haskell.org/ghc/docs/7.6.3/html/libraries/ghc-prim-0.3.0.0/GHC-Prim.html#g:25>),
> but the physical representation of a thunk or function doesn't change, and
> thus the GC must treat those objects exactly as it would if they were
> *not*coerced to
> Any.  Sound right?
>
> Cheers,
>   -Ryan
>
> [1] P.S. The places I checked before asking on this list were here:
>   http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
>
> And here:  http://ghc.haskell.org/trac/ghc/wiki/GarbageCollectorNotes
>
> If there is newer documentation for the GC, please let me know.
>
> [2] One hint is on line 531 of
> StgMiscClosures.cmm<https://github.com/ghc/ghc/blob/d61c623ed6b2d352474a7497a65015dbf6a72e12/rts/StgMiscClosures.cmm#L531>
> :
>
> // PRIM rather than CONSTR, because PRIM objects cannot be duplicated by
> the GC.
>
> Yet there are 62 different types of objects in ClosureTypes.hs, so I'm not
> sure what all the rules are.