1 /* $OpenBSD: kern_timeout.c,v 1.14 2002/03/14 01:27:04 millert 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. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. The name of the author may not be used to endorse or promote products 17 * derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 21 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 22 * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 25 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 27 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 28 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include <sys/param.h> 32 #include <sys/systm.h> 33 #include <sys/lock.h> 34 #include <sys/timeout.h> 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 (((rel) <= (1 << (2*WHEELBITS))) \ 63 ? ((rel) <= (1 << WHEELBITS)) \ 64 ? timeout_wheel[MASKWHEEL(0, (abs))] \ 65 : timeout_wheel[MASKWHEEL(1, (abs)) + WHEELSIZE] \ 66 : ((rel) <= (1 << (3*WHEELBITS))) \ 67 ? timeout_wheel[MASKWHEEL(2, (abs)) + 2*WHEELSIZE] \ 68 : timeout_wheel[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 lock (which must also block out all 76 * interrupts). 77 */ 78 struct simplelock _timeout_lock; 79 80 #define timeout_wheel_lock(s) \ 81 do { *(s) = splhigh(); simple_lock(&_timeout_lock); } while (0) 82 #define timeout_wheel_unlock(s) \ 83 do { simple_unlock(&_timeout_lock); splx(s); } while (0) 84 85 /* 86 * Circular queue definitions. 87 */ 88 89 #define CIRCQ_INIT(elem) do { \ 90 (elem)->next = (elem); \ 91 (elem)->prev = (elem); \ 92 } while (0) 93 94 #define CIRCQ_INSERT(elem, list) do { \ 95 (elem)->prev = (list)->prev; \ 96 (elem)->next = (list); \ 97 (list)->prev->next = (elem); \ 98 (list)->prev = (elem); \ 99 } while (0) 100 101 #define CIRCQ_APPEND(fst, snd) do { \ 102 if (!CIRCQ_EMPTY(snd)) { \ 103 (fst)->prev->next = (snd)->next;\ 104 (snd)->next->prev = (fst)->prev;\ 105 (snd)->prev->next = (fst); \ 106 (fst)->prev = (snd)->prev; \ 107 CIRCQ_INIT(snd); \ 108 } \ 109 } while (0) 110 111 #define CIRCQ_REMOVE(elem) do { \ 112 (elem)->next->prev = (elem)->prev; \ 113 (elem)->prev->next = (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 caluculate 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 simple_lock_init(&_timeout_lock); 144 } 145 146 void 147 timeout_set(struct timeout *new, void (*fn)(void *), void *arg) 148 { 149 new->to_func = fn; 150 new->to_arg = arg; 151 new->to_flags = TIMEOUT_INITIALIZED; 152 } 153 154 155 void 156 timeout_add(struct timeout *new, int to_ticks) 157 { 158 int s; 159 int old_time; 160 161 timeout_wheel_lock(&s); 162 #ifdef DIAGNOSTIC 163 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 164 panic("timeout_add: not initialized"); 165 if (to_ticks < 0) 166 panic("timeout_add: to_ticks < 0"); 167 #endif 168 /* Initialize the time here, it won't change. */ 169 old_time = new->to_time; 170 new->to_time = to_ticks + ticks; 171 new->to_flags &= ~TIMEOUT_TRIGGERED; 172 173 /* 174 * If this timeout already is scheduled and now is moved 175 * earlier, reschedule it now. Otherwise leave it in place 176 * and let it be rescheduled later. 177 */ 178 if (new->to_flags & TIMEOUT_ONQUEUE) { 179 if (new->to_time < old_time) { 180 CIRCQ_REMOVE(&new->to_list); 181 CIRCQ_INSERT(&new->to_list, &timeout_todo); 182 } 183 } else { 184 new->to_flags |= TIMEOUT_ONQUEUE; 185 CIRCQ_INSERT(&new->to_list, &timeout_todo); 186 } 187 188 timeout_wheel_unlock(s); 189 } 190 191 void 192 timeout_del(struct timeout *to) 193 { 194 int s; 195 196 timeout_wheel_lock(&s); 197 if (to->to_flags & TIMEOUT_ONQUEUE) { 198 CIRCQ_REMOVE(&to->to_list); 199 to->to_flags &= ~TIMEOUT_ONQUEUE; 200 } 201 to->to_flags &= ~TIMEOUT_TRIGGERED; 202 timeout_wheel_unlock(s); 203 } 204 205 /* 206 * This is called from hardclock() once every tick. 207 * We return !0 if we need to schedule a softclock. 208 * 209 * We don't need locking in here. 210 */ 211 int 212 timeout_hardclock_update(void) 213 { 214 MOVEBUCKET(0, ticks); 215 if (MASKWHEEL(0, ticks) == 0) { 216 MOVEBUCKET(1, ticks); 217 if (MASKWHEEL(1, ticks) == 0) { 218 MOVEBUCKET(2, ticks); 219 if (MASKWHEEL(2, ticks) == 0) 220 MOVEBUCKET(3, ticks); 221 } 222 } 223 return (!CIRCQ_EMPTY(&timeout_todo)); 224 } 225 226 void 227 softclock(void) 228 { 229 struct timeout *to; 230 int s; 231 void (*fn)(void *); 232 void *arg; 233 234 timeout_wheel_lock(&s); 235 while (!CIRCQ_EMPTY(&timeout_todo)) { 236 237 to = (struct timeout *)CIRCQ_FIRST(&timeout_todo); /* XXX */ 238 CIRCQ_REMOVE(&to->to_list); 239 240 /* If due run it, otherwise insert it into the right bucket. */ 241 if (to->to_time - ticks > 0) { 242 CIRCQ_INSERT(&to->to_list, 243 &BUCKET((to->to_time - ticks), to->to_time)); 244 } else { 245 #ifdef DEBUG 246 if (to->to_time - ticks < 0) 247 printf("timeout delayed %d\n", to->to_time - 248 ticks); 249 #endif 250 to->to_flags &= ~TIMEOUT_ONQUEUE; 251 to->to_flags |= TIMEOUT_TRIGGERED; 252 253 fn = to->to_func; 254 arg = to->to_arg; 255 256 timeout_wheel_unlock(s); 257 fn(arg); 258 timeout_wheel_lock(&s); 259 } 260 } 261 timeout_wheel_unlock(s); 262 } 263 264 #ifdef DDB 265 void db_show_callout_bucket(struct circq *); 266 267 void 268 db_show_callout_bucket(struct circq *bucket) 269 { 270 struct timeout *to; 271 struct circq *p; 272 db_expr_t offset; 273 char *name; 274 275 for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) { 276 to = (struct timeout *)p; /* XXX */ 277 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 278 name = name ? name : "?"; 279 db_printf("%9d %2d/%-4d %8x %s\n", to->to_time - ticks, 280 (bucket - timeout_wheel) / WHEELSIZE, 281 bucket - timeout_wheel, to->to_arg, name); 282 } 283 } 284 285 void 286 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 287 { 288 int s; 289 int b; 290 291 db_printf("ticks now: %d\n", ticks); 292 db_printf(" ticks wheel arg func\n"); 293 294 timeout_wheel_lock(&s); 295 296 /* XXX: Show timeout_todo? */ 297 for (b = 0; b < BUCKETS; b++) 298 db_show_callout_bucket(&timeout_wheel[b]); 299 300 timeout_wheel_unlock(s); 301 } 302 #endif 303