/*      $OpenBSD: kern_lock.c,v 1.86 2026/02/04 00:10:27 jsg Exp $      */

/*
 * Copyright (c) 2017 Visa Hankala
 * Copyright (c) 2014 David Gwynne <dlg@openbsd.org>
 * Copyright (c) 2004 Artur Grabowski <art@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/sched.h>
#include <sys/atomic.h>
#include <sys/witness.h>
#include <sys/mutex.h>
#include <sys/pclock.h>

#include <ddb/db_output.h>

#ifdef MP_LOCKDEBUG
#ifndef DDB
#error "MP_LOCKDEBUG requires DDB"
#endif

/*
 * CPU-dependent timing, this needs to be settable from ddb.
 * Use a "long" to allow larger thresholds on fast 64 bits machines.
 */
long __mp_lock_spinout = 1L * INT_MAX;
#endif /* MP_LOCKDEBUG */

extern int ncpusfound;

/*
 * Min & max numbers of "busy cycles" to waste before trying again to
 * acquire a contended lock using an atomic operation.
 *
 * The min number must be as small as possible to not introduce extra
 * latency.  It also doesn't matter if the first steps of an exponential
 * backoff are smalls.
 *
 * The max number is used to cap the exponential backoff.  It should
 * be small enough to not waste too many cycles in %sys time and big
 * enough to reduce (ideally avoid) cache line contention.
 */
#define CPU_MIN_BUSY_CYCLES     1
#define CPU_MAX_BUSY_CYCLES     ncpusfound

#ifdef MULTIPROCESSOR

#include <sys/percpu.h> /* CACHELINESIZE */
#include <sys/mplock.h>
struct __mp_lock kernel_lock;

#ifdef __USE_MI_MUTEX
static void mtx_init_parking(void);
#endif /* __USE_MI_MUTEX */

/*
 * Functions for manipulating the kernel_lock.  We put them here
 * so that they show up in profiles.
 */

void
_kernel_lock_init(void)
{
        __mp_lock_init(&kernel_lock);
#ifdef __USE_MI_MUTEX
        mtx_init_parking();
#endif /* __USE_MI_MUTEX */
}

/*
 * Acquire/release the kernel lock.  Intended for use in the scheduler
 * and the lower half of the kernel.
 */

void
_kernel_lock(void)
{
        SCHED_ASSERT_UNLOCKED();
        __mp_lock(&kernel_lock);
}

void
_kernel_unlock(void)
{
        __mp_unlock(&kernel_lock);
}

int
_kernel_lock_held(void)
{
        if (panicstr || db_active)
                return 1;
        return (__mp_lock_held(&kernel_lock, curcpu()));
}

#ifdef __USE_MI_MPLOCK

/* Ticket lock implementation */

#include <machine/cpu.h>

void
___mp_lock_init(struct __mp_lock *mpl, const struct lock_type *type)
{
        memset(mpl->mpl_cpus, 0, sizeof(mpl->mpl_cpus));
        mpl->mpl_users = 0;
        mpl->mpl_ticket = 1;

#ifdef WITNESS
        mpl->mpl_lock_obj.lo_name = type->lt_name;
        mpl->mpl_lock_obj.lo_type = type;
        if (mpl == &kernel_lock)
                mpl->mpl_lock_obj.lo_flags = LO_WITNESS | LO_INITIALIZED |
                    LO_SLEEPABLE | (LO_CLASS_KERNEL_LOCK << LO_CLASSSHIFT);
        WITNESS_INIT(&mpl->mpl_lock_obj, type);
#endif
}

static __inline void
__mp_lock_spin(struct __mp_lock *mpl, u_int me)
{
        struct schedstate_percpu *spc = &curcpu()->ci_schedstate;
#ifdef MP_LOCKDEBUG
        long nticks = __mp_lock_spinout;
#endif

        spc->spc_spinning++;
        while (mpl->mpl_ticket != me) {
                CPU_BUSY_CYCLE();

#ifdef MP_LOCKDEBUG
                if (--nticks <= 0) {
                        db_printf("%s: %p lock spun out\n", __func__, mpl);
                        db_enter();
                        nticks = __mp_lock_spinout;
                }
#endif
        }
        spc->spc_spinning--;
}

void
__mp_lock(struct __mp_lock *mpl)
{
        struct __mp_lock_cpu *cpu = &mpl->mpl_cpus[cpu_number()];
        unsigned long s;

#ifdef WITNESS
        if (!__mp_lock_held(mpl, curcpu()))
                WITNESS_CHECKORDER(&mpl->mpl_lock_obj,
                    LOP_EXCLUSIVE | LOP_NEWORDER, NULL);
#endif

        s = intr_disable();
        if (cpu->mplc_depth++ == 0)
                cpu->mplc_ticket = atomic_inc_int_nv(&mpl->mpl_users);
        intr_restore(s);

        __mp_lock_spin(mpl, cpu->mplc_ticket);
        membar_enter_after_atomic();

        WITNESS_LOCK(&mpl->mpl_lock_obj, LOP_EXCLUSIVE);
}

void
__mp_unlock(struct __mp_lock *mpl)
{
        struct __mp_lock_cpu *cpu = &mpl->mpl_cpus[cpu_number()];
        unsigned long s;

#ifdef MP_LOCKDEBUG
        if (!__mp_lock_held(mpl, curcpu())) {
                db_printf("__mp_unlock(%p): not held lock\n", mpl);
                db_enter();
        }
#endif

        WITNESS_UNLOCK(&mpl->mpl_lock_obj, LOP_EXCLUSIVE);

        s = intr_disable();
        if (--cpu->mplc_depth == 0) {
                membar_exit();
                mpl->mpl_ticket++;
        }
        intr_restore(s);
}

int
__mp_release_all(struct __mp_lock *mpl)
{
        struct __mp_lock_cpu *cpu = &mpl->mpl_cpus[cpu_number()];
        unsigned long s;
        int rv;
#ifdef WITNESS
        int i;
#endif

        s = intr_disable();
        rv = cpu->mplc_depth;
#ifdef WITNESS
        for (i = 0; i < rv; i++)
                WITNESS_UNLOCK(&mpl->mpl_lock_obj, LOP_EXCLUSIVE);
#endif
        cpu->mplc_depth = 0;
        membar_exit();
        mpl->mpl_ticket++;
        intr_restore(s);

        return (rv);
}

void
__mp_acquire_count(struct __mp_lock *mpl, int count)
{
        while (count--)
                __mp_lock(mpl);
}

int
__mp_lock_held(struct __mp_lock *mpl, struct cpu_info *ci)
{
        struct __mp_lock_cpu *cpu = &mpl->mpl_cpus[CPU_INFO_UNIT(ci)];

        return (cpu->mplc_ticket == mpl->mpl_ticket && cpu->mplc_depth > 0);
}

#endif /* __USE_MI_MPLOCK */

#endif /* MULTIPROCESSOR */


#ifdef __USE_MI_MUTEX
void
__mtx_init(struct mutex *mtx, int wantipl)
{
        mtx->mtx_owner = 0;
        mtx->mtx_wantipl = wantipl;
        mtx->mtx_oldipl = IPL_NONE;
}

#ifdef MULTIPROCESSOR
struct mtx_waiter {
        struct mutex            *mtx;
        volatile unsigned int    wait;
        TAILQ_ENTRY(mtx_waiter)  entry;
};

TAILQ_HEAD(mtx_waitlist, mtx_waiter);

struct mtx_park {
        struct cpu_info         *volatile lock;
        struct mtx_waitlist      waiters;
} __aligned(CACHELINESIZE);

#define MTX_PARKING_BITS        7
#define MTX_PARKING_LOTS        (1 << MTX_PARKING_BITS)
#define MTX_PARKING_MASK        (MTX_PARKING_LOTS - 1)

static struct mtx_park mtx_parking[MTX_PARKING_LOTS];

static void
mtx_init_parking(void)
{
        size_t i;

        for (i = 0; i < nitems(mtx_parking); i++) {
                struct mtx_park *p = &mtx_parking[i];

                p->lock = NULL;
                TAILQ_INIT(&p->waiters);
        }
}

#ifdef DDB
void
mtx_print_parks(void)
{
        size_t i;

        for (i = 0; i < nitems(mtx_parking); i++) {
                struct mtx_park *p = &mtx_parking[i];
                struct mtx_waiter *w;

                db_printf("park %zu @ %p lock %p\n", i, p, p->lock);
                TAILQ_FOREACH(w, &p->waiters, entry) {
                        db_printf("\twaiter mtx %p wait %u\n",
                            w->mtx, w->wait);
                }
        }
}
#endif /* DDB */

static struct mtx_park *
mtx_park(struct mutex *mtx)
{
        unsigned long addr = (unsigned long)mtx;
        addr >>= 6;
        addr ^= addr >> MTX_PARKING_BITS;
        addr &= MTX_PARKING_MASK;

        return &mtx_parking[addr];
}

static unsigned long
mtx_enter_park(struct mtx_park *p)
{
        struct cpu_info *ci = curcpu();
        struct cpu_info *owner;
        unsigned long m;

        m = intr_disable();
        while ((owner = atomic_cas_ptr(&p->lock, NULL, ci)) != NULL)
                CPU_BUSY_CYCLE();
        membar_enter_after_atomic();

        return (m);
}

static void
mtx_leave_park(struct mtx_park *p, unsigned long m)
{
        membar_exit();
        p->lock = NULL;
        intr_restore(m);
}

static inline unsigned long
mtx_cas(struct mutex *mtx, unsigned long e, unsigned long v)
{
        return atomic_cas_ulong(&mtx->mtx_owner, e, v);
}

int
mtx_enter_try(struct mutex *mtx)
{
        struct cpu_info *ci = curcpu();
        unsigned long owner, self = (unsigned long)ci;
        int s;

        /* Avoid deadlocks after panic or in DDB */
        if (panicstr || db_active)
                return (1);

        if (mtx->mtx_wantipl != IPL_NONE)
                s = splraise(mtx->mtx_wantipl);

        owner = mtx_cas(mtx, 0, self);
        if (owner == 0) {
                membar_enter_after_atomic();
                if (mtx->mtx_wantipl != IPL_NONE)
                        mtx->mtx_oldipl = s;
#ifdef DIAGNOSTIC
                ci->ci_mutex_level++;
#endif
                WITNESS_LOCK(MUTEX_LOCK_OBJECT(mtx), LOP_EXCLUSIVE);
                return (1);
        }

        if (mtx->mtx_wantipl != IPL_NONE)
                splx(s);

#ifdef DIAGNOSTIC
        if (__predict_false((owner & ~1UL) == self))
                panic("mtx %p: locking against myself", mtx);
#endif

        return (0);
}

void
mtx_enter(struct mutex *mtx)
{
        struct cpu_info *ci = curcpu();
        struct schedstate_percpu *spc = &ci->ci_schedstate;
        unsigned long owner, self = (unsigned long)ci;
        struct mtx_park *p;
        struct mtx_waiter w;
        unsigned long m;
        int spins = 0;
        int s;
#ifdef MP_LOCKDEBUG
        long nticks = __mp_lock_spinout;
#endif

        /* Avoid deadlocks after panic or in DDB */
        if (panicstr || db_active)
                return;

        WITNESS_CHECKORDER(MUTEX_LOCK_OBJECT(mtx),
            LOP_EXCLUSIVE | LOP_NEWORDER, NULL);

        if (mtx->mtx_wantipl != IPL_NONE)
                s = splraise(mtx->mtx_wantipl);

        owner = mtx_cas(mtx, 0, self);
        if (owner == 0) {
                /* we got the lock first go. this is the fast path */
                goto locked;
        }

#ifdef DIAGNOSTIC
        if (__predict_false((owner & ~1ULL) == self))
                panic("mtx %p: locking against myself", mtx);
#endif

        /* we're going to have to spin for it now */
        spc->spc_spinning++;

        for (spins = 0; spins < 40; spins++) {
                if (ISSET(owner, 1)) {
                        /* don't spin if cpus are already parked */
                        break;
                }
                CPU_BUSY_CYCLE();
                owner = mtx->mtx_owner;
                if (owner == 0) {
                        owner = mtx_cas(mtx, 0, self);
                        if (owner == 0)
                                goto spinlocked;
                }
        }

        /* take the really slow path */
        p = mtx_park(mtx);

        /* publish our existence in the parking lot */
        w.mtx = mtx;
        m = mtx_enter_park(p);
        TAILQ_INSERT_TAIL(&p->waiters, &w, entry);
        mtx_leave_park(p, m);

        do {
                unsigned long o;

                w.wait = 1;
                /* ensure wait is visible before attempting the cas */
                membar_enter(); /* StoreStore | StoreLoad */
                o = mtx_cas(mtx, owner, owner | 1);
                if (o == owner) {
                        while (w.wait) {
                                CPU_BUSY_CYCLE();
#ifdef MP_LOCKDEBUG
                                if (--nticks <= 0) {
                                        db_printf("%s: %p lock spun out\n",
                                            __func__, mtx);
                                        db_enter();
                                        nticks = __mp_lock_spinout;
                                }
#endif
                        }
                        membar_consumer();
                } else if (o != 0) {
                        owner = o;
                        continue;
                }

                owner = mtx_cas(mtx, 0, self | 1);
        } while (owner != 0);

        m = mtx_enter_park(p);
        TAILQ_REMOVE(&p->waiters, &w, entry);
        mtx_leave_park(p, m);
spinlocked:
        spc->spc_spinning--;
locked:
        membar_enter_after_atomic();
        if (mtx->mtx_wantipl != IPL_NONE)
                mtx->mtx_oldipl = s;
#ifdef DIAGNOSTIC
        ci->ci_mutex_level++;
#endif
        WITNESS_LOCK(MUTEX_LOCK_OBJECT(mtx), LOP_EXCLUSIVE);
}

void
mtx_leave(struct mutex *mtx)
{
        struct cpu_info *ci = curcpu();
        unsigned long owner, self = (unsigned long)ci;
        int s;

        /* Avoid deadlocks after panic or in DDB */
        if (panicstr || db_active)
                return;

        WITNESS_UNLOCK(MUTEX_LOCK_OBJECT(mtx), LOP_EXCLUSIVE);

#ifdef DIAGNOSTIC
        curcpu()->ci_mutex_level--;
#endif

        s = mtx->mtx_oldipl;
        membar_exit_before_atomic();
        owner = atomic_cas_ulong(&mtx->mtx_owner, self, 0);
        if (owner != self) {
                struct mtx_park *p;
                unsigned long m;
                struct mtx_waiter *w;

#ifdef DIAGNOSTIC
                if (__predict_false((owner & ~1ULL) != self))
                        panic("mtx %p: not held", mtx);
#endif

                p = mtx_park(mtx);
                m = mtx_enter_park(p);
                mtx->mtx_owner = 0;
                membar_producer();
                TAILQ_FOREACH(w, &p->waiters, entry) {
                        if (w->mtx == mtx) {
                                w->wait = 0;
                                break;
                        }
                }
                mtx_leave_park(p, m);
        }

        if (mtx->mtx_wantipl != IPL_NONE)
                splx(s);
}
#else /* MULTIPROCESSOR */
void
mtx_enter(struct mutex *mtx)
{
        unsigned long self = mtx_curcpu();

        /* Avoid deadlocks after panic or in DDB */
        if (panicstr || db_active)
                return;

        WITNESS_CHECKORDER(MUTEX_LOCK_OBJECT(mtx),
            LOP_EXCLUSIVE | LOP_NEWORDER, NULL);

#ifdef DIAGNOSTIC
        if (__predict_false(mtx_owner(mtx) == self))
                panic("mtx %p: locking against myself", mtx);
#endif

        if (mtx->mtx_wantipl != IPL_NONE)
                mtx->mtx_oldipl = splraise(mtx->mtx_wantipl);

        mtx->mtx_owner = self;

#ifdef DIAGNOSTIC
        curcpu()->ci_mutex_level++;
#endif
        WITNESS_LOCK(MUTEX_LOCK_OBJECT(mtx), LOP_EXCLUSIVE);
}

int
mtx_enter_try(struct mutex *mtx)
{
        mtx_enter(mtx);
        return (1);
}

void
mtx_leave(struct mutex *mtx)
{
        int s;

        /* Avoid deadlocks after panic or in DDB */
        if (panicstr || db_active)
                return;

        MUTEX_ASSERT_LOCKED(mtx);
        WITNESS_UNLOCK(MUTEX_LOCK_OBJECT(mtx), LOP_EXCLUSIVE);

#ifdef DIAGNOSTIC
        curcpu()->ci_mutex_level--;
#endif

        s = mtx->mtx_oldipl;
        mtx->mtx_owner = 0;
        if (mtx->mtx_wantipl != IPL_NONE)
                splx(s);
}
#endif /* MULTIPROCESSOR */

#ifdef DDB
void
db_mtx_enter(struct db_mutex *mtx)
{
        struct cpu_info *ci = curcpu(), *owner;
        unsigned int i, ncycle = CPU_MIN_BUSY_CYCLES;
        unsigned long s;

#ifdef DIAGNOSTIC
        if (__predict_false(mtx->mtx_owner == ci))
                panic("%s: mtx %p: locking against myself", __func__, mtx);
#endif

        s = intr_disable();
        for (;;) {
                /*
                 * Avoid unconditional atomic operation to prevent cache
                 * line contention.
                 */
                owner = mtx->mtx_owner;
                if (owner == NULL) {
                        owner = atomic_cas_ptr(&mtx->mtx_owner, NULL, ci);
                        if (owner == NULL)
                                break;
                        /* Busy loop with exponential backoff. */
                        for (i = ncycle; i > 0; i--)
                                CPU_BUSY_CYCLE();
                        if (ncycle < CPU_MAX_BUSY_CYCLES)
                                ncycle += ncycle;
                }
        }
        membar_enter_after_atomic();

        mtx->mtx_intr_state = s;

#ifdef DIAGNOSTIC
        ci->ci_mutex_level++;
#endif
}

void
db_mtx_leave(struct db_mutex *mtx)
{
#ifdef DIAGNOSTIC
        struct cpu_info *ci = curcpu();
#endif
        unsigned long s;

#ifdef DIAGNOSTIC
        if (__predict_false(mtx->mtx_owner != ci))
                panic("%s: mtx %p: not owned by this CPU", __func__, mtx);
        ci->ci_mutex_level--;
#endif

        s = mtx->mtx_intr_state;
#ifdef MULTIPROCESSOR
        membar_exit();
#endif
        mtx->mtx_owner = NULL;
        intr_restore(s);
}
#endif /* DDB */
#endif /* __USE_MI_MUTEX */

#ifdef WITNESS
void
_mtx_init_flags(struct mutex *m, int ipl, const char *name, int flags,
    const struct lock_type *type)
{
        struct lock_object *lo = MUTEX_LOCK_OBJECT(m);

        lo->lo_flags = MTX_LO_FLAGS(flags);
        if (name != NULL)
                lo->lo_name = name;
        else
                lo->lo_name = type->lt_name;
        WITNESS_INIT(lo, type);

        _mtx_init(m, ipl);
}
#endif /* WITNESS */

void
pc_lock_init(struct pc_lock *pcl)
{
        pcl->pcl_gen = 0;
}

unsigned int
pc_sprod_enter(struct pc_lock *pcl)
{
        unsigned int gen;

        gen = pcl->pcl_gen;
        pcl->pcl_gen = ++gen;
        membar_producer();

        return (gen);
}

void
pc_sprod_leave(struct pc_lock *pcl, unsigned int gen)
{
        membar_producer();
        pcl->pcl_gen = ++gen;
}

#ifdef MULTIPROCESSOR
unsigned int
pc_mprod_enter(struct pc_lock *pcl)
{
        unsigned int gen, ngen, ogen;

        gen = pcl->pcl_gen;
        for (;;) {
                while (gen & 1) {
                        CPU_BUSY_CYCLE();
                        gen = pcl->pcl_gen;
                }

                ngen = 1 + gen;
                ogen = atomic_cas_uint(&pcl->pcl_gen, gen, ngen);
                if (gen == ogen)
                        break;

                CPU_BUSY_CYCLE();
                gen = ogen;
        }

        membar_enter_after_atomic();
        return (ngen);
}

void
pc_mprod_leave(struct pc_lock *pcl, unsigned int gen)
{
        membar_exit();
        pcl->pcl_gen = ++gen;
}
#else /* MULTIPROCESSOR */
unsigned int    pc_mprod_enter(struct pc_lock *)
                    __attribute__((alias("pc_sprod_enter")));
void            pc_mprod_leave(struct pc_lock *, unsigned int)
                    __attribute__((alias("pc_sprod_leave")));
#endif /* MULTIPROCESSOR */

void
pc_cons_enter(struct pc_lock *pcl, unsigned int *genp)
{
        unsigned int gen;

        gen = pcl->pcl_gen;
        while (gen & 1) {
                CPU_BUSY_CYCLE();
                gen = pcl->pcl_gen;
        }

        membar_consumer();
        *genp = gen;
}

int
pc_cons_leave(struct pc_lock *pcl, unsigned int *genp)
{
        unsigned int gen;

        membar_consumer();

        gen = pcl->pcl_gen;
        if (gen & 1) {
                do {
                        CPU_BUSY_CYCLE();
                        gen = pcl->pcl_gen;
                } while (gen & 1);
        } else if (gen == *genp)
                return (0);

        *genp = gen;
        return (EBUSY);
}