135e6168fSJeff Roberson /*- 215dc847eSJeff Roberson * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org> 335e6168fSJeff Roberson * All rights reserved. 435e6168fSJeff Roberson * 535e6168fSJeff Roberson * Redistribution and use in source and binary forms, with or without 635e6168fSJeff Roberson * modification, are permitted provided that the following conditions 735e6168fSJeff Roberson * are met: 835e6168fSJeff Roberson * 1. Redistributions of source code must retain the above copyright 935e6168fSJeff Roberson * notice unmodified, this list of conditions, and the following 1035e6168fSJeff Roberson * disclaimer. 1135e6168fSJeff Roberson * 2. Redistributions in binary form must reproduce the above copyright 1235e6168fSJeff Roberson * notice, this list of conditions and the following disclaimer in the 1335e6168fSJeff Roberson * documentation and/or other materials provided with the distribution. 1435e6168fSJeff Roberson * 1535e6168fSJeff Roberson * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1635e6168fSJeff Roberson * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1735e6168fSJeff Roberson * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1835e6168fSJeff Roberson * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1935e6168fSJeff Roberson * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2035e6168fSJeff Roberson * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2135e6168fSJeff Roberson * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2235e6168fSJeff Roberson * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2335e6168fSJeff Roberson * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2435e6168fSJeff Roberson * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2535e6168fSJeff Roberson */ 2635e6168fSJeff Roberson 27677b542eSDavid E. O'Brien #include <sys/cdefs.h> 28677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$"); 29677b542eSDavid E. O'Brien 309923b511SScott Long #include <opt_sched.h> 319923b511SScott Long 32ed062c8dSJulian Elischer #define kse td_sched 33ed062c8dSJulian Elischer 3435e6168fSJeff Roberson #include <sys/param.h> 3535e6168fSJeff Roberson #include <sys/systm.h> 362c3490b1SMarcel Moolenaar #include <sys/kdb.h> 3735e6168fSJeff Roberson #include <sys/kernel.h> 3835e6168fSJeff Roberson #include <sys/ktr.h> 3935e6168fSJeff Roberson #include <sys/lock.h> 4035e6168fSJeff Roberson #include <sys/mutex.h> 4135e6168fSJeff Roberson #include <sys/proc.h> 42245f3abfSJeff Roberson #include <sys/resource.h> 439bacd788SJeff Roberson #include <sys/resourcevar.h> 4435e6168fSJeff Roberson #include <sys/sched.h> 4535e6168fSJeff Roberson #include <sys/smp.h> 4635e6168fSJeff Roberson #include <sys/sx.h> 4735e6168fSJeff Roberson #include <sys/sysctl.h> 4835e6168fSJeff Roberson #include <sys/sysproto.h> 49f5c157d9SJohn Baldwin #include <sys/turnstile.h> 5035e6168fSJeff Roberson #include <sys/vmmeter.h> 5135e6168fSJeff Roberson #ifdef KTRACE 5235e6168fSJeff Roberson #include <sys/uio.h> 5335e6168fSJeff Roberson #include <sys/ktrace.h> 5435e6168fSJeff Roberson #endif 5535e6168fSJeff Roberson 56ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS 57ebccf1e3SJoseph Koshy #include <sys/pmckern.h> 58ebccf1e3SJoseph Koshy #endif 59ebccf1e3SJoseph Koshy 6035e6168fSJeff Roberson #include <machine/cpu.h> 6122bf7d9aSJeff Roberson #include <machine/smp.h> 6235e6168fSJeff Roberson 6335e6168fSJeff Roberson /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 6435e6168fSJeff Roberson /* XXX This is bogus compatability crap for ps */ 6535e6168fSJeff Roberson static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 6635e6168fSJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 6735e6168fSJeff Roberson 6835e6168fSJeff Roberson static void sched_setup(void *dummy); 6935e6168fSJeff Roberson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 7035e6168fSJeff Roberson 71e038d354SScott Long static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "Scheduler"); 72e1f89c22SJeff Roberson 73e038d354SScott Long SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ule", 0, 74e038d354SScott Long "Scheduler name"); 75dc095794SScott Long 7615dc847eSJeff Roberson static int slice_min = 1; 7715dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, ""); 7815dc847eSJeff Roberson 79210491d3SJeff Roberson static int slice_max = 10; 8015dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, ""); 8115dc847eSJeff Roberson 8215dc847eSJeff Roberson int realstathz; 8315dc847eSJeff Roberson int tickincr = 1; 84783caefbSJeff Roberson 8535e6168fSJeff Roberson /* 86ed062c8dSJulian Elischer * The schedulable entity that can be given a context to run. 87ed062c8dSJulian Elischer * A process may have several of these. Probably one per processor 88ed062c8dSJulian Elischer * but posibly a few more. In this universe they are grouped 89ed062c8dSJulian Elischer * with a KSEG that contains the priority and niceness 90ed062c8dSJulian Elischer * for the group. 91ed062c8dSJulian Elischer */ 92ed062c8dSJulian Elischer struct kse { 93ed062c8dSJulian Elischer TAILQ_ENTRY(kse) ke_procq; /* (j/z) Run queue. */ 94ed062c8dSJulian Elischer int ke_flags; /* (j) KEF_* flags. */ 95ed062c8dSJulian Elischer struct thread *ke_thread; /* (*) Active associated thread. */ 96ed062c8dSJulian Elischer fixpt_t ke_pctcpu; /* (j) %cpu during p_swtime. */ 97ed062c8dSJulian Elischer char ke_rqindex; /* (j) Run queue index. */ 98ed062c8dSJulian Elischer enum { 99ed062c8dSJulian Elischer KES_THREAD = 0x0, /* slaved to thread state */ 100ed062c8dSJulian Elischer KES_ONRUNQ 101ed062c8dSJulian Elischer } ke_state; /* (j) thread sched specific status. */ 102ed062c8dSJulian Elischer int ke_slptime; 103ed062c8dSJulian Elischer int ke_slice; 104ed062c8dSJulian Elischer struct runq *ke_runq; 105ed062c8dSJulian Elischer u_char ke_cpu; /* CPU that we have affinity for. */ 106ed062c8dSJulian Elischer /* The following variables are only used for pctcpu calculation */ 107ed062c8dSJulian Elischer int ke_ltick; /* Last tick that we were running on */ 108ed062c8dSJulian Elischer int ke_ftick; /* First tick that we were running on */ 109ed062c8dSJulian Elischer int ke_ticks; /* Tick count */ 110ed062c8dSJulian Elischer 111ed062c8dSJulian Elischer }; 112ed062c8dSJulian Elischer 113ed062c8dSJulian Elischer 114ed062c8dSJulian Elischer #define td_kse td_sched 115ed062c8dSJulian Elischer #define td_slptime td_kse->ke_slptime 116ed062c8dSJulian Elischer #define ke_proc ke_thread->td_proc 117ed062c8dSJulian Elischer #define ke_ksegrp ke_thread->td_ksegrp 118ed062c8dSJulian Elischer 119ed062c8dSJulian Elischer /* flags kept in ke_flags */ 120ed062c8dSJulian Elischer #define KEF_SCHED0 0x00001 /* For scheduler-specific use. */ 121ed062c8dSJulian Elischer #define KEF_SCHED1 0x00002 /* For scheduler-specific use. */ 122ed062c8dSJulian Elischer #define KEF_SCHED2 0x00004 /* For scheduler-specific use. */ 123ed062c8dSJulian Elischer #define KEF_SCHED3 0x00008 /* For scheduler-specific use. */ 1242d59a44dSJeff Roberson #define KEF_SCHED4 0x00010 1258ffb8f55SJeff Roberson #define KEF_SCHED5 0x00020 126ed062c8dSJulian Elischer #define KEF_DIDRUN 0x02000 /* Thread actually ran. */ 127ed062c8dSJulian Elischer #define KEF_EXIT 0x04000 /* Thread is being killed. */ 128ed062c8dSJulian Elischer 129ed062c8dSJulian Elischer /* 13035e6168fSJeff Roberson * These datastructures are allocated within their parent datastructure but 13135e6168fSJeff Roberson * are scheduler specific. 13235e6168fSJeff Roberson */ 13335e6168fSJeff Roberson 13422bf7d9aSJeff Roberson #define ke_assign ke_procq.tqe_next 13522bf7d9aSJeff Roberson 136598b368dSJeff Roberson #define KEF_ASSIGNED 0x0001 /* Thread is being migrated. */ 137598b368dSJeff Roberson #define KEF_BOUND 0x0002 /* Thread can not migrate. */ 138598b368dSJeff Roberson #define KEF_XFERABLE 0x0004 /* Thread was added as transferable. */ 139598b368dSJeff Roberson #define KEF_HOLD 0x0008 /* Thread is temporarily bound. */ 140598b368dSJeff Roberson #define KEF_REMOVED 0x0010 /* Thread was removed while ASSIGNED */ 141f5c157d9SJohn Baldwin #define KEF_INTERNAL 0x0020 14235e6168fSJeff Roberson 14335e6168fSJeff Roberson struct kg_sched { 144ed062c8dSJulian Elischer struct thread *skg_last_assigned; /* (j) Last thread assigned to */ 145ed062c8dSJulian Elischer /* the system scheduler */ 146407b0157SJeff Roberson int skg_slptime; /* Number of ticks we vol. slept */ 147407b0157SJeff Roberson int skg_runtime; /* Number of ticks we were running */ 148ed062c8dSJulian Elischer int skg_avail_opennings; /* (j) Num unfilled slots in group.*/ 149ed062c8dSJulian Elischer int skg_concurrency; /* (j) Num threads requested in group.*/ 15035e6168fSJeff Roberson }; 151ed062c8dSJulian Elischer #define kg_last_assigned kg_sched->skg_last_assigned 152ed062c8dSJulian Elischer #define kg_avail_opennings kg_sched->skg_avail_opennings 153ed062c8dSJulian Elischer #define kg_concurrency kg_sched->skg_concurrency 154407b0157SJeff Roberson #define kg_runtime kg_sched->skg_runtime 155ed062c8dSJulian Elischer #define kg_slptime kg_sched->skg_slptime 15635e6168fSJeff Roberson 157d39063f2SJulian Elischer #define SLOT_RELEASE(kg) \ 158d39063f2SJulian Elischer do { \ 159d39063f2SJulian Elischer kg->kg_avail_opennings++; \ 160d39063f2SJulian Elischer CTR3(KTR_RUNQ, "kg %p(%d) Slot released (->%d)", \ 161d39063f2SJulian Elischer kg, \ 162d39063f2SJulian Elischer kg->kg_concurrency, \ 163d39063f2SJulian Elischer kg->kg_avail_opennings); \ 164d39063f2SJulian Elischer /*KASSERT((kg->kg_avail_opennings <= kg->kg_concurrency), \ 165d39063f2SJulian Elischer ("slots out of whack")); */ \ 166d39063f2SJulian Elischer } while (0) 167d39063f2SJulian Elischer 168d39063f2SJulian Elischer #define SLOT_USE(kg) \ 169d39063f2SJulian Elischer do { \ 170d39063f2SJulian Elischer kg->kg_avail_opennings--; \ 171d39063f2SJulian Elischer CTR3(KTR_RUNQ, "kg %p(%d) Slot used (->%d)", \ 172d39063f2SJulian Elischer kg, \ 173d39063f2SJulian Elischer kg->kg_concurrency, \ 174d39063f2SJulian Elischer kg->kg_avail_opennings); \ 175d39063f2SJulian Elischer /*KASSERT((kg->kg_avail_opennings >= 0), \ 176d39063f2SJulian Elischer ("slots out of whack"));*/ \ 177d39063f2SJulian Elischer } while (0) 178d39063f2SJulian Elischer 179ed062c8dSJulian Elischer static struct kse kse0; 180ed062c8dSJulian Elischer static struct kg_sched kg_sched0; 18135e6168fSJeff Roberson 18235e6168fSJeff Roberson /* 183665cb285SJeff Roberson * The priority is primarily determined by the interactivity score. Thus, we 184665cb285SJeff Roberson * give lower(better) priorities to kse groups that use less CPU. The nice 185665cb285SJeff Roberson * value is then directly added to this to allow nice to have some effect 186665cb285SJeff Roberson * on latency. 187e1f89c22SJeff Roberson * 188e1f89c22SJeff Roberson * PRI_RANGE: Total priority range for timeshare threads. 189665cb285SJeff Roberson * PRI_NRESV: Number of nice values. 190e1f89c22SJeff Roberson * PRI_BASE: The start of the dynamic range. 19135e6168fSJeff Roberson */ 192407b0157SJeff Roberson #define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1) 193a0a931ceSJeff Roberson #define SCHED_PRI_NRESV ((PRIO_MAX - PRIO_MIN) + 1) 194a0a931ceSJeff Roberson #define SCHED_PRI_NHALF (SCHED_PRI_NRESV / 2) 195665cb285SJeff Roberson #define SCHED_PRI_BASE (PRI_MIN_TIMESHARE) 19615dc847eSJeff Roberson #define SCHED_PRI_INTERACT(score) \ 197665cb285SJeff Roberson ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX) 19835e6168fSJeff Roberson 19935e6168fSJeff Roberson /* 200e1f89c22SJeff Roberson * These determine the interactivity of a process. 20135e6168fSJeff Roberson * 202407b0157SJeff Roberson * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate 203407b0157SJeff Roberson * before throttling back. 204d322132cSJeff Roberson * SLP_RUN_FORK: Maximum slp+run time to inherit at fork time. 205210491d3SJeff Roberson * INTERACT_MAX: Maximum interactivity value. Smaller is better. 206e1f89c22SJeff Roberson * INTERACT_THRESH: Threshhold for placement on the current runq. 20735e6168fSJeff Roberson */ 2084c9612c6SJeff Roberson #define SCHED_SLP_RUN_MAX ((hz * 5) << 10) 209d322132cSJeff Roberson #define SCHED_SLP_RUN_FORK ((hz / 2) << 10) 210210491d3SJeff Roberson #define SCHED_INTERACT_MAX (100) 211210491d3SJeff Roberson #define SCHED_INTERACT_HALF (SCHED_INTERACT_MAX / 2) 2124c9612c6SJeff Roberson #define SCHED_INTERACT_THRESH (30) 213e1f89c22SJeff Roberson 21435e6168fSJeff Roberson /* 21535e6168fSJeff Roberson * These parameters and macros determine the size of the time slice that is 21635e6168fSJeff Roberson * granted to each thread. 21735e6168fSJeff Roberson * 21835e6168fSJeff Roberson * SLICE_MIN: Minimum time slice granted, in units of ticks. 21935e6168fSJeff Roberson * SLICE_MAX: Maximum time slice granted. 22035e6168fSJeff Roberson * SLICE_RANGE: Range of available time slices scaled by hz. 221245f3abfSJeff Roberson * SLICE_SCALE: The number slices granted per val in the range of [0, max]. 222245f3abfSJeff Roberson * SLICE_NICE: Determine the amount of slice granted to a scaled nice. 2237d1a81b4SJeff Roberson * SLICE_NTHRESH: The nice cutoff point for slice assignment. 22435e6168fSJeff Roberson */ 22515dc847eSJeff Roberson #define SCHED_SLICE_MIN (slice_min) 22615dc847eSJeff Roberson #define SCHED_SLICE_MAX (slice_max) 2270392e39dSJeff Roberson #define SCHED_SLICE_INTERACTIVE (slice_max) 2287d1a81b4SJeff Roberson #define SCHED_SLICE_NTHRESH (SCHED_PRI_NHALF - 1) 22935e6168fSJeff Roberson #define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1) 23035e6168fSJeff Roberson #define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max)) 231245f3abfSJeff Roberson #define SCHED_SLICE_NICE(nice) \ 2327d1a81b4SJeff Roberson (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_SLICE_NTHRESH)) 23335e6168fSJeff Roberson 23435e6168fSJeff Roberson /* 235ed062c8dSJulian Elischer * This macro determines whether or not the thread belongs on the current or 23635e6168fSJeff Roberson * next run queue. 23735e6168fSJeff Roberson */ 23815dc847eSJeff Roberson #define SCHED_INTERACTIVE(kg) \ 23915dc847eSJeff Roberson (sched_interact_score(kg) < SCHED_INTERACT_THRESH) 240a5f099d0SJeff Roberson #define SCHED_CURR(kg, ke) \ 241f5c157d9SJohn Baldwin ((ke->ke_thread->td_flags & TDF_BORROWING) || SCHED_INTERACTIVE(kg)) 24235e6168fSJeff Roberson 24335e6168fSJeff Roberson /* 24435e6168fSJeff Roberson * Cpu percentage computation macros and defines. 24535e6168fSJeff Roberson * 24635e6168fSJeff Roberson * SCHED_CPU_TIME: Number of seconds to average the cpu usage across. 24735e6168fSJeff Roberson * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across. 24835e6168fSJeff Roberson */ 24935e6168fSJeff Roberson 2505053d272SJeff Roberson #define SCHED_CPU_TIME 10 25135e6168fSJeff Roberson #define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME) 25235e6168fSJeff Roberson 25335e6168fSJeff Roberson /* 25415dc847eSJeff Roberson * kseq - per processor runqs and statistics. 25535e6168fSJeff Roberson */ 25635e6168fSJeff Roberson struct kseq { 257a8949de2SJeff Roberson struct runq ksq_idle; /* Queue of IDLE threads. */ 25815dc847eSJeff Roberson struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */ 25915dc847eSJeff Roberson struct runq *ksq_next; /* Next timeshare queue. */ 26015dc847eSJeff Roberson struct runq *ksq_curr; /* Current queue. */ 261ef1134c9SJeff Roberson int ksq_load_timeshare; /* Load for timeshare. */ 26215dc847eSJeff Roberson int ksq_load; /* Aggregate load. */ 263a0a931ceSJeff Roberson short ksq_nice[SCHED_PRI_NRESV]; /* KSEs in each nice bin. */ 26415dc847eSJeff Roberson short ksq_nicemin; /* Least nice. */ 2655d7ef00cSJeff Roberson #ifdef SMP 26680f86c9fSJeff Roberson int ksq_transferable; 26780f86c9fSJeff Roberson LIST_ENTRY(kseq) ksq_siblings; /* Next in kseq group. */ 26880f86c9fSJeff Roberson struct kseq_group *ksq_group; /* Our processor group. */ 269fa9c9717SJeff Roberson volatile struct kse *ksq_assigned; /* assigned by another CPU. */ 27033916c36SJeff Roberson #else 27133916c36SJeff Roberson int ksq_sysload; /* For loadavg, !ITHD load. */ 2725d7ef00cSJeff Roberson #endif 27335e6168fSJeff Roberson }; 27435e6168fSJeff Roberson 27580f86c9fSJeff Roberson #ifdef SMP 27680f86c9fSJeff Roberson /* 27780f86c9fSJeff Roberson * kseq groups are groups of processors which can cheaply share threads. When 27880f86c9fSJeff Roberson * one processor in the group goes idle it will check the runqs of the other 27980f86c9fSJeff Roberson * processors in its group prior to halting and waiting for an interrupt. 28080f86c9fSJeff Roberson * These groups are suitable for SMT (Symetric Multi-Threading) and not NUMA. 28180f86c9fSJeff Roberson * In a numa environment we'd want an idle bitmap per group and a two tiered 28280f86c9fSJeff Roberson * load balancer. 28380f86c9fSJeff Roberson */ 28480f86c9fSJeff Roberson struct kseq_group { 28580f86c9fSJeff Roberson int ksg_cpus; /* Count of CPUs in this kseq group. */ 286b2ae7ed7SMarcel Moolenaar cpumask_t ksg_cpumask; /* Mask of cpus in this group. */ 287b2ae7ed7SMarcel Moolenaar cpumask_t ksg_idlemask; /* Idle cpus in this group. */ 288b2ae7ed7SMarcel Moolenaar cpumask_t ksg_mask; /* Bit mask for first cpu. */ 289cac77d04SJeff Roberson int ksg_load; /* Total load of this group. */ 29080f86c9fSJeff Roberson int ksg_transferable; /* Transferable load of this group. */ 29180f86c9fSJeff Roberson LIST_HEAD(, kseq) ksg_members; /* Linked list of all members. */ 29280f86c9fSJeff Roberson }; 29380f86c9fSJeff Roberson #endif 29480f86c9fSJeff Roberson 29535e6168fSJeff Roberson /* 29635e6168fSJeff Roberson * One kse queue per processor. 29735e6168fSJeff Roberson */ 2980a016a05SJeff Roberson #ifdef SMP 299b2ae7ed7SMarcel Moolenaar static cpumask_t kseq_idle; 300cac77d04SJeff Roberson static int ksg_maxid; 30122bf7d9aSJeff Roberson static struct kseq kseq_cpu[MAXCPU]; 30280f86c9fSJeff Roberson static struct kseq_group kseq_groups[MAXCPU]; 303dc03363dSJeff Roberson static int bal_tick; 304dc03363dSJeff Roberson static int gbal_tick; 305598b368dSJeff Roberson static int balance_groups; 306dc03363dSJeff Roberson 30780f86c9fSJeff Roberson #define KSEQ_SELF() (&kseq_cpu[PCPU_GET(cpuid)]) 30880f86c9fSJeff Roberson #define KSEQ_CPU(x) (&kseq_cpu[(x)]) 309cac77d04SJeff Roberson #define KSEQ_ID(x) ((x) - kseq_cpu) 310cac77d04SJeff Roberson #define KSEQ_GROUP(x) (&kseq_groups[(x)]) 31180f86c9fSJeff Roberson #else /* !SMP */ 31222bf7d9aSJeff Roberson static struct kseq kseq_cpu; 313dc03363dSJeff Roberson 3140a016a05SJeff Roberson #define KSEQ_SELF() (&kseq_cpu) 3150a016a05SJeff Roberson #define KSEQ_CPU(x) (&kseq_cpu) 3160a016a05SJeff Roberson #endif 31735e6168fSJeff Roberson 318ed062c8dSJulian Elischer static void slot_fill(struct ksegrp *kg); 319ed062c8dSJulian Elischer static struct kse *sched_choose(void); /* XXX Should be thread * */ 320245f3abfSJeff Roberson static void sched_slice(struct kse *ke); 32115dc847eSJeff Roberson static void sched_priority(struct ksegrp *kg); 322f5c157d9SJohn Baldwin static void sched_thread_priority(struct thread *td, u_char prio); 323e1f89c22SJeff Roberson static int sched_interact_score(struct ksegrp *kg); 3244b60e324SJeff Roberson static void sched_interact_update(struct ksegrp *kg); 325d322132cSJeff Roberson static void sched_interact_fork(struct ksegrp *kg); 32622bf7d9aSJeff Roberson static void sched_pctcpu_update(struct kse *ke); 32735e6168fSJeff Roberson 3285d7ef00cSJeff Roberson /* Operations on per processor queues */ 32922bf7d9aSJeff Roberson static struct kse * kseq_choose(struct kseq *kseq); 3300a016a05SJeff Roberson static void kseq_setup(struct kseq *kseq); 331155b9987SJeff Roberson static void kseq_load_add(struct kseq *kseq, struct kse *ke); 332155b9987SJeff Roberson static void kseq_load_rem(struct kseq *kseq, struct kse *ke); 333598b368dSJeff Roberson static __inline void kseq_runq_add(struct kseq *kseq, struct kse *ke, int); 334155b9987SJeff Roberson static __inline void kseq_runq_rem(struct kseq *kseq, struct kse *ke); 33515dc847eSJeff Roberson static void kseq_nice_add(struct kseq *kseq, int nice); 33615dc847eSJeff Roberson static void kseq_nice_rem(struct kseq *kseq, int nice); 3377cd650a9SJeff Roberson void kseq_print(int cpu); 3385d7ef00cSJeff Roberson #ifdef SMP 33980f86c9fSJeff Roberson static int kseq_transfer(struct kseq *ksq, struct kse *ke, int class); 34022bf7d9aSJeff Roberson static struct kse *runq_steal(struct runq *rq); 341dc03363dSJeff Roberson static void sched_balance(void); 342dc03363dSJeff Roberson static void sched_balance_groups(void); 343cac77d04SJeff Roberson static void sched_balance_group(struct kseq_group *ksg); 344cac77d04SJeff Roberson static void sched_balance_pair(struct kseq *high, struct kseq *low); 34522bf7d9aSJeff Roberson static void kseq_move(struct kseq *from, int cpu); 34680f86c9fSJeff Roberson static int kseq_idled(struct kseq *kseq); 34722bf7d9aSJeff Roberson static void kseq_notify(struct kse *ke, int cpu); 34822bf7d9aSJeff Roberson static void kseq_assign(struct kseq *); 34980f86c9fSJeff Roberson static struct kse *kseq_steal(struct kseq *kseq, int stealidle); 350598b368dSJeff Roberson #define KSE_CAN_MIGRATE(ke) \ 3511e7fad6bSScott Long ((ke)->ke_thread->td_pinned == 0 && ((ke)->ke_flags & KEF_BOUND) == 0) 3525d7ef00cSJeff Roberson #endif 3535d7ef00cSJeff Roberson 35415dc847eSJeff Roberson void 3557cd650a9SJeff Roberson kseq_print(int cpu) 35615dc847eSJeff Roberson { 3577cd650a9SJeff Roberson struct kseq *kseq; 35815dc847eSJeff Roberson int i; 35915dc847eSJeff Roberson 3607cd650a9SJeff Roberson kseq = KSEQ_CPU(cpu); 36115dc847eSJeff Roberson 36215dc847eSJeff Roberson printf("kseq:\n"); 36315dc847eSJeff Roberson printf("\tload: %d\n", kseq->ksq_load); 364155b9987SJeff Roberson printf("\tload TIMESHARE: %d\n", kseq->ksq_load_timeshare); 365ef1134c9SJeff Roberson #ifdef SMP 36680f86c9fSJeff Roberson printf("\tload transferable: %d\n", kseq->ksq_transferable); 367ef1134c9SJeff Roberson #endif 36815dc847eSJeff Roberson printf("\tnicemin:\t%d\n", kseq->ksq_nicemin); 36915dc847eSJeff Roberson printf("\tnice counts:\n"); 370a0a931ceSJeff Roberson for (i = 0; i < SCHED_PRI_NRESV; i++) 37115dc847eSJeff Roberson if (kseq->ksq_nice[i]) 37215dc847eSJeff Roberson printf("\t\t%d = %d\n", 37315dc847eSJeff Roberson i - SCHED_PRI_NHALF, kseq->ksq_nice[i]); 37415dc847eSJeff Roberson } 37515dc847eSJeff Roberson 376155b9987SJeff Roberson static __inline void 377598b368dSJeff Roberson kseq_runq_add(struct kseq *kseq, struct kse *ke, int flags) 378155b9987SJeff Roberson { 379155b9987SJeff Roberson #ifdef SMP 380598b368dSJeff Roberson if (KSE_CAN_MIGRATE(ke)) { 38180f86c9fSJeff Roberson kseq->ksq_transferable++; 38280f86c9fSJeff Roberson kseq->ksq_group->ksg_transferable++; 3832454aaf5SJeff Roberson ke->ke_flags |= KEF_XFERABLE; 38480f86c9fSJeff Roberson } 385155b9987SJeff Roberson #endif 386598b368dSJeff Roberson runq_add(ke->ke_runq, ke, flags); 387155b9987SJeff Roberson } 388155b9987SJeff Roberson 389155b9987SJeff Roberson static __inline void 390155b9987SJeff Roberson kseq_runq_rem(struct kseq *kseq, struct kse *ke) 391155b9987SJeff Roberson { 392155b9987SJeff Roberson #ifdef SMP 3932454aaf5SJeff Roberson if (ke->ke_flags & KEF_XFERABLE) { 39480f86c9fSJeff Roberson kseq->ksq_transferable--; 39580f86c9fSJeff Roberson kseq->ksq_group->ksg_transferable--; 3962454aaf5SJeff Roberson ke->ke_flags &= ~KEF_XFERABLE; 39780f86c9fSJeff Roberson } 398155b9987SJeff Roberson #endif 399155b9987SJeff Roberson runq_remove(ke->ke_runq, ke); 400155b9987SJeff Roberson } 401155b9987SJeff Roberson 402a8949de2SJeff Roberson static void 403155b9987SJeff Roberson kseq_load_add(struct kseq *kseq, struct kse *ke) 4045d7ef00cSJeff Roberson { 405ef1134c9SJeff Roberson int class; 406b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 407ef1134c9SJeff Roberson class = PRI_BASE(ke->ke_ksegrp->kg_pri_class); 408ef1134c9SJeff Roberson if (class == PRI_TIMESHARE) 409ef1134c9SJeff Roberson kseq->ksq_load_timeshare++; 41015dc847eSJeff Roberson kseq->ksq_load++; 41181d47d3fSJeff Roberson CTR1(KTR_SCHED, "load: %d", kseq->ksq_load); 412207a6c0dSDavid E. O'Brien if (class != PRI_ITHD && (ke->ke_proc->p_flag & P_NOLOAD) == 0) 41333916c36SJeff Roberson #ifdef SMP 414cac77d04SJeff Roberson kseq->ksq_group->ksg_load++; 41533916c36SJeff Roberson #else 41633916c36SJeff Roberson kseq->ksq_sysload++; 417cac77d04SJeff Roberson #endif 41815dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 419fa885116SJulian Elischer kseq_nice_add(kseq, ke->ke_proc->p_nice); 4205d7ef00cSJeff Roberson } 42115dc847eSJeff Roberson 422a8949de2SJeff Roberson static void 423155b9987SJeff Roberson kseq_load_rem(struct kseq *kseq, struct kse *ke) 4245d7ef00cSJeff Roberson { 425ef1134c9SJeff Roberson int class; 426b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 427ef1134c9SJeff Roberson class = PRI_BASE(ke->ke_ksegrp->kg_pri_class); 428ef1134c9SJeff Roberson if (class == PRI_TIMESHARE) 429ef1134c9SJeff Roberson kseq->ksq_load_timeshare--; 430207a6c0dSDavid E. O'Brien if (class != PRI_ITHD && (ke->ke_proc->p_flag & P_NOLOAD) == 0) 43133916c36SJeff Roberson #ifdef SMP 432cac77d04SJeff Roberson kseq->ksq_group->ksg_load--; 43333916c36SJeff Roberson #else 43433916c36SJeff Roberson kseq->ksq_sysload--; 435cac77d04SJeff Roberson #endif 43615dc847eSJeff Roberson kseq->ksq_load--; 43781d47d3fSJeff Roberson CTR1(KTR_SCHED, "load: %d", kseq->ksq_load); 43815dc847eSJeff Roberson ke->ke_runq = NULL; 43915dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 440fa885116SJulian Elischer kseq_nice_rem(kseq, ke->ke_proc->p_nice); 4415d7ef00cSJeff Roberson } 4425d7ef00cSJeff Roberson 44315dc847eSJeff Roberson static void 44415dc847eSJeff Roberson kseq_nice_add(struct kseq *kseq, int nice) 44515dc847eSJeff Roberson { 446b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 44715dc847eSJeff Roberson /* Normalize to zero. */ 44815dc847eSJeff Roberson kseq->ksq_nice[nice + SCHED_PRI_NHALF]++; 449ef1134c9SJeff Roberson if (nice < kseq->ksq_nicemin || kseq->ksq_load_timeshare == 1) 45015dc847eSJeff Roberson kseq->ksq_nicemin = nice; 45115dc847eSJeff Roberson } 45215dc847eSJeff Roberson 45315dc847eSJeff Roberson static void 45415dc847eSJeff Roberson kseq_nice_rem(struct kseq *kseq, int nice) 45515dc847eSJeff Roberson { 45615dc847eSJeff Roberson int n; 45715dc847eSJeff Roberson 458b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 45915dc847eSJeff Roberson /* Normalize to zero. */ 46015dc847eSJeff Roberson n = nice + SCHED_PRI_NHALF; 46115dc847eSJeff Roberson kseq->ksq_nice[n]--; 46215dc847eSJeff Roberson KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count.")); 46315dc847eSJeff Roberson 46415dc847eSJeff Roberson /* 46515dc847eSJeff Roberson * If this wasn't the smallest nice value or there are more in 46615dc847eSJeff Roberson * this bucket we can just return. Otherwise we have to recalculate 46715dc847eSJeff Roberson * the smallest nice. 46815dc847eSJeff Roberson */ 46915dc847eSJeff Roberson if (nice != kseq->ksq_nicemin || 47015dc847eSJeff Roberson kseq->ksq_nice[n] != 0 || 471ef1134c9SJeff Roberson kseq->ksq_load_timeshare == 0) 47215dc847eSJeff Roberson return; 47315dc847eSJeff Roberson 474a0a931ceSJeff Roberson for (; n < SCHED_PRI_NRESV; n++) 47515dc847eSJeff Roberson if (kseq->ksq_nice[n]) { 47615dc847eSJeff Roberson kseq->ksq_nicemin = n - SCHED_PRI_NHALF; 47715dc847eSJeff Roberson return; 47815dc847eSJeff Roberson } 47915dc847eSJeff Roberson } 48015dc847eSJeff Roberson 4815d7ef00cSJeff Roberson #ifdef SMP 482356500a3SJeff Roberson /* 483155b9987SJeff Roberson * sched_balance is a simple CPU load balancing algorithm. It operates by 484356500a3SJeff Roberson * finding the least loaded and most loaded cpu and equalizing their load 485356500a3SJeff Roberson * by migrating some processes. 486356500a3SJeff Roberson * 487356500a3SJeff Roberson * Dealing only with two CPUs at a time has two advantages. Firstly, most 488356500a3SJeff Roberson * installations will only have 2 cpus. Secondly, load balancing too much at 489356500a3SJeff Roberson * once can have an unpleasant effect on the system. The scheduler rarely has 490356500a3SJeff Roberson * enough information to make perfect decisions. So this algorithm chooses 491356500a3SJeff Roberson * algorithm simplicity and more gradual effects on load in larger systems. 492356500a3SJeff Roberson * 493356500a3SJeff Roberson * It could be improved by considering the priorities and slices assigned to 494356500a3SJeff Roberson * each task prior to balancing them. There are many pathological cases with 495356500a3SJeff Roberson * any approach and so the semi random algorithm below may work as well as any. 496356500a3SJeff Roberson * 497356500a3SJeff Roberson */ 49822bf7d9aSJeff Roberson static void 499dc03363dSJeff Roberson sched_balance(void) 500356500a3SJeff Roberson { 501cac77d04SJeff Roberson struct kseq_group *high; 502cac77d04SJeff Roberson struct kseq_group *low; 503cac77d04SJeff Roberson struct kseq_group *ksg; 504cac77d04SJeff Roberson int cnt; 505356500a3SJeff Roberson int i; 506356500a3SJeff Roberson 507598b368dSJeff Roberson bal_tick = ticks + (random() % (hz * 2)); 50886f8ae96SJeff Roberson if (smp_started == 0) 509598b368dSJeff Roberson return; 510cac77d04SJeff Roberson low = high = NULL; 511cac77d04SJeff Roberson i = random() % (ksg_maxid + 1); 512cac77d04SJeff Roberson for (cnt = 0; cnt <= ksg_maxid; cnt++) { 513cac77d04SJeff Roberson ksg = KSEQ_GROUP(i); 514cac77d04SJeff Roberson /* 515cac77d04SJeff Roberson * Find the CPU with the highest load that has some 516cac77d04SJeff Roberson * threads to transfer. 517cac77d04SJeff Roberson */ 518cac77d04SJeff Roberson if ((high == NULL || ksg->ksg_load > high->ksg_load) 519cac77d04SJeff Roberson && ksg->ksg_transferable) 520cac77d04SJeff Roberson high = ksg; 521cac77d04SJeff Roberson if (low == NULL || ksg->ksg_load < low->ksg_load) 522cac77d04SJeff Roberson low = ksg; 523cac77d04SJeff Roberson if (++i > ksg_maxid) 524cac77d04SJeff Roberson i = 0; 525cac77d04SJeff Roberson } 526cac77d04SJeff Roberson if (low != NULL && high != NULL && high != low) 527cac77d04SJeff Roberson sched_balance_pair(LIST_FIRST(&high->ksg_members), 528cac77d04SJeff Roberson LIST_FIRST(&low->ksg_members)); 529cac77d04SJeff Roberson } 53086f8ae96SJeff Roberson 531cac77d04SJeff Roberson static void 532dc03363dSJeff Roberson sched_balance_groups(void) 533cac77d04SJeff Roberson { 534cac77d04SJeff Roberson int i; 535cac77d04SJeff Roberson 536598b368dSJeff Roberson gbal_tick = ticks + (random() % (hz * 2)); 537dc03363dSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 538cac77d04SJeff Roberson if (smp_started) 539cac77d04SJeff Roberson for (i = 0; i <= ksg_maxid; i++) 540cac77d04SJeff Roberson sched_balance_group(KSEQ_GROUP(i)); 541356500a3SJeff Roberson } 542cac77d04SJeff Roberson 543cac77d04SJeff Roberson static void 544cac77d04SJeff Roberson sched_balance_group(struct kseq_group *ksg) 545cac77d04SJeff Roberson { 546cac77d04SJeff Roberson struct kseq *kseq; 547cac77d04SJeff Roberson struct kseq *high; 548cac77d04SJeff Roberson struct kseq *low; 549cac77d04SJeff Roberson int load; 550cac77d04SJeff Roberson 551cac77d04SJeff Roberson if (ksg->ksg_transferable == 0) 552cac77d04SJeff Roberson return; 553cac77d04SJeff Roberson low = NULL; 554cac77d04SJeff Roberson high = NULL; 555cac77d04SJeff Roberson LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) { 556cac77d04SJeff Roberson load = kseq->ksq_load; 557cac77d04SJeff Roberson if (high == NULL || load > high->ksq_load) 558cac77d04SJeff Roberson high = kseq; 559cac77d04SJeff Roberson if (low == NULL || load < low->ksq_load) 560cac77d04SJeff Roberson low = kseq; 561356500a3SJeff Roberson } 562cac77d04SJeff Roberson if (high != NULL && low != NULL && high != low) 563cac77d04SJeff Roberson sched_balance_pair(high, low); 564356500a3SJeff Roberson } 565cac77d04SJeff Roberson 566cac77d04SJeff Roberson static void 567cac77d04SJeff Roberson sched_balance_pair(struct kseq *high, struct kseq *low) 568cac77d04SJeff Roberson { 569cac77d04SJeff Roberson int transferable; 570cac77d04SJeff Roberson int high_load; 571cac77d04SJeff Roberson int low_load; 572cac77d04SJeff Roberson int move; 573cac77d04SJeff Roberson int diff; 574cac77d04SJeff Roberson int i; 575cac77d04SJeff Roberson 57680f86c9fSJeff Roberson /* 57780f86c9fSJeff Roberson * If we're transfering within a group we have to use this specific 57880f86c9fSJeff Roberson * kseq's transferable count, otherwise we can steal from other members 57980f86c9fSJeff Roberson * of the group. 58080f86c9fSJeff Roberson */ 581cac77d04SJeff Roberson if (high->ksq_group == low->ksq_group) { 582cac77d04SJeff Roberson transferable = high->ksq_transferable; 583cac77d04SJeff Roberson high_load = high->ksq_load; 584cac77d04SJeff Roberson low_load = low->ksq_load; 585cac77d04SJeff Roberson } else { 586cac77d04SJeff Roberson transferable = high->ksq_group->ksg_transferable; 587cac77d04SJeff Roberson high_load = high->ksq_group->ksg_load; 588cac77d04SJeff Roberson low_load = low->ksq_group->ksg_load; 589cac77d04SJeff Roberson } 59080f86c9fSJeff Roberson if (transferable == 0) 591cac77d04SJeff Roberson return; 592155b9987SJeff Roberson /* 593155b9987SJeff Roberson * Determine what the imbalance is and then adjust that to how many 59480f86c9fSJeff Roberson * kses we actually have to give up (transferable). 595155b9987SJeff Roberson */ 596cac77d04SJeff Roberson diff = high_load - low_load; 597356500a3SJeff Roberson move = diff / 2; 598356500a3SJeff Roberson if (diff & 0x1) 599356500a3SJeff Roberson move++; 60080f86c9fSJeff Roberson move = min(move, transferable); 601356500a3SJeff Roberson for (i = 0; i < move; i++) 602cac77d04SJeff Roberson kseq_move(high, KSEQ_ID(low)); 603356500a3SJeff Roberson return; 604356500a3SJeff Roberson } 605356500a3SJeff Roberson 60622bf7d9aSJeff Roberson static void 607356500a3SJeff Roberson kseq_move(struct kseq *from, int cpu) 608356500a3SJeff Roberson { 60980f86c9fSJeff Roberson struct kseq *kseq; 61080f86c9fSJeff Roberson struct kseq *to; 611356500a3SJeff Roberson struct kse *ke; 612356500a3SJeff Roberson 61380f86c9fSJeff Roberson kseq = from; 61480f86c9fSJeff Roberson to = KSEQ_CPU(cpu); 61580f86c9fSJeff Roberson ke = kseq_steal(kseq, 1); 61680f86c9fSJeff Roberson if (ke == NULL) { 61780f86c9fSJeff Roberson struct kseq_group *ksg; 61880f86c9fSJeff Roberson 61980f86c9fSJeff Roberson ksg = kseq->ksq_group; 62080f86c9fSJeff Roberson LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) { 62180f86c9fSJeff Roberson if (kseq == from || kseq->ksq_transferable == 0) 62280f86c9fSJeff Roberson continue; 62380f86c9fSJeff Roberson ke = kseq_steal(kseq, 1); 62480f86c9fSJeff Roberson break; 62580f86c9fSJeff Roberson } 62680f86c9fSJeff Roberson if (ke == NULL) 62780f86c9fSJeff Roberson panic("kseq_move: No KSEs available with a " 62880f86c9fSJeff Roberson "transferable count of %d\n", 62980f86c9fSJeff Roberson ksg->ksg_transferable); 63080f86c9fSJeff Roberson } 63180f86c9fSJeff Roberson if (kseq == to) 63280f86c9fSJeff Roberson return; 633356500a3SJeff Roberson ke->ke_state = KES_THREAD; 63480f86c9fSJeff Roberson kseq_runq_rem(kseq, ke); 63580f86c9fSJeff Roberson kseq_load_rem(kseq, ke); 636112b6d3aSJeff Roberson kseq_notify(ke, cpu); 637356500a3SJeff Roberson } 63822bf7d9aSJeff Roberson 63980f86c9fSJeff Roberson static int 64080f86c9fSJeff Roberson kseq_idled(struct kseq *kseq) 64122bf7d9aSJeff Roberson { 64280f86c9fSJeff Roberson struct kseq_group *ksg; 64380f86c9fSJeff Roberson struct kseq *steal; 64480f86c9fSJeff Roberson struct kse *ke; 64580f86c9fSJeff Roberson 64680f86c9fSJeff Roberson ksg = kseq->ksq_group; 64780f86c9fSJeff Roberson /* 64880f86c9fSJeff Roberson * If we're in a cpu group, try and steal kses from another cpu in 64980f86c9fSJeff Roberson * the group before idling. 65080f86c9fSJeff Roberson */ 65180f86c9fSJeff Roberson if (ksg->ksg_cpus > 1 && ksg->ksg_transferable) { 65280f86c9fSJeff Roberson LIST_FOREACH(steal, &ksg->ksg_members, ksq_siblings) { 65380f86c9fSJeff Roberson if (steal == kseq || steal->ksq_transferable == 0) 65480f86c9fSJeff Roberson continue; 65580f86c9fSJeff Roberson ke = kseq_steal(steal, 0); 65680f86c9fSJeff Roberson if (ke == NULL) 65780f86c9fSJeff Roberson continue; 65880f86c9fSJeff Roberson ke->ke_state = KES_THREAD; 65980f86c9fSJeff Roberson kseq_runq_rem(steal, ke); 66080f86c9fSJeff Roberson kseq_load_rem(steal, ke); 66180f86c9fSJeff Roberson ke->ke_cpu = PCPU_GET(cpuid); 662598b368dSJeff Roberson ke->ke_flags |= KEF_INTERNAL | KEF_HOLD; 663598b368dSJeff Roberson sched_add(ke->ke_thread, SRQ_YIELDING); 66480f86c9fSJeff Roberson return (0); 66580f86c9fSJeff Roberson } 66680f86c9fSJeff Roberson } 66780f86c9fSJeff Roberson /* 66880f86c9fSJeff Roberson * We only set the idled bit when all of the cpus in the group are 66980f86c9fSJeff Roberson * idle. Otherwise we could get into a situation where a KSE bounces 67080f86c9fSJeff Roberson * back and forth between two idle cores on seperate physical CPUs. 67180f86c9fSJeff Roberson */ 67280f86c9fSJeff Roberson ksg->ksg_idlemask |= PCPU_GET(cpumask); 67380f86c9fSJeff Roberson if (ksg->ksg_idlemask != ksg->ksg_cpumask) 67480f86c9fSJeff Roberson return (1); 67580f86c9fSJeff Roberson atomic_set_int(&kseq_idle, ksg->ksg_mask); 67680f86c9fSJeff Roberson return (1); 67722bf7d9aSJeff Roberson } 67822bf7d9aSJeff Roberson 67922bf7d9aSJeff Roberson static void 68022bf7d9aSJeff Roberson kseq_assign(struct kseq *kseq) 68122bf7d9aSJeff Roberson { 68222bf7d9aSJeff Roberson struct kse *nke; 68322bf7d9aSJeff Roberson struct kse *ke; 68422bf7d9aSJeff Roberson 68522bf7d9aSJeff Roberson do { 68600fbcda8SAlexander Kabaev *(volatile struct kse **)&ke = kseq->ksq_assigned; 68722bf7d9aSJeff Roberson } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke, NULL)); 68822bf7d9aSJeff Roberson for (; ke != NULL; ke = nke) { 68922bf7d9aSJeff Roberson nke = ke->ke_assign; 690598b368dSJeff Roberson kseq->ksq_group->ksg_load--; 691598b368dSJeff Roberson kseq->ksq_load--; 69222bf7d9aSJeff Roberson ke->ke_flags &= ~KEF_ASSIGNED; 693598b368dSJeff Roberson ke->ke_flags |= KEF_INTERNAL | KEF_HOLD; 694598b368dSJeff Roberson sched_add(ke->ke_thread, SRQ_YIELDING); 69522bf7d9aSJeff Roberson } 69622bf7d9aSJeff Roberson } 69722bf7d9aSJeff Roberson 69822bf7d9aSJeff Roberson static void 69922bf7d9aSJeff Roberson kseq_notify(struct kse *ke, int cpu) 70022bf7d9aSJeff Roberson { 70122bf7d9aSJeff Roberson struct kseq *kseq; 70222bf7d9aSJeff Roberson struct thread *td; 70322bf7d9aSJeff Roberson struct pcpu *pcpu; 704598b368dSJeff Roberson int class; 7052454aaf5SJeff Roberson int prio; 70622bf7d9aSJeff Roberson 707598b368dSJeff Roberson kseq = KSEQ_CPU(cpu); 708598b368dSJeff Roberson /* XXX */ 709598b368dSJeff Roberson class = PRI_BASE(ke->ke_ksegrp->kg_pri_class); 710598b368dSJeff Roberson if ((class == PRI_TIMESHARE || class == PRI_REALTIME) && 711598b368dSJeff Roberson (kseq_idle & kseq->ksq_group->ksg_mask)) 712598b368dSJeff Roberson atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask); 713598b368dSJeff Roberson kseq->ksq_group->ksg_load++; 714598b368dSJeff Roberson kseq->ksq_load++; 71586e1c22aSJeff Roberson ke->ke_cpu = cpu; 71622bf7d9aSJeff Roberson ke->ke_flags |= KEF_ASSIGNED; 7172454aaf5SJeff Roberson prio = ke->ke_thread->td_priority; 71822bf7d9aSJeff Roberson 7190c0a98b2SJeff Roberson /* 72022bf7d9aSJeff Roberson * Place a KSE on another cpu's queue and force a resched. 72122bf7d9aSJeff Roberson */ 72222bf7d9aSJeff Roberson do { 72300fbcda8SAlexander Kabaev *(volatile struct kse **)&ke->ke_assign = kseq->ksq_assigned; 72422bf7d9aSJeff Roberson } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke->ke_assign, ke)); 7252454aaf5SJeff Roberson /* 7262454aaf5SJeff Roberson * Without sched_lock we could lose a race where we set NEEDRESCHED 7272454aaf5SJeff Roberson * on a thread that is switched out before the IPI is delivered. This 7282454aaf5SJeff Roberson * would lead us to miss the resched. This will be a problem once 7292454aaf5SJeff Roberson * sched_lock is pushed down. 7302454aaf5SJeff Roberson */ 73122bf7d9aSJeff Roberson pcpu = pcpu_find(cpu); 73222bf7d9aSJeff Roberson td = pcpu->pc_curthread; 73322bf7d9aSJeff Roberson if (ke->ke_thread->td_priority < td->td_priority || 73422bf7d9aSJeff Roberson td == pcpu->pc_idlethread) { 73522bf7d9aSJeff Roberson td->td_flags |= TDF_NEEDRESCHED; 73622bf7d9aSJeff Roberson ipi_selected(1 << cpu, IPI_AST); 73722bf7d9aSJeff Roberson } 73822bf7d9aSJeff Roberson } 73922bf7d9aSJeff Roberson 74022bf7d9aSJeff Roberson static struct kse * 74122bf7d9aSJeff Roberson runq_steal(struct runq *rq) 74222bf7d9aSJeff Roberson { 74322bf7d9aSJeff Roberson struct rqhead *rqh; 74422bf7d9aSJeff Roberson struct rqbits *rqb; 74522bf7d9aSJeff Roberson struct kse *ke; 74622bf7d9aSJeff Roberson int word; 74722bf7d9aSJeff Roberson int bit; 74822bf7d9aSJeff Roberson 74922bf7d9aSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 75022bf7d9aSJeff Roberson rqb = &rq->rq_status; 75122bf7d9aSJeff Roberson for (word = 0; word < RQB_LEN; word++) { 75222bf7d9aSJeff Roberson if (rqb->rqb_bits[word] == 0) 75322bf7d9aSJeff Roberson continue; 75422bf7d9aSJeff Roberson for (bit = 0; bit < RQB_BPW; bit++) { 755a2640c9bSPeter Wemm if ((rqb->rqb_bits[word] & (1ul << bit)) == 0) 75622bf7d9aSJeff Roberson continue; 75722bf7d9aSJeff Roberson rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)]; 75822bf7d9aSJeff Roberson TAILQ_FOREACH(ke, rqh, ke_procq) { 759598b368dSJeff Roberson if (KSE_CAN_MIGRATE(ke)) 76022bf7d9aSJeff Roberson return (ke); 76122bf7d9aSJeff Roberson } 76222bf7d9aSJeff Roberson } 76322bf7d9aSJeff Roberson } 76422bf7d9aSJeff Roberson return (NULL); 76522bf7d9aSJeff Roberson } 76622bf7d9aSJeff Roberson 76722bf7d9aSJeff Roberson static struct kse * 76880f86c9fSJeff Roberson kseq_steal(struct kseq *kseq, int stealidle) 76922bf7d9aSJeff Roberson { 77022bf7d9aSJeff Roberson struct kse *ke; 77122bf7d9aSJeff Roberson 77280f86c9fSJeff Roberson /* 77380f86c9fSJeff Roberson * Steal from next first to try to get a non-interactive task that 77480f86c9fSJeff Roberson * may not have run for a while. 77580f86c9fSJeff Roberson */ 77622bf7d9aSJeff Roberson if ((ke = runq_steal(kseq->ksq_next)) != NULL) 77722bf7d9aSJeff Roberson return (ke); 77880f86c9fSJeff Roberson if ((ke = runq_steal(kseq->ksq_curr)) != NULL) 77980f86c9fSJeff Roberson return (ke); 78080f86c9fSJeff Roberson if (stealidle) 78122bf7d9aSJeff Roberson return (runq_steal(&kseq->ksq_idle)); 78280f86c9fSJeff Roberson return (NULL); 78322bf7d9aSJeff Roberson } 78480f86c9fSJeff Roberson 78580f86c9fSJeff Roberson int 78680f86c9fSJeff Roberson kseq_transfer(struct kseq *kseq, struct kse *ke, int class) 78780f86c9fSJeff Roberson { 788598b368dSJeff Roberson struct kseq_group *nksg; 78980f86c9fSJeff Roberson struct kseq_group *ksg; 790598b368dSJeff Roberson struct kseq *old; 79180f86c9fSJeff Roberson int cpu; 792598b368dSJeff Roberson int idx; 79380f86c9fSJeff Roberson 794670c524fSJeff Roberson if (smp_started == 0) 795670c524fSJeff Roberson return (0); 79680f86c9fSJeff Roberson cpu = 0; 79780f86c9fSJeff Roberson /* 7982454aaf5SJeff Roberson * If our load exceeds a certain threshold we should attempt to 7992454aaf5SJeff Roberson * reassign this thread. The first candidate is the cpu that 8002454aaf5SJeff Roberson * originally ran the thread. If it is idle, assign it there, 8012454aaf5SJeff Roberson * otherwise, pick an idle cpu. 8022454aaf5SJeff Roberson * 8032454aaf5SJeff Roberson * The threshold at which we start to reassign kses has a large impact 804670c524fSJeff Roberson * on the overall performance of the system. Tuned too high and 805670c524fSJeff Roberson * some CPUs may idle. Too low and there will be excess migration 806d50c87deSOlivier Houchard * and context switches. 807670c524fSJeff Roberson */ 808598b368dSJeff Roberson old = KSEQ_CPU(ke->ke_cpu); 809598b368dSJeff Roberson nksg = old->ksq_group; 8102454aaf5SJeff Roberson ksg = kseq->ksq_group; 811598b368dSJeff Roberson if (kseq_idle) { 812598b368dSJeff Roberson if (kseq_idle & nksg->ksg_mask) { 813598b368dSJeff Roberson cpu = ffs(nksg->ksg_idlemask); 814598b368dSJeff Roberson if (cpu) { 815598b368dSJeff Roberson CTR2(KTR_SCHED, 816598b368dSJeff Roberson "kseq_transfer: %p found old cpu %X " 817598b368dSJeff Roberson "in idlemask.", ke, cpu); 8182454aaf5SJeff Roberson goto migrate; 8192454aaf5SJeff Roberson } 820598b368dSJeff Roberson } 82180f86c9fSJeff Roberson /* 82280f86c9fSJeff Roberson * Multiple cpus could find this bit simultaneously 82380f86c9fSJeff Roberson * but the race shouldn't be terrible. 82480f86c9fSJeff Roberson */ 82580f86c9fSJeff Roberson cpu = ffs(kseq_idle); 826598b368dSJeff Roberson if (cpu) { 827598b368dSJeff Roberson CTR2(KTR_SCHED, "kseq_transfer: %p found %X " 828598b368dSJeff Roberson "in idlemask.", ke, cpu); 8292454aaf5SJeff Roberson goto migrate; 83080f86c9fSJeff Roberson } 831598b368dSJeff Roberson } 832598b368dSJeff Roberson idx = 0; 833598b368dSJeff Roberson #if 0 834598b368dSJeff Roberson if (old->ksq_load < kseq->ksq_load) { 835598b368dSJeff Roberson cpu = ke->ke_cpu + 1; 836598b368dSJeff Roberson CTR2(KTR_SCHED, "kseq_transfer: %p old cpu %X " 837598b368dSJeff Roberson "load less than ours.", ke, cpu); 838598b368dSJeff Roberson goto migrate; 839598b368dSJeff Roberson } 840598b368dSJeff Roberson /* 841598b368dSJeff Roberson * No new CPU was found, look for one with less load. 842598b368dSJeff Roberson */ 843598b368dSJeff Roberson for (idx = 0; idx <= ksg_maxid; idx++) { 844598b368dSJeff Roberson nksg = KSEQ_GROUP(idx); 845598b368dSJeff Roberson if (nksg->ksg_load /*+ (nksg->ksg_cpus * 2)*/ < ksg->ksg_load) { 846598b368dSJeff Roberson cpu = ffs(nksg->ksg_cpumask); 847598b368dSJeff Roberson CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X load less " 848598b368dSJeff Roberson "than ours.", ke, cpu); 849598b368dSJeff Roberson goto migrate; 850598b368dSJeff Roberson } 851598b368dSJeff Roberson } 852598b368dSJeff Roberson #endif 85380f86c9fSJeff Roberson /* 85480f86c9fSJeff Roberson * If another cpu in this group has idled, assign a thread over 85580f86c9fSJeff Roberson * to them after checking to see if there are idled groups. 85680f86c9fSJeff Roberson */ 8572454aaf5SJeff Roberson if (ksg->ksg_idlemask) { 85880f86c9fSJeff Roberson cpu = ffs(ksg->ksg_idlemask); 859598b368dSJeff Roberson if (cpu) { 860598b368dSJeff Roberson CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X idle in " 861598b368dSJeff Roberson "group.", ke, cpu); 8622454aaf5SJeff Roberson goto migrate; 86380f86c9fSJeff Roberson } 864598b368dSJeff Roberson } 8652454aaf5SJeff Roberson return (0); 8662454aaf5SJeff Roberson migrate: 8672454aaf5SJeff Roberson /* 86880f86c9fSJeff Roberson * Now that we've found an idle CPU, migrate the thread. 86980f86c9fSJeff Roberson */ 87080f86c9fSJeff Roberson cpu--; 87180f86c9fSJeff Roberson ke->ke_runq = NULL; 87280f86c9fSJeff Roberson kseq_notify(ke, cpu); 8732454aaf5SJeff Roberson 87480f86c9fSJeff Roberson return (1); 87580f86c9fSJeff Roberson } 87680f86c9fSJeff Roberson 87722bf7d9aSJeff Roberson #endif /* SMP */ 87822bf7d9aSJeff Roberson 87922bf7d9aSJeff Roberson /* 88022bf7d9aSJeff Roberson * Pick the highest priority task we have and return it. 8810c0a98b2SJeff Roberson */ 8820c0a98b2SJeff Roberson 88322bf7d9aSJeff Roberson static struct kse * 88422bf7d9aSJeff Roberson kseq_choose(struct kseq *kseq) 8855d7ef00cSJeff Roberson { 8865d7ef00cSJeff Roberson struct runq *swap; 8870516c8ddSJeff Roberson struct kse *ke; 8880516c8ddSJeff Roberson int nice; 8895d7ef00cSJeff Roberson 890b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 89115dc847eSJeff Roberson swap = NULL; 892a8949de2SJeff Roberson 89315dc847eSJeff Roberson for (;;) { 89415dc847eSJeff Roberson ke = runq_choose(kseq->ksq_curr); 89515dc847eSJeff Roberson if (ke == NULL) { 89615dc847eSJeff Roberson /* 897bf0acc27SJohn Baldwin * We already swapped once and didn't get anywhere. 89815dc847eSJeff Roberson */ 89915dc847eSJeff Roberson if (swap) 90015dc847eSJeff Roberson break; 9015d7ef00cSJeff Roberson swap = kseq->ksq_curr; 9025d7ef00cSJeff Roberson kseq->ksq_curr = kseq->ksq_next; 9035d7ef00cSJeff Roberson kseq->ksq_next = swap; 90415dc847eSJeff Roberson continue; 905a8949de2SJeff Roberson } 90615dc847eSJeff Roberson /* 90715dc847eSJeff Roberson * If we encounter a slice of 0 the kse is in a 90815dc847eSJeff Roberson * TIMESHARE kse group and its nice was too far out 90915dc847eSJeff Roberson * of the range that receives slices. 91015dc847eSJeff Roberson */ 9110516c8ddSJeff Roberson nice = ke->ke_proc->p_nice + (0 - kseq->ksq_nicemin); 9128ffb8f55SJeff Roberson if (ke->ke_slice == 0 || (nice > SCHED_SLICE_NTHRESH && 9138ffb8f55SJeff Roberson ke->ke_proc->p_nice != 0)) { 91415dc847eSJeff Roberson runq_remove(ke->ke_runq, ke); 91515dc847eSJeff Roberson sched_slice(ke); 91615dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 917c20c691bSJulian Elischer runq_add(ke->ke_runq, ke, 0); 91815dc847eSJeff Roberson continue; 91915dc847eSJeff Roberson } 92015dc847eSJeff Roberson return (ke); 92115dc847eSJeff Roberson } 92215dc847eSJeff Roberson 923a8949de2SJeff Roberson return (runq_choose(&kseq->ksq_idle)); 924245f3abfSJeff Roberson } 9250a016a05SJeff Roberson 9260a016a05SJeff Roberson static void 9270a016a05SJeff Roberson kseq_setup(struct kseq *kseq) 9280a016a05SJeff Roberson { 92915dc847eSJeff Roberson runq_init(&kseq->ksq_timeshare[0]); 93015dc847eSJeff Roberson runq_init(&kseq->ksq_timeshare[1]); 931a8949de2SJeff Roberson runq_init(&kseq->ksq_idle); 93215dc847eSJeff Roberson kseq->ksq_curr = &kseq->ksq_timeshare[0]; 93315dc847eSJeff Roberson kseq->ksq_next = &kseq->ksq_timeshare[1]; 9347cd650a9SJeff Roberson kseq->ksq_load = 0; 935ef1134c9SJeff Roberson kseq->ksq_load_timeshare = 0; 9360a016a05SJeff Roberson } 9370a016a05SJeff Roberson 93835e6168fSJeff Roberson static void 93935e6168fSJeff Roberson sched_setup(void *dummy) 94035e6168fSJeff Roberson { 9410ec896fdSJeff Roberson #ifdef SMP 94235e6168fSJeff Roberson int i; 9430ec896fdSJeff Roberson #endif 94435e6168fSJeff Roberson 945e493a5d9SJeff Roberson slice_min = (hz/100); /* 10ms */ 946e493a5d9SJeff Roberson slice_max = (hz/7); /* ~140ms */ 947e1f89c22SJeff Roberson 948356500a3SJeff Roberson #ifdef SMP 949cac77d04SJeff Roberson balance_groups = 0; 95080f86c9fSJeff Roberson /* 95180f86c9fSJeff Roberson * Initialize the kseqs. 95280f86c9fSJeff Roberson */ 953749d01b0SJeff Roberson for (i = 0; i < MAXCPU; i++) { 95480f86c9fSJeff Roberson struct kseq *ksq; 95580f86c9fSJeff Roberson 95680f86c9fSJeff Roberson ksq = &kseq_cpu[i]; 95780f86c9fSJeff Roberson ksq->ksq_assigned = NULL; 958749d01b0SJeff Roberson kseq_setup(&kseq_cpu[i]); 95980f86c9fSJeff Roberson } 96080f86c9fSJeff Roberson if (smp_topology == NULL) { 96180f86c9fSJeff Roberson struct kseq_group *ksg; 96280f86c9fSJeff Roberson struct kseq *ksq; 963598b368dSJeff Roberson int cpus; 96480f86c9fSJeff Roberson 965598b368dSJeff Roberson for (cpus = 0, i = 0; i < MAXCPU; i++) { 966598b368dSJeff Roberson if (CPU_ABSENT(i)) 967598b368dSJeff Roberson continue; 968598b368dSJeff Roberson ksq = &kseq_cpu[cpus]; 969598b368dSJeff Roberson ksg = &kseq_groups[cpus]; 97080f86c9fSJeff Roberson /* 971dc03363dSJeff Roberson * Setup a kseq group with one member. 97280f86c9fSJeff Roberson */ 97380f86c9fSJeff Roberson ksq->ksq_transferable = 0; 97480f86c9fSJeff Roberson ksq->ksq_group = ksg; 97580f86c9fSJeff Roberson ksg->ksg_cpus = 1; 97680f86c9fSJeff Roberson ksg->ksg_idlemask = 0; 97780f86c9fSJeff Roberson ksg->ksg_cpumask = ksg->ksg_mask = 1 << i; 978cac77d04SJeff Roberson ksg->ksg_load = 0; 97980f86c9fSJeff Roberson ksg->ksg_transferable = 0; 98080f86c9fSJeff Roberson LIST_INIT(&ksg->ksg_members); 98180f86c9fSJeff Roberson LIST_INSERT_HEAD(&ksg->ksg_members, ksq, ksq_siblings); 982598b368dSJeff Roberson cpus++; 983749d01b0SJeff Roberson } 984598b368dSJeff Roberson ksg_maxid = cpus - 1; 985749d01b0SJeff Roberson } else { 98680f86c9fSJeff Roberson struct kseq_group *ksg; 98780f86c9fSJeff Roberson struct cpu_group *cg; 988749d01b0SJeff Roberson int j; 989749d01b0SJeff Roberson 990749d01b0SJeff Roberson for (i = 0; i < smp_topology->ct_count; i++) { 991749d01b0SJeff Roberson cg = &smp_topology->ct_group[i]; 99280f86c9fSJeff Roberson ksg = &kseq_groups[i]; 99380f86c9fSJeff Roberson /* 99480f86c9fSJeff Roberson * Initialize the group. 99580f86c9fSJeff Roberson */ 99680f86c9fSJeff Roberson ksg->ksg_idlemask = 0; 997cac77d04SJeff Roberson ksg->ksg_load = 0; 99880f86c9fSJeff Roberson ksg->ksg_transferable = 0; 99980f86c9fSJeff Roberson ksg->ksg_cpus = cg->cg_count; 100080f86c9fSJeff Roberson ksg->ksg_cpumask = cg->cg_mask; 100180f86c9fSJeff Roberson LIST_INIT(&ksg->ksg_members); 100280f86c9fSJeff Roberson /* 100380f86c9fSJeff Roberson * Find all of the group members and add them. 100480f86c9fSJeff Roberson */ 100580f86c9fSJeff Roberson for (j = 0; j < MAXCPU; j++) { 100680f86c9fSJeff Roberson if ((cg->cg_mask & (1 << j)) != 0) { 100780f86c9fSJeff Roberson if (ksg->ksg_mask == 0) 100880f86c9fSJeff Roberson ksg->ksg_mask = 1 << j; 100980f86c9fSJeff Roberson kseq_cpu[j].ksq_transferable = 0; 101080f86c9fSJeff Roberson kseq_cpu[j].ksq_group = ksg; 101180f86c9fSJeff Roberson LIST_INSERT_HEAD(&ksg->ksg_members, 101280f86c9fSJeff Roberson &kseq_cpu[j], ksq_siblings); 101380f86c9fSJeff Roberson } 101480f86c9fSJeff Roberson } 1015cac77d04SJeff Roberson if (ksg->ksg_cpus > 1) 1016cac77d04SJeff Roberson balance_groups = 1; 1017749d01b0SJeff Roberson } 1018cac77d04SJeff Roberson ksg_maxid = smp_topology->ct_count - 1; 1019749d01b0SJeff Roberson } 1020cac77d04SJeff Roberson /* 1021cac77d04SJeff Roberson * Stagger the group and global load balancer so they do not 1022cac77d04SJeff Roberson * interfere with each other. 1023cac77d04SJeff Roberson */ 1024dc03363dSJeff Roberson bal_tick = ticks + hz; 1025cac77d04SJeff Roberson if (balance_groups) 1026dc03363dSJeff Roberson gbal_tick = ticks + (hz / 2); 1027749d01b0SJeff Roberson #else 1028749d01b0SJeff Roberson kseq_setup(KSEQ_SELF()); 1029356500a3SJeff Roberson #endif 1030749d01b0SJeff Roberson mtx_lock_spin(&sched_lock); 1031155b9987SJeff Roberson kseq_load_add(KSEQ_SELF(), &kse0); 1032749d01b0SJeff Roberson mtx_unlock_spin(&sched_lock); 103335e6168fSJeff Roberson } 103435e6168fSJeff Roberson 103535e6168fSJeff Roberson /* 103635e6168fSJeff Roberson * Scale the scheduling priority according to the "interactivity" of this 103735e6168fSJeff Roberson * process. 103835e6168fSJeff Roberson */ 103915dc847eSJeff Roberson static void 104035e6168fSJeff Roberson sched_priority(struct ksegrp *kg) 104135e6168fSJeff Roberson { 104235e6168fSJeff Roberson int pri; 104335e6168fSJeff Roberson 104435e6168fSJeff Roberson if (kg->kg_pri_class != PRI_TIMESHARE) 104515dc847eSJeff Roberson return; 104635e6168fSJeff Roberson 104715dc847eSJeff Roberson pri = SCHED_PRI_INTERACT(sched_interact_score(kg)); 1048e1f89c22SJeff Roberson pri += SCHED_PRI_BASE; 1049fa885116SJulian Elischer pri += kg->kg_proc->p_nice; 105035e6168fSJeff Roberson 105135e6168fSJeff Roberson if (pri > PRI_MAX_TIMESHARE) 105235e6168fSJeff Roberson pri = PRI_MAX_TIMESHARE; 105335e6168fSJeff Roberson else if (pri < PRI_MIN_TIMESHARE) 105435e6168fSJeff Roberson pri = PRI_MIN_TIMESHARE; 105535e6168fSJeff Roberson 105635e6168fSJeff Roberson kg->kg_user_pri = pri; 105735e6168fSJeff Roberson 105815dc847eSJeff Roberson return; 105935e6168fSJeff Roberson } 106035e6168fSJeff Roberson 106135e6168fSJeff Roberson /* 1062245f3abfSJeff Roberson * Calculate a time slice based on the properties of the kseg and the runq 1063a8949de2SJeff Roberson * that we're on. This is only for PRI_TIMESHARE ksegrps. 106435e6168fSJeff Roberson */ 1065245f3abfSJeff Roberson static void 1066245f3abfSJeff Roberson sched_slice(struct kse *ke) 106735e6168fSJeff Roberson { 106815dc847eSJeff Roberson struct kseq *kseq; 1069245f3abfSJeff Roberson struct ksegrp *kg; 107035e6168fSJeff Roberson 1071245f3abfSJeff Roberson kg = ke->ke_ksegrp; 107215dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 107335e6168fSJeff Roberson 1074f5c157d9SJohn Baldwin if (ke->ke_thread->td_flags & TDF_BORROWING) { 10758ffb8f55SJeff Roberson ke->ke_slice = SCHED_SLICE_MIN; 10768ffb8f55SJeff Roberson return; 10778ffb8f55SJeff Roberson } 10788ffb8f55SJeff Roberson 1079245f3abfSJeff Roberson /* 1080245f3abfSJeff Roberson * Rationale: 10812454aaf5SJeff Roberson * KSEs in interactive ksegs get a minimal slice so that we 1082245f3abfSJeff Roberson * quickly notice if it abuses its advantage. 1083245f3abfSJeff Roberson * 1084245f3abfSJeff Roberson * KSEs in non-interactive ksegs are assigned a slice that is 1085245f3abfSJeff Roberson * based on the ksegs nice value relative to the least nice kseg 1086245f3abfSJeff Roberson * on the run queue for this cpu. 1087245f3abfSJeff Roberson * 1088245f3abfSJeff Roberson * If the KSE is less nice than all others it gets the maximum 1089245f3abfSJeff Roberson * slice and other KSEs will adjust their slice relative to 1090245f3abfSJeff Roberson * this when they first expire. 1091245f3abfSJeff Roberson * 1092245f3abfSJeff Roberson * There is 20 point window that starts relative to the least 1093245f3abfSJeff Roberson * nice kse on the run queue. Slice size is determined by 1094245f3abfSJeff Roberson * the kse distance from the last nice ksegrp. 1095245f3abfSJeff Roberson * 10967d1a81b4SJeff Roberson * If the kse is outside of the window it will get no slice 10977d1a81b4SJeff Roberson * and will be reevaluated each time it is selected on the 10987d1a81b4SJeff Roberson * run queue. The exception to this is nice 0 ksegs when 10997d1a81b4SJeff Roberson * a nice -20 is running. They are always granted a minimum 11007d1a81b4SJeff Roberson * slice. 1101245f3abfSJeff Roberson */ 110215dc847eSJeff Roberson if (!SCHED_INTERACTIVE(kg)) { 1103245f3abfSJeff Roberson int nice; 1104245f3abfSJeff Roberson 1105fa885116SJulian Elischer nice = kg->kg_proc->p_nice + (0 - kseq->ksq_nicemin); 1106ef1134c9SJeff Roberson if (kseq->ksq_load_timeshare == 0 || 1107fa885116SJulian Elischer kg->kg_proc->p_nice < kseq->ksq_nicemin) 1108245f3abfSJeff Roberson ke->ke_slice = SCHED_SLICE_MAX; 11097d1a81b4SJeff Roberson else if (nice <= SCHED_SLICE_NTHRESH) 1110245f3abfSJeff Roberson ke->ke_slice = SCHED_SLICE_NICE(nice); 1111fa885116SJulian Elischer else if (kg->kg_proc->p_nice == 0) 11127d1a81b4SJeff Roberson ke->ke_slice = SCHED_SLICE_MIN; 1113245f3abfSJeff Roberson else 1114245f3abfSJeff Roberson ke->ke_slice = 0; 1115245f3abfSJeff Roberson } else 11169b5f6f62SJeff Roberson ke->ke_slice = SCHED_SLICE_INTERACTIVE; 111735e6168fSJeff Roberson 1118245f3abfSJeff Roberson return; 111935e6168fSJeff Roberson } 112035e6168fSJeff Roberson 1121d322132cSJeff Roberson /* 1122d322132cSJeff Roberson * This routine enforces a maximum limit on the amount of scheduling history 1123d322132cSJeff Roberson * kept. It is called after either the slptime or runtime is adjusted. 1124d322132cSJeff Roberson * This routine will not operate correctly when slp or run times have been 1125d322132cSJeff Roberson * adjusted to more than double their maximum. 1126d322132cSJeff Roberson */ 11274b60e324SJeff Roberson static void 11284b60e324SJeff Roberson sched_interact_update(struct ksegrp *kg) 11294b60e324SJeff Roberson { 1130d322132cSJeff Roberson int sum; 11313f741ca1SJeff Roberson 1132d322132cSJeff Roberson sum = kg->kg_runtime + kg->kg_slptime; 1133d322132cSJeff Roberson if (sum < SCHED_SLP_RUN_MAX) 1134d322132cSJeff Roberson return; 1135d322132cSJeff Roberson /* 1136d322132cSJeff Roberson * If we have exceeded by more than 1/5th then the algorithm below 1137d322132cSJeff Roberson * will not bring us back into range. Dividing by two here forces 11382454aaf5SJeff Roberson * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX] 1139d322132cSJeff Roberson */ 114037a35e4aSJeff Roberson if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) { 1141d322132cSJeff Roberson kg->kg_runtime /= 2; 1142d322132cSJeff Roberson kg->kg_slptime /= 2; 1143d322132cSJeff Roberson return; 1144d322132cSJeff Roberson } 1145d322132cSJeff Roberson kg->kg_runtime = (kg->kg_runtime / 5) * 4; 1146d322132cSJeff Roberson kg->kg_slptime = (kg->kg_slptime / 5) * 4; 1147d322132cSJeff Roberson } 1148d322132cSJeff Roberson 1149d322132cSJeff Roberson static void 1150d322132cSJeff Roberson sched_interact_fork(struct ksegrp *kg) 1151d322132cSJeff Roberson { 1152d322132cSJeff Roberson int ratio; 1153d322132cSJeff Roberson int sum; 1154d322132cSJeff Roberson 1155d322132cSJeff Roberson sum = kg->kg_runtime + kg->kg_slptime; 1156d322132cSJeff Roberson if (sum > SCHED_SLP_RUN_FORK) { 1157d322132cSJeff Roberson ratio = sum / SCHED_SLP_RUN_FORK; 1158d322132cSJeff Roberson kg->kg_runtime /= ratio; 1159d322132cSJeff Roberson kg->kg_slptime /= ratio; 11604b60e324SJeff Roberson } 11614b60e324SJeff Roberson } 11624b60e324SJeff Roberson 1163e1f89c22SJeff Roberson static int 1164e1f89c22SJeff Roberson sched_interact_score(struct ksegrp *kg) 1165e1f89c22SJeff Roberson { 1166210491d3SJeff Roberson int div; 1167e1f89c22SJeff Roberson 1168e1f89c22SJeff Roberson if (kg->kg_runtime > kg->kg_slptime) { 1169210491d3SJeff Roberson div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF); 1170210491d3SJeff Roberson return (SCHED_INTERACT_HALF + 1171210491d3SJeff Roberson (SCHED_INTERACT_HALF - (kg->kg_slptime / div))); 1172210491d3SJeff Roberson } if (kg->kg_slptime > kg->kg_runtime) { 1173210491d3SJeff Roberson div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF); 1174210491d3SJeff Roberson return (kg->kg_runtime / div); 1175e1f89c22SJeff Roberson } 1176e1f89c22SJeff Roberson 1177210491d3SJeff Roberson /* 1178210491d3SJeff Roberson * This can happen if slptime and runtime are 0. 1179210491d3SJeff Roberson */ 1180210491d3SJeff Roberson return (0); 1181e1f89c22SJeff Roberson 1182e1f89c22SJeff Roberson } 1183e1f89c22SJeff Roberson 118415dc847eSJeff Roberson /* 1185ed062c8dSJulian Elischer * Very early in the boot some setup of scheduler-specific 1186ed062c8dSJulian Elischer * parts of proc0 and of soem scheduler resources needs to be done. 1187ed062c8dSJulian Elischer * Called from: 1188ed062c8dSJulian Elischer * proc0_init() 1189ed062c8dSJulian Elischer */ 1190ed062c8dSJulian Elischer void 1191ed062c8dSJulian Elischer schedinit(void) 1192ed062c8dSJulian Elischer { 1193ed062c8dSJulian Elischer /* 1194ed062c8dSJulian Elischer * Set up the scheduler specific parts of proc0. 1195ed062c8dSJulian Elischer */ 1196ed062c8dSJulian Elischer proc0.p_sched = NULL; /* XXX */ 1197d39063f2SJulian Elischer ksegrp0.kg_sched = &kg_sched0; 1198d39063f2SJulian Elischer thread0.td_sched = &kse0; 1199ed062c8dSJulian Elischer kse0.ke_thread = &thread0; 1200ed062c8dSJulian Elischer kse0.ke_state = KES_THREAD; 1201ed062c8dSJulian Elischer kg_sched0.skg_concurrency = 1; 1202ed062c8dSJulian Elischer kg_sched0.skg_avail_opennings = 0; /* we are already running */ 1203ed062c8dSJulian Elischer } 1204ed062c8dSJulian Elischer 1205ed062c8dSJulian Elischer /* 120615dc847eSJeff Roberson * This is only somewhat accurate since given many processes of the same 120715dc847eSJeff Roberson * priority they will switch when their slices run out, which will be 120815dc847eSJeff Roberson * at most SCHED_SLICE_MAX. 120915dc847eSJeff Roberson */ 121035e6168fSJeff Roberson int 121135e6168fSJeff Roberson sched_rr_interval(void) 121235e6168fSJeff Roberson { 121335e6168fSJeff Roberson return (SCHED_SLICE_MAX); 121435e6168fSJeff Roberson } 121535e6168fSJeff Roberson 121622bf7d9aSJeff Roberson static void 121735e6168fSJeff Roberson sched_pctcpu_update(struct kse *ke) 121835e6168fSJeff Roberson { 121935e6168fSJeff Roberson /* 122035e6168fSJeff Roberson * Adjust counters and watermark for pctcpu calc. 1221210491d3SJeff Roberson */ 122281de51bfSJeff Roberson if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) { 1223210491d3SJeff Roberson /* 122481de51bfSJeff Roberson * Shift the tick count out so that the divide doesn't 122581de51bfSJeff Roberson * round away our results. 122665c8760dSJeff Roberson */ 122765c8760dSJeff Roberson ke->ke_ticks <<= 10; 122881de51bfSJeff Roberson ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) * 122935e6168fSJeff Roberson SCHED_CPU_TICKS; 123065c8760dSJeff Roberson ke->ke_ticks >>= 10; 123181de51bfSJeff Roberson } else 123281de51bfSJeff Roberson ke->ke_ticks = 0; 123335e6168fSJeff Roberson ke->ke_ltick = ticks; 123435e6168fSJeff Roberson ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS; 123535e6168fSJeff Roberson } 123635e6168fSJeff Roberson 123735e6168fSJeff Roberson void 1238f5c157d9SJohn Baldwin sched_thread_priority(struct thread *td, u_char prio) 123935e6168fSJeff Roberson { 12403f741ca1SJeff Roberson struct kse *ke; 124135e6168fSJeff Roberson 124281d47d3fSJeff Roberson CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)", 124381d47d3fSJeff Roberson td, td->td_proc->p_comm, td->td_priority, prio, curthread, 124481d47d3fSJeff Roberson curthread->td_proc->p_comm); 12453f741ca1SJeff Roberson ke = td->td_kse; 124635e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 1247f5c157d9SJohn Baldwin if (td->td_priority == prio) 1248f5c157d9SJohn Baldwin return; 124935e6168fSJeff Roberson if (TD_ON_RUNQ(td)) { 12503f741ca1SJeff Roberson /* 12513f741ca1SJeff Roberson * If the priority has been elevated due to priority 12523f741ca1SJeff Roberson * propagation, we may have to move ourselves to a new 12533f741ca1SJeff Roberson * queue. We still call adjustrunqueue below in case kse 12543f741ca1SJeff Roberson * needs to fix things up. 12553f741ca1SJeff Roberson */ 12568ffb8f55SJeff Roberson if (prio < td->td_priority && ke->ke_runq != NULL && 1257769a3635SJeff Roberson (ke->ke_flags & KEF_ASSIGNED) == 0 && 125822bf7d9aSJeff Roberson ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) { 12593f741ca1SJeff Roberson runq_remove(ke->ke_runq, ke); 12603f741ca1SJeff Roberson ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr; 1261c20c691bSJulian Elischer runq_add(ke->ke_runq, ke, 0); 126235e6168fSJeff Roberson } 1263f2b74cbfSJeff Roberson /* 1264f2b74cbfSJeff Roberson * Hold this kse on this cpu so that sched_prio() doesn't 1265f2b74cbfSJeff Roberson * cause excessive migration. We only want migration to 1266f2b74cbfSJeff Roberson * happen as the result of a wakeup. 1267f2b74cbfSJeff Roberson */ 1268f2b74cbfSJeff Roberson ke->ke_flags |= KEF_HOLD; 12693f741ca1SJeff Roberson adjustrunqueue(td, prio); 1270598b368dSJeff Roberson ke->ke_flags &= ~KEF_HOLD; 12713f741ca1SJeff Roberson } else 12723f741ca1SJeff Roberson td->td_priority = prio; 127335e6168fSJeff Roberson } 127435e6168fSJeff Roberson 1275f5c157d9SJohn Baldwin /* 1276f5c157d9SJohn Baldwin * Update a thread's priority when it is lent another thread's 1277f5c157d9SJohn Baldwin * priority. 1278f5c157d9SJohn Baldwin */ 1279f5c157d9SJohn Baldwin void 1280f5c157d9SJohn Baldwin sched_lend_prio(struct thread *td, u_char prio) 1281f5c157d9SJohn Baldwin { 1282f5c157d9SJohn Baldwin 1283f5c157d9SJohn Baldwin td->td_flags |= TDF_BORROWING; 1284f5c157d9SJohn Baldwin sched_thread_priority(td, prio); 1285f5c157d9SJohn Baldwin } 1286f5c157d9SJohn Baldwin 1287f5c157d9SJohn Baldwin /* 1288f5c157d9SJohn Baldwin * Restore a thread's priority when priority propagation is 1289f5c157d9SJohn Baldwin * over. The prio argument is the minimum priority the thread 1290f5c157d9SJohn Baldwin * needs to have to satisfy other possible priority lending 1291f5c157d9SJohn Baldwin * requests. If the thread's regular priority is less 1292f5c157d9SJohn Baldwin * important than prio, the thread will keep a priority boost 1293f5c157d9SJohn Baldwin * of prio. 1294f5c157d9SJohn Baldwin */ 1295f5c157d9SJohn Baldwin void 1296f5c157d9SJohn Baldwin sched_unlend_prio(struct thread *td, u_char prio) 1297f5c157d9SJohn Baldwin { 1298f5c157d9SJohn Baldwin u_char base_pri; 1299f5c157d9SJohn Baldwin 1300f5c157d9SJohn Baldwin if (td->td_base_pri >= PRI_MIN_TIMESHARE && 1301f5c157d9SJohn Baldwin td->td_base_pri <= PRI_MAX_TIMESHARE) 1302f5c157d9SJohn Baldwin base_pri = td->td_ksegrp->kg_user_pri; 1303f5c157d9SJohn Baldwin else 1304f5c157d9SJohn Baldwin base_pri = td->td_base_pri; 1305f5c157d9SJohn Baldwin if (prio >= base_pri) { 1306f5c157d9SJohn Baldwin td->td_flags &= ~TDF_BORROWING; 1307f5c157d9SJohn Baldwin sched_thread_priority(td, base_pri); 1308f5c157d9SJohn Baldwin } else 1309f5c157d9SJohn Baldwin sched_lend_prio(td, prio); 1310f5c157d9SJohn Baldwin } 1311f5c157d9SJohn Baldwin 1312f5c157d9SJohn Baldwin void 1313f5c157d9SJohn Baldwin sched_prio(struct thread *td, u_char prio) 1314f5c157d9SJohn Baldwin { 1315f5c157d9SJohn Baldwin u_char oldprio; 1316f5c157d9SJohn Baldwin 1317f5c157d9SJohn Baldwin /* First, update the base priority. */ 1318f5c157d9SJohn Baldwin td->td_base_pri = prio; 1319f5c157d9SJohn Baldwin 1320f5c157d9SJohn Baldwin /* 132150aaa791SJohn Baldwin * If the thread is borrowing another thread's priority, don't 1322f5c157d9SJohn Baldwin * ever lower the priority. 1323f5c157d9SJohn Baldwin */ 1324f5c157d9SJohn Baldwin if (td->td_flags & TDF_BORROWING && td->td_priority < prio) 1325f5c157d9SJohn Baldwin return; 1326f5c157d9SJohn Baldwin 1327f5c157d9SJohn Baldwin /* Change the real priority. */ 1328f5c157d9SJohn Baldwin oldprio = td->td_priority; 1329f5c157d9SJohn Baldwin sched_thread_priority(td, prio); 1330f5c157d9SJohn Baldwin 1331f5c157d9SJohn Baldwin /* 1332f5c157d9SJohn Baldwin * If the thread is on a turnstile, then let the turnstile update 1333f5c157d9SJohn Baldwin * its state. 1334f5c157d9SJohn Baldwin */ 1335f5c157d9SJohn Baldwin if (TD_ON_LOCK(td) && oldprio != prio) 1336f5c157d9SJohn Baldwin turnstile_adjust(td, oldprio); 1337f5c157d9SJohn Baldwin } 1338f5c157d9SJohn Baldwin 133935e6168fSJeff Roberson void 13403389af30SJulian Elischer sched_switch(struct thread *td, struct thread *newtd, int flags) 134135e6168fSJeff Roberson { 1342598b368dSJeff Roberson struct kseq *ksq; 134335e6168fSJeff Roberson struct kse *ke; 134435e6168fSJeff Roberson 134535e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 134635e6168fSJeff Roberson 134735e6168fSJeff Roberson ke = td->td_kse; 1348598b368dSJeff Roberson ksq = KSEQ_SELF(); 134935e6168fSJeff Roberson 1350060563ecSJulian Elischer td->td_lastcpu = td->td_oncpu; 1351060563ecSJulian Elischer td->td_oncpu = NOCPU; 135252eb8464SJohn Baldwin td->td_flags &= ~TDF_NEEDRESCHED; 135377918643SStephan Uphoff td->td_owepreempt = 0; 135435e6168fSJeff Roberson 1355b11fdad0SJeff Roberson /* 1356b11fdad0SJeff Roberson * If the KSE has been assigned it may be in the process of switching 1357b11fdad0SJeff Roberson * to the new cpu. This is the case in sched_bind(). 1358b11fdad0SJeff Roberson */ 13592454aaf5SJeff Roberson if (td == PCPU_GET(idlethread)) { 1360bf0acc27SJohn Baldwin TD_SET_CAN_RUN(td); 1361598b368dSJeff Roberson } else if ((ke->ke_flags & KEF_ASSIGNED) == 0) { 1362ed062c8dSJulian Elischer /* We are ending our run so make our slot available again */ 1363d39063f2SJulian Elischer SLOT_RELEASE(td->td_ksegrp); 1364598b368dSJeff Roberson kseq_load_rem(ksq, ke); 1365ed062c8dSJulian Elischer if (TD_IS_RUNNING(td)) { 1366f2b74cbfSJeff Roberson /* 1367ed062c8dSJulian Elischer * Don't allow the thread to migrate 1368ed062c8dSJulian Elischer * from a preemption. 1369f2b74cbfSJeff Roberson */ 1370f2b74cbfSJeff Roberson ke->ke_flags |= KEF_HOLD; 1371598b368dSJeff Roberson setrunqueue(td, (flags & SW_PREEMPT) ? 1372598b368dSJeff Roberson SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED : 1373598b368dSJeff Roberson SRQ_OURSELF|SRQ_YIELDING); 1374598b368dSJeff Roberson ke->ke_flags &= ~KEF_HOLD; 1375598b368dSJeff Roberson } else if ((td->td_proc->p_flag & P_HADTHREADS) && 1376598b368dSJeff Roberson (newtd == NULL || newtd->td_ksegrp != td->td_ksegrp)) 137735e6168fSJeff Roberson /* 1378ed062c8dSJulian Elischer * We will not be on the run queue. 1379ed062c8dSJulian Elischer * So we must be sleeping or similar. 1380c20c691bSJulian Elischer * Don't use the slot if we will need it 1381c20c691bSJulian Elischer * for newtd. 138235e6168fSJeff Roberson */ 1383ed062c8dSJulian Elischer slot_fill(td->td_ksegrp); 1384ed062c8dSJulian Elischer } 1385d39063f2SJulian Elischer if (newtd != NULL) { 1386c20c691bSJulian Elischer /* 1387c20c691bSJulian Elischer * If we bring in a thread, 1388c20c691bSJulian Elischer * then account for it as if it had been added to the 1389c20c691bSJulian Elischer * run queue and then chosen. 1390c20c691bSJulian Elischer */ 1391c5c3fb33SJulian Elischer newtd->td_kse->ke_flags |= KEF_DIDRUN; 1392598b368dSJeff Roberson newtd->td_kse->ke_runq = ksq->ksq_curr; 1393d39063f2SJulian Elischer SLOT_USE(newtd->td_ksegrp); 1394c20c691bSJulian Elischer TD_SET_RUNNING(newtd); 1395bf0acc27SJohn Baldwin kseq_load_add(KSEQ_SELF(), newtd->td_kse); 1396d39063f2SJulian Elischer } else 13972454aaf5SJeff Roberson newtd = choosethread(); 1398ebccf1e3SJoseph Koshy if (td != newtd) { 1399ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS 1400ebccf1e3SJoseph Koshy if (PMC_PROC_IS_USING_PMCS(td->td_proc)) 1401ebccf1e3SJoseph Koshy PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT); 1402ebccf1e3SJoseph Koshy #endif 1403ae53b483SJeff Roberson cpu_switch(td, newtd); 1404ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS 1405ebccf1e3SJoseph Koshy if (PMC_PROC_IS_USING_PMCS(td->td_proc)) 1406ebccf1e3SJoseph Koshy PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN); 1407ebccf1e3SJoseph Koshy #endif 1408ebccf1e3SJoseph Koshy } 1409ebccf1e3SJoseph Koshy 1410ae53b483SJeff Roberson sched_lock.mtx_lock = (uintptr_t)td; 141135e6168fSJeff Roberson 1412060563ecSJulian Elischer td->td_oncpu = PCPU_GET(cpuid); 141335e6168fSJeff Roberson } 141435e6168fSJeff Roberson 141535e6168fSJeff Roberson void 1416fa885116SJulian Elischer sched_nice(struct proc *p, int nice) 141735e6168fSJeff Roberson { 1418fa885116SJulian Elischer struct ksegrp *kg; 141915dc847eSJeff Roberson struct kse *ke; 142035e6168fSJeff Roberson struct thread *td; 142115dc847eSJeff Roberson struct kseq *kseq; 142235e6168fSJeff Roberson 1423fa885116SJulian Elischer PROC_LOCK_ASSERT(p, MA_OWNED); 14240b5318c8SJohn Baldwin mtx_assert(&sched_lock, MA_OWNED); 142515dc847eSJeff Roberson /* 142615dc847eSJeff Roberson * We need to adjust the nice counts for running KSEs. 142715dc847eSJeff Roberson */ 1428fa885116SJulian Elischer FOREACH_KSEGRP_IN_PROC(p, kg) { 1429fa885116SJulian Elischer if (kg->kg_pri_class == PRI_TIMESHARE) { 1430ed062c8dSJulian Elischer FOREACH_THREAD_IN_GROUP(kg, td) { 1431ed062c8dSJulian Elischer ke = td->td_kse; 1432d07ac847SJeff Roberson if (ke->ke_runq == NULL) 143315dc847eSJeff Roberson continue; 143415dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 1435fa885116SJulian Elischer kseq_nice_rem(kseq, p->p_nice); 143615dc847eSJeff Roberson kseq_nice_add(kseq, nice); 143715dc847eSJeff Roberson } 1438fa885116SJulian Elischer } 1439fa885116SJulian Elischer } 1440fa885116SJulian Elischer p->p_nice = nice; 1441fa885116SJulian Elischer FOREACH_KSEGRP_IN_PROC(p, kg) { 144235e6168fSJeff Roberson sched_priority(kg); 144315dc847eSJeff Roberson FOREACH_THREAD_IN_GROUP(kg, td) 14444a338afdSJulian Elischer td->td_flags |= TDF_NEEDRESCHED; 144535e6168fSJeff Roberson } 1446fa885116SJulian Elischer } 144735e6168fSJeff Roberson 144835e6168fSJeff Roberson void 144944f3b092SJohn Baldwin sched_sleep(struct thread *td) 145035e6168fSJeff Roberson { 145135e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 145235e6168fSJeff Roberson 145335e6168fSJeff Roberson td->td_slptime = ticks; 145435e6168fSJeff Roberson } 145535e6168fSJeff Roberson 145635e6168fSJeff Roberson void 145735e6168fSJeff Roberson sched_wakeup(struct thread *td) 145835e6168fSJeff Roberson { 145935e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 146035e6168fSJeff Roberson 146135e6168fSJeff Roberson /* 146235e6168fSJeff Roberson * Let the kseg know how long we slept for. This is because process 146335e6168fSJeff Roberson * interactivity behavior is modeled in the kseg. 146435e6168fSJeff Roberson */ 146535e6168fSJeff Roberson if (td->td_slptime) { 1466f1e8dc4aSJeff Roberson struct ksegrp *kg; 146715dc847eSJeff Roberson int hzticks; 1468f1e8dc4aSJeff Roberson 1469f1e8dc4aSJeff Roberson kg = td->td_ksegrp; 1470d322132cSJeff Roberson hzticks = (ticks - td->td_slptime) << 10; 1471d322132cSJeff Roberson if (hzticks >= SCHED_SLP_RUN_MAX) { 1472d322132cSJeff Roberson kg->kg_slptime = SCHED_SLP_RUN_MAX; 1473d322132cSJeff Roberson kg->kg_runtime = 1; 1474d322132cSJeff Roberson } else { 1475d322132cSJeff Roberson kg->kg_slptime += hzticks; 14764b60e324SJeff Roberson sched_interact_update(kg); 1477d322132cSJeff Roberson } 1478f1e8dc4aSJeff Roberson sched_priority(kg); 14794b60e324SJeff Roberson sched_slice(td->td_kse); 148035e6168fSJeff Roberson td->td_slptime = 0; 1481f1e8dc4aSJeff Roberson } 14822630e4c9SJulian Elischer setrunqueue(td, SRQ_BORING); 148335e6168fSJeff Roberson } 148435e6168fSJeff Roberson 148535e6168fSJeff Roberson /* 148635e6168fSJeff Roberson * Penalize the parent for creating a new child and initialize the child's 148735e6168fSJeff Roberson * priority. 148835e6168fSJeff Roberson */ 148935e6168fSJeff Roberson void 1490ed062c8dSJulian Elischer sched_fork(struct thread *td, struct thread *childtd) 149135e6168fSJeff Roberson { 149235e6168fSJeff Roberson 149335e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 149435e6168fSJeff Roberson 1495ed062c8dSJulian Elischer sched_fork_ksegrp(td, childtd->td_ksegrp); 1496ed062c8dSJulian Elischer sched_fork_thread(td, childtd); 149715dc847eSJeff Roberson } 149815dc847eSJeff Roberson 149915dc847eSJeff Roberson void 150055d44f79SJulian Elischer sched_fork_ksegrp(struct thread *td, struct ksegrp *child) 150115dc847eSJeff Roberson { 150255d44f79SJulian Elischer struct ksegrp *kg = td->td_ksegrp; 1503ed062c8dSJulian Elischer mtx_assert(&sched_lock, MA_OWNED); 1504210491d3SJeff Roberson 1505d322132cSJeff Roberson child->kg_slptime = kg->kg_slptime; 1506d322132cSJeff Roberson child->kg_runtime = kg->kg_runtime; 1507d322132cSJeff Roberson child->kg_user_pri = kg->kg_user_pri; 1508d322132cSJeff Roberson sched_interact_fork(child); 15094b60e324SJeff Roberson kg->kg_runtime += tickincr << 10; 15104b60e324SJeff Roberson sched_interact_update(kg); 1511c9f25d8fSJeff Roberson } 1512c9f25d8fSJeff Roberson 151315dc847eSJeff Roberson void 151415dc847eSJeff Roberson sched_fork_thread(struct thread *td, struct thread *child) 151515dc847eSJeff Roberson { 1516ed062c8dSJulian Elischer struct kse *ke; 1517ed062c8dSJulian Elischer struct kse *ke2; 1518ed062c8dSJulian Elischer 1519ed062c8dSJulian Elischer sched_newthread(child); 1520ed062c8dSJulian Elischer ke = td->td_kse; 1521ed062c8dSJulian Elischer ke2 = child->td_kse; 1522ed062c8dSJulian Elischer ke2->ke_slice = 1; /* Attempt to quickly learn interactivity. */ 1523ed062c8dSJulian Elischer ke2->ke_cpu = ke->ke_cpu; 1524ed062c8dSJulian Elischer ke2->ke_runq = NULL; 1525ed062c8dSJulian Elischer 1526ed062c8dSJulian Elischer /* Grab our parents cpu estimation information. */ 1527ed062c8dSJulian Elischer ke2->ke_ticks = ke->ke_ticks; 1528ed062c8dSJulian Elischer ke2->ke_ltick = ke->ke_ltick; 1529ed062c8dSJulian Elischer ke2->ke_ftick = ke->ke_ftick; 153015dc847eSJeff Roberson } 153115dc847eSJeff Roberson 153215dc847eSJeff Roberson void 153315dc847eSJeff Roberson sched_class(struct ksegrp *kg, int class) 153415dc847eSJeff Roberson { 153515dc847eSJeff Roberson struct kseq *kseq; 153615dc847eSJeff Roberson struct kse *ke; 1537ed062c8dSJulian Elischer struct thread *td; 1538ef1134c9SJeff Roberson int nclass; 1539ef1134c9SJeff Roberson int oclass; 154015dc847eSJeff Roberson 15412056d0a1SJohn Baldwin mtx_assert(&sched_lock, MA_OWNED); 154215dc847eSJeff Roberson if (kg->kg_pri_class == class) 154315dc847eSJeff Roberson return; 154415dc847eSJeff Roberson 1545ef1134c9SJeff Roberson nclass = PRI_BASE(class); 1546ef1134c9SJeff Roberson oclass = PRI_BASE(kg->kg_pri_class); 1547ed062c8dSJulian Elischer FOREACH_THREAD_IN_GROUP(kg, td) { 1548ed062c8dSJulian Elischer ke = td->td_kse; 154942a29039SJeff Roberson if ((ke->ke_state != KES_ONRUNQ && 155042a29039SJeff Roberson ke->ke_state != KES_THREAD) || ke->ke_runq == NULL) 155115dc847eSJeff Roberson continue; 155215dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 155315dc847eSJeff Roberson 1554ef1134c9SJeff Roberson #ifdef SMP 1555155b9987SJeff Roberson /* 1556155b9987SJeff Roberson * On SMP if we're on the RUNQ we must adjust the transferable 1557155b9987SJeff Roberson * count because could be changing to or from an interrupt 1558155b9987SJeff Roberson * class. 1559155b9987SJeff Roberson */ 1560155b9987SJeff Roberson if (ke->ke_state == KES_ONRUNQ) { 1561598b368dSJeff Roberson if (KSE_CAN_MIGRATE(ke)) { 156280f86c9fSJeff Roberson kseq->ksq_transferable--; 156380f86c9fSJeff Roberson kseq->ksq_group->ksg_transferable--; 156480f86c9fSJeff Roberson } 1565598b368dSJeff Roberson if (KSE_CAN_MIGRATE(ke)) { 156680f86c9fSJeff Roberson kseq->ksq_transferable++; 156780f86c9fSJeff Roberson kseq->ksq_group->ksg_transferable++; 156880f86c9fSJeff Roberson } 1569155b9987SJeff Roberson } 1570ef1134c9SJeff Roberson #endif 1571155b9987SJeff Roberson if (oclass == PRI_TIMESHARE) { 1572ef1134c9SJeff Roberson kseq->ksq_load_timeshare--; 1573fa885116SJulian Elischer kseq_nice_rem(kseq, kg->kg_proc->p_nice); 1574155b9987SJeff Roberson } 1575155b9987SJeff Roberson if (nclass == PRI_TIMESHARE) { 1576155b9987SJeff Roberson kseq->ksq_load_timeshare++; 1577fa885116SJulian Elischer kseq_nice_add(kseq, kg->kg_proc->p_nice); 157815dc847eSJeff Roberson } 1579155b9987SJeff Roberson } 158015dc847eSJeff Roberson 158115dc847eSJeff Roberson kg->kg_pri_class = class; 158235e6168fSJeff Roberson } 158335e6168fSJeff Roberson 158435e6168fSJeff Roberson /* 158535e6168fSJeff Roberson * Return some of the child's priority and interactivity to the parent. 158635e6168fSJeff Roberson */ 158735e6168fSJeff Roberson void 1588ed062c8dSJulian Elischer sched_exit(struct proc *p, struct thread *childtd) 158935e6168fSJeff Roberson { 159035e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 1591ed062c8dSJulian Elischer sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), childtd); 159281d47d3fSJeff Roberson sched_exit_thread(NULL, childtd); 1593141ad61cSJeff Roberson } 1594141ad61cSJeff Roberson 1595141ad61cSJeff Roberson void 159655d44f79SJulian Elischer sched_exit_ksegrp(struct ksegrp *kg, struct thread *td) 1597141ad61cSJeff Roberson { 159855d44f79SJulian Elischer /* kg->kg_slptime += td->td_ksegrp->kg_slptime; */ 159955d44f79SJulian Elischer kg->kg_runtime += td->td_ksegrp->kg_runtime; 16004b60e324SJeff Roberson sched_interact_update(kg); 1601141ad61cSJeff Roberson } 1602141ad61cSJeff Roberson 1603141ad61cSJeff Roberson void 1604ed062c8dSJulian Elischer sched_exit_thread(struct thread *td, struct thread *childtd) 1605141ad61cSJeff Roberson { 160681d47d3fSJeff Roberson CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d", 160781d47d3fSJeff Roberson childtd, childtd->td_proc->p_comm, childtd->td_priority); 1608ed062c8dSJulian Elischer kseq_load_rem(KSEQ_CPU(childtd->td_kse->ke_cpu), childtd->td_kse); 160935e6168fSJeff Roberson } 161035e6168fSJeff Roberson 161135e6168fSJeff Roberson void 16127cf90fb3SJeff Roberson sched_clock(struct thread *td) 161335e6168fSJeff Roberson { 161435e6168fSJeff Roberson struct kseq *kseq; 16150a016a05SJeff Roberson struct ksegrp *kg; 16167cf90fb3SJeff Roberson struct kse *ke; 161735e6168fSJeff Roberson 1618dc03363dSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 16192454aaf5SJeff Roberson kseq = KSEQ_SELF(); 1620dc03363dSJeff Roberson #ifdef SMP 1621598b368dSJeff Roberson if (ticks >= bal_tick) 1622dc03363dSJeff Roberson sched_balance(); 1623598b368dSJeff Roberson if (ticks >= gbal_tick && balance_groups) 1624dc03363dSJeff Roberson sched_balance_groups(); 16252454aaf5SJeff Roberson /* 16262454aaf5SJeff Roberson * We could have been assigned a non real-time thread without an 16272454aaf5SJeff Roberson * IPI. 16282454aaf5SJeff Roberson */ 16292454aaf5SJeff Roberson if (kseq->ksq_assigned) 16302454aaf5SJeff Roberson kseq_assign(kseq); /* Potentially sets NEEDRESCHED */ 1631dc03363dSJeff Roberson #endif 163215dc847eSJeff Roberson /* 163315dc847eSJeff Roberson * sched_setup() apparently happens prior to stathz being set. We 163415dc847eSJeff Roberson * need to resolve the timers earlier in the boot so we can avoid 163515dc847eSJeff Roberson * calculating this here. 163615dc847eSJeff Roberson */ 163715dc847eSJeff Roberson if (realstathz == 0) { 163815dc847eSJeff Roberson realstathz = stathz ? stathz : hz; 163915dc847eSJeff Roberson tickincr = hz / realstathz; 164015dc847eSJeff Roberson /* 164115dc847eSJeff Roberson * XXX This does not work for values of stathz that are much 164215dc847eSJeff Roberson * larger than hz. 164315dc847eSJeff Roberson */ 164415dc847eSJeff Roberson if (tickincr == 0) 164515dc847eSJeff Roberson tickincr = 1; 164615dc847eSJeff Roberson } 164735e6168fSJeff Roberson 16487cf90fb3SJeff Roberson ke = td->td_kse; 164915dc847eSJeff Roberson kg = ke->ke_ksegrp; 165035e6168fSJeff Roberson 16510a016a05SJeff Roberson /* Adjust ticks for pctcpu */ 165265c8760dSJeff Roberson ke->ke_ticks++; 1653d465fb95SJeff Roberson ke->ke_ltick = ticks; 1654a8949de2SJeff Roberson 1655d465fb95SJeff Roberson /* Go up to one second beyond our max and then trim back down */ 1656d465fb95SJeff Roberson if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick) 1657d465fb95SJeff Roberson sched_pctcpu_update(ke); 1658d465fb95SJeff Roberson 165943fdafb1SJulian Elischer if (td->td_flags & TDF_IDLETD) 166035e6168fSJeff Roberson return; 16613f741ca1SJeff Roberson /* 1662a8949de2SJeff Roberson * We only do slicing code for TIMESHARE ksegrps. 1663a8949de2SJeff Roberson */ 1664a8949de2SJeff Roberson if (kg->kg_pri_class != PRI_TIMESHARE) 1665a8949de2SJeff Roberson return; 1666a8949de2SJeff Roberson /* 166715dc847eSJeff Roberson * We used a tick charge it to the ksegrp so that we can compute our 166815dc847eSJeff Roberson * interactivity. 166915dc847eSJeff Roberson */ 167015dc847eSJeff Roberson kg->kg_runtime += tickincr << 10; 16714b60e324SJeff Roberson sched_interact_update(kg); 1672407b0157SJeff Roberson 167335e6168fSJeff Roberson /* 167435e6168fSJeff Roberson * We used up one time slice. 167535e6168fSJeff Roberson */ 1676093c05e3SJeff Roberson if (--ke->ke_slice > 0) 167715dc847eSJeff Roberson return; 167835e6168fSJeff Roberson /* 167915dc847eSJeff Roberson * We're out of time, recompute priorities and requeue. 168035e6168fSJeff Roberson */ 1681155b9987SJeff Roberson kseq_load_rem(kseq, ke); 1682e1f89c22SJeff Roberson sched_priority(kg); 168315dc847eSJeff Roberson sched_slice(ke); 168415dc847eSJeff Roberson if (SCHED_CURR(kg, ke)) 168515dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 168615dc847eSJeff Roberson else 168715dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 1688155b9987SJeff Roberson kseq_load_add(kseq, ke); 16894a338afdSJulian Elischer td->td_flags |= TDF_NEEDRESCHED; 169035e6168fSJeff Roberson } 169135e6168fSJeff Roberson 169235e6168fSJeff Roberson int 169335e6168fSJeff Roberson sched_runnable(void) 169435e6168fSJeff Roberson { 169535e6168fSJeff Roberson struct kseq *kseq; 1696b90816f1SJeff Roberson int load; 169735e6168fSJeff Roberson 1698b90816f1SJeff Roberson load = 1; 1699b90816f1SJeff Roberson 17000a016a05SJeff Roberson kseq = KSEQ_SELF(); 170122bf7d9aSJeff Roberson #ifdef SMP 170246f8b265SJeff Roberson if (kseq->ksq_assigned) { 170346f8b265SJeff Roberson mtx_lock_spin(&sched_lock); 170422bf7d9aSJeff Roberson kseq_assign(kseq); 170546f8b265SJeff Roberson mtx_unlock_spin(&sched_lock); 170646f8b265SJeff Roberson } 170722bf7d9aSJeff Roberson #endif 17083f741ca1SJeff Roberson if ((curthread->td_flags & TDF_IDLETD) != 0) { 17093f741ca1SJeff Roberson if (kseq->ksq_load > 0) 17103f741ca1SJeff Roberson goto out; 17113f741ca1SJeff Roberson } else 17123f741ca1SJeff Roberson if (kseq->ksq_load - 1 > 0) 1713b90816f1SJeff Roberson goto out; 1714b90816f1SJeff Roberson load = 0; 1715b90816f1SJeff Roberson out: 1716b90816f1SJeff Roberson return (load); 171735e6168fSJeff Roberson } 171835e6168fSJeff Roberson 171935e6168fSJeff Roberson void 172035e6168fSJeff Roberson sched_userret(struct thread *td) 172135e6168fSJeff Roberson { 172235e6168fSJeff Roberson struct ksegrp *kg; 172335e6168fSJeff Roberson 1724f5c157d9SJohn Baldwin KASSERT((td->td_flags & TDF_BORROWING) == 0, 1725f5c157d9SJohn Baldwin ("thread with borrowed priority returning to userland")); 172635e6168fSJeff Roberson kg = td->td_ksegrp; 1727f5c157d9SJohn Baldwin if (td->td_priority != kg->kg_user_pri) { 172835e6168fSJeff Roberson mtx_lock_spin(&sched_lock); 172935e6168fSJeff Roberson td->td_priority = kg->kg_user_pri; 1730f5c157d9SJohn Baldwin td->td_base_pri = kg->kg_user_pri; 173135e6168fSJeff Roberson mtx_unlock_spin(&sched_lock); 173235e6168fSJeff Roberson } 173335e6168fSJeff Roberson } 173435e6168fSJeff Roberson 1735c9f25d8fSJeff Roberson struct kse * 1736c9f25d8fSJeff Roberson sched_choose(void) 1737c9f25d8fSJeff Roberson { 17380a016a05SJeff Roberson struct kseq *kseq; 1739c9f25d8fSJeff Roberson struct kse *ke; 174015dc847eSJeff Roberson 1741b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 174222bf7d9aSJeff Roberson kseq = KSEQ_SELF(); 174315dc847eSJeff Roberson #ifdef SMP 174480f86c9fSJeff Roberson restart: 174522bf7d9aSJeff Roberson if (kseq->ksq_assigned) 174622bf7d9aSJeff Roberson kseq_assign(kseq); 174715dc847eSJeff Roberson #endif 174822bf7d9aSJeff Roberson ke = kseq_choose(kseq); 174935e6168fSJeff Roberson if (ke) { 175022bf7d9aSJeff Roberson #ifdef SMP 175122bf7d9aSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE) 175280f86c9fSJeff Roberson if (kseq_idled(kseq) == 0) 175380f86c9fSJeff Roberson goto restart; 175422bf7d9aSJeff Roberson #endif 1755155b9987SJeff Roberson kseq_runq_rem(kseq, ke); 175635e6168fSJeff Roberson ke->ke_state = KES_THREAD; 175715dc847eSJeff Roberson return (ke); 175835e6168fSJeff Roberson } 1759c9f25d8fSJeff Roberson #ifdef SMP 176080f86c9fSJeff Roberson if (kseq_idled(kseq) == 0) 176180f86c9fSJeff Roberson goto restart; 1762c9f25d8fSJeff Roberson #endif 176315dc847eSJeff Roberson return (NULL); 176435e6168fSJeff Roberson } 176535e6168fSJeff Roberson 176635e6168fSJeff Roberson void 17672630e4c9SJulian Elischer sched_add(struct thread *td, int flags) 176835e6168fSJeff Roberson { 1769c9f25d8fSJeff Roberson struct kseq *kseq; 177015dc847eSJeff Roberson struct ksegrp *kg; 17717cf90fb3SJeff Roberson struct kse *ke; 1772598b368dSJeff Roberson int preemptive; 17732454aaf5SJeff Roberson int canmigrate; 177422bf7d9aSJeff Roberson int class; 1775c9f25d8fSJeff Roberson 177681d47d3fSJeff Roberson CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)", 177781d47d3fSJeff Roberson td, td->td_proc->p_comm, td->td_priority, curthread, 177881d47d3fSJeff Roberson curthread->td_proc->p_comm); 177922bf7d9aSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 17807cf90fb3SJeff Roberson ke = td->td_kse; 17817cf90fb3SJeff Roberson kg = td->td_ksegrp; 1782598b368dSJeff Roberson canmigrate = 1; 1783598b368dSJeff Roberson preemptive = !(flags & SRQ_YIELDING); 1784598b368dSJeff Roberson class = PRI_BASE(kg->kg_pri_class); 1785598b368dSJeff Roberson kseq = KSEQ_SELF(); 1786598b368dSJeff Roberson if ((ke->ke_flags & KEF_INTERNAL) == 0) 1787598b368dSJeff Roberson SLOT_USE(td->td_ksegrp); 1788598b368dSJeff Roberson ke->ke_flags &= ~KEF_INTERNAL; 1789598b368dSJeff Roberson #ifdef SMP 17902d59a44dSJeff Roberson if (ke->ke_flags & KEF_ASSIGNED) { 1791598b368dSJeff Roberson if (ke->ke_flags & KEF_REMOVED) 17922d59a44dSJeff Roberson ke->ke_flags &= ~KEF_REMOVED; 179322bf7d9aSJeff Roberson return; 17942d59a44dSJeff Roberson } 1795598b368dSJeff Roberson canmigrate = KSE_CAN_MIGRATE(ke); 1796598b368dSJeff Roberson #endif 17975d7ef00cSJeff Roberson KASSERT(ke->ke_state != KES_ONRUNQ, 17985d7ef00cSJeff Roberson ("sched_add: kse %p (%s) already in run queue", ke, 17995d7ef00cSJeff Roberson ke->ke_proc->p_comm)); 18005d7ef00cSJeff Roberson KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 18015d7ef00cSJeff Roberson ("sched_add: process swapped out")); 18029bca28a7SJeff Roberson KASSERT(ke->ke_runq == NULL, 18039bca28a7SJeff Roberson ("sched_add: KSE %p is still assigned to a run queue", ke)); 180422bf7d9aSJeff Roberson switch (class) { 1805a8949de2SJeff Roberson case PRI_ITHD: 1806a8949de2SJeff Roberson case PRI_REALTIME: 180715dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 180815dc847eSJeff Roberson ke->ke_slice = SCHED_SLICE_MAX; 1809598b368dSJeff Roberson if (canmigrate) 18107cd650a9SJeff Roberson ke->ke_cpu = PCPU_GET(cpuid); 1811a8949de2SJeff Roberson break; 1812a8949de2SJeff Roberson case PRI_TIMESHARE: 181315dc847eSJeff Roberson if (SCHED_CURR(kg, ke)) 181415dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 181515dc847eSJeff Roberson else 181615dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 181715dc847eSJeff Roberson break; 181815dc847eSJeff Roberson case PRI_IDLE: 181915dc847eSJeff Roberson /* 182015dc847eSJeff Roberson * This is for priority prop. 182115dc847eSJeff Roberson */ 18223f741ca1SJeff Roberson if (ke->ke_thread->td_priority < PRI_MIN_IDLE) 182315dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 182415dc847eSJeff Roberson else 182515dc847eSJeff Roberson ke->ke_runq = &kseq->ksq_idle; 182615dc847eSJeff Roberson ke->ke_slice = SCHED_SLICE_MIN; 182715dc847eSJeff Roberson break; 182815dc847eSJeff Roberson default: 1829d322132cSJeff Roberson panic("Unknown pri class."); 1830a8949de2SJeff Roberson break; 1831a6ed4186SJeff Roberson } 183222bf7d9aSJeff Roberson #ifdef SMP 18332454aaf5SJeff Roberson /* 18342454aaf5SJeff Roberson * Don't migrate running threads here. Force the long term balancer 18352454aaf5SJeff Roberson * to do it. 18362454aaf5SJeff Roberson */ 1837f2b74cbfSJeff Roberson if (ke->ke_flags & KEF_HOLD) { 1838f2b74cbfSJeff Roberson ke->ke_flags &= ~KEF_HOLD; 18392454aaf5SJeff Roberson canmigrate = 0; 1840f2b74cbfSJeff Roberson } 18412454aaf5SJeff Roberson /* 18422454aaf5SJeff Roberson * If this thread is pinned or bound, notify the target cpu. 18432454aaf5SJeff Roberson */ 18442454aaf5SJeff Roberson if (!canmigrate && ke->ke_cpu != PCPU_GET(cpuid) ) { 184586e1c22aSJeff Roberson ke->ke_runq = NULL; 184680f86c9fSJeff Roberson kseq_notify(ke, ke->ke_cpu); 184780f86c9fSJeff Roberson return; 184880f86c9fSJeff Roberson } 184922bf7d9aSJeff Roberson /* 1850670c524fSJeff Roberson * If we had been idle, clear our bit in the group and potentially 1851670c524fSJeff Roberson * the global bitmap. If not, see if we should transfer this thread. 185222bf7d9aSJeff Roberson */ 185380f86c9fSJeff Roberson if ((class == PRI_TIMESHARE || class == PRI_REALTIME) && 185480f86c9fSJeff Roberson (kseq->ksq_group->ksg_idlemask & PCPU_GET(cpumask)) != 0) { 185580f86c9fSJeff Roberson /* 185680f86c9fSJeff Roberson * Check to see if our group is unidling, and if so, remove it 185780f86c9fSJeff Roberson * from the global idle mask. 185880f86c9fSJeff Roberson */ 185980f86c9fSJeff Roberson if (kseq->ksq_group->ksg_idlemask == 186080f86c9fSJeff Roberson kseq->ksq_group->ksg_cpumask) 186180f86c9fSJeff Roberson atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask); 186280f86c9fSJeff Roberson /* 186380f86c9fSJeff Roberson * Now remove ourselves from the group specific idle mask. 186480f86c9fSJeff Roberson */ 186580f86c9fSJeff Roberson kseq->ksq_group->ksg_idlemask &= ~PCPU_GET(cpumask); 1866598b368dSJeff Roberson } else if (canmigrate && kseq->ksq_load > 1 && class != PRI_ITHD) 1867670c524fSJeff Roberson if (kseq_transfer(kseq, ke, class)) 1868670c524fSJeff Roberson return; 18692454aaf5SJeff Roberson ke->ke_cpu = PCPU_GET(cpuid); 187022bf7d9aSJeff Roberson #endif 1871f2b74cbfSJeff Roberson if (td->td_priority < curthread->td_priority && 1872f2b74cbfSJeff Roberson ke->ke_runq == kseq->ksq_curr) 187322bf7d9aSJeff Roberson curthread->td_flags |= TDF_NEEDRESCHED; 187463fcce68SJohn Baldwin if (preemptive && maybe_preempt(td)) 18750c0b25aeSJohn Baldwin return; 187635e6168fSJeff Roberson ke->ke_state = KES_ONRUNQ; 187735e6168fSJeff Roberson 1878598b368dSJeff Roberson kseq_runq_add(kseq, ke, flags); 1879155b9987SJeff Roberson kseq_load_add(kseq, ke); 188035e6168fSJeff Roberson } 188135e6168fSJeff Roberson 188235e6168fSJeff Roberson void 18837cf90fb3SJeff Roberson sched_rem(struct thread *td) 188435e6168fSJeff Roberson { 188515dc847eSJeff Roberson struct kseq *kseq; 18867cf90fb3SJeff Roberson struct kse *ke; 18877cf90fb3SJeff Roberson 188881d47d3fSJeff Roberson CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)", 188981d47d3fSJeff Roberson td, td->td_proc->p_comm, td->td_priority, curthread, 189081d47d3fSJeff Roberson curthread->td_proc->p_comm); 1891598b368dSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 1892598b368dSJeff Roberson ke = td->td_kse; 18932d59a44dSJeff Roberson SLOT_RELEASE(td->td_ksegrp); 1894598b368dSJeff Roberson if (ke->ke_flags & KEF_ASSIGNED) { 18952d59a44dSJeff Roberson ke->ke_flags |= KEF_REMOVED; 189622bf7d9aSJeff Roberson return; 18972d59a44dSJeff Roberson } 1898c494ddc8SJeff Roberson KASSERT((ke->ke_state == KES_ONRUNQ), 1899c494ddc8SJeff Roberson ("sched_rem: KSE not on run queue")); 190035e6168fSJeff Roberson 19012d59a44dSJeff Roberson ke->ke_state = KES_THREAD; 190215dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 1903155b9987SJeff Roberson kseq_runq_rem(kseq, ke); 1904155b9987SJeff Roberson kseq_load_rem(kseq, ke); 190535e6168fSJeff Roberson } 190635e6168fSJeff Roberson 190735e6168fSJeff Roberson fixpt_t 19087cf90fb3SJeff Roberson sched_pctcpu(struct thread *td) 190935e6168fSJeff Roberson { 191035e6168fSJeff Roberson fixpt_t pctcpu; 19117cf90fb3SJeff Roberson struct kse *ke; 191235e6168fSJeff Roberson 191335e6168fSJeff Roberson pctcpu = 0; 19147cf90fb3SJeff Roberson ke = td->td_kse; 1915484288deSJeff Roberson if (ke == NULL) 1916484288deSJeff Roberson return (0); 191735e6168fSJeff Roberson 1918b90816f1SJeff Roberson mtx_lock_spin(&sched_lock); 191935e6168fSJeff Roberson if (ke->ke_ticks) { 192035e6168fSJeff Roberson int rtick; 192135e6168fSJeff Roberson 1922210491d3SJeff Roberson /* 1923210491d3SJeff Roberson * Don't update more frequently than twice a second. Allowing 1924210491d3SJeff Roberson * this causes the cpu usage to decay away too quickly due to 1925210491d3SJeff Roberson * rounding errors. 1926210491d3SJeff Roberson */ 19272e227f04SJeff Roberson if (ke->ke_ftick + SCHED_CPU_TICKS < ke->ke_ltick || 19282e227f04SJeff Roberson ke->ke_ltick < (ticks - (hz / 2))) 192935e6168fSJeff Roberson sched_pctcpu_update(ke); 193035e6168fSJeff Roberson /* How many rtick per second ? */ 1931210491d3SJeff Roberson rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS); 19327121cce5SScott Long pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT; 193335e6168fSJeff Roberson } 193435e6168fSJeff Roberson 193535e6168fSJeff Roberson ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick; 1936828e7683SJohn Baldwin mtx_unlock_spin(&sched_lock); 193735e6168fSJeff Roberson 193835e6168fSJeff Roberson return (pctcpu); 193935e6168fSJeff Roberson } 194035e6168fSJeff Roberson 19419bacd788SJeff Roberson void 19429bacd788SJeff Roberson sched_bind(struct thread *td, int cpu) 19439bacd788SJeff Roberson { 19449bacd788SJeff Roberson struct kse *ke; 19459bacd788SJeff Roberson 19469bacd788SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 19479bacd788SJeff Roberson ke = td->td_kse; 19489bacd788SJeff Roberson ke->ke_flags |= KEF_BOUND; 194980f86c9fSJeff Roberson #ifdef SMP 195080f86c9fSJeff Roberson if (PCPU_GET(cpuid) == cpu) 19519bacd788SJeff Roberson return; 19529bacd788SJeff Roberson /* sched_rem without the runq_remove */ 19539bacd788SJeff Roberson ke->ke_state = KES_THREAD; 1954155b9987SJeff Roberson kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke); 19559bacd788SJeff Roberson kseq_notify(ke, cpu); 19569bacd788SJeff Roberson /* When we return from mi_switch we'll be on the correct cpu. */ 1957279f949eSPoul-Henning Kamp mi_switch(SW_VOL, NULL); 19589bacd788SJeff Roberson #endif 19599bacd788SJeff Roberson } 19609bacd788SJeff Roberson 19619bacd788SJeff Roberson void 19629bacd788SJeff Roberson sched_unbind(struct thread *td) 19639bacd788SJeff Roberson { 19649bacd788SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 19659bacd788SJeff Roberson td->td_kse->ke_flags &= ~KEF_BOUND; 19669bacd788SJeff Roberson } 19679bacd788SJeff Roberson 196835e6168fSJeff Roberson int 1969ebccf1e3SJoseph Koshy sched_is_bound(struct thread *td) 1970ebccf1e3SJoseph Koshy { 1971ebccf1e3SJoseph Koshy mtx_assert(&sched_lock, MA_OWNED); 1972ebccf1e3SJoseph Koshy return (td->td_kse->ke_flags & KEF_BOUND); 1973ebccf1e3SJoseph Koshy } 1974ebccf1e3SJoseph Koshy 1975ebccf1e3SJoseph Koshy int 197633916c36SJeff Roberson sched_load(void) 197733916c36SJeff Roberson { 197833916c36SJeff Roberson #ifdef SMP 197933916c36SJeff Roberson int total; 198033916c36SJeff Roberson int i; 198133916c36SJeff Roberson 198233916c36SJeff Roberson total = 0; 198333916c36SJeff Roberson for (i = 0; i <= ksg_maxid; i++) 198433916c36SJeff Roberson total += KSEQ_GROUP(i)->ksg_load; 198533916c36SJeff Roberson return (total); 198633916c36SJeff Roberson #else 198733916c36SJeff Roberson return (KSEQ_SELF()->ksq_sysload); 198833916c36SJeff Roberson #endif 198933916c36SJeff Roberson } 199033916c36SJeff Roberson 199133916c36SJeff Roberson int 199235e6168fSJeff Roberson sched_sizeof_ksegrp(void) 199335e6168fSJeff Roberson { 199435e6168fSJeff Roberson return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 199535e6168fSJeff Roberson } 199635e6168fSJeff Roberson 199735e6168fSJeff Roberson int 199835e6168fSJeff Roberson sched_sizeof_proc(void) 199935e6168fSJeff Roberson { 200035e6168fSJeff Roberson return (sizeof(struct proc)); 200135e6168fSJeff Roberson } 200235e6168fSJeff Roberson 200335e6168fSJeff Roberson int 200435e6168fSJeff Roberson sched_sizeof_thread(void) 200535e6168fSJeff Roberson { 200635e6168fSJeff Roberson return (sizeof(struct thread) + sizeof(struct td_sched)); 200735e6168fSJeff Roberson } 2008ed062c8dSJulian Elischer #define KERN_SWITCH_INCLUDE 1 2009ed062c8dSJulian Elischer #include "kern/kern_switch.c" 2010