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#define LOCK_PRIVATE 1
30#include <stdint.h>
31#include <kern/thread.h>
32#include <kern/locks_internal.h>
33#include <kern/locks.h>
34#include <kern/lock_stat.h>
35#include <machine/machine_cpu.h>
36#include <vm/pmap.h>
37#include <san/kasan.h>
38
39/*
40 * "Ticket": A FIFO spinlock with constant backoff
41 * cf. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors
42 * by Mellor-Crumney and Scott, 1991
43 *
44 * Note: 'cticket' is 'now_serving', 'nticket' is 'next_ticket'
45 */
46
47/*
48 * TODO: proportional back-off based on desired-current ticket distance
49 * This has the potential to considerably reduce snoop traffic
50 * but must be tuned carefully
51 * TODO: Evaluate a bias towards the performant clusters on
52 * asymmetric efficient/performant multi-cluster systems, while
53 * retaining the starvation-free property. A small intra-cluster bias may
54 * be profitable for overall throughput
55 */
56
57#if defined(__x86_64__)
58#include <i386/mp.h>
59extern uint64_t LockTimeOutTSC;
60#define TICKET_LOCK_PANIC_TIMEOUT LockTimeOutTSC
61#endif /* defined(__x86_64__) */
62
63#if defined(__arm64__)
64extern uint64_t TLockTimeOut;
65#define TICKET_LOCK_PANIC_TIMEOUT TLockTimeOut
66#endif /* defined(__arm64__) */
67
68#if CONFIG_PV_TICKET
69
70/*
71 * Tunable that controls how many pause/wfe loops
72 * to execute before checking for timeouts and
73 * issuing a "wait" hypercall.
74 */
75#if __x86_64__
76#define DEFAULT_TICKET_LOOPS (LOCK_SNOOP_SPINS)
77#else
78#define DEFAULT_TICKET_LOOPS (LOCK_SNOOP_SPINS / 8)
79#endif
80uint32_t ticket_lock_spins = DEFAULT_TICKET_LOOPS;
81#define TICKET_LOCK_SNOOP_LOOPS ticket_lock_spins
82
83#else /* CONFIG_PV_TICKET */
84
85/*
86 * How many pause/wfe loops to execute before
87 * checking for timeouts.
88 */
89#define TICKET_LOCK_SNOOP_LOOPS LOCK_SNOOP_SPINS
90
91#endif /* CONFIG_PV_TICKET */
92
93/*
94 * Current ticket size limit--tickets can be trivially expanded
95 * to 16-bits if needed
96 */
97static_assert(MAX_CPUS < (256 / HW_LCK_TICKET_LOCK_INCREMENT));
98static_assert(sizeof(hw_lck_ticket_t) == 4);
99static_assert(offsetof(hw_lck_ticket_t, tcurnext) == 2);
100static_assert(offsetof(hw_lck_ticket_t, cticket) == 2);
101static_assert(offsetof(hw_lck_ticket_t, nticket) == 3);
102static_assert(HW_LCK_TICKET_LOCK_INC_WORD ==
103 (HW_LCK_TICKET_LOCK_INCREMENT << (8 * offsetof(hw_lck_ticket_t, nticket))));
104#if 0 /* the expression below is sadly not constant, thank you for nothing C */
105static_assert((1u << HW_LCK_TICKET_LOCK_VALID_BIT) ==
106 ((hw_lck_ticket_t){ .lck_valid = 1 }).lck_value);
107#endif
108
109__header_always_inline int
110equal_tickets(uint8_t t0, uint8_t t1)
111{
112 return !((t0 ^ t1) & ~HW_LCK_TICKET_LOCK_PVWAITFLAG);
113}
114
115__header_always_inline uint8_t
116ticket_count(uint8_t t)
117{
118 return t & ~HW_LCK_TICKET_LOCK_PVWAITFLAG;
119}
120
121__abortlike
122static void
123__hw_lck_ticket_invalid_panic(hw_lck_ticket_t *lck)
124{
125 panic("Invalid HW ticket lock %p <0x%08x>", lck, lck->lck_value);
126}
127
128__abortlike
129static void
130__lck_ticket_invalid_panic(lck_ticket_t *lck)
131{
132 panic("Invalid ticket lock %p <0x%08x 0x%08x 0x%08x 0x%08x>",
133 lck, *(uint32_t *)lck, lck->lck_ticket_owner,
134 lck->tu.lck_value, lck->lck_ticket_padding);
135}
136
137__abortlike
138static void
139__lck_ticket_owned_panic(const lck_ticket_t *lck)
140{
141 thread_t self = current_thread();
142
143 panic("Ticket lock %p is unexpectedly owned by thread %p", lck, self);
144}
145
146__abortlike
147static void
148__lck_ticket_not_owned_panic(const lck_ticket_t *lck)
149{
150 thread_t self = current_thread();
151
152 panic("Ticket lock %p is unexpectedly not owned by thread %p", lck, self);
153}
154
155static inline void
156hw_lck_ticket_verify(hw_lck_ticket_t *lck)
157{
158 if (lck->lck_type != LCK_TYPE_TICKET) {
159 __hw_lck_ticket_invalid_panic(lck);
160 }
161}
162
163static inline void
164lck_ticket_verify(lck_ticket_t *tlock)
165{
166 if (tlock->lck_ticket_type != LCK_TYPE_TICKET) {
167 __lck_ticket_invalid_panic(lck: tlock);
168 }
169}
170
171#if DEVELOPMENT || DEBUG
172#define HW_LCK_TICKET_VERIFY(lck) hw_lck_ticket_verify(lck)
173#define LCK_TICKET_VERIFY(lck) lck_ticket_verify(lck)
174#define LCK_TICKET_UNLOCK_VERIFY(l) ({ \
175 if ((l)->lck_ticket_owner != current_thread()->ctid) { \
176 __lck_ticket_not_owned_panic(l); \
177 } \
178})
179#else
180#define HW_LCK_TICKET_VERIFY(lck) ((void)0)
181#define LCK_TICKET_VERIFY(lck) ((void)0)
182#define LCK_TICKET_UNLOCK_VERIFY(l) ((void)0)
183#endif /* DEVELOPMENT || DEBUG */
184
185MARK_AS_HIBERNATE_TEXT void
186hw_lck_ticket_init(hw_lck_ticket_t *lck, lck_grp_t *grp)
187{
188 assert(((uintptr_t)lck & 3) == 0);
189 os_atomic_store(lck, ((hw_lck_ticket_t){
190 .lck_type = LCK_TYPE_TICKET,
191#if CONFIG_PV_TICKET
192 .lck_is_pv = has_lock_pv,
193#endif /* CONFIG_PV_TICKET */
194 .lck_valid = 1,
195 }), relaxed);
196
197#if LCK_GRP_USE_ARG
198 if (grp) {
199 lck_grp_reference(grp, &grp->lck_grp_ticketcnt);
200 }
201#endif /* LCK_GRP_USE_ARG */
202}
203
204void
205hw_lck_ticket_init_locked(hw_lck_ticket_t *lck, lck_grp_t *grp)
206{
207 assert(((uintptr_t)lck & 3) == 0);
208
209 lock_disable_preemption_for_thread(current_thread());
210
211 os_atomic_store(lck, ((hw_lck_ticket_t){
212 .lck_type = LCK_TYPE_TICKET,
213#if CONFIG_PV_TICKET
214 .lck_is_pv = has_lock_pv,
215#endif /* CONFIG_PV_TICKET */
216 .lck_valid = 1,
217 .nticket = HW_LCK_TICKET_LOCK_INCREMENT,
218 }), relaxed);
219
220#if LCK_GRP_USE_ARG
221 if (grp) {
222 lck_grp_reference(grp, &grp->lck_grp_ticketcnt);
223 }
224#endif /* LCK_GRP_USE_ARG */
225}
226
227MARK_AS_HIBERNATE_TEXT void
228lck_ticket_init(lck_ticket_t *tlock, __unused lck_grp_t *grp)
229{
230 *tlock = (lck_ticket_t){
231 .lck_ticket_type = LCK_TYPE_TICKET,
232 .tu = {
233 .lck_type = LCK_TYPE_TICKET,
234#if CONFIG_PV_TICKET
235 .lck_is_pv = has_lock_pv,
236#endif /* CONFIG_PV_TICKET */
237 .lck_valid = 1,
238 },
239 };
240
241#if LCK_GRP_USE_ARG
242 if (grp) {
243 lck_grp_reference(grp, &grp->lck_grp_ticketcnt);
244 }
245#endif /* LCK_GRP_USE_ARG */
246}
247
248static inline void
249hw_lck_ticket_destroy_internal(hw_lck_ticket_t *lck, bool sync
250 LCK_GRP_ARG(lck_grp_t *grp))
251{
252 __assert_only hw_lck_ticket_t tmp;
253
254 tmp.lck_value = os_atomic_load(&lck->lck_value, relaxed);
255
256 if (__improbable(sync && !tmp.lck_valid && !equal_tickets(tmp.nticket, tmp.cticket))) {
257 /*
258 * If the lock has been invalidated and there are pending
259 * reservations, it means hw_lck_ticket_lock_allow_invalid()
260 * or hw_lck_ticket_reserve() are being used.
261 *
262 * Such caller do not guarantee the liveness of the object
263 * they try to lock, we need to flush their reservations
264 * before proceeding.
265 *
266 * Because the lock is FIFO, we go through a cycle of
267 * locking/unlocking which will have this effect, because
268 * the lock is now invalid, new calls to
269 * hw_lck_ticket_lock_allow_invalid() will fail before taking
270 * a reservation, and we can safely destroy the lock.
271 */
272 hw_lck_ticket_lock(lck, grp);
273 hw_lck_ticket_unlock(tlock: lck);
274 }
275
276 os_atomic_store(&lck->lck_value, 0U, relaxed);
277
278#if LCK_GRP_USE_ARG
279 if (grp) {
280 lck_grp_deallocate(grp, &grp->lck_grp_ticketcnt);
281 }
282#endif /* LCK_GRP_USE_ARG */
283}
284
285void
286hw_lck_ticket_destroy(hw_lck_ticket_t *lck, lck_grp_t *grp)
287{
288 hw_lck_ticket_verify(lck);
289 hw_lck_ticket_destroy_internal(lck, true LCK_GRP_ARG(grp));
290}
291
292void
293lck_ticket_destroy(lck_ticket_t *tlock, __unused lck_grp_t *grp)
294{
295 lck_ticket_verify(tlock);
296 assert(tlock->lck_ticket_owner == 0);
297 tlock->lck_ticket_type = LCK_TYPE_NONE;
298 hw_lck_ticket_destroy_internal(lck: &tlock->tu, false LCK_GRP_ARG(grp));
299}
300
301bool
302hw_lck_ticket_held(hw_lck_ticket_t *lck)
303{
304 hw_lck_ticket_t tmp;
305 tmp.tcurnext = os_atomic_load(&lck->tcurnext, relaxed);
306 return !equal_tickets(t0: tmp.cticket, t1: tmp.nticket);
307}
308
309bool
310kdp_lck_ticket_is_acquired(lck_ticket_t *lck)
311{
312 if (not_in_kdp) {
313 panic("panic: ticket lock acquired check done outside of kernel debugger");
314 }
315 return hw_lck_ticket_held(lck: &lck->tu);
316}
317
318static inline void
319tlock_mark_owned(lck_ticket_t *tlock, thread_t cthread)
320{
321 /*
322 * There is a small pre-emption disabled window (also interrupts masked
323 * for the pset lock) between the acquisition of the lock and the
324 * population of the advisory 'owner' thread field
325 * On architectures with a DCAS (ARM v8.1 or x86), conceivably we could
326 * populate the next ticket and the thread atomically, with
327 * possible overhead, potential loss of micro-architectural fwd progress
328 * properties of an unconditional fetch-add, and a 16 byte alignment requirement.
329 */
330 assert3u(tlock->lck_ticket_owner, ==, 0);
331 os_atomic_store(&tlock->lck_ticket_owner, cthread->ctid, relaxed);
332}
333
334__abortlike
335static hw_spin_timeout_status_t
336hw_lck_ticket_timeout_panic(void *_lock, hw_spin_timeout_t to, hw_spin_state_t st)
337{
338 lck_spinlock_to_info_t lsti;
339 hw_lck_ticket_t *lck = _lock;
340 hw_lck_ticket_t tmp;
341
342 tmp.lck_value = os_atomic_load(&lck->lck_value, relaxed);
343
344 if (pmap_in_ppl()) {
345 panic("Ticket spinlock[%p] " HW_SPIN_TIMEOUT_FMT "; "
346 "cticket: 0x%x, nticket: 0x%x, valid: %d, "
347 HW_SPIN_TIMEOUT_DETAILS_FMT,
348 lck, HW_SPIN_TIMEOUT_ARG(to, st),
349 tmp.cticket, tmp.nticket, tmp.lck_valid,
350 HW_SPIN_TIMEOUT_DETAILS_ARG(to, st));
351 }
352
353 lsti = lck_spinlock_timeout_hit(lck, owner: 0);
354 panic("Ticket spinlock[%p] " HW_SPIN_TIMEOUT_FMT "; "
355 "cticket: 0x%x, nticket: 0x%x, waiting for 0x%x, valid: %d, "
356 HW_SPIN_TIMEOUT_DETAILS_FMT,
357 lck, HW_SPIN_TIMEOUT_ARG(to, st),
358 tmp.cticket, tmp.nticket, lsti->extra, tmp.lck_valid,
359 HW_SPIN_TIMEOUT_DETAILS_ARG(to, st));
360}
361
362__abortlike
363static hw_spin_timeout_status_t
364lck_ticket_timeout_panic(void *_lock, hw_spin_timeout_t to, hw_spin_state_t st)
365{
366 lck_spinlock_to_info_t lsti;
367 lck_ticket_t *lck = _lock;
368 hw_lck_ticket_t tmp;
369
370 lsti = lck_spinlock_timeout_hit(lck: &lck->tu, owner: lck->lck_ticket_owner);
371 tmp.tcurnext = os_atomic_load(&lck->tu.tcurnext, relaxed);
372
373 panic("Ticket spinlock[%p] " HW_SPIN_TIMEOUT_FMT "; "
374 "cticket: 0x%x, nticket: 0x%x, waiting for 0x%x, "
375 "current owner: %p (on CPU %d), "
376#if DEBUG || DEVELOPMENT
377 "orig owner: %p, "
378#endif /* DEBUG || DEVELOPMENT */
379 HW_SPIN_TIMEOUT_DETAILS_FMT,
380 lck, HW_SPIN_TIMEOUT_ARG(to, st),
381 tmp.cticket, tmp.nticket, lsti->extra,
382 (void *)lsti->owner_thread_cur, lsti->owner_cpu,
383#if DEBUG || DEVELOPMENT
384 (void *)lsti->owner_thread_orig,
385#endif /* DEBUG || DEVELOPMENT */
386 HW_SPIN_TIMEOUT_DETAILS_ARG(to, st));
387}
388
389static const struct hw_spin_policy hw_lck_ticket_spin_policy = {
390 .hwsp_name = "hw_lck_ticket_lock",
391 .hwsp_timeout = &TICKET_LOCK_PANIC_TIMEOUT,
392 .hwsp_op_timeout = hw_lck_ticket_timeout_panic,
393};
394
395static const struct hw_spin_policy lck_ticket_spin_policy = {
396 .hwsp_name = "lck_ticket_lock",
397 .hwsp_timeout = &TICKET_LOCK_PANIC_TIMEOUT,
398 .hwsp_lock_offset = offsetof(lck_ticket_t, tu),
399 .hwsp_op_timeout = lck_ticket_timeout_panic,
400};
401
402
403#if CONFIG_PV_TICKET
404
405#if DEBUG || DEVELOPMENT
406SCALABLE_COUNTER_DEFINE(ticket_wflag_cleared);
407SCALABLE_COUNTER_DEFINE(ticket_wflag_still);
408SCALABLE_COUNTER_DEFINE(ticket_just_unlock);
409SCALABLE_COUNTER_DEFINE(ticket_kick_count);
410SCALABLE_COUNTER_DEFINE(ticket_wait_count);
411SCALABLE_COUNTER_DEFINE(ticket_already_count);
412SCALABLE_COUNTER_DEFINE(ticket_spin_count);
413#endif
414
415static inline void
416hw_lck_ticket_unlock_inner_pv(hw_lck_ticket_t *lck)
417{
418 const uint8_t cticket = (uint8_t) os_atomic_add(&lck->cticket,
419 HW_LCK_TICKET_LOCK_INCREMENT, acq_rel);
420 if (__improbable(cticket & HW_LCK_TICKET_LOCK_PVWAITFLAG)) {
421 hw_lck_ticket_unlock_kick_pv(tlock: lck, value: ticket_count(t: cticket));
422 } else {
423 PVTICKET_STATS_INC(just_unlock);
424 }
425}
426#endif /* CONFIG_PV_TICKET */
427
428__header_always_inline void
429hw_lck_ticket_unlock_inner(hw_lck_ticket_t *lck)
430{
431 _Atomic uint8_t *ctp = (_Atomic uint8_t *)&lck->cticket;
432 uint8_t cticket;
433
434 /*
435 * Do not use os_atomic* here, we want non volatile atomics
436 * so that the compiler can codegen an `incb` on Intel.
437 */
438 cticket = atomic_load_explicit(ctp, memory_order_relaxed);
439 atomic_store_explicit(ctp, cticket +
440 HW_LCK_TICKET_LOCK_INCREMENT, memory_order_release);
441}
442
443__header_always_inline void
444hw_lck_ticket_unlock_internal_nopreempt(hw_lck_ticket_t *lck)
445{
446#if CONFIG_PV_TICKET
447 if (lck->lck_is_pv) {
448 hw_lck_ticket_unlock_inner_pv(lck);
449 } else {
450 hw_lck_ticket_unlock_inner(lck);
451 }
452#else
453 hw_lck_ticket_unlock_inner(lck);
454#endif
455#if CONFIG_DTRACE
456 LOCKSTAT_RECORD(LS_LCK_TICKET_LOCK_RELEASE, lck);
457#endif /* CONFIG_DTRACE */
458}
459
460__header_always_inline void
461hw_lck_ticket_unlock_internal(hw_lck_ticket_t *lck)
462{
463 hw_lck_ticket_unlock_internal_nopreempt(lck);
464 lock_enable_preemption();
465}
466
467struct hw_lck_ticket_reserve_arg {
468 uint8_t mt;
469 bool validate;
470};
471
472/*
473 * On contention, poll for ownership
474 * Returns when the current ticket is observed equal to "mt"
475 */
476__result_use_check
477static hw_lock_status_t __attribute__((noinline))
478hw_lck_ticket_contended(
479 hw_lck_ticket_t *lck,
480 struct hw_lck_ticket_reserve_arg arg,
481 hw_spin_policy_t pol
482 LCK_GRP_ARG(lck_grp_t *grp))
483{
484 hw_spin_timeout_t to = hw_spin_compute_timeout(policy: pol);
485 hw_spin_state_t state = { };
486 uint32_t pv_spin_count = 0;
487 hw_lck_ticket_t value;
488
489#if CONFIG_DTRACE || LOCK_STATS
490 uint64_t begin = 0;
491 boolean_t stat_enabled = lck_grp_ticket_spin_enabled(lock: lck LCK_GRP_ARG(grp));
492
493 if (__improbable(stat_enabled)) {
494 begin = mach_absolute_time();
495 }
496#endif /* CONFIG_DTRACE || LOCK_STATS */
497
498 while (__improbable(!hw_spin_wait_until_n(TICKET_LOCK_SNOOP_LOOPS,
499 &lck->lck_value, value.lck_value,
500 (pv_spin_count++, equal_tickets(value.cticket, arg.mt))))) {
501 if (state.hwss_deadline == 0 && !hw_spin_in_ppl(to)) {
502 /* remember the droid we're looking for */
503 PERCPU_GET(lck_spinlock_to_info)->extra = arg.mt;
504 }
505
506 if (__improbable(!hw_spin_should_keep_spinning(lck, pol, to, &state))) {
507#if CONFIG_PV_TICKET
508 PVTICKET_STATS_ADD(spin_count, pv_spin_count);
509#endif /* CONFIG_PV_TICKET */
510#if CONFIG_DTRACE || LOCK_STATS
511 if (__improbable(stat_enabled)) {
512 lck_grp_ticket_update_spin(lock: lck LCK_GRP_ARG(grp),
513 time: mach_absolute_time() - begin);
514 }
515 lck_grp_ticket_update_miss(lock: lck LCK_GRP_ARG(grp));
516#endif /* CONFIG_DTRACE || LOCK_STATS */
517 return HW_LOCK_CONTENDED;
518 }
519
520#if CONFIG_PV_TICKET
521 if (lck->lck_is_pv) {
522 os_atomic_or(&lck->cticket, HW_LCK_TICKET_LOCK_PVWAITFLAG, acq_rel);
523 hw_lck_ticket_lock_wait_pv(tlock: lck, value: arg.mt);
524 }
525#endif /* CONFIG_PV_TICKET */
526 }
527
528 /*
529 * We now have successfully acquired the lock
530 */
531
532#if CONFIG_PV_TICKET
533 PVTICKET_STATS_ADD(spin_count, pv_spin_count);
534 if (__improbable(value.cticket & HW_LCK_TICKET_LOCK_PVWAITFLAG)) {
535 /*
536 * Try and clear the wait flag
537 */
538 const hw_lck_ticket_t olck = {
539 .cticket = value.cticket,
540 .nticket = ticket_count(t: value.cticket)
541 + HW_LCK_TICKET_LOCK_INCREMENT,
542 };
543 const hw_lck_ticket_t nlck = {
544 .cticket = ticket_count(t: value.cticket),
545 .nticket = olck.nticket,
546 };
547 if (os_atomic_cmpxchg(&lck->tcurnext,
548 olck.tcurnext, nlck.tcurnext, acq_rel)) {
549 PVTICKET_STATS_INC(wflag_cleared);
550 } else {
551 PVTICKET_STATS_INC(wflag_still);
552 }
553 }
554#endif /* CONFIG_PV_TICKET */
555#if CONFIG_DTRACE || LOCK_STATS
556 if (__improbable(stat_enabled)) {
557 lck_grp_ticket_update_spin(lock: lck LCK_GRP_ARG(grp),
558 time: mach_absolute_time() - begin);
559 }
560 lck_grp_ticket_update_miss(lock: lck LCK_GRP_ARG(grp));
561 lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
562#endif /* CONFIG_DTRACE || LOCK_STATS */
563
564 if (__improbable(arg.validate && !value.lck_valid)) {
565 /*
566 * We got the lock, however the caller is
567 * hw_lck_ticket_lock_allow_invalid() and the
568 * lock has been invalidated while we were
569 * waiting for our turn.
570 *
571 * We need to unlock and pretend we failed.
572 */
573 hw_lck_ticket_unlock_internal(lck);
574 return HW_LOCK_INVALID;
575 }
576
577 os_atomic_thread_fence(acquire);
578 return HW_LOCK_ACQUIRED;
579}
580
581static void __attribute__((noinline))
582lck_ticket_contended(lck_ticket_t *tlock, uint8_t mt, thread_t cthread
583 LCK_GRP_ARG(lck_grp_t *grp))
584{
585 if (cthread->ctid == tlock->lck_ticket_owner) {
586 __lck_ticket_owned_panic(lck: tlock);
587 }
588
589 struct hw_lck_ticket_reserve_arg arg = { .mt = mt };
590 lck_spinlock_timeout_set_orig_ctid(ctid: tlock->lck_ticket_owner);
591 (void)hw_lck_ticket_contended(lck: &tlock->tu, arg, pol: &lck_ticket_spin_policy
592 LCK_GRP_ARG(grp));
593 lck_spinlock_timeout_set_orig_ctid(ctid: 0);
594 tlock_mark_owned(tlock, cthread);
595}
596
597static inline uint32_t
598hw_lck_ticket_reserve_orig(hw_lck_ticket_t *lck)
599{
600 /*
601 * Atomically load both the entier lock state, and increment the
602 * "nticket". Wrap of the ticket field is OK as long as the total
603 * number of contending CPUs is < maximum ticket
604 */
605 return os_atomic_add_orig(&lck->lck_value,
606 HW_LCK_TICKET_LOCK_INC_WORD, acquire);
607}
608
609__header_always_inline void
610hw_lck_ticket_lock_internal(
611 hw_lck_ticket_t *lck
612 LCK_GRP_ARG(lck_grp_t *grp))
613{
614 hw_lck_ticket_t tmp;
615
616 HW_LCK_TICKET_VERIFY(lck);
617 tmp.lck_value = hw_lck_ticket_reserve_orig(lck);
618
619 if (__probable(equal_tickets(tmp.cticket, tmp.nticket))) {
620 return lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
621 }
622
623 /* Contention? branch to out of line contended block */
624 struct hw_lck_ticket_reserve_arg arg = { .mt = tmp.nticket };
625 (void)hw_lck_ticket_contended(lck, arg, pol: &hw_lck_ticket_spin_policy
626 LCK_GRP_ARG(grp));
627}
628
629void
630hw_lck_ticket_lock_nopreempt(hw_lck_ticket_t *lck, lck_grp_t *grp)
631{
632 hw_lck_ticket_lock_internal(lck LCK_GRP_ARG(grp));
633}
634
635void
636hw_lck_ticket_lock(hw_lck_ticket_t *lck, lck_grp_t *grp)
637{
638 lock_disable_preemption_for_thread(current_thread());
639 hw_lck_ticket_lock_internal(lck LCK_GRP_ARG(grp));
640}
641
642__header_always_inline hw_lock_status_t
643hw_lck_ticket_lock_to_internal(
644 hw_lck_ticket_t *lck,
645 hw_spin_policy_t pol
646 LCK_GRP_ARG(lck_grp_t *grp))
647{
648 hw_lck_ticket_t tmp;
649
650 HW_LCK_TICKET_VERIFY(lck);
651 tmp.lck_value = hw_lck_ticket_reserve_orig(lck);
652
653 if (__probable(equal_tickets(tmp.cticket, tmp.nticket))) {
654 lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
655 return HW_LOCK_ACQUIRED;
656 }
657
658 /* Contention? branch to out of line contended block */
659 struct hw_lck_ticket_reserve_arg arg = { .mt = tmp.nticket };
660 return hw_lck_ticket_contended(lck, arg, pol LCK_GRP_ARG(grp));
661}
662
663hw_lock_status_t
664hw_lck_ticket_lock_nopreempt_to(
665 hw_lck_ticket_t *lck,
666 hw_spin_policy_t pol,
667 lck_grp_t *grp)
668{
669 return hw_lck_ticket_lock_to_internal(lck, pol LCK_GRP_ARG(grp));
670}
671
672hw_lock_status_t
673hw_lck_ticket_lock_to(
674 hw_lck_ticket_t *lck,
675 hw_spin_policy_t pol,
676 lck_grp_t *grp)
677{
678 lock_disable_preemption_for_thread(current_thread());
679 return hw_lck_ticket_lock_to_internal(lck, pol LCK_GRP_ARG(grp));
680}
681
682__header_always_inline void
683lck_ticket_lock_internal(lck_ticket_t *tlock, thread_t cthread, __unused lck_grp_t *grp)
684{
685 hw_lck_ticket_t tmp;
686
687 LCK_TICKET_VERIFY(tlock);
688 tmp.lck_value = hw_lck_ticket_reserve_orig(lck: &tlock->tu);
689
690 if (__probable(tmp.cticket == tmp.nticket)) {
691 tlock_mark_owned(tlock, cthread);
692 return lck_grp_ticket_update_held(lock: &tlock->tu LCK_GRP_ARG(grp));
693 }
694
695 /* Contention? branch to out of line contended block */
696 lck_ticket_contended(tlock, mt: tmp.nticket, cthread LCK_GRP_ARG(grp));
697}
698
699void
700lck_ticket_lock(lck_ticket_t *tlock, __unused lck_grp_t *grp)
701{
702 thread_t cthread = current_thread();
703
704 lock_disable_preemption_for_thread(cthread);
705 lck_ticket_lock_internal(tlock, cthread, grp);
706}
707
708void
709lck_ticket_lock_nopreempt(lck_ticket_t *tlock, __unused lck_grp_t *grp)
710{
711 thread_t cthread = current_thread();
712
713 lck_ticket_lock_internal(tlock, cthread, grp);
714}
715
716__header_always_inline bool
717hw_lck_ticket_lock_try_internal(
718 hw_lck_ticket_t *lck,
719 bool nopreempt
720 LCK_GRP_ARG(lck_grp_t *grp))
721{
722 hw_lck_ticket_t olck, nlck;
723
724 HW_LCK_TICKET_VERIFY(lck);
725 if (!nopreempt) {
726 lock_disable_preemption_for_thread(current_thread());
727 }
728
729 os_atomic_rmw_loop(&lck->tcurnext, olck.tcurnext, nlck.tcurnext, acquire, {
730 if (__improbable(!equal_tickets(olck.cticket, olck.nticket))) {
731 os_atomic_rmw_loop_give_up({
732 if (!nopreempt) {
733 lock_enable_preemption();
734 }
735 return false;
736 });
737 }
738 nlck.cticket = olck.cticket;
739 nlck.nticket = olck.nticket + HW_LCK_TICKET_LOCK_INCREMENT;
740 });
741
742 lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
743 return true;
744}
745
746bool
747hw_lck_ticket_lock_try(hw_lck_ticket_t *lck, lck_grp_t *grp)
748{
749 return hw_lck_ticket_lock_try_internal(lck, false LCK_GRP_ARG(grp));
750}
751
752bool
753hw_lck_ticket_lock_try_nopreempt(hw_lck_ticket_t *lck, lck_grp_t *grp)
754{
755 return hw_lck_ticket_lock_try_internal(lck, true LCK_GRP_ARG(grp));
756}
757
758__header_always_inline bool
759lck_ticket_lock_try_internal(lck_ticket_t *tlock, __unused lck_grp_t *grp, bool nopreempt)
760{
761 thread_t cthread = current_thread();
762 hw_lck_ticket_t olck, nlck;
763
764 LCK_TICKET_VERIFY(tlock);
765 if (!nopreempt) {
766 lock_disable_preemption_for_thread(cthread);
767 }
768
769 os_atomic_rmw_loop(&tlock->tu.tcurnext, olck.tcurnext, nlck.tcurnext, acquire, {
770 if (__improbable(!equal_tickets(olck.cticket, olck.nticket))) {
771 os_atomic_rmw_loop_give_up({
772 if (!nopreempt) {
773 lock_enable_preemption();
774 }
775 return false;
776 });
777 }
778 nlck.cticket = olck.cticket;
779 nlck.nticket = olck.nticket + HW_LCK_TICKET_LOCK_INCREMENT;
780 });
781
782 tlock_mark_owned(tlock, cthread);
783 lck_grp_ticket_update_held(lock: &tlock->tu LCK_GRP_ARG(grp));
784 return true;
785}
786
787bool
788lck_ticket_lock_try(lck_ticket_t *tlock, __unused lck_grp_t *grp)
789{
790 return lck_ticket_lock_try_internal(tlock, grp, false);
791}
792
793bool
794lck_ticket_lock_try_nopreempt(lck_ticket_t *tlock, __unused lck_grp_t *grp)
795{
796 return lck_ticket_lock_try_internal(tlock, grp, true);
797}
798
799/*
800 * Assembly routine that
801 * Returns a "reserved" lock or a lock where `lck_valid` is 0.
802 *
803 * More or less equivalent to this:
804 *
805 * hw_lck_ticket_t
806 * hw_lck_ticket_lock_allow_invalid(hw_lck_ticket_t *lck)
807 * {
808 * hw_lck_ticket_t o, n;
809 *
810 * os_atomic_rmw_loop(lck, o, n, acquire, {
811 * if (__improbable(!o.lck_valid)) {
812 * os_atomic_rmw_loop_give_up({
813 * return (hw_lck_ticket_t){ 0 };
814 * });
815 * }
816 * n = o;
817 * n.nticket++;
818 * });
819 * return o;
820 * }
821 */
822
823#if KASAN_TBI
824extern hw_lck_ticket_t
825hw_lck_ticket_reserve_orig_allow_invalid(hw_lck_ticket_t *lck, const uint8_t *tag_addr);
826#else /* KASAN_TBI */
827extern hw_lck_ticket_t
828hw_lck_ticket_reserve_orig_allow_invalid(hw_lck_ticket_t *lck);
829#endif /* KASAN_TBI */
830
831bool
832hw_lck_ticket_reserve_nopreempt(hw_lck_ticket_t *lck, uint32_t *ticket, lck_grp_t *grp)
833{
834 hw_lck_ticket_t tmp;
835
836 HW_LCK_TICKET_VERIFY(lck);
837 tmp.lck_value = *ticket = hw_lck_ticket_reserve_orig(lck);
838
839 if (__probable(tmp.cticket == tmp.nticket)) {
840 lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
841 return true;
842 }
843
844 return false;
845}
846
847bool
848hw_lck_ticket_reserve(hw_lck_ticket_t *lck, uint32_t *ticket, lck_grp_t *grp)
849{
850 lock_disable_preemption_for_thread(current_thread());
851
852 return hw_lck_ticket_reserve_nopreempt(lck, ticket, grp);
853}
854
855hw_lock_status_t
856hw_lck_ticket_reserve_allow_invalid(hw_lck_ticket_t *lck, uint32_t *ticket, lck_grp_t *grp)
857{
858 hw_lck_ticket_t tmp;
859
860 lock_disable_preemption_for_thread(current_thread());
861
862#if KASAN_TBI
863 /* Expand the check to also include the tag value. See machine_routines_asm.s for the details */
864 tmp = hw_lck_ticket_reserve_orig_allow_invalid(lck,
865 kasan_tbi_get_tag_address((vm_offset_t)lck));
866#else /* KASAN_TBI */
867 tmp = hw_lck_ticket_reserve_orig_allow_invalid(lck);
868#endif /* KASAN_TBI */
869 *ticket = tmp.lck_value;
870
871 if (__improbable(!tmp.lck_valid)) {
872 lock_enable_preemption();
873 return HW_LOCK_INVALID;
874 }
875
876 if (__probable(equal_tickets(tmp.cticket, tmp.nticket))) {
877 lck_grp_ticket_update_held(lock: lck LCK_GRP_ARG(grp));
878 return HW_LOCK_ACQUIRED;
879 }
880
881 return HW_LOCK_CONTENDED;
882}
883
884hw_lock_status_t
885hw_lck_ticket_wait(
886 hw_lck_ticket_t *lck,
887 uint32_t ticket,
888 hw_spin_policy_t pol,
889 lck_grp_t *grp)
890{
891 hw_lck_ticket_t tmp = { .lck_value = ticket };
892 struct hw_lck_ticket_reserve_arg arg = { .mt = tmp.nticket };
893
894 if (pol == NULL) {
895 pol = &hw_lck_ticket_spin_policy;
896 }
897 return hw_lck_ticket_contended(lck, arg, pol LCK_GRP_ARG(grp));
898}
899
900hw_lock_status_t
901hw_lck_ticket_lock_allow_invalid(
902 hw_lck_ticket_t *lck,
903 hw_spin_policy_t pol,
904 lck_grp_t *grp)
905{
906 hw_lock_status_t st;
907 hw_lck_ticket_t tmp;
908
909 st = hw_lck_ticket_reserve_allow_invalid(lck, &tmp.lck_value, grp);
910
911 if (__improbable(st == HW_LOCK_CONTENDED)) {
912 /* Contention? branch to out of line contended block */
913 struct hw_lck_ticket_reserve_arg arg = {
914 .mt = tmp.nticket,
915 .validate = true,
916 };
917 return hw_lck_ticket_contended(lck, arg, pol LCK_GRP_ARG(grp));
918 }
919
920 return st;
921}
922
923void
924hw_lck_ticket_invalidate(hw_lck_ticket_t *lck)
925{
926 hw_lck_ticket_t tmp = { .lck_valid = 1 };
927
928 os_atomic_andnot(&lck->lck_value, tmp.lck_value, relaxed);
929}
930
931void
932hw_lck_ticket_unlock_nopreempt(hw_lck_ticket_t *lck)
933{
934 HW_LCK_TICKET_VERIFY(lck);
935 hw_lck_ticket_unlock_internal_nopreempt(lck);
936}
937
938void
939hw_lck_ticket_unlock(hw_lck_ticket_t *lck)
940{
941 HW_LCK_TICKET_VERIFY(lck);
942 hw_lck_ticket_unlock_internal(lck);
943}
944
945void
946lck_ticket_unlock_nopreempt(lck_ticket_t *tlock)
947{
948 LCK_TICKET_VERIFY(tlock);
949 LCK_TICKET_UNLOCK_VERIFY(tlock);
950 os_atomic_store(&tlock->lck_ticket_owner, 0, relaxed);
951 hw_lck_ticket_unlock_internal_nopreempt(lck: &tlock->tu);
952}
953
954void
955lck_ticket_unlock(lck_ticket_t *tlock)
956{
957 LCK_TICKET_VERIFY(tlock);
958 LCK_TICKET_UNLOCK_VERIFY(tlock);
959 os_atomic_store(&tlock->lck_ticket_owner, 0, relaxed);
960 hw_lck_ticket_unlock_internal(lck: &tlock->tu);
961}
962
963void
964lck_ticket_assert_owned(const lck_ticket_t *tlock)
965{
966 if (current_thread()->ctid != tlock->lck_ticket_owner) {
967 __lck_ticket_not_owned_panic(lck: tlock);
968 }
969}
970
971void
972lck_ticket_assert_not_owned(const lck_ticket_t *tlock)
973{
974 if (current_thread()->ctid == tlock->lck_ticket_owner) {
975 __lck_ticket_owned_panic(lck: tlock);
976 }
977}
978