Module Name: src Committed By: thorpej Date: Thu Aug 5 23:14:21 UTC 2021
Modified Files: src/sys/kern [thorpej-futex2]: sys_futex.c src/sys/sys [thorpej-futex2]: lwp.h Log Message: Bring over just the futex sleepq infrastructure changes from thorpej-futex to a new branch based on current HEAD. This contains only the fixes for the priority problems, and is intended to finish debugging those changes (without the new extensions). To generate a diff of this commit: cvs rdiff -u -r1.12 -r1.12.4.1 src/sys/kern/sys_futex.c cvs rdiff -u -r1.212 -r1.212.14.1 src/sys/sys/lwp.h Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/sys/kern/sys_futex.c diff -u src/sys/kern/sys_futex.c:1.12 src/sys/kern/sys_futex.c:1.12.4.1 --- src/sys/kern/sys_futex.c:1.12 Wed Jul 21 06:35:45 2021 +++ src/sys/kern/sys_futex.c Thu Aug 5 23:14:21 2021 @@ -1,4 +1,4 @@ -/* $NetBSD: sys_futex.c,v 1.12 2021/07/21 06:35:45 skrll Exp $ */ +/* $NetBSD: sys_futex.c,v 1.12.4.1 2021/08/05 23:14:21 thorpej Exp $ */ /*- * Copyright (c) 2018, 2019, 2020 The NetBSD Foundation, Inc. @@ -30,7 +30,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: sys_futex.c,v 1.12 2021/07/21 06:35:45 skrll Exp $"); +__KERNEL_RCSID(0, "$NetBSD: sys_futex.c,v 1.12.4.1 2021/08/05 23:14:21 thorpej Exp $"); /* * Futexes @@ -121,7 +121,9 @@ __KERNEL_RCSID(0, "$NetBSD: sys_futex.c, #include <sys/futex.h> #include <sys/mutex.h> #include <sys/rbtree.h> +#include <sys/sleepq.h> #include <sys/queue.h> +#include <sys/sdt.h> #include <sys/syscall.h> #include <sys/syscallargs.h> @@ -130,13 +132,56 @@ __KERNEL_RCSID(0, "$NetBSD: sys_futex.c, #include <uvm/uvm_extern.h> /* + * DTrace probes. + */ +SDT_PROVIDER_DEFINE(futex); + +/* entry: uaddr, val, bitset, timeout, clkflags, fflags */ +/* exit: error */ +SDT_PROBE_DEFINE6(futex, func, wait, entry, "int *", "int", "int", + "struct timespec *", "int", "int"); +SDT_PROBE_DEFINE1(futex, func, wait, exit, "int"); + +/* entry: uaddr, nwake, bitset, fflags */ +/* exit: error, nwoken */ +SDT_PROBE_DEFINE4(futex, func, wake, entry, "int *", "int", "int", "int"); +SDT_PROBE_DEFINE2(futex, func, wake, exit, "int", "int"); + +/* entry: uaddr, nwake, uaddr2, nrequeue, fflags */ +/* exit: error, nwoken */ +SDT_PROBE_DEFINE5(futex, func, requeue, entry, "int *", "int", "int *", "int", + "int"); +SDT_PROBE_DEFINE2(futex, func, requeue, exit, "int", "int"); + +/* entry: uaddr, nwake, uaddr2, nrequeue, val3, fflags */ +/* exit: error, nwoken */ +SDT_PROBE_DEFINE6(futex, func, cmp_requeue, entry, "int *", "int", "int *", + "int", "int", "int"); +SDT_PROBE_DEFINE2(futex, func, cmp_requeue, exit, "int", "int"); + +/* entry: uaddr, nwake, uaddr2, nwake2, wakeop, fflags */ +/* exit: error, nwoken */ +SDT_PROBE_DEFINE6(futex, func, wake_op, entry, "int *", "int", "int *", "int", + "int", "int"); +SDT_PROBE_DEFINE2(futex, func, wake_op, exit, "int", "int"); + +SDT_PROBE_DEFINE0(futex, wait, finish, normally); +SDT_PROBE_DEFINE0(futex, wait, finish, wakerace); +SDT_PROBE_DEFINE0(futex, wait, finish, aborted); + +/* entry: timo */ +/* exit: error */ +SDT_PROBE_DEFINE1(futex, wait, sleepq_block, entry, "int"); +SDT_PROBE_DEFINE1(futex, wait, sleepq_block, exit, "int"); + +/* * Lock order: * * futex_tab.lock - * futex::fx_qlock ordered by kva of struct futex - * -> futex_wait::fw_lock only one at a time - * futex_wait::fw_lock only one at a time - * -> futex::fx_abortlock only one at a time + * futex::fx_op_lock ordered by kva of struct futex + * -> futex::fx_sq_lock ordered by kva of sleepq lock + * + * N.B. multiple futexes can share a single sleepq lock. */ /* @@ -166,37 +211,52 @@ union futex_key { * that can be present on the system at any given time, and the * assumption is that limit will be good enough on a 32-bit platform. * See futex_wake() for why overflow needs to be avoided. + * + * XXX Since futex addresses must be 4-byte aligned, we could + * XXX squirrel away fx_shared and fx_on_tree bits in the "va" + * XXX field of the key. Worth it? */ struct futex { union futex_key fx_key; + struct rb_node fx_node; unsigned long fx_refcnt; bool fx_shared; bool fx_on_tree; - struct rb_node fx_node; + uint8_t fx_class; - kmutex_t fx_qlock; - TAILQ_HEAD(, futex_wait) fx_queue; - - kmutex_t fx_abortlock; - LIST_HEAD(, futex_wait) fx_abortlist; - kcondvar_t fx_abortcv; + kmutex_t fx_op_lock; /* adaptive */ + kmutex_t * fx_sq_lock; /* &sleepq_locks[...] */ + sleepq_t fx_sqs[2]; /* 0=reader, 1=writer */ + unsigned int fx_nwaiters[2]; }; /* - * struct futex_wait - * - * State for a thread to wait on a futex. Threads wait on fw_cv - * for fw_bitset to be set to zero. The thread may transition to - * a different futex queue at any time under the futex's lock. - */ -struct futex_wait { - kmutex_t fw_lock; - kcondvar_t fw_cv; - struct futex *fw_futex; - TAILQ_ENTRY(futex_wait) fw_entry; /* queue lock */ - LIST_ENTRY(futex_wait) fw_abort; /* queue abortlock */ - int fw_bitset; - bool fw_aborting; /* fw_lock */ + * futex classes: Some futex operations can only be carried out on + * futexes that are known to be abiding by a certain protocol. These + * classes are assigned to a futex when created due to a wait event, + * and when subsequent wake or requeue operations are issued, the + * class is checked at futex lookup time. If the class does not match, + * EINVAL is the result. + */ +#define FUTEX_CLASS_ANY 0 /* match any class in lookup */ +#define FUTEX_CLASS_NORMAL 1 /* normal futex */ +#define FUTEX_CLASS_RWLOCK 2 /* rwlock futex */ +#define FUTEX_CLASS_PI 3 /* for FUTEX_*_PI ops */ + +/* sleepq definitions */ +#define FUTEX_READERQ 0 +#define FUTEX_WRITERQ 1 + +static const char futex_wmesg[] = "futex"; + +static void futex_unsleep(lwp_t *, bool); + +static syncobj_t futex_syncobj = { + .sobj_flag = SOBJ_SLEEPQ_SORTED, + .sobj_unsleep = futex_unsleep, + .sobj_changepri = sleepq_changepri, + .sobj_lendpri = sleepq_lendpri, + .sobj_owner = syncobj_noowner, }; /* @@ -280,7 +340,95 @@ static const rb_tree_ops_t futex_shared_ .rbto_node_offset = offsetof(struct futex, fx_node), }; -static void futex_wait_dequeue(struct futex_wait *, struct futex *); +/* + * futex_sq_lock2(f, f2) + * + * Acquire the sleepq locks for f and f2, which may be null, or + * which may be the same. If they are distinct, an arbitrary total + * order is chosen on the locks. + * + * Callers should only ever acquire multiple sleepq locks + * simultaneously using futex_sq_lock2. + */ +static void +futex_sq_lock2(struct futex * const f, struct futex * const f2) +{ + + /* + * If both are null, do nothing; if one is null and the other + * is not, lock the other and be done with it. + */ + if (f == NULL && f2 == NULL) { + return; + } else if (f == NULL) { + mutex_spin_enter(f2->fx_sq_lock); + return; + } else if (f2 == NULL) { + mutex_spin_enter(f->fx_sq_lock); + return; + } + + kmutex_t * const m = f->fx_sq_lock; + kmutex_t * const m2 = f2->fx_sq_lock; + + /* If both locks are the same, acquire only one. */ + if (m == m2) { + mutex_spin_enter(m); + return; + } + + /* Otherwise, use the ordering on the kva of the lock pointer. */ + if ((uintptr_t)m < (uintptr_t)m2) { + mutex_spin_enter(m); + mutex_spin_enter(m2); + } else { + mutex_spin_enter(m2); + mutex_spin_enter(m); + } +} + +/* + * futex_sq_unlock2(f, f2) + * + * Release the sleep queue locks for f and f2, which may be null, or + * which may have the same underlying lock. + */ +static void +futex_sq_unlock2(struct futex * const f, struct futex * const f2) +{ + + /* + * If both are null, do nothing; if one is null and the other + * is not, unlock the other and be done with it. + */ + if (f == NULL && f2 == NULL) { + return; + } else if (f == NULL) { + mutex_spin_exit(f2->fx_sq_lock); + return; + } else if (f2 == NULL) { + mutex_spin_exit(f->fx_sq_lock); + return; + } + + kmutex_t * const m = f->fx_sq_lock; + kmutex_t * const m2 = f2->fx_sq_lock; + + /* If both locks are the same, release only one. */ + if (m == m2) { + mutex_spin_exit(m); + return; + } + + /* Otherwise, use the ordering on the kva of the lock pointer. */ + if ((uintptr_t)m < (uintptr_t)m2) { + mutex_spin_exit(m2); + mutex_spin_exit(m); + } else { + mutex_spin_exit(m); + mutex_spin_exit(m2); + } +} /* * futex_load(uaddr, kaddr) @@ -313,6 +461,11 @@ futex_test(int *uaddr, int expected) return val == expected; } +static pool_cache_t futex_cache __read_mostly; + +static int futex_ctor(void *, void *, int); +static void futex_dtor(void *, void *); + /* * futex_sys_init() * @@ -325,6 +478,10 @@ futex_sys_init(void) mutex_init(&futex_tab.lock, MUTEX_DEFAULT, IPL_NONE); rb_tree_init(&futex_tab.va, &futex_rb_ops); rb_tree_init(&futex_tab.oa, &futex_shared_rb_ops); + + futex_cache = pool_cache_init(sizeof(struct futex), + coherency_unit, 0, 0, "futex", NULL, IPL_NONE, futex_ctor, + futex_dtor, NULL); } /* @@ -342,69 +499,38 @@ futex_sys_fini(void) } /* - * futex_queue_init(f) + * futex_ctor() * - * Initialize the futex queue. Caller must call futex_queue_fini - * when done. - * - * Never sleeps. + * Futex object constructor. */ -static void -futex_queue_init(struct futex *f) +static int +futex_ctor(void *arg __unused, void *obj, int flags __unused) { + extern sleepqlock_t sleepq_locks[SLEEPTAB_HASH_SIZE]; + struct futex * const f = obj; - mutex_init(&f->fx_qlock, MUTEX_DEFAULT, IPL_NONE); - mutex_init(&f->fx_abortlock, MUTEX_DEFAULT, IPL_NONE); - cv_init(&f->fx_abortcv, "fqabort"); - LIST_INIT(&f->fx_abortlist); - TAILQ_INIT(&f->fx_queue); -} - -/* - * futex_queue_drain(f) - * - * Wait for any aborting waiters in f; then empty the queue of - * any stragglers and wake them. Caller must guarantee no new - * references to f. - * - * May sleep. - */ -static void -futex_queue_drain(struct futex *f) -{ - struct futex_wait *fw, *fw_next; + mutex_init(&f->fx_op_lock, MUTEX_DEFAULT, IPL_NONE); + f->fx_sq_lock = &sleepq_locks[SLEEPTAB_HASH(f)].lock; - mutex_enter(&f->fx_abortlock); - while (!LIST_EMPTY(&f->fx_abortlist)) - cv_wait(&f->fx_abortcv, &f->fx_abortlock); - mutex_exit(&f->fx_abortlock); + sleepq_init(&f->fx_sqs[FUTEX_READERQ]); + sleepq_init(&f->fx_sqs[FUTEX_WRITERQ]); + f->fx_nwaiters[FUTEX_READERQ] = f->fx_nwaiters[FUTEX_WRITERQ] = 0; - mutex_enter(&f->fx_qlock); - TAILQ_FOREACH_SAFE(fw, &f->fx_queue, fw_entry, fw_next) { - mutex_enter(&fw->fw_lock); - futex_wait_dequeue(fw, f); - cv_broadcast(&fw->fw_cv); - mutex_exit(&fw->fw_lock); - } - mutex_exit(&f->fx_qlock); + return 0; } /* - * futex_queue_fini(fq) + * futex_dtor() * - * Finalize the futex queue initialized by futex_queue_init. Queue - * must be empty. Caller must not use f again until a subsequent - * futex_queue_init. + * Futex object destructor. */ static void -futex_queue_fini(struct futex *f) +futex_dtor(void *arg __unused, void *obj) { + struct futex * const f = obj; - KASSERT(TAILQ_EMPTY(&f->fx_queue)); - KASSERT(LIST_EMPTY(&f->fx_abortlist)); - mutex_destroy(&f->fx_qlock); - mutex_destroy(&f->fx_abortlock); - cv_destroy(&f->fx_abortcv); + mutex_destroy(&f->fx_op_lock); + f->fx_sq_lock = NULL; } /* @@ -452,11 +578,11 @@ futex_key_fini(union futex_key *fk, bool * Never sleeps for memory, but may sleep to acquire a lock. */ static struct futex * -futex_create(union futex_key *fk, bool shared) +futex_create(union futex_key *fk, bool shared, uint8_t class) { struct futex *f; - f = kmem_alloc(sizeof(*f), KM_NOSLEEP); + f = pool_cache_get(futex_cache, PR_NOWAIT); if (f == NULL) { futex_key_fini(fk, shared); return NULL; @@ -465,7 +591,7 @@ futex_create(union futex_key *fk, bool s f->fx_refcnt = 1; f->fx_shared = shared; f->fx_on_tree = false; - futex_queue_init(f); + f->fx_class = class; return f; } @@ -486,18 +612,18 @@ futex_destroy(struct futex *f) KASSERT(atomic_load_relaxed(&f->fx_refcnt) == 0); KASSERT(!f->fx_on_tree); - - /* Drain and destroy the private queue. */ - futex_queue_drain(f); - futex_queue_fini(f); + KASSERT(LIST_EMPTY(&f->fx_sqs[FUTEX_READERQ])); + KASSERT(LIST_EMPTY(&f->fx_sqs[FUTEX_WRITERQ])); + KASSERT(f->fx_nwaiters[FUTEX_READERQ] == 0); + KASSERT(f->fx_nwaiters[FUTEX_WRITERQ] == 0); futex_key_fini(&f->fx_key, f->fx_shared); - kmem_free(f, sizeof(*f)); + pool_cache_put(futex_cache, f); } /* - * futex_hold(f) + * futex_hold_count(f, n) * * Attempt to acquire a reference to f. Return 0 on success, * ENFILE on too many references. @@ -505,21 +631,23 @@ futex_destroy(struct futex *f) * Never sleeps. */ static int -futex_hold(struct futex *f) +futex_hold_count(struct futex *f, unsigned long const count) { unsigned long refcnt; do { refcnt = atomic_load_relaxed(&f->fx_refcnt); - if (refcnt == ULONG_MAX) + if (ULONG_MAX - refcnt < count) return ENFILE; - } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, refcnt + 1) != refcnt); + } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, + refcnt + count) != refcnt); return 0; } +#define futex_hold(f) futex_hold_count(f, 1) /* - * futex_rele(f) + * futex_rele_count(f, n) * * Release a reference to f acquired with futex_create or * futex_hold. @@ -527,7 +655,7 @@ futex_hold(struct futex *f) * May sleep to free f. */ static void -futex_rele(struct futex *f) +futex_rele_count(struct futex *f, unsigned long const count) { unsigned long refcnt; @@ -535,14 +663,17 @@ futex_rele(struct futex *f) do { refcnt = atomic_load_relaxed(&f->fx_refcnt); - if (refcnt == 1) + KASSERT(refcnt >= count); + if (refcnt - count == 0) goto trylast; - } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, refcnt - 1) != refcnt); + } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, + refcnt - count) != refcnt); return; trylast: + KASSERT(count <= LONG_MAX); mutex_enter(&futex_tab.lock); - if (atomic_dec_ulong_nv(&f->fx_refcnt) == 0) { + if (atomic_add_long_nv(&f->fx_refcnt, -(long)count) == 0) { if (f->fx_on_tree) { if (__predict_false(f->fx_shared)) rb_tree_remove_node(&futex_tab.oa, f); @@ -558,9 +689,10 @@ trylast: if (f != NULL) futex_destroy(f); } +#define futex_rele(f) futex_rele_count(f, 1) /* - * futex_rele_not_last(f) + * futex_rele_count_not_last(f, n) * * Release a reference to f acquired with futex_create or * futex_hold. @@ -569,18 +701,19 @@ trylast: * reference to f. */ static void -futex_rele_not_last(struct futex *f) +futex_rele_count_not_last(struct futex *f, unsigned long const count) { unsigned long refcnt; do { refcnt = atomic_load_relaxed(&f->fx_refcnt); - KASSERT(refcnt > 1); - } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, refcnt - 1) != refcnt); + KASSERT(refcnt >= count); + } while (atomic_cas_ulong(&f->fx_refcnt, refcnt, + refcnt - count) != refcnt); } /* - * futex_lookup_by_key(key, shared, &f) + * futex_lookup_by_key(key, shared, class, &f) * * Try to find an existing futex va reference in the specified key * On success, return 0, set f to found futex or to NULL if not found, @@ -592,7 +725,8 @@ futex_rele_not_last(struct futex *f) * futex_lookup_create(). */ static int -futex_lookup_by_key(union futex_key *fk, bool shared, struct futex **fp) +futex_lookup_by_key(union futex_key *fk, bool shared, uint8_t class, + struct futex **fp) { struct futex *f; int error = 0; @@ -604,7 +738,11 @@ futex_lookup_by_key(union futex_key *fk, f = rb_tree_find_node(&futex_tab.va, fk); } if (f) { - error = futex_hold(f); + if (__predict_true(f->fx_class == class || + class == FUTEX_CLASS_ANY)) + error = futex_hold(f); + else + error = EINVAL; if (error) f = NULL; } @@ -655,7 +793,7 @@ out: mutex_exit(&futex_tab.lock); } /* - * futex_lookup(uaddr, shared, &f) + * futex_lookup(uaddr, shared, class, &f) * * Find a futex at the userland pointer uaddr in the current * process's VM space. On success, return the futex in f and @@ -664,7 +802,7 @@ out: mutex_exit(&futex_tab.lock); * Caller must call futex_rele when done. */ static int -futex_lookup(int *uaddr, bool shared, struct futex **fp) +futex_lookup(int *uaddr, bool shared, uint8_t class, struct futex **fp) { union futex_key fk; struct vmspace *vm = curproc->p_vmspace; @@ -675,7 +813,7 @@ futex_lookup(int *uaddr, bool shared, st * Reject unaligned user pointers so we don't cross page * boundaries and so atomics will work. */ - if ((va & 3) != 0) + if (__predict_false((va & 3) != 0)) return EINVAL; /* Look it up. */ @@ -683,12 +821,13 @@ futex_lookup(int *uaddr, bool shared, st if (error) return error; - error = futex_lookup_by_key(&fk, shared, fp); + error = futex_lookup_by_key(&fk, shared, class, fp); futex_key_fini(&fk, shared); if (error) return error; KASSERT(*fp == NULL || (*fp)->fx_shared == shared); + KASSERT(*fp == NULL || (*fp)->fx_class == class); KASSERT(*fp == NULL || atomic_load_relaxed(&(*fp)->fx_refcnt) != 0); /* @@ -702,7 +841,7 @@ futex_lookup(int *uaddr, bool shared, st } /* - * futex_lookup_create(uaddr, shared, &f) + * futex_lookup_create(uaddr, shared, class, &f) * * Find or create a futex at the userland pointer uaddr in the * current process's VM space. On success, return the futex in f @@ -711,7 +850,7 @@ futex_lookup(int *uaddr, bool shared, st * Caller must call futex_rele when done. */ static int -futex_lookup_create(int *uaddr, bool shared, struct futex **fp) +futex_lookup_create(int *uaddr, bool shared, uint8_t class, struct futex **fp) { union futex_key fk; struct vmspace *vm = curproc->p_vmspace; @@ -723,7 +862,10 @@ futex_lookup_create(int *uaddr, bool sha * Reject unaligned user pointers so we don't cross page * boundaries and so atomics will work. */ - if ((va & 3) != 0) + if (__predict_false((va & 3) != 0)) + return EINVAL; + + if (__predict_false(class == FUTEX_CLASS_ANY)) return EINVAL; error = futex_key_init(&fk, vm, va, shared); @@ -734,7 +876,7 @@ futex_lookup_create(int *uaddr, bool sha * Optimistically assume there already is one, and try to find * it. */ - error = futex_lookup_by_key(&fk, shared, fp); + error = futex_lookup_by_key(&fk, shared, class, fp); if (error || *fp != NULL) { /* * We either found one, or there was an error. @@ -748,7 +890,7 @@ futex_lookup_create(int *uaddr, bool sha * Create a futex recoard. This tranfers ownership of the key * in all cases. */ - f = futex_create(&fk, shared); + f = futex_create(&fk, shared, class); if (f == NULL) { error = ENOMEM; goto out; @@ -775,222 +917,220 @@ out: if (f != NULL) } /* - * futex_wait_init(fw, bitset) - * - * Initialize a record for a thread to wait on a futex matching - * the specified bit set. Should be passed to futex_wait_enqueue - * before futex_wait, and should be passed to futex_wait_fini when - * done. - */ -static void -futex_wait_init(struct futex_wait *fw, int bitset) -{ - - KASSERT(bitset); - - mutex_init(&fw->fw_lock, MUTEX_DEFAULT, IPL_NONE); - cv_init(&fw->fw_cv, "futex"); - fw->fw_futex = NULL; - fw->fw_bitset = bitset; - fw->fw_aborting = false; -} - -/* - * futex_wait_fini(fw) - * - * Finalize a record for a futex waiter. Must not be on any - * futex's queue. - */ -static void -futex_wait_fini(struct futex_wait *fw) -{ - - KASSERT(fw->fw_futex == NULL); - - cv_destroy(&fw->fw_cv); - mutex_destroy(&fw->fw_lock); -} - -/* - * futex_wait_enqueue(fw, f) + * futex_unsleep: * - * Put fw on the futex queue. Must be done before futex_wait. - * Caller must hold fw's lock and f's lock, and fw must not be on - * any existing futex's waiter list. + * Remove an LWP from the futex and sleep queue. This is called when + * the LWP has not been awoken normally but instead interrupted: for + * example, when a signal is received. Must be called with the LWP + * locked. Will unlock if "unlock" is true. */ static void -futex_wait_enqueue(struct futex_wait *fw, struct futex *f) +futex_unsleep(lwp_t *l, bool unlock) { + struct futex *f __diagused; - KASSERT(mutex_owned(&f->fx_qlock)); - KASSERT(mutex_owned(&fw->fw_lock)); - KASSERT(fw->fw_futex == NULL); - KASSERT(!fw->fw_aborting); - - fw->fw_futex = f; - TAILQ_INSERT_TAIL(&f->fx_queue, fw, fw_entry); -} + f = (struct futex *)(uintptr_t)l->l_wchan; -/* - * futex_wait_dequeue(fw, f) - * - * Remove fw from the futex queue. Precludes subsequent - * futex_wait until a futex_wait_enqueue. Caller must hold fw's - * lock and f's lock, and fw must be on f. - */ -static void -futex_wait_dequeue(struct futex_wait *fw, struct futex *f) -{ + KASSERT(mutex_owned(f->fx_sq_lock)); - KASSERT(mutex_owned(&f->fx_qlock)); - KASSERT(mutex_owned(&fw->fw_lock)); - KASSERT(fw->fw_futex == f); + /* WRITERQ is more likely */ + if (__predict_true(l->l_sleepq == &f->fx_sqs[FUTEX_WRITERQ])) { + KASSERT(f->fx_nwaiters[FUTEX_WRITERQ] > 0); + f->fx_nwaiters[FUTEX_WRITERQ]--; + } else { + KASSERT(l->l_sleepq == &f->fx_sqs[FUTEX_READERQ]); + KASSERT(f->fx_nwaiters[FUTEX_READERQ] > 0); + f->fx_nwaiters[FUTEX_READERQ]--; + } - TAILQ_REMOVE(&f->fx_queue, fw, fw_entry); - fw->fw_futex = NULL; + sleepq_unsleep(l, unlock); } /* - * futex_wait_abort(fw) + * futex_wait(f, timeout, clkid, bitset) * - * Caller is no longer waiting for fw. Remove it from any queue - * if it was on one. Caller must hold fw->fw_lock. + * Wait until deadline on the clock clkid, or forever if deadline + * is NULL, for a futex wakeup. Return 0 on explicit wakeup, + * ETIMEDOUT on timeout, EINTR on signal. */ -static void -futex_wait_abort(struct futex_wait *fw) +static int +futex_wait(struct futex *f, int q, const struct timespec *deadline, + clockid_t clkid, int bitset) { - struct futex *f; - - KASSERT(mutex_owned(&fw->fw_lock)); /* - * Grab the futex queue. It can't go away as long as we hold - * fw_lock. However, we can't take the queue lock because - * that's a lock order reversal. + * Some things to note about how this function works: + * + * ==> When we enter futex_wait(), the futex's op lock is + * held, preventing us from missing wakes. Once we are on + * the futex's sleepq, it is safe to release the op lock. + * + * ==> We have a single early escape to avoid calling + * sleepq_block(): our deadline already having passed. + * If this is a no-timeout wait, or if the deadline has + * not already passed, we are guaranteed to call sleepq_block(). + * + * ==> sleepq_block() contains all of the necessary logic + * for handling signals; we do not need to check for them + * ourselves. + * + * ==> Once we have blocked, other futex operations will + * be able to wake us or requeue us. Until we have blocked, + * those other futex operations will not be able to acquire + * the sleepq locks in order to perform those operations, + * even if we have dropped the op lock. Thus, we will not + * miss wakes. This fundamental invariant is relied upon by + * every other synchronization object in the kernel. + * + * ==> sleepq_block() returns for one of three reasons: + * + * -- We were awakened. + * -- We were signaled. + * -- We timed out. + * + * ==> Once sleepq_block() returns, we will not call + * sleepq_block() again. + * + * ==> If sleepq_block() returns due to being signaled, + * we must check to see if we were also awakened. This + * is to handle the following sequence: + * + * -- Futex wake takes us off sleepq, places us on runq. + * -- We are signaled while sitting on the runq. + * -- We run, and sleepq_block() notices the signal and + * returns EINTR/ERESTART. + * + * In this situation, we want to indicate a successful wake + * to the caller, because that wake has been reported to the + * thread that issued it. + * + * Note that it is NOT possible for a wake to be issued after + * a signal; the LWP will already have been taken off the sleepq + * by the signal, so the wake will never happen. Note that for + * this reason, we must *never* return ERESTART, because it could + * result in us waiting again with no one to awaken us. */ - f = fw->fw_futex; - /* Put us on the abort list so that fq won't go away. */ - mutex_enter(&f->fx_abortlock); - LIST_INSERT_HEAD(&f->fx_abortlist, fw, fw_abort); - mutex_exit(&f->fx_abortlock); + struct lwp * const l = curlwp; + int timo; + int error; /* - * Mark fw as aborting so it won't lose wakeups and won't be - * transferred to any other queue. + * Compute our timeout before taking any locks. */ - fw->fw_aborting = true; + if (deadline) { + struct timespec ts; - /* f is now stable, so we can release fw_lock. */ - mutex_exit(&fw->fw_lock); + /* Check our watch. */ + error = clock_gettime1(clkid, &ts); + if (error) { + mutex_exit(&f->fx_op_lock); + return error; + } - /* Now we can remove fw under the queue lock. */ - mutex_enter(&f->fx_qlock); - mutex_enter(&fw->fw_lock); - futex_wait_dequeue(fw, f); - mutex_exit(&fw->fw_lock); - mutex_exit(&f->fx_qlock); + /* + * If we're past the deadline, ETIMEDOUT. + */ + if (timespeccmp(deadline, &ts, <=)) { + mutex_exit(&f->fx_op_lock); + return ETIMEDOUT; + } else { + /* Count how much time is left. */ + timespecsub(deadline, &ts, &ts); + timo = tstohz(&ts); + if (timo == 0) { + /* + * tstohz() already rounds up, and + * a return value of 0 ticks means + * "expired now or in the past". + */ + mutex_exit(&f->fx_op_lock); + return ETIMEDOUT; + } + } + } else { + timo = 0; + } /* - * Finally, remove us from the abort list and notify anyone - * waiting for the abort to complete if we were the last to go. + * Acquire in sleepq -> lwp order. While we're at it, ensure + * that there's room for us to block. */ - mutex_enter(&f->fx_abortlock); - LIST_REMOVE(fw, fw_abort); - if (LIST_EMPTY(&f->fx_abortlist)) - cv_broadcast(&f->fx_abortcv); - mutex_exit(&f->fx_abortlock); + mutex_spin_enter(f->fx_sq_lock); + if (__predict_false(q == FUTEX_READERQ && + f->fx_nwaiters[q] == FUTEX_TID_MASK)) { + mutex_spin_exit(f->fx_sq_lock); + mutex_exit(&f->fx_op_lock); + return ENFILE; + } + lwp_lock(l); /* - * Release our reference to the futex now that we are not - * waiting for it. + * No need for locks here; until we're on a futex's sleepq, these + * values are private to the LWP, and the locks needed to get onto + * the sleepq provide the memory barriers needed to ensure visibility. */ - futex_rele(f); + l->l_futex = f; + l->l_futex_wakesel = bitset; /* - * Reacquire the fw lock as caller expects. Verify that we're - * aborting and no longer associated with a futex. + * This is an inlined bit of sleepq_enter(); + * we already hold the lwp lock. */ - mutex_enter(&fw->fw_lock); - KASSERT(fw->fw_aborting); - KASSERT(fw->fw_futex == NULL); -} - -/* - * futex_wait(fw, deadline, clkid) - * - * fw must be a waiter on a futex's queue. Wait until deadline on - * the clock clkid, or forever if deadline is NULL, for a futex - * wakeup. Return 0 on explicit wakeup or destruction of futex, - * ETIMEDOUT on timeout, EINTR/ERESTART on signal. Either way, fw - * will no longer be on a futex queue on return. - */ -static int -futex_wait(struct futex_wait *fw, const struct timespec *deadline, - clockid_t clkid) -{ - int error = 0; - - /* Test and wait under the wait lock. */ - mutex_enter(&fw->fw_lock); - - for (;;) { - /* If we're done yet, stop and report success. */ - if (fw->fw_bitset == 0 || fw->fw_futex == NULL) { - error = 0; - break; - } - - /* If anything went wrong in the last iteration, stop. */ - if (error) - break; + lwp_unlock_to(l, f->fx_sq_lock); + KERNEL_UNLOCK_ALL(NULL, &l->l_biglocks); + KASSERT(lwp_locked(l, f->fx_sq_lock)); - /* Not done yet. Wait. */ - if (deadline) { - struct timespec ts; - - /* Check our watch. */ - error = clock_gettime1(clkid, &ts); - if (error) - break; + sleepq_enqueue(&f->fx_sqs[q], f, futex_wmesg, &futex_syncobj, true); + f->fx_nwaiters[q]++; - /* If we're past the deadline, ETIMEDOUT. */ - if (timespeccmp(deadline, &ts, <=)) { - error = ETIMEDOUT; - break; - } + /* We can now safely release the op lock. */ + mutex_exit(&f->fx_op_lock); - /* Count how much time is left. */ - timespecsub(deadline, &ts, &ts); + SDT_PROBE1(futex, wait, sleepq_block, entry, timo); + error = sleepq_block(timo, true); + SDT_PROBE1(futex, wait, sleepq_block, exit, error); - /* Wait for that much time, allowing signals. */ - error = cv_timedwait_sig(&fw->fw_cv, &fw->fw_lock, - tstohz(&ts)); - } else { - /* Wait indefinitely, allowing signals. */ - error = cv_wait_sig(&fw->fw_cv, &fw->fw_lock); - } - } + /* + * f is no longer valid; we may have been moved to another + * futex sleepq while we slept. + */ /* - * If we were woken up, the waker will have removed fw from the - * queue. But if anything went wrong, we must remove fw from - * the queue ourselves. While here, convert EWOULDBLOCK to - * ETIMEDOUT. + * If something went wrong, we may still have a futex reference. + * Check for that here and drop it if so. We can do this without + * taking any locks because l->l_futex is private to the LWP when + * not on any futex's sleepq, and we are not on any sleepq because + * we are running. + * + * Convert EWOULDBLOCK to ETIMEDOUT in case sleepq_block() returned + * EWOULDBLOCK, and ensure the only other error we return is EINTR. */ if (error) { - futex_wait_abort(fw); + f = l->l_futex; + if (f != NULL) { + SDT_PROBE0(futex, wait, finish, aborted); + l->l_futex = NULL; + futex_rele(f); + } else { + /* Raced with wakeup; report success. */ + SDT_PROBE0(futex, wait, finish, wakerace); + error = 0; + } if (error == EWOULDBLOCK) error = ETIMEDOUT; + else if (error != ETIMEDOUT) + error = EINTR; + } else { + KASSERT(l->l_futex == NULL); + SDT_PROBE0(futex, wait, finish, normally); } - mutex_exit(&fw->fw_lock); - return error; } /* - * futex_wake(f, nwake, f2, nrequeue, bitset) + * futex_wake(f, q, nwake, f2, q2, nrequeue, bitset) * * Wake up to nwake waiters on f matching bitset; then, if f2 is * provided, move up to nrequeue remaining waiters on f matching @@ -998,118 +1138,123 @@ futex_wait(struct futex_wait *fw, const * Caller must hold the locks of f and f2, if provided. */ static unsigned -futex_wake(struct futex *f, unsigned nwake, struct futex *f2, - unsigned nrequeue, int bitset) +futex_wake(struct futex *f, int q, unsigned int const nwake, + struct futex *f2, int q2, unsigned int const nrequeue, + int bitset) { - struct futex_wait *fw, *fw_next; + struct lwp *l, *l_next; unsigned nwoken = 0; - int hold_error __diagused; + unsigned nrequeued = 0; - KASSERT(mutex_owned(&f->fx_qlock)); - KASSERT(f2 == NULL || mutex_owned(&f2->fx_qlock)); + KASSERT(mutex_owned(&f->fx_op_lock)); + KASSERT(f2 == NULL || mutex_owned(&f2->fx_op_lock)); + + futex_sq_lock2(f, f2); /* Wake up to nwake waiters, and count the number woken. */ - TAILQ_FOREACH_SAFE(fw, &f->fx_queue, fw_entry, fw_next) { - if ((fw->fw_bitset & bitset) == 0) - continue; - if (nwake > 0) { - mutex_enter(&fw->fw_lock); - if (__predict_false(fw->fw_aborting)) { - mutex_exit(&fw->fw_lock); - continue; - } - futex_wait_dequeue(fw, f); - fw->fw_bitset = 0; - cv_broadcast(&fw->fw_cv); - mutex_exit(&fw->fw_lock); - nwake--; - nwoken++; - /* - * Drop the futex reference on behalf of the - * waiter. We assert this is not the last - * reference on the futex (our caller should - * also have one). - */ - futex_rele_not_last(f); - } else { + LIST_FOREACH_SAFE(l, &f->fx_sqs[q], l_sleepchain, l_next) { + if (nwoken == nwake) break; - } + + KASSERT(l->l_syncobj == &futex_syncobj); + KASSERT(l->l_wchan == (wchan_t)f); + KASSERT(l->l_futex == f); + KASSERT(l->l_sleepq == &f->fx_sqs[q]); + KASSERT(l->l_mutex == f->fx_sq_lock); + + if ((l->l_futex_wakesel & bitset) == 0) + continue; + + l->l_futex_wakesel = 0; + l->l_futex = NULL; + sleepq_remove(&f->fx_sqs[q], l); + f->fx_nwaiters[q]--; + nwoken++; + /* hold counts adjusted in bulk below */ } - if (f2) { + if (nrequeue) { + KASSERT(f2 != NULL); /* Move up to nrequeue waiters from f's queue to f2's queue. */ - TAILQ_FOREACH_SAFE(fw, &f->fx_queue, fw_entry, fw_next) { - if ((fw->fw_bitset & bitset) == 0) - continue; - if (nrequeue > 0) { - mutex_enter(&fw->fw_lock); - if (__predict_false(fw->fw_aborting)) { - mutex_exit(&fw->fw_lock); - continue; - } - futex_wait_dequeue(fw, f); - futex_wait_enqueue(fw, f2); - mutex_exit(&fw->fw_lock); - nrequeue--; - /* - * Transfer the reference from f to f2. - * As above, we assert that we are not - * dropping the last reference to f here. - * - * XXX futex_hold() could theoretically - * XXX fail here. - */ - futex_rele_not_last(f); - hold_error = futex_hold(f2); - KASSERT(hold_error == 0); - } else { + LIST_FOREACH_SAFE(l, &f->fx_sqs[q], l_sleepchain, l_next) { + if (nrequeued == nrequeue) break; - } + + KASSERT(l->l_syncobj == &futex_syncobj); + KASSERT(l->l_wchan == (wchan_t)f); + KASSERT(l->l_futex == f); + KASSERT(l->l_sleepq == &f->fx_sqs[q]); + KASSERT(l->l_mutex == f->fx_sq_lock); + + if ((l->l_futex_wakesel & bitset) == 0) + continue; + + l->l_futex = f2; + sleepq_transfer(l, &f->fx_sqs[q], + &f2->fx_sqs[q2], f2, futex_wmesg, + &futex_syncobj, f2->fx_sq_lock, true); + f->fx_nwaiters[q]--; + f2->fx_nwaiters[q2]++; + nrequeued++; + /* hold counts adjusted in bulk below */ + } + if (nrequeued) { + /* XXX futex_hold() could theoretically fail here. */ + int hold_error __diagused = + futex_hold_count(f2, nrequeued); + KASSERT(hold_error == 0); } - } else { - KASSERT(nrequeue == 0); } - /* Return the number of waiters woken. */ - return nwoken; + /* + * Adjust the futex reference counts for the wakes and + * requeues. + */ + KASSERT(nwoken + nrequeued <= LONG_MAX); + futex_rele_count_not_last(f, nwoken + nrequeued); + + futex_sq_unlock2(f, f2); + + /* Return the number of waiters woken and requeued. */ + return nwoken + nrequeued; } /* - * futex_queue_lock(f) + * futex_op_lock(f) * - * Acquire the queue lock of f. Pair with futex_queue_unlock. Do + * Acquire the op lock of f. Pair with futex_op_unlock. Do * not use if caller needs to acquire two locks; use - * futex_queue_lock2 instead. + * futex_op_lock2 instead. */ static void -futex_queue_lock(struct futex *f) +futex_op_lock(struct futex *f) { - mutex_enter(&f->fx_qlock); + mutex_enter(&f->fx_op_lock); } /* - * futex_queue_unlock(f) + * futex_op_unlock(f) * * Release the queue lock of f. */ static void -futex_queue_unlock(struct futex *f) +futex_op_unlock(struct futex *f) { - mutex_exit(&f->fx_qlock); + mutex_exit(&f->fx_op_lock); } /* - * futex_queue_lock2(f, f2) + * futex_op_lock2(f, f2) * - * Acquire the queue locks of both f and f2, which may be null, or - * which may have the same underlying queue. If they are - * distinct, an arbitrary total order is chosen on the locks. + * Acquire the op locks of both f and f2, which may be null, or + * which may be the same. If they are distinct, an arbitrary total + * order is chosen on the locks. * - * Callers should only ever acquire multiple queue locks - * simultaneously using futex_queue_lock2. + * Callers should only ever acquire multiple op locks + * simultaneously using futex_op_lock2. */ static void -futex_queue_lock2(struct futex *f, struct futex *f2) +futex_op_lock2(struct futex *f, struct futex *f2) { /* @@ -1119,37 +1264,37 @@ futex_queue_lock2(struct futex *f, struc if (f == NULL && f2 == NULL) { return; } else if (f == NULL) { - mutex_enter(&f2->fx_qlock); + mutex_enter(&f2->fx_op_lock); return; } else if (f2 == NULL) { - mutex_enter(&f->fx_qlock); + mutex_enter(&f->fx_op_lock); return; } /* If both futexes are the same, acquire only one. */ if (f == f2) { - mutex_enter(&f->fx_qlock); + mutex_enter(&f->fx_op_lock); return; } /* Otherwise, use the ordering on the kva of the futex pointer. */ if ((uintptr_t)f < (uintptr_t)f2) { - mutex_enter(&f->fx_qlock); - mutex_enter(&f2->fx_qlock); + mutex_enter(&f->fx_op_lock); + mutex_enter(&f2->fx_op_lock); } else { - mutex_enter(&f2->fx_qlock); - mutex_enter(&f->fx_qlock); + mutex_enter(&f2->fx_op_lock); + mutex_enter(&f->fx_op_lock); } } /* - * futex_queue_unlock2(f, f2) + * futex_op_unlock2(f, f2) * * Release the queue locks of both f and f2, which may be null, or * which may have the same underlying queue. */ static void -futex_queue_unlock2(struct futex *f, struct futex *f2) +futex_op_unlock2(struct futex *f, struct futex *f2) { /* @@ -1159,33 +1304,33 @@ futex_queue_unlock2(struct futex *f, str if (f == NULL && f2 == NULL) { return; } else if (f == NULL) { - mutex_exit(&f2->fx_qlock); + mutex_exit(&f2->fx_op_lock); return; } else if (f2 == NULL) { - mutex_exit(&f->fx_qlock); + mutex_exit(&f->fx_op_lock); return; } /* If both futexes are the same, release only one. */ if (f == f2) { - mutex_exit(&f->fx_qlock); + mutex_exit(&f->fx_op_lock); return; } /* Otherwise, use the ordering on the kva of the futex pointer. */ if ((uintptr_t)f < (uintptr_t)f2) { - mutex_exit(&f2->fx_qlock); - mutex_exit(&f->fx_qlock); + mutex_exit(&f2->fx_op_lock); + mutex_exit(&f->fx_op_lock); } else { - mutex_exit(&f->fx_qlock); - mutex_exit(&f2->fx_qlock); + mutex_exit(&f->fx_op_lock); + mutex_exit(&f2->fx_op_lock); } } /* * futex_func_wait(uaddr, val, val3, timeout, clkid, clkflags, retval) * - * Implement futex(FUTEX_WAIT). + * Implement futex(FUTEX_WAIT) and futex(FUTEX_WAIT_BITSET). */ static int futex_func_wait(bool shared, int *uaddr, int val, int val3, @@ -1193,7 +1338,6 @@ futex_func_wait(bool shared, int *uaddr, register_t *retval) { struct futex *f; - struct futex_wait wait, *fw = &wait; struct timespec ts; const struct timespec *deadline; int error; @@ -1210,62 +1354,71 @@ futex_func_wait(bool shared, int *uaddr, return EAGAIN; /* Determine a deadline on the specified clock. */ - if (timeout == NULL || (clkflags & TIMER_ABSTIME) == TIMER_ABSTIME) { + if (timeout == NULL) { + deadline = timeout; + } else if ((clkflags & TIMER_ABSTIME) == TIMER_ABSTIME) { + /* Sanity-check the deadline. */ + if (timeout->tv_sec < 0 || + timeout->tv_nsec < 0 || + timeout->tv_nsec >= 1000000000L) { + return EINVAL; + } deadline = timeout; } else { + struct timespec interval = *timeout; + + error = itimespecfix(&interval); + if (error) + return error; error = clock_gettime1(clkid, &ts); if (error) return error; - timespecadd(&ts, timeout, &ts); + timespecadd(&ts, &interval, &ts); deadline = &ts; } /* Get the futex, creating it if necessary. */ - error = futex_lookup_create(uaddr, shared, &f); + error = futex_lookup_create(uaddr, shared, FUTEX_CLASS_NORMAL, &f); if (error) return error; KASSERT(f); - /* Get ready to wait. */ - futex_wait_init(fw, val3); - /* - * Under the queue lock, check the value again: if it has + * Under the op lock, check the value again: if it has * already changed, EAGAIN; otherwise enqueue the waiter. * Since FUTEX_WAKE will use the same lock and be done after * modifying the value, the order in which we check and enqueue * is immaterial. */ - futex_queue_lock(f); + futex_op_lock(f); if (!futex_test(uaddr, val)) { - futex_queue_unlock(f); + futex_op_unlock(f); error = EAGAIN; goto out; } - mutex_enter(&fw->fw_lock); - futex_wait_enqueue(fw, f); - mutex_exit(&fw->fw_lock); - futex_queue_unlock(f); + + /* + * Now wait. futex_wait() will drop our op lock once we + * are entered into the sleep queue, thus ensuring atomicity + * of wakes with respect to waits. + */ + error = futex_wait(f, FUTEX_WRITERQ, deadline, clkid, val3); /* * We cannot drop our reference to the futex here, because * we might be enqueued on a different one when we are awakened. - * The references will be managed on our behalf in the requeue - * and wake cases. + * The references will be managed on our behalf in the requeue, + * wake, and error cases. */ f = NULL; - /* Wait. */ - error = futex_wait(fw, deadline, clkid); - if (error) - goto out; - - /* Return 0 on success, error on failure. */ - *retval = 0; + if (__predict_true(error == 0)) { + /* Return 0 on success, error on failure. */ + *retval = 0; + } out: if (f != NULL) futex_rele(f); - futex_wait_fini(fw); return error; } @@ -1288,7 +1441,7 @@ futex_func_wake(bool shared, int *uaddr, } /* Look up the futex, if any. */ - error = futex_lookup(uaddr, shared, &f); + error = futex_lookup(uaddr, shared, FUTEX_CLASS_NORMAL, &f); if (error) goto out; @@ -1297,12 +1450,13 @@ futex_func_wake(bool shared, int *uaddr, goto out; /* - * Under f's queue lock, wake the waiters and remember the + * Under f's op lock, wake the waiters and remember the * number woken. */ - futex_queue_lock(f); - nwoken = futex_wake(f, val, NULL, 0, val3); - futex_queue_unlock(f); + futex_op_lock(f); + nwoken = futex_wake(f, FUTEX_WRITERQ, val, + NULL, FUTEX_WRITERQ, 0, val3); + futex_op_unlock(f); /* Release the futex. */ futex_rele(f); @@ -1335,7 +1489,7 @@ futex_func_requeue(bool shared, int op, } /* Look up the source futex, if any. */ - error = futex_lookup(uaddr, shared, &f); + error = futex_lookup(uaddr, shared, FUTEX_CLASS_NORMAL, &f); if (error) goto out; @@ -1347,22 +1501,24 @@ futex_func_requeue(bool shared, int op, * We may need to create the destination futex because it's * entirely possible it does not currently have any waiters. */ - error = futex_lookup_create(uaddr2, shared, &f2); + error = futex_lookup_create(uaddr2, shared, FUTEX_CLASS_NORMAL, &f2); if (error) goto out; /* - * Under the futexes' queue locks, check the value; if + * Under the futexes' op locks, check the value; if * unchanged from val3, wake the waiters. */ - futex_queue_lock2(f, f2); + futex_op_lock2(f, f2); if (op == FUTEX_CMP_REQUEUE && !futex_test(uaddr, val3)) { error = EAGAIN; } else { error = 0; - nwoken = futex_wake(f, val, f2, val2, FUTEX_BITSET_MATCH_ANY); + nwoken = futex_wake(f, FUTEX_WRITERQ, val, + f2, FUTEX_WRITERQ, val2, + FUTEX_BITSET_MATCH_ANY); } - futex_queue_unlock2(f, f2); + futex_op_unlock2(f, f2); out: /* Return the number of waiters woken. */ @@ -1526,23 +1682,23 @@ futex_func_wake_op(bool shared, int *uad goto out; /* Look up the first futex, if any. */ - error = futex_lookup(uaddr, shared, &f); + error = futex_lookup(uaddr, shared, FUTEX_CLASS_NORMAL, &f); if (error) goto out; /* Look up the second futex, if any. */ - error = futex_lookup(uaddr2, shared, &f2); + error = futex_lookup(uaddr2, shared, FUTEX_CLASS_NORMAL, &f2); if (error) goto out; /* - * Under the queue locks: + * Under the op locks: * * 1. Read/modify/write: *uaddr2 op= oparg. * 2. Unconditionally wake uaddr. - * 3. Conditionally wake uaddr2, if it previously matched val2. + * 3. Conditionally wake uaddr2, if it previously matched val3. */ - futex_queue_lock2(f, f2); + futex_op_lock2(f, f2); do { error = futex_load(uaddr2, &oldval); if (error) @@ -1552,15 +1708,18 @@ futex_func_wake_op(bool shared, int *uad if (error) goto out_unlock; } while (actual != oldval); - nwoken = (f ? futex_wake(f, val, NULL, 0, FUTEX_BITSET_MATCH_ANY) : 0); + nwoken = (f ? futex_wake(f, FUTEX_WRITERQ, val, + NULL, FUTEX_WRITERQ, 0, + FUTEX_BITSET_MATCH_ANY) : 0); if (f2 && futex_compute_cmp(oldval, val3)) - nwoken += futex_wake(f2, val2, NULL, 0, - FUTEX_BITSET_MATCH_ANY); + nwoken += futex_wake(f2, FUTEX_WRITERQ, val2, + NULL, FUTEX_WRITERQ, 0, + FUTEX_BITSET_MATCH_ANY); /* Success! */ error = 0; out_unlock: - futex_queue_unlock2(f, f2); + futex_op_unlock2(f, f2); out: /* Return the number of waiters woken. */ @@ -1587,38 +1746,76 @@ do_futex(int *uaddr, int op, int val, co const bool shared = (op & FUTEX_PRIVATE_FLAG) ? false : true; const clockid_t clkid = (op & FUTEX_CLOCK_REALTIME) ? CLOCK_REALTIME : CLOCK_MONOTONIC; + int error; op &= FUTEX_CMD_MASK; switch (op) { case FUTEX_WAIT: - return futex_func_wait(shared, uaddr, val, + SDT_PROBE6(futex, func, wait, entry, + uaddr, val, FUTEX_BITSET_MATCH_ANY, timeout, + TIMER_RELTIME, op & ~FUTEX_CMD_MASK); + error = futex_func_wait(shared, uaddr, val, FUTEX_BITSET_MATCH_ANY, timeout, clkid, TIMER_RELTIME, retval); + SDT_PROBE1(futex, func, wait, exit, error); + break; + + case FUTEX_WAIT_BITSET: + SDT_PROBE6(futex, func, wait, entry, + uaddr, val, val3, timeout, + TIMER_ABSTIME, op & ~FUTEX_CMD_MASK); + error = futex_func_wait(shared, uaddr, val, val3, timeout, + clkid, TIMER_ABSTIME, retval); + SDT_PROBE1(futex, func, wait, exit, error); + break; case FUTEX_WAKE: - val3 = FUTEX_BITSET_MATCH_ANY; - /* FALLTHROUGH */ + SDT_PROBE4(futex, func, wake, entry, + uaddr, val, FUTEX_BITSET_MATCH_ANY, op & ~FUTEX_CMD_MASK); + error = futex_func_wake(shared, uaddr, val, + FUTEX_BITSET_MATCH_ANY, retval); + SDT_PROBE2(futex, func, wake, exit, error, *retval); + break; + case FUTEX_WAKE_BITSET: - return futex_func_wake(shared, uaddr, val, val3, retval); + SDT_PROBE4(futex, func, wake, entry, + uaddr, val, val3, op & ~FUTEX_CMD_MASK); + error = futex_func_wake(shared, uaddr, val, val3, retval); + SDT_PROBE2(futex, func, wake, exit, error, *retval); + break; case FUTEX_REQUEUE: + SDT_PROBE5(futex, func, requeue, entry, + uaddr, val, uaddr2, val2, op & ~FUTEX_CMD_MASK); + error = futex_func_requeue(shared, op, uaddr, val, uaddr2, + val2, 0, retval); + SDT_PROBE2(futex, func, requeue, exit, error, *retval); + break; + case FUTEX_CMP_REQUEUE: - return futex_func_requeue(shared, op, uaddr, val, uaddr2, + SDT_PROBE6(futex, func, cmp_requeue, entry, + uaddr, val, uaddr2, val2, val3, op & ~FUTEX_CMD_MASK); + error = futex_func_requeue(shared, op, uaddr, val, uaddr2, val2, val3, retval); - - case FUTEX_WAIT_BITSET: - return futex_func_wait(shared, uaddr, val, val3, timeout, - clkid, TIMER_ABSTIME, retval); + SDT_PROBE2(futex, func, cmp_requeue, exit, error, *retval); + break; case FUTEX_WAKE_OP: - return futex_func_wake_op(shared, uaddr, val, uaddr2, val2, + SDT_PROBE6(futex, func, wake_op, entry, + uaddr, val, uaddr2, val2, val3, op & ~FUTEX_CMD_MASK); + error = futex_func_wake_op(shared, uaddr, val, uaddr2, val2, val3, retval); + SDT_PROBE2(futex, func, wake_op, exit, error, *retval); + break; case FUTEX_FD: default: - return ENOSYS; + error = ENOSYS; + break; } + + return error; } /* @@ -1730,6 +1927,7 @@ release_futex(uintptr_t const uptr, lwpi struct futex *f; int oldval, newval, actual; int error; + bool shared; /* If it's misaligned, tough. */ if (__predict_false(uptr & 3)) @@ -1760,8 +1958,11 @@ release_futex(uintptr_t const uptr, lwpi */ if (__predict_false(is_pending && (oldval & ~FUTEX_WAITERS) == 0)) { register_t retval; - (void) futex_func_wake(/*shared*/true, uaddr, 1, + error = futex_func_wake(/*shared*/true, uaddr, 1, FUTEX_BITSET_MATCH_ANY, &retval); + if (error != 0 || retval == 0) + (void) futex_func_wake(/*shared*/false, uaddr, 1, + FUTEX_BITSET_MATCH_ANY, &retval); return; } @@ -1805,22 +2006,23 @@ release_futex(uintptr_t const uptr, lwpi } /* - * Look for a shared futex since we have no positive indication - * it is private. If we can't, tough. - */ - error = futex_lookup(uaddr, /*shared*/true, &f); - if (error) - return; - - /* - * If there's no kernel state for this futex, there's nothing to - * release. + * Look for a futex. Try shared first, then private. If we + * can't fine one, tough. + * + * Note: the assumption here is that anyone placing a futex on + * the robust list is adhering to the rules, regardless of the + * futex class. */ - if (f == NULL) - return; + for (f = NULL, shared = true; f == NULL; shared = false) { + error = futex_lookup(uaddr, shared, FUTEX_CLASS_ANY, &f); + if (error) + return; + if (f == NULL && shared == false) + return; + } - /* Work under the futex queue lock. */ - futex_queue_lock(f); + /* Work under the futex op lock. */ + futex_op_lock(f); /* * Fetch the word: if the tid doesn't match ours, skip; @@ -1844,11 +2046,14 @@ release_futex(uintptr_t const uptr, lwpi * * XXX eventual PI handling? */ - if (oldval & FUTEX_WAITERS) - (void)futex_wake(f, 1, NULL, 0, FUTEX_BITSET_MATCH_ANY); + if (oldval & FUTEX_WAITERS) { + (void)futex_wake(f, FUTEX_WRITERQ, 1, + NULL, FUTEX_WRITERQ, 0, + FUTEX_BITSET_MATCH_ANY); + } /* Unlock the queue and release the futex. */ -out: futex_queue_unlock(f); +out: futex_op_unlock(f); futex_rele(f); } Index: src/sys/sys/lwp.h diff -u src/sys/sys/lwp.h:1.212 src/sys/sys/lwp.h:1.212.14.1 --- src/sys/sys/lwp.h:1.212 Fri Oct 23 00:25:45 2020 +++ src/sys/sys/lwp.h Thu Aug 5 23:14:21 2021 @@ -1,4 +1,4 @@ -/* $NetBSD: lwp.h,v 1.212 2020/10/23 00:25:45 thorpej Exp $ */ +/* $NetBSD: lwp.h,v 1.212.14.1 2021/08/05 23:14:21 thorpej Exp $ */ /* * Copyright (c) 2001, 2006, 2007, 2008, 2009, 2010, 2019, 2020 @@ -72,6 +72,7 @@ static __inline struct cpu_info *lwp_get * S: l_selcluster->sc_lock * (: unlocked, stable * !: unlocked, may only be reliably accessed by the LWP itself + * x: special; see comments for field. * * Fields are clustered together by usage (to increase the likelihood * of cache hits) and by size (to reduce dead space in the structure). @@ -79,6 +80,7 @@ static __inline struct cpu_info *lwp_get #include <sys/pcu.h> +struct futex; struct lockdebug; struct sysent; @@ -139,9 +141,19 @@ struct lwp { u_int l_slptime; /* l: time since last blocked */ bool l_vforkwaiting; /* a: vfork() waiting */ - /* User-space synchronization. */ + /* + * User-space synchronization. + * + * Special locking considerations: + * + * l_futex and l_futex_wakesel are acccessed unlocked and private + * to the LWP *unless* the LWP is present on a futex sleepq, in + * which case they are protected by the lwp_lock (which will in + * actuality be the futex sleepq lock). + */ uintptr_t l_robust_head; /* !: list of robust futexes */ - uint32_t l___rsvd1; /* reserved for future use */ + struct futex *l_futex; /* x: futex we're waiting on */ + uint32_t l_futex_wakesel;/* x: futex wake selector */ #if PCU_UNIT_COUNT > 0 struct cpu_info * volatile l_pcu_cpu[PCU_UNIT_COUNT];