1df8bae1dSRodney W. Grimes /*- 2df8bae1dSRodney W. Grimes * Copyright (c) 1982, 1986, 1991, 1993 3df8bae1dSRodney W. Grimes * The Regents of the University of California. All rights reserved. 4df8bae1dSRodney W. Grimes * (c) UNIX System Laboratories, Inc. 5df8bae1dSRodney W. Grimes * All or some portions of this file are derived from material licensed 6df8bae1dSRodney W. Grimes * to the University of California by American Telephone and Telegraph 7df8bae1dSRodney W. Grimes * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8df8bae1dSRodney W. Grimes * the permission of UNIX System Laboratories, Inc. 9df8bae1dSRodney W. Grimes * 10df8bae1dSRodney W. Grimes * Redistribution and use in source and binary forms, with or without 11df8bae1dSRodney W. Grimes * modification, are permitted provided that the following conditions 12df8bae1dSRodney W. Grimes * are met: 13df8bae1dSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 14df8bae1dSRodney W. Grimes * notice, this list of conditions and the following disclaimer. 15df8bae1dSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 16df8bae1dSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 17df8bae1dSRodney W. Grimes * documentation and/or other materials provided with the distribution. 18df8bae1dSRodney W. Grimes * 3. All advertising materials mentioning features or use of this software 19df8bae1dSRodney W. Grimes * must display the following acknowledgement: 20df8bae1dSRodney W. Grimes * This product includes software developed by the University of 21df8bae1dSRodney W. Grimes * California, Berkeley and its contributors. 22df8bae1dSRodney W. Grimes * 4. Neither the name of the University nor the names of its contributors 23df8bae1dSRodney W. Grimes * may be used to endorse or promote products derived from this software 24df8bae1dSRodney W. Grimes * without specific prior written permission. 25df8bae1dSRodney W. Grimes * 26df8bae1dSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27df8bae1dSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28df8bae1dSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29df8bae1dSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30df8bae1dSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31df8bae1dSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32df8bae1dSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33df8bae1dSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34df8bae1dSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35df8bae1dSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36df8bae1dSRodney W. Grimes * SUCH DAMAGE. 37df8bae1dSRodney W. Grimes * 38df8bae1dSRodney W. Grimes * @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 39a50ec505SPoul-Henning Kamp * $Id: kern_timeout.c,v 1.48 1998/01/07 12:29:17 phk Exp $ 40df8bae1dSRodney W. Grimes */ 41df8bae1dSRodney W. Grimes 423f31c649SGarrett Wollman /* Portions of this software are covered by the following: */ 433f31c649SGarrett Wollman /****************************************************************************** 443f31c649SGarrett Wollman * * 453f31c649SGarrett Wollman * Copyright (c) David L. Mills 1993, 1994 * 463f31c649SGarrett Wollman * * 473f31c649SGarrett Wollman * Permission to use, copy, modify, and distribute this software and its * 483f31c649SGarrett Wollman * documentation for any purpose and without fee is hereby granted, provided * 493f31c649SGarrett Wollman * that the above copyright notice appears in all copies and that both the * 503f31c649SGarrett Wollman * copyright notice and this permission notice appear in supporting * 513f31c649SGarrett Wollman * documentation, and that the name University of Delaware not be used in * 523f31c649SGarrett Wollman * advertising or publicity pertaining to distribution of the software * 533f31c649SGarrett Wollman * without specific, written prior permission. The University of Delaware * 543f31c649SGarrett Wollman * makes no representations about the suitability this software for any * 553f31c649SGarrett Wollman * purpose. It is provided "as is" without express or implied warranty. * 563f31c649SGarrett Wollman * * 573f31c649SGarrett Wollman *****************************************************************************/ 583f31c649SGarrett Wollman 59df8bae1dSRodney W. Grimes #include <sys/param.h> 60df8bae1dSRodney W. Grimes #include <sys/systm.h> 61df8bae1dSRodney W. Grimes #include <sys/dkstat.h> 62df8bae1dSRodney W. Grimes #include <sys/callout.h> 63df8bae1dSRodney W. Grimes #include <sys/kernel.h> 64df8bae1dSRodney W. Grimes #include <sys/proc.h> 65df8bae1dSRodney W. Grimes #include <sys/resourcevar.h> 66797f2d22SPoul-Henning Kamp #include <sys/signalvar.h> 673f31c649SGarrett Wollman #include <sys/timex.h> 688a129caeSDavid Greenman #include <vm/vm.h> 69996c772fSJohn Dyson #include <sys/lock.h> 70efeaf95aSDavid Greenman #include <vm/pmap.h> 71efeaf95aSDavid Greenman #include <vm/vm_map.h> 72797f2d22SPoul-Henning Kamp #include <sys/sysctl.h> 73df8bae1dSRodney W. Grimes 74df8bae1dSRodney W. Grimes #include <machine/cpu.h> 75835bd1ceSBruce Evans #define CLOCK_HAIR /* XXX */ 763f31c649SGarrett Wollman #include <machine/clock.h> 77b1037dcdSBruce Evans #include <machine/limits.h> 78df8bae1dSRodney W. Grimes 79cc3d5226SBruce Evans /* Exported to machdep.c. */ 80ab36c067SJustin T. Gibbs struct callout *callout; 81ab36c067SJustin T. Gibbs struct callout_list callfree; 82ab36c067SJustin T. Gibbs int callwheelsize, callwheelbits, callwheelmask; 83ab36c067SJustin T. Gibbs struct callout_tailq *callwheel; 84f23b4c91SGarrett Wollman 85ab36c067SJustin T. Gibbs static int softticks; /* Like ticks, but for softclock(). */ 86ab36c067SJustin T. Gibbs static struct callout *nextsoftcheck; /* Next callout to be checked. */ 87df8bae1dSRodney W. Grimes 88df8bae1dSRodney W. Grimes /* 89ab36c067SJustin T. Gibbs * The callout mechanism is based on the work of Adam M. Costello and 90ab36c067SJustin T. Gibbs * George Varghese, published in a technical report entitled "Redesigning 91ab36c067SJustin T. Gibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion 92ab36c067SJustin T. Gibbs * in FreeBSD by Justin T. Gibbs. The original work on the data structures 93ab36c067SJustin T. Gibbs * used in this implementation was published by G.Varghese and A. Lauck in 94ab36c067SJustin T. Gibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 95ab36c067SJustin T. Gibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of 96ab36c067SJustin T. Gibbs * the 11th ACM Annual Symposium on Operating Systems Principles, 97ab36c067SJustin T. Gibbs * Austin, Texas Nov 1987. 98ab36c067SJustin T. Gibbs */ 99a50ec505SPoul-Henning Kamp 100ab36c067SJustin T. Gibbs /* 101df8bae1dSRodney W. Grimes * Software (low priority) clock interrupt. 102df8bae1dSRodney W. Grimes * Run periodic events from timeout queue. 103df8bae1dSRodney W. Grimes */ 104a50ec505SPoul-Henning Kamp 105a50ec505SPoul-Henning Kamp #ifndef MAX_SOFTCLOCK_STEPS 106a50ec505SPoul-Henning Kamp #define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 107a50ec505SPoul-Henning Kamp #endif /* MAX_SOFTCLOCK_STEPS */ 108a50ec505SPoul-Henning Kamp 109df8bae1dSRodney W. Grimes /*ARGSUSED*/ 110df8bae1dSRodney W. Grimes void 111a50ec505SPoul-Henning Kamp softclock(frame) 112a50ec505SPoul-Henning Kamp struct clockframe *frame; 113df8bae1dSRodney W. Grimes { 114df8bae1dSRodney W. Grimes register struct callout *c; 11545327611SJustin T. Gibbs register struct callout_tailq *bucket; 116df8bae1dSRodney W. Grimes register int s; 11745327611SJustin T. Gibbs register int curticks; 118ab36c067SJustin T. Gibbs register int steps; /* 119ab36c067SJustin T. Gibbs * Number of steps taken since 120ab36c067SJustin T. Gibbs * we last allowed interrupts. 121ab36c067SJustin T. Gibbs */ 122df8bae1dSRodney W. Grimes 123a50ec505SPoul-Henning Kamp if (TAILQ_FIRST(&callwheel[ticks & callwheelmask]) == NULL) { 124a50ec505SPoul-Henning Kamp softticks++; 125a50ec505SPoul-Henning Kamp return; 126a50ec505SPoul-Henning Kamp } 127a50ec505SPoul-Henning Kamp if (!CLKF_BASEPRI(frame)) { 128a50ec505SPoul-Henning Kamp /* Not yet, come back later */ 129a50ec505SPoul-Henning Kamp setsoftclock(); 130a50ec505SPoul-Henning Kamp return; 131a50ec505SPoul-Henning Kamp } 132a50ec505SPoul-Henning Kamp 133a50ec505SPoul-Henning Kamp (void)splsoftclock(); 134ab36c067SJustin T. Gibbs 135ab36c067SJustin T. Gibbs steps = 0; 136df8bae1dSRodney W. Grimes s = splhigh(); 137ab36c067SJustin T. Gibbs while (softticks != ticks) { 13845327611SJustin T. Gibbs softticks++; 13945327611SJustin T. Gibbs /* 14045327611SJustin T. Gibbs * softticks may be modified by hard clock, so cache 14145327611SJustin T. Gibbs * it while we work on a given bucket. 14245327611SJustin T. Gibbs */ 14345327611SJustin T. Gibbs curticks = softticks; 14445327611SJustin T. Gibbs bucket = &callwheel[curticks & callwheelmask]; 14545327611SJustin T. Gibbs c = TAILQ_FIRST(bucket); 146ab36c067SJustin T. Gibbs while (c) { 14745327611SJustin T. Gibbs if (c->c_time != curticks) { 148ab36c067SJustin T. Gibbs c = TAILQ_NEXT(c, c_links.tqe); 149ab36c067SJustin T. Gibbs ++steps; 150ab36c067SJustin T. Gibbs if (steps >= MAX_SOFTCLOCK_STEPS) { 151ab36c067SJustin T. Gibbs nextsoftcheck = c; 15245327611SJustin T. Gibbs /* Give interrupts a chance. */ 153df8bae1dSRodney W. Grimes splx(s); 154ab36c067SJustin T. Gibbs s = splhigh(); 155ab36c067SJustin T. Gibbs c = nextsoftcheck; 156ab36c067SJustin T. Gibbs steps = 0; 157df8bae1dSRodney W. Grimes } 158ab36c067SJustin T. Gibbs } else { 159ab36c067SJustin T. Gibbs void (*c_func)(void *); 160ab36c067SJustin T. Gibbs void *c_arg; 161ab36c067SJustin T. Gibbs 162ab36c067SJustin T. Gibbs nextsoftcheck = TAILQ_NEXT(c, c_links.tqe); 16345327611SJustin T. Gibbs TAILQ_REMOVE(bucket, c, c_links.tqe); 164ab36c067SJustin T. Gibbs c_func = c->c_func; 165ab36c067SJustin T. Gibbs c_arg = c->c_arg; 166ab36c067SJustin T. Gibbs c->c_func = NULL; 167ab36c067SJustin T. Gibbs SLIST_INSERT_HEAD(&callfree, c, c_links.sle); 168ab36c067SJustin T. Gibbs splx(s); 169ab36c067SJustin T. Gibbs c_func(c_arg); 170ab36c067SJustin T. Gibbs s = splhigh(); 171ab36c067SJustin T. Gibbs steps = 0; 172ab36c067SJustin T. Gibbs c = nextsoftcheck; 173ab36c067SJustin T. Gibbs } 174ab36c067SJustin T. Gibbs } 175ab36c067SJustin T. Gibbs } 176ab36c067SJustin T. Gibbs nextsoftcheck = NULL; 177df8bae1dSRodney W. Grimes splx(s); 178df8bae1dSRodney W. Grimes } 179df8bae1dSRodney W. Grimes 180df8bae1dSRodney W. Grimes /* 181df8bae1dSRodney W. Grimes * timeout -- 182df8bae1dSRodney W. Grimes * Execute a function after a specified length of time. 183df8bae1dSRodney W. Grimes * 184df8bae1dSRodney W. Grimes * untimeout -- 185df8bae1dSRodney W. Grimes * Cancel previous timeout function call. 186df8bae1dSRodney W. Grimes * 187ab36c067SJustin T. Gibbs * callout_handle_init -- 188ab36c067SJustin T. Gibbs * Initialize a handle so that using it with untimeout is benign. 189ab36c067SJustin T. Gibbs * 190df8bae1dSRodney W. Grimes * See AT&T BCI Driver Reference Manual for specification. This 191ab36c067SJustin T. Gibbs * implementation differs from that one in that although an 192ab36c067SJustin T. Gibbs * identification value is returned from timeout, the original 193ab36c067SJustin T. Gibbs * arguments to timeout as well as the identifier are used to 194ab36c067SJustin T. Gibbs * identify entries for untimeout. 195df8bae1dSRodney W. Grimes */ 196ab36c067SJustin T. Gibbs struct callout_handle 197ab36c067SJustin T. Gibbs timeout(ftn, arg, to_ticks) 198f23b4c91SGarrett Wollman timeout_t ftn; 199df8bae1dSRodney W. Grimes void *arg; 200ab36c067SJustin T. Gibbs register int to_ticks; 201df8bae1dSRodney W. Grimes { 202ab36c067SJustin T. Gibbs int s; 203ab36c067SJustin T. Gibbs struct callout *new; 204ab36c067SJustin T. Gibbs struct callout_handle handle; 205df8bae1dSRodney W. Grimes 206ab36c067SJustin T. Gibbs if (to_ticks <= 0) 207ab36c067SJustin T. Gibbs to_ticks = 1; 208df8bae1dSRodney W. Grimes 209df8bae1dSRodney W. Grimes /* Lock out the clock. */ 210df8bae1dSRodney W. Grimes s = splhigh(); 211df8bae1dSRodney W. Grimes 212df8bae1dSRodney W. Grimes /* Fill in the next free callout structure. */ 213ab36c067SJustin T. Gibbs new = SLIST_FIRST(&callfree); 214ab36c067SJustin T. Gibbs if (new == NULL) 215ab36c067SJustin T. Gibbs /* XXX Attempt to malloc first */ 216df8bae1dSRodney W. Grimes panic("timeout table full"); 217ab36c067SJustin T. Gibbs 218ab36c067SJustin T. Gibbs SLIST_REMOVE_HEAD(&callfree, c_links.sle); 219df8bae1dSRodney W. Grimes new->c_arg = arg; 220df8bae1dSRodney W. Grimes new->c_func = ftn; 22145327611SJustin T. Gibbs new->c_time = ticks + to_ticks; 22245327611SJustin T. Gibbs TAILQ_INSERT_TAIL(&callwheel[new->c_time & callwheelmask], 22345327611SJustin T. Gibbs new, c_links.tqe); 224df8bae1dSRodney W. Grimes 225df8bae1dSRodney W. Grimes splx(s); 226ab36c067SJustin T. Gibbs handle.callout = new; 227ab36c067SJustin T. Gibbs return (handle); 228df8bae1dSRodney W. Grimes } 229df8bae1dSRodney W. Grimes 230df8bae1dSRodney W. Grimes void 231ab36c067SJustin T. Gibbs untimeout(ftn, arg, handle) 232f23b4c91SGarrett Wollman timeout_t ftn; 233df8bae1dSRodney W. Grimes void *arg; 234ab36c067SJustin T. Gibbs struct callout_handle handle; 235df8bae1dSRodney W. Grimes { 236df8bae1dSRodney W. Grimes register int s; 237df8bae1dSRodney W. Grimes 238ab36c067SJustin T. Gibbs /* 239ab36c067SJustin T. Gibbs * Check for a handle that was initialized 240ab36c067SJustin T. Gibbs * by callout_handle_init, but never used 241ab36c067SJustin T. Gibbs * for a real timeout. 242ab36c067SJustin T. Gibbs */ 243ab36c067SJustin T. Gibbs if (handle.callout == NULL) 244ab36c067SJustin T. Gibbs return; 245df8bae1dSRodney W. Grimes 246ab36c067SJustin T. Gibbs s = splhigh(); 247ab36c067SJustin T. Gibbs if ((handle.callout->c_func == ftn) 248ab36c067SJustin T. Gibbs && (handle.callout->c_arg == arg)) { 249ab36c067SJustin T. Gibbs if (nextsoftcheck == handle.callout) { 250ab36c067SJustin T. Gibbs nextsoftcheck = TAILQ_NEXT(handle.callout, c_links.tqe); 251ab36c067SJustin T. Gibbs } 25245327611SJustin T. Gibbs TAILQ_REMOVE(&callwheel[handle.callout->c_time & callwheelmask], 253ab36c067SJustin T. Gibbs handle.callout, c_links.tqe); 254ab36c067SJustin T. Gibbs handle.callout->c_func = NULL; 255ab36c067SJustin T. Gibbs SLIST_INSERT_HEAD(&callfree, handle.callout, c_links.sle); 256df8bae1dSRodney W. Grimes } 257df8bae1dSRodney W. Grimes splx(s); 258df8bae1dSRodney W. Grimes } 259df8bae1dSRodney W. Grimes 2603c816944SBruce Evans void 261ab36c067SJustin T. Gibbs callout_handle_init(struct callout_handle *handle) 262ab36c067SJustin T. Gibbs { 263ab36c067SJustin T. Gibbs handle->callout = NULL; 264ab36c067SJustin T. Gibbs } 265ab36c067SJustin T. Gibbs 266e1d6dc65SNate Williams #ifdef APM_FIXUP_CALLTODO 267e1d6dc65SNate Williams /* 268e1d6dc65SNate Williams * Adjust the kernel calltodo timeout list. This routine is used after 269e1d6dc65SNate Williams * an APM resume to recalculate the calltodo timer list values with the 270e1d6dc65SNate Williams * number of hz's we have been sleeping. The next hardclock() will detect 271e1d6dc65SNate Williams * that there are fired timers and run softclock() to execute them. 272e1d6dc65SNate Williams * 273e1d6dc65SNate Williams * Please note, I have not done an exhaustive analysis of what code this 274e1d6dc65SNate Williams * might break. I am motivated to have my select()'s and alarm()'s that 275e1d6dc65SNate Williams * have expired during suspend firing upon resume so that the applications 276e1d6dc65SNate Williams * which set the timer can do the maintanence the timer was for as close 277e1d6dc65SNate Williams * as possible to the originally intended time. Testing this code for a 278e1d6dc65SNate Williams * week showed that resuming from a suspend resulted in 22 to 25 timers 279e1d6dc65SNate Williams * firing, which seemed independant on whether the suspend was 2 hours or 280e1d6dc65SNate Williams * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 281e1d6dc65SNate Williams */ 282e1d6dc65SNate Williams void 283e1d6dc65SNate Williams adjust_timeout_calltodo(time_change) 284e1d6dc65SNate Williams struct timeval *time_change; 285e1d6dc65SNate Williams { 286e1d6dc65SNate Williams register struct callout *p; 287e1d6dc65SNate Williams unsigned long delta_ticks; 288e1d6dc65SNate Williams int s; 289e1d6dc65SNate Williams 290e1d6dc65SNate Williams /* 291e1d6dc65SNate Williams * How many ticks were we asleep? 292e1d6dc65SNate Williams * (stolen from hzto()). 293e1d6dc65SNate Williams */ 294e1d6dc65SNate Williams 295e1d6dc65SNate Williams /* Don't do anything */ 296e1d6dc65SNate Williams if (time_change->tv_sec < 0) 297e1d6dc65SNate Williams return; 298e1d6dc65SNate Williams else if (time_change->tv_sec <= LONG_MAX / 1000000) 299e1d6dc65SNate Williams delta_ticks = (time_change->tv_sec * 1000000 + 300e1d6dc65SNate Williams time_change->tv_usec + (tick - 1)) / tick + 1; 301e1d6dc65SNate Williams else if (time_change->tv_sec <= LONG_MAX / hz) 302e1d6dc65SNate Williams delta_ticks = time_change->tv_sec * hz + 303e1d6dc65SNate Williams (time_change->tv_usec + (tick - 1)) / tick + 1; 304e1d6dc65SNate Williams else 305e1d6dc65SNate Williams delta_ticks = LONG_MAX; 306e1d6dc65SNate Williams 307e1d6dc65SNate Williams if (delta_ticks > INT_MAX) 308e1d6dc65SNate Williams delta_ticks = INT_MAX; 309e1d6dc65SNate Williams 310e1d6dc65SNate Williams /* 311e1d6dc65SNate Williams * Now rip through the timer calltodo list looking for timers 312e1d6dc65SNate Williams * to expire. 313e1d6dc65SNate Williams */ 314e1d6dc65SNate Williams 315e1d6dc65SNate Williams /* don't collide with softclock() */ 316e1d6dc65SNate Williams s = splhigh(); 317e1d6dc65SNate Williams for (p = calltodo.c_next; p != NULL; p = p->c_next) { 318e1d6dc65SNate Williams p->c_time -= delta_ticks; 319e1d6dc65SNate Williams 320e1d6dc65SNate Williams /* Break if the timer had more time on it than delta_ticks */ 321e1d6dc65SNate Williams if (p->c_time > 0) 322e1d6dc65SNate Williams break; 323e1d6dc65SNate Williams 324e1d6dc65SNate Williams /* take back the ticks the timer didn't use (p->c_time <= 0) */ 325e1d6dc65SNate Williams delta_ticks = -p->c_time; 326e1d6dc65SNate Williams } 327e1d6dc65SNate Williams splx(s); 328e1d6dc65SNate Williams 329e1d6dc65SNate Williams return; 330e1d6dc65SNate Williams } 331e1d6dc65SNate Williams #endif /* APM_FIXUP_CALLTODO */ 332