Line data Source code
1 : /* $OpenBSD: kern_timeout.c,v 1.53 2017/12/14 02:42:18 dlg 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/kthread.h>
31 : #include <sys/timeout.h>
32 : #include <sys/mutex.h>
33 : #include <sys/kernel.h>
34 : #include <sys/queue.h> /* _Q_INVALIDATE */
35 :
36 : #ifdef DDB
37 : #include <machine/db_machdep.h>
38 : #include <ddb/db_interface.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 : struct circq timeout_proc; /* Due timeouts needing proc. context */
58 :
59 : #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK)
60 :
61 : #define BUCKET(rel, abs) \
62 : (timeout_wheel[ \
63 : ((rel) <= (1 << (2*WHEELBITS))) \
64 : ? ((rel) <= (1 << WHEELBITS)) \
65 : ? MASKWHEEL(0, (abs)) \
66 : : MASKWHEEL(1, (abs)) + WHEELSIZE \
67 : : ((rel) <= (1 << (3*WHEELBITS))) \
68 : ? MASKWHEEL(2, (abs)) + 2*WHEELSIZE \
69 : : MASKWHEEL(3, (abs)) + 3*WHEELSIZE])
70 :
71 : #define MOVEBUCKET(wheel, time) \
72 : CIRCQ_APPEND(&timeout_todo, \
73 : &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE])
74 :
75 : /*
76 : * The first thing in a struct timeout is its struct circq, so we
77 : * can get back from a pointer to the latter to a pointer to the
78 : * whole timeout with just a cast.
79 : */
80 : static __inline struct timeout *
81 0 : timeout_from_circq(struct circq *p)
82 : {
83 0 : return ((struct timeout *)(p));
84 : }
85 :
86 : /*
87 : * All wheels are locked with the same mutex.
88 : *
89 : * We need locking since the timeouts are manipulated from hardclock that's
90 : * not behind the big lock.
91 : */
92 : struct mutex timeout_mutex = MUTEX_INITIALIZER(IPL_HIGH);
93 :
94 : /*
95 : * Circular queue definitions.
96 : */
97 :
98 : #define CIRCQ_INIT(elem) do { \
99 : (elem)->next = (elem); \
100 : (elem)->prev = (elem); \
101 : } while (0)
102 :
103 : #define CIRCQ_INSERT(elem, list) do { \
104 : (elem)->prev = (list)->prev; \
105 : (elem)->next = (list); \
106 : (list)->prev->next = (elem); \
107 : (list)->prev = (elem); \
108 : } while (0)
109 :
110 : #define CIRCQ_APPEND(fst, snd) do { \
111 : if (!CIRCQ_EMPTY(snd)) { \
112 : (fst)->prev->next = (snd)->next;\
113 : (snd)->next->prev = (fst)->prev;\
114 : (snd)->prev->next = (fst); \
115 : (fst)->prev = (snd)->prev; \
116 : CIRCQ_INIT(snd); \
117 : } \
118 : } while (0)
119 :
120 : #define CIRCQ_REMOVE(elem) do { \
121 : (elem)->next->prev = (elem)->prev; \
122 : (elem)->prev->next = (elem)->next; \
123 : _Q_INVALIDATE((elem)->prev); \
124 : _Q_INVALIDATE((elem)->next); \
125 : } while (0)
126 :
127 : #define CIRCQ_FIRST(elem) ((elem)->next)
128 :
129 : #define CIRCQ_EMPTY(elem) (CIRCQ_FIRST(elem) == (elem))
130 :
131 : void softclock_thread(void *);
132 : void softclock_create_thread(void *);
133 :
134 : /*
135 : * Some of the "math" in here is a bit tricky.
136 : *
137 : * We have to beware of wrapping ints.
138 : * We use the fact that any element added to the queue must be added with a
139 : * positive time. That means that any element `to' on the queue cannot be
140 : * scheduled to timeout further in time than INT_MAX, but to->to_time can
141 : * be positive or negative so comparing it with anything is dangerous.
142 : * The only way we can use the to->to_time value in any predictable way
143 : * is when we calculate how far in the future `to' will timeout -
144 : * "to->to_time - ticks". The result will always be positive for future
145 : * timeouts and 0 or negative for due timeouts.
146 : */
147 :
148 : void
149 0 : timeout_startup(void)
150 : {
151 : int b;
152 :
153 0 : CIRCQ_INIT(&timeout_todo);
154 0 : CIRCQ_INIT(&timeout_proc);
155 0 : for (b = 0; b < nitems(timeout_wheel); b++)
156 0 : CIRCQ_INIT(&timeout_wheel[b]);
157 0 : }
158 :
159 : void
160 0 : timeout_proc_init(void)
161 : {
162 0 : kthread_create_deferred(softclock_create_thread, NULL);
163 0 : }
164 :
165 : void
166 0 : timeout_set(struct timeout *new, void (*fn)(void *), void *arg)
167 : {
168 0 : new->to_func = fn;
169 0 : new->to_arg = arg;
170 0 : new->to_flags = TIMEOUT_INITIALIZED;
171 0 : }
172 :
173 : void
174 0 : timeout_set_proc(struct timeout *new, void (*fn)(void *), void *arg)
175 : {
176 0 : timeout_set(new, fn, arg);
177 0 : new->to_flags |= TIMEOUT_NEEDPROCCTX;
178 0 : }
179 :
180 : int
181 0 : timeout_add(struct timeout *new, int to_ticks)
182 : {
183 : int old_time;
184 : int ret = 1;
185 :
186 : #ifdef DIAGNOSTIC
187 0 : if (!(new->to_flags & TIMEOUT_INITIALIZED))
188 0 : panic("timeout_add: not initialized");
189 0 : if (to_ticks < 0)
190 0 : panic("timeout_add: to_ticks (%d) < 0", to_ticks);
191 : #endif
192 :
193 0 : mtx_enter(&timeout_mutex);
194 : /* Initialize the time here, it won't change. */
195 0 : old_time = new->to_time;
196 0 : new->to_time = to_ticks + ticks;
197 0 : new->to_flags &= ~TIMEOUT_TRIGGERED;
198 :
199 : /*
200 : * If this timeout already is scheduled and now is moved
201 : * earlier, reschedule it now. Otherwise leave it in place
202 : * and let it be rescheduled later.
203 : */
204 0 : if (new->to_flags & TIMEOUT_ONQUEUE) {
205 0 : if (new->to_time - ticks < old_time - ticks) {
206 0 : CIRCQ_REMOVE(&new->to_list);
207 0 : CIRCQ_INSERT(&new->to_list, &timeout_todo);
208 0 : }
209 : ret = 0;
210 0 : } else {
211 0 : new->to_flags |= TIMEOUT_ONQUEUE;
212 0 : CIRCQ_INSERT(&new->to_list, &timeout_todo);
213 : }
214 0 : mtx_leave(&timeout_mutex);
215 :
216 0 : return (ret);
217 : }
218 :
219 : int
220 0 : timeout_add_tv(struct timeout *to, const struct timeval *tv)
221 : {
222 : uint64_t to_ticks;
223 :
224 0 : to_ticks = (uint64_t)hz * tv->tv_sec + tv->tv_usec / tick;
225 0 : if (to_ticks > INT_MAX)
226 : to_ticks = INT_MAX;
227 0 : if (to_ticks == 0 && tv->tv_usec > 0)
228 0 : to_ticks = 1;
229 :
230 0 : return (timeout_add(to, (int)to_ticks));
231 : }
232 :
233 : int
234 0 : timeout_add_ts(struct timeout *to, const struct timespec *ts)
235 : {
236 : uint64_t to_ticks;
237 :
238 0 : to_ticks = (uint64_t)hz * ts->tv_sec + ts->tv_nsec / (tick * 1000);
239 0 : if (to_ticks > INT_MAX)
240 : to_ticks = INT_MAX;
241 0 : if (to_ticks == 0 && ts->tv_nsec > 0)
242 0 : to_ticks = 1;
243 :
244 0 : return (timeout_add(to, (int)to_ticks));
245 : }
246 :
247 : int
248 0 : timeout_add_bt(struct timeout *to, const struct bintime *bt)
249 : {
250 : uint64_t to_ticks;
251 :
252 0 : to_ticks = (uint64_t)hz * bt->sec + (long)(((uint64_t)1000000 *
253 0 : (uint32_t)(bt->frac >> 32)) >> 32) / tick;
254 0 : if (to_ticks > INT_MAX)
255 : to_ticks = INT_MAX;
256 0 : if (to_ticks == 0 && bt->frac > 0)
257 0 : to_ticks = 1;
258 :
259 0 : return (timeout_add(to, (int)to_ticks));
260 : }
261 :
262 : int
263 0 : timeout_add_sec(struct timeout *to, int secs)
264 : {
265 : uint64_t to_ticks;
266 :
267 0 : to_ticks = (uint64_t)hz * secs;
268 0 : if (to_ticks > INT_MAX)
269 : to_ticks = INT_MAX;
270 :
271 0 : return (timeout_add(to, (int)to_ticks));
272 : }
273 :
274 : int
275 0 : timeout_add_msec(struct timeout *to, int msecs)
276 : {
277 : uint64_t to_ticks;
278 :
279 0 : to_ticks = (uint64_t)msecs * 1000 / tick;
280 0 : if (to_ticks > INT_MAX)
281 : to_ticks = INT_MAX;
282 0 : if (to_ticks == 0 && msecs > 0)
283 : to_ticks = 1;
284 :
285 0 : return (timeout_add(to, (int)to_ticks));
286 : }
287 :
288 : int
289 0 : timeout_add_usec(struct timeout *to, int usecs)
290 : {
291 0 : int to_ticks = usecs / tick;
292 :
293 0 : if (to_ticks == 0 && usecs > 0)
294 : to_ticks = 1;
295 :
296 0 : return (timeout_add(to, to_ticks));
297 : }
298 :
299 : int
300 0 : timeout_add_nsec(struct timeout *to, int nsecs)
301 : {
302 0 : int to_ticks = nsecs / (tick * 1000);
303 :
304 0 : if (to_ticks == 0 && nsecs > 0)
305 : to_ticks = 1;
306 :
307 0 : return (timeout_add(to, to_ticks));
308 : }
309 :
310 : int
311 0 : timeout_del(struct timeout *to)
312 : {
313 : int ret = 0;
314 :
315 0 : mtx_enter(&timeout_mutex);
316 0 : if (to->to_flags & TIMEOUT_ONQUEUE) {
317 0 : CIRCQ_REMOVE(&to->to_list);
318 0 : to->to_flags &= ~TIMEOUT_ONQUEUE;
319 : ret = 1;
320 0 : }
321 0 : to->to_flags &= ~TIMEOUT_TRIGGERED;
322 0 : mtx_leave(&timeout_mutex);
323 :
324 0 : return (ret);
325 : }
326 :
327 : void timeout_proc_barrier(void *);
328 :
329 : void
330 0 : timeout_barrier(struct timeout *to)
331 : {
332 0 : if (!ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX)) {
333 0 : KERNEL_LOCK();
334 0 : splx(splsoftclock());
335 0 : KERNEL_UNLOCK();
336 0 : } else {
337 0 : struct cond c = COND_INITIALIZER();
338 0 : struct timeout barrier;
339 :
340 0 : timeout_set_proc(&barrier, timeout_proc_barrier, &c);
341 :
342 0 : mtx_enter(&timeout_mutex);
343 0 : barrier.to_flags |= TIMEOUT_ONQUEUE;
344 0 : CIRCQ_INSERT(&barrier.to_list, &timeout_proc);
345 0 : mtx_leave(&timeout_mutex);
346 :
347 0 : wakeup_one(&timeout_proc);
348 :
349 0 : cond_wait(&c, "tmobar");
350 0 : }
351 0 : }
352 :
353 : void
354 0 : timeout_proc_barrier(void *arg)
355 : {
356 0 : struct cond *c = arg;
357 :
358 0 : cond_signal(c);
359 0 : }
360 :
361 : /*
362 : * This is called from hardclock() once every tick.
363 : * We return !0 if we need to schedule a softclock.
364 : */
365 : int
366 0 : timeout_hardclock_update(void)
367 : {
368 : int ret;
369 :
370 0 : mtx_enter(&timeout_mutex);
371 :
372 0 : MOVEBUCKET(0, ticks);
373 0 : if (MASKWHEEL(0, ticks) == 0) {
374 0 : MOVEBUCKET(1, ticks);
375 0 : if (MASKWHEEL(1, ticks) == 0) {
376 0 : MOVEBUCKET(2, ticks);
377 0 : if (MASKWHEEL(2, ticks) == 0)
378 0 : MOVEBUCKET(3, ticks);
379 : }
380 : }
381 0 : ret = !CIRCQ_EMPTY(&timeout_todo);
382 0 : mtx_leave(&timeout_mutex);
383 :
384 0 : return (ret);
385 : }
386 :
387 : void
388 0 : timeout_run(struct timeout *to)
389 : {
390 : void (*fn)(void *);
391 : void *arg;
392 :
393 0 : MUTEX_ASSERT_LOCKED(&timeout_mutex);
394 :
395 0 : to->to_flags &= ~TIMEOUT_ONQUEUE;
396 0 : to->to_flags |= TIMEOUT_TRIGGERED;
397 :
398 0 : fn = to->to_func;
399 0 : arg = to->to_arg;
400 :
401 0 : mtx_leave(&timeout_mutex);
402 0 : fn(arg);
403 0 : mtx_enter(&timeout_mutex);
404 0 : }
405 :
406 : void
407 0 : softclock(void *arg)
408 : {
409 : int delta;
410 : struct circq *bucket;
411 : struct timeout *to;
412 : int needsproc = 0;
413 :
414 0 : mtx_enter(&timeout_mutex);
415 0 : while (!CIRCQ_EMPTY(&timeout_todo)) {
416 0 : to = timeout_from_circq(CIRCQ_FIRST(&timeout_todo));
417 0 : CIRCQ_REMOVE(&to->to_list);
418 :
419 : /*
420 : * If due run it or defer execution to the thread,
421 : * otherwise insert it into the right bucket.
422 : */
423 0 : delta = to->to_time - ticks;
424 0 : if (delta > 0) {
425 0 : bucket = &BUCKET(delta, to->to_time);
426 0 : CIRCQ_INSERT(&to->to_list, bucket);
427 0 : } else if (to->to_flags & TIMEOUT_NEEDPROCCTX) {
428 0 : CIRCQ_INSERT(&to->to_list, &timeout_proc);
429 : needsproc = 1;
430 0 : } else {
431 : #ifdef DEBUG
432 : if (delta < 0)
433 : printf("timeout delayed %d\n", delta);
434 : #endif
435 0 : timeout_run(to);
436 : }
437 : }
438 0 : mtx_leave(&timeout_mutex);
439 :
440 0 : if (needsproc)
441 0 : wakeup(&timeout_proc);
442 0 : }
443 :
444 : void
445 0 : softclock_create_thread(void *arg)
446 : {
447 0 : if (kthread_create(softclock_thread, NULL, NULL, "softclock"))
448 0 : panic("fork softclock");
449 0 : }
450 :
451 : void
452 0 : softclock_thread(void *arg)
453 : {
454 : CPU_INFO_ITERATOR cii;
455 : struct cpu_info *ci;
456 0 : struct sleep_state sls;
457 : struct timeout *to;
458 :
459 0 : KERNEL_ASSERT_LOCKED();
460 :
461 : /* Be conservative for the moment */
462 0 : CPU_INFO_FOREACH(cii, ci) {
463 0 : if (CPU_IS_PRIMARY(ci))
464 : break;
465 : }
466 0 : KASSERT(ci != NULL);
467 0 : sched_peg_curproc(ci);
468 :
469 0 : for (;;) {
470 0 : sleep_setup(&sls, &timeout_proc, PSWP, "bored");
471 0 : sleep_finish(&sls, CIRCQ_EMPTY(&timeout_proc));
472 :
473 0 : mtx_enter(&timeout_mutex);
474 0 : while (!CIRCQ_EMPTY(&timeout_proc)) {
475 0 : to = timeout_from_circq(CIRCQ_FIRST(&timeout_proc));
476 0 : CIRCQ_REMOVE(&to->to_list);
477 0 : timeout_run(to);
478 : }
479 0 : mtx_leave(&timeout_mutex);
480 : }
481 : }
482 :
483 : #ifndef SMALL_KERNEL
484 : void
485 0 : timeout_adjust_ticks(int adj)
486 : {
487 : struct timeout *to;
488 : struct circq *p;
489 : int new_ticks, b;
490 :
491 : /* adjusting the monotonic clock backwards would be a Bad Thing */
492 0 : if (adj <= 0)
493 0 : return;
494 :
495 0 : mtx_enter(&timeout_mutex);
496 0 : new_ticks = ticks + adj;
497 0 : for (b = 0; b < nitems(timeout_wheel); b++) {
498 0 : p = CIRCQ_FIRST(&timeout_wheel[b]);
499 0 : while (p != &timeout_wheel[b]) {
500 0 : to = timeout_from_circq(p);
501 0 : p = CIRCQ_FIRST(p);
502 :
503 : /* when moving a timeout forward need to reinsert it */
504 0 : if (to->to_time - ticks < adj)
505 0 : to->to_time = new_ticks;
506 0 : CIRCQ_REMOVE(&to->to_list);
507 0 : CIRCQ_INSERT(&to->to_list, &timeout_todo);
508 : }
509 : }
510 0 : ticks = new_ticks;
511 0 : mtx_leave(&timeout_mutex);
512 0 : }
513 : #endif
514 :
515 : #ifdef DDB
516 : void db_show_callout_bucket(struct circq *);
517 :
518 : void
519 0 : db_show_callout_bucket(struct circq *bucket)
520 : {
521 : struct timeout *to;
522 : struct circq *p;
523 0 : db_expr_t offset;
524 0 : char *name;
525 :
526 0 : for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) {
527 0 : to = timeout_from_circq(p);
528 0 : db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset);
529 0 : name = name ? name : "?";
530 0 : db_printf("%9d %2td/%-4td %p %s\n", to->to_time - ticks,
531 0 : (bucket - timeout_wheel) / WHEELSIZE,
532 0 : bucket - timeout_wheel, to->to_arg, name);
533 : }
534 0 : }
535 :
536 : void
537 0 : db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif)
538 : {
539 : int b;
540 :
541 0 : db_printf("ticks now: %d\n", ticks);
542 0 : db_printf(" ticks wheel arg func\n");
543 :
544 0 : db_show_callout_bucket(&timeout_todo);
545 0 : for (b = 0; b < nitems(timeout_wheel); b++)
546 0 : db_show_callout_bucket(&timeout_wheel[b]);
547 0 : }
548 : #endif
|
