1/*
2 * Fast Userspace Mutexes (which I call "Futexes!").
3 * (C) Rusty Russell, IBM 2002
4 *
5 * Generalized futexes, futex requeueing, misc fixes by Ingo Molnar
6 * (C) Copyright 2003 Red Hat Inc, All Rights Reserved
7 *
8 * Removed page pinning, fix privately mapped COW pages and other cleanups
9 * (C) Copyright 2003, 2004 Jamie Lokier
10 *
11 * Robust futex support started by Ingo Molnar
12 * (C) Copyright 2006 Red Hat Inc, All Rights Reserved
13 * Thanks to Thomas Gleixner for suggestions, analysis and fixes.
14 *
15 * PI-futex support started by Ingo Molnar and Thomas Gleixner
16 * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
17 * Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
18 *
19 * PRIVATE futexes by Eric Dumazet
20 * Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com>
21 *
22 * Requeue-PI support by Darren Hart <dvhltc@us.ibm.com>
23 * Copyright (C) IBM Corporation, 2009
24 * Thanks to Thomas Gleixner for conceptual design and careful reviews.
25 *
26 * Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
27 * enough at me, Linus for the original (flawed) idea, Matthew
28 * Kirkwood for proof-of-concept implementation.
29 *
30 * "The futexes are also cursed."
31 * "But they come in a choice of three flavours!"
32 *
33 * This program is free software; you can redistribute it and/or modify
34 * it under the terms of the GNU General Public License as published by
35 * the Free Software Foundation; either version 2 of the License, or
36 * (at your option) any later version.
37 *
38 * This program is distributed in the hope that it will be useful,
39 * but WITHOUT ANY WARRANTY; without even the implied warranty of
40 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
41 * GNU General Public License for more details.
42 *
43 * You should have received a copy of the GNU General Public License
44 * along with this program; if not, write to the Free Software
45 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
46 */
47#include <linux/compat.h>
48#include <linux/slab.h>
49#include <linux/poll.h>
50#include <linux/fs.h>
51#include <linux/file.h>
52#include <linux/jhash.h>
53#include <linux/init.h>
54#include <linux/futex.h>
55#include <linux/mount.h>
56#include <linux/pagemap.h>
57#include <linux/syscalls.h>
58#include <linux/signal.h>
59#include <linux/export.h>
60#include <linux/magic.h>
61#include <linux/pid.h>
62#include <linux/nsproxy.h>
63#include <linux/ptrace.h>
64#include <linux/sched/rt.h>
65#include <linux/sched/wake_q.h>
66#include <linux/sched/mm.h>
67#include <linux/hugetlb.h>
68#include <linux/freezer.h>
69#include <linux/memblock.h>
70#include <linux/fault-inject.h>
71#include <linux/refcount.h>
72
73#include <asm/futex.h>
74
75#include "locking/rtmutex_common.h"
76
77/*
78 * READ this before attempting to hack on futexes!
79 *
80 * Basic futex operation and ordering guarantees
81 * =============================================
82 *
83 * The waiter reads the futex value in user space and calls
84 * futex_wait(). This function computes the hash bucket and acquires
85 * the hash bucket lock. After that it reads the futex user space value
86 * again and verifies that the data has not changed. If it has not changed
87 * it enqueues itself into the hash bucket, releases the hash bucket lock
88 * and schedules.
89 *
90 * The waker side modifies the user space value of the futex and calls
91 * futex_wake(). This function computes the hash bucket and acquires the
92 * hash bucket lock. Then it looks for waiters on that futex in the hash
93 * bucket and wakes them.
94 *
95 * In futex wake up scenarios where no tasks are blocked on a futex, taking
96 * the hb spinlock can be avoided and simply return. In order for this
97 * optimization to work, ordering guarantees must exist so that the waiter
98 * being added to the list is acknowledged when the list is concurrently being
99 * checked by the waker, avoiding scenarios like the following:
100 *
101 * CPU 0 CPU 1
102 * val = *futex;
103 * sys_futex(WAIT, futex, val);
104 * futex_wait(futex, val);
105 * uval = *futex;
106 * *futex = newval;
107 * sys_futex(WAKE, futex);
108 * futex_wake(futex);
109 * if (queue_empty())
110 * return;
111 * if (uval == val)
112 * lock(hash_bucket(futex));
113 * queue();
114 * unlock(hash_bucket(futex));
115 * schedule();
116 *
117 * This would cause the waiter on CPU 0 to wait forever because it
118 * missed the transition of the user space value from val to newval
119 * and the waker did not find the waiter in the hash bucket queue.
120 *
121 * The correct serialization ensures that a waiter either observes
122 * the changed user space value before blocking or is woken by a
123 * concurrent waker:
124 *
125 * CPU 0 CPU 1
126 * val = *futex;
127 * sys_futex(WAIT, futex, val);
128 * futex_wait(futex, val);
129 *
130 * waiters++; (a)
131 * smp_mb(); (A) <-- paired with -.
132 * |
133 * lock(hash_bucket(futex)); |
134 * |
135 * uval = *futex; |
136 * | *futex = newval;
137 * | sys_futex(WAKE, futex);
138 * | futex_wake(futex);
139 * |
140 * `--------> smp_mb(); (B)
141 * if (uval == val)
142 * queue();
143 * unlock(hash_bucket(futex));
144 * schedule(); if (waiters)
145 * lock(hash_bucket(futex));
146 * else wake_waiters(futex);
147 * waiters--; (b) unlock(hash_bucket(futex));
148 *
149 * Where (A) orders the waiters increment and the futex value read through
150 * atomic operations (see hb_waiters_inc) and where (B) orders the write
151 * to futex and the waiters read -- this is done by the barriers for both
152 * shared and private futexes in get_futex_key_refs().
153 *
154 * This yields the following case (where X:=waiters, Y:=futex):
155 *
156 * X = Y = 0
157 *
158 * w[X]=1 w[Y]=1
159 * MB MB
160 * r[Y]=y r[X]=x
161 *
162 * Which guarantees that x==0 && y==0 is impossible; which translates back into
163 * the guarantee that we cannot both miss the futex variable change and the
164 * enqueue.
165 *
166 * Note that a new waiter is accounted for in (a) even when it is possible that
167 * the wait call can return error, in which case we backtrack from it in (b).
168 * Refer to the comment in queue_lock().
169 *
170 * Similarly, in order to account for waiters being requeued on another
171 * address we always increment the waiters for the destination bucket before
172 * acquiring the lock. It then decrements them again after releasing it -
173 * the code that actually moves the futex(es) between hash buckets (requeue_futex)
174 * will do the additional required waiter count housekeeping. This is done for
175 * double_lock_hb() and double_unlock_hb(), respectively.
176 */
177
178#ifdef CONFIG_HAVE_FUTEX_CMPXCHG
179#define futex_cmpxchg_enabled 1
180#else
181static int __read_mostly futex_cmpxchg_enabled;
182#endif
183
184/*
185 * Futex flags used to encode options to functions and preserve them across
186 * restarts.
187 */
188#ifdef CONFIG_MMU
189# define FLAGS_SHARED 0x01
190#else
191/*
192 * NOMMU does not have per process address space. Let the compiler optimize
193 * code away.
194 */
195# define FLAGS_SHARED 0x00
196#endif
197#define FLAGS_CLOCKRT 0x02
198#define FLAGS_HAS_TIMEOUT 0x04
199
200/*
201 * Priority Inheritance state:
202 */
203struct futex_pi_state {
204 /*
205 * list of 'owned' pi_state instances - these have to be
206 * cleaned up in do_exit() if the task exits prematurely:
207 */
208 struct list_head list;
209
210 /*
211 * The PI object:
212 */
213 struct rt_mutex pi_mutex;
214
215 struct task_struct *owner;
216 refcount_t refcount;
217
218 union futex_key key;
219} __randomize_layout;
220
221/**
222 * struct futex_q - The hashed futex queue entry, one per waiting task
223 * @list: priority-sorted list of tasks waiting on this futex
224 * @task: the task waiting on the futex
225 * @lock_ptr: the hash bucket lock
226 * @key: the key the futex is hashed on
227 * @pi_state: optional priority inheritance state
228 * @rt_waiter: rt_waiter storage for use with requeue_pi
229 * @requeue_pi_key: the requeue_pi target futex key
230 * @bitset: bitset for the optional bitmasked wakeup
231 *
232 * We use this hashed waitqueue, instead of a normal wait_queue_entry_t, so
233 * we can wake only the relevant ones (hashed queues may be shared).
234 *
235 * A futex_q has a woken state, just like tasks have TASK_RUNNING.
236 * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
237 * The order of wakeup is always to make the first condition true, then
238 * the second.
239 *
240 * PI futexes are typically woken before they are removed from the hash list via
241 * the rt_mutex code. See unqueue_me_pi().
242 */
243struct futex_q {
244 struct plist_node list;
245
246 struct task_struct *task;
247 spinlock_t *lock_ptr;
248 union futex_key key;
249 struct futex_pi_state *pi_state;
250 struct rt_mutex_waiter *rt_waiter;
251 union futex_key *requeue_pi_key;
252 u32 bitset;
253} __randomize_layout;
254
255static const struct futex_q futex_q_init = {
256 /* list gets initialized in queue_me()*/
257 .key = FUTEX_KEY_INIT,
258 .bitset = FUTEX_BITSET_MATCH_ANY
259};
260
261/*
262 * Hash buckets are shared by all the futex_keys that hash to the same
263 * location. Each key may have multiple futex_q structures, one for each task
264 * waiting on a futex.
265 */
266struct futex_hash_bucket {
267 atomic_t waiters;
268 spinlock_t lock;
269 struct plist_head chain;
270} ____cacheline_aligned_in_smp;
271
272/*
273 * The base of the bucket array and its size are always used together
274 * (after initialization only in hash_futex()), so ensure that they
275 * reside in the same cacheline.
276 */
277static struct {
278 struct futex_hash_bucket *queues;
279 unsigned long hashsize;
280} __futex_data __read_mostly __aligned(2*sizeof(long));
281#define futex_queues (__futex_data.queues)
282#define futex_hashsize (__futex_data.hashsize)
283
284
285/*
286 * Fault injections for futexes.
287 */
288#ifdef CONFIG_FAIL_FUTEX
289
290static struct {
291 struct fault_attr attr;
292
293 bool ignore_private;
294} fail_futex = {
295 .attr = FAULT_ATTR_INITIALIZER,
296 .ignore_private = false,
297};
298
299static int __init setup_fail_futex(char *str)
300{
301 return setup_fault_attr(&fail_futex.attr, str);
302}
303__setup("fail_futex=", setup_fail_futex);
304
305static bool should_fail_futex(bool fshared)
306{
307 if (fail_futex.ignore_private && !fshared)
308 return false;
309
310 return should_fail(&fail_futex.attr, 1);
311}
312
313#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
314
315static int __init fail_futex_debugfs(void)
316{
317 umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
318 struct dentry *dir;
319
320 dir = fault_create_debugfs_attr("fail_futex", NULL,
321 &fail_futex.attr);
322 if (IS_ERR(dir))
323 return PTR_ERR(dir);
324
325 debugfs_create_bool("ignore-private", mode, dir,
326 &fail_futex.ignore_private);
327 return 0;
328}
329
330late_initcall(fail_futex_debugfs);
331
332#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
333
334#else
335static inline bool should_fail_futex(bool fshared)
336{
337 return false;
338}
339#endif /* CONFIG_FAIL_FUTEX */
340
341static inline void futex_get_mm(union futex_key *key)
342{
343 mmgrab(key->private.mm);
344 /*
345 * Ensure futex_get_mm() implies a full barrier such that
346 * get_futex_key() implies a full barrier. This is relied upon
347 * as smp_mb(); (B), see the ordering comment above.
348 */
349 smp_mb__after_atomic();
350}
351
352/*
353 * Reflects a new waiter being added to the waitqueue.
354 */
355static inline void hb_waiters_inc(struct futex_hash_bucket *hb)
356{
357#ifdef CONFIG_SMP
358 atomic_inc(&hb->waiters);
359 /*
360 * Full barrier (A), see the ordering comment above.
361 */
362 smp_mb__after_atomic();
363#endif
364}
365
366/*
367 * Reflects a waiter being removed from the waitqueue by wakeup
368 * paths.
369 */
370static inline void hb_waiters_dec(struct futex_hash_bucket *hb)
371{
372#ifdef CONFIG_SMP
373 atomic_dec(&hb->waiters);
374#endif
375}
376
377static inline int hb_waiters_pending(struct futex_hash_bucket *hb)
378{
379#ifdef CONFIG_SMP
380 return atomic_read(&hb->waiters);
381#else
382 return 1;
383#endif
384}
385
386/**
387 * hash_futex - Return the hash bucket in the global hash
388 * @key: Pointer to the futex key for which the hash is calculated
389 *
390 * We hash on the keys returned from get_futex_key (see below) and return the
391 * corresponding hash bucket in the global hash.
392 */
393static struct futex_hash_bucket *hash_futex(union futex_key *key)
394{
395 u32 hash = jhash2((u32*)&key->both.word,
396 (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
397 key->both.offset);
398 return &futex_queues[hash & (futex_hashsize - 1)];
399}
400
401
402/**
403 * match_futex - Check whether two futex keys are equal
404 * @key1: Pointer to key1
405 * @key2: Pointer to key2
406 *
407 * Return 1 if two futex_keys are equal, 0 otherwise.
408 */
409static inline int match_futex(union futex_key *key1, union futex_key *key2)
410{
411 return (key1 && key2
412 && key1->both.word == key2->both.word
413 && key1->both.ptr == key2->both.ptr
414 && key1->both.offset == key2->both.offset);
415}
416
417/*
418 * Take a reference to the resource addressed by a key.
419 * Can be called while holding spinlocks.
420 *
421 */
422static void get_futex_key_refs(union futex_key *key)
423{
424 if (!key->both.ptr)
425 return;
426
427 /*
428 * On MMU less systems futexes are always "private" as there is no per
429 * process address space. We need the smp wmb nevertheless - yes,
430 * arch/blackfin has MMU less SMP ...
431 */
432 if (!IS_ENABLED(CONFIG_MMU)) {
433 smp_mb(); /* explicit smp_mb(); (B) */
434 return;
435 }
436
437 switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
438 case FUT_OFF_INODE:
439 ihold(key->shared.inode); /* implies smp_mb(); (B) */
440 break;
441 case FUT_OFF_MMSHARED:
442 futex_get_mm(key); /* implies smp_mb(); (B) */
443 break;
444 default:
445 /*
446 * Private futexes do not hold reference on an inode or
447 * mm, therefore the only purpose of calling get_futex_key_refs
448 * is because we need the barrier for the lockless waiter check.
449 */
450 smp_mb(); /* explicit smp_mb(); (B) */
451 }
452}
453
454/*
455 * Drop a reference to the resource addressed by a key.
456 * The hash bucket spinlock must not be held. This is
457 * a no-op for private futexes, see comment in the get
458 * counterpart.
459 */
460static void drop_futex_key_refs(union futex_key *key)
461{
462 if (!key->both.ptr) {
463 /* If we're here then we tried to put a key we failed to get */
464 WARN_ON_ONCE(1);
465 return;
466 }
467
468 if (!IS_ENABLED(CONFIG_MMU))
469 return;
470
471 switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
472 case FUT_OFF_INODE:
473 iput(key->shared.inode);
474 break;
475 case FUT_OFF_MMSHARED:
476 mmdrop(key->private.mm);
477 break;
478 }
479}
480
481enum futex_access {
482 FUTEX_READ,
483 FUTEX_WRITE
484};
485
486/**
487 * get_futex_key() - Get parameters which are the keys for a futex
488 * @uaddr: virtual address of the futex
489 * @fshared: 0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
490 * @key: address where result is stored.
491 * @rw: mapping needs to be read/write (values: FUTEX_READ,
492 * FUTEX_WRITE)
493 *
494 * Return: a negative error code or 0
495 *
496 * The key words are stored in @key on success.
497 *
498 * For shared mappings, it's (page->index, file_inode(vma->vm_file),
499 * offset_within_page). For private mappings, it's (uaddr, current->mm).
500 * We can usually work out the index without swapping in the page.
501 *
502 * lock_page() might sleep, the caller should not hold a spinlock.
503 */
504static int
505get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key, enum futex_access rw)
506{
507 unsigned long address = (unsigned long)uaddr;
508 struct mm_struct *mm = current->mm;
509 struct page *page, *tail;
510 struct address_space *mapping;
511 int err, ro = 0;
512
513 /*
514 * The futex address must be "naturally" aligned.
515 */
516 key->both.offset = address % PAGE_SIZE;
517 if (unlikely((address % sizeof(u32)) != 0))
518 return -EINVAL;
519 address -= key->both.offset;
520
521 if (unlikely(!access_ok(uaddr, sizeof(u32))))
522 return -EFAULT;
523
524 if (unlikely(should_fail_futex(fshared)))
525 return -EFAULT;
526
527 /*
528 * PROCESS_PRIVATE futexes are fast.
529 * As the mm cannot disappear under us and the 'key' only needs
530 * virtual address, we dont even have to find the underlying vma.
531 * Note : We do have to check 'uaddr' is a valid user address,
532 * but access_ok() should be faster than find_vma()
533 */
534 if (!fshared) {
535 key->private.mm = mm;
536 key->private.address = address;
537 get_futex_key_refs(key); /* implies smp_mb(); (B) */
538 return 0;
539 }
540
541again:
542 /* Ignore any VERIFY_READ mapping (futex common case) */
543 if (unlikely(should_fail_futex(fshared)))
544 return -EFAULT;
545
546 err = get_user_pages_fast(address, 1, 1, &page);
547 /*
548 * If write access is not required (eg. FUTEX_WAIT), try
549 * and get read-only access.
550 */
551 if (err == -EFAULT && rw == FUTEX_READ) {
552 err = get_user_pages_fast(address, 1, 0, &page);
553 ro = 1;
554 }
555 if (err < 0)
556 return err;
557 else
558 err = 0;
559
560 /*
561 * The treatment of mapping from this point on is critical. The page
562 * lock protects many things but in this context the page lock
563 * stabilizes mapping, prevents inode freeing in the shared
564 * file-backed region case and guards against movement to swap cache.
565 *
566 * Strictly speaking the page lock is not needed in all cases being
567 * considered here and page lock forces unnecessarily serialization
568 * From this point on, mapping will be re-verified if necessary and
569 * page lock will be acquired only if it is unavoidable
570 *
571 * Mapping checks require the head page for any compound page so the
572 * head page and mapping is looked up now. For anonymous pages, it
573 * does not matter if the page splits in the future as the key is
574 * based on the address. For filesystem-backed pages, the tail is
575 * required as the index of the page determines the key. For
576 * base pages, there is no tail page and tail == page.
577 */
578 tail = page;
579 page = compound_head(page);
580 mapping = READ_ONCE(page->mapping);
581
582 /*
583 * If page->mapping is NULL, then it cannot be a PageAnon
584 * page; but it might be the ZERO_PAGE or in the gate area or
585 * in a special mapping (all cases which we are happy to fail);
586 * or it may have been a good file page when get_user_pages_fast
587 * found it, but truncated or holepunched or subjected to
588 * invalidate_complete_page2 before we got the page lock (also
589 * cases which we are happy to fail). And we hold a reference,
590 * so refcount care in invalidate_complete_page's remove_mapping
591 * prevents drop_caches from setting mapping to NULL beneath us.
592 *
593 * The case we do have to guard against is when memory pressure made
594 * shmem_writepage move it from filecache to swapcache beneath us:
595 * an unlikely race, but we do need to retry for page->mapping.
596 */
597 if (unlikely(!mapping)) {
598 int shmem_swizzled;
599
600 /*
601 * Page lock is required to identify which special case above
602 * applies. If this is really a shmem page then the page lock
603 * will prevent unexpected transitions.
604 */
605 lock_page(page);
606 shmem_swizzled = PageSwapCache(page) || page->mapping;
607 unlock_page(page);
608 put_page(page);
609
610 if (shmem_swizzled)
611 goto again;
612
613 return -EFAULT;
614 }
615
616 /*
617 * Private mappings are handled in a simple way.
618 *
619 * If the futex key is stored on an anonymous page, then the associated
620 * object is the mm which is implicitly pinned by the calling process.
621 *
622 * NOTE: When userspace waits on a MAP_SHARED mapping, even if
623 * it's a read-only handle, it's expected that futexes attach to
624 * the object not the particular process.
625 */
626 if (PageAnon(page)) {
627 /*
628 * A RO anonymous page will never change and thus doesn't make
629 * sense for futex operations.
630 */
631 if (unlikely(should_fail_futex(fshared)) || ro) {
632 err = -EFAULT;
633 goto out;
634 }
635
636 key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
637 key->private.mm = mm;
638 key->private.address = address;
639
640 get_futex_key_refs(key); /* implies smp_mb(); (B) */
641
642 } else {
643 struct inode *inode;
644
645 /*
646 * The associated futex object in this case is the inode and
647 * the page->mapping must be traversed. Ordinarily this should
648 * be stabilised under page lock but it's not strictly
649 * necessary in this case as we just want to pin the inode, not
650 * update the radix tree or anything like that.
651 *
652 * The RCU read lock is taken as the inode is finally freed
653 * under RCU. If the mapping still matches expectations then the
654 * mapping->host can be safely accessed as being a valid inode.
655 */
656 rcu_read_lock();
657
658 if (READ_ONCE(page->mapping) != mapping) {
659 rcu_read_unlock();
660 put_page(page);
661
662 goto again;
663 }
664
665 inode = READ_ONCE(mapping->host);
666 if (!inode) {
667 rcu_read_unlock();
668 put_page(page);
669
670 goto again;
671 }
672
673 /*
674 * Take a reference unless it is about to be freed. Previously
675 * this reference was taken by ihold under the page lock
676 * pinning the inode in place so i_lock was unnecessary. The
677 * only way for this check to fail is if the inode was
678 * truncated in parallel which is almost certainly an
679 * application bug. In such a case, just retry.
680 *
681 * We are not calling into get_futex_key_refs() in file-backed
682 * cases, therefore a successful atomic_inc return below will
683 * guarantee that get_futex_key() will still imply smp_mb(); (B).
684 */
685 if (!atomic_inc_not_zero(&inode->i_count)) {
686 rcu_read_unlock();
687 put_page(page);
688
689 goto again;
690 }
691
692 /* Should be impossible but lets be paranoid for now */
693 if (WARN_ON_ONCE(inode->i_mapping != mapping)) {
694 err = -EFAULT;
695 rcu_read_unlock();
696 iput(inode);
697
698 goto out;
699 }
700
701 key->both.offset |= FUT_OFF_INODE; /* inode-based key */
702 key->shared.inode = inode;
703 key->shared.pgoff = basepage_index(tail);
704 rcu_read_unlock();
705 }
706
707out:
708 put_page(page);
709 return err;
710}
711
712static inline void put_futex_key(union futex_key *key)
713{
714 drop_futex_key_refs(key);
715}
716
717/**
718 * fault_in_user_writeable() - Fault in user address and verify RW access
719 * @uaddr: pointer to faulting user space address
720 *
721 * Slow path to fixup the fault we just took in the atomic write
722 * access to @uaddr.
723 *
724 * We have no generic implementation of a non-destructive write to the
725 * user address. We know that we faulted in the atomic pagefault
726 * disabled section so we can as well avoid the #PF overhead by
727 * calling get_user_pages() right away.
728 */
729static int fault_in_user_writeable(u32 __user *uaddr)
730{
731 struct mm_struct *mm = current->mm;
732 int ret;
733
734 down_read(&mm->mmap_sem);
735 ret = fixup_user_fault(current, mm, (unsigned long)uaddr,
736 FAULT_FLAG_WRITE, NULL);
737 up_read(&mm->mmap_sem);
738
739 return ret < 0 ? ret : 0;
740}
741
742/**
743 * futex_top_waiter() - Return the highest priority waiter on a futex
744 * @hb: the hash bucket the futex_q's reside in
745 * @key: the futex key (to distinguish it from other futex futex_q's)
746 *
747 * Must be called with the hb lock held.
748 */
749static struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb,
750 union futex_key *key)
751{
752 struct futex_q *this;
753
754 plist_for_each_entry(this, &hb->chain, list) {
755 if (match_futex(&this->key, key))
756 return this;
757 }
758 return NULL;
759}
760
761static int cmpxchg_futex_value_locked(u32 *curval, u32 __user *uaddr,
762 u32 uval, u32 newval)
763{
764 int ret;
765
766 pagefault_disable();
767 ret = futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);
768 pagefault_enable();
769
770 return ret;
771}
772
773static int get_futex_value_locked(u32 *dest, u32 __user *from)
774{
775 int ret;
776
777 pagefault_disable();
778 ret = __get_user(*dest, from);
779 pagefault_enable();
780
781 return ret ? -EFAULT : 0;
782}
783
784
785/*
786 * PI code:
787 */
788static int refill_pi_state_cache(void)
789{
790 struct futex_pi_state *pi_state;
791
792 if (likely(current->pi_state_cache))
793 return 0;
794
795 pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
796
797 if (!pi_state)
798 return -ENOMEM;
799
800 INIT_LIST_HEAD(&pi_state->list);
801 /* pi_mutex gets initialized later */
802 pi_state->owner = NULL;
803 refcount_set(&pi_state->refcount, 1);
804 pi_state->key = FUTEX_KEY_INIT;
805
806 current->pi_state_cache = pi_state;
807
808 return 0;
809}
810
811static struct futex_pi_state *alloc_pi_state(void)
812{
813 struct futex_pi_state *pi_state = current->pi_state_cache;
814
815 WARN_ON(!pi_state);
816 current->pi_state_cache = NULL;
817
818 return pi_state;
819}
820
821static void get_pi_state(struct futex_pi_state *pi_state)
822{
823 WARN_ON_ONCE(!refcount_inc_not_zero(&pi_state->refcount));
824}
825
826/*
827 * Drops a reference to the pi_state object and frees or caches it
828 * when the last reference is gone.
829 */
830static void put_pi_state(struct futex_pi_state *pi_state)
831{
832 if (!pi_state)
833 return;
834
835 if (!refcount_dec_and_test(&pi_state->refcount))
836 return;
837
838 /*
839 * If pi_state->owner is NULL, the owner is most probably dying
840 * and has cleaned up the pi_state already
841 */
842 if (pi_state->owner) {
843 struct task_struct *owner;
844
845 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
846 owner = pi_state->owner;
847 if (owner) {
848 raw_spin_lock(&owner->pi_lock);
849 list_del_init(&pi_state->list);
850 raw_spin_unlock(&owner->pi_lock);
851 }
852 rt_mutex_proxy_unlock(&pi_state->pi_mutex, owner);
853 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
854 }
855
856 if (current->pi_state_cache) {
857 kfree(pi_state);
858 } else {
859 /*
860 * pi_state->list is already empty.
861 * clear pi_state->owner.
862 * refcount is at 0 - put it back to 1.
863 */
864 pi_state->owner = NULL;
865 refcount_set(&pi_state->refcount, 1);
866 current->pi_state_cache = pi_state;
867 }
868}
869
870#ifdef CONFIG_FUTEX_PI
871
872/*
873 * This task is holding PI mutexes at exit time => bad.
874 * Kernel cleans up PI-state, but userspace is likely hosed.
875 * (Robust-futex cleanup is separate and might save the day for userspace.)
876 */
877void exit_pi_state_list(struct task_struct *curr)
878{
879 struct list_head *next, *head = &curr->pi_state_list;
880 struct futex_pi_state *pi_state;
881 struct futex_hash_bucket *hb;
882 union futex_key key = FUTEX_KEY_INIT;
883
884 if (!futex_cmpxchg_enabled)
885 return;
886 /*
887 * We are a ZOMBIE and nobody can enqueue itself on
888 * pi_state_list anymore, but we have to be careful
889 * versus waiters unqueueing themselves:
890 */
891 raw_spin_lock_irq(&curr->pi_lock);
892 while (!list_empty(head)) {
893 next = head->next;
894 pi_state = list_entry(next, struct futex_pi_state, list);
895 key = pi_state->key;
896 hb = hash_futex(&key);
897
898 /*
899 * We can race against put_pi_state() removing itself from the
900 * list (a waiter going away). put_pi_state() will first
901 * decrement the reference count and then modify the list, so
902 * its possible to see the list entry but fail this reference
903 * acquire.
904 *
905 * In that case; drop the locks to let put_pi_state() make
906 * progress and retry the loop.
907 */
908 if (!refcount_inc_not_zero(&pi_state->refcount)) {
909 raw_spin_unlock_irq(&curr->pi_lock);
910 cpu_relax();
911 raw_spin_lock_irq(&curr->pi_lock);
912 continue;
913 }
914 raw_spin_unlock_irq(&curr->pi_lock);
915
916 spin_lock(&hb->lock);
917 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
918 raw_spin_lock(&curr->pi_lock);
919 /*
920 * We dropped the pi-lock, so re-check whether this
921 * task still owns the PI-state:
922 */
923 if (head->next != next) {
924 /* retain curr->pi_lock for the loop invariant */
925 raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
926 spin_unlock(&hb->lock);
927 put_pi_state(pi_state);
928 continue;
929 }
930
931 WARN_ON(pi_state->owner != curr);
932 WARN_ON(list_empty(&pi_state->list));
933 list_del_init(&pi_state->list);
934 pi_state->owner = NULL;
935
936 raw_spin_unlock(&curr->pi_lock);
937 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
938 spin_unlock(&hb->lock);
939
940 rt_mutex_futex_unlock(&pi_state->pi_mutex);
941 put_pi_state(pi_state);
942
943 raw_spin_lock_irq(&curr->pi_lock);
944 }
945 raw_spin_unlock_irq(&curr->pi_lock);
946}
947
948#endif
949
950/*
951 * We need to check the following states:
952 *
953 * Waiter | pi_state | pi->owner | uTID | uODIED | ?
954 *
955 * [1] NULL | --- | --- | 0 | 0/1 | Valid
956 * [2] NULL | --- | --- | >0 | 0/1 | Valid
957 *
958 * [3] Found | NULL | -- | Any | 0/1 | Invalid
959 *
960 * [4] Found | Found | NULL | 0 | 1 | Valid
961 * [5] Found | Found | NULL | >0 | 1 | Invalid
962 *
963 * [6] Found | Found | task | 0 | 1 | Valid
964 *
965 * [7] Found | Found | NULL | Any | 0 | Invalid
966 *
967 * [8] Found | Found | task | ==taskTID | 0/1 | Valid
968 * [9] Found | Found | task | 0 | 0 | Invalid
969 * [10] Found | Found | task | !=taskTID | 0/1 | Invalid
970 *
971 * [1] Indicates that the kernel can acquire the futex atomically. We
972 * came came here due to a stale FUTEX_WAITERS/FUTEX_OWNER_DIED bit.
973 *
974 * [2] Valid, if TID does not belong to a kernel thread. If no matching
975 * thread is found then it indicates that the owner TID has died.
976 *
977 * [3] Invalid. The waiter is queued on a non PI futex
978 *
979 * [4] Valid state after exit_robust_list(), which sets the user space
980 * value to FUTEX_WAITERS | FUTEX_OWNER_DIED.
981 *
982 * [5] The user space value got manipulated between exit_robust_list()
983 * and exit_pi_state_list()
984 *
985 * [6] Valid state after exit_pi_state_list() which sets the new owner in
986 * the pi_state but cannot access the user space value.
987 *
988 * [7] pi_state->owner can only be NULL when the OWNER_DIED bit is set.
989 *
990 * [8] Owner and user space value match
991 *
992 * [9] There is no transient state which sets the user space TID to 0
993 * except exit_robust_list(), but this is indicated by the
994 * FUTEX_OWNER_DIED bit. See [4]
995 *
996 * [10] There is no transient state which leaves owner and user space
997 * TID out of sync.
998 *
999 *
1000 * Serialization and lifetime rules:
1001 *
1002 * hb->lock:
1003 *
1004 * hb -> futex_q, relation
1005 * futex_q -> pi_state, relation
1006 *
1007 * (cannot be raw because hb can contain arbitrary amount
1008 * of futex_q's)
1009 *
1010 * pi_mutex->wait_lock:
1011 *
1012 * {uval, pi_state}
1013 *
1014 * (and pi_mutex 'obviously')
1015 *
1016 * p->pi_lock:
1017 *
1018 * p->pi_state_list -> pi_state->list, relation
1019 *
1020 * pi_state->refcount:
1021 *
1022 * pi_state lifetime
1023 *
1024 *
1025 * Lock order:
1026 *
1027 * hb->lock
1028 * pi_mutex->wait_lock
1029 * p->pi_lock
1030 *
1031 */
1032
1033/*
1034 * Validate that the existing waiter has a pi_state and sanity check
1035 * the pi_state against the user space value. If correct, attach to
1036 * it.
1037 */
1038static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
1039 struct futex_pi_state *pi_state,
1040 struct futex_pi_state **ps)
1041{
1042 pid_t pid = uval & FUTEX_TID_MASK;
1043 u32 uval2;
1044 int ret;
1045
1046 /*
1047 * Userspace might have messed up non-PI and PI futexes [3]
1048 */
1049 if (unlikely(!pi_state))
1050 return -EINVAL;
1051
1052 /*
1053 * We get here with hb->lock held, and having found a
1054 * futex_top_waiter(). This means that futex_lock_pi() of said futex_q
1055 * has dropped the hb->lock in between queue_me() and unqueue_me_pi(),
1056 * which in turn means that futex_lock_pi() still has a reference on
1057 * our pi_state.
1058 *
1059 * The waiter holding a reference on @pi_state also protects against
1060 * the unlocked put_pi_state() in futex_unlock_pi(), futex_lock_pi()
1061 * and futex_wait_requeue_pi() as it cannot go to 0 and consequently
1062 * free pi_state before we can take a reference ourselves.
1063 */
1064 WARN_ON(!refcount_read(&pi_state->refcount));
1065
1066 /*
1067 * Now that we have a pi_state, we can acquire wait_lock
1068 * and do the state validation.
1069 */
1070 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
1071
1072 /*
1073 * Since {uval, pi_state} is serialized by wait_lock, and our current
1074 * uval was read without holding it, it can have changed. Verify it
1075 * still is what we expect it to be, otherwise retry the entire
1076 * operation.
1077 */
1078 if (get_futex_value_locked(&uval2, uaddr))
1079 goto out_efault;
1080
1081 if (uval != uval2)
1082 goto out_eagain;
1083
1084 /*
1085 * Handle the owner died case:
1086 */
1087 if (uval & FUTEX_OWNER_DIED) {
1088 /*
1089 * exit_pi_state_list sets owner to NULL and wakes the
1090 * topmost waiter. The task which acquires the
1091 * pi_state->rt_mutex will fixup owner.
1092 */
1093 if (!pi_state->owner) {
1094 /*
1095 * No pi state owner, but the user space TID
1096 * is not 0. Inconsistent state. [5]
1097 */
1098 if (pid)
1099 goto out_einval;
1100 /*
1101 * Take a ref on the state and return success. [4]
1102 */
1103 goto out_attach;
1104 }
1105
1106 /*
1107 * If TID is 0, then either the dying owner has not
1108 * yet executed exit_pi_state_list() or some waiter
1109 * acquired the rtmutex in the pi state, but did not
1110 * yet fixup the TID in user space.
1111 *
1112 * Take a ref on the state and return success. [6]
1113 */
1114 if (!pid)
1115 goto out_attach;
1116 } else {
1117 /*
1118 * If the owner died bit is not set, then the pi_state
1119 * must have an owner. [7]
1120 */
1121 if (!pi_state->owner)
1122 goto out_einval;
1123 }
1124
1125 /*
1126 * Bail out if user space manipulated the futex value. If pi
1127 * state exists then the owner TID must be the same as the
1128 * user space TID. [9/10]
1129 */
1130 if (pid != task_pid_vnr(pi_state->owner))
1131 goto out_einval;
1132
1133out_attach:
1134 get_pi_state(pi_state);
1135 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
1136 *ps = pi_state;
1137 return 0;
1138
1139out_einval:
1140 ret = -EINVAL;
1141 goto out_error;
1142
1143out_eagain:
1144 ret = -EAGAIN;
1145 goto out_error;
1146
1147out_efault:
1148 ret = -EFAULT;
1149 goto out_error;
1150
1151out_error:
1152 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
1153 return ret;
1154}
1155
1156static int handle_exit_race(u32 __user *uaddr, u32 uval,
1157 struct task_struct *tsk)
1158{
1159 u32 uval2;
1160
1161 /*
1162 * If PF_EXITPIDONE is not yet set, then try again.
1163 */
1164 if (tsk && !(tsk->flags & PF_EXITPIDONE))
1165 return -EAGAIN;
1166
1167 /*
1168 * Reread the user space value to handle the following situation:
1169 *
1170 * CPU0 CPU1
1171 *
1172 * sys_exit() sys_futex()
1173 * do_exit() futex_lock_pi()
1174 * futex_lock_pi_atomic()
1175 * exit_signals(tsk) No waiters:
1176 * tsk->flags |= PF_EXITING; *uaddr == 0x00000PID
1177 * mm_release(tsk) Set waiter bit
1178 * exit_robust_list(tsk) { *uaddr = 0x80000PID;
1179 * Set owner died attach_to_pi_owner() {
1180 * *uaddr = 0xC0000000; tsk = get_task(PID);
1181 * } if (!tsk->flags & PF_EXITING) {
1182 * ... attach();
1183 * tsk->flags |= PF_EXITPIDONE; } else {
1184 * if (!(tsk->flags & PF_EXITPIDONE))
1185 * return -EAGAIN;
1186 * return -ESRCH; <--- FAIL
1187 * }
1188 *
1189 * Returning ESRCH unconditionally is wrong here because the
1190 * user space value has been changed by the exiting task.
1191 *
1192 * The same logic applies to the case where the exiting task is
1193 * already gone.
1194 */
1195 if (get_futex_value_locked(&uval2, uaddr))
1196 return -EFAULT;
1197
1198 /* If the user space value has changed, try again. */
1199 if (uval2 != uval)
1200 return -EAGAIN;
1201
1202 /*
1203 * The exiting task did not have a robust list, the robust list was
1204 * corrupted or the user space value in *uaddr is simply bogus.
1205 * Give up and tell user space.
1206 */
1207 return -ESRCH;
1208}
1209
1210/*
1211 * Lookup the task for the TID provided from user space and attach to
1212 * it after doing proper sanity checks.
1213 */
1214static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
1215 struct futex_pi_state **ps)
1216{
1217 pid_t pid = uval & FUTEX_TID_MASK;
1218 struct futex_pi_state *pi_state;
1219 struct task_struct *p;
1220
1221 /*
1222 * We are the first waiter - try to look up the real owner and attach
1223 * the new pi_state to it, but bail out when TID = 0 [1]
1224 *
1225 * The !pid check is paranoid. None of the call sites should end up
1226 * with pid == 0, but better safe than sorry. Let the caller retry
1227 */
1228 if (!pid)
1229 return -EAGAIN;
1230 p = find_get_task_by_vpid(pid);
1231 if (!p)
1232 return handle_exit_race(uaddr, uval, NULL);
1233
1234 if (unlikely(p->flags & PF_KTHREAD)) {
1235 put_task_struct(p);
1236 return -EPERM;
1237 }
1238
1239 /*
1240 * We need to look at the task state flags to figure out,
1241 * whether the task is exiting. To protect against the do_exit
1242 * change of the task flags, we do this protected by
1243 * p->pi_lock:
1244 */
1245 raw_spin_lock_irq(&p->pi_lock);
1246 if (unlikely(p->flags & PF_EXITING)) {
1247 /*
1248 * The task is on the way out. When PF_EXITPIDONE is
1249 * set, we know that the task has finished the
1250 * cleanup:
1251 */
1252 int ret = handle_exit_race(uaddr, uval, p);
1253
1254 raw_spin_unlock_irq(&p->pi_lock);
1255 put_task_struct(p);
1256 return ret;
1257 }
1258
1259 /*
1260 * No existing pi state. First waiter. [2]
1261 *
1262 * This creates pi_state, we have hb->lock held, this means nothing can
1263 * observe this state, wait_lock is irrelevant.
1264 */
1265 pi_state = alloc_pi_state();
1266
1267 /*
1268 * Initialize the pi_mutex in locked state and make @p
1269 * the owner of it:
1270 */
1271 rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
1272
1273 /* Store the key for possible exit cleanups: */
1274 pi_state->key = *key;
1275
1276 WARN_ON(!list_empty(&pi_state->list));
1277 list_add(&pi_state->list, &p->pi_state_list);
1278 /*
1279 * Assignment without holding pi_state->pi_mutex.wait_lock is safe
1280 * because there is no concurrency as the object is not published yet.
1281 */
1282 pi_state->owner = p;
1283 raw_spin_unlock_irq(&p->pi_lock);
1284
1285 put_task_struct(p);
1286
1287 *ps = pi_state;
1288
1289 return 0;
1290}
1291
1292static int lookup_pi_state(u32 __user *uaddr, u32 uval,
1293 struct futex_hash_bucket *hb,
1294 union futex_key *key, struct futex_pi_state **ps)
1295{
1296 struct futex_q *top_waiter = futex_top_waiter(hb, key);
1297
1298 /*
1299 * If there is a waiter on that futex, validate it and
1300 * attach to the pi_state when the validation succeeds.
1301 */
1302 if (top_waiter)
1303 return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
1304
1305 /*
1306 * We are the first waiter - try to look up the owner based on
1307 * @uval and attach to it.
1308 */
1309 return attach_to_pi_owner(uaddr, uval, key, ps);
1310}
1311
1312static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
1313{
1314 u32 uninitialized_var(curval);
1315
1316 if (unlikely(should_fail_futex(true)))
1317 return -EFAULT;
1318
1319 if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)))
1320 return -EFAULT;
1321
1322 /* If user space value changed, let the caller retry */
1323 return curval != uval ? -EAGAIN : 0;
1324}
1325
1326/**
1327 * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
1328 * @uaddr: the pi futex user address
1329 * @hb: the pi futex hash bucket
1330 * @key: the futex key associated with uaddr and hb
1331 * @ps: the pi_state pointer where we store the result of the
1332 * lookup
1333 * @task: the task to perform the atomic lock work for. This will
1334 * be "current" except in the case of requeue pi.
1335 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
1336 *
1337 * Return:
1338 * - 0 - ready to wait;
1339 * - 1 - acquired the lock;
1340 * - <0 - error
1341 *
1342 * The hb->lock and futex_key refs shall be held by the caller.
1343 */
1344static int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
1345 union futex_key *key,
1346 struct futex_pi_state **ps,
1347 struct task_struct *task, int set_waiters)
1348{
1349 u32 uval, newval, vpid = task_pid_vnr(task);
1350 struct futex_q *top_waiter;
1351 int ret;
1352
1353 /*
1354 * Read the user space value first so we can validate a few
1355 * things before proceeding further.
1356 */
1357 if (get_futex_value_locked(&uval, uaddr))
1358 return -EFAULT;
1359
1360 if (unlikely(should_fail_futex(true)))
1361 return -EFAULT;
1362
1363 /*
1364 * Detect deadlocks.
1365 */
1366 if ((unlikely((uval & FUTEX_TID_MASK) == vpid)))
1367 return -EDEADLK;
1368
1369 if ((unlikely(should_fail_futex(true))))
1370 return -EDEADLK;
1371
1372 /*
1373 * Lookup existing state first. If it exists, try to attach to
1374 * its pi_state.
1375 */
1376 top_waiter = futex_top_waiter(hb, key);
1377 if (top_waiter)
1378 return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
1379
1380 /*
1381 * No waiter and user TID is 0. We are here because the
1382 * waiters or the owner died bit is set or called from
1383 * requeue_cmp_pi or for whatever reason something took the
1384 * syscall.
1385 */
1386 if (!(uval & FUTEX_TID_MASK)) {
1387 /*
1388 * We take over the futex. No other waiters and the user space
1389 * TID is 0. We preserve the owner died bit.
1390 */
1391 newval = uval & FUTEX_OWNER_DIED;
1392 newval |= vpid;
1393
1394 /* The futex requeue_pi code can enforce the waiters bit */
1395 if (set_waiters)
1396 newval |= FUTEX_WAITERS;
1397
1398 ret = lock_pi_update_atomic(uaddr, uval, newval);
1399 /* If the take over worked, return 1 */
1400 return ret < 0 ? ret : 1;
1401 }
1402
1403 /*
1404 * First waiter. Set the waiters bit before attaching ourself to
1405 * the owner. If owner tries to unlock, it will be forced into
1406 * the kernel and blocked on hb->lock.
1407 */
1408 newval = uval | FUTEX_WAITERS;
1409 ret = lock_pi_update_atomic(uaddr, uval, newval);
1410 if (ret)
1411 return ret;
1412 /*
1413 * If the update of the user space value succeeded, we try to
1414 * attach to the owner. If that fails, no harm done, we only
1415 * set the FUTEX_WAITERS bit in the user space variable.
1416 */
1417 return attach_to_pi_owner(uaddr, newval, key, ps);
1418}
1419
1420/**
1421 * __unqueue_futex() - Remove the futex_q from its futex_hash_bucket
1422 * @q: The futex_q to unqueue
1423 *
1424 * The q->lock_ptr must not be NULL and must be held by the caller.
1425 */
1426static void __unqueue_futex(struct futex_q *q)
1427{
1428 struct futex_hash_bucket *hb;
1429
1430 if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list)))
1431 return;
1432 lockdep_assert_held(q->lock_ptr);
1433
1434 hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);
1435 plist_del(&q->list, &hb->chain);
1436 hb_waiters_dec(hb);
1437}
1438
1439/*
1440 * The hash bucket lock must be held when this is called.
1441 * Afterwards, the futex_q must not be accessed. Callers
1442 * must ensure to later call wake_up_q() for the actual
1443 * wakeups to occur.
1444 */
1445static void mark_wake_futex(struct wake_q_head *wake_q, struct futex_q *q)
1446{
1447 struct task_struct *p = q->task;
1448
1449 if (WARN(q->pi_state || q->rt_waiter, "refusing to wake PI futex\n"))
1450 return;
1451
1452 get_task_struct(p);
1453 __unqueue_futex(q);
1454 /*
1455 * The waiting task can free the futex_q as soon as q->lock_ptr = NULL
1456 * is written, without taking any locks. This is possible in the event
1457 * of a spurious wakeup, for example. A memory barrier is required here
1458 * to prevent the following store to lock_ptr from getting ahead of the
1459 * plist_del in __unqueue_futex().
1460 */
1461 smp_store_release(&q->lock_ptr, NULL);
1462
1463 /*
1464 * Queue the task for later wakeup for after we've released
1465 * the hb->lock. wake_q_add() grabs reference to p.
1466 */
1467 wake_q_add_safe(wake_q, p);
1468}
1469
1470/*
1471 * Caller must hold a reference on @pi_state.
1472 */
1473static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_pi_state *pi_state)
1474{
1475 u32 uninitialized_var(curval), newval;
1476 struct task_struct *new_owner;
1477 bool postunlock = false;
1478 DEFINE_WAKE_Q(wake_q);
1479 int ret = 0;
1480
1481 new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
1482 if (WARN_ON_ONCE(!new_owner)) {
1483 /*
1484 * As per the comment in futex_unlock_pi() this should not happen.
1485 *
1486 * When this happens, give up our locks and try again, giving
1487 * the futex_lock_pi() instance time to complete, either by
1488 * waiting on the rtmutex or removing itself from the futex
1489 * queue.
1490 */
1491 ret = -EAGAIN;
1492 goto out_unlock;
1493 }
1494
1495 /*
1496 * We pass it to the next owner. The WAITERS bit is always kept
1497 * enabled while there is PI state around. We cleanup the owner
1498 * died bit, because we are the owner.
1499 */
1500 newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
1501
1502 if (unlikely(should_fail_futex(true)))
1503 ret = -EFAULT;
1504
1505 if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)) {
1506 ret = -EFAULT;
1507
1508 } else if (curval != uval) {
1509 /*
1510 * If a unconditional UNLOCK_PI operation (user space did not
1511 * try the TID->0 transition) raced with a waiter setting the
1512 * FUTEX_WAITERS flag between get_user() and locking the hash
1513 * bucket lock, retry the operation.
1514 */
1515 if ((FUTEX_TID_MASK & curval) == uval)
1516 ret = -EAGAIN;
1517 else
1518 ret = -EINVAL;
1519 }
1520
1521 if (ret)
1522 goto out_unlock;
1523
1524 /*
1525 * This is a point of no return; once we modify the uval there is no
1526 * going back and subsequent operations must not fail.
1527 */
1528
1529 raw_spin_lock(&pi_state->owner->pi_lock);
1530 WARN_ON(list_empty(&pi_state->list));
1531 list_del_init(&pi_state->list);
1532 raw_spin_unlock(&pi_state->owner->pi_lock);
1533
1534 raw_spin_lock(&new_owner->pi_lock);
1535 WARN_ON(!list_empty(&pi_state->list));
1536 list_add(&pi_state->list, &new_owner->pi_state_list);
1537 pi_state->owner = new_owner;
1538 raw_spin_unlock(&new_owner->pi_lock);
1539
1540 postunlock = __rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
1541
1542out_unlock:
1543 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
1544
1545 if (postunlock)
1546 rt_mutex_postunlock(&wake_q);
1547
1548 return ret;
1549}
1550
1551/*
1552 * Express the locking dependencies for lockdep:
1553 */
1554static inline void
1555double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
1556{
1557 if (hb1 <= hb2) {
1558 spin_lock(&hb1->lock);
1559 if (hb1 < hb2)
1560 spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
1561 } else { /* hb1 > hb2 */
1562 spin_lock(&hb2->lock);
1563 spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
1564 }
1565}
1566
1567static inline void
1568double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
1569{
1570 spin_unlock(&hb1->lock);
1571 if (hb1 != hb2)
1572 spin_unlock(&hb2->lock);
1573}
1574
1575/*
1576 * Wake up waiters matching bitset queued on this futex (uaddr).
1577 */
1578static int
1579futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
1580{
1581 struct futex_hash_bucket *hb;
1582 struct futex_q *this, *next;
1583 union futex_key key = FUTEX_KEY_INIT;
1584 int ret;
1585 DEFINE_WAKE_Q(wake_q);
1586
1587 if (!bitset)
1588 return -EINVAL;
1589
1590 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, FUTEX_READ);
1591 if (unlikely(ret != 0))
1592 goto out;
1593
1594 hb = hash_futex(&key);
1595
1596 /* Make sure we really have tasks to wakeup */
1597 if (!hb_waiters_pending(hb))
1598 goto out_put_key;
1599
1600 spin_lock(&hb->lock);
1601
1602 plist_for_each_entry_safe(this, next, &hb->chain, list) {
1603 if (match_futex (&this->key, &key)) {
1604 if (this->pi_state || this->rt_waiter) {
1605 ret = -EINVAL;
1606 break;
1607 }
1608
1609 /* Check if one of the bits is set in both bitsets */
1610 if (!(this->bitset & bitset))
1611 continue;
1612
1613 mark_wake_futex(&wake_q, this);
1614 if (++ret >= nr_wake)
1615 break;
1616 }
1617 }
1618
1619 spin_unlock(&hb->lock);
1620 wake_up_q(&wake_q);
1621out_put_key:
1622 put_futex_key(&key);
1623out:
1624 return ret;
1625}
1626
1627static int futex_atomic_op_inuser(unsigned int encoded_op, u32 __user *uaddr)
1628{
1629 unsigned int op = (encoded_op & 0x70000000) >> 28;
1630 unsigned int cmp = (encoded_op & 0x0f000000) >> 24;
1631 int oparg = sign_extend32((encoded_op & 0x00fff000) >> 12, 11);
1632 int cmparg = sign_extend32(encoded_op & 0x00000fff, 11);
1633 int oldval, ret;
1634
1635 if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28)) {
1636 if (oparg < 0 || oparg > 31) {
1637 char comm[sizeof(current->comm)];
1638 /*
1639 * kill this print and return -EINVAL when userspace
1640 * is sane again
1641 */
1642 pr_info_ratelimited("futex_wake_op: %s tries to shift op by %d; fix this program\n",
1643 get_task_comm(comm, current), oparg);
1644 oparg &= 31;
1645 }
1646 oparg = 1 << oparg;
1647 }
1648
1649 if (!access_ok(uaddr, sizeof(u32)))
1650 return -EFAULT;
1651
1652 ret = arch_futex_atomic_op_inuser(op, oparg, &oldval, uaddr);
1653 if (ret)
1654 return ret;
1655
1656 switch (cmp) {
1657 case FUTEX_OP_CMP_EQ:
1658 return oldval == cmparg;
1659 case FUTEX_OP_CMP_NE:
1660 return oldval != cmparg;
1661 case FUTEX_OP_CMP_LT:
1662 return oldval < cmparg;
1663 case FUTEX_OP_CMP_GE:
1664 return oldval >= cmparg;
1665 case FUTEX_OP_CMP_LE:
1666 return oldval <= cmparg;
1667 case FUTEX_OP_CMP_GT:
1668 return oldval > cmparg;
1669 default:
1670 return -ENOSYS;
1671 }
1672}
1673
1674/*
1675 * Wake up all waiters hashed on the physical page that is mapped
1676 * to this virtual address:
1677 */
1678static int
1679futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
1680 int nr_wake, int nr_wake2, int op)
1681{
1682 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
1683 struct futex_hash_bucket *hb1, *hb2;
1684 struct futex_q *this, *next;
1685 int ret, op_ret;
1686 DEFINE_WAKE_Q(wake_q);
1687
1688retry:
1689 ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, FUTEX_READ);
1690 if (unlikely(ret != 0))
1691 goto out;
1692 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, FUTEX_WRITE);
1693 if (unlikely(ret != 0))
1694 goto out_put_key1;
1695
1696 hb1 = hash_futex(&key1);
1697 hb2 = hash_futex(&key2);
1698
1699retry_private:
1700 double_lock_hb(hb1, hb2);
1701 op_ret = futex_atomic_op_inuser(op, uaddr2);
1702 if (unlikely(op_ret < 0)) {
1703
1704 double_unlock_hb(hb1, hb2);
1705
1706#ifndef CONFIG_MMU
1707 /*
1708 * we don't get EFAULT from MMU faults if we don't have an MMU,
1709 * but we might get them from range checking
1710 */
1711 ret = op_ret;
1712 goto out_put_keys;
1713#endif
1714
1715 if (unlikely(op_ret != -EFAULT)) {
1716 ret = op_ret;
1717 goto out_put_keys;
1718 }
1719
1720 ret = fault_in_user_writeable(uaddr2);
1721 if (ret)
1722 goto out_put_keys;
1723
1724 if (!(flags & FLAGS_SHARED))
1725 goto retry_private;
1726
1727 put_futex_key(&key2);
1728 put_futex_key(&key1);
1729 goto retry;
1730 }
1731
1732 plist_for_each_entry_safe(this, next, &hb1->chain, list) {
1733 if (match_futex (&this->key, &key1)) {
1734 if (this->pi_state || this->rt_waiter) {
1735 ret = -EINVAL;
1736 goto out_unlock;
1737 }
1738 mark_wake_futex(&wake_q, this);
1739 if (++ret >= nr_wake)
1740 break;
1741 }
1742 }
1743
1744 if (op_ret > 0) {
1745 op_ret = 0;
1746 plist_for_each_entry_safe(this, next, &hb2->chain, list) {
1747 if (match_futex (&this->key, &key2)) {
1748 if (this->pi_state || this->rt_waiter) {
1749 ret = -EINVAL;
1750 goto out_unlock;
1751 }
1752 mark_wake_futex(&wake_q, this);
1753 if (++op_ret >= nr_wake2)
1754 break;
1755 }
1756 }
1757 ret += op_ret;
1758 }
1759
1760out_unlock:
1761 double_unlock_hb(hb1, hb2);
1762 wake_up_q(&wake_q);
1763out_put_keys:
1764 put_futex_key(&key2);
1765out_put_key1:
1766 put_futex_key(&key1);
1767out:
1768 return ret;
1769}
1770
1771/**
1772 * requeue_futex() - Requeue a futex_q from one hb to another
1773 * @q: the futex_q to requeue
1774 * @hb1: the source hash_bucket
1775 * @hb2: the target hash_bucket
1776 * @key2: the new key for the requeued futex_q
1777 */
1778static inline
1779void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
1780 struct futex_hash_bucket *hb2, union futex_key *key2)
1781{
1782
1783 /*
1784 * If key1 and key2 hash to the same bucket, no need to
1785 * requeue.
1786 */
1787 if (likely(&hb1->chain != &hb2->chain)) {
1788 plist_del(&q->list, &hb1->chain);
1789 hb_waiters_dec(hb1);
1790 hb_waiters_inc(hb2);
1791 plist_add(&q->list, &hb2->chain);
1792 q->lock_ptr = &hb2->lock;
1793 }
1794 get_futex_key_refs(key2);
1795 q->key = *key2;
1796}
1797
1798/**
1799 * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
1800 * @q: the futex_q
1801 * @key: the key of the requeue target futex
1802 * @hb: the hash_bucket of the requeue target futex
1803 *
1804 * During futex_requeue, with requeue_pi=1, it is possible to acquire the
1805 * target futex if it is uncontended or via a lock steal. Set the futex_q key
1806 * to the requeue target futex so the waiter can detect the wakeup on the right
1807 * futex, but remove it from the hb and NULL the rt_waiter so it can detect
1808 * atomic lock acquisition. Set the q->lock_ptr to the requeue target hb->lock
1809 * to protect access to the pi_state to fixup the owner later. Must be called
1810 * with both q->lock_ptr and hb->lock held.
1811 */
1812static inline
1813void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
1814 struct futex_hash_bucket *hb)
1815{
1816 get_futex_key_refs(key);
1817 q->key = *key;
1818
1819 __unqueue_futex(q);
1820
1821 WARN_ON(!q->rt_waiter);
1822 q->rt_waiter = NULL;
1823
1824 q->lock_ptr = &hb->lock;
1825
1826 wake_up_state(q->task, TASK_NORMAL);
1827}
1828
1829/**
1830 * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter
1831 * @pifutex: the user address of the to futex
1832 * @hb1: the from futex hash bucket, must be locked by the caller
1833 * @hb2: the to futex hash bucket, must be locked by the caller
1834 * @key1: the from futex key
1835 * @key2: the to futex key
1836 * @ps: address to store the pi_state pointer
1837 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
1838 *
1839 * Try and get the lock on behalf of the top waiter if we can do it atomically.
1840 * Wake the top waiter if we succeed. If the caller specified set_waiters,
1841 * then direct futex_lock_pi_atomic() to force setting the FUTEX_WAITERS bit.
1842 * hb1 and hb2 must be held by the caller.
1843 *
1844 * Return:
1845 * - 0 - failed to acquire the lock atomically;
1846 * - >0 - acquired the lock, return value is vpid of the top_waiter
1847 * - <0 - error
1848 */
1849static int futex_proxy_trylock_atomic(u32 __user *pifutex,
1850 struct futex_hash_bucket *hb1,
1851 struct futex_hash_bucket *hb2,
1852 union futex_key *key1, union futex_key *key2,
1853 struct futex_pi_state **ps, int set_waiters)
1854{
1855 struct futex_q *top_waiter = NULL;
1856 u32 curval;
1857 int ret, vpid;
1858
1859 if (get_futex_value_locked(&curval, pifutex))
1860 return -EFAULT;
1861
1862 if (unlikely(should_fail_futex(true)))
1863 return -EFAULT;
1864
1865 /*
1866 * Find the top_waiter and determine if there are additional waiters.
1867 * If the caller intends to requeue more than 1 waiter to pifutex,
1868 * force futex_lock_pi_atomic() to set the FUTEX_WAITERS bit now,
1869 * as we have means to handle the possible fault. If not, don't set
1870 * the bit unecessarily as it will force the subsequent unlock to enter
1871 * the kernel.
1872 */
1873 top_waiter = futex_top_waiter(hb1, key1);
1874
1875 /* There are no waiters, nothing for us to do. */
1876 if (!top_waiter)
1877 return 0;
1878
1879 /* Ensure we requeue to the expected futex. */
1880 if (!match_futex(top_waiter->requeue_pi_key, key2))
1881 return -EINVAL;
1882
1883 /*
1884 * Try to take the lock for top_waiter. Set the FUTEX_WAITERS bit in
1885 * the contended case or if set_waiters is 1. The pi_state is returned
1886 * in ps in contended cases.
1887 */
1888 vpid = task_pid_vnr(top_waiter->task);
1889 ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
1890 set_waiters);
1891 if (ret == 1) {
1892 requeue_pi_wake_futex(top_waiter, key2, hb2);
1893 return vpid;
1894 }
1895 return ret;
1896}
1897
1898/**
1899 * futex_requeue() - Requeue waiters from uaddr1 to uaddr2
1900 * @uaddr1: source futex user address
1901 * @flags: futex flags (FLAGS_SHARED, etc.)
1902 * @uaddr2: target futex user address
1903 * @nr_wake: number of waiters to wake (must be 1 for requeue_pi)
1904 * @nr_requeue: number of waiters to requeue (0-INT_MAX)
1905 * @cmpval: @uaddr1 expected value (or %NULL)
1906 * @requeue_pi: if we are attempting to requeue from a non-pi futex to a
1907 * pi futex (pi to pi requeue is not supported)
1908 *
1909 * Requeue waiters on uaddr1 to uaddr2. In the requeue_pi case, try to acquire
1910 * uaddr2 atomically on behalf of the top waiter.
1911 *
1912 * Return:
1913 * - >=0 - on success, the number of tasks requeued or woken;
1914 * - <0 - on error
1915 */
1916static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
1917 u32 __user *uaddr2, int nr_wake, int nr_requeue,
1918 u32 *cmpval, int requeue_pi)
1919{
1920 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
1921 int drop_count = 0, task_count = 0, ret;
1922 struct futex_pi_state *pi_state = NULL;
1923 struct futex_hash_bucket *hb1, *hb2;
1924 struct futex_q *this, *next;
1925 DEFINE_WAKE_Q(wake_q);
1926
1927 if (nr_wake < 0 || nr_requeue < 0)
1928 return -EINVAL;
1929
1930 /*
1931 * When PI not supported: return -ENOSYS if requeue_pi is true,
1932 * consequently the compiler knows requeue_pi is always false past
1933 * this point which will optimize away all the conditional code
1934 * further down.
1935 */
1936 if (!IS_ENABLED(CONFIG_FUTEX_PI) && requeue_pi)
1937 return -ENOSYS;
1938
1939 if (requeue_pi) {
1940 /*
1941 * Requeue PI only works on two distinct uaddrs. This
1942 * check is only valid for private futexes. See below.
1943 */
1944 if (uaddr1 == uaddr2)
1945 return -EINVAL;
1946
1947 /*
1948 * requeue_pi requires a pi_state, try to allocate it now
1949 * without any locks in case it fails.
1950 */
1951 if (refill_pi_state_cache())
1952 return -ENOMEM;
1953 /*
1954 * requeue_pi must wake as many tasks as it can, up to nr_wake
1955 * + nr_requeue, since it acquires the rt_mutex prior to
1956 * returning to userspace, so as to not leave the rt_mutex with
1957 * waiters and no owner. However, second and third wake-ups
1958 * cannot be predicted as they involve race conditions with the
1959 * first wake and a fault while looking up the pi_state. Both
1960 * pthread_cond_signal() and pthread_cond_broadcast() should
1961 * use nr_wake=1.
1962 */
1963 if (nr_wake != 1)
1964 return -EINVAL;
1965 }
1966
1967retry:
1968 ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, FUTEX_READ);
1969 if (unlikely(ret != 0))
1970 goto out;
1971 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2,
1972 requeue_pi ? FUTEX_WRITE : FUTEX_READ);
1973 if (unlikely(ret != 0))
1974 goto out_put_key1;
1975
1976 /*
1977 * The check above which compares uaddrs is not sufficient for
1978 * shared futexes. We need to compare the keys:
1979 */
1980 if (requeue_pi && match_futex(&key1, &key2)) {
1981 ret = -EINVAL;
1982 goto out_put_keys;
1983 }
1984
1985 hb1 = hash_futex(&key1);
1986 hb2 = hash_futex(&key2);
1987
1988retry_private:
1989 hb_waiters_inc(hb2);
1990 double_lock_hb(hb1, hb2);
1991
1992 if (likely(cmpval != NULL)) {
1993 u32 curval;
1994
1995 ret = get_futex_value_locked(&curval, uaddr1);
1996
1997 if (unlikely(ret)) {
1998 double_unlock_hb(hb1, hb2);
1999 hb_waiters_dec(hb2);
2000
2001 ret = get_user(curval, uaddr1);
2002 if (ret)
2003 goto out_put_keys;
2004
2005 if (!(flags & FLAGS_SHARED))
2006 goto retry_private;
2007
2008 put_futex_key(&key2);
2009 put_futex_key(&key1);
2010 goto retry;
2011 }
2012 if (curval != *cmpval) {
2013 ret = -EAGAIN;
2014 goto out_unlock;
2015 }
2016 }
2017
2018 if (requeue_pi && (task_count - nr_wake < nr_requeue)) {
2019 /*
2020 * Attempt to acquire uaddr2 and wake the top waiter. If we
2021 * intend to requeue waiters, force setting the FUTEX_WAITERS
2022 * bit. We force this here where we are able to easily handle
2023 * faults rather in the requeue loop below.
2024 */
2025 ret = futex_proxy_trylock_atomic(uaddr2, hb1, hb2, &key1,
2026 &key2, &pi_state, nr_requeue);
2027
2028 /*
2029 * At this point the top_waiter has either taken uaddr2 or is
2030 * waiting on it. If the former, then the pi_state will not
2031 * exist yet, look it up one more time to ensure we have a
2032 * reference to it. If the lock was taken, ret contains the
2033 * vpid of the top waiter task.
2034 * If the lock was not taken, we have pi_state and an initial
2035 * refcount on it. In case of an error we have nothing.
2036 */
2037 if (ret > 0) {
2038 WARN_ON(pi_state);
2039 drop_count++;
2040 task_count++;
2041 /*
2042 * If we acquired the lock, then the user space value
2043 * of uaddr2 should be vpid. It cannot be changed by
2044 * the top waiter as it is blocked on hb2 lock if it
2045 * tries to do so. If something fiddled with it behind
2046 * our back the pi state lookup might unearth it. So
2047 * we rather use the known value than rereading and
2048 * handing potential crap to lookup_pi_state.
2049 *
2050 * If that call succeeds then we have pi_state and an
2051 * initial refcount on it.
2052 */
2053 ret = lookup_pi_state(uaddr2, ret, hb2, &key2, &pi_state);
2054 }
2055
2056 switch (ret) {
2057 case 0:
2058 /* We hold a reference on the pi state. */
2059 break;
2060
2061 /* If the above failed, then pi_state is NULL */
2062 case -EFAULT:
2063 double_unlock_hb(hb1, hb2);
2064 hb_waiters_dec(hb2);
2065 put_futex_key(&key2);
2066 put_futex_key(&key1);
2067 ret = fault_in_user_writeable(uaddr2);
2068 if (!ret)
2069 goto retry;
2070 goto out;
2071 case -EAGAIN:
2072 /*
2073 * Two reasons for this:
2074 * - Owner is exiting and we just wait for the
2075 * exit to complete.
2076 * - The user space value changed.
2077 */
2078 double_unlock_hb(hb1, hb2);
2079 hb_waiters_dec(hb2);
2080 put_futex_key(&key2);
2081 put_futex_key(&key1);
2082 cond_resched();
2083 goto retry;
2084 default:
2085 goto out_unlock;
2086 }
2087 }
2088
2089 plist_for_each_entry_safe(this, next, &hb1->chain, list) {
2090 if (task_count - nr_wake >= nr_requeue)
2091 break;
2092
2093 if (!match_futex(&this->key, &key1))
2094 continue;
2095
2096 /*
2097 * FUTEX_WAIT_REQEUE_PI and FUTEX_CMP_REQUEUE_PI should always
2098 * be paired with each other and no other futex ops.
2099 *
2100 * We should never be requeueing a futex_q with a pi_state,
2101 * which is awaiting a futex_unlock_pi().
2102 */
2103 if ((requeue_pi && !this->rt_waiter) ||
2104 (!requeue_pi && this->rt_waiter) ||
2105 this->pi_state) {
2106 ret = -EINVAL;
2107 break;
2108 }
2109
2110 /*
2111 * Wake nr_wake waiters. For requeue_pi, if we acquired the
2112 * lock, we already woke the top_waiter. If not, it will be
2113 * woken by futex_unlock_pi().
2114 */
2115 if (++task_count <= nr_wake && !requeue_pi) {
2116 mark_wake_futex(&wake_q, this);
2117 continue;
2118 }
2119
2120 /* Ensure we requeue to the expected futex for requeue_pi. */
2121 if (requeue_pi && !match_futex(this->requeue_pi_key, &key2)) {
2122 ret = -EINVAL;
2123 break;
2124 }
2125
2126 /*
2127 * Requeue nr_requeue waiters and possibly one more in the case
2128 * of requeue_pi if we couldn't acquire the lock atomically.
2129 */
2130 if (requeue_pi) {
2131 /*
2132 * Prepare the waiter to take the rt_mutex. Take a
2133 * refcount on the pi_state and store the pointer in
2134 * the futex_q object of the waiter.
2135 */
2136 get_pi_state(pi_state);
2137 this->pi_state = pi_state;
2138 ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,
2139 this->rt_waiter,
2140 this->task);
2141 if (ret == 1) {
2142 /*
2143 * We got the lock. We do neither drop the
2144 * refcount on pi_state nor clear
2145 * this->pi_state because the waiter needs the
2146 * pi_state for cleaning up the user space
2147 * value. It will drop the refcount after
2148 * doing so.
2149 */
2150 requeue_pi_wake_futex(this, &key2, hb2);
2151 drop_count++;
2152 continue;
2153 } else if (ret) {
2154 /*
2155 * rt_mutex_start_proxy_lock() detected a
2156 * potential deadlock when we tried to queue
2157 * that waiter. Drop the pi_state reference
2158 * which we took above and remove the pointer
2159 * to the state from the waiters futex_q
2160 * object.
2161 */
2162 this->pi_state = NULL;
2163 put_pi_state(pi_state);
2164 /*
2165 * We stop queueing more waiters and let user
2166 * space deal with the mess.
2167 */
2168 break;
2169 }
2170 }
2171 requeue_futex(this, hb1, hb2, &key2);
2172 drop_count++;
2173 }
2174
2175 /*
2176 * We took an extra initial reference to the pi_state either
2177 * in futex_proxy_trylock_atomic() or in lookup_pi_state(). We
2178 * need to drop it here again.
2179 */
2180 put_pi_state(pi_state);
2181
2182out_unlock:
2183 double_unlock_hb(hb1, hb2);
2184 wake_up_q(&wake_q);
2185 hb_waiters_dec(hb2);
2186
2187 /*
2188 * drop_futex_key_refs() must be called outside the spinlocks. During
2189 * the requeue we moved futex_q's from the hash bucket at key1 to the
2190 * one at key2 and updated their key pointer. We no longer need to
2191 * hold the references to key1.
2192 */
2193 while (--drop_count >= 0)
2194 drop_futex_key_refs(&key1);
2195
2196out_put_keys:
2197 put_futex_key(&key2);
2198out_put_key1:
2199 put_futex_key(&key1);
2200out:
2201 return ret ? ret : task_count;
2202}
2203
2204/* The key must be already stored in q->key. */
2205static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
2206 __acquires(&hb->lock)
2207{
2208 struct futex_hash_bucket *hb;
2209
2210 hb = hash_futex(&q->key);
2211
2212 /*
2213 * Increment the counter before taking the lock so that
2214 * a potential waker won't miss a to-be-slept task that is
2215 * waiting for the spinlock. This is safe as all queue_lock()
2216 * users end up calling queue_me(). Similarly, for housekeeping,
2217 * decrement the counter at queue_unlock() when some error has
2218 * occurred and we don't end up adding the task to the list.
2219 */
2220 hb_waiters_inc(hb); /* implies smp_mb(); (A) */
2221
2222 q->lock_ptr = &hb->lock;
2223
2224 spin_lock(&hb->lock);
2225 return hb;
2226}
2227
2228static inline void
2229queue_unlock(struct futex_hash_bucket *hb)
2230 __releases(&hb->lock)
2231{
2232 spin_unlock(&hb->lock);
2233 hb_waiters_dec(hb);
2234}
2235
2236static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
2237{
2238 int prio;
2239
2240 /*
2241 * The priority used to register this element is
2242 * - either the real thread-priority for the real-time threads
2243 * (i.e. threads with a priority lower than MAX_RT_PRIO)
2244 * - or MAX_RT_PRIO for non-RT threads.
2245 * Thus, all RT-threads are woken first in priority order, and
2246 * the others are woken last, in FIFO order.
2247 */
2248 prio = min(current->normal_prio, MAX_RT_PRIO);
2249
2250 plist_node_init(&q->list, prio);
2251 plist_add(&q->list, &hb->chain);
2252 q->task = current;
2253}
2254
2255/**
2256 * queue_me() - Enqueue the futex_q on the futex_hash_bucket
2257 * @q: The futex_q to enqueue
2258 * @hb: The destination hash bucket
2259 *
2260 * The hb->lock must be held by the caller, and is released here. A call to
2261 * queue_me() is typically paired with exactly one call to unqueue_me(). The
2262 * exceptions involve the PI related operations, which may use unqueue_me_pi()
2263 * or nothing if the unqueue is done as part of the wake process and the unqueue
2264 * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
2265 * an example).
2266 */
2267static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
2268 __releases(&hb->lock)
2269{
2270 __queue_me(q, hb);
2271 spin_unlock(&hb->lock);
2272}
2273
2274/**
2275 * unqueue_me() - Remove the futex_q from its futex_hash_bucket
2276 * @q: The futex_q to unqueue
2277 *
2278 * The q->lock_ptr must not be held by the caller. A call to unqueue_me() must
2279 * be paired with exactly one earlier call to queue_me().
2280 *
2281 * Return:
2282 * - 1 - if the futex_q was still queued (and we removed unqueued it);
2283 * - 0 - if the futex_q was already removed by the waking thread
2284 */
2285static int unqueue_me(struct futex_q *q)
2286{
2287 spinlock_t *lock_ptr;
2288 int ret = 0;
2289
2290 /* In the common case we don't take the spinlock, which is nice. */
2291retry:
2292 /*
2293 * q->lock_ptr can change between this read and the following spin_lock.
2294 * Use READ_ONCE to forbid the compiler from reloading q->lock_ptr and
2295 * optimizing lock_ptr out of the logic below.
2296 */
2297 lock_ptr = READ_ONCE(q->lock_ptr);
2298 if (lock_ptr != NULL) {
2299 spin_lock(lock_ptr);
2300 /*
2301 * q->lock_ptr can change between reading it and
2302 * spin_lock(), causing us to take the wrong lock. This
2303 * corrects the race condition.
2304 *
2305 * Reasoning goes like this: if we have the wrong lock,
2306 * q->lock_ptr must have changed (maybe several times)
2307 * between reading it and the spin_lock(). It can
2308 * change again after the spin_lock() but only if it was
2309 * already changed before the spin_lock(). It cannot,
2310 * however, change back to the original value. Therefore
2311 * we can detect whether we acquired the correct lock.
2312 */
2313 if (unlikely(lock_ptr != q->lock_ptr)) {
2314 spin_unlock(lock_ptr);
2315 goto retry;
2316 }
2317 __unqueue_futex(q);
2318
2319 BUG_ON(q->pi_state);
2320
2321 spin_unlock(lock_ptr);
2322 ret = 1;
2323 }
2324
2325 drop_futex_key_refs(&q->key);
2326 return ret;
2327}
2328
2329/*
2330 * PI futexes can not be requeued and must remove themself from the
2331 * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
2332 * and dropped here.
2333 */
2334static void unqueue_me_pi(struct futex_q *q)
2335 __releases(q->lock_ptr)
2336{
2337 __unqueue_futex(q);
2338
2339 BUG_ON(!q->pi_state);
2340 put_pi_state(q->pi_state);
2341 q->pi_state = NULL;
2342
2343 spin_unlock(q->lock_ptr);
2344}
2345
2346static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
2347 struct task_struct *argowner)
2348{
2349 struct futex_pi_state *pi_state = q->pi_state;
2350 u32 uval, uninitialized_var(curval), newval;
2351 struct task_struct *oldowner, *newowner;
2352 u32 newtid;
2353 int ret;
2354
2355 lockdep_assert_held(q->lock_ptr);
2356
2357 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
2358
2359 oldowner = pi_state->owner;
2360
2361 /*
2362 * We are here because either:
2363 *
2364 * - we stole the lock and pi_state->owner needs updating to reflect
2365 * that (@argowner == current),
2366 *
2367 * or:
2368 *
2369 * - someone stole our lock and we need to fix things to point to the
2370 * new owner (@argowner == NULL).
2371 *
2372 * Either way, we have to replace the TID in the user space variable.
2373 * This must be atomic as we have to preserve the owner died bit here.
2374 *
2375 * Note: We write the user space value _before_ changing the pi_state
2376 * because we can fault here. Imagine swapped out pages or a fork
2377 * that marked all the anonymous memory readonly for cow.
2378 *
2379 * Modifying pi_state _before_ the user space value would leave the
2380 * pi_state in an inconsistent state when we fault here, because we
2381 * need to drop the locks to handle the fault. This might be observed
2382 * in the PID check in lookup_pi_state.
2383 */
2384retry:
2385 if (!argowner) {
2386 if (oldowner != current) {
2387 /*
2388 * We raced against a concurrent self; things are
2389 * already fixed up. Nothing to do.
2390 */
2391 ret = 0;
2392 goto out_unlock;
2393 }
2394
2395 if (__rt_mutex_futex_trylock(&pi_state->pi_mutex)) {
2396 /* We got the lock after all, nothing to fix. */
2397 ret = 0;
2398 goto out_unlock;
2399 }
2400
2401 /*
2402 * Since we just failed the trylock; there must be an owner.
2403 */
2404 newowner = rt_mutex_owner(&pi_state->pi_mutex);
2405 BUG_ON(!newowner);
2406 } else {
2407 WARN_ON_ONCE(argowner != current);
2408 if (oldowner == current) {
2409 /*
2410 * We raced against a concurrent self; things are
2411 * already fixed up. Nothing to do.
2412 */
2413 ret = 0;
2414 goto out_unlock;
2415 }
2416 newowner = argowner;
2417 }
2418
2419 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
2420 /* Owner died? */
2421 if (!pi_state->owner)
2422 newtid |= FUTEX_OWNER_DIED;
2423
2424 if (get_futex_value_locked(&uval, uaddr))
2425 goto handle_fault;
2426
2427 for (;;) {
2428 newval = (uval & FUTEX_OWNER_DIED) | newtid;
2429
2430 if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval))
2431 goto handle_fault;
2432 if (curval == uval)
2433 break;
2434 uval = curval;
2435 }
2436
2437 /*
2438 * We fixed up user space. Now we need to fix the pi_state
2439 * itself.
2440 */
2441 if (pi_state->owner != NULL) {
2442 raw_spin_lock(&pi_state->owner->pi_lock);
2443 WARN_ON(list_empty(&pi_state->list));
2444 list_del_init(&pi_state->list);
2445 raw_spin_unlock(&pi_state->owner->pi_lock);
2446 }
2447
2448 pi_state->owner = newowner;
2449
2450 raw_spin_lock(&newowner->pi_lock);
2451 WARN_ON(!list_empty(&pi_state->list));
2452 list_add(&pi_state->list, &newowner->pi_state_list);
2453 raw_spin_unlock(&newowner->pi_lock);
2454 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
2455
2456 return 0;
2457
2458 /*
2459 * To handle the page fault we need to drop the locks here. That gives
2460 * the other task (either the highest priority waiter itself or the
2461 * task which stole the rtmutex) the chance to try the fixup of the
2462 * pi_state. So once we are back from handling the fault we need to
2463 * check the pi_state after reacquiring the locks and before trying to
2464 * do another fixup. When the fixup has been done already we simply
2465 * return.
2466 *
2467 * Note: we hold both hb->lock and pi_mutex->wait_lock. We can safely
2468 * drop hb->lock since the caller owns the hb -> futex_q relation.
2469 * Dropping the pi_mutex->wait_lock requires the state revalidate.
2470 */
2471handle_fault:
2472 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
2473 spin_unlock(q->lock_ptr);
2474
2475 ret = fault_in_user_writeable(uaddr);
2476
2477 spin_lock(q->lock_ptr);
2478 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
2479
2480 /*
2481 * Check if someone else fixed it for us:
2482 */
2483 if (pi_state->owner != oldowner) {
2484 ret = 0;
2485 goto out_unlock;
2486 }
2487
2488 if (ret)
2489 goto out_unlock;
2490
2491 goto retry;
2492
2493out_unlock:
2494 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
2495 return ret;
2496}
2497
2498static long futex_wait_restart(struct restart_block *restart);
2499
2500/**
2501 * fixup_owner() - Post lock pi_state and corner case management
2502 * @uaddr: user address of the futex
2503 * @q: futex_q (contains pi_state and access to the rt_mutex)
2504 * @locked: if the attempt to take the rt_mutex succeeded (1) or not (0)
2505 *
2506 * After attempting to lock an rt_mutex, this function is called to cleanup
2507 * the pi_state owner as well as handle race conditions that may allow us to
2508 * acquire the lock. Must be called with the hb lock held.
2509 *
2510 * Return:
2511 * - 1 - success, lock taken;
2512 * - 0 - success, lock not taken;
2513 * - <0 - on error (-EFAULT)
2514 */
2515static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
2516{
2517 int ret = 0;
2518
2519 if (locked) {
2520 /*
2521 * Got the lock. We might not be the anticipated owner if we
2522 * did a lock-steal - fix up the PI-state in that case:
2523 *
2524 * Speculative pi_state->owner read (we don't hold wait_lock);
2525 * since we own the lock pi_state->owner == current is the
2526 * stable state, anything else needs more attention.
2527 */
2528 if (q->pi_state->owner != current)
2529 ret = fixup_pi_state_owner(uaddr, q, current);
2530 goto out;
2531 }
2532
2533 /*
2534 * If we didn't get the lock; check if anybody stole it from us. In
2535 * that case, we need to fix up the uval to point to them instead of
2536 * us, otherwise bad things happen. [10]
2537 *
2538 * Another speculative read; pi_state->owner == current is unstable
2539 * but needs our attention.
2540 */
2541 if (q->pi_state->owner == current) {
2542 ret = fixup_pi_state_owner(uaddr, q, NULL);
2543 goto out;
2544 }
2545
2546 /*
2547 * Paranoia check. If we did not take the lock, then we should not be
2548 * the owner of the rt_mutex.
2549 */
2550 if (rt_mutex_owner(&q->pi_state->pi_mutex) == current) {
2551 printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "
2552 "pi-state %p\n", ret,
2553 q->pi_state->pi_mutex.owner,
2554 q->pi_state->owner);
2555 }
2556
2557out:
2558 return ret ? ret : locked;
2559}
2560
2561/**
2562 * futex_wait_queue_me() - queue_me() and wait for wakeup, timeout, or signal
2563 * @hb: the futex hash bucket, must be locked by the caller
2564 * @q: the futex_q to queue up on
2565 * @timeout: the prepared hrtimer_sleeper, or null for no timeout
2566 */
2567static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
2568 struct hrtimer_sleeper *timeout)
2569{
2570 /*
2571 * The task state is guaranteed to be set before another task can
2572 * wake it. set_current_state() is implemented using smp_store_mb() and
2573 * queue_me() calls spin_unlock() upon completion, both serializing
2574 * access to the hash list and forcing another memory barrier.
2575 */
2576 set_current_state(TASK_INTERRUPTIBLE);
2577 queue_me(q, hb);
2578
2579 /* Arm the timer */
2580 if (timeout)
2581 hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
2582
2583 /*
2584 * If we have been removed from the hash list, then another task
2585 * has tried to wake us, and we can skip the call to schedule().
2586 */
2587 if (likely(!plist_node_empty(&q->list))) {
2588 /*
2589 * If the timer has already expired, current will already be
2590 * flagged for rescheduling. Only call schedule if there
2591 * is no timeout, or if it has yet to expire.
2592 */
2593 if (!timeout || timeout->task)
2594 freezable_schedule();
2595 }
2596 __set_current_state(TASK_RUNNING);
2597}
2598
2599/**
2600 * futex_wait_setup() - Prepare to wait on a futex
2601 * @uaddr: the futex userspace address
2602 * @val: the expected value
2603 * @flags: futex flags (FLAGS_SHARED, etc.)
2604 * @q: the associated futex_q
2605 * @hb: storage for hash_bucket pointer to be returned to caller
2606 *
2607 * Setup the futex_q and locate the hash_bucket. Get the futex value and
2608 * compare it with the expected value. Handle atomic faults internally.
2609 * Return with the hb lock held and a q.key reference on success, and unlocked
2610 * with no q.key reference on failure.
2611 *
2612 * Return:
2613 * - 0 - uaddr contains val and hb has been locked;
2614 * - <1 - -EFAULT or -EWOULDBLOCK (uaddr does not contain val) and hb is unlocked
2615 */
2616static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
2617 struct futex_q *q, struct futex_hash_bucket **hb)
2618{
2619 u32 uval;
2620 int ret;
2621
2622 /*
2623 * Access the page AFTER the hash-bucket is locked.
2624 * Order is important:
2625 *
2626 * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
2627 * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); }
2628 *
2629 * The basic logical guarantee of a futex is that it blocks ONLY
2630 * if cond(var) is known to be true at the time of blocking, for
2631 * any cond. If we locked the hash-bucket after testing *uaddr, that
2632 * would open a race condition where we could block indefinitely with
2633 * cond(var) false, which would violate the guarantee.
2634 *
2635 * On the other hand, we insert q and release the hash-bucket only
2636 * after testing *uaddr. This guarantees that futex_wait() will NOT
2637 * absorb a wakeup if *uaddr does not match the desired values
2638 * while the syscall executes.
2639 */
2640retry:
2641 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key, FUTEX_READ);
2642 if (unlikely(ret != 0))
2643 return ret;
2644
2645retry_private:
2646 *hb = queue_lock(q);
2647
2648 ret = get_futex_value_locked(&uval, uaddr);
2649
2650 if (ret) {
2651 queue_unlock(*hb);
2652
2653 ret = get_user(uval, uaddr);
2654 if (ret)
2655 goto out;
2656
2657 if (!(flags & FLAGS_SHARED))
2658 goto retry_private;
2659
2660 put_futex_key(&q->key);
2661 goto retry;
2662 }
2663
2664 if (uval != val) {
2665 queue_unlock(*hb);
2666 ret = -EWOULDBLOCK;
2667 }
2668
2669out:
2670 if (ret)
2671 put_futex_key(&q->key);
2672 return ret;
2673}
2674
2675static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
2676 ktime_t *abs_time, u32 bitset)
2677{
2678 struct hrtimer_sleeper timeout, *to = NULL;
2679 struct restart_block *restart;
2680 struct futex_hash_bucket *hb;
2681 struct futex_q q = futex_q_init;
2682 int ret;
2683
2684 if (!bitset)
2685 return -EINVAL;
2686 q.bitset = bitset;
2687
2688 if (abs_time) {
2689 to = &timeout;
2690
2691 hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
2692 CLOCK_REALTIME : CLOCK_MONOTONIC,
2693 HRTIMER_MODE_ABS);
2694 hrtimer_init_sleeper(to, current);
2695 hrtimer_set_expires_range_ns(&to->timer, *abs_time,
2696 current->timer_slack_ns);
2697 }
2698
2699retry:
2700 /*
2701 * Prepare to wait on uaddr. On success, holds hb lock and increments
2702 * q.key refs.
2703 */
2704 ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
2705 if (ret)
2706 goto out;
2707
2708 /* queue_me and wait for wakeup, timeout, or a signal. */
2709 futex_wait_queue_me(hb, &q, to);
2710
2711 /* If we were woken (and unqueued), we succeeded, whatever. */
2712 ret = 0;
2713 /* unqueue_me() drops q.key ref */
2714 if (!unqueue_me(&q))
2715 goto out;
2716 ret = -ETIMEDOUT;
2717 if (to && !to->task)
2718 goto out;
2719
2720 /*
2721 * We expect signal_pending(current), but we might be the
2722 * victim of a spurious wakeup as well.
2723 */
2724 if (!signal_pending(current))
2725 goto retry;
2726
2727 ret = -ERESTARTSYS;
2728 if (!abs_time)
2729 goto out;
2730
2731 restart = &current->restart_block;
2732 restart->fn = futex_wait_restart;
2733 restart->futex.uaddr = uaddr;
2734 restart->futex.val = val;
2735 restart->futex.time = *abs_time;
2736 restart->futex.bitset = bitset;
2737 restart->futex.flags = flags | FLAGS_HAS_TIMEOUT;
2738
2739 ret = -ERESTART_RESTARTBLOCK;
2740
2741out:
2742 if (to) {
2743 hrtimer_cancel(&to->timer);
2744 destroy_hrtimer_on_stack(&to->timer);
2745 }
2746 return ret;
2747}
2748
2749
2750static long futex_wait_restart(struct restart_block *restart)
2751{
2752 u32 __user *uaddr = restart->futex.uaddr;
2753 ktime_t t, *tp = NULL;
2754
2755 if (restart->futex.flags & FLAGS_HAS_TIMEOUT) {
2756 t = restart->futex.time;
2757 tp = &t;
2758 }
2759 restart->fn = do_no_restart_syscall;
2760
2761 return (long)futex_wait(uaddr, restart->futex.flags,
2762 restart->futex.val, tp, restart->futex.bitset);
2763}
2764
2765
2766/*
2767 * Userspace tried a 0 -> TID atomic transition of the futex value
2768 * and failed. The kernel side here does the whole locking operation:
2769 * if there are waiters then it will block as a consequence of relying
2770 * on rt-mutexes, it does PI, etc. (Due to races the kernel might see
2771 * a 0 value of the futex too.).
2772 *
2773 * Also serves as futex trylock_pi()'ing, and due semantics.
2774 */
2775static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
2776 ktime_t *time, int trylock)
2777{
2778 struct hrtimer_sleeper timeout, *to = NULL;
2779 struct futex_pi_state *pi_state = NULL;
2780 struct rt_mutex_waiter rt_waiter;
2781 struct futex_hash_bucket *hb;
2782 struct futex_q q = futex_q_init;
2783 int res, ret;
2784
2785 if (!IS_ENABLED(CONFIG_FUTEX_PI))
2786 return -ENOSYS;
2787
2788 if (refill_pi_state_cache())
2789 return -ENOMEM;
2790
2791 if (time) {
2792 to = &timeout;
2793 hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
2794 HRTIMER_MODE_ABS);
2795 hrtimer_init_sleeper(to, current);
2796 hrtimer_set_expires(&to->timer, *time);
2797 }
2798
2799retry:
2800 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, FUTEX_WRITE);
2801 if (unlikely(ret != 0))
2802 goto out;
2803
2804retry_private:
2805 hb = queue_lock(&q);
2806
2807 ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &q.pi_state, current, 0);
2808 if (unlikely(ret)) {
2809 /*
2810 * Atomic work succeeded and we got the lock,
2811 * or failed. Either way, we do _not_ block.
2812 */
2813 switch (ret) {
2814 case 1:
2815 /* We got the lock. */
2816 ret = 0;
2817 goto out_unlock_put_key;
2818 case -EFAULT:
2819 goto uaddr_faulted;
2820 case -EAGAIN:
2821 /*
2822 * Two reasons for this:
2823 * - Task is exiting and we just wait for the
2824 * exit to complete.
2825 * - The user space value changed.
2826 */
2827 queue_unlock(hb);
2828 put_futex_key(&q.key);
2829 cond_resched();
2830 goto retry;
2831 default:
2832 goto out_unlock_put_key;
2833 }
2834 }
2835
2836 WARN_ON(!q.pi_state);
2837
2838 /*
2839 * Only actually queue now that the atomic ops are done:
2840 */
2841 __queue_me(&q, hb);
2842
2843 if (trylock) {
2844 ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
2845 /* Fixup the trylock return value: */
2846 ret = ret ? 0 : -EWOULDBLOCK;
2847 goto no_block;
2848 }
2849
2850 rt_mutex_init_waiter(&rt_waiter);
2851
2852 /*
2853 * On PREEMPT_RT_FULL, when hb->lock becomes an rt_mutex, we must not
2854 * hold it while doing rt_mutex_start_proxy(), because then it will
2855 * include hb->lock in the blocking chain, even through we'll not in
2856 * fact hold it while blocking. This will lead it to report -EDEADLK
2857 * and BUG when futex_unlock_pi() interleaves with this.
2858 *
2859 * Therefore acquire wait_lock while holding hb->lock, but drop the
2860 * latter before calling __rt_mutex_start_proxy_lock(). This
2861 * interleaves with futex_unlock_pi() -- which does a similar lock
2862 * handoff -- such that the latter can observe the futex_q::pi_state
2863 * before __rt_mutex_start_proxy_lock() is done.
2864 */
2865 raw_spin_lock_irq(&q.pi_state->pi_mutex.wait_lock);
2866 spin_unlock(q.lock_ptr);
2867 /*
2868 * __rt_mutex_start_proxy_lock() unconditionally enqueues the @rt_waiter
2869 * such that futex_unlock_pi() is guaranteed to observe the waiter when
2870 * it sees the futex_q::pi_state.
2871 */
2872 ret = __rt_mutex_start_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter, current);
2873 raw_spin_unlock_irq(&q.pi_state->pi_mutex.wait_lock);
2874
2875 if (ret) {
2876 if (ret == 1)
2877 ret = 0;
2878 goto cleanup;
2879 }
2880
2881 if (unlikely(to))
2882 hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
2883
2884 ret = rt_mutex_wait_proxy_lock(&q.pi_state->pi_mutex, to, &rt_waiter);
2885
2886cleanup:
2887 spin_lock(q.lock_ptr);
2888 /*
2889 * If we failed to acquire the lock (deadlock/signal/timeout), we must
2890 * first acquire the hb->lock before removing the lock from the
2891 * rt_mutex waitqueue, such that we can keep the hb and rt_mutex wait
2892 * lists consistent.
2893 *
2894 * In particular; it is important that futex_unlock_pi() can not
2895 * observe this inconsistency.
2896 */
2897 if (ret && !rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter))
2898 ret = 0;
2899
2900no_block:
2901 /*
2902 * Fixup the pi_state owner and possibly acquire the lock if we
2903 * haven't already.
2904 */
2905 res = fixup_owner(uaddr, &q, !ret);
2906 /*
2907 * If fixup_owner() returned an error, proprogate that. If it acquired
2908 * the lock, clear our -ETIMEDOUT or -EINTR.
2909 */
2910 if (res)
2911 ret = (res < 0) ? res : 0;
2912
2913 /*
2914 * If fixup_owner() faulted and was unable to handle the fault, unlock
2915 * it and return the fault to userspace.
2916 */
2917 if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current)) {
2918 pi_state = q.pi_state;
2919 get_pi_state(pi_state);
2920 }
2921
2922 /* Unqueue and drop the lock */
2923 unqueue_me_pi(&q);
2924
2925 if (pi_state) {
2926 rt_mutex_futex_unlock(&pi_state->pi_mutex);
2927 put_pi_state(pi_state);
2928 }
2929
2930 goto out_put_key;
2931
2932out_unlock_put_key:
2933 queue_unlock(hb);
2934
2935out_put_key:
2936 put_futex_key(&q.key);
2937out:
2938 if (to) {
2939 hrtimer_cancel(&to->timer);
2940 destroy_hrtimer_on_stack(&to->timer);
2941 }
2942 return ret != -EINTR ? ret : -ERESTARTNOINTR;
2943
2944uaddr_faulted:
2945 queue_unlock(hb);
2946
2947 ret = fault_in_user_writeable(uaddr);
2948 if (ret)
2949 goto out_put_key;
2950
2951 if (!(flags & FLAGS_SHARED))
2952 goto retry_private;
2953
2954 put_futex_key(&q.key);
2955 goto retry;
2956}
2957
2958/*
2959 * Userspace attempted a TID -> 0 atomic transition, and failed.
2960 * This is the in-kernel slowpath: we look up the PI state (if any),
2961 * and do the rt-mutex unlock.
2962 */
2963static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
2964{
2965 u32 uninitialized_var(curval), uval, vpid = task_pid_vnr(current);
2966 union futex_key key = FUTEX_KEY_INIT;
2967 struct futex_hash_bucket *hb;
2968 struct futex_q *top_waiter;
2969 int ret;
2970
2971 if (!IS_ENABLED(CONFIG_FUTEX_PI))
2972 return -ENOSYS;
2973
2974retry:
2975 if (get_user(uval, uaddr))
2976 return -EFAULT;
2977 /*
2978 * We release only a lock we actually own:
2979 */
2980 if ((uval & FUTEX_TID_MASK) != vpid)
2981 return -EPERM;
2982
2983 ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, FUTEX_WRITE);
2984 if (ret)
2985 return ret;
2986
2987 hb = hash_futex(&key);
2988 spin_lock(&hb->lock);
2989
2990 /*
2991 * Check waiters first. We do not trust user space values at
2992 * all and we at least want to know if user space fiddled
2993 * with the futex value instead of blindly unlocking.
2994 */
2995 top_waiter = futex_top_waiter(hb, &key);
2996 if (top_waiter) {
2997 struct futex_pi_state *pi_state = top_waiter->pi_state;
2998
2999 ret = -EINVAL;
3000 if (!pi_state)
3001 goto out_unlock;
3002
3003 /*
3004 * If current does not own the pi_state then the futex is
3005 * inconsistent and user space fiddled with the futex value.
3006 */
3007 if (pi_state->owner != current)
3008 goto out_unlock;
3009
3010 get_pi_state(pi_state);
3011 /*
3012 * By taking wait_lock while still holding hb->lock, we ensure
3013 * there is no point where we hold neither; and therefore
3014 * wake_futex_pi() must observe a state consistent with what we
3015 * observed.
3016 *
3017 * In particular; this forces __rt_mutex_start_proxy() to
3018 * complete such that we're guaranteed to observe the
3019 * rt_waiter. Also see the WARN in wake_futex_pi().
3020 */
3021 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
3022 spin_unlock(&hb->lock);
3023
3024 /* drops pi_state->pi_mutex.wait_lock */
3025 ret = wake_futex_pi(uaddr, uval, pi_state);
3026
3027 put_pi_state(pi_state);
3028
3029 /*
3030 * Success, we're done! No tricky corner cases.
3031 */
3032 if (!ret)
3033 goto out_putkey;
3034 /*
3035 * The atomic access to the futex value generated a
3036 * pagefault, so retry the user-access and the wakeup:
3037 */
3038 if (ret == -EFAULT)
3039 goto pi_faulted;
3040 /*
3041 * A unconditional UNLOCK_PI op raced against a waiter
3042 * setting the FUTEX_WAITERS bit. Try again.
3043 */
3044 if (ret == -EAGAIN) {
3045 put_futex_key(&key);
3046 goto retry;
3047 }
3048 /*
3049 * wake_futex_pi has detected invalid state. Tell user
3050 * space.
3051 */
3052 goto out_putkey;
3053 }
3054
3055 /*
3056 * We have no kernel internal state, i.e. no waiters in the
3057 * kernel. Waiters which are about to queue themselves are stuck
3058 * on hb->lock. So we can safely ignore them. We do neither
3059 * preserve the WAITERS bit not the OWNER_DIED one. We are the
3060 * owner.
3061 */
3062 if (cmpxchg_futex_value_locked(&curval, uaddr, uval, 0)) {
3063 spin_unlock(&hb->lock);
3064 goto pi_faulted;
3065 }
3066
3067 /*
3068 * If uval has changed, let user space handle it.
3069 */
3070 ret = (curval == uval) ? 0 : -EAGAIN;
3071
3072out_unlock:
3073 spin_unlock(&hb->lock);
3074out_putkey:
3075 put_futex_key(&key);
3076 return ret;
3077
3078pi_faulted:
3079 put_futex_key(&key);
3080
3081 ret = fault_in_user_writeable(uaddr);
3082 if (!ret)
3083 goto retry;
3084
3085 return ret;
3086}
3087
3088/**
3089 * handle_early_requeue_pi_wakeup() - Detect early wakeup on the initial futex
3090 * @hb: the hash_bucket futex_q was original enqueued on
3091 * @q: the futex_q woken while waiting to be requeued
3092 * @key2: the futex_key of the requeue target futex
3093 * @timeout: the timeout associated with the wait (NULL if none)
3094 *
3095 * Detect if the task was woken on the initial futex as opposed to the requeue
3096 * target futex. If so, determine if it was a timeout or a signal that caused
3097 * the wakeup and return the appropriate error code to the caller. Must be
3098 * called with the hb lock held.
3099 *
3100 * Return:
3101 * - 0 = no early wakeup detected;
3102 * - <0 = -ETIMEDOUT or -ERESTARTNOINTR
3103 */
3104static inline
3105int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb,
3106 struct futex_q *q, union futex_key *key2,
3107 struct hrtimer_sleeper *timeout)
3108{
3109 int ret = 0;
3110
3111 /*
3112 * With the hb lock held, we avoid races while we process the wakeup.
3113 * We only need to hold hb (and not hb2) to ensure atomicity as the
3114 * wakeup code can't change q.key from uaddr to uaddr2 if we hold hb.
3115 * It can't be requeued from uaddr2 to something else since we don't
3116 * support a PI aware source futex for requeue.
3117 */
3118 if (!match_futex(&q->key, key2)) {
3119 WARN_ON(q->lock_ptr && (&hb->lock != q->lock_ptr));
3120 /*
3121 * We were woken prior to requeue by a timeout or a signal.
3122 * Unqueue the futex_q and determine which it was.
3123 */
3124 plist_del(&q->list, &hb->chain);
3125 hb_waiters_dec(hb);
3126
3127 /* Handle spurious wakeups gracefully */
3128 ret = -EWOULDBLOCK;
3129 if (timeout && !timeout->task)
3130 ret = -ETIMEDOUT;
3131 else if (signal_pending(current))
3132 ret = -ERESTARTNOINTR;
3133 }
3134 return ret;
3135}
3136
3137/**
3138 * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2
3139 * @uaddr: the futex we initially wait on (non-pi)
3140 * @flags: futex flags (FLAGS_SHARED, FLAGS_CLOCKRT, etc.), they must be
3141 * the same type, no requeueing from private to shared, etc.
3142 * @val: the expected value of uaddr
3143 * @abs_time: absolute timeout
3144 * @bitset: 32 bit wakeup bitset set by userspace, defaults to all
3145 * @uaddr2: the pi futex we will take prior to returning to user-space
3146 *
3147 * The caller will wait on uaddr and will be requeued by futex_requeue() to
3148 * uaddr2 which must be PI aware and unique from uaddr. Normal wakeup will wake
3149 * on uaddr2 and complete the acquisition of the rt_mutex prior to returning to
3150 * userspace. This ensures the rt_mutex maintains an owner when it has waiters;
3151 * without one, the pi logic would not know which task to boost/deboost, if
3152 * there was a need to.
3153 *
3154 * We call schedule in futex_wait_queue_me() when we enqueue and return there
3155 * via the following--
3156 * 1) wakeup on uaddr2 after an atomic lock acquisition by futex_requeue()
3157 * 2) wakeup on uaddr2 after a requeue
3158 * 3) signal
3159 * 4) timeout
3160 *
3161 * If 3, cleanup and return -ERESTARTNOINTR.
3162 *
3163 * If 2, we may then block on trying to take the rt_mutex and return via:
3164 * 5) successful lock
3165 * 6) signal
3166 * 7) timeout
3167 * 8) other lock acquisition failure
3168 *
3169 * If 6, return -EWOULDBLOCK (restarting the syscall would do the same).
3170 *
3171 * If 4 or 7, we cleanup and return with -ETIMEDOUT.
3172 *
3173 * Return:
3174 * - 0 - On success;
3175 * - <0 - On error
3176 */
3177static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
3178 u32 val, ktime_t *abs_time, u32 bitset,
3179 u32 __user *uaddr2)
3180{
3181 struct hrtimer_sleeper timeout, *to = NULL;
3182 struct futex_pi_state *pi_state = NULL;
3183 struct rt_mutex_waiter rt_waiter;
3184 struct futex_hash_bucket *hb;
3185 union futex_key key2 = FUTEX_KEY_INIT;
3186 struct futex_q q = futex_q_init;
3187 int res, ret;
3188
3189 if (!IS_ENABLED(CONFIG_FUTEX_PI))
3190 return -ENOSYS;
3191
3192 if (uaddr == uaddr2)
3193 return -EINVAL;
3194
3195 if (!bitset)
3196 return -EINVAL;
3197
3198 if (abs_time) {
3199 to = &timeout;
3200 hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
3201 CLOCK_REALTIME : CLOCK_MONOTONIC,
3202 HRTIMER_MODE_ABS);
3203 hrtimer_init_sleeper(to, current);
3204 hrtimer_set_expires_range_ns(&to->timer, *abs_time,
3205 current->timer_slack_ns);
3206 }
3207
3208 /*
3209 * The waiter is allocated on our stack, manipulated by the requeue
3210 * code while we sleep on uaddr.
3211 */
3212 rt_mutex_init_waiter(&rt_waiter);
3213
3214 ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, FUTEX_WRITE);
3215 if (unlikely(ret != 0))
3216 goto out;
3217
3218 q.bitset = bitset;
3219 q.rt_waiter = &rt_waiter;
3220 q.requeue_pi_key = &key2;
3221
3222 /*
3223 * Prepare to wait on uaddr. On success, increments q.key (key1) ref
3224 * count.
3225 */
3226 ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
3227 if (ret)
3228 goto out_key2;
3229
3230 /*
3231 * The check above which compares uaddrs is not sufficient for
3232 * shared futexes. We need to compare the keys:
3233 */
3234 if (match_futex(&q.key, &key2)) {
3235 queue_unlock(hb);
3236 ret = -EINVAL;
3237 goto out_put_keys;
3238 }
3239
3240 /* Queue the futex_q, drop the hb lock, wait for wakeup. */
3241 futex_wait_queue_me(hb, &q, to);
3242
3243 spin_lock(&hb->lock);
3244 ret = handle_early_requeue_pi_wakeup(hb, &q, &key2, to);
3245 spin_unlock(&hb->lock);
3246 if (ret)
3247 goto out_put_keys;
3248
3249 /*
3250 * In order for us to be here, we know our q.key == key2, and since
3251 * we took the hb->lock above, we also know that futex_requeue() has
3252 * completed and we no longer have to concern ourselves with a wakeup
3253 * race with the atomic proxy lock acquisition by the requeue code. The
3254 * futex_requeue dropped our key1 reference and incremented our key2
3255 * reference count.
3256 */
3257
3258 /* Check if the requeue code acquired the second futex for us. */
3259 if (!q.rt_waiter) {
3260 /*
3261 * Got the lock. We might not be the anticipated owner if we
3262 * did a lock-steal - fix up the PI-state in that case.
3263 */
3264 if (q.pi_state && (q.pi_state->owner != current)) {
3265 spin_lock(q.lock_ptr);
3266 ret = fixup_pi_state_owner(uaddr2, &q, current);
3267 if (ret && rt_mutex_owner(&q.pi_state->pi_mutex) == current) {
3268 pi_state = q.pi_state;
3269 get_pi_state(pi_state);
3270 }
3271 /*
3272 * Drop the reference to the pi state which
3273 * the requeue_pi() code acquired for us.
3274 */
3275 put_pi_state(q.pi_state);
3276 spin_unlock(q.lock_ptr);
3277 }
3278 } else {
3279 struct rt_mutex *pi_mutex;
3280
3281 /*
3282 * We have been woken up by futex_unlock_pi(), a timeout, or a
3283 * signal. futex_unlock_pi() will not destroy the lock_ptr nor
3284 * the pi_state.
3285 */
3286 WARN_ON(!q.pi_state);
3287 pi_mutex = &q.pi_state->pi_mutex;
3288 ret = rt_mutex_wait_proxy_lock(pi_mutex, to, &rt_waiter);
3289
3290 spin_lock(q.lock_ptr);
3291 if (ret && !rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter))
3292 ret = 0;
3293
3294 debug_rt_mutex_free_waiter(&rt_waiter);
3295 /*
3296 * Fixup the pi_state owner and possibly acquire the lock if we
3297 * haven't already.
3298 */
3299 res = fixup_owner(uaddr2, &q, !ret);
3300 /*
3301 * If fixup_owner() returned an error, proprogate that. If it
3302 * acquired the lock, clear -ETIMEDOUT or -EINTR.
3303 */
3304 if (res)
3305 ret = (res < 0) ? res : 0;
3306
3307 /*
3308 * If fixup_pi_state_owner() faulted and was unable to handle
3309 * the fault, unlock the rt_mutex and return the fault to
3310 * userspace.
3311 */
3312 if (ret && rt_mutex_owner(&q.pi_state->pi_mutex) == current) {
3313 pi_state = q.pi_state;
3314 get_pi_state(pi_state);
3315 }
3316
3317 /* Unqueue and drop the lock. */
3318 unqueue_me_pi(&q);
3319 }
3320
3321 if (pi_state) {
3322 rt_mutex_futex_unlock(&pi_state->pi_mutex);
3323 put_pi_state(pi_state);
3324 }
3325
3326 if (ret == -EINTR) {
3327 /*
3328 * We've already been requeued, but cannot restart by calling
3329 * futex_lock_pi() directly. We could restart this syscall, but
3330 * it would detect that the user space "val" changed and return
3331 * -EWOULDBLOCK. Save the overhead of the restart and return
3332 * -EWOULDBLOCK directly.
3333 */
3334 ret = -EWOULDBLOCK;
3335 }
3336
3337out_put_keys:
3338 put_futex_key(&q.key);
3339out_key2:
3340 put_futex_key(&key2);
3341
3342out:
3343 if (to) {
3344 hrtimer_cancel(&to->timer);
3345 destroy_hrtimer_on_stack(&to->timer);
3346 }
3347 return ret;
3348}
3349
3350/*
3351 * Support for robust futexes: the kernel cleans up held futexes at
3352 * thread exit time.
3353 *
3354 * Implementation: user-space maintains a per-thread list of locks it
3355 * is holding. Upon do_exit(), the kernel carefully walks this list,
3356 * and marks all locks that are owned by this thread with the
3357 * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
3358 * always manipulated with the lock held, so the list is private and
3359 * per-thread. Userspace also maintains a per-thread 'list_op_pending'
3360 * field, to allow the kernel to clean up if the thread dies after
3361 * acquiring the lock, but just before it could have added itself to
3362 * the list. There can only be one such pending lock.
3363 */
3364
3365/**
3366 * sys_set_robust_list() - Set the robust-futex list head of a task
3367 * @head: pointer to the list-head
3368 * @len: length of the list-head, as userspace expects
3369 */
3370SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head,
3371 size_t, len)
3372{
3373 if (!futex_cmpxchg_enabled)
3374 return -ENOSYS;
3375 /*
3376 * The kernel knows only one size for now:
3377 */
3378 if (unlikely(len != sizeof(*head)))
3379 return -EINVAL;
3380
3381 current->robust_list = head;
3382
3383 return 0;
3384}
3385
3386/**
3387 * sys_get_robust_list() - Get the robust-futex list head of a task
3388 * @pid: pid of the process [zero for current task]
3389 * @head_ptr: pointer to a list-head pointer, the kernel fills it in
3390 * @len_ptr: pointer to a length field, the kernel fills in the header size
3391 */
3392SYSCALL_DEFINE3(get_robust_list, int, pid,
3393 struct robust_list_head __user * __user *, head_ptr,
3394 size_t __user *, len_ptr)
3395{
3396 struct robust_list_head __user *head;
3397 unsigned long ret;
3398 struct task_struct *p;
3399
3400 if (!futex_cmpxchg_enabled)
3401 return -ENOSYS;
3402
3403 rcu_read_lock();
3404
3405 ret = -ESRCH;
3406 if (!pid)
3407 p = current;
3408 else {
3409 p = find_task_by_vpid(pid);
3410 if (!p)
3411 goto err_unlock;
3412 }
3413
3414 ret = -EPERM;
3415 if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS))
3416 goto err_unlock;
3417
3418 head = p->robust_list;
3419 rcu_read_unlock();
3420
3421 if (put_user(sizeof(*head), len_ptr))
3422 return -EFAULT;
3423 return put_user(head, head_ptr);
3424
3425err_unlock:
3426 rcu_read_unlock();
3427
3428 return ret;
3429}
3430
3431/*
3432 * Process a futex-list entry, check whether it's owned by the
3433 * dying task, and do notification if so:
3434 */
3435static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
3436{
3437 u32 uval, uninitialized_var(nval), mval;
3438
3439 /* Futex address must be 32bit aligned */
3440 if ((((unsigned long)uaddr) % sizeof(*uaddr)) != 0)
3441 return -1;
3442
3443retry:
3444 if (get_user(uval, uaddr))
3445 return -1;
3446
3447 if ((uval & FUTEX_TID_MASK) == task_pid_vnr(curr)) {
3448 /*
3449 * Ok, this dying thread is truly holding a futex
3450 * of interest. Set the OWNER_DIED bit atomically
3451 * via cmpxchg, and if the value had FUTEX_WAITERS
3452 * set, wake up a waiter (if any). (We have to do a
3453 * futex_wake() even if OWNER_DIED is already set -
3454 * to handle the rare but possible case of recursive
3455 * thread-death.) The rest of the cleanup is done in
3456 * userspace.
3457 */
3458 mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
3459 /*
3460 * We are not holding a lock here, but we want to have
3461 * the pagefault_disable/enable() protection because
3462 * we want to handle the fault gracefully. If the
3463 * access fails we try to fault in the futex with R/W
3464 * verification via get_user_pages. get_user() above
3465 * does not guarantee R/W access. If that fails we
3466 * give up and leave the futex locked.
3467 */
3468 if (cmpxchg_futex_value_locked(&nval, uaddr, uval, mval)) {
3469 if (fault_in_user_writeable(uaddr))
3470 return -1;
3471 goto retry;
3472 }
3473 if (nval != uval)
3474 goto retry;
3475
3476 /*
3477 * Wake robust non-PI futexes here. The wakeup of
3478 * PI futexes happens in exit_pi_state():
3479 */
3480 if (!pi && (uval & FUTEX_WAITERS))
3481 futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
3482 }
3483 return 0;
3484}
3485
3486/*
3487 * Fetch a robust-list pointer. Bit 0 signals PI futexes:
3488 */
3489static inline int fetch_robust_entry(struct robust_list __user **entry,
3490 struct robust_list __user * __user *head,
3491 unsigned int *pi)
3492{
3493 unsigned long uentry;
3494
3495 if (get_user(uentry, (unsigned long __user *)head))
3496 return -EFAULT;
3497
3498 *entry = (void __user *)(uentry & ~1UL);
3499 *pi = uentry & 1;
3500
3501 return 0;
3502}
3503
3504/*
3505 * Walk curr->robust_list (very carefully, it's a userspace list!)
3506 * and mark any locks found there dead, and notify any waiters.
3507 *
3508 * We silently return on any sign of list-walking problem.
3509 */
3510void exit_robust_list(struct task_struct *curr)
3511{
3512 struct robust_list_head __user *head = curr->robust_list;
3513 struct robust_list __user *entry, *next_entry, *pending;
3514 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
3515 unsigned int uninitialized_var(next_pi);
3516 unsigned long futex_offset;
3517 int rc;
3518
3519 if (!futex_cmpxchg_enabled)
3520 return;
3521
3522 /*
3523 * Fetch the list head (which was registered earlier, via
3524 * sys_set_robust_list()):
3525 */
3526 if (fetch_robust_entry(&entry, &head->list.next, &pi))
3527 return;
3528 /*
3529 * Fetch the relative futex offset:
3530 */
3531 if (get_user(futex_offset, &head->futex_offset))
3532 return;
3533 /*
3534 * Fetch any possibly pending lock-add first, and handle it
3535 * if it exists:
3536 */
3537 if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
3538 return;
3539
3540 next_entry = NULL; /* avoid warning with gcc */
3541 while (entry != &head->list) {
3542 /*
3543 * Fetch the next entry in the list before calling
3544 * handle_futex_death:
3545 */
3546 rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
3547 /*
3548 * A pending lock might already be on the list, so
3549 * don't process it twice:
3550 */
3551 if (entry != pending)
3552 if (handle_futex_death((void __user *)entry + futex_offset,
3553 curr, pi))
3554 return;
3555 if (rc)
3556 return;
3557 entry = next_entry;
3558 pi = next_pi;
3559 /*
3560 * Avoid excessively long or circular lists:
3561 */
3562 if (!--limit)
3563 break;
3564
3565 cond_resched();
3566 }
3567
3568 if (pending)
3569 handle_futex_death((void __user *)pending + futex_offset,
3570 curr, pip);
3571}
3572
3573long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
3574 u32 __user *uaddr2, u32 val2, u32 val3)
3575{
3576 int cmd = op & FUTEX_CMD_MASK;
3577 unsigned int flags = 0;
3578
3579 if (!(op & FUTEX_PRIVATE_FLAG))
3580 flags |= FLAGS_SHARED;
3581
3582 if (op & FUTEX_CLOCK_REALTIME) {
3583 flags |= FLAGS_CLOCKRT;
3584 if (cmd != FUTEX_WAIT && cmd != FUTEX_WAIT_BITSET && \
3585 cmd != FUTEX_WAIT_REQUEUE_PI)
3586 return -ENOSYS;
3587 }
3588
3589 switch (cmd) {
3590 case FUTEX_LOCK_PI:
3591 case FUTEX_UNLOCK_PI:
3592 case FUTEX_TRYLOCK_PI:
3593 case FUTEX_WAIT_REQUEUE_PI:
3594 case FUTEX_CMP_REQUEUE_PI:
3595 if (!futex_cmpxchg_enabled)
3596 return -ENOSYS;
3597 }
3598
3599 switch (cmd) {
3600 case FUTEX_WAIT:
3601 val3 = FUTEX_BITSET_MATCH_ANY;
3602 /* fall through */
3603 case FUTEX_WAIT_BITSET:
3604 return futex_wait(uaddr, flags, val, timeout, val3);
3605 case FUTEX_WAKE:
3606 val3 = FUTEX_BITSET_MATCH_ANY;
3607 /* fall through */
3608 case FUTEX_WAKE_BITSET:
3609 return futex_wake(uaddr, flags, val, val3);
3610 case FUTEX_REQUEUE:
3611 return futex_requeue(uaddr, flags, uaddr2, val, val2, NULL, 0);
3612 case FUTEX_CMP_REQUEUE:
3613 return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 0);
3614 case FUTEX_WAKE_OP:
3615 return futex_wake_op(uaddr, flags, uaddr2, val, val2, val3);
3616 case FUTEX_LOCK_PI:
3617 return futex_lock_pi(uaddr, flags, timeout, 0);
3618 case FUTEX_UNLOCK_PI:
3619 return futex_unlock_pi(uaddr, flags);
3620 case FUTEX_TRYLOCK_PI:
3621 return futex_lock_pi(uaddr, flags, NULL, 1);
3622 case FUTEX_WAIT_REQUEUE_PI:
3623 val3 = FUTEX_BITSET_MATCH_ANY;
3624 return futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
3625 uaddr2);
3626 case FUTEX_CMP_REQUEUE_PI:
3627 return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
3628 }
3629 return -ENOSYS;
3630}
3631
3632
3633SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
3634 struct __kernel_timespec __user *, utime, u32 __user *, uaddr2,
3635 u32, val3)
3636{
3637 struct timespec64 ts;
3638 ktime_t t, *tp = NULL;
3639 u32 val2 = 0;
3640 int cmd = op & FUTEX_CMD_MASK;
3641
3642 if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
3643 cmd == FUTEX_WAIT_BITSET ||
3644 cmd == FUTEX_WAIT_REQUEUE_PI)) {
3645 if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
3646 return -EFAULT;
3647 if (get_timespec64(&ts, utime))
3648 return -EFAULT;
3649 if (!timespec64_valid(&ts))
3650 return -EINVAL;
3651
3652 t = timespec64_to_ktime(ts);
3653 if (cmd == FUTEX_WAIT)
3654 t = ktime_add_safe(ktime_get(), t);
3655 tp = &t;
3656 }
3657 /*
3658 * requeue parameter in 'utime' if cmd == FUTEX_*_REQUEUE_*.
3659 * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
3660 */
3661 if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
3662 cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
3663 val2 = (u32) (unsigned long) utime;
3664
3665 return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
3666}
3667
3668#ifdef CONFIG_COMPAT
3669/*
3670 * Fetch a robust-list pointer. Bit 0 signals PI futexes:
3671 */
3672static inline int
3673compat_fetch_robust_entry(compat_uptr_t *uentry, struct robust_list __user **entry,
3674 compat_uptr_t __user *head, unsigned int *pi)
3675{
3676 if (get_user(*uentry, head))
3677 return -EFAULT;
3678
3679 *entry = compat_ptr((*uentry) & ~1);
3680 *pi = (unsigned int)(*uentry) & 1;
3681
3682 return 0;
3683}
3684
3685static void __user *futex_uaddr(struct robust_list __user *entry,
3686 compat_long_t futex_offset)
3687{
3688 compat_uptr_t base = ptr_to_compat(entry);
3689 void __user *uaddr = compat_ptr(base + futex_offset);
3690
3691 return uaddr;
3692}
3693
3694/*
3695 * Walk curr->robust_list (very carefully, it's a userspace list!)
3696 * and mark any locks found there dead, and notify any waiters.
3697 *
3698 * We silently return on any sign of list-walking problem.
3699 */
3700void compat_exit_robust_list(struct task_struct *curr)
3701{
3702 struct compat_robust_list_head __user *head = curr->compat_robust_list;
3703 struct robust_list __user *entry, *next_entry, *pending;
3704 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
3705 unsigned int uninitialized_var(next_pi);
3706 compat_uptr_t uentry, next_uentry, upending;
3707 compat_long_t futex_offset;
3708 int rc;
3709
3710 if (!futex_cmpxchg_enabled)
3711 return;
3712
3713 /*
3714 * Fetch the list head (which was registered earlier, via
3715 * sys_set_robust_list()):
3716 */
3717 if (compat_fetch_robust_entry(&uentry, &entry, &head->list.next, &pi))
3718 return;
3719 /*
3720 * Fetch the relative futex offset:
3721 */
3722 if (get_user(futex_offset, &head->futex_offset))
3723 return;
3724 /*
3725 * Fetch any possibly pending lock-add first, and handle it
3726 * if it exists:
3727 */
3728 if (compat_fetch_robust_entry(&upending, &pending,
3729 &head->list_op_pending, &pip))
3730 return;
3731
3732 next_entry = NULL; /* avoid warning with gcc */
3733 while (entry != (struct robust_list __user *) &head->list) {
3734 /*
3735 * Fetch the next entry in the list before calling
3736 * handle_futex_death:
3737 */
3738 rc = compat_fetch_robust_entry(&next_uentry, &next_entry,
3739 (compat_uptr_t __user *)&entry->next, &next_pi);
3740 /*
3741 * A pending lock might already be on the list, so
3742 * dont process it twice:
3743 */
3744 if (entry != pending) {
3745 void __user *uaddr = futex_uaddr(entry, futex_offset);
3746
3747 if (handle_futex_death(uaddr, curr, pi))
3748 return;
3749 }
3750 if (rc)
3751 return;
3752 uentry = next_uentry;
3753 entry = next_entry;
3754 pi = next_pi;
3755 /*
3756 * Avoid excessively long or circular lists:
3757 */
3758 if (!--limit)
3759 break;
3760
3761 cond_resched();
3762 }
3763 if (pending) {
3764 void __user *uaddr = futex_uaddr(pending, futex_offset);
3765
3766 handle_futex_death(uaddr, curr, pip);
3767 }
3768}
3769
3770COMPAT_SYSCALL_DEFINE2(set_robust_list,
3771 struct compat_robust_list_head __user *, head,
3772 compat_size_t, len)
3773{
3774 if (!futex_cmpxchg_enabled)
3775 return -ENOSYS;
3776
3777 if (unlikely(len != sizeof(*head)))
3778 return -EINVAL;
3779
3780 current->compat_robust_list = head;
3781
3782 return 0;
3783}
3784
3785COMPAT_SYSCALL_DEFINE3(get_robust_list, int, pid,
3786 compat_uptr_t __user *, head_ptr,
3787 compat_size_t __user *, len_ptr)
3788{
3789 struct compat_robust_list_head __user *head;
3790 unsigned long ret;
3791 struct task_struct *p;
3792
3793 if (!futex_cmpxchg_enabled)
3794 return -ENOSYS;
3795
3796 rcu_read_lock();
3797
3798 ret = -ESRCH;
3799 if (!pid)
3800 p = current;
3801 else {
3802 p = find_task_by_vpid(pid);
3803 if (!p)
3804 goto err_unlock;
3805 }
3806
3807 ret = -EPERM;
3808 if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS))
3809 goto err_unlock;
3810
3811 head = p->compat_robust_list;
3812 rcu_read_unlock();
3813
3814 if (put_user(sizeof(*head), len_ptr))
3815 return -EFAULT;
3816 return put_user(ptr_to_compat(head), head_ptr);
3817
3818err_unlock:
3819 rcu_read_unlock();
3820
3821 return ret;
3822}
3823#endif /* CONFIG_COMPAT */
3824
3825#ifdef CONFIG_COMPAT_32BIT_TIME
3826SYSCALL_DEFINE6(futex_time32, u32 __user *, uaddr, int, op, u32, val,
3827 struct old_timespec32 __user *, utime, u32 __user *, uaddr2,
3828 u32, val3)
3829{
3830 struct timespec64 ts;
3831 ktime_t t, *tp = NULL;
3832 int val2 = 0;
3833 int cmd = op & FUTEX_CMD_MASK;
3834
3835 if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
3836 cmd == FUTEX_WAIT_BITSET ||
3837 cmd == FUTEX_WAIT_REQUEUE_PI)) {
3838 if (get_old_timespec32(&ts, utime))
3839 return -EFAULT;
3840 if (!timespec64_valid(&ts))
3841 return -EINVAL;
3842
3843 t = timespec64_to_ktime(ts);
3844 if (cmd == FUTEX_WAIT)
3845 t = ktime_add_safe(ktime_get(), t);
3846 tp = &t;
3847 }
3848 if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
3849 cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
3850 val2 = (int) (unsigned long) utime;
3851
3852 return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
3853}
3854#endif /* CONFIG_COMPAT_32BIT_TIME */
3855
3856static void __init futex_detect_cmpxchg(void)
3857{
3858#ifndef CONFIG_HAVE_FUTEX_CMPXCHG
3859 u32 curval;
3860
3861 /*
3862 * This will fail and we want it. Some arch implementations do
3863 * runtime detection of the futex_atomic_cmpxchg_inatomic()
3864 * functionality. We want to know that before we call in any
3865 * of the complex code paths. Also we want to prevent
3866 * registration of robust lists in that case. NULL is
3867 * guaranteed to fault and we get -EFAULT on functional
3868 * implementation, the non-functional ones will return
3869 * -ENOSYS.
3870 */
3871 if (cmpxchg_futex_value_locked(&curval, NULL, 0, 0) == -EFAULT)
3872 futex_cmpxchg_enabled = 1;
3873#endif
3874}
3875
3876static int __init futex_init(void)
3877{
3878 unsigned int futex_shift;
3879 unsigned long i;
3880
3881#if CONFIG_BASE_SMALL
3882 futex_hashsize = 16;
3883#else
3884 futex_hashsize = roundup_pow_of_two(256 * num_possible_cpus());
3885#endif
3886
3887 futex_queues = alloc_large_system_hash("futex", sizeof(*futex_queues),
3888 futex_hashsize, 0,
3889 futex_hashsize < 256 ? HASH_SMALL : 0,
3890 &futex_shift, NULL,
3891 futex_hashsize, futex_hashsize);
3892 futex_hashsize = 1UL << futex_shift;
3893
3894 futex_detect_cmpxchg();
3895
3896 for (i = 0; i < futex_hashsize; i++) {
3897 atomic_set(&futex_queues[i].waiters, 0);
3898 plist_head_init(&futex_queues[i].chain);
3899 spin_lock_init(&futex_queues[i].lock);
3900 }
3901
3902 return 0;
3903}
3904core_initcall(futex_init);
3905