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