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.
40 #include <linux/fault-inject.h>
99 	debugfs_create_bool("ignore-private", mode, dir,  in fail_futex_debugfs()
111  * futex_hash - Return the hash bucket in the global hash
120 			  key->both.offset);  in futex_hash()
122 	return &futex_queues[hash & (futex_hashsize - 1)];  in futex_hash()
127  * futex_setup_timer - set up the sleeping hrtimer.
150 	hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);  in futex_setup_timer()
158  * This relies on u64 not wrapping in the life-time of the machine; which with
169  * It is important that futex_match() will never have a false-positive, esp.
170  * for PI futexes that can mess up the state. The above argues that false-negatives
179 	old = atomic64_read(&inode->i_sequence);  in get_inode_sequence_number()
189 		if (!atomic64_try_cmpxchg_relaxed(&inode->i_sequence, &old, new))  in get_inode_sequence_number()
196  * get_futex_key() - Get parameters which are the keys for a futex
209  *   ( inode->i_sequence, page->index, offset_within_page )
215  *   ( current->mm, address, 0 )
226 	struct mm_struct *mm = current->mm;  in get_futex_key()
238 	key->both.offset = address % PAGE_SIZE;  in get_futex_key()
240 		return -EINVAL;  in get_futex_key()
241 	address -= key->both.offset;  in get_futex_key()
244 		return -EFAULT;  in get_futex_key()
247 		return -EFAULT;  in get_futex_key()
258 		 * On no-MMU, shared futexes are treated as private, therefore  in get_futex_key()
264 			key->private.mm = mm;  in get_futex_key()
266 			key->private.mm = NULL;  in get_futex_key()
268 		key->private.address = address;  in get_futex_key()
275 		return -EFAULT;  in get_futex_key()
280 	 * and get read-only access.  in get_futex_key()
282 	if (err == -EFAULT && rw == FUTEX_READ) {  in get_futex_key()
295 	 * file-backed region case and guards against movement to swap cache.  in get_futex_key()
299 	 * From this point on, mapping will be re-verified if necessary and  in get_futex_key()
305 	 * filesystem-backed pages, the precise page is required as the  in get_futex_key()
309 	mapping = READ_ONCE(folio->mapping);  in get_futex_key()
312 	 * If folio->mapping is NULL, then it cannot be an anonymous  in get_futex_key()
324 	 * an unlikely race, but we do need to retry for folio->mapping.  in get_futex_key()
335 		shmem_swizzled = folio_test_swapcache(folio) || folio->mapping;  in get_futex_key()
342 		return -EFAULT;  in get_futex_key()
352 	 * it's a read-only handle, it's expected that futexes attach to  in get_futex_key()
361 			err = -EFAULT;  in get_futex_key()
365 		key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */  in get_futex_key()
366 		key->private.mm = mm;  in get_futex_key()
367 		key->private.address = address;  in get_futex_key()
374 		 * the folio->mapping must be traversed. Ordinarily this should  in get_futex_key()
381 		 * mapping->host can be safely accessed as being a valid inode.  in get_futex_key()
385 		if (READ_ONCE(folio->mapping) != mapping) {  in get_futex_key()
392 		inode = READ_ONCE(mapping->host);  in get_futex_key()
400 		key->both.offset |= FUT_OFF_INODE; /* inode-based key */  in get_futex_key()
401 		key->shared.i_seq = get_inode_sequence_number(inode);  in get_futex_key()
402 		key->shared.pgoff = page_pgoff(folio, page);  in get_futex_key()
412  * fault_in_user_writeable() - Fault in user address and verify RW access
418  * We have no generic implementation of a non-destructive write to the
425 	struct mm_struct *mm = current->mm;  in fault_in_user_writeable()
437  * futex_top_waiter() - Return the highest priority waiter on a futex
447 	plist_for_each_entry(this, &hb->chain, list) {  in futex_top_waiter()
448 		if (futex_match(&this->key, key))  in futex_top_waiter()
455  * wait_for_owner_exiting - Block until the owner has exited
463 	if (ret != -EBUSY) {  in wait_for_owner_exiting()
468 	if (WARN_ON_ONCE(ret == -EBUSY && !exiting))  in wait_for_owner_exiting()
471 	mutex_lock(&exiting->futex_exit_mutex);  in wait_for_owner_exiting()
474 	 * while the task was in exec()->exec_futex_release() then it can  in wait_for_owner_exiting()
480 	mutex_unlock(&exiting->futex_exit_mutex);  in wait_for_owner_exiting()
486  * __futex_unqueue() - Remove the futex_q from its futex_hash_bucket
489  * The q->lock_ptr must not be NULL and must be held by the caller.
495 	if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list)))  in __futex_unqueue()
497 	lockdep_assert_held(q->lock_ptr);  in __futex_unqueue()
499 	hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);  in __futex_unqueue()
500 	plist_del(&q->list, &hb->chain);  in __futex_unqueue()
504 /* The key must be already stored in q->key. */
506 	__acquires(&hb->lock)  in futex_q_lock()
510 	hb = futex_hash(&q->key);  in futex_q_lock()
514 	 * a potential waker won't miss a to-be-slept task that is  in futex_q_lock()
522 	q->lock_ptr = &hb->lock;  in futex_q_lock()
524 	spin_lock(&hb->lock);  in futex_q_lock()
529 	__releases(&hb->lock)  in futex_q_unlock()
531 	spin_unlock(&hb->lock);  in futex_q_unlock()
542 	 * - either the real thread-priority for the real-time threads  in __futex_queue()
544 	 * - or MAX_RT_PRIO for non-RT threads.  in __futex_queue()
545 	 * Thus, all RT-threads are woken first in priority order, and  in __futex_queue()
548 	prio = min(current->normal_prio, MAX_RT_PRIO);  in __futex_queue()
550 	plist_node_init(&q->list, prio);  in __futex_queue()
551 	plist_add(&q->list, &hb->chain);  in __futex_queue()
552 	q->task = task;  in __futex_queue()
556  * futex_unqueue() - Remove the futex_q from its futex_hash_bucket
559  * The q->lock_ptr must not be held by the caller. A call to futex_unqueue() must
563  *  - 1 - if the futex_q was still queued (and we removed unqueued it);
564  *  - 0 - if the futex_q was already removed by the waking thread
574 	 * q->lock_ptr can change between this read and the following spin_lock.  in futex_unqueue()
575 	 * Use READ_ONCE to forbid the compiler from reloading q->lock_ptr and  in futex_unqueue()
578 	lock_ptr = READ_ONCE(q->lock_ptr);  in futex_unqueue()
582 		 * q->lock_ptr can change between reading it and  in futex_unqueue()
587 		 * q->lock_ptr must have changed (maybe several times)  in futex_unqueue()
594 		if (unlikely(lock_ptr != q->lock_ptr)) {  in futex_unqueue()
600 		BUG_ON(q->pi_state);  in futex_unqueue()
623 	if (!plist_node_empty(&q->list))  in futex_unqueue_pi()
626 	BUG_ON(!q->pi_state);  in futex_unqueue_pi()
627 	put_pi_state(q->pi_state);  in futex_unqueue_pi()
628 	q->pi_state = NULL;  in futex_unqueue_pi()
636  * Process a futex-list entry, check whether it's owned by the
648 		return -1;  in handle_futex_death()
652 		return -1;  in handle_futex_death()
670 	 * potential waiters which can cause these waiters to block  in handle_futex_death()
675 	 *	1) task->robust_list->list_op_pending != NULL  in handle_futex_death()
706 	 * futex_wake() even if OWNER_DIED is already set -  in handle_futex_death()
708 	 * thread-death.) The rest of the cleanup is done in  in handle_futex_death()
724 		case -EFAULT:  in handle_futex_death()
726 				return -1;  in handle_futex_death()
729 		case -EAGAIN:  in handle_futex_death()
743 	 * Wake robust non-PI futexes here. The wakeup of  in handle_futex_death()
755  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
764 		return -EFAULT;  in fetch_robust_entry()
773  * Walk curr->robust_list (very carefully, it's a userspace list!)
776  * We silently return on any sign of list-walking problem.
780 	struct robust_list_head __user *head = curr->robust_list;  in exit_robust_list()
788 	 * Fetch the list head (which was registered earlier, via  in exit_robust_list()
791 	if (fetch_robust_entry(&entry, &head->list.next, &pi))  in exit_robust_list()
794 	 * Fetch the relative futex offset:  in exit_robust_list()
796 	if (get_user(futex_offset, &head->futex_offset))  in exit_robust_list()
799 	 * Fetch any possibly pending lock-add first, and handle it  in exit_robust_list()
802 	if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))  in exit_robust_list()
806 	while (entry != &head->list) {  in exit_robust_list()
808 		 * Fetch the next entry in the list before calling  in exit_robust_list()
811 		rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);  in exit_robust_list()
828 		if (!--limit)  in exit_robust_list()
851  * Fetch a robust-list pointer. Bit 0 signals PI futexes:
858 		return -EFAULT;  in compat_fetch_robust_entry()
867  * Walk curr->robust_list (very carefully, it's a userspace list!)
870  * We silently return on any sign of list-walking problem.
874 	struct compat_robust_list_head __user *head = curr->compat_robust_list;  in compat_exit_robust_list()
883 	 * Fetch the list head (which was registered earlier, via  in compat_exit_robust_list()
886 	if (compat_fetch_robust_entry(&uentry, &entry, &head->list.next, &pi))  in compat_exit_robust_list()
889 	 * Fetch the relative futex offset:  in compat_exit_robust_list()
891 	if (get_user(futex_offset, &head->futex_offset))  in compat_exit_robust_list()
894 	 * Fetch any possibly pending lock-add first, and handle it  in compat_exit_robust_list()
898 			       &head->list_op_pending, &pip))  in compat_exit_robust_list()
902 	while (entry != (struct robust_list __user *) &head->list) {  in compat_exit_robust_list()
904 		 * Fetch the next entry in the list before calling  in compat_exit_robust_list()
908 			(compat_uptr_t __user *)&entry->next, &next_pi);  in compat_exit_robust_list()
928 		if (!--limit)  in compat_exit_robust_list()
945  * Kernel cleans up PI-state, but userspace is likely hosed.
946  * (Robust-futex cleanup is separate and might save the day for userspace.)
950 	struct list_head *next, *head = &curr->pi_state_list;  in exit_pi_state_list()
960 	raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
962 		next = head->next;  in exit_pi_state_list()
964 		key = pi_state->key;  in exit_pi_state_list()
977 		if (!refcount_inc_not_zero(&pi_state->refcount)) {  in exit_pi_state_list()
978 			raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
980 			raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
983 		raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
985 		spin_lock(&hb->lock);  in exit_pi_state_list()
986 		raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
987 		raw_spin_lock(&curr->pi_lock);  in exit_pi_state_list()
989 		 * We dropped the pi-lock, so re-check whether this  in exit_pi_state_list()
990 		 * task still owns the PI-state:  in exit_pi_state_list()
992 		if (head->next != next) {  in exit_pi_state_list()
993 			/* retain curr->pi_lock for the loop invariant */  in exit_pi_state_list()
994 			raw_spin_unlock(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
995 			spin_unlock(&hb->lock);  in exit_pi_state_list()
1000 		WARN_ON(pi_state->owner != curr);  in exit_pi_state_list()
1001 		WARN_ON(list_empty(&pi_state->list));  in exit_pi_state_list()
1002 		list_del_init(&pi_state->list);  in exit_pi_state_list()
1003 		pi_state->owner = NULL;  in exit_pi_state_list()
1005 		raw_spin_unlock(&curr->pi_lock);  in exit_pi_state_list()
1006 		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);  in exit_pi_state_list()
1007 		spin_unlock(&hb->lock);  in exit_pi_state_list()
1009 		rt_mutex_futex_unlock(&pi_state->pi_mutex);  in exit_pi_state_list()
1012 		raw_spin_lock_irq(&curr->pi_lock);  in exit_pi_state_list()
1014 	raw_spin_unlock_irq(&curr->pi_lock);  in exit_pi_state_list()
1022 	if (unlikely(tsk->robust_list)) {  in futex_cleanup()
1024 		tsk->robust_list = NULL;  in futex_cleanup()
1028 	if (unlikely(tsk->compat_robust_list)) {  in futex_cleanup()
1030 		tsk->compat_robust_list = NULL;  in futex_cleanup()
1034 	if (unlikely(!list_empty(&tsk->pi_state_list)))  in futex_cleanup()
1039  * futex_exit_recursive - Set the tasks futex state to FUTEX_STATE_DEAD
1053  * block forever, but there is nothing which can be done about that.
1058 	if (tsk->futex_state == FUTEX_STATE_EXITING)  in futex_exit_recursive()
1059 		mutex_unlock(&tsk->futex_exit_mutex);  in futex_exit_recursive()
1060 	tsk->futex_state = FUTEX_STATE_DEAD;  in futex_exit_recursive()
1067 	 * including live locks by forcing the waiter to block on  in futex_cleanup_begin()
1068 	 * tsk->futex_exit_mutex when it observes FUTEX_STATE_EXITING in  in futex_cleanup_begin()
1071 	mutex_lock(&tsk->futex_exit_mutex);  in futex_cleanup_begin()
1074 	 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_lock.  in futex_cleanup_begin()
1076 	 * This ensures that all subsequent checks of tsk->futex_state in  in futex_cleanup_begin()
1078 	 * tsk->pi_lock held.  in futex_cleanup_begin()
1081 	 * the state change under tsk->pi_lock by a concurrent waiter must  in futex_cleanup_begin()
1084 	raw_spin_lock_irq(&tsk->pi_lock);  in futex_cleanup_begin()
1085 	tsk->futex_state = FUTEX_STATE_EXITING;  in futex_cleanup_begin()
1086 	raw_spin_unlock_irq(&tsk->pi_lock);  in futex_cleanup_begin()
1095 	tsk->futex_state = state;  in futex_cleanup_end()
1100 	mutex_unlock(&tsk->futex_exit_mutex);  in futex_cleanup_end()