19454b2d8SWarner Losh /*- 28a36da99SPedro F. Giffuni * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 38a36da99SPedro F. Giffuni * 4d5a08a60SJake Burkholder * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 5d5a08a60SJake Burkholder * All rights reserved. 6dba6c5a6SPeter Wemm * 7dba6c5a6SPeter Wemm * Redistribution and use in source and binary forms, with or without 8dba6c5a6SPeter Wemm * modification, are permitted provided that the following conditions 9dba6c5a6SPeter Wemm * are met: 10dba6c5a6SPeter Wemm * 1. Redistributions of source code must retain the above copyright 11dba6c5a6SPeter Wemm * notice, this list of conditions and the following disclaimer. 12dba6c5a6SPeter Wemm * 2. Redistributions in binary form must reproduce the above copyright 13dba6c5a6SPeter Wemm * notice, this list of conditions and the following disclaimer in the 14dba6c5a6SPeter Wemm * documentation and/or other materials provided with the distribution. 15dba6c5a6SPeter Wemm * 16dba6c5a6SPeter Wemm * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17dba6c5a6SPeter Wemm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18dba6c5a6SPeter Wemm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19dba6c5a6SPeter Wemm * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20dba6c5a6SPeter Wemm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21dba6c5a6SPeter Wemm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22dba6c5a6SPeter Wemm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23dba6c5a6SPeter Wemm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24dba6c5a6SPeter Wemm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25dba6c5a6SPeter Wemm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26dba6c5a6SPeter Wemm * SUCH DAMAGE. 27dba6c5a6SPeter Wemm */ 28dba6c5a6SPeter Wemm 29e602ba25SJulian Elischer 30677b542eSDavid E. O'Brien #include <sys/cdefs.h> 31677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$"); 32e602ba25SJulian Elischer 336804a3abSJulian Elischer #include "opt_sched.h" 340c0b25aeSJohn Baldwin 35dba6c5a6SPeter Wemm #include <sys/param.h> 36dba6c5a6SPeter Wemm #include <sys/systm.h> 372d50560aSMarcel Moolenaar #include <sys/kdb.h> 38dba6c5a6SPeter Wemm #include <sys/kernel.h> 390384fff8SJason Evans #include <sys/ktr.h> 40f34fa851SJohn Baldwin #include <sys/lock.h> 4135e0e5b3SJohn Baldwin #include <sys/mutex.h> 42dba6c5a6SPeter Wemm #include <sys/proc.h> 43dba6c5a6SPeter Wemm #include <sys/queue.h> 44b43179fbSJeff Roberson #include <sys/sched.h> 45cc66ebe2SPeter Wemm #include <sys/smp.h> 469727e637SJeff Roberson #include <sys/sysctl.h> 476804a3abSJulian Elischer 487b20fb19SJeff Roberson #include <machine/cpu.h> 497b20fb19SJeff Roberson 501335c4dfSNate Lawson /* Uncomment this to enable logging of critical_enter/exit. */ 511335c4dfSNate Lawson #if 0 521335c4dfSNate Lawson #define KTR_CRITICAL KTR_SCHED 531335c4dfSNate Lawson #else 541335c4dfSNate Lawson #define KTR_CRITICAL 0 551335c4dfSNate Lawson #endif 561335c4dfSNate Lawson 579923b511SScott Long #ifdef FULL_PREEMPTION 589923b511SScott Long #ifndef PREEMPTION 599923b511SScott Long #error "The FULL_PREEMPTION option requires the PREEMPTION option" 609923b511SScott Long #endif 619923b511SScott Long #endif 62dba6c5a6SPeter Wemm 63d2ac2316SJake Burkholder CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 64d2ac2316SJake Burkholder 656220dcbaSRobert Watson /* 666220dcbaSRobert Watson * kern.sched.preemption allows user space to determine if preemption support 676220dcbaSRobert Watson * is compiled in or not. It is not currently a boot or runtime flag that 686220dcbaSRobert Watson * can be changed. 696220dcbaSRobert Watson */ 706220dcbaSRobert Watson #ifdef PREEMPTION 716220dcbaSRobert Watson static int kern_sched_preemption = 1; 726220dcbaSRobert Watson #else 736220dcbaSRobert Watson static int kern_sched_preemption = 0; 746220dcbaSRobert Watson #endif 756220dcbaSRobert Watson SYSCTL_INT(_kern_sched, OID_AUTO, preemption, CTLFLAG_RD, 766220dcbaSRobert Watson &kern_sched_preemption, 0, "Kernel preemption enabled"); 776220dcbaSRobert Watson 788df78c41SJeff Roberson /* 798df78c41SJeff Roberson * Support for scheduler stats exported via kern.sched.stats. All stats may 808df78c41SJeff Roberson * be reset with kern.sched.stats.reset = 1. Stats may be defined elsewhere 818df78c41SJeff Roberson * with SCHED_STAT_DEFINE(). 828df78c41SJeff Roberson */ 837b20fb19SJeff Roberson #ifdef SCHED_STATS 848df78c41SJeff Roberson SYSCTL_NODE(_kern_sched, OID_AUTO, stats, CTLFLAG_RW, 0, "switch stats"); 85791d9a6eSJeff Roberson 86791d9a6eSJeff Roberson /* Switch reasons from mi_switch(). */ 87791d9a6eSJeff Roberson DPCPU_DEFINE(long, sched_switch_stats[SWT_COUNT]); 88791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(uncategorized, 89791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_NONE]), ""); 90791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(preempt, 91791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_PREEMPT]), ""); 92791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(owepreempt, 93791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_OWEPREEMPT]), ""); 94791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(turnstile, 95791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_TURNSTILE]), ""); 96791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(sleepq, 97791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_SLEEPQ]), ""); 98a115fb62SHans Petter Selasky SCHED_STAT_DEFINE_VAR(sleepqtimo, 99a115fb62SHans Petter Selasky &DPCPU_NAME(sched_switch_stats[SWT_SLEEPQTIMO]), ""); 100791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(relinquish, 101791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_RELINQUISH]), ""); 102791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(needresched, 103791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_NEEDRESCHED]), ""); 104791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(idle, 105791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_IDLE]), ""); 106791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(iwait, 107791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_IWAIT]), ""); 108791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(suspend, 109791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_SUSPEND]), ""); 110791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(remotepreempt, 111791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_REMOTEPREEMPT]), ""); 112791d9a6eSJeff Roberson SCHED_STAT_DEFINE_VAR(remotewakeidle, 113791d9a6eSJeff Roberson &DPCPU_NAME(sched_switch_stats[SWT_REMOTEWAKEIDLE]), ""); 1148df78c41SJeff Roberson 1157b20fb19SJeff Roberson static int 1167b20fb19SJeff Roberson sysctl_stats_reset(SYSCTL_HANDLER_ARGS) 1177b20fb19SJeff Roberson { 1188df78c41SJeff Roberson struct sysctl_oid *p; 119791d9a6eSJeff Roberson uintptr_t counter; 1207b20fb19SJeff Roberson int error; 1217b20fb19SJeff Roberson int val; 122791d9a6eSJeff Roberson int i; 1237b20fb19SJeff Roberson 1247b20fb19SJeff Roberson val = 0; 1257b20fb19SJeff Roberson error = sysctl_handle_int(oidp, &val, 0, req); 1267b20fb19SJeff Roberson if (error != 0 || req->newptr == NULL) 1277b20fb19SJeff Roberson return (error); 1287b20fb19SJeff Roberson if (val == 0) 1297b20fb19SJeff Roberson return (0); 1308df78c41SJeff Roberson /* 1318df78c41SJeff Roberson * Traverse the list of children of _kern_sched_stats and reset each 1328df78c41SJeff Roberson * to 0. Skip the reset entry. 1338df78c41SJeff Roberson */ 1348df78c41SJeff Roberson SLIST_FOREACH(p, oidp->oid_parent, oid_link) { 1358df78c41SJeff Roberson if (p == oidp || p->oid_arg1 == NULL) 1368df78c41SJeff Roberson continue; 137791d9a6eSJeff Roberson counter = (uintptr_t)p->oid_arg1; 1383aa6d94eSJohn Baldwin CPU_FOREACH(i) { 139791d9a6eSJeff Roberson *(long *)(dpcpu_off[i] + counter) = 0; 140791d9a6eSJeff Roberson } 1418df78c41SJeff Roberson } 1427b20fb19SJeff Roberson return (0); 1437b20fb19SJeff Roberson } 1447b20fb19SJeff Roberson 1457b20fb19SJeff Roberson SYSCTL_PROC(_kern_sched_stats, OID_AUTO, reset, CTLTYPE_INT | CTLFLAG_WR, NULL, 1467b20fb19SJeff Roberson 0, sysctl_stats_reset, "I", "Reset scheduler statistics"); 1477b20fb19SJeff Roberson #endif 1487b20fb19SJeff Roberson 149e602ba25SJulian Elischer /************************************************************************ 150e602ba25SJulian Elischer * Functions that manipulate runnability from a thread perspective. * 151e602ba25SJulian Elischer ************************************************************************/ 1528460a577SJohn Birrell /* 1538460a577SJohn Birrell * Select the thread that will be run next. 1548460a577SJohn Birrell */ 155e602ba25SJulian Elischer 15632aef9ffSMateusz Guzik static __noinline struct thread * 15732aef9ffSMateusz Guzik choosethread_panic(struct thread *td) 15832aef9ffSMateusz Guzik { 15993a7aa79SJulian Elischer 16093a7aa79SJulian Elischer /* 161faaa20f6SJulian Elischer * If we are in panic, only allow system threads, 162faaa20f6SJulian Elischer * plus the one we are running in, to be run. 16393a7aa79SJulian Elischer */ 16432aef9ffSMateusz Guzik retry: 16532aef9ffSMateusz Guzik if (((td->td_proc->p_flag & P_SYSTEM) == 0 && 166faaa20f6SJulian Elischer (td->td_flags & TDF_INPANIC) == 0)) { 167faaa20f6SJulian Elischer /* note that it is no longer on the run queue */ 168faaa20f6SJulian Elischer TD_SET_CAN_RUN(td); 16932aef9ffSMateusz Guzik td = sched_choose(); 170fe799533SAndrew Gallatin goto retry; 171faaa20f6SJulian Elischer } 17293a7aa79SJulian Elischer 17371fad9fdSJulian Elischer TD_SET_RUNNING(td); 174e602ba25SJulian Elischer return (td); 175e602ba25SJulian Elischer } 176e602ba25SJulian Elischer 17732aef9ffSMateusz Guzik struct thread * 17832aef9ffSMateusz Guzik choosethread(void) 17932aef9ffSMateusz Guzik { 18032aef9ffSMateusz Guzik struct thread *td; 18132aef9ffSMateusz Guzik 18232aef9ffSMateusz Guzik td = sched_choose(); 18332aef9ffSMateusz Guzik 18432aef9ffSMateusz Guzik if (__predict_false(panicstr != NULL)) 18532aef9ffSMateusz Guzik return (choosethread_panic(td)); 18632aef9ffSMateusz Guzik 18732aef9ffSMateusz Guzik TD_SET_RUNNING(td); 18832aef9ffSMateusz Guzik return (td); 18932aef9ffSMateusz Guzik } 19032aef9ffSMateusz Guzik 1910c0b25aeSJohn Baldwin /* 1920c0b25aeSJohn Baldwin * Kernel thread preemption implementation. Critical sections mark 1930c0b25aeSJohn Baldwin * regions of code in which preemptions are not allowed. 194e68ccbe8SAttilio Rao * 195e68ccbe8SAttilio Rao * It might seem a good idea to inline critical_enter() but, in order 196e68ccbe8SAttilio Rao * to prevent instructions reordering by the compiler, a __compiler_membar() 197e68ccbe8SAttilio Rao * would have to be used here (the same as sched_pin()). The performance 198e68ccbe8SAttilio Rao * penalty imposed by the membar could, then, produce slower code than 199e68ccbe8SAttilio Rao * the function call itself, for most cases. 2000c0b25aeSJohn Baldwin */ 2017e1f6dfeSJohn Baldwin void 2026443773dSMatt Macy critical_enter_KBI(void) 2037e1f6dfeSJohn Baldwin { 2046443773dSMatt Macy #ifdef KTR 2056443773dSMatt Macy struct thread *td = curthread; 2066443773dSMatt Macy #endif 2076443773dSMatt Macy critical_enter(); 2081335c4dfSNate Lawson CTR4(KTR_CRITICAL, "critical_enter by thread %p (%ld, %s) to %d", td, 209431f8906SJulian Elischer (long)td->td_proc->p_pid, td->td_name, td->td_critnest); 2107e1f6dfeSJohn Baldwin } 2117e1f6dfeSJohn Baldwin 2126443773dSMatt Macy void __noinline 213748b15fcSMateusz Guzik critical_exit_preempt(void) 2147e1f6dfeSJohn Baldwin { 2157e1f6dfeSJohn Baldwin struct thread *td; 2168df78c41SJeff Roberson int flags; 2177e1f6dfeSJohn Baldwin 2186fee84e3SMateusz Guzik /* 2196fee84e3SMateusz Guzik * If td_critnest is 0, it is possible that we are going to get 2206fee84e3SMateusz Guzik * preempted again before reaching the code below. This happens 2216fee84e3SMateusz Guzik * rarely and is harmless. However, this means td_owepreempt may 2226fee84e3SMateusz Guzik * now be unset. 2236fee84e3SMateusz Guzik */ 2247e1f6dfeSJohn Baldwin td = curthread; 225748b15fcSMateusz Guzik if (td->td_critnest != 0) 226748b15fcSMateusz Guzik return; 227748b15fcSMateusz Guzik if (kdb_active) 228748b15fcSMateusz Guzik return; 2295bce4ae3SJeff Roberson 2303467f88cSKonstantin Belousov /* 2313467f88cSKonstantin Belousov * Microoptimization: we committed to switch, 2323467f88cSKonstantin Belousov * disable preemption in interrupt handlers 2333467f88cSKonstantin Belousov * while spinning for the thread lock. 2343467f88cSKonstantin Belousov */ 23577918643SStephan Uphoff td->td_critnest = 1; 2367b20fb19SJeff Roberson thread_lock(td); 23777918643SStephan Uphoff td->td_critnest--; 2388df78c41SJeff Roberson flags = SW_INVOL | SW_PREEMPT; 2398df78c41SJeff Roberson if (TD_IS_IDLETHREAD(td)) 2408df78c41SJeff Roberson flags |= SWT_IDLE; 2418df78c41SJeff Roberson else 2428df78c41SJeff Roberson flags |= SWT_OWEPREEMPT; 243*686bcb5cSJeff Roberson mi_switch(flags); 2440c0b25aeSJohn Baldwin } 245d13ec713SStephan Uphoff 246748b15fcSMateusz Guzik void 2476443773dSMatt Macy critical_exit_KBI(void) 248748b15fcSMateusz Guzik { 2496443773dSMatt Macy #ifdef KTR 2506443773dSMatt Macy struct thread *td = curthread; 2516443773dSMatt Macy #endif 2526443773dSMatt Macy critical_exit(); 2531335c4dfSNate Lawson CTR4(KTR_CRITICAL, "critical_exit by thread %p (%ld, %s) to %d", td, 254431f8906SJulian Elischer (long)td->td_proc->p_pid, td->td_name, td->td_critnest); 255d74ac681SMatthew Dillon } 2567e1f6dfeSJohn Baldwin 257e602ba25SJulian Elischer /************************************************************************ 258e602ba25SJulian Elischer * SYSTEM RUN QUEUE manipulations and tests * 259e602ba25SJulian Elischer ************************************************************************/ 260e602ba25SJulian Elischer /* 261e602ba25SJulian Elischer * Initialize a run structure. 262e602ba25SJulian Elischer */ 263e602ba25SJulian Elischer void 264e602ba25SJulian Elischer runq_init(struct runq *rq) 265e602ba25SJulian Elischer { 266e602ba25SJulian Elischer int i; 267e602ba25SJulian Elischer 268e602ba25SJulian Elischer bzero(rq, sizeof *rq); 269e602ba25SJulian Elischer for (i = 0; i < RQ_NQS; i++) 270e602ba25SJulian Elischer TAILQ_INIT(&rq->rq_queues[i]); 271e602ba25SJulian Elischer } 272e602ba25SJulian Elischer 273d5a08a60SJake Burkholder /* 274d5a08a60SJake Burkholder * Clear the status bit of the queue corresponding to priority level pri, 275d5a08a60SJake Burkholder * indicating that it is empty. 276d5a08a60SJake Burkholder */ 277d5a08a60SJake Burkholder static __inline void 278d5a08a60SJake Burkholder runq_clrbit(struct runq *rq, int pri) 279d5a08a60SJake Burkholder { 280d5a08a60SJake Burkholder struct rqbits *rqb; 281d5a08a60SJake Burkholder 282d5a08a60SJake Burkholder rqb = &rq->rq_status; 283d5a08a60SJake Burkholder CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 284d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)], 285d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 286d5a08a60SJake Burkholder RQB_BIT(pri), RQB_WORD(pri)); 287d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 288d5a08a60SJake Burkholder } 289d5a08a60SJake Burkholder 290d5a08a60SJake Burkholder /* 291d5a08a60SJake Burkholder * Find the index of the first non-empty run queue. This is done by 292d5a08a60SJake Burkholder * scanning the status bits, a set bit indicates a non-empty queue. 293d5a08a60SJake Burkholder */ 294d5a08a60SJake Burkholder static __inline int 295d5a08a60SJake Burkholder runq_findbit(struct runq *rq) 296d5a08a60SJake Burkholder { 297d5a08a60SJake Burkholder struct rqbits *rqb; 298d5a08a60SJake Burkholder int pri; 299d5a08a60SJake Burkholder int i; 300d5a08a60SJake Burkholder 301d5a08a60SJake Burkholder rqb = &rq->rq_status; 302d5a08a60SJake Burkholder for (i = 0; i < RQB_LEN; i++) 303d5a08a60SJake Burkholder if (rqb->rqb_bits[i]) { 3042f9267ecSPeter Wemm pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 305d5a08a60SJake Burkholder CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 306d5a08a60SJake Burkholder rqb->rqb_bits[i], i, pri); 307d5a08a60SJake Burkholder return (pri); 308d5a08a60SJake Burkholder } 309d5a08a60SJake Burkholder 310d5a08a60SJake Burkholder return (-1); 311d5a08a60SJake Burkholder } 312d5a08a60SJake Burkholder 3133fed7d23SJeff Roberson static __inline int 31467e20930SJeff Roberson runq_findbit_from(struct runq *rq, u_char pri) 3153fed7d23SJeff Roberson { 3163fed7d23SJeff Roberson struct rqbits *rqb; 31767e20930SJeff Roberson rqb_word_t mask; 3183fed7d23SJeff Roberson int i; 3193fed7d23SJeff Roberson 32067e20930SJeff Roberson /* 32167e20930SJeff Roberson * Set the mask for the first word so we ignore priorities before 'pri'. 32267e20930SJeff Roberson */ 32367e20930SJeff Roberson mask = (rqb_word_t)-1 << (pri & (RQB_BPW - 1)); 3243fed7d23SJeff Roberson rqb = &rq->rq_status; 3253fed7d23SJeff Roberson again: 32667e20930SJeff Roberson for (i = RQB_WORD(pri); i < RQB_LEN; mask = -1, i++) { 32767e20930SJeff Roberson mask = rqb->rqb_bits[i] & mask; 32867e20930SJeff Roberson if (mask == 0) 3293fed7d23SJeff Roberson continue; 33067e20930SJeff Roberson pri = RQB_FFS(mask) + (i << RQB_L2BPW); 3313fed7d23SJeff Roberson CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d pri=%d", 33267e20930SJeff Roberson mask, i, pri); 3333fed7d23SJeff Roberson return (pri); 3343fed7d23SJeff Roberson } 33567e20930SJeff Roberson if (pri == 0) 3363fed7d23SJeff Roberson return (-1); 33767e20930SJeff Roberson /* 33867e20930SJeff Roberson * Wrap back around to the beginning of the list just once so we 33967e20930SJeff Roberson * scan the whole thing. 34067e20930SJeff Roberson */ 34167e20930SJeff Roberson pri = 0; 34267e20930SJeff Roberson goto again; 3433fed7d23SJeff Roberson } 3443fed7d23SJeff Roberson 345d5a08a60SJake Burkholder /* 346d5a08a60SJake Burkholder * Set the status bit of the queue corresponding to priority level pri, 347d5a08a60SJake Burkholder * indicating that it is non-empty. 348d5a08a60SJake Burkholder */ 349d5a08a60SJake Burkholder static __inline void 350d5a08a60SJake Burkholder runq_setbit(struct runq *rq, int pri) 351d5a08a60SJake Burkholder { 352d5a08a60SJake Burkholder struct rqbits *rqb; 353d5a08a60SJake Burkholder 354d5a08a60SJake Burkholder rqb = &rq->rq_status; 355d5a08a60SJake Burkholder CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 356d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)], 357d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 358d5a08a60SJake Burkholder RQB_BIT(pri), RQB_WORD(pri)); 359d5a08a60SJake Burkholder rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 360d5a08a60SJake Burkholder } 361d5a08a60SJake Burkholder 362d5a08a60SJake Burkholder /* 363ad1e7d28SJulian Elischer * Add the thread to the queue specified by its priority, and set the 364d5a08a60SJake Burkholder * corresponding status bit. 365d5a08a60SJake Burkholder */ 366d5a08a60SJake Burkholder void 3679727e637SJeff Roberson runq_add(struct runq *rq, struct thread *td, int flags) 368d5a08a60SJake Burkholder { 369d5a08a60SJake Burkholder struct rqhead *rqh; 370d5a08a60SJake Burkholder int pri; 371dba6c5a6SPeter Wemm 3729727e637SJeff Roberson pri = td->td_priority / RQ_PPQ; 3739727e637SJeff Roberson td->td_rqindex = pri; 374d5a08a60SJake Burkholder runq_setbit(rq, pri); 375d5a08a60SJake Burkholder rqh = &rq->rq_queues[pri]; 3769727e637SJeff Roberson CTR4(KTR_RUNQ, "runq_add: td=%p pri=%d %d rqh=%p", 3779727e637SJeff Roberson td, td->td_priority, pri, rqh); 378c20c691bSJulian Elischer if (flags & SRQ_PREEMPTED) { 3799727e637SJeff Roberson TAILQ_INSERT_HEAD(rqh, td, td_runq); 380c20c691bSJulian Elischer } else { 3819727e637SJeff Roberson TAILQ_INSERT_TAIL(rqh, td, td_runq); 382dba6c5a6SPeter Wemm } 383c20c691bSJulian Elischer } 384d5a08a60SJake Burkholder 3853fed7d23SJeff Roberson void 3869727e637SJeff Roberson runq_add_pri(struct runq *rq, struct thread *td, u_char pri, int flags) 3873fed7d23SJeff Roberson { 3883fed7d23SJeff Roberson struct rqhead *rqh; 3893fed7d23SJeff Roberson 3903fed7d23SJeff Roberson KASSERT(pri < RQ_NQS, ("runq_add_pri: %d out of range", pri)); 3919727e637SJeff Roberson td->td_rqindex = pri; 3923fed7d23SJeff Roberson runq_setbit(rq, pri); 3933fed7d23SJeff Roberson rqh = &rq->rq_queues[pri]; 3949727e637SJeff Roberson CTR4(KTR_RUNQ, "runq_add_pri: td=%p pri=%d idx=%d rqh=%p", 3959727e637SJeff Roberson td, td->td_priority, pri, rqh); 3963fed7d23SJeff Roberson if (flags & SRQ_PREEMPTED) { 3979727e637SJeff Roberson TAILQ_INSERT_HEAD(rqh, td, td_runq); 3983fed7d23SJeff Roberson } else { 3999727e637SJeff Roberson TAILQ_INSERT_TAIL(rqh, td, td_runq); 4003fed7d23SJeff Roberson } 4013fed7d23SJeff Roberson } 402d5a08a60SJake Burkholder /* 403d5a08a60SJake Burkholder * Return true if there are runnable processes of any priority on the run 404d5a08a60SJake Burkholder * queue, false otherwise. Has no side effects, does not modify the run 405d5a08a60SJake Burkholder * queue structure. 406d5a08a60SJake Burkholder */ 407d5a08a60SJake Burkholder int 408d5a08a60SJake Burkholder runq_check(struct runq *rq) 409d5a08a60SJake Burkholder { 410d5a08a60SJake Burkholder struct rqbits *rqb; 411d5a08a60SJake Burkholder int i; 412d5a08a60SJake Burkholder 413d5a08a60SJake Burkholder rqb = &rq->rq_status; 414d5a08a60SJake Burkholder for (i = 0; i < RQB_LEN; i++) 415d5a08a60SJake Burkholder if (rqb->rqb_bits[i]) { 416d5a08a60SJake Burkholder CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 417d5a08a60SJake Burkholder rqb->rqb_bits[i], i); 418d5a08a60SJake Burkholder return (1); 419dba6c5a6SPeter Wemm } 420d5a08a60SJake Burkholder CTR0(KTR_RUNQ, "runq_check: empty"); 421d5a08a60SJake Burkholder 422d5a08a60SJake Burkholder return (0); 423dba6c5a6SPeter Wemm } 424d5a08a60SJake Burkholder 425a90f3f25SJeff Roberson /* 426a90f3f25SJeff Roberson * Find the highest priority process on the run queue. 427a90f3f25SJeff Roberson */ 4289727e637SJeff Roberson struct thread * 429a90f3f25SJeff Roberson runq_choose_fuzz(struct runq *rq, int fuzz) 430a90f3f25SJeff Roberson { 431a90f3f25SJeff Roberson struct rqhead *rqh; 4329727e637SJeff Roberson struct thread *td; 433a90f3f25SJeff Roberson int pri; 434a90f3f25SJeff Roberson 435a90f3f25SJeff Roberson while ((pri = runq_findbit(rq)) != -1) { 436a90f3f25SJeff Roberson rqh = &rq->rq_queues[pri]; 437a90f3f25SJeff Roberson /* fuzz == 1 is normal.. 0 or less are ignored */ 438a90f3f25SJeff Roberson if (fuzz > 1) { 439a90f3f25SJeff Roberson /* 440a90f3f25SJeff Roberson * In the first couple of entries, check if 441a90f3f25SJeff Roberson * there is one for our CPU as a preference. 442a90f3f25SJeff Roberson */ 443a90f3f25SJeff Roberson int count = fuzz; 444a90f3f25SJeff Roberson int cpu = PCPU_GET(cpuid); 4459727e637SJeff Roberson struct thread *td2; 4469727e637SJeff Roberson td2 = td = TAILQ_FIRST(rqh); 447a90f3f25SJeff Roberson 4489727e637SJeff Roberson while (count-- && td2) { 449681e4062SJulian Elischer if (td2->td_lastcpu == cpu) { 4509727e637SJeff Roberson td = td2; 451a90f3f25SJeff Roberson break; 452a90f3f25SJeff Roberson } 4539727e637SJeff Roberson td2 = TAILQ_NEXT(td2, td_runq); 454a90f3f25SJeff Roberson } 455a90f3f25SJeff Roberson } else 4569727e637SJeff Roberson td = TAILQ_FIRST(rqh); 4579727e637SJeff Roberson KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy queue")); 458a90f3f25SJeff Roberson CTR3(KTR_RUNQ, 4599727e637SJeff Roberson "runq_choose_fuzz: pri=%d thread=%p rqh=%p", pri, td, rqh); 4609727e637SJeff Roberson return (td); 461a90f3f25SJeff Roberson } 462a90f3f25SJeff Roberson CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc pri=%d", pri); 463a90f3f25SJeff Roberson 464a90f3f25SJeff Roberson return (NULL); 465a90f3f25SJeff Roberson } 4666804a3abSJulian Elischer 467d5a08a60SJake Burkholder /* 468b43179fbSJeff Roberson * Find the highest priority process on the run queue. 469d5a08a60SJake Burkholder */ 4709727e637SJeff Roberson struct thread * 471d5a08a60SJake Burkholder runq_choose(struct runq *rq) 472d5a08a60SJake Burkholder { 473d5a08a60SJake Burkholder struct rqhead *rqh; 4749727e637SJeff Roberson struct thread *td; 475d5a08a60SJake Burkholder int pri; 476d5a08a60SJake Burkholder 477e602ba25SJulian Elischer while ((pri = runq_findbit(rq)) != -1) { 478d5a08a60SJake Burkholder rqh = &rq->rq_queues[pri]; 4799727e637SJeff Roberson td = TAILQ_FIRST(rqh); 4809727e637SJeff Roberson KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); 481e602ba25SJulian Elischer CTR3(KTR_RUNQ, 4829727e637SJeff Roberson "runq_choose: pri=%d thread=%p rqh=%p", pri, td, rqh); 4839727e637SJeff Roberson return (td); 484d5a08a60SJake Burkholder } 4859727e637SJeff Roberson CTR1(KTR_RUNQ, "runq_choose: idlethread pri=%d", pri); 486d5a08a60SJake Burkholder 487e602ba25SJulian Elischer return (NULL); 488d5a08a60SJake Burkholder } 489d5a08a60SJake Burkholder 4909727e637SJeff Roberson struct thread * 491ed0e8f2fSJeff Roberson runq_choose_from(struct runq *rq, u_char idx) 4923fed7d23SJeff Roberson { 4933fed7d23SJeff Roberson struct rqhead *rqh; 4949727e637SJeff Roberson struct thread *td; 4953fed7d23SJeff Roberson int pri; 4963fed7d23SJeff Roberson 497cd49bb70SJeff Roberson if ((pri = runq_findbit_from(rq, idx)) != -1) { 4983fed7d23SJeff Roberson rqh = &rq->rq_queues[pri]; 4999727e637SJeff Roberson td = TAILQ_FIRST(rqh); 5009727e637SJeff Roberson KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); 5013fed7d23SJeff Roberson CTR4(KTR_RUNQ, 5029727e637SJeff Roberson "runq_choose_from: pri=%d thread=%p idx=%d rqh=%p", 5039727e637SJeff Roberson pri, td, td->td_rqindex, rqh); 5049727e637SJeff Roberson return (td); 5053fed7d23SJeff Roberson } 5069727e637SJeff Roberson CTR1(KTR_RUNQ, "runq_choose_from: idlethread pri=%d", pri); 5073fed7d23SJeff Roberson 5083fed7d23SJeff Roberson return (NULL); 5093fed7d23SJeff Roberson } 510d5a08a60SJake Burkholder /* 511ad1e7d28SJulian Elischer * Remove the thread from the queue specified by its priority, and clear the 512d5a08a60SJake Burkholder * corresponding status bit if the queue becomes empty. 513f0393f06SJeff Roberson * Caller must set state afterwards. 514d5a08a60SJake Burkholder */ 515d5a08a60SJake Burkholder void 5169727e637SJeff Roberson runq_remove(struct runq *rq, struct thread *td) 517d5a08a60SJake Burkholder { 5183fed7d23SJeff Roberson 5199727e637SJeff Roberson runq_remove_idx(rq, td, NULL); 5203fed7d23SJeff Roberson } 5213fed7d23SJeff Roberson 5223fed7d23SJeff Roberson void 5239727e637SJeff Roberson runq_remove_idx(struct runq *rq, struct thread *td, u_char *idx) 5243fed7d23SJeff Roberson { 525d5a08a60SJake Burkholder struct rqhead *rqh; 526ed0e8f2fSJeff Roberson u_char pri; 527d5a08a60SJake Burkholder 5289727e637SJeff Roberson KASSERT(td->td_flags & TDF_INMEM, 529b61ce5b0SJeff Roberson ("runq_remove_idx: thread swapped out")); 5309727e637SJeff Roberson pri = td->td_rqindex; 5317b20fb19SJeff Roberson KASSERT(pri < RQ_NQS, ("runq_remove_idx: Invalid index %d\n", pri)); 532d5a08a60SJake Burkholder rqh = &rq->rq_queues[pri]; 5339727e637SJeff Roberson CTR4(KTR_RUNQ, "runq_remove_idx: td=%p, pri=%d %d rqh=%p", 5349727e637SJeff Roberson td, td->td_priority, pri, rqh); 5359727e637SJeff Roberson TAILQ_REMOVE(rqh, td, td_runq); 536d5a08a60SJake Burkholder if (TAILQ_EMPTY(rqh)) { 5373fed7d23SJeff Roberson CTR0(KTR_RUNQ, "runq_remove_idx: empty"); 538d5a08a60SJake Burkholder runq_clrbit(rq, pri); 5393fed7d23SJeff Roberson if (idx != NULL && *idx == pri) 5403fed7d23SJeff Roberson *idx = (pri + 1) % RQ_NQS; 541d5a08a60SJake Burkholder } 542dba6c5a6SPeter Wemm } 543