Seastar
High performance C++ framework for concurrent servers
timer-set.hh
1/*
2 * Copyright (C) 2014 Cloudius Systems, Ltd.
3 */
4
5/*
6 * Imported from OSv:
7 *
8 * Copyright (C) 2014 Cloudius Systems, Ltd.
9 *
10 * This work is open source software, licensed under the terms of the
11 * BSD license as described in the LICENSE file in the top-level directory.
12 */
13
14#pragma once
15
16#include <seastar/core/bitset-iter.hh>
18#ifndef SEASTAR_MODULE
19#include <boost/intrusive/list.hpp>
20#include <exception>
21#include <array>
22#include <bitset>
23#include <limits>
24#endif
25
26namespace seastar {
27
28namespace internal {
29void log_timer_callback_exception(std::exception_ptr) noexcept;
30}
31
43template<typename Timer, boost::intrusive::list_member_hook<> Timer::*link>
44class timer_set {
45public:
46 using time_point = typename Timer::time_point;
47 using timer_list_t = boost::intrusive::list<Timer, boost::intrusive::member_hook<Timer, boost::intrusive::list_member_hook<>, link>>;
48private:
49 using duration = typename Timer::duration;
50 using timestamp_t = typename Timer::duration::rep;
51
52 static constexpr timestamp_t max_timestamp = std::numeric_limits<timestamp_t>::max();
53 static constexpr int timestamp_bits = std::numeric_limits<timestamp_t>::digits;
54
55 // The last bucket is reserved for active timers with timeout <= _last.
56 static constexpr int n_buckets = timestamp_bits + 1;
57
58 std::array<timer_list_t, n_buckets> _buckets;
59 timestamp_t _last;
60 timestamp_t _next;
61
62 std::bitset<n_buckets> _non_empty_buckets;
63private:
64 static timestamp_t get_timestamp(time_point _time_point) noexcept
65 {
66 return _time_point.time_since_epoch().count();
67 }
68
69 static timestamp_t get_timestamp(Timer& timer) noexcept
70 {
71 return get_timestamp(timer.get_timeout());
72 }
73
74 int get_index(timestamp_t timestamp) const noexcept
75 {
76 if (timestamp <= _last) {
77 return n_buckets - 1;
78 }
79
80 auto index = bitsets::count_leading_zeros(timestamp ^ _last);
81 assert(index < n_buckets - 1);
82 return index;
83 }
84
85 int get_index(Timer& timer) const noexcept
86 {
87 return get_index(get_timestamp(timer));
88 }
89
90 int get_last_non_empty_bucket() const noexcept
91 {
92 return bitsets::get_last_set(_non_empty_buckets);
93 }
94
95public:
96 timer_set() noexcept
97 : _last(0)
98 , _next(max_timestamp)
99 , _non_empty_buckets(0)
100 {
101 }
102
103 ~timer_set() {
104 for (auto&& list : _buckets) {
105 while (!list.empty()) {
106 auto& timer = *list.begin();
107 timer.cancel();
108 }
109 }
110 }
111
129 bool insert(Timer& timer) noexcept
130 {
131 auto timestamp = get_timestamp(timer);
132 auto index = get_index(timestamp);
133
134 _buckets[index].push_back(timer);
135 _non_empty_buckets[index] = true;
136
137 if (timestamp < _next) {
138 _next = timestamp;
139 return true;
140 }
141 return false;
142 }
143
155 void remove(Timer& timer) noexcept
156 {
157 auto index = get_index(timer);
158 auto& list = _buckets[index];
159 list.erase(list.iterator_to(timer));
160 if (list.empty()) {
161 _non_empty_buckets[index] = false;
162 }
163 }
164
168 void remove(Timer& timer, timer_list_t& expired) noexcept
169 {
170 if (timer._expired) {
171 expired.erase(expired.iterator_to(timer));
172 timer._expired = false;
173 } else {
174 remove(timer);
175 }
176 }
177
192 timer_list_t expire(time_point now) noexcept
193 {
194 timer_list_t exp;
195 auto timestamp = get_timestamp(now);
196
197 if (timestamp < _last) {
198 abort();
199 }
200
201 auto index = get_index(timestamp);
202
203 for (int i : bitsets::for_each_set(_non_empty_buckets, index + 1)) {
204 exp.splice(exp.end(), _buckets[i]);
205 _non_empty_buckets[i] = false;
206 }
207
208 _last = timestamp;
209 _next = max_timestamp;
210
211 auto& list = _buckets[index];
212 while (!list.empty()) {
213 auto& timer = *list.begin();
214 list.pop_front();
215 if (timer.get_timeout() <= now) {
216 exp.push_back(timer);
217 } else {
218 insert(timer);
219 }
220 }
221
222 _non_empty_buckets[index] = !list.empty();
223
224 if (_next == max_timestamp && _non_empty_buckets.any()) {
225 for (auto& timer : _buckets[get_last_non_empty_bucket()]) {
226 _next = std::min(_next, get_timestamp(timer));
227 }
228 }
229 return exp;
230 }
231
232 template <typename EnableFunc>
233 void complete(timer_list_t& expired_timers, EnableFunc&& enable_fn) noexcept(noexcept(enable_fn())) {
234 expired_timers = expire(this->now());
235 for (auto& t : expired_timers) {
236 t._expired = true;
237 }
238 const auto prev_sg = current_scheduling_group();
239 while (!expired_timers.empty()) {
240 auto t = &*expired_timers.begin();
241 expired_timers.pop_front();
242 t->_queued = false;
243 if (t->_armed) {
244 t->_armed = false;
245 if (t->_period) {
246 t->readd_periodic();
247 }
248 try {
249 *internal::current_scheduling_group_ptr() = t->_sg;
250 t->_callback();
251 } catch (...) {
252 internal::log_timer_callback_exception(std::current_exception());
253 }
254 }
255 }
256 // complete_timers() can be called from the context of run_tasks()
257 // as well so we need to restore the previous scheduling group (set by run_tasks()).
258 *internal::current_scheduling_group_ptr() = prev_sg;
259 enable_fn();
260 }
261
268 time_point get_next_timeout() const noexcept
269 {
270 return time_point(duration(std::max(_last, _next)));
271 }
272
276 void clear() noexcept
277 {
278 for (int i : bitsets::for_each_set(_non_empty_buckets)) {
279 _buckets[i].clear();
280 }
281 }
282
283 size_t size() const noexcept
284 {
285 size_t res = 0;
286 for (int i : bitsets::for_each_set(_non_empty_buckets)) {
287 res += _buckets[i].size();
288 }
289 return res;
290 }
291
295 bool empty() const noexcept
296 {
297 return _non_empty_buckets.none();
298 }
299
300 time_point now() noexcept {
301 return Timer::clock::now();
302 }
303};
304}
Definition: timer-set.hh:44
bool insert(Timer &timer) noexcept
Definition: timer-set.hh:129
void clear() noexcept
Definition: timer-set.hh:276
time_point get_next_timeout() const noexcept
Definition: timer-set.hh:268
void remove(Timer &timer, timer_list_t &expired) noexcept
Definition: timer-set.hh:168
timer_list_t expire(time_point now) noexcept
Definition: timer-set.hh:192
void remove(Timer &timer) noexcept
Definition: timer-set.hh:155
bool empty() const noexcept
Definition: timer-set.hh:295
Definition: timer.hh:83
time_point get_timeout() const noexcept
Definition: timer.hh:217
bool cancel() noexcept
future now()
Returns a ready future.
Definition: later.hh:35
Seastar API namespace.
Definition: abort_on_ebadf.hh:26
scheduling_group current_scheduling_group() noexcept
Returns the current scheduling group.
Definition: scheduling.hh:397