include/boost/corosio/detail/timer_service.hpp

97.5% Lines (234 / 240) 100.0% Functions (28 / 28)

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

timer_service.hpp

f(x) Functions (28)

Function Calls Lines Blocks

Line	Hits	Source Code
1		//
2		// Copyright (c) 2025 Vinnie Falco ([email protected])
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	4115x	callback() = default;
101
102		/// Construct a callback with the given context and function.
103	4115x	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	11756x	void operator()() const
113		{
114	11756x	if (fn_)
115	11756x	fn_(ctx_);
116	11756x	}
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	4115x	inline timer_service(capy::execution_context&, scheduler& sched)
142	4115x	: sched_(&sched)
143		{
144	4115x	}
145
146		/// Return the associated scheduler.
147	38850x	inline scheduler& get_scheduler() noexcept
148		{
149	38850x	return *sched_;
150		}
151
152		/// Destroy the timer service.
153	8230x	~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	4115x	inline void set_on_earliest_changed(callback cb)
160		{
161	4115x	on_earliest_changed_ = cb;
162	4115x	}
163
164		/// Return true if no timers are in the heap.
165	42478x	inline bool empty() const noexcept
166		{
167	42478x	return cached_nearest_ns_.load(std::memory_order_acquire) ==
168	42478x	(std::numeric_limits<std::int64_t>::max)();
169		}
170
171		/// Return the nearest timer expiry without acquiring the mutex.
172	23156x	inline time_point nearest_expiry() const noexcept
173		{
174	23156x	auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
175	23156x	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	106184x	inline void refresh_cached_nearest() noexcept
204		{
205	106184x	auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
206	96757x	: heap_[0].time_.time_since_epoch().count();
207	106184x	cached_nearest_ns_.store(ns, std::memory_order_release);
208	106184x	}
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	80x	~tl_cache_owner()
232		{
233	80x	delete tl_cached_impl.get();
234	80x	tl_cached_impl.set(nullptr);
235	80x	}
236		};
237
238		inline void
239	18924x	arm_tl_cache_cleanup() noexcept
240		{
241	18924x	[[maybe_unused]] thread_local tl_cache_owner owner;
242	18924x	}
243
244		inline timer::implementation*
245	20708x	try_pop_tl_cache(timer_service* svc) noexcept
246		{
247	20708x	auto* impl = tl_cached_impl.get();
248	20708x	if (impl)
249		{
250	18248x	tl_cached_impl.set(nullptr);
251	18248x	if (impl->svc_ == svc)
252	18248x	return impl;
253		// Stale impl from a destroyed service
254	✗	delete impl;
255		}
256	2460x	return nullptr;
257		}
258
259		inline bool
260	20664x	try_push_tl_cache(timer::implementation* impl) noexcept
261		{
262	20664x	if (!tl_cached_impl.get())
263		{
264	18924x	arm_tl_cache_cleanup();
265	18924x	tl_cached_impl.set(impl);
266	18924x	return true;
267		}
268	1740x	return false;
269		}
270
271		inline void
272	4115x	timer_service_invalidate_cache() noexcept
273		{
274	4115x	delete tl_cached_impl.get();
275	4115x	tl_cached_impl.set(nullptr);
276	4115x	}
277
278		// timer_service out-of-class member function definitions
279
280		inline void
281	4115x	timer_service::shutdown()
282		{
283	4115x	timer_service_invalidate_cache();
284	4115x	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	4115x	std::vector<timer::implementation*> impls;
291	4115x	impls.reserve(heap_.size());
292	4159x	for (auto& entry : heap_)
293		{
294	44x	entry.timer_->heap_index_.store(
295		(std::numeric_limits<std::size_t>::max)(),
296		std::memory_order_relaxed);
297	44x	impls.push_back(entry.timer_);
298		}
299	4115x	heap_.clear();
300	4115x	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	4159x	for (auto* impl : impls)
309		{
310	44x	if (auto* w = std::exchange(impl->waiter_, nullptr))
311		{
312	44x	w->reset_stop_cb();
313	44x	auto h = std::exchange(w->h_, {});
314	44x	sched_->work_finished();
315		// Destroying the frame also ends the node's storage
316	44x	if (h)
317	44x	h.destroy();
318		}
319	44x	delete impl;
320		}
321
322		// Delete free-listed impls
323	5852x	while (free_list_)
324		{
325	1737x	auto* next = free_list_->next_free_;
326	1737x	delete free_list_;
327	1737x	free_list_ = next;
328		}
329	4115x	}
330
331		inline io_object::implementation*
332	20708x	timer_service::construct()
333		{
334	20708x	timer::implementation* impl = try_pop_tl_cache(this);
335	20708x	if (impl)
336		{
337	18248x	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	18248x	impl->expiry_ = {};
341	18248x	impl->heap_index_.store(
342		(std::numeric_limits<std::size_t>::max)(),
343		std::memory_order_relaxed);
344	18248x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
345	18248x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
346	18248x	return impl;
347		}
348
349	2460x	std::lock_guard lock(mutex_);
350	2460x	if (free_list_)
351		{
352	3x	impl = free_list_;
353	3x	free_list_ = impl->next_free_;
354	3x	impl->next_free_ = nullptr;
355	3x	impl->svc_ = this;
356	3x	impl->expiry_ = {};
357	3x	impl->heap_index_.store(
358		(std::numeric_limits<std::size_t>::max)(),
359		std::memory_order_relaxed);
360	3x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
361	3x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
362		}
363		else
364		{
365	2457x	impl = new timer::implementation(*this);
366		}
367	2460x	return impl;
368	2460x	}
369
370		inline void
371	20708x	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	20708x	if (shutting_down_)
380	44x	return;
381	20664x	destroy_impl(static_cast<timer::implementation&>(*p));
382		}
383
384		inline void
385	20664x	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	20664x	if (shutting_down_)
392	18924x	return;
393
394	20664x	cancel_timer(impl);
395
396	41328x	if (impl.heap_index_.load(std::memory_order_relaxed) !=
397	20664x	(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	20664x	if (try_push_tl_cache(&impl))
405	18924x	return;
406
407	1740x	std::lock_guard lock(mutex_);
408	1740x	impl.next_free_ = free_list_;
409	1740x	free_list_ = &impl;
410	1740x	}
411
412		inline void
413	25326x	timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
414		{
415	25326x	bool notify = false;
416	25326x	bool lost_cancel = false;
417		{
418	25326x	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	25326x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
423	50652x	(std::numeric_limits<std::size_t>::max)() &&
424	25326x	heap_.size() == heap_.capacity())
425	702x	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	25326x	w->impl_ = &impl;
429	50652x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
430	25326x	(std::numeric_limits<std::size_t>::max)())
431		{
432	25326x	impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
433	25326x	heap_.push_back({impl.expiry_, &impl});
434	25326x	up_heap(heap_.size() - 1);
435	25326x	notify = (impl.heap_index_.load(std::memory_order_relaxed) == 0);
436	25326x	refresh_cached_nearest();
437		}
438	25326x	BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
439	25326x	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	25326x	if (w->token_->stop_requested())
445		{
446	241x	w->impl_ = nullptr;
447	241x	impl.waiter_ = nullptr;
448	241x	remove_timer_impl(impl);
449	241x	impl.might_have_pending_waits_.store(
450		false, std::memory_order_relaxed);
451	241x	refresh_cached_nearest();
452	241x	lost_cancel = true;
453	241x	notify = false; // insertion undone; nearest unchanged
454		}
455	25326x	}
456	25326x	if (notify)
457	11756x	on_earliest_changed_();
458	25326x	if (lost_cancel)
459		{
460	241x	w->ec_ = make_error_code(capy::error::canceled);
461	241x	sched_->post(&w->op_);
462		}
463	25326x	}
464
465		inline void
466	20664x	timer_service::cancel_timer(timer::implementation& impl)
467		{
468	20664x	if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
469	20661x	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	3x	waiter_node* canceled = nullptr;
479
480		{
481	3x	std::lock_guard lock(mutex_);
482	3x	remove_timer_impl(impl);
483	3x	canceled = std::exchange(impl.waiter_, nullptr);
484	3x	if (canceled)
485	3x	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	3x	impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
489	3x	refresh_cached_nearest();
490	3x	}
491
492	3x	if (canceled)
493		{
494	3x	canceled->ec_ = make_error_code(capy::error::canceled);
495	3x	sched_->post(&canceled->op_);
496		}
497		}
498
499		inline void
500	3763x	timer_service::cancel_waiter(waiter_node* w)
501		{
502		{
503	3763x	std::lock_guard lock(mutex_);
504		// Already removed by another drain: cancel_timer,
505		// process_expired, or insert_waiter's lost-cancel recheck
506	3763x	if (!w->impl_)
507	247x	return;
508	3516x	auto* impl = w->impl_;
509	3516x	w->impl_ = nullptr;
510	3516x	impl->waiter_ = nullptr;
511	3516x	remove_timer_impl(*impl);
512	3516x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
513	3516x	refresh_cached_nearest();
514	3763x	}
515
516	3516x	w->ec_ = make_error_code(capy::error::canceled);
517	3516x	sched_->post(&w->op_);
518		}
519
520		inline std::size_t
521	77098x	timer_service::process_expired()
522		{
523	77098x	intrusive_list<waiter_node> expired;
524
525		{
526	77098x	std::lock_guard lock(mutex_);
527	77098x	auto now = clock_type::now();
528
529	98620x	while (!heap_.empty() && heap_[0].time_ <= now)
530		{
531	21522x	timer::implementation* t = heap_[0].timer_;
532	21522x	remove_timer_impl(*t);
533	21522x	if (auto* w = std::exchange(t->waiter_, nullptr))
534		{
535	21522x	w->impl_ = nullptr;
536	21522x	w->ec_ = {};
537	21522x	expired.push_back(w);
538		}
539	21522x	t->might_have_pending_waits_.store(
540		false, std::memory_order_relaxed);
541		}
542
543	77098x	refresh_cached_nearest();
544	77098x	}
545
546	77098x	std::size_t count = 0;
547	98620x	while (auto* w = expired.pop_front())
548		{
549	21522x	sched_->post(&w->op_);
550	21522x	++count;
551	21522x	}
552
553	77098x	return count;
554		}
555
556		inline void
557	25282x	timer_service::remove_timer_impl(timer::implementation& impl)
558		{
559	25282x	std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
560	25282x	if (index >= heap_.size())
561	✗	return; // Not in heap
562
563	25282x	if (index == heap_.size() - 1)
564		{
565		// Last element, just pop
566	4789x	impl.heap_index_.store(
567		(std::numeric_limits<std::size_t>::max)(),
568		std::memory_order_relaxed);
569	4789x	heap_.pop_back();
570		}
571		else
572		{
573		// Swap with last and reheapify
574	20493x	swap_heap(index, heap_.size() - 1);
575	20493x	impl.heap_index_.store(
576		(std::numeric_limits<std::size_t>::max)(),
577		std::memory_order_relaxed);
578	20493x	heap_.pop_back();
579
580	20493x	if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
581	5x	up_heap(index);
582		else
583	20488x	down_heap(index);
584		}
585		}
586
587		inline void
588	25331x	timer_service::up_heap(std::size_t index)
589		{
590	36057x	while (index > 0)
591		{
592	24198x	std::size_t parent = (index - 1) / 2;
593	24198x	if (!(heap_[index].time_ < heap_[parent].time_))
594	13472x	break;
595	10726x	swap_heap(index, parent);
596	10726x	index = parent;
597		}
598	25331x	}
599
600		inline void
601	20488x	timer_service::down_heap(std::size_t index)
602		{
603	20488x	std::size_t child = index * 2 + 1;
604	44792x	while (child < heap_.size())
605		{
606	26548x	std::size_t min_child = (child + 1 == heap_.size() \|\|
607	23454x	heap_[child].time_ < heap_[child + 1].time_)
608	50002x	? child
609	26548x	: child + 1;
610
611	26548x	if (heap_[index].time_ < heap_[min_child].time_)
612	2244x	break;
613
614	24304x	swap_heap(index, min_child);
615	24304x	index = min_child;
616	24304x	child = index * 2 + 1;
617		}
618	20488x	}
619
620		inline void
621	55523x	timer_service::swap_heap(std::size_t i1, std::size_t i2)
622		{
623	55523x	heap_entry tmp = heap_[i1];
624	55523x	heap_[i1] = heap_[i2];
625	55523x	heap_[i2] = tmp;
626	55523x	heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
627	55523x	heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
628	55523x	}
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	4115x	get_timer_service(capy::execution_context& ctx, scheduler& sched)
648		{
649	4115x	return ctx.make_service<timer_service>(sched);
650		}
651
652		} // namespace boost::corosio::detail
653
654		#endif
655