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> |
59 | extern uint64_t LockTimeOutTSC; |
60 | #define TICKET_LOCK_PANIC_TIMEOUT LockTimeOutTSC |
61 | #endif /* defined(__x86_64__) */ |
62 | |
63 | #if defined(__arm64__) |
64 | extern 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 |
80 | uint32_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 | */ |
97 | static_assert(MAX_CPUS < (256 / HW_LCK_TICKET_LOCK_INCREMENT)); |
98 | static_assert(sizeof(hw_lck_ticket_t) == 4); |
99 | static_assert(offsetof(hw_lck_ticket_t, tcurnext) == 2); |
100 | static_assert(offsetof(hw_lck_ticket_t, cticket) == 2); |
101 | static_assert(offsetof(hw_lck_ticket_t, nticket) == 3); |
102 | static_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 */ |
105 | static_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 |
110 | equal_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 |
116 | ticket_count(uint8_t t) |
117 | { |
118 | return t & ~HW_LCK_TICKET_LOCK_PVWAITFLAG; |
119 | } |
120 | |
121 | __abortlike |
122 | static 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 |
129 | static 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 |
138 | static 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 |
147 | static 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 | |
155 | static inline void |
156 | hw_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 | |
163 | static inline void |
164 | lck_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 | |
185 | MARK_AS_HIBERNATE_TEXT void |
186 | hw_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 | |
204 | void |
205 | hw_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 | |
227 | MARK_AS_HIBERNATE_TEXT void |
228 | lck_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 | |
248 | static inline void |
249 | hw_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 | |
285 | void |
286 | hw_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 | |
292 | void |
293 | lck_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 | |
301 | bool |
302 | hw_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 | |
309 | bool |
310 | kdp_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 | |
318 | static inline void |
319 | tlock_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 |
335 | static hw_spin_timeout_status_t |
336 | hw_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 |
363 | static hw_spin_timeout_status_t |
364 | lck_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 | |
389 | static 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 | |
395 | static 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 |
406 | SCALABLE_COUNTER_DEFINE(ticket_wflag_cleared); |
407 | SCALABLE_COUNTER_DEFINE(ticket_wflag_still); |
408 | SCALABLE_COUNTER_DEFINE(ticket_just_unlock); |
409 | SCALABLE_COUNTER_DEFINE(ticket_kick_count); |
410 | SCALABLE_COUNTER_DEFINE(ticket_wait_count); |
411 | SCALABLE_COUNTER_DEFINE(ticket_already_count); |
412 | SCALABLE_COUNTER_DEFINE(ticket_spin_count); |
413 | #endif |
414 | |
415 | static inline void |
416 | hw_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 |
429 | hw_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 |
444 | hw_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 |
461 | hw_lck_ticket_unlock_internal(hw_lck_ticket_t *lck) |
462 | { |
463 | hw_lck_ticket_unlock_internal_nopreempt(lck); |
464 | lock_enable_preemption(); |
465 | } |
466 | |
467 | struct 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 |
477 | static hw_lock_status_t __attribute__((noinline)) |
478 | hw_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 | |
581 | static void __attribute__((noinline)) |
582 | lck_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 | |
597 | static inline uint32_t |
598 | hw_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 |
610 | hw_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 | |
629 | void |
630 | hw_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 | |
635 | void |
636 | hw_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 |
643 | hw_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 | |
663 | hw_lock_status_t |
664 | hw_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 | |
672 | hw_lock_status_t |
673 | hw_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 |
683 | lck_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 | |
699 | void |
700 | lck_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 | |
708 | void |
709 | lck_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 |
717 | hw_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 | |
746 | bool |
747 | hw_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 | |
752 | bool |
753 | hw_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 |
759 | lck_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 | |
787 | bool |
788 | lck_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 | |
793 | bool |
794 | lck_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 |
824 | extern hw_lck_ticket_t |
825 | hw_lck_ticket_reserve_orig_allow_invalid(hw_lck_ticket_t *lck, const uint8_t *tag_addr); |
826 | #else /* KASAN_TBI */ |
827 | extern hw_lck_ticket_t |
828 | hw_lck_ticket_reserve_orig_allow_invalid(hw_lck_ticket_t *lck); |
829 | #endif /* KASAN_TBI */ |
830 | |
831 | bool |
832 | hw_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 | |
847 | bool |
848 | hw_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 | |
855 | hw_lock_status_t |
856 | hw_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 | |
884 | hw_lock_status_t |
885 | hw_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 | |
900 | hw_lock_status_t |
901 | hw_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 | |
923 | void |
924 | hw_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 | |
931 | void |
932 | hw_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 | |
938 | void |
939 | hw_lck_ticket_unlock(hw_lck_ticket_t *lck) |
940 | { |
941 | HW_LCK_TICKET_VERIFY(lck); |
942 | hw_lck_ticket_unlock_internal(lck); |
943 | } |
944 | |
945 | void |
946 | lck_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 | |
954 | void |
955 | lck_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 | |
963 | void |
964 | lck_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 | |
971 | void |
972 | lck_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 | |