linux - kernel/futex.c

2759 lines · 71.1 KiB

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 <[email protected]>
17	* Copyright (C) 2006 Timesys Corp., Thomas Gleixner <[email protected]>
18	*
19	* PRIVATE futexes by Eric Dumazet
20	* Copyright (C) 2007 Eric Dumazet <[email protected]>
21	*
22	* Requeue-PI support by Darren Hart <[email protected]>
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);