include/boost/corosio/detail/timer_service.hpp

97.5% Lines (231 / 237) 100.0% Functions (27 / 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	2310x	callback() = default;
101
102		/// Construct a callback with the given context and function.
103	2310x	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	6846x	void operator()() const
113		{
114	6846x	if (fn_)
115	6846x	fn_(ctx_);
116	6846x	}
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	2310x	inline timer_service(capy::execution_context&, scheduler& sched)
142	2310x	: sched_(&sched)
143		{
144	2310x	}
145
146		/// Return the associated scheduler.
147	28437x	inline scheduler& get_scheduler() noexcept
148		{
149	28437x	return *sched_;
150		}
151
152		/// Destroy the timer service.
153	4620x	~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	2310x	inline void set_on_earliest_changed(callback cb)
160		{
161	2310x	on_earliest_changed_ = cb;
162	2310x	}
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	319421x	inline time_point nearest_expiry() const noexcept
173		{
174	319421x	auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
175	319421x	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	359987x	inline void refresh_cached_nearest() noexcept
204		{
205	359987x	auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
206	354272x	: heap_[0].time_.time_since_epoch().count();
207	359987x	cached_nearest_ns_.store(ns, std::memory_order_release);
208	359987x	}
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	43x	~tl_cache_owner()
232		{
233	43x	delete tl_cached_impl.get();
234	43x	tl_cached_impl.set(nullptr);
235	43x	}
236		};
237
238		inline void
239	13703x	arm_tl_cache_cleanup() noexcept
240		{
241	13703x	[[maybe_unused]] thread_local tl_cache_owner owner;
242	13703x	}
243
244		inline timer::implementation*
245	15086x	try_pop_tl_cache(timer_service* svc) noexcept
246		{
247	15086x	auto* impl = tl_cached_impl.get();
248	15086x	if (impl)
249		{
250	13278x	tl_cached_impl.set(nullptr);
251	13278x	if (impl->svc_ == svc)
252	13278x	return impl;
253		// Stale impl from a destroyed service
254	✗	delete impl;
255		}
256	1808x	return nullptr;
257		}
258
259		inline bool
260	15057x	try_push_tl_cache(timer::implementation* impl) noexcept
261		{
262	15057x	if (!tl_cached_impl.get())
263		{
264	13703x	arm_tl_cache_cleanup();
265	13703x	tl_cached_impl.set(impl);
266	13703x	return true;
267		}
268	1354x	return false;
269		}
270
271		inline void
272	2310x	timer_service_invalidate_cache() noexcept
273		{
274	2310x	delete tl_cached_impl.get();
275	2310x	tl_cached_impl.set(nullptr);
276	2310x	}
277
278		// timer_service out-of-class member function definitions
279
280		inline void
281	2310x	timer_service::shutdown()
282		{
283	2310x	timer_service_invalidate_cache();
284	2310x	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	2310x	std::vector<timer::implementation*> impls;
291	2310x	impls.reserve(heap_.size());
292	2339x	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	2310x	heap_.clear();
300	2310x	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	2339x	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	3662x	while (free_list_)
324		{
325	1352x	auto* next = free_list_->next_free_;
326	1352x	delete free_list_;
327	1352x	free_list_ = next;
328		}
329	2310x	}
330
331		inline io_object::implementation*
332	15086x	timer_service::construct()
333		{
334	15086x	timer::implementation* impl = try_pop_tl_cache(this);
335	15086x	if (impl)
336		{
337	13278x	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	13278x	impl->expiry_ = {};
341	13278x	impl->heap_index_.store(
342		(std::numeric_limits<std::size_t>::max)(),
343		std::memory_order_relaxed);
344	13278x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
345	13278x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
346	13278x	return impl;
347		}
348
349	1808x	std::lock_guard lock(mutex_);
350	1808x	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	1806x	impl = new timer::implementation(*this);
366		}
367	1808x	return impl;
368	1808x	}
369
370		inline void
371	15086x	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	15086x	if (shutting_down_)
380	29x	return;
381	15057x	destroy_impl(static_cast<timer::implementation&>(*p));
382		}
383
384		inline void
385	15057x	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	15057x	if (shutting_down_)
392	13703x	return;
393
394	15057x	cancel_timer(impl);
395
396	30114x	if (impl.heap_index_.load(std::memory_order_relaxed) !=
397	15057x	(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	15057x	if (try_push_tl_cache(&impl))
405	13703x	return;
406
407	1354x	std::lock_guard lock(mutex_);
408	1354x	impl.next_free_ = free_list_;
409	1354x	free_list_ = &impl;
410	1354x	}
411
412		inline void
413	18376x	timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
414		{
415	18376x	bool notify = false;
416	18376x	bool lost_cancel = false;
417		{
418	18376x	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	18376x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
423	36752x	(std::numeric_limits<std::size_t>::max)() &&
424	18376x	heap_.size() == heap_.capacity())
425	444x	heap_.reserve(heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
426		// Publish: from here the waiter is visible to the fire path and
427		// to its own stop callback (impl_ non-null enables cancel_waiter).
428	18376x	w->impl_ = &impl;
429	36752x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
430	18376x	(std::numeric_limits<std::size_t>::max)())
431		{
432	18376x	impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
433	18376x	heap_.push_back({impl.expiry_, &impl});
434	18376x	up_heap(heap_.size() - 1);
435	18376x	notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0);
436	18376x	refresh_cached_nearest();
437		}
438	18376x	BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
439	18376x	impl.waiter_ = w;
440
441		// Lost-cancel re-check: a stop requested after the canceller was
442		// armed in wait() but before this publication found impl_ null
443		// and returned a no-op. Observe it now and undo the insertion.
444	18376x	if (w->token_->stop_requested())
445		{
446	3x	w->impl_ = nullptr;
447	3x	impl.waiter_ = nullptr;
448	3x	remove_timer_impl(impl);
449	3x	impl.might_have_pending_waits_.store(
450		false, std::memory_order_relaxed);
451	3x	refresh_cached_nearest();
452	3x	lost_cancel = true;
453	3x	notify = false; // insertion undone; nearest unchanged
454		}
455	18376x	}
456	18376x	if (notify)
457	6846x	on_earliest_changed_();
458	18376x	if (lost_cancel)
459		{
460	3x	w->ec_ = make_error_code(capy::error::canceled);
461	3x	sched_->post(&w->op_);
462		}
463	18376x	}
464
465		inline void
466	15057x	timer_service::cancel_timer(timer::implementation& impl)
467		{
468	15057x	if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
469	15055x	return;
470
471		// No unlocked already-done fast-out here: it would need the
472		// non-atomic waiter_ (a race with concurrent drains), and an
473		// index-only check is lifetime-unsafe because npos is stored
474		// before the drain finishes touching the impl. A stale-true
475		// flag is rare with the stateless API; the locked path below
476		// re-validates.
477
478	2x	waiter_node* canceled = nullptr;
479
480		{
481	2x	std::lock_guard lock(mutex_);
482	2x	remove_timer_impl(impl);
483	2x	canceled = std::exchange(impl.waiter_, nullptr);
484	2x	if (canceled)
485	2x	canceled->impl_ = nullptr;
486		// Store false as the final touch of the impl under the lock so
487		// a pre-lock false-flag check trusts it unqualified.
488	2x	impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
489	2x	refresh_cached_nearest();
490	2x	}
491
492	2x	if (canceled)
493		{
494	2x	canceled->ec_ = make_error_code(capy::error::canceled);
495	2x	sched_->post(&canceled->op_);
496		}
497		}
498
499		inline void
500	1749x	timer_service::cancel_waiter(waiter_node* w)
501		{
502		{
503	1749x	std::lock_guard lock(mutex_);
504		// Already removed by another drain: cancel_timer,
505		// process_expired, or insert_waiter's lost-cancel recheck
506	1749x	if (!w->impl_)
507	4x	return;
508	1745x	auto* impl = w->impl_;
509	1745x	w->impl_ = nullptr;
510	1745x	impl->waiter_ = nullptr;
511	1745x	remove_timer_impl(*impl);
512	1745x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
513	1745x	refresh_cached_nearest();
514	1749x	}
515
516	1745x	w->ec_ = make_error_code(capy::error::canceled);
517	1745x	sched_->post(&w->op_);
518		}
519
520		inline std::size_t
521	339861x	timer_service::process_expired()
522		{
523	339861x	intrusive_list<waiter_node> expired;
524
525		{
526	339861x	std::lock_guard lock(mutex_);
527	339861x	auto now = clock_type::now();
528
529	356458x	while (!heap_.empty() && heap_[0].time_ <= now)
530		{
531	16597x	timer::implementation* t = heap_[0].timer_;
532	16597x	remove_timer_impl(*t);
533	16597x	if (auto* w = std::exchange(t->waiter_, nullptr))
534		{
535	16597x	w->impl_ = nullptr;
536	16597x	w->ec_ = {};
537	16597x	expired.push_back(w);
538		}
539	16597x	t->might_have_pending_waits_.store(
540		false, std::memory_order_relaxed);
541		}
542
543	339861x	refresh_cached_nearest();
544	339861x	}
545
546	339861x	std::size_t count = 0;
547	356458x	while (auto* w = expired.pop_front())
548		{
549	16597x	sched_->post(&w->op_);
550	16597x	++count;
551	16597x	}
552
553	339861x	return count;
554		}
555
556		inline void
557	18347x	timer_service::remove_timer_impl(timer::implementation& impl)
558		{
559	18347x	std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
560	18347x	if (index >= heap_.size())
561	✗	return; // Not in heap
562
563	18347x	if (index == heap_.size() - 1)
564		{
565		// Last element, just pop
566	2475x	impl.heap_index_.store(
567		(std::numeric_limits<std::size_t>::max)(),
568		std::memory_order_relaxed);
569	2475x	heap_.pop_back();
570		}
571		else
572		{
573		// Swap with last and reheapify
574	15872x	swap_heap(index, heap_.size() - 1);
575	15872x	impl.heap_index_.store(
576		(std::numeric_limits<std::size_t>::max)(),
577		std::memory_order_relaxed);
578	15872x	heap_.pop_back();
579
580	15872x	if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
581	1x	up_heap(index);
582		else
583	15871x	down_heap(index);
584		}
585		}
586
587		inline void
588	18377x	timer_service::up_heap(std::size_t index)
589		{
590	25557x	while (index > 0)
591		{
592	18708x	std::size_t parent = (index - 1) / 2;
593	18708x	if (!(heap_[index].time_ < heap_[parent].time_))
594	11528x	break;
595	7180x	swap_heap(index, parent);
596	7180x	index = parent;
597		}
598	18377x	}
599
600		inline void
601	15871x	timer_service::down_heap(std::size_t index)
602		{
603	15871x	std::size_t child = index * 2 + 1;
604	33766x	while (child < heap_.size())
605		{
606	19641x	std::size_t min_child = (child + 1 == heap_.size() \|\|
607	16096x	heap_[child].time_ < heap_[child + 1].time_)
608	35737x	? child
609	19641x	: child + 1;
610
611	19641x	if (heap_[index].time_ < heap_[min_child].time_)
612	1746x	break;
613
614	17895x	swap_heap(index, min_child);
615	17895x	index = min_child;
616	17895x	child = index * 2 + 1;
617		}
618	15871x	}
619
620		inline void
621	40947x	timer_service::swap_heap(std::size_t i1, std::size_t i2)
622		{
623	40947x	heap_entry tmp = heap_[i1];
624	40947x	heap_[i1] = heap_[i2];
625	40947x	heap_[i2] = tmp;
626	40947x	heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
627	40947x	heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
628	40947x	}
629
630		// waiter_node's completion_op and canceller members are defined in
631		// timer.cpp alongside implementation::wait(), for the same reason
632		// wait() lives there (see below).
633
634		// timer::implementation::wait() is defined in timer.cpp, not here.
635		// It must be a non-inline definition in a translation unit that is
636		// always pulled into the link whenever detail::timer is used (every
637		// consumer needs timer's constructors from that same object file).
638		// An inline definition in this header would only be emitted in
639		// translation units that happen to also include this header, which
640		// is not guaranteed for every caller of wait_awaitable::await_suspend
641		// in timer.hpp (e.g. code that only reaches timer.hpp through
642		// delay.hpp, without transitively including a scheduler header).
643
644		// Free functions
645
646		inline timer_service&
647	2310x	get_timer_service(capy::execution_context& ctx, scheduler& sched)
648		{
649	2310x	return ctx.make_service<timer_service>(sched);
650		}
651
652		} // namespace boost::corosio::detail
653
654		#endif
655