folly/io/async/HHWheelTimer.cpp

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