gh-111964: Implement stop-the-world pauses (gh-112471)

The `--disable-gil` builds occasionally need to pause all but one thread.  Some
examples include:

* Cyclic garbage collection, where this is often called a "stop the world event"
* Before calling `fork()`, to ensure a consistent state for internal data structures
* During interpreter shutdown, to ensure that daemon threads aren't accessing Python objects

This adds the following functions to implement global and per-interpreter pauses:

* `_PyEval_StopTheWorldAll()` and `_PyEval_StartTheWorldAll()` (for the global runtime)
* `_PyEval_StopTheWorld()` and `_PyEval_StartTheWorld()` (per-interpreter)

(The function names may change.)

These functions are no-ops outside of the `--disable-gil` build.

6 files changed, 68 insertions, 14 deletions

diff --git a/Include/internal/pycore_ceval.h b/Include/internal/pycore_ceval.h
index a357bfa..a66af13 100644
--- a/Include/internal/pycore_ceval.h
+++ b/Include/internal/pycore_ceval.h
@@ -205,6 +205,7 @@ void _PyEval_FrameClearAndPop(PyThreadState *tstate, _PyInterpreterFrame *frame)
 #define _PY_CALLS_TO_DO_BIT 2
 #define _PY_ASYNC_EXCEPTION_BIT 3
 #define _PY_GC_SCHEDULED_BIT 4
+#define _PY_EVAL_PLEASE_STOP_BIT 5
 
 /* Reserve a few bits for future use */
 #define _PY_EVAL_EVENTS_BITS 8
diff --git a/Include/internal/pycore_interp.h b/Include/internal/pycore_interp.h
index 922c845..f953b84 100644
--- a/Include/internal/pycore_interp.h
+++ b/Include/internal/pycore_interp.h
@@ -41,6 +41,22 @@ struct _Py_long_state {
     int max_str_digits;
 };
 
+// Support for stop-the-world events. This exists in both the PyRuntime struct
+// for global pauses and in each PyInterpreterState for per-interpreter pauses.
+struct _stoptheworld_state {
+    PyMutex mutex;       // Serializes stop-the-world attempts.
+
+    // NOTE: The below fields are protected by HEAD_LOCK(runtime), not by the
+    // above mutex.
+    bool requested;      // Set when a pause is requested.
+    bool world_stopped;  // Set when the world is stopped.
+    bool is_global;      // Set when contained in PyRuntime struct.
+
+    PyEvent stop_event;  // Set when thread_countdown reaches zero.
+    Py_ssize_t thread_countdown;  // Number of threads that must pause.
+
+    PyThreadState *requester; // Thread that requested the pause (may be NULL).
+};
 
 /* cross-interpreter data registry */
 
@@ -166,6 +182,7 @@ struct _is {
 
     struct _warnings_runtime_state warnings;
     struct atexit_state atexit;
+    struct _stoptheworld_state stoptheworld;
 
 #if defined(Py_GIL_DISABLED)
     struct _mimalloc_interp_state mimalloc;
diff --git a/Include/internal/pycore_llist.h b/Include/internal/pycore_llist.h
index 5fd261d..f629902 100644
--- a/Include/internal/pycore_llist.h
+++ b/Include/internal/pycore_llist.h
@@ -37,8 +37,7 @@ struct llist_node {
 };
 
 // Get the struct containing a node.
-#define llist_data(node, type, member) \
-    (type*)((char*)node - offsetof(type, member))
+#define llist_data(node, type, member) (_Py_CONTAINER_OF(node, type, member))
 
 // Iterate over a list.
 #define llist_for_each(node, head) \
diff --git a/Include/internal/pycore_pystate.h b/Include/internal/pycore_pystate.h
index 348c5c6..289ef28 100644
--- a/Include/internal/pycore_pystate.h
+++ b/Include/internal/pycore_pystate.h
@@ -21,23 +21,27 @@ extern "C" {
 // interpreter at the same time. Only the "bound" thread may perform the
 // transitions between "attached" and "detached" on its own PyThreadState.
 //
-// The "gc" state is used to implement stop-the-world pauses, such as for
-// cyclic garbage collection. It is only used in `--disable-gil` builds. It is
-// similar to the "detached" state, but only the thread performing a
-// stop-the-world pause may transition threads between the "detached" and "gc"
-// states. A thread trying to "attach" from the "gc" state will block until
-// it is transitioned back to "detached" when the stop-the-world pause is
-// complete.
+// The "suspended" state is used to implement stop-the-world pauses, such as
+// for cyclic garbage collection. It is only used in `--disable-gil` builds.
+// The "suspended" state is similar to the "detached" state in that in both
+// states the thread is not allowed to call most Python APIs. However, unlike
+// the "detached" state, a thread may not transition itself out from the
+// "suspended" state. Only the thread performing a stop-the-world pause may
+// transition a thread from the "suspended" state back to the "detached" state.
 //
 // State transition diagram:
 //
 //            (bound thread)        (stop-the-world thread)
-// [attached]       <->       [detached]       <->       [gc]
+// [attached]       <->       [detached]       <->       [suspended]
+//   |                                                        ^
+//   +---------------------------->---------------------------+
+//                          (bound thread)
 //
-// See `_PyThreadState_Attach()` and `_PyThreadState_Detach()`.
+// The (bound thread) and (stop-the-world thread) labels indicate which thread
+// is allowed to perform the transition.
 #define _Py_THREAD_DETACHED     0
 #define _Py_THREAD_ATTACHED     1
-#define _Py_THREAD_GC           2
+#define _Py_THREAD_SUSPENDED    2
 
 
 /* Check if the current thread is the main thread.
@@ -140,13 +144,36 @@ _PyThreadState_GET(void)
 //
 // High-level code should generally call PyEval_RestoreThread() instead, which
 // calls this function.
-void _PyThreadState_Attach(PyThreadState *tstate);
+extern void _PyThreadState_Attach(PyThreadState *tstate);
 
 // Detaches the current thread from the interpreter.
 //
 // High-level code should generally call PyEval_SaveThread() instead, which
 // calls this function.
-void _PyThreadState_Detach(PyThreadState *tstate);
+extern void _PyThreadState_Detach(PyThreadState *tstate);
+
+// Detaches the current thread to the "suspended" state if a stop-the-world
+// pause is in progress.
+//
+// If there is no stop-the-world pause in progress, then the thread switches
+// to the "detached" state.
+extern void _PyThreadState_Suspend(PyThreadState *tstate);
+
+// Perform a stop-the-world pause for all threads in the all interpreters.
+//
+// Threads in the "attached" state are paused and transitioned to the "GC"
+// state. Threads in the "detached" state switch to the "GC" state, preventing
+// them from reattaching until the stop-the-world pause is complete.
+//
+// NOTE: This is a no-op outside of Py_GIL_DISABLED builds.
+extern void _PyEval_StopTheWorldAll(_PyRuntimeState *runtime);
+extern void _PyEval_StartTheWorldAll(_PyRuntimeState *runtime);
+
+// Perform a stop-the-world pause for threads in the specified interpreter.
+//
+// NOTE: This is a no-op outside of Py_GIL_DISABLED builds.
+extern void _PyEval_StopTheWorld(PyInterpreterState *interp);
+extern void _PyEval_StartTheWorld(PyInterpreterState *interp);
 
 
 static inline void
diff --git a/Include/internal/pycore_runtime.h b/Include/internal/pycore_runtime.h
index e334829..02ab22b 100644
--- a/Include/internal/pycore_runtime.h
+++ b/Include/internal/pycore_runtime.h
@@ -227,6 +227,13 @@ typedef struct pyruntimestate {
     struct _faulthandler_runtime_state faulthandler;
     struct _tracemalloc_runtime_state tracemalloc;
 
+    // The rwmutex is used to prevent overlapping global and per-interpreter
+    // stop-the-world events. Global stop-the-world events lock the mutex
+    // exclusively (as a "writer"), while per-interpreter stop-the-world events
+    // lock it non-exclusively (as "readers").
+    _PyRWMutex stoptheworld_mutex;
+    struct _stoptheworld_state stoptheworld;
+
     PyPreConfig preconfig;
 
     // Audit values must be preserved when Py_Initialize()/Py_Finalize()
diff --git a/Include/internal/pycore_runtime_init.h b/Include/internal/pycore_runtime_init.h
index 5f47d60..b4806ab 100644
--- a/Include/internal/pycore_runtime_init.h
+++ b/Include/internal/pycore_runtime_init.h
@@ -116,6 +116,9 @@ extern PyTypeObject _PyExc_MemoryError;
         }, \
         .faulthandler = _faulthandler_runtime_state_INIT, \
         .tracemalloc = _tracemalloc_runtime_state_INIT, \
+        .stoptheworld = { \
+            .is_global = 1, \
+        }, \
         .float_state = { \
             .float_format = _py_float_format_unknown, \
             .double_format = _py_float_format_unknown, \