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