kern_timeout.c revision 200510
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 200510 2009-12-14 12:23:46Z luigi $"); 39116182Sobrien 40187664Srwatson#include "opt_kdtrace.h" 41187664Srwatson 421541Srgrimes#include <sys/param.h> 431541Srgrimes#include <sys/systm.h> 44177859Sjeff#include <sys/bus.h> 4533392Sphk#include <sys/callout.h> 46127969Scperciva#include <sys/condvar.h> 47177859Sjeff#include <sys/interrupt.h> 481541Srgrimes#include <sys/kernel.h> 49133229Srwatson#include <sys/ktr.h> 5074914Sjhb#include <sys/lock.h> 51177859Sjeff#include <sys/malloc.h> 5268840Sjhb#include <sys/mutex.h> 53150188Sjhb#include <sys/proc.h> 54187664Srwatson#include <sys/sdt.h> 55171053Sattilio#include <sys/sleepqueue.h> 56115810Sphk#include <sys/sysctl.h> 57177859Sjeff#include <sys/smp.h> 581541Srgrimes 59187664SrwatsonSDT_PROVIDER_DEFINE(callout_execute); 60187664SrwatsonSDT_PROBE_DEFINE(callout_execute, kernel, , callout_start); 61187664SrwatsonSDT_PROBE_ARGTYPE(callout_execute, kernel, , callout_start, 0, 62187664Srwatson "struct callout *"); 63187664SrwatsonSDT_PROBE_DEFINE(callout_execute, kernel, , callout_end); 64187664SrwatsonSDT_PROBE_ARGTYPE(callout_execute, kernel, , callout_end, 0, 65187664Srwatson "struct callout *"); 66187664Srwatson 67115810Sphkstatic int avg_depth; 68115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0, 69115810Sphk "Average number of items examined per softclock call. Units = 1/1000"); 70115810Sphkstatic int avg_gcalls; 71115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0, 72115810Sphk "Average number of Giant callouts made per softclock call. Units = 1/1000"); 73173760Sattiliostatic int avg_lockcalls; 74173760SattilioSYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0, 75173760Sattilio "Average number of lock callouts made per softclock call. Units = 1/1000"); 76115810Sphkstatic int avg_mpcalls; 77115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0, 78115810Sphk "Average number of MP callouts made per softclock call. Units = 1/1000"); 7933392Sphk/* 8033392Sphk * TODO: 8133392Sphk * allocate more timeout table slots when table overflows. 8233392Sphk */ 8329680Sgibbsint callwheelsize, callwheelbits, callwheelmask; 842112Swollman 85200510Sluigi/* 86200510Sluigi * There is one struct callout_cpu per cpu, holding all relevant 87200510Sluigi * state for the callout processing thread on the individual CPU. 88200510Sluigi * In particular: 89200510Sluigi * cc_ticks is incremented once per tick in callout_cpu(). 90200510Sluigi * It tracks the global 'ticks' but in a way that the individual 91200510Sluigi * threads should not worry about races in the order in which 92200510Sluigi * hardclock() and hardclock_cpu() run on the various CPUs. 93200510Sluigi * cc_softclock is advanced in callout_cpu() to point to the 94200510Sluigi * first entry in cc_callwheel that may need handling. In turn, 95200510Sluigi * a softclock() is scheduled so it can serve the various entries i 96200510Sluigi * such that cc_softclock <= i <= cc_ticks . 97200510Sluigi * XXX maybe cc_softclock and cc_ticks should be volatile ? 98200510Sluigi * 99200510Sluigi * cc_ticks is also used in callout_reset_cpu() to determine 100200510Sluigi * when the callout should be served. 101200510Sluigi */ 102177859Sjeffstruct callout_cpu { 103177859Sjeff struct mtx cc_lock; 104177859Sjeff struct callout *cc_callout; 105177859Sjeff struct callout_tailq *cc_callwheel; 106177859Sjeff struct callout_list cc_callfree; 107177859Sjeff struct callout *cc_next; 108177859Sjeff struct callout *cc_curr; 109177859Sjeff void *cc_cookie; 110200510Sluigi int cc_ticks; 111177859Sjeff int cc_softticks; 112177859Sjeff int cc_cancel; 113177859Sjeff int cc_waiting; 114177859Sjeff}; 115128024Scperciva 116177859Sjeff#ifdef SMP 117177859Sjeffstruct callout_cpu cc_cpu[MAXCPU]; 118177859Sjeff#define CC_CPU(cpu) (&cc_cpu[(cpu)]) 119177859Sjeff#define CC_SELF() CC_CPU(PCPU_GET(cpuid)) 120177859Sjeff#else 121177859Sjeffstruct callout_cpu cc_cpu; 122177859Sjeff#define CC_CPU(cpu) &cc_cpu 123177859Sjeff#define CC_SELF() &cc_cpu 124177859Sjeff#endif 125177859Sjeff#define CC_LOCK(cc) mtx_lock_spin(&(cc)->cc_lock) 126177859Sjeff#define CC_UNLOCK(cc) mtx_unlock_spin(&(cc)->cc_lock) 127177859Sjeff 128177859Sjeffstatic int timeout_cpu; 129177859Sjeff 130177859SjeffMALLOC_DEFINE(M_CALLOUT, "callout", "Callout datastructures"); 131177859Sjeff 132139831Scperciva/** 133177859Sjeff * Locked by cc_lock: 134177859Sjeff * cc_curr - If a callout is in progress, it is curr_callout. 135155957Sjhb * If curr_callout is non-NULL, threads waiting in 136177859Sjeff * callout_drain() will be woken up as soon as the 137127969Scperciva * relevant callout completes. 138177859Sjeff * cc_cancel - Changing to 1 with both callout_lock and c_lock held 139141428Siedowse * guarantees that the current callout will not run. 140141428Siedowse * The softclock() function sets this to 0 before it 141173760Sattilio * drops callout_lock to acquire c_lock, and it calls 142155957Sjhb * the handler only if curr_cancelled is still 0 after 143173760Sattilio * c_lock is successfully acquired. 144177859Sjeff * cc_waiting - If a thread is waiting in callout_drain(), then 145155957Sjhb * callout_wait is nonzero. Set only when 146128024Scperciva * curr_callout is non-NULL. 147127969Scperciva */ 148128024Scperciva 1491541Srgrimes/* 15082127Sdillon * kern_timeout_callwheel_alloc() - kernel low level callwheel initialization 15182127Sdillon * 15282127Sdillon * This code is called very early in the kernel initialization sequence, 15382127Sdillon * and may be called more then once. 15482127Sdillon */ 15582127Sdilloncaddr_t 15682127Sdillonkern_timeout_callwheel_alloc(caddr_t v) 15782127Sdillon{ 158177859Sjeff struct callout_cpu *cc; 159177859Sjeff 160177859Sjeff timeout_cpu = PCPU_GET(cpuid); 161177859Sjeff cc = CC_CPU(timeout_cpu); 16282127Sdillon /* 16382127Sdillon * Calculate callout wheel size 16482127Sdillon */ 16582127Sdillon for (callwheelsize = 1, callwheelbits = 0; 16682127Sdillon callwheelsize < ncallout; 16782127Sdillon callwheelsize <<= 1, ++callwheelbits) 16882127Sdillon ; 16982127Sdillon callwheelmask = callwheelsize - 1; 17082127Sdillon 171177859Sjeff cc->cc_callout = (struct callout *)v; 172177859Sjeff v = (caddr_t)(cc->cc_callout + ncallout); 173177859Sjeff cc->cc_callwheel = (struct callout_tailq *)v; 174177859Sjeff v = (caddr_t)(cc->cc_callwheel + callwheelsize); 17582127Sdillon return(v); 17682127Sdillon} 17782127Sdillon 178177859Sjeffstatic void 179177859Sjeffcallout_cpu_init(struct callout_cpu *cc) 180177859Sjeff{ 181177859Sjeff struct callout *c; 182177859Sjeff int i; 183177859Sjeff 184177859Sjeff mtx_init(&cc->cc_lock, "callout", NULL, MTX_SPIN | MTX_RECURSE); 185177859Sjeff SLIST_INIT(&cc->cc_callfree); 186177859Sjeff for (i = 0; i < callwheelsize; i++) { 187177859Sjeff TAILQ_INIT(&cc->cc_callwheel[i]); 188177859Sjeff } 189177859Sjeff if (cc->cc_callout == NULL) 190177859Sjeff return; 191177859Sjeff for (i = 0; i < ncallout; i++) { 192177859Sjeff c = &cc->cc_callout[i]; 193177859Sjeff callout_init(c, 0); 194177859Sjeff c->c_flags = CALLOUT_LOCAL_ALLOC; 195177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 196177859Sjeff } 197177859Sjeff} 198177859Sjeff 19982127Sdillon/* 20082127Sdillon * kern_timeout_callwheel_init() - initialize previously reserved callwheel 20182127Sdillon * space. 20282127Sdillon * 20382127Sdillon * This code is called just once, after the space reserved for the 20482127Sdillon * callout wheel has been finalized. 20582127Sdillon */ 20682127Sdillonvoid 20782127Sdillonkern_timeout_callwheel_init(void) 20882127Sdillon{ 209177859Sjeff callout_cpu_init(CC_CPU(timeout_cpu)); 210177859Sjeff} 21182127Sdillon 212177859Sjeff/* 213177859Sjeff * Start standard softclock thread. 214177859Sjeff */ 215177859Sjeffvoid *softclock_ih; 216177859Sjeff 217177859Sjeffstatic void 218177859Sjeffstart_softclock(void *dummy) 219177859Sjeff{ 220177859Sjeff struct callout_cpu *cc; 221177859Sjeff#ifdef SMP 222177859Sjeff int cpu; 223177859Sjeff#endif 224177859Sjeff 225177859Sjeff cc = CC_CPU(timeout_cpu); 226177859Sjeff if (swi_add(&clk_intr_event, "clock", softclock, cc, SWI_CLOCK, 227177859Sjeff INTR_MPSAFE, &softclock_ih)) 228177859Sjeff panic("died while creating standard software ithreads"); 229177859Sjeff cc->cc_cookie = softclock_ih; 230177859Sjeff#ifdef SMP 231177859Sjeff for (cpu = 0; cpu <= mp_maxid; cpu++) { 232177859Sjeff if (cpu == timeout_cpu) 233177859Sjeff continue; 234177859Sjeff if (CPU_ABSENT(cpu)) 235177859Sjeff continue; 236177859Sjeff cc = CC_CPU(cpu); 237177859Sjeff if (swi_add(NULL, "clock", softclock, cc, SWI_CLOCK, 238177859Sjeff INTR_MPSAFE, &cc->cc_cookie)) 239177859Sjeff panic("died while creating standard software ithreads"); 240177859Sjeff cc->cc_callout = NULL; /* Only cpu0 handles timeout(). */ 241177859Sjeff cc->cc_callwheel = malloc( 242177859Sjeff sizeof(struct callout_tailq) * callwheelsize, M_CALLOUT, 243177859Sjeff M_WAITOK); 244177859Sjeff callout_cpu_init(cc); 24582127Sdillon } 246177859Sjeff#endif 247177859Sjeff} 248177859Sjeff 249177859SjeffSYSINIT(start_softclock, SI_SUB_SOFTINTR, SI_ORDER_FIRST, start_softclock, NULL); 250177859Sjeff 251177859Sjeffvoid 252177859Sjeffcallout_tick(void) 253177859Sjeff{ 254177859Sjeff struct callout_cpu *cc; 255180608Sjeff int need_softclock; 256180608Sjeff int bucket; 257177859Sjeff 258177859Sjeff /* 259177859Sjeff * Process callouts at a very low cpu priority, so we don't keep the 260177859Sjeff * relatively high clock interrupt priority any longer than necessary. 261177859Sjeff */ 262180608Sjeff need_softclock = 0; 263177859Sjeff cc = CC_SELF(); 264177859Sjeff mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET); 265200510Sluigi cc->cc_ticks++; 266200510Sluigi for (; (cc->cc_softticks - cc->cc_ticks) <= 0; cc->cc_softticks++) { 267180608Sjeff bucket = cc->cc_softticks & callwheelmask; 268180608Sjeff if (!TAILQ_EMPTY(&cc->cc_callwheel[bucket])) { 269180608Sjeff need_softclock = 1; 270180608Sjeff break; 271180608Sjeff } 272180608Sjeff } 273177859Sjeff mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET); 274177859Sjeff /* 275177859Sjeff * swi_sched acquires the thread lock, so we don't want to call it 276177859Sjeff * with cc_lock held; incorrect locking order. 277177859Sjeff */ 278177859Sjeff if (need_softclock) 279177859Sjeff swi_sched(cc->cc_cookie, 0); 280177859Sjeff} 281177859Sjeff 282177859Sjeffstatic struct callout_cpu * 283177859Sjeffcallout_lock(struct callout *c) 284177859Sjeff{ 285177859Sjeff struct callout_cpu *cc; 286177859Sjeff int cpu; 287177859Sjeff 288177859Sjeff for (;;) { 289177859Sjeff cpu = c->c_cpu; 290177859Sjeff cc = CC_CPU(cpu); 291177859Sjeff CC_LOCK(cc); 292177859Sjeff if (cpu == c->c_cpu) 293177859Sjeff break; 294177859Sjeff CC_UNLOCK(cc); 29582127Sdillon } 296177859Sjeff return (cc); 29782127Sdillon} 29882127Sdillon 29982127Sdillon/* 30029680Sgibbs * The callout mechanism is based on the work of Adam M. Costello and 30129680Sgibbs * George Varghese, published in a technical report entitled "Redesigning 30229680Sgibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion 30329680Sgibbs * in FreeBSD by Justin T. Gibbs. The original work on the data structures 304128630Shmp * used in this implementation was published by G. Varghese and T. Lauck in 30529680Sgibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 30629680Sgibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of 30729680Sgibbs * the 11th ACM Annual Symposium on Operating Systems Principles, 30829680Sgibbs * Austin, Texas Nov 1987. 30929680Sgibbs */ 31032388Sphk 31129680Sgibbs/* 3121541Srgrimes * Software (low priority) clock interrupt. 3131541Srgrimes * Run periodic events from timeout queue. 3141541Srgrimes */ 3151541Srgrimesvoid 316177859Sjeffsoftclock(void *arg) 3171541Srgrimes{ 318177859Sjeff struct callout_cpu *cc; 319102936Sphk struct callout *c; 320102936Sphk struct callout_tailq *bucket; 321102936Sphk int curticks; 322102936Sphk int steps; /* #steps since we last allowed interrupts */ 323115810Sphk int depth; 324115810Sphk int mpcalls; 325173760Sattilio int lockcalls; 326115810Sphk int gcalls; 327122585Smckusick#ifdef DIAGNOSTIC 328122585Smckusick struct bintime bt1, bt2; 329122585Smckusick struct timespec ts2; 330122585Smckusick static uint64_t maxdt = 36893488147419102LL; /* 2 msec */ 331123254Sphk static timeout_t *lastfunc; 332122585Smckusick#endif 3331541Srgrimes 33433392Sphk#ifndef MAX_SOFTCLOCK_STEPS 33533392Sphk#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 33633392Sphk#endif /* MAX_SOFTCLOCK_STEPS */ 33729680Sgibbs 338115810Sphk mpcalls = 0; 339173760Sattilio lockcalls = 0; 340115810Sphk gcalls = 0; 341115810Sphk depth = 0; 34229680Sgibbs steps = 0; 343177859Sjeff cc = (struct callout_cpu *)arg; 344177859Sjeff CC_LOCK(cc); 345200510Sluigi while (cc->cc_softticks - 1 != cc->cc_ticks) { 34629805Sgibbs /* 347177859Sjeff * cc_softticks may be modified by hard clock, so cache 34829805Sgibbs * it while we work on a given bucket. 34929805Sgibbs */ 350177859Sjeff curticks = cc->cc_softticks; 351180608Sjeff cc->cc_softticks++; 352177859Sjeff bucket = &cc->cc_callwheel[curticks & callwheelmask]; 35329805Sgibbs c = TAILQ_FIRST(bucket); 35429680Sgibbs while (c) { 355115810Sphk depth++; 35629805Sgibbs if (c->c_time != curticks) { 35729680Sgibbs c = TAILQ_NEXT(c, c_links.tqe); 35829680Sgibbs ++steps; 35929680Sgibbs if (steps >= MAX_SOFTCLOCK_STEPS) { 360177859Sjeff cc->cc_next = c; 36129805Sgibbs /* Give interrupts a chance. */ 362177859Sjeff CC_UNLOCK(cc); 36381370Sjhb ; /* nothing */ 364177859Sjeff CC_LOCK(cc); 365177859Sjeff c = cc->cc_next; 36629680Sgibbs steps = 0; 36729680Sgibbs } 36829680Sgibbs } else { 36929680Sgibbs void (*c_func)(void *); 37029680Sgibbs void *c_arg; 371173760Sattilio struct lock_class *class; 372173842Sattilio struct lock_object *c_lock; 373173760Sattilio int c_flags, sharedlock; 37429680Sgibbs 375177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 37629805Sgibbs TAILQ_REMOVE(bucket, c, c_links.tqe); 377173760Sattilio class = (c->c_lock != NULL) ? 378173760Sattilio LOCK_CLASS(c->c_lock) : NULL; 379173760Sattilio sharedlock = (c->c_flags & CALLOUT_SHAREDLOCK) ? 380173760Sattilio 0 : 1; 381173842Sattilio c_lock = c->c_lock; 38229680Sgibbs c_func = c->c_func; 38329680Sgibbs c_arg = c->c_arg; 38468889Sjake c_flags = c->c_flags; 38544510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 38644510Swollman c->c_flags = CALLOUT_LOCAL_ALLOC; 38744510Swollman } else { 38844510Swollman c->c_flags = 38950673Sjlemon (c->c_flags & ~CALLOUT_PENDING); 39044510Swollman } 391177859Sjeff cc->cc_curr = c; 392177859Sjeff cc->cc_cancel = 0; 393177859Sjeff CC_UNLOCK(cc); 394173842Sattilio if (c_lock != NULL) { 395173842Sattilio class->lc_lock(c_lock, sharedlock); 396141428Siedowse /* 397141428Siedowse * The callout may have been cancelled 398141428Siedowse * while we switched locks. 399141428Siedowse */ 400177859Sjeff if (cc->cc_cancel) { 401173842Sattilio class->lc_unlock(c_lock); 402155957Sjhb goto skip; 403141428Siedowse } 404141428Siedowse /* The callout cannot be stopped now. */ 405177859Sjeff cc->cc_cancel = 1; 406141428Siedowse 407173842Sattilio if (c_lock == &Giant.lock_object) { 408141428Siedowse gcalls++; 409163246Sglebius CTR3(KTR_CALLOUT, 410163246Sglebius "callout %p func %p arg %p", 411163246Sglebius c, c_func, c_arg); 412141428Siedowse } else { 413173760Sattilio lockcalls++; 414173760Sattilio CTR3(KTR_CALLOUT, "callout lock" 415163246Sglebius " %p func %p arg %p", 416163246Sglebius c, c_func, c_arg); 417141428Siedowse } 418115810Sphk } else { 419115810Sphk mpcalls++; 420163246Sglebius CTR3(KTR_CALLOUT, 421163246Sglebius "callout mpsafe %p func %p arg %p", 422163246Sglebius c, c_func, c_arg); 423115810Sphk } 424122585Smckusick#ifdef DIAGNOSTIC 425122585Smckusick binuptime(&bt1); 426122585Smckusick#endif 427150187Sjhb THREAD_NO_SLEEPING(); 428187664Srwatson SDT_PROBE(callout_execute, kernel, , 429187664Srwatson callout_start, c, 0, 0, 0, 0); 43029680Sgibbs c_func(c_arg); 431187664Srwatson SDT_PROBE(callout_execute, kernel, , 432187664Srwatson callout_end, c, 0, 0, 0, 0); 433150187Sjhb THREAD_SLEEPING_OK(); 434122585Smckusick#ifdef DIAGNOSTIC 435122585Smckusick binuptime(&bt2); 436122585Smckusick bintime_sub(&bt2, &bt1); 437122585Smckusick if (bt2.frac > maxdt) { 438123254Sphk if (lastfunc != c_func || 439123254Sphk bt2.frac > maxdt * 2) { 440123254Sphk bintime2timespec(&bt2, &ts2); 441123254Sphk printf( 442123254Sphk "Expensive timeout(9) function: %p(%p) %jd.%09ld s\n", 443123254Sphk c_func, c_arg, 444123254Sphk (intmax_t)ts2.tv_sec, 445123254Sphk ts2.tv_nsec); 446123254Sphk } 447122585Smckusick maxdt = bt2.frac; 448123254Sphk lastfunc = c_func; 449122585Smckusick } 450122585Smckusick#endif 451187150Sjhb CTR1(KTR_CALLOUT, "callout %p finished", c); 452141428Siedowse if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0) 453173842Sattilio class->lc_unlock(c_lock); 454155957Sjhb skip: 455177859Sjeff CC_LOCK(cc); 456177491Salfred /* 457177491Salfred * If the current callout is locally 458177491Salfred * allocated (from timeout(9)) 459177491Salfred * then put it on the freelist. 460177491Salfred * 461177491Salfred * Note: we need to check the cached 462177491Salfred * copy of c_flags because if it was not 463177491Salfred * local, then it's not safe to deref the 464177491Salfred * callout pointer. 465177491Salfred */ 466177491Salfred if (c_flags & CALLOUT_LOCAL_ALLOC) { 467177491Salfred KASSERT(c->c_flags == 468177491Salfred CALLOUT_LOCAL_ALLOC, 469177491Salfred ("corrupted callout")); 470177491Salfred c->c_func = NULL; 471177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, 472177491Salfred c_links.sle); 473177491Salfred } 474177859Sjeff cc->cc_curr = NULL; 475177859Sjeff if (cc->cc_waiting) { 476127969Scperciva /* 477155957Sjhb * There is someone waiting 478127969Scperciva * for the callout to complete. 479127969Scperciva */ 480177859Sjeff cc->cc_waiting = 0; 481177859Sjeff CC_UNLOCK(cc); 482177859Sjeff wakeup(&cc->cc_waiting); 483177859Sjeff CC_LOCK(cc); 484128024Scperciva } 48529680Sgibbs steps = 0; 486177859Sjeff c = cc->cc_next; 48729680Sgibbs } 48829680Sgibbs } 4891541Srgrimes } 490115810Sphk avg_depth += (depth * 1000 - avg_depth) >> 8; 491115810Sphk avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8; 492173760Sattilio avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8; 493115810Sphk avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8; 494177859Sjeff cc->cc_next = NULL; 495177859Sjeff CC_UNLOCK(cc); 4961541Srgrimes} 4971541Srgrimes 4981541Srgrimes/* 4991541Srgrimes * timeout -- 5001541Srgrimes * Execute a function after a specified length of time. 5011541Srgrimes * 5021541Srgrimes * untimeout -- 5031541Srgrimes * Cancel previous timeout function call. 5041541Srgrimes * 50529680Sgibbs * callout_handle_init -- 50629680Sgibbs * Initialize a handle so that using it with untimeout is benign. 50729680Sgibbs * 5081541Srgrimes * See AT&T BCI Driver Reference Manual for specification. This 50929680Sgibbs * implementation differs from that one in that although an 51029680Sgibbs * identification value is returned from timeout, the original 51129680Sgibbs * arguments to timeout as well as the identifier are used to 51229680Sgibbs * identify entries for untimeout. 5131541Srgrimes */ 51429680Sgibbsstruct callout_handle 51529680Sgibbstimeout(ftn, arg, to_ticks) 51633824Sbde timeout_t *ftn; 5171541Srgrimes void *arg; 51869147Sjlemon int to_ticks; 5191541Srgrimes{ 520177859Sjeff struct callout_cpu *cc; 52129680Sgibbs struct callout *new; 52229680Sgibbs struct callout_handle handle; 5231541Srgrimes 524177859Sjeff cc = CC_CPU(timeout_cpu); 525177859Sjeff CC_LOCK(cc); 5261541Srgrimes /* Fill in the next free callout structure. */ 527177859Sjeff new = SLIST_FIRST(&cc->cc_callfree); 52829680Sgibbs if (new == NULL) 52929680Sgibbs /* XXX Attempt to malloc first */ 5301541Srgrimes panic("timeout table full"); 531177859Sjeff SLIST_REMOVE_HEAD(&cc->cc_callfree, c_links.sle); 53244510Swollman callout_reset(new, to_ticks, ftn, arg); 533177859Sjeff handle.callout = new; 534177859Sjeff CC_UNLOCK(cc); 5351541Srgrimes 53629680Sgibbs return (handle); 5371541Srgrimes} 5381541Srgrimes 5391541Srgrimesvoid 54029680Sgibbsuntimeout(ftn, arg, handle) 54133824Sbde timeout_t *ftn; 5421541Srgrimes void *arg; 54329680Sgibbs struct callout_handle handle; 5441541Srgrimes{ 545177859Sjeff struct callout_cpu *cc; 5461541Srgrimes 54729680Sgibbs /* 54829680Sgibbs * Check for a handle that was initialized 54929680Sgibbs * by callout_handle_init, but never used 55029680Sgibbs * for a real timeout. 55129680Sgibbs */ 55229680Sgibbs if (handle.callout == NULL) 55329680Sgibbs return; 55429680Sgibbs 555177859Sjeff cc = callout_lock(handle.callout); 55644510Swollman if (handle.callout->c_func == ftn && handle.callout->c_arg == arg) 55744510Swollman callout_stop(handle.callout); 558177859Sjeff CC_UNLOCK(cc); 5591541Srgrimes} 5601541Srgrimes 56124101Sbdevoid 56229680Sgibbscallout_handle_init(struct callout_handle *handle) 56329680Sgibbs{ 56429680Sgibbs handle->callout = NULL; 56529680Sgibbs} 56629680Sgibbs 56744510Swollman/* 56844510Swollman * New interface; clients allocate their own callout structures. 56944510Swollman * 57044510Swollman * callout_reset() - establish or change a timeout 57144510Swollman * callout_stop() - disestablish a timeout 57244510Swollman * callout_init() - initialize a callout structure so that it can 57344510Swollman * safely be passed to callout_reset() and callout_stop() 57444510Swollman * 57550673Sjlemon * <sys/callout.h> defines three convenience macros: 57644510Swollman * 577140487Scperciva * callout_active() - returns truth if callout has not been stopped, 578140487Scperciva * drained, or deactivated since the last time the callout was 579140487Scperciva * reset. 58050673Sjlemon * callout_pending() - returns truth if callout is still waiting for timeout 58150673Sjlemon * callout_deactivate() - marks the callout as having been serviced 58244510Swollman */ 583149879Sglebiusint 584177859Sjeffcallout_reset_on(struct callout *c, int to_ticks, void (*ftn)(void *), 585177859Sjeff void *arg, int cpu) 58644510Swollman{ 587177859Sjeff struct callout_cpu *cc; 588149879Sglebius int cancelled = 0; 58944510Swollman 590177859Sjeff /* 591177859Sjeff * Don't allow migration of pre-allocated callouts lest they 592177859Sjeff * become unbalanced. 593177859Sjeff */ 594177859Sjeff if (c->c_flags & CALLOUT_LOCAL_ALLOC) 595177859Sjeff cpu = c->c_cpu; 596177859Sjeffretry: 597177859Sjeff cc = callout_lock(c); 598177859Sjeff if (cc->cc_curr == c) { 599127969Scperciva /* 600127969Scperciva * We're being asked to reschedule a callout which is 601173760Sattilio * currently in progress. If there is a lock then we 602141428Siedowse * can cancel the callout if it has not really started. 603127969Scperciva */ 604177859Sjeff if (c->c_lock != NULL && !cc->cc_cancel) 605177859Sjeff cancelled = cc->cc_cancel = 1; 606177859Sjeff if (cc->cc_waiting) { 607141428Siedowse /* 608141428Siedowse * Someone has called callout_drain to kill this 609141428Siedowse * callout. Don't reschedule. 610141428Siedowse */ 611163246Sglebius CTR4(KTR_CALLOUT, "%s %p func %p arg %p", 612163246Sglebius cancelled ? "cancelled" : "failed to cancel", 613163246Sglebius c, c->c_func, c->c_arg); 614177859Sjeff CC_UNLOCK(cc); 615149879Sglebius return (cancelled); 616141428Siedowse } 617128024Scperciva } 618133190Scperciva if (c->c_flags & CALLOUT_PENDING) { 619177859Sjeff if (cc->cc_next == c) { 620177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 621133190Scperciva } 622177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 623133190Scperciva c_links.tqe); 62444510Swollman 625149879Sglebius cancelled = 1; 626177859Sjeff c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 627133190Scperciva } 62844510Swollman /* 629177859Sjeff * If the lock must migrate we have to check the state again as 630177859Sjeff * we can't hold both the new and old locks simultaneously. 63144510Swollman */ 632177859Sjeff if (c->c_cpu != cpu) { 633177859Sjeff c->c_cpu = cpu; 634177859Sjeff CC_UNLOCK(cc); 635177859Sjeff goto retry; 636177859Sjeff } 637177859Sjeff 63844510Swollman if (to_ticks <= 0) 63944510Swollman to_ticks = 1; 64044510Swollman 64144510Swollman c->c_arg = arg; 64269147Sjlemon c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING); 64344510Swollman c->c_func = ftn; 644200510Sluigi c->c_time = cc->cc_ticks + to_ticks; 645177859Sjeff TAILQ_INSERT_TAIL(&cc->cc_callwheel[c->c_time & callwheelmask], 64644510Swollman c, c_links.tqe); 647163246Sglebius CTR5(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d", 648163246Sglebius cancelled ? "re" : "", c, c->c_func, c->c_arg, to_ticks); 649177859Sjeff CC_UNLOCK(cc); 650149879Sglebius 651149879Sglebius return (cancelled); 65244510Swollman} 65344510Swollman 654181191Ssam/* 655181191Ssam * Common idioms that can be optimized in the future. 656181191Ssam */ 65781481Sjhbint 658181191Ssamcallout_schedule_on(struct callout *c, int to_ticks, int cpu) 659181191Ssam{ 660181191Ssam return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, cpu); 661181191Ssam} 662181191Ssam 663181191Ssamint 664181191Ssamcallout_schedule(struct callout *c, int to_ticks) 665181191Ssam{ 666181191Ssam return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, c->c_cpu); 667181191Ssam} 668181191Ssam 669181191Ssamint 670127969Scperciva_callout_stop_safe(c, safe) 671127969Scperciva struct callout *c; 672127969Scperciva int safe; 673127969Scperciva{ 674177859Sjeff struct callout_cpu *cc; 675173760Sattilio struct lock_class *class; 676173760Sattilio int use_lock, sq_locked; 677127969Scperciva 678173760Sattilio /* 679173760Sattilio * Some old subsystems don't hold Giant while running a callout_stop(), 680173760Sattilio * so just discard this check for the moment. 681173760Sattilio */ 682173760Sattilio if (!safe && c->c_lock != NULL) { 683173760Sattilio if (c->c_lock == &Giant.lock_object) 684173760Sattilio use_lock = mtx_owned(&Giant); 685173760Sattilio else { 686173760Sattilio use_lock = 1; 687173760Sattilio class = LOCK_CLASS(c->c_lock); 688173760Sattilio class->lc_assert(c->c_lock, LA_XLOCKED); 689173760Sattilio } 690173760Sattilio } else 691173760Sattilio use_lock = 0; 692141428Siedowse 693172025Sjhb sq_locked = 0; 694172025Sjhbagain: 695177859Sjeff cc = callout_lock(c); 69644510Swollman /* 697155957Sjhb * If the callout isn't pending, it's not on the queue, so 698155957Sjhb * don't attempt to remove it from the queue. We can try to 699155957Sjhb * stop it by other means however. 70044510Swollman */ 70144510Swollman if (!(c->c_flags & CALLOUT_PENDING)) { 70250673Sjlemon c->c_flags &= ~CALLOUT_ACTIVE; 703155957Sjhb 704155957Sjhb /* 705155957Sjhb * If it wasn't on the queue and it isn't the current 706155957Sjhb * callout, then we can't stop it, so just bail. 707155957Sjhb */ 708177859Sjeff if (cc->cc_curr != c) { 709163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 710163246Sglebius c, c->c_func, c->c_arg); 711177859Sjeff CC_UNLOCK(cc); 712172025Sjhb if (sq_locked) 713177949Sjeff sleepq_release(&cc->cc_waiting); 714141428Siedowse return (0); 715141428Siedowse } 716155957Sjhb 717141428Siedowse if (safe) { 718127969Scperciva /* 719155957Sjhb * The current callout is running (or just 720155957Sjhb * about to run) and blocking is allowed, so 721155957Sjhb * just wait for the current invocation to 722155957Sjhb * finish. 723127969Scperciva */ 724177859Sjeff while (cc->cc_curr == c) { 725171053Sattilio 726171053Sattilio /* 727171053Sattilio * Use direct calls to sleepqueue interface 728171053Sattilio * instead of cv/msleep in order to avoid 729177859Sjeff * a LOR between cc_lock and sleepqueue 730171053Sattilio * chain spinlocks. This piece of code 731171053Sattilio * emulates a msleep_spin() call actually. 732172025Sjhb * 733172025Sjhb * If we already have the sleepqueue chain 734172025Sjhb * locked, then we can safely block. If we 735172025Sjhb * don't already have it locked, however, 736177859Sjeff * we have to drop the cc_lock to lock 737172025Sjhb * it. This opens several races, so we 738172025Sjhb * restart at the beginning once we have 739172025Sjhb * both locks. If nothing has changed, then 740172025Sjhb * we will end up back here with sq_locked 741172025Sjhb * set. 742171053Sattilio */ 743172025Sjhb if (!sq_locked) { 744177859Sjeff CC_UNLOCK(cc); 745177949Sjeff sleepq_lock(&cc->cc_waiting); 746172025Sjhb sq_locked = 1; 747172025Sjhb goto again; 748172025Sjhb } 749177859Sjeff cc->cc_waiting = 1; 750171053Sattilio DROP_GIANT(); 751177859Sjeff CC_UNLOCK(cc); 752177949Sjeff sleepq_add(&cc->cc_waiting, 753177859Sjeff &cc->cc_lock.lock_object, "codrain", 754171053Sattilio SLEEPQ_SLEEP, 0); 755177949Sjeff sleepq_wait(&cc->cc_waiting, 0); 756172025Sjhb sq_locked = 0; 757171053Sattilio 758171053Sattilio /* Reacquire locks previously released. */ 759171053Sattilio PICKUP_GIANT(); 760177859Sjeff CC_LOCK(cc); 761155957Sjhb } 762177859Sjeff } else if (use_lock && !cc->cc_cancel) { 763155957Sjhb /* 764173760Sattilio * The current callout is waiting for its 765173760Sattilio * lock which we hold. Cancel the callout 766155957Sjhb * and return. After our caller drops the 767173760Sattilio * lock, the callout will be skipped in 768155957Sjhb * softclock(). 769155957Sjhb */ 770177859Sjeff cc->cc_cancel = 1; 771163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 772163246Sglebius c, c->c_func, c->c_arg); 773177859Sjeff CC_UNLOCK(cc); 774172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain locked")); 775141428Siedowse return (1); 776155957Sjhb } 777163246Sglebius CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 778163246Sglebius c, c->c_func, c->c_arg); 779177859Sjeff CC_UNLOCK(cc); 780172025Sjhb KASSERT(!sq_locked, ("sleepqueue chain still locked")); 78181481Sjhb return (0); 78244510Swollman } 783172025Sjhb if (sq_locked) 784177949Sjeff sleepq_release(&cc->cc_waiting); 785172025Sjhb 78650673Sjlemon c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 78744510Swollman 788177859Sjeff if (cc->cc_next == c) { 789177859Sjeff cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 79044510Swollman } 791177859Sjeff TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 792177859Sjeff c_links.tqe); 79344510Swollman 794163246Sglebius CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 795163246Sglebius c, c->c_func, c->c_arg); 796163246Sglebius 79744510Swollman if (c->c_flags & CALLOUT_LOCAL_ALLOC) { 798140492Scperciva c->c_func = NULL; 799177859Sjeff SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 80044510Swollman } 801177859Sjeff CC_UNLOCK(cc); 80281481Sjhb return (1); 80344510Swollman} 80444510Swollman 80544510Swollmanvoid 80669147Sjlemoncallout_init(c, mpsafe) 80744510Swollman struct callout *c; 80869147Sjlemon int mpsafe; 80944510Swollman{ 81044527Swollman bzero(c, sizeof *c); 811141428Siedowse if (mpsafe) { 812173760Sattilio c->c_lock = NULL; 813141428Siedowse c->c_flags = CALLOUT_RETURNUNLOCKED; 814141428Siedowse } else { 815173760Sattilio c->c_lock = &Giant.lock_object; 816141428Siedowse c->c_flags = 0; 817141428Siedowse } 818177859Sjeff c->c_cpu = timeout_cpu; 81944510Swollman} 82044510Swollman 821141428Siedowsevoid 822173760Sattilio_callout_init_lock(c, lock, flags) 823141428Siedowse struct callout *c; 824173760Sattilio struct lock_object *lock; 825141428Siedowse int flags; 826141428Siedowse{ 827141428Siedowse bzero(c, sizeof *c); 828173760Sattilio c->c_lock = lock; 829173760Sattilio KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0, 830173760Sattilio ("callout_init_lock: bad flags %d", flags)); 831173760Sattilio KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0, 832173760Sattilio ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock")); 833176013Sattilio KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags & 834176013Sattilio (LC_SPINLOCK | LC_SLEEPABLE)), ("%s: invalid lock class", 835173760Sattilio __func__)); 836173760Sattilio c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK); 837177859Sjeff c->c_cpu = timeout_cpu; 838141428Siedowse} 839141428Siedowse 84031950Snate#ifdef APM_FIXUP_CALLTODO 84131950Snate/* 84231950Snate * Adjust the kernel calltodo timeout list. This routine is used after 84331950Snate * an APM resume to recalculate the calltodo timer list values with the 84431950Snate * number of hz's we have been sleeping. The next hardclock() will detect 84531950Snate * that there are fired timers and run softclock() to execute them. 84631950Snate * 84731950Snate * Please note, I have not done an exhaustive analysis of what code this 84831950Snate * might break. I am motivated to have my select()'s and alarm()'s that 84931950Snate * have expired during suspend firing upon resume so that the applications 85031950Snate * which set the timer can do the maintanence the timer was for as close 85131950Snate * as possible to the originally intended time. Testing this code for a 85231950Snate * week showed that resuming from a suspend resulted in 22 to 25 timers 85331950Snate * firing, which seemed independant on whether the suspend was 2 hours or 85431950Snate * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 85531950Snate */ 85631950Snatevoid 85731950Snateadjust_timeout_calltodo(time_change) 85831950Snate struct timeval *time_change; 85931950Snate{ 86031950Snate register struct callout *p; 86131950Snate unsigned long delta_ticks; 86231950Snate 86331950Snate /* 86431950Snate * How many ticks were we asleep? 86536127Sbde * (stolen from tvtohz()). 86631950Snate */ 86731950Snate 86831950Snate /* Don't do anything */ 86931950Snate if (time_change->tv_sec < 0) 87031950Snate return; 87131950Snate else if (time_change->tv_sec <= LONG_MAX / 1000000) 87231950Snate delta_ticks = (time_change->tv_sec * 1000000 + 87331950Snate time_change->tv_usec + (tick - 1)) / tick + 1; 87431950Snate else if (time_change->tv_sec <= LONG_MAX / hz) 87531950Snate delta_ticks = time_change->tv_sec * hz + 87631950Snate (time_change->tv_usec + (tick - 1)) / tick + 1; 87731950Snate else 87831950Snate delta_ticks = LONG_MAX; 87931950Snate 88031950Snate if (delta_ticks > INT_MAX) 88131950Snate delta_ticks = INT_MAX; 88231950Snate 88331950Snate /* 88431950Snate * Now rip through the timer calltodo list looking for timers 88531950Snate * to expire. 88631950Snate */ 88731950Snate 88831950Snate /* don't collide with softclock() */ 889177859Sjeff CC_LOCK(cc); 89031950Snate for (p = calltodo.c_next; p != NULL; p = p->c_next) { 89131950Snate p->c_time -= delta_ticks; 89231950Snate 89331950Snate /* Break if the timer had more time on it than delta_ticks */ 89431950Snate if (p->c_time > 0) 89531950Snate break; 89631950Snate 89731950Snate /* take back the ticks the timer didn't use (p->c_time <= 0) */ 89831950Snate delta_ticks = -p->c_time; 89931950Snate } 900177859Sjeff CC_UNLOCK(cc); 90131950Snate 90231950Snate return; 90331950Snate} 90431950Snate#endif /* APM_FIXUP_CALLTODO */ 905