| 1 |
// The QSBR APIs (quiescent state-based reclamation) provide a mechanism for |
| 2 |
// the free-threaded build to safely reclaim memory when there may be |
| 3 |
// concurrent accesses. |
| 4 |
// |
| 5 |
// Many operations in the free-threaded build are protected by locks. However, |
| 6 |
// in some cases, we want to allow reads to happen concurrently with updates. |
| 7 |
// In this case, we need to delay freeing ("reclaiming") any memory that may be |
| 8 |
// concurrently accessed by a reader. The QSBR APIs provide a way to do this. |
| 9 |
#ifndef Py_INTERNAL_QSBR_H |
| 10 |
#define Py_INTERNAL_QSBR_H |
| 11 |
|
| 12 |
#include <stdbool.h> |
| 13 |
#include <stdint.h> |
| 14 |
|
| 15 |
#ifdef __cplusplus |
| 16 |
extern "C" { |
| 17 |
#endif |
| 18 |
|
| 19 |
#ifndef Py_BUILD_CORE |
| 20 |
# error "this header requires Py_BUILD_CORE define" |
| 21 |
#endif |
| 22 |
|
| 23 |
// The shared write sequence is always odd and incremented by two. Detached |
| 24 |
// threads are indicated by a read sequence of zero. This avoids collisions |
| 25 |
// between the offline state and any valid sequence number even if the |
| 26 |
// sequences numbers wrap around. |
| 27 |
#define QSBR_OFFLINE 0 |
| 28 |
#define QSBR_INITIAL 1 |
| 29 |
#define QSBR_INCR 2 |
| 30 |
|
| 31 |
// Wrap-around safe comparison. This is a holdover from the FreeBSD |
| 32 |
// implementation, which uses 32-bit sequence numbers. We currently use 64-bit |
| 33 |
// sequence numbers, so wrap-around is unlikely. |
| 34 |
#define QSBR_LT(a, b) ((int64_t)((a)-(b)) < 0) |
| 35 |
#define QSBR_LEQ(a, b) ((int64_t)((a)-(b)) <= 0) |
| 36 |
|
| 37 |
struct _qsbr_shared; |
| 38 |
struct _PyThreadStateImpl; // forward declare to avoid circular dependency |
| 39 |
|
| 40 |
// Per-thread state |
| 41 |
struct _qsbr_thread_state { |
| 42 |
// Last observed write sequence (or 0 if detached) |
| 43 |
uint64_t seq; |
| 44 |
|
| 45 |
// Shared (per-interpreter) QSBR state |
| 46 |
struct _qsbr_shared *shared; |
| 47 |
|
| 48 |
// Thread state (or NULL) |
| 49 |
PyThreadState *tstate; |
| 50 |
|
| 51 |
// Number of held items added by this thread since the last write sequence |
| 52 |
// advance |
| 53 |
int deferred_count; |
| 54 |
|
| 55 |
// Estimate for the amount of memory that is held by this thread since |
| 56 |
// the last write sequence advance |
| 57 |
size_t deferred_memory; |
| 58 |
|
| 59 |
// Amount of memory in mimalloc pages deferred from collection. When |
| 60 |
// deferred, they are prevented from being used for a different size class |
| 61 |
// and in a different thread. |
| 62 |
size_t deferred_page_memory; |
| 63 |
|
| 64 |
// True if the deferred memory frees should be processed. |
| 65 |
bool should_process; |
| 66 |
|
| 67 |
// Is this thread state allocated? |
| 68 |
bool allocated; |
| 69 |
struct _qsbr_thread_state *freelist_next; |
| 70 |
}; |
| 71 |
|
| 72 |
// Padding to avoid false sharing |
| 73 |
struct _qsbr_pad { |
| 74 |
struct _qsbr_thread_state qsbr; |
| 75 |
char __padding[64 - sizeof(struct _qsbr_thread_state)]; |
| 76 |
}; |
| 77 |
|
| 78 |
// Per-interpreter state |
| 79 |
struct _qsbr_shared { |
| 80 |
// Write sequence: always odd, incremented by two |
| 81 |
uint64_t wr_seq; |
| 82 |
|
| 83 |
// Minimum observed read sequence of all QSBR thread states |
| 84 |
uint64_t rd_seq; |
| 85 |
|
| 86 |
// Array of QSBR thread states (aligned to 64 bytes). |
| 87 |
struct _qsbr_pad *array; |
| 88 |
void *array_raw; // raw allocation pointer (for free) |
| 89 |
Py_ssize_t size; |
| 90 |
|
| 91 |
// Freelist of unused _qsbr_thread_states (protected by mutex) |
| 92 |
PyMutex mutex; |
| 93 |
struct _qsbr_thread_state *freelist; |
| 94 |
}; |
| 95 |
|
| 96 |
static inline uint64_t |
| 97 |
_Py_qsbr_shared_current(struct _qsbr_shared *shared) |
| 98 |
{ |
| 99 |
return _Py_atomic_load_uint64_acquire(&shared->wr_seq); |
| 100 |
} |
| 101 |
|
| 102 |
// Reports a quiescent state: the caller no longer holds any pointer to shared |
| 103 |
// data not protected by locks or reference counts. |
| 104 |
static inline void |
| 105 |
_Py_qsbr_quiescent_state(struct _qsbr_thread_state *qsbr) |
| 106 |
{ |
| 107 |
uint64_t seq = _Py_qsbr_shared_current(qsbr->shared); |
| 108 |
_Py_atomic_store_uint64_release(&qsbr->seq, seq); |
| 109 |
} |
| 110 |
|
| 111 |
// Have the read sequences advanced to the given goal? Like `_Py_qsbr_poll()`, |
| 112 |
// but does not perform a scan of threads. |
| 113 |
static inline bool |
| 114 |
_Py_qbsr_goal_reached(struct _qsbr_thread_state *qsbr, uint64_t goal) |
| 115 |
{ |
| 116 |
uint64_t rd_seq = _Py_atomic_load_uint64(&qsbr->shared->rd_seq); |
| 117 |
return QSBR_LEQ(goal, rd_seq); |
| 118 |
} |
| 119 |
|
| 120 |
// Advance the write sequence and return the new goal. This should be called |
| 121 |
// after data is removed. The returned goal is used with `_Py_qsbr_poll()` to |
| 122 |
// determine when it is safe to reclaim (free) the memory. |
| 123 |
extern uint64_t |
| 124 |
_Py_qsbr_advance(struct _qsbr_shared *shared); |
| 125 |
|
| 126 |
// Return the next value for the write sequence (current plus the increment). |
| 127 |
extern uint64_t |
| 128 |
_Py_qsbr_shared_next(struct _qsbr_shared *shared); |
| 129 |
|
| 130 |
// Return true if deferred memory frees held by QSBR should be processed to |
| 131 |
// determine if they can be safely freed. |
| 132 |
static inline bool |
| 133 |
_Py_qsbr_should_process(struct _qsbr_thread_state *qsbr) |
| 134 |
{ |
| 135 |
return qsbr->should_process; |
| 136 |
} |
| 137 |
|
| 138 |
// Have the read sequences advanced to the given goal? If this returns true, |
| 139 |
// it safe to reclaim any memory tagged with the goal (or earlier goal). |
| 140 |
extern bool |
| 141 |
_Py_qsbr_poll(struct _qsbr_thread_state *qsbr, uint64_t goal); |
| 142 |
|
| 143 |
// Called when thread attaches to interpreter |
| 144 |
extern void |
| 145 |
_Py_qsbr_attach(struct _qsbr_thread_state *qsbr); |
| 146 |
|
| 147 |
// Called when thread detaches from interpreter |
| 148 |
extern void |
| 149 |
_Py_qsbr_detach(struct _qsbr_thread_state *qsbr); |
| 150 |
|
| 151 |
// Reserves (allocates) a QSBR state and returns its index. |
| 152 |
extern Py_ssize_t |
| 153 |
_Py_qsbr_reserve(PyInterpreterState *interp); |
| 154 |
|
| 155 |
// Associates a PyThreadState with the QSBR state at the given index |
| 156 |
extern void |
| 157 |
_Py_qsbr_register(struct _PyThreadStateImpl *tstate, |
| 158 |
PyInterpreterState *interp, Py_ssize_t index); |
| 159 |
|
| 160 |
// Disassociates a PyThreadState from the QSBR state and frees the QSBR state. |
| 161 |
extern void |
| 162 |
_Py_qsbr_unregister(PyThreadState *tstate); |
| 163 |
|
| 164 |
extern void |
| 165 |
_Py_qsbr_fini(PyInterpreterState *interp); |
| 166 |
|
| 167 |
extern void |
| 168 |
_Py_qsbr_after_fork(struct _PyThreadStateImpl *tstate); |
| 169 |
|
| 170 |
#ifdef __cplusplus |
| 171 |
} |
| 172 |
#endif |
| 173 |
#endif /* !Py_INTERNAL_QSBR_H */ |