. /include/boost/corosio /detail /timer_service.hpp
76.69% Lines (227/296) 84.38% Functions (27/32)
[ ] 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/intrusive.hpp> 17   #include <boost/corosio/detail/intrusive.hpp>
18   #include <boost/corosio/detail/thread_local_ptr.hpp> 18   #include <boost/corosio/detail/thread_local_ptr.hpp>
19   #include <boost/capy/error.hpp> 19   #include <boost/capy/error.hpp>
20   #include <boost/capy/ex/execution_context.hpp> 20   #include <boost/capy/ex/execution_context.hpp>
21   #include <boost/capy/ex/executor_ref.hpp> 21   #include <boost/capy/ex/executor_ref.hpp>
22   #include <system_error> 22   #include <system_error>
23   23  
24   #include <atomic> 24   #include <atomic>
25   #include <chrono> 25   #include <chrono>
26   #include <coroutine> 26   #include <coroutine>
27   #include <cstddef> 27   #include <cstddef>
28   #include <limits> 28   #include <limits>
29   #include <mutex> 29   #include <mutex>
30   #include <stop_token> 30   #include <stop_token>
31   #include <utility> 31   #include <utility>
32   #include <vector> 32   #include <vector>
33   33  
34   namespace boost::corosio::detail { 34   namespace boost::corosio::detail {
35   35  
36   struct scheduler; 36   struct scheduler;
37   37  
38   /* 38   /*
39   Timer Service 39   Timer Service
40   ============= 40   =============
41   41  
42   Data Structures 42   Data Structures
43   --------------- 43   ---------------
44   waiter_node (defined in timer.hpp) holds per-waiter state: 44   waiter_node (defined in timer.hpp) holds per-waiter state:
45   coroutine handle, executor, error output, embedded 45   coroutine handle, executor, error output, embedded
46   completion_op. Each concurrent co_await t.wait() embeds one 46   completion_op. Each concurrent co_await t.wait() embeds one
47   waiter_node in the awaitable on the suspended coroutine's 47   waiter_node in the awaitable on the suspended coroutine's
48   frame — waits perform no allocation. 48   frame — waits perform no allocation.
49   49  
50   timer::implementation holds per-timer state: expiry, heap 50   timer::implementation holds per-timer state: expiry, heap
51   index, and an intrusive_list of waiter_nodes. Multiple 51   index, and an intrusive_list of waiter_nodes. Multiple
52   coroutines can wait on the same timer simultaneously. 52   coroutines can wait on the same timer simultaneously.
53   53  
54   timer_service owns a min-heap of active timers and a free list 54   timer_service owns a min-heap of active timers and a free list
55   of recycled impls. The heap is ordered by expiry time; the 55   of recycled impls. The heap is ordered by expiry time; the
56   scheduler queries nearest_expiry() to set the epoll/timerfd 56   scheduler queries nearest_expiry() to set the epoll/timerfd
57   timeout. 57   timeout.
58   58  
59   Optimization Strategy 59   Optimization Strategy
60   --------------------- 60   ---------------------
61   1. Deferred heap insertion — expires_after() stores the expiry 61   1. Deferred heap insertion — expires_after() stores the expiry
62   but does not insert into the heap. Insertion happens in wait(). 62   but does not insert into the heap. Insertion happens in wait().
63   2. Thread-local impl cache — single-slot per-thread cache. 63   2. Thread-local impl cache — single-slot per-thread cache.
64   3. Frame-resident waiter_node with embedded completion_op — 64   3. Frame-resident waiter_node with embedded completion_op —
65   eliminates heap allocation per wait/fire/cancel. 65   eliminates heap allocation per wait/fire/cancel.
66   4. Cached nearest expiry — atomic avoids mutex in nearest_expiry(). 66   4. Cached nearest expiry — atomic avoids mutex in nearest_expiry().
67   5. might_have_pending_waits_ flag — skips lock when no wait issued. 67   5. might_have_pending_waits_ flag — skips lock when no wait issued.
68   68  
69   Concurrency 69   Concurrency
70   ----------- 70   -----------
71   stop_token callbacks can fire from any thread. The impl_ 71   stop_token callbacks can fire from any thread. The impl_
72   pointer on waiter_node is used as a "still in list" marker. 72   pointer on waiter_node is used as a "still in list" marker.
73   A waiter_node's storage is the suspended coroutine's frame: 73   A waiter_node's storage is the suspended coroutine's frame:
74   every completion path must finish touching the node before 74   every completion path must finish touching the node before
75   posting the continuation or destroying the handle. 75   posting the continuation or destroying the handle.
76   */ 76   */
77   77  
78   inline void timer_service_invalidate_cache() noexcept; 78   inline void timer_service_invalidate_cache() noexcept;
79   79  
80   // timer_service class body — member function definitions are 80   // timer_service class body — member function definitions are
81   // out-of-class (after implementation and waiter_node are complete) 81   // out-of-class (after implementation and waiter_node are complete)
82   class BOOST_COROSIO_DECL timer_service final 82   class BOOST_COROSIO_DECL timer_service final
83   : public capy::execution_context::service 83   : public capy::execution_context::service
84   , public io_object::io_service 84   , public io_object::io_service
85   { 85   {
86   public: 86   public:
87   using clock_type = std::chrono::steady_clock; 87   using clock_type = std::chrono::steady_clock;
88   using time_point = clock_type::time_point; 88   using time_point = clock_type::time_point;
89   89  
90   /// Type-erased callback for earliest-expiry-changed notifications. 90   /// Type-erased callback for earliest-expiry-changed notifications.
91   class callback 91   class callback
92   { 92   {
93   void* ctx_ = nullptr; 93   void* ctx_ = nullptr;
94   void (*fn_)(void*) = nullptr; 94   void (*fn_)(void*) = nullptr;
95   95  
96   public: 96   public:
97   /// Construct an empty callback. 97   /// Construct an empty callback.
HITCBC 98   1370 callback() = default; 98   1227 callback() = default;
99   99  
100   /// Construct a callback with the given context and function. 100   /// Construct a callback with the given context and function.
HITCBC 101   1370 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {} 101   1227 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {}
102   102  
103   /// Return true if the callback is non-empty. 103   /// Return true if the callback is non-empty.
104   explicit operator bool() const noexcept 104   explicit operator bool() const noexcept
105   { 105   {
106   return fn_ != nullptr; 106   return fn_ != nullptr;
107   } 107   }
108   108  
109   /// Invoke the callback. 109   /// Invoke the callback.
HITCBC 110   6206 void operator()() const 110   5837 void operator()() const
111   { 111   {
HITCBC 112   6206 if (fn_) 112   5837 if (fn_)
HITCBC 113   6206 fn_(ctx_); 113   5837 fn_(ctx_);
HITCBC 114   6206 } 114   5837 }
115   }; 115   };
116   116  
117   private: 117   private:
118   struct heap_entry 118   struct heap_entry
119   { 119   {
120   time_point time_; 120   time_point time_;
121   timer::implementation* timer_; 121   timer::implementation* timer_;
122   }; 122   };
123   123  
124   scheduler* sched_ = nullptr; 124   scheduler* sched_ = nullptr;
125   BOOST_COROSIO_MSVC_WARNING_PUSH 125   BOOST_COROSIO_MSVC_WARNING_PUSH
126   BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface 126   BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface
127   mutable std::mutex mutex_; 127   mutable std::mutex mutex_;
128   std::vector<heap_entry> heap_; 128   std::vector<heap_entry> heap_;
129   timer::implementation* free_list_ = nullptr; 129   timer::implementation* free_list_ = nullptr;
130   callback on_earliest_changed_; 130   callback on_earliest_changed_;
131   bool shutting_down_ = false; 131   bool shutting_down_ = false;
132   // Avoids mutex in nearest_expiry() and empty() 132   // Avoids mutex in nearest_expiry() and empty()
133   mutable std::atomic<std::int64_t> cached_nearest_ns_{ 133   mutable std::atomic<std::int64_t> cached_nearest_ns_{
134   (std::numeric_limits<std::int64_t>::max)()}; 134   (std::numeric_limits<std::int64_t>::max)()};
135   BOOST_COROSIO_MSVC_WARNING_POP 135   BOOST_COROSIO_MSVC_WARNING_POP
136   136  
137   public: 137   public:
138   /// Construct the timer service bound to a scheduler. 138   /// Construct the timer service bound to a scheduler.
HITCBC 139   1370 inline timer_service(capy::execution_context&, scheduler& sched) 139   1227 inline timer_service(capy::execution_context&, scheduler& sched)
HITCBC 140   1370 : sched_(&sched) 140   1227 : sched_(&sched)
141   { 141   {
HITCBC 142   1370 } 142   1227 }
143   143  
144   /// Return the associated scheduler. 144   /// Return the associated scheduler.
HITCBC 145   13178 inline scheduler& get_scheduler() noexcept 145   12410 inline scheduler& get_scheduler() noexcept
146   { 146   {
HITCBC 147   13178 return *sched_; 147   12410 return *sched_;
148   } 148   }
149   149  
150   /// Destroy the timer service. 150   /// Destroy the timer service.
HITCBC 151   2740 ~timer_service() override = default; 151   2454 ~timer_service() override = default;
152   152  
153   timer_service(timer_service const&) = delete; 153   timer_service(timer_service const&) = delete;
154   timer_service& operator=(timer_service const&) = delete; 154   timer_service& operator=(timer_service const&) = delete;
155   155  
156   /// Register a callback invoked when the earliest expiry changes. 156   /// Register a callback invoked when the earliest expiry changes.
HITCBC 157   1370 inline void set_on_earliest_changed(callback cb) 157   1227 inline void set_on_earliest_changed(callback cb)
158   { 158   {
HITCBC 159   1370 on_earliest_changed_ = cb; 159   1227 on_earliest_changed_ = cb;
HITCBC 160   1370 } 160   1227 }
161   161  
162   /// Return true if no timers are in the heap. 162   /// Return true if no timers are in the heap.
163   inline bool empty() const noexcept 163   inline bool empty() const noexcept
164   { 164   {
165   return cached_nearest_ns_.load(std::memory_order_acquire) == 165   return cached_nearest_ns_.load(std::memory_order_acquire) ==
166   (std::numeric_limits<std::int64_t>::max)(); 166   (std::numeric_limits<std::int64_t>::max)();
167   } 167   }
168   168  
169   /// Return the nearest timer expiry without acquiring the mutex. 169   /// Return the nearest timer expiry without acquiring the mutex.
HITCBC 170   180601 inline time_point nearest_expiry() const noexcept 170   181022 inline time_point nearest_expiry() const noexcept
171   { 171   {
HITCBC 172   180601 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 172   181022 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 173   180601 return time_point(time_point::duration(ns)); 173   181022 return time_point(time_point::duration(ns));
174   } 174   }
175   175  
176   /// Cancel all pending timers and free cached resources. 176   /// Cancel all pending timers and free cached resources.
177   inline void shutdown() override; 177   inline void shutdown() override;
178   178  
179   /// Construct a new timer implementation. 179   /// Construct a new timer implementation.
180   inline io_object::implementation* construct() override; 180   inline io_object::implementation* construct() override;
181   181  
182   /// Destroy a timer implementation, cancelling pending waiters. 182   /// Destroy a timer implementation, cancelling pending waiters.
183   inline void destroy(io_object::implementation* p) override; 183   inline void destroy(io_object::implementation* p) override;
184   184  
185   /// Cancel and recycle a timer implementation. 185   /// Cancel and recycle a timer implementation.
186   inline void destroy_impl(timer::implementation& impl); 186   inline void destroy_impl(timer::implementation& impl);
187   187  
188   /// Update the timer expiry, cancelling existing waiters. 188   /// Update the timer expiry, cancelling existing waiters.
189   inline std::size_t update_timer( 189   inline std::size_t update_timer(
190   timer::implementation& impl, time_point new_time); 190   timer::implementation& impl, time_point new_time);
191   191  
192   /// Insert a waiter into the timer's waiter list and the heap. 192   /// Insert a waiter into the timer's waiter list and the heap.
193   inline void insert_waiter(timer::implementation& impl, waiter_node* w); 193   inline void insert_waiter(timer::implementation& impl, waiter_node* w);
194   194  
195   /// Cancel all waiters on a timer. 195   /// Cancel all waiters on a timer.
196   inline std::size_t cancel_timer(timer::implementation& impl); 196   inline std::size_t cancel_timer(timer::implementation& impl);
197   197  
198   /// Cancel one specific waiter ( stop_token callback path ). 198   /// Cancel one specific waiter ( stop_token callback path ).
199   inline void cancel_waiter(waiter_node* w); 199   inline void cancel_waiter(waiter_node* w);
200   200  
201   /// Cancel the oldest pending waiter on a timer ( FIFO ). 201   /// Cancel the oldest pending waiter on a timer ( FIFO ).
202   inline std::size_t cancel_one_waiter(timer::implementation& impl); 202   inline std::size_t cancel_one_waiter(timer::implementation& impl);
203   203  
204   /// Complete all waiters whose timers have expired. 204   /// Complete all waiters whose timers have expired.
205   inline std::size_t process_expired(); 205   inline std::size_t process_expired();
206   206  
207   private: 207   private:
HITCBC 208   208150 inline void refresh_cached_nearest() noexcept 208   209280 inline void refresh_cached_nearest() noexcept
209   { 209   {
HITCBC 210   208150 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 210   209280 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 211   204994 : heap_[0].time_.time_since_epoch().count(); 211   206083 : heap_[0].time_.time_since_epoch().count();
HITCBC 212   208150 cached_nearest_ns_.store(ns, std::memory_order_release); 212   209280 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 213   208150 } 213   209280 }
214   214  
215   inline void remove_timer_impl(timer::implementation& impl); 215   inline void remove_timer_impl(timer::implementation& impl);
216   inline void up_heap(std::size_t index); 216   inline void up_heap(std::size_t index);
217   inline void down_heap(std::size_t index); 217   inline void down_heap(std::size_t index);
218   inline void swap_heap(std::size_t i1, std::size_t i2); 218   inline void swap_heap(std::size_t i1, std::size_t i2);
219   }; 219   };
220   220  
221   // Thread-local cache avoids hot-path mutex acquisitions: 221   // Thread-local cache avoids hot-path mutex acquisitions:
222   // single-slot impl cache, validated by comparing svc_. Cleared by 222   // single-slot impl cache, validated by comparing svc_. Cleared by
223   // timer_service_invalidate_cache() during shutdown. 223   // timer_service_invalidate_cache() during shutdown.
224   224  
225   inline thread_local_ptr<timer::implementation> tl_cached_impl; 225   inline thread_local_ptr<timer::implementation> tl_cached_impl;
226   226  
227   // The POD TLS slot above never runs destructors, so a short-lived 227   // The POD TLS slot above never runs destructors, so a short-lived
228   // run() thread would leak its cached impl. Each push arms this 228   // run() thread would leak its cached impl. Each push arms this
229   // owner, whose destructor frees the slot at thread exit. A cached 229   // owner, whose destructor frees the slot at thread exit. A cached
230   // entry is a quiescent heap object (nothing in the heap or free 230   // entry is a quiescent heap object (nothing in the heap or free
231   // list) and deletion touches no service state, so it is safe after 231   // list) and deletion touches no service state, so it is safe after
232   // the owning service is gone (the stale-entry path in 232   // the owning service is gone (the stale-entry path in
233   // try_pop_tl_cache deletes the same way). 233   // try_pop_tl_cache deletes the same way).
234   struct tl_cache_owner 234   struct tl_cache_owner
235   { 235   {
HITCBC 236   42 ~tl_cache_owner() 236   43 ~tl_cache_owner()
237   { 237   {
HITCBC 238   42 delete tl_cached_impl.get(); 238   43 delete tl_cached_impl.get();
HITCBC 239   42 tl_cached_impl.set(nullptr); 239   43 tl_cached_impl.set(nullptr);
HITCBC 240   42 } 240   43 }
241   }; 241   };
242   242  
243   inline void 243   inline void
HITCBC 244   7048 arm_tl_cache_cleanup() noexcept 244   6690 arm_tl_cache_cleanup() noexcept
245   { 245   {
HITCBC 246   7048 thread_local tl_cache_owner owner; 246   6690 thread_local tl_cache_owner owner;
247   (void)owner; 247   (void)owner;
HITCBC 248   7048 } 248   6690 }
249   249  
250   inline timer::implementation* 250   inline timer::implementation*
HITCBC 251   7462 try_pop_tl_cache(timer_service* svc) noexcept 251   7071 try_pop_tl_cache(timer_service* svc) noexcept
252   { 252   {
HITCBC 253   7462 auto* impl = tl_cached_impl.get(); 253   7071 auto* impl = tl_cached_impl.get();
HITCBC 254   7462 if (impl) 254   7071 if (impl)
255   { 255   {
HITCBC 256   6816 tl_cached_impl.set(nullptr); 256   6461 tl_cached_impl.set(nullptr);
HITCBC 257   6816 if (impl->svc_ == svc) 257   6461 if (impl->svc_ == svc)
HITCBC 258   6816 return impl; 258   6461 return impl;
259   // Stale impl from a destroyed service 259   // Stale impl from a destroyed service
MISUBC 260   ✗ delete impl; 260   ✗ delete impl;
261   } 261   }
HITCBC 262   646 return nullptr; 262   610 return nullptr;
263   } 263   }
264   264  
265   inline bool 265   inline bool
HITCBC 266   7436 try_push_tl_cache(timer::implementation* impl) noexcept 266   7045 try_push_tl_cache(timer::implementation* impl) noexcept
267   { 267   {
HITCBC 268   7436 if (!tl_cached_impl.get()) 268   7045 if (!tl_cached_impl.get())
269   { 269   {
HITCBC 270   7048 arm_tl_cache_cleanup(); 270   6690 arm_tl_cache_cleanup();
HITCBC 271   7048 tl_cached_impl.set(impl); 271   6690 tl_cached_impl.set(impl);
HITCBC 272   7048 return true; 272   6690 return true;
273   } 273   }
HITCBC 274   388 return false; 274   355 return false;
275   } 275   }
276   276  
277   inline void 277   inline void
HITCBC 278   1370 timer_service_invalidate_cache() noexcept 278   1227 timer_service_invalidate_cache() noexcept
279   { 279   {
HITCBC 280   1370 delete tl_cached_impl.get(); 280   1227 delete tl_cached_impl.get();
HITCBC 281   1370 tl_cached_impl.set(nullptr); 281   1227 tl_cached_impl.set(nullptr);
HITCBC 282   1370 } 282   1227 }
283   283  
284   // timer_service out-of-class member function definitions 284   // timer_service out-of-class member function definitions
285   285  
286   inline void 286   inline void
HITCBC 287   1370 timer_service::shutdown() 287   1227 timer_service::shutdown()
288   { 288   {
HITCBC 289   1370 timer_service_invalidate_cache(); 289   1227 timer_service_invalidate_cache();
HITCBC 290   1370 shutting_down_ = true; 290   1227 shutting_down_ = true;
291   291  
292   // Snapshot impls and detach them from the heap so that 292   // Snapshot impls and detach them from the heap so that
293   // coroutine-owned timer destructors (triggered by h.destroy() 293   // coroutine-owned timer destructors (triggered by h.destroy()
294   // below) cannot re-enter remove_timer_impl() and mutate the 294   // below) cannot re-enter remove_timer_impl() and mutate the
295   // vector during iteration. 295   // vector during iteration.
HITCBC 296   1370 std::vector<timer::implementation*> impls; 296   1227 std::vector<timer::implementation*> impls;
HITCBC 297   1370 impls.reserve(heap_.size()); 297   1227 impls.reserve(heap_.size());
HITCBC 298   1396 for (auto& entry : heap_) 298   1253 for (auto& entry : heap_)
299   { 299   {
HITCBC 300   26 entry.timer_->heap_index_.store( 300   26 entry.timer_->heap_index_.store(
301   (std::numeric_limits<std::size_t>::max)(), 301   (std::numeric_limits<std::size_t>::max)(),
302   std::memory_order_relaxed); 302   std::memory_order_relaxed);
HITCBC 303   26 impls.push_back(entry.timer_); 303   26 impls.push_back(entry.timer_);
304   } 304   }
HITCBC 305   1370 heap_.clear(); 305   1227 heap_.clear();
HITCBC 306   1370 cached_nearest_ns_.store( 306   1227 cached_nearest_ns_.store(
307   (std::numeric_limits<std::int64_t>::max)(), std::memory_order_release); 307   (std::numeric_limits<std::int64_t>::max)(), std::memory_order_release);
308   308  
309   // Cancel waiting timers. Each waiter called work_started() 309   // Cancel waiting timers. Each waiter called work_started()
310   // in implementation::wait(). On IOCP the scheduler shutdown 310   // in implementation::wait(). On IOCP the scheduler shutdown
311   // loop exits when outstanding_work_ reaches zero, so we must 311   // loop exits when outstanding_work_ reaches zero, so we must
312   // call work_finished() here to balance it. On other backends 312   // call work_finished() here to balance it. On other backends
313   // this is harmless. 313   // this is harmless.
HITCBC 314   1396 for (auto* impl : impls) 314   1253 for (auto* impl : impls)
315   { 315   {
HITCBC 316   52 while (auto* w = impl->waiters_.pop_front()) 316   52 while (auto* w = impl->waiters_.pop_front())
317   { 317   {
HITCBC 318   26 w->reset_stop_cb(); 318   26 w->reset_stop_cb();
HITCBC 319   26 auto h = std::exchange(w->h_, {}); 319   26 auto h = std::exchange(w->h_, {});
HITCBC 320   26 sched_->work_finished(); 320   26 sched_->work_finished();
321   // Destroying the frame also ends the node's storage 321   // Destroying the frame also ends the node's storage
HITCBC 322   26 if (h) 322   26 if (h)
HITCBC 323   26 h.destroy(); 323   26 h.destroy();
HITCBC 324   26 } 324   26 }
HITCBC 325   26 delete impl; 325   26 delete impl;
326   } 326   }
327   327  
328   // Delete free-listed impls 328   // Delete free-listed impls
HITCBC 329   1758 while (free_list_) 329   1582 while (free_list_)
330   { 330   {
HITCBC 331   388 auto* next = free_list_->next_free_; 331   355 auto* next = free_list_->next_free_;
HITCBC 332   388 delete free_list_; 332   355 delete free_list_;
HITCBC 333   388 free_list_ = next; 333   355 free_list_ = next;
334   } 334   }
HITCBC 335   1370 } 335   1227 }
336   336  
337   inline io_object::implementation* 337   inline io_object::implementation*
HITCBC 338   7462 timer_service::construct() 338   7071 timer_service::construct()
339   { 339   {
HITCBC 340   7462 timer::implementation* impl = try_pop_tl_cache(this); 340   7071 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 341   7462 if (impl) 341   7071 if (impl)
342   { 342   {
HITCBC 343   6816 impl->svc_ = this; 343   6461 impl->svc_ = this;
344   // Reset expiry_ too: a recycled impl must behave like a fresh 344   // Reset expiry_ too: a recycled impl must behave like a fresh
345   // one, whose default expiry reads as already elapsed 345   // one, whose default expiry reads as already elapsed
HITCBC 346   6816 impl->expiry_ = {}; 346   6461 impl->expiry_ = {};
HITCBC 347   6816 impl->heap_index_.store( 347   6461 impl->heap_index_.store(
348   (std::numeric_limits<std::size_t>::max)(), 348   (std::numeric_limits<std::size_t>::max)(),
349   std::memory_order_relaxed); 349   std::memory_order_relaxed);
HITCBC 350   6816 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 350   6461 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
HITCBC 351   6816 return impl; 351   6461 return impl;
352   } 352   }
353   353  
HITCBC 354   646 std::lock_guard lock(mutex_); 354   610 std::lock_guard lock(mutex_);
HITCBC 355   646 if (free_list_) 355   610 if (free_list_)
356   { 356   {
MISUBC 357   ✗ impl = free_list_; 357   ✗ impl = free_list_;
MISUBC 358   ✗ free_list_ = impl->next_free_; 358   ✗ free_list_ = impl->next_free_;
MISUBC 359   ✗ impl->next_free_ = nullptr; 359   ✗ impl->next_free_ = nullptr;
MISUBC 360   ✗ impl->svc_ = this; 360   ✗ impl->svc_ = this;
MISUBC 361   ✗ impl->expiry_ = {}; 361   ✗ impl->expiry_ = {};
MISUBC 362   ✗ impl->heap_index_.store( 362   ✗ impl->heap_index_.store(
363   (std::numeric_limits<std::size_t>::max)(), 363   (std::numeric_limits<std::size_t>::max)(),
364   std::memory_order_relaxed); 364   std::memory_order_relaxed);
MISUBC 365   ✗ impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 365   ✗ impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
366   } 366   }
367   else 367   else
368   { 368   {
HITCBC 369   646 impl = new timer::implementation(*this); 369   610 impl = new timer::implementation(*this);
370   } 370   }
HITCBC 371   646 return impl; 371   610 return impl;
HITCBC 372   646 } 372   610 }
373   373  
374   inline void 374   inline void
HITCBC 375   7462 timer_service::destroy(io_object::implementation* p) 375   7071 timer_service::destroy(io_object::implementation* p)
376   { 376   {
377   // During shutdown the drain loop owns every impl and deletes 377   // During shutdown the drain loop owns every impl and deletes
378   // them directly. A frame destroyed by that loop can unwind a 378   // them directly. A frame destroyed by that loop can unwind a
379   // handle whose impl was freed in an earlier iteration (a 379   // handle whose impl was freed in an earlier iteration (a
380   // timeout's parent frame owns the timeout timer while 380   // timeout's parent frame owns the timeout timer while
381   // suspended on the inner delay's timer), so bail out before 381   // suspended on the inner delay's timer), so bail out before
382   // even downcasting the pointer. 382   // even downcasting the pointer.
HITCBC 383   7462 if (shutting_down_) 383   7071 if (shutting_down_)
HITCBC 384   26 return; 384   26 return;
HITCBC 385   7436 destroy_impl(static_cast<timer::implementation&>(*p)); 385   7045 destroy_impl(static_cast<timer::implementation&>(*p));
386   } 386   }
387   387  
388   inline void 388   inline void
HITCBC 389   7436 timer_service::destroy_impl(timer::implementation& impl) 389   7045 timer_service::destroy_impl(timer::implementation& impl)
390   { 390   {
391   // During shutdown the impl is owned by the shutdown loop. 391   // During shutdown the impl is owned by the shutdown loop.
392   // Re-entering here (from a coroutine-owned timer destructor 392   // Re-entering here (from a coroutine-owned timer destructor
393   // triggered by h.destroy()) must not modify the heap or 393   // triggered by h.destroy()) must not modify the heap or
394   // recycle the impl — shutdown deletes it directly. 394   // recycle the impl — shutdown deletes it directly.
HITCBC 395   7436 if (shutting_down_) 395   7045 if (shutting_down_)
HITCBC 396   7048 return; 396   6690 return;
397   397  
HITCBC 398   7436 cancel_timer(impl); 398   7045 cancel_timer(impl);
399   399  
HITCBC 400   14872 if (impl.heap_index_.load(std::memory_order_relaxed) != 400   14090 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 401   7436 (std::numeric_limits<std::size_t>::max)()) 401   7045 (std::numeric_limits<std::size_t>::max)())
402   { 402   {
MISUBC 403   ✗ std::lock_guard lock(mutex_); 403   ✗ std::lock_guard lock(mutex_);
MISUBC 404   ✗ remove_timer_impl(impl); 404   ✗ remove_timer_impl(impl);
MISUBC 405   ✗ refresh_cached_nearest(); 405   ✗ refresh_cached_nearest();
MISUBC 406   ✗ } 406   ✗ }
407   407  
HITCBC 408   7436 if (try_push_tl_cache(&impl)) 408   7045 if (try_push_tl_cache(&impl))
HITCBC 409   7048 return; 409   6690 return;
410   410  
HITCBC 411   388 std::lock_guard lock(mutex_); 411   355 std::lock_guard lock(mutex_);
HITCBC 412   388 impl.next_free_ = free_list_; 412   355 impl.next_free_ = free_list_;
HITCBC 413   388 free_list_ = &impl; 413   355 free_list_ = &impl;
HITCBC 414   388 } 414   355 }
415   415  
416   inline std::size_t 416   inline std::size_t
MISUBC 417   ✗ timer_service::update_timer(timer::implementation& impl, time_point new_time) 417   ✗ timer_service::update_timer(timer::implementation& impl, time_point new_time)
418   { 418   {
419   // Gate on the flag, not waiters_: reading the non-atomic list 419   // Gate on the flag, not waiters_: reading the non-atomic list
420   // here would race a concurrent drain. A false flag is safe to 420   // here would race a concurrent drain. A false flag is safe to
421   // trust pre-lock: wait() stores it true before publishing, and 421   // trust pre-lock: wait() stores it true before publishing, and
422   // it is cleared only under the mutex when the waiter list is 422   // it is cleared only under the mutex when the waiter list is
423   // empty, so false implies no published waiters. 423   // empty, so false implies no published waiters.
424   bool in_heap = 424   bool in_heap =
MISUBC 425   ✗ (impl.heap_index_.load(std::memory_order_relaxed) != 425   ✗ (impl.heap_index_.load(std::memory_order_relaxed) !=
MISUBC 426   ✗ (std::numeric_limits<std::size_t>::max)()); 426   ✗ (std::numeric_limits<std::size_t>::max)());
MISUBC 427   ✗ if (!in_heap && 427   ✗ if (!in_heap &&
MISUBC 428   ✗ !impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 428   ✗ !impl.might_have_pending_waits_.load(std::memory_order_relaxed))
MISUBC 429   ✗ return 0; 429   ✗ return 0;
430   430  
MISUBC 431   ✗ bool notify = false; 431   ✗ bool notify = false;
MISUBC 432   ✗ intrusive_list<waiter_node> canceled; 432   ✗ intrusive_list<waiter_node> canceled;
433   433  
434   { 434   {
MISUBC 435   ✗ std::lock_guard lock(mutex_); 435   ✗ std::lock_guard lock(mutex_);
436   436  
MISUBC 437   ✗ while (auto* w = impl.waiters_.pop_front()) 437   ✗ while (auto* w = impl.waiters_.pop_front())
438   { 438   {
MISUBC 439   ✗ w->impl_ = nullptr; 439   ✗ w->impl_ = nullptr;
MISUBC 440   ✗ canceled.push_back(w); 440   ✗ canceled.push_back(w);
MISUBC 441   ✗ } 441   ✗ }
442   442  
MISUBC 443   ✗ std::size_t idx = impl.heap_index_.load(std::memory_order_relaxed); 443   ✗ std::size_t idx = impl.heap_index_.load(std::memory_order_relaxed);
MISUBC 444   ✗ if (idx < heap_.size()) 444   ✗ if (idx < heap_.size())
445   { 445   {
MISUBC 446   ✗ time_point old_time = heap_[idx].time_; 446   ✗ time_point old_time = heap_[idx].time_;
MISUBC 447   ✗ heap_[idx].time_ = new_time; 447   ✗ heap_[idx].time_ = new_time;
448   448  
MISUBC 449   ✗ if (new_time < old_time) 449   ✗ if (new_time < old_time)
MISUBC 450   ✗ up_heap(idx); 450   ✗ up_heap(idx);
451   else 451   else
MISUBC 452   ✗ down_heap(idx); 452   ✗ down_heap(idx);
453   453  
MISUBC 454   ✗ notify = 454   ✗ notify =
MISUBC 455   ✗ (impl.heap_index_.load(std::memory_order_relaxed) == 0); 455   ✗ (impl.heap_index_.load(std::memory_order_relaxed) == 0);
456   } 456   }
457   457  
MISUBC 458   ✗ refresh_cached_nearest(); 458   ✗ refresh_cached_nearest();
MISUBC 459   ✗ } 459   ✗ }
460   460  
MISUBC 461   ✗ std::size_t count = 0; 461   ✗ std::size_t count = 0;
MISUBC 462   ✗ while (auto* w = canceled.pop_front()) 462   ✗ while (auto* w = canceled.pop_front())
463   { 463   {
MISUBC 464   ✗ w->ec_ = make_error_code(capy::error::canceled); 464   ✗ w->ec_ = make_error_code(capy::error::canceled);
MISUBC 465   ✗ sched_->post(&w->op_); 465   ✗ sched_->post(&w->op_);
MISUBC 466   ✗ ++count; 466   ✗ ++count;
MISUBC 467   ✗ } 467   ✗ }
468   468  
MISUBC 469   ✗ if (notify) 469   ✗ if (notify)
MISUBC 470   ✗ on_earliest_changed_(); 470   ✗ on_earliest_changed_();
471   471  
MISUBC 472   ✗ return count; 472   ✗ return count;
473   } 473   }
474   474  
475   inline void 475   inline void
HITCBC 476   6602 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 476   6218 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
477   { 477   {
HITCBC 478   6602 bool notify = false; 478   6218 bool notify = false;
HITCBC 479   6602 bool lost_cancel = false; 479   6218 bool lost_cancel = false;
480   { 480   {
HITCBC 481   6602 std::lock_guard lock(mutex_); 481   6218 std::lock_guard lock(mutex_);
482   // Publish: from here the waiter is visible to the fire path and 482   // Publish: from here the waiter is visible to the fire path and
483   // to its own stop callback (impl_ non-null enables cancel_waiter). 483   // to its own stop callback (impl_ non-null enables cancel_waiter).
HITCBC 484   6602 w->impl_ = &impl; 484   6218 w->impl_ = &impl;
HITCBC 485   13204 if (impl.heap_index_.load(std::memory_order_relaxed) == 485   12436 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 486   6602 (std::numeric_limits<std::size_t>::max)()) 486   6218 (std::numeric_limits<std::size_t>::max)())
487   { 487   {
HITCBC 488   6602 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 488   6218 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 489   6602 heap_.push_back({impl.expiry_, &impl}); 489   6218 heap_.push_back({impl.expiry_, &impl});
HITCBC 490   6602 up_heap(heap_.size() - 1); 490   6218 up_heap(heap_.size() - 1);
HITCBC 491   6602 notify = 491   6218 notify =
HITCBC 492   6602 (impl.heap_index_.load(std::memory_order_relaxed) == 0); 492   6218 (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 493   6602 refresh_cached_nearest(); 493   6218 refresh_cached_nearest();
494   } 494   }
HITCBC 495   6602 impl.waiters_.push_back(w); 495   6218 impl.waiters_.push_back(w);
496   496  
497   // Lost-cancel re-check: a stop requested after the canceller was 497   // Lost-cancel re-check: a stop requested after the canceller was
498   // armed in wait() but before this publication found impl_ null 498   // armed in wait() but before this publication found impl_ null
499   // and returned a no-op. Observe it now and undo the insertion. 499   // and returned a no-op. Observe it now and undo the insertion.
HITCBC 500   6602 if (w->token_->stop_requested()) 500   6218 if (w->token_->stop_requested())
501   { 501   {
HITCBC 502   5 w->impl_ = nullptr; 502   6 w->impl_ = nullptr;
HITCBC 503   5 impl.waiters_.remove(w); 503   6 impl.waiters_.remove(w);
HITCBC 504   5 if (impl.waiters_.empty()) 504   6 if (impl.waiters_.empty())
505   { 505   {
HITCBC 506   5 remove_timer_impl(impl); 506   6 remove_timer_impl(impl);
HITCBC 507   5 impl.might_have_pending_waits_.store( 507   6 impl.might_have_pending_waits_.store(
508   false, std::memory_order_relaxed); 508   false, std::memory_order_relaxed);
509   } 509   }
HITCBC 510   5 refresh_cached_nearest(); 510   6 refresh_cached_nearest();
HITCBC 511   5 lost_cancel = true; 511   6 lost_cancel = true;
HITCBC 512   5 notify = false; // insertion undone; nearest unchanged 512   6 notify = false; // insertion undone; nearest unchanged
513   } 513   }
HITCBC 514   6602 } 514   6218 }
HITCBC 515   6602 if (notify) 515   6218 if (notify)
HITCBC 516   6206 on_earliest_changed_(); 516   5837 on_earliest_changed_();
HITCBC 517   6602 if (lost_cancel) 517   6218 if (lost_cancel)
518   { 518   {
HITCBC 519   5 w->ec_ = make_error_code(capy::error::canceled); 519   6 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 520   5 sched_->post(&w->op_); 520   6 sched_->post(&w->op_);
521   } 521   }
HITCBC 522   6602 } 522   6218 }
523   523  
524   inline std::size_t 524   inline std::size_t
HITCBC 525   7436 timer_service::cancel_timer(timer::implementation& impl) 525   7045 timer_service::cancel_timer(timer::implementation& impl)
526   { 526   {
HITCBC 527   7436 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 527   7045 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
HITCBC 528   7434 return 0; 528   7043 return 0;
529   529  
530   // No unlocked already-done fast-out here: it would need the 530   // No unlocked already-done fast-out here: it would need the
531   // non-atomic waiters_ (a race with concurrent drains), and an 531   // non-atomic waiters_ (a race with concurrent drains), and an
532   // index-only check is lifetime-unsafe because npos is stored 532   // index-only check is lifetime-unsafe because npos is stored
533   // before the drain finishes touching the impl. A stale-true 533   // before the drain finishes touching the impl. A stale-true
534   // flag is rare with the stateless API; the locked path below 534   // flag is rare with the stateless API; the locked path below
535   // re-validates. 535   // re-validates.
536   536  
HITCBC 537   2 intrusive_list<waiter_node> canceled; 537   2 intrusive_list<waiter_node> canceled;
538   538  
539   { 539   {
HITCBC 540   2 std::lock_guard lock(mutex_); 540   2 std::lock_guard lock(mutex_);
HITCBC 541   2 remove_timer_impl(impl); 541   2 remove_timer_impl(impl);
HITCBC 542   4 while (auto* w = impl.waiters_.pop_front()) 542   4 while (auto* w = impl.waiters_.pop_front())
543   { 543   {
HITCBC 544   2 w->impl_ = nullptr; 544   2 w->impl_ = nullptr;
HITCBC 545   2 canceled.push_back(w); 545   2 canceled.push_back(w);
HITCBC 546   2 } 546   2 }
547   // Store false as the final touch of the impl under the lock so 547   // Store false as the final touch of the impl under the lock so
548   // update_timer's pre-lock false-flag trust holds unqualified. 548   // update_timer's pre-lock false-flag trust holds unqualified.
HITCBC 549   2 impl.might_have_pending_waits_.store(false, std::memory_order_relaxed); 549   2 impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
HITCBC 550   2 refresh_cached_nearest(); 550   2 refresh_cached_nearest();
HITCBC 551   2 } 551   2 }
552   552  
HITCBC 553   2 std::size_t count = 0; 553   2 std::size_t count = 0;
HITCBC 554   4 while (auto* w = canceled.pop_front()) 554   4 while (auto* w = canceled.pop_front())
555   { 555   {
HITCBC 556   2 w->ec_ = make_error_code(capy::error::canceled); 556   2 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 557   2 sched_->post(&w->op_); 557   2 sched_->post(&w->op_);
HITCBC 558   2 ++count; 558   2 ++count;
HITCBC 559   2 } 559   2 }
560   560  
HITCBC 561   2 return count; 561   2 return count;
562   } 562   }
563   563  
564   inline void 564   inline void
HITCBC 565   1601 timer_service::cancel_waiter(waiter_node* w) 565   1683 timer_service::cancel_waiter(waiter_node* w)
566   { 566   {
567   { 567   {
HITCBC 568   1601 std::lock_guard lock(mutex_); 568   1683 std::lock_guard lock(mutex_);
569   // Already removed by another drain: cancel_timer, 569   // Already removed by another drain: cancel_timer,
570   // cancel_one_waiter, update_timer, process_expired, or 570   // cancel_one_waiter, update_timer, process_expired, or
571   // insert_waiter's lost-cancel recheck 571   // insert_waiter's lost-cancel recheck
HITCBC 572   1601 if (!w->impl_) 572   1683 if (!w->impl_)
HITCBC 573   5 return; 573   49 return;
HITCBC 574   1596 auto* impl = w->impl_; 574   1634 auto* impl = w->impl_;
HITCBC 575   1596 w->impl_ = nullptr; 575   1634 w->impl_ = nullptr;
HITCBC 576   1596 impl->waiters_.remove(w); 576   1634 impl->waiters_.remove(w);
HITCBC 577   1596 if (impl->waiters_.empty()) 577   1634 if (impl->waiters_.empty())
578   { 578   {
HITCBC 579   1596 remove_timer_impl(*impl); 579   1634 remove_timer_impl(*impl);
HITCBC 580   1596 impl->might_have_pending_waits_.store( 580   1634 impl->might_have_pending_waits_.store(
581   false, std::memory_order_relaxed); 581   false, std::memory_order_relaxed);
582   } 582   }
HITCBC 583   1596 refresh_cached_nearest(); 583   1634 refresh_cached_nearest();
HITCBC 584   1601 } 584   1683 }
585   585  
HITCBC 586   1596 w->ec_ = make_error_code(capy::error::canceled); 586   1634 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 587   1596 sched_->post(&w->op_); 587   1634 sched_->post(&w->op_);
588   } 588   }
589   589  
590   inline std::size_t 590   inline std::size_t
MISUBC 591   ✗ timer_service::cancel_one_waiter(timer::implementation& impl) 591   ✗ timer_service::cancel_one_waiter(timer::implementation& impl)
592   { 592   {
MISUBC 593   ✗ if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 593   ✗ if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
MISUBC 594   ✗ return 0; 594   ✗ return 0;
595   595  
MISUBC 596   ✗ waiter_node* w = nullptr; 596   ✗ waiter_node* w = nullptr;
597   597  
598   { 598   {
MISUBC 599   ✗ std::lock_guard lock(mutex_); 599   ✗ std::lock_guard lock(mutex_);
MISUBC 600   ✗ w = impl.waiters_.pop_front(); 600   ✗ w = impl.waiters_.pop_front();
MISUBC 601   ✗ if (!w) 601   ✗ if (!w)
MISUBC 602   ✗ return 0; 602   ✗ return 0;
MISUBC 603   ✗ w->impl_ = nullptr; 603   ✗ w->impl_ = nullptr;
MISUBC 604   ✗ if (impl.waiters_.empty()) 604   ✗ if (impl.waiters_.empty())
605   { 605   {
MISUBC 606   ✗ remove_timer_impl(impl); 606   ✗ remove_timer_impl(impl);
MISUBC 607   ✗ impl.might_have_pending_waits_.store( 607   ✗ impl.might_have_pending_waits_.store(
608   false, std::memory_order_relaxed); 608   false, std::memory_order_relaxed);
609   } 609   }
MISUBC 610   ✗ refresh_cached_nearest(); 610   ✗ refresh_cached_nearest();
MISUBC 611   ✗ } 611   ✗ }
612   612  
MISUBC 613   ✗ w->ec_ = make_error_code(capy::error::canceled); 613   ✗ w->ec_ = make_error_code(capy::error::canceled);
MISUBC 614   ✗ sched_->post(&w->op_); 614   ✗ sched_->post(&w->op_);
MISUBC 615   ✗ return 1; 615   ✗ return 1;
616   } 616   }
617   617  
618   inline std::size_t 618   inline std::size_t
HITCBC 619   199945 timer_service::process_expired() 619   201420 timer_service::process_expired()
620   { 620   {
HITCBC 621   199945 intrusive_list<waiter_node> expired; 621   201420 intrusive_list<waiter_node> expired;
622   622  
623   { 623   {
HITCBC 624   199945 std::lock_guard lock(mutex_); 624   201420 std::lock_guard lock(mutex_);
HITCBC 625   199945 auto now = clock_type::now(); 625   201420 auto now = clock_type::now();
626   626  
HITCBC 627   204918 while (!heap_.empty() && heap_[0].time_ <= now) 627   205970 while (!heap_.empty() && heap_[0].time_ <= now)
628   { 628   {
HITCBC 629   4973 timer::implementation* t = heap_[0].timer_; 629   4550 timer::implementation* t = heap_[0].timer_;
HITCBC 630   4973 remove_timer_impl(*t); 630   4550 remove_timer_impl(*t);
HITCBC 631   9946 while (auto* w = t->waiters_.pop_front()) 631   9100 while (auto* w = t->waiters_.pop_front())
632   { 632   {
HITCBC 633   4973 w->impl_ = nullptr; 633   4550 w->impl_ = nullptr;
HITCBC 634   4973 w->ec_ = {}; 634   4550 w->ec_ = {};
HITCBC 635   4973 expired.push_back(w); 635   4550 expired.push_back(w);
HITCBC 636   4973 } 636   4550 }
HITCBC 637   4973 t->might_have_pending_waits_.store( 637   4550 t->might_have_pending_waits_.store(
638   false, std::memory_order_relaxed); 638   false, std::memory_order_relaxed);
639   } 639   }
640   640  
HITCBC 641   199945 refresh_cached_nearest(); 641   201420 refresh_cached_nearest();
HITCBC 642   199945 } 642   201420 }
643   643  
HITCBC 644   199945 std::size_t count = 0; 644   201420 std::size_t count = 0;
HITCBC 645   204918 while (auto* w = expired.pop_front()) 645   205970 while (auto* w = expired.pop_front())
646   { 646   {
HITCBC 647   4973 sched_->post(&w->op_); 647   4550 sched_->post(&w->op_);
HITCBC 648   4973 ++count; 648   4550 ++count;
HITCBC 649   4973 } 649   4550 }
650   650  
HITCBC 651   199945 return count; 651   201420 return count;
652   } 652   }
653   653  
654   inline void 654   inline void
HITCBC 655   6576 timer_service::remove_timer_impl(timer::implementation& impl) 655   6192 timer_service::remove_timer_impl(timer::implementation& impl)
656   { 656   {
HITCBC 657   6576 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 657   6192 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 658   6576 if (index >= heap_.size()) 658   6192 if (index >= heap_.size())
MISUBC 659   ✗ return; // Not in heap 659   ✗ return; // Not in heap
660   660  
HITCBC 661   6576 if (index == heap_.size() - 1) 661   6192 if (index == heap_.size() - 1)
662   { 662   {
663   // Last element, just pop 663   // Last element, just pop
HITCBC 664   1573 impl.heap_index_.store( 664   1617 impl.heap_index_.store(
665   (std::numeric_limits<std::size_t>::max)(), 665   (std::numeric_limits<std::size_t>::max)(),
666   std::memory_order_relaxed); 666   std::memory_order_relaxed);
HITCBC 667   1573 heap_.pop_back(); 667   1617 heap_.pop_back();
668   } 668   }
669   else 669   else
670   { 670   {
671   // Swap with last and reheapify 671   // Swap with last and reheapify
HITCBC 672   5003 swap_heap(index, heap_.size() - 1); 672   4575 swap_heap(index, heap_.size() - 1);
HITCBC 673   5003 impl.heap_index_.store( 673   4575 impl.heap_index_.store(
674   (std::numeric_limits<std::size_t>::max)(), 674   (std::numeric_limits<std::size_t>::max)(),
675   std::memory_order_relaxed); 675   std::memory_order_relaxed);
HITCBC 676   5003 heap_.pop_back(); 676   4575 heap_.pop_back();
677   677  
HITCBC 678   5003 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 678   4575 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
HITCBC 679   3 up_heap(index); 679   1 up_heap(index);
680   else 680   else
HITCBC 681   5000 down_heap(index); 681   4574 down_heap(index);
682   } 682   }
683   } 683   }
684   684  
685   inline void 685   inline void
HITCBC 686   6605 timer_service::up_heap(std::size_t index) 686   6219 timer_service::up_heap(std::size_t index)
687   { 687   {
HITCBC 688   11408 while (index > 0) 688   10567 while (index > 0)
689   { 689   {
HITCBC 690   5197 std::size_t parent = (index - 1) / 2; 690   4724 std::size_t parent = (index - 1) / 2;
HITCBC 691   5197 if (!(heap_[index].time_ < heap_[parent].time_)) 691   4724 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 692   394 break; 692   376 break;
HITCBC 693   4803 swap_heap(index, parent); 693   4348 swap_heap(index, parent);
HITCBC 694   4803 index = parent; 694   4348 index = parent;
695   } 695   }
HITCBC 696   6605 } 696   6219 }
697   697  
698   inline void 698   inline void
HITCBC 699   5000 timer_service::down_heap(std::size_t index) 699   4574 timer_service::down_heap(std::size_t index)
700   { 700   {
HITCBC 701   5000 std::size_t child = index * 2 + 1; 701   4574 std::size_t child = index * 2 + 1;
HITCBC 702   5663 while (child < heap_.size()) 702   5273 while (child < heap_.size())
703   { 703   {
HITCBC 704   721 std::size_t min_child = (child + 1 == heap_.size() || 704   742 std::size_t min_child = (child + 1 == heap_.size() ||
HITCBC 705   677 heap_[child].time_ < heap_[child + 1].time_) 705   712 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 706   1398 ? child 706   1454 ? child
HITCBC 707   721 : child + 1; 707   742 : child + 1;
708   708  
HITCBC 709   721 if (heap_[index].time_ < heap_[min_child].time_) 709   742 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 710   58 break; 710   43 break;
711   711  
HITCBC 712   663 swap_heap(index, min_child); 712   699 swap_heap(index, min_child);
HITCBC 713   663 index = min_child; 713   699 index = min_child;
HITCBC 714   663 child = index * 2 + 1; 714   699 child = index * 2 + 1;
715   } 715   }
HITCBC 716   5000 } 716   4574 }
717   717  
718   inline void 718   inline void
HITCBC 719   10469 timer_service::swap_heap(std::size_t i1, std::size_t i2) 719   9622 timer_service::swap_heap(std::size_t i1, std::size_t i2)
720   { 720   {
HITCBC 721   10469 heap_entry tmp = heap_[i1]; 721   9622 heap_entry tmp = heap_[i1];
HITCBC 722   10469 heap_[i1] = heap_[i2]; 722   9622 heap_[i1] = heap_[i2];
HITCBC 723   10469 heap_[i2] = tmp; 723   9622 heap_[i2] = tmp;
HITCBC 724   10469 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 724   9622 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 725   10469 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 725   9622 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 726   10469 } 726   9622 }
727   727  
728   // waiter_node's completion_op and canceller members are defined in 728   // waiter_node's completion_op and canceller members are defined in
729   // timer.cpp alongside implementation::wait(), for the same reason 729   // timer.cpp alongside implementation::wait(), for the same reason
730   // wait() lives there (see below). 730   // wait() lives there (see below).
731   731  
732   // timer::implementation::wait() is defined in timer.cpp, not here. 732   // timer::implementation::wait() is defined in timer.cpp, not here.
733   // It must be a non-inline definition in a translation unit that is 733   // It must be a non-inline definition in a translation unit that is
734   // always pulled into the link whenever detail::timer is used (every 734   // always pulled into the link whenever detail::timer is used (every
735   // consumer needs timer's constructors from that same object file). 735   // consumer needs timer's constructors from that same object file).
736   // An inline definition in this header would only be emitted in 736   // An inline definition in this header would only be emitted in
737   // translation units that happen to also include this header, which 737   // translation units that happen to also include this header, which
738   // is not guaranteed for every caller of wait_awaitable::await_suspend 738   // is not guaranteed for every caller of wait_awaitable::await_suspend
739   // in timer.hpp (e.g. code that only reaches timer.hpp through 739   // in timer.hpp (e.g. code that only reaches timer.hpp through
740   // delay.hpp, without transitively including a scheduler header). 740   // delay.hpp, without transitively including a scheduler header).
741   741  
742   // Free functions 742   // Free functions
743   743  
744   inline std::size_t 744   inline std::size_t
MISUBC 745   ✗ timer_service_update_expiry(timer::implementation& impl) 745   ✗ timer_service_update_expiry(timer::implementation& impl)
746   { 746   {
MISUBC 747   ✗ return impl.svc_->update_timer(impl, impl.expiry_); 747   ✗ return impl.svc_->update_timer(impl, impl.expiry_);
748   } 748   }
749   749  
750   inline std::size_t 750   inline std::size_t
MISUBC 751   ✗ timer_service_cancel(timer::implementation& impl) noexcept 751   ✗ timer_service_cancel(timer::implementation& impl) noexcept
752   { 752   {
MISUBC 753   ✗ return impl.svc_->cancel_timer(impl); 753   ✗ return impl.svc_->cancel_timer(impl);
754   } 754   }
755   755  
756   inline std::size_t 756   inline std::size_t
MISUBC 757   ✗ timer_service_cancel_one(timer::implementation& impl) noexcept 757   ✗ timer_service_cancel_one(timer::implementation& impl) noexcept
758   { 758   {
MISUBC 759   ✗ return impl.svc_->cancel_one_waiter(impl); 759   ✗ return impl.svc_->cancel_one_waiter(impl);
760   } 760   }
761   761  
762   inline timer_service& 762   inline timer_service&
HITCBC 763   1370 get_timer_service(capy::execution_context& ctx, scheduler& sched) 763   1227 get_timer_service(capy::execution_context& ctx, scheduler& sched)
764   { 764   {
HITCBC 765   1370 return ctx.make_service<timer_service>(sched); 765   1227 return ctx.make_service<timer_service>(sched);
766   } 766   }
767   767  
768   } // namespace boost::corosio::detail 768   } // namespace boost::corosio::detail
769   769  
770   #endif 770   #endif