1 /* 2 * Copyright (c) 2012 The DragonFly Project. All rights reserved. 3 * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>. All rights reserved. 4 * 5 * This code is derived from software contributed to The DragonFly Project 6 * by Matthew Dillon <dillon@backplane.com>, 7 * by Mihai Carabas <mihai.carabas@gmail.com> 8 * and many others. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 #include <sys/param.h> 33 #include <sys/systm.h> 34 #include <sys/kernel.h> 35 #include <sys/lock.h> 36 #include <sys/queue.h> 37 #include <sys/proc.h> 38 #include <sys/rtprio.h> 39 #include <sys/uio.h> 40 #include <sys/sysctl.h> 41 #include <sys/resourcevar.h> 42 #include <sys/spinlock.h> 43 #include <sys/cpu_topology.h> 44 #include <sys/thread2.h> 45 #include <sys/spinlock2.h> 46 47 #include <sys/ktr.h> 48 49 #include <machine/cpu.h> 50 #include <machine/smp.h> 51 52 /* 53 * Priorities. Note that with 32 run queues per scheduler each queue 54 * represents four priority levels. 55 */ 56 57 #define MAXPRI 128 58 #define PRIMASK (MAXPRI - 1) 59 #define PRIBASE_REALTIME 0 60 #define PRIBASE_NORMAL MAXPRI 61 #define PRIBASE_IDLE (MAXPRI * 2) 62 #define PRIBASE_THREAD (MAXPRI * 3) 63 #define PRIBASE_NULL (MAXPRI * 4) 64 65 #define NQS 32 /* 32 run queues. */ 66 #define PPQ (MAXPRI / NQS) /* priorities per queue */ 67 #define PPQMASK (PPQ - 1) 68 69 /* 70 * NICEPPQ - number of nice units per priority queue 71 * 72 * ESTCPUPPQ - number of estcpu units per priority queue 73 * ESTCPUMAX - number of estcpu units 74 */ 75 #define NICEPPQ 2 76 #define ESTCPUPPQ 512 77 #define ESTCPUMAX (ESTCPUPPQ * NQS) 78 #define BATCHMAX (ESTCPUFREQ * 30) 79 #define PRIO_RANGE (PRIO_MAX - PRIO_MIN + 1) 80 81 #define ESTCPULIM(v) min((v), ESTCPUMAX) 82 83 TAILQ_HEAD(rq, lwp); 84 85 #define lwp_priority lwp_usdata.bsd4.priority 86 #define lwp_rqindex lwp_usdata.bsd4.rqindex 87 #define lwp_estcpu lwp_usdata.bsd4.estcpu 88 #define lwp_batch lwp_usdata.bsd4.batch 89 #define lwp_rqtype lwp_usdata.bsd4.rqtype 90 91 static void bsd4_acquire_curproc(struct lwp *lp); 92 static void bsd4_release_curproc(struct lwp *lp); 93 static void bsd4_select_curproc(globaldata_t gd); 94 static void bsd4_setrunqueue(struct lwp *lp); 95 static void bsd4_schedulerclock(struct lwp *lp, sysclock_t period, 96 sysclock_t cpstamp); 97 static void bsd4_recalculate_estcpu(struct lwp *lp); 98 static void bsd4_resetpriority(struct lwp *lp); 99 static void bsd4_forking(struct lwp *plp, struct lwp *lp); 100 static void bsd4_exiting(struct lwp *lp, struct proc *); 101 static void bsd4_uload_update(struct lwp *lp); 102 static void bsd4_yield(struct lwp *lp); 103 static void bsd4_need_user_resched_remote(void *dummy); 104 static int bsd4_batchy_looser_pri_test(struct lwp* lp); 105 static struct lwp *bsd4_chooseproc_locked_cache_coherent(struct lwp *chklp); 106 static void bsd4_kick_helper(struct lwp *lp); 107 static struct lwp *bsd4_chooseproc_locked(struct lwp *chklp); 108 static void bsd4_remrunqueue_locked(struct lwp *lp); 109 static void bsd4_setrunqueue_locked(struct lwp *lp); 110 static void bsd4_changedcpu(struct lwp *lp); 111 112 struct usched usched_bsd4 = { 113 { NULL }, 114 "bsd4", "Original DragonFly Scheduler", 115 NULL, /* default registration */ 116 NULL, /* default deregistration */ 117 bsd4_acquire_curproc, 118 bsd4_release_curproc, 119 bsd4_setrunqueue, 120 bsd4_schedulerclock, 121 bsd4_recalculate_estcpu, 122 bsd4_resetpriority, 123 bsd4_forking, 124 bsd4_exiting, 125 bsd4_uload_update, 126 NULL, /* setcpumask not supported */ 127 bsd4_yield, 128 bsd4_changedcpu 129 }; 130 131 struct usched_bsd4_pcpu { 132 struct thread *helper_thread; 133 short rrcount; 134 short upri; 135 struct lwp *uschedcp; 136 struct lwp *old_uschedcp; 137 cpu_node_t *cpunode; 138 }; 139 140 typedef struct usched_bsd4_pcpu *bsd4_pcpu_t; 141 142 /* 143 * We have NQS (32) run queues per scheduling class. For the normal 144 * class, there are 128 priorities scaled onto these 32 queues. New 145 * processes are added to the last entry in each queue, and processes 146 * are selected for running by taking them from the head and maintaining 147 * a simple FIFO arrangement. Realtime and Idle priority processes have 148 * and explicit 0-31 priority which maps directly onto their class queue 149 * index. When a queue has something in it, the corresponding bit is 150 * set in the queuebits variable, allowing a single read to determine 151 * the state of all 32 queues and then a ffs() to find the first busy 152 * queue. 153 */ 154 static struct rq bsd4_queues[NQS]; 155 static struct rq bsd4_rtqueues[NQS]; 156 static struct rq bsd4_idqueues[NQS]; 157 static u_int32_t bsd4_queuebits; 158 static u_int32_t bsd4_rtqueuebits; 159 static u_int32_t bsd4_idqueuebits; 160 /* currently running a user process */ 161 static cpumask_t bsd4_curprocmask = CPUMASK_INITIALIZER_ALLONES; 162 /* ready to accept a user process */ 163 static cpumask_t bsd4_rdyprocmask; 164 static int bsd4_runqcount; 165 static volatile int bsd4_scancpu; 166 static struct spinlock bsd4_spin; 167 static struct usched_bsd4_pcpu bsd4_pcpu[MAXCPU]; 168 static struct sysctl_ctx_list usched_bsd4_sysctl_ctx; 169 static struct sysctl_oid *usched_bsd4_sysctl_tree; 170 171 /* Debug info exposed through debug.* sysctl */ 172 173 SYSCTL_INT(_debug, OID_AUTO, bsd4_runqcount, CTLFLAG_RD, 174 &bsd4_runqcount, 0, 175 "Number of run queues"); 176 177 static int usched_bsd4_debug = -1; 178 SYSCTL_INT(_debug, OID_AUTO, bsd4_scdebug, CTLFLAG_RW, 179 &usched_bsd4_debug, 0, 180 "Print debug information for this pid"); 181 182 static int usched_bsd4_pid_debug = -1; 183 SYSCTL_INT(_debug, OID_AUTO, bsd4_pid_debug, CTLFLAG_RW, 184 &usched_bsd4_pid_debug, 0, 185 "Print KTR debug information for this pid"); 186 187 /* Tunning usched_bsd4 - configurable through kern.usched_bsd4.* */ 188 static int usched_bsd4_smt = 0; 189 static int usched_bsd4_cache_coherent = 0; 190 static int usched_bsd4_upri_affinity = 16; /* 32 queues - half-way */ 191 static int usched_bsd4_queue_checks = 5; 192 static int usched_bsd4_stick_to_level = 0; 193 static long usched_bsd4_kicks; 194 static int usched_bsd4_rrinterval = (ESTCPUFREQ + 9) / 10; 195 static int usched_bsd4_decay = 8; 196 static int usched_bsd4_batch_time = 10; 197 198 /* KTR debug printings */ 199 200 KTR_INFO_MASTER_EXTERN(usched); 201 202 #if !defined(KTR_USCHED_BSD4) 203 #define KTR_USCHED_BSD4 KTR_ALL 204 #endif 205 206 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_acquire_curproc_urw, 0, 207 "USCHED_BSD4(bsd4_acquire_curproc in user_reseched_wanted " 208 "after release: pid %d, cpuid %d, curr_cpuid %d)", 209 pid_t pid, int cpuid, int curr); 210 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_acquire_curproc_before_loop, 0, 211 "USCHED_BSD4(bsd4_acquire_curproc before loop: pid %d, cpuid %d, " 212 "curr_cpuid %d)", 213 pid_t pid, int cpuid, int curr); 214 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_acquire_curproc_not, 0, 215 "USCHED_BSD4(bsd4_acquire_curproc couldn't acquire after " 216 "bsd4_setrunqueue: pid %d, cpuid %d, curr_lp pid %d, curr_cpuid %d)", 217 pid_t pid, int cpuid, pid_t curr_pid, int curr_cpuid); 218 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_acquire_curproc_switch, 0, 219 "USCHED_BSD4(bsd4_acquire_curproc after lwkt_switch: pid %d, " 220 "cpuid %d, curr_cpuid %d)", 221 pid_t pid, int cpuid, int curr); 222 223 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_release_curproc, 0, 224 "USCHED_BSD4(bsd4_release_curproc before select: pid %d, " 225 "cpuid %d, curr_cpuid %d)", 226 pid_t pid, int cpuid, int curr); 227 228 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_select_curproc, 0, 229 "USCHED_BSD4(bsd4_release_curproc before select: pid %d, " 230 "cpuid %d, old_pid %d, old_cpuid %d, curr_cpuid %d)", 231 pid_t pid, int cpuid, pid_t old_pid, int old_cpuid, int curr); 232 233 KTR_INFO(KTR_USCHED_BSD4, usched, batchy_test_false, 0, 234 "USCHED_BSD4(batchy_looser_pri_test false: pid %d, " 235 "cpuid %d, verify_mask %lu)", 236 pid_t pid, int cpuid, unsigned long mask); 237 KTR_INFO(KTR_USCHED_BSD4, usched, batchy_test_true, 0, 238 "USCHED_BSD4(batchy_looser_pri_test true: pid %d, " 239 "cpuid %d, verify_mask %lu)", 240 pid_t pid, int cpuid, unsigned long mask); 241 242 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_fc_smt, 0, 243 "USCHED_BSD4(bsd4_setrunqueue free cpus smt: pid %d, cpuid %d, " 244 "mask %lu, curr_cpuid %d)", 245 pid_t pid, int cpuid, unsigned long mask, int curr); 246 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_fc_non_smt, 0, 247 "USCHED_BSD4(bsd4_setrunqueue free cpus check non_smt: pid %d, " 248 "cpuid %d, mask %lu, curr_cpuid %d)", 249 pid_t pid, int cpuid, unsigned long mask, int curr); 250 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_rc, 0, 251 "USCHED_BSD4(bsd4_setrunqueue running cpus check: pid %d, " 252 "cpuid %d, mask %lu, curr_cpuid %d)", 253 pid_t pid, int cpuid, unsigned long mask, int curr); 254 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_found, 0, 255 "USCHED_BSD4(bsd4_setrunqueue found cpu: pid %d, cpuid %d, " 256 "mask %lu, found_cpuid %d, curr_cpuid %d)", 257 pid_t pid, int cpuid, unsigned long mask, int found_cpuid, int curr); 258 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_not_found, 0, 259 "USCHED_BSD4(bsd4_setrunqueue not found cpu: pid %d, cpuid %d, " 260 "try_cpuid %d, curr_cpuid %d)", 261 pid_t pid, int cpuid, int try_cpuid, int curr); 262 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_setrunqueue_found_best_cpuid, 0, 263 "USCHED_BSD4(bsd4_setrunqueue found cpu: pid %d, cpuid %d, " 264 "mask %lu, found_cpuid %d, curr_cpuid %d)", 265 pid_t pid, int cpuid, unsigned long mask, int found_cpuid, int curr); 266 267 KTR_INFO(KTR_USCHED_BSD4, usched, bsd4_chooseproc, 0, 268 "USCHED_BSD4(chooseproc: pid %d, old_cpuid %d, curr_cpuid %d)", 269 pid_t pid, int old_cpuid, int curr); 270 KTR_INFO(KTR_USCHED_BSD4, usched, chooseproc_cc, 0, 271 "USCHED_BSD4(chooseproc_cc: pid %d, old_cpuid %d, curr_cpuid %d)", 272 pid_t pid, int old_cpuid, int curr); 273 KTR_INFO(KTR_USCHED_BSD4, usched, chooseproc_cc_not_good, 0, 274 "USCHED_BSD4(chooseproc_cc not good: pid %d, old_cpumask %lu, " 275 "sibling_mask %lu, curr_cpumask %lu)", 276 pid_t pid, unsigned long old_cpumask, unsigned long sibling_mask, unsigned long curr); 277 KTR_INFO(KTR_USCHED_BSD4, usched, chooseproc_cc_elected, 0, 278 "USCHED_BSD4(chooseproc_cc elected: pid %d, old_cpumask %lu, " 279 "sibling_mask %lu, curr_cpumask: %lu)", 280 pid_t pid, unsigned long old_cpumask, unsigned long sibling_mask, unsigned long curr); 281 282 KTR_INFO(KTR_USCHED_BSD4, usched, sched_thread_no_process, 0, 283 "USCHED_BSD4(sched_thread %d no process scheduled: pid %d, old_cpuid %d)", 284 int id, pid_t pid, int cpuid); 285 KTR_INFO(KTR_USCHED_BSD4, usched, sched_thread_process, 0, 286 "USCHED_BSD4(sched_thread %d process scheduled: pid %d, old_cpuid %d)", 287 int id, pid_t pid, int cpuid); 288 KTR_INFO(KTR_USCHED_BSD4, usched, sched_thread_no_process_found, 0, 289 "USCHED_BSD4(sched_thread %d no process found; tmpmask %lu)", 290 int id, unsigned long tmpmask); 291 292 /* 293 * Initialize the run queues at boot time. 294 */ 295 static void 296 bsd4_rqinit(void *dummy) 297 { 298 int i; 299 300 spin_init(&bsd4_spin, "bsd4rq"); 301 for (i = 0; i < NQS; i++) { 302 TAILQ_INIT(&bsd4_queues[i]); 303 TAILQ_INIT(&bsd4_rtqueues[i]); 304 TAILQ_INIT(&bsd4_idqueues[i]); 305 } 306 ATOMIC_CPUMASK_NANDBIT(bsd4_curprocmask, 0); 307 } 308 SYSINIT(runqueue, SI_BOOT2_USCHED, SI_ORDER_FIRST, bsd4_rqinit, NULL); 309 310 /* 311 * BSD4_ACQUIRE_CURPROC 312 * 313 * This function is called when the kernel intends to return to userland. 314 * It is responsible for making the thread the current designated userland 315 * thread for this cpu, blocking if necessary. 316 * 317 * The kernel will not depress our LWKT priority until after we return, 318 * in case we have to shove over to another cpu. 319 * 320 * We must determine our thread's disposition before we switch away. This 321 * is very sensitive code. 322 * 323 * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE 324 * TO ANOTHER CPU! Because most of the kernel assumes that no migration will 325 * occur, this function is called only under very controlled circumstances. 326 * 327 * MPSAFE 328 */ 329 static void 330 bsd4_acquire_curproc(struct lwp *lp) 331 { 332 globaldata_t gd; 333 bsd4_pcpu_t dd; 334 thread_t td; 335 #if 0 336 struct lwp *olp; 337 #endif 338 339 /* 340 * Make sure we aren't sitting on a tsleep queue. 341 */ 342 td = lp->lwp_thread; 343 crit_enter_quick(td); 344 if (td->td_flags & TDF_TSLEEPQ) 345 tsleep_remove(td); 346 bsd4_recalculate_estcpu(lp); 347 348 /* 349 * If a reschedule was requested give another thread the 350 * driver's seat. 351 */ 352 if (user_resched_wanted()) { 353 clear_user_resched(); 354 bsd4_release_curproc(lp); 355 356 KTR_COND_LOG(usched_bsd4_acquire_curproc_urw, 357 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 358 lp->lwp_proc->p_pid, 359 lp->lwp_thread->td_gd->gd_cpuid, 360 mycpu->gd_cpuid); 361 } 362 363 /* 364 * Loop until we are the current user thread 365 */ 366 gd = mycpu; 367 dd = &bsd4_pcpu[gd->gd_cpuid]; 368 369 KTR_COND_LOG(usched_bsd4_acquire_curproc_before_loop, 370 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 371 lp->lwp_proc->p_pid, 372 lp->lwp_thread->td_gd->gd_cpuid, 373 gd->gd_cpuid); 374 375 do { 376 /* 377 * Process any pending events and higher priority threads. 378 */ 379 lwkt_yield(); 380 381 /* This lwp is an outcast; force reschedule. */ 382 if (__predict_false( 383 CPUMASK_TESTBIT(lp->lwp_cpumask, gd->gd_cpuid) == 0)) { 384 bsd4_release_curproc(lp); 385 goto resched; 386 } 387 388 /* 389 * Become the currently scheduled user thread for this cpu 390 * if we can do so trivially. 391 * 392 * We can steal another thread's current thread designation 393 * on this cpu since if we are running that other thread 394 * must not be, so we can safely deschedule it. 395 */ 396 if (dd->uschedcp == lp) { 397 /* 398 * We are already the current lwp (hot path). 399 */ 400 dd->upri = lp->lwp_priority; 401 } else if (dd->uschedcp == NULL) { 402 /* 403 * We can trivially become the current lwp. 404 */ 405 ATOMIC_CPUMASK_ORBIT(bsd4_curprocmask, gd->gd_cpuid); 406 dd->uschedcp = lp; 407 dd->upri = lp->lwp_priority; 408 } else if (dd->upri > lp->lwp_priority) { 409 /* 410 * We can steal the current cpu's lwp designation 411 * away simply by replacing it. The other thread 412 * will stall when it tries to return to userland. 413 */ 414 dd->uschedcp = lp; 415 dd->upri = lp->lwp_priority; 416 /* 417 lwkt_deschedule(olp->lwp_thread); 418 bsd4_setrunqueue(olp); 419 */ 420 } else { 421 resched: 422 /* 423 * We cannot become the current lwp, place the lp 424 * on the bsd4 run-queue and deschedule ourselves. 425 * 426 * When we are reactivated we will have another 427 * chance. 428 */ 429 lwkt_deschedule(lp->lwp_thread); 430 431 bsd4_setrunqueue(lp); 432 433 KTR_COND_LOG(usched_bsd4_acquire_curproc_not, 434 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 435 lp->lwp_proc->p_pid, 436 lp->lwp_thread->td_gd->gd_cpuid, 437 dd->uschedcp->lwp_proc->p_pid, 438 gd->gd_cpuid); 439 440 441 lwkt_switch(); 442 443 /* 444 * Reload after a switch or setrunqueue/switch possibly 445 * moved us to another cpu. 446 */ 447 gd = mycpu; 448 dd = &bsd4_pcpu[gd->gd_cpuid]; 449 450 KTR_COND_LOG(usched_bsd4_acquire_curproc_switch, 451 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 452 lp->lwp_proc->p_pid, 453 lp->lwp_thread->td_gd->gd_cpuid, 454 gd->gd_cpuid); 455 } 456 } while (dd->uschedcp != lp); 457 458 crit_exit_quick(td); 459 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 460 } 461 462 /* 463 * BSD4_RELEASE_CURPROC 464 * 465 * This routine detaches the current thread from the userland scheduler, 466 * usually because the thread needs to run or block in the kernel (at 467 * kernel priority) for a while. 468 * 469 * This routine is also responsible for selecting a new thread to 470 * make the current thread. 471 * 472 * NOTE: This implementation differs from the dummy example in that 473 * bsd4_select_curproc() is able to select the current process, whereas 474 * dummy_select_curproc() is not able to select the current process. 475 * This means we have to NULL out uschedcp. 476 * 477 * Additionally, note that we may already be on a run queue if releasing 478 * via the lwkt_switch() in bsd4_setrunqueue(). 479 * 480 * MPSAFE 481 */ 482 483 static void 484 bsd4_release_curproc(struct lwp *lp) 485 { 486 globaldata_t gd = mycpu; 487 bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid]; 488 489 if (dd->uschedcp == lp) { 490 crit_enter(); 491 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 492 493 KTR_COND_LOG(usched_bsd4_release_curproc, 494 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 495 lp->lwp_proc->p_pid, 496 lp->lwp_thread->td_gd->gd_cpuid, 497 gd->gd_cpuid); 498 499 dd->uschedcp = NULL; /* don't let lp be selected */ 500 dd->upri = PRIBASE_NULL; 501 ATOMIC_CPUMASK_NANDBIT(bsd4_curprocmask, gd->gd_cpuid); 502 dd->old_uschedcp = lp; /* used only for KTR debug prints */ 503 bsd4_select_curproc(gd); 504 crit_exit(); 505 } 506 } 507 508 /* 509 * BSD4_SELECT_CURPROC 510 * 511 * Select a new current process for this cpu and clear any pending user 512 * reschedule request. The cpu currently has no current process. 513 * 514 * This routine is also responsible for equal-priority round-robining, 515 * typically triggered from bsd4_schedulerclock(). In our dummy example 516 * all the 'user' threads are LWKT scheduled all at once and we just 517 * call lwkt_switch(). 518 * 519 * The calling process is not on the queue and cannot be selected. 520 * 521 * MPSAFE 522 */ 523 static 524 void 525 bsd4_select_curproc(globaldata_t gd) 526 { 527 bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid]; 528 struct lwp *nlp; 529 int cpuid = gd->gd_cpuid; 530 531 crit_enter_gd(gd); 532 533 spin_lock(&bsd4_spin); 534 if(usched_bsd4_cache_coherent) 535 nlp = bsd4_chooseproc_locked_cache_coherent(dd->uschedcp); 536 else 537 nlp = bsd4_chooseproc_locked(dd->uschedcp); 538 539 if (nlp) { 540 541 KTR_COND_LOG(usched_bsd4_select_curproc, 542 nlp->lwp_proc->p_pid == usched_bsd4_pid_debug, 543 nlp->lwp_proc->p_pid, 544 nlp->lwp_thread->td_gd->gd_cpuid, 545 dd->old_uschedcp->lwp_proc->p_pid, 546 dd->old_uschedcp->lwp_thread->td_gd->gd_cpuid, 547 gd->gd_cpuid); 548 549 ATOMIC_CPUMASK_ORBIT(bsd4_curprocmask, cpuid); 550 dd->upri = nlp->lwp_priority; 551 dd->uschedcp = nlp; 552 dd->rrcount = 0; /* reset round robin */ 553 spin_unlock(&bsd4_spin); 554 lwkt_acquire(nlp->lwp_thread); 555 lwkt_schedule(nlp->lwp_thread); 556 } else { 557 spin_unlock(&bsd4_spin); 558 } 559 560 #if 0 561 } else if (bsd4_runqcount && CPUMASK_TESTBIT(bsd4_rdyprocmask, cpuid)) { 562 ATOMIC_CPUMASK_NANDBIT(bsd4_rdyprocmask, cpuid); 563 spin_unlock(&bsd4_spin); 564 lwkt_schedule(dd->helper_thread); 565 } else { 566 spin_unlock(&bsd4_spin); 567 } 568 #endif 569 crit_exit_gd(gd); 570 } 571 572 /* 573 * batchy_looser_pri_test() - determine if a process is batchy or not 574 * relative to the other processes running in the system 575 */ 576 static int 577 bsd4_batchy_looser_pri_test(struct lwp* lp) 578 { 579 cpumask_t mask; 580 bsd4_pcpu_t other_dd; 581 int cpu; 582 583 /* Current running processes */ 584 mask = bsd4_curprocmask; 585 CPUMASK_ANDMASK(mask, smp_active_mask); 586 CPUMASK_ANDMASK(mask, usched_global_cpumask); 587 588 while (CPUMASK_TESTNZERO(mask)) { 589 cpu = BSFCPUMASK(mask); 590 other_dd = &bsd4_pcpu[cpu]; 591 if (other_dd->upri - lp->lwp_priority > usched_bsd4_upri_affinity * PPQ) { 592 593 KTR_COND_LOG(usched_batchy_test_false, 594 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 595 lp->lwp_proc->p_pid, 596 lp->lwp_thread->td_gd->gd_cpuid, 597 (unsigned long)CPUMASK_LOWMASK(mask)); 598 599 return 0; 600 } 601 CPUMASK_NANDBIT(mask, cpu); 602 } 603 604 KTR_COND_LOG(usched_batchy_test_true, 605 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 606 lp->lwp_proc->p_pid, 607 lp->lwp_thread->td_gd->gd_cpuid, 608 (unsigned long)CPUMASK_LOWMASK(mask)); 609 610 return 1; 611 } 612 613 /* 614 * 615 * BSD4_SETRUNQUEUE 616 * 617 * Place the specified lwp on the user scheduler's run queue. This routine 618 * must be called with the thread descheduled. The lwp must be runnable. 619 * 620 * The thread may be the current thread as a special case. 621 * 622 * MPSAFE 623 */ 624 static void 625 bsd4_setrunqueue(struct lwp *lp) 626 { 627 globaldata_t gd; 628 bsd4_pcpu_t dd; 629 int cpuid; 630 cpumask_t mask; 631 cpumask_t tmpmask; 632 633 /* 634 * First validate the process state relative to the current cpu. 635 * We don't need the spinlock for this, just a critical section. 636 * We are in control of the process. 637 */ 638 crit_enter(); 639 KASSERT(lp->lwp_stat == LSRUN, ("setrunqueue: lwp not LSRUN")); 640 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0, 641 ("lwp %d/%d already on runq! flag %08x/%08x", lp->lwp_proc->p_pid, 642 lp->lwp_tid, lp->lwp_proc->p_flags, lp->lwp_flags)); 643 KKASSERT((lp->lwp_thread->td_flags & TDF_RUNQ) == 0); 644 645 /* 646 * Note: gd and dd are relative to the target thread's last cpu, 647 * NOT our current cpu. 648 */ 649 gd = lp->lwp_thread->td_gd; 650 dd = &bsd4_pcpu[gd->gd_cpuid]; 651 652 /* 653 * This process is not supposed to be scheduled anywhere or assigned 654 * as the current process anywhere. Assert the condition. 655 */ 656 KKASSERT(dd->uschedcp != lp); 657 658 /* 659 * XXX fixme. Could be part of a remrunqueue/setrunqueue 660 * operation when the priority is recalculated, so TDF_MIGRATING 661 * may already be set. 662 */ 663 if ((lp->lwp_thread->td_flags & TDF_MIGRATING) == 0) 664 lwkt_giveaway(lp->lwp_thread); 665 666 /* 667 * We lose control of lp the moment we release the spinlock after 668 * having placed lp on the queue. i.e. another cpu could pick it 669 * up and it could exit, or its priority could be further adjusted, 670 * or something like that. 671 */ 672 spin_lock(&bsd4_spin); 673 bsd4_setrunqueue_locked(lp); 674 lp->lwp_rebal_ticks = sched_ticks; 675 676 /* 677 * Kick the scheduler helper on one of the other cpu's 678 * and request a reschedule if appropriate. 679 * 680 * NOTE: We check all cpus whos rdyprocmask is set. First we 681 * look for cpus without designated lps, then we look for 682 * cpus with designated lps with a worse priority than our 683 * process. 684 */ 685 ++bsd4_scancpu; 686 687 if (usched_bsd4_smt) { 688 689 /* 690 * SMT heuristic - Try to schedule on a free physical core. 691 * If no physical core found than choose the one that has 692 * an interactive thread. 693 */ 694 695 int best_cpuid = -1; 696 int min_prio = MAXPRI * MAXPRI; 697 int sibling; 698 699 cpuid = (bsd4_scancpu & 0xFFFF) % ncpus; 700 mask = bsd4_rdyprocmask; 701 CPUMASK_NANDMASK(mask, bsd4_curprocmask); 702 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 703 CPUMASK_ANDMASK(mask, smp_active_mask); 704 CPUMASK_ANDMASK(mask, usched_global_cpumask); 705 706 KTR_COND_LOG(usched_bsd4_setrunqueue_fc_smt, 707 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 708 lp->lwp_proc->p_pid, 709 lp->lwp_thread->td_gd->gd_cpuid, 710 (unsigned long)CPUMASK_LOWMASK(mask), 711 mycpu->gd_cpuid); 712 713 while (CPUMASK_TESTNZERO(mask)) { 714 CPUMASK_ASSNBMASK(tmpmask, cpuid); 715 if (CPUMASK_TESTMASK(tmpmask, mask)) { 716 CPUMASK_ANDMASK(tmpmask, mask); 717 cpuid = BSFCPUMASK(tmpmask); 718 } else { 719 cpuid = BSFCPUMASK(mask); 720 } 721 gd = globaldata_find(cpuid); 722 dd = &bsd4_pcpu[cpuid]; 723 724 if ((dd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK)) { 725 tmpmask = dd->cpunode->parent_node->members; 726 CPUMASK_NANDMASK(tmpmask, dd->cpunode->members); 727 CPUMASK_ANDMASK(tmpmask, mask); 728 if (CPUMASK_TESTNZERO(tmpmask)) { 729 KTR_COND_LOG(usched_bsd4_setrunqueue_found, 730 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 731 lp->lwp_proc->p_pid, 732 lp->lwp_thread->td_gd->gd_cpuid, 733 (unsigned long)CPUMASK_LOWMASK(mask), 734 cpuid, 735 mycpu->gd_cpuid); 736 737 goto found; 738 } else { 739 tmpmask = 740 dd->cpunode->parent_node->members; 741 CPUMASK_NANDMASK(tmpmask, 742 dd->cpunode->members); 743 sibling = BSFCPUMASK(tmpmask); 744 if (min_prio > 745 bsd4_pcpu[sibling].upri) { 746 min_prio = 747 bsd4_pcpu[sibling].upri; 748 best_cpuid = cpuid; 749 } 750 } 751 } 752 CPUMASK_NANDBIT(mask, cpuid); 753 } 754 755 if (best_cpuid != -1) { 756 cpuid = best_cpuid; 757 gd = globaldata_find(cpuid); 758 dd = &bsd4_pcpu[cpuid]; 759 760 KTR_COND_LOG(usched_bsd4_setrunqueue_found_best_cpuid, 761 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 762 lp->lwp_proc->p_pid, 763 lp->lwp_thread->td_gd->gd_cpuid, 764 (unsigned long)CPUMASK_LOWMASK(mask), 765 cpuid, 766 mycpu->gd_cpuid); 767 768 goto found; 769 } 770 } else { 771 /* Fallback to the original heuristic */ 772 cpuid = (bsd4_scancpu & 0xFFFF) % ncpus; 773 mask = bsd4_rdyprocmask; 774 CPUMASK_NANDMASK(mask, bsd4_curprocmask); 775 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 776 CPUMASK_ANDMASK(mask, smp_active_mask); 777 CPUMASK_ANDMASK(mask, usched_global_cpumask); 778 779 KTR_COND_LOG(usched_bsd4_setrunqueue_fc_non_smt, 780 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 781 lp->lwp_proc->p_pid, 782 lp->lwp_thread->td_gd->gd_cpuid, 783 (unsigned long)CPUMASK_LOWMASK(mask), 784 mycpu->gd_cpuid); 785 786 while (CPUMASK_TESTNZERO(mask)) { 787 CPUMASK_ASSNBMASK(tmpmask, cpuid); 788 if (CPUMASK_TESTMASK(tmpmask, mask)) { 789 CPUMASK_ANDMASK(tmpmask, mask); 790 cpuid = BSFCPUMASK(tmpmask); 791 } else { 792 cpuid = BSFCPUMASK(mask); 793 } 794 gd = globaldata_find(cpuid); 795 dd = &bsd4_pcpu[cpuid]; 796 797 if ((dd->upri & ~PPQMASK) >= 798 (lp->lwp_priority & ~PPQMASK)) { 799 KTR_COND_LOG(usched_bsd4_setrunqueue_found, 800 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 801 lp->lwp_proc->p_pid, 802 lp->lwp_thread->td_gd->gd_cpuid, 803 (unsigned long)CPUMASK_LOWMASK(mask), 804 cpuid, 805 mycpu->gd_cpuid); 806 807 goto found; 808 } 809 CPUMASK_NANDBIT(mask, cpuid); 810 } 811 } 812 813 /* 814 * Then cpus which might have a currently running lp 815 */ 816 mask = bsd4_curprocmask; 817 CPUMASK_ANDMASK(mask, bsd4_rdyprocmask); 818 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 819 CPUMASK_ANDMASK(mask, smp_active_mask); 820 CPUMASK_ANDMASK(mask, usched_global_cpumask); 821 822 KTR_COND_LOG(usched_bsd4_setrunqueue_rc, 823 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 824 lp->lwp_proc->p_pid, 825 lp->lwp_thread->td_gd->gd_cpuid, 826 (unsigned long)CPUMASK_LOWMASK(mask), 827 mycpu->gd_cpuid); 828 829 while (CPUMASK_TESTNZERO(mask)) { 830 CPUMASK_ASSNBMASK(tmpmask, cpuid); 831 if (CPUMASK_TESTMASK(tmpmask, mask)) { 832 CPUMASK_ANDMASK(tmpmask, mask); 833 cpuid = BSFCPUMASK(tmpmask); 834 } else { 835 cpuid = BSFCPUMASK(mask); 836 } 837 gd = globaldata_find(cpuid); 838 dd = &bsd4_pcpu[cpuid]; 839 840 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) { 841 KTR_COND_LOG(usched_bsd4_setrunqueue_found, 842 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 843 lp->lwp_proc->p_pid, 844 lp->lwp_thread->td_gd->gd_cpuid, 845 (unsigned long)CPUMASK_LOWMASK(mask), 846 cpuid, 847 mycpu->gd_cpuid); 848 849 goto found; 850 } 851 CPUMASK_NANDBIT(mask, cpuid); 852 } 853 854 /* 855 * If we cannot find a suitable cpu we reload from bsd4_scancpu 856 * and round-robin. Other cpus will pickup as they release their 857 * current lwps or become ready. 858 * 859 * Avoid a degenerate system lockup case if usched_global_cpumask 860 * is set to 0 or otherwise does not cover lwp_cpumask. 861 * 862 * We only kick the target helper thread in this case, we do not 863 * set the user resched flag because 864 */ 865 cpuid = (bsd4_scancpu & 0xFFFF) % ncpus; 866 if (CPUMASK_TESTBIT(lp->lwp_cpumask, cpuid) == 0) 867 cpuid = BSFCPUMASK(lp->lwp_cpumask); 868 else if (CPUMASK_TESTBIT(usched_global_cpumask, cpuid) == 0) 869 cpuid = 0; 870 gd = globaldata_find(cpuid); 871 dd = &bsd4_pcpu[cpuid]; 872 873 KTR_COND_LOG(usched_bsd4_setrunqueue_not_found, 874 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 875 lp->lwp_proc->p_pid, 876 lp->lwp_thread->td_gd->gd_cpuid, 877 cpuid, 878 mycpu->gd_cpuid); 879 880 found: 881 if (gd == mycpu) { 882 spin_unlock(&bsd4_spin); 883 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) { 884 if (dd->uschedcp == NULL) { 885 wakeup_mycpu(dd->helper_thread); 886 } else { 887 need_user_resched(); 888 } 889 } 890 } else { 891 ATOMIC_CPUMASK_NANDBIT(bsd4_rdyprocmask, cpuid); 892 spin_unlock(&bsd4_spin); 893 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) 894 lwkt_send_ipiq(gd, bsd4_need_user_resched_remote, NULL); 895 else 896 wakeup(dd->helper_thread); 897 } 898 crit_exit(); 899 } 900 901 /* 902 * This routine is called from a systimer IPI. It MUST be MP-safe and 903 * the BGL IS NOT HELD ON ENTRY. This routine is called at ESTCPUFREQ on 904 * each cpu. 905 * 906 * This routine is called on every sched tick. If the currently running 907 * thread belongs to this scheduler it will be called with a non-NULL lp, 908 * otherwise it will be called with a NULL lp. 909 * 910 * MPSAFE 911 */ 912 static 913 void 914 bsd4_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp) 915 { 916 globaldata_t gd = mycpu; 917 bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid]; 918 919 /* 920 * No impl if no lp running. 921 */ 922 if (lp == NULL) 923 return; 924 925 /* 926 * Do we need to round-robin? We round-robin 10 times a second. 927 * This should only occur for cpu-bound batch processes. 928 */ 929 if (++dd->rrcount >= usched_bsd4_rrinterval) { 930 dd->rrcount = 0; 931 need_user_resched(); 932 } 933 934 /* 935 * Adjust estcpu upward using a real time equivalent calculation. 936 */ 937 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUMAX / ESTCPUFREQ + 1); 938 939 /* 940 * Spinlocks also hold a critical section so there should not be 941 * any active. 942 */ 943 KKASSERT(gd->gd_spinlocks == 0); 944 945 bsd4_resetpriority(lp); 946 } 947 948 /* 949 * Called from acquire and from kern_synch's one-second timer (one of the 950 * callout helper threads) with a critical section held. 951 * 952 * Decay p_estcpu based on the number of ticks we haven't been running 953 * and our p_nice. As the load increases each process observes a larger 954 * number of idle ticks (because other processes are running in them). 955 * This observation leads to a larger correction which tends to make the 956 * system more 'batchy'. 957 * 958 * Note that no recalculation occurs for a process which sleeps and wakes 959 * up in the same tick. That is, a system doing thousands of context 960 * switches per second will still only do serious estcpu calculations 961 * ESTCPUFREQ times per second. 962 * 963 * MPSAFE 964 */ 965 static 966 void 967 bsd4_recalculate_estcpu(struct lwp *lp) 968 { 969 globaldata_t gd = mycpu; 970 sysclock_t cpbase; 971 sysclock_t ttlticks; 972 int estcpu; 973 int decay_factor; 974 975 /* 976 * We have to subtract periodic to get the last schedclock 977 * timeout time, otherwise we would get the upcoming timeout. 978 * Keep in mind that a process can migrate between cpus and 979 * while the scheduler clock should be very close, boundary 980 * conditions could lead to a small negative delta. 981 */ 982 cpbase = gd->gd_schedclock.time - gd->gd_schedclock.periodic; 983 984 if (lp->lwp_slptime > 1) { 985 /* 986 * Too much time has passed, do a coarse correction. 987 */ 988 lp->lwp_estcpu = lp->lwp_estcpu >> 1; 989 bsd4_resetpriority(lp); 990 lp->lwp_cpbase = cpbase; 991 lp->lwp_cpticks = 0; 992 lp->lwp_batch -= ESTCPUFREQ; 993 if (lp->lwp_batch < 0) 994 lp->lwp_batch = 0; 995 } else if (lp->lwp_cpbase != cpbase) { 996 /* 997 * Adjust estcpu if we are in a different tick. Don't waste 998 * time if we are in the same tick. 999 * 1000 * First calculate the number of ticks in the measurement 1001 * interval. The ttlticks calculation can wind up 0 due to 1002 * a bug in the handling of lwp_slptime (as yet not found), 1003 * so make sure we do not get a divide by 0 panic. 1004 */ 1005 ttlticks = (cpbase - lp->lwp_cpbase) / 1006 gd->gd_schedclock.periodic; 1007 if ((ssysclock_t)ttlticks < 0) { 1008 ttlticks = 0; 1009 lp->lwp_cpbase = cpbase; 1010 } 1011 if (ttlticks == 0) 1012 return; 1013 updatepcpu(lp, lp->lwp_cpticks, ttlticks); 1014 1015 /* 1016 * Calculate the percentage of one cpu used factoring in ncpus 1017 * and the load and adjust estcpu. Handle degenerate cases 1018 * by adding 1 to bsd4_runqcount. 1019 * 1020 * estcpu is scaled by ESTCPUMAX. 1021 * 1022 * bsd4_runqcount is the excess number of user processes 1023 * that cannot be immediately scheduled to cpus. We want 1024 * to count these as running to avoid range compression 1025 * in the base calculation (which is the actual percentage 1026 * of one cpu used). 1027 */ 1028 estcpu = (lp->lwp_cpticks * ESTCPUMAX) * 1029 (bsd4_runqcount + ncpus) / (ncpus * ttlticks); 1030 1031 /* 1032 * If estcpu is > 50% we become more batch-like 1033 * If estcpu is <= 50% we become less batch-like 1034 * 1035 * It takes 30 cpu seconds to traverse the entire range. 1036 */ 1037 if (estcpu > ESTCPUMAX / 2) { 1038 lp->lwp_batch += ttlticks; 1039 if (lp->lwp_batch > BATCHMAX) 1040 lp->lwp_batch = BATCHMAX; 1041 } else { 1042 lp->lwp_batch -= ttlticks; 1043 if (lp->lwp_batch < 0) 1044 lp->lwp_batch = 0; 1045 } 1046 1047 if (usched_bsd4_debug == lp->lwp_proc->p_pid) { 1048 kprintf("pid %d lwp %p estcpu %3d %3d bat %d " 1049 "cp %ld/%ld", 1050 lp->lwp_proc->p_pid, lp, 1051 estcpu, lp->lwp_estcpu, 1052 lp->lwp_batch, 1053 lp->lwp_cpticks, ttlticks); 1054 } 1055 1056 /* 1057 * Adjust lp->lwp_esetcpu. The decay factor determines how 1058 * quickly lwp_estcpu collapses to its realtime calculation. 1059 * A slower collapse gives us a more accurate number but 1060 * can cause a cpu hog to eat too much cpu before the 1061 * scheduler decides to downgrade it. 1062 * 1063 * NOTE: p_nice is accounted for in bsd4_resetpriority(), 1064 * and not here, but we must still ensure that a 1065 * cpu-bound nice -20 process does not completely 1066 * override a cpu-bound nice +20 process. 1067 * 1068 * NOTE: We must use ESTCPULIM() here to deal with any 1069 * overshoot. 1070 */ 1071 decay_factor = usched_bsd4_decay; 1072 if (decay_factor < 1) 1073 decay_factor = 1; 1074 if (decay_factor > 1024) 1075 decay_factor = 1024; 1076 1077 lp->lwp_estcpu = ESTCPULIM( 1078 (lp->lwp_estcpu * decay_factor + estcpu) / 1079 (decay_factor + 1)); 1080 1081 if (usched_bsd4_debug == lp->lwp_proc->p_pid) 1082 kprintf(" finalestcpu %d\n", lp->lwp_estcpu); 1083 bsd4_resetpriority(lp); 1084 lp->lwp_cpbase += ttlticks * gd->gd_schedclock.periodic; 1085 lp->lwp_cpticks = 0; 1086 } 1087 } 1088 1089 /* 1090 * Compute the priority of a process when running in user mode. 1091 * Arrange to reschedule if the resulting priority is better 1092 * than that of the current process. 1093 * 1094 * This routine may be called with any process. 1095 * 1096 * This routine is called by fork1() for initial setup with the process 1097 * of the run queue, and also may be called normally with the process on or 1098 * off the run queue. 1099 * 1100 * MPSAFE 1101 */ 1102 static void 1103 bsd4_resetpriority(struct lwp *lp) 1104 { 1105 bsd4_pcpu_t dd; 1106 int newpriority; 1107 u_short newrqtype; 1108 int reschedcpu; 1109 int checkpri; 1110 int estcpu; 1111 1112 /* 1113 * Calculate the new priority and queue type 1114 */ 1115 crit_enter(); 1116 spin_lock(&bsd4_spin); 1117 1118 newrqtype = lp->lwp_rtprio.type; 1119 1120 switch(newrqtype) { 1121 case RTP_PRIO_REALTIME: 1122 case RTP_PRIO_FIFO: 1123 newpriority = PRIBASE_REALTIME + 1124 (lp->lwp_rtprio.prio & PRIMASK); 1125 break; 1126 case RTP_PRIO_NORMAL: 1127 /* 1128 * Detune estcpu based on batchiness. lwp_batch ranges 1129 * from 0 to BATCHMAX. Limit estcpu for the sake of 1130 * the priority calculation to between 50% and 100%. 1131 */ 1132 estcpu = lp->lwp_estcpu * (lp->lwp_batch + BATCHMAX) / 1133 (BATCHMAX * 2); 1134 1135 /* 1136 * p_nice piece Adds (0-40) * 2 0-80 1137 * estcpu Adds 16384 * 4 / 512 0-128 1138 */ 1139 newpriority = (lp->lwp_proc->p_nice - PRIO_MIN) * PPQ / NICEPPQ; 1140 newpriority += estcpu * PPQ / ESTCPUPPQ; 1141 newpriority = newpriority * MAXPRI / (PRIO_RANGE * PPQ / 1142 NICEPPQ + ESTCPUMAX * PPQ / ESTCPUPPQ); 1143 newpriority = PRIBASE_NORMAL + (newpriority & PRIMASK); 1144 break; 1145 case RTP_PRIO_IDLE: 1146 newpriority = PRIBASE_IDLE + (lp->lwp_rtprio.prio & PRIMASK); 1147 break; 1148 case RTP_PRIO_THREAD: 1149 newpriority = PRIBASE_THREAD + (lp->lwp_rtprio.prio & PRIMASK); 1150 break; 1151 default: 1152 panic("Bad RTP_PRIO %d", newrqtype); 1153 /* NOT REACHED */ 1154 } 1155 1156 /* 1157 * The newpriority incorporates the queue type so do a simple masked 1158 * check to determine if the process has moved to another queue. If 1159 * it has, and it is currently on a run queue, then move it. 1160 * 1161 * td_upri has normal sense (higher values are more desireable), so 1162 * negate it. 1163 */ 1164 lp->lwp_thread->td_upri = -(newpriority & ~PPQMASK); 1165 if ((lp->lwp_priority ^ newpriority) & ~PPQMASK) { 1166 lp->lwp_priority = newpriority; 1167 if (lp->lwp_mpflags & LWP_MP_ONRUNQ) { 1168 bsd4_remrunqueue_locked(lp); 1169 lp->lwp_rqtype = newrqtype; 1170 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ; 1171 bsd4_setrunqueue_locked(lp); 1172 checkpri = 1; 1173 } else { 1174 lp->lwp_rqtype = newrqtype; 1175 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ; 1176 checkpri = 0; 1177 } 1178 reschedcpu = lp->lwp_thread->td_gd->gd_cpuid; 1179 } else { 1180 lp->lwp_priority = newpriority; 1181 reschedcpu = -1; 1182 checkpri = 1; 1183 } 1184 1185 /* 1186 * Determine if we need to reschedule the target cpu. This only 1187 * occurs if the LWP is already on a scheduler queue, which means 1188 * that idle cpu notification has already occured. At most we 1189 * need only issue a need_user_resched() on the appropriate cpu. 1190 * 1191 * The LWP may be owned by a CPU different from the current one, 1192 * in which case dd->uschedcp may be modified without an MP lock 1193 * or a spinlock held. The worst that happens is that the code 1194 * below causes a spurious need_user_resched() on the target CPU 1195 * and dd->pri to be wrong for a short period of time, both of 1196 * which are harmless. 1197 * 1198 * If checkpri is 0 we are adjusting the priority of the current 1199 * process, possibly higher (less desireable), so ignore the upri 1200 * check which will fail in that case. 1201 */ 1202 if (reschedcpu >= 0) { 1203 dd = &bsd4_pcpu[reschedcpu]; 1204 if (CPUMASK_TESTBIT(bsd4_rdyprocmask, reschedcpu) && 1205 (checkpri == 0 || 1206 (dd->upri & ~PRIMASK) > (lp->lwp_priority & ~PRIMASK))) { 1207 if (reschedcpu == mycpu->gd_cpuid) { 1208 spin_unlock(&bsd4_spin); 1209 need_user_resched(); 1210 } else { 1211 spin_unlock(&bsd4_spin); 1212 ATOMIC_CPUMASK_NANDBIT(bsd4_rdyprocmask, 1213 reschedcpu); 1214 lwkt_send_ipiq(lp->lwp_thread->td_gd, 1215 bsd4_need_user_resched_remote, 1216 NULL); 1217 } 1218 } else { 1219 spin_unlock(&bsd4_spin); 1220 } 1221 } else { 1222 spin_unlock(&bsd4_spin); 1223 } 1224 crit_exit(); 1225 } 1226 1227 /* 1228 * MPSAFE 1229 */ 1230 static 1231 void 1232 bsd4_yield(struct lwp *lp) 1233 { 1234 #if 0 1235 /* FUTURE (or something similar) */ 1236 switch(lp->lwp_rqtype) { 1237 case RTP_PRIO_NORMAL: 1238 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUINCR); 1239 break; 1240 default: 1241 break; 1242 } 1243 #endif 1244 need_user_resched(); 1245 } 1246 1247 static 1248 void 1249 bsd4_changedcpu(struct lwp *lp __unused) 1250 { 1251 } 1252 1253 /* 1254 * Called from fork1() when a new child process is being created. 1255 * 1256 * Give the child process an initial estcpu that is more batch then 1257 * its parent and dock the parent for the fork (but do not 1258 * reschedule the parent). This comprises the main part of our batch 1259 * detection heuristic for both parallel forking and sequential execs. 1260 * 1261 * XXX lwp should be "spawning" instead of "forking" 1262 * 1263 * MPSAFE 1264 */ 1265 static void 1266 bsd4_forking(struct lwp *plp, struct lwp *lp) 1267 { 1268 /* 1269 * Put the child 4 queue slots (out of 32) higher than the parent 1270 * (less desireable than the parent). 1271 */ 1272 lp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ * 4); 1273 1274 /* 1275 * The batch status of children always starts out centerline 1276 * and will inch-up or inch-down as appropriate. It takes roughly 1277 * ~15 seconds of >50% cpu to hit the limit. 1278 */ 1279 lp->lwp_batch = BATCHMAX / 2; 1280 1281 /* 1282 * Dock the parent a cost for the fork, protecting us from fork 1283 * bombs. If the parent is forking quickly make the child more 1284 * batchy. 1285 */ 1286 plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ / 16); 1287 } 1288 1289 /* 1290 * Called when a lwp is being removed from this scheduler, typically 1291 * during lwp_exit(). 1292 */ 1293 static void 1294 bsd4_exiting(struct lwp *lp, struct proc *child_proc) 1295 { 1296 } 1297 1298 static void 1299 bsd4_uload_update(struct lwp *lp) 1300 { 1301 } 1302 1303 /* 1304 * chooseproc() is called when a cpu needs a user process to LWKT schedule, 1305 * it selects a user process and returns it. If chklp is non-NULL and chklp 1306 * has a better or equal priority then the process that would otherwise be 1307 * chosen, NULL is returned. 1308 * 1309 * Until we fix the RUNQ code the chklp test has to be strict or we may 1310 * bounce between processes trying to acquire the current process designation. 1311 * 1312 * MPSAFE - must be called with bsd4_spin exclusive held. The spinlock is 1313 * left intact through the entire routine. 1314 */ 1315 static 1316 struct lwp * 1317 bsd4_chooseproc_locked(struct lwp *chklp) 1318 { 1319 struct lwp *lp; 1320 struct rq *q; 1321 u_int32_t *which, *which2; 1322 u_int32_t pri; 1323 u_int32_t rtqbits; 1324 u_int32_t tsqbits; 1325 u_int32_t idqbits; 1326 cpumask_t cpumask; 1327 1328 rtqbits = bsd4_rtqueuebits; 1329 tsqbits = bsd4_queuebits; 1330 idqbits = bsd4_idqueuebits; 1331 cpumask = mycpu->gd_cpumask; 1332 1333 1334 again: 1335 if (rtqbits) { 1336 pri = bsfl(rtqbits); 1337 q = &bsd4_rtqueues[pri]; 1338 which = &bsd4_rtqueuebits; 1339 which2 = &rtqbits; 1340 } else if (tsqbits) { 1341 pri = bsfl(tsqbits); 1342 q = &bsd4_queues[pri]; 1343 which = &bsd4_queuebits; 1344 which2 = &tsqbits; 1345 } else if (idqbits) { 1346 pri = bsfl(idqbits); 1347 q = &bsd4_idqueues[pri]; 1348 which = &bsd4_idqueuebits; 1349 which2 = &idqbits; 1350 } else { 1351 return NULL; 1352 } 1353 lp = TAILQ_FIRST(q); 1354 KASSERT(lp, ("chooseproc: no lwp on busy queue")); 1355 1356 while (CPUMASK_TESTMASK(lp->lwp_cpumask, cpumask) == 0) { 1357 lp = TAILQ_NEXT(lp, lwp_procq); 1358 if (lp == NULL) { 1359 *which2 &= ~(1 << pri); 1360 goto again; 1361 } 1362 } 1363 1364 /* 1365 * If the passed lwp <chklp> is reasonably close to the selected 1366 * lwp <lp>, return NULL (indicating that <chklp> should be kept). 1367 * 1368 * Note that we must error on the side of <chklp> to avoid bouncing 1369 * between threads in the acquire code. 1370 */ 1371 if (chklp) { 1372 if (chklp->lwp_priority < lp->lwp_priority + PPQ) 1373 return(NULL); 1374 } 1375 1376 /* 1377 * If the chosen lwp does not reside on this cpu spend a few 1378 * cycles looking for a better candidate at the same priority level. 1379 * This is a fallback check, setrunqueue() tries to wakeup the 1380 * correct cpu and is our front-line affinity. 1381 */ 1382 if (lp->lwp_thread->td_gd != mycpu && 1383 (chklp = TAILQ_NEXT(lp, lwp_procq)) != NULL 1384 ) { 1385 if (chklp->lwp_thread->td_gd == mycpu) { 1386 lp = chklp; 1387 } 1388 } 1389 1390 KTR_COND_LOG(usched_bsd4_chooseproc, 1391 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1392 lp->lwp_proc->p_pid, 1393 lp->lwp_thread->td_gd->gd_cpuid, 1394 mycpu->gd_cpuid); 1395 1396 TAILQ_REMOVE(q, lp, lwp_procq); 1397 --bsd4_runqcount; 1398 if (TAILQ_EMPTY(q)) 1399 *which &= ~(1 << pri); 1400 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) != 0, ("not on runq6!")); 1401 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1402 1403 return lp; 1404 } 1405 1406 /* 1407 * chooseproc() - with a cache coherence heuristic. Try to pull a process that 1408 * has its home on the current CPU> If the process doesn't have its home here 1409 * and is a batchy one (see batcy_looser_pri_test), we can wait for a 1410 * sched_tick, may be its home will become free and pull it in. Anyway, 1411 * we can't wait more than one tick. If that tick expired, we pull in that 1412 * process, no matter what. 1413 */ 1414 static 1415 struct lwp * 1416 bsd4_chooseproc_locked_cache_coherent(struct lwp *chklp) 1417 { 1418 struct lwp *lp; 1419 struct rq *q; 1420 u_int32_t *which, *which2; 1421 u_int32_t pri; 1422 u_int32_t checks; 1423 u_int32_t rtqbits; 1424 u_int32_t tsqbits; 1425 u_int32_t idqbits; 1426 cpumask_t cpumask; 1427 1428 struct lwp * min_level_lwp = NULL; 1429 struct rq *min_q = NULL; 1430 cpumask_t siblings; 1431 cpu_node_t* cpunode = NULL; 1432 u_int32_t min_level = MAXCPU; /* number of levels < MAXCPU */ 1433 u_int32_t *min_which = NULL; 1434 u_int32_t min_pri = 0; 1435 u_int32_t level = 0; 1436 1437 rtqbits = bsd4_rtqueuebits; 1438 tsqbits = bsd4_queuebits; 1439 idqbits = bsd4_idqueuebits; 1440 cpumask = mycpu->gd_cpumask; 1441 1442 /* Get the mask coresponding to the sysctl configured level */ 1443 cpunode = bsd4_pcpu[mycpu->gd_cpuid].cpunode; 1444 level = usched_bsd4_stick_to_level; 1445 while (level) { 1446 cpunode = cpunode->parent_node; 1447 level--; 1448 } 1449 /* The cpus which can ellect a process */ 1450 siblings = cpunode->members; 1451 checks = 0; 1452 1453 again: 1454 if (rtqbits) { 1455 pri = bsfl(rtqbits); 1456 q = &bsd4_rtqueues[pri]; 1457 which = &bsd4_rtqueuebits; 1458 which2 = &rtqbits; 1459 } else if (tsqbits) { 1460 pri = bsfl(tsqbits); 1461 q = &bsd4_queues[pri]; 1462 which = &bsd4_queuebits; 1463 which2 = &tsqbits; 1464 } else if (idqbits) { 1465 pri = bsfl(idqbits); 1466 q = &bsd4_idqueues[pri]; 1467 which = &bsd4_idqueuebits; 1468 which2 = &idqbits; 1469 } else { 1470 /* 1471 * No more left and we didn't reach the checks limit. 1472 */ 1473 bsd4_kick_helper(min_level_lwp); 1474 return NULL; 1475 } 1476 lp = TAILQ_FIRST(q); 1477 KASSERT(lp, ("chooseproc: no lwp on busy queue")); 1478 1479 /* 1480 * Limit the number of checks/queue to a configurable value to 1481 * minimize the contention (we are in a locked region 1482 */ 1483 while (checks < usched_bsd4_queue_checks) { 1484 if (CPUMASK_TESTMASK(lp->lwp_cpumask, cpumask) == 0 || 1485 (CPUMASK_TESTMASK(siblings, 1486 lp->lwp_thread->td_gd->gd_cpumask) == 0 && 1487 (lp->lwp_rebal_ticks == sched_ticks || 1488 lp->lwp_rebal_ticks == (int)(sched_ticks - 1)) && 1489 bsd4_batchy_looser_pri_test(lp))) { 1490 1491 KTR_COND_LOG(usched_chooseproc_cc_not_good, 1492 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1493 lp->lwp_proc->p_pid, 1494 (unsigned long)CPUMASK_LOWMASK( 1495 lp->lwp_thread->td_gd->gd_cpumask), 1496 (unsigned long)CPUMASK_LOWMASK(siblings), 1497 (unsigned long)CPUMASK_LOWMASK(cpumask)); 1498 1499 cpunode = bsd4_pcpu[lp->lwp_thread->td_gd->gd_cpuid].cpunode; 1500 level = 0; 1501 while (cpunode) { 1502 if (CPUMASK_TESTMASK(cpunode->members, 1503 cpumask)) { 1504 break; 1505 } 1506 cpunode = cpunode->parent_node; 1507 level++; 1508 } 1509 if (level < min_level || 1510 (level == min_level && min_level_lwp && 1511 lp->lwp_priority < min_level_lwp->lwp_priority)) { 1512 bsd4_kick_helper(min_level_lwp); 1513 min_level_lwp = lp; 1514 min_level = level; 1515 min_q = q; 1516 min_which = which; 1517 min_pri = pri; 1518 } else { 1519 bsd4_kick_helper(lp); 1520 } 1521 lp = TAILQ_NEXT(lp, lwp_procq); 1522 if (lp == NULL) { 1523 *which2 &= ~(1 << pri); 1524 goto again; 1525 } 1526 } else { 1527 KTR_COND_LOG(usched_chooseproc_cc_elected, 1528 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1529 lp->lwp_proc->p_pid, 1530 (unsigned long)CPUMASK_LOWMASK( 1531 lp->lwp_thread->td_gd->gd_cpumask), 1532 (unsigned long)CPUMASK_LOWMASK(siblings), 1533 (unsigned long)CPUMASK_LOWMASK(cpumask)); 1534 1535 goto found; 1536 } 1537 ++checks; 1538 } 1539 1540 /* 1541 * Checks exhausted, we tried to defer too many threads, so schedule 1542 * the best of the worst. 1543 */ 1544 lp = min_level_lwp; 1545 q = min_q; 1546 which = min_which; 1547 pri = min_pri; 1548 KASSERT(lp, ("chooseproc: at least the first lp was good")); 1549 1550 found: 1551 1552 /* 1553 * If the passed lwp <chklp> is reasonably close to the selected 1554 * lwp <lp>, return NULL (indicating that <chklp> should be kept). 1555 * 1556 * Note that we must error on the side of <chklp> to avoid bouncing 1557 * between threads in the acquire code. 1558 */ 1559 if (chklp) { 1560 if (chklp->lwp_priority < lp->lwp_priority + PPQ) { 1561 bsd4_kick_helper(lp); 1562 return(NULL); 1563 } 1564 } 1565 1566 KTR_COND_LOG(usched_chooseproc_cc, 1567 lp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1568 lp->lwp_proc->p_pid, 1569 lp->lwp_thread->td_gd->gd_cpuid, 1570 mycpu->gd_cpuid); 1571 1572 TAILQ_REMOVE(q, lp, lwp_procq); 1573 --bsd4_runqcount; 1574 if (TAILQ_EMPTY(q)) 1575 *which &= ~(1 << pri); 1576 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) != 0, ("not on runq6!")); 1577 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1578 1579 return lp; 1580 } 1581 1582 /* 1583 * If we aren't willing to schedule a ready process on our cpu, give it's 1584 * target cpu a kick rather than wait for the next tick. 1585 * 1586 * Called with bsd4_spin held. 1587 */ 1588 static 1589 void 1590 bsd4_kick_helper(struct lwp *lp) 1591 { 1592 globaldata_t gd; 1593 bsd4_pcpu_t dd; 1594 cpumask_t tmpmask; 1595 1596 if (lp == NULL) 1597 return; 1598 gd = lp->lwp_thread->td_gd; 1599 dd = &bsd4_pcpu[gd->gd_cpuid]; 1600 1601 tmpmask = smp_active_mask; 1602 CPUMASK_ANDMASK(tmpmask, usched_global_cpumask); 1603 CPUMASK_ANDMASK(tmpmask, bsd4_rdyprocmask); 1604 CPUMASK_ANDMASK(tmpmask, gd->gd_cpumask); 1605 if (CPUMASK_TESTZERO(tmpmask)) 1606 return; 1607 1608 ++usched_bsd4_kicks; 1609 ATOMIC_CPUMASK_NANDBIT(bsd4_rdyprocmask, gd->gd_cpuid); 1610 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) { 1611 lwkt_send_ipiq(gd, bsd4_need_user_resched_remote, NULL); 1612 } else { 1613 wakeup(dd->helper_thread); 1614 } 1615 } 1616 1617 static 1618 void 1619 bsd4_need_user_resched_remote(void *dummy) 1620 { 1621 globaldata_t gd = mycpu; 1622 bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid]; 1623 1624 need_user_resched(); 1625 1626 /* Call wakeup_mycpu to avoid sending IPIs to other CPUs */ 1627 wakeup_mycpu(dd->helper_thread); 1628 } 1629 1630 /* 1631 * bsd4_remrunqueue_locked() removes a given process from the run queue 1632 * that it is on, clearing the queue busy bit if it becomes empty. 1633 * 1634 * Note that user process scheduler is different from the LWKT schedule. 1635 * The user process scheduler only manages user processes but it uses LWKT 1636 * underneath, and a user process operating in the kernel will often be 1637 * 'released' from our management. 1638 * 1639 * MPSAFE - bsd4_spin must be held exclusively on call 1640 */ 1641 static void 1642 bsd4_remrunqueue_locked(struct lwp *lp) 1643 { 1644 struct rq *q; 1645 u_int32_t *which; 1646 u_int8_t pri; 1647 1648 KKASSERT(lp->lwp_mpflags & LWP_MP_ONRUNQ); 1649 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1650 --bsd4_runqcount; 1651 KKASSERT(bsd4_runqcount >= 0); 1652 1653 pri = lp->lwp_rqindex; 1654 switch(lp->lwp_rqtype) { 1655 case RTP_PRIO_NORMAL: 1656 q = &bsd4_queues[pri]; 1657 which = &bsd4_queuebits; 1658 break; 1659 case RTP_PRIO_REALTIME: 1660 case RTP_PRIO_FIFO: 1661 q = &bsd4_rtqueues[pri]; 1662 which = &bsd4_rtqueuebits; 1663 break; 1664 case RTP_PRIO_IDLE: 1665 q = &bsd4_idqueues[pri]; 1666 which = &bsd4_idqueuebits; 1667 break; 1668 default: 1669 panic("remrunqueue: invalid rtprio type"); 1670 /* NOT REACHED */ 1671 } 1672 TAILQ_REMOVE(q, lp, lwp_procq); 1673 if (TAILQ_EMPTY(q)) { 1674 KASSERT((*which & (1 << pri)) != 0, 1675 ("remrunqueue: remove from empty queue")); 1676 *which &= ~(1 << pri); 1677 } 1678 } 1679 1680 /* 1681 * bsd4_setrunqueue_locked() 1682 * 1683 * Add a process whos rqtype and rqindex had previously been calculated 1684 * onto the appropriate run queue. Determine if the addition requires 1685 * a reschedule on a cpu and return the cpuid or -1. 1686 * 1687 * NOTE: Lower priorities are better priorities. 1688 * 1689 * MPSAFE - bsd4_spin must be held exclusively on call 1690 */ 1691 static void 1692 bsd4_setrunqueue_locked(struct lwp *lp) 1693 { 1694 struct rq *q; 1695 u_int32_t *which; 1696 int pri; 1697 1698 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 1699 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1700 ++bsd4_runqcount; 1701 1702 pri = lp->lwp_rqindex; 1703 1704 switch(lp->lwp_rqtype) { 1705 case RTP_PRIO_NORMAL: 1706 q = &bsd4_queues[pri]; 1707 which = &bsd4_queuebits; 1708 break; 1709 case RTP_PRIO_REALTIME: 1710 case RTP_PRIO_FIFO: 1711 q = &bsd4_rtqueues[pri]; 1712 which = &bsd4_rtqueuebits; 1713 break; 1714 case RTP_PRIO_IDLE: 1715 q = &bsd4_idqueues[pri]; 1716 which = &bsd4_idqueuebits; 1717 break; 1718 default: 1719 panic("remrunqueue: invalid rtprio type"); 1720 /* NOT REACHED */ 1721 } 1722 1723 /* 1724 * Add to the correct queue and set the appropriate bit. If no 1725 * lower priority (i.e. better) processes are in the queue then 1726 * we want a reschedule, calculate the best cpu for the job. 1727 * 1728 * Always run reschedules on the LWPs original cpu. 1729 */ 1730 TAILQ_INSERT_TAIL(q, lp, lwp_procq); 1731 *which |= 1 << pri; 1732 } 1733 1734 /* 1735 * For SMP systems a user scheduler helper thread is created for each 1736 * cpu and is used to allow one cpu to wakeup another for the purposes of 1737 * scheduling userland threads from setrunqueue(). 1738 * 1739 * UP systems do not need the helper since there is only one cpu. 1740 * 1741 * We can't use the idle thread for this because we might block. 1742 * Additionally, doing things this way allows us to HLT idle cpus 1743 * on MP systems. 1744 * 1745 * MPSAFE 1746 */ 1747 static void 1748 sched_thread(void *dummy) 1749 { 1750 globaldata_t gd; 1751 bsd4_pcpu_t dd; 1752 bsd4_pcpu_t tmpdd; 1753 struct lwp *nlp; 1754 cpumask_t mask; 1755 int cpuid; 1756 cpumask_t tmpmask; 1757 int tmpid; 1758 1759 gd = mycpu; 1760 cpuid = gd->gd_cpuid; /* doesn't change */ 1761 mask = gd->gd_cpumask; /* doesn't change */ 1762 dd = &bsd4_pcpu[cpuid]; 1763 1764 /* 1765 * Since we are woken up only when no user processes are scheduled 1766 * on a cpu, we can run at an ultra low priority. 1767 */ 1768 lwkt_setpri_self(TDPRI_USER_SCHEDULER); 1769 1770 tsleep(dd->helper_thread, 0, "sched_thread_sleep", 0); 1771 1772 for (;;) { 1773 /* 1774 * We use the LWKT deschedule-interlock trick to avoid racing 1775 * bsd4_rdyprocmask. This means we cannot block through to the 1776 * manual lwkt_switch() call we make below. 1777 */ 1778 crit_enter_gd(gd); 1779 tsleep_interlock(dd->helper_thread, 0); 1780 spin_lock(&bsd4_spin); 1781 ATOMIC_CPUMASK_ORMASK(bsd4_rdyprocmask, mask); 1782 1783 clear_user_resched(); /* This satisfied the reschedule request */ 1784 dd->rrcount = 0; /* Reset the round-robin counter */ 1785 1786 if (CPUMASK_TESTMASK(bsd4_curprocmask, mask) == 0) { 1787 /* 1788 * No thread is currently scheduled. 1789 */ 1790 KKASSERT(dd->uschedcp == NULL); 1791 if ((nlp = bsd4_chooseproc_locked(NULL)) != NULL) { 1792 KTR_COND_LOG(usched_sched_thread_no_process, 1793 nlp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1794 gd->gd_cpuid, 1795 nlp->lwp_proc->p_pid, 1796 nlp->lwp_thread->td_gd->gd_cpuid); 1797 1798 ATOMIC_CPUMASK_ORMASK(bsd4_curprocmask, mask); 1799 dd->upri = nlp->lwp_priority; 1800 dd->uschedcp = nlp; 1801 dd->rrcount = 0; /* reset round robin */ 1802 spin_unlock(&bsd4_spin); 1803 lwkt_acquire(nlp->lwp_thread); 1804 lwkt_schedule(nlp->lwp_thread); 1805 } else { 1806 spin_unlock(&bsd4_spin); 1807 } 1808 } else if (bsd4_runqcount) { 1809 if ((nlp = bsd4_chooseproc_locked(dd->uschedcp)) != NULL) { 1810 KTR_COND_LOG(usched_sched_thread_process, 1811 nlp->lwp_proc->p_pid == usched_bsd4_pid_debug, 1812 gd->gd_cpuid, 1813 nlp->lwp_proc->p_pid, 1814 nlp->lwp_thread->td_gd->gd_cpuid); 1815 1816 dd->upri = nlp->lwp_priority; 1817 dd->uschedcp = nlp; 1818 dd->rrcount = 0; /* reset round robin */ 1819 spin_unlock(&bsd4_spin); 1820 lwkt_acquire(nlp->lwp_thread); 1821 lwkt_schedule(nlp->lwp_thread); 1822 } else { 1823 /* 1824 * CHAINING CONDITION TRAIN 1825 * 1826 * We could not deal with the scheduler wakeup 1827 * request on this cpu, locate a ready scheduler 1828 * with no current lp assignment and chain to it. 1829 * 1830 * This ensures that a wakeup race which fails due 1831 * to priority test does not leave other unscheduled 1832 * cpus idle when the runqueue is not empty. 1833 */ 1834 tmpmask = bsd4_rdyprocmask; 1835 CPUMASK_NANDMASK(tmpmask, bsd4_curprocmask); 1836 CPUMASK_ANDMASK(tmpmask, smp_active_mask); 1837 if (CPUMASK_TESTNZERO(tmpmask)) { 1838 tmpid = BSFCPUMASK(tmpmask); 1839 tmpdd = &bsd4_pcpu[tmpid]; 1840 ATOMIC_CPUMASK_NANDBIT(bsd4_rdyprocmask, tmpid); 1841 spin_unlock(&bsd4_spin); 1842 wakeup(tmpdd->helper_thread); 1843 } else { 1844 spin_unlock(&bsd4_spin); 1845 } 1846 1847 KTR_LOG(usched_sched_thread_no_process_found, 1848 gd->gd_cpuid, (unsigned long)CPUMASK_LOWMASK(tmpmask)); 1849 } 1850 } else { 1851 /* 1852 * The runq is empty. 1853 */ 1854 spin_unlock(&bsd4_spin); 1855 } 1856 1857 /* 1858 * We're descheduled unless someone scheduled us. Switch away. 1859 * Exiting the critical section will cause splz() to be called 1860 * for us if interrupts and such are pending. 1861 */ 1862 crit_exit_gd(gd); 1863 tsleep(dd->helper_thread, PINTERLOCKED, "schslp", 0); 1864 } 1865 } 1866 1867 /* sysctl stick_to_level parameter */ 1868 static int 1869 sysctl_usched_bsd4_stick_to_level(SYSCTL_HANDLER_ARGS) 1870 { 1871 int error, new_val; 1872 1873 new_val = usched_bsd4_stick_to_level; 1874 1875 error = sysctl_handle_int(oidp, &new_val, 0, req); 1876 if (error != 0 || req->newptr == NULL) 1877 return (error); 1878 if (new_val > cpu_topology_levels_number - 1 || new_val < 0) 1879 return (EINVAL); 1880 usched_bsd4_stick_to_level = new_val; 1881 return (0); 1882 } 1883 1884 /* 1885 * Setup our scheduler helpers. Note that curprocmask bit 0 has already 1886 * been cleared by rqinit() and we should not mess with it further. 1887 */ 1888 static void 1889 sched_thread_cpu_init(void) 1890 { 1891 int i; 1892 int smt_not_supported = 0; 1893 int cache_coherent_not_supported = 0; 1894 1895 if (bootverbose) 1896 kprintf("Start usched_bsd4 helpers on cpus:\n"); 1897 1898 sysctl_ctx_init(&usched_bsd4_sysctl_ctx); 1899 usched_bsd4_sysctl_tree = 1900 SYSCTL_ADD_NODE(&usched_bsd4_sysctl_ctx, 1901 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO, 1902 "usched_bsd4", CTLFLAG_RD, 0, ""); 1903 1904 for (i = 0; i < ncpus; ++i) { 1905 bsd4_pcpu_t dd = &bsd4_pcpu[i]; 1906 cpumask_t mask; 1907 1908 CPUMASK_ASSBIT(mask, i); 1909 1910 if (CPUMASK_TESTMASK(mask, smp_active_mask) == 0) 1911 continue; 1912 1913 dd->cpunode = get_cpu_node_by_cpuid(i); 1914 1915 if (dd->cpunode == NULL) { 1916 smt_not_supported = 1; 1917 cache_coherent_not_supported = 1; 1918 if (bootverbose) 1919 kprintf (" cpu%d - WARNING: No CPU NODE " 1920 "found for cpu\n", i); 1921 } else { 1922 switch (dd->cpunode->type) { 1923 case THREAD_LEVEL: 1924 if (bootverbose) 1925 kprintf (" cpu%d - HyperThreading " 1926 "available. Core siblings: ", 1927 i); 1928 break; 1929 case CORE_LEVEL: 1930 smt_not_supported = 1; 1931 1932 if (bootverbose) 1933 kprintf (" cpu%d - No HT available, " 1934 "multi-core/physical " 1935 "cpu. Physical siblings: ", 1936 i); 1937 break; 1938 case CHIP_LEVEL: 1939 smt_not_supported = 1; 1940 1941 if (bootverbose) 1942 kprintf (" cpu%d - No HT available, " 1943 "single-core/physical cpu. " 1944 "Package Siblings: ", 1945 i); 1946 break; 1947 default: 1948 /* Let's go for safe defaults here */ 1949 smt_not_supported = 1; 1950 cache_coherent_not_supported = 1; 1951 if (bootverbose) 1952 kprintf (" cpu%d - Unknown cpunode->" 1953 "type=%u. Siblings: ", 1954 i, 1955 (u_int)dd->cpunode->type); 1956 break; 1957 } 1958 1959 if (bootverbose) { 1960 if (dd->cpunode->parent_node != NULL) { 1961 kprint_cpuset(&dd->cpunode-> 1962 parent_node->members); 1963 kprintf("\n"); 1964 } else { 1965 kprintf(" no siblings\n"); 1966 } 1967 } 1968 } 1969 1970 lwkt_create(sched_thread, NULL, &dd->helper_thread, NULL, 1971 0, i, "usched %d", i); 1972 1973 /* 1974 * Allow user scheduling on the target cpu. cpu #0 has already 1975 * been enabled in rqinit(). 1976 */ 1977 if (i) 1978 ATOMIC_CPUMASK_NANDMASK(bsd4_curprocmask, mask); 1979 ATOMIC_CPUMASK_ORMASK(bsd4_rdyprocmask, mask); 1980 dd->upri = PRIBASE_NULL; 1981 1982 } 1983 1984 /* usched_bsd4 sysctl configurable parameters */ 1985 1986 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 1987 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 1988 OID_AUTO, "rrinterval", CTLFLAG_RW, 1989 &usched_bsd4_rrinterval, 0, ""); 1990 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 1991 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 1992 OID_AUTO, "decay", CTLFLAG_RW, 1993 &usched_bsd4_decay, 0, "Extra decay when not running"); 1994 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 1995 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 1996 OID_AUTO, "batch_time", CTLFLAG_RW, 1997 &usched_bsd4_batch_time, 0, "Min batch counter value"); 1998 SYSCTL_ADD_LONG(&usched_bsd4_sysctl_ctx, 1999 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2000 OID_AUTO, "kicks", CTLFLAG_RW, 2001 &usched_bsd4_kicks, "Number of kickstarts"); 2002 2003 /* Add enable/disable option for SMT scheduling if supported */ 2004 if (smt_not_supported) { 2005 usched_bsd4_smt = 0; 2006 SYSCTL_ADD_STRING(&usched_bsd4_sysctl_ctx, 2007 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2008 OID_AUTO, "smt", CTLFLAG_RD, 2009 "NOT SUPPORTED", 0, "SMT NOT SUPPORTED"); 2010 } else { 2011 usched_bsd4_smt = 1; 2012 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 2013 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2014 OID_AUTO, "smt", CTLFLAG_RW, 2015 &usched_bsd4_smt, 0, "Enable SMT scheduling"); 2016 } 2017 2018 /* 2019 * Add enable/disable option for cache coherent scheduling 2020 * if supported 2021 */ 2022 if (cache_coherent_not_supported) { 2023 usched_bsd4_cache_coherent = 0; 2024 SYSCTL_ADD_STRING(&usched_bsd4_sysctl_ctx, 2025 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2026 OID_AUTO, "cache_coherent", CTLFLAG_RD, 2027 "NOT SUPPORTED", 0, 2028 "Cache coherence NOT SUPPORTED"); 2029 } else { 2030 usched_bsd4_cache_coherent = 1; 2031 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 2032 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2033 OID_AUTO, "cache_coherent", CTLFLAG_RW, 2034 &usched_bsd4_cache_coherent, 0, 2035 "Enable/Disable cache coherent scheduling"); 2036 2037 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 2038 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2039 OID_AUTO, "upri_affinity", CTLFLAG_RW, 2040 &usched_bsd4_upri_affinity, 1, 2041 "Number of PPQs in user priority check"); 2042 2043 SYSCTL_ADD_INT(&usched_bsd4_sysctl_ctx, 2044 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2045 OID_AUTO, "queue_checks", CTLFLAG_RW, 2046 &usched_bsd4_queue_checks, 5, 2047 "LWPs to check from a queue before giving up"); 2048 2049 SYSCTL_ADD_PROC(&usched_bsd4_sysctl_ctx, 2050 SYSCTL_CHILDREN(usched_bsd4_sysctl_tree), 2051 OID_AUTO, "stick_to_level", 2052 CTLTYPE_INT | CTLFLAG_RW, 2053 NULL, sizeof usched_bsd4_stick_to_level, 2054 sysctl_usched_bsd4_stick_to_level, "I", 2055 "Stick a process to this level. See sysctl" 2056 "paremter hw.cpu_topology.level_description"); 2057 } 2058 } 2059 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND, 2060 sched_thread_cpu_init, NULL); 2061