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