Mechanisms for Coordination Between Garbage Collector and Mutator
-----------------------------------------------------------------

Most garbage collection work can proceed concurrently with the client or
mutator Java threads. But in certain places, for example while tracing from
thread stacks, the garbage collector needs to ensure that Java data processed
by the collector is consistent and complete. At these points, the mutators
should not hold references to the heap that are invisible to the garbage
collector. And they should not be modifying the data that is visible to the
collector.

Logically, the collector and mutator share a reader-writer lock on the Java
heap and associated data structures. Mutators hold the lock in reader or shared mode
while running Java code or touching heap-related data structures. The collector
holds the lock in writer or exclusive mode while it needs the heap data
structures to be stable. However, this reader-writer lock has a very customized
implementation that also provides additional facilities, such as the ability
to exclude only a single thread, so that we can specifically examine its heap
references.

In order to ensure consistency of the Java data, the compiler inserts "suspend
points", sometimes also called "safe points" into the code. These allow a thread
to respond to external requests.

Whenever a thread is runnable, i.e. whenever a thread logically holds the
mutator lock in shared mode, it is expected to regularly execute such a suspend
point, and check for pending requests. They are currently implemented by
setting a flag in the thread structure[^1], which is then explicitly tested by the
compiler-generated code.

A thread responds to suspend requests only when it is "runnable", i.e. logically
running Java code. When it runs native code, or is blocked in a kernel call, it
logically releases the mutator lock. When the garbage collector needs mutator
cooperation, and the thread is not runnable, it is assured that the mutator is
not touching Java data, and hence the collector can safely perform the required
action itself, on the mutator thread's behalf.

Normally, when a thread makes a JNI call, it is not considered runnable while
executing native code. This makes the transitions to and from running native JNI
code somewhat expensive (see below). But these transitions are necessary to
ensure that such code, which does not execute "suspend points", and can thus not
cooperate with the GC, doesn't delay GC completion. `@FastNative` and
`@CriticalNative` calls avoid these transitions, instead allowing the thread to
remain "runnable", at the expense of potentially delaying GC operations for the
duration of the call.

Although we say that a thread is "suspended" when it is not running Java code,
it may in fact still be running native code and touching data structures that
are not considered "Java data". This distinction can be a fine line. For
example, a Java thread blocked on a Java monitor will normally be "suspended"
and blocked on a mutex contained in the monitor data structure. But it may wake
up for reasons beyond ARTs control, which will normally result in touching the
mutex. The monitor code must be quite careful to ensure that this does not cause
problems, especially if the ART runtime was shut down in the interim and the
monitor data structure has been reclaimed.

Calls to change thread state
----------------------------

When a thread changes between running Java and native code, it has to
correspondingly change its state between "runnable" and one of several
other states, all of which are considered to be "suspended" for our purposes.
When a Java thread starts to execute native code, and may thus not respond
promptly to suspend requests, it will normally create an object of type
`ScopedThreadSuspension`. `ScopedThreadSuspension`'s constructor changes state to
the "suspended" state given as an argument, logically releasing the mutator lock
and promising to no longer touch Java data structures. It also handles any
pending suspension requests that slid in just before it changed state.

Conversely, `ScopedThreadSuspension`'s destructor waits until the GC has finished
any actions it is currently performing on the thread's behalf and effectively
released the mutator exclusive lock, and then returns to runnable state,
re-acquiring the mutator lock.

Occasionally a thread running native code needs to temporarily again access Java
data structures, performing the above transitions in the opposite order.
`ScopedObjectAccess` is a similar RAII object whose constructor and destructor
perform those transitions in the reverse order from `ScopedThreadSuspension`.

Mutator lock implementation
---------------------------

The mutator lock is not implemented as a conventional mutex. But it plays by the
rules of our normal static thread-safety analysis. Thus a function that is
expected to be called in runnable state, with the ability to access Java data,
should be annotated with `REQUIRES_SHARED(Locks::mutator_lock_)`.

There is an explicit `mutator_lock_` object, of type `MutatorMutex`. `MutatorMutex` is
seemingly a minor refinement of `ReaderWriterMutex`, but it is used entirely
differently. It is acquired explicitly by clients that need to hold it
exclusively, and in a small number of cases, it is acquired in shared mode, e.g.
via `SharedTryLock()`, or by the GC itself. However, more commonly
`MutatorMutex::TransitionFromSuspendedToRunnable()`, is used to logically acquire
the mutator mutex, e.g. as part of `ScopedObjectAccess` construction.

`TransitionFromSuspendedToRunnable()` does not physically acquire the
`ReaderWriterMutex` in shared mode. Thus any thread acquiring the lock in exclusive mode
must, in addition, explicitly arrange for mutator threads to be suspended via the
thread suspension mechanism, and then make them runnable again on release.

Logically the mutator lock is held in shared/reader mode if ***either*** the
underlying reader-writer lock is held in shared mode, ***or*** if a mutator is in
runnable state. These two ways of holding the mutator mutex are ***not***
equivalent: In particular, we rely on the garbage collector never actually
entering a "runnable" state while active (see below). However, it often runs with
the explicit mutator mutex in shared mode, thus blocking others from acquiring it
in exclusive mode.

Suspension and checkpoint API
-----------------------------

Suspend point checks enable three kinds of communication with mutator threads:

**Checkpoints**
: Checkpoint requests are used to get a thread to perform an action
on our behalf. `RequestCheckpoint()` asks a specific thread to execute the closure
supplied as an argument at its leisure. `RequestSynchronousCheckpoint()` in
addition waits for the thread to complete running the closure, and handles
suspended threads by running the closure on their behalf. In addition to these
functions provided by `Thread`, `ThreadList` provides the `RunCheckpoint()` function
that runs a checkpoint function on behalf of each thread, either by using
`RequestCheckpoint()` to run it inside a running thread, or by ensuring that a
suspended thread stays suspended, and then running the function on its behalf.
`RunCheckpoint()` does not wait for completion of the function calls triggered by
the resulting `RequestCheckpoint()` invocations.

**Empty checkpoints**
: ThreadList provides `RunEmptyCheckpoint()`, which waits until
all threads have either passed a suspend point, or have been suspended. This
ensures that no thread is still executing Java code inside the same
suspend-point-delimited code interval it was executing before the call. For
example, a read-barrier started before a `RunEmptyCheckpoint()` call will have
finished before the call returns.

**Thread suspension**
: ThreadList provides a number of `SuspendThread...()` calls and
a `SuspendAll()` call to suspend one or all threads until they are resumed by
`Resume()` or `ResumeAll()`. The `Suspend...` calls guarantee that the target
thread(s) are suspended (again, only in the sense of not running Java code)
when the call returns.

Deadlock freedom
----------------

It is easy to deadlock while attempting to run checkpoints, or suspending
threads. In particular, we need to avoid situations in which we cannot suspend
a thread because it is blocked, directly, or indirectly, on the GC completing
its task. Deadlocks are avoided as follows:

**Mutator lock ordering**
The mutator lock participates in the normal ART lock ordering hierarchy, as though it
were a regular lock. See `base/locks.h` for the hierarchy. In particular, only
locks at or below level `kPostMutatorTopLockLevel` may be acquired after
acquiring the mutator lock, e.g. inside the scope of a `ScopedObjectAccess`.
Similarly only locks at level strictly above `kMutatatorLock` may be held while
acquiring the mutator lock, e.g. either by starting a `ScopedObjectAccess`, or
ending a `ScopedThreadSuspension`.

This ensures that code that uses purely mutexes and threads state changes cannot
deadlock: Since we always wait on a lower-level lock, the holder of the
lowest-level lock can always progress. An attempt to initiate a checkpoint or to
suspend another thread must also be treated as an acquisition of the mutator
lock: A thread that is waiting for a lock before it can respond to the request
is itself holding the mutator lock, and can only be blocked on lower-level
locks. And acquisition of those can never depend on acquiring the mutator
lock.

**Checkpoints**
Running a checkpoint in a thread requires suspending that thread for the
duration of the checkpoint, or running the checkpoint on the threads behalf
while that thread is blocked from executing Java code. In the former case, the
checkpoint code is run from `CheckSuspend`, which requires the mutator lock,
so checkpoint code may only acquire mutexes at or below level
`kPostMutatorTopLockLevel`. But that is not sufficient.

No matter whether the checkpoint is run in the target thread, or on its behalf,
the target thread is effectively suspended and prevented from running Java code.
However the target may hold arbitrary Java monitors, which it can no longer
release. This may also prevent higher level mutexes from getting released.  Thus
checkpoint code should only acquire mutexes at level `kPostMonitorLock` or
below.


**Waiting**
This becomes much more problematic when we wait for something other than a lock.
Waiting for something that may depend on the GC, while holding the mutator lock,
can potentially lead to deadlock, since it will prevent the waiting thread from
participating in GC checkpoints. Waiting while holding a lower-level lock like
`thread_list_lock_` is similarly unsafe in general, since a runnable thread may
not respond to checkpoints until it acquires `thread_list_lock_`. In general,
waiting for a condition variable while holding an unrelated lock is problematic,
and these are specific instances of that general problem.

We do currently provide `WaitHoldingLocks`, and it is sometimes used with
low-level locks held. But such code must somehow ensure that such waits
eventually terminate without deadlock.

One common use of WaitHoldingLocks is to wait for weak reference processing.
Special rules apply to avoid deadlocks in this case: Such waits must start after
weak reference processing is disabled; the GC may not issue further nonempty
checkpoints or suspend requests until weak reference processing has been
reenabled, and threads have been notified. Thus the waiting thread's inability
to respond to nonempty checkpoints and suspend requests cannot directly block
the GC. Non-GC checkpoint or suspend requests that target a thread waiting on
reference processing will block until reference processing completes.

Consider a case in which thread W1 waits on reference processing, while holding
a low-level mutex M. Thread W2 holds the mutator lock and waits on M. We avoid a
situation in which the GC needs to suspend or checkpoint W2 by briefly stopping
the world to disable weak reference access. During the stop-the-world phase, W1
cannot yet be waiting for weak-reference access.  Thus there is no danger of
deadlock while entering this phase. After this phase, there is no need for W2 to
suspend or execute a nonempty checkpoint. If we replaced the stop-the-world
phase by a checkpoint, W2 could receive the checkpoint request too late, and be
unable to respond.

Empty checkpoints can continue to occur during reference processing.  Reference
processing wait loops explicitly handle empty checkpoints, and an empty
checkpoint request notifies the condition variable used to wait for reference
processing, after acquiring `reference_processor_lock_`.  This means that empty
checkpoints do not preclude client threads from being in the middle of an
operation that involves a weak reference access, while nonempty checkpoints do.

**Suspending the GC**
Under unusual conditions, the GC can run on any thread. This means that when
thread *A* suspends thread *B* for some other reason, Thread *B* might be
running the garbage collector and conceivably thus cause it to block.  This
would be very deadlock prone. If Thread *A* allocates while Thread *B* is
suspended in the GC, and the allocation requires the GC's help to complete, we
deadlock.

Thus we ensure that the GC, together with anything else that can block GCs,
cannot be blocked for thread suspension requests. This is accomplished by
ensuring that it always appears to be in a suspended thread state. Since we
only check for suspend requests when entering the runnable state, suspend
requests go unnoticed until the GC completes. It may physically acquire and
release the actual `mutator_lock_` in either shared or exclusive mode.

Thread Suspension Mechanics
---------------------------

Thread suspension is initiated by a registered thread, except that, for testing
purposes, `SuspendAll` may be invoked with `self == nullptr`.  We never suspend
the initiating thread, explicitly exclusing it from `SuspendAll()`, and failing
`SuspendThreadBy...()` requests to that effect.

The suspend calls invoke `IncrementSuspendCount()` to increment the thread
suspend count for each thread. That adds a "suspend barrier" (atomic counter) to
the per-thread list of such counters to decrement. It normally sets the
`kSuspendRequest` ("should enter safepoint handler") and `kActiveSuspendBarrier`
("need to notify us when suspended") flags.

After setting these two flags, we check whether the thread is suspended and
`kSuspendRequest` is still set. Since the thread is already suspended, it cannot
be expected to respond to "pass the suspend barrier" (decrement the atomic
counter) in a timely fashion.  Hence we do so on its behalf. This decrements
the "barrier" and removes it from the thread's list of barriers to decrement,
and clears `kActiveSuspendBarrier`. `kSuspendRequest` remains to ensure the
thread doesn't prematurely return to runnable state.

If `SuspendAllInternal()` does not immediately see a suspended state, then it is up
to the target thread to decrement the suspend barrier.
`TransitionFromRunnableToSuspended()` calls
`TransitionToSuspendedAndRunCheckpoints()`, which changes the thread state
and returns. `TransitionFromRunnableToSuspended()` then calls
`CheckActiveSuspendBarriers()` to check for the `kActiveSuspendBarrier` flag
and decrement the suspend barrier if set.

The `suspend_count_lock_` is not consistently held in the target thread
during this process.  Thus correctness in resolving the race between a
suspension-requesting thread and a target thread voluntarily suspending relies
on first requesting suspension, and then checking whether the target is
already suspended, The detailed correctness argument is given in a comment
inside `SuspendAllInternal()`. This also ensures that the barrier cannot be
decremented after the stack frame holding the barrier goes away.

This relies on the fact that the two stores in the two threads to the state and
kActiveSuspendBarrier flag are ordered with respect to the later loads. That's
guaranteed, since they are all stored in a single `atomic<>`. Thus even relaxed
accesses are OK.

The actual suspend barrier representation still varies between `SuspendAll()`
and `SuspendThreadBy...()`.  The former relies on the fact that only one such
barrier can be in use at a time, while the latter maintains a linked list of
active suspend barriers for each target thread, relying on the fact that each
one can appear on the list of only one thread, and we can thus use list nodes
allocated in the stack frames of requesting threads.

**Avoiding suspension cycles**

Any thread can issue a `SuspendThreadByPeer()`, `SuspendThreadByThreadId()` or
`SuspendAll()` request. But if Thread A increments Thread B's suspend count
while Thread B increments Thread A's suspend count, and they then both suspend
during a subsequent thread transition, we're deadlocked.

For single-thread suspension requests, we refuse to initiate
a suspend request from a registered thread that is also being asked to suspend
(i.e. the suspend count is nonzero).  Instead the requestor waits for that
condition to change.  This means that we cannot create a cycle in which each
thread has asked to suspend the next one, and thus no thread can progress.  The
required atomicity of the requestor suspend count check with setting the suspend
count of the target(s) target is ensured by holding `suspend_count_lock_`.

For `SuspendAll()`, we enforce a requirement that at most one `SuspendAll()`
request is running at one time. We also set the `kSuspensionImmune` thread flag
to prevent a single thread suspension of a thread currently between
`SuspendAll()` and `ResumeAll()` calls. Thus once a `SuspendAll()` call starts,
it will complete before it can be affected by suspension requests from other
threads.


Thread state transitions, flags, and memory ordering
----------------------------------------------------

Logically when a state transitions to state `kRunnable`, it acquires the mutator
lock (in shared mode). When it changes its state back to suspended, it releases
that lock. These must enforce proper happens-before ordering with respect to a
thread acquiring the mutator lock in exclusive mode. Thus changing the thread
state to suspended normally requires a release operation, to ensure visibility
to a thread wishing to "suspend". Conversely, when we change the state back to
`kRunnable` in `TransitionFromSuspendedToRunnable` we do so with an acquire
compare-exchange operation to check that no suspension request remains.

Any suspending thread should clear `kSuspendRequest` with a release
operation. This, together with the acquire compare-exchange when returning to
runnable state, ensure that suspend-count decrements happen-before a thread
becomes runnable again.

Flags are often set and tested with relaxed ordering, even when they may
communicate a request to another thread. The reason this is safe varies.
Generally the request is conformed by some other better synchronized
interaction, which establishes the necessary ordering. In particular:

`kCheckPointRequest`
: See below. The call happens-before checkpoint execution since
`checkpoint_function` accesses are guarded by a lock, as are updates to the
flag. Checkpoint completion ordering is ensured by waiting for both
`ThreadList::RunCheckpoint()` to complete, and for a barrier indicating
completion in "runnable" threads.

`kEmptyCheckpointRequest`
: Currently (12/2024) in flux. See below and b/382722942 . We currently use
acquire/release ordering to access this flag in some places to partially
mitigate memory ordering issues here.

`kActiveSuspendBarrier`
: Changes are protected by `thread_suspend_count_lock_`, and
`PassActiveSuspendBarriers` rechecks it while holding that lock.

`kPendingFlipFunction`
: Set while holding `thread_list_lock_`, but this lock is not consistently held
while checking the flag, notably in `EnsureFlipFunctionStarted()`. We need
acquire/release ordering to make sure that the requestor happens-before flip
function execution, and the flip function is properly visible, among other
things. We still commonly read the flag using a relaxed operation, but we
confirm it with an acquire compare-exchange operation in
`EnsureFlipFunctionStarted()` before actiong on it.

`kRunningFlipFunction`
: Cleared with release ordering, and read with acquire ordering by
`WaitForFlipFunction` and its callers, thus ensuring that flip function
execution happens-before completion of WaitForFlipFunction.

`kSuspensionImmune`
: Guarded by `thread_suspend_count_lock_`.

### Checkpoint-specific considerations

Checkpoints expose additional tricky issues, since they are also used to ensure
that certain global state changes have propagated to all running Java threads.

`ThreadList::RunCheckpoint()` guarantees that "if at point _X_ `RunCheckpoint()`
has returned, and all checkpoints have been properly observed to have completed,
then every thread has executed a code sequence _S_ during which it remained in
a suspended state, such that the call to `RunCheckpoint` happens-before the end
of _S_, and the beginning of _S_ happened before _X_."

For each thread _T_, we attempt to atomically install the `kCheckpointRequest`
flag while ensuring that _T_ is runnable.  If this succeeds, the fact that
`tlsPtr_.checkpoint_function` is protected by `thread_suspend_count_lock_`, and
`checkpoint_function` is written by the requestor, and read by _T_ at a suspend
point, ensures that the call happens-before _S_. Normally a barrier ensures that
_S_ happens-before _X_ .

If we are unable to do so for a thread _T_ because we find it suspended, we run
`checkpoint_function` ourselves. Before running it we set `kSuspendRequest`
(with a release store) while _T_ is in _S_, preventing _T_ from terminating _S_
by becoming runnable, after an acquire load of the flags. This ensures that the
`RunCheckpoint()` call happens-before the end of _S_. Since we learned of _T_'s
suspended state via an acquire load of its state, which it stored with a release
store, we know that the beginning of _S_ happens-before we return from
`RunCheckpoint()`, and hence before _X_ .

The case of empty checkpoints is worth highlighting. We have traditionally
optimized that by avoiding ever suspending the affected threads. This appears
correct if all operations are sequentially consistent. But once memory model
issues are considered, it appears more expensive to do fully correctly than it
is to forego the optimization, as we explain below:

We need to ensure that if Thread _A_ performs some update _U_ and then calls
`RunEmptyCheckpoint()` then, when `RunEmptyCheckpoint()` returns, every Thread
_B_ will have passed a suspend point at which _U_ became guaranteed visible to
that thread. This could be ensured in different ways, depending on the observed
state of Thread _B_:

Runnable
: Use acquire/release ordering when setting and detecting the
`kEmptyCheckpointRequest` flag, and then use a barrier to observe when thread _B_
has done so. In this case, Thread _B_ actually executes code at a suspend point.
The acquire release ordering on `kEmptyCheckpointRequest` ensures that _U_
happens-before the suspend point, and the barrier ensures that the suspend point
happens-before the `RunEmptyCheckpoint()` return.

Suspended
: In this case, we have no mechanism for the thread to execute synchronization
operations, and things become trickier. Thread _B_ is suspended, but it may
restart at any time. Thread _A_ wants to conclude that Thread _B_ is already
suspended at a suspend point, and thus it is safe to ignore Thread _B_.
Effectively, it wants to perform the update _U_, read _B_'s state, and continue,
while _B_ may change its state back to runnable, and then read the result of
_U_. Both threads effectively perform a store (either _U_ or to the state of
_B_) and then read the other value. With only acquire/release ordering, this can
result in _A_ seeing the old suspended state, and _B_ failing to see the update
_U_, which is an incorrect outcome.
: The canonical fix for this kind of `store; load` reordering problem is to make
all operations sequentially consistent. There does not appear to be an easy way
to limit this overhead to just empty checkpoint execution. Thus it appears to be
better to forego this "optimization".

[^1]: In the most recent versions of ART on arm64, compiler-generated code loads
    through the address at `tlsPtr_.suspend_trigger`. A thread suspension is
    requested by setting this to null, triggering a `SIGSEGV`, causing that
    thread to check for GC cooperation requests. The older mechanism instead
    sets an appropriate `ThreadFlag` entry to request suspension or a
    checkpoint. Note that the actual checkpoint function value is set, along
    with the flag, while holding `suspend_count_lock_`. If the target thread
    notices that a checkpoint is requested, it then acquires the
    `suspend_count_lock_` to read the checkpoint function.