. /include/boost/corosio /detail /timer_service.hpp
96.43% Lines (243/252) 100.00% Functions (28/28)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // 1   //
2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com) 2   // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3   // Copyright (c) 2026 Steve Gerbino 3   // Copyright (c) 2026 Steve Gerbino
4   // 4   //
5   // Distributed under the Boost Software License, Version 1.0. (See accompanying 5   // Distributed under the Boost Software License, Version 1.0. (See accompanying
6   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7   // 7   //
8   // Official repository: https://github.com/cppalliance/corosio 8   // Official repository: https://github.com/cppalliance/corosio
9   // 9   //
10   10  
11   #ifndef BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP 11   #ifndef BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP
12   #define BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP 12   #define BOOST_COROSIO_DETAIL_TIMER_SERVICE_HPP
13   13  
14   #include <boost/corosio/detail/timer.hpp> 14   #include <boost/corosio/detail/timer.hpp>
15   #include <boost/corosio/detail/scheduler.hpp> 15   #include <boost/corosio/detail/scheduler.hpp>
16   #include <boost/corosio/detail/scheduler_op.hpp> 16   #include <boost/corosio/detail/scheduler_op.hpp>
17   #include <boost/corosio/detail/object_pool.hpp> 17   #include <boost/corosio/detail/object_pool.hpp>
18   #include <boost/corosio/detail/object_ref.hpp> 18   #include <boost/corosio/detail/object_ref.hpp>
19   #include <boost/corosio/detail/intrusive.hpp> 19   #include <boost/corosio/detail/intrusive.hpp>
20   #include <boost/corosio/detail/thread_local_ptr.hpp> 20   #include <boost/corosio/detail/thread_local_ptr.hpp>
21   #include <boost/capy/error.hpp> 21   #include <boost/capy/error.hpp>
22   #include <boost/capy/ex/execution_context.hpp> 22   #include <boost/capy/ex/execution_context.hpp>
23   #include <boost/capy/ex/abandon.hpp> 23   #include <boost/capy/ex/abandon.hpp>
24   #include <boost/capy/ex/executor_ref.hpp> 24   #include <boost/capy/ex/executor_ref.hpp>
25   #include <system_error> 25   #include <system_error>
26   26  
27   #include <atomic> 27   #include <atomic>
28   #include <chrono> 28   #include <chrono>
29   #include <coroutine> 29   #include <coroutine>
30   #include <cstddef> 30   #include <cstddef>
31   #include <limits> 31   #include <limits>
32   #include <mutex> 32   #include <mutex>
33   #include <thread> 33   #include <thread>
34   #include <stop_token> 34   #include <stop_token>
35   #include <utility> 35   #include <utility>
36   #include <vector> 36   #include <vector>
37   37  
38   namespace boost::corosio::detail { 38   namespace boost::corosio::detail {
39   39  
40   class scheduler; 40   class scheduler;
41   41  
42   /* 42   /*
43   Timer Service 43   Timer Service
44   ============= 44   =============
45   45  
46   Data Structures 46   Data Structures
47   --------------- 47   ---------------
48   waiter_node (defined in timer.hpp) holds per-waiter state: 48   waiter_node (defined in timer.hpp) holds per-waiter state:
49   coroutine handle, executor, error output, embedded 49   coroutine handle, executor, error output, embedded
50   completion_op. Each concurrent co_await t.wait() embeds one 50   completion_op. Each concurrent co_await t.wait() embeds one
51   waiter_node in the awaitable on the suspended coroutine's 51   waiter_node in the awaitable on the suspended coroutine's
52   frame — waits perform no allocation. 52   frame — waits perform no allocation.
53   53  
54   timer::implementation holds per-timer state: expiry, heap 54   timer::implementation holds per-timer state: expiry, heap
55   index, and the single published waiter. Each timer holds 55   index, and the single published waiter. Each timer holds
56   at most one waiter; process_expired's local cross-timer drain 56   at most one waiter; process_expired's local cross-timer drain
57   list still threads waiters through their intrusive hooks when 57   list still threads waiters through their intrusive hooks when
58   collecting several timers' waiters past the lock. 58   collecting several timers' waiters past the lock.
59   59  
60   timer_service owns a min-heap of active timers and recycles 60   timer_service owns a min-heap of active timers and recycles
61   retired impls through a per-service object_pool, fronted by a 61   retired impls through a per-service object_pool, fronted by a
62   thread-local single-slot cache. The heap is ordered by expiry 62   thread-local single-slot cache. The heap is ordered by expiry
63   time; the scheduler queries nearest_expiry() to set the 63   time; the scheduler queries nearest_expiry() to set the
64   epoll/timerfd timeout. 64   epoll/timerfd timeout.
65   65  
66   Optimization Strategy 66   Optimization Strategy
67   --------------------- 67   ---------------------
68   1. Deferred heap insertion — expires_after() stores the expiry 68   1. Deferred heap insertion — expires_after() stores the expiry
69   but does not insert into the heap. Insertion happens in wait(). 69   but does not insert into the heap. Insertion happens in wait().
70   2. Thread-local impl cache — single-slot per-thread cache, in 70   2. Thread-local impl cache — single-slot per-thread cache, in
71   front of the object_pool fallback; keeps a thread's hot impl 71   front of the object_pool fallback; keeps a thread's hot impl
72   out of the shared free list. 72   out of the shared free list.
73   3. Frame-resident waiter_node with embedded completion_op — 73   3. Frame-resident waiter_node with embedded completion_op —
74   eliminates heap allocation per wait/fire/cancel. 74   eliminates heap allocation per wait/fire/cancel.
75   4. Cached nearest expiry — atomic avoids mutex in nearest_expiry(). 75   4. Cached nearest expiry — atomic avoids mutex in nearest_expiry().
76   5. might_have_pending_waits_ flag — skips lock when no wait issued. 76   5. might_have_pending_waits_ flag — skips lock when no wait issued.
77   77  
78   Concurrency 78   Concurrency
79   ----------- 79   -----------
80   stop_token callbacks can fire from any thread. The impl_ 80   stop_token callbacks can fire from any thread. The impl_
81   pointer on waiter_node is used as a "still in list" marker. 81   pointer on waiter_node is used as a "still in list" marker.
82   A waiter_node's storage is the suspended coroutine's frame: 82   A waiter_node's storage is the suspended coroutine's frame:
83   every completion path must finish touching the node before 83   every completion path must finish touching the node before
84 - posting the continuation or destroying the handle. 84 + dispatching the continuation or destroying the handle.
85   */ 85   */
86   86  
87   inline void timer_service_invalidate_cache() noexcept; 87   inline void timer_service_invalidate_cache() noexcept;
88   88  
89   /** The timer service's recycling pool. 89   /** The timer service's recycling pool.
90   90  
91   Adds no behavior of its own — it exists only to re-expose 91   Adds no behavior of its own — it exists only to re-expose
92   `adopt()` and `remove()` as public, so the timer service's 92   `adopt()` and `remove()` as public, so the timer service's
93   thread-local cache can transfer a cached impl's `live_` tracking 93   thread-local cache can transfer a cached impl's `live_` tracking
94   on both sides of the handoff: `construct()` re-adopts a 94   on both sides of the handoff: `construct()` re-adopts a
95   TL-cached impl as live, `shutdown()` detaches one before its 95   TL-cached impl as live, `shutdown()` detaches one before its
96   direct delete. 96   direct delete.
97   */ 97   */
98   class timer_object_pool : public object_pool<timer::implementation> 98   class timer_object_pool : public object_pool<timer::implementation>
99   { 99   {
100   public: 100   public:
101   using object_pool::adopt; 101   using object_pool::adopt;
102   using object_pool::remove; 102   using object_pool::remove;
103   }; 103   };
104   104  
105   // timer_service class body — member function definitions are 105   // timer_service class body — member function definitions are
106   // out-of-class (after implementation and waiter_node are complete) 106   // out-of-class (after implementation and waiter_node are complete)
107   class BOOST_COROSIO_DECL timer_service final 107   class BOOST_COROSIO_DECL timer_service final
108   : public capy::execution_context::service 108   : public capy::execution_context::service
109   , public io_object::io_service 109   , public io_object::io_service
110   { 110   {
111   friend struct timer::implementation; 111   friend struct timer::implementation;
112   112  
113   public: 113   public:
114   using clock_type = std::chrono::steady_clock; 114   using clock_type = std::chrono::steady_clock;
115   using time_point = clock_type::time_point; 115   using time_point = clock_type::time_point;
116   116  
117   /// Type-erased callback for earliest-expiry-changed notifications. 117   /// Type-erased callback for earliest-expiry-changed notifications.
118   class callback 118   class callback
119   { 119   {
120   void* ctx_ = nullptr; 120   void* ctx_ = nullptr;
121   void (*fn_)(void*) = nullptr; 121   void (*fn_)(void*) = nullptr;
122   122  
123   public: 123   public:
124   /// Construct an empty callback. 124   /// Construct an empty callback.
HITCBC 125   4417 callback() = default; 125   931 callback() = default;
126   126  
127   /// Construct a callback with the given context and function. 127   /// Construct a callback with the given context and function.
HITCBC 128   4417 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {} 128   927 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {}
129   129  
130   /// Return true if the callback is non-empty. 130   /// Return true if the callback is non-empty.
131   explicit operator bool() const noexcept 131   explicit operator bool() const noexcept
132   { 132   {
133   return fn_ != nullptr; 133   return fn_ != nullptr;
134   } 134   }
135   135  
136   /// Invoke the callback. 136   /// Invoke the callback.
HITCBC 137   8153 void operator()() const 137   7841 void operator()() const
138   { 138   {
HITCBC 139   8153 if (fn_) 139   7841 if (fn_)
HITCBC 140   8153 fn_(ctx_); 140   7841 fn_(ctx_);
HITCBC 141   8153 } 141   7841 }
142   }; 142   };
143   143  
144   private: 144   private:
145   struct heap_entry 145   struct heap_entry
146   { 146   {
147   time_point time_; 147   time_point time_;
148   timer::implementation* timer_; 148   timer::implementation* timer_;
149   }; 149   };
150   150  
151   scheduler* sched_ = nullptr; 151   scheduler* sched_ = nullptr;
152   BOOST_COROSIO_MSVC_WARNING_PUSH 152   BOOST_COROSIO_MSVC_WARNING_PUSH
153   BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface 153   BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface
154   mutable std::mutex mutex_; 154   mutable std::mutex mutex_;
155   std::vector<heap_entry> heap_; 155   std::vector<heap_entry> heap_;
156   timer_object_pool pool_; 156   timer_object_pool pool_;
157   callback on_earliest_changed_; 157   callback on_earliest_changed_;
158   bool shutting_down_ = false; 158   bool shutting_down_ = false;
  159 + // Set once the scheduler waits on this service; read without the
  160 + // mutex by every timer construction after the first.
  161 + std::atomic<bool> attached_{false};
159   162  
160   // Cancellers that claimed a waiter and have yet to post it; 163   // Cancellers that claimed a waiter and have yet to post it;
161   // shutdown waits them out so the scheduler's drain finds the post. 164   // shutdown waits them out so the scheduler's drain finds the post.
162   std::size_t cancels_posting_ = 0; // guarded by mutex_ 165   std::size_t cancels_posting_ = 0; // guarded by mutex_
163   // Avoids mutex in nearest_expiry() and empty() 166   // Avoids mutex in nearest_expiry() and empty()
164   mutable std::atomic<std::int64_t> cached_nearest_ns_{ 167   mutable std::atomic<std::int64_t> cached_nearest_ns_{
165   (std::numeric_limits<std::int64_t>::max)()}; 168   (std::numeric_limits<std::int64_t>::max)()};
166   BOOST_COROSIO_MSVC_WARNING_POP 169   BOOST_COROSIO_MSVC_WARNING_POP
167   170  
168   public: 171   public:
169 - /// Construct the timer service bound to a scheduler. 172 + /** Construct the timer service for a context's scheduler.
ECB 170 - 4417 inline timer_service(capy::execution_context&, scheduler& sched) 173 +
ECB 171 - 4417 : sched_(&sched) 174 + Created with the context's first timer. It does not attach to
  175 + the scheduler here: a concurrent first use may construct a
  176 + second service that the context then discards. See
  177 + @ref attach.
  178 +
  179 + @throws std::logic_error if the context has no scheduler.
  180 + */
HITGNC   181 + 931 inline explicit timer_service(capy::execution_context& ctx)
HITGNC   182 + 931 : sched_(ctx.find_service<scheduler>())
172   { 183   {
HITGNC   184 + 931 if (!sched_)
HITGNC   185 + 4 detail::throw_logic_error(
  186 + "timer_service: the context has no scheduler");
HITCBC 173   4417 } 187   943 }
174   188  
175   /// Return the associated scheduler. 189   /// Return the associated scheduler.
HITCBC 176   35542 inline scheduler& get_scheduler() noexcept 190   34867 inline scheduler& get_scheduler() noexcept
177   { 191   {
HITCBC 178   35542 return *sched_; 192   34867 return *sched_;
179   } 193   }
180   194  
181 - /// Destroy the timer service. 195 + /// Destroy the timer service, detaching it from the scheduler.
HITCBC 182 - 8834 ~timer_service() override = default; 196 + 1854 ~timer_service() override
HITGNC   197 + 927 {
HITGNC   198 + 927 if (attached_.load(std::memory_order_acquire))
HITGNC   199 + 927 sched_->detach_timer_service();
HITGNC   200 + 1854 }
  201 +
  202 + /** Attach this service to the scheduler, if not yet attached.
  203 +
  204 + Call once the context has settled which service it keeps; no
  205 + timer of this service can wait before this returns.
  206 +
  207 + @par Exception Safety
  208 + Strong guarantee: on failure the service stays detached and
  209 + the next call retries.
  210 + */
HITGNC   211 + 19991 inline void attach()
  212 + {
HITGNC   213 + 19991 if (attached_.load(std::memory_order_acquire))
HITGNC   214 + 19064 return;
HITGNC   215 + 928 std::lock_guard lock(mutex_);
HITGNC   216 + 928 if (attached_.load(std::memory_order_relaxed))
HITGNC   217 + 1 return;
HITGNC   218 + 927 sched_->attach_timer_service(*this);
HITGNC   219 + 927 attached_.store(true, std::memory_order_release);
HITGNC   220 + 928 }
183   221  
184   timer_service(timer_service const&) = delete; 222   timer_service(timer_service const&) = delete;
185   timer_service& operator=(timer_service const&) = delete; 223   timer_service& operator=(timer_service const&) = delete;
186   224  
187   /// Register a callback invoked when the earliest expiry changes. 225   /// Register a callback invoked when the earliest expiry changes.
HITCBC 188   4417 inline void set_on_earliest_changed(callback cb) 226   927 inline void set_on_earliest_changed(callback cb)
189   { 227   {
HITCBC 190   4417 on_earliest_changed_ = cb; 228   927 on_earliest_changed_ = cb;
HITCBC 191   4417 } 229   927 }
192   230  
193   /// Return true if no timers are in the heap. 231   /// Return true if no timers are in the heap.
194   inline bool empty() const noexcept 232   inline bool empty() const noexcept
195   { 233   {
196   return cached_nearest_ns_.load(std::memory_order_acquire) == 234   return cached_nearest_ns_.load(std::memory_order_acquire) ==
197   (std::numeric_limits<std::int64_t>::max)(); 235   (std::numeric_limits<std::int64_t>::max)();
198   } 236   }
199   237  
200   /// Return the nearest timer expiry without acquiring the mutex. 238   /// Return the nearest timer expiry without acquiring the mutex.
HITCBC 201   30205 inline time_point nearest_expiry() const noexcept 239   18038 inline time_point nearest_expiry() const noexcept
202   { 240   {
HITCBC 203   30205 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 241   18038 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 204   30205 return time_point(time_point::duration(ns)); 242   18038 return time_point(time_point::duration(ns));
205   } 243   }
206   244  
207   /// Cancel all pending timers and free cached resources. 245   /// Cancel all pending timers and free cached resources.
208   inline void shutdown() override; 246   inline void shutdown() override;
209   247  
210   /// Construct a new timer implementation. 248   /// Construct a new timer implementation.
211   inline io_object::implementation* construct() override; 249   inline io_object::implementation* construct() override;
212   250  
213   /// Destroy a timer implementation, cancelling pending waiters. 251   /// Destroy a timer implementation, cancelling pending waiters.
214   inline void destroy(io_object::implementation* p) override; 252   inline void destroy(io_object::implementation* p) override;
215   253  
216   /// Cancel and recycle a timer implementation. 254   /// Cancel and recycle a timer implementation.
217   inline void destroy_impl(timer::implementation& impl); 255   inline void destroy_impl(timer::implementation& impl);
218   256  
219   /// Publish the timer's waiter and insert the timer into the heap. 257   /// Publish the timer's waiter and insert the timer into the heap.
220   inline void insert_waiter(timer::implementation& impl, waiter_node* w); 258   inline void insert_waiter(timer::implementation& impl, waiter_node* w);
221   259  
222   /// Cancel the timer's published waiter, if any. 260   /// Cancel the timer's published waiter, if any.
223   inline void cancel_timer(timer::implementation& impl); 261   inline void cancel_timer(timer::implementation& impl);
224   262  
225   /// Cancel one specific waiter ( stop_token callback path ). 263   /// Cancel one specific waiter ( stop_token callback path ).
226   inline void cancel_waiter(waiter_node* w); 264   inline void cancel_waiter(waiter_node* w);
227   265  
228   /// Complete all waiters whose timers have expired. 266   /// Complete all waiters whose timers have expired.
229   inline std::size_t process_expired(); 267   inline std::size_t process_expired();
230   268  
231   private: 269   private:
HITCBC 232   183945 inline void refresh_cached_nearest() noexcept 270   61911 inline void refresh_cached_nearest() noexcept
233   { 271   {
HITCBC 234   183945 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 272   61911 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 235   63472 : heap_[0].time_.time_since_epoch().count(); 273   58660 : heap_[0].time_.time_since_epoch().count();
HITCBC 236   183945 cached_nearest_ns_.store(ns, std::memory_order_release); 274   61911 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 237   183945 } 275   61911 }
238   276  
239   inline void remove_timer_impl(timer::implementation& impl); 277   inline void remove_timer_impl(timer::implementation& impl);
240   inline void up_heap(std::size_t index); 278   inline void up_heap(std::size_t index);
241   inline void down_heap(std::size_t index); 279   inline void down_heap(std::size_t index);
242   inline void swap_heap(std::size_t i1, std::size_t i2); 280   inline void swap_heap(std::size_t i1, std::size_t i2);
243   }; 281   };
244   282  
245   // Thread-local single-slot impl cache, validated by comparing svc_. 283   // Thread-local single-slot impl cache, validated by comparing svc_.
246   // Keeps a hot impl out of the shared free list; both sides still 284   // Keeps a hot impl out of the shared free list; both sides still
247   // take the pool lock to move it in and out of live tracking. 285   // take the pool lock to move it in and out of live tracking.
248   // Cleared by timer_service_invalidate_cache() during shutdown. 286   // Cleared by timer_service_invalidate_cache() during shutdown.
249   287  
250   inline thread_local_ptr<timer::implementation> tl_cached_impl; 288   inline thread_local_ptr<timer::implementation> tl_cached_impl;
251   289  
252   // The POD TLS slot above never runs destructors, so a short-lived 290   // The POD TLS slot above never runs destructors, so a short-lived
253   // run() thread would leak its cached impl. Each push arms this 291   // run() thread would leak its cached impl. Each push arms this
254   // owner, whose destructor frees the slot at thread exit. A cached 292   // owner, whose destructor frees the slot at thread exit. A cached
255   // entry is a quiescent heap object (nothing in the heap or free 293   // entry is a quiescent heap object (nothing in the heap or free
256   // list) and deletion touches no service state, so it is safe after 294   // list) and deletion touches no service state, so it is safe after
257   // the owning service is gone (the stale-entry path in 295   // the owning service is gone (the stale-entry path in
258   // try_pop_tl_cache deletes the same way). 296   // try_pop_tl_cache deletes the same way).
259   struct tl_cache_owner 297   struct tl_cache_owner
260   { 298   {
HITCBC 261   63 ~tl_cache_owner() 299   62 ~tl_cache_owner()
262   { 300   {
HITCBC 263   63 delete tl_cached_impl.get(); 301   62 delete tl_cached_impl.get();
HITCBC 264   63 tl_cached_impl.set(nullptr); 302   62 tl_cached_impl.set(nullptr);
HITCBC 265   63 } 303   62 }
266   }; 304   };
267   305  
268   inline void 306   inline void
HITCBC 269   15178 arm_tl_cache_cleanup() noexcept 307   14999 arm_tl_cache_cleanup() noexcept
270   { 308   {
HITCBC 271   15178 [[maybe_unused]] thread_local tl_cache_owner owner; 309   14999 [[maybe_unused]] thread_local tl_cache_owner owner;
HITCBC 272   15178 } 310   14999 }
273   311  
274   inline timer::implementation* 312   inline timer::implementation*
HITCBC 275   20311 try_pop_tl_cache(timer_service* svc) noexcept 313   19991 try_pop_tl_cache(timer_service* svc) noexcept
276   { 314   {
HITCBC 277   20311 auto* impl = tl_cached_impl.get(); 315   19991 auto* impl = tl_cached_impl.get();
HITCBC 278   20311 if (impl) 316   19991 if (impl)
279   { 317   {
HITCBC 280   14672 tl_cached_impl.set(nullptr); 318   14486 tl_cached_impl.set(nullptr);
HITCBC 281   14672 if (impl->svc_ == svc) 319   14486 if (impl->svc_ == svc)
HITCBC 282   14672 return impl; 320   14486 return impl;
283   // Stale impl from a destroyed service 321   // Stale impl from a destroyed service
MISUBC 284   ✗ delete impl; 322   ✗ delete impl;
285   } 323   }
HITCBC 286   5639 return nullptr; 324   5505 return nullptr;
287   } 325   }
288   326  
289   inline bool 327   inline bool
HITCBC 290   17060 try_push_tl_cache(timer::implementation* impl) noexcept 328   16740 try_push_tl_cache(timer::implementation* impl) noexcept
291   { 329   {
HITCBC 292   17060 if (!tl_cached_impl.get()) 330   16740 if (!tl_cached_impl.get())
293   { 331   {
HITCBC 294   15178 arm_tl_cache_cleanup(); 332   14999 arm_tl_cache_cleanup();
HITCBC 295   15178 tl_cached_impl.set(impl); 333   14999 tl_cached_impl.set(impl);
HITCBC 296   15178 return true; 334   14999 return true;
297   } 335   }
HITCBC 298   1882 return false; 336   1741 return false;
299   } 337   }
300   338  
301   inline void 339   inline void
HITCBC 302   8834 timer_service_invalidate_cache() noexcept 340   927 timer_service_invalidate_cache() noexcept
303   { 341   {
HITCBC 304   8834 delete tl_cached_impl.get(); 342   927 delete tl_cached_impl.get();
HITCBC 305   8834 tl_cached_impl.set(nullptr); 343   927 tl_cached_impl.set(nullptr);
HITCBC 306   8834 } 344   927 }
307   345  
308   // timer_service out-of-class member function definitions 346   // timer_service out-of-class member function definitions
309   347  
310   inline void 348   inline void
HITCBC 311   8834 timer_service::shutdown() 349   927 timer_service::shutdown()
312   { 350   {
HITCBC 313   8834 timer_service_invalidate_cache(); 351   927 timer_service_invalidate_cache();
HITCBC 314   8834 shutting_down_ = true; 352   927 shutting_down_ = true;
315   // Flag only; the real drain walks the expiry heap below, not 353   // Flag only; the real drain walks the expiry heap below, not
316   // object_pool's live_ list, so the visit callback is a no-op. 354   // object_pool's live_ list, so the visit callback is a no-op.
HITCBC 317   8834 pool_.shutdown([](timer::implementation*) {}); 355   927 pool_.shutdown([](timer::implementation*) {});
318   356  
319   // Snapshot impls and detach them from the heap so that 357   // Snapshot impls and detach them from the heap so that
320   // coroutine-owned timer destructors (run by the unwinds the 358   // coroutine-owned timer destructors (run by the unwinds the
321   // abandons below start) cannot re-enter remove_timer_impl() and 359   // abandons below start) cannot re-enter remove_timer_impl() and
322   // mutate the vector during iteration. A stop requested on another thread 360   // mutate the vector during iteration. A stop requested on another thread
323   // reaches cancel_waiter() under the same lock: whichever side 361   // reaches cancel_waiter() under the same lock: whichever side
324   // claims a waiter first owns it, and a waiter its canceller 362   // claims a waiter first owns it, and a waiter its canceller
325   // claimed is posted, so the scheduler's drain abandons it. 363   // claimed is posted, so the scheduler's drain abandons it.
HITCBC 326   8834 std::vector<timer::implementation*> impls; 364   927 std::vector<timer::implementation*> impls;
HITCBC 327   8834 std::vector<waiter_node*> waiters; 365   927 std::vector<waiter_node*> waiters;
328   { 366   {
HITCBC 329   8834 std::lock_guard lock(mutex_); 367   927 std::lock_guard lock(mutex_);
HITCBC 330   8834 impls.reserve(heap_.size()); 368   927 impls.reserve(heap_.size());
HITCBC 331   8834 waiters.reserve(heap_.size()); 369   927 waiters.reserve(heap_.size());
HITCBC 332   12062 for (auto& entry : heap_) 370   4174 for (auto& entry : heap_)
333   { 371   {
HITCBC 334   3228 entry.timer_->heap_index_.store( 372   3247 entry.timer_->heap_index_.store(
335   (std::numeric_limits<std::size_t>::max)(), 373   (std::numeric_limits<std::size_t>::max)(),
336   std::memory_order_relaxed); 374   std::memory_order_relaxed);
HITCBC 337   3228 impls.push_back(entry.timer_); 375   3247 impls.push_back(entry.timer_);
HITCBC 338   3228 if (auto* w = std::exchange(entry.timer_->waiter_, nullptr)) 376   3247 if (auto* w = std::exchange(entry.timer_->waiter_, nullptr))
339   { 377   {
HITCBC 340   3228 w->impl_ = nullptr; 378   3247 w->impl_ = nullptr;
HITCBC 341   3228 waiters.push_back(w); 379   3247 waiters.push_back(w);
342   } 380   }
343   } 381   }
HITCBC 344   8834 heap_.clear(); 382   927 heap_.clear();
HITCBC 345   8834 cached_nearest_ns_.store( 383   927 cached_nearest_ns_.store(
346   (std::numeric_limits<std::int64_t>::max)(), 384   (std::numeric_limits<std::int64_t>::max)(),
347   std::memory_order_release); 385   std::memory_order_release);
HITCBC 348   8834 } 386   927 }
349   387  
350   // A stop on another thread may have claimed its waiter before the 388   // A stop on another thread may have claimed its waiter before the
351   // pass above and still be posting it; the scheduler drains next, 389   // pass above and still be posting it; the scheduler drains next,
352   // and must find that post. 390   // and must find that post.
353   for (;;) 391   for (;;)
354   { 392   {
355   { 393   {
HITCBC 356   9368 std::lock_guard lock(mutex_); 394   927 std::lock_guard lock(mutex_);
HITCBC 357   9368 if (cancels_posting_ == 0) 395   927 if (cancels_posting_ == 0)
HITCBC 358   8834 break; 396   927 break;
HITCBC 359   9368 } 397   927 }
MISLBC 360   534 std::this_thread::yield(); 398   ✗ std::this_thread::yield();
MISLBC 361   534 } 399   ✗ }
362   400  
363   // Cancel waiting timers. Each waiter called work_started() 401   // Cancel waiting timers. Each waiter called work_started()
364   // in implementation::wait(); a waiter given up here never 402   // in implementation::wait(); a waiter given up here never
365   // completes, so its work is finished here to keep the count 403   // completes, so its work is finished here to keep the count
366   // balanced. Resetting the stop callback outside the lock 404   // balanced. Resetting the stop callback outside the lock
367   // waits out a canceller already running, which finds the waiter 405   // waits out a canceller already running, which finds the waiter
368   // claimed. 406   // claimed.
HITCBC 369   12062 for (auto* w : waiters) 407   4174 for (auto* w : waiters)
370   { 408   {
HITCBC 371   3228 w->reset_stop_cb(); 409   3247 w->reset_stop_cb();
HITCBC 372   3228 auto c = std::exchange(w->cont_, {}); 410   3247 auto c = std::exchange(w->cont_, {});
HITCBC 373   3228 sched_->work_finished(); 411   3247 sched_->work_finished();
374   // Unwinding the frame also ends the node's storage 412   // Unwinding the frame also ends the node's storage
HITCBC 375   3228 if (c.h) 413   3247 if (c.h)
HITCBC 376   3228 capy::abandon(c); 414   3247 capy::abandon(c);
377   } 415   }
378   416  
HITCBC 379   12062 for (auto* impl : impls) 417   4174 for (auto* impl : impls)
380   { 418   {
381   // Unlink from the pool's live_ list before the direct delete 419   // Unlink from the pool's live_ list before the direct delete
382   // below, or ~object_pool()'s unconditional sweep would delete 420   // below, or ~object_pool()'s unconditional sweep would delete
383   // this impl a second time. 421   // this impl a second time.
HITCBC 384   3228 [[maybe_unused]] bool const removed = pool_.remove(impl); 422   3247 [[maybe_unused]] bool const removed = pool_.remove(impl);
HITCBC 385   3228 BOOST_COROSIO_ASSERT(removed); 423   3247 BOOST_COROSIO_ASSERT(removed);
HITCBC 386   3228 delete impl; 424   3247 delete impl;
387   } 425   }
388   426  
389   // Anything still parked in pool_ (free-listed or live with no 427   // Anything still parked in pool_ (free-listed or live with no
390   // pending wait at shutdown) is freed by object_pool's own destructor. 428   // pending wait at shutdown) is freed by object_pool's own destructor.
HITCBC 391   8834 } 429   927 }
392   430  
393   inline io_object::implementation* 431   inline io_object::implementation*
HITCBC 394   20311 timer_service::construct() 432   19991 timer_service::construct()
395   { 433   {
HITCBC 396   20311 timer::implementation* impl = try_pop_tl_cache(this); 434   19991 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 397   20311 if (impl) 435   19991 if (impl)
398   { 436   {
HITCBC 399   14672 impl->svc_ = this; 437   14486 impl->svc_ = this;
HITCBC 400   14672 impl->reuse(); 438   14486 impl->reuse();
HITCBC 401   14672 impl->refs_.store(1, std::memory_order_relaxed); 439   14486 impl->refs_.store(1, std::memory_order_relaxed);
402   // The TL push that parked impl here also removed it from 440   // The TL push that parked impl here also removed it from
403   // live_ (see destroy_impl) — re-adopt it now that it is live 441   // live_ (see destroy_impl) — re-adopt it now that it is live
404   // again. 442   // again.
HITCBC 405   14672 pool_.adopt(impl); 443   14486 pool_.adopt(impl);
HITCBC 406   14672 return impl; 444   14486 return impl;
407   } 445   }
408   446  
HITCBC 409   5639 return pool_.acquire(*this); 447   5505 return pool_.acquire(*this);
410   } 448   }
411   449  
412   inline void 450   inline void
HITCBC 413   20311 timer_service::destroy(io_object::implementation* p) 451   19991 timer_service::destroy(io_object::implementation* p)
414   { 452   {
415   // During shutdown the drain loop owns every impl and deletes 453   // During shutdown the drain loop owns every impl and deletes
416   // them directly. A frame destroyed by that loop can unwind a 454   // them directly. A frame destroyed by that loop can unwind a
417   // handle whose impl was freed in an earlier iteration (a 455   // handle whose impl was freed in an earlier iteration (a
418   // timeout's parent frame owns the timeout timer while 456   // timeout's parent frame owns the timeout timer while
419   // suspended on the inner delay's timer), so bail out before 457   // suspended on the inner delay's timer), so bail out before
420   // even downcasting the pointer. 458   // even downcasting the pointer.
HITCBC 421   20311 if (shutting_down_) 459   19991 if (shutting_down_)
HITCBC 422   3251 return; 460   3251 return;
HITCBC 423   17060 destroy_impl(static_cast<timer::implementation&>(*p)); 461   16740 destroy_impl(static_cast<timer::implementation&>(*p));
424   } 462   }
425   463  
426   inline void 464   inline void
HITCBC 427   17060 timer_service::destroy_impl(timer::implementation& impl) 465   16740 timer_service::destroy_impl(timer::implementation& impl)
428   { 466   {
429   // During shutdown the impl is owned by the shutdown loop. 467   // During shutdown the impl is owned by the shutdown loop.
430   // Re-entering here (from a coroutine-owned timer destructor 468   // Re-entering here (from a coroutine-owned timer destructor
431   // triggered by h.destroy()) must not modify the heap or 469   // triggered by h.destroy()) must not modify the heap or
432   // recycle the impl — shutdown deletes it directly. 470   // recycle the impl — shutdown deletes it directly.
HITCBC 433   17060 if (shutting_down_) 471   16740 if (shutting_down_)
MISUBC 434   ✗ return; 472   ✗ return;
435   473  
HITCBC 436   17060 cancel_timer(impl); 474   16740 cancel_timer(impl);
437   475  
HITCBC 438   34120 if (impl.heap_index_.load(std::memory_order_relaxed) != 476   33480 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 439   17060 (std::numeric_limits<std::size_t>::max)()) 477   16740 (std::numeric_limits<std::size_t>::max)())
440   { 478   {
MISUBC 441   ✗ std::lock_guard lock(mutex_); 479   ✗ std::lock_guard lock(mutex_);
MISUBC 442   ✗ remove_timer_impl(impl); 480   ✗ remove_timer_impl(impl);
MISUBC 443   ✗ refresh_cached_nearest(); 481   ✗ refresh_cached_nearest();
MISUBC 444   ✗ } 482   ✗ }
445   483  
HITCBC 446   17060 if (try_push_tl_cache(&impl)) 484   16740 if (try_push_tl_cache(&impl))
447   { 485   {
448   // The TL slot takes sole ownership: it is deleted directly by 486   // The TL slot takes sole ownership: it is deleted directly by
449   // tl_cache_owner / the stale-service path, never through this 487   // tl_cache_owner / the stale-service path, never through this
450   // pool, so it must leave live_ now or ~object_pool() would see 488   // pool, so it must leave live_ now or ~object_pool() would see
451   // it as abandoned (and, at the wrong moment, double-delete it 489   // it as abandoned (and, at the wrong moment, double-delete it
452   // after a later construct() re-adopts it). 490   // after a later construct() re-adopts it).
HITCBC 453   15178 [[maybe_unused]] bool const removed = pool_.remove(&impl); 491   14999 [[maybe_unused]] bool const removed = pool_.remove(&impl);
HITCBC 454   15178 BOOST_COROSIO_ASSERT(removed); 492   14999 BOOST_COROSIO_ASSERT(removed);
HITCBC 455   15178 return; 493   14999 return;
456   } 494   }
457   495  
458   // No op keepalives on a timer impl: this is the only reference, 496   // No op keepalives on a timer impl: this is the only reference,
459   // so release() always recycles immediately via retire(). 497   // so release() always recycles immediately via retire().
HITCBC 460   1882 release(&impl); 498   1741 release(&impl);
461   } 499   }
462   500  
463   inline void 501   inline void
HITCBC 464   25430 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 502   24030 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
465   { 503   {
HITCBC 466   25430 bool notify = false; 504   24030 bool notify = false;
HITCBC 467   25430 bool lost_cancel = false; 505   24030 bool lost_cancel = false;
468   { 506   {
HITCBC 469   25430 std::lock_guard lock(mutex_); 507   24030 std::lock_guard lock(mutex_);
470   // Grow before publishing anything, so the push_back below 508   // Grow before publishing anything, so the push_back below
471   // cannot throw: a failure here leaves the waiter untouched, 509   // cannot throw: a failure here leaves the waiter untouched,
472   // the strong guarantee rearm_wait's recovery relies on. 510   // the strong guarantee rearm_wait's recovery relies on.
HITCBC 473   25430 if (impl.heap_index_.load(std::memory_order_relaxed) == 511   24030 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 474   50860 (std::numeric_limits<std::size_t>::max)() && 512   48060 (std::numeric_limits<std::size_t>::max)() &&
HITCBC 475   25430 heap_.size() == heap_.capacity()) 513   24030 heap_.size() == heap_.capacity())
HITCBC 476   945 heap_.reserve(heap_.capacity() == 0 ? 16 : 2 * heap_.capacity()); 514   945 heap_.reserve(heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
477   // Publish: from here the waiter is visible to the fire path and 515   // Publish: from here the waiter is visible to the fire path and
478   // to its own stop callback (impl_ non-null enables cancel_waiter). 516   // to its own stop callback (impl_ non-null enables cancel_waiter).
HITCBC 479   25430 w->impl_ = &impl; 517   24030 w->impl_ = &impl;
HITCBC 480   50860 if (impl.heap_index_.load(std::memory_order_relaxed) == 518   48060 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 481   25430 (std::numeric_limits<std::size_t>::max)()) 519   24030 (std::numeric_limits<std::size_t>::max)())
482   { 520   {
HITCBC 483   25430 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 521   24030 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 484   25430 heap_.push_back({impl.expiry_, &impl}); 522   24030 heap_.push_back({impl.expiry_, &impl});
HITCBC 485   25430 up_heap(heap_.size() - 1); 523   24030 up_heap(heap_.size() - 1);
HITCBC 486   25430 notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0); 524   24030 notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 487   25430 refresh_cached_nearest(); 525   24030 refresh_cached_nearest();
488   } 526   }
HITCBC 489   25430 BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr); 527   24030 BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
HITCBC 490   25430 impl.waiter_ = w; 528   24030 impl.waiter_ = w;
491   529  
492   // Lost-cancel re-check: a stop requested after the canceller was 530   // Lost-cancel re-check: a stop requested after the canceller was
493   // armed in wait() but before this publication found impl_ null 531   // armed in wait() but before this publication found impl_ null
494   // and returned a no-op. Observe it now and undo the insertion. 532   // and returned a no-op. Observe it now and undo the insertion.
HITCBC 495   25430 if (w->token_->stop_requested()) 533   24030 if (w->token_->stop_requested())
496   { 534   {
HITCBC 497   394 w->impl_ = nullptr; 535   255 w->impl_ = nullptr;
HITCBC 498   394 impl.waiter_ = nullptr; 536   255 impl.waiter_ = nullptr;
HITCBC 499   394 remove_timer_impl(impl); 537   255 remove_timer_impl(impl);
HITCBC 500   394 impl.might_have_pending_waits_.store( 538   255 impl.might_have_pending_waits_.store(
501   false, std::memory_order_release); 539   false, std::memory_order_release);
HITCBC 502   394 refresh_cached_nearest(); 540   255 refresh_cached_nearest();
HITCBC 503   394 lost_cancel = true; 541   255 lost_cancel = true;
HITCBC 504   394 notify = false; // insertion undone; nearest unchanged 542   255 notify = false; // insertion undone; nearest unchanged
505   } 543   }
HITCBC 506   25430 } 544   24030 }
HITCBC 507   25430 if (notify) 545   24030 if (notify)
HITCBC 508   8153 on_earliest_changed_(); 546   7841 on_earliest_changed_();
HITCBC 509   25430 if (lost_cancel) 547   24030 if (lost_cancel)
510   { 548   {
HITCBC 511   394 w->ec_ = make_error_code(capy::error::canceled); 549   255 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 512   394 sched_->post(&w->op_); 550   255 sched_->post(&w->op_);
513   } 551   }
HITCBC 514   25430 } 552   24030 }
515   553  
516   inline void 554   inline void
HITCBC 517   17060 timer_service::cancel_timer(timer::implementation& impl) 555   16740 timer_service::cancel_timer(timer::implementation& impl)
518   { 556   {
519   // Acquire pairs with the drains' release: a caller that skips the 557   // Acquire pairs with the drains' release: a caller that skips the
520   // lock may recycle the impl next, so the drain's writes to it must 558   // lock may recycle the impl next, so the drain's writes to it must
521   // happen before. 559   // happen before.
HITCBC 522   17060 if (!impl.might_have_pending_waits_.load(std::memory_order_acquire)) 560   16740 if (!impl.might_have_pending_waits_.load(std::memory_order_acquire))
HITCBC 523   17058 return; 561   16738 return;
524   562  
525   // No unlocked already-done fast-out here: it would need the 563   // No unlocked already-done fast-out here: it would need the
526   // non-atomic waiter_ (a race with concurrent drains), and an 564   // non-atomic waiter_ (a race with concurrent drains), and an
527   // index-only check is lifetime-unsafe because npos is stored 565   // index-only check is lifetime-unsafe because npos is stored
528   // before the drain finishes touching the impl. A stale-true 566   // before the drain finishes touching the impl. A stale-true
529   // flag is rare with the stateless API; the locked path below 567   // flag is rare with the stateless API; the locked path below
530   // re-validates. 568   // re-validates.
531   569  
HITCBC 532   2 waiter_node* canceled = nullptr; 570   2 waiter_node* canceled = nullptr;
533   571  
534   { 572   {
HITCBC 535   2 std::lock_guard lock(mutex_); 573   2 std::lock_guard lock(mutex_);
HITCBC 536   2 remove_timer_impl(impl); 574   2 remove_timer_impl(impl);
HITCBC 537   2 canceled = std::exchange(impl.waiter_, nullptr); 575   2 canceled = std::exchange(impl.waiter_, nullptr);
HITCBC 538   2 if (canceled) 576   2 if (canceled)
HITCBC 539   2 canceled->impl_ = nullptr; 577   2 canceled->impl_ = nullptr;
540   // Store false as the final touch of the impl under the lock so 578   // Store false as the final touch of the impl under the lock so
541   // a pre-lock false-flag check trusts it unqualified. 579   // a pre-lock false-flag check trusts it unqualified.
HITCBC 542   2 impl.might_have_pending_waits_.store(false, std::memory_order_release); 580   2 impl.might_have_pending_waits_.store(false, std::memory_order_release);
HITCBC 543   2 refresh_cached_nearest(); 581   2 refresh_cached_nearest();
HITCBC 544   2 } 582   2 }
545   583  
HITCBC 546   2 if (canceled) 584   2 if (canceled)
547   { 585   {
HITCBC 548   2 canceled->ec_ = make_error_code(capy::error::canceled); 586   2 canceled->ec_ = make_error_code(capy::error::canceled);
HITCBC 549   2 sched_->post(&canceled->op_); 587   2 sched_->post(&canceled->op_);
550   } 588   }
551   } 589   }
552   590  
553   inline void 591   inline void
HITCBC 554   3015 timer_service::cancel_waiter(waiter_node* w) 592   2481 timer_service::cancel_waiter(waiter_node* w)
555   { 593   {
556   { 594   {
HITCBC 557   3015 std::lock_guard lock(mutex_); 595   2481 std::lock_guard lock(mutex_);
558   // Already removed by another drain: cancel_timer, 596   // Already removed by another drain: cancel_timer,
559   // process_expired, or insert_waiter's lost-cancel recheck 597   // process_expired, or insert_waiter's lost-cancel recheck
HITCBC 560   3015 if (!w->impl_) 598   2481 if (!w->impl_)
HITCBC 561   978 return; 599   510 return;
HITCBC 562   2037 auto* impl = w->impl_; 600   1971 auto* impl = w->impl_;
HITCBC 563   2037 w->impl_ = nullptr; 601   1971 w->impl_ = nullptr;
HITCBC 564   2037 impl->waiter_ = nullptr; 602   1971 impl->waiter_ = nullptr;
HITCBC 565   2037 remove_timer_impl(*impl); 603   1971 remove_timer_impl(*impl);
HITCBC 566   2037 impl->might_have_pending_waits_.store(false, std::memory_order_release); 604   1971 impl->might_have_pending_waits_.store(false, std::memory_order_release);
HITCBC 567   2037 refresh_cached_nearest(); 605   1971 refresh_cached_nearest();
HITCBC 568   2037 ++cancels_posting_; 606   1971 ++cancels_posting_;
HITCBC 569   3015 } 607   2481 }
570   608  
HITCBC 571   2037 w->ec_ = make_error_code(capy::error::canceled); 609   1971 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 572   2037 sched_->post(&w->op_); 610   1971 sched_->post(&w->op_);
573   611  
HITCBC 574   2037 std::lock_guard lock(mutex_); 612   1971 std::lock_guard lock(mutex_);
HITCBC 575   2037 --cancels_posting_; 613   1971 --cancels_posting_;
HITCBC 576   2037 } 614   1971 }
577   615  
578   inline std::size_t 616   inline std::size_t
HITCBC 579   156082 timer_service::process_expired() 617   35653 timer_service::process_expired()
580   { 618   {
HITCBC 581   156082 intrusive_list<waiter_node> expired; 619   35653 intrusive_list<waiter_node> expired;
582   620  
583   { 621   {
HITCBC 584   156082 std::lock_guard lock(mutex_); 622   35653 std::lock_guard lock(mutex_);
HITCBC 585   156082 auto now = clock_type::now(); 623   35653 auto now = clock_type::now();
586   624  
HITCBC 587   175851 while (!heap_.empty() && heap_[0].time_ <= now) 625   54208 while (!heap_.empty() && heap_[0].time_ <= now)
588   { 626   {
HITCBC 589   19769 timer::implementation* t = heap_[0].timer_; 627   18555 timer::implementation* t = heap_[0].timer_;
HITCBC 590   19769 remove_timer_impl(*t); 628   18555 remove_timer_impl(*t);
HITCBC 591   19769 if (auto* w = std::exchange(t->waiter_, nullptr)) 629   18555 if (auto* w = std::exchange(t->waiter_, nullptr))
592   { 630   {
HITCBC 593   19769 w->impl_ = nullptr; 631   18555 w->impl_ = nullptr;
HITCBC 594   19769 w->ec_ = {}; 632   18555 w->ec_ = {};
HITCBC 595   19769 expired.push_back(w); 633   18555 expired.push_back(w);
596   } 634   }
HITCBC 597   19769 t->might_have_pending_waits_.store( 635   18555 t->might_have_pending_waits_.store(
598   false, std::memory_order_release); 636   false, std::memory_order_release);
599   } 637   }
600   638  
HITCBC 601   156082 refresh_cached_nearest(); 639   35653 refresh_cached_nearest();
HITCBC 602   156082 } 640   35653 }
603   641  
HITCBC 604   156082 std::size_t count = 0; 642   35653 std::size_t count = 0;
HITCBC 605   175851 while (auto* w = expired.pop_front()) 643   54208 while (auto* w = expired.pop_front())
606   { 644   {
HITCBC 607   19769 sched_->post(&w->op_); 645   18555 sched_->post(&w->op_);
HITCBC 608   19769 ++count; 646   18555 ++count;
HITCBC 609   19769 } 647   18555 }
610   648  
HITCBC 611   156082 return count; 649   35653 return count;
612   } 650   }
613   651  
614   inline void 652   inline void
HITCBC 615   22202 timer_service::remove_timer_impl(timer::implementation& impl) 653   20783 timer_service::remove_timer_impl(timer::implementation& impl)
616   { 654   {
HITCBC 617   22202 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 655   20783 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 618   22202 if (index >= heap_.size()) 656   20783 if (index >= heap_.size())
MISUBC 619   ✗ return; // Not in heap 657   ✗ return; // Not in heap
620   658  
HITCBC 621   22202 if (index == heap_.size() - 1) 659   20783 if (index == heap_.size() - 1)
622   { 660   {
623   // Last element, just pop 661   // Last element, just pop
HITCBC 624   3349 impl.heap_index_.store( 662   3092 impl.heap_index_.store(
625   (std::numeric_limits<std::size_t>::max)(), 663   (std::numeric_limits<std::size_t>::max)(),
626   std::memory_order_relaxed); 664   std::memory_order_relaxed);
HITCBC 627   3349 heap_.pop_back(); 665   3092 heap_.pop_back();
628   } 666   }
629   else 667   else
630   { 668   {
631   // Swap with last and reheapify 669   // Swap with last and reheapify
HITCBC 632   18853 swap_heap(index, heap_.size() - 1); 670   17691 swap_heap(index, heap_.size() - 1);
HITCBC 633   18853 impl.heap_index_.store( 671   17691 impl.heap_index_.store(
634   (std::numeric_limits<std::size_t>::max)(), 672   (std::numeric_limits<std::size_t>::max)(),
635   std::memory_order_relaxed); 673   std::memory_order_relaxed);
HITCBC 636   18853 heap_.pop_back(); 674   17691 heap_.pop_back();
637   675  
HITCBC 638   18853 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 676   17691 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
HITCBC 639   3 up_heap(index); 677   1 up_heap(index);
640   else 678   else
HITCBC 641   18850 down_heap(index); 679   17690 down_heap(index);
642   } 680   }
643   } 681   }
644   682  
645   inline void 683   inline void
HITCBC 646   25433 timer_service::up_heap(std::size_t index) 684   24031 timer_service::up_heap(std::size_t index)
647   { 685   {
HITCBC 648   32869 while (index > 0) 686   30264 while (index > 0)
649   { 687   {
HITCBC 650   24492 std::size_t parent = (index - 1) / 2; 688   22343 std::size_t parent = (index - 1) / 2;
HITCBC 651   24492 if (!(heap_[index].time_ < heap_[parent].time_)) 689   22343 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 652   17056 break; 690   16110 break;
HITCBC 653   7436 swap_heap(index, parent); 691   6233 swap_heap(index, parent);
HITCBC 654   7436 index = parent; 692   6233 index = parent;
655   } 693   }
HITCBC 656   25433 } 694   24031 }
657   695  
658   inline void 696   inline void
HITCBC 659   18850 timer_service::down_heap(std::size_t index) 697   17690 timer_service::down_heap(std::size_t index)
660   { 698   {
HITCBC 661   18850 std::size_t child = index * 2 + 1; 699   17690 std::size_t child = index * 2 + 1;
HITCBC 662   44471 while (child < heap_.size()) 700   41539 while (child < heap_.size())
663   { 701   {
HITCBC 664   27824 std::size_t min_child = (child + 1 == heap_.size() || 702   26175 std::size_t min_child = (child + 1 == heap_.size() ||
HITCBC 665   24571 heap_[child].time_ < heap_[child + 1].time_) 703   21881 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 666   52395 ? child 704   48056 ? child
HITCBC 667   27824 : child + 1; 705   26175 : child + 1;
668   706  
HITCBC 669   27824 if (heap_[index].time_ < heap_[min_child].time_) 707   26175 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 670   2203 break; 708   2326 break;
671   709  
HITCBC 672   25621 swap_heap(index, min_child); 710   23849 swap_heap(index, min_child);
HITCBC 673   25621 index = min_child; 711   23849 index = min_child;
HITCBC 674   25621 child = index * 2 + 1; 712   23849 child = index * 2 + 1;
675   } 713   }
HITCBC 676   18850 } 714   17690 }
677   715  
678   inline void 716   inline void
HITCBC 679   51910 timer_service::swap_heap(std::size_t i1, std::size_t i2) 717   47773 timer_service::swap_heap(std::size_t i1, std::size_t i2)
680   { 718   {
HITCBC 681   51910 heap_entry tmp = heap_[i1]; 719   47773 heap_entry tmp = heap_[i1];
HITCBC 682   51910 heap_[i1] = heap_[i2]; 720   47773 heap_[i1] = heap_[i2];
HITCBC 683   51910 heap_[i2] = tmp; 721   47773 heap_[i2] = tmp;
HITCBC 684   51910 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 722   47773 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 685   51910 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 723   47773 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 686   51910 } 724   47773 }
687   725  
688   // waiter_node's completion_op and canceller members are defined in 726   // waiter_node's completion_op and canceller members are defined in
689   // timer.cpp alongside implementation::wait(), for the same reason 727   // timer.cpp alongside implementation::wait(), for the same reason
690   // wait() lives there (see below). 728   // wait() lives there (see below).
691   729  
692   // timer::implementation::wait() is defined in timer.cpp, not here. 730   // timer::implementation::wait() is defined in timer.cpp, not here.
693   // It must be a non-inline definition in a translation unit that is 731   // It must be a non-inline definition in a translation unit that is
694   // always pulled into the link whenever detail::timer is used (every 732   // always pulled into the link whenever detail::timer is used (every
695   // consumer needs timer's constructors from that same object file). 733   // consumer needs timer's constructors from that same object file).
696   // An inline definition in this header would only be emitted in 734   // An inline definition in this header would only be emitted in
697   // translation units that happen to also include this header, which 735   // translation units that happen to also include this header, which
698   // is not guaranteed for every caller of wait_awaitable::await_suspend 736   // is not guaranteed for every caller of wait_awaitable::await_suspend
699   // in timer.hpp (e.g. code that only reaches timer.hpp through 737   // in timer.hpp (e.g. code that only reaches timer.hpp through
700 -  
701 - // Free functions  
702 -  
703 - inline timer_service&  
704 - get_timer_service(capy::execution_context& ctx, scheduler& sched)  
DCB 705 - 4417 {  
706 - return ctx.make_service<timer_service>(sched);  
DCB 707 - 4417 }  
708   // delay.hpp, without transitively including a scheduler header). 738   // delay.hpp, without transitively including a scheduler header).
709   739  
710   } // namespace boost::corosio::detail 740   } // namespace boost::corosio::detail
711   741  
712   #endif 742   #endif