1 | /* |
2 | * Copyright (c) 2022 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | #ifndef _KERN_LOCKS_INTERNAL_H_ |
30 | #define _KERN_LOCKS_INTERNAL_H_ |
31 | |
32 | #define LOCK_PRIVATE 1 |
33 | #include <sys/cdefs.h> |
34 | #include <stdint.h> |
35 | #include <kern/startup.h> |
36 | #include <kern/percpu.h> |
37 | #include <kern/lock_types.h> |
38 | #include <kern/lock_group.h> |
39 | #include <machine/cpu_number.h> |
40 | #include <machine/locks.h> |
41 | #include <machine/machine_cpu.h> |
42 | #include <os/atomic_private.h> |
43 | |
44 | /* |
45 | * This file shares implementation details for XNU lock implementations. |
46 | * It is not meant to be shared with any other part of the code. |
47 | */ |
48 | |
49 | __BEGIN_DECLS __ASSUME_PTR_ABI_SINGLE_BEGIN |
50 | |
51 | #pragma GCC visibility push(hidden) |
52 | |
53 | /*! |
54 | * @macro hw_spin_wait_until_n() |
55 | * |
56 | * @brief |
57 | * Abstracts the platform specific way to spin around the value |
58 | * of a memory location until a certain condition is met. |
59 | * |
60 | * @param count how many times to spin without evaluating progress |
61 | * @param ptr the pointer to the memory location being observed |
62 | * @param load_var the variable to store the result of the load into |
63 | * @param cond_expr the stopping condition (can use @c load_var) |
64 | * |
65 | * @returns |
66 | * - 0 if the loop stopped when the counter expired |
67 | * - cond_expr's return value otherwise |
68 | */ |
69 | #define hw_spin_wait_until_n(count, ptr, load_var, cond_expr) ({ \ |
70 | typeof((cond_expr)) __cond_result; \ |
71 | \ |
72 | for (uint32_t __cond_init = (count), __cond_count = __cond_init; \ |
73 | __probable(__cond_count-- > 0);) { \ |
74 | __hw_spin_wait_load(ptr, load_var, __cond_result, cond_expr); \ |
75 | if (__probable(__cond_result)) { \ |
76 | break; \ |
77 | } \ |
78 | } \ |
79 | \ |
80 | __cond_result; \ |
81 | }) |
82 | |
83 | /*! |
84 | * @macro hw_spin_wait_until() |
85 | * |
86 | * @brief |
87 | * Conveniency wrapper for hw_spin_wait_until_n() with the typical |
88 | * LOCK_SNOOP_SPINS counter for progress evaluation. |
89 | */ |
90 | #define hw_spin_wait_until(ptr, load_var, cond_expr) \ |
91 | hw_spin_wait_until_n(LOCK_SNOOP_SPINS, ptr, load_var, cond_expr) |
92 | |
93 | |
94 | #if LOCK_PRETEST |
95 | #define lck_pretestv(p, e, g) ({ \ |
96 | __auto_type __e = (e); \ |
97 | __auto_type __v = os_atomic_load(p, relaxed); \ |
98 | if (__v != __e) { \ |
99 | *(g) = __v; \ |
100 | } \ |
101 | __v == __e; \ |
102 | }) |
103 | #define lck_pretest(p, e) \ |
104 | (os_atomic_load(p, relaxed) == (e)) |
105 | #else |
106 | #define lck_pretestv(p, e, g) 1 |
107 | #define lck_pretest(p, e) 1 |
108 | #endif |
109 | |
110 | /*! |
111 | * @function lock_cmpxchg |
112 | * |
113 | * @brief |
114 | * Similar to os_atomic_cmpxchg() but with a pretest when LOCK_PRETEST is set. |
115 | */ |
116 | #define lock_cmpxchg(p, e, v, m) ({ \ |
117 | __auto_type _p = (p); \ |
118 | __auto_type _e = (e); \ |
119 | lck_pretest(_p, _e) && os_atomic_cmpxchg(_p, _e, v, m); \ |
120 | }) |
121 | |
122 | /*! |
123 | * @function lock_cmpxchgv |
124 | * |
125 | * @brief |
126 | * Similar to os_atomic_cmpxchgv() but with a pretest when LOCK_PRETEST is set. |
127 | */ |
128 | #define lock_cmpxchgv(p, e, v, g, m) ({ \ |
129 | __auto_type _p = (p); \ |
130 | __auto_type _e = (e); \ |
131 | lck_pretestv(_p, _e, g) && os_atomic_cmpxchgv(_p, _e, v, g, m); \ |
132 | }) |
133 | |
134 | #if OS_ATOMIC_HAS_LLSC |
135 | #define lock_load_exclusive(p, m) os_atomic_load_exclusive(p, m) |
136 | #define lock_wait_for_event() wait_for_event() |
137 | #define lock_store_exclusive(p, ov, nv, m) os_atomic_store_exclusive(p, nv, m) |
138 | #else |
139 | #define lock_load_exclusive(p, m) os_atomic_load(p, relaxed) |
140 | #define lock_wait_for_event() cpu_pause() |
141 | #define lock_store_exclusive(p, ov, nv, m) os_atomic_cmpxchg(p, ov, nv, m) |
142 | #endif |
143 | |
144 | |
145 | /*! |
146 | * @enum lck_type_t |
147 | * |
148 | * @brief |
149 | * A one-byte type tag used in byte 3 of locks to be able to identify them. |
150 | */ |
151 | __enum_decl(lck_type_t, uint8_t, { |
152 | LCK_TYPE_NONE = 0x00, |
153 | LCK_TYPE_MUTEX = 0x22, |
154 | LCK_TYPE_RW = 0x33, |
155 | LCK_TYPE_TICKET = 0x44, |
156 | LCK_TYPE_GATE = 0x55, |
157 | }); |
158 | |
159 | |
160 | /*! |
161 | * @typedef lck_mtx_mcs_t |
162 | * |
163 | * @brief |
164 | * The type of per-cpu MCS-like nodes used for the mutex acquisition slowpath. |
165 | * |
166 | * @discussion |
167 | * There is one such structure per CPU: such nodes are used with preemption |
168 | * disabled, and using kernel mutexes in interrupt context isn't allowed. |
169 | * |
170 | * The nodes are used not as a lock as in traditional MCS, but to order |
171 | * waiters. The head of the queue spins against the lock itself, which allows |
172 | * to release the MCS node once the kernel mutex is acquired. |
173 | * |
174 | * Those nodes provide 2 queues: |
175 | * |
176 | * 1. an adaptive spin queue that is used to order threads who chose to |
177 | * adaptively spin to wait for the lock to become available, |
178 | * |
179 | * This queue is doubly linked, threads can add themselves concurrently, |
180 | * the interlock of the mutex is required to dequeue. |
181 | * |
182 | * 2. an interlock queue which is more typical MCS. |
183 | */ |
184 | typedef struct lck_mtx_mcs { |
185 | struct _lck_mtx_ *lmm_ilk_current; |
186 | |
187 | struct lck_mtx_mcs *lmm_ilk_next; |
188 | unsigned long lmm_ilk_ready; |
189 | |
190 | struct lck_mtx_mcs *lmm_as_next; |
191 | unsigned long long lmm_as_prev; |
192 | } __attribute__((aligned(64))) * lck_mtx_mcs_t; |
193 | |
194 | |
195 | /*! |
196 | * @typedef lck_spin_mcs_t |
197 | * |
198 | * @brief |
199 | * The type of per-cpu MCS-like nodes used for various spinlock wait queues. |
200 | * |
201 | * @discussion |
202 | * Unlike the mutex ones, these nodes can be used for spinlocks taken |
203 | * in interrupt context. |
204 | */ |
205 | typedef struct lck_spin_mcs { |
206 | struct lck_spin_mcs *lsm_next; |
207 | const void *lsm_lock; |
208 | unsigned long lsm_ready; |
209 | } *lck_spin_mcs_t; |
210 | |
211 | |
212 | typedef struct lck_mcs { |
213 | struct lck_mtx_mcs mcs_mtx; |
214 | volatile unsigned long mcs_spin_rsv; |
215 | struct lck_spin_mcs mcs_spin[2]; |
216 | } __attribute__((aligned(128))) * lck_mcs_t; |
217 | |
218 | |
219 | PERCPU_DECL(struct lck_mcs, lck_mcs); |
220 | |
221 | typedef uint16_t lck_mcs_id_t; |
222 | |
223 | #define LCK_MCS_ID_CPU_MASK 0x3fff |
224 | #define LCK_MCS_ID_SLOT_SHIFT 14 |
225 | #define LCK_MCS_ID_SLOT_MASK 0xc000 |
226 | |
227 | #define LCK_MCS_SLOT_0 0 |
228 | #define LCK_MCS_SLOT_1 1 |
229 | |
230 | static inline lck_mcs_id_t |
231 | lck_mcs_id_make(int cpu, unsigned long slot) |
232 | { |
233 | return (uint16_t)(((slot + 1) << LCK_MCS_ID_SLOT_SHIFT) | cpu); |
234 | } |
235 | |
236 | static inline lck_mcs_id_t |
237 | lck_mcs_id_current(unsigned long slot) |
238 | { |
239 | return lck_mcs_id_make(cpu: cpu_number(), slot); |
240 | } |
241 | |
242 | static inline uint16_t |
243 | lck_mcs_id_cpu(lck_mcs_id_t mcs_id) |
244 | { |
245 | return mcs_id & LCK_MCS_ID_CPU_MASK; |
246 | } |
247 | |
248 | static inline uint16_t |
249 | lck_mcs_id_slot(lck_mcs_id_t mcs_id) |
250 | { |
251 | return (mcs_id >> LCK_MCS_ID_SLOT_SHIFT) - 1; |
252 | } |
253 | |
254 | static inline lck_mcs_t |
255 | lck_mcs_get_current(void) |
256 | { |
257 | return PERCPU_GET(lck_mcs); |
258 | } |
259 | |
260 | static inline lck_mcs_t |
261 | lck_mcs_get_other(lck_mcs_id_t mcs_id) |
262 | { |
263 | vm_offset_t base = other_percpu_base(cpu_number: lck_mcs_id_cpu(mcs_id)); |
264 | |
265 | return PERCPU_GET_WITH_BASE(base, lck_mcs); |
266 | } |
267 | |
268 | |
269 | static inline lck_spin_mcs_t |
270 | lck_spin_mcs_decode(lck_mcs_id_t mcs_id) |
271 | { |
272 | lck_mcs_t other = lck_mcs_get_other(mcs_id); |
273 | |
274 | return &other->mcs_spin[lck_mcs_id_slot(mcs_id)]; |
275 | } |
276 | |
277 | typedef struct { |
278 | lck_mcs_t txn_mcs; |
279 | lck_spin_mcs_t txn_slot; |
280 | lck_mcs_id_t txn_mcs_id; |
281 | } lck_spin_txn_t; |
282 | |
283 | static inline lck_spin_txn_t |
284 | lck_spin_txn_begin(void *lck) |
285 | { |
286 | lck_spin_txn_t txn; |
287 | unsigned long slot; |
288 | |
289 | txn.txn_mcs = lck_mcs_get_current(); |
290 | os_compiler_barrier(); |
291 | slot = txn.txn_mcs->mcs_spin_rsv++; |
292 | assert(slot <= LCK_MCS_SLOT_1); |
293 | os_compiler_barrier(); |
294 | |
295 | txn.txn_mcs_id = lck_mcs_id_current(slot); |
296 | txn.txn_slot = &txn.txn_mcs->mcs_spin[slot]; |
297 | txn.txn_slot->lsm_lock = lck; |
298 | |
299 | return txn; |
300 | } |
301 | |
302 | static inline bool |
303 | lck_spin_txn_enqueue(lck_spin_txn_t *txn, lck_mcs_id_t *tail) |
304 | { |
305 | lck_spin_mcs_t pnode; |
306 | lck_mcs_id_t pidx; |
307 | |
308 | pidx = os_atomic_xchg(tail, txn->txn_mcs_id, release); |
309 | if (pidx) { |
310 | pnode = lck_spin_mcs_decode(mcs_id: pidx); |
311 | os_atomic_store(&pnode->lsm_next, txn->txn_slot, relaxed); |
312 | return true; |
313 | } |
314 | |
315 | return false; |
316 | } |
317 | |
318 | static inline void |
319 | lck_spin_txn_end(lck_spin_txn_t *txn) |
320 | { |
321 | unsigned long slot = lck_mcs_id_slot(mcs_id: txn->txn_mcs_id); |
322 | lck_mcs_t mcs = txn->txn_mcs; |
323 | |
324 | *txn->txn_slot = (struct lck_spin_mcs){ }; |
325 | *txn = (lck_spin_txn_t){ }; |
326 | |
327 | assert(mcs->mcs_spin_rsv == slot + 1); |
328 | os_atomic_store(&mcs->mcs_spin_rsv, slot, compiler_acq_rel); |
329 | } |
330 | |
331 | |
332 | #pragma GCC visibility pop |
333 | |
334 | __ASSUME_PTR_ABI_SINGLE_END __END_DECLS |
335 | |
336 | #endif /* _KERN_LOCKS_INTERNAL_H_ */ |
337 | |