kern_timeout.c revision 180608
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 180608 2008-07-19 05:18:29Z 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 struct callout_cpu *cc; 226180608Sjeff int need_softclock; 227180608Sjeff int bucket; 228177859Sjeff 229177859Sjeff /* 230177859Sjeff * Process callouts at a very low cpu priority, so we don't keep the 231177859Sjeff * relatively high clock interrupt priority any longer than necessary. 232177859Sjeff */ 233180608Sjeff need_softclock = 0; 234177859Sjeff cc = CC_SELF(); 235177859Sjeff mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET); 236180608Sjeff for (; cc->cc_softticks < ticks; cc->cc_softticks++) { 237180608Sjeff bucket = cc->cc_softticks & callwheelmask; 238180608Sjeff if (!TAILQ_EMPTY(&cc->cc_callwheel[bucket])) { 239180608Sjeff need_softclock = 1; 240180608Sjeff break; 241180608Sjeff } 242180608Sjeff } 243177859Sjeff mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET); 244177859Sjeff /* 245177859Sjeff * swi_sched acquires the thread lock, so we don't want to call it 246177859Sjeff * with cc_lock held; incorrect locking order. 247177859Sjeff */ 248177859Sjeff if (need_softclock) 249177859Sjeff swi_sched(cc->cc_cookie, 0); 250177859Sjeff} 251177859Sjeff 252177859Sjeffstatic struct callout_cpu * 253177859Sjeffcallout_lock(struct callout *c) 254177859Sjeff{ 255177859Sjeff struct callout_cpu *cc; 256177859Sjeff int cpu; 257177859Sjeff 258177859Sjeff for (;;) { 259177859Sjeff cpu = c->c_cpu; 260177859Sjeff cc = CC_CPU(cpu); 261177859Sjeff CC_LOCK(cc); 262177859Sjeff if (cpu == c->c_cpu) 263177859Sjeff break; 264177859Sjeff CC_UNLOCK(cc); 26582127Sdillon } 266177859Sjeff return (cc); 26782127Sdillon} 26882127Sdillon 26982127Sdillon/* 27029680Sgibbs * The callout mechanism is based on the work of Adam M. Costello and 27129680Sgibbs * George Varghese, published in a technical report entitled "Redesigning 27229680Sgibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion 27329680Sgibbs * in FreeBSD by Justin T. Gibbs. The original work on the data structures 274128630Shmp * used in this implementation was published by G. Varghese and T. Lauck in 27529680Sgibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 27629680Sgibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of 27729680Sgibbs * the 11th ACM Annual Symposium on Operating Systems Principles, 27829680Sgibbs * Austin, Texas Nov 1987. 27929680Sgibbs */ 28032388Sphk 28129680Sgibbs/* 2821541Srgrimes * Software (low priority) clock interrupt. 2831541Srgrimes * Run periodic events from timeout queue. 2841541Srgrimes */ 2851541Srgrimesvoid 286177859Sjeffsoftclock(void *arg) 2871541Srgrimes{ 288177859Sjeff struct callout_cpu *cc; 289102936Sphk struct callout *c; 290102936Sphk struct callout_tailq *bucket; 291102936Sphk int curticks; 292102936Sphk int steps; /* #steps since we last allowed interrupts */ 293115810Sphk int depth; 294115810Sphk int mpcalls; 295173760Sattilio int lockcalls; 296115810Sphk int gcalls; 297122585Smckusick#ifdef DIAGNOSTIC 298122585Smckusick struct bintime bt1, bt2; 299122585Smckusick struct timespec ts2; 300122585Smckusick static uint64_t maxdt = 36893488147419102LL; /* 2 msec */ 301123254Sphk static timeout_t *lastfunc; 302122585Smckusick#endif 3031541Srgrimes 30433392Sphk#ifndef MAX_SOFTCLOCK_STEPS 30533392Sphk#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 30633392Sphk#endif /* MAX_SOFTCLOCK_STEPS */ 30729680Sgibbs 308115810Sphk mpcalls = 0; 309173760Sattilio lockcalls = 0; 310115810Sphk gcalls = 0; 311115810Sphk depth = 0; 31229680Sgibbs steps = 0; 313177859Sjeff cc = (struct callout_cpu *)arg; 314177859Sjeff CC_LOCK(cc); 315177859Sjeff while (cc->cc_softticks != ticks) { 31629805Sgibbs /* 317177859Sjeff * cc_softticks may be modified by hard clock, so cache 31829805Sgibbs * it while we work on a given bucket. 31929805Sgibbs */ 320177859Sjeff curticks = cc->cc_softticks; 321180608Sjeff cc->cc_softticks++; 322177859Sjeff bucket = &cc->cc_callwheel[curticks & callwheelmask]; 32329805Sgibbs c = TAILQ_FIRST(bucket); 32429680Sgibbs while (c) { 325115810Sphk depth++; 32629805Sgibbs if (c->c_time != curticks) { 32729680Sgibbs c = TAILQ_NEXT(c, c_links.tqe); 32829680Sgibbs ++steps; 32929680Sgibbs if (steps >= MAX_SOFTCLOCK_STEPS) { 330177859Sjeff cc->cc_next = c; 33129805Sgibbs /* Give interrupts a chance. */ 332177859Sjeff CC_UNLOCK(cc); 33381370Sjhb ; /* nothing */ 334177859Sjeff CC_LOCK(cc); 335177859Sjeff c = cc->cc_next; 33629680Sgibbs steps = 0; 33729680Sgibbs } 33829680Sgibbs } else { 33929680Sgibbs void (*c_func)(void *); 34029680Sgibbs void *c_arg; 341173760Sattilio struct lock_class *class; 342173842Sattilio struct lock_object *c_lock; 343173760Sattilio int c_flags, sharedlock; 34429680Sgibbs 345177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 34629805Sgibbs TAILQ_REMOVE(bucket, c, c_links.tqe); 347173760Sattilio class = (c->c_lock != NULL) ? 348173760Sattilio LOCK_CLASS(c->c_lock) : NULL; 349173760Sattilio sharedlock = (c->c_flags & CALLOUT_SHAREDLOCK) ? 350173760Sattilio 0 : 1; 351173842Sattilio c_lock = c->c_lock; 35229680Sgibbs c_func = c->c_func; 35329680Sgibbs c_arg = c->c_arg; 35468889Sjake c_flags = c->c_flags; 35544510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 35644510Swollman c->c_flags = CALLOUT_LOCAL_ALLOC; 35744510Swollman } else { 35844510Swollman c->c_flags = 35950673Sjlemon (c->c_flags & ~CALLOUT_PENDING); 36044510Swollman } 361177859Sjeff cc->cc_curr = c; 362177859Sjeff cc->cc_cancel = 0; 363177859Sjeff CC_UNLOCK(cc); 364173842Sattilio if (c_lock != NULL) { 365173842Sattilio class->lc_lock(c_lock, sharedlock); 366141428Siedowse /* 367141428Siedowse * The callout may have been cancelled 368141428Siedowse * while we switched locks. 369141428Siedowse */ 370177859Sjeff if (cc->cc_cancel) { 371173842Sattilio class->lc_unlock(c_lock); 372155957Sjhb goto skip; 373141428Siedowse } 374141428Siedowse /* The callout cannot be stopped now. */ 375177859Sjeff cc->cc_cancel = 1; 376141428Siedowse 377173842Sattilio if (c_lock == &Giant.lock_object) { 378141428Siedowse gcalls++; 379163246Sglebius CTR3(KTR_CALLOUT, 380163246Sglebius "callout %p func %p arg %p", 381163246Sglebius c, c_func, c_arg); 382141428Siedowse } else { 383173760Sattilio lockcalls++; 384173760Sattilio CTR3(KTR_CALLOUT, "callout lock" 385163246Sglebius " %p func %p arg %p", 386163246Sglebius c, c_func, c_arg); 387141428Siedowse } 388115810Sphk } else { 389115810Sphk mpcalls++; 390163246Sglebius CTR3(KTR_CALLOUT, 391163246Sglebius "callout mpsafe %p func %p arg %p", 392163246Sglebius c, c_func, c_arg); 393115810Sphk } 394122585Smckusick#ifdef DIAGNOSTIC 395122585Smckusick binuptime(&bt1); 396122585Smckusick#endif 397150187Sjhb THREAD_NO_SLEEPING(); 39829680Sgibbs c_func(c_arg); 399150187Sjhb THREAD_SLEEPING_OK(); 400122585Smckusick#ifdef DIAGNOSTIC 401122585Smckusick binuptime(&bt2); 402122585Smckusick bintime_sub(&bt2, &bt1); 403122585Smckusick if (bt2.frac > maxdt) { 404123254Sphk if (lastfunc != c_func || 405123254Sphk bt2.frac > maxdt * 2) { 406123254Sphk bintime2timespec(&bt2, &ts2); 407123254Sphk printf( 408123254Sphk "Expensive timeout(9) function: %p(%p) %jd.%09ld s\n", 409123254Sphk c_func, c_arg, 410123254Sphk (intmax_t)ts2.tv_sec, 411123254Sphk ts2.tv_nsec); 412123254Sphk } 413122585Smckusick maxdt = bt2.frac; 414123254Sphk lastfunc = c_func; 415122585Smckusick } 416122585Smckusick#endif 417141428Siedowse if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0) 418173842Sattilio class->lc_unlock(c_lock); 419155957Sjhb skip: 420177859Sjeff CC_LOCK(cc); 421177491Salfred /* 422177491Salfred * If the current callout is locally 423177491Salfred * allocated (from timeout(9)) 424177491Salfred * then put it on the freelist. 425177491Salfred * 426177491Salfred * Note: we need to check the cached 427177491Salfred * copy of c_flags because if it was not 428177491Salfred * local, then it's not safe to deref the 429177491Salfred * callout pointer. 430177491Salfred */ 431177491Salfred if (c_flags & CALLOUT_LOCAL_ALLOC) { 432177491Salfred KASSERT(c->c_flags == 433177491Salfred CALLOUT_LOCAL_ALLOC, 434177491Salfred ("corrupted callout")); 435177491Salfred c->c_func = NULL; 436177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, 437177491Salfred c_links.sle); 438177491Salfred } 439177859Sjeff cc->cc_curr = NULL; 440177859Sjeff if (cc->cc_waiting) { 441127969Scperciva /* 442155957Sjhb * There is someone waiting 443127969Scperciva * for the callout to complete. 444127969Scperciva */ 445177859Sjeff cc->cc_waiting = 0; 446177859Sjeff CC_UNLOCK(cc); 447177859Sjeff wakeup(&cc->cc_waiting); 448177859Sjeff CC_LOCK(cc); 449128024Scperciva } 45029680Sgibbs steps = 0; 451177859Sjeff c = cc->cc_next; 45229680Sgibbs } 45329680Sgibbs } 4541541Srgrimes } 455115810Sphk avg_depth += (depth * 1000 - avg_depth) >> 8; 456115810Sphk avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8; 457173760Sattilio avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8; 458115810Sphk avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8; 459177859Sjeff cc->cc_next = NULL; 460177859Sjeff CC_UNLOCK(cc); 4611541Srgrimes} 4621541Srgrimes 4631541Srgrimes/* 4641541Srgrimes * timeout -- 4651541Srgrimes * Execute a function after a specified length of time. 4661541Srgrimes * 4671541Srgrimes * untimeout -- 4681541Srgrimes * Cancel previous timeout function call. 4691541Srgrimes * 47029680Sgibbs * callout_handle_init -- 47129680Sgibbs * Initialize a handle so that using it with untimeout is benign. 47229680Sgibbs * 4731541Srgrimes * See AT&T BCI Driver Reference Manual for specification. This 47429680Sgibbs * implementation differs from that one in that although an 47529680Sgibbs * identification value is returned from timeout, the original 47629680Sgibbs * arguments to timeout as well as the identifier are used to 47729680Sgibbs * identify entries for untimeout. 4781541Srgrimes */ 47929680Sgibbsstruct callout_handle 48029680Sgibbstimeout(ftn, arg, to_ticks) 48133824Sbde timeout_t *ftn; 4821541Srgrimes void *arg; 48369147Sjlemon int to_ticks; 4841541Srgrimes{ 485177859Sjeff struct callout_cpu *cc; 48629680Sgibbs struct callout *new; 48729680Sgibbs struct callout_handle handle; 4881541Srgrimes 489177859Sjeff cc = CC_CPU(timeout_cpu); 490177859Sjeff CC_LOCK(cc); 4911541Srgrimes /* Fill in the next free callout structure. */ 492177859Sjeff new = SLIST_FIRST(&cc->cc_callfree); 49329680Sgibbs if (new == NULL) 49429680Sgibbs /* XXX Attempt to malloc first */ 4951541Srgrimes panic("timeout table full"); 496177859Sjeff SLIST_REMOVE_HEAD(&cc->cc_callfree, c_links.sle); 49744510Swollman callout_reset(new, to_ticks, ftn, arg); 498177859Sjeff handle.callout = new; 499177859Sjeff CC_UNLOCK(cc); 5001541Srgrimes 50129680Sgibbs return (handle); 5021541Srgrimes} 5031541Srgrimes 5041541Srgrimesvoid 50529680Sgibbsuntimeout(ftn, arg, handle) 50633824Sbde timeout_t *ftn; 5071541Srgrimes void *arg; 50829680Sgibbs struct callout_handle handle; 5091541Srgrimes{ 510177859Sjeff struct callout_cpu *cc; 5111541Srgrimes 51229680Sgibbs /* 51329680Sgibbs * Check for a handle that was initialized 51429680Sgibbs * by callout_handle_init, but never used 51529680Sgibbs * for a real timeout. 51629680Sgibbs */ 51729680Sgibbs if (handle.callout == NULL) 51829680Sgibbs return; 51929680Sgibbs 520177859Sjeff cc = callout_lock(handle.callout); 52144510Swollman if (handle.callout->c_func == ftn && handle.callout->c_arg == arg) 52244510Swollman callout_stop(handle.callout); 523177859Sjeff CC_UNLOCK(cc); 5241541Srgrimes} 5251541Srgrimes 52624101Sbdevoid 52729680Sgibbscallout_handle_init(struct callout_handle *handle) 52829680Sgibbs{ 52929680Sgibbs handle->callout = NULL; 53029680Sgibbs} 53129680Sgibbs 53244510Swollman/* 53344510Swollman * New interface; clients allocate their own callout structures. 53444510Swollman * 53544510Swollman * callout_reset() - establish or change a timeout 53644510Swollman * callout_stop() - disestablish a timeout 53744510Swollman * callout_init() - initialize a callout structure so that it can 53844510Swollman * safely be passed to callout_reset() and callout_stop() 53944510Swollman * 54050673Sjlemon * <sys/callout.h> defines three convenience macros: 54144510Swollman * 542140487Scperciva * callout_active() - returns truth if callout has not been stopped, 543140487Scperciva * drained, or deactivated since the last time the callout was 544140487Scperciva * reset. 54550673Sjlemon * callout_pending() - returns truth if callout is still waiting for timeout 54650673Sjlemon * callout_deactivate() - marks the callout as having been serviced 54744510Swollman */ 548149879Sglebiusint 549177859Sjeffcallout_reset_on(struct callout *c, int to_ticks, void (*ftn)(void *), 550177859Sjeff void *arg, int cpu) 55144510Swollman{ 552177859Sjeff struct callout_cpu *cc; 553149879Sglebius int cancelled = 0; 55444510Swollman 555177859Sjeff /* 556177859Sjeff * Don't allow migration of pre-allocated callouts lest they 557177859Sjeff * become unbalanced. 558177859Sjeff */ 559177859Sjeff if (c->c_flags & CALLOUT_LOCAL_ALLOC) 560177859Sjeff cpu = c->c_cpu; 561177859Sjeffretry: 562177859Sjeff cc = callout_lock(c); 563177859Sjeff if (cc->cc_curr == c) { 564127969Scperciva /* 565127969Scperciva * We're being asked to reschedule a callout which is 566173760Sattilio * currently in progress. If there is a lock then we 567141428Siedowse * can cancel the callout if it has not really started. 568127969Scperciva */ 569177859Sjeff if (c->c_lock != NULL && !cc->cc_cancel) 570177859Sjeff cancelled = cc->cc_cancel = 1; 571177859Sjeff if (cc->cc_waiting) { 572141428Siedowse /* 573141428Siedowse * Someone has called callout_drain to kill this 574141428Siedowse * callout. Don't reschedule. 575141428Siedowse */ 576163246Sglebius CTR4(KTR_CALLOUT, "%s %p func %p arg %p", 577163246Sglebius cancelled ? "cancelled" : "failed to cancel", 578163246Sglebius c, c->c_func, c->c_arg); 579177859Sjeff CC_UNLOCK(cc); 580149879Sglebius return (cancelled); 581141428Siedowse } 582128024Scperciva } 583133190Scperciva if (c->c_flags & CALLOUT_PENDING) { 584177859Sjeff if (cc->cc_next == c) { 585177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 586133190Scperciva } 587177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 588133190Scperciva c_links.tqe); 58944510Swollman 590149879Sglebius cancelled = 1; 591177859Sjeff c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 592133190Scperciva } 59344510Swollman /* 594177859Sjeff * If the lock must migrate we have to check the state again as 595177859Sjeff * we can't hold both the new and old locks simultaneously. 59644510Swollman */ 597177859Sjeff if (c->c_cpu != cpu) { 598177859Sjeff c->c_cpu = cpu; 599177859Sjeff CC_UNLOCK(cc); 600177859Sjeff goto retry; 601177859Sjeff } 602177859Sjeff 60344510Swollman if (to_ticks <= 0) 60444510Swollman to_ticks = 1; 60544510Swollman 60644510Swollman c->c_arg = arg; 60769147Sjlemon c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING); 60844510Swollman c->c_func = ftn; 60944510Swollman c->c_time = ticks + to_ticks; 610177859Sjeff TAILQ_INSERT_TAIL(&cc->cc_callwheel[c->c_time & callwheelmask], 61144510Swollman c, c_links.tqe); 612163246Sglebius CTR5(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d", 613163246Sglebius cancelled ? "re" : "", c, c->c_func, c->c_arg, to_ticks); 614177859Sjeff CC_UNLOCK(cc); 615149879Sglebius 616149879Sglebius return (cancelled); 61744510Swollman} 61844510Swollman 61981481Sjhbint 620127969Scperciva_callout_stop_safe(c, safe) 621127969Scperciva struct callout *c; 622127969Scperciva int safe; 623127969Scperciva{ 624177859Sjeff struct callout_cpu *cc; 625173760Sattilio struct lock_class *class; 626173760Sattilio int use_lock, sq_locked; 627127969Scperciva 628173760Sattilio /* 629173760Sattilio * Some old subsystems don't hold Giant while running a callout_stop(), 630173760Sattilio * so just discard this check for the moment. 631173760Sattilio */ 632173760Sattilio if (!safe && c->c_lock != NULL) { 633173760Sattilio if (c->c_lock == &Giant.lock_object) 634173760Sattilio use_lock = mtx_owned(&Giant); 635173760Sattilio else { 636173760Sattilio use_lock = 1; 637173760Sattilio class = LOCK_CLASS(c->c_lock); 638173760Sattilio class->lc_assert(c->c_lock, LA_XLOCKED); 639173760Sattilio } 640173760Sattilio } else 641173760Sattilio use_lock = 0; 642141428Siedowse 643172025Sjhb sq_locked = 0; 644172025Sjhbagain: 645177859Sjeff cc = callout_lock(c); 64644510Swollman /* 647155957Sjhb * If the callout isn't pending, it's not on the queue, so 648155957Sjhb * don't attempt to remove it from the queue. We can try to 649155957Sjhb * stop it by other means however. 65044510Swollman */ 65144510Swollman if (!(c->c_flags & CALLOUT_PENDING)) { 65250673Sjlemon c->c_flags &= ~CALLOUT_ACTIVE; 653155957Sjhb 654155957Sjhb /* 655155957Sjhb * If it wasn't on the queue and it isn't the current 656155957Sjhb * callout, then we can't stop it, so just bail. 657155957Sjhb */ 658177859Sjeff if (cc->cc_curr != c) { 659163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 660163246Sglebius c, c->c_func, c->c_arg); 661177859Sjeff CC_UNLOCK(cc); 662172025Sjhb if (sq_locked) 663177949Sjeff sleepq_release(&cc->cc_waiting); 664141428Siedowse return (0); 665141428Siedowse } 666155957Sjhb 667141428Siedowse if (safe) { 668127969Scperciva /* 669155957Sjhb * The current callout is running (or just 670155957Sjhb * about to run) and blocking is allowed, so 671155957Sjhb * just wait for the current invocation to 672155957Sjhb * finish. 673127969Scperciva */ 674177859Sjeff while (cc->cc_curr == c) { 675171053Sattilio 676171053Sattilio /* 677171053Sattilio * Use direct calls to sleepqueue interface 678171053Sattilio * instead of cv/msleep in order to avoid 679177859Sjeff * a LOR between cc_lock and sleepqueue 680171053Sattilio * chain spinlocks. This piece of code 681171053Sattilio * emulates a msleep_spin() call actually. 682172025Sjhb * 683172025Sjhb * If we already have the sleepqueue chain 684172025Sjhb * locked, then we can safely block. If we 685172025Sjhb * don't already have it locked, however, 686177859Sjeff * we have to drop the cc_lock to lock 687172025Sjhb * it. This opens several races, so we 688172025Sjhb * restart at the beginning once we have 689172025Sjhb * both locks. If nothing has changed, then 690172025Sjhb * we will end up back here with sq_locked 691172025Sjhb * set. 692171053Sattilio */ 693172025Sjhb if (!sq_locked) { 694177859Sjeff CC_UNLOCK(cc); 695177949Sjeff sleepq_lock(&cc->cc_waiting); 696172025Sjhb sq_locked = 1; 697172025Sjhb goto again; 698172025Sjhb } 699177859Sjeff cc->cc_waiting = 1; 700171053Sattilio DROP_GIANT(); 701177859Sjeff CC_UNLOCK(cc); 702177949Sjeff sleepq_add(&cc->cc_waiting, 703177859Sjeff &cc->cc_lock.lock_object, "codrain", 704171053Sattilio SLEEPQ_SLEEP, 0); 705177949Sjeff sleepq_wait(&cc->cc_waiting, 0); 706172025Sjhb sq_locked = 0; 707171053Sattilio 708171053Sattilio /* Reacquire locks previously released. */ 709171053Sattilio PICKUP_GIANT(); 710177859Sjeff CC_LOCK(cc); 711155957Sjhb } 712177859Sjeff } else if (use_lock && !cc->cc_cancel) { 713155957Sjhb /* 714173760Sattilio * The current callout is waiting for its 715173760Sattilio * lock which we hold. Cancel the callout 716155957Sjhb * and return. After our caller drops the 717173760Sattilio * lock, the callout will be skipped in 718155957Sjhb * softclock(). 719155957Sjhb */ 720177859Sjeff cc->cc_cancel = 1; 721163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 722163246Sglebius c, c->c_func, c->c_arg); 723177859Sjeff CC_UNLOCK(cc); 724172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain locked")); 725141428Siedowse return (1); 726155957Sjhb } 727163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 728163246Sglebius c, c->c_func, c->c_arg); 729177859Sjeff CC_UNLOCK(cc); 730172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain still locked")); 73181481Sjhb return (0); 73244510Swollman } 733172025Sjhb if (sq_locked) 734177949Sjeff sleepq_release(&cc->cc_waiting); 735172025Sjhb 73650673Sjlemon c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 73744510Swollman 738177859Sjeff if (cc->cc_next == c) { 739177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 74044510Swollman } 741177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 742177859Sjeff c_links.tqe); 74344510Swollman 744163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 745163246Sglebius c, c->c_func, c->c_arg); 746163246Sglebius 74744510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 748140492Scperciva c->c_func = NULL; 749177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 75044510Swollman } 751177859Sjeff CC_UNLOCK(cc); 75281481Sjhb return (1); 75344510Swollman} 75444510Swollman 75544510Swollmanvoid 75669147Sjlemoncallout_init(c, mpsafe) 75744510Swollman struct callout *c; 75869147Sjlemon int mpsafe; 75944510Swollman{ 76044527Swollman bzero(c, sizeof *c); 761141428Siedowse if (mpsafe) { 762173760Sattilio c->c_lock = NULL; 763141428Siedowse c->c_flags = CALLOUT_RETURNUNLOCKED; 764141428Siedowse } else { 765173760Sattilio c->c_lock = &Giant.lock_object; 766141428Siedowse c->c_flags = 0; 767141428Siedowse } 768177859Sjeff c->c_cpu = timeout_cpu; 76944510Swollman} 77044510Swollman 771141428Siedowsevoid 772173760Sattilio_callout_init_lock(c, lock, flags) 773141428Siedowse struct callout *c; 774173760Sattilio struct lock_object *lock; 775141428Siedowse int flags; 776141428Siedowse{ 777141428Siedowse bzero(c, sizeof *c); 778173760Sattilio c->c_lock = lock; 779173760Sattilio KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0, 780173760Sattilio ("callout_init_lock: bad flags %d", flags)); 781173760Sattilio KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0, 782173760Sattilio ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock")); 783176013Sattilio KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags & 784176013Sattilio (LC_SPINLOCK | LC_SLEEPABLE)), ("%s: invalid lock class", 785173760Sattilio __func__)); 786173760Sattilio c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK); 787177859Sjeff c->c_cpu = timeout_cpu; 788141428Siedowse} 789141428Siedowse 79031950Snate#ifdef APM_FIXUP_CALLTODO 79131950Snate/* 79231950Snate * Adjust the kernel calltodo timeout list. This routine is used after 79331950Snate * an APM resume to recalculate the calltodo timer list values with the 79431950Snate * number of hz's we have been sleeping. The next hardclock() will detect 79531950Snate * that there are fired timers and run softclock() to execute them. 79631950Snate * 79731950Snate * Please note, I have not done an exhaustive analysis of what code this 79831950Snate * might break. I am motivated to have my select()'s and alarm()'s that 79931950Snate * have expired during suspend firing upon resume so that the applications 80031950Snate * which set the timer can do the maintanence the timer was for as close 80131950Snate * as possible to the originally intended time. Testing this code for a 80231950Snate * week showed that resuming from a suspend resulted in 22 to 25 timers 80331950Snate * firing, which seemed independant on whether the suspend was 2 hours or 80431950Snate * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 80531950Snate */ 80631950Snatevoid 80731950Snateadjust_timeout_calltodo(time_change) 80831950Snate struct timeval *time_change; 80931950Snate{ 81031950Snate register struct callout *p; 81131950Snate unsigned long delta_ticks; 81231950Snate 81331950Snate /* 81431950Snate * How many ticks were we asleep? 81536127Sbde * (stolen from tvtohz()). 81631950Snate */ 81731950Snate 81831950Snate /* Don't do anything */ 81931950Snate if (time_change->tv_sec < 0) 82031950Snate return; 82131950Snate else if (time_change->tv_sec <= LONG_MAX / 1000000) 82231950Snate delta_ticks = (time_change->tv_sec * 1000000 + 82331950Snate time_change->tv_usec + (tick - 1)) / tick + 1; 82431950Snate else if (time_change->tv_sec <= LONG_MAX / hz) 82531950Snate delta_ticks = time_change->tv_sec * hz + 82631950Snate (time_change->tv_usec + (tick - 1)) / tick + 1; 82731950Snate else 82831950Snate delta_ticks = LONG_MAX; 82931950Snate 83031950Snate if (delta_ticks > INT_MAX) 83131950Snate delta_ticks = INT_MAX; 83231950Snate 83331950Snate /* 83431950Snate * Now rip through the timer calltodo list looking for timers 83531950Snate * to expire. 83631950Snate */ 83731950Snate 83831950Snate /* don't collide with softclock() */ 839177859Sjeff CC_LOCK(cc); 84031950Snate for (p = calltodo.c_next; p != NULL; p = p->c_next) { 84131950Snate p->c_time -= delta_ticks; 84231950Snate 84331950Snate /* Break if the timer had more time on it than delta_ticks */ 84431950Snate if (p->c_time > 0) 84531950Snate break; 84631950Snate 84731950Snate /* take back the ticks the timer didn't use (p->c_time <= 0) */ 84831950Snate delta_ticks = -p->c_time; 84931950Snate } 850177859Sjeff CC_UNLOCK(cc); 85131950Snate 85231950Snate return; 85331950Snate} 85431950Snate#endif /* APM_FIXUP_CALLTODO */ 855