1 /* 2 * Copyright (c) 2006 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 * $DragonFly: src/sys/kern/usched_dummy.c,v 1.9 2008/04/21 15:24:46 dillon Exp $ 35 */ 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 <machine/cpu.h> 49 #include <machine/smp.h> 50 51 #include <sys/thread2.h> 52 #include <sys/spinlock2.h> 53 54 #define MAXPRI 128 55 #define PRIBASE_REALTIME 0 56 #define PRIBASE_NORMAL MAXPRI 57 #define PRIBASE_IDLE (MAXPRI * 2) 58 #define PRIBASE_THREAD (MAXPRI * 3) 59 #define PRIBASE_NULL (MAXPRI * 4) 60 61 #define lwp_priority lwp_usdata.bsd4.priority 62 #define lwp_estcpu lwp_usdata.bsd4.estcpu 63 64 static void dummy_acquire_curproc(struct lwp *lp); 65 static void dummy_release_curproc(struct lwp *lp); 66 static void dummy_select_curproc(globaldata_t gd); 67 static void dummy_setrunqueue(struct lwp *lp); 68 static void dummy_schedulerclock(struct lwp *lp, sysclock_t period, 69 sysclock_t cpstamp); 70 static void dummy_recalculate_estcpu(struct lwp *lp); 71 static void dummy_resetpriority(struct lwp *lp); 72 static void dummy_forking(struct lwp *plp, struct lwp *lp); 73 static void dummy_exiting(struct lwp *plp, struct lwp *lp); 74 static void dummy_yield(struct lwp *lp); 75 76 struct usched usched_dummy = { 77 { NULL }, 78 "dummy", "Dummy DragonFly Scheduler", 79 NULL, /* default registration */ 80 NULL, /* default deregistration */ 81 dummy_acquire_curproc, 82 dummy_release_curproc, 83 dummy_setrunqueue, 84 dummy_schedulerclock, 85 dummy_recalculate_estcpu, 86 dummy_resetpriority, 87 dummy_forking, 88 dummy_exiting, 89 NULL, /* setcpumask not supported */ 90 dummy_yield 91 }; 92 93 struct usched_dummy_pcpu { 94 int rrcount; 95 struct thread helper_thread; 96 struct lwp *uschedcp; 97 }; 98 99 typedef struct usched_dummy_pcpu *dummy_pcpu_t; 100 101 static struct usched_dummy_pcpu dummy_pcpu[MAXCPU]; 102 static cpumask_t dummy_curprocmask = -1; 103 static cpumask_t dummy_rdyprocmask; 104 static struct spinlock dummy_spin; 105 static TAILQ_HEAD(rq, lwp) dummy_runq; 106 static int dummy_runqcount; 107 108 static int usched_dummy_rrinterval = (ESTCPUFREQ + 9) / 10; 109 SYSCTL_INT(_kern, OID_AUTO, usched_dummy_rrinterval, CTLFLAG_RW, 110 &usched_dummy_rrinterval, 0, ""); 111 112 /* 113 * Initialize the run queues at boot time, clear cpu 0 in curprocmask 114 * to allow dummy scheduling on cpu 0. 115 */ 116 static void 117 dummyinit(void *dummy) 118 { 119 TAILQ_INIT(&dummy_runq); 120 spin_init(&dummy_spin); 121 atomic_clear_int(&dummy_curprocmask, 1); 122 } 123 SYSINIT(runqueue, SI_BOOT2_USCHED, SI_ORDER_FIRST, dummyinit, NULL) 124 125 /* 126 * DUMMY_ACQUIRE_CURPROC 127 * 128 * This function is called when the kernel intends to return to userland. 129 * It is responsible for making the thread the current designated userland 130 * thread for this cpu, blocking if necessary. 131 * 132 * We are expected to handle userland reschedule requests here too. 133 * 134 * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE 135 * TO ANOTHER CPU! Because most of the kernel assumes that no migration will 136 * occur, this function is called only under very controlled circumstances. 137 * 138 * MPSAFE 139 */ 140 static void 141 dummy_acquire_curproc(struct lwp *lp) 142 { 143 globaldata_t gd = mycpu; 144 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid]; 145 thread_t td = lp->lwp_thread; 146 147 /* 148 * Possibly select another thread 149 */ 150 if (user_resched_wanted()) 151 dummy_select_curproc(gd); 152 153 /* 154 * If this cpu has no current thread, select ourself 155 */ 156 if (dd->uschedcp == lp || 157 (dd->uschedcp == NULL && TAILQ_EMPTY(&dummy_runq))) { 158 atomic_set_int(&dummy_curprocmask, gd->gd_cpumask); 159 dd->uschedcp = lp; 160 return; 161 } 162 163 /* 164 * If this cpu's current user process thread is not our thread, 165 * deschedule ourselves and place us on the run queue, then 166 * switch away. 167 * 168 * We loop until we become the current process. Its a good idea 169 * to run any passive release(s) before we mess with the scheduler 170 * so our thread is in the expected state. 171 */ 172 KKASSERT(dd->uschedcp != lp); 173 if (td->td_release) 174 td->td_release(lp->lwp_thread); 175 do { 176 crit_enter(); 177 lwkt_deschedule_self(td); 178 dummy_setrunqueue(lp); 179 if ((td->td_flags & TDF_RUNQ) == 0) 180 ++lp->lwp_ru.ru_nivcsw; 181 lwkt_switch(); /* WE MAY MIGRATE TO ANOTHER CPU */ 182 crit_exit(); 183 gd = mycpu; 184 dd = &dummy_pcpu[gd->gd_cpuid]; 185 KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0); 186 } while (dd->uschedcp != lp); 187 } 188 189 /* 190 * DUMMY_RELEASE_CURPROC 191 * 192 * This routine detaches the current thread from the userland scheduler, 193 * usually because the thread needs to run in the kernel (at kernel priority) 194 * for a while. 195 * 196 * This routine is also responsible for selecting a new thread to 197 * make the current thread. 198 * 199 * WARNING! The MP lock may be in an unsynchronized state due to the 200 * way get_mplock() works and the fact that this function may be called 201 * from a passive release during a lwkt_switch(). try_mplock() will deal 202 * with this for us but you should be aware that td_mpcount may not be 203 * useable. 204 * 205 * MPSAFE 206 */ 207 static void 208 dummy_release_curproc(struct lwp *lp) 209 { 210 globaldata_t gd = mycpu; 211 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid]; 212 213 KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0); 214 if (dd->uschedcp == lp) { 215 dummy_select_curproc(gd); 216 } 217 } 218 219 /* 220 * DUMMY_SELECT_CURPROC 221 * 222 * Select a new current process for this cpu. This satisfies a user 223 * scheduler reschedule request so clear that too. 224 * 225 * This routine is also responsible for equal-priority round-robining, 226 * typically triggered from dummy_schedulerclock(). In our dummy example 227 * all the 'user' threads are LWKT scheduled all at once and we just 228 * call lwkt_switch(). 229 * 230 * MPSAFE 231 */ 232 static 233 void 234 dummy_select_curproc(globaldata_t gd) 235 { 236 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid]; 237 struct lwp *lp; 238 239 clear_user_resched(); 240 spin_lock_wr(&dummy_spin); 241 if ((lp = TAILQ_FIRST(&dummy_runq)) == NULL) { 242 dd->uschedcp = NULL; 243 atomic_clear_int(&dummy_curprocmask, gd->gd_cpumask); 244 spin_unlock_wr(&dummy_spin); 245 } else { 246 --dummy_runqcount; 247 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq); 248 lp->lwp_flag &= ~LWP_ONRUNQ; 249 dd->uschedcp = lp; 250 atomic_set_int(&dummy_curprocmask, gd->gd_cpumask); 251 spin_unlock_wr(&dummy_spin); 252 #ifdef SMP 253 lwkt_acquire(lp->lwp_thread); 254 #endif 255 lwkt_schedule(lp->lwp_thread); 256 } 257 } 258 259 /* 260 * DUMMY_SETRUNQUEUE 261 * 262 * This routine is called to schedule a new user process after a fork. 263 * The scheduler module itself might also call this routine to place 264 * the current process on the userland scheduler's run queue prior 265 * to calling dummy_select_curproc(). 266 * 267 * The caller may set P_PASSIVE_ACQ in p_flag to indicate that we should 268 * attempt to leave the thread on the current cpu. 269 * 270 * MPSAFE 271 */ 272 static void 273 dummy_setrunqueue(struct lwp *lp) 274 { 275 globaldata_t gd = mycpu; 276 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid]; 277 cpumask_t mask; 278 int cpuid; 279 280 if (dd->uschedcp == NULL) { 281 dd->uschedcp = lp; 282 atomic_set_int(&dummy_curprocmask, gd->gd_cpumask); 283 lwkt_schedule(lp->lwp_thread); 284 } else { 285 /* 286 * Add to our global runq 287 */ 288 KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0); 289 spin_lock_wr(&dummy_spin); 290 ++dummy_runqcount; 291 TAILQ_INSERT_TAIL(&dummy_runq, lp, lwp_procq); 292 lp->lwp_flag |= LWP_ONRUNQ; 293 #ifdef SMP 294 lwkt_giveaway(lp->lwp_thread); 295 #endif 296 297 /* lp = TAILQ_FIRST(&dummy_runq); */ 298 299 /* 300 * Notify the next available cpu. P.S. some 301 * cpu affinity could be done here. 302 * 303 * The rdyprocmask bit placeholds the knowledge that there 304 * is a process on the runq that needs service. If the 305 * helper thread cannot find a home for it it will forward 306 * the request to another available cpu. 307 */ 308 mask = ~dummy_curprocmask & dummy_rdyprocmask & 309 gd->gd_other_cpus; 310 if (mask) { 311 cpuid = bsfl(mask); 312 atomic_clear_int(&dummy_rdyprocmask, 1 << cpuid); 313 spin_unlock_wr(&dummy_spin); 314 lwkt_schedule(&dummy_pcpu[cpuid].helper_thread); 315 } else { 316 spin_unlock_wr(&dummy_spin); 317 } 318 } 319 } 320 321 /* 322 * This routine is called from a systimer IPI. Thus it is called with 323 * a critical section held. Any spinlocks we get here that are also 324 * obtained in other procedures must be proected by a critical section 325 * in those other procedures to avoid a deadlock. 326 * 327 * The MP lock may or may not be held on entry and cannot be obtained 328 * by this routine (because it is called from a systimer IPI). Additionally, 329 * because this is equivalent to a FAST interrupt, spinlocks cannot be used 330 * (or at least, you have to check that gd_spin* counts are 0 before you 331 * can). 332 * 333 * This routine is called at ESTCPUFREQ on each cpu independantly. 334 * 335 * This routine typically queues a reschedule request, which will cause 336 * the scheduler's BLAH_select_curproc() to be called as soon as possible. 337 * 338 * MPSAFE 339 */ 340 static 341 void 342 dummy_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp) 343 { 344 globaldata_t gd = mycpu; 345 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid]; 346 347 if (++dd->rrcount >= usched_dummy_rrinterval) { 348 dd->rrcount = 0; 349 need_user_resched(); 350 } 351 } 352 353 /* 354 * DUMMY_RECALCULATE_ESTCPU 355 * 356 * Called once a second for any process that is running or has slept 357 * for less then 2 seconds. 358 * 359 * MPSAFE 360 */ 361 static 362 void 363 dummy_recalculate_estcpu(struct lwp *lp) 364 { 365 } 366 367 static 368 void 369 dummy_yield(struct lwp *lp) 370 { 371 need_user_resched(); 372 } 373 374 /* 375 * DUMMY_RESETPRIORITY 376 * 377 * This routine is called after the kernel has potentially modified 378 * the lwp_rtprio structure. The target process may be running or sleeping 379 * or scheduled but not yet running or owned by another cpu. Basically, 380 * it can be in virtually any state. 381 * 382 * This routine is called by fork1() for initial setup with the process 383 * of the run queue, and also may be called normally with the process on or 384 * off the run queue. 385 * 386 * MPSAFE 387 */ 388 static void 389 dummy_resetpriority(struct lwp *lp) 390 { 391 /* XXX spinlock usually needed */ 392 /* 393 * Set p_priority for general process comparisons 394 */ 395 switch(lp->lwp_rtprio.type) { 396 case RTP_PRIO_REALTIME: 397 lp->lwp_priority = PRIBASE_REALTIME + lp->lwp_rtprio.prio; 398 return; 399 case RTP_PRIO_NORMAL: 400 lp->lwp_priority = PRIBASE_NORMAL + lp->lwp_rtprio.prio; 401 break; 402 case RTP_PRIO_IDLE: 403 lp->lwp_priority = PRIBASE_IDLE + lp->lwp_rtprio.prio; 404 return; 405 case RTP_PRIO_THREAD: 406 lp->lwp_priority = PRIBASE_THREAD + lp->lwp_rtprio.prio; 407 return; 408 } 409 /* XXX spinlock usually needed */ 410 } 411 412 413 /* 414 * DUMMY_FORKING 415 * 416 * Called from fork1() when a new child process is being created. Allows 417 * the scheduler to predispose the child process before it gets scheduled. 418 * 419 * MPSAFE 420 */ 421 static void 422 dummy_forking(struct lwp *plp, struct lwp *lp) 423 { 424 lp->lwp_estcpu = plp->lwp_estcpu; 425 #if 0 426 ++plp->lwp_estcpu; 427 #endif 428 } 429 430 /* 431 * DUMMY_EXITING 432 * 433 * Called when the parent reaps a child. Typically used to propogate cpu 434 * use by the child back to the parent as part of a batch detection 435 * heuristic. 436 * 437 * NOTE: cpu use is not normally back-propogated to PID 1. 438 * 439 * MPSAFE 440 */ 441 static void 442 dummy_exiting(struct lwp *plp, struct lwp *lp) 443 { 444 } 445 446 /* 447 * SMP systems may need a scheduler helper thread. This is how one can be 448 * setup. 449 * 450 * We use a neat LWKT scheduling trick to interlock the helper thread. It 451 * is possible to deschedule an LWKT thread and then do some work before 452 * switching away. The thread can be rescheduled at any time, even before 453 * we switch away. 454 */ 455 #ifdef SMP 456 457 static void 458 dummy_sched_thread(void *dummy) 459 { 460 globaldata_t gd; 461 dummy_pcpu_t dd; 462 struct lwp *lp; 463 cpumask_t cpumask; 464 cpumask_t tmpmask; 465 int cpuid; 466 int tmpid; 467 468 gd = mycpu; 469 cpuid = gd->gd_cpuid; 470 dd = &dummy_pcpu[cpuid]; 471 cpumask = 1 << cpuid; 472 473 /* 474 * Our Scheduler helper thread does not need to hold the MP lock 475 */ 476 rel_mplock(); 477 478 for (;;) { 479 lwkt_deschedule_self(gd->gd_curthread); /* interlock */ 480 atomic_set_int(&dummy_rdyprocmask, cpumask); 481 spin_lock_wr(&dummy_spin); 482 if (dd->uschedcp) { 483 /* 484 * We raced another cpu trying to schedule a thread onto us. 485 * If the runq isn't empty hit another free cpu. 486 */ 487 tmpmask = ~dummy_curprocmask & dummy_rdyprocmask & 488 gd->gd_other_cpus; 489 if (tmpmask && dummy_runqcount) { 490 tmpid = bsfl(tmpmask); 491 KKASSERT(tmpid != cpuid); 492 atomic_clear_int(&dummy_rdyprocmask, 1 << tmpid); 493 spin_unlock_wr(&dummy_spin); 494 lwkt_schedule(&dummy_pcpu[tmpid].helper_thread); 495 } else { 496 spin_unlock_wr(&dummy_spin); 497 } 498 } else if ((lp = TAILQ_FIRST(&dummy_runq)) != NULL) { 499 --dummy_runqcount; 500 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq); 501 lp->lwp_flag &= ~LWP_ONRUNQ; 502 dd->uschedcp = lp; 503 atomic_set_int(&dummy_curprocmask, cpumask); 504 spin_unlock_wr(&dummy_spin); 505 #ifdef SMP 506 lwkt_acquire(lp->lwp_thread); 507 #endif 508 lwkt_schedule(lp->lwp_thread); 509 } else { 510 spin_unlock_wr(&dummy_spin); 511 } 512 lwkt_switch(); 513 } 514 } 515 516 /* 517 * Setup our scheduler helpers. Note that curprocmask bit 0 has already 518 * been cleared by rqinit() and we should not mess with it further. 519 */ 520 static void 521 dummy_sched_thread_cpu_init(void) 522 { 523 int i; 524 525 if (bootverbose) 526 kprintf("start dummy scheduler helpers on cpus:"); 527 528 for (i = 0; i < ncpus; ++i) { 529 dummy_pcpu_t dd = &dummy_pcpu[i]; 530 cpumask_t mask = 1 << i; 531 532 if ((mask & smp_active_mask) == 0) 533 continue; 534 535 if (bootverbose) 536 kprintf(" %d", i); 537 538 lwkt_create(dummy_sched_thread, NULL, NULL, &dd->helper_thread, 539 TDF_STOPREQ, i, "dsched %d", i); 540 541 /* 542 * Allow user scheduling on the target cpu. cpu #0 has already 543 * been enabled in rqinit(). 544 */ 545 if (i) 546 atomic_clear_int(&dummy_curprocmask, mask); 547 atomic_set_int(&dummy_rdyprocmask, mask); 548 } 549 if (bootverbose) 550 kprintf("\n"); 551 } 552 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND, 553 dummy_sched_thread_cpu_init, NULL) 554 555 #endif 556 557