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