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