1 /* $NetBSD: kern_timeout.c,v 1.14 2005/02/26 21:34:55 perry 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.14 2005/02/26 21:34:55 perry 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: 5b76377e593a8ecb34234bcf251e7467
|