. /include/boost/corosio /detail /timer_service.hpp
79.05% Lines (234/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   1227 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   1227 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   6985 void operator()() const 110   4731 void operator()() const
111   { 111   {
HITCBC 112   6985 if (fn_) 112   4731 if (fn_)
HITCBC 113   6985 fn_(ctx_); 113   4731 fn_(ctx_);
HITCBC 114   6985 } 114   4731 }
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   1227 inline timer_service(capy::execution_context&, scheduler& sched) 139   1227 inline timer_service(capy::execution_context&, scheduler& sched)
HITCBC 140   1227 : sched_(&sched) 140   1227 : sched_(&sched)
141   { 141   {
HITCBC 142   1227 } 142   1227 }
143   143  
144   /// Return the associated scheduler. 144   /// Return the associated scheduler.
HITCBC 145   14306 inline scheduler& get_scheduler() noexcept 145   11328 inline scheduler& get_scheduler() noexcept
146   { 146   {
HITCBC 147   14306 return *sched_; 147   11328 return *sched_;
148   } 148   }
149   149  
150   /// Destroy the timer service. 150   /// Destroy the timer service.
HITCBC 151   2454 ~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   1227 inline void set_on_earliest_changed(callback cb) 157   1227 inline void set_on_earliest_changed(callback cb)
158   { 158   {
HITCBC 159   1227 on_earliest_changed_ = cb; 159   1227 on_earliest_changed_ = cb;
HITCBC 160   1227 } 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   206836 inline time_point nearest_expiry() const noexcept 170   83385 inline time_point nearest_expiry() const noexcept
171   { 171   {
HITCBC 172   206836 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 172   83385 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 173   206836 return time_point(time_point::duration(ns)); 173   83385 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   234591 inline void refresh_cached_nearest() noexcept 208   98593 inline void refresh_cached_nearest() noexcept
209   { 209   {
HITCBC 210   234591 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 210   98593 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 211   231496 : heap_[0].time_.time_since_epoch().count(); 211   95644 : heap_[0].time_.time_since_epoch().count();
HITCBC 212   234591 cached_nearest_ns_.store(ns, std::memory_order_release); 212   98593 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 213   234591 } 213   98593 }
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   36 ~tl_cache_owner() 236   46 ~tl_cache_owner()
237   { 237   {
HITCBC 238   36 delete tl_cached_impl.get(); 238   46 delete tl_cached_impl.get();
HITCBC 239   36 tl_cached_impl.set(nullptr); 239   46 tl_cached_impl.set(nullptr);
HITCBC 240   36 } 240   46 }
241   }; 241   };
242   242  
243   inline void 243   inline void
HITCBC 244   7951 arm_tl_cache_cleanup() noexcept 244   5657 arm_tl_cache_cleanup() noexcept
245   { 245   {
HITCBC 246   7951 thread_local tl_cache_owner owner; 246   5657 thread_local tl_cache_owner owner;
247   (void)owner; 247   (void)owner;
HITCBC 248   7951 } 248   5657 }
249   249  
250   inline timer::implementation* 250   inline timer::implementation*
HITCBC 251   8021 try_pop_tl_cache(timer_service* svc) noexcept 251   6471 try_pop_tl_cache(timer_service* svc) noexcept
252   { 252   {
HITCBC 253   8021 auto* impl = tl_cached_impl.get(); 253   6471 auto* impl = tl_cached_impl.get();
HITCBC 254   8021 if (impl) 254   6471 if (impl)
255   { 255   {
HITCBC 256   7729 tl_cached_impl.set(nullptr); 256   5425 tl_cached_impl.set(nullptr);
HITCBC 257   7729 if (impl->svc_ == svc) 257   5425 if (impl->svc_ == svc)
HITCBC 258   7729 return impl; 258   5425 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   292 return nullptr; 262   1046 return nullptr;
263   } 263   }
264   264  
265   inline bool 265   inline bool
HITCBC 266   7995 try_push_tl_cache(timer::implementation* impl) noexcept 266   6445 try_push_tl_cache(timer::implementation* impl) noexcept
267   { 267   {
HITCBC 268   7995 if (!tl_cached_impl.get()) 268   6445 if (!tl_cached_impl.get())
269   { 269   {
HITCBC 270   7951 arm_tl_cache_cleanup(); 270   5657 arm_tl_cache_cleanup();
HITCBC 271   7951 tl_cached_impl.set(impl); 271   5657 tl_cached_impl.set(impl);
HITCBC 272   7951 return true; 272   5657 return true;
273   } 273   }
HITCBC 274   44 return false; 274   788 return false;
275   } 275   }
276   276  
277   inline void 277   inline void
HITCBC 278   1227 timer_service_invalidate_cache() noexcept 278   1227 timer_service_invalidate_cache() noexcept
279   { 279   {
HITCBC 280   1227 delete tl_cached_impl.get(); 280   1227 delete tl_cached_impl.get();
HITCBC 281   1227 tl_cached_impl.set(nullptr); 281   1227 tl_cached_impl.set(nullptr);
HITCBC 282   1227 } 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   1227 timer_service::shutdown() 287   1227 timer_service::shutdown()
288   { 288   {
HITCBC 289   1227 timer_service_invalidate_cache(); 289   1227 timer_service_invalidate_cache();
HITCBC 290   1227 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   1227 std::vector<timer::implementation*> impls; 296   1227 std::vector<timer::implementation*> impls;
HITCBC 297   1227 impls.reserve(heap_.size()); 297   1227 impls.reserve(heap_.size());
HITCBC 298   1253 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   1227 heap_.clear(); 305   1227 heap_.clear();
HITCBC 306   1227 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   1253 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   1271 while (free_list_) 329   2014 while (free_list_)
330   { 330   {
HITCBC 331   44 auto* next = free_list_->next_free_; 331   787 auto* next = free_list_->next_free_;
HITCBC 332   44 delete free_list_; 332   787 delete free_list_;
HITCBC 333   44 free_list_ = next; 333   787 free_list_ = next;
334   } 334   }
HITCBC 335   1227 } 335   1227 }
336   336  
337   inline io_object::implementation* 337   inline io_object::implementation*
HITCBC 338   8021 timer_service::construct() 338   6471 timer_service::construct()
339   { 339   {
HITCBC 340   8021 timer::implementation* impl = try_pop_tl_cache(this); 340   6471 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 341   8021 if (impl) 341   6471 if (impl)
342   { 342   {
HITCBC 343   7729 impl->svc_ = this; 343   5425 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   7729 impl->expiry_ = {}; 346   5425 impl->expiry_ = {};
HITCBC 347   7729 impl->heap_index_.store( 347   5425 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   7729 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 350   5425 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
HITCBC 351   7729 return impl; 351   5425 return impl;
352   } 352   }
353   353  
HITCBC 354   292 std::lock_guard lock(mutex_); 354   1046 std::lock_guard lock(mutex_);
HITCBC 355   292 if (free_list_) 355   1046 if (free_list_)
356   { 356   {
HITGBC 357   ✗ impl = free_list_; 357   1 impl = free_list_;
HITGBC 358   ✗ free_list_ = impl->next_free_; 358   1 free_list_ = impl->next_free_;
HITGBC 359   ✗ impl->next_free_ = nullptr; 359   1 impl->next_free_ = nullptr;
HITGBC 360   ✗ impl->svc_ = this; 360   1 impl->svc_ = this;
HITGBC 361   ✗ impl->expiry_ = {}; 361   1 impl->expiry_ = {};
HITGBC 362   ✗ impl->heap_index_.store( 362   1 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);
HITGBC 365   ✗ impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 365   1 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
366   } 366   }
367   else 367   else
368   { 368   {
HITCBC 369   292 impl = new timer::implementation(*this); 369   1045 impl = new timer::implementation(*this);
370   } 370   }
HITCBC 371   292 return impl; 371   1046 return impl;
HITCBC 372   292 } 372   1046 }
373   373  
374   inline void 374   inline void
HITCBC 375   8021 timer_service::destroy(io_object::implementation* p) 375   6471 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   8021 if (shutting_down_) 383   6471 if (shutting_down_)
HITCBC 384   26 return; 384   26 return;
HITCBC 385   7995 destroy_impl(static_cast<timer::implementation&>(*p)); 385   6445 destroy_impl(static_cast<timer::implementation&>(*p));
386   } 386   }
387   387  
388   inline void 388   inline void
HITCBC 389   7995 timer_service::destroy_impl(timer::implementation& impl) 389   6445 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   7995 if (shutting_down_) 395   6445 if (shutting_down_)
HITCBC 396   7951 return; 396   5657 return;
397   397  
HITCBC 398   7995 cancel_timer(impl); 398   6445 cancel_timer(impl);
399   399  
HITCBC 400   15990 if (impl.heap_index_.load(std::memory_order_relaxed) != 400   12890 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 401   7995 (std::numeric_limits<std::size_t>::max)()) 401   6445 (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   7995 if (try_push_tl_cache(&impl)) 408   6445 if (try_push_tl_cache(&impl))
HITCBC 409   7951 return; 409   5657 return;
410   410  
HITCBC 411   44 std::lock_guard lock(mutex_); 411   788 std::lock_guard lock(mutex_);
HITCBC 412   44 impl.next_free_ = free_list_; 412   788 impl.next_free_ = free_list_;
HITCBC 413   44 free_list_ = &impl; 413   788 free_list_ = &impl;
HITCBC 414   44 } 414   788 }
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   7166 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 476   5677 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
477   { 477   {
HITCBC 478   7166 bool notify = false; 478   5677 bool notify = false;
HITCBC 479   7166 bool lost_cancel = false; 479   5677 bool lost_cancel = false;
480   { 480   {
HITCBC 481   7166 std::lock_guard lock(mutex_); 481   5677 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   7166 w->impl_ = &impl; 484   5677 w->impl_ = &impl;
HITCBC 485   14332 if (impl.heap_index_.load(std::memory_order_relaxed) == 485   11354 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 486   7166 (std::numeric_limits<std::size_t>::max)()) 486   5677 (std::numeric_limits<std::size_t>::max)())
487   { 487   {
HITCBC 488   7166 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 488   5677 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 489   7166 heap_.push_back({impl.expiry_, &impl}); 489   5677 heap_.push_back({impl.expiry_, &impl});
HITCBC 490   7166 up_heap(heap_.size() - 1); 490   5677 up_heap(heap_.size() - 1);
HITCBC 491   7166 notify = 491   5677 notify =
HITCBC 492   7166 (impl.heap_index_.load(std::memory_order_relaxed) == 0); 492   5677 (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 493   7166 refresh_cached_nearest(); 493   5677 refresh_cached_nearest();
494   } 494   }
HITCBC 495   7166 impl.waiters_.push_back(w); 495   5677 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   7166 if (w->token_->stop_requested()) 500   5677 if (w->token_->stop_requested())
501   { 501   {
HITGBC 502   ✗ w->impl_ = nullptr; 502   4 w->impl_ = nullptr;
HITGBC 503   ✗ impl.waiters_.remove(w); 503   4 impl.waiters_.remove(w);
HITGBC 504   ✗ if (impl.waiters_.empty()) 504   4 if (impl.waiters_.empty())
505   { 505   {
HITGBC 506   ✗ remove_timer_impl(impl); 506   4 remove_timer_impl(impl);
HITGBC 507   ✗ 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   }
HITGBC 510   ✗ refresh_cached_nearest(); 510   4 refresh_cached_nearest();
HITGBC 511   ✗ lost_cancel = true; 511   4 lost_cancel = true;
HITGBC 512   ✗ notify = false; // insertion undone; nearest unchanged 512   4 notify = false; // insertion undone; nearest unchanged
513   } 513   }
HITCBC 514   7166 } 514   5677 }
HITCBC 515   7166 if (notify) 515   5677 if (notify)
HITCBC 516   6985 on_earliest_changed_(); 516   4731 on_earliest_changed_();
HITCBC 517   7166 if (lost_cancel) 517   5677 if (lost_cancel)
518   { 518   {
HITGBC 519   ✗ w->ec_ = make_error_code(capy::error::canceled); 519   4 w->ec_ = make_error_code(capy::error::canceled);
HITGBC 520   ✗ sched_->post(&w->op_); 520   4 sched_->post(&w->op_);
521   } 521   }
HITCBC 522   7166 } 522   5677 }
523   523  
524   inline std::size_t 524   inline std::size_t
HITCBC 525   7995 timer_service::cancel_timer(timer::implementation& impl) 525   6445 timer_service::cancel_timer(timer::implementation& impl)
526   { 526   {
HITCBC 527   7995 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 527   6445 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
HITCBC 528   7993 return 0; 528   6443 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   1386 timer_service::cancel_waiter(waiter_node* w) 565   1785 timer_service::cancel_waiter(waiter_node* w)
566   { 566   {
567   { 567   {
HITCBC 568   1386 std::lock_guard lock(mutex_); 568   1785 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   1386 if (!w->impl_) 572   1785 if (!w->impl_)
HITGBC 573   ✗ return; 573   91 return;
HITCBC 574   1386 auto* impl = w->impl_; 574   1694 auto* impl = w->impl_;
HITCBC 575   1386 w->impl_ = nullptr; 575   1694 w->impl_ = nullptr;
HITCBC 576   1386 impl->waiters_.remove(w); 576   1694 impl->waiters_.remove(w);
HITCBC 577   1386 if (impl->waiters_.empty()) 577   1694 if (impl->waiters_.empty())
578   { 578   {
HITCBC 579   1386 remove_timer_impl(*impl); 579   1694 remove_timer_impl(*impl);
HITCBC 580   1386 impl->might_have_pending_waits_.store( 580   1694 impl->might_have_pending_waits_.store(
581   false, std::memory_order_relaxed); 581   false, std::memory_order_relaxed);
582   } 582   }
HITCBC 583   1386 refresh_cached_nearest(); 583   1694 refresh_cached_nearest();
HITCBC 584   1386 } 584   1785 }
585   585  
HITCBC 586   1386 w->ec_ = make_error_code(capy::error::canceled); 586   1694 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 587   1386 sched_->post(&w->op_); 587   1694 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   226037 timer_service::process_expired() 619   91216 timer_service::process_expired()
620   { 620   {
HITCBC 621   226037 intrusive_list<waiter_node> expired; 621   91216 intrusive_list<waiter_node> expired;
622   622  
623   { 623   {
HITCBC 624   226037 std::lock_guard lock(mutex_); 624   91216 std::lock_guard lock(mutex_);
HITCBC 625   226037 auto now = clock_type::now(); 625   91216 auto now = clock_type::now();
626   626  
HITCBC 627   231789 while (!heap_.empty() && heap_[0].time_ <= now) 627   95167 while (!heap_.empty() && heap_[0].time_ <= now)
628   { 628   {
HITCBC 629   5752 timer::implementation* t = heap_[0].timer_; 629   3951 timer::implementation* t = heap_[0].timer_;
HITCBC 630   5752 remove_timer_impl(*t); 630   3951 remove_timer_impl(*t);
HITCBC 631   11504 while (auto* w = t->waiters_.pop_front()) 631   7902 while (auto* w = t->waiters_.pop_front())
632   { 632   {
HITCBC 633   5752 w->impl_ = nullptr; 633   3951 w->impl_ = nullptr;
HITCBC 634   5752 w->ec_ = {}; 634   3951 w->ec_ = {};
HITCBC 635   5752 expired.push_back(w); 635   3951 expired.push_back(w);
HITCBC 636   5752 } 636   3951 }
HITCBC 637   5752 t->might_have_pending_waits_.store( 637   3951 t->might_have_pending_waits_.store(
638   false, std::memory_order_relaxed); 638   false, std::memory_order_relaxed);
639   } 639   }
640   640  
HITCBC 641   226037 refresh_cached_nearest(); 641   91216 refresh_cached_nearest();
HITCBC 642   226037 } 642   91216 }
643   643  
HITCBC 644   226037 std::size_t count = 0; 644   91216 std::size_t count = 0;
HITCBC 645   231789 while (auto* w = expired.pop_front()) 645   95167 while (auto* w = expired.pop_front())
646   { 646   {
HITCBC 647   5752 sched_->post(&w->op_); 647   3951 sched_->post(&w->op_);
HITCBC 648   5752 ++count; 648   3951 ++count;
HITCBC 649   5752 } 649   3951 }
650   650  
HITCBC 651   226037 return count; 651   91216 return count;
652   } 652   }
653   653  
654   inline void 654   inline void
HITCBC 655   7140 timer_service::remove_timer_impl(timer::implementation& impl) 655   5651 timer_service::remove_timer_impl(timer::implementation& impl)
656   { 656   {
HITCBC 657   7140 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 657   5651 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 658   7140 if (index >= heap_.size()) 658   5651 if (index >= heap_.size())
MISUBC 659   ✗ return; // Not in heap 659   ✗ return; // Not in heap
660   660  
HITCBC 661   7140 if (index == heap_.size() - 1) 661   5651 if (index == heap_.size() - 1)
662   { 662   {
663   // Last element, just pop 663   // Last element, just pop
HITCBC 664   1620 impl.heap_index_.store( 664   1518 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   1620 heap_.pop_back(); 667   1518 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   5520 swap_heap(index, heap_.size() - 1); 672   4133 swap_heap(index, heap_.size() - 1);
HITCBC 673   5520 impl.heap_index_.store( 673   4133 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   5520 heap_.pop_back(); 676   4133 heap_.pop_back();
677   677  
HITCBC 678   5520 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 678   4133 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
HITGBC 679   ✗ up_heap(index); 679   1 up_heap(index);
680   else 680   else
HITCBC 681   5520 down_heap(index); 681   4132 down_heap(index);
682   } 682   }
683   } 683   }
684   684  
685   inline void 685   inline void
HITCBC 686   7166 timer_service::up_heap(std::size_t index) 686   5678 timer_service::up_heap(std::size_t index)
687   { 687   {
HITCBC 688   12660 while (index > 0) 688   9322 while (index > 0)
689   { 689   {
HITCBC 690   5675 std::size_t parent = (index - 1) / 2; 690   4587 std::size_t parent = (index - 1) / 2;
HITCBC 691   5675 if (!(heap_[index].time_ < heap_[parent].time_)) 691   4587 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 692   181 break; 692   943 break;
HITCBC 693   5494 swap_heap(index, parent); 693   3644 swap_heap(index, parent);
HITCBC 694   5494 index = parent; 694   3644 index = parent;
695   } 695   }
HITCBC 696   7166 } 696   5678 }
697   697  
698   inline void 698   inline void
HITCBC 699   5520 timer_service::down_heap(std::size_t index) 699   4132 timer_service::down_heap(std::size_t index)
700   { 700   {
HITCBC 701   5520 std::size_t child = index * 2 + 1; 701   4132 std::size_t child = index * 2 + 1;
HITCBC 702   5522 while (child < heap_.size()) 702   6356 while (child < heap_.size())
703   { 703   {
HITCBC 704   4 std::size_t min_child = (child + 1 == heap_.size() || 704   2305 std::size_t min_child = (child + 1 == heap_.size() ||
HITGBC 705   ✗ heap_[child].time_ < heap_[child + 1].time_) 705   2256 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 706   4 ? child 706   4561 ? child
HITCBC 707   4 : child + 1; 707   2305 : child + 1;
708   708  
HITCBC 709   4 if (heap_[index].time_ < heap_[min_child].time_) 709   2305 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 710   2 break; 710   81 break;
711   711  
HITCBC 712   2 swap_heap(index, min_child); 712   2224 swap_heap(index, min_child);
HITCBC 713   2 index = min_child; 713   2224 index = min_child;
HITCBC 714   2 child = index * 2 + 1; 714   2224 child = index * 2 + 1;
715   } 715   }
HITCBC 716   5520 } 716   4132 }
717   717  
718   inline void 718   inline void
HITCBC 719   11016 timer_service::swap_heap(std::size_t i1, std::size_t i2) 719   10001 timer_service::swap_heap(std::size_t i1, std::size_t i2)
720   { 720   {
HITCBC 721   11016 heap_entry tmp = heap_[i1]; 721   10001 heap_entry tmp = heap_[i1];
HITCBC 722   11016 heap_[i1] = heap_[i2]; 722   10001 heap_[i1] = heap_[i2];
HITCBC 723   11016 heap_[i2] = tmp; 723   10001 heap_[i2] = tmp;
HITCBC 724   11016 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 724   10001 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 725   11016 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 725   10001 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 726   11016 } 726   10001 }
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   1227 get_timer_service(capy::execution_context& ctx, scheduler& sched) 763   1227 get_timer_service(capy::execution_context& ctx, scheduler& sched)
764   { 764   {
HITCBC 765   1227 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