futex: Add futex_q static initializer
[linux-2.6.git] / kernel / futex.c
1 /*
2  *  Fast Userspace Mutexes (which I call "Futexes!").
3  *  (C) Rusty Russell, IBM 2002
4  *
5  *  Generalized futexes, futex requeueing, misc fixes by Ingo Molnar
6  *  (C) Copyright 2003 Red Hat Inc, All Rights Reserved
7  *
8  *  Removed page pinning, fix privately mapped COW pages and other cleanups
9  *  (C) Copyright 2003, 2004 Jamie Lokier
10  *
11  *  Robust futex support started by Ingo Molnar
12  *  (C) Copyright 2006 Red Hat Inc, All Rights Reserved
13  *  Thanks to Thomas Gleixner for suggestions, analysis and fixes.
14  *
15  *  PI-futex support started by Ingo Molnar and Thomas Gleixner
16  *  Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
17  *  Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
18  *
19  *  PRIVATE futexes by Eric Dumazet
20  *  Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com>
21  *
22  *  Requeue-PI support by Darren Hart <dvhltc@us.ibm.com>
23  *  Copyright (C) IBM Corporation, 2009
24  *  Thanks to Thomas Gleixner for conceptual design and careful reviews.
25  *
26  *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
27  *  enough at me, Linus for the original (flawed) idea, Matthew
28  *  Kirkwood for proof-of-concept implementation.
29  *
30  *  "The futexes are also cursed."
31  *  "But they come in a choice of three flavours!"
32  *
33  *  This program is free software; you can redistribute it and/or modify
34  *  it under the terms of the GNU General Public License as published by
35  *  the Free Software Foundation; either version 2 of the License, or
36  *  (at your option) any later version.
37  *
38  *  This program is distributed in the hope that it will be useful,
39  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
40  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
41  *  GNU General Public License for more details.
42  *
43  *  You should have received a copy of the GNU General Public License
44  *  along with this program; if not, write to the Free Software
45  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
46  */
47 #include <linux/slab.h>
48 #include <linux/poll.h>
49 #include <linux/fs.h>
50 #include <linux/file.h>
51 #include <linux/jhash.h>
52 #include <linux/init.h>
53 #include <linux/futex.h>
54 #include <linux/mount.h>
55 #include <linux/pagemap.h>
56 #include <linux/syscalls.h>
57 #include <linux/signal.h>
58 #include <linux/module.h>
59 #include <linux/magic.h>
60 #include <linux/pid.h>
61 #include <linux/nsproxy.h>
62
63 #include <asm/futex.h>
64
65 #include "rtmutex_common.h"
66
67 int __read_mostly futex_cmpxchg_enabled;
68
69 #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
70
71 /*
72  * Futex flags used to encode options to functions and preserve them across
73  * restarts.
74  */
75 #define FLAGS_SHARED            0x01
76 #define FLAGS_CLOCKRT           0x02
77 #define FLAGS_HAS_TIMEOUT       0x04
78
79 /*
80  * Priority Inheritance state:
81  */
82 struct futex_pi_state {
83         /*
84          * list of 'owned' pi_state instances - these have to be
85          * cleaned up in do_exit() if the task exits prematurely:
86          */
87         struct list_head list;
88
89         /*
90          * The PI object:
91          */
92         struct rt_mutex pi_mutex;
93
94         struct task_struct *owner;
95         atomic_t refcount;
96
97         union futex_key key;
98 };
99
100 /**
101  * struct futex_q - The hashed futex queue entry, one per waiting task
102  * @list:               priority-sorted list of tasks waiting on this futex
103  * @task:               the task waiting on the futex
104  * @lock_ptr:           the hash bucket lock
105  * @key:                the key the futex is hashed on
106  * @pi_state:           optional priority inheritance state
107  * @rt_waiter:          rt_waiter storage for use with requeue_pi
108  * @requeue_pi_key:     the requeue_pi target futex key
109  * @bitset:             bitset for the optional bitmasked wakeup
110  *
111  * We use this hashed waitqueue, instead of a normal wait_queue_t, so
112  * we can wake only the relevant ones (hashed queues may be shared).
113  *
114  * A futex_q has a woken state, just like tasks have TASK_RUNNING.
115  * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
116  * The order of wakeup is always to make the first condition true, then
117  * the second.
118  *
119  * PI futexes are typically woken before they are removed from the hash list via
120  * the rt_mutex code. See unqueue_me_pi().
121  */
122 struct futex_q {
123         struct plist_node list;
124
125         struct task_struct *task;
126         spinlock_t *lock_ptr;
127         union futex_key key;
128         struct futex_pi_state *pi_state;
129         struct rt_mutex_waiter *rt_waiter;
130         union futex_key *requeue_pi_key;
131         u32 bitset;
132 };
133
134 static const struct futex_q futex_q_init = {
135         /* list gets initialized in queue_me()*/
136         .key = FUTEX_KEY_INIT,
137         .bitset = FUTEX_BITSET_MATCH_ANY
138 };
139
140 /*
141  * Hash buckets are shared by all the futex_keys that hash to the same
142  * location.  Each key may have multiple futex_q structures, one for each task
143  * waiting on a futex.
144  */
145 struct futex_hash_bucket {
146         spinlock_t lock;
147         struct plist_head chain;
148 };
149
150 static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
151
152 /*
153  * We hash on the keys returned from get_futex_key (see below).
154  */
155 static struct futex_hash_bucket *hash_futex(union futex_key *key)
156 {
157         u32 hash = jhash2((u32*)&key->both.word,
158                           (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
159                           key->both.offset);
160         return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
161 }
162
163 /*
164  * Return 1 if two futex_keys are equal, 0 otherwise.
165  */
166 static inline int match_futex(union futex_key *key1, union futex_key *key2)
167 {
168         return (key1 && key2
169                 && key1->both.word == key2->both.word
170                 && key1->both.ptr == key2->both.ptr
171                 && key1->both.offset == key2->both.offset);
172 }
173
174 /*
175  * Take a reference to the resource addressed by a key.
176  * Can be called while holding spinlocks.
177  *
178  */
179 static void get_futex_key_refs(union futex_key *key)
180 {
181         if (!key->both.ptr)
182                 return;
183
184         switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
185         case FUT_OFF_INODE:
186                 ihold(key->shared.inode);
187                 break;
188         case FUT_OFF_MMSHARED:
189                 atomic_inc(&key->private.mm->mm_count);
190                 break;
191         }
192 }
193
194 /*
195  * Drop a reference to the resource addressed by a key.
196  * The hash bucket spinlock must not be held.
197  */
198 static void drop_futex_key_refs(union futex_key *key)
199 {
200         if (!key->both.ptr) {
201                 /* If we're here then we tried to put a key we failed to get */
202                 WARN_ON_ONCE(1);
203                 return;
204         }
205
206         switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
207         case FUT_OFF_INODE:
208                 iput(key->shared.inode);
209                 break;
210         case FUT_OFF_MMSHARED:
211                 mmdrop(key->private.mm);
212                 break;
213         }
214 }
215
216 /**
217  * get_futex_key() - Get parameters which are the keys for a futex
218  * @uaddr:      virtual address of the futex
219  * @fshared:    0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
220  * @key:        address where result is stored.
221  *
222  * Returns a negative error code or 0
223  * The key words are stored in *key on success.
224  *
225  * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode,
226  * offset_within_page).  For private mappings, it's (uaddr, current->mm).
227  * We can usually work out the index without swapping in the page.
228  *
229  * lock_page() might sleep, the caller should not hold a spinlock.
230  */
231 static int
232 get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key)
233 {
234         unsigned long address = (unsigned long)uaddr;
235         struct mm_struct *mm = current->mm;
236         struct page *page;
237         int err;
238
239         /*
240          * The futex address must be "naturally" aligned.
241          */
242         key->both.offset = address % PAGE_SIZE;
243         if (unlikely((address % sizeof(u32)) != 0))
244                 return -EINVAL;
245         address -= key->both.offset;
246
247         /*
248          * PROCESS_PRIVATE futexes are fast.
249          * As the mm cannot disappear under us and the 'key' only needs
250          * virtual address, we dont even have to find the underlying vma.
251          * Note : We do have to check 'uaddr' is a valid user address,
252          *        but access_ok() should be faster than find_vma()
253          */
254         if (!fshared) {
255                 if (unlikely(!access_ok(VERIFY_WRITE, uaddr, sizeof(u32))))
256                         return -EFAULT;
257                 key->private.mm = mm;
258                 key->private.address = address;
259                 get_futex_key_refs(key);
260                 return 0;
261         }
262
263 again:
264         err = get_user_pages_fast(address, 1, 1, &page);
265         if (err < 0)
266                 return err;
267
268         page = compound_head(page);
269         lock_page(page);
270         if (!page->mapping) {
271                 unlock_page(page);
272                 put_page(page);
273                 goto again;
274         }
275
276         /*
277          * Private mappings are handled in a simple way.
278          *
279          * NOTE: When userspace waits on a MAP_SHARED mapping, even if
280          * it's a read-only handle, it's expected that futexes attach to
281          * the object not the particular process.
282          */
283         if (PageAnon(page)) {
284                 key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
285                 key->private.mm = mm;
286                 key->private.address = address;
287         } else {
288                 key->both.offset |= FUT_OFF_INODE; /* inode-based key */
289                 key->shared.inode = page->mapping->host;
290                 key->shared.pgoff = page->index;
291         }
292
293         get_futex_key_refs(key);
294
295         unlock_page(page);
296         put_page(page);
297         return 0;
298 }
299
300 static inline void put_futex_key(union futex_key *key)
301 {
302         drop_futex_key_refs(key);
303 }
304
305 /**
306  * fault_in_user_writeable() - Fault in user address and verify RW access
307  * @uaddr:      pointer to faulting user space address
308  *
309  * Slow path to fixup the fault we just took in the atomic write
310  * access to @uaddr.
311  *
312  * We have no generic implementation of a non-destructive write to the
313  * user address. We know that we faulted in the atomic pagefault
314  * disabled section so we can as well avoid the #PF overhead by
315  * calling get_user_pages() right away.
316  */
317 static int fault_in_user_writeable(u32 __user *uaddr)
318 {
319         struct mm_struct *mm = current->mm;
320         int ret;
321
322         down_read(&mm->mmap_sem);
323         ret = get_user_pages(current, mm, (unsigned long)uaddr,
324                              1, 1, 0, NULL, NULL);
325         up_read(&mm->mmap_sem);
326
327         return ret < 0 ? ret : 0;
328 }
329
330 /**
331  * futex_top_waiter() - Return the highest priority waiter on a futex
332  * @hb:         the hash bucket the futex_q's reside in
333  * @key:        the futex key (to distinguish it from other futex futex_q's)
334  *
335  * Must be called with the hb lock held.
336  */
337 static struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb,
338                                         union futex_key *key)
339 {
340         struct futex_q *this;
341
342         plist_for_each_entry(this, &hb->chain, list) {
343                 if (match_futex(&this->key, key))
344                         return this;
345         }
346         return NULL;
347 }
348
349 static u32 cmpxchg_futex_value_locked(u32 __user *uaddr, u32 uval, u32 newval)
350 {
351         u32 curval;
352
353         pagefault_disable();
354         curval = futex_atomic_cmpxchg_inatomic(uaddr, uval, newval);
355         pagefault_enable();
356
357         return curval;
358 }
359
360 static int get_futex_value_locked(u32 *dest, u32 __user *from)
361 {
362         int ret;
363
364         pagefault_disable();
365         ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
366         pagefault_enable();
367
368         return ret ? -EFAULT : 0;
369 }
370
371
372 /*
373  * PI code:
374  */
375 static int refill_pi_state_cache(void)
376 {
377         struct futex_pi_state *pi_state;
378
379         if (likely(current->pi_state_cache))
380                 return 0;
381
382         pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
383
384         if (!pi_state)
385                 return -ENOMEM;
386
387         INIT_LIST_HEAD(&pi_state->list);
388         /* pi_mutex gets initialized later */
389         pi_state->owner = NULL;
390         atomic_set(&pi_state->refcount, 1);
391         pi_state->key = FUTEX_KEY_INIT;
392
393         current->pi_state_cache = pi_state;
394
395         return 0;
396 }
397
398 static struct futex_pi_state * alloc_pi_state(void)
399 {
400         struct futex_pi_state *pi_state = current->pi_state_cache;
401
402         WARN_ON(!pi_state);
403         current->pi_state_cache = NULL;
404
405         return pi_state;
406 }
407
408 static void free_pi_state(struct futex_pi_state *pi_state)
409 {
410         if (!atomic_dec_and_test(&pi_state->refcount))
411                 return;
412
413         /*
414          * If pi_state->owner is NULL, the owner is most probably dying
415          * and has cleaned up the pi_state already
416          */
417         if (pi_state->owner) {
418                 raw_spin_lock_irq(&pi_state->owner->pi_lock);
419                 list_del_init(&pi_state->list);
420                 raw_spin_unlock_irq(&pi_state->owner->pi_lock);
421
422                 rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
423         }
424
425         if (current->pi_state_cache)
426                 kfree(pi_state);
427         else {
428                 /*
429                  * pi_state->list is already empty.
430                  * clear pi_state->owner.
431                  * refcount is at 0 - put it back to 1.
432                  */
433                 pi_state->owner = NULL;
434                 atomic_set(&pi_state->refcount, 1);
435                 current->pi_state_cache = pi_state;
436         }
437 }
438
439 /*
440  * Look up the task based on what TID userspace gave us.
441  * We dont trust it.
442  */
443 static struct task_struct * futex_find_get_task(pid_t pid)
444 {
445         struct task_struct *p;
446
447         rcu_read_lock();
448         p = find_task_by_vpid(pid);
449         if (p)
450                 get_task_struct(p);
451
452         rcu_read_unlock();
453
454         return p;
455 }
456
457 /*
458  * This task is holding PI mutexes at exit time => bad.
459  * Kernel cleans up PI-state, but userspace is likely hosed.
460  * (Robust-futex cleanup is separate and might save the day for userspace.)
461  */
462 void exit_pi_state_list(struct task_struct *curr)
463 {
464         struct list_head *next, *head = &curr->pi_state_list;
465         struct futex_pi_state *pi_state;
466         struct futex_hash_bucket *hb;
467         union futex_key key = FUTEX_KEY_INIT;
468
469         if (!futex_cmpxchg_enabled)
470                 return;
471         /*
472          * We are a ZOMBIE and nobody can enqueue itself on
473          * pi_state_list anymore, but we have to be careful
474          * versus waiters unqueueing themselves:
475          */
476         raw_spin_lock_irq(&curr->pi_lock);
477         while (!list_empty(head)) {
478
479                 next = head->next;
480                 pi_state = list_entry(next, struct futex_pi_state, list);
481                 key = pi_state->key;
482                 hb = hash_futex(&key);
483                 raw_spin_unlock_irq(&curr->pi_lock);
484
485                 spin_lock(&hb->lock);
486
487                 raw_spin_lock_irq(&curr->pi_lock);
488                 /*
489                  * We dropped the pi-lock, so re-check whether this
490                  * task still owns the PI-state:
491                  */
492                 if (head->next != next) {
493                         spin_unlock(&hb->lock);
494                         continue;
495                 }
496
497                 WARN_ON(pi_state->owner != curr);
498                 WARN_ON(list_empty(&pi_state->list));
499                 list_del_init(&pi_state->list);
500                 pi_state->owner = NULL;
501                 raw_spin_unlock_irq(&curr->pi_lock);
502
503                 rt_mutex_unlock(&pi_state->pi_mutex);
504
505                 spin_unlock(&hb->lock);
506
507                 raw_spin_lock_irq(&curr->pi_lock);
508         }
509         raw_spin_unlock_irq(&curr->pi_lock);
510 }
511
512 static int
513 lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
514                 union futex_key *key, struct futex_pi_state **ps)
515 {
516         struct futex_pi_state *pi_state = NULL;
517         struct futex_q *this, *next;
518         struct plist_head *head;
519         struct task_struct *p;
520         pid_t pid = uval & FUTEX_TID_MASK;
521
522         head = &hb->chain;
523
524         plist_for_each_entry_safe(this, next, head, list) {
525                 if (match_futex(&this->key, key)) {
526                         /*
527                          * Another waiter already exists - bump up
528                          * the refcount and return its pi_state:
529                          */
530                         pi_state = this->pi_state;
531                         /*
532                          * Userspace might have messed up non-PI and PI futexes
533                          */
534                         if (unlikely(!pi_state))
535                                 return -EINVAL;
536
537                         WARN_ON(!atomic_read(&pi_state->refcount));
538
539                         /*
540                          * When pi_state->owner is NULL then the owner died
541                          * and another waiter is on the fly. pi_state->owner
542                          * is fixed up by the task which acquires
543                          * pi_state->rt_mutex.
544                          *
545                          * We do not check for pid == 0 which can happen when
546                          * the owner died and robust_list_exit() cleared the
547                          * TID.
548                          */
549                         if (pid && pi_state->owner) {
550                                 /*
551                                  * Bail out if user space manipulated the
552                                  * futex value.
553                                  */
554                                 if (pid != task_pid_vnr(pi_state->owner))
555                                         return -EINVAL;
556                         }
557
558                         atomic_inc(&pi_state->refcount);
559                         *ps = pi_state;
560
561                         return 0;
562                 }
563         }
564
565         /*
566          * We are the first waiter - try to look up the real owner and attach
567          * the new pi_state to it, but bail out when TID = 0
568          */
569         if (!pid)
570                 return -ESRCH;
571         p = futex_find_get_task(pid);
572         if (!p)
573                 return -ESRCH;
574
575         /*
576          * We need to look at the task state flags to figure out,
577          * whether the task is exiting. To protect against the do_exit
578          * change of the task flags, we do this protected by
579          * p->pi_lock:
580          */
581         raw_spin_lock_irq(&p->pi_lock);
582         if (unlikely(p->flags & PF_EXITING)) {
583                 /*
584                  * The task is on the way out. When PF_EXITPIDONE is
585                  * set, we know that the task has finished the
586                  * cleanup:
587                  */
588                 int ret = (p->flags & PF_EXITPIDONE) ? -ESRCH : -EAGAIN;
589
590                 raw_spin_unlock_irq(&p->pi_lock);
591                 put_task_struct(p);
592                 return ret;
593         }
594
595         pi_state = alloc_pi_state();
596
597         /*
598          * Initialize the pi_mutex in locked state and make 'p'
599          * the owner of it:
600          */
601         rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
602
603         /* Store the key for possible exit cleanups: */
604         pi_state->key = *key;
605
606         WARN_ON(!list_empty(&pi_state->list));
607         list_add(&pi_state->list, &p->pi_state_list);
608         pi_state->owner = p;
609         raw_spin_unlock_irq(&p->pi_lock);
610
611         put_task_struct(p);
612
613         *ps = pi_state;
614
615         return 0;
616 }
617
618 /**
619  * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
620  * @uaddr:              the pi futex user address
621  * @hb:                 the pi futex hash bucket
622  * @key:                the futex key associated with uaddr and hb
623  * @ps:                 the pi_state pointer where we store the result of the
624  *                      lookup
625  * @task:               the task to perform the atomic lock work for.  This will
626  *                      be "current" except in the case of requeue pi.
627  * @set_waiters:        force setting the FUTEX_WAITERS bit (1) or not (0)
628  *
629  * Returns:
630  *  0 - ready to wait
631  *  1 - acquired the lock
632  * <0 - error
633  *
634  * The hb->lock and futex_key refs shall be held by the caller.
635  */
636 static int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
637                                 union futex_key *key,
638                                 struct futex_pi_state **ps,
639                                 struct task_struct *task, int set_waiters)
640 {
641         int lock_taken, ret, ownerdied = 0;
642         u32 uval, newval, curval;
643
644 retry:
645         ret = lock_taken = 0;
646
647         /*
648          * To avoid races, we attempt to take the lock here again
649          * (by doing a 0 -> TID atomic cmpxchg), while holding all
650          * the locks. It will most likely not succeed.
651          */
652         newval = task_pid_vnr(task);
653         if (set_waiters)
654                 newval |= FUTEX_WAITERS;
655
656         curval = cmpxchg_futex_value_locked(uaddr, 0, newval);
657
658         if (unlikely(curval == -EFAULT))
659                 return -EFAULT;
660
661         /*
662          * Detect deadlocks.
663          */
664         if ((unlikely((curval & FUTEX_TID_MASK) == task_pid_vnr(task))))
665                 return -EDEADLK;
666
667         /*
668          * Surprise - we got the lock. Just return to userspace:
669          */
670         if (unlikely(!curval))
671                 return 1;
672
673         uval = curval;
674
675         /*
676          * Set the FUTEX_WAITERS flag, so the owner will know it has someone
677          * to wake at the next unlock.
678          */
679         newval = curval | FUTEX_WAITERS;
680
681         /*
682          * There are two cases, where a futex might have no owner (the
683          * owner TID is 0): OWNER_DIED. We take over the futex in this
684          * case. We also do an unconditional take over, when the owner
685          * of the futex died.
686          *
687          * This is safe as we are protected by the hash bucket lock !
688          */
689         if (unlikely(ownerdied || !(curval & FUTEX_TID_MASK))) {
690                 /* Keep the OWNER_DIED bit */
691                 newval = (curval & ~FUTEX_TID_MASK) | task_pid_vnr(task);
692                 ownerdied = 0;
693                 lock_taken = 1;
694         }
695
696         curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
697
698         if (unlikely(curval == -EFAULT))
699                 return -EFAULT;
700         if (unlikely(curval != uval))
701                 goto retry;
702
703         /*
704          * We took the lock due to owner died take over.
705          */
706         if (unlikely(lock_taken))
707                 return 1;
708
709         /*
710          * We dont have the lock. Look up the PI state (or create it if
711          * we are the first waiter):
712          */
713         ret = lookup_pi_state(uval, hb, key, ps);
714
715         if (unlikely(ret)) {
716                 switch (ret) {
717                 case -ESRCH:
718                         /*
719                          * No owner found for this futex. Check if the
720                          * OWNER_DIED bit is set to figure out whether
721                          * this is a robust futex or not.
722                          */
723                         if (get_futex_value_locked(&curval, uaddr))
724                                 return -EFAULT;
725
726                         /*
727                          * We simply start over in case of a robust
728                          * futex. The code above will take the futex
729                          * and return happy.
730                          */
731                         if (curval & FUTEX_OWNER_DIED) {
732                                 ownerdied = 1;
733                                 goto retry;
734                         }
735                 default:
736                         break;
737                 }
738         }
739
740         return ret;
741 }
742
743 /*
744  * The hash bucket lock must be held when this is called.
745  * Afterwards, the futex_q must not be accessed.
746  */
747 static void wake_futex(struct futex_q *q)
748 {
749         struct task_struct *p = q->task;
750
751         /*
752          * We set q->lock_ptr = NULL _before_ we wake up the task. If
753          * a non-futex wake up happens on another CPU then the task
754          * might exit and p would dereference a non-existing task
755          * struct. Prevent this by holding a reference on p across the
756          * wake up.
757          */
758         get_task_struct(p);
759
760         plist_del(&q->list, &q->list.plist);
761         /*
762          * The waiting task can free the futex_q as soon as
763          * q->lock_ptr = NULL is written, without taking any locks. A
764          * memory barrier is required here to prevent the following
765          * store to lock_ptr from getting ahead of the plist_del.
766          */
767         smp_wmb();
768         q->lock_ptr = NULL;
769
770         wake_up_state(p, TASK_NORMAL);
771         put_task_struct(p);
772 }
773
774 static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
775 {
776         struct task_struct *new_owner;
777         struct futex_pi_state *pi_state = this->pi_state;
778         u32 curval, newval;
779
780         if (!pi_state)
781                 return -EINVAL;
782
783         /*
784          * If current does not own the pi_state then the futex is
785          * inconsistent and user space fiddled with the futex value.
786          */
787         if (pi_state->owner != current)
788                 return -EINVAL;
789
790         raw_spin_lock(&pi_state->pi_mutex.wait_lock);
791         new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
792
793         /*
794          * This happens when we have stolen the lock and the original
795          * pending owner did not enqueue itself back on the rt_mutex.
796          * Thats not a tragedy. We know that way, that a lock waiter
797          * is on the fly. We make the futex_q waiter the pending owner.
798          */
799         if (!new_owner)
800                 new_owner = this->task;
801
802         /*
803          * We pass it to the next owner. (The WAITERS bit is always
804          * kept enabled while there is PI state around. We must also
805          * preserve the owner died bit.)
806          */
807         if (!(uval & FUTEX_OWNER_DIED)) {
808                 int ret = 0;
809
810                 newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
811
812                 curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
813
814                 if (curval == -EFAULT)
815                         ret = -EFAULT;
816                 else if (curval != uval)
817                         ret = -EINVAL;
818                 if (ret) {
819                         raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
820                         return ret;
821                 }
822         }
823
824         raw_spin_lock_irq(&pi_state->owner->pi_lock);
825         WARN_ON(list_empty(&pi_state->list));
826         list_del_init(&pi_state->list);
827         raw_spin_unlock_irq(&pi_state->owner->pi_lock);
828
829         raw_spin_lock_irq(&new_owner->pi_lock);
830         WARN_ON(!list_empty(&pi_state->list));
831         list_add(&pi_state->list, &new_owner->pi_state_list);
832         pi_state->owner = new_owner;
833         raw_spin_unlock_irq(&new_owner->pi_lock);
834
835         raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
836         rt_mutex_unlock(&pi_state->pi_mutex);
837
838         return 0;
839 }
840
841 static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
842 {
843         u32 oldval;
844
845         /*
846          * There is no waiter, so we unlock the futex. The owner died
847          * bit has not to be preserved here. We are the owner:
848          */
849         oldval = cmpxchg_futex_value_locked(uaddr, uval, 0);
850
851         if (oldval == -EFAULT)
852                 return oldval;
853         if (oldval != uval)
854                 return -EAGAIN;
855
856         return 0;
857 }
858
859 /*
860  * Express the locking dependencies for lockdep:
861  */
862 static inline void
863 double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
864 {
865         if (hb1 <= hb2) {
866                 spin_lock(&hb1->lock);
867                 if (hb1 < hb2)
868                         spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
869         } else { /* hb1 > hb2 */
870                 spin_lock(&hb2->lock);
871                 spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
872         }
873 }
874
875 static inline void
876 double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
877 {
878         spin_unlock(&hb1->lock);
879         if (hb1 != hb2)
880                 spin_unlock(&hb2->lock);
881 }
882
883 /*
884  * Wake up waiters matching bitset queued on this futex (uaddr).
885  */
886 static int
887 futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
888 {
889         struct futex_hash_bucket *hb;
890         struct futex_q *this, *next;
891         struct plist_head *head;
892         union futex_key key = FUTEX_KEY_INIT;
893         int ret;
894
895         if (!bitset)
896                 return -EINVAL;
897
898         ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key);
899         if (unlikely(ret != 0))
900                 goto out;
901
902         hb = hash_futex(&key);
903         spin_lock(&hb->lock);
904         head = &hb->chain;
905
906         plist_for_each_entry_safe(this, next, head, list) {
907                 if (match_futex (&this->key, &key)) {
908                         if (this->pi_state || this->rt_waiter) {
909                                 ret = -EINVAL;
910                                 break;
911                         }
912
913                         /* Check if one of the bits is set in both bitsets */
914                         if (!(this->bitset & bitset))
915                                 continue;
916
917                         wake_futex(this);
918                         if (++ret >= nr_wake)
919                                 break;
920                 }
921         }
922
923         spin_unlock(&hb->lock);
924         put_futex_key(&key);
925 out:
926         return ret;
927 }
928
929 /*
930  * Wake up all waiters hashed on the physical page that is mapped
931  * to this virtual address:
932  */
933 static int
934 futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
935               int nr_wake, int nr_wake2, int op)
936 {
937         union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
938         struct futex_hash_bucket *hb1, *hb2;
939         struct plist_head *head;
940         struct futex_q *this, *next;
941         int ret, op_ret;
942
943 retry:
944         ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1);
945         if (unlikely(ret != 0))
946                 goto out;
947         ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2);
948         if (unlikely(ret != 0))
949                 goto out_put_key1;
950
951         hb1 = hash_futex(&key1);
952         hb2 = hash_futex(&key2);
953
954 retry_private:
955         double_lock_hb(hb1, hb2);
956         op_ret = futex_atomic_op_inuser(op, uaddr2);
957         if (unlikely(op_ret < 0)) {
958
959                 double_unlock_hb(hb1, hb2);
960
961 #ifndef CONFIG_MMU
962                 /*
963                  * we don't get EFAULT from MMU faults if we don't have an MMU,
964                  * but we might get them from range checking
965                  */
966                 ret = op_ret;
967                 goto out_put_keys;
968 #endif
969
970                 if (unlikely(op_ret != -EFAULT)) {
971                         ret = op_ret;
972                         goto out_put_keys;
973                 }
974
975                 ret = fault_in_user_writeable(uaddr2);
976                 if (ret)
977                         goto out_put_keys;
978
979                 if (!(flags & FLAGS_SHARED))
980                         goto retry_private;
981
982                 put_futex_key(&key2);
983                 put_futex_key(&key1);
984                 goto retry;
985         }
986
987         head = &hb1->chain;
988
989         plist_for_each_entry_safe(this, next, head, list) {
990                 if (match_futex (&this->key, &key1)) {
991                         wake_futex(this);
992                         if (++ret >= nr_wake)
993                                 break;
994                 }
995         }
996
997         if (op_ret > 0) {
998                 head = &hb2->chain;
999
1000                 op_ret = 0;
1001                 plist_for_each_entry_safe(this, next, head, list) {
1002                         if (match_futex (&this->key, &key2)) {
1003                                 wake_futex(this);
1004                                 if (++op_ret >= nr_wake2)
1005                                         break;
1006                         }
1007                 }
1008                 ret += op_ret;
1009         }
1010
1011         double_unlock_hb(hb1, hb2);
1012 out_put_keys:
1013         put_futex_key(&key2);
1014 out_put_key1:
1015         put_futex_key(&key1);
1016 out:
1017         return ret;
1018 }
1019
1020 /**
1021  * requeue_futex() - Requeue a futex_q from one hb to another
1022  * @q:          the futex_q to requeue
1023  * @hb1:        the source hash_bucket
1024  * @hb2:        the target hash_bucket
1025  * @key2:       the new key for the requeued futex_q
1026  */
1027 static inline
1028 void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
1029                    struct futex_hash_bucket *hb2, union futex_key *key2)
1030 {
1031
1032         /*
1033          * If key1 and key2 hash to the same bucket, no need to
1034          * requeue.
1035          */
1036         if (likely(&hb1->chain != &hb2->chain)) {
1037                 plist_del(&q->list, &hb1->chain);
1038                 plist_add(&q->list, &hb2->chain);
1039                 q->lock_ptr = &hb2->lock;
1040 #ifdef CONFIG_DEBUG_PI_LIST
1041                 q->list.plist.spinlock = &hb2->lock;
1042 #endif
1043         }
1044         get_futex_key_refs(key2);
1045         q->key = *key2;
1046 }
1047
1048 /**
1049  * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
1050  * @q:          the futex_q
1051  * @key:        the key of the requeue target futex
1052  * @hb:         the hash_bucket of the requeue target futex
1053  *
1054  * During futex_requeue, with requeue_pi=1, it is possible to acquire the
1055  * target futex if it is uncontended or via a lock steal.  Set the futex_q key
1056  * to the requeue target futex so the waiter can detect the wakeup on the right
1057  * futex, but remove it from the hb and NULL the rt_waiter so it can detect
1058  * atomic lock acquisition.  Set the q->lock_ptr to the requeue target hb->lock
1059  * to protect access to the pi_state to fixup the owner later.  Must be called
1060  * with both q->lock_ptr and hb->lock held.
1061  */
1062 static inline
1063 void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
1064                            struct futex_hash_bucket *hb)
1065 {
1066         get_futex_key_refs(key);
1067         q->key = *key;
1068
1069         WARN_ON(plist_node_empty(&q->list));
1070         plist_del(&q->list, &q->list.plist);
1071
1072         WARN_ON(!q->rt_waiter);
1073         q->rt_waiter = NULL;
1074
1075         q->lock_ptr = &hb->lock;
1076 #ifdef CONFIG_DEBUG_PI_LIST
1077         q->list.plist.spinlock = &hb->lock;
1078 #endif
1079
1080         wake_up_state(q->task, TASK_NORMAL);
1081 }
1082
1083 /**
1084  * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter
1085  * @pifutex:            the user address of the to futex
1086  * @hb1:                the from futex hash bucket, must be locked by the caller
1087  * @hb2:                the to futex hash bucket, must be locked by the caller
1088  * @key1:               the from futex key
1089  * @key2:               the to futex key
1090  * @ps:                 address to store the pi_state pointer
1091  * @set_waiters:        force setting the FUTEX_WAITERS bit (1) or not (0)
1092  *
1093  * Try and get the lock on behalf of the top waiter if we can do it atomically.
1094  * Wake the top waiter if we succeed.  If the caller specified set_waiters,
1095  * then direct futex_lock_pi_atomic() to force setting the FUTEX_WAITERS bit.
1096  * hb1 and hb2 must be held by the caller.
1097  *
1098  * Returns:
1099  *  0 - failed to acquire the lock atomicly
1100  *  1 - acquired the lock
1101  * <0 - error
1102  */
1103 static int futex_proxy_trylock_atomic(u32 __user *pifutex,
1104                                  struct futex_hash_bucket *hb1,
1105                                  struct futex_hash_bucket *hb2,
1106                                  union futex_key *key1, union futex_key *key2,
1107                                  struct futex_pi_state **ps, int set_waiters)
1108 {
1109         struct futex_q *top_waiter = NULL;
1110         u32 curval;
1111         int ret;
1112
1113         if (get_futex_value_locked(&curval, pifutex))
1114                 return -EFAULT;
1115
1116         /*
1117          * Find the top_waiter and determine if there are additional waiters.
1118          * If the caller intends to requeue more than 1 waiter to pifutex,
1119          * force futex_lock_pi_atomic() to set the FUTEX_WAITERS bit now,
1120          * as we have means to handle the possible fault.  If not, don't set
1121          * the bit unecessarily as it will force the subsequent unlock to enter
1122          * the kernel.
1123          */
1124         top_waiter = futex_top_waiter(hb1, key1);
1125
1126         /* There are no waiters, nothing for us to do. */
1127         if (!top_waiter)
1128                 return 0;
1129
1130         /* Ensure we requeue to the expected futex. */
1131         if (!match_futex(top_waiter->requeue_pi_key, key2))
1132                 return -EINVAL;
1133
1134         /*
1135          * Try to take the lock for top_waiter.  Set the FUTEX_WAITERS bit in
1136          * the contended case or if set_waiters is 1.  The pi_state is returned
1137          * in ps in contended cases.
1138          */
1139         ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
1140                                    set_waiters);
1141         if (ret == 1)
1142                 requeue_pi_wake_futex(top_waiter, key2, hb2);
1143
1144         return ret;
1145 }
1146
1147 /**
1148  * futex_requeue() - Requeue waiters from uaddr1 to uaddr2
1149  * @uaddr1:     source futex user address
1150  * @flags:      futex flags (FLAGS_SHARED, etc.)
1151  * @uaddr2:     target futex user address
1152  * @nr_wake:    number of waiters to wake (must be 1 for requeue_pi)
1153  * @nr_requeue: number of waiters to requeue (0-INT_MAX)
1154  * @cmpval:     @uaddr1 expected value (or %NULL)
1155  * @requeue_pi: if we are attempting to requeue from a non-pi futex to a
1156  *              pi futex (pi to pi requeue is not supported)
1157  *
1158  * Requeue waiters on uaddr1 to uaddr2. In the requeue_pi case, try to acquire
1159  * uaddr2 atomically on behalf of the top waiter.
1160  *
1161  * Returns:
1162  * >=0 - on success, the number of tasks requeued or woken
1163  *  <0 - on error
1164  */
1165 static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
1166                          u32 __user *uaddr2, int nr_wake, int nr_requeue,
1167                          u32 *cmpval, int requeue_pi)
1168 {
1169         union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
1170         int drop_count = 0, task_count = 0, ret;
1171         struct futex_pi_state *pi_state = NULL;
1172         struct futex_hash_bucket *hb1, *hb2;
1173         struct plist_head *head1;
1174         struct futex_q *this, *next;
1175         u32 curval2;
1176
1177         if (requeue_pi) {
1178                 /*
1179                  * requeue_pi requires a pi_state, try to allocate it now
1180                  * without any locks in case it fails.
1181                  */
1182                 if (refill_pi_state_cache())
1183                         return -ENOMEM;
1184                 /*
1185                  * requeue_pi must wake as many tasks as it can, up to nr_wake
1186                  * + nr_requeue, since it acquires the rt_mutex prior to
1187                  * returning to userspace, so as to not leave the rt_mutex with
1188                  * waiters and no owner.  However, second and third wake-ups
1189                  * cannot be predicted as they involve race conditions with the
1190                  * first wake and a fault while looking up the pi_state.  Both
1191                  * pthread_cond_signal() and pthread_cond_broadcast() should
1192                  * use nr_wake=1.
1193                  */
1194                 if (nr_wake != 1)
1195                         return -EINVAL;
1196         }
1197
1198 retry:
1199         if (pi_state != NULL) {
1200                 /*
1201                  * We will have to lookup the pi_state again, so free this one
1202                  * to keep the accounting correct.
1203                  */
1204                 free_pi_state(pi_state);
1205                 pi_state = NULL;
1206         }
1207
1208         ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1);
1209         if (unlikely(ret != 0))
1210                 goto out;
1211         ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2);
1212         if (unlikely(ret != 0))
1213                 goto out_put_key1;
1214
1215         hb1 = hash_futex(&key1);
1216         hb2 = hash_futex(&key2);
1217
1218 retry_private:
1219         double_lock_hb(hb1, hb2);
1220
1221         if (likely(cmpval != NULL)) {
1222                 u32 curval;
1223
1224                 ret = get_futex_value_locked(&curval, uaddr1);
1225
1226                 if (unlikely(ret)) {
1227                         double_unlock_hb(hb1, hb2);
1228
1229                         ret = get_user(curval, uaddr1);
1230                         if (ret)
1231                                 goto out_put_keys;
1232
1233                         if (!(flags & FLAGS_SHARED))
1234                                 goto retry_private;
1235
1236                         put_futex_key(&key2);
1237                         put_futex_key(&key1);
1238                         goto retry;
1239                 }
1240                 if (curval != *cmpval) {
1241                         ret = -EAGAIN;
1242                         goto out_unlock;
1243                 }
1244         }
1245
1246         if (requeue_pi && (task_count - nr_wake < nr_requeue)) {
1247                 /*
1248                  * Attempt to acquire uaddr2 and wake the top waiter. If we
1249                  * intend to requeue waiters, force setting the FUTEX_WAITERS
1250                  * bit.  We force this here where we are able to easily handle
1251                  * faults rather in the requeue loop below.
1252                  */
1253                 ret = futex_proxy_trylock_atomic(uaddr2, hb1, hb2, &key1,
1254                                                  &key2, &pi_state, nr_requeue);
1255
1256                 /*
1257                  * At this point the top_waiter has either taken uaddr2 or is
1258                  * waiting on it.  If the former, then the pi_state will not
1259                  * exist yet, look it up one more time to ensure we have a
1260                  * reference to it.
1261                  */
1262                 if (ret == 1) {
1263                         WARN_ON(pi_state);
1264                         drop_count++;
1265                         task_count++;
1266                         ret = get_futex_value_locked(&curval2, uaddr2);
1267                         if (!ret)
1268                                 ret = lookup_pi_state(curval2, hb2, &key2,
1269                                                       &pi_state);
1270                 }
1271
1272                 switch (ret) {
1273                 case 0:
1274                         break;
1275                 case -EFAULT:
1276                         double_unlock_hb(hb1, hb2);
1277                         put_futex_key(&key2);
1278                         put_futex_key(&key1);
1279                         ret = fault_in_user_writeable(uaddr2);
1280                         if (!ret)
1281                                 goto retry;
1282                         goto out;
1283                 case -EAGAIN:
1284                         /* The owner was exiting, try again. */
1285                         double_unlock_hb(hb1, hb2);
1286                         put_futex_key(&key2);
1287                         put_futex_key(&key1);
1288                         cond_resched();
1289                         goto retry;
1290                 default:
1291                         goto out_unlock;
1292                 }
1293         }
1294
1295         head1 = &hb1->chain;
1296         plist_for_each_entry_safe(this, next, head1, list) {
1297                 if (task_count - nr_wake >= nr_requeue)
1298                         break;
1299
1300                 if (!match_futex(&this->key, &key1))
1301                         continue;
1302
1303                 /*
1304                  * FUTEX_WAIT_REQEUE_PI and FUTEX_CMP_REQUEUE_PI should always
1305                  * be paired with each other and no other futex ops.
1306                  */
1307                 if ((requeue_pi && !this->rt_waiter) ||
1308                     (!requeue_pi && this->rt_waiter)) {
1309                         ret = -EINVAL;
1310                         break;
1311                 }
1312
1313                 /*
1314                  * Wake nr_wake waiters.  For requeue_pi, if we acquired the
1315                  * lock, we already woke the top_waiter.  If not, it will be
1316                  * woken by futex_unlock_pi().
1317                  */
1318                 if (++task_count <= nr_wake && !requeue_pi) {
1319                         wake_futex(this);
1320                         continue;
1321                 }
1322
1323                 /* Ensure we requeue to the expected futex for requeue_pi. */
1324                 if (requeue_pi && !match_futex(this->requeue_pi_key, &key2)) {
1325                         ret = -EINVAL;
1326                         break;
1327                 }
1328
1329                 /*
1330                  * Requeue nr_requeue waiters and possibly one more in the case
1331                  * of requeue_pi if we couldn't acquire the lock atomically.
1332                  */
1333                 if (requeue_pi) {
1334                         /* Prepare the waiter to take the rt_mutex. */
1335                         atomic_inc(&pi_state->refcount);
1336                         this->pi_state = pi_state;
1337                         ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,
1338                                                         this->rt_waiter,
1339                                                         this->task, 1);
1340                         if (ret == 1) {
1341                                 /* We got the lock. */
1342                                 requeue_pi_wake_futex(this, &key2, hb2);
1343                                 drop_count++;
1344                                 continue;
1345                         } else if (ret) {
1346                                 /* -EDEADLK */
1347                                 this->pi_state = NULL;
1348                                 free_pi_state(pi_state);
1349                                 goto out_unlock;
1350                         }
1351                 }
1352                 requeue_futex(this, hb1, hb2, &key2);
1353                 drop_count++;
1354         }
1355
1356 out_unlock:
1357         double_unlock_hb(hb1, hb2);
1358
1359         /*
1360          * drop_futex_key_refs() must be called outside the spinlocks. During
1361          * the requeue we moved futex_q's from the hash bucket at key1 to the
1362          * one at key2 and updated their key pointer.  We no longer need to
1363          * hold the references to key1.
1364          */
1365         while (--drop_count >= 0)
1366                 drop_futex_key_refs(&key1);
1367
1368 out_put_keys:
1369         put_futex_key(&key2);
1370 out_put_key1:
1371         put_futex_key(&key1);
1372 out:
1373         if (pi_state != NULL)
1374                 free_pi_state(pi_state);
1375         return ret ? ret : task_count;
1376 }
1377
1378 /* The key must be already stored in q->key. */
1379 static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
1380         __acquires(&hb->lock)
1381 {
1382         struct futex_hash_bucket *hb;
1383
1384         hb = hash_futex(&q->key);
1385         q->lock_ptr = &hb->lock;
1386
1387         spin_lock(&hb->lock);
1388         return hb;
1389 }
1390
1391 static inline void
1392 queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
1393         __releases(&hb->lock)
1394 {
1395         spin_unlock(&hb->lock);
1396 }
1397
1398 /**
1399  * queue_me() - Enqueue the futex_q on the futex_hash_bucket
1400  * @q:  The futex_q to enqueue
1401  * @hb: The destination hash bucket
1402  *
1403  * The hb->lock must be held by the caller, and is released here. A call to
1404  * queue_me() is typically paired with exactly one call to unqueue_me().  The
1405  * exceptions involve the PI related operations, which may use unqueue_me_pi()
1406  * or nothing if the unqueue is done as part of the wake process and the unqueue
1407  * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
1408  * an example).
1409  */
1410 static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
1411         __releases(&hb->lock)
1412 {
1413         int prio;
1414
1415         /*
1416          * The priority used to register this element is
1417          * - either the real thread-priority for the real-time threads
1418          * (i.e. threads with a priority lower than MAX_RT_PRIO)
1419          * - or MAX_RT_PRIO for non-RT threads.
1420          * Thus, all RT-threads are woken first in priority order, and
1421          * the others are woken last, in FIFO order.
1422          */
1423         prio = min(current->normal_prio, MAX_RT_PRIO);
1424
1425         plist_node_init(&q->list, prio);
1426 #ifdef CONFIG_DEBUG_PI_LIST
1427         q->list.plist.spinlock = &hb->lock;
1428 #endif
1429         plist_add(&q->list, &hb->chain);
1430         q->task = current;
1431         spin_unlock(&hb->lock);
1432 }
1433
1434 /**
1435  * unqueue_me() - Remove the futex_q from its futex_hash_bucket
1436  * @q:  The futex_q to unqueue
1437  *
1438  * The q->lock_ptr must not be held by the caller. A call to unqueue_me() must
1439  * be paired with exactly one earlier call to queue_me().
1440  *
1441  * Returns:
1442  *   1 - if the futex_q was still queued (and we removed unqueued it)
1443  *   0 - if the futex_q was already removed by the waking thread
1444  */
1445 static int unqueue_me(struct futex_q *q)
1446 {
1447         spinlock_t *lock_ptr;
1448         int ret = 0;
1449
1450         /* In the common case we don't take the spinlock, which is nice. */
1451 retry:
1452         lock_ptr = q->lock_ptr;
1453         barrier();
1454         if (lock_ptr != NULL) {
1455                 spin_lock(lock_ptr);
1456                 /*
1457                  * q->lock_ptr can change between reading it and
1458                  * spin_lock(), causing us to take the wrong lock.  This
1459                  * corrects the race condition.
1460                  *
1461                  * Reasoning goes like this: if we have the wrong lock,
1462                  * q->lock_ptr must have changed (maybe several times)
1463                  * between reading it and the spin_lock().  It can
1464                  * change again after the spin_lock() but only if it was
1465                  * already changed before the spin_lock().  It cannot,
1466                  * however, change back to the original value.  Therefore
1467                  * we can detect whether we acquired the correct lock.
1468                  */
1469                 if (unlikely(lock_ptr != q->lock_ptr)) {
1470                         spin_unlock(lock_ptr);
1471                         goto retry;
1472                 }
1473                 WARN_ON(plist_node_empty(&q->list));
1474                 plist_del(&q->list, &q->list.plist);
1475
1476                 BUG_ON(q->pi_state);
1477
1478                 spin_unlock(lock_ptr);
1479                 ret = 1;
1480         }
1481
1482         drop_futex_key_refs(&q->key);
1483         return ret;
1484 }
1485
1486 /*
1487  * PI futexes can not be requeued and must remove themself from the
1488  * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
1489  * and dropped here.
1490  */
1491 static void unqueue_me_pi(struct futex_q *q)
1492         __releases(q->lock_ptr)
1493 {
1494         WARN_ON(plist_node_empty(&q->list));
1495         plist_del(&q->list, &q->list.plist);
1496
1497         BUG_ON(!q->pi_state);
1498         free_pi_state(q->pi_state);
1499         q->pi_state = NULL;
1500
1501         spin_unlock(q->lock_ptr);
1502 }
1503
1504 /*
1505  * Fixup the pi_state owner with the new owner.
1506  *
1507  * Must be called with hash bucket lock held and mm->sem held for non
1508  * private futexes.
1509  */
1510 static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
1511                                 struct task_struct *newowner)
1512 {
1513         u32 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
1514         struct futex_pi_state *pi_state = q->pi_state;
1515         struct task_struct *oldowner = pi_state->owner;
1516         u32 uval, curval, newval;
1517         int ret;
1518
1519         /* Owner died? */
1520         if (!pi_state->owner)
1521                 newtid |= FUTEX_OWNER_DIED;
1522
1523         /*
1524          * We are here either because we stole the rtmutex from the
1525          * pending owner or we are the pending owner which failed to
1526          * get the rtmutex. We have to replace the pending owner TID
1527          * in the user space variable. This must be atomic as we have
1528          * to preserve the owner died bit here.
1529          *
1530          * Note: We write the user space value _before_ changing the pi_state
1531          * because we can fault here. Imagine swapped out pages or a fork
1532          * that marked all the anonymous memory readonly for cow.
1533          *
1534          * Modifying pi_state _before_ the user space value would
1535          * leave the pi_state in an inconsistent state when we fault
1536          * here, because we need to drop the hash bucket lock to
1537          * handle the fault. This might be observed in the PID check
1538          * in lookup_pi_state.
1539          */
1540 retry:
1541         if (get_futex_value_locked(&uval, uaddr))
1542                 goto handle_fault;
1543
1544         while (1) {
1545                 newval = (uval & FUTEX_OWNER_DIED) | newtid;
1546
1547                 curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
1548
1549                 if (curval == -EFAULT)
1550                         goto handle_fault;
1551                 if (curval == uval)
1552                         break;
1553                 uval = curval;
1554         }
1555
1556         /*
1557          * We fixed up user space. Now we need to fix the pi_state
1558          * itself.
1559          */
1560         if (pi_state->owner != NULL) {
1561                 raw_spin_lock_irq(&pi_state->owner->pi_lock);
1562                 WARN_ON(list_empty(&pi_state->list));
1563                 list_del_init(&pi_state->list);
1564                 raw_spin_unlock_irq(&pi_state->owner->pi_lock);
1565         }
1566
1567         pi_state->owner = newowner;
1568
1569         raw_spin_lock_irq(&newowner->pi_lock);
1570         WARN_ON(!list_empty(&pi_state->list));
1571         list_add(&pi_state->list, &newowner->pi_state_list);
1572         raw_spin_unlock_irq(&newowner->pi_lock);
1573         return 0;
1574
1575         /*
1576          * To handle the page fault we need to drop the hash bucket
1577          * lock here. That gives the other task (either the pending
1578          * owner itself or the task which stole the rtmutex) the
1579          * chance to try the fixup of the pi_state. So once we are
1580          * back from handling the fault we need to check the pi_state
1581          * after reacquiring the hash bucket lock and before trying to
1582          * do another fixup. When the fixup has been done already we
1583          * simply return.
1584          */
1585 handle_fault:
1586         spin_unlock(q->lock_ptr);
1587
1588         ret = fault_in_user_writeable(uaddr);
1589
1590         spin_lock(q->lock_ptr);
1591
1592         /*
1593          * Check if someone else fixed it for us:
1594          */
1595         if (pi_state->owner != oldowner)
1596                 return 0;
1597
1598         if (ret)
1599                 return ret;
1600
1601         goto retry;
1602 }
1603
1604 static long futex_wait_restart(struct restart_block *restart);
1605
1606 /**
1607  * fixup_owner() - Post lock pi_state and corner case management
1608  * @uaddr:      user address of the futex
1609  * @q:          futex_q (contains pi_state and access to the rt_mutex)
1610  * @locked:     if the attempt to take the rt_mutex succeeded (1) or not (0)
1611  *
1612  * After attempting to lock an rt_mutex, this function is called to cleanup
1613  * the pi_state owner as well as handle race conditions that may allow us to
1614  * acquire the lock. Must be called with the hb lock held.
1615  *
1616  * Returns:
1617  *  1 - success, lock taken
1618  *  0 - success, lock not taken
1619  * <0 - on error (-EFAULT)
1620  */
1621 static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
1622 {
1623         struct task_struct *owner;
1624         int ret = 0;
1625
1626         if (locked) {
1627                 /*
1628                  * Got the lock. We might not be the anticipated owner if we
1629                  * did a lock-steal - fix up the PI-state in that case:
1630                  */
1631                 if (q->pi_state->owner != current)
1632                         ret = fixup_pi_state_owner(uaddr, q, current);
1633                 goto out;
1634         }
1635
1636         /*
1637          * Catch the rare case, where the lock was released when we were on the
1638          * way back before we locked the hash bucket.
1639          */
1640         if (q->pi_state->owner == current) {
1641                 /*
1642                  * Try to get the rt_mutex now. This might fail as some other
1643                  * task acquired the rt_mutex after we removed ourself from the
1644                  * rt_mutex waiters list.
1645                  */
1646                 if (rt_mutex_trylock(&q->pi_state->pi_mutex)) {
1647                         locked = 1;
1648                         goto out;
1649                 }
1650
1651                 /*
1652                  * pi_state is incorrect, some other task did a lock steal and
1653                  * we returned due to timeout or signal without taking the
1654                  * rt_mutex. Too late. We can access the rt_mutex_owner without
1655                  * locking, as the other task is now blocked on the hash bucket
1656                  * lock. Fix the state up.
1657                  */
1658                 owner = rt_mutex_owner(&q->pi_state->pi_mutex);
1659                 ret = fixup_pi_state_owner(uaddr, q, owner);
1660                 goto out;
1661         }
1662
1663         /*
1664          * Paranoia check. If we did not take the lock, then we should not be
1665          * the owner, nor the pending owner, of the rt_mutex.
1666          */
1667         if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
1668                 printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "
1669                                 "pi-state %p\n", ret,
1670                                 q->pi_state->pi_mutex.owner,
1671                                 q->pi_state->owner);
1672
1673 out:
1674         return ret ? ret : locked;
1675 }
1676
1677 /**
1678  * futex_wait_queue_me() - queue_me() and wait for wakeup, timeout, or signal
1679  * @hb:         the futex hash bucket, must be locked by the caller
1680  * @q:          the futex_q to queue up on
1681  * @timeout:    the prepared hrtimer_sleeper, or null for no timeout
1682  */
1683 static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
1684                                 struct hrtimer_sleeper *timeout)
1685 {
1686         /*
1687          * The task state is guaranteed to be set before another task can
1688          * wake it. set_current_state() is implemented using set_mb() and
1689          * queue_me() calls spin_unlock() upon completion, both serializing
1690          * access to the hash list and forcing another memory barrier.
1691          */
1692         set_current_state(TASK_INTERRUPTIBLE);
1693         queue_me(q, hb);
1694
1695         /* Arm the timer */
1696         if (timeout) {
1697                 hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
1698                 if (!hrtimer_active(&timeout->timer))
1699                         timeout->task = NULL;
1700         }
1701
1702         /*
1703          * If we have been removed from the hash list, then another task
1704          * has tried to wake us, and we can skip the call to schedule().
1705          */
1706         if (likely(!plist_node_empty(&q->list))) {
1707                 /*
1708                  * If the timer has already expired, current will already be
1709                  * flagged for rescheduling. Only call schedule if there
1710                  * is no timeout, or if it has yet to expire.
1711                  */
1712                 if (!timeout || timeout->task)
1713                         schedule();
1714         }
1715         __set_current_state(TASK_RUNNING);
1716 }
1717
1718 /**
1719  * futex_wait_setup() - Prepare to wait on a futex
1720  * @uaddr:      the futex userspace address
1721  * @val:        the expected value
1722  * @flags:      futex flags (FLAGS_SHARED, etc.)
1723  * @q:          the associated futex_q
1724  * @hb:         storage for hash_bucket pointer to be returned to caller
1725  *
1726  * Setup the futex_q and locate the hash_bucket.  Get the futex value and
1727  * compare it with the expected value.  Handle atomic faults internally.
1728  * Return with the hb lock held and a q.key reference on success, and unlocked
1729  * with no q.key reference on failure.
1730  *
1731  * Returns:
1732  *  0 - uaddr contains val and hb has been locked
1733  * <1 - -EFAULT or -EWOULDBLOCK (uaddr does not contain val) and hb is unlcoked
1734  */
1735 static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
1736                            struct futex_q *q, struct futex_hash_bucket **hb)
1737 {
1738         u32 uval;
1739         int ret;
1740
1741         /*
1742          * Access the page AFTER the hash-bucket is locked.
1743          * Order is important:
1744          *
1745          *   Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
1746          *   Userspace waker:  if (cond(var)) { var = new; futex_wake(&var); }
1747          *
1748          * The basic logical guarantee of a futex is that it blocks ONLY
1749          * if cond(var) is known to be true at the time of blocking, for
1750          * any cond.  If we queued after testing *uaddr, that would open
1751          * a race condition where we could block indefinitely with
1752          * cond(var) false, which would violate the guarantee.
1753          *
1754          * A consequence is that futex_wait() can return zero and absorb
1755          * a wakeup when *uaddr != val on entry to the syscall.  This is
1756          * rare, but normal.
1757          */
1758 retry:
1759         ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key);
1760         if (unlikely(ret != 0))
1761                 return ret;
1762
1763 retry_private:
1764         *hb = queue_lock(q);
1765
1766         ret = get_futex_value_locked(&uval, uaddr);
1767
1768         if (ret) {
1769                 queue_unlock(q, *hb);
1770
1771                 ret = get_user(uval, uaddr);
1772                 if (ret)
1773                         goto out;
1774
1775                 if (!(flags & FLAGS_SHARED))
1776                         goto retry_private;
1777
1778                 put_futex_key(&q->key);
1779                 goto retry;
1780         }
1781
1782         if (uval != val) {
1783                 queue_unlock(q, *hb);
1784                 ret = -EWOULDBLOCK;
1785         }
1786
1787 out:
1788         if (ret)
1789                 put_futex_key(&q->key);
1790         return ret;
1791 }
1792
1793 static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
1794                       ktime_t *abs_time, u32 bitset)
1795 {
1796         struct hrtimer_sleeper timeout, *to = NULL;
1797         struct restart_block *restart;
1798         struct futex_hash_bucket *hb;
1799         struct futex_q q = futex_q_init;
1800         int ret;
1801
1802         if (!bitset)
1803                 return -EINVAL;
1804         q.bitset = bitset;
1805
1806         if (abs_time) {
1807                 to = &timeout;
1808
1809                 hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
1810                                       CLOCK_REALTIME : CLOCK_MONOTONIC,
1811                                       HRTIMER_MODE_ABS);
1812                 hrtimer_init_sleeper(to, current);
1813                 hrtimer_set_expires_range_ns(&to->timer, *abs_time,
1814                                              current->timer_slack_ns);
1815         }
1816
1817 retry:
1818         /*
1819          * Prepare to wait on uaddr. On success, holds hb lock and increments
1820          * q.key refs.
1821          */
1822         ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
1823         if (ret)
1824                 goto out;
1825
1826         /* queue_me and wait for wakeup, timeout, or a signal. */
1827         futex_wait_queue_me(hb, &q, to);
1828
1829         /* If we were woken (and unqueued), we succeeded, whatever. */
1830         ret = 0;
1831         /* unqueue_me() drops q.key ref */
1832         if (!unqueue_me(&q))
1833                 goto out;
1834         ret = -ETIMEDOUT;
1835         if (to && !to->task)
1836                 goto out;
1837
1838         /*
1839          * We expect signal_pending(current), but we might be the
1840          * victim of a spurious wakeup as well.
1841          */
1842         if (!signal_pending(current))
1843                 goto retry;
1844
1845         ret = -ERESTARTSYS;
1846         if (!abs_time)
1847                 goto out;
1848
1849         restart = &current_thread_info()->restart_block;
1850         restart->fn = futex_wait_restart;
1851         restart->futex.uaddr = uaddr;
1852         restart->futex.val = val;
1853         restart->futex.time = abs_time->tv64;
1854         restart->futex.bitset = bitset;
1855         restart->futex.flags = flags;
1856
1857         ret = -ERESTART_RESTARTBLOCK;
1858
1859 out:
1860         if (to) {
1861                 hrtimer_cancel(&to->timer);
1862                 destroy_hrtimer_on_stack(&to->timer);
1863         }
1864         return ret;
1865 }
1866
1867
1868 static long futex_wait_restart(struct restart_block *restart)
1869 {
1870         u32 __user *uaddr = restart->futex.uaddr;
1871         ktime_t t, *tp = NULL;
1872
1873         if (restart->futex.flags & FLAGS_HAS_TIMEOUT) {
1874                 t.tv64 = restart->futex.time;
1875                 tp = &t;
1876         }
1877         restart->fn = do_no_restart_syscall;
1878
1879         return (long)futex_wait(uaddr, restart->futex.flags,
1880                                 restart->futex.val, tp, restart->futex.bitset);
1881 }
1882
1883
1884 /*
1885  * Userspace tried a 0 -> TID atomic transition of the futex value
1886  * and failed. The kernel side here does the whole locking operation:
1887  * if there are waiters then it will block, it does PI, etc. (Due to
1888  * races the kernel might see a 0 value of the futex too.)
1889  */
1890 static int futex_lock_pi(u32 __user *uaddr, unsigned int flags, int detect,
1891                          ktime_t *time, int trylock)
1892 {
1893         struct hrtimer_sleeper timeout, *to = NULL;
1894         struct futex_hash_bucket *hb;
1895         struct futex_q q = futex_q_init;
1896         int res, ret;
1897
1898         if (refill_pi_state_cache())
1899                 return -ENOMEM;
1900
1901         if (time) {
1902                 to = &timeout;
1903                 hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
1904                                       HRTIMER_MODE_ABS);
1905                 hrtimer_init_sleeper(to, current);
1906                 hrtimer_set_expires(&to->timer, *time);
1907         }
1908
1909 retry:
1910         ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key);
1911         if (unlikely(ret != 0))
1912                 goto out;
1913
1914 retry_private:
1915         hb = queue_lock(&q);
1916
1917         ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &q.pi_state, current, 0);
1918         if (unlikely(ret)) {
1919                 switch (ret) {
1920                 case 1:
1921                         /* We got the lock. */
1922                         ret = 0;
1923                         goto out_unlock_put_key;
1924                 case -EFAULT:
1925                         goto uaddr_faulted;
1926                 case -EAGAIN:
1927                         /*
1928                          * Task is exiting and we just wait for the
1929                          * exit to complete.
1930                          */
1931                         queue_unlock(&q, hb);
1932                         put_futex_key(&q.key);
1933                         cond_resched();
1934                         goto retry;
1935                 default:
1936                         goto out_unlock_put_key;
1937                 }
1938         }
1939
1940         /*
1941          * Only actually queue now that the atomic ops are done:
1942          */
1943         queue_me(&q, hb);
1944
1945         WARN_ON(!q.pi_state);
1946         /*
1947          * Block on the PI mutex:
1948          */
1949         if (!trylock)
1950                 ret = rt_mutex_timed_lock(&q.pi_state->pi_mutex, to, 1);
1951         else {
1952                 ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
1953                 /* Fixup the trylock return value: */
1954                 ret = ret ? 0 : -EWOULDBLOCK;
1955         }
1956
1957         spin_lock(q.lock_ptr);
1958         /*
1959          * Fixup the pi_state owner and possibly acquire the lock if we
1960          * haven't already.
1961          */
1962         res = fixup_owner(uaddr, &q, !ret);
1963         /*
1964          * If fixup_owner() returned an error, proprogate that.  If it acquired
1965          * the lock, clear our -ETIMEDOUT or -EINTR.
1966          */
1967         if (res)
1968                 ret = (res < 0) ? res : 0;
1969
1970         /*
1971          * If fixup_owner() faulted and was unable to handle the fault, unlock
1972          * it and return the fault to userspace.
1973          */
1974         if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current))
1975                 rt_mutex_unlock(&q.pi_state->pi_mutex);
1976
1977         /* Unqueue and drop the lock */
1978         unqueue_me_pi(&q);
1979
1980         goto out_put_key;
1981
1982 out_unlock_put_key:
1983         queue_unlock(&q, hb);
1984
1985 out_put_key:
1986         put_futex_key(&q.key);
1987 out:
1988         if (to)
1989                 destroy_hrtimer_on_stack(&to->timer);
1990         return ret != -EINTR ? ret : -ERESTARTNOINTR;
1991
1992 uaddr_faulted:
1993         queue_unlock(&q, hb);
1994
1995         ret = fault_in_user_writeable(uaddr);
1996         if (ret)
1997                 goto out_put_key;
1998
1999         if (!(flags & FLAGS_SHARED))
2000                 goto retry_private;
2001
2002         put_futex_key(&q.key);
2003         goto retry;
2004 }
2005
2006 /*
2007  * Userspace attempted a TID -> 0 atomic transition, and failed.
2008  * This is the in-kernel slowpath: we look up the PI state (if any),
2009  * and do the rt-mutex unlock.
2010  */
2011 static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
2012 {
2013         struct futex_hash_bucket *hb;
2014         struct futex_q *this, *next;
2015         u32 uval;
2016         struct plist_head *head;
2017         union futex_key key = FUTEX_KEY_INIT;
2018         int ret;
2019
2020 retry:
2021         if (get_user(uval, uaddr))
2022                 return -EFAULT;
2023         /*
2024          * We release only a lock we actually own:
2025          */
2026         if ((uval & FUTEX_TID_MASK) != task_pid_vnr(current))
2027                 return -EPERM;
2028
2029         ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key);
2030         if (unlikely(ret != 0))
2031                 goto out;
2032
2033         hb = hash_futex(&key);
2034         spin_lock(&hb->lock);
2035
2036         /*
2037          * To avoid races, try to do the TID -> 0 atomic transition
2038          * again. If it succeeds then we can return without waking
2039          * anyone else up:
2040          */
2041         if (!(uval & FUTEX_OWNER_DIED))
2042                 uval = cmpxchg_futex_value_locked(uaddr, task_pid_vnr(current), 0);
2043
2044
2045         if (unlikely(uval == -EFAULT))
2046                 goto pi_faulted;
2047         /*
2048          * Rare case: we managed to release the lock atomically,
2049          * no need to wake anyone else up:
2050          */
2051         if (unlikely(uval == task_pid_vnr(current)))
2052                 goto out_unlock;
2053
2054         /*
2055          * Ok, other tasks may need to be woken up - check waiters
2056          * and do the wakeup if necessary:
2057          */
2058         head = &hb->chain;
2059
2060         plist_for_each_entry_safe(this, next, head, list) {
2061                 if (!match_futex (&this->key, &key))
2062                         continue;
2063                 ret = wake_futex_pi(uaddr, uval, this);
2064                 /*
2065                  * The atomic access to the futex value
2066                  * generated a pagefault, so retry the
2067                  * user-access and the wakeup:
2068                  */
2069                 if (ret == -EFAULT)
2070                         goto pi_faulted;
2071                 goto out_unlock;
2072         }
2073         /*
2074          * No waiters - kernel unlocks the futex:
2075          */
2076         if (!(uval & FUTEX_OWNER_DIED)) {
2077                 ret = unlock_futex_pi(uaddr, uval);
2078                 if (ret == -EFAULT)
2079                         goto pi_faulted;
2080         }
2081
2082 out_unlock:
2083         spin_unlock(&hb->lock);
2084         put_futex_key(&key);
2085
2086 out:
2087         return ret;
2088
2089 pi_faulted:
2090         spin_unlock(&hb->lock);
2091         put_futex_key(&key);
2092
2093         ret = fault_in_user_writeable(uaddr);
2094         if (!ret)
2095                 goto retry;
2096
2097         return ret;
2098 }
2099
2100 /**
2101  * handle_early_requeue_pi_wakeup() - Detect early wakeup on the initial futex
2102  * @hb:         the hash_bucket futex_q was original enqueued on
2103  * @q:          the futex_q woken while waiting to be requeued
2104  * @key2:       the futex_key of the requeue target futex
2105  * @timeout:    the timeout associated with the wait (NULL if none)
2106  *
2107  * Detect if the task was woken on the initial futex as opposed to the requeue
2108  * target futex.  If so, determine if it was a timeout or a signal that caused
2109  * the wakeup and return the appropriate error code to the caller.  Must be
2110  * called with the hb lock held.
2111  *
2112  * Returns
2113  *  0 - no early wakeup detected
2114  * <0 - -ETIMEDOUT or -ERESTARTNOINTR
2115  */
2116 static inline
2117 int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb,
2118                                    struct futex_q *q, union futex_key *key2,
2119                                    struct hrtimer_sleeper *timeout)
2120 {
2121         int ret = 0;
2122
2123         /*
2124          * With the hb lock held, we avoid races while we process the wakeup.
2125          * We only need to hold hb (and not hb2) to ensure atomicity as the
2126          * wakeup code can't change q.key from uaddr to uaddr2 if we hold hb.
2127          * It can't be requeued from uaddr2 to something else since we don't
2128          * support a PI aware source futex for requeue.
2129          */
2130         if (!match_futex(&q->key, key2)) {
2131                 WARN_ON(q->lock_ptr && (&hb->lock != q->lock_ptr));
2132                 /*
2133                  * We were woken prior to requeue by a timeout or a signal.
2134                  * Unqueue the futex_q and determine which it was.
2135                  */
2136                 plist_del(&q->list, &q->list.plist);
2137
2138                 /* Handle spurious wakeups gracefully */
2139                 ret = -EWOULDBLOCK;
2140                 if (timeout && !timeout->task)
2141                         ret = -ETIMEDOUT;
2142                 else if (signal_pending(current))
2143                         ret = -ERESTARTNOINTR;
2144         }
2145         return ret;
2146 }
2147
2148 /**
2149  * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2
2150  * @uaddr:      the futex we initially wait on (non-pi)
2151  * @flags:      futex flags (FLAGS_SHARED, FLAGS_CLOCKRT, etc.), they must be
2152  *              the same type, no requeueing from private to shared, etc.
2153  * @val:        the expected value of uaddr
2154  * @abs_time:   absolute timeout
2155  * @bitset:     32 bit wakeup bitset set by userspace, defaults to all
2156  * @clockrt:    whether to use CLOCK_REALTIME (1) or CLOCK_MONOTONIC (0)
2157  * @uaddr2:     the pi futex we will take prior to returning to user-space
2158  *
2159  * The caller will wait on uaddr and will be requeued by futex_requeue() to
2160  * uaddr2 which must be PI aware.  Normal wakeup will wake on uaddr2 and
2161  * complete the acquisition of the rt_mutex prior to returning to userspace.
2162  * This ensures the rt_mutex maintains an owner when it has waiters; without
2163  * one, the pi logic wouldn't know which task to boost/deboost, if there was a
2164  * need to.
2165  *
2166  * We call schedule in futex_wait_queue_me() when we enqueue and return there
2167  * via the following:
2168  * 1) wakeup on uaddr2 after an atomic lock acquisition by futex_requeue()
2169  * 2) wakeup on uaddr2 after a requeue
2170  * 3) signal
2171  * 4) timeout
2172  *
2173  * If 3, cleanup and return -ERESTARTNOINTR.
2174  *
2175  * If 2, we may then block on trying to take the rt_mutex and return via:
2176  * 5) successful lock
2177  * 6) signal
2178  * 7) timeout
2179  * 8) other lock acquisition failure
2180  *
2181  * If 6, return -EWOULDBLOCK (restarting the syscall would do the same).
2182  *
2183  * If 4 or 7, we cleanup and return with -ETIMEDOUT.
2184  *
2185  * Returns:
2186  *  0 - On success
2187  * <0 - On error
2188  */
2189 static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
2190                                  u32 val, ktime_t *abs_time, u32 bitset,
2191                                  u32 __user *uaddr2)
2192 {
2193         struct hrtimer_sleeper timeout, *to = NULL;
2194         struct rt_mutex_waiter rt_waiter;
2195         struct rt_mutex *pi_mutex = NULL;
2196         struct futex_hash_bucket *hb;
2197         union futex_key key2 = FUTEX_KEY_INIT;
2198         struct futex_q q = futex_q_init;
2199         int res, ret;
2200
2201         if (!bitset)
2202                 return -EINVAL;
2203
2204         if (abs_time) {
2205                 to = &timeout;
2206                 hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
2207                                       CLOCK_REALTIME : CLOCK_MONOTONIC,
2208                                       HRTIMER_MODE_ABS);
2209                 hrtimer_init_sleeper(to, current);
2210                 hrtimer_set_expires_range_ns(&to->timer, *abs_time,
2211                                              current->timer_slack_ns);
2212         }
2213
2214         /*
2215          * The waiter is allocated on our stack, manipulated by the requeue
2216          * code while we sleep on uaddr.
2217          */
2218         debug_rt_mutex_init_waiter(&rt_waiter);
2219         rt_waiter.task = NULL;
2220
2221         ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2);
2222         if (unlikely(ret != 0))
2223                 goto out;
2224
2225         q.bitset = bitset;
2226         q.rt_waiter = &rt_waiter;
2227         q.requeue_pi_key = &key2;
2228
2229         /*
2230          * Prepare to wait on uaddr. On success, increments q.key (key1) ref
2231          * count.
2232          */
2233         ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
2234         if (ret)
2235                 goto out_key2;
2236
2237         /* Queue the futex_q, drop the hb lock, wait for wakeup. */
2238         futex_wait_queue_me(hb, &q, to);
2239
2240         spin_lock(&hb->lock);
2241         ret = handle_early_requeue_pi_wakeup(hb, &q, &key2, to);
2242         spin_unlock(&hb->lock);
2243         if (ret)
2244                 goto out_put_keys;
2245
2246         /*
2247          * In order for us to be here, we know our q.key == key2, and since
2248          * we took the hb->lock above, we also know that futex_requeue() has
2249          * completed and we no longer have to concern ourselves with a wakeup
2250          * race with the atomic proxy lock acquisition by the requeue code. The
2251          * futex_requeue dropped our key1 reference and incremented our key2
2252          * reference count.
2253          */
2254
2255         /* Check if the requeue code acquired the second futex for us. */
2256         if (!q.rt_waiter) {
2257                 /*
2258                  * Got the lock. We might not be the anticipated owner if we
2259                  * did a lock-steal - fix up the PI-state in that case.
2260                  */
2261                 if (q.pi_state && (q.pi_state->owner != current)) {
2262                         spin_lock(q.lock_ptr);
2263                         ret = fixup_pi_state_owner(uaddr2, &q, current);
2264                         spin_unlock(q.lock_ptr);
2265                 }
2266         } else {
2267                 /*
2268                  * We have been woken up by futex_unlock_pi(), a timeout, or a
2269                  * signal.  futex_unlock_pi() will not destroy the lock_ptr nor
2270                  * the pi_state.
2271                  */
2272                 WARN_ON(!&q.pi_state);
2273                 pi_mutex = &q.pi_state->pi_mutex;
2274                 ret = rt_mutex_finish_proxy_lock(pi_mutex, to, &rt_waiter, 1);
2275                 debug_rt_mutex_free_waiter(&rt_waiter);
2276
2277                 spin_lock(q.lock_ptr);
2278                 /*
2279                  * Fixup the pi_state owner and possibly acquire the lock if we
2280                  * haven't already.
2281                  */
2282                 res = fixup_owner(uaddr2, &q, !ret);
2283                 /*
2284                  * If fixup_owner() returned an error, proprogate that.  If it
2285                  * acquired the lock, clear -ETIMEDOUT or -EINTR.
2286                  */
2287                 if (res)
2288                         ret = (res < 0) ? res : 0;
2289
2290                 /* Unqueue and drop the lock. */
2291                 unqueue_me_pi(&q);
2292         }
2293
2294         /*
2295          * If fixup_pi_state_owner() faulted and was unable to handle the
2296          * fault, unlock the rt_mutex and return the fault to userspace.
2297          */
2298         if (ret == -EFAULT) {
2299                 if (rt_mutex_owner(pi_mutex) == current)
2300                         rt_mutex_unlock(pi_mutex);
2301         } else if (ret == -EINTR) {
2302                 /*
2303                  * We've already been requeued, but cannot restart by calling
2304                  * futex_lock_pi() directly. We could restart this syscall, but
2305                  * it would detect that the user space "val" changed and return
2306                  * -EWOULDBLOCK.  Save the overhead of the restart and return
2307                  * -EWOULDBLOCK directly.
2308                  */
2309                 ret = -EWOULDBLOCK;
2310         }
2311
2312 out_put_keys:
2313         put_futex_key(&q.key);
2314 out_key2:
2315         put_futex_key(&key2);
2316
2317 out:
2318         if (to) {
2319                 hrtimer_cancel(&to->timer);
2320                 destroy_hrtimer_on_stack(&to->timer);
2321         }
2322         return ret;
2323 }
2324
2325 /*
2326  * Support for robust futexes: the kernel cleans up held futexes at
2327  * thread exit time.
2328  *
2329  * Implementation: user-space maintains a per-thread list of locks it
2330  * is holding. Upon do_exit(), the kernel carefully walks this list,
2331  * and marks all locks that are owned by this thread with the
2332  * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
2333  * always manipulated with the lock held, so the list is private and
2334  * per-thread. Userspace also maintains a per-thread 'list_op_pending'
2335  * field, to allow the kernel to clean up if the thread dies after
2336  * acquiring the lock, but just before it could have added itself to
2337  * the list. There can only be one such pending lock.
2338  */
2339
2340 /**
2341  * sys_set_robust_list() - Set the robust-futex list head of a task
2342  * @head:       pointer to the list-head
2343  * @len:        length of the list-head, as userspace expects
2344  */
2345 SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head,
2346                 size_t, len)
2347 {
2348         if (!futex_cmpxchg_enabled)
2349                 return -ENOSYS;
2350         /*
2351          * The kernel knows only one size for now:
2352          */
2353         if (unlikely(len != sizeof(*head)))
2354                 return -EINVAL;
2355
2356         current->robust_list = head;
2357
2358         return 0;
2359 }
2360
2361 /**
2362  * sys_get_robust_list() - Get the robust-futex list head of a task
2363  * @pid:        pid of the process [zero for current task]
2364  * @head_ptr:   pointer to a list-head pointer, the kernel fills it in
2365  * @len_ptr:    pointer to a length field, the kernel fills in the header size
2366  */
2367 SYSCALL_DEFINE3(get_robust_list, int, pid,
2368                 struct robust_list_head __user * __user *, head_ptr,
2369                 size_t __user *, len_ptr)
2370 {
2371         struct robust_list_head __user *head;
2372         unsigned long ret;
2373         const struct cred *cred = current_cred(), *pcred;
2374
2375         if (!futex_cmpxchg_enabled)
2376                 return -ENOSYS;
2377
2378         if (!pid)
2379                 head = current->robust_list;
2380         else {
2381                 struct task_struct *p;
2382
2383                 ret = -ESRCH;
2384                 rcu_read_lock();
2385                 p = find_task_by_vpid(pid);
2386                 if (!p)
2387                         goto err_unlock;
2388                 ret = -EPERM;
2389                 pcred = __task_cred(p);
2390                 if (cred->euid != pcred->euid &&
2391                     cred->euid != pcred->uid &&
2392                     !capable(CAP_SYS_PTRACE))
2393                         goto err_unlock;
2394                 head = p->robust_list;
2395                 rcu_read_unlock();
2396         }
2397
2398         if (put_user(sizeof(*head), len_ptr))
2399                 return -EFAULT;
2400         return put_user(head, head_ptr);
2401
2402 err_unlock:
2403         rcu_read_unlock();
2404
2405         return ret;
2406 }
2407
2408 /*
2409  * Process a futex-list entry, check whether it's owned by the
2410  * dying task, and do notification if so:
2411  */
2412 int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
2413 {
2414         u32 uval, nval, mval;
2415
2416 retry:
2417         if (get_user(uval, uaddr))
2418                 return -1;
2419
2420         if ((uval & FUTEX_TID_MASK) == task_pid_vnr(curr)) {
2421                 /*
2422                  * Ok, this dying thread is truly holding a futex
2423                  * of interest. Set the OWNER_DIED bit atomically
2424                  * via cmpxchg, and if the value had FUTEX_WAITERS
2425                  * set, wake up a waiter (if any). (We have to do a
2426                  * futex_wake() even if OWNER_DIED is already set -
2427                  * to handle the rare but possible case of recursive
2428                  * thread-death.) The rest of the cleanup is done in
2429                  * userspace.
2430                  */
2431                 mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
2432                 nval = futex_atomic_cmpxchg_inatomic(uaddr, uval, mval);
2433
2434                 if (nval == -EFAULT)
2435                         return -1;
2436
2437                 if (nval != uval)
2438                         goto retry;
2439
2440                 /*
2441                  * Wake robust non-PI futexes here. The wakeup of
2442                  * PI futexes happens in exit_pi_state():
2443                  */
2444                 if (!pi && (uval & FUTEX_WAITERS))
2445                         futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
2446         }
2447         return 0;
2448 }
2449
2450 /*
2451  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
2452  */
2453 static inline int fetch_robust_entry(struct robust_list __user **entry,
2454                                      struct robust_list __user * __user *head,
2455                                      unsigned int *pi)
2456 {
2457         unsigned long uentry;
2458
2459         if (get_user(uentry, (unsigned long __user *)head))
2460                 return -EFAULT;
2461
2462         *entry = (void __user *)(uentry & ~1UL);
2463         *pi = uentry & 1;
2464
2465         return 0;
2466 }
2467
2468 /*
2469  * Walk curr->robust_list (very carefully, it's a userspace list!)
2470  * and mark any locks found there dead, and notify any waiters.
2471  *
2472  * We silently return on any sign of list-walking problem.
2473  */
2474 void exit_robust_list(struct task_struct *curr)
2475 {
2476         struct robust_list_head __user *head = curr->robust_list;
2477         struct robust_list __user *entry, *next_entry, *pending;
2478         unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
2479         unsigned int uninitialized_var(next_pi);
2480         unsigned long futex_offset;
2481         int rc;
2482
2483         if (!futex_cmpxchg_enabled)
2484                 return;
2485
2486         /*
2487          * Fetch the list head (which was registered earlier, via
2488          * sys_set_robust_list()):
2489          */
2490         if (fetch_robust_entry(&entry, &head->list.next, &pi))
2491                 return;
2492         /*
2493          * Fetch the relative futex offset:
2494          */
2495         if (get_user(futex_offset, &head->futex_offset))
2496                 return;
2497         /*
2498          * Fetch any possibly pending lock-add first, and handle it
2499          * if it exists:
2500          */
2501         if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
2502                 return;
2503
2504         next_entry = NULL;      /* avoid warning with gcc */
2505         while (entry != &head->list) {
2506                 /*
2507                  * Fetch the next entry in the list before calling
2508                  * handle_futex_death:
2509                  */
2510                 rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
2511                 /*
2512                  * A pending lock might already be on the list, so
2513                  * don't process it twice:
2514                  */
2515                 if (entry != pending)
2516                         if (handle_futex_death((void __user *)entry + futex_offset,
2517                                                 curr, pi))
2518                                 return;
2519                 if (rc)
2520                         return;
2521                 entry = next_entry;
2522                 pi = next_pi;
2523                 /*
2524                  * Avoid excessively long or circular lists:
2525                  */
2526                 if (!--limit)
2527                         break;
2528
2529                 cond_resched();
2530         }
2531
2532         if (pending)
2533                 handle_futex_death((void __user *)pending + futex_offset,
2534                                    curr, pip);
2535 }
2536
2537 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
2538                 u32 __user *uaddr2, u32 val2, u32 val3)
2539 {
2540         int ret = -ENOSYS, cmd = op & FUTEX_CMD_MASK;
2541         unsigned int flags = 0;
2542
2543         if (!(op & FUTEX_PRIVATE_FLAG))
2544                 flags |= FLAGS_SHARED;
2545
2546         if (op & FUTEX_CLOCK_REALTIME) {
2547                 flags |= FLAGS_CLOCKRT;
2548                 if (cmd != FUTEX_WAIT_BITSET && cmd != FUTEX_WAIT_REQUEUE_PI)
2549                         return -ENOSYS;
2550         }
2551
2552         switch (cmd) {
2553         case FUTEX_WAIT:
2554                 val3 = FUTEX_BITSET_MATCH_ANY;
2555         case FUTEX_WAIT_BITSET:
2556                 ret = futex_wait(uaddr, flags, val, timeout, val3);
2557                 break;
2558         case FUTEX_WAKE:
2559                 val3 = FUTEX_BITSET_MATCH_ANY;
2560         case FUTEX_WAKE_BITSET:
2561                 ret = futex_wake(uaddr, flags, val, val3);
2562                 break;
2563         case FUTEX_REQUEUE:
2564                 ret = futex_requeue(uaddr, flags, uaddr2, val, val2, NULL, 0);
2565                 break;
2566         case FUTEX_CMP_REQUEUE:
2567                 ret = futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 0);
2568                 break;
2569         case FUTEX_WAKE_OP:
2570                 ret = futex_wake_op(uaddr, flags, uaddr2, val, val2, val3);
2571                 break;
2572         case FUTEX_LOCK_PI:
2573                 if (futex_cmpxchg_enabled)
2574                         ret = futex_lock_pi(uaddr, flags, val, timeout, 0);
2575                 break;
2576         case FUTEX_UNLOCK_PI:
2577                 if (futex_cmpxchg_enabled)
2578                         ret = futex_unlock_pi(uaddr, flags);
2579                 break;
2580         case FUTEX_TRYLOCK_PI:
2581                 if (futex_cmpxchg_enabled)
2582                         ret = futex_lock_pi(uaddr, flags, 0, timeout, 1);
2583                 break;
2584         case FUTEX_WAIT_REQUEUE_PI:
2585                 val3 = FUTEX_BITSET_MATCH_ANY;
2586                 ret = futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
2587                                             uaddr2);
2588                 break;
2589         case FUTEX_CMP_REQUEUE_PI:
2590                 ret = futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
2591                 break;
2592         default:
2593                 ret = -ENOSYS;
2594         }
2595         return ret;
2596 }
2597
2598
2599 SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
2600                 struct timespec __user *, utime, u32 __user *, uaddr2,
2601                 u32, val3)
2602 {
2603         struct timespec ts;
2604         ktime_t t, *tp = NULL;
2605         u32 val2 = 0;
2606         int cmd = op & FUTEX_CMD_MASK;
2607
2608         if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
2609                       cmd == FUTEX_WAIT_BITSET ||
2610                       cmd == FUTEX_WAIT_REQUEUE_PI)) {
2611                 if (copy_from_user(&ts, utime, sizeof(ts)) != 0)
2612                         return -EFAULT;
2613                 if (!timespec_valid(&ts))
2614                         return -EINVAL;
2615
2616                 t = timespec_to_ktime(ts);
2617                 if (cmd == FUTEX_WAIT)
2618                         t = ktime_add_safe(ktime_get(), t);
2619                 tp = &t;
2620         }
2621         /*
2622          * requeue parameter in 'utime' if cmd == FUTEX_*_REQUEUE_*.
2623          * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
2624          */
2625         if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
2626             cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
2627                 val2 = (u32) (unsigned long) utime;
2628
2629         return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
2630 }
2631
2632 static int __init futex_init(void)
2633 {
2634         u32 curval;
2635         int i;
2636
2637         /*
2638          * This will fail and we want it. Some arch implementations do
2639          * runtime detection of the futex_atomic_cmpxchg_inatomic()
2640          * functionality. We want to know that before we call in any
2641          * of the complex code paths. Also we want to prevent
2642          * registration of robust lists in that case. NULL is
2643          * guaranteed to fault and we get -EFAULT on functional
2644          * implementation, the non-functional ones will return
2645          * -ENOSYS.
2646          */
2647         curval = cmpxchg_futex_value_locked(NULL, 0, 0);
2648         if (curval == -EFAULT)
2649                 futex_cmpxchg_enabled = 1;
2650
2651         for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
2652                 plist_head_init(&futex_queues[i].chain, &futex_queues[i].lock);
2653                 spin_lock_init(&futex_queues[i].lock);
2654         }
2655
2656         return 0;
2657 }
2658 __initcall(futex_init);