kern_timeout.c revision 1.12
1 /* $NetBSD: kern_timeout.c,v 1.12 2003/10/27 16:52:01 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c) 2003 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 /* 40 * Copyright (c) 2001 Thomas Nordin <nordin (at) openbsd.org> 41 * Copyright (c) 2000-2001 Artur Grabowski <art (at) openbsd.org> 42 * All rights reserved. 43 * 44 * Redistribution and use in source and binary forms, with or without 45 * modification, are permitted provided that the following conditions 46 * are met: 47 * 48 * 1. Redistributions of source code must retain the above copyright 49 * notice, this list of conditions and the following disclaimer. 50 * 2. Redistributions in binary form must reproduce the above copyright 51 * notice, this list of conditions and the following disclaimer in the 52 * documentation and/or other materials provided with the distribution. 53 * 3. The name of the author may not be used to endorse or promote products 54 * derived from this software without specific prior written permission. 55 * 56 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 57 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 58 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 59 * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 60 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 61 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 62 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 63 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 64 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 65 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 66 */ 67 68 #include <sys/cdefs.h> 69 __KERNEL_RCSID(0, "$NetBSD: kern_timeout.c,v 1.12 2003/10/27 16:52:01 thorpej Exp $"); 70 71 /* 72 * Adapted from OpenBSD: kern_timeout.c,v 1.15 2002/12/08 04:21:07 art Exp, 73 * modified to match NetBSD's pre-existing callout API. 74 */ 75 76 #include <sys/param.h> 77 #include <sys/systm.h> 78 #include <sys/kernel.h> 79 #include <sys/lock.h> 80 #include <sys/callout.h> 81 82 #ifdef DDB 83 #include <machine/db_machdep.h> 84 #include <ddb/db_interface.h> 85 #include <ddb/db_access.h> 86 #include <ddb/db_sym.h> 87 #include <ddb/db_output.h> 88 #endif 89 90 /* 91 * Timeouts are kept in a hierarchical timing wheel. The c_time is the value 92 * of the global variable "hardclock_ticks" when the timeout should be called. 93 * There are four levels with 256 buckets each. See 'Scheme 7' in 94 * "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for 95 * Implementing a Timer Facility" by George Varghese and Tony Lauck. 96 */ 97 #define BUCKETS 1024 98 #define WHEELSIZE 256 99 #define WHEELMASK 255 100 #define WHEELBITS 8 101 102 static struct callout_circq timeout_wheel[BUCKETS]; /* Queues of timeouts */ 103 static struct callout_circq timeout_todo; /* Worklist */ 104 105 #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK) 106 107 #define BUCKET(rel, abs) \ 108 (((rel) <= (1 << (2*WHEELBITS))) \ 109 ? ((rel) <= (1 << WHEELBITS)) \ 110 ? &timeout_wheel[MASKWHEEL(0, (abs))] \ 111 : &timeout_wheel[MASKWHEEL(1, (abs)) + WHEELSIZE] \ 112 : ((rel) <= (1 << (3*WHEELBITS))) \ 113 ? &timeout_wheel[MASKWHEEL(2, (abs)) + 2*WHEELSIZE] \ 114 : &timeout_wheel[MASKWHEEL(3, (abs)) + 3*WHEELSIZE]) 115 116 #define MOVEBUCKET(wheel, time) \ 117 CIRCQ_APPEND(&timeout_todo, \ 118 &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE]) 119 120 /* 121 * All wheels are locked with the same lock (which must also block out all 122 * interrupts). 123 */ 124 static struct simplelock callout_slock; 125 126 #define CALLOUT_LOCK(s) \ 127 do { \ 128 s = splsched(); \ 129 simple_lock(&callout_slock); \ 130 } while (/*CONSTCOND*/0) 131 132 #define CALLOUT_UNLOCK(s) \ 133 do { \ 134 simple_unlock(&callout_slock); \ 135 splx((s)); \ 136 } while (/*CONSTCOND*/0) 137 138 /* 139 * Circular queue definitions. 140 */ 141 142 #define CIRCQ_INIT(list) \ 143 do { \ 144 (list)->cq_next_l = (list); \ 145 (list)->cq_prev_l = (list); \ 146 } while (/*CONSTCOND*/0) 147 148 #define CIRCQ_INSERT(elem, list) \ 149 do { \ 150 (elem)->cq_prev_e = (list)->cq_prev_e; \ 151 (elem)->cq_next_l = (list); \ 152 (list)->cq_prev_l->cq_next_l = (elem); \ 153 (list)->cq_prev_l = (elem); \ 154 } while (/*CONSTCOND*/0) 155 156 #define CIRCQ_APPEND(fst, snd) \ 157 do { \ 158 if (!CIRCQ_EMPTY(snd)) { \ 159 (fst)->cq_prev_l->cq_next_l = (snd)->cq_next_l; \ 160 (snd)->cq_next_l->cq_prev_l = (fst)->cq_prev_l; \ 161 (snd)->cq_prev_l->cq_next_l = (fst); \ 162 (fst)->cq_prev_l = (snd)->cq_prev_l; \ 163 CIRCQ_INIT(snd); \ 164 } \ 165 } while (/*CONSTCOND*/0) 166 167 #define CIRCQ_REMOVE(elem) \ 168 do { \ 169 (elem)->cq_next_l->cq_prev_e = (elem)->cq_prev_e; \ 170 (elem)->cq_prev_l->cq_next_e = (elem)->cq_next_e; \ 171 } while (/*CONSTCOND*/0) 172 173 #define CIRCQ_FIRST(list) ((list)->cq_next_e) 174 #define CIRCQ_NEXT(elem) ((elem)->cq_next_e) 175 #define CIRCQ_LAST(elem,list) ((elem)->cq_next_l == (list)) 176 #define CIRCQ_EMPTY(list) ((list)->cq_next_l == (list)) 177 178 /* 179 * Some of the "math" in here is a bit tricky. 180 * 181 * We have to beware of wrapping ints. 182 * We use the fact that any element added to the queue must be added with a 183 * positive time. That means that any element `to' on the queue cannot be 184 * scheduled to timeout further in time than INT_MAX, but c->c_time can 185 * be positive or negative so comparing it with anything is dangerous. 186 * The only way we can use the c->c_time value in any predictable way 187 * is when we calculate how far in the future `to' will timeout - 188 * "c->c_time - hardclock_ticks". The result will always be positive for 189 * future timeouts and 0 or negative for due timeouts. 190 */ 191 192 #ifdef CALLOUT_EVENT_COUNTERS 193 static struct evcnt callout_ev_late; 194 #endif 195 196 /* 197 * callout_startup: 198 * 199 * Initialize the callout facility, called at system startup time. 200 */ 201 void 202 callout_startup(void) 203 { 204 int b; 205 206 CIRCQ_INIT(&timeout_todo); 207 for (b = 0; b < BUCKETS; b++) 208 CIRCQ_INIT(&timeout_wheel[b]); 209 simple_lock_init(&callout_slock); 210 211 #ifdef CALLOUT_EVENT_COUNTERS 212 evcnt_attach_dynamic(&callout_ev_late, EVCNT_TYPE_MISC, 213 NULL, "callout", "late"); 214 #endif 215 } 216 217 /* 218 * callout_init: 219 * 220 * Initialize a callout structure. 221 */ 222 void 223 callout_init(struct callout *c) 224 { 225 226 memset(c, 0, sizeof(*c)); 227 } 228 229 /* 230 * callout_setfunc: 231 * 232 * Initialize a callout structure and set the function and 233 * argument. 234 * 235 * NOTE: THE CALLOUT STRUCTURE MUST ALREADY BE INITIALIZED! 236 */ 237 void 238 callout_setfunc(struct callout *c, void (*func)(void *), void *arg) 239 { 240 241 c->c_func = func; 242 c->c_arg = arg; 243 } 244 245 /* 246 * callout_reset: 247 * 248 * Reset a callout structure with a new function and argument, and 249 * schedule it to run. 250 */ 251 void 252 callout_reset(struct callout *c, int to_ticks, void (*func)(void *), void *arg) 253 { 254 int s, old_time; 255 256 KASSERT(to_ticks >= 0); 257 258 CALLOUT_LOCK(s); 259 260 /* Initialize the time here, it won't change. */ 261 old_time = c->c_time; 262 c->c_time = to_ticks + hardclock_ticks; 263 c->c_flags &= ~(CALLOUT_FIRED|CALLOUT_INVOKING); 264 265 c->c_func = func; 266 c->c_arg = arg; 267 268 /* 269 * If this timeout is already scheduled and now is moved 270 * earlier, reschedule it now. Otherwise leave it in place 271 * and let it be rescheduled later. 272 */ 273 if (callout_pending(c)) { 274 if (c->c_time - old_time < 0) { 275 CIRCQ_REMOVE(&c->c_list); 276 CIRCQ_INSERT(&c->c_list, &timeout_todo); 277 } 278 } else { 279 c->c_flags |= CALLOUT_PENDING; 280 CIRCQ_INSERT(&c->c_list, &timeout_todo); 281 } 282 283 CALLOUT_UNLOCK(s); 284 } 285 286 /* 287 * callout_schedule: 288 * 289 * Schedule a callout to run. The function and argument must 290 * already be set in the callout structure. 291 */ 292 void 293 callout_schedule(struct callout *c, int to_ticks) 294 { 295 int s, old_time; 296 297 KASSERT(to_ticks >= 0); 298 299 CALLOUT_LOCK(s); 300 301 /* Initialize the time here, it won't change. */ 302 old_time = c->c_time; 303 c->c_time = to_ticks + hardclock_ticks; 304 c->c_flags &= ~(CALLOUT_FIRED|CALLOUT_INVOKING); 305 306 /* 307 * If this timeout is already scheduled and now is moved 308 * earlier, reschedule it now. Otherwise leave it in place 309 * and let it be rescheduled later. 310 */ 311 if (callout_pending(c)) { 312 if (c->c_time - old_time < 0) { 313 CIRCQ_REMOVE(&c->c_list); 314 CIRCQ_INSERT(&c->c_list, &timeout_todo); 315 } 316 } else { 317 c->c_flags |= CALLOUT_PENDING; 318 CIRCQ_INSERT(&c->c_list, &timeout_todo); 319 } 320 321 CALLOUT_UNLOCK(s); 322 } 323 324 /* 325 * callout_stop: 326 * 327 * Cancel a pending callout. 328 */ 329 void 330 callout_stop(struct callout *c) 331 { 332 int s; 333 334 CALLOUT_LOCK(s); 335 336 if (callout_pending(c)) 337 CIRCQ_REMOVE(&c->c_list); 338 339 c->c_flags &= ~(CALLOUT_PENDING|CALLOUT_FIRED); 340 341 CALLOUT_UNLOCK(s); 342 } 343 344 /* 345 * This is called from hardclock() once every tick. 346 * We return !0 if we need to schedule a softclock. 347 */ 348 int 349 callout_hardclock(void) 350 { 351 int s; 352 int needsoftclock; 353 354 CALLOUT_LOCK(s); 355 356 MOVEBUCKET(0, hardclock_ticks); 357 if (MASKWHEEL(0, hardclock_ticks) == 0) { 358 MOVEBUCKET(1, hardclock_ticks); 359 if (MASKWHEEL(1, hardclock_ticks) == 0) { 360 MOVEBUCKET(2, hardclock_ticks); 361 if (MASKWHEEL(2, hardclock_ticks) == 0) 362 MOVEBUCKET(3, hardclock_ticks); 363 } 364 } 365 366 needsoftclock = !CIRCQ_EMPTY(&timeout_todo); 367 CALLOUT_UNLOCK(s); 368 369 return needsoftclock; 370 } 371 372 /* ARGSUSED */ 373 void 374 softclock(void *v) 375 { 376 struct callout *c; 377 void (*func)(void *); 378 void *arg; 379 int s; 380 381 CALLOUT_LOCK(s); 382 383 while (!CIRCQ_EMPTY(&timeout_todo)) { 384 c = CIRCQ_FIRST(&timeout_todo); 385 CIRCQ_REMOVE(&c->c_list); 386 387 /* If due run it, otherwise insert it into the right bucket. */ 388 if (c->c_time - hardclock_ticks > 0) { 389 CIRCQ_INSERT(&c->c_list, 390 BUCKET((c->c_time - hardclock_ticks), c->c_time)); 391 } else { 392 #ifdef CALLOUT_EVENT_COUNTERS 393 if (c->c_time - hardclock_ticks < 0) 394 callout_ev_late.ev_count++; 395 #endif 396 c->c_flags = (c->c_flags & ~CALLOUT_PENDING) | 397 (CALLOUT_FIRED|CALLOUT_INVOKING); 398 399 func = c->c_func; 400 arg = c->c_arg; 401 402 CALLOUT_UNLOCK(s); 403 (*func)(arg); 404 CALLOUT_LOCK(s); 405 } 406 } 407 408 CALLOUT_UNLOCK(s); 409 } 410 411 #ifdef DDB 412 static void 413 db_show_callout_bucket(struct callout_circq *bucket) 414 { 415 struct callout *c; 416 db_expr_t offset; 417 char *name; 418 419 if (CIRCQ_EMPTY(bucket)) 420 return; 421 422 for (c = CIRCQ_FIRST(bucket); /*nothing*/; c = CIRCQ_NEXT(&c->c_list)) { 423 db_find_sym_and_offset((db_addr_t)(intptr_t)c->c_func, &name, 424 &offset); 425 name = name ? name : "?"; 426 #ifdef _LP64 427 #define POINTER_WIDTH "%16lx" 428 #else 429 #define POINTER_WIDTH "%8lx" 430 #endif 431 db_printf("%9d %2d/%-4d " POINTER_WIDTH " %s\n", 432 c->c_time - hardclock_ticks, 433 (int)((bucket - timeout_wheel) / WHEELSIZE), 434 (int)(bucket - timeout_wheel), (u_long) c->c_arg, name); 435 436 if (CIRCQ_LAST(&c->c_list, bucket)) 437 break; 438 } 439 } 440 441 void 442 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 443 { 444 int b; 445 446 db_printf("hardclock_ticks now: %d\n", hardclock_ticks); 447 #ifdef _LP64 448 db_printf(" ticks wheel arg func\n"); 449 #else 450 db_printf(" ticks wheel arg func\n"); 451 #endif 452 453 /* 454 * Don't lock the callwheel; all the other CPUs are paused 455 * anyhow, and we might be called in a circumstance where 456 * some other CPU was paused while holding the lock. 457 */ 458 459 db_show_callout_bucket(&timeout_todo); 460 for (b = 0; b < BUCKETS; b++) 461 db_show_callout_bucket(&timeout_wheel[b]); 462 } 463 #endif /* DDB */ 464
Indexes created Sat Sep 20 22:09:52 GMT 2025