kern_timeout.c revision 177859
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 * 4. Neither the name of the University nor the names of its contributors 191541Srgrimes * may be used to endorse or promote products derived from this software 201541Srgrimes * without specific prior written permission. 211541Srgrimes * 221541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 231541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 241541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 251541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 261541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 271541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 281541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 291541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 301541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 311541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 321541Srgrimes * SUCH DAMAGE. 331541Srgrimes * 3444510Swollman * From: @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 351541Srgrimes */ 361541Srgrimes 37116182Sobrien#include <sys/cdefs.h> 38116182Sobrien__FBSDID("$FreeBSD: head/sys/kern/kern_timeout.c 177859 2008-04-02 11:20:30Z jeff $"); 39116182Sobrien 401541Srgrimes#include <sys/param.h> 411541Srgrimes#include <sys/systm.h> 42177859Sjeff#include <sys/bus.h> 4333392Sphk#include <sys/callout.h> 44127969Scperciva#include <sys/condvar.h> 45177859Sjeff#include <sys/interrupt.h> 461541Srgrimes#include <sys/kernel.h> 47133229Srwatson#include <sys/ktr.h> 4874914Sjhb#include <sys/lock.h> 49177859Sjeff#include <sys/malloc.h> 5068840Sjhb#include <sys/mutex.h> 51150188Sjhb#include <sys/proc.h> 52171053Sattilio#include <sys/sleepqueue.h> 53115810Sphk#include <sys/sysctl.h> 54177859Sjeff#include <sys/smp.h> 551541Srgrimes 56115810Sphkstatic int avg_depth; 57115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0, 58115810Sphk "Average number of items examined per softclock call. Units = 1/1000"); 59115810Sphkstatic int avg_gcalls; 60115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0, 61115810Sphk "Average number of Giant callouts made per softclock call. Units = 1/1000"); 62173760Sattiliostatic int avg_lockcalls; 63173760SattilioSYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0, 64173760Sattilio "Average number of lock callouts made per softclock call. Units = 1/1000"); 65115810Sphkstatic int avg_mpcalls; 66115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0, 67115810Sphk "Average number of MP callouts made per softclock call. Units = 1/1000"); 6833392Sphk/* 6933392Sphk * TODO: 7033392Sphk * allocate more timeout table slots when table overflows. 7133392Sphk */ 7229680Sgibbsint callwheelsize, callwheelbits, callwheelmask; 732112Swollman 74177859Sjeffstruct callout_cpu { 75177859Sjeff struct mtx cc_lock; 76177859Sjeff struct callout *cc_callout; 77177859Sjeff struct callout_tailq *cc_callwheel; 78177859Sjeff struct callout_list cc_callfree; 79177859Sjeff struct callout *cc_next; 80177859Sjeff struct callout *cc_curr; 81177859Sjeff void *cc_cookie; 82177859Sjeff int cc_softticks; 83177859Sjeff int cc_cancel; 84177859Sjeff int cc_waiting; 85177859Sjeff}; 86128024Scperciva 87177859Sjeff#ifdef SMP 88177859Sjeffstruct callout_cpu cc_cpu[MAXCPU]; 89177859Sjeff#define CC_CPU(cpu) (&cc_cpu[(cpu)]) 90177859Sjeff#define CC_SELF() CC_CPU(PCPU_GET(cpuid)) 91177859Sjeff#else 92177859Sjeffstruct callout_cpu cc_cpu; 93177859Sjeff#define CC_CPU(cpu) &cc_cpu 94177859Sjeff#define CC_SELF() &cc_cpu 95177859Sjeff#endif 96177859Sjeff#define CC_LOCK(cc) mtx_lock_spin(&(cc)->cc_lock) 97177859Sjeff#define CC_UNLOCK(cc) mtx_unlock_spin(&(cc)->cc_lock) 98177859Sjeff 99177859Sjeffstatic int timeout_cpu; 100177859Sjeff 101177859SjeffMALLOC_DEFINE(M_CALLOUT, "callout", "Callout datastructures"); 102177859Sjeff 103139831Scperciva/** 104177859Sjeff * Locked by cc_lock: 105177859Sjeff * cc_curr - If a callout is in progress, it is curr_callout. 106155957Sjhb * If curr_callout is non-NULL, threads waiting in 107177859Sjeff * callout_drain() will be woken up as soon as the 108127969Scperciva * relevant callout completes. 109177859Sjeff * cc_cancel - Changing to 1 with both callout_lock and c_lock held 110141428Siedowse * guarantees that the current callout will not run. 111141428Siedowse * The softclock() function sets this to 0 before it 112173760Sattilio * drops callout_lock to acquire c_lock, and it calls 113155957Sjhb * the handler only if curr_cancelled is still 0 after 114173760Sattilio * c_lock is successfully acquired. 115177859Sjeff * cc_waiting - If a thread is waiting in callout_drain(), then 116155957Sjhb * callout_wait is nonzero. Set only when 117128024Scperciva * curr_callout is non-NULL. 118127969Scperciva */ 119128024Scperciva 1201541Srgrimes/* 12182127Sdillon * kern_timeout_callwheel_alloc() - kernel low level callwheel initialization 12282127Sdillon * 12382127Sdillon * This code is called very early in the kernel initialization sequence, 12482127Sdillon * and may be called more then once. 12582127Sdillon */ 12682127Sdilloncaddr_t 12782127Sdillonkern_timeout_callwheel_alloc(caddr_t v) 12882127Sdillon{ 129177859Sjeff struct callout_cpu *cc; 130177859Sjeff 131177859Sjeff timeout_cpu = PCPU_GET(cpuid); 132177859Sjeff cc = CC_CPU(timeout_cpu); 13382127Sdillon /* 13482127Sdillon * Calculate callout wheel size 13582127Sdillon */ 13682127Sdillon for (callwheelsize = 1, callwheelbits = 0; 13782127Sdillon callwheelsize < ncallout; 13882127Sdillon callwheelsize <<= 1, ++callwheelbits) 13982127Sdillon ; 14082127Sdillon callwheelmask = callwheelsize - 1; 14182127Sdillon 142177859Sjeff cc->cc_callout = (struct callout *)v; 143177859Sjeff v = (caddr_t)(cc->cc_callout + ncallout); 144177859Sjeff cc->cc_callwheel = (struct callout_tailq *)v; 145177859Sjeff v = (caddr_t)(cc->cc_callwheel + callwheelsize); 14682127Sdillon return(v); 14782127Sdillon} 14882127Sdillon 149177859Sjeffstatic void 150177859Sjeffcallout_cpu_init(struct callout_cpu *cc) 151177859Sjeff{ 152177859Sjeff struct callout *c; 153177859Sjeff int i; 154177859Sjeff 155177859Sjeff mtx_init(&cc->cc_lock, "callout", NULL, MTX_SPIN | MTX_RECURSE); 156177859Sjeff SLIST_INIT(&cc->cc_callfree); 157177859Sjeff for (i = 0; i < callwheelsize; i++) { 158177859Sjeff TAILQ_INIT(&cc->cc_callwheel[i]); 159177859Sjeff } 160177859Sjeff if (cc->cc_callout == NULL) 161177859Sjeff return; 162177859Sjeff for (i = 0; i < ncallout; i++) { 163177859Sjeff c = &cc->cc_callout[i]; 164177859Sjeff callout_init(c, 0); 165177859Sjeff c->c_flags = CALLOUT_LOCAL_ALLOC; 166177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 167177859Sjeff } 168177859Sjeff} 169177859Sjeff 17082127Sdillon/* 17182127Sdillon * kern_timeout_callwheel_init() - initialize previously reserved callwheel 17282127Sdillon * space. 17382127Sdillon * 17482127Sdillon * This code is called just once, after the space reserved for the 17582127Sdillon * callout wheel has been finalized. 17682127Sdillon */ 17782127Sdillonvoid 17882127Sdillonkern_timeout_callwheel_init(void) 17982127Sdillon{ 180177859Sjeff callout_cpu_init(CC_CPU(timeout_cpu)); 181177859Sjeff} 18282127Sdillon 183177859Sjeff/* 184177859Sjeff * Start standard softclock thread. 185177859Sjeff */ 186177859Sjeffvoid *softclock_ih; 187177859Sjeff 188177859Sjeffstatic void 189177859Sjeffstart_softclock(void *dummy) 190177859Sjeff{ 191177859Sjeff struct callout_cpu *cc; 192177859Sjeff#ifdef SMP 193177859Sjeff int cpu; 194177859Sjeff#endif 195177859Sjeff 196177859Sjeff cc = CC_CPU(timeout_cpu); 197177859Sjeff if (swi_add(&clk_intr_event, "clock", softclock, cc, SWI_CLOCK, 198177859Sjeff INTR_MPSAFE, &softclock_ih)) 199177859Sjeff panic("died while creating standard software ithreads"); 200177859Sjeff cc->cc_cookie = softclock_ih; 201177859Sjeff#ifdef SMP 202177859Sjeff for (cpu = 0; cpu <= mp_maxid; cpu++) { 203177859Sjeff if (cpu == timeout_cpu) 204177859Sjeff continue; 205177859Sjeff if (CPU_ABSENT(cpu)) 206177859Sjeff continue; 207177859Sjeff cc = CC_CPU(cpu); 208177859Sjeff if (swi_add(NULL, "clock", softclock, cc, SWI_CLOCK, 209177859Sjeff INTR_MPSAFE, &cc->cc_cookie)) 210177859Sjeff panic("died while creating standard software ithreads"); 211177859Sjeff cc->cc_callout = NULL; /* Only cpu0 handles timeout(). */ 212177859Sjeff cc->cc_callwheel = malloc( 213177859Sjeff sizeof(struct callout_tailq) * callwheelsize, M_CALLOUT, 214177859Sjeff M_WAITOK); 215177859Sjeff callout_cpu_init(cc); 21682127Sdillon } 217177859Sjeff#endif 218177859Sjeff} 219177859Sjeff 220177859SjeffSYSINIT(start_softclock, SI_SUB_SOFTINTR, SI_ORDER_FIRST, start_softclock, NULL); 221177859Sjeff 222177859Sjeffvoid 223177859Sjeffcallout_tick(void) 224177859Sjeff{ 225177859Sjeff int need_softclock = 0; 226177859Sjeff struct callout_cpu *cc; 227177859Sjeff 228177859Sjeff /* 229177859Sjeff * Process callouts at a very low cpu priority, so we don't keep the 230177859Sjeff * relatively high clock interrupt priority any longer than necessary. 231177859Sjeff */ 232177859Sjeff cc = CC_SELF(); 233177859Sjeff mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET); 234177859Sjeff if (!TAILQ_EMPTY(&cc->cc_callwheel[ticks & callwheelmask])) { 235177859Sjeff need_softclock = 1; 236177859Sjeff } else if (cc->cc_softticks + 1 == ticks) 237177859Sjeff ++cc->cc_softticks; 238177859Sjeff mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET); 239177859Sjeff /* 240177859Sjeff * swi_sched acquires the thread lock, so we don't want to call it 241177859Sjeff * with cc_lock held; incorrect locking order. 242177859Sjeff */ 243177859Sjeff if (need_softclock) 244177859Sjeff swi_sched(cc->cc_cookie, 0); 245177859Sjeff} 246177859Sjeff 247177859Sjeffstatic struct callout_cpu * 248177859Sjeffcallout_lock(struct callout *c) 249177859Sjeff{ 250177859Sjeff struct callout_cpu *cc; 251177859Sjeff int cpu; 252177859Sjeff 253177859Sjeff for (;;) { 254177859Sjeff cpu = c->c_cpu; 255177859Sjeff cc = CC_CPU(cpu); 256177859Sjeff CC_LOCK(cc); 257177859Sjeff if (cpu == c->c_cpu) 258177859Sjeff break; 259177859Sjeff CC_UNLOCK(cc); 26082127Sdillon } 261177859Sjeff return (cc); 26282127Sdillon} 26382127Sdillon 26482127Sdillon/* 26529680Sgibbs * The callout mechanism is based on the work of Adam M. Costello and 26629680Sgibbs * George Varghese, published in a technical report entitled "Redesigning 26729680Sgibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion 26829680Sgibbs * in FreeBSD by Justin T. Gibbs. The original work on the data structures 269128630Shmp * used in this implementation was published by G. Varghese and T. Lauck in 27029680Sgibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 27129680Sgibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of 27229680Sgibbs * the 11th ACM Annual Symposium on Operating Systems Principles, 27329680Sgibbs * Austin, Texas Nov 1987. 27429680Sgibbs */ 27532388Sphk 27629680Sgibbs/* 2771541Srgrimes * Software (low priority) clock interrupt. 2781541Srgrimes * Run periodic events from timeout queue. 2791541Srgrimes */ 2801541Srgrimesvoid 281177859Sjeffsoftclock(void *arg) 2821541Srgrimes{ 283177859Sjeff struct callout_cpu *cc; 284102936Sphk struct callout *c; 285102936Sphk struct callout_tailq *bucket; 286102936Sphk int curticks; 287102936Sphk int steps; /* #steps since we last allowed interrupts */ 288115810Sphk int depth; 289115810Sphk int mpcalls; 290173760Sattilio int lockcalls; 291115810Sphk int gcalls; 292122585Smckusick#ifdef DIAGNOSTIC 293122585Smckusick struct bintime bt1, bt2; 294122585Smckusick struct timespec ts2; 295122585Smckusick static uint64_t maxdt = 36893488147419102LL; /* 2 msec */ 296123254Sphk static timeout_t *lastfunc; 297122585Smckusick#endif 2981541Srgrimes 29933392Sphk#ifndef MAX_SOFTCLOCK_STEPS 30033392Sphk#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 30133392Sphk#endif /* MAX_SOFTCLOCK_STEPS */ 30229680Sgibbs 303115810Sphk mpcalls = 0; 304173760Sattilio lockcalls = 0; 305115810Sphk gcalls = 0; 306115810Sphk depth = 0; 30729680Sgibbs steps = 0; 308177859Sjeff cc = (struct callout_cpu *)arg; 309177859Sjeff CC_LOCK(cc); 310177859Sjeff while (cc->cc_softticks != ticks) { 311177859Sjeff cc->cc_softticks++; 31229805Sgibbs /* 313177859Sjeff * cc_softticks may be modified by hard clock, so cache 31429805Sgibbs * it while we work on a given bucket. 31529805Sgibbs */ 316177859Sjeff curticks = cc->cc_softticks; 317177859Sjeff bucket = &cc->cc_callwheel[curticks & callwheelmask]; 31829805Sgibbs c = TAILQ_FIRST(bucket); 31929680Sgibbs while (c) { 320115810Sphk depth++; 32129805Sgibbs if (c->c_time != curticks) { 32229680Sgibbs c = TAILQ_NEXT(c, c_links.tqe); 32329680Sgibbs ++steps; 32429680Sgibbs if (steps >= MAX_SOFTCLOCK_STEPS) { 325177859Sjeff cc->cc_next = c; 32629805Sgibbs /* Give interrupts a chance. */ 327177859Sjeff CC_UNLOCK(cc); 32881370Sjhb ; /* nothing */ 329177859Sjeff CC_LOCK(cc); 330177859Sjeff c = cc->cc_next; 33129680Sgibbs steps = 0; 33229680Sgibbs } 33329680Sgibbs } else { 33429680Sgibbs void (*c_func)(void *); 33529680Sgibbs void *c_arg; 336173760Sattilio struct lock_class *class; 337173842Sattilio struct lock_object *c_lock; 338173760Sattilio int c_flags, sharedlock; 33929680Sgibbs 340177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 34129805Sgibbs TAILQ_REMOVE(bucket, c, c_links.tqe); 342173760Sattilio class = (c->c_lock != NULL) ? 343173760Sattilio LOCK_CLASS(c->c_lock) : NULL; 344173760Sattilio sharedlock = (c->c_flags & CALLOUT_SHAREDLOCK) ? 345173760Sattilio 0 : 1; 346173842Sattilio c_lock = c->c_lock; 34729680Sgibbs c_func = c->c_func; 34829680Sgibbs c_arg = c->c_arg; 34968889Sjake c_flags = c->c_flags; 35044510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 35144510Swollman c->c_flags = CALLOUT_LOCAL_ALLOC; 35244510Swollman } else { 35344510Swollman c->c_flags = 35450673Sjlemon (c->c_flags & ~CALLOUT_PENDING); 35544510Swollman } 356177859Sjeff cc->cc_curr = c; 357177859Sjeff cc->cc_cancel = 0; 358177859Sjeff CC_UNLOCK(cc); 359173842Sattilio if (c_lock != NULL) { 360173842Sattilio class->lc_lock(c_lock, sharedlock); 361141428Siedowse /* 362141428Siedowse * The callout may have been cancelled 363141428Siedowse * while we switched locks. 364141428Siedowse */ 365177859Sjeff if (cc->cc_cancel) { 366173842Sattilio class->lc_unlock(c_lock); 367155957Sjhb goto skip; 368141428Siedowse } 369141428Siedowse /* The callout cannot be stopped now. */ 370177859Sjeff cc->cc_cancel = 1; 371141428Siedowse 372173842Sattilio if (c_lock == &Giant.lock_object) { 373141428Siedowse gcalls++; 374163246Sglebius CTR3(KTR_CALLOUT, 375163246Sglebius "callout %p func %p arg %p", 376163246Sglebius c, c_func, c_arg); 377141428Siedowse } else { 378173760Sattilio lockcalls++; 379173760Sattilio CTR3(KTR_CALLOUT, "callout lock" 380163246Sglebius " %p func %p arg %p", 381163246Sglebius c, c_func, c_arg); 382141428Siedowse } 383115810Sphk } else { 384115810Sphk mpcalls++; 385163246Sglebius CTR3(KTR_CALLOUT, 386163246Sglebius "callout mpsafe %p func %p arg %p", 387163246Sglebius c, c_func, c_arg); 388115810Sphk } 389122585Smckusick#ifdef DIAGNOSTIC 390122585Smckusick binuptime(&bt1); 391122585Smckusick#endif 392150187Sjhb THREAD_NO_SLEEPING(); 39329680Sgibbs c_func(c_arg); 394150187Sjhb THREAD_SLEEPING_OK(); 395122585Smckusick#ifdef DIAGNOSTIC 396122585Smckusick binuptime(&bt2); 397122585Smckusick bintime_sub(&bt2, &bt1); 398122585Smckusick if (bt2.frac > maxdt) { 399123254Sphk if (lastfunc != c_func || 400123254Sphk bt2.frac > maxdt * 2) { 401123254Sphk bintime2timespec(&bt2, &ts2); 402123254Sphk printf( 403123254Sphk "Expensive timeout(9) function: %p(%p) %jd.%09ld s\n", 404123254Sphk c_func, c_arg, 405123254Sphk (intmax_t)ts2.tv_sec, 406123254Sphk ts2.tv_nsec); 407123254Sphk } 408122585Smckusick maxdt = bt2.frac; 409123254Sphk lastfunc = c_func; 410122585Smckusick } 411122585Smckusick#endif 412141428Siedowse if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0) 413173842Sattilio class->lc_unlock(c_lock); 414155957Sjhb skip: 415177859Sjeff CC_LOCK(cc); 416177491Salfred /* 417177491Salfred * If the current callout is locally 418177491Salfred * allocated (from timeout(9)) 419177491Salfred * then put it on the freelist. 420177491Salfred * 421177491Salfred * Note: we need to check the cached 422177491Salfred * copy of c_flags because if it was not 423177491Salfred * local, then it's not safe to deref the 424177491Salfred * callout pointer. 425177491Salfred */ 426177491Salfred if (c_flags & CALLOUT_LOCAL_ALLOC) { 427177491Salfred KASSERT(c->c_flags == 428177491Salfred CALLOUT_LOCAL_ALLOC, 429177491Salfred ("corrupted callout")); 430177491Salfred c->c_func = NULL; 431177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, 432177491Salfred c_links.sle); 433177491Salfred } 434177859Sjeff cc->cc_curr = NULL; 435177859Sjeff if (cc->cc_waiting) { 436127969Scperciva /* 437155957Sjhb * There is someone waiting 438127969Scperciva * for the callout to complete. 439127969Scperciva */ 440177859Sjeff cc->cc_waiting = 0; 441177859Sjeff CC_UNLOCK(cc); 442177859Sjeff wakeup(&cc->cc_waiting); 443177859Sjeff CC_LOCK(cc); 444128024Scperciva } 44529680Sgibbs steps = 0; 446177859Sjeff c = cc->cc_next; 44729680Sgibbs } 44829680Sgibbs } 4491541Srgrimes } 450115810Sphk avg_depth += (depth * 1000 - avg_depth) >> 8; 451115810Sphk avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8; 452173760Sattilio avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8; 453115810Sphk avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8; 454177859Sjeff cc->cc_next = NULL; 455177859Sjeff CC_UNLOCK(cc); 4561541Srgrimes} 4571541Srgrimes 4581541Srgrimes/* 4591541Srgrimes * timeout -- 4601541Srgrimes * Execute a function after a specified length of time. 4611541Srgrimes * 4621541Srgrimes * untimeout -- 4631541Srgrimes * Cancel previous timeout function call. 4641541Srgrimes * 46529680Sgibbs * callout_handle_init -- 46629680Sgibbs * Initialize a handle so that using it with untimeout is benign. 46729680Sgibbs * 4681541Srgrimes * See AT&T BCI Driver Reference Manual for specification. This 46929680Sgibbs * implementation differs from that one in that although an 47029680Sgibbs * identification value is returned from timeout, the original 47129680Sgibbs * arguments to timeout as well as the identifier are used to 47229680Sgibbs * identify entries for untimeout. 4731541Srgrimes */ 47429680Sgibbsstruct callout_handle 47529680Sgibbstimeout(ftn, arg, to_ticks) 47633824Sbde timeout_t *ftn; 4771541Srgrimes void *arg; 47869147Sjlemon int to_ticks; 4791541Srgrimes{ 480177859Sjeff struct callout_cpu *cc; 48129680Sgibbs struct callout *new; 48229680Sgibbs struct callout_handle handle; 4831541Srgrimes 484177859Sjeff cc = CC_CPU(timeout_cpu); 485177859Sjeff CC_LOCK(cc); 4861541Srgrimes /* Fill in the next free callout structure. */ 487177859Sjeff new = SLIST_FIRST(&cc->cc_callfree); 48829680Sgibbs if (new == NULL) 48929680Sgibbs /* XXX Attempt to malloc first */ 4901541Srgrimes panic("timeout table full"); 491177859Sjeff SLIST_REMOVE_HEAD(&cc->cc_callfree, c_links.sle); 49244510Swollman callout_reset(new, to_ticks, ftn, arg); 493177859Sjeff handle.callout = new; 494177859Sjeff CC_UNLOCK(cc); 4951541Srgrimes 49629680Sgibbs return (handle); 4971541Srgrimes} 4981541Srgrimes 4991541Srgrimesvoid 50029680Sgibbsuntimeout(ftn, arg, handle) 50133824Sbde timeout_t *ftn; 5021541Srgrimes void *arg; 50329680Sgibbs struct callout_handle handle; 5041541Srgrimes{ 505177859Sjeff struct callout_cpu *cc; 5061541Srgrimes 50729680Sgibbs /* 50829680Sgibbs * Check for a handle that was initialized 50929680Sgibbs * by callout_handle_init, but never used 51029680Sgibbs * for a real timeout. 51129680Sgibbs */ 51229680Sgibbs if (handle.callout == NULL) 51329680Sgibbs return; 51429680Sgibbs 515177859Sjeff cc = callout_lock(handle.callout); 51644510Swollman if (handle.callout->c_func == ftn && handle.callout->c_arg == arg) 51744510Swollman callout_stop(handle.callout); 518177859Sjeff CC_UNLOCK(cc); 5191541Srgrimes} 5201541Srgrimes 52124101Sbdevoid 52229680Sgibbscallout_handle_init(struct callout_handle *handle) 52329680Sgibbs{ 52429680Sgibbs handle->callout = NULL; 52529680Sgibbs} 52629680Sgibbs 52744510Swollman/* 52844510Swollman * New interface; clients allocate their own callout structures. 52944510Swollman * 53044510Swollman * callout_reset() - establish or change a timeout 53144510Swollman * callout_stop() - disestablish a timeout 53244510Swollman * callout_init() - initialize a callout structure so that it can 53344510Swollman * safely be passed to callout_reset() and callout_stop() 53444510Swollman * 53550673Sjlemon * <sys/callout.h> defines three convenience macros: 53644510Swollman * 537140487Scperciva * callout_active() - returns truth if callout has not been stopped, 538140487Scperciva * drained, or deactivated since the last time the callout was 539140487Scperciva * reset. 54050673Sjlemon * callout_pending() - returns truth if callout is still waiting for timeout 54150673Sjlemon * callout_deactivate() - marks the callout as having been serviced 54244510Swollman */ 543149879Sglebiusint 544177859Sjeffcallout_reset_on(struct callout *c, int to_ticks, void (*ftn)(void *), 545177859Sjeff void *arg, int cpu) 54644510Swollman{ 547177859Sjeff struct callout_cpu *cc; 548149879Sglebius int cancelled = 0; 54944510Swollman 550177859Sjeff /* 551177859Sjeff * Don't allow migration of pre-allocated callouts lest they 552177859Sjeff * become unbalanced. 553177859Sjeff */ 554177859Sjeff if (c->c_flags & CALLOUT_LOCAL_ALLOC) 555177859Sjeff cpu = c->c_cpu; 556177859Sjeffretry: 557177859Sjeff cc = callout_lock(c); 558177859Sjeff if (cc->cc_curr == c) { 559127969Scperciva /* 560127969Scperciva * We're being asked to reschedule a callout which is 561173760Sattilio * currently in progress. If there is a lock then we 562141428Siedowse * can cancel the callout if it has not really started. 563127969Scperciva */ 564177859Sjeff if (c->c_lock != NULL && !cc->cc_cancel) 565177859Sjeff cancelled = cc->cc_cancel = 1; 566177859Sjeff if (cc->cc_waiting) { 567141428Siedowse /* 568141428Siedowse * Someone has called callout_drain to kill this 569141428Siedowse * callout. Don't reschedule. 570141428Siedowse */ 571163246Sglebius CTR4(KTR_CALLOUT, "%s %p func %p arg %p", 572163246Sglebius cancelled ? "cancelled" : "failed to cancel", 573163246Sglebius c, c->c_func, c->c_arg); 574177859Sjeff CC_UNLOCK(cc); 575149879Sglebius return (cancelled); 576141428Siedowse } 577128024Scperciva } 578133190Scperciva if (c->c_flags & CALLOUT_PENDING) { 579177859Sjeff if (cc->cc_next == c) { 580177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 581133190Scperciva } 582177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 583133190Scperciva c_links.tqe); 58444510Swollman 585149879Sglebius cancelled = 1; 586177859Sjeff c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 587133190Scperciva } 58844510Swollman /* 589177859Sjeff * If the lock must migrate we have to check the state again as 590177859Sjeff * we can't hold both the new and old locks simultaneously. 59144510Swollman */ 592177859Sjeff if (c->c_cpu != cpu) { 593177859Sjeff c->c_cpu = cpu; 594177859Sjeff CC_UNLOCK(cc); 595177859Sjeff goto retry; 596177859Sjeff } 597177859Sjeff 59844510Swollman if (to_ticks <= 0) 59944510Swollman to_ticks = 1; 60044510Swollman 60144510Swollman c->c_arg = arg; 60269147Sjlemon c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING); 60344510Swollman c->c_func = ftn; 60444510Swollman c->c_time = ticks + to_ticks; 605177859Sjeff TAILQ_INSERT_TAIL(&cc->cc_callwheel[c->c_time & callwheelmask], 60644510Swollman c, c_links.tqe); 607163246Sglebius CTR5(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d", 608163246Sglebius cancelled ? "re" : "", c, c->c_func, c->c_arg, to_ticks); 609177859Sjeff CC_UNLOCK(cc); 610149879Sglebius 611149879Sglebius return (cancelled); 61244510Swollman} 61344510Swollman 61481481Sjhbint 615127969Scperciva_callout_stop_safe(c, safe) 616127969Scperciva struct callout *c; 617127969Scperciva int safe; 618127969Scperciva{ 619177859Sjeff struct callout_cpu *cc; 620173760Sattilio struct lock_class *class; 621173760Sattilio int use_lock, sq_locked; 622127969Scperciva 623173760Sattilio /* 624173760Sattilio * Some old subsystems don't hold Giant while running a callout_stop(), 625173760Sattilio * so just discard this check for the moment. 626173760Sattilio */ 627173760Sattilio if (!safe && c->c_lock != NULL) { 628173760Sattilio if (c->c_lock == &Giant.lock_object) 629173760Sattilio use_lock = mtx_owned(&Giant); 630173760Sattilio else { 631173760Sattilio use_lock = 1; 632173760Sattilio class = LOCK_CLASS(c->c_lock); 633173760Sattilio class->lc_assert(c->c_lock, LA_XLOCKED); 634173760Sattilio } 635173760Sattilio } else 636173760Sattilio use_lock = 0; 637141428Siedowse 638172025Sjhb sq_locked = 0; 639172025Sjhbagain: 640177859Sjeff cc = callout_lock(c); 64144510Swollman /* 642155957Sjhb * If the callout isn't pending, it's not on the queue, so 643155957Sjhb * don't attempt to remove it from the queue. We can try to 644155957Sjhb * stop it by other means however. 64544510Swollman */ 64644510Swollman if (!(c->c_flags & CALLOUT_PENDING)) { 64750673Sjlemon c->c_flags &= ~CALLOUT_ACTIVE; 648155957Sjhb 649155957Sjhb /* 650155957Sjhb * If it wasn't on the queue and it isn't the current 651155957Sjhb * callout, then we can't stop it, so just bail. 652155957Sjhb */ 653177859Sjeff if (cc->cc_curr != c) { 654163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 655163246Sglebius c, c->c_func, c->c_arg); 656177859Sjeff CC_UNLOCK(cc); 657172025Sjhb if (sq_locked) 658177859Sjeff sleepq_release(&cc->cc_curr); 659141428Siedowse return (0); 660141428Siedowse } 661155957Sjhb 662141428Siedowse if (safe) { 663127969Scperciva /* 664155957Sjhb * The current callout is running (or just 665155957Sjhb * about to run) and blocking is allowed, so 666155957Sjhb * just wait for the current invocation to 667155957Sjhb * finish. 668127969Scperciva */ 669177859Sjeff while (cc->cc_curr == c) { 670171053Sattilio 671171053Sattilio /* 672171053Sattilio * Use direct calls to sleepqueue interface 673171053Sattilio * instead of cv/msleep in order to avoid 674177859Sjeff * a LOR between cc_lock and sleepqueue 675171053Sattilio * chain spinlocks. This piece of code 676171053Sattilio * emulates a msleep_spin() call actually. 677172025Sjhb * 678172025Sjhb * If we already have the sleepqueue chain 679172025Sjhb * locked, then we can safely block. If we 680172025Sjhb * don't already have it locked, however, 681177859Sjeff * we have to drop the cc_lock to lock 682172025Sjhb * it. This opens several races, so we 683172025Sjhb * restart at the beginning once we have 684172025Sjhb * both locks. If nothing has changed, then 685172025Sjhb * we will end up back here with sq_locked 686172025Sjhb * set. 687171053Sattilio */ 688172025Sjhb if (!sq_locked) { 689177859Sjeff CC_UNLOCK(cc); 690177859Sjeff sleepq_lock(&cc->cc_curr); 691172025Sjhb sq_locked = 1; 692172025Sjhb goto again; 693172025Sjhb } 694177859Sjeff cc->cc_waiting = 1; 695171053Sattilio DROP_GIANT(); 696177859Sjeff CC_UNLOCK(cc); 697177859Sjeff sleepq_add(&cc->cc_curr, 698177859Sjeff &cc->cc_lock.lock_object, "codrain", 699171053Sattilio SLEEPQ_SLEEP, 0); 700177859Sjeff sleepq_wait(&cc->cc_curr, 0); 701172025Sjhb sq_locked = 0; 702171053Sattilio 703171053Sattilio /* Reacquire locks previously released. */ 704171053Sattilio PICKUP_GIANT(); 705177859Sjeff CC_LOCK(cc); 706155957Sjhb } 707177859Sjeff } else if (use_lock && !cc->cc_cancel) { 708155957Sjhb /* 709173760Sattilio * The current callout is waiting for its 710173760Sattilio * lock which we hold. Cancel the callout 711155957Sjhb * and return. After our caller drops the 712173760Sattilio * lock, the callout will be skipped in 713155957Sjhb * softclock(). 714155957Sjhb */ 715177859Sjeff cc->cc_cancel = 1; 716163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 717163246Sglebius c, c->c_func, c->c_arg); 718177859Sjeff CC_UNLOCK(cc); 719172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain locked")); 720141428Siedowse return (1); 721155957Sjhb } 722163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 723163246Sglebius c, c->c_func, c->c_arg); 724177859Sjeff CC_UNLOCK(cc); 725172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain still locked")); 72681481Sjhb return (0); 72744510Swollman } 728172025Sjhb if (sq_locked) 729177859Sjeff sleepq_release(&cc->cc_curr); 730172025Sjhb 73150673Sjlemon c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 73244510Swollman 733177859Sjeff if (cc->cc_next == c) { 734177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 73544510Swollman } 736177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 737177859Sjeff c_links.tqe); 73844510Swollman 739163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 740163246Sglebius c, c->c_func, c->c_arg); 741163246Sglebius 74244510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 743140492Scperciva c->c_func = NULL; 744177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 74544510Swollman } 746177859Sjeff CC_UNLOCK(cc); 74781481Sjhb return (1); 74844510Swollman} 74944510Swollman 75044510Swollmanvoid 75169147Sjlemoncallout_init(c, mpsafe) 75244510Swollman struct callout *c; 75369147Sjlemon int mpsafe; 75444510Swollman{ 75544527Swollman bzero(c, sizeof *c); 756141428Siedowse if (mpsafe) { 757173760Sattilio c->c_lock = NULL; 758141428Siedowse c->c_flags = CALLOUT_RETURNUNLOCKED; 759141428Siedowse } else { 760173760Sattilio c->c_lock = &Giant.lock_object; 761141428Siedowse c->c_flags = 0; 762141428Siedowse } 763177859Sjeff c->c_cpu = timeout_cpu; 76444510Swollman} 76544510Swollman 766141428Siedowsevoid 767173760Sattilio_callout_init_lock(c, lock, flags) 768141428Siedowse struct callout *c; 769173760Sattilio struct lock_object *lock; 770141428Siedowse int flags; 771141428Siedowse{ 772141428Siedowse bzero(c, sizeof *c); 773173760Sattilio c->c_lock = lock; 774173760Sattilio KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0, 775173760Sattilio ("callout_init_lock: bad flags %d", flags)); 776173760Sattilio KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0, 777173760Sattilio ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock")); 778176013Sattilio KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags & 779176013Sattilio (LC_SPINLOCK | LC_SLEEPABLE)), ("%s: invalid lock class", 780173760Sattilio __func__)); 781173760Sattilio c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK); 782177859Sjeff c->c_cpu = timeout_cpu; 783141428Siedowse} 784141428Siedowse 78531950Snate#ifdef APM_FIXUP_CALLTODO 78631950Snate/* 78731950Snate * Adjust the kernel calltodo timeout list. This routine is used after 78831950Snate * an APM resume to recalculate the calltodo timer list values with the 78931950Snate * number of hz's we have been sleeping. The next hardclock() will detect 79031950Snate * that there are fired timers and run softclock() to execute them. 79131950Snate * 79231950Snate * Please note, I have not done an exhaustive analysis of what code this 79331950Snate * might break. I am motivated to have my select()'s and alarm()'s that 79431950Snate * have expired during suspend firing upon resume so that the applications 79531950Snate * which set the timer can do the maintanence the timer was for as close 79631950Snate * as possible to the originally intended time. Testing this code for a 79731950Snate * week showed that resuming from a suspend resulted in 22 to 25 timers 79831950Snate * firing, which seemed independant on whether the suspend was 2 hours or 79931950Snate * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 80031950Snate */ 80131950Snatevoid 80231950Snateadjust_timeout_calltodo(time_change) 80331950Snate struct timeval *time_change; 80431950Snate{ 80531950Snate register struct callout *p; 80631950Snate unsigned long delta_ticks; 80731950Snate 80831950Snate /* 80931950Snate * How many ticks were we asleep? 81036127Sbde * (stolen from tvtohz()). 81131950Snate */ 81231950Snate 81331950Snate /* Don't do anything */ 81431950Snate if (time_change->tv_sec < 0) 81531950Snate return; 81631950Snate else if (time_change->tv_sec <= LONG_MAX / 1000000) 81731950Snate delta_ticks = (time_change->tv_sec * 1000000 + 81831950Snate time_change->tv_usec + (tick - 1)) / tick + 1; 81931950Snate else if (time_change->tv_sec <= LONG_MAX / hz) 82031950Snate delta_ticks = time_change->tv_sec * hz + 82131950Snate (time_change->tv_usec + (tick - 1)) / tick + 1; 82231950Snate else 82331950Snate delta_ticks = LONG_MAX; 82431950Snate 82531950Snate if (delta_ticks > INT_MAX) 82631950Snate delta_ticks = INT_MAX; 82731950Snate 82831950Snate /* 82931950Snate * Now rip through the timer calltodo list looking for timers 83031950Snate * to expire. 83131950Snate */ 83231950Snate 83331950Snate /* don't collide with softclock() */ 834177859Sjeff CC_LOCK(cc); 83531950Snate for (p = calltodo.c_next; p != NULL; p = p->c_next) { 83631950Snate p->c_time -= delta_ticks; 83731950Snate 83831950Snate /* Break if the timer had more time on it than delta_ticks */ 83931950Snate if (p->c_time > 0) 84031950Snate break; 84131950Snate 84231950Snate /* take back the ticks the timer didn't use (p->c_time <= 0) */ 84331950Snate delta_ticks = -p->c_time; 84431950Snate } 845177859Sjeff CC_UNLOCK(cc); 84631950Snate 84731950Snate return; 84831950Snate} 84931950Snate#endif /* APM_FIXUP_CALLTODO */ 850