folly/io/async/HHWheelTimer.h

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