Annotation of sys/kern/kern_timeout.c, Revision 1.1
1.1 ! nbrk 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: */
! 27:
! 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>
! 34:
! 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
! 42:
! 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
! 54:
! 55: struct circq timeout_wheel[BUCKETS]; /* Queues of timeouts */
! 56: struct circq timeout_todo; /* Worklist */
! 57:
! 58: #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK)
! 59:
! 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])
! 69:
! 70: #define MOVEBUCKET(wheel, time) \
! 71: CIRCQ_APPEND(&timeout_todo, \
! 72: &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE])
! 73:
! 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);
! 81:
! 82: /*
! 83: * Circular queue definitions.
! 84: */
! 85:
! 86: #define CIRCQ_INIT(elem) do { \
! 87: (elem)->next = (elem); \
! 88: (elem)->prev = (elem); \
! 89: } while (0)
! 90:
! 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)
! 97:
! 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; \
! 104: CIRCQ_INIT(snd); \
! 105: } \
! 106: } while (0)
! 107:
! 108: #define CIRCQ_REMOVE(elem) do { \
! 109: (elem)->next->prev = (elem)->prev; \
! 110: (elem)->prev->next = (elem)->next; \
! 111: _Q_INVALIDATE((elem)->prev); \
! 112: _Q_INVALIDATE((elem)->next); \
! 113: } while (0)
! 114:
! 115: #define CIRCQ_FIRST(elem) ((elem)->next)
! 116:
! 117: #define CIRCQ_EMPTY(elem) (CIRCQ_FIRST(elem) == (elem))
! 118:
! 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 */
! 133:
! 134: void
! 135: timeout_startup(void)
! 136: {
! 137: int b;
! 138:
! 139: CIRCQ_INIT(&timeout_todo);
! 140: for (b = 0; b < BUCKETS; b++)
! 141: CIRCQ_INIT(&timeout_wheel[b]);
! 142: }
! 143:
! 144: void
! 145: timeout_set(struct timeout *new, void (*fn)(void *), void *arg)
! 146: {
! 147: new->to_func = fn;
! 148: new->to_arg = arg;
! 149: new->to_flags = TIMEOUT_INITIALIZED;
! 150: }
! 151:
! 152:
! 153: void
! 154: timeout_add(struct timeout *new, int to_ticks)
! 155: {
! 156: int old_time;
! 157:
! 158: #ifdef DIAGNOSTIC
! 159: if (!(new->to_flags & TIMEOUT_INITIALIZED))
! 160: panic("timeout_add: not initialized");
! 161: if (to_ticks < 0)
! 162: panic("timeout_add: to_ticks (%d) < 0", to_ticks);
! 163: #endif
! 164:
! 165: mtx_enter(&timeout_mutex);
! 166: /* Initialize the time here, it won't change. */
! 167: old_time = new->to_time;
! 168: new->to_time = to_ticks + ticks;
! 169: new->to_flags &= ~TIMEOUT_TRIGGERED;
! 170:
! 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) {
! 178: CIRCQ_REMOVE(&new->to_list);
! 179: CIRCQ_INSERT(&new->to_list, &timeout_todo);
! 180: }
! 181: } else {
! 182: new->to_flags |= TIMEOUT_ONQUEUE;
! 183: CIRCQ_INSERT(&new->to_list, &timeout_todo);
! 184: }
! 185: mtx_leave(&timeout_mutex);
! 186: }
! 187:
! 188: void
! 189: timeout_del(struct timeout *to)
! 190: {
! 191: mtx_enter(&timeout_mutex);
! 192: if (to->to_flags & TIMEOUT_ONQUEUE) {
! 193: CIRCQ_REMOVE(&to->to_list);
! 194: to->to_flags &= ~TIMEOUT_ONQUEUE;
! 195: }
! 196: to->to_flags &= ~TIMEOUT_TRIGGERED;
! 197: mtx_leave(&timeout_mutex);
! 198: }
! 199:
! 200: /*
! 201: * This is called from hardclock() once every tick.
! 202: * We return !0 if we need to schedule a softclock.
! 203: */
! 204: int
! 205: timeout_hardclock_update(void)
! 206: {
! 207: int ret;
! 208:
! 209: mtx_enter(&timeout_mutex);
! 210:
! 211: ticks++;
! 212:
! 213: MOVEBUCKET(0, ticks);
! 214: if (MASKWHEEL(0, ticks) == 0) {
! 215: MOVEBUCKET(1, ticks);
! 216: if (MASKWHEEL(1, ticks) == 0) {
! 217: MOVEBUCKET(2, ticks);
! 218: if (MASKWHEEL(2, ticks) == 0)
! 219: MOVEBUCKET(3, ticks);
! 220: }
! 221: }
! 222: ret = !CIRCQ_EMPTY(&timeout_todo);
! 223: mtx_leave(&timeout_mutex);
! 224:
! 225: return (ret);
! 226: }
! 227:
! 228: void
! 229: softclock(void)
! 230: {
! 231: struct timeout *to;
! 232: void (*fn)(void *);
! 233: void *arg;
! 234:
! 235: mtx_enter(&timeout_mutex);
! 236: while (!CIRCQ_EMPTY(&timeout_todo)) {
! 237:
! 238: to = (struct timeout *)CIRCQ_FIRST(&timeout_todo); /* XXX */
! 239: CIRCQ_REMOVE(&to->to_list);
! 240:
! 241: /* If due run it, otherwise insert it into the right bucket. */
! 242: if (to->to_time - ticks > 0) {
! 243: 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)
! 248: printf("timeout delayed %d\n", to->to_time -
! 249: ticks);
! 250: #endif
! 251: to->to_flags &= ~TIMEOUT_ONQUEUE;
! 252: to->to_flags |= TIMEOUT_TRIGGERED;
! 253:
! 254: fn = to->to_func;
! 255: arg = to->to_arg;
! 256:
! 257: mtx_leave(&timeout_mutex);
! 258: fn(arg);
! 259: mtx_enter(&timeout_mutex);
! 260: }
! 261: }
! 262: mtx_leave(&timeout_mutex);
! 263: }
! 264:
! 265: #ifdef DDB
! 266: void db_show_callout_bucket(struct circq *);
! 267:
! 268: void
! 269: db_show_callout_bucket(struct circq *bucket)
! 270: {
! 271: struct timeout *to;
! 272: struct circq *p;
! 273: db_expr_t offset;
! 274: char *name;
! 275:
! 276: for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) {
! 277: to = (struct timeout *)p; /* XXX */
! 278: db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset);
! 279: name = name ? name : "?";
! 280: db_printf("%9d %2d/%-4d %8x %s\n", to->to_time - ticks,
! 281: (bucket - timeout_wheel) / WHEELSIZE,
! 282: bucket - timeout_wheel, to->to_arg, name);
! 283: }
! 284: }
! 285:
! 286: void
! 287: db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif)
! 288: {
! 289: int b;
! 290:
! 291: db_printf("ticks now: %d\n", ticks);
! 292: db_printf(" ticks wheel arg func\n");
! 293:
! 294: mtx_enter(&timeout_mutex);
! 295: db_show_callout_bucket(&timeout_todo);
! 296: for (b = 0; b < BUCKETS; b++)
! 297: db_show_callout_bucket(&timeout_wheel[b]);
! 298: mtx_leave(&timeout_mutex);
! 299: }
! 300: #endif
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to kern_timeout.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / kern