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 timeout_from_circq(struct circq *p) 82 { 83 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 timeout_startup(void) 150 { 151 int b; 152 153 CIRCQ_INIT(&timeout_todo); 154 CIRCQ_INIT(&timeout_proc); 155 for (b = 0; b < nitems(timeout_wheel); b++) 156 CIRCQ_INIT(&timeout_wheel[b]); 157 } 158 159 void 160 timeout_proc_init(void) 161 { 162 kthread_create_deferred(softclock_create_thread, NULL); 163 } 164 165 void 166 timeout_set(struct timeout *new, void (*fn)(void *), void *arg) 167 { 168 new->to_func = fn; 169 new->to_arg = arg; 170 new->to_flags = TIMEOUT_INITIALIZED; 171 } 172 173 void 174 timeout_set_proc(struct timeout *new, void (*fn)(void *), void *arg) 175 { 176 timeout_set(new, fn, arg); 177 new->to_flags |= TIMEOUT_NEEDPROCCTX; 178 } 179 180 int 181 timeout_add(struct timeout *new, int to_ticks) 182 { 183 int old_time; 184 int ret = 1; 185 186 #ifdef DIAGNOSTIC 187 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 188 panic("timeout_add: not initialized"); 189 if (to_ticks < 0) 190 panic("timeout_add: to_ticks (%d) < 0", to_ticks); 191 #endif 192 193 mtx_enter(&timeout_mutex); 194 /* Initialize the time here, it won't change. */ 195 old_time = new->to_time; 196 new->to_time = to_ticks + ticks; 197 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 if (new->to_flags & TIMEOUT_ONQUEUE) { 205 if (new->to_time - ticks < old_time - ticks) { 206 CIRCQ_REMOVE(&new->to_list); 207 CIRCQ_INSERT(&new->to_list, &timeout_todo); 208 } 209 ret = 0; 210 } else { 211 new->to_flags |= TIMEOUT_ONQUEUE; 212 CIRCQ_INSERT(&new->to_list, &timeout_todo); 213 } 214 mtx_leave(&timeout_mutex); 215 216 return (ret); 217 } 218 219 int 220 timeout_add_tv(struct timeout *to, const struct timeval *tv) 221 { 222 uint64_t to_ticks; 223 224 to_ticks = (uint64_t)hz * tv->tv_sec + tv->tv_usec / tick; 225 if (to_ticks > INT_MAX) 226 to_ticks = INT_MAX; 227 if (to_ticks == 0 && tv->tv_usec > 0) 228 to_ticks = 1; 229 230 return (timeout_add(to, (int)to_ticks)); 231 } 232 233 int 234 timeout_add_ts(struct timeout *to, const struct timespec *ts) 235 { 236 uint64_t to_ticks; 237 238 to_ticks = (uint64_t)hz * ts->tv_sec + ts->tv_nsec / (tick * 1000); 239 if (to_ticks > INT_MAX) 240 to_ticks = INT_MAX; 241 if (to_ticks == 0 && ts->tv_nsec > 0) 242 to_ticks = 1; 243 244 return (timeout_add(to, (int)to_ticks)); 245 } 246 247 int 248 timeout_add_bt(struct timeout *to, const struct bintime *bt) 249 { 250 uint64_t to_ticks; 251 252 to_ticks = (uint64_t)hz * bt->sec + (long)(((uint64_t)1000000 * 253 (uint32_t)(bt->frac >> 32)) >> 32) / tick; 254 if (to_ticks > INT_MAX) 255 to_ticks = INT_MAX; 256 if (to_ticks == 0 && bt->frac > 0) 257 to_ticks = 1; 258 259 return (timeout_add(to, (int)to_ticks)); 260 } 261 262 int 263 timeout_add_sec(struct timeout *to, int secs) 264 { 265 uint64_t to_ticks; 266 267 to_ticks = (uint64_t)hz * secs; 268 if (to_ticks > INT_MAX) 269 to_ticks = INT_MAX; 270 271 return (timeout_add(to, (int)to_ticks)); 272 } 273 274 int 275 timeout_add_msec(struct timeout *to, int msecs) 276 { 277 uint64_t to_ticks; 278 279 to_ticks = (uint64_t)msecs * 1000 / tick; 280 if (to_ticks > INT_MAX) 281 to_ticks = INT_MAX; 282 if (to_ticks == 0 && msecs > 0) 283 to_ticks = 1; 284 285 return (timeout_add(to, (int)to_ticks)); 286 } 287 288 int 289 timeout_add_usec(struct timeout *to, int usecs) 290 { 291 int to_ticks = usecs / tick; 292 293 if (to_ticks == 0 && usecs > 0) 294 to_ticks = 1; 295 296 return (timeout_add(to, to_ticks)); 297 } 298 299 int 300 timeout_add_nsec(struct timeout *to, int nsecs) 301 { 302 int to_ticks = nsecs / (tick * 1000); 303 304 if (to_ticks == 0 && nsecs > 0) 305 to_ticks = 1; 306 307 return (timeout_add(to, to_ticks)); 308 } 309 310 int 311 timeout_del(struct timeout *to) 312 { 313 int ret = 0; 314 315 mtx_enter(&timeout_mutex); 316 if (to->to_flags & TIMEOUT_ONQUEUE) { 317 CIRCQ_REMOVE(&to->to_list); 318 to->to_flags &= ~TIMEOUT_ONQUEUE; 319 ret = 1; 320 } 321 to->to_flags &= ~TIMEOUT_TRIGGERED; 322 mtx_leave(&timeout_mutex); 323 324 return (ret); 325 } 326 327 void timeout_proc_barrier(void *); 328 329 void 330 timeout_barrier(struct timeout *to) 331 { 332 if (!ISSET(to->to_flags, TIMEOUT_NEEDPROCCTX)) { 333 KERNEL_LOCK(); 334 splx(splsoftclock()); 335 KERNEL_UNLOCK(); 336 } else { 337 struct cond c = COND_INITIALIZER(); 338 struct timeout barrier; 339 340 timeout_set_proc(&barrier, timeout_proc_barrier, &c); 341 342 mtx_enter(&timeout_mutex); 343 barrier.to_flags |= TIMEOUT_ONQUEUE; 344 CIRCQ_INSERT(&barrier.to_list, &timeout_proc); 345 mtx_leave(&timeout_mutex); 346 347 wakeup_one(&timeout_proc); 348 349 cond_wait(&c, "tmobar"); 350 } 351 } 352 353 void 354 timeout_proc_barrier(void *arg) 355 { 356 struct cond *c = arg; 357 358 cond_signal(c); 359 } 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 timeout_hardclock_update(void) 367 { 368 int ret; 369 370 mtx_enter(&timeout_mutex); 371 372 MOVEBUCKET(0, ticks); 373 if (MASKWHEEL(0, ticks) == 0) { 374 MOVEBUCKET(1, ticks); 375 if (MASKWHEEL(1, ticks) == 0) { 376 MOVEBUCKET(2, ticks); 377 if (MASKWHEEL(2, ticks) == 0) 378 MOVEBUCKET(3, ticks); 379 } 380 } 381 ret = !CIRCQ_EMPTY(&timeout_todo); 382 mtx_leave(&timeout_mutex); 383 384 return (ret); 385 } 386 387 void 388 timeout_run(struct timeout *to) 389 { 390 void (*fn)(void *); 391 void *arg; 392 393 MUTEX_ASSERT_LOCKED(&timeout_mutex); 394 395 to->to_flags &= ~TIMEOUT_ONQUEUE; 396 to->to_flags |= TIMEOUT_TRIGGERED; 397 398 fn = to->to_func; 399 arg = to->to_arg; 400 401 mtx_leave(&timeout_mutex); 402 fn(arg); 403 mtx_enter(&timeout_mutex); 404 } 405 406 void 407 softclock(void *arg) 408 { 409 int delta; 410 struct circq *bucket; 411 struct timeout *to; 412 int needsproc = 0; 413 414 mtx_enter(&timeout_mutex); 415 while (!CIRCQ_EMPTY(&timeout_todo)) { 416 to = timeout_from_circq(CIRCQ_FIRST(&timeout_todo)); 417 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 delta = to->to_time - ticks; 424 if (delta > 0) { 425 bucket = &BUCKET(delta, to->to_time); 426 CIRCQ_INSERT(&to->to_list, bucket); 427 } else if (to->to_flags & TIMEOUT_NEEDPROCCTX) { 428 CIRCQ_INSERT(&to->to_list, &timeout_proc); 429 needsproc = 1; 430 } else { 431 #ifdef DEBUG 432 if (delta < 0) 433 printf("timeout delayed %d\n", delta); 434 #endif 435 timeout_run(to); 436 } 437 } 438 mtx_leave(&timeout_mutex); 439 440 if (needsproc) 441 wakeup(&timeout_proc); 442 } 443 444 void 445 softclock_create_thread(void *arg) 446 { 447 if (kthread_create(softclock_thread, NULL, NULL, "softclock")) 448 panic("fork softclock"); 449 } 450 451 void 452 softclock_thread(void *arg) 453 { 454 CPU_INFO_ITERATOR cii; 455 struct cpu_info *ci; 456 struct sleep_state sls; 457 struct timeout *to; 458 459 KERNEL_ASSERT_LOCKED(); 460 461 /* Be conservative for the moment */ 462 CPU_INFO_FOREACH(cii, ci) { 463 if (CPU_IS_PRIMARY(ci)) 464 break; 465 } 466 KASSERT(ci != NULL); 467 sched_peg_curproc(ci); 468 469 for (;;) { 470 sleep_setup(&sls, &timeout_proc, PSWP, "bored"); 471 sleep_finish(&sls, CIRCQ_EMPTY(&timeout_proc)); 472 473 mtx_enter(&timeout_mutex); 474 while (!CIRCQ_EMPTY(&timeout_proc)) { 475 to = timeout_from_circq(CIRCQ_FIRST(&timeout_proc)); 476 CIRCQ_REMOVE(&to->to_list); 477 timeout_run(to); 478 } 479 mtx_leave(&timeout_mutex); 480 } 481 } 482 483 #ifndef SMALL_KERNEL 484 void 485 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 if (adj <= 0) 493 return; 494 495 mtx_enter(&timeout_mutex); 496 new_ticks = ticks + adj; 497 for (b = 0; b < nitems(timeout_wheel); b++) { 498 p = CIRCQ_FIRST(&timeout_wheel[b]); 499 while (p != &timeout_wheel[b]) { 500 to = timeout_from_circq(p); 501 p = CIRCQ_FIRST(p); 502 503 /* when moving a timeout forward need to reinsert it */ 504 if (to->to_time - ticks < adj) 505 to->to_time = new_ticks; 506 CIRCQ_REMOVE(&to->to_list); 507 CIRCQ_INSERT(&to->to_list, &timeout_todo); 508 } 509 } 510 ticks = new_ticks; 511 mtx_leave(&timeout_mutex); 512 } 513 #endif 514 515 #ifdef DDB 516 void db_show_callout_bucket(struct circq *); 517 518 void 519 db_show_callout_bucket(struct circq *bucket) 520 { 521 struct timeout *to; 522 struct circq *p; 523 db_expr_t offset; 524 char *name; 525 526 for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) { 527 to = timeout_from_circq(p); 528 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 529 name = name ? name : "?"; 530 db_printf("%9d %2td/%-4td %p %s\n", to->to_time - ticks, 531 (bucket - timeout_wheel) / WHEELSIZE, 532 bucket - timeout_wheel, to->to_arg, name); 533 } 534 } 535 536 void 537 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 538 { 539 int b; 540 541 db_printf("ticks now: %d\n", ticks); 542 db_printf(" ticks wheel arg func\n"); 543 544 db_show_callout_bucket(&timeout_todo); 545 for (b = 0; b < nitems(timeout_wheel); b++) 546 db_show_callout_bucket(&timeout_wheel[b]); 547 } 548 #endif 549