Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/python3.14/internal/pycore_qsbr.h
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 */
