1 /* $OpenBSD: kern_timeout.c,v 1.26 2008/01/20 18:23:38 miod 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 34 #ifdef DDB 35 #include <machine/db_machdep.h> 36 #include <ddb/db_interface.h> 37 #include <ddb/db_access.h> 38 #include <ddb/db_sym.h> 39 #include <ddb/db_output.h> 40 #endif 41 42 /* 43 * Timeouts are kept in a hierarchical timing wheel. The to_time is the value 44 * of the global variable "ticks" when the timeout should be called. There are 45 * four levels with 256 buckets each. See 'Scheme 7' in 46 * "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for 47 * Implementing a Timer Facility" by George Varghese and Tony Lauck. 48 */ 49 #define BUCKETS 1024 50 #define WHEELSIZE 256 51 #define WHEELMASK 255 52 #define WHEELBITS 8 53 54 struct circq timeout_wheel[BUCKETS]; /* Queues of timeouts */ 55 struct circq timeout_todo; /* Worklist */ 56 57 #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK) 58 59 #define BUCKET(rel, abs) \ 60 (timeout_wheel[ \ 61 ((rel) <= (1 << (2*WHEELBITS))) \ 62 ? ((rel) <= (1 << WHEELBITS)) \ 63 ? MASKWHEEL(0, (abs)) \ 64 : MASKWHEEL(1, (abs)) + WHEELSIZE \ 65 : ((rel) <= (1 << (3*WHEELBITS))) \ 66 ? MASKWHEEL(2, (abs)) + 2*WHEELSIZE \ 67 : MASKWHEEL(3, (abs)) + 3*WHEELSIZE]) 68 69 #define MOVEBUCKET(wheel, time) \ 70 CIRCQ_APPEND(&timeout_todo, \ 71 &timeout_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE]) 72 73 /* 74 * All wheels are locked with the same mutex. 75 * 76 * We need locking since the timeouts are manipulated from hardclock that's 77 * not behind the big lock. 78 */ 79 struct mutex timeout_mutex = MUTEX_INITIALIZER(IPL_HIGH); 80 81 /* 82 * Circular queue definitions. 83 */ 84 85 #define CIRCQ_INIT(elem) do { \ 86 (elem)->next = (elem); \ 87 (elem)->prev = (elem); \ 88 } while (0) 89 90 #define CIRCQ_INSERT(elem, list) do { \ 91 (elem)->prev = (list)->prev; \ 92 (elem)->next = (list); \ 93 (list)->prev->next = (elem); \ 94 (list)->prev = (elem); \ 95 } while (0) 96 97 #define CIRCQ_APPEND(fst, snd) do { \ 98 if (!CIRCQ_EMPTY(snd)) { \ 99 (fst)->prev->next = (snd)->next;\ 100 (snd)->next->prev = (fst)->prev;\ 101 (snd)->prev->next = (fst); \ 102 (fst)->prev = (snd)->prev; \ 103 CIRCQ_INIT(snd); \ 104 } \ 105 } while (0) 106 107 #define CIRCQ_REMOVE(elem) do { \ 108 (elem)->next->prev = (elem)->prev; \ 109 (elem)->prev->next = (elem)->next; \ 110 } while (0) 111 112 #define CIRCQ_FIRST(elem) ((elem)->next) 113 114 #define CIRCQ_EMPTY(elem) (CIRCQ_FIRST(elem) == (elem)) 115 116 /* 117 * Some of the "math" in here is a bit tricky. 118 * 119 * We have to beware of wrapping ints. 120 * We use the fact that any element added to the queue must be added with a 121 * positive time. That means that any element `to' on the queue cannot be 122 * scheduled to timeout further in time than INT_MAX, but to->to_time can 123 * be positive or negative so comparing it with anything is dangerous. 124 * The only way we can use the to->to_time value in any predictable way 125 * is when we calculate how far in the future `to' will timeout - 126 * "to->to_time - ticks". The result will always be positive for future 127 * timeouts and 0 or negative for due timeouts. 128 */ 129 extern int ticks; /* XXX - move to sys/X.h */ 130 131 void 132 timeout_startup(void) 133 { 134 int b; 135 136 CIRCQ_INIT(&timeout_todo); 137 for (b = 0; b < BUCKETS; b++) 138 CIRCQ_INIT(&timeout_wheel[b]); 139 } 140 141 void 142 timeout_set(struct timeout *new, void (*fn)(void *), void *arg) 143 { 144 new->to_func = fn; 145 new->to_arg = arg; 146 new->to_flags = TIMEOUT_INITIALIZED; 147 } 148 149 150 void 151 timeout_add(struct timeout *new, int to_ticks) 152 { 153 int old_time; 154 155 #ifdef DIAGNOSTIC 156 if (!(new->to_flags & TIMEOUT_INITIALIZED)) 157 panic("timeout_add: not initialized"); 158 if (to_ticks < 0) 159 panic("timeout_add: to_ticks (%d) < 0", to_ticks); 160 #endif 161 162 mtx_enter(&timeout_mutex); 163 /* Initialize the time here, it won't change. */ 164 old_time = new->to_time; 165 new->to_time = to_ticks + ticks; 166 new->to_flags &= ~TIMEOUT_TRIGGERED; 167 168 /* 169 * If this timeout already is scheduled and now is moved 170 * earlier, reschedule it now. Otherwise leave it in place 171 * and let it be rescheduled later. 172 */ 173 if (new->to_flags & TIMEOUT_ONQUEUE) { 174 if (new->to_time - ticks < old_time - ticks) { 175 CIRCQ_REMOVE(&new->to_list); 176 CIRCQ_INSERT(&new->to_list, &timeout_todo); 177 } 178 } else { 179 new->to_flags |= TIMEOUT_ONQUEUE; 180 CIRCQ_INSERT(&new->to_list, &timeout_todo); 181 } 182 mtx_leave(&timeout_mutex); 183 } 184 185 void 186 timeout_del(struct timeout *to) 187 { 188 mtx_enter(&timeout_mutex); 189 if (to->to_flags & TIMEOUT_ONQUEUE) { 190 CIRCQ_REMOVE(&to->to_list); 191 to->to_flags &= ~TIMEOUT_ONQUEUE; 192 } 193 to->to_flags &= ~TIMEOUT_TRIGGERED; 194 mtx_leave(&timeout_mutex); 195 } 196 197 /* 198 * This is called from hardclock() once every tick. 199 * We return !0 if we need to schedule a softclock. 200 */ 201 int 202 timeout_hardclock_update(void) 203 { 204 int ret; 205 206 mtx_enter(&timeout_mutex); 207 208 ticks++; 209 210 MOVEBUCKET(0, ticks); 211 if (MASKWHEEL(0, ticks) == 0) { 212 MOVEBUCKET(1, ticks); 213 if (MASKWHEEL(1, ticks) == 0) { 214 MOVEBUCKET(2, ticks); 215 if (MASKWHEEL(2, ticks) == 0) 216 MOVEBUCKET(3, ticks); 217 } 218 } 219 ret = !CIRCQ_EMPTY(&timeout_todo); 220 mtx_leave(&timeout_mutex); 221 222 return (ret); 223 } 224 225 void 226 softclock(void) 227 { 228 struct timeout *to; 229 void (*fn)(void *); 230 void *arg; 231 232 mtx_enter(&timeout_mutex); 233 while (!CIRCQ_EMPTY(&timeout_todo)) { 234 235 to = (struct timeout *)CIRCQ_FIRST(&timeout_todo); /* XXX */ 236 CIRCQ_REMOVE(&to->to_list); 237 238 /* If due run it, otherwise insert it into the right bucket. */ 239 if (to->to_time - ticks > 0) { 240 CIRCQ_INSERT(&to->to_list, 241 &BUCKET((to->to_time - ticks), to->to_time)); 242 } else { 243 #ifdef DEBUG 244 if (to->to_time - ticks < 0) 245 printf("timeout delayed %d\n", to->to_time - 246 ticks); 247 #endif 248 to->to_flags &= ~TIMEOUT_ONQUEUE; 249 to->to_flags |= TIMEOUT_TRIGGERED; 250 251 fn = to->to_func; 252 arg = to->to_arg; 253 254 mtx_leave(&timeout_mutex); 255 fn(arg); 256 mtx_enter(&timeout_mutex); 257 } 258 } 259 mtx_leave(&timeout_mutex); 260 } 261 262 #ifdef DDB 263 void db_show_callout_bucket(struct circq *); 264 265 void 266 db_show_callout_bucket(struct circq *bucket) 267 { 268 struct timeout *to; 269 struct circq *p; 270 db_expr_t offset; 271 char *name; 272 273 for (p = CIRCQ_FIRST(bucket); p != bucket; p = CIRCQ_FIRST(p)) { 274 to = (struct timeout *)p; /* XXX */ 275 db_find_sym_and_offset((db_addr_t)to->to_func, &name, &offset); 276 name = name ? name : "?"; 277 db_printf("%9d %2d/%-4d %8x %s\n", to->to_time - ticks, 278 (bucket - timeout_wheel) / WHEELSIZE, 279 bucket - timeout_wheel, to->to_arg, name); 280 } 281 } 282 283 void 284 db_show_callout(db_expr_t addr, int haddr, db_expr_t count, char *modif) 285 { 286 int b; 287 288 db_printf("ticks now: %d\n", ticks); 289 db_printf(" ticks wheel arg func\n"); 290 291 mtx_enter(&timeout_mutex); 292 db_show_callout_bucket(&timeout_todo); 293 for (b = 0; b < BUCKETS; b++) 294 db_show_callout_bucket(&timeout_wheel[b]); 295 mtx_leave(&timeout_mutex); 296 } 297 #endif 298