folly/io/async/HHWheelTimer.cpp

   1 /*
   2  * Copyright 2004-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 #include <folly/io/async/Request.h>
  19
  20 #include <folly/Memory.h>
  21 #include <folly/Optional.h>
  22 #include <folly/ScopeGuard.h>
  23
  24 #include <folly/Bits.h>
  25
  26 #include <cassert>
  27
  28 using std::chrono::milliseconds;
  29
  30 namespace 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  */
  44 int HHWheelTimer::DEFAULT_TICK_INTERVAL = 10;
  45
  46 HHWheelTimer::Callback::~Callback() {
  47   if (isScheduled()) {
  48     cancelTimeout();
  49   }
  50 }
  51
  52 void HHWheelTimer::Callback::setScheduled(HHWheelTimer* wheel,
  53                                           std::chrono::milliseconds timeout) {
  54   assert(wheel_ == nullptr);
  55   assert(expiration_ == decltype(expiration_){});
  56
  57   wheel_ = wheel;
  58
  59   expiration_ = getCurTime() + timeout;
  60 }
  61
  62 void 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
  77 HHWheelTimer::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       lastTick_(1),
  86       expireTick_(1),
  87       count_(0),
  88       startTime_(getCurTime()),
  89       processingCallbacksGuard_(nullptr) {
  90   bitmap_.resize((WHEEL_SIZE / sizeof(uint64_t)) / 8, 0);
  91 }
  92
  93 HHWheelTimer::~HHWheelTimer() {
  94   // Ensure this gets done, but right before destruction finishes.
  95   auto destructionPublisherGuard = folly::makeGuard([&] {
  96     // Inform the subscriber that this instance is doomed.
  97     if (processingCallbacksGuard_) {
  98       *processingCallbacksGuard_ = true;
  99     }
 100   });
 101   while (!timeouts.empty()) {
 102     auto* cb = &timeouts.front();
 103     timeouts.pop_front();
 104     cb->cancelTimeout();
 105     cb->callbackCanceled();
 106   }
 107   cancelAll();
 108 }
 109
 110 void HHWheelTimer::scheduleTimeoutImpl(Callback* callback,
 111                                        std::chrono::milliseconds timeout) {
 112   auto nextTick = calcNextTick();
 113   int64_t due = timeToWheelTicks(timeout) + nextTick;
 114   int64_t diff = due - nextTick;
 115   CallbackList* list;
 116
 117   auto bi = makeBitIterator(bitmap_.begin());
 118
 119   if (diff < 0) {
 120     list = &buckets_[0][nextTick & WHEEL_MASK];
 121     *(bi + (nextTick & WHEEL_MASK)) = true;
 122     callback->bucket_ = nextTick & WHEEL_MASK;
 123   } else if (diff < WHEEL_SIZE) {
 124     list = &buckets_[0][due & WHEEL_MASK];
 125     *(bi + (due & WHEEL_MASK)) = true;
 126     callback->bucket_ = due & WHEEL_MASK;
 127   } else if (diff < 1 << (2 * WHEEL_BITS)) {
 128     list = &buckets_[1][(due >> WHEEL_BITS) & WHEEL_MASK];
 129   } else if (diff < 1 << (3 * WHEEL_BITS)) {
 130     list = &buckets_[2][(due >> 2 * WHEEL_BITS) & WHEEL_MASK];
 131   } else {
 132     /* in largest slot */
 133     if (diff > LARGEST_SLOT) {
 134       diff = LARGEST_SLOT;
 135       due = diff + nextTick;
 136     }
 137     list = &buckets_[3][(due >> 3 * WHEEL_BITS) & WHEEL_MASK];
 138   }
 139   list->push_back(*callback);
 140 }
 141
 142 void HHWheelTimer::scheduleTimeout(Callback* callback,
 143                                    std::chrono::milliseconds timeout) {
 144   // Cancel the callback if it happens to be scheduled already.
 145   callback->cancelTimeout();
 146
 147   callback->context_ = RequestContext::saveContext();
 148
 149   count_++;
 150
 151   callback->setScheduled(this, timeout);
 152   scheduleTimeoutImpl(callback, timeout);
 153
 154   /* If we're calling callbacks, timer will be reset after all
 155    * callbacks are called.
 156    */
 157   if (!processingCallbacksGuard_) {
 158     scheduleNextTimeout();
 159   }
 160 }
 161
 162 void HHWheelTimer::scheduleTimeout(Callback* callback) {
 163   CHECK(std::chrono::milliseconds(-1) != defaultTimeout_)
 164       << "Default timeout was not initialized";
 165   scheduleTimeout(callback, defaultTimeout_);
 166 }
 167
 168 bool HHWheelTimer::cascadeTimers(int bucket, int tick) {
 169   CallbackList cbs;
 170   cbs.swap(buckets_[bucket][tick]);
 171   while (!cbs.empty()) {
 172     auto* cb = &cbs.front();
 173     cbs.pop_front();
 174     scheduleTimeoutImpl(cb, cb->getTimeRemaining(getCurTime()));
 175   }
 176
 177   // If tick is zero, timeoutExpired will cascade the next bucket.
 178   return tick == 0;
 179 }
 180
 181 void HHWheelTimer::timeoutExpired() noexcept {
 182   auto nextTick = calcNextTick();
 183
 184   // If the last smart pointer for "this" is reset inside the callback's
 185   // timeoutExpired(), then the guard will detect that it is time to bail from
 186   // this method.
 187   auto isDestroyed = false;
 188   // If scheduleTimeout is called from a callback in this function, it may
 189   // cause inconsistencies in the state of this object. As such, we need
 190   // to treat these calls slightly differently.
 191   CHECK(!processingCallbacksGuard_);
 192   processingCallbacksGuard_ = &isDestroyed;
 193   auto reEntryGuard = folly::makeGuard([&] {
 194     if (!isDestroyed) {
 195       processingCallbacksGuard_ = nullptr;
 196     }
 197   });
 198
 199   // timeoutExpired() can only be invoked directly from the event base loop.
 200   // It should never be invoked recursively.
 201   //
 202   lastTick_ = expireTick_;
 203   while (lastTick_ < nextTick) {
 204     int idx = lastTick_ & WHEEL_MASK;
 205
 206     auto bi = makeBitIterator(bitmap_.begin());
 207     *(bi + idx) = false;
 208
 209     lastTick_++;
 210     CallbackList* cbs = &buckets_[0][idx];
 211     while (!cbs->empty()) {
 212       auto* cb = &cbs->front();
 213       cbs->pop_front();
 214       timeouts.push_back(*cb);
 215     }
 216
 217     if (idx == 0) {
 218       // Cascade timers
 219       if (cascadeTimers(1, (lastTick_ >> WHEEL_BITS) & WHEEL_MASK) &&
 220           cascadeTimers(2, (lastTick_ >> (2 * WHEEL_BITS)) & WHEEL_MASK)) {
 221         cascadeTimers(3, (lastTick_ >> (3 * WHEEL_BITS)) & WHEEL_MASK);
 222       }
 223     }
 224   }
 225
 226   while (!timeouts.empty()) {
 227     auto* cb = &timeouts.front();
 228     timeouts.pop_front();
 229     count_--;
 230     cb->wheel_ = nullptr;
 231     cb->expiration_ = {};
 232     RequestContextScopeGuard rctx(cb->context_);
 233     cb->timeoutExpired();
 234     if (isDestroyed) {
 235       // The HHWheelTimer itself has been destroyed. The other callbacks
 236       // will have been cancelled from the destructor. Bail before causing
 237       // damage.
 238       return;
 239     }
 240   }
 241   scheduleNextTimeout();
 242 }
 243
 244 size_t HHWheelTimer::cancelAll() {
 245   size_t count = 0;
 246
 247   if (count_ != 0) {
 248     const uint64_t numElements = WHEEL_BUCKETS * WHEEL_SIZE;
 249     auto maxBuckets = std::min(numElements, count_);
 250     auto buckets = std::make_unique<CallbackList[]>(maxBuckets);
 251     size_t countBuckets = 0;
 252     for (auto& tick : buckets_) {
 253       for (auto& bucket : tick) {
 254         if (bucket.empty()) {
 255           continue;
 256         }
 257         count += bucket.size();
 258         std::swap(bucket, buckets[countBuckets++]);
 259         if (count >= count_) {
 260           break;
 261         }
 262       }
 263     }
 264
 265     for (size_t i = 0; i < countBuckets; ++i) {
 266       auto& bucket = buckets[i];
 267       while (!bucket.empty()) {
 268         auto& cb = bucket.front();
 269         cb.cancelTimeout();
 270         cb.callbackCanceled();
 271       }
 272     }
 273   }
 274
 275   return count;
 276 }
 277
 278 void HHWheelTimer::scheduleNextTimeout() {
 279   auto nextTick = calcNextTick();
 280   int64_t tick = 1;
 281
 282   if (nextTick & WHEEL_MASK) {
 283     auto bi = makeBitIterator(bitmap_.begin());
 284     auto bi_end = makeBitIterator(bitmap_.end());
 285     auto it = folly::findFirstSet(bi + (nextTick & WHEEL_MASK), bi_end);
 286     if (it == bi_end) {
 287       tick = WHEEL_SIZE - ((nextTick - 1) & WHEEL_MASK);
 288     } else {
 289       tick = std::distance(bi + (nextTick & WHEEL_MASK), it) + 1;
 290     }
 291   }
 292
 293   if (count_ > 0) {
 294     if (!this->AsyncTimeout::isScheduled() ||
 295         (expireTick_ > tick + nextTick - 1)) {
 296       this->AsyncTimeout::scheduleTimeout(interval_ * tick);
 297       expireTick_ = tick + nextTick - 1;
 298     }
 299   } else {
 300     this->AsyncTimeout::cancelTimeout();
 301   }
 302 }
 303
 304 int64_t HHWheelTimer::calcNextTick() {
 305   auto intervals = (getCurTime() - startTime_) / interval_;
 306   // Slow eventbases will have skew between the actual time and the
 307   // callback time.  To avoid racing the next scheduleNextTimeout()
 308   // call, always schedule new timeouts against the actual
 309   // timeoutExpired() time.
 310   if (!processingCallbacksGuard_) {
 311     return intervals;
 312   } else {
 313     return lastTick_;
 314   }
 315 }
 316
 317 } // folly