kernel - Attempt to fix two out-of-order read MP races
[dragonfly.git] / sys / kern / lwkt_thread.c
1 /*
2  * Copyright (c) 2003-2010 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 /*
36  * Each cpu in a system has its own self-contained light weight kernel
37  * thread scheduler, which means that generally speaking we only need
38  * to use a critical section to avoid problems.  Foreign thread 
39  * scheduling is queued via (async) IPIs.
40  */
41
42 #include <sys/param.h>
43 #include <sys/systm.h>
44 #include <sys/kernel.h>
45 #include <sys/proc.h>
46 #include <sys/rtprio.h>
47 #include <sys/kinfo.h>
48 #include <sys/queue.h>
49 #include <sys/sysctl.h>
50 #include <sys/kthread.h>
51 #include <machine/cpu.h>
52 #include <sys/lock.h>
53 #include <sys/caps.h>
54 #include <sys/spinlock.h>
55 #include <sys/ktr.h>
56
57 #include <sys/thread2.h>
58 #include <sys/spinlock2.h>
59 #include <sys/mplock2.h>
60
61 #include <sys/dsched.h>
62
63 #include <vm/vm.h>
64 #include <vm/vm_param.h>
65 #include <vm/vm_kern.h>
66 #include <vm/vm_object.h>
67 #include <vm/vm_page.h>
68 #include <vm/vm_map.h>
69 #include <vm/vm_pager.h>
70 #include <vm/vm_extern.h>
71
72 #include <machine/stdarg.h>
73 #include <machine/smp.h>
74
75 #if !defined(KTR_CTXSW)
76 #define KTR_CTXSW KTR_ALL
77 #endif
78 KTR_INFO_MASTER(ctxsw);
79 KTR_INFO(KTR_CTXSW, ctxsw, sw, 0, "#cpu[%d].td = %p",
80          sizeof(int) + sizeof(struct thread *));
81 KTR_INFO(KTR_CTXSW, ctxsw, pre, 1, "#cpu[%d].td = %p",
82          sizeof(int) + sizeof(struct thread *));
83 KTR_INFO(KTR_CTXSW, ctxsw, newtd, 2, "#threads[%p].name = %s",
84          sizeof (struct thread *) + sizeof(char *));
85 KTR_INFO(KTR_CTXSW, ctxsw, deadtd, 3, "#threads[%p].name = <dead>", sizeof (struct thread *));
86
87 static MALLOC_DEFINE(M_THREAD, "thread", "lwkt threads");
88
89 #ifdef  INVARIANTS
90 static int panic_on_cscount = 0;
91 #endif
92 static __int64_t switch_count = 0;
93 static __int64_t preempt_hit = 0;
94 static __int64_t preempt_miss = 0;
95 static __int64_t preempt_weird = 0;
96 static __int64_t token_contention_count __debugvar = 0;
97 static int lwkt_use_spin_port;
98 static struct objcache *thread_cache;
99
100 #ifdef SMP
101 static void lwkt_schedule_remote(void *arg, int arg2, struct intrframe *frame);
102 #endif
103 static void lwkt_fairq_accumulate(globaldata_t gd, thread_t td);
104
105 extern void cpu_heavy_restore(void);
106 extern void cpu_lwkt_restore(void);
107 extern void cpu_kthread_restore(void);
108 extern void cpu_idle_restore(void);
109
110 #ifdef __x86_64__
111
112 static int
113 jg_tos_ok(struct thread *td)
114 {
115         void *tos;
116         int tos_ok;
117
118         if (td == NULL) {
119                 return 1;
120         }
121         KKASSERT(td->td_sp != NULL);
122         tos = ((void **)td->td_sp)[0];
123         tos_ok = 0;
124         if ((tos == cpu_heavy_restore) || (tos == cpu_lwkt_restore) ||
125             (tos == cpu_kthread_restore) || (tos == cpu_idle_restore)) {
126                 tos_ok = 1;
127         }
128         return tos_ok;
129 }
130
131 #endif
132
133 /*
134  * We can make all thread ports use the spin backend instead of the thread
135  * backend.  This should only be set to debug the spin backend.
136  */
137 TUNABLE_INT("lwkt.use_spin_port", &lwkt_use_spin_port);
138
139 #ifdef  INVARIANTS
140 SYSCTL_INT(_lwkt, OID_AUTO, panic_on_cscount, CTLFLAG_RW, &panic_on_cscount, 0, "");
141 #endif
142 SYSCTL_QUAD(_lwkt, OID_AUTO, switch_count, CTLFLAG_RW, &switch_count, 0, "");
143 SYSCTL_QUAD(_lwkt, OID_AUTO, preempt_hit, CTLFLAG_RW, &preempt_hit, 0, 
144             "Successful preemption events");
145 SYSCTL_QUAD(_lwkt, OID_AUTO, preempt_miss, CTLFLAG_RW, &preempt_miss, 0, 
146             "Failed preemption events");
147 SYSCTL_QUAD(_lwkt, OID_AUTO, preempt_weird, CTLFLAG_RW, &preempt_weird, 0, "");
148 #ifdef  INVARIANTS
149 SYSCTL_QUAD(_lwkt, OID_AUTO, token_contention_count, CTLFLAG_RW,
150         &token_contention_count, 0, "spinning due to token contention");
151 #endif
152 static int fairq_enable = 1;
153 SYSCTL_INT(_lwkt, OID_AUTO, fairq_enable, CTLFLAG_RW, &fairq_enable, 0, "");
154 static int user_pri_sched = 0;
155 SYSCTL_INT(_lwkt, OID_AUTO, user_pri_sched, CTLFLAG_RW, &user_pri_sched, 0, "");
156 static int preempt_enable = 1;
157 SYSCTL_INT(_lwkt, OID_AUTO, preempt_enable, CTLFLAG_RW, &preempt_enable, 0, "");
158
159
160 /*
161  * These helper procedures handle the runq, they can only be called from
162  * within a critical section.
163  *
164  * WARNING!  Prior to SMP being brought up it is possible to enqueue and
165  * dequeue threads belonging to other cpus, so be sure to use td->td_gd
166  * instead of 'mycpu' when referencing the globaldata structure.   Once
167  * SMP live enqueuing and dequeueing only occurs on the current cpu.
168  */
169 static __inline
170 void
171 _lwkt_dequeue(thread_t td)
172 {
173     if (td->td_flags & TDF_RUNQ) {
174         struct globaldata *gd = td->td_gd;
175
176         td->td_flags &= ~TDF_RUNQ;
177         TAILQ_REMOVE(&gd->gd_tdrunq, td, td_threadq);
178         gd->gd_fairq_total_pri -= td->td_pri;
179         if (TAILQ_FIRST(&gd->gd_tdrunq) == NULL)
180                 atomic_clear_int_nonlocked(&gd->gd_reqflags, RQF_RUNNING);
181     }
182 }
183
184 /*
185  * Priority enqueue.
186  *
187  * NOTE: There are a limited number of lwkt threads runnable since user
188  *       processes only schedule one at a time per cpu.
189  */
190 static __inline
191 void
192 _lwkt_enqueue(thread_t td)
193 {
194     thread_t xtd;
195
196     if ((td->td_flags & (TDF_RUNQ|TDF_MIGRATING|TDF_BLOCKQ)) == 0) {
197         struct globaldata *gd = td->td_gd;
198
199         td->td_flags |= TDF_RUNQ;
200         xtd = TAILQ_FIRST(&gd->gd_tdrunq);
201         if (xtd == NULL) {
202                 TAILQ_INSERT_TAIL(&gd->gd_tdrunq, td, td_threadq);
203                 atomic_set_int_nonlocked(&gd->gd_reqflags, RQF_RUNNING);
204         } else {
205                 while (xtd && xtd->td_pri > td->td_pri)
206                         xtd = TAILQ_NEXT(xtd, td_threadq);
207                 if (xtd)
208                         TAILQ_INSERT_BEFORE(xtd, td, td_threadq);
209                 else
210                         TAILQ_INSERT_TAIL(&gd->gd_tdrunq, td, td_threadq);
211         }
212         gd->gd_fairq_total_pri += td->td_pri;
213     }
214 }
215
216 static __boolean_t
217 _lwkt_thread_ctor(void *obj, void *privdata, int ocflags)
218 {
219         struct thread *td = (struct thread *)obj;
220
221         td->td_kstack = NULL;
222         td->td_kstack_size = 0;
223         td->td_flags = TDF_ALLOCATED_THREAD;
224         return (1);
225 }
226
227 static void
228 _lwkt_thread_dtor(void *obj, void *privdata)
229 {
230         struct thread *td = (struct thread *)obj;
231
232         KASSERT(td->td_flags & TDF_ALLOCATED_THREAD,
233             ("_lwkt_thread_dtor: not allocated from objcache"));
234         KASSERT((td->td_flags & TDF_ALLOCATED_STACK) && td->td_kstack &&
235                 td->td_kstack_size > 0,
236             ("_lwkt_thread_dtor: corrupted stack"));
237         kmem_free(&kernel_map, (vm_offset_t)td->td_kstack, td->td_kstack_size);
238 }
239
240 /*
241  * Initialize the lwkt s/system.
242  */
243 void
244 lwkt_init(void)
245 {
246     /* An objcache has 2 magazines per CPU so divide cache size by 2. */
247     thread_cache = objcache_create_mbacked(M_THREAD, sizeof(struct thread),
248                         NULL, CACHE_NTHREADS/2,
249                         _lwkt_thread_ctor, _lwkt_thread_dtor, NULL);
250 }
251
252 /*
253  * Schedule a thread to run.  As the current thread we can always safely
254  * schedule ourselves, and a shortcut procedure is provided for that
255  * function.
256  *
257  * (non-blocking, self contained on a per cpu basis)
258  */
259 void
260 lwkt_schedule_self(thread_t td)
261 {
262     crit_enter_quick(td);
263     KASSERT(td != &td->td_gd->gd_idlethread,
264             ("lwkt_schedule_self(): scheduling gd_idlethread is illegal!"));
265     KKASSERT(td->td_lwp == NULL || (td->td_lwp->lwp_flag & LWP_ONRUNQ) == 0);
266     _lwkt_enqueue(td);
267     crit_exit_quick(td);
268 }
269
270 /*
271  * Deschedule a thread.
272  *
273  * (non-blocking, self contained on a per cpu basis)
274  */
275 void
276 lwkt_deschedule_self(thread_t td)
277 {
278     crit_enter_quick(td);
279     _lwkt_dequeue(td);
280     crit_exit_quick(td);
281 }
282
283 /*
284  * LWKTs operate on a per-cpu basis
285  *
286  * WARNING!  Called from early boot, 'mycpu' may not work yet.
287  */
288 void
289 lwkt_gdinit(struct globaldata *gd)
290 {
291     TAILQ_INIT(&gd->gd_tdrunq);
292     TAILQ_INIT(&gd->gd_tdallq);
293 }
294
295 /*
296  * Create a new thread.  The thread must be associated with a process context
297  * or LWKT start address before it can be scheduled.  If the target cpu is
298  * -1 the thread will be created on the current cpu.
299  *
300  * If you intend to create a thread without a process context this function
301  * does everything except load the startup and switcher function.
302  */
303 thread_t
304 lwkt_alloc_thread(struct thread *td, int stksize, int cpu, int flags)
305 {
306     globaldata_t gd = mycpu;
307     void *stack;
308
309     /*
310      * If static thread storage is not supplied allocate a thread.  Reuse
311      * a cached free thread if possible.  gd_freetd is used to keep an exiting
312      * thread intact through the exit.
313      */
314     if (td == NULL) {
315         if ((td = gd->gd_freetd) != NULL)
316             gd->gd_freetd = NULL;
317         else
318             td = objcache_get(thread_cache, M_WAITOK);
319         KASSERT((td->td_flags &
320                  (TDF_ALLOCATED_THREAD|TDF_RUNNING)) == TDF_ALLOCATED_THREAD,
321                 ("lwkt_alloc_thread: corrupted td flags 0x%X", td->td_flags));
322         flags |= td->td_flags & (TDF_ALLOCATED_THREAD|TDF_ALLOCATED_STACK);
323     }
324
325     /*
326      * Try to reuse cached stack.
327      */
328     if ((stack = td->td_kstack) != NULL && td->td_kstack_size != stksize) {
329         if (flags & TDF_ALLOCATED_STACK) {
330             kmem_free(&kernel_map, (vm_offset_t)stack, td->td_kstack_size);
331             stack = NULL;
332         }
333     }
334     if (stack == NULL) {
335         stack = (void *)kmem_alloc(&kernel_map, stksize);
336         flags |= TDF_ALLOCATED_STACK;
337     }
338     if (cpu < 0)
339         lwkt_init_thread(td, stack, stksize, flags, gd);
340     else
341         lwkt_init_thread(td, stack, stksize, flags, globaldata_find(cpu));
342     return(td);
343 }
344
345 /*
346  * Initialize a preexisting thread structure.  This function is used by
347  * lwkt_alloc_thread() and also used to initialize the per-cpu idlethread.
348  *
349  * All threads start out in a critical section at a priority of
350  * TDPRI_KERN_DAEMON.  Higher level code will modify the priority as
351  * appropriate.  This function may send an IPI message when the 
352  * requested cpu is not the current cpu and consequently gd_tdallq may
353  * not be initialized synchronously from the point of view of the originating
354  * cpu.
355  *
356  * NOTE! we have to be careful in regards to creating threads for other cpus
357  * if SMP has not yet been activated.
358  */
359 #ifdef SMP
360
361 static void
362 lwkt_init_thread_remote(void *arg)
363 {
364     thread_t td = arg;
365
366     /*
367      * Protected by critical section held by IPI dispatch
368      */
369     TAILQ_INSERT_TAIL(&td->td_gd->gd_tdallq, td, td_allq);
370 }
371
372 #endif
373
374 /*
375  * lwkt core thread structural initialization.
376  *
377  * NOTE: All threads are initialized as mpsafe threads.
378  */
379 void
380 lwkt_init_thread(thread_t td, void *stack, int stksize, int flags,
381                 struct globaldata *gd)
382 {
383     globaldata_t mygd = mycpu;
384
385     bzero(td, sizeof(struct thread));
386     td->td_kstack = stack;
387     td->td_kstack_size = stksize;
388     td->td_flags = flags;
389     td->td_gd = gd;
390     td->td_pri = TDPRI_KERN_DAEMON;
391     td->td_critcount = 1;
392     td->td_toks_stop = &td->td_toks_base;
393     if (lwkt_use_spin_port)
394         lwkt_initport_spin(&td->td_msgport);
395     else
396         lwkt_initport_thread(&td->td_msgport, td);
397     pmap_init_thread(td);
398 #ifdef SMP
399     /*
400      * Normally initializing a thread for a remote cpu requires sending an
401      * IPI.  However, the idlethread is setup before the other cpus are
402      * activated so we have to treat it as a special case.  XXX manipulation
403      * of gd_tdallq requires the BGL.
404      */
405     if (gd == mygd || td == &gd->gd_idlethread) {
406         crit_enter_gd(mygd);
407         TAILQ_INSERT_TAIL(&gd->gd_tdallq, td, td_allq);
408         crit_exit_gd(mygd);
409     } else {
410         lwkt_send_ipiq(gd, lwkt_init_thread_remote, td);
411     }
412 #else
413     crit_enter_gd(mygd);
414     TAILQ_INSERT_TAIL(&gd->gd_tdallq, td, td_allq);
415     crit_exit_gd(mygd);
416 #endif
417
418     dsched_new_thread(td);
419 }
420
421 void
422 lwkt_set_comm(thread_t td, const char *ctl, ...)
423 {
424     __va_list va;
425
426     __va_start(va, ctl);
427     kvsnprintf(td->td_comm, sizeof(td->td_comm), ctl, va);
428     __va_end(va);
429     KTR_LOG(ctxsw_newtd, td, &td->td_comm[0]);
430 }
431
432 void
433 lwkt_hold(thread_t td)
434 {
435     ++td->td_refs;
436 }
437
438 void
439 lwkt_rele(thread_t td)
440 {
441     KKASSERT(td->td_refs > 0);
442     --td->td_refs;
443 }
444
445 void
446 lwkt_wait_free(thread_t td)
447 {
448     while (td->td_refs)
449         tsleep(td, 0, "tdreap", hz);
450 }
451
452 void
453 lwkt_free_thread(thread_t td)
454 {
455     KASSERT((td->td_flags & TDF_RUNNING) == 0,
456         ("lwkt_free_thread: did not exit! %p", td));
457
458     if (td->td_flags & TDF_ALLOCATED_THREAD) {
459         objcache_put(thread_cache, td);
460     } else if (td->td_flags & TDF_ALLOCATED_STACK) {
461         /* client-allocated struct with internally allocated stack */
462         KASSERT(td->td_kstack && td->td_kstack_size > 0,
463             ("lwkt_free_thread: corrupted stack"));
464         kmem_free(&kernel_map, (vm_offset_t)td->td_kstack, td->td_kstack_size);
465         td->td_kstack = NULL;
466         td->td_kstack_size = 0;
467     }
468     KTR_LOG(ctxsw_deadtd, td);
469 }
470
471
472 /*
473  * Switch to the next runnable lwkt.  If no LWKTs are runnable then 
474  * switch to the idlethread.  Switching must occur within a critical
475  * section to avoid races with the scheduling queue.
476  *
477  * We always have full control over our cpu's run queue.  Other cpus
478  * that wish to manipulate our queue must use the cpu_*msg() calls to
479  * talk to our cpu, so a critical section is all that is needed and
480  * the result is very, very fast thread switching.
481  *
482  * The LWKT scheduler uses a fixed priority model and round-robins at
483  * each priority level.  User process scheduling is a totally
484  * different beast and LWKT priorities should not be confused with
485  * user process priorities.
486  *
487  * The MP lock may be out of sync with the thread's td_mpcount + td_xpcount.
488  * lwkt_switch() cleans it up.
489  *
490  * Note that the td_switch() function cannot do anything that requires
491  * the MP lock since the MP lock will have already been setup for
492  * the target thread (not the current thread).  It's nice to have a scheduler
493  * that does not need the MP lock to work because it allows us to do some
494  * really cool high-performance MP lock optimizations.
495  *
496  * PREEMPTION NOTE: Preemption occurs via lwkt_preempt().  lwkt_switch()
497  * is not called by the current thread in the preemption case, only when
498  * the preempting thread blocks (in order to return to the original thread).
499  */
500 void
501 lwkt_switch(void)
502 {
503     globaldata_t gd = mycpu;
504     thread_t td = gd->gd_curthread;
505     thread_t ntd;
506     thread_t xtd;
507     thread_t nlast;
508     int nquserok;
509 #ifdef SMP
510     int mpheld;
511 #endif
512     int didaccumulate;
513     const char *lmsg;   /* diagnostic - 'systat -pv 1' */
514     const void *laddr;
515
516     /*
517      * Switching from within a 'fast' (non thread switched) interrupt or IPI
518      * is illegal.  However, we may have to do it anyway if we hit a fatal
519      * kernel trap or we have paniced.
520      *
521      * If this case occurs save and restore the interrupt nesting level.
522      */
523     if (gd->gd_intr_nesting_level) {
524         int savegdnest;
525         int savegdtrap;
526
527         if (gd->gd_trap_nesting_level == 0 && panic_cpu_gd != mycpu) {
528             panic("lwkt_switch: Attempt to switch from a "
529                   "a fast interrupt, ipi, or hard code section, "
530                   "td %p\n",
531                   td);
532         } else {
533             savegdnest = gd->gd_intr_nesting_level;
534             savegdtrap = gd->gd_trap_nesting_level;
535             gd->gd_intr_nesting_level = 0;
536             gd->gd_trap_nesting_level = 0;
537             if ((td->td_flags & TDF_PANICWARN) == 0) {
538                 td->td_flags |= TDF_PANICWARN;
539                 kprintf("Warning: thread switch from interrupt, IPI, "
540                         "or hard code section.\n"
541                         "thread %p (%s)\n", td, td->td_comm);
542                 print_backtrace(-1);
543             }
544             lwkt_switch();
545             gd->gd_intr_nesting_level = savegdnest;
546             gd->gd_trap_nesting_level = savegdtrap;
547             return;
548         }
549     }
550
551     /*
552      * Passive release (used to transition from user to kernel mode
553      * when we block or switch rather then when we enter the kernel).
554      * This function is NOT called if we are switching into a preemption
555      * or returning from a preemption.  Typically this causes us to lose
556      * our current process designation (if we have one) and become a true
557      * LWKT thread, and may also hand the current process designation to
558      * another process and schedule thread.
559      */
560     if (td->td_release)
561             td->td_release(td);
562
563     crit_enter_gd(gd);
564     if (TD_TOKS_HELD(td))
565             lwkt_relalltokens(td);
566
567     /*
568      * We had better not be holding any spin locks, but don't get into an
569      * endless panic loop.
570      */
571     KASSERT(gd->gd_spinlocks_wr == 0 || panicstr != NULL, 
572             ("lwkt_switch: still holding %d exclusive spinlocks!",
573              gd->gd_spinlocks_wr));
574
575
576 #ifdef SMP
577     /*
578      * td_mpcount + td_xpcount cannot be used to determine if we currently
579      * hold the MP lock because get_mplock() will increment it prior to
580      * attempting to get the lock, and switch out if it can't.  Our
581      * ownership of the actual lock will remain stable while we are
582      * in a critical section, and once we actually acquire the underlying
583      * lock as long as the count is greater than 0.
584      */
585     mpheld = MP_LOCK_HELD(gd);
586 #ifdef  INVARIANTS
587     if (td->td_cscount) {
588         kprintf("Diagnostic: attempt to switch while mastering cpusync: %p\n",
589                 td);
590         if (panic_on_cscount)
591             panic("switching while mastering cpusync");
592     }
593 #endif
594 #endif
595
596     /*
597      * If we had preempted another thread on this cpu, resume the preempted
598      * thread.  This occurs transparently, whether the preempted thread
599      * was scheduled or not (it may have been preempted after descheduling
600      * itself).
601      *
602      * We have to setup the MP lock for the original thread after backing
603      * out the adjustment that was made to curthread when the original
604      * was preempted.
605      */
606     if ((ntd = td->td_preempted) != NULL) {
607         KKASSERT(ntd->td_flags & TDF_PREEMPT_LOCK);
608 #ifdef SMP
609         if (ntd->td_mpcount + ntd->td_xpcount && mpheld == 0) {
610             panic("MPLOCK NOT HELD ON RETURN: %p %p %d %d",
611                td, ntd, td->td_mpcount, ntd->td_mpcount + ntd->td_xpcount);
612         }
613         td->td_xpcount = 0;
614 #endif
615         ntd->td_flags |= TDF_PREEMPT_DONE;
616
617         /*
618          * The interrupt may have woken a thread up, we need to properly
619          * set the reschedule flag if the originally interrupted thread is
620          * at a lower priority.
621          */
622         if (TAILQ_FIRST(&gd->gd_tdrunq) &&
623             TAILQ_FIRST(&gd->gd_tdrunq)->td_pri > ntd->td_pri) {
624             need_lwkt_resched();
625         }
626         /* YYY release mp lock on switchback if original doesn't need it */
627         goto havethread_preempted;
628     }
629
630     /*
631      * Implement round-robin fairq with priority insertion.  The priority
632      * insertion is handled by _lwkt_enqueue()
633      *
634      * We have to adjust the MP lock for the target thread.  If we
635      * need the MP lock and cannot obtain it we try to locate a
636      * thread that does not need the MP lock.  If we cannot, we spin
637      * instead of HLT.
638      *
639      * A similar issue exists for the tokens held by the target thread.
640      * If we cannot obtain ownership of the tokens we cannot immediately
641      * schedule the thread.
642      */
643     for (;;) {
644         clear_lwkt_resched();
645         didaccumulate = 0;
646         ntd = TAILQ_FIRST(&gd->gd_tdrunq);
647
648         /*
649          * Hotpath if we can get all necessary resources.
650          *
651          * If nothing is runnable switch to the idle thread
652          */
653         if (ntd == NULL) {
654             ntd = &gd->gd_idlethread;
655             if (gd->gd_reqflags & RQF_IDLECHECK_MASK)
656                     ntd->td_flags |= TDF_IDLE_NOHLT;
657 #ifdef SMP
658             KKASSERT(ntd->td_xpcount == 0);
659             if (ntd->td_mpcount) {
660                 if (gd->gd_trap_nesting_level == 0 && panicstr == NULL)
661                     panic("Idle thread %p was holding the BGL!", ntd);
662                 if (mpheld == 0) {
663                     set_cpu_contention_mask(gd);
664                     handle_cpu_contention_mask();
665                     cpu_try_mplock();
666                     mpheld = MP_LOCK_HELD(gd);
667                     cpu_pause();
668                     continue;
669                 }
670             }
671             clr_cpu_contention_mask(gd);
672 #endif
673             cpu_time.cp_msg[0] = 0;
674             cpu_time.cp_stallpc = 0;
675             goto haveidle;
676         }
677
678         /*
679          * Hotpath schedule
680          *
681          * NOTE: For UP there is no mplock and lwkt_getalltokens()
682          *           always succeeds.
683          */
684         if (ntd->td_fairq_accum >= 0 &&
685 #ifdef SMP
686             (ntd->td_mpcount + ntd->td_xpcount == 0 ||
687              mpheld || cpu_try_mplock()) &&
688 #endif
689             (!TD_TOKS_HELD(ntd) || lwkt_getalltokens(ntd, &lmsg, &laddr))
690         ) {
691 #ifdef SMP
692             clr_cpu_contention_mask(gd);
693 #endif
694             goto havethread;
695         }
696
697         lmsg = NULL;
698         laddr = NULL;
699
700 #ifdef SMP
701         if (ntd->td_fairq_accum >= 0)
702                 set_cpu_contention_mask(gd);
703         /* Reload mpheld (it become stale after mplock/token ops) */
704         mpheld = MP_LOCK_HELD(gd);
705         if (ntd->td_mpcount + ntd->td_xpcount && mpheld == 0) {
706             lmsg = "mplock";
707             laddr = ntd->td_mplock_stallpc;
708         }
709 #endif
710
711         /*
712          * Coldpath - unable to schedule ntd, continue looking for threads
713          * to schedule.  This is only allowed of the (presumably) kernel
714          * thread exhausted its fair share.  A kernel thread stuck on
715          * resources does not currently allow a user thread to get in
716          * front of it.
717          */
718 #ifdef SMP
719         nquserok = ((ntd->td_pri < TDPRI_KERN_LPSCHED) ||
720                     (ntd->td_fairq_accum < 0));
721 #else
722         nquserok = 1;
723 #endif
724         nlast = NULL;
725
726         for (;;) {
727             /*
728              * If the fair-share scheduler ran out ntd gets moved to the
729              * end and its accumulator will be bumped, if it didn't we
730              * maintain the same queue position.
731              *
732              * nlast keeps track of the last element prior to any moves.
733              */
734             if (ntd->td_fairq_accum < 0) {
735                 lwkt_fairq_accumulate(gd, ntd);
736                 didaccumulate = 1;
737
738                 /*
739                  * Move to end
740                  */
741                 xtd = TAILQ_NEXT(ntd, td_threadq);
742                 TAILQ_REMOVE(&gd->gd_tdrunq, ntd, td_threadq);
743                 TAILQ_INSERT_TAIL(&gd->gd_tdrunq, ntd, td_threadq);
744
745                 /*
746                  * Set terminal element (nlast)
747                  */
748                 if (nlast == NULL) {
749                     nlast = ntd;
750                     if (xtd == NULL)
751                         xtd = ntd;
752                 }
753                 ntd = xtd;
754             } else {
755                 ntd = TAILQ_NEXT(ntd, td_threadq);
756             }
757
758             /*
759              * If we exhausted the run list switch to the idle thread.
760              * Since one or more threads had resource acquisition issues
761              * we do not allow the idle thread to halt.
762              *
763              * NOTE: nlast can be NULL.
764              */
765             if (ntd == nlast) {
766                 cpu_pause();
767                 ntd = &gd->gd_idlethread;
768                 ntd->td_flags |= TDF_IDLE_NOHLT;
769 #ifdef SMP
770                 KKASSERT(ntd->td_xpcount == 0);
771                 if (ntd->td_mpcount) {
772                     mpheld = MP_LOCK_HELD(gd);
773                     if (gd->gd_trap_nesting_level == 0 && panicstr == NULL)
774                         panic("Idle thread %p was holding the BGL!", ntd);
775                     if (mpheld == 0) {
776                         set_cpu_contention_mask(gd);
777                         handle_cpu_contention_mask();
778                         cpu_try_mplock();
779                         mpheld = MP_LOCK_HELD(gd);
780                         cpu_pause();
781                         break;          /* try again from the top, almost */
782                     }
783                 }
784 #endif
785
786                 /*
787                  * If fairq accumulations occured we do not schedule the
788                  * idle thread.  This will cause us to try again from
789                  * the (almost) top.
790                  */
791                 if (didaccumulate)
792                         break;          /* try again from the top, almost */
793                 if (lmsg)
794                     strlcpy(cpu_time.cp_msg, lmsg, sizeof(cpu_time.cp_msg));
795                 cpu_time.cp_stallpc = (uintptr_t)laddr;
796                 goto haveidle;
797             }
798
799             /*
800              * Try to switch to this thread.
801              *
802              * NOTE: For UP there is no mplock and lwkt_getalltokens()
803              *       always succeeds.
804              */
805             if ((ntd->td_pri >= TDPRI_KERN_LPSCHED || nquserok ||
806                 user_pri_sched) && ntd->td_fairq_accum >= 0 &&
807 #ifdef SMP
808                 (ntd->td_mpcount + ntd->td_xpcount == 0 ||
809                  mpheld || cpu_try_mplock()) &&
810 #endif
811                 (!TD_TOKS_HELD(ntd) || lwkt_getalltokens(ntd, &lmsg, &laddr))
812             ) {
813 #ifdef SMP
814                     clr_cpu_contention_mask(gd);
815 #endif
816                     goto havethread;
817             }
818 #ifdef SMP
819             if (ntd->td_fairq_accum >= 0)
820                     set_cpu_contention_mask(gd);
821             /*
822              * Reload mpheld (it become stale after mplock/token ops).
823              */
824             mpheld = MP_LOCK_HELD(gd);
825             if (ntd->td_mpcount + ntd->td_xpcount && mpheld == 0) {
826                 lmsg = "mplock";
827                 laddr = ntd->td_mplock_stallpc;
828             }
829             if (ntd->td_pri >= TDPRI_KERN_LPSCHED && ntd->td_fairq_accum >= 0)
830                 nquserok = 0;
831 #endif
832         }
833
834         /*
835          * All threads exhausted but we can loop due to a negative
836          * accumulator.
837          *
838          * While we are looping in the scheduler be sure to service
839          * any interrupts which were made pending due to our critical
840          * section, otherwise we could livelock (e.g.) IPIs.
841          *
842          * NOTE: splz can enter and exit the mplock so mpheld is
843          * stale after this call.
844          */
845         splz_check();
846
847 #ifdef SMP
848         /*
849          * Our mplock can be cached and cause other cpus to livelock
850          * if we loop due to e.g. not being able to acquire tokens.
851          */
852         if (MP_LOCK_HELD(gd))
853             cpu_rel_mplock(gd->gd_cpuid);
854         mpheld = 0;
855 #endif
856     }
857
858     /*
859      * Do the actual switch.  WARNING: mpheld is stale here.
860      *
861      * We must always decrement td_fairq_accum on non-idle threads just
862      * in case a thread never gets a tick due to being in a continuous
863      * critical section.  The page-zeroing code does that.
864      *
865      * If the thread we came up with is a higher or equal priority verses
866      * the thread at the head of the queue we move our thread to the
867      * front.  This way we can always check the front of the queue.
868      */
869 havethread:
870     ++gd->gd_cnt.v_swtch;
871     --ntd->td_fairq_accum;
872     xtd = TAILQ_FIRST(&gd->gd_tdrunq);
873     if (ntd != xtd && ntd->td_pri >= xtd->td_pri) {
874         TAILQ_REMOVE(&gd->gd_tdrunq, ntd, td_threadq);
875         TAILQ_INSERT_HEAD(&gd->gd_tdrunq, ntd, td_threadq);
876     }
877 havethread_preempted:
878     ;
879     /*
880      * If the new target does not need the MP lock and we are holding it,
881      * release the MP lock.  If the new target requires the MP lock we have
882      * already acquired it for the target.
883      *
884      * WARNING: mpheld is stale here.
885      */
886 haveidle:
887     KASSERT(ntd->td_critcount,
888             ("priority problem in lwkt_switch %d %d", td->td_pri, ntd->td_pri));
889 #ifdef SMP
890     if (ntd->td_mpcount + ntd->td_xpcount == 0 ) {
891         if (MP_LOCK_HELD(gd))
892             cpu_rel_mplock(gd->gd_cpuid);
893     } else {
894         ASSERT_MP_LOCK_HELD(ntd);
895     }
896 #endif
897     if (td != ntd) {
898         ++switch_count;
899 #ifdef __x86_64__
900         {
901             int tos_ok __debugvar = jg_tos_ok(ntd);
902             KKASSERT(tos_ok);
903         }
904 #endif
905         KTR_LOG(ctxsw_sw, gd->gd_cpuid, ntd);
906         td->td_switch(ntd);
907     }
908     /* NOTE: current cpu may have changed after switch */
909     crit_exit_quick(td);
910 }
911
912 /*
913  * Request that the target thread preempt the current thread.  Preemption
914  * only works under a specific set of conditions:
915  *
916  *      - We are not preempting ourselves
917  *      - The target thread is owned by the current cpu
918  *      - We are not currently being preempted
919  *      - The target is not currently being preempted
920  *      - We are not holding any spin locks
921  *      - The target thread is not holding any tokens
922  *      - We are able to satisfy the target's MP lock requirements (if any).
923  *
924  * THE CALLER OF LWKT_PREEMPT() MUST BE IN A CRITICAL SECTION.  Typically
925  * this is called via lwkt_schedule() through the td_preemptable callback.
926  * critcount is the managed critical priority that we should ignore in order
927  * to determine whether preemption is possible (aka usually just the crit
928  * priority of lwkt_schedule() itself).
929  *
930  * XXX at the moment we run the target thread in a critical section during
931  * the preemption in order to prevent the target from taking interrupts
932  * that *WE* can't.  Preemption is strictly limited to interrupt threads
933  * and interrupt-like threads, outside of a critical section, and the
934  * preempted source thread will be resumed the instant the target blocks
935  * whether or not the source is scheduled (i.e. preemption is supposed to
936  * be as transparent as possible).
937  *
938  * The target thread inherits our MP count (added to its own) for the
939  * duration of the preemption in order to preserve the atomicy of the
940  * MP lock during the preemption.  Therefore, any preempting targets must be
941  * careful in regards to MP assertions.  Note that the MP count may be
942  * out of sync with the physical mp_lock, but we do not have to preserve
943  * the original ownership of the lock if it was out of synch (that is, we
944  * can leave it synchronized on return).
945  */
946 void
947 lwkt_preempt(thread_t ntd, int critcount)
948 {
949     struct globaldata *gd = mycpu;
950     thread_t td;
951 #ifdef SMP
952     int mpheld;
953     int savecnt;
954 #endif
955
956     /*
957      * The caller has put us in a critical section.  We can only preempt
958      * if the caller of the caller was not in a critical section (basically
959      * a local interrupt), as determined by the 'critcount' parameter.  We
960      * also can't preempt if the caller is holding any spinlocks (even if
961      * he isn't in a critical section).  This also handles the tokens test.
962      *
963      * YYY The target thread must be in a critical section (else it must
964      * inherit our critical section?  I dunno yet).
965      *
966      * Set need_lwkt_resched() unconditionally for now YYY.
967      */
968     KASSERT(ntd->td_critcount, ("BADCRIT0 %d", ntd->td_pri));
969
970     if (preempt_enable == 0) {
971         ++preempt_miss;
972         return;
973     }
974
975     td = gd->gd_curthread;
976     if (ntd->td_pri <= td->td_pri) {
977         ++preempt_miss;
978         return;
979     }
980     if (td->td_critcount > critcount) {
981         ++preempt_miss;
982         need_lwkt_resched();
983         return;
984     }
985 #ifdef SMP
986     if (ntd->td_gd != gd) {
987         ++preempt_miss;
988         need_lwkt_resched();
989         return;
990     }
991 #endif
992     /*
993      * We don't have to check spinlocks here as they will also bump
994      * td_critcount.
995      *
996      * Do not try to preempt if the target thread is holding any tokens.
997      * We could try to acquire the tokens but this case is so rare there
998      * is no need to support it.
999      */
1000     KKASSERT(gd->gd_spinlocks_wr == 0);
1001
1002     if (TD_TOKS_HELD(ntd)) {
1003         ++preempt_miss;
1004         need_lwkt_resched();
1005         return;
1006     }
1007     if (td == ntd || ((td->td_flags | ntd->td_flags) & TDF_PREEMPT_LOCK)) {
1008         ++preempt_weird;
1009         need_lwkt_resched();
1010         return;
1011     }
1012     if (ntd->td_preempted) {
1013         ++preempt_hit;
1014         need_lwkt_resched();
1015         return;
1016     }
1017 #ifdef SMP
1018     /*
1019      * NOTE: An interrupt might have occured just as we were transitioning
1020      * to or from the MP lock.  In this case td_mpcount will be pre-disposed
1021      * (non-zero) but not actually synchronized with the mp_lock itself.
1022      * We can use it to imply an MP lock requirement for the preemption but
1023      * we cannot use it to test whether we hold the MP lock or not.
1024      */
1025     savecnt = td->td_mpcount;
1026     mpheld = MP_LOCK_HELD(gd);
1027     ntd->td_xpcount = td->td_mpcount + td->td_xpcount;
1028     if (mpheld == 0 && ntd->td_mpcount + ntd->td_xpcount && !cpu_try_mplock()) {
1029         ntd->td_xpcount = 0;
1030         ++preempt_miss;
1031         need_lwkt_resched();
1032         return;
1033     }
1034 #endif
1035
1036     /*
1037      * Since we are able to preempt the current thread, there is no need to
1038      * call need_lwkt_resched().
1039      */
1040     ++preempt_hit;
1041     ntd->td_preempted = td;
1042     td->td_flags |= TDF_PREEMPT_LOCK;
1043     KTR_LOG(ctxsw_pre, gd->gd_cpuid, ntd);
1044     td->td_switch(ntd);
1045
1046     KKASSERT(ntd->td_preempted && (td->td_flags & TDF_PREEMPT_DONE));
1047 #ifdef SMP
1048     KKASSERT(savecnt == td->td_mpcount);
1049     mpheld = MP_LOCK_HELD(gd);
1050     if (mpheld && td->td_mpcount == 0)
1051         cpu_rel_mplock(gd->gd_cpuid);
1052     else if (mpheld == 0 && td->td_mpcount + td->td_xpcount)
1053         panic("lwkt_preempt(): MP lock was not held through");
1054 #endif
1055     ntd->td_preempted = NULL;
1056     td->td_flags &= ~(TDF_PREEMPT_LOCK|TDF_PREEMPT_DONE);
1057 }
1058
1059 /*
1060  * Conditionally call splz() if gd_reqflags indicates work is pending.
1061  * This will work inside a critical section but not inside a hard code
1062  * section.
1063  *
1064  * (self contained on a per cpu basis)
1065  */
1066 void
1067 splz_check(void)
1068 {
1069     globaldata_t gd = mycpu;
1070     thread_t td = gd->gd_curthread;
1071
1072     if ((gd->gd_reqflags & RQF_IDLECHECK_MASK) &&
1073         gd->gd_intr_nesting_level == 0 &&
1074         td->td_nest_count < 2)
1075     {
1076         splz();
1077     }
1078 }
1079
1080 /*
1081  * This version is integrated into crit_exit, reqflags has already
1082  * been tested but td_critcount has not.
1083  *
1084  * We only want to execute the splz() on the 1->0 transition of
1085  * critcount and not in a hard code section or if too deeply nested.
1086  */
1087 void
1088 lwkt_maybe_splz(thread_t td)
1089 {
1090     globaldata_t gd = td->td_gd;
1091
1092     if (td->td_critcount == 0 &&
1093         gd->gd_intr_nesting_level == 0 &&
1094         td->td_nest_count < 2)
1095     {
1096         splz();
1097     }
1098 }
1099
1100 /*
1101  * This function is used to negotiate a passive release of the current
1102  * process/lwp designation with the user scheduler, allowing the user
1103  * scheduler to schedule another user thread.  The related kernel thread
1104  * (curthread) continues running in the released state.
1105  */
1106 void
1107 lwkt_passive_release(struct thread *td)
1108 {
1109     struct lwp *lp = td->td_lwp;
1110
1111     td->td_release = NULL;
1112     lwkt_setpri_self(TDPRI_KERN_USER);
1113     lp->lwp_proc->p_usched->release_curproc(lp);
1114 }
1115
1116
1117 /*
1118  * This implements a normal yield.  This routine is virtually a nop if
1119  * there is nothing to yield to but it will always run any pending interrupts
1120  * if called from a critical section.
1121  *
1122  * This yield is designed for kernel threads without a user context.
1123  *
1124  * (self contained on a per cpu basis)
1125  */
1126 void
1127 lwkt_yield(void)
1128 {
1129     globaldata_t gd = mycpu;
1130     thread_t td = gd->gd_curthread;
1131     thread_t xtd;
1132
1133     if ((gd->gd_reqflags & RQF_IDLECHECK_MASK) && td->td_nest_count < 2)
1134         splz();
1135     if (td->td_fairq_accum < 0) {
1136         lwkt_schedule_self(curthread);
1137         lwkt_switch();
1138     } else {
1139         xtd = TAILQ_FIRST(&gd->gd_tdrunq);
1140         if (xtd && xtd->td_pri > td->td_pri) {
1141             lwkt_schedule_self(curthread);
1142             lwkt_switch();
1143         }
1144     }
1145 }
1146
1147 /*
1148  * This yield is designed for kernel threads with a user context.
1149  *
1150  * The kernel acting on behalf of the user is potentially cpu-bound,
1151  * this function will efficiently allow other threads to run and also
1152  * switch to other processes by releasing.
1153  *
1154  * The lwkt_user_yield() function is designed to have very low overhead
1155  * if no yield is determined to be needed.
1156  */
1157 void
1158 lwkt_user_yield(void)
1159 {
1160     globaldata_t gd = mycpu;
1161     thread_t td = gd->gd_curthread;
1162
1163     /*
1164      * Always run any pending interrupts in case we are in a critical
1165      * section.
1166      */
1167     if ((gd->gd_reqflags & RQF_IDLECHECK_MASK) && td->td_nest_count < 2)
1168         splz();
1169
1170 #ifdef SMP
1171     /*
1172      * XXX SEVERE TEMPORARY HACK.  A cpu-bound operation running in the
1173      * kernel can prevent other cpus from servicing interrupt threads
1174      * which still require the MP lock (which is a lot of them).  This
1175      * has a chaining effect since if the interrupt is blocked, so is
1176      * the event, so normal scheduling will not pick up on the problem.
1177      */
1178     if (cpu_contention_mask && td->td_mpcount + td->td_xpcount) {
1179         yield_mplock(td);
1180     }
1181 #endif
1182
1183     /*
1184      * Switch (which forces a release) if another kernel thread needs
1185      * the cpu, if userland wants us to resched, or if our kernel
1186      * quantum has run out.
1187      */
1188     if (lwkt_resched_wanted() ||
1189         user_resched_wanted() ||
1190         td->td_fairq_accum < 0)
1191     {
1192         lwkt_switch();
1193     }
1194
1195 #if 0
1196     /*
1197      * Reacquire the current process if we are released.
1198      *
1199      * XXX not implemented atm.  The kernel may be holding locks and such,
1200      *     so we want the thread to continue to receive cpu.
1201      */
1202     if (td->td_release == NULL && lp) {
1203         lp->lwp_proc->p_usched->acquire_curproc(lp);
1204         td->td_release = lwkt_passive_release;
1205         lwkt_setpri_self(TDPRI_USER_NORM);
1206     }
1207 #endif
1208 }
1209
1210 /*
1211  * Generic schedule.  Possibly schedule threads belonging to other cpus and
1212  * deal with threads that might be blocked on a wait queue.
1213  *
1214  * We have a little helper inline function which does additional work after
1215  * the thread has been enqueued, including dealing with preemption and
1216  * setting need_lwkt_resched() (which prevents the kernel from returning
1217  * to userland until it has processed higher priority threads).
1218  *
1219  * It is possible for this routine to be called after a failed _enqueue
1220  * (due to the target thread migrating, sleeping, or otherwise blocked).
1221  * We have to check that the thread is actually on the run queue!
1222  *
1223  * reschedok is an optimized constant propagated from lwkt_schedule() or
1224  * lwkt_schedule_noresched().  By default it is non-zero, causing a
1225  * reschedule to be requested if the target thread has a higher priority.
1226  * The port messaging code will set MSG_NORESCHED and cause reschedok to
1227  * be 0, prevented undesired reschedules.
1228  */
1229 static __inline
1230 void
1231 _lwkt_schedule_post(globaldata_t gd, thread_t ntd, int ccount, int reschedok)
1232 {
1233     thread_t otd;
1234
1235     if (ntd->td_flags & TDF_RUNQ) {
1236         if (ntd->td_preemptable && reschedok) {
1237             ntd->td_preemptable(ntd, ccount);   /* YYY +token */
1238         } else if (reschedok) {
1239             otd = curthread;
1240             if (ntd->td_pri > otd->td_pri)
1241                 need_lwkt_resched();
1242         }
1243
1244         /*
1245          * Give the thread a little fair share scheduler bump if it
1246          * has been asleep for a while.  This is primarily to avoid
1247          * a degenerate case for interrupt threads where accumulator
1248          * crosses into negative territory unnecessarily.
1249          */
1250         if (ntd->td_fairq_lticks != ticks) {
1251             ntd->td_fairq_lticks = ticks;
1252             ntd->td_fairq_accum += gd->gd_fairq_total_pri;
1253             if (ntd->td_fairq_accum > TDFAIRQ_MAX(gd))
1254                     ntd->td_fairq_accum = TDFAIRQ_MAX(gd);
1255         }
1256     }
1257 }
1258
1259 static __inline
1260 void
1261 _lwkt_schedule(thread_t td, int reschedok)
1262 {
1263     globaldata_t mygd = mycpu;
1264
1265     KASSERT(td != &td->td_gd->gd_idlethread, ("lwkt_schedule(): scheduling gd_idlethread is illegal!"));
1266     crit_enter_gd(mygd);
1267     KKASSERT(td->td_lwp == NULL || (td->td_lwp->lwp_flag & LWP_ONRUNQ) == 0);
1268     if (td == mygd->gd_curthread) {
1269         _lwkt_enqueue(td);
1270     } else {
1271         /*
1272          * If we own the thread, there is no race (since we are in a
1273          * critical section).  If we do not own the thread there might
1274          * be a race but the target cpu will deal with it.
1275          */
1276 #ifdef SMP
1277         if (td->td_gd == mygd) {
1278             _lwkt_enqueue(td);
1279             _lwkt_schedule_post(mygd, td, 1, reschedok);
1280         } else {
1281             lwkt_send_ipiq3(td->td_gd, lwkt_schedule_remote, td, 0);
1282         }
1283 #else
1284         _lwkt_enqueue(td);
1285         _lwkt_schedule_post(mygd, td, 1, reschedok);
1286 #endif
1287     }
1288     crit_exit_gd(mygd);
1289 }
1290
1291 void
1292 lwkt_schedule(thread_t td)
1293 {
1294     _lwkt_schedule(td, 1);
1295 }
1296
1297 void
1298 lwkt_schedule_noresched(thread_t td)
1299 {
1300     _lwkt_schedule(td, 0);
1301 }
1302
1303 #ifdef SMP
1304
1305 /*
1306  * When scheduled remotely if frame != NULL the IPIQ is being
1307  * run via doreti or an interrupt then preemption can be allowed.
1308  *
1309  * To allow preemption we have to drop the critical section so only
1310  * one is present in _lwkt_schedule_post.
1311  */
1312 static void
1313 lwkt_schedule_remote(void *arg, int arg2, struct intrframe *frame)
1314 {
1315     thread_t td = curthread;
1316     thread_t ntd = arg;
1317
1318     if (frame && ntd->td_preemptable) {
1319         crit_exit_noyield(td);
1320         _lwkt_schedule(ntd, 1);
1321         crit_enter_quick(td);
1322     } else {
1323         _lwkt_schedule(ntd, 1);
1324     }
1325 }
1326
1327 /*
1328  * Thread migration using a 'Pull' method.  The thread may or may not be
1329  * the current thread.  It MUST be descheduled and in a stable state.
1330  * lwkt_giveaway() must be called on the cpu owning the thread.
1331  *
1332  * At any point after lwkt_giveaway() is called, the target cpu may
1333  * 'pull' the thread by calling lwkt_acquire().
1334  *
1335  * We have to make sure the thread is not sitting on a per-cpu tsleep
1336  * queue or it will blow up when it moves to another cpu.
1337  *
1338  * MPSAFE - must be called under very specific conditions.
1339  */
1340 void
1341 lwkt_giveaway(thread_t td)
1342 {
1343     globaldata_t gd = mycpu;
1344
1345     crit_enter_gd(gd);
1346     if (td->td_flags & TDF_TSLEEPQ)
1347         tsleep_remove(td);
1348     KKASSERT(td->td_gd == gd);
1349     TAILQ_REMOVE(&gd->gd_tdallq, td, td_allq);
1350     td->td_flags |= TDF_MIGRATING;
1351     crit_exit_gd(gd);
1352 }
1353
1354 void
1355 lwkt_acquire(thread_t td)
1356 {
1357     globaldata_t gd;
1358     globaldata_t mygd;
1359
1360     KKASSERT(td->td_flags & TDF_MIGRATING);
1361     gd = td->td_gd;
1362     mygd = mycpu;
1363     if (gd != mycpu) {
1364         cpu_lfence();
1365         KKASSERT((td->td_flags & TDF_RUNQ) == 0);
1366         crit_enter_gd(mygd);
1367         while (td->td_flags & (TDF_RUNNING|TDF_PREEMPT_LOCK)) {
1368 #ifdef SMP
1369             lwkt_process_ipiq();
1370 #endif
1371             cpu_lfence();
1372         }
1373         cpu_mfence();
1374         td->td_gd = mygd;
1375         TAILQ_INSERT_TAIL(&mygd->gd_tdallq, td, td_allq);
1376         td->td_flags &= ~TDF_MIGRATING;
1377         crit_exit_gd(mygd);
1378     } else {
1379         crit_enter_gd(mygd);
1380         TAILQ_INSERT_TAIL(&mygd->gd_tdallq, td, td_allq);
1381         td->td_flags &= ~TDF_MIGRATING;
1382         crit_exit_gd(mygd);
1383     }
1384 }
1385
1386 #endif
1387
1388 /*
1389  * Generic deschedule.  Descheduling threads other then your own should be
1390  * done only in carefully controlled circumstances.  Descheduling is 
1391  * asynchronous.  
1392  *
1393  * This function may block if the cpu has run out of messages.
1394  */
1395 void
1396 lwkt_deschedule(thread_t td)
1397 {
1398     crit_enter();
1399 #ifdef SMP
1400     if (td == curthread) {
1401         _lwkt_dequeue(td);
1402     } else {
1403         if (td->td_gd == mycpu) {
1404             _lwkt_dequeue(td);
1405         } else {
1406             lwkt_send_ipiq(td->td_gd, (ipifunc1_t)lwkt_deschedule, td);
1407         }
1408     }
1409 #else
1410     _lwkt_dequeue(td);
1411 #endif
1412     crit_exit();
1413 }
1414
1415 /*
1416  * Set the target thread's priority.  This routine does not automatically
1417  * switch to a higher priority thread, LWKT threads are not designed for
1418  * continuous priority changes.  Yield if you want to switch.
1419  */
1420 void
1421 lwkt_setpri(thread_t td, int pri)
1422 {
1423     KKASSERT(td->td_gd == mycpu);
1424     if (td->td_pri != pri) {
1425         KKASSERT(pri >= 0);
1426         crit_enter();
1427         if (td->td_flags & TDF_RUNQ) {
1428             _lwkt_dequeue(td);
1429             td->td_pri = pri;
1430             _lwkt_enqueue(td);
1431         } else {
1432             td->td_pri = pri;
1433         }
1434         crit_exit();
1435     }
1436 }
1437
1438 /*
1439  * Set the initial priority for a thread prior to it being scheduled for
1440  * the first time.  The thread MUST NOT be scheduled before or during
1441  * this call.  The thread may be assigned to a cpu other then the current
1442  * cpu.
1443  *
1444  * Typically used after a thread has been created with TDF_STOPPREQ,
1445  * and before the thread is initially scheduled.
1446  */
1447 void
1448 lwkt_setpri_initial(thread_t td, int pri)
1449 {
1450     KKASSERT(pri >= 0);
1451     KKASSERT((td->td_flags & TDF_RUNQ) == 0);
1452     td->td_pri = pri;
1453 }
1454
1455 void
1456 lwkt_setpri_self(int pri)
1457 {
1458     thread_t td = curthread;
1459
1460     KKASSERT(pri >= 0 && pri <= TDPRI_MAX);
1461     crit_enter();
1462     if (td->td_flags & TDF_RUNQ) {
1463         _lwkt_dequeue(td);
1464         td->td_pri = pri;
1465         _lwkt_enqueue(td);
1466     } else {
1467         td->td_pri = pri;
1468     }
1469     crit_exit();
1470 }
1471
1472 /*
1473  * 1/hz tick (typically 10ms) x TDFAIRQ_SCALE (typ 8) = 80ms full cycle.
1474  *
1475  * Example: two competing threads, same priority N.  decrement by (2*N)
1476  * increment by N*8, each thread will get 4 ticks.
1477  */
1478 void
1479 lwkt_fairq_schedulerclock(thread_t td)
1480 {
1481     if (fairq_enable) {
1482         while (td) {
1483             if (td != &td->td_gd->gd_idlethread) {
1484                 td->td_fairq_accum -= td->td_gd->gd_fairq_total_pri;
1485                 if (td->td_fairq_accum < -TDFAIRQ_MAX(td->td_gd))
1486                         td->td_fairq_accum = -TDFAIRQ_MAX(td->td_gd);
1487                 if (td->td_fairq_accum < 0)
1488                         need_lwkt_resched();
1489                 td->td_fairq_lticks = ticks;
1490             }
1491             td = td->td_preempted;
1492         }
1493     }
1494 }
1495
1496 static void
1497 lwkt_fairq_accumulate(globaldata_t gd, thread_t td)
1498 {
1499         td->td_fairq_accum += td->td_pri * TDFAIRQ_SCALE;
1500         if (td->td_fairq_accum > TDFAIRQ_MAX(td->td_gd))
1501                 td->td_fairq_accum = TDFAIRQ_MAX(td->td_gd);
1502 }
1503
1504 /*
1505  * Migrate the current thread to the specified cpu. 
1506  *
1507  * This is accomplished by descheduling ourselves from the current cpu,
1508  * moving our thread to the tdallq of the target cpu, IPI messaging the
1509  * target cpu, and switching out.  TDF_MIGRATING prevents scheduling
1510  * races while the thread is being migrated.
1511  *
1512  * We must be sure to remove ourselves from the current cpu's tsleepq
1513  * before potentially moving to another queue.  The thread can be on
1514  * a tsleepq due to a left-over tsleep_interlock().
1515  */
1516 #ifdef SMP
1517 static void lwkt_setcpu_remote(void *arg);
1518 #endif
1519
1520 void
1521 lwkt_setcpu_self(globaldata_t rgd)
1522 {
1523 #ifdef SMP
1524     thread_t td = curthread;
1525
1526     if (td->td_gd != rgd) {
1527         crit_enter_quick(td);
1528         if (td->td_flags & TDF_TSLEEPQ)
1529             tsleep_remove(td);
1530         td->td_flags |= TDF_MIGRATING;
1531         lwkt_deschedule_self(td);
1532         TAILQ_REMOVE(&td->td_gd->gd_tdallq, td, td_allq);
1533         lwkt_send_ipiq(rgd, (ipifunc1_t)lwkt_setcpu_remote, td);
1534         lwkt_switch();
1535         /* we are now on the target cpu */
1536         TAILQ_INSERT_TAIL(&rgd->gd_tdallq, td, td_allq);
1537         crit_exit_quick(td);
1538     }
1539 #endif
1540 }
1541
1542 void
1543 lwkt_migratecpu(int cpuid)
1544 {
1545 #ifdef SMP
1546         globaldata_t rgd;
1547
1548         rgd = globaldata_find(cpuid);
1549         lwkt_setcpu_self(rgd);
1550 #endif
1551 }
1552
1553 /*
1554  * Remote IPI for cpu migration (called while in a critical section so we
1555  * do not have to enter another one).  The thread has already been moved to
1556  * our cpu's allq, but we must wait for the thread to be completely switched
1557  * out on the originating cpu before we schedule it on ours or the stack
1558  * state may be corrupt.  We clear TDF_MIGRATING after flushing the GD
1559  * change to main memory.
1560  *
1561  * XXX The use of TDF_MIGRATING might not be sufficient to avoid races
1562  * against wakeups.  It is best if this interface is used only when there
1563  * are no pending events that might try to schedule the thread.
1564  */
1565 #ifdef SMP
1566 static void
1567 lwkt_setcpu_remote(void *arg)
1568 {
1569     thread_t td = arg;
1570     globaldata_t gd = mycpu;
1571
1572     while (td->td_flags & (TDF_RUNNING|TDF_PREEMPT_LOCK)) {
1573 #ifdef SMP
1574         lwkt_process_ipiq();
1575 #endif
1576         cpu_lfence();
1577         cpu_pause();
1578     }
1579     td->td_gd = gd;
1580     cpu_mfence();
1581     td->td_flags &= ~TDF_MIGRATING;
1582     KKASSERT(td->td_lwp == NULL || (td->td_lwp->lwp_flag & LWP_ONRUNQ) == 0);
1583     _lwkt_enqueue(td);
1584 }
1585 #endif
1586
1587 struct lwp *
1588 lwkt_preempted_proc(void)
1589 {
1590     thread_t td = curthread;
1591     while (td->td_preempted)
1592         td = td->td_preempted;
1593     return(td->td_lwp);
1594 }
1595
1596 /*
1597  * Create a kernel process/thread/whatever.  It shares it's address space
1598  * with proc0 - ie: kernel only.
1599  *
1600  * NOTE!  By default new threads are created with the MP lock held.  A 
1601  * thread which does not require the MP lock should release it by calling
1602  * rel_mplock() at the start of the new thread.
1603  */
1604 int
1605 lwkt_create(void (*func)(void *), void *arg, struct thread **tdp,
1606             thread_t template, int tdflags, int cpu, const char *fmt, ...)
1607 {
1608     thread_t td;
1609     __va_list ap;
1610
1611     td = lwkt_alloc_thread(template, LWKT_THREAD_STACK, cpu,
1612                            tdflags);
1613     if (tdp)
1614         *tdp = td;
1615     cpu_set_thread_handler(td, lwkt_exit, func, arg);
1616
1617     /*
1618      * Set up arg0 for 'ps' etc
1619      */
1620     __va_start(ap, fmt);
1621     kvsnprintf(td->td_comm, sizeof(td->td_comm), fmt, ap);
1622     __va_end(ap);
1623
1624     /*
1625      * Schedule the thread to run
1626      */
1627     if ((td->td_flags & TDF_STOPREQ) == 0)
1628         lwkt_schedule(td);
1629     else
1630         td->td_flags &= ~TDF_STOPREQ;
1631     return 0;
1632 }
1633
1634 /*
1635  * Destroy an LWKT thread.   Warning!  This function is not called when
1636  * a process exits, cpu_proc_exit() directly calls cpu_thread_exit() and
1637  * uses a different reaping mechanism.
1638  */
1639 void
1640 lwkt_exit(void)
1641 {
1642     thread_t td = curthread;
1643     thread_t std;
1644     globaldata_t gd;
1645
1646     if (td->td_flags & TDF_VERBOSE)
1647         kprintf("kthread %p %s has exited\n", td, td->td_comm);
1648     caps_exit(td);
1649
1650     /*
1651      * Get us into a critical section to interlock gd_freetd and loop
1652      * until we can get it freed.
1653      *
1654      * We have to cache the current td in gd_freetd because objcache_put()ing
1655      * it would rip it out from under us while our thread is still active.
1656      */
1657     gd = mycpu;
1658     crit_enter_quick(td);
1659     while ((std = gd->gd_freetd) != NULL) {
1660         gd->gd_freetd = NULL;
1661         objcache_put(thread_cache, std);
1662     }
1663
1664     /*
1665      * Remove thread resources from kernel lists and deschedule us for
1666      * the last time.
1667      */
1668     if (td->td_flags & TDF_TSLEEPQ)
1669         tsleep_remove(td);
1670     biosched_done(td);
1671     dsched_exit_thread(td);
1672     lwkt_deschedule_self(td);
1673     lwkt_remove_tdallq(td);
1674     if (td->td_flags & TDF_ALLOCATED_THREAD)
1675         gd->gd_freetd = td;
1676     cpu_thread_exit();
1677 }
1678
1679 void
1680 lwkt_remove_tdallq(thread_t td)
1681 {
1682     KKASSERT(td->td_gd == mycpu);
1683     TAILQ_REMOVE(&td->td_gd->gd_tdallq, td, td_allq);
1684 }
1685
1686 /*
1687  * Code reduction and branch prediction improvements.  Call/return
1688  * overhead on modern cpus often degenerates into 0 cycles due to
1689  * the cpu's branch prediction hardware and return pc cache.  We
1690  * can take advantage of this by not inlining medium-complexity
1691  * functions and we can also reduce the branch prediction impact
1692  * by collapsing perfectly predictable branches into a single
1693  * procedure instead of duplicating it.
1694  *
1695  * Is any of this noticeable?  Probably not, so I'll take the
1696  * smaller code size.
1697  */
1698 void
1699 crit_exit_wrapper(__DEBUG_CRIT_ARG__)
1700 {
1701     _crit_exit(mycpu __DEBUG_CRIT_PASS_ARG__);
1702 }
1703
1704 void
1705 crit_panic(void)
1706 {
1707     thread_t td = curthread;
1708     int lcrit = td->td_critcount;
1709
1710     td->td_critcount = 0;
1711     panic("td_critcount is/would-go negative! %p %d", td, lcrit);
1712     /* NOT REACHED */
1713 }
1714
1715 #ifdef SMP
1716
1717 /*
1718  * Called from debugger/panic on cpus which have been stopped.  We must still
1719  * process the IPIQ while stopped, even if we were stopped while in a critical
1720  * section (XXX).
1721  *
1722  * If we are dumping also try to process any pending interrupts.  This may
1723  * or may not work depending on the state of the cpu at the point it was
1724  * stopped.
1725  */
1726 void
1727 lwkt_smp_stopped(void)
1728 {
1729     globaldata_t gd = mycpu;
1730
1731     crit_enter_gd(gd);
1732     if (dumping) {
1733         lwkt_process_ipiq();
1734         splz();
1735     } else {
1736         lwkt_process_ipiq();
1737     }
1738     crit_exit_gd(gd);
1739 }
1740
1741 #endif