1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Fast Userspace Mutexes (which I call "Futexes!"). 4 * (C) Rusty Russell, IBM 2002 5 * 6 * Generalized futexes, futex requeueing, misc fixes by Ingo Molnar 7 * (C) Copyright 2003 Red Hat Inc, All Rights Reserved 8 * 9 * Removed page pinning, fix privately mapped COW pages and other cleanups 10 * (C) Copyright 2003, 2004 Jamie Lokier 11 * 12 * Robust futex support started by Ingo Molnar 13 * (C) Copyright 2006 Red Hat Inc, All Rights Reserved 14 * Thanks to Thomas Gleixner for suggestions, analysis and fixes. 15 * 16 * PI-futex support started by Ingo Molnar and Thomas Gleixner 17 * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com> 18 * Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com> 19 * 20 * PRIVATE futexes by Eric Dumazet 21 * Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com> 22 * 23 * Requeue-PI support by Darren Hart <dvhltc@us.ibm.com> 24 * Copyright (C) IBM Corporation, 2009 25 * Thanks to Thomas Gleixner for conceptual design and careful reviews. 26 * 27 * Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly 28 * enough at me, Linus for the original (flawed) idea, Matthew 29 * Kirkwood for proof-of-concept implementation. 30 * 31 * "The futexes are also cursed." 32 * "But they come in a choice of three flavours!" 33 */ 34 #include <linux/compat.h> 35 #include <linux/jhash.h> 36 #include <linux/pagemap.h> 37 #include <linux/memblock.h> 38 #include <linux/fault-inject.h> 39 #include <linux/slab.h> 40 41 #include "futex.h" 42 #include "../locking/rtmutex_common.h" 43 44 /* 45 * The base of the bucket array and its size are always used together 46 * (after initialization only in futex_hash()), so ensure that they 47 * reside in the same cacheline. 48 */ 49 static struct { 50 struct futex_hash_bucket *queues; 51 unsigned long hashsize; 52 } __futex_data __read_mostly __aligned(2*sizeof(long)); 53 #define futex_queues (__futex_data.queues) 54 #define futex_hashsize (__futex_data.hashsize) 55 56 57 /* 58 * Fault injections for futexes. 59 */ 60 #ifdef CONFIG_FAIL_FUTEX 61 62 static struct { 63 struct fault_attr attr; 64 65 bool ignore_private; 66 } fail_futex = { 67 .attr = FAULT_ATTR_INITIALIZER, 68 .ignore_private = false, 69 }; 70 71 static int __init setup_fail_futex(char *str) 72 { 73 return setup_fault_attr(&fail_futex.attr, str); 74 } 75 __setup("fail_futex=", setup_fail_futex); 76 77 bool should_fail_futex(bool fshared) 78 { 79 if (fail_futex.ignore_private && !fshared) 80 return false; 81 82 return should_fail(&fail_futex.attr, 1); 83 } 84 85 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS 86 87 static int __init fail_futex_debugfs(void) 88 { 89 umode_t mode = S_IFREG | S_IRUSR | S_IWUSR; 90 struct dentry *dir; 91 92 dir = fault_create_debugfs_attr("fail_futex", NULL, 93 &fail_futex.attr); 94 if (IS_ERR(dir)) 95 return PTR_ERR(dir); 96 97 debugfs_create_bool("ignore-private", mode, dir, 98 &fail_futex.ignore_private); 99 return 0; 100 } 101 102 late_initcall(fail_futex_debugfs); 103 104 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ 105 106 #endif /* CONFIG_FAIL_FUTEX */ 107 108 /** 109 * futex_hash - Return the hash bucket in the global hash 110 * @key: Pointer to the futex key for which the hash is calculated 111 * 112 * We hash on the keys returned from get_futex_key (see below) and return the 113 * corresponding hash bucket in the global hash. 114 */ 115 struct futex_hash_bucket *futex_hash(union futex_key *key) 116 { 117 u32 hash = jhash2((u32 *)key, offsetof(typeof(*key), both.offset) / 4, 118 key->both.offset); 119 120 return &futex_queues[hash & (futex_hashsize - 1)]; 121 } 122 123 124 /** 125 * futex_setup_timer - set up the sleeping hrtimer. 126 * @time: ptr to the given timeout value 127 * @timeout: the hrtimer_sleeper structure to be set up 128 * @flags: futex flags 129 * @range_ns: optional range in ns 130 * 131 * Return: Initialized hrtimer_sleeper structure or NULL if no timeout 132 * value given 133 */ 134 struct hrtimer_sleeper * 135 futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout, 136 int flags, u64 range_ns) 137 { 138 if (!time) 139 return NULL; 140 141 hrtimer_init_sleeper_on_stack(timeout, (flags & FLAGS_CLOCKRT) ? 142 CLOCK_REALTIME : CLOCK_MONOTONIC, 143 HRTIMER_MODE_ABS); 144 /* 145 * If range_ns is 0, calling hrtimer_set_expires_range_ns() is 146 * effectively the same as calling hrtimer_set_expires(). 147 */ 148 hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns); 149 150 return timeout; 151 } 152 153 /* 154 * Generate a machine wide unique identifier for this inode. 155 * 156 * This relies on u64 not wrapping in the life-time of the machine; which with 157 * 1ns resolution means almost 585 years. 158 * 159 * This further relies on the fact that a well formed program will not unmap 160 * the file while it has a (shared) futex waiting on it. This mapping will have 161 * a file reference which pins the mount and inode. 162 * 163 * If for some reason an inode gets evicted and read back in again, it will get 164 * a new sequence number and will _NOT_ match, even though it is the exact same 165 * file. 166 * 167 * It is important that futex_match() will never have a false-positive, esp. 168 * for PI futexes that can mess up the state. The above argues that false-negatives 169 * are only possible for malformed programs. 170 */ 171 static u64 get_inode_sequence_number(struct inode *inode) 172 { 173 static atomic64_t i_seq; 174 u64 old; 175 176 /* Does the inode already have a sequence number? */ 177 old = atomic64_read(&inode->i_sequence); 178 if (likely(old)) 179 return old; 180 181 for (;;) { 182 u64 new = atomic64_add_return(1, &i_seq); 183 if (WARN_ON_ONCE(!new)) 184 continue; 185 186 old = atomic64_cmpxchg_relaxed(&inode->i_sequence, 0, new); 187 if (old) 188 return old; 189 return new; 190 } 191 } 192 193 /** 194 * get_futex_key() - Get parameters which are the keys for a futex 195 * @uaddr: virtual address of the futex 196 * @flags: FLAGS_* 197 * @key: address where result is stored. 198 * @rw: mapping needs to be read/write (values: FUTEX_READ, 199 * FUTEX_WRITE) 200 * 201 * Return: a negative error code or 0 202 * 203 * The key words are stored in @key on success. 204 * 205 * For shared mappings (when @fshared), the key is: 206 * 207 * ( inode->i_sequence, page->index, offset_within_page ) 208 * 209 * [ also see get_inode_sequence_number() ] 210 * 211 * For private mappings (or when !@fshared), the key is: 212 * 213 * ( current->mm, address, 0 ) 214 * 215 * This allows (cross process, where applicable) identification of the futex 216 * without keeping the page pinned for the duration of the FUTEX_WAIT. 217 * 218 * lock_page() might sleep, the caller should not hold a spinlock. 219 */ 220 int get_futex_key(u32 __user *uaddr, unsigned int flags, union futex_key *key, 221 enum futex_access rw) 222 { 223 unsigned long address = (unsigned long)uaddr; 224 struct mm_struct *mm = current->mm; 225 struct page *page; 226 struct folio *folio; 227 struct address_space *mapping; 228 int err, ro = 0; 229 bool fshared; 230 231 fshared = flags & FLAGS_SHARED; 232 233 /* 234 * The futex address must be "naturally" aligned. 235 */ 236 key->both.offset = address % PAGE_SIZE; 237 if (unlikely((address % sizeof(u32)) != 0)) 238 return -EINVAL; 239 address -= key->both.offset; 240 241 if (unlikely(!access_ok(uaddr, sizeof(u32)))) 242 return -EFAULT; 243 244 if (unlikely(should_fail_futex(fshared))) 245 return -EFAULT; 246 247 /* 248 * PROCESS_PRIVATE futexes are fast. 249 * As the mm cannot disappear under us and the 'key' only needs 250 * virtual address, we dont even have to find the underlying vma. 251 * Note : We do have to check 'uaddr' is a valid user address, 252 * but access_ok() should be faster than find_vma() 253 */ 254 if (!fshared) { 255 /* 256 * On no-MMU, shared futexes are treated as private, therefore 257 * we must not include the current process in the key. Since 258 * there is only one address space, the address is a unique key 259 * on its own. 260 */ 261 if (IS_ENABLED(CONFIG_MMU)) 262 key->private.mm = mm; 263 else 264 key->private.mm = NULL; 265 266 key->private.address = address; 267 return 0; 268 } 269 270 again: 271 /* Ignore any VERIFY_READ mapping (futex common case) */ 272 if (unlikely(should_fail_futex(true))) 273 return -EFAULT; 274 275 err = get_user_pages_fast(address, 1, FOLL_WRITE, &page); 276 /* 277 * If write access is not required (eg. FUTEX_WAIT), try 278 * and get read-only access. 279 */ 280 if (err == -EFAULT && rw == FUTEX_READ) { 281 err = get_user_pages_fast(address, 1, 0, &page); 282 ro = 1; 283 } 284 if (err < 0) 285 return err; 286 else 287 err = 0; 288 289 /* 290 * The treatment of mapping from this point on is critical. The folio 291 * lock protects many things but in this context the folio lock 292 * stabilizes mapping, prevents inode freeing in the shared 293 * file-backed region case and guards against movement to swap cache. 294 * 295 * Strictly speaking the folio lock is not needed in all cases being 296 * considered here and folio lock forces unnecessarily serialization. 297 * From this point on, mapping will be re-verified if necessary and 298 * folio lock will be acquired only if it is unavoidable 299 * 300 * Mapping checks require the folio so it is looked up now. For 301 * anonymous pages, it does not matter if the folio is split 302 * in the future as the key is based on the address. For 303 * filesystem-backed pages, the precise page is required as the 304 * index of the page determines the key. 305 */ 306 folio = page_folio(page); 307 mapping = READ_ONCE(folio->mapping); 308 309 /* 310 * If folio->mapping is NULL, then it cannot be an anonymous 311 * page; but it might be the ZERO_PAGE or in the gate area or 312 * in a special mapping (all cases which we are happy to fail); 313 * or it may have been a good file page when get_user_pages_fast 314 * found it, but truncated or holepunched or subjected to 315 * invalidate_complete_page2 before we got the folio lock (also 316 * cases which we are happy to fail). And we hold a reference, 317 * so refcount care in invalidate_inode_page's remove_mapping 318 * prevents drop_caches from setting mapping to NULL beneath us. 319 * 320 * The case we do have to guard against is when memory pressure made 321 * shmem_writepage move it from filecache to swapcache beneath us: 322 * an unlikely race, but we do need to retry for folio->mapping. 323 */ 324 if (unlikely(!mapping)) { 325 int shmem_swizzled; 326 327 /* 328 * Folio lock is required to identify which special case above 329 * applies. If this is really a shmem page then the folio lock 330 * will prevent unexpected transitions. 331 */ 332 folio_lock(folio); 333 shmem_swizzled = folio_test_swapcache(folio) || folio->mapping; 334 folio_unlock(folio); 335 folio_put(folio); 336 337 if (shmem_swizzled) 338 goto again; 339 340 return -EFAULT; 341 } 342 343 /* 344 * Private mappings are handled in a simple way. 345 * 346 * If the futex key is stored in anonymous memory, then the associated 347 * object is the mm which is implicitly pinned by the calling process. 348 * 349 * NOTE: When userspace waits on a MAP_SHARED mapping, even if 350 * it's a read-only handle, it's expected that futexes attach to 351 * the object not the particular process. 352 */ 353 if (folio_test_anon(folio)) { 354 /* 355 * A RO anonymous page will never change and thus doesn't make 356 * sense for futex operations. 357 */ 358 if (unlikely(should_fail_futex(true)) || ro) { 359 err = -EFAULT; 360 goto out; 361 } 362 363 key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */ 364 key->private.mm = mm; 365 key->private.address = address; 366 367 } else { 368 struct inode *inode; 369 370 /* 371 * The associated futex object in this case is the inode and 372 * the folio->mapping must be traversed. Ordinarily this should 373 * be stabilised under folio lock but it's not strictly 374 * necessary in this case as we just want to pin the inode, not 375 * update i_pages or anything like that. 376 * 377 * The RCU read lock is taken as the inode is finally freed 378 * under RCU. If the mapping still matches expectations then the 379 * mapping->host can be safely accessed as being a valid inode. 380 */ 381 rcu_read_lock(); 382 383 if (READ_ONCE(folio->mapping) != mapping) { 384 rcu_read_unlock(); 385 folio_put(folio); 386 387 goto again; 388 } 389 390 inode = READ_ONCE(mapping->host); 391 if (!inode) { 392 rcu_read_unlock(); 393 folio_put(folio); 394 395 goto again; 396 } 397 398 key->both.offset |= FUT_OFF_INODE; /* inode-based key */ 399 key->shared.i_seq = get_inode_sequence_number(inode); 400 key->shared.pgoff = folio->index + folio_page_idx(folio, page); 401 rcu_read_unlock(); 402 } 403 404 out: 405 folio_put(folio); 406 return err; 407 } 408 409 /** 410 * fault_in_user_writeable() - Fault in user address and verify RW access 411 * @uaddr: pointer to faulting user space address 412 * 413 * Slow path to fixup the fault we just took in the atomic write 414 * access to @uaddr. 415 * 416 * We have no generic implementation of a non-destructive write to the 417 * user address. We know that we faulted in the atomic pagefault 418 * disabled section so we can as well avoid the #PF overhead by 419 * calling get_user_pages() right away. 420 */ 421 int fault_in_user_writeable(u32 __user *uaddr) 422 { 423 struct mm_struct *mm = current->mm; 424 int ret; 425 426 mmap_read_lock(mm); 427 ret = fixup_user_fault(mm, (unsigned long)uaddr, 428 FAULT_FLAG_WRITE, NULL); 429 mmap_read_unlock(mm); 430 431 return ret < 0 ? ret : 0; 432 } 433 434 /** 435 * futex_top_waiter() - Return the highest priority waiter on a futex 436 * @hb: the hash bucket the futex_q's reside in 437 * @key: the futex key (to distinguish it from other futex futex_q's) 438 * 439 * Must be called with the hb lock held. 440 */ 441 struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb, union futex_key *key) 442 { 443 struct futex_q *this; 444 445 plist_for_each_entry(this, &hb->chain, list) { 446 if (futex_match(&this->key, key)) 447 return this; 448 } 449 return NULL; 450 } 451 452 int futex_cmpxchg_value_locked(u32 *curval, u32 __user *uaddr, u32 uval, u32 newval) 453 { 454 int ret; 455 456 pagefault_disable(); 457 ret = futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval); 458 pagefault_enable(); 459 460 return ret; 461 } 462 463 int futex_get_value_locked(u32 *dest, u32 __user *from) 464 { 465 int ret; 466 467 pagefault_disable(); 468 ret = __get_user(*dest, from); 469 pagefault_enable(); 470 471 return ret ? -EFAULT : 0; 472 } 473 474 /** 475 * wait_for_owner_exiting - Block until the owner has exited 476 * @ret: owner's current futex lock status 477 * @exiting: Pointer to the exiting task 478 * 479 * Caller must hold a refcount on @exiting. 480 */ 481 void wait_for_owner_exiting(int ret, struct task_struct *exiting) 482 { 483 if (ret != -EBUSY) { 484 WARN_ON_ONCE(exiting); 485 return; 486 } 487 488 if (WARN_ON_ONCE(ret == -EBUSY && !exiting)) 489 return; 490 491 mutex_lock(&exiting->futex_exit_mutex); 492 /* 493 * No point in doing state checking here. If the waiter got here 494 * while the task was in exec()->exec_futex_release() then it can 495 * have any FUTEX_STATE_* value when the waiter has acquired the 496 * mutex. OK, if running, EXITING or DEAD if it reached exit() 497 * already. Highly unlikely and not a problem. Just one more round 498 * through the futex maze. 499 */ 500 mutex_unlock(&exiting->futex_exit_mutex); 501 502 put_task_struct(exiting); 503 } 504 505 /** 506 * __futex_unqueue() - Remove the futex_q from its futex_hash_bucket 507 * @q: The futex_q to unqueue 508 * 509 * The q->lock_ptr must not be NULL and must be held by the caller. 510 */ 511 void __futex_unqueue(struct futex_q *q) 512 { 513 struct futex_hash_bucket *hb; 514 515 if (WARN_ON_SMP(!q->lock_ptr) || WARN_ON(plist_node_empty(&q->list))) 516 return; 517 lockdep_assert_held(q->lock_ptr); 518 519 hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock); 520 plist_del(&q->list, &hb->chain); 521 futex_hb_waiters_dec(hb); 522 } 523 524 /* The key must be already stored in q->key. */ 525 struct futex_hash_bucket *futex_q_lock(struct futex_q *q) 526 __acquires(&hb->lock) 527 { 528 struct futex_hash_bucket *hb; 529 530 hb = futex_hash(&q->key); 531 532 /* 533 * Increment the counter before taking the lock so that 534 * a potential waker won't miss a to-be-slept task that is 535 * waiting for the spinlock. This is safe as all futex_q_lock() 536 * users end up calling futex_queue(). Similarly, for housekeeping, 537 * decrement the counter at futex_q_unlock() when some error has 538 * occurred and we don't end up adding the task to the list. 539 */ 540 futex_hb_waiters_inc(hb); /* implies smp_mb(); (A) */ 541 542 q->lock_ptr = &hb->lock; 543 544 spin_lock(&hb->lock); 545 return hb; 546 } 547 548 void futex_q_unlock(struct futex_hash_bucket *hb) 549 __releases(&hb->lock) 550 { 551 spin_unlock(&hb->lock); 552 futex_hb_waiters_dec(hb); 553 } 554 555 void __futex_queue(struct futex_q *q, struct futex_hash_bucket *hb) 556 { 557 int prio; 558 559 /* 560 * The priority used to register this element is 561 * - either the real thread-priority for the real-time threads 562 * (i.e. threads with a priority lower than MAX_RT_PRIO) 563 * - or MAX_RT_PRIO for non-RT threads. 564 * Thus, all RT-threads are woken first in priority order, and 565 * the others are woken last, in FIFO order. 566 */ 567 prio = min(current->normal_prio, MAX_RT_PRIO); 568 569 plist_node_init(&q->list, prio); 570 plist_add(&q->list, &hb->chain); 571 q->task = current; 572 } 573 574 /** 575 * futex_unqueue() - Remove the futex_q from its futex_hash_bucket 576 * @q: The futex_q to unqueue 577 * 578 * The q->lock_ptr must not be held by the caller. A call to futex_unqueue() must 579 * be paired with exactly one earlier call to futex_queue(). 580 * 581 * Return: 582 * - 1 - if the futex_q was still queued (and we removed unqueued it); 583 * - 0 - if the futex_q was already removed by the waking thread 584 */ 585 int futex_unqueue(struct futex_q *q) 586 { 587 spinlock_t *lock_ptr; 588 int ret = 0; 589 590 /* In the common case we don't take the spinlock, which is nice. */ 591 retry: 592 /* 593 * q->lock_ptr can change between this read and the following spin_lock. 594 * Use READ_ONCE to forbid the compiler from reloading q->lock_ptr and 595 * optimizing lock_ptr out of the logic below. 596 */ 597 lock_ptr = READ_ONCE(q->lock_ptr); 598 if (lock_ptr != NULL) { 599 spin_lock(lock_ptr); 600 /* 601 * q->lock_ptr can change between reading it and 602 * spin_lock(), causing us to take the wrong lock. This 603 * corrects the race condition. 604 * 605 * Reasoning goes like this: if we have the wrong lock, 606 * q->lock_ptr must have changed (maybe several times) 607 * between reading it and the spin_lock(). It can 608 * change again after the spin_lock() but only if it was 609 * already changed before the spin_lock(). It cannot, 610 * however, change back to the original value. Therefore 611 * we can detect whether we acquired the correct lock. 612 */ 613 if (unlikely(lock_ptr != q->lock_ptr)) { 614 spin_unlock(lock_ptr); 615 goto retry; 616 } 617 __futex_unqueue(q); 618 619 BUG_ON(q->pi_state); 620 621 spin_unlock(lock_ptr); 622 ret = 1; 623 } 624 625 return ret; 626 } 627 628 /* 629 * PI futexes can not be requeued and must remove themselves from the 630 * hash bucket. The hash bucket lock (i.e. lock_ptr) is held. 631 */ 632 void futex_unqueue_pi(struct futex_q *q) 633 { 634 __futex_unqueue(q); 635 636 BUG_ON(!q->pi_state); 637 put_pi_state(q->pi_state); 638 q->pi_state = NULL; 639 } 640 641 /* Constants for the pending_op argument of handle_futex_death */ 642 #define HANDLE_DEATH_PENDING true 643 #define HANDLE_DEATH_LIST false 644 645 /* 646 * Process a futex-list entry, check whether it's owned by the 647 * dying task, and do notification if so: 648 */ 649 static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, 650 bool pi, bool pending_op) 651 { 652 u32 uval, nval, mval; 653 pid_t owner; 654 int err; 655 656 /* Futex address must be 32bit aligned */ 657 if ((((unsigned long)uaddr) % sizeof(*uaddr)) != 0) 658 return -1; 659 660 retry: 661 if (get_user(uval, uaddr)) 662 return -1; 663 664 /* 665 * Special case for regular (non PI) futexes. The unlock path in 666 * user space has two race scenarios: 667 * 668 * 1. The unlock path releases the user space futex value and 669 * before it can execute the futex() syscall to wake up 670 * waiters it is killed. 671 * 672 * 2. A woken up waiter is killed before it can acquire the 673 * futex in user space. 674 * 675 * In the second case, the wake up notification could be generated 676 * by the unlock path in user space after setting the futex value 677 * to zero or by the kernel after setting the OWNER_DIED bit below. 678 * 679 * In both cases the TID validation below prevents a wakeup of 680 * potential waiters which can cause these waiters to block 681 * forever. 682 * 683 * In both cases the following conditions are met: 684 * 685 * 1) task->robust_list->list_op_pending != NULL 686 * @pending_op == true 687 * 2) The owner part of user space futex value == 0 688 * 3) Regular futex: @pi == false 689 * 690 * If these conditions are met, it is safe to attempt waking up a 691 * potential waiter without touching the user space futex value and 692 * trying to set the OWNER_DIED bit. If the futex value is zero, 693 * the rest of the user space mutex state is consistent, so a woken 694 * waiter will just take over the uncontended futex. Setting the 695 * OWNER_DIED bit would create inconsistent state and malfunction 696 * of the user space owner died handling. Otherwise, the OWNER_DIED 697 * bit is already set, and the woken waiter is expected to deal with 698 * this. 699 */ 700 owner = uval & FUTEX_TID_MASK; 701 702 if (pending_op && !pi && !owner) { 703 futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, 1, 704 FUTEX_BITSET_MATCH_ANY); 705 return 0; 706 } 707 708 if (owner != task_pid_vnr(curr)) 709 return 0; 710 711 /* 712 * Ok, this dying thread is truly holding a futex 713 * of interest. Set the OWNER_DIED bit atomically 714 * via cmpxchg, and if the value had FUTEX_WAITERS 715 * set, wake up a waiter (if any). (We have to do a 716 * futex_wake() even if OWNER_DIED is already set - 717 * to handle the rare but possible case of recursive 718 * thread-death.) The rest of the cleanup is done in 719 * userspace. 720 */ 721 mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED; 722 723 /* 724 * We are not holding a lock here, but we want to have 725 * the pagefault_disable/enable() protection because 726 * we want to handle the fault gracefully. If the 727 * access fails we try to fault in the futex with R/W 728 * verification via get_user_pages. get_user() above 729 * does not guarantee R/W access. If that fails we 730 * give up and leave the futex locked. 731 */ 732 if ((err = futex_cmpxchg_value_locked(&nval, uaddr, uval, mval))) { 733 switch (err) { 734 case -EFAULT: 735 if (fault_in_user_writeable(uaddr)) 736 return -1; 737 goto retry; 738 739 case -EAGAIN: 740 cond_resched(); 741 goto retry; 742 743 default: 744 WARN_ON_ONCE(1); 745 return err; 746 } 747 } 748 749 if (nval != uval) 750 goto retry; 751 752 /* 753 * Wake robust non-PI futexes here. The wakeup of 754 * PI futexes happens in exit_pi_state(): 755 */ 756 if (!pi && (uval & FUTEX_WAITERS)) { 757 futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, 1, 758 FUTEX_BITSET_MATCH_ANY); 759 } 760 761 return 0; 762 } 763 764 /* 765 * Fetch a robust-list pointer. Bit 0 signals PI futexes: 766 */ 767 static inline int fetch_robust_entry(struct robust_list __user **entry, 768 struct robust_list __user * __user *head, 769 unsigned int *pi) 770 { 771 unsigned long uentry; 772 773 if (get_user(uentry, (unsigned long __user *)head)) 774 return -EFAULT; 775 776 *entry = (void __user *)(uentry & ~1UL); 777 *pi = uentry & 1; 778 779 return 0; 780 } 781 782 /* 783 * Walk curr->robust_list (very carefully, it's a userspace list!) 784 * and mark any locks found there dead, and notify any waiters. 785 * 786 * We silently return on any sign of list-walking problem. 787 */ 788 static void exit_robust_list(struct task_struct *curr) 789 { 790 struct robust_list_head __user *head = curr->robust_list; 791 struct robust_list __user *entry, *next_entry, *pending; 792 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; 793 unsigned int next_pi; 794 unsigned long futex_offset; 795 int rc; 796 797 /* 798 * Fetch the list head (which was registered earlier, via 799 * sys_set_robust_list()): 800 */ 801 if (fetch_robust_entry(&entry, &head->list.next, &pi)) 802 return; 803 /* 804 * Fetch the relative futex offset: 805 */ 806 if (get_user(futex_offset, &head->futex_offset)) 807 return; 808 /* 809 * Fetch any possibly pending lock-add first, and handle it 810 * if it exists: 811 */ 812 if (fetch_robust_entry(&pending, &head->list_op_pending, &pip)) 813 return; 814 815 next_entry = NULL; /* avoid warning with gcc */ 816 while (entry != &head->list) { 817 /* 818 * Fetch the next entry in the list before calling 819 * handle_futex_death: 820 */ 821 rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi); 822 /* 823 * A pending lock might already be on the list, so 824 * don't process it twice: 825 */ 826 if (entry != pending) { 827 if (handle_futex_death((void __user *)entry + futex_offset, 828 curr, pi, HANDLE_DEATH_LIST)) 829 return; 830 } 831 if (rc) 832 return; 833 entry = next_entry; 834 pi = next_pi; 835 /* 836 * Avoid excessively long or circular lists: 837 */ 838 if (!--limit) 839 break; 840 841 cond_resched(); 842 } 843 844 if (pending) { 845 handle_futex_death((void __user *)pending + futex_offset, 846 curr, pip, HANDLE_DEATH_PENDING); 847 } 848 } 849 850 #ifdef CONFIG_COMPAT 851 static void __user *futex_uaddr(struct robust_list __user *entry, 852 compat_long_t futex_offset) 853 { 854 compat_uptr_t base = ptr_to_compat(entry); 855 void __user *uaddr = compat_ptr(base + futex_offset); 856 857 return uaddr; 858 } 859 860 /* 861 * Fetch a robust-list pointer. Bit 0 signals PI futexes: 862 */ 863 static inline int 864 compat_fetch_robust_entry(compat_uptr_t *uentry, struct robust_list __user **entry, 865 compat_uptr_t __user *head, unsigned int *pi) 866 { 867 if (get_user(*uentry, head)) 868 return -EFAULT; 869 870 *entry = compat_ptr((*uentry) & ~1); 871 *pi = (unsigned int)(*uentry) & 1; 872 873 return 0; 874 } 875 876 /* 877 * Walk curr->robust_list (very carefully, it's a userspace list!) 878 * and mark any locks found there dead, and notify any waiters. 879 * 880 * We silently return on any sign of list-walking problem. 881 */ 882 static void compat_exit_robust_list(struct task_struct *curr) 883 { 884 struct compat_robust_list_head __user *head = curr->compat_robust_list; 885 struct robust_list __user *entry, *next_entry, *pending; 886 unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; 887 unsigned int next_pi; 888 compat_uptr_t uentry, next_uentry, upending; 889 compat_long_t futex_offset; 890 int rc; 891 892 /* 893 * Fetch the list head (which was registered earlier, via 894 * sys_set_robust_list()): 895 */ 896 if (compat_fetch_robust_entry(&uentry, &entry, &head->list.next, &pi)) 897 return; 898 /* 899 * Fetch the relative futex offset: 900 */ 901 if (get_user(futex_offset, &head->futex_offset)) 902 return; 903 /* 904 * Fetch any possibly pending lock-add first, and handle it 905 * if it exists: 906 */ 907 if (compat_fetch_robust_entry(&upending, &pending, 908 &head->list_op_pending, &pip)) 909 return; 910 911 next_entry = NULL; /* avoid warning with gcc */ 912 while (entry != (struct robust_list __user *) &head->list) { 913 /* 914 * Fetch the next entry in the list before calling 915 * handle_futex_death: 916 */ 917 rc = compat_fetch_robust_entry(&next_uentry, &next_entry, 918 (compat_uptr_t __user *)&entry->next, &next_pi); 919 /* 920 * A pending lock might already be on the list, so 921 * dont process it twice: 922 */ 923 if (entry != pending) { 924 void __user *uaddr = futex_uaddr(entry, futex_offset); 925 926 if (handle_futex_death(uaddr, curr, pi, 927 HANDLE_DEATH_LIST)) 928 return; 929 } 930 if (rc) 931 return; 932 uentry = next_uentry; 933 entry = next_entry; 934 pi = next_pi; 935 /* 936 * Avoid excessively long or circular lists: 937 */ 938 if (!--limit) 939 break; 940 941 cond_resched(); 942 } 943 if (pending) { 944 void __user *uaddr = futex_uaddr(pending, futex_offset); 945 946 handle_futex_death(uaddr, curr, pip, HANDLE_DEATH_PENDING); 947 } 948 } 949 #endif 950 951 #ifdef CONFIG_FUTEX_PI 952 953 /* 954 * This task is holding PI mutexes at exit time => bad. 955 * Kernel cleans up PI-state, but userspace is likely hosed. 956 * (Robust-futex cleanup is separate and might save the day for userspace.) 957 */ 958 static void exit_pi_state_list(struct task_struct *curr) 959 { 960 struct list_head *next, *head = &curr->pi_state_list; 961 struct futex_pi_state *pi_state; 962 struct futex_hash_bucket *hb; 963 union futex_key key = FUTEX_KEY_INIT; 964 965 /* 966 * We are a ZOMBIE and nobody can enqueue itself on 967 * pi_state_list anymore, but we have to be careful 968 * versus waiters unqueueing themselves: 969 */ 970 raw_spin_lock_irq(&curr->pi_lock); 971 while (!list_empty(head)) { 972 next = head->next; 973 pi_state = list_entry(next, struct futex_pi_state, list); 974 key = pi_state->key; 975 hb = futex_hash(&key); 976 977 /* 978 * We can race against put_pi_state() removing itself from the 979 * list (a waiter going away). put_pi_state() will first 980 * decrement the reference count and then modify the list, so 981 * its possible to see the list entry but fail this reference 982 * acquire. 983 * 984 * In that case; drop the locks to let put_pi_state() make 985 * progress and retry the loop. 986 */ 987 if (!refcount_inc_not_zero(&pi_state->refcount)) { 988 raw_spin_unlock_irq(&curr->pi_lock); 989 cpu_relax(); 990 raw_spin_lock_irq(&curr->pi_lock); 991 continue; 992 } 993 raw_spin_unlock_irq(&curr->pi_lock); 994 995 spin_lock(&hb->lock); 996 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock); 997 raw_spin_lock(&curr->pi_lock); 998 /* 999 * We dropped the pi-lock, so re-check whether this 1000 * task still owns the PI-state: 1001 */ 1002 if (head->next != next) { 1003 /* retain curr->pi_lock for the loop invariant */ 1004 raw_spin_unlock(&pi_state->pi_mutex.wait_lock); 1005 spin_unlock(&hb->lock); 1006 put_pi_state(pi_state); 1007 continue; 1008 } 1009 1010 WARN_ON(pi_state->owner != curr); 1011 WARN_ON(list_empty(&pi_state->list)); 1012 list_del_init(&pi_state->list); 1013 pi_state->owner = NULL; 1014 1015 raw_spin_unlock(&curr->pi_lock); 1016 raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock); 1017 spin_unlock(&hb->lock); 1018 1019 rt_mutex_futex_unlock(&pi_state->pi_mutex); 1020 put_pi_state(pi_state); 1021 1022 raw_spin_lock_irq(&curr->pi_lock); 1023 } 1024 raw_spin_unlock_irq(&curr->pi_lock); 1025 } 1026 #else 1027 static inline void exit_pi_state_list(struct task_struct *curr) { } 1028 #endif 1029 1030 static void futex_cleanup(struct task_struct *tsk) 1031 { 1032 if (unlikely(tsk->robust_list)) { 1033 exit_robust_list(tsk); 1034 tsk->robust_list = NULL; 1035 } 1036 1037 #ifdef CONFIG_COMPAT 1038 if (unlikely(tsk->compat_robust_list)) { 1039 compat_exit_robust_list(tsk); 1040 tsk->compat_robust_list = NULL; 1041 } 1042 #endif 1043 1044 if (unlikely(!list_empty(&tsk->pi_state_list))) 1045 exit_pi_state_list(tsk); 1046 } 1047 1048 /** 1049 * futex_exit_recursive - Set the tasks futex state to FUTEX_STATE_DEAD 1050 * @tsk: task to set the state on 1051 * 1052 * Set the futex exit state of the task lockless. The futex waiter code 1053 * observes that state when a task is exiting and loops until the task has 1054 * actually finished the futex cleanup. The worst case for this is that the 1055 * waiter runs through the wait loop until the state becomes visible. 1056 * 1057 * This is called from the recursive fault handling path in make_task_dead(). 1058 * 1059 * This is best effort. Either the futex exit code has run already or 1060 * not. If the OWNER_DIED bit has been set on the futex then the waiter can 1061 * take it over. If not, the problem is pushed back to user space. If the 1062 * futex exit code did not run yet, then an already queued waiter might 1063 * block forever, but there is nothing which can be done about that. 1064 */ 1065 void futex_exit_recursive(struct task_struct *tsk) 1066 { 1067 /* If the state is FUTEX_STATE_EXITING then futex_exit_mutex is held */ 1068 if (tsk->futex_state == FUTEX_STATE_EXITING) 1069 mutex_unlock(&tsk->futex_exit_mutex); 1070 tsk->futex_state = FUTEX_STATE_DEAD; 1071 } 1072 1073 static void futex_cleanup_begin(struct task_struct *tsk) 1074 { 1075 /* 1076 * Prevent various race issues against a concurrent incoming waiter 1077 * including live locks by forcing the waiter to block on 1078 * tsk->futex_exit_mutex when it observes FUTEX_STATE_EXITING in 1079 * attach_to_pi_owner(). 1080 */ 1081 mutex_lock(&tsk->futex_exit_mutex); 1082 1083 /* 1084 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_lock. 1085 * 1086 * This ensures that all subsequent checks of tsk->futex_state in 1087 * attach_to_pi_owner() must observe FUTEX_STATE_EXITING with 1088 * tsk->pi_lock held. 1089 * 1090 * It guarantees also that a pi_state which was queued right before 1091 * the state change under tsk->pi_lock by a concurrent waiter must 1092 * be observed in exit_pi_state_list(). 1093 */ 1094 raw_spin_lock_irq(&tsk->pi_lock); 1095 tsk->futex_state = FUTEX_STATE_EXITING; 1096 raw_spin_unlock_irq(&tsk->pi_lock); 1097 } 1098 1099 static void futex_cleanup_end(struct task_struct *tsk, int state) 1100 { 1101 /* 1102 * Lockless store. The only side effect is that an observer might 1103 * take another loop until it becomes visible. 1104 */ 1105 tsk->futex_state = state; 1106 /* 1107 * Drop the exit protection. This unblocks waiters which observed 1108 * FUTEX_STATE_EXITING to reevaluate the state. 1109 */ 1110 mutex_unlock(&tsk->futex_exit_mutex); 1111 } 1112 1113 void futex_exec_release(struct task_struct *tsk) 1114 { 1115 /* 1116 * The state handling is done for consistency, but in the case of 1117 * exec() there is no way to prevent further damage as the PID stays 1118 * the same. But for the unlikely and arguably buggy case that a 1119 * futex is held on exec(), this provides at least as much state 1120 * consistency protection which is possible. 1121 */ 1122 futex_cleanup_begin(tsk); 1123 futex_cleanup(tsk); 1124 /* 1125 * Reset the state to FUTEX_STATE_OK. The task is alive and about 1126 * exec a new binary. 1127 */ 1128 futex_cleanup_end(tsk, FUTEX_STATE_OK); 1129 } 1130 1131 void futex_exit_release(struct task_struct *tsk) 1132 { 1133 futex_cleanup_begin(tsk); 1134 futex_cleanup(tsk); 1135 futex_cleanup_end(tsk, FUTEX_STATE_DEAD); 1136 } 1137 1138 static int __init futex_init(void) 1139 { 1140 unsigned int futex_shift; 1141 unsigned long i; 1142 1143 #if CONFIG_BASE_SMALL 1144 futex_hashsize = 16; 1145 #else 1146 futex_hashsize = roundup_pow_of_two(256 * num_possible_cpus()); 1147 #endif 1148 1149 futex_queues = alloc_large_system_hash("futex", sizeof(*futex_queues), 1150 futex_hashsize, 0, 0, 1151 &futex_shift, NULL, 1152 futex_hashsize, futex_hashsize); 1153 futex_hashsize = 1UL << futex_shift; 1154 1155 for (i = 0; i < futex_hashsize; i++) { 1156 atomic_set(&futex_queues[i].waiters, 0); 1157 plist_head_init(&futex_queues[i].chain); 1158 spin_lock_init(&futex_queues[i].lock); 1159 } 1160 1161 return 0; 1162 } 1163 core_initcall(futex_init); 1164