kern_timeout.c revision 247714
1/*- 2 * Copyright (c) 1982, 1986, 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * (c) UNIX System Laboratories, Inc. 5 * All or some portions of this file are derived from material licensed 6 * to the University of California by American Telephone and Telegraph 7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8 * the permission of UNIX System Laboratories, Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 4. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 * From: @(#)kern_clock.c 8.5 (Berkeley) 1/21/94 35 */ 36 37#include <sys/cdefs.h> 38__FBSDID("$FreeBSD: head/sys/kern/kern_timeout.c 247714 2013-03-03 14:47:02Z davide $"); 39 40#include "opt_kdtrace.h" 41 42#include <sys/param.h> 43#include <sys/systm.h> 44#include <sys/bus.h> 45#include <sys/callout.h> 46#include <sys/interrupt.h> 47#include <sys/kernel.h> 48#include <sys/ktr.h> 49#include <sys/lock.h> 50#include <sys/malloc.h> 51#include <sys/mutex.h> 52#include <sys/proc.h> 53#include <sys/sdt.h> 54#include <sys/sleepqueue.h> 55#include <sys/sysctl.h> 56#include <sys/smp.h> 57 58#ifdef SMP 59#include <machine/cpu.h> 60#endif 61 62SDT_PROVIDER_DEFINE(callout_execute); 63SDT_PROBE_DEFINE(callout_execute, kernel, , callout_start, callout-start); 64SDT_PROBE_ARGTYPE(callout_execute, kernel, , callout_start, 0, 65 "struct callout *"); 66SDT_PROBE_DEFINE(callout_execute, kernel, , callout_end, callout-end); 67SDT_PROBE_ARGTYPE(callout_execute, kernel, , callout_end, 0, 68 "struct callout *"); 69 70static int avg_depth; 71SYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0, 72 "Average number of items examined per softclock call. Units = 1/1000"); 73static int avg_gcalls; 74SYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0, 75 "Average number of Giant callouts made per softclock call. Units = 1/1000"); 76static int avg_lockcalls; 77SYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0, 78 "Average number of lock callouts made per softclock call. Units = 1/1000"); 79static int avg_mpcalls; 80SYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0, 81 "Average number of MP callouts made per softclock call. Units = 1/1000"); 82/* 83 * TODO: 84 * allocate more timeout table slots when table overflows. 85 */ 86int callwheelsize, callwheelmask; 87 88/* 89 * The callout cpu migration entity represents informations necessary for 90 * describing the migrating callout to the new callout cpu. 91 * The cached informations are very important for deferring migration when 92 * the migrating callout is already running. 93 */ 94struct cc_mig_ent { 95#ifdef SMP 96 void (*ce_migration_func)(void *); 97 void *ce_migration_arg; 98 int ce_migration_cpu; 99 int ce_migration_ticks; 100#endif 101}; 102 103/* 104 * There is one struct callout_cpu per cpu, holding all relevant 105 * state for the callout processing thread on the individual CPU. 106 * In particular: 107 * cc_ticks is incremented once per tick in callout_cpu(). 108 * It tracks the global 'ticks' but in a way that the individual 109 * threads should not worry about races in the order in which 110 * hardclock() and hardclock_cpu() run on the various CPUs. 111 * cc_softclock is advanced in callout_cpu() to point to the 112 * first entry in cc_callwheel that may need handling. In turn, 113 * a softclock() is scheduled so it can serve the various entries i 114 * such that cc_softclock <= i <= cc_ticks . 115 * XXX maybe cc_softclock and cc_ticks should be volatile ? 116 * 117 * cc_ticks is also used in callout_reset_cpu() to determine 118 * when the callout should be served. 119 */ 120struct callout_cpu { 121 struct mtx_padalign cc_lock; 122 struct cc_mig_ent cc_migrating_entity; 123 struct callout *cc_callout; 124 struct callout_tailq *cc_callwheel; 125 struct callout_list cc_callfree; 126 struct callout *cc_next; 127 struct callout *cc_curr; 128 void *cc_cookie; 129 int cc_ticks; 130 int cc_softticks; 131 int cc_cancel; 132 int cc_waiting; 133 int cc_firsttick; 134}; 135 136#ifdef SMP 137#define cc_migration_func cc_migrating_entity.ce_migration_func 138#define cc_migration_arg cc_migrating_entity.ce_migration_arg 139#define cc_migration_cpu cc_migrating_entity.ce_migration_cpu 140#define cc_migration_ticks cc_migrating_entity.ce_migration_ticks 141 142struct callout_cpu cc_cpu[MAXCPU]; 143#define CPUBLOCK MAXCPU 144#define CC_CPU(cpu) (&cc_cpu[(cpu)]) 145#define CC_SELF() CC_CPU(PCPU_GET(cpuid)) 146#else 147struct callout_cpu cc_cpu; 148#define CC_CPU(cpu) &cc_cpu 149#define CC_SELF() &cc_cpu 150#endif 151#define CC_LOCK(cc) mtx_lock_spin(&(cc)->cc_lock) 152#define CC_UNLOCK(cc) mtx_unlock_spin(&(cc)->cc_lock) 153#define CC_LOCK_ASSERT(cc) mtx_assert(&(cc)->cc_lock, MA_OWNED) 154 155static int timeout_cpu; 156void (*callout_new_inserted)(int cpu, int ticks) = NULL; 157 158static MALLOC_DEFINE(M_CALLOUT, "callout", "Callout datastructures"); 159 160/** 161 * Locked by cc_lock: 162 * cc_curr - If a callout is in progress, it is curr_callout. 163 * If curr_callout is non-NULL, threads waiting in 164 * callout_drain() will be woken up as soon as the 165 * relevant callout completes. 166 * cc_cancel - Changing to 1 with both callout_lock and c_lock held 167 * guarantees that the current callout will not run. 168 * The softclock() function sets this to 0 before it 169 * drops callout_lock to acquire c_lock, and it calls 170 * the handler only if curr_cancelled is still 0 after 171 * c_lock is successfully acquired. 172 * cc_waiting - If a thread is waiting in callout_drain(), then 173 * callout_wait is nonzero. Set only when 174 * curr_callout is non-NULL. 175 */ 176 177/* 178 * Resets the migration entity tied to a specific callout cpu. 179 */ 180static void 181cc_cme_cleanup(struct callout_cpu *cc) 182{ 183 184#ifdef SMP 185 cc->cc_migration_cpu = CPUBLOCK; 186 cc->cc_migration_ticks = 0; 187 cc->cc_migration_func = NULL; 188 cc->cc_migration_arg = NULL; 189#endif 190} 191 192/* 193 * Checks if migration is requested by a specific callout cpu. 194 */ 195static int 196cc_cme_migrating(struct callout_cpu *cc) 197{ 198 199#ifdef SMP 200 return (cc->cc_migration_cpu != CPUBLOCK); 201#else 202 return (0); 203#endif 204} 205 206/* 207 * kern_timeout_callwheel_alloc() - kernel low level callwheel initialization 208 * 209 * This code is called very early in the kernel initialization sequence, 210 * and may be called more then once. 211 */ 212caddr_t 213kern_timeout_callwheel_alloc(caddr_t v) 214{ 215 struct callout_cpu *cc; 216 217 timeout_cpu = PCPU_GET(cpuid); 218 cc = CC_CPU(timeout_cpu); 219 /* 220 * Calculate callout wheel size, should be next power of two higher 221 * than 'ncallout'. 222 */ 223 callwheelsize = 1 << fls(ncallout); 224 callwheelmask = callwheelsize - 1; 225 226 cc->cc_callout = (struct callout *)v; 227 v = (caddr_t)(cc->cc_callout + ncallout); 228 cc->cc_callwheel = (struct callout_tailq *)v; 229 v = (caddr_t)(cc->cc_callwheel + callwheelsize); 230 return(v); 231} 232 233static void 234callout_cpu_init(struct callout_cpu *cc) 235{ 236 struct callout *c; 237 int i; 238 239 mtx_init(&cc->cc_lock, "callout", NULL, MTX_SPIN | MTX_RECURSE); 240 SLIST_INIT(&cc->cc_callfree); 241 for (i = 0; i < callwheelsize; i++) { 242 TAILQ_INIT(&cc->cc_callwheel[i]); 243 } 244 cc_cme_cleanup(cc); 245 if (cc->cc_callout == NULL) 246 return; 247 for (i = 0; i < ncallout; i++) { 248 c = &cc->cc_callout[i]; 249 callout_init(c, 0); 250 c->c_flags = CALLOUT_LOCAL_ALLOC; 251 SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 252 } 253} 254 255#ifdef SMP 256/* 257 * Switches the cpu tied to a specific callout. 258 * The function expects a locked incoming callout cpu and returns with 259 * locked outcoming callout cpu. 260 */ 261static struct callout_cpu * 262callout_cpu_switch(struct callout *c, struct callout_cpu *cc, int new_cpu) 263{ 264 struct callout_cpu *new_cc; 265 266 MPASS(c != NULL && cc != NULL); 267 CC_LOCK_ASSERT(cc); 268 269 /* 270 * Avoid interrupts and preemption firing after the callout cpu 271 * is blocked in order to avoid deadlocks as the new thread 272 * may be willing to acquire the callout cpu lock. 273 */ 274 c->c_cpu = CPUBLOCK; 275 spinlock_enter(); 276 CC_UNLOCK(cc); 277 new_cc = CC_CPU(new_cpu); 278 CC_LOCK(new_cc); 279 spinlock_exit(); 280 c->c_cpu = new_cpu; 281 return (new_cc); 282} 283#endif 284 285/* 286 * kern_timeout_callwheel_init() - initialize previously reserved callwheel 287 * space. 288 * 289 * This code is called just once, after the space reserved for the 290 * callout wheel has been finalized. 291 */ 292void 293kern_timeout_callwheel_init(void) 294{ 295 callout_cpu_init(CC_CPU(timeout_cpu)); 296} 297 298/* 299 * Start standard softclock thread. 300 */ 301static void 302start_softclock(void *dummy) 303{ 304 struct callout_cpu *cc; 305#ifdef SMP 306 int cpu; 307#endif 308 309 cc = CC_CPU(timeout_cpu); 310 if (swi_add(&clk_intr_event, "clock", softclock, cc, SWI_CLOCK, 311 INTR_MPSAFE, &cc->cc_cookie)) 312 panic("died while creating standard software ithreads"); 313#ifdef SMP 314 CPU_FOREACH(cpu) { 315 if (cpu == timeout_cpu) 316 continue; 317 cc = CC_CPU(cpu); 318 if (swi_add(NULL, "clock", softclock, cc, SWI_CLOCK, 319 INTR_MPSAFE, &cc->cc_cookie)) 320 panic("died while creating standard software ithreads"); 321 cc->cc_callout = NULL; /* Only cpu0 handles timeout(). */ 322 cc->cc_callwheel = malloc( 323 sizeof(struct callout_tailq) * callwheelsize, M_CALLOUT, 324 M_WAITOK); 325 callout_cpu_init(cc); 326 } 327#endif 328} 329 330SYSINIT(start_softclock, SI_SUB_SOFTINTR, SI_ORDER_FIRST, start_softclock, NULL); 331 332void 333callout_tick(void) 334{ 335 struct callout_cpu *cc; 336 int need_softclock; 337 int bucket; 338 339 /* 340 * Process callouts at a very low cpu priority, so we don't keep the 341 * relatively high clock interrupt priority any longer than necessary. 342 */ 343 need_softclock = 0; 344 cc = CC_SELF(); 345 mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET); 346 cc->cc_firsttick = cc->cc_ticks = ticks; 347 for (; (cc->cc_softticks - cc->cc_ticks) <= 0; cc->cc_softticks++) { 348 bucket = cc->cc_softticks & callwheelmask; 349 if (!TAILQ_EMPTY(&cc->cc_callwheel[bucket])) { 350 need_softclock = 1; 351 break; 352 } 353 } 354 mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET); 355 /* 356 * swi_sched acquires the thread lock, so we don't want to call it 357 * with cc_lock held; incorrect locking order. 358 */ 359 if (need_softclock) 360 swi_sched(cc->cc_cookie, 0); 361} 362 363int 364callout_tickstofirst(int limit) 365{ 366 struct callout_cpu *cc; 367 struct callout *c; 368 struct callout_tailq *sc; 369 int curticks; 370 int skip = 1; 371 372 cc = CC_SELF(); 373 mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET); 374 curticks = cc->cc_ticks; 375 while( skip < ncallout && skip < limit ) { 376 sc = &cc->cc_callwheel[ (curticks+skip) & callwheelmask ]; 377 /* search scanning ticks */ 378 TAILQ_FOREACH( c, sc, c_links.tqe ){ 379 if (c->c_time - curticks <= ncallout) 380 goto out; 381 } 382 skip++; 383 } 384out: 385 cc->cc_firsttick = curticks + skip; 386 mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET); 387 return (skip); 388} 389 390static struct callout_cpu * 391callout_lock(struct callout *c) 392{ 393 struct callout_cpu *cc; 394 int cpu; 395 396 for (;;) { 397 cpu = c->c_cpu; 398#ifdef SMP 399 if (cpu == CPUBLOCK) { 400 while (c->c_cpu == CPUBLOCK) 401 cpu_spinwait(); 402 continue; 403 } 404#endif 405 cc = CC_CPU(cpu); 406 CC_LOCK(cc); 407 if (cpu == c->c_cpu) 408 break; 409 CC_UNLOCK(cc); 410 } 411 return (cc); 412} 413 414static void 415callout_cc_add(struct callout *c, struct callout_cpu *cc, int to_ticks, 416 void (*func)(void *), void *arg, int cpu) 417{ 418 419 CC_LOCK_ASSERT(cc); 420 421 if (to_ticks <= 0) 422 to_ticks = 1; 423 c->c_arg = arg; 424 c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING); 425 c->c_func = func; 426 c->c_time = ticks + to_ticks; 427 TAILQ_INSERT_TAIL(&cc->cc_callwheel[c->c_time & callwheelmask], 428 c, c_links.tqe); 429 if ((c->c_time - cc->cc_firsttick) < 0 && 430 callout_new_inserted != NULL) { 431 cc->cc_firsttick = c->c_time; 432 (*callout_new_inserted)(cpu, 433 to_ticks + (ticks - cc->cc_ticks)); 434 } 435} 436 437static void 438callout_cc_del(struct callout *c, struct callout_cpu *cc) 439{ 440 441 if ((c->c_flags & CALLOUT_LOCAL_ALLOC) == 0) 442 return; 443 c->c_func = NULL; 444 SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle); 445} 446 447static void 448softclock_call_cc(struct callout *c, struct callout_cpu *cc, int *mpcalls, 449 int *lockcalls, int *gcalls) 450{ 451 void (*c_func)(void *); 452 void *c_arg; 453 struct lock_class *class; 454 struct lock_object *c_lock; 455 int c_flags, sharedlock; 456#ifdef SMP 457 struct callout_cpu *new_cc; 458 void (*new_func)(void *); 459 void *new_arg; 460 int new_cpu, new_ticks; 461#endif 462#ifdef DIAGNOSTIC 463 struct bintime bt1, bt2; 464 struct timespec ts2; 465 static uint64_t maxdt = 36893488147419102LL; /* 2 msec */ 466 static timeout_t *lastfunc; 467#endif 468 469 KASSERT((c->c_flags & (CALLOUT_PENDING | CALLOUT_ACTIVE)) == 470 (CALLOUT_PENDING | CALLOUT_ACTIVE), 471 ("softclock_call_cc: pend|act %p %x", c, c->c_flags)); 472 class = (c->c_lock != NULL) ? LOCK_CLASS(c->c_lock) : NULL; 473 sharedlock = (c->c_flags & CALLOUT_SHAREDLOCK) ? 0 : 1; 474 c_lock = c->c_lock; 475 c_func = c->c_func; 476 c_arg = c->c_arg; 477 c_flags = c->c_flags; 478 if (c->c_flags & CALLOUT_LOCAL_ALLOC) 479 c->c_flags = CALLOUT_LOCAL_ALLOC; 480 else 481 c->c_flags &= ~CALLOUT_PENDING; 482 cc->cc_curr = c; 483 cc->cc_cancel = 0; 484 CC_UNLOCK(cc); 485 if (c_lock != NULL) { 486 class->lc_lock(c_lock, sharedlock); 487 /* 488 * The callout may have been cancelled 489 * while we switched locks. 490 */ 491 if (cc->cc_cancel) { 492 class->lc_unlock(c_lock); 493 goto skip; 494 } 495 /* The callout cannot be stopped now. */ 496 cc->cc_cancel = 1; 497 498 if (c_lock == &Giant.lock_object) { 499 (*gcalls)++; 500 CTR3(KTR_CALLOUT, "callout %p func %p arg %p", 501 c, c_func, c_arg); 502 } else { 503 (*lockcalls)++; 504 CTR3(KTR_CALLOUT, "callout lock %p func %p arg %p", 505 c, c_func, c_arg); 506 } 507 } else { 508 (*mpcalls)++; 509 CTR3(KTR_CALLOUT, "callout mpsafe %p func %p arg %p", 510 c, c_func, c_arg); 511 } 512#ifdef DIAGNOSTIC 513 binuptime(&bt1); 514#endif 515 THREAD_NO_SLEEPING(); 516 SDT_PROBE(callout_execute, kernel, , callout_start, c, 0, 0, 0, 0); 517 c_func(c_arg); 518 SDT_PROBE(callout_execute, kernel, , callout_end, c, 0, 0, 0, 0); 519 THREAD_SLEEPING_OK(); 520#ifdef DIAGNOSTIC 521 binuptime(&bt2); 522 bintime_sub(&bt2, &bt1); 523 if (bt2.frac > maxdt) { 524 if (lastfunc != c_func || bt2.frac > maxdt * 2) { 525 bintime2timespec(&bt2, &ts2); 526 printf( 527 "Expensive timeout(9) function: %p(%p) %jd.%09ld s\n", 528 c_func, c_arg, (intmax_t)ts2.tv_sec, ts2.tv_nsec); 529 } 530 maxdt = bt2.frac; 531 lastfunc = c_func; 532 } 533#endif 534 CTR1(KTR_CALLOUT, "callout %p finished", c); 535 if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0) 536 class->lc_unlock(c_lock); 537skip: 538 CC_LOCK(cc); 539 KASSERT(cc->cc_curr == c, ("mishandled cc_curr")); 540 cc->cc_curr = NULL; 541 if (cc->cc_waiting) { 542 /* 543 * There is someone waiting for the 544 * callout to complete. 545 * If the callout was scheduled for 546 * migration just cancel it. 547 */ 548 if (cc_cme_migrating(cc)) { 549 cc_cme_cleanup(cc); 550 551 /* 552 * It should be assert here that the callout is not 553 * destroyed but that is not easy. 554 */ 555 c->c_flags &= ~CALLOUT_DFRMIGRATION; 556 } 557 cc->cc_waiting = 0; 558 CC_UNLOCK(cc); 559 wakeup(&cc->cc_waiting); 560 CC_LOCK(cc); 561 } else if (cc_cme_migrating(cc)) { 562 KASSERT((c_flags & CALLOUT_LOCAL_ALLOC) == 0, 563 ("Migrating legacy callout %p", c)); 564#ifdef SMP 565 /* 566 * If the callout was scheduled for 567 * migration just perform it now. 568 */ 569 new_cpu = cc->cc_migration_cpu; 570 new_ticks = cc->cc_migration_ticks; 571 new_func = cc->cc_migration_func; 572 new_arg = cc->cc_migration_arg; 573 cc_cme_cleanup(cc); 574 575 /* 576 * It should be assert here that the callout is not destroyed 577 * but that is not easy. 578 * 579 * As first thing, handle deferred callout stops. 580 */ 581 if ((c->c_flags & CALLOUT_DFRMIGRATION) == 0) { 582 CTR3(KTR_CALLOUT, 583 "deferred cancelled %p func %p arg %p", 584 c, new_func, new_arg); 585 callout_cc_del(c, cc); 586 return; 587 } 588 c->c_flags &= ~CALLOUT_DFRMIGRATION; 589 590 new_cc = callout_cpu_switch(c, cc, new_cpu); 591 callout_cc_add(c, new_cc, new_ticks, new_func, new_arg, 592 new_cpu); 593 CC_UNLOCK(new_cc); 594 CC_LOCK(cc); 595#else 596 panic("migration should not happen"); 597#endif 598 } 599 /* 600 * If the current callout is locally allocated (from 601 * timeout(9)) then put it on the freelist. 602 * 603 * Note: we need to check the cached copy of c_flags because 604 * if it was not local, then it's not safe to deref the 605 * callout pointer. 606 */ 607 KASSERT((c_flags & CALLOUT_LOCAL_ALLOC) == 0 || 608 c->c_flags == CALLOUT_LOCAL_ALLOC, 609 ("corrupted callout")); 610 if (c_flags & CALLOUT_LOCAL_ALLOC) 611 callout_cc_del(c, cc); 612} 613 614/* 615 * The callout mechanism is based on the work of Adam M. Costello and 616 * George Varghese, published in a technical report entitled "Redesigning 617 * the BSD Callout and Timer Facilities" and modified slightly for inclusion 618 * in FreeBSD by Justin T. Gibbs. The original work on the data structures 619 * used in this implementation was published by G. Varghese and T. Lauck in 620 * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for 621 * the Efficient Implementation of a Timer Facility" in the Proceedings of 622 * the 11th ACM Annual Symposium on Operating Systems Principles, 623 * Austin, Texas Nov 1987. 624 */ 625 626/* 627 * Software (low priority) clock interrupt. 628 * Run periodic events from timeout queue. 629 */ 630void 631softclock(void *arg) 632{ 633 struct callout_cpu *cc; 634 struct callout *c; 635 struct callout_tailq *bucket; 636 int curticks; 637 int steps; /* #steps since we last allowed interrupts */ 638 int depth; 639 int mpcalls; 640 int lockcalls; 641 int gcalls; 642 643#ifndef MAX_SOFTCLOCK_STEPS 644#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */ 645#endif /* MAX_SOFTCLOCK_STEPS */ 646 647 mpcalls = 0; 648 lockcalls = 0; 649 gcalls = 0; 650 depth = 0; 651 steps = 0; 652 cc = (struct callout_cpu *)arg; 653 CC_LOCK(cc); 654 while (cc->cc_softticks - 1 != cc->cc_ticks) { 655 /* 656 * cc_softticks may be modified by hard clock, so cache 657 * it while we work on a given bucket. 658 */ 659 curticks = cc->cc_softticks; 660 cc->cc_softticks++; 661 bucket = &cc->cc_callwheel[curticks & callwheelmask]; 662 c = TAILQ_FIRST(bucket); 663 while (c != NULL) { 664 depth++; 665 if (c->c_time != curticks) { 666 c = TAILQ_NEXT(c, c_links.tqe); 667 ++steps; 668 if (steps >= MAX_SOFTCLOCK_STEPS) { 669 cc->cc_next = c; 670 /* Give interrupts a chance. */ 671 CC_UNLOCK(cc); 672 ; /* nothing */ 673 CC_LOCK(cc); 674 c = cc->cc_next; 675 steps = 0; 676 } 677 } else { 678 cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 679 TAILQ_REMOVE(bucket, c, c_links.tqe); 680 softclock_call_cc(c, cc, &mpcalls, 681 &lockcalls, &gcalls); 682 steps = 0; 683 c = cc->cc_next; 684 } 685 } 686 } 687 avg_depth += (depth * 1000 - avg_depth) >> 8; 688 avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8; 689 avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8; 690 avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8; 691 cc->cc_next = NULL; 692 CC_UNLOCK(cc); 693} 694 695/* 696 * timeout -- 697 * Execute a function after a specified length of time. 698 * 699 * untimeout -- 700 * Cancel previous timeout function call. 701 * 702 * callout_handle_init -- 703 * Initialize a handle so that using it with untimeout is benign. 704 * 705 * See AT&T BCI Driver Reference Manual for specification. This 706 * implementation differs from that one in that although an 707 * identification value is returned from timeout, the original 708 * arguments to timeout as well as the identifier are used to 709 * identify entries for untimeout. 710 */ 711struct callout_handle 712timeout(ftn, arg, to_ticks) 713 timeout_t *ftn; 714 void *arg; 715 int to_ticks; 716{ 717 struct callout_cpu *cc; 718 struct callout *new; 719 struct callout_handle handle; 720 721 cc = CC_CPU(timeout_cpu); 722 CC_LOCK(cc); 723 /* Fill in the next free callout structure. */ 724 new = SLIST_FIRST(&cc->cc_callfree); 725 if (new == NULL) 726 /* XXX Attempt to malloc first */ 727 panic("timeout table full"); 728 SLIST_REMOVE_HEAD(&cc->cc_callfree, c_links.sle); 729 callout_reset(new, to_ticks, ftn, arg); 730 handle.callout = new; 731 CC_UNLOCK(cc); 732 733 return (handle); 734} 735 736void 737untimeout(ftn, arg, handle) 738 timeout_t *ftn; 739 void *arg; 740 struct callout_handle handle; 741{ 742 struct callout_cpu *cc; 743 744 /* 745 * Check for a handle that was initialized 746 * by callout_handle_init, but never used 747 * for a real timeout. 748 */ 749 if (handle.callout == NULL) 750 return; 751 752 cc = callout_lock(handle.callout); 753 if (handle.callout->c_func == ftn && handle.callout->c_arg == arg) 754 callout_stop(handle.callout); 755 CC_UNLOCK(cc); 756} 757 758void 759callout_handle_init(struct callout_handle *handle) 760{ 761 handle->callout = NULL; 762} 763 764/* 765 * New interface; clients allocate their own callout structures. 766 * 767 * callout_reset() - establish or change a timeout 768 * callout_stop() - disestablish a timeout 769 * callout_init() - initialize a callout structure so that it can 770 * safely be passed to callout_reset() and callout_stop() 771 * 772 * <sys/callout.h> defines three convenience macros: 773 * 774 * callout_active() - returns truth if callout has not been stopped, 775 * drained, or deactivated since the last time the callout was 776 * reset. 777 * callout_pending() - returns truth if callout is still waiting for timeout 778 * callout_deactivate() - marks the callout as having been serviced 779 */ 780int 781callout_reset_on(struct callout *c, int to_ticks, void (*ftn)(void *), 782 void *arg, int cpu) 783{ 784 struct callout_cpu *cc; 785 int cancelled = 0; 786 787 /* 788 * Don't allow migration of pre-allocated callouts lest they 789 * become unbalanced. 790 */ 791 if (c->c_flags & CALLOUT_LOCAL_ALLOC) 792 cpu = c->c_cpu; 793 cc = callout_lock(c); 794 if (cc->cc_curr == c) { 795 /* 796 * We're being asked to reschedule a callout which is 797 * currently in progress. If there is a lock then we 798 * can cancel the callout if it has not really started. 799 */ 800 if (c->c_lock != NULL && !cc->cc_cancel) 801 cancelled = cc->cc_cancel = 1; 802 if (cc->cc_waiting) { 803 /* 804 * Someone has called callout_drain to kill this 805 * callout. Don't reschedule. 806 */ 807 CTR4(KTR_CALLOUT, "%s %p func %p arg %p", 808 cancelled ? "cancelled" : "failed to cancel", 809 c, c->c_func, c->c_arg); 810 CC_UNLOCK(cc); 811 return (cancelled); 812 } 813 } 814 if (c->c_flags & CALLOUT_PENDING) { 815 if (cc->cc_next == c) { 816 cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 817 } 818 TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 819 c_links.tqe); 820 821 cancelled = 1; 822 c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 823 } 824 825#ifdef SMP 826 /* 827 * If the callout must migrate try to perform it immediately. 828 * If the callout is currently running, just defer the migration 829 * to a more appropriate moment. 830 */ 831 if (c->c_cpu != cpu) { 832 if (cc->cc_curr == c) { 833 cc->cc_migration_cpu = cpu; 834 cc->cc_migration_ticks = to_ticks; 835 cc->cc_migration_func = ftn; 836 cc->cc_migration_arg = arg; 837 c->c_flags |= CALLOUT_DFRMIGRATION; 838 CTR5(KTR_CALLOUT, 839 "migration of %p func %p arg %p in %d to %u deferred", 840 c, c->c_func, c->c_arg, to_ticks, cpu); 841 CC_UNLOCK(cc); 842 return (cancelled); 843 } 844 cc = callout_cpu_switch(c, cc, cpu); 845 } 846#endif 847 848 callout_cc_add(c, cc, to_ticks, ftn, arg, cpu); 849 CTR5(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d", 850 cancelled ? "re" : "", c, c->c_func, c->c_arg, to_ticks); 851 CC_UNLOCK(cc); 852 853 return (cancelled); 854} 855 856/* 857 * Common idioms that can be optimized in the future. 858 */ 859int 860callout_schedule_on(struct callout *c, int to_ticks, int cpu) 861{ 862 return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, cpu); 863} 864 865int 866callout_schedule(struct callout *c, int to_ticks) 867{ 868 return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, c->c_cpu); 869} 870 871int 872_callout_stop_safe(c, safe) 873 struct callout *c; 874 int safe; 875{ 876 struct callout_cpu *cc, *old_cc; 877 struct lock_class *class; 878 int use_lock, sq_locked; 879 880 /* 881 * Some old subsystems don't hold Giant while running a callout_stop(), 882 * so just discard this check for the moment. 883 */ 884 if (!safe && c->c_lock != NULL) { 885 if (c->c_lock == &Giant.lock_object) 886 use_lock = mtx_owned(&Giant); 887 else { 888 use_lock = 1; 889 class = LOCK_CLASS(c->c_lock); 890 class->lc_assert(c->c_lock, LA_XLOCKED); 891 } 892 } else 893 use_lock = 0; 894 895 sq_locked = 0; 896 old_cc = NULL; 897again: 898 cc = callout_lock(c); 899 900 /* 901 * If the callout was migrating while the callout cpu lock was 902 * dropped, just drop the sleepqueue lock and check the states 903 * again. 904 */ 905 if (sq_locked != 0 && cc != old_cc) { 906#ifdef SMP 907 CC_UNLOCK(cc); 908 sleepq_release(&old_cc->cc_waiting); 909 sq_locked = 0; 910 old_cc = NULL; 911 goto again; 912#else 913 panic("migration should not happen"); 914#endif 915 } 916 917 /* 918 * If the callout isn't pending, it's not on the queue, so 919 * don't attempt to remove it from the queue. We can try to 920 * stop it by other means however. 921 */ 922 if (!(c->c_flags & CALLOUT_PENDING)) { 923 c->c_flags &= ~CALLOUT_ACTIVE; 924 925 /* 926 * If it wasn't on the queue and it isn't the current 927 * callout, then we can't stop it, so just bail. 928 */ 929 if (cc->cc_curr != c) { 930 CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 931 c, c->c_func, c->c_arg); 932 CC_UNLOCK(cc); 933 if (sq_locked) 934 sleepq_release(&cc->cc_waiting); 935 return (0); 936 } 937 938 if (safe) { 939 /* 940 * The current callout is running (or just 941 * about to run) and blocking is allowed, so 942 * just wait for the current invocation to 943 * finish. 944 */ 945 while (cc->cc_curr == c) { 946 947 /* 948 * Use direct calls to sleepqueue interface 949 * instead of cv/msleep in order to avoid 950 * a LOR between cc_lock and sleepqueue 951 * chain spinlocks. This piece of code 952 * emulates a msleep_spin() call actually. 953 * 954 * If we already have the sleepqueue chain 955 * locked, then we can safely block. If we 956 * don't already have it locked, however, 957 * we have to drop the cc_lock to lock 958 * it. This opens several races, so we 959 * restart at the beginning once we have 960 * both locks. If nothing has changed, then 961 * we will end up back here with sq_locked 962 * set. 963 */ 964 if (!sq_locked) { 965 CC_UNLOCK(cc); 966 sleepq_lock(&cc->cc_waiting); 967 sq_locked = 1; 968 old_cc = cc; 969 goto again; 970 } 971 972 /* 973 * Migration could be cancelled here, but 974 * as long as it is still not sure when it 975 * will be packed up, just let softclock() 976 * take care of it. 977 */ 978 cc->cc_waiting = 1; 979 DROP_GIANT(); 980 CC_UNLOCK(cc); 981 sleepq_add(&cc->cc_waiting, 982 &cc->cc_lock.lock_object, "codrain", 983 SLEEPQ_SLEEP, 0); 984 sleepq_wait(&cc->cc_waiting, 0); 985 sq_locked = 0; 986 old_cc = NULL; 987 988 /* Reacquire locks previously released. */ 989 PICKUP_GIANT(); 990 CC_LOCK(cc); 991 } 992 } else if (use_lock && !cc->cc_cancel) { 993 /* 994 * The current callout is waiting for its 995 * lock which we hold. Cancel the callout 996 * and return. After our caller drops the 997 * lock, the callout will be skipped in 998 * softclock(). 999 */ 1000 cc->cc_cancel = 1; 1001 CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 1002 c, c->c_func, c->c_arg); 1003 KASSERT(!cc_cme_migrating(cc), 1004 ("callout wrongly scheduled for migration")); 1005 CC_UNLOCK(cc); 1006 KASSERT(!sq_locked, ("sleepqueue chain locked")); 1007 return (1); 1008 } else if ((c->c_flags & CALLOUT_DFRMIGRATION) != 0) { 1009 c->c_flags &= ~CALLOUT_DFRMIGRATION; 1010 CTR3(KTR_CALLOUT, "postponing stop %p func %p arg %p", 1011 c, c->c_func, c->c_arg); 1012 CC_UNLOCK(cc); 1013 return (1); 1014 } 1015 CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p", 1016 c, c->c_func, c->c_arg); 1017 CC_UNLOCK(cc); 1018 KASSERT(!sq_locked, ("sleepqueue chain still locked")); 1019 return (0); 1020 } 1021 if (sq_locked) 1022 sleepq_release(&cc->cc_waiting); 1023 1024 c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING); 1025 1026 CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p", 1027 c, c->c_func, c->c_arg); 1028 if (cc->cc_next == c) 1029 cc->cc_next = TAILQ_NEXT(c, c_links.tqe); 1030 TAILQ_REMOVE(&cc->cc_callwheel[c->c_time & callwheelmask], c, 1031 c_links.tqe); 1032 callout_cc_del(c, cc); 1033 1034 CC_UNLOCK(cc); 1035 return (1); 1036} 1037 1038void 1039callout_init(c, mpsafe) 1040 struct callout *c; 1041 int mpsafe; 1042{ 1043 bzero(c, sizeof *c); 1044 if (mpsafe) { 1045 c->c_lock = NULL; 1046 c->c_flags = CALLOUT_RETURNUNLOCKED; 1047 } else { 1048 c->c_lock = &Giant.lock_object; 1049 c->c_flags = 0; 1050 } 1051 c->c_cpu = timeout_cpu; 1052} 1053 1054void 1055_callout_init_lock(c, lock, flags) 1056 struct callout *c; 1057 struct lock_object *lock; 1058 int flags; 1059{ 1060 bzero(c, sizeof *c); 1061 c->c_lock = lock; 1062 KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0, 1063 ("callout_init_lock: bad flags %d", flags)); 1064 KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0, 1065 ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock")); 1066 KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags & 1067 (LC_SPINLOCK | LC_SLEEPABLE)), ("%s: invalid lock class", 1068 __func__)); 1069 c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK); 1070 c->c_cpu = timeout_cpu; 1071} 1072 1073#ifdef APM_FIXUP_CALLTODO 1074/* 1075 * Adjust the kernel calltodo timeout list. This routine is used after 1076 * an APM resume to recalculate the calltodo timer list values with the 1077 * number of hz's we have been sleeping. The next hardclock() will detect 1078 * that there are fired timers and run softclock() to execute them. 1079 * 1080 * Please note, I have not done an exhaustive analysis of what code this 1081 * might break. I am motivated to have my select()'s and alarm()'s that 1082 * have expired during suspend firing upon resume so that the applications 1083 * which set the timer can do the maintanence the timer was for as close 1084 * as possible to the originally intended time. Testing this code for a 1085 * week showed that resuming from a suspend resulted in 22 to 25 timers 1086 * firing, which seemed independant on whether the suspend was 2 hours or 1087 * 2 days. Your milage may vary. - Ken Key <key@cs.utk.edu> 1088 */ 1089void 1090adjust_timeout_calltodo(time_change) 1091 struct timeval *time_change; 1092{ 1093 register struct callout *p; 1094 unsigned long delta_ticks; 1095 1096 /* 1097 * How many ticks were we asleep? 1098 * (stolen from tvtohz()). 1099 */ 1100 1101 /* Don't do anything */ 1102 if (time_change->tv_sec < 0) 1103 return; 1104 else if (time_change->tv_sec <= LONG_MAX / 1000000) 1105 delta_ticks = (time_change->tv_sec * 1000000 + 1106 time_change->tv_usec + (tick - 1)) / tick + 1; 1107 else if (time_change->tv_sec <= LONG_MAX / hz) 1108 delta_ticks = time_change->tv_sec * hz + 1109 (time_change->tv_usec + (tick - 1)) / tick + 1; 1110 else 1111 delta_ticks = LONG_MAX; 1112 1113 if (delta_ticks > INT_MAX) 1114 delta_ticks = INT_MAX; 1115 1116 /* 1117 * Now rip through the timer calltodo list looking for timers 1118 * to expire. 1119 */ 1120 1121 /* don't collide with softclock() */ 1122 CC_LOCK(cc); 1123 for (p = calltodo.c_next; p != NULL; p = p->c_next) { 1124 p->c_time -= delta_ticks; 1125 1126 /* Break if the timer had more time on it than delta_ticks */ 1127 if (p->c_time > 0) 1128 break; 1129 1130 /* take back the ticks the timer didn't use (p->c_time <= 0) */ 1131 delta_ticks = -p->c_time; 1132 } 1133 CC_UNLOCK(cc); 1134 1135 return; 1136} 1137#endif /* APM_FIXUP_CALLTODO */ 1138