. /include/boost/corosio /detail /timer_service.hpp
95.63% Lines (241/252) 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   dispatching 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   932 callback() = default; 125   925 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   928 callback(void* ctx, void (*fn)(void*)) noexcept : ctx_(ctx), fn_(fn) {} 128   920 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   8082 void operator()() const 137   7931 void operator()() const
138   { 138   {
HITCBC 139   8082 if (fn_) 139   7931 if (fn_)
HITCBC 140   8082 fn_(ctx_); 140   7931 fn_(ctx_);
HITCBC 141   8082 } 141   7931 }
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   bool shutting_down_ = false; 158   bool shutting_down_ = false;
159   // Set once the scheduler waits on this service; read without the 159   // Set once the scheduler waits on this service; read without the
160   // mutex by every timer construction after the first. 160   // mutex by every timer construction after the first.
161   std::atomic<bool> attached_{false}; 161   std::atomic<bool> attached_{false};
162   162  
163   // Cancellers that claimed a waiter and have yet to post it; 163   // Cancellers that claimed a waiter and have yet to post it;
164   // shutdown waits them out so the scheduler's drain finds the post. 164   // shutdown waits them out so the scheduler's drain finds the post.
165   std::size_t cancels_posting_ = 0; // guarded by mutex_ 165   std::size_t cancels_posting_ = 0; // guarded by mutex_
166   // Avoids mutex in nearest_expiry() and empty() 166   // Avoids mutex in nearest_expiry() and empty()
167   mutable std::atomic<std::int64_t> cached_nearest_ns_{ 167   mutable std::atomic<std::int64_t> cached_nearest_ns_{
168   (std::numeric_limits<std::int64_t>::max)()}; 168   (std::numeric_limits<std::int64_t>::max)()};
169   BOOST_COROSIO_MSVC_WARNING_POP 169   BOOST_COROSIO_MSVC_WARNING_POP
170   170  
171   public: 171   public:
172   /** Construct the timer service for a context's scheduler. 172   /** Construct the timer service for a context's scheduler.
173   173  
174   Created with the context's first timer. It does not attach to 174   Created with the context's first timer. It does not attach to
175   the scheduler here: a concurrent first use may construct a 175   the scheduler here: a concurrent first use may construct a
176   second service that the context then discards. See 176   second service that the context then discards. See
177   @ref attach. 177   @ref attach.
178   178  
179   @throws std::logic_error if the context has no scheduler. 179   @throws std::logic_error if the context has no scheduler.
180   */ 180   */
HITCBC 181   932 inline explicit timer_service(capy::execution_context& ctx) 181   925 inline explicit timer_service(capy::execution_context& ctx)
HITCBC 182   932 : sched_(ctx.find_service<scheduler>()) 182   925 : sched_(ctx.find_service<scheduler>())
183   { 183   {
HITCBC 184   932 if (!sched_) 184   925 if (!sched_)
HITCBC 185   4 detail::throw_logic_error( 185   4 detail::throw_logic_error(
186   "timer_service: the context has no scheduler"); 186   "timer_service: the context has no scheduler");
HITCBC 187   944 } 187   937 }
188   188  
189   /// Return the associated scheduler. 189   /// Return the associated scheduler.
HITCBC 190   35319 inline scheduler& get_scheduler() noexcept 190   33737 inline scheduler& get_scheduler() noexcept
191   { 191   {
HITCBC 192   35319 return *sched_; 192   33737 return *sched_;
193   } 193   }
194   194  
195   /// Destroy the timer service, detaching it from the scheduler. 195   /// Destroy the timer service, detaching it from the scheduler.
HITCBC 196   1856 ~timer_service() override 196   1842 ~timer_service() override
HITCBC 197   928 { 197   921 {
HITCBC 198   928 if (attached_.load(std::memory_order_acquire)) 198   921 if (attached_.load(std::memory_order_acquire))
HITCBC 199   928 sched_->detach_timer_service(); 199   920 sched_->detach_timer_service();
HITCBC 200   1856 } 200   1842 }
201   201  
202   /** Attach this service to the scheduler, if not yet attached. 202   /** Attach this service to the scheduler, if not yet attached.
203   203  
204   Call once the context has settled which service it keeps; no 204   Call once the context has settled which service it keeps; no
205   timer of this service can wait before this returns. 205   timer of this service can wait before this returns.
206   206  
207   @par Exception Safety 207   @par Exception Safety
208   Strong guarantee: on failure the service stays detached and 208   Strong guarantee: on failure the service stays detached and
209   the next call retries. 209   the next call retries.
210   */ 210   */
HITCBC 211   20216 inline void attach() 211   19416 inline void attach()
212   { 212   {
HITCBC 213   20216 if (attached_.load(std::memory_order_acquire)) 213   19416 if (attached_.load(std::memory_order_acquire))
HITCBC 214   19288 return; 214   18496 return;
HITCBC 215   928 std::lock_guard lock(mutex_); 215   920 std::lock_guard lock(mutex_);
HITCBC 216   928 if (attached_.load(std::memory_order_relaxed)) 216   920 if (attached_.load(std::memory_order_relaxed))
MISUBC 217   ✗ return; 217   ✗ return;
HITCBC 218   928 sched_->attach_timer_service(*this); 218   920 sched_->attach_timer_service(*this);
HITCBC 219   928 attached_.store(true, std::memory_order_release); 219   920 attached_.store(true, std::memory_order_release);
HITCBC 220   928 } 220   920 }
221   221  
222   timer_service(timer_service const&) = delete; 222   timer_service(timer_service const&) = delete;
223   timer_service& operator=(timer_service const&) = delete; 223   timer_service& operator=(timer_service const&) = delete;
224   224  
225   /// Register a callback invoked when the earliest expiry changes. 225   /// Register a callback invoked when the earliest expiry changes.
HITCBC 226   928 inline void set_on_earliest_changed(callback cb) 226   920 inline void set_on_earliest_changed(callback cb)
227   { 227   {
HITCBC 228   928 on_earliest_changed_ = cb; 228   920 on_earliest_changed_ = cb;
HITCBC 229   928 } 229   920 }
230   230  
231   /// Return true if no timers are in the heap. 231   /// Return true if no timers are in the heap.
232   inline bool empty() const noexcept 232   inline bool empty() const noexcept
233   { 233   {
234   return cached_nearest_ns_.load(std::memory_order_acquire) == 234   return cached_nearest_ns_.load(std::memory_order_acquire) ==
235   (std::numeric_limits<std::int64_t>::max)(); 235   (std::numeric_limits<std::int64_t>::max)();
236   } 236   }
237   237  
238   /// Return the nearest timer expiry without acquiring the mutex. 238   /// Return the nearest timer expiry without acquiring the mutex.
HITCBC 239   18994 inline time_point nearest_expiry() const noexcept 239   18068 inline time_point nearest_expiry() const noexcept
240   { 240   {
HITCBC 241   18994 auto ns = cached_nearest_ns_.load(std::memory_order_acquire); 241   18068 auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
HITCBC 242   18994 return time_point(time_point::duration(ns)); 242   18068 return time_point(time_point::duration(ns));
243   } 243   }
244   244  
245   /// Cancel all pending timers and free cached resources. 245   /// Cancel all pending timers and free cached resources.
246   inline void shutdown() override; 246   inline void shutdown() override;
247   247  
248   /// Construct a new timer implementation. 248   /// Construct a new timer implementation.
249   inline io_object::implementation* construct() override; 249   inline io_object::implementation* construct() override;
250   250  
251   /// Destroy a timer implementation, cancelling pending waiters. 251   /// Destroy a timer implementation, cancelling pending waiters.
252   inline void destroy(io_object::implementation* p) override; 252   inline void destroy(io_object::implementation* p) override;
253   253  
254   /// Cancel and recycle a timer implementation. 254   /// Cancel and recycle a timer implementation.
255   inline void destroy_impl(timer::implementation& impl); 255   inline void destroy_impl(timer::implementation& impl);
256   256  
257   /// Publish the timer's waiter and insert the timer into the heap. 257   /// Publish the timer's waiter and insert the timer into the heap.
258   inline void insert_waiter(timer::implementation& impl, waiter_node* w); 258   inline void insert_waiter(timer::implementation& impl, waiter_node* w);
259   259  
260   /// Cancel the timer's published waiter, if any. 260   /// Cancel the timer's published waiter, if any.
261   inline void cancel_timer(timer::implementation& impl); 261   inline void cancel_timer(timer::implementation& impl);
262   262  
263   /// Cancel one specific waiter ( stop_token callback path ). 263   /// Cancel one specific waiter ( stop_token callback path ).
264   inline void cancel_waiter(waiter_node* w); 264   inline void cancel_waiter(waiter_node* w);
265   265  
266   /// Complete all waiters whose timers have expired. 266   /// Complete all waiters whose timers have expired.
267   inline std::size_t process_expired(); 267   inline std::size_t process_expired();
268   268  
269   private: 269   private:
HITCBC 270   63363 inline void refresh_cached_nearest() noexcept 270   62271 inline void refresh_cached_nearest() noexcept
271   { 271   {
HITCBC 272   63363 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)() 272   62271 auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
HITCBC 273   60039 : heap_[0].time_.time_since_epoch().count(); 273   59125 : heap_[0].time_.time_since_epoch().count();
HITCBC 274   63363 cached_nearest_ns_.store(ns, std::memory_order_release); 274   62271 cached_nearest_ns_.store(ns, std::memory_order_release);
HITCBC 275   63363 } 275   62271 }
276   276  
277   inline void remove_timer_impl(timer::implementation& impl); 277   inline void remove_timer_impl(timer::implementation& impl);
278   inline void up_heap(std::size_t index); 278   inline void up_heap(std::size_t index);
279   inline void down_heap(std::size_t index); 279   inline void down_heap(std::size_t index);
280   inline void swap_heap(std::size_t i1, std::size_t i2); 280   inline void swap_heap(std::size_t i1, std::size_t i2);
281   }; 281   };
282   282  
283   // Thread-local single-slot impl cache, validated by comparing svc_. 283   // Thread-local single-slot impl cache, validated by comparing svc_.
284   // Keeps a hot impl out of the shared free list; both sides still 284   // 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. 285   // take the pool lock to move it in and out of live tracking.
286   // Cleared by timer_service_invalidate_cache() during shutdown. 286   // Cleared by timer_service_invalidate_cache() during shutdown.
287   287  
288   inline thread_local_ptr<timer::implementation> tl_cached_impl; 288   inline thread_local_ptr<timer::implementation> tl_cached_impl;
289   289  
290   // The POD TLS slot above never runs destructors, so a short-lived 290   // The POD TLS slot above never runs destructors, so a short-lived
291   // run() thread would leak its cached impl. Each push arms this 291   // run() thread would leak its cached impl. Each push arms this
292   // owner, whose destructor frees the slot at thread exit. A cached 292   // owner, whose destructor frees the slot at thread exit. A cached
293   // entry is a quiescent heap object (nothing in the heap or free 293   // 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 294   // list) and deletion touches no service state, so it is safe after
295   // the owning service is gone (the stale-entry path in 295   // the owning service is gone (the stale-entry path in
296   // try_pop_tl_cache deletes the same way). 296   // try_pop_tl_cache deletes the same way).
297   struct tl_cache_owner 297   struct tl_cache_owner
298   { 298   {
HITCBC 299   63 ~tl_cache_owner() 299   48 ~tl_cache_owner()
300   { 300   {
HITCBC 301   63 delete tl_cached_impl.get(); 301   48 delete tl_cached_impl.get();
HITCBC 302   63 tl_cached_impl.set(nullptr); 302   48 tl_cached_impl.set(nullptr);
HITCBC 303   63 } 303   48 }
304   }; 304   };
305   305  
306   inline void 306   inline void
HITCBC 307   15125 arm_tl_cache_cleanup() noexcept 307   15104 arm_tl_cache_cleanup() noexcept
308   { 308   {
HITCBC 309   15125 [[maybe_unused]] thread_local tl_cache_owner owner; 309   15104 [[maybe_unused]] thread_local tl_cache_owner owner;
HITCBC 310   15125 } 310   15104 }
311   311  
312   inline timer::implementation* 312   inline timer::implementation*
HITCBC 313   20216 try_pop_tl_cache(timer_service* svc) noexcept 313   19416 try_pop_tl_cache(timer_service* svc) noexcept
314   { 314   {
HITCBC 315   20216 auto* impl = tl_cached_impl.get(); 315   19416 auto* impl = tl_cached_impl.get();
HITCBC 316   20216 if (impl) 316   19416 if (impl)
317   { 317   {
HITCBC 318   14611 tl_cached_impl.set(nullptr); 318   14605 tl_cached_impl.set(nullptr);
HITCBC 319   14611 if (impl->svc_ == svc) 319   14605 if (impl->svc_ == svc)
HITCBC 320   14611 return impl; 320   14605 return impl;
321   // Stale impl from a destroyed service 321   // Stale impl from a destroyed service
MISUBC 322   ✗ delete impl; 322   ✗ delete impl;
323   } 323   }
HITCBC 324   5605 return nullptr; 324   4811 return nullptr;
325   } 325   }
326   326  
327   inline bool 327   inline bool
HITCBC 328   16965 try_push_tl_cache(timer::implementation* impl) noexcept 328   16165 try_push_tl_cache(timer::implementation* impl) noexcept
329   { 329   {
HITCBC 330   16965 if (!tl_cached_impl.get()) 330   16165 if (!tl_cached_impl.get())
331   { 331   {
HITCBC 332   15125 arm_tl_cache_cleanup(); 332   15104 arm_tl_cache_cleanup();
HITCBC 333   15125 tl_cached_impl.set(impl); 333   15104 tl_cached_impl.set(impl);
HITCBC 334   15125 return true; 334   15104 return true;
335   } 335   }
HITCBC 336   1840 return false; 336   1061 return false;
337   } 337   }
338   338  
339   inline void 339   inline void
HITCBC 340   928 timer_service_invalidate_cache() noexcept 340   920 timer_service_invalidate_cache() noexcept
341   { 341   {
HITCBC 342   928 delete tl_cached_impl.get(); 342   920 delete tl_cached_impl.get();
HITCBC 343   928 tl_cached_impl.set(nullptr); 343   920 tl_cached_impl.set(nullptr);
HITCBC 344   928 } 344   920 }
345   345  
346   // timer_service out-of-class member function definitions 346   // timer_service out-of-class member function definitions
347   347  
348   inline void 348   inline void
HITCBC 349   928 timer_service::shutdown() 349   920 timer_service::shutdown()
350   { 350   {
HITCBC 351   928 timer_service_invalidate_cache(); 351   920 timer_service_invalidate_cache();
HITCBC 352   928 shutting_down_ = true; 352   920 shutting_down_ = true;
353   // Flag only; the real drain walks the expiry heap below, not 353   // 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. 354   // object_pool's live_ list, so the visit callback is a no-op.
HITCBC 355   928 pool_.shutdown([](timer::implementation*) {}); 355   920 pool_.shutdown([](timer::implementation*) {});
356   356  
357   // Snapshot impls and detach them from the heap so that 357   // Snapshot impls and detach them from the heap so that
358   // coroutine-owned timer destructors (run by the unwinds the 358   // coroutine-owned timer destructors (run by the unwinds the
359   // abandons below start) cannot re-enter remove_timer_impl() and 359   // abandons below start) cannot re-enter remove_timer_impl() and
360   // mutate the vector during iteration. A stop requested on another thread 360   // mutate the vector during iteration. A stop requested on another thread
361   // reaches cancel_waiter() under the same lock: whichever side 361   // reaches cancel_waiter() under the same lock: whichever side
362   // claims a waiter first owns it, and a waiter its canceller 362   // claims a waiter first owns it, and a waiter its canceller
363   // claimed is posted, so the scheduler's drain abandons it. 363   // claimed is posted, so the scheduler's drain abandons it.
HITCBC 364   928 std::vector<timer::implementation*> impls; 364   920 std::vector<timer::implementation*> impls;
HITCBC 365   928 std::vector<waiter_node*> waiters; 365   920 std::vector<waiter_node*> waiters;
366   { 366   {
HITCBC 367   928 std::lock_guard lock(mutex_); 367   920 std::lock_guard lock(mutex_);
HITCBC 368   928 impls.reserve(heap_.size()); 368   920 impls.reserve(heap_.size());
HITCBC 369   928 waiters.reserve(heap_.size()); 369   920 waiters.reserve(heap_.size());
HITCBC 370   4175 for (auto& entry : heap_) 370   4159 for (auto& entry : heap_)
371   { 371   {
HITCBC 372   3247 entry.timer_->heap_index_.store( 372   3239 entry.timer_->heap_index_.store(
373   (std::numeric_limits<std::size_t>::max)(), 373   (std::numeric_limits<std::size_t>::max)(),
374   std::memory_order_relaxed); 374   std::memory_order_relaxed);
HITCBC 375   3247 impls.push_back(entry.timer_); 375   3239 impls.push_back(entry.timer_);
HITCBC 376   3247 if (auto* w = std::exchange(entry.timer_->waiter_, nullptr)) 376   3239 if (auto* w = std::exchange(entry.timer_->waiter_, nullptr))
377   { 377   {
HITCBC 378   3247 w->impl_ = nullptr; 378   3239 w->impl_ = nullptr;
HITCBC 379   3247 waiters.push_back(w); 379   3239 waiters.push_back(w);
380   } 380   }
381   } 381   }
HITCBC 382   928 heap_.clear(); 382   920 heap_.clear();
HITCBC 383   928 cached_nearest_ns_.store( 383   920 cached_nearest_ns_.store(
384   (std::numeric_limits<std::int64_t>::max)(), 384   (std::numeric_limits<std::int64_t>::max)(),
385   std::memory_order_release); 385   std::memory_order_release);
HITCBC 386   928 } 386   920 }
387   387  
388   // A stop on another thread may have claimed its waiter before the 388   // A stop on another thread may have claimed its waiter before the
389   // pass above and still be posting it; the scheduler drains next, 389   // pass above and still be posting it; the scheduler drains next,
390   // and must find that post. 390   // and must find that post.
391   for (;;) 391   for (;;)
392   { 392   {
393   { 393   {
HITCBC 394   928 std::lock_guard lock(mutex_); 394   920 std::lock_guard lock(mutex_);
HITCBC 395   928 if (cancels_posting_ == 0) 395   920 if (cancels_posting_ == 0)
HITCBC 396   928 break; 396   920 break;
HITCBC 397   928 } 397   920 }
MISUBC 398   ✗ std::this_thread::yield(); 398   ✗ std::this_thread::yield();
MISUBC 399   ✗ } 399   ✗ }
400   400  
401   // Cancel waiting timers. Each waiter called work_started() 401   // Cancel waiting timers. Each waiter called work_started()
402   // in implementation::wait(); a waiter given up here never 402   // in implementation::wait(); a waiter given up here never
403   // completes, so its work is finished here to keep the count 403   // completes, so its work is finished here to keep the count
404   // balanced. Resetting the stop callback outside the lock 404   // balanced. Resetting the stop callback outside the lock
405   // waits out a canceller already running, which finds the waiter 405   // waits out a canceller already running, which finds the waiter
406   // claimed. 406   // claimed.
HITCBC 407   4175 for (auto* w : waiters) 407   4159 for (auto* w : waiters)
408   { 408   {
HITCBC 409   3247 w->reset_stop_cb(); 409   3239 w->reset_stop_cb();
HITCBC 410   3247 auto c = std::exchange(w->cont_, {}); 410   3239 auto c = std::exchange(w->cont_, {});
HITCBC 411   3247 sched_->work_finished(); 411   3239 sched_->work_finished();
412   // Unwinding the frame also ends the node's storage 412   // Unwinding the frame also ends the node's storage
HITCBC 413   3247 if (c.h) 413   3239 if (c.h)
HITCBC 414   3247 capy::abandon(c); 414   3239 capy::abandon(c);
415   } 415   }
416   416  
HITCBC 417   4175 for (auto* impl : impls) 417   4159 for (auto* impl : impls)
418   { 418   {
419   // Unlink from the pool's live_ list before the direct delete 419   // Unlink from the pool's live_ list before the direct delete
420   // below, or ~object_pool()'s unconditional sweep would delete 420   // below, or ~object_pool()'s unconditional sweep would delete
421   // this impl a second time. 421   // this impl a second time.
HITCBC 422   3247 [[maybe_unused]] bool const removed = pool_.remove(impl); 422   3239 [[maybe_unused]] bool const removed = pool_.remove(impl);
HITCBC 423   3247 BOOST_COROSIO_ASSERT(removed); 423   3239 BOOST_COROSIO_ASSERT(removed);
HITCBC 424   3247 delete impl; 424   3239 delete impl;
425   } 425   }
426   426  
427   // Anything still parked in pool_ (free-listed or live with no 427   // Anything still parked in pool_ (free-listed or live with no
428   // pending wait at shutdown) is freed by object_pool's own destructor. 428   // pending wait at shutdown) is freed by object_pool's own destructor.
HITCBC 429   928 } 429   920 }
430   430  
431   inline io_object::implementation* 431   inline io_object::implementation*
HITCBC 432   20216 timer_service::construct() 432   19416 timer_service::construct()
433   { 433   {
HITCBC 434   20216 timer::implementation* impl = try_pop_tl_cache(this); 434   19416 timer::implementation* impl = try_pop_tl_cache(this);
HITCBC 435   20216 if (impl) 435   19416 if (impl)
436   { 436   {
HITCBC 437   14611 impl->svc_ = this; 437   14605 impl->svc_ = this;
HITCBC 438   14611 impl->reuse(); 438   14605 impl->reuse();
HITCBC 439   14611 impl->refs_.store(1, std::memory_order_relaxed); 439   14605 impl->refs_.store(1, std::memory_order_relaxed);
440   // The TL push that parked impl here also removed it from 440   // The TL push that parked impl here also removed it from
441   // live_ (see destroy_impl) — re-adopt it now that it is live 441   // live_ (see destroy_impl) — re-adopt it now that it is live
442   // again. 442   // again.
HITCBC 443   14611 pool_.adopt(impl); 443   14605 pool_.adopt(impl);
HITCBC 444   14611 return impl; 444   14605 return impl;
445   } 445   }
446   446  
HITCBC 447   5605 return pool_.acquire(*this); 447   4811 return pool_.acquire(*this);
448   } 448   }
449   449  
450   inline void 450   inline void
HITCBC 451   20216 timer_service::destroy(io_object::implementation* p) 451   19416 timer_service::destroy(io_object::implementation* p)
452   { 452   {
453   // During shutdown the drain loop owns every impl and deletes 453   // During shutdown the drain loop owns every impl and deletes
454   // them directly. A frame destroyed by that loop can unwind a 454   // them directly. A frame destroyed by that loop can unwind a
455   // handle whose impl was freed in an earlier iteration (a 455   // handle whose impl was freed in an earlier iteration (a
456   // timeout's parent frame owns the timeout timer while 456   // timeout's parent frame owns the timeout timer while
457   // suspended on the inner delay's timer), so bail out before 457   // suspended on the inner delay's timer), so bail out before
458   // even downcasting the pointer. 458   // even downcasting the pointer.
HITCBC 459   20216 if (shutting_down_) 459   19416 if (shutting_down_)
HITCBC 460   3251 return; 460   3251 return;
HITCBC 461   16965 destroy_impl(static_cast<timer::implementation&>(*p)); 461   16165 destroy_impl(static_cast<timer::implementation&>(*p));
462   } 462   }
463   463  
464   inline void 464   inline void
HITCBC 465   16965 timer_service::destroy_impl(timer::implementation& impl) 465   16165 timer_service::destroy_impl(timer::implementation& impl)
466   { 466   {
467   // During shutdown the impl is owned by the shutdown loop. 467   // During shutdown the impl is owned by the shutdown loop.
468   // Re-entering here (from a coroutine-owned timer destructor 468   // Re-entering here (from a coroutine-owned timer destructor
469   // triggered by h.destroy()) must not modify the heap or 469   // triggered by h.destroy()) must not modify the heap or
470   // recycle the impl — shutdown deletes it directly. 470   // recycle the impl — shutdown deletes it directly.
HITCBC 471   16965 if (shutting_down_) 471   16165 if (shutting_down_)
MISUBC 472   ✗ return; 472   ✗ return;
473   473  
HITCBC 474   16965 cancel_timer(impl); 474   16165 cancel_timer(impl);
475   475  
HITCBC 476   33930 if (impl.heap_index_.load(std::memory_order_relaxed) != 476   32330 if (impl.heap_index_.load(std::memory_order_relaxed) !=
HITCBC 477   16965 (std::numeric_limits<std::size_t>::max)()) 477   16165 (std::numeric_limits<std::size_t>::max)())
478   { 478   {
MISUBC 479   ✗ std::lock_guard lock(mutex_); 479   ✗ std::lock_guard lock(mutex_);
MISUBC 480   ✗ remove_timer_impl(impl); 480   ✗ remove_timer_impl(impl);
MISUBC 481   ✗ refresh_cached_nearest(); 481   ✗ refresh_cached_nearest();
MISUBC 482   ✗ } 482   ✗ }
483   483  
HITCBC 484   16965 if (try_push_tl_cache(&impl)) 484   16165 if (try_push_tl_cache(&impl))
485   { 485   {
486   // The TL slot takes sole ownership: it is deleted directly by 486   // The TL slot takes sole ownership: it is deleted directly by
487   // tl_cache_owner / the stale-service path, never through this 487   // tl_cache_owner / the stale-service path, never through this
488   // pool, so it must leave live_ now or ~object_pool() would see 488   // pool, so it must leave live_ now or ~object_pool() would see
489   // it as abandoned (and, at the wrong moment, double-delete it 489   // it as abandoned (and, at the wrong moment, double-delete it
490   // after a later construct() re-adopts it). 490   // after a later construct() re-adopts it).
HITCBC 491   15125 [[maybe_unused]] bool const removed = pool_.remove(&impl); 491   15104 [[maybe_unused]] bool const removed = pool_.remove(&impl);
HITCBC 492   15125 BOOST_COROSIO_ASSERT(removed); 492   15104 BOOST_COROSIO_ASSERT(removed);
HITCBC 493   15125 return; 493   15104 return;
494   } 494   }
495   495  
496   // No op keepalives on a timer impl: this is the only reference, 496   // No op keepalives on a timer impl: this is the only reference,
497   // so release() always recycles immediately via retire(). 497   // so release() always recycles immediately via retire().
HITCBC 498   1840 release(&impl); 498   1061 release(&impl);
499   } 499   }
500   500  
501   inline void 501   inline void
HITCBC 502   24398 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w) 502   22622 timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
503   { 503   {
HITCBC 504   24398 bool notify = false; 504   22622 bool notify = false;
HITCBC 505   24398 bool lost_cancel = false; 505   22622 bool lost_cancel = false;
506   { 506   {
HITCBC 507   24398 std::lock_guard lock(mutex_); 507   22622 std::lock_guard lock(mutex_);
508   // Grow before publishing anything, so the push_back below 508   // Grow before publishing anything, so the push_back below
509   // cannot throw: a failure here leaves the waiter untouched, 509   // cannot throw: a failure here leaves the waiter untouched,
510   // the strong guarantee rearm_wait's recovery relies on. 510   // the strong guarantee rearm_wait's recovery relies on.
HITCBC 511   24398 if (impl.heap_index_.load(std::memory_order_relaxed) == 511   22622 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 512   48796 (std::numeric_limits<std::size_t>::max)() && 512   45244 (std::numeric_limits<std::size_t>::max)() &&
HITCBC 513   24398 heap_.size() == heap_.capacity()) 513   22622 heap_.size() == heap_.capacity())
HITCBC 514   950 heap_.reserve(heap_.capacity() == 0 ? 16 : 2 * heap_.capacity()); 514   921 heap_.reserve(heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
515   // Publish: from here the waiter is visible to the fire path and 515   // Publish: from here the waiter is visible to the fire path and
516   // to its own stop callback (impl_ non-null enables cancel_waiter). 516   // to its own stop callback (impl_ non-null enables cancel_waiter).
HITCBC 517   24398 w->impl_ = &impl; 517   22622 w->impl_ = &impl;
HITCBC 518   48796 if (impl.heap_index_.load(std::memory_order_relaxed) == 518   45244 if (impl.heap_index_.load(std::memory_order_relaxed) ==
HITCBC 519   24398 (std::numeric_limits<std::size_t>::max)()) 519   22622 (std::numeric_limits<std::size_t>::max)())
520   { 520   {
HITCBC 521   24398 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed); 521   22622 impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
HITCBC 522   24398 heap_.push_back({impl.expiry_, &impl}); 522   22622 heap_.push_back({impl.expiry_, &impl});
HITCBC 523   24398 up_heap(heap_.size() - 1); 523   22622 up_heap(heap_.size() - 1);
HITCBC 524   24398 notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0); 524   22622 notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0);
HITCBC 525   24398 refresh_cached_nearest(); 525   22622 refresh_cached_nearest();
526   } 526   }
HITCBC 527   24398 BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr); 527   22622 BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
HITCBC 528   24398 impl.waiter_ = w; 528   22622 impl.waiter_ = w;
529   529  
530   // Lost-cancel re-check: a stop requested after the canceller was 530   // Lost-cancel re-check: a stop requested after the canceller was
531   // armed in wait() but before this publication found impl_ null 531   // armed in wait() but before this publication found impl_ null
532   // and returned a no-op. Observe it now and undo the insertion. 532   // and returned a no-op. Observe it now and undo the insertion.
HITCBC 533   24398 if (w->token_->stop_requested()) 533   22622 if (w->token_->stop_requested())
534   { 534   {
HITCBC 535   263 w->impl_ = nullptr; 535   1 w->impl_ = nullptr;
HITCBC 536   263 impl.waiter_ = nullptr; 536   1 impl.waiter_ = nullptr;
HITCBC 537   263 remove_timer_impl(impl); 537   1 remove_timer_impl(impl);
HITCBC 538   263 impl.might_have_pending_waits_.store( 538   1 impl.might_have_pending_waits_.store(
539   false, std::memory_order_release); 539   false, std::memory_order_release);
HITCBC 540   263 refresh_cached_nearest(); 540   1 refresh_cached_nearest();
HITCBC 541   263 lost_cancel = true; 541   1 lost_cancel = true;
HITCBC 542   263 notify = false; // insertion undone; nearest unchanged 542   1 notify = false; // insertion undone; nearest unchanged
543   } 543   }
HITCBC 544   24398 } 544   22622 }
HITCBC 545   24398 if (notify) 545   22622 if (notify)
HITCBC 546   8082 on_earliest_changed_(); 546   7931 on_earliest_changed_();
HITCBC 547   24398 if (lost_cancel) 547   22622 if (lost_cancel)
548   { 548   {
HITCBC 549   263 w->ec_ = make_error_code(capy::error::canceled); 549   1 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 550   263 sched_->post(&w->op_); 550   1 sched_->post(&w->op_);
551   } 551   }
HITCBC 552   24398 } 552   22622 }
553   553  
554   inline void 554   inline void
HITCBC 555   16965 timer_service::cancel_timer(timer::implementation& impl) 555   16165 timer_service::cancel_timer(timer::implementation& impl)
556   { 556   {
557   // Acquire pairs with the drains' release: a caller that skips the 557   // 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 558   // lock may recycle the impl next, so the drain's writes to it must
559   // happen before. 559   // happen before.
HITCBC 560   16965 if (!impl.might_have_pending_waits_.load(std::memory_order_acquire)) 560   16165 if (!impl.might_have_pending_waits_.load(std::memory_order_acquire))
HITCBC 561   16963 return; 561   16163 return;
562   562  
563   // No unlocked already-done fast-out here: it would need the 563   // No unlocked already-done fast-out here: it would need the
564   // non-atomic waiter_ (a race with concurrent drains), and an 564   // non-atomic waiter_ (a race with concurrent drains), and an
565   // index-only check is lifetime-unsafe because npos is stored 565   // index-only check is lifetime-unsafe because npos is stored
566   // before the drain finishes touching the impl. A stale-true 566   // before the drain finishes touching the impl. A stale-true
567   // flag is rare with the stateless API; the locked path below 567   // flag is rare with the stateless API; the locked path below
568   // re-validates. 568   // re-validates.
569   569  
HITCBC 570   2 waiter_node* canceled = nullptr; 570   2 waiter_node* canceled = nullptr;
571   571  
572   { 572   {
HITCBC 573   2 std::lock_guard lock(mutex_); 573   2 std::lock_guard lock(mutex_);
HITCBC 574   2 remove_timer_impl(impl); 574   2 remove_timer_impl(impl);
HITCBC 575   2 canceled = std::exchange(impl.waiter_, nullptr); 575   2 canceled = std::exchange(impl.waiter_, nullptr);
HITCBC 576   2 if (canceled) 576   2 if (canceled)
HITCBC 577   2 canceled->impl_ = nullptr; 577   2 canceled->impl_ = nullptr;
578   // Store false as the final touch of the impl under the lock so 578   // Store false as the final touch of the impl under the lock so
579   // a pre-lock false-flag check trusts it unqualified. 579   // a pre-lock false-flag check trusts it unqualified.
HITCBC 580   2 impl.might_have_pending_waits_.store(false, std::memory_order_release); 580   2 impl.might_have_pending_waits_.store(false, std::memory_order_release);
HITCBC 581   2 refresh_cached_nearest(); 581   2 refresh_cached_nearest();
HITCBC 582   2 } 582   2 }
583   583  
HITCBC 584   2 if (canceled) 584   2 if (canceled)
585   { 585   {
HITCBC 586   2 canceled->ec_ = make_error_code(capy::error::canceled); 586   2 canceled->ec_ = make_error_code(capy::error::canceled);
HITCBC 587   2 sched_->post(&canceled->op_); 587   2 sched_->post(&canceled->op_);
588   } 588   }
589   } 589   }
590   590  
591   inline void 591   inline void
HITCBC 592   2677 timer_service::cancel_waiter(waiter_node* w) 592   1753 timer_service::cancel_waiter(waiter_node* w)
593   { 593   {
594   { 594   {
HITCBC 595   2677 std::lock_guard lock(mutex_); 595   1753 std::lock_guard lock(mutex_);
596   // Already removed by another drain: cancel_timer, 596   // Already removed by another drain: cancel_timer,
597   // process_expired, or insert_waiter's lost-cancel recheck 597   // process_expired, or insert_waiter's lost-cancel recheck
HITCBC 598   2677 if (!w->impl_) 598   1753 if (!w->impl_)
HITCBC 599   688 return; 599   169 return;
HITCBC 600   1989 auto* impl = w->impl_; 600   1584 auto* impl = w->impl_;
HITCBC 601   1989 w->impl_ = nullptr; 601   1584 w->impl_ = nullptr;
HITCBC 602   1989 impl->waiter_ = nullptr; 602   1584 impl->waiter_ = nullptr;
HITCBC 603   1989 remove_timer_impl(*impl); 603   1584 remove_timer_impl(*impl);
HITCBC 604   1989 impl->might_have_pending_waits_.store(false, std::memory_order_release); 604   1584 impl->might_have_pending_waits_.store(false, std::memory_order_release);
HITCBC 605   1989 refresh_cached_nearest(); 605   1584 refresh_cached_nearest();
HITCBC 606   1989 ++cancels_posting_; 606   1584 ++cancels_posting_;
HITCBC 607   2677 } 607   1753 }
608   608  
HITCBC 609   1989 w->ec_ = make_error_code(capy::error::canceled); 609   1584 w->ec_ = make_error_code(capy::error::canceled);
HITCBC 610   1989 sched_->post(&w->op_); 610   1584 sched_->post(&w->op_);
611   611  
HITCBC 612   1989 std::lock_guard lock(mutex_); 612   1584 std::lock_guard lock(mutex_);
HITCBC 613   1989 --cancels_posting_; 613   1584 --cancels_posting_;
HITCBC 614   1989 } 614   1584 }
615   615  
616   inline std::size_t 616   inline std::size_t
HITCBC 617   36711 timer_service::process_expired() 617   38062 timer_service::process_expired()
618   { 618   {
HITCBC 619   36711 intrusive_list<waiter_node> expired; 619   38062 intrusive_list<waiter_node> expired;
620   620  
621   { 621   {
HITCBC 622   36711 std::lock_guard lock(mutex_); 622   38062 std::lock_guard lock(mutex_);
HITCBC 623   36711 auto now = clock_type::now(); 623   38062 auto now = clock_type::now();
624   624  
HITCBC 625   55608 while (!heap_.empty() && heap_[0].time_ <= now) 625   55858 while (!heap_.empty() && heap_[0].time_ <= now)
626   { 626   {
HITCBC 627   18897 timer::implementation* t = heap_[0].timer_; 627   17796 timer::implementation* t = heap_[0].timer_;
HITCBC 628   18897 remove_timer_impl(*t); 628   17796 remove_timer_impl(*t);
HITCBC 629   18897 if (auto* w = std::exchange(t->waiter_, nullptr)) 629   17796 if (auto* w = std::exchange(t->waiter_, nullptr))
630   { 630   {
HITCBC 631   18897 w->impl_ = nullptr; 631   17796 w->impl_ = nullptr;
HITCBC 632   18897 w->ec_ = {}; 632   17796 w->ec_ = {};
HITCBC 633   18897 expired.push_back(w); 633   17796 expired.push_back(w);
634   } 634   }
HITCBC 635   18897 t->might_have_pending_waits_.store( 635   17796 t->might_have_pending_waits_.store(
636   false, std::memory_order_release); 636   false, std::memory_order_release);
637   } 637   }
638   638  
HITCBC 639   36711 refresh_cached_nearest(); 639   38062 refresh_cached_nearest();
HITCBC 640   36711 } 640   38062 }
641   641  
HITCBC 642   36711 std::size_t count = 0; 642   38062 std::size_t count = 0;
HITCBC 643   55608 while (auto* w = expired.pop_front()) 643   55858 while (auto* w = expired.pop_front())
644   { 644   {
HITCBC 645   18897 sched_->post(&w->op_); 645   17796 sched_->post(&w->op_);
HITCBC 646   18897 ++count; 646   17796 ++count;
HITCBC 647   18897 } 647   17796 }
648   648  
HITCBC 649   36711 return count; 649   38062 return count;
650   } 650   }
651   651  
652   inline void 652   inline void
HITCBC 653   21151 timer_service::remove_timer_impl(timer::implementation& impl) 653   19383 timer_service::remove_timer_impl(timer::implementation& impl)
654   { 654   {
HITCBC 655   21151 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed); 655   19383 std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
HITCBC 656   21151 if (index >= heap_.size()) 656   19383 if (index >= heap_.size())
MISUBC 657   ✗ return; // Not in heap 657   ✗ return; // Not in heap
658   658  
HITCBC 659   21151 if (index == heap_.size() - 1) 659   19383 if (index == heap_.size() - 1)
660   { 660   {
661   // Last element, just pop 661   // Last element, just pop
HITCBC 662   3149 impl.heap_index_.store( 662   2757 impl.heap_index_.store(
663   (std::numeric_limits<std::size_t>::max)(), 663   (std::numeric_limits<std::size_t>::max)(),
664   std::memory_order_relaxed); 664   std::memory_order_relaxed);
HITCBC 665   3149 heap_.pop_back(); 665   2757 heap_.pop_back();
666   } 666   }
667   else 667   else
668   { 668   {
669   // Swap with last and reheapify 669   // Swap with last and reheapify
HITCBC 670   18002 swap_heap(index, heap_.size() - 1); 670   16626 swap_heap(index, heap_.size() - 1);
HITCBC 671   18002 impl.heap_index_.store( 671   16626 impl.heap_index_.store(
672   (std::numeric_limits<std::size_t>::max)(), 672   (std::numeric_limits<std::size_t>::max)(),
673   std::memory_order_relaxed); 673   std::memory_order_relaxed);
HITCBC 674   18002 heap_.pop_back(); 674   16626 heap_.pop_back();
675   675  
HITCBC 676   18002 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_) 676   16626 if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
MISLBC 677   2 up_heap(index); 677   ✗ up_heap(index);
678   else 678   else
HITCBC 679   18000 down_heap(index); 679   16626 down_heap(index);
680   } 680   }
681   } 681   }
682   682  
683   inline void 683   inline void
HITCBC 684   24400 timer_service::up_heap(std::size_t index) 684   22622 timer_service::up_heap(std::size_t index)
685   { 685   {
HITCBC 686   31436 while (index > 0) 686   28884 while (index > 0)
687   { 687   {
HITCBC 688   23232 std::size_t parent = (index - 1) / 2; 688   20952 std::size_t parent = (index - 1) / 2;
HITCBC 689   23232 if (!(heap_[index].time_ < heap_[parent].time_)) 689   20952 if (!(heap_[index].time_ < heap_[parent].time_))
HITCBC 690   16196 break; 690   14690 break;
HITCBC 691   7036 swap_heap(index, parent); 691   6262 swap_heap(index, parent);
HITCBC 692   7036 index = parent; 692   6262 index = parent;
693   } 693   }
HITCBC 694   24400 } 694   22622 }
695   695  
696   inline void 696   inline void
HITCBC 697   18000 timer_service::down_heap(std::size_t index) 697   16626 timer_service::down_heap(std::size_t index)
698   { 698   {
HITCBC 699   18000 std::size_t child = index * 2 + 1; 699   16626 std::size_t child = index * 2 + 1;
HITCBC 700   42508 while (child < heap_.size()) 700   36550 while (child < heap_.size())
701   { 701   {
HITCBC 702   26166 std::size_t min_child = (child + 1 == heap_.size() || 702   22405 std::size_t min_child = (child + 1 == heap_.size() ||
HITCBC 703   22254 heap_[child].time_ < heap_[child + 1].time_) 703   18257 heap_[child].time_ < heap_[child + 1].time_)
HITCBC 704   48420 ? child 704   40662 ? child
HITCBC 705   26166 : child + 1; 705   22405 : child + 1;
706   706  
HITCBC 707   26166 if (heap_[index].time_ < heap_[min_child].time_) 707   22405 if (heap_[index].time_ < heap_[min_child].time_)
HITCBC 708   1658 break; 708   2481 break;
709   709  
HITCBC 710   24508 swap_heap(index, min_child); 710   19924 swap_heap(index, min_child);
HITCBC 711   24508 index = min_child; 711   19924 index = min_child;
HITCBC 712   24508 child = index * 2 + 1; 712   19924 child = index * 2 + 1;
713   } 713   }
HITCBC 714   18000 } 714   16626 }
715   715  
716   inline void 716   inline void
HITCBC 717   49546 timer_service::swap_heap(std::size_t i1, std::size_t i2) 717   42812 timer_service::swap_heap(std::size_t i1, std::size_t i2)
718   { 718   {
HITCBC 719   49546 heap_entry tmp = heap_[i1]; 719   42812 heap_entry tmp = heap_[i1];
HITCBC 720   49546 heap_[i1] = heap_[i2]; 720   42812 heap_[i1] = heap_[i2];
HITCBC 721   49546 heap_[i2] = tmp; 721   42812 heap_[i2] = tmp;
HITCBC 722   49546 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed); 722   42812 heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
HITCBC 723   49546 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed); 723   42812 heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
HITCBC 724   49546 } 724   42812 }
725   725  
726   // waiter_node's completion_op and canceller members are defined in 726   // waiter_node's completion_op and canceller members are defined in
727   // timer.cpp alongside implementation::wait(), for the same reason 727   // timer.cpp alongside implementation::wait(), for the same reason
728   // wait() lives there (see below). 728   // wait() lives there (see below).
729   729  
730   // timer::implementation::wait() is defined in timer.cpp, not here. 730   // timer::implementation::wait() is defined in timer.cpp, not here.
731   // It must be a non-inline definition in a translation unit that is 731   // 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 732   // always pulled into the link whenever detail::timer is used (every
733   // consumer needs timer's constructors from that same object file). 733   // consumer needs timer's constructors from that same object file).
734   // An inline definition in this header would only be emitted in 734   // An inline definition in this header would only be emitted in
735   // translation units that happen to also include this header, which 735   // translation units that happen to also include this header, which
736   // is not guaranteed for every caller of wait_awaitable::await_suspend 736   // is not guaranteed for every caller of wait_awaitable::await_suspend
737   // in timer.hpp (e.g. code that only reaches timer.hpp through 737   // in timer.hpp (e.g. code that only reaches timer.hpp through
738   // delay.hpp, without transitively including a scheduler header). 738   // delay.hpp, without transitively including a scheduler header).
739   739  
740   } // namespace boost::corosio::detail 740   } // namespace boost::corosio::detail
741   741  
742   #endif 742   #endif