2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
19 #include <folly/io/async/HHWheelTimer.h>
20 #include <folly/io/async/Request.h>
22 #include <folly/ScopeGuard.h>
26 using std::chrono::milliseconds;
31 * We want to select the default interval carefully.
32 * An interval of 10ms will give us 10ms * WHEEL_SIZE^WHEEL_BUCKETS
33 * for the largest timeout possible, or about 497 days.
35 * For a lower bound, we want a reasonable limit on local IO, 10ms
38 * A shorter interval also has CPU implications, less than 1ms might
39 * start showing up in cpu perf. Also, it might not be possible to set
40 * tick interval less than 10ms on older kernels.
42 int HHWheelTimer::DEFAULT_TICK_INTERVAL = 10;
44 HHWheelTimer::Callback::~Callback() {
50 void HHWheelTimer::Callback::setScheduled(HHWheelTimer* wheel,
51 std::chrono::milliseconds timeout) {
52 assert(wheel_ == nullptr);
53 assert(expiration_ == milliseconds(0));
57 if (wheel_->count_ == 0) {
58 wheel_->now_ = std::chrono::duration_cast<milliseconds>(
59 std::chrono::steady_clock::now().time_since_epoch());
62 expiration_ = wheel_->now_ + timeout;
65 void HHWheelTimer::Callback::cancelTimeoutImpl() {
66 if (--wheel_->count_ <= 0) {
67 assert(wheel_->count_ == 0);
68 wheel_->AsyncTimeout::cancelTimeout();
73 expiration_ = milliseconds(0);
76 HHWheelTimer::HHWheelTimer(folly::EventBase* eventBase,
77 std::chrono::milliseconds intervalMS)
78 : AsyncTimeout(eventBase)
79 , interval_(intervalMS)
82 , catchupEveryN_(DEFAULT_CATCHUP_EVERY_N)
83 , expirationsSinceCatchup_(0)
87 HHWheelTimer::~HHWheelTimer() {
90 void HHWheelTimer::destroy() {
92 DelayedDestruction::destroy();
95 void HHWheelTimer::scheduleTimeoutImpl(Callback* callback,
96 std::chrono::milliseconds timeout) {
97 uint32_t due = timeToWheelTicks(timeout) + nextTick_;
98 int64_t diff = due - nextTick_;
101 if (diff < WHEEL_SIZE) {
102 list = &buckets_[0][due & WHEEL_MASK];
103 } else if (diff < 1 << (2 * WHEEL_BITS)) {
104 list = &buckets_[1][(due >> WHEEL_BITS) & WHEEL_MASK];
105 } else if (diff < 1 << (3 * WHEEL_BITS)) {
106 list = &buckets_[2][(due >> 2 * WHEEL_BITS) & WHEEL_MASK];
107 } else if (diff < 0) {
108 list = &buckets_[0][nextTick_ & WHEEL_MASK];
110 /* in largest slot */
111 if (diff > LARGEST_SLOT) {
113 due = diff + nextTick_;
115 list = &buckets_[3][(due >> 3 * WHEEL_BITS) & WHEEL_MASK];
117 list->push_back(*callback);
120 void HHWheelTimer::scheduleTimeout(Callback* callback,
121 std::chrono::milliseconds timeout) {
122 // Cancel the callback if it happens to be scheduled already.
123 callback->cancelTimeout();
125 callback->context_ = RequestContext::saveContext();
128 this->AsyncTimeout::scheduleTimeout(interval_.count());
131 callback->setScheduled(this, timeout);
132 scheduleTimeoutImpl(callback, timeout);
136 bool HHWheelTimer::cascadeTimers(int bucket, int tick) {
138 cbs.swap(buckets_[bucket][tick]);
139 while (!cbs.empty()) {
140 auto* cb = &cbs.front();
142 scheduleTimeoutImpl(cb, cb->getTimeRemaining(now_));
145 // If tick is zero, timeoutExpired will cascade the next bucket.
149 void HHWheelTimer::timeoutExpired() noexcept {
150 // If destroy() is called inside timeoutExpired(), delay actual destruction
151 // until timeoutExpired() returns
152 DestructorGuard dg(this);
154 // timeoutExpired() can only be invoked directly from the event base loop.
155 // It should never be invoked recursively.
157 milliseconds catchup = now_ + interval_;
158 // If catchup is enabled, we may have missed multiple intervals, use
159 // currentTime() to check exactly.
160 if (++expirationsSinceCatchup_ >= catchupEveryN_) {
161 catchup = std::chrono::duration_cast<milliseconds>(
162 std::chrono::steady_clock::now().time_since_epoch());
163 expirationsSinceCatchup_ = 0;
165 while (now_ < catchup) {
168 int idx = nextTick_ & WHEEL_MASK;
171 if (cascadeTimers(1, (nextTick_ >> WHEEL_BITS) & WHEEL_MASK) &&
172 cascadeTimers(2, (nextTick_ >> (2 * WHEEL_BITS)) & WHEEL_MASK)) {
173 cascadeTimers(3, (nextTick_ >> (3 * WHEEL_BITS)) & WHEEL_MASK);
178 CallbackList* cbs = &buckets_[0][idx];
179 while (!cbs->empty()) {
180 auto* cb = &cbs->front();
183 cb->wheel_ = nullptr;
184 cb->expiration_ = milliseconds(0);
186 RequestContext::setContext(cb->context_);
187 cb->timeoutExpired();
188 RequestContext::setContext(old_ctx);
192 this->AsyncTimeout::scheduleTimeout(interval_.count());