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.3 2003/06/21 17:31:19 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 <machine/cpu.h>
  41
  42 static __inline
  43 void
  44 _lwkt_dequeue(thread_t td)
  45 {
  46     if (td->td_flags & TDF_RUNQ) {
  47         td->td_flags &= ~TDF_RUNQ;
  48         TAILQ_REMOVE(&mycpu->gd_tdrunq, td, td_threadq);
  49     }
  50 }
  51
  52 static __inline
  53 void
  54 _lwkt_enqueue(thread_t td)
  55 {
  56     if ((td->td_flags & TDF_RUNQ) == 0) {
  57         td->td_flags |= TDF_RUNQ;
  58         TAILQ_INSERT_TAIL(&mycpu->gd_tdrunq, td, td_threadq);
  59     }
  60 }
  61
  62 /*
  63  * LWKTs operate on a per-cpu basis
  64  *
  65  * YYY implement strict priorities & round-robin at the same priority
  66  */
  67 void
  68 lwkt_gdinit(struct globaldata *gd)
  69 {
  70     TAILQ_INIT(&gd->gd_tdrunq);
  71 }
  72
  73 /*
  74  * Switch to the next runnable lwkt.  If no LWKTs are runnable then
  75  * switch to the idlethread.  Switching must occur within a critical
  76  * section to avoid races with the scheduling queue.
  77  *
  78  * We always have full control over our cpu's run queue.  Other cpus
  79  * that wish to manipulate our queue must use the cpu_*msg() calls to
  80  * talk to our cpu, so a critical section is all that is needed and
  81  * the result is very, very fast thread switching.
  82  *
  83  * We always 'own' our own thread and the threads on our run queue,l
  84  * due to TDF_RUNNING or TDF_RUNQ being set.  We can safely clear
  85  * TDF_RUNNING while in a critical section.
  86  *
  87  * The td_switch() function must be called while in the critical section.
  88  * This function saves as much state as is appropriate for the type of
  89  * thread.
  90  *
  91  * (self contained on a per cpu basis)
  92  */
  93 void
  94 lwkt_switch(void)
  95 {
  96     thread_t td = curthread;
  97     thread_t ntd;
  98
  99     crit_enter();
 100     if ((ntd = TAILQ_FIRST(&mycpu->gd_tdrunq)) != NULL) {
 101         TAILQ_REMOVE(&mycpu->gd_tdrunq, ntd, td_threadq);
 102         TAILQ_INSERT_TAIL(&mycpu->gd_tdrunq, ntd, td_threadq);
 103     } else {
 104         ntd = &mycpu->gd_idlethread;
 105     }
 106     if (td != ntd) {
 107         td->td_flags &= ~TDF_RUNNING;
 108         ntd->td_flags |= TDF_RUNNING;
 109         td->td_switch(ntd);
 110     }
 111     crit_exit();
 112 }
 113
 114 /*
 115  * Yield our thread while higher priority threads are pending.  This is
 116  * typically called when we leave a critical section but it can be safely
 117  * called while we are in a critical section.
 118  *
 119  * This function will not generally yield to equal priority threads but it
 120  * can occur as a side effect.  Note that lwkt_switch() is called from
 121  * inside the critical section to pervent its own crit_exit() from reentering
 122  * lwkt_yield_quick().
 123  *
 124  * (self contained on a per cpu basis)
 125  */
 126 void
 127 lwkt_yield_quick(void)
 128 {
 129     thread_t td = curthread;
 130     while ((td->td_pri & TDPRI_MASK) < mycpu->gd_reqpri) {
 131 #if 0
 132         cpu_schedule_reqs();    /* resets gd_reqpri */
 133 #endif
 134         splz();
 135     }
 136
 137     /*
 138      * YYY enabling will cause wakeup() to task-switch, which really
 139      * confused the old 4.x code.  This is a good way to simulate
 140      * preemption without actually doing preemption, because a lot
 141      * of code (including schedule, deschedule) uses critical sections
 142      * which devolve to here if an interrupt occured.
 143      */
 144 #if 0
 145     if (intr_nesting_level == 0) {
 146         crit_enter();
 147         /*
 148          * YYY temporary hacks until we disassociate the userland scheduler
 149          * from the LWKT scheduler.
 150          */
 151         if (td->td_flags & TDF_RUNQ) {
 152             lwkt_switch();              /* will not reenter yield function */
 153         } else {
 154             lwkt_schedule_self();       /* make sure we are scheduled */
 155             lwkt_switch();              /* will not reenter yield function */
 156             lwkt_deschedule_self();     /* make sure we are descheduled */
 157         }
 158         crit_exit_noyield();
 159     }
 160 #endif
 161 }
 162
 163 /*
 164  * This implements a normal yield which, unlike _quick, will yield to equal
 165  * priority threads as well.  Note that gd_reqpri tests will be handled by
 166  * the crit_exit() call in lwkt_switch().
 167  *
 168  * (self contained on a per cpu basis)
 169  */
 170 void
 171 lwkt_yield(void)
 172 {
 173     lwkt_schedule_self();
 174     lwkt_switch();
 175 }
 176
 177 /*
 178  * Schedule a thread to run.  As the current thread we can always safely
 179  * schedule ourselves, and a shortcut procedure is provided for that
 180  * function.
 181  *
 182  * (non-blocking, self contained on a per cpu basis)
 183  */
 184 void
 185 lwkt_schedule_self(void)
 186 {
 187     thread_t td = curthread;
 188
 189     crit_enter();
 190     KASSERT(td->td_wait == NULL, ("lwkt_schedule_self(): td_wait not NULL!"));
 191     KASSERT(td->td_flags & TDF_RUNNING, ("lwkt_schedule_self(): TDF_RUNNING not set!"));
 192     _lwkt_enqueue(td);
 193     crit_exit();
 194 }
 195
 196 /*
 197  * Generic schedule.  Possibly schedule threads belonging to other cpus and
 198  * deal with threads that might be blocked on a wait queue.
 199  *
 200  * This function will queue requests asynchronously when possible, but may
 201  * block if no request structures are available.  Upon return the caller
 202  * should note that the scheduling request may not yet have been processed
 203  * by the target cpu.
 204  *
 205  * YYY this is one of the best places to implement any load balancing code.
 206  * Load balancing can be accomplished by requesting other sorts of actions
 207  * for the thread in question.
 208  */
 209 void
 210 lwkt_schedule(thread_t td)
 211 {
 212     crit_enter();
 213     if (td == curthread) {
 214         _lwkt_enqueue(td);
 215     } else {
 216         lwkt_wait_t w;
 217
 218         /*
 219          * If the thread is on a wait list we have to send our scheduling
 220          * request to the owner of the wait structure.  Otherwise we send
 221          * the scheduling request to the cpu owning the thread.  Races
 222          * are ok, the target will forward the message as necessary (the
 223          * message may chase the thread around before it finally gets
 224          * acted upon).
 225          *
 226          * (remember, wait structures use stable storage)
 227          */
 228         if ((w = td->td_wait) != NULL) {
 229             if (lwkt_havetoken(&w->wa_token)) {
 230                 TAILQ_REMOVE(&w->wa_waitq, td, td_threadq);
 231                 --w->wa_count;
 232                 td->td_wait = NULL;
 233                 if (td->td_cpu == mycpu->gd_cpu) {
 234                     _lwkt_enqueue(td);
 235                 } else {
 236                     panic("lwkt_schedule: cpu mismatch1");
 237 #if 0
 238                     lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 239                     initScheduleReqMsg_Wait(&msg.mu_SchedReq, td, w);
 240                     cpu_sendnormsg(&msg.mu_Msg);
 241 #endif
 242                 }
 243             } else {
 244                 panic("lwkt_schedule: cpu mismatch2");
 245 #if 0
 246                 lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 247                 initScheduleReqMsg_Wait(&msg.mu_SchedReq, td, w);
 248                 cpu_sendnormsg(&msg.mu_Msg);
 249 #endif
 250             }
 251         } else {
 252             /*
 253              * If the wait structure is NULL and we own the thread, there
 254              * is no race (since we are in a critical section).  If we
 255              * do not own the thread there might be a race but the
 256              * target cpu will deal with it.
 257              */
 258             if (td->td_cpu == mycpu->gd_cpu) {
 259                 _lwkt_enqueue(td);
 260             } else {
 261                 panic("lwkt_schedule: cpu mismatch3");
 262 #if 0
 263                 lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 264                 initScheduleReqMsg_Thread(&msg.mu_SchedReq, td);
 265                 cpu_sendnormsg(&msg.mu_Msg);
 266 #endif
 267             }
 268         }
 269     }
 270     crit_exit();
 271 }
 272
 273 /*
 274  * Deschedule a thread.
 275  *
 276  * (non-blocking, self contained on a per cpu basis)
 277  */
 278 void
 279 lwkt_deschedule_self(void)
 280 {
 281     thread_t td = curthread;
 282
 283     crit_enter();
 284     KASSERT(td->td_wait == NULL, ("lwkt_schedule_self(): td_wait not NULL!"));
 285     KASSERT(td->td_flags & TDF_RUNNING, ("lwkt_schedule_self(): TDF_RUNNING not set!"));
 286     _lwkt_dequeue(td);
 287     crit_exit();
 288 }
 289
 290 /*
 291  * Generic deschedule.  Descheduling threads other then your own should be
 292  * done only in carefully controlled circumstances.  Descheduling is
 293  * asynchronous.
 294  *
 295  * This function may block if the cpu has run out of messages.
 296  */
 297 void
 298 lwkt_deschedule(thread_t td)
 299 {
 300     crit_enter();
 301     if (td == curthread) {
 302         _lwkt_dequeue(td);
 303     } else {
 304         if (td->td_cpu == mycpu->gd_cpu) {
 305             _lwkt_dequeue(td);
 306         } else {
 307             panic("lwkt_deschedule: cpu mismatch");
 308 #if 0
 309             lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 310             initDescheduleReqMsg_Thread(&msg.mu_DeschedReq, td);
 311             cpu_sendnormsg(&msg.mu_Msg);
 312 #endif
 313         }
 314     }
 315     crit_exit();
 316 }
 317
 318 /*
 319  * Initialize a thread wait queue
 320  */
 321 void
 322 lwkt_wait_init(lwkt_wait_t w)
 323 {
 324     TAILQ_INIT(&w->wa_waitq);
 325 }
 326
 327 /*
 328  * This function deschedules the current thread and blocks on the specified
 329  * wait queue.  We obtain ownership of the wait queue in order to block
 330  * on it.  A generation number is used to interlock the wait queue in case
 331  * it gets signalled while we are blocked waiting on the token.
 332  *
 333  * Note: alternatively we could dequeue our thread and then message the
 334  * target cpu owning the wait queue.  YYY implement as sysctl.
 335  *
 336  * Note: wait queue signals normally ping-pong the cpu as an optimization.
 337  */
 338 void
 339 lwkt_block(lwkt_wait_t w, const char *wmesg, int *gen)
 340 {
 341     thread_t td = curthread;
 342
 343     lwkt_gettoken(&w->wa_token);
 344     if (w->wa_gen == *gen) {
 345         _lwkt_dequeue(td);
 346         TAILQ_INSERT_TAIL(&w->wa_waitq, td, td_threadq);
 347         ++w->wa_count;
 348         td->td_wait = w;
 349         td->td_wmesg = wmesg;
 350         lwkt_switch();
 351     }
 352     /* token might be lost, doesn't matter for gen update */
 353     *gen = w->wa_gen;
 354     lwkt_reltoken(&w->wa_token);
 355 }
 356
 357 /*
 358  * Signal a wait queue.  We gain ownership of the wait queue in order to
 359  * signal it.  Once a thread is removed from the wait queue we have to
 360  * deal with the cpu owning the thread.
 361  *
 362  * Note: alternatively we could message the target cpu owning the wait
 363  * queue.  YYY implement as sysctl.
 364  */
 365 void
 366 lwkt_signal(lwkt_wait_t w)
 367 {
 368     thread_t td;
 369     int count;
 370
 371     lwkt_gettoken(&w->wa_token);
 372     ++w->wa_gen;
 373     count = w->wa_count;
 374     while ((td = TAILQ_FIRST(&w->wa_waitq)) != NULL && count) {
 375         --count;
 376         --w->wa_count;
 377         TAILQ_REMOVE(&w->wa_waitq, td, td_threadq);
 378         td->td_wait = NULL;
 379         td->td_wmesg = NULL;
 380         if (td->td_cpu == mycpu->gd_cpu) {
 381             _lwkt_enqueue(td);
 382         } else {
 383 #if 0
 384             lwkt_cpu_msg_union_t msg = lwkt_getcpumsg();
 385             initScheduleReqMsg_Thread(&msg.mu_SchedReq, td);
 386             cpu_sendnormsg(&msg.mu_Msg);
 387 #endif
 388             panic("lwkt_signal: cpu mismatch");
 389         }
 390         lwkt_regettoken(&w->wa_token);
 391     }
 392     lwkt_reltoken(&w->wa_token);
 393 }
 394
 395 /*
 396  * Aquire ownership of a token
 397  *
 398  * Aquire ownership of a token.  The token may have spl and/or critical
 399  * section side effects, depending on its purpose.  These side effects
 400  * guarentee that you will maintain ownership of the token as long as you
 401  * do not block.  If you block you may lose access to the token (but you
 402  * must still release it even if you lose your access to it).
 403  *
 404  * Note that the spl and critical section characteristics of a token
 405  * may not be changed once the token has been initialized.
 406  */
 407 void
 408 lwkt_gettoken(lwkt_token_t tok)
 409 {
 410     /*
 411      * Prevent preemption so the token can't be taken away from us once
 412      * we gain ownership of it.  Use a synchronous request which might
 413      * block.  The request will be forwarded as necessary playing catchup
 414      * to the token.
 415      */
 416     crit_enter();
 417 #if 0
 418     while (tok->t_cpu != mycpu->gd_cpu) {
 419         lwkt_cpu_msg_union msg;
 420         initTokenReqMsg(&msg.mu_TokenReq);
 421         cpu_domsg(&msg);
 422     }
 423 #endif
 424     /*
 425      * leave us in a critical section on return.  This will be undone
 426      * by lwkt_reltoken()
 427      */
 428 }
 429
 430 /*
 431  * Release your ownership of a token.  Releases must occur in reverse
 432  * order to aquisitions, eventually so priorities can be unwound properly
 433  * like SPLs.  At the moment the actual implemention doesn't care.
 434  *
 435  * We can safely hand a token that we own to another cpu without notifying
 436  * it, but once we do we can't get it back without requesting it (unless
 437  * the other cpu hands it back to us before we check).
 438  *
 439  * We might have lost the token, so check that.
 440  */
 441 void
 442 lwkt_reltoken(lwkt_token_t tok)
 443 {
 444     if (tok->t_cpu == mycpu->gd_cpu) {
 445         tok->t_cpu = tok->t_reqcpu;
 446     }
 447     crit_exit();
 448 }
 449
 450 /*
 451  * Reaquire a token that might have been lost.  Returns 1 if we blocked
 452  * while reaquiring the token (meaning that you might have lost other
 453  * tokens you held when you made this call), return 0 if we did not block.
 454  */
 455 int
 456 lwkt_regettoken(lwkt_token_t tok)
 457 {
 458 #if 0
 459     if (tok->t_cpu != mycpu->gd_cpu) {
 460         while (tok->t_cpu != mycpu->gd_cpu) {
 461             lwkt_cpu_msg_union msg;
 462             initTokenReqMsg(&msg.mu_TokenReq);
 463             cpu_domsg(&msg);
 464         }
 465         return(1);
 466     }
 467 #endif
 468     return(0);
 469 }
 470