futex: fix init order
[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  *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
23  *  enough at me, Linus for the original (flawed) idea, Matthew
24  *  Kirkwood for proof-of-concept implementation.
25  *
26  *  "The futexes are also cursed."
27  *  "But they come in a choice of three flavours!"
28  *
29  *  This program is free software; you can redistribute it and/or modify
30  *  it under the terms of the GNU General Public License as published by
31  *  the Free Software Foundation; either version 2 of the License, or
32  *  (at your option) any later version.
33  *
34  *  This program is distributed in the hope that it will be useful,
35  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
36  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
37  *  GNU General Public License for more details.
38  *
39  *  You should have received a copy of the GNU General Public License
40  *  along with this program; if not, write to the Free Software
41  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
42  */
43 #include <linux/slab.h>
44 #include <linux/poll.h>
45 #include <linux/fs.h>
46 #include <linux/file.h>
47 #include <linux/jhash.h>
48 #include <linux/init.h>
49 #include <linux/futex.h>
50 #include <linux/mount.h>
51 #include <linux/pagemap.h>
52 #include <linux/syscalls.h>
53 #include <linux/signal.h>
54 #include <linux/module.h>
55 #include <linux/magic.h>
56 #include <linux/pid.h>
57 #include <linux/nsproxy.h>
58
59 #include <asm/futex.h>
60
61 #include "rtmutex_common.h"
62
63 #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
64
65 /*
66  * Priority Inheritance state:
67  */
68 struct futex_pi_state {
69         /*
70          * list of 'owned' pi_state instances - these have to be
71          * cleaned up in do_exit() if the task exits prematurely:
72          */
73         struct list_head list;
74
75         /*
76          * The PI object:
77          */
78         struct rt_mutex pi_mutex;
79
80         struct task_struct *owner;
81         atomic_t refcount;
82
83         union futex_key key;
84 };
85
86 /*
87  * We use this hashed waitqueue instead of a normal wait_queue_t, so
88  * we can wake only the relevant ones (hashed queues may be shared).
89  *
90  * A futex_q has a woken state, just like tasks have TASK_RUNNING.
91  * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
92  * The order of wakup is always to make the first condition true, then
93  * wake up q->waiters, then make the second condition true.
94  */
95 struct futex_q {
96         struct plist_node list;
97         wait_queue_head_t waiters;
98
99         /* Which hash list lock to use: */
100         spinlock_t *lock_ptr;
101
102         /* Key which the futex is hashed on: */
103         union futex_key key;
104
105         /* For fd, sigio sent using these: */
106         int fd;
107         struct file *filp;
108
109         /* Optional priority inheritance state: */
110         struct futex_pi_state *pi_state;
111         struct task_struct *task;
112
113         /* Bitset for the optional bitmasked wakeup */
114         u32 bitset;
115 };
116
117 /*
118  * Split the global futex_lock into every hash list lock.
119  */
120 struct futex_hash_bucket {
121         spinlock_t lock;
122         struct plist_head chain;
123 };
124
125 static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
126
127 /* Futex-fs vfsmount entry: */
128 static struct vfsmount *futex_mnt;
129
130 /*
131  * Take mm->mmap_sem, when futex is shared
132  */
133 static inline void futex_lock_mm(struct rw_semaphore *fshared)
134 {
135         if (fshared)
136                 down_read(fshared);
137 }
138
139 /*
140  * Release mm->mmap_sem, when the futex is shared
141  */
142 static inline void futex_unlock_mm(struct rw_semaphore *fshared)
143 {
144         if (fshared)
145                 up_read(fshared);
146 }
147
148 /*
149  * We hash on the keys returned from get_futex_key (see below).
150  */
151 static struct futex_hash_bucket *hash_futex(union futex_key *key)
152 {
153         u32 hash = jhash2((u32*)&key->both.word,
154                           (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
155                           key->both.offset);
156         return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
157 }
158
159 /*
160  * Return 1 if two futex_keys are equal, 0 otherwise.
161  */
162 static inline int match_futex(union futex_key *key1, union futex_key *key2)
163 {
164         return (key1->both.word == key2->both.word
165                 && key1->both.ptr == key2->both.ptr
166                 && key1->both.offset == key2->both.offset);
167 }
168
169 /**
170  * get_futex_key - Get parameters which are the keys for a futex.
171  * @uaddr: virtual address of the futex
172  * @shared: NULL for a PROCESS_PRIVATE futex,
173  *      &current->mm->mmap_sem for a PROCESS_SHARED futex
174  * @key: address where result is stored.
175  *
176  * Returns a negative error code or 0
177  * The key words are stored in *key on success.
178  *
179  * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode,
180  * offset_within_page).  For private mappings, it's (uaddr, current->mm).
181  * We can usually work out the index without swapping in the page.
182  *
183  * fshared is NULL for PROCESS_PRIVATE futexes
184  * For other futexes, it points to &current->mm->mmap_sem and
185  * caller must have taken the reader lock. but NOT any spinlocks.
186  */
187 static int get_futex_key(u32 __user *uaddr, struct rw_semaphore *fshared,
188                          union futex_key *key)
189 {
190         unsigned long address = (unsigned long)uaddr;
191         struct mm_struct *mm = current->mm;
192         struct vm_area_struct *vma;
193         struct page *page;
194         int err;
195
196         /*
197          * The futex address must be "naturally" aligned.
198          */
199         key->both.offset = address % PAGE_SIZE;
200         if (unlikely((address % sizeof(u32)) != 0))
201                 return -EINVAL;
202         address -= key->both.offset;
203
204         /*
205          * PROCESS_PRIVATE futexes are fast.
206          * As the mm cannot disappear under us and the 'key' only needs
207          * virtual address, we dont even have to find the underlying vma.
208          * Note : We do have to check 'uaddr' is a valid user address,
209          *        but access_ok() should be faster than find_vma()
210          */
211         if (!fshared) {
212                 if (unlikely(!access_ok(VERIFY_WRITE, uaddr, sizeof(u32))))
213                         return -EFAULT;
214                 key->private.mm = mm;
215                 key->private.address = address;
216                 return 0;
217         }
218         /*
219          * The futex is hashed differently depending on whether
220          * it's in a shared or private mapping.  So check vma first.
221          */
222         vma = find_extend_vma(mm, address);
223         if (unlikely(!vma))
224                 return -EFAULT;
225
226         /*
227          * Permissions.
228          */
229         if (unlikely((vma->vm_flags & (VM_IO|VM_READ)) != VM_READ))
230                 return (vma->vm_flags & VM_IO) ? -EPERM : -EACCES;
231
232         /*
233          * Private mappings are handled in a simple way.
234          *
235          * NOTE: When userspace waits on a MAP_SHARED mapping, even if
236          * it's a read-only handle, it's expected that futexes attach to
237          * the object not the particular process.  Therefore we use
238          * VM_MAYSHARE here, not VM_SHARED which is restricted to shared
239          * mappings of _writable_ handles.
240          */
241         if (likely(!(vma->vm_flags & VM_MAYSHARE))) {
242                 key->both.offset |= FUT_OFF_MMSHARED; /* reference taken on mm */
243                 key->private.mm = mm;
244                 key->private.address = address;
245                 return 0;
246         }
247
248         /*
249          * Linear file mappings are also simple.
250          */
251         key->shared.inode = vma->vm_file->f_path.dentry->d_inode;
252         key->both.offset |= FUT_OFF_INODE; /* inode-based key. */
253         if (likely(!(vma->vm_flags & VM_NONLINEAR))) {
254                 key->shared.pgoff = (((address - vma->vm_start) >> PAGE_SHIFT)
255                                      + vma->vm_pgoff);
256                 return 0;
257         }
258
259         /*
260          * We could walk the page table to read the non-linear
261          * pte, and get the page index without fetching the page
262          * from swap.  But that's a lot of code to duplicate here
263          * for a rare case, so we simply fetch the page.
264          */
265         err = get_user_pages(current, mm, address, 1, 0, 0, &page, NULL);
266         if (err >= 0) {
267                 key->shared.pgoff =
268                         page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
269                 put_page(page);
270                 return 0;
271         }
272         return err;
273 }
274
275 /*
276  * Take a reference to the resource addressed by a key.
277  * Can be called while holding spinlocks.
278  *
279  */
280 static void get_futex_key_refs(union futex_key *key)
281 {
282         if (key->both.ptr == 0)
283                 return;
284         switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
285                 case FUT_OFF_INODE:
286                         atomic_inc(&key->shared.inode->i_count);
287                         break;
288                 case FUT_OFF_MMSHARED:
289                         atomic_inc(&key->private.mm->mm_count);
290                         break;
291         }
292 }
293
294 /*
295  * Drop a reference to the resource addressed by a key.
296  * The hash bucket spinlock must not be held.
297  */
298 static void drop_futex_key_refs(union futex_key *key)
299 {
300         if (!key->both.ptr)
301                 return;
302         switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
303                 case FUT_OFF_INODE:
304                         iput(key->shared.inode);
305                         break;
306                 case FUT_OFF_MMSHARED:
307                         mmdrop(key->private.mm);
308                         break;
309         }
310 }
311
312 static u32 cmpxchg_futex_value_locked(u32 __user *uaddr, u32 uval, u32 newval)
313 {
314         u32 curval;
315
316         pagefault_disable();
317         curval = futex_atomic_cmpxchg_inatomic(uaddr, uval, newval);
318         pagefault_enable();
319
320         return curval;
321 }
322
323 static int get_futex_value_locked(u32 *dest, u32 __user *from)
324 {
325         int ret;
326
327         pagefault_disable();
328         ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
329         pagefault_enable();
330
331         return ret ? -EFAULT : 0;
332 }
333
334 /*
335  * Fault handling.
336  * if fshared is non NULL, current->mm->mmap_sem is already held
337  */
338 static int futex_handle_fault(unsigned long address,
339                               struct rw_semaphore *fshared, int attempt)
340 {
341         struct vm_area_struct * vma;
342         struct mm_struct *mm = current->mm;
343         int ret = -EFAULT;
344
345         if (attempt > 2)
346                 return ret;
347
348         if (!fshared)
349                 down_read(&mm->mmap_sem);
350         vma = find_vma(mm, address);
351         if (vma && address >= vma->vm_start &&
352             (vma->vm_flags & VM_WRITE)) {
353                 int fault;
354                 fault = handle_mm_fault(mm, vma, address, 1);
355                 if (unlikely((fault & VM_FAULT_ERROR))) {
356 #if 0
357                         /* XXX: let's do this when we verify it is OK */
358                         if (ret & VM_FAULT_OOM)
359                                 ret = -ENOMEM;
360 #endif
361                 } else {
362                         ret = 0;
363                         if (fault & VM_FAULT_MAJOR)
364                                 current->maj_flt++;
365                         else
366                                 current->min_flt++;
367                 }
368         }
369         if (!fshared)
370                 up_read(&mm->mmap_sem);
371         return ret;
372 }
373
374 /*
375  * PI code:
376  */
377 static int refill_pi_state_cache(void)
378 {
379         struct futex_pi_state *pi_state;
380
381         if (likely(current->pi_state_cache))
382                 return 0;
383
384         pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
385
386         if (!pi_state)
387                 return -ENOMEM;
388
389         INIT_LIST_HEAD(&pi_state->list);
390         /* pi_mutex gets initialized later */
391         pi_state->owner = NULL;
392         atomic_set(&pi_state->refcount, 1);
393
394         current->pi_state_cache = pi_state;
395
396         return 0;
397 }
398
399 static struct futex_pi_state * alloc_pi_state(void)
400 {
401         struct futex_pi_state *pi_state = current->pi_state_cache;
402
403         WARN_ON(!pi_state);
404         current->pi_state_cache = NULL;
405
406         return pi_state;
407 }
408
409 static void free_pi_state(struct futex_pi_state *pi_state)
410 {
411         if (!atomic_dec_and_test(&pi_state->refcount))
412                 return;
413
414         /*
415          * If pi_state->owner is NULL, the owner is most probably dying
416          * and has cleaned up the pi_state already
417          */
418         if (pi_state->owner) {
419                 spin_lock_irq(&pi_state->owner->pi_lock);
420                 list_del_init(&pi_state->list);
421                 spin_unlock_irq(&pi_state->owner->pi_lock);
422
423                 rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
424         }
425
426         if (current->pi_state_cache)
427                 kfree(pi_state);
428         else {
429                 /*
430                  * pi_state->list is already empty.
431                  * clear pi_state->owner.
432                  * refcount is at 0 - put it back to 1.
433                  */
434                 pi_state->owner = NULL;
435                 atomic_set(&pi_state->refcount, 1);
436                 current->pi_state_cache = pi_state;
437         }
438 }
439
440 /*
441  * Look up the task based on what TID userspace gave us.
442  * We dont trust it.
443  */
444 static struct task_struct * futex_find_get_task(pid_t pid)
445 {
446         struct task_struct *p;
447
448         rcu_read_lock();
449         p = find_task_by_vpid(pid);
450         if (!p || ((current->euid != p->euid) && (current->euid != p->uid)))
451                 p = ERR_PTR(-ESRCH);
452         else
453                 get_task_struct(p);
454
455         rcu_read_unlock();
456
457         return p;
458 }
459
460 /*
461  * This task is holding PI mutexes at exit time => bad.
462  * Kernel cleans up PI-state, but userspace is likely hosed.
463  * (Robust-futex cleanup is separate and might save the day for userspace.)
464  */
465 void exit_pi_state_list(struct task_struct *curr)
466 {
467         struct list_head *next, *head = &curr->pi_state_list;
468         struct futex_pi_state *pi_state;
469         struct futex_hash_bucket *hb;
470         union futex_key key;
471
472         /*
473          * We are a ZOMBIE and nobody can enqueue itself on
474          * pi_state_list anymore, but we have to be careful
475          * versus waiters unqueueing themselves:
476          */
477         spin_lock_irq(&curr->pi_lock);
478         while (!list_empty(head)) {
479
480                 next = head->next;
481                 pi_state = list_entry(next, struct futex_pi_state, list);
482                 key = pi_state->key;
483                 hb = hash_futex(&key);
484                 spin_unlock_irq(&curr->pi_lock);
485
486                 spin_lock(&hb->lock);
487
488                 spin_lock_irq(&curr->pi_lock);
489                 /*
490                  * We dropped the pi-lock, so re-check whether this
491                  * task still owns the PI-state:
492                  */
493                 if (head->next != next) {
494                         spin_unlock(&hb->lock);
495                         continue;
496                 }
497
498                 WARN_ON(pi_state->owner != curr);
499                 WARN_ON(list_empty(&pi_state->list));
500                 list_del_init(&pi_state->list);
501                 pi_state->owner = NULL;
502                 spin_unlock_irq(&curr->pi_lock);
503
504                 rt_mutex_unlock(&pi_state->pi_mutex);
505
506                 spin_unlock(&hb->lock);
507
508                 spin_lock_irq(&curr->pi_lock);
509         }
510         spin_unlock_irq(&curr->pi_lock);
511 }
512
513 static int
514 lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
515                 union futex_key *key, struct futex_pi_state **ps)
516 {
517         struct futex_pi_state *pi_state = NULL;
518         struct futex_q *this, *next;
519         struct plist_head *head;
520         struct task_struct *p;
521         pid_t pid = uval & FUTEX_TID_MASK;
522
523         head = &hb->chain;
524
525         plist_for_each_entry_safe(this, next, head, list) {
526                 if (match_futex(&this->key, key)) {
527                         /*
528                          * Another waiter already exists - bump up
529                          * the refcount and return its pi_state:
530                          */
531                         pi_state = this->pi_state;
532                         /*
533                          * Userspace might have messed up non PI and PI futexes
534                          */
535                         if (unlikely(!pi_state))
536                                 return -EINVAL;
537
538                         WARN_ON(!atomic_read(&pi_state->refcount));
539                         WARN_ON(pid && pi_state->owner &&
540                                 pi_state->owner->pid != pid);
541
542                         atomic_inc(&pi_state->refcount);
543                         *ps = pi_state;
544
545                         return 0;
546                 }
547         }
548
549         /*
550          * We are the first waiter - try to look up the real owner and attach
551          * the new pi_state to it, but bail out when TID = 0
552          */
553         if (!pid)
554                 return -ESRCH;
555         p = futex_find_get_task(pid);
556         if (IS_ERR(p))
557                 return PTR_ERR(p);
558
559         /*
560          * We need to look at the task state flags to figure out,
561          * whether the task is exiting. To protect against the do_exit
562          * change of the task flags, we do this protected by
563          * p->pi_lock:
564          */
565         spin_lock_irq(&p->pi_lock);
566         if (unlikely(p->flags & PF_EXITING)) {
567                 /*
568                  * The task is on the way out. When PF_EXITPIDONE is
569                  * set, we know that the task has finished the
570                  * cleanup:
571                  */
572                 int ret = (p->flags & PF_EXITPIDONE) ? -ESRCH : -EAGAIN;
573
574                 spin_unlock_irq(&p->pi_lock);
575                 put_task_struct(p);
576                 return ret;
577         }
578
579         pi_state = alloc_pi_state();
580
581         /*
582          * Initialize the pi_mutex in locked state and make 'p'
583          * the owner of it:
584          */
585         rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
586
587         /* Store the key for possible exit cleanups: */
588         pi_state->key = *key;
589
590         WARN_ON(!list_empty(&pi_state->list));
591         list_add(&pi_state->list, &p->pi_state_list);
592         pi_state->owner = p;
593         spin_unlock_irq(&p->pi_lock);
594
595         put_task_struct(p);
596
597         *ps = pi_state;
598
599         return 0;
600 }
601
602 /*
603  * The hash bucket lock must be held when this is called.
604  * Afterwards, the futex_q must not be accessed.
605  */
606 static void wake_futex(struct futex_q *q)
607 {
608         plist_del(&q->list, &q->list.plist);
609         if (q->filp)
610                 send_sigio(&q->filp->f_owner, q->fd, POLL_IN);
611         /*
612          * The lock in wake_up_all() is a crucial memory barrier after the
613          * plist_del() and also before assigning to q->lock_ptr.
614          */
615         wake_up_all(&q->waiters);
616         /*
617          * The waiting task can free the futex_q as soon as this is written,
618          * without taking any locks.  This must come last.
619          *
620          * A memory barrier is required here to prevent the following store
621          * to lock_ptr from getting ahead of the wakeup. Clearing the lock
622          * at the end of wake_up_all() does not prevent this store from
623          * moving.
624          */
625         smp_wmb();
626         q->lock_ptr = NULL;
627 }
628
629 static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
630 {
631         struct task_struct *new_owner;
632         struct futex_pi_state *pi_state = this->pi_state;
633         u32 curval, newval;
634
635         if (!pi_state)
636                 return -EINVAL;
637
638         spin_lock(&pi_state->pi_mutex.wait_lock);
639         new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
640
641         /*
642          * This happens when we have stolen the lock and the original
643          * pending owner did not enqueue itself back on the rt_mutex.
644          * Thats not a tragedy. We know that way, that a lock waiter
645          * is on the fly. We make the futex_q waiter the pending owner.
646          */
647         if (!new_owner)
648                 new_owner = this->task;
649
650         /*
651          * We pass it to the next owner. (The WAITERS bit is always
652          * kept enabled while there is PI state around. We must also
653          * preserve the owner died bit.)
654          */
655         if (!(uval & FUTEX_OWNER_DIED)) {
656                 int ret = 0;
657
658                 newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
659
660                 curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
661
662                 if (curval == -EFAULT)
663                         ret = -EFAULT;
664                 else if (curval != uval)
665                         ret = -EINVAL;
666                 if (ret) {
667                         spin_unlock(&pi_state->pi_mutex.wait_lock);
668                         return ret;
669                 }
670         }
671
672         spin_lock_irq(&pi_state->owner->pi_lock);
673         WARN_ON(list_empty(&pi_state->list));
674         list_del_init(&pi_state->list);
675         spin_unlock_irq(&pi_state->owner->pi_lock);
676
677         spin_lock_irq(&new_owner->pi_lock);
678         WARN_ON(!list_empty(&pi_state->list));
679         list_add(&pi_state->list, &new_owner->pi_state_list);
680         pi_state->owner = new_owner;
681         spin_unlock_irq(&new_owner->pi_lock);
682
683         spin_unlock(&pi_state->pi_mutex.wait_lock);
684         rt_mutex_unlock(&pi_state->pi_mutex);
685
686         return 0;
687 }
688
689 static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
690 {
691         u32 oldval;
692
693         /*
694          * There is no waiter, so we unlock the futex. The owner died
695          * bit has not to be preserved here. We are the owner:
696          */
697         oldval = cmpxchg_futex_value_locked(uaddr, uval, 0);
698
699         if (oldval == -EFAULT)
700                 return oldval;
701         if (oldval != uval)
702                 return -EAGAIN;
703
704         return 0;
705 }
706
707 /*
708  * Express the locking dependencies for lockdep:
709  */
710 static inline void
711 double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
712 {
713         if (hb1 <= hb2) {
714                 spin_lock(&hb1->lock);
715                 if (hb1 < hb2)
716                         spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
717         } else { /* hb1 > hb2 */
718                 spin_lock(&hb2->lock);
719                 spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
720         }
721 }
722
723 /*
724  * Wake up all waiters hashed on the physical page that is mapped
725  * to this virtual address:
726  */
727 static int futex_wake(u32 __user *uaddr, struct rw_semaphore *fshared,
728                       int nr_wake, u32 bitset)
729 {
730         struct futex_hash_bucket *hb;
731         struct futex_q *this, *next;
732         struct plist_head *head;
733         union futex_key key;
734         int ret;
735
736         if (!bitset)
737                 return -EINVAL;
738
739         futex_lock_mm(fshared);
740
741         ret = get_futex_key(uaddr, fshared, &key);
742         if (unlikely(ret != 0))
743                 goto out;
744
745         hb = hash_futex(&key);
746         spin_lock(&hb->lock);
747         head = &hb->chain;
748
749         plist_for_each_entry_safe(this, next, head, list) {
750                 if (match_futex (&this->key, &key)) {
751                         if (this->pi_state) {
752                                 ret = -EINVAL;
753                                 break;
754                         }
755
756                         /* Check if one of the bits is set in both bitsets */
757                         if (!(this->bitset & bitset))
758                                 continue;
759
760                         wake_futex(this);
761                         if (++ret >= nr_wake)
762                                 break;
763                 }
764         }
765
766         spin_unlock(&hb->lock);
767 out:
768         futex_unlock_mm(fshared);
769         return ret;
770 }
771
772 /*
773  * Wake up all waiters hashed on the physical page that is mapped
774  * to this virtual address:
775  */
776 static int
777 futex_wake_op(u32 __user *uaddr1, struct rw_semaphore *fshared,
778               u32 __user *uaddr2,
779               int nr_wake, int nr_wake2, int op)
780 {
781         union futex_key key1, key2;
782         struct futex_hash_bucket *hb1, *hb2;
783         struct plist_head *head;
784         struct futex_q *this, *next;
785         int ret, op_ret, attempt = 0;
786
787 retryfull:
788         futex_lock_mm(fshared);
789
790         ret = get_futex_key(uaddr1, fshared, &key1);
791         if (unlikely(ret != 0))
792                 goto out;
793         ret = get_futex_key(uaddr2, fshared, &key2);
794         if (unlikely(ret != 0))
795                 goto out;
796
797         hb1 = hash_futex(&key1);
798         hb2 = hash_futex(&key2);
799
800 retry:
801         double_lock_hb(hb1, hb2);
802
803         op_ret = futex_atomic_op_inuser(op, uaddr2);
804         if (unlikely(op_ret < 0)) {
805                 u32 dummy;
806
807                 spin_unlock(&hb1->lock);
808                 if (hb1 != hb2)
809                         spin_unlock(&hb2->lock);
810
811 #ifndef CONFIG_MMU
812                 /*
813                  * we don't get EFAULT from MMU faults if we don't have an MMU,
814                  * but we might get them from range checking
815                  */
816                 ret = op_ret;
817                 goto out;
818 #endif
819
820                 if (unlikely(op_ret != -EFAULT)) {
821                         ret = op_ret;
822                         goto out;
823                 }
824
825                 /*
826                  * futex_atomic_op_inuser needs to both read and write
827                  * *(int __user *)uaddr2, but we can't modify it
828                  * non-atomically.  Therefore, if get_user below is not
829                  * enough, we need to handle the fault ourselves, while
830                  * still holding the mmap_sem.
831                  */
832                 if (attempt++) {
833                         ret = futex_handle_fault((unsigned long)uaddr2,
834                                                  fshared, attempt);
835                         if (ret)
836                                 goto out;
837                         goto retry;
838                 }
839
840                 /*
841                  * If we would have faulted, release mmap_sem,
842                  * fault it in and start all over again.
843                  */
844                 futex_unlock_mm(fshared);
845
846                 ret = get_user(dummy, uaddr2);
847                 if (ret)
848                         return ret;
849
850                 goto retryfull;
851         }
852
853         head = &hb1->chain;
854
855         plist_for_each_entry_safe(this, next, head, list) {
856                 if (match_futex (&this->key, &key1)) {
857                         wake_futex(this);
858                         if (++ret >= nr_wake)
859                                 break;
860                 }
861         }
862
863         if (op_ret > 0) {
864                 head = &hb2->chain;
865
866                 op_ret = 0;
867                 plist_for_each_entry_safe(this, next, head, list) {
868                         if (match_futex (&this->key, &key2)) {
869                                 wake_futex(this);
870                                 if (++op_ret >= nr_wake2)
871                                         break;
872                         }
873                 }
874                 ret += op_ret;
875         }
876
877         spin_unlock(&hb1->lock);
878         if (hb1 != hb2)
879                 spin_unlock(&hb2->lock);
880 out:
881         futex_unlock_mm(fshared);
882
883         return ret;
884 }
885
886 /*
887  * Requeue all waiters hashed on one physical page to another
888  * physical page.
889  */
890 static int futex_requeue(u32 __user *uaddr1, struct rw_semaphore *fshared,
891                          u32 __user *uaddr2,
892                          int nr_wake, int nr_requeue, u32 *cmpval)
893 {
894         union futex_key key1, key2;
895         struct futex_hash_bucket *hb1, *hb2;
896         struct plist_head *head1;
897         struct futex_q *this, *next;
898         int ret, drop_count = 0;
899
900  retry:
901         futex_lock_mm(fshared);
902
903         ret = get_futex_key(uaddr1, fshared, &key1);
904         if (unlikely(ret != 0))
905                 goto out;
906         ret = get_futex_key(uaddr2, fshared, &key2);
907         if (unlikely(ret != 0))
908                 goto out;
909
910         hb1 = hash_futex(&key1);
911         hb2 = hash_futex(&key2);
912
913         double_lock_hb(hb1, hb2);
914
915         if (likely(cmpval != NULL)) {
916                 u32 curval;
917
918                 ret = get_futex_value_locked(&curval, uaddr1);
919
920                 if (unlikely(ret)) {
921                         spin_unlock(&hb1->lock);
922                         if (hb1 != hb2)
923                                 spin_unlock(&hb2->lock);
924
925                         /*
926                          * If we would have faulted, release mmap_sem, fault
927                          * it in and start all over again.
928                          */
929                         futex_unlock_mm(fshared);
930
931                         ret = get_user(curval, uaddr1);
932
933                         if (!ret)
934                                 goto retry;
935
936                         return ret;
937                 }
938                 if (curval != *cmpval) {
939                         ret = -EAGAIN;
940                         goto out_unlock;
941                 }
942         }
943
944         head1 = &hb1->chain;
945         plist_for_each_entry_safe(this, next, head1, list) {
946                 if (!match_futex (&this->key, &key1))
947                         continue;
948                 if (++ret <= nr_wake) {
949                         wake_futex(this);
950                 } else {
951                         /*
952                          * If key1 and key2 hash to the same bucket, no need to
953                          * requeue.
954                          */
955                         if (likely(head1 != &hb2->chain)) {
956                                 plist_del(&this->list, &hb1->chain);
957                                 plist_add(&this->list, &hb2->chain);
958                                 this->lock_ptr = &hb2->lock;
959 #ifdef CONFIG_DEBUG_PI_LIST
960                                 this->list.plist.lock = &hb2->lock;
961 #endif
962                         }
963                         this->key = key2;
964                         get_futex_key_refs(&key2);
965                         drop_count++;
966
967                         if (ret - nr_wake >= nr_requeue)
968                                 break;
969                 }
970         }
971
972 out_unlock:
973         spin_unlock(&hb1->lock);
974         if (hb1 != hb2)
975                 spin_unlock(&hb2->lock);
976
977         /* drop_futex_key_refs() must be called outside the spinlocks. */
978         while (--drop_count >= 0)
979                 drop_futex_key_refs(&key1);
980
981 out:
982         futex_unlock_mm(fshared);
983         return ret;
984 }
985
986 /* The key must be already stored in q->key. */
987 static inline struct futex_hash_bucket *
988 queue_lock(struct futex_q *q, int fd, struct file *filp)
989 {
990         struct futex_hash_bucket *hb;
991
992         q->fd = fd;
993         q->filp = filp;
994
995         init_waitqueue_head(&q->waiters);
996
997         get_futex_key_refs(&q->key);
998         hb = hash_futex(&q->key);
999         q->lock_ptr = &hb->lock;
1000
1001         spin_lock(&hb->lock);
1002         return hb;
1003 }
1004
1005 static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
1006 {
1007         int prio;
1008
1009         /*
1010          * The priority used to register this element is
1011          * - either the real thread-priority for the real-time threads
1012          * (i.e. threads with a priority lower than MAX_RT_PRIO)
1013          * - or MAX_RT_PRIO for non-RT threads.
1014          * Thus, all RT-threads are woken first in priority order, and
1015          * the others are woken last, in FIFO order.
1016          */
1017         prio = min(current->normal_prio, MAX_RT_PRIO);
1018
1019         plist_node_init(&q->list, prio);
1020 #ifdef CONFIG_DEBUG_PI_LIST
1021         q->list.plist.lock = &hb->lock;
1022 #endif
1023         plist_add(&q->list, &hb->chain);
1024         q->task = current;
1025         spin_unlock(&hb->lock);
1026 }
1027
1028 static inline void
1029 queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
1030 {
1031         spin_unlock(&hb->lock);
1032         drop_futex_key_refs(&q->key);
1033 }
1034
1035 /*
1036  * queue_me and unqueue_me must be called as a pair, each
1037  * exactly once.  They are called with the hashed spinlock held.
1038  */
1039
1040 /* The key must be already stored in q->key. */
1041 static void queue_me(struct futex_q *q, int fd, struct file *filp)
1042 {
1043         struct futex_hash_bucket *hb;
1044
1045         hb = queue_lock(q, fd, filp);
1046         __queue_me(q, hb);
1047 }
1048
1049 /* Return 1 if we were still queued (ie. 0 means we were woken) */
1050 static int unqueue_me(struct futex_q *q)
1051 {
1052         spinlock_t *lock_ptr;
1053         int ret = 0;
1054
1055         /* In the common case we don't take the spinlock, which is nice. */
1056  retry:
1057         lock_ptr = q->lock_ptr;
1058         barrier();
1059         if (lock_ptr != NULL) {
1060                 spin_lock(lock_ptr);
1061                 /*
1062                  * q->lock_ptr can change between reading it and
1063                  * spin_lock(), causing us to take the wrong lock.  This
1064                  * corrects the race condition.
1065                  *
1066                  * Reasoning goes like this: if we have the wrong lock,
1067                  * q->lock_ptr must have changed (maybe several times)
1068                  * between reading it and the spin_lock().  It can
1069                  * change again after the spin_lock() but only if it was
1070                  * already changed before the spin_lock().  It cannot,
1071                  * however, change back to the original value.  Therefore
1072                  * we can detect whether we acquired the correct lock.
1073                  */
1074                 if (unlikely(lock_ptr != q->lock_ptr)) {
1075                         spin_unlock(lock_ptr);
1076                         goto retry;
1077                 }
1078                 WARN_ON(plist_node_empty(&q->list));
1079                 plist_del(&q->list, &q->list.plist);
1080
1081                 BUG_ON(q->pi_state);
1082
1083                 spin_unlock(lock_ptr);
1084                 ret = 1;
1085         }
1086
1087         drop_futex_key_refs(&q->key);
1088         return ret;
1089 }
1090
1091 /*
1092  * PI futexes can not be requeued and must remove themself from the
1093  * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
1094  * and dropped here.
1095  */
1096 static void unqueue_me_pi(struct futex_q *q)
1097 {
1098         WARN_ON(plist_node_empty(&q->list));
1099         plist_del(&q->list, &q->list.plist);
1100
1101         BUG_ON(!q->pi_state);
1102         free_pi_state(q->pi_state);
1103         q->pi_state = NULL;
1104
1105         spin_unlock(q->lock_ptr);
1106
1107         drop_futex_key_refs(&q->key);
1108 }
1109
1110 /*
1111  * Fixup the pi_state owner with the new owner.
1112  *
1113  * Must be called with hash bucket lock held and mm->sem held for non
1114  * private futexes.
1115  */
1116 static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
1117                                 struct task_struct *newowner)
1118 {
1119         u32 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
1120         struct futex_pi_state *pi_state = q->pi_state;
1121         u32 uval, curval, newval;
1122         int ret;
1123
1124         /* Owner died? */
1125         if (pi_state->owner != NULL) {
1126                 spin_lock_irq(&pi_state->owner->pi_lock);
1127                 WARN_ON(list_empty(&pi_state->list));
1128                 list_del_init(&pi_state->list);
1129                 spin_unlock_irq(&pi_state->owner->pi_lock);
1130         } else
1131                 newtid |= FUTEX_OWNER_DIED;
1132
1133         pi_state->owner = newowner;
1134
1135         spin_lock_irq(&newowner->pi_lock);
1136         WARN_ON(!list_empty(&pi_state->list));
1137         list_add(&pi_state->list, &newowner->pi_state_list);
1138         spin_unlock_irq(&newowner->pi_lock);
1139
1140         /*
1141          * We own it, so we have to replace the pending owner
1142          * TID. This must be atomic as we have preserve the
1143          * owner died bit here.
1144          */
1145         ret = get_futex_value_locked(&uval, uaddr);
1146
1147         while (!ret) {
1148                 newval = (uval & FUTEX_OWNER_DIED) | newtid;
1149
1150                 curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
1151
1152                 if (curval == -EFAULT)
1153                         ret = -EFAULT;
1154                 if (curval == uval)
1155                         break;
1156                 uval = curval;
1157         }
1158         return ret;
1159 }
1160
1161 /*
1162  * In case we must use restart_block to restart a futex_wait,
1163  * we encode in the 'flags' shared capability
1164  */
1165 #define FLAGS_SHARED  1
1166
1167 static long futex_wait_restart(struct restart_block *restart);
1168
1169 static int futex_wait(u32 __user *uaddr, struct rw_semaphore *fshared,
1170                       u32 val, ktime_t *abs_time, u32 bitset)
1171 {
1172         struct task_struct *curr = current;
1173         DECLARE_WAITQUEUE(wait, curr);
1174         struct futex_hash_bucket *hb;
1175         struct futex_q q;
1176         u32 uval;
1177         int ret;
1178         struct hrtimer_sleeper t;
1179         int rem = 0;
1180
1181         if (!bitset)
1182                 return -EINVAL;
1183
1184         q.pi_state = NULL;
1185         q.bitset = bitset;
1186  retry:
1187         futex_lock_mm(fshared);
1188
1189         ret = get_futex_key(uaddr, fshared, &q.key);
1190         if (unlikely(ret != 0))
1191                 goto out_release_sem;
1192
1193         hb = queue_lock(&q, -1, NULL);
1194
1195         /*
1196          * Access the page AFTER the futex is queued.
1197          * Order is important:
1198          *
1199          *   Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
1200          *   Userspace waker:  if (cond(var)) { var = new; futex_wake(&var); }
1201          *
1202          * The basic logical guarantee of a futex is that it blocks ONLY
1203          * if cond(var) is known to be true at the time of blocking, for
1204          * any cond.  If we queued after testing *uaddr, that would open
1205          * a race condition where we could block indefinitely with
1206          * cond(var) false, which would violate the guarantee.
1207          *
1208          * A consequence is that futex_wait() can return zero and absorb
1209          * a wakeup when *uaddr != val on entry to the syscall.  This is
1210          * rare, but normal.
1211          *
1212          * for shared futexes, we hold the mmap semaphore, so the mapping
1213          * cannot have changed since we looked it up in get_futex_key.
1214          */
1215         ret = get_futex_value_locked(&uval, uaddr);
1216
1217         if (unlikely(ret)) {
1218                 queue_unlock(&q, hb);
1219
1220                 /*
1221                  * If we would have faulted, release mmap_sem, fault it in and
1222                  * start all over again.
1223                  */
1224                 futex_unlock_mm(fshared);
1225
1226                 ret = get_user(uval, uaddr);
1227
1228                 if (!ret)
1229                         goto retry;
1230                 return ret;
1231         }
1232         ret = -EWOULDBLOCK;
1233         if (uval != val)
1234                 goto out_unlock_release_sem;
1235
1236         /* Only actually queue if *uaddr contained val.  */
1237         __queue_me(&q, hb);
1238
1239         /*
1240          * Now the futex is queued and we have checked the data, we
1241          * don't want to hold mmap_sem while we sleep.
1242          */
1243         futex_unlock_mm(fshared);
1244
1245         /*
1246          * There might have been scheduling since the queue_me(), as we
1247          * cannot hold a spinlock across the get_user() in case it
1248          * faults, and we cannot just set TASK_INTERRUPTIBLE state when
1249          * queueing ourselves into the futex hash.  This code thus has to
1250          * rely on the futex_wake() code removing us from hash when it
1251          * wakes us up.
1252          */
1253
1254         /* add_wait_queue is the barrier after __set_current_state. */
1255         __set_current_state(TASK_INTERRUPTIBLE);
1256         add_wait_queue(&q.waiters, &wait);
1257         /*
1258          * !plist_node_empty() is safe here without any lock.
1259          * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
1260          */
1261         if (likely(!plist_node_empty(&q.list))) {
1262                 if (!abs_time)
1263                         schedule();
1264                 else {
1265                         hrtimer_init(&t.timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1266                         hrtimer_init_sleeper(&t, current);
1267                         t.timer.expires = *abs_time;
1268
1269                         hrtimer_start(&t.timer, t.timer.expires, HRTIMER_MODE_ABS);
1270                         if (!hrtimer_active(&t.timer))
1271                                 t.task = NULL;
1272
1273                         /*
1274                          * the timer could have already expired, in which
1275                          * case current would be flagged for rescheduling.
1276                          * Don't bother calling schedule.
1277                          */
1278                         if (likely(t.task))
1279                                 schedule();
1280
1281                         hrtimer_cancel(&t.timer);
1282
1283                         /* Flag if a timeout occured */
1284                         rem = (t.task == NULL);
1285                 }
1286         }
1287         __set_current_state(TASK_RUNNING);
1288
1289         /*
1290          * NOTE: we don't remove ourselves from the waitqueue because
1291          * we are the only user of it.
1292          */
1293
1294         /* If we were woken (and unqueued), we succeeded, whatever. */
1295         if (!unqueue_me(&q))
1296                 return 0;
1297         if (rem)
1298                 return -ETIMEDOUT;
1299
1300         /*
1301          * We expect signal_pending(current), but another thread may
1302          * have handled it for us already.
1303          */
1304         if (!abs_time)
1305                 return -ERESTARTSYS;
1306         else {
1307                 struct restart_block *restart;
1308                 restart = &current_thread_info()->restart_block;
1309                 restart->fn = futex_wait_restart;
1310                 restart->futex.uaddr = (u32 *)uaddr;
1311                 restart->futex.val = val;
1312                 restart->futex.time = abs_time->tv64;
1313                 restart->futex.bitset = bitset;
1314                 restart->futex.flags = 0;
1315
1316                 if (fshared)
1317                         restart->futex.flags |= FLAGS_SHARED;
1318                 return -ERESTART_RESTARTBLOCK;
1319         }
1320
1321  out_unlock_release_sem:
1322         queue_unlock(&q, hb);
1323
1324  out_release_sem:
1325         futex_unlock_mm(fshared);
1326         return ret;
1327 }
1328
1329
1330 static long futex_wait_restart(struct restart_block *restart)
1331 {
1332         u32 __user *uaddr = (u32 __user *)restart->futex.uaddr;
1333         struct rw_semaphore *fshared = NULL;
1334         ktime_t t;
1335
1336         t.tv64 = restart->futex.time;
1337         restart->fn = do_no_restart_syscall;
1338         if (restart->futex.flags & FLAGS_SHARED)
1339                 fshared = &current->mm->mmap_sem;
1340         return (long)futex_wait(uaddr, fshared, restart->futex.val, &t,
1341                                 restart->futex.bitset);
1342 }
1343
1344
1345 /*
1346  * Userspace tried a 0 -> TID atomic transition of the futex value
1347  * and failed. The kernel side here does the whole locking operation:
1348  * if there are waiters then it will block, it does PI, etc. (Due to
1349  * races the kernel might see a 0 value of the futex too.)
1350  */
1351 static int futex_lock_pi(u32 __user *uaddr, struct rw_semaphore *fshared,
1352                          int detect, ktime_t *time, int trylock)
1353 {
1354         struct hrtimer_sleeper timeout, *to = NULL;
1355         struct task_struct *curr = current;
1356         struct futex_hash_bucket *hb;
1357         u32 uval, newval, curval;
1358         struct futex_q q;
1359         int ret, lock_taken, ownerdied = 0, attempt = 0;
1360
1361         if (refill_pi_state_cache())
1362                 return -ENOMEM;
1363
1364         if (time) {
1365                 to = &timeout;
1366                 hrtimer_init(&to->timer, CLOCK_REALTIME, HRTIMER_MODE_ABS);
1367                 hrtimer_init_sleeper(to, current);
1368                 to->timer.expires = *time;
1369         }
1370
1371         q.pi_state = NULL;
1372  retry:
1373         futex_lock_mm(fshared);
1374
1375         ret = get_futex_key(uaddr, fshared, &q.key);
1376         if (unlikely(ret != 0))
1377                 goto out_release_sem;
1378
1379  retry_unlocked:
1380         hb = queue_lock(&q, -1, NULL);
1381
1382  retry_locked:
1383         ret = lock_taken = 0;
1384
1385         /*
1386          * To avoid races, we attempt to take the lock here again
1387          * (by doing a 0 -> TID atomic cmpxchg), while holding all
1388          * the locks. It will most likely not succeed.
1389          */
1390         newval = task_pid_vnr(current);
1391
1392         curval = cmpxchg_futex_value_locked(uaddr, 0, newval);
1393
1394         if (unlikely(curval == -EFAULT))
1395                 goto uaddr_faulted;
1396
1397         /*
1398          * Detect deadlocks. In case of REQUEUE_PI this is a valid
1399          * situation and we return success to user space.
1400          */
1401         if (unlikely((curval & FUTEX_TID_MASK) == task_pid_vnr(current))) {
1402                 ret = -EDEADLK;
1403                 goto out_unlock_release_sem;
1404         }
1405
1406         /*
1407          * Surprise - we got the lock. Just return to userspace:
1408          */
1409         if (unlikely(!curval))
1410                 goto out_unlock_release_sem;
1411
1412         uval = curval;
1413
1414         /*
1415          * Set the WAITERS flag, so the owner will know it has someone
1416          * to wake at next unlock
1417          */
1418         newval = curval | FUTEX_WAITERS;
1419
1420         /*
1421          * There are two cases, where a futex might have no owner (the
1422          * owner TID is 0): OWNER_DIED. We take over the futex in this
1423          * case. We also do an unconditional take over, when the owner
1424          * of the futex died.
1425          *
1426          * This is safe as we are protected by the hash bucket lock !
1427          */
1428         if (unlikely(ownerdied || !(curval & FUTEX_TID_MASK))) {
1429                 /* Keep the OWNER_DIED bit */
1430                 newval = (curval & ~FUTEX_TID_MASK) | task_pid_vnr(current);
1431                 ownerdied = 0;
1432                 lock_taken = 1;
1433         }
1434
1435         curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
1436
1437         if (unlikely(curval == -EFAULT))
1438                 goto uaddr_faulted;
1439         if (unlikely(curval != uval))
1440                 goto retry_locked;
1441
1442         /*
1443          * We took the lock due to owner died take over.
1444          */
1445         if (unlikely(lock_taken))
1446                 goto out_unlock_release_sem;
1447
1448         /*
1449          * We dont have the lock. Look up the PI state (or create it if
1450          * we are the first waiter):
1451          */
1452         ret = lookup_pi_state(uval, hb, &q.key, &q.pi_state);
1453
1454         if (unlikely(ret)) {
1455                 switch (ret) {
1456
1457                 case -EAGAIN:
1458                         /*
1459                          * Task is exiting and we just wait for the
1460                          * exit to complete.
1461                          */
1462                         queue_unlock(&q, hb);
1463                         futex_unlock_mm(fshared);
1464                         cond_resched();
1465                         goto retry;
1466
1467                 case -ESRCH:
1468                         /*
1469                          * No owner found for this futex. Check if the
1470                          * OWNER_DIED bit is set to figure out whether
1471                          * this is a robust futex or not.
1472                          */
1473                         if (get_futex_value_locked(&curval, uaddr))
1474                                 goto uaddr_faulted;
1475
1476                         /*
1477                          * We simply start over in case of a robust
1478                          * futex. The code above will take the futex
1479                          * and return happy.
1480                          */
1481                         if (curval & FUTEX_OWNER_DIED) {
1482                                 ownerdied = 1;
1483                                 goto retry_locked;
1484                         }
1485                 default:
1486                         goto out_unlock_release_sem;
1487                 }
1488         }
1489
1490         /*
1491          * Only actually queue now that the atomic ops are done:
1492          */
1493         __queue_me(&q, hb);
1494
1495         /*
1496          * Now the futex is queued and we have checked the data, we
1497          * don't want to hold mmap_sem while we sleep.
1498          */
1499         futex_unlock_mm(fshared);
1500
1501         WARN_ON(!q.pi_state);
1502         /*
1503          * Block on the PI mutex:
1504          */
1505         if (!trylock)
1506                 ret = rt_mutex_timed_lock(&q.pi_state->pi_mutex, to, 1);
1507         else {
1508                 ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
1509                 /* Fixup the trylock return value: */
1510                 ret = ret ? 0 : -EWOULDBLOCK;
1511         }
1512
1513         futex_lock_mm(fshared);
1514         spin_lock(q.lock_ptr);
1515
1516         if (!ret) {
1517                 /*
1518                  * Got the lock. We might not be the anticipated owner
1519                  * if we did a lock-steal - fix up the PI-state in
1520                  * that case:
1521                  */
1522                 if (q.pi_state->owner != curr)
1523                         ret = fixup_pi_state_owner(uaddr, &q, curr);
1524         } else {
1525                 /*
1526                  * Catch the rare case, where the lock was released
1527                  * when we were on the way back before we locked the
1528                  * hash bucket.
1529                  */
1530                 if (q.pi_state->owner == curr) {
1531                         /*
1532                          * Try to get the rt_mutex now. This might
1533                          * fail as some other task acquired the
1534                          * rt_mutex after we removed ourself from the
1535                          * rt_mutex waiters list.
1536                          */
1537                         if (rt_mutex_trylock(&q.pi_state->pi_mutex))
1538                                 ret = 0;
1539                         else {
1540                                 /*
1541                                  * pi_state is incorrect, some other
1542                                  * task did a lock steal and we
1543                                  * returned due to timeout or signal
1544                                  * without taking the rt_mutex. Too
1545                                  * late. We can access the
1546                                  * rt_mutex_owner without locking, as
1547                                  * the other task is now blocked on
1548                                  * the hash bucket lock. Fix the state
1549                                  * up.
1550                                  */
1551                                 struct task_struct *owner;
1552                                 int res;
1553
1554                                 owner = rt_mutex_owner(&q.pi_state->pi_mutex);
1555                                 res = fixup_pi_state_owner(uaddr, &q, owner);
1556
1557                                 /* propagate -EFAULT, if the fixup failed */
1558                                 if (res)
1559                                         ret = res;
1560                         }
1561                 } else {
1562                         /*
1563                          * Paranoia check. If we did not take the lock
1564                          * in the trylock above, then we should not be
1565                          * the owner of the rtmutex, neither the real
1566                          * nor the pending one:
1567                          */
1568                         if (rt_mutex_owner(&q.pi_state->pi_mutex) == curr)
1569                                 printk(KERN_ERR "futex_lock_pi: ret = %d "
1570                                        "pi-mutex: %p pi-state %p\n", ret,
1571                                        q.pi_state->pi_mutex.owner,
1572                                        q.pi_state->owner);
1573                 }
1574         }
1575
1576         /* Unqueue and drop the lock */
1577         unqueue_me_pi(&q);
1578         futex_unlock_mm(fshared);
1579
1580         return ret != -EINTR ? ret : -ERESTARTNOINTR;
1581
1582  out_unlock_release_sem:
1583         queue_unlock(&q, hb);
1584
1585  out_release_sem:
1586         futex_unlock_mm(fshared);
1587         return ret;
1588
1589  uaddr_faulted:
1590         /*
1591          * We have to r/w  *(int __user *)uaddr, but we can't modify it
1592          * non-atomically.  Therefore, if get_user below is not
1593          * enough, we need to handle the fault ourselves, while
1594          * still holding the mmap_sem.
1595          *
1596          * ... and hb->lock. :-) --ANK
1597          */
1598         queue_unlock(&q, hb);
1599
1600         if (attempt++) {
1601                 ret = futex_handle_fault((unsigned long)uaddr, fshared,
1602                                          attempt);
1603                 if (ret)
1604                         goto out_release_sem;
1605                 goto retry_unlocked;
1606         }
1607
1608         futex_unlock_mm(fshared);
1609
1610         ret = get_user(uval, uaddr);
1611         if (!ret && (uval != -EFAULT))
1612                 goto retry;
1613
1614         return ret;
1615 }
1616
1617 /*
1618  * Userspace attempted a TID -> 0 atomic transition, and failed.
1619  * This is the in-kernel slowpath: we look up the PI state (if any),
1620  * and do the rt-mutex unlock.
1621  */
1622 static int futex_unlock_pi(u32 __user *uaddr, struct rw_semaphore *fshared)
1623 {
1624         struct futex_hash_bucket *hb;
1625         struct futex_q *this, *next;
1626         u32 uval;
1627         struct plist_head *head;
1628         union futex_key key;
1629         int ret, attempt = 0;
1630
1631 retry:
1632         if (get_user(uval, uaddr))
1633                 return -EFAULT;
1634         /*
1635          * We release only a lock we actually own:
1636          */
1637         if ((uval & FUTEX_TID_MASK) != task_pid_vnr(current))
1638                 return -EPERM;
1639         /*
1640          * First take all the futex related locks:
1641          */
1642         futex_lock_mm(fshared);
1643
1644         ret = get_futex_key(uaddr, fshared, &key);
1645         if (unlikely(ret != 0))
1646                 goto out;
1647
1648         hb = hash_futex(&key);
1649 retry_unlocked:
1650         spin_lock(&hb->lock);
1651
1652         /*
1653          * To avoid races, try to do the TID -> 0 atomic transition
1654          * again. If it succeeds then we can return without waking
1655          * anyone else up:
1656          */
1657         if (!(uval & FUTEX_OWNER_DIED))
1658                 uval = cmpxchg_futex_value_locked(uaddr, task_pid_vnr(current), 0);
1659
1660
1661         if (unlikely(uval == -EFAULT))
1662                 goto pi_faulted;
1663         /*
1664          * Rare case: we managed to release the lock atomically,
1665          * no need to wake anyone else up:
1666          */
1667         if (unlikely(uval == task_pid_vnr(current)))
1668                 goto out_unlock;
1669
1670         /*
1671          * Ok, other tasks may need to be woken up - check waiters
1672          * and do the wakeup if necessary:
1673          */
1674         head = &hb->chain;
1675
1676         plist_for_each_entry_safe(this, next, head, list) {
1677                 if (!match_futex (&this->key, &key))
1678                         continue;
1679                 ret = wake_futex_pi(uaddr, uval, this);
1680                 /*
1681                  * The atomic access to the futex value
1682                  * generated a pagefault, so retry the
1683                  * user-access and the wakeup:
1684                  */
1685                 if (ret == -EFAULT)
1686                         goto pi_faulted;
1687                 goto out_unlock;
1688         }
1689         /*
1690          * No waiters - kernel unlocks the futex:
1691          */
1692         if (!(uval & FUTEX_OWNER_DIED)) {
1693                 ret = unlock_futex_pi(uaddr, uval);
1694                 if (ret == -EFAULT)
1695                         goto pi_faulted;
1696         }
1697
1698 out_unlock:
1699         spin_unlock(&hb->lock);
1700 out:
1701         futex_unlock_mm(fshared);
1702
1703         return ret;
1704
1705 pi_faulted:
1706         /*
1707          * We have to r/w  *(int __user *)uaddr, but we can't modify it
1708          * non-atomically.  Therefore, if get_user below is not
1709          * enough, we need to handle the fault ourselves, while
1710          * still holding the mmap_sem.
1711          *
1712          * ... and hb->lock. --ANK
1713          */
1714         spin_unlock(&hb->lock);
1715
1716         if (attempt++) {
1717                 ret = futex_handle_fault((unsigned long)uaddr, fshared,
1718                                          attempt);
1719                 if (ret)
1720                         goto out;
1721                 uval = 0;
1722                 goto retry_unlocked;
1723         }
1724
1725         futex_unlock_mm(fshared);
1726
1727         ret = get_user(uval, uaddr);
1728         if (!ret && (uval != -EFAULT))
1729                 goto retry;
1730
1731         return ret;
1732 }
1733
1734 static int futex_close(struct inode *inode, struct file *filp)
1735 {
1736         struct futex_q *q = filp->private_data;
1737
1738         unqueue_me(q);
1739         kfree(q);
1740
1741         return 0;
1742 }
1743
1744 /* This is one-shot: once it's gone off you need a new fd */
1745 static unsigned int futex_poll(struct file *filp,
1746                                struct poll_table_struct *wait)
1747 {
1748         struct futex_q *q = filp->private_data;
1749         int ret = 0;
1750
1751         poll_wait(filp, &q->waiters, wait);
1752
1753         /*
1754          * plist_node_empty() is safe here without any lock.
1755          * q->lock_ptr != 0 is not safe, because of ordering against wakeup.
1756          */
1757         if (plist_node_empty(&q->list))
1758                 ret = POLLIN | POLLRDNORM;
1759
1760         return ret;
1761 }
1762
1763 static const struct file_operations futex_fops = {
1764         .release        = futex_close,
1765         .poll           = futex_poll,
1766 };
1767
1768 /*
1769  * Signal allows caller to avoid the race which would occur if they
1770  * set the sigio stuff up afterwards.
1771  */
1772 static int futex_fd(u32 __user *uaddr, int signal)
1773 {
1774         struct futex_q *q;
1775         struct file *filp;
1776         int ret, err;
1777         struct rw_semaphore *fshared;
1778         static unsigned long printk_interval;
1779
1780         if (printk_timed_ratelimit(&printk_interval, 60 * 60 * 1000)) {
1781                 printk(KERN_WARNING "Process `%s' used FUTEX_FD, which "
1782                        "will be removed from the kernel in June 2007\n",
1783                        current->comm);
1784         }
1785
1786         ret = -EINVAL;
1787         if (!valid_signal(signal))
1788                 goto out;
1789
1790         ret = get_unused_fd();
1791         if (ret < 0)
1792                 goto out;
1793         filp = get_empty_filp();
1794         if (!filp) {
1795                 put_unused_fd(ret);
1796                 ret = -ENFILE;
1797                 goto out;
1798         }
1799         filp->f_op = &futex_fops;
1800         filp->f_path.mnt = mntget(futex_mnt);
1801         filp->f_path.dentry = dget(futex_mnt->mnt_root);
1802         filp->f_mapping = filp->f_path.dentry->d_inode->i_mapping;
1803
1804         if (signal) {
1805                 err = __f_setown(filp, task_pid(current), PIDTYPE_PID, 1);
1806                 if (err < 0) {
1807                         goto error;
1808                 }
1809                 filp->f_owner.signum = signal;
1810         }
1811
1812         q = kmalloc(sizeof(*q), GFP_KERNEL);
1813         if (!q) {
1814                 err = -ENOMEM;
1815                 goto error;
1816         }
1817         q->pi_state = NULL;
1818
1819         fshared = &current->mm->mmap_sem;
1820         down_read(fshared);
1821         err = get_futex_key(uaddr, fshared, &q->key);
1822
1823         if (unlikely(err != 0)) {
1824                 up_read(fshared);
1825                 kfree(q);
1826                 goto error;
1827         }
1828
1829         /*
1830          * queue_me() must be called before releasing mmap_sem, because
1831          * key->shared.inode needs to be referenced while holding it.
1832          */
1833         filp->private_data = q;
1834
1835         queue_me(q, ret, filp);
1836         up_read(fshared);
1837
1838         /* Now we map fd to filp, so userspace can access it */
1839         fd_install(ret, filp);
1840 out:
1841         return ret;
1842 error:
1843         put_unused_fd(ret);
1844         put_filp(filp);
1845         ret = err;
1846         goto out;
1847 }
1848
1849 /*
1850  * Support for robust futexes: the kernel cleans up held futexes at
1851  * thread exit time.
1852  *
1853  * Implementation: user-space maintains a per-thread list of locks it
1854  * is holding. Upon do_exit(), the kernel carefully walks this list,
1855  * and marks all locks that are owned by this thread with the
1856  * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
1857  * always manipulated with the lock held, so the list is private and
1858  * per-thread. Userspace also maintains a per-thread 'list_op_pending'
1859  * field, to allow the kernel to clean up if the thread dies after
1860  * acquiring the lock, but just before it could have added itself to
1861  * the list. There can only be one such pending lock.
1862  */
1863
1864 /**
1865  * sys_set_robust_list - set the robust-futex list head of a task
1866  * @head: pointer to the list-head
1867  * @len: length of the list-head, as userspace expects
1868  */
1869 asmlinkage long
1870 sys_set_robust_list(struct robust_list_head __user *head,
1871                     size_t len)
1872 {
1873         /*
1874          * The kernel knows only one size for now:
1875          */
1876         if (unlikely(len != sizeof(*head)))
1877                 return -EINVAL;
1878
1879         current->robust_list = head;
1880
1881         return 0;
1882 }
1883
1884 /**
1885  * sys_get_robust_list - get the robust-futex list head of a task
1886  * @pid: pid of the process [zero for current task]
1887  * @head_ptr: pointer to a list-head pointer, the kernel fills it in
1888  * @len_ptr: pointer to a length field, the kernel fills in the header size
1889  */
1890 asmlinkage long
1891 sys_get_robust_list(int pid, struct robust_list_head __user * __user *head_ptr,
1892                     size_t __user *len_ptr)
1893 {
1894         struct robust_list_head __user *head;
1895         unsigned long ret;
1896
1897         if (!pid)
1898                 head = current->robust_list;
1899         else {
1900                 struct task_struct *p;
1901
1902                 ret = -ESRCH;
1903                 rcu_read_lock();
1904                 p = find_task_by_vpid(pid);
1905                 if (!p)
1906                         goto err_unlock;
1907                 ret = -EPERM;
1908                 if ((current->euid != p->euid) && (current->euid != p->uid) &&
1909                                 !capable(CAP_SYS_PTRACE))
1910                         goto err_unlock;
1911                 head = p->robust_list;
1912                 rcu_read_unlock();
1913         }
1914
1915         if (put_user(sizeof(*head), len_ptr))
1916                 return -EFAULT;
1917         return put_user(head, head_ptr);
1918
1919 err_unlock:
1920         rcu_read_unlock();
1921
1922         return ret;
1923 }
1924
1925 /*
1926  * Process a futex-list entry, check whether it's owned by the
1927  * dying task, and do notification if so:
1928  */
1929 int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
1930 {
1931         u32 uval, nval, mval;
1932
1933 retry:
1934         if (get_user(uval, uaddr))
1935                 return -1;
1936
1937         if ((uval & FUTEX_TID_MASK) == task_pid_vnr(curr)) {
1938                 /*
1939                  * Ok, this dying thread is truly holding a futex
1940                  * of interest. Set the OWNER_DIED bit atomically
1941                  * via cmpxchg, and if the value had FUTEX_WAITERS
1942                  * set, wake up a waiter (if any). (We have to do a
1943                  * futex_wake() even if OWNER_DIED is already set -
1944                  * to handle the rare but possible case of recursive
1945                  * thread-death.) The rest of the cleanup is done in
1946                  * userspace.
1947                  */
1948                 mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
1949                 nval = futex_atomic_cmpxchg_inatomic(uaddr, uval, mval);
1950
1951                 if (nval == -EFAULT)
1952                         return -1;
1953
1954                 if (nval != uval)
1955                         goto retry;
1956
1957                 /*
1958                  * Wake robust non-PI futexes here. The wakeup of
1959                  * PI futexes happens in exit_pi_state():
1960                  */
1961                 if (!pi && (uval & FUTEX_WAITERS))
1962                         futex_wake(uaddr, &curr->mm->mmap_sem, 1,
1963                                    FUTEX_BITSET_MATCH_ANY);
1964         }
1965         return 0;
1966 }
1967
1968 /*
1969  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
1970  */
1971 static inline int fetch_robust_entry(struct robust_list __user **entry,
1972                                      struct robust_list __user * __user *head,
1973                                      int *pi)
1974 {
1975         unsigned long uentry;
1976
1977         if (get_user(uentry, (unsigned long __user *)head))
1978                 return -EFAULT;
1979
1980         *entry = (void __user *)(uentry & ~1UL);
1981         *pi = uentry & 1;
1982
1983         return 0;
1984 }
1985
1986 /*
1987  * Walk curr->robust_list (very carefully, it's a userspace list!)
1988  * and mark any locks found there dead, and notify any waiters.
1989  *
1990  * We silently return on any sign of list-walking problem.
1991  */
1992 void exit_robust_list(struct task_struct *curr)
1993 {
1994         struct robust_list_head __user *head = curr->robust_list;
1995         struct robust_list __user *entry, *next_entry, *pending;
1996         unsigned int limit = ROBUST_LIST_LIMIT, pi, next_pi, pip;
1997         unsigned long futex_offset;
1998         int rc;
1999
2000         /*
2001          * Fetch the list head (which was registered earlier, via
2002          * sys_set_robust_list()):
2003          */
2004         if (fetch_robust_entry(&entry, &head->list.next, &pi))
2005                 return;
2006         /*
2007          * Fetch the relative futex offset:
2008          */
2009         if (get_user(futex_offset, &head->futex_offset))
2010                 return;
2011         /*
2012          * Fetch any possibly pending lock-add first, and handle it
2013          * if it exists:
2014          */
2015         if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
2016                 return;
2017
2018         next_entry = NULL;      /* avoid warning with gcc */
2019         while (entry != &head->list) {
2020                 /*
2021                  * Fetch the next entry in the list before calling
2022                  * handle_futex_death:
2023                  */
2024                 rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
2025                 /*
2026                  * A pending lock might already be on the list, so
2027                  * don't process it twice:
2028                  */
2029                 if (entry != pending)
2030                         if (handle_futex_death((void __user *)entry + futex_offset,
2031                                                 curr, pi))
2032                                 return;
2033                 if (rc)
2034                         return;
2035                 entry = next_entry;
2036                 pi = next_pi;
2037                 /*
2038                  * Avoid excessively long or circular lists:
2039                  */
2040                 if (!--limit)
2041                         break;
2042
2043                 cond_resched();
2044         }
2045
2046         if (pending)
2047                 handle_futex_death((void __user *)pending + futex_offset,
2048                                    curr, pip);
2049 }
2050
2051 long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
2052                 u32 __user *uaddr2, u32 val2, u32 val3)
2053 {
2054         int ret;
2055         int cmd = op & FUTEX_CMD_MASK;
2056         struct rw_semaphore *fshared = NULL;
2057
2058         if (!(op & FUTEX_PRIVATE_FLAG))
2059                 fshared = &current->mm->mmap_sem;
2060
2061         switch (cmd) {
2062         case FUTEX_WAIT:
2063                 val3 = FUTEX_BITSET_MATCH_ANY;
2064         case FUTEX_WAIT_BITSET:
2065                 ret = futex_wait(uaddr, fshared, val, timeout, val3);
2066                 break;
2067         case FUTEX_WAKE:
2068                 val3 = FUTEX_BITSET_MATCH_ANY;
2069         case FUTEX_WAKE_BITSET:
2070                 ret = futex_wake(uaddr, fshared, val, val3);
2071                 break;
2072         case FUTEX_FD:
2073                 /* non-zero val means F_SETOWN(getpid()) & F_SETSIG(val) */
2074                 ret = futex_fd(uaddr, val);
2075                 break;
2076         case FUTEX_REQUEUE:
2077                 ret = futex_requeue(uaddr, fshared, uaddr2, val, val2, NULL);
2078                 break;
2079         case FUTEX_CMP_REQUEUE:
2080                 ret = futex_requeue(uaddr, fshared, uaddr2, val, val2, &val3);
2081                 break;
2082         case FUTEX_WAKE_OP:
2083                 ret = futex_wake_op(uaddr, fshared, uaddr2, val, val2, val3);
2084                 break;
2085         case FUTEX_LOCK_PI:
2086                 ret = futex_lock_pi(uaddr, fshared, val, timeout, 0);
2087                 break;
2088         case FUTEX_UNLOCK_PI:
2089                 ret = futex_unlock_pi(uaddr, fshared);
2090                 break;
2091         case FUTEX_TRYLOCK_PI:
2092                 ret = futex_lock_pi(uaddr, fshared, 0, timeout, 1);
2093                 break;
2094         default:
2095                 ret = -ENOSYS;
2096         }
2097         return ret;
2098 }
2099
2100
2101 asmlinkage long sys_futex(u32 __user *uaddr, int op, u32 val,
2102                           struct timespec __user *utime, u32 __user *uaddr2,
2103                           u32 val3)
2104 {
2105         struct timespec ts;
2106         ktime_t t, *tp = NULL;
2107         u32 val2 = 0;
2108         int cmd = op & FUTEX_CMD_MASK;
2109
2110         if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
2111                       cmd == FUTEX_WAIT_BITSET)) {
2112                 if (copy_from_user(&ts, utime, sizeof(ts)) != 0)
2113                         return -EFAULT;
2114                 if (!timespec_valid(&ts))
2115                         return -EINVAL;
2116
2117                 t = timespec_to_ktime(ts);
2118                 if (cmd == FUTEX_WAIT)
2119                         t = ktime_add_safe(ktime_get(), t);
2120                 tp = &t;
2121         }
2122         /*
2123          * requeue parameter in 'utime' if cmd == FUTEX_REQUEUE.
2124          * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
2125          */
2126         if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
2127             cmd == FUTEX_WAKE_OP)
2128                 val2 = (u32) (unsigned long) utime;
2129
2130         return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
2131 }
2132
2133 static int futexfs_get_sb(struct file_system_type *fs_type,
2134                           int flags, const char *dev_name, void *data,
2135                           struct vfsmount *mnt)
2136 {
2137         return get_sb_pseudo(fs_type, "futex", NULL, FUTEXFS_SUPER_MAGIC, mnt);
2138 }
2139
2140 static struct file_system_type futex_fs_type = {
2141         .name           = "futexfs",
2142         .get_sb         = futexfs_get_sb,
2143         .kill_sb        = kill_anon_super,
2144 };
2145
2146 static int __init init(void)
2147 {
2148         int i;
2149
2150         for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
2151                 plist_head_init(&futex_queues[i].chain, &futex_queues[i].lock);
2152                 spin_lock_init(&futex_queues[i].lock);
2153         }
2154
2155         i = register_filesystem(&futex_fs_type);
2156         if (i)
2157                 return i;
2158
2159         futex_mnt = kern_mount(&futex_fs_type);
2160         if (IS_ERR(futex_mnt)) {
2161                 unregister_filesystem(&futex_fs_type);
2162                 return PTR_ERR(futex_mnt);
2163         }
2164
2165         return 0;
2166 }
2167 __initcall(init);