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     /// 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
 158   /**
 159    * Destroy the HHWheelTimer.
 160    *
 161    * A HHWheelTimer should only be destroyed when there are no more
 162    * callbacks pending in the set. (If it helps you may use cancelAll() to
 163    * cancel all pending timeouts explicitly before calling this.)
 164    */
 165   virtual void destroy();
 166
 167   /**
 168    * Cancel all outstanding timeouts
 169    *
 170    * @returns the number of timeouts that were cancelled.
 171    */
 172   size_t cancelAll();
 173
 174   /**
 175    * Get the tick interval for this HHWheelTimer.
 176    *
 177    * Returns the tick interval in milliseconds.
 178    */
 179   std::chrono::milliseconds getTickInterval() const {
 180     return interval_;
 181   }
 182
 183   /**
 184    * Schedule the specified Callback to be invoked after the
 185    * specified timeout interval.
 186    *
 187    * If the callback is already scheduled, this cancels the existing timeout
 188    * before scheduling the new timeout.
 189    */
 190   void scheduleTimeout(Callback* callback,
 191                        std::chrono::milliseconds timeout);
 192   void scheduleTimeoutImpl(Callback* callback,
 193                        std::chrono::milliseconds timeout);
 194
 195   template <class F>
 196   void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
 197     struct Wrapper : Callback {
 198       Wrapper(F f) : fn_(std::move(f)) {}
 199       void timeoutExpired() noexcept override {
 200         try {
 201           fn_();
 202         } catch (std::exception const& e) {
 203           LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
 204             << e.what();
 205         } catch (...) {
 206           LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
 207         }
 208         delete this;
 209       }
 210       F fn_;
 211     };
 212     Wrapper* w = new Wrapper(std::move(fn));
 213     scheduleTimeout(w, timeout);
 214   }
 215
 216   /**
 217    * Return the number of currently pending timeouts
 218    */
 219   uint64_t count() const {
 220     return count_;
 221   }
 222
 223   /**
 224    * This turns on more exact timing.  By default the wheel timer
 225    * increments its cached time only once everyN (default) ticks.
 226    *
 227    * With catchupEveryN at 1, timeouts will only be delayed until the
 228    * next tick, at which point all overdue timeouts are called.  The
 229    * wheel timer is approximately 2x slower with this set to 1.
 230    *
 231    * Load testing in opt mode showed skew was about 1% with no catchup.
 232    */
 233   void setCatchupEveryN(uint32_t everyN) {
 234     catchupEveryN_ = everyN;
 235   }
 236
 237   bool isDetachable() const {
 238     return !folly::AsyncTimeout::isScheduled();
 239   }
 240
 241   using folly::AsyncTimeout::attachEventBase;
 242   using folly::AsyncTimeout::detachEventBase;
 243   using folly::AsyncTimeout::getTimeoutManager;
 244
 245  protected:
 246   /**
 247    * Protected destructor.
 248    *
 249    * Use destroy() instead.  See the comments in DelayedDestruction for more
 250    * details.
 251    */
 252   virtual ~HHWheelTimer();
 253
 254  private:
 255   // Forbidden copy constructor and assignment operator
 256   HHWheelTimer(HHWheelTimer const &) = delete;
 257   HHWheelTimer& operator=(HHWheelTimer const &) = delete;
 258
 259   // Methods inherited from TAsyncTimeout
 260   virtual void timeoutExpired() noexcept;
 261
 262   std::chrono::milliseconds interval_;
 263
 264   static constexpr int WHEEL_BUCKETS = 4;
 265   static constexpr int WHEEL_BITS = 8;
 266   static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
 267   static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
 268   static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
 269
 270   typedef Callback::List CallbackList;
 271   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
 272
 273   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
 274     return t.count() / interval_.count();
 275   }
 276
 277   bool cascadeTimers(int bucket, int tick);
 278   int64_t nextTick_;
 279   uint64_t count_;
 280   std::chrono::milliseconds now_;
 281
 282   static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
 283
 284   uint32_t catchupEveryN_;
 285   uint32_t expirationsSinceCatchup_;
 286   bool processingCallbacksGuard_;
 287 };
 288
 289 } // folly