1 /* $OpenBSD: kern_timeout.c,v 1.8 2001/03/28 07:33:51 art Exp $ */ 2 /* 3 * Copyright (c) 2000 Artur Grabowski <art@openbsd.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. The name of the author may not be used to endorse or promote products 16 * derived from this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 19 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 20 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 21 * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 24 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 26 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 27 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #include <sys/param.h> 31 #include <sys/systm.h> 32 #include <sys/lock.h> 33 #include <sys/timeout.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 on a queue. The to_time is the value of the global 45 * variable "ticks" when the timeout should be called. 46 * 47 * In the future we might want to build a timer wheel to improve the speed 48 * of timeout_add (right now it's linear). See "Redesigning the BSD Callout 49 * and Timer Facilities" by Adam M. Costello and Geroge Varghese. 50 */ 51 52 TAILQ_HEAD(,timeout) timeout_todo; /* Queue of timeouts. */ 53 TAILQ_HEAD(,timeout) timeout_static; /* Static pool of timeouts. */ 54 55 /* 56 * All lists are locked with the same lock (which must also block out all 57 * interrupts). 58 */ 59 struct simplelock _timeout_lock; 60 61 #define timeout_list_lock(s) \ 62 do { *(s) = splhigh(); simple_lock(&_timeout_lock); } while (0) 63 #define timeout_list_unlock(s) \ 64 do { simple_unlock(&_timeout_lock); splx(s); } while (0) 65 66 /* 67 * Some of the "math" in here is a bit tricky. 68 * 69 * We have to beware of wrapping ints. 70 * We use the fact that any element added to the list must be added with a 71 * positive time. That means that any element `to' on the list cannot be 72 * scheduled to timeout further in time than INT_MAX, but to->to_time can 73 * be positive or negative so comparing it with anything is dangerous. 74 * The only way we can use the to->to_time value in any predictable way 75 * is when we caluculate how far in the future `to' will timeout - 76 *"to->to_time - ticks". The result will always be positive for future 77 * timeouts and 0 or negative for due timeouts. 78 */ 79 extern int ticks; /* XXX - move to sys/X.h */ 80 81 void 82 timeout_init() 83 { 84 int i; 85 86 TAILQ_INIT(&timeout_todo); 87 TAILQ_INIT(&timeout_static); 88 simple_lock_init(&_timeout_lock); 89 90 for (i = 0; i < ntimeout; i++) 91 TAILQ_INSERT_HEAD(&timeout_static, &timeouts[i], to_list); 92 } 93 94 void 95 timeout_set(new, fn, arg) 96 struct timeout *new; 97 void (*fn)(void *); 98 void *arg; 99 { 100 101 #ifdef DIAGNOSTIC 102 struct timeout *to; 103 int s; 104 105 /* 106 * Be careful. We could be called with random non-zero memory, but 107 * on the other hand we could be called with a timeout that's 108 * already queued. 109 * XXX - this is expensive. 110 */ 111 timeout_list_lock(&s); 112 if (new->to_flags & TIMEOUT_ONQUEUE) { 113 TAILQ_FOREACH(to, &timeout_todo, to_list) 114 if (to == new) 115 panic("timeout_set: on queue"); 116 } 117 timeout_list_unlock(s); 118 #endif 119 120 new->to_func = fn; 121 new->to_arg = arg; 122 new->to_flags = TIMEOUT_INITIALIZED; 123 } 124 125 void 126 timeout_add(new, to_ticks) 127 struct timeout *new; 128 int to_ticks; 129 { 130 struct timeout *to; 131 int s; 132 133 /* 134 * You are supposed to understand this function before you fiddle. 135 */ 136 137 #ifdef DIAGNOSTIC 138 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 139 panic("timeout_add: not initialized"); 140 if (to_ticks < 0) 141 panic("timeout_add: to_ticks < 0"); 142 #endif 143 144 timeout_list_lock(&s); 145 146 /* 147 * First we prepare the new timeout so that we can return right 148 * after the insertion in the queue (makes the code simpler). 149 */ 150 151 /* If this timeout was already on a queue we remove it. */ 152 if (new->to_flags & TIMEOUT_ONQUEUE) 153 TAILQ_REMOVE(&timeout_todo, new, to_list); 154 else 155 new->to_flags |= TIMEOUT_ONQUEUE; 156 /* Initialize the time here, it won't change. */ 157 new->to_time = to_ticks + ticks; 158 new->to_flags &= ~TIMEOUT_TRIGGERED; 159 160 /* 161 * Walk the list of pending timeouts and find an entry which 162 * will timeout after we do, insert the new timeout there. 163 */ 164 TAILQ_FOREACH(to, &timeout_todo, to_list) { 165 if (to->to_time - ticks > to_ticks) { 166 TAILQ_INSERT_BEFORE(to, new, to_list); 167 goto out; 168 } 169 } 170 171 /* We can only get here if we're the last (or only) entry */ 172 TAILQ_INSERT_TAIL(&timeout_todo, new, to_list); 173 out: 174 timeout_list_unlock(s); 175 } 176 177 void 178 timeout_del(to) 179 struct timeout *to; 180 { 181 int s; 182 183 timeout_list_lock(&s); 184 if (to->to_flags & TIMEOUT_ONQUEUE) { 185 TAILQ_REMOVE(&timeout_todo, to, to_list); 186 to->to_flags &= ~TIMEOUT_ONQUEUE; 187 } 188 to->to_flags &= ~TIMEOUT_TRIGGERED; 189 timeout_list_unlock(s); 190 } 191 192 /* 193 * This is called from hardclock() once every tick. 194 * We return !0 if we need to schedule a softclock. 195 * 196 * We don't need locking in here. 197 */ 198 int 199 timeout_hardclock_update() 200 { 201 struct timeout *to; 202 203 to = TAILQ_FIRST(&timeout_todo); 204 205 if (to == NULL) 206 return 0; 207 208 return (to->to_time - ticks <= 0); 209 } 210 211 void 212 softclock() 213 { 214 int s; 215 struct timeout *to; 216 void (*fn) __P((void *)); 217 void *arg; 218 219 timeout_list_lock(&s); 220 while ((to = TAILQ_FIRST(&timeout_todo)) != NULL && 221 to->to_time - ticks <= 0) { 222 #ifdef DIAGNOSTIC 223 if (!(to->to_flags & TIMEOUT_ONQUEUE)) 224 panic("softclock: not onqueue"); 225 #endif 226 TAILQ_REMOVE(&timeout_todo, to, to_list); 227 to->to_flags &= ~TIMEOUT_ONQUEUE; 228 to->to_flags |= TIMEOUT_TRIGGERED; 229 230 fn = to->to_func; 231 arg = to->to_arg; 232 233 if (to->to_flags & TIMEOUT_STATIC) 234 TAILQ_INSERT_HEAD(&timeout_static, to, to_list); 235 timeout_list_unlock(s); 236 fn(arg); 237 timeout_list_lock(&s); 238 } 239 timeout_list_unlock(s); 240 } 241 242 /* 243 * Legacy interfaces. timeout() and untimeout() 244 * 245 * Kill those when everything is converted. They are slow and use the 246 * static pool (which causes (potential and real) problems). 247 */ 248 249 void 250 timeout(fn, arg, to_ticks) 251 void (*fn) __P((void *)); 252 void *arg; 253 int to_ticks; 254 { 255 struct timeout *to; 256 int s; 257 258 if (to_ticks <= 0) 259 to_ticks = 1; 260 261 /* 262 * Get a timeout struct from the static list. 263 */ 264 timeout_list_lock(&s); 265 266 to = TAILQ_FIRST(&timeout_static); 267 if (to == NULL) 268 panic("timeout table full"); 269 TAILQ_REMOVE(&timeout_static, to, to_list); 270 271 timeout_list_unlock(s); 272 273 timeout_set(to, fn, arg); 274 to->to_flags |= TIMEOUT_STATIC; 275 timeout_add(to, to_ticks); 276 } 277 278 void 279 untimeout(fn, arg) 280 void (*fn) __P((void *)); 281 void *arg; 282 { 283 int s; 284 struct timeout *to; 285 286 timeout_list_lock(&s); 287 TAILQ_FOREACH(to, &timeout_todo, to_list) { 288 if (to->to_func == fn && to->to_arg == arg) { 289 #ifdef DIAGNOSTIC 290 if ((to->to_flags & TIMEOUT_ONQUEUE) == 0) 291 panic("untimeout: not TIMEOUT_ONQUEUE"); 292 if ((to->to_flags & TIMEOUT_STATIC) == 0) 293 panic("untimeout: not static"); 294 #endif 295 TAILQ_REMOVE(&timeout_todo, to, to_list); 296 to->to_flags &= ~TIMEOUT_ONQUEUE; 297 /* return it to the static pool */ 298 TAILQ_INSERT_HEAD(&timeout_static, to, to_list); 299 break; 300 } 301 } 302 timeout_list_unlock(s); 303 } 304 305 #ifdef DDB 306 void 307 db_show_callout(addr, haddr, count, modif) 308 db_expr_t addr; 309 int haddr; 310 db_expr_t count; 311 char *modif; 312 { 313 struct timeout *to; 314 int s; 315 db_expr_t offset; 316 char *name; 317 318 db_printf("ticks now: %d\n", ticks); 319 db_printf(" ticks arg func\n"); 320 321 timeout_list_lock(&s); 322 323 TAILQ_FOREACH(to, &timeout_todo, to_list) { 324 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 325 326 name = name ? name : "?"; 327 328 db_printf("%9d %8x %s\n", to->to_time, to->to_arg, name); 329 } 330 331 timeout_list_unlock(s); 332 333 } 334 #endif 335