Annotation of sys/kern/kern_timeout.c, Revision 1.1.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