root/kern/kern_timeout.c

DEFINITIONS

1. timeout_startup
2. timeout_set
3. timeout_add
4. timeout_del
5. timeout_hardclock_update
6. softclock
7. db_show_callout_bucket
8. db_show_callout

    1 /*      $OpenBSD: kern_timeout.c,v 1.25 2006/07/19 20:25:08 miod Exp $  */
    2 /*
    3  * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org>
    4  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
    5  * All rights reserved. 
    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. The name of the author may not be used to endorse or promote products
   14  *    derived from this software without specific prior written permission. 
   15  *
   16  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
   17  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
   18  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
   19  * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   20  * EXEMPLARY, OR CONSEQUENTIAL  DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
   22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
   23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
   24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
   25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
   26  */
   28 #include <sys/param.h>
   29 #include <sys/systm.h>
   30 #include <sys/lock.h>
   31 #include <sys/timeout.h>
   32 #include <sys/mutex.h>
   33 #include <sys/queue.h>
   35 #ifdef DDB
   36 #include <machine/db_machdep.h>
   37 #include <ddb/db_interface.h>
   38 #include <ddb/db_access.h>
   39 #include <ddb/db_sym.h>
   40 #include <ddb/db_output.h>
   41 #endif
   43 /*
   44  * Timeouts are kept in a hierarchical timing wheel. The to_time is the value
   45  * of the global variable "ticks" when the timeout should be called. There are
   46  * four levels with 256 buckets each. See 'Scheme 7' in
   47  * "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for
   48  * Implementing a Timer Facility" by George Varghese and Tony Lauck.
   49  */
   50 #define BUCKETS 1024
   51 #define WHEELSIZE 256
   52 #define WHEELMASK 255
   53 #define WHEELBITS 8
   55 struct circq timeout_wheel[BUCKETS];    /* Queues of timeouts */
   56 struct circq timeout_todo;              /* Worklist */
   58 #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK)
   60 #define BUCKET(rel, abs)                                                \
   61     (timeout_wheel[                                                     \
   62         ((rel) <= (1 << (2*WHEELBITS)))                         \
   63             ? ((rel) <= (1 << WHEELBITS))                               \
   64                 ? MASKWHEEL(0, (abs))                                   \
   65                 : MASKWHEEL(1, (abs)) + WHEELSIZE                       \
   66             : ((rel) <= (1 << (3*WHEELBITS)))                           \
   67                 ? MASKWHEEL(2, (abs)) + 2*WHEELSIZE                     \
   68                 : MASKWHEEL(3, (abs)) + 3*WHEELSIZE])
   70 #define MOVEBUCKET(wheel, time)                                         \
CIRCQ_APPEND(&timeout_todo,                                         \
   72         &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE])
   74 /*
   75  * All wheels are locked with the same mutex.
   76  *
   77  * We need locking since the timeouts are manipulated from hardclock that's
   78  * not behind the big lock.
   79  */
   80 struct mutex timeout_mutex = MUTEX_INITIALIZER(IPL_HIGH);
   82 /*
   83  * Circular queue definitions.
   84  */
   86 #define CIRCQ_INIT(elem) do {                   \
   87         (elem)->next = (elem);                  \
   88         (elem)->prev = (elem);                  \
   89 } while (0)
   91 #define CIRCQ_INSERT(elem, list) do {           \
   92         (elem)->prev = (list)->prev;            \
   93         (elem)->next = (list);                  \
   94         (list)->prev->next = (elem);            \
   95         (list)->prev = (elem);                  \
   96 } while (0)
   98 #define CIRCQ_APPEND(fst, snd) do {             \
   99         if (!CIRCQ_EMPTY(snd)) {                \
  100                 (fst)->prev->next = (snd)->next;\
  101                 (snd)->next->prev = (fst)->prev;\
  102                 (snd)->prev->next = (fst);      \
  103                 (fst)->prev = (snd)->prev;      \
CIRCQ_INIT(snd);                \
  105         }                                       \
  106 } while (0)
  108 #define CIRCQ_REMOVE(elem) do {                 \
  109         (elem)->next->prev = (elem)->prev;      \
  110         (elem)->prev->next = (elem)->next;      \
_Q_INVALIDATE((elem)->prev);            \
_Q_INVALIDATE((elem)->next);            \
  113 } while (0)
  115 #define CIRCQ_FIRST(elem) ((elem)->next)
  117 #define CIRCQ_EMPTY(elem) (CIRCQ_FIRST(elem) == (elem))
  119 /*
  120  * Some of the "math" in here is a bit tricky.
  121  *
  122  * We have to beware of wrapping ints.
  123  * We use the fact that any element added to the queue must be added with a
  124  * positive time. That means that any element `to' on the queue cannot be
  125  * scheduled to timeout further in time than INT_MAX, but to->to_time can
  126  * be positive or negative so comparing it with anything is dangerous.
  127  * The only way we can use the to->to_time value in any predictable way
  128  * is when we calculate how far in the future `to' will timeout -
  129  * "to->to_time - ticks". The result will always be positive for future
  130  * timeouts and 0 or negative for due timeouts.
  131  */
  132 extern int ticks;               /* XXX - move to sys/X.h */
  134 void
timeout_startup(void)
  136 {
  137         int b;
CIRCQ_INIT(&timeout_todo);
  140         for (b = 0; b < BUCKETS; b++)
CIRCQ_INIT(&timeout_wheel[b]);
  142 }
  144 void
timeout_set(struct timeout *new, void (*fn)(void *), void *arg)
  146 {
new->to_func = fn;
new->to_arg = arg;
new->to_flags = TIMEOUT_INITIALIZED;
  150 }
  153 void
timeout_add(struct timeout *new, int to_ticks)
  155 {
  156         int old_time;
  158 #ifdef DIAGNOSTIC
  159         if (!(new->to_flags & TIMEOUT_INITIALIZED))
panic("timeout_add: not initialized");
  161         if (to_ticks < 0)
panic("timeout_add: to_ticks (%d) < 0", to_ticks);
  163 #endif
mtx_enter(&timeout_mutex);
  166         /* Initialize the time here, it won't change. */
old_time = new->to_time;
new->to_time = to_ticks + ticks;
new->to_flags &= ~TIMEOUT_TRIGGERED;
  171         /*
  172          * If this timeout already is scheduled and now is moved
  173          * earlier, reschedule it now. Otherwise leave it in place
  174          * and let it be rescheduled later.
  175          */
  176         if (new->to_flags & TIMEOUT_ONQUEUE) {
  177                 if (new->to_time - ticks < old_time - ticks) {
CIRCQ_REMOVE(&new->to_list);
CIRCQ_INSERT(&new->to_list, &timeout_todo);
  180                 }
  181         } else {
new->to_flags |= TIMEOUT_ONQUEUE;
CIRCQ_INSERT(&new->to_list, &timeout_todo);
  184         }
mtx_leave(&timeout_mutex);
  186 }
  188 void
timeout_del(struct timeout *to)
  190 {
mtx_enter(&timeout_mutex);
  192         if (to->to_flags & TIMEOUT_ONQUEUE) {
CIRCQ_REMOVE(&to->to_list);
to->to_flags &= ~TIMEOUT_ONQUEUE;
  195         }
to->to_flags &= ~TIMEOUT_TRIGGERED;
mtx_leave(&timeout_mutex);
  198 }
  200 /*
  201  * This is called from hardclock() once every tick.
  202  * We return !0 if we need to schedule a softclock.
  203  */
  204 int
timeout_hardclock_update(void)
  206 {
  207         int ret;
mtx_enter(&timeout_mutex);
ticks++;
MOVEBUCKET(0, ticks);
  214         if (MASKWHEEL(0, ticks) == 0) {
MOVEBUCKET(1, ticks);
  216                 if (MASKWHEEL(1, ticks) == 0) {
MOVEBUCKET(2, ticks);
  218                         if (MASKWHEEL(2, ticks) == 0)
MOVEBUCKET(3, ticks);
  220                 }
  221         }
ret = !CIRCQ_EMPTY(&timeout_todo);
mtx_leave(&timeout_mutex);
  225         return (ret);
  226 }
  228 void
softclock(void)
  230 {
  231         struct timeout *to;
  232         void (*fn)(void *);
  233         void *arg;
mtx_enter(&timeout_mutex);
  236         while (!CIRCQ_EMPTY(&timeout_todo)) {
to = (struct timeout *)CIRCQ_FIRST(&timeout_todo); /* XXX */
CIRCQ_REMOVE(&to->to_list);
  241                 /* If due run it, otherwise insert it into the right bucket. */
  242                 if (to->to_time - ticks > 0) {
CIRCQ_INSERT(&to->to_list,
  244                             &BUCKET((to->to_time - ticks), to->to_time));
  245                 } else {
  246 #ifdef DEBUG
  247                         if (to->to_time - ticks < 0)
printf("timeout delayed %d\n", to->to_time -
ticks);
  250 #endif
to->to_flags &= ~TIMEOUT_ONQUEUE;
to->to_flags |= TIMEOUT_TRIGGERED;
fn = to->to_func;
arg = to->to_arg;
mtx_leave(&timeout_mutex);
fn(arg);
mtx_enter(&timeout_mutex);
  260                 }
  261         }
mtx_leave(&timeout_mutex);
  263 }
  265 #ifdef DDB
  266 void db_show_callout_bucket(struct circq *);
  268 void
db_show_callout_bucket(struct circq *bucket)
  270 {
  271         struct timeout *to;
  272         struct circq *p;
db_expr_t offset;
  274         char *name;
  276         for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) {
to = (struct timeout *)p; /* XXX */
db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset);
name = name ? name : "?";
db_printf("%9d %2d/%-4d %8x  %s\n", to->to_time - ticks,
  281                     (bucket - timeout_wheel) / WHEELSIZE,
bucket - timeout_wheel, to->to_arg, name);
  283         }
  284 }
  286 void
db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif)
  288 {
  289         int b;
db_printf("ticks now: %d\n", ticks);
db_printf("    ticks  wheel       arg  func\n");
mtx_enter(&timeout_mutex);
db_show_callout_bucket(&timeout_todo);
  296         for (b = 0; b < BUCKETS; b++)
db_show_callout_bucket(&timeout_wheel[b]);
mtx_leave(&timeout_mutex);
  299 }
  300 #endif