kernel - usched_dfly revamp (4), improve tail
[dragonfly.git] / sys / kern / usched_dummy.c
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 #include <sys/mplock2.h>
54
55 #define MAXPRI                  128
56 #define PRIBASE_REALTIME        0
57 #define PRIBASE_NORMAL          MAXPRI
58 #define PRIBASE_IDLE            (MAXPRI * 2)
59 #define PRIBASE_THREAD          (MAXPRI * 3)
60 #define PRIBASE_NULL            (MAXPRI * 4)
61
62 #define lwp_priority    lwp_usdata.bsd4.priority
63 #define lwp_estcpu      lwp_usdata.bsd4.estcpu
64
65 static void dummy_acquire_curproc(struct lwp *lp);
66 static void dummy_release_curproc(struct lwp *lp);
67 static void dummy_select_curproc(globaldata_t gd);
68 static void dummy_setrunqueue(struct lwp *lp);
69 static void dummy_schedulerclock(struct lwp *lp, sysclock_t period,
70                                 sysclock_t cpstamp);
71 static void dummy_recalculate_estcpu(struct lwp *lp);
72 static void dummy_resetpriority(struct lwp *lp);
73 static void dummy_forking(struct lwp *plp, struct lwp *lp);
74 static void dummy_exiting(struct lwp *plp, struct proc *child);
75 static void dummy_uload_update(struct lwp *lp);
76 static void dummy_yield(struct lwp *lp);
77
78 struct usched usched_dummy = {
79         { NULL },
80         "dummy", "Dummy DragonFly Scheduler",
81         NULL,                   /* default registration */
82         NULL,                   /* default deregistration */
83         dummy_acquire_curproc,
84         dummy_release_curproc,
85         dummy_setrunqueue,
86         dummy_schedulerclock,
87         dummy_recalculate_estcpu,
88         dummy_resetpriority,
89         dummy_forking,
90         dummy_exiting,
91         dummy_uload_update,
92         NULL,                   /* setcpumask not supported */
93         dummy_yield
94 };
95
96 struct usched_dummy_pcpu {
97         int     rrcount;
98         struct thread helper_thread;
99         struct lwp *uschedcp;
100 };
101
102 typedef struct usched_dummy_pcpu *dummy_pcpu_t;
103
104 static struct usched_dummy_pcpu dummy_pcpu[MAXCPU];
105 static cpumask_t dummy_curprocmask = -1;
106 static cpumask_t dummy_rdyprocmask;
107 static struct spinlock dummy_spin;
108 static TAILQ_HEAD(rq, lwp) dummy_runq;
109 static int dummy_runqcount;
110
111 static int usched_dummy_rrinterval = (ESTCPUFREQ + 9) / 10;
112 SYSCTL_INT(_kern, OID_AUTO, usched_dummy_rrinterval, CTLFLAG_RW,
113         &usched_dummy_rrinterval, 0, "");
114
115 /*
116  * Initialize the run queues at boot time, clear cpu 0 in curprocmask
117  * to allow dummy scheduling on cpu 0.
118  */
119 static void
120 dummyinit(void *dummy)
121 {
122         TAILQ_INIT(&dummy_runq);
123         spin_init(&dummy_spin);
124         atomic_clear_cpumask(&dummy_curprocmask, 1);
125 }
126 SYSINIT(runqueue, SI_BOOT2_USCHED, SI_ORDER_FIRST, dummyinit, NULL)
127
128 /*
129  * DUMMY_ACQUIRE_CURPROC
130  *
131  * This function is called when the kernel intends to return to userland.
132  * It is responsible for making the thread the current designated userland
133  * thread for this cpu, blocking if necessary.
134  *
135  * We are expected to handle userland reschedule requests here too.
136  *
137  * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE
138  * TO ANOTHER CPU!  Because most of the kernel assumes that no migration will
139  * occur, this function is called only under very controlled circumstances.
140  *
141  * MPSAFE
142  */
143 static void
144 dummy_acquire_curproc(struct lwp *lp)
145 {
146         globaldata_t gd = mycpu;
147         dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
148         thread_t td = lp->lwp_thread;
149
150         /*
151          * Possibly select another thread
152          */
153         if (user_resched_wanted())
154                 dummy_select_curproc(gd);
155
156         /*
157          * If this cpu has no current thread, select ourself
158          */
159         if (dd->uschedcp == lp ||
160             (dd->uschedcp == NULL && TAILQ_EMPTY(&dummy_runq))) {
161                 atomic_set_cpumask(&dummy_curprocmask, gd->gd_cpumask);
162                 dd->uschedcp = lp;
163                 return;
164         }
165
166         /*
167          * If this cpu's current user process thread is not our thread,
168          * deschedule ourselves and place us on the run queue, then
169          * switch away.
170          *
171          * We loop until we become the current process.  Its a good idea
172          * to run any passive release(s) before we mess with the scheduler
173          * so our thread is in the expected state.
174          */
175         KKASSERT(dd->uschedcp != lp);
176         if (td->td_release)
177                 td->td_release(lp->lwp_thread);
178         do {
179                 crit_enter();
180                 lwkt_deschedule_self(td);
181                 dummy_setrunqueue(lp);
182                 if ((td->td_flags & TDF_RUNQ) == 0)
183                         ++lp->lwp_ru.ru_nivcsw;
184                 lwkt_switch();          /* WE MAY MIGRATE TO ANOTHER CPU */
185                 crit_exit();
186                 gd = mycpu;
187                 dd = &dummy_pcpu[gd->gd_cpuid];
188                 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
189         } while (dd->uschedcp != lp);
190 }
191
192 /*
193  * DUMMY_RELEASE_CURPROC
194  *
195  * This routine detaches the current thread from the userland scheduler,
196  * usually because the thread needs to run in the kernel (at kernel priority)
197  * for a while.
198  *
199  * This routine is also responsible for selecting a new thread to
200  * make the current thread.
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_mpflags & LWP_MP_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(&dummy_spin);
238         if ((lp = TAILQ_FIRST(&dummy_runq)) == NULL) {
239                 dd->uschedcp = NULL;
240                 atomic_clear_cpumask(&dummy_curprocmask, gd->gd_cpumask);
241                 spin_unlock(&dummy_spin);
242         } else {
243                 --dummy_runqcount;
244                 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq);
245                 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
246                 dd->uschedcp = lp;
247                 atomic_set_cpumask(&dummy_curprocmask, gd->gd_cpumask);
248                 spin_unlock(&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 LWP_PASSIVE_ACQ in lwp_flags 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_cpumask(&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_mpflags & LWP_MP_ONRUNQ) == 0);
286                 spin_lock(&dummy_spin);
287                 ++dummy_runqcount;
288                 TAILQ_INSERT_TAIL(&dummy_runq, lp, lwp_procq);
289                 atomic_set_int(&lp->lwp_mpflags, LWP_MP_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 = BSFCPUMASK(mask);
309                         atomic_clear_cpumask(&dummy_rdyprocmask, CPUMASK(cpuid));
310                         spin_unlock(&dummy_spin);
311                         lwkt_schedule(&dummy_pcpu[cpuid].helper_thread);
312                 } else {
313                         spin_unlock(&dummy_spin);
314                 }
315         }
316 }
317
318 /*
319  * This routine is called from a systimer IPI.  It must NEVER block.
320  * If a lwp compatible with this scheduler is the currently running
321  * thread this function is called with a non-NULL lp, otherwise it
322  * will be called with a NULL lp.
323  *
324  * This routine is called at ESTCPUFREQ on each cpu independantly.
325  *
326  * This routine typically queues a reschedule request, which will cause
327  * the scheduler's BLAH_select_curproc() to be called as soon as possible.
328  */
329 static
330 void
331 dummy_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp)
332 {
333         globaldata_t gd = mycpu;
334         dummy_pcpu_t dd = &dummy_pcpu[gd->gd_cpuid];
335
336         if (lp == NULL)
337                 return;
338
339         if (++dd->rrcount >= usched_dummy_rrinterval) {
340                 dd->rrcount = 0;
341                 need_user_resched();
342         }
343 }
344
345 /*
346  * DUMMY_RECALCULATE_ESTCPU
347  *
348  * Called once a second for any process that is running or has slept
349  * for less then 2 seconds.
350  *
351  * MPSAFE
352  */
353 static
354 void 
355 dummy_recalculate_estcpu(struct lwp *lp)
356 {
357 }
358
359 /*
360  * MPSAFE
361  */
362 static
363 void
364 dummy_yield(struct lwp *lp)
365 {
366         need_user_resched();
367 }
368
369 /*
370  * DUMMY_RESETPRIORITY
371  *
372  * This routine is called after the kernel has potentially modified
373  * the lwp_rtprio structure.  The target process may be running or sleeping
374  * or scheduled but not yet running or owned by another cpu.  Basically,
375  * it can be in virtually any state.
376  *
377  * This routine is called by fork1() for initial setup with the process 
378  * of the run queue, and also may be called normally with the process on or
379  * off the run queue.
380  *
381  * MPSAFE
382  */
383 static void
384 dummy_resetpriority(struct lwp *lp)
385 {
386         /* XXX spinlock usually needed */
387         /*
388          * Set p_priority for general process comparisons
389          */
390         switch(lp->lwp_rtprio.type) {
391         case RTP_PRIO_REALTIME:
392                 lp->lwp_priority = PRIBASE_REALTIME + lp->lwp_rtprio.prio;
393                 return;
394         case RTP_PRIO_NORMAL:
395                 lp->lwp_priority = PRIBASE_NORMAL + lp->lwp_rtprio.prio;
396                 break;
397         case RTP_PRIO_IDLE:
398                 lp->lwp_priority = PRIBASE_IDLE + lp->lwp_rtprio.prio;
399                 return;
400         case RTP_PRIO_THREAD:
401                 lp->lwp_priority = PRIBASE_THREAD + lp->lwp_rtprio.prio;
402                 return;
403         }
404
405         /*
406          * td_upri has normal sense (higher numbers are more desireable),
407          * so negate it.
408          */
409         lp->lwp_thread->td_upri = -lp->lwp_priority;
410         /* XXX spinlock usually needed */
411 }
412
413
414 /*
415  * DUMMY_FORKING
416  *
417  * Called from fork1() when a new child process is being created.  Allows
418  * the scheduler to predispose the child process before it gets scheduled.
419  *
420  * MPSAFE
421  */
422 static void
423 dummy_forking(struct lwp *plp, struct lwp *lp)
424 {
425         lp->lwp_estcpu = plp->lwp_estcpu;
426 #if 0
427         ++plp->lwp_estcpu;
428 #endif
429 }
430
431 /*
432  * Called when a lwp is being removed from this scheduler, typically
433  * during lwp_exit().
434  */
435 static void
436 dummy_exiting(struct lwp *plp, struct proc *child)
437 {
438 }
439
440 static void
441 dummy_uload_update(struct lwp *lp)
442 {
443 }
444
445 /*
446  * SMP systems may need a scheduler helper thread.  This is how one can be
447  * setup.
448  *
449  * We use a neat LWKT scheduling trick to interlock the helper thread.  It
450  * is possible to deschedule an LWKT thread and then do some work before
451  * switching away.  The thread can be rescheduled at any time, even before
452  * we switch away.
453  *
454  * MPSAFE
455  */
456 #ifdef SMP
457
458 static void
459 dummy_sched_thread(void *dummy)
460 {
461     globaldata_t gd;
462     dummy_pcpu_t dd;
463     struct lwp *lp;
464     cpumask_t cpumask;
465     cpumask_t tmpmask;
466     int cpuid;
467     int tmpid;
468
469     gd = mycpu;
470     cpuid = gd->gd_cpuid;
471     dd = &dummy_pcpu[cpuid];
472     cpumask = CPUMASK(cpuid);
473
474     for (;;) {
475         lwkt_deschedule_self(gd->gd_curthread);         /* interlock */
476         atomic_set_cpumask(&dummy_rdyprocmask, cpumask);
477         spin_lock(&dummy_spin);
478         if (dd->uschedcp) {
479                 /*
480                  * We raced another cpu trying to schedule a thread onto us.
481                  * If the runq isn't empty hit another free cpu.
482                  */
483                 tmpmask = ~dummy_curprocmask & dummy_rdyprocmask & 
484                           gd->gd_other_cpus;
485                 if (tmpmask && dummy_runqcount) {
486                         tmpid = BSFCPUMASK(tmpmask);
487                         KKASSERT(tmpid != cpuid);
488                         atomic_clear_cpumask(&dummy_rdyprocmask, CPUMASK(tmpid));
489                         spin_unlock(&dummy_spin);
490                         lwkt_schedule(&dummy_pcpu[tmpid].helper_thread);
491                 } else {
492                         spin_unlock(&dummy_spin);
493                 }
494         } else if ((lp = TAILQ_FIRST(&dummy_runq)) != NULL) {
495                 --dummy_runqcount;
496                 TAILQ_REMOVE(&dummy_runq, lp, lwp_procq);
497                 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
498                 dd->uschedcp = lp;
499                 atomic_set_cpumask(&dummy_curprocmask, cpumask);
500                 spin_unlock(&dummy_spin);
501 #ifdef SMP
502                 lwkt_acquire(lp->lwp_thread);
503 #endif
504                 lwkt_schedule(lp->lwp_thread);
505         } else {
506                 spin_unlock(&dummy_spin);
507         }
508         lwkt_switch();
509     }
510 }
511
512 /*
513  * Setup our scheduler helpers.  Note that curprocmask bit 0 has already
514  * been cleared by rqinit() and we should not mess with it further.
515  */
516 static void
517 dummy_sched_thread_cpu_init(void)
518 {
519     int i;
520
521     if (bootverbose)
522         kprintf("start dummy scheduler helpers on cpus:");
523
524     for (i = 0; i < ncpus; ++i) {
525         dummy_pcpu_t dd = &dummy_pcpu[i];
526         cpumask_t mask = CPUMASK(i);
527
528         if ((mask & smp_active_mask) == 0)
529             continue;
530
531         if (bootverbose)
532             kprintf(" %d", i);
533
534         lwkt_create(dummy_sched_thread, NULL, NULL, &dd->helper_thread, 
535                     TDF_NOSTART, i, "dsched %d", i);
536
537         /*
538          * Allow user scheduling on the target cpu.  cpu #0 has already
539          * been enabled in rqinit().
540          */
541         if (i)
542             atomic_clear_cpumask(&dummy_curprocmask, mask);
543         atomic_set_cpumask(&dummy_rdyprocmask, mask);
544     }
545     if (bootverbose)
546         kprintf("\n");
547 }
548 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
549         dummy_sched_thread_cpu_init, NULL)
550
551 #endif
552