2 * Copyright 2017 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
36 * We model timers as the number of ticks until the next
37 * due event. We allow 32-bits of space to track this
38 * due interval, and break that into 4 regions of 8 bits.
39 * Each region indexes into a bucket of 256 lists.
41 * Bucket 0 represents those events that are due the soonest.
42 * Each tick causes us to look at the next list in a bucket.
43 * The 0th list in a bucket is special; it means that it is time to
44 * flush the timers from the next higher bucket and schedule them
45 * into a different bucket.
47 * This technique results in a very cheap mechanism for
48 * maintaining time and timers.
50 * Unlike the original timer wheel paper, this implementation does
51 * *not* tick constantly, and instead calculates the exact next wakeup
54 class HHWheelTimer : private folly::AsyncTimeout,
55 public folly::DelayedDestruction {
57 using UniquePtr = std::unique_ptr<HHWheelTimer, Destructor>;
58 using SharedPtr = std::shared_ptr<HHWheelTimer>;
60 template <typename... Args>
61 static UniquePtr newTimer(Args&&... args) {
62 return UniquePtr(new HHWheelTimer(std::forward<Args>(args)...));
66 * A callback to be notified when a timeout has expired.
69 : public boost::intrusive::list_base_hook<
70 boost::intrusive::link_mode<boost::intrusive::auto_unlink>> {
76 * timeoutExpired() is invoked when the timeout has expired.
78 virtual void timeoutExpired() noexcept = 0;
80 /// This callback was canceled. The default implementation is to just
81 /// proxy to `timeoutExpired` but if you care about the difference between
82 /// the timeout finishing or being canceled you can override this.
83 virtual void callbackCanceled() noexcept {
88 * Cancel the timeout, if it is running.
90 * If the timeout is not scheduled, cancelTimeout() does nothing.
92 void cancelTimeout() {
93 if (wheel_ == nullptr) {
94 // We're not scheduled, so there's nothing to do.
101 * Return true if this timeout is currently scheduled, and false otherwise.
103 bool isScheduled() const {
104 return wheel_ != nullptr;
108 * Get the time remaining until this timeout expires. Return 0 if this
109 * timeout is not scheduled or expired. Otherwise, return expiration time
110 * minus getCurTime().
112 std::chrono::milliseconds getTimeRemaining() {
113 return getTimeRemaining(getCurTime());
118 * Don't override this unless you're doing a test. This is mainly here so
119 * that we can override it to simulate lag in steady_clock.
121 virtual std::chrono::steady_clock::time_point getCurTime() {
122 return std::chrono::steady_clock::now();
126 // Get the time remaining until this timeout expires
127 std::chrono::milliseconds getTimeRemaining(
128 std::chrono::steady_clock::time_point now) const {
129 if (now >= expiration_) {
130 return std::chrono::milliseconds(0);
132 return std::chrono::duration_cast<std::chrono::milliseconds>(
136 void setScheduled(HHWheelTimer* wheel,
137 std::chrono::milliseconds);
138 void cancelTimeoutImpl();
140 HHWheelTimer* wheel_{nullptr};
141 std::chrono::steady_clock::time_point expiration_{};
144 typedef boost::intrusive::list<
146 boost::intrusive::constant_time_size<false> > List;
148 std::shared_ptr<RequestContext> context_;
150 // Give HHWheelTimer direct access to our members so it can take care
151 // of scheduling/cancelling.
152 friend class HHWheelTimer;
156 * Create a new HHWheelTimer with the specified interval and the
157 * default timeout value set.
159 * Objects created using this version of constructor can be used
160 * to schedule both variable interval timeouts using
161 * scheduleTimeout(callback, timeout) method, and default
162 * interval timeouts using scheduleTimeout(callback) method.
164 static int DEFAULT_TICK_INTERVAL;
165 explicit HHWheelTimer(
166 folly::TimeoutManager* timeoutManager,
167 std::chrono::milliseconds intervalMS =
168 std::chrono::milliseconds(DEFAULT_TICK_INTERVAL),
169 AsyncTimeout::InternalEnum internal = AsyncTimeout::InternalEnum::NORMAL,
170 std::chrono::milliseconds defaultTimeoutMS =
171 std::chrono::milliseconds(-1));
174 * Cancel all outstanding timeouts
176 * @returns the number of timeouts that were cancelled.
181 * Get the tick interval for this HHWheelTimer.
183 * Returns the tick interval in milliseconds.
185 std::chrono::milliseconds getTickInterval() const {
190 * Get the default timeout interval for this HHWheelTimer.
192 * Returns the timeout interval in milliseconds.
194 std::chrono::milliseconds getDefaultTimeout() const {
195 return defaultTimeout_;
199 * Schedule the specified Callback to be invoked after the
200 * specified timeout interval.
202 * If the callback is already scheduled, this cancels the existing timeout
203 * before scheduling the new timeout.
205 void scheduleTimeout(Callback* callback,
206 std::chrono::milliseconds timeout);
207 void scheduleTimeoutImpl(Callback* callback,
208 std::chrono::milliseconds timeout);
211 * Schedule the specified Callback to be invoked after the
212 * default timeout interval.
214 * If the callback is already scheduled, this cancels the existing timeout
215 * before scheduling the new timeout.
217 * This method uses CHECK() to make sure that the default timeout was
218 * specified on the object initialization.
220 void scheduleTimeout(Callback* callback);
223 void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
224 struct Wrapper : Callback {
225 Wrapper(F f) : fn_(std::move(f)) {}
226 void timeoutExpired() noexcept override {
229 } catch (std::exception const& e) {
230 LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
233 LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
239 Wrapper* w = new Wrapper(std::move(fn));
240 scheduleTimeout(w, timeout);
244 * Return the number of currently pending timeouts
246 uint64_t count() const {
250 bool isDetachable() const {
251 return !folly::AsyncTimeout::isScheduled();
254 using folly::AsyncTimeout::attachEventBase;
255 using folly::AsyncTimeout::detachEventBase;
256 using folly::AsyncTimeout::getTimeoutManager;
260 * Protected destructor.
262 * Use destroy() instead. See the comments in DelayedDestruction for more
265 ~HHWheelTimer() override;
268 // Forbidden copy constructor and assignment operator
269 HHWheelTimer(HHWheelTimer const &) = delete;
270 HHWheelTimer& operator=(HHWheelTimer const &) = delete;
272 // Methods inherited from AsyncTimeout
273 void timeoutExpired() noexcept override;
275 std::chrono::milliseconds interval_;
276 std::chrono::milliseconds defaultTimeout_;
278 static constexpr int WHEEL_BUCKETS = 4;
279 static constexpr int WHEEL_BITS = 8;
280 static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
281 static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
282 static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
284 typedef Callback::List CallbackList;
285 CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
286 std::vector<uint64_t> bitmap_;
288 int64_t timeToWheelTicks(std::chrono::milliseconds t) {
289 return t.count() / interval_.count();
292 bool cascadeTimers(int bucket, int tick);
296 std::chrono::steady_clock::time_point startTime_;
298 int64_t calcNextTick();
300 void scheduleNextTimeout();
302 bool* processingCallbacksGuard_;
303 CallbackList timeouts; // Timeouts queued to run
305 std::chrono::steady_clock::time_point getCurTime() {
306 return std::chrono::steady_clock::now();