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