kern_timeout.c revision 82127
11541Srgrimes/*- 21541Srgrimes * Copyright (c) 1982, 1986, 1991, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * (c) UNIX System Laboratories, Inc. 51541Srgrimes * All or some portions of this file are derived from material licensed 61541Srgrimes * to the University of California by American Telephone and Telegraph 71541Srgrimes * Co. or Unix System Laboratories, Inc. and are reproduced herein with 81541Srgrimes * the permission of UNIX System Laboratories, Inc. 91541Srgrimes * 101541Srgrimes * Redistribution and use in source and binary forms, with or without 111541Srgrimes * modification, are permitted provided that the following conditions 121541Srgrimes * are met: 131541Srgrimes * 1. Redistributions of source code must retain the above copyright 141541Srgrimes * notice, this list of conditions and the following disclaimer. 151541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161541Srgrimes * notice, this list of conditions and the following disclaimer in the 171541Srgrimes * documentation and/or other materials provided with the distribution. 181541Srgrimes * 3. All advertising materials mentioning features or use of this software 191541Srgrimes * must display the following acknowledgement: 201541Srgrimes * This product includes software developed by the University of 211541Srgrimes * California, Berkeley and its contributors. 221541Srgrimes * 4. Neither the name of the University nor the names of its contributors 231541Srgrimes * may be used to endorse or promote products derived from this software 241541Srgrimes * without specific prior written permission. 251541Srgrimes * 261541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361541Srgrimes * SUCH DAMAGE. 371541Srgrimes * 3844510Swollman * From: @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 3950477Speter * $FreeBSD: head/sys/kern/kern_timeout.c 82127 2001-08-22 04:07:27Z dillon $ 401541Srgrimes */ 411541Srgrimes 421541Srgrimes#include <sys/param.h> 431541Srgrimes#include <sys/systm.h> 4433392Sphk#include <sys/callout.h> 451541Srgrimes#include <sys/kernel.h> 4674914Sjhb#include <sys/lock.h> 4768840Sjhb#include <sys/mutex.h> 481541Srgrimes 4933392Sphk/* 5033392Sphk * TODO: 5133392Sphk * allocate more timeout table slots when table overflows. 5233392Sphk */ 5333392Sphk 5433392Sphk/* Exported to machdep.c and/or kern_clock.c. */ 5529680Sgibbsstruct callout *callout; 5629680Sgibbsstruct callout_list callfree; 5729680Sgibbsint callwheelsize, callwheelbits, callwheelmask; 5829680Sgibbsstruct callout_tailq *callwheel; 5933392Sphkint softticks; /* Like ticks, but for softclock(). */ 6068889Sjakestruct mtx callout_lock; 612112Swollman 6229680Sgibbsstatic struct callout *nextsoftcheck; /* Next callout to be checked. */ 631541Srgrimes 641541Srgrimes/* 6582127Sdillon * kern_timeout_callwheel_alloc() - kernel low level callwheel initialization 6682127Sdillon * 6782127Sdillon * This code is called very early in the kernel initialization sequence, 6882127Sdillon * and may be called more then once. 6982127Sdillon */ 7082127Sdilloncaddr_t 7182127Sdillonkern_timeout_callwheel_alloc(caddr_t v) 7282127Sdillon{ 7382127Sdillon /* 7482127Sdillon * Calculate callout wheel size 7582127Sdillon */ 7682127Sdillon for (callwheelsize = 1, callwheelbits = 0; 7782127Sdillon callwheelsize < ncallout; 7882127Sdillon callwheelsize <<= 1, ++callwheelbits) 7982127Sdillon ; 8082127Sdillon callwheelmask = callwheelsize - 1; 8182127Sdillon 8282127Sdillon callout = (struct callout *)v; 8382127Sdillon v = (caddr_t)(callout + ncallout); 8482127Sdillon callwheel = (struct callout_tailq *)v; 8582127Sdillon v = (caddr_t)(callwheel + callwheelsize); 8682127Sdillon return(v); 8782127Sdillon} 8882127Sdillon 8982127Sdillon/* 9082127Sdillon * kern_timeout_callwheel_init() - initialize previously reserved callwheel 9182127Sdillon * space. 9282127Sdillon * 9382127Sdillon * This code is called just once, after the space reserved for the 9482127Sdillon * callout wheel has been finalized. 9582127Sdillon */ 9682127Sdillonvoid 9782127Sdillonkern_timeout_callwheel_init(void) 9882127Sdillon{ 9982127Sdillon int i; 10082127Sdillon 10182127Sdillon SLIST_INIT(&callfree); 10282127Sdillon for (i = 0; i < ncallout; i++) { 10382127Sdillon callout_init(&callout[i], 0); 10482127Sdillon callout[i].c_flags = CALLOUT_LOCAL_ALLOC; 10582127Sdillon SLIST_INSERT_HEAD(&callfree, &callout[i], c_links.sle); 10682127Sdillon } 10782127Sdillon for (i = 0; i < callwheelsize; i++) { 10882127Sdillon TAILQ_INIT(&callwheel[i]); 10982127Sdillon } 11082127Sdillon mtx_init(&callout_lock, "callout", MTX_SPIN | MTX_RECURSE); 11182127Sdillon} 11282127Sdillon 11382127Sdillon/* 11429680Sgibbs * The callout mechanism is based on the work of Adam M. Costello and 11529680Sgibbs * George Varghese, published in a technical report entitled "Redesigning 11629680Sgibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion 11729680Sgibbs * in FreeBSD by Justin T. Gibbs. The original work on the data structures 11829680Sgibbs * used in this implementation was published by G.Varghese and A. Lauck in 11929680Sgibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 12029680Sgibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of 12129680Sgibbs * the 11th ACM Annual Symposium on Operating Systems Principles, 12229680Sgibbs * Austin, Texas Nov 1987. 12329680Sgibbs */ 12432388Sphk 12529680Sgibbs/* 1261541Srgrimes * Software (low priority) clock interrupt. 1271541Srgrimes * Run periodic events from timeout queue. 1281541Srgrimes */ 1291541Srgrimesvoid 13067551Sjhbsoftclock(void *dummy) 1311541Srgrimes{ 1321541Srgrimes register struct callout *c; 13329805Sgibbs register struct callout_tailq *bucket; 13429805Sgibbs register int curticks; 13533392Sphk register int steps; /* #steps since we last allowed interrupts */ 1361541Srgrimes 13733392Sphk#ifndef MAX_SOFTCLOCK_STEPS 13833392Sphk#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 13933392Sphk#endif /* MAX_SOFTCLOCK_STEPS */ 14029680Sgibbs 14129680Sgibbs steps = 0; 14272200Sbmilekic mtx_lock_spin(&callout_lock); 14329680Sgibbs while (softticks != ticks) { 14429805Sgibbs softticks++; 14529805Sgibbs /* 14629805Sgibbs * softticks may be modified by hard clock, so cache 14729805Sgibbs * it while we work on a given bucket. 14829805Sgibbs */ 14929805Sgibbs curticks = softticks; 15029805Sgibbs bucket = &callwheel[curticks & callwheelmask]; 15129805Sgibbs c = TAILQ_FIRST(bucket); 15229680Sgibbs while (c) { 15329805Sgibbs if (c->c_time != curticks) { 15429680Sgibbs c = TAILQ_NEXT(c, c_links.tqe); 15529680Sgibbs ++steps; 15629680Sgibbs if (steps >= MAX_SOFTCLOCK_STEPS) { 15729680Sgibbs nextsoftcheck = c; 15829805Sgibbs /* Give interrupts a chance. */ 15972200Sbmilekic mtx_unlock_spin(&callout_lock); 16081370Sjhb ; /* nothing */ 16172200Sbmilekic mtx_lock_spin(&callout_lock); 16229680Sgibbs c = nextsoftcheck; 16329680Sgibbs steps = 0; 16429680Sgibbs } 16529680Sgibbs } else { 16629680Sgibbs void (*c_func)(void *); 16729680Sgibbs void *c_arg; 16868889Sjake int c_flags; 16929680Sgibbs 17029680Sgibbs nextsoftcheck = TAILQ_NEXT(c, c_links.tqe); 17129805Sgibbs TAILQ_REMOVE(bucket, c, c_links.tqe); 17229680Sgibbs c_func = c->c_func; 17329680Sgibbs c_arg = c->c_arg; 17468889Sjake c_flags = c->c_flags; 17529680Sgibbs c->c_func = NULL; 17644510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 17744510Swollman c->c_flags = CALLOUT_LOCAL_ALLOC; 17844510Swollman SLIST_INSERT_HEAD(&callfree, c, 17944510Swollman c_links.sle); 18044510Swollman } else { 18144510Swollman c->c_flags = 18250673Sjlemon (c->c_flags & ~CALLOUT_PENDING); 18344510Swollman } 18472200Sbmilekic mtx_unlock_spin(&callout_lock); 18568889Sjake if (!(c_flags & CALLOUT_MPSAFE)) 18672200Sbmilekic mtx_lock(&Giant); 18729680Sgibbs c_func(c_arg); 18868889Sjake if (!(c_flags & CALLOUT_MPSAFE)) 18972200Sbmilekic mtx_unlock(&Giant); 19072200Sbmilekic mtx_lock_spin(&callout_lock); 19129680Sgibbs steps = 0; 19229680Sgibbs c = nextsoftcheck; 19329680Sgibbs } 19429680Sgibbs } 1951541Srgrimes } 19629680Sgibbs nextsoftcheck = NULL; 19772200Sbmilekic mtx_unlock_spin(&callout_lock); 1981541Srgrimes} 1991541Srgrimes 2001541Srgrimes/* 2011541Srgrimes * timeout -- 2021541Srgrimes * Execute a function after a specified length of time. 2031541Srgrimes * 2041541Srgrimes * untimeout -- 2051541Srgrimes * Cancel previous timeout function call. 2061541Srgrimes * 20729680Sgibbs * callout_handle_init -- 20829680Sgibbs * Initialize a handle so that using it with untimeout is benign. 20929680Sgibbs * 2101541Srgrimes * See AT&T BCI Driver Reference Manual for specification. This 21129680Sgibbs * implementation differs from that one in that although an 21229680Sgibbs * identification value is returned from timeout, the original 21329680Sgibbs * arguments to timeout as well as the identifier are used to 21429680Sgibbs * identify entries for untimeout. 2151541Srgrimes */ 21629680Sgibbsstruct callout_handle 21729680Sgibbstimeout(ftn, arg, to_ticks) 21833824Sbde timeout_t *ftn; 2191541Srgrimes void *arg; 22069147Sjlemon int to_ticks; 2211541Srgrimes{ 22229680Sgibbs struct callout *new; 22329680Sgibbs struct callout_handle handle; 2241541Srgrimes 22572200Sbmilekic mtx_lock_spin(&callout_lock); 2261541Srgrimes 2271541Srgrimes /* Fill in the next free callout structure. */ 22829680Sgibbs new = SLIST_FIRST(&callfree); 22929680Sgibbs if (new == NULL) 23029680Sgibbs /* XXX Attempt to malloc first */ 2311541Srgrimes panic("timeout table full"); 23229680Sgibbs SLIST_REMOVE_HEAD(&callfree, c_links.sle); 23344510Swollman 23444510Swollman callout_reset(new, to_ticks, ftn, arg); 2351541Srgrimes 23644510Swollman handle.callout = new; 23772200Sbmilekic mtx_unlock_spin(&callout_lock); 23829680Sgibbs return (handle); 2391541Srgrimes} 2401541Srgrimes 2411541Srgrimesvoid 24229680Sgibbsuntimeout(ftn, arg, handle) 24333824Sbde timeout_t *ftn; 2441541Srgrimes void *arg; 24529680Sgibbs struct callout_handle handle; 2461541Srgrimes{ 2471541Srgrimes 24829680Sgibbs /* 24929680Sgibbs * Check for a handle that was initialized 25029680Sgibbs * by callout_handle_init, but never used 25129680Sgibbs * for a real timeout. 25229680Sgibbs */ 25329680Sgibbs if (handle.callout == NULL) 25429680Sgibbs return; 25529680Sgibbs 25672200Sbmilekic mtx_lock_spin(&callout_lock); 25744510Swollman if (handle.callout->c_func == ftn && handle.callout->c_arg == arg) 25844510Swollman callout_stop(handle.callout); 25972200Sbmilekic mtx_unlock_spin(&callout_lock); 2601541Srgrimes} 2611541Srgrimes 26224101Sbdevoid 26329680Sgibbscallout_handle_init(struct callout_handle *handle) 26429680Sgibbs{ 26529680Sgibbs handle->callout = NULL; 26629680Sgibbs} 26729680Sgibbs 26844510Swollman/* 26944510Swollman * New interface; clients allocate their own callout structures. 27044510Swollman * 27144510Swollman * callout_reset() - establish or change a timeout 27244510Swollman * callout_stop() - disestablish a timeout 27344510Swollman * callout_init() - initialize a callout structure so that it can 27444510Swollman * safely be passed to callout_reset() and callout_stop() 27544510Swollman * 27650673Sjlemon * <sys/callout.h> defines three convenience macros: 27744510Swollman * 27850673Sjlemon * callout_active() - returns truth if callout has not been serviced 27950673Sjlemon * callout_pending() - returns truth if callout is still waiting for timeout 28050673Sjlemon * callout_deactivate() - marks the callout as having been serviced 28144510Swollman */ 28244510Swollmanvoid 28369147Sjlemoncallout_reset(c, to_ticks, ftn, arg) 28444510Swollman struct callout *c; 28544510Swollman int to_ticks; 28644510Swollman void (*ftn) __P((void *)); 28744510Swollman void *arg; 28844510Swollman{ 28944510Swollman 29072200Sbmilekic mtx_lock_spin(&callout_lock); 29144510Swollman if (c->c_flags & CALLOUT_PENDING) 29244510Swollman callout_stop(c); 29344510Swollman 29444510Swollman /* 29581370Sjhb * We could unlock callout_lock here and lock it again before the 29681370Sjhb * TAILQ_INSERT_TAIL, but there's no point since doing this setup 29781370Sjhb * doesn't take much time. 29844510Swollman */ 29944510Swollman if (to_ticks <= 0) 30044510Swollman to_ticks = 1; 30144510Swollman 30244510Swollman c->c_arg = arg; 30369147Sjlemon c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING); 30444510Swollman c->c_func = ftn; 30544510Swollman c->c_time = ticks + to_ticks; 30644510Swollman TAILQ_INSERT_TAIL(&callwheel[c->c_time & callwheelmask], 30744510Swollman c, c_links.tqe); 30872200Sbmilekic mtx_unlock_spin(&callout_lock); 30944510Swollman} 31044510Swollman 31181481Sjhbint 31244510Swollmancallout_stop(c) 31344510Swollman struct callout *c; 31444510Swollman{ 31544510Swollman 31672200Sbmilekic mtx_lock_spin(&callout_lock); 31744510Swollman /* 31844510Swollman * Don't attempt to delete a callout that's not on the queue. 31944510Swollman */ 32044510Swollman if (!(c->c_flags & CALLOUT_PENDING)) { 32150673Sjlemon c->c_flags &= ~CALLOUT_ACTIVE; 32272200Sbmilekic mtx_unlock_spin(&callout_lock); 32381481Sjhb return (0); 32444510Swollman } 32550673Sjlemon c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 32644510Swollman 32744510Swollman if (nextsoftcheck == c) { 32844510Swollman nextsoftcheck = TAILQ_NEXT(c, c_links.tqe); 32944510Swollman } 33044510Swollman TAILQ_REMOVE(&callwheel[c->c_time & callwheelmask], c, c_links.tqe); 33144510Swollman c->c_func = NULL; 33244510Swollman 33344510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 33444510Swollman SLIST_INSERT_HEAD(&callfree, c, c_links.sle); 33544510Swollman } 33672200Sbmilekic mtx_unlock_spin(&callout_lock); 33781481Sjhb return (1); 33844510Swollman} 33944510Swollman 34044510Swollmanvoid 34169147Sjlemoncallout_init(c, mpsafe) 34244510Swollman struct callout *c; 34369147Sjlemon int mpsafe; 34444510Swollman{ 34544527Swollman bzero(c, sizeof *c); 34669147Sjlemon if (mpsafe) 34769147Sjlemon c->c_flags |= CALLOUT_MPSAFE; 34844510Swollman} 34944510Swollman 35031950Snate#ifdef APM_FIXUP_CALLTODO 35131950Snate/* 35231950Snate * Adjust the kernel calltodo timeout list. This routine is used after 35331950Snate * an APM resume to recalculate the calltodo timer list values with the 35431950Snate * number of hz's we have been sleeping. The next hardclock() will detect 35531950Snate * that there are fired timers and run softclock() to execute them. 35631950Snate * 35731950Snate * Please note, I have not done an exhaustive analysis of what code this 35831950Snate * might break. I am motivated to have my select()'s and alarm()'s that 35931950Snate * have expired during suspend firing upon resume so that the applications 36031950Snate * which set the timer can do the maintanence the timer was for as close 36131950Snate * as possible to the originally intended time. Testing this code for a 36231950Snate * week showed that resuming from a suspend resulted in 22 to 25 timers 36331950Snate * firing, which seemed independant on whether the suspend was 2 hours or 36431950Snate * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 36531950Snate */ 36631950Snatevoid 36731950Snateadjust_timeout_calltodo(time_change) 36831950Snate struct timeval *time_change; 36931950Snate{ 37031950Snate register struct callout *p; 37131950Snate unsigned long delta_ticks; 37231950Snate 37331950Snate /* 37431950Snate * How many ticks were we asleep? 37536127Sbde * (stolen from tvtohz()). 37631950Snate */ 37731950Snate 37831950Snate /* Don't do anything */ 37931950Snate if (time_change->tv_sec < 0) 38031950Snate return; 38131950Snate else if (time_change->tv_sec <= LONG_MAX / 1000000) 38231950Snate delta_ticks = (time_change->tv_sec * 1000000 + 38331950Snate time_change->tv_usec + (tick - 1)) / tick + 1; 38431950Snate else if (time_change->tv_sec <= LONG_MAX / hz) 38531950Snate delta_ticks = time_change->tv_sec * hz + 38631950Snate (time_change->tv_usec + (tick - 1)) / tick + 1; 38731950Snate else 38831950Snate delta_ticks = LONG_MAX; 38931950Snate 39031950Snate if (delta_ticks > INT_MAX) 39131950Snate delta_ticks = INT_MAX; 39231950Snate 39331950Snate /* 39431950Snate * Now rip through the timer calltodo list looking for timers 39531950Snate * to expire. 39631950Snate */ 39731950Snate 39831950Snate /* don't collide with softclock() */ 39972200Sbmilekic mtx_lock_spin(&callout_lock); 40031950Snate for (p = calltodo.c_next; p != NULL; p = p->c_next) { 40131950Snate p->c_time -= delta_ticks; 40231950Snate 40331950Snate /* Break if the timer had more time on it than delta_ticks */ 40431950Snate if (p->c_time > 0) 40531950Snate break; 40631950Snate 40731950Snate /* take back the ticks the timer didn't use (p->c_time <= 0) */ 40831950Snate delta_ticks = -p->c_time; 40931950Snate } 41072200Sbmilekic mtx_unlock_spin(&callout_lock); 41131950Snate 41231950Snate return; 41331950Snate} 41431950Snate#endif /* APM_FIXUP_CALLTODO */ 415