Remove `cast_ref_to_mut` related to Prepare and Release

[wks]

Parent: #850

Problem

There are periods in GC when we know some work packets have exclusive access to the Plan instance. Examples include Prepare, Release and EndOfGC. The problem is, we know this fact as humans, but the Rust programming language cannot check if that work packet has exclusive access to Plan, using either compile-time checking or run-time checking. Therefore, we worked around this by casting &Plan to &mut Plan

Possible solution

Because of the dynamic nature of MMTk-VM interaction and the work packet system, it is hard to check whether a thread is the only thread that can access a data structure.

But it is possible to do this dynamically using reference counting. If we can count how many threads have access to a given data structure (for example, MMTk, or Plan), we can let the users "yield" their right to access to that data structure. Once we are sure all read-only users yielded, we can grant another thread (the one running Prepare or other work packets) read-write access. It is checked at run time. If a thread attempts to get read-write access while the read-only user count is greater than 0, it shall panic (which is not as good as compile-time checking in which case unsafe code doesn't compile).

p.s. The same idea can be applied to the parking of GC worker threads. If all workers parked, the last GC worker can gain read-write access and modify work buckets states.

AtomicRefCell is the closest tool for this need. However, AtomicRefCell requires the "handle" instances (Borrow and BorrowMut) to live within the lifetime of the AtomicRefCell itself, with compile-time lifetime checking. Because of this limitation, we can't send the Borrow<T> handle to another thread.

I once made a proof-of-concept project for "lending" some owned data to another thread, with run-time checking. The main difference is, the compiler will not prevent the handles from being sent to other threads. But if the owner of the object dies while it is still lent, it panics. (Sorry. In such a dynamic environment, there is not much the compiler can do.)

[wks]

In Prepare and Release, we call Plan.prepare/release which calls the prepare/release methods of each space. All of those prepare/release methods have &mut self as parameters. Obviously, they are intended to modify the internal states of those spaces.

Case study of ImmixSpace

I had a look at ImmixSpace.

pub struct ImmixSpace<VM: VMBinding> {
    common: CommonSpace<VM>,
    pr: BlockPageResource<VM, Block>,
    pub chunk_map: ChunkMap,
    pub line_mark_state: AtomicU8,
    line_unavail_state: AtomicU8,
    pub reusable_blocks: ReusableBlockPool,
    pub(super) defrag: Defrag,
    lines_consumed: AtomicUsize,
    mark_state: u8,
    scheduler: Arc<GCWorkScheduler<VM>>,
    space_args: ImmixSpaceArgs,
}

pub struct Defrag {
    in_defrag_collection: AtomicBool,
    defrag_space_exhausted: AtomicBool,
    pub mark_histograms: Mutex<Vec<Histogram>>,
    pub defrag_spill_threshold: AtomicUsize,
    available_clean_pages_for_defrag: AtomicUsize,
}

We can see many AtomicXxxx variables here. They are intended to workaround the limitation of & reference in Rust. Take line_mark_state: AtomicU8 and line_unavail_state for example.

They are modified in the following cases:

• line_mark_state is incremented by 1 (wrap back to 1 if exceeding MAX_MARK_STATE) during prepare on every major GC.
• line_unavail_state is updated to the value of line_mark_state during release on every major GC.

They are loaded in the following cases:

• When marking a line, line_mark_state is loaded, and this value is stored to the state of the line.
• When allocating objects, both line_mark_state and line_unavail_state are loaded for searching for available lines.
• When sweeping a block, line_mark_state is loaded, and the value is used to sweep lines.

We see that line_mark_state and line_unavail_state are not used for synchronisation, but used as an ordinary state variable. Atomic variables used for synchronisation are usually updated with atomic read-modify-write operations, and seeing a value loaded from an Atomic variable usually indicates something has "happened before". It is clearly not the case for line_mark_state as can be seen in the following code:

            if !super::BLOCK_ONLY {
                self.line_mark_state.fetch_add(1, Ordering::AcqRel);
                if self.line_mark_state.load(Ordering::Acquire) > Line::MAX_MARK_STATE {
                    self.line_mark_state.store(Line::RESET_MARK_STATE, Ordering::Release);
                }
            }

This means this variable is used for internal mutability (which is still one proper use case of AtomicXxxx probably not a proper use. See below.).

On the other hand, the variable mark_state: u8 has the cast_ref_to_mut problem. It is the object-level mark state. It is assigned in prepare, and loaded when marking one object (in trace_object_{without_moving,with_opportunistic_copy}). It is intended to cycle between 0 and 1 between odd and even GC. But currently we only implemented on-the-side mark bits, so the value of mark_state. Despite of this, it is still assigned in prepare, and it is the only reason why ImmixSpace::prepare need to have a &mut self parameter.

What does this mean?

From what we have seen, the prepare method of ImmixSpace does want to mutate internal states. Currently, other mutable states (including line_mark_state, line_unavail_state, etc.) are either AtomicXxxx fields or allocated in raw memory (for example, metadata), accessed by methods of Address backed by unsafe load/store operations.

So if we just want to eliminate all the instances of cast_ref_to_mut which have undefined behaviour, we can change more variables to AtomicXxxx, protect them with Mutex or AtomicRefCell, allocate them in raw memory, or just use unsafe and handle the safety manually.

However, in the long term, I think we should let the work packet scheduler make the guarantee that some data structures are only used by one work packet in some stage and give the GC worker actual &mut T references, which is idiomatic in Rust and allows the Rust compiler to safely do more aggressive optimisations (for example, eliminating excessive loads under the assumption that if a &T reference exists, no &mut T can point to the same location and modify its value).

Why is AtomicXxxx not good enough?

Atomic variables allow multiple threads to access it concurrently even with a &T reference. However, atomic variables are intended to be used when we know there will be multiple threads accessing it concurrently. Specifically,

• We want the race to be benign, in the sense that when reading from it, we always see a value written by one of the writers (instead of word tearing or crashing the program).
  • For example, multiple threads are computing the same value, and they will all write the result to the same Atomic variable at unspecified times. It doesn't matter which thread computed the result first. Any result shall work.
  • For example, multiple threads attempt to lazily intialise a string. It doesn't matter if one thread overwrote the value written by another thread. The redundant instance will be garbage-collected.
• Or we intentionally use the atomic variable to communicate between threads (i.e. synchronisation), using atomic read-modify-write operations and/or memory order.
  • For example, an AtomicBool indicates a task has finished. If one thread finished the task and store(true, Release), and another thread does load(Acquire) and sees true, the second thread knows the first thread has finished, and the memory order allows the second thread to see the result of memory stores done by the first thread.
  • For example, if multiple threads call swap(true) on an AtomicBool whose initial value is false, only one thread shall see the old value being false and all other threads see the old value being true. This is the basis of mutex locking, and we mark objects this way, too.
  • For example, we use an AtomicUsize as a counter. Each thread that performs fetch_add(1) sees a different value, and that can be used to determine which thread will be waken up next (i.e. the fair lock algorithm).

But the AtomicXxxx variables we updated during prepare and release do not have any races. If MMTk is implemented correctly, no other threads can update those variables (including mark_state, line_mark_state, line_unavail_state, etc.) concurrently. &mut ImmixSpace should really be the proper parameter of the ImmixSpace::prepare method. The problem is, how do we guarantee only one &mut ImmixSpace exists and no &ImmixSpace exist at the same time. I think the key is the algorithm of work packet scheduling. It is the scheduler that is responsible for making such guarantee. For example, if the scheduler erroneously opened the Closure bucket while the Prepare work packet is still being executed, it is the scheduler's fault, not &mut ImmixSpace's.

[k-sareen]

Examples include Prepare, Release and EndOfGC. The problem is, we know this fact as humans

Actually we don't know this. In fact this is the cause of a race condition for MarkSweep in the Release work packet. See #824. We need to make sure that our assumptions are correct. MarkSweep isn't the only plan, Immix will also generate more work packets for the Release work bucket so it's not true that the Release work packet has exclusive access to plan.

[qinsoon]

1. Remove unnecessary references to Plan.

When a type holds a reference, they can access the plan. Based on the general rules of one mutable reference and many immutable references, when other types have an immutable reference, we can't access the plan mutably.

This is a full list of types that holds a long-lived reference to the plan:

• Mutator: The plan reference is only used for allocators that may rebind spaces (they can access the space from the plan).
• PlanProcessEdges/PlanScanObjects: Though they can always access the plan through the mmtk argument in do_work, that would require dynamic dispatch or using downcast (with an overhead). So those types hold a reference to the statically typed plan so they can dispatch calls more efficiently.
• GCTrigger: they need to query the plan about page usage and ask the plan if a GC is needed.
• Allocator: they hold a reference to the plan to access some states and GCRequester.

In many cases, when a type hold a reference to Plan, they do not actually need to access the plan. Like Mutator and Allocator. They just need to access some particular spaces, or some states in the plan. We can do refactoring like #949 , so those types no longer reference the plan, and instead they reference those spaces or states.

2. Make rules about interior mutability and exterior mutability

As we cannot safely get a mutable reference to Plan, in many cases, we work around the issue by using interior mutability, like Atomic types or locks. So we end up using both interior mutability (mutating a field using atomics or locks) and exterior mutability (pass in &mut self). That is saying, we may mutate Plan even if we only have an immutable reference, and we may also see a race if we get a mutable reference with unsafe (when there are other immutable references).

We should be clear when we should use interior mutability, and when we should use exterior mutability, rather than using interior mutability to work around mutability issues. I suggesting using exterior mutability where possible.

We could try some crates to help us sort out the mutability properly with good performance.

• parking_lot: provides low cost mutex and rwlock. If uncontended, the cost is claimed to be neglectable. Measure the performance of uncontended RwLock servo/servo#22790
• peace_lock: provides a mutex/rwlock interface. It can run run-time checks to make sure there is no race for debug builds, and omit the checks for a performant build. This could be very helpful for our case. Even if we do not plan to use the crate, we could write types with similar properties in our code base. It makes the source code clear, helps us debugging, and performs well.

[qinsoon]

I tried with both parking_lot::RwLock and peace_lock::RwLock on the spaces, i.e. Arc<RwLock<dyn Space>> or Arc<RwLock<ImmortalSpace>>. By doing this, it is clear that we mutate a space, and that we no longer need to mutate on a plan. In my experiements, both approaches have little impact in mutator time, but they both slow down STW time. parking_lot::RwLock has 10x slowdown in STW time, and peace_lock::RwLock without checking (which should be as efficient as unsafe cells) has ~7% overhead in STW time. I am looking further into peace_lock::RwLock and see where the overhead is from.

The refactoring identifies an obvious violation for Rust mutability rules (though it is still correct): a mutator thread is holding an immutable reference to the space when it is blocked in Space.acquire, and later in GC, we unsafely get a mutable reference to the space. This is correct, as the mutator thread cannot access the space during GC. But it is still holding a reference to the space, and it becomes a deadlock case if we apply RwLock on spaces: when we attempt to get a mutable reference to the space while someone is holding an immutable reference.