text: /*
      Copyright (c) 2008-2016 Apple Inc. All rights reserved.
  
      @APPLE_APACHE_LICENSE_HEADER_START@
  
      Licensed under the Apache License, Version 2.0 (the "License");
      you may not use this file except in compliance with the License.
      You may obtain a copy of the License at
  
         http://www.apache.org/licenses/LICENSE-2.0
  
      Unless required by applicable law or agreed to in writing, software
      distributed under the License is distributed on an "AS IS" BASIS,
      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      See the License for the specific language governing permissions and
      limitations under the License.
  
      @APPLE_APACHE_LICENSE_HEADER_END@
  */
  
  #include "internal.h"
  
  #pragma mark unote generic functions
  
  static void _dispatch_timer_unote_register(dispatch_timer_source_refs_t dt,
          dispatch_wlh_t wlh, dispatch_priority_t pri);
  static void _dispatch_timer_unote_resume(dispatch_timer_source_refs_t dt);
  static void _dispatch_timer_unote_unregister(dispatch_timer_source_refs_t dt);
  
  DISPATCH_NOINLINE
  static dispatch_unote_t
  _dispatch_unote_create(dispatch_source_type_t dst,
                         uintptr_t handle, uintptr_t mask) {
      dispatch_unote_linkage_t dul;
      dispatch_unote_class_t du;
  
      if (mask & ~dst->dst_mask) {
          return DISPATCH_UNOTE_NULL;
      }
  
      if (dst->dst_mask && !dst->dst_allow_empty_mask && !mask) {
          return DISPATCH_UNOTE_NULL;
      }
  
      if (dst->dst_flags & EV_UDATA_SPECIFIC) {
          du = _dispatch_calloc(1u, dst->dst_size);
      } else {
          dul = _dispatch_calloc(1u, sizeof(*dul) + dst->dst_size);
          du = _dispatch_unote_linkage_get_unote(dul)._du;
      }
      du->du_type = dst;
      du->du_can_be_wlh = dst->dst_per_trigger_qos;
      du->du_ident = (dispatch_unote_ident_t)handle;
      du->du_filter = dst->dst_filter;
      du->du_fflags = (__typeof__(du->du_fflags))mask;
      if (dst->dst_flags & EV_UDATA_SPECIFIC) {
          du->du_is_direct = true;
      }
      return (dispatch_unote_t) {
          ._du = du
      };
  }
  
  DISPATCH_NOINLINE
  dispatch_unote_t
  _dispatch_unote_create_with_handle(dispatch_source_type_t dst,
                                     uintptr_t handle, uintptr_t mask) {
      if (!handle) {
          return DISPATCH_UNOTE_NULL;
      }
      return _dispatch_unote_create(dst, handle, mask);
  }
  
  DISPATCH_NOINLINE
  dispatch_unote_t
  _dispatch_unote_create_with_fd(dispatch_source_type_t dst,
                                 uintptr_t handle, uintptr_t mask) {
  #if !TARGET_OS_MAC // <rdar://problem/27756657>
      if (handle > INT_MAX) {
          return DISPATCH_UNOTE_NULL;
      }
  #endif
      return _dispatch_unote_create(dst, handle, mask);
  }
  
  DISPATCH_NOINLINE
  dispatch_unote_t
  _dispatch_unote_create_without_handle(dispatch_source_type_t dst,
                                        uintptr_t handle, uintptr_t mask) {
      if (handle) {
          return DISPATCH_UNOTE_NULL;
      }
      return _dispatch_unote_create(dst, handle, mask);
  }
  
  DISPATCH_NOINLINE
  void
  _dispatch_unote_dispose(dispatch_unote_t du) {
      void *ptr = du._du;
  #if HAVE_MACH
      if (du._du->dmrr_handler_is_block) {
          Block_release(du._dmrr->dmrr_handler_ctxt);
      }
  #endif
      if (du._du->du_is_timer) {
          if (unlikely(du._dt->dt_heap_entry[DTH_TARGET_ID] != DTH_INVALID_ID ||
                       du._dt->dt_heap_entry[DTH_DEADLINE_ID] != DTH_INVALID_ID)) {
              DISPATCH_INTERNAL_CRASH(0, "Disposing of timer still in its heap");
          }
          if (unlikely(du._dt->dt_pending_config)) {
              free(du._dt->dt_pending_config);
              du._dt->dt_pending_config = NULL;
          }
      } else if (!du._du->du_is_direct) {
          ptr = _dispatch_unote_get_linkage(du);
      }
      free(ptr);
  }
  
  bool
  _dispatch_unote_register(dispatch_unote_t du, dispatch_wlh_t wlh,
                           dispatch_priority_t pri) {
      dispatch_assert(du._du->du_is_timer || !_dispatch_unote_registered(du));
      dispatch_priority_t masked_pri;
  
      masked_pri = pri & (DISPATCH_PRIORITY_FLAG_MANAGER |
                          DISPATCH_PRIORITY_FLAG_FALLBACK |
                          DISPATCH_PRIORITY_FLAG_FLOOR |
                          DISPATCH_PRIORITY_FALLBACK_QOS_MASK |
                          DISPATCH_PRIORITY_REQUESTED_MASK);
  
      dispatch_assert(wlh == DISPATCH_WLH_ANON || masked_pri);
      if (masked_pri == _dispatch_priority_make_fallback(DISPATCH_QOS_DEFAULT)) {
          _dispatch_ktrace1(DISPATCH_PERF_source_registration_without_qos,
                            _dispatch_wref2ptr(du._du->du_owner_wref));
      }
  
      du._du->du_priority = pri;
  
      switch (du._du->du_filter) {
      case DISPATCH_EVFILT_CUSTOM_ADD:
      case DISPATCH_EVFILT_CUSTOM_OR:
      case DISPATCH_EVFILT_CUSTOM_REPLACE:
          _dispatch_unote_state_set(du, DISPATCH_WLH_ANON, DU_STATE_ARMED);
          return true;
      }
      if (du._du->du_is_timer) {
          _dispatch_timer_unote_register(du._dt, wlh, pri);
          return true;
      }
  #if DISPATCH_HAVE_DIRECT_KNOTES
      if (du._du->du_is_direct) {
          return _dispatch_unote_register_direct(du, wlh);
      }
  #endif
      return _dispatch_unote_register_muxed(du);
  }
  
  void
  _dispatch_unote_resume(dispatch_unote_t du) {
      dispatch_assert(du._du->du_is_timer || _dispatch_unote_needs_rearm(du));
      if (du._du->du_is_timer) {
          _dispatch_timer_unote_resume(du._dt);
  #if DISPATCH_HAVE_DIRECT_KNOTES
      } else if (du._du->du_is_direct) {
          _dispatch_unote_resume_direct(du);
  #endif
      } else {
          _dispatch_unote_resume_muxed(du);
      }
  }
  
  bool
  _dispatch_unote_unregister(dispatch_unote_t du, uint32_t flags) {
      if (!_dispatch_unote_registered(du)) {
          return true;
      }
      switch (du._du->du_filter) {
      case DISPATCH_EVFILT_CUSTOM_ADD:
      case DISPATCH_EVFILT_CUSTOM_OR:
      case DISPATCH_EVFILT_CUSTOM_REPLACE:
          _dispatch_unote_state_set(du, DU_STATE_UNREGISTERED);
          return true;
      }
      if (du._du->du_is_timer) {
          _dispatch_timer_unote_unregister(du._dt);
          return true;
      }
  #if DISPATCH_HAVE_DIRECT_KNOTES
      if (du._du->du_is_direct) {
          return _dispatch_unote_unregister_direct(du, flags);
      }
  #endif
  
      dispatch_assert(flags & DUU_DELETE_ACK);
      return _dispatch_unote_unregister_muxed(du);
  }
  
  #pragma mark data or / add
  
  static dispatch_unote_t
  _dispatch_source_data_create(dispatch_source_type_t dst, uintptr_t handle,
                               uintptr_t mask) {
      if (handle || mask) {
          return DISPATCH_UNOTE_NULL;
      }
  
      // bypass _dispatch_unote_create() because this is always "direct"
      // even when EV_UDATA_SPECIFIC is 0
      dispatch_unote_class_t du = _dispatch_calloc(1u, dst->dst_size);
      du->du_type = dst;
      du->du_filter = dst->dst_filter;
      du->du_is_direct = true;
      return (dispatch_unote_t) {
          ._du = du
      };
  }
  
  const dispatch_source_type_s _dispatch_source_type_data_add = {
      .dst_kind       = "data-add",
      .dst_filter     = DISPATCH_EVFILT_CUSTOM_ADD,
      .dst_flags      = EV_UDATA_SPECIFIC|EV_CLEAR,
      .dst_action     = DISPATCH_UNOTE_ACTION_PASS_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_source_data_create,
      .dst_merge_evt  = NULL,
  };
  
  const dispatch_source_type_s _dispatch_source_type_data_or = {
      .dst_kind       = "data-or",
      .dst_filter     = DISPATCH_EVFILT_CUSTOM_OR,
      .dst_flags      = EV_UDATA_SPECIFIC|EV_CLEAR,
      .dst_action     = DISPATCH_UNOTE_ACTION_PASS_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_source_data_create,
      .dst_merge_evt  = NULL,
  };
  
  const dispatch_source_type_s _dispatch_source_type_data_replace = {
      .dst_kind       = "data-replace",
      .dst_filter     = DISPATCH_EVFILT_CUSTOM_REPLACE,
      .dst_flags      = EV_UDATA_SPECIFIC|EV_CLEAR,
      .dst_action     = DISPATCH_UNOTE_ACTION_PASS_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_source_data_create,
      .dst_merge_evt  = NULL,
  };
  
  #pragma mark file descriptors
  
  const dispatch_source_type_s _dispatch_source_type_read = {
      .dst_kind       = "read",
      .dst_filter     = EVFILT_READ,
      .dst_flags      = EV_UDATA_SPECIFIC|EV_DISPATCH|EV_VANISHED,
  #if DISPATCH_EVENT_BACKEND_KEVENT
  #if HAVE_DECL_NOTE_LOWAT
      .dst_fflags     = NOTE_LOWAT,
  #endif
      .dst_data       = 1,
  #endif // DISPATCH_EVENT_BACKEND_KEVENT
      .dst_action     = DISPATCH_UNOTE_ACTION_SOURCE_SET_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_unote_create_with_fd,
      .dst_merge_evt  = _dispatch_source_merge_evt,
  };
  
  const dispatch_source_type_s _dispatch_source_type_write = {
      .dst_kind       = "write",
      .dst_filter     = EVFILT_WRITE,
      .dst_flags      = EV_UDATA_SPECIFIC|EV_DISPATCH|EV_VANISHED,
  #if DISPATCH_EVENT_BACKEND_KEVENT
  #if HAVE_DECL_NOTE_LOWAT
      .dst_fflags     = NOTE_LOWAT,
  #endif
      .dst_data       = 1,
  #endif // DISPATCH_EVENT_BACKEND_KEVENT
      .dst_action     = DISPATCH_UNOTE_ACTION_SOURCE_SET_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_unote_create_with_fd,
      .dst_merge_evt  = _dispatch_source_merge_evt,
  };
  
  #pragma mark signals
  
  static dispatch_unote_t
  _dispatch_source_signal_create(dispatch_source_type_t dst, uintptr_t handle,
                                 uintptr_t mask) {
      if (handle >= NSIG) {
          return DISPATCH_UNOTE_NULL;
      }
      return _dispatch_unote_create_with_handle(dst, handle, mask);
  }
  
  const dispatch_source_type_s _dispatch_source_type_signal = {
      .dst_kind       = "signal",
      .dst_filter     = EVFILT_SIGNAL,
      .dst_flags      = DISPATCH_EV_DIRECT|EV_CLEAR,
      .dst_action     = DISPATCH_UNOTE_ACTION_SOURCE_ADD_DATA,
      .dst_size       = sizeof(struct dispatch_source_refs_s),
  
      .dst_create     = _dispatch_source_signal_create,
      .dst_merge_evt  = _dispatch_source_merge_evt,
  };
  
  #pragma mark -
  #pragma mark timer globals
  
  DISPATCH_GLOBAL(struct dispatch_timer_heap_s
                  _dispatch_timers_heap[DISPATCH_TIMER_COUNT]);
  
  #if DISPATCH_USE_DTRACE
  DISPATCH_STATIC_GLOBAL(dispatch_timer_source_refs_t
                         _dispatch_trace_next_timer[DISPATCH_TIMER_QOS_COUNT]);
  #define _dispatch_trace_next_timer_set(x, q) \
  		_dispatch_trace_next_timer[(q)] = (x)
  #define _dispatch_trace_next_timer_program(d, q) \
  		_dispatch_trace_timer_program(_dispatch_trace_next_timer[(q)], (d))
  #else
  #define _dispatch_trace_next_timer_set(x, q)
  #define _dispatch_trace_next_timer_program(d, q)
  #endif
  
  #pragma mark timer heap
  /*
      The dispatch_timer_heap_t structure is a double min-heap of timers,
      interleaving the by-target min-heap in the even slots, and the by-deadline
      in the odd ones.
  
      The min element of these is held inline in the dispatch_timer_heap_t
      structure, and further entries are held in segments.
  
      dth_segments is the number of allocated segments.
  
      Segment 0 has a size of `DISPATCH_HEAP_INIT_SEGMENT_CAPACITY` pointers
      Segment k has a size of (DISPATCH_HEAP_INIT_SEGMENT_CAPACITY << (k - 1))
  
      Segment n (dth_segments - 1) is the last segment and points its final n
      entries to previous segments. Its address is held in the `dth_heap` field.
  
      segment n   [ regular timer pointers | n-1 | k | 0 ]
                                             |    |   |
      segment n-1 <---------------------------'    |   |
      segment k   <--------------------------------'   |
      segment 0   <------------------------------------'
  */
  #define DISPATCH_HEAP_INIT_SEGMENT_CAPACITY 8u
  
  /*
      There are two min-heaps stored interleaved in a single array,
      even indices are for the by-target min-heap, and odd indices for
      the by-deadline one.
  */
  #define DTH_HEAP_ID_MASK (DTH_ID_COUNT - 1)
  #define DTH_HEAP_ID(idx) ((idx) & DTH_HEAP_ID_MASK)
  #define DTH_IDX_FOR_HEAP_ID(idx, heap_id) \
  		(((idx) & ~DTH_HEAP_ID_MASK) | (heap_id))
  
  DISPATCH_ALWAYS_INLINE
  static inline uint32_t
  _dispatch_timer_heap_capacity(uint32_t segments) {
      if (segments == 0) {
          return 2;
      }
      uint32_t seg_no = segments - 1;
      // for C = DISPATCH_HEAP_INIT_SEGMENT_CAPACITY,
      // 2 + C + SUM(C << (i-1), i = 1..seg_no) - seg_no
      return 2 + (DISPATCH_HEAP_INIT_SEGMENT_CAPACITY << seg_no) - seg_no;
  }
  
  static void
  _dispatch_timer_heap_grow(dispatch_timer_heap_t dth) {
      uint32_t seg_capacity = DISPATCH_HEAP_INIT_SEGMENT_CAPACITY;
      uint32_t seg_no = dth->dth_segments++;
      void **heap, **heap_prev = dth->dth_heap;
  
      if (seg_no > 0) {
          seg_capacity <<= (seg_no - 1);
      }
      heap = _dispatch_calloc(seg_capacity, sizeof(void *));
      if (seg_no > 1) {
          uint32_t prev_seg_no = seg_no - 1;
          uint32_t prev_seg_capacity = seg_capacity >> 1;
          memcpy(&heap[seg_capacity - prev_seg_no],
                 &heap_prev[prev_seg_capacity - prev_seg_no],
                 prev_seg_no * sizeof(void *));
      }
      if (seg_no > 0) {
          heap[seg_capacity - seg_no] = heap_prev;
      }
      dth->dth_heap = heap;
  }
  
  static void
  _dispatch_timer_heap_shrink(dispatch_timer_heap_t dth) {
      uint32_t seg_capacity = DISPATCH_HEAP_INIT_SEGMENT_CAPACITY;
      uint32_t seg_no = --dth->dth_segments;
      void **heap = dth->dth_heap, **heap_prev = NULL;
  
      if (seg_no > 0) {
          seg_capacity <<= (seg_no - 1);
          heap_prev = heap[seg_capacity - seg_no];
      }
      if (seg_no > 1) {
          uint32_t prev_seg_no = seg_no - 1;
          uint32_t prev_seg_capacity = seg_capacity >> 1;
          memcpy(&heap_prev[prev_seg_capacity - prev_seg_no],
                 &heap[seg_capacity - prev_seg_no],
                 prev_seg_no * sizeof(void *));
      }
      dth->dth_heap = heap_prev;
      free(heap);
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline dispatch_timer_source_refs_t *
  _dispatch_timer_heap_get_slot(dispatch_timer_heap_t dth, uint32_t idx) {
      uint32_t seg_no, segments = dth->dth_segments;
      void **segment;
  
      if (idx < DTH_ID_COUNT) {
          return &dth->dth_min[idx];
      }
      idx -= DTH_ID_COUNT;
  
      // Derive the segment number from the index. Naming
      // DISPATCH_HEAP_INIT_SEGMENT_CAPACITY `C`, the segments index ranges are:
      // 0: 0 .. (C - 1)
      // 1: C .. 2 * C - 1
      // k: 2^(k-1) * C .. 2^k * C - 1
      // so `k` can be derived from the first bit set in `idx`
      seg_no = (uint32_t)(__builtin_clz(DISPATCH_HEAP_INIT_SEGMENT_CAPACITY - 1) -
                          __builtin_clz(idx | (DISPATCH_HEAP_INIT_SEGMENT_CAPACITY - 1)));
      if (seg_no + 1 == segments) {
          segment = dth->dth_heap;
      } else {
          uint32_t seg_capacity = DISPATCH_HEAP_INIT_SEGMENT_CAPACITY;
          seg_capacity <<= (segments - 2);
          segment = dth->dth_heap[seg_capacity - seg_no - 1];
      }
      if (seg_no) {
          idx -= DISPATCH_HEAP_INIT_SEGMENT_CAPACITY << (seg_no - 1);
      }
      return (dispatch_timer_source_refs_t *)(segment + idx);
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline void
  _dispatch_timer_heap_set(dispatch_timer_heap_t dth,
                           dispatch_timer_source_refs_t *slot,
                           dispatch_timer_source_refs_t dt, uint32_t idx) {
      if (idx < DTH_ID_COUNT) {
          dth->dth_needs_program = true;
      }
      *slot = dt;
      dt->dt_heap_entry[DTH_HEAP_ID(idx)] = idx;
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline uint32_t
  _dispatch_timer_heap_parent(uint32_t idx) {
      uint32_t heap_id = DTH_HEAP_ID(idx);
      idx = (idx - DTH_ID_COUNT) / 2; // go to the parent
      return DTH_IDX_FOR_HEAP_ID(idx, heap_id);
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline uint32_t
  _dispatch_timer_heap_left_child(uint32_t idx) {
      uint32_t heap_id = DTH_HEAP_ID(idx);
      // 2 * (idx - heap_id) + DTH_ID_COUNT + heap_id
      return 2 * idx + DTH_ID_COUNT - heap_id;
  }
  
  #if DISPATCH_HAVE_TIMER_COALESCING
  DISPATCH_ALWAYS_INLINE
  static inline uint32_t
  _dispatch_timer_heap_walk_skip(uint32_t idx, uint32_t count) {
      uint32_t heap_id = DTH_HEAP_ID(idx);
  
      idx -= heap_id;
      if (unlikely(idx + DTH_ID_COUNT == count)) {
          // reaching `count` doesn't mean we're done, but there is a weird
          // corner case if the last item of the heap is a left child:
          //
          //     /\
          //    /  \
          //   /  __\
          //  /__/
          //     ^
          //
          // The formula below would return the sibling of `idx` which is
          // out of bounds. Fortunately, the correct answer is the same
          // as for idx's parent
          idx = _dispatch_timer_heap_parent(idx);
      }
  
      //
      // When considering the index in a non interleaved, 1-based array
      // representation of a heap, hence looking at (idx / DTH_ID_COUNT + 1)
      // for a given idx in our dual-heaps, that index is in one of two forms:
      //
      //     (a) 1xxxx011111    or    (b) 111111111
      //         d    i    0              d       0
      //
      // The first bit set is the row of the binary tree node (0-based).
      // The following digits from most to least significant represent the path
      // to that node, where `0` is a left turn and `1` a right turn.
      //
      // For example 0b0101 (5) is a node on row 2 accessed going left then right:
      //
      // row 0          1
      //              /   .
      // row 1      2       3
      //           . \     . .
      // row 2    4   5   6   7
      //         : : : : : : : :
      //
      // Skipping a sub-tree in walk order means going to the sibling of the last
      // node reached after we turned left. If the node was of the form (a),
      // this node is 1xxxx1, which for the above example is 0b0011 (3).
      // If the node was of the form (b) then we never took a left, meaning
      // we reached the last element in traversal order.
      //
  
      //
      // we want to find
      // - the least significant bit set to 0 in (idx / DTH_ID_COUNT + 1)
      // - which is offset by log_2(DTH_ID_COUNT) from the position of the least
      //   significant 0 in (idx + DTH_ID_COUNT + DTH_ID_COUNT - 1)
      //   since idx is a multiple of DTH_ID_COUNT and DTH_ID_COUNT a power of 2.
      // - which in turn is the same as the position of the least significant 1 in
      //   ~(idx + DTH_ID_COUNT + DTH_ID_COUNT - 1)
      //
      dispatch_static_assert(powerof2(DTH_ID_COUNT));
      idx += DTH_ID_COUNT + DTH_ID_COUNT - 1;
      idx >>= __builtin_ctz(~idx);
  
      //
      // `idx` is now either:
      // - 0 if it was the (b) case above, in which case the walk is done
      // - 1xxxx0 as the position in a 0 based array representation of a non
      //   interleaved heap, so we just have to compute the interleaved index.
      //
      return likely(idx) ? DTH_ID_COUNT * idx + heap_id : UINT32_MAX;
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline uint32_t
  _dispatch_timer_heap_walk_next(uint32_t idx, uint32_t count) {
      //
      // Goes to the next element in heap walk order, which is the prefix ordered
      // walk of the tree.
      //
      // From a given node, the next item to return is the left child if it
      // exists, else the first right sibling we find by walking our parent chain,
      // which is exactly what _dispatch_timer_heap_walk_skip() returns.
      //
      uint32_t lchild = _dispatch_timer_heap_left_child(idx);
      if (lchild < count) {
          return lchild;
      }
      return _dispatch_timer_heap_walk_skip(idx, count);
  }
  
  static uint64_t
  _dispatch_timer_heap_max_target_before(dispatch_timer_heap_t dth, uint64_t limit) {
      dispatch_timer_source_refs_t dri;
      uint32_t idx = _dispatch_timer_heap_left_child(DTH_TARGET_ID);
      uint32_t count = dth->dth_count;
      uint64_t tmp, target = dth->dth_min[DTH_TARGET_ID]->dt_timer.target;
  
      while (idx < count) {
          dri = *_dispatch_timer_heap_get_slot(dth, idx);
          tmp = dri->dt_timer.target;
          if (tmp > limit) {
              // skip subtree since none of the targets below can be before limit
              idx = _dispatch_timer_heap_walk_skip(idx, count);
          } else {
              target = tmp;
              idx = _dispatch_timer_heap_walk_next(idx, count);
          }
      }
      return target;
  }
  #endif // DISPATCH_HAVE_TIMER_COALESCING
  
  static void
  _dispatch_timer_heap_resift(dispatch_timer_heap_t dth,
                              dispatch_timer_source_refs_t dt, uint32_t idx) {
      dispatch_static_assert(offsetof(struct dispatch_timer_source_s, target) ==
                             offsetof(struct dispatch_timer_source_s, heap_key[DTH_TARGET_ID]));
      dispatch_static_assert(offsetof(struct dispatch_timer_source_s, deadline) ==
                             offsetof(struct dispatch_timer_source_s, heap_key[DTH_DEADLINE_ID]));
  #define dth_cmp(hid, dt1, op, dt2) \
  		(((dt1)->dt_timer.heap_key)[hid] op ((dt2)->dt_timer.heap_key)[hid])
  
      dispatch_timer_source_refs_t *pslot, pdt;
      dispatch_timer_source_refs_t *cslot, cdt;
      dispatch_timer_source_refs_t *rslot, rdt;
      uint32_t cidx, dth_count = dth->dth_count;
      dispatch_timer_source_refs_t *slot;
      int heap_id = DTH_HEAP_ID(idx);
      bool sifted_up = false;
  
      // try to sift up
  
      slot = _dispatch_timer_heap_get_slot(dth, idx);
      while (idx >= DTH_ID_COUNT) {
          uint32_t pidx = _dispatch_timer_heap_parent(idx);
          pslot = _dispatch_timer_heap_get_slot(dth, pidx);
          pdt = *pslot;
          if (dth_cmp(heap_id, pdt, <=, dt)) {
              break;
          }
          _dispatch_timer_heap_set(dth, slot, pdt, idx);
          slot = pslot;
          idx = pidx;
          sifted_up = true;
      }
      if (sifted_up) {
          goto done;
      }
  
      // try to sift down
  
      while ((cidx = _dispatch_timer_heap_left_child(idx)) < dth_count) {
          uint32_t ridx = cidx + DTH_ID_COUNT;
          cslot = _dispatch_timer_heap_get_slot(dth, cidx);
          cdt = *cslot;
          if (ridx < dth_count) {
              rslot = _dispatch_timer_heap_get_slot(dth, ridx);
              rdt = *rslot;
              if (dth_cmp(heap_id, cdt, >, rdt)) {
                  cidx = ridx;
                  cdt = rdt;
                  cslot = rslot;
              }
          }
          if (dth_cmp(heap_id, dt, <=, cdt)) {
              break;
          }
          _dispatch_timer_heap_set(dth, slot, cdt, idx);
          slot = cslot;
          idx = cidx;
      }
  
  done:
      _dispatch_timer_heap_set(dth, slot, dt, idx);
  #undef dth_cmp
  }
  
  DISPATCH_ALWAYS_INLINE
  static void
  _dispatch_timer_heap_insert(dispatch_timer_heap_t dth,
                              dispatch_timer_source_refs_t dt) {
      uint32_t idx = (dth->dth_count += DTH_ID_COUNT) - DTH_ID_COUNT;
  
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_TARGET_ID], ==,
                            DTH_INVALID_ID, "target idx");
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_DEADLINE_ID], ==,
                            DTH_INVALID_ID, "deadline idx");
  
      dispatch_qos_t qos = MAX(_dispatch_priority_qos(dt->du_priority),
                               _dispatch_priority_fallback_qos(dt->du_priority));
      if (dth->dth_max_qos < qos) {
          dth->dth_max_qos = (uint8_t)qos;
          dth->dth_needs_program = true;
      }
  
      if (idx == 0) {
          dth->dth_needs_program = true;
          dt->dt_heap_entry[DTH_TARGET_ID] = DTH_TARGET_ID;
          dt->dt_heap_entry[DTH_DEADLINE_ID] = DTH_DEADLINE_ID;
          dth->dth_min[DTH_TARGET_ID] = dth->dth_min[DTH_DEADLINE_ID] = dt;
          return;
      }
  
      if (unlikely(idx + DTH_ID_COUNT >
                   _dispatch_timer_heap_capacity(dth->dth_segments))) {
          _dispatch_timer_heap_grow(dth);
      }
      _dispatch_timer_heap_resift(dth, dt, idx + DTH_TARGET_ID);
      _dispatch_timer_heap_resift(dth, dt, idx + DTH_DEADLINE_ID);
  }
  
  static void
  _dispatch_timer_heap_remove(dispatch_timer_heap_t dth,
                              dispatch_timer_source_refs_t dt) {
      uint32_t idx = (dth->dth_count -= DTH_ID_COUNT);
  
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_TARGET_ID], !=,
                            DTH_INVALID_ID, "target idx");
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_DEADLINE_ID], !=,
                            DTH_INVALID_ID, "deadline idx");
  
      if (idx == 0) {
          DISPATCH_TIMER_ASSERT(dth->dth_min[DTH_TARGET_ID], ==, dt,
                                "target slot");
          DISPATCH_TIMER_ASSERT(dth->dth_min[DTH_DEADLINE_ID], ==, dt,
                                "deadline slot");
          dth->dth_needs_program = true;
          dth->dth_min[DTH_TARGET_ID] = dth->dth_min[DTH_DEADLINE_ID] = NULL;
          goto clear_heap_entry;
      }
  
      for (uint32_t heap_id = 0; heap_id < DTH_ID_COUNT; heap_id++) {
          dispatch_timer_source_refs_t *slot, last_dt;
          slot = _dispatch_timer_heap_get_slot(dth, idx + heap_id);
          last_dt = *slot;
          *slot = NULL;
          if (last_dt != dt) {
              uint32_t removed_idx = dt->dt_heap_entry[heap_id];
              _dispatch_timer_heap_resift(dth, last_dt, removed_idx);
          }
      }
      if (unlikely(idx <= _dispatch_timer_heap_capacity(dth->dth_segments - 1))) {
          _dispatch_timer_heap_shrink(dth);
      }
  
  clear_heap_entry:
      dt->dt_heap_entry[DTH_TARGET_ID] = DTH_INVALID_ID;
      dt->dt_heap_entry[DTH_DEADLINE_ID] = DTH_INVALID_ID;
  }
  
  DISPATCH_ALWAYS_INLINE
  static inline void
  _dispatch_timer_heap_update(dispatch_timer_heap_t dth,
                              dispatch_timer_source_refs_t dt) {
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_TARGET_ID], !=,
                            DTH_INVALID_ID, "target idx");
      DISPATCH_TIMER_ASSERT(dt->dt_heap_entry[DTH_DEADLINE_ID], !=,
                            DTH_INVALID_ID, "deadline idx");
  
      _dispatch_timer_heap_resift(dth, dt, dt->dt_heap_entry[DTH_TARGET_ID]);
      _dispatch_timer_heap_resift(dth, dt, dt->dt_heap_entry[DTH_DEADLINE_ID]);
  }
  
  #pragma mark timer unote
  
  #define _dispatch_timer_du_debug(what, du) \
  		_dispatch_debug("kevent-source[%p]: %s kevent[%p] { ident = 0x%x }", \
  				_dispatch_wref2ptr((du)->du_owner_wref), what, \
  				(du), (du)->du_ident)
  
  DISPATCH_ALWAYS_INLINE
  static inline unsigned int
  _dispatch_timer_unote_idx(dispatch_timer_source_refs_t dt) {
      dispatch_clock_t clock = _dispatch_timer_flags_to_clock(dt->du_timer_flags);
      uint32_t qos = 0;
  
  #if DISPATCH_HAVE_TIMER_QOS
      dispatch_assert(DISPATCH_TIMER_STRICT == DISPATCH_TIMER_QOS_CRITICAL);
      dispatch_assert(DISPATCH_TIMER_BACKGROUND == DISPATCH_TIMER_QOS_BACKGROUND);
      qos = dt->du_timer_flags & (DISPATCH_TIMER_STRICT|DISPATCH_TIMER_BACKGROUND);
      // flags are normalized so this should never happen
      dispatch_assert(qos < DISPATCH_TIMER_QOS_COUNT);
  #endif
  
      return DISPATCH_TIMER_INDEX(clock, qos);
  }
  
  static void
  _dispatch_timer_unote_disarm(dispatch_timer_source_refs_t dt,
                               dispatch_timer_heap_t dth) {
      uint32_t tidx = dt->du_ident;
  
      dispatch_assert(_dispatch_unote_armed(dt));
      _dispatch_timer_heap_remove(&dth[tidx], dt);
      _dispatch_timers_heap_dirty(dth, tidx);
      _dispatch_unote_state_clear_bit(dt, DU_STATE_ARMED);
      _dispatch_timer_du_debug("disarmed", dt);
  }
  
  static void
  _dispatch_timer_unote_arm(dispatch_timer_source_refs_t dt,
                            dispatch_timer_heap_t dth, uint32_t tidx) {
      if (_dispatch_unote_armed(dt)) {
          DISPATCH_TIMER_ASSERT(dt->du_ident, ==, tidx, "tidx");
          _dispatch_timer_heap_update(&dth[tidx], dt);
          _dispatch_timer_du_debug("updated", dt);
      } else {
          dt->du_ident = tidx;
          _dispatch_timer_heap_insert(&dth[tidx], dt);
          _dispatch_unote_state_set_bit(dt, DU_STATE_ARMED);
          _dispatch_timer_du_debug("armed", dt);
      }
      _dispatch_timers_heap_dirty(dth, tidx);
  }
  
  #define DISPATCH_TIMER_UNOTE_TRACE_SUSPENSION 0x1
  
  DISPATCH_ALWAYS_INLINE
  static inline bool
  _dispatch_timer_unote_needs_rearm(dispatch_timer_source_refs_t dr, int flags) {
      dispatch_source_t ds = _dispatch_source_from_refs(dr);
      if (unlikely(DISPATCH_QUEUE_IS_SUSPENDED(ds))) {
          if (flags & DISPATCH_TIMER_UNOTE_TRACE_SUSPENSION) {
              _dispatch_ktrace1(DISPATCH_PERF_suspended_timer_fire, ds);
          }
          return false;
      }
      return dr->du_ident != DISPATCH_TIMER_IDENT_CANCELED &&
             dr->dt_timer.target < INT64_MAX;
  }
  
  DISPATCH_NOINLINE
  static void
  _dispatch_timer_unote_register(dispatch_timer_source_refs_t dt,
                                 dispatch_wlh_t wlh, dispatch_priority_t pri) {
      // aggressively coalesce background/maintenance QoS timers
      // <rdar://problem/12200216&27342536>
      if (_dispatch_qos_is_background(_dispatch_priority_qos(pri))) {
          if (dt->du_timer_flags & DISPATCH_TIMER_STRICT) {
              _dispatch_ktrace1(DISPATCH_PERF_strict_bg_timer,
                                _dispatch_source_from_refs(dt));
          } else {
              dt->du_timer_flags |= DISPATCH_TIMER_BACKGROUND;
              dt->du_ident = _dispatch_timer_unote_idx(dt);
          }
      }
      // _dispatch_source_activate() can pre-set a wlh for timers directly
      // attached to their workloops.
      if (_dispatch_unote_wlh(dt) != wlh) {
          dispatch_assert(_dispatch_unote_wlh(dt) == NULL);
          _dispatch_unote_state_set(dt, DISPATCH_WLH_ANON, 0);
      }
      if (os_atomic_load2o(dt, dt_pending_config, relaxed)) {
          _dispatch_timer_unote_configure(dt);
      }
  }
  
  void
  _dispatch_timer_unote_configure(dispatch_timer_source_refs_t dt) {
      dispatch_timer_config_t dtc;
  
      dtc = os_atomic_xchg2o(dt, dt_pending_config, NULL, dependency);
      if (dtc->dtc_clock != _dispatch_timer_flags_to_clock(dt->du_timer_flags)) {
          dt->du_timer_flags &= ~_DISPATCH_TIMER_CLOCK_MASK;
          dt->du_timer_flags |= _dispatch_timer_flags_from_clock(dtc->dtc_clock);
      }
      dt->dt_timer = dtc->dtc_timer;
      free(dtc);
      // Clear any pending data that might have accumulated on
      // older timer params <rdar://problem/8574886>
      os_atomic_store2o(dt, ds_pending_data, 0, relaxed);
  
      if (_dispatch_unote_armed(dt)) {
          return _dispatch_timer_unote_resume(dt);
      }
  }
  
  static inline dispatch_timer_heap_t
  _dispatch_timer_unote_heap(dispatch_timer_source_refs_t dt) {
      dispatch_wlh_t wlh = _dispatch_unote_wlh(dt);
      if (wlh == DISPATCH_WLH_ANON) {
          return _dispatch_timers_heap;
      }
      return ((dispatch_workloop_t)wlh)->dwl_timer_heap;
  }
  
  DISPATCH_NOINLINE
  static void
  _dispatch_timer_unote_resume(dispatch_timer_source_refs_t dt) {
      // ... and now reflect any impact the reconfiguration has to the heap.
      // The heap also owns a +2 on dispatch sources it references, so maintain
      // this invariant as we tweak the registration.
  
      bool will_arm = _dispatch_timer_unote_needs_rearm(dt, 0);
      bool was_armed = _dispatch_unote_armed(dt);
      uint32_t tidx = _dispatch_timer_unote_idx(dt);
      dispatch_timer_heap_t dth = _dispatch_timer_unote_heap(dt);
  
      if (unlikely(was_armed && (!will_arm || dt->du_ident != tidx))) {
          _dispatch_timer_unote_disarm(dt, dth);
      }
      if (will_arm) {
          if (!was_armed) {
              _dispatch_retain_unote_owner(dt);
          }
          _dispatch_timer_unote_arm(dt, dth, tidx);
      } else if (was_armed) {
          _dispatch_release_unote_owner_tailcall(dt);
      }
  }
  
  DISPATCH_NOINLINE
  static void
  _dispatch_timer_unote_unregister(dispatch_timer_source_refs_t dt) {
      dispatch_timer_heap_t dth = _dispatch_timer_unote_heap(dt);
      if (_dispatch_unote_armed(dt)) {
          _dispatch_timer_unote_disarm(dt, dth);
          _dispatch_release_2_no_dispose(_dispatch_source_from_refs(dt));
      }
      _dispatch_wlh_release(_dispatch_unote_wlh(dt));
      _dispatch_unote_state_set(dt, DU_STATE_UNREGISTERED);
      dt->du_ident = DISPATCH_TIMER_IDENT_CANCELED;
  }
  
  static dispatch_unote_t
  _dispatch_source_timer_create(dispatch_source_type_t dst,
                                uintptr_t handle, uintptr_t mask) {
      dispatch_timer_source_refs_t dt;
  
      // normalize flags
      if (mask & DISPATCH_TIMER_STRICT) {
          mask &= ~(uintptr_t)DISPATCH_TIMER_BACKGROUND;
      }
      if (mask & ~dst->dst_mask) {
          return DISPATCH_UNOTE_NULL;
      }
  
      if (dst->dst_timer_flags & DISPATCH_TIMER_INTERVAL) {
          if (!handle) {
              return DISPATCH_UNOTE_NULL;
          }
      } else if (dst->dst_filter == DISPATCH_EVFILT_TIMER_WITH_CLOCK) {
          if (handle) {
              return DISPATCH_UNOTE_NULL;
          }
      } else
          switch (handle) {
          case 0:
              break;
          case DISPATCH_CLOCKID_UPTIME:
              dst = &_dispatch_source_type_timer_with_clock;
              mask |= DISPATCH_TIMER_CLOCK_UPTIME;
              break;
          case DISPATCH_CLOCKID_MONOTONIC:
              dst = &_dispatch_source_type_timer_with_clock;
              mask |= DISPATCH_TIMER_CLOCK_MONOTONIC;
              break;
          case DISPATCH_CLOCKID_WALLTIME:
              dst = &_dispatch_source_type_timer_with_clock;
              mask |= DISPATCH_TIMER_CLOCK_WALL;
              break;
          default:
              return DISPATCH_UNOTE_NULL;
          }
  
      dt = _dispatch_calloc(1u, dst->dst_size);
      dt->du_type = dst;
      dt->du_filter = dst->dst_filter;
      dt->du_is_timer = true;
      dt->du_timer_flags |= (uint8_t)(mask | dst->dst_timer_flags);
      dt->du_ident = _dispatch_timer_unote_idx(dt);
      dt->dt_timer.target = UINT64_MAX;
      dt->dt_timer.deadline = UINT64_MAX;
      dt->dt_timer.interval = UINT64_MAX;
      dt->dt_heap_entry[DTH_TARGET_ID] = DTH_INVALID_ID;
      dt->dt_heap_entry[DTH_DEADLINE_ID] = DTH_INVALID_ID;
      return (dispatch_unote_t) {
          ._dt = dt
      };
  }
  
  const dispatch_source_type_s _dispatch_source_type_timer = {
      .dst_kind           = "timer",
      .dst_filter         = DISPATCH_EVFILT_TIMER,
      .dst_flags          = EV_DISPATCH,
      .dst_mask           = DISPATCH_TIMER_STRICT|DISPATCH_TIMER_BACKGROUND,
      .dst_timer_flags    = 0,
      .dst_action         = DISPATCH_UNOTE_ACTION_SOURCE_TIMER,
      .dst_size           = sizeof(struct dispatch_timer_source_refs_s),
  
      .dst_create         = _dispatch_source_timer_create,
      .dst_merge_evt      = _dispatch_source_merge_evt,
  };
  
  const dispatch_source_type_s _dispatch_source_type_timer_with_clock = {
      .dst_kind           = "timer (fixed-clock)",
      .dst_filter         = DISPATCH_EVFILT_TIMER_WITH_CLOCK,
      .dst_flags          = EV_DISPATCH,
      .dst_mask           = DISPATCH_TIMER_STRICT|DISPATCH_TIMER_BACKGROUND,
      .dst_timer_flags    = 0,
      .dst_action         = DISPATCH_UNOTE_ACTION_SOURCE_TIMER,
      .dst_size           = sizeof(struct dispatch_timer_source_refs_s),
      .dst_strict         = true,
  
      .dst_create         = _dispatch_source_timer_create,
      .dst_merge_evt      = _dispatch_source_merge_evt,
  };
  
  const dispatch_source_type_s _dispatch_source_type_after = {
      .dst_kind           = "timer (after)",
      .dst_filter         = DISPATCH_EVFILT_TIMER_WITH_CLOCK,
      .dst_flags          = EV_DISPATCH,
      .dst_mask           = 0,
      .dst_timer_flags    = DISPATCH_TIMER_AFTER,
      .dst_action         = DISPATCH_UNOTE_ACTION_SOURCE_TIMER,
      .dst_size           = sizeof(struct dispatch_timer_source_refs_s),
  
      .dst_create         = _dispatch_source_timer_create,
      .dst_merge_evt      = _dispatch_source_merge_evt,
  };
  
  const dispatch_source_type_s _dispatch_source_type_interval = {
      .dst_kind           = "timer (interval)",
      .dst_filter         = DISPATCH_EVFILT_TIMER_WITH_CLOCK,
      .dst_flags          = EV_DISPATCH,
      .dst_mask           = DISPATCH_TIMER_STRICT|DISPATCH_TIMER_BACKGROUND|
      DISPATCH_INTERVAL_UI_ANIMATION,
      .dst_timer_flags    = DISPATCH_TIMER_INTERVAL|DISPATCH_TIMER_CLOCK_UPTIME,
      .dst_action         = DISPATCH_UNOTE_ACTION_SOURCE_TIMER,
      .dst_size           = sizeof(struct dispatch_timer_source_refs_s),
  
      .dst_create         = _dispatch_source_timer_create,
      .dst_merge_evt      = _dispatch_source_merge_evt,
  };
  
  #pragma mark timer draining
  
  static void
  _dispatch_timers_run(dispatch_timer_heap_t dth, uint32_t tidx,
                       dispatch_clock_now_cache_t nows) {
      dispatch_timer_source_refs_t dr;
      uint64_t pending, now;
  
      while ((dr = dth[tidx].dth_min[DTH_TARGET_ID])) {
          DISPATCH_TIMER_ASSERT(dr->du_ident, ==, tidx, "tidx");
          DISPATCH_TIMER_ASSERT(dr->dt_timer.target, !=, 0, "missing target");
  
          now = _dispatch_time_now_cached(DISPATCH_TIMER_CLOCK(tidx), nows);
          if (dr->dt_timer.target > now) {
              // Done running timers for now.
              break;
          }
  
          if (dr->du_timer_flags & DISPATCH_TIMER_AFTER) {
              _dispatch_timer_unote_disarm(dr, dth); // +2 is consumed by _merge_evt()
              _dispatch_wlh_release(_dispatch_unote_wlh(dr));
              _dispatch_unote_state_set(dr, DU_STATE_UNREGISTERED);
              os_atomic_store2o(dr, ds_pending_data, 2, relaxed);
              _dispatch_trace_timer_fire(dr, 1, 1);
              dux_merge_evt(dr, EV_ONESHOT, 0, 0);
              continue;
          }
  
          if (os_atomic_load2o(dr, dt_pending_config, relaxed)) {
              _dispatch_timer_unote_configure(dr);
              continue;
          }
  
          // We want to try to keep repeating timers in the heap if their handler
          // is keeping up to avoid useless hops through the manager thread.
          //
          // However, if we can observe a non consumed ds_pending_data, we have to
          // remove the timer from the heap until the handler keeps up (disarm).
          // Such an operation is a one-way street, as _dispatch_source_invoke2()
          // can decide to dispose of a timer without going back to the manager if
          // it can observe that it is disarmed.
          //
          // To solve this race, we use a the MISSED marker in ds_pending_data
          // with a release barrier to make the changes accumulated on `ds_timer`
          // visible to _dispatch_source_timer_data(). Doing this also transfers
          // the responsibility to call _dispatch_timer_unote_compute_missed()
          // to _dispatch_source_invoke2() without the manager involvement.
          //
          // Suspension also causes the timer to be removed from the heap. We need
          // to make sure _dispatch_source_timer_data() will recompute the proper
          // number of fired events when the source is resumed, and also use the
          // MISSED marker for this similar purpose.
          if (unlikely(os_atomic_load2o(dr, ds_pending_data, relaxed))) {
              _dispatch_timer_unote_disarm(dr, dth);
              pending = os_atomic_or_orig2o(dr, ds_pending_data,
                                            DISPATCH_TIMER_DISARMED_MARKER, relaxed);
          } else {
              pending = _dispatch_timer_unote_compute_missed(dr, now, 0) << 1;
              if (_dispatch_timer_unote_needs_rearm(dr,
                                                    DISPATCH_TIMER_UNOTE_TRACE_SUSPENSION)) {
                  // _dispatch_source_merge_evt() consumes a +2 which we transfer
                  // from the heap ownership when we disarm the timer. If it stays
                  // armed, we need to take new retain counts
                  _dispatch_retain_unote_owner(dr);
                  _dispatch_timer_unote_arm(dr, dth, tidx);
                  os_atomic_store2o(dr, ds_pending_data, pending, relaxed);
              } else {
                  _dispatch_timer_unote_disarm(dr, dth);
                  pending |= DISPATCH_TIMER_DISARMED_MARKER;
                  os_atomic_store2o(dr, ds_pending_data, pending, release);
              }
          }
          _dispatch_trace_timer_fire(dr, pending >> 1, pending >> 1);
          dux_merge_evt(dr, EV_ONESHOT, 0, 0);
      }
  }
  
  #if DISPATCH_HAVE_TIMER_COALESCING
  #define DISPATCH_KEVENT_COALESCING_WINDOW_INIT(qos, ms) \
  		[DISPATCH_TIMER_QOS_##qos] = 2ull * (ms) * NSEC_PER_MSEC
  
  static const uint64_t _dispatch_kevent_coalescing_window[] = {
      DISPATCH_KEVENT_COALESCING_WINDOW_INIT(NORMAL, 75),
  #if DISPATCH_HAVE_TIMER_QOS
      DISPATCH_KEVENT_COALESCING_WINDOW_INIT(CRITICAL, 1),
      DISPATCH_KEVENT_COALESCING_WINDOW_INIT(BACKGROUND, 100),
  #endif
  };
  #endif // DISPATCH_HAVE_TIMER_COALESCING
  
  DISPATCH_ALWAYS_INLINE
  static inline dispatch_timer_delay_s
  _dispatch_timers_get_delay(dispatch_timer_heap_t dth, uint32_t tidx,
                             uint32_t qos, dispatch_clock_now_cache_t nows) {
      uint64_t target, deadline;
      dispatch_timer_delay_s rc;
  
      if (!dth[tidx].dth_min[DTH_TARGET_ID]) {
          rc.delay = rc.leeway = INT64_MAX;
          return rc;
      }
  
      target = dth[tidx].dth_min[DTH_TARGET_ID]->dt_timer.target;
      deadline = dth[tidx].dth_min[DTH_DEADLINE_ID]->dt_timer.deadline;
      dispatch_assert(target <= deadline && target < INT64_MAX);
  
      uint64_t now = _dispatch_time_now_cached(DISPATCH_TIMER_CLOCK(tidx), nows);
      if (target <= now) {
          rc.delay = rc.leeway = 0;
          return rc;
      }
  
      if (qos < DISPATCH_TIMER_QOS_COUNT && dth[tidx].dth_count > 2) {
  #if DISPATCH_HAVE_TIMER_COALESCING
          // Timer pre-coalescing <rdar://problem/13222034>
          // When we have several timers with this target/deadline bracket:
          //
          //      Target        window  Deadline
          //        V           <-------V
          // t1:    [...........|.................]
          // t2:         [......|.......]
          // t3:             [..|..........]
          // t4:                | [.............]
          //                 ^
          //          Optimal Target
          //
          // Coalescing works better if the Target is delayed to "Optimal", by
          // picking the latest target that isn't too close to the deadline.
          uint64_t window = _dispatch_kevent_coalescing_window[qos];
          if (target + window < deadline) {
              uint64_t latest = deadline - window;
              target = _dispatch_timer_heap_max_target_before(&dth[tidx], latest);
          }
  #endif
      }
  
      rc.delay = MIN(target - now, INT64_MAX);
      rc.leeway = MIN(deadline - target, INT64_MAX);
      return rc;
  }
  
  static void
  _dispatch_timers_program(dispatch_timer_heap_t dth, uint32_t tidx,
                           dispatch_clock_now_cache_t nows) {
      uint32_t qos = DISPATCH_TIMER_QOS(tidx);
      dispatch_timer_delay_s range;
  
      range = _dispatch_timers_get_delay(dth, tidx, qos, nows);
      if (range.delay == 0) {
          _dispatch_timers_heap_dirty(dth, tidx);
      }
      if (range.delay == 0 || range.delay >= INT64_MAX) {
          _dispatch_trace_next_timer_set(NULL, qos);
          if (dth[tidx].dth_armed) {
              _dispatch_event_loop_timer_delete(dth, tidx);
          }
          dth[tidx].dth_armed = false;
          dth[tidx].dth_needs_program = false;
      } else {
          _dispatch_trace_next_timer_set(dth[tidx].dth_min[DTH_TARGET_ID], qos);
          _dispatch_trace_next_timer_program(range.delay, qos);
          _dispatch_event_loop_timer_arm(dth, tidx, range, nows);
          dth[tidx].dth_armed = true;
          dth[tidx].dth_needs_program = false;
      }
  }
  
  void
  _dispatch_event_loop_drain_timers(dispatch_timer_heap_t dth, uint32_t count) {
      dispatch_clock_now_cache_s nows = { };
      uint32_t tidx;
  
      do {
          for (tidx = 0; tidx < count; tidx++) {
              _dispatch_timers_run(dth, tidx, &nows);
          }
  
  #if DISPATCH_USE_DTRACE
          uint32_t mask = dth[0].dth_dirty_bits & DTH_DIRTY_QOS_MASK;
          while (mask && DISPATCH_TIMER_WAKE_ENABLED()) {
              int qos = __builtin_ctz(mask);
              mask -= 1 << qos;
              _dispatch_trace_timer_wake(_dispatch_trace_next_timer[qos]);
          }
  #endif // DISPATCH_USE_DTRACE
  
          dth[0].dth_dirty_bits = 0;
  
          for (tidx = 0; tidx < count; tidx++) {
              if (dth[tidx].dth_needs_program) {
                  _dispatch_timers_program(dth, tidx, &nows);
              }
          }
  
          /*
              Note: dth_dirty_bits being set again can happen if we notice
              a new configuration during _dispatch_timers_run() that causes
              the timer to change clocks for a bucket we already drained.
  
              This is however extremely unlikely, and because we drain relatively
              to a constant cached "now", this will converge quickly.
          */
      } while (unlikely(dth[0].dth_dirty_bits));
  }
  