Debian Codegraph @

Include/internal/pycore_qsbr.h

raw
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 */