1 /* $OpenBSD: kern_timeout.c,v 1.48 2016/07/06 15:53:01 tedu 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/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 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 * The first thing in a struct timeout is its struct circq, so we 76 * can get back from a pointer to the latter to a pointer to the 77 * whole timeout with just a cast. 78 */ 79 static __inline struct timeout * 80 timeout_from_circq(struct circq *p) 81 { 82 return ((struct timeout *)(p)); 83 } 84 85 /* 86 * All wheels are locked with the same mutex. 87 * 88 * We need locking since the timeouts are manipulated from hardclock that's 89 * not behind the big lock. 90 */ 91 struct mutex timeout_mutex = MUTEX_INITIALIZER(IPL_HIGH); 92 93 /* 94 * Circular queue definitions. 95 */ 96 97 #define CIRCQ_INIT(elem) do { \ 98 (elem)->next = (elem); \ 99 (elem)->prev = (elem); \ 100 } while (0) 101 102 #define CIRCQ_INSERT(elem, list) do { \ 103 (elem)->prev = (list)->prev; \ 104 (elem)->next = (list); \ 105 (list)->prev->next = (elem); \ 106 (list)->prev = (elem); \ 107 } while (0) 108 109 #define CIRCQ_APPEND(fst, snd) do { \ 110 if (!CIRCQ_EMPTY(snd)) { \ 111 (fst)->prev->next = (snd)->next;\ 112 (snd)->next->prev = (fst)->prev;\ 113 (snd)->prev->next = (fst); \ 114 (fst)->prev = (snd)->prev; \ 115 CIRCQ_INIT(snd); \ 116 } \ 117 } while (0) 118 119 #define CIRCQ_REMOVE(elem) do { \ 120 (elem)->next->prev = (elem)->prev; \ 121 (elem)->prev->next = (elem)->next; \ 122 _Q_INVALIDATE((elem)->prev); \ 123 _Q_INVALIDATE((elem)->next); \ 124 } while (0) 125 126 #define CIRCQ_FIRST(elem) ((elem)->next) 127 128 #define CIRCQ_EMPTY(elem) (CIRCQ_FIRST(elem) == (elem)) 129 130 /* 131 * Some of the "math" in here is a bit tricky. 132 * 133 * We have to beware of wrapping ints. 134 * We use the fact that any element added to the queue must be added with a 135 * positive time. That means that any element `to' on the queue cannot be 136 * scheduled to timeout further in time than INT_MAX, but to->to_time can 137 * be positive or negative so comparing it with anything is dangerous. 138 * The only way we can use the to->to_time value in any predictable way 139 * is when we calculate how far in the future `to' will timeout - 140 * "to->to_time - ticks". The result will always be positive for future 141 * timeouts and 0 or negative for due timeouts. 142 */ 143 144 void 145 timeout_startup(void) 146 { 147 int b; 148 149 CIRCQ_INIT(&timeout_todo); 150 for (b = 0; b < nitems(timeout_wheel); b++) 151 CIRCQ_INIT(&timeout_wheel[b]); 152 } 153 154 void 155 timeout_set(struct timeout *new, void (*fn)(void *), void *arg) 156 { 157 new->to_func = fn; 158 new->to_arg = arg; 159 new->to_flags = TIMEOUT_INITIALIZED; 160 } 161 162 163 int 164 timeout_add(struct timeout *new, int to_ticks) 165 { 166 int old_time; 167 int ret = 1; 168 169 #ifdef DIAGNOSTIC 170 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 171 panic("timeout_add: not initialized"); 172 if (to_ticks < 0) 173 panic("timeout_add: to_ticks (%d) < 0", to_ticks); 174 #endif 175 176 mtx_enter(&timeout_mutex); 177 /* Initialize the time here, it won't change. */ 178 old_time = new->to_time; 179 new->to_time = to_ticks + ticks; 180 new->to_flags &= ~TIMEOUT_TRIGGERED; 181 182 /* 183 * If this timeout already is scheduled and now is moved 184 * earlier, reschedule it now. Otherwise leave it in place 185 * and let it be rescheduled later. 186 */ 187 if (new->to_flags & TIMEOUT_ONQUEUE) { 188 if (new->to_time - ticks < old_time - ticks) { 189 CIRCQ_REMOVE(&new->to_list); 190 CIRCQ_INSERT(&new->to_list, &timeout_todo); 191 } 192 ret = 0; 193 } else { 194 new->to_flags |= TIMEOUT_ONQUEUE; 195 CIRCQ_INSERT(&new->to_list, &timeout_todo); 196 } 197 mtx_leave(&timeout_mutex); 198 199 return (ret); 200 } 201 202 int 203 timeout_add_tv(struct timeout *to, const struct timeval *tv) 204 { 205 uint64_t to_ticks; 206 207 to_ticks = (uint64_t)hz * tv->tv_sec + tv->tv_usec / tick; 208 if (to_ticks > INT_MAX) 209 to_ticks = INT_MAX; 210 if (to_ticks == 0 && tv->tv_usec > 0) 211 to_ticks = 1; 212 213 return (timeout_add(to, (int)to_ticks)); 214 } 215 216 int 217 timeout_add_ts(struct timeout *to, const struct timespec *ts) 218 { 219 uint64_t to_ticks; 220 221 to_ticks = (uint64_t)hz * ts->tv_sec + ts->tv_nsec / (tick * 1000); 222 if (to_ticks > INT_MAX) 223 to_ticks = INT_MAX; 224 if (to_ticks == 0 && ts->tv_nsec > 0) 225 to_ticks = 1; 226 227 return (timeout_add(to, (int)to_ticks)); 228 } 229 230 int 231 timeout_add_bt(struct timeout *to, const struct bintime *bt) 232 { 233 uint64_t to_ticks; 234 235 to_ticks = (uint64_t)hz * bt->sec + (long)(((uint64_t)1000000 * 236 (uint32_t)(bt->frac >> 32)) >> 32) / tick; 237 if (to_ticks > INT_MAX) 238 to_ticks = INT_MAX; 239 if (to_ticks == 0 && bt->frac > 0) 240 to_ticks = 1; 241 242 return (timeout_add(to, (int)to_ticks)); 243 } 244 245 int 246 timeout_add_sec(struct timeout *to, int secs) 247 { 248 uint64_t to_ticks; 249 250 to_ticks = (uint64_t)hz * secs; 251 if (to_ticks > INT_MAX) 252 to_ticks = INT_MAX; 253 254 return (timeout_add(to, (int)to_ticks)); 255 } 256 257 int 258 timeout_add_msec(struct timeout *to, int msecs) 259 { 260 uint64_t to_ticks; 261 262 to_ticks = (uint64_t)msecs * 1000 / tick; 263 if (to_ticks > INT_MAX) 264 to_ticks = INT_MAX; 265 if (to_ticks == 0 && msecs > 0) 266 to_ticks = 1; 267 268 return (timeout_add(to, (int)to_ticks)); 269 } 270 271 int 272 timeout_add_usec(struct timeout *to, int usecs) 273 { 274 int to_ticks = usecs / tick; 275 276 if (to_ticks == 0 && usecs > 0) 277 to_ticks = 1; 278 279 return (timeout_add(to, to_ticks)); 280 } 281 282 int 283 timeout_add_nsec(struct timeout *to, int nsecs) 284 { 285 int to_ticks = nsecs / (tick * 1000); 286 287 if (to_ticks == 0 && nsecs > 0) 288 to_ticks = 1; 289 290 return (timeout_add(to, to_ticks)); 291 } 292 293 int 294 timeout_del(struct timeout *to) 295 { 296 int ret = 0; 297 298 mtx_enter(&timeout_mutex); 299 if (to->to_flags & TIMEOUT_ONQUEUE) { 300 CIRCQ_REMOVE(&to->to_list); 301 to->to_flags &= ~TIMEOUT_ONQUEUE; 302 ret = 1; 303 } 304 to->to_flags &= ~TIMEOUT_TRIGGERED; 305 mtx_leave(&timeout_mutex); 306 307 return (ret); 308 } 309 310 /* 311 * This is called from hardclock() once every tick. 312 * We return !0 if we need to schedule a softclock. 313 */ 314 int 315 timeout_hardclock_update(void) 316 { 317 int ret; 318 319 mtx_enter(&timeout_mutex); 320 321 MOVEBUCKET(0, ticks); 322 if (MASKWHEEL(0, ticks) == 0) { 323 MOVEBUCKET(1, ticks); 324 if (MASKWHEEL(1, ticks) == 0) { 325 MOVEBUCKET(2, ticks); 326 if (MASKWHEEL(2, ticks) == 0) 327 MOVEBUCKET(3, ticks); 328 } 329 } 330 ret = !CIRCQ_EMPTY(&timeout_todo); 331 mtx_leave(&timeout_mutex); 332 333 return (ret); 334 } 335 336 void 337 softclock(void *arg) 338 { 339 int delta; 340 struct circq *bucket; 341 struct timeout *to; 342 void (*fn)(void *); 343 344 mtx_enter(&timeout_mutex); 345 while (!CIRCQ_EMPTY(&timeout_todo)) { 346 to = timeout_from_circq(CIRCQ_FIRST(&timeout_todo)); 347 CIRCQ_REMOVE(&to->to_list); 348 349 /* If due run it, otherwise insert it into the right bucket. */ 350 delta = to->to_time - ticks; 351 if (delta > 0) { 352 bucket = &BUCKET(delta, to->to_time); 353 CIRCQ_INSERT(&to->to_list, bucket); 354 } else { 355 #ifdef DEBUG 356 if (delta < 0) 357 printf("timeout delayed %d\n", delta); 358 #endif 359 to->to_flags &= ~TIMEOUT_ONQUEUE; 360 to->to_flags |= TIMEOUT_TRIGGERED; 361 362 fn = to->to_func; 363 arg = to->to_arg; 364 365 mtx_leave(&timeout_mutex); 366 fn(arg); 367 mtx_enter(&timeout_mutex); 368 } 369 } 370 mtx_leave(&timeout_mutex); 371 } 372 373 #ifndef SMALL_KERNEL 374 void 375 timeout_adjust_ticks(int adj) 376 { 377 struct timeout *to; 378 struct circq *p; 379 int new_ticks, b; 380 381 /* adjusting the monotonic clock backwards would be a Bad Thing */ 382 if (adj <= 0) 383 return; 384 385 mtx_enter(&timeout_mutex); 386 new_ticks = ticks + adj; 387 for (b = 0; b < nitems(timeout_wheel); b++) { 388 p = CIRCQ_FIRST(&timeout_wheel[b]); 389 while (p != &timeout_wheel[b]) { 390 to = timeout_from_circq(p); 391 p = CIRCQ_FIRST(p); 392 393 /* when moving a timeout forward need to reinsert it */ 394 if (to->to_time - ticks < adj) 395 to->to_time = new_ticks; 396 CIRCQ_REMOVE(&to->to_list); 397 CIRCQ_INSERT(&to->to_list, &timeout_todo); 398 } 399 } 400 ticks = new_ticks; 401 mtx_leave(&timeout_mutex); 402 } 403 #endif 404 405 #ifdef DDB 406 void db_show_callout_bucket(struct circq *); 407 408 void 409 db_show_callout_bucket(struct circq *bucket) 410 { 411 struct timeout *to; 412 struct circq *p; 413 db_expr_t offset; 414 char *name; 415 416 for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) { 417 to = timeout_from_circq(p); 418 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 419 name = name ? name : "?"; 420 db_printf("%9d %2td/%-4td %p %s\n", to->to_time - ticks, 421 (bucket - timeout_wheel) / WHEELSIZE, 422 bucket - timeout_wheel, to->to_arg, name); 423 } 424 } 425 426 void 427 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 428 { 429 int b; 430 431 db_printf("ticks now: %d\n", ticks); 432 db_printf(" ticks wheel arg func\n"); 433 434 db_show_callout_bucket(&timeout_todo); 435 for (b = 0; b < nitems(timeout_wheel); b++) 436 db_show_callout_bucket(&timeout_wheel[b]); 437 } 438 #endif 439