// 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/debugfs.h>#include <linux/fault-inject.h>#include <linux/gfp.h>#include <linux/jhash.h>#include <linux/memblock.h>#include <linux/mempolicy.h>#include <linux/mmap_lock.h>#include <linux/pagemap.h>#include <linux/plist.h>#include <linux/prctl.h>#include <linux/rseq.h>#include <linux/slab.h>#include <linux/vmalloc.h> #include <vdso/futex.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 {	unsigned long            hashmask;	unsigned int		 hashshift;	struct futex_hash_bucket *queues[MAX_NUMNODES];} __futex_data __read_mostly __aligned(2*sizeof(long)); #define futex_hashmask	(__futex_data.hashmask)#define futex_hashshift	(__futex_data.hashshift)#define futex_queues	(__futex_data.queues) struct futex_private_hash {	int		state;	unsigned int	hash_mask;	struct rcu_head	rcu;	void		*mm;	bool		custom;	struct futex_hash_bucket queues[];}; /* * 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 */ static struct futex_hash_bucket *__futex_hash(union futex_key *key, struct futex_private_hash *fph, struct futex_private_hash **fph_p); #ifdef CONFIG_FUTEX_PRIVATE_HASHstatic bool futex_ref_get(struct futex_private_hash *fph);static bool futex_ref_put(struct futex_private_hash *fph);static bool futex_ref_is_dead(struct futex_private_hash *fph); enum { FR_PERCPU = 0, FR_ATOMIC }; static bool futex_private_hash_get(struct futex_private_hash *fph){	return futex_ref_get(fph);} void futex_private_hash_put(struct futex_private_hash *fph){	if (fph && futex_ref_put(fph))		wake_up_var(fph->mm);} static struct futex_hash_bucket *__futex_hash_private(union futex_key *key, struct futex_private_hash *fph){	u32 hash; 	hash = jhash2((void *)&key->private.address, sizeof(key->private.address) / 4,		      key->both.offset); 	return &fph->queues[hash & fph->hash_mask];} static void futex_rehash_private(struct futex_private_hash *old,				 struct futex_private_hash *new){	struct futex_hash_bucket *hb_old, *hb_new;	unsigned int slots = old->hash_mask + 1;	unsigned int i; 	for (i = 0; i < slots; i++) {		struct futex_q *this, *tmp; 		hb_old = &old->queues[i]; 		spin_lock(&hb_old->lock);		plist_for_each_entry_safe(this, tmp, &hb_old->chain, list) {			plist_del(&this->list, &hb_old->chain);			futex_hb_waiters_dec(hb_old); 			WARN_ON_ONCE(this->lock_ptr != &hb_old->lock); 			hb_new = __futex_hash(&this->key, new, NULL);			futex_hb_waiters_inc(hb_new);			/*			 * The new pointer isn't published yet but an already			 * moved user can be unqueued due to timeout or signal.			 */			spin_lock_nested(&hb_new->lock, SINGLE_DEPTH_NESTING);			plist_add(&this->list, &hb_new->chain);			this->lock_ptr = &hb_new->lock;			spin_unlock(&hb_new->lock);		}		spin_unlock(&hb_old->lock);	}} static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *new){	struct futex_mm_phash *mmph = &mm->futex.phash;	struct futex_private_hash *fph; 	WARN_ON_ONCE(mmph->hash_new); 	fph = rcu_dereference_protected(mmph->hash, lockdep_is_held(&mmph->lock));	if (fph) {		if (!futex_ref_is_dead(fph)) {			mmph->hash_new = new;			return false;		} 		futex_rehash_private(fph, new);	}	new->state = FR_PERCPU;	scoped_guard(rcu) {		mmph->batches = get_state_synchronize_rcu();		rcu_assign_pointer(mmph->hash, new);	}	kvfree_rcu(fph, rcu);	return true;} static void futex_pivot_hash(struct mm_struct *mm){	scoped_guard(mutex, &mm->futex.phash.lock) {		struct futex_private_hash *fph; 		fph = mm->futex.phash.hash_new;		if (fph) {			mm->futex.phash.hash_new = NULL;			__futex_pivot_hash(mm, fph);		}	}} struct futex_private_hash *futex_private_hash(struct mm_struct *mm){	/*	 * Ideally we don't loop. If there is a replacement in progress	 * then a new private hash is already prepared and a reference can't be	 * obtained once the last user dropped it's.	 * In that case we block on mm_struct::futex_hash_lock and either have	 * to perform the replacement or wait while someone else is doing the	 * job. Eitherway, on the second iteration we acquire a reference on the	 * new private hash or loop again because a new replacement has been	 * requested.	 */again:	scoped_guard(rcu) {		struct futex_private_hash *fph; 		fph = rcu_dereference(mm->futex.phash.hash);		if (!fph)			return NULL; 		if (futex_private_hash_get(fph))			return fph;	}	futex_pivot_hash(mm);	goto again;} struct futex_bucket_ref futex_hash(union futex_key *key){again:	scoped_guard(rcu) {		struct futex_private_hash *fph = NULL;		struct futex_hash_bucket *hb; 		hb = __futex_hash(key, NULL, &fph); 		if (!fph || futex_private_hash_get(fph))			return (struct futex_bucket_ref){ .hb = hb, .fph = fph };	}	futex_pivot_hash(key->private.mm);	goto again;} #else /* !CONFIG_FUTEX_PRIVATE_HASH */ struct futex_bucket_ref futex_hash(union futex_key *key){	return (struct futex_bucket_ref){ .hb = __futex_hash(key, NULL, NULL), .fph = NULL };} #endif /* CONFIG_FUTEX_PRIVATE_HASH */ #ifdef CONFIG_FUTEX_MPOL static int __futex_key_to_node(struct mm_struct *mm, unsigned long addr){	struct vm_area_struct *vma = vma_lookup(mm, addr);	struct mempolicy *mpol;	int node = FUTEX_NO_NODE; 	if (!vma)		return FUTEX_NO_NODE; 	mpol = READ_ONCE(vma->vm_policy);	if (!mpol)		return FUTEX_NO_NODE; 	switch (mpol->mode) {	case MPOL_PREFERRED:		node = first_node(mpol->nodes);		break;	case MPOL_PREFERRED_MANY:	case MPOL_BIND:		if (mpol->home_node != NUMA_NO_NODE)			node = mpol->home_node;		break;	default:		break;	} 	return node;} static int futex_key_to_node_opt(struct mm_struct *mm, unsigned long addr){	int seq, node; 	guard(rcu)(); 	if (!mmap_lock_speculate_try_begin(mm, &seq))		return -EBUSY; 	node = __futex_key_to_node(mm, addr); 	if (mmap_lock_speculate_retry(mm, seq))		return -EAGAIN; 	return node;} static int futex_mpol(struct mm_struct *mm, unsigned long addr){	int node; 	node = futex_key_to_node_opt(mm, addr);	if (node >= FUTEX_NO_NODE)		return node; 	guard(mmap_read_lock)(mm);	return __futex_key_to_node(mm, addr);} #else /* !CONFIG_FUTEX_MPOL */ static int futex_mpol(struct mm_struct *mm, unsigned long addr){	return FUTEX_NO_NODE;} #endif /* CONFIG_FUTEX_MPOL */ /** * __futex_hash - Return the hash bucket * @key:	Pointer to the futex key for which the hash is calculated * @fph:	Pointer to private hash if known * @fph_p:	Pointer to a private hash pointer; output for the private hash *              used when set. * * We hash on the keys returned from get_futex_key (see below) and return the * corresponding hash bucket. * If the FUTEX is PROCESS_PRIVATE then a per-process hash bucket (from the * private hash) is returned if existing. Otherwise a hash bucket from the * global hash is returned. */static struct futex_hash_bucket *__futex_hash(union futex_key *key, struct futex_private_hash *fph, struct futex_private_hash **fph_p){	int node = key->both.node;	u32 hash; #ifdef CONFIG_FUTEX_PRIVATE_HASH	if (node == FUTEX_NO_NODE && futex_key_is_private(key)) {		if (!fph)			fph = rcu_dereference(key->private.mm->futex.phash.hash);		if (fph && fph->hash_mask) {			if (fph_p)				*fph_p = fph;			return __futex_hash_private(key, fph);		}	}#endif 	hash = jhash2((u32 *)key, offsetof(typeof(*key), both.offset) / sizeof(u32),		      key->both.offset); 	if (node == FUTEX_NO_NODE) {		/*		 * In case of !FLAGS_NUMA, use some unused hash bits to pick a		 * node -- this ensures regular futexes are interleaved across		 * the nodes and avoids having to allocate multiple		 * hash-tables.		 *		 * NOTE: this isn't perfectly uniform, but it is fast and		 * handles sparse node masks.		 */		node = (hash >> futex_hashshift) % nr_node_ids;		if (!node_possible(node)) {			node = find_next_bit_wrap(node_possible_map.bits, nr_node_ids, node);		}	} 	return &futex_queues[node][hash & futex_hashmask];} /** * 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 offset within mapping, 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.

Lines 1–500 of 2049. Load more