/* *  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 * *  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. * *  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> * *  PRIVATE futexes by Eric Dumazet *  Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com> * *  Requeue-PI support by Darren Hart <dvhltc@us.ibm.com> *  Copyright (C) IBM Corporation, 2009 *  Thanks to Thomas Gleixner for conceptual design and careful reviews. * *  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>#include <linux/signal.h>#include <linux/export.h>#include <linux/magic.h>#include <linux/pid.h>#include <linux/nsproxy.h>#include <linux/ptrace.h>#include <linux/sched/rt.h>#include <linux/sched/wake_q.h>#include <linux/sched/mm.h>#include <linux/hugetlb.h>#include <linux/freezer.h>#include <linux/memblock.h>#include <linux/fault-inject.h> #include <asm/futex.h> #include "locking/rtmutex_common.h" /* * READ this before attempting to hack on futexes! * * Basic futex operation and ordering guarantees * ============================================= * * The waiter reads the futex value in user space and calls * futex_wait(). This function computes the hash bucket and acquires * the hash bucket lock. After that it reads the futex user space value * again and verifies that the data has not changed. If it has not changed * it enqueues itself into the hash bucket, releases the hash bucket lock * and schedules. * * The waker side modifies the user space value of the futex and calls * futex_wake(). This function computes the hash bucket and acquires the * hash bucket lock. Then it looks for waiters on that futex in the hash * bucket and wakes them. * * In futex wake up scenarios where no tasks are blocked on a futex, taking * the hb spinlock can be avoided and simply return. In order for this * optimization to work, ordering guarantees must exist so that the waiter * being added to the list is acknowledged when the list is concurrently being * checked by the waker, avoiding scenarios like the following: * * CPU 0                               CPU 1 * val = *futex; * sys_futex(WAIT, futex, val); *   futex_wait(futex, val); *   uval = *futex; *                                     *futex = newval; *                                     sys_futex(WAKE, futex); *                                       futex_wake(futex); *                                       if (queue_empty()) *                                         return; *   if (uval == val) *      lock(hash_bucket(futex)); *      queue(); *     unlock(hash_bucket(futex)); *     schedule(); * * This would cause the waiter on CPU 0 to wait forever because it * missed the transition of the user space value from val to newval * and the waker did not find the waiter in the hash bucket queue. * * The correct serialization ensures that a waiter either observes * the changed user space value before blocking or is woken by a * concurrent waker: * * CPU 0                                 CPU 1 * val = *futex; * sys_futex(WAIT, futex, val); *   futex_wait(futex, val); * *   waiters++; (a) *   smp_mb(); (A) <-- paired with -. *                                  | *   lock(hash_bucket(futex));      | *                                  | *   uval = *futex;                 | *                                  |        *futex = newval; *                                  |        sys_futex(WAKE, futex); *                                  |          futex_wake(futex); *                                  | *                                  `--------> smp_mb(); (B) *   if (uval == val) *     queue(); *     unlock(hash_bucket(futex)); *     schedule();                         if (waiters) *                                           lock(hash_bucket(futex)); *   else                                    wake_waiters(futex); *     waiters--; (b)                        unlock(hash_bucket(futex)); * * Where (A) orders the waiters increment and the futex value read through * atomic operations (see hb_waiters_inc) and where (B) orders the write * to futex and the waiters read -- this is done by the barriers for both * shared and private futexes in get_futex_key_refs(). * * This yields the following case (where X:=waiters, Y:=futex): * *	X = Y = 0 * *	w[X]=1		w[Y]=1 *	MB		MB *	r[Y]=y		r[X]=x * * Which guarantees that x==0 && y==0 is impossible; which translates back into * the guarantee that we cannot both miss the futex variable change and the * enqueue. * * Note that a new waiter is accounted for in (a) even when it is possible that * the wait call can return error, in which case we backtrack from it in (b). * Refer to the comment in queue_lock(). * * Similarly, in order to account for waiters being requeued on another * address we always increment the waiters for the destination bucket before * acquiring the lock. It then decrements them again  after releasing it - * the code that actually moves the futex(es) between hash buckets (requeue_futex) * will do the additional required waiter count housekeeping. This is done for * double_lock_hb() and double_unlock_hb(), respectively. */ #ifndef CONFIG_HAVE_FUTEX_CMPXCHGint __read_mostly futex_cmpxchg_enabled;#endif /* * Futex flags used to encode options to functions and preserve them across * restarts. */#ifdef CONFIG_MMU# define FLAGS_SHARED		0x01#else/* * NOMMU does not have per process address space. Let the compiler optimize * code away. */# define FLAGS_SHARED		0x00#endif#define FLAGS_CLOCKRT		0x02#define FLAGS_HAS_TIMEOUT	0x04 /* * 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;} __randomize_layout; /** * struct futex_q - The hashed futex queue entry, one per waiting task * @list:		priority-sorted list of tasks waiting on this futex * @task:		the task waiting on the futex * @lock_ptr:		the hash bucket lock * @key:		the key the futex is hashed on * @pi_state:		optional priority inheritance state * @rt_waiter:		rt_waiter storage for use with requeue_pi * @requeue_pi_key:	the requeue_pi target futex key * @bitset:		bitset for the optional bitmasked wakeup * * We use this hashed waitqueue, instead of a normal wait_queue_entry_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. * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0. * The order of wakeup is always to make the first condition true, then * the second. * * PI futexes are typically woken before they are removed from the hash list via * the rt_mutex code. See unqueue_me_pi(). */struct futex_q {	struct plist_node list; 	struct task_struct *task;	spinlock_t *lock_ptr;	union futex_key key;	struct futex_pi_state *pi_state;	struct rt_mutex_waiter *rt_waiter;	union futex_key *requeue_pi_key;	u32 bitset;} __randomize_layout; static const struct futex_q futex_q_init = {	/* list gets initialized in queue_me()*/	.key = FUTEX_KEY_INIT,	.bitset = FUTEX_BITSET_MATCH_ANY}; /* * 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. */struct futex_hash_bucket {	atomic_t waiters;	spinlock_t lock;	struct plist_head chain;} ____cacheline_aligned_in_smp; /* * The base of the bucket array and its size are always used together * (after initialization only in hash_futex()), so ensure that they * reside in the same cacheline. */static struct {	struct futex_hash_bucket *queues;	unsigned long            hashsize;} __futex_data __read_mostly __aligned(2*sizeof(long));#define futex_queues   (__futex_data.queues)#define futex_hashsize (__futex_data.hashsize)  /* * Fault injections for futexes. */#ifdef CONFIG_FAIL_FUTEX static struct {	struct fault_attr attr; 	bool ignore_private;} fail_futex = {	.attr = FAULT_ATTR_INITIALIZER,	.ignore_private = false,}; static int __init setup_fail_futex(char *str){	return setup_fault_attr(&fail_futex.attr, str);}__setup("fail_futex=", setup_fail_futex); static bool should_fail_futex(bool fshared){	if (fail_futex.ignore_private && !fshared)		return false; 	return should_fail(&fail_futex.attr, 1);} #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS static int __init fail_futex_debugfs(void){	umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;	struct dentry *dir; 	dir = fault_create_debugfs_attr("fail_futex", NULL,					&fail_futex.attr);	if (IS_ERR(dir))		return PTR_ERR(dir); 	if (!debugfs_create_bool("ignore-private", mode, dir,				 &fail_futex.ignore_private)) {		debugfs_remove_recursive(dir);		return -ENOMEM;	} 	return 0;} late_initcall(fail_futex_debugfs); #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ #elsestatic inline bool should_fail_futex(bool fshared){	return false;}#endif /* CONFIG_FAIL_FUTEX */ static inline void futex_get_mm(union futex_key *key){	mmgrab(key->private.mm);	/*	 * Ensure futex_get_mm() implies a full barrier such that	 * get_futex_key() implies a full barrier. This is relied upon	 * as smp_mb(); (B), see the ordering comment above.	 */	smp_mb__after_atomic();} /* * Reflects a new waiter being added to the waitqueue. */static inline void hb_waiters_inc(struct futex_hash_bucket *hb){#ifdef CONFIG_SMP	atomic_inc(&hb->waiters);	/*	 * Full barrier (A), see the ordering comment above.	 */	smp_mb__after_atomic();#endif} /* * Reflects a waiter being removed from the waitqueue by wakeup * paths. */static inline void hb_waiters_dec(struct futex_hash_bucket *hb){#ifdef CONFIG_SMP	atomic_dec(&hb->waiters);#endif} static inline int hb_waiters_pending(struct futex_hash_bucket *hb){#ifdef CONFIG_SMP	return atomic_read(&hb->waiters);#else	return 1;#endif} /** * hash_futex - Return the hash bucket in the global hash * @key:	Pointer to the futex key for which the hash is calculated * * We hash on the keys returned from get_futex_key (see below) and return the * corresponding hash bucket in the global hash. */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 & (futex_hashsize - 1)];}  /** * match_futex - Check whether two futex keys are equal * @key1:	Pointer to key1 * @key2:	Pointer to key2 * * 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 && key2		&& key1->both.word == key2->both.word		&& key1->both.ptr == key2->both.ptr		&& key1->both.offset == key2->both.offset);} /* * 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; 	/*	 * On MMU less systems futexes are always "private" as there is no per	 * process address space. We need the smp wmb nevertheless - yes,	 * arch/blackfin has MMU less SMP ...	 */	if (!IS_ENABLED(CONFIG_MMU)) {		smp_mb(); /* explicit smp_mb(); (B) */		return;	} 	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {	case FUT_OFF_INODE:		ihold(key->shared.inode); /* implies smp_mb(); (B) */		break;	case FUT_OFF_MMSHARED:		futex_get_mm(key); /* implies smp_mb(); (B) */		break;	default:		/*		 * Private futexes do not hold reference on an inode or		 * mm, therefore the only purpose of calling get_futex_key_refs		 * is because we need the barrier for the lockless waiter check.		 */		smp_mb(); /* explicit smp_mb(); (B) */	}} /* * Drop a reference to the resource addressed by a key. * The hash bucket spinlock must not be held. This is * a no-op for private futexes, see comment in the get * counterpart. */static void drop_futex_key_refs(union futex_key *key){	if (!key->both.ptr) {		/* If we're here then we tried to put a key we failed to get */		WARN_ON_ONCE(1);		return;	} 	if (!IS_ENABLED(CONFIG_MMU))		return; 	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;	}} /** * get_futex_key() - Get parameters which are the keys for a futex * @uaddr:	virtual address of the futex * @fshared:	0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED * @key:	address where result is stored. * @rw:		mapping needs to be read/write (values: VERIFY_READ, *              VERIFY_WRITE) * * Return: a negative error code or 0 * * The key words are stored in @key on success. * * For shared mappings, it's (page->index, file_inode(vma->vm_file), * offset_within_page).  For private mappings, it's (uaddr, current->mm). * We can usually work out the index without swapping in the page. * * lock_page() might sleep, the caller should not hold a spinlock. */static intget_futex_key(u32 __user *uaddr, int fshared, union futex_key *key, int rw)

Lines 1–500 of 3697. Load more