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