Merge git://git.kernel.org/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6
[linux-2.6] / 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  *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
12  *  enough at me, Linus for the original (flawed) idea, Matthew
13  *  Kirkwood for proof-of-concept implementation.
14  *
15  *  "The futexes are also cursed."
16  *  "But they come in a choice of three flavours!"
17  *
18  *  This program is free software; you can redistribute it and/or modify
19  *  it under the terms of the GNU General Public License as published by
20  *  the Free Software Foundation; either version 2 of the License, or
21  *  (at your option) any later version.
22  *
23  *  This program is distributed in the hope that it will be useful,
24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
26  *  GNU General Public License for more details.
27  *
28  *  You should have received a copy of the GNU General Public License
29  *  along with this program; if not, write to the Free Software
30  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
31  */
32 #include <linux/slab.h>
33 #include <linux/poll.h>
34 #include <linux/fs.h>
35 #include <linux/file.h>
36 #include <linux/jhash.h>
37 #include <linux/init.h>
38 #include <linux/futex.h>
39 #include <linux/mount.h>
40 #include <linux/pagemap.h>
41 #include <linux/syscalls.h>
42 #include <linux/signal.h>
43 #include <asm/futex.h>
44
45 #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
46
47 /*
48  * Futexes are matched on equal values of this key.
49  * The key type depends on whether it's a shared or private mapping.
50  * Don't rearrange members without looking at hash_futex().
51  *
52  * offset is aligned to a multiple of sizeof(u32) (== 4) by definition.
53  * We set bit 0 to indicate if it's an inode-based key.
54  */
55 union futex_key {
56         struct {
57                 unsigned long pgoff;
58                 struct inode *inode;
59                 int offset;
60         } shared;
61         struct {
62                 unsigned long uaddr;
63                 struct mm_struct *mm;
64                 int offset;
65         } private;
66         struct {
67                 unsigned long word;
68                 void *ptr;
69                 int offset;
70         } both;
71 };
72
73 /*
74  * We use this hashed waitqueue instead of a normal wait_queue_t, so
75  * we can wake only the relevant ones (hashed queues may be shared).
76  *
77  * A futex_q has a woken state, just like tasks have TASK_RUNNING.
78  * It is considered woken when list_empty(&q->list) || q->lock_ptr == 0.
79  * The order of wakup is always to make the first condition true, then
80  * wake up q->waiters, then make the second condition true.
81  */
82 struct futex_q {
83         struct list_head list;
84         wait_queue_head_t waiters;
85
86         /* Which hash list lock to use. */
87         spinlock_t *lock_ptr;
88
89         /* Key which the futex is hashed on. */
90         union futex_key key;
91
92         /* For fd, sigio sent using these. */
93         int fd;
94         struct file *filp;
95 };
96
97 /*
98  * Split the global futex_lock into every hash list lock.
99  */
100 struct futex_hash_bucket {
101        spinlock_t              lock;
102        struct list_head       chain;
103 };
104
105 static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
106
107 /* Futex-fs vfsmount entry: */
108 static struct vfsmount *futex_mnt;
109
110 /*
111  * We hash on the keys returned from get_futex_key (see below).
112  */
113 static struct futex_hash_bucket *hash_futex(union futex_key *key)
114 {
115         u32 hash = jhash2((u32*)&key->both.word,
116                           (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
117                           key->both.offset);
118         return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
119 }
120
121 /*
122  * Return 1 if two futex_keys are equal, 0 otherwise.
123  */
124 static inline int match_futex(union futex_key *key1, union futex_key *key2)
125 {
126         return (key1->both.word == key2->both.word
127                 && key1->both.ptr == key2->both.ptr
128                 && key1->both.offset == key2->both.offset);
129 }
130
131 /*
132  * Get parameters which are the keys for a futex.
133  *
134  * For shared mappings, it's (page->index, vma->vm_file->f_dentry->d_inode,
135  * offset_within_page).  For private mappings, it's (uaddr, current->mm).
136  * We can usually work out the index without swapping in the page.
137  *
138  * Returns: 0, or negative error code.
139  * The key words are stored in *key on success.
140  *
141  * Should be called with &current->mm->mmap_sem but NOT any spinlocks.
142  */
143 static int get_futex_key(unsigned long uaddr, union futex_key *key)
144 {
145         struct mm_struct *mm = current->mm;
146         struct vm_area_struct *vma;
147         struct page *page;
148         int err;
149
150         /*
151          * The futex address must be "naturally" aligned.
152          */
153         key->both.offset = uaddr % PAGE_SIZE;
154         if (unlikely((key->both.offset % sizeof(u32)) != 0))
155                 return -EINVAL;
156         uaddr -= key->both.offset;
157
158         /*
159          * The futex is hashed differently depending on whether
160          * it's in a shared or private mapping.  So check vma first.
161          */
162         vma = find_extend_vma(mm, uaddr);
163         if (unlikely(!vma))
164                 return -EFAULT;
165
166         /*
167          * Permissions.
168          */
169         if (unlikely((vma->vm_flags & (VM_IO|VM_READ)) != VM_READ))
170                 return (vma->vm_flags & VM_IO) ? -EPERM : -EACCES;
171
172         /*
173          * Private mappings are handled in a simple way.
174          *
175          * NOTE: When userspace waits on a MAP_SHARED mapping, even if
176          * it's a read-only handle, it's expected that futexes attach to
177          * the object not the particular process.  Therefore we use
178          * VM_MAYSHARE here, not VM_SHARED which is restricted to shared
179          * mappings of _writable_ handles.
180          */
181         if (likely(!(vma->vm_flags & VM_MAYSHARE))) {
182                 key->private.mm = mm;
183                 key->private.uaddr = uaddr;
184                 return 0;
185         }
186
187         /*
188          * Linear file mappings are also simple.
189          */
190         key->shared.inode = vma->vm_file->f_dentry->d_inode;
191         key->both.offset++; /* Bit 0 of offset indicates inode-based key. */
192         if (likely(!(vma->vm_flags & VM_NONLINEAR))) {
193                 key->shared.pgoff = (((uaddr - vma->vm_start) >> PAGE_SHIFT)
194                                      + vma->vm_pgoff);
195                 return 0;
196         }
197
198         /*
199          * We could walk the page table to read the non-linear
200          * pte, and get the page index without fetching the page
201          * from swap.  But that's a lot of code to duplicate here
202          * for a rare case, so we simply fetch the page.
203          */
204         err = get_user_pages(current, mm, uaddr, 1, 0, 0, &page, NULL);
205         if (err >= 0) {
206                 key->shared.pgoff =
207                         page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
208                 put_page(page);
209                 return 0;
210         }
211         return err;
212 }
213
214 /*
215  * Take a reference to the resource addressed by a key.
216  * Can be called while holding spinlocks.
217  *
218  * NOTE: mmap_sem MUST be held between get_futex_key() and calling this
219  * function, if it is called at all.  mmap_sem keeps key->shared.inode valid.
220  */
221 static inline void get_key_refs(union futex_key *key)
222 {
223         if (key->both.ptr != 0) {
224                 if (key->both.offset & 1)
225                         atomic_inc(&key->shared.inode->i_count);
226                 else
227                         atomic_inc(&key->private.mm->mm_count);
228         }
229 }
230
231 /*
232  * Drop a reference to the resource addressed by a key.
233  * The hash bucket spinlock must not be held.
234  */
235 static void drop_key_refs(union futex_key *key)
236 {
237         if (key->both.ptr != 0) {
238                 if (key->both.offset & 1)
239                         iput(key->shared.inode);
240                 else
241                         mmdrop(key->private.mm);
242         }
243 }
244
245 static inline int get_futex_value_locked(int *dest, int __user *from)
246 {
247         int ret;
248
249         inc_preempt_count();
250         ret = __copy_from_user_inatomic(dest, from, sizeof(int));
251         dec_preempt_count();
252
253         return ret ? -EFAULT : 0;
254 }
255
256 /*
257  * The hash bucket lock must be held when this is called.
258  * Afterwards, the futex_q must not be accessed.
259  */
260 static void wake_futex(struct futex_q *q)
261 {
262         list_del_init(&q->list);
263         if (q->filp)
264                 send_sigio(&q->filp->f_owner, q->fd, POLL_IN);
265         /*
266          * The lock in wake_up_all() is a crucial memory barrier after the
267          * list_del_init() and also before assigning to q->lock_ptr.
268          */
269         wake_up_all(&q->waiters);
270         /*
271          * The waiting task can free the futex_q as soon as this is written,
272          * without taking any locks.  This must come last.
273          *
274          * A memory barrier is required here to prevent the following store
275          * to lock_ptr from getting ahead of the wakeup. Clearing the lock
276          * at the end of wake_up_all() does not prevent this store from
277          * moving.
278          */
279         wmb();
280         q->lock_ptr = NULL;
281 }
282
283 /*
284  * Wake up all waiters hashed on the physical page that is mapped
285  * to this virtual address:
286  */
287 static int futex_wake(unsigned long uaddr, int nr_wake)
288 {
289         union futex_key key;
290         struct futex_hash_bucket *bh;
291         struct list_head *head;
292         struct futex_q *this, *next;
293         int ret;
294
295         down_read(&current->mm->mmap_sem);
296
297         ret = get_futex_key(uaddr, &key);
298         if (unlikely(ret != 0))
299                 goto out;
300
301         bh = hash_futex(&key);
302         spin_lock(&bh->lock);
303         head = &bh->chain;
304
305         list_for_each_entry_safe(this, next, head, list) {
306                 if (match_futex (&this->key, &key)) {
307                         wake_futex(this);
308                         if (++ret >= nr_wake)
309                                 break;
310                 }
311         }
312
313         spin_unlock(&bh->lock);
314 out:
315         up_read(&current->mm->mmap_sem);
316         return ret;
317 }
318
319 /*
320  * Wake up all waiters hashed on the physical page that is mapped
321  * to this virtual address:
322  */
323 static int futex_wake_op(unsigned long uaddr1, unsigned long uaddr2, int nr_wake, int nr_wake2, int op)
324 {
325         union futex_key key1, key2;
326         struct futex_hash_bucket *bh1, *bh2;
327         struct list_head *head;
328         struct futex_q *this, *next;
329         int ret, op_ret, attempt = 0;
330
331 retryfull:
332         down_read(&current->mm->mmap_sem);
333
334         ret = get_futex_key(uaddr1, &key1);
335         if (unlikely(ret != 0))
336                 goto out;
337         ret = get_futex_key(uaddr2, &key2);
338         if (unlikely(ret != 0))
339                 goto out;
340
341         bh1 = hash_futex(&key1);
342         bh2 = hash_futex(&key2);
343
344 retry:
345         if (bh1 < bh2)
346                 spin_lock(&bh1->lock);
347         spin_lock(&bh2->lock);
348         if (bh1 > bh2)
349                 spin_lock(&bh1->lock);
350
351         op_ret = futex_atomic_op_inuser(op, (int __user *)uaddr2);
352         if (unlikely(op_ret < 0)) {
353                 int dummy;
354
355                 spin_unlock(&bh1->lock);
356                 if (bh1 != bh2)
357                         spin_unlock(&bh2->lock);
358
359                 if (unlikely(op_ret != -EFAULT)) {
360                         ret = op_ret;
361                         goto out;
362                 }
363
364                 /* futex_atomic_op_inuser needs to both read and write
365                  * *(int __user *)uaddr2, but we can't modify it
366                  * non-atomically.  Therefore, if get_user below is not
367                  * enough, we need to handle the fault ourselves, while
368                  * still holding the mmap_sem.  */
369                 if (attempt++) {
370                         struct vm_area_struct * vma;
371                         struct mm_struct *mm = current->mm;
372
373                         ret = -EFAULT;
374                         if (attempt >= 2 ||
375                             !(vma = find_vma(mm, uaddr2)) ||
376                             vma->vm_start > uaddr2 ||
377                             !(vma->vm_flags & VM_WRITE))
378                                 goto out;
379
380                         switch (handle_mm_fault(mm, vma, uaddr2, 1)) {
381                         case VM_FAULT_MINOR:
382                                 current->min_flt++;
383                                 break;
384                         case VM_FAULT_MAJOR:
385                                 current->maj_flt++;
386                                 break;
387                         default:
388                                 goto out;
389                         }
390                         goto retry;
391                 }
392
393                 /* If we would have faulted, release mmap_sem,
394                  * fault it in and start all over again.  */
395                 up_read(&current->mm->mmap_sem);
396
397                 ret = get_user(dummy, (int __user *)uaddr2);
398                 if (ret)
399                         return ret;
400
401                 goto retryfull;
402         }
403
404         head = &bh1->chain;
405
406         list_for_each_entry_safe(this, next, head, list) {
407                 if (match_futex (&this->key, &key1)) {
408                         wake_futex(this);
409                         if (++ret >= nr_wake)
410                                 break;
411                 }
412         }
413
414         if (op_ret > 0) {
415                 head = &bh2->chain;
416
417                 op_ret = 0;
418                 list_for_each_entry_safe(this, next, head, list) {
419                         if (match_futex (&this->key, &key2)) {
420                                 wake_futex(this);
421                                 if (++op_ret >= nr_wake2)
422                                         break;
423                         }
424                 }
425                 ret += op_ret;
426         }
427
428         spin_unlock(&bh1->lock);
429         if (bh1 != bh2)
430                 spin_unlock(&bh2->lock);
431 out:
432         up_read(&current->mm->mmap_sem);
433         return ret;
434 }
435
436 /*
437  * Requeue all waiters hashed on one physical page to another
438  * physical page.
439  */
440 static int futex_requeue(unsigned long uaddr1, unsigned long uaddr2,
441                          int nr_wake, int nr_requeue, int *valp)
442 {
443         union futex_key key1, key2;
444         struct futex_hash_bucket *bh1, *bh2;
445         struct list_head *head1;
446         struct futex_q *this, *next;
447         int ret, drop_count = 0;
448
449  retry:
450         down_read(&current->mm->mmap_sem);
451
452         ret = get_futex_key(uaddr1, &key1);
453         if (unlikely(ret != 0))
454                 goto out;
455         ret = get_futex_key(uaddr2, &key2);
456         if (unlikely(ret != 0))
457                 goto out;
458
459         bh1 = hash_futex(&key1);
460         bh2 = hash_futex(&key2);
461
462         if (bh1 < bh2)
463                 spin_lock(&bh1->lock);
464         spin_lock(&bh2->lock);
465         if (bh1 > bh2)
466                 spin_lock(&bh1->lock);
467
468         if (likely(valp != NULL)) {
469                 int curval;
470
471                 ret = get_futex_value_locked(&curval, (int __user *)uaddr1);
472
473                 if (unlikely(ret)) {
474                         spin_unlock(&bh1->lock);
475                         if (bh1 != bh2)
476                                 spin_unlock(&bh2->lock);
477
478                         /* If we would have faulted, release mmap_sem, fault
479                          * it in and start all over again.
480                          */
481                         up_read(&current->mm->mmap_sem);
482
483                         ret = get_user(curval, (int __user *)uaddr1);
484
485                         if (!ret)
486                                 goto retry;
487
488                         return ret;
489                 }
490                 if (curval != *valp) {
491                         ret = -EAGAIN;
492                         goto out_unlock;
493                 }
494         }
495
496         head1 = &bh1->chain;
497         list_for_each_entry_safe(this, next, head1, list) {
498                 if (!match_futex (&this->key, &key1))
499                         continue;
500                 if (++ret <= nr_wake) {
501                         wake_futex(this);
502                 } else {
503                         list_move_tail(&this->list, &bh2->chain);
504                         this->lock_ptr = &bh2->lock;
505                         this->key = key2;
506                         get_key_refs(&key2);
507                         drop_count++;
508
509                         if (ret - nr_wake >= nr_requeue)
510                                 break;
511                         /* Make sure to stop if key1 == key2 */
512                         if (head1 == &bh2->chain && head1 != &next->list)
513                                 head1 = &this->list;
514                 }
515         }
516
517 out_unlock:
518         spin_unlock(&bh1->lock);
519         if (bh1 != bh2)
520                 spin_unlock(&bh2->lock);
521
522         /* drop_key_refs() must be called outside the spinlocks. */
523         while (--drop_count >= 0)
524                 drop_key_refs(&key1);
525
526 out:
527         up_read(&current->mm->mmap_sem);
528         return ret;
529 }
530
531 /* The key must be already stored in q->key. */
532 static inline struct futex_hash_bucket *
533 queue_lock(struct futex_q *q, int fd, struct file *filp)
534 {
535         struct futex_hash_bucket *bh;
536
537         q->fd = fd;
538         q->filp = filp;
539
540         init_waitqueue_head(&q->waiters);
541
542         get_key_refs(&q->key);
543         bh = hash_futex(&q->key);
544         q->lock_ptr = &bh->lock;
545
546         spin_lock(&bh->lock);
547         return bh;
548 }
549
550 static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *bh)
551 {
552         list_add_tail(&q->list, &bh->chain);
553         spin_unlock(&bh->lock);
554 }
555
556 static inline void
557 queue_unlock(struct futex_q *q, struct futex_hash_bucket *bh)
558 {
559         spin_unlock(&bh->lock);
560         drop_key_refs(&q->key);
561 }
562
563 /*
564  * queue_me and unqueue_me must be called as a pair, each
565  * exactly once.  They are called with the hashed spinlock held.
566  */
567
568 /* The key must be already stored in q->key. */
569 static void queue_me(struct futex_q *q, int fd, struct file *filp)
570 {
571         struct futex_hash_bucket *bh;
572         bh = queue_lock(q, fd, filp);
573         __queue_me(q, bh);
574 }
575
576 /* Return 1 if we were still queued (ie. 0 means we were woken) */
577 static int unqueue_me(struct futex_q *q)
578 {
579         int ret = 0;
580         spinlock_t *lock_ptr;
581
582         /* In the common case we don't take the spinlock, which is nice. */
583  retry:
584         lock_ptr = q->lock_ptr;
585         if (lock_ptr != 0) {
586                 spin_lock(lock_ptr);
587                 /*
588                  * q->lock_ptr can change between reading it and
589                  * spin_lock(), causing us to take the wrong lock.  This
590                  * corrects the race condition.
591                  *
592                  * Reasoning goes like this: if we have the wrong lock,
593                  * q->lock_ptr must have changed (maybe several times)
594                  * between reading it and the spin_lock().  It can
595                  * change again after the spin_lock() but only if it was
596                  * already changed before the spin_lock().  It cannot,
597                  * however, change back to the original value.  Therefore
598                  * we can detect whether we acquired the correct lock.
599                  */
600                 if (unlikely(lock_ptr != q->lock_ptr)) {
601                         spin_unlock(lock_ptr);
602                         goto retry;
603                 }
604                 WARN_ON(list_empty(&q->list));
605                 list_del(&q->list);
606                 spin_unlock(lock_ptr);
607                 ret = 1;
608         }
609
610         drop_key_refs(&q->key);
611         return ret;
612 }
613
614 static int futex_wait(unsigned long uaddr, int val, unsigned long time)
615 {
616         DECLARE_WAITQUEUE(wait, current);
617         int ret, curval;
618         struct futex_q q;
619         struct futex_hash_bucket *bh;
620
621  retry:
622         down_read(&current->mm->mmap_sem);
623
624         ret = get_futex_key(uaddr, &q.key);
625         if (unlikely(ret != 0))
626                 goto out_release_sem;
627
628         bh = queue_lock(&q, -1, NULL);
629
630         /*
631          * Access the page AFTER the futex is queued.
632          * Order is important:
633          *
634          *   Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
635          *   Userspace waker:  if (cond(var)) { var = new; futex_wake(&var); }
636          *
637          * The basic logical guarantee of a futex is that it blocks ONLY
638          * if cond(var) is known to be true at the time of blocking, for
639          * any cond.  If we queued after testing *uaddr, that would open
640          * a race condition where we could block indefinitely with
641          * cond(var) false, which would violate the guarantee.
642          *
643          * A consequence is that futex_wait() can return zero and absorb
644          * a wakeup when *uaddr != val on entry to the syscall.  This is
645          * rare, but normal.
646          *
647          * We hold the mmap semaphore, so the mapping cannot have changed
648          * since we looked it up in get_futex_key.
649          */
650
651         ret = get_futex_value_locked(&curval, (int __user *)uaddr);
652
653         if (unlikely(ret)) {
654                 queue_unlock(&q, bh);
655
656                 /* If we would have faulted, release mmap_sem, fault it in and
657                  * start all over again.
658                  */
659                 up_read(&current->mm->mmap_sem);
660
661                 ret = get_user(curval, (int __user *)uaddr);
662
663                 if (!ret)
664                         goto retry;
665                 return ret;
666         }
667         if (curval != val) {
668                 ret = -EWOULDBLOCK;
669                 queue_unlock(&q, bh);
670                 goto out_release_sem;
671         }
672
673         /* Only actually queue if *uaddr contained val.  */
674         __queue_me(&q, bh);
675
676         /*
677          * Now the futex is queued and we have checked the data, we
678          * don't want to hold mmap_sem while we sleep.
679          */     
680         up_read(&current->mm->mmap_sem);
681
682         /*
683          * There might have been scheduling since the queue_me(), as we
684          * cannot hold a spinlock across the get_user() in case it
685          * faults, and we cannot just set TASK_INTERRUPTIBLE state when
686          * queueing ourselves into the futex hash.  This code thus has to
687          * rely on the futex_wake() code removing us from hash when it
688          * wakes us up.
689          */
690
691         /* add_wait_queue is the barrier after __set_current_state. */
692         __set_current_state(TASK_INTERRUPTIBLE);
693         add_wait_queue(&q.waiters, &wait);
694         /*
695          * !list_empty() is safe here without any lock.
696          * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
697          */
698         if (likely(!list_empty(&q.list)))
699                 time = schedule_timeout(time);
700         __set_current_state(TASK_RUNNING);
701
702         /*
703          * NOTE: we don't remove ourselves from the waitqueue because
704          * we are the only user of it.
705          */
706
707         /* If we were woken (and unqueued), we succeeded, whatever. */
708         if (!unqueue_me(&q))
709                 return 0;
710         if (time == 0)
711                 return -ETIMEDOUT;
712         /* We expect signal_pending(current), but another thread may
713          * have handled it for us already. */
714         return -EINTR;
715
716  out_release_sem:
717         up_read(&current->mm->mmap_sem);
718         return ret;
719 }
720
721 static int futex_close(struct inode *inode, struct file *filp)
722 {
723         struct futex_q *q = filp->private_data;
724
725         unqueue_me(q);
726         kfree(q);
727         return 0;
728 }
729
730 /* This is one-shot: once it's gone off you need a new fd */
731 static unsigned int futex_poll(struct file *filp,
732                                struct poll_table_struct *wait)
733 {
734         struct futex_q *q = filp->private_data;
735         int ret = 0;
736
737         poll_wait(filp, &q->waiters, wait);
738
739         /*
740          * list_empty() is safe here without any lock.
741          * q->lock_ptr != 0 is not safe, because of ordering against wakeup.
742          */
743         if (list_empty(&q->list))
744                 ret = POLLIN | POLLRDNORM;
745
746         return ret;
747 }
748
749 static struct file_operations futex_fops = {
750         .release        = futex_close,
751         .poll           = futex_poll,
752 };
753
754 /*
755  * Signal allows caller to avoid the race which would occur if they
756  * set the sigio stuff up afterwards.
757  */
758 static int futex_fd(unsigned long uaddr, int signal)
759 {
760         struct futex_q *q;
761         struct file *filp;
762         int ret, err;
763
764         ret = -EINVAL;
765         if (!valid_signal(signal))
766                 goto out;
767
768         ret = get_unused_fd();
769         if (ret < 0)
770                 goto out;
771         filp = get_empty_filp();
772         if (!filp) {
773                 put_unused_fd(ret);
774                 ret = -ENFILE;
775                 goto out;
776         }
777         filp->f_op = &futex_fops;
778         filp->f_vfsmnt = mntget(futex_mnt);
779         filp->f_dentry = dget(futex_mnt->mnt_root);
780         filp->f_mapping = filp->f_dentry->d_inode->i_mapping;
781
782         if (signal) {
783                 err = f_setown(filp, current->pid, 1);
784                 if (err < 0) {
785                         goto error;
786                 }
787                 filp->f_owner.signum = signal;
788         }
789
790         q = kmalloc(sizeof(*q), GFP_KERNEL);
791         if (!q) {
792                 err = -ENOMEM;
793                 goto error;
794         }
795
796         down_read(&current->mm->mmap_sem);
797         err = get_futex_key(uaddr, &q->key);
798
799         if (unlikely(err != 0)) {
800                 up_read(&current->mm->mmap_sem);
801                 kfree(q);
802                 goto error;
803         }
804
805         /*
806          * queue_me() must be called before releasing mmap_sem, because
807          * key->shared.inode needs to be referenced while holding it.
808          */
809         filp->private_data = q;
810
811         queue_me(q, ret, filp);
812         up_read(&current->mm->mmap_sem);
813
814         /* Now we map fd to filp, so userspace can access it */
815         fd_install(ret, filp);
816 out:
817         return ret;
818 error:
819         put_unused_fd(ret);
820         put_filp(filp);
821         ret = err;
822         goto out;
823 }
824
825 long do_futex(unsigned long uaddr, int op, int val, unsigned long timeout,
826                 unsigned long uaddr2, int val2, int val3)
827 {
828         int ret;
829
830         switch (op) {
831         case FUTEX_WAIT:
832                 ret = futex_wait(uaddr, val, timeout);
833                 break;
834         case FUTEX_WAKE:
835                 ret = futex_wake(uaddr, val);
836                 break;
837         case FUTEX_FD:
838                 /* non-zero val means F_SETOWN(getpid()) & F_SETSIG(val) */
839                 ret = futex_fd(uaddr, val);
840                 break;
841         case FUTEX_REQUEUE:
842                 ret = futex_requeue(uaddr, uaddr2, val, val2, NULL);
843                 break;
844         case FUTEX_CMP_REQUEUE:
845                 ret = futex_requeue(uaddr, uaddr2, val, val2, &val3);
846                 break;
847         case FUTEX_WAKE_OP:
848                 ret = futex_wake_op(uaddr, uaddr2, val, val2, val3);
849                 break;
850         default:
851                 ret = -ENOSYS;
852         }
853         return ret;
854 }
855
856
857 asmlinkage long sys_futex(u32 __user *uaddr, int op, int val,
858                           struct timespec __user *utime, u32 __user *uaddr2,
859                           int val3)
860 {
861         struct timespec t;
862         unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
863         int val2 = 0;
864
865         if ((op == FUTEX_WAIT) && utime) {
866                 if (copy_from_user(&t, utime, sizeof(t)) != 0)
867                         return -EFAULT;
868                 timeout = timespec_to_jiffies(&t) + 1;
869         }
870         /*
871          * requeue parameter in 'utime' if op == FUTEX_REQUEUE.
872          */
873         if (op >= FUTEX_REQUEUE)
874                 val2 = (int) (unsigned long) utime;
875
876         return do_futex((unsigned long)uaddr, op, val, timeout,
877                         (unsigned long)uaddr2, val2, val3);
878 }
879
880 static struct super_block *
881 futexfs_get_sb(struct file_system_type *fs_type,
882                int flags, const char *dev_name, void *data)
883 {
884         return get_sb_pseudo(fs_type, "futex", NULL, 0xBAD1DEA);
885 }
886
887 static struct file_system_type futex_fs_type = {
888         .name           = "futexfs",
889         .get_sb         = futexfs_get_sb,
890         .kill_sb        = kill_anon_super,
891 };
892
893 static int __init init(void)
894 {
895         unsigned int i;
896
897         register_filesystem(&futex_fs_type);
898         futex_mnt = kern_mount(&futex_fs_type);
899
900         for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
901                 INIT_LIST_HEAD(&futex_queues[i].chain);
902                 spin_lock_init(&futex_queues[i].lock);
903         }
904         return 0;
905 }
906 __initcall(init);