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 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in 18 * the documentation and/or other materials provided with the 19 * distribution. 20 * 3. Neither the name of The DragonFly Project nor the names of its 21 * contributors may be used to endorse or promote products derived 22 * from this software without specific, prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 25 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 28 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 29 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 32 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 33 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 34 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 #include <sys/param.h> 38 #include <sys/systm.h> 39 #include <sys/kernel.h> 40 #include <sys/lock.h> 41 #include <sys/queue.h> 42 #include <sys/proc.h> 43 #include <sys/rtprio.h> 44 #include <sys/uio.h> 45 #include <sys/sysctl.h> 46 #include <sys/resourcevar.h> 47 #include <sys/spinlock.h> 48 #include <sys/cpu_topology.h> 49 #include <sys/thread2.h> 50 #include <sys/spinlock2.h> 51 52 #include <sys/ktr.h> 53 54 #include <machine/cpu.h> 55 #include <machine/smp.h> 56 57 /* 58 * Priorities. Note that with 32 run queues per scheduler each queue 59 * represents four priority levels. 60 */ 61 62 int dfly_rebalanced; 63 64 #define MAXPRI 128 65 #define PRIMASK (MAXPRI - 1) 66 #define PRIBASE_REALTIME 0 67 #define PRIBASE_NORMAL MAXPRI 68 #define PRIBASE_IDLE (MAXPRI * 2) 69 #define PRIBASE_THREAD (MAXPRI * 3) 70 #define PRIBASE_NULL (MAXPRI * 4) 71 72 #define NQS 32 /* 32 run queues per priority */ 73 #define PPQ (MAXPRI / NQS) /* priorities per queue */ 74 #define PPQMASK (PPQ - 1) 75 76 /* 77 * NICEPPQ - number of nice units per priority queue 78 * ESTCPUPPQ - number of estcpu units per priority queue 79 * ESTCPUMAX - number of estcpu units 80 */ 81 #define NICEPPQ 2 82 #define ESTCPUPPQ 512 83 #define ESTCPUMAX (ESTCPUPPQ * NQS / 2) 84 #define BATCHMAX (ESTCPUFREQ * 30) 85 #define PRIO_RANGE (PRIO_MAX - PRIO_MIN + 1) /* 41 */ 86 87 #define ESTCPULIM(v) min((v), ESTCPUMAX) 88 89 TAILQ_HEAD(rq, lwp); 90 91 #define lwp_priority lwp_usdata.dfly.priority 92 #define lwp_forked lwp_usdata.dfly.forked 93 #define lwp_rqindex lwp_usdata.dfly.rqindex 94 #define lwp_estcpu lwp_usdata.dfly.estcpu 95 #define lwp_estfast lwp_usdata.dfly.estfast 96 #define lwp_uload lwp_usdata.dfly.uload 97 #define lwp_rqtype lwp_usdata.dfly.rqtype 98 #define lwp_qcpu lwp_usdata.dfly.qcpu 99 #define lwp_rrcount lwp_usdata.dfly.rrcount 100 101 struct usched_dfly_pcpu { 102 struct spinlock spin; 103 struct thread *helper_thread; 104 u_short scancpu; 105 short upri; 106 int uload; 107 int ucount; 108 struct lwp *uschedcp; 109 struct rq queues[NQS]; 110 struct rq rtqueues[NQS]; 111 struct rq idqueues[NQS]; 112 u_int32_t queuebits; 113 u_int32_t rtqueuebits; 114 u_int32_t idqueuebits; 115 int runqcount; 116 int cpuid; 117 cpumask_t cpumask; 118 cpu_node_t *cpunode; 119 }; 120 121 typedef struct usched_dfly_pcpu *dfly_pcpu_t; 122 123 static void dfly_acquire_curproc(struct lwp *lp); 124 static void dfly_release_curproc(struct lwp *lp); 125 static void dfly_select_curproc(globaldata_t gd); 126 static void dfly_setrunqueue(struct lwp *lp); 127 static void dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp); 128 static void dfly_schedulerclock(struct lwp *lp, sysclock_t period, 129 sysclock_t cpstamp); 130 static void dfly_recalculate_estcpu(struct lwp *lp); 131 static void dfly_resetpriority(struct lwp *lp); 132 static void dfly_forking(struct lwp *plp, struct lwp *lp); 133 static void dfly_exiting(struct lwp *lp, struct proc *); 134 static void dfly_uload_update(struct lwp *lp); 135 static void dfly_yield(struct lwp *lp); 136 static void dfly_changeqcpu_locked(struct lwp *lp, 137 dfly_pcpu_t dd, dfly_pcpu_t rdd); 138 static dfly_pcpu_t dfly_choose_best_queue(struct lwp *lp); 139 static dfly_pcpu_t dfly_choose_worst_queue(dfly_pcpu_t dd); 140 static dfly_pcpu_t dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp); 141 static void dfly_need_user_resched_remote(void *dummy); 142 static struct lwp *dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd, 143 struct lwp *chklp, int worst); 144 static void dfly_remrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp); 145 static void dfly_setrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp); 146 static void dfly_changedcpu(struct lwp *lp); 147 148 struct usched usched_dfly = { 149 { NULL }, 150 "dfly", "Original DragonFly Scheduler", 151 NULL, /* default registration */ 152 NULL, /* default deregistration */ 153 dfly_acquire_curproc, 154 dfly_release_curproc, 155 dfly_setrunqueue, 156 dfly_schedulerclock, 157 dfly_recalculate_estcpu, 158 dfly_resetpriority, 159 dfly_forking, 160 dfly_exiting, 161 dfly_uload_update, 162 NULL, /* setcpumask not supported */ 163 dfly_yield, 164 dfly_changedcpu 165 }; 166 167 /* 168 * We have NQS (32) run queues per scheduling class. For the normal 169 * class, there are 128 priorities scaled onto these 32 queues. New 170 * processes are added to the last entry in each queue, and processes 171 * are selected for running by taking them from the head and maintaining 172 * a simple FIFO arrangement. Realtime and Idle priority processes have 173 * and explicit 0-31 priority which maps directly onto their class queue 174 * index. When a queue has something in it, the corresponding bit is 175 * set in the queuebits variable, allowing a single read to determine 176 * the state of all 32 queues and then a ffs() to find the first busy 177 * queue. 178 */ 179 /* currently running a user process */ 180 static cpumask_t dfly_curprocmask = CPUMASK_INITIALIZER_ALLONES; 181 static cpumask_t dfly_rdyprocmask; /* ready to accept a user process */ 182 static volatile int dfly_ucount; /* total running on whole system */ 183 static struct usched_dfly_pcpu dfly_pcpu[MAXCPU]; 184 static struct sysctl_ctx_list usched_dfly_sysctl_ctx; 185 static struct sysctl_oid *usched_dfly_sysctl_tree; 186 187 /* Debug info exposed through debug.* sysctl */ 188 189 static int usched_dfly_debug = -1; 190 SYSCTL_INT(_debug, OID_AUTO, dfly_scdebug, CTLFLAG_RW, 191 &usched_dfly_debug, 0, 192 "Print debug information for this pid"); 193 194 static int usched_dfly_pid_debug = -1; 195 SYSCTL_INT(_debug, OID_AUTO, dfly_pid_debug, CTLFLAG_RW, 196 &usched_dfly_pid_debug, 0, 197 "Print KTR debug information for this pid"); 198 199 static int usched_dfly_chooser = 0; 200 SYSCTL_INT(_debug, OID_AUTO, dfly_chooser, CTLFLAG_RW, 201 &usched_dfly_chooser, 0, 202 "Print KTR debug information for this pid"); 203 204 /* 205 * Tunning usched_dfly - configurable through kern.usched_dfly. 206 * 207 * weight1 - Tries to keep threads on their current cpu. If you 208 * make this value too large the scheduler will not be 209 * able to load-balance large loads. 210 * 211 * weight2 - If non-zero, detects thread pairs undergoing synchronous 212 * communications and tries to move them closer together. 213 * Behavior is adjusted by bit 4 of features (0x10). 214 * 215 * WARNING! Weight2 is a ridiculously sensitive parameter, 216 * a small value is recommended. 217 * 218 * weight3 - Weighting based on the number of recently runnable threads 219 * on the userland scheduling queue (ignoring their loads). 220 * A nominal value here prevents high-priority (low-load) 221 * threads from accumulating on one cpu core when other 222 * cores are available. 223 * 224 * This value should be left fairly small relative to weight1 225 * and weight4. 226 * 227 * weight4 - Weighting based on other cpu queues being available 228 * or running processes with higher lwp_priority's. 229 * 230 * This allows a thread to migrate to another nearby cpu if it 231 * is unable to run on the current cpu based on the other cpu 232 * being idle or running a lower priority (higher lwp_priority) 233 * thread. This value should be large enough to override weight1 234 * 235 * features - These flags can be set or cleared to enable or disable various 236 * features. 237 * 238 * 0x01 Enable idle-cpu pulling (default) 239 * 0x02 Enable proactive pushing (default) 240 * 0x04 Enable rebalancing rover (default) 241 * 0x08 Enable more proactive pushing (default) 242 * 0x10 (flip weight2 limit on same cpu) (default) 243 * 0x20 choose best cpu for forked process 244 * 0x40 choose current cpu for forked process 245 * 0x80 choose random cpu for forked process (default) 246 */ 247 static int usched_dfly_smt = 0; 248 static int usched_dfly_cache_coherent = 0; 249 static int usched_dfly_weight1 = 200; /* keep thread on current cpu */ 250 static int usched_dfly_weight2 = 180; /* synchronous peer's current cpu */ 251 static int usched_dfly_weight3 = 40; /* number of threads on queue */ 252 static int usched_dfly_weight4 = 160; /* availability of idle cores */ 253 static int usched_dfly_features = 0x8F; /* allow pulls */ 254 static int usched_dfly_fast_resched = 0;/* delta priority / resched */ 255 static int usched_dfly_swmask = ~PPQMASK; /* allow pulls */ 256 static int usched_dfly_rrinterval = (ESTCPUFREQ + 9) / 10; 257 static int usched_dfly_decay = 8; 258 259 /* KTR debug printings */ 260 261 KTR_INFO_MASTER(usched); 262 263 #if !defined(KTR_USCHED_DFLY) 264 #define KTR_USCHED_DFLY KTR_ALL 265 #endif 266 267 KTR_INFO(KTR_USCHED_DFLY, usched, chooseproc, 0, 268 "USCHED_DFLY(chooseproc: pid %d, old_cpuid %d, curr_cpuid %d)", 269 pid_t pid, int old_cpuid, int curr); 270 271 /* 272 * This function is called when the kernel intends to return to userland. 273 * It is responsible for making the thread the current designated userland 274 * thread for this cpu, blocking if necessary. 275 * 276 * The kernel will not depress our LWKT priority until after we return, 277 * in case we have to shove over to another cpu. 278 * 279 * We must determine our thread's disposition before we switch away. This 280 * is very sensitive code. 281 * 282 * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE 283 * TO ANOTHER CPU! Because most of the kernel assumes that no migration will 284 * occur, this function is called only under very controlled circumstances. 285 */ 286 static void 287 dfly_acquire_curproc(struct lwp *lp) 288 { 289 globaldata_t gd; 290 dfly_pcpu_t dd; 291 dfly_pcpu_t rdd; 292 thread_t td; 293 int force_resched; 294 295 /* 296 * Make sure we aren't sitting on a tsleep queue. 297 */ 298 td = lp->lwp_thread; 299 crit_enter_quick(td); 300 if (td->td_flags & TDF_TSLEEPQ) 301 tsleep_remove(td); 302 dfly_recalculate_estcpu(lp); 303 304 gd = mycpu; 305 dd = &dfly_pcpu[gd->gd_cpuid]; 306 307 /* 308 * Process any pending interrupts/ipi's, then handle reschedule 309 * requests. dfly_release_curproc() will try to assign a new 310 * uschedcp that isn't us and otherwise NULL it out. 311 */ 312 force_resched = 0; 313 if ((td->td_mpflags & TDF_MP_BATCH_DEMARC) && 314 lp->lwp_rrcount >= usched_dfly_rrinterval / 2) { 315 force_resched = 1; 316 } 317 318 if (user_resched_wanted()) { 319 if (dd->uschedcp == lp) 320 force_resched = 1; 321 clear_user_resched(); 322 dfly_release_curproc(lp); 323 } 324 325 /* 326 * Loop until we are the current user thread. 327 * 328 * NOTE: dd spinlock not held at top of loop. 329 */ 330 if (dd->uschedcp == lp) 331 lwkt_yield_quick(); 332 333 while (dd->uschedcp != lp) { 334 lwkt_yield_quick(); 335 336 spin_lock(&dd->spin); 337 338 /* This lwp is an outcast; force reschedule. */ 339 if (__predict_false( 340 CPUMASK_TESTBIT(lp->lwp_cpumask, gd->gd_cpuid) == 0) && 341 (rdd = dfly_choose_best_queue(lp)) != dd) { 342 dfly_changeqcpu_locked(lp, dd, rdd); 343 spin_unlock(&dd->spin); 344 lwkt_deschedule(lp->lwp_thread); 345 dfly_setrunqueue_dd(rdd, lp); 346 lwkt_switch(); 347 gd = mycpu; 348 dd = &dfly_pcpu[gd->gd_cpuid]; 349 continue; 350 } 351 352 if (force_resched && 353 (usched_dfly_features & 0x08) && 354 (rdd = dfly_choose_best_queue(lp)) != dd) { 355 /* 356 * We are not or are no longer the current lwp and a 357 * forced reschedule was requested. Figure out the 358 * best cpu to run on (our current cpu will be given 359 * significant weight). 360 * 361 * (if a reschedule was not requested we want to 362 * move this step after the uschedcp tests). 363 */ 364 dfly_changeqcpu_locked(lp, dd, rdd); 365 spin_unlock(&dd->spin); 366 lwkt_deschedule(lp->lwp_thread); 367 dfly_setrunqueue_dd(rdd, lp); 368 lwkt_switch(); 369 gd = mycpu; 370 dd = &dfly_pcpu[gd->gd_cpuid]; 371 continue; 372 } 373 374 /* 375 * Either no reschedule was requested or the best queue was 376 * dd, and no current process has been selected. We can 377 * trivially become the current lwp on the current cpu. 378 */ 379 if (dd->uschedcp == NULL) { 380 atomic_clear_int(&lp->lwp_thread->td_mpflags, 381 TDF_MP_DIDYIELD); 382 ATOMIC_CPUMASK_ORBIT(dfly_curprocmask, gd->gd_cpuid); 383 dd->uschedcp = lp; 384 dd->upri = lp->lwp_priority; 385 KKASSERT(lp->lwp_qcpu == dd->cpuid); 386 spin_unlock(&dd->spin); 387 break; 388 } 389 390 /* 391 * Put us back on the same run queue unconditionally. 392 * 393 * Set rrinterval to force placement at end of queue. 394 * Select the worst queue to ensure we round-robin, 395 * but do not change estcpu. 396 */ 397 if (lp->lwp_thread->td_mpflags & TDF_MP_DIDYIELD) { 398 u_int32_t tsqbits; 399 400 switch(lp->lwp_rqtype) { 401 case RTP_PRIO_NORMAL: 402 tsqbits = dd->queuebits; 403 spin_unlock(&dd->spin); 404 405 lp->lwp_rrcount = usched_dfly_rrinterval; 406 if (tsqbits) 407 lp->lwp_rqindex = bsrl(tsqbits); 408 break; 409 default: 410 spin_unlock(&dd->spin); 411 break; 412 } 413 lwkt_deschedule(lp->lwp_thread); 414 dfly_setrunqueue_dd(dd, lp); 415 atomic_clear_int(&lp->lwp_thread->td_mpflags, 416 TDF_MP_DIDYIELD); 417 lwkt_switch(); 418 gd = mycpu; 419 dd = &dfly_pcpu[gd->gd_cpuid]; 420 continue; 421 } 422 423 /* 424 * Can we steal the current designated user thread? 425 * 426 * If we do the other thread will stall when it tries to 427 * return to userland, possibly rescheduling elsewhere. 428 * 429 * It is important to do a masked test to avoid the edge 430 * case where two near-equal-priority threads are constantly 431 * interrupting each other. 432 * 433 * In the exact match case another thread has already gained 434 * uschedcp and lowered its priority, if we steal it the 435 * other thread will stay stuck on the LWKT runq and not 436 * push to another cpu. So don't steal on equal-priority even 437 * though it might appear to be more beneficial due to not 438 * having to switch back to the other thread's context. 439 * 440 * usched_dfly_fast_resched requires that two threads be 441 * significantly far apart in priority in order to interrupt. 442 * 443 * If better but not sufficiently far apart, the current 444 * uschedcp will be interrupted at the next scheduler clock. 445 */ 446 if (dd->uschedcp && 447 (dd->upri & ~PPQMASK) > 448 (lp->lwp_priority & ~PPQMASK) + usched_dfly_fast_resched) { 449 dd->uschedcp = lp; 450 dd->upri = lp->lwp_priority; 451 KKASSERT(lp->lwp_qcpu == dd->cpuid); 452 spin_unlock(&dd->spin); 453 break; 454 } 455 /* 456 * We are not the current lwp, figure out the best cpu 457 * to run on (our current cpu will be given significant 458 * weight). Loop on cpu change. 459 */ 460 if ((usched_dfly_features & 0x02) && 461 force_resched == 0 && 462 (rdd = dfly_choose_best_queue(lp)) != dd) { 463 dfly_changeqcpu_locked(lp, dd, rdd); 464 spin_unlock(&dd->spin); 465 lwkt_deschedule(lp->lwp_thread); 466 dfly_setrunqueue_dd(rdd, lp); 467 lwkt_switch(); 468 gd = mycpu; 469 dd = &dfly_pcpu[gd->gd_cpuid]; 470 continue; 471 } 472 473 /* 474 * We cannot become the current lwp, place the lp on the 475 * run-queue of this or another cpu and deschedule ourselves. 476 * 477 * When we are reactivated we will have another chance. 478 * 479 * Reload after a switch or setrunqueue/switch possibly 480 * moved us to another cpu. 481 */ 482 spin_unlock(&dd->spin); 483 lwkt_deschedule(lp->lwp_thread); 484 dfly_setrunqueue_dd(dd, lp); 485 lwkt_switch(); 486 gd = mycpu; 487 dd = &dfly_pcpu[gd->gd_cpuid]; 488 } 489 490 /* 491 * Make sure upri is synchronized, then yield to LWKT threads as 492 * needed before returning. This could result in another reschedule. 493 * XXX 494 */ 495 crit_exit_quick(td); 496 497 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 498 } 499 500 /* 501 * DFLY_RELEASE_CURPROC 502 * 503 * This routine detaches the current thread from the userland scheduler, 504 * usually because the thread needs to run or block in the kernel (at 505 * kernel priority) for a while. 506 * 507 * This routine is also responsible for selecting a new thread to 508 * make the current thread. 509 * 510 * NOTE: This implementation differs from the dummy example in that 511 * dfly_select_curproc() is able to select the current process, whereas 512 * dummy_select_curproc() is not able to select the current process. 513 * This means we have to NULL out uschedcp. 514 * 515 * Additionally, note that we may already be on a run queue if releasing 516 * via the lwkt_switch() in dfly_setrunqueue(). 517 */ 518 static void 519 dfly_release_curproc(struct lwp *lp) 520 { 521 globaldata_t gd = mycpu; 522 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid]; 523 524 /* 525 * Make sure td_wakefromcpu is defaulted. This will be overwritten 526 * by wakeup(). 527 */ 528 if (dd->uschedcp == lp) { 529 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 530 spin_lock(&dd->spin); 531 if (dd->uschedcp == lp) { 532 dd->uschedcp = NULL; /* don't let lp be selected */ 533 dd->upri = PRIBASE_NULL; 534 ATOMIC_CPUMASK_NANDBIT(dfly_curprocmask, gd->gd_cpuid); 535 spin_unlock(&dd->spin); 536 dfly_select_curproc(gd); 537 } else { 538 spin_unlock(&dd->spin); 539 } 540 } 541 } 542 543 /* 544 * DFLY_SELECT_CURPROC 545 * 546 * Select a new current process for this cpu and clear any pending user 547 * reschedule request. The cpu currently has no current process. 548 * 549 * This routine is also responsible for equal-priority round-robining, 550 * typically triggered from dfly_schedulerclock(). In our dummy example 551 * all the 'user' threads are LWKT scheduled all at once and we just 552 * call lwkt_switch(). 553 * 554 * The calling process is not on the queue and cannot be selected. 555 */ 556 static 557 void 558 dfly_select_curproc(globaldata_t gd) 559 { 560 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid]; 561 struct lwp *nlp; 562 int cpuid = gd->gd_cpuid; 563 564 crit_enter_gd(gd); 565 566 spin_lock(&dd->spin); 567 nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0); 568 569 if (nlp) { 570 ATOMIC_CPUMASK_ORBIT(dfly_curprocmask, cpuid); 571 dd->upri = nlp->lwp_priority; 572 dd->uschedcp = nlp; 573 #if 0 574 dd->rrcount = 0; /* reset round robin */ 575 #endif 576 spin_unlock(&dd->spin); 577 lwkt_acquire(nlp->lwp_thread); 578 lwkt_schedule(nlp->lwp_thread); 579 } else { 580 spin_unlock(&dd->spin); 581 } 582 crit_exit_gd(gd); 583 } 584 585 /* 586 * Place the specified lwp on the user scheduler's run queue. This routine 587 * must be called with the thread descheduled. The lwp must be runnable. 588 * It must not be possible for anyone else to explicitly schedule this thread. 589 * 590 * The thread may be the current thread as a special case. 591 */ 592 static void 593 dfly_setrunqueue(struct lwp *lp) 594 { 595 dfly_pcpu_t dd; 596 dfly_pcpu_t rdd; 597 598 /* 599 * First validate the process LWKT state. 600 */ 601 KASSERT(lp->lwp_stat == LSRUN, ("setrunqueue: lwp not LSRUN")); 602 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0, 603 ("lwp %d/%d already on runq! flag %08x/%08x", lp->lwp_proc->p_pid, 604 lp->lwp_tid, lp->lwp_proc->p_flags, lp->lwp_flags)); 605 KKASSERT((lp->lwp_thread->td_flags & TDF_RUNQ) == 0); 606 607 /* 608 * NOTE: dd/rdd do not necessarily represent the current cpu. 609 * Instead they may represent the cpu the thread was last 610 * scheduled on or inherited by its parent. 611 */ 612 dd = &dfly_pcpu[lp->lwp_qcpu]; 613 rdd = dd; 614 615 /* 616 * This process is not supposed to be scheduled anywhere or assigned 617 * as the current process anywhere. Assert the condition. 618 */ 619 KKASSERT(rdd->uschedcp != lp); 620 621 /* 622 * Ok, we have to setrunqueue some target cpu and request a reschedule 623 * if necessary. 624 * 625 * We have to choose the best target cpu. It might not be the current 626 * target even if the current cpu has no running user thread (for 627 * example, because the current cpu might be a hyperthread and its 628 * sibling has a thread assigned). 629 * 630 * If we just forked it is most optimal to run the child on the same 631 * cpu just in case the parent decides to wait for it (thus getting 632 * off that cpu). As long as there is nothing else runnable on the 633 * cpu, that is. If we did this unconditionally a parent forking 634 * multiple children before waiting (e.g. make -j N) leaves other 635 * cpus idle that could be working. 636 */ 637 if (lp->lwp_forked) { 638 lp->lwp_forked = 0; 639 if (usched_dfly_features & 0x20) 640 rdd = dfly_choose_best_queue(lp); 641 else if (usched_dfly_features & 0x40) 642 rdd = &dfly_pcpu[lp->lwp_qcpu]; 643 else if (usched_dfly_features & 0x80) 644 rdd = dfly_choose_queue_simple(rdd, lp); 645 else if (dfly_pcpu[lp->lwp_qcpu].runqcount) 646 rdd = dfly_choose_best_queue(lp); 647 else 648 rdd = &dfly_pcpu[lp->lwp_qcpu]; 649 } else { 650 rdd = dfly_choose_best_queue(lp); 651 /* rdd = &dfly_pcpu[lp->lwp_qcpu]; */ 652 } 653 if (lp->lwp_qcpu != rdd->cpuid) { 654 spin_lock(&dd->spin); 655 dfly_changeqcpu_locked(lp, dd, rdd); 656 spin_unlock(&dd->spin); 657 } 658 dfly_setrunqueue_dd(rdd, lp); 659 } 660 661 /* 662 * Change qcpu to rdd->cpuid. The dd the lp is CURRENTLY on must be 663 * spin-locked on-call. rdd does not have to be. 664 */ 665 static void 666 dfly_changeqcpu_locked(struct lwp *lp, dfly_pcpu_t dd, dfly_pcpu_t rdd) 667 { 668 if (lp->lwp_qcpu != rdd->cpuid) { 669 if (lp->lwp_mpflags & LWP_MP_ULOAD) { 670 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD); 671 atomic_add_int(&dd->uload, -lp->lwp_uload); 672 atomic_add_int(&dd->ucount, -1); 673 atomic_add_int(&dfly_ucount, -1); 674 } 675 lp->lwp_qcpu = rdd->cpuid; 676 } 677 } 678 679 /* 680 * Place lp on rdd's runqueue. Nothing is locked on call. This function 681 * also performs all necessary ancillary notification actions. 682 */ 683 static void 684 dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp) 685 { 686 globaldata_t rgd; 687 688 /* 689 * We might be moving the lp to another cpu's run queue, and once 690 * on the runqueue (even if it is our cpu's), another cpu can rip 691 * it away from us. 692 * 693 * TDF_MIGRATING might already be set if this is part of a 694 * remrunqueue+setrunqueue sequence. 695 */ 696 if ((lp->lwp_thread->td_flags & TDF_MIGRATING) == 0) 697 lwkt_giveaway(lp->lwp_thread); 698 699 rgd = globaldata_find(rdd->cpuid); 700 701 /* 702 * We lose control of the lp the moment we release the spinlock 703 * after having placed it on the queue. i.e. another cpu could pick 704 * it up, or it could exit, or its priority could be further 705 * adjusted, or something like that. 706 * 707 * WARNING! rdd can point to a foreign cpu! 708 */ 709 spin_lock(&rdd->spin); 710 dfly_setrunqueue_locked(rdd, lp); 711 712 /* 713 * Potentially interrupt the currently-running thread 714 */ 715 if ((rdd->upri & ~PPQMASK) <= (lp->lwp_priority & ~PPQMASK)) { 716 /* 717 * Currently running thread is better or same, do not 718 * interrupt. 719 */ 720 spin_unlock(&rdd->spin); 721 } else if ((rdd->upri & ~PPQMASK) <= (lp->lwp_priority & ~PPQMASK) + 722 usched_dfly_fast_resched) { 723 /* 724 * Currently running thread is not better, but not so bad 725 * that we need to interrupt it. Let it run for one more 726 * scheduler tick. 727 */ 728 if (rdd->uschedcp && 729 rdd->uschedcp->lwp_rrcount < usched_dfly_rrinterval) { 730 rdd->uschedcp->lwp_rrcount = usched_dfly_rrinterval - 1; 731 } 732 spin_unlock(&rdd->spin); 733 } else if (rgd == mycpu) { 734 /* 735 * We should interrupt the currently running thread, which 736 * is on the current cpu. However, if DIDYIELD is set we 737 * round-robin unconditionally and do not interrupt it. 738 */ 739 spin_unlock(&rdd->spin); 740 if (rdd->uschedcp == NULL) 741 wakeup_mycpu(rdd->helper_thread); /* XXX */ 742 if ((lp->lwp_thread->td_mpflags & TDF_MP_DIDYIELD) == 0) 743 need_user_resched(); 744 } else { 745 /* 746 * We should interrupt the currently running thread, which 747 * is on a different cpu. 748 */ 749 spin_unlock(&rdd->spin); 750 lwkt_send_ipiq(rgd, dfly_need_user_resched_remote, NULL); 751 } 752 } 753 754 /* 755 * This routine is called from a systimer IPI. It MUST be MP-safe and 756 * the BGL IS NOT HELD ON ENTRY. This routine is called at ESTCPUFREQ on 757 * each cpu. 758 */ 759 static 760 void 761 dfly_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp) 762 { 763 globaldata_t gd = mycpu; 764 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid]; 765 766 /* 767 * Spinlocks also hold a critical section so there should not be 768 * any active. 769 */ 770 KKASSERT(gd->gd_spinlocks == 0 || dumping); 771 772 /* 773 * If lp is NULL we might be contended and lwkt_switch() may have 774 * cycled into the idle thread. Apply the tick to the current 775 * process on this cpu if it is contended. 776 */ 777 if (gd->gd_curthread == &gd->gd_idlethread) { 778 lp = dd->uschedcp; 779 if (lp && (lp->lwp_thread == NULL || 780 lp->lwp_thread->td_contended == 0)) { 781 lp = NULL; 782 } 783 } 784 785 /* 786 * Dock thread for tick 787 */ 788 if (lp) { 789 /* 790 * Do we need to round-robin? We round-robin 10 times a 791 * second. This should only occur for cpu-bound batch 792 * processes. 793 */ 794 if (++lp->lwp_rrcount >= usched_dfly_rrinterval) { 795 lp->lwp_thread->td_wakefromcpu = -1; 796 need_user_resched(); 797 } 798 799 /* 800 * Adjust estcpu upward using a real time equivalent 801 * calculation, and recalculate lp's priority. 802 */ 803 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + 804 ESTCPUMAX / ESTCPUFREQ + 1); 805 dfly_resetpriority(lp); 806 } 807 808 /* 809 * Rebalance two cpus every 8 ticks, pulling the worst thread 810 * from the worst cpu's queue into a rotating cpu number. 811 * 812 * This mechanic is needed because the push algorithms can 813 * steady-state in an non-optimal configuration. We need to mix it 814 * up a little, even if it means breaking up a paired thread, so 815 * the push algorithms can rebalance the degenerate conditions. 816 * This portion of the algorithm exists to ensure stability at the 817 * selected weightings. 818 * 819 * Because we might be breaking up optimal conditions we do not want 820 * to execute this too quickly, hence we only rebalance approximately 821 * ~7-8 times per second. The push's, on the otherhand, are capable 822 * moving threads to other cpus at a much higher rate. 823 * 824 * We choose the most heavily loaded thread from the worst queue 825 * in order to ensure that multiple heavy-weight threads on the same 826 * queue get broken up, and also because these threads are the most 827 * likely to be able to remain in place. Hopefully then any pairings, 828 * if applicable, migrate to where these threads are. 829 */ 830 if ((usched_dfly_features & 0x04) && 831 ((u_int)sched_ticks & 7) == 0 && 832 (u_int)sched_ticks / 8 % ncpus == gd->gd_cpuid) { 833 /* 834 * Our cpu is up. 835 */ 836 struct lwp *nlp; 837 dfly_pcpu_t rdd; 838 839 rdd = dfly_choose_worst_queue(dd); 840 if (rdd) { 841 spin_lock(&dd->spin); 842 if (spin_trylock(&rdd->spin)) { 843 nlp = dfly_chooseproc_locked(rdd, dd, NULL, 1); 844 spin_unlock(&rdd->spin); 845 if (nlp == NULL) 846 spin_unlock(&dd->spin); 847 } else { 848 spin_unlock(&dd->spin); 849 nlp = NULL; 850 } 851 } else { 852 nlp = NULL; 853 } 854 /* dd->spin held if nlp != NULL */ 855 856 /* 857 * Either schedule it or add it to our queue. 858 */ 859 if (nlp && 860 (nlp->lwp_priority & ~PPQMASK) < (dd->upri & ~PPQMASK)) { 861 ATOMIC_CPUMASK_ORMASK(dfly_curprocmask, dd->cpumask); 862 dd->upri = nlp->lwp_priority; 863 dd->uschedcp = nlp; 864 #if 0 865 dd->rrcount = 0; /* reset round robin */ 866 #endif 867 spin_unlock(&dd->spin); 868 lwkt_acquire(nlp->lwp_thread); 869 lwkt_schedule(nlp->lwp_thread); 870 } else if (nlp) { 871 dfly_setrunqueue_locked(dd, nlp); 872 spin_unlock(&dd->spin); 873 } 874 } 875 } 876 877 /* 878 * Called from acquire and from kern_synch's one-second timer (one of the 879 * callout helper threads) with a critical section held. 880 * 881 * Adjust p_estcpu based on our single-cpu load, p_nice, and compensate for 882 * overall system load. 883 * 884 * Note that no recalculation occurs for a process which sleeps and wakes 885 * up in the same tick. That is, a system doing thousands of context 886 * switches per second will still only do serious estcpu calculations 887 * ESTCPUFREQ times per second. 888 */ 889 static 890 void 891 dfly_recalculate_estcpu(struct lwp *lp) 892 { 893 globaldata_t gd = mycpu; 894 sysclock_t cpbase; 895 sysclock_t ttlticks; 896 int estcpu; 897 int decay_factor; 898 int ucount; 899 900 /* 901 * We have to subtract periodic to get the last schedclock 902 * timeout time, otherwise we would get the upcoming timeout. 903 * Keep in mind that a process can migrate between cpus and 904 * while the scheduler clock should be very close, boundary 905 * conditions could lead to a small negative delta. 906 */ 907 cpbase = gd->gd_schedclock.time - gd->gd_schedclock.periodic; 908 909 if (lp->lwp_slptime > 1) { 910 /* 911 * Too much time has passed, do a coarse correction. 912 */ 913 lp->lwp_estcpu = lp->lwp_estcpu >> 1; 914 dfly_resetpriority(lp); 915 lp->lwp_cpbase = cpbase; 916 lp->lwp_cpticks = 0; 917 lp->lwp_estfast = 0; 918 } else if (lp->lwp_cpbase != cpbase) { 919 /* 920 * Adjust estcpu if we are in a different tick. Don't waste 921 * time if we are in the same tick. 922 * 923 * First calculate the number of ticks in the measurement 924 * interval. The ttlticks calculation can wind up 0 due to 925 * a bug in the handling of lwp_slptime (as yet not found), 926 * so make sure we do not get a divide by 0 panic. 927 */ 928 ttlticks = (cpbase - lp->lwp_cpbase) / 929 gd->gd_schedclock.periodic; 930 if ((ssysclock_t)ttlticks < 0) { 931 ttlticks = 0; 932 lp->lwp_cpbase = cpbase; 933 } 934 if (ttlticks == 0) 935 return; 936 updatepcpu(lp, lp->lwp_cpticks, ttlticks); 937 938 /* 939 * Calculate the percentage of one cpu being used then 940 * compensate for any system load in excess of ncpus. 941 * 942 * For example, if we have 8 cores and 16 running cpu-bound 943 * processes then all things being equal each process will 944 * get 50% of one cpu. We need to pump this value back 945 * up to 100% so the estcpu calculation properly adjusts 946 * the process's dynamic priority. 947 * 948 * estcpu is scaled by ESTCPUMAX, pctcpu is scaled by FSCALE. 949 */ 950 estcpu = (lp->lwp_pctcpu * ESTCPUMAX) >> FSHIFT; 951 ucount = dfly_ucount; 952 if (ucount > ncpus) { 953 estcpu += estcpu * (ucount - ncpus) / ncpus; 954 } 955 956 if (usched_dfly_debug == lp->lwp_proc->p_pid) { 957 kprintf("pid %d lwp %p estcpu %3d %3d cp %d/%d", 958 lp->lwp_proc->p_pid, lp, 959 estcpu, lp->lwp_estcpu, 960 lp->lwp_cpticks, ttlticks); 961 } 962 963 /* 964 * Adjust lp->lwp_esetcpu. The decay factor determines how 965 * quickly lwp_estcpu collapses to its realtime calculation. 966 * A slower collapse gives us a more accurate number over 967 * the long term but can create problems with bursty threads 968 * or threads which become cpu hogs. 969 * 970 * To solve this problem, newly started lwps and lwps which 971 * are restarting after having been asleep for a while are 972 * given a much, much faster decay in order to quickly 973 * detect whether they become cpu-bound. 974 * 975 * NOTE: p_nice is accounted for in dfly_resetpriority(), 976 * and not here, but we must still ensure that a 977 * cpu-bound nice -20 process does not completely 978 * override a cpu-bound nice +20 process. 979 * 980 * NOTE: We must use ESTCPULIM() here to deal with any 981 * overshoot. 982 */ 983 decay_factor = usched_dfly_decay; 984 if (decay_factor < 1) 985 decay_factor = 1; 986 if (decay_factor > 1024) 987 decay_factor = 1024; 988 989 if (lp->lwp_estfast < usched_dfly_decay) { 990 ++lp->lwp_estfast; 991 lp->lwp_estcpu = ESTCPULIM( 992 (lp->lwp_estcpu * lp->lwp_estfast + estcpu) / 993 (lp->lwp_estfast + 1)); 994 } else { 995 lp->lwp_estcpu = ESTCPULIM( 996 (lp->lwp_estcpu * decay_factor + estcpu) / 997 (decay_factor + 1)); 998 } 999 1000 if (usched_dfly_debug == lp->lwp_proc->p_pid) 1001 kprintf(" finalestcpu %d\n", lp->lwp_estcpu); 1002 dfly_resetpriority(lp); 1003 lp->lwp_cpbase += ttlticks * gd->gd_schedclock.periodic; 1004 lp->lwp_cpticks = 0; 1005 } 1006 } 1007 1008 /* 1009 * Compute the priority of a process when running in user mode. 1010 * Arrange to reschedule if the resulting priority is better 1011 * than that of the current process. 1012 * 1013 * This routine may be called with any process. 1014 * 1015 * This routine is called by fork1() for initial setup with the process of 1016 * the run queue, and also may be called normally with the process on or 1017 * off the run queue. 1018 */ 1019 static void 1020 dfly_resetpriority(struct lwp *lp) 1021 { 1022 dfly_pcpu_t rdd; 1023 int newpriority; 1024 u_short newrqtype; 1025 int rcpu; 1026 int checkpri; 1027 int estcpu; 1028 int delta_uload; 1029 1030 crit_enter(); 1031 1032 /* 1033 * Lock the scheduler (lp) belongs to. This can be on a different 1034 * cpu. Handle races. This loop breaks out with the appropriate 1035 * rdd locked. 1036 */ 1037 for (;;) { 1038 rcpu = lp->lwp_qcpu; 1039 cpu_ccfence(); 1040 rdd = &dfly_pcpu[rcpu]; 1041 spin_lock(&rdd->spin); 1042 if (rcpu == lp->lwp_qcpu) 1043 break; 1044 spin_unlock(&rdd->spin); 1045 } 1046 1047 /* 1048 * Calculate the new priority and queue type 1049 */ 1050 newrqtype = lp->lwp_rtprio.type; 1051 1052 switch(newrqtype) { 1053 case RTP_PRIO_REALTIME: 1054 case RTP_PRIO_FIFO: 1055 newpriority = PRIBASE_REALTIME + 1056 (lp->lwp_rtprio.prio & PRIMASK); 1057 break; 1058 case RTP_PRIO_NORMAL: 1059 /* 1060 * 1061 */ 1062 estcpu = lp->lwp_estcpu; 1063 1064 /* 1065 * p_nice piece Adds (0-40) * 2 0-80 1066 * estcpu Adds 16384 * 4 / 512 0-128 1067 */ 1068 newpriority = (lp->lwp_proc->p_nice - PRIO_MIN) * PPQ / NICEPPQ; 1069 newpriority += estcpu * PPQ / ESTCPUPPQ; 1070 newpriority = newpriority * MAXPRI / 1071 (PRIO_RANGE * PPQ / NICEPPQ + 1072 ESTCPUMAX * PPQ / ESTCPUPPQ); 1073 newpriority = PRIBASE_NORMAL + (newpriority & PRIMASK); 1074 break; 1075 case RTP_PRIO_IDLE: 1076 newpriority = PRIBASE_IDLE + (lp->lwp_rtprio.prio & PRIMASK); 1077 break; 1078 case RTP_PRIO_THREAD: 1079 newpriority = PRIBASE_THREAD + (lp->lwp_rtprio.prio & PRIMASK); 1080 break; 1081 default: 1082 panic("Bad RTP_PRIO %d", newrqtype); 1083 /* NOT REACHED */ 1084 } 1085 1086 /* 1087 * The LWKT scheduler doesn't dive usched structures, give it a hint 1088 * on the relative priority of user threads running in the kernel. 1089 * The LWKT scheduler will always ensure that a user thread running 1090 * in the kernel will get cpu some time, regardless of its upri, 1091 * but can decide not to instantly switch from one kernel or user 1092 * mode user thread to a kernel-mode user thread when it has a less 1093 * desireable user priority. 1094 * 1095 * td_upri has normal sense (higher values are more desireable), so 1096 * negate it. 1097 */ 1098 lp->lwp_thread->td_upri = -(newpriority & usched_dfly_swmask); 1099 1100 /* 1101 * The newpriority incorporates the queue type so do a simple masked 1102 * check to determine if the process has moved to another queue. If 1103 * it has, and it is currently on a run queue, then move it. 1104 * 1105 * Since uload is ~PPQMASK masked, no modifications are necessary if 1106 * we end up in the same run queue. 1107 * 1108 * Reset rrcount if moving to a higher-priority queue, otherwise 1109 * retain rrcount. 1110 */ 1111 if ((lp->lwp_priority ^ newpriority) & ~PPQMASK) { 1112 if (lp->lwp_priority < newpriority) 1113 lp->lwp_rrcount = 0; 1114 if (lp->lwp_mpflags & LWP_MP_ONRUNQ) { 1115 dfly_remrunqueue_locked(rdd, lp); 1116 lp->lwp_priority = newpriority; 1117 lp->lwp_rqtype = newrqtype; 1118 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ; 1119 dfly_setrunqueue_locked(rdd, lp); 1120 checkpri = 1; 1121 } else { 1122 lp->lwp_priority = newpriority; 1123 lp->lwp_rqtype = newrqtype; 1124 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ; 1125 checkpri = 0; 1126 } 1127 } else { 1128 /* 1129 * In the same PPQ, uload cannot change. 1130 */ 1131 lp->lwp_priority = newpriority; 1132 checkpri = 1; 1133 rcpu = -1; 1134 } 1135 1136 /* 1137 * Adjust effective load. 1138 * 1139 * Calculate load then scale up or down geometrically based on p_nice. 1140 * Processes niced up (positive) are less important, and processes 1141 * niced downard (negative) are more important. The higher the uload, 1142 * the more important the thread. 1143 */ 1144 /* 0-511, 0-100% cpu */ 1145 delta_uload = lp->lwp_estcpu / NQS; 1146 delta_uload -= delta_uload * lp->lwp_proc->p_nice / (PRIO_MAX + 1); 1147 1148 1149 delta_uload -= lp->lwp_uload; 1150 lp->lwp_uload += delta_uload; 1151 if (lp->lwp_mpflags & LWP_MP_ULOAD) 1152 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload, delta_uload); 1153 1154 /* 1155 * Determine if we need to reschedule the target cpu. This only 1156 * occurs if the LWP is already on a scheduler queue, which means 1157 * that idle cpu notification has already occured. At most we 1158 * need only issue a need_user_resched() on the appropriate cpu. 1159 * 1160 * The LWP may be owned by a CPU different from the current one, 1161 * in which case dd->uschedcp may be modified without an MP lock 1162 * or a spinlock held. The worst that happens is that the code 1163 * below causes a spurious need_user_resched() on the target CPU 1164 * and dd->pri to be wrong for a short period of time, both of 1165 * which are harmless. 1166 * 1167 * If checkpri is 0 we are adjusting the priority of the current 1168 * process, possibly higher (less desireable), so ignore the upri 1169 * check which will fail in that case. 1170 */ 1171 if (rcpu >= 0) { 1172 if (CPUMASK_TESTBIT(dfly_rdyprocmask, rcpu) && 1173 (checkpri == 0 || 1174 (rdd->upri & ~PRIMASK) > 1175 (lp->lwp_priority & ~PRIMASK))) { 1176 if (rcpu == mycpu->gd_cpuid) { 1177 spin_unlock(&rdd->spin); 1178 need_user_resched(); 1179 } else { 1180 spin_unlock(&rdd->spin); 1181 lwkt_send_ipiq(globaldata_find(rcpu), 1182 dfly_need_user_resched_remote, 1183 NULL); 1184 } 1185 } else { 1186 spin_unlock(&rdd->spin); 1187 } 1188 } else { 1189 spin_unlock(&rdd->spin); 1190 } 1191 crit_exit(); 1192 } 1193 1194 static 1195 void 1196 dfly_yield(struct lwp *lp) 1197 { 1198 if (lp->lwp_qcpu != mycpu->gd_cpuid) 1199 return; 1200 KKASSERT(lp == curthread->td_lwp); 1201 1202 /* 1203 * Don't set need_user_resched() or mess with rrcount or anything. 1204 * the TDF flag will override everything as long as we release. 1205 */ 1206 atomic_set_int(&lp->lwp_thread->td_mpflags, TDF_MP_DIDYIELD); 1207 dfly_release_curproc(lp); 1208 } 1209 1210 /* 1211 * Thread was forcefully migrated to another cpu. Normally forced migrations 1212 * are used for iterations and the kernel returns to the original cpu before 1213 * returning and this is not needed. However, if the kernel migrates a 1214 * thread to another cpu and wants to leave it there, it has to call this 1215 * scheduler helper. 1216 * 1217 * Note that the lwkt_migratecpu() function also released the thread, so 1218 * we don't have to worry about that. 1219 */ 1220 static 1221 void 1222 dfly_changedcpu(struct lwp *lp) 1223 { 1224 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu]; 1225 dfly_pcpu_t rdd = &dfly_pcpu[mycpu->gd_cpuid]; 1226 1227 if (dd != rdd) { 1228 spin_lock(&dd->spin); 1229 dfly_changeqcpu_locked(lp, dd, rdd); 1230 spin_unlock(&dd->spin); 1231 } 1232 } 1233 1234 /* 1235 * Called from fork1() when a new child process is being created. 1236 * 1237 * Give the child process an initial estcpu that is more batch then 1238 * its parent and dock the parent for the fork (but do not 1239 * reschedule the parent). 1240 * 1241 * fast 1242 * 1243 * XXX lwp should be "spawning" instead of "forking" 1244 */ 1245 static void 1246 dfly_forking(struct lwp *plp, struct lwp *lp) 1247 { 1248 /* 1249 * Put the child 4 queue slots (out of 32) higher than the parent 1250 * (less desireable than the parent). 1251 */ 1252 lp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ * 4); 1253 lp->lwp_forked = 1; 1254 lp->lwp_estfast = 0; 1255 1256 /* 1257 * Even though the lp will be scheduled specially the first time 1258 * due to lp->lwp_forked, it is important to initialize lwp_qcpu 1259 * to avoid favoring a fixed cpu. 1260 */ 1261 #if 0 1262 static uint16_t save_cpu; 1263 lp->lwp_qcpu = ++save_cpu % ncpus; 1264 #else 1265 lp->lwp_qcpu = plp->lwp_qcpu; 1266 if (CPUMASK_TESTBIT(lp->lwp_cpumask, lp->lwp_qcpu) == 0) 1267 lp->lwp_qcpu = BSFCPUMASK(lp->lwp_cpumask); 1268 #endif 1269 1270 /* 1271 * Dock the parent a cost for the fork, protecting us from fork 1272 * bombs. If the parent is forking quickly make the child more 1273 * batchy. 1274 */ 1275 plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ / 16); 1276 } 1277 1278 /* 1279 * Called when a lwp is being removed from this scheduler, typically 1280 * during lwp_exit(). We have to clean out any ULOAD accounting before 1281 * we can let the lp go. The dd->spin lock is not needed for uload 1282 * updates. 1283 * 1284 * Scheduler dequeueing has already occurred, no further action in that 1285 * regard is needed. 1286 */ 1287 static void 1288 dfly_exiting(struct lwp *lp, struct proc *child_proc) 1289 { 1290 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu]; 1291 1292 if (lp->lwp_mpflags & LWP_MP_ULOAD) { 1293 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD); 1294 atomic_add_int(&dd->uload, -lp->lwp_uload); 1295 atomic_add_int(&dd->ucount, -1); 1296 atomic_add_int(&dfly_ucount, -1); 1297 } 1298 } 1299 1300 /* 1301 * This function cannot block in any way, but spinlocks are ok. 1302 * 1303 * Update the uload based on the state of the thread (whether it is going 1304 * to sleep or running again). The uload is meant to be a longer-term 1305 * load and not an instantanious load. 1306 */ 1307 static void 1308 dfly_uload_update(struct lwp *lp) 1309 { 1310 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu]; 1311 1312 if (lp->lwp_thread->td_flags & TDF_RUNQ) { 1313 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) { 1314 spin_lock(&dd->spin); 1315 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) { 1316 atomic_set_int(&lp->lwp_mpflags, 1317 LWP_MP_ULOAD); 1318 atomic_add_int(&dd->uload, lp->lwp_uload); 1319 atomic_add_int(&dd->ucount, 1); 1320 atomic_add_int(&dfly_ucount, 1); 1321 } 1322 spin_unlock(&dd->spin); 1323 } 1324 } else if (lp->lwp_slptime > 0) { 1325 if (lp->lwp_mpflags & LWP_MP_ULOAD) { 1326 spin_lock(&dd->spin); 1327 if (lp->lwp_mpflags & LWP_MP_ULOAD) { 1328 atomic_clear_int(&lp->lwp_mpflags, 1329 LWP_MP_ULOAD); 1330 atomic_add_int(&dd->uload, -lp->lwp_uload); 1331 atomic_add_int(&dd->ucount, -1); 1332 atomic_add_int(&dfly_ucount, -1); 1333 } 1334 spin_unlock(&dd->spin); 1335 } 1336 } 1337 } 1338 1339 /* 1340 * chooseproc() is called when a cpu needs a user process to LWKT schedule, 1341 * it selects a user process and returns it. If chklp is non-NULL and chklp 1342 * has a better or equal priority then the process that would otherwise be 1343 * chosen, NULL is returned. 1344 * 1345 * Until we fix the RUNQ code the chklp test has to be strict or we may 1346 * bounce between processes trying to acquire the current process designation. 1347 * 1348 * Must be called with rdd->spin locked. The spinlock is left intact through 1349 * the entire routine. dd->spin does not have to be locked. 1350 * 1351 * If worst is non-zero this function finds the worst thread instead of the 1352 * best thread (used by the schedulerclock-based rover). 1353 */ 1354 static 1355 struct lwp * 1356 dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd, 1357 struct lwp *chklp, int worst) 1358 { 1359 struct lwp *lp; 1360 struct rq *q; 1361 u_int32_t *which; 1362 u_int32_t pri; 1363 u_int32_t rtqbits; 1364 u_int32_t tsqbits; 1365 u_int32_t idqbits; 1366 1367 rtqbits = rdd->rtqueuebits; 1368 tsqbits = rdd->queuebits; 1369 idqbits = rdd->idqueuebits; 1370 1371 if (worst) { 1372 if (idqbits) { 1373 pri = bsrl(idqbits); 1374 q = &rdd->idqueues[pri]; 1375 which = &rdd->idqueuebits; 1376 } else if (tsqbits) { 1377 pri = bsrl(tsqbits); 1378 q = &rdd->queues[pri]; 1379 which = &rdd->queuebits; 1380 } else if (rtqbits) { 1381 pri = bsrl(rtqbits); 1382 q = &rdd->rtqueues[pri]; 1383 which = &rdd->rtqueuebits; 1384 } else { 1385 return (NULL); 1386 } 1387 lp = TAILQ_LAST(q, rq); 1388 } else { 1389 if (rtqbits) { 1390 pri = bsfl(rtqbits); 1391 q = &rdd->rtqueues[pri]; 1392 which = &rdd->rtqueuebits; 1393 } else if (tsqbits) { 1394 pri = bsfl(tsqbits); 1395 q = &rdd->queues[pri]; 1396 which = &rdd->queuebits; 1397 } else if (idqbits) { 1398 pri = bsfl(idqbits); 1399 q = &rdd->idqueues[pri]; 1400 which = &rdd->idqueuebits; 1401 } else { 1402 return (NULL); 1403 } 1404 lp = TAILQ_FIRST(q); 1405 } 1406 KASSERT(lp, ("chooseproc: no lwp on busy queue")); 1407 1408 /* 1409 * If the passed lwp <chklp> is reasonably close to the selected 1410 * lwp <lp>, return NULL (indicating that <chklp> should be kept). 1411 * 1412 * Note that we must error on the side of <chklp> to avoid bouncing 1413 * between threads in the acquire code. 1414 */ 1415 if (chklp) { 1416 if (chklp->lwp_priority < lp->lwp_priority + PPQ) 1417 return(NULL); 1418 } 1419 1420 KTR_COND_LOG(usched_chooseproc, 1421 lp->lwp_proc->p_pid == usched_dfly_pid_debug, 1422 lp->lwp_proc->p_pid, 1423 lp->lwp_thread->td_gd->gd_cpuid, 1424 mycpu->gd_cpuid); 1425 1426 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) != 0, ("not on runq6!")); 1427 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1428 TAILQ_REMOVE(q, lp, lwp_procq); 1429 --rdd->runqcount; 1430 if (TAILQ_EMPTY(q)) 1431 *which &= ~(1 << pri); 1432 1433 /* 1434 * If we are choosing a process from rdd with the intent to 1435 * move it to dd, lwp_qcpu must be adjusted while rdd's spinlock 1436 * is still held. 1437 */ 1438 if (rdd != dd) { 1439 if (lp->lwp_mpflags & LWP_MP_ULOAD) { 1440 atomic_add_int(&rdd->uload, -lp->lwp_uload); 1441 atomic_add_int(&rdd->ucount, -1); 1442 atomic_add_int(&dfly_ucount, -1); 1443 } 1444 lp->lwp_qcpu = dd->cpuid; 1445 atomic_add_int(&dd->uload, lp->lwp_uload); 1446 atomic_add_int(&dd->ucount, 1); 1447 atomic_add_int(&dfly_ucount, 1); 1448 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD); 1449 } 1450 return lp; 1451 } 1452 1453 /* 1454 * USED TO PUSH RUNNABLE LWPS TO THE LEAST LOADED CPU. 1455 * 1456 * Choose a cpu node to schedule lp on, hopefully nearby its current 1457 * node. 1458 * 1459 * We give the current node a modest advantage for obvious reasons. 1460 * 1461 * We also give the node the thread was woken up FROM a slight advantage 1462 * in order to try to schedule paired threads which synchronize/block waiting 1463 * for each other fairly close to each other. Similarly in a network setting 1464 * this feature will also attempt to place a user process near the kernel 1465 * protocol thread that is feeding it data. THIS IS A CRITICAL PART of the 1466 * algorithm as it heuristically groups synchronizing processes for locality 1467 * of reference in multi-socket systems. 1468 * 1469 * We check against running processes and give a big advantage if there 1470 * are none running. 1471 * 1472 * The caller will normally dfly_setrunqueue() lp on the returned queue. 1473 * 1474 * When the topology is known choose a cpu whos group has, in aggregate, 1475 * has the lowest weighted load. 1476 */ 1477 static 1478 dfly_pcpu_t 1479 dfly_choose_best_queue(struct lwp *lp) 1480 { 1481 cpumask_t wakemask; 1482 cpumask_t mask; 1483 cpu_node_t *cpup; 1484 cpu_node_t *cpun; 1485 cpu_node_t *cpub; 1486 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu]; 1487 dfly_pcpu_t rdd; 1488 int wakecpu; 1489 int cpuid; 1490 int n; 1491 int count; 1492 int load; 1493 int lowest_load; 1494 1495 /* 1496 * When the topology is unknown choose a random cpu that is hopefully 1497 * idle. 1498 */ 1499 if (dd->cpunode == NULL) 1500 return (dfly_choose_queue_simple(dd, lp)); 1501 1502 /* 1503 * Pairing mask 1504 */ 1505 if ((wakecpu = lp->lwp_thread->td_wakefromcpu) >= 0) 1506 wakemask = dfly_pcpu[wakecpu].cpumask; 1507 else 1508 CPUMASK_ASSZERO(wakemask); 1509 1510 /* 1511 * When the topology is known choose a cpu whos group has, in 1512 * aggregate, has the lowest weighted load. 1513 */ 1514 cpup = root_cpu_node; 1515 rdd = dd; 1516 1517 while (cpup) { 1518 /* 1519 * Degenerate case super-root 1520 */ 1521 if (cpup->child_no == 1) { 1522 cpup = cpup->child_node[0]; 1523 continue; 1524 } 1525 1526 /* 1527 * Terminal cpunode 1528 */ 1529 if (cpup->child_no == 0) { 1530 rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)]; 1531 break; 1532 } 1533 1534 cpub = NULL; 1535 lowest_load = 0x7FFFFFFF; 1536 1537 for (n = 0; n < cpup->child_no; ++n) { 1538 /* 1539 * Accumulate load information for all cpus 1540 * which are members of this node. 1541 */ 1542 cpun = cpup->child_node[n]; 1543 mask = cpun->members; 1544 CPUMASK_ANDMASK(mask, usched_global_cpumask); 1545 CPUMASK_ANDMASK(mask, smp_active_mask); 1546 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 1547 if (CPUMASK_TESTZERO(mask)) 1548 continue; 1549 1550 count = 0; 1551 load = 0; 1552 1553 while (CPUMASK_TESTNZERO(mask)) { 1554 cpuid = BSFCPUMASK(mask); 1555 rdd = &dfly_pcpu[cpuid]; 1556 load += rdd->uload; 1557 load += rdd->ucount * usched_dfly_weight3; 1558 1559 if (rdd->uschedcp == NULL && 1560 rdd->runqcount == 0 && 1561 globaldata_find(cpuid)->gd_tdrunqcount == 0 1562 ) { 1563 load -= usched_dfly_weight4; 1564 } 1565 #if 0 1566 else if (rdd->upri > lp->lwp_priority + PPQ) { 1567 load -= usched_dfly_weight4 / 2; 1568 } 1569 #endif 1570 CPUMASK_NANDBIT(mask, cpuid); 1571 ++count; 1572 } 1573 1574 /* 1575 * Compensate if the lp is already accounted for in 1576 * the aggregate uload for this mask set. We want 1577 * to calculate the loads as if lp were not present, 1578 * otherwise the calculation is bogus. 1579 */ 1580 if ((lp->lwp_mpflags & LWP_MP_ULOAD) && 1581 CPUMASK_TESTMASK(dd->cpumask, cpun->members)) { 1582 load -= lp->lwp_uload; 1583 load -= usched_dfly_weight3; 1584 } 1585 1586 load /= count; 1587 1588 /* 1589 * Advantage the cpu group (lp) is already on. 1590 */ 1591 if (CPUMASK_TESTMASK(cpun->members, dd->cpumask)) 1592 load -= usched_dfly_weight1; 1593 1594 /* 1595 * Advantage the cpu group we want to pair (lp) to, 1596 * but don't let it go to the exact same cpu as 1597 * the wakecpu target. 1598 * 1599 * We do this by checking whether cpun is a 1600 * terminal node or not. All cpun's at the same 1601 * level will either all be terminal or all not 1602 * terminal. 1603 * 1604 * If it is and we match we disadvantage the load. 1605 * If it is and we don't match we advantage the load. 1606 * 1607 * Also note that we are effectively disadvantaging 1608 * all-but-one by the same amount, so it won't effect 1609 * the weight1 factor for the all-but-one nodes. 1610 */ 1611 if (CPUMASK_TESTMASK(cpun->members, wakemask)) { 1612 if (cpun->child_no != 0) { 1613 /* advantage */ 1614 load -= usched_dfly_weight2; 1615 } else { 1616 if (usched_dfly_features & 0x10) 1617 load += usched_dfly_weight2; 1618 else 1619 load -= usched_dfly_weight2; 1620 } 1621 } 1622 1623 /* 1624 * Calculate the best load 1625 */ 1626 if (cpub == NULL || lowest_load > load || 1627 (lowest_load == load && 1628 CPUMASK_TESTMASK(cpun->members, dd->cpumask)) 1629 ) { 1630 lowest_load = load; 1631 cpub = cpun; 1632 } 1633 } 1634 cpup = cpub; 1635 } 1636 /* Dispatch this outcast to a proper CPU. */ 1637 if (__predict_false(CPUMASK_TESTBIT(lp->lwp_cpumask, rdd->cpuid) == 0)) 1638 rdd = &dfly_pcpu[BSFCPUMASK(lp->lwp_cpumask)]; 1639 if (usched_dfly_chooser > 0) { 1640 --usched_dfly_chooser; /* only N lines */ 1641 kprintf("lp %02d->%02d %s\n", 1642 lp->lwp_qcpu, rdd->cpuid, lp->lwp_proc->p_comm); 1643 } 1644 return (rdd); 1645 } 1646 1647 /* 1648 * USED TO PULL RUNNABLE LWPS FROM THE MOST LOADED CPU. 1649 * 1650 * Choose the worst queue close to dd's cpu node with a non-empty runq 1651 * that is NOT dd. Also require that the moving of the highest-load thread 1652 * from rdd to dd does not cause the uload's to cross each other. 1653 * 1654 * This is used by the thread chooser when the current cpu's queues are 1655 * empty to steal a thread from another cpu's queue. We want to offload 1656 * the most heavily-loaded queue. 1657 */ 1658 static 1659 dfly_pcpu_t 1660 dfly_choose_worst_queue(dfly_pcpu_t dd) 1661 { 1662 cpumask_t mask; 1663 cpu_node_t *cpup; 1664 cpu_node_t *cpun; 1665 cpu_node_t *cpub; 1666 dfly_pcpu_t rdd; 1667 int cpuid; 1668 int n; 1669 int count; 1670 int load; 1671 #if 0 1672 int pri; 1673 int hpri; 1674 #endif 1675 int highest_load; 1676 1677 /* 1678 * When the topology is unknown choose a random cpu that is hopefully 1679 * idle. 1680 */ 1681 if (dd->cpunode == NULL) { 1682 return (NULL); 1683 } 1684 1685 /* 1686 * When the topology is known choose a cpu whos group has, in 1687 * aggregate, has the highest weighted load. 1688 */ 1689 cpup = root_cpu_node; 1690 rdd = dd; 1691 while (cpup) { 1692 /* 1693 * Degenerate case super-root 1694 */ 1695 if (cpup->child_no == 1) { 1696 cpup = cpup->child_node[0]; 1697 continue; 1698 } 1699 1700 /* 1701 * Terminal cpunode 1702 */ 1703 if (cpup->child_no == 0) { 1704 rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)]; 1705 break; 1706 } 1707 1708 cpub = NULL; 1709 highest_load = 0; 1710 1711 for (n = 0; n < cpup->child_no; ++n) { 1712 /* 1713 * Accumulate load information for all cpus 1714 * which are members of this node. 1715 */ 1716 cpun = cpup->child_node[n]; 1717 mask = cpun->members; 1718 CPUMASK_ANDMASK(mask, usched_global_cpumask); 1719 CPUMASK_ANDMASK(mask, smp_active_mask); 1720 if (CPUMASK_TESTZERO(mask)) 1721 continue; 1722 1723 count = 0; 1724 load = 0; 1725 1726 while (CPUMASK_TESTNZERO(mask)) { 1727 cpuid = BSFCPUMASK(mask); 1728 rdd = &dfly_pcpu[cpuid]; 1729 load += rdd->uload; 1730 load += rdd->ucount * usched_dfly_weight3; 1731 1732 if (rdd->uschedcp == NULL && 1733 rdd->runqcount == 0 && 1734 globaldata_find(cpuid)->gd_tdrunqcount == 0 1735 ) { 1736 load -= usched_dfly_weight4; 1737 } 1738 #if 0 1739 else if (rdd->upri > dd->upri + PPQ) { 1740 load -= usched_dfly_weight4 / 2; 1741 } 1742 #endif 1743 CPUMASK_NANDBIT(mask, cpuid); 1744 ++count; 1745 } 1746 load /= count; 1747 1748 /* 1749 * Prefer candidates which are somewhat closer to 1750 * our cpu. 1751 */ 1752 if (CPUMASK_TESTMASK(dd->cpumask, cpun->members)) 1753 load += usched_dfly_weight1; 1754 1755 /* 1756 * The best candidate is the one with the worst 1757 * (highest) load. 1758 */ 1759 if (cpub == NULL || highest_load < load || 1760 (highest_load == load && 1761 CPUMASK_TESTMASK(cpun->members, dd->cpumask))) { 1762 highest_load = load; 1763 cpub = cpun; 1764 } 1765 } 1766 cpup = cpub; 1767 } 1768 1769 /* 1770 * We never return our own node (dd), and only return a remote 1771 * node if it's load is significantly worse than ours (i.e. where 1772 * stealing a thread would be considered reasonable). 1773 * 1774 * This also helps us avoid breaking paired threads apart which 1775 * can have disastrous effects on performance. 1776 */ 1777 if (rdd == dd) 1778 return(NULL); 1779 1780 #if 0 1781 hpri = 0; 1782 if (rdd->rtqueuebits && hpri < (pri = bsrl(rdd->rtqueuebits))) 1783 hpri = pri; 1784 if (rdd->queuebits && hpri < (pri = bsrl(rdd->queuebits))) 1785 hpri = pri; 1786 if (rdd->idqueuebits && hpri < (pri = bsrl(rdd->idqueuebits))) 1787 hpri = pri; 1788 hpri *= PPQ; 1789 if (rdd->uload - hpri < dd->uload + hpri) 1790 return(NULL); 1791 #endif 1792 return (rdd); 1793 } 1794 1795 static 1796 dfly_pcpu_t 1797 dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp) 1798 { 1799 dfly_pcpu_t rdd; 1800 cpumask_t tmpmask; 1801 cpumask_t mask; 1802 int cpubase; 1803 int cpuid; 1804 1805 /* 1806 * Fallback to the original heuristic, select random cpu, 1807 * first checking the cpus not currently running a user thread. 1808 * 1809 * Use cpuid as the base cpu in our scan, first checking 1810 * cpuid...(ncpus-1), then 0...(cpuid-1). This avoid favoring 1811 * lower-numbered cpus. 1812 */ 1813 ++dd->scancpu; /* SMP race ok */ 1814 mask = dfly_rdyprocmask; 1815 CPUMASK_NANDMASK(mask, dfly_curprocmask); 1816 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 1817 CPUMASK_ANDMASK(mask, smp_active_mask); 1818 CPUMASK_ANDMASK(mask, usched_global_cpumask); 1819 1820 cpubase = (int)(dd->scancpu % ncpus); 1821 CPUMASK_ASSBMASK(tmpmask, cpubase); 1822 CPUMASK_INVMASK(tmpmask); 1823 CPUMASK_ANDMASK(tmpmask, mask); 1824 while (CPUMASK_TESTNZERO(tmpmask)) { 1825 cpuid = BSFCPUMASK(tmpmask); 1826 rdd = &dfly_pcpu[cpuid]; 1827 1828 if ((rdd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK)) 1829 goto found; 1830 CPUMASK_NANDBIT(tmpmask, cpuid); 1831 } 1832 1833 CPUMASK_ASSBMASK(tmpmask, cpubase); 1834 CPUMASK_ANDMASK(tmpmask, mask); 1835 while (CPUMASK_TESTNZERO(tmpmask)) { 1836 cpuid = BSFCPUMASK(tmpmask); 1837 rdd = &dfly_pcpu[cpuid]; 1838 1839 if ((rdd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK)) 1840 goto found; 1841 CPUMASK_NANDBIT(tmpmask, cpuid); 1842 } 1843 1844 /* 1845 * Then cpus which might have a currently running lp 1846 */ 1847 mask = dfly_rdyprocmask; 1848 CPUMASK_ANDMASK(mask, dfly_curprocmask); 1849 CPUMASK_ANDMASK(mask, lp->lwp_cpumask); 1850 CPUMASK_ANDMASK(mask, smp_active_mask); 1851 CPUMASK_ANDMASK(mask, usched_global_cpumask); 1852 1853 CPUMASK_ASSBMASK(tmpmask, cpubase); 1854 CPUMASK_INVMASK(tmpmask); 1855 CPUMASK_ANDMASK(tmpmask, mask); 1856 while (CPUMASK_TESTNZERO(tmpmask)) { 1857 cpuid = BSFCPUMASK(tmpmask); 1858 rdd = &dfly_pcpu[cpuid]; 1859 1860 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) 1861 goto found; 1862 CPUMASK_NANDBIT(tmpmask, cpuid); 1863 } 1864 1865 CPUMASK_ASSBMASK(tmpmask, cpubase); 1866 CPUMASK_ANDMASK(tmpmask, mask); 1867 while (CPUMASK_TESTNZERO(tmpmask)) { 1868 cpuid = BSFCPUMASK(tmpmask); 1869 rdd = &dfly_pcpu[cpuid]; 1870 1871 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) 1872 goto found; 1873 CPUMASK_NANDBIT(tmpmask, cpuid); 1874 } 1875 1876 /* 1877 * If we cannot find a suitable cpu we round-robin using scancpu. 1878 * Other cpus will pickup as they release their current lwps or 1879 * become ready. 1880 * 1881 * Avoid a degenerate system lockup case if usched_global_cpumask 1882 * is set to 0 or otherwise does not cover lwp_cpumask. 1883 * 1884 * We only kick the target helper thread in this case, we do not 1885 * set the user resched flag because 1886 */ 1887 cpuid = cpubase; 1888 if (CPUMASK_TESTBIT(lp->lwp_cpumask, cpuid) == 0) 1889 cpuid = BSFCPUMASK(lp->lwp_cpumask); 1890 else if (CPUMASK_TESTBIT(usched_global_cpumask, cpuid) == 0) 1891 cpuid = 0; 1892 rdd = &dfly_pcpu[cpuid]; 1893 found: 1894 return (rdd); 1895 } 1896 1897 static 1898 void 1899 dfly_need_user_resched_remote(void *dummy) 1900 { 1901 globaldata_t gd = mycpu; 1902 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid]; 1903 1904 /* 1905 * Flag reschedule needed 1906 */ 1907 need_user_resched(); 1908 1909 /* 1910 * If no user thread is currently running we need to kick the helper 1911 * on our cpu to recover. Otherwise the cpu will never schedule 1912 * anything again. 1913 * 1914 * We cannot schedule the process ourselves because this is an 1915 * IPI callback and we cannot acquire spinlocks in an IPI callback. 1916 * 1917 * Call wakeup_mycpu to avoid sending IPIs to other CPUs 1918 */ 1919 if (dd->uschedcp == NULL && 1920 CPUMASK_TESTBIT(dfly_rdyprocmask, gd->gd_cpuid)) { 1921 ATOMIC_CPUMASK_NANDBIT(dfly_rdyprocmask, gd->gd_cpuid); 1922 wakeup_mycpu(dd->helper_thread); 1923 } 1924 } 1925 1926 /* 1927 * dfly_remrunqueue_locked() removes a given process from the run queue 1928 * that it is on, clearing the queue busy bit if it becomes empty. 1929 * 1930 * Note that user process scheduler is different from the LWKT schedule. 1931 * The user process scheduler only manages user processes but it uses LWKT 1932 * underneath, and a user process operating in the kernel will often be 1933 * 'released' from our management. 1934 * 1935 * uload is NOT adjusted here. It is only adjusted if the lwkt_thread goes 1936 * to sleep or the lwp is moved to a different runq. 1937 */ 1938 static void 1939 dfly_remrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp) 1940 { 1941 struct rq *q; 1942 u_int32_t *which; 1943 u_int8_t pri; 1944 1945 KKASSERT(rdd->runqcount >= 0); 1946 1947 pri = lp->lwp_rqindex; 1948 1949 switch(lp->lwp_rqtype) { 1950 case RTP_PRIO_NORMAL: 1951 q = &rdd->queues[pri]; 1952 which = &rdd->queuebits; 1953 break; 1954 case RTP_PRIO_REALTIME: 1955 case RTP_PRIO_FIFO: 1956 q = &rdd->rtqueues[pri]; 1957 which = &rdd->rtqueuebits; 1958 break; 1959 case RTP_PRIO_IDLE: 1960 q = &rdd->idqueues[pri]; 1961 which = &rdd->idqueuebits; 1962 break; 1963 default: 1964 panic("remrunqueue: invalid rtprio type"); 1965 /* NOT REACHED */ 1966 } 1967 KKASSERT(lp->lwp_mpflags & LWP_MP_ONRUNQ); 1968 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 1969 TAILQ_REMOVE(q, lp, lwp_procq); 1970 --rdd->runqcount; 1971 if (TAILQ_EMPTY(q)) { 1972 KASSERT((*which & (1 << pri)) != 0, 1973 ("remrunqueue: remove from empty queue")); 1974 *which &= ~(1 << pri); 1975 } 1976 } 1977 1978 /* 1979 * dfly_setrunqueue_locked() 1980 * 1981 * Add a process whos rqtype and rqindex had previously been calculated 1982 * onto the appropriate run queue. Determine if the addition requires 1983 * a reschedule on a cpu and return the cpuid or -1. 1984 * 1985 * NOTE: Lower priorities are better priorities. 1986 * 1987 * NOTE ON ULOAD: This variable specifies the aggregate load on a cpu, the 1988 * sum of the rough lwp_priority for all running and runnable 1989 * processes. Lower priority processes (higher lwp_priority 1990 * values) actually DO count as more load, not less, because 1991 * these are the programs which require the most care with 1992 * regards to cpu selection. 1993 */ 1994 static void 1995 dfly_setrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp) 1996 { 1997 u_int32_t *which; 1998 struct rq *q; 1999 int pri; 2000 2001 KKASSERT(lp->lwp_qcpu == rdd->cpuid); 2002 2003 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) { 2004 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD); 2005 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload, lp->lwp_uload); 2006 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].ucount, 1); 2007 atomic_add_int(&dfly_ucount, 1); 2008 } 2009 2010 pri = lp->lwp_rqindex; 2011 2012 switch(lp->lwp_rqtype) { 2013 case RTP_PRIO_NORMAL: 2014 q = &rdd->queues[pri]; 2015 which = &rdd->queuebits; 2016 break; 2017 case RTP_PRIO_REALTIME: 2018 case RTP_PRIO_FIFO: 2019 q = &rdd->rtqueues[pri]; 2020 which = &rdd->rtqueuebits; 2021 break; 2022 case RTP_PRIO_IDLE: 2023 q = &rdd->idqueues[pri]; 2024 which = &rdd->idqueuebits; 2025 break; 2026 default: 2027 panic("remrunqueue: invalid rtprio type"); 2028 /* NOT REACHED */ 2029 } 2030 2031 /* 2032 * Place us on the selected queue. Determine if we should be 2033 * placed at the head of the queue or at the end. 2034 * 2035 * We are placed at the tail if our round-robin count has expired, 2036 * or is about to expire and the system thinks its a good place to 2037 * round-robin, or there is already a next thread on the queue 2038 * (it might be trying to pick up where it left off and we don't 2039 * want to interfere). 2040 */ 2041 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0); 2042 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ); 2043 ++rdd->runqcount; 2044 2045 if (lp->lwp_rrcount >= usched_dfly_rrinterval || 2046 (lp->lwp_rrcount >= usched_dfly_rrinterval / 2 && 2047 (lp->lwp_thread->td_mpflags & TDF_MP_BATCH_DEMARC)) 2048 ) { 2049 /* 2050 * Place on tail 2051 */ 2052 atomic_clear_int(&lp->lwp_thread->td_mpflags, 2053 TDF_MP_BATCH_DEMARC); 2054 lp->lwp_rrcount = 0; 2055 TAILQ_INSERT_TAIL(q, lp, lwp_procq); 2056 } else { 2057 /* 2058 * Retain rrcount and place on head. Count is retained 2059 * even if the queue is empty. 2060 */ 2061 TAILQ_INSERT_HEAD(q, lp, lwp_procq); 2062 } 2063 *which |= 1 << pri; 2064 } 2065 2066 /* 2067 * For SMP systems a user scheduler helper thread is created for each 2068 * cpu and is used to allow one cpu to wakeup another for the purposes of 2069 * scheduling userland threads from setrunqueue(). 2070 * 2071 * UP systems do not need the helper since there is only one cpu. 2072 * 2073 * We can't use the idle thread for this because we might block. 2074 * Additionally, doing things this way allows us to HLT idle cpus 2075 * on MP systems. 2076 */ 2077 static void 2078 dfly_helper_thread(void *dummy) 2079 { 2080 globaldata_t gd; 2081 dfly_pcpu_t dd; 2082 dfly_pcpu_t rdd; 2083 struct lwp *nlp; 2084 cpumask_t mask; 2085 int cpuid; 2086 2087 gd = mycpu; 2088 cpuid = gd->gd_cpuid; /* doesn't change */ 2089 mask = gd->gd_cpumask; /* doesn't change */ 2090 dd = &dfly_pcpu[cpuid]; 2091 2092 /* 2093 * Since we only want to be woken up only when no user processes 2094 * are scheduled on a cpu, run at an ultra low priority. 2095 */ 2096 lwkt_setpri_self(TDPRI_USER_SCHEDULER); 2097 2098 tsleep(dd->helper_thread, 0, "schslp", 0); 2099 2100 for (;;) { 2101 /* 2102 * We use the LWKT deschedule-interlock trick to avoid racing 2103 * dfly_rdyprocmask. This means we cannot block through to the 2104 * manual lwkt_switch() call we make below. 2105 */ 2106 crit_enter_gd(gd); 2107 tsleep_interlock(dd->helper_thread, 0); 2108 2109 spin_lock(&dd->spin); 2110 2111 ATOMIC_CPUMASK_ORMASK(dfly_rdyprocmask, mask); 2112 clear_user_resched(); /* This satisfied the reschedule request */ 2113 #if 0 2114 dd->rrcount = 0; /* Reset the round-robin counter */ 2115 #endif 2116 2117 if (dd->runqcount || dd->uschedcp != NULL) { 2118 /* 2119 * Threads are available. A thread may or may not be 2120 * currently scheduled. Get the best thread already queued 2121 * to this cpu. 2122 */ 2123 nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0); 2124 if (nlp) { 2125 ATOMIC_CPUMASK_ORMASK(dfly_curprocmask, mask); 2126 dd->upri = nlp->lwp_priority; 2127 dd->uschedcp = nlp; 2128 #if 0 2129 dd->rrcount = 0; /* reset round robin */ 2130 #endif 2131 spin_unlock(&dd->spin); 2132 lwkt_acquire(nlp->lwp_thread); 2133 lwkt_schedule(nlp->lwp_thread); 2134 } else { 2135 /* 2136 * This situation should not occur because we had 2137 * at least one thread available. 2138 */ 2139 spin_unlock(&dd->spin); 2140 } 2141 } else if (usched_dfly_features & 0x01) { 2142 /* 2143 * This cpu is devoid of runnable threads, steal a thread 2144 * from another cpu. Since we're stealing, might as well 2145 * load balance at the same time. 2146 * 2147 * We choose the highest-loaded thread from the worst queue. 2148 * 2149 * NOTE! This function only returns a non-NULL rdd when 2150 * another cpu's queue is obviously overloaded. We 2151 * do not want to perform the type of rebalancing 2152 * the schedclock does here because it would result 2153 * in insane process pulling when 'steady' state is 2154 * partially unbalanced (e.g. 6 runnables and only 2155 * 4 cores). 2156 */ 2157 rdd = dfly_choose_worst_queue(dd); 2158 if (rdd && spin_trylock(&rdd->spin)) { 2159 nlp = dfly_chooseproc_locked(rdd, dd, NULL, 1); 2160 spin_unlock(&rdd->spin); 2161 } else { 2162 nlp = NULL; 2163 } 2164 if (nlp) { 2165 ATOMIC_CPUMASK_ORMASK(dfly_curprocmask, mask); 2166 dd->upri = nlp->lwp_priority; 2167 dd->uschedcp = nlp; 2168 #if 0 2169 dd->rrcount = 0; /* reset round robin */ 2170 #endif 2171 spin_unlock(&dd->spin); 2172 lwkt_acquire(nlp->lwp_thread); 2173 lwkt_schedule(nlp->lwp_thread); 2174 } else { 2175 /* 2176 * Leave the thread on our run queue. Another 2177 * scheduler will try to pull it later. 2178 */ 2179 spin_unlock(&dd->spin); 2180 } 2181 } else { 2182 /* 2183 * devoid of runnable threads and not allowed to steal 2184 * any. 2185 */ 2186 spin_unlock(&dd->spin); 2187 } 2188 2189 /* 2190 * We're descheduled unless someone scheduled us. Switch away. 2191 * Exiting the critical section will cause splz() to be called 2192 * for us if interrupts and such are pending. 2193 */ 2194 crit_exit_gd(gd); 2195 tsleep(dd->helper_thread, PINTERLOCKED, "schslp", 0); 2196 } 2197 } 2198 2199 #if 0 2200 static int 2201 sysctl_usched_dfly_stick_to_level(SYSCTL_HANDLER_ARGS) 2202 { 2203 int error, new_val; 2204 2205 new_val = usched_dfly_stick_to_level; 2206 2207 error = sysctl_handle_int(oidp, &new_val, 0, req); 2208 if (error != 0 || req->newptr == NULL) 2209 return (error); 2210 if (new_val > cpu_topology_levels_number - 1 || new_val < 0) 2211 return (EINVAL); 2212 usched_dfly_stick_to_level = new_val; 2213 return (0); 2214 } 2215 #endif 2216 2217 /* 2218 * Setup the queues and scheduler helpers (scheduler helpers are SMP only). 2219 * Note that curprocmask bit 0 has already been cleared by rqinit() and 2220 * we should not mess with it further. 2221 */ 2222 static void 2223 usched_dfly_cpu_init(void) 2224 { 2225 int i; 2226 int j; 2227 int smt_not_supported = 0; 2228 int cache_coherent_not_supported = 0; 2229 2230 if (bootverbose) 2231 kprintf("Start usched_dfly helpers on cpus:\n"); 2232 2233 sysctl_ctx_init(&usched_dfly_sysctl_ctx); 2234 usched_dfly_sysctl_tree = 2235 SYSCTL_ADD_NODE(&usched_dfly_sysctl_ctx, 2236 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO, 2237 "usched_dfly", CTLFLAG_RD, 0, ""); 2238 2239 for (i = 0; i < ncpus; ++i) { 2240 dfly_pcpu_t dd = &dfly_pcpu[i]; 2241 cpumask_t mask; 2242 2243 CPUMASK_ASSBIT(mask, i); 2244 if (CPUMASK_TESTMASK(mask, smp_active_mask) == 0) 2245 continue; 2246 2247 spin_init(&dd->spin, "uschedcpuinit"); 2248 dd->cpunode = get_cpu_node_by_cpuid(i); 2249 dd->cpuid = i; 2250 CPUMASK_ASSBIT(dd->cpumask, i); 2251 for (j = 0; j < NQS; j++) { 2252 TAILQ_INIT(&dd->queues[j]); 2253 TAILQ_INIT(&dd->rtqueues[j]); 2254 TAILQ_INIT(&dd->idqueues[j]); 2255 } 2256 ATOMIC_CPUMASK_NANDBIT(dfly_curprocmask, 0); 2257 2258 if (dd->cpunode == NULL) { 2259 smt_not_supported = 1; 2260 cache_coherent_not_supported = 1; 2261 if (bootverbose) 2262 kprintf (" cpu%d - WARNING: No CPU NODE " 2263 "found for cpu\n", i); 2264 } else { 2265 switch (dd->cpunode->type) { 2266 case THREAD_LEVEL: 2267 if (bootverbose) 2268 kprintf (" cpu%d - HyperThreading " 2269 "available. Core siblings: ", 2270 i); 2271 break; 2272 case CORE_LEVEL: 2273 smt_not_supported = 1; 2274 2275 if (bootverbose) 2276 kprintf (" cpu%d - No HT available, " 2277 "multi-core/physical " 2278 "cpu. Physical siblings: ", 2279 i); 2280 break; 2281 case CHIP_LEVEL: 2282 smt_not_supported = 1; 2283 2284 if (bootverbose) 2285 kprintf (" cpu%d - No HT available, " 2286 "single-core/physical cpu. " 2287 "Package siblings: ", 2288 i); 2289 break; 2290 default: 2291 /* Let's go for safe defaults here */ 2292 smt_not_supported = 1; 2293 cache_coherent_not_supported = 1; 2294 if (bootverbose) 2295 kprintf (" cpu%d - Unknown cpunode->" 2296 "type=%u. siblings: ", 2297 i, 2298 (u_int)dd->cpunode->type); 2299 break; 2300 } 2301 2302 if (bootverbose) { 2303 if (dd->cpunode->parent_node != NULL) { 2304 kprint_cpuset(&dd->cpunode-> 2305 parent_node->members); 2306 kprintf("\n"); 2307 } else { 2308 kprintf(" no siblings\n"); 2309 } 2310 } 2311 } 2312 2313 lwkt_create(dfly_helper_thread, NULL, &dd->helper_thread, NULL, 2314 0, i, "usched %d", i); 2315 2316 /* 2317 * Allow user scheduling on the target cpu. cpu #0 has already 2318 * been enabled in rqinit(). 2319 */ 2320 if (i) 2321 ATOMIC_CPUMASK_NANDMASK(dfly_curprocmask, mask); 2322 ATOMIC_CPUMASK_ORMASK(dfly_rdyprocmask, mask); 2323 dd->upri = PRIBASE_NULL; 2324 2325 } 2326 2327 /* usched_dfly sysctl configurable parameters */ 2328 2329 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2330 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2331 OID_AUTO, "rrinterval", CTLFLAG_RW, 2332 &usched_dfly_rrinterval, 0, ""); 2333 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2334 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2335 OID_AUTO, "decay", CTLFLAG_RW, 2336 &usched_dfly_decay, 0, "Extra decay when not running"); 2337 2338 /* Add enable/disable option for SMT scheduling if supported */ 2339 if (smt_not_supported) { 2340 usched_dfly_smt = 0; 2341 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx, 2342 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2343 OID_AUTO, "smt", CTLFLAG_RD, 2344 "NOT SUPPORTED", 0, "SMT NOT SUPPORTED"); 2345 } else { 2346 usched_dfly_smt = 1; 2347 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2348 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2349 OID_AUTO, "smt", CTLFLAG_RW, 2350 &usched_dfly_smt, 0, "Enable SMT scheduling"); 2351 } 2352 2353 /* 2354 * Add enable/disable option for cache coherent scheduling 2355 * if supported 2356 */ 2357 if (cache_coherent_not_supported) { 2358 usched_dfly_cache_coherent = 0; 2359 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx, 2360 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2361 OID_AUTO, "cache_coherent", CTLFLAG_RD, 2362 "NOT SUPPORTED", 0, 2363 "Cache coherence NOT SUPPORTED"); 2364 } else { 2365 usched_dfly_cache_coherent = 1; 2366 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2367 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2368 OID_AUTO, "cache_coherent", CTLFLAG_RW, 2369 &usched_dfly_cache_coherent, 0, 2370 "Enable/Disable cache coherent scheduling"); 2371 2372 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2373 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2374 OID_AUTO, "weight1", CTLFLAG_RW, 2375 &usched_dfly_weight1, 200, 2376 "Weight selection for current cpu"); 2377 2378 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2379 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2380 OID_AUTO, "weight2", CTLFLAG_RW, 2381 &usched_dfly_weight2, 180, 2382 "Weight selection for wakefrom cpu"); 2383 2384 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2385 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2386 OID_AUTO, "weight3", CTLFLAG_RW, 2387 &usched_dfly_weight3, 40, 2388 "Weight selection for num threads on queue"); 2389 2390 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2391 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2392 OID_AUTO, "weight4", CTLFLAG_RW, 2393 &usched_dfly_weight4, 160, 2394 "Availability of other idle cpus"); 2395 2396 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2397 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2398 OID_AUTO, "fast_resched", CTLFLAG_RW, 2399 &usched_dfly_fast_resched, 0, 2400 "Availability of other idle cpus"); 2401 2402 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2403 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2404 OID_AUTO, "features", CTLFLAG_RW, 2405 &usched_dfly_features, 0x8F, 2406 "Allow pulls into empty queues"); 2407 2408 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx, 2409 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2410 OID_AUTO, "swmask", CTLFLAG_RW, 2411 &usched_dfly_swmask, ~PPQMASK, 2412 "Queue mask to force thread switch"); 2413 2414 #if 0 2415 SYSCTL_ADD_PROC(&usched_dfly_sysctl_ctx, 2416 SYSCTL_CHILDREN(usched_dfly_sysctl_tree), 2417 OID_AUTO, "stick_to_level", 2418 CTLTYPE_INT | CTLFLAG_RW, 2419 NULL, sizeof usched_dfly_stick_to_level, 2420 sysctl_usched_dfly_stick_to_level, "I", 2421 "Stick a process to this level. See sysctl" 2422 "paremter hw.cpu_topology.level_description"); 2423 #endif 2424 } 2425 } 2426 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND, 2427 usched_dfly_cpu_init, NULL); 2428