xref: /illumos-gate/usr/src/uts/common/os/cyclic.c (revision 5422785d352a2bb398daceab3d1898a8aa64d006)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * Copyright (c) 2012, Joyent Inc. All rights reserved.
 */

/*
 *  The Cyclic Subsystem
 *  --------------------
 *
 *  Prehistory
 *
 *  Historically, most computer architectures have specified interval-based
 *  timer parts (e.g. SPARCstation's counter/timer; Intel's i8254).  While
 *  these parts deal in relative (i.e. not absolute) time values, they are
 *  typically used by the operating system to implement the abstraction of
 *  absolute time.  As a result, these parts cannot typically be reprogrammed
 *  without introducing error in the system's notion of time.
 *
 *  Starting in about 1994, chip architectures began specifying high resolution
 *  timestamp registers.  As of this writing (1999), all major chip families
 *  (UltraSPARC, PentiumPro, MIPS, PowerPC, Alpha) have high resolution
 *  timestamp registers, and two (UltraSPARC and MIPS) have added the capacity
 *  to interrupt based on timestamp values.  These timestamp-compare registers
 *  present a time-based interrupt source which can be reprogrammed arbitrarily
 *  often without introducing error.  Given the low cost of implementing such a
 *  timestamp-compare register (and the tangible benefit of eliminating
 *  discrete timer parts), it is reasonable to expect that future chip
 *  architectures will adopt this feature.
 *
 *  The cyclic subsystem has been designed to take advantage of chip
 *  architectures with the capacity to interrupt based on absolute, high
 *  resolution values of time.
 *
 *  Subsystem Overview
 *
 *  The cyclic subsystem is a low-level kernel subsystem designed to provide
 *  arbitrarily high resolution, per-CPU interval timers (to avoid colliding
 *  with existing terms, we dub such an interval timer a "cyclic").  Cyclics
 *  can be specified to fire at high, lock or low interrupt level, and may be
 *  optionally bound to a CPU or a CPU partition.  A cyclic's CPU or CPU
 *  partition binding may be changed dynamically; the cyclic will be "juggled"
 *  to a CPU which satisfies the new binding.  Alternatively, a cyclic may
 *  be specified to be "omnipresent", denoting firing on all online CPUs.
 *
 *  Cyclic Subsystem Interface Overview
 *  -----------------------------------
 *
 *  The cyclic subsystem has interfaces with the kernel at-large, with other
 *  kernel subsystems (e.g. the processor management subsystem, the checkpoint
 *  resume subsystem) and with the platform (the cyclic backend).  Each
 *  of these interfaces is given a brief synopsis here, and is described
 *  in full above the interface's implementation.
 *
 *  The following diagram displays the cyclic subsystem's interfaces to
 *  other kernel components.  The arrows denote a "calls" relationship, with
 *  the large arrow indicating the cyclic subsystem's consumer interface.
 *  Each arrow is labeled with the section in which the corresponding
 *  interface is described.
 *
 *           Kernel at-large consumers
 *           -----------++------------
 *                      ||
 *                      ||
 *                     _||_
 *                     \  /
 *                      \/
 *            +---------------------+
 *            |                     |
 *            |  Cyclic subsystem   |<-----------  Other kernel subsystems
 *            |                     |
 *            +---------------------+
 *                   ^       |
 *                   |       |
 *                   |       |
 *                   |       v
 *            +---------------------+
 *            |                     |
 *            |   Cyclic backend    |
 *            | (platform specific) |
 *            |                     |
 *            +---------------------+
 *
 *
 *  Kernel At-Large Interfaces
 *
 *      cyclic_add()         <-- Creates a cyclic
 *      cyclic_add_omni()    <-- Creates an omnipresent cyclic
 *      cyclic_remove()      <-- Removes a cyclic
 *      cyclic_bind()        <-- Change a cyclic's CPU or partition binding
 *      cyclic_reprogram()   <-- Reprogram a cyclic's expiration
 *
 *  Inter-subsystem Interfaces
 *
 *      cyclic_juggle()      <-- Juggles cyclics away from a CPU
 *      cyclic_offline()     <-- Offlines cyclic operation on a CPU
 *      cyclic_online()      <-- Reenables operation on an offlined CPU
 *      cyclic_move_in()     <-- Notifies subsystem of change in CPU partition
 *      cyclic_move_out()    <-- Notifies subsystem of change in CPU partition
 *      cyclic_suspend()     <-- Suspends the cyclic subsystem on all CPUs
 *      cyclic_resume()      <-- Resumes the cyclic subsystem on all CPUs
 *
 *  Backend Interfaces
 *
 *      cyclic_init()        <-- Initializes the cyclic subsystem
 *      cyclic_fire()        <-- CY_HIGH_LEVEL interrupt entry point
 *      cyclic_softint()     <-- CY_LOCK/LOW_LEVEL soft interrupt entry point
 *
 *  The backend-supplied interfaces (through the cyc_backend structure) are
 *  documented in detail in <sys/cyclic_impl.h>
 *
 *
 *  Cyclic Subsystem Implementation Overview
 *  ----------------------------------------
 *
 *  The cyclic subsystem is designed to minimize interference between cyclics
 *  on different CPUs.  Thus, all of the cyclic subsystem's data structures
 *  hang off of a per-CPU structure, cyc_cpu.
 *
 *  Each cyc_cpu has a power-of-two sized array of cyclic structures (the
 *  cyp_cyclics member of the cyc_cpu structure).  If cyclic_add() is called
 *  and there does not exist a free slot in the cyp_cyclics array, the size of
 *  the array will be doubled.  The array will never shrink.  Cyclics are
 *  referred to by their index in the cyp_cyclics array, which is of type
 *  cyc_index_t.
 *
 *  The cyclics are kept sorted by expiration time in the cyc_cpu's heap.  The
 *  heap is keyed by cyclic expiration time, with parents expiring earlier
 *  than their children.
 *
 *  Heap Management
 *
 *  The heap is managed primarily by cyclic_fire().  Upon entry, cyclic_fire()
 *  compares the root cyclic's expiration time to the current time.  If the
 *  expiration time is in the past, cyclic_expire() is called on the root
 *  cyclic.  Upon return from cyclic_expire(), the cyclic's new expiration time
 *  is derived by adding its interval to its old expiration time, and a
 *  downheap operation is performed.  After the downheap, cyclic_fire()
 *  examines the (potentially changed) root cyclic, repeating the
 *  cyclic_expire()/add interval/cyclic_downheap() sequence until the root
 *  cyclic has an expiration time in the future.  This expiration time
 *  (guaranteed to be the earliest in the heap) is then communicated to the
 *  backend via cyb_reprogram.  Optimal backends will next call cyclic_fire()
 *  shortly after the root cyclic's expiration time.
 *
 *  To allow efficient, deterministic downheap operations, we implement the
 *  heap as an array (the cyp_heap member of the cyc_cpu structure), with each
 *  element containing an index into the CPU's cyp_cyclics array.
 *
 *  The heap is laid out in the array according to the following:
 *
 *   1.  The root of the heap is always in the 0th element of the heap array
 *   2.  The left and right children of the nth element are element
 *       (((n + 1) << 1) - 1) and element ((n + 1) << 1), respectively.
 *
 *  This layout is standard (see, e.g., Cormen's "Algorithms"); the proof
 *  that these constraints correctly lay out a heap (or indeed, any binary
 *  tree) is trivial and left to the reader.
 *
 *  To see the heap by example, assume our cyclics array has the following
 *  members (at time t):
 *
 *            cy_handler            cy_level      cy_expire
 *            ---------------------------------------------
 *     [ 0]   clock()                   LOCK     t+10000000
 *     [ 1]   deadman()                 HIGH   t+1000000000
 *     [ 2]   clock_highres_fire()       LOW          t+100
 *     [ 3]   clock_highres_fire()       LOW         t+1000
 *     [ 4]   clock_highres_fire()       LOW          t+500
 *     [ 5]   (free)                      --             --
 *     [ 6]   (free)                      --             --
 *     [ 7]   (free)                      --             --
 *
 *  The heap array could be:
 *
 *                [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 *              +-----+-----+-----+-----+-----+-----+-----+-----+
 *              |     |     |     |     |     |     |     |     |
 *              |  2  |  3  |  4  |  0  |  1  |  x  |  x  |  x  |
 *              |     |     |     |     |     |     |     |     |
 *              +-----+-----+-----+-----+-----+-----+-----+-----+
 *
 *  Graphically, this array corresponds to the following (excuse the ASCII art):
 *
 *                                       2
 *                                       |
 *                    +------------------+------------------+
 *                    3                                     4
 *                    |
 *          +---------+--------+
 *          0                  1
 *
 *  Note that the heap is laid out by layer:  all nodes at a given depth are
 *  stored in consecutive elements of the array.  Moreover, layers of
 *  consecutive depths are in adjacent element ranges.  This property
 *  guarantees high locality of reference during downheap operations.
 *  Specifically, we are guaranteed that we can downheap to a depth of
 *
 *      lg (cache_line_size / sizeof (cyc_index_t))
 *
 *  nodes with at most one cache miss.  On UltraSPARC (64 byte e-cache line
 *  size), this corresponds to a depth of four nodes.  Thus, if there are
 *  fewer than sixteen cyclics in the heap, downheaps on UltraSPARC miss at
 *  most once in the e-cache.
 *
 *  Downheaps are required to compare siblings as they proceed down the
 *  heap.  For downheaps proceeding beyond the one-cache-miss depth, every
 *  access to a left child could potentially miss in the cache.  However,
 *  if we assume
 *
 *      (cache_line_size / sizeof (cyc_index_t)) > 2,
 *
 *  then all siblings are guaranteed to be on the same cache line.  Thus, the
 *  miss on the left child will guarantee a hit on the right child; downheaps
 *  will incur at most one cache miss per layer beyond the one-cache-miss
 *  depth.  The total number of cache misses for heap management during a
 *  downheap operation is thus bounded by
 *
 *      lg (n) - lg (cache_line_size / sizeof (cyc_index_t))
 *
 *  Traditional pointer-based heaps are implemented without regard to
 *  locality.  Downheaps can thus incur two cache misses per layer (one for
 *  each child), but at most one cache miss at the root.  This yields a bound
 *  of
 *
 *      2 * lg (n) - 1
 *
 *  on the total cache misses.
 *
 *  This difference may seem theoretically trivial (the difference is, after
 *  all, constant), but can become substantial in practice -- especially for
 *  caches with very large cache lines and high miss penalties (e.g. TLBs).
 *
 *  Heaps must always be full, balanced trees.  Heap management must therefore
 *  track the next point-of-insertion into the heap.  In pointer-based heaps,
 *  recomputing this point takes O(lg (n)).  Given the layout of the
 *  array-based implementation, however, the next point-of-insertion is
 *  always:
 *
 *      heap[number_of_elements]
 *
 *  We exploit this property by implementing the free-list in the usused
 *  heap elements.  Heap insertion, therefore, consists only of filling in
 *  the cyclic at cyp_cyclics[cyp_heap[number_of_elements]], incrementing
 *  the number of elements, and performing an upheap.  Heap deletion consists
 *  of decrementing the number of elements, swapping the to-be-deleted element
 *  with the element at cyp_heap[number_of_elements], and downheaping.
 *
 *  Filling in more details in our earlier example:
 *
 *                                               +--- free list head
 *                                               |
 *                                               V
 *
 *                [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 *              +-----+-----+-----+-----+-----+-----+-----+-----+
 *              |     |     |     |     |     |     |     |     |
 *              |  2  |  3  |  4  |  0  |  1  |  5  |  6  |  7  |
 *              |     |     |     |     |     |     |     |     |
 *              +-----+-----+-----+-----+-----+-----+-----+-----+
 *
 *  To insert into this heap, we would just need to fill in the cyclic at
 *  cyp_cyclics[5], bump the number of elements (from 5 to 6) and perform
 *  an upheap.
 *
 *  If we wanted to remove, say, cyp_cyclics[3], we would first scan for it
 *  in the cyp_heap, and discover it at cyp_heap[1].  We would then decrement
 *  the number of elements (from 5 to 4), swap cyp_heap[1] with cyp_heap[4],
 *  and perform a downheap from cyp_heap[1].  The linear scan is required
 *  because the cyclic does not keep a backpointer into the heap.  This makes
 *  heap manipulation (e.g. downheaps) faster at the expense of removal
 *  operations.
 *
 *  Expiry processing
 *
 *  As alluded to above, cyclic_expire() is called by cyclic_fire() at
 *  CY_HIGH_LEVEL to expire a cyclic.  Cyclic subsystem consumers are
 *  guaranteed that for an arbitrary time t in the future, their cyclic
 *  handler will have been called (t - cyt_when) / cyt_interval times.  Thus,
 *  there must be a one-to-one mapping between a cyclic's expiration at
 *  CY_HIGH_LEVEL and its execution at the desired level (either CY_HIGH_LEVEL,
 *  CY_LOCK_LEVEL or CY_LOW_LEVEL).
 *
 *  For CY_HIGH_LEVEL cyclics, this is trivial; cyclic_expire() simply needs
 *  to call the handler.
 *
 *  For CY_LOCK_LEVEL and CY_LOW_LEVEL cyclics, however, there exists a
 *  potential disconnect:  if the CPU is at an interrupt level less than
 *  CY_HIGH_LEVEL but greater than the level of a cyclic for a period of
 *  time longer than twice the cyclic's interval, the cyclic will be expired
 *  twice before it can be handled.
 *
 *  To maintain the one-to-one mapping, we track the difference between the
 *  number of times a cyclic has been expired and the number of times it's
 *  been handled in a "pending count" (the cy_pend field of the cyclic
 *  structure).  cyclic_expire() thus increments the cy_pend count for the
 *  expired cyclic and posts a soft interrupt at the desired level.  In the
 *  cyclic subsystem's soft interrupt handler, cyclic_softint(), we repeatedly
 *  call the cyclic handler and decrement cy_pend until we have decremented
 *  cy_pend to zero.
 *
 *  The Producer/Consumer Buffer
 *
 *  If we wish to avoid a linear scan of the cyclics array at soft interrupt
 *  level, cyclic_softint() must be able to quickly determine which cyclics
 *  have a non-zero cy_pend count.  We thus introduce a per-soft interrupt
 *  level producer/consumer buffer shared with CY_HIGH_LEVEL.  These buffers
 *  are encapsulated in the cyc_pcbuffer structure, and, like cyp_heap, are
 *  implemented as cyc_index_t arrays (the cypc_buf member of the cyc_pcbuffer
 *  structure).
 *
 *  The producer (cyclic_expire() running at CY_HIGH_LEVEL) enqueues a cyclic
 *  by storing the cyclic's index to cypc_buf[cypc_prodndx] and incrementing
 *  cypc_prodndx.  The consumer (cyclic_softint() running at either
 *  CY_LOCK_LEVEL or CY_LOW_LEVEL) dequeues a cyclic by loading from
 *  cypc_buf[cypc_consndx] and bumping cypc_consndx.  The buffer is empty when
 *  cypc_prodndx == cypc_consndx.
 *
 *  To bound the size of the producer/consumer buffer, cyclic_expire() only
 *  enqueues a cyclic if its cy_pend was zero (if the cyclic's cy_pend is
 *  non-zero, cyclic_expire() only bumps cy_pend).  Symmetrically,
 *  cyclic_softint() only consumes a cyclic after it has decremented the
 *  cy_pend count to zero.
 *
 *  Returning to our example, here is what the CY_LOW_LEVEL producer/consumer
 *  buffer might look like:
 *
 *     cypc_consndx ---+                 +--- cypc_prodndx
 *                     |                 |
 *                     V                 V
 *
 *        [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
 *      +-----+-----+-----+-----+-----+-----+-----+-----+
 *      |     |     |     |     |     |     |     |     |
 *      |  x  |  x  |  3  |  2  |  4  |  x  |  x  |  x  |   <== cypc_buf
 *      |     |     |  .  |  .  |  .  |     |     |     |
 *      +-----+-----+- | -+- | -+- | -+-----+-----+-----+
 *                     |     |     |
 *                     |     |     |              cy_pend  cy_handler
 *                     |     |     |          -------------------------
 *                     |     |     |          [ 0]      1  clock()
 *                     |     |     |          [ 1]      0  deadman()
 *                     |     +---- | -------> [ 2]      3  clock_highres_fire()
 *                     +---------- | -------> [ 3]      1  clock_highres_fire()
 *                                 +--------> [ 4]      1  clock_highres_fire()
 *                                            [ 5]      -  (free)
 *                                            [ 6]      -  (free)
 *                                            [ 7]      -  (free)
 *
 *  In particular, note that clock()'s cy_pend is 1 but that it is _not_ in
 *  this producer/consumer buffer; it would be enqueued in the CY_LOCK_LEVEL
 *  producer/consumer buffer.
 *
 *  Locking
 *
 *  Traditionally, access to per-CPU data structures shared between
 *  interrupt levels is serialized by manipulating programmable interrupt
 *  level:  readers and writers are required to raise their interrupt level
 *  to that of the highest level writer.
 *
 *  For the producer/consumer buffers (shared between cyclic_fire()/
 *  cyclic_expire() executing at CY_HIGH_LEVEL and cyclic_softint() executing
 *  at one of CY_LOCK_LEVEL or CY_LOW_LEVEL), forcing cyclic_softint() to raise
 *  programmable interrupt level is undesirable:  aside from the additional
 *  latency incurred by manipulating interrupt level in the hot cy_pend
 *  processing path, this would create the potential for soft level cy_pend
 *  processing to delay CY_HIGH_LEVEL firing and expiry processing.
 *  CY_LOCK/LOW_LEVEL cyclics could thereby induce jitter in CY_HIGH_LEVEL
 *  cyclics.
 *
 *  To minimize jitter, then, we would like the cyclic_fire()/cyclic_expire()
 *  and cyclic_softint() code paths to be lock-free.
 *
 *  For cyclic_fire()/cyclic_expire(), lock-free execution is straightforward:
 *  because these routines execute at a higher interrupt level than
 *  cyclic_softint(), their actions on the producer/consumer buffer appear
 *  atomic.  In particular, the increment of cy_pend appears to occur
 *  atomically with the increment of cypc_prodndx.
 *
 *  For cyclic_softint(), however, lock-free execution requires more delicacy.
 *  When cyclic_softint() discovers a cyclic in the producer/consumer buffer,
 *  it calls the cyclic's handler and attempts to atomically decrement the
 *  cy_pend count with a compare&swap operation.
 *
 *  If the compare&swap operation succeeds, cyclic_softint() behaves
 *  conditionally based on the value it atomically wrote to cy_pend:
 *
 *     - If the cy_pend was decremented to 0, the cyclic has been consumed;
 *       cyclic_softint() increments the cypc_consndx and checks for more
 *       enqueued work.
 *
 *     - If the count was decremented to a non-zero value, there is more work
 *       to be done on the cyclic; cyclic_softint() calls the cyclic handler
 *       and repeats the atomic decrement process.
 *
 *  If the compare&swap operation fails, cyclic_softint() knows that
 *  cyclic_expire() has intervened and bumped the cy_pend count (resizes
 *  and removals complicate this, however -- see the sections on their
 *  operation, below).  cyclic_softint() thus reloads cy_pend, and re-attempts
 *  the atomic decrement.
 *
 *  Recall that we bound the size of the producer/consumer buffer by
 *  having cyclic_expire() only enqueue the specified cyclic if its
 *  cy_pend count is zero; this assures that each cyclic is enqueued at
 *  most once.  This leads to a critical constraint on cyclic_softint(),
 *  however:  after the compare&swap operation which successfully decrements
 *  cy_pend to zero, cyclic_softint() must _not_ re-examine the consumed
 *  cyclic.  In part to obey this constraint, cyclic_softint() calls the
 *  cyclic handler before decrementing cy_pend.
 *
 *  Resizing
 *
 *  All of the discussion thus far has assumed a static number of cyclics.
 *  Obviously, static limitations are not practical; we need the capacity
 *  to resize our data structures dynamically.
 *
 *  We resize our data structures lazily, and only on a per-CPU basis.
 *  The size of the data structures always doubles and never shrinks.  We
 *  serialize adds (and thus resizes) on cpu_lock; we never need to deal
 *  with concurrent resizes.  Resizes should be rare; they may induce jitter
 *  on the CPU being resized, but should not affect cyclic operation on other
 *  CPUs.  Pending cyclics may not be dropped during a resize operation.
 *
 *  Three key cyc_cpu data structures need to be resized:  the cyclics array,
 *  the heap array and the producer/consumer buffers.  Resizing the first two
 *  is relatively straightforward:
 *
 *    1.  The new, larger arrays are allocated in cyclic_expand() (called
 *        from cyclic_add()).
 *    2.  cyclic_expand() cross calls cyclic_expand_xcall() on the CPU
 *        undergoing the resize.
 *    3.  cyclic_expand_xcall() raises interrupt level to CY_HIGH_LEVEL
 *    4.  The contents of the old arrays are copied into the new arrays.
 *    5.  The old cyclics array is bzero()'d
 *    6.  The pointers are updated.
 *
 *  The producer/consumer buffer is dicier:  cyclic_expand_xcall() may have
 *  interrupted cyclic_softint() in the middle of consumption. To resize the
 *  producer/consumer buffer, we implement up to two buffers per soft interrupt
 *  level:  a hard buffer (the buffer being produced into by cyclic_expire())
 *  and a soft buffer (the buffer from which cyclic_softint() is consuming).
 *  During normal operation, the hard buffer and soft buffer point to the
 *  same underlying producer/consumer buffer.
 *
 *  During a resize, however, cyclic_expand_xcall() changes the hard buffer
 *  to point to the new, larger producer/consumer buffer; all future
 *  cyclic_expire()'s will produce into the new buffer.  cyclic_expand_xcall()
 *  then posts a CY_LOCK_LEVEL soft interrupt, landing in cyclic_softint().
 *
 *  As under normal operation, cyclic_softint() will consume cyclics from
 *  its soft buffer.  After the soft buffer is drained, however,
 *  cyclic_softint() will see that the hard buffer has changed.  At that time,
 *  cyclic_softint() will change its soft buffer to point to the hard buffer,
 *  and repeat the producer/consumer buffer draining procedure.
 *
 *  After the new buffer is drained, cyclic_softint() will determine if both
 *  soft levels have seen their new producer/consumer buffer.  If both have,
 *  cyclic_softint() will post on the semaphore cyp_modify_wait.  If not, a
 *  soft interrupt will be generated for the remaining level.
 *
 *  cyclic_expand() blocks on the cyp_modify_wait semaphore (a semaphore is
 *  used instead of a condition variable because of the race between the
 *  sema_p() in cyclic_expand() and the sema_v() in cyclic_softint()).  This
 *  allows cyclic_expand() to know when the resize operation is complete;
 *  all of the old buffers (the heap, the cyclics array and the producer/
 *  consumer buffers) can be freed.
 *
 *  A final caveat on resizing:  we described step (5) in the
 *  cyclic_expand_xcall() procedure without providing any motivation.  This
 *  step addresses the problem of a cyclic_softint() attempting to decrement
 *  a cy_pend count while interrupted by a cyclic_expand_xcall().  Because
 *  cyclic_softint() has already called the handler by the time cy_pend is
 *  decremented, we want to assure that it doesn't decrement a cy_pend
 *  count in the old cyclics array.  By zeroing the old cyclics array in
 *  cyclic_expand_xcall(), we are zeroing out every cy_pend count; when
 *  cyclic_softint() attempts to compare&swap on the cy_pend count, it will
 *  fail and recognize that the count has been zeroed.  cyclic_softint() will
 *  update its stale copy of the cyp_cyclics pointer, re-read the cy_pend
 *  count from the new cyclics array, and re-attempt the compare&swap.
 *
 *  Removals
 *
 *  Cyclic removals should be rare.  To simplify the implementation (and to
 *  allow optimization for the cyclic_fire()/cyclic_expire()/cyclic_softint()
 *  path), we force removals and adds to serialize on cpu_lock.
 *
 *  Cyclic removal is complicated by a guarantee made to the consumer of
 *  the cyclic subsystem:  after cyclic_remove() returns, the cyclic handler
 *  has returned and will never again be called.
 *
 *  Here is the procedure for cyclic removal:
 *
 *    1.  cyclic_remove() calls cyclic_remove_xcall() on the CPU undergoing
 *        the removal.
 *    2.  cyclic_remove_xcall() raises interrupt level to CY_HIGH_LEVEL
 *    3.  The current expiration time for the removed cyclic is recorded.
 *    4.  If the cy_pend count on the removed cyclic is non-zero, it
 *        is copied into cyp_rpend and subsequently zeroed.
 *    5.  The cyclic is removed from the heap
 *    6.  If the root of the heap has changed, the backend is reprogrammed.
 *    7.  If the cy_pend count was non-zero cyclic_remove() blocks on the
 *        cyp_modify_wait semaphore.
 *
 *  The motivation for step (3) is explained in "Juggling", below.
 *
 *  The cy_pend count is decremented in cyclic_softint() after the cyclic
 *  handler returns.  Thus, if we find a cy_pend count of zero in step
 *  (4), we know that cyclic_remove() doesn't need to block.
 *
 *  If the cy_pend count is non-zero, however, we must block in cyclic_remove()
 *  until cyclic_softint() has finished calling the cyclic handler.  To let
 *  cyclic_softint() know that this cyclic has been removed, we zero the
 *  cy_pend count.  This will cause cyclic_softint()'s compare&swap to fail.
 *  When cyclic_softint() sees the zero cy_pend count, it knows that it's been
 *  caught during a resize (see "Resizing", above) or that the cyclic has been
 *  removed.  In the latter case, it calls cyclic_remove_pend() to call the
 *  cyclic handler cyp_rpend - 1 times, and posts on cyp_modify_wait.
 *
 *  Juggling
 *
 *  At first glance, cyclic juggling seems to be a difficult problem.  The
 *  subsystem must guarantee that a cyclic doesn't execute simultaneously on
 *  different CPUs, while also assuring that a cyclic fires exactly once
 *  per interval.  We solve this problem by leveraging a property of the
 *  platform:  gethrtime() is required to increase in lock-step across
 *  multiple CPUs.  Therefore, to juggle a cyclic, we remove it from its
 *  CPU, recording its expiration time in the remove cross call (step (3)
 *  in "Removing", above).  We then add the cyclic to the new CPU, explicitly
 *  setting its expiration time to the time recorded in the removal.  This
 *  leverages the existing cyclic expiry processing, which will compensate
 *  for any time lost while juggling.
 *
 *  Reprogramming
 *
 *  Normally, after a cyclic fires, its next expiration is computed from
 *  the current time and the cyclic interval. But there are situations when
 *  the next expiration needs to be reprogrammed by the kernel subsystem that
 *  is using the cyclic. cyclic_reprogram() allows this to be done. This,
 *  unlike the other kernel at-large cyclic API functions, is permitted to
 *  be called from the cyclic handler. This is because it does not use the
 *  cpu_lock to serialize access.
 *
 *  When cyclic_reprogram() is called for an omni-cyclic, the operation is
 *  applied to the omni-cyclic's component on the current CPU.
 *
 *  If a high-level cyclic handler reprograms its own cyclic, then
 *  cyclic_fire() detects that and does not recompute the cyclic's next
 *  expiration. However, for a lock-level or a low-level cyclic, the
 *  actual cyclic handler will execute at the lower PIL only after
 *  cyclic_fire() is done with all expired cyclics. To deal with this, such
 *  cyclics can be specified with a special interval of CY_INFINITY (INT64_MAX).
 *  cyclic_fire() recognizes this special value and recomputes the next
 *  expiration to CY_INFINITY. This effectively moves the cyclic to the
 *  bottom of the heap and prevents it from going off until its handler has
 *  had a chance to reprogram it. Infact, this is the way to create and reuse
 *  "one-shot" timers in the context of the cyclic subsystem without using
 *  cyclic_remove().
 *
 *  Here is the procedure for cyclic reprogramming:
 *
 *    1.  cyclic_reprogram() calls cyclic_reprogram_xcall() on the CPU
 *        that houses the cyclic.
 *    2.  cyclic_reprogram_xcall() raises interrupt level to CY_HIGH_LEVEL
 *    3.  The cyclic is located in the cyclic heap. The search for this is
 *        done from the bottom of the heap to the top as reprogrammable cyclics
 *        would be located closer to the bottom than the top.
 *    4.  The cyclic expiration is set and the cyclic is moved to its
 *        correct position in the heap (up or down depending on whether the
 *        new expiration is less than or greater than the old one).
 *    5.  If the cyclic move modified the root of the heap, the backend is
 *	  reprogrammed.
 *
 *  Reprogramming can be a frequent event (see the callout subsystem). So,
 *  the serialization used has to be efficient. As with all other cyclic
 *  operations, the interrupt level is raised during reprogramming. Plus,
 *  during reprogramming, the cyclic must not be juggled (regular cyclic)
 *  or stopped (omni-cyclic). The implementation defines a per-cyclic
 *  reader-writer lock to accomplish this. This lock is acquired in the
 *  reader mode by cyclic_reprogram() and writer mode by cyclic_juggle() and
 *  cyclic_omni_stop(). The reader-writer lock makes it efficient if
 *  an omni-cyclic is reprogrammed on different CPUs frequently.
 *
 *  Note that since the cpu_lock is not used during reprogramming, it is
 *  the responsibility of the user of the reprogrammable cyclic to make sure
 *  that the cyclic is not removed via cyclic_remove() during reprogramming.
 *  This is not an unreasonable requirement as the user will typically have
 *  some sort of synchronization for its cyclic-related activities. This
 *  little caveat exists because the cyclic ID is not really an ID. It is
 *  implemented as a pointer to a structure.
 */
#include <sys/cyclic_impl.h>
#include <sys/sysmacros.h>
#include <sys/systm.h>
#include <sys/atomic.h>
#include <sys/kmem.h>
#include <sys/cmn_err.h>
#include <sys/ddi.h>
#include <sys/sdt.h>

#ifdef CYCLIC_TRACE

/*
 * cyc_trace_enabled is for the benefit of kernel debuggers.
 */
int cyc_trace_enabled = 1;
static cyc_tracebuf_t cyc_ptrace;
static cyc_coverage_t cyc_coverage[CY_NCOVERAGE];

/*
 * Seen this anywhere?
 */
static uint_t
cyclic_coverage_hash(char *p)
{
	unsigned int g;
	uint_t hval;

	hval = 0;
	while (*p) {
		hval = (hval << 4) + *p++;
		if ((g = (hval & 0xf0000000)) != 0)
			hval ^= g >> 24;
		hval &= ~g;
	}
	return (hval);
}

static void
cyclic_coverage(char *why, int level, uint64_t arg0, uint64_t arg1)
{
	uint_t ndx, orig;

	for (ndx = orig = cyclic_coverage_hash(why) % CY_NCOVERAGE; ; ) {
		if (cyc_coverage[ndx].cyv_why == why)
			break;

		if (cyc_coverage[ndx].cyv_why != NULL ||
		    atomic_cas_ptr(&cyc_coverage[ndx].cyv_why, NULL, why) !=
		    NULL) {

			if (++ndx == CY_NCOVERAGE)
				ndx = 0;

			if (ndx == orig)
				panic("too many cyclic coverage points");
			continue;
		}

		/*
		 * If we're here, we have successfully swung our guy into
		 * the position at "ndx".
		 */
		break;
	}

	if (level == CY_PASSIVE_LEVEL)
		cyc_coverage[ndx].cyv_passive_count++;
	else
		cyc_coverage[ndx].cyv_count[level]++;

	cyc_coverage[ndx].cyv_arg0 = arg0;
	cyc_coverage[ndx].cyv_arg1 = arg1;
}

#define	CYC_TRACE(cpu, level, why, arg0, arg1) \
	CYC_TRACE_IMPL(&cpu->cyp_trace[level], level, why, arg0, arg1)

#define	CYC_PTRACE(why, arg0, arg1) \
	CYC_TRACE_IMPL(&cyc_ptrace, CY_PASSIVE_LEVEL, why, arg0, arg1)

#define	CYC_TRACE_IMPL(buf, level, why, a0, a1) { \
	if (panicstr == NULL) { \
		int _ndx = (buf)->cyt_ndx; \
		cyc_tracerec_t *_rec = &(buf)->cyt_buf[_ndx]; \
		(buf)->cyt_ndx = (++_ndx == CY_NTRACEREC) ? 0 : _ndx; \
		_rec->cyt_tstamp = gethrtime_unscaled(); \
		_rec->cyt_why = (why); \
		_rec->cyt_arg0 = (uint64_t)(uintptr_t)(a0); \
		_rec->cyt_arg1 = (uint64_t)(uintptr_t)(a1); \
		cyclic_coverage(why, level,	\
		    (uint64_t)(uintptr_t)(a0), (uint64_t)(uintptr_t)(a1)); \
	} \
}

#else

static int cyc_trace_enabled = 0;

#define	CYC_TRACE(cpu, level, why, arg0, arg1)
#define	CYC_PTRACE(why, arg0, arg1)

#endif

#define	CYC_TRACE0(cpu, level, why) CYC_TRACE(cpu, level, why, 0, 0)
#define	CYC_TRACE1(cpu, level, why, arg0) CYC_TRACE(cpu, level, why, arg0, 0)

#define	CYC_PTRACE0(why) CYC_PTRACE(why, 0, 0)
#define	CYC_PTRACE1(why, arg0) CYC_PTRACE(why, arg0, 0)

static kmem_cache_t *cyclic_id_cache;
static cyc_id_t *cyclic_id_head;
static hrtime_t cyclic_resolution;
static cyc_backend_t cyclic_backend;

/*
 * Returns 1 if the upheap propagated to the root, 0 if it did not.  This
 * allows the caller to reprogram the backend only when the root has been
 * modified.
 */
static int
cyclic_upheap(cyc_cpu_t *cpu, cyc_index_t ndx)
{
	cyclic_t *cyclics;
	cyc_index_t *heap;
	cyc_index_t heap_parent, heap_current = ndx;
	cyc_index_t parent, current;

	if (heap_current == 0)
		return (1);

	heap = cpu->cyp_heap;
	cyclics = cpu->cyp_cyclics;
	heap_parent = CYC_HEAP_PARENT(heap_current);

	for (;;) {
		current = heap[heap_current];
		parent = heap[heap_parent];

		/*
		 * We have an expiration time later than our parent; we're
		 * done.
		 */
		if (cyclics[current].cy_expire >= cyclics[parent].cy_expire)
			return (0);

		/*
		 * We need to swap with our parent, and continue up the heap.
		 */
		heap[heap_parent] = current;
		heap[heap_current] = parent;

		/*
		 * If we just reached the root, we're done.
		 */
		if (heap_parent == 0)
			return (1);

		heap_current = heap_parent;
		heap_parent = CYC_HEAP_PARENT(heap_current);
	}
}

static void
cyclic_downheap(cyc_cpu_t *cpu, cyc_index_t ndx)
{
	cyclic_t *cyclics = cpu->cyp_cyclics;
	cyc_index_t *heap = cpu->cyp_heap;

	cyc_index_t heap_left, heap_right, heap_me = ndx;
	cyc_index_t left, right, me;
	cyc_index_t nelems = cpu->cyp_nelems;

	for (;;) {
		/*
		 * If we don't have a left child (i.e., we're a leaf), we're
		 * done.
		 */
		if ((heap_left = CYC_HEAP_LEFT(heap_me)) >= nelems)
			return;

		left = heap[heap_left];
		me = heap[heap_me];

		heap_right = CYC_HEAP_RIGHT(heap_me);

		/*
		 * Even if we don't have a right child, we still need to compare
		 * our expiration time against that of our left child.
		 */
		if (heap_right >= nelems)
			goto comp_left;

		right = heap[heap_right];

		/*
		 * We have both a left and a right child.  We need to compare
		 * the expiration times of the children to determine which
		 * expires earlier.
		 */
		if (cyclics[right].cy_expire < cyclics[left].cy_expire) {
			/*
			 * Our right child is the earlier of our children.
			 * We'll now compare our expiration time to its; if
			 * ours is the earlier, we're done.
			 */
			if (cyclics[me].cy_expire <= cyclics[right].cy_expire)
				return;

			/*
			 * Our right child expires earlier than we do; swap
			 * with our right child, and descend right.
			 */
			heap[heap_right] = me;
			heap[heap_me] = right;
			heap_me = heap_right;
			continue;
		}

comp_left:
		/*
		 * Our left child is the earlier of our children (or we have
		 * no right child).  We'll now compare our expiration time
		 * to its; if ours is the earlier, we're done.
		 */
		if (cyclics[me].cy_expire <= cyclics[left].cy_expire)
			return;

		/*
		 * Our left child expires earlier than we do; swap with our
		 * left child, and descend left.
		 */
		heap[heap_left] = me;
		heap[heap_me] = left;
		heap_me = heap_left;
	}
}

static void
cyclic_expire(cyc_cpu_t *cpu, cyc_index_t ndx, cyclic_t *cyclic)
{
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_level_t level = cyclic->cy_level;

	/*
	 * If this is a CY_HIGH_LEVEL cyclic, just call the handler; we don't
	 * need to worry about the pend count for CY_HIGH_LEVEL cyclics.
	 */
	if (level == CY_HIGH_LEVEL) {
		cyc_func_t handler = cyclic->cy_handler;
		void *arg = cyclic->cy_arg;

		CYC_TRACE(cpu, CY_HIGH_LEVEL, "handler-in", handler, arg);
		DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);

		(*handler)(arg);

		DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
		CYC_TRACE(cpu, CY_HIGH_LEVEL, "handler-out", handler, arg);

		return;
	}

	/*
	 * We're at CY_HIGH_LEVEL; this modification to cy_pend need not
	 * be atomic (the high interrupt level assures that it will appear
	 * atomic to any softint currently running).
	 */
	if (cyclic->cy_pend++ == 0) {
		cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[level];
		cyc_pcbuffer_t *pc = &softbuf->cys_buf[softbuf->cys_hard];

		/*
		 * We need to enqueue this cyclic in the soft buffer.
		 */
		CYC_TRACE(cpu, CY_HIGH_LEVEL, "expire-enq", cyclic,
		    pc->cypc_prodndx);
		pc->cypc_buf[pc->cypc_prodndx++ & pc->cypc_sizemask] = ndx;

		ASSERT(pc->cypc_prodndx != pc->cypc_consndx);
	} else {
		/*
		 * If the pend count is zero after we incremented it, then
		 * we've wrapped (i.e. we had a cy_pend count of over four
		 * billion.  In this case, we clamp the pend count at
		 * UINT32_MAX.  Yes, cyclics can be lost in this case.
		 */
		if (cyclic->cy_pend == 0) {
			CYC_TRACE1(cpu, CY_HIGH_LEVEL, "expire-wrap", cyclic);
			cyclic->cy_pend = UINT32_MAX;
		}

		CYC_TRACE(cpu, CY_HIGH_LEVEL, "expire-bump", cyclic, 0);
	}

	be->cyb_softint(be->cyb_arg, cyclic->cy_level);
}

/*
 *  cyclic_fire(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_fire() is the cyclic subsystem's CY_HIGH_LEVEL interrupt handler.
 *    Called by the cyclic backend.
 *
 *  Arguments and notes
 *
 *    The only argument is the CPU on which the interrupt is executing;
 *    backends must call into cyclic_fire() on the specified CPU.
 *
 *    cyclic_fire() may be called spuriously without ill effect.  Optimal
 *    backends will call into cyclic_fire() at or shortly after the time
 *    requested via cyb_reprogram().  However, calling cyclic_fire()
 *    arbitrarily late will only manifest latency bubbles; the correctness
 *    of the cyclic subsystem does not rely on the timeliness of the backend.
 *
 *    cyclic_fire() is wait-free; it will not block or spin.
 *
 *  Return values
 *
 *    None.
 *
 *  Caller's context
 *
 *    cyclic_fire() must be called from CY_HIGH_LEVEL interrupt context.
 */
void
cyclic_fire(cpu_t *c)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_index_t *heap = cpu->cyp_heap;
	cyclic_t *cyclic, *cyclics = cpu->cyp_cyclics;
	void *arg = be->cyb_arg;
	hrtime_t now = gethrtime();
	hrtime_t exp;

	CYC_TRACE(cpu, CY_HIGH_LEVEL, "fire", now, 0);

	if (cpu->cyp_nelems == 0) {
		/*
		 * This is a spurious fire.  Count it as such, and blow
		 * out of here.
		 */
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "fire-spurious");
		return;
	}

	for (;;) {
		cyc_index_t ndx = heap[0];

		cyclic = &cyclics[ndx];

		ASSERT(!(cyclic->cy_flags & CYF_FREE));

		CYC_TRACE(cpu, CY_HIGH_LEVEL, "fire-check", cyclic,
		    cyclic->cy_expire);

		if ((exp = cyclic->cy_expire) > now)
			break;

		cyclic_expire(cpu, ndx, cyclic);

		/*
		 * If the handler reprogrammed the cyclic, then don't
		 * recompute the expiration. Then, if the interval is
		 * infinity, set the expiration to infinity. This can
		 * be used to create one-shot timers.
		 */
		if (exp != cyclic->cy_expire) {
			/*
			 * If a hi level cyclic reprograms itself,
			 * the heap adjustment and reprogramming of the
			 * clock source have already been done at this
			 * point. So, we can continue.
			 */
			continue;
		}

		if (cyclic->cy_interval == CY_INFINITY)
			exp = CY_INFINITY;
		else
			exp += cyclic->cy_interval;

		/*
		 * If this cyclic will be set to next expire in the distant
		 * past, we have one of two situations:
		 *
		 *   a)	This is the first firing of a cyclic which had
		 *	cy_expire set to 0.
		 *
		 *   b)	We are tragically late for a cyclic -- most likely
		 *	due to being in the debugger.
		 *
		 * In either case, we set the new expiration time to be the
		 * the next interval boundary.  This assures that the
		 * expiration time modulo the interval is invariant.
		 *
		 * We arbitrarily define "distant" to be one second (one second
		 * is chosen because it's shorter than any foray to the
		 * debugger while still being longer than any legitimate
		 * stretch at CY_HIGH_LEVEL).
		 */

		if (now - exp > NANOSEC) {
			hrtime_t interval = cyclic->cy_interval;

			CYC_TRACE(cpu, CY_HIGH_LEVEL, exp == interval ?
			    "fire-first" : "fire-swing", now, exp);

			exp += ((now - exp) / interval + 1) * interval;
		}

		cyclic->cy_expire = exp;
		cyclic_downheap(cpu, 0);
	}

	/*
	 * Now we have a cyclic in the root slot which isn't in the past;
	 * reprogram the interrupt source.
	 */
	be->cyb_reprogram(arg, exp);
}

static void
cyclic_remove_pend(cyc_cpu_t *cpu, cyc_level_t level, cyclic_t *cyclic)
{
	cyc_func_t handler = cyclic->cy_handler;
	void *arg = cyclic->cy_arg;
	uint32_t i, rpend = cpu->cyp_rpend - 1;

	ASSERT(cyclic->cy_flags & CYF_FREE);
	ASSERT(cyclic->cy_pend == 0);
	ASSERT(cpu->cyp_state == CYS_REMOVING);
	ASSERT(cpu->cyp_rpend > 0);

	CYC_TRACE(cpu, level, "remove-rpend", cyclic, cpu->cyp_rpend);

	/*
	 * Note that we only call the handler cyp_rpend - 1 times; this is
	 * to account for the handler call in cyclic_softint().
	 */
	for (i = 0; i < rpend; i++) {
		CYC_TRACE(cpu, level, "rpend-in", handler, arg);
		DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);

		(*handler)(arg);

		DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
		CYC_TRACE(cpu, level, "rpend-out", handler, arg);
	}

	/*
	 * We can now let the remove operation complete.
	 */
	sema_v(&cpu->cyp_modify_wait);
}

/*
 *  cyclic_softint(cpu_t *cpu, cyc_level_t level)
 *
 *  Overview
 *
 *    cyclic_softint() is the cyclic subsystem's CY_LOCK_LEVEL and CY_LOW_LEVEL
 *    soft interrupt handler.  Called by the cyclic backend.
 *
 *  Arguments and notes
 *
 *    The first argument to cyclic_softint() is the CPU on which the interrupt
 *    is executing; backends must call into cyclic_softint() on the specified
 *    CPU.  The second argument is the level of the soft interrupt; it must
 *    be one of CY_LOCK_LEVEL or CY_LOW_LEVEL.
 *
 *    cyclic_softint() will call the handlers for cyclics pending at the
 *    specified level.  cyclic_softint() will not return until all pending
 *    cyclics at the specified level have been dealt with; intervening
 *    CY_HIGH_LEVEL interrupts which enqueue cyclics at the specified level
 *    may therefore prolong cyclic_softint().
 *
 *    cyclic_softint() never disables interrupts, and, if neither a
 *    cyclic_add() nor a cyclic_remove() is pending on the specified CPU, is
 *    lock-free.  This assures that in the common case, cyclic_softint()
 *    completes without blocking, and never starves cyclic_fire().  If either
 *    cyclic_add() or cyclic_remove() is pending, cyclic_softint() may grab
 *    a dispatcher lock.
 *
 *    While cyclic_softint() is designed for bounded latency, it is obviously
 *    at the mercy of its cyclic handlers.  Because cyclic handlers may block
 *    arbitrarily, callers of cyclic_softint() should not rely upon
 *    deterministic completion.
 *
 *    cyclic_softint() may be called spuriously without ill effect.
 *
 *  Return value
 *
 *    None.
 *
 *  Caller's context
 *
 *    The caller must be executing in soft interrupt context at either
 *    CY_LOCK_LEVEL or CY_LOW_LEVEL.  The level passed to cyclic_softint()
 *    must match the level at which it is executing.  On optimal backends,
 *    the caller will hold no locks.  In any case, the caller may not hold
 *    cpu_lock or any lock acquired by any cyclic handler or held across
 *    any of cyclic_add(), cyclic_remove(), cyclic_bind() or cyclic_juggle().
 */
void
cyclic_softint(cpu_t *c, cyc_level_t level)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_softbuf_t *softbuf;
	int soft, *buf, consndx, resized = 0, intr_resized = 0;
	cyc_pcbuffer_t *pc;
	cyclic_t *cyclics = cpu->cyp_cyclics;
	int sizemask;

	CYC_TRACE(cpu, level, "softint", cyclics, 0);

	ASSERT(level < CY_LOW_LEVEL + CY_SOFT_LEVELS);

	softbuf = &cpu->cyp_softbuf[level];
top:
	soft = softbuf->cys_soft;
	ASSERT(soft == 0 || soft == 1);

	pc = &softbuf->cys_buf[soft];
	buf = pc->cypc_buf;
	consndx = pc->cypc_consndx;
	sizemask = pc->cypc_sizemask;

	CYC_TRACE(cpu, level, "softint-top", cyclics, pc);

	while (consndx != pc->cypc_prodndx) {
		uint32_t pend, npend, opend;
		int consmasked = consndx & sizemask;
		cyclic_t *cyclic = &cyclics[buf[consmasked]];
		cyc_func_t handler = cyclic->cy_handler;
		void *arg = cyclic->cy_arg;

		ASSERT(buf[consmasked] < cpu->cyp_size);
		CYC_TRACE(cpu, level, "consuming", consndx, cyclic);

		/*
		 * We have found this cyclic in the pcbuffer.  We know that
		 * one of the following is true:
		 *
		 *  (a)	The pend is non-zero.  We need to execute the handler
		 *	at least once.
		 *
		 *  (b)	The pend _was_ non-zero, but it's now zero due to a
		 *	resize.  We will call the handler once, see that we
		 *	are in this case, and read the new cyclics buffer
		 *	(and hence the old non-zero pend).
		 *
		 *  (c)	The pend _was_ non-zero, but it's now zero due to a
		 *	removal.  We will call the handler once, see that we
		 *	are in this case, and call into cyclic_remove_pend()
		 *	to call the cyclic rpend times.  We will take into
		 *	account that we have already called the handler once.
		 *
		 * Point is:  it's safe to call the handler without first
		 * checking the pend.
		 */
		do {
			CYC_TRACE(cpu, level, "handler-in", handler, arg);
			DTRACE_PROBE1(cyclic__start, cyclic_t *, cyclic);

			(*handler)(arg);

			DTRACE_PROBE1(cyclic__end, cyclic_t *, cyclic);
			CYC_TRACE(cpu, level, "handler-out", handler, arg);
reread:
			pend = cyclic->cy_pend;
			npend = pend - 1;

			if (pend == 0) {
				if (cpu->cyp_state == CYS_REMOVING) {
					/*
					 * This cyclic has been removed while
					 * it had a non-zero pend count (we
					 * know it was non-zero because we
					 * found this cyclic in the pcbuffer).
					 * There must be a non-zero rpend for
					 * this CPU, and there must be a remove
					 * operation blocking; we'll call into
					 * cyclic_remove_pend() to clean this
					 * up, and break out of the pend loop.
					 */
					cyclic_remove_pend(cpu, level, cyclic);
					break;
				}

				/*
				 * We must have had a resize interrupt us.
				 */
				CYC_TRACE(cpu, level, "resize-int", cyclics, 0);
				ASSERT(cpu->cyp_state == CYS_EXPANDING);
				ASSERT(cyclics != cpu->cyp_cyclics);
				ASSERT(resized == 0);
				ASSERT(intr_resized == 0);
				intr_resized = 1;
				cyclics = cpu->cyp_cyclics;
				cyclic = &cyclics[buf[consmasked]];
				ASSERT(cyclic->cy_handler == handler);
				ASSERT(cyclic->cy_arg == arg);
				goto reread;
			}

			if ((opend =
			    atomic_cas_32(&cyclic->cy_pend, pend, npend)) !=
			    pend) {
				/*
				 * Our atomic_cas_32 can fail for one of several
				 * reasons:
				 *
				 *  (a)	An intervening high level bumped up the
				 *	pend count on this cyclic.  In this
				 *	case, we will see a higher pend.
				 *
				 *  (b)	The cyclics array has been yanked out
				 *	from underneath us by a resize
				 *	operation.  In this case, pend is 0 and
				 *	cyp_state is CYS_EXPANDING.
				 *
				 *  (c)	The cyclic has been removed by an
				 *	intervening remove-xcall.  In this case,
				 *	pend will be 0, the cyp_state will be
				 *	CYS_REMOVING, and the cyclic will be
				 *	marked CYF_FREE.
				 *
				 * The assertion below checks that we are
				 * in one of the above situations.  The
				 * action under all three is to return to
				 * the top of the loop.
				 */
				CYC_TRACE(cpu, level, "cas-fail", opend, pend);
				ASSERT(opend > pend || (opend == 0 &&
				    ((cyclics != cpu->cyp_cyclics &&
				    cpu->cyp_state == CYS_EXPANDING) ||
				    (cpu->cyp_state == CYS_REMOVING &&
				    (cyclic->cy_flags & CYF_FREE)))));
				goto reread;
			}

			/*
			 * Okay, so we've managed to successfully decrement
			 * pend.  If we just decremented the pend to 0, we're
			 * done.
			 */
		} while (npend > 0);

		pc->cypc_consndx = ++consndx;
	}

	/*
	 * If the high level handler is no longer writing to the same
	 * buffer, then we've had a resize.  We need to switch our soft
	 * index, and goto top.
	 */
	if (soft != softbuf->cys_hard) {
		/*
		 * We can assert that the other buffer has grown by exactly
		 * one factor of two.
		 */
		CYC_TRACE(cpu, level, "buffer-grow", 0, 0);
		ASSERT(cpu->cyp_state == CYS_EXPANDING);
		ASSERT(softbuf->cys_buf[softbuf->cys_hard].cypc_sizemask ==
		    (softbuf->cys_buf[soft].cypc_sizemask << 1) + 1 ||
		    softbuf->cys_buf[soft].cypc_sizemask == 0);
		ASSERT(softbuf->cys_hard == (softbuf->cys_soft ^ 1));

		/*
		 * If our cached cyclics pointer doesn't match cyp_cyclics,
		 * then we took a resize between our last iteration of the
		 * pend loop and the check against softbuf->cys_hard.
		 */
		if (cpu->cyp_cyclics != cyclics) {
			CYC_TRACE1(cpu, level, "resize-int-int", consndx);
			cyclics = cpu->cyp_cyclics;
		}

		softbuf->cys_soft = softbuf->cys_hard;

		ASSERT(resized == 0);
		resized = 1;
		goto top;
	}

	/*
	 * If we were interrupted by a resize operation, then we must have
	 * seen the hard index change.
	 */
	ASSERT(!(intr_resized == 1 && resized == 0));

	if (resized) {
		uint32_t lev, nlev;

		ASSERT(cpu->cyp_state == CYS_EXPANDING);

		do {
			lev = cpu->cyp_modify_levels;
			nlev = lev + 1;
		} while (atomic_cas_32(&cpu->cyp_modify_levels, lev, nlev) !=
		    lev);

		/*
		 * If we are the last soft level to see the modification,
		 * post on cyp_modify_wait.  Otherwise, (if we're not
		 * already at low level), post down to the next soft level.
		 */
		if (nlev == CY_SOFT_LEVELS) {
			CYC_TRACE0(cpu, level, "resize-kick");
			sema_v(&cpu->cyp_modify_wait);
		} else {
			ASSERT(nlev < CY_SOFT_LEVELS);
			if (level != CY_LOW_LEVEL) {
				cyc_backend_t *be = cpu->cyp_backend;

				CYC_TRACE0(cpu, level, "resize-post");
				be->cyb_softint(be->cyb_arg, level - 1);
			}
		}
	}
}

static void
cyclic_expand_xcall(cyc_xcallarg_t *arg)
{
	cyc_cpu_t *cpu = arg->cyx_cpu;
	cyc_backend_t *be = cpu->cyp_backend;
	cyb_arg_t bar = be->cyb_arg;
	cyc_cookie_t cookie;
	cyc_index_t new_size = arg->cyx_size, size = cpu->cyp_size, i;
	cyc_index_t *new_heap = arg->cyx_heap;
	cyclic_t *cyclics = cpu->cyp_cyclics, *new_cyclics = arg->cyx_cyclics;

	ASSERT(cpu->cyp_state == CYS_EXPANDING);

	/*
	 * This is a little dicey.  First, we'll raise our interrupt level
	 * to CY_HIGH_LEVEL.  This CPU already has a new heap, cyclic array,
	 * etc.; we just need to bcopy them across.  As for the softint
	 * buffers, we'll switch the active buffers.  The actual softints will
	 * take care of consuming any pending cyclics in the old buffer.
	 */
	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE(cpu, CY_HIGH_LEVEL, "expand", new_size, 0);

	/*
	 * Assert that the new size is a power of 2.
	 */
	ASSERT((new_size & new_size - 1) == 0);
	ASSERT(new_size == (size << 1));
	ASSERT(cpu->cyp_heap != NULL && cpu->cyp_cyclics != NULL);

	bcopy(cpu->cyp_heap, new_heap, sizeof (cyc_index_t) * size);
	bcopy(cyclics, new_cyclics, sizeof (cyclic_t) * size);

	/*
	 * Now run through the old cyclics array, setting pend to 0.  To
	 * softints (which are executing at a lower priority level), the
	 * pends dropping to 0 will appear atomic with the cyp_cyclics
	 * pointer changing.
	 */
	for (i = 0; i < size; i++)
		cyclics[i].cy_pend = 0;

	/*
	 * Set up the free list, and set all of the new cyclics to be CYF_FREE.
	 */
	for (i = size; i < new_size; i++) {
		new_heap[i] = i;
		new_cyclics[i].cy_flags = CYF_FREE;
	}

	/*
	 * We can go ahead and plow the value of cyp_heap and cyp_cyclics;
	 * cyclic_expand() has kept a copy.
	 */
	cpu->cyp_heap = new_heap;
	cpu->cyp_cyclics = new_cyclics;
	cpu->cyp_size = new_size;

	/*
	 * We've switched over the heap and the cyclics array.  Now we need
	 * to switch over our active softint buffer pointers.
	 */
	for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
		cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
		uchar_t hard = softbuf->cys_hard;

		/*
		 * Assert that we're not in the middle of a resize operation.
		 */
		ASSERT(hard == softbuf->cys_soft);
		ASSERT(hard == 0 || hard == 1);
		ASSERT(softbuf->cys_buf[hard].cypc_buf != NULL);

		softbuf->cys_hard = hard ^ 1;

		/*
		 * The caller (cyclic_expand()) is responsible for setting
		 * up the new producer-consumer buffer; assert that it's
		 * been done correctly.
		 */
		ASSERT(softbuf->cys_buf[hard ^ 1].cypc_buf != NULL);
		ASSERT(softbuf->cys_buf[hard ^ 1].cypc_prodndx == 0);
		ASSERT(softbuf->cys_buf[hard ^ 1].cypc_consndx == 0);
	}

	/*
	 * That's all there is to it; now we just need to postdown to
	 * get the softint chain going.
	 */
	be->cyb_softint(bar, CY_HIGH_LEVEL - 1);
	be->cyb_restore_level(bar, cookie);
}

/*
 * cyclic_expand() will cross call onto the CPU to perform the actual
 * expand operation.
 */
static void
cyclic_expand(cyc_cpu_t *cpu)
{
	cyc_index_t new_size, old_size;
	cyc_index_t *new_heap, *old_heap;
	cyclic_t *new_cyclics, *old_cyclics;
	cyc_xcallarg_t arg;
	cyc_backend_t *be = cpu->cyp_backend;
	char old_hard;
	int i;

	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);

	cpu->cyp_state = CYS_EXPANDING;

	old_heap = cpu->cyp_heap;
	old_cyclics = cpu->cyp_cyclics;

	if ((new_size = ((old_size = cpu->cyp_size) << 1)) == 0) {
		new_size = CY_DEFAULT_PERCPU;
		ASSERT(old_heap == NULL && old_cyclics == NULL);
	}

	/*
	 * Check that the new_size is a power of 2.
	 */
	ASSERT((new_size - 1 & new_size) == 0);

	new_heap = kmem_alloc(sizeof (cyc_index_t) * new_size, KM_SLEEP);
	new_cyclics = kmem_zalloc(sizeof (cyclic_t) * new_size, KM_SLEEP);

	/*
	 * We know that no other expansions are in progress (they serialize
	 * on cpu_lock), so we can safely read the softbuf metadata.
	 */
	old_hard = cpu->cyp_softbuf[0].cys_hard;

	for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
		cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
		char hard = softbuf->cys_hard;
		cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard ^ 1];

		ASSERT(hard == old_hard);
		ASSERT(hard == softbuf->cys_soft);
		ASSERT(pc->cypc_buf == NULL);

		pc->cypc_buf =
		    kmem_alloc(sizeof (cyc_index_t) * new_size, KM_SLEEP);
		pc->cypc_prodndx = pc->cypc_consndx = 0;
		pc->cypc_sizemask = new_size - 1;
	}

	arg.cyx_cpu = cpu;
	arg.cyx_heap = new_heap;
	arg.cyx_cyclics = new_cyclics;
	arg.cyx_size = new_size;

	cpu->cyp_modify_levels = 0;

	be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
	    (cyc_func_t)cyclic_expand_xcall, &arg);

	/*
	 * Now block, waiting for the resize operation to complete.
	 */
	sema_p(&cpu->cyp_modify_wait);
	ASSERT(cpu->cyp_modify_levels == CY_SOFT_LEVELS);

	/*
	 * The operation is complete; we can now free the old buffers.
	 */
	for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
		cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
		char hard = softbuf->cys_hard;
		cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard ^ 1];

		ASSERT(hard == (old_hard ^ 1));
		ASSERT(hard == softbuf->cys_soft);

		if (pc->cypc_buf == NULL)
			continue;

		ASSERT(pc->cypc_sizemask == ((new_size - 1) >> 1));

		kmem_free(pc->cypc_buf,
		    sizeof (cyc_index_t) * (pc->cypc_sizemask + 1));
		pc->cypc_buf = NULL;
	}

	if (old_cyclics != NULL) {
		ASSERT(old_heap != NULL);
		ASSERT(old_size != 0);
		kmem_free(old_cyclics, sizeof (cyclic_t) * old_size);
		kmem_free(old_heap, sizeof (cyc_index_t) * old_size);
	}

	ASSERT(cpu->cyp_state == CYS_EXPANDING);
	cpu->cyp_state = CYS_ONLINE;
}

/*
 * cyclic_pick_cpu will attempt to pick a CPU according to the constraints
 * specified by the partition, bound CPU, and flags.  Additionally,
 * cyclic_pick_cpu() will not pick the avoid CPU; it will return NULL if
 * the avoid CPU is the only CPU which satisfies the constraints.
 *
 * If CYF_CPU_BOUND is set in flags, the specified CPU must be non-NULL.
 * If CYF_PART_BOUND is set in flags, the specified partition must be non-NULL.
 * If both CYF_CPU_BOUND and CYF_PART_BOUND are set, the specified CPU must
 * be in the specified partition.
 */
static cyc_cpu_t *
cyclic_pick_cpu(cpupart_t *part, cpu_t *bound, cpu_t *avoid, uint16_t flags)
{
	cpu_t *c, *start = (part != NULL) ? part->cp_cpulist : CPU;
	cpu_t *online = NULL;
	uintptr_t offset;

	CYC_PTRACE("pick-cpu", part, bound);

	ASSERT(!(flags & CYF_CPU_BOUND) || bound != NULL);
	ASSERT(!(flags & CYF_PART_BOUND) || part != NULL);

	/*
	 * If we're bound to our CPU, there isn't much choice involved.  We
	 * need to check that the CPU passed as bound is in the cpupart, and
	 * that the CPU that we're binding to has been configured.
	 */
	if (flags & CYF_CPU_BOUND) {
		CYC_PTRACE("pick-cpu-bound", bound, avoid);

		if ((flags & CYF_PART_BOUND) && bound->cpu_part != part)
			panic("cyclic_pick_cpu:  "
			    "CPU binding contradicts partition binding");

		if (bound == avoid)
			return (NULL);

		if (bound->cpu_cyclic == NULL)
			panic("cyclic_pick_cpu:  "
			    "attempt to bind to non-configured CPU");

		return (bound->cpu_cyclic);
	}

	if (flags & CYF_PART_BOUND) {
		CYC_PTRACE("pick-part-bound", bound, avoid);
		offset = offsetof(cpu_t, cpu_next_part);
	} else {
		offset = offsetof(cpu_t, cpu_next_onln);
	}

	c = start;
	do {
		if (c->cpu_cyclic == NULL)
			continue;

		if (c->cpu_cyclic->cyp_state == CYS_OFFLINE)
			continue;

		if (c == avoid)
			continue;

		if (c->cpu_flags & CPU_ENABLE)
			goto found;

		if (online == NULL)
			online = c;
	} while ((c = *(cpu_t **)((uintptr_t)c + offset)) != start);

	/*
	 * If we're here, we're in one of two situations:
	 *
	 *  (a)	We have a partition-bound cyclic, and there is no CPU in
	 *	our partition which is CPU_ENABLE'd.  If we saw another
	 *	non-CYS_OFFLINE CPU in our partition, we'll go with it.
	 *	If not, the avoid CPU must be the only non-CYS_OFFLINE
	 *	CPU in the partition; we're forced to return NULL.
	 *
	 *  (b)	We have a partition-unbound cyclic, in which case there
	 *	must only be one CPU CPU_ENABLE'd, and it must be the one
	 *	we're trying to avoid.  If cyclic_juggle()/cyclic_offline()
	 *	are called appropriately, this generally shouldn't happen
	 *	(the offline should fail before getting to this code).
	 *	At any rate: we can't avoid the avoid CPU, so we return
	 *	NULL.
	 */
	if (!(flags & CYF_PART_BOUND)) {
		ASSERT(avoid->cpu_flags & CPU_ENABLE);
		return (NULL);
	}

	CYC_PTRACE("pick-no-intr", part, avoid);

	if ((c = online) != NULL)
		goto found;

	CYC_PTRACE("pick-fail", part, avoid);
	ASSERT(avoid->cpu_part == start->cpu_part);
	return (NULL);

found:
	CYC_PTRACE("pick-cpu-found", c, avoid);
	ASSERT(c != avoid);
	ASSERT(c->cpu_cyclic != NULL);

	return (c->cpu_cyclic);
}

static void
cyclic_add_xcall(cyc_xcallarg_t *arg)
{
	cyc_cpu_t *cpu = arg->cyx_cpu;
	cyc_handler_t *hdlr = arg->cyx_hdlr;
	cyc_time_t *when = arg->cyx_when;
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_index_t ndx, nelems;
	cyc_cookie_t cookie;
	cyb_arg_t bar = be->cyb_arg;
	cyclic_t *cyclic;

	ASSERT(cpu->cyp_nelems < cpu->cyp_size);

	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE(cpu, CY_HIGH_LEVEL,
	    "add-xcall", when->cyt_when, when->cyt_interval);

	nelems = cpu->cyp_nelems++;

	if (nelems == 0) {
		/*
		 * If this is the first element, we need to enable the
		 * backend on this CPU.
		 */
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "enabled");
		be->cyb_enable(bar);
	}

	ndx = cpu->cyp_heap[nelems];
	cyclic = &cpu->cyp_cyclics[ndx];

	ASSERT(cyclic->cy_flags == CYF_FREE);
	cyclic->cy_interval = when->cyt_interval;

	if (when->cyt_when == 0) {
		/*
		 * If a start time hasn't been explicitly specified, we'll
		 * start on the next interval boundary.
		 */
		cyclic->cy_expire = (gethrtime() / cyclic->cy_interval + 1) *
		    cyclic->cy_interval;
	} else {
		cyclic->cy_expire = when->cyt_when;
	}

	cyclic->cy_handler = hdlr->cyh_func;
	cyclic->cy_arg = hdlr->cyh_arg;
	cyclic->cy_level = hdlr->cyh_level;
	cyclic->cy_flags = arg->cyx_flags;

	if (cyclic_upheap(cpu, nelems)) {
		hrtime_t exp = cyclic->cy_expire;

		CYC_TRACE(cpu, CY_HIGH_LEVEL, "add-reprog", cyclic, exp);

		/*
		 * If our upheap propagated to the root, we need to
		 * reprogram the interrupt source.
		 */
		be->cyb_reprogram(bar, exp);
	}
	be->cyb_restore_level(bar, cookie);

	arg->cyx_ndx = ndx;
}

static cyc_index_t
cyclic_add_here(cyc_cpu_t *cpu, cyc_handler_t *hdlr,
    cyc_time_t *when, uint16_t flags)
{
	cyc_backend_t *be = cpu->cyp_backend;
	cyb_arg_t bar = be->cyb_arg;
	cyc_xcallarg_t arg;

	CYC_PTRACE("add-cpu", cpu, hdlr->cyh_func);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(!(cpu->cyp_cpu->cpu_flags & CPU_OFFLINE));
	ASSERT(when->cyt_when >= 0 && when->cyt_interval > 0);

	if (cpu->cyp_nelems == cpu->cyp_size) {
		/*
		 * This is expensive; it will cross call onto the other
		 * CPU to perform the expansion.
		 */
		cyclic_expand(cpu);
		ASSERT(cpu->cyp_nelems < cpu->cyp_size);
	}

	/*
	 * By now, we know that we're going to be able to successfully
	 * perform the add.  Now cross call over to the CPU of interest to
	 * actually add our cyclic.
	 */
	arg.cyx_cpu = cpu;
	arg.cyx_hdlr = hdlr;
	arg.cyx_when = when;
	arg.cyx_flags = flags;

	be->cyb_xcall(bar, cpu->cyp_cpu, (cyc_func_t)cyclic_add_xcall, &arg);

	CYC_PTRACE("add-cpu-done", cpu, arg.cyx_ndx);

	return (arg.cyx_ndx);
}

static void
cyclic_remove_xcall(cyc_xcallarg_t *arg)
{
	cyc_cpu_t *cpu = arg->cyx_cpu;
	cyc_backend_t *be = cpu->cyp_backend;
	cyb_arg_t bar = be->cyb_arg;
	cyc_cookie_t cookie;
	cyc_index_t ndx = arg->cyx_ndx, nelems, i;
	cyc_index_t *heap, last;
	cyclic_t *cyclic;
#ifdef DEBUG
	cyc_index_t root;
#endif

	ASSERT(cpu->cyp_state == CYS_REMOVING);

	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE1(cpu, CY_HIGH_LEVEL, "remove-xcall", ndx);

	heap = cpu->cyp_heap;
	nelems = cpu->cyp_nelems;
	ASSERT(nelems > 0);
	cyclic = &cpu->cyp_cyclics[ndx];

	/*
	 * Grab the current expiration time.  If this cyclic is being
	 * removed as part of a juggling operation, the expiration time
	 * will be used when the cyclic is added to the new CPU.
	 */
	if (arg->cyx_when != NULL) {
		arg->cyx_when->cyt_when = cyclic->cy_expire;
		arg->cyx_when->cyt_interval = cyclic->cy_interval;
	}

	if (cyclic->cy_pend != 0) {
		/*
		 * The pend is non-zero; this cyclic is currently being
		 * executed (or will be executed shortly).  If the caller
		 * refuses to wait, we must return (doing nothing).  Otherwise,
		 * we will stash the pend value * in this CPU's rpend, and
		 * then zero it out.  The softint in the pend loop will see
		 * that we have zeroed out pend, and will call the cyclic
		 * handler rpend times.  The caller will wait until the
		 * softint has completed calling the cyclic handler.
		 */
		if (arg->cyx_wait == CY_NOWAIT) {
			arg->cyx_wait = CY_WAIT;
			goto out;
		}

		ASSERT(cyclic->cy_level != CY_HIGH_LEVEL);
		CYC_TRACE1(cpu, CY_HIGH_LEVEL, "remove-pend", cyclic->cy_pend);
		cpu->cyp_rpend = cyclic->cy_pend;
		cyclic->cy_pend = 0;
	}

	/*
	 * Now set the flags to CYF_FREE.  We don't need a membar_enter()
	 * between zeroing pend and setting the flags because we're at
	 * CY_HIGH_LEVEL (that is, the zeroing of pend and the setting
	 * of cy_flags appear atomic to softints).
	 */
	cyclic->cy_flags = CYF_FREE;

	for (i = 0; i < nelems; i++) {
		if (heap[i] == ndx)
			break;
	}

	if (i == nelems)
		panic("attempt to remove non-existent cyclic");

	cpu->cyp_nelems = --nelems;

	if (nelems == 0) {
		/*
		 * If we just removed the last element, then we need to
		 * disable the backend on this CPU.
		 */
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "disabled");
		be->cyb_disable(bar);
	}

	if (i == nelems) {
		/*
		 * If we just removed the last element of the heap, then
		 * we don't have to downheap.
		 */
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-bottom");
		goto out;
	}

#ifdef DEBUG
	root = heap[0];
#endif

	/*
	 * Swap the last element of the heap with the one we want to
	 * remove, and downheap (this has the implicit effect of putting
	 * the newly freed element on the free list).
	 */
	heap[i] = (last = heap[nelems]);
	heap[nelems] = ndx;

	if (i == 0) {
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-root");
		cyclic_downheap(cpu, 0);
	} else {
		if (cyclic_upheap(cpu, i) == 0) {
			/*
			 * The upheap didn't propagate to the root; if it
			 * didn't propagate at all, we need to downheap.
			 */
			CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-no-root");
			if (heap[i] == last) {
				CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-no-up");
				cyclic_downheap(cpu, i);
			}
			ASSERT(heap[0] == root);
			goto out;
		}
	}

	/*
	 * We're here because we changed the root; we need to reprogram
	 * the clock source.
	 */
	cyclic = &cpu->cyp_cyclics[heap[0]];

	CYC_TRACE0(cpu, CY_HIGH_LEVEL, "remove-reprog");

	ASSERT(nelems != 0);
	be->cyb_reprogram(bar, cyclic->cy_expire);
out:
	be->cyb_restore_level(bar, cookie);
}

static int
cyclic_remove_here(cyc_cpu_t *cpu, cyc_index_t ndx, cyc_time_t *when, int wait)
{
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_xcallarg_t arg;
	cyclic_t *cyclic = &cpu->cyp_cyclics[ndx];
	cyc_level_t level = cyclic->cy_level;

	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_rpend == 0);
	ASSERT(wait == CY_WAIT || wait == CY_NOWAIT);

	arg.cyx_ndx = ndx;
	arg.cyx_cpu = cpu;
	arg.cyx_when = when;
	arg.cyx_wait = wait;

	ASSERT(cpu->cyp_state == CYS_ONLINE);
	cpu->cyp_state = CYS_REMOVING;

	be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
	    (cyc_func_t)cyclic_remove_xcall, &arg);

	/*
	 * If the cyclic we removed wasn't at CY_HIGH_LEVEL, then we need to
	 * check the cyp_rpend.  If it's non-zero, then we need to wait here
	 * for all pending cyclic handlers to run.
	 */
	ASSERT(!(level == CY_HIGH_LEVEL && cpu->cyp_rpend != 0));
	ASSERT(!(wait == CY_NOWAIT && cpu->cyp_rpend != 0));
	ASSERT(!(arg.cyx_wait == CY_NOWAIT && cpu->cyp_rpend != 0));

	if (wait != arg.cyx_wait) {
		/*
		 * We are being told that we must wait if we want to
		 * remove this cyclic; put the CPU back in the CYS_ONLINE
		 * state and return failure.
		 */
		ASSERT(wait == CY_NOWAIT && arg.cyx_wait == CY_WAIT);
		ASSERT(cpu->cyp_state == CYS_REMOVING);
		cpu->cyp_state = CYS_ONLINE;

		return (0);
	}

	if (cpu->cyp_rpend != 0)
		sema_p(&cpu->cyp_modify_wait);

	ASSERT(cpu->cyp_state == CYS_REMOVING);

	cpu->cyp_rpend = 0;
	cpu->cyp_state = CYS_ONLINE;

	return (1);
}

/*
 * If cyclic_reprogram() is called on the same CPU as the cyclic's CPU, then
 * it calls this function directly. Else, it invokes this function through
 * an X-call to the cyclic's CPU.
 */
static void
cyclic_reprogram_cyclic(cyc_cpu_t *cpu, cyc_index_t ndx, hrtime_t expire)
{
	cyc_backend_t *be = cpu->cyp_backend;
	cyb_arg_t bar = be->cyb_arg;
	cyc_cookie_t cookie;
	cyc_index_t nelems, i;
	cyc_index_t *heap;
	cyclic_t *cyclic;
	hrtime_t oexpire;
	int reprog;

	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-xcall", ndx);

	nelems = cpu->cyp_nelems;
	ASSERT(nelems > 0);
	heap = cpu->cyp_heap;

	/*
	 * Reprogrammed cyclics are typically one-shot ones that get
	 * set to infinity on every expiration. We shorten the search by
	 * searching from the bottom of the heap to the top instead of the
	 * other way around.
	 */
	for (i = nelems - 1; i >= 0; i--) {
		if (heap[i] == ndx)
			break;
	}
	if (i < 0)
		panic("attempt to reprogram non-existent cyclic");

	cyclic = &cpu->cyp_cyclics[ndx];
	oexpire = cyclic->cy_expire;
	cyclic->cy_expire = expire;

	reprog = (i == 0);
	if (expire > oexpire) {
		CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-down", i);
		cyclic_downheap(cpu, i);
	} else if (i > 0) {
		CYC_TRACE1(cpu, CY_HIGH_LEVEL, "reprog-up", i);
		reprog = cyclic_upheap(cpu, i);
	}

	if (reprog && (cpu->cyp_state != CYS_SUSPENDED)) {
		/*
		 * The root changed. Reprogram the clock source.
		 */
		CYC_TRACE0(cpu, CY_HIGH_LEVEL, "reprog-root");
		cyclic = &cpu->cyp_cyclics[heap[0]];
		be->cyb_reprogram(bar, cyclic->cy_expire);
	}

	be->cyb_restore_level(bar, cookie);
}

static void
cyclic_reprogram_xcall(cyc_xcallarg_t *arg)
{
	cyclic_reprogram_cyclic(arg->cyx_cpu, arg->cyx_ndx,
	    arg->cyx_when->cyt_when);
}

static void
cyclic_reprogram_here(cyc_cpu_t *cpu, cyc_index_t ndx, hrtime_t expiration)
{
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_xcallarg_t arg;
	cyc_time_t when;

	ASSERT(expiration > 0);

	arg.cyx_ndx = ndx;
	arg.cyx_cpu = cpu;
	arg.cyx_when = &when;
	when.cyt_when = expiration;

	be->cyb_xcall(be->cyb_arg, cpu->cyp_cpu,
	    (cyc_func_t)cyclic_reprogram_xcall, &arg);
}

/*
 * cyclic_juggle_one_to() should only be called when the source cyclic
 * can be juggled and the destination CPU is known to be able to accept
 * it.
 */
static void
cyclic_juggle_one_to(cyc_id_t *idp, cyc_cpu_t *dest)
{
	cyc_cpu_t *src = idp->cyi_cpu;
	cyc_index_t ndx = idp->cyi_ndx;
	cyc_time_t when;
	cyc_handler_t hdlr;
	cyclic_t *cyclic;
	uint16_t flags;
	hrtime_t delay;

	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(src != NULL && idp->cyi_omni_list == NULL);
	ASSERT(!(dest->cyp_cpu->cpu_flags & (CPU_QUIESCED | CPU_OFFLINE)));
	CYC_PTRACE("juggle-one-to", idp, dest);

	cyclic = &src->cyp_cyclics[ndx];

	flags = cyclic->cy_flags;
	ASSERT(!(flags & CYF_CPU_BOUND) && !(flags & CYF_FREE));

	hdlr.cyh_func = cyclic->cy_handler;
	hdlr.cyh_level = cyclic->cy_level;
	hdlr.cyh_arg = cyclic->cy_arg;

	/*
	 * Before we begin the juggling process, see if the destination
	 * CPU requires an expansion.  If it does, we'll perform the
	 * expansion before removing the cyclic.  This is to prevent us
	 * from blocking while a system-critical cyclic (notably, the clock
	 * cyclic) isn't on a CPU.
	 */
	if (dest->cyp_nelems == dest->cyp_size) {
		CYC_PTRACE("remove-expand", idp, dest);
		cyclic_expand(dest);
		ASSERT(dest->cyp_nelems < dest->cyp_size);
	}

	/*
	 * Prevent a reprogram of this cyclic while we are relocating it.
	 * Otherwise, cyclic_reprogram_here() will end up sending an X-call
	 * to the wrong CPU.
	 */
	rw_enter(&idp->cyi_lock, RW_WRITER);

	/*
	 * Remove the cyclic from the source.  As mentioned above, we cannot
	 * block during this operation; if we cannot remove the cyclic
	 * without waiting, we spin for a time shorter than the interval, and
	 * reattempt the (non-blocking) removal.  If we continue to fail,
	 * we will exponentially back off (up to half of the interval).
	 * Note that the removal will ultimately succeed -- even if the
	 * cyclic handler is blocked on a resource held by a thread which we
	 * have preempted, priority inheritance assures that the preempted
	 * thread will preempt us and continue to progress.
	 */
	for (delay = NANOSEC / MICROSEC; ; delay <<= 1) {
		/*
		 * Before we begin this operation, disable kernel preemption.
		 */
		kpreempt_disable();
		if (cyclic_remove_here(src, ndx, &when, CY_NOWAIT))
			break;

		/*
		 * The operation failed; enable kernel preemption while
		 * spinning.
		 */
		kpreempt_enable();

		CYC_PTRACE("remove-retry", idp, src);

		if (delay > (cyclic->cy_interval >> 1))
			delay = cyclic->cy_interval >> 1;

		/*
		 * Drop the RW lock to avoid a deadlock with the cyclic
		 * handler (because it can potentially call cyclic_reprogram().
		 */
		rw_exit(&idp->cyi_lock);
		drv_usecwait((clock_t)(delay / (NANOSEC / MICROSEC)));
		rw_enter(&idp->cyi_lock, RW_WRITER);
	}

	/*
	 * Now add the cyclic to the destination.  This won't block; we
	 * performed any necessary (blocking) expansion of the destination
	 * CPU before removing the cyclic from the source CPU.
	 */
	idp->cyi_ndx = cyclic_add_here(dest, &hdlr, &when, flags);
	idp->cyi_cpu = dest;
	kpreempt_enable();

	/*
	 * Now that we have successfully relocated the cyclic, allow
	 * it to be reprogrammed.
	 */
	rw_exit(&idp->cyi_lock);
}

static int
cyclic_juggle_one(cyc_id_t *idp)
{
	cyc_index_t ndx = idp->cyi_ndx;
	cyc_cpu_t *cpu = idp->cyi_cpu, *dest;
	cyclic_t *cyclic = &cpu->cyp_cyclics[ndx];
	cpu_t *c = cpu->cyp_cpu;
	cpupart_t *part = c->cpu_part;

	CYC_PTRACE("juggle-one", idp, cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(!(c->cpu_flags & CPU_OFFLINE));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(!(cyclic->cy_flags & CYF_FREE));

	if ((dest = cyclic_pick_cpu(part, c, c, cyclic->cy_flags)) == NULL) {
		/*
		 * Bad news:  this cyclic can't be juggled.
		 */
		CYC_PTRACE("juggle-fail", idp, cpu)
		return (0);
	}

	cyclic_juggle_one_to(idp, dest);

	return (1);
}

static void
cyclic_unbind_cpu(cyclic_id_t id)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *cpu = idp->cyi_cpu;
	cpu_t *c = cpu->cyp_cpu;
	cyclic_t *cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];

	CYC_PTRACE("unbind-cpu", id, cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(!(cyclic->cy_flags & CYF_FREE));
	ASSERT(cyclic->cy_flags & CYF_CPU_BOUND);

	cyclic->cy_flags &= ~CYF_CPU_BOUND;

	/*
	 * If we were bound to CPU which has interrupts disabled, we need
	 * to juggle away.  This can only fail if we are bound to a
	 * processor set, and if every CPU in the processor set has
	 * interrupts disabled.
	 */
	if (!(c->cpu_flags & CPU_ENABLE)) {
		int res = cyclic_juggle_one(idp);

		ASSERT((res && idp->cyi_cpu != cpu) ||
		    (!res && (cyclic->cy_flags & CYF_PART_BOUND)));
	}
}

static void
cyclic_bind_cpu(cyclic_id_t id, cpu_t *d)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *dest = d->cpu_cyclic, *cpu = idp->cyi_cpu;
	cpu_t *c = cpu->cyp_cpu;
	cyclic_t *cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];
	cpupart_t *part = c->cpu_part;

	CYC_PTRACE("bind-cpu", id, dest);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(!(d->cpu_flags & CPU_OFFLINE));
	ASSERT(!(c->cpu_flags & CPU_OFFLINE));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(dest != NULL);
	ASSERT(dest->cyp_state == CYS_ONLINE);
	ASSERT(!(cyclic->cy_flags & CYF_FREE));
	ASSERT(!(cyclic->cy_flags & CYF_CPU_BOUND));

	dest = cyclic_pick_cpu(part, d, NULL, cyclic->cy_flags | CYF_CPU_BOUND);

	if (dest != cpu) {
		cyclic_juggle_one_to(idp, dest);
		cyclic = &dest->cyp_cyclics[idp->cyi_ndx];
	}

	cyclic->cy_flags |= CYF_CPU_BOUND;
}

static void
cyclic_unbind_cpupart(cyclic_id_t id)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *cpu = idp->cyi_cpu;
	cpu_t *c = cpu->cyp_cpu;
	cyclic_t *cyc = &cpu->cyp_cyclics[idp->cyi_ndx];

	CYC_PTRACE("unbind-part", idp, c->cpu_part);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(!(cyc->cy_flags & CYF_FREE));
	ASSERT(cyc->cy_flags & CYF_PART_BOUND);

	cyc->cy_flags &= ~CYF_PART_BOUND;

	/*
	 * If we're on a CPU which has interrupts disabled (and if this cyclic
	 * isn't bound to the CPU), we need to juggle away.
	 */
	if (!(c->cpu_flags & CPU_ENABLE) && !(cyc->cy_flags & CYF_CPU_BOUND)) {
		int res = cyclic_juggle_one(idp);

		ASSERT(res && idp->cyi_cpu != cpu);
	}
}

static void
cyclic_bind_cpupart(cyclic_id_t id, cpupart_t *part)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *cpu = idp->cyi_cpu, *dest;
	cpu_t *c = cpu->cyp_cpu;
	cyclic_t *cyc = &cpu->cyp_cyclics[idp->cyi_ndx];

	CYC_PTRACE("bind-part", idp, part);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(!(c->cpu_flags & CPU_OFFLINE));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(!(cyc->cy_flags & CYF_FREE));
	ASSERT(!(cyc->cy_flags & CYF_PART_BOUND));
	ASSERT(part->cp_ncpus > 0);

	dest = cyclic_pick_cpu(part, c, NULL, cyc->cy_flags | CYF_PART_BOUND);

	if (dest != cpu) {
		cyclic_juggle_one_to(idp, dest);
		cyc = &dest->cyp_cyclics[idp->cyi_ndx];
	}

	cyc->cy_flags |= CYF_PART_BOUND;
}

static void
cyclic_configure(cpu_t *c)
{
	cyc_cpu_t *cpu = kmem_zalloc(sizeof (cyc_cpu_t), KM_SLEEP);
	cyc_backend_t *nbe = kmem_zalloc(sizeof (cyc_backend_t), KM_SLEEP);
	int i;

	CYC_PTRACE1("configure", cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));

	if (cyclic_id_cache == NULL)
		cyclic_id_cache = kmem_cache_create("cyclic_id_cache",
		    sizeof (cyc_id_t), 0, NULL, NULL, NULL, NULL, NULL, 0);

	cpu->cyp_cpu = c;

	sema_init(&cpu->cyp_modify_wait, 0, NULL, SEMA_DEFAULT, NULL);

	cpu->cyp_size = 1;
	cpu->cyp_heap = kmem_zalloc(sizeof (cyc_index_t), KM_SLEEP);
	cpu->cyp_cyclics = kmem_zalloc(sizeof (cyclic_t), KM_SLEEP);
	cpu->cyp_cyclics->cy_flags = CYF_FREE;

	for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
		/*
		 * We don't need to set the sizemask; it's already zero
		 * (which is the appropriate sizemask for a size of 1).
		 */
		cpu->cyp_softbuf[i].cys_buf[0].cypc_buf =
		    kmem_alloc(sizeof (cyc_index_t), KM_SLEEP);
	}

	cpu->cyp_state = CYS_OFFLINE;

	/*
	 * Setup the backend for this CPU.
	 */
	bcopy(&cyclic_backend, nbe, sizeof (cyc_backend_t));
	nbe->cyb_arg = nbe->cyb_configure(c);
	cpu->cyp_backend = nbe;

	/*
	 * On platforms where stray interrupts may be taken during startup,
	 * the CPU's cpu_cyclic pointer serves as an indicator that the
	 * cyclic subsystem for this CPU is prepared to field interrupts.
	 */
	membar_producer();

	c->cpu_cyclic = cpu;
}

static void
cyclic_unconfigure(cpu_t *c)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_backend_t *be = cpu->cyp_backend;
	cyb_arg_t bar = be->cyb_arg;
	int i;

	CYC_PTRACE1("unconfigure", cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_OFFLINE);
	ASSERT(cpu->cyp_nelems == 0);

	/*
	 * Let the backend know that the CPU is being yanked, and free up
	 * the backend structure.
	 */
	be->cyb_unconfigure(bar);
	kmem_free(be, sizeof (cyc_backend_t));
	cpu->cyp_backend = NULL;

	/*
	 * Free up the producer/consumer buffers at each of the soft levels.
	 */
	for (i = CY_LOW_LEVEL; i < CY_LOW_LEVEL + CY_SOFT_LEVELS; i++) {
		cyc_softbuf_t *softbuf = &cpu->cyp_softbuf[i];
		uchar_t hard = softbuf->cys_hard;
		cyc_pcbuffer_t *pc = &softbuf->cys_buf[hard];
		size_t bufsize = sizeof (cyc_index_t) * (pc->cypc_sizemask + 1);

		/*
		 * Assert that we're not in the middle of a resize operation.
		 */
		ASSERT(hard == softbuf->cys_soft);
		ASSERT(hard == 0 || hard == 1);
		ASSERT(pc->cypc_buf != NULL);
		ASSERT(softbuf->cys_buf[hard ^ 1].cypc_buf == NULL);

		kmem_free(pc->cypc_buf, bufsize);
		pc->cypc_buf = NULL;
	}

	/*
	 * Finally, clean up our remaining dynamic structures and NULL out
	 * the cpu_cyclic pointer.
	 */
	kmem_free(cpu->cyp_cyclics, cpu->cyp_size * sizeof (cyclic_t));
	kmem_free(cpu->cyp_heap, cpu->cyp_size * sizeof (cyc_index_t));
	kmem_free(cpu, sizeof (cyc_cpu_t));

	c->cpu_cyclic = NULL;
}

static int
cyclic_cpu_setup(cpu_setup_t what, int id)
{
	/*
	 * We are guaranteed that there is still/already an entry in the
	 * cpu array for this CPU.
	 */
	cpu_t *c = cpu[id];
	cyc_cpu_t *cyp = c->cpu_cyclic;

	ASSERT(MUTEX_HELD(&cpu_lock));

	switch (what) {
	case CPU_CONFIG:
		ASSERT(cyp == NULL);
		cyclic_configure(c);
		break;

	case CPU_UNCONFIG:
		ASSERT(cyp != NULL && cyp->cyp_state == CYS_OFFLINE);
		cyclic_unconfigure(c);
		break;

	default:
		break;
	}

	return (0);
}

static void
cyclic_suspend_xcall(cyc_xcallarg_t *arg)
{
	cyc_cpu_t *cpu = arg->cyx_cpu;
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_cookie_t cookie;
	cyb_arg_t bar = be->cyb_arg;

	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE1(cpu, CY_HIGH_LEVEL, "suspend-xcall", cpu->cyp_nelems);
	ASSERT(cpu->cyp_state == CYS_ONLINE || cpu->cyp_state == CYS_OFFLINE);

	/*
	 * We won't disable this CPU unless it has a non-zero number of
	 * elements (cpu_lock assures that no one else may be attempting
	 * to disable this CPU).
	 */
	if (cpu->cyp_nelems > 0) {
		ASSERT(cpu->cyp_state == CYS_ONLINE);
		be->cyb_disable(bar);
	}

	if (cpu->cyp_state == CYS_ONLINE)
		cpu->cyp_state = CYS_SUSPENDED;

	be->cyb_suspend(bar);
	be->cyb_restore_level(bar, cookie);
}

static void
cyclic_resume_xcall(cyc_xcallarg_t *arg)
{
	cyc_cpu_t *cpu = arg->cyx_cpu;
	cyc_backend_t *be = cpu->cyp_backend;
	cyc_cookie_t cookie;
	cyb_arg_t bar = be->cyb_arg;
	cyc_state_t state = cpu->cyp_state;

	cookie = be->cyb_set_level(bar, CY_HIGH_LEVEL);

	CYC_TRACE1(cpu, CY_HIGH_LEVEL, "resume-xcall", cpu->cyp_nelems);
	ASSERT(state == CYS_SUSPENDED || state == CYS_OFFLINE);

	be->cyb_resume(bar);

	/*
	 * We won't enable this CPU unless it has a non-zero number of
	 * elements.
	 */
	if (cpu->cyp_nelems > 0) {
		cyclic_t *cyclic = &cpu->cyp_cyclics[cpu->cyp_heap[0]];
		hrtime_t exp = cyclic->cy_expire;

		CYC_TRACE(cpu, CY_HIGH_LEVEL, "resume-reprog", cyclic, exp);
		ASSERT(state == CYS_SUSPENDED);
		be->cyb_enable(bar);
		be->cyb_reprogram(bar, exp);
	}

	if (state == CYS_SUSPENDED)
		cpu->cyp_state = CYS_ONLINE;

	CYC_TRACE1(cpu, CY_HIGH_LEVEL, "resume-done", cpu->cyp_nelems);
	be->cyb_restore_level(bar, cookie);
}

static void
cyclic_omni_start(cyc_id_t *idp, cyc_cpu_t *cpu)
{
	cyc_omni_handler_t *omni = &idp->cyi_omni_hdlr;
	cyc_omni_cpu_t *ocpu = kmem_alloc(sizeof (cyc_omni_cpu_t), KM_SLEEP);
	cyc_handler_t hdlr;
	cyc_time_t when;

	CYC_PTRACE("omni-start", cpu, idp);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(idp->cyi_cpu == NULL);

	hdlr.cyh_func = NULL;
	hdlr.cyh_arg = NULL;
	hdlr.cyh_level = CY_LEVELS;

	when.cyt_when = 0;
	when.cyt_interval = 0;

	omni->cyo_online(omni->cyo_arg, cpu->cyp_cpu, &hdlr, &when);

	ASSERT(hdlr.cyh_func != NULL);
	ASSERT(hdlr.cyh_level < CY_LEVELS);
	ASSERT(when.cyt_when >= 0 && when.cyt_interval > 0);

	ocpu->cyo_cpu = cpu;
	ocpu->cyo_arg = hdlr.cyh_arg;
	ocpu->cyo_ndx = cyclic_add_here(cpu, &hdlr, &when, 0);
	ocpu->cyo_next = idp->cyi_omni_list;
	idp->cyi_omni_list = ocpu;
}

static void
cyclic_omni_stop(cyc_id_t *idp, cyc_cpu_t *cpu)
{
	cyc_omni_handler_t *omni = &idp->cyi_omni_hdlr;
	cyc_omni_cpu_t *ocpu = idp->cyi_omni_list, *prev = NULL;
	clock_t delay;
	int ret;

	CYC_PTRACE("omni-stop", cpu, idp);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_ONLINE);
	ASSERT(idp->cyi_cpu == NULL);
	ASSERT(ocpu != NULL);

	/*
	 * Prevent a reprogram of this cyclic while we are removing it.
	 * Otherwise, cyclic_reprogram_here() will end up sending an X-call
	 * to the offlined CPU.
	 */
	rw_enter(&idp->cyi_lock, RW_WRITER);

	while (ocpu != NULL && ocpu->cyo_cpu != cpu) {
		prev = ocpu;
		ocpu = ocpu->cyo_next;
	}

	/*
	 * We _must_ have found an cyc_omni_cpu which corresponds to this
	 * CPU -- the definition of an omnipresent cyclic is that it runs
	 * on all online CPUs.
	 */
	ASSERT(ocpu != NULL);

	if (prev == NULL) {
		idp->cyi_omni_list = ocpu->cyo_next;
	} else {
		prev->cyo_next = ocpu->cyo_next;
	}

	/*
	 * Remove the cyclic from the source.  We cannot block during this
	 * operation because we are holding the cyi_lock which can be held
	 * by the cyclic handler via cyclic_reprogram().
	 *
	 * If we cannot remove the cyclic without waiting, we spin for a time,
	 * and reattempt the (non-blocking) removal. If the handler is blocked
	 * on the cyi_lock, then we let go of it in the spin loop to give
	 * the handler a chance to run. Note that the removal will ultimately
	 * succeed -- even if the cyclic handler is blocked on a resource
	 * held by a thread which we have preempted, priority inheritance
	 * assures that the preempted thread will preempt us and continue
	 * to progress.
	 */
	for (delay = 1; ; delay <<= 1) {
		/*
		 * Before we begin this operation, disable kernel preemption.
		 */
		kpreempt_disable();
		ret = cyclic_remove_here(ocpu->cyo_cpu, ocpu->cyo_ndx, NULL,
		    CY_NOWAIT);
		/*
		 * Enable kernel preemption while spinning.
		 */
		kpreempt_enable();

		if (ret)
			break;

		CYC_PTRACE("remove-omni-retry", idp, ocpu->cyo_cpu);

		/*
		 * Drop the RW lock to avoid a deadlock with the cyclic
		 * handler (because it can potentially call cyclic_reprogram().
		 */
		rw_exit(&idp->cyi_lock);
		drv_usecwait(delay);
		rw_enter(&idp->cyi_lock, RW_WRITER);
	}

	/*
	 * Now that we have successfully removed the cyclic, allow the omni
	 * cyclic to be reprogrammed on other CPUs.
	 */
	rw_exit(&idp->cyi_lock);

	/*
	 * The cyclic has been removed from this CPU; time to call the
	 * omnipresent offline handler.
	 */
	if (omni->cyo_offline != NULL)
		omni->cyo_offline(omni->cyo_arg, cpu->cyp_cpu, ocpu->cyo_arg);

	kmem_free(ocpu, sizeof (cyc_omni_cpu_t));
}

static cyc_id_t *
cyclic_new_id()
{
	cyc_id_t *idp;

	ASSERT(MUTEX_HELD(&cpu_lock));

	idp = kmem_cache_alloc(cyclic_id_cache, KM_SLEEP);

	/*
	 * The cyi_cpu field of the cyc_id_t structure tracks the CPU
	 * associated with the cyclic.  If and only if this field is NULL, the
	 * cyc_id_t is an omnipresent cyclic.  Note that cyi_omni_list may be
	 * NULL for an omnipresent cyclic while the cyclic is being created
	 * or destroyed.
	 */
	idp->cyi_cpu = NULL;
	idp->cyi_ndx = 0;
	rw_init(&idp->cyi_lock, NULL, RW_DEFAULT, NULL);

	idp->cyi_next = cyclic_id_head;
	idp->cyi_prev = NULL;
	idp->cyi_omni_list = NULL;

	if (cyclic_id_head != NULL) {
		ASSERT(cyclic_id_head->cyi_prev == NULL);
		cyclic_id_head->cyi_prev = idp;
	}

	cyclic_id_head = idp;

	return (idp);
}

/*
 *  cyclic_id_t cyclic_add(cyc_handler_t *, cyc_time_t *)
 *
 *  Overview
 *
 *    cyclic_add() will create an unbound cyclic with the specified handler and
 *    interval.  The cyclic will run on a CPU which both has interrupts enabled
 *    and is in the system CPU partition.
 *
 *  Arguments and notes
 *
 *    As its first argument, cyclic_add() takes a cyc_handler, which has the
 *    following members:
 *
 *      cyc_func_t cyh_func    <-- Cyclic handler
 *      void *cyh_arg          <-- Argument to cyclic handler
 *      cyc_level_t cyh_level  <-- Level at which to fire; must be one of
 *                                 CY_LOW_LEVEL, CY_LOCK_LEVEL or CY_HIGH_LEVEL
 *
 *    Note that cyh_level is _not_ an ipl or spl; it must be one the
 *    CY_*_LEVELs.  This layer of abstraction allows the platform to define
 *    the precise interrupt priority levels, within the following constraints:
 *
 *       CY_LOCK_LEVEL must map to LOCK_LEVEL
 *       CY_HIGH_LEVEL must map to an ipl greater than LOCK_LEVEL
 *       CY_LOW_LEVEL must map to an ipl below LOCK_LEVEL
 *
 *    In addition to a cyc_handler, cyclic_add() takes a cyc_time, which
 *    has the following members:
 *
 *       hrtime_t cyt_when     <-- Absolute time, in nanoseconds since boot, at
 *                                 which to start firing
 *       hrtime_t cyt_interval <-- Length of interval, in nanoseconds
 *
 *    gethrtime() is the time source for nanoseconds since boot.  If cyt_when
 *    is set to 0, the cyclic will start to fire when cyt_interval next
 *    divides the number of nanoseconds since boot.
 *
 *    The cyt_interval field _must_ be filled in by the caller; one-shots are
 *    _not_ explicitly supported by the cyclic subsystem (cyclic_add() will
 *    assert that cyt_interval is non-zero).  The maximum value for either
 *    field is INT64_MAX; the caller is responsible for assuring that
 *    cyt_when + cyt_interval <= INT64_MAX.  Neither field may be negative.
 *
 *    For an arbitrary time t in the future, the cyclic handler is guaranteed
 *    to have been called (t - cyt_when) / cyt_interval times.  This will
 *    be true even if interrupts have been disabled for periods greater than
 *    cyt_interval nanoseconds.  In order to compensate for such periods,
 *    the cyclic handler may be called a finite number of times with an
 *    arbitrarily small interval.
 *
 *    The cyclic subsystem will not enforce any lower bound on the interval;
 *    if the interval is less than the time required to process an interrupt,
 *    the CPU will wedge.  It's the responsibility of the caller to assure that
 *    either the value of the interval is sane, or that its caller has
 *    sufficient privilege to deny service (i.e. its caller is root).
 *
 *    The cyclic handler is guaranteed to be single threaded, even while the
 *    cyclic is being juggled between CPUs (see cyclic_juggle(), below).
 *    That is, a given cyclic handler will never be executed simultaneously
 *    on different CPUs.
 *
 *  Return value
 *
 *    cyclic_add() returns a cyclic_id_t, which is guaranteed to be a value
 *    other than CYCLIC_NONE.  cyclic_add() cannot fail.
 *
 *  Caller's context
 *
 *    cpu_lock must be held by the caller, and the caller must not be in
 *    interrupt context.  cyclic_add() will perform a KM_SLEEP kernel
 *    memory allocation, so the usual rules (e.g. p_lock cannot be held)
 *    apply.  A cyclic may be added even in the presence of CPUs that have
 *    not been configured with respect to the cyclic subsystem, but only
 *    configured CPUs will be eligible to run the new cyclic.
 *
 *  Cyclic handler's context
 *
 *    Cyclic handlers will be executed in the interrupt context corresponding
 *    to the specified level (i.e. either high, lock or low level).  The
 *    usual context rules apply.
 *
 *    A cyclic handler may not grab ANY locks held by the caller of any of
 *    cyclic_add(), cyclic_remove() or cyclic_bind(); the implementation of
 *    these functions may require blocking on cyclic handler completion.
 *    Moreover, cyclic handlers may not make any call back into the cyclic
 *    subsystem.
 */
cyclic_id_t
cyclic_add(cyc_handler_t *hdlr, cyc_time_t *when)
{
	cyc_id_t *idp = cyclic_new_id();

	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(when->cyt_when >= 0 && when->cyt_interval > 0);

	idp->cyi_cpu = cyclic_pick_cpu(NULL, NULL, NULL, 0);
	idp->cyi_ndx = cyclic_add_here(idp->cyi_cpu, hdlr, when, 0);

	return ((uintptr_t)idp);
}

/*
 *  cyclic_id_t cyclic_add_omni(cyc_omni_handler_t *)
 *
 *  Overview
 *
 *    cyclic_add_omni() will create an omnipresent cyclic with the specified
 *    online and offline handlers.  Omnipresent cyclics run on all online
 *    CPUs, including CPUs which have unbound interrupts disabled.
 *
 *  Arguments
 *
 *    As its only argument, cyclic_add_omni() takes a cyc_omni_handler, which
 *    has the following members:
 *
 *      void (*cyo_online)()   <-- Online handler
 *      void (*cyo_offline)()  <-- Offline handler
 *      void *cyo_arg          <-- Argument to be passed to on/offline handlers
 *
 *  Online handler
 *
 *    The cyo_online member is a pointer to a function which has the following
 *    four arguments:
 *
 *      void *                 <-- Argument (cyo_arg)
 *      cpu_t *                <-- Pointer to CPU about to be onlined
 *      cyc_handler_t *        <-- Pointer to cyc_handler_t; must be filled in
 *                                 by omni online handler
 *      cyc_time_t *           <-- Pointer to cyc_time_t; must be filled in by
 *                                 omni online handler
 *
 *    The omni cyclic online handler is always called _before_ the omni
 *    cyclic begins to fire on the specified CPU.  As the above argument
 *    description implies, the online handler must fill in the two structures
 *    passed to it:  the cyc_handler_t and the cyc_time_t.  These are the
 *    same two structures passed to cyclic_add(), outlined above.  This
 *    allows the omni cyclic to have maximum flexibility; different CPUs may
 *    optionally
 *
 *      (a)  have different intervals
 *      (b)  be explicitly in or out of phase with one another
 *      (c)  have different handlers
 *      (d)  have different handler arguments
 *      (e)  fire at different levels
 *
 *    Of these, (e) seems somewhat dubious, but is nonetheless allowed.
 *
 *    The omni online handler is called in the same context as cyclic_add(),
 *    and has the same liberties:  omni online handlers may perform KM_SLEEP
 *    kernel memory allocations, and may grab locks which are also acquired
 *    by cyclic handlers.  However, omni cyclic online handlers may _not_
 *    call back into the cyclic subsystem, and should be generally careful
 *    about calling into arbitrary kernel subsystems.
 *
 *  Offline handler
 *
 *    The cyo_offline member is a pointer to a function which has the following
 *    three arguments:
 *
 *      void *                 <-- Argument (cyo_arg)
 *      cpu_t *                <-- Pointer to CPU about to be offlined
 *      void *                 <-- CPU's cyclic argument (that is, value
 *                                 to which cyh_arg member of the cyc_handler_t
 *                                 was set in the omni online handler)
 *
 *    The omni cyclic offline handler is always called _after_ the omni
 *    cyclic has ceased firing on the specified CPU.  Its purpose is to
 *    allow cleanup of any resources dynamically allocated in the omni cyclic
 *    online handler.  The context of the offline handler is identical to
 *    that of the online handler; the same constraints and liberties apply.
 *
 *    The offline handler is optional; it may be NULL.
 *
 *  Return value
 *
 *    cyclic_add_omni() returns a cyclic_id_t, which is guaranteed to be a
 *    value other than CYCLIC_NONE.  cyclic_add_omni() cannot fail.
 *
 *  Caller's context
 *
 *    The caller's context is identical to that of cyclic_add(), specified
 *    above.
 */
cyclic_id_t
cyclic_add_omni(cyc_omni_handler_t *omni)
{
	cyc_id_t *idp = cyclic_new_id();
	cyc_cpu_t *cpu;
	cpu_t *c;

	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(omni != NULL && omni->cyo_online != NULL);

	idp->cyi_omni_hdlr = *omni;

	c = cpu_list;
	do {
		if ((cpu = c->cpu_cyclic) == NULL)
			continue;

		if (cpu->cyp_state != CYS_ONLINE) {
			ASSERT(cpu->cyp_state == CYS_OFFLINE);
			continue;
		}

		cyclic_omni_start(idp, cpu);
	} while ((c = c->cpu_next) != cpu_list);

	/*
	 * We must have found at least one online CPU on which to run
	 * this cyclic.
	 */
	ASSERT(idp->cyi_omni_list != NULL);
	ASSERT(idp->cyi_cpu == NULL);

	return ((uintptr_t)idp);
}

/*
 *  void cyclic_remove(cyclic_id_t)
 *
 *  Overview
 *
 *    cyclic_remove() will remove the specified cyclic from the system.
 *
 *  Arguments and notes
 *
 *    The only argument is a cyclic_id returned from either cyclic_add() or
 *    cyclic_add_omni().
 *
 *    By the time cyclic_remove() returns, the caller is guaranteed that the
 *    removed cyclic handler has completed execution (this is the same
 *    semantic that untimeout() provides).  As a result, cyclic_remove() may
 *    need to block, waiting for the removed cyclic to complete execution.
 *    This leads to an important constraint on the caller:  no lock may be
 *    held across cyclic_remove() that also may be acquired by a cyclic
 *    handler.
 *
 *  Return value
 *
 *    None; cyclic_remove() always succeeds.
 *
 *  Caller's context
 *
 *    cpu_lock must be held by the caller, and the caller must not be in
 *    interrupt context.  The caller may not hold any locks which are also
 *    grabbed by any cyclic handler.  See "Arguments and notes", above.
 */
void
cyclic_remove(cyclic_id_t id)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_id_t *prev = idp->cyi_prev, *next = idp->cyi_next;
	cyc_cpu_t *cpu = idp->cyi_cpu;

	CYC_PTRACE("remove", idp, idp->cyi_cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));

	if (cpu != NULL) {
		(void) cyclic_remove_here(cpu, idp->cyi_ndx, NULL, CY_WAIT);
	} else {
		ASSERT(idp->cyi_omni_list != NULL);
		while (idp->cyi_omni_list != NULL)
			cyclic_omni_stop(idp, idp->cyi_omni_list->cyo_cpu);
	}

	if (prev != NULL) {
		ASSERT(cyclic_id_head != idp);
		prev->cyi_next = next;
	} else {
		ASSERT(cyclic_id_head == idp);
		cyclic_id_head = next;
	}

	if (next != NULL)
		next->cyi_prev = prev;

	kmem_cache_free(cyclic_id_cache, idp);
}

/*
 *  void cyclic_bind(cyclic_id_t, cpu_t *, cpupart_t *)
 *
 *  Overview
 *
 *    cyclic_bind() atomically changes the CPU and CPU partition bindings
 *    of a cyclic.
 *
 *  Arguments and notes
 *
 *    The first argument is a cyclic_id retuned from cyclic_add().
 *    cyclic_bind() may _not_ be called on a cyclic_id returned from
 *    cyclic_add_omni().
 *
 *    The second argument specifies the CPU to which to bind the specified
 *    cyclic.  If the specified cyclic is bound to a CPU other than the one
 *    specified, it will be unbound from its bound CPU.  Unbinding the cyclic
 *    from its CPU may cause it to be juggled to another CPU.  If the specified
 *    CPU is non-NULL, the cyclic will be subsequently rebound to the specified
 *    CPU.
 *
 *    If a CPU with bound cyclics is transitioned into the P_NOINTR state,
 *    only cyclics not bound to the CPU can be juggled away; CPU-bound cyclics
 *    will continue to fire on the P_NOINTR CPU.  A CPU with bound cyclics
 *    cannot be offlined (attempts to offline the CPU will return EBUSY).
 *    Likewise, cyclics may not be bound to an offline CPU; if the caller
 *    attempts to bind a cyclic to an offline CPU, the cyclic subsystem will
 *    panic.
 *
 *    The third argument specifies the CPU partition to which to bind the
 *    specified cyclic.  If the specified cyclic is bound to a CPU partition
 *    other than the one specified, it will be unbound from its bound
 *    partition.  Unbinding the cyclic from its CPU partition may cause it
 *    to be juggled to another CPU.  If the specified CPU partition is
 *    non-NULL, the cyclic will be subsequently rebound to the specified CPU
 *    partition.
 *
 *    It is the caller's responsibility to assure that the specified CPU
 *    partition contains a CPU.  If it does not, the cyclic subsystem will
 *    panic.  A CPU partition with bound cyclics cannot be destroyed (attempts
 *    to destroy the partition will return EBUSY).  If a CPU with
 *    partition-bound cyclics is transitioned into the P_NOINTR state, cyclics
 *    bound to the CPU's partition (but not bound to the CPU) will be juggled
 *    away only if there exists another CPU in the partition in the P_ONLINE
 *    state.
 *
 *    It is the caller's responsibility to assure that the specified CPU and
 *    CPU partition are self-consistent.  If both parameters are non-NULL,
 *    and the specified CPU partition does not contain the specified CPU, the
 *    cyclic subsystem will panic.
 *
 *    It is the caller's responsibility to assure that the specified CPU has
 *    been configured with respect to the cyclic subsystem.  Generally, this
 *    is always true for valid, on-line CPUs.  The only periods of time during
 *    which this may not be true are during MP boot (i.e. after cyclic_init()
 *    is called but before cyclic_mp_init() is called) or during dynamic
 *    reconfiguration; cyclic_bind() should only be called with great care
 *    from these contexts.
 *
 *  Return value
 *
 *    None; cyclic_bind() always succeeds.
 *
 *  Caller's context
 *
 *    cpu_lock must be held by the caller, and the caller must not be in
 *    interrupt context.  The caller may not hold any locks which are also
 *    grabbed by any cyclic handler.
 */
void
cyclic_bind(cyclic_id_t id, cpu_t *d, cpupart_t *part)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *cpu = idp->cyi_cpu;
	cpu_t *c;
	uint16_t flags;

	CYC_PTRACE("bind", d, part);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(part == NULL || d == NULL || d->cpu_part == part);

	if (cpu == NULL) {
		ASSERT(idp->cyi_omni_list != NULL);
		panic("attempt to change binding of omnipresent cyclic");
	}

	c = cpu->cyp_cpu;
	flags = cpu->cyp_cyclics[idp->cyi_ndx].cy_flags;

	if (c != d && (flags & CYF_CPU_BOUND))
		cyclic_unbind_cpu(id);

	/*
	 * Reload our cpu (we may have migrated).  We don't have to reload
	 * the flags field here; if we were CYF_PART_BOUND on entry, we are
	 * CYF_PART_BOUND now.
	 */
	cpu = idp->cyi_cpu;
	c = cpu->cyp_cpu;

	if (part != c->cpu_part && (flags & CYF_PART_BOUND))
		cyclic_unbind_cpupart(id);

	/*
	 * Now reload the flags field, asserting that if we are CPU bound,
	 * the CPU was specified (and likewise, if we are partition bound,
	 * the partition was specified).
	 */
	cpu = idp->cyi_cpu;
	c = cpu->cyp_cpu;
	flags = cpu->cyp_cyclics[idp->cyi_ndx].cy_flags;
	ASSERT(!(flags & CYF_CPU_BOUND) || c == d);
	ASSERT(!(flags & CYF_PART_BOUND) || c->cpu_part == part);

	if (!(flags & CYF_CPU_BOUND) && d != NULL)
		cyclic_bind_cpu(id, d);

	if (!(flags & CYF_PART_BOUND) && part != NULL)
		cyclic_bind_cpupart(id, part);
}

int
cyclic_reprogram(cyclic_id_t id, hrtime_t expiration)
{
	cyc_id_t *idp = (cyc_id_t *)id;
	cyc_cpu_t *cpu;
	cyc_omni_cpu_t *ocpu;
	cyc_index_t ndx;

	ASSERT(expiration > 0);

	CYC_PTRACE("reprog", idp, idp->cyi_cpu);

	kpreempt_disable();

	/*
	 * Prevent the cyclic from moving or disappearing while we reprogram.
	 */
	rw_enter(&idp->cyi_lock, RW_READER);

	if (idp->cyi_cpu == NULL) {
		ASSERT(curthread->t_preempt > 0);
		cpu = CPU->cpu_cyclic;

		/*
		 * For an omni cyclic, we reprogram the cyclic corresponding
		 * to the current CPU. Look for it in the list.
		 */
		ocpu = idp->cyi_omni_list;
		while (ocpu != NULL) {
			if (ocpu->cyo_cpu == cpu)
				break;
			ocpu = ocpu->cyo_next;
		}

		if (ocpu == NULL) {
			/*
			 * Didn't find it. This means that CPU offline
			 * must have removed it racing with us. So,
			 * nothing to do.
			 */
			rw_exit(&idp->cyi_lock);

			kpreempt_enable();

			return (0);
		}
		ndx = ocpu->cyo_ndx;
	} else {
		cpu = idp->cyi_cpu;
		ndx = idp->cyi_ndx;
	}

	if (cpu->cyp_cpu == CPU)
		cyclic_reprogram_cyclic(cpu, ndx, expiration);
	else
		cyclic_reprogram_here(cpu, ndx, expiration);

	/*
	 * Allow the cyclic to be moved or removed.
	 */
	rw_exit(&idp->cyi_lock);

	kpreempt_enable();

	return (1);
}

hrtime_t
cyclic_getres()
{
	return (cyclic_resolution);
}

void
cyclic_init(cyc_backend_t *be, hrtime_t resolution)
{
	ASSERT(MUTEX_HELD(&cpu_lock));

	CYC_PTRACE("init", be, resolution);
	cyclic_resolution = resolution;

	/*
	 * Copy the passed cyc_backend into the backend template.  This must
	 * be done before the CPU can be configured.
	 */
	bcopy(be, &cyclic_backend, sizeof (cyc_backend_t));

	/*
	 * It's safe to look at the "CPU" pointer without disabling kernel
	 * preemption; cyclic_init() is called only during startup by the
	 * cyclic backend.
	 */
	cyclic_configure(CPU);
	cyclic_online(CPU);
}

/*
 * It is assumed that cyclic_mp_init() is called some time after cyclic
 * init (and therefore, after cpu0 has been initialized).  We grab cpu_lock,
 * find the already initialized CPU, and initialize every other CPU with the
 * same backend.  Finally, we register a cpu_setup function.
 */
void
cyclic_mp_init()
{
	cpu_t *c;

	mutex_enter(&cpu_lock);

	c = cpu_list;
	do {
		if (c->cpu_cyclic == NULL) {
			cyclic_configure(c);
			cyclic_online(c);
		}
	} while ((c = c->cpu_next) != cpu_list);

	register_cpu_setup_func((cpu_setup_func_t *)cyclic_cpu_setup, NULL);
	mutex_exit(&cpu_lock);
}

/*
 *  int cyclic_juggle(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_juggle() juggles as many cyclics as possible away from the
 *    specified CPU; all remaining cyclics on the CPU will either be CPU-
 *    or partition-bound.
 *
 *  Arguments and notes
 *
 *    The only argument to cyclic_juggle() is the CPU from which cyclics
 *    should be juggled.  CPU-bound cyclics are never juggled; partition-bound
 *    cyclics are only juggled if the specified CPU is in the P_NOINTR state
 *    and there exists a P_ONLINE CPU in the partition.  The cyclic subsystem
 *    assures that a cyclic will never fire late or spuriously, even while
 *    being juggled.
 *
 *  Return value
 *
 *    cyclic_juggle() returns a non-zero value if all cyclics were able to
 *    be juggled away from the CPU, and zero if one or more cyclics could
 *    not be juggled away.
 *
 *  Caller's context
 *
 *    cpu_lock must be held by the caller, and the caller must not be in
 *    interrupt context.  The caller may not hold any locks which are also
 *    grabbed by any cyclic handler.  While cyclic_juggle() _may_ be called
 *    in any context satisfying these constraints, it _must_ be called
 *    immediately after clearing CPU_ENABLE (i.e. before dropping cpu_lock).
 *    Failure to do so could result in an assertion failure in the cyclic
 *    subsystem.
 */
int
cyclic_juggle(cpu_t *c)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_id_t *idp;
	int all_juggled = 1;

	CYC_PTRACE1("juggle", c);
	ASSERT(MUTEX_HELD(&cpu_lock));

	/*
	 * We'll go through each cyclic on the CPU, attempting to juggle
	 * each one elsewhere.
	 */
	for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
		if (idp->cyi_cpu != cpu)
			continue;

		if (cyclic_juggle_one(idp) == 0) {
			all_juggled = 0;
			continue;
		}

		ASSERT(idp->cyi_cpu != cpu);
	}

	return (all_juggled);
}

/*
 *  int cyclic_offline(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_offline() offlines the cyclic subsystem on the specified CPU.
 *
 *  Arguments and notes
 *
 *    The only argument to cyclic_offline() is a CPU to offline.
 *    cyclic_offline() will attempt to juggle cyclics away from the specified
 *    CPU.
 *
 *  Return value
 *
 *    cyclic_offline() returns 1 if all cyclics on the CPU were juggled away
 *    and the cyclic subsystem on the CPU was successfully offlines.
 *    cyclic_offline returns 0 if some cyclics remain, blocking the cyclic
 *    offline operation.  All remaining cyclics on the CPU will either be
 *    CPU- or partition-bound.
 *
 *    See the "Arguments and notes" of cyclic_juggle(), below, for more detail
 *    on cyclic juggling.
 *
 *  Caller's context
 *
 *    The only caller of cyclic_offline() should be the processor management
 *    subsystem.  It is expected that the caller of cyclic_offline() will
 *    offline the CPU immediately after cyclic_offline() returns success (i.e.
 *    before dropping cpu_lock).  Moreover, it is expected that the caller will
 *    fail the CPU offline operation if cyclic_offline() returns failure.
 */
int
cyclic_offline(cpu_t *c)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_id_t *idp;

	CYC_PTRACE1("offline", cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));

	if (!cyclic_juggle(c))
		return (0);

	/*
	 * This CPU is headed offline; we need to now stop omnipresent
	 * cyclic firing on this CPU.
	 */
	for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
		if (idp->cyi_cpu != NULL)
			continue;

		/*
		 * We cannot possibly be offlining the last CPU; cyi_omni_list
		 * must be non-NULL.
		 */
		ASSERT(idp->cyi_omni_list != NULL);
		cyclic_omni_stop(idp, cpu);
	}

	ASSERT(cpu->cyp_state == CYS_ONLINE);
	cpu->cyp_state = CYS_OFFLINE;

	return (1);
}

/*
 *  void cyclic_online(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_online() onlines a CPU previously offlined with cyclic_offline().
 *
 *  Arguments and notes
 *
 *    cyclic_online()'s only argument is a CPU to online.  The specified
 *    CPU must have been previously offlined with cyclic_offline().  After
 *    cyclic_online() returns, the specified CPU will be eligible to execute
 *    cyclics.
 *
 *  Return value
 *
 *    None; cyclic_online() always succeeds.
 *
 *  Caller's context
 *
 *    cyclic_online() should only be called by the processor management
 *    subsystem; cpu_lock must be held.
 */
void
cyclic_online(cpu_t *c)
{
	cyc_cpu_t *cpu = c->cpu_cyclic;
	cyc_id_t *idp;

	CYC_PTRACE1("online", cpu);
	ASSERT(c->cpu_flags & CPU_ENABLE);
	ASSERT(MUTEX_HELD(&cpu_lock));
	ASSERT(cpu->cyp_state == CYS_OFFLINE);

	cpu->cyp_state = CYS_ONLINE;

	/*
	 * Now that this CPU is open for business, we need to start firing
	 * all omnipresent cyclics on it.
	 */
	for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
		if (idp->cyi_cpu != NULL)
			continue;

		cyclic_omni_start(idp, cpu);
	}
}

/*
 *  void cyclic_move_in(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_move_in() is called by the CPU partition code immediately after
 *    the specified CPU has moved into a new partition.
 *
 *  Arguments and notes
 *
 *    The only argument to cyclic_move_in() is a CPU which has moved into a
 *    new partition.  If the specified CPU is P_ONLINE, and every other
 *    CPU in the specified CPU's new partition is P_NOINTR, cyclic_move_in()
 *    will juggle all partition-bound, CPU-unbound cyclics to the specified
 *    CPU.
 *
 *  Return value
 *
 *    None; cyclic_move_in() always succeeds.
 *
 *  Caller's context
 *
 *    cyclic_move_in() should _only_ be called immediately after a CPU has
 *    moved into a new partition, with cpu_lock held.  As with other calls
 *    into the cyclic subsystem, no lock may be held which is also grabbed
 *    by any cyclic handler.
 */
void
cyclic_move_in(cpu_t *d)
{
	cyc_id_t *idp;
	cyc_cpu_t *dest = d->cpu_cyclic;
	cyclic_t *cyclic;
	cpupart_t *part = d->cpu_part;

	CYC_PTRACE("move-in", dest, part);
	ASSERT(MUTEX_HELD(&cpu_lock));

	/*
	 * Look for CYF_PART_BOUND cyclics in the new partition.  If
	 * we find one, check to see if it is currently on a CPU which has
	 * interrupts disabled.  If it is (and if this CPU currently has
	 * interrupts enabled), we'll juggle those cyclics over here.
	 */
	if (!(d->cpu_flags & CPU_ENABLE)) {
		CYC_PTRACE1("move-in-none", dest);
		return;
	}

	for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {
		cyc_cpu_t *cpu = idp->cyi_cpu;
		cpu_t *c;

		/*
		 * Omnipresent cyclics are exempt from juggling.
		 */
		if (cpu == NULL)
			continue;

		c = cpu->cyp_cpu;

		if (c->cpu_part != part || (c->cpu_flags & CPU_ENABLE))
			continue;

		cyclic = &cpu->cyp_cyclics[idp->cyi_ndx];

		if (cyclic->cy_flags & CYF_CPU_BOUND)
			continue;

		/*
		 * We know that this cyclic is bound to its processor set
		 * (otherwise, it would not be on a CPU with interrupts
		 * disabled); juggle it to our CPU.
		 */
		ASSERT(cyclic->cy_flags & CYF_PART_BOUND);
		cyclic_juggle_one_to(idp, dest);
	}

	CYC_PTRACE1("move-in-done", dest);
}

/*
 *  int cyclic_move_out(cpu_t *)
 *
 *  Overview
 *
 *    cyclic_move_out() is called by the CPU partition code immediately before
 *    the specified CPU is to move out of its partition.
 *
 *  Arguments and notes
 *
 *    The only argument to cyclic_move_out() is a CPU which is to move out of
 *    its partition.
 *
 *    cyclic_move_out() will attempt to juggle away all partition-bound
 *    cyclics.  If the specified CPU is the last CPU in a partition with
 *    partition-bound cyclics, cyclic_move_out() will fail.  If there exists
 *    a partition-bound cyclic which is CPU-bound to the specified CPU,
 *    cyclic_move_out() will fail.
 *
 *    Note that cyclic_move_out() will _only_ attempt to juggle away
 *    partition-bound cyclics; CPU-bound cyclics which are not partition-bound
 *    and unbound cyclics are not affected by changing the partition
 *    affiliation of the CPU.
 *
 *  Return value
 *
 *    cyclic_move_out() returns 1 if all partition-bound cyclics on the CPU
 *    were juggled away; 0 if some cyclics remain.
 *
 *  Caller's context
 *
 *    cyclic_move_out() should _only_ be called immediately before a CPU has
 *    moved out of its partition, with cpu_lock held.  It is expected that
 *    the caller of cyclic_move_out() will change the processor set affiliation
 *    of the specified CPU immediately after cyclic_move_out() returns
 *    success (i.e. before dropping cpu_lock).  Moreover, it is expected that
 *    the caller will fail the CPU repartitioning operation if cyclic_move_out()
 *    returns failure.  As with other calls into the cyclic subsystem, no lock
 *    may be held which is also grabbed by any cyclic handler.
 */
int
cyclic_move_out(cpu_t *c)
{
	cyc_id_t *idp;
	cyc_cpu_t *cpu = c->cpu_cyclic, *dest;
	cyclic_t *cyclic, *cyclics = cpu->cyp_cyclics;
	cpupart_t *part = c->cpu_part;

	CYC_PTRACE1("move-out", cpu);
	ASSERT(MUTEX_HELD(&cpu_lock));

	/*
	 * If there are any CYF_PART_BOUND cyclics on this CPU, we need
	 * to try to juggle them away.
	 */
	for (idp = cyclic_id_head; idp != NULL; idp = idp->cyi_next) {

		if (idp->cyi_cpu != cpu)
			continue;

		cyclic = &cyclics[idp->cyi_ndx];

		if (!(cyclic->cy_flags & CYF_PART_BOUND))
			continue;

		dest = cyclic_pick_cpu(part, c, c, cyclic->cy_flags);

		if (dest == NULL) {
			/*
			 * We can't juggle this cyclic; we need to return
			 * failure (we won't bother trying to juggle away
			 * other cyclics).
			 */
			CYC_PTRACE("move-out-fail", cpu, idp);
			return (0);
		}
		cyclic_juggle_one_to(idp, dest);
	}

	CYC_PTRACE1("move-out-done", cpu);
	return (1);
}

/*
 *  void cyclic_suspend()
 *
 *  Overview
 *
 *    cyclic_suspend() suspends all cyclic activity throughout the cyclic
 *    subsystem.  It should be called only by subsystems which are attempting
 *    to suspend the entire system (e.g. checkpoint/resume, dynamic
 *    reconfiguration).
 *
 *  Arguments and notes
 *
 *    cyclic_suspend() takes no arguments.  Each CPU with an active cyclic
 *    disables its backend (offline CPUs disable their backends as part of
 *    the cyclic_offline() operation), thereby disabling future CY_HIGH_LEVEL
 *    interrupts.
 *
 *    Note that disabling CY_HIGH_LEVEL interrupts does not completely preclude
 *    cyclic handlers from being called after cyclic_suspend() returns:  if a
 *    CY_LOCK_LEVEL or CY_LOW_LEVEL interrupt thread was blocked at the time
 *    of cyclic_suspend(), cyclic handlers at its level may continue to be
 *    called after the interrupt thread becomes unblocked.  The
 *    post-cyclic_suspend() activity is bounded by the pend count on all
 *    cyclics at the time of cyclic_suspend().  Callers concerned with more
 *    than simply disabling future CY_HIGH_LEVEL interrupts must check for
 *    this condition.
 *
 *    On most platforms, timestamps from gethrtime() and gethrestime() are not
 *    guaranteed to monotonically increase between cyclic_suspend() and
 *    cyclic_resume().  However, timestamps are guaranteed to monotonically
 *    increase across the entire cyclic_suspend()/cyclic_resume() operation.
 *    That is, every timestamp obtained before cyclic_suspend() will be less
 *    than every timestamp obtained after cyclic_resume().
 *
 *  Return value
 *
 *    None; cyclic_suspend() always succeeds.
 *
 *  Caller's context
 *
 *    The cyclic subsystem must be configured on every valid CPU;
 *    cyclic_suspend() may not be called during boot or during dynamic
 *    reconfiguration.  Additionally, cpu_lock must be held, and the caller
 *    cannot be in high-level interrupt context.  However, unlike most other
 *    cyclic entry points, cyclic_suspend() may be called with locks held
 *    which are also acquired by CY_LOCK_LEVEL or CY_LOW_LEVEL cyclic
 *    handlers.
 */
void
cyclic_suspend()
{
	cpu_t *c;
	cyc_cpu_t *cpu;
	cyc_xcallarg_t arg;
	cyc_backend_t *be;

	CYC_PTRACE0("suspend");
	ASSERT(MUTEX_HELD(&cpu_lock));
	c = cpu_list;

	do {
		cpu = c->cpu_cyclic;
		be = cpu->cyp_backend;
		arg.cyx_cpu = cpu;

		be->cyb_xcall(be->cyb_arg, c,
		    (cyc_func_t)cyclic_suspend_xcall, &arg);
	} while ((c = c->cpu_next) != cpu_list);
}

/*
 *  void cyclic_resume()
 *
 *    cyclic_resume() resumes all cyclic activity throughout the cyclic
 *    subsystem.  It should be called only by system-suspending subsystems.
 *
 *  Arguments and notes
 *
 *    cyclic_resume() takes no arguments.  Each CPU with an active cyclic
 *    reenables and reprograms its backend (offline CPUs are not reenabled).
 *    On most platforms, timestamps from gethrtime() and gethrestime() are not
 *    guaranteed to monotonically increase between cyclic_suspend() and
 *    cyclic_resume().  However, timestamps are guaranteed to monotonically
 *    increase across the entire cyclic_suspend()/cyclic_resume() operation.
 *    That is, every timestamp obtained before cyclic_suspend() will be less
 *    than every timestamp obtained after cyclic_resume().
 *
 *  Return value
 *
 *    None; cyclic_resume() always succeeds.
 *
 *  Caller's context
 *
 *    The cyclic subsystem must be configured on every valid CPU;
 *    cyclic_resume() may not be called during boot or during dynamic
 *    reconfiguration.  Additionally, cpu_lock must be held, and the caller
 *    cannot be in high-level interrupt context.  However, unlike most other
 *    cyclic entry points, cyclic_resume() may be called with locks held which
 *    are also acquired by CY_LOCK_LEVEL or CY_LOW_LEVEL cyclic handlers.
 */
void
cyclic_resume()
{
	cpu_t *c;
	cyc_cpu_t *cpu;
	cyc_xcallarg_t arg;
	cyc_backend_t *be;

	CYC_PTRACE0("resume");
	ASSERT(MUTEX_HELD(&cpu_lock));

	c = cpu_list;

	do {
		cpu = c->cpu_cyclic;
		be = cpu->cyp_backend;
		arg.cyx_cpu = cpu;

		be->cyb_xcall(be->cyb_arg, c,
		    (cyc_func_t)cyclic_resume_xcall, &arg);
	} while ((c = c->cpu_next) != cpu_list);
}