1 // SPDX-License-Identifier: GPL-2.0-or-later
25  * On the waiter side:
26  *   Q_REQUEUE_PI_NONE		-> Q_REQUEUE_PI_IGNORE
27  *   Q_REQUEUE_PI_IN_PROGRESS	-> Q_REQUEUE_PI_WAIT
29  * On the requeue side:
30  *   Q_REQUEUE_PI_NONE		-> Q_REQUEUE_PI_INPROGRESS
31  *   Q_REQUEUE_PI_IN_PROGRESS	-> Q_REQUEUE_PI_DONE/LOCKED
32  *   Q_REQUEUE_PI_IN_PROGRESS	-> Q_REQUEUE_PI_NONE (requeue failed)
33  *   Q_REQUEUE_PI_WAIT		-> Q_REQUEUE_PI_DONE/LOCKED
34  *   Q_REQUEUE_PI_WAIT		-> Q_REQUEUE_PI_IGNORE (requeue failed)
36  * The requeue side ignores a waiter with state Q_REQUEUE_PI_IGNORE as this
40  * The waiter side signals early wakeup to the requeue side either through
45  * to wait for the requeue side to change the state. Either to DONE/LOCKED
48  * the requeue side when the requeue attempt failed via deadlock detection
69  * requeue_futex() - Requeue a futex_q from one hb to another
84 	if (likely(&hb1->chain != &hb2->chain)) {  in requeue_futex()
85 		plist_del(&q->list, &hb1->chain);  in requeue_futex()
88 		plist_add(&q->list, &hb2->chain);  in requeue_futex()
89 		q->lock_ptr = &hb2->lock;  in requeue_futex()
96 	q->key = *key2;  in requeue_futex()
109 	old = atomic_read_acquire(&q->requeue_state);  in futex_requeue_pi_prepare()
126 	} while (!atomic_try_cmpxchg(&q->requeue_state, &old, new));  in futex_requeue_pi_prepare()
128 	q->pi_state = pi_state;  in futex_requeue_pi_prepare()
136 	old = atomic_read_acquire(&q->requeue_state);  in futex_requeue_pi_complete()
154 	} while (!atomic_try_cmpxchg(&q->requeue_state, &old, new));  in futex_requeue_pi_complete()
159 		rcuwait_wake_up(&q->requeue_wait);  in futex_requeue_pi_complete()
167 	old = atomic_read_acquire(&q->requeue_state);  in futex_requeue_pi_wakeup_sync()
180 	} while (!atomic_try_cmpxchg(&q->requeue_state, &old, new));  in futex_requeue_pi_wakeup_sync()
185 		rcuwait_wait_event(&q->requeue_wait,  in futex_requeue_pi_wakeup_sync()
186 				   atomic_read(&q->requeue_state) != Q_REQUEUE_PI_WAIT,  in futex_requeue_pi_wakeup_sync()
189 		(void)atomic_cond_read_relaxed(&q->requeue_state, VAL != Q_REQUEUE_PI_WAIT);  in futex_requeue_pi_wakeup_sync()
196 	 * will modify q->requeue_state after this point.  in futex_requeue_pi_wakeup_sync()
198 	return atomic_read(&q->requeue_state);  in futex_requeue_pi_wakeup_sync()
202  * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
218  * 4) Set the q->lock_ptr to the requeue target hb->lock for the case that
227  * Must be called with both q->lock_ptr and hb->lock held.
235 	q->key = *key;  in requeue_pi_wake_futex()
238 	WARN_ON(!q->rt_waiter);  in requeue_pi_wake_futex()
239 	q->rt_waiter = NULL;  in requeue_pi_wake_futex()
245 	q->drop_hb_ref = true;  in requeue_pi_wake_futex()
246 	q->lock_ptr = &hb->lock;  in requeue_pi_wake_futex()
247 	task = READ_ONCE(q->task);  in requeue_pi_wake_futex()
255  * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter
256  * @pifutex:		the user address of the to futex
271  * @exiting is only set when the return value is -EBUSY. If so, this holds
276  *  -  0 - failed to acquire the lock atomically;
277  *  - >0 - acquired the lock, return value is vpid of the top_waiter
278  *  - <0 - error
291 		return -EFAULT;  in futex_proxy_trylock_atomic()
294 		return -EFAULT;  in futex_proxy_trylock_atomic()
314 	if (!top_waiter->rt_waiter || top_waiter->pi_state)  in futex_proxy_trylock_atomic()
315 		return -EINVAL;  in futex_proxy_trylock_atomic()
318 	if (!futex_match(top_waiter->requeue_pi_key, key2))  in futex_proxy_trylock_atomic()
319 		return -EINVAL;  in futex_proxy_trylock_atomic()
323 		plist_del(&top_waiter->list, &hb1->chain);  in futex_proxy_trylock_atomic()
325 		return -EAGAIN;  in futex_proxy_trylock_atomic()
333 	 * the user space lock can be acquired then PI state is attached to  in futex_proxy_trylock_atomic()
334 	 * the new owner (@top_waiter->task) when @set_waiters is true.  in futex_proxy_trylock_atomic()
336 	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,  in futex_proxy_trylock_atomic()
340 		 * Lock was acquired in user space and PI state was  in futex_proxy_trylock_atomic()
341 		 * attached to @top_waiter->task. That means state is fully  in futex_proxy_trylock_atomic()
342 		 * consistent and the waiter can return to user space  in futex_proxy_trylock_atomic()
351 		 * futex_lock_pi_atomic() did not acquire the user space  in futex_proxy_trylock_atomic()
364  * futex_requeue() - Requeue waiters from uaddr1 to uaddr2
365  * @uaddr1:	source futex user address
367  * @uaddr2:	target futex user address
370  * @nr_requeue:	number of waiters to requeue (0-INT_MAX)
372  * @requeue_pi:	if we are attempting to requeue from a non-pi futex to a
379  *  - >=0 - on success, the number of tasks requeued or woken;
380  *  -  <0 - on error
393 		return -EINVAL;  in futex_requeue()
396 	 * When PI not supported: return -ENOSYS if requeue_pi is true,  in futex_requeue()
402 		return -ENOSYS;  in futex_requeue()
410 			return -EINVAL;  in futex_requeue()
420 		 * return to user space without further action. A secondary  in futex_requeue()
434 			return -EINVAL;  in futex_requeue()
441 			return -ENOMEM;  in futex_requeue()
458 		return -EINVAL;  in futex_requeue()
487 				ret = -EAGAIN;  in futex_requeue()
515 			 *  - If the lock was acquired atomically (ret == 1), then  in futex_requeue()
519 			 *    return to user space immediately. The kernel/user  in futex_requeue()
521 			 *    more waiters requeued the WAITERS bit in the user  in futex_requeue()
528 			 *  - If the trylock failed with an error (ret < 0) then  in futex_requeue()
533 			 *  - If the trylock did not succeed (ret == 0) then the  in futex_requeue()
548 				 * futex_proxy_trylock_atomic() acquired the user space  in futex_requeue()
559 			case -EFAULT:  in futex_requeue()
566 			case -EBUSY:  in futex_requeue()
567 			case -EAGAIN:  in futex_requeue()
570 				 * - EBUSY: Owner is exiting and we just wait for the  in futex_requeue()
572 				 * - EAGAIN: The user space value changed.  in futex_requeue()
589 		plist_for_each_entry_safe(this, next, &hb1->chain, list) {  in futex_requeue()
590 			if (task_count - nr_wake >= nr_requeue)  in futex_requeue()
593 			if (!futex_match(&this->key, &key1))  in futex_requeue()
603 			if ((requeue_pi && !this->rt_waiter) ||  in futex_requeue()
604 			    (!requeue_pi && this->rt_waiter) ||  in futex_requeue()
605 			    this->pi_state) {  in futex_requeue()
606 				ret = -EINVAL;  in futex_requeue()
613 					this->wake(&wake_q, this);  in futex_requeue()
620 			if (!futex_match(this->requeue_pi_key, &key2)) {  in futex_requeue()
621 				ret = -EINVAL;  in futex_requeue()
640 				 * next waiter. @this->pi_state is still NULL.  in futex_requeue()
646 			ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,  in futex_requeue()
647 							this->rt_waiter,  in futex_requeue()
648 							this->task);  in futex_requeue()
653 				 * on pi_state nor clear this->pi_state because the  in futex_requeue()
655 				 * user space value. It will drop the refcount  in futex_requeue()
674 				this->pi_state = NULL;  in futex_requeue()
678 				 * We stop queueing more waiters and let user space  in futex_requeue()
700  * handle_early_requeue_pi_wakeup() - Handle early wakeup on the initial futex
708  *  -EWOULDBLOCK or -ETIMEDOUT or -ERESTARTNOINTR
724 	WARN_ON_ONCE(&hb->lock != q->lock_ptr);  in handle_early_requeue_pi_wakeup()
730 	if (!plist_node_empty(&q->list)) {  in handle_early_requeue_pi_wakeup()
731 		plist_del(&q->list, &hb->chain);  in handle_early_requeue_pi_wakeup()
736 	ret = -EWOULDBLOCK;  in handle_early_requeue_pi_wakeup()
737 	if (timeout && !timeout->task)  in handle_early_requeue_pi_wakeup()
738 		ret = -ETIMEDOUT;  in handle_early_requeue_pi_wakeup()
740 		ret = -ERESTARTNOINTR;  in handle_early_requeue_pi_wakeup()
745  * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2
746  * @uaddr:	the futex we initially wait on (non-pi)
752  * @uaddr2:	the pi futex we will take prior to returning to user-space
762  * via the following--
768  * If 3, cleanup and return -ERESTARTNOINTR.
776  * If 6, return -EWOULDBLOCK (restarting the syscall would do the same).
778  * If 4 or 7, we cleanup and return with -ETIMEDOUT.
781  *  -  0 - On success;
782  *  - <0 - On error
796 		return -ENOSYS;  in futex_wait_requeue_pi()
799 		return -EINVAL;  in futex_wait_requeue_pi()
802 		return -EINVAL;  in futex_wait_requeue_pi()
805 			       current->timer_slack_ns);  in futex_wait_requeue_pi()
822 	 * Prepare to wait on uaddr. On success, it holds hb->lock and q  in futex_wait_requeue_pi()
837 			spin_lock(&hb->lock);  in futex_wait_requeue_pi()
839 			spin_unlock(&hb->lock);  in futex_wait_requeue_pi()
845 		if (q.pi_state && (q.pi_state->owner != current)) {  in futex_wait_requeue_pi()
855 			 * Adjust the return value. It's either -EFAULT or  in futex_wait_requeue_pi()
864 		pi_mutex = &q.pi_state->pi_mutex;  in futex_wait_requeue_pi()
882 		 * acquired the lock, clear -ETIMEDOUT or -EINTR.  in futex_wait_requeue_pi()
890 		if (ret == -EINTR) {  in futex_wait_requeue_pi()
895 			 * the user space "val" changed and return  in futex_wait_requeue_pi()
896 			 * -EWOULDBLOCK.  Save the overhead of the restart  in futex_wait_requeue_pi()
897 			 * and return -EWOULDBLOCK directly.  in futex_wait_requeue_pi()
899 			ret = -EWOULDBLOCK;  in futex_wait_requeue_pi()
913 		hrtimer_cancel(&to->timer);  in futex_wait_requeue_pi()
914 		destroy_hrtimer_on_stack(&to->timer);  in futex_wait_requeue_pi()