The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_timeout.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: kern_timeout.c,v 1.13 2003/10/30 04:32:56 thorpej Exp $        */
    2 
    3 /*-
    4  * Copyright (c) 2003 The NetBSD Foundation, Inc.
    5  * All rights reserved.
    6  *
    7  * This code is derived from software contributed to The NetBSD Foundation
    8  * by Jason R. Thorpe.
    9  *
   10  * Redistribution and use in source and binary forms, with or without
   11  * modification, are permitted provided that the following conditions
   12  * are met:
   13  * 1. Redistributions of source code must retain the above copyright
   14  *    notice, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  * 3. All advertising materials mentioning features or use of this software
   19  *    must display the following acknowledgement:
   20  *      This product includes software developed by the NetBSD
   21  *      Foundation, Inc. and its contributors.
   22  * 4. Neither the name of The NetBSD Foundation nor the names of its
   23  *    contributors may be used to endorse or promote products derived
   24  *    from this software without specific prior written permission.
   25  *
   26  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   27  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   28  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   29  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   30  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   31  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   32  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   33  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   34  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   36  * POSSIBILITY OF SUCH DAMAGE.
   37  */
   38 
   39 /*
   40  * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org>
   41  * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org>
   42  * All rights reserved. 
   43  *
   44  * Redistribution and use in source and binary forms, with or without 
   45  * modification, are permitted provided that the following conditions 
   46  * are met: 
   47  *
   48  * 1. Redistributions of source code must retain the above copyright 
   49  *    notice, this list of conditions and the following disclaimer. 
   50  * 2. Redistributions in binary form must reproduce the above copyright 
   51  *    notice, this list of conditions and the following disclaimer in the 
   52  *    documentation and/or other materials provided with the distribution. 
   53  * 3. The name of the author may not be used to endorse or promote products
   54  *    derived from this software without specific prior written permission. 
   55  *
   56  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
   57  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
   58  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
   59  * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   60  * EXEMPLARY, OR CONSEQUENTIAL  DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   61  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
   62  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
   63  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
   64  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
   65  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
   66  */
   67 
   68 #include <sys/cdefs.h>
   69 __KERNEL_RCSID(0, "$NetBSD: kern_timeout.c,v 1.13 2003/10/30 04:32:56 thorpej Exp $");
   70 
   71 /*
   72  * Adapted from OpenBSD: kern_timeout.c,v 1.15 2002/12/08 04:21:07 art Exp,
   73  * modified to match NetBSD's pre-existing callout API.
   74  */
   75 
   76 #include <sys/param.h>
   77 #include <sys/systm.h>
   78 #include <sys/kernel.h>
   79 #include <sys/lock.h>
   80 #include <sys/callout.h>
   81 
   82 #ifdef DDB
   83 #include <machine/db_machdep.h>
   84 #include <ddb/db_interface.h>
   85 #include <ddb/db_access.h>
   86 #include <ddb/db_sym.h>
   87 #include <ddb/db_output.h>
   88 #endif
   89 
   90 /*
   91  * Timeouts are kept in a hierarchical timing wheel. The c_time is the value
   92  * of the global variable "hardclock_ticks" when the timeout should be called.
   93  * There are four levels with 256 buckets each. See 'Scheme 7' in
   94  * "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for
   95  * Implementing a Timer Facility" by George Varghese and Tony Lauck.
   96  */
   97 #define BUCKETS 1024
   98 #define WHEELSIZE 256
   99 #define WHEELMASK 255
  100 #define WHEELBITS 8
  101 
  102 static struct callout_circq timeout_wheel[BUCKETS];     /* Queues of timeouts */
  103 static struct callout_circq timeout_todo;               /* Worklist */
  104 
  105 #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK)
  106 
  107 #define BUCKET(rel, abs)                                                \
  108     (((rel) <= (1 << (2*WHEELBITS)))                                    \
  109         ? ((rel) <= (1 << WHEELBITS))                                   \
  110             ? &timeout_wheel[MASKWHEEL(0, (abs))]                       \
  111             : &timeout_wheel[MASKWHEEL(1, (abs)) + WHEELSIZE]           \
  112         : ((rel) <= (1 << (3*WHEELBITS)))                               \
  113             ? &timeout_wheel[MASKWHEEL(2, (abs)) + 2*WHEELSIZE]         \
  114             : &timeout_wheel[MASKWHEEL(3, (abs)) + 3*WHEELSIZE])
  115 
  116 #define MOVEBUCKET(wheel, time)                                         \
  117     CIRCQ_APPEND(&timeout_todo,                                         \
  118         &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE])
  119 
  120 /*
  121  * All wheels are locked with the same lock (which must also block out all
  122  * interrupts).
  123  */
  124 static struct simplelock callout_slock;
  125 
  126 #define CALLOUT_LOCK(s)                                                 \
  127 do {                                                                    \
  128         s = splsched();                                                 \
  129         simple_lock(&callout_slock);                                    \
  130 } while (/*CONSTCOND*/0)
  131 
  132 #define CALLOUT_UNLOCK(s)                                               \
  133 do {                                                                    \
  134         simple_unlock(&callout_slock);                                  \
  135         splx((s));                                                      \
  136 } while (/*CONSTCOND*/0)
  137 
  138 /*
  139  * Circular queue definitions.
  140  */
  141 
  142 #define CIRCQ_INIT(list)                                                \
  143 do {                                                                    \
  144         (list)->cq_next_l = (list);                                     \
  145         (list)->cq_prev_l = (list);                                     \
  146 } while (/*CONSTCOND*/0)
  147 
  148 #define CIRCQ_INSERT(elem, list)                                        \
  149 do {                                                                    \
  150         (elem)->cq_prev_e = (list)->cq_prev_e;                          \
  151         (elem)->cq_next_l = (list);                                     \
  152         (list)->cq_prev_l->cq_next_l = (elem);                          \
  153         (list)->cq_prev_l = (elem);                                     \
  154 } while (/*CONSTCOND*/0)
  155 
  156 #define CIRCQ_APPEND(fst, snd)                                          \
  157 do {                                                                    \
  158         if (!CIRCQ_EMPTY(snd)) {                                        \
  159                 (fst)->cq_prev_l->cq_next_l = (snd)->cq_next_l;         \
  160                 (snd)->cq_next_l->cq_prev_l = (fst)->cq_prev_l;         \
  161                 (snd)->cq_prev_l->cq_next_l = (fst);                    \
  162                 (fst)->cq_prev_l = (snd)->cq_prev_l;                    \
  163                 CIRCQ_INIT(snd);                                        \
  164         }                                                               \
  165 } while (/*CONSTCOND*/0)
  166 
  167 #define CIRCQ_REMOVE(elem)                                              \
  168 do {                                                                    \
  169         (elem)->cq_next_l->cq_prev_e = (elem)->cq_prev_e;               \
  170         (elem)->cq_prev_l->cq_next_e = (elem)->cq_next_e;               \
  171 } while (/*CONSTCOND*/0)
  172 
  173 #define CIRCQ_FIRST(list)       ((list)->cq_next_e)
  174 #define CIRCQ_NEXT(elem)        ((elem)->cq_next_e)
  175 #define CIRCQ_LAST(elem,list)   ((elem)->cq_next_l == (list))
  176 #define CIRCQ_EMPTY(list)       ((list)->cq_next_l == (list))
  177 
  178 /*
  179  * Some of the "math" in here is a bit tricky.
  180  *
  181  * We have to beware of wrapping ints.
  182  * We use the fact that any element added to the queue must be added with a
  183  * positive time. That means that any element `to' on the queue cannot be
  184  * scheduled to timeout further in time than INT_MAX, but c->c_time can
  185  * be positive or negative so comparing it with anything is dangerous.
  186  * The only way we can use the c->c_time value in any predictable way
  187  * is when we calculate how far in the future `to' will timeout -
  188  * "c->c_time - hardclock_ticks". The result will always be positive for
  189  * future timeouts and 0 or negative for due timeouts.
  190  */
  191 
  192 #ifdef CALLOUT_EVENT_COUNTERS
  193 static struct evcnt callout_ev_late;
  194 #endif
  195 
  196 /*
  197  * callout_startup:
  198  *
  199  *      Initialize the callout facility, called at system startup time.
  200  */
  201 void
  202 callout_startup(void)
  203 {
  204         int b;
  205 
  206         CIRCQ_INIT(&timeout_todo);
  207         for (b = 0; b < BUCKETS; b++)
  208                 CIRCQ_INIT(&timeout_wheel[b]);
  209         simple_lock_init(&callout_slock);
  210 
  211 #ifdef CALLOUT_EVENT_COUNTERS
  212         evcnt_attach_dynamic(&callout_ev_late, EVCNT_TYPE_MISC,
  213             NULL, "callout", "late");
  214 #endif
  215 }
  216 
  217 /*
  218  * callout_init:
  219  *
  220  *      Initialize a callout structure.
  221  */
  222 void
  223 callout_init(struct callout *c)
  224 {
  225 
  226         memset(c, 0, sizeof(*c));
  227 }
  228 
  229 /*
  230  * callout_reset:
  231  *
  232  *      Reset a callout structure with a new function and argument, and
  233  *      schedule it to run.
  234  */
  235 void
  236 callout_reset(struct callout *c, int to_ticks, void (*func)(void *), void *arg)
  237 {
  238         int s, old_time;
  239 
  240         KASSERT(to_ticks >= 0);
  241 
  242         CALLOUT_LOCK(s);
  243 
  244         /* Initialize the time here, it won't change. */
  245         old_time = c->c_time;
  246         c->c_time = to_ticks + hardclock_ticks;
  247         c->c_flags &= ~(CALLOUT_FIRED|CALLOUT_INVOKING);
  248 
  249         c->c_func = func;
  250         c->c_arg = arg;
  251 
  252         /*
  253          * If this timeout is already scheduled and now is moved
  254          * earlier, reschedule it now. Otherwise leave it in place
  255          * and let it be rescheduled later.
  256          */
  257         if (callout_pending(c)) {
  258                 if (c->c_time - old_time < 0) {
  259                         CIRCQ_REMOVE(&c->c_list);
  260                         CIRCQ_INSERT(&c->c_list, &timeout_todo);
  261                 }
  262         } else {
  263                 c->c_flags |= CALLOUT_PENDING;
  264                 CIRCQ_INSERT(&c->c_list, &timeout_todo);
  265         }
  266 
  267         CALLOUT_UNLOCK(s);
  268 }
  269 
  270 /*
  271  * callout_schedule:
  272  *
  273  *      Schedule a callout to run.  The function and argument must
  274  *      already be set in the callout structure.
  275  */
  276 void
  277 callout_schedule(struct callout *c, int to_ticks)
  278 {
  279         int s, old_time;
  280 
  281         KASSERT(to_ticks >= 0);
  282 
  283         CALLOUT_LOCK(s);
  284 
  285         /* Initialize the time here, it won't change. */
  286         old_time = c->c_time;
  287         c->c_time = to_ticks + hardclock_ticks;
  288         c->c_flags &= ~(CALLOUT_FIRED|CALLOUT_INVOKING);
  289 
  290         /*
  291          * If this timeout is already scheduled and now is moved
  292          * earlier, reschedule it now. Otherwise leave it in place
  293          * and let it be rescheduled later.
  294          */
  295         if (callout_pending(c)) {
  296                 if (c->c_time - old_time < 0) {
  297                         CIRCQ_REMOVE(&c->c_list);
  298                         CIRCQ_INSERT(&c->c_list, &timeout_todo);
  299                 }
  300         } else {
  301                 c->c_flags |= CALLOUT_PENDING;
  302                 CIRCQ_INSERT(&c->c_list, &timeout_todo);
  303         }
  304 
  305         CALLOUT_UNLOCK(s);
  306 }
  307 
  308 /*
  309  * callout_stop:
  310  *
  311  *      Cancel a pending callout.
  312  */
  313 void
  314 callout_stop(struct callout *c)
  315 {
  316         int s;
  317 
  318         CALLOUT_LOCK(s);
  319 
  320         if (callout_pending(c))
  321                 CIRCQ_REMOVE(&c->c_list);
  322 
  323         c->c_flags &= ~(CALLOUT_PENDING|CALLOUT_FIRED);
  324 
  325         CALLOUT_UNLOCK(s);
  326 }
  327 
  328 /*
  329  * This is called from hardclock() once every tick.
  330  * We return !0 if we need to schedule a softclock.
  331  */
  332 int
  333 callout_hardclock(void)
  334 {
  335         int s;
  336         int needsoftclock;
  337 
  338         CALLOUT_LOCK(s);
  339 
  340         MOVEBUCKET(0, hardclock_ticks);
  341         if (MASKWHEEL(0, hardclock_ticks) == 0) {
  342                 MOVEBUCKET(1, hardclock_ticks);
  343                 if (MASKWHEEL(1, hardclock_ticks) == 0) {
  344                         MOVEBUCKET(2, hardclock_ticks);
  345                         if (MASKWHEEL(2, hardclock_ticks) == 0)
  346                                 MOVEBUCKET(3, hardclock_ticks);
  347                 }
  348         }
  349 
  350         needsoftclock = !CIRCQ_EMPTY(&timeout_todo);
  351         CALLOUT_UNLOCK(s);
  352 
  353         return needsoftclock;
  354 }
  355 
  356 /* ARGSUSED */
  357 void
  358 softclock(void *v)
  359 {
  360         struct callout *c;
  361         void (*func)(void *);
  362         void *arg;
  363         int s;
  364 
  365         CALLOUT_LOCK(s);
  366 
  367         while (!CIRCQ_EMPTY(&timeout_todo)) {
  368                 c = CIRCQ_FIRST(&timeout_todo);
  369                 CIRCQ_REMOVE(&c->c_list);
  370 
  371                 /* If due run it, otherwise insert it into the right bucket. */
  372                 if (c->c_time - hardclock_ticks > 0) {
  373                         CIRCQ_INSERT(&c->c_list,
  374                             BUCKET((c->c_time - hardclock_ticks), c->c_time));
  375                 } else {
  376 #ifdef CALLOUT_EVENT_COUNTERS
  377                         if (c->c_time - hardclock_ticks < 0)
  378                                 callout_ev_late.ev_count++;
  379 #endif
  380                         c->c_flags = (c->c_flags  & ~CALLOUT_PENDING) |
  381                             (CALLOUT_FIRED|CALLOUT_INVOKING);
  382 
  383                         func = c->c_func;
  384                         arg = c->c_arg;
  385 
  386                         CALLOUT_UNLOCK(s);
  387                         (*func)(arg);
  388                         CALLOUT_LOCK(s);
  389                 }
  390         }
  391 
  392         CALLOUT_UNLOCK(s);
  393 }
  394 
  395 #ifdef DDB
  396 static void
  397 db_show_callout_bucket(struct callout_circq *bucket)
  398 {
  399         struct callout *c;
  400         db_expr_t offset;
  401         char *name;
  402 
  403         if (CIRCQ_EMPTY(bucket))
  404                 return;
  405 
  406         for (c = CIRCQ_FIRST(bucket); /*nothing*/; c = CIRCQ_NEXT(&c->c_list)) {
  407                 db_find_sym_and_offset((db_addr_t)(intptr_t)c->c_func, &name,
  408                     &offset);
  409                 name = name ? name : "?";
  410 #ifdef _LP64
  411 #define POINTER_WIDTH   "%16lx"
  412 #else
  413 #define POINTER_WIDTH   "%8lx"
  414 #endif
  415                 db_printf("%9d %2d/%-4d " POINTER_WIDTH "  %s\n",
  416                     c->c_time - hardclock_ticks,
  417                     (int)((bucket - timeout_wheel) / WHEELSIZE),
  418                     (int)(bucket - timeout_wheel), (u_long) c->c_arg, name);
  419 
  420                 if (CIRCQ_LAST(&c->c_list, bucket))
  421                         break;
  422         }
  423 }
  424 
  425 void
  426 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif)
  427 {
  428         int b;
  429 
  430         db_printf("hardclock_ticks now: %d\n", hardclock_ticks);
  431 #ifdef _LP64
  432         db_printf("    ticks  wheel               arg  func\n");
  433 #else
  434         db_printf("    ticks  wheel       arg  func\n");
  435 #endif
  436 
  437         /*
  438          * Don't lock the callwheel; all the other CPUs are paused
  439          * anyhow, and we might be called in a circumstance where
  440          * some other CPU was paused while holding the lock.
  441          */
  442 
  443         db_show_callout_bucket(&timeout_todo);
  444         for (b = 0; b < BUCKETS; b++)
  445                 db_show_callout_bucket(&timeout_wheel[b]);
  446 }
  447 #endif /* DDB */

Cache object: ea1a4969a42cd5c18a899b61d810a5f8


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.