1 // SPDX-License-Identifier: GPL-2.0-or-later 2 3 #include <linux/sched/task.h> 4 #include <linux/sched/signal.h> 5 #include <linux/freezer.h> 6 7 #include "futex.h" 8 9 /* 10 * READ this before attempting to hack on futexes! 11 * 12 * Basic futex operation and ordering guarantees 13 * ============================================= 14 * 15 * The waiter reads the futex value in user space and calls 16 * futex_wait(). This function computes the hash bucket and acquires 17 * the hash bucket lock. After that it reads the futex user space value 18 * again and verifies that the data has not changed. If it has not changed 19 * it enqueues itself into the hash bucket, releases the hash bucket lock 20 * and schedules. 21 * 22 * The waker side modifies the user space value of the futex and calls 23 * futex_wake(). This function computes the hash bucket and acquires the 24 * hash bucket lock. Then it looks for waiters on that futex in the hash 25 * bucket and wakes them. 26 * 27 * In futex wake up scenarios where no tasks are blocked on a futex, taking 28 * the hb spinlock can be avoided and simply return. In order for this 29 * optimization to work, ordering guarantees must exist so that the waiter 30 * being added to the list is acknowledged when the list is concurrently being 31 * checked by the waker, avoiding scenarios like the following: 32 * 33 * CPU 0 CPU 1 34 * val = *futex; 35 * sys_futex(WAIT, futex, val); 36 * futex_wait(futex, val); 37 * uval = *futex; 38 * *futex = newval; 39 * sys_futex(WAKE, futex); 40 * futex_wake(futex); 41 * if (queue_empty()) 42 * return; 43 * if (uval == val) 44 * lock(hash_bucket(futex)); 45 * queue(); 46 * unlock(hash_bucket(futex)); 47 * schedule(); 48 * 49 * This would cause the waiter on CPU 0 to wait forever because it 50 * missed the transition of the user space value from val to newval 51 * and the waker did not find the waiter in the hash bucket queue. 52 * 53 * The correct serialization ensures that a waiter either observes 54 * the changed user space value before blocking or is woken by a 55 * concurrent waker: 56 * 57 * CPU 0 CPU 1 58 * val = *futex; 59 * sys_futex(WAIT, futex, val); 60 * futex_wait(futex, val); 61 * 62 * waiters++; (a) 63 * smp_mb(); (A) <-- paired with -. 64 * | 65 * lock(hash_bucket(futex)); | 66 * | 67 * uval = *futex; | 68 * | *futex = newval; 69 * | sys_futex(WAKE, futex); 70 * | futex_wake(futex); 71 * | 72 * `--------> smp_mb(); (B) 73 * if (uval == val) 74 * queue(); 75 * unlock(hash_bucket(futex)); 76 * schedule(); if (waiters) 77 * lock(hash_bucket(futex)); 78 * else wake_waiters(futex); 79 * waiters--; (b) unlock(hash_bucket(futex)); 80 * 81 * Where (A) orders the waiters increment and the futex value read through 82 * atomic operations (see futex_hb_waiters_inc) and where (B) orders the write 83 * to futex and the waiters read (see futex_hb_waiters_pending()). 84 * 85 * This yields the following case (where X:=waiters, Y:=futex): 86 * 87 * X = Y = 0 88 * 89 * w[X]=1 w[Y]=1 90 * MB MB 91 * r[Y]=y r[X]=x 92 * 93 * Which guarantees that x==0 && y==0 is impossible; which translates back into 94 * the guarantee that we cannot both miss the futex variable change and the 95 * enqueue. 96 * 97 * Note that a new waiter is accounted for in (a) even when it is possible that 98 * the wait call can return error, in which case we backtrack from it in (b). 99 * Refer to the comment in futex_q_lock(). 100 * 101 * Similarly, in order to account for waiters being requeued on another 102 * address we always increment the waiters for the destination bucket before 103 * acquiring the lock. It then decrements them again after releasing it - 104 * the code that actually moves the futex(es) between hash buckets (requeue_futex) 105 * will do the additional required waiter count housekeeping. This is done for 106 * double_lock_hb() and double_unlock_hb(), respectively. 107 */ 108 109 /* 110 * The hash bucket lock must be held when this is called. 111 * Afterwards, the futex_q must not be accessed. Callers 112 * must ensure to later call wake_up_q() for the actual 113 * wakeups to occur. 114 */ 115 void futex_wake_mark(struct wake_q_head *wake_q, struct futex_q *q) 116 { 117 struct task_struct *p = q->task; 118 119 if (WARN(q->pi_state || q->rt_waiter, "refusing to wake PI futex\n")) 120 return; 121 122 get_task_struct(p); 123 __futex_unqueue(q); 124 /* 125 * The waiting task can free the futex_q as soon as q->lock_ptr = NULL 126 * is written, without taking any locks. This is possible in the event 127 * of a spurious wakeup, for example. A memory barrier is required here 128 * to prevent the following store to lock_ptr from getting ahead of the 129 * plist_del in __futex_unqueue(). 130 */ 131 smp_store_release(&q->lock_ptr, NULL); 132 133 /* 134 * Queue the task for later wakeup for after we've released 135 * the hb->lock. 136 */ 137 wake_q_add_safe(wake_q, p); 138 } 139 140 /* 141 * Wake up waiters matching bitset queued on this futex (uaddr). 142 */ 143 int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset) 144 { 145 struct futex_hash_bucket *hb; 146 struct futex_q *this, *next; 147 union futex_key key = FUTEX_KEY_INIT; 148 DEFINE_WAKE_Q(wake_q); 149 int ret; 150 151 if (!bitset) 152 return -EINVAL; 153 154 ret = get_futex_key(uaddr, flags, &key, FUTEX_READ); 155 if (unlikely(ret != 0)) 156 return ret; 157 158 if ((flags & FLAGS_STRICT) && !nr_wake) 159 return 0; 160 161 hb = futex_hash(&key); 162 163 /* Make sure we really have tasks to wakeup */ 164 if (!futex_hb_waiters_pending(hb)) 165 return ret; 166 167 spin_lock(&hb->lock); 168 169 plist_for_each_entry_safe(this, next, &hb->chain, list) { 170 if (futex_match (&this->key, &key)) { 171 if (this->pi_state || this->rt_waiter) { 172 ret = -EINVAL; 173 break; 174 } 175 176 /* Check if one of the bits is set in both bitsets */ 177 if (!(this->bitset & bitset)) 178 continue; 179 180 futex_wake_mark(&wake_q, this); 181 if (++ret >= nr_wake) 182 break; 183 } 184 } 185 186 spin_unlock(&hb->lock); 187 wake_up_q(&wake_q); 188 return ret; 189 } 190 191 static int futex_atomic_op_inuser(unsigned int encoded_op, u32 __user *uaddr) 192 { 193 unsigned int op = (encoded_op & 0x70000000) >> 28; 194 unsigned int cmp = (encoded_op & 0x0f000000) >> 24; 195 int oparg = sign_extend32((encoded_op & 0x00fff000) >> 12, 11); 196 int cmparg = sign_extend32(encoded_op & 0x00000fff, 11); 197 int oldval, ret; 198 199 if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28)) { 200 if (oparg < 0 || oparg > 31) { 201 char comm[sizeof(current->comm)]; 202 /* 203 * kill this print and return -EINVAL when userspace 204 * is sane again 205 */ 206 pr_info_ratelimited("futex_wake_op: %s tries to shift op by %d; fix this program\n", 207 get_task_comm(comm, current), oparg); 208 oparg &= 31; 209 } 210 oparg = 1 << oparg; 211 } 212 213 pagefault_disable(); 214 ret = arch_futex_atomic_op_inuser(op, oparg, &oldval, uaddr); 215 pagefault_enable(); 216 if (ret) 217 return ret; 218 219 switch (cmp) { 220 case FUTEX_OP_CMP_EQ: 221 return oldval == cmparg; 222 case FUTEX_OP_CMP_NE: 223 return oldval != cmparg; 224 case FUTEX_OP_CMP_LT: 225 return oldval < cmparg; 226 case FUTEX_OP_CMP_GE: 227 return oldval >= cmparg; 228 case FUTEX_OP_CMP_LE: 229 return oldval <= cmparg; 230 case FUTEX_OP_CMP_GT: 231 return oldval > cmparg; 232 default: 233 return -ENOSYS; 234 } 235 } 236 237 /* 238 * Wake up all waiters hashed on the physical page that is mapped 239 * to this virtual address: 240 */ 241 int futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2, 242 int nr_wake, int nr_wake2, int op) 243 { 244 union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT; 245 struct futex_hash_bucket *hb1, *hb2; 246 struct futex_q *this, *next; 247 int ret, op_ret; 248 DEFINE_WAKE_Q(wake_q); 249 250 retry: 251 ret = get_futex_key(uaddr1, flags, &key1, FUTEX_READ); 252 if (unlikely(ret != 0)) 253 return ret; 254 ret = get_futex_key(uaddr2, flags, &key2, FUTEX_WRITE); 255 if (unlikely(ret != 0)) 256 return ret; 257 258 hb1 = futex_hash(&key1); 259 hb2 = futex_hash(&key2); 260 261 retry_private: 262 double_lock_hb(hb1, hb2); 263 op_ret = futex_atomic_op_inuser(op, uaddr2); 264 if (unlikely(op_ret < 0)) { 265 double_unlock_hb(hb1, hb2); 266 267 if (!IS_ENABLED(CONFIG_MMU) || 268 unlikely(op_ret != -EFAULT && op_ret != -EAGAIN)) { 269 /* 270 * we don't get EFAULT from MMU faults if we don't have 271 * an MMU, but we might get them from range checking 272 */ 273 ret = op_ret; 274 return ret; 275 } 276 277 if (op_ret == -EFAULT) { 278 ret = fault_in_user_writeable(uaddr2); 279 if (ret) 280 return ret; 281 } 282 283 cond_resched(); 284 if (!(flags & FLAGS_SHARED)) 285 goto retry_private; 286 goto retry; 287 } 288 289 plist_for_each_entry_safe(this, next, &hb1->chain, list) { 290 if (futex_match (&this->key, &key1)) { 291 if (this->pi_state || this->rt_waiter) { 292 ret = -EINVAL; 293 goto out_unlock; 294 } 295 futex_wake_mark(&wake_q, this); 296 if (++ret >= nr_wake) 297 break; 298 } 299 } 300 301 if (op_ret > 0) { 302 op_ret = 0; 303 plist_for_each_entry_safe(this, next, &hb2->chain, list) { 304 if (futex_match (&this->key, &key2)) { 305 if (this->pi_state || this->rt_waiter) { 306 ret = -EINVAL; 307 goto out_unlock; 308 } 309 futex_wake_mark(&wake_q, this); 310 if (++op_ret >= nr_wake2) 311 break; 312 } 313 } 314 ret += op_ret; 315 } 316 317 out_unlock: 318 double_unlock_hb(hb1, hb2); 319 wake_up_q(&wake_q); 320 return ret; 321 } 322 323 static long futex_wait_restart(struct restart_block *restart); 324 325 /** 326 * futex_wait_queue() - futex_queue() and wait for wakeup, timeout, or signal 327 * @hb: the futex hash bucket, must be locked by the caller 328 * @q: the futex_q to queue up on 329 * @timeout: the prepared hrtimer_sleeper, or null for no timeout 330 */ 331 void futex_wait_queue(struct futex_hash_bucket *hb, struct futex_q *q, 332 struct hrtimer_sleeper *timeout) 333 { 334 /* 335 * The task state is guaranteed to be set before another task can 336 * wake it. set_current_state() is implemented using smp_store_mb() and 337 * futex_queue() calls spin_unlock() upon completion, both serializing 338 * access to the hash list and forcing another memory barrier. 339 */ 340 set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE); 341 futex_queue(q, hb); 342 343 /* Arm the timer */ 344 if (timeout) 345 hrtimer_sleeper_start_expires(timeout, HRTIMER_MODE_ABS); 346 347 /* 348 * If we have been removed from the hash list, then another task 349 * has tried to wake us, and we can skip the call to schedule(). 350 */ 351 if (likely(!plist_node_empty(&q->list))) { 352 /* 353 * If the timer has already expired, current will already be 354 * flagged for rescheduling. Only call schedule if there 355 * is no timeout, or if it has yet to expire. 356 */ 357 if (!timeout || timeout->task) 358 schedule(); 359 } 360 __set_current_state(TASK_RUNNING); 361 } 362 363 /** 364 * unqueue_multiple - Remove various futexes from their hash bucket 365 * @v: The list of futexes to unqueue 366 * @count: Number of futexes in the list 367 * 368 * Helper to unqueue a list of futexes. This can't fail. 369 * 370 * Return: 371 * - >=0 - Index of the last futex that was awoken; 372 * - -1 - No futex was awoken 373 */ 374 static int unqueue_multiple(struct futex_vector *v, int count) 375 { 376 int ret = -1, i; 377 378 for (i = 0; i < count; i++) { 379 if (!futex_unqueue(&v[i].q)) 380 ret = i; 381 } 382 383 return ret; 384 } 385 386 /** 387 * futex_wait_multiple_setup - Prepare to wait and enqueue multiple futexes 388 * @vs: The futex list to wait on 389 * @count: The size of the list 390 * @woken: Index of the last woken futex, if any. Used to notify the 391 * caller that it can return this index to userspace (return parameter) 392 * 393 * Prepare multiple futexes in a single step and enqueue them. This may fail if 394 * the futex list is invalid or if any futex was already awoken. On success the 395 * task is ready to interruptible sleep. 396 * 397 * Return: 398 * - 1 - One of the futexes was woken by another thread 399 * - 0 - Success 400 * - <0 - -EFAULT, -EWOULDBLOCK or -EINVAL 401 */ 402 static int futex_wait_multiple_setup(struct futex_vector *vs, int count, int *woken) 403 { 404 struct futex_hash_bucket *hb; 405 bool retry = false; 406 int ret, i; 407 u32 uval; 408 409 /* 410 * Enqueuing multiple futexes is tricky, because we need to enqueue 411 * each futex on the list before dealing with the next one to avoid 412 * deadlocking on the hash bucket. But, before enqueuing, we need to 413 * make sure that current->state is TASK_INTERRUPTIBLE, so we don't 414 * lose any wake events, which cannot be done before the get_futex_key 415 * of the next key, because it calls get_user_pages, which can sleep. 416 * Thus, we fetch the list of futexes keys in two steps, by first 417 * pinning all the memory keys in the futex key, and only then we read 418 * each key and queue the corresponding futex. 419 * 420 * Private futexes doesn't need to recalculate hash in retry, so skip 421 * get_futex_key() when retrying. 422 */ 423 retry: 424 for (i = 0; i < count; i++) { 425 if (!(vs[i].w.flags & FLAGS_SHARED) && retry) 426 continue; 427 428 ret = get_futex_key(u64_to_user_ptr(vs[i].w.uaddr), 429 vs[i].w.flags, 430 &vs[i].q.key, FUTEX_READ); 431 432 if (unlikely(ret)) 433 return ret; 434 } 435 436 set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE); 437 438 for (i = 0; i < count; i++) { 439 u32 __user *uaddr = (u32 __user *)(unsigned long)vs[i].w.uaddr; 440 struct futex_q *q = &vs[i].q; 441 u32 val = vs[i].w.val; 442 443 hb = futex_q_lock(q); 444 ret = futex_get_value_locked(&uval, uaddr); 445 446 if (!ret && uval == val) { 447 /* 448 * The bucket lock can't be held while dealing with the 449 * next futex. Queue each futex at this moment so hb can 450 * be unlocked. 451 */ 452 futex_queue(q, hb); 453 continue; 454 } 455 456 futex_q_unlock(hb); 457 __set_current_state(TASK_RUNNING); 458 459 /* 460 * Even if something went wrong, if we find out that a futex 461 * was woken, we don't return error and return this index to 462 * userspace 463 */ 464 *woken = unqueue_multiple(vs, i); 465 if (*woken >= 0) 466 return 1; 467 468 if (ret) { 469 /* 470 * If we need to handle a page fault, we need to do so 471 * without any lock and any enqueued futex (otherwise 472 * we could lose some wakeup). So we do it here, after 473 * undoing all the work done so far. In success, we 474 * retry all the work. 475 */ 476 if (get_user(uval, uaddr)) 477 return -EFAULT; 478 479 retry = true; 480 goto retry; 481 } 482 483 if (uval != val) 484 return -EWOULDBLOCK; 485 } 486 487 return 0; 488 } 489 490 /** 491 * futex_sleep_multiple - Check sleeping conditions and sleep 492 * @vs: List of futexes to wait for 493 * @count: Length of vs 494 * @to: Timeout 495 * 496 * Sleep if and only if the timeout hasn't expired and no futex on the list has 497 * been woken up. 498 */ 499 static void futex_sleep_multiple(struct futex_vector *vs, unsigned int count, 500 struct hrtimer_sleeper *to) 501 { 502 if (to && !to->task) 503 return; 504 505 for (; count; count--, vs++) { 506 if (!READ_ONCE(vs->q.lock_ptr)) 507 return; 508 } 509 510 schedule(); 511 } 512 513 /** 514 * futex_wait_multiple - Prepare to wait on and enqueue several futexes 515 * @vs: The list of futexes to wait on 516 * @count: The number of objects 517 * @to: Timeout before giving up and returning to userspace 518 * 519 * Entry point for the FUTEX_WAIT_MULTIPLE futex operation, this function 520 * sleeps on a group of futexes and returns on the first futex that is 521 * wake, or after the timeout has elapsed. 522 * 523 * Return: 524 * - >=0 - Hint to the futex that was awoken 525 * - <0 - On error 526 */ 527 int futex_wait_multiple(struct futex_vector *vs, unsigned int count, 528 struct hrtimer_sleeper *to) 529 { 530 int ret, hint = 0; 531 532 if (to) 533 hrtimer_sleeper_start_expires(to, HRTIMER_MODE_ABS); 534 535 while (1) { 536 ret = futex_wait_multiple_setup(vs, count, &hint); 537 if (ret) { 538 if (ret > 0) { 539 /* A futex was woken during setup */ 540 ret = hint; 541 } 542 return ret; 543 } 544 545 futex_sleep_multiple(vs, count, to); 546 547 __set_current_state(TASK_RUNNING); 548 549 ret = unqueue_multiple(vs, count); 550 if (ret >= 0) 551 return ret; 552 553 if (to && !to->task) 554 return -ETIMEDOUT; 555 else if (signal_pending(current)) 556 return -ERESTARTSYS; 557 /* 558 * The final case is a spurious wakeup, for 559 * which just retry. 560 */ 561 } 562 } 563 564 /** 565 * futex_wait_setup() - Prepare to wait on a futex 566 * @uaddr: the futex userspace address 567 * @val: the expected value 568 * @flags: futex flags (FLAGS_SHARED, etc.) 569 * @q: the associated futex_q 570 * @hb: storage for hash_bucket pointer to be returned to caller 571 * 572 * Setup the futex_q and locate the hash_bucket. Get the futex value and 573 * compare it with the expected value. Handle atomic faults internally. 574 * Return with the hb lock held on success, and unlocked on failure. 575 * 576 * Return: 577 * - 0 - uaddr contains val and hb has been locked; 578 * - <1 - -EFAULT or -EWOULDBLOCK (uaddr does not contain val) and hb is unlocked 579 */ 580 int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags, 581 struct futex_q *q, struct futex_hash_bucket **hb) 582 { 583 u32 uval; 584 int ret; 585 586 /* 587 * Access the page AFTER the hash-bucket is locked. 588 * Order is important: 589 * 590 * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val); 591 * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); } 592 * 593 * The basic logical guarantee of a futex is that it blocks ONLY 594 * if cond(var) is known to be true at the time of blocking, for 595 * any cond. If we locked the hash-bucket after testing *uaddr, that 596 * would open a race condition where we could block indefinitely with 597 * cond(var) false, which would violate the guarantee. 598 * 599 * On the other hand, we insert q and release the hash-bucket only 600 * after testing *uaddr. This guarantees that futex_wait() will NOT 601 * absorb a wakeup if *uaddr does not match the desired values 602 * while the syscall executes. 603 */ 604 retry: 605 ret = get_futex_key(uaddr, flags, &q->key, FUTEX_READ); 606 if (unlikely(ret != 0)) 607 return ret; 608 609 retry_private: 610 *hb = futex_q_lock(q); 611 612 ret = futex_get_value_locked(&uval, uaddr); 613 614 if (ret) { 615 futex_q_unlock(*hb); 616 617 ret = get_user(uval, uaddr); 618 if (ret) 619 return ret; 620 621 if (!(flags & FLAGS_SHARED)) 622 goto retry_private; 623 624 goto retry; 625 } 626 627 if (uval != val) { 628 futex_q_unlock(*hb); 629 ret = -EWOULDBLOCK; 630 } 631 632 return ret; 633 } 634 635 int __futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, 636 struct hrtimer_sleeper *to, u32 bitset) 637 { 638 struct futex_q q = futex_q_init; 639 struct futex_hash_bucket *hb; 640 int ret; 641 642 if (!bitset) 643 return -EINVAL; 644 645 q.bitset = bitset; 646 647 retry: 648 /* 649 * Prepare to wait on uaddr. On success, it holds hb->lock and q 650 * is initialized. 651 */ 652 ret = futex_wait_setup(uaddr, val, flags, &q, &hb); 653 if (ret) 654 return ret; 655 656 /* futex_queue and wait for wakeup, timeout, or a signal. */ 657 futex_wait_queue(hb, &q, to); 658 659 /* If we were woken (and unqueued), we succeeded, whatever. */ 660 if (!futex_unqueue(&q)) 661 return 0; 662 663 if (to && !to->task) 664 return -ETIMEDOUT; 665 666 /* 667 * We expect signal_pending(current), but we might be the 668 * victim of a spurious wakeup as well. 669 */ 670 if (!signal_pending(current)) 671 goto retry; 672 673 return -ERESTARTSYS; 674 } 675 676 int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset) 677 { 678 struct hrtimer_sleeper timeout, *to; 679 struct restart_block *restart; 680 int ret; 681 682 to = futex_setup_timer(abs_time, &timeout, flags, 683 current->timer_slack_ns); 684 685 ret = __futex_wait(uaddr, flags, val, to, bitset); 686 687 /* No timeout, nothing to clean up. */ 688 if (!to) 689 return ret; 690 691 hrtimer_cancel(&to->timer); 692 destroy_hrtimer_on_stack(&to->timer); 693 694 if (ret == -ERESTARTSYS) { 695 restart = ¤t->restart_block; 696 restart->futex.uaddr = uaddr; 697 restart->futex.val = val; 698 restart->futex.time = *abs_time; 699 restart->futex.bitset = bitset; 700 restart->futex.flags = flags | FLAGS_HAS_TIMEOUT; 701 702 return set_restart_fn(restart, futex_wait_restart); 703 } 704 705 return ret; 706 } 707 708 static long futex_wait_restart(struct restart_block *restart) 709 { 710 u32 __user *uaddr = restart->futex.uaddr; 711 ktime_t t, *tp = NULL; 712 713 if (restart->futex.flags & FLAGS_HAS_TIMEOUT) { 714 t = restart->futex.time; 715 tp = &t; 716 } 717 restart->fn = do_no_restart_syscall; 718 719 return (long)futex_wait(uaddr, restart->futex.flags, 720 restart->futex.val, tp, restart->futex.bitset); 721 } 722 723