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