sys/kern/lwkt_thread.c

   1 /*
   2  * Copyright (c) 2003 Matthew Dillon <dillon@backplane.com>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  *      Each cpu in a system has its own self-contained light weight kernel
  27  *      thread scheduler, which means that generally speaking we only need
  28  *      to use a critical section to prevent hicups.
  29  *
  30  * $DragonFly: src/sys/kern/lwkt_thread.c,v 1.4 2003/06/22 04:30:42 dillon Exp $
  31  */
  32
  33 #include <sys/param.h>
  34 #include <sys/systm.h>
  35 #include <sys/kernel.h>
  36 #include <sys/proc.h>
  37 #include <sys/rtprio.h>
  38 #include <sys/queue.h>
  39 #include <sys/thread2.h>
  40 #include <sys/lock.h>
  41 #include <sys/sysctl.h>
  42 #include <machine/cpu.h>
  43
  44 #include <vm/vm.h>
  45 #include <vm/vm_param.h>
  46 #include <vm/vm_kern.h>
  47 #include <vm/vm_object.h>
  48 #include <vm/vm_page.h>
  49 #include <vm/vm_map.h>
  50 #include <vm/vm_pager.h>
  51 #include <vm/vm_extern.h>
  52 #include <vm/vm_zone.h>
  53
  54 static int untimely_switch = 0;
  55 SYSCTL_INT(_debug, OID_AUTO, untimely_switch, CTLFLAG_RW, &untimely_switch, 0, "");
  56
  57
  58 static __inline
  59 void
  60 _lwkt_dequeue(thread_t td)
  61 {
  62     if (td->td_flags & TDF_RUNQ) {
  63         td->td_flags &= ~TDF_RUNQ;
  64         TAILQ_REMOVE(&mycpu->gd_tdrunq, td, td_threadq);
  65     }
  66 }
  67
  68 static __inline
  69 void
  70 _lwkt_enqueue(thread_t td)
  71 {
  72     if ((td->td_flags & TDF_RUNQ) == 0) {
  73         td->td_flags |= TDF_RUNQ;
  74         TAILQ_INSERT_TAIL(&mycpu->gd_tdrunq, td, td_threadq);
  75     }
  76 }
  77
  78 /*
  79  * LWKTs operate on a per-cpu basis
  80  *
  81  * YYY implement strict priorities & round-robin at the same priority
  82  */
  83 void
  84 lwkt_gdinit(struct globaldata *gd)
  85 {
  86     TAILQ_INIT(&gd->gd_tdrunq);
  87 }
  88
  89 /*
  90  * Initialize a thread wait structure prior to first use.
  91  *
  92  * NOTE!  called from low level boot code, we cannot do anything fancy!
  93  */
  94 void
  95 lwkt_init_wait(lwkt_wait_t w)
  96 {
  97     TAILQ_INIT(&w->wa_waitq);
  98 }
  99
 100 /*
 101  * Create a new thread.  The thread must be associated with a process context
 102  * or LWKT start address before it can be scheduled.
 103  */
 104 thread_t
 105 lwkt_alloc_thread(void)
 106 {
 107         struct thread *td;
 108         void *stack;
 109
 110         crit_enter();
 111         if (mycpu->gd_tdfreecount > 0) {
 112                 --mycpu->gd_tdfreecount;
 113                 td = TAILQ_FIRST(&mycpu->gd_tdfreeq);
 114                 KASSERT(td != NULL, ("unexpected null cache td"));
 115                 TAILQ_REMOVE(&mycpu->gd_tdfreeq, td, td_threadq);
 116                 crit_exit();
 117                 stack = td->td_kstack;
 118         } else {
 119                 crit_exit();
 120                 td = zalloc(thread_zone);
 121                 stack = (void *)kmem_alloc(kernel_map, UPAGES * PAGE_SIZE);
 122         }
 123         lwkt_init_thread(td, stack);
 124         return(td);
 125 }
 126
 127 /*
 128  * Initialize a preexisting thread structure.  This function is used by
 129  * lwkt_alloc_thread() and also used to initialize the per-cpu idlethread.
 130  *
 131  * NOTE!  called from low level boot code, we cannot do anything fancy!
 132  */
 133 void
 134 lwkt_init_thread(thread_t td, void *stack)
 135 {
 136         bzero(td, sizeof(struct thread));
 137         lwkt_rwlock_init(&td->td_rwlock);
 138         td->td_kstack = stack;
 139         pmap_init_thread(td);
 140 }
 141
 142 /*
 143  * Switch to the next runnable lwkt.  If no LWKTs are runnable then
 144  * switch to the idlethread.  Switching must occur within a critical
 145  * section to avoid races with the scheduling queue.
 146  *
 147  * We always have full control over our cpu's run queue.  Other cpus
 148  * that wish to manipulate our queue must use the cpu_*msg() calls to
 149  * talk to our cpu, so a critical section is all that is needed and
 150  * the result is very, very fast thread switching.
 151  *
 152  * We always 'own' our own thread and the threads on our run queue,l
 153  * due to TDF_RUNNING or TDF_RUNQ being set.  We can safely clear
 154  * TDF_RUNNING while in a critical section.
 155  *
 156  * The td_switch() function must be called while in the critical section.
 157  * This function saves as much state as is appropriate for the type of
 158  * thread.
 159  *
 160  * (self contained on a per cpu basis)
 161  */
 162 void
 163 lwkt_switch(void)
 164 {
 165     thread_t td = curthread;
 166     thread_t ntd;
 167
 168     crit_enter();
 169     if ((ntd = TAILQ_FIRST(&mycpu->gd_tdrunq)) != NULL) {
 170         TAILQ_REMOVE(&mycpu->gd_tdrunq, ntd, td_threadq);
 171         TAILQ_INSERT_TAIL(&mycpu->gd_tdrunq, ntd, td_threadq);
 172     } else {
 173         ntd = &mycpu->gd_idlethread;
 174     }
 175     if (td != ntd) {
 176         td->td_flags &= ~TDF_RUNNING;
 177         ntd->td_flags |= TDF_RUNNING;
 178         td->td_switch(ntd);
 179     }
 180     crit_exit();
 181 }
 182
 183 /*
 184  * Yield our thread while higher priority threads are pending.  This is
 185  * typically called when we leave a critical section but it can be safely
 186  * called while we are in a critical section.
 187  *
 188  * This function will not generally yield to equal priority threads but it
 189  * can occur as a side effect.  Note that lwkt_switch() is called from
 190  * inside the critical section to pervent its own crit_exit() from reentering
 191  * lwkt_yield_quick().
 192  *
 193  * (self contained on a per cpu basis)
 194  */
 195 void
 196 lwkt_yield_quick(void)
 197 {
 198     thread_t td = curthread;
 199     while ((td->td_pri & TDPRI_MASK) < mycpu->gd_reqpri) {
 200 #if 0
 201         cpu_schedule_reqs();    /* resets gd_reqpri */
 202 #endif
 203         splz();
 204     }
 205
 206     /*
 207      * YYY enabling will cause wakeup() to task-switch, which really
 208      * confused the old 4.x code.  This is a good way to simulate
 209      * preemption and MP without actually doing preemption or MP, because a
 210      * lot of code assumes that wakeup() does not block.
 211      */
 212     if (untimely_switch && intr_nesting_level == 0) {
 213         crit_enter();
 214         /*
 215          * YYY temporary hacks until we disassociate the userland scheduler
 216          * from the LWKT scheduler.
 217          */
 218         if (td->td_flags & TDF_RUNQ) {
 219             lwkt_switch();              /* will not reenter yield function */
 220         } else {
 221             lwkt_schedule_self();       /* make sure we are scheduled */
 222             lwkt_switch();              /* will not reenter yield function */
 223             lwkt_deschedule_self();     /* make sure we are descheduled */
 224         }
 225         crit_exit_noyield();
 226     }
 227 }
 228
 229 /*
 230  * This implements a normal yield which, unlike _quick, will yield to equal
 231  * priority threads as well.  Note that gd_reqpri tests will be handled by
 232  * the crit_exit() call in lwkt_switch().
 233  *
 234  * (self contained on a per cpu basis)
 235  */
 236 void
 237 lwkt_yield(void)
 238 {
 239     lwkt_schedule_self();
 240     lwkt_switch();
 241 }
 242
 243 /*
 244  * Schedule a thread to run.  As the current thread we can always safely
 245  * schedule ourselves, and a shortcut procedure is provided for that
 246  * function.
 247  *
 248  * (non-blocking, self contained on a per cpu basis)
 249  */
 250 void
 251 lwkt_schedule_self(void)
 252 {
 253     thread_t td = curthread;
 254
 255     crit_enter();
 256     KASSERT(td->td_wait == NULL, ("lwkt_schedule_self(): td_wait not NULL!"));
 257     KASSERT(td->td_flags & TDF_RUNNING, ("lwkt_schedule_self(): TDF_RUNNING not set!"));
 258     _lwkt_enqueue(td);
 259     crit_exit();
 260 }
 261
 262 /*
 263  * Generic schedule.  Possibly schedule threads belonging to other cpus and
 264  * deal with threads that might be blocked on a wait queue.
 265  *
 266  * This function will queue requests asynchronously when possible, but may
 267  * block if no request structures are available.  Upon return the caller
 268  * should note that the scheduling request may not yet have been processed
 269  * by the target cpu.
 270  *
 271  * YYY this is one of the best places to implement any load balancing code.
 272  * Load balancing can be accomplished by requesting other sorts of actions
 273  * for the thread in question.
 274  */
 275 void
 276 lwkt_schedule(thread_t td)
 277 {
 278     crit_enter();
 279     if (td == curthread) {
 280         _lwkt_enqueue(td);
 281     } else {
 282         lwkt_wait_t w;
 283
 284         /*
 285          * If the thread is on a wait list we have to send our scheduling
 286          * request to the owner of the wait structure.  Otherwise we send
 287          * the scheduling request to the cpu owning the thread.  Races
 288          * are ok, the target will forward the message as necessary (the
 289          * message may chase the thread around before it finally gets
 290          * acted upon).
 291          *
 292          * (remember, wait structures use stable storage)
 293          */
 294         if ((w = td->td_wait) != NULL) {
 295             if (lwkt_havetoken(&w->wa_token)) {
 296                 TAILQ_REMOVE(&w->wa_waitq, td, td_threadq);
 297                 --w->wa_count;
 298                 td->td_wait = NULL;
 299                 if (td->td_cpu == mycpu->gd_cpu) {
 300                     _lwkt_enqueue(td);
 301                 } else {
 302                     panic("lwkt_schedule: cpu mismatch1");
 303 #if 0
 304                     lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 305                     initScheduleReqMsg_Wait(&msg.mu_SchedReq, td, w);
 306                     cpu_sendnormsg(&msg.mu_Msg);
 307 #endif
 308                 }
 309             } else {
 310                 panic("lwkt_schedule: cpu mismatch2");
 311 #if 0
 312                 lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 313                 initScheduleReqMsg_Wait(&msg.mu_SchedReq, td, w);
 314                 cpu_sendnormsg(&msg.mu_Msg);
 315 #endif
 316             }
 317         } else {
 318             /*
 319              * If the wait structure is NULL and we own the thread, there
 320              * is no race (since we are in a critical section).  If we
 321              * do not own the thread there might be a race but the
 322              * target cpu will deal with it.
 323              */
 324             if (td->td_cpu == mycpu->gd_cpu) {
 325                 _lwkt_enqueue(td);
 326             } else {
 327                 panic("lwkt_schedule: cpu mismatch3");
 328 #if 0
 329                 lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 330                 initScheduleReqMsg_Thread(&msg.mu_SchedReq, td);
 331                 cpu_sendnormsg(&msg.mu_Msg);
 332 #endif
 333             }
 334         }
 335     }
 336     crit_exit();
 337 }
 338
 339 /*
 340  * Deschedule a thread.
 341  *
 342  * (non-blocking, self contained on a per cpu basis)
 343  */
 344 void
 345 lwkt_deschedule_self(void)
 346 {
 347     thread_t td = curthread;
 348
 349     crit_enter();
 350     KASSERT(td->td_wait == NULL, ("lwkt_schedule_self(): td_wait not NULL!"));
 351     KASSERT(td->td_flags & TDF_RUNNING, ("lwkt_schedule_self(): TDF_RUNNING not set!"));
 352     _lwkt_dequeue(td);
 353     crit_exit();
 354 }
 355
 356 /*
 357  * Generic deschedule.  Descheduling threads other then your own should be
 358  * done only in carefully controlled circumstances.  Descheduling is
 359  * asynchronous.
 360  *
 361  * This function may block if the cpu has run out of messages.
 362  */
 363 void
 364 lwkt_deschedule(thread_t td)
 365 {
 366     crit_enter();
 367     if (td == curthread) {
 368         _lwkt_dequeue(td);
 369     } else {
 370         if (td->td_cpu == mycpu->gd_cpu) {
 371             _lwkt_dequeue(td);
 372         } else {
 373             panic("lwkt_deschedule: cpu mismatch");
 374 #if 0
 375             lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 376             initDescheduleReqMsg_Thread(&msg.mu_DeschedReq, td);
 377             cpu_sendnormsg(&msg.mu_Msg);
 378 #endif
 379         }
 380     }
 381     crit_exit();
 382 }
 383
 384 /*
 385  * This function deschedules the current thread and blocks on the specified
 386  * wait queue.  We obtain ownership of the wait queue in order to block
 387  * on it.  A generation number is used to interlock the wait queue in case
 388  * it gets signalled while we are blocked waiting on the token.
 389  *
 390  * Note: alternatively we could dequeue our thread and then message the
 391  * target cpu owning the wait queue.  YYY implement as sysctl.
 392  *
 393  * Note: wait queue signals normally ping-pong the cpu as an optimization.
 394  */
 395 void
 396 lwkt_block(lwkt_wait_t w, const char *wmesg, int *gen)
 397 {
 398     thread_t td = curthread;
 399
 400     lwkt_gettoken(&w->wa_token);
 401     if (w->wa_gen == *gen) {
 402         _lwkt_dequeue(td);
 403         TAILQ_INSERT_TAIL(&w->wa_waitq, td, td_threadq);
 404         ++w->wa_count;
 405         td->td_wait = w;
 406         td->td_wmesg = wmesg;
 407         lwkt_switch();
 408     }
 409     /* token might be lost, doesn't matter for gen update */
 410     *gen = w->wa_gen;
 411     lwkt_reltoken(&w->wa_token);
 412 }
 413
 414 /*
 415  * Signal a wait queue.  We gain ownership of the wait queue in order to
 416  * signal it.  Once a thread is removed from the wait queue we have to
 417  * deal with the cpu owning the thread.
 418  *
 419  * Note: alternatively we could message the target cpu owning the wait
 420  * queue.  YYY implement as sysctl.
 421  */
 422 void
 423 lwkt_signal(lwkt_wait_t w)
 424 {
 425     thread_t td;
 426     int count;
 427
 428     lwkt_gettoken(&w->wa_token);
 429     ++w->wa_gen;
 430     count = w->wa_count;
 431     while ((td = TAILQ_FIRST(&w->wa_waitq)) != NULL && count) {
 432         --count;
 433         --w->wa_count;
 434         TAILQ_REMOVE(&w->wa_waitq, td, td_threadq);
 435         td->td_wait = NULL;
 436         td->td_wmesg = NULL;
 437         if (td->td_cpu == mycpu->gd_cpu) {
 438             _lwkt_enqueue(td);
 439         } else {
 440 #if 0
 441             lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 442             initScheduleReqMsg_Thread(&msg.mu_SchedReq, td);
 443             cpu_sendnormsg(&msg.mu_Msg);
 444 #endif
 445             panic("lwkt_signal: cpu mismatch");
 446         }
 447         lwkt_regettoken(&w->wa_token);
 448     }
 449     lwkt_reltoken(&w->wa_token);
 450 }
 451
 452 /*
 453  * Aquire ownership of a token
 454  *
 455  * Aquire ownership of a token.  The token may have spl and/or critical
 456  * section side effects, depending on its purpose.  These side effects
 457  * guarentee that you will maintain ownership of the token as long as you
 458  * do not block.  If you block you may lose access to the token (but you
 459  * must still release it even if you lose your access to it).
 460  *
 461  * Note that the spl and critical section characteristics of a token
 462  * may not be changed once the token has been initialized.
 463  */
 464 void
 465 lwkt_gettoken(lwkt_token_t tok)
 466 {
 467     /*
 468      * Prevent preemption so the token can't be taken away from us once
 469      * we gain ownership of it.  Use a synchronous request which might
 470      * block.  The request will be forwarded as necessary playing catchup
 471      * to the token.
 472      */
 473     crit_enter();
 474 #if 0
 475     while (tok->t_cpu != mycpu->gd_cpu) {
 476         lwkt_cpu_msg_union msg;
 477         initTokenReqMsg(&msg.mu_TokenReq);
 478         cpu_domsg(&msg);
 479     }
 480 #endif
 481     /*
 482      * leave us in a critical section on return.  This will be undone
 483      * by lwkt_reltoken()
 484      */
 485 }
 486
 487 /*
 488  * Release your ownership of a token.  Releases must occur in reverse
 489  * order to aquisitions, eventually so priorities can be unwound properly
 490  * like SPLs.  At the moment the actual implemention doesn't care.
 491  *
 492  * We can safely hand a token that we own to another cpu without notifying
 493  * it, but once we do we can't get it back without requesting it (unless
 494  * the other cpu hands it back to us before we check).
 495  *
 496  * We might have lost the token, so check that.
 497  */
 498 void
 499 lwkt_reltoken(lwkt_token_t tok)
 500 {
 501     if (tok->t_cpu == mycpu->gd_cpu) {
 502         tok->t_cpu = tok->t_reqcpu;
 503     }
 504     crit_exit();
 505 }
 506
 507 /*
 508  * Reaquire a token that might have been lost.  Returns 1 if we blocked
 509  * while reaquiring the token (meaning that you might have lost other
 510  * tokens you held when you made this call), return 0 if we did not block.
 511  */
 512 int
 513 lwkt_regettoken(lwkt_token_t tok)
 514 {
 515 #if 0
 516     if (tok->t_cpu != mycpu->gd_cpu) {
 517         while (tok->t_cpu != mycpu->gd_cpu) {
 518             lwkt_cpu_msg_union msg;
 519             initTokenReqMsg(&msg.mu_TokenReq);
 520             cpu_domsg(&msg);
 521         }
 522         return(1);
 523     }
 524 #endif
 525     return(0);
 526 }
 527