1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 /*
  27  * Copyright (c) 2012, Joyent Inc. All rights reserved.
  28  */
  29 
  30 /*
  31  *  The Cyclic Subsystem
  32  *  --------------------
  33  *
  34  *  Prehistory
  35  *
  36  *  Historically, most computer architectures have specified interval-based
  37  *  timer parts (e.g. SPARCstation's counter/timer; Intel's i8254).  While
  38  *  these parts deal in relative (i.e. not absolute) time values, they are
  39  *  typically used by the operating system to implement the abstraction of
  40  *  absolute time.  As a result, these parts cannot typically be reprogrammed
  41  *  without introducing error in the system's notion of time.
  42  *
  43  *  Starting in about 1994, chip architectures began specifying high resolution
  44  *  timestamp registers.  As of this writing (1999), all major chip families
  45  *  (UltraSPARC, PentiumPro, MIPS, PowerPC, Alpha) have high resolution
  46  *  timestamp registers, and two (UltraSPARC and MIPS) have added the capacity
  47  *  to interrupt based on timestamp values.  These timestamp-compare registers
  48  *  present a time-based interrupt source which can be reprogrammed arbitrarily
  49  *  often without introducing error.  Given the low cost of implementing such a
  50  *  timestamp-compare register (and the tangible benefit of eliminating
  51  *  discrete timer parts), it is reasonable to expect that future chip
  52  *  architectures will adopt this feature.
  53  *
  54  *  The cyclic subsystem has been designed to take advantage of chip
  55  *  architectures with the capacity to interrupt based on absolute, high
  56  *  resolution values of time.
  57  *
  58  *  Subsystem Overview
  59  *
  60  *  The cyclic subsystem is a low-level kernel subsystem designed to provide
  61  *  arbitrarily high resolution, per-CPU interval timers (to avoid colliding
  62  *  with existing terms, we dub such an interval timer a "cyclic").  Cyclics
  63  *  can be specified to fire at high, lock or low interrupt level, and may be
  64  *  optionally bound to a CPU or a CPU partition.  A cyclic's CPU or CPU
  65  *  partition binding may be changed dynamically; the cyclic will be "juggled"
  66  *  to a CPU which satisfies the new binding.  Alternatively, a cyclic may
  67  *  be specified to be "omnipresent", denoting firing on all online CPUs.
  68  *
  69  *  Cyclic Subsystem Interface Overview
  70  *  -----------------------------------
  71  *
  72  *  The cyclic subsystem has interfaces with the kernel at-large, with other
  73  *  kernel subsystems (e.g. the processor management subsystem, the checkpoint
  74  *  resume subsystem) and with the platform (the cyclic backend).  Each
  75  *  of these interfaces is given a brief synopsis here, and is described
  76  *  in full above the interface's implementation.
  77  *
  78  *  The following diagram displays the cyclic subsystem's interfaces to
  79  *  other kernel components.  The arrows denote a "calls" relationship, with
  80  *  the large arrow indicating the cyclic subsystem's consumer interface.
  81  *  Each arrow is labeled with the section in which the corresponding
  82  *  interface is described.
  83  *
  84  *           Kernel at-large consumers
  85  *           -----------++------------
  86  *                      ||
  87  *                      ||
  88  *                     _||_
  89  *                     \  /
  90  *                      \/
  91  *            +---------------------+
  92  *            |                     |
  93  *            |  Cyclic subsystem   |<-----------  Other kernel subsystems
  94  *            |                     |
  95  *            +---------------------+
  96  *                   ^       |
  97  *                   |       |
  98  *                   |       |
  99  *                   |       v
 100  *            +---------------------+
 101  *            |                     |
 102  *            |   Cyclic backend    |
 103  *            | (platform specific) |
 104  *            |                     |
 105  *            +---------------------+
 106  *
 107  *
 108  *  Kernel At-Large Interfaces
 109  *
 110  *      cyclic_add()         <-- Creates a cyclic
 111  *      cyclic_add_omni()    <-- Creates an omnipresent cyclic
 112  *      cyclic_remove()      <-- Removes a cyclic
 113  *      cyclic_bind()        <-- Change a cyclic's CPU or partition binding
 114  *      cyclic_reprogram()   <-- Reprogram a cyclic's expiration
 115  *
 116  *  Inter-subsystem Interfaces
 117  *
 118  *      cyclic_juggle()      <-- Juggles cyclics away from a CPU
 119  *      cyclic_offline()     <-- Offlines cyclic operation on a CPU
 120  *      cyclic_online()      <-- Reenables operation on an offlined CPU
 121  *      cyclic_move_in()     <-- Notifies subsystem of change in CPU partition
 122  *      cyclic_move_out()    <-- Notifies subsystem of change in CPU partition
 123  *      cyclic_suspend()     <-- Suspends the cyclic subsystem on all CPUs
 124  *      cyclic_resume()      <-- Resumes the cyclic subsystem on all CPUs
 125  *
 126  *  Backend Interfaces
 127  *
 128  *      cyclic_init()        <-- Initializes the cyclic subsystem
 129  *      cyclic_fire()        <-- CY_HIGH_LEVEL interrupt entry point
 130  *      cyclic_softint()     <-- CY_LOCK/LOW_LEVEL soft interrupt entry point
 131  *
 132  *  The backend-supplied interfaces (through the cyc_backend structure) are
 133  *  documented in detail in <sys/cyclic_impl.h>
 134  *
 135  *
 136  *  Cyclic Subsystem Implementation Overview
 137  *  ----------------------------------------
 138  *
 139  *  The cyclic subsystem is designed to minimize interference between cyclics
 140  *  on different CPUs.  Thus, all of the cyclic subsystem's data structures
 141  *  hang off of a per-CPU structure, cyc_cpu.
 142  *
 143  *  Each cyc_cpu has a power-of-two sized array of cyclic structures (the
 144  *  cyp_cyclics member of the cyc_cpu structure).  If cyclic_add() is called
 145  *  and there does not exist a free slot in the cyp_cyclics array, the size of
 146  *  the array will be doubled.  The array will never shrink.  Cyclics are
 147  *  referred to by their index in the cyp_cyclics array, which is of type
 148  *  cyc_index_t.
 149  *
 150  *  The cyclics are kept sorted by expiration time in the cyc_cpu's heap.  The
 151  *  heap is keyed by cyclic expiration time, with parents expiring earlier
 152  *  than their children.
 153  *
 154  *  Heap Management
 155  *
 156  *  The heap is managed primarily by cyclic_fire().  Upon entry, cyclic_fire()
 157  *  compares the root cyclic's expiration time to the current time.  If the
 158  *  expiration time is in the past, cyclic_expire() is called on the root
 159  *  cyclic.  Upon return from cyclic_expire(), the cyclic's new expiration time
 160  *  is derived by adding its interval to its old expiration time, and a
 161  *  downheap operation is performed.  After the downheap, cyclic_fire()
 162  *  examines the (potentially changed) root cyclic, repeating the
 163  *  cyclic_expire()/add interval/cyclic_downheap() sequence until the root
 164  *  cyclic has an expiration time in the future.  This expiration time
 165  *  (guaranteed to be the earliest in the heap) is then communicated to the
 166  *  backend via cyb_reprogram.  Optimal backends will next call cyclic_fire()
 167  *  shortly after the root cyclic's expiration time.
 168  *
 169  *  To allow efficient, deterministic downheap operations, we implement the
 170  *  heap as an array (the cyp_heap member of the cyc_cpu structure), with each
 171  *  element containing an index into the CPU's cyp_cyclics array.
 172  *
 173  *  The heap is laid out in the array according to the following:
 174  *
 175  *   1.  The root of the heap is always in the 0th element of the heap array
 176  *   2.  The left and right children of the nth element are element
 177  *       (((n + 1) << 1) - 1) and element ((n + 1) << 1), respectively.
 178  *
 179  *  This layout is standard (see, e.g., Cormen's "Algorithms"); the proof
 180  *  that these constraints correctly lay out a heap (or indeed, any binary
 181  *  tree) is trivial and left to the reader.
 182  *
 183  *  To see the heap by example, assume our cyclics array has the following
 184  *  members (at time t):
 185  *
 186  *            cy_handler            cy_level      cy_expire
 187  *            ---------------------------------------------
 188  *     [ 0]   clock()                   LOCK     t+10000000
 189  *     [ 1]   deadman()                 HIGH   t+1000000000
 190  *     [ 2]   clock_highres_fire()       LOW          t+100
 191  *     [ 3]   clock_highres_fire()       LOW         t+1000
 192  *     [ 4]   clock_highres_fire()       LOW          t+500
 193  *     [ 5]   (free)                      --             --
 194  *     [ 6]   (free)                      --             --
 195  *     [ 7]   (free)                      --             --
 196  *
 197  *  The heap array could be:
 198  *
 199  *                [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 200  *              +-----+-----+-----+-----+-----+-----+-----+-----+
 201  *              |     |     |     |     |     |     |     |     |
 202  *              |  2  |  3  |  4  |  0  |  1  |  x  |  x  |  x  |
 203  *              |     |     |     |     |     |     |     |     |
 204  *              +-----+-----+-----+-----+-----+-----+-----+-----+
 205  *
 206  *  Graphically, this array corresponds to the following (excuse the ASCII art):
 207  *
 208  *                                       2
 209  *                                       |
 210  *                    +------------------+------------------+
 211  *                    3                                     4
 212  *                    |
 213  *          +---------+--------+
 214  *          0                  1
 215  *
 216  *  Note that the heap is laid out by layer:  all nodes at a given depth are
 217  *  stored in consecutive elements of the array.  Moreover, layers of
 218  *  consecutive depths are in adjacent element ranges.  This property
 219  *  guarantees high locality of reference during downheap operations.
 220  *  Specifically, we are guaranteed that we can downheap to a depth of
 221  *
 222  *      lg (cache_line_size / sizeof (cyc_index_t))
 223  *
 224  *  nodes with at most one cache miss.  On UltraSPARC (64 byte e-cache line
 225  *  size), this corresponds to a depth of four nodes.  Thus, if there are
 226  *  fewer than sixteen cyclics in the heap, downheaps on UltraSPARC miss at
 227  *  most once in the e-cache.
 228  *
 229  *  Downheaps are required to compare siblings as they proceed down the
 230  *  heap.  For downheaps proceeding beyond the one-cache-miss depth, every
 231  *  access to a left child could potentially miss in the cache.  However,
 232  *  if we assume
 233  *
 234  *      (cache_line_size / sizeof (cyc_index_t)) > 2,
 235  *
 236  *  then all siblings are guaranteed to be on the same cache line.  Thus, the
 237  *  miss on the left child will guarantee a hit on the right child; downheaps
 238  *  will incur at most one cache miss per layer beyond the one-cache-miss
 239  *  depth.  The total number of cache misses for heap management during a
 240  *  downheap operation is thus bounded by
 241  *
 242  *      lg (n) - lg (cache_line_size / sizeof (cyc_index_t))
 243  *
 244  *  Traditional pointer-based heaps are implemented without regard to
 245  *  locality.  Downheaps can thus incur two cache misses per layer (one for
 246  *  each child), but at most one cache miss at the root.  This yields a bound
 247  *  of
 248  *
 249  *      2 * lg (n) - 1
 250  *
 251  *  on the total cache misses.
 252  *
 253  *  This difference may seem theoretically trivial (the difference is, after
 254  *  all, constant), but can become substantial in practice -- especially for
 255  *  caches with very large cache lines and high miss penalties (e.g. TLBs).
 256  *
 257  *  Heaps must always be full, balanced trees.  Heap management must therefore
 258  *  track the next point-of-insertion into the heap.  In pointer-based heaps,
 259  *  recomputing this point takes O(lg (n)).  Given the layout of the
 260  *  array-based implementation, however, the next point-of-insertion is
 261  *  always:
 262  *
 263  *      heap[number_of_elements]
 264  *
 265  *  We exploit this property by implementing the free-list in the usused
 266  *  heap elements.  Heap insertion, therefore, consists only of filling in
 267  *  the cyclic at cyp_cyclics[cyp_heap[number_of_elements]], incrementing
 268  *  the number of elements, and performing an upheap.  Heap deletion consists
 269  *  of decrementing the number of elements, swapping the to-be-deleted element
 270  *  with the element at cyp_heap[number_of_elements], and downheaping.
 271  *
 272  *  Filling in more details in our earlier example:
 273  *
 274  *                                               +--- free list head
 275  *                                               |
 276  *                                               V
 277  *
 278  *                [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 279  *              +-----+-----+-----+-----+-----+-----+-----+-----+
 280  *              |     |     |     |     |     |     |     |     |
 281  *              |  2  |  3  |  4  |  0  |  1  |  5  |  6  |  7  |
 282  *              |     |     |     |     |     |     |     |     |
 283  *              +-----+-----+-----+-----+-----+-----+-----+-----+
 284  *
 285  *  To insert into this heap, we would just need to fill in the cyclic at
 286  *  cyp_cyclics[5], bump the number of elements (from 5 to 6) and perform
 287  *  an upheap.
 288  *
 289  *  If we wanted to remove, say, cyp_cyclics[3], we would first scan for it
 290  *  in the cyp_heap, and discover it at cyp_heap[1].  We would then decrement
 291  *  the number of elements (from 5 to 4), swap cyp_heap[1] with cyp_heap[4],
 292  *  and perform a downheap from cyp_heap[1].  The linear scan is required
 293  *  because the cyclic does not keep a backpointer into the heap.  This makes
 294  *  heap manipulation (e.g. downheaps) faster at the expense of removal
 295  *  operations.
 296  *
 297  *  Expiry processing
 298  *
 299  *  As alluded to above, cyclic_expire() is called by cyclic_fire() at
 300  *  CY_HIGH_LEVEL to expire a cyclic.  Cyclic subsystem consumers are
 301  *  guaranteed that for an arbitrary time t in the future, their cyclic
 302  *  handler will have been called (t - cyt_when) / cyt_interval times.  Thus,
 303  *  there must be a one-to-one mapping between a cyclic's expiration at
 304  *  CY_HIGH_LEVEL and its execution at the desired level (either CY_HIGH_LEVEL,
 305  *  CY_LOCK_LEVEL or CY_LOW_LEVEL).
 306  *
 307  *  For CY_HIGH_LEVEL cyclics, this is trivial; cyclic_expire() simply needs
 308  *  to call the handler.
 309  *
 310  *  For CY_LOCK_LEVEL and CY_LOW_LEVEL cyclics, however, there exists a
 311  *  potential disconnect:  if the CPU is at an interrupt level less than
 312  *  CY_HIGH_LEVEL but greater than the level of a cyclic for a period of
 313  *  time longer than twice the cyclic's interval, the cyclic will be expired
 314  *  twice before it can be handled.
 315  *
 316  *  To maintain the one-to-one mapping, we track the difference between the
 317  *  number of times a cyclic has been expired and the number of times it's
 318  *  been handled in a "pending count" (the cy_pend field of the cyclic
 319  *  structure).  cyclic_expire() thus increments the cy_pend count for the
 320  *  expired cyclic and posts a soft interrupt at the desired level.  In the
 321  *  cyclic subsystem's soft interrupt handler, cyclic_softint(), we repeatedly
 322  *  call the cyclic handler and decrement cy_pend until we have decremented
 323  *  cy_pend to zero.
 324  *
 325  *  The Producer/Consumer Buffer
 326  *
 327  *  If we wish to avoid a linear scan of the cyclics array at soft interrupt
 328  *  level, cyclic_softint() must be able to quickly determine which cyclics
 329  *  have a non-zero cy_pend count.  We thus introduce a per-soft interrupt
 330  *  level producer/consumer buffer shared with CY_HIGH_LEVEL.  These buffers
 331  *  are encapsulated in the cyc_pcbuffer structure, and, like cyp_heap, are
 332  *  implemented as cyc_index_t arrays (the cypc_buf member of the cyc_pcbuffer
 333  *  structure).
 334  *
 335  *  The producer (cyclic_expire() running at CY_HIGH_LEVEL) enqueues a cyclic
 336  *  by storing the cyclic's index to cypc_buf[cypc_prodndx] and incrementing
 337  *  cypc_prodndx.  The consumer (cyclic_softint() running at either
 338  *  CY_LOCK_LEVEL or CY_LOW_LEVEL) dequeues a cyclic by loading from
 339  *  cypc_buf[cypc_consndx] and bumping cypc_consndx.  The buffer is empty when
 340  *  cypc_prodndx == cypc_consndx.
 341  *
 342  *  To bound the size of the producer/consumer buffer, cyclic_expire() only
 343  *  enqueues a cyclic if its cy_pend was zero (if the cyclic's cy_pend is
 344  *  non-zero, cyclic_expire() only bumps cy_pend).  Symmetrically,
 345  *  cyclic_softint() only consumes a cyclic after it has decremented the
 346  *  cy_pend count to zero.
 347  *
 348  *  Returning to our example, here is what the CY_LOW_LEVEL producer/consumer
 349  *  buffer might look like:
 350  *
 351  *     cypc_consndx ---+                 +--- cypc_prodndx
 352  *                     |                 |
 353  *                     V                 V
 354  *
 355  *        [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 356  *      +-----+-----+-----+-----+-----+-----+-----+-----+
 357  *      |     |     |     |     |     |     |     |     |
 358  *      |  x  |  x  |  3  |  2  |  4  |  x  |  x  |  x  |   <== cypc_buf
 359  *      |     |     |  .  |  .  |  .  |     |     |     |
 360  *      +-----+-----+- | -+- | -+- | -+-----+-----+-----+
 361  *                     |     |     |
 362  *                     |     |     |              cy_pend  cy_handler
 363  *                     |     |     |          -------------------------
 364  *                     |     |     |          [ 0]      1  clock()
 365  *                     |     |     |          [ 1]      0  deadman()
 366  *                     |     +---- | -------> [ 2]      3  clock_highres_fire()
 367  *                     +---------- | -------> [ 3]      1  clock_highres_fire()
 368  *                                 +--------> [ 4]      1  clock_highres_fire()
 369  *                                            [ 5]      -  (free)
 370  *                                            [ 6]      -  (free)
 371  *                                            [ 7]      -  (free)
 372  *
 373  *  In particular, note that clock()'s cy_pend is 1 but that it is _not_ in
 374  *  this producer/consumer buffer; it would be enqueued in the CY_LOCK_LEVEL
 375  *  producer/consumer buffer.
 376  *
 377  *  Locking
 378  *
 379  *  Traditionally, access to per-CPU data structures shared between
 380  *  interrupt levels is serialized by manipulating programmable interrupt
 381  *  level:  readers and writers are required to raise their interrupt level
 382  *  to that of the highest level writer.
 383  *
 384  *  For the producer/consumer buffers (shared between cyclic_fire()/
 385  *  cyclic_expire() executing at CY_HIGH_LEVEL and cyclic_softint() executing
 386  *  at one of CY_LOCK_LEVEL or CY_LOW_LEVEL), forcing cyclic_softint() to raise
 387  *  programmable interrupt level is undesirable:  aside from the additional
 388  *  latency incurred by manipulating interrupt level in the hot cy_pend
 389  *  processing path, this would create the potential for soft level cy_pend
 390  *  processing to delay CY_HIGH_LEVEL firing and expiry processing.
 391  *  CY_LOCK/LOW_LEVEL cyclics could thereby induce jitter in CY_HIGH_LEVEL
 392  *  cyclics.
 393  *
 394  *  To minimize jitter, then, we would like the cyclic_fire()/cyclic_expire()
 395  *  and cyclic_softint() code paths to be lock-free.
 396  *
 397  *  For cyclic_fire()/cyclic_expire(), lock-free execution is straightforward:
 398  *  because these routines execute at a higher interrupt level than
 399  *  cyclic_softint(), their actions on the producer/consumer buffer appear
 400  *  atomic.  In particular, the increment of cy_pend appears to occur
 401  *  atomically with the increment of cypc_prodndx.
 402  *
 403  *  For cyclic_softint(), however, lock-free execution requires more delicacy.
 404  *  When cyclic_softint() discovers a cyclic in the producer/consumer buffer,
 405  *  it calls the cyclic's handler and attempts to atomically decrement the
 406  *  cy_pend count with a compare&swap operation.
 407  *
 408  *  If the compare&swap operation succeeds, cyclic_softint() behaves
 409  *  conditionally based on the value it atomically wrote to cy_pend:
 410  *
 411  *     - If the cy_pend was decremented to 0, the cyclic has been consumed;
 412  *       cyclic_softint() increments the cypc_consndx and checks for more
 413  *       enqueued work.
 414  *
 415  *     - If the count was decremented to a non-zero value, there is more work
 416  *       to be done on the cyclic; cyclic_softint() calls the cyclic handler
 417  *       and repeats the atomic decrement process.
 418  *
 419  *  If the compare&swap operation fails, cyclic_softint() knows that
 420  *  cyclic_expire() has intervened and bumped the cy_pend count (resizes
 421  *  and removals complicate this, however -- see the sections on their
 422  *  operation, below).  cyclic_softint() thus reloads cy_pend, and re-attempts
 423  *  the atomic decrement.
 424  *
 425  *  Recall that we bound the size of the producer/consumer buffer by
 426  *  having cyclic_expire() only enqueue the specified cyclic if its
 427  *  cy_pend count is zero; this assures that each cyclic is enqueued at
 428  *  most once.  This leads to a critical constraint on cyclic_softint(),
 429  *  however:  after the compare&swap operation which successfully decrements
 430  *  cy_pend to zero, cyclic_softint() must _not_ re-examine the consumed
 431  *  cyclic.  In part to obey this constraint, cyclic_softint() calls the
 432  *  cyclic handler before decrementing cy_pend.
 433  *
 434  *  Resizing
 435  *
 436  *  All of the discussion thus far has assumed a static number of cyclics.
 437  *  Obviously, static limitations are not practical; we need the capacity
 438  *  to resize our data structures dynamically.
 439  *
 440  *  We resize our data structures lazily, and only on a per-CPU basis.
 441  *  The size of the data structures always doubles and never shrinks.  We
 442  *  serialize adds (and thus resizes) on cpu_lock; we never need to deal
 443  *  with concurrent resizes.  Resizes should be rare; they may induce jitter
 444  *  on the CPU being resized, but should not affect cyclic operation on other
 445  *  CPUs.  Pending cyclics may not be dropped during a resize operation.
 446  *
 447  *  Three key cyc_cpu data structures need to be resized:  the cyclics array,
 448  *  the heap array and the producer/consumer buffers.  Resizing the first two
 449  *  is relatively straightforward:
 450  *
 451  *    1.  The new, larger arrays are allocated in cyclic_expand() (called
 452  *        from cyclic_add()).
 453  *    2.  cyclic_expand() cross calls cyclic_expand_xcall() on the CPU
 454  *        undergoing the resize.
 455  *    3.  cyclic_expand_xcall() raises interrupt level to CY_HIGH_LEVEL
 456  *    4.  The contents of the old arrays are copied into the new arrays.
 457  *    5.  The old cyclics array is bzero()'d
 458  *    6.  The pointers are updated.
 459  *
 460  *  The producer/consumer buffer is dicier:  cyclic_expand_xcall() may have
 461  *  interrupted cyclic_softint() in the middle of consumption. To resize the
 462  *  producer/consumer buffer, we implement up to two buffers per soft interrupt
 463  *  level:  a hard buffer (the buffer being produced into by cyclic_expire())
 464  *  and a soft buffer (the buffer from which cyclic_softint() is consuming).
 465  *  During normal operation, the hard buffer and soft buffer point to the
 466  *  same underlying producer/consumer buffer.
 467  *
 468  *  During a resize, however, cyclic_expand_xcall() changes the hard buffer
 469  *  to point to the new, larger producer/consumer buffer; all future
 470  *  cyclic_expire()'s will produce into the new buffer.  cyclic_expand_xcall()
 471  *  then posts a CY_LOCK_LEVEL soft interrupt, landing in cyclic_softint().
 472  *
 473  *  As under normal operation, cyclic_softint() will consume cyclics from
 474  *  its soft buffer.  After the soft buffer is drained, however,
 475  *  cyclic_softint() will see that the hard buffer has changed.  At that time,
 476  *  cyclic_softint() will change its soft buffer to point to the hard buffer,
 477  *  and repeat the producer/consumer buffer draining procedure.
 478  *
 479  *  After the new buffer is drained, cyclic_softint() will determine if both
 480  *  soft levels have seen their new producer/consumer buffer.  If both have,
 481  *  cyclic_softint() will post on the semaphore cyp_modify_wait.  If not, a
 482  *  soft interrupt will be generated for the remaining level.
 483  *
 484  *  cyclic_expand() blocks on the cyp_modify_wait semaphore (a semaphore is
 485  *  used instead of a condition variable because of the race between the
 486  *  sema_p() in cyclic_expand() and the sema_v() in cyclic_softint()).  This
 487  *  allows cyclic_expand() to know when the resize operation is complete;
 488  *  all of the old buffers (the heap, the cyclics array and the producer/
 489  *  consumer buffers) can be freed.
 490  *
 491  *  A final caveat on resizing:  we described step (5) in the
 492  *  cyclic_expand_xcall() procedure without providing any motivation.  This
 493  *  step addresses the problem of a cyclic_softint() attempting to decrement
 494  *  a cy_pend count while interrupted by a cyclic_expand_xcall().  Because
 495  *  cyclic_softint() has already called the handler by the time cy_pend is
 496  *  decremented, we want to assure that it doesn't decrement a cy_pend
 497  *  count in the old cyclics array.  By zeroing the old cyclics array in
 498  *  cyclic_expand_xcall(), we are zeroing out every cy_pend count; when
 499  *  cyclic_softint() attempts to compare&swap on the cy_pend count, it will
 500  *  fail and recognize that the count has been zeroed.  cyclic_softint() will
 501  *  update its stale copy of the cyp_cyclics pointer, re-read the cy_pend
 502  *  count from the new cyclics array, and re-attempt the compare&swap.
 503  *
 504  *  Removals
 505  *
 506  *  Cyclic removals should be rare.  To simplify the implementation (and to
 507  *  allow optimization for the cyclic_fire()/cyclic_expire()/cyclic_softint()
 508  *  path), we force removals and adds to serialize on cpu_lock.
 509  *
 510  *  Cyclic removal is complicated by a guarantee made to the consumer of
 511  *  the cyclic subsystem:  after cyclic_remove() returns, the cyclic handler
 512  *  has returned and will never again be called.
 513  *
 514  *  Here is the procedure for cyclic removal:
 515  *
 516  *    1.  cyclic_remove() calls cyclic_remove_xcall() on the CPU undergoing
 517  *        the removal.
 518  *    2.  cyclic_remove_xcall() raises interrupt level to CY_HIGH_LEVEL
 519  *    3.  The current expiration time for the removed cyclic is recorded.
 520  *    4.  If the cy_pend count on the removed cyclic is non-zero, it
 521  *        is copied into cyp_rpend and subsequently zeroed.
 522  *    5.  The cyclic is removed from the heap
 523  *    6.  If the root of the heap has changed, the backend is reprogrammed.
 524  *    7.  If the cy_pend count was non-zero cyclic_remove() blocks on the
 525  *        cyp_modify_wait semaphore.
 526  *
 527  *  The motivation for step (3) is explained in "Juggling", below.
 528  *
 529  *  The cy_pend count is decremented in cyclic_softint() after the cyclic
 530  *  handler returns.  Thus, if we find a cy_pend count of zero in step
 531  *  (4), we know that cyclic_remove() doesn't need to block.
 532  *
 533  *  If the cy_pend count is non-zero, however, we must block in cyclic_remove()
 534  *  until cyclic_softint() has finished calling the cyclic handler.  To let
 535  *  cyclic_softint() know that this cyclic has been removed, we zero the
 536  *  cy_pend count.  This will cause cyclic_softint()'s compare&swap to fail.
 537  *  When cyclic_softint() sees the zero cy_pend count, it knows that it's been
 538  *  caught during a resize (see "Resizing", above) or that the cyclic has been
 539  *  removed.  In the latter case, it calls cyclic_remove_pend() to call the
 540  *  cyclic handler cyp_rpend - 1 times, and posts on cyp_modify_wait.
 541  *
 542  *  Juggling
 543  *
 544  *  At first glance, cyclic juggling seems to be a difficult problem.  The
 545  *  subsystem must guarantee that a cyclic doesn't execute simultaneously on
 546  *  different CPUs, while also assuring that a cyclic fires exactly once
 547  *  per interval.  We solve this problem by leveraging a property of the
 548  *  platform:  gethrtime() is required to increase in lock-step across
 549  *  multiple CPUs.  Therefore, to juggle a cyclic, we remove it from its
 550  *  CPU, recording its expiration time in the remove cross call (step (3)
 551  *  in "Removing", above).  We then add the cyclic to the new CPU, explicitly
 552  *  setting its expiration time to the time recorded in the removal.  This
 553  *  leverages the existing cyclic expiry processing, which will compensate
 554  *  for any time lost while juggling.
 555  *
 556  *  Reprogramming
 557  *
 558  *  Normally, after a cyclic fires, its next expiration is computed from
 559  *  the current time and the cyclic interval. But there are situations when
 560  *  the next expiration needs to be reprogrammed by the kernel subsystem that
 561  *  is using the cyclic. cyclic_reprogram() allows this to be done. This,
 562  *  unlike the other kernel at-large cyclic API functions, is permitted to
 563  *  be called from the cyclic handler. This is because it does not use the
 564  *  cpu_lock to serialize access.
 565  *
 566  *  When cyclic_reprogram() is called for an omni-cyclic, the operation is
 567  *  applied to the omni-cyclic's component on the current CPU.
 568  *
 569  *  If a high-level cyclic handler reprograms its own cyclic, then
 570  *  cyclic_fire() detects that and does not recompute the cyclic's next
 571  *  expiration. However, for a lock-level or a low-level cyclic, the
 572  *  actual cyclic handler will execute at the lower PIL only after
 573  *  cyclic_fire() is done with all expired cyclics. To deal with this, such
 574  *  cyclics can be specified with a special interval of CY_INFINITY (INT64_MAX).
 575  *  cyclic_fire() recognizes this special value and recomputes the next
 576  *  expiration to CY_INFINITY. This effectively moves the cyclic to the
 577  *  bottom of the heap and prevents it from going off until its handler has
 578  *  had a chance to reprogram it. Infact, this is the way to create and reuse
 579  *  "one-shot" timers in the context of the cyclic subsystem without using
 580  *  cyclic_remove().
 581  *
 582  *  Here is the procedure for cyclic reprogramming:
 583  *
 584  *    1.  cyclic_reprogram() calls cyclic_reprogram_xcall() on the CPU
 585  *        that houses the cyclic.
 586  *    2.  cyclic_reprogram_xcall() raises interrupt level to CY_HIGH_LEVEL
 587  *    3.  The cyclic is located in the cyclic heap. The search for this is
 588  *        done from the bottom of the heap to the top as reprogrammable cyclics
 589  *        would be located closer to the bottom than the top.
 590  *    4.  The cyclic expiration is set and the cyclic is moved to its
 591  *        correct position in the heap (up or down depending on whether the
 592  *        new expiration is less than or greater than the old one).
 593  *    5.  If the cyclic move modified the root of the heap, the backend is
 594  *        reprogrammed.
 595  *
 596  *  Reprogramming can be a frequent event (see the callout subsystem). So,
 597  *  the serialization used has to be efficient. As with all other cyclic
 598  *  operations, the interrupt level is raised during reprogramming. Plus,
 599  *  during reprogramming, the cyclic must not be juggled (regular cyclic)
 600  *  or stopped (omni-cyclic). The implementation defines a per-cyclic
 601  *  reader-writer lock to accomplish this. This lock is acquired in the
 602  *  reader mode by cyclic_reprogram() and writer mode by cyclic_juggle() and
 603  *  cyclic_omni_stop(). The reader-writer lock makes it efficient if
 604  *  an omni-cyclic is reprogrammed on different CPUs frequently.
 605  *
 606  *  Note that since the cpu_lock is not used during reprogramming, it is
 607  *  the responsibility of the user of the reprogrammable cyclic to make sure
 608  *  that the cyclic is not removed via cyclic_remove() during reprogramming.
 609  *  This is not an unreasonable requirement as the user will typically have
 610  *  some sort of synchronization for its cyclic-related activities. This
 611  *  little caveat exists because the cyclic ID is not really an ID. It is
 612  *  implemented as a pointer to a structure.
 613  */
 614 #include <sys/cyclic_impl.h>
 615 #include <sys/sysmacros.h>
 616 #include <sys/systm.h>
 617 #include <sys/atomic.h>
 618 #include <sys/kmem.h>
 619 #include <sys/cmn_err.h>
 620 #include <sys/ddi.h>
 621 #include <sys/sdt.h>
 622 
 623 #ifdef CYCLIC_TRACE
 624 
 625 /*
 626  * cyc_trace_enabled is for the benefit of kernel debuggers.
 627  */
 628 int cyc_trace_enabled = 1;
 629 static cyc_tracebuf_t cyc_ptrace;
 630 static cyc_coverage_t cyc_coverage[CY_NCOVERAGE];
 631 
 632 /*
 633  * Seen this anywhere?
 634  */
 635 static uint_t
 636 cyclic_coverage_hash(char *p)
 637 {
 638         unsigned int g;
 639         uint_t hval;
 640 
 641         hval = 0;
 642         while (*p) {
 643                 hval = (hval << 4) + *p++;
 644                 if ((g = (hval & 0xf0000000)) != 0)
 645                         hval ^= g >> 24;
 646                 hval &= ~g;
 647         }
 648         return (hval);
 649 }
 650 
 651 static void
 652 cyclic_coverage(char *why, int level, uint64_t arg0, uint64_t arg1)
 653 {
 654         uint_t ndx, orig;
 655 
 656         for (ndx = orig = cyclic_coverage_hash(why) % CY_NCOVERAGE; ; ) {
 657                 if (cyc_coverage[ndx].cyv_why == why)
 658                         break;
 659 
 660                 if (cyc_coverage[ndx].cyv_why != NULL ||
 661                     casptr(&cyc_coverage[ndx].cyv_why, NULL, why) != NULL) {
 662 
 663                         if (++ndx == CY_NCOVERAGE)
 664                                 ndx = 0;
 665 
 666                         if (ndx == orig)
 667                                 panic("too many cyclic coverage points");
 668                         continue;
 669                 }
 670 
 671                 /*
 672                  * If we're here, we have successfully swung our guy into
 673                  * the position at "ndx".
 674                  */
 675                 break;
 676         }
 677 
 678         if (level == CY_PASSIVE_LEVEL)
 679                 cyc_coverage[ndx].cyv_passive_count++;
 680         else
 681                 cyc_coverage[ndx].cyv_count[level]++;
 682 
 683         cyc_coverage[ndx].cyv_arg0 = arg0;
 684         cyc_coverage[ndx].cyv_arg1 = arg1;
 685 }
 686 
 687 #define CYC_TRACE(cpu, level, why, arg0, arg1) \
 688         CYC_TRACE_IMPL(&cpu->cyp_trace[level], level, why, arg0, arg1)
 689 
 690 #define CYC_PTRACE(why, arg0, arg1) \
 691         CYC_TRACE_IMPL(&cyc_ptrace, CY_PASSIVE_LEVEL, why, arg0, arg1)
 692 
 693 #define CYC_TRACE_IMPL(buf, level, why, a0, a1) { \
 694         if (panicstr == NULL) { \
 695                 int _ndx = (buf)->cyt_ndx; \
 696                 cyc_tracerec_t *_rec = &(buf)->cyt_buf[_ndx]; \
 697                 (buf)->cyt_ndx = (++_ndx == CY_NTRACEREC) ? 0 : _ndx; \
 698                 _rec->cyt_tstamp = gethrtime_unscaled(); \
 699                 _rec->cyt_why = (why); \
 700                 _rec->cyt_arg0 = (uint64_t)(uintptr_t)(a0); \
 701                 _rec->cyt_arg1 = (uint64_t)(uintptr_t)(a1); \
 702                 cyclic_coverage(why, level,     \
 703                     (uint64_t)(uintptr_t)(a0), (uint64_t)(uintptr_t)(a1)); \
 704         } \
 705 }
 706 
 707 #else
 708 
 709 static int cyc_trace_enabled = 0;
 710 
 711 #define CYC_TRACE(cpu, level, why, arg0, arg1)
 712 #define CYC_PTRACE(why, arg0, arg1)
 713 
 714 #endif
 715 
 716 #define CYC_TRACE0(cpu, level, why) CYC_TRACE(cpu, level, why, 0, 0)
 717 #define CYC_TRACE1(cpu, level, why, arg0) CYC_TRACE(cpu, level, why, arg0, 0)
 718 
 719 #define CYC_PTRACE0(why) CYC_PTRACE(why, 0, 0)
 720 #define CYC_PTRACE1(why, arg0) CYC_PTRACE(why, arg0, 0)
 721 
 722 static kmem_cache_t *cyclic_id_cache;
 723 static cyc_id_t *cyclic_id_head;
 724 static hrtime_t cyclic_resolution;
 725 static cyc_backend_t cyclic_backend;
 726 
 727 /*
 728  * Returns 1 if the upheap propagated to the root, 0 if it did not.  This
 729  * allows the caller to reprogram the backend only when the root has been
 730  * modified.
 731  */
 732 static int
 733 cyclic_upheap(cyc_cpu_t *cpu, cyc_index_t ndx)
 734 {
 735         cyclic_t *cyclics;
 736         cyc_index_t *heap;
 737         cyc_index_t heap_parent, heap_current = ndx;
 738         cyc_index_t parent, current;
 739 
 740         if (heap_current == 0)
 741                 return (1);
 742 
 743         heap = cpu->cyp_heap;
 744         cyclics = cpu->cyp_cyclics;
 745         heap_parent = CYC_HEAP_PARENT(heap_current);
 746 
 747         for (;;) {
 748                 current = heap[heap_current];
 749                 parent = heap[heap_parent];
 750 
 751                 /*
 752                  * We have an expiration time later than our parent; we're
 753                  * done.
 754                  */
 755                 if (cyclics[current].cy_expire >= cyclics[parent].cy_expire)
 756                         return (0);
 757 
 758                 /*
 759                  * We need to swap with our parent, and continue up the heap.
 760                  */
 761                 heap[heap_parent] = current;
 762                 heap[heap_current] = parent;
 763 
 764                 /*
 765                  * If we just reached the root, we're done.
 766                  */
 767                 if (heap_parent == 0)
 768                         return (1);
 769 
 770                 heap_current = heap_parent;
 771                 heap_parent = CYC_HEAP_PARENT(heap_current);
 772         }
 773 }
 774 
 775 static void
 776 cyclic_downheap(cyc_cpu_t *cpu, cyc_index_t ndx)
 777 {
 778         cyclic_t *cyclics = cpu->cyp_cyclics;
 779         cyc_index_t *heap = cpu->cyp_heap;
 780 
 781         cyc_index_t heap_left, heap_right, heap_me = ndx;
 782         cyc_index_t left, right, me;
 783         cyc_index_t nelems = cpu->cyp_nelems;
 784 
 785         for (;;) {
 786                 /*
 787                  * If we don't have a left child (i.e., we're a leaf), we're
 788                  * done.
 789                  */
 790                 if ((heap_left = CYC_HEAP_LEFT(heap_me)) >= nelems)
 791                         return;
 792 
 793                 left = heap[heap_left];
 794                 me = heap[heap_me];
 795 
 796                 heap_right = CYC_HEAP_RIGHT(heap_me);
 797 
 798                 /*
 799                  * Even if we don't have a right child, we still need to compare
 800                  * our expiration time against that of our left child.
 801                  */
 802                 if (heap_right >= nelems)
 803                         goto comp_left;
 804 
 805                 right = heap[heap_right];
 806 
 807                 /*
 808                  * We have both a left and a right child.  We need to compare
 809                  * the expiration times of the children to determine which
 810                  * expires earlier.
 811                  */
 812                 if (cyclics[right].cy_expire < cyclics[left].cy_expire) {
 813                         /*
 814                          * Our right child is the earlier of our children.
 815                          * We'll now compare our expiration time to its; if
 816                          * ours is the earlier, we're done.
 817                          */
 818                         if (cyclics[me].cy_expire <= cyclics[right].cy_expire)
 819                                 return;
 820 
 821                         /*
 822                          * Our right child expires earlier than we do; swap
 823                          * with our right child, and descend right.
 824                          */
 825                         heap[heap_right] = me;
 826                         heap[heap_me] = right;
 827                         heap_me = heap_right;
 828                         continue;
 829                 }
 830 
 831 comp_left:
 832                 /*
 833                  * Our left child is the earlier of our children (or we have
 834                  * no right child).  We'll now compare our expiration time
 835                  * to its; if ours is the earlier, we're done.
 836                  */
 837                 if (cyclics[me].cy_expire <= cyclics[left].cy_expire)
 838                         return;
 839 
 840                 /*
 841                  * Our left child expires earlier than we do; swap with our
 842                  * left child, and descend left.
 843                  */
 844                 heap[heap_left] = me;
 845                 heap[heap_me] = left;
 846                 heap_me = heap_left;
 847         }
 848 }
 849 
 850 static void
 851 cyclic_expire(cyc_cpu_t *cpu, cyc_index_t ndx, cyclic_t *cyclic)
 852 {
 853         cyc_backend_t *be = cpu->cyp_backend;
 854         cyc_level_t level = cyclic->cy_level;
 855 
 856         /*
 857          * If this is a CY_HIGH_LEVEL cyclic, just call the handler; we don't
 858          * need to worry about the pend count for CY_HIGH_LEVEL cyclics.
 859          */
 860         if (level == CY_HIGH_LEVEL) {
 861                 cyc_func_t handler = cyclic->cy_handler;
 862                 void *arg = cyclic->cy_arg;
 863 
 864                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "handler-in", handler, arg);
 865                 DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);
 866 
 867                 (*handler)(arg);
 868 
 869                 DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
 870                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "handler-out", handler, arg);
 871 
 872                 return;
 873         }
 874 
 875         /*
 876          * We're at CY_HIGH_LEVEL; this modification to cy_pend need not
 877          * be atomic (the high interrupt level assures that it will appear
 878          * atomic to any softint currently running).
 879          */
 880         if (cyclic->cy_pend++ == 0) {
 881                 cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[level];
 882                 cyc_pcbuffer_t *pc = &softbuf->cys_buf[softbuf->cys_hard];
 883 
 884                 /*
 885                  * We need to enqueue this cyclic in the soft buffer.
 886                  */
 887                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "expire-enq", cyclic,
 888                     pc->cypc_prodndx);
 889                 pc->cypc_buf[pc->cypc_prodndx++ & pc->cypc_sizemask] = ndx;
 890 
 891                 ASSERT(pc->cypc_prodndx != pc->cypc_consndx);
 892         } else {
 893                 /*
 894                  * If the pend count is zero after we incremented it, then
 895                  * we've wrapped (i.e. we had a cy_pend count of over four
 896                  * billion.  In this case, we clamp the pend count at
 897                  * UINT32_MAX.  Yes, cyclics can be lost in this case.
 898                  */
 899                 if (cyclic->cy_pend == 0) {
 900                         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "expire-wrap", cyclic);
 901                         cyclic->cy_pend = UINT32_MAX;
 902                 }
 903 
 904                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "expire-bump", cyclic, 0);
 905         }
 906 
 907         be->cyb_softint(be->cyb_arg, cyclic->cy_level);
 908 }
 909 
 910 /*
 911  *  cyclic_fire(cpu_t *)
 912  *
 913  *  Overview
 914  *
 915  *    cyclic_fire() is the cyclic subsystem's CY_HIGH_LEVEL interrupt handler.
 916  *    Called by the cyclic backend.
 917  *
 918  *  Arguments and notes
 919  *
 920  *    The only argument is the CPU on which the interrupt is executing;
 921  *    backends must call into cyclic_fire() on the specified CPU.
 922  *
 923  *    cyclic_fire() may be called spuriously without ill effect.  Optimal
 924  *    backends will call into cyclic_fire() at or shortly after the time
 925  *    requested via cyb_reprogram().  However, calling cyclic_fire()
 926  *    arbitrarily late will only manifest latency bubbles; the correctness
 927  *    of the cyclic subsystem does not rely on the timeliness of the backend.
 928  *
 929  *    cyclic_fire() is wait-free; it will not block or spin.
 930  *
 931  *  Return values
 932  *
 933  *    None.
 934  *
 935  *  Caller's context
 936  *
 937  *    cyclic_fire() must be called from CY_HIGH_LEVEL interrupt context.
 938  */
 939 void
 940 cyclic_fire(cpu_t *c)
 941 {
 942         cyc_cpu_t *cpu = c->cpu_cyclic;
 943         cyc_backend_t *be = cpu->cyp_backend;
 944         cyc_index_t *heap = cpu->cyp_heap;
 945         cyclic_t *cyclic, *cyclics = cpu->cyp_cyclics;
 946         void *arg = be->cyb_arg;
 947         hrtime_t now = gethrtime();
 948         hrtime_t exp;
 949 
 950         CYC_TRACE(cpu, CY_HIGH_LEVEL, "fire", now, 0);
 951 
 952         if (cpu->cyp_nelems == 0) {
 953                 /*
 954                  * This is a spurious fire.  Count it as such, and blow
 955                  * out of here.
 956                  */
 957                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "fire-spurious");
 958                 return;
 959         }
 960 
 961         for (;;) {
 962                 cyc_index_t ndx = heap[0];
 963 
 964                 cyclic = &cyclics[ndx];
 965 
 966                 ASSERT(!(cyclic->cy_flags & CYF_FREE));
 967 
 968                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "fire-check", cyclic,
 969                     cyclic->cy_expire);
 970 
 971                 if ((exp = cyclic->cy_expire) > now)
 972                         break;
 973 
 974                 cyclic_expire(cpu, ndx, cyclic);
 975 
 976                 /*
 977                  * If the handler reprogrammed the cyclic, then don't
 978                  * recompute the expiration. Then, if the interval is
 979                  * infinity, set the expiration to infinity. This can
 980                  * be used to create one-shot timers.
 981                  */
 982                 if (exp != cyclic->cy_expire) {
 983                         /*
 984                          * If a hi level cyclic reprograms itself,
 985                          * the heap adjustment and reprogramming of the
 986                          * clock source have already been done at this
 987                          * point. So, we can continue.
 988                          */
 989                         continue;
 990                 }
 991 
 992                 if (cyclic->cy_interval == CY_INFINITY)
 993                         exp = CY_INFINITY;
 994                 else
 995                         exp += cyclic->cy_interval;
 996 
 997                 /*
 998                  * If this cyclic will be set to next expire in the distant
 999                  * past, we have one of two situations:
1000                  *
1001                  *   a) This is the first firing of a cyclic which had
1002                  *      cy_expire set to 0.
1003                  *
1004                  *   b) We are tragically late for a cyclic -- most likely
1005                  *      due to being in the debugger.
1006                  *
1007                  * In either case, we set the new expiration time to be the
1008                  * the next interval boundary.  This assures that the
1009                  * expiration time modulo the interval is invariant.
1010                  *
1011                  * We arbitrarily define "distant" to be one second (one second
1012                  * is chosen because it's shorter than any foray to the
1013                  * debugger while still being longer than any legitimate
1014                  * stretch at CY_HIGH_LEVEL).
1015                  */
1016 
1017                 if (now - exp > NANOSEC) {
1018                         hrtime_t interval = cyclic->cy_interval;
1019 
1020                         CYC_TRACE(cpu, CY_HIGH_LEVEL, exp == interval ?
1021                             "fire-first" : "fire-swing", now, exp);
1022 
1023                         exp += ((now - exp) / interval + 1) * interval;
1024                 }
1025 
1026                 cyclic->cy_expire = exp;
1027                 cyclic_downheap(cpu, 0);
1028         }
1029 
1030         /*
1031          * Now we have a cyclic in the root slot which isn't in the past;
1032          * reprogram the interrupt source.
1033          */
1034         be->cyb_reprogram(arg, exp);
1035 }
1036 
1037 static void
1038 cyclic_remove_pend(cyc_cpu_t *cpu, cyc_level_t level, cyclic_t *cyclic)
1039 {
1040         cyc_func_t handler = cyclic->cy_handler;
1041         void *arg = cyclic->cy_arg;
1042         uint32_t i, rpend = cpu->cyp_rpend - 1;
1043 
1044         ASSERT(cyclic->cy_flags & CYF_FREE);
1045         ASSERT(cyclic->cy_pend == 0);
1046         ASSERT(cpu->cyp_state == CYS_REMOVING);
1047         ASSERT(cpu->cyp_rpend > 0);
1048 
1049         CYC_TRACE(cpu, level, "remove-rpend", cyclic, cpu->cyp_rpend);
1050 
1051         /*
1052          * Note that we only call the handler cyp_rpend - 1 times; this is
1053          * to account for the handler call in cyclic_softint().
1054          */
1055         for (i = 0; i < rpend; i++) {
1056                 CYC_TRACE(cpu, level, "rpend-in", handler, arg);
1057                 DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);
1058 
1059                 (*handler)(arg);
1060 
1061                 DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
1062                 CYC_TRACE(cpu, level, "rpend-out", handler, arg);
1063         }
1064 
1065         /*
1066          * We can now let the remove operation complete.
1067          */
1068         sema_v(&cpu->cyp_modify_wait);
1069 }
1070 
1071 /*
1072  *  cyclic_softint(cpu_t *cpu, cyc_level_t level)
1073  *
1074  *  Overview
1075  *
1076  *    cyclic_softint() is the cyclic subsystem's CY_LOCK_LEVEL and CY_LOW_LEVEL
1077  *    soft interrupt handler.  Called by the cyclic backend.
1078  *
1079  *  Arguments and notes
1080  *
1081  *    The first argument to cyclic_softint() is the CPU on which the interrupt
1082  *    is executing; backends must call into cyclic_softint() on the specified
1083  *    CPU.  The second argument is the level of the soft interrupt; it must
1084  *    be one of CY_LOCK_LEVEL or CY_LOW_LEVEL.
1085  *
1086  *    cyclic_softint() will call the handlers for cyclics pending at the
1087  *    specified level.  cyclic_softint() will not return until all pending
1088  *    cyclics at the specified level have been dealt with; intervening
1089  *    CY_HIGH_LEVEL interrupts which enqueue cyclics at the specified level
1090  *    may therefore prolong cyclic_softint().
1091  *
1092  *    cyclic_softint() never disables interrupts, and, if neither a
1093  *    cyclic_add() nor a cyclic_remove() is pending on the specified CPU, is
1094  *    lock-free.  This assures that in the common case, cyclic_softint()
1095  *    completes without blocking, and never starves cyclic_fire().  If either
1096  *    cyclic_add() or cyclic_remove() is pending, cyclic_softint() may grab
1097  *    a dispatcher lock.
1098  *
1099  *    While cyclic_softint() is designed for bounded latency, it is obviously
1100  *    at the mercy of its cyclic handlers.  Because cyclic handlers may block
1101  *    arbitrarily, callers of cyclic_softint() should not rely upon
1102  *    deterministic completion.
1103  *
1104  *    cyclic_softint() may be called spuriously without ill effect.
1105  *
1106  *  Return value
1107  *
1108  *    None.
1109  *
1110  *  Caller's context
1111  *
1112  *    The caller must be executing in soft interrupt context at either
1113  *    CY_LOCK_LEVEL or CY_LOW_LEVEL.  The level passed to cyclic_softint()
1114  *    must match the level at which it is executing.  On optimal backends,
1115  *    the caller will hold no locks.  In any case, the caller may not hold
1116  *    cpu_lock or any lock acquired by any cyclic handler or held across
1117  *    any of cyclic_add(), cyclic_remove(), cyclic_bind() or cyclic_juggle().
1118  */
1119 void
1120 cyclic_softint(cpu_t *c, cyc_level_t level)
1121 {
1122         cyc_cpu_t *cpu = c->cpu_cyclic;
1123         cyc_softbuf_t *softbuf;
1124         int soft, *buf, consndx, resized = 0, intr_resized = 0;
1125         cyc_pcbuffer_t *pc;
1126         cyclic_t *cyclics = cpu->cyp_cyclics;
1127         int sizemask;
1128 
1129         CYC_TRACE(cpu, level, "softint", cyclics, 0);
1130 
1131         ASSERT(level < CY_LOW_LEVEL + CY_SOFT_LEVELS);
1132 
1133         softbuf = &cpu->cyp_softbuf[level];
1134 top:
1135         soft = softbuf->cys_soft;
1136         ASSERT(soft == 0 || soft == 1);
1137 
1138         pc = &softbuf->cys_buf[soft];
1139         buf = pc->cypc_buf;
1140         consndx = pc->cypc_consndx;
1141         sizemask = pc->cypc_sizemask;
1142 
1143         CYC_TRACE(cpu, level, "softint-top", cyclics, pc);
1144 
1145         while (consndx != pc->cypc_prodndx) {
1146                 uint32_t pend, npend, opend;
1147                 int consmasked = consndx & sizemask;
1148                 cyclic_t *cyclic = &cyclics[buf[consmasked]];
1149                 cyc_func_t handler = cyclic->cy_handler;
1150                 void *arg = cyclic->cy_arg;
1151 
1152                 ASSERT(buf[consmasked] < cpu->cyp_size);
1153                 CYC_TRACE(cpu, level, "consuming", consndx, cyclic);
1154 
1155                 /*
1156                  * We have found this cyclic in the pcbuffer.  We know that
1157                  * one of the following is true:
1158                  *
1159                  *  (a) The pend is non-zero.  We need to execute the handler
1160                  *      at least once.
1161                  *
1162                  *  (b) The pend _was_ non-zero, but it's now zero due to a
1163                  *      resize.  We will call the handler once, see that we
1164                  *      are in this case, and read the new cyclics buffer
1165                  *      (and hence the old non-zero pend).
1166                  *
1167                  *  (c) The pend _was_ non-zero, but it's now zero due to a
1168                  *      removal.  We will call the handler once, see that we
1169                  *      are in this case, and call into cyclic_remove_pend()
1170                  *      to call the cyclic rpend times.  We will take into
1171                  *      account that we have already called the handler once.
1172                  *
1173                  * Point is:  it's safe to call the handler without first
1174                  * checking the pend.
1175                  */
1176                 do {
1177                         CYC_TRACE(cpu, level, "handler-in", handler, arg);
1178                         DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);
1179 
1180                         (*handler)(arg);
1181 
1182                         DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
1183                         CYC_TRACE(cpu, level, "handler-out", handler, arg);
1184 reread:
1185                         pend = cyclic->cy_pend;
1186                         npend = pend - 1;
1187 
1188                         if (pend == 0) {
1189                                 if (cpu->cyp_state == CYS_REMOVING) {
1190                                         /*
1191                                          * This cyclic has been removed while
1192                                          * it had a non-zero pend count (we
1193                                          * know it was non-zero because we
1194                                          * found this cyclic in the pcbuffer).
1195                                          * There must be a non-zero rpend for
1196                                          * this CPU, and there must be a remove
1197                                          * operation blocking; we'll call into
1198                                          * cyclic_remove_pend() to clean this
1199                                          * up, and break out of the pend loop.
1200                                          */
1201                                         cyclic_remove_pend(cpu, level, cyclic);
1202                                         break;
1203                                 }
1204 
1205                                 /*
1206                                  * We must have had a resize interrupt us.
1207                                  */
1208                                 CYC_TRACE(cpu, level, "resize-int", cyclics, 0);
1209                                 ASSERT(cpu->cyp_state == CYS_EXPANDING);
1210                                 ASSERT(cyclics != cpu->cyp_cyclics);
1211                                 ASSERT(resized == 0);
1212                                 ASSERT(intr_resized == 0);
1213                                 intr_resized = 1;
1214                                 cyclics = cpu->cyp_cyclics;
1215                                 cyclic = &cyclics[buf[consmasked]];
1216                                 ASSERT(cyclic->cy_handler == handler);
1217                                 ASSERT(cyclic->cy_arg == arg);
1218                                 goto reread;
1219                         }
1220 
1221                         if ((opend =
1222                             cas32(&cyclic->cy_pend, pend, npend)) != pend) {
1223                                 /*
1224                                  * Our cas32 can fail for one of several
1225                                  * reasons:
1226                                  *
1227                                  *  (a) An intervening high level bumped up the
1228                                  *      pend count on this cyclic.  In this
1229                                  *      case, we will see a higher pend.
1230                                  *
1231                                  *  (b) The cyclics array has been yanked out
1232                                  *      from underneath us by a resize
1233                                  *      operation.  In this case, pend is 0 and
1234                                  *      cyp_state is CYS_EXPANDING.
1235                                  *
1236                                  *  (c) The cyclic has been removed by an
1237                                  *      intervening remove-xcall.  In this case,
1238                                  *      pend will be 0, the cyp_state will be
1239                                  *      CYS_REMOVING, and the cyclic will be
1240                                  *      marked CYF_FREE.
1241                                  *
1242                                  * The assertion below checks that we are
1243                                  * in one of the above situations.  The
1244                                  * action under all three is to return to
1245                                  * the top of the loop.
1246                                  */
1247                                 CYC_TRACE(cpu, level, "cas-fail", opend, pend);
1248                                 ASSERT(opend > pend || (opend == 0 &&
1249                                     ((cyclics != cpu->cyp_cyclics &&
1250                                     cpu->cyp_state == CYS_EXPANDING) ||
1251                                     (cpu->cyp_state == CYS_REMOVING &&
1252                                     (cyclic->cy_flags & CYF_FREE)))));
1253                                 goto reread;
1254                         }
1255 
1256                         /*
1257                          * Okay, so we've managed to successfully decrement
1258                          * pend.  If we just decremented the pend to 0, we're
1259                          * done.
1260                          */
1261                 } while (npend > 0);
1262 
1263                 pc->cypc_consndx = ++consndx;
1264         }
1265 
1266         /*
1267          * If the high level handler is no longer writing to the same
1268          * buffer, then we've had a resize.  We need to switch our soft
1269          * index, and goto top.
1270          */
1271         if (soft != softbuf->cys_hard) {
1272                 /*
1273                  * We can assert that the other buffer has grown by exactly
1274                  * one factor of two.
1275                  */
1276                 CYC_TRACE(cpu, level, "buffer-grow", 0, 0);
1277                 ASSERT(cpu->cyp_state == CYS_EXPANDING);
1278                 ASSERT(softbuf->cys_buf[softbuf->cys_hard].cypc_sizemask ==
1279                     (softbuf->cys_buf[soft].cypc_sizemask << 1) + 1 ||
1280                     softbuf->cys_buf[soft].cypc_sizemask == 0);
1281                 ASSERT(softbuf->cys_hard == (softbuf->cys_soft ^ 1));
1282 
1283                 /*
1284                  * If our cached cyclics pointer doesn't match cyp_cyclics,
1285                  * then we took a resize between our last iteration of the
1286                  * pend loop and the check against softbuf->cys_hard.
1287                  */
1288                 if (cpu->cyp_cyclics != cyclics) {
1289                         CYC_TRACE1(cpu, level, "resize-int-int", consndx);
1290                         cyclics = cpu->cyp_cyclics;
1291                 }
1292 
1293                 softbuf->cys_soft = softbuf->cys_hard;
1294 
1295                 ASSERT(resized == 0);
1296                 resized = 1;
1297                 goto top;
1298         }
1299 
1300         /*
1301          * If we were interrupted by a resize operation, then we must have
1302          * seen the hard index change.
1303          */
1304         ASSERT(!(intr_resized == 1 && resized == 0));
1305 
1306         if (resized) {
1307                 uint32_t lev, nlev;
1308 
1309                 ASSERT(cpu->cyp_state == CYS_EXPANDING);
1310 
1311                 do {
1312                         lev = cpu->cyp_modify_levels;
1313                         nlev = lev + 1;
1314                 } while (cas32(&cpu->cyp_modify_levels, lev, nlev) != lev);
1315 
1316                 /*
1317                  * If we are the last soft level to see the modification,
1318                  * post on cyp_modify_wait.  Otherwise, (if we're not
1319                  * already at low level), post down to the next soft level.
1320                  */
1321                 if (nlev == CY_SOFT_LEVELS) {
1322                         CYC_TRACE0(cpu, level, "resize-kick");
1323                         sema_v(&cpu->cyp_modify_wait);
1324                 } else {
1325                         ASSERT(nlev < CY_SOFT_LEVELS);
1326                         if (level != CY_LOW_LEVEL) {
1327                                 cyc_backend_t *be = cpu->cyp_backend;
1328 
1329                                 CYC_TRACE0(cpu, level, "resize-post");
1330                                 be->cyb_softint(be->cyb_arg, level - 1);
1331                         }
1332                 }
1333         }
1334 }
1335 
1336 static void
1337 cyclic_expand_xcall(cyc_xcallarg_t *arg)
1338 {
1339         cyc_cpu_t *cpu = arg->cyx_cpu;
1340         cyc_backend_t *be = cpu->cyp_backend;
1341         cyb_arg_t bar = be->cyb_arg;
1342         cyc_cookie_t cookie;
1343         cyc_index_t new_size = arg->cyx_size, size = cpu->cyp_size, i;
1344         cyc_index_t *new_heap = arg->cyx_heap;
1345         cyclic_t *cyclics = cpu->cyp_cyclics, *new_cyclics = arg->cyx_cyclics;
1346 
1347         ASSERT(cpu->cyp_state == CYS_EXPANDING);
1348 
1349         /*
1350          * This is a little dicey.  First, we'll raise our interrupt level
1351          * to CY_HIGH_LEVEL.  This CPU already has a new heap, cyclic array,
1352          * etc.; we just need to bcopy them across.  As for the softint
1353          * buffers, we'll switch the active buffers.  The actual softints will
1354          * take care of consuming any pending cyclics in the old buffer.
1355          */
1356         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
1357 
1358         CYC_TRACE(cpu, CY_HIGH_LEVEL, "expand", new_size, 0);
1359 
1360         /*
1361          * Assert that the new size is a power of 2.
1362          */
1363         ASSERT((new_size & new_size - 1) == 0);
1364         ASSERT(new_size == (size << 1));
1365         ASSERT(cpu->cyp_heap != NULL && cpu->cyp_cyclics != NULL);
1366 
1367         bcopy(cpu->cyp_heap, new_heap, sizeof (cyc_index_t) * size);
1368         bcopy(cyclics, new_cyclics, sizeof (cyclic_t) * size);
1369 
1370         /*
1371          * Now run through the old cyclics array, setting pend to 0.  To
1372          * softints (which are executing at a lower priority level), the
1373          * pends dropping to 0 will appear atomic with the cyp_cyclics
1374          * pointer changing.
1375          */
1376         for (i = 0; i < size; i++)
1377                 cyclics[i].cy_pend = 0;
1378 
1379         /*
1380          * Set up the free list, and set all of the new cyclics to be CYF_FREE.
1381          */
1382         for (i = size; i < new_size; i++) {
1383                 new_heap[i] = i;
1384                 new_cyclics[i].cy_flags = CYF_FREE;
1385         }
1386 
1387         /*
1388          * We can go ahead and plow the value of cyp_heap and cyp_cyclics;
1389          * cyclic_expand() has kept a copy.
1390          */
1391         cpu->cyp_heap = new_heap;
1392         cpu->cyp_cyclics = new_cyclics;
1393         cpu->cyp_size = new_size;
1394 
1395         /*
1396          * We've switched over the heap and the cyclics array.  Now we need
1397          * to switch over our active softint buffer pointers.
1398          */
1399         for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
1400                 cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
1401                 uchar_t hard = softbuf->cys_hard;
1402 
1403                 /*
1404                  * Assert that we're not in the middle of a resize operation.
1405                  */
1406                 ASSERT(hard == softbuf->cys_soft);
1407                 ASSERT(hard == 0 || hard == 1);
1408                 ASSERT(softbuf->cys_buf[hard].cypc_buf != NULL);
1409 
1410                 softbuf->cys_hard = hard ^ 1;
1411 
1412                 /*
1413                  * The caller (cyclic_expand()) is responsible for setting
1414                  * up the new producer-consumer buffer; assert that it's
1415                  * been done correctly.
1416                  */
1417                 ASSERT(softbuf->cys_buf[hard ^ 1].cypc_buf != NULL);
1418                 ASSERT(softbuf->cys_buf[hard ^ 1].cypc_prodndx == 0);
1419                 ASSERT(softbuf->cys_buf[hard ^ 1].cypc_consndx == 0);
1420         }
1421 
1422         /*
1423          * That's all there is to it; now we just need to postdown to
1424          * get the softint chain going.
1425          */
1426         be->cyb_softint(bar, CY_HIGH_LEVEL - 1);
1427         be->cyb_restore_level(bar, cookie);
1428 }
1429 
1430 /*
1431  * cyclic_expand() will cross call onto the CPU to perform the actual
1432  * expand operation.
1433  */
1434 static void
1435 cyclic_expand(cyc_cpu_t *cpu)
1436 {
1437         cyc_index_t new_size, old_size;
1438         cyc_index_t *new_heap, *old_heap;
1439         cyclic_t *new_cyclics, *old_cyclics;
1440         cyc_xcallarg_t arg;
1441         cyc_backend_t *be = cpu->cyp_backend;
1442         char old_hard;
1443         int i;
1444 
1445         ASSERT(MUTEX_HELD(&cpu_lock));
1446         ASSERT(cpu->cyp_state == CYS_ONLINE);
1447 
1448         cpu->cyp_state = CYS_EXPANDING;
1449 
1450         old_heap = cpu->cyp_heap;
1451         old_cyclics = cpu->cyp_cyclics;
1452 
1453         if ((new_size = ((old_size = cpu->cyp_size) << 1)) == 0) {
1454                 new_size = CY_DEFAULT_PERCPU;
1455                 ASSERT(old_heap == NULL && old_cyclics == NULL);
1456         }
1457 
1458         /*
1459          * Check that the new_size is a power of 2.
1460          */
1461         ASSERT((new_size - 1 & new_size) == 0);
1462 
1463         new_heap = kmem_alloc(sizeof (cyc_index_t) * new_size, KM_SLEEP);
1464         new_cyclics = kmem_zalloc(sizeof (cyclic_t) * new_size, KM_SLEEP);
1465 
1466         /*
1467          * We know that no other expansions are in progress (they serialize
1468          * on cpu_lock), so we can safely read the softbuf metadata.
1469          */
1470         old_hard = cpu->cyp_softbuf[0].cys_hard;
1471 
1472         for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
1473                 cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
1474                 char hard = softbuf->cys_hard;
1475                 cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard ^ 1];
1476 
1477                 ASSERT(hard == old_hard);
1478                 ASSERT(hard == softbuf->cys_soft);
1479                 ASSERT(pc->cypc_buf == NULL);
1480 
1481                 pc->cypc_buf =
1482                     kmem_alloc(sizeof (cyc_index_t) * new_size, KM_SLEEP);
1483                 pc->cypc_prodndx = pc->cypc_consndx = 0;
1484                 pc->cypc_sizemask = new_size - 1;
1485         }
1486 
1487         arg.cyx_cpu = cpu;
1488         arg.cyx_heap = new_heap;
1489         arg.cyx_cyclics = new_cyclics;
1490         arg.cyx_size = new_size;
1491 
1492         cpu->cyp_modify_levels = 0;
1493 
1494         be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
1495             (cyc_func_t)cyclic_expand_xcall, &arg);
1496 
1497         /*
1498          * Now block, waiting for the resize operation to complete.
1499          */
1500         sema_p(&cpu->cyp_modify_wait);
1501         ASSERT(cpu->cyp_modify_levels == CY_SOFT_LEVELS);
1502 
1503         /*
1504          * The operation is complete; we can now free the old buffers.
1505          */
1506         for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
1507                 cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
1508                 char hard = softbuf->cys_hard;
1509                 cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard ^ 1];
1510 
1511                 ASSERT(hard == (old_hard ^ 1));
1512                 ASSERT(hard == softbuf->cys_soft);
1513 
1514                 if (pc->cypc_buf == NULL)
1515                         continue;
1516 
1517                 ASSERT(pc->cypc_sizemask == ((new_size - 1) >> 1));
1518 
1519                 kmem_free(pc->cypc_buf,
1520                     sizeof (cyc_index_t) * (pc->cypc_sizemask + 1));
1521                 pc->cypc_buf = NULL;
1522         }
1523 
1524         if (old_cyclics != NULL) {
1525                 ASSERT(old_heap != NULL);
1526                 ASSERT(old_size != 0);
1527                 kmem_free(old_cyclics, sizeof (cyclic_t) * old_size);
1528                 kmem_free(old_heap, sizeof (cyc_index_t) * old_size);
1529         }
1530 
1531         ASSERT(cpu->cyp_state == CYS_EXPANDING);
1532         cpu->cyp_state = CYS_ONLINE;
1533 }
1534 
1535 /*
1536  * cyclic_pick_cpu will attempt to pick a CPU according to the constraints
1537  * specified by the partition, bound CPU, and flags.  Additionally,
1538  * cyclic_pick_cpu() will not pick the avoid CPU; it will return NULL if
1539  * the avoid CPU is the only CPU which satisfies the constraints.
1540  *
1541  * If CYF_CPU_BOUND is set in flags, the specified CPU must be non-NULL.
1542  * If CYF_PART_BOUND is set in flags, the specified partition must be non-NULL.
1543  * If both CYF_CPU_BOUND and CYF_PART_BOUND are set, the specified CPU must
1544  * be in the specified partition.
1545  */
1546 static cyc_cpu_t *
1547 cyclic_pick_cpu(cpupart_t *part, cpu_t *bound, cpu_t *avoid, uint16_t flags)
1548 {
1549         cpu_t *c, *start = (part != NULL) ? part->cp_cpulist : CPU;
1550         cpu_t *online = NULL;
1551         uintptr_t offset;
1552 
1553         CYC_PTRACE("pick-cpu", part, bound);
1554 
1555         ASSERT(!(flags & CYF_CPU_BOUND) || bound != NULL);
1556         ASSERT(!(flags & CYF_PART_BOUND) || part != NULL);
1557 
1558         /*
1559          * If we're bound to our CPU, there isn't much choice involved.  We
1560          * need to check that the CPU passed as bound is in the cpupart, and
1561          * that the CPU that we're binding to has been configured.
1562          */
1563         if (flags & CYF_CPU_BOUND) {
1564                 CYC_PTRACE("pick-cpu-bound", bound, avoid);
1565 
1566                 if ((flags & CYF_PART_BOUND) && bound->cpu_part != part)
1567                         panic("cyclic_pick_cpu:  "
1568                             "CPU binding contradicts partition binding");
1569 
1570                 if (bound == avoid)
1571                         return (NULL);
1572 
1573                 if (bound->cpu_cyclic == NULL)
1574                         panic("cyclic_pick_cpu:  "
1575                             "attempt to bind to non-configured CPU");
1576 
1577                 return (bound->cpu_cyclic);
1578         }
1579 
1580         if (flags & CYF_PART_BOUND) {
1581                 CYC_PTRACE("pick-part-bound", bound, avoid);
1582                 offset = offsetof(cpu_t, cpu_next_part);
1583         } else {
1584                 offset = offsetof(cpu_t, cpu_next_onln);
1585         }
1586 
1587         c = start;
1588         do {
1589                 if (c->cpu_cyclic == NULL)
1590                         continue;
1591 
1592                 if (c->cpu_cyclic->cyp_state == CYS_OFFLINE)
1593                         continue;
1594 
1595                 if (c == avoid)
1596                         continue;
1597 
1598                 if (c->cpu_flags & CPU_ENABLE)
1599                         goto found;
1600 
1601                 if (online == NULL)
1602                         online = c;
1603         } while ((c = *(cpu_t **)((uintptr_t)c + offset)) != start);
1604 
1605         /*
1606          * If we're here, we're in one of two situations:
1607          *
1608          *  (a) We have a partition-bound cyclic, and there is no CPU in
1609          *      our partition which is CPU_ENABLE'd.  If we saw another
1610          *      non-CYS_OFFLINE CPU in our partition, we'll go with it.
1611          *      If not, the avoid CPU must be the only non-CYS_OFFLINE
1612          *      CPU in the partition; we're forced to return NULL.
1613          *
1614          *  (b) We have a partition-unbound cyclic, in which case there
1615          *      must only be one CPU CPU_ENABLE'd, and it must be the one
1616          *      we're trying to avoid.  If cyclic_juggle()/cyclic_offline()
1617          *      are called appropriately, this generally shouldn't happen
1618          *      (the offline should fail before getting to this code).
1619          *      At any rate: we can't avoid the avoid CPU, so we return
1620          *      NULL.
1621          */
1622         if (!(flags & CYF_PART_BOUND)) {
1623                 ASSERT(avoid->cpu_flags & CPU_ENABLE);
1624                 return (NULL);
1625         }
1626 
1627         CYC_PTRACE("pick-no-intr", part, avoid);
1628 
1629         if ((c = online) != NULL)
1630                 goto found;
1631 
1632         CYC_PTRACE("pick-fail", part, avoid);
1633         ASSERT(avoid->cpu_part == start->cpu_part);
1634         return (NULL);
1635 
1636 found:
1637         CYC_PTRACE("pick-cpu-found", c, avoid);
1638         ASSERT(c != avoid);
1639         ASSERT(c->cpu_cyclic != NULL);
1640 
1641         return (c->cpu_cyclic);
1642 }
1643 
1644 static void
1645 cyclic_add_xcall(cyc_xcallarg_t *arg)
1646 {
1647         cyc_cpu_t *cpu = arg->cyx_cpu;
1648         cyc_handler_t *hdlr = arg->cyx_hdlr;
1649         cyc_time_t *when = arg->cyx_when;
1650         cyc_backend_t *be = cpu->cyp_backend;
1651         cyc_index_t ndx, nelems;
1652         cyc_cookie_t cookie;
1653         cyb_arg_t bar = be->cyb_arg;
1654         cyclic_t *cyclic;
1655 
1656         ASSERT(cpu->cyp_nelems < cpu->cyp_size);
1657 
1658         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
1659 
1660         CYC_TRACE(cpu, CY_HIGH_LEVEL,
1661             "add-xcall", when->cyt_when, when->cyt_interval);
1662 
1663         nelems = cpu->cyp_nelems++;
1664 
1665         if (nelems == 0) {
1666                 /*
1667                  * If this is the first element, we need to enable the
1668                  * backend on this CPU.
1669                  */
1670                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "enabled");
1671                 be->cyb_enable(bar);
1672         }
1673 
1674         ndx = cpu->cyp_heap[nelems];
1675         cyclic = &cpu->cyp_cyclics[ndx];
1676 
1677         ASSERT(cyclic->cy_flags == CYF_FREE);
1678         cyclic->cy_interval = when->cyt_interval;
1679 
1680         if (when->cyt_when == 0) {
1681                 /*
1682                  * If a start time hasn't been explicitly specified, we'll
1683                  * start on the next interval boundary.
1684                  */
1685                 cyclic->cy_expire = (gethrtime() / cyclic->cy_interval + 1) *
1686                     cyclic->cy_interval;
1687         } else {
1688                 cyclic->cy_expire = when->cyt_when;
1689         }
1690 
1691         cyclic->cy_handler = hdlr->cyh_func;
1692         cyclic->cy_arg = hdlr->cyh_arg;
1693         cyclic->cy_level = hdlr->cyh_level;
1694         cyclic->cy_flags = arg->cyx_flags;
1695 
1696         if (cyclic_upheap(cpu, nelems)) {
1697                 hrtime_t exp = cyclic->cy_expire;
1698 
1699                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "add-reprog", cyclic, exp);
1700 
1701                 /*
1702                  * If our upheap propagated to the root, we need to
1703                  * reprogram the interrupt source.
1704                  */
1705                 be->cyb_reprogram(bar, exp);
1706         }
1707         be->cyb_restore_level(bar, cookie);
1708 
1709         arg->cyx_ndx = ndx;
1710 }
1711 
1712 static cyc_index_t
1713 cyclic_add_here(cyc_cpu_t *cpu, cyc_handler_t *hdlr,
1714     cyc_time_t *when, uint16_t flags)
1715 {
1716         cyc_backend_t *be = cpu->cyp_backend;
1717         cyb_arg_t bar = be->cyb_arg;
1718         cyc_xcallarg_t arg;
1719 
1720         CYC_PTRACE("add-cpu", cpu, hdlr->cyh_func);
1721         ASSERT(MUTEX_HELD(&cpu_lock));
1722         ASSERT(cpu->cyp_state == CYS_ONLINE);
1723         ASSERT(!(cpu->cyp_cpu->cpu_flags & CPU_OFFLINE));
1724         ASSERT(when->cyt_when >= 0 && when->cyt_interval > 0);
1725 
1726         if (cpu->cyp_nelems == cpu->cyp_size) {
1727                 /*
1728                  * This is expensive; it will cross call onto the other
1729                  * CPU to perform the expansion.
1730                  */
1731                 cyclic_expand(cpu);
1732                 ASSERT(cpu->cyp_nelems < cpu->cyp_size);
1733         }
1734 
1735         /*
1736          * By now, we know that we're going to be able to successfully
1737          * perform the add.  Now cross call over to the CPU of interest to
1738          * actually add our cyclic.
1739          */
1740         arg.cyx_cpu = cpu;
1741         arg.cyx_hdlr = hdlr;
1742         arg.cyx_when = when;
1743         arg.cyx_flags = flags;
1744 
1745         be->cyb_xcall(bar, cpu->cyp_cpu, (cyc_func_t)cyclic_add_xcall, &arg);
1746 
1747         CYC_PTRACE("add-cpu-done", cpu, arg.cyx_ndx);
1748 
1749         return (arg.cyx_ndx);
1750 }
1751 
1752 static void
1753 cyclic_remove_xcall(cyc_xcallarg_t *arg)
1754 {
1755         cyc_cpu_t *cpu = arg->cyx_cpu;
1756         cyc_backend_t *be = cpu->cyp_backend;
1757         cyb_arg_t bar = be->cyb_arg;
1758         cyc_cookie_t cookie;
1759         cyc_index_t ndx = arg->cyx_ndx, nelems, i;
1760         cyc_index_t *heap, last;
1761         cyclic_t *cyclic;
1762 #ifdef DEBUG
1763         cyc_index_t root;
1764 #endif
1765 
1766         ASSERT(cpu->cyp_state == CYS_REMOVING);
1767 
1768         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
1769 
1770         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "remove-xcall", ndx);
1771 
1772         heap = cpu->cyp_heap;
1773         nelems = cpu->cyp_nelems;
1774         ASSERT(nelems > 0);
1775         cyclic = &cpu->cyp_cyclics[ndx];
1776 
1777         /*
1778          * Grab the current expiration time.  If this cyclic is being
1779          * removed as part of a juggling operation, the expiration time
1780          * will be used when the cyclic is added to the new CPU.
1781          */
1782         if (arg->cyx_when != NULL) {
1783                 arg->cyx_when->cyt_when = cyclic->cy_expire;
1784                 arg->cyx_when->cyt_interval = cyclic->cy_interval;
1785         }
1786 
1787         if (cyclic->cy_pend != 0) {
1788                 /*
1789                  * The pend is non-zero; this cyclic is currently being
1790                  * executed (or will be executed shortly).  If the caller
1791                  * refuses to wait, we must return (doing nothing).  Otherwise,
1792                  * we will stash the pend value * in this CPU's rpend, and
1793                  * then zero it out.  The softint in the pend loop will see
1794                  * that we have zeroed out pend, and will call the cyclic
1795                  * handler rpend times.  The caller will wait until the
1796                  * softint has completed calling the cyclic handler.
1797                  */
1798                 if (arg->cyx_wait == CY_NOWAIT) {
1799                         arg->cyx_wait = CY_WAIT;
1800                         goto out;
1801                 }
1802 
1803                 ASSERT(cyclic->cy_level != CY_HIGH_LEVEL);
1804                 CYC_TRACE1(cpu, CY_HIGH_LEVEL, "remove-pend", cyclic->cy_pend);
1805                 cpu->cyp_rpend = cyclic->cy_pend;
1806                 cyclic->cy_pend = 0;
1807         }
1808 
1809         /*
1810          * Now set the flags to CYF_FREE.  We don't need a membar_enter()
1811          * between zeroing pend and setting the flags because we're at
1812          * CY_HIGH_LEVEL (that is, the zeroing of pend and the setting
1813          * of cy_flags appear atomic to softints).
1814          */
1815         cyclic->cy_flags = CYF_FREE;
1816 
1817         for (i = 0; i < nelems; i++) {
1818                 if (heap[i] == ndx)
1819                         break;
1820         }
1821 
1822         if (i == nelems)
1823                 panic("attempt to remove non-existent cyclic");
1824 
1825         cpu->cyp_nelems = --nelems;
1826 
1827         if (nelems == 0) {
1828                 /*
1829                  * If we just removed the last element, then we need to
1830                  * disable the backend on this CPU.
1831                  */
1832                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "disabled");
1833                 be->cyb_disable(bar);
1834         }
1835 
1836         if (i == nelems) {
1837                 /*
1838                  * If we just removed the last element of the heap, then
1839                  * we don't have to downheap.
1840                  */
1841                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-bottom");
1842                 goto out;
1843         }
1844 
1845 #ifdef DEBUG
1846         root = heap[0];
1847 #endif
1848 
1849         /*
1850          * Swap the last element of the heap with the one we want to
1851          * remove, and downheap (this has the implicit effect of putting
1852          * the newly freed element on the free list).
1853          */
1854         heap[i] = (last = heap[nelems]);
1855         heap[nelems] = ndx;
1856 
1857         if (i == 0) {
1858                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-root");
1859                 cyclic_downheap(cpu, 0);
1860         } else {
1861                 if (cyclic_upheap(cpu, i) == 0) {
1862                         /*
1863                          * The upheap didn't propagate to the root; if it
1864                          * didn't propagate at all, we need to downheap.
1865                          */
1866                         CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-no-root");
1867                         if (heap[i] == last) {
1868                                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-no-up");
1869                                 cyclic_downheap(cpu, i);
1870                         }
1871                         ASSERT(heap[0] == root);
1872                         goto out;
1873                 }
1874         }
1875 
1876         /*
1877          * We're here because we changed the root; we need to reprogram
1878          * the clock source.
1879          */
1880         cyclic = &cpu->cyp_cyclics[heap[0]];
1881 
1882         CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-reprog");
1883 
1884         ASSERT(nelems != 0);
1885         be->cyb_reprogram(bar, cyclic->cy_expire);
1886 out:
1887         be->cyb_restore_level(bar, cookie);
1888 }
1889 
1890 static int
1891 cyclic_remove_here(cyc_cpu_t *cpu, cyc_index_t ndx, cyc_time_t *when, int wait)
1892 {
1893         cyc_backend_t *be = cpu->cyp_backend;
1894         cyc_xcallarg_t arg;
1895         cyclic_t *cyclic = &cpu->cyp_cyclics[ndx];
1896         cyc_level_t level = cyclic->cy_level;
1897 
1898         ASSERT(MUTEX_HELD(&cpu_lock));
1899         ASSERT(cpu->cyp_rpend == 0);
1900         ASSERT(wait == CY_WAIT || wait == CY_NOWAIT);
1901 
1902         arg.cyx_ndx = ndx;
1903         arg.cyx_cpu = cpu;
1904         arg.cyx_when = when;
1905         arg.cyx_wait = wait;
1906 
1907         ASSERT(cpu->cyp_state == CYS_ONLINE);
1908         cpu->cyp_state = CYS_REMOVING;
1909 
1910         be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
1911             (cyc_func_t)cyclic_remove_xcall, &arg);
1912 
1913         /*
1914          * If the cyclic we removed wasn't at CY_HIGH_LEVEL, then we need to
1915          * check the cyp_rpend.  If it's non-zero, then we need to wait here
1916          * for all pending cyclic handlers to run.
1917          */
1918         ASSERT(!(level == CY_HIGH_LEVEL && cpu->cyp_rpend != 0));
1919         ASSERT(!(wait == CY_NOWAIT && cpu->cyp_rpend != 0));
1920         ASSERT(!(arg.cyx_wait == CY_NOWAIT && cpu->cyp_rpend != 0));
1921 
1922         if (wait != arg.cyx_wait) {
1923                 /*
1924                  * We are being told that we must wait if we want to
1925                  * remove this cyclic; put the CPU back in the CYS_ONLINE
1926                  * state and return failure.
1927                  */
1928                 ASSERT(wait == CY_NOWAIT && arg.cyx_wait == CY_WAIT);
1929                 ASSERT(cpu->cyp_state == CYS_REMOVING);
1930                 cpu->cyp_state = CYS_ONLINE;
1931 
1932                 return (0);
1933         }
1934 
1935         if (cpu->cyp_rpend != 0)
1936                 sema_p(&cpu->cyp_modify_wait);
1937 
1938         ASSERT(cpu->cyp_state == CYS_REMOVING);
1939 
1940         cpu->cyp_rpend = 0;
1941         cpu->cyp_state = CYS_ONLINE;
1942 
1943         return (1);
1944 }
1945 
1946 /*
1947  * If cyclic_reprogram() is called on the same CPU as the cyclic's CPU, then
1948  * it calls this function directly. Else, it invokes this function through
1949  * an X-call to the cyclic's CPU.
1950  */
1951 static void
1952 cyclic_reprogram_cyclic(cyc_cpu_t *cpu, cyc_index_t ndx, hrtime_t expire)
1953 {
1954         cyc_backend_t *be = cpu->cyp_backend;
1955         cyb_arg_t bar = be->cyb_arg;
1956         cyc_cookie_t cookie;
1957         cyc_index_t nelems, i;
1958         cyc_index_t *heap;
1959         cyclic_t *cyclic;
1960         hrtime_t oexpire;
1961         int reprog;
1962 
1963         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
1964 
1965         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-xcall", ndx);
1966 
1967         nelems = cpu->cyp_nelems;
1968         ASSERT(nelems > 0);
1969         heap = cpu->cyp_heap;
1970 
1971         /*
1972          * Reprogrammed cyclics are typically one-shot ones that get
1973          * set to infinity on every expiration. We shorten the search by
1974          * searching from the bottom of the heap to the top instead of the
1975          * other way around.
1976          */
1977         for (i = nelems - 1; i >= 0; i--) {
1978                 if (heap[i] == ndx)
1979                         break;
1980         }
1981         if (i < 0)
1982                 panic("attempt to reprogram non-existent cyclic");
1983 
1984         cyclic = &cpu->cyp_cyclics[ndx];
1985         oexpire = cyclic->cy_expire;
1986         cyclic->cy_expire = expire;
1987 
1988         reprog = (i == 0);
1989         if (expire > oexpire) {
1990                 CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-down", i);
1991                 cyclic_downheap(cpu, i);
1992         } else if (i > 0) {
1993                 CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-up", i);
1994                 reprog = cyclic_upheap(cpu, i);
1995         }
1996 
1997         if (reprog && (cpu->cyp_state != CYS_SUSPENDED)) {
1998                 /*
1999                  * The root changed. Reprogram the clock source.
2000                  */
2001                 CYC_TRACE0(cpu, CY_HIGH_LEVEL, "reprog-root");
2002                 cyclic = &cpu->cyp_cyclics[heap[0]];
2003                 be->cyb_reprogram(bar, cyclic->cy_expire);
2004         }
2005 
2006         be->cyb_restore_level(bar, cookie);
2007 }
2008 
2009 static void
2010 cyclic_reprogram_xcall(cyc_xcallarg_t *arg)
2011 {
2012         cyclic_reprogram_cyclic(arg->cyx_cpu, arg->cyx_ndx,
2013             arg->cyx_when->cyt_when);
2014 }
2015 
2016 static void
2017 cyclic_reprogram_here(cyc_cpu_t *cpu, cyc_index_t ndx, hrtime_t expiration)
2018 {
2019         cyc_backend_t *be = cpu->cyp_backend;
2020         cyc_xcallarg_t arg;
2021         cyc_time_t when;
2022 
2023         ASSERT(expiration > 0);
2024 
2025         arg.cyx_ndx = ndx;
2026         arg.cyx_cpu = cpu;
2027         arg.cyx_when = &when;
2028         when.cyt_when = expiration;
2029 
2030         be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
2031             (cyc_func_t)cyclic_reprogram_xcall, &arg);
2032 }
2033 
2034 /*
2035  * cyclic_juggle_one_to() should only be called when the source cyclic
2036  * can be juggled and the destination CPU is known to be able to accept
2037  * it.
2038  */
2039 static void
2040 cyclic_juggle_one_to(cyc_id_t *idp, cyc_cpu_t *dest)
2041 {
2042         cyc_cpu_t *src = idp->cyi_cpu;
2043         cyc_index_t ndx = idp->cyi_ndx;
2044         cyc_time_t when;
2045         cyc_handler_t hdlr;
2046         cyclic_t *cyclic;
2047         uint16_t flags;
2048         hrtime_t delay;
2049 
2050         ASSERT(MUTEX_HELD(&cpu_lock));
2051         ASSERT(src != NULL && idp->cyi_omni_list == NULL);
2052         ASSERT(!(dest->cyp_cpu->cpu_flags & (CPU_QUIESCED | CPU_OFFLINE)));
2053         CYC_PTRACE("juggle-one-to", idp, dest);
2054 
2055         cyclic = &src->cyp_cyclics[ndx];
2056 
2057         flags = cyclic->cy_flags;
2058         ASSERT(!(flags & CYF_CPU_BOUND) && !(flags & CYF_FREE));
2059 
2060         hdlr.cyh_func = cyclic->cy_handler;
2061         hdlr.cyh_level = cyclic->cy_level;
2062         hdlr.cyh_arg = cyclic->cy_arg;
2063 
2064         /*
2065          * Before we begin the juggling process, see if the destination
2066          * CPU requires an expansion.  If it does, we'll perform the
2067          * expansion before removing the cyclic.  This is to prevent us
2068          * from blocking while a system-critical cyclic (notably, the clock
2069          * cyclic) isn't on a CPU.
2070          */
2071         if (dest->cyp_nelems == dest->cyp_size) {
2072                 CYC_PTRACE("remove-expand", idp, dest);
2073                 cyclic_expand(dest);
2074                 ASSERT(dest->cyp_nelems < dest->cyp_size);
2075         }
2076 
2077         /*
2078          * Prevent a reprogram of this cyclic while we are relocating it.
2079          * Otherwise, cyclic_reprogram_here() will end up sending an X-call
2080          * to the wrong CPU.
2081          */
2082         rw_enter(&idp->cyi_lock, RW_WRITER);
2083 
2084         /*
2085          * Remove the cyclic from the source.  As mentioned above, we cannot
2086          * block during this operation; if we cannot remove the cyclic
2087          * without waiting, we spin for a time shorter than the interval, and
2088          * reattempt the (non-blocking) removal.  If we continue to fail,
2089          * we will exponentially back off (up to half of the interval).
2090          * Note that the removal will ultimately succeed -- even if the
2091          * cyclic handler is blocked on a resource held by a thread which we
2092          * have preempted, priority inheritance assures that the preempted
2093          * thread will preempt us and continue to progress.
2094          */
2095         for (delay = NANOSEC / MICROSEC; ; delay <<= 1) {
2096                 /*
2097                  * Before we begin this operation, disable kernel preemption.
2098                  */
2099                 kpreempt_disable();
2100                 if (cyclic_remove_here(src, ndx, &when, CY_NOWAIT))
2101                         break;
2102 
2103                 /*
2104                  * The operation failed; enable kernel preemption while
2105                  * spinning.
2106                  */
2107                 kpreempt_enable();
2108 
2109                 CYC_PTRACE("remove-retry", idp, src);
2110 
2111                 if (delay > (cyclic->cy_interval >> 1))
2112                         delay = cyclic->cy_interval >> 1;
2113 
2114                 /*
2115                  * Drop the RW lock to avoid a deadlock with the cyclic
2116                  * handler (because it can potentially call cyclic_reprogram().
2117                  */
2118                 rw_exit(&idp->cyi_lock);
2119                 drv_usecwait((clock_t)(delay / (NANOSEC / MICROSEC)));
2120                 rw_enter(&idp->cyi_lock, RW_WRITER);
2121         }
2122 
2123         /*
2124          * Now add the cyclic to the destination.  This won't block; we
2125          * performed any necessary (blocking) expansion of the destination
2126          * CPU before removing the cyclic from the source CPU.
2127          */
2128         idp->cyi_ndx = cyclic_add_here(dest, &hdlr, &when, flags);
2129         idp->cyi_cpu = dest;
2130         kpreempt_enable();
2131 
2132         /*
2133          * Now that we have successfully relocated the cyclic, allow
2134          * it to be reprogrammed.
2135          */
2136         rw_exit(&idp->cyi_lock);
2137 }
2138 
2139 static int
2140 cyclic_juggle_one(cyc_id_t *idp)
2141 {
2142         cyc_index_t ndx = idp->cyi_ndx;
2143         cyc_cpu_t *cpu = idp->cyi_cpu, *dest;
2144         cyclic_t *cyclic = &cpu->cyp_cyclics[ndx];
2145         cpu_t *c = cpu->cyp_cpu;
2146         cpupart_t *part = c->cpu_part;
2147 
2148         CYC_PTRACE("juggle-one", idp, cpu);
2149         ASSERT(MUTEX_HELD(&cpu_lock));
2150         ASSERT(!(c->cpu_flags & CPU_OFFLINE));
2151         ASSERT(cpu->cyp_state == CYS_ONLINE);
2152         ASSERT(!(cyclic->cy_flags & CYF_FREE));
2153 
2154         if ((dest = cyclic_pick_cpu(part, c, c, cyclic->cy_flags)) == NULL) {
2155                 /*
2156                  * Bad news:  this cyclic can't be juggled.
2157                  */
2158                 CYC_PTRACE("juggle-fail", idp, cpu)
2159                 return (0);
2160         }
2161 
2162         cyclic_juggle_one_to(idp, dest);
2163 
2164         return (1);
2165 }
2166 
2167 static void
2168 cyclic_unbind_cpu(cyclic_id_t id)
2169 {
2170         cyc_id_t *idp = (cyc_id_t *)id;
2171         cyc_cpu_t *cpu = idp->cyi_cpu;
2172         cpu_t *c = cpu->cyp_cpu;
2173         cyclic_t *cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];
2174 
2175         CYC_PTRACE("unbind-cpu", id, cpu);
2176         ASSERT(MUTEX_HELD(&cpu_lock));
2177         ASSERT(cpu->cyp_state == CYS_ONLINE);
2178         ASSERT(!(cyclic->cy_flags & CYF_FREE));
2179         ASSERT(cyclic->cy_flags & CYF_CPU_BOUND);
2180 
2181         cyclic->cy_flags &= ~CYF_CPU_BOUND;
2182 
2183         /*
2184          * If we were bound to CPU which has interrupts disabled, we need
2185          * to juggle away.  This can only fail if we are bound to a
2186          * processor set, and if every CPU in the processor set has
2187          * interrupts disabled.
2188          */
2189         if (!(c->cpu_flags & CPU_ENABLE)) {
2190                 int res = cyclic_juggle_one(idp);
2191 
2192                 ASSERT((res && idp->cyi_cpu != cpu) ||
2193                     (!res && (cyclic->cy_flags & CYF_PART_BOUND)));
2194         }
2195 }
2196 
2197 static void
2198 cyclic_bind_cpu(cyclic_id_t id, cpu_t *d)
2199 {
2200         cyc_id_t *idp = (cyc_id_t *)id;
2201         cyc_cpu_t *dest = d->cpu_cyclic, *cpu = idp->cyi_cpu;
2202         cpu_t *c = cpu->cyp_cpu;
2203         cyclic_t *cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];
2204         cpupart_t *part = c->cpu_part;
2205 
2206         CYC_PTRACE("bind-cpu", id, dest);
2207         ASSERT(MUTEX_HELD(&cpu_lock));
2208         ASSERT(!(d->cpu_flags & CPU_OFFLINE));
2209         ASSERT(!(c->cpu_flags & CPU_OFFLINE));
2210         ASSERT(cpu->cyp_state == CYS_ONLINE);
2211         ASSERT(dest != NULL);
2212         ASSERT(dest->cyp_state == CYS_ONLINE);
2213         ASSERT(!(cyclic->cy_flags & CYF_FREE));
2214         ASSERT(!(cyclic->cy_flags & CYF_CPU_BOUND));
2215 
2216         dest = cyclic_pick_cpu(part, d, NULL, cyclic->cy_flags | CYF_CPU_BOUND);
2217 
2218         if (dest != cpu) {
2219                 cyclic_juggle_one_to(idp, dest);
2220                 cyclic = &dest->cyp_cyclics[idp->cyi_ndx];
2221         }
2222 
2223         cyclic->cy_flags |= CYF_CPU_BOUND;
2224 }
2225 
2226 static void
2227 cyclic_unbind_cpupart(cyclic_id_t id)
2228 {
2229         cyc_id_t *idp = (cyc_id_t *)id;
2230         cyc_cpu_t *cpu = idp->cyi_cpu;
2231         cpu_t *c = cpu->cyp_cpu;
2232         cyclic_t *cyc = &cpu->cyp_cyclics[idp->cyi_ndx];
2233 
2234         CYC_PTRACE("unbind-part", idp, c->cpu_part);
2235         ASSERT(MUTEX_HELD(&cpu_lock));
2236         ASSERT(cpu->cyp_state == CYS_ONLINE);
2237         ASSERT(!(cyc->cy_flags & CYF_FREE));
2238         ASSERT(cyc->cy_flags & CYF_PART_BOUND);
2239 
2240         cyc->cy_flags &= ~CYF_PART_BOUND;
2241 
2242         /*
2243          * If we're on a CPU which has interrupts disabled (and if this cyclic
2244          * isn't bound to the CPU), we need to juggle away.
2245          */
2246         if (!(c->cpu_flags & CPU_ENABLE) && !(cyc->cy_flags & CYF_CPU_BOUND)) {
2247                 int res = cyclic_juggle_one(idp);
2248 
2249                 ASSERT(res && idp->cyi_cpu != cpu);
2250         }
2251 }
2252 
2253 static void
2254 cyclic_bind_cpupart(cyclic_id_t id, cpupart_t *part)
2255 {
2256         cyc_id_t *idp = (cyc_id_t *)id;
2257         cyc_cpu_t *cpu = idp->cyi_cpu, *dest;
2258         cpu_t *c = cpu->cyp_cpu;
2259         cyclic_t *cyc = &cpu->cyp_cyclics[idp->cyi_ndx];
2260 
2261         CYC_PTRACE("bind-part", idp, part);
2262         ASSERT(MUTEX_HELD(&cpu_lock));
2263         ASSERT(!(c->cpu_flags & CPU_OFFLINE));
2264         ASSERT(cpu->cyp_state == CYS_ONLINE);
2265         ASSERT(!(cyc->cy_flags & CYF_FREE));
2266         ASSERT(!(cyc->cy_flags & CYF_PART_BOUND));
2267         ASSERT(part->cp_ncpus > 0);
2268 
2269         dest = cyclic_pick_cpu(part, c, NULL, cyc->cy_flags | CYF_PART_BOUND);
2270 
2271         if (dest != cpu) {
2272                 cyclic_juggle_one_to(idp, dest);
2273                 cyc = &dest->cyp_cyclics[idp->cyi_ndx];
2274         }
2275 
2276         cyc->cy_flags |= CYF_PART_BOUND;
2277 }
2278 
2279 static void
2280 cyclic_configure(cpu_t *c)
2281 {
2282         cyc_cpu_t *cpu = kmem_zalloc(sizeof (cyc_cpu_t), KM_SLEEP);
2283         cyc_backend_t *nbe = kmem_zalloc(sizeof (cyc_backend_t), KM_SLEEP);
2284         int i;
2285 
2286         CYC_PTRACE1("configure", cpu);
2287         ASSERT(MUTEX_HELD(&cpu_lock));
2288 
2289         if (cyclic_id_cache == NULL)
2290                 cyclic_id_cache = kmem_cache_create("cyclic_id_cache",
2291                     sizeof (cyc_id_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
2292 
2293         cpu->cyp_cpu = c;
2294 
2295         sema_init(&cpu->cyp_modify_wait, 0, NULL, SEMA_DEFAULT, NULL);
2296 
2297         cpu->cyp_size = 1;
2298         cpu->cyp_heap = kmem_zalloc(sizeof (cyc_index_t), KM_SLEEP);
2299         cpu->cyp_cyclics = kmem_zalloc(sizeof (cyclic_t), KM_SLEEP);
2300         cpu->cyp_cyclics->cy_flags = CYF_FREE;
2301 
2302         for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
2303                 /*
2304                  * We don't need to set the sizemask; it's already zero
2305                  * (which is the appropriate sizemask for a size of 1).
2306                  */
2307                 cpu->cyp_softbuf[i].cys_buf[0].cypc_buf =
2308                     kmem_alloc(sizeof (cyc_index_t), KM_SLEEP);
2309         }
2310 
2311         cpu->cyp_state = CYS_OFFLINE;
2312 
2313         /*
2314          * Setup the backend for this CPU.
2315          */
2316         bcopy(&cyclic_backend, nbe, sizeof (cyc_backend_t));
2317         nbe->cyb_arg = nbe->cyb_configure(c);
2318         cpu->cyp_backend = nbe;
2319 
2320         /*
2321          * On platforms where stray interrupts may be taken during startup,
2322          * the CPU's cpu_cyclic pointer serves as an indicator that the
2323          * cyclic subsystem for this CPU is prepared to field interrupts.
2324          */
2325         membar_producer();
2326 
2327         c->cpu_cyclic = cpu;
2328 }
2329 
2330 static void
2331 cyclic_unconfigure(cpu_t *c)
2332 {
2333         cyc_cpu_t *cpu = c->cpu_cyclic;
2334         cyc_backend_t *be = cpu->cyp_backend;
2335         cyb_arg_t bar = be->cyb_arg;
2336         int i;
2337 
2338         CYC_PTRACE1("unconfigure", cpu);
2339         ASSERT(MUTEX_HELD(&cpu_lock));
2340         ASSERT(cpu->cyp_state == CYS_OFFLINE);
2341         ASSERT(cpu->cyp_nelems == 0);
2342 
2343         /*
2344          * Let the backend know that the CPU is being yanked, and free up
2345          * the backend structure.
2346          */
2347         be->cyb_unconfigure(bar);
2348         kmem_free(be, sizeof (cyc_backend_t));
2349         cpu->cyp_backend = NULL;
2350 
2351         /*
2352          * Free up the producer/consumer buffers at each of the soft levels.
2353          */
2354         for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
2355                 cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
2356                 uchar_t hard = softbuf->cys_hard;
2357                 cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard];
2358                 size_t bufsize = sizeof (cyc_index_t) * (pc->cypc_sizemask + 1);
2359 
2360                 /*
2361                  * Assert that we're not in the middle of a resize operation.
2362                  */
2363                 ASSERT(hard == softbuf->cys_soft);
2364                 ASSERT(hard == 0 || hard == 1);
2365                 ASSERT(pc->cypc_buf != NULL);
2366                 ASSERT(softbuf->cys_buf[hard ^ 1].cypc_buf == NULL);
2367 
2368                 kmem_free(pc->cypc_buf, bufsize);
2369                 pc->cypc_buf = NULL;
2370         }
2371 
2372         /*
2373          * Finally, clean up our remaining dynamic structures and NULL out
2374          * the cpu_cyclic pointer.
2375          */
2376         kmem_free(cpu->cyp_cyclics, cpu->cyp_size * sizeof (cyclic_t));
2377         kmem_free(cpu->cyp_heap, cpu->cyp_size * sizeof (cyc_index_t));
2378         kmem_free(cpu, sizeof (cyc_cpu_t));
2379 
2380         c->cpu_cyclic = NULL;
2381 }
2382 
2383 static int
2384 cyclic_cpu_setup(cpu_setup_t what, int id)
2385 {
2386         /*
2387          * We are guaranteed that there is still/already an entry in the
2388          * cpu array for this CPU.
2389          */
2390         cpu_t *c = cpu[id];
2391         cyc_cpu_t *cyp = c->cpu_cyclic;
2392 
2393         ASSERT(MUTEX_HELD(&cpu_lock));
2394 
2395         switch (what) {
2396         case CPU_CONFIG:
2397                 ASSERT(cyp == NULL);
2398                 cyclic_configure(c);
2399                 break;
2400 
2401         case CPU_UNCONFIG:
2402                 ASSERT(cyp != NULL && cyp->cyp_state == CYS_OFFLINE);
2403                 cyclic_unconfigure(c);
2404                 break;
2405 
2406         default:
2407                 break;
2408         }
2409 
2410         return (0);
2411 }
2412 
2413 static void
2414 cyclic_suspend_xcall(cyc_xcallarg_t *arg)
2415 {
2416         cyc_cpu_t *cpu = arg->cyx_cpu;
2417         cyc_backend_t *be = cpu->cyp_backend;
2418         cyc_cookie_t cookie;
2419         cyb_arg_t bar = be->cyb_arg;
2420 
2421         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
2422 
2423         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "suspend-xcall", cpu->cyp_nelems);
2424         ASSERT(cpu->cyp_state == CYS_ONLINE || cpu->cyp_state == CYS_OFFLINE);
2425 
2426         /*
2427          * We won't disable this CPU unless it has a non-zero number of
2428          * elements (cpu_lock assures that no one else may be attempting
2429          * to disable this CPU).
2430          */
2431         if (cpu->cyp_nelems > 0) {
2432                 ASSERT(cpu->cyp_state == CYS_ONLINE);
2433                 be->cyb_disable(bar);
2434         }
2435 
2436         if (cpu->cyp_state == CYS_ONLINE)
2437                 cpu->cyp_state = CYS_SUSPENDED;
2438 
2439         be->cyb_suspend(bar);
2440         be->cyb_restore_level(bar, cookie);
2441 }
2442 
2443 static void
2444 cyclic_resume_xcall(cyc_xcallarg_t *arg)
2445 {
2446         cyc_cpu_t *cpu = arg->cyx_cpu;
2447         cyc_backend_t *be = cpu->cyp_backend;
2448         cyc_cookie_t cookie;
2449         cyb_arg_t bar = be->cyb_arg;
2450         cyc_state_t state = cpu->cyp_state;
2451 
2452         cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);
2453 
2454         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "resume-xcall", cpu->cyp_nelems);
2455         ASSERT(state == CYS_SUSPENDED || state == CYS_OFFLINE);
2456 
2457         be->cyb_resume(bar);
2458 
2459         /*
2460          * We won't enable this CPU unless it has a non-zero number of
2461          * elements.
2462          */
2463         if (cpu->cyp_nelems > 0) {
2464                 cyclic_t *cyclic = &cpu->cyp_cyclics[cpu->cyp_heap[0]];
2465                 hrtime_t exp = cyclic->cy_expire;
2466 
2467                 CYC_TRACE(cpu, CY_HIGH_LEVEL, "resume-reprog", cyclic, exp);
2468                 ASSERT(state == CYS_SUSPENDED);
2469                 be->cyb_enable(bar);
2470                 be->cyb_reprogram(bar, exp);
2471         }
2472 
2473         if (state == CYS_SUSPENDED)
2474                 cpu->cyp_state = CYS_ONLINE;
2475 
2476         CYC_TRACE1(cpu, CY_HIGH_LEVEL, "resume-done", cpu->cyp_nelems);
2477         be->cyb_restore_level(bar, cookie);
2478 }
2479 
2480 static void
2481 cyclic_omni_start(cyc_id_t *idp, cyc_cpu_t *cpu)
2482 {
2483         cyc_omni_handler_t *omni = &idp->cyi_omni_hdlr;
2484         cyc_omni_cpu_t *ocpu = kmem_alloc(sizeof (cyc_omni_cpu_t), KM_SLEEP);
2485         cyc_handler_t hdlr;
2486         cyc_time_t when;
2487 
2488         CYC_PTRACE("omni-start", cpu, idp);
2489         ASSERT(MUTEX_HELD(&cpu_lock));
2490         ASSERT(cpu->cyp_state == CYS_ONLINE);
2491         ASSERT(idp->cyi_cpu == NULL);
2492 
2493         hdlr.cyh_func = NULL;
2494         hdlr.cyh_arg = NULL;
2495         hdlr.cyh_level = CY_LEVELS;
2496 
2497         when.cyt_when = 0;
2498         when.cyt_interval = 0;
2499 
2500         omni->cyo_online(omni->cyo_arg, cpu->cyp_cpu, &hdlr, &when);
2501 
2502         ASSERT(hdlr.cyh_func != NULL);
2503         ASSERT(hdlr.cyh_level < CY_LEVELS);
2504         ASSERT(when.cyt_when >= 0 && when.cyt_interval > 0);
2505 
2506         ocpu->cyo_cpu = cpu;
2507         ocpu->cyo_arg = hdlr.cyh_arg;
2508         ocpu->cyo_ndx = cyclic_add_here(cpu, &hdlr, &when, 0);
2509         ocpu->cyo_next = idp->cyi_omni_list;
2510         idp->cyi_omni_list = ocpu;
2511 }
2512 
2513 static void
2514 cyclic_omni_stop(cyc_id_t *idp, cyc_cpu_t *cpu)
2515 {
2516         cyc_omni_handler_t *omni = &idp->cyi_omni_hdlr;
2517         cyc_omni_cpu_t *ocpu = idp->cyi_omni_list, *prev = NULL;
2518         clock_t delay;
2519         int ret;
2520 
2521         CYC_PTRACE("omni-stop", cpu, idp);
2522         ASSERT(MUTEX_HELD(&cpu_lock));
2523         ASSERT(cpu->cyp_state == CYS_ONLINE);
2524         ASSERT(idp->cyi_cpu == NULL);
2525         ASSERT(ocpu != NULL);
2526 
2527         /*
2528          * Prevent a reprogram of this cyclic while we are removing it.
2529          * Otherwise, cyclic_reprogram_here() will end up sending an X-call
2530          * to the offlined CPU.
2531          */
2532         rw_enter(&idp->cyi_lock, RW_WRITER);
2533 
2534         while (ocpu != NULL && ocpu->cyo_cpu != cpu) {
2535                 prev = ocpu;
2536                 ocpu = ocpu->cyo_next;
2537         }
2538 
2539         /*
2540          * We _must_ have found an cyc_omni_cpu which corresponds to this
2541          * CPU -- the definition of an omnipresent cyclic is that it runs
2542          * on all online CPUs.
2543          */
2544         ASSERT(ocpu != NULL);
2545 
2546         if (prev == NULL) {
2547                 idp->cyi_omni_list = ocpu->cyo_next;
2548         } else {
2549                 prev->cyo_next = ocpu->cyo_next;
2550         }
2551 
2552         /*
2553          * Remove the cyclic from the source.  We cannot block during this
2554          * operation because we are holding the cyi_lock which can be held
2555          * by the cyclic handler via cyclic_reprogram().
2556          *
2557          * If we cannot remove the cyclic without waiting, we spin for a time,
2558          * and reattempt the (non-blocking) removal. If the handler is blocked
2559          * on the cyi_lock, then we let go of it in the spin loop to give
2560          * the handler a chance to run. Note that the removal will ultimately
2561          * succeed -- even if the cyclic handler is blocked on a resource
2562          * held by a thread which we have preempted, priority inheritance
2563          * assures that the preempted thread will preempt us and continue
2564          * to progress.
2565          */
2566         for (delay = 1; ; delay <<= 1) {
2567                 /*
2568                  * Before we begin this operation, disable kernel preemption.
2569                  */
2570                 kpreempt_disable();
2571                 ret = cyclic_remove_here(ocpu->cyo_cpu, ocpu->cyo_ndx, NULL,
2572                     CY_NOWAIT);
2573                 /*
2574                  * Enable kernel preemption while spinning.
2575                  */
2576                 kpreempt_enable();
2577 
2578                 if (ret)
2579                         break;
2580 
2581                 CYC_PTRACE("remove-omni-retry", idp, ocpu->cyo_cpu);
2582 
2583                 /*
2584                  * Drop the RW lock to avoid a deadlock with the cyclic
2585                  * handler (because it can potentially call cyclic_reprogram().
2586                  */
2587                 rw_exit(&idp->cyi_lock);
2588                 drv_usecwait(delay);
2589                 rw_enter(&idp->cyi_lock, RW_WRITER);
2590         }
2591 
2592         /*
2593          * Now that we have successfully removed the cyclic, allow the omni
2594          * cyclic to be reprogrammed on other CPUs.
2595          */
2596         rw_exit(&idp->cyi_lock);
2597 
2598         /*
2599          * The cyclic has been removed from this CPU; time to call the
2600          * omnipresent offline handler.
2601          */
2602         if (omni->cyo_offline != NULL)
2603                 omni->cyo_offline(omni->cyo_arg, cpu->cyp_cpu, ocpu->cyo_arg);
2604 
2605         kmem_free(ocpu, sizeof (cyc_omni_cpu_t));
2606 }
2607 
2608 static cyc_id_t *
2609 cyclic_new_id()
2610 {
2611         cyc_id_t *idp;
2612 
2613         ASSERT(MUTEX_HELD(&cpu_lock));
2614 
2615         idp = kmem_cache_alloc(cyclic_id_cache, KM_SLEEP);
2616 
2617         /*
2618          * The cyi_cpu field of the cyc_id_t structure tracks the CPU
2619          * associated with the cyclic.  If and only if this field is NULL, the
2620          * cyc_id_t is an omnipresent cyclic.  Note that cyi_omni_list may be
2621          * NULL for an omnipresent cyclic while the cyclic is being created
2622          * or destroyed.
2623          */
2624         idp->cyi_cpu = NULL;
2625         idp->cyi_ndx = 0;
2626         rw_init(&idp->cyi_lock, NULL, RW_DEFAULT, NULL);
2627 
2628         idp->cyi_next = cyclic_id_head;
2629         idp->cyi_prev = NULL;
2630         idp->cyi_omni_list = NULL;
2631 
2632         if (cyclic_id_head != NULL) {
2633                 ASSERT(cyclic_id_head->cyi_prev == NULL);
2634                 cyclic_id_head->cyi_prev = idp;
2635         }
2636 
2637         cyclic_id_head = idp;
2638 
2639         return (idp);
2640 }
2641 
2642 /*
2643  *  cyclic_id_t cyclic_add(cyc_handler_t *, cyc_time_t *)
2644  *
2645  *  Overview
2646  *
2647  *    cyclic_add() will create an unbound cyclic with the specified handler and
2648  *    interval.  The cyclic will run on a CPU which both has interrupts enabled
2649  *    and is in the system CPU partition.
2650  *
2651  *  Arguments and notes
2652  *
2653  *    As its first argument, cyclic_add() takes a cyc_handler, which has the
2654  *    following members:
2655  *
2656  *      cyc_func_t cyh_func    <-- Cyclic handler
2657  *      void *cyh_arg          <-- Argument to cyclic handler
2658  *      cyc_level_t cyh_level  <-- Level at which to fire; must be one of
2659  *                                 CY_LOW_LEVEL, CY_LOCK_LEVEL or CY_HIGH_LEVEL
2660  *
2661  *    Note that cyh_level is _not_ an ipl or spl; it must be one the
2662  *    CY_*_LEVELs.  This layer of abstraction allows the platform to define
2663  *    the precise interrupt priority levels, within the following constraints:
2664  *
2665  *       CY_LOCK_LEVEL must map to LOCK_LEVEL
2666  *       CY_HIGH_LEVEL must map to an ipl greater than LOCK_LEVEL
2667  *       CY_LOW_LEVEL must map to an ipl below LOCK_LEVEL
2668  *
2669  *    In addition to a cyc_handler, cyclic_add() takes a cyc_time, which
2670  *    has the following members:
2671  *
2672  *       hrtime_t cyt_when     <-- Absolute time, in nanoseconds since boot, at
2673  *                                 which to start firing
2674  *       hrtime_t cyt_interval <-- Length of interval, in nanoseconds
2675  *
2676  *    gethrtime() is the time source for nanoseconds since boot.  If cyt_when
2677  *    is set to 0, the cyclic will start to fire when cyt_interval next
2678  *    divides the number of nanoseconds since boot.
2679  *
2680  *    The cyt_interval field _must_ be filled in by the caller; one-shots are
2681  *    _not_ explicitly supported by the cyclic subsystem (cyclic_add() will
2682  *    assert that cyt_interval is non-zero).  The maximum value for either
2683  *    field is INT64_MAX; the caller is responsible for assuring that
2684  *    cyt_when + cyt_interval <= INT64_MAX.  Neither field may be negative.
2685  *
2686  *    For an arbitrary time t in the future, the cyclic handler is guaranteed
2687  *    to have been called (t - cyt_when) / cyt_interval times.  This will
2688  *    be true even if interrupts have been disabled for periods greater than
2689  *    cyt_interval nanoseconds.  In order to compensate for such periods,
2690  *    the cyclic handler may be called a finite number of times with an
2691  *    arbitrarily small interval.
2692  *
2693  *    The cyclic subsystem will not enforce any lower bound on the interval;
2694  *    if the interval is less than the time required to process an interrupt,
2695  *    the CPU will wedge.  It's the responsibility of the caller to assure that
2696  *    either the value of the interval is sane, or that its caller has
2697  *    sufficient privilege to deny service (i.e. its caller is root).
2698  *
2699  *    The cyclic handler is guaranteed to be single threaded, even while the
2700  *    cyclic is being juggled between CPUs (see cyclic_juggle(), below).
2701  *    That is, a given cyclic handler will never be executed simultaneously
2702  *    on different CPUs.
2703  *
2704  *  Return value
2705  *
2706  *    cyclic_add() returns a cyclic_id_t, which is guaranteed to be a value
2707  *    other than CYCLIC_NONE.  cyclic_add() cannot fail.
2708  *
2709  *  Caller's context
2710  *
2711  *    cpu_lock must be held by the caller, and the caller must not be in
2712  *    interrupt context.  cyclic_add() will perform a KM_SLEEP kernel
2713  *    memory allocation, so the usual rules (e.g. p_lock cannot be held)
2714  *    apply.  A cyclic may be added even in the presence of CPUs that have
2715  *    not been configured with respect to the cyclic subsystem, but only
2716  *    configured CPUs will be eligible to run the new cyclic.
2717  *
2718  *  Cyclic handler's context
2719  *
2720  *    Cyclic handlers will be executed in the interrupt context corresponding
2721  *    to the specified level (i.e. either high, lock or low level).  The
2722  *    usual context rules apply.
2723  *
2724  *    A cyclic handler may not grab ANY locks held by the caller of any of
2725  *    cyclic_add(), cyclic_remove() or cyclic_bind(); the implementation of
2726  *    these functions may require blocking on cyclic handler completion.
2727  *    Moreover, cyclic handlers may not make any call back into the cyclic
2728  *    subsystem.
2729  */
2730 cyclic_id_t
2731 cyclic_add(cyc_handler_t *hdlr, cyc_time_t *when)
2732 {
2733         cyc_id_t *idp = cyclic_new_id();
2734 
2735         ASSERT(MUTEX_HELD(&cpu_lock));
2736         ASSERT(when->cyt_when >= 0 && when->cyt_interval > 0);
2737 
2738         idp->cyi_cpu = cyclic_pick_cpu(NULL, NULL, NULL, 0);
2739         idp->cyi_ndx = cyclic_add_here(idp->cyi_cpu, hdlr, when, 0);
2740 
2741         return ((uintptr_t)idp);
2742 }
2743 
2744 /*
2745  *  cyclic_id_t cyclic_add_omni(cyc_omni_handler_t *)
2746  *
2747  *  Overview
2748  *
2749  *    cyclic_add_omni() will create an omnipresent cyclic with the specified
2750  *    online and offline handlers.  Omnipresent cyclics run on all online
2751  *    CPUs, including CPUs which have unbound interrupts disabled.
2752  *
2753  *  Arguments
2754  *
2755  *    As its only argument, cyclic_add_omni() takes a cyc_omni_handler, which
2756  *    has the following members:
2757  *
2758  *      void (*cyo_online)()   <-- Online handler
2759  *      void (*cyo_offline)()  <-- Offline handler
2760  *      void *cyo_arg          <-- Argument to be passed to on/offline handlers
2761  *
2762  *  Online handler
2763  *
2764  *    The cyo_online member is a pointer to a function which has the following
2765  *    four arguments:
2766  *
2767  *      void *                 <-- Argument (cyo_arg)
2768  *      cpu_t *                <-- Pointer to CPU about to be onlined
2769  *      cyc_handler_t *        <-- Pointer to cyc_handler_t; must be filled in
2770  *                                 by omni online handler
2771  *      cyc_time_t *           <-- Pointer to cyc_time_t; must be filled in by
2772  *                                 omni online handler
2773  *
2774  *    The omni cyclic online handler is always called _before_ the omni
2775  *    cyclic begins to fire on the specified CPU.  As the above argument
2776  *    description implies, the online handler must fill in the two structures
2777  *    passed to it:  the cyc_handler_t and the cyc_time_t.  These are the
2778  *    same two structures passed to cyclic_add(), outlined above.  This
2779  *    allows the omni cyclic to have maximum flexibility; different CPUs may
2780  *    optionally
2781  *
2782  *      (a)  have different intervals
2783  *      (b)  be explicitly in or out of phase with one another
2784  *      (c)  have different handlers
2785  *      (d)  have different handler arguments
2786  *      (e)  fire at different levels
2787  *
2788  *    Of these, (e) seems somewhat dubious, but is nonetheless allowed.
2789  *
2790  *    The omni online handler is called in the same context as cyclic_add(),
2791  *    and has the same liberties:  omni online handlers may perform KM_SLEEP
2792  *    kernel memory allocations, and may grab locks which are also acquired
2793  *    by cyclic handlers.  However, omni cyclic online handlers may _not_
2794  *    call back into the cyclic subsystem, and should be generally careful
2795  *    about calling into arbitrary kernel subsystems.
2796  *
2797  *  Offline handler
2798  *
2799  *    The cyo_offline member is a pointer to a function which has the following
2800  *    three arguments:
2801  *
2802  *      void *                 <-- Argument (cyo_arg)
2803  *      cpu_t *                <-- Pointer to CPU about to be offlined
2804  *      void *                 <-- CPU's cyclic argument (that is, value
2805  *                                 to which cyh_arg member of the cyc_handler_t
2806  *                                 was set in the omni online handler)
2807  *
2808  *    The omni cyclic offline handler is always called _after_ the omni
2809  *    cyclic has ceased firing on the specified CPU.  Its purpose is to
2810  *    allow cleanup of any resources dynamically allocated in the omni cyclic
2811  *    online handler.  The context of the offline handler is identical to
2812  *    that of the online handler; the same constraints and liberties apply.
2813  *
2814  *    The offline handler is optional; it may be NULL.
2815  *
2816  *  Return value
2817  *
2818  *    cyclic_add_omni() returns a cyclic_id_t, which is guaranteed to be a
2819  *    value other than CYCLIC_NONE.  cyclic_add_omni() cannot fail.
2820  *
2821  *  Caller's context
2822  *
2823  *    The caller's context is identical to that of cyclic_add(), specified
2824  *    above.
2825  */
2826 cyclic_id_t
2827 cyclic_add_omni(cyc_omni_handler_t *omni)
2828 {
2829         cyc_id_t *idp = cyclic_new_id();
2830         cyc_cpu_t *cpu;
2831         cpu_t *c;
2832 
2833         ASSERT(MUTEX_HELD(&cpu_lock));
2834         ASSERT(omni != NULL && omni->cyo_online != NULL);
2835 
2836         idp->cyi_omni_hdlr = *omni;
2837 
2838         c = cpu_list;
2839         do {
2840                 if ((cpu = c->cpu_cyclic) == NULL)
2841                         continue;
2842 
2843                 if (cpu->cyp_state != CYS_ONLINE) {
2844                         ASSERT(cpu->cyp_state == CYS_OFFLINE);
2845                         continue;
2846                 }
2847 
2848                 cyclic_omni_start(idp, cpu);
2849         } while ((c = c->cpu_next) != cpu_list);
2850 
2851         /*
2852          * We must have found at least one online CPU on which to run
2853          * this cyclic.
2854          */
2855         ASSERT(idp->cyi_omni_list != NULL);
2856         ASSERT(idp->cyi_cpu == NULL);
2857 
2858         return ((uintptr_t)idp);
2859 }
2860 
2861 /*
2862  *  void cyclic_remove(cyclic_id_t)
2863  *
2864  *  Overview
2865  *
2866  *    cyclic_remove() will remove the specified cyclic from the system.
2867  *
2868  *  Arguments and notes
2869  *
2870  *    The only argument is a cyclic_id returned from either cyclic_add() or
2871  *    cyclic_add_omni().
2872  *
2873  *    By the time cyclic_remove() returns, the caller is guaranteed that the
2874  *    removed cyclic handler has completed execution (this is the same
2875  *    semantic that untimeout() provides).  As a result, cyclic_remove() may
2876  *    need to block, waiting for the removed cyclic to complete execution.
2877  *    This leads to an important constraint on the caller:  no lock may be
2878  *    held across cyclic_remove() that also may be acquired by a cyclic
2879  *    handler.
2880  *
2881  *  Return value
2882  *
2883  *    None; cyclic_remove() always succeeds.
2884  *
2885  *  Caller's context
2886  *
2887  *    cpu_lock must be held by the caller, and the caller must not be in
2888  *    interrupt context.  The caller may not hold any locks which are also
2889  *    grabbed by any cyclic handler.  See "Arguments and notes", above.
2890  */
2891 void
2892 cyclic_remove(cyclic_id_t id)
2893 {
2894         cyc_id_t *idp = (cyc_id_t *)id;
2895         cyc_id_t *prev = idp->cyi_prev, *next = idp->cyi_next;
2896         cyc_cpu_t *cpu = idp->cyi_cpu;
2897 
2898         CYC_PTRACE("remove", idp, idp->cyi_cpu);
2899         ASSERT(MUTEX_HELD(&cpu_lock));
2900 
2901         if (cpu != NULL) {
2902                 (void) cyclic_remove_here(cpu, idp->cyi_ndx, NULL, CY_WAIT);
2903         } else {
2904                 ASSERT(idp->cyi_omni_list != NULL);
2905                 while (idp->cyi_omni_list != NULL)
2906                         cyclic_omni_stop(idp, idp->cyi_omni_list->cyo_cpu);
2907         }
2908 
2909         if (prev != NULL) {
2910                 ASSERT(cyclic_id_head != idp);
2911                 prev->cyi_next = next;
2912         } else {
2913                 ASSERT(cyclic_id_head == idp);
2914                 cyclic_id_head = next;
2915         }
2916 
2917         if (next != NULL)
2918                 next->cyi_prev = prev;
2919 
2920         kmem_cache_free(cyclic_id_cache, idp);
2921 }
2922 
2923 /*
2924  *  void cyclic_bind(cyclic_id_t, cpu_t *, cpupart_t *)
2925  *
2926  *  Overview
2927  *
2928  *    cyclic_bind() atomically changes the CPU and CPU partition bindings
2929  *    of a cyclic.
2930  *
2931  *  Arguments and notes
2932  *
2933  *    The first argument is a cyclic_id retuned from cyclic_add().
2934  *    cyclic_bind() may _not_ be called on a cyclic_id returned from
2935  *    cyclic_add_omni().
2936  *
2937  *    The second argument specifies the CPU to which to bind the specified
2938  *    cyclic.  If the specified cyclic is bound to a CPU other than the one
2939  *    specified, it will be unbound from its bound CPU.  Unbinding the cyclic
2940  *    from its CPU may cause it to be juggled to another CPU.  If the specified
2941  *    CPU is non-NULL, the cyclic will be subsequently rebound to the specified
2942  *    CPU.
2943  *
2944  *    If a CPU with bound cyclics is transitioned into the P_NOINTR state,
2945  *    only cyclics not bound to the CPU can be juggled away; CPU-bound cyclics
2946  *    will continue to fire on the P_NOINTR CPU.  A CPU with bound cyclics
2947  *    cannot be offlined (attempts to offline the CPU will return EBUSY).
2948  *    Likewise, cyclics may not be bound to an offline CPU; if the caller
2949  *    attempts to bind a cyclic to an offline CPU, the cyclic subsystem will
2950  *    panic.
2951  *
2952  *    The third argument specifies the CPU partition to which to bind the
2953  *    specified cyclic.  If the specified cyclic is bound to a CPU partition
2954  *    other than the one specified, it will be unbound from its bound
2955  *    partition.  Unbinding the cyclic from its CPU partition may cause it
2956  *    to be juggled to another CPU.  If the specified CPU partition is
2957  *    non-NULL, the cyclic will be subsequently rebound to the specified CPU
2958  *    partition.
2959  *
2960  *    It is the caller's responsibility to assure that the specified CPU
2961  *    partition contains a CPU.  If it does not, the cyclic subsystem will
2962  *    panic.  A CPU partition with bound cyclics cannot be destroyed (attempts
2963  *    to destroy the partition will return EBUSY).  If a CPU with
2964  *    partition-bound cyclics is transitioned into the P_NOINTR state, cyclics
2965  *    bound to the CPU's partition (but not bound to the CPU) will be juggled
2966  *    away only if there exists another CPU in the partition in the P_ONLINE
2967  *    state.
2968  *
2969  *    It is the caller's responsibility to assure that the specified CPU and
2970  *    CPU partition are self-consistent.  If both parameters are non-NULL,
2971  *    and the specified CPU partition does not contain the specified CPU, the
2972  *    cyclic subsystem will panic.
2973  *
2974  *    It is the caller's responsibility to assure that the specified CPU has
2975  *    been configured with respect to the cyclic subsystem.  Generally, this
2976  *    is always true for valid, on-line CPUs.  The only periods of time during
2977  *    which this may not be true are during MP boot (i.e. after cyclic_init()
2978  *    is called but before cyclic_mp_init() is called) or during dynamic
2979  *    reconfiguration; cyclic_bind() should only be called with great care
2980  *    from these contexts.
2981  *
2982  *  Return value
2983  *
2984  *    None; cyclic_bind() always succeeds.
2985  *
2986  *  Caller's context
2987  *
2988  *    cpu_lock must be held by the caller, and the caller must not be in
2989  *    interrupt context.  The caller may not hold any locks which are also
2990  *    grabbed by any cyclic handler.
2991  */
2992 void
2993 cyclic_bind(cyclic_id_t id, cpu_t *d, cpupart_t *part)
2994 {
2995         cyc_id_t *idp = (cyc_id_t *)id;
2996         cyc_cpu_t *cpu = idp->cyi_cpu;
2997         cpu_t *c;
2998         uint16_t flags;
2999 
3000         CYC_PTRACE("bind", d, part);
3001         ASSERT(MUTEX_HELD(&cpu_lock));
3002         ASSERT(part == NULL || d == NULL || d->cpu_part == part);
3003 
3004         if (cpu == NULL) {
3005                 ASSERT(idp->cyi_omni_list != NULL);
3006                 panic("attempt to change binding of omnipresent cyclic");
3007         }
3008 
3009         c = cpu->cyp_cpu;
3010         flags = cpu->cyp_cyclics[idp->cyi_ndx].cy_flags;
3011 
3012         if (c != d && (flags & CYF_CPU_BOUND))
3013                 cyclic_unbind_cpu(id);
3014 
3015         /*
3016          * Reload our cpu (we may have migrated).  We don't have to reload
3017          * the flags field here; if we were CYF_PART_BOUND on entry, we are
3018          * CYF_PART_BOUND now.
3019          */
3020         cpu = idp->cyi_cpu;
3021         c = cpu->cyp_cpu;
3022 
3023         if (part != c->cpu_part && (flags & CYF_PART_BOUND))
3024                 cyclic_unbind_cpupart(id);
3025 
3026         /*
3027          * Now reload the flags field, asserting that if we are CPU bound,
3028          * the CPU was specified (and likewise, if we are partition bound,
3029          * the partition was specified).
3030          */
3031         cpu = idp->cyi_cpu;
3032         c = cpu->cyp_cpu;
3033         flags = cpu->cyp_cyclics[idp->cyi_ndx].cy_flags;
3034         ASSERT(!(flags & CYF_CPU_BOUND) || c == d);
3035         ASSERT(!(flags & CYF_PART_BOUND) || c->cpu_part == part);
3036 
3037         if (!(flags & CYF_CPU_BOUND) && d != NULL)
3038                 cyclic_bind_cpu(id, d);
3039 
3040         if (!(flags & CYF_PART_BOUND) && part != NULL)
3041                 cyclic_bind_cpupart(id, part);
3042 }
3043 
3044 int
3045 cyclic_reprogram(cyclic_id_t id, hrtime_t expiration)
3046 {
3047         cyc_id_t *idp = (cyc_id_t *)id;
3048         cyc_cpu_t *cpu;
3049         cyc_omni_cpu_t *ocpu;
3050         cyc_index_t ndx;
3051 
3052         ASSERT(expiration > 0);
3053 
3054         CYC_PTRACE("reprog", idp, idp->cyi_cpu);
3055 
3056         kpreempt_disable();
3057 
3058         /*
3059          * Prevent the cyclic from moving or disappearing while we reprogram.
3060          */
3061         rw_enter(&idp->cyi_lock, RW_READER);
3062 
3063         if (idp->cyi_cpu == NULL) {
3064                 ASSERT(curthread->t_preempt > 0);
3065                 cpu = CPU->cpu_cyclic;
3066 
3067                 /*
3068                  * For an omni cyclic, we reprogram the cyclic corresponding
3069                  * to the current CPU. Look for it in the list.
3070                  */
3071                 ocpu = idp->cyi_omni_list;
3072                 while (ocpu != NULL) {
3073                         if (ocpu->cyo_cpu == cpu)
3074                                 break;
3075                         ocpu = ocpu->cyo_next;
3076                 }
3077 
3078                 if (ocpu == NULL) {
3079                         /*
3080                          * Didn't find it. This means that CPU offline
3081                          * must have removed it racing with us. So,
3082                          * nothing to do.
3083                          */
3084                         rw_exit(&idp->cyi_lock);
3085 
3086                         kpreempt_enable();
3087 
3088                         return (0);
3089                 }
3090                 ndx = ocpu->cyo_ndx;
3091         } else {
3092                 cpu = idp->cyi_cpu;
3093                 ndx = idp->cyi_ndx;
3094         }
3095 
3096         if (cpu->cyp_cpu == CPU)
3097                 cyclic_reprogram_cyclic(cpu, ndx, expiration);
3098         else
3099                 cyclic_reprogram_here(cpu, ndx, expiration);
3100 
3101         /*
3102          * Allow the cyclic to be moved or removed.
3103          */
3104         rw_exit(&idp->cyi_lock);
3105 
3106         kpreempt_enable();
3107 
3108         return (1);
3109 }
3110 
3111 hrtime_t
3112 cyclic_getres()
3113 {
3114         return (cyclic_resolution);
3115 }
3116 
3117 void
3118 cyclic_init(cyc_backend_t *be, hrtime_t resolution)
3119 {
3120         ASSERT(MUTEX_HELD(&cpu_lock));
3121 
3122         CYC_PTRACE("init", be, resolution);
3123         cyclic_resolution = resolution;
3124 
3125         /*
3126          * Copy the passed cyc_backend into the backend template.  This must
3127          * be done before the CPU can be configured.
3128          */
3129         bcopy(be, &cyclic_backend, sizeof (cyc_backend_t));
3130 
3131         /*
3132          * It's safe to look at the "CPU" pointer without disabling kernel
3133          * preemption; cyclic_init() is called only during startup by the
3134          * cyclic backend.
3135          */
3136         cyclic_configure(CPU);
3137         cyclic_online(CPU);
3138 }
3139 
3140 /*
3141  * It is assumed that cyclic_mp_init() is called some time after cyclic
3142  * init (and therefore, after cpu0 has been initialized).  We grab cpu_lock,
3143  * find the already initialized CPU, and initialize every other CPU with the
3144  * same backend.  Finally, we register a cpu_setup function.
3145  */
3146 void
3147 cyclic_mp_init()
3148 {
3149         cpu_t *c;
3150 
3151         mutex_enter(&cpu_lock);
3152 
3153         c = cpu_list;
3154         do {
3155                 if (c->cpu_cyclic == NULL) {
3156                         cyclic_configure(c);
3157                         cyclic_online(c);
3158                 }
3159         } while ((c = c->cpu_next) != cpu_list);
3160 
3161         register_cpu_setup_func((cpu_setup_func_t *)cyclic_cpu_setup, NULL);
3162         mutex_exit(&cpu_lock);
3163 }
3164 
3165 /*
3166  *  int cyclic_juggle(cpu_t *)
3167  *
3168  *  Overview
3169  *
3170  *    cyclic_juggle() juggles as many cyclics as possible away from the
3171  *    specified CPU; all remaining cyclics on the CPU will either be CPU-
3172  *    or partition-bound.
3173  *
3174  *  Arguments and notes
3175  *
3176  *    The only argument to cyclic_juggle() is the CPU from which cyclics
3177  *    should be juggled.  CPU-bound cyclics are never juggled; partition-bound
3178  *    cyclics are only juggled if the specified CPU is in the P_NOINTR state
3179  *    and there exists a P_ONLINE CPU in the partition.  The cyclic subsystem
3180  *    assures that a cyclic will never fire late or spuriously, even while
3181  *    being juggled.
3182  *
3183  *  Return value
3184  *
3185  *    cyclic_juggle() returns a non-zero value if all cyclics were able to
3186  *    be juggled away from the CPU, and zero if one or more cyclics could
3187  *    not be juggled away.
3188  *
3189  *  Caller's context
3190  *
3191  *    cpu_lock must be held by the caller, and the caller must not be in
3192  *    interrupt context.  The caller may not hold any locks which are also
3193  *    grabbed by any cyclic handler.  While cyclic_juggle() _may_ be called
3194  *    in any context satisfying these constraints, it _must_ be called
3195  *    immediately after clearing CPU_ENABLE (i.e. before dropping cpu_lock).
3196  *    Failure to do so could result in an assertion failure in the cyclic
3197  *    subsystem.
3198  */
3199 int
3200 cyclic_juggle(cpu_t *c)
3201 {
3202         cyc_cpu_t *cpu = c->cpu_cyclic;
3203         cyc_id_t *idp;
3204         int all_juggled = 1;
3205 
3206         CYC_PTRACE1("juggle", c);
3207         ASSERT(MUTEX_HELD(&cpu_lock));
3208 
3209         /*
3210          * We'll go through each cyclic on the CPU, attempting to juggle
3211          * each one elsewhere.
3212          */
3213         for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
3214                 if (idp->cyi_cpu != cpu)
3215                         continue;
3216 
3217                 if (cyclic_juggle_one(idp) == 0) {
3218                         all_juggled = 0;
3219                         continue;
3220                 }
3221 
3222                 ASSERT(idp->cyi_cpu != cpu);
3223         }
3224 
3225         return (all_juggled);
3226 }
3227 
3228 /*
3229  *  int cyclic_offline(cpu_t *)
3230  *
3231  *  Overview
3232  *
3233  *    cyclic_offline() offlines the cyclic subsystem on the specified CPU.
3234  *
3235  *  Arguments and notes
3236  *
3237  *    The only argument to cyclic_offline() is a CPU to offline.
3238  *    cyclic_offline() will attempt to juggle cyclics away from the specified
3239  *    CPU.
3240  *
3241  *  Return value
3242  *
3243  *    cyclic_offline() returns 1 if all cyclics on the CPU were juggled away
3244  *    and the cyclic subsystem on the CPU was successfully offlines.
3245  *    cyclic_offline returns 0 if some cyclics remain, blocking the cyclic
3246  *    offline operation.  All remaining cyclics on the CPU will either be
3247  *    CPU- or partition-bound.
3248  *
3249  *    See the "Arguments and notes" of cyclic_juggle(), below, for more detail
3250  *    on cyclic juggling.
3251  *
3252  *  Caller's context
3253  *
3254  *    The only caller of cyclic_offline() should be the processor management
3255  *    subsystem.  It is expected that the caller of cyclic_offline() will
3256  *    offline the CPU immediately after cyclic_offline() returns success (i.e.
3257  *    before dropping cpu_lock).  Moreover, it is expected that the caller will
3258  *    fail the CPU offline operation if cyclic_offline() returns failure.
3259  */
3260 int
3261 cyclic_offline(cpu_t *c)
3262 {
3263         cyc_cpu_t *cpu = c->cpu_cyclic;
3264         cyc_id_t *idp;
3265 
3266         CYC_PTRACE1("offline", cpu);
3267         ASSERT(MUTEX_HELD(&cpu_lock));
3268 
3269         if (!cyclic_juggle(c))
3270                 return (0);
3271 
3272         /*
3273          * This CPU is headed offline; we need to now stop omnipresent
3274          * cyclic firing on this CPU.
3275          */
3276         for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
3277                 if (idp->cyi_cpu != NULL)
3278                         continue;
3279 
3280                 /*
3281                  * We cannot possibly be offlining the last CPU; cyi_omni_list
3282                  * must be non-NULL.
3283                  */
3284                 ASSERT(idp->cyi_omni_list != NULL);
3285                 cyclic_omni_stop(idp, cpu);
3286         }
3287 
3288         ASSERT(cpu->cyp_state == CYS_ONLINE);
3289         cpu->cyp_state = CYS_OFFLINE;
3290 
3291         return (1);
3292 }
3293 
3294 /*
3295  *  void cyclic_online(cpu_t *)
3296  *
3297  *  Overview
3298  *
3299  *    cyclic_online() onlines a CPU previously offlined with cyclic_offline().
3300  *
3301  *  Arguments and notes
3302  *
3303  *    cyclic_online()'s only argument is a CPU to online.  The specified
3304  *    CPU must have been previously offlined with cyclic_offline().  After
3305  *    cyclic_online() returns, the specified CPU will be eligible to execute
3306  *    cyclics.
3307  *
3308  *  Return value
3309  *
3310  *    None; cyclic_online() always succeeds.
3311  *
3312  *  Caller's context
3313  *
3314  *    cyclic_online() should only be called by the processor management
3315  *    subsystem; cpu_lock must be held.
3316  */
3317 void
3318 cyclic_online(cpu_t *c)
3319 {
3320         cyc_cpu_t *cpu = c->cpu_cyclic;
3321         cyc_id_t *idp;
3322 
3323         CYC_PTRACE1("online", cpu);
3324         ASSERT(c->cpu_flags & CPU_ENABLE);
3325         ASSERT(MUTEX_HELD(&cpu_lock));
3326         ASSERT(cpu->cyp_state == CYS_OFFLINE);
3327 
3328         cpu->cyp_state = CYS_ONLINE;
3329 
3330         /*
3331          * Now that this CPU is open for business, we need to start firing
3332          * all omnipresent cyclics on it.
3333          */
3334         for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
3335                 if (idp->cyi_cpu != NULL)
3336                         continue;
3337 
3338                 cyclic_omni_start(idp, cpu);
3339         }
3340 }
3341 
3342 /*
3343  *  void cyclic_move_in(cpu_t *)
3344  *
3345  *  Overview
3346  *
3347  *    cyclic_move_in() is called by the CPU partition code immediately after
3348  *    the specified CPU has moved into a new partition.
3349  *
3350  *  Arguments and notes
3351  *
3352  *    The only argument to cyclic_move_in() is a CPU which has moved into a
3353  *    new partition.  If the specified CPU is P_ONLINE, and every other
3354  *    CPU in the specified CPU's new partition is P_NOINTR, cyclic_move_in()
3355  *    will juggle all partition-bound, CPU-unbound cyclics to the specified
3356  *    CPU.
3357  *
3358  *  Return value
3359  *
3360  *    None; cyclic_move_in() always succeeds.
3361  *
3362  *  Caller's context
3363  *
3364  *    cyclic_move_in() should _only_ be called immediately after a CPU has
3365  *    moved into a new partition, with cpu_lock held.  As with other calls
3366  *    into the cyclic subsystem, no lock may be held which is also grabbed
3367  *    by any cyclic handler.
3368  */
3369 void
3370 cyclic_move_in(cpu_t *d)
3371 {
3372         cyc_id_t *idp;
3373         cyc_cpu_t *dest = d->cpu_cyclic;
3374         cyclic_t *cyclic;
3375         cpupart_t *part = d->cpu_part;
3376 
3377         CYC_PTRACE("move-in", dest, part);
3378         ASSERT(MUTEX_HELD(&cpu_lock));
3379 
3380         /*
3381          * Look for CYF_PART_BOUND cyclics in the new partition.  If
3382          * we find one, check to see if it is currently on a CPU which has
3383          * interrupts disabled.  If it is (and if this CPU currently has
3384          * interrupts enabled), we'll juggle those cyclics over here.
3385          */
3386         if (!(d->cpu_flags & CPU_ENABLE)) {
3387                 CYC_PTRACE1("move-in-none", dest);
3388                 return;
3389         }
3390 
3391         for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
3392                 cyc_cpu_t *cpu = idp->cyi_cpu;
3393                 cpu_t *c;
3394 
3395                 /*
3396                  * Omnipresent cyclics are exempt from juggling.
3397                  */
3398                 if (cpu == NULL)
3399                         continue;
3400 
3401                 c = cpu->cyp_cpu;
3402 
3403                 if (c->cpu_part != part || (c->cpu_flags & CPU_ENABLE))
3404                         continue;
3405 
3406                 cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];
3407 
3408                 if (cyclic->cy_flags & CYF_CPU_BOUND)
3409                         continue;
3410 
3411                 /*
3412                  * We know that this cyclic is bound to its processor set
3413                  * (otherwise, it would not be on a CPU with interrupts
3414                  * disabled); juggle it to our CPU.
3415                  */
3416                 ASSERT(cyclic->cy_flags & CYF_PART_BOUND);
3417                 cyclic_juggle_one_to(idp, dest);
3418         }
3419 
3420         CYC_PTRACE1("move-in-done", dest);
3421 }
3422 
3423 /*
3424  *  int cyclic_move_out(cpu_t *)
3425  *
3426  *  Overview
3427  *
3428  *    cyclic_move_out() is called by the CPU partition code immediately before
3429  *    the specified CPU is to move out of its partition.
3430  *
3431  *  Arguments and notes
3432  *
3433  *    The only argument to cyclic_move_out() is a CPU which is to move out of
3434  *    its partition.
3435  *
3436  *    cyclic_move_out() will attempt to juggle away all partition-bound
3437  *    cyclics.  If the specified CPU is the last CPU in a partition with
3438  *    partition-bound cyclics, cyclic_move_out() will fail.  If there exists
3439  *    a partition-bound cyclic which is CPU-bound to the specified CPU,
3440  *    cyclic_move_out() will fail.
3441  *
3442  *    Note that cyclic_move_out() will _only_ attempt to juggle away
3443  *    partition-bound cyclics; CPU-bound cyclics which are not partition-bound
3444  *    and unbound cyclics are not affected by changing the partition
3445  *    affiliation of the CPU.
3446  *
3447  *  Return value
3448  *
3449  *    cyclic_move_out() returns 1 if all partition-bound cyclics on the CPU
3450  *    were juggled away; 0 if some cyclics remain.
3451  *
3452  *  Caller's context
3453  *
3454  *    cyclic_move_out() should _only_ be called immediately before a CPU has
3455  *    moved out of its partition, with cpu_lock held.  It is expected that
3456  *    the caller of cyclic_move_out() will change the processor set affiliation
3457  *    of the specified CPU immediately after cyclic_move_out() returns
3458  *    success (i.e. before dropping cpu_lock).  Moreover, it is expected that
3459  *    the caller will fail the CPU repartitioning operation if cyclic_move_out()
3460  *    returns failure.  As with other calls into the cyclic subsystem, no lock
3461  *    may be held which is also grabbed by any cyclic handler.
3462  */
3463 int
3464 cyclic_move_out(cpu_t *c)
3465 {
3466         cyc_id_t *idp;
3467         cyc_cpu_t *cpu = c->cpu_cyclic, *dest;
3468         cyclic_t *cyclic, *cyclics = cpu->cyp_cyclics;
3469         cpupart_t *part = c->cpu_part;
3470 
3471         CYC_PTRACE1("move-out", cpu);
3472         ASSERT(MUTEX_HELD(&cpu_lock));
3473 
3474         /*
3475          * If there are any CYF_PART_BOUND cyclics on this CPU, we need
3476          * to try to juggle them away.
3477          */
3478         for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
3479 
3480                 if (idp->cyi_cpu != cpu)
3481                         continue;
3482 
3483                 cyclic = &cyclics[idp->cyi_ndx];
3484 
3485                 if (!(cyclic->cy_flags & CYF_PART_BOUND))
3486                         continue;
3487 
3488                 dest = cyclic_pick_cpu(part, c, c, cyclic->cy_flags);
3489 
3490                 if (dest == NULL) {
3491                         /*
3492                          * We can't juggle this cyclic; we need to return
3493                          * failure (we won't bother trying to juggle away
3494                          * other cyclics).
3495                          */
3496                         CYC_PTRACE("move-out-fail", cpu, idp);
3497                         return (0);
3498                 }
3499                 cyclic_juggle_one_to(idp, dest);
3500         }
3501 
3502         CYC_PTRACE1("move-out-done", cpu);
3503         return (1);
3504 }
3505 
3506 /*
3507  *  void cyclic_suspend()
3508  *
3509  *  Overview
3510  *
3511  *    cyclic_suspend() suspends all cyclic activity throughout the cyclic
3512  *    subsystem.  It should be called only by subsystems which are attempting
3513  *    to suspend the entire system (e.g. checkpoint/resume, dynamic
3514  *    reconfiguration).
3515  *
3516  *  Arguments and notes
3517  *
3518  *    cyclic_suspend() takes no arguments.  Each CPU with an active cyclic
3519  *    disables its backend (offline CPUs disable their backends as part of
3520  *    the cyclic_offline() operation), thereby disabling future CY_HIGH_LEVEL
3521  *    interrupts.
3522  *
3523  *    Note that disabling CY_HIGH_LEVEL interrupts does not completely preclude
3524  *    cyclic handlers from being called after cyclic_suspend() returns:  if a
3525  *    CY_LOCK_LEVEL or CY_LOW_LEVEL interrupt thread was blocked at the time
3526  *    of cyclic_suspend(), cyclic handlers at its level may continue to be
3527  *    called after the interrupt thread becomes unblocked.  The
3528  *    post-cyclic_suspend() activity is bounded by the pend count on all
3529  *    cyclics at the time of cyclic_suspend().  Callers concerned with more
3530  *    than simply disabling future CY_HIGH_LEVEL interrupts must check for
3531  *    this condition.
3532  *
3533  *    On most platforms, timestamps from gethrtime() and gethrestime() are not
3534  *    guaranteed to monotonically increase between cyclic_suspend() and
3535  *    cyclic_resume().  However, timestamps are guaranteed to monotonically
3536  *    increase across the entire cyclic_suspend()/cyclic_resume() operation.
3537  *    That is, every timestamp obtained before cyclic_suspend() will be less
3538  *    than every timestamp obtained after cyclic_resume().
3539  *
3540  *  Return value
3541  *
3542  *    None; cyclic_suspend() always succeeds.
3543  *
3544  *  Caller's context
3545  *
3546  *    The cyclic subsystem must be configured on every valid CPU;
3547  *    cyclic_suspend() may not be called during boot or during dynamic
3548  *    reconfiguration.  Additionally, cpu_lock must be held, and the caller
3549  *    cannot be in high-level interrupt context.  However, unlike most other
3550  *    cyclic entry points, cyclic_suspend() may be called with locks held
3551  *    which are also acquired by CY_LOCK_LEVEL or CY_LOW_LEVEL cyclic
3552  *    handlers.
3553  */
3554 void
3555 cyclic_suspend()
3556 {
3557         cpu_t *c;
3558         cyc_cpu_t *cpu;
3559         cyc_xcallarg_t arg;
3560         cyc_backend_t *be;
3561 
3562         CYC_PTRACE0("suspend");
3563         ASSERT(MUTEX_HELD(&cpu_lock));
3564         c = cpu_list;
3565 
3566         do {
3567                 cpu = c->cpu_cyclic;
3568                 be = cpu->cyp_backend;
3569                 arg.cyx_cpu = cpu;
3570 
3571                 be->cyb_xcall(be->cyb_arg, c,
3572                     (cyc_func_t)cyclic_suspend_xcall, &arg);
3573         } while ((c = c->cpu_next) != cpu_list);
3574 }
3575 
3576 /*
3577  *  void cyclic_resume()
3578  *
3579  *    cyclic_resume() resumes all cyclic activity throughout the cyclic
3580  *    subsystem.  It should be called only by system-suspending subsystems.
3581  *
3582  *  Arguments and notes
3583  *
3584  *    cyclic_resume() takes no arguments.  Each CPU with an active cyclic
3585  *    reenables and reprograms its backend (offline CPUs are not reenabled).
3586  *    On most platforms, timestamps from gethrtime() and gethrestime() are not
3587  *    guaranteed to monotonically increase between cyclic_suspend() and
3588  *    cyclic_resume().  However, timestamps are guaranteed to monotonically
3589  *    increase across the entire cyclic_suspend()/cyclic_resume() operation.
3590  *    That is, every timestamp obtained before cyclic_suspend() will be less
3591  *    than every timestamp obtained after cyclic_resume().
3592  *
3593  *  Return value
3594  *
3595  *    None; cyclic_resume() always succeeds.
3596  *
3597  *  Caller's context
3598  *
3599  *    The cyclic subsystem must be configured on every valid CPU;
3600  *    cyclic_resume() may not be called during boot or during dynamic
3601  *    reconfiguration.  Additionally, cpu_lock must be held, and the caller
3602  *    cannot be in high-level interrupt context.  However, unlike most other
3603  *    cyclic entry points, cyclic_resume() may be called with locks held which
3604  *    are also acquired by CY_LOCK_LEVEL or CY_LOW_LEVEL cyclic handlers.
3605  */
3606 void
3607 cyclic_resume()
3608 {
3609         cpu_t *c;
3610         cyc_cpu_t *cpu;
3611         cyc_xcallarg_t arg;
3612         cyc_backend_t *be;
3613 
3614         CYC_PTRACE0("resume");
3615         ASSERT(MUTEX_HELD(&cpu_lock));
3616 
3617         c = cpu_list;
3618 
3619         do {
3620                 cpu = c->cpu_cyclic;
3621                 be = cpu->cyp_backend;
3622                 arg.cyx_cpu = cpu;
3623 
3624                 be->cyb_xcall(be->cyb_arg, c,
3625                     (cyc_func_t)cyclic_resume_xcall, &arg);
3626         } while ((c = c->cpu_next) != cpu_list);
3627 }