// SPDX-License-Identifier: GPL-2.0-or-later/* *  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!" */#include <linux/compat.h>#include <linux/jhash.h>#include <linux/pagemap.h>#include <linux/debugfs.h>#include <linux/plist.h>#include <linux/memblock.h>#include <linux/fault-inject.h>#include <linux/slab.h> #include "futex.h"#include "../locking/rtmutex_common.h" /* * The base of the bucket array and its size are always used together * (after initialization only in futex_hash()), 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); 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); 	debugfs_create_bool("ignore-private", mode, dir,			    &fail_futex.ignore_private);	return 0;} late_initcall(fail_futex_debugfs); #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ #endif /* CONFIG_FAIL_FUTEX */ /** * futex_hash - 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. */struct futex_hash_bucket *futex_hash(union futex_key *key){	u32 hash = jhash2((u32 *)key, offsetof(typeof(*key), both.offset) / 4,			  key->both.offset); 	return &futex_queues[hash & (futex_hashsize - 1)];}  /** * futex_setup_timer - set up the sleeping hrtimer. * @time:	ptr to the given timeout value * @timeout:	the hrtimer_sleeper structure to be set up * @flags:	futex flags * @range_ns:	optional range in ns * * Return: Initialized hrtimer_sleeper structure or NULL if no timeout *	   value given */struct hrtimer_sleeper *futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,		  int flags, u64 range_ns){	if (!time)		return NULL; 	hrtimer_setup_sleeper_on_stack(timeout,				       (flags & FLAGS_CLOCKRT) ? CLOCK_REALTIME : CLOCK_MONOTONIC,				       HRTIMER_MODE_ABS);	/*	 * If range_ns is 0, calling hrtimer_set_expires_range_ns() is	 * effectively the same as calling hrtimer_set_expires().	 */	hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns); 	return timeout;} /* * Generate a machine wide unique identifier for this inode. * * This relies on u64 not wrapping in the life-time of the machine; which with * 1ns resolution means almost 585 years. * * This further relies on the fact that a well formed program will not unmap * the file while it has a (shared) futex waiting on it. This mapping will have * a file reference which pins the mount and inode. * * If for some reason an inode gets evicted and read back in again, it will get * a new sequence number and will _NOT_ match, even though it is the exact same * file. * * It is important that futex_match() will never have a false-positive, esp. * for PI futexes that can mess up the state. The above argues that false-negatives * are only possible for malformed programs. */static u64 get_inode_sequence_number(struct inode *inode){	static atomic64_t i_seq;	u64 old; 	/* Does the inode already have a sequence number? */	old = atomic64_read(&inode->i_sequence);	if (likely(old))		return old; 	for (;;) {		u64 new = atomic64_inc_return(&i_seq);		if (WARN_ON_ONCE(!new))			continue; 		old = 0;		if (!atomic64_try_cmpxchg_relaxed(&inode->i_sequence, &old, new))			return old;		return new;	}} /** * get_futex_key() - Get parameters which are the keys for a futex * @uaddr:	virtual address of the futex * @flags:	FLAGS_* * @key:	address where result is stored. * @rw:		mapping needs to be read/write (values: FUTEX_READ, *              FUTEX_WRITE) * * Return: a negative error code or 0 * * The key words are stored in @key on success. * * For shared mappings (when @fshared), the key is: * *   ( inode->i_sequence, page->index, offset_within_page ) * * [ also see get_inode_sequence_number() ] * * For private mappings (or when !@fshared), the key is: * *   ( current->mm, address, 0 ) * * This allows (cross process, where applicable) identification of the futex * without keeping the page pinned for the duration of the FUTEX_WAIT. * * lock_page() might sleep, the caller should not hold a spinlock. */int get_futex_key(u32 __user *uaddr, unsigned int flags, union futex_key *key,		  enum futex_access rw){	unsigned long address = (unsigned long)uaddr;	struct mm_struct *mm = current->mm;	struct page *page;	struct folio *folio;	struct address_space *mapping;	int err, ro = 0;	bool fshared; 	fshared = flags & FLAGS_SHARED; 	/*	 * The futex address must be "naturally" aligned.	 */	key->both.offset = address % PAGE_SIZE;	if (unlikely((address % sizeof(u32)) != 0))		return -EINVAL;	address -= key->both.offset; 	if (unlikely(!access_ok(uaddr, sizeof(u32))))		return -EFAULT; 	if (unlikely(should_fail_futex(fshared)))		return -EFAULT; 	/*	 * 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) {		/*		 * On no-MMU, shared futexes are treated as private, therefore		 * we must not include the current process in the key. Since		 * there is only one address space, the address is a unique key		 * on its own.		 */		if (IS_ENABLED(CONFIG_MMU))			key->private.mm = mm;		else			key->private.mm = NULL; 		key->private.address = address;		return 0;	} again:	/* Ignore any VERIFY_READ mapping (futex common case) */	if (unlikely(should_fail_futex(true)))		return -EFAULT; 	err = get_user_pages_fast(address, 1, FOLL_WRITE, &page);	/*	 * If write access is not required (eg. FUTEX_WAIT), try	 * and get read-only access.	 */	if (err == -EFAULT && rw == FUTEX_READ) {		err = get_user_pages_fast(address, 1, 0, &page);		ro = 1;	}	if (err < 0)		return err;	else		err = 0; 	/*	 * The treatment of mapping from this point on is critical. The folio	 * lock protects many things but in this context the folio lock	 * stabilizes mapping, prevents inode freeing in the shared	 * file-backed region case and guards against movement to swap cache.	 *	 * Strictly speaking the folio lock is not needed in all cases being	 * considered here and folio lock forces unnecessarily serialization.	 * From this point on, mapping will be re-verified if necessary and	 * folio lock will be acquired only if it is unavoidable	 *	 * Mapping checks require the folio so it is looked up now. For	 * anonymous pages, it does not matter if the folio is split	 * in the future as the key is based on the address. For	 * filesystem-backed pages, the precise page is required as the	 * index of the page determines the key.	 */	folio = page_folio(page);	mapping = READ_ONCE(folio->mapping); 	/*	 * If folio->mapping is NULL, then it cannot be an anonymous	 * page; but it might be the ZERO_PAGE or in the gate area or	 * in a special mapping (all cases which we are happy to fail);	 * or it may have been a good file page when get_user_pages_fast	 * found it, but truncated or holepunched or subjected to	 * invalidate_complete_page2 before we got the folio lock (also	 * cases which we are happy to fail).  And we hold a reference,	 * so refcount care in invalidate_inode_page's remove_mapping	 * prevents drop_caches from setting mapping to NULL beneath us.	 *	 * The case we do have to guard against is when memory pressure made	 * shmem_writepage move it from filecache to swapcache beneath us:	 * an unlikely race, but we do need to retry for folio->mapping.	 */	if (unlikely(!mapping)) {		int shmem_swizzled; 		/*		 * Folio lock is required to identify which special case above		 * applies. If this is really a shmem page then the folio lock		 * will prevent unexpected transitions.		 */		folio_lock(folio);		shmem_swizzled = folio_test_swapcache(folio) || folio->mapping;		folio_unlock(folio);		folio_put(folio); 		if (shmem_swizzled)			goto again; 		return -EFAULT;	} 	/*	 * Private mappings are handled in a simple way.	 *	 * If the futex key is stored in anonymous memory, then the associated	 * object is the mm which is implicitly pinned by the calling process.	 *	 * NOTE: When userspace waits on a MAP_SHARED mapping, even if	 * it's a read-only handle, it's expected that futexes attach to	 * the object not the particular process.	 */	if (folio_test_anon(folio)) {		/*		 * A RO anonymous page will never change and thus doesn't make		 * sense for futex operations.		 */		if (unlikely(should_fail_futex(true)) || ro) {			err = -EFAULT;			goto out;		} 		key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */		key->private.mm = mm;		key->private.address = address; 	} else {		struct inode *inode; 		/*		 * The associated futex object in this case is the inode and		 * the folio->mapping must be traversed. Ordinarily this should		 * be stabilised under folio lock but it's not strictly		 * necessary in this case as we just want to pin the inode, not		 * update i_pages or anything like that.		 *		 * The RCU read lock is taken as the inode is finally freed		 * under RCU. If the mapping still matches expectations then the		 * mapping->host can be safely accessed as being a valid inode.		 */		rcu_read_lock(); 		if (READ_ONCE(folio->mapping) != mapping) {			rcu_read_unlock();			folio_put(folio); 			goto again;		} 		inode = READ_ONCE(mapping->host);		if (!inode) {			rcu_read_unlock();			folio_put(folio); 			goto again;		} 		key->both.offset |= FUT_OFF_INODE; /* inode-based key */		key->shared.i_seq = get_inode_sequence_number(inode);		key->shared.pgoff = page_pgoff(folio, page);		rcu_read_unlock();	} out:	folio_put(folio);	return err;} /** * fault_in_user_writeable() - Fault in user address and verify RW access * @uaddr:	pointer to faulting user space address * * Slow path to fixup the fault we just took in the atomic write * access to @uaddr. * * We have no generic implementation of a non-destructive write to the * user address. We know that we faulted in the atomic pagefault * disabled section so we can as well avoid the #PF overhead by * calling get_user_pages() right away. */int fault_in_user_writeable(u32 __user *uaddr){	struct mm_struct *mm = current->mm;	int ret; 	mmap_read_lock(mm);	ret = fixup_user_fault(mm, (unsigned long)uaddr,			       FAULT_FLAG_WRITE, NULL);	mmap_read_unlock(mm); 	return ret < 0 ? ret : 0;} /** * futex_top_waiter() - Return the highest priority waiter on a futex * @hb:		the hash bucket the futex_q's reside in * @key:	the futex key (to distinguish it from other futex futex_q's) * * Must be called with the hb lock held. */struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb, union futex_key *key){	struct futex_q *this; 	plist_for_each_entry(this, &hb->chain, list) {		if (futex_match(&this->key, key))			return this;	}	return NULL;} /** * wait_for_owner_exiting - Block until the owner has exited * @ret: owner's current futex lock status * @exiting:	Pointer to the exiting task * * Caller must hold a refcount on @exiting. */void wait_for_owner_exiting(int ret, struct task_struct *exiting){	if (ret != -EBUSY) {		WARN_ON_ONCE(exiting);		return;	} 	if (WARN_ON_ONCE(ret == -EBUSY && !exiting))		return; 	mutex_lock(&exiting->futex_exit_mutex);	/*	 * No point in doing state checking here. If the waiter got here	 * while the task was in exec()->exec_futex_release() then it can	 * have any FUTEX_STATE_* value when the waiter has acquired the	 * mutex. OK, if running, EXITING or DEAD if it reached exit()	 * already. Highly unlikely and not a problem. Just one more round	 * through the futex maze.	 */	mutex_unlock(&exiting->futex_exit_mutex); 	put_task_struct(exiting);} /** * __futex_unqueue() - Remove the futex_q from its futex_hash_bucket * @q:	The futex_q to unqueue * * The q->lock_ptr must not be NULL and must be held by the caller. */void __futex_unqueue(struct futex_q *q){	struct futex_hash_bucket *hb; 	if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list)))		return;	lockdep_assert_held(q->lock_ptr); 	hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);	plist_del(&q->list, &hb->chain);

Lines 1–500 of 1152. Load more