Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/kernel/futex.c

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us