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