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