. /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   1227 callback() = default; 98   1370 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   1370 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   8123 void operator()() const 110   5835 void operator()() const
111   { 111   {
HITCBC 112   8123 if (fn_) 112   5835 if (fn_)
HITCBC 113   8123 fn_(ctx_); 113   5835 fn_(ctx_);
HITCBC 114   8123 } 114   5835 }
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   1370 inline timer_service(capy::execution_context&, scheduler& sched)
HITCBC 140   1227 : sched_(&sched) 140   1370 : sched_(&sched)
141   { 141   {
HITCBC 142   1227 } 142   1370 }
143   143  
144   /// Return the associated scheduler. 144   /// Return the associated scheduler.
HITCBC 145   17566 inline scheduler& get_scheduler() noexcept 145   12028 inline scheduler& get_scheduler() noexcept
146   { 146   {
HITCBC 147   17566 return *sched_; 147   12028 return *sched_;
148   } 148   }
149   149  
150   /// Destroy the timer service. 150   /// Destroy the timer service.
HITCBC 151   2454 ~timer_service() override = default; 151   2740 ~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   1370 inline void set_on_earliest_changed(callback cb)
158   { 158   {
HITCBC 159   1227 on_earliest_changed_ = cb; 159   1370 on_earliest_changed_ = cb;
HITCBC 160   1227 } 160   1370 }
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   209435 inline time_point nearest_expiry() const noexcept 170   182627 inline time_point nearest_expiry() const noexcept
171   { 171   {
HITCBC 172   209435 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 172   182627 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 173   209435 return time_point(time_point::duration(ns)); 173   182627 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   240852 inline void refresh_cached_nearest() noexcept 208   205216 inline void refresh_cached_nearest() noexcept
209   { 209   {
HITCBC 210   240852 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 210   205216 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 211   237763 : heap_[0].time_.time_since_epoch().count(); 211   202095 : heap_[0].time_.time_since_epoch().count();
HITCBC 212   240852 cached_nearest_ns_.store(ns, std::memory_order_release); 212   205216 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 213   240852 } 213   205216 }
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   48 ~tl_cache_owner() 236   38 ~tl_cache_owner()
237   { 237   {
HITCBC 238   48 delete tl_cached_impl.get(); 238   38 delete tl_cached_impl.get();
HITCBC 239   48 tl_cached_impl.set(nullptr); 239   38 tl_cached_impl.set(nullptr);
HITCBC 240   48 } 240   38 }
241   }; 241   };
242   242  
243   inline void 243   inline void
HITCBC 244   9103 arm_tl_cache_cleanup() noexcept 244   6755 arm_tl_cache_cleanup() noexcept
245   { 245   {
HITCBC 246   9103 thread_local tl_cache_owner owner; 246   6755 thread_local tl_cache_owner owner;
247   (void)owner; 247   (void)owner;
HITCBC 248   9103 } 248   6755 }
249   249  
250   inline timer::implementation* 250   inline timer::implementation*
HITCBC 251   9647 try_pop_tl_cache(timer_service* svc) noexcept 251   6865 try_pop_tl_cache(timer_service* svc) noexcept
252   { 252   {
HITCBC 253   9647 auto* impl = tl_cached_impl.get(); 253   6865 auto* impl = tl_cached_impl.get();
HITCBC 254   9647 if (impl) 254   6865 if (impl)
255   { 255   {
HITCBC 256   8869 tl_cached_impl.set(nullptr); 256   6527 tl_cached_impl.set(nullptr);
HITCBC 257   8869 if (impl->svc_ == svc) 257   6527 if (impl->svc_ == svc)
HITCBC 258   8869 return impl; 258   6527 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   778 return nullptr; 262   338 return nullptr;
263   } 263   }
264   264  
265   inline bool 265   inline bool
HITCBC 266   9621 try_push_tl_cache(timer::implementation* impl) noexcept 266   6839 try_push_tl_cache(timer::implementation* impl) noexcept
267   { 267   {
HITCBC 268   9621 if (!tl_cached_impl.get()) 268   6839 if (!tl_cached_impl.get())
269   { 269   {
HITCBC 270   9103 arm_tl_cache_cleanup(); 270   6755 arm_tl_cache_cleanup();
HITCBC 271   9103 tl_cached_impl.set(impl); 271   6755 tl_cached_impl.set(impl);
HITCBC 272   9103 return true; 272   6755 return true;
273   } 273   }
HITCBC 274   518 return false; 274   84 return false;
275   } 275   }
276   276  
277   inline void 277   inline void
HITCBC 278   1227 timer_service_invalidate_cache() noexcept 278   1370 timer_service_invalidate_cache() noexcept
279   { 279   {
HITCBC 280   1227 delete tl_cached_impl.get(); 280   1370 delete tl_cached_impl.get();
HITCBC 281   1227 tl_cached_impl.set(nullptr); 281   1370 tl_cached_impl.set(nullptr);
HITCBC 282   1227 } 282   1370 }
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   1370 timer_service::shutdown()
288   { 288   {
HITCBC 289   1227 timer_service_invalidate_cache(); 289   1370 timer_service_invalidate_cache();
HITCBC 290   1227 shutting_down_ = true; 290   1370 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   1370 std::vector<timer::implementation*> impls;
HITCBC 297   1227 impls.reserve(heap_.size()); 297   1370 impls.reserve(heap_.size());
HITCBC 298   1253 for (auto& entry : heap_) 298   1396 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   1370 heap_.clear();
HITCBC 306   1227 cached_nearest_ns_.store( 306   1370 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   1396 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   1743 while (free_list_) 329   1454 while (free_list_)
330   { 330   {
HITCBC 331   516 auto* next = free_list_->next_free_; 331   84 auto* next = free_list_->next_free_;
HITCBC 332   516 delete free_list_; 332   84 delete free_list_;
HITCBC 333   516 free_list_ = next; 333   84 free_list_ = next;
334   } 334   }
HITCBC 335   1227 } 335   1370 }
336   336  
337   inline io_object::implementation* 337   inline io_object::implementation*
HITCBC 338   9647 timer_service::construct() 338   6865 timer_service::construct()
339   { 339   {
HITCBC 340   9647 timer::implementation* impl = try_pop_tl_cache(this); 340   6865 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 341   9647 if (impl) 341   6865 if (impl)
342   { 342   {
HITCBC 343   8869 impl->svc_ = this; 343   6527 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   8869 impl->expiry_ = {}; 346   6527 impl->expiry_ = {};
HITCBC 347   8869 impl->heap_index_.store( 347   6527 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   8869 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed); 350   6527 impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
HITCBC 351   8869 return impl; 351   6527 return impl;
352   } 352   }
353   353  
HITCBC 354   778 std::lock_guard lock(mutex_); 354   338 std::lock_guard lock(mutex_);
HITCBC 355   778 if (free_list_) 355   338 if (free_list_)
356   { 356   {
MISLBC 357   2 impl = free_list_; 357   ✗ impl = free_list_;
MISLBC 358   2 free_list_ = impl->next_free_; 358   ✗ free_list_ = impl->next_free_;
MISLBC 359   2 impl->next_free_ = nullptr; 359   ✗ impl->next_free_ = nullptr;
MISLBC 360   2 impl->svc_ = this; 360   ✗ impl->svc_ = this;
MISLBC 361   2 impl->expiry_ = {}; 361   ✗ impl->expiry_ = {};
MISLBC 362   2 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   2 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   776 impl = new timer::implementation(*this); 369   338 impl = new timer::implementation(*this);
370   } 370   }
HITCBC 371   778 return impl; 371   338 return impl;
HITCBC 372   778 } 372   338 }
373   373  
374   inline void 374   inline void
HITCBC 375   9647 timer_service::destroy(io_object::implementation* p) 375   6865 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   9647 if (shutting_down_) 383   6865 if (shutting_down_)
HITCBC 384   26 return; 384   26 return;
HITCBC 385   9621 destroy_impl(static_cast<timer::implementation&>(*p)); 385   6839 destroy_impl(static_cast<timer::implementation&>(*p));
386   } 386   }
387   387  
388   inline void 388   inline void
HITCBC 389   9621 timer_service::destroy_impl(timer::implementation& impl) 389   6839 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   9621 if (shutting_down_) 395   6839 if (shutting_down_)
HITCBC 396   9103 return; 396   6755 return;
397   397  
HITCBC 398   9621 cancel_timer(impl); 398   6839 cancel_timer(impl);
399   399  
HITCBC 400   19242 if (impl.heap_index_.load(std::memory_order_relaxed) != 400   13678 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 401   9621 (std::numeric_limits<std::size_t>::max)()) 401   6839 (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   9621 if (try_push_tl_cache(&impl)) 408   6839 if (try_push_tl_cache(&impl))
HITCBC 409   9103 return; 409   6755 return;
410   410  
HITCBC 411   518 std::lock_guard lock(mutex_); 411   84 std::lock_guard lock(mutex_);
HITCBC 412   518 impl.next_free_ = free_list_; 412   84 impl.next_free_ = free_list_;
HITCBC 413   518 free_list_ = &impl; 413   84 free_list_ = &impl;
HITCBC 414   518 } 414   84 }
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   8796 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 476   6027 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
477   { 477   {
HITCBC 478   8796 bool notify = false; 478   6027 bool notify = false;
HITCBC 479   8796 bool lost_cancel = false; 479   6027 bool lost_cancel = false;
480   { 480   {
HITCBC 481   8796 std::lock_guard lock(mutex_); 481   6027 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   8796 w->impl_ = &impl; 484   6027 w->impl_ = &impl;
HITCBC 485   17592 if (impl.heap_index_.load(std::memory_order_relaxed) == 485   12054 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 486   8796 (std::numeric_limits<std::size_t>::max)()) 486   6027 (std::numeric_limits<std::size_t>::max)())
487   { 487   {
HITCBC 488   8796 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 488   6027 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 489   8796 heap_.push_back({impl.expiry_, &impl}); 489   6027 heap_.push_back({impl.expiry_, &impl});
HITCBC 490   8796 up_heap(heap_.size() - 1); 490   6027 up_heap(heap_.size() - 1);
HITCBC 491   8796 notify = 491   6027 notify =
HITCBC 492   8796 (impl.heap_index_.load(std::memory_order_relaxed) == 0); 492   6027 (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 493   8796 refresh_cached_nearest(); 493   6027 refresh_cached_nearest();
494   } 494   }
HITCBC 495   8796 impl.waiters_.push_back(w); 495   6027 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   8796 if (w->token_->stop_requested()) 500   6027 if (w->token_->stop_requested())
501   { 501   {
HITCBC 502   7 w->impl_ = nullptr; 502   2 w->impl_ = nullptr;
HITCBC 503   7 impl.waiters_.remove(w); 503   2 impl.waiters_.remove(w);
HITCBC 504   7 if (impl.waiters_.empty()) 504   2 if (impl.waiters_.empty())
505   { 505   {
HITCBC 506   7 remove_timer_impl(impl); 506   2 remove_timer_impl(impl);
HITCBC 507   7 impl.might_have_pending_waits_.store( 507   2 impl.might_have_pending_waits_.store(
508   false, std::memory_order_relaxed); 508   false, std::memory_order_relaxed);
509   } 509   }
HITCBC 510   7 refresh_cached_nearest(); 510   2 refresh_cached_nearest();
HITCBC 511   7 lost_cancel = true; 511   2 lost_cancel = true;
HITCBC 512   7 notify = false; // insertion undone; nearest unchanged 512   2 notify = false; // insertion undone; nearest unchanged
513   } 513   }
HITCBC 514   8796 } 514   6027 }
HITCBC 515   8796 if (notify) 515   6027 if (notify)
HITCBC 516   8123 on_earliest_changed_(); 516   5835 on_earliest_changed_();
HITCBC 517   8796 if (lost_cancel) 517   6027 if (lost_cancel)
518   { 518   {
HITCBC 519   7 w->ec_ = make_error_code(capy::error::canceled); 519   2 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 520   7 sched_->post(&w->op_); 520   2 sched_->post(&w->op_);
521   } 521   }
HITCBC 522   8796 } 522   6027 }
523   523  
524   inline std::size_t 524   inline std::size_t
HITCBC 525   9621 timer_service::cancel_timer(timer::implementation& impl) 525   6839 timer_service::cancel_timer(timer::implementation& impl)
526   { 526   {
HITCBC 527   9621 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed)) 527   6839 if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
HITCBC 528   9619 return 0; 528   6837 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   1872 timer_service::cancel_waiter(waiter_node* w) 565   1408 timer_service::cancel_waiter(waiter_node* w)
566   { 566   {
567   { 567   {
HITCBC 568   1872 std::lock_guard lock(mutex_); 568   1408 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   1872 if (!w->impl_) 572   1408 if (!w->impl_)
HITCBC 573   40 return; 573   4 return;
HITCBC 574   1832 auto* impl = w->impl_; 574   1404 auto* impl = w->impl_;
HITCBC 575   1832 w->impl_ = nullptr; 575   1404 w->impl_ = nullptr;
HITCBC 576   1832 impl->waiters_.remove(w); 576   1404 impl->waiters_.remove(w);
HITCBC 577   1832 if (impl->waiters_.empty()) 577   1404 if (impl->waiters_.empty())
578   { 578   {
HITCBC 579   1832 remove_timer_impl(*impl); 579   1404 remove_timer_impl(*impl);
HITCBC 580   1832 impl->might_have_pending_waits_.store( 580   1404 impl->might_have_pending_waits_.store(
581   false, std::memory_order_relaxed); 581   false, std::memory_order_relaxed);
582   } 582   }
HITCBC 583   1832 refresh_cached_nearest(); 583   1404 refresh_cached_nearest();
HITCBC 584   1872 } 584   1408 }
585   585  
HITCBC 586   1832 w->ec_ = make_error_code(capy::error::canceled); 586   1404 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 587   1832 sched_->post(&w->op_); 587   1404 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   230215 timer_service::process_expired() 619   197781 timer_service::process_expired()
620   { 620   {
HITCBC 621   230215 intrusive_list<waiter_node> expired; 621   197781 intrusive_list<waiter_node> expired;
622   622  
623   { 623   {
HITCBC 624   230215 std::lock_guard lock(mutex_); 624   197781 std::lock_guard lock(mutex_);
HITCBC 625   230215 auto now = clock_type::now(); 625   197781 auto now = clock_type::now();
626   626  
HITCBC 627   237144 while (!heap_.empty() && heap_[0].time_ <= now) 627   202374 while (!heap_.empty() && heap_[0].time_ <= now)
628   { 628   {
HITCBC 629   6929 timer::implementation* t = heap_[0].timer_; 629   4593 timer::implementation* t = heap_[0].timer_;
HITCBC 630   6929 remove_timer_impl(*t); 630   4593 remove_timer_impl(*t);
HITCBC 631   13858 while (auto* w = t->waiters_.pop_front()) 631   9186 while (auto* w = t->waiters_.pop_front())
632   { 632   {
HITCBC 633   6929 w->impl_ = nullptr; 633   4593 w->impl_ = nullptr;
HITCBC 634   6929 w->ec_ = {}; 634   4593 w->ec_ = {};
HITCBC 635   6929 expired.push_back(w); 635   4593 expired.push_back(w);
HITCBC 636   6929 } 636   4593 }
HITCBC 637   6929 t->might_have_pending_waits_.store( 637   4593 t->might_have_pending_waits_.store(
638   false, std::memory_order_relaxed); 638   false, std::memory_order_relaxed);
639   } 639   }
640   640  
HITCBC 641   230215 refresh_cached_nearest(); 641   197781 refresh_cached_nearest();
HITCBC 642   230215 } 642   197781 }
643   643  
HITCBC 644   230215 std::size_t count = 0; 644   197781 std::size_t count = 0;
HITCBC 645   237144 while (auto* w = expired.pop_front()) 645   202374 while (auto* w = expired.pop_front())
646   { 646   {
HITCBC 647   6929 sched_->post(&w->op_); 647   4593 sched_->post(&w->op_);
HITCBC 648   6929 ++count; 648   4593 ++count;
HITCBC 649   6929 } 649   4593 }
650   650  
HITCBC 651   230215 return count; 651   197781 return count;
652   } 652   }
653   653  
654   inline void 654   inline void
HITCBC 655   8770 timer_service::remove_timer_impl(timer::implementation& impl) 655   6001 timer_service::remove_timer_impl(timer::implementation& impl)
656   { 656   {
HITCBC 657   8770 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 657   6001 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 658   8770 if (index >= heap_.size()) 658   6001 if (index >= heap_.size())
MISUBC 659   ✗ return; // Not in heap 659   ✗ return; // Not in heap
660   660  
HITCBC 661   8770 if (index == heap_.size() - 1) 661   6001 if (index == heap_.size() - 1)
662   { 662   {
663   // Last element, just pop 663   // Last element, just pop
HITCBC 664   1630 impl.heap_index_.store( 664   1617 impl.heap_index_.store(
665   (std::numeric_limits<std::size_t>::max)(), 665   (std::numeric_limits<std::size_t>::max)(),
666   std::memory_order_relaxed); 666   std::memory_order_relaxed);
HITCBC 667   1630 heap_.pop_back(); 667   1617 heap_.pop_back();
668   } 668   }
669   else 669   else
670   { 670   {
671   // Swap with last and reheapify 671   // Swap with last and reheapify
HITCBC 672   7140 swap_heap(index, heap_.size() - 1); 672   4384 swap_heap(index, heap_.size() - 1);
HITCBC 673   7140 impl.heap_index_.store( 673   4384 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   7140 heap_.pop_back(); 676   4384 heap_.pop_back();
677   677  
HITCBC 678   7140 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 678   4384 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   7136 down_heap(index); 681   4384 down_heap(index);
682   } 682   }
683   } 683   }
684   684  
685   inline void 685   inline void
HITCBC 686   8800 timer_service::up_heap(std::size_t index) 686   6027 timer_service::up_heap(std::size_t index)
687   { 687   {
HITCBC 688   15635 while (index > 0) 688   10372 while (index > 0)
689   { 689   {
HITCBC 690   7505 std::size_t parent = (index - 1) / 2; 690   4535 std::size_t parent = (index - 1) / 2;
HITCBC 691   7505 if (!(heap_[index].time_ < heap_[parent].time_)) 691   4535 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 692   670 break; 692   190 break;
HITCBC 693   6835 swap_heap(index, parent); 693   4345 swap_heap(index, parent);
HITCBC 694   6835 index = parent; 694   4345 index = parent;
695   } 695   }
HITCBC 696   8800 } 696   6027 }
697   697  
698   inline void 698   inline void
HITCBC 699   7136 timer_service::down_heap(std::size_t index) 699   4384 timer_service::down_heap(std::size_t index)
700   { 700   {
HITCBC 701   7136 std::size_t child = index * 2 + 1; 701   4384 std::size_t child = index * 2 + 1;
HITCBC 702   8210 while (child < heap_.size()) 702   4425 while (child < heap_.size())
703   { 703   {
HITCBC 704   1140 std::size_t min_child = (child + 1 == heap_.size() || 704   52 std::size_t min_child = (child + 1 == heap_.size() ||
HITCBC 705   1108 heap_[child].time_ < heap_[child + 1].time_) 705   40 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 706   2248 ? child 706   92 ? child
HITCBC 707   1140 : child + 1; 707   52 : child + 1;
708   708  
HITCBC 709   1140 if (heap_[index].time_ < heap_[min_child].time_) 709   52 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 710   66 break; 710   11 break;
711   711  
HITCBC 712   1074 swap_heap(index, min_child); 712   41 swap_heap(index, min_child);
HITCBC 713   1074 index = min_child; 713   41 index = min_child;
HITCBC 714   1074 child = index * 2 + 1; 714   41 child = index * 2 + 1;
715   } 715   }
HITCBC 716   7136 } 716   4384 }
717   717  
718   inline void 718   inline void
HITCBC 719   15049 timer_service::swap_heap(std::size_t i1, std::size_t i2) 719   8770 timer_service::swap_heap(std::size_t i1, std::size_t i2)
720   { 720   {
HITCBC 721   15049 heap_entry tmp = heap_[i1]; 721   8770 heap_entry tmp = heap_[i1];
HITCBC 722   15049 heap_[i1] = heap_[i2]; 722   8770 heap_[i1] = heap_[i2];
HITCBC 723   15049 heap_[i2] = tmp; 723   8770 heap_[i2] = tmp;
HITCBC 724   15049 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 724   8770 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 725   15049 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 725   8770 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 726   15049 } 726   8770 }
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   1370 get_timer_service(capy::execution_context& ctx, scheduler& sched)
764   { 764   {
HITCBC 765   1227 return ctx.make_service<timer_service>(sched); 765   1370 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