1/*
2 * Copyright 2014-present Facebook, Inc.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17#include <folly/io/async/HHWheelTimer.h>
18
19#include <cassert>
20
21#include <folly/Memory.h>
22#include <folly/Optional.h>
23#include <folly/ScopeGuard.h>
24#include <folly/container/BitIterator.h>
25#include <folly/io/async/Request.h>
26#include <folly/lang/Bits.h>
27
28using std::chrono::milliseconds;
29
30namespace folly {
31
32/**
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.
36 *
37 * For a lower bound, we want a reasonable limit on local IO, 10ms
38 * seems short enough
39 *
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.
43 */
44int HHWheelTimer::DEFAULT_TICK_INTERVAL = 10;
45
46HHWheelTimer::Callback::~Callback() {
47 if (isScheduled()) {
48 cancelTimeout();
49 }
50}
51
52void HHWheelTimer::Callback::setScheduled(
53 HHWheelTimer* wheel,
54 std::chrono::steady_clock::time_point deadline) {
55 assert(wheel_ == nullptr);
56 assert(expiration_ == decltype(expiration_){});
57
58 wheel_ = wheel;
59 expiration_ = deadline;
60}
61
62void HHWheelTimer::Callback::cancelTimeoutImpl() {
63 if (--wheel_->count_ <= 0) {
64 assert(wheel_->count_ == 0);
65 wheel_->AsyncTimeout::cancelTimeout();
66 }
67 unlink();
68 if ((-1 != bucket_) && (wheel_->buckets_[0][bucket_].empty())) {
69 auto bi = makeBitIterator(wheel_->bitmap_.begin());
70 *(bi + bucket_) = false;
71 }
72
73 wheel_ = nullptr;
74 expiration_ = {};
75}
76
77HHWheelTimer::HHWheelTimer(
78 folly::TimeoutManager* timeoutMananger,
79 std::chrono::milliseconds intervalMS,
80 AsyncTimeout::InternalEnum internal,
81 std::chrono::milliseconds defaultTimeoutMS)
82 : AsyncTimeout(timeoutMananger, internal),
83 interval_(intervalMS),
84 defaultTimeout_(defaultTimeoutMS),
85 expireTick_(1),
86 count_(0),
87 startTime_(getCurTime()),
88 processingCallbacksGuard_(nullptr) {
89 bitmap_.resize((WHEEL_SIZE / sizeof(std::size_t)) / 8, 0);
90}
91
92HHWheelTimer::~HHWheelTimer() {
93 // Ensure this gets done, but right before destruction finishes.
94 auto destructionPublisherGuard = folly::makeGuard([&] {
95 // Inform the subscriber that this instance is doomed.
96 if (processingCallbacksGuard_) {
97 *processingCallbacksGuard_ = true;
98 }
99 });
100 cancelAll();
101}
102
103void HHWheelTimer::scheduleTimeoutImpl(
104 Callback* callback,
105 std::chrono::milliseconds timeout,
106 int64_t nextTickToProcess,
107 int64_t nextTick) {
108 int64_t due = timeToWheelTicks(timeout) + nextTick;
109 int64_t diff = due - nextTickToProcess;
110 CallbackList* list;
111
112 auto bi = makeBitIterator(bitmap_.begin());
113
114 if (diff < 0) {
115 list = &buckets_[0][nextTick & WHEEL_MASK];
116 *(bi + (nextTick & WHEEL_MASK)) = true;
117 callback->bucket_ = nextTick & WHEEL_MASK;
118 } else if (diff < WHEEL_SIZE) {
119 list = &buckets_[0][due & WHEEL_MASK];
120 *(bi + (due & WHEEL_MASK)) = true;
121 callback->bucket_ = due & WHEEL_MASK;
122 } else if (diff < 1 << (2 * WHEEL_BITS)) {
123 list = &buckets_[1][(due >> WHEEL_BITS) & WHEEL_MASK];
124 } else if (diff < 1 << (3 * WHEEL_BITS)) {
125 list = &buckets_[2][(due >> 2 * WHEEL_BITS) & WHEEL_MASK];
126 } else {
127 /* in largest slot */
128 if (diff > LARGEST_SLOT) {
129 diff = LARGEST_SLOT;
130 due = diff + nextTickToProcess;
131 }
132 list = &buckets_[3][(due >> 3 * WHEEL_BITS) & WHEEL_MASK];
133 }
134 list->push_back(*callback);
135}
136
137void HHWheelTimer::scheduleTimeout(
138 Callback* callback,
139 std::chrono::milliseconds timeout) {
140 // Cancel the callback if it happens to be scheduled already.
141 callback->cancelTimeout();
142 callback->requestContext_ = RequestContext::saveContext();
143
144 count_++;
145
146 auto now = getCurTime();
147 auto nextTick = calcNextTick(now);
148 callback->setScheduled(this, now + timeout);
149
150 // There are three possible scenarios:
151 // - we are currently inside of HHWheelTimer::timeoutExpired. In this case,
152 // we need to use its last tick as a base for computations
153 // - HHWheelTimer tick timeout is already scheduled. In this case,
154 // we need to use its scheduled tick as a base.
155 // - none of the above are true. In this case, it's safe to use the nextTick
156 // as a base.
157 int64_t baseTick = nextTick;
158 if (processingCallbacksGuard_ || isScheduled()) {
159 baseTick = std::min(expireTick_, nextTick);
160 }
161 scheduleTimeoutImpl(callback, timeout, baseTick, nextTick);
162
163 /* If we're calling callbacks, timer will be reset after all
164 * callbacks are called.
165 */
166 if (!processingCallbacksGuard_) {
167 scheduleNextTimeout(nextTick);
168 }
169}
170
171void HHWheelTimer::scheduleTimeout(Callback* callback) {
172 CHECK(std::chrono::milliseconds(-1) != defaultTimeout_)
173 << "Default timeout was not initialized";
174 scheduleTimeout(callback, defaultTimeout_);
175}
176
177bool HHWheelTimer::cascadeTimers(int bucket, int tick) {
178 CallbackList cbs;
179 cbs.swap(buckets_[bucket][tick]);
180 auto now = getCurTime();
181 auto nextTick = calcNextTick(now);
182 while (!cbs.empty()) {
183 auto* cb = &cbs.front();
184 cbs.pop_front();
185 scheduleTimeoutImpl(cb, cb->getTimeRemaining(now), expireTick_, nextTick);
186 }
187
188 // If tick is zero, timeoutExpired will cascade the next bucket.
189 return tick == 0;
190}
191
192void HHWheelTimer::timeoutExpired() noexcept {
193 auto nextTick = calcNextTick();
194
195 // If the last smart pointer for "this" is reset inside the callback's
196 // timeoutExpired(), then the guard will detect that it is time to bail from
197 // this method.
198 auto isDestroyed = false;
199 // If scheduleTimeout is called from a callback in this function, it may
200 // cause inconsistencies in the state of this object. As such, we need
201 // to treat these calls slightly differently.
202 CHECK(!processingCallbacksGuard_);
203 processingCallbacksGuard_ = &isDestroyed;
204 auto reEntryGuard = folly::makeGuard([&] {
205 if (!isDestroyed) {
206 processingCallbacksGuard_ = nullptr;
207 }
208 });
209
210 // timeoutExpired() can only be invoked directly from the event base loop.
211 // It should never be invoked recursively.
212 //
213 while (expireTick_ < nextTick) {
214 int idx = expireTick_ & WHEEL_MASK;
215
216 if (idx == 0) {
217 // Cascade timers
218 if (cascadeTimers(1, (expireTick_ >> WHEEL_BITS) & WHEEL_MASK) &&
219 cascadeTimers(2, (expireTick_ >> (2 * WHEEL_BITS)) & WHEEL_MASK)) {
220 cascadeTimers(3, (expireTick_ >> (3 * WHEEL_BITS)) & WHEEL_MASK);
221 }
222 }
223
224 auto bi = makeBitIterator(bitmap_.begin());
225 *(bi + idx) = false;
226
227 expireTick_++;
228 CallbackList* cbs = &buckets_[0][idx];
229 while (!cbs->empty()) {
230 auto* cb = &cbs->front();
231 cbs->pop_front();
232 timeoutsToRunNow_.push_back(*cb);
233 }
234 }
235
236 while (!timeoutsToRunNow_.empty()) {
237 auto* cb = &timeoutsToRunNow_.front();
238 timeoutsToRunNow_.pop_front();
239 count_--;
240 cb->wheel_ = nullptr;
241 cb->expiration_ = {};
242 RequestContextScopeGuard rctx(cb->requestContext_);
243 cb->timeoutExpired();
244 if (isDestroyed) {
245 // The HHWheelTimer itself has been destroyed. The other callbacks
246 // will have been cancelled from the destructor. Bail before causing
247 // damage.
248 return;
249 }
250 }
251 scheduleNextTimeout(expireTick_);
252}
253
254size_t HHWheelTimer::cancelAll() {
255 size_t count = 0;
256
257 if (count_ != 0) {
258 const std::size_t numElements = WHEEL_BUCKETS * WHEEL_SIZE;
259 auto maxBuckets = std::min(numElements, count_);
260 auto buckets = std::make_unique<CallbackList[]>(maxBuckets);
261 size_t countBuckets = 0;
262 for (auto& tick : buckets_) {
263 for (auto& bucket : tick) {
264 if (bucket.empty()) {
265 continue;
266 }
267 count += bucket.size();
268 std::swap(bucket, buckets[countBuckets++]);
269 if (count >= count_) {
270 break;
271 }
272 }
273 }
274
275 for (size_t i = 0; i < countBuckets; ++i) {
276 cancelTimeoutsFromList(buckets[i]);
277 }
278 // Swap the list to prevent potential recursion if cancelAll is called by
279 // one of the callbacks.
280 CallbackList timeoutsToRunNow;
281 timeoutsToRunNow.swap(timeoutsToRunNow_);
282 count += cancelTimeoutsFromList(timeoutsToRunNow);
283 }
284
285 return count;
286}
287
288void HHWheelTimer::scheduleNextTimeout(int64_t nextTick) {
289 int64_t tick = 1;
290
291 if (nextTick & WHEEL_MASK) {
292 auto bi = makeBitIterator(bitmap_.begin());
293 auto bi_end = makeBitIterator(bitmap_.end());
294 auto it = folly::findFirstSet(bi + (nextTick & WHEEL_MASK), bi_end);
295 if (it == bi_end) {
296 tick = WHEEL_SIZE - ((nextTick - 1) & WHEEL_MASK);
297 } else {
298 tick = std::distance(bi + (nextTick & WHEEL_MASK), it) + 1;
299 }
300 }
301
302 if (count_ > 0) {
303 if (!this->AsyncTimeout::isScheduled() ||
304 (expireTick_ > tick + nextTick - 1)) {
305 this->AsyncTimeout::scheduleTimeout(interval_ * tick);
306 expireTick_ = tick + nextTick - 1;
307 }
308 } else {
309 this->AsyncTimeout::cancelTimeout();
310 }
311}
312
313size_t HHWheelTimer::cancelTimeoutsFromList(CallbackList& timeouts) {
314 size_t count = 0;
315 while (!timeouts.empty()) {
316 ++count;
317 auto& cb = timeouts.front();
318 cb.cancelTimeout();
319 cb.callbackCanceled();
320 }
321 return count;
322}
323
324int64_t HHWheelTimer::calcNextTick() {
325 return calcNextTick(getCurTime());
326}
327
328int64_t HHWheelTimer::calcNextTick(
329 std::chrono::steady_clock::time_point curTime) {
330 return (curTime - startTime_) / interval_;
331}
332
333} // namespace folly
334