2 * Copyright 2016 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include <folly/Optional.h>
20 #include <folly/io/async/AsyncTimeout.h>
21 #include <folly/io/async/DelayedDestruction.h>
23 #include <boost/intrusive/list.hpp>
24 #include <glog/logging.h>
34 * Hashed Hierarchical Wheel Timer
37 * AsyncTimeout - a single timeout.
38 * HHWheelTimer - a set of efficient timeouts with different interval,
39 * but timeouts are not exact.
41 * All of the above are O(1) in insertion, tick update and cancel
43 * This implementation ticks once every 10ms.
44 * We model timers as the number of ticks until the next
45 * due event. We allow 32-bits of space to track this
46 * due interval, and break that into 4 regions of 8 bits.
47 * Each region indexes into a bucket of 256 lists.
49 * Bucket 0 represents those events that are due the soonest.
50 * Each tick causes us to look at the next list in a bucket.
51 * The 0th list in a bucket is special; it means that it is time to
52 * flush the timers from the next higher bucket and schedule them
53 * into a different bucket.
55 * This technique results in a very cheap mechanism for
56 * maintaining time and timers, provided that we can maintain
57 * a consistent rate of ticks.
59 class HHWheelTimer : private folly::AsyncTimeout,
60 public folly::DelayedDestruction {
62 // This type has always been a misnomer, because it is not a unique pointer.
63 using UniquePtr = std::unique_ptr<HHWheelTimer, Destructor>;
64 using SharedPtr = IntrusivePtr<HHWheelTimer>;
66 template <typename... Args>
67 static UniquePtr newTimer(Args&&... args) {
68 return UniquePtr(new HHWheelTimer(std::forward<Args>(args)...));
72 * A callback to be notified when a timeout has expired.
83 * timeoutExpired() is invoked when the timeout has expired.
85 virtual void timeoutExpired() noexcept = 0;
87 /// This callback was canceled. The default implementation is to just
88 /// proxy to `timeoutExpired` but if you care about the difference between
89 /// the timeout finishing or being canceled you can override this.
90 virtual void callbackCanceled() noexcept {
95 * Cancel the timeout, if it is running.
97 * If the timeout is not scheduled, cancelTimeout() does nothing.
99 void cancelTimeout() {
100 if (wheel_ == nullptr) {
101 // We're not scheduled, so there's nothing to do.
108 * Return true if this timeout is currently scheduled, and false otherwise.
110 bool isScheduled() const {
111 return wheel_ != nullptr;
116 * Don't override this unless you're doing a test. This is mainly here so
117 * that we can override it to simulate lag in steady_clock.
119 virtual std::chrono::milliseconds getCurTime() {
120 return std::chrono::duration_cast<std::chrono::milliseconds>(
121 std::chrono::steady_clock::now().time_since_epoch());
125 // Get the time remaining until this timeout expires
126 std::chrono::milliseconds getTimeRemaining(
127 std::chrono::milliseconds now) const {
128 if (now >= expiration_) {
129 return std::chrono::milliseconds(0);
131 return expiration_ - now;
134 void setScheduled(HHWheelTimer* wheel,
135 std::chrono::milliseconds);
136 void cancelTimeoutImpl();
138 HHWheelTimer* wheel_;
139 folly::Optional<DestructorGuard> wheelGuard_;
140 std::chrono::milliseconds expiration_;
142 typedef boost::intrusive::list_member_hook<
143 boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
147 typedef boost::intrusive::list<
149 boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
150 boost::intrusive::constant_time_size<false> > List;
152 std::shared_ptr<RequestContext> context_;
154 // Give HHWheelTimer direct access to our members so it can take care
155 // of scheduling/cancelling.
156 friend class HHWheelTimer;
160 * Create a new HHWheelTimer with the specified interval and the
161 * default timeout value set.
163 * Objects created using this version of constructor can be used
164 * to schedule both variable interval timeouts using
165 * scheduleTimeout(callback, timeout) method, and default
166 * interval timeouts using scheduleTimeout(callback) method.
168 static int DEFAULT_TICK_INTERVAL;
169 explicit HHWheelTimer(
170 folly::TimeoutManager* timeoutManager,
171 std::chrono::milliseconds intervalMS =
172 std::chrono::milliseconds(DEFAULT_TICK_INTERVAL),
173 AsyncTimeout::InternalEnum internal = AsyncTimeout::InternalEnum::NORMAL,
174 std::chrono::milliseconds defaultTimeoutMS =
175 std::chrono::milliseconds(-1));
178 * Destroy the HHWheelTimer.
180 * A HHWheelTimer should only be destroyed when there are no more
181 * callbacks pending in the set. (If it helps you may use cancelAll() to
182 * cancel all pending timeouts explicitly before calling this.)
184 * However, it is OK to invoke this function (or via UniquePtr dtor) while
185 * there are outstanding DestructorGuard's or HHWheelTimer::SharedPtr's.
187 virtual void destroy();
190 * Cancel all outstanding timeouts
192 * @returns the number of timeouts that were cancelled.
197 * Get the tick interval for this HHWheelTimer.
199 * Returns the tick interval in milliseconds.
201 std::chrono::milliseconds getTickInterval() const {
206 * Get the default timeout interval for this HHWheelTimer.
208 * Returns the timeout interval in milliseconds.
210 std::chrono::milliseconds getDefaultTimeout() const {
211 return defaultTimeout_;
215 * Schedule the specified Callback to be invoked after the
216 * specified timeout interval.
218 * If the callback is already scheduled, this cancels the existing timeout
219 * before scheduling the new timeout.
221 void scheduleTimeout(Callback* callback,
222 std::chrono::milliseconds timeout);
223 void scheduleTimeoutImpl(Callback* callback,
224 std::chrono::milliseconds timeout);
227 * Schedule the specified Callback to be invoked after the
228 * fefault timeout interval.
230 * If the callback is already scheduled, this cancels the existing timeout
231 * before scheduling the new timeout.
233 * This method uses CHECK() to make sure that the default timeout was
234 * specified on the object initialization.
236 void scheduleTimeout(Callback* callback);
239 void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
240 struct Wrapper : Callback {
241 Wrapper(F f) : fn_(std::move(f)) {}
242 void timeoutExpired() noexcept override {
245 } catch (std::exception const& e) {
246 LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
249 LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
255 Wrapper* w = new Wrapper(std::move(fn));
256 scheduleTimeout(w, timeout);
260 * Return the number of currently pending timeouts
262 uint64_t count() const {
267 * This turns on more exact timing. By default the wheel timer
268 * increments its cached time only once everyN (default) ticks.
270 * With catchupEveryN at 1, timeouts will only be delayed until the
271 * next tick, at which point all overdue timeouts are called. The
272 * wheel timer is approximately 2x slower with this set to 1.
274 * Load testing in opt mode showed skew was about 1% with no catchup.
276 void setCatchupEveryN(uint32_t everyN) {
277 catchupEveryN_ = everyN;
280 bool isDetachable() const {
281 return !folly::AsyncTimeout::isScheduled();
284 using folly::AsyncTimeout::attachEventBase;
285 using folly::AsyncTimeout::detachEventBase;
286 using folly::AsyncTimeout::getTimeoutManager;
290 * Protected destructor.
292 * Use destroy() instead. See the comments in DelayedDestruction for more
295 virtual ~HHWheelTimer();
298 // Forbidden copy constructor and assignment operator
299 HHWheelTimer(HHWheelTimer const &) = delete;
300 HHWheelTimer& operator=(HHWheelTimer const &) = delete;
302 // Methods inherited from AsyncTimeout
303 virtual void timeoutExpired() noexcept;
305 std::chrono::milliseconds interval_;
306 std::chrono::milliseconds defaultTimeout_;
308 static constexpr int WHEEL_BUCKETS = 4;
309 static constexpr int WHEEL_BITS = 8;
310 static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
311 static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
312 static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
314 typedef Callback::List CallbackList;
315 CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
317 int64_t timeToWheelTicks(std::chrono::milliseconds t) {
318 return t.count() / interval_.count();
321 bool cascadeTimers(int bucket, int tick);
324 std::chrono::milliseconds now_;
326 static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
328 uint32_t catchupEveryN_;
329 uint32_t expirationsSinceCatchup_;
330 bool processingCallbacksGuard_;