2 * Copyright 2015 Facebook, Inc.
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
12 * http://www.apache.org/licenses/LICENSE-2.0
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
21 #include <folly/io/async/HHWheelTimer.h>
22 #include <folly/io/async/Request.h>
24 #include <folly/ScopeGuard.h>
28 using std::chrono::milliseconds;
33 * We want to select the default interval carefully.
34 * An interval of 10ms will give us 10ms * WHEEL_SIZE^WHEEL_BUCKETS
35 * for the largest timeout possible, or about 497 days.
37 * For a lower bound, we want a reasonable limit on local IO, 10ms
40 * A shorter interval also has CPU implications, less than 1ms might
41 * start showing up in cpu perf. Also, it might not be possible to set
42 * tick interval less than 10ms on older kernels.
44 int HHWheelTimer::DEFAULT_TICK_INTERVAL = 10;
46 HHWheelTimer::Callback::~Callback() {
52 void HHWheelTimer::Callback::setScheduled(HHWheelTimer* wheel,
53 std::chrono::milliseconds timeout) {
54 assert(wheel_ == nullptr);
55 assert(expiration_ == milliseconds(0));
59 // Only update the now_ time if we're not in a timeout expired callback
60 if (wheel_->count_ == 0 && !wheel_->processingCallbacksGuard_) {
61 wheel_->now_ = getCurTime();
64 expiration_ = wheel_->now_ + timeout;
67 void HHWheelTimer::Callback::cancelTimeoutImpl() {
68 if (--wheel_->count_ <= 0) {
69 assert(wheel_->count_ == 0);
70 wheel_->AsyncTimeout::cancelTimeout();
75 expiration_ = milliseconds(0);
78 HHWheelTimer::HHWheelTimer(folly::EventBase* eventBase,
79 std::chrono::milliseconds intervalMS,
80 AsyncTimeout::InternalEnum internal)
81 : AsyncTimeout(eventBase, internal)
82 , interval_(intervalMS)
85 , catchupEveryN_(DEFAULT_CATCHUP_EVERY_N)
86 , expirationsSinceCatchup_(0)
87 , processingCallbacksGuard_(false)
91 HHWheelTimer::~HHWheelTimer() {
94 void HHWheelTimer::destroy() {
96 DelayedDestruction::destroy();
99 void HHWheelTimer::scheduleTimeoutImpl(Callback* callback,
100 std::chrono::milliseconds timeout) {
101 int64_t due = timeToWheelTicks(timeout) + nextTick_;
102 int64_t diff = due - nextTick_;
106 list = &buckets_[0][nextTick_ & WHEEL_MASK];
107 } else if (diff < WHEEL_SIZE) {
108 list = &buckets_[0][due & WHEEL_MASK];
109 } else if (diff < 1 << (2 * WHEEL_BITS)) {
110 list = &buckets_[1][(due >> WHEEL_BITS) & WHEEL_MASK];
111 } else if (diff < 1 << (3 * WHEEL_BITS)) {
112 list = &buckets_[2][(due >> 2 * WHEEL_BITS) & WHEEL_MASK];
114 /* in largest slot */
115 if (diff > LARGEST_SLOT) {
117 due = diff + nextTick_;
119 list = &buckets_[3][(due >> 3 * WHEEL_BITS) & WHEEL_MASK];
121 list->push_back(*callback);
124 void HHWheelTimer::scheduleTimeout(Callback* callback,
125 std::chrono::milliseconds timeout) {
126 // Cancel the callback if it happens to be scheduled already.
127 callback->cancelTimeout();
129 callback->context_ = RequestContext::saveContext();
131 if (count_ == 0 && !processingCallbacksGuard_) {
132 this->AsyncTimeout::scheduleTimeout(interval_.count());
135 callback->setScheduled(this, timeout);
136 scheduleTimeoutImpl(callback, timeout);
140 bool HHWheelTimer::cascadeTimers(int bucket, int tick) {
142 cbs.swap(buckets_[bucket][tick]);
143 while (!cbs.empty()) {
144 auto* cb = &cbs.front();
146 scheduleTimeoutImpl(cb, cb->getTimeRemaining(now_));
149 // If tick is zero, timeoutExpired will cascade the next bucket.
153 void HHWheelTimer::timeoutExpired() noexcept {
154 // If destroy() is called inside timeoutExpired(), delay actual destruction
155 // until timeoutExpired() returns
156 DestructorGuard dg(this);
157 // If scheduleTimeout is called from a callback in this function, it may
158 // cause inconsistencies in the state of this object. As such, we need
159 // to treat these calls slightly differently.
160 processingCallbacksGuard_ = true;
161 auto reEntryGuard = folly::makeGuard([&] {
162 processingCallbacksGuard_ = false;
165 // timeoutExpired() can only be invoked directly from the event base loop.
166 // It should never be invoked recursively.
168 milliseconds catchup = now_ + interval_;
169 // If catchup is enabled, we may have missed multiple intervals, use
170 // currentTime() to check exactly.
171 if (++expirationsSinceCatchup_ >= catchupEveryN_) {
172 catchup = std::chrono::duration_cast<milliseconds>(
173 std::chrono::steady_clock::now().time_since_epoch());
174 expirationsSinceCatchup_ = 0;
176 while (now_ < catchup) {
179 int idx = nextTick_ & WHEEL_MASK;
182 if (cascadeTimers(1, (nextTick_ >> WHEEL_BITS) & WHEEL_MASK) &&
183 cascadeTimers(2, (nextTick_ >> (2 * WHEEL_BITS)) & WHEEL_MASK)) {
184 cascadeTimers(3, (nextTick_ >> (3 * WHEEL_BITS)) & WHEEL_MASK);
189 CallbackList* cbs = &buckets_[0][idx];
190 while (!cbs->empty()) {
191 auto* cb = &cbs->front();
194 cb->wheel_ = nullptr;
195 cb->expiration_ = milliseconds(0);
197 RequestContext::setContext(cb->context_);
198 cb->timeoutExpired();
199 RequestContext::setContext(old_ctx);
203 this->AsyncTimeout::scheduleTimeout(interval_.count());
207 size_t HHWheelTimer::cancelAll() {
208 decltype(buckets_) buckets;
210 // Work around std::swap() bug in libc++
212 // http://llvm.org/bugs/show_bug.cgi?id=22106
214 for (size_t i = 0; i < WHEEL_BUCKETS; ++i) {
215 for (size_t ii = 0; ii < WHEEL_SIZE; ++ii) {
216 std::swap(buckets_[i][ii], buckets[i][ii]);
220 std::swap(buckets, buckets_);
225 for (auto& tick : buckets) {
226 for (auto& bucket : tick) {
227 while (!bucket.empty()) {
228 auto& cb = bucket.front();
230 cb.callbackCanceled();