/* *  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 <asm/futex.h> #include "rtmutex_common.h" int __read_mostly futex_cmpxchg_enabled; #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8) /* * Futex flags used to encode options to functions and preserve them across * restarts. */#define FLAGS_SHARED		0x01#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;}; /** * 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_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;}; 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 {	spinlock_t lock;	struct plist_head chain;}; 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 && 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; 	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {	case FUT_OFF_INODE:		ihold(key->shared.inode);		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){	if (!key->both.ptr) {		/* If we're here then we tried to put a key we failed to get */		WARN_ON_ONCE(1);		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) * * Returns a negative error code or 0 * The key words are stored in *key on success. * * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode, * 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){	unsigned long address = (unsigned long)uaddr;	struct mm_struct *mm = current->mm;	struct page *page, *page_head;	int err, ro = 0; 	/*	 * 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; 	/*	 * 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;		get_futex_key_refs(key);		return 0;	} again:	err = get_user_pages_fast(address, 1, 1, &page);	/*	 * If write access is not required (eg. FUTEX_WAIT), try	 * and get read-only access.	 */	if (err == -EFAULT && rw == VERIFY_READ) {		err = get_user_pages_fast(address, 1, 0, &page);		ro = 1;	}	if (err < 0)		return err;	else		err = 0; #ifdef CONFIG_TRANSPARENT_HUGEPAGE	page_head = page;	if (unlikely(PageTail(page))) {		put_page(page);		/* serialize against __split_huge_page_splitting() */		local_irq_disable();		if (likely(__get_user_pages_fast(address, 1, 1, &page) == 1)) {			page_head = compound_head(page);			/*			 * page_head is valid pointer but we must pin			 * it before taking the PG_lock and/or			 * PG_compound_lock. The moment we re-enable			 * irqs __split_huge_page_splitting() can			 * return and the head page can be freed from			 * under us. We can't take the PG_lock and/or			 * PG_compound_lock on a page that could be			 * freed from under us.			 */			if (page != page_head) {				get_page(page_head);				put_page(page);			}			local_irq_enable();		} else {			local_irq_enable();			goto again;		}	}#else	page_head = compound_head(page);	if (page != page_head) {		get_page(page_head);		put_page(page);	}#endif 	lock_page(page_head); 	/*	 * If page_head->mapping is NULL, then it cannot be a PageAnon	 * 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 page lock (also	 * cases which we are happy to fail).  And we hold a reference,	 * so refcount care in invalidate_complete_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 page_head->mapping.	 */	if (!page_head->mapping) {		int shmem_swizzled = PageSwapCache(page_head);		unlock_page(page_head);		put_page(page_head);		if (shmem_swizzled)			goto again;		return -EFAULT;	} 	/*	 * 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	 * the object not the particular process.	 */	if (PageAnon(page_head)) {		/*		 * A RO anonymous page will never change and thus doesn't make		 * sense for futex operations.		 */		if (ro) {			err = -EFAULT;			goto out;		} 		key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */		key->private.mm = mm;		key->private.address = address;	} else {		key->both.offset |= FUT_OFF_INODE; /* inode-based key */		key->shared.inode = page_head->mapping->host;		key->shared.pgoff = page_head->index;	} 	get_futex_key_refs(key); out:	unlock_page(page_head);	put_page(page_head);	return err;} static inline void put_futex_key(union futex_key *key){	drop_futex_key_refs(key);} /** * 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. */static int fault_in_user_writeable(u32 __user *uaddr){	struct mm_struct *mm = current->mm;	int ret; 	down_read(&mm->mmap_sem);	ret = fixup_user_fault(current, mm, (unsigned long)uaddr,			       FAULT_FLAG_WRITE);	up_read(&mm->mmap_sem); 	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. */static 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 (match_futex(&this->key, key))			return this;	}	return NULL;} static int cmpxchg_futex_value_locked(u32 *curval, u32 __user *uaddr,				      u32 uval, u32 newval){	int ret; 	pagefault_disable();	ret = futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);	pagefault_enable(); 	return ret;} static int get_futex_value_locked(u32 *dest, u32 __user *from){	int ret; 	pagefault_disable();	ret = __copy_from_user_inatomic(dest, from, sizeof(u32));	pagefault_enable(); 	return ret ? -EFAULT : 0;}  /* * PI code: */static int refill_pi_state_cache(void){	struct futex_pi_state *pi_state; 	if (likely(current->pi_state_cache))		return 0; 	pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL); 	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);	pi_state->key = FUTEX_KEY_INIT; 	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) {		raw_spin_lock_irq(&pi_state->owner->pi_lock);		list_del_init(&pi_state->list);		raw_spin_unlock_irq(&pi_state->owner->pi_lock); 		rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);

Lines 1–500 of 2735. Load more