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