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 : protected 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    private:
  99     // Get the time remaining until this timeout expires
 100     std::chrono::milliseconds getTimeRemaining(
 101           std::chrono::milliseconds now) const {
 102       if (now >= expiration_) {
 103         return std::chrono::milliseconds(0);
 104       }
 105       return expiration_ - now;
 106     }
 107
 108     void setScheduled(HHWheelTimer* wheel,
 109                       std::chrono::milliseconds);
 110     void cancelTimeoutImpl();
 111
 112     HHWheelTimer* wheel_;
 113     std::chrono::milliseconds expiration_;
 114
 115     typedef boost::intrusive::list_member_hook<
 116       boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
 117
 118     ListHook hook_;
 119
 120     typedef boost::intrusive::list<
 121       Callback,
 122       boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
 123       boost::intrusive::constant_time_size<false> > List;
 124
 125     std::shared_ptr<RequestContext> context_;
 126
 127     // Give HHWheelTimer direct access to our members so it can take care
 128     // of scheduling/cancelling.
 129     friend class HHWheelTimer;
 130   };
 131
 132   /**
 133    * Create a new HHWheelTimer with the specified interval.
 134    */
 135   static int DEFAULT_TICK_INTERVAL;
 136   explicit HHWheelTimer(folly::EventBase* eventBase,
 137                         std::chrono::milliseconds intervalMS =
 138                         std::chrono::milliseconds(DEFAULT_TICK_INTERVAL));
 139
 140   /**
 141    * Destroy the HHWheelTimer.
 142    *
 143    * A HHWheelTimer should only be destroyed when there are no more
 144    * callbacks pending in the set.
 145    */
 146   virtual void destroy();
 147
 148   /**
 149    * Get the tick interval for this HHWheelTimer.
 150    *
 151    * Returns the tick interval in milliseconds.
 152    */
 153   std::chrono::milliseconds getTickInterval() const {
 154     return interval_;
 155   }
 156
 157   /**
 158    * Schedule the specified Callback to be invoked after the
 159    * specified timeout interval.
 160    *
 161    * If the callback is already scheduled, this cancels the existing timeout
 162    * before scheduling the new timeout.
 163    */
 164   void scheduleTimeout(Callback* callback,
 165                        std::chrono::milliseconds timeout);
 166   void scheduleTimeoutImpl(Callback* callback,
 167                        std::chrono::milliseconds timeout);
 168
 169   /**
 170    * Return the number of currently pending timeouts
 171    */
 172   uint64_t count() const {
 173     return count_;
 174   }
 175
 176   /**
 177    * This turns on more exact timing.  By default the wheel timer
 178    * increments its cached time only once everyN (default) ticks.
 179    *
 180    * With catchupEveryN at 1, timeouts will only be delayed until the
 181    * next tick, at which point all overdue timeouts are called.  The
 182    * wheel timer is approximately 2x slower with this set to 1.
 183    *
 184    * Load testing in opt mode showed skew was about 1% with no catchup.
 185    */
 186   void setCatchupEveryN(uint32_t everyN) {
 187     catchupEveryN_ = everyN;
 188   }
 189
 190   using folly::AsyncTimeout::attachEventBase;
 191   using folly::AsyncTimeout::detachEventBase;
 192   using folly::AsyncTimeout::getTimeoutManager;
 193
 194  protected:
 195   /**
 196    * Protected destructor.
 197    *
 198    * Use destroy() instead.  See the comments in DelayedDestruction for more
 199    * details.
 200    */
 201   virtual ~HHWheelTimer();
 202
 203  private:
 204   // Forbidden copy constructor and assignment operator
 205   HHWheelTimer(HHWheelTimer const &) = delete;
 206   HHWheelTimer& operator=(HHWheelTimer const &) = delete;
 207
 208   // Methods inherited from TAsyncTimeout
 209   virtual void timeoutExpired() noexcept;
 210
 211   std::chrono::milliseconds interval_;
 212
 213   static constexpr int WHEEL_BUCKETS = 4;
 214   static constexpr int WHEEL_BITS = 8;
 215   static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
 216   static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
 217   static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
 218
 219   typedef Callback::List CallbackList;
 220   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
 221
 222   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
 223     return t.count() / interval_.count();
 224   }
 225
 226   bool cascadeTimers(int bucket, int tick);
 227   int64_t nextTick_;
 228   uint64_t count_;
 229   std::chrono::milliseconds now_;
 230
 231   static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
 232
 233   uint32_t catchupEveryN_;
 234   uint32_t expirationsSinceCatchup_;
 235 };
 236
 237 } // folly