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