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