folly/io/async/HHWheelTimer.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  18
  19 #include <folly/Optional.h>
  20 #include <folly/io/async/AsyncTimeout.h>
  21 #include <folly/io/async/DelayedDestruction.h>
  22
  23 #include <boost/intrusive/list.hpp>
  24 #include <glog/logging.h>
  25
  26 #include <chrono>
  27 #include <cstddef>
  28 #include <list>
  29 #include <memory>
  30
  31 namespace folly {
  32
  33 /**
  34  * Hashed Hierarchical Wheel Timer
  35  *
  36  * We model timers as the number of ticks until the next
  37  * due event.  We allow 32-bits of space to track this
  38  * due interval, and break that into 4 regions of 8 bits.
  39  * Each region indexes into a bucket of 256 lists.
  40  *
  41  * Bucket 0 represents those events that are due the soonest.
  42  * Each tick causes us to look at the next list in a bucket.
  43  * The 0th list in a bucket is special; it means that it is time to
  44  * flush the timers from the next higher bucket and schedule them
  45  * into a different bucket.
  46  *
  47  * This technique results in a very cheap mechanism for
  48  * maintaining time and timers.
  49  *
  50  * Unlike the original timer wheel paper, this implementation does
  51  * *not* tick constantly, and instead calculates the exact next wakeup
  52  * time.
  53  */
  54 class HHWheelTimer : private folly::AsyncTimeout,
  55                      public folly::DelayedDestruction {
  56  public:
  57   using UniquePtr = std::unique_ptr<HHWheelTimer, Destructor>;
  58   using SharedPtr = std::shared_ptr<HHWheelTimer>;
  59
  60   template <typename... Args>
  61   static UniquePtr newTimer(Args&&... args) {
  62     return UniquePtr(new HHWheelTimer(std::forward<Args>(args)...));
  63   }
  64
  65   /**
  66    * A callback to be notified when a timeout has expired.
  67    */
  68   class Callback
  69       : public boost::intrusive::list_base_hook<
  70             boost::intrusive::link_mode<boost::intrusive::auto_unlink>> {
  71    public:
  72     Callback() = default;
  73     virtual ~Callback();
  74
  75     /**
  76      * timeoutExpired() is invoked when the timeout has expired.
  77      */
  78     virtual void timeoutExpired() noexcept = 0;
  79
  80     /// This callback was canceled. The default implementation is to just
  81     /// proxy to `timeoutExpired` but if you care about the difference between
  82     /// the timeout finishing or being canceled you can override this.
  83     virtual void callbackCanceled() noexcept {
  84       timeoutExpired();
  85     }
  86
  87     /**
  88      * Cancel the timeout, if it is running.
  89      *
  90      * If the timeout is not scheduled, cancelTimeout() does nothing.
  91      */
  92     void cancelTimeout() {
  93       if (wheel_ == nullptr) {
  94         // We're not scheduled, so there's nothing to do.
  95         return;
  96       }
  97       cancelTimeoutImpl();
  98     }
  99
 100     /**
 101      * Return true if this timeout is currently scheduled, and false otherwise.
 102      */
 103     bool isScheduled() const {
 104       return wheel_ != nullptr;
 105     }
 106
 107     /**
 108      * Get the time remaining until this timeout expires. Return 0 if this
 109      * timeout is not scheduled or expired. Otherwise, return expiration time
 110      * minus getCurTime().
 111      */
 112     std::chrono::milliseconds getTimeRemaining() {
 113       return getTimeRemaining(getCurTime());
 114     }
 115
 116    protected:
 117     /**
 118      * Don't override this unless you're doing a test. This is mainly here so
 119      * that we can override it to simulate lag in steady_clock.
 120      */
 121     virtual std::chrono::steady_clock::time_point getCurTime() {
 122       return std::chrono::steady_clock::now();
 123     }
 124
 125    private:
 126     // Get the time remaining until this timeout expires
 127     std::chrono::milliseconds getTimeRemaining(
 128         std::chrono::steady_clock::time_point now) const {
 129       if (now >= expiration_) {
 130         return std::chrono::milliseconds(0);
 131       }
 132       return std::chrono::duration_cast<std::chrono::milliseconds>(
 133           expiration_ - now);
 134     }
 135
 136     void setScheduled(HHWheelTimer* wheel,
 137                       std::chrono::milliseconds);
 138     void cancelTimeoutImpl();
 139
 140     HHWheelTimer* wheel_{nullptr};
 141     std::chrono::steady_clock::time_point expiration_{};
 142     int bucket_{-1};
 143
 144     typedef boost::intrusive::list<
 145       Callback,
 146       boost::intrusive::constant_time_size<false> > List;
 147
 148     std::shared_ptr<RequestContext> context_;
 149
 150     // Give HHWheelTimer direct access to our members so it can take care
 151     // of scheduling/cancelling.
 152     friend class HHWheelTimer;
 153   };
 154
 155   /**
 156    * Create a new HHWheelTimer with the specified interval and the
 157    * default timeout value set.
 158    *
 159    * Objects created using this version of constructor can be used
 160    * to schedule both variable interval timeouts using
 161    * scheduleTimeout(callback, timeout) method, and default
 162    * interval timeouts using scheduleTimeout(callback) method.
 163    */
 164   static int DEFAULT_TICK_INTERVAL;
 165   explicit HHWheelTimer(
 166       folly::TimeoutManager* timeoutManager,
 167       std::chrono::milliseconds intervalMS =
 168           std::chrono::milliseconds(DEFAULT_TICK_INTERVAL),
 169       AsyncTimeout::InternalEnum internal = AsyncTimeout::InternalEnum::NORMAL,
 170       std::chrono::milliseconds defaultTimeoutMS =
 171           std::chrono::milliseconds(-1));
 172
 173   /**
 174    * Cancel all outstanding timeouts
 175    *
 176    * @returns the number of timeouts that were cancelled.
 177    */
 178   size_t cancelAll();
 179
 180   /**
 181    * Get the tick interval for this HHWheelTimer.
 182    *
 183    * Returns the tick interval in milliseconds.
 184    */
 185   std::chrono::milliseconds getTickInterval() const {
 186     return interval_;
 187   }
 188
 189   /**
 190    * Get the default timeout interval for this HHWheelTimer.
 191    *
 192    * Returns the timeout interval in milliseconds.
 193    */
 194   std::chrono::milliseconds getDefaultTimeout() const {
 195     return defaultTimeout_;
 196   }
 197
 198   /**
 199    * Schedule the specified Callback to be invoked after the
 200    * specified timeout interval.
 201    *
 202    * If the callback is already scheduled, this cancels the existing timeout
 203    * before scheduling the new timeout.
 204    */
 205   void scheduleTimeout(Callback* callback,
 206                        std::chrono::milliseconds timeout);
 207   void scheduleTimeoutImpl(Callback* callback,
 208                        std::chrono::milliseconds timeout);
 209
 210   /**
 211    * Schedule the specified Callback to be invoked after the
 212    * default timeout interval.
 213    *
 214    * If the callback is already scheduled, this cancels the existing timeout
 215    * before scheduling the new timeout.
 216    *
 217    * This method uses CHECK() to make sure that the default timeout was
 218    * specified on the object initialization.
 219    */
 220   void scheduleTimeout(Callback* callback);
 221
 222   template <class F>
 223   void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
 224     struct Wrapper : Callback {
 225       Wrapper(F f) : fn_(std::move(f)) {}
 226       void timeoutExpired() noexcept override {
 227         try {
 228           fn_();
 229         } catch (std::exception const& e) {
 230           LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
 231             << e.what();
 232         } catch (...) {
 233           LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
 234         }
 235         delete this;
 236       }
 237       F fn_;
 238     };
 239     Wrapper* w = new Wrapper(std::move(fn));
 240     scheduleTimeout(w, timeout);
 241   }
 242
 243   /**
 244    * Return the number of currently pending timeouts
 245    */
 246   uint64_t count() const {
 247     return count_;
 248   }
 249
 250   bool isDetachable() const {
 251     return !folly::AsyncTimeout::isScheduled();
 252   }
 253
 254   using folly::AsyncTimeout::attachEventBase;
 255   using folly::AsyncTimeout::detachEventBase;
 256   using folly::AsyncTimeout::getTimeoutManager;
 257
 258  protected:
 259   /**
 260    * Protected destructor.
 261    *
 262    * Use destroy() instead.  See the comments in DelayedDestruction for more
 263    * details.
 264    */
 265   ~HHWheelTimer() override;
 266
 267  private:
 268   // Forbidden copy constructor and assignment operator
 269   HHWheelTimer(HHWheelTimer const &) = delete;
 270   HHWheelTimer& operator=(HHWheelTimer const &) = delete;
 271
 272   // Methods inherited from AsyncTimeout
 273   void timeoutExpired() noexcept override;
 274
 275   std::chrono::milliseconds interval_;
 276   std::chrono::milliseconds defaultTimeout_;
 277
 278   static constexpr int WHEEL_BUCKETS = 4;
 279   static constexpr int WHEEL_BITS = 8;
 280   static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
 281   static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
 282   static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
 283
 284   typedef Callback::List CallbackList;
 285   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
 286   std::vector<uint64_t> bitmap_;
 287
 288   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
 289     return t.count() / interval_.count();
 290   }
 291
 292   bool cascadeTimers(int bucket, int tick);
 293   int64_t lastTick_;
 294   int64_t expireTick_;
 295   uint64_t count_;
 296   std::chrono::steady_clock::time_point startTime_;
 297
 298   int64_t calcNextTick();
 299
 300   void scheduleNextTimeout();
 301
 302   bool* processingCallbacksGuard_;
 303   CallbackList timeouts; // Timeouts queued to run
 304
 305   std::chrono::steady_clock::time_point getCurTime() {
 306     return std::chrono::steady_clock::now();
 307   }
 308 };
 309
 310 } // namespace folly