. /include/boost/corosio /detail /timer_service.hpp
76.35% Lines (226/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   1382 callback() = default; 98   1382 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   1382 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {} 101   1382 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   5951 void operator()() const 110   5784 void operator()() const
111   { 111   {
HITCBC 112   5951 if (fn_) 112   5784 if (fn_)
HITCBC 113   5951 fn_(ctx_); 113   5784 fn_(ctx_);
HITCBC 114   5951 } 114   5784 }
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   1382 inline timer_service(capy::execution_context&, scheduler& sched) 139   1382 inline timer_service(capy::execution_context&, scheduler& sched)
HITCBC 140   1382 : sched_(&sched) 140   1382 : sched_(&sched)
141   { 141   {
HITCBC 142   1382 } 142   1382 }
143   143  
144   /// Return the associated scheduler. 144   /// Return the associated scheduler.
HITCBC 145   13506 inline scheduler& get_scheduler() noexcept 145   12756 inline scheduler& get_scheduler() noexcept
146   { 146   {
HITCBC 147   13506 return *sched_; 147   12756 return *sched_;
148   } 148   }
149   149  
150   /// Destroy the timer service. 150   /// Destroy the timer service.
HITCBC 151   2764 ~timer_service() override = default; 151   2764 ~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   1382 inline void set_on_earliest_changed(callback cb) 157   1382 inline void set_on_earliest_changed(callback cb)
158   { 158   {
HITCBC 159   1382 on_earliest_changed_ = cb; 159   1382 on_earliest_changed_ = cb;
HITCBC 160   1382 } 160   1382 }
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   198971 inline time_point nearest_expiry() const noexcept 170   198561 inline time_point nearest_expiry() const noexcept
171   { 171   {
HITCBC 172   198971 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 172   198561 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 173   198971 return time_point(time_point::duration(ns)); 173   198561 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   228116 inline void refresh_cached_nearest() noexcept 208   226606 inline void refresh_cached_nearest() noexcept
209   { 209   {
HITCBC 210   228116 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 210   226606 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 211   225053 : heap_[0].time_.time_since_epoch().count(); 211   223641 : heap_[0].time_.time_since_epoch().count();
HITCBC 212   228116 cached_nearest_ns_.store(ns, std::memory_order_release); 212   226606 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 213   228116 } 213   226606 }
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   45 ~tl_cache_owner() 236   37 ~tl_cache_owner()
237   { 237   {
HITCBC 238   45 delete tl_cached_impl.get(); 238   37 delete tl_cached_impl.get();
HITCBC 239   45 tl_cached_impl.set(nullptr); 239   37 tl_cached_impl.set(nullptr);
HITCBC 240   45 } 240   37 }
241   }; 241   };
242   242  
243   inline void 243   inline void
HITCBC 244   6864 arm_tl_cache_cleanup() noexcept 244   6627 arm_tl_cache_cleanup() noexcept
245   { 245   {
HITCBC 246   6864 thread_local tl_cache_owner owner; 246   6627 thread_local tl_cache_owner owner;
247   (void)owner; 247   (void)owner;
HITCBC 248   6864 } 248   6627 }
249   249  
250   inline timer::implementation* 250   inline timer::implementation*
HITCBC 251   7621 try_pop_tl_cache(timer_service* svc) noexcept 251   7245 try_pop_tl_cache(timer_service* svc) noexcept
252   { 252   {
HITCBC 253   7621 auto* impl = tl_cached_impl.get(); 253   7245 auto* impl = tl_cached_impl.get();
HITCBC 254   7621 if (impl) 254   7245 if (impl)
255   { 255   {
HITCBC 256   6621 tl_cached_impl.set(nullptr); 256   6392 tl_cached_impl.set(nullptr);
HITCBC 257   6621 if (impl->svc_ == svc) 257   6392 if (impl->svc_ == svc)
HITCBC 258   6621 return impl; 258   6392 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   1000 return nullptr; 262   853 return nullptr;
263   } 263   }
264   264  
265   inline bool 265   inline bool
HITCBC 266   7595 try_push_tl_cache(timer::implementation* impl) noexcept 266   7219 try_push_tl_cache(timer::implementation* impl) noexcept
267   { 267   {
HITCBC 268   7595 if (!tl_cached_impl.get()) 268   7219 if (!tl_cached_impl.get())
269   { 269   {
HITCBC 270   6864 arm_tl_cache_cleanup(); 270   6627 arm_tl_cache_cleanup();
HITCBC 271   6864 tl_cached_impl.set(impl); 271   6627 tl_cached_impl.set(impl);
HITCBC 272   6864 return true; 272   6627 return true;
273   } 273   }
HITCBC 274   731 return false; 274   592 return false;
275   } 275   }
276   276  
277   inline void 277   inline void
HITCBC 278   1382 timer_service_invalidate_cache() noexcept 278   1382 timer_service_invalidate_cache() noexcept
279   { 279   {
HITCBC 280   1382 delete tl_cached_impl.get(); 280   1382 delete tl_cached_impl.get();
HITCBC 281   1382 tl_cached_impl.set(nullptr); 281   1382 tl_cached_impl.set(nullptr);
HITCBC 282   1382 } 282   1382 }
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   1382 timer_service::shutdown() 287   1382 timer_service::shutdown()
288   { 288   {
HITCBC 289   1382 timer_service_invalidate_cache(); 289   1382 timer_service_invalidate_cache();
HITCBC 290   1382 shutting_down_ = true; 290   1382 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   1382 std::vector<timer::implementation*> impls; 296   1382 std::vector<timer::implementation*> impls;
HITCBC 297   1382 impls.reserve(heap_.size()); 297   1382 impls.reserve(heap_.size());
HITCBC 298   1408 for (auto& entry : heap_) 298   1408 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   1382 heap_.clear(); 305   1382 heap_.clear();
HITCBC 306   1382 cached_nearest_ns_.store( 306   1382 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   1408 for (auto* impl : impls) 314   1408 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   2110 while (free_list_) 329   1974 while (free_list_)
330   { 330   {
HITCBC 331   728 auto* next = free_list_->next_free_; 331   592 auto* next = free_list_->next_free_;
HITCBC 332   728 delete free_list_; 332   592 delete free_list_;
HITCBC 333   728 free_list_ = next; 333   592 free_list_ = next;
334   } 334   }
HITCBC 335   1382 } 335   1382 }
336   336  
337   inline io_object::implementation* 337   inline io_object::implementation*
HITCBC 338   7621 timer_service::construct() 338   7245 timer_service::construct()
339   { 339   {
HITCBC 340   7621 timer::implementation* impl = try_pop_tl_cache(this); 340   7245 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 341   7621 if (impl) 341   7245 if (impl)
342   { 342   {
HITCBC 343   6621 impl->svc_ = this; 343   6392 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   6621 impl->expiry_ = {}; 346   6392 impl->expiry_ = {};
HITCBC 347   6621 impl->heap_index_.store( 347   6392 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   6621 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 350   6392 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
HITCBC 351   6621 return impl; 351   6392 return impl;
352   } 352   }
353   353  
HITCBC 354   1000 std::lock_guard lock(mutex_); 354   853 std::lock_guard lock(mutex_);
HITCBC 355   1000 if (free_list_) 355   853 if (free_list_)
356   { 356   {
MISLBC 357   3 impl = free_list_; 357   ✗ impl = free_list_;
MISLBC 358   3 free_list_ = impl->next_free_; 358   ✗ free_list_ = impl->next_free_;
MISLBC 359   3 impl->next_free_ = nullptr; 359   ✗ impl->next_free_ = nullptr;
MISLBC 360   3 impl->svc_ = this; 360   ✗ impl->svc_ = this;
MISLBC 361   3 impl->expiry_ = {}; 361   ✗ impl->expiry_ = {};
MISLBC 362   3 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);
MISLBC 365   3 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   997 impl = new timer::implementation(*this); 369   853 impl = new timer::implementation(*this);
370   } 370   }
HITCBC 371   1000 return impl; 371   853 return impl;
HITCBC 372   1000 } 372   853 }
373   373  
374   inline void 374   inline void
HITCBC 375   7621 timer_service::destroy(io_object::implementation* p) 375   7245 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   7621 if (shutting_down_) 383   7245 if (shutting_down_)
HITCBC 384   26 return; 384   26 return;
HITCBC 385   7595 destroy_impl(static_cast<timer::implementation&>(*p)); 385   7219 destroy_impl(static_cast<timer::implementation&>(*p));
386   } 386   }
387   387  
388   inline void 388   inline void
HITCBC 389   7595 timer_service::destroy_impl(timer::implementation& impl) 389   7219 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   7595 if (shutting_down_) 395   7219 if (shutting_down_)
HITCBC 396   6864 return; 396   6627 return;
397   397  
HITCBC 398   7595 cancel_timer(impl); 398   7219 cancel_timer(impl);
399   399  
HITCBC 400   15190 if (impl.heap_index_.load(std::memory_order_relaxed) != 400   14438 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 401   7595 (std::numeric_limits<std::size_t>::max)()) 401   7219 (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   7595 if (try_push_tl_cache(&impl)) 408   7219 if (try_push_tl_cache(&impl))
HITCBC 409   6864 return; 409   6627 return;
410   410  
HITCBC 411   731 std::lock_guard lock(mutex_); 411   592 std::lock_guard lock(mutex_);
HITCBC 412   731 impl.next_free_ = free_list_; 412   592 impl.next_free_ = free_list_;
HITCBC 413   731 free_list_ = &impl; 413   592 free_list_ = &impl;
HITCBC 414   731 } 414   592 }
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   6766 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 476   6391 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
477   { 477   {
HITCBC 478   6766 bool notify = false; 478   6391 bool notify = false;
HITCBC 479   6766 bool lost_cancel = false; 479   6391 bool lost_cancel = false;
480   { 480   {
HITCBC 481   6766 std::lock_guard lock(mutex_); 481   6391 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   6766 w->impl_ = &impl; 484   6391 w->impl_ = &impl;
HITCBC 485   13532 if (impl.heap_index_.load(std::memory_order_relaxed) == 485   12782 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 486   6766 (std::numeric_limits<std::size_t>::max)()) 486   6391 (std::numeric_limits<std::size_t>::max)())
487   { 487   {
HITCBC 488   6766 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 488   6391 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 489   6766 heap_.push_back({impl.expiry_, &impl}); 489   6391 heap_.push_back({impl.expiry_, &impl});
HITCBC 490   6766 up_heap(heap_.size() - 1); 490   6391 up_heap(heap_.size() - 1);
HITCBC 491   6766 notify = 491   6391 notify =
HITCBC 492   6766 (impl.heap_index_.load(std::memory_order_relaxed) == 0); 492   6391 (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 493   6766 refresh_cached_nearest(); 493   6391 refresh_cached_nearest();
494   } 494   }
HITCBC 495   6766 impl.waiters_.push_back(w); 495   6391 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   6766 if (w->token_->stop_requested()) 500   6391 if (w->token_->stop_requested())
501   { 501   {
HITCBC 502   6 w->impl_ = nullptr; 502   4 w->impl_ = nullptr;
HITCBC 503   6 impl.waiters_.remove(w); 503   4 impl.waiters_.remove(w);
HITCBC 504   6 if (impl.waiters_.empty()) 504   4 if (impl.waiters_.empty())
505   { 505   {
HITCBC 506   6 remove_timer_impl(impl); 506   4 remove_timer_impl(impl);
HITCBC 507   6 impl.might_have_pending_waits_.store( 507   4 impl.might_have_pending_waits_.store(
508   false, std::memory_order_relaxed); 508   false, std::memory_order_relaxed);
509   } 509   }
HITCBC 510   6 refresh_cached_nearest(); 510   4 refresh_cached_nearest();
HITCBC 511   6 lost_cancel = true; 511   4 lost_cancel = true;
HITCBC 512   6 notify = false; // insertion undone; nearest unchanged 512   4 notify = false; // insertion undone; nearest unchanged
513   } 513   }
HITCBC 514   6766 } 514   6391 }
HITCBC 515   6766 if (notify) 515   6391 if (notify)
HITCBC 516   5951 on_earliest_changed_(); 516   5784 on_earliest_changed_();
HITCBC 517   6766 if (lost_cancel) 517   6391 if (lost_cancel)
518   { 518   {
HITCBC 519   6 w->ec_ = make_error_code(capy::error::canceled); 519   4 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 520   6 sched_->post(&w->op_); 520   4 sched_->post(&w->op_);
521   } 521   }
HITCBC 522   6766 } 522   6391 }
523   523  
524   inline std::size_t 524   inline std::size_t
HITCBC 525   7595 timer_service::cancel_timer(timer::implementation& impl) 525   7219 timer_service::cancel_timer(timer::implementation& impl)
526   { 526   {
HITCBC 527   7595 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 527   7219 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
HITCBC 528   7593 return 0; 528   7217 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   1949 timer_service::cancel_waiter(waiter_node* w) 565   1667 timer_service::cancel_waiter(waiter_node* w)
566   { 566   {
567   { 567   {
HITCBC 568   1949 std::lock_guard lock(mutex_); 568   1667 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   1949 if (!w->impl_) 572   1667 if (!w->impl_)
HITCBC 573   72 return; 573   4 return;
HITCBC 574   1877 auto* impl = w->impl_; 574   1663 auto* impl = w->impl_;
HITCBC 575   1877 w->impl_ = nullptr; 575   1663 w->impl_ = nullptr;
HITCBC 576   1877 impl->waiters_.remove(w); 576   1663 impl->waiters_.remove(w);
HITCBC 577   1877 if (impl->waiters_.empty()) 577   1663 if (impl->waiters_.empty())
578   { 578   {
HITCBC 579   1877 remove_timer_impl(*impl); 579   1663 remove_timer_impl(*impl);
HITCBC 580   1877 impl->might_have_pending_waits_.store( 580   1663 impl->might_have_pending_waits_.store(
581   false, std::memory_order_relaxed); 581   false, std::memory_order_relaxed);
582   } 582   }
HITCBC 583   1877 refresh_cached_nearest(); 583   1663 refresh_cached_nearest();
HITCBC 584   1949 } 584   1667 }
585   585  
HITCBC 586   1877 w->ec_ = make_error_code(capy::error::canceled); 586   1663 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 587   1877 sched_->post(&w->op_); 587   1663 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   219465 timer_service::process_expired() 619   218546 timer_service::process_expired()
620   { 620   {
HITCBC 621   219465 intrusive_list<waiter_node> expired; 621   218546 intrusive_list<waiter_node> expired;
622   622  
623   { 623   {
HITCBC 624   219465 std::lock_guard lock(mutex_); 624   218546 std::lock_guard lock(mutex_);
HITCBC 625   219465 auto now = clock_type::now(); 625   218546 auto now = clock_type::now();
626   626  
HITCBC 627   224320 while (!heap_.empty() && heap_[0].time_ <= now) 627   223242 while (!heap_.empty() && heap_[0].time_ <= now)
628   { 628   {
HITCBC 629   4855 timer::implementation* t = heap_[0].timer_; 629   4696 timer::implementation* t = heap_[0].timer_;
HITCBC 630   4855 remove_timer_impl(*t); 630   4696 remove_timer_impl(*t);
HITCBC 631   9710 while (auto* w = t->waiters_.pop_front()) 631   9392 while (auto* w = t->waiters_.pop_front())
632   { 632   {
HITCBC 633   4855 w->impl_ = nullptr; 633   4696 w->impl_ = nullptr;
HITCBC 634   4855 w->ec_ = {}; 634   4696 w->ec_ = {};
HITCBC 635   4855 expired.push_back(w); 635   4696 expired.push_back(w);
HITCBC 636   4855 } 636   4696 }
HITCBC 637   4855 t->might_have_pending_waits_.store( 637   4696 t->might_have_pending_waits_.store(
638   false, std::memory_order_relaxed); 638   false, std::memory_order_relaxed);
639   } 639   }
640   640  
HITCBC 641   219465 refresh_cached_nearest(); 641   218546 refresh_cached_nearest();
HITCBC 642   219465 } 642   218546 }
643   643  
HITCBC 644   219465 std::size_t count = 0; 644   218546 std::size_t count = 0;
HITCBC 645   224320 while (auto* w = expired.pop_front()) 645   223242 while (auto* w = expired.pop_front())
646   { 646   {
HITCBC 647   4855 sched_->post(&w->op_); 647   4696 sched_->post(&w->op_);
HITCBC 648   4855 ++count; 648   4696 ++count;
HITCBC 649   4855 } 649   4696 }
650   650  
HITCBC 651   219465 return count; 651   218546 return count;
652   } 652   }
653   653  
654   inline void 654   inline void
HITCBC 655   6740 timer_service::remove_timer_impl(timer::implementation& impl) 655   6365 timer_service::remove_timer_impl(timer::implementation& impl)
656   { 656   {
HITCBC 657   6740 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 657   6365 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 658   6740 if (index >= heap_.size()) 658   6365 if (index >= heap_.size())
MISUBC 659   ✗ return; // Not in heap 659   ✗ return; // Not in heap
660   660  
HITCBC 661   6740 if (index == heap_.size() - 1) 661   6365 if (index == heap_.size() - 1)
662   { 662   {
663   // Last element, just pop 663   // Last element, just pop
HITCBC 664   1540 impl.heap_index_.store( 664   1405 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   1540 heap_.pop_back(); 667   1405 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   5200 swap_heap(index, heap_.size() - 1); 672   4960 swap_heap(index, heap_.size() - 1);
HITCBC 673   5200 impl.heap_index_.store( 673   4960 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   5200 heap_.pop_back(); 676   4960 heap_.pop_back();
677   677  
HITCBC 678   5200 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 678   4960 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
MISLBC 679   4 up_heap(index); 679   ✗ up_heap(index);
680   else 680   else
HITCBC 681   5196 down_heap(index); 681   4960 down_heap(index);
682   } 682   }
683   } 683   }
684   684  
685   inline void 685   inline void
HITCBC 686   6770 timer_service::up_heap(std::size_t index) 686   6391 timer_service::up_heap(std::size_t index)
687   { 687   {
HITCBC 688   11593 while (index > 0) 688   11071 while (index > 0)
689   { 689   {
HITCBC 690   5636 std::size_t parent = (index - 1) / 2; 690   5283 std::size_t parent = (index - 1) / 2;
HITCBC 691   5636 if (!(heap_[index].time_ < heap_[parent].time_)) 691   5283 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 692   813 break; 692   603 break;
HITCBC 693   4823 swap_heap(index, parent); 693   4680 swap_heap(index, parent);
HITCBC 694   4823 index = parent; 694   4680 index = parent;
695   } 695   }
HITCBC 696   6770 } 696   6391 }
697   697  
698   inline void 698   inline void
HITCBC 699   5196 timer_service::down_heap(std::size_t index) 699   4960 timer_service::down_heap(std::size_t index)
700   { 700   {
HITCBC 701   5196 std::size_t child = index * 2 + 1; 701   4960 std::size_t child = index * 2 + 1;
HITCBC 702   6636 while (child < heap_.size()) 702   5772 while (child < heap_.size())
703   { 703   {
HITCBC 704   1542 std::size_t min_child = (child + 1 == heap_.size() || 704   925 std::size_t min_child = (child + 1 == heap_.size() ||
HITCBC 705   1488 heap_[child].time_ < heap_[child + 1].time_) 705   840 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 706   3030 ? child 706   1765 ? child
HITCBC 707   1542 : child + 1; 707   925 : child + 1;
708   708  
HITCBC 709   1542 if (heap_[index].time_ < heap_[min_child].time_) 709   925 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 710   102 break; 710   113 break;
711   711  
HITCBC 712   1440 swap_heap(index, min_child); 712   812 swap_heap(index, min_child);
HITCBC 713   1440 index = min_child; 713   812 index = min_child;
HITCBC 714   1440 child = index * 2 + 1; 714   812 child = index * 2 + 1;
715   } 715   }
HITCBC 716   5196 } 716   4960 }
717   717  
718   inline void 718   inline void
HITCBC 719   11463 timer_service::swap_heap(std::size_t i1, std::size_t i2) 719   10452 timer_service::swap_heap(std::size_t i1, std::size_t i2)
720   { 720   {
HITCBC 721   11463 heap_entry tmp = heap_[i1]; 721   10452 heap_entry tmp = heap_[i1];
HITCBC 722   11463 heap_[i1] = heap_[i2]; 722   10452 heap_[i1] = heap_[i2];
HITCBC 723   11463 heap_[i2] = tmp; 723   10452 heap_[i2] = tmp;
HITCBC 724   11463 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 724   10452 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 725   11463 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 725   10452 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 726   11463 } 726   10452 }
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   1382 get_timer_service(capy::execution_context& ctx, scheduler& sched) 763   1382 get_timer_service(capy::execution_context& ctx, scheduler& sched)
764   { 764   {
HITCBC 765   1382 return ctx.make_service<timer_service>(sched); 765   1382 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