projects/linux·blob master · refs

1371 lines · 37.7 KiB

1// SPDX-License-Identifier: GPL-2.0-or-later
2
3#include <linux/slab.h>
4#include <linux/sched/rt.h>
5#include <linux/sched/task.h>
6
7#include "futex.h"
8#include "../locking/rtmutex_common.h"
9
10/*
11 * PI code:
12 */
13int refill_pi_state_cache(void)
14{
15 struct futex_pi_state *pi_state;
16
17 if (likely(current->futex.pi_state_cache))
18 return 0;
19
20 pi_state = kzalloc_obj(*pi_state);
21
22 if (!pi_state)
23 return -ENOMEM;
24
25 INIT_LIST_HEAD(&pi_state->list);
26 /* pi_mutex gets initialized later */
27 pi_state->owner = NULL;
28 refcount_set(&pi_state->refcount, 1);
29 pi_state->key = FUTEX_KEY_INIT;
30
31 current->futex.pi_state_cache = pi_state;
32
33 return 0;
34}
35
36static struct futex_pi_state *alloc_pi_state(void)
37{
38 struct futex_pi_state *pi_state = current->futex.pi_state_cache;
39
40 WARN_ON(!pi_state);
41 current->futex.pi_state_cache = NULL;
42
43 return pi_state;
44}
45
46static void pi_state_update_owner(struct futex_pi_state *pi_state,
47 struct task_struct *new_owner)
48{
49 struct task_struct *old_owner = pi_state->owner;
50
51 lockdep_assert_held(&pi_state->pi_mutex.wait_lock);
52
53 if (old_owner) {
54 raw_spin_lock(&old_owner->pi_lock);
55 WARN_ON(list_empty(&pi_state->list));
56 list_del_init(&pi_state->list);
57 raw_spin_unlock(&old_owner->pi_lock);
58 }
59
60 if (new_owner) {
61 raw_spin_lock(&new_owner->pi_lock);
62 WARN_ON(!list_empty(&pi_state->list));
63 list_add(&pi_state->list, &new_owner->futex.pi_state_list);
64 pi_state->owner = new_owner;
65 raw_spin_unlock(&new_owner->pi_lock);
66 }
67}
68
69void get_pi_state(struct futex_pi_state *pi_state)
70{
71 WARN_ON_ONCE(!refcount_inc_not_zero(&pi_state->refcount));
72}
73
74/*
75 * Drops a reference to the pi_state object and frees or caches it
76 * when the last reference is gone.
77 */
78void put_pi_state(struct futex_pi_state *pi_state)
79{
80 if (!pi_state)
81 return;
82
83 if (!refcount_dec_and_test(&pi_state->refcount))
84 return;
85
86 /*
87 * If pi_state->owner is NULL, the owner is most probably dying
88 * and has cleaned up the pi_state already
89 */
90 if (pi_state->owner) {
91 unsigned long flags;
92
93 raw_spin_lock_irqsave(&pi_state->pi_mutex.wait_lock, flags);
94 pi_state_update_owner(pi_state, NULL);
95 rt_mutex_proxy_unlock(&pi_state->pi_mutex);
96 raw_spin_unlock_irqrestore(&pi_state->pi_mutex.wait_lock, flags);
97 }
98
99 if (current->futex.pi_state_cache) {
100 kfree(pi_state);
101 } else {
102 /*
103 * pi_state->list is already empty.
104 * clear pi_state->owner.
105 * refcount is at 0 - put it back to 1.
106 */
107 pi_state->owner = NULL;
108 refcount_set(&pi_state->refcount, 1);
109 current->futex.pi_state_cache = pi_state;
110 }
111}
112
113/*
114 * We need to check the following states:
115 *
116 * Waiter | pi_state | pi->owner | uTID | uODIED | ?
117 *
118 * [1] NULL | --- | --- | 0 | 0/1 | Valid
119 * [2] NULL | --- | --- | >0 | 0/1 | Valid
120 *
121 * [3] Found | NULL | -- | Any | 0/1 | Invalid
122 *
123 * [4] Found | Found | NULL | 0 | 1 | Valid
124 * [5] Found | Found | NULL | >0 | 1 | Invalid
125 *
126 * [6] Found | Found | task | 0 | 1 | Valid
127 *
128 * [7] Found | Found | NULL | Any | 0 | Invalid
129 *
130 * [8] Found | Found | task | ==taskTID | 0/1 | Valid
131 * [9] Found | Found | task | 0 | 0 | Invalid
132 * [10] Found | Found | task | !=taskTID | 0/1 | Invalid
133 *
134 * [1] Indicates that the kernel can acquire the futex atomically. We
135 * came here due to a stale FUTEX_WAITERS/FUTEX_OWNER_DIED bit.
136 *
137 * [2] Valid, if TID does not belong to a kernel thread. If no matching
138 * thread is found then it indicates that the owner TID has died.
139 *
140 * [3] Invalid. The waiter is queued on a non PI futex
141 *
142 * [4] Valid state after exit_robust_list(), which sets the user space
143 * value to FUTEX_WAITERS | FUTEX_OWNER_DIED.
144 *
145 * [5] The user space value got manipulated between exit_robust_list()
146 * and exit_pi_state_list()
147 *
148 * [6] Valid state after exit_pi_state_list() which sets the new owner in
149 * the pi_state but cannot access the user space value.
150 *
151 * [7] pi_state->owner can only be NULL when the OWNER_DIED bit is set.
152 *
153 * [8] Owner and user space value match
154 *
155 * [9] There is no transient state which sets the user space TID to 0
156 * except exit_robust_list(), but this is indicated by the
157 * FUTEX_OWNER_DIED bit. See [4]
158 *
159 * [10] There is no transient state which leaves owner and user space
160 * TID out of sync. Except one error case where the kernel is denied
161 * write access to the user address, see fixup_pi_state_owner().
162 *
163 *
164 * Serialization and lifetime rules:
165 *
166 * hb->lock:
167 *
168 * hb -> futex_q, relation
169 * futex_q -> pi_state, relation
170 *
171 * (cannot be raw because hb can contain arbitrary amount
172 * of futex_q's)
173 *
174 * pi_mutex->wait_lock:
175 *
176 * {uval, pi_state}
177 *
178 * (and pi_mutex 'obviously')
179 *
180 * p->pi_lock:
181 *
182 * p->futex.pi_state_list -> pi_state->list, relation
183 * pi_mutex->owner -> pi_state->owner, relation
184 *
185 * pi_state->refcount:
186 *
187 * pi_state lifetime
188 *
189 *
190 * Lock order:
191 *
192 * hb->lock
193 * pi_mutex->wait_lock
194 * p->pi_lock
195 *
196 * Futex kernel state:
197 *
198 * The kernel tracks the task state in p::futex::state to protect against exit()
199 * and exec(). The states are:
200 *
201 * - FUTEX_STATE_OK when the task is alive and waiters can be attached
202 *
203 * - FUTEX_STATE_EXITING when the task cleans up the robust list and PI
204 * state. Concurrent waiters cannot attach anymore and have to wait until the
205 * cleanup is finished to re-evaluate the potential changes caused by the
206 * robust list and PI state cleanups.
207 *
208 * - FUTEX_STATE_DEAD when the task has cleaned up the robust list. This state
209 * is set independent of exit() or exec(). In the exit() case the task is
210 * gone. In the exec() case this ensures that nothing can attach to the task
211 * after cleaning up the robust list and PI state before it has switched to
212 * the new mm. From a futex point of view the task is dead until it sets the
213 * state to FUTEX_STATE_OK again after switching to the new mm.
214 *
215 * The valid state transitions for exit():
216 *
217 * FUTEX_STATE_OK -> FUTEX_STATE_EXITING -> FUTEX_STATE_DEAD
218 *
219 * The valid state transitions for exec():
220 *
221 * FUTEX_STATE_OK -> FUTEX_STATE_EXITING -> FUTEX_STATE_DEAD -> FUTEX_STATE_OK
222 *
223 * The state has two related locks:
224 *
225 * 1) p::pi_lock
226 *
227 * p::pi_lock has to be taken by the waiter when evaluating the state to
228 * protect against a concurrent exit/exec cleanup by the owner. If the state
229 * is OK then the waiter can be attached to the owner while still holding
230 * pi_lock.
231 *
232 * The cleanup code has to hold it for all state transitions to ensure that
233 * the stores to the state cannot be reordered against previous stores on
234 * which the waiter correctness depends on.
235 *
236 * 2) p::futex::exit_mutex
237 *
238 * The mutex is acquired when the cleanup starts and released at the end. It
239 * obviously is not serializing the owner's cleanup against itself. It is
240 * used to avoid a live lock caused by a waiter preempting the owner's
241 * cleanup. Such a waiter would busy loop forever waiting for the owner to
242 * finish the cleanup.
243 *
244 * To prevent this, waiters have to drop all locks when observing
245 * FUTEX_STATE_EXITING and block on the mutex. When the owner releases the
246 * mutex after finishing the cleanup the waiters make progress and
247 * re-evaluate the situation.
248 */
249
250/*
251 * Validate that the existing waiter has a pi_state and sanity check
252 * the pi_state against the user space value. If correct, attach to
253 * it.
254 */
255static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
256 struct futex_pi_state *pi_state,
257 struct futex_pi_state **ps)
258{
259 pid_t pid = uval & FUTEX_TID_MASK;
260 u32 uval2;
261 int ret;
262
263 /*
264 * Userspace might have messed up non-PI and PI futexes [3]
265 */
266 if (unlikely(!pi_state))
267 return -EINVAL;
268
269 /*
270 * We get here with hb->lock held, and having found a
271 * futex_top_waiter(). This means that futex_lock_pi() of said futex_q
272 * has dropped the hb->lock in between futex_queue() and futex_unqueue_pi(),
273 * which in turn means that futex_lock_pi() still has a reference on
274 * our pi_state.
275 *
276 * The waiter holding a reference on @pi_state also protects against
277 * the unlocked put_pi_state() in futex_unlock_pi(), futex_lock_pi()
278 * and futex_wait_requeue_pi() as it cannot go to 0 and consequently
279 * free pi_state before we can take a reference ourselves.
280 */
281 WARN_ON(!refcount_read(&pi_state->refcount));
282
283 /*
284 * Now that we have a pi_state, we can acquire wait_lock
285 * and do the state validation.
286 */
287 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
288
289 /*
290 * Since {uval, pi_state} is serialized by wait_lock, and our current
291 * uval was read without holding it, it can have changed. Verify it
292 * still is what we expect it to be, otherwise retry the entire
293 * operation.
294 */
295 if (futex_get_value_locked(&uval2, uaddr))
296 goto out_efault;
297
298 if (uval != uval2)
299 goto out_eagain;
300
301 /*
302 * Handle the owner died case:
303 */
304 if (uval & FUTEX_OWNER_DIED) {
305 /*
306 * exit_pi_state_list sets owner to NULL and wakes the
307 * topmost waiter. The task which acquires the
308 * pi_state->rt_mutex will fixup owner.
309 */
310 if (!pi_state->owner) {
311 /*
312 * No pi state owner, but the user space TID
313 * is not 0. Inconsistent state. [5]
314 */
315 if (pid)
316 goto out_einval;
317 /*
318 * Take a ref on the state and return success. [4]
319 */
320 goto out_attach;
321 }
322
323 /*
324 * If TID is 0, then either the dying owner has not
325 * yet executed exit_pi_state_list() or some waiter
326 * acquired the rtmutex in the pi state, but did not
327 * yet fixup the TID in user space.
328 *
329 * Take a ref on the state and return success. [6]
330 */
331 if (!pid)
332 goto out_attach;
333 } else {
334 /*
335 * If the owner died bit is not set, then the pi_state
336 * must have an owner. [7]
337 */
338 if (!pi_state->owner)
339 goto out_einval;
340 }
341
342 /*
343 * Bail out if user space manipulated the futex value. If pi
344 * state exists then the owner TID must be the same as the
345 * user space TID. [9/10]
346 */
347 if (pid != task_pid_vnr(pi_state->owner))
348 goto out_einval;
349
350out_attach:
351 get_pi_state(pi_state);
352 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
353 *ps = pi_state;
354 return 0;
355
356out_einval:
357 ret = -EINVAL;
358 goto out_error;
359
360out_eagain:
361 ret = -EAGAIN;
362 goto out_error;
363
364out_efault:
365 ret = -EFAULT;
366 goto out_error;
367
368out_error:
369 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
370 return ret;
371}
372
373static int handle_exit_race(u32 __user *uaddr, u32 uval)
374{
375 u32 uval2;
376
377 /*
378 * Reread the user space value to handle the following situation:
379 *
380 * CPU0 CPU1
381 *
382 * sys_exit() sys_futex()
383 * do_exit() futex_lock_pi()
384 * futex_lock_pi_atomic()
385 * exit_signals(tsk) No waiters:
386 * tsk->flags |= PF_EXITING; *uaddr == 0x00000PID
387 * mm_release(tsk) Set waiter bit
388 * exit_robust_list(tsk) { *uaddr = 0x80000PID;
389 * Set owner died attach_to_pi_owner() {
390 * *uaddr = 0xC0000000; tsk = get_task(PID);
391 * } if (!tsk->flags & PF_EXITING) {
392 * ... attach();
393 * tsk->futex.state = } else {
394 * FUTEX_STATE_DEAD; if (tsk->futex.state !=
395 * FUTEX_STATE_DEAD)
396 * return -EAGAIN;
397 * return -ESRCH; <--- FAIL
398 * }
399 *
400 * Returning ESRCH unconditionally is wrong here because the
401 * user space value has been changed by the exiting task.
402 *
403 * The same logic applies to the case where the exiting task is
404 * already gone.
405 */
406 if (futex_get_value_locked(&uval2, uaddr))
407 return -EFAULT;
408
409 /* If the user space value has changed, try again. */
410 if (uval2 != uval)
411 return -EAGAIN;
412
413 /*
414 * The exiting task did not have a robust list, the robust list was
415 * corrupted or the user space value in *uaddr is simply bogus.
416 * Give up and tell user space.
417 */
418 return -ESRCH;
419}
420
421static void __attach_to_pi_owner(struct task_struct *p, union futex_key *key,
422 struct futex_pi_state **ps)
423{
424 /*
425 * No existing pi state. First waiter. [2]
426 *
427 * This creates pi_state, we have hb->lock held, this means nothing can
428 * observe this state, wait_lock is irrelevant.
429 */
430 struct futex_pi_state *pi_state = alloc_pi_state();
431
432 /*
433 * Initialize the pi_mutex in locked state and make @p
434 * the owner of it:
435 */
436 __assume_ctx_lock(&pi_state->pi_mutex.wait_lock);
437 rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
438
439 /* Store the key for possible exit cleanups: */
440 pi_state->key = *key;
441
442 WARN_ON(!list_empty(&pi_state->list));
443 list_add(&pi_state->list, &p->futex.pi_state_list);
444 /*
445 * Assignment without holding pi_state->pi_mutex.wait_lock is safe
446 * because there is no concurrency as the object is not published yet.
447 */
448 pi_state->owner = p;
449
450 *ps = pi_state;
451}
452/*
453 * Lookup the task for the TID provided from user space and attach to
454 * it after doing proper sanity checks.
455 */
456static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
457 struct futex_pi_state **ps,
458 struct task_struct **exiting)
459{
460 pid_t pid = uval & FUTEX_TID_MASK;
461 struct task_struct *p;
462
463 /*
464 * We are the first waiter - try to look up the real owner and attach
465 * the new pi_state to it, but bail out when TID = 0 [1]
466 *
467 * The !pid check is paranoid. None of the call sites should end up
468 * with pid == 0, but better safe than sorry. Let the caller retry
469 */
470 if (!pid)
471 return -EAGAIN;
472 p = find_get_task_by_vpid(pid);
473 if (!p)
474 return handle_exit_race(uaddr, uval);
475
476 if (unlikely(p->flags & PF_KTHREAD)) {
477 put_task_struct(p);
478 return -EPERM;
479 }
480
481 /*
482 * We need to look at the task state to figure out whether the task is
483 * exiting. To protect against the change of the task state from
484 * FUTEX_STATE_OK to FUTEX_STATE_EXISTING in futex_cleanup_begin() it is
485 * required to do this protected by p->pi_lock, which prevents the owner
486 * from concurrently starting the exit cleanup.
487 *
488 * If the state is FUTEX_STATE_OK pi_lock must be held until the waiter
489 * is attached to protect against a concurrent exit()/exec().
490 */
491 raw_spin_lock_irq(&p->pi_lock);
492
493 /* Validate that the task is ready for futex operations. */
494 if (unlikely(p->futex.state != FUTEX_STATE_OK)) {
495 /*
496 * The task is on the way out. When state is FUTEX_STATE_EXITING
497 * the cleanup is in progress. To avoid a live lock when the
498 * waiter preempted the owner, store the task pointer in
499 * @exiting and keep the reference on the task. The calling code
500 * will drop all locks, block on @p::futex::exit_mutex and wait
501 * for the owner to finish the cleanup. Once the owner released
502 * the mutex the waiter drops the reference count and
503 * re-evaluates the situation.
504 */
505 if (p->futex.state == FUTEX_STATE_EXITING) {
506 raw_spin_unlock_irq(&p->pi_lock);
507 *exiting = p;
508 return -EBUSY;
509 }
510
511 int ret = handle_exit_race(uaddr, uval);
512
513 raw_spin_unlock_irq(&p->pi_lock);
514 put_task_struct(p);
515 return ret;
516 }
517
518 if (IS_ENABLED(CONFIG_MMU) && futex_key_is_private(key)) {
519 /*
520 * A private futex key holds a pointer to the waiter's mm
521 * without holding a reference on it. So it must not be attached
522 * to an owner in a different address space. Otherwise that
523 * owner's exit cleanup could access the private hash after the
524 * key's mm is freed.
525 */
526 if (unlikely(p->mm != key->private.mm)) {
527 raw_spin_unlock_irq(&p->pi_lock);
528 put_task_struct(p);
529 return -EPERM;
530 }
531 }
532
533 __attach_to_pi_owner(p, key, ps);
534 raw_spin_unlock_irq(&p->pi_lock);
535
536 put_task_struct(p);
537
538 return 0;
539}
540
541static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
542{
543 int err;
544 u32 curval;
545
546 if (unlikely(should_fail_futex(true)))
547 return -EFAULT;
548
549 err = futex_cmpxchg_value_locked(&curval, uaddr, uval, newval);
550 if (unlikely(err))
551 return err;
552
553 /* If user space value changed, let the caller retry */
554 return curval != uval ? -EAGAIN : 0;
555}
556
557/**
558 * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
559 * @uaddr: the pi futex user address
560 * @hb: the pi futex hash bucket
561 * @key: the futex key associated with uaddr and hb
562 * @ps: the pi_state pointer where we store the result of the
563 * lookup
564 * @task: the task to perform the atomic lock work for. This will
565 * be "current" except in the case of requeue pi.
566 * @exiting: Pointer to store the task pointer of the owner task
567 * which is in the middle of exiting
568 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
569 *
570 * Return:
571 * - 0 - ready to wait;
572 * - 1 - acquired the lock;
573 * - <0 - error
574 *
575 * The hb->lock must be held by the caller.
576 *
577 * @exiting is only set when the return value is -EBUSY. If so, this holds
578 * a refcount on the exiting task on return and the caller needs to drop it
579 * after waiting for the exit to complete.
580 */
581int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
582 union futex_key *key,
583 struct futex_pi_state **ps,
584 struct task_struct *task,
585 struct task_struct **exiting,
586 int set_waiters)
587{
588 u32 uval, newval, vpid = task_pid_vnr(task);
589 struct futex_q *top_waiter;
590 int ret;
591
592 /*
593 * Read the user space value first so we can validate a few
594 * things before proceeding further.
595 */
596 if (futex_get_value_locked(&uval, uaddr))
597 return -EFAULT;
598
599 if (unlikely(should_fail_futex(true)))
600 return -EFAULT;
601
602 /*
603 * Detect deadlocks.
604 */
605 if ((unlikely((uval & FUTEX_TID_MASK) == vpid)))
606 return -EDEADLK;
607
608 if ((unlikely(should_fail_futex(true))))
609 return -EDEADLK;
610
611 /*
612 * Lookup existing state first. If it exists, try to attach to
613 * its pi_state.
614 */
615 top_waiter = futex_top_waiter(hb, key);
616 if (top_waiter)
617 return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
618
619 /*
620 * No waiter and user TID is 0. We are here because the
621 * waiters or the owner died bit is set or called from
622 * requeue_cmp_pi or for whatever reason something took the
623 * syscall.
624 */
625 if (!(uval & FUTEX_TID_MASK)) {
626 /*
627 * We take over the futex. No other waiters and the user space
628 * TID is 0. We preserve the owner died bit.
629 */
630 newval = uval & FUTEX_OWNER_DIED;
631 newval |= vpid;
632
633 /* The futex requeue_pi code can enforce the waiters bit */
634 if (set_waiters)
635 newval |= FUTEX_WAITERS;
636
637 ret = lock_pi_update_atomic(uaddr, uval, newval);
638 if (ret)
639 return ret;
640
641 /*
642 * If the waiter bit was requested the caller also needs PI
643 * state attached to the new owner of the user space futex.
644 *
645 * @task is guaranteed to be alive and it cannot be exiting
646 * because it is either sleeping or waiting in
647 * futex_requeue_pi_wakeup_sync().
648 *
649 * No need to do the full attach_to_pi_owner() exercise
650 * because @task is known and valid.
651 */
652 if (set_waiters) {
653 raw_spin_lock_irq(&task->pi_lock);
654 __attach_to_pi_owner(task, key, ps);
655 raw_spin_unlock_irq(&task->pi_lock);
656 }
657 return 1;
658 }
659
660 /*
661 * First waiter. Set the waiters bit before attaching ourself to
662 * the owner. If owner tries to unlock, it will be forced into
663 * the kernel and blocked on hb->lock.
664 */
665 newval = uval | FUTEX_WAITERS;
666 ret = lock_pi_update_atomic(uaddr, uval, newval);
667 if (ret)
668 return ret;
669 /*
670 * If the update of the user space value succeeded, we try to
671 * attach to the owner. If that fails, no harm done, we only
672 * set the FUTEX_WAITERS bit in the user space variable.
673 */
674 return attach_to_pi_owner(uaddr, newval, key, ps, exiting);
675}
676
677/*
678 * Caller must hold a reference on @pi_state.
679 */
680static int wake_futex_pi(u32 __user *uaddr, u32 uval,
681 struct futex_pi_state *pi_state,
682 struct rt_mutex_waiter *top_waiter)
683 __must_hold(&pi_state->pi_mutex.wait_lock)
684 __releases(&pi_state->pi_mutex.wait_lock)
685{
686 struct task_struct *new_owner;
687 bool postunlock = false;
688 DEFINE_RT_WAKE_Q(wqh);
689 u32 curval, newval;
690 int ret = 0;
691
692 new_owner = top_waiter->task;
693
694 /*
695 * We pass it to the next owner. The WAITERS bit is always kept
696 * enabled while there is PI state around. We cleanup the owner
697 * died bit, because we are the owner.
698 */
699 newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
700
701 if (unlikely(should_fail_futex(true))) {
702 ret = -EFAULT;
703 goto out_unlock;
704 }
705
706 ret = futex_cmpxchg_value_locked(&curval, uaddr, uval, newval);
707 if (!ret && (curval != uval)) {
708 /*
709 * If a unconditional UNLOCK_PI operation (user space did not
710 * try the TID->0 transition) raced with a waiter setting the
711 * FUTEX_WAITERS flag between get_user() and locking the hash
712 * bucket lock, retry the operation.
713 */
714 if ((FUTEX_TID_MASK & curval) == uval)
715 ret = -EAGAIN;
716 else
717 ret = -EINVAL;
718 }
719
720 if (!ret) {
721 /*
722 * This is a point of no return; once we modified the uval
723 * there is no going back and subsequent operations must
724 * not fail.
725 */
726 pi_state_update_owner(pi_state, new_owner);
727 postunlock = __rt_mutex_futex_unlock(&pi_state->pi_mutex, &wqh);
728 }
729
730out_unlock:
731 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
732
733 if (postunlock)
734 rt_mutex_postunlock(&wqh);
735
736 return ret;
737}
738
739static int __fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
740 struct task_struct *argowner)
741 __must_hold(&q->pi_state->pi_mutex.wait_lock)
742 __must_hold(q->lock_ptr)
743{
744 struct futex_pi_state *pi_state = q->pi_state;
745 struct task_struct *oldowner, *newowner;
746 u32 uval, curval, newval, newtid;
747 int err = 0;
748
749 oldowner = pi_state->owner;
750
751 /*
752 * We are here because either:
753 *
754 * - we stole the lock and pi_state->owner needs updating to reflect
755 * that (@argowner == current),
756 *
757 * or:
758 *
759 * - someone stole our lock and we need to fix things to point to the
760 * new owner (@argowner == NULL).
761 *
762 * Either way, we have to replace the TID in the user space variable.
763 * This must be atomic as we have to preserve the owner died bit here.
764 *
765 * Note: We write the user space value _before_ changing the pi_state
766 * because we can fault here. Imagine swapped out pages or a fork
767 * that marked all the anonymous memory readonly for cow.
768 *
769 * Modifying pi_state _before_ the user space value would leave the
770 * pi_state in an inconsistent state when we fault here, because we
771 * need to drop the locks to handle the fault. This might be observed
772 * in the PID checks when attaching to PI state .
773 */
774retry:
775 if (!argowner) {
776 if (oldowner != current) {
777 /*
778 * We raced against a concurrent self; things are
779 * already fixed up. Nothing to do.
780 */
781 return 0;
782 }
783
784 if (__rt_mutex_futex_trylock(&pi_state->pi_mutex)) {
785 /* We got the lock. pi_state is correct. Tell caller. */
786 return 1;
787 }
788
789 /*
790 * The trylock just failed, so either there is an owner or
791 * there is a higher priority waiter than this one.
792 */
793 newowner = rt_mutex_owner(&pi_state->pi_mutex);
794 /*
795 * If the higher priority waiter has not yet taken over the
796 * rtmutex then newowner is NULL. We can't return here with
797 * that state because it's inconsistent vs. the user space
798 * state. So drop the locks and try again. It's a valid
799 * situation and not any different from the other retry
800 * conditions.
801 */
802 if (unlikely(!newowner)) {
803 err = -EAGAIN;
804 goto handle_err;
805 }
806 } else {
807 WARN_ON_ONCE(argowner != current);
808 if (oldowner == current) {
809 /*
810 * We raced against a concurrent self; things are
811 * already fixed up. Nothing to do.
812 */
813 return 1;
814 }
815 newowner = argowner;
816 }
817
818 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
819 /* Owner died? */
820 if (!pi_state->owner)
821 newtid |= FUTEX_OWNER_DIED;
822
823 err = futex_get_value_locked(&uval, uaddr);
824 if (err)
825 goto handle_err;
826
827 for (;;) {
828 newval = (uval & FUTEX_OWNER_DIED) | newtid;
829
830 err = futex_cmpxchg_value_locked(&curval, uaddr, uval, newval);
831 if (err)
832 goto handle_err;
833
834 if (curval == uval)
835 break;
836 uval = curval;
837 }
838
839 /*
840 * We fixed up user space. Now we need to fix the pi_state
841 * itself.
842 */
843 pi_state_update_owner(pi_state, newowner);
844
845 return argowner == current;
846
847 /*
848 * In order to reschedule or handle a page fault, we need to drop the
849 * locks here. In the case of a fault, this gives the other task
850 * (either the highest priority waiter itself or the task which stole
851 * the rtmutex) the chance to try the fixup of the pi_state. So once we
852 * are back from handling the fault we need to check the pi_state after
853 * reacquiring the locks and before trying to do another fixup. When
854 * the fixup has been done already we simply return.
855 *
856 * Note: we hold both hb->lock and pi_mutex->wait_lock. We can safely
857 * drop hb->lock since the caller owns the hb -> futex_q relation.
858 * Dropping the pi_mutex->wait_lock requires the state revalidate.
859 */
860handle_err:
861 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
862 spin_unlock(q->lock_ptr);
863
864 switch (err) {
865 case -EFAULT:
866 err = fault_in_user_writeable(uaddr);
867 break;
868
869 case -EAGAIN:
870 cond_resched();
871 err = 0;
872 break;
873
874 default:
875 WARN_ON_ONCE(1);
876 break;
877 }
878
879 futex_q_lockptr_lock(q);
880 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
881
882 /*
883 * Check if someone else fixed it for us:
884 */
885 if (pi_state->owner != oldowner)
886 return argowner == current;
887
888 /* Retry if err was -EAGAIN or the fault in succeeded */
889 if (!err)
890 goto retry;
891
892 /*
893 * fault_in_user_writeable() failed so user state is immutable. At
894 * best we can make the kernel state consistent but user state will
895 * be most likely hosed and any subsequent unlock operation will be
896 * rejected due to PI futex rule [10].
897 *
898 * Ensure that the rtmutex owner is also the pi_state owner despite
899 * the user space value claiming something different. There is no
900 * point in unlocking the rtmutex if current is the owner as it
901 * would need to wait until the next waiter has taken the rtmutex
902 * to guarantee consistent state. Keep it simple. Userspace asked
903 * for this wreckaged state.
904 *
905 * The rtmutex has an owner - either current or some other
906 * task. See the EAGAIN loop above.
907 */
908 pi_state_update_owner(pi_state, rt_mutex_owner(&pi_state->pi_mutex));
909
910 return err;
911}
912
913static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
914 struct task_struct *argowner)
915{
916 struct futex_pi_state *pi_state = q->pi_state;
917 int ret;
918
919 lockdep_assert_held(q->lock_ptr);
920
921 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
922 ret = __fixup_pi_state_owner(uaddr, q, argowner);
923 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
924 return ret;
925}
926
927/**
928 * fixup_pi_owner() - Post lock pi_state and corner case management
929 * @uaddr: user address of the futex
930 * @q: futex_q (contains pi_state and access to the rt_mutex)
931 * @locked: if the attempt to take the rt_mutex succeeded (1) or not (0)
932 *
933 * After attempting to lock an rt_mutex, this function is called to cleanup
934 * the pi_state owner as well as handle race conditions that may allow us to
935 * acquire the lock. Must be called with the hb lock held.
936 *
937 * Return:
938 * - 1 - success, lock taken;
939 * - 0 - success, lock not taken;
940 * - <0 - on error (-EFAULT)
941 */
942int fixup_pi_owner(u32 __user *uaddr, struct futex_q *q, int locked)
943{
944 if (locked) {
945 /*
946 * Got the lock. We might not be the anticipated owner if we
947 * did a lock-steal - fix up the PI-state in that case:
948 *
949 * Speculative pi_state->owner read (we don't hold wait_lock);
950 * since we own the lock pi_state->owner == current is the
951 * stable state, anything else needs more attention.
952 */
953 if (q->pi_state->owner != current)
954 return fixup_pi_state_owner(uaddr, q, current);
955 return 1;
956 }
957
958 /*
959 * If we didn't get the lock; check if anybody stole it from us. In
960 * that case, we need to fix up the uval to point to them instead of
961 * us, otherwise bad things happen. [10]
962 *
963 * Another speculative read; pi_state->owner == current is unstable
964 * but needs our attention.
965 */
966 if (q->pi_state->owner == current)
967 return fixup_pi_state_owner(uaddr, q, NULL);
968
969 /*
970 * Paranoia check. If we did not take the lock, then we should not be
971 * the owner of the rt_mutex. Warn and establish consistent state.
972 */
973 if (WARN_ON_ONCE(rt_mutex_owner(&q->pi_state->pi_mutex) == current))
974 return fixup_pi_state_owner(uaddr, q, current);
975
976 return 0;
977}
978
979/*
980 * Userspace tried a 0 -> TID atomic transition of the futex value
981 * and failed. The kernel side here does the whole locking operation:
982 * if there are waiters then it will block as a consequence of relying
983 * on rt-mutexes, it does PI, etc. (Due to races the kernel might see
984 * a 0 value of the futex too.).
985 *
986 * Also serves as futex trylock_pi()'ing, and due semantics.
987 */
988int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int trylock)
989{
990 struct hrtimer_sleeper timeout, *to;
991 struct task_struct *exiting;
992 struct rt_mutex_waiter rt_waiter;
993 struct futex_q q = futex_q_init;
994 DEFINE_WAKE_Q(wake_q);
995 int res, ret;
996
997 if (!IS_ENABLED(CONFIG_FUTEX_PI))
998 return -ENOSYS;
999
1000 if (refill_pi_state_cache())
1001 return -ENOMEM;
1002
1003 to = futex_setup_timer(time, &timeout, flags, 0);
1004
1005retry:
1006 exiting = NULL;
1007 ret = get_futex_key(uaddr, flags, &q.key, FUTEX_WRITE);
1008 if (unlikely(ret != 0))
1009 goto out;
1010
1011retry_private:
1012 if (1) {
1013 CLASS(hbr, hbr)(&q.key);
1014 auto hb = hbr.hb;
1015
1016 futex_q_lock(&q, hb);
1017
1018 ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &q.pi_state, current,
1019 &exiting, 0);
1020 if (unlikely(ret)) {
1021 /*
1022 * Atomic work succeeded and we got the lock,
1023 * or failed. Either way, we do _not_ block.
1024 */
1025 switch (ret) {
1026 case 1:
1027 /* We got the lock. */
1028 ret = 0;
1029 goto out_unlock_put_key;
1030 case -EFAULT:
1031 goto uaddr_faulted;
1032 case -EBUSY:
1033 case -EAGAIN:
1034 /*
1035 * Two reasons for this:
1036 * - EBUSY: Task is exiting and we just wait for the
1037 * exit to complete.
1038 * - EAGAIN: The user space value changed.
1039 */
1040 futex_q_unlock(hb);
1041 __release(q.lock_ptr);
1042 /*
1043 * Handle the case where the owner is in the middle of
1044 * exiting. Wait for the exit to complete otherwise
1045 * this task might loop forever, aka. live lock.
1046 */
1047 wait_for_owner_exiting(ret, exiting);
1048 cond_resched();
1049 goto retry;
1050 default:
1051 goto out_unlock_put_key;
1052 }
1053 }
1054
1055 WARN_ON(!q.pi_state);
1056
1057 /*
1058 * Only actually queue now that the atomic ops are done:
1059 */
1060 __futex_queue(&q, hb, current);
1061
1062 if (trylock) {
1063 ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
1064 /* Fixup the trylock return value: */
1065 ret = ret ? 0 : -EWOULDBLOCK;
1066 goto no_block;
1067 }
1068
1069 /*
1070 * Caution; releasing @hb in-scope. The hb->lock is still locked
1071 * while the reference is dropped. The reference can not be dropped
1072 * after the unlock because if a user initiated resize is in progress
1073 * then we might need to wake him. The hb will remain valid
1074 * because the thread, performing resize, will block on
1075 * hb->lock during the requeue.
1076 */
1077 futex_private_hash_put(no_free_ptr(hbr.fph));
1078
1079 rt_mutex_init_waiter(&rt_waiter);
1080
1081 /*
1082 * On PREEMPT_RT, when hb->lock becomes an rt_mutex, we must not
1083 * hold it while doing rt_mutex_start_proxy(), because then it will
1084 * include hb->lock in the blocking chain, even through we'll not in
1085 * fact hold it while blocking. This will lead it to report -EDEADLK
1086 * and BUG when futex_unlock_pi() interleaves with this.
1087 *
1088 * Therefore acquire wait_lock while holding hb->lock, but drop the
1089 * latter before calling __rt_mutex_start_proxy_lock(). This
1090 * interleaves with futex_unlock_pi() -- which does a similar lock
1091 * handoff -- such that the latter can observe the futex_q::pi_state
1092 * before __rt_mutex_start_proxy_lock() is done.
1093 */
1094 raw_spin_lock_irq(&q.pi_state->pi_mutex.wait_lock);
1095 spin_unlock(q.lock_ptr);
1096 /*
1097 * __rt_mutex_start_proxy_lock() unconditionally enqueues the @rt_waiter
1098 * such that futex_unlock_pi() is guaranteed to observe the waiter when
1099 * it sees the futex_q::pi_state.
1100 */
1101 ret = __rt_mutex_start_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter, current, &wake_q);
1102 raw_spin_unlock_irq_wake(&q.pi_state->pi_mutex.wait_lock, &wake_q);
1103
1104 if (ret) {
1105 if (ret == 1)
1106 ret = 0;
1107 goto cleanup;
1108 }
1109
1110 if (unlikely(to))
1111 hrtimer_sleeper_start_expires(to, HRTIMER_MODE_ABS);
1112
1113 ret = rt_mutex_wait_proxy_lock(&q.pi_state->pi_mutex, to, &rt_waiter);
1114
1115cleanup:
1116 /*
1117 * If we failed to acquire the lock (deadlock/signal/timeout), we must
1118 * unwind the above, however we canont lock hb->lock because
1119 * rt_mutex already has a waiter enqueued and hb->lock can itself try
1120 * and enqueue an rt_waiter through rtlock.
1121 *
1122 * Doing the cleanup without holding hb->lock can cause inconsistent
1123 * state between hb and pi_state, but only in the direction of not
1124 * seeing a waiter that is leaving.
1125 *
1126 * See futex_unlock_pi(), it deals with this inconsistency.
1127 *
1128 * There be dragons here, since we must deal with the inconsistency on
1129 * the way out (here), it is impossible to detect/warn about the race
1130 * the other way around (missing an incoming waiter).
1131 *
1132 * What could possibly go wrong...
1133 */
1134 if (ret && !rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter))
1135 ret = 0;
1136
1137 /*
1138 * Now that the rt_waiter has been dequeued, it is safe to use
1139 * spinlock/rtlock (which might enqueue its own rt_waiter) and fix up
1140 * the
1141 */
1142 futex_q_lockptr_lock(&q);
1143no_block:
1144 /*
1145 * Fixup the pi_state owner and possibly acquire the lock if we
1146 * haven't already.
1147 */
1148 res = fixup_pi_owner(uaddr, &q, !ret);
1149 /*
1150 * If fixup_pi_owner() returned an error, propagate that. If it acquired
1151 * the lock, clear our -ETIMEDOUT or -EINTR.
1152 */
1153 if (res)
1154 ret = (res < 0) ? res : 0;
1155
1156 __release(&hb->lock);
1157 futex_unqueue_pi(&q);
1158 spin_unlock(q.lock_ptr);
1159
1160 /* Additional reference from futex_unlock_pi() */
1161 futex_private_hash_put(q.drop_fph);
1162 goto out;
1163
1164out_unlock_put_key:
1165 futex_q_unlock(hb);
1166 __release(q.lock_ptr);
1167 goto out;
1168
1169uaddr_faulted:
1170 futex_q_unlock(hb);
1171 __release(q.lock_ptr);
1172
1173 ret = fault_in_user_writeable(uaddr);
1174 if (ret)
1175 goto out;
1176
1177 if (!(flags & FLAGS_SHARED))
1178 goto retry_private;
1179
1180 goto retry;
1181 }
1182
1183out:
1184 if (to) {
1185 hrtimer_cancel(&to->timer);
1186 destroy_hrtimer_on_stack(&to->timer);
1187 }
1188 return ret != -EINTR ? ret : -ERESTARTNOINTR;
1189}
1190
1191/*
1192 * Userspace attempted a TID -> 0 atomic transition, and failed.
1193 * This is the in-kernel slowpath: we look up the PI state (if any),
1194 * and do the rt-mutex unlock.
1195 */
1196static int __futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
1197{
1198 u32 curval, uval, vpid = task_pid_vnr(current);
1199 union futex_key key = FUTEX_KEY_INIT;
1200 struct futex_q *top_waiter;
1201 int ret;
1202
1203 if (!IS_ENABLED(CONFIG_FUTEX_PI))
1204 return -ENOSYS;
1205retry:
1206 if (get_user(uval, uaddr))
1207 return -EFAULT;
1208 /*
1209 * We release only a lock we actually own:
1210 */
1211 if ((uval & FUTEX_TID_MASK) != vpid)
1212 return -EPERM;
1213
1214 ret = get_futex_key(uaddr, flags, &key, FUTEX_WRITE);
1215 if (ret)
1216 return ret;
1217
1218 CLASS(hbr, hbr)(&key);
1219 auto hb = hbr.hb;
1220 spin_lock(&hb->lock);
1221retry_hb:
1222
1223 /*
1224 * Check waiters first. We do not trust user space values at
1225 * all and we at least want to know if user space fiddled
1226 * with the futex value instead of blindly unlocking.
1227 */
1228 top_waiter = futex_top_waiter(hb, &key);
1229 if (top_waiter) {
1230 struct futex_pi_state *pi_state = top_waiter->pi_state;
1231 struct rt_mutex_waiter *rt_waiter;
1232
1233 ret = -EINVAL;
1234 if (!pi_state)
1235 goto out_unlock;
1236
1237 /*
1238 * If current does not own the pi_state then the futex is
1239 * inconsistent and user space fiddled with the futex value.
1240 */
1241 if (pi_state->owner != current)
1242 goto out_unlock;
1243
1244 /*
1245 * By taking wait_lock while still holding hb->lock, we ensure
1246 * there is no point where we hold neither; and thereby
1247 * wake_futex_pi() must observe any new waiters.
1248 *
1249 * Since the cleanup: case in futex_lock_pi() removes the
1250 * rt_waiter without holding hb->lock, it is possible for
1251 * wake_futex_pi() to not find a waiter while the above does,
1252 * in this case the waiter is on the way out and it can be
1253 * ignored.
1254 *
1255 * In particular; this forces __rt_mutex_start_proxy() to
1256 * complete such that we're guaranteed to observe the
1257 * rt_waiter.
1258 */
1259 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
1260
1261 /*
1262 * Futex vs rt_mutex waiter state -- if there are no rt_mutex
1263 * waiters even though futex thinks there are, then the waiter
1264 * is leaving. The entry needs to be removed from the list so a
1265 * new futex_lock_pi() is not using this stale PI-state while
1266 * the futex is available in user space again.
1267 * There can be more than one task on its way out so it needs
1268 * to retry.
1269 */
1270 rt_waiter = rt_mutex_top_waiter(&pi_state->pi_mutex);
1271 if (!rt_waiter) {
1272 /*
1273 * Acquire a reference for the leaving waiter to ensure
1274 * valid futex_q::lock_ptr.
1275 */
1276 if (futex_key_is_private(&key))
1277 top_waiter->drop_fph = futex_private_hash(key.private.mm);
1278
1279 __futex_unqueue(top_waiter);
1280 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
1281 goto retry_hb;
1282 }
1283
1284 get_pi_state(pi_state);
1285 spin_unlock(&hb->lock);
1286
1287 /* drops pi_state->pi_mutex.wait_lock */
1288 ret = wake_futex_pi(uaddr, uval, pi_state, rt_waiter);
1289
1290 put_pi_state(pi_state);
1291
1292 /*
1293 * Success, we're done! No tricky corner cases.
1294 */
1295 if (!ret)
1296 return ret;
1297 /*
1298 * The atomic access to the futex value generated a
1299 * pagefault, so retry the user-access and the wakeup:
1300 */
1301 if (ret == -EFAULT)
1302 goto pi_faulted;
1303 /*
1304 * A unconditional UNLOCK_PI op raced against a waiter
1305 * setting the FUTEX_WAITERS bit. Try again.
1306 */
1307 if (ret == -EAGAIN)
1308 goto pi_retry;
1309 /*
1310 * wake_futex_pi has detected invalid state. Tell user
1311 * space.
1312 */
1313 return ret;
1314 }
1315
1316 /*
1317 * We have no kernel internal state, i.e. no waiters in the
1318 * kernel. Waiters which are about to queue themselves are stuck
1319 * on hb->lock. So we can safely ignore them. We do neither
1320 * preserve the WAITERS bit not the OWNER_DIED one. We are the
1321 * owner.
1322 */
1323 if ((ret = futex_cmpxchg_value_locked(&curval, uaddr, uval, 0))) {
1324 spin_unlock(&hb->lock);
1325 switch (ret) {
1326 case -EFAULT:
1327 goto pi_faulted;
1328
1329 case -EAGAIN:
1330 goto pi_retry;
1331
1332 default:
1333 WARN_ON_ONCE(1);
1334 return ret;
1335 }
1336 }
1337
1338 /*
1339 * If uval has changed, let user space handle it.
1340 */
1341 ret = (curval == uval) ? 0 : -EAGAIN;
1342
1343out_unlock:
1344 spin_unlock(&hb->lock);
1345 return ret;
1346
1347pi_retry:
1348 cond_resched();
1349 goto retry;
1350
1351pi_faulted:
1352
1353 ret = fault_in_user_writeable(uaddr);
1354 if (!ret)
1355 goto retry;
1356
1357 return ret;
1358}
1359
1360int futex_unlock_pi(u32 __user *uaddr, unsigned int flags, void __user *pop)
1361{
1362 int ret = __futex_unlock_pi(uaddr, flags);
1363
1364 if (ret || !(flags & FLAGS_ROBUST_UNLOCK))
1365 return ret;
1366
1367 if (!futex_robust_list_clear_pending(pop, flags))
1368 return -EFAULT;
1369
1370 return 0;
1371}