/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2009-2021 Dmitry Chagin <dchagin@FreeBSD.org>
 * Copyright (c) 2008 Roman Divacky
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/imgact.h>
#include <sys/imgact_elf.h>
#include <sys/ktr.h>
#include <sys/lock.h>
#include <sys/mutex.h>
#include <sys/priv.h>
#include <sys/proc.h>
#include <sys/sched.h>
#include <sys/sysent.h>
#include <sys/vnode.h>
#include <sys/umtxvar.h>

#ifdef COMPAT_LINUX32
#include <machine/../linux32/linux.h>
#include <machine/../linux32/linux32_proto.h>
#else
#include <machine/../linux/linux.h>
#include <machine/../linux/linux_proto.h>
#endif
#include <compat/linux/linux_emul.h>
#include <compat/linux/linux_futex.h>
#include <compat/linux/linux_misc.h>
#include <compat/linux/linux_time.h>
#include <compat/linux/linux_util.h>

#define FUTEX_SHARED    0x8     /* shared futex */
#define FUTEX_UNOWNED   0

#define GET_SHARED(a)   (a->flags & FUTEX_SHARED) ? AUTO_SHARE : THREAD_SHARE

static int futex_atomic_op(struct thread *, int, uint32_t *, int *);
static int handle_futex_death(struct thread *td, struct linux_emuldata *,
    uint32_t *, unsigned int, bool);
static int fetch_robust_entry(struct linux_robust_list **,
    struct linux_robust_list **, unsigned int *);

struct linux_futex_args {
        uint32_t        *uaddr;
        int32_t         op;
        uint32_t        flags;
        bool            clockrt;
        uint32_t        val;
        struct timespec *ts;
        uint32_t        *uaddr2;
        uint32_t        val3;
        bool            val3_compare;
        struct timespec kts;
};

static inline int futex_key_get(const void *, int, int, struct umtx_key *);
static void linux_umtx_abs_timeout_init(struct umtx_abs_timeout *,
            struct linux_futex_args *);
static int linux_futex(struct thread *, struct linux_futex_args *);
static int linux_futex_wait(struct thread *, struct linux_futex_args *);
static int linux_futex_wake(struct thread *, struct linux_futex_args *);
static int linux_futex_requeue(struct thread *, struct linux_futex_args *);
static int linux_futex_wakeop(struct thread *, struct linux_futex_args *);
static int linux_futex_lock_pi(struct thread *, bool, struct linux_futex_args *);
static int linux_futex_unlock_pi(struct thread *, bool,
            struct linux_futex_args *);
static int futex_wake_pi(struct thread *, uint32_t *, bool);

static int
futex_key_get(const void *uaddr, int type, int share, struct umtx_key *key)
{

        /* Check that futex address is a 32bit aligned. */
        if (!__is_aligned(uaddr, sizeof(uint32_t)))
                return (EINVAL);
        return (umtx_key_get(uaddr, type, share, key));
}

int
futex_wake(struct thread *td, uint32_t *uaddr, int val, bool shared)
{
        struct linux_futex_args args;

        bzero(&args, sizeof(args));
        args.op = LINUX_FUTEX_WAKE;
        args.uaddr = uaddr;
        args.flags = shared == true ? FUTEX_SHARED : 0;
        args.val = val;
        args.val3 = FUTEX_BITSET_MATCH_ANY;

        return (linux_futex_wake(td, &args));
}

static int
futex_wake_pi(struct thread *td, uint32_t *uaddr, bool shared)
{
        struct linux_futex_args args;

        bzero(&args, sizeof(args));
        args.op = LINUX_FUTEX_UNLOCK_PI;
        args.uaddr = uaddr;
        args.flags = shared == true ? FUTEX_SHARED : 0;

        return (linux_futex_unlock_pi(td, true, &args));
}

static int
futex_atomic_op(struct thread *td, int encoded_op, uint32_t *uaddr,
    int *res)
{
        int op = (encoded_op >> 28) & 7;
        int cmp = (encoded_op >> 24) & 15;
        int oparg = (encoded_op << 8) >> 20;
        int cmparg = (encoded_op << 20) >> 20;
        int oldval = 0, ret;

        if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28))
                oparg = 1 << oparg;

        switch (op) {
        case FUTEX_OP_SET:
                ret = futex_xchgl(oparg, uaddr, &oldval);
                break;
        case FUTEX_OP_ADD:
                ret = futex_addl(oparg, uaddr, &oldval);
                break;
        case FUTEX_OP_OR:
                ret = futex_orl(oparg, uaddr, &oldval);
                break;
        case FUTEX_OP_ANDN:
                ret = futex_andl(~oparg, uaddr, &oldval);
                break;
        case FUTEX_OP_XOR:
                ret = futex_xorl(oparg, uaddr, &oldval);
                break;
        default:
                ret = ENOSYS;
                break;
        }

        if (ret != 0)
                return (ret);

        switch (cmp) {
        case FUTEX_OP_CMP_EQ:
                *res = (oldval == cmparg);
                break;
        case FUTEX_OP_CMP_NE:
                *res = (oldval != cmparg);
                break;
        case FUTEX_OP_CMP_LT:
                *res = (oldval < cmparg);
                break;
        case FUTEX_OP_CMP_GE:
                *res = (oldval >= cmparg);
                break;
        case FUTEX_OP_CMP_LE:
                *res = (oldval <= cmparg);
                break;
        case FUTEX_OP_CMP_GT:
                *res = (oldval > cmparg);
                break;
        default:
                ret = ENOSYS;
        }

        return (ret);
}

static int
linux_futex(struct thread *td, struct linux_futex_args *args)
{
        struct linux_pemuldata *pem;
        struct proc *p;

        if (args->op & LINUX_FUTEX_PRIVATE_FLAG) {
                args->flags = 0;
                args->op &= ~LINUX_FUTEX_PRIVATE_FLAG;
        } else
                args->flags = FUTEX_SHARED;

        args->clockrt = args->op & LINUX_FUTEX_CLOCK_REALTIME;
        args->op = args->op & ~LINUX_FUTEX_CLOCK_REALTIME;

        if (args->clockrt &&
            args->op != LINUX_FUTEX_WAIT_BITSET &&
            args->op != LINUX_FUTEX_WAIT_REQUEUE_PI &&
            args->op != LINUX_FUTEX_LOCK_PI2)
                return (ENOSYS);

        switch (args->op) {
        case LINUX_FUTEX_WAIT:
                args->val3 = FUTEX_BITSET_MATCH_ANY;
                /* FALLTHROUGH */

        case LINUX_FUTEX_WAIT_BITSET:
                LINUX_CTR3(sys_futex, "WAIT uaddr %p val 0x%x bitset 0x%x",
                    args->uaddr, args->val, args->val3);

                return (linux_futex_wait(td, args));

        case LINUX_FUTEX_WAKE:
                args->val3 = FUTEX_BITSET_MATCH_ANY;
                /* FALLTHROUGH */

        case LINUX_FUTEX_WAKE_BITSET:
                LINUX_CTR3(sys_futex, "WAKE uaddr %p nrwake 0x%x bitset 0x%x",
                    args->uaddr, args->val, args->val3);

                return (linux_futex_wake(td, args));

        case LINUX_FUTEX_REQUEUE:
                /*
                 * Glibc does not use this operation since version 2.3.3,
                 * as it is racy and replaced by FUTEX_CMP_REQUEUE operation.
                 * Glibc versions prior to 2.3.3 fall back to FUTEX_WAKE when
                 * FUTEX_REQUEUE returned EINVAL.
                 */
                pem = pem_find(td->td_proc);
                if ((pem->flags & LINUX_XDEPR_REQUEUEOP) == 0) {
                        linux_msg(td, "unsupported FUTEX_REQUEUE");
                        pem->flags |= LINUX_XDEPR_REQUEUEOP;
                }

                /*
                 * The above is true, however musl libc does make use of the
                 * futex requeue operation, allow operation for brands which
                 * set LINUX_BI_FUTEX_REQUEUE bit of Brandinfo flags.
                 */
                p = td->td_proc;
                const Elf_Brandinfo *bi = p->p_elf_brandinfo;
                if (bi == NULL || ((bi->flags & LINUX_BI_FUTEX_REQUEUE)) == 0)
                        return (EINVAL);
                args->val3_compare = false;
                /* FALLTHROUGH */

        case LINUX_FUTEX_CMP_REQUEUE:
                LINUX_CTR5(sys_futex, "CMP_REQUEUE uaddr %p "
                    "nrwake 0x%x uval 0x%x uaddr2 %p nrequeue 0x%x",
                    args->uaddr, args->val, args->val3, args->uaddr2,
                    args->ts);

                return (linux_futex_requeue(td, args));

        case LINUX_FUTEX_WAKE_OP:
                LINUX_CTR5(sys_futex, "WAKE_OP "
                    "uaddr %p nrwake 0x%x uaddr2 %p op 0x%x nrwake2 0x%x",
                    args->uaddr, args->val, args->uaddr2, args->val3,
                    args->ts);

                return (linux_futex_wakeop(td, args));

        case LINUX_FUTEX_LOCK_PI:
                args->clockrt = true;
                /* FALLTHROUGH */

        case LINUX_FUTEX_LOCK_PI2:
                LINUX_CTR2(sys_futex, "LOCKPI uaddr %p val 0x%x",
                    args->uaddr, args->val);

                return (linux_futex_lock_pi(td, false, args));

        case LINUX_FUTEX_UNLOCK_PI:
                LINUX_CTR1(sys_futex, "UNLOCKPI uaddr %p",
                    args->uaddr);

                return (linux_futex_unlock_pi(td, false, args));

        case LINUX_FUTEX_TRYLOCK_PI:
                LINUX_CTR1(sys_futex, "TRYLOCKPI uaddr %p",
                    args->uaddr);

                return (linux_futex_lock_pi(td, true, args));

        /*
         * Current implementation of FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI
         * can't be used anymore to implement conditional variables.
         * A detailed explanation can be found here:
         *
         * https://sourceware.org/bugzilla/show_bug.cgi?id=13165
         * and here http://austingroupbugs.net/view.php?id=609
         *
         * And since commit
         * https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=ed19993b5b0d05d62cc883571519a67dae481a14
         * glibc does not use them.
         */
        case LINUX_FUTEX_WAIT_REQUEUE_PI:
                /* not yet implemented */
                pem = pem_find(td->td_proc);
                if ((pem->flags & LINUX_XUNSUP_FUTEXPIOP) == 0) {
                        linux_msg(td, "unsupported FUTEX_WAIT_REQUEUE_PI");
                        pem->flags |= LINUX_XUNSUP_FUTEXPIOP;
                }
                return (ENOSYS);

        case LINUX_FUTEX_CMP_REQUEUE_PI:
                /* not yet implemented */
                pem = pem_find(td->td_proc);
                if ((pem->flags & LINUX_XUNSUP_FUTEXPIOP) == 0) {
                        linux_msg(td, "unsupported FUTEX_CMP_REQUEUE_PI");
                        pem->flags |= LINUX_XUNSUP_FUTEXPIOP;
                }
                return (ENOSYS);

        default:
                linux_msg(td, "unsupported futex op %d", args->op);
                return (ENOSYS);
        }
}

/*
 * pi protocol:
 * - 0 futex word value means unlocked.
 * - TID futex word value means locked.
 * Userspace uses atomic ops to lock/unlock these futexes without entering the
 * kernel. If the lock-acquire fastpath fails, (transition from 0 to TID fails),
 * then FUTEX_LOCK_PI is called.
 * The kernel atomically set FUTEX_WAITERS bit in the futex word value, if no
 * other waiters exists looks up the thread that owns the futex (it has put its
 * own TID into the futex value) and made this thread the owner of the internal
 * pi-aware lock object (mutex). Then the kernel tries to lock the internal lock
 * object, on which it blocks. Once it returns, it has the mutex acquired, and it
 * sets the futex value to its own TID and returns (futex value contains
 * FUTEX_WAITERS|TID).
 * The unlock fastpath would fail (because the FUTEX_WAITERS bit is set) and
 * FUTEX_UNLOCK_PI will be called.
 * If a futex is found to be held at exit time, the kernel sets the OWNER_DIED
 * bit of the futex word and wakes up the next futex waiter (if any), WAITERS
 * bit is preserved (if any).
 * If OWNER_DIED bit is set the kernel sanity checks the futex word value against
 * the internal futex state and if correct, acquire futex.
 */
static int
linux_futex_lock_pi(struct thread *td, bool try, struct linux_futex_args *args)
{
        struct umtx_abs_timeout timo;
        struct linux_emuldata *em;
        struct umtx_pi *pi, *new_pi;
        struct thread *td1;
        struct umtx_q *uq;
        int error, rv;
        uint32_t owner, old_owner;

        em = em_find(td);
        uq = td->td_umtxq;
        error = futex_key_get(args->uaddr, TYPE_PI_FUTEX, GET_SHARED(args),
            &uq->uq_key);
        if (error != 0)
                return (error);
        if (args->ts != NULL)
                linux_umtx_abs_timeout_init(&timo, args);

        umtxq_lock(&uq->uq_key);
        pi = umtx_pi_lookup(&uq->uq_key);
        if (pi == NULL) {
                new_pi = umtx_pi_alloc(M_NOWAIT);
                if (new_pi == NULL) {
                        umtxq_unlock(&uq->uq_key);
                        new_pi = umtx_pi_alloc(M_WAITOK);
                        umtxq_lock(&uq->uq_key);
                        pi = umtx_pi_lookup(&uq->uq_key);
                        if (pi != NULL) {
                                umtx_pi_free(new_pi);
                                new_pi = NULL;
                        }
                }
                if (new_pi != NULL) {
                        new_pi->pi_key = uq->uq_key;
                        umtx_pi_insert(new_pi);
                        pi = new_pi;
                }
        }
        umtx_pi_ref(pi);
        umtxq_unlock(&uq->uq_key);
        for (;;) {
                /* Try uncontested case first. */
                rv = casueword32(args->uaddr, FUTEX_UNOWNED, &owner, em->em_tid);
                /* The acquire succeeded. */
                if (rv == 0) {
                        error = 0;
                        break;
                }
                if (rv == -1) {
                        error = EFAULT;
                        break;
                }

                /*
                 * Nobody owns it, but the acquire failed. This can happen
                 * with ll/sc atomic.
                 */
                if (owner == FUTEX_UNOWNED) {
                        error = thread_check_susp(td, true);
                        if (error != 0)
                                break;
                        continue;
                }

                /*
                 * Avoid overwriting a possible error from sleep due
                 * to the pending signal with suspension check result.
                 */
                if (error == 0) {
                        error = thread_check_susp(td, true);
                        if (error != 0)
                                break;
                }

                /* The futex word at *uaddr is already locked by the caller. */
                if ((owner & FUTEX_TID_MASK) == em->em_tid) {
                        error = EDEADLK;
                        break;
                }

                /*
                 * Futex owner died, handle_futex_death() set the OWNER_DIED bit
                 * and clear tid. Try to acquire it.
                 */
                if ((owner & FUTEX_TID_MASK) == FUTEX_UNOWNED) {
                        old_owner = owner;
                        owner = owner & (FUTEX_WAITERS | FUTEX_OWNER_DIED);
                        owner |= em->em_tid;
                        rv = casueword32(args->uaddr, old_owner, &owner, owner);
                        if (rv == -1) {
                                error = EFAULT;
                                break;
                        }
                        if (rv == 1) {
                                if (error == 0) {
                                        error = thread_check_susp(td, true);
                                        if (error != 0)
                                                break;
                                }

                                /*
                                 * If this failed the lock could
                                 * changed, restart.
                                 */
                                continue;
                        }

                        umtxq_lock(&uq->uq_key);
                        umtxq_busy(&uq->uq_key);
                        error = umtx_pi_claim(pi, td);
                        umtxq_unbusy(&uq->uq_key);
                        umtxq_unlock(&uq->uq_key);
                        if (error != 0) {
                                /*
                                 * Since we're going to return an
                                 * error, restore the futex to its
                                 * previous, unowned state to avoid
                                 * compounding the problem.
                                 */
                                (void)casuword32(args->uaddr, owner, old_owner);
                        }
                        break;
                }

                /*
                 * Inconsistent state: OWNER_DIED is set and tid is not 0.
                 * Linux does some checks of futex state, we return EINVAL,
                 * as the user space can take care of this.
                 */
                if ((owner & FUTEX_OWNER_DIED) != FUTEX_UNOWNED) {
                        error = EINVAL;
                        break;
                }

                if (try != 0) {
                        error = EBUSY;
                        break;
                }

                /*
                 * If we caught a signal, we have retried and now
                 * exit immediately.
                 */
                if (error != 0)
                        break;

                umtxq_busy_unlocked(&uq->uq_key);

                /*
                 * Set the contested bit so that a release in user space knows
                 * to use the system call for unlock. If this fails either some
                 * one else has acquired the lock or it has been released.
                 */
                rv = casueword32(args->uaddr, owner, &owner,
                    owner | FUTEX_WAITERS);
                if (rv == -1) {
                        umtxq_unbusy_unlocked(&uq->uq_key);
                        error = EFAULT;
                        break;
                }
                if (rv == 1) {
                        umtxq_unbusy_unlocked(&uq->uq_key);
                        error = thread_check_susp(td, true);
                        if (error != 0)
                                break;

                        /*
                         * The lock changed and we need to retry or we
                         * lost a race to the thread unlocking the umtx.
                         */
                        continue;
                }

                /*
                 * Substitute Linux thread id by native thread id to
                 * avoid refactoring code of umtxq_sleep_pi().
                 */
                td1 = linux_tdfind(td, owner & FUTEX_TID_MASK, -1);
                if (td1 != NULL) {
                        owner = td1->td_tid;
                        PROC_UNLOCK(td1->td_proc);
                } else {
                        umtxq_unbusy_unlocked(&uq->uq_key);
                        error = EINVAL;
                        break;
                }

                umtxq_lock(&uq->uq_key);

                /* We set the contested bit, sleep. */
                error = umtxq_sleep_pi(uq, pi, owner, "futexp",
                    args->ts == NULL ? NULL : &timo,
                    (args->flags & FUTEX_SHARED) != 0);
                if (error != 0)
                        continue;

                error = thread_check_susp(td, false);
                if (error != 0)
                        break;
        }

        umtxq_lock(&uq->uq_key);
        umtx_pi_unref(pi);
        umtxq_unlock(&uq->uq_key);
        umtx_key_release(&uq->uq_key);
        return (error);
}

static int
linux_futex_unlock_pi(struct thread *td, bool rb, struct linux_futex_args *args)
{
        struct linux_emuldata *em;
        struct umtx_key key;
        uint32_t old, owner, new_owner;
        int count, error;

        em = em_find(td);

        /*
         * Make sure we own this mtx.
         */
        error = fueword32(args->uaddr, &owner);
        if (error == -1)
                return (EFAULT);
        if (!rb && (owner & FUTEX_TID_MASK) != em->em_tid)
                return (EPERM);

        error = futex_key_get(args->uaddr, TYPE_PI_FUTEX, GET_SHARED(args), &key);
        if (error != 0)
                return (error);
        umtxq_lock(&key);
        umtxq_busy(&key);
        error = umtx_pi_drop(td, &key, rb, &count);
        if (error != 0 || rb) {
                umtxq_unbusy(&key);
                umtxq_unlock(&key);
                umtx_key_release(&key);
                return (error);
        }
        umtxq_unlock(&key);

        /*
         * When unlocking the futex, it must be marked as unowned if
         * there is zero or one thread only waiting for it.
         * Otherwise, it must be marked as contested.
         */
        if (count > 1)
                new_owner = FUTEX_WAITERS;
        else
                new_owner = FUTEX_UNOWNED;

again:
        error = casueword32(args->uaddr, owner, &old, new_owner);
        if (error == 1) {
                error = thread_check_susp(td, false);
                if (error == 0)
                        goto again;
        }
        umtxq_unbusy_unlocked(&key);
        umtx_key_release(&key);
        if (error == -1)
                return (EFAULT);
        if (error == 0 && old != owner)
                return (EINVAL);
        return (error);
}

static int
linux_futex_wakeop(struct thread *td, struct linux_futex_args *args)
{
        struct umtx_key key, key2;
        int nrwake, op_ret, ret;
        int error, count;

        if (args->uaddr == args->uaddr2)
                return (EINVAL);

        error = futex_key_get(args->uaddr, TYPE_FUTEX, GET_SHARED(args), &key);
        if (error != 0)
                return (error);
        error = futex_key_get(args->uaddr2, TYPE_FUTEX, GET_SHARED(args), &key2);
        if (error != 0) {
                umtx_key_release(&key);
                return (error);
        }
        umtxq_busy_unlocked(&key);
        error = futex_atomic_op(td, args->val3, args->uaddr2, &op_ret);
        umtxq_lock(&key);
        umtxq_unbusy(&key);
        if (error != 0)
                goto out;
        ret = umtxq_signal_mask(&key, args->val, args->val3);
        if (op_ret > 0) {
                nrwake = (int)(unsigned long)args->ts;
                umtxq_lock(&key2);
                count = umtxq_count(&key2);
                if (count > 0)
                        ret += umtxq_signal_mask(&key2, nrwake, args->val3);
                else
                        ret += umtxq_signal_mask(&key, nrwake, args->val3);
                umtxq_unlock(&key2);
        }
        td->td_retval[0] = ret;
out:
        umtxq_unlock(&key);
        umtx_key_release(&key2);
        umtx_key_release(&key);
        return (error);
}

static int
linux_futex_requeue(struct thread *td, struct linux_futex_args *args)
{
        int nrwake, nrrequeue;
        struct umtx_key key, key2;
        int error;
        uint32_t uval;

        /*
         * Linux allows this, we would not, it is an incorrect
         * usage of declared ABI, so return EINVAL.
         */
        if (args->uaddr == args->uaddr2)
                return (EINVAL);

        nrrequeue = (int)(unsigned long)args->ts;
        nrwake = args->val;
        /*
         * Sanity check to prevent signed integer overflow,
         * see Linux CVE-2018-6927
         */
        if (nrwake < 0 || nrrequeue < 0)
                return (EINVAL);

        error = futex_key_get(args->uaddr, TYPE_FUTEX, GET_SHARED(args), &key);
        if (error != 0)
                return (error);
        error = futex_key_get(args->uaddr2, TYPE_FUTEX, GET_SHARED(args), &key2);
        if (error != 0) {
                umtx_key_release(&key);
                return (error);
        }
        umtxq_busy_unlocked(&key);
        error = fueword32(args->uaddr, &uval);
        if (error != 0)
                error = EFAULT;
        else if (args->val3_compare == true && uval != args->val3)
                error = EWOULDBLOCK;
        umtxq_lock(&key);
        umtxq_unbusy(&key);
        if (error == 0) {
                umtxq_lock(&key2);
                td->td_retval[0] = umtxq_requeue(&key, nrwake, &key2, nrrequeue);
                umtxq_unlock(&key2);
        }
        umtxq_unlock(&key);
        umtx_key_release(&key2);
        umtx_key_release(&key);
        return (error);
}

static int
linux_futex_wake(struct thread *td, struct linux_futex_args *args)
{
        struct umtx_key key;
        int error;

        if (args->val3 == 0)
                return (EINVAL);

        error = futex_key_get(args->uaddr, TYPE_FUTEX, GET_SHARED(args), &key);
        if (error != 0)
                return (error);
        umtxq_lock(&key);
        td->td_retval[0] = umtxq_signal_mask(&key, args->val, args->val3);
        umtxq_unlock(&key);
        umtx_key_release(&key);
        return (0);
}

static int
linux_futex_wait(struct thread *td, struct linux_futex_args *args)
{
        struct umtx_abs_timeout timo;
        struct umtx_q *uq;
        uint32_t uval;
        int error;

        if (args->val3 == 0)
                error = EINVAL;

        uq = td->td_umtxq;
        error = futex_key_get(args->uaddr, TYPE_FUTEX, GET_SHARED(args),
            &uq->uq_key);
        if (error != 0)
                return (error);
        if (args->ts != NULL)
                linux_umtx_abs_timeout_init(&timo, args);
        umtxq_lock(&uq->uq_key);
        umtxq_busy(&uq->uq_key);
        uq->uq_bitset = args->val3;
        umtxq_insert(uq);
        umtxq_unlock(&uq->uq_key);
        error = fueword32(args->uaddr, &uval);
        if (error != 0)
                error = EFAULT;
        else if (uval != args->val)
                error = EWOULDBLOCK;
        umtxq_lock(&uq->uq_key);
        umtxq_unbusy(&uq->uq_key);
        if (error == 0) {
                error = umtxq_sleep(uq, "futex",
                    args->ts == NULL ? NULL : &timo);
                if ((uq->uq_flags & UQF_UMTXQ) == 0)
                        error = 0;
                else
                        umtxq_remove(uq);
        } else if ((uq->uq_flags & UQF_UMTXQ) != 0) {
                umtxq_remove(uq);
        }
        umtxq_unlock(&uq->uq_key);
        umtx_key_release(&uq->uq_key);
        if (error == ERESTART)
                error = EINTR;
        return (error);
}

static void
linux_umtx_abs_timeout_init(struct umtx_abs_timeout *timo,
    struct linux_futex_args *args)
{
        int clockid, absolute;

        /*
         * The FUTEX_CLOCK_REALTIME option bit can be employed only with the
         * FUTEX_WAIT_BITSET, FUTEX_WAIT_REQUEUE_PI, FUTEX_LOCK_PI2.
         * For FUTEX_WAIT, timeout is interpreted as a relative value, for other
         * futex operations timeout is interpreted as an absolute value.
         * If FUTEX_CLOCK_REALTIME option bit is set, the Linux kernel measures
         * the timeout against the CLOCK_REALTIME clock, otherwise the kernel
         * measures the timeout against the CLOCK_MONOTONIC clock.
         */
        clockid = args->clockrt ? CLOCK_REALTIME : CLOCK_MONOTONIC;
        absolute = args->op == LINUX_FUTEX_WAIT ? false : true;
        umtx_abs_timeout_init(timo, clockid, absolute, args->ts);
}

int
linux_sys_futex(struct thread *td, struct linux_sys_futex_args *args)
{
        struct linux_futex_args fargs = {
                .uaddr = args->uaddr,
                .op = args->op,
                .val = args->val,
                .ts = NULL,
                .uaddr2 = args->uaddr2,
                .val3 = args->val3,
                .val3_compare = true,
        };
        int error;

        switch (args->op & LINUX_FUTEX_CMD_MASK) {
        case LINUX_FUTEX_WAIT:
        case LINUX_FUTEX_WAIT_BITSET:
        case LINUX_FUTEX_LOCK_PI:
        case LINUX_FUTEX_LOCK_PI2:
                if (args->timeout != NULL) {
                        error = linux_get_timespec(&fargs.kts, args->timeout);
                        if (error != 0)
                                return (error);
                        fargs.ts = &fargs.kts;
                }
                break;
        default:
                fargs.ts = PTRIN(args->timeout);
        }
        return (linux_futex(td, &fargs));
}

#if defined(__i386__) || (defined(__amd64__) && defined(COMPAT_LINUX32))
int
linux_sys_futex_time64(struct thread *td,
    struct linux_sys_futex_time64_args *args)
{
        struct linux_futex_args fargs = {
                .uaddr = args->uaddr,
                .op = args->op,
                .val = args->val,
                .ts = NULL,
                .uaddr2 = args->uaddr2,
                .val3 = args->val3,
                .val3_compare = true,
        };
        int error;

        switch (args->op & LINUX_FUTEX_CMD_MASK) {
        case LINUX_FUTEX_WAIT:
        case LINUX_FUTEX_WAIT_BITSET:
        case LINUX_FUTEX_LOCK_PI:
        case LINUX_FUTEX_LOCK_PI2:
                if (args->timeout != NULL) {
                        error = linux_get_timespec64(&fargs.kts, args->timeout);
                        if (error != 0)
                                return (error);
                        fargs.ts = &fargs.kts;
                }
                break;
        default:
                fargs.ts = PTRIN(args->timeout);
        }
        return (linux_futex(td, &fargs));
}
#endif

int
linux_set_robust_list(struct thread *td, struct linux_set_robust_list_args *args)
{
        struct linux_emuldata *em;

        if (args->len != sizeof(struct linux_robust_list_head))
                return (EINVAL);

        em = em_find(td);
        em->robust_futexes = args->head;

        return (0);
}

int
linux_get_robust_list(struct thread *td, struct linux_get_robust_list_args *args)
{
        struct linux_emuldata *em;
        struct linux_robust_list_head *head;
        l_size_t len;
        struct thread *td2;
        int error;

        if (!args->pid) {
                em = em_find(td);
                KASSERT(em != NULL, ("get_robust_list: emuldata notfound.\n"));
                head = em->robust_futexes;
        } else {
                td2 = linux_tdfind(td, args->pid, -1);
                if (td2 == NULL)
                        return (ESRCH);
                if (SV_PROC_ABI(td2->td_proc) != SV_ABI_LINUX) {
                        PROC_UNLOCK(td2->td_proc);
                        return (EPERM);
                }

                em = em_find(td2);
                KASSERT(em != NULL, ("get_robust_list: emuldata notfound.\n"));
                /* XXX: ptrace? */
                if (priv_check(td, PRIV_CRED_SETUID) ||
                    priv_check(td, PRIV_CRED_SETEUID) ||
                    p_candebug(td, td2->td_proc)) {
                        PROC_UNLOCK(td2->td_proc);
                        return (EPERM);
                }
                head = em->robust_futexes;

                PROC_UNLOCK(td2->td_proc);
        }

        len = sizeof(struct linux_robust_list_head);
        error = copyout(&len, args->len, sizeof(l_size_t));
        if (error != 0)
                return (EFAULT);

        return (copyout(&head, args->head, sizeof(l_uintptr_t)));
}

static int
handle_futex_death(struct thread *td, struct linux_emuldata *em, uint32_t *uaddr,
    unsigned int pi, bool pending_op)
{
        uint32_t uval, nval, mval;
        int error;

retry:
        error = fueword32(uaddr, &uval);
        if (error != 0)
                return (EFAULT);

        /*
         * Special case for regular (non PI) futexes. The unlock path in
         * user space has two race scenarios:
         *
         * 1. The unlock path releases the user space futex value and
         *    before it can execute the futex() syscall to wake up
         *    waiters it is killed.
         *
         * 2. A woken up waiter is killed before it can acquire the
         *    futex in user space.
         *
         * In both cases the TID validation below prevents a wakeup of
         * potential waiters which can cause these waiters to block
         * forever.
         *
         * In both cases it is safe to attempt waking up a potential
         * waiter without touching the user space futex value and trying
         * to set the OWNER_DIED bit.
         */
        if (pending_op && !pi && !uval) {
                (void)futex_wake(td, uaddr, 1, true);
                return (0);
        }

        if ((uval & FUTEX_TID_MASK) == em->em_tid) {
                mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
                error = casueword32(uaddr, uval, &nval, mval);
                if (error == -1)
                        return (EFAULT);
                if (error == 1) {
                        error = thread_check_susp(td, false);
                        if (error != 0)
                                return (error);
                        goto retry;
                }

                if (!pi && (uval & FUTEX_WAITERS)) {
                        error = futex_wake(td, uaddr, 1, true);
                        if (error != 0)
                                return (error);
                } else if (pi && (uval & FUTEX_WAITERS)) {
                        error = futex_wake_pi(td, uaddr, true);
                        if (error != 0)
                                return (error);
                }
        }

        return (0);
}

static int
fetch_robust_entry(struct linux_robust_list **entry,
    struct linux_robust_list **head, unsigned int *pi)
{
        l_ulong uentry;
        int error;

        error = copyin((const void *)head, &uentry, sizeof(uentry));
        if (error != 0)
                return (EFAULT);

        *entry = (void *)(uentry & ~1UL);
        *pi = uentry & 1;

        return (0);
}

#define LINUX_HANDLE_DEATH_PENDING      true
#define LINUX_HANDLE_DEATH_LIST         false

/* This walks the list of robust futexes releasing them. */
void
release_futexes(struct thread *td, struct linux_emuldata *em)
{
        struct linux_robust_list_head *head;
        struct linux_robust_list *entry, *next_entry, *pending;
        unsigned int limit = 2048, pi, next_pi, pip;
        uint32_t *uaddr;
        l_long futex_offset;
        int error;

        head = em->robust_futexes;
        if (head == NULL)
                return;

        if (fetch_robust_entry(&entry, PTRIN(&head->list.next), &pi))
                return;

        error = copyin(&head->futex_offset, &futex_offset,
            sizeof(futex_offset));
        if (error != 0)
                return;

        if (fetch_robust_entry(&pending, PTRIN(&head->pending_list), &pip))
                return;

        while (entry != &head->list) {
                error = fetch_robust_entry(&next_entry, PTRIN(&entry->next),
                    &next_pi);

                /*
                 * A pending lock might already be on the list, so
                 * don't process it twice.
                 */
                if (entry != pending) {
                        uaddr = (uint32_t *)((caddr_t)entry + futex_offset);
                        if (handle_futex_death(td, em, uaddr, pi,
                            LINUX_HANDLE_DEATH_LIST))
                                return;
                }
                if (error != 0)
                        return;

                entry = next_entry;
                pi = next_pi;

                if (!--limit)
                        break;

                sched_relinquish(curthread);
        }

        if (pending) {
                uaddr = (uint32_t *)((caddr_t)pending + futex_offset);
                (void)handle_futex_death(td, em, uaddr, pip,
                    LINUX_HANDLE_DEATH_PENDING);
        }
}