folly/io/async/HHWheelTimer.h

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