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