Sealing buckets

[wks]

I am pondering why bugs like #770 and #778 exists at all. Superficially, those bugs are caused by 'a new bucket is opened while some thread (most likely the coordinator that is about to be removed completely) can still add new packets to old open buckets'. But I think there is a deeper reason.

Currently, the rules governing opening buckets are quite informal and naive:

• The Unconstrained bucket is always open.
• The first STW bucket (Prepare) can be opened when all mutators paused.
• Any subsequent STW bucket is opened when packets in all previous STW buckets are empty, and all workers have parked.

But what is the property that those rules try to guarantee? I think those rules exist for maintaining the dependencies between work packets. For example, we can only start sweeping when we visited all reachable objects. So we place the Sweep packet in the Release bucket, and the ProcessEdgesWork packets in the Closure bucket which is before Release. By 'visited all reachable objects', we mean all existing ProcessEdgesWork packets have been executed, and no more ProcessEdgesWork packets can be generated. The latter is the reason why we want workers to stop before opening new buckets because workers can add new packets while executing existing packets. (And when we had a coordinator, the coordinator can add packets, and the coordinator is not governed by the 'all workers have parked' predicate, which is the source of many previous bugs.)

I want to strengthen the rules by adding the ability to 'seal buckets'. When opening a new bucket, we seal the previous bucket so that we can no longer add more packets into them. Now a work bucket has three states:

Operation	Closed	Open	Sealed
add packet	yes	yes	no
remove packet	no	yes	no

When GC starts, the state of all STW buckets are Closed. Buckets are opened as before. But whenever we open an STW bucket (except Prepare), we seal the previous buckets so that no work packets can be added.

If our existing plans and work packets are implemented correctly, they should not add packets to sealed buckets. No work packets need to be modified, and they will just work after we add the new Sealed state to buckets. If new buckets are opened while a thread can still add packets to an old bucket, it will be an error (because it is trying to add a packet into a sealed bucket).

This can be generalised to bucket graphs instead of the current linear bucket sequence. A work bucket can be opened only if its dependent buckets are all sealed.

[qinsoon]

This issue is based on the current implementation, and we agreed that the current implementation does not precisely reflect the original design. See my response in #774 (comment).

[steveblackburn]

@wenyuzhao is actively working on the re-design of work packets as part of his PhD. This issue is subsumed by his work, IMO.