1 // SPDX-License-Identifier: GPL-2.0-or-later
16  *  PI-futex support started by Ingo Molnar and Thomas Gleixner
23  *  Requeue-PI support by Darren Hart <dvhltc@us.ibm.com>
29  *  Kirkwood for proof-of-concept implementation.
39 #include <linux/fault-inject.h>
98 	debugfs_create_bool("ignore-private", mode, dir,  in fail_futex_debugfs()
110  * futex_hash - Return the hash bucket in the global hash
111  * @key:	Pointer to the futex key for which the hash is calculated
116 struct futex_hash_bucket *futex_hash(union futex_key *key)  in futex_hash()  argument
118 	u32 hash = jhash2((u32 *)key, offsetof(typeof(*key), both.offset) / 4,  in futex_hash()
119 			  key->both.offset);  in futex_hash()
121 	return &futex_queues[hash & (futex_hashsize - 1)];  in futex_hash()
126  * futex_setup_timer - set up the sleeping hrtimer.
128  * @timeout:	the hrtimer_sleeper structure to be set up
149 	hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);  in futex_setup_timer()
157  * This relies on u64 not wrapping in the life-time of the machine; which with
168  * It is important that futex_match() will never have a false-positive, esp.
169  * for PI futexes that can mess up the state. The above argues that false-negatives
178 	old = atomic64_read(&inode->i_sequence);  in get_inode_sequence_number()
187 		old = atomic64_cmpxchg_relaxed(&inode->i_sequence, 0, new);  in get_inode_sequence_number()
195  * get_futex_key() - Get parameters which are the keys for a futex
198  * @key:	address where result is stored.
204  * The key words are stored in @key on success.
206  * For shared mappings (when @fshared), the key is:
208  *   ( inode->i_sequence, page->index, offset_within_page )
212  * For private mappings (or when !@fshared), the key is:
214  *   ( current->mm, address, 0 )
221 int get_futex_key(u32 __user *uaddr, unsigned int flags, union futex_key *key,  in get_futex_key()  argument
225 	struct mm_struct *mm = current->mm;  in get_futex_key()
237 	key->both.offset = address % PAGE_SIZE;  in get_futex_key()
239 		return -EINVAL;  in get_futex_key()
240 	address -= key->both.offset;  in get_futex_key()
243 		return -EFAULT;  in get_futex_key()
246 		return -EFAULT;  in get_futex_key()
250 	 * As the mm cannot disappear under us and the 'key' only needs  in get_futex_key()
257 		 * On no-MMU, shared futexes are treated as private, therefore  in get_futex_key()
258 		 * we must not include the current process in the key. Since  in get_futex_key()
259 		 * there is only one address space, the address is a unique key  in get_futex_key()
263 			key->private.mm = mm;  in get_futex_key()
265 			key->private.mm = NULL;  in get_futex_key()
267 		key->private.address = address;  in get_futex_key()
274 		return -EFAULT;  in get_futex_key()
279 	 * and get read-only access.  in get_futex_key()
281 	if (err == -EFAULT && rw == FUTEX_READ) {  in get_futex_key()
294 	 * file-backed region case and guards against movement to swap cache.  in get_futex_key()
298 	 * From this point on, mapping will be re-verified if necessary and  in get_futex_key()
301 	 * Mapping checks require the folio so it is looked up now. For  in get_futex_key()
303 	 * in the future as the key is based on the address. For  in get_futex_key()
304 	 * filesystem-backed pages, the precise page is required as the  in get_futex_key()
305 	 * index of the page determines the key.  in get_futex_key()
308 	mapping = READ_ONCE(folio->mapping);  in get_futex_key()
311 	 * If folio->mapping is NULL, then it cannot be an anonymous  in get_futex_key()
323 	 * an unlikely race, but we do need to retry for folio->mapping.  in get_futex_key()
334 		shmem_swizzled = folio_test_swapcache(folio) || folio->mapping;  in get_futex_key()
341 		return -EFAULT;  in get_futex_key()
347 	 * If the futex key is stored in anonymous memory, then the associated  in get_futex_key()
351 	 * it's a read-only handle, it's expected that futexes attach to  in get_futex_key()
360 			err = -EFAULT;  in get_futex_key()
364 		key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */  in get_futex_key()
365 		key->private.mm = mm;  in get_futex_key()
366 		key->private.address = address;  in get_futex_key()
373 		 * the folio->mapping must be traversed. Ordinarily this should  in get_futex_key()
380 		 * mapping->host can be safely accessed as being a valid inode.  in get_futex_key()
384 		if (READ_ONCE(folio->mapping) != mapping) {  in get_futex_key()
391 		inode = READ_ONCE(mapping->host);  in get_futex_key()
399 		key->both.offset |= FUT_OFF_INODE; /* inode-based key */  in get_futex_key()
400 		key->shared.i_seq = get_inode_sequence_number(inode);  in get_futex_key()
401 		key->shared.pgoff = folio->index + folio_page_idx(folio, page);  in get_futex_key()
411  * fault_in_user_writeable() - Fault in user address and verify RW access
417  * We have no generic implementation of a non-destructive write to the
424 	struct mm_struct *mm = current->mm;  in fault_in_user_writeable()
436  * futex_top_waiter() - Return the highest priority waiter on a futex
438  * @key:	the futex key (to distinguish it from other futex futex_q's)
442 struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb, union futex_key *key)  in futex_top_waiter()  argument
446 	plist_for_each_entry(this, &hb->chain, list) {  in futex_top_waiter()
447 		if (futex_match(&this->key, key))  in futex_top_waiter()
472 	return ret ? -EFAULT : 0;  in futex_get_value_locked()
476  * wait_for_owner_exiting - Block until the owner has exited
484 	if (ret != -EBUSY) {  in wait_for_owner_exiting()
489 	if (WARN_ON_ONCE(ret == -EBUSY && !exiting))  in wait_for_owner_exiting()
492 	mutex_lock(&exiting->futex_exit_mutex);  in wait_for_owner_exiting()
495 	 * while the task was in exec()->exec_futex_release() then it can  in wait_for_owner_exiting()
501 	mutex_unlock(&exiting->futex_exit_mutex);  in wait_for_owner_exiting()
507  * __futex_unqueue() - Remove the futex_q from its futex_hash_bucket
510  * The q->lock_ptr must not be NULL and must be held by the caller.
516 	if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list)))  in __futex_unqueue()
518 	lockdep_assert_held(q->lock_ptr);  in __futex_unqueue()
520 	hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);  in __futex_unqueue()
521 	plist_del(&q->list, &hb->chain);  in __futex_unqueue()
525 /* The key must be already stored in q->key. */
527 	__acquires(&hb->lock)  in futex_q_lock()
531 	hb = futex_hash(&q->key);  in futex_q_lock()
535 	 * a potential waker won't miss a to-be-slept task that is  in futex_q_lock()
537 	 * users end up calling futex_queue(). Similarly, for housekeeping,  in futex_q_lock()
539 	 * occurred and we don't end up adding the task to the list.  in futex_q_lock()
543 	q->lock_ptr = &hb->lock;  in futex_q_lock()
545 	spin_lock(&hb->lock);  in futex_q_lock()
550 	__releases(&hb->lock)  in futex_q_unlock()
552 	spin_unlock(&hb->lock);  in futex_q_unlock()
562 	 * - either the real thread-priority for the real-time threads  in __futex_queue()
564 	 * - or MAX_RT_PRIO for non-RT threads.  in __futex_queue()
565 	 * Thus, all RT-threads are woken first in priority order, and  in __futex_queue()
568 	prio = min(current->normal_prio, MAX_RT_PRIO);  in __futex_queue()
570 	plist_node_init(&q->list, prio);  in __futex_queue()
571 	plist_add(&q->list, &hb->chain);  in __futex_queue()
572 	q->task = current;  in __futex_queue()
576  * futex_unqueue() - Remove the futex_q from its futex_hash_bucket
579  * The q->lock_ptr must not be held by the caller. A call to futex_unqueue() must
583  *  - 1 - if the futex_q was still queued (and we removed unqueued it);
584  *  - 0 - if the futex_q was already removed by the waking thread
594 	 * q->lock_ptr can change between this read and the following spin_lock.  in futex_unqueue()
595 	 * Use READ_ONCE to forbid the compiler from reloading q->lock_ptr and  in futex_unqueue()
598 	lock_ptr = READ_ONCE(q->lock_ptr);  in futex_unqueue()
602 		 * q->lock_ptr can change between reading it and  in futex_unqueue()
607 		 * q->lock_ptr must have changed (maybe several times)  in futex_unqueue()
614 		if (unlikely(lock_ptr != q->lock_ptr)) {  in futex_unqueue()
620 		BUG_ON(q->pi_state);  in futex_unqueue()
643 	if (!plist_node_empty(&q->list))  in futex_unqueue_pi()
646 	BUG_ON(!q->pi_state);  in futex_unqueue_pi()
647 	put_pi_state(q->pi_state);  in futex_unqueue_pi()
648 	q->pi_state = NULL;  in futex_unqueue_pi()
656  * Process a futex-list entry, check whether it's owned by the
668 		return -1;  in handle_futex_death()
672 		return -1;  in handle_futex_death()
679 	 *    before it can execute the futex() syscall to wake up  in handle_futex_death()
682 	 * 2. A woken up waiter is killed before it can acquire the  in handle_futex_death()
685 	 * In the second case, the wake up notification could be generated  in handle_futex_death()
695 	 *	1) task->robust_list->list_op_pending != NULL  in handle_futex_death()
700 	 * If these conditions are met, it is safe to attempt waking up a  in handle_futex_death()
725 	 * set, wake up a waiter (if any). (We have to do a  in handle_futex_death()
726 	 * futex_wake() even if OWNER_DIED is already set -  in handle_futex_death()
728 	 * thread-death.) The rest of the cleanup is done in  in handle_futex_death()
740 	 * give up and leave the futex locked.  in handle_futex_death()
744 		case -EFAULT:  in handle_futex_death()
746 				return -1;  in handle_futex_death()
749 		case -EAGAIN:  in handle_futex_death()
763 	 * Wake robust non-PI futexes here. The wakeup of  in handle_futex_death()
775  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
784 		return -EFAULT;  in fetch_robust_entry()
793  * Walk curr->robust_list (very carefully, it's a userspace list!)
796  * We silently return on any sign of list-walking problem.
800 	struct robust_list_head __user *head = curr->robust_list;  in exit_robust_list()
811 	if (fetch_robust_entry(&entry, &head->list.next, &pi))  in exit_robust_list()
816 	if (get_user(futex_offset, &head->futex_offset))  in exit_robust_list()
819 	 * Fetch any possibly pending lock-add first, and handle it  in exit_robust_list()
822 	if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))  in exit_robust_list()
826 	while (entry != &head->list) {  in exit_robust_list()
831 		rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);  in exit_robust_list()
848 		if (!--limit)  in exit_robust_list()
871  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
878 		return -EFAULT;  in compat_fetch_robust_entry()
887  * Walk curr->robust_list (very carefully, it's a userspace list!)
890  * We silently return on any sign of list-walking problem.
894 	struct compat_robust_list_head __user *head = curr->compat_robust_list;  in compat_exit_robust_list()
906 	if (compat_fetch_robust_entry(&uentry, &entry, &head->list.next, &pi))  in compat_exit_robust_list()
911 	if (get_user(futex_offset, &head->futex_offset))  in compat_exit_robust_list()
914 	 * Fetch any possibly pending lock-add first, and handle it  in compat_exit_robust_list()
918 			       &head->list_op_pending, &pip))  in compat_exit_robust_list()
922 	while (entry != (struct robust_list __user *) &head->list) {  in compat_exit_robust_list()
928 			(compat_uptr_t __user *)&entry->next, &next_pi);  in compat_exit_robust_list()
948 		if (!--limit)  in compat_exit_robust_list()
965  * Kernel cleans up PI-state, but userspace is likely hosed.
966  * (Robust-futex cleanup is separate and might save the day for userspace.)
970 	struct list_head *next, *head = &curr->pi_state_list;  in exit_pi_state_list()
973 	union futex_key key = FUTEX_KEY_INIT;  in exit_pi_state_list()  local
980 	raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
982 		next = head->next;  in exit_pi_state_list()
984 		key = pi_state->key;  in exit_pi_state_list()
985 		hb = futex_hash(&key);  in exit_pi_state_list()
997 		if (!refcount_inc_not_zero(&pi_state->refcount)) {  in exit_pi_state_list()
998 			raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
1000 			raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
1003 		raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
1005 		spin_lock(&hb->lock);  in exit_pi_state_list()
1006 		raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
1007 		raw_spin_lock(&curr->pi_lock);  in exit_pi_state_list()
1009 		 * We dropped the pi-lock, so re-check whether this  in exit_pi_state_list()
1010 		 * task still owns the PI-state:  in exit_pi_state_list()
1012 		if (head->next != next) {  in exit_pi_state_list()
1013 			/* retain curr->pi_lock for the loop invariant */  in exit_pi_state_list()
1014 			raw_spin_unlock(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
1015 			spin_unlock(&hb->lock);  in exit_pi_state_list()
1020 		WARN_ON(pi_state->owner != curr);  in exit_pi_state_list()
1021 		WARN_ON(list_empty(&pi_state->list));  in exit_pi_state_list()
1022 		list_del_init(&pi_state->list);  in exit_pi_state_list()
1023 		pi_state->owner = NULL;  in exit_pi_state_list()
1025 		raw_spin_unlock(&curr->pi_lock);  in exit_pi_state_list()
1026 		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
1027 		spin_unlock(&hb->lock);  in exit_pi_state_list()
1029 		rt_mutex_futex_unlock(&pi_state->pi_mutex);  in exit_pi_state_list()
1032 		raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
1034 	raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
1042 	if (unlikely(tsk->robust_list)) {  in futex_cleanup()
1044 		tsk->robust_list = NULL;  in futex_cleanup()
1048 	if (unlikely(tsk->compat_robust_list)) {  in futex_cleanup()
1050 		tsk->compat_robust_list = NULL;  in futex_cleanup()
1054 	if (unlikely(!list_empty(&tsk->pi_state_list)))  in futex_cleanup()
1059  * futex_exit_recursive - Set the tasks futex state to FUTEX_STATE_DEAD
1078 	if (tsk->futex_state == FUTEX_STATE_EXITING)  in futex_exit_recursive()
1079 		mutex_unlock(&tsk->futex_exit_mutex);  in futex_exit_recursive()
1080 	tsk->futex_state = FUTEX_STATE_DEAD;  in futex_exit_recursive()
1088 	 * tsk->futex_exit_mutex when it observes FUTEX_STATE_EXITING in  in futex_cleanup_begin()
1091 	mutex_lock(&tsk->futex_exit_mutex);  in futex_cleanup_begin()
1094 	 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_lock.  in futex_cleanup_begin()
1096 	 * This ensures that all subsequent checks of tsk->futex_state in  in futex_cleanup_begin()
1098 	 * tsk->pi_lock held.  in futex_cleanup_begin()
1101 	 * the state change under tsk->pi_lock by a concurrent waiter must  in futex_cleanup_begin()
1104 	raw_spin_lock_irq(&tsk->pi_lock);  in futex_cleanup_begin()
1105 	tsk->futex_state = FUTEX_STATE_EXITING;  in futex_cleanup_begin()
1106 	raw_spin_unlock_irq(&tsk->pi_lock);  in futex_cleanup_begin()
1115 	tsk->futex_state = state;  in futex_cleanup_end()
1120 	mutex_unlock(&tsk->futex_exit_mutex);  in futex_cleanup_end()