/*      $NetBSD: scheduler.c,v 1.55 2023/10/05 19:41:07 ad Exp $        */

/*
* Copyright (c) 2010, 2011 Antti Kantee.  All Rights Reserved.
*
* 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 ``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/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: scheduler.c,v 1.55 2023/10/05 19:41:07 ad Exp $");

#include <sys/param.h>
#include <sys/atomic.h>
#include <sys/cpu.h>
#include <sys/kmem.h>
#include <sys/mutex.h>
#include <sys/namei.h>
#include <sys/queue.h>
#include <sys/select.h>
#include <sys/systm.h>

#include <rump-sys/kern.h>

#include <rump/rumpuser.h>

static struct rumpcpu {
       /* needed in fastpath */
       struct cpu_info *rcpu_ci;
       void *rcpu_prevlwp;

       /* needed in slowpath */
       struct rumpuser_mtx *rcpu_mtx;
       struct rumpuser_cv *rcpu_cv;
       int rcpu_wanted;

       /* offset 20 (P=4) or 36 (P=8) here */

       /*
        * Some stats.  Not really that necessary, but we should
        * have room.  Note that these overflow quite fast, so need
        * to be collected often.
        */
       unsigned int rcpu_fastpath;
       unsigned int rcpu_slowpath;
       unsigned int rcpu_migrated;

       /* offset 32 (P=4) or 50 (P=8) */

       int rcpu_align[0] __aligned(CACHE_LINE_SIZE);
} rcpu_storage[MAXCPUS];

static inline struct rumpcpu *
cpuinfo_to_rumpcpu(struct cpu_info *ci)
{

       return &rcpu_storage[cpu_index(ci)];
}

struct cpu_info rump_bootcpu;

#define RCPULWP_BUSY    ((void *)-1)
#define RCPULWP_WANTED  ((void *)-2)

static struct rumpuser_mtx *lwp0mtx;
static struct rumpuser_cv *lwp0cv;
static unsigned nextcpu;

kmutex_t unruntime_lock; /* unruntime lwp lock.  practically unused */

static bool lwp0isbusy = false;

/*
* Keep some stats.
*
* Keeping track of there is not really critical for speed, unless
* stats happen to be on a different cache line (CACHE_LINE_SIZE is
* really just a coarse estimate), so default for the performant case
* (i.e. no stats).
*/
#ifdef RUMPSCHED_STATS
#define SCHED_FASTPATH(rcpu) rcpu->rcpu_fastpath++;
#define SCHED_SLOWPATH(rcpu) rcpu->rcpu_slowpath++;
#define SCHED_MIGRATED(rcpu) rcpu->rcpu_migrated++;
#else
#define SCHED_FASTPATH(rcpu)
#define SCHED_SLOWPATH(rcpu)
#define SCHED_MIGRATED(rcpu)
#endif

struct cpu_info *
cpu_lookup(u_int index)
{

       return rcpu_storage[index].rcpu_ci;
}

static inline struct rumpcpu *
getnextcpu(void)
{
       unsigned newcpu;

       newcpu = atomic_inc_uint_nv(&nextcpu);
       if (__predict_false(ncpu > UINT_MAX/2))
               atomic_and_uint(&nextcpu, 0);
       newcpu = newcpu % ncpu;

       return &rcpu_storage[newcpu];
}

/* this could/should be mi_attach_cpu? */
void
rump_cpus_bootstrap(int *nump)
{
       int num = *nump;

       if (num > MAXCPUS) {
               aprint_verbose("CPU limit: %d wanted, %d (MAXCPUS) "
                   "available (adjusted)\n", num, MAXCPUS);
               num = MAXCPUS;
       }

       cpu_setmodel("rumpcore (virtual)");

       mi_cpu_init();

       /* attach first cpu for bootstrap */
       rump_cpu_attach(&rump_bootcpu);
       ncpu = 1;
       *nump = num;
}

void
rump_scheduler_init(int numcpu)
{
       struct rumpcpu *rcpu;
       struct cpu_info *ci;
       int i;

       rumpuser_mutex_init(&lwp0mtx, RUMPUSER_MTX_SPIN);
       rumpuser_cv_init(&lwp0cv);
       for (i = 0; i < numcpu; i++) {
               if (i == 0) {
                       ci = &rump_bootcpu;
               } else {
                       ci = kmem_zalloc(sizeof(*ci), KM_SLEEP);
                       ci->ci_index = i;
               }

               rcpu = &rcpu_storage[i];
               rcpu->rcpu_ci = ci;
               rcpu->rcpu_wanted = 0;
               rumpuser_cv_init(&rcpu->rcpu_cv);
               rumpuser_mutex_init(&rcpu->rcpu_mtx, RUMPUSER_MTX_SPIN);

               ci->ci_schedstate.spc_mutex =
                   mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED);
               ci->ci_schedstate.spc_flags = SPCF_RUNNING;
       }

       mutex_init(&unruntime_lock, MUTEX_DEFAULT, IPL_SCHED);
}

void
rump_schedlock_cv_signal(struct cpu_info *ci, struct rumpuser_cv *cv)
{
       struct rumpcpu *rcpu = cpuinfo_to_rumpcpu(ci);

       rumpuser_mutex_enter_nowrap(rcpu->rcpu_mtx);
       rumpuser_cv_signal(cv);
       rumpuser_mutex_exit(rcpu->rcpu_mtx);
}

/*
* condvar ops using scheduler lock as the rumpuser interlock.
*/
void
rump_schedlock_cv_wait(struct rumpuser_cv *cv)
{
       struct lwp *l = curlwp;
       struct rumpcpu *rcpu = cpuinfo_to_rumpcpu(l->l_cpu);

       /* mutex will be taken and released in cpu schedule/unschedule */
       rumpuser_cv_wait(cv, rcpu->rcpu_mtx);
}

int
rump_schedlock_cv_timedwait(struct rumpuser_cv *cv, const struct timespec *ts)
{
       struct lwp *l = curlwp;
       struct rumpcpu *rcpu = cpuinfo_to_rumpcpu(l->l_cpu);

       /* mutex will be taken and released in cpu schedule/unschedule */
       return rumpuser_cv_timedwait(cv, rcpu->rcpu_mtx,
           ts->tv_sec, ts->tv_nsec);
}

static void
lwp0busy(void)
{

       /* busy lwp0 */
       KASSERT(curlwp == NULL || curlwp->l_stat != LSONPROC);
       rumpuser_mutex_enter_nowrap(lwp0mtx);
       while (lwp0isbusy)
               rumpuser_cv_wait_nowrap(lwp0cv, lwp0mtx);
       lwp0isbusy = true;
       rumpuser_mutex_exit(lwp0mtx);
}

static void
lwp0rele(void)
{

       rumpuser_mutex_enter_nowrap(lwp0mtx);
       KASSERT(lwp0isbusy == true);
       lwp0isbusy = false;
       rumpuser_cv_signal(lwp0cv);
       rumpuser_mutex_exit(lwp0mtx);
}

/*
* rump_schedule: ensure that the calling host thread has a valid lwp context.
* ie. ensure that curlwp != NULL.  Also, ensure that there
* a 1:1 mapping between the lwp and rump kernel cpu.
*/
void
rump_schedule()
{
       struct lwp *l;

       /*
        * If there is no dedicated lwp, allocate a temp one and
        * set it to be free'd upon unschedule().  Use lwp0 context
        * for reserving the necessary resources.  Don't optimize
        * for this case -- anyone who cares about performance will
        * start a real thread.
        */
       if (__predict_true((l = curlwp) != NULL)) {
               struct proc *p = l->l_proc;
               rump_schedule_cpu(l);
               if (l->l_cred != p->p_cred) {
                       kauth_cred_t oc = l->l_cred;
                       mutex_enter(p->p_lock);
                       l->l_cred = kauth_cred_hold(p->p_cred);
                       mutex_exit(p->p_lock);
                       kauth_cred_free(oc);
               }
       } else {
               lwp0busy();

               /* schedule cpu and use lwp0 */
               rump_schedule_cpu(&lwp0);
               rump_lwproc_curlwp_set(&lwp0);

               /* allocate thread, switch to it, and release lwp0 */
               l = rump__lwproc_alloclwp(initproc);
               rump_lwproc_switch(l);
               lwp0rele();

               /*
                * mark new thread dead-on-unschedule.  this
                * means that we'll be running with l_refcnt == 0.
                * relax, it's fine.
                */
               rump_lwproc_releaselwp();
       }
}

void
rump_schedule_cpu(struct lwp *l)
{

       rump_schedule_cpu_interlock(l, NULL);
}

/*
* Schedule a CPU.  This optimizes for the case where we schedule
* the same thread often, and we have nCPU >= nFrequently-Running-Thread
* (where CPU is virtual rump cpu, not host CPU).
*/
void
rump_schedule_cpu_interlock(struct lwp *l, void *interlock)
{
       struct rumpcpu *rcpu;
       struct cpu_info *ci;
       void *old;
       bool domigrate;
       bool bound = l->l_pflag & LP_BOUND;

       l->l_stat = LSRUN;

       /*
        * First, try fastpath: if we were the previous user of the
        * CPU, everything is in order cachewise and we can just
        * proceed to use it.
        *
        * If we are a different thread (i.e. CAS fails), we must go
        * through a memory barrier to ensure we get a truthful
        * view of the world.
        */

       KASSERT(l->l_target_cpu != NULL);
       rcpu = cpuinfo_to_rumpcpu(l->l_target_cpu);
       if (atomic_cas_ptr(&rcpu->rcpu_prevlwp, l, RCPULWP_BUSY) == l) {
               if (interlock == rcpu->rcpu_mtx)
                       rumpuser_mutex_exit(rcpu->rcpu_mtx);
               SCHED_FASTPATH(rcpu);
               /* jones, you're the man */
               goto fastlane;
       }

       /*
        * Else, it's the slowpath for us.  First, determine if we
        * can migrate.
        */
       if (ncpu == 1)
               domigrate = false;
       else
               domigrate = true;

       /* Take lock.  This acts as a load barrier too. */
       if (interlock != rcpu->rcpu_mtx)
               rumpuser_mutex_enter_nowrap(rcpu->rcpu_mtx);

       for (;;) {
               SCHED_SLOWPATH(rcpu);
               old = atomic_swap_ptr(&rcpu->rcpu_prevlwp, RCPULWP_WANTED);

               /* CPU is free? */
               if (old != RCPULWP_BUSY && old != RCPULWP_WANTED) {
                       if (atomic_cas_ptr(&rcpu->rcpu_prevlwp,
                           RCPULWP_WANTED, RCPULWP_BUSY) == RCPULWP_WANTED) {
                               break;
                       }
               }

               /*
                * Do we want to migrate once?
                * This may need a slightly better algorithm, or we
                * might cache pingpong eternally for non-frequent
                * threads.
                */
               if (domigrate && !bound) {
                       domigrate = false;
                       SCHED_MIGRATED(rcpu);
                       rumpuser_mutex_exit(rcpu->rcpu_mtx);
                       rcpu = getnextcpu();
                       rumpuser_mutex_enter_nowrap(rcpu->rcpu_mtx);
                       continue;
               }

               /* Want CPU, wait until it's released an retry */
               rcpu->rcpu_wanted++;
               rumpuser_cv_wait_nowrap(rcpu->rcpu_cv, rcpu->rcpu_mtx);
               rcpu->rcpu_wanted--;
       }
       rumpuser_mutex_exit(rcpu->rcpu_mtx);

fastlane:
       ci = rcpu->rcpu_ci;
       l->l_cpu = l->l_target_cpu = ci;
       l->l_mutex = rcpu->rcpu_ci->ci_schedstate.spc_mutex;
       l->l_ru.ru_nvcsw++;
       l->l_stat = LSONPROC;

       /*
        * No interrupts, so ci_curlwp === cpu_onproc.
        * Okay, we could make an attempt to not set cpu_onproc
        * in the case that an interrupt is scheduled immediately
        * after a user proc, but leave that for later.
        */
       ci->ci_curlwp = ci->ci_onproc = l;
}

void
rump_unschedule()
{
       struct lwp *l = curlwp;
#ifdef DIAGNOSTIC
       int nlock;

       KERNEL_UNLOCK_ALL(l, &nlock);
       KASSERT(nlock == 0);
#endif

       KASSERT(l->l_mutex == l->l_cpu->ci_schedstate.spc_mutex);
       rump_unschedule_cpu(l);
       l->l_mutex = &unruntime_lock;
       l->l_stat = LSSTOP;

       /*
        * Check special conditions:
        *  1) do we need to free the lwp which just unscheduled?
        *     (locking order: lwp0, cpu)
        *  2) do we want to clear curlwp for the current host thread
        */
       if (__predict_false(l->l_flag & LW_WEXIT)) {
               lwp0busy();

               /* Now that we have lwp0, we can schedule a CPU again */
               rump_schedule_cpu(l);

               /* switch to lwp0.  this frees the old thread */
               KASSERT(l->l_flag & LW_WEXIT);
               rump_lwproc_switch(&lwp0);

               /* release lwp0 */
               rump_unschedule_cpu(&lwp0);
               lwp0.l_mutex = &unruntime_lock;
               lwp0.l_pflag &= ~LP_RUNNING;
               lwp0rele();
               rump_lwproc_curlwp_clear(&lwp0);

       } else if (__predict_false(l->l_flag & LW_RUMP_CLEAR)) {
               rump_lwproc_curlwp_clear(l);
               l->l_flag &= ~LW_RUMP_CLEAR;
       }
}

void
rump_unschedule_cpu(struct lwp *l)
{

       rump_unschedule_cpu_interlock(l, NULL);
}

void
rump_unschedule_cpu_interlock(struct lwp *l, void *interlock)
{

       if ((l->l_pflag & LP_INTR) == 0)
               rump_softint_run(l->l_cpu);
       rump_unschedule_cpu1(l, interlock);
}

void
rump_unschedule_cpu1(struct lwp *l, void *interlock)
{
       struct rumpcpu *rcpu;
       struct cpu_info *ci;
       void *old;

       ci = l->l_cpu;
       ci->ci_curlwp = ci->ci_onproc = NULL;
       rcpu = cpuinfo_to_rumpcpu(ci);

       KASSERT(rcpu->rcpu_ci == ci);

       /*
        * Make sure all stores are seen before the CPU release.  This
        * is relevant only in the non-fastpath scheduling case, but
        * we don't know here if that's going to happen, so need to
        * expect the worst.
        *
        * If the scheduler interlock was requested by the caller, we
        * need to obtain it before we release the CPU.  Otherwise, we risk a
        * race condition where another thread is scheduled onto the
        * rump kernel CPU before our current thread can
        * grab the interlock.
        */
       if (interlock == rcpu->rcpu_mtx)
               rumpuser_mutex_enter_nowrap(rcpu->rcpu_mtx);
       else
               membar_release(); /* XXX what does this pair with? */

       /* Release the CPU. */
       old = atomic_swap_ptr(&rcpu->rcpu_prevlwp, l);

       /* No waiters?  No problems.  We're outta here. */
       if (old == RCPULWP_BUSY) {
               return;
       }

       KASSERT(old == RCPULWP_WANTED);

       /*
        * Ok, things weren't so snappy.
        *
        * Snailpath: take lock and signal anyone waiting for this CPU.
        */

       if (interlock != rcpu->rcpu_mtx)
               rumpuser_mutex_enter_nowrap(rcpu->rcpu_mtx);
       if (rcpu->rcpu_wanted)
               rumpuser_cv_broadcast(rcpu->rcpu_cv);
       if (interlock != rcpu->rcpu_mtx)
               rumpuser_mutex_exit(rcpu->rcpu_mtx);
}

/* Give up and retake CPU (perhaps a different one) */
void
yield()
{
       struct lwp *l = curlwp;
       int nlocks;

       KERNEL_UNLOCK_ALL(l, &nlocks);
       rump_unschedule_cpu(l);
       rump_schedule_cpu(l);
       KERNEL_LOCK(nlocks, l);
}

void
preempt()
{

       yield();
}

bool
kpreempt(uintptr_t where)
{

       return false;
}

/*
* There is no kernel thread preemption in rump currently.  But call
* the implementing macros anyway in case they grow some side-effects
* down the road.
*/
void
kpreempt_disable(void)
{

       KPREEMPT_DISABLE(curlwp);
}

void
kpreempt_enable(void)
{

       KPREEMPT_ENABLE(curlwp);
}

bool
kpreempt_disabled(void)
{
#if 0
       const lwp_t *l = curlwp;

       return l->l_nopreempt != 0 || l->l_stat == LSZOMB ||
           (l->l_flag & LW_IDLE) != 0 || cpu_kpreempt_disabled();
#endif
       /* XXX: emulate cpu_kpreempt_disabled() */
       return true;
}

void
suspendsched(void)
{

       /*
        * Could wait until everyone is out and block further entries,
        * but skip that for now.
        */
}

void
sched_nice(struct proc *p, int level)
{

       /* nothing to do for now */
}

void
setrunnable(struct lwp *l)
{

       sched_enqueue(l);
}

void
sched_enqueue(struct lwp *l)
{

       rump_thread_allow(l);
}

void
sched_resched_cpu(struct cpu_info *ci, pri_t pri, bool unlock)
{

}

void
sched_resched_lwp(struct lwp *l, bool unlock)
{

}

void
sched_dequeue(struct lwp *l)
{

       panic("sched_dequeue not implemented");
}

void
preempt_point(void)
{

}

bool
preempt_needed(void)
{

       return false;
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.