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 | |
104 | extern unsigned int not_in_kdp; |
105 | |
106 | MACHINE_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 | |
113 | KALLOC_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 | */ |
126 | uint32_t |
127 | load_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 | |
140 | boolean_t |
141 | store_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 | |
154 | uint32_t |
155 | atomic_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 | |
167 | boolean_t |
168 | atomic_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 | |
178 | void |
179 | atomic_exchange_abort(void) |
180 | { |
181 | os_atomic_clear_exclusive(); |
182 | } |
183 | |
184 | boolean_t |
185 | atomic_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 |
210 | void |
211 | lck_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 | } |
221 | STARTUP(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 | |
228 | lck_spin_t * |
229 | lck_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 | |
238 | void |
239 | lck_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 | |
245 | void |
246 | lck_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 | */ |
254 | MARK_AS_HIBERNATE_TEXT void inline |
255 | arm_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 | |
260 | void |
261 | lck_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 | |
272 | void |
273 | lck_spin_lock(lck_spin_t *lock) |
274 | { |
275 | lck_ticket_lock(lock, LCK_GRP_NULL); |
276 | } |
277 | |
278 | void |
279 | lck_spin_lock_nopreempt(lck_spin_t *lock) |
280 | { |
281 | lck_ticket_lock_nopreempt(lock, LCK_GRP_NULL); |
282 | } |
283 | |
284 | int |
285 | lck_spin_try_lock(lck_spin_t *lock) |
286 | { |
287 | return lck_ticket_lock_try(lock, LCK_GRP_NULL); |
288 | } |
289 | |
290 | int |
291 | lck_spin_try_lock_nopreempt(lck_spin_t *lock) |
292 | { |
293 | return lck_ticket_lock_try_nopreempt(lock, LCK_GRP_NULL); |
294 | } |
295 | |
296 | void |
297 | lck_spin_unlock(lck_spin_t *lock) |
298 | { |
299 | lck_ticket_unlock(lock); |
300 | } |
301 | |
302 | void |
303 | lck_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") |
320 | make_alias(lck_spin_lock_grp, lck_ticket_lock); |
321 | make_alias(lck_spin_lock_nopreempt_grp, lck_ticket_lock_nopreempt); |
322 | make_alias(lck_spin_try_lock_grp, lck_ticket_lock_try); |
323 | make_alias(lck_spin_try_lock_nopreempt_grp, lck_ticket_lock_try_nopreempt); |
324 | make_alias(lck_spin_unlock_nopreempt, lck_ticket_unlock_nopreempt); |
325 | make_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 |
332 | static 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 | |
346 | static inline void |
347 | lck_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 | |
358 | lck_spin_t * |
359 | lck_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 | |
368 | void |
369 | lck_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 | |
375 | void |
376 | lck_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 | */ |
388 | MARK_AS_HIBERNATE_TEXT void inline |
389 | arm_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 | |
395 | void |
396 | lck_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 | |
422 | void |
423 | lck_spin_lock(lck_spin_t *lock) |
424 | { |
425 | lck_spin_verify(lock); |
426 | hw_lock_lock(&lock->hwlock, LCK_GRP_NULL); |
427 | } |
428 | |
429 | void |
430 | lck_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 | |
437 | void |
438 | lck_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 | |
444 | void |
445 | lck_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 | |
452 | int |
453 | lck_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 | |
459 | int |
460 | lck_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 | |
467 | int |
468 | lck_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 | |
474 | int |
475 | lck_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 | |
482 | void |
483 | lck_spin_unlock(lck_spin_t *lock) |
484 | { |
485 | lck_spin_verify(lock); |
486 | hw_lock_unlock(&lock->hwlock); |
487 | } |
488 | |
489 | void |
490 | lck_spin_unlock_nopreempt(lck_spin_t *lock) |
491 | { |
492 | lck_spin_verify(lock); |
493 | hw_lock_unlock_nopreempt(&lock->hwlock); |
494 | } |
495 | |
496 | void |
497 | lck_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 | */ |
513 | boolean_t |
514 | kdp_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 | */ |
529 | void |
530 | usimple_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 | */ |
545 | void |
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 | */ |
561 | void |
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 | */ |
581 | unsigned |
582 | int |
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 | |