1/*
2 * Copyright (c) 2022 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
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56
57#include <kern/kalloc.h>
58#include <kern/thread.h>
59#include <machine/atomic.h>
60#include <kern/kern_apfs_reflock.h>
61
62KALLOC_TYPE_DEFINE(KT_KERN_APFSREFLOCK, struct kern_apfs_reflock, KT_PRIV_ACCT);
63
64static_assert(sizeof(struct kern_apfs_reflock) == sizeof(uint64_t));
65
66void
67kern_apfs_reflock_init(kern_apfs_reflock_t reflock)
68{
69 reflock->kern_apfs_rl_data.cond64_data = 0;
70}
71
72void
73kern_apfs_reflock_destroy(kern_apfs_reflock_t reflock)
74{
75 if (reflock->kern_apfs_rl_data.cond64_data == KERN_APFS_REFLOCK_DESTROYED) {
76 panic("kern_apfs_reflock_t %p was already destroyed", reflock);
77 }
78 if (reflock->kern_apfs_rl_allocated == 1) {
79 panic("kern_apfs_reflock_t %p was allocated. kern_apfs_reflock_free should be called instead of kern_apfs_reflock_destroy", reflock);
80 }
81 if (reflock->kern_apfs_rl_owner != 0) {
82 panic("kern_apfs_reflock_t %p: destroying a reflock currently locked by ctid %d", reflock, reflock->kern_apfs_rl_owner);
83 }
84 if (reflock->kern_apfs_rl_wake != 0) {
85 panic("kern_apfs_reflock_t %p: destroying a reflock with threads currently waiting or in the process of waiting", reflock);
86 }
87 assert(reflock->kern_apfs_rl_allow_force == 0);
88 assert(reflock->kern_apfs_rl_waiters == 0);
89 assert(reflock->kern_apfs_rl_delayed_free == 0);
90 reflock->kern_apfs_rl_data.cond64_data = KERN_APFS_REFLOCK_DESTROYED;
91}
92
93kern_apfs_reflock_t
94kern_apfs_reflock_alloc_init(void)
95{
96 kern_apfs_reflock_t reflock = zalloc_flags(KT_KERN_APFSREFLOCK, Z_WAITOK | Z_ZERO | Z_NOFAIL);
97 reflock->kern_apfs_rl_allocated = 1;
98 return reflock;
99}
100
101static void
102kern_apfs_reflock_free_internal(kern_apfs_reflock_t reflock)
103{
104 assert(reflock->kern_apfs_rl_waiters == 0);
105 assert(reflock->kern_apfs_rl_owner == 0);
106 assert(reflock->kern_apfs_rl_allow_force == 0);
107 assert(reflock->kern_apfs_rl_wake == 0);
108 assert(reflock->kern_apfs_rl_allocated == 1);
109 assert(reflock->kern_apfs_rl_delayed_free == 1);
110
111 zfree(KT_KERN_APFSREFLOCK, reflock);
112}
113
114static void inline
115kern_apfs_reflock_check_valid(kern_apfs_reflock_t reflock)
116{
117 if (reflock->kern_apfs_rl_data.cond64_data == KERN_APFS_REFLOCK_DESTROYED) {
118 panic("reflock %p was destoryed", reflock);
119 }
120 if (reflock->kern_apfs_rl_allocated == 1 && reflock->kern_apfs_rl_delayed_free == 1) {
121 panic("reflock %p used after request for free", reflock);
122 }
123}
124
125void
126kern_apfs_reflock_free(kern_apfs_reflock_t reflock)
127{
128 struct kern_apfs_reflock old_reflock, new_reflock;
129
130 if (reflock->kern_apfs_rl_allocated == 0) {
131 panic("kern_apfs_reflock_t %p was not allocated. kern_apfs_reflock_destroy should be called instead of kern_apfs_reflock_free", reflock);
132 }
133
134 /*
135 * This could be concurrent with kern_apfs_reflock_wait_for_unlock
136 */
137 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, release, {
138 new_reflock = old_reflock;
139
140 if (reflock->kern_apfs_rl_delayed_free == 1) {
141 panic("kern_apfs_reflock_t %p is already in the process of being freed", reflock);
142 }
143 if (reflock->kern_apfs_rl_owner != 0) {
144 panic("kern_apfs_reflock_t %p: freeing a reflock currently locked by ctid %d", reflock, reflock->kern_apfs_rl_owner);
145 }
146 assert(reflock->kern_apfs_rl_wake == 0);
147 assert(reflock->kern_apfs_rl_allow_force == 0);
148
149 new_reflock.kern_apfs_rl_delayed_free = 1;
150 });
151
152 if (new_reflock.kern_apfs_rl_waiters == 0) {
153 kern_apfs_reflock_free_internal(reflock);
154 }
155}
156
157bool
158kern_apfs_reflock_try_get_ref(struct kern_apfs_reflock *reflock, kern_apfs_reflock_in_flags_t in_flags, kern_apfs_reflock_out_flags_t *out_flags)
159{
160 struct kern_apfs_reflock old_reflock, new_reflock;
161 ctid_t my_ctid = thread_get_ctid(thread: current_thread());
162 bool acquired = false;
163 bool locked = false;
164 bool will_wait = (in_flags & KERN_APFS_REFLOCK_IN_WILL_WAIT) != 0;
165 bool force = (in_flags & KERN_APFS_REFLOCK_IN_FORCE) != 0;
166 bool try_lock = (in_flags & KERN_APFS_REFLOCK_IN_LOCK_IF_FIRST) != 0;
167
168 if (force && try_lock) {
169 panic("Cannot use KERN_APFS_REFLOCK_IN_FORCE and KERN_APFS_REFLOCK_IN_LOCK_IF_FIRST together");
170 }
171
172 kern_apfs_reflock_check_valid(reflock);
173 *out_flags = KERN_APFS_REFLOCK_OUT_DEFAULT;
174
175 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, acquire, {
176 new_reflock = old_reflock;
177 locked = false;
178 /*
179 * Check if refcount modifications are halted by
180 * a thread that is holding the lock.
181 */
182 if (old_reflock.kern_apfs_rl_owner != 0 &&
183 !(force && old_reflock.kern_apfs_rl_allow_force == 1)) {
184 acquired = false;
185 if (will_wait && reflock->kern_apfs_rl_allocated == 1) {
186 /*
187 * We need to remember how many threads
188 * will call wait_unlock so that
189 * in case a free happens the last waiter
190 * leaving the wait_unlock will free the reflock.
191 */
192 if (old_reflock.kern_apfs_rl_waiters == KERN_APFS_REFLOCK_MAXWAITERS) {
193 panic("kern_apfs_reflock: too many waiters for %p thread %p", reflock, current_thread());
194 }
195 new_reflock.kern_apfs_rl_waiters = old_reflock.kern_apfs_rl_waiters + 1;
196 } else {
197 /*
198 * Caller does not want to wait or we do not need to remember how many waiters there are.
199 */
200 os_atomic_rmw_loop_give_up(break);
201 }
202 } else {
203 acquired = true;
204 if (old_reflock.kern_apfs_rl_count == KERN_APFS_REFLOCK_MAXREFCOUNT) {
205 panic("kern_apfs_reflock: too many refs for %p thread %p", reflock, current_thread());
206 }
207 new_reflock.kern_apfs_rl_count = old_reflock.kern_apfs_rl_count + 1;
208 if (try_lock && new_reflock.kern_apfs_rl_count == 1) {
209 new_reflock.kern_apfs_rl_owner = my_ctid;
210 new_reflock.kern_apfs_rl_allow_force = 0;
211 locked = true;
212 }
213 }
214 });
215
216 if (locked) {
217 assert(acquired == true);
218 assert((in_flags & KERN_APFS_REFLOCK_IN_LOCK_IF_FIRST) != 0);
219 *out_flags |= KERN_APFS_REFLOCK_OUT_LOCKED;
220 }
221
222 return acquired;
223}
224
225bool
226kern_apfs_reflock_try_put_ref(kern_apfs_reflock_t reflock, kern_apfs_reflock_in_flags_t in_flags, kern_apfs_reflock_out_flags_t *out_flags)
227{
228 struct kern_apfs_reflock old_reflock, new_reflock;
229 ctid_t my_ctid = thread_get_ctid(thread: current_thread());
230 bool released = false;
231 bool last_release = false;
232 bool locked = false;
233 bool will_wait = (in_flags & KERN_APFS_REFLOCK_IN_WILL_WAIT) != 0;
234 bool force = (in_flags & KERN_APFS_REFLOCK_IN_FORCE) != 0;
235 bool try_lock = (in_flags & KERN_APFS_REFLOCK_IN_LOCK_IF_LAST) != 0;
236
237 if (force && try_lock) {
238 panic("Cannot use KERN_APFS_REFLOCK_IN_FORCE and KERN_APFS_REFLOCK_IN_LOCK_IF_LAST together");
239 }
240
241 kern_apfs_reflock_check_valid(reflock);
242 *out_flags = KERN_APFS_REFLOCK_OUT_DEFAULT;
243
244 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, release, {
245 if (old_reflock.kern_apfs_rl_count == 0) {
246 panic("kern_apfs_reflock: over releasing reflock %p thread %p", reflock, current_thread());
247 }
248
249 new_reflock = old_reflock;
250 locked = false;
251 last_release = false;
252
253 /*
254 * Check if refcount modifications are halted by
255 * a thread that is holding the lock.
256 */
257 if (old_reflock.kern_apfs_rl_owner != 0 &&
258 !(force && old_reflock.kern_apfs_rl_allow_force == 1)) {
259 released = false;
260 if (will_wait && reflock->kern_apfs_rl_allocated == 1) {
261 /*
262 * We need to remember how many threads
263 * will call wait_unlock so that
264 * in case a free happens the last waiters
265 * leaving the wait_unlock will free the reflock.
266 */
267 if (old_reflock.kern_apfs_rl_waiters == KERN_APFS_REFLOCK_MAXWAITERS) {
268 panic("kern_apfs_reflock: too many waiters for %p thread %p", reflock, current_thread());
269 }
270 new_reflock.kern_apfs_rl_waiters = old_reflock.kern_apfs_rl_waiters + 1;
271 } else {
272 /*
273 * Caller does not want to wait or we do not need to remember how many waiters there are.
274 */
275 os_atomic_rmw_loop_give_up(break);
276 }
277 } else {
278 released = true;
279 new_reflock.kern_apfs_rl_count = old_reflock.kern_apfs_rl_count - 1;
280 if (new_reflock.kern_apfs_rl_count == 0) {
281 last_release = true;
282 if (try_lock) {
283 new_reflock.kern_apfs_rl_owner = my_ctid;
284 new_reflock.kern_apfs_rl_allow_force = 0;
285 locked = true;
286 }
287 }
288 }
289 });
290
291 if (locked) {
292 assert(released == true);
293 assert((in_flags & KERN_APFS_REFLOCK_IN_LOCK_IF_LAST) != 0);
294 *out_flags |= KERN_APFS_REFLOCK_OUT_LOCKED;
295 }
296
297 if (locked || last_release) {
298 os_atomic_thread_fence(acquire);
299 }
300
301 return released;
302}
303
304bool
305kern_apfs_reflock_try_lock(kern_apfs_reflock_t reflock, kern_apfs_reflock_in_flags_t in_flags, uint32_t *refcount_when_lock)
306{
307 struct kern_apfs_reflock old_reflock, new_reflock;
308 ctid_t my_ctid = thread_get_ctid(thread: current_thread());
309 bool acquired = false;
310 bool allow_force = (in_flags & KERN_APFS_REFLOCK_IN_ALLOW_FORCE) != 0;
311 bool will_wait = (in_flags & KERN_APFS_REFLOCK_IN_WILL_WAIT) != 0;
312 uint32_t refcount = 0;
313
314 kern_apfs_reflock_check_valid(reflock);
315
316 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, acquire, {
317 new_reflock = old_reflock;
318 /*
319 * Check if a thread is already holding the lock.
320 */
321 if (old_reflock.kern_apfs_rl_owner != 0) {
322 if (old_reflock.kern_apfs_rl_owner == my_ctid) {
323 panic("Trying to lock a reflock owned by the same thread %p, reflock %p", current_thread(), reflock);
324 }
325 acquired = false;
326 if (will_wait && reflock->kern_apfs_rl_allocated == 1) {
327 /*
328 * We need to remember how many threads
329 * will call wait_unlock so that
330 * in case a free happens the last waiter
331 * leaving the wait_unlock will free the reflock.
332 */
333 if (old_reflock.kern_apfs_rl_waiters == KERN_APFS_REFLOCK_MAXWAITERS) {
334 panic("kern_apfs_reflock: too many waiters for %p thread %p", reflock, current_thread());
335 }
336 new_reflock.kern_apfs_rl_waiters = old_reflock.kern_apfs_rl_waiters + 1;
337 } else {
338 /*
339 * Caller does not want to wait or we do not need to remember how many waiters there are.
340 */
341 os_atomic_rmw_loop_give_up(break);
342 }
343 } else {
344 acquired = true;
345 refcount = old_reflock.kern_apfs_rl_count;
346 new_reflock.kern_apfs_rl_owner = my_ctid;
347 if (allow_force) {
348 new_reflock.kern_apfs_rl_allow_force = 1;
349 } else {
350 new_reflock.kern_apfs_rl_allow_force = 0;
351 }
352 }
353 });
354
355 if (acquired && refcount_when_lock != NULL) {
356 *refcount_when_lock = refcount;
357 }
358
359 return acquired;
360}
361
362wait_result_t
363kern_apfs_reflock_wait_for_unlock(kern_apfs_reflock_t reflock, wait_interrupt_t interruptible, uint64_t deadline)
364{
365 struct kern_apfs_reflock old_reflock, new_reflock;
366 ctid_t my_ctid = thread_get_ctid(thread: current_thread());
367 wait_result_t ret;
368 bool wait = false;
369 bool free = false;
370
371 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, relaxed, {
372 new_reflock = old_reflock;
373 free = false;
374
375 /*
376 * Be sure that kern_apfs_rl_waiters were incremented
377 * before waiting.
378 */
379 if (old_reflock.kern_apfs_rl_allocated == 1 && old_reflock.kern_apfs_rl_waiters == 0) {
380 panic("kern_apfs_reflock: kern_apfs_rl_waiters are 0 when trying to wait reflock %p thread %p. Probably a try* function with a positive will_wait wasn't called before waiting.", reflock, current_thread());
381 }
382
383 /*
384 * Check if a thread is still holding the lock.
385 */
386 if (old_reflock.kern_apfs_rl_owner != 0) {
387 if (old_reflock.kern_apfs_rl_owner == my_ctid) {
388 panic("Trying to wait on a reflock owned by the same thread %p, reflock %p", current_thread(), reflock);
389 }
390 /*
391 * Somebody is holding the lock.
392 * Notify we have seen this, and we
393 * are intentioned to wait.
394 */
395 new_reflock.kern_apfs_rl_wake = 1;
396 wait = true;
397 } else {
398 /*
399 * Lock not held, do not wait.
400 */
401 wait = false;
402 if (old_reflock.kern_apfs_rl_allocated == 1) {
403 new_reflock.kern_apfs_rl_waiters = old_reflock.kern_apfs_rl_waiters - 1;
404 if (old_reflock.kern_apfs_rl_delayed_free == 1 && new_reflock.kern_apfs_rl_waiters == 0) {
405 free = true;
406 }
407 } else {
408 os_atomic_rmw_loop_give_up(break);
409 }
410 }
411 });
412
413 if (free) {
414 assert(wait == false);
415 kern_apfs_reflock_free_internal(reflock);
416 return KERN_NOT_WAITING;
417 }
418
419 if (!wait) {
420 return KERN_NOT_WAITING;
421 }
422
423 /*
424 * We want to sleep only if we see an owner still set and if the wakeup flag is set.
425 * If the owner observed is different from the one saved we want to not sleep.
426 */
427 ret = cond_sleep_with_inheritor64_mask(cond: (cond_swi_var_t) reflock, expected_cond: new_reflock.kern_apfs_rl_data, KERN_APFS_SLEEP_DEBOUNCE_MASK, interruptible, deadline);
428
429 /*
430 * In case reflock was allocated we need to remove
431 * ourselves from the waiters
432 */
433 if (new_reflock.kern_apfs_rl_allocated == 1) {
434 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, acquire, {
435 new_reflock = old_reflock;
436 assert(old_reflock.kern_apfs_rl_waiters > 0);
437 new_reflock.kern_apfs_rl_waiters = old_reflock.kern_apfs_rl_waiters - 1;
438 });
439 }
440
441 if (new_reflock.kern_apfs_rl_delayed_free == 1 && new_reflock.kern_apfs_rl_waiters == 0) {
442 kern_apfs_reflock_free_internal(reflock);
443 }
444
445 return ret;
446}
447
448void
449kern_apfs_reflock_unlock(kern_apfs_reflock_t reflock)
450{
451 struct kern_apfs_reflock old_reflock, new_reflock;
452 ctid_t my_ctid = thread_get_ctid(thread: current_thread());
453 bool waiters = false;
454
455 kern_apfs_reflock_check_valid(reflock);
456
457 os_atomic_rmw_loop(&reflock->kern_apfs_rl_data.cond64_data, old_reflock.kern_apfs_rl_data.cond64_data, new_reflock.kern_apfs_rl_data.cond64_data, release, {
458 if (old_reflock.kern_apfs_rl_owner != my_ctid) {
459 panic("Unlocking swiref_t %p from thread ctid %u owned by ctid %u", reflock, my_ctid, old_reflock.kern_apfs_rl_owner);
460 }
461
462 new_reflock = old_reflock;
463 /* Check if anybody is waiting for the unlock */
464 if (old_reflock.kern_apfs_rl_wake == 1) {
465 waiters = true;
466 new_reflock.kern_apfs_rl_wake = 0;
467 } else {
468 waiters = false;
469 }
470 new_reflock.kern_apfs_rl_owner = 0;
471 new_reflock.kern_apfs_rl_allow_force = 0;
472 });
473
474 if (waiters) {
475 cond_wakeup_all_with_inheritor(cond: (cond_swi_var_t) reflock, THREAD_AWAKENED);
476 }
477}
478
479uint64_t
480kern_apfs_reflock_read_ref(kern_apfs_reflock_t reflock)
481{
482 struct kern_apfs_reflock reflock_value;
483
484 kern_apfs_reflock_check_valid(reflock);
485
486 reflock_value.kern_apfs_rl_data.cond64_data = os_atomic_load(&reflock->kern_apfs_rl_data.cond64_data, relaxed);
487
488 return reflock_value.kern_apfs_rl_count;
489}
490