futex.c 48.0 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10
/*
 *  Fast Userspace Mutexes (which I call "Futexes!").
 *  (C) Rusty Russell, IBM 2002
 *
 *  Generalized futexes, futex requeueing, misc fixes by Ingo Molnar
 *  (C) Copyright 2003 Red Hat Inc, All Rights Reserved
 *
 *  Removed page pinning, fix privately mapped COW pages and other cleanups
 *  (C) Copyright 2003, 2004 Jamie Lokier
 *
11 12 13 14
 *  Robust futex support started by Ingo Molnar
 *  (C) Copyright 2006 Red Hat Inc, All Rights Reserved
 *  Thanks to Thomas Gleixner for suggestions, analysis and fixes.
 *
15 16 17 18
 *  PI-futex support started by Ingo Molnar and Thomas Gleixner
 *  Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
 *  Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
 *
E
Eric Dumazet 已提交
19 20 21
 *  PRIVATE futexes by Eric Dumazet
 *  Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com>
 *
L
Linus Torvalds 已提交
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
 *  Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
 *  enough at me, Linus for the original (flawed) idea, Matthew
 *  Kirkwood for proof-of-concept implementation.
 *
 *  "The futexes are also cursed."
 *  "But they come in a choice of three flavours!"
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include <linux/slab.h>
#include <linux/poll.h>
#include <linux/fs.h>
#include <linux/file.h>
#include <linux/jhash.h>
#include <linux/init.h>
#include <linux/futex.h>
#include <linux/mount.h>
#include <linux/pagemap.h>
#include <linux/syscalls.h>
53
#include <linux/signal.h>
54
#include <linux/module.h>
55
#include <linux/magic.h>
56 57 58
#include <linux/pid.h>
#include <linux/nsproxy.h>

59
#include <asm/futex.h>
L
Linus Torvalds 已提交
60

61 62
#include "rtmutex_common.h"

63 64
int __read_mostly futex_cmpxchg_enabled;

L
Linus Torvalds 已提交
65 66
#define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)

67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
/*
 * Priority Inheritance state:
 */
struct futex_pi_state {
	/*
	 * list of 'owned' pi_state instances - these have to be
	 * cleaned up in do_exit() if the task exits prematurely:
	 */
	struct list_head list;

	/*
	 * The PI object:
	 */
	struct rt_mutex pi_mutex;

	struct task_struct *owner;
	atomic_t refcount;

	union futex_key key;
};

L
Linus Torvalds 已提交
88 89 90 91 92
/*
 * We use this hashed waitqueue instead of a normal wait_queue_t, so
 * we can wake only the relevant ones (hashed queues may be shared).
 *
 * A futex_q has a woken state, just like tasks have TASK_RUNNING.
P
Pierre Peiffer 已提交
93
 * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
L
Linus Torvalds 已提交
94
 * The order of wakup is always to make the first condition true, then
95
 * wake up q->waiter, then make the second condition true.
L
Linus Torvalds 已提交
96 97
 */
struct futex_q {
P
Pierre Peiffer 已提交
98
	struct plist_node list;
99 100
	/* There can only be a single waiter */
	wait_queue_head_t waiter;
L
Linus Torvalds 已提交
101

102
	/* Which hash list lock to use: */
L
Linus Torvalds 已提交
103 104
	spinlock_t *lock_ptr;

105
	/* Key which the futex is hashed on: */
L
Linus Torvalds 已提交
106 107
	union futex_key key;

108 109 110
	/* Optional priority inheritance state: */
	struct futex_pi_state *pi_state;
	struct task_struct *task;
111 112 113

	/* Bitset for the optional bitmasked wakeup */
	u32 bitset;
L
Linus Torvalds 已提交
114 115 116
};

/*
D
Darren Hart 已提交
117 118 119
 * Hash buckets are shared by all the futex_keys that hash to the same
 * location.  Each key may have multiple futex_q structures, one for each task
 * waiting on a futex.
L
Linus Torvalds 已提交
120 121
 */
struct futex_hash_bucket {
P
Pierre Peiffer 已提交
122 123
	spinlock_t lock;
	struct plist_head chain;
L
Linus Torvalds 已提交
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
};

static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];

/*
 * We hash on the keys returned from get_futex_key (see below).
 */
static struct futex_hash_bucket *hash_futex(union futex_key *key)
{
	u32 hash = jhash2((u32*)&key->both.word,
			  (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
			  key->both.offset);
	return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
}

/*
 * Return 1 if two futex_keys are equal, 0 otherwise.
 */
static inline int match_futex(union futex_key *key1, union futex_key *key2)
{
	return (key1->both.word == key2->both.word
		&& key1->both.ptr == key2->both.ptr
		&& key1->both.offset == key2->both.offset);
}

149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
/*
 * Take a reference to the resource addressed by a key.
 * Can be called while holding spinlocks.
 *
 */
static void get_futex_key_refs(union futex_key *key)
{
	if (!key->both.ptr)
		return;

	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
	case FUT_OFF_INODE:
		atomic_inc(&key->shared.inode->i_count);
		break;
	case FUT_OFF_MMSHARED:
		atomic_inc(&key->private.mm->mm_count);
		break;
	}
}

/*
 * Drop a reference to the resource addressed by a key.
 * The hash bucket spinlock must not be held.
 */
static void drop_futex_key_refs(union futex_key *key)
{
175 176 177
	if (!key->both.ptr) {
		/* If we're here then we tried to put a key we failed to get */
		WARN_ON_ONCE(1);
178
		return;
179
	}
180 181 182 183 184 185 186 187 188 189 190

	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
	case FUT_OFF_INODE:
		iput(key->shared.inode);
		break;
	case FUT_OFF_MMSHARED:
		mmdrop(key->private.mm);
		break;
	}
}

E
Eric Dumazet 已提交
191 192 193
/**
 * get_futex_key - Get parameters which are the keys for a futex.
 * @uaddr: virtual address of the futex
D
Darren Hart 已提交
194
 * @fshared: 0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
E
Eric Dumazet 已提交
195 196 197 198
 * @key: address where result is stored.
 *
 * Returns a negative error code or 0
 * The key words are stored in *key on success.
L
Linus Torvalds 已提交
199
 *
200
 * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode,
L
Linus Torvalds 已提交
201 202 203
 * offset_within_page).  For private mappings, it's (uaddr, current->mm).
 * We can usually work out the index without swapping in the page.
 *
D
Darren Hart 已提交
204
 * lock_page() might sleep, the caller should not hold a spinlock.
L
Linus Torvalds 已提交
205
 */
P
Peter Zijlstra 已提交
206
static int get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key)
L
Linus Torvalds 已提交
207
{
208
	unsigned long address = (unsigned long)uaddr;
L
Linus Torvalds 已提交
209 210 211 212 213 214 215
	struct mm_struct *mm = current->mm;
	struct page *page;
	int err;

	/*
	 * The futex address must be "naturally" aligned.
	 */
216
	key->both.offset = address % PAGE_SIZE;
E
Eric Dumazet 已提交
217
	if (unlikely((address % sizeof(u32)) != 0))
L
Linus Torvalds 已提交
218
		return -EINVAL;
219
	address -= key->both.offset;
L
Linus Torvalds 已提交
220

E
Eric Dumazet 已提交
221 222 223 224 225 226 227 228 229 230 231 232
	/*
	 * PROCESS_PRIVATE futexes are fast.
	 * As the mm cannot disappear under us and the 'key' only needs
	 * virtual address, we dont even have to find the underlying vma.
	 * Note : We do have to check 'uaddr' is a valid user address,
	 *        but access_ok() should be faster than find_vma()
	 */
	if (!fshared) {
		if (unlikely(!access_ok(VERIFY_WRITE, uaddr, sizeof(u32))))
			return -EFAULT;
		key->private.mm = mm;
		key->private.address = address;
233
		get_futex_key_refs(key);
E
Eric Dumazet 已提交
234 235
		return 0;
	}
L
Linus Torvalds 已提交
236

237
again:
P
Peter Zijlstra 已提交
238
	err = get_user_pages_fast(address, 1, 0, &page);
239 240 241 242 243 244 245 246 247
	if (err < 0)
		return err;

	lock_page(page);
	if (!page->mapping) {
		unlock_page(page);
		put_page(page);
		goto again;
	}
L
Linus Torvalds 已提交
248 249 250 251 252 253

	/*
	 * Private mappings are handled in a simple way.
	 *
	 * NOTE: When userspace waits on a MAP_SHARED mapping, even if
	 * it's a read-only handle, it's expected that futexes attach to
254
	 * the object not the particular process.
L
Linus Torvalds 已提交
255
	 */
256 257
	if (PageAnon(page)) {
		key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
L
Linus Torvalds 已提交
258
		key->private.mm = mm;
259
		key->private.address = address;
260 261 262 263
	} else {
		key->both.offset |= FUT_OFF_INODE; /* inode-based key */
		key->shared.inode = page->mapping->host;
		key->shared.pgoff = page->index;
L
Linus Torvalds 已提交
264 265
	}

266
	get_futex_key_refs(key);
L
Linus Torvalds 已提交
267

268 269 270
	unlock_page(page);
	put_page(page);
	return 0;
L
Linus Torvalds 已提交
271 272
}

273
static inline
P
Peter Zijlstra 已提交
274
void put_futex_key(int fshared, union futex_key *key)
L
Linus Torvalds 已提交
275
{
276
	drop_futex_key_refs(key);
L
Linus Torvalds 已提交
277 278
}

T
Thomas Gleixner 已提交
279 280 281 282 283 284 285 286 287 288 289 290
static u32 cmpxchg_futex_value_locked(u32 __user *uaddr, u32 uval, u32 newval)
{
	u32 curval;

	pagefault_disable();
	curval = futex_atomic_cmpxchg_inatomic(uaddr, uval, newval);
	pagefault_enable();

	return curval;
}

static int get_futex_value_locked(u32 *dest, u32 __user *from)
L
Linus Torvalds 已提交
291 292 293
{
	int ret;

294
	pagefault_disable();
295
	ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
296
	pagefault_enable();
L
Linus Torvalds 已提交
297 298 299 300

	return ret ? -EFAULT : 0;
}

301 302 303 304 305 306 307 308 309 310 311

/*
 * PI code:
 */
static int refill_pi_state_cache(void)
{
	struct futex_pi_state *pi_state;

	if (likely(current->pi_state_cache))
		return 0;

312
	pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
313 314 315 316 317 318 319 320

	if (!pi_state)
		return -ENOMEM;

	INIT_LIST_HEAD(&pi_state->list);
	/* pi_mutex gets initialized later */
	pi_state->owner = NULL;
	atomic_set(&pi_state->refcount, 1);
321
	pi_state->key = FUTEX_KEY_INIT;
322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375

	current->pi_state_cache = pi_state;

	return 0;
}

static struct futex_pi_state * alloc_pi_state(void)
{
	struct futex_pi_state *pi_state = current->pi_state_cache;

	WARN_ON(!pi_state);
	current->pi_state_cache = NULL;

	return pi_state;
}

static void free_pi_state(struct futex_pi_state *pi_state)
{
	if (!atomic_dec_and_test(&pi_state->refcount))
		return;

	/*
	 * If pi_state->owner is NULL, the owner is most probably dying
	 * and has cleaned up the pi_state already
	 */
	if (pi_state->owner) {
		spin_lock_irq(&pi_state->owner->pi_lock);
		list_del_init(&pi_state->list);
		spin_unlock_irq(&pi_state->owner->pi_lock);

		rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
	}

	if (current->pi_state_cache)
		kfree(pi_state);
	else {
		/*
		 * pi_state->list is already empty.
		 * clear pi_state->owner.
		 * refcount is at 0 - put it back to 1.
		 */
		pi_state->owner = NULL;
		atomic_set(&pi_state->refcount, 1);
		current->pi_state_cache = pi_state;
	}
}

/*
 * Look up the task based on what TID userspace gave us.
 * We dont trust it.
 */
static struct task_struct * futex_find_get_task(pid_t pid)
{
	struct task_struct *p;
376
	const struct cred *cred = current_cred(), *pcred;
377

378
	rcu_read_lock();
379
	p = find_task_by_vpid(pid);
380
	if (!p) {
381
		p = ERR_PTR(-ESRCH);
382 383 384 385 386 387 388 389
	} else {
		pcred = __task_cred(p);
		if (cred->euid != pcred->euid &&
		    cred->euid != pcred->uid)
			p = ERR_PTR(-ESRCH);
		else
			get_task_struct(p);
	}
390

391
	rcu_read_unlock();
392 393 394 395 396 397 398 399 400 401 402 403 404

	return p;
}

/*
 * This task is holding PI mutexes at exit time => bad.
 * Kernel cleans up PI-state, but userspace is likely hosed.
 * (Robust-futex cleanup is separate and might save the day for userspace.)
 */
void exit_pi_state_list(struct task_struct *curr)
{
	struct list_head *next, *head = &curr->pi_state_list;
	struct futex_pi_state *pi_state;
405
	struct futex_hash_bucket *hb;
406
	union futex_key key = FUTEX_KEY_INIT;
407

408 409
	if (!futex_cmpxchg_enabled)
		return;
410 411 412
	/*
	 * We are a ZOMBIE and nobody can enqueue itself on
	 * pi_state_list anymore, but we have to be careful
413
	 * versus waiters unqueueing themselves:
414 415 416 417 418 419 420
	 */
	spin_lock_irq(&curr->pi_lock);
	while (!list_empty(head)) {

		next = head->next;
		pi_state = list_entry(next, struct futex_pi_state, list);
		key = pi_state->key;
421
		hb = hash_futex(&key);
422 423 424 425 426
		spin_unlock_irq(&curr->pi_lock);

		spin_lock(&hb->lock);

		spin_lock_irq(&curr->pi_lock);
427 428 429 430
		/*
		 * We dropped the pi-lock, so re-check whether this
		 * task still owns the PI-state:
		 */
431 432 433 434 435 436
		if (head->next != next) {
			spin_unlock(&hb->lock);
			continue;
		}

		WARN_ON(pi_state->owner != curr);
437 438
		WARN_ON(list_empty(&pi_state->list));
		list_del_init(&pi_state->list);
439 440 441 442 443 444 445 446 447 448 449 450 451
		pi_state->owner = NULL;
		spin_unlock_irq(&curr->pi_lock);

		rt_mutex_unlock(&pi_state->pi_mutex);

		spin_unlock(&hb->lock);

		spin_lock_irq(&curr->pi_lock);
	}
	spin_unlock_irq(&curr->pi_lock);
}

static int
P
Pierre Peiffer 已提交
452 453
lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
		union futex_key *key, struct futex_pi_state **ps)
454 455 456
{
	struct futex_pi_state *pi_state = NULL;
	struct futex_q *this, *next;
P
Pierre Peiffer 已提交
457
	struct plist_head *head;
458
	struct task_struct *p;
459
	pid_t pid = uval & FUTEX_TID_MASK;
460 461 462

	head = &hb->chain;

P
Pierre Peiffer 已提交
463
	plist_for_each_entry_safe(this, next, head, list) {
P
Pierre Peiffer 已提交
464
		if (match_futex(&this->key, key)) {
465 466 467 468 469
			/*
			 * Another waiter already exists - bump up
			 * the refcount and return its pi_state:
			 */
			pi_state = this->pi_state;
470 471 472 473 474 475
			/*
			 * Userspace might have messed up non PI and PI futexes
			 */
			if (unlikely(!pi_state))
				return -EINVAL;

476
			WARN_ON(!atomic_read(&pi_state->refcount));
477 478
			WARN_ON(pid && pi_state->owner &&
				pi_state->owner->pid != pid);
479

480
			atomic_inc(&pi_state->refcount);
P
Pierre Peiffer 已提交
481
			*ps = pi_state;
482 483 484 485 486 487

			return 0;
		}
	}

	/*
488
	 * We are the first waiter - try to look up the real owner and attach
489
	 * the new pi_state to it, but bail out when TID = 0
490
	 */
491
	if (!pid)
492
		return -ESRCH;
493
	p = futex_find_get_task(pid);
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
	if (IS_ERR(p))
		return PTR_ERR(p);

	/*
	 * We need to look at the task state flags to figure out,
	 * whether the task is exiting. To protect against the do_exit
	 * change of the task flags, we do this protected by
	 * p->pi_lock:
	 */
	spin_lock_irq(&p->pi_lock);
	if (unlikely(p->flags & PF_EXITING)) {
		/*
		 * The task is on the way out. When PF_EXITPIDONE is
		 * set, we know that the task has finished the
		 * cleanup:
		 */
		int ret = (p->flags & PF_EXITPIDONE) ? -ESRCH : -EAGAIN;

		spin_unlock_irq(&p->pi_lock);
		put_task_struct(p);
		return ret;
	}
516 517 518 519 520 521 522 523 524 525

	pi_state = alloc_pi_state();

	/*
	 * Initialize the pi_mutex in locked state and make 'p'
	 * the owner of it:
	 */
	rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);

	/* Store the key for possible exit cleanups: */
P
Pierre Peiffer 已提交
526
	pi_state->key = *key;
527

528
	WARN_ON(!list_empty(&pi_state->list));
529 530 531 532 533 534
	list_add(&pi_state->list, &p->pi_state_list);
	pi_state->owner = p;
	spin_unlock_irq(&p->pi_lock);

	put_task_struct(p);

P
Pierre Peiffer 已提交
535
	*ps = pi_state;
536 537 538 539

	return 0;
}

L
Linus Torvalds 已提交
540 541 542 543 544 545
/*
 * The hash bucket lock must be held when this is called.
 * Afterwards, the futex_q must not be accessed.
 */
static void wake_futex(struct futex_q *q)
{
P
Pierre Peiffer 已提交
546
	plist_del(&q->list, &q->list.plist);
L
Linus Torvalds 已提交
547 548
	/*
	 * The lock in wake_up_all() is a crucial memory barrier after the
P
Pierre Peiffer 已提交
549
	 * plist_del() and also before assigning to q->lock_ptr.
L
Linus Torvalds 已提交
550
	 */
551
	wake_up(&q->waiter);
L
Linus Torvalds 已提交
552 553 554
	/*
	 * The waiting task can free the futex_q as soon as this is written,
	 * without taking any locks.  This must come last.
555
	 *
D
Darren Hart 已提交
556 557 558
	 * A memory barrier is required here to prevent the following store to
	 * lock_ptr from getting ahead of the wakeup. Clearing the lock at the
	 * end of wake_up() does not prevent this store from moving.
L
Linus Torvalds 已提交
559
	 */
560
	smp_wmb();
L
Linus Torvalds 已提交
561 562 563
	q->lock_ptr = NULL;
}

564 565 566 567 568 569 570 571 572
static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
{
	struct task_struct *new_owner;
	struct futex_pi_state *pi_state = this->pi_state;
	u32 curval, newval;

	if (!pi_state)
		return -EINVAL;

573
	spin_lock(&pi_state->pi_mutex.wait_lock);
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);

	/*
	 * This happens when we have stolen the lock and the original
	 * pending owner did not enqueue itself back on the rt_mutex.
	 * Thats not a tragedy. We know that way, that a lock waiter
	 * is on the fly. We make the futex_q waiter the pending owner.
	 */
	if (!new_owner)
		new_owner = this->task;

	/*
	 * We pass it to the next owner. (The WAITERS bit is always
	 * kept enabled while there is PI state around. We must also
	 * preserve the owner died bit.)
	 */
590
	if (!(uval & FUTEX_OWNER_DIED)) {
591 592
		int ret = 0;

593
		newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
594

T
Thomas Gleixner 已提交
595
		curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
596

597
		if (curval == -EFAULT)
598
			ret = -EFAULT;
599
		else if (curval != uval)
600 601 602 603 604
			ret = -EINVAL;
		if (ret) {
			spin_unlock(&pi_state->pi_mutex.wait_lock);
			return ret;
		}
605
	}
606

607 608 609 610 611 612 613
	spin_lock_irq(&pi_state->owner->pi_lock);
	WARN_ON(list_empty(&pi_state->list));
	list_del_init(&pi_state->list);
	spin_unlock_irq(&pi_state->owner->pi_lock);

	spin_lock_irq(&new_owner->pi_lock);
	WARN_ON(!list_empty(&pi_state->list));
614 615
	list_add(&pi_state->list, &new_owner->pi_state_list);
	pi_state->owner = new_owner;
616 617
	spin_unlock_irq(&new_owner->pi_lock);

618
	spin_unlock(&pi_state->pi_mutex.wait_lock);
619 620 621 622 623 624 625 626 627 628 629 630 631
	rt_mutex_unlock(&pi_state->pi_mutex);

	return 0;
}

static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
{
	u32 oldval;

	/*
	 * There is no waiter, so we unlock the futex. The owner died
	 * bit has not to be preserved here. We are the owner:
	 */
T
Thomas Gleixner 已提交
632
	oldval = cmpxchg_futex_value_locked(uaddr, uval, 0);
633 634 635 636 637 638 639 640 641

	if (oldval == -EFAULT)
		return oldval;
	if (oldval != uval)
		return -EAGAIN;

	return 0;
}

I
Ingo Molnar 已提交
642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657
/*
 * Express the locking dependencies for lockdep:
 */
static inline void
double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
{
	if (hb1 <= hb2) {
		spin_lock(&hb1->lock);
		if (hb1 < hb2)
			spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
	} else { /* hb1 > hb2 */
		spin_lock(&hb2->lock);
		spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
	}
}

D
Darren Hart 已提交
658 659 660
static inline void
double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
{
661 662
	spin_unlock(&hb1->lock);
	spin_unlock(&hb2->lock);
D
Darren Hart 已提交
663 664
}

L
Linus Torvalds 已提交
665
/*
D
Darren Hart 已提交
666
 * Wake up waiters matching bitset queued on this futex (uaddr).
L
Linus Torvalds 已提交
667
 */
P
Peter Zijlstra 已提交
668
static int futex_wake(u32 __user *uaddr, int fshared, int nr_wake, u32 bitset)
L
Linus Torvalds 已提交
669
{
670
	struct futex_hash_bucket *hb;
L
Linus Torvalds 已提交
671
	struct futex_q *this, *next;
P
Pierre Peiffer 已提交
672
	struct plist_head *head;
673
	union futex_key key = FUTEX_KEY_INIT;
L
Linus Torvalds 已提交
674 675
	int ret;

676 677 678
	if (!bitset)
		return -EINVAL;

E
Eric Dumazet 已提交
679
	ret = get_futex_key(uaddr, fshared, &key);
L
Linus Torvalds 已提交
680 681 682
	if (unlikely(ret != 0))
		goto out;

683 684 685
	hb = hash_futex(&key);
	spin_lock(&hb->lock);
	head = &hb->chain;
L
Linus Torvalds 已提交
686

P
Pierre Peiffer 已提交
687
	plist_for_each_entry_safe(this, next, head, list) {
L
Linus Torvalds 已提交
688
		if (match_futex (&this->key, &key)) {
689 690 691 692
			if (this->pi_state) {
				ret = -EINVAL;
				break;
			}
693 694 695 696 697

			/* Check if one of the bits is set in both bitsets */
			if (!(this->bitset & bitset))
				continue;

L
Linus Torvalds 已提交
698 699 700 701 702 703
			wake_futex(this);
			if (++ret >= nr_wake)
				break;
		}
	}

704
	spin_unlock(&hb->lock);
705
	put_futex_key(fshared, &key);
706
out:
L
Linus Torvalds 已提交
707 708 709
	return ret;
}

710 711 712 713
/*
 * Wake up all waiters hashed on the physical page that is mapped
 * to this virtual address:
 */
714
static int
P
Peter Zijlstra 已提交
715
futex_wake_op(u32 __user *uaddr1, int fshared, u32 __user *uaddr2,
716
	      int nr_wake, int nr_wake2, int op)
717
{
718
	union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
719
	struct futex_hash_bucket *hb1, *hb2;
P
Pierre Peiffer 已提交
720
	struct plist_head *head;
721
	struct futex_q *this, *next;
D
Darren Hart 已提交
722
	int ret, op_ret;
723

D
Darren Hart 已提交
724
retry:
E
Eric Dumazet 已提交
725
	ret = get_futex_key(uaddr1, fshared, &key1);
726 727
	if (unlikely(ret != 0))
		goto out;
E
Eric Dumazet 已提交
728
	ret = get_futex_key(uaddr2, fshared, &key2);
729
	if (unlikely(ret != 0))
730
		goto out_put_key1;
731

732 733
	hb1 = hash_futex(&key1);
	hb2 = hash_futex(&key2);
734

I
Ingo Molnar 已提交
735
	double_lock_hb(hb1, hb2);
D
Darren Hart 已提交
736
retry_private:
737
	op_ret = futex_atomic_op_inuser(op, uaddr2);
738
	if (unlikely(op_ret < 0)) {
739
		u32 dummy;
740

D
Darren Hart 已提交
741
		double_unlock_hb(hb1, hb2);
742

743
#ifndef CONFIG_MMU
744 745 746 747
		/*
		 * we don't get EFAULT from MMU faults if we don't have an MMU,
		 * but we might get them from range checking
		 */
748
		ret = op_ret;
749
		goto out_put_keys;
750 751
#endif

752 753
		if (unlikely(op_ret != -EFAULT)) {
			ret = op_ret;
754
			goto out_put_keys;
755 756
		}

757
		ret = get_user(dummy, uaddr2);
758
		if (ret)
759
			goto out_put_keys;
760

D
Darren Hart 已提交
761 762 763
		if (!fshared)
			goto retry_private;

764 765
		put_futex_key(fshared, &key2);
		put_futex_key(fshared, &key1);
D
Darren Hart 已提交
766
		goto retry;
767 768
	}

769
	head = &hb1->chain;
770

P
Pierre Peiffer 已提交
771
	plist_for_each_entry_safe(this, next, head, list) {
772 773 774 775 776 777 778 779
		if (match_futex (&this->key, &key1)) {
			wake_futex(this);
			if (++ret >= nr_wake)
				break;
		}
	}

	if (op_ret > 0) {
780
		head = &hb2->chain;
781 782

		op_ret = 0;
P
Pierre Peiffer 已提交
783
		plist_for_each_entry_safe(this, next, head, list) {
784 785 786 787 788 789 790 791 792
			if (match_futex (&this->key, &key2)) {
				wake_futex(this);
				if (++op_ret >= nr_wake2)
					break;
			}
		}
		ret += op_ret;
	}

D
Darren Hart 已提交
793
	double_unlock_hb(hb1, hb2);
794
out_put_keys:
795
	put_futex_key(fshared, &key2);
796
out_put_key1:
797
	put_futex_key(fshared, &key1);
798
out:
799 800 801
	return ret;
}

L
Linus Torvalds 已提交
802 803 804 805
/*
 * Requeue all waiters hashed on one physical page to another
 * physical page.
 */
P
Peter Zijlstra 已提交
806
static int futex_requeue(u32 __user *uaddr1, int fshared, u32 __user *uaddr2,
807
			 int nr_wake, int nr_requeue, u32 *cmpval)
L
Linus Torvalds 已提交
808
{
809
	union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
810
	struct futex_hash_bucket *hb1, *hb2;
P
Pierre Peiffer 已提交
811
	struct plist_head *head1;
L
Linus Torvalds 已提交
812 813 814
	struct futex_q *this, *next;
	int ret, drop_count = 0;

815
retry:
E
Eric Dumazet 已提交
816
	ret = get_futex_key(uaddr1, fshared, &key1);
L
Linus Torvalds 已提交
817 818
	if (unlikely(ret != 0))
		goto out;
E
Eric Dumazet 已提交
819
	ret = get_futex_key(uaddr2, fshared, &key2);
L
Linus Torvalds 已提交
820
	if (unlikely(ret != 0))
821
		goto out_put_key1;
L
Linus Torvalds 已提交
822

823 824
	hb1 = hash_futex(&key1);
	hb2 = hash_futex(&key2);
L
Linus Torvalds 已提交
825

D
Darren Hart 已提交
826
retry_private:
I
Ingo Molnar 已提交
827
	double_lock_hb(hb1, hb2);
L
Linus Torvalds 已提交
828

829 830
	if (likely(cmpval != NULL)) {
		u32 curval;
L
Linus Torvalds 已提交
831

832
		ret = get_futex_value_locked(&curval, uaddr1);
L
Linus Torvalds 已提交
833 834

		if (unlikely(ret)) {
D
Darren Hart 已提交
835
			double_unlock_hb(hb1, hb2);
L
Linus Torvalds 已提交
836

837
			ret = get_user(curval, uaddr1);
D
Darren Hart 已提交
838 839
			if (ret)
				goto out_put_keys;
L
Linus Torvalds 已提交
840

D
Darren Hart 已提交
841 842
			if (!fshared)
				goto retry_private;
L
Linus Torvalds 已提交
843

D
Darren Hart 已提交
844 845 846
			put_futex_key(fshared, &key2);
			put_futex_key(fshared, &key1);
			goto retry;
L
Linus Torvalds 已提交
847
		}
848
		if (curval != *cmpval) {
L
Linus Torvalds 已提交
849 850 851 852 853
			ret = -EAGAIN;
			goto out_unlock;
		}
	}

854
	head1 = &hb1->chain;
P
Pierre Peiffer 已提交
855
	plist_for_each_entry_safe(this, next, head1, list) {
L
Linus Torvalds 已提交
856 857 858 859 860
		if (!match_futex (&this->key, &key1))
			continue;
		if (++ret <= nr_wake) {
			wake_futex(this);
		} else {
861 862 863 864 865
			/*
			 * If key1 and key2 hash to the same bucket, no need to
			 * requeue.
			 */
			if (likely(head1 != &hb2->chain)) {
P
Pierre Peiffer 已提交
866 867
				plist_del(&this->list, &hb1->chain);
				plist_add(&this->list, &hb2->chain);
868
				this->lock_ptr = &hb2->lock;
P
Pierre Peiffer 已提交
869 870 871
#ifdef CONFIG_DEBUG_PI_LIST
				this->list.plist.lock = &hb2->lock;
#endif
872
			}
L
Linus Torvalds 已提交
873
			this->key = key2;
874
			get_futex_key_refs(&key2);
L
Linus Torvalds 已提交
875 876 877 878 879 880 881 882
			drop_count++;

			if (ret - nr_wake >= nr_requeue)
				break;
		}
	}

out_unlock:
D
Darren Hart 已提交
883
	double_unlock_hb(hb1, hb2);
L
Linus Torvalds 已提交
884

885
	/* drop_futex_key_refs() must be called outside the spinlocks. */
L
Linus Torvalds 已提交
886
	while (--drop_count >= 0)
887
		drop_futex_key_refs(&key1);
L
Linus Torvalds 已提交
888

889
out_put_keys:
890
	put_futex_key(fshared, &key2);
891
out_put_key1:
892
	put_futex_key(fshared, &key1);
893
out:
L
Linus Torvalds 已提交
894 895 896 897
	return ret;
}

/* The key must be already stored in q->key. */
E
Eric Sesterhenn 已提交
898
static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
L
Linus Torvalds 已提交
899
{
900
	struct futex_hash_bucket *hb;
L
Linus Torvalds 已提交
901

902
	init_waitqueue_head(&q->waiter);
L
Linus Torvalds 已提交
903

904
	get_futex_key_refs(&q->key);
905 906
	hb = hash_futex(&q->key);
	q->lock_ptr = &hb->lock;
L
Linus Torvalds 已提交
907

908 909
	spin_lock(&hb->lock);
	return hb;
L
Linus Torvalds 已提交
910 911
}

E
Eric Sesterhenn 已提交
912
static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
L
Linus Torvalds 已提交
913
{
P
Pierre Peiffer 已提交
914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930
	int prio;

	/*
	 * The priority used to register this element is
	 * - either the real thread-priority for the real-time threads
	 * (i.e. threads with a priority lower than MAX_RT_PRIO)
	 * - or MAX_RT_PRIO for non-RT threads.
	 * Thus, all RT-threads are woken first in priority order, and
	 * the others are woken last, in FIFO order.
	 */
	prio = min(current->normal_prio, MAX_RT_PRIO);

	plist_node_init(&q->list, prio);
#ifdef CONFIG_DEBUG_PI_LIST
	q->list.plist.lock = &hb->lock;
#endif
	plist_add(&q->list, &hb->chain);
931
	q->task = current;
932
	spin_unlock(&hb->lock);
L
Linus Torvalds 已提交
933 934 935
}

static inline void
936
queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
L
Linus Torvalds 已提交
937
{
938
	spin_unlock(&hb->lock);
939
	drop_futex_key_refs(&q->key);
L
Linus Torvalds 已提交
940 941 942 943 944 945 946 947 948 949 950
}

/*
 * queue_me and unqueue_me must be called as a pair, each
 * exactly once.  They are called with the hashed spinlock held.
 */

/* Return 1 if we were still queued (ie. 0 means we were woken) */
static int unqueue_me(struct futex_q *q)
{
	spinlock_t *lock_ptr;
951
	int ret = 0;
L
Linus Torvalds 已提交
952 953

	/* In the common case we don't take the spinlock, which is nice. */
954
retry:
L
Linus Torvalds 已提交
955
	lock_ptr = q->lock_ptr;
956
	barrier();
957
	if (lock_ptr != NULL) {
L
Linus Torvalds 已提交
958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975
		spin_lock(lock_ptr);
		/*
		 * q->lock_ptr can change between reading it and
		 * spin_lock(), causing us to take the wrong lock.  This
		 * corrects the race condition.
		 *
		 * Reasoning goes like this: if we have the wrong lock,
		 * q->lock_ptr must have changed (maybe several times)
		 * between reading it and the spin_lock().  It can
		 * change again after the spin_lock() but only if it was
		 * already changed before the spin_lock().  It cannot,
		 * however, change back to the original value.  Therefore
		 * we can detect whether we acquired the correct lock.
		 */
		if (unlikely(lock_ptr != q->lock_ptr)) {
			spin_unlock(lock_ptr);
			goto retry;
		}
P
Pierre Peiffer 已提交
976 977
		WARN_ON(plist_node_empty(&q->list));
		plist_del(&q->list, &q->list.plist);
978 979 980

		BUG_ON(q->pi_state);

L
Linus Torvalds 已提交
981 982 983 984
		spin_unlock(lock_ptr);
		ret = 1;
	}

985
	drop_futex_key_refs(&q->key);
L
Linus Torvalds 已提交
986 987 988
	return ret;
}

989 990
/*
 * PI futexes can not be requeued and must remove themself from the
P
Pierre Peiffer 已提交
991 992
 * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
 * and dropped here.
993
 */
P
Pierre Peiffer 已提交
994
static void unqueue_me_pi(struct futex_q *q)
995
{
P
Pierre Peiffer 已提交
996 997
	WARN_ON(plist_node_empty(&q->list));
	plist_del(&q->list, &q->list.plist);
998 999 1000 1001 1002

	BUG_ON(!q->pi_state);
	free_pi_state(q->pi_state);
	q->pi_state = NULL;

P
Pierre Peiffer 已提交
1003
	spin_unlock(q->lock_ptr);
1004

1005
	drop_futex_key_refs(&q->key);
1006 1007
}

P
Pierre Peiffer 已提交
1008
/*
1009
 * Fixup the pi_state owner with the new owner.
P
Pierre Peiffer 已提交
1010
 *
1011 1012
 * Must be called with hash bucket lock held and mm->sem held for non
 * private futexes.
P
Pierre Peiffer 已提交
1013
 */
1014
static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
P
Peter Zijlstra 已提交
1015
				struct task_struct *newowner, int fshared)
P
Pierre Peiffer 已提交
1016
{
1017
	u32 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
P
Pierre Peiffer 已提交
1018
	struct futex_pi_state *pi_state = q->pi_state;
1019
	struct task_struct *oldowner = pi_state->owner;
P
Pierre Peiffer 已提交
1020
	u32 uval, curval, newval;
D
Darren Hart 已提交
1021
	int ret;
P
Pierre Peiffer 已提交
1022 1023

	/* Owner died? */
1024 1025 1026 1027 1028 1029 1030 1031 1032 1033
	if (!pi_state->owner)
		newtid |= FUTEX_OWNER_DIED;

	/*
	 * We are here either because we stole the rtmutex from the
	 * pending owner or we are the pending owner which failed to
	 * get the rtmutex. We have to replace the pending owner TID
	 * in the user space variable. This must be atomic as we have
	 * to preserve the owner died bit here.
	 *
D
Darren Hart 已提交
1034 1035 1036
	 * Note: We write the user space value _before_ changing the pi_state
	 * because we can fault here. Imagine swapped out pages or a fork
	 * that marked all the anonymous memory readonly for cow.
1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063
	 *
	 * Modifying pi_state _before_ the user space value would
	 * leave the pi_state in an inconsistent state when we fault
	 * here, because we need to drop the hash bucket lock to
	 * handle the fault. This might be observed in the PID check
	 * in lookup_pi_state.
	 */
retry:
	if (get_futex_value_locked(&uval, uaddr))
		goto handle_fault;

	while (1) {
		newval = (uval & FUTEX_OWNER_DIED) | newtid;

		curval = cmpxchg_futex_value_locked(uaddr, uval, newval);

		if (curval == -EFAULT)
			goto handle_fault;
		if (curval == uval)
			break;
		uval = curval;
	}

	/*
	 * We fixed up user space. Now we need to fix the pi_state
	 * itself.
	 */
P
Pierre Peiffer 已提交
1064 1065 1066 1067 1068
	if (pi_state->owner != NULL) {
		spin_lock_irq(&pi_state->owner->pi_lock);
		WARN_ON(list_empty(&pi_state->list));
		list_del_init(&pi_state->list);
		spin_unlock_irq(&pi_state->owner->pi_lock);
1069
	}
P
Pierre Peiffer 已提交
1070

1071
	pi_state->owner = newowner;
P
Pierre Peiffer 已提交
1072

1073
	spin_lock_irq(&newowner->pi_lock);
P
Pierre Peiffer 已提交
1074
	WARN_ON(!list_empty(&pi_state->list));
1075 1076
	list_add(&pi_state->list, &newowner->pi_state_list);
	spin_unlock_irq(&newowner->pi_lock);
1077
	return 0;
P
Pierre Peiffer 已提交
1078 1079

	/*
1080 1081 1082 1083 1084 1085 1086 1087
	 * To handle the page fault we need to drop the hash bucket
	 * lock here. That gives the other task (either the pending
	 * owner itself or the task which stole the rtmutex) the
	 * chance to try the fixup of the pi_state. So once we are
	 * back from handling the fault we need to check the pi_state
	 * after reacquiring the hash bucket lock and before trying to
	 * do another fixup. When the fixup has been done already we
	 * simply return.
P
Pierre Peiffer 已提交
1088
	 */
1089 1090
handle_fault:
	spin_unlock(q->lock_ptr);
1091

D
Darren Hart 已提交
1092
	ret = get_user(uval, uaddr);
1093

1094
	spin_lock(q->lock_ptr);
1095

1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
	/*
	 * Check if someone else fixed it for us:
	 */
	if (pi_state->owner != oldowner)
		return 0;

	if (ret)
		return ret;

	goto retry;
P
Pierre Peiffer 已提交
1106 1107
}

E
Eric Dumazet 已提交
1108 1109
/*
 * In case we must use restart_block to restart a futex_wait,
1110
 * we encode in the 'flags' shared capability
E
Eric Dumazet 已提交
1111
 */
1112 1113
#define FLAGS_SHARED		0x01
#define FLAGS_CLOCKRT		0x02
E
Eric Dumazet 已提交
1114

N
Nick Piggin 已提交
1115
static long futex_wait_restart(struct restart_block *restart);
T
Thomas Gleixner 已提交
1116

P
Peter Zijlstra 已提交
1117
static int futex_wait(u32 __user *uaddr, int fshared,
1118
		      u32 val, ktime_t *abs_time, u32 bitset, int clockrt)
L
Linus Torvalds 已提交
1119
{
1120
	struct task_struct *curr = current;
P
Peter Zijlstra 已提交
1121
	struct restart_block *restart;
1122
	DECLARE_WAITQUEUE(wait, curr);
1123
	struct futex_hash_bucket *hb;
L
Linus Torvalds 已提交
1124
	struct futex_q q;
1125 1126
	u32 uval;
	int ret;
1127
	struct hrtimer_sleeper t;
1128
	int rem = 0;
L
Linus Torvalds 已提交
1129

1130 1131 1132
	if (!bitset)
		return -EINVAL;

1133
	q.pi_state = NULL;
1134
	q.bitset = bitset;
1135
retry:
1136
	q.key = FUTEX_KEY_INIT;
E
Eric Dumazet 已提交
1137
	ret = get_futex_key(uaddr, fshared, &q.key);
L
Linus Torvalds 已提交
1138
	if (unlikely(ret != 0))
1139
		goto out;
L
Linus Torvalds 已提交
1140

D
Darren Hart 已提交
1141
retry_private:
E
Eric Sesterhenn 已提交
1142
	hb = queue_lock(&q);
L
Linus Torvalds 已提交
1143 1144

	/*
D
Darren Hart 已提交
1145
	 * Access the page AFTER the hash-bucket is locked.
L
Linus Torvalds 已提交
1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160
	 * Order is important:
	 *
	 *   Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
	 *   Userspace waker:  if (cond(var)) { var = new; futex_wake(&var); }
	 *
	 * The basic logical guarantee of a futex is that it blocks ONLY
	 * if cond(var) is known to be true at the time of blocking, for
	 * any cond.  If we queued after testing *uaddr, that would open
	 * a race condition where we could block indefinitely with
	 * cond(var) false, which would violate the guarantee.
	 *
	 * A consequence is that futex_wait() can return zero and absorb
	 * a wakeup when *uaddr != val on entry to the syscall.  This is
	 * rare, but normal.
	 *
D
Darren Hart 已提交
1161
	 * For shared futexes, we hold the mmap semaphore, so the mapping
E
Eric Dumazet 已提交
1162
	 * cannot have changed since we looked it up in get_futex_key.
L
Linus Torvalds 已提交
1163
	 */
1164
	ret = get_futex_value_locked(&uval, uaddr);
L
Linus Torvalds 已提交
1165 1166

	if (unlikely(ret)) {
1167
		queue_unlock(&q, hb);
L
Linus Torvalds 已提交
1168

1169
		ret = get_user(uval, uaddr);
D
Darren Hart 已提交
1170 1171
		if (ret)
			goto out_put_key;
L
Linus Torvalds 已提交
1172

D
Darren Hart 已提交
1173 1174 1175 1176 1177
		if (!fshared)
			goto retry_private;

		put_futex_key(fshared, &q.key);
		goto retry;
L
Linus Torvalds 已提交
1178
	}
1179
	ret = -EWOULDBLOCK;
P
Peter Zijlstra 已提交
1180 1181 1182 1183
	if (unlikely(uval != val)) {
		queue_unlock(&q, hb);
		goto out_put_key;
	}
L
Linus Torvalds 已提交
1184 1185

	/* Only actually queue if *uaddr contained val.  */
E
Eric Sesterhenn 已提交
1186
	queue_me(&q, hb);
L
Linus Torvalds 已提交
1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198

	/*
	 * There might have been scheduling since the queue_me(), as we
	 * cannot hold a spinlock across the get_user() in case it
	 * faults, and we cannot just set TASK_INTERRUPTIBLE state when
	 * queueing ourselves into the futex hash.  This code thus has to
	 * rely on the futex_wake() code removing us from hash when it
	 * wakes us up.
	 */

	/* add_wait_queue is the barrier after __set_current_state. */
	__set_current_state(TASK_INTERRUPTIBLE);
1199
	add_wait_queue(&q.waiter, &wait);
L
Linus Torvalds 已提交
1200
	/*
P
Pierre Peiffer 已提交
1201
	 * !plist_node_empty() is safe here without any lock.
L
Linus Torvalds 已提交
1202 1203
	 * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
	 */
P
Pierre Peiffer 已提交
1204
	if (likely(!plist_node_empty(&q.list))) {
1205 1206 1207
		if (!abs_time)
			schedule();
		else {
1208 1209 1210 1211
			hrtimer_init_on_stack(&t.timer,
					      clockrt ? CLOCK_REALTIME :
					      CLOCK_MONOTONIC,
					      HRTIMER_MODE_ABS);
1212
			hrtimer_init_sleeper(&t, current);
1213 1214
			hrtimer_set_expires_range_ns(&t.timer, *abs_time,
						     current->timer_slack_ns);
1215

1216
			hrtimer_start_expires(&t.timer, HRTIMER_MODE_ABS);
1217 1218
			if (!hrtimer_active(&t.timer))
				t.task = NULL;
1219 1220 1221 1222 1223 1224 1225 1226 1227 1228

			/*
			 * the timer could have already expired, in which
			 * case current would be flagged for rescheduling.
			 * Don't bother calling schedule.
			 */
			if (likely(t.task))
				schedule();

			hrtimer_cancel(&t.timer);
N
Nick Piggin 已提交
1229

1230 1231
			/* Flag if a timeout occured */
			rem = (t.task == NULL);
1232 1233

			destroy_hrtimer_on_stack(&t.timer);
1234
		}
N
Nick Piggin 已提交
1235
	}
L
Linus Torvalds 已提交
1236 1237 1238 1239 1240 1241 1242 1243
	__set_current_state(TASK_RUNNING);

	/*
	 * NOTE: we don't remove ourselves from the waitqueue because
	 * we are the only user of it.
	 */

	/* If we were woken (and unqueued), we succeeded, whatever. */
P
Peter Zijlstra 已提交
1244
	ret = 0;
L
Linus Torvalds 已提交
1245
	if (!unqueue_me(&q))
P
Peter Zijlstra 已提交
1246 1247
		goto out_put_key;
	ret = -ETIMEDOUT;
1248
	if (rem)
P
Peter Zijlstra 已提交
1249
		goto out_put_key;
N
Nick Piggin 已提交
1250

1251 1252 1253 1254
	/*
	 * We expect signal_pending(current), but another thread may
	 * have handled it for us already.
	 */
P
Peter Zijlstra 已提交
1255
	ret = -ERESTARTSYS;
1256
	if (!abs_time)
P
Peter Zijlstra 已提交
1257
		goto out_put_key;
L
Linus Torvalds 已提交
1258

P
Peter Zijlstra 已提交
1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270
	restart = &current_thread_info()->restart_block;
	restart->fn = futex_wait_restart;
	restart->futex.uaddr = (u32 *)uaddr;
	restart->futex.val = val;
	restart->futex.time = abs_time->tv64;
	restart->futex.bitset = bitset;
	restart->futex.flags = 0;

	if (fshared)
		restart->futex.flags |= FLAGS_SHARED;
	if (clockrt)
		restart->futex.flags |= FLAGS_CLOCKRT;
1271

P
Peter Zijlstra 已提交
1272 1273 1274 1275
	ret = -ERESTART_RESTARTBLOCK;

out_put_key:
	put_futex_key(fshared, &q.key);
1276
out:
1277 1278 1279
	return ret;
}

N
Nick Piggin 已提交
1280 1281 1282

static long futex_wait_restart(struct restart_block *restart)
{
1283
	u32 __user *uaddr = (u32 __user *)restart->futex.uaddr;
P
Peter Zijlstra 已提交
1284
	int fshared = 0;
1285
	ktime_t t;
N
Nick Piggin 已提交
1286

1287
	t.tv64 = restart->futex.time;
N
Nick Piggin 已提交
1288
	restart->fn = do_no_restart_syscall;
1289
	if (restart->futex.flags & FLAGS_SHARED)
P
Peter Zijlstra 已提交
1290
		fshared = 1;
1291
	return (long)futex_wait(uaddr, fshared, restart->futex.val, &t,
1292 1293
				restart->futex.bitset,
				restart->futex.flags & FLAGS_CLOCKRT);
N
Nick Piggin 已提交
1294 1295 1296
}


1297 1298 1299 1300 1301 1302
/*
 * Userspace tried a 0 -> TID atomic transition of the futex value
 * and failed. The kernel side here does the whole locking operation:
 * if there are waiters then it will block, it does PI, etc. (Due to
 * races the kernel might see a 0 value of the futex too.)
 */
P
Peter Zijlstra 已提交
1303
static int futex_lock_pi(u32 __user *uaddr, int fshared,
E
Eric Dumazet 已提交
1304
			 int detect, ktime_t *time, int trylock)
1305
{
1306
	struct hrtimer_sleeper timeout, *to = NULL;
1307 1308 1309 1310
	struct task_struct *curr = current;
	struct futex_hash_bucket *hb;
	u32 uval, newval, curval;
	struct futex_q q;
D
Darren Hart 已提交
1311
	int ret, lock_taken, ownerdied = 0;
1312 1313 1314 1315

	if (refill_pi_state_cache())
		return -ENOMEM;

1316
	if (time) {
1317
		to = &timeout;
1318 1319
		hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
				      HRTIMER_MODE_ABS);
1320
		hrtimer_init_sleeper(to, current);
1321
		hrtimer_set_expires(&to->timer, *time);
1322 1323
	}

1324
	q.pi_state = NULL;
1325
retry:
1326
	q.key = FUTEX_KEY_INIT;
E
Eric Dumazet 已提交
1327
	ret = get_futex_key(uaddr, fshared, &q.key);
1328
	if (unlikely(ret != 0))
1329
		goto out;
1330

D
Darren Hart 已提交
1331
retry_private:
E
Eric Sesterhenn 已提交
1332
	hb = queue_lock(&q);
1333

1334
retry_locked:
1335
	ret = lock_taken = 0;
P
Pierre Peiffer 已提交
1336

1337 1338 1339 1340 1341
	/*
	 * To avoid races, we attempt to take the lock here again
	 * (by doing a 0 -> TID atomic cmpxchg), while holding all
	 * the locks. It will most likely not succeed.
	 */
1342
	newval = task_pid_vnr(current);
1343

T
Thomas Gleixner 已提交
1344
	curval = cmpxchg_futex_value_locked(uaddr, 0, newval);
1345 1346 1347 1348

	if (unlikely(curval == -EFAULT))
		goto uaddr_faulted;

1349 1350 1351 1352
	/*
	 * Detect deadlocks. In case of REQUEUE_PI this is a valid
	 * situation and we return success to user space.
	 */
1353
	if (unlikely((curval & FUTEX_TID_MASK) == task_pid_vnr(current))) {
1354
		ret = -EDEADLK;
1355
		goto out_unlock_put_key;
1356 1357 1358
	}

	/*
1359
	 * Surprise - we got the lock. Just return to userspace:
1360 1361
	 */
	if (unlikely(!curval))
1362
		goto out_unlock_put_key;
1363 1364

	uval = curval;
1365

P
Pierre Peiffer 已提交
1366
	/*
1367 1368
	 * Set the WAITERS flag, so the owner will know it has someone
	 * to wake at next unlock
P
Pierre Peiffer 已提交
1369
	 */
1370 1371 1372 1373
	newval = curval | FUTEX_WAITERS;

	/*
	 * There are two cases, where a futex might have no owner (the
1374 1375 1376
	 * owner TID is 0): OWNER_DIED. We take over the futex in this
	 * case. We also do an unconditional take over, when the owner
	 * of the futex died.
1377 1378 1379 1380
	 *
	 * This is safe as we are protected by the hash bucket lock !
	 */
	if (unlikely(ownerdied || !(curval & FUTEX_TID_MASK))) {
1381
		/* Keep the OWNER_DIED bit */
1382
		newval = (curval & ~FUTEX_TID_MASK) | task_pid_vnr(current);
1383 1384 1385
		ownerdied = 0;
		lock_taken = 1;
	}
1386

T
Thomas Gleixner 已提交
1387
	curval = cmpxchg_futex_value_locked(uaddr, uval, newval);
1388 1389 1390 1391 1392 1393

	if (unlikely(curval == -EFAULT))
		goto uaddr_faulted;
	if (unlikely(curval != uval))
		goto retry_locked;

1394
	/*
1395
	 * We took the lock due to owner died take over.
1396
	 */
1397
	if (unlikely(lock_taken))
1398
		goto out_unlock_put_key;
P
Pierre Peiffer 已提交
1399

1400 1401 1402 1403
	/*
	 * We dont have the lock. Look up the PI state (or create it if
	 * we are the first waiter):
	 */
P
Pierre Peiffer 已提交
1404
	ret = lookup_pi_state(uval, hb, &q.key, &q.pi_state);
1405 1406

	if (unlikely(ret)) {
1407
		switch (ret) {
1408

1409 1410 1411 1412 1413 1414
		case -EAGAIN:
			/*
			 * Task is exiting and we just wait for the
			 * exit to complete.
			 */
			queue_unlock(&q, hb);
1415
			put_futex_key(fshared, &q.key);
1416 1417
			cond_resched();
			goto retry;
1418

1419 1420 1421 1422 1423 1424 1425
		case -ESRCH:
			/*
			 * No owner found for this futex. Check if the
			 * OWNER_DIED bit is set to figure out whether
			 * this is a robust futex or not.
			 */
			if (get_futex_value_locked(&curval, uaddr))
1426
				goto uaddr_faulted;
1427 1428 1429 1430 1431 1432 1433 1434

			/*
			 * We simply start over in case of a robust
			 * futex. The code above will take the futex
			 * and return happy.
			 */
			if (curval & FUTEX_OWNER_DIED) {
				ownerdied = 1;
1435
				goto retry_locked;
1436 1437
			}
		default:
1438
			goto out_unlock_put_key;
1439 1440 1441 1442 1443 1444
		}
	}

	/*
	 * Only actually queue now that the atomic ops are done:
	 */
E
Eric Sesterhenn 已提交
1445
	queue_me(&q, hb);
1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458

	WARN_ON(!q.pi_state);
	/*
	 * Block on the PI mutex:
	 */
	if (!trylock)
		ret = rt_mutex_timed_lock(&q.pi_state->pi_mutex, to, 1);
	else {
		ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
		/* Fixup the trylock return value: */
		ret = ret ? 0 : -EWOULDBLOCK;
	}

1459
	spin_lock(q.lock_ptr);
1460

1461 1462 1463 1464 1465 1466 1467
	if (!ret) {
		/*
		 * Got the lock. We might not be the anticipated owner
		 * if we did a lock-steal - fix up the PI-state in
		 * that case:
		 */
		if (q.pi_state->owner != curr)
1468
			ret = fixup_pi_state_owner(uaddr, &q, curr, fshared);
1469
	} else {
1470 1471
		/*
		 * Catch the rare case, where the lock was released
1472 1473
		 * when we were on the way back before we locked the
		 * hash bucket.
1474
		 */
1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499
		if (q.pi_state->owner == curr) {
			/*
			 * Try to get the rt_mutex now. This might
			 * fail as some other task acquired the
			 * rt_mutex after we removed ourself from the
			 * rt_mutex waiters list.
			 */
			if (rt_mutex_trylock(&q.pi_state->pi_mutex))
				ret = 0;
			else {
				/*
				 * pi_state is incorrect, some other
				 * task did a lock steal and we
				 * returned due to timeout or signal
				 * without taking the rt_mutex. Too
				 * late. We can access the
				 * rt_mutex_owner without locking, as
				 * the other task is now blocked on
				 * the hash bucket lock. Fix the state
				 * up.
				 */
				struct task_struct *owner;
				int res;

				owner = rt_mutex_owner(&q.pi_state->pi_mutex);
1500 1501
				res = fixup_pi_state_owner(uaddr, &q, owner,
							   fshared);
1502 1503 1504 1505 1506

				/* propagate -EFAULT, if the fixup failed */
				if (res)
					ret = res;
			}
1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518
		} else {
			/*
			 * Paranoia check. If we did not take the lock
			 * in the trylock above, then we should not be
			 * the owner of the rtmutex, neither the real
			 * nor the pending one:
			 */
			if (rt_mutex_owner(&q.pi_state->pi_mutex) == curr)
				printk(KERN_ERR "futex_lock_pi: ret = %d "
				       "pi-mutex: %p pi-state %p\n", ret,
				       q.pi_state->pi_mutex.owner,
				       q.pi_state->owner);
1519 1520 1521
		}
	}

1522 1523 1524 1525 1526 1527 1528
	/*
	 * If fixup_pi_state_owner() faulted and was unable to handle the
	 * fault, unlock it and return the fault to userspace.
	 */
	if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current))
		rt_mutex_unlock(&q.pi_state->pi_mutex);

1529 1530
	/* Unqueue and drop the lock */
	unqueue_me_pi(&q);
1531

1532 1533
	if (to)
		destroy_hrtimer_on_stack(&to->timer);
1534
	return ret != -EINTR ? ret : -ERESTARTNOINTR;
1535

1536
out_unlock_put_key:
1537 1538
	queue_unlock(&q, hb);

1539
out_put_key:
1540
	put_futex_key(fshared, &q.key);
1541
out:
1542 1543
	if (to)
		destroy_hrtimer_on_stack(&to->timer);
1544 1545
	return ret;

1546
uaddr_faulted:
1547
	/*
1548 1549 1550 1551 1552
	 * We have to r/w  *(int __user *)uaddr, and we have to modify it
	 * atomically.  Therefore, if we continue to fault after get_user()
	 * below, we need to handle the fault ourselves, while still holding
	 * the mmap_sem.  This can occur if the uaddr is under contention as
	 * we have to drop the mmap_sem in order to call get_user().
1553
	 */
1554 1555
	queue_unlock(&q, hb);

1556
	ret = get_user(uval, uaddr);
D
Darren Hart 已提交
1557 1558
	if (ret)
		goto out_put_key;
1559

D
Darren Hart 已提交
1560 1561 1562 1563 1564
	if (!fshared)
		goto retry_private;

	put_futex_key(fshared, &q.key);
	goto retry;
1565 1566
}

1567

1568 1569 1570 1571 1572
/*
 * Userspace attempted a TID -> 0 atomic transition, and failed.
 * This is the in-kernel slowpath: we look up the PI state (if any),
 * and do the rt-mutex unlock.
 */
P
Peter Zijlstra 已提交
1573
static int futex_unlock_pi(u32 __user *uaddr, int fshared)
1574 1575 1576 1577
{
	struct futex_hash_bucket *hb;
	struct futex_q *this, *next;
	u32 uval;
P
Pierre Peiffer 已提交
1578
	struct plist_head *head;
1579
	union futex_key key = FUTEX_KEY_INIT;
D
Darren Hart 已提交
1580
	int ret;
1581 1582 1583 1584 1585 1586 1587

retry:
	if (get_user(uval, uaddr))
		return -EFAULT;
	/*
	 * We release only a lock we actually own:
	 */
1588
	if ((uval & FUTEX_TID_MASK) != task_pid_vnr(current))
1589 1590
		return -EPERM;

E
Eric Dumazet 已提交
1591
	ret = get_futex_key(uaddr, fshared, &key);
1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602
	if (unlikely(ret != 0))
		goto out;

	hb = hash_futex(&key);
	spin_lock(&hb->lock);

	/*
	 * To avoid races, try to do the TID -> 0 atomic transition
	 * again. If it succeeds then we can return without waking
	 * anyone else up:
	 */
T
Thomas Gleixner 已提交
1603
	if (!(uval & FUTEX_OWNER_DIED))
1604
		uval = cmpxchg_futex_value_locked(uaddr, task_pid_vnr(current), 0);
T
Thomas Gleixner 已提交
1605

1606 1607 1608 1609 1610 1611 1612

	if (unlikely(uval == -EFAULT))
		goto pi_faulted;
	/*
	 * Rare case: we managed to release the lock atomically,
	 * no need to wake anyone else up:
	 */
1613
	if (unlikely(uval == task_pid_vnr(current)))
1614 1615 1616 1617 1618 1619 1620 1621
		goto out_unlock;

	/*
	 * Ok, other tasks may need to be woken up - check waiters
	 * and do the wakeup if necessary:
	 */
	head = &hb->chain;

P
Pierre Peiffer 已提交
1622
	plist_for_each_entry_safe(this, next, head, list) {
1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637
		if (!match_futex (&this->key, &key))
			continue;
		ret = wake_futex_pi(uaddr, uval, this);
		/*
		 * The atomic access to the futex value
		 * generated a pagefault, so retry the
		 * user-access and the wakeup:
		 */
		if (ret == -EFAULT)
			goto pi_faulted;
		goto out_unlock;
	}
	/*
	 * No waiters - kernel unlocks the futex:
	 */
1638 1639 1640 1641 1642
	if (!(uval & FUTEX_OWNER_DIED)) {
		ret = unlock_futex_pi(uaddr, uval);
		if (ret == -EFAULT)
			goto pi_faulted;
	}
1643 1644 1645

out_unlock:
	spin_unlock(&hb->lock);
1646
	put_futex_key(fshared, &key);
1647

1648
out:
1649 1650 1651 1652
	return ret;

pi_faulted:
	/*
1653 1654 1655 1656 1657
	 * We have to r/w  *(int __user *)uaddr, and we have to modify it
	 * atomically.  Therefore, if we continue to fault after get_user()
	 * below, we need to handle the fault ourselves, while still holding
	 * the mmap_sem.  This can occur if the uaddr is under contention as
	 * we have to drop the mmap_sem in order to call get_user().
1658
	 */
1659
	spin_unlock(&hb->lock);
D
Darren Hart 已提交
1660
	put_futex_key(fshared, &key);
1661 1662

	ret = get_user(uval, uaddr);
1663
	if (!ret)
1664 1665
		goto retry;

L
Linus Torvalds 已提交
1666 1667 1668
	return ret;
}

1669 1670 1671 1672 1673 1674 1675
/*
 * Support for robust futexes: the kernel cleans up held futexes at
 * thread exit time.
 *
 * Implementation: user-space maintains a per-thread list of locks it
 * is holding. Upon do_exit(), the kernel carefully walks this list,
 * and marks all locks that are owned by this thread with the
1676
 * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688
 * always manipulated with the lock held, so the list is private and
 * per-thread. Userspace also maintains a per-thread 'list_op_pending'
 * field, to allow the kernel to clean up if the thread dies after
 * acquiring the lock, but just before it could have added itself to
 * the list. There can only be one such pending lock.
 */

/**
 * sys_set_robust_list - set the robust-futex list head of a task
 * @head: pointer to the list-head
 * @len: length of the list-head, as userspace expects
 */
1689 1690
SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head,
		size_t, len)
1691
{
1692 1693
	if (!futex_cmpxchg_enabled)
		return -ENOSYS;
1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710
	/*
	 * The kernel knows only one size for now:
	 */
	if (unlikely(len != sizeof(*head)))
		return -EINVAL;

	current->robust_list = head;

	return 0;
}

/**
 * sys_get_robust_list - get the robust-futex list head of a task
 * @pid: pid of the process [zero for current task]
 * @head_ptr: pointer to a list-head pointer, the kernel fills it in
 * @len_ptr: pointer to a length field, the kernel fills in the header size
 */
1711 1712 1713
SYSCALL_DEFINE3(get_robust_list, int, pid,
		struct robust_list_head __user * __user *, head_ptr,
		size_t __user *, len_ptr)
1714
{
A
Al Viro 已提交
1715
	struct robust_list_head __user *head;
1716
	unsigned long ret;
1717
	const struct cred *cred = current_cred(), *pcred;
1718

1719 1720 1721
	if (!futex_cmpxchg_enabled)
		return -ENOSYS;

1722 1723 1724 1725 1726 1727
	if (!pid)
		head = current->robust_list;
	else {
		struct task_struct *p;

		ret = -ESRCH;
1728
		rcu_read_lock();
1729
		p = find_task_by_vpid(pid);
1730 1731 1732
		if (!p)
			goto err_unlock;
		ret = -EPERM;
1733 1734 1735
		pcred = __task_cred(p);
		if (cred->euid != pcred->euid &&
		    cred->euid != pcred->uid &&
1736
		    !capable(CAP_SYS_PTRACE))
1737 1738
			goto err_unlock;
		head = p->robust_list;
1739
		rcu_read_unlock();
1740 1741 1742 1743 1744 1745 1746
	}

	if (put_user(sizeof(*head), len_ptr))
		return -EFAULT;
	return put_user(head, head_ptr);

err_unlock:
1747
	rcu_read_unlock();
1748 1749 1750 1751 1752 1753 1754 1755

	return ret;
}

/*
 * Process a futex-list entry, check whether it's owned by the
 * dying task, and do notification if so:
 */
1756
int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
1757
{
1758
	u32 uval, nval, mval;
1759

1760 1761
retry:
	if (get_user(uval, uaddr))
1762 1763
		return -1;

1764
	if ((uval & FUTEX_TID_MASK) == task_pid_vnr(curr)) {
1765 1766 1767 1768 1769 1770 1771 1772 1773 1774
		/*
		 * Ok, this dying thread is truly holding a futex
		 * of interest. Set the OWNER_DIED bit atomically
		 * via cmpxchg, and if the value had FUTEX_WAITERS
		 * set, wake up a waiter (if any). (We have to do a
		 * futex_wake() even if OWNER_DIED is already set -
		 * to handle the rare but possible case of recursive
		 * thread-death.) The rest of the cleanup is done in
		 * userspace.
		 */
1775 1776 1777
		mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
		nval = futex_atomic_cmpxchg_inatomic(uaddr, uval, mval);

1778 1779 1780 1781
		if (nval == -EFAULT)
			return -1;

		if (nval != uval)
1782
			goto retry;
1783

1784 1785 1786 1787
		/*
		 * Wake robust non-PI futexes here. The wakeup of
		 * PI futexes happens in exit_pi_state():
		 */
T
Thomas Gleixner 已提交
1788
		if (!pi && (uval & FUTEX_WAITERS))
P
Peter Zijlstra 已提交
1789
			futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
1790 1791 1792 1793
	}
	return 0;
}

1794 1795 1796 1797
/*
 * Fetch a robust-list pointer. Bit 0 signals PI futexes:
 */
static inline int fetch_robust_entry(struct robust_list __user **entry,
A
Al Viro 已提交
1798 1799
				     struct robust_list __user * __user *head,
				     int *pi)
1800 1801 1802
{
	unsigned long uentry;

A
Al Viro 已提交
1803
	if (get_user(uentry, (unsigned long __user *)head))
1804 1805
		return -EFAULT;

A
Al Viro 已提交
1806
	*entry = (void __user *)(uentry & ~1UL);
1807 1808 1809 1810 1811
	*pi = uentry & 1;

	return 0;
}

1812 1813 1814 1815 1816 1817 1818 1819 1820
/*
 * Walk curr->robust_list (very carefully, it's a userspace list!)
 * and mark any locks found there dead, and notify any waiters.
 *
 * We silently return on any sign of list-walking problem.
 */
void exit_robust_list(struct task_struct *curr)
{
	struct robust_list_head __user *head = curr->robust_list;
M
Martin Schwidefsky 已提交
1821 1822
	struct robust_list __user *entry, *next_entry, *pending;
	unsigned int limit = ROBUST_LIST_LIMIT, pi, next_pi, pip;
1823
	unsigned long futex_offset;
M
Martin Schwidefsky 已提交
1824
	int rc;
1825

1826 1827 1828
	if (!futex_cmpxchg_enabled)
		return;

1829 1830 1831 1832
	/*
	 * Fetch the list head (which was registered earlier, via
	 * sys_set_robust_list()):
	 */
1833
	if (fetch_robust_entry(&entry, &head->list.next, &pi))
1834 1835 1836 1837 1838 1839 1840 1841 1842 1843
		return;
	/*
	 * Fetch the relative futex offset:
	 */
	if (get_user(futex_offset, &head->futex_offset))
		return;
	/*
	 * Fetch any possibly pending lock-add first, and handle it
	 * if it exists:
	 */
1844
	if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
1845
		return;
1846

M
Martin Schwidefsky 已提交
1847
	next_entry = NULL;	/* avoid warning with gcc */
1848
	while (entry != &head->list) {
M
Martin Schwidefsky 已提交
1849 1850 1851 1852 1853
		/*
		 * Fetch the next entry in the list before calling
		 * handle_futex_death:
		 */
		rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
1854 1855
		/*
		 * A pending lock might already be on the list, so
1856
		 * don't process it twice:
1857 1858
		 */
		if (entry != pending)
A
Al Viro 已提交
1859
			if (handle_futex_death((void __user *)entry + futex_offset,
1860
						curr, pi))
1861
				return;
M
Martin Schwidefsky 已提交
1862
		if (rc)
1863
			return;
M
Martin Schwidefsky 已提交
1864 1865
		entry = next_entry;
		pi = next_pi;
1866 1867 1868 1869 1870 1871 1872 1873
		/*
		 * Avoid excessively long or circular lists:
		 */
		if (!--limit)
			break;

		cond_resched();
	}
M
Martin Schwidefsky 已提交
1874 1875 1876 1877

	if (pending)
		handle_futex_death((void __user *)pending + futex_offset,
				   curr, pip);
1878 1879
}

1880
long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
1881
		u32 __user *uaddr2, u32 val2, u32 val3)
L
Linus Torvalds 已提交
1882
{
1883
	int clockrt, ret = -ENOSYS;
E
Eric Dumazet 已提交
1884
	int cmd = op & FUTEX_CMD_MASK;
P
Peter Zijlstra 已提交
1885
	int fshared = 0;
E
Eric Dumazet 已提交
1886 1887

	if (!(op & FUTEX_PRIVATE_FLAG))
P
Peter Zijlstra 已提交
1888
		fshared = 1;
L
Linus Torvalds 已提交
1889

1890 1891 1892
	clockrt = op & FUTEX_CLOCK_REALTIME;
	if (clockrt && cmd != FUTEX_WAIT_BITSET)
		return -ENOSYS;
L
Linus Torvalds 已提交
1893

E
Eric Dumazet 已提交
1894
	switch (cmd) {
L
Linus Torvalds 已提交
1895
	case FUTEX_WAIT:
1896 1897
		val3 = FUTEX_BITSET_MATCH_ANY;
	case FUTEX_WAIT_BITSET:
1898
		ret = futex_wait(uaddr, fshared, val, timeout, val3, clockrt);
L
Linus Torvalds 已提交
1899 1900
		break;
	case FUTEX_WAKE:
1901 1902 1903
		val3 = FUTEX_BITSET_MATCH_ANY;
	case FUTEX_WAKE_BITSET:
		ret = futex_wake(uaddr, fshared, val, val3);
L
Linus Torvalds 已提交
1904 1905
		break;
	case FUTEX_REQUEUE:
E
Eric Dumazet 已提交
1906
		ret = futex_requeue(uaddr, fshared, uaddr2, val, val2, NULL);
L
Linus Torvalds 已提交
1907 1908
		break;
	case FUTEX_CMP_REQUEUE:
E
Eric Dumazet 已提交
1909
		ret = futex_requeue(uaddr, fshared, uaddr2, val, val2, &val3);
L
Linus Torvalds 已提交
1910
		break;
1911
	case FUTEX_WAKE_OP:
E
Eric Dumazet 已提交
1912
		ret = futex_wake_op(uaddr, fshared, uaddr2, val, val2, val3);
1913
		break;
1914
	case FUTEX_LOCK_PI:
1915 1916
		if (futex_cmpxchg_enabled)
			ret = futex_lock_pi(uaddr, fshared, val, timeout, 0);
1917 1918
		break;
	case FUTEX_UNLOCK_PI:
1919 1920
		if (futex_cmpxchg_enabled)
			ret = futex_unlock_pi(uaddr, fshared);
1921 1922
		break;
	case FUTEX_TRYLOCK_PI:
1923 1924
		if (futex_cmpxchg_enabled)
			ret = futex_lock_pi(uaddr, fshared, 0, timeout, 1);
1925
		break;
L
Linus Torvalds 已提交
1926 1927 1928 1929 1930 1931 1932
	default:
		ret = -ENOSYS;
	}
	return ret;
}


1933 1934 1935
SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
		struct timespec __user *, utime, u32 __user *, uaddr2,
		u32, val3)
L
Linus Torvalds 已提交
1936
{
1937 1938
	struct timespec ts;
	ktime_t t, *tp = NULL;
1939
	u32 val2 = 0;
E
Eric Dumazet 已提交
1940
	int cmd = op & FUTEX_CMD_MASK;
L
Linus Torvalds 已提交
1941

1942 1943
	if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
		      cmd == FUTEX_WAIT_BITSET)) {
1944
		if (copy_from_user(&ts, utime, sizeof(ts)) != 0)
L
Linus Torvalds 已提交
1945
			return -EFAULT;
1946
		if (!timespec_valid(&ts))
1947
			return -EINVAL;
1948 1949

		t = timespec_to_ktime(ts);
E
Eric Dumazet 已提交
1950
		if (cmd == FUTEX_WAIT)
1951
			t = ktime_add_safe(ktime_get(), t);
1952
		tp = &t;
L
Linus Torvalds 已提交
1953 1954
	}
	/*
E
Eric Dumazet 已提交
1955
	 * requeue parameter in 'utime' if cmd == FUTEX_REQUEUE.
1956
	 * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
L
Linus Torvalds 已提交
1957
	 */
1958 1959
	if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
	    cmd == FUTEX_WAKE_OP)
1960
		val2 = (u32) (unsigned long) utime;
L
Linus Torvalds 已提交
1961

1962
	return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
L
Linus Torvalds 已提交
1963 1964
}

1965
static int __init futex_init(void)
L
Linus Torvalds 已提交
1966
{
1967
	u32 curval;
T
Thomas Gleixner 已提交
1968
	int i;
A
Akinobu Mita 已提交
1969

1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983
	/*
	 * This will fail and we want it. Some arch implementations do
	 * runtime detection of the futex_atomic_cmpxchg_inatomic()
	 * functionality. We want to know that before we call in any
	 * of the complex code paths. Also we want to prevent
	 * registration of robust lists in that case. NULL is
	 * guaranteed to fault and we get -EFAULT on functional
	 * implementation, the non functional ones will return
	 * -ENOSYS.
	 */
	curval = cmpxchg_futex_value_locked(NULL, 0, 0);
	if (curval == -EFAULT)
		futex_cmpxchg_enabled = 1;

T
Thomas Gleixner 已提交
1984 1985 1986 1987 1988
	for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
		plist_head_init(&futex_queues[i].chain, &futex_queues[i].lock);
		spin_lock_init(&futex_queues[i].lock);
	}

L
Linus Torvalds 已提交
1989 1990
	return 0;
}
1991
__initcall(futex_init);