1 | /* |
2 | * Copyright (c) 2021 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_TICKET_LOCK_H_ |
30 | #define _KERN_TICKET_LOCK_H_ |
31 | |
32 | #ifndef __ASSEMBLER__ |
33 | #include <kern/lock_types.h> |
34 | #include <kern/lock_group.h> |
35 | #if XNU_KERNEL_PRIVATE |
36 | #include <kern/counter.h> |
37 | #endif /* XNU_KERNEL_PRIVATE */ |
38 | #endif /* __ASSEMBLER__ */ |
39 | |
40 | #ifndef __ASSEMBLER__ |
41 | |
42 | __BEGIN_DECLS |
43 | #pragma GCC visibility push(hidden) |
44 | |
45 | #ifdef MACH_KERNEL_PRIVATE |
46 | |
47 | /*! |
48 | * @typedef hw_lck_ticket_t |
49 | * |
50 | * @discussion |
51 | * This type describes the low level type for a ticket lock. |
52 | * @c lck_ticket_t provides a higher level abstraction |
53 | * that also provides thread ownership information. |
54 | * |
55 | * This is a low level lock meant to be part of data structures |
56 | * that are very constrained on space, or is part of a larger lock. |
57 | * |
58 | * This lower level interface supports an @c *_allow_invalid() |
59 | * to implement advanced memory reclamation schemes using sequestering. |
60 | * Do note that when @c CONFIG_PROB_GZALLOC is engaged, and the target lock |
61 | * comes from a zone, PGZ must be handled manually. |
62 | * See ipc_object_lock_allow_invalid() for an example of that. |
63 | * |
64 | * @c hw_lck_ticket_invalidate() must be used on locks |
65 | * that will be used this way: in addition to make subsequent calls to |
66 | * @c hw_lck_ticket_lock_allow_invalid() to fail, it allows for |
67 | * @c hw_lck_ticket_destroy() to synchronize with callers to |
68 | * @c hw_lck_ticket_lock_allow_invalid() who successfully reserved |
69 | * a ticket but will fail, ensuring the memory can't be freed too early. |
70 | * |
71 | * |
72 | * @c hw_lck_ticket_reserve() can be used to pre-reserve a ticket. |
73 | * When this function returns @c true, then the lock was acquired. |
74 | * When it returns @c false, then @c hw_lck_ticket_wait() must |
75 | * be called to wait for this ticket. |
76 | * |
77 | * This can be used to resolve certain lock inversions: assuming |
78 | * two locks, @c L (a mutex or any kind of lock) and @c T (a ticket lock), |
79 | * where @c L can be taken when @c T is held but not the other way around, |
80 | * then the following can be done to take both locks in "the wrong order", |
81 | * with a guarantee of forward progress: |
82 | * |
83 | * <code> |
84 | * // starts with L held |
85 | * uint32_t ticket; |
86 | * |
87 | * if (!hw_lck_ticket_reserve(T, &ticket)) { |
88 | * unlock(L); |
89 | * hw_lck_ticket_wait(T, ticket): |
90 | * lock(L); |
91 | * // possibly validate what might have changed |
92 | * // due to dropping L |
93 | * } |
94 | * |
95 | * // both L and T are held |
96 | * </code> |
97 | * |
98 | * This pattern above is safe even for a case when the protected |
99 | * resource contains the ticket lock @c T, provided that it is |
100 | * guaranteed that both @c T and @c L (in the proper order) will |
101 | * be taken before that resource death. In that case, in the resource |
102 | * destructor, when @c hw_lck_ticket_destroy() is called, it will |
103 | * wait for the reservation to be released. |
104 | * |
105 | * See @c waitq_pull_thread_locked() for an example of this where: |
106 | * - @c L is the thread lock of a thread waiting on a given waitq, |
107 | * - @c T is the lock for that waitq, |
108 | * - the waitq can't be destroyed before the thread is unhooked from it, |
109 | * which happens under both @c L and @c T. |
110 | * |
111 | * |
112 | * @note: |
113 | * At the moment, this construct only supports up to 255 CPUs. |
114 | * Supporting more CPUs requires losing the `lck_type` field, |
115 | * and burning the low bit of the cticket/nticket |
116 | * for the "invalidation" feature. |
117 | */ |
118 | typedef union { |
119 | struct { |
120 | uint8_t lck_type; |
121 | uint8_t lck_valid : 1; |
122 | uint8_t lck_is_pv : 1; |
123 | uint8_t lck_unused : 6; |
124 | union { |
125 | struct { |
126 | uint8_t cticket; |
127 | uint8_t nticket; |
128 | }; |
129 | uint16_t tcurnext; |
130 | }; |
131 | }; |
132 | uint32_t lck_value; |
133 | } hw_lck_ticket_t; |
134 | |
135 | /*! |
136 | * @typedef lck_ticket_t |
137 | * |
138 | * @discussion |
139 | * A higher level construct than hw_lck_ticket_t in 2 words |
140 | * like other kernel locks, which admits thread ownership information. |
141 | */ |
142 | typedef struct { |
143 | uint32_t __lck_ticket_unused : 24; |
144 | uint32_t lck_ticket_type : 8; |
145 | uint32_t lck_ticket_padding; |
146 | hw_lck_ticket_t tu; |
147 | uint32_t lck_ticket_owner; |
148 | } lck_ticket_t; |
149 | |
150 | #else /* !MACH_KERNEL_PRIVATE */ |
151 | |
152 | typedef struct { |
153 | uint32_t opaque0; |
154 | uint32_t opaque1; |
155 | uint32_t opaque2; |
156 | uint32_t opaque3; |
157 | } lck_ticket_t; |
158 | |
159 | #endif /* !MACH_KERNEL_PRIVATE */ |
160 | #if MACH_KERNEL_PRIVATE |
161 | |
162 | #if !LCK_GRP_USE_ARG |
163 | #define hw_lck_ticket_init(lck, grp) hw_lck_ticket_init(lck) |
164 | #define hw_lck_ticket_init_locked(lck, grp) hw_lck_ticket_init_locked(lck) |
165 | #define hw_lck_ticket_destroy(lck, grp) hw_lck_ticket_destroy(lck) |
166 | #define hw_lck_ticket_lock(lck, grp) hw_lck_ticket_lock(lck) |
167 | #define hw_lck_ticket_lock_nopreempt(lck, grp) hw_lck_ticket_lock_nopreempt(lck) |
168 | #define hw_lck_ticket_lock_to(lck, pol, grp) hw_lck_ticket_lock_to(lck, pol) |
169 | #define hw_lck_ticket_lock_nopreempt_to(lck, pol, grp) \ |
170 | hw_lck_ticket_lock_nopreempt_to(lck, pol) |
171 | #define hw_lck_ticket_lock_try(lck, grp) hw_lck_ticket_lock_try(lck) |
172 | #define hw_lck_ticket_lock_try_nopreempt(lck, grp) \ |
173 | hw_lck_ticket_lock_try_nopreempt(lck) |
174 | #define hw_lck_ticket_lock_allow_invalid(lck, pol, grp) \ |
175 | hw_lck_ticket_lock_allow_invalid(lck, pol) |
176 | #define hw_lck_ticket_reserve(lck, t, grp) hw_lck_ticket_reserve(lck, t) |
177 | #define hw_lck_ticket_reserve_nopreempt(lck, t, grp) \ |
178 | hw_lck_ticket_reserve_nopreempt(lck, t) |
179 | #define hw_lck_ticket_reserve_allow_invalid(lck, t, grp) \ |
180 | hw_lck_ticket_reserve_allow_invalid(lck, t) |
181 | #define hw_lck_ticket_wait(lck, ticket, pol, grp) \ |
182 | hw_lck_ticket_wait(lck, ticket, pol) |
183 | #endif /* !LCK_GRP_USE_ARG */ |
184 | |
185 | |
186 | /* init/destroy */ |
187 | |
188 | extern void hw_lck_ticket_init( |
189 | hw_lck_ticket_t *tlock, |
190 | lck_grp_t *grp); |
191 | |
192 | extern void hw_lck_ticket_init_locked( |
193 | hw_lck_ticket_t *tlock, |
194 | lck_grp_t *grp); |
195 | |
196 | extern void hw_lck_ticket_destroy( |
197 | hw_lck_ticket_t *tlock, |
198 | lck_grp_t *grp); |
199 | |
200 | extern void hw_lck_ticket_invalidate( |
201 | hw_lck_ticket_t *tlock); |
202 | |
203 | extern bool hw_lck_ticket_held( |
204 | hw_lck_ticket_t *tlock) __result_use_check; |
205 | |
206 | |
207 | /* lock */ |
208 | |
209 | extern void hw_lck_ticket_lock( |
210 | hw_lck_ticket_t *tlock, |
211 | lck_grp_t *grp); |
212 | |
213 | extern void hw_lck_ticket_lock_nopreempt( |
214 | hw_lck_ticket_t *tlock, |
215 | lck_grp_t *grp); |
216 | |
217 | extern hw_lock_status_t hw_lck_ticket_lock_to( |
218 | hw_lck_ticket_t *tlock, |
219 | hw_spin_policy_t policy, |
220 | lck_grp_t *grp); |
221 | |
222 | extern hw_lock_status_t hw_lck_ticket_lock_nopreempt_to( |
223 | hw_lck_ticket_t *tlock, |
224 | hw_spin_policy_t policy, |
225 | lck_grp_t *grp); |
226 | |
227 | |
228 | /* lock_try */ |
229 | |
230 | extern bool hw_lck_ticket_lock_try( |
231 | hw_lck_ticket_t *tlock, |
232 | lck_grp_t *grp) __result_use_check; |
233 | |
234 | extern bool hw_lck_ticket_lock_try_nopreempt( |
235 | hw_lck_ticket_t *tlock, |
236 | lck_grp_t *grp) __result_use_check; |
237 | |
238 | |
239 | /* unlock */ |
240 | |
241 | extern void hw_lck_ticket_unlock( |
242 | hw_lck_ticket_t *tlock); |
243 | |
244 | extern void hw_lck_ticket_unlock_nopreempt( |
245 | hw_lck_ticket_t *tlock); |
246 | |
247 | |
248 | /* reserve/wait */ |
249 | |
250 | extern bool hw_lck_ticket_reserve( |
251 | hw_lck_ticket_t *tlock, |
252 | uint32_t *ticket, |
253 | lck_grp_t *grp) __result_use_check; |
254 | |
255 | extern bool hw_lck_ticket_reserve_nopreempt( |
256 | hw_lck_ticket_t *tlock, |
257 | uint32_t *ticket, |
258 | lck_grp_t *grp) __result_use_check; |
259 | |
260 | extern hw_lock_status_t hw_lck_ticket_reserve_allow_invalid( |
261 | hw_lck_ticket_t *tlock, |
262 | uint32_t *ticket, |
263 | lck_grp_t *grp) __result_use_check; |
264 | |
265 | extern hw_lock_status_t hw_lck_ticket_wait( |
266 | hw_lck_ticket_t *tlock, |
267 | uint32_t ticket, |
268 | hw_spin_policy_t policy, |
269 | lck_grp_t *grp); |
270 | |
271 | extern hw_lock_status_t hw_lck_ticket_lock_allow_invalid( |
272 | hw_lck_ticket_t *tlock, |
273 | hw_spin_policy_t policy, |
274 | lck_grp_t *grp); |
275 | |
276 | /* pv */ |
277 | |
278 | extern void hw_lck_ticket_unlock_kick_pv( |
279 | hw_lck_ticket_t *tlock, |
280 | uint8_t value); |
281 | |
282 | extern void hw_lck_ticket_lock_wait_pv( |
283 | hw_lck_ticket_t *tlock, |
284 | uint8_t value); |
285 | |
286 | #endif /* MACH_KERNEL_PRIVATE */ |
287 | #if XNU_KERNEL_PRIVATE |
288 | |
289 | extern bool kdp_lck_ticket_is_acquired( |
290 | lck_ticket_t *tlock) __result_use_check; |
291 | |
292 | extern void lck_ticket_lock_nopreempt( |
293 | lck_ticket_t *tlock, |
294 | lck_grp_t *grp); |
295 | |
296 | extern bool lck_ticket_lock_try( |
297 | lck_ticket_t *tlock, |
298 | lck_grp_t *grp) __result_use_check; |
299 | |
300 | extern bool lck_ticket_lock_try_nopreempt( |
301 | lck_ticket_t *tlock, |
302 | lck_grp_t *grp) __result_use_check; |
303 | |
304 | extern void lck_ticket_unlock_nopreempt( |
305 | lck_ticket_t *tlock); |
306 | |
307 | #endif /* XNU_KERNEL_PRIVATE */ |
308 | |
309 | extern __exported void lck_ticket_init( |
310 | lck_ticket_t *tlock, |
311 | lck_grp_t *grp); |
312 | |
313 | extern __exported void lck_ticket_destroy( |
314 | lck_ticket_t *tlock, |
315 | lck_grp_t *grp); |
316 | |
317 | extern __exported void lck_ticket_lock( |
318 | lck_ticket_t *tlock, |
319 | lck_grp_t *grp); |
320 | |
321 | extern __exported void lck_ticket_unlock( |
322 | lck_ticket_t *tlock); |
323 | |
324 | extern __exported void lck_ticket_assert_owned( |
325 | const lck_ticket_t *tlock); |
326 | |
327 | extern __exported void lck_ticket_assert_not_owned( |
328 | const lck_ticket_t *tlock); |
329 | |
330 | #if MACH_ASSERT |
331 | #define LCK_TICKET_ASSERT_OWNED(tlock) lck_ticket_assert_owned(tlock) |
332 | #define LCK_TICKET_ASSERT_NOT_OWNED(tlock) lck_ticket_assert_owned(tlock) |
333 | #else |
334 | #define LCK_TICKET_ASSERT_OWNED(tlock) (void)(tlock) |
335 | #define LCK_TICKET_ASSERT_NOT_OWNED(tlock) (void)(tlock) |
336 | #endif |
337 | |
338 | #pragma GCC visibility pop |
339 | __END_DECLS |
340 | |
341 | #endif /* __ASSEMBLER__ */ |
342 | #if XNU_KERNEL_PRIVATE |
343 | |
344 | #define HW_LCK_TICKET_LOCK_VALID_BIT 8 |
345 | |
346 | #if CONFIG_PV_TICKET |
347 | |
348 | /* |
349 | * For the PV case, the lsbit of cticket is treated as as wait flag, |
350 | * and the ticket counters are incremented by 2 |
351 | */ |
352 | #define HW_LCK_TICKET_LOCK_PVWAITFLAG ((uint8_t)1) |
353 | #define HW_LCK_TICKET_LOCK_INCREMENT ((uint8_t)2) |
354 | #define HW_LCK_TICKET_LOCK_INC_WORD 0x02000000 |
355 | |
356 | #if !defined(__ASSEMBLER__) && (DEBUG || DEVELOPMENT) |
357 | /* counters for sysctls */ |
358 | SCALABLE_COUNTER_DECLARE(ticket_wflag_cleared); |
359 | SCALABLE_COUNTER_DECLARE(ticket_wflag_still); |
360 | SCALABLE_COUNTER_DECLARE(ticket_just_unlock); |
361 | SCALABLE_COUNTER_DECLARE(ticket_kick_count); |
362 | SCALABLE_COUNTER_DECLARE(ticket_wait_count); |
363 | SCALABLE_COUNTER_DECLARE(ticket_already_count); |
364 | SCALABLE_COUNTER_DECLARE(ticket_spin_count); |
365 | #define PVTICKET_STATS_ADD(var, i) counter_add_preemption_disabled(&ticket_##var, (i)) |
366 | #define PVTICKET_STATS_INC(var) counter_inc_preemption_disabled(&ticket_##var) |
367 | #else |
368 | #define PVTICKET_STATS_ADD(var, i) /* empty */ |
369 | #define PVTICKET_STATS_INC(var) /* empty */ |
370 | #endif |
371 | |
372 | #else /* CONFIG_PV_TICKET */ |
373 | |
374 | #define HW_LCK_TICKET_LOCK_PVWAITFLAG ((uint8_t)0) |
375 | #define HW_LCK_TICKET_LOCK_INCREMENT ((uint8_t)1) |
376 | #define HW_LCK_TICKET_LOCK_INC_WORD 0x01000000 |
377 | |
378 | #endif /* CONFIG_PV_TICKET */ |
379 | #endif /* XNU_KERNEL_PRIVATE */ |
380 | #endif /* _KERN_TICKET_LOCK_H_ */ |
381 | |