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  * AsyncTimeout - 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   template <typename... Args>
  64   static UniquePtr newTimer(Args&&... args) {
  65     return UniquePtr(new HHWheelTimer(std::forward<Args>(args)...));
  66   }
  67
  68   /**
  69    * A callback to be notified when a timeout has expired.
  70    */
  71   class Callback {
  72    public:
  73     Callback()
  74       : wheel_(nullptr)
  75       , expiration_(0) {}
  76
  77     virtual ~Callback();
  78
  79     /**
  80      * timeoutExpired() is invoked when the timeout has expired.
  81      */
  82     virtual void timeoutExpired() noexcept = 0;
  83
  84     /// This callback was canceled. The default implementation is to just
  85     /// proxy to `timeoutExpired` but if you care about the difference between
  86     /// the timeout finishing or being canceled you can override this.
  87     virtual void callbackCanceled() noexcept {
  88       timeoutExpired();
  89     }
  90
  91     /**
  92      * Cancel the timeout, if it is running.
  93      *
  94      * If the timeout is not scheduled, cancelTimeout() does nothing.
  95      */
  96     void cancelTimeout() {
  97       if (wheel_ == nullptr) {
  98         // We're not scheduled, so there's nothing to do.
  99         return;
 100       }
 101       cancelTimeoutImpl();
 102     }
 103
 104     /**
 105      * Return true if this timeout is currently scheduled, and false otherwise.
 106      */
 107     bool isScheduled() const {
 108       return wheel_ != nullptr;
 109     }
 110
 111    protected:
 112     /**
 113      * Don't override this unless you're doing a test. This is mainly here so
 114      * that we can override it to simulate lag in steady_clock.
 115      */
 116     virtual std::chrono::milliseconds getCurTime() {
 117       return std::chrono::duration_cast<std::chrono::milliseconds>(
 118         std::chrono::steady_clock::now().time_since_epoch());
 119     }
 120
 121    private:
 122     // Get the time remaining until this timeout expires
 123     std::chrono::milliseconds getTimeRemaining(
 124           std::chrono::milliseconds now) const {
 125       if (now >= expiration_) {
 126         return std::chrono::milliseconds(0);
 127       }
 128       return expiration_ - now;
 129     }
 130
 131     void setScheduled(HHWheelTimer* wheel,
 132                       std::chrono::milliseconds);
 133     void cancelTimeoutImpl();
 134
 135     HHWheelTimer* wheel_;
 136     std::chrono::milliseconds expiration_;
 137
 138     typedef boost::intrusive::list_member_hook<
 139       boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
 140
 141     ListHook hook_;
 142
 143     typedef boost::intrusive::list<
 144       Callback,
 145       boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
 146       boost::intrusive::constant_time_size<false> > List;
 147
 148     std::shared_ptr<RequestContext> context_;
 149
 150     // Give HHWheelTimer direct access to our members so it can take care
 151     // of scheduling/cancelling.
 152     friend class HHWheelTimer;
 153   };
 154
 155   /**
 156    * Create a new HHWheelTimer with the specified interval and the
 157    * default timeout value set.
 158    *
 159    * Objects created using this version of constructor can be used
 160    * to schedule both variable interval timeouts using
 161    * scheduleTimeout(callback, timeout) method, and default
 162    * interval timeouts using scheduleTimeout(callback) method.
 163    */
 164   static int DEFAULT_TICK_INTERVAL;
 165   explicit HHWheelTimer(folly::EventBase* eventBase,
 166                         std::chrono::milliseconds intervalMS =
 167                         std::chrono::milliseconds(DEFAULT_TICK_INTERVAL),
 168                         AsyncTimeout::InternalEnum internal =
 169                         AsyncTimeout::InternalEnum::NORMAL,
 170                         std::chrono::milliseconds defaultTimeoutMS =
 171                         std::chrono::milliseconds(-1));
 172
 173   /**
 174    * Destroy the HHWheelTimer.
 175    *
 176    * A HHWheelTimer should only be destroyed when there are no more
 177    * callbacks pending in the set. (If it helps you may use cancelAll() to
 178    * cancel all pending timeouts explicitly before calling this.)
 179    */
 180   virtual void destroy();
 181
 182   /**
 183    * Cancel all outstanding timeouts
 184    *
 185    * @returns the number of timeouts that were cancelled.
 186    */
 187   size_t cancelAll();
 188
 189   /**
 190    * Get the tick interval for this HHWheelTimer.
 191    *
 192    * Returns the tick interval in milliseconds.
 193    */
 194   std::chrono::milliseconds getTickInterval() const {
 195     return interval_;
 196   }
 197
 198   /**
 199    * Get the default timeout interval for this HHWheelTimer.
 200    *
 201    * Returns the timeout interval in milliseconds.
 202    */
 203   std::chrono::milliseconds getDefaultTimeout() const {
 204     return defaultTimeout_;
 205   }
 206
 207   /**
 208    * Schedule the specified Callback to be invoked after the
 209    * specified timeout interval.
 210    *
 211    * If the callback is already scheduled, this cancels the existing timeout
 212    * before scheduling the new timeout.
 213    */
 214   void scheduleTimeout(Callback* callback,
 215                        std::chrono::milliseconds timeout);
 216   void scheduleTimeoutImpl(Callback* callback,
 217                        std::chrono::milliseconds timeout);
 218
 219   /**
 220    * Schedule the specified Callback to be invoked after the
 221    * fefault timeout interval.
 222    *
 223    * If the callback is already scheduled, this cancels the existing timeout
 224    * before scheduling the new timeout.
 225    *
 226    * This method uses CHECK() to make sure that the default timeout was
 227    * specified on the object initialization.
 228    */
 229   void scheduleTimeout(Callback* callback);
 230
 231   template <class F>
 232   void scheduleTimeoutFn(F fn, std::chrono::milliseconds timeout) {
 233     struct Wrapper : Callback {
 234       Wrapper(F f) : fn_(std::move(f)) {}
 235       void timeoutExpired() noexcept override {
 236         try {
 237           fn_();
 238         } catch (std::exception const& e) {
 239           LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
 240             << e.what();
 241         } catch (...) {
 242           LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
 243         }
 244         delete this;
 245       }
 246       F fn_;
 247     };
 248     Wrapper* w = new Wrapper(std::move(fn));
 249     scheduleTimeout(w, timeout);
 250   }
 251
 252   /**
 253    * Return the number of currently pending timeouts
 254    */
 255   uint64_t count() const {
 256     return count_;
 257   }
 258
 259   /**
 260    * This turns on more exact timing.  By default the wheel timer
 261    * increments its cached time only once everyN (default) ticks.
 262    *
 263    * With catchupEveryN at 1, timeouts will only be delayed until the
 264    * next tick, at which point all overdue timeouts are called.  The
 265    * wheel timer is approximately 2x slower with this set to 1.
 266    *
 267    * Load testing in opt mode showed skew was about 1% with no catchup.
 268    */
 269   void setCatchupEveryN(uint32_t everyN) {
 270     catchupEveryN_ = everyN;
 271   }
 272
 273   bool isDetachable() const {
 274     return !folly::AsyncTimeout::isScheduled();
 275   }
 276
 277   using folly::AsyncTimeout::attachEventBase;
 278   using folly::AsyncTimeout::detachEventBase;
 279   using folly::AsyncTimeout::getTimeoutManager;
 280
 281  protected:
 282   /**
 283    * Protected destructor.
 284    *
 285    * Use destroy() instead.  See the comments in DelayedDestruction for more
 286    * details.
 287    */
 288   virtual ~HHWheelTimer();
 289
 290  private:
 291   // Forbidden copy constructor and assignment operator
 292   HHWheelTimer(HHWheelTimer const &) = delete;
 293   HHWheelTimer& operator=(HHWheelTimer const &) = delete;
 294
 295   // Methods inherited from AsyncTimeout
 296   virtual void timeoutExpired() noexcept;
 297
 298   std::chrono::milliseconds interval_;
 299   std::chrono::milliseconds defaultTimeout_;
 300
 301   static constexpr int WHEEL_BUCKETS = 4;
 302   static constexpr int WHEEL_BITS = 8;
 303   static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS);
 304   static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1);
 305   static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL;
 306
 307   typedef Callback::List CallbackList;
 308   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
 309
 310   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
 311     return t.count() / interval_.count();
 312   }
 313
 314   bool cascadeTimers(int bucket, int tick);
 315   int64_t nextTick_;
 316   uint64_t count_;
 317   std::chrono::milliseconds now_;
 318
 319   static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
 320
 321   uint32_t catchupEveryN_;
 322   uint32_t expirationsSinceCatchup_;
 323   bool processingCallbacksGuard_;
 324 };
 325
 326 } // folly