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