[concurrency-interest] Fences and card tables
gil at azulsystems.com
Sun Aug 23 06:34:28 EDT 2015
For generational collection the ordering required by a collector's reference store barrier depends on the collector mechanisms. The purpose of the reference store barrier in generational collectors is to maintain remembered sets from older to younger generations. A card table is a good example of such a remembered set.
When the collector performs younger generation collections in monolithic stop-the-world pauses, the only ordering requirement between a card mark store and the associated reference store is that they cannot be separated by a safepoint. They can occur in any order as long as that requirement is maintained. This describes the situation for all current young generation collectors in HotSpot (AFAIK Zing's C4 is still the only non-STW young generation collector in a shipping JVM).
When the young generation collection can run concurrently with mutator execution the typical ordering requirement would be for the recording of generational remembered set information (e.g. a card table store) to be visible to GC threads before the reference store itself. Hence a logical StoreStore fence exists between the two, and must be enforced by all code generation and executing CPUs. Note that the requirement for the two stores to not be separated by a safepoint is usually still there as well (and that requirement is not satisfied by a StoreStore barrier). Also note that I use "typically" and "usually" above, because correct concurrent card scanning algorithms that do not carry these specific requirements certainly exist. As noted, this is not relevant for HotSpot's generational behavior because the younggens are all STW. But in the specific example of Zing/C4 we do use a card table, we do scan it concurrently, and we do require both the StoreStore order and the not-separated-but-safepoint requirement.
Beyond generational collection, It is VERY important to remember that some collectors use reference store barriers for purposes other than generational remembered set tracking.
E.g. to my understanding CMS uses the same card table store to *also* track mutations during concurrent marking of the oldgen. So while the generational part of the collector has no concurrency or ordering issues, the oldgen marking functionality does require the StoreStore ordering in addition to the not-separated-by-safepoint requirement.
Similarly, G1 uses a reference store barrier (not just a card table store) to enforce its mostly concurrent marker's snapshot-at-the-beginning (SATB) invariants (in addition to doing reference set tracking). As such, it too *might* need the StoreStore order. I'm less sure about that one, because I think SATB might do fine without the orderinggucen the information captured by the barrier.
Sent from Gil's iPhone
> On Aug 23, 2015, at 2:23 AM, Andrew Haley <aph at redhat.com> wrote:
>> On 08/21/2015 02:16 PM, Doug Lea wrote:
>>> On 08/20/2015 01:50 PM, Andrew Haley wrote:
>>> Just to reassure me: a card table write in a generational collector
>>> only needs a StoreStore fence, not a release. Is that right?
>> Definitive answers might be collector-specific.
>> So you might try asking on hotspot-gc-dev?
> Sure, I understand that. My question was more general, following
> Hans's sometimes surprising observations of the failures of StoreStore
> fences. A card table store is merely a constant written into a table,
> and that constant is fixed. All that is required is that the
> preceding reference store and the card table store are observable to
> all threads in the order they were written. Hence a StoreStore fence.
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
More information about the Concurrency-interest