1 /* $OpenBSD: kern_timeout.c,v 1.11 2001/09/12 15:48:45 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 54 /* 55 * All lists are locked with the same lock (which must also block out all 56 * interrupts). 57 */ 58 struct simplelock _timeout_lock; 59 60 #define timeout_list_lock(s) \ 61 do { *(s) = splhigh(); simple_lock(&_timeout_lock); } while (0) 62 #define timeout_list_unlock(s) \ 63 do { simple_unlock(&_timeout_lock); splx(s); } while (0) 64 65 /* 66 * Some of the "math" in here is a bit tricky. 67 * 68 * We have to beware of wrapping ints. 69 * We use the fact that any element added to the list must be added with a 70 * positive time. That means that any element `to' on the list cannot be 71 * scheduled to timeout further in time than INT_MAX, but to->to_time can 72 * be positive or negative so comparing it with anything is dangerous. 73 * The only way we can use the to->to_time value in any predictable way 74 * is when we caluculate how far in the future `to' will timeout - 75 *"to->to_time - ticks". The result will always be positive for future 76 * timeouts and 0 or negative for due timeouts. 77 */ 78 extern int ticks; /* XXX - move to sys/X.h */ 79 80 void 81 timeout_startup() 82 { 83 84 TAILQ_INIT(&timeout_todo); 85 simple_lock_init(&_timeout_lock); 86 } 87 88 void 89 timeout_set(new, fn, arg) 90 struct timeout *new; 91 void (*fn)(void *); 92 void *arg; 93 { 94 95 #ifdef DIAGNOSTIC 96 struct timeout *to; 97 int s; 98 99 /* 100 * Be careful. We could be called with random non-zero memory, but 101 * on the other hand we could be called with a timeout that's 102 * already queued. 103 * XXX - this is expensive. 104 */ 105 timeout_list_lock(&s); 106 if (new->to_flags & TIMEOUT_ONQUEUE) { 107 TAILQ_FOREACH(to, &timeout_todo, to_list) 108 if (to == new) 109 panic("timeout_set: on queue"); 110 } 111 timeout_list_unlock(s); 112 #endif 113 114 new->to_func = fn; 115 new->to_arg = arg; 116 new->to_flags = TIMEOUT_INITIALIZED; 117 } 118 119 void 120 timeout_add(new, to_ticks) 121 struct timeout *new; 122 int to_ticks; 123 { 124 struct timeout *to; 125 int s; 126 127 /* 128 * You are supposed to understand this function before you fiddle. 129 */ 130 131 #ifdef DIAGNOSTIC 132 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 133 panic("timeout_add: not initialized"); 134 if (to_ticks < 0) 135 panic("timeout_add: to_ticks < 0"); 136 #endif 137 138 timeout_list_lock(&s); 139 140 /* 141 * First we prepare the new timeout so that we can return right 142 * after the insertion in the queue (makes the code simpler). 143 */ 144 145 /* If this timeout was already on a queue we remove it. */ 146 if (new->to_flags & TIMEOUT_ONQUEUE) 147 TAILQ_REMOVE(&timeout_todo, new, to_list); 148 else 149 new->to_flags |= TIMEOUT_ONQUEUE; 150 /* Initialize the time here, it won't change. */ 151 new->to_time = to_ticks + ticks; 152 new->to_flags &= ~TIMEOUT_TRIGGERED; 153 154 /* 155 * Walk the list of pending timeouts and find an entry which 156 * will timeout after we do, insert the new timeout there. 157 */ 158 TAILQ_FOREACH(to, &timeout_todo, to_list) { 159 if (to->to_time - ticks > to_ticks) { 160 TAILQ_INSERT_BEFORE(to, new, to_list); 161 goto out; 162 } 163 } 164 165 /* We can only get here if we're the last (or only) entry */ 166 TAILQ_INSERT_TAIL(&timeout_todo, new, to_list); 167 out: 168 timeout_list_unlock(s); 169 } 170 171 void 172 timeout_del(to) 173 struct timeout *to; 174 { 175 int s; 176 177 timeout_list_lock(&s); 178 if (to->to_flags & TIMEOUT_ONQUEUE) { 179 TAILQ_REMOVE(&timeout_todo, to, to_list); 180 to->to_flags &= ~TIMEOUT_ONQUEUE; 181 } 182 to->to_flags &= ~TIMEOUT_TRIGGERED; 183 timeout_list_unlock(s); 184 } 185 186 /* 187 * This is called from hardclock() once every tick. 188 * We return !0 if we need to schedule a softclock. 189 * 190 * We don't need locking in here. 191 */ 192 int 193 timeout_hardclock_update() 194 { 195 struct timeout *to; 196 197 to = TAILQ_FIRST(&timeout_todo); 198 199 if (to == NULL) 200 return 0; 201 202 return (to->to_time - ticks <= 0); 203 } 204 205 void 206 softclock() 207 { 208 int s; 209 struct timeout *to; 210 void (*fn) __P((void *)); 211 void *arg; 212 213 timeout_list_lock(&s); 214 while ((to = TAILQ_FIRST(&timeout_todo)) != NULL && 215 to->to_time - ticks <= 0) { 216 #ifdef DIAGNOSTIC 217 if (!(to->to_flags & TIMEOUT_ONQUEUE)) 218 panic("softclock: not onqueue"); 219 #endif 220 TAILQ_REMOVE(&timeout_todo, to, to_list); 221 to->to_flags &= ~TIMEOUT_ONQUEUE; 222 to->to_flags |= TIMEOUT_TRIGGERED; 223 224 fn = to->to_func; 225 arg = to->to_arg; 226 227 timeout_list_unlock(s); 228 fn(arg); 229 timeout_list_lock(&s); 230 } 231 timeout_list_unlock(s); 232 } 233 234 #ifdef DDB 235 void 236 db_show_callout(addr, haddr, count, modif) 237 db_expr_t addr; 238 int haddr; 239 db_expr_t count; 240 char *modif; 241 { 242 struct timeout *to; 243 int s; 244 db_expr_t offset; 245 char *name; 246 247 db_printf("ticks now: %d\n", ticks); 248 db_printf(" ticks arg func\n"); 249 250 timeout_list_lock(&s); 251 252 TAILQ_FOREACH(to, &timeout_todo, to_list) { 253 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 254 255 name = name ? name : "?"; 256 257 db_printf("%9d %8x %s\n", to->to_time, to->to_arg, name); 258 } 259 260 timeout_list_unlock(s); 261 262 } 263 #endif 264