folly/io/async/HHWheelTimer.h

   1 /*
   2  * Copyright 2014 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     /**
  80      * Cancel the timeout, if it is running.
  81      *
  82      * If the timeout is not scheduled, cancelTimeout() does nothing.
  83      */
  84     void cancelTimeout() {
  85       if (wheel_ == nullptr) {
  86         // We're not scheduled, so there's nothing to do.
  87         return;
  88       }
  89       cancelTimeoutImpl();
  90     }
  91
  92     /**
  93      * Return true if this timeout is currently scheduled, and false otherwise.
  94      */
  95     bool isScheduled() const {
  96       return wheel_ != nullptr;
  97     }
  98
  99    protected:
 100     /**
 101      * Don't override this unless you're doing a test. This is mainly here so
 102      * that we can override it to simulate lag in steady_clock.
 103      */
 104     virtual std::chrono::milliseconds getCurTime() {
 105       return std::chrono::duration_cast<std::chrono::milliseconds>(
 106         std::chrono::steady_clock::now().time_since_epoch());
 107     }
 108
 109    private:
 110     // Get the time remaining until this timeout expires
 111     std::chrono::milliseconds getTimeRemaining(
 112           std::chrono::milliseconds now) const {
 113       if (now >= expiration_) {
 114         return std::chrono::milliseconds(0);
 115       }
 116       return expiration_ - now;
 117     }
 118
 119     void setScheduled(HHWheelTimer* wheel,
 120                       std::chrono::milliseconds);
 121     void cancelTimeoutImpl();
 122
 123     HHWheelTimer* wheel_;
 124     std::chrono::milliseconds expiration_;
 125
 126     typedef boost::intrusive::list_member_hook<
 127       boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
 128
 129     ListHook hook_;
 130
 131     typedef boost::intrusive::list<
 132       Callback,
 133       boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
 134       boost::intrusive::constant_time_size<false> > List;
 135
 136     std::shared_ptr<RequestContext> context_;
 137
 138     // Give HHWheelTimer direct access to our members so it can take care
 139     // of scheduling/cancelling.
 140     friend class HHWheelTimer;
 141   };
 142
 143   /**
 144    * Create a new HHWheelTimer with the specified interval.
 145    */
 146   static int DEFAULT_TICK_INTERVAL;
 147   explicit HHWheelTimer(folly::EventBase* eventBase,
 148                         std::chrono::milliseconds intervalMS =
 149                         std::chrono::milliseconds(DEFAULT_TICK_INTERVAL));
 150
 151   /**
 152    * Destroy the HHWheelTimer.
 153    *
 154    * A HHWheelTimer should only be destroyed when there are no more
 155    * callbacks pending in the set.
 156    */
 157   virtual void destroy();
 158
 159   /**
 160    * Get the tick interval for this HHWheelTimer.
 161    *
 162    * Returns the tick interval in milliseconds.
 163    */
 164   std::chrono::milliseconds getTickInterval() const {
 165     return interval_;
 166   }
 167
 168   /**
 169    * Schedule the specified Callback to be invoked after the
 170    * specified timeout interval.
 171    *
 172    * If the callback is already scheduled, this cancels the existing timeout
 173    * before scheduling the new timeout.
 174    */
 175   void scheduleTimeout(Callback* callback,
 176                        std::chrono::milliseconds timeout);
 177   void scheduleTimeoutImpl(Callback* callback,
 178                        std::chrono::milliseconds timeout);
 179
 180   template <class F>
 181   void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
 182     struct Wrapper : Callback {
 183       Wrapper(F fn) : fn_(std::move(fn)) {}
 184       void timeoutExpired() noexcept override {
 185         try {
 186           fn_();
 187         } catch (std::exception const& e) {
 188           LOG(ERROR) << e.what();
 189         } catch (...) { }
 190         delete this;
 191       }
 192       F fn_;
 193     };
 194     Wrapper* w = new Wrapper(std::move(fn));
 195     scheduleTimeout(w, timeout);
 196   }
 197
 198   /**
 199    * Return the number of currently pending timeouts
 200    */
 201   uint64_t count() const {
 202     return count_;
 203   }
 204
 205   /**
 206    * This turns on more exact timing.  By default the wheel timer
 207    * increments its cached time only once everyN (default) ticks.
 208    *
 209    * With catchupEveryN at 1, timeouts will only be delayed until the
 210    * next tick, at which point all overdue timeouts are called.  The
 211    * wheel timer is approximately 2x slower with this set to 1.
 212    *
 213    * Load testing in opt mode showed skew was about 1% with no catchup.
 214    */
 215   void setCatchupEveryN(uint32_t everyN) {
 216     catchupEveryN_ = everyN;
 217   }
 218
 219   bool isDetachable() const {
 220     return !folly::AsyncTimeout::isScheduled();
 221   }
 222
 223   using folly::AsyncTimeout::attachEventBase;
 224   using folly::AsyncTimeout::detachEventBase;
 225   using folly::AsyncTimeout::getTimeoutManager;
 226
 227  protected:
 228   /**
 229    * Protected destructor.
 230    *
 231    * Use destroy() instead.  See the comments in DelayedDestruction for more
 232    * details.
 233    */
 234   virtual ~HHWheelTimer();
 235
 236  private:
 237   // Forbidden copy constructor and assignment operator
 238   HHWheelTimer(HHWheelTimer const &) = delete;
 239   HHWheelTimer& operator=(HHWheelTimer const &) = delete;
 240
 241   // Methods inherited from TAsyncTimeout
 242   virtual void timeoutExpired() noexcept;
 243
 244   std::chrono::milliseconds interval_;
 245
 246   static constexpr int WHEEL_BUCKETS = 4;
 247   static constexpr int WHEEL_BITS = 8;
 248   static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
 249   static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
 250   static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
 251
 252   typedef Callback::List CallbackList;
 253   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
 254
 255   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
 256     return t.count() / interval_.count();
 257   }
 258
 259   bool cascadeTimers(int bucket, int tick);
 260   int64_t nextTick_;
 261   uint64_t count_;
 262   std::chrono::milliseconds now_;
 263
 264   static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
 265
 266   uint32_t catchupEveryN_;
 267   uint32_t expirationsSinceCatchup_;
 268   bool processingCallbacksGuard_;
 269 };
 270
 271 } // folly