1/*
2 * Copyright (c) 2007-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 * @OSF_COPYRIGHT@
30 */
31/*
32 * Mach Operating System Copyright (c) 1991,1990,1989,1988,1987 Carnegie
33 * Mellon University All Rights Reserved.
34 *
35 * Permission to use, copy, modify and distribute this software and its
36 * documentation is hereby granted, provided that both the copyright notice
37 * and this permission notice appear in all copies of the software,
38 * derivative works or modified versions, and any portions thereof, and that
39 * both notices appear in supporting documentation.
40 *
41 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.
42 * CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
43 * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
44 *
45 * Carnegie Mellon requests users of this software to return to
46 *
47 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
48 * School of Computer Science Carnegie Mellon University Pittsburgh PA
49 * 15213-3890
50 *
51 * any improvements or extensions that they make and grant Carnegie Mellon the
52 * rights to redistribute these changes.
53 */
54/*
55 * File: kern/lock.c
56 * Author: Avadis Tevanian, Jr., Michael Wayne Young
57 * Date: 1985
58 *
59 * Locking primitives implementation
60 */
61
62#define LOCK_PRIVATE 1
63
64#include <mach_ldebug.h>
65
66#include <mach/machine/sdt.h>
67
68#include <kern/locks_internal.h>
69#include <kern/zalloc.h>
70#include <kern/lock_stat.h>
71#include <kern/locks.h>
72#include <kern/misc_protos.h>
73#include <kern/thread.h>
74#include <kern/processor.h>
75#include <kern/sched_hygiene.h>
76#include <kern/sched_prim.h>
77#include <kern/debug.h>
78#include <kern/kcdata.h>
79#include <kern/percpu.h>
80#include <kern/hvg_hypercall.h>
81#include <string.h>
82#include <arm/cpu_internal.h>
83#include <os/hash.h>
84#include <arm/cpu_data.h>
85
86#include <arm/cpu_data_internal.h>
87#include <arm64/proc_reg.h>
88#include <arm/smp.h>
89#include <machine/atomic.h>
90#include <machine/machine_cpu.h>
91
92#include <pexpert/pexpert.h>
93
94#include <sys/kdebug.h>
95
96#define ANY_LOCK_DEBUG (USLOCK_DEBUG || LOCK_DEBUG || MUTEX_DEBUG)
97
98// Panic in tests that check lock usage correctness
99// These are undesirable when in a panic or a debugger is runnning.
100#define LOCK_CORRECTNESS_PANIC() (kernel_debugger_entry_count == 0)
101
102/* Forwards */
103
104extern unsigned int not_in_kdp;
105
106MACHINE_TIMEOUT(lock_panic_timeout, "lock-panic",
107 0xc00000 /* 12.5 m ticks ~= 524ms with 24MHz OSC */, MACHINE_TIMEOUT_UNIT_TIMEBASE, NULL);
108
109#define NOINLINE __attribute__((noinline))
110
111#define interrupts_disabled(mask) (mask & DAIF_IRQF)
112
113KALLOC_TYPE_DEFINE(KT_LCK_SPIN, lck_spin_t, KT_PRIV_ACCT);
114
115#pragma GCC visibility push(hidden)
116/*
117 * atomic exchange API is a low level abstraction of the operations
118 * to atomically read, modify, and write a pointer. This abstraction works
119 * for both Intel and ARMv8.1 compare and exchange atomic instructions as
120 * well as the ARM exclusive instructions.
121 *
122 * atomic_exchange_begin() - begin exchange and retrieve current value
123 * atomic_exchange_complete() - conclude an exchange
124 * atomic_exchange_abort() - cancel an exchange started with atomic_exchange_begin()
125 */
126uint32_t
127load_exclusive32(uint32_t *target, enum memory_order ord)
128{
129 uint32_t value;
130
131 if (_os_atomic_mo_has_acquire(ord)) {
132 value = __builtin_arm_ldaex(target); // ldaxr
133 } else {
134 value = __builtin_arm_ldrex(target); // ldxr
135 }
136
137 return value;
138}
139
140boolean_t
141store_exclusive32(uint32_t *target, uint32_t value, enum memory_order ord)
142{
143 boolean_t err;
144
145 if (_os_atomic_mo_has_release(ord)) {
146 err = __builtin_arm_stlex(value, target); // stlxr
147 } else {
148 err = __builtin_arm_strex(value, target); // stxr
149 }
150
151 return !err;
152}
153
154uint32_t
155atomic_exchange_begin32(uint32_t *target, uint32_t *previous, enum memory_order ord)
156{
157 uint32_t val;
158
159#if !OS_ATOMIC_USE_LLSC
160 ord = memory_order_relaxed;
161#endif
162 val = load_exclusive32(target, ord);
163 *previous = val;
164 return val;
165}
166
167boolean_t
168atomic_exchange_complete32(uint32_t *target, uint32_t previous, uint32_t newval, enum memory_order ord)
169{
170#if !OS_ATOMIC_USE_LLSC
171 return __c11_atomic_compare_exchange_strong((_Atomic uint32_t *)target, &previous, newval, ord, memory_order_relaxed);
172#else
173 (void)previous; // Previous not needed, monitor is held
174 return store_exclusive32(target, value: newval, ord);
175#endif
176}
177
178void
179atomic_exchange_abort(void)
180{
181 os_atomic_clear_exclusive();
182}
183
184boolean_t
185atomic_test_and_set32(uint32_t *target, uint32_t test_mask, uint32_t set_mask, enum memory_order ord, boolean_t wait)
186{
187 uint32_t value, prev;
188
189 for (;;) {
190 value = atomic_exchange_begin32(target, previous: &prev, ord);
191 if (value & test_mask) {
192 if (wait) {
193 wait_for_event(); // Wait with monitor held
194 } else {
195 atomic_exchange_abort(); // Clear exclusive monitor
196 }
197 return FALSE;
198 }
199 value |= set_mask;
200 if (atomic_exchange_complete32(target, previous: prev, newval: value, ord)) {
201 return TRUE;
202 }
203 }
204}
205
206#pragma GCC visibility pop
207
208#if CONFIG_PV_TICKET
209__startup_func
210void
211lck_init_pv(void)
212{
213 uint32_t pvtck = 1;
214 PE_parse_boot_argn(arg_string: "pvticket", arg_ptr: &pvtck, max_arg: sizeof(pvtck));
215 if (pvtck == 0) {
216 return;
217 }
218 has_lock_pv = hvg_is_hcall_available(HVG_HCALL_VCPU_WFK) &&
219 hvg_is_hcall_available(HVG_HCALL_VCPU_KICK);
220}
221STARTUP(LOCKS, STARTUP_RANK_FIRST, lck_init_pv);
222#endif
223
224
225#pragma mark lck_spin_t
226#if LCK_SPIN_IS_TICKET_LOCK
227
228lck_spin_t *
229lck_spin_alloc_init(lck_grp_t *grp, lck_attr_t *attr)
230{
231 lck_spin_t *lck;
232
233 lck = zalloc(KT_LCK_SPIN);
234 lck_spin_init(lck, grp, attr);
235 return lck;
236}
237
238void
239lck_spin_free(lck_spin_t *lck, lck_grp_t *grp)
240{
241 lck_spin_destroy(lck, grp);
242 zfree(KT_LCK_SPIN, lck);
243}
244
245void
246lck_spin_init(lck_spin_t *lck, lck_grp_t *grp, __unused lck_attr_t *attr)
247{
248 lck_ticket_init(lck, grp);
249}
250
251/*
252 * arm_usimple_lock is a lck_spin_t without a group or attributes
253 */
254MARK_AS_HIBERNATE_TEXT void inline
255arm_usimple_lock_init(simple_lock_t lck, __unused unsigned short initial_value)
256{
257 lck_ticket_init((lck_ticket_t *)lck, LCK_GRP_NULL);
258}
259
260void
261lck_spin_assert(const lck_spin_t *lock, unsigned int type)
262{
263 if (type == LCK_ASSERT_OWNED) {
264 lck_ticket_assert_owned(lock);
265 } else if (type == LCK_ASSERT_NOTOWNED) {
266 lck_ticket_assert_not_owned(lock);
267 } else {
268 panic("lck_spin_assert(): invalid arg (%u)", type);
269 }
270}
271
272void
273lck_spin_lock(lck_spin_t *lock)
274{
275 lck_ticket_lock(lock, LCK_GRP_NULL);
276}
277
278void
279lck_spin_lock_nopreempt(lck_spin_t *lock)
280{
281 lck_ticket_lock_nopreempt(lock, LCK_GRP_NULL);
282}
283
284int
285lck_spin_try_lock(lck_spin_t *lock)
286{
287 return lck_ticket_lock_try(lock, LCK_GRP_NULL);
288}
289
290int
291lck_spin_try_lock_nopreempt(lck_spin_t *lock)
292{
293 return lck_ticket_lock_try_nopreempt(lock, LCK_GRP_NULL);
294}
295
296void
297lck_spin_unlock(lck_spin_t *lock)
298{
299 lck_ticket_unlock(lock);
300}
301
302void
303lck_spin_destroy(lck_spin_t *lck, lck_grp_t *grp)
304{
305 lck_ticket_destroy(lck, grp);
306}
307
308/*
309 * those really should be in an alias file instead,
310 * but you can't make that conditional.
311 *
312 * it will be good enough for perf evals for now
313 *
314 * we also can't make aliases for symbols that
315 * are in alias files like lck_spin_init and friends,
316 * so this suffers double jump penalties for kexts
317 * (LTO does the right thing for XNU).
318 */
319#define make_alias(a, b) asm(".globl _" #a "\n" ".set _" #a ", _" #b "\n")
320make_alias(lck_spin_lock_grp, lck_ticket_lock);
321make_alias(lck_spin_lock_nopreempt_grp, lck_ticket_lock_nopreempt);
322make_alias(lck_spin_try_lock_grp, lck_ticket_lock_try);
323make_alias(lck_spin_try_lock_nopreempt_grp, lck_ticket_lock_try_nopreempt);
324make_alias(lck_spin_unlock_nopreempt, lck_ticket_unlock_nopreempt);
325make_alias(kdp_lck_spin_is_acquired, kdp_lck_ticket_is_acquired);
326#undef make_alias
327
328#else /* !LCK_SPIN_IS_TICKET_LOCK */
329
330#if DEVELOPMENT || DEBUG
331__abortlike
332static void
333__lck_spin_invalid_panic(lck_spin_t *lck)
334{
335 const char *how = "Invalid";
336
337 if (lck->type == LCK_SPIN_TYPE_DESTROYED ||
338 lck->lck_spin_data == LCK_SPIN_TAG_DESTROYED) {
339 how = "Destroyed";
340 }
341
342 panic("%s spinlock %p: <0x%016lx 0x%16lx>",
343 how, lck, lck->lck_spin_data, lck->type);
344}
345
346static inline void
347lck_spin_verify(lck_spin_t *lck)
348{
349 if (lck->type != LCK_SPIN_TYPE ||
350 lck->lck_spin_data == LCK_SPIN_TAG_DESTROYED) {
351 __lck_spin_invalid_panic(lck);
352 }
353}
354#else /* DEVELOPMENT || DEBUG */
355#define lck_spin_verify(lck) ((void)0)
356#endif /* DEVELOPMENT || DEBUG */
357
358lck_spin_t *
359lck_spin_alloc_init(lck_grp_t *grp, lck_attr_t *attr)
360{
361 lck_spin_t *lck;
362
363 lck = zalloc(kt_view: KT_LCK_SPIN);
364 lck_spin_init(lck, grp, attr);
365 return lck;
366}
367
368void
369lck_spin_free(lck_spin_t *lck, lck_grp_t *grp)
370{
371 lck_spin_destroy(lck, grp);
372 zfree(KT_LCK_SPIN, lck);
373}
374
375void
376lck_spin_init(lck_spin_t *lck, lck_grp_t *grp, __unused lck_attr_t *attr)
377{
378 lck->type = LCK_SPIN_TYPE;
379 hw_lock_init(&lck->hwlock);
380 if (grp) {
381 lck_grp_reference(grp, cnt: &grp->lck_grp_spincnt);
382 }
383}
384
385/*
386 * arm_usimple_lock is a lck_spin_t without a group or attributes
387 */
388MARK_AS_HIBERNATE_TEXT void inline
389arm_usimple_lock_init(simple_lock_t lck, __unused unsigned short initial_value)
390{
391 lck->type = LCK_SPIN_TYPE;
392 hw_lock_init(&lck->hwlock);
393}
394
395void
396lck_spin_assert(const lck_spin_t *lock, unsigned int type)
397{
398 thread_t thread, holder;
399
400 if (lock->type != LCK_SPIN_TYPE) {
401 panic("Invalid spinlock %p", lock);
402 }
403
404 holder = HW_LOCK_STATE_TO_THREAD(lock->lck_spin_data);
405 thread = current_thread();
406 if (type == LCK_ASSERT_OWNED) {
407 if (holder == 0) {
408 panic("Lock not owned %p = %p", lock, holder);
409 }
410 if (holder != thread) {
411 panic("Lock not owned by current thread %p = %p", lock, holder);
412 }
413 } else if (type == LCK_ASSERT_NOTOWNED) {
414 if (holder != THREAD_NULL && holder == thread) {
415 panic("Lock owned by current thread %p = %p", lock, holder);
416 }
417 } else {
418 panic("lck_spin_assert(): invalid arg (%u)", type);
419 }
420}
421
422void
423lck_spin_lock(lck_spin_t *lock)
424{
425 lck_spin_verify(lock);
426 hw_lock_lock(&lock->hwlock, LCK_GRP_NULL);
427}
428
429void
430lck_spin_lock_grp(lck_spin_t *lock, lck_grp_t *grp)
431{
432#pragma unused(grp)
433 lck_spin_verify(lock);
434 hw_lock_lock(&lock->hwlock, grp);
435}
436
437void
438lck_spin_lock_nopreempt(lck_spin_t *lock)
439{
440 lck_spin_verify(lock);
441 hw_lock_lock_nopreempt(&lock->hwlock, LCK_GRP_NULL);
442}
443
444void
445lck_spin_lock_nopreempt_grp(lck_spin_t *lock, lck_grp_t *grp)
446{
447#pragma unused(grp)
448 lck_spin_verify(lock);
449 hw_lock_lock_nopreempt(&lock->hwlock, grp);
450}
451
452int
453lck_spin_try_lock(lck_spin_t *lock)
454{
455 lck_spin_verify(lock);
456 return hw_lock_try(&lock->hwlock, LCK_GRP_NULL);
457}
458
459int
460lck_spin_try_lock_grp(lck_spin_t *lock, lck_grp_t *grp)
461{
462#pragma unused(grp)
463 lck_spin_verify(lock);
464 return hw_lock_try(&lock->hwlock, grp);
465}
466
467int
468lck_spin_try_lock_nopreempt(lck_spin_t *lock)
469{
470 lck_spin_verify(lock);
471 return hw_lock_try_nopreempt(&lock->hwlock, LCK_GRP_NULL);
472}
473
474int
475lck_spin_try_lock_nopreempt_grp(lck_spin_t *lock, lck_grp_t *grp)
476{
477#pragma unused(grp)
478 lck_spin_verify(lock);
479 return hw_lock_try_nopreempt(&lock->hwlock, grp);
480}
481
482void
483lck_spin_unlock(lck_spin_t *lock)
484{
485 lck_spin_verify(lock);
486 hw_lock_unlock(&lock->hwlock);
487}
488
489void
490lck_spin_unlock_nopreempt(lck_spin_t *lock)
491{
492 lck_spin_verify(lock);
493 hw_lock_unlock_nopreempt(&lock->hwlock);
494}
495
496void
497lck_spin_destroy(lck_spin_t *lck, lck_grp_t *grp)
498{
499 lck_spin_verify(lck);
500 *lck = (lck_spin_t){
501 .lck_spin_data = LCK_SPIN_TAG_DESTROYED,
502 .type = LCK_SPIN_TYPE_DESTROYED,
503 };
504 if (grp) {
505 lck_grp_deallocate(grp, cnt: &grp->lck_grp_spincnt);
506 }
507}
508
509/*
510 * Routine: kdp_lck_spin_is_acquired
511 * NOT SAFE: To be used only by kernel debugger to avoid deadlock.
512 */
513boolean_t
514kdp_lck_spin_is_acquired(lck_spin_t *lck)
515{
516 if (not_in_kdp) {
517 panic("panic: spinlock acquired check done outside of kernel debugger");
518 }
519 return ((lck->lck_spin_data & ~LCK_SPIN_TAG_DESTROYED) != 0) ? TRUE:FALSE;
520}
521
522#endif /* !LCK_SPIN_IS_TICKET_LOCK */
523
524/*
525 * Initialize a usimple_lock.
526 *
527 * No change in preemption state.
528 */
529void
530usimple_lock_init(
531 usimple_lock_t l,
532 unsigned short tag)
533{
534 simple_lock_init((simple_lock_t) l, tag);
535}
536
537
538/*
539 * Acquire a usimple_lock.
540 *
541 * Returns with preemption disabled. Note
542 * that the hw_lock routines are responsible for
543 * maintaining preemption state.
544 */
545void
546(usimple_lock)(
547 usimple_lock_t l
548 LCK_GRP_ARG(lck_grp_t *grp))
549{
550 simple_lock((simple_lock_t) l, LCK_GRP_PROBEARG(grp));
551}
552
553
554/*
555 * Release a usimple_lock.
556 *
557 * Returns with preemption enabled. Note
558 * that the hw_lock routines are responsible for
559 * maintaining preemption state.
560 */
561void
562(usimple_unlock)(
563 usimple_lock_t l)
564{
565 simple_unlock((simple_lock_t)l);
566}
567
568
569/*
570 * Conditionally acquire a usimple_lock.
571 *
572 * On success, returns with preemption disabled.
573 * On failure, returns with preemption in the same state
574 * as when first invoked. Note that the hw_lock routines
575 * are responsible for maintaining preemption state.
576 *
577 * XXX No stats are gathered on a miss; I preserved this
578 * behavior from the original assembly-language code, but
579 * doesn't it make sense to log misses? XXX
580 */
581unsigned
582int
583(usimple_lock_try)(
584 usimple_lock_t l
585 LCK_GRP_ARG(lck_grp_t *grp))
586{
587 return simple_lock_try((simple_lock_t) l, grp);
588}
589