include/boost/corosio/detail/timer_service.hpp

97.1% Lines (232/0/239) 100.0% List of functions (27/0/27)

[ ] prev/next file n p prev/next uncovered line

timer_service.hpp

f(x) Functions (27)

Function Calls Lines Blocks

Line	Hits	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/intrusive.hpp>
18		#include <boost/corosio/detail/thread_local_ptr.hpp>
19		#include <boost/capy/error.hpp>
20		#include <boost/capy/ex/execution_context.hpp>
21		#include <boost/capy/ex/executor_ref.hpp>
22		#include <system_error>
23
24		#include <atomic>
25		#include <chrono>
26		#include <coroutine>
27		#include <cstddef>
28		#include <limits>
29		#include <mutex>
30		#include <stop_token>
31		#include <utility>
32		#include <vector>
33
34		namespace boost::corosio::detail {
35
36		struct scheduler;
37
38		/*
39		Timer Service
40		=============
41
42		Data Structures
43		---------------
44		waiter_node (defined in timer.hpp) holds per-waiter state:
45		coroutine handle, executor, error output, embedded
46		completion_op. Each concurrent co_await t.wait() embeds one
47		waiter_node in the awaitable on the suspended coroutine's
48		frame — waits perform no allocation.
49
50		timer::implementation holds per-timer state: expiry, heap
51		index, and the single published waiter. Each timer holds
52		at most one waiter; process_expired's local cross-timer drain
53		list still threads waiters through their intrusive hooks when
54		collecting several timers' waiters past the lock.
55
56		timer_service owns a min-heap of active timers and a free list
57		of recycled impls. The heap is ordered by expiry time; the
58		scheduler queries nearest_expiry() to set the epoll/timerfd
59		timeout.
60
61		Optimization Strategy
62		---------------------
63		1. Deferred heap insertion — expires_after() stores the expiry
64		but does not insert into the heap. Insertion happens in wait().
65		2. Thread-local impl cache — single-slot per-thread cache.
66		3. Frame-resident waiter_node with embedded completion_op —
67		eliminates heap allocation per wait/fire/cancel.
68		4. Cached nearest expiry — atomic avoids mutex in nearest_expiry().
69		5. might_have_pending_waits_ flag — skips lock when no wait issued.
70
71		Concurrency
72		-----------
73		stop_token callbacks can fire from any thread. The impl_
74		pointer on waiter_node is used as a "still in list" marker.
75		A waiter_node's storage is the suspended coroutine's frame:
76		every completion path must finish touching the node before
77		posting the continuation or destroying the handle.
78		*/
79
80		inline void timer_service_invalidate_cache() noexcept;
81
82		// timer_service class body — member function definitions are
83		// out-of-class (after implementation and waiter_node are complete)
84		class BOOST_COROSIO_DECL timer_service final
85		: public capy::execution_context::service
86		, public io_object::io_service
87		{
88		public:
89		using clock_type = std::chrono::steady_clock;
90		using time_point = clock_type::time_point;
91
92		/// Type-erased callback for earliest-expiry-changed notifications.
93		class callback
94		{
95		void* ctx_ = nullptr;
96		void (fn_)(void) = nullptr;
97
98		public:
99		/// Construct an empty callback.
100	1790x	callback() = default;
101
102		/// Construct a callback with the given context and function.
103	1790x	callback(void* ctx, void (fn)(void)) noexcept : ctx_(ctx), fn_(fn) {}
104
105		/// Return true if the callback is non-empty.
106		explicit operator bool() const noexcept
107		{
108		return fn_ != nullptr;
109		}
110
111		/// Invoke the callback.
112	6840x	void operator()() const
113		{
114	6840x	if (fn_)
115	6840x	fn_(ctx_);
116	6840x	}
117		};
118
119		private:
120		struct heap_entry
121		{
122		time_point time_;
123		timer::implementation* timer_;
124		};
125
126		scheduler* sched_ = nullptr;
127		BOOST_COROSIO_MSVC_WARNING_PUSH
128		BOOST_COROSIO_MSVC_WARNING_DISABLE(4251) // std:: members, dll-interface
129		mutable std::mutex mutex_;
130		std::vector<heap_entry> heap_;
131		timer::implementation* free_list_ = nullptr;
132		callback on_earliest_changed_;
133		bool shutting_down_ = false;
134		// Avoids mutex in nearest_expiry() and empty()
135		mutable std::atomic<std::int64_t> cached_nearest_ns_{
136		(std::numeric_limits<std::int64_t>::max)()};
137		BOOST_COROSIO_MSVC_WARNING_POP
138
139		public:
140		/// Construct the timer service bound to a scheduler.
141	1790x	inline timer_service(capy::execution_context&, scheduler& sched)
142	1790x	: sched_(&sched)
143		{
144	1790x	}
145
146		/// Return the associated scheduler.
147	13957x	inline scheduler& get_scheduler() noexcept
148		{
149	13957x	return *sched_;
150		}
151
152		/// Destroy the timer service.
153	3580x	~timer_service() override = default;
154
155		timer_service(timer_service const&) = delete;
156		timer_service& operator=(timer_service const&) = delete;
157
158		/// Register a callback invoked when the earliest expiry changes.
159	1790x	inline void set_on_earliest_changed(callback cb)
160		{
161	1790x	on_earliest_changed_ = cb;
162	1790x	}
163
164		/// Return true if no timers are in the heap.
165		inline bool empty() const noexcept
166		{
167		return cached_nearest_ns_.load(std::memory_order_acquire) ==
168		(std::numeric_limits<std::int64_t>::max)();
169		}
170
171		/// Return the nearest timer expiry without acquiring the mutex.
172	347089x	inline time_point nearest_expiry() const noexcept
173		{
174	347089x	auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
175	347089x	return time_point(time_point::duration(ns));
176		}
177
178		/// Cancel all pending timers and free cached resources.
179		inline void shutdown() override;
180
181		/// Construct a new timer implementation.
182		inline io_object::implementation* construct() override;
183
184		/// Destroy a timer implementation, cancelling pending waiters.
185		inline void destroy(io_object::implementation* p) override;
186
187		/// Cancel and recycle a timer implementation.
188		inline void destroy_impl(timer::implementation& impl);
189
190		/// Publish the timer's waiter and insert the timer into the heap.
191		inline void insert_waiter(timer::implementation& impl, waiter_node* w);
192
193		/// Cancel the timer's published waiter, if any.
194		inline void cancel_timer(timer::implementation& impl);
195
196		/// Cancel one specific waiter ( stop_token callback path ).
197		inline void cancel_waiter(waiter_node* w);
198
199		/// Complete all waiters whose timers have expired.
200		inline std::size_t process_expired();
201
202		private:
203	374911x	inline void refresh_cached_nearest() noexcept
204		{
205	374911x	auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
206	371183x	: heap_[0].time_.time_since_epoch().count();
207	374911x	cached_nearest_ns_.store(ns, std::memory_order_release);
208	374911x	}
209
210		inline void remove_timer_impl(timer::implementation& impl);
211		inline void up_heap(std::size_t index);
212		inline void down_heap(std::size_t index);
213		inline void swap_heap(std::size_t i1, std::size_t i2);
214		};
215
216		// Thread-local cache avoids hot-path mutex acquisitions:
217		// single-slot impl cache, validated by comparing svc_. Cleared by
218		// timer_service_invalidate_cache() during shutdown.
219
220		inline thread_local_ptr<timer::implementation> tl_cached_impl;
221
222		// The POD TLS slot above never runs destructors, so a short-lived
223		// run() thread would leak its cached impl. Each push arms this
224		// owner, whose destructor frees the slot at thread exit. A cached
225		// entry is a quiescent heap object (nothing in the heap or free
226		// list) and deletion touches no service state, so it is safe after
227		// the owning service is gone (the stale-entry path in
228		// try_pop_tl_cache deletes the same way).
229		struct tl_cache_owner
230		{
231	40x	~tl_cache_owner()
232		{
233	40x	delete tl_cached_impl.get();
234	40x	tl_cached_impl.set(nullptr);
235	40x	}
236		};
237
238		inline void
239	7653x	arm_tl_cache_cleanup() noexcept
240		{
241	7653x	[[maybe_unused]] thread_local tl_cache_owner owner;
242	7653x	}
243
244		inline timer::implementation*
245	7844x	try_pop_tl_cache(timer_service* svc) noexcept
246		{
247	7844x	auto* impl = tl_cached_impl.get();
248	7844x	if (impl)
249		{
250	7362x	tl_cached_impl.set(nullptr);
251	7362x	if (impl->svc_ == svc)
252	7362x	return impl;
253		// Stale impl from a destroyed service
254	✗	delete impl;
255		}
256	482x	return nullptr;
257		}
258
259		inline bool
260	7815x	try_push_tl_cache(timer::implementation* impl) noexcept
261		{
262	7815x	if (!tl_cached_impl.get())
263		{
264	7653x	arm_tl_cache_cleanup();
265	7653x	tl_cached_impl.set(impl);
266	7653x	return true;
267		}
268	162x	return false;
269		}
270
271		inline void
272	1790x	timer_service_invalidate_cache() noexcept
273		{
274	1790x	delete tl_cached_impl.get();
275	1790x	tl_cached_impl.set(nullptr);
276	1790x	}
277
278		// timer_service out-of-class member function definitions
279
280		inline void
281	1790x	timer_service::shutdown()
282		{
283	1790x	timer_service_invalidate_cache();
284	1790x	shutting_down_ = true;
285
286		// Snapshot impls and detach them from the heap so that
287		// coroutine-owned timer destructors (triggered by h.destroy()
288		// below) cannot re-enter remove_timer_impl() and mutate the
289		// vector during iteration.
290	1790x	std::vector<timer::implementation*> impls;
291	1790x	impls.reserve(heap_.size());
292	1819x	for (auto& entry : heap_)
293		{
294	29x	entry.timer_->heap_index_.store(
295		(std::numeric_limits<std::size_t>::max)(),
296		std::memory_order_relaxed);
297	29x	impls.push_back(entry.timer_);
298		}
299	1790x	heap_.clear();
300	1790x	cached_nearest_ns_.store(
301		(std::numeric_limits<std::int64_t>::max)(), std::memory_order_release);
302
303		// Cancel waiting timers. Each waiter called work_started()
304		// in implementation::wait(). On IOCP the scheduler shutdown
305		// loop exits when outstanding_work_ reaches zero, so we must
306		// call work_finished() here to balance it. On other backends
307		// this is harmless.
308	1819x	for (auto* impl : impls)
309		{
310	29x	if (auto* w = std::exchange(impl->waiter_, nullptr))
311		{
312	29x	w->reset_stop_cb();
313	29x	auto h = std::exchange(w->h_, {});
314	29x	sched_->work_finished();
315		// Destroying the frame also ends the node's storage
316	29x	if (h)
317	29x	h.destroy();
318		}
319	29x	delete impl;
320		}
321
322		// Delete free-listed impls
323	1950x	while (free_list_)
324		{
325	160x	auto* next = free_list_->next_free_;
326	160x	delete free_list_;
327	160x	free_list_ = next;
328		}
329	1790x	}
330
331		inline io_object::implementation*
332	7844x	timer_service::construct()
333		{
334	7844x	timer::implementation* impl = try_pop_tl_cache(this);
335	7844x	if (impl)
336		{
337	7362x	impl->svc_ = this;
338		// Reset expiry_ too: a recycled impl must behave like a fresh
339		// one, whose default expiry reads as already elapsed
340	7362x	impl->expiry_ = {};
341	7362x	impl->heap_index_.store(
342		(std::numeric_limits<std::size_t>::max)(),
343		std::memory_order_relaxed);
344	7362x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
345	7362x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
346	7362x	return impl;
347		}
348
349	482x	std::lock_guard lock(mutex_);
350	482x	if (free_list_)
351		{
352	2x	impl = free_list_;
353	2x	free_list_ = impl->next_free_;
354	2x	impl->next_free_ = nullptr;
355	2x	impl->svc_ = this;
356	2x	impl->expiry_ = {};
357	2x	impl->heap_index_.store(
358		(std::numeric_limits<std::size_t>::max)(),
359		std::memory_order_relaxed);
360	2x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
361	2x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
362		}
363		else
364		{
365	480x	impl = new timer::implementation(*this);
366		}
367	482x	return impl;
368	482x	}
369
370		inline void
371	7844x	timer_service::destroy(io_object::implementation* p)
372		{
373		// During shutdown the drain loop owns every impl and deletes
374		// them directly. A frame destroyed by that loop can unwind a
375		// handle whose impl was freed in an earlier iteration (a
376		// timeout's parent frame owns the timeout timer while
377		// suspended on the inner delay's timer), so bail out before
378		// even downcasting the pointer.
379	7844x	if (shutting_down_)
380	29x	return;
381	7815x	destroy_impl(static_cast<timer::implementation&>(*p));
382		}
383
384		inline void
385	7815x	timer_service::destroy_impl(timer::implementation& impl)
386		{
387		// During shutdown the impl is owned by the shutdown loop.
388		// Re-entering here (from a coroutine-owned timer destructor
389		// triggered by h.destroy()) must not modify the heap or
390		// recycle the impl — shutdown deletes it directly.
391	7815x	if (shutting_down_)
392	7653x	return;
393
394	7815x	cancel_timer(impl);
395
396	15630x	if (impl.heap_index_.load(std::memory_order_relaxed) !=
397	7815x	(std::numeric_limits<std::size_t>::max)())
398		{
399	✗	std::lock_guard lock(mutex_);
400	✗	remove_timer_impl(impl);
401	✗	refresh_cached_nearest();
402	✗	}
403
404	7815x	if (try_push_tl_cache(&impl))
405	7653x	return;
406
407	162x	std::lock_guard lock(mutex_);
408	162x	impl.next_free_ = free_list_;
409	162x	free_list_ = &impl;
410	162x	}
411
412		inline void
413	7005x	timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
414		{
415	7005x	bool notify = false;
416	7005x	bool lost_cancel = false;
417		{
418	7005x	std::lock_guard lock(mutex_);
419		// Grow before publishing anything, so the push_back below
420		// cannot throw: a failure here leaves the waiter untouched,
421		// the strong guarantee rearm_wait's recovery relies on.
422	7005x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
423	14010x	(std::numeric_limits<std::size_t>::max)() &&
424	7005x	heap_.size() == heap_.capacity())
425	301x	heap_.reserve(
426	301x	heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
427		// Publish: from here the waiter is visible to the fire path and
428		// to its own stop callback (impl_ non-null enables cancel_waiter).
429	7005x	w->impl_ = &impl;
430	14010x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
431	7005x	(std::numeric_limits<std::size_t>::max)())
432		{
433	7005x	impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
434	7005x	heap_.push_back({impl.expiry_, &impl});
435	7005x	up_heap(heap_.size() - 1);
436	7005x	notify =
437	7005x	(impl.heap_index_.load(std::memory_order_relaxed) == 0);
438	7005x	refresh_cached_nearest();
439		}
440	7005x	BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
441	7005x	impl.waiter_ = w;
442
443		// Lost-cancel re-check: a stop requested after the canceller was
444		// armed in wait() but before this publication found impl_ null
445		// and returned a no-op. Observe it now and undo the insertion.
446	7005x	if (w->token_->stop_requested())
447		{
448	3x	w->impl_ = nullptr;
449	3x	impl.waiter_ = nullptr;
450	3x	remove_timer_impl(impl);
451	3x	impl.might_have_pending_waits_.store(
452		false, std::memory_order_relaxed);
453	3x	refresh_cached_nearest();
454	3x	lost_cancel = true;
455	3x	notify = false; // insertion undone; nearest unchanged
456		}
457	7005x	}
458	7005x	if (notify)
459	6840x	on_earliest_changed_();
460	7005x	if (lost_cancel)
461		{
462	3x	w->ec_ = make_error_code(capy::error::canceled);
463	3x	sched_->post(&w->op_);
464		}
465	7005x	}
466
467		inline void
468	7815x	timer_service::cancel_timer(timer::implementation& impl)
469		{
470	7815x	if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
471	7813x	return;
472
473		// No unlocked already-done fast-out here: it would need the
474		// non-atomic waiter_ (a race with concurrent drains), and an
475		// index-only check is lifetime-unsafe because npos is stored
476		// before the drain finishes touching the impl. A stale-true
477		// flag is rare with the stateless API; the locked path below
478		// re-validates.
479
480	2x	waiter_node* canceled = nullptr;
481
482		{
483	2x	std::lock_guard lock(mutex_);
484	2x	remove_timer_impl(impl);
485	2x	canceled = std::exchange(impl.waiter_, nullptr);
486	2x	if (canceled)
487	2x	canceled->impl_ = nullptr;
488		// Store false as the final touch of the impl under the lock so
489		// a pre-lock false-flag check trusts it unqualified.
490	2x	impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
491	2x	refresh_cached_nearest();
492	2x	}
493
494	2x	if (canceled)
495		{
496	2x	canceled->ec_ = make_error_code(capy::error::canceled);
497	2x	sched_->post(&canceled->op_);
498		}
499		}
500
501		inline void
502	1462x	timer_service::cancel_waiter(waiter_node* w)
503		{
504		{
505	1462x	std::lock_guard lock(mutex_);
506		// Already removed by another drain: cancel_timer,
507		// process_expired, or insert_waiter's lost-cancel recheck
508	1462x	if (!w->impl_)
509	3x	return;
510	1459x	auto* impl = w->impl_;
511	1459x	w->impl_ = nullptr;
512	1459x	impl->waiter_ = nullptr;
513	1459x	remove_timer_impl(*impl);
514	1459x	impl->might_have_pending_waits_.store(
515		false, std::memory_order_relaxed);
516	1459x	refresh_cached_nearest();
517	1462x	}
518
519	1459x	w->ec_ = make_error_code(capy::error::canceled);
520	1459x	sched_->post(&w->op_);
521		}
522
523		inline std::size_t
524	366442x	timer_service::process_expired()
525		{
526	366442x	intrusive_list<waiter_node> expired;
527
528		{
529	366442x	std::lock_guard lock(mutex_);
530	366442x	auto now = clock_type::now();
531
532	371954x	while (!heap_.empty() && heap_[0].time_ <= now)
533		{
534	5512x	timer::implementation* t = heap_[0].timer_;
535	5512x	remove_timer_impl(*t);
536	5512x	if (auto* w = std::exchange(t->waiter_, nullptr))
537		{
538	5512x	w->impl_ = nullptr;
539	5512x	w->ec_ = {};
540	5512x	expired.push_back(w);
541		}
542	5512x	t->might_have_pending_waits_.store(
543		false, std::memory_order_relaxed);
544		}
545
546	366442x	refresh_cached_nearest();
547	366442x	}
548
549	366442x	std::size_t count = 0;
550	371954x	while (auto* w = expired.pop_front())
551		{
552	5512x	sched_->post(&w->op_);
553	5512x	++count;
554	5512x	}
555
556	366442x	return count;
557		}
558
559		inline void
560	6976x	timer_service::remove_timer_impl(timer::implementation& impl)
561		{
562	6976x	std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
563	6976x	if (index >= heap_.size())
564	✗	return; // Not in heap
565
566	6976x	if (index == heap_.size() - 1)
567		{
568		// Last element, just pop
569	1697x	impl.heap_index_.store(
570		(std::numeric_limits<std::size_t>::max)(),
571		std::memory_order_relaxed);
572	1697x	heap_.pop_back();
573		}
574		else
575		{
576		// Swap with last and reheapify
577	5279x	swap_heap(index, heap_.size() - 1);
578	5279x	impl.heap_index_.store(
579		(std::numeric_limits<std::size_t>::max)(),
580		std::memory_order_relaxed);
581	5279x	heap_.pop_back();
582
583	5279x	if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
584	✗	up_heap(index);
585		else
586	5279x	down_heap(index);
587		}
588		}
589
590		inline void
591	7005x	timer_service::up_heap(std::size_t index)
592		{
593	12213x	while (index > 0)
594		{
595	5370x	std::size_t parent = (index - 1) / 2;
596	5370x	if (!(heap_[index].time_ < heap_[parent].time_))
597	162x	break;
598	5208x	swap_heap(index, parent);
599	5208x	index = parent;
600		}
601	7005x	}
602
603		inline void
604	5279x	timer_service::down_heap(std::size_t index)
605		{
606	5279x	std::size_t child = index * 2 + 1;
607	5405x	while (child < heap_.size())
608		{
609	150x	std::size_t min_child = (child + 1 == heap_.size() \|\|
610	122x	heap_[child].time_ < heap_[child + 1].time_)
611	272x	? child
612	150x	: child + 1;
613
614	150x	if (heap_[index].time_ < heap_[min_child].time_)
615	24x	break;
616
617	126x	swap_heap(index, min_child);
618	126x	index = min_child;
619	126x	child = index * 2 + 1;
620		}
621	5279x	}
622
623		inline void
624	10613x	timer_service::swap_heap(std::size_t i1, std::size_t i2)
625		{
626	10613x	heap_entry tmp = heap_[i1];
627	10613x	heap_[i1] = heap_[i2];
628	10613x	heap_[i2] = tmp;
629	10613x	heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
630	10613x	heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
631	10613x	}
632
633		// waiter_node's completion_op and canceller members are defined in
634		// timer.cpp alongside implementation::wait(), for the same reason
635		// wait() lives there (see below).
636
637		// timer::implementation::wait() is defined in timer.cpp, not here.
638		// It must be a non-inline definition in a translation unit that is
639		// always pulled into the link whenever detail::timer is used (every
640		// consumer needs timer's constructors from that same object file).
641		// An inline definition in this header would only be emitted in
642		// translation units that happen to also include this header, which
643		// is not guaranteed for every caller of wait_awaitable::await_suspend
644		// in timer.hpp (e.g. code that only reaches timer.hpp through
645		// delay.hpp, without transitively including a scheduler header).
646
647		// Free functions
648
649		inline timer_service&
650	1790x	get_timer_service(capy::execution_context& ctx, scheduler& sched)
651		{
652	1790x	return ctx.make_service<timer_service>(sched);
653		}
654
655		} // namespace boost::corosio::detail
656
657		#endif
658