sched_m2.c revision 1.10.2.5
1 1.10.2.5 matt /* sched_m2.c,v 1.10.2.4 2008/01/09 01:56:14 matt Exp */ 2 1.10.2.2 matt 3 1.10.2.2 matt /* 4 1.10.2.5 matt * Copyright (c) 2007, 2008 Mindaugas Rasiukevicius <rmind at NetBSD org> 5 1.10.2.4 matt * All rights reserved. 6 1.10.2.2 matt * 7 1.10.2.2 matt * Redistribution and use in source and binary forms, with or without 8 1.10.2.2 matt * modification, are permitted provided that the following conditions 9 1.10.2.2 matt * are met: 10 1.10.2.2 matt * 1. Redistributions of source code must retain the above copyright 11 1.10.2.2 matt * notice, this list of conditions and the following disclaimer. 12 1.10.2.2 matt * 2. Redistributions in binary form must reproduce the above copyright 13 1.10.2.2 matt * notice, this list of conditions and the following disclaimer in the 14 1.10.2.2 matt * documentation and/or other materials provided with the distribution. 15 1.10.2.2 matt * 16 1.10.2.5 matt * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 1.10.2.5 matt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 1.10.2.5 matt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 1.10.2.5 matt * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 1.10.2.5 matt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 1.10.2.5 matt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 1.10.2.5 matt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 1.10.2.5 matt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 1.10.2.5 matt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 1.10.2.5 matt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 1.10.2.5 matt * SUCH DAMAGE. 27 1.10.2.2 matt */ 28 1.10.2.2 matt 29 1.10.2.2 matt /* 30 1.10.2.2 matt * TODO: 31 1.10.2.2 matt * - Implementation of fair share queue; 32 1.10.2.2 matt * - Support for NUMA; 33 1.10.2.2 matt */ 34 1.10.2.2 matt 35 1.10.2.2 matt #include <sys/cdefs.h> 36 1.10.2.5 matt __KERNEL_RCSID(0, "sched_m2.c,v 1.10.2.4 2008/01/09 01:56:14 matt Exp"); 37 1.10.2.2 matt 38 1.10.2.2 matt #include <sys/param.h> 39 1.10.2.2 matt 40 1.10.2.2 matt #include <sys/bitops.h> 41 1.10.2.2 matt #include <sys/cpu.h> 42 1.10.2.2 matt #include <sys/callout.h> 43 1.10.2.2 matt #include <sys/errno.h> 44 1.10.2.2 matt #include <sys/kernel.h> 45 1.10.2.2 matt #include <sys/kmem.h> 46 1.10.2.2 matt #include <sys/lwp.h> 47 1.10.2.2 matt #include <sys/mutex.h> 48 1.10.2.2 matt #include <sys/pool.h> 49 1.10.2.2 matt #include <sys/proc.h> 50 1.10.2.5 matt #include <sys/pset.h> 51 1.10.2.2 matt #include <sys/resource.h> 52 1.10.2.2 matt #include <sys/resourcevar.h> 53 1.10.2.2 matt #include <sys/sched.h> 54 1.10.2.2 matt #include <sys/syscallargs.h> 55 1.10.2.2 matt #include <sys/sysctl.h> 56 1.10.2.2 matt #include <sys/types.h> 57 1.10.2.2 matt 58 1.10.2.2 matt /* 59 1.10.2.2 matt * Priority related defintions. 60 1.10.2.2 matt */ 61 1.10.2.2 matt #define PRI_TS_COUNT (NPRI_USER) 62 1.10.2.2 matt #define PRI_RT_COUNT (PRI_COUNT - PRI_TS_COUNT) 63 1.10.2.2 matt #define PRI_HTS_RANGE (PRI_TS_COUNT / 10) 64 1.10.2.2 matt 65 1.10.2.3 matt #define PRI_HIGHEST_TS (MAXPRI_USER) 66 1.10.2.2 matt 67 1.10.2.2 matt const int schedppq = 1; 68 1.10.2.2 matt 69 1.10.2.2 matt /* 70 1.10.2.2 matt * Bits per map. 71 1.10.2.2 matt */ 72 1.10.2.2 matt #define BITMAP_BITS (32) 73 1.10.2.2 matt #define BITMAP_SHIFT (5) 74 1.10.2.3 matt #define BITMAP_MSB (0x80000000U) 75 1.10.2.2 matt #define BITMAP_MASK (BITMAP_BITS - 1) 76 1.10.2.2 matt 77 1.10.2.2 matt /* 78 1.10.2.2 matt * Time-slices and priorities. 79 1.10.2.2 matt */ 80 1.10.2.2 matt static u_int min_ts; /* Minimal time-slice */ 81 1.10.2.2 matt static u_int max_ts; /* Maximal time-slice */ 82 1.10.2.2 matt static u_int rt_ts; /* Real-time time-slice */ 83 1.10.2.2 matt static u_int ts_map[PRI_COUNT]; /* Map of time-slices */ 84 1.10.2.2 matt static pri_t high_pri[PRI_COUNT]; /* Map for priority increase */ 85 1.10.2.2 matt 86 1.10.2.2 matt /* 87 1.10.2.2 matt * Migration and balancing. 88 1.10.2.2 matt */ 89 1.10.2.2 matt #ifdef MULTIPROCESSOR 90 1.10.2.5 matt 91 1.10.2.2 matt static u_int cacheht_time; /* Cache hotness time */ 92 1.10.2.2 matt static u_int min_catch; /* Minimal LWP count for catching */ 93 1.10.2.2 matt 94 1.10.2.2 matt static u_int balance_period; /* Balance period */ 95 1.10.2.2 matt static struct callout balance_ch; /* Callout of balancer */ 96 1.10.2.2 matt 97 1.10.2.2 matt static struct cpu_info * volatile worker_ci; 98 1.10.2.2 matt 99 1.10.2.2 matt #endif 100 1.10.2.2 matt 101 1.10.2.2 matt /* 102 1.10.2.2 matt * Structures, runqueue. 103 1.10.2.2 matt */ 104 1.10.2.2 matt 105 1.10.2.2 matt typedef struct { 106 1.10.2.2 matt TAILQ_HEAD(, lwp) q_head; 107 1.10.2.2 matt } queue_t; 108 1.10.2.2 matt 109 1.10.2.2 matt typedef struct { 110 1.10.2.2 matt /* Lock and bitmap */ 111 1.10.2.2 matt uint32_t r_bitmap[PRI_COUNT >> BITMAP_SHIFT]; 112 1.10.2.2 matt /* Counters */ 113 1.10.2.2 matt u_int r_count; /* Count of the threads */ 114 1.10.2.2 matt pri_t r_highest_pri; /* Highest priority */ 115 1.10.2.2 matt u_int r_avgcount; /* Average count of threads */ 116 1.10.2.2 matt u_int r_mcount; /* Count of migratable threads */ 117 1.10.2.2 matt /* Runqueues */ 118 1.10.2.2 matt queue_t r_rt_queue[PRI_RT_COUNT]; 119 1.10.2.2 matt queue_t r_ts_queue[PRI_TS_COUNT]; 120 1.10.2.2 matt } runqueue_t; 121 1.10.2.2 matt 122 1.10.2.2 matt typedef struct { 123 1.10.2.2 matt u_int sl_flags; 124 1.10.2.2 matt u_int sl_timeslice; /* Time-slice of thread */ 125 1.10.2.2 matt u_int sl_slept; /* Saved sleep time for sleep sum */ 126 1.10.2.2 matt u_int sl_slpsum; /* Sum of sleep time */ 127 1.10.2.2 matt u_int sl_rtime; /* Saved start time of run */ 128 1.10.2.2 matt u_int sl_rtsum; /* Sum of the run time */ 129 1.10.2.2 matt u_int sl_lrtime; /* Last run time */ 130 1.10.2.2 matt } sched_info_lwp_t; 131 1.10.2.2 matt 132 1.10.2.2 matt /* Flags */ 133 1.10.2.2 matt #define SL_BATCH 0x01 134 1.10.2.2 matt 135 1.10.2.2 matt /* Pool of the scheduler-specific structures for threads */ 136 1.10.2.5 matt static pool_cache_t sil_pool; 137 1.10.2.2 matt 138 1.10.2.2 matt /* 139 1.10.2.2 matt * Prototypes. 140 1.10.2.2 matt */ 141 1.10.2.2 matt 142 1.10.2.2 matt static inline void * sched_getrq(runqueue_t *, const pri_t); 143 1.10.2.2 matt static inline void sched_newts(struct lwp *); 144 1.10.2.2 matt static void sched_precalcts(void); 145 1.10.2.2 matt 146 1.10.2.2 matt #ifdef MULTIPROCESSOR 147 1.10.2.2 matt static struct lwp * sched_catchlwp(void); 148 1.10.2.2 matt static void sched_balance(void *); 149 1.10.2.2 matt #endif 150 1.10.2.2 matt 151 1.10.2.2 matt /* 152 1.10.2.2 matt * Initialization and setup. 153 1.10.2.2 matt */ 154 1.10.2.2 matt 155 1.10.2.2 matt void 156 1.10.2.2 matt sched_rqinit(void) 157 1.10.2.2 matt { 158 1.10.2.2 matt struct cpu_info *ci = curcpu(); 159 1.10.2.2 matt 160 1.10.2.2 matt if (hz < 100) { 161 1.10.2.2 matt panic("sched_rqinit: value of HZ is too low\n"); 162 1.10.2.2 matt } 163 1.10.2.2 matt 164 1.10.2.2 matt /* Default timing ranges */ 165 1.10.2.2 matt min_ts = mstohz(50); /* ~50ms */ 166 1.10.2.2 matt max_ts = mstohz(150); /* ~150ms */ 167 1.10.2.2 matt rt_ts = mstohz(100); /* ~100ms */ 168 1.10.2.2 matt sched_precalcts(); 169 1.10.2.2 matt 170 1.10.2.2 matt #ifdef MULTIPROCESSOR 171 1.10.2.2 matt /* Balancing */ 172 1.10.2.2 matt worker_ci = ci; 173 1.10.2.2 matt cacheht_time = mstohz(5); /* ~5 ms */ 174 1.10.2.2 matt balance_period = mstohz(300); /* ~300ms */ 175 1.10.2.2 matt min_catch = ~0; 176 1.10.2.2 matt #endif 177 1.10.2.2 matt 178 1.10.2.2 matt /* Pool of the scheduler-specific structures */ 179 1.10.2.5 matt sil_pool = pool_cache_init(sizeof(sched_info_lwp_t), CACHE_LINE_SIZE, 180 1.10.2.5 matt 0, 0, "lwpsd", NULL, IPL_NONE, NULL, NULL, NULL); 181 1.10.2.2 matt 182 1.10.2.2 matt /* Attach the primary CPU here */ 183 1.10.2.2 matt sched_cpuattach(ci); 184 1.10.2.2 matt 185 1.10.2.2 matt sched_lwp_fork(NULL, &lwp0); 186 1.10.2.2 matt sched_newts(&lwp0); 187 1.10.2.2 matt } 188 1.10.2.2 matt 189 1.10.2.2 matt void 190 1.10.2.2 matt sched_setup(void) 191 1.10.2.2 matt { 192 1.10.2.2 matt 193 1.10.2.2 matt #ifdef MULTIPROCESSOR 194 1.10.2.2 matt /* Minimal count of LWPs for catching: log2(count of CPUs) */ 195 1.10.2.2 matt min_catch = min(ilog2(ncpu), 4); 196 1.10.2.2 matt 197 1.10.2.2 matt /* Initialize balancing callout and run it */ 198 1.10.2.2 matt callout_init(&balance_ch, CALLOUT_MPSAFE); 199 1.10.2.2 matt callout_setfunc(&balance_ch, sched_balance, NULL); 200 1.10.2.2 matt callout_schedule(&balance_ch, balance_period); 201 1.10.2.2 matt #endif 202 1.10.2.2 matt } 203 1.10.2.2 matt 204 1.10.2.2 matt void 205 1.10.2.2 matt sched_cpuattach(struct cpu_info *ci) 206 1.10.2.2 matt { 207 1.10.2.2 matt runqueue_t *ci_rq; 208 1.10.2.2 matt void *rq_ptr; 209 1.10.2.2 matt u_int i, size; 210 1.10.2.2 matt 211 1.10.2.5 matt if (ci == lwp0.l_cpu) { 212 1.10.2.5 matt /* Initialize the scheduler structure of the primary LWP */ 213 1.10.2.5 matt lwp0.l_mutex = ci->ci_schedstate.spc_lwplock; 214 1.10.2.5 matt } 215 1.10.2.5 matt 216 1.10.2.5 matt if (ci->ci_schedstate.spc_mutex != NULL) { 217 1.10.2.5 matt /* Already initialized. */ 218 1.10.2.5 matt return; 219 1.10.2.5 matt } 220 1.10.2.5 matt 221 1.10.2.5 matt /* Allocate the run queue */ 222 1.10.2.5 matt size = roundup2(sizeof(runqueue_t), CACHE_LINE_SIZE) + CACHE_LINE_SIZE; 223 1.10.2.4 matt rq_ptr = kmem_zalloc(size, KM_SLEEP); 224 1.10.2.2 matt if (rq_ptr == NULL) { 225 1.10.2.5 matt panic("sched_cpuattach: could not allocate the runqueue"); 226 1.10.2.2 matt } 227 1.10.2.5 matt ci_rq = (void *)(roundup2((uintptr_t)(rq_ptr), CACHE_LINE_SIZE)); 228 1.10.2.2 matt 229 1.10.2.2 matt /* Initialize run queues */ 230 1.10.2.5 matt KASSERT(sizeof(kmutex_t) <= CACHE_LINE_SIZE); 231 1.10.2.5 matt ci->ci_schedstate.spc_mutex = kmem_alloc(CACHE_LINE_SIZE, KM_SLEEP); 232 1.10.2.5 matt mutex_init(ci->ci_schedstate.spc_mutex, MUTEX_DEFAULT, IPL_SCHED); 233 1.10.2.2 matt for (i = 0; i < PRI_RT_COUNT; i++) 234 1.10.2.2 matt TAILQ_INIT(&ci_rq->r_rt_queue[i].q_head); 235 1.10.2.2 matt for (i = 0; i < PRI_TS_COUNT; i++) 236 1.10.2.2 matt TAILQ_INIT(&ci_rq->r_ts_queue[i].q_head); 237 1.10.2.2 matt ci_rq->r_highest_pri = 0; 238 1.10.2.2 matt 239 1.10.2.2 matt ci->ci_schedstate.spc_sched_info = ci_rq; 240 1.10.2.2 matt } 241 1.10.2.2 matt 242 1.10.2.2 matt /* Pre-calculate the time-slices for the priorities */ 243 1.10.2.2 matt static void 244 1.10.2.2 matt sched_precalcts(void) 245 1.10.2.2 matt { 246 1.10.2.2 matt pri_t p; 247 1.10.2.2 matt 248 1.10.2.2 matt /* Time-sharing range */ 249 1.10.2.2 matt for (p = 0; p <= PRI_HIGHEST_TS; p++) { 250 1.10.2.2 matt ts_map[p] = max_ts - 251 1.10.2.2 matt (p * 100 / (PRI_TS_COUNT - 1) * (max_ts - min_ts) / 100); 252 1.10.2.2 matt high_pri[p] = (PRI_HIGHEST_TS - PRI_HTS_RANGE) + 253 1.10.2.2 matt ((p * PRI_HTS_RANGE) / (PRI_TS_COUNT - 1)); 254 1.10.2.2 matt } 255 1.10.2.2 matt 256 1.10.2.2 matt /* Real-time range */ 257 1.10.2.2 matt for (p = (PRI_HIGHEST_TS + 1); p < PRI_COUNT; p++) { 258 1.10.2.2 matt ts_map[p] = rt_ts; 259 1.10.2.2 matt high_pri[p] = p; 260 1.10.2.2 matt } 261 1.10.2.2 matt } 262 1.10.2.2 matt 263 1.10.2.2 matt /* 264 1.10.2.2 matt * Hooks. 265 1.10.2.2 matt */ 266 1.10.2.2 matt 267 1.10.2.2 matt void 268 1.10.2.2 matt sched_proc_fork(struct proc *parent, struct proc *child) 269 1.10.2.2 matt { 270 1.10.2.2 matt struct lwp *l; 271 1.10.2.2 matt 272 1.10.2.2 matt LIST_FOREACH(l, &child->p_lwps, l_sibling) { 273 1.10.2.2 matt lwp_lock(l); 274 1.10.2.2 matt sched_newts(l); 275 1.10.2.2 matt lwp_unlock(l); 276 1.10.2.2 matt } 277 1.10.2.2 matt } 278 1.10.2.2 matt 279 1.10.2.2 matt void 280 1.10.2.2 matt sched_proc_exit(struct proc *child, struct proc *parent) 281 1.10.2.2 matt { 282 1.10.2.2 matt 283 1.10.2.2 matt /* Dummy */ 284 1.10.2.2 matt } 285 1.10.2.2 matt 286 1.10.2.2 matt void 287 1.10.2.2 matt sched_lwp_fork(struct lwp *l1, struct lwp *l2) 288 1.10.2.2 matt { 289 1.10.2.2 matt 290 1.10.2.2 matt KASSERT(l2->l_sched_info == NULL); 291 1.10.2.5 matt l2->l_sched_info = pool_cache_get(sil_pool, PR_WAITOK); 292 1.10.2.2 matt memset(l2->l_sched_info, 0, sizeof(sched_info_lwp_t)); 293 1.10.2.2 matt } 294 1.10.2.2 matt 295 1.10.2.2 matt void 296 1.10.2.2 matt sched_lwp_exit(struct lwp *l) 297 1.10.2.2 matt { 298 1.10.2.2 matt 299 1.10.2.2 matt KASSERT(l->l_sched_info != NULL); 300 1.10.2.5 matt pool_cache_put(sil_pool, l->l_sched_info); 301 1.10.2.2 matt l->l_sched_info = NULL; 302 1.10.2.2 matt } 303 1.10.2.2 matt 304 1.10.2.2 matt void 305 1.10.2.2 matt sched_lwp_collect(struct lwp *l) 306 1.10.2.2 matt { 307 1.10.2.2 matt 308 1.10.2.2 matt } 309 1.10.2.2 matt 310 1.10.2.2 matt void 311 1.10.2.2 matt sched_setrunnable(struct lwp *l) 312 1.10.2.2 matt { 313 1.10.2.2 matt 314 1.10.2.2 matt /* Dummy */ 315 1.10.2.2 matt } 316 1.10.2.2 matt 317 1.10.2.2 matt void 318 1.10.2.2 matt sched_schedclock(struct lwp *l) 319 1.10.2.2 matt { 320 1.10.2.2 matt 321 1.10.2.2 matt /* Dummy */ 322 1.10.2.2 matt } 323 1.10.2.2 matt 324 1.10.2.2 matt /* 325 1.10.2.2 matt * Priorities and time-slice. 326 1.10.2.2 matt */ 327 1.10.2.2 matt 328 1.10.2.2 matt void 329 1.10.2.2 matt sched_nice(struct proc *p, int prio) 330 1.10.2.2 matt { 331 1.10.2.2 matt 332 1.10.2.5 matt /* TODO: implement as SCHED_IA */ 333 1.10.2.2 matt } 334 1.10.2.2 matt 335 1.10.2.2 matt /* Recalculate the time-slice */ 336 1.10.2.2 matt static inline void 337 1.10.2.2 matt sched_newts(struct lwp *l) 338 1.10.2.2 matt { 339 1.10.2.2 matt sched_info_lwp_t *sil = l->l_sched_info; 340 1.10.2.2 matt 341 1.10.2.2 matt sil->sl_timeslice = ts_map[lwp_eprio(l)]; 342 1.10.2.2 matt } 343 1.10.2.2 matt 344 1.10.2.2 matt /* 345 1.10.2.2 matt * Control of the runqueue. 346 1.10.2.2 matt */ 347 1.10.2.2 matt 348 1.10.2.2 matt static inline void * 349 1.10.2.2 matt sched_getrq(runqueue_t *ci_rq, const pri_t prio) 350 1.10.2.2 matt { 351 1.10.2.2 matt 352 1.10.2.2 matt KASSERT(prio < PRI_COUNT); 353 1.10.2.2 matt return (prio <= PRI_HIGHEST_TS) ? 354 1.10.2.2 matt &ci_rq->r_ts_queue[prio].q_head : 355 1.10.2.2 matt &ci_rq->r_rt_queue[prio - PRI_HIGHEST_TS - 1].q_head; 356 1.10.2.2 matt } 357 1.10.2.2 matt 358 1.10.2.2 matt void 359 1.10.2.2 matt sched_enqueue(struct lwp *l, bool swtch) 360 1.10.2.2 matt { 361 1.10.2.2 matt runqueue_t *ci_rq; 362 1.10.2.2 matt sched_info_lwp_t *sil = l->l_sched_info; 363 1.10.2.2 matt TAILQ_HEAD(, lwp) *q_head; 364 1.10.2.2 matt const pri_t eprio = lwp_eprio(l); 365 1.10.2.2 matt 366 1.10.2.2 matt ci_rq = l->l_cpu->ci_schedstate.spc_sched_info; 367 1.10.2.2 matt KASSERT(lwp_locked(l, l->l_cpu->ci_schedstate.spc_mutex)); 368 1.10.2.2 matt 369 1.10.2.2 matt /* Update the last run time on switch */ 370 1.10.2.3 matt if (__predict_true(swtch == true)) { 371 1.10.2.2 matt sil->sl_lrtime = hardclock_ticks; 372 1.10.2.2 matt sil->sl_rtsum += (hardclock_ticks - sil->sl_rtime); 373 1.10.2.2 matt } else if (sil->sl_lrtime == 0) 374 1.10.2.2 matt sil->sl_lrtime = hardclock_ticks; 375 1.10.2.2 matt 376 1.10.2.2 matt /* Enqueue the thread */ 377 1.10.2.2 matt q_head = sched_getrq(ci_rq, eprio); 378 1.10.2.2 matt if (TAILQ_EMPTY(q_head)) { 379 1.10.2.2 matt u_int i; 380 1.10.2.2 matt uint32_t q; 381 1.10.2.2 matt 382 1.10.2.2 matt /* Mark bit */ 383 1.10.2.2 matt i = eprio >> BITMAP_SHIFT; 384 1.10.2.2 matt q = BITMAP_MSB >> (eprio & BITMAP_MASK); 385 1.10.2.2 matt KASSERT((ci_rq->r_bitmap[i] & q) == 0); 386 1.10.2.2 matt ci_rq->r_bitmap[i] |= q; 387 1.10.2.2 matt } 388 1.10.2.2 matt TAILQ_INSERT_TAIL(q_head, l, l_runq); 389 1.10.2.2 matt ci_rq->r_count++; 390 1.10.2.2 matt if ((l->l_flag & LW_BOUND) == 0) 391 1.10.2.2 matt ci_rq->r_mcount++; 392 1.10.2.2 matt 393 1.10.2.2 matt /* 394 1.10.2.2 matt * Update the value of highest priority in the runqueue, 395 1.10.2.2 matt * if priority of this thread is higher. 396 1.10.2.2 matt */ 397 1.10.2.2 matt if (eprio > ci_rq->r_highest_pri) 398 1.10.2.2 matt ci_rq->r_highest_pri = eprio; 399 1.10.2.2 matt 400 1.10.2.2 matt sched_newts(l); 401 1.10.2.2 matt } 402 1.10.2.2 matt 403 1.10.2.2 matt void 404 1.10.2.2 matt sched_dequeue(struct lwp *l) 405 1.10.2.2 matt { 406 1.10.2.2 matt runqueue_t *ci_rq; 407 1.10.2.2 matt TAILQ_HEAD(, lwp) *q_head; 408 1.10.2.2 matt const pri_t eprio = lwp_eprio(l); 409 1.10.2.2 matt 410 1.10.2.2 matt ci_rq = l->l_cpu->ci_schedstate.spc_sched_info; 411 1.10.2.2 matt KASSERT(lwp_locked(l, l->l_cpu->ci_schedstate.spc_mutex)); 412 1.10.2.5 matt 413 1.10.2.2 matt KASSERT(eprio <= ci_rq->r_highest_pri); 414 1.10.2.2 matt KASSERT(ci_rq->r_bitmap[eprio >> BITMAP_SHIFT] != 0); 415 1.10.2.2 matt KASSERT(ci_rq->r_count > 0); 416 1.10.2.2 matt 417 1.10.2.2 matt ci_rq->r_count--; 418 1.10.2.2 matt if ((l->l_flag & LW_BOUND) == 0) 419 1.10.2.2 matt ci_rq->r_mcount--; 420 1.10.2.2 matt 421 1.10.2.2 matt q_head = sched_getrq(ci_rq, eprio); 422 1.10.2.2 matt TAILQ_REMOVE(q_head, l, l_runq); 423 1.10.2.2 matt if (TAILQ_EMPTY(q_head)) { 424 1.10.2.2 matt u_int i; 425 1.10.2.2 matt uint32_t q; 426 1.10.2.2 matt 427 1.10.2.2 matt /* Unmark bit */ 428 1.10.2.2 matt i = eprio >> BITMAP_SHIFT; 429 1.10.2.2 matt q = BITMAP_MSB >> (eprio & BITMAP_MASK); 430 1.10.2.2 matt KASSERT((ci_rq->r_bitmap[i] & q) != 0); 431 1.10.2.2 matt ci_rq->r_bitmap[i] &= ~q; 432 1.10.2.2 matt 433 1.10.2.2 matt /* 434 1.10.2.2 matt * Update the value of highest priority in the runqueue, in a 435 1.10.2.2 matt * case it was a last thread in the queue of highest priority. 436 1.10.2.2 matt */ 437 1.10.2.2 matt if (eprio != ci_rq->r_highest_pri) 438 1.10.2.2 matt return; 439 1.10.2.2 matt 440 1.10.2.2 matt do { 441 1.10.2.2 matt q = ffs(ci_rq->r_bitmap[i]); 442 1.10.2.2 matt if (q) { 443 1.10.2.2 matt ci_rq->r_highest_pri = 444 1.10.2.2 matt (i << BITMAP_SHIFT) + (BITMAP_BITS - q); 445 1.10.2.2 matt return; 446 1.10.2.2 matt } 447 1.10.2.2 matt } while (i--); 448 1.10.2.2 matt 449 1.10.2.2 matt /* If not found - set the lowest value */ 450 1.10.2.2 matt ci_rq->r_highest_pri = 0; 451 1.10.2.2 matt } 452 1.10.2.2 matt } 453 1.10.2.2 matt 454 1.10.2.2 matt void 455 1.10.2.2 matt sched_slept(struct lwp *l) 456 1.10.2.2 matt { 457 1.10.2.2 matt sched_info_lwp_t *sil = l->l_sched_info; 458 1.10.2.2 matt 459 1.10.2.2 matt /* Save the time when thread has slept */ 460 1.10.2.2 matt sil->sl_slept = hardclock_ticks; 461 1.10.2.2 matt 462 1.10.2.2 matt /* 463 1.10.2.2 matt * If thread is in time-sharing queue and batch flag is not marked, 464 1.10.2.2 matt * increase the the priority, and run with the lower time-quantum. 465 1.10.2.2 matt */ 466 1.10.2.5 matt if (l->l_priority < PRI_HIGHEST_TS && 467 1.10.2.5 matt (sil->sl_flags & SL_BATCH) == 0) { 468 1.10.2.2 matt KASSERT(l->l_class == SCHED_OTHER); 469 1.10.2.2 matt l->l_priority++; 470 1.10.2.2 matt } 471 1.10.2.2 matt } 472 1.10.2.2 matt 473 1.10.2.2 matt void 474 1.10.2.2 matt sched_wakeup(struct lwp *l) 475 1.10.2.2 matt { 476 1.10.2.2 matt sched_info_lwp_t *sil = l->l_sched_info; 477 1.10.2.5 matt const u_int slptime = hardclock_ticks - sil->sl_slept; 478 1.10.2.2 matt 479 1.10.2.2 matt /* Update sleep time delta */ 480 1.10.2.5 matt sil->sl_slpsum += (l->l_slptime == 0) ? slptime : hz; 481 1.10.2.2 matt 482 1.10.2.2 matt /* If thread was sleeping a second or more - set a high priority */ 483 1.10.2.5 matt if (l->l_slptime > 1 || slptime >= hz) 484 1.10.2.2 matt l->l_priority = high_pri[l->l_priority]; 485 1.10.2.2 matt 486 1.10.2.2 matt /* Also, consider looking for a better CPU to wake up */ 487 1.10.2.5 matt l->l_cpu = sched_takecpu(l); 488 1.10.2.2 matt } 489 1.10.2.2 matt 490 1.10.2.2 matt void 491 1.10.2.2 matt sched_pstats_hook(struct lwp *l) 492 1.10.2.2 matt { 493 1.10.2.2 matt sched_info_lwp_t *sil = l->l_sched_info; 494 1.10.2.3 matt pri_t prio; 495 1.10.2.2 matt bool batch; 496 1.10.2.2 matt 497 1.10.2.2 matt if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP || 498 1.10.2.2 matt l->l_stat == LSSUSPENDED) 499 1.10.2.2 matt l->l_slptime++; 500 1.10.2.2 matt 501 1.10.2.2 matt /* 502 1.10.2.2 matt * Set that thread is more CPU-bound, if sum of run time exceeds the 503 1.10.2.2 matt * sum of sleep time. Check if thread is CPU-bound a first time. 504 1.10.2.2 matt */ 505 1.10.2.2 matt batch = (sil->sl_rtsum > sil->sl_slpsum); 506 1.10.2.2 matt if (batch) { 507 1.10.2.2 matt if ((sil->sl_flags & SL_BATCH) == 0) 508 1.10.2.2 matt batch = false; 509 1.10.2.2 matt sil->sl_flags |= SL_BATCH; 510 1.10.2.2 matt } else 511 1.10.2.2 matt sil->sl_flags &= ~SL_BATCH; 512 1.10.2.2 matt 513 1.10.2.5 matt /* 514 1.10.2.5 matt * If thread is CPU-bound and never sleeps, it would occupy the CPU. 515 1.10.2.5 matt * In such case reset the value of last sleep, and check it later, if 516 1.10.2.5 matt * it is still zero - perform the migration, unmark the batch flag. 517 1.10.2.5 matt */ 518 1.10.2.5 matt if (batch && (l->l_slptime + sil->sl_slpsum) == 0) { 519 1.10.2.5 matt if (l->l_stat != LSONPROC && sil->sl_slept == 0) { 520 1.10.2.5 matt struct cpu_info *ci = sched_takecpu(l); 521 1.10.2.5 matt 522 1.10.2.5 matt if (l->l_cpu != ci) 523 1.10.2.5 matt l->l_target_cpu = ci; 524 1.10.2.5 matt sil->sl_flags &= ~SL_BATCH; 525 1.10.2.5 matt } else { 526 1.10.2.5 matt sil->sl_slept = 0; 527 1.10.2.5 matt } 528 1.10.2.5 matt } 529 1.10.2.5 matt 530 1.10.2.2 matt /* Reset the time sums */ 531 1.10.2.2 matt sil->sl_slpsum = 0; 532 1.10.2.2 matt sil->sl_rtsum = 0; 533 1.10.2.2 matt 534 1.10.2.5 matt /* 535 1.10.2.5 matt * Estimate threads on time-sharing queue only, however, 536 1.10.2.5 matt * exclude the highest priority for performance purposes. 537 1.10.2.5 matt */ 538 1.10.2.2 matt if (l->l_priority >= PRI_HIGHEST_TS) 539 1.10.2.2 matt return; 540 1.10.2.5 matt KASSERT(l->l_class == SCHED_OTHER); 541 1.10.2.2 matt 542 1.10.2.2 matt /* If it is CPU-bound not a first time - decrease the priority */ 543 1.10.2.3 matt prio = l->l_priority; 544 1.10.2.3 matt if (batch && prio != 0) 545 1.10.2.3 matt prio--; 546 1.10.2.2 matt 547 1.10.2.2 matt /* If thread was not ran a second or more - set a high priority */ 548 1.10.2.3 matt if (l->l_stat == LSRUN) { 549 1.10.2.3 matt if (sil->sl_lrtime && (hardclock_ticks - sil->sl_lrtime >= hz)) 550 1.10.2.3 matt prio = high_pri[prio]; 551 1.10.2.3 matt /* Re-enqueue the thread if priority has changed */ 552 1.10.2.3 matt if (prio != l->l_priority) 553 1.10.2.3 matt lwp_changepri(l, prio); 554 1.10.2.3 matt } else { 555 1.10.2.3 matt /* In other states, change the priority directly */ 556 1.10.2.3 matt l->l_priority = prio; 557 1.10.2.3 matt } 558 1.10.2.2 matt } 559 1.10.2.2 matt 560 1.10.2.2 matt /* 561 1.10.2.2 matt * Migration and balancing. 562 1.10.2.2 matt */ 563 1.10.2.2 matt 564 1.10.2.2 matt #ifdef MULTIPROCESSOR 565 1.10.2.2 matt 566 1.10.2.5 matt /* Estimate if LWP is cache-hot */ 567 1.10.2.5 matt static inline bool 568 1.10.2.5 matt lwp_cache_hot(const struct lwp *l) 569 1.10.2.5 matt { 570 1.10.2.5 matt const sched_info_lwp_t *sil = l->l_sched_info; 571 1.10.2.5 matt 572 1.10.2.5 matt if (l->l_slptime || sil->sl_lrtime == 0) 573 1.10.2.5 matt return false; 574 1.10.2.5 matt 575 1.10.2.5 matt return (hardclock_ticks - sil->sl_lrtime <= cacheht_time); 576 1.10.2.5 matt } 577 1.10.2.5 matt 578 1.10.2.2 matt /* Check if LWP can migrate to the chosen CPU */ 579 1.10.2.2 matt static inline bool 580 1.10.2.5 matt sched_migratable(const struct lwp *l, struct cpu_info *ci) 581 1.10.2.2 matt { 582 1.10.2.5 matt const struct schedstate_percpu *spc = &ci->ci_schedstate; 583 1.10.2.2 matt 584 1.10.2.5 matt /* CPU is offline */ 585 1.10.2.5 matt if (__predict_false(spc->spc_flags & SPCF_OFFLINE)) 586 1.10.2.2 matt return false; 587 1.10.2.2 matt 588 1.10.2.5 matt /* Affinity bind */ 589 1.10.2.5 matt if (__predict_false(l->l_flag & LW_AFFINITY)) 590 1.10.2.5 matt return CPU_ISSET(cpu_index(ci), &l->l_affinity); 591 1.10.2.5 matt 592 1.10.2.5 matt /* Processor-set */ 593 1.10.2.5 matt return (spc->spc_psid == l->l_psid); 594 1.10.2.2 matt } 595 1.10.2.2 matt 596 1.10.2.2 matt /* 597 1.10.2.2 matt * Estimate the migration of LWP to the other CPU. 598 1.10.2.2 matt * Take and return the CPU, if migration is needed. 599 1.10.2.2 matt */ 600 1.10.2.2 matt struct cpu_info * 601 1.10.2.2 matt sched_takecpu(struct lwp *l) 602 1.10.2.2 matt { 603 1.10.2.5 matt struct cpu_info *ci, *tci; 604 1.10.2.2 matt struct schedstate_percpu *spc; 605 1.10.2.2 matt runqueue_t *ci_rq; 606 1.10.2.2 matt CPU_INFO_ITERATOR cii; 607 1.10.2.2 matt pri_t eprio, lpri; 608 1.10.2.2 matt 609 1.10.2.5 matt KASSERT(lwp_locked(l, NULL)); 610 1.10.2.5 matt 611 1.10.2.2 matt ci = l->l_cpu; 612 1.10.2.2 matt spc = &ci->ci_schedstate; 613 1.10.2.2 matt ci_rq = spc->spc_sched_info; 614 1.10.2.2 matt 615 1.10.2.5 matt /* If thread is strictly bound, do not estimate other CPUs */ 616 1.10.2.5 matt if (l->l_flag & LW_BOUND) 617 1.10.2.5 matt return ci; 618 1.10.2.5 matt 619 1.10.2.2 matt /* CPU of this thread is idling - run there */ 620 1.10.2.2 matt if (ci_rq->r_count == 0) 621 1.10.2.2 matt return ci; 622 1.10.2.2 matt 623 1.10.2.2 matt eprio = lwp_eprio(l); 624 1.10.2.2 matt 625 1.10.2.2 matt /* Stay if thread is cache-hot */ 626 1.10.2.5 matt if (__predict_true(l->l_stat != LSIDL) && 627 1.10.2.5 matt lwp_cache_hot(l) && eprio >= spc->spc_curpriority) 628 1.10.2.2 matt return ci; 629 1.10.2.2 matt 630 1.10.2.2 matt /* Run on current CPU if priority of thread is higher */ 631 1.10.2.2 matt ci = curcpu(); 632 1.10.2.2 matt spc = &ci->ci_schedstate; 633 1.10.2.2 matt if (eprio > spc->spc_curpriority && sched_migratable(l, ci)) 634 1.10.2.2 matt return ci; 635 1.10.2.2 matt 636 1.10.2.2 matt /* 637 1.10.2.2 matt * Look for the CPU with the lowest priority thread. In case of 638 1.10.2.2 matt * equal the priority - check the lower count of the threads. 639 1.10.2.2 matt */ 640 1.10.2.5 matt tci = l->l_cpu; 641 1.10.2.2 matt lpri = PRI_COUNT; 642 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) { 643 1.10.2.2 matt runqueue_t *ici_rq; 644 1.10.2.2 matt pri_t pri; 645 1.10.2.2 matt 646 1.10.2.2 matt spc = &ci->ci_schedstate; 647 1.10.2.2 matt ici_rq = spc->spc_sched_info; 648 1.10.2.2 matt pri = max(spc->spc_curpriority, ici_rq->r_highest_pri); 649 1.10.2.2 matt if (pri > lpri) 650 1.10.2.2 matt continue; 651 1.10.2.2 matt 652 1.10.2.5 matt if (pri == lpri && ci_rq->r_count < ici_rq->r_count) 653 1.10.2.2 matt continue; 654 1.10.2.2 matt 655 1.10.2.5 matt if (!sched_migratable(l, ci)) 656 1.10.2.2 matt continue; 657 1.10.2.2 matt 658 1.10.2.2 matt lpri = pri; 659 1.10.2.2 matt tci = ci; 660 1.10.2.2 matt ci_rq = ici_rq; 661 1.10.2.2 matt } 662 1.10.2.2 matt return tci; 663 1.10.2.2 matt } 664 1.10.2.2 matt 665 1.10.2.2 matt /* 666 1.10.2.2 matt * Tries to catch an LWP from the runqueue of other CPU. 667 1.10.2.2 matt */ 668 1.10.2.2 matt static struct lwp * 669 1.10.2.2 matt sched_catchlwp(void) 670 1.10.2.2 matt { 671 1.10.2.2 matt struct cpu_info *curci = curcpu(), *ci = worker_ci; 672 1.10.2.2 matt TAILQ_HEAD(, lwp) *q_head; 673 1.10.2.2 matt runqueue_t *ci_rq; 674 1.10.2.2 matt struct lwp *l; 675 1.10.2.2 matt 676 1.10.2.2 matt if (curci == ci) 677 1.10.2.2 matt return NULL; 678 1.10.2.2 matt 679 1.10.2.2 matt /* Lockless check */ 680 1.10.2.2 matt ci_rq = ci->ci_schedstate.spc_sched_info; 681 1.10.2.5 matt if (ci_rq->r_mcount < min_catch) 682 1.10.2.2 matt return NULL; 683 1.10.2.2 matt 684 1.10.2.2 matt /* 685 1.10.2.2 matt * Double-lock the runqueues. 686 1.10.2.2 matt */ 687 1.10.2.2 matt if (curci < ci) { 688 1.10.2.2 matt spc_lock(ci); 689 1.10.2.2 matt } else if (!mutex_tryenter(ci->ci_schedstate.spc_mutex)) { 690 1.10.2.2 matt const runqueue_t *cur_rq = curci->ci_schedstate.spc_sched_info; 691 1.10.2.2 matt 692 1.10.2.2 matt spc_unlock(curci); 693 1.10.2.2 matt spc_lock(ci); 694 1.10.2.2 matt spc_lock(curci); 695 1.10.2.2 matt 696 1.10.2.2 matt if (cur_rq->r_count) { 697 1.10.2.2 matt spc_unlock(ci); 698 1.10.2.2 matt return NULL; 699 1.10.2.2 matt } 700 1.10.2.2 matt } 701 1.10.2.2 matt 702 1.10.2.5 matt if (ci_rq->r_mcount < min_catch) { 703 1.10.2.2 matt spc_unlock(ci); 704 1.10.2.2 matt return NULL; 705 1.10.2.2 matt } 706 1.10.2.2 matt 707 1.10.2.2 matt /* Take the highest priority thread */ 708 1.10.2.2 matt q_head = sched_getrq(ci_rq, ci_rq->r_highest_pri); 709 1.10.2.2 matt l = TAILQ_FIRST(q_head); 710 1.10.2.2 matt 711 1.10.2.2 matt for (;;) { 712 1.10.2.2 matt /* Check the first and next result from the queue */ 713 1.10.2.2 matt if (l == NULL) 714 1.10.2.2 matt break; 715 1.10.2.5 matt KASSERT(l->l_stat == LSRUN); 716 1.10.2.5 matt KASSERT(l->l_flag & LW_INMEM); 717 1.10.2.2 matt 718 1.10.2.2 matt /* Look for threads, whose are allowed to migrate */ 719 1.10.2.5 matt if ((l->l_flag & LW_BOUND) || lwp_cache_hot(l) || 720 1.10.2.5 matt !sched_migratable(l, curci)) { 721 1.10.2.2 matt l = TAILQ_NEXT(l, l_runq); 722 1.10.2.2 matt continue; 723 1.10.2.2 matt } 724 1.10.2.5 matt 725 1.10.2.5 matt /* Grab the thread, and move to the local run queue */ 726 1.10.2.5 matt sched_dequeue(l); 727 1.10.2.5 matt l->l_cpu = curci; 728 1.10.2.5 matt lwp_unlock_to(l, curci->ci_schedstate.spc_mutex); 729 1.10.2.5 matt sched_enqueue(l, false); 730 1.10.2.5 matt return l; 731 1.10.2.2 matt } 732 1.10.2.2 matt spc_unlock(ci); 733 1.10.2.2 matt 734 1.10.2.2 matt return l; 735 1.10.2.2 matt } 736 1.10.2.2 matt 737 1.10.2.2 matt /* 738 1.10.2.2 matt * Periodical calculations for balancing. 739 1.10.2.2 matt */ 740 1.10.2.2 matt static void 741 1.10.2.2 matt sched_balance(void *nocallout) 742 1.10.2.2 matt { 743 1.10.2.2 matt struct cpu_info *ci, *hci; 744 1.10.2.2 matt runqueue_t *ci_rq; 745 1.10.2.2 matt CPU_INFO_ITERATOR cii; 746 1.10.2.2 matt u_int highest; 747 1.10.2.2 matt 748 1.10.2.2 matt hci = curcpu(); 749 1.10.2.2 matt highest = 0; 750 1.10.2.2 matt 751 1.10.2.2 matt /* Make lockless countings */ 752 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) { 753 1.10.2.2 matt ci_rq = ci->ci_schedstate.spc_sched_info; 754 1.10.2.2 matt 755 1.10.2.2 matt /* Average count of the threads */ 756 1.10.2.2 matt ci_rq->r_avgcount = (ci_rq->r_avgcount + ci_rq->r_mcount) >> 1; 757 1.10.2.2 matt 758 1.10.2.2 matt /* Look for CPU with the highest average */ 759 1.10.2.2 matt if (ci_rq->r_avgcount > highest) { 760 1.10.2.2 matt hci = ci; 761 1.10.2.2 matt highest = ci_rq->r_avgcount; 762 1.10.2.2 matt } 763 1.10.2.2 matt } 764 1.10.2.2 matt 765 1.10.2.2 matt /* Update the worker */ 766 1.10.2.2 matt worker_ci = hci; 767 1.10.2.2 matt 768 1.10.2.2 matt if (nocallout == NULL) 769 1.10.2.2 matt callout_schedule(&balance_ch, balance_period); 770 1.10.2.2 matt } 771 1.10.2.2 matt 772 1.10.2.2 matt #else 773 1.10.2.2 matt 774 1.10.2.2 matt struct cpu_info * 775 1.10.2.2 matt sched_takecpu(struct lwp *l) 776 1.10.2.2 matt { 777 1.10.2.2 matt 778 1.10.2.2 matt return l->l_cpu; 779 1.10.2.2 matt } 780 1.10.2.2 matt 781 1.10.2.2 matt #endif /* MULTIPROCESSOR */ 782 1.10.2.2 matt 783 1.10.2.2 matt /* 784 1.10.2.2 matt * Scheduler mill. 785 1.10.2.2 matt */ 786 1.10.2.2 matt struct lwp * 787 1.10.2.2 matt sched_nextlwp(void) 788 1.10.2.2 matt { 789 1.10.2.2 matt struct cpu_info *ci = curcpu(); 790 1.10.2.2 matt struct schedstate_percpu *spc; 791 1.10.2.2 matt TAILQ_HEAD(, lwp) *q_head; 792 1.10.2.2 matt sched_info_lwp_t *sil; 793 1.10.2.2 matt runqueue_t *ci_rq; 794 1.10.2.2 matt struct lwp *l; 795 1.10.2.2 matt 796 1.10.2.2 matt spc = &ci->ci_schedstate; 797 1.10.2.2 matt ci_rq = ci->ci_schedstate.spc_sched_info; 798 1.10.2.2 matt 799 1.10.2.2 matt #ifdef MULTIPROCESSOR 800 1.10.2.2 matt /* If runqueue is empty, try to catch some thread from other CPU */ 801 1.10.2.3 matt if (__predict_false(spc->spc_flags & SPCF_OFFLINE)) { 802 1.10.2.2 matt if ((ci_rq->r_count - ci_rq->r_mcount) == 0) 803 1.10.2.2 matt return NULL; 804 1.10.2.2 matt } else if (ci_rq->r_count == 0) { 805 1.10.2.2 matt /* Reset the counter, and call the balancer */ 806 1.10.2.2 matt ci_rq->r_avgcount = 0; 807 1.10.2.2 matt sched_balance(ci); 808 1.10.2.2 matt 809 1.10.2.2 matt /* The re-locking will be done inside */ 810 1.10.2.2 matt return sched_catchlwp(); 811 1.10.2.2 matt } 812 1.10.2.2 matt #else 813 1.10.2.2 matt if (ci_rq->r_count == 0) 814 1.10.2.2 matt return NULL; 815 1.10.2.2 matt #endif 816 1.10.2.2 matt 817 1.10.2.2 matt /* Take the highest priority thread */ 818 1.10.2.2 matt KASSERT(ci_rq->r_bitmap[ci_rq->r_highest_pri >> BITMAP_SHIFT]); 819 1.10.2.2 matt q_head = sched_getrq(ci_rq, ci_rq->r_highest_pri); 820 1.10.2.2 matt l = TAILQ_FIRST(q_head); 821 1.10.2.2 matt KASSERT(l != NULL); 822 1.10.2.2 matt 823 1.10.2.2 matt /* Update the counters */ 824 1.10.2.2 matt sil = l->l_sched_info; 825 1.10.2.2 matt KASSERT(sil->sl_timeslice >= min_ts); 826 1.10.2.2 matt KASSERT(sil->sl_timeslice <= max_ts); 827 1.10.2.2 matt spc->spc_ticks = sil->sl_timeslice; 828 1.10.2.2 matt sil->sl_rtime = hardclock_ticks; 829 1.10.2.2 matt 830 1.10.2.2 matt return l; 831 1.10.2.2 matt } 832 1.10.2.2 matt 833 1.10.2.2 matt bool 834 1.10.2.2 matt sched_curcpu_runnable_p(void) 835 1.10.2.2 matt { 836 1.10.2.2 matt const struct cpu_info *ci = curcpu(); 837 1.10.2.2 matt const runqueue_t *ci_rq = ci->ci_schedstate.spc_sched_info; 838 1.10.2.2 matt 839 1.10.2.3 matt #ifndef __HAVE_FAST_SOFTINTS 840 1.10.2.3 matt if (ci->ci_data.cpu_softints) 841 1.10.2.3 matt return true; 842 1.10.2.3 matt #endif 843 1.10.2.3 matt 844 1.10.2.2 matt if (ci->ci_schedstate.spc_flags & SPCF_OFFLINE) 845 1.10.2.2 matt return (ci_rq->r_count - ci_rq->r_mcount); 846 1.10.2.2 matt 847 1.10.2.2 matt return ci_rq->r_count; 848 1.10.2.2 matt } 849 1.10.2.2 matt 850 1.10.2.2 matt /* 851 1.10.2.2 matt * Time-driven events. 852 1.10.2.2 matt */ 853 1.10.2.2 matt 854 1.10.2.2 matt /* 855 1.10.2.2 matt * Called once per time-quantum. This routine is CPU-local and runs at 856 1.10.2.2 matt * IPL_SCHED, thus the locking is not needed. 857 1.10.2.2 matt */ 858 1.10.2.2 matt void 859 1.10.2.2 matt sched_tick(struct cpu_info *ci) 860 1.10.2.2 matt { 861 1.10.2.2 matt const runqueue_t *ci_rq = ci->ci_schedstate.spc_sched_info; 862 1.10.2.2 matt struct schedstate_percpu *spc = &ci->ci_schedstate; 863 1.10.2.2 matt struct lwp *l = curlwp; 864 1.10.2.5 matt const sched_info_lwp_t *sil = l->l_sched_info; 865 1.10.2.2 matt 866 1.10.2.2 matt if (CURCPU_IDLE_P()) 867 1.10.2.2 matt return; 868 1.10.2.2 matt 869 1.10.2.2 matt switch (l->l_class) { 870 1.10.2.2 matt case SCHED_FIFO: 871 1.10.2.2 matt /* 872 1.10.2.2 matt * Update the time-quantum, and continue running, 873 1.10.2.2 matt * if thread runs on FIFO real-time policy. 874 1.10.2.2 matt */ 875 1.10.2.5 matt KASSERT(l->l_priority > PRI_HIGHEST_TS); 876 1.10.2.2 matt spc->spc_ticks = sil->sl_timeslice; 877 1.10.2.2 matt return; 878 1.10.2.2 matt case SCHED_OTHER: 879 1.10.2.2 matt /* 880 1.10.2.2 matt * If thread is in time-sharing queue, decrease the priority, 881 1.10.2.2 matt * and run with a higher time-quantum. 882 1.10.2.2 matt */ 883 1.10.2.5 matt KASSERT(l->l_priority <= PRI_HIGHEST_TS); 884 1.10.2.2 matt if (l->l_priority != 0) 885 1.10.2.2 matt l->l_priority--; 886 1.10.2.2 matt break; 887 1.10.2.2 matt } 888 1.10.2.2 matt 889 1.10.2.2 matt /* 890 1.10.2.2 matt * If there are higher priority threads or threads in the same queue, 891 1.10.2.2 matt * mark that thread should yield, otherwise, continue running. 892 1.10.2.2 matt */ 893 1.10.2.5 matt if (lwp_eprio(l) <= ci_rq->r_highest_pri || l->l_target_cpu) { 894 1.10.2.2 matt spc->spc_flags |= SPCF_SHOULDYIELD; 895 1.10.2.2 matt cpu_need_resched(ci, 0); 896 1.10.2.2 matt } else 897 1.10.2.2 matt spc->spc_ticks = sil->sl_timeslice; 898 1.10.2.2 matt } 899 1.10.2.2 matt 900 1.10.2.2 matt /* 901 1.10.2.2 matt * Sysctl nodes and initialization. 902 1.10.2.2 matt */ 903 1.10.2.2 matt 904 1.10.2.2 matt static int 905 1.10.2.5 matt sysctl_sched_rtts(SYSCTLFN_ARGS) 906 1.10.2.5 matt { 907 1.10.2.5 matt struct sysctlnode node; 908 1.10.2.5 matt int rttsms = hztoms(rt_ts); 909 1.10.2.5 matt 910 1.10.2.5 matt node = *rnode; 911 1.10.2.5 matt node.sysctl_data = &rttsms; 912 1.10.2.5 matt return sysctl_lookup(SYSCTLFN_CALL(&node)); 913 1.10.2.5 matt } 914 1.10.2.5 matt 915 1.10.2.5 matt static int 916 1.10.2.2 matt sysctl_sched_mints(SYSCTLFN_ARGS) 917 1.10.2.2 matt { 918 1.10.2.2 matt struct sysctlnode node; 919 1.10.2.2 matt struct cpu_info *ci; 920 1.10.2.2 matt int error, newsize; 921 1.10.2.2 matt CPU_INFO_ITERATOR cii; 922 1.10.2.2 matt 923 1.10.2.2 matt node = *rnode; 924 1.10.2.2 matt node.sysctl_data = &newsize; 925 1.10.2.2 matt 926 1.10.2.2 matt newsize = hztoms(min_ts); 927 1.10.2.2 matt error = sysctl_lookup(SYSCTLFN_CALL(&node)); 928 1.10.2.2 matt if (error || newp == NULL) 929 1.10.2.2 matt return error; 930 1.10.2.2 matt 931 1.10.2.2 matt newsize = mstohz(newsize); 932 1.10.2.2 matt if (newsize < 1 || newsize > hz || newsize >= max_ts) 933 1.10.2.2 matt return EINVAL; 934 1.10.2.2 matt 935 1.10.2.2 matt /* It is safe to do this in such order */ 936 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) 937 1.10.2.2 matt spc_lock(ci); 938 1.10.2.2 matt 939 1.10.2.2 matt min_ts = newsize; 940 1.10.2.2 matt sched_precalcts(); 941 1.10.2.2 matt 942 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) 943 1.10.2.2 matt spc_unlock(ci); 944 1.10.2.2 matt 945 1.10.2.2 matt return 0; 946 1.10.2.2 matt } 947 1.10.2.2 matt 948 1.10.2.2 matt static int 949 1.10.2.2 matt sysctl_sched_maxts(SYSCTLFN_ARGS) 950 1.10.2.2 matt { 951 1.10.2.2 matt struct sysctlnode node; 952 1.10.2.2 matt struct cpu_info *ci; 953 1.10.2.2 matt int error, newsize; 954 1.10.2.2 matt CPU_INFO_ITERATOR cii; 955 1.10.2.2 matt 956 1.10.2.2 matt node = *rnode; 957 1.10.2.2 matt node.sysctl_data = &newsize; 958 1.10.2.2 matt 959 1.10.2.2 matt newsize = hztoms(max_ts); 960 1.10.2.2 matt error = sysctl_lookup(SYSCTLFN_CALL(&node)); 961 1.10.2.2 matt if (error || newp == NULL) 962 1.10.2.2 matt return error; 963 1.10.2.2 matt 964 1.10.2.2 matt newsize = mstohz(newsize); 965 1.10.2.2 matt if (newsize < 10 || newsize > hz || newsize <= min_ts) 966 1.10.2.2 matt return EINVAL; 967 1.10.2.2 matt 968 1.10.2.2 matt /* It is safe to do this in such order */ 969 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) 970 1.10.2.2 matt spc_lock(ci); 971 1.10.2.2 matt 972 1.10.2.2 matt max_ts = newsize; 973 1.10.2.2 matt sched_precalcts(); 974 1.10.2.2 matt 975 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) 976 1.10.2.2 matt spc_unlock(ci); 977 1.10.2.2 matt 978 1.10.2.2 matt return 0; 979 1.10.2.2 matt } 980 1.10.2.2 matt 981 1.10.2.2 matt SYSCTL_SETUP(sysctl_sched_setup, "sysctl kern.sched subtree setup") 982 1.10.2.2 matt { 983 1.10.2.2 matt const struct sysctlnode *node = NULL; 984 1.10.2.2 matt 985 1.10.2.2 matt sysctl_createv(clog, 0, NULL, NULL, 986 1.10.2.2 matt CTLFLAG_PERMANENT, 987 1.10.2.2 matt CTLTYPE_NODE, "kern", NULL, 988 1.10.2.2 matt NULL, 0, NULL, 0, 989 1.10.2.2 matt CTL_KERN, CTL_EOL); 990 1.10.2.2 matt sysctl_createv(clog, 0, NULL, &node, 991 1.10.2.2 matt CTLFLAG_PERMANENT, 992 1.10.2.2 matt CTLTYPE_NODE, "sched", 993 1.10.2.2 matt SYSCTL_DESCR("Scheduler options"), 994 1.10.2.2 matt NULL, 0, NULL, 0, 995 1.10.2.2 matt CTL_KERN, CTL_CREATE, CTL_EOL); 996 1.10.2.2 matt 997 1.10.2.2 matt if (node == NULL) 998 1.10.2.2 matt return; 999 1.10.2.2 matt 1000 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1001 1.10.2.2 matt CTLFLAG_PERMANENT, 1002 1.10.2.2 matt CTLTYPE_STRING, "name", NULL, 1003 1.10.2.2 matt NULL, 0, __UNCONST("M2"), 0, 1004 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1005 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1006 1.10.2.5 matt CTLFLAG_PERMANENT, 1007 1.10.2.5 matt CTLTYPE_INT, "rtts", 1008 1.10.2.5 matt SYSCTL_DESCR("Round-robin time quantum (in miliseconds)"), 1009 1.10.2.5 matt sysctl_sched_rtts, 0, NULL, 0, 1010 1.10.2.5 matt CTL_CREATE, CTL_EOL); 1011 1.10.2.5 matt sysctl_createv(clog, 0, &node, NULL, 1012 1.10.2.2 matt CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 1013 1.10.2.2 matt CTLTYPE_INT, "maxts", 1014 1.10.2.2 matt SYSCTL_DESCR("Maximal time quantum (in miliseconds)"), 1015 1.10.2.2 matt sysctl_sched_maxts, 0, &max_ts, 0, 1016 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1017 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1018 1.10.2.2 matt CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 1019 1.10.2.2 matt CTLTYPE_INT, "mints", 1020 1.10.2.2 matt SYSCTL_DESCR("Minimal time quantum (in miliseconds)"), 1021 1.10.2.2 matt sysctl_sched_mints, 0, &min_ts, 0, 1022 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1023 1.10.2.2 matt 1024 1.10.2.2 matt #ifdef MULTIPROCESSOR 1025 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1026 1.10.2.2 matt CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 1027 1.10.2.2 matt CTLTYPE_INT, "cacheht_time", 1028 1.10.2.2 matt SYSCTL_DESCR("Cache hotness time (in ticks)"), 1029 1.10.2.2 matt NULL, 0, &cacheht_time, 0, 1030 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1031 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1032 1.10.2.2 matt CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 1033 1.10.2.2 matt CTLTYPE_INT, "balance_period", 1034 1.10.2.2 matt SYSCTL_DESCR("Balance period (in ticks)"), 1035 1.10.2.2 matt NULL, 0, &balance_period, 0, 1036 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1037 1.10.2.2 matt sysctl_createv(clog, 0, &node, NULL, 1038 1.10.2.2 matt CTLFLAG_PERMANENT | CTLFLAG_READWRITE, 1039 1.10.2.2 matt CTLTYPE_INT, "min_catch", 1040 1.10.2.2 matt SYSCTL_DESCR("Minimal count of the threads for catching"), 1041 1.10.2.2 matt NULL, 0, &min_catch, 0, 1042 1.10.2.2 matt CTL_CREATE, CTL_EOL); 1043 1.10.2.2 matt #endif 1044 1.10.2.2 matt } 1045 1.10.2.2 matt 1046 1.10.2.2 matt /* 1047 1.10.2.2 matt * Debugging. 1048 1.10.2.2 matt */ 1049 1.10.2.2 matt 1050 1.10.2.2 matt #ifdef DDB 1051 1.10.2.2 matt 1052 1.10.2.2 matt void 1053 1.10.2.2 matt sched_print_runqueue(void (*pr)(const char *, ...)) 1054 1.10.2.2 matt { 1055 1.10.2.2 matt runqueue_t *ci_rq; 1056 1.10.2.2 matt sched_info_lwp_t *sil; 1057 1.10.2.2 matt struct lwp *l; 1058 1.10.2.2 matt struct proc *p; 1059 1.10.2.2 matt int i; 1060 1.10.2.2 matt 1061 1.10.2.2 matt struct cpu_info *ci; 1062 1.10.2.2 matt CPU_INFO_ITERATOR cii; 1063 1.10.2.2 matt 1064 1.10.2.2 matt for (CPU_INFO_FOREACH(cii, ci)) { 1065 1.10.2.2 matt ci_rq = ci->ci_schedstate.spc_sched_info; 1066 1.10.2.2 matt 1067 1.10.2.5 matt (*pr)("Run-queue (CPU = %u):\n", ci->ci_index); 1068 1.10.2.2 matt (*pr)(" pid.lid = %d.%d, threads count = %u, " 1069 1.10.2.2 matt "avgcount = %u, highest pri = %d\n", 1070 1.10.2.2 matt ci->ci_curlwp->l_proc->p_pid, ci->ci_curlwp->l_lid, 1071 1.10.2.2 matt ci_rq->r_count, ci_rq->r_avgcount, ci_rq->r_highest_pri); 1072 1.10.2.2 matt i = (PRI_COUNT >> BITMAP_SHIFT) - 1; 1073 1.10.2.2 matt do { 1074 1.10.2.2 matt uint32_t q; 1075 1.10.2.2 matt q = ci_rq->r_bitmap[i]; 1076 1.10.2.2 matt (*pr)(" bitmap[%d] => [ %d (0x%x) ]\n", i, ffs(q), q); 1077 1.10.2.2 matt } while (i--); 1078 1.10.2.2 matt } 1079 1.10.2.2 matt 1080 1.10.2.2 matt (*pr)(" %5s %4s %4s %10s %3s %4s %11s %3s %s\n", 1081 1.10.2.2 matt "LID", "PRI", "EPRI", "FL", "ST", "TS", "LWP", "CPU", "LRTIME"); 1082 1.10.2.2 matt 1083 1.10.2.2 matt PROCLIST_FOREACH(p, &allproc) { 1084 1.10.2.2 matt (*pr)(" /- %d (%s)\n", (int)p->p_pid, p->p_comm); 1085 1.10.2.2 matt LIST_FOREACH(l, &p->p_lwps, l_sibling) { 1086 1.10.2.2 matt sil = l->l_sched_info; 1087 1.10.2.2 matt ci = l->l_cpu; 1088 1.10.2.5 matt (*pr)(" | %5d %4u %4u 0x%8.8x %3s %4u %11p %3u " 1089 1.10.2.2 matt "%u ST=%d RT=%d %d\n", 1090 1.10.2.2 matt (int)l->l_lid, l->l_priority, lwp_eprio(l), 1091 1.10.2.2 matt l->l_flag, l->l_stat == LSRUN ? "RQ" : 1092 1.10.2.2 matt (l->l_stat == LSSLEEP ? "SQ" : "-"), 1093 1.10.2.5 matt sil->sl_timeslice, l, ci->ci_index, 1094 1.10.2.2 matt (u_int)(hardclock_ticks - sil->sl_lrtime), 1095 1.10.2.2 matt sil->sl_slpsum, sil->sl_rtsum, sil->sl_flags); 1096 1.10.2.2 matt } 1097 1.10.2.2 matt } 1098 1.10.2.2 matt } 1099 1.10.2.2 matt 1100 1.10.2.5 matt #endif 1101
Indexes created Thu Oct 02 07:10:07 GMT 2025