1 /* $OpenBSD: kern_timeout.c,v 1.41 2013/11/27 04:28:32 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/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_access.h> 40 #include <ddb/db_sym.h> 41 #include <ddb/db_output.h> 42 #endif 43 44 /* 45 * Timeouts are kept in a hierarchical timing wheel. The to_time is the value 46 * of the global variable "ticks" when the timeout should be called. There are 47 * four levels with 256 buckets each. See 'Scheme 7' in 48 * "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for 49 * Implementing a Timer Facility" by George Varghese and Tony Lauck. 50 */ 51 #define BUCKETS 1024 52 #define WHEELSIZE 256 53 #define WHEELMASK 255 54 #define WHEELBITS 8 55 56 struct circq timeout_wheel[BUCKETS]; /* Queues of timeouts */ 57 struct circq timeout_todo; /* Worklist */ 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 /* 132 * Some of the "math" in here is a bit tricky. 133 * 134 * We have to beware of wrapping ints. 135 * We use the fact that any element added to the queue must be added with a 136 * positive time. That means that any element `to' on the queue cannot be 137 * scheduled to timeout further in time than INT_MAX, but to->to_time can 138 * be positive or negative so comparing it with anything is dangerous. 139 * The only way we can use the to->to_time value in any predictable way 140 * is when we calculate how far in the future `to' will timeout - 141 * "to->to_time - ticks". The result will always be positive for future 142 * timeouts and 0 or negative for due timeouts. 143 */ 144 extern int ticks; /* XXX - move to sys/X.h */ 145 146 void 147 timeout_startup(void) 148 { 149 int b; 150 151 CIRCQ_INIT(&timeout_todo); 152 for (b = 0; b < nitems(timeout_wheel); b++) 153 CIRCQ_INIT(&timeout_wheel[b]); 154 } 155 156 void 157 timeout_set(struct timeout *new, void (*fn)(void *), void *arg) 158 { 159 new->to_func = fn; 160 new->to_arg = arg; 161 new->to_flags = TIMEOUT_INITIALIZED; 162 } 163 164 165 int 166 timeout_add(struct timeout *new, int to_ticks) 167 { 168 int old_time; 169 int ret = 1; 170 171 #ifdef DIAGNOSTIC 172 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 173 panic("timeout_add: not initialized"); 174 if (to_ticks < 0) 175 panic("timeout_add: to_ticks (%d) < 0", to_ticks); 176 #endif 177 178 mtx_enter(&timeout_mutex); 179 /* Initialize the time here, it won't change. */ 180 old_time = new->to_time; 181 new->to_time = to_ticks + ticks; 182 new->to_flags &= ~TIMEOUT_TRIGGERED; 183 184 /* 185 * If this timeout already is scheduled and now is moved 186 * earlier, reschedule it now. Otherwise leave it in place 187 * and let it be rescheduled later. 188 */ 189 if (new->to_flags & TIMEOUT_ONQUEUE) { 190 if (new->to_time - ticks < old_time - ticks) { 191 CIRCQ_REMOVE(&new->to_list); 192 CIRCQ_INSERT(&new->to_list, &timeout_todo); 193 } 194 ret = 0; 195 } else { 196 new->to_flags |= TIMEOUT_ONQUEUE; 197 CIRCQ_INSERT(&new->to_list, &timeout_todo); 198 } 199 mtx_leave(&timeout_mutex); 200 201 return (ret); 202 } 203 204 int 205 timeout_add_tv(struct timeout *to, const struct timeval *tv) 206 { 207 long long to_ticks; 208 209 to_ticks = (long long)hz * tv->tv_sec + tv->tv_usec / tick; 210 if (to_ticks > INT_MAX) 211 to_ticks = INT_MAX; 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 long long to_ticks; 220 221 to_ticks = (long long)hz * ts->tv_sec + ts->tv_nsec / (tick * 1000); 222 if (to_ticks > INT_MAX) 223 to_ticks = INT_MAX; 224 225 return (timeout_add(to, (int)to_ticks)); 226 } 227 228 int 229 timeout_add_bt(struct timeout *to, const struct bintime *bt) 230 { 231 long long to_ticks; 232 233 to_ticks = (long long)hz * bt->sec + (long)(((uint64_t)1000000 * 234 (uint32_t)(bt->frac >> 32)) >> 32) / tick; 235 if (to_ticks > INT_MAX) 236 to_ticks = INT_MAX; 237 238 return (timeout_add(to, (int)to_ticks)); 239 } 240 241 int 242 timeout_add_sec(struct timeout *to, int secs) 243 { 244 long long to_ticks; 245 246 to_ticks = (long long)hz * secs; 247 if (to_ticks > INT_MAX) 248 to_ticks = INT_MAX; 249 250 return (timeout_add(to, (int)to_ticks)); 251 } 252 253 int 254 timeout_add_msec(struct timeout *to, int msecs) 255 { 256 long long to_ticks; 257 258 to_ticks = (long long)msecs * 1000 / tick; 259 if (to_ticks > INT_MAX) 260 to_ticks = INT_MAX; 261 262 return (timeout_add(to, (int)to_ticks)); 263 } 264 265 int 266 timeout_add_usec(struct timeout *to, int usecs) 267 { 268 int to_ticks = usecs / tick; 269 270 return (timeout_add(to, to_ticks)); 271 } 272 273 int 274 timeout_add_nsec(struct timeout *to, int nsecs) 275 { 276 int to_ticks = nsecs / (tick * 1000); 277 278 return (timeout_add(to, to_ticks)); 279 } 280 281 int 282 timeout_del(struct timeout *to) 283 { 284 int ret = 0; 285 286 mtx_enter(&timeout_mutex); 287 if (to->to_flags & TIMEOUT_ONQUEUE) { 288 CIRCQ_REMOVE(&to->to_list); 289 to->to_flags &= ~TIMEOUT_ONQUEUE; 290 ret = 1; 291 } 292 to->to_flags &= ~TIMEOUT_TRIGGERED; 293 mtx_leave(&timeout_mutex); 294 295 return (ret); 296 } 297 298 /* 299 * This is called from hardclock() once every tick. 300 * We return !0 if we need to schedule a softclock. 301 */ 302 int 303 timeout_hardclock_update(void) 304 { 305 int ret; 306 307 mtx_enter(&timeout_mutex); 308 309 ticks++; 310 311 MOVEBUCKET(0, ticks); 312 if (MASKWHEEL(0, ticks) == 0) { 313 MOVEBUCKET(1, ticks); 314 if (MASKWHEEL(1, ticks) == 0) { 315 MOVEBUCKET(2, ticks); 316 if (MASKWHEEL(2, ticks) == 0) 317 MOVEBUCKET(3, ticks); 318 } 319 } 320 ret = !CIRCQ_EMPTY(&timeout_todo); 321 mtx_leave(&timeout_mutex); 322 323 return (ret); 324 } 325 326 void 327 softclock(void *arg) 328 { 329 struct timeout *to; 330 void (*fn)(void *); 331 332 mtx_enter(&timeout_mutex); 333 while (!CIRCQ_EMPTY(&timeout_todo)) { 334 335 to = timeout_from_circq(CIRCQ_FIRST(&timeout_todo)); 336 CIRCQ_REMOVE(&to->to_list); 337 338 /* If due run it, otherwise insert it into the right bucket. */ 339 if (to->to_time - ticks > 0) { 340 CIRCQ_INSERT(&to->to_list, 341 &BUCKET((to->to_time - ticks), to->to_time)); 342 } else { 343 #ifdef DEBUG 344 if (to->to_time - ticks < 0) 345 printf("timeout delayed %d\n", to->to_time - 346 ticks); 347 #endif 348 to->to_flags &= ~TIMEOUT_ONQUEUE; 349 to->to_flags |= TIMEOUT_TRIGGERED; 350 351 fn = to->to_func; 352 arg = to->to_arg; 353 354 mtx_leave(&timeout_mutex); 355 fn(arg); 356 mtx_enter(&timeout_mutex); 357 } 358 } 359 mtx_leave(&timeout_mutex); 360 } 361 362 #ifndef SMALL_KERNEL 363 void 364 timeout_adjust_ticks(int adj) 365 { 366 struct timeout *to; 367 struct circq *p; 368 int new_ticks, b; 369 370 /* adjusting the monotonic clock backwards would be a Bad Thing */ 371 if (adj <= 0) 372 return; 373 374 mtx_enter(&timeout_mutex); 375 new_ticks = ticks + adj; 376 for (b = 0; b < nitems(timeout_wheel); b++) { 377 p = CIRCQ_FIRST(&timeout_wheel[b]); 378 while (p != &timeout_wheel[b]) { 379 to = timeout_from_circq(p); 380 p = CIRCQ_FIRST(p); 381 382 /* when moving a timeout forward need to reinsert it */ 383 if (to->to_time - ticks < adj) 384 to->to_time = new_ticks; 385 CIRCQ_REMOVE(&to->to_list); 386 CIRCQ_INSERT(&to->to_list, &timeout_todo); 387 } 388 } 389 ticks = new_ticks; 390 mtx_leave(&timeout_mutex); 391 } 392 #endif 393 394 #ifdef DDB 395 void db_show_callout_bucket(struct circq *); 396 397 void 398 db_show_callout_bucket(struct circq *bucket) 399 { 400 struct timeout *to; 401 struct circq *p; 402 db_expr_t offset; 403 char *name; 404 405 for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) { 406 to = timeout_from_circq(p); 407 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 408 name = name ? name : "?"; 409 db_printf("%9d %2td/%-4td %p %s\n", to->to_time - ticks, 410 (bucket - timeout_wheel) / WHEELSIZE, 411 bucket - timeout_wheel, to->to_arg, name); 412 } 413 } 414 415 void 416 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 417 { 418 int b; 419 420 db_printf("ticks now: %d\n", ticks); 421 db_printf(" ticks wheel arg func\n"); 422 423 db_show_callout_bucket(&timeout_todo); 424 for (b = 0; b < nitems(timeout_wheel); b++) 425 db_show_callout_bucket(&timeout_wheel[b]); 426 } 427 #endif 428