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 */
118typedef 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 */
142typedef 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
152typedef 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
188extern void hw_lck_ticket_init(
189 hw_lck_ticket_t *tlock,
190 lck_grp_t *grp);
191
192extern void hw_lck_ticket_init_locked(
193 hw_lck_ticket_t *tlock,
194 lck_grp_t *grp);
195
196extern void hw_lck_ticket_destroy(
197 hw_lck_ticket_t *tlock,
198 lck_grp_t *grp);
199
200extern void hw_lck_ticket_invalidate(
201 hw_lck_ticket_t *tlock);
202
203extern bool hw_lck_ticket_held(
204 hw_lck_ticket_t *tlock) __result_use_check;
205
206
207/* lock */
208
209extern void hw_lck_ticket_lock(
210 hw_lck_ticket_t *tlock,
211 lck_grp_t *grp);
212
213extern void hw_lck_ticket_lock_nopreempt(
214 hw_lck_ticket_t *tlock,
215 lck_grp_t *grp);
216
217extern 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
222extern 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
230extern bool hw_lck_ticket_lock_try(
231 hw_lck_ticket_t *tlock,
232 lck_grp_t *grp) __result_use_check;
233
234extern 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
241extern void hw_lck_ticket_unlock(
242 hw_lck_ticket_t *tlock);
243
244extern void hw_lck_ticket_unlock_nopreempt(
245 hw_lck_ticket_t *tlock);
246
247
248/* reserve/wait */
249
250extern bool hw_lck_ticket_reserve(
251 hw_lck_ticket_t *tlock,
252 uint32_t *ticket,
253 lck_grp_t *grp) __result_use_check;
254
255extern 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
260extern 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
265extern 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
271extern 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
278extern void hw_lck_ticket_unlock_kick_pv(
279 hw_lck_ticket_t *tlock,
280 uint8_t value);
281
282extern 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
289extern bool kdp_lck_ticket_is_acquired(
290 lck_ticket_t *tlock) __result_use_check;
291
292extern void lck_ticket_lock_nopreempt(
293 lck_ticket_t *tlock,
294 lck_grp_t *grp);
295
296extern bool lck_ticket_lock_try(
297 lck_ticket_t *tlock,
298 lck_grp_t *grp) __result_use_check;
299
300extern bool lck_ticket_lock_try_nopreempt(
301 lck_ticket_t *tlock,
302 lck_grp_t *grp) __result_use_check;
303
304extern void lck_ticket_unlock_nopreempt(
305 lck_ticket_t *tlock);
306
307#endif /* XNU_KERNEL_PRIVATE */
308
309extern __exported void lck_ticket_init(
310 lck_ticket_t *tlock,
311 lck_grp_t *grp);
312
313extern __exported void lck_ticket_destroy(
314 lck_ticket_t *tlock,
315 lck_grp_t *grp);
316
317extern __exported void lck_ticket_lock(
318 lck_ticket_t *tlock,
319 lck_grp_t *grp);
320
321extern __exported void lck_ticket_unlock(
322 lck_ticket_t *tlock);
323
324extern __exported void lck_ticket_assert_owned(
325 const lck_ticket_t *tlock);
326
327extern __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 */
358SCALABLE_COUNTER_DECLARE(ticket_wflag_cleared);
359SCALABLE_COUNTER_DECLARE(ticket_wflag_still);
360SCALABLE_COUNTER_DECLARE(ticket_just_unlock);
361SCALABLE_COUNTER_DECLARE(ticket_kick_count);
362SCALABLE_COUNTER_DECLARE(ticket_wait_count);
363SCALABLE_COUNTER_DECLARE(ticket_already_count);
364SCALABLE_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