sys/kern/kern_timeout.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1982, 1986, 1991, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  * (c) UNIX System Laboratories, Inc.
   7  * All or some portions of this file are derived from material licensed
   8  * to the University of California by American Telephone and Telegraph
   9  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
  10  * the permission of UNIX System Laboratories, Inc.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  *      From: @(#)kern_clock.c  8.5 (Berkeley) 1/21/94
  37  */
  38
  39 #include <sys/cdefs.h>
  40 #include "opt_callout_profiling.h"
  41 #include "opt_ddb.h"
  42 #include "opt_rss.h"
  43
  44 #include <sys/param.h>
  45 #include <sys/systm.h>
  46 #include <sys/bus.h>
  47 #include <sys/callout.h>
  48 #include <sys/domainset.h>
  49 #include <sys/file.h>
  50 #include <sys/interrupt.h>
  51 #include <sys/kernel.h>
  52 #include <sys/ktr.h>
  53 #include <sys/kthread.h>
  54 #include <sys/lock.h>
  55 #include <sys/malloc.h>
  56 #include <sys/mutex.h>
  57 #include <sys/proc.h>
  58 #include <sys/random.h>
  59 #include <sys/sched.h>
  60 #include <sys/sdt.h>
  61 #include <sys/sleepqueue.h>
  62 #include <sys/sysctl.h>
  63 #include <sys/smp.h>
  64 #include <sys/unistd.h>
  65
  66 #ifdef DDB
  67 #include <ddb/ddb.h>
  68 #include <ddb/db_sym.h>
  69 #include <machine/_inttypes.h>
  70 #endif
  71
  72 #ifdef SMP
  73 #include <machine/cpu.h>
  74 #endif
  75
  76 DPCPU_DECLARE(sbintime_t, hardclocktime);
  77
  78 SDT_PROVIDER_DEFINE(callout_execute);
  79 SDT_PROBE_DEFINE1(callout_execute, , , callout__start, "struct callout *");
  80 SDT_PROBE_DEFINE1(callout_execute, , , callout__end, "struct callout *");
  81
  82 static void     softclock_thread(void *arg);
  83
  84 #ifdef CALLOUT_PROFILING
  85 static int avg_depth;
  86 SYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0,
  87     "Average number of items examined per softclock call. Units = 1/1000");
  88 static int avg_gcalls;
  89 SYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0,
  90     "Average number of Giant callouts made per softclock call. Units = 1/1000");
  91 static int avg_lockcalls;
  92 SYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0,
  93     "Average number of lock callouts made per softclock call. Units = 1/1000");
  94 static int avg_mpcalls;
  95 SYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0,
  96     "Average number of MP callouts made per softclock call. Units = 1/1000");
  97 static int avg_depth_dir;
  98 SYSCTL_INT(_debug, OID_AUTO, to_avg_depth_dir, CTLFLAG_RD, &avg_depth_dir, 0,
  99     "Average number of direct callouts examined per callout_process call. "
 100     "Units = 1/1000");
 101 static int avg_lockcalls_dir;
 102 SYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls_dir, CTLFLAG_RD,
 103     &avg_lockcalls_dir, 0, "Average number of lock direct callouts made per "
 104     "callout_process call. Units = 1/1000");
 105 static int avg_mpcalls_dir;
 106 SYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls_dir, CTLFLAG_RD, &avg_mpcalls_dir,
 107     0, "Average number of MP direct callouts made per callout_process call. "
 108     "Units = 1/1000");
 109 #endif
 110
 111 static int ncallout;
 112 SYSCTL_INT(_kern, OID_AUTO, ncallout, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &ncallout, 0,
 113     "Number of entries in callwheel and size of timeout() preallocation");
 114
 115 #ifdef  RSS
 116 static int pin_default_swi = 1;
 117 static int pin_pcpu_swi = 1;
 118 #else
 119 static int pin_default_swi = 0;
 120 static int pin_pcpu_swi = 0;
 121 #endif
 122
 123 SYSCTL_INT(_kern, OID_AUTO, pin_default_swi, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &pin_default_swi,
 124     0, "Pin the default (non-per-cpu) swi (shared with PCPU 0 swi)");
 125 SYSCTL_INT(_kern, OID_AUTO, pin_pcpu_swi, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &pin_pcpu_swi,
 126     0, "Pin the per-CPU swis (except PCPU 0, which is also default)");
 127
 128 /*
 129  * TODO:
 130  *      allocate more timeout table slots when table overflows.
 131  */
 132 static u_int __read_mostly callwheelsize;
 133 static u_int __read_mostly callwheelmask;
 134
 135 /*
 136  * The callout cpu exec entities represent informations necessary for
 137  * describing the state of callouts currently running on the CPU and the ones
 138  * necessary for migrating callouts to the new callout cpu. In particular,
 139  * the first entry of the array cc_exec_entity holds informations for callout
 140  * running in SWI thread context, while the second one holds informations
 141  * for callout running directly from hardware interrupt context.
 142  * The cached informations are very important for deferring migration when
 143  * the migrating callout is already running.
 144  */
 145 struct cc_exec {
 146         struct callout          *cc_curr;
 147         callout_func_t          *cc_drain;
 148         void                    *cc_last_func;
 149         void                    *cc_last_arg;
 150 #ifdef SMP
 151         callout_func_t          *ce_migration_func;
 152         void                    *ce_migration_arg;
 153         sbintime_t              ce_migration_time;
 154         sbintime_t              ce_migration_prec;
 155         int                     ce_migration_cpu;
 156 #endif
 157         bool                    cc_cancel;
 158         bool                    cc_waiting;
 159 };
 160
 161 /*
 162  * There is one struct callout_cpu per cpu, holding all relevant
 163  * state for the callout processing thread on the individual CPU.
 164  */
 165 struct callout_cpu {
 166         struct mtx_padalign     cc_lock;
 167         struct cc_exec          cc_exec_entity[2];
 168         struct callout          *cc_next;
 169         struct callout_list     *cc_callwheel;
 170         struct callout_tailq    cc_expireq;
 171         sbintime_t              cc_firstevent;
 172         sbintime_t              cc_lastscan;
 173         struct thread           *cc_thread;
 174         u_int                   cc_bucket;
 175 #ifdef KTR
 176         char                    cc_ktr_event_name[20];
 177 #endif
 178 };
 179
 180 #define callout_migrating(c)    ((c)->c_iflags & CALLOUT_DFRMIGRATION)
 181
 182 #define cc_exec_curr(cc, dir)           cc->cc_exec_entity[dir].cc_curr
 183 #define cc_exec_last_func(cc, dir)      cc->cc_exec_entity[dir].cc_last_func
 184 #define cc_exec_last_arg(cc, dir)       cc->cc_exec_entity[dir].cc_last_arg
 185 #define cc_exec_drain(cc, dir)          cc->cc_exec_entity[dir].cc_drain
 186 #define cc_exec_next(cc)                cc->cc_next
 187 #define cc_exec_cancel(cc, dir)         cc->cc_exec_entity[dir].cc_cancel
 188 #define cc_exec_waiting(cc, dir)        cc->cc_exec_entity[dir].cc_waiting
 189 #ifdef SMP
 190 #define cc_migration_func(cc, dir)      cc->cc_exec_entity[dir].ce_migration_func
 191 #define cc_migration_arg(cc, dir)       cc->cc_exec_entity[dir].ce_migration_arg
 192 #define cc_migration_cpu(cc, dir)       cc->cc_exec_entity[dir].ce_migration_cpu
 193 #define cc_migration_time(cc, dir)      cc->cc_exec_entity[dir].ce_migration_time
 194 #define cc_migration_prec(cc, dir)      cc->cc_exec_entity[dir].ce_migration_prec
 195
 196 DPCPU_DEFINE_STATIC(struct callout_cpu, cc_cpu);
 197 #define CPUBLOCK        MAXCPU
 198 #define CC_CPU(cpu)     DPCPU_ID_PTR(cpu, cc_cpu)
 199 #define CC_SELF()       CC_CPU(PCPU_GET(cpuid))
 200 #else
 201 static struct callout_cpu cc_cpu;
 202 #define CC_CPU(cpu)     (&cc_cpu)
 203 #define CC_SELF()       (&cc_cpu)
 204 #endif
 205 #define CC_LOCK(cc)     mtx_lock_spin(&(cc)->cc_lock)
 206 #define CC_UNLOCK(cc)   mtx_unlock_spin(&(cc)->cc_lock)
 207 #define CC_LOCK_ASSERT(cc)      mtx_assert(&(cc)->cc_lock, MA_OWNED)
 208
 209 static int __read_mostly cc_default_cpu;
 210
 211 static void     callout_cpu_init(struct callout_cpu *cc, int cpu);
 212 static void     softclock_call_cc(struct callout *c, struct callout_cpu *cc,
 213 #ifdef CALLOUT_PROFILING
 214                     int *mpcalls, int *lockcalls, int *gcalls,
 215 #endif
 216                     int direct);
 217
 218 static MALLOC_DEFINE(M_CALLOUT, "callout", "Callout datastructures");
 219
 220 /**
 221  * Locked by cc_lock:
 222  *   cc_curr         - If a callout is in progress, it is cc_curr.
 223  *                     If cc_curr is non-NULL, threads waiting in
 224  *                     callout_drain() will be woken up as soon as the
 225  *                     relevant callout completes.
 226  *   cc_cancel       - Changing to 1 with both callout_lock and cc_lock held
 227  *                     guarantees that the current callout will not run.
 228  *                     The softclock_call_cc() function sets this to 0 before it
 229  *                     drops callout_lock to acquire c_lock, and it calls
 230  *                     the handler only if curr_cancelled is still 0 after
 231  *                     cc_lock is successfully acquired.
 232  *   cc_waiting      - If a thread is waiting in callout_drain(), then
 233  *                     callout_wait is nonzero.  Set only when
 234  *                     cc_curr is non-NULL.
 235  */
 236
 237 /*
 238  * Resets the execution entity tied to a specific callout cpu.
 239  */
 240 static void
 241 cc_cce_cleanup(struct callout_cpu *cc, int direct)
 242 {
 243
 244         cc_exec_curr(cc, direct) = NULL;
 245         cc_exec_cancel(cc, direct) = false;
 246         cc_exec_waiting(cc, direct) = false;
 247 #ifdef SMP
 248         cc_migration_cpu(cc, direct) = CPUBLOCK;
 249         cc_migration_time(cc, direct) = 0;
 250         cc_migration_prec(cc, direct) = 0;
 251         cc_migration_func(cc, direct) = NULL;
 252         cc_migration_arg(cc, direct) = NULL;
 253 #endif
 254 }
 255
 256 /*
 257  * Checks if migration is requested by a specific callout cpu.
 258  */
 259 static int
 260 cc_cce_migrating(struct callout_cpu *cc, int direct)
 261 {
 262
 263 #ifdef SMP
 264         return (cc_migration_cpu(cc, direct) != CPUBLOCK);
 265 #else
 266         return (0);
 267 #endif
 268 }
 269
 270 /*
 271  * Kernel low level callwheel initialization
 272  * called on the BSP during kernel startup.
 273  */
 274 static void
 275 callout_callwheel_init(void *dummy)
 276 {
 277         struct callout_cpu *cc;
 278         int cpu;
 279
 280         /*
 281          * Calculate the size of the callout wheel and the preallocated
 282          * timeout() structures.
 283          * XXX: Clip callout to result of previous function of maxusers
 284          * maximum 384.  This is still huge, but acceptable.
 285          */
 286         ncallout = imin(16 + maxproc + maxfiles, 18508);
 287         TUNABLE_INT_FETCH("kern.ncallout", &ncallout);
 288
 289         /*
 290          * Calculate callout wheel size, should be next power of two higher
 291          * than 'ncallout'.
 292          */
 293         callwheelsize = 1 << fls(ncallout);
 294         callwheelmask = callwheelsize - 1;
 295
 296         /*
 297          * Fetch whether we're pinning the swi's or not.
 298          */
 299         TUNABLE_INT_FETCH("kern.pin_default_swi", &pin_default_swi);
 300         TUNABLE_INT_FETCH("kern.pin_pcpu_swi", &pin_pcpu_swi);
 301
 302         /*
 303          * Initialize callout wheels.  The software interrupt threads
 304          * are created later.
 305          */
 306         cc_default_cpu = PCPU_GET(cpuid);
 307         CPU_FOREACH(cpu) {
 308                 cc = CC_CPU(cpu);
 309                 callout_cpu_init(cc, cpu);
 310         }
 311 }
 312 SYSINIT(callwheel_init, SI_SUB_CPU, SI_ORDER_ANY, callout_callwheel_init, NULL);
 313
 314 /*
 315  * Initialize the per-cpu callout structures.
 316  */
 317 static void
 318 callout_cpu_init(struct callout_cpu *cc, int cpu)
 319 {
 320         int i;
 321
 322         mtx_init(&cc->cc_lock, "callout", NULL, MTX_SPIN);
 323         cc->cc_callwheel = malloc_domainset(sizeof(struct callout_list) *
 324             callwheelsize, M_CALLOUT,
 325             DOMAINSET_PREF(pcpu_find(cpu)->pc_domain), M_WAITOK);
 326         for (i = 0; i < callwheelsize; i++)
 327                 LIST_INIT(&cc->cc_callwheel[i]);
 328         TAILQ_INIT(&cc->cc_expireq);
 329         cc->cc_firstevent = SBT_MAX;
 330         for (i = 0; i < 2; i++)
 331                 cc_cce_cleanup(cc, i);
 332 #ifdef KTR
 333         snprintf(cc->cc_ktr_event_name, sizeof(cc->cc_ktr_event_name),
 334             "callwheel cpu %d", cpu);
 335 #endif
 336 }
 337
 338 #ifdef SMP
 339 /*
 340  * Switches the cpu tied to a specific callout.
 341  * The function expects a locked incoming callout cpu and returns with
 342  * locked outcoming callout cpu.
 343  */
 344 static struct callout_cpu *
 345 callout_cpu_switch(struct callout *c, struct callout_cpu *cc, int new_cpu)
 346 {
 347         struct callout_cpu *new_cc;
 348
 349         MPASS(c != NULL && cc != NULL);
 350         CC_LOCK_ASSERT(cc);
 351
 352         /*
 353          * Avoid interrupts and preemption firing after the callout cpu
 354          * is blocked in order to avoid deadlocks as the new thread
 355          * may be willing to acquire the callout cpu lock.
 356          */
 357         c->c_cpu = CPUBLOCK;
 358         spinlock_enter();
 359         CC_UNLOCK(cc);
 360         new_cc = CC_CPU(new_cpu);
 361         CC_LOCK(new_cc);
 362         spinlock_exit();
 363         c->c_cpu = new_cpu;
 364         return (new_cc);
 365 }
 366 #endif
 367
 368 /*
 369  * Start softclock threads.
 370  */
 371 static void
 372 start_softclock(void *dummy)
 373 {
 374         struct proc *p;
 375         struct thread *td;
 376         struct callout_cpu *cc;
 377         int cpu, error;
 378         bool pin_swi;
 379
 380         p = NULL;
 381         CPU_FOREACH(cpu) {
 382                 cc = CC_CPU(cpu);
 383                 error = kproc_kthread_add(softclock_thread, cc, &p, &td,
 384                     RFSTOPPED, 0, "clock", "clock (%d)", cpu);
 385                 if (error != 0)
 386                         panic("failed to create softclock thread for cpu %d: %d",
 387                             cpu, error);
 388                 CC_LOCK(cc);
 389                 cc->cc_thread = td;
 390                 thread_lock(td);
 391                 sched_class(td, PRI_ITHD);
 392                 sched_ithread_prio(td, PI_SOFTCLOCK);
 393                 TD_SET_IWAIT(td);
 394                 thread_lock_set(td, (struct mtx *)&cc->cc_lock);
 395                 thread_unlock(td);
 396                 if (cpu == cc_default_cpu)
 397                         pin_swi = pin_default_swi;
 398                 else
 399                         pin_swi = pin_pcpu_swi;
 400                 if (pin_swi) {
 401                         error = cpuset_setithread(td->td_tid, cpu);
 402                         if (error != 0)
 403                                 printf("%s: %s clock couldn't be pinned to cpu %d: %d\n",
 404                                     __func__, cpu == cc_default_cpu ?
 405                                     "default" : "per-cpu", cpu, error);
 406                 }
 407         }
 408 }
 409 SYSINIT(start_softclock, SI_SUB_SOFTINTR, SI_ORDER_FIRST, start_softclock, NULL);
 410
 411 #define CC_HASH_SHIFT   8
 412
 413 static inline u_int
 414 callout_hash(sbintime_t sbt)
 415 {
 416
 417         return (sbt >> (32 - CC_HASH_SHIFT));
 418 }
 419
 420 static inline u_int
 421 callout_get_bucket(sbintime_t sbt)
 422 {
 423
 424         return (callout_hash(sbt) & callwheelmask);
 425 }
 426
 427 void
 428 callout_process(sbintime_t now)
 429 {
 430         struct callout_entropy {
 431                 struct callout_cpu *cc;
 432                 struct thread *td;
 433                 sbintime_t now;
 434         } entropy;
 435         struct callout *c, *next;
 436         struct callout_cpu *cc;
 437         struct callout_list *sc;
 438         struct thread *td;
 439         sbintime_t first, last, lookahead, max, tmp_max;
 440         u_int firstb, lastb, nowb;
 441 #ifdef CALLOUT_PROFILING
 442         int depth_dir = 0, mpcalls_dir = 0, lockcalls_dir = 0;
 443 #endif
 444
 445         cc = CC_SELF();
 446         mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET);
 447
 448         /* Compute the buckets of the last scan and present times. */
 449         firstb = callout_hash(cc->cc_lastscan);
 450         cc->cc_lastscan = now;
 451         nowb = callout_hash(now);
 452
 453         /* Compute the last bucket and minimum time of the bucket after it. */
 454         if (nowb == firstb)
 455                 lookahead = (SBT_1S / 16);
 456         else if (nowb - firstb == 1)
 457                 lookahead = (SBT_1S / 8);
 458         else
 459                 lookahead = SBT_1S;
 460         first = last = now;
 461         first += (lookahead / 2);
 462         last += lookahead;
 463         last &= (0xffffffffffffffffLLU << (32 - CC_HASH_SHIFT));
 464         lastb = callout_hash(last) - 1;
 465         max = last;
 466
 467         /*
 468          * Check if we wrapped around the entire wheel from the last scan.
 469          * In case, we need to scan entirely the wheel for pending callouts.
 470          */
 471         if (lastb - firstb >= callwheelsize) {
 472                 lastb = firstb + callwheelsize - 1;
 473                 if (nowb - firstb >= callwheelsize)
 474                         nowb = lastb;
 475         }
 476
 477         /* Iterate callwheel from firstb to nowb and then up to lastb. */
 478         do {
 479                 sc = &cc->cc_callwheel[firstb & callwheelmask];
 480                 LIST_FOREACH_SAFE(c, sc, c_links.le, next) {
 481                         /* Run the callout if present time within allowed. */
 482                         if (c->c_time <= now) {
 483                                 /*
 484                                  * Consumer told us the callout may be run
 485                                  * directly from hardware interrupt context.
 486                                  */
 487                                 if (c->c_iflags & CALLOUT_DIRECT) {
 488 #ifdef CALLOUT_PROFILING
 489                                         ++depth_dir;
 490 #endif
 491                                         cc_exec_next(cc) = next;
 492                                         cc->cc_bucket = firstb & callwheelmask;
 493                                         LIST_REMOVE(c, c_links.le);
 494                                         softclock_call_cc(c, cc,
 495 #ifdef CALLOUT_PROFILING
 496                                             &mpcalls_dir, &lockcalls_dir, NULL,
 497 #endif
 498                                             1);
 499                                         next = cc_exec_next(cc);
 500                                         cc_exec_next(cc) = NULL;
 501                                 } else {
 502                                         LIST_REMOVE(c, c_links.le);
 503                                         TAILQ_INSERT_TAIL(&cc->cc_expireq,
 504                                             c, c_links.tqe);
 505                                         c->c_iflags |= CALLOUT_PROCESSED;
 506                                 }
 507                         } else if (c->c_time >= max) {
 508                                 /*
 509                                  * Skip events in the distant future.
 510                                  */
 511                                 ;
 512                         } else if (c->c_time > last) {
 513                                 /*
 514                                  * Event minimal time is bigger than present
 515                                  * maximal time, so it cannot be aggregated.
 516                                  */
 517                                 lastb = nowb;
 518                         } else {
 519                                 /*
 520                                  * Update first and last time, respecting this
 521                                  * event.
 522                                  */
 523                                 if (c->c_time < first)
 524                                         first = c->c_time;
 525                                 tmp_max = c->c_time + c->c_precision;
 526                                 if (tmp_max < last)
 527                                         last = tmp_max;
 528                         }
 529                 }
 530                 /* Proceed with the next bucket. */
 531                 firstb++;
 532                 /*
 533                  * Stop if we looked after present time and found
 534                  * some event we can't execute at now.
 535                  * Stop if we looked far enough into the future.
 536                  */
 537         } while (((int)(firstb - lastb)) <= 0);
 538         cc->cc_firstevent = last;
 539         cpu_new_callout(curcpu, last, first);
 540
 541 #ifdef CALLOUT_PROFILING
 542         avg_depth_dir += (depth_dir * 1000 - avg_depth_dir) >> 8;
 543         avg_mpcalls_dir += (mpcalls_dir * 1000 - avg_mpcalls_dir) >> 8;
 544         avg_lockcalls_dir += (lockcalls_dir * 1000 - avg_lockcalls_dir) >> 8;
 545 #endif
 546         if (!TAILQ_EMPTY(&cc->cc_expireq)) {
 547                 entropy.cc = cc;
 548                 entropy.td = curthread;
 549                 entropy.now = now;
 550                 random_harvest_queue(&entropy, sizeof(entropy), RANDOM_CALLOUT);
 551
 552                 td = cc->cc_thread;
 553                 if (TD_AWAITING_INTR(td)) {
 554                         thread_lock_block_wait(td);
 555                         THREAD_LOCK_ASSERT(td, MA_OWNED);
 556                         TD_CLR_IWAIT(td);
 557                         sched_wakeup(td, SRQ_INTR);
 558                 } else
 559                         mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET);
 560         } else
 561                 mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET);
 562 }
 563
 564 static struct callout_cpu *
 565 callout_lock(struct callout *c)
 566 {
 567         struct callout_cpu *cc;
 568         int cpu;
 569
 570         for (;;) {
 571                 cpu = c->c_cpu;
 572 #ifdef SMP
 573                 if (cpu == CPUBLOCK) {
 574                         while (c->c_cpu == CPUBLOCK)
 575                                 cpu_spinwait();
 576                         continue;
 577                 }
 578 #endif
 579                 cc = CC_CPU(cpu);
 580                 CC_LOCK(cc);
 581                 if (cpu == c->c_cpu)
 582                         break;
 583                 CC_UNLOCK(cc);
 584         }
 585         return (cc);
 586 }
 587
 588 static void
 589 callout_cc_add(struct callout *c, struct callout_cpu *cc,
 590     sbintime_t sbt, sbintime_t precision, void (*func)(void *),
 591     void *arg, int flags)
 592 {
 593         int bucket;
 594
 595         CC_LOCK_ASSERT(cc);
 596         if (sbt < cc->cc_lastscan)
 597                 sbt = cc->cc_lastscan;
 598         c->c_arg = arg;
 599         c->c_iflags |= CALLOUT_PENDING;
 600         c->c_iflags &= ~CALLOUT_PROCESSED;
 601         c->c_flags |= CALLOUT_ACTIVE;
 602         if (flags & C_DIRECT_EXEC)
 603                 c->c_iflags |= CALLOUT_DIRECT;
 604         c->c_func = func;
 605         c->c_time = sbt;
 606         c->c_precision = precision;
 607         bucket = callout_get_bucket(c->c_time);
 608         CTR3(KTR_CALLOUT, "precision set for %p: %d.%08x",
 609             c, (int)(c->c_precision >> 32),
 610             (u_int)(c->c_precision & 0xffffffff));
 611         LIST_INSERT_HEAD(&cc->cc_callwheel[bucket], c, c_links.le);
 612         if (cc->cc_bucket == bucket)
 613                 cc_exec_next(cc) = c;
 614
 615         /*
 616          * Inform the eventtimers(4) subsystem there's a new callout
 617          * that has been inserted, but only if really required.
 618          */
 619         if (SBT_MAX - c->c_time < c->c_precision)
 620                 c->c_precision = SBT_MAX - c->c_time;
 621         sbt = c->c_time + c->c_precision;
 622         if (sbt < cc->cc_firstevent) {
 623                 cc->cc_firstevent = sbt;
 624                 cpu_new_callout(c->c_cpu, sbt, c->c_time);
 625         }
 626 }
 627
 628 static void
 629 softclock_call_cc(struct callout *c, struct callout_cpu *cc,
 630 #ifdef CALLOUT_PROFILING
 631     int *mpcalls, int *lockcalls, int *gcalls,
 632 #endif
 633     int direct)
 634 {
 635         struct rm_priotracker tracker;
 636         callout_func_t *c_func, *drain;
 637         void *c_arg;
 638         struct lock_class *class;
 639         struct lock_object *c_lock;
 640         uintptr_t lock_status;
 641         int c_iflags;
 642 #ifdef SMP
 643         struct callout_cpu *new_cc;
 644         callout_func_t *new_func;
 645         void *new_arg;
 646         int flags, new_cpu;
 647         sbintime_t new_prec, new_time;
 648 #endif
 649 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
 650         sbintime_t sbt1, sbt2;
 651         struct timespec ts2;
 652         static sbintime_t maxdt = 2 * SBT_1MS;  /* 2 msec */
 653         static callout_func_t *lastfunc;
 654 #endif
 655
 656         KASSERT((c->c_iflags & CALLOUT_PENDING) == CALLOUT_PENDING,
 657             ("softclock_call_cc: pend %p %x", c, c->c_iflags));
 658         KASSERT((c->c_flags & CALLOUT_ACTIVE) == CALLOUT_ACTIVE,
 659             ("softclock_call_cc: act %p %x", c, c->c_flags));
 660         class = (c->c_lock != NULL) ? LOCK_CLASS(c->c_lock) : NULL;
 661         lock_status = 0;
 662         if (c->c_iflags & CALLOUT_SHAREDLOCK) {
 663                 if (class == &lock_class_rm)
 664                         lock_status = (uintptr_t)&tracker;
 665                 else
 666                         lock_status = 1;
 667         }
 668         c_lock = c->c_lock;
 669         c_func = c->c_func;
 670         c_arg = c->c_arg;
 671         c_iflags = c->c_iflags;
 672         c->c_iflags &= ~CALLOUT_PENDING;
 673
 674         cc_exec_curr(cc, direct) = c;
 675         cc_exec_last_func(cc, direct) = c_func;
 676         cc_exec_last_arg(cc, direct) = c_arg;
 677         cc_exec_cancel(cc, direct) = false;
 678         cc_exec_drain(cc, direct) = NULL;
 679         CC_UNLOCK(cc);
 680         if (c_lock != NULL) {
 681                 class->lc_lock(c_lock, lock_status);
 682                 /*
 683                  * The callout may have been cancelled
 684                  * while we switched locks.
 685                  */
 686                 if (cc_exec_cancel(cc, direct)) {
 687                         class->lc_unlock(c_lock);
 688                         goto skip;
 689                 }
 690                 /* The callout cannot be stopped now. */
 691                 cc_exec_cancel(cc, direct) = true;
 692                 if (c_lock == &Giant.lock_object) {
 693 #ifdef CALLOUT_PROFILING
 694                         (*gcalls)++;
 695 #endif
 696                         CTR3(KTR_CALLOUT, "callout giant %p func %p arg %p",
 697                             c, c_func, c_arg);
 698                 } else {
 699 #ifdef CALLOUT_PROFILING
 700                         (*lockcalls)++;
 701 #endif
 702                         CTR3(KTR_CALLOUT, "callout lock %p func %p arg %p",
 703                             c, c_func, c_arg);
 704                 }
 705         } else {
 706 #ifdef CALLOUT_PROFILING
 707                 (*mpcalls)++;
 708 #endif
 709                 CTR3(KTR_CALLOUT, "callout %p func %p arg %p",
 710                     c, c_func, c_arg);
 711         }
 712         KTR_STATE3(KTR_SCHED, "callout", cc->cc_ktr_event_name, "running",
 713             "func:%p", c_func, "arg:%p", c_arg, "direct:%d", direct);
 714 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
 715         sbt1 = sbinuptime();
 716 #endif
 717         THREAD_NO_SLEEPING();
 718         SDT_PROBE1(callout_execute, , , callout__start, c);
 719         c_func(c_arg);
 720         SDT_PROBE1(callout_execute, , , callout__end, c);
 721         THREAD_SLEEPING_OK();
 722 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
 723         sbt2 = sbinuptime();
 724         sbt2 -= sbt1;
 725         if (sbt2 > maxdt) {
 726                 if (lastfunc != c_func || sbt2 > maxdt * 2) {
 727                         ts2 = sbttots(sbt2);
 728                         printf(
 729                 "Expensive callout(9) function: %p(%p) %jd.%09ld s\n",
 730                             c_func, c_arg, (intmax_t)ts2.tv_sec, ts2.tv_nsec);
 731                 }
 732                 maxdt = sbt2;
 733                 lastfunc = c_func;
 734         }
 735 #endif
 736         KTR_STATE0(KTR_SCHED, "callout", cc->cc_ktr_event_name, "idle");
 737         CTR1(KTR_CALLOUT, "callout %p finished", c);
 738         if ((c_iflags & CALLOUT_RETURNUNLOCKED) == 0)
 739                 class->lc_unlock(c_lock);
 740 skip:
 741         CC_LOCK(cc);
 742         KASSERT(cc_exec_curr(cc, direct) == c, ("mishandled cc_curr"));
 743         cc_exec_curr(cc, direct) = NULL;
 744         if (cc_exec_drain(cc, direct)) {
 745                 drain = cc_exec_drain(cc, direct);
 746                 cc_exec_drain(cc, direct) = NULL;
 747                 CC_UNLOCK(cc);
 748                 drain(c_arg);
 749                 CC_LOCK(cc);
 750         }
 751         if (cc_exec_waiting(cc, direct)) {
 752                 /*
 753                  * There is someone waiting for the
 754                  * callout to complete.
 755                  * If the callout was scheduled for
 756                  * migration just cancel it.
 757                  */
 758                 if (cc_cce_migrating(cc, direct)) {
 759                         cc_cce_cleanup(cc, direct);
 760
 761                         /*
 762                          * It should be assert here that the callout is not
 763                          * destroyed but that is not easy.
 764                          */
 765                         c->c_iflags &= ~CALLOUT_DFRMIGRATION;
 766                 }
 767                 cc_exec_waiting(cc, direct) = false;
 768                 CC_UNLOCK(cc);
 769                 wakeup(&cc_exec_waiting(cc, direct));
 770                 CC_LOCK(cc);
 771         } else if (cc_cce_migrating(cc, direct)) {
 772 #ifdef SMP
 773                 /*
 774                  * If the callout was scheduled for
 775                  * migration just perform it now.
 776                  */
 777                 new_cpu = cc_migration_cpu(cc, direct);
 778                 new_time = cc_migration_time(cc, direct);
 779                 new_prec = cc_migration_prec(cc, direct);
 780                 new_func = cc_migration_func(cc, direct);
 781                 new_arg = cc_migration_arg(cc, direct);
 782                 cc_cce_cleanup(cc, direct);
 783
 784                 /*
 785                  * It should be assert here that the callout is not destroyed
 786                  * but that is not easy.
 787                  *
 788                  * As first thing, handle deferred callout stops.
 789                  */
 790                 if (!callout_migrating(c)) {
 791                         CTR3(KTR_CALLOUT,
 792                              "deferred cancelled %p func %p arg %p",
 793                              c, new_func, new_arg);
 794                         return;
 795                 }
 796                 c->c_iflags &= ~CALLOUT_DFRMIGRATION;
 797
 798                 new_cc = callout_cpu_switch(c, cc, new_cpu);
 799                 flags = (direct) ? C_DIRECT_EXEC : 0;
 800                 callout_cc_add(c, new_cc, new_time, new_prec, new_func,
 801                     new_arg, flags);
 802                 CC_UNLOCK(new_cc);
 803                 CC_LOCK(cc);
 804 #else
 805                 panic("migration should not happen");
 806 #endif
 807         }
 808 }
 809
 810 /*
 811  * The callout mechanism is based on the work of Adam M. Costello and
 812  * George Varghese, published in a technical report entitled "Redesigning
 813  * the BSD Callout and Timer Facilities" and modified slightly for inclusion
 814  * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
 815  * used in this implementation was published by G. Varghese and T. Lauck in
 816  * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for
 817  * the Efficient Implementation of a Timer Facility" in the Proceedings of
 818  * the 11th ACM Annual Symposium on Operating Systems Principles,
 819  * Austin, Texas Nov 1987.
 820  */
 821
 822 /*
 823  * Software (low priority) clock interrupt thread handler.
 824  * Run periodic events from timeout queue.
 825  */
 826 static void
 827 softclock_thread(void *arg)
 828 {
 829         struct thread *td = curthread;
 830         struct callout_cpu *cc;
 831         struct callout *c;
 832 #ifdef CALLOUT_PROFILING
 833         int depth, gcalls, lockcalls, mpcalls;
 834 #endif
 835
 836         cc = (struct callout_cpu *)arg;
 837         CC_LOCK(cc);
 838         for (;;) {
 839                 while (TAILQ_EMPTY(&cc->cc_expireq)) {
 840                         /*
 841                          * Use CC_LOCK(cc) as the thread_lock while
 842                          * idle.
 843                          */
 844                         thread_lock(td);
 845                         thread_lock_set(td, (struct mtx *)&cc->cc_lock);
 846                         TD_SET_IWAIT(td);
 847                         mi_switch(SW_VOL | SWT_IWAIT);
 848
 849                         /* mi_switch() drops thread_lock(). */
 850                         CC_LOCK(cc);
 851                 }
 852
 853 #ifdef CALLOUT_PROFILING
 854                 depth = gcalls = lockcalls = mpcalls = 0;
 855 #endif
 856                 while ((c = TAILQ_FIRST(&cc->cc_expireq)) != NULL) {
 857                         TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
 858                         softclock_call_cc(c, cc,
 859 #ifdef CALLOUT_PROFILING
 860                             &mpcalls, &lockcalls, &gcalls,
 861 #endif
 862                             0);
 863 #ifdef CALLOUT_PROFILING
 864                         ++depth;
 865 #endif
 866                 }
 867 #ifdef CALLOUT_PROFILING
 868                 avg_depth += (depth * 1000 - avg_depth) >> 8;
 869                 avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8;
 870                 avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8;
 871                 avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8;
 872 #endif
 873         }
 874 }
 875
 876 void
 877 callout_when(sbintime_t sbt, sbintime_t precision, int flags,
 878     sbintime_t *res, sbintime_t *prec_res)
 879 {
 880         sbintime_t to_sbt, to_pr;
 881
 882         if ((flags & (C_ABSOLUTE | C_PRECALC)) != 0) {
 883                 *res = sbt;
 884                 *prec_res = precision;
 885                 return;
 886         }
 887         if ((flags & C_HARDCLOCK) != 0 && sbt < tick_sbt)
 888                 sbt = tick_sbt;
 889         if ((flags & C_HARDCLOCK) != 0 || sbt >= sbt_tickthreshold) {
 890                 /*
 891                  * Obtain the time of the last hardclock() call on
 892                  * this CPU directly from the kern_clocksource.c.
 893                  * This value is per-CPU, but it is equal for all
 894                  * active ones.
 895                  */
 896 #ifdef __LP64__
 897                 to_sbt = DPCPU_GET(hardclocktime);
 898 #else
 899                 spinlock_enter();
 900                 to_sbt = DPCPU_GET(hardclocktime);
 901                 spinlock_exit();
 902 #endif
 903                 if (cold && to_sbt == 0)
 904                         to_sbt = sbinuptime();
 905                 if ((flags & C_HARDCLOCK) == 0)
 906                         to_sbt += tick_sbt;
 907         } else
 908                 to_sbt = sbinuptime();
 909         if (SBT_MAX - to_sbt < sbt)
 910                 to_sbt = SBT_MAX;
 911         else
 912                 to_sbt += sbt;
 913         *res = to_sbt;
 914         to_pr = ((C_PRELGET(flags) < 0) ? sbt >> tc_precexp :
 915             sbt >> C_PRELGET(flags));
 916         *prec_res = to_pr > precision ? to_pr : precision;
 917 }
 918
 919 /*
 920  * New interface; clients allocate their own callout structures.
 921  *
 922  * callout_reset() - establish or change a timeout
 923  * callout_stop() - disestablish a timeout
 924  * callout_init() - initialize a callout structure so that it can
 925  *      safely be passed to callout_reset() and callout_stop()
 926  *
 927  * <sys/callout.h> defines three convenience macros:
 928  *
 929  * callout_active() - returns truth if callout has not been stopped,
 930  *      drained, or deactivated since the last time the callout was
 931  *      reset.
 932  * callout_pending() - returns truth if callout is still waiting for timeout
 933  * callout_deactivate() - marks the callout as having been serviced
 934  */
 935 int
 936 callout_reset_sbt_on(struct callout *c, sbintime_t sbt, sbintime_t prec,
 937     callout_func_t *ftn, void *arg, int cpu, int flags)
 938 {
 939         sbintime_t to_sbt, precision;
 940         struct callout_cpu *cc;
 941         int cancelled, direct;
 942
 943         cancelled = 0;
 944         callout_when(sbt, prec, flags, &to_sbt, &precision);
 945
 946         /*
 947          * This flag used to be added by callout_cc_add, but the
 948          * first time you call this we could end up with the
 949          * wrong direct flag if we don't do it before we add.
 950          */
 951         if (flags & C_DIRECT_EXEC) {
 952                 direct = 1;
 953         } else {
 954                 direct = 0;
 955         }
 956         KASSERT(!direct || c->c_lock == NULL ||
 957             (LOCK_CLASS(c->c_lock)->lc_flags & LC_SPINLOCK),
 958             ("%s: direct callout %p has non-spin lock", __func__, c));
 959
 960         cc = callout_lock(c);
 961         if (cpu == -1)
 962                 cpu = c->c_cpu;
 963         KASSERT(cpu >= 0 && cpu <= mp_maxid && !CPU_ABSENT(cpu),
 964             ("%s: invalid cpu %d", __func__, cpu));
 965
 966         if (cc_exec_curr(cc, direct) == c) {
 967                 /*
 968                  * We're being asked to reschedule a callout which is
 969                  * currently in progress.  If there is a lock then we
 970                  * can cancel the callout if it has not really started.
 971                  */
 972                 if (c->c_lock != NULL && !cc_exec_cancel(cc, direct))
 973                         cancelled = cc_exec_cancel(cc, direct) = true;
 974                 if (cc_exec_waiting(cc, direct) || cc_exec_drain(cc, direct)) {
 975                         /*
 976                          * Someone has called callout_drain to kill this
 977                          * callout.  Don't reschedule.
 978                          */
 979                         CTR4(KTR_CALLOUT, "%s %p func %p arg %p",
 980                             cancelled ? "cancelled" : "failed to cancel",
 981                             c, c->c_func, c->c_arg);
 982                         CC_UNLOCK(cc);
 983                         return (cancelled);
 984                 }
 985 #ifdef SMP
 986                 if (callout_migrating(c)) {
 987                         /*
 988                          * This only occurs when a second callout_reset_sbt_on
 989                          * is made after a previous one moved it into
 990                          * deferred migration (below). Note we do *not* change
 991                          * the prev_cpu even though the previous target may
 992                          * be different.
 993                          */
 994                         cc_migration_cpu(cc, direct) = cpu;
 995                         cc_migration_time(cc, direct) = to_sbt;
 996                         cc_migration_prec(cc, direct) = precision;
 997                         cc_migration_func(cc, direct) = ftn;
 998                         cc_migration_arg(cc, direct) = arg;
 999                         cancelled = 1;
1000                         CC_UNLOCK(cc);
1001                         return (cancelled);
1002                 }
1003 #endif
1004         }
1005         if (c->c_iflags & CALLOUT_PENDING) {
1006                 if ((c->c_iflags & CALLOUT_PROCESSED) == 0) {
1007                         if (cc_exec_next(cc) == c)
1008                                 cc_exec_next(cc) = LIST_NEXT(c, c_links.le);
1009                         LIST_REMOVE(c, c_links.le);
1010                 } else {
1011                         TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
1012                 }
1013                 cancelled = 1;
1014                 c->c_iflags &= ~ CALLOUT_PENDING;
1015                 c->c_flags &= ~ CALLOUT_ACTIVE;
1016         }
1017
1018 #ifdef SMP
1019         /*
1020          * If the callout must migrate try to perform it immediately.
1021          * If the callout is currently running, just defer the migration
1022          * to a more appropriate moment.
1023          */
1024         if (c->c_cpu != cpu) {
1025                 if (cc_exec_curr(cc, direct) == c) {
1026                         /*
1027                          * Pending will have been removed since we are
1028                          * actually executing the callout on another
1029                          * CPU. That callout should be waiting on the
1030                          * lock the caller holds. If we set both
1031                          * active/and/pending after we return and the
1032                          * lock on the executing callout proceeds, it
1033                          * will then see pending is true and return.
1034                          * At the return from the actual callout execution
1035                          * the migration will occur in softclock_call_cc
1036                          * and this new callout will be placed on the
1037                          * new CPU via a call to callout_cpu_switch() which
1038                          * will get the lock on the right CPU followed
1039                          * by a call callout_cc_add() which will add it there.
1040                          * (see above in softclock_call_cc()).
1041                          */
1042                         cc_migration_cpu(cc, direct) = cpu;
1043                         cc_migration_time(cc, direct) = to_sbt;
1044                         cc_migration_prec(cc, direct) = precision;
1045                         cc_migration_func(cc, direct) = ftn;
1046                         cc_migration_arg(cc, direct) = arg;
1047                         c->c_iflags |= (CALLOUT_DFRMIGRATION | CALLOUT_PENDING);
1048                         c->c_flags |= CALLOUT_ACTIVE;
1049                         CTR6(KTR_CALLOUT,
1050                     "migration of %p func %p arg %p in %d.%08x to %u deferred",
1051                             c, c->c_func, c->c_arg, (int)(to_sbt >> 32),
1052                             (u_int)(to_sbt & 0xffffffff), cpu);
1053                         CC_UNLOCK(cc);
1054                         return (cancelled);
1055                 }
1056                 cc = callout_cpu_switch(c, cc, cpu);
1057         }
1058 #endif
1059
1060         callout_cc_add(c, cc, to_sbt, precision, ftn, arg, flags);
1061         CTR6(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d.%08x",
1062             cancelled ? "re" : "", c, c->c_func, c->c_arg, (int)(to_sbt >> 32),
1063             (u_int)(to_sbt & 0xffffffff));
1064         CC_UNLOCK(cc);
1065
1066         return (cancelled);
1067 }
1068
1069 /*
1070  * Common idioms that can be optimized in the future.
1071  */
1072 int
1073 callout_schedule_on(struct callout *c, int to_ticks, int cpu)
1074 {
1075         return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, cpu);
1076 }
1077
1078 int
1079 callout_schedule(struct callout *c, int to_ticks)
1080 {
1081         return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, c->c_cpu);
1082 }
1083
1084 int
1085 _callout_stop_safe(struct callout *c, int flags, callout_func_t *drain)
1086 {
1087         struct callout_cpu *cc, *old_cc;
1088         struct lock_class *class;
1089         int direct, sq_locked, use_lock;
1090         int cancelled, not_on_a_list;
1091
1092         if ((flags & CS_DRAIN) != 0)
1093                 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, c->c_lock,
1094                     "calling %s", __func__);
1095
1096         KASSERT((flags & CS_DRAIN) == 0 || drain == NULL,
1097             ("Cannot set drain callback and CS_DRAIN flag at the same time"));
1098
1099         /*
1100          * Some old subsystems don't hold Giant while running a callout_stop(),
1101          * so just discard this check for the moment.
1102          */
1103         if ((flags & CS_DRAIN) == 0 && c->c_lock != NULL) {
1104                 if (c->c_lock == &Giant.lock_object)
1105                         use_lock = mtx_owned(&Giant);
1106                 else {
1107                         use_lock = 1;
1108                         class = LOCK_CLASS(c->c_lock);
1109                         class->lc_assert(c->c_lock, LA_XLOCKED);
1110                 }
1111         } else
1112                 use_lock = 0;
1113         if (c->c_iflags & CALLOUT_DIRECT) {
1114                 direct = 1;
1115         } else {
1116                 direct = 0;
1117         }
1118         sq_locked = 0;
1119         old_cc = NULL;
1120 again:
1121         cc = callout_lock(c);
1122
1123         if ((c->c_iflags & (CALLOUT_DFRMIGRATION | CALLOUT_PENDING)) ==
1124             (CALLOUT_DFRMIGRATION | CALLOUT_PENDING) &&
1125             ((c->c_flags & CALLOUT_ACTIVE) == CALLOUT_ACTIVE)) {
1126                 /*
1127                  * Special case where this slipped in while we
1128                  * were migrating *as* the callout is about to
1129                  * execute. The caller probably holds the lock
1130                  * the callout wants.
1131                  *
1132                  * Get rid of the migration first. Then set
1133                  * the flag that tells this code *not* to
1134                  * try to remove it from any lists (its not
1135                  * on one yet). When the callout wheel runs,
1136                  * it will ignore this callout.
1137                  */
1138                 c->c_iflags &= ~CALLOUT_PENDING;
1139                 c->c_flags &= ~CALLOUT_ACTIVE;
1140                 not_on_a_list = 1;
1141         } else {
1142                 not_on_a_list = 0;
1143         }
1144
1145         /*
1146          * If the callout was migrating while the callout cpu lock was
1147          * dropped,  just drop the sleepqueue lock and check the states
1148          * again.
1149          */
1150         if (sq_locked != 0 && cc != old_cc) {
1151 #ifdef SMP
1152                 CC_UNLOCK(cc);
1153                 sleepq_release(&cc_exec_waiting(old_cc, direct));
1154                 sq_locked = 0;
1155                 old_cc = NULL;
1156                 goto again;
1157 #else
1158                 panic("migration should not happen");
1159 #endif
1160         }
1161
1162         /*
1163          * If the callout is running, try to stop it or drain it.
1164          */
1165         if (cc_exec_curr(cc, direct) == c) {
1166                 /*
1167                  * Succeed we to stop it or not, we must clear the
1168                  * active flag - this is what API users expect.  If we're
1169                  * draining and the callout is currently executing, first wait
1170                  * until it finishes.
1171                  */
1172                 if ((flags & CS_DRAIN) == 0)
1173                         c->c_flags &= ~CALLOUT_ACTIVE;
1174
1175                 if ((flags & CS_DRAIN) != 0) {
1176                         /*
1177                          * The current callout is running (or just
1178                          * about to run) and blocking is allowed, so
1179                          * just wait for the current invocation to
1180                          * finish.
1181                          */
1182                         if (cc_exec_curr(cc, direct) == c) {
1183                                 /*
1184                                  * Use direct calls to sleepqueue interface
1185                                  * instead of cv/msleep in order to avoid
1186                                  * a LOR between cc_lock and sleepqueue
1187                                  * chain spinlocks.  This piece of code
1188                                  * emulates a msleep_spin() call actually.
1189                                  *
1190                                  * If we already have the sleepqueue chain
1191                                  * locked, then we can safely block.  If we
1192                                  * don't already have it locked, however,
1193                                  * we have to drop the cc_lock to lock
1194                                  * it.  This opens several races, so we
1195                                  * restart at the beginning once we have
1196                                  * both locks.  If nothing has changed, then
1197                                  * we will end up back here with sq_locked
1198                                  * set.
1199                                  */
1200                                 if (!sq_locked) {
1201                                         CC_UNLOCK(cc);
1202                                         sleepq_lock(
1203                                             &cc_exec_waiting(cc, direct));
1204                                         sq_locked = 1;
1205                                         old_cc = cc;
1206                                         goto again;
1207                                 }
1208
1209                                 /*
1210                                  * Migration could be cancelled here, but
1211                                  * as long as it is still not sure when it
1212                                  * will be packed up, just let softclock()
1213                                  * take care of it.
1214                                  */
1215                                 cc_exec_waiting(cc, direct) = true;
1216                                 DROP_GIANT();
1217                                 CC_UNLOCK(cc);
1218                                 sleepq_add(
1219                                     &cc_exec_waiting(cc, direct),
1220                                     &cc->cc_lock.lock_object, "codrain",
1221                                     SLEEPQ_SLEEP, 0);
1222                                 sleepq_wait(
1223                                     &cc_exec_waiting(cc, direct),
1224                                              0);
1225                                 sq_locked = 0;
1226                                 old_cc = NULL;
1227
1228                                 /* Reacquire locks previously released. */
1229                                 PICKUP_GIANT();
1230                                 goto again;
1231                         }
1232                         c->c_flags &= ~CALLOUT_ACTIVE;
1233                 } else if (use_lock &&
1234                            !cc_exec_cancel(cc, direct) && (drain == NULL)) {
1235
1236                         /*
1237                          * The current callout is waiting for its
1238                          * lock which we hold.  Cancel the callout
1239                          * and return.  After our caller drops the
1240                          * lock, the callout will be skipped in
1241                          * softclock(). This *only* works with a
1242                          * callout_stop() *not* callout_drain() or
1243                          * callout_async_drain().
1244                          */
1245                         cc_exec_cancel(cc, direct) = true;
1246                         CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
1247                             c, c->c_func, c->c_arg);
1248                         KASSERT(!cc_cce_migrating(cc, direct),
1249                             ("callout wrongly scheduled for migration"));
1250                         if (callout_migrating(c)) {
1251                                 c->c_iflags &= ~CALLOUT_DFRMIGRATION;
1252 #ifdef SMP
1253                                 cc_migration_cpu(cc, direct) = CPUBLOCK;
1254                                 cc_migration_time(cc, direct) = 0;
1255                                 cc_migration_prec(cc, direct) = 0;
1256                                 cc_migration_func(cc, direct) = NULL;
1257                                 cc_migration_arg(cc, direct) = NULL;
1258 #endif
1259                         }
1260                         CC_UNLOCK(cc);
1261                         KASSERT(!sq_locked, ("sleepqueue chain locked"));
1262                         return (1);
1263                 } else if (callout_migrating(c)) {
1264                         /*
1265                          * The callout is currently being serviced
1266                          * and the "next" callout is scheduled at
1267                          * its completion with a migration. We remove
1268                          * the migration flag so it *won't* get rescheduled,
1269                          * but we can't stop the one thats running so
1270                          * we return 0.
1271                          */
1272                         c->c_iflags &= ~CALLOUT_DFRMIGRATION;
1273 #ifdef SMP
1274                         /*
1275                          * We can't call cc_cce_cleanup here since
1276                          * if we do it will remove .ce_curr and
1277                          * its still running. This will prevent a
1278                          * reschedule of the callout when the
1279                          * execution completes.
1280                          */
1281                         cc_migration_cpu(cc, direct) = CPUBLOCK;
1282                         cc_migration_time(cc, direct) = 0;
1283                         cc_migration_prec(cc, direct) = 0;
1284                         cc_migration_func(cc, direct) = NULL;
1285                         cc_migration_arg(cc, direct) = NULL;
1286 #endif
1287                         CTR3(KTR_CALLOUT, "postponing stop %p func %p arg %p",
1288                             c, c->c_func, c->c_arg);
1289                         if (drain) {
1290                                 KASSERT(cc_exec_drain(cc, direct) == NULL,
1291                                     ("callout drain function already set to %p",
1292                                     cc_exec_drain(cc, direct)));
1293                                 cc_exec_drain(cc, direct) = drain;
1294                         }
1295                         CC_UNLOCK(cc);
1296                         return (0);
1297                 } else {
1298                         CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
1299                             c, c->c_func, c->c_arg);
1300                         if (drain) {
1301                                 KASSERT(cc_exec_drain(cc, direct) == NULL,
1302                                     ("callout drain function already set to %p",
1303                                     cc_exec_drain(cc, direct)));
1304                                 cc_exec_drain(cc, direct) = drain;
1305                         }
1306                 }
1307                 KASSERT(!sq_locked, ("sleepqueue chain still locked"));
1308                 cancelled = 0;
1309         } else
1310                 cancelled = 1;
1311
1312         if (sq_locked)
1313                 sleepq_release(&cc_exec_waiting(cc, direct));
1314
1315         if ((c->c_iflags & CALLOUT_PENDING) == 0) {
1316                 CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
1317                     c, c->c_func, c->c_arg);
1318                 /*
1319                  * For not scheduled and not executing callout return
1320                  * negative value.
1321                  */
1322                 if (cc_exec_curr(cc, direct) != c)
1323                         cancelled = -1;
1324                 CC_UNLOCK(cc);
1325                 return (cancelled);
1326         }
1327
1328         c->c_iflags &= ~CALLOUT_PENDING;
1329         c->c_flags &= ~CALLOUT_ACTIVE;
1330
1331         CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
1332             c, c->c_func, c->c_arg);
1333         if (not_on_a_list == 0) {
1334                 if ((c->c_iflags & CALLOUT_PROCESSED) == 0) {
1335                         if (cc_exec_next(cc) == c)
1336                                 cc_exec_next(cc) = LIST_NEXT(c, c_links.le);
1337                         LIST_REMOVE(c, c_links.le);
1338                 } else {
1339                         TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
1340                 }
1341         }
1342         CC_UNLOCK(cc);
1343         return (cancelled);
1344 }
1345
1346 void
1347 callout_init(struct callout *c, int mpsafe)
1348 {
1349         bzero(c, sizeof *c);
1350         if (mpsafe) {
1351                 c->c_lock = NULL;
1352                 c->c_iflags = CALLOUT_RETURNUNLOCKED;
1353         } else {
1354                 c->c_lock = &Giant.lock_object;
1355                 c->c_iflags = 0;
1356         }
1357         c->c_cpu = cc_default_cpu;
1358 }
1359
1360 void
1361 _callout_init_lock(struct callout *c, struct lock_object *lock, int flags)
1362 {
1363         bzero(c, sizeof *c);
1364         c->c_lock = lock;
1365         KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0,
1366             ("callout_init_lock: bad flags %d", flags));
1367         KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0,
1368             ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock"));
1369         KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags & LC_SLEEPABLE),
1370             ("%s: callout %p has sleepable lock", __func__, c));
1371         c->c_iflags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK);
1372         c->c_cpu = cc_default_cpu;
1373 }
1374
1375 static int
1376 flssbt(sbintime_t sbt)
1377 {
1378
1379         sbt += (uint64_t)sbt >> 1;
1380         if (sizeof(long) >= sizeof(sbintime_t))
1381                 return (flsl(sbt));
1382         if (sbt >= SBT_1S)
1383                 return (flsl(((uint64_t)sbt) >> 32) + 32);
1384         return (flsl(sbt));
1385 }
1386
1387 /*
1388  * Dump immediate statistic snapshot of the scheduled callouts.
1389  */
1390 static int
1391 sysctl_kern_callout_stat(SYSCTL_HANDLER_ARGS)
1392 {
1393         struct callout *tmp;
1394         struct callout_cpu *cc;
1395         struct callout_list *sc;
1396         sbintime_t maxpr, maxt, medpr, medt, now, spr, st, t;
1397         int ct[64], cpr[64], ccpbk[32];
1398         int error, val, i, count, tcum, pcum, maxc, c, medc;
1399         int cpu;
1400
1401         val = 0;
1402         error = sysctl_handle_int(oidp, &val, 0, req);
1403         if (error != 0 || req->newptr == NULL)
1404                 return (error);
1405         count = maxc = 0;
1406         st = spr = maxt = maxpr = 0;
1407         bzero(ccpbk, sizeof(ccpbk));
1408         bzero(ct, sizeof(ct));
1409         bzero(cpr, sizeof(cpr));
1410         now = sbinuptime();
1411         CPU_FOREACH(cpu) {
1412                 cc = CC_CPU(cpu);
1413                 CC_LOCK(cc);
1414                 for (i = 0; i < callwheelsize; i++) {
1415                         sc = &cc->cc_callwheel[i];
1416                         c = 0;
1417                         LIST_FOREACH(tmp, sc, c_links.le) {
1418                                 c++;
1419                                 t = tmp->c_time - now;
1420                                 if (t < 0)
1421                                         t = 0;
1422                                 st += t / SBT_1US;
1423                                 spr += tmp->c_precision / SBT_1US;
1424                                 if (t > maxt)
1425                                         maxt = t;
1426                                 if (tmp->c_precision > maxpr)
1427                                         maxpr = tmp->c_precision;
1428                                 ct[flssbt(t)]++;
1429                                 cpr[flssbt(tmp->c_precision)]++;
1430                         }
1431                         if (c > maxc)
1432                                 maxc = c;
1433                         ccpbk[fls(c + c / 2)]++;
1434                         count += c;
1435                 }
1436                 CC_UNLOCK(cc);
1437         }
1438
1439         for (i = 0, tcum = 0; i < 64 && tcum < count / 2; i++)
1440                 tcum += ct[i];
1441         medt = (i >= 2) ? (((sbintime_t)1) << (i - 2)) : 0;
1442         for (i = 0, pcum = 0; i < 64 && pcum < count / 2; i++)
1443                 pcum += cpr[i];
1444         medpr = (i >= 2) ? (((sbintime_t)1) << (i - 2)) : 0;
1445         for (i = 0, c = 0; i < 32 && c < count / 2; i++)
1446                 c += ccpbk[i];
1447         medc = (i >= 2) ? (1 << (i - 2)) : 0;
1448
1449         printf("Scheduled callouts statistic snapshot:\n");
1450         printf("  Callouts: %6d  Buckets: %6d*%-3d  Bucket size: 0.%06ds\n",
1451             count, callwheelsize, mp_ncpus, 1000000 >> CC_HASH_SHIFT);
1452         printf("  C/Bk: med %5d         avg %6d.%06jd  max %6d\n",
1453             medc,
1454             count / callwheelsize / mp_ncpus,
1455             (uint64_t)count * 1000000 / callwheelsize / mp_ncpus % 1000000,
1456             maxc);
1457         printf("  Time: med %5jd.%06jds avg %6jd.%06jds max %6jd.%06jds\n",
1458             medt / SBT_1S, (medt & 0xffffffff) * 1000000 >> 32,
1459             (st / count) / 1000000, (st / count) % 1000000,
1460             maxt / SBT_1S, (maxt & 0xffffffff) * 1000000 >> 32);
1461         printf("  Prec: med %5jd.%06jds avg %6jd.%06jds max %6jd.%06jds\n",
1462             medpr / SBT_1S, (medpr & 0xffffffff) * 1000000 >> 32,
1463             (spr / count) / 1000000, (spr / count) % 1000000,
1464             maxpr / SBT_1S, (maxpr & 0xffffffff) * 1000000 >> 32);
1465         printf("  Distribution:       \tbuckets\t   time\t   tcum\t"
1466             "   prec\t   pcum\n");
1467         for (i = 0, tcum = pcum = 0; i < 64; i++) {
1468                 if (ct[i] == 0 && cpr[i] == 0)
1469                         continue;
1470                 t = (i != 0) ? (((sbintime_t)1) << (i - 1)) : 0;
1471                 tcum += ct[i];
1472                 pcum += cpr[i];
1473                 printf("  %10jd.%06jds\t 2**%d\t%7d\t%7d\t%7d\t%7d\n",
1474                     t / SBT_1S, (t & 0xffffffff) * 1000000 >> 32,
1475                     i - 1 - (32 - CC_HASH_SHIFT),
1476                     ct[i], tcum, cpr[i], pcum);
1477         }
1478         return (error);
1479 }
1480 SYSCTL_PROC(_kern, OID_AUTO, callout_stat,
1481     CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
1482     0, 0, sysctl_kern_callout_stat, "I",
1483     "Dump immediate statistic snapshot of the scheduled callouts");
1484
1485 #ifdef DDB
1486 static void
1487 _show_callout(struct callout *c)
1488 {
1489
1490         db_printf("callout %p\n", c);
1491 #define C_DB_PRINTF(f, e)       db_printf("   %s = " f "\n", #e, c->e);
1492         db_printf("   &c_links = %p\n", &(c->c_links));
1493         C_DB_PRINTF("%" PRId64, c_time);
1494         C_DB_PRINTF("%" PRId64, c_precision);
1495         C_DB_PRINTF("%p",       c_arg);
1496         C_DB_PRINTF("%p",       c_func);
1497         C_DB_PRINTF("%p",       c_lock);
1498         C_DB_PRINTF("%#x",      c_flags);
1499         C_DB_PRINTF("%#x",      c_iflags);
1500         C_DB_PRINTF("%d",       c_cpu);
1501 #undef  C_DB_PRINTF
1502 }
1503
1504 DB_SHOW_COMMAND(callout, db_show_callout)
1505 {
1506
1507         if (!have_addr) {
1508                 db_printf("usage: show callout <struct callout *>\n");
1509                 return;
1510         }
1511
1512         _show_callout((struct callout *)addr);
1513 }
1514
1515 static void
1516 _show_last_callout(int cpu, int direct, const char *dirstr)
1517 {
1518         struct callout_cpu *cc;
1519         void *func, *arg;
1520
1521         cc = CC_CPU(cpu);
1522         func = cc_exec_last_func(cc, direct);
1523         arg = cc_exec_last_arg(cc, direct);
1524         db_printf("cpu %d last%s callout function: %p ", cpu, dirstr, func);
1525         db_printsym((db_expr_t)func, DB_STGY_ANY);
1526         db_printf("\ncpu %d last%s callout argument: %p\n", cpu, dirstr, arg);
1527 }
1528
1529 DB_SHOW_COMMAND_FLAGS(callout_last, db_show_callout_last, DB_CMD_MEMSAFE)
1530 {
1531         int cpu, last;
1532
1533         if (have_addr) {
1534                 if (addr < 0 || addr > mp_maxid || CPU_ABSENT(addr)) {
1535                         db_printf("no such cpu: %d\n", (int)addr);
1536                         return;
1537                 }
1538                 cpu = last = addr;
1539         } else {
1540                 cpu = 0;
1541                 last = mp_maxid;
1542         }
1543
1544         while (cpu <= last) {
1545                 if (!CPU_ABSENT(cpu)) {
1546                         _show_last_callout(cpu, 0, "");
1547                         _show_last_callout(cpu, 1, " direct");
1548                 }
1549                 cpu++;
1550         }
1551 }
1552 #endif /* DDB */