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