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
35 #include <sys/param.h>
36 #include <sys/systm.h>
37 #include <sys/kernel.h>
38 #include <sys/lock.h>
39 #include <sys/queue.h>
40 #include <sys/proc.h>
41 #include <sys/rtprio.h>
42 #include <sys/uio.h>
43 #include <sys/sysctl.h>
44 #include <sys/resourcevar.h>
45 #include <sys/spinlock.h>
46 #include <machine/cpu.h>
47 #include <machine/smp.h>
48
49 #include <sys/thread2.h>
50 #include <sys/spinlock2.h>
51
52 #define MAXPRI 128
53 #define PRIBASE_REALTIME 0
54 #define PRIBASE_NORMAL MAXPRI
55 #define PRIBASE_IDLE (MAXPRI * 2)
56 #define PRIBASE_THREAD (MAXPRI * 3)
57 #define PRIBASE_NULL (MAXPRI * 4)
58
59 #define lwp_priority lwp_usdata.bsd4.priority
60 #define lwp_estcpu lwp_usdata.bsd4.estcpu
61
62 static void dummy_acquire_curproc(struct lwp *lp);
63 static void dummy_release_curproc(struct lwp *lp);
64 static void dummy_select_curproc(globaldata_t gd);
65 static void dummy_setrunqueue(struct lwp *lp);
66 static void dummy_schedulerclock(struct lwp *lp, sysclock_t period,
67 sysclock_t cpstamp);
68 static void dummy_recalculate_estcpu(struct lwp *lp);
69 static void dummy_resetpriority(struct lwp *lp);
70 static void dummy_forking(struct lwp *plp, struct lwp *lp);
71 static void dummy_exiting(struct lwp *plp, struct proc *child);
72 static void dummy_uload_update(struct lwp *lp);
73 static void dummy_yield(struct lwp *lp);
74 static void dummy_changedcpu(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 dummy_uload_update,
90 NULL, /* setcpumask not supported */
91 dummy_yield,
92 dummy_changedcpu
93 };
94
95 struct usched_dummy_pcpu {
96 int rrcount;
97 struct thread *helper_thread;
98 struct lwp *uschedcp;
99 };
100
101 typedef struct usched_dummy_pcpu *dummy_pcpu_t;
102
103 static struct usched_dummy_pcpu dummy_pcpu[MAXCPU];
104 static cpumask_t dummy_curprocmask = CPUMASK_INITIALIZER_ALLONES;
105 static cpumask_t dummy_rdyprocmask;
106 static struct spinlock dummy_spin;
107 static TAILQ_HEAD(rq, lwp) dummy_runq;
108 static int dummy_runqcount;
109
110 static int usched_dummy_rrinterval = (ESTCPUFREQ + 9) / 10;
111 SYSCTL_INT(_kern, OID_AUTO, usched_dummy_rrinterval, CTLFLAG_RW,
112 &usched_dummy_rrinterval, 0, "");
113
114 /*
115 * Initialize the run queues at boot time, clear cpu 0 in curprocmask
116 * to allow dummy scheduling on cpu 0.
117 */
118 static void
dummyinit(void * dummy)119 dummyinit(void *dummy)
120 {
121 TAILQ_INIT(&dummy_runq);
122 spin_init(&dummy_spin, "uscheddummy");
123 ATOMIC_CPUMASK_NANDBIT(dummy_curprocmask, 0);
124 }
125 SYSINIT(runqueue, SI_BOOT2_USCHED, SI_ORDER_FIRST, dummyinit, NULL);
126
127 /*
128 * DUMMY_ACQUIRE_CURPROC
129 *
130 * This function is called when the kernel intends to return to userland.
131 * It is responsible for making the thread the current designated userland
132 * thread for this cpu, blocking if necessary.
133 *
134 * The kernel will not depress our LWKT priority until after we return,
135 * in case we have to shove over to another cpu.
136 *
137 * We must determine our thread's disposition before we switch away. This
138 * is very sensitive code.
139 *
140 * We are expected to handle userland reschedule requests here too.
141 *
142 * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE
143 * TO ANOTHER CPU! Because most of the kernel assumes that no migration will
144 * occur, this function is called only under very controlled circumstances.
145 *
146 * MPSAFE
147 */
148 static void
dummy_acquire_curproc(struct lwp * lp)149 dummy_acquire_curproc(struct lwp *lp)
150 {
151 globaldata_t gd = mycpu;
152 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
153 thread_t td = lp->lwp_thread;
154
155 /*
156 * Possibly select another thread
157 */
158 if (user_resched_wanted())
159 dummy_select_curproc(gd);
160
161 /*
162 * If this cpu has no current thread, select ourself
163 */
164 if (dd->uschedcp == lp ||
165 (dd->uschedcp == NULL && TAILQ_EMPTY(&dummy_runq))) {
166 ATOMIC_CPUMASK_ORBIT(dummy_curprocmask, gd->gd_cpuid);
167 dd->uschedcp = lp;
168 return;
169 }
170
171 /*
172 * If this cpu's current user process thread is not our thread,
173 * deschedule ourselves and place us on the run queue, then
174 * switch away.
175 *
176 * We loop until we become the current process. Its a good idea
177 * to run any passive release(s) before we mess with the scheduler
178 * so our thread is in the expected state.
179 */
180 KKASSERT(dd->uschedcp != lp);
181 if (td->td_release)
182 td->td_release(lp->lwp_thread);
183 do {
184 crit_enter();
185 lwkt_deschedule_self(td);
186 dummy_setrunqueue(lp);
187 if ((td->td_flags & TDF_RUNQ) == 0)
188 ++lp->lwp_ru.ru_nivcsw;
189 lwkt_switch(); /* WE MAY MIGRATE TO ANOTHER CPU */
190 crit_exit();
191 gd = mycpu;
192 dd = &dummy_pcpu[gd->gd_cpuid];
193 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
194 } while (dd->uschedcp != lp);
195 }
196
197 /*
198 * DUMMY_RELEASE_CURPROC
199 *
200 * This routine detaches the current thread from the userland scheduler,
201 * usually because the thread needs to run in the kernel (at kernel priority)
202 * for a while.
203 *
204 * This routine is also responsible for selecting a new thread to
205 * make the current thread.
206 *
207 * MPSAFE
208 */
209 static void
dummy_release_curproc(struct lwp * lp)210 dummy_release_curproc(struct lwp *lp)
211 {
212 globaldata_t gd = mycpu;
213 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
214
215 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
216 if (dd->uschedcp == lp) {
217 dummy_select_curproc(gd);
218 }
219 }
220
221 /*
222 * DUMMY_SELECT_CURPROC
223 *
224 * Select a new current process for this cpu. This satisfies a user
225 * scheduler reschedule request so clear that too.
226 *
227 * This routine is also responsible for equal-priority round-robining,
228 * typically triggered from dummy_schedulerclock(). In our dummy example
229 * all the 'user' threads are LWKT scheduled all at once and we just
230 * call lwkt_switch().
231 *
232 * MPSAFE
233 */
234 static
235 void
dummy_select_curproc(globaldata_t gd)236 dummy_select_curproc(globaldata_t gd)
237 {
238 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
239 struct lwp *lp;
240
241 clear_user_resched();
242 spin_lock(&dummy_spin);
243 if ((lp = TAILQ_FIRST(&dummy_runq)) == NULL) {
244 dd->uschedcp = NULL;
245 ATOMIC_CPUMASK_NANDBIT(dummy_curprocmask, gd->gd_cpuid);
246 spin_unlock(&dummy_spin);
247 } else {
248 --dummy_runqcount;
249 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq);
250 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
251 dd->uschedcp = lp;
252 ATOMIC_CPUMASK_ORBIT(dummy_curprocmask, gd->gd_cpuid);
253 spin_unlock(&dummy_spin);
254 lwkt_acquire(lp->lwp_thread);
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 LWP_PASSIVE_ACQ in lwp_flags to indicate that we should
268 * attempt to leave the thread on the current cpu.
269 *
270 * MPSAFE
271 */
272 static void
dummy_setrunqueue(struct lwp * lp)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_CPUMASK_ORBIT(dummy_curprocmask, gd->gd_cpuid);
283 lwkt_schedule(lp->lwp_thread);
284 } else {
285 /*
286 * Add to our global runq
287 */
288 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
289 spin_lock(&dummy_spin);
290 ++dummy_runqcount;
291 TAILQ_INSERT_TAIL(&dummy_runq, lp, lwp_procq);
292 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
293 lwkt_giveaway(lp->lwp_thread);
294
295 /* lp = TAILQ_FIRST(&dummy_runq); */
296
297 /*
298 * Notify the next available cpu. P.S. some
299 * cpu affinity could be done here.
300 *
301 * The rdyprocmask bit placeholds the knowledge that there
302 * is a process on the runq that needs service. If the
303 * helper thread cannot find a home for it it will forward
304 * the request to another available cpu.
305 */
306 mask = dummy_rdyprocmask;
307 CPUMASK_NANDMASK(mask, dummy_curprocmask);
308 CPUMASK_ANDMASK(mask, gd->gd_other_cpus);
309 if (CPUMASK_TESTNZERO(mask)) {
310 cpuid = BSFCPUMASK(mask);
311 ATOMIC_CPUMASK_NANDBIT(dummy_rdyprocmask, cpuid);
312 spin_unlock(&dummy_spin);
313 lwkt_schedule(dummy_pcpu[cpuid].helper_thread);
314 } else {
315 spin_unlock(&dummy_spin);
316 }
317 }
318 }
319
320 /*
321 * This routine is called from a systimer IPI. It must NEVER block.
322 * If a lwp compatible with this scheduler is the currently running
323 * thread this function is called with a non-NULL lp, otherwise it
324 * will be called with a NULL lp.
325 *
326 * This routine is called at ESTCPUFREQ on each cpu independantly.
327 *
328 * This routine typically queues a reschedule request, which will cause
329 * the scheduler's BLAH_select_curproc() to be called as soon as possible.
330 */
331 static
332 void
dummy_schedulerclock(struct lwp * lp,sysclock_t period,sysclock_t cpstamp)333 dummy_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp)
334 {
335 globaldata_t gd = mycpu;
336 dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
337
338 if (lp == NULL)
339 return;
340
341 if (++dd->rrcount >= usched_dummy_rrinterval) {
342 dd->rrcount = 0;
343 need_user_resched();
344 }
345 }
346
347 /*
348 * DUMMY_RECALCULATE_ESTCPU
349 *
350 * Called once a second for any process that is running or has slept
351 * for less then 2 seconds.
352 *
353 * MPSAFE
354 */
355 static
356 void
dummy_recalculate_estcpu(struct lwp * lp)357 dummy_recalculate_estcpu(struct lwp *lp)
358 {
359 }
360
361 /*
362 * MPSAFE
363 */
364 static
365 void
dummy_yield(struct lwp * lp)366 dummy_yield(struct lwp *lp)
367 {
368 need_user_resched();
369 }
370
371 static
372 void
dummy_changedcpu(struct lwp * lp __unused)373 dummy_changedcpu(struct lwp *lp __unused)
374 {
375 }
376
377 /*
378 * DUMMY_RESETPRIORITY
379 *
380 * This routine is called after the kernel has potentially modified
381 * the lwp_rtprio structure. The target process may be running or sleeping
382 * or scheduled but not yet running or owned by another cpu. Basically,
383 * it can be in virtually any state.
384 *
385 * This routine is called by fork1() for initial setup with the process
386 * of the run queue, and also may be called normally with the process on or
387 * off the run queue.
388 *
389 * MPSAFE
390 */
391 static void
dummy_resetpriority(struct lwp * lp)392 dummy_resetpriority(struct lwp *lp)
393 {
394 /* XXX spinlock usually needed */
395 /*
396 * Set p_priority for general process comparisons
397 */
398 switch(lp->lwp_rtprio.type) {
399 case RTP_PRIO_REALTIME:
400 lp->lwp_priority = PRIBASE_REALTIME + lp->lwp_rtprio.prio;
401 return;
402 case RTP_PRIO_NORMAL:
403 lp->lwp_priority = PRIBASE_NORMAL + lp->lwp_rtprio.prio;
404 break;
405 case RTP_PRIO_IDLE:
406 lp->lwp_priority = PRIBASE_IDLE + lp->lwp_rtprio.prio;
407 return;
408 case RTP_PRIO_THREAD:
409 lp->lwp_priority = PRIBASE_THREAD + lp->lwp_rtprio.prio;
410 return;
411 }
412
413 /*
414 * td_upri has normal sense (higher numbers are more desireable),
415 * so negate it.
416 */
417 lp->lwp_thread->td_upri = -lp->lwp_priority;
418 /* XXX spinlock usually needed */
419 }
420
421
422 /*
423 * DUMMY_FORKING
424 *
425 * Called from fork1() when a new child process is being created. Allows
426 * the scheduler to predispose the child process before it gets scheduled.
427 *
428 * MPSAFE
429 */
430 static void
dummy_forking(struct lwp * plp,struct lwp * lp)431 dummy_forking(struct lwp *plp, struct lwp *lp)
432 {
433 lp->lwp_estcpu = plp->lwp_estcpu;
434 #if 0
435 ++plp->lwp_estcpu;
436 #endif
437 }
438
439 /*
440 * Called when a lwp is being removed from this scheduler, typically
441 * during lwp_exit().
442 */
443 static void
dummy_exiting(struct lwp * plp,struct proc * child)444 dummy_exiting(struct lwp *plp, struct proc *child)
445 {
446 }
447
448 static void
dummy_uload_update(struct lwp * lp)449 dummy_uload_update(struct lwp *lp)
450 {
451 }
452
453 /*
454 * SMP systems may need a scheduler helper thread. This is how one can be
455 * setup.
456 *
457 * We use a neat LWKT scheduling trick to interlock the helper thread. It
458 * is possible to deschedule an LWKT thread and then do some work before
459 * switching away. The thread can be rescheduled at any time, even before
460 * we switch away.
461 *
462 * MPSAFE
463 */
464 static void
dummy_sched_thread(void * dummy)465 dummy_sched_thread(void *dummy)
466 {
467 globaldata_t gd;
468 dummy_pcpu_t dd;
469 struct lwp *lp;
470 cpumask_t cpumask;
471 cpumask_t tmpmask;
472 int cpuid;
473 int tmpid;
474
475 gd = mycpu;
476 cpuid = gd->gd_cpuid;
477 dd = &dummy_pcpu[cpuid];
478 CPUMASK_ASSBIT(cpumask, cpuid);
479
480 for (;;) {
481 lwkt_deschedule_self(gd->gd_curthread); /* interlock */
482 ATOMIC_CPUMASK_ORBIT(dummy_rdyprocmask, cpuid);
483 spin_lock(&dummy_spin);
484 if (dd->uschedcp) {
485 /*
486 * We raced another cpu trying to schedule a thread onto us.
487 * If the runq isn't empty hit another free cpu.
488 */
489 tmpmask = dummy_rdyprocmask;
490 CPUMASK_NANDMASK(tmpmask, dummy_curprocmask);
491 CPUMASK_ANDMASK(tmpmask, gd->gd_other_cpus);
492 if (CPUMASK_TESTNZERO(tmpmask) && dummy_runqcount) {
493 tmpid = BSFCPUMASK(tmpmask);
494 KKASSERT(tmpid != cpuid);
495 ATOMIC_CPUMASK_NANDBIT(dummy_rdyprocmask, tmpid);
496 spin_unlock(&dummy_spin);
497 lwkt_schedule(dummy_pcpu[tmpid].helper_thread);
498 } else {
499 spin_unlock(&dummy_spin);
500 }
501 } else if ((lp = TAILQ_FIRST(&dummy_runq)) != NULL) {
502 --dummy_runqcount;
503 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq);
504 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
505 dd->uschedcp = lp;
506 ATOMIC_CPUMASK_ORBIT(dummy_curprocmask, cpuid);
507 spin_unlock(&dummy_spin);
508 lwkt_acquire(lp->lwp_thread);
509 lwkt_schedule(lp->lwp_thread);
510 } else {
511 spin_unlock(&dummy_spin);
512 }
513 lwkt_switch();
514 }
515 }
516
517 /*
518 * Setup our scheduler helpers. Note that curprocmask bit 0 has already
519 * been cleared by rqinit() and we should not mess with it further.
520 */
521 static void
dummy_sched_thread_cpu_init(void)522 dummy_sched_thread_cpu_init(void)
523 {
524 int i;
525
526 if (bootverbose)
527 kprintf("start dummy scheduler helpers on cpus:");
528
529 for (i = 0; i < ncpus; ++i) {
530 dummy_pcpu_t dd = &dummy_pcpu[i];
531 cpumask_t mask;
532
533 CPUMASK_ASSBIT(mask, i);
534
535 if (CPUMASK_TESTMASK(mask, smp_active_mask) == 0)
536 continue;
537
538 if (bootverbose)
539 kprintf(" %d", i);
540
541 lwkt_create(dummy_sched_thread, NULL, &dd->helper_thread, NULL,
542 TDF_NOSTART, i, "dsched %d", i);
543
544 /*
545 * Allow user scheduling on the target cpu. cpu #0 has already
546 * been enabled in rqinit().
547 */
548 if (i)
549 ATOMIC_CPUMASK_NANDMASK(dummy_curprocmask, mask);
550 ATOMIC_CPUMASK_ORMASK(dummy_rdyprocmask, mask);
551 }
552 if (bootverbose)
553 kprintf("\n");
554 }
555 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
556 dummy_sched_thread_cpu_init, NULL);
557