1 // SPDX-License-Identifier: GPL-2.0-or-later 2 3 #include <linux/plist.h> 4 #include <linux/sched/signal.h> 5 6 #include "futex.h" 7 #include "../locking/rtmutex_common.h" 8 9 /* 10 * On PREEMPT_RT, the hash bucket lock is a 'sleeping' spinlock with an 11 * underlying rtmutex. The task which is about to be requeued could have 12 * just woken up (timeout, signal). After the wake up the task has to 13 * acquire hash bucket lock, which is held by the requeue code. As a task 14 * can only be blocked on _ONE_ rtmutex at a time, the proxy lock blocking 15 * and the hash bucket lock blocking would collide and corrupt state. 16 * 17 * On !PREEMPT_RT this is not a problem and everything could be serialized 18 * on hash bucket lock, but aside of having the benefit of common code, 19 * this allows to avoid doing the requeue when the task is already on the 20 * way out and taking the hash bucket lock of the original uaddr1 when the 21 * requeue has been completed. 22 * 23 * The following state transitions are valid: 24 * 25 * On the waiter side: 26 * Q_REQUEUE_PI_NONE -> Q_REQUEUE_PI_IGNORE 27 * Q_REQUEUE_PI_IN_PROGRESS -> Q_REQUEUE_PI_WAIT 28 * 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) 35 * 36 * The requeue side ignores a waiter with state Q_REQUEUE_PI_IGNORE as this 37 * signals that the waiter is already on the way out. It also means that 38 * the waiter is still on the 'wait' futex, i.e. uaddr1. 39 * 40 * The waiter side signals early wakeup to the requeue side either through 41 * setting state to Q_REQUEUE_PI_IGNORE or to Q_REQUEUE_PI_WAIT depending 42 * on the current state. In case of Q_REQUEUE_PI_IGNORE it can immediately 43 * proceed to take the hash bucket lock of uaddr1. If it set state to WAIT, 44 * which means the wakeup is interleaving with a requeue in progress it has 45 * to wait for the requeue side to change the state. Either to DONE/LOCKED 46 * or to IGNORE. DONE/LOCKED means the waiter q is now on the uaddr2 futex 47 * and either blocked (DONE) or has acquired it (LOCKED). IGNORE is set by 48 * the requeue side when the requeue attempt failed via deadlock detection 49 * and therefore the waiter q is still on the uaddr1 futex. 50 */ 51 enum { 52 Q_REQUEUE_PI_NONE = 0, 53 Q_REQUEUE_PI_IGNORE, 54 Q_REQUEUE_PI_IN_PROGRESS, 55 Q_REQUEUE_PI_WAIT, 56 Q_REQUEUE_PI_DONE, 57 Q_REQUEUE_PI_LOCKED, 58 }; 59 60 const struct futex_q futex_q_init = { 61 /* list gets initialized in futex_queue()*/ 62 .wake = futex_wake_mark, 63 .key = FUTEX_KEY_INIT, 64 .bitset = FUTEX_BITSET_MATCH_ANY, 65 .requeue_state = ATOMIC_INIT(Q_REQUEUE_PI_NONE), 66 }; 67 68 /** 69 * requeue_futex() - Requeue a futex_q from one hb to another 70 * @q: the futex_q to requeue 71 * @hb1: the source hash_bucket 72 * @hb2: the target hash_bucket 73 * @key2: the new key for the requeued futex_q 74 */ 75 static inline 76 void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1, 77 struct futex_hash_bucket *hb2, union futex_key *key2) 78 { 79 80 /* 81 * If key1 and key2 hash to the same bucket, no need to 82 * requeue. 83 */ 84 if (likely(&hb1->chain != &hb2->chain)) { 85 plist_del(&q->list, &hb1->chain); 86 futex_hb_waiters_dec(hb1); 87 futex_hb_waiters_inc(hb2); 88 plist_add(&q->list, &hb2->chain); 89 q->lock_ptr = &hb2->lock; 90 /* 91 * hb1 and hb2 belong to the same futex_hash_bucket_private 92 * because if we managed get a reference on hb1 then it can't be 93 * replaced. Therefore we avoid put(hb1)+get(hb2) here. 94 */ 95 } 96 q->key = *key2; 97 } 98 99 static inline bool futex_requeue_pi_prepare(struct futex_q *q, 100 struct futex_pi_state *pi_state) 101 { 102 int old, new; 103 104 /* 105 * Set state to Q_REQUEUE_PI_IN_PROGRESS unless an early wakeup has 106 * already set Q_REQUEUE_PI_IGNORE to signal that requeue should 107 * ignore the waiter. 108 */ 109 old = atomic_read_acquire(&q->requeue_state); 110 do { 111 if (old == Q_REQUEUE_PI_IGNORE) 112 return false; 113 114 /* 115 * futex_proxy_trylock_atomic() might have set it to 116 * IN_PROGRESS and a interleaved early wake to WAIT. 117 * 118 * It was considered to have an extra state for that 119 * trylock, but that would just add more conditionals 120 * all over the place for a dubious value. 121 */ 122 if (old != Q_REQUEUE_PI_NONE) 123 break; 124 125 new = Q_REQUEUE_PI_IN_PROGRESS; 126 } while (!atomic_try_cmpxchg(&q->requeue_state, &old, new)); 127 128 q->pi_state = pi_state; 129 return true; 130 } 131 132 static inline void futex_requeue_pi_complete(struct futex_q *q, int locked) 133 { 134 int old, new; 135 136 old = atomic_read_acquire(&q->requeue_state); 137 do { 138 if (old == Q_REQUEUE_PI_IGNORE) 139 return; 140 141 if (locked >= 0) { 142 /* Requeue succeeded. Set DONE or LOCKED */ 143 WARN_ON_ONCE(old != Q_REQUEUE_PI_IN_PROGRESS && 144 old != Q_REQUEUE_PI_WAIT); 145 new = Q_REQUEUE_PI_DONE + locked; 146 } else if (old == Q_REQUEUE_PI_IN_PROGRESS) { 147 /* Deadlock, no early wakeup interleave */ 148 new = Q_REQUEUE_PI_NONE; 149 } else { 150 /* Deadlock, early wakeup interleave. */ 151 WARN_ON_ONCE(old != Q_REQUEUE_PI_WAIT); 152 new = Q_REQUEUE_PI_IGNORE; 153 } 154 } while (!atomic_try_cmpxchg(&q->requeue_state, &old, new)); 155 156 #ifdef CONFIG_PREEMPT_RT 157 /* If the waiter interleaved with the requeue let it know */ 158 if (unlikely(old == Q_REQUEUE_PI_WAIT)) 159 rcuwait_wake_up(&q->requeue_wait); 160 #endif 161 } 162 163 static inline int futex_requeue_pi_wakeup_sync(struct futex_q *q) 164 { 165 int old, new; 166 167 old = atomic_read_acquire(&q->requeue_state); 168 do { 169 /* Is requeue done already? */ 170 if (old >= Q_REQUEUE_PI_DONE) 171 return old; 172 173 /* 174 * If not done, then tell the requeue code to either ignore 175 * the waiter or to wake it up once the requeue is done. 176 */ 177 new = Q_REQUEUE_PI_WAIT; 178 if (old == Q_REQUEUE_PI_NONE) 179 new = Q_REQUEUE_PI_IGNORE; 180 } while (!atomic_try_cmpxchg(&q->requeue_state, &old, new)); 181 182 /* If the requeue was in progress, wait for it to complete */ 183 if (old == Q_REQUEUE_PI_IN_PROGRESS) { 184 #ifdef CONFIG_PREEMPT_RT 185 rcuwait_wait_event(&q->requeue_wait, 186 atomic_read(&q->requeue_state) != Q_REQUEUE_PI_WAIT, 187 TASK_UNINTERRUPTIBLE); 188 #else 189 (void)atomic_cond_read_relaxed(&q->requeue_state, VAL != Q_REQUEUE_PI_WAIT); 190 #endif 191 } 192 193 /* 194 * Requeue is now either prohibited or complete. Reread state 195 * because during the wait above it might have changed. Nothing 196 * will modify q->requeue_state after this point. 197 */ 198 return atomic_read(&q->requeue_state); 199 } 200 201 /** 202 * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue 203 * @q: the futex_q 204 * @key: the key of the requeue target futex 205 * @hb: the hash_bucket of the requeue target futex 206 * 207 * During futex_requeue, with requeue_pi=1, it is possible to acquire the 208 * target futex if it is uncontended or via a lock steal. 209 * 210 * 1) Set @q::key to the requeue target futex key so the waiter can detect 211 * the wakeup on the right futex. 212 * 213 * 2) Dequeue @q from the hash bucket. 214 * 215 * 3) Set @q::rt_waiter to NULL so the woken up task can detect atomic lock 216 * acquisition. 217 * 218 * 4) Set the q->lock_ptr to the requeue target hb->lock for the case that 219 * the waiter has to fixup the pi state. 220 * 221 * 5) Complete the requeue state so the waiter can make progress. After 222 * this point the waiter task can return from the syscall immediately in 223 * case that the pi state does not have to be fixed up. 224 * 225 * 6) Wake the waiter task. 226 * 227 * Must be called with both q->lock_ptr and hb->lock held. 228 */ 229 static inline 230 void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key, 231 struct futex_hash_bucket *hb) 232 { 233 struct task_struct *task; 234 235 q->key = *key; 236 __futex_unqueue(q); 237 238 WARN_ON(!q->rt_waiter); 239 q->rt_waiter = NULL; 240 /* 241 * Acquire a reference for the waiter to ensure valid 242 * futex_q::lock_ptr. 243 */ 244 if (futex_key_is_private(key)) 245 q->drop_fph = futex_private_hash(key->private.mm); 246 q->lock_ptr = &hb->lock; 247 task = READ_ONCE(q->task); 248 249 /* Signal locked state to the waiter */ 250 futex_requeue_pi_complete(q, 1); 251 wake_up_state(task, TASK_NORMAL); 252 } 253 254 /** 255 * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter 256 * @pifutex: the user address of the to futex 257 * @hb1: the from futex hash bucket, must be locked by the caller 258 * @hb2: the to futex hash bucket, must be locked by the caller 259 * @key1: the from futex key 260 * @key2: the to futex key 261 * @ps: address to store the pi_state pointer 262 * @exiting: Pointer to store the task pointer of the owner task 263 * which is in the middle of exiting 264 * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0) 265 * 266 * Try and get the lock on behalf of the top waiter if we can do it atomically. 267 * Wake the top waiter if we succeed. If the caller specified set_waiters, 268 * then direct futex_lock_pi_atomic() to force setting the FUTEX_WAITERS bit. 269 * hb1 and hb2 must be held by the caller. 270 * 271 * @exiting is only set when the return value is -EBUSY. If so, this holds 272 * a refcount on the exiting task on return and the caller needs to drop it 273 * after waiting for the exit to complete. 274 * 275 * Return: 276 * - 0 - failed to acquire the lock atomically; 277 * - >0 - acquired the lock, return value is vpid of the top_waiter 278 * - <0 - error 279 */ 280 static int 281 futex_proxy_trylock_atomic(u32 __user *pifutex, struct futex_hash_bucket *hb1, 282 struct futex_hash_bucket *hb2, union futex_key *key1, 283 union futex_key *key2, struct futex_pi_state **ps, 284 struct task_struct **exiting, int set_waiters) 285 { 286 struct futex_q *top_waiter; 287 u32 curval; 288 int ret; 289 290 if (futex_get_value_locked(&curval, pifutex)) 291 return -EFAULT; 292 293 if (unlikely(should_fail_futex(true))) 294 return -EFAULT; 295 296 /* 297 * Find the top_waiter and determine if there are additional waiters. 298 * If the caller intends to requeue more than 1 waiter to pifutex, 299 * force futex_lock_pi_atomic() to set the FUTEX_WAITERS bit now, 300 * as we have means to handle the possible fault. If not, don't set 301 * the bit unnecessarily as it will force the subsequent unlock to enter 302 * the kernel. 303 */ 304 top_waiter = futex_top_waiter(hb1, key1); 305 306 /* There are no waiters, nothing for us to do. */ 307 if (!top_waiter) 308 return 0; 309 310 /* 311 * Ensure that this is a waiter sitting in futex_wait_requeue_pi() 312 * and waiting on the 'waitqueue' futex which is always !PI. 313 */ 314 if (!top_waiter->rt_waiter || top_waiter->pi_state) 315 return -EINVAL; 316 317 /* Ensure we requeue to the expected futex. */ 318 if (!futex_match(top_waiter->requeue_pi_key, key2)) 319 return -EINVAL; 320 321 /* Ensure that this does not race against an early wakeup */ 322 if (!futex_requeue_pi_prepare(top_waiter, NULL)) { 323 plist_del(&top_waiter->list, &hb1->chain); 324 futex_hb_waiters_dec(hb1); 325 return -EAGAIN; 326 } 327 328 /* 329 * Try to take the lock for top_waiter and set the FUTEX_WAITERS bit 330 * in the contended case or if @set_waiters is true. 331 * 332 * In the contended case PI state is attached to the lock owner. If 333 * the user space lock can be acquired then PI state is attached to 334 * the new owner (@top_waiter->task) when @set_waiters is true. 335 */ 336 ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task, 337 exiting, set_waiters); 338 if (ret == 1) { 339 /* 340 * Lock was acquired in user space and PI state was 341 * attached to @top_waiter->task. That means state is fully 342 * consistent and the waiter can return to user space 343 * immediately after the wakeup. 344 */ 345 requeue_pi_wake_futex(top_waiter, key2, hb2); 346 } else if (ret < 0) { 347 /* Rewind top_waiter::requeue_state */ 348 futex_requeue_pi_complete(top_waiter, ret); 349 } else { 350 /* 351 * futex_lock_pi_atomic() did not acquire the user space 352 * futex, but managed to establish the proxy lock and pi 353 * state. top_waiter::requeue_state cannot be fixed up here 354 * because the waiter is not enqueued on the rtmutex 355 * yet. This is handled at the callsite depending on the 356 * result of rt_mutex_start_proxy_lock() which is 357 * guaranteed to be reached with this function returning 0. 358 */ 359 } 360 return ret; 361 } 362 363 /** 364 * futex_requeue() - Requeue waiters from uaddr1 to uaddr2 365 * @uaddr1: source futex user address 366 * @flags1: futex flags (FLAGS_SHARED, etc.) 367 * @uaddr2: target futex user address 368 * @flags2: futex flags (FLAGS_SHARED, etc.) 369 * @nr_wake: number of waiters to wake (must be 1 for requeue_pi) 370 * @nr_requeue: number of waiters to requeue (0-INT_MAX) 371 * @cmpval: @uaddr1 expected value (or %NULL) 372 * @requeue_pi: if we are attempting to requeue from a non-pi futex to a 373 * pi futex (pi to pi requeue is not supported) 374 * 375 * Requeue waiters on uaddr1 to uaddr2. In the requeue_pi case, try to acquire 376 * uaddr2 atomically on behalf of the top waiter. 377 * 378 * Return: 379 * - >=0 - on success, the number of tasks requeued or woken; 380 * - <0 - on error 381 */ 382 int futex_requeue(u32 __user *uaddr1, unsigned int flags1, 383 u32 __user *uaddr2, unsigned int flags2, 384 int nr_wake, int nr_requeue, u32 *cmpval, int requeue_pi) 385 { 386 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT; 387 int task_count = 0, ret; 388 struct futex_pi_state *pi_state = NULL; 389 struct futex_q *this, *next; 390 DEFINE_WAKE_Q(wake_q); 391 392 if (nr_wake < 0 || nr_requeue < 0) 393 return -EINVAL; 394 395 /* 396 * When PI not supported: return -ENOSYS if requeue_pi is true, 397 * consequently the compiler knows requeue_pi is always false past 398 * this point which will optimize away all the conditional code 399 * further down. 400 */ 401 if (!IS_ENABLED(CONFIG_FUTEX_PI) && requeue_pi) 402 return -ENOSYS; 403 404 if (requeue_pi) { 405 /* 406 * Requeue PI only works on two distinct uaddrs. This 407 * check is only valid for private futexes. See below. 408 */ 409 if (uaddr1 == uaddr2) 410 return -EINVAL; 411 412 /* 413 * futex_requeue() allows the caller to define the number 414 * of waiters to wake up via the @nr_wake argument. With 415 * REQUEUE_PI, waking up more than one waiter is creating 416 * more problems than it solves. Waking up a waiter makes 417 * only sense if the PI futex @uaddr2 is uncontended as 418 * this allows the requeue code to acquire the futex 419 * @uaddr2 before waking the waiter. The waiter can then 420 * return to user space without further action. A secondary 421 * wakeup would just make the futex_wait_requeue_pi() 422 * handling more complex, because that code would have to 423 * look up pi_state and do more or less all the handling 424 * which the requeue code has to do for the to be requeued 425 * waiters. So restrict the number of waiters to wake to 426 * one, and only wake it up when the PI futex is 427 * uncontended. Otherwise requeue it and let the unlock of 428 * the PI futex handle the wakeup. 429 * 430 * All REQUEUE_PI users, e.g. pthread_cond_signal() and 431 * pthread_cond_broadcast() must use nr_wake=1. 432 */ 433 if (nr_wake != 1) 434 return -EINVAL; 435 436 /* 437 * requeue_pi requires a pi_state, try to allocate it now 438 * without any locks in case it fails. 439 */ 440 if (refill_pi_state_cache()) 441 return -ENOMEM; 442 } 443 444 retry: 445 ret = get_futex_key(uaddr1, flags1, &key1, FUTEX_READ); 446 if (unlikely(ret != 0)) 447 return ret; 448 ret = get_futex_key(uaddr2, flags2, &key2, 449 requeue_pi ? FUTEX_WRITE : FUTEX_READ); 450 if (unlikely(ret != 0)) 451 return ret; 452 453 /* 454 * The check above which compares uaddrs is not sufficient for 455 * shared futexes. We need to compare the keys: 456 */ 457 if (requeue_pi && futex_match(&key1, &key2)) 458 return -EINVAL; 459 460 retry_private: 461 if (1) { 462 CLASS(hbr, hbr1)(&key1); 463 CLASS(hbr, hbr2)(&key2); 464 auto hb1 = hbr1.hb; 465 auto hb2 = hbr2.hb; 466 467 futex_hb_waiters_inc(hb2); 468 double_lock_hb(hb1, hb2); 469 470 if (likely(cmpval != NULL)) { 471 u32 curval; 472 473 ret = futex_get_value_locked(&curval, uaddr1); 474 475 if (unlikely(ret)) { 476 futex_hb_waiters_dec(hb2); 477 double_unlock_hb(hb1, hb2); 478 479 ret = get_user(curval, uaddr1); 480 if (ret) 481 return ret; 482 483 if (!(flags1 & FLAGS_SHARED)) 484 goto retry_private; 485 486 goto retry; 487 } 488 if (curval != *cmpval) { 489 ret = -EAGAIN; 490 goto out_unlock; 491 } 492 } 493 494 if (requeue_pi) { 495 struct task_struct *exiting = NULL; 496 497 /* 498 * Attempt to acquire uaddr2 and wake the top waiter. If we 499 * intend to requeue waiters, force setting the FUTEX_WAITERS 500 * bit. We force this here where we are able to easily handle 501 * faults rather in the requeue loop below. 502 * 503 * Updates topwaiter::requeue_state if a top waiter exists. 504 */ 505 ret = futex_proxy_trylock_atomic(uaddr2, hb1, hb2, &key1, 506 &key2, &pi_state, 507 &exiting, nr_requeue); 508 509 /* 510 * At this point the top_waiter has either taken uaddr2 or 511 * is waiting on it. In both cases pi_state has been 512 * established and an initial refcount on it. In case of an 513 * error there's nothing. 514 * 515 * The top waiter's requeue_state is up to date: 516 * 517 * - If the lock was acquired atomically (ret == 1), then 518 * the state is Q_REQUEUE_PI_LOCKED. 519 * 520 * The top waiter has been dequeued and woken up and can 521 * return to user space immediately. The kernel/user 522 * space state is consistent. In case that there must be 523 * more waiters requeued the WAITERS bit in the user 524 * space futex is set so the top waiter task has to go 525 * into the syscall slowpath to unlock the futex. This 526 * will block until this requeue operation has been 527 * completed and the hash bucket locks have been 528 * dropped. 529 * 530 * - If the trylock failed with an error (ret < 0) then 531 * the state is either Q_REQUEUE_PI_NONE, i.e. "nothing 532 * happened", or Q_REQUEUE_PI_IGNORE when there was an 533 * interleaved early wakeup. 534 * 535 * - If the trylock did not succeed (ret == 0) then the 536 * state is either Q_REQUEUE_PI_IN_PROGRESS or 537 * Q_REQUEUE_PI_WAIT if an early wakeup interleaved. 538 * This will be cleaned up in the loop below, which 539 * cannot fail because futex_proxy_trylock_atomic() did 540 * the same sanity checks for requeue_pi as the loop 541 * below does. 542 */ 543 switch (ret) { 544 case 0: 545 /* We hold a reference on the pi state. */ 546 break; 547 548 case 1: 549 /* 550 * futex_proxy_trylock_atomic() acquired the user space 551 * futex. Adjust task_count. 552 */ 553 task_count++; 554 ret = 0; 555 break; 556 557 /* 558 * If the above failed, then pi_state is NULL and 559 * waiter::requeue_state is correct. 560 */ 561 case -EFAULT: 562 futex_hb_waiters_dec(hb2); 563 double_unlock_hb(hb1, hb2); 564 ret = fault_in_user_writeable(uaddr2); 565 if (!ret) 566 goto retry; 567 return ret; 568 case -EBUSY: 569 case -EAGAIN: 570 /* 571 * Two reasons for this: 572 * - EBUSY: Owner is exiting and we just wait for the 573 * exit to complete. 574 * - EAGAIN: The user space value changed. 575 */ 576 futex_hb_waiters_dec(hb2); 577 double_unlock_hb(hb1, hb2); 578 /* 579 * Handle the case where the owner is in the middle of 580 * exiting. Wait for the exit to complete otherwise 581 * this task might loop forever, aka. live lock. 582 */ 583 wait_for_owner_exiting(ret, exiting); 584 cond_resched(); 585 goto retry; 586 default: 587 goto out_unlock; 588 } 589 } 590 591 plist_for_each_entry_safe(this, next, &hb1->chain, list) { 592 if (task_count - nr_wake >= nr_requeue) 593 break; 594 595 if (!futex_match(&this->key, &key1)) 596 continue; 597 598 /* 599 * FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI should always 600 * be paired with each other and no other futex ops. 601 * 602 * We should never be requeueing a futex_q with a pi_state, 603 * which is awaiting a futex_unlock_pi(). 604 */ 605 if ((requeue_pi && !this->rt_waiter) || 606 (!requeue_pi && this->rt_waiter) || 607 this->pi_state) { 608 ret = -EINVAL; 609 break; 610 } 611 612 /* Plain futexes just wake or requeue and are done */ 613 if (!requeue_pi) { 614 if (++task_count <= nr_wake) 615 this->wake(&wake_q, this); 616 else 617 requeue_futex(this, hb1, hb2, &key2); 618 continue; 619 } 620 621 /* Ensure we requeue to the expected futex for requeue_pi. */ 622 if (!futex_match(this->requeue_pi_key, &key2)) { 623 ret = -EINVAL; 624 break; 625 } 626 627 /* 628 * Requeue nr_requeue waiters and possibly one more in the case 629 * of requeue_pi if we couldn't acquire the lock atomically. 630 * 631 * Prepare the waiter to take the rt_mutex. Take a refcount 632 * on the pi_state and store the pointer in the futex_q 633 * object of the waiter. 634 */ 635 get_pi_state(pi_state); 636 637 /* Don't requeue when the waiter is already on the way out. */ 638 if (!futex_requeue_pi_prepare(this, pi_state)) { 639 /* 640 * Early woken waiter signaled that it is on the 641 * way out. Drop the pi_state reference and try the 642 * next waiter. @this->pi_state is still NULL. 643 */ 644 put_pi_state(pi_state); 645 continue; 646 } 647 648 /* Self-deadlock: non-top waiter already owns the PI futex. */ 649 if (rt_mutex_owner(&pi_state->pi_mutex) == this->task) { 650 ret = -EDEADLK; 651 break; 652 } 653 654 ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex, 655 this->rt_waiter, 656 this->task); 657 658 if (ret == 1) { 659 /* 660 * We got the lock. We do neither drop the refcount 661 * on pi_state nor clear this->pi_state because the 662 * waiter needs the pi_state for cleaning up the 663 * user space value. It will drop the refcount 664 * after doing so. this::requeue_state is updated 665 * in the wakeup as well. 666 */ 667 requeue_pi_wake_futex(this, &key2, hb2); 668 task_count++; 669 } else if (!ret) { 670 /* Waiter is queued, move it to hb2 */ 671 requeue_futex(this, hb1, hb2, &key2); 672 futex_requeue_pi_complete(this, 0); 673 task_count++; 674 } else { 675 /* 676 * rt_mutex_start_proxy_lock() detected a potential 677 * deadlock when we tried to queue that waiter. 678 * Drop the pi_state reference which we took above 679 * and remove the pointer to the state from the 680 * waiters futex_q object. 681 */ 682 this->pi_state = NULL; 683 put_pi_state(pi_state); 684 futex_requeue_pi_complete(this, ret); 685 /* 686 * We stop queueing more waiters and let user space 687 * deal with the mess. 688 */ 689 break; 690 } 691 } 692 693 /* 694 * We took an extra initial reference to the pi_state in 695 * futex_proxy_trylock_atomic(). We need to drop it here again. 696 */ 697 put_pi_state(pi_state); 698 699 out_unlock: 700 futex_hb_waiters_dec(hb2); 701 double_unlock_hb(hb1, hb2); 702 } 703 wake_up_q(&wake_q); 704 return ret ? ret : task_count; 705 } 706 707 /** 708 * handle_early_requeue_pi_wakeup() - Handle early wakeup on the initial futex 709 * @hb: the hash_bucket futex_q was original enqueued on 710 * @q: the futex_q woken while waiting to be requeued 711 * @timeout: the timeout associated with the wait (NULL if none) 712 * 713 * Determine the cause for the early wakeup. 714 * 715 * Return: 716 * -EWOULDBLOCK or -ETIMEDOUT or -ERESTARTNOINTR 717 */ 718 static inline 719 int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb, 720 struct futex_q *q, 721 struct hrtimer_sleeper *timeout) 722 { 723 int ret; 724 725 /* 726 * With the hb lock held, we avoid races while we process the wakeup. 727 * We only need to hold hb (and not hb2) to ensure atomicity as the 728 * wakeup code can't change q.key from uaddr to uaddr2 if we hold hb. 729 * It can't be requeued from uaddr2 to something else since we don't 730 * support a PI aware source futex for requeue. 731 */ 732 WARN_ON_ONCE(&hb->lock != q->lock_ptr); 733 734 /* 735 * We were woken prior to requeue by a timeout or a signal. 736 * Conditionally unqueue the futex_q and determine which it was. 737 */ 738 if (!plist_node_empty(&q->list)) { 739 plist_del(&q->list, &hb->chain); 740 futex_hb_waiters_dec(hb); 741 } 742 743 /* Handle spurious wakeups gracefully */ 744 ret = -EWOULDBLOCK; 745 if (timeout && !timeout->task) 746 ret = -ETIMEDOUT; 747 else if (signal_pending(current)) 748 ret = -ERESTARTNOINTR; 749 return ret; 750 } 751 752 /** 753 * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2 754 * @uaddr: the futex we initially wait on (non-pi) 755 * @flags: futex flags (FLAGS_SHARED, FLAGS_CLOCKRT, etc.), they must be 756 * the same type, no requeueing from private to shared, etc. 757 * @val: the expected value of uaddr 758 * @abs_time: absolute timeout 759 * @bitset: 32 bit wakeup bitset set by userspace, defaults to all 760 * @uaddr2: the pi futex we will take prior to returning to user-space 761 * 762 * The caller will wait on uaddr and will be requeued by futex_requeue() to 763 * uaddr2 which must be PI aware and unique from uaddr. Normal wakeup will wake 764 * on uaddr2 and complete the acquisition of the rt_mutex prior to returning to 765 * userspace. This ensures the rt_mutex maintains an owner when it has waiters; 766 * without one, the pi logic would not know which task to boost/deboost, if 767 * there was a need to. 768 * 769 * We call schedule in futex_wait_queue() when we enqueue and return there 770 * via the following-- 771 * 1) wakeup on uaddr2 after an atomic lock acquisition by futex_requeue() 772 * 2) wakeup on uaddr2 after a requeue 773 * 3) signal 774 * 4) timeout 775 * 776 * If 3, cleanup and return -ERESTARTNOINTR. 777 * 778 * If 2, we may then block on trying to take the rt_mutex and return via: 779 * 5) successful lock 780 * 6) signal 781 * 7) timeout 782 * 8) other lock acquisition failure 783 * 784 * If 6, return -EWOULDBLOCK (restarting the syscall would do the same). 785 * 786 * If 4 or 7, we cleanup and return with -ETIMEDOUT. 787 * 788 * Return: 789 * - 0 - On success; 790 * - <0 - On error 791 */ 792 int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags, 793 u32 val, ktime_t *abs_time, u32 bitset, 794 u32 __user *uaddr2) 795 { 796 struct hrtimer_sleeper timeout, *to; 797 struct rt_mutex_waiter rt_waiter; 798 union futex_key key2 = FUTEX_KEY_INIT; 799 struct futex_q q = futex_q_init; 800 struct rt_mutex_base *pi_mutex; 801 int res, ret; 802 803 if (!IS_ENABLED(CONFIG_FUTEX_PI)) 804 return -ENOSYS; 805 806 if (uaddr == uaddr2) 807 return -EINVAL; 808 809 if (!bitset) 810 return -EINVAL; 811 812 to = futex_setup_timer(abs_time, &timeout, flags, 813 current->timer_slack_ns); 814 815 /* 816 * The waiter is allocated on our stack, manipulated by the requeue 817 * code while we sleep on uaddr. 818 */ 819 rt_mutex_init_waiter(&rt_waiter); 820 821 ret = get_futex_key(uaddr2, flags, &key2, FUTEX_WRITE); 822 if (unlikely(ret != 0)) 823 goto out; 824 825 q.bitset = bitset; 826 q.rt_waiter = &rt_waiter; 827 q.requeue_pi_key = &key2; 828 829 /* 830 * Prepare to wait on uaddr. On success, it holds hb->lock and q 831 * is initialized. 832 */ 833 ret = futex_wait_setup(uaddr, val, flags, &q, &key2, current); 834 if (ret) 835 goto out; 836 837 /* Queue the futex_q, drop the hb lock, wait for wakeup. */ 838 futex_do_wait(&q, to); 839 840 switch (futex_requeue_pi_wakeup_sync(&q)) { 841 case Q_REQUEUE_PI_IGNORE: 842 { 843 CLASS(hbr, hbr)(&q.key); 844 auto hb = hbr.hb; 845 /* The waiter is still on uaddr1 */ 846 spin_lock(&hb->lock); 847 ret = handle_early_requeue_pi_wakeup(hb, &q, to); 848 spin_unlock(&hb->lock); 849 } 850 break; 851 852 case Q_REQUEUE_PI_LOCKED: 853 /* The requeue acquired the lock */ 854 if (q.pi_state && (q.pi_state->owner != current)) { 855 futex_q_lockptr_lock(&q); 856 ret = fixup_pi_owner(uaddr2, &q, true); 857 /* 858 * Drop the reference to the pi state which the 859 * requeue_pi() code acquired for us. 860 */ 861 put_pi_state(q.pi_state); 862 spin_unlock(q.lock_ptr); 863 /* 864 * Adjust the return value. It's either -EFAULT or 865 * success (1) but the caller expects 0 for success. 866 */ 867 ret = ret < 0 ? ret : 0; 868 } 869 break; 870 871 case Q_REQUEUE_PI_DONE: 872 /* Requeue completed. Current is 'pi_blocked_on' the rtmutex */ 873 pi_mutex = &q.pi_state->pi_mutex; 874 ret = rt_mutex_wait_proxy_lock(pi_mutex, to, &rt_waiter); 875 876 /* 877 * See futex_unlock_pi()'s cleanup: comment. 878 */ 879 if (ret && !rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter)) 880 ret = 0; 881 882 futex_q_lockptr_lock(&q); 883 debug_rt_mutex_free_waiter(&rt_waiter); 884 /* 885 * Fixup the pi_state owner and possibly acquire the lock if we 886 * haven't already. 887 */ 888 res = fixup_pi_owner(uaddr2, &q, !ret); 889 /* 890 * If fixup_pi_owner() returned an error, propagate that. If it 891 * acquired the lock, clear -ETIMEDOUT or -EINTR. 892 */ 893 if (res) 894 ret = (res < 0) ? res : 0; 895 896 futex_unqueue_pi(&q); 897 spin_unlock(q.lock_ptr); 898 899 if (ret == -EINTR) { 900 /* 901 * We've already been requeued, but cannot restart 902 * by calling futex_lock_pi() directly. We could 903 * restart this syscall, but it would detect that 904 * the user space "val" changed and return 905 * -EWOULDBLOCK. Save the overhead of the restart 906 * and return -EWOULDBLOCK directly. 907 */ 908 ret = -EWOULDBLOCK; 909 } 910 break; 911 default: 912 BUG(); 913 } 914 /* Additional reference from requeue_pi_wake_futex() */ 915 futex_private_hash_put(q.drop_fph); 916 917 out: 918 if (to) { 919 hrtimer_cancel(&to->timer); 920 destroy_hrtimer_on_stack(&to->timer); 921 } 922 return ret; 923 } 924 925