include/boost/corosio/detail/timer_service.hpp

89.1% Lines (213/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	1410x	callback() = default;
101
102		/// Construct a callback with the given context and function.
103	1410x	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	9873x	void operator()() const
113		{
114	9873x	if (fn_)
115	9873x	fn_(ctx_);
116	9873x	}
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	1410x	inline timer_service(capy::execution_context&, scheduler& sched)
142	1410x	: sched_(&sched)
143		{
144	1410x	}
145
146		/// Return the associated scheduler.
147	19944x	inline scheduler& get_scheduler() noexcept
148		{
149	19944x	return *sched_;
150		}
151
152		/// Destroy the timer service.
153	2820x	~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	1410x	inline void set_on_earliest_changed(callback cb)
160		{
161	1410x	on_earliest_changed_ = cb;
162	1410x	}
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	294358x	inline time_point nearest_expiry() const noexcept
173		{
174	294358x	auto ns = cached_nearest_ns_.load(std::memory_order_acquire);
175	294358x	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	333584x	inline void refresh_cached_nearest() noexcept
204		{
205	333584x	auto ns = heap_.empty() ? (std::numeric_limits<std::int64_t>::max)()
206	330373x	: heap_[0].time_.time_since_epoch().count();
207	333584x	cached_nearest_ns_.store(ns, std::memory_order_release);
208	333584x	}
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	37x	~tl_cache_owner()
232		{
233	37x	delete tl_cached_impl.get();
234	37x	tl_cached_impl.set(nullptr);
235	37x	}
236		};
237
238		inline void
239	10779x	arm_tl_cache_cleanup() noexcept
240		{
241	10779x	thread_local tl_cache_owner owner;
242		(void)owner;
243	10779x	}
244
245		inline timer::implementation*
246	10853x	try_pop_tl_cache(timer_service* svc) noexcept
247		{
248	10853x	auto* impl = tl_cached_impl.get();
249	10853x	if (impl)
250		{
251	10536x	tl_cached_impl.set(nullptr);
252	10536x	if (impl->svc_ == svc)
253	10536x	return impl;
254		// Stale impl from a destroyed service
255	✗	delete impl;
256		}
257	317x	return nullptr;
258		}
259
260		inline bool
261	10825x	try_push_tl_cache(timer::implementation* impl) noexcept
262		{
263	10825x	if (!tl_cached_impl.get())
264		{
265	10779x	arm_tl_cache_cleanup();
266	10779x	tl_cached_impl.set(impl);
267	10779x	return true;
268		}
269	46x	return false;
270		}
271
272		inline void
273	1410x	timer_service_invalidate_cache() noexcept
274		{
275	1410x	delete tl_cached_impl.get();
276	1410x	tl_cached_impl.set(nullptr);
277	1410x	}
278
279		// timer_service out-of-class member function definitions
280
281		inline void
282	1410x	timer_service::shutdown()
283		{
284	1410x	timer_service_invalidate_cache();
285	1410x	shutting_down_ = true;
286
287		// Snapshot impls and detach them from the heap so that
288		// coroutine-owned timer destructors (triggered by h.destroy()
289		// below) cannot re-enter remove_timer_impl() and mutate the
290		// vector during iteration.
291	1410x	std::vector<timer::implementation*> impls;
292	1410x	impls.reserve(heap_.size());
293	1438x	for (auto& entry : heap_)
294		{
295	28x	entry.timer_->heap_index_.store(
296		(std::numeric_limits<std::size_t>::max)(),
297		std::memory_order_relaxed);
298	28x	impls.push_back(entry.timer_);
299		}
300	1410x	heap_.clear();
301	1410x	cached_nearest_ns_.store(
302		(std::numeric_limits<std::int64_t>::max)(), std::memory_order_release);
303
304		// Cancel waiting timers. Each waiter called work_started()
305		// in implementation::wait(). On IOCP the scheduler shutdown
306		// loop exits when outstanding_work_ reaches zero, so we must
307		// call work_finished() here to balance it. On other backends
308		// this is harmless.
309	1438x	for (auto* impl : impls)
310		{
311	28x	if (auto* w = std::exchange(impl->waiter_, nullptr))
312		{
313	28x	w->reset_stop_cb();
314	28x	auto h = std::exchange(w->h_, {});
315	28x	sched_->work_finished();
316		// Destroying the frame also ends the node's storage
317	28x	if (h)
318	28x	h.destroy();
319		}
320	28x	delete impl;
321		}
322
323		// Delete free-listed impls
324	1456x	while (free_list_)
325		{
326	46x	auto* next = free_list_->next_free_;
327	46x	delete free_list_;
328	46x	free_list_ = next;
329		}
330	1410x	}
331
332		inline io_object::implementation*
333	10853x	timer_service::construct()
334		{
335	10853x	timer::implementation* impl = try_pop_tl_cache(this);
336	10853x	if (impl)
337		{
338	10536x	impl->svc_ = this;
339		// Reset expiry_ too: a recycled impl must behave like a fresh
340		// one, whose default expiry reads as already elapsed
341	10536x	impl->expiry_ = {};
342	10536x	impl->heap_index_.store(
343		(std::numeric_limits<std::size_t>::max)(),
344		std::memory_order_relaxed);
345	10536x	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
346	10536x	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
347	10536x	return impl;
348		}
349
350	317x	std::lock_guard lock(mutex_);
351	317x	if (free_list_)
352		{
353	✗	impl = free_list_;
354	✗	free_list_ = impl->next_free_;
355	✗	impl->next_free_ = nullptr;
356	✗	impl->svc_ = this;
357	✗	impl->expiry_ = {};
358	✗	impl->heap_index_.store(
359		(std::numeric_limits<std::size_t>::max)(),
360		std::memory_order_relaxed);
361	✗	impl->might_have_pending_waits_.store(false, std::memory_order_relaxed);
362	✗	BOOST_COROSIO_ASSERT(impl->waiter_ == nullptr);
363		}
364		else
365		{
366	317x	impl = new timer::implementation(*this);
367		}
368	317x	return impl;
369	317x	}
370
371		inline void
372	10853x	timer_service::destroy(io_object::implementation* p)
373		{
374		// During shutdown the drain loop owns every impl and deletes
375		// them directly. A frame destroyed by that loop can unwind a
376		// handle whose impl was freed in an earlier iteration (a
377		// timeout's parent frame owns the timeout timer while
378		// suspended on the inner delay's timer), so bail out before
379		// even downcasting the pointer.
380	10853x	if (shutting_down_)
381	28x	return;
382	10825x	destroy_impl(static_cast<timer::implementation&>(*p));
383		}
384
385		inline void
386	10825x	timer_service::destroy_impl(timer::implementation& impl)
387		{
388		// During shutdown the impl is owned by the shutdown loop.
389		// Re-entering here (from a coroutine-owned timer destructor
390		// triggered by h.destroy()) must not modify the heap or
391		// recycle the impl — shutdown deletes it directly.
392	10825x	if (shutting_down_)
393	10779x	return;
394
395	10825x	cancel_timer(impl);
396
397	21650x	if (impl.heap_index_.load(std::memory_order_relaxed) !=
398	10825x	(std::numeric_limits<std::size_t>::max)())
399		{
400	✗	std::lock_guard lock(mutex_);
401	✗	remove_timer_impl(impl);
402	✗	refresh_cached_nearest();
403	✗	}
404
405	10825x	if (try_push_tl_cache(&impl))
406	10779x	return;
407
408	46x	std::lock_guard lock(mutex_);
409	46x	impl.next_free_ = free_list_;
410	46x	free_list_ = &impl;
411	46x	}
412
413		inline void
414	9998x	timer_service::insert_waiter(timer::implementation& impl, waiter_node* w)
415		{
416	9998x	bool notify = false;
417	9998x	bool lost_cancel = false;
418		{
419	9998x	std::lock_guard lock(mutex_);
420		// Grow before publishing anything, so the push_back below
421		// cannot throw: a failure here leaves the waiter untouched,
422		// the strong guarantee rearm_wait's recovery relies on.
423	9998x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
424	19996x	(std::numeric_limits<std::size_t>::max)() &&
425	9998x	heap_.size() == heap_.capacity())
426	245x	heap_.reserve(
427	245x	heap_.capacity() == 0 ? 16 : 2 * heap_.capacity());
428		// Publish: from here the waiter is visible to the fire path and
429		// to its own stop callback (impl_ non-null enables cancel_waiter).
430	9998x	w->impl_ = &impl;
431	19996x	if (impl.heap_index_.load(std::memory_order_relaxed) ==
432	9998x	(std::numeric_limits<std::size_t>::max)())
433		{
434	9998x	impl.heap_index_.store(heap_.size(), std::memory_order_relaxed);
435	9998x	heap_.push_back({impl.expiry_, &impl});
436	9998x	up_heap(heap_.size() - 1);
437	9998x	notify =
438	9998x	(impl.heap_index_.load(std::memory_order_relaxed) == 0);
439	9998x	refresh_cached_nearest();
440		}
441	9998x	BOOST_COROSIO_ASSERT(impl.waiter_ == nullptr);
442	9998x	impl.waiter_ = w;
443
444		// Lost-cancel re-check: a stop requested after the canceller was
445		// armed in wait() but before this publication found impl_ null
446		// and returned a no-op. Observe it now and undo the insertion.
447	9998x	if (w->token_->stop_requested())
448		{
449	✗	w->impl_ = nullptr;
450	✗	impl.waiter_ = nullptr;
451	✗	remove_timer_impl(impl);
452	✗	impl.might_have_pending_waits_.store(
453		false, std::memory_order_relaxed);
454	✗	refresh_cached_nearest();
455	✗	lost_cancel = true;
456	✗	notify = false; // insertion undone; nearest unchanged
457		}
458	9998x	}
459	9998x	if (notify)
460	9873x	on_earliest_changed_();
461	9998x	if (lost_cancel)
462		{
463	✗	w->ec_ = make_error_code(capy::error::canceled);
464	✗	sched_->post(&w->op_);
465		}
466	9998x	}
467
468		inline void
469	10825x	timer_service::cancel_timer(timer::implementation& impl)
470		{
471	10825x	if (!impl.might_have_pending_waits_.load(std::memory_order_relaxed))
472	10823x	return;
473
474		// No unlocked already-done fast-out here: it would need the
475		// non-atomic waiter_ (a race with concurrent drains), and an
476		// index-only check is lifetime-unsafe because npos is stored
477		// before the drain finishes touching the impl. A stale-true
478		// flag is rare with the stateless API; the locked path below
479		// re-validates.
480
481	2x	waiter_node* canceled = nullptr;
482
483		{
484	2x	std::lock_guard lock(mutex_);
485	2x	remove_timer_impl(impl);
486	2x	canceled = std::exchange(impl.waiter_, nullptr);
487	2x	if (canceled)
488	2x	canceled->impl_ = nullptr;
489		// Store false as the final touch of the impl under the lock so
490		// a pre-lock false-flag check trusts it unqualified.
491	2x	impl.might_have_pending_waits_.store(false, std::memory_order_relaxed);
492	2x	refresh_cached_nearest();
493	2x	}
494
495	2x	if (canceled)
496		{
497	2x	canceled->ec_ = make_error_code(capy::error::canceled);
498	2x	sched_->post(&canceled->op_);
499		}
500		}
501
502		inline void
503	1394x	timer_service::cancel_waiter(waiter_node* w)
504		{
505		{
506	1394x	std::lock_guard lock(mutex_);
507		// Already removed by another drain: cancel_timer,
508		// process_expired, or insert_waiter's lost-cancel recheck
509	1394x	if (!w->impl_)
510	✗	return;
511	1394x	auto* impl = w->impl_;
512	1394x	w->impl_ = nullptr;
513	1394x	impl->waiter_ = nullptr;
514	1394x	remove_timer_impl(*impl);
515	1394x	impl->might_have_pending_waits_.store(
516		false, std::memory_order_relaxed);
517	1394x	refresh_cached_nearest();
518	1394x	}
519
520	1394x	w->ec_ = make_error_code(capy::error::canceled);
521	1394x	sched_->post(&w->op_);
522		}
523
524		inline std::size_t
525	322190x	timer_service::process_expired()
526		{
527	322190x	intrusive_list<waiter_node> expired;
528
529		{
530	322190x	std::lock_guard lock(mutex_);
531	322190x	auto now = clock_type::now();
532
533	330764x	while (!heap_.empty() && heap_[0].time_ <= now)
534		{
535	8574x	timer::implementation* t = heap_[0].timer_;
536	8574x	remove_timer_impl(*t);
537	8574x	if (auto* w = std::exchange(t->waiter_, nullptr))
538		{
539	8574x	w->impl_ = nullptr;
540	8574x	w->ec_ = {};
541	8574x	expired.push_back(w);
542		}
543	8574x	t->might_have_pending_waits_.store(
544		false, std::memory_order_relaxed);
545		}
546
547	322190x	refresh_cached_nearest();
548	322190x	}
549
550	322190x	std::size_t count = 0;
551	330764x	while (auto* w = expired.pop_front())
552		{
553	8574x	sched_->post(&w->op_);
554	8574x	++count;
555	8574x	}
556
557	322190x	return count;
558		}
559
560		inline void
561	9970x	timer_service::remove_timer_impl(timer::implementation& impl)
562		{
563	9970x	std::size_t index = impl.heap_index_.load(std::memory_order_relaxed);
564	9970x	if (index >= heap_.size())
565	✗	return; // Not in heap
566
567	9970x	if (index == heap_.size() - 1)
568		{
569		// Last element, just pop
570	1633x	impl.heap_index_.store(
571		(std::numeric_limits<std::size_t>::max)(),
572		std::memory_order_relaxed);
573	1633x	heap_.pop_back();
574		}
575		else
576		{
577		// Swap with last and reheapify
578	8337x	swap_heap(index, heap_.size() - 1);
579	8337x	impl.heap_index_.store(
580		(std::numeric_limits<std::size_t>::max)(),
581		std::memory_order_relaxed);
582	8337x	heap_.pop_back();
583
584	8337x	if (index > 0 && heap_[index].time_ < heap_[(index - 1) / 2].time_)
585	✗	up_heap(index);
586		else
587	8337x	down_heap(index);
588		}
589		}
590
591		inline void
592	9998x	timer_service::up_heap(std::size_t index)
593		{
594	18305x	while (index > 0)
595		{
596	8432x	std::size_t parent = (index - 1) / 2;
597	8432x	if (!(heap_[index].time_ < heap_[parent].time_))
598	125x	break;
599	8307x	swap_heap(index, parent);
600	8307x	index = parent;
601		}
602	9998x	}
603
604		inline void
605	8337x	timer_service::down_heap(std::size_t index)
606		{
607	8337x	std::size_t child = index * 2 + 1;
608	8339x	while (child < heap_.size())
609		{
610	4x	std::size_t min_child = (child + 1 == heap_.size() \|\|
611	✗	heap_[child].time_ < heap_[child + 1].time_)
612	4x	? child
613	4x	: child + 1;
614
615	4x	if (heap_[index].time_ < heap_[min_child].time_)
616	2x	break;
617
618	2x	swap_heap(index, min_child);
619	2x	index = min_child;
620	2x	child = index * 2 + 1;
621		}
622	8337x	}
623
624		inline void
625	16646x	timer_service::swap_heap(std::size_t i1, std::size_t i2)
626		{
627	16646x	heap_entry tmp = heap_[i1];
628	16646x	heap_[i1] = heap_[i2];
629	16646x	heap_[i2] = tmp;
630	16646x	heap_[i1].timer_->heap_index_.store(i1, std::memory_order_relaxed);
631	16646x	heap_[i2].timer_->heap_index_.store(i2, std::memory_order_relaxed);
632	16646x	}
633
634		// waiter_node's completion_op and canceller members are defined in
635		// timer.cpp alongside implementation::wait(), for the same reason
636		// wait() lives there (see below).
637
638		// timer::implementation::wait() is defined in timer.cpp, not here.
639		// It must be a non-inline definition in a translation unit that is
640		// always pulled into the link whenever detail::timer is used (every
641		// consumer needs timer's constructors from that same object file).
642		// An inline definition in this header would only be emitted in
643		// translation units that happen to also include this header, which
644		// is not guaranteed for every caller of wait_awaitable::await_suspend
645		// in timer.hpp (e.g. code that only reaches timer.hpp through
646		// delay.hpp, without transitively including a scheduler header).
647
648		// Free functions
649
650		inline timer_service&
651	1410x	get_timer_service(capy::execution_context& ctx, scheduler& sched)
652		{
653	1410x	return ctx.make_service<timer_service>(sched);
654		}
655
656		} // namespace boost::corosio::detail
657
658		#endif
659