proxygen
folly::HHWheelTimer Class Reference

#include <HHWheelTimer.h>

Inheritance diagram for folly::HHWheelTimer:
folly::AsyncTimeout folly::DelayedDestruction folly::DelayedDestructionBase folly::UndelayedDestruction< HHWheelTimer >

Classes

class  Callback
 

Public Types

using UniquePtr = std::unique_ptr< HHWheelTimer, Destructor >
 
using SharedPtr = std::shared_ptr< HHWheelTimer >
 

Public Member Functions

 HHWheelTimer (folly::TimeoutManager *timeoutManager, std::chrono::milliseconds intervalMS=std::chrono::milliseconds(DEFAULT_TICK_INTERVAL), AsyncTimeout::InternalEnum internal=AsyncTimeout::InternalEnum::NORMAL, std::chrono::milliseconds defaultTimeoutMS=std::chrono::milliseconds(-1))
 
size_t cancelAll ()
 
std::chrono::milliseconds getTickInterval () const
 
std::chrono::milliseconds getDefaultTimeout () const
 
void setDefaultTimeout (std::chrono::milliseconds timeout)
 
void scheduleTimeout (Callback *callback, std::chrono::milliseconds timeout)
 
void scheduleTimeoutImpl (Callback *callback, std::chrono::milliseconds timeout)
 
void scheduleTimeout (Callback *callback)
 
template<class F >
void scheduleTimeoutFn (F fn, std::chrono::milliseconds timeout)
 
std::size_t count () const
 
bool isDetachable () const
 
- Public Member Functions inherited from folly::DelayedDestruction
virtual void destroy ()
 
bool getDestroyPending () const
 
- Public Member Functions inherited from folly::DelayedDestructionBase
virtual ~DelayedDestructionBase ()=default
 

Static Public Member Functions

template<typename... Args>
static UniquePtr newTimer (Args &&...args)
 

Static Public Attributes

static int DEFAULT_TICK_INTERVAL = 10
 

Protected Member Functions

 ~HHWheelTimer () override
 
- Protected Member Functions inherited from folly::DelayedDestruction
 ~DelayedDestruction () override=default
 
 DelayedDestruction ()
 
- Protected Member Functions inherited from folly::DelayedDestructionBase
 DelayedDestructionBase ()
 
uint32_t getDestructorGuardCount () const
 

Private Types

typedef Callback::List CallbackList
 
- Private Types inherited from folly::AsyncTimeout
typedef TimeoutManager::InternalEnum InternalEnum
 

Private Member Functions

 HHWheelTimer (HHWheelTimer const &)=delete
 
HHWheelTimeroperator= (HHWheelTimer const &)=delete
 
void timeoutExpired () noexceptoverride
 
int64_t timeToWheelTicks (std::chrono::milliseconds t)
 
bool cascadeTimers (int bucket, int tick)
 
int64_t calcNextTick ()
 
void scheduleNextTimeout ()
 
std::chrono::steady_clock::time_point getCurTime ()
 
- Private Member Functions inherited from folly::AsyncTimeout
 AsyncTimeout (TimeoutManager *timeoutManager)
 
 AsyncTimeout (EventBase *eventBase)
 
 AsyncTimeout (TimeoutManager *timeoutManager, InternalEnum internal)
 
 AsyncTimeout (EventBase *eventBase, InternalEnum internal)
 
 AsyncTimeout ()
 
virtual ~AsyncTimeout ()
 
bool scheduleTimeout (uint32_t milliseconds)
 
bool scheduleTimeout (TimeoutManager::timeout_type timeout)
 
void cancelTimeout ()
 
bool isScheduled () const
 
void attachTimeoutManager (TimeoutManager *timeoutManager, InternalEnum internal=InternalEnum::NORMAL)
 
void attachEventBase (EventBase *eventBase, InternalEnum internal=InternalEnum::NORMAL)
 
void detachTimeoutManager ()
 
void detachEventBase ()
 
const TimeoutManagergetTimeoutManager ()
 
struct event * getEvent ()
 

Private Attributes

std::chrono::milliseconds interval_
 
std::chrono::milliseconds defaultTimeout_
 
CallbackList buckets_ [WHEEL_BUCKETS][WHEEL_SIZE]
 
std::vector< std::size_t > bitmap_
 
int64_t lastTick_
 
int64_t expireTick_
 
std::size_t count_
 
std::chrono::steady_clock::time_point startTime_
 
bool * processingCallbacksGuard_
 
CallbackList timeouts
 

Static Private Attributes

static constexpr int WHEEL_BUCKETS = 4
 
static constexpr int WHEEL_BITS = 8
 
static constexpr unsigned int WHEEL_SIZE = (1 << WHEEL_BITS)
 
static constexpr unsigned int WHEEL_MASK = (WHEEL_SIZE - 1)
 
static constexpr uint32_t LARGEST_SLOT = 0xffffffffUL
 

Additional Inherited Members

- Static Private Member Functions inherited from folly::AsyncTimeout
template<typename TCallback >
static std::unique_ptr< AsyncTimeoutmake (TimeoutManager &manager, TCallback &&callback)
 
template<typename TCallback >
static std::unique_ptr< AsyncTimeoutschedule (TimeoutManager::timeout_type timeout, TimeoutManager &manager, TCallback &&callback)
 

Detailed Description

Hashed Hierarchical Wheel Timer

We model timers as the number of ticks until the next due event. We allow 32-bits of space to track this due interval, and break that into 4 regions of 8 bits. Each region indexes into a bucket of 256 lists.

Bucket 0 represents those events that are due the soonest. Each tick causes us to look at the next list in a bucket. The 0th list in a bucket is special; it means that it is time to flush the timers from the next higher bucket and schedule them into a different bucket.

This technique results in a very cheap mechanism for maintaining time and timers.

Unlike the original timer wheel paper, this implementation does not tick constantly, and instead calculates the exact next wakeup time.

Definition at line 54 of file HHWheelTimer.h.

Member Typedef Documentation

Definition at line 290 of file HHWheelTimer.h.

using folly::HHWheelTimer::SharedPtr = std::shared_ptr<HHWheelTimer>

Definition at line 58 of file HHWheelTimer.h.

Definition at line 57 of file HHWheelTimer.h.

Constructor & Destructor Documentation

folly::HHWheelTimer::HHWheelTimer ( folly::TimeoutManager timeoutManager,
std::chrono::milliseconds  intervalMS = std::chrono::milliseconds(DEFAULT_TICK_INTERVAL),
AsyncTimeout::InternalEnum  internal = AsyncTimeout::InternalEnum::NORMAL,
std::chrono::milliseconds  defaultTimeoutMS = std::chrono::milliseconds(-1) 
)
explicit

Definition at line 78 of file HHWheelTimer.cpp.

References bitmap_, and WHEEL_SIZE.

Referenced by newTimer().

83  : AsyncTimeout(timeoutMananger, internal),
84  interval_(intervalMS),
85  defaultTimeout_(defaultTimeoutMS),
86  lastTick_(1),
87  expireTick_(1),
88  count_(0),
90  processingCallbacksGuard_(nullptr) {
91  bitmap_.resize((WHEEL_SIZE / sizeof(std::size_t)) / 8, 0);
92 }
std::vector< std::size_t > bitmap_
Definition: HHWheelTimer.h:292
std::chrono::steady_clock::time_point startTime_
Definition: HHWheelTimer.h:302
static constexpr unsigned int WHEEL_SIZE
Definition: HHWheelTimer.h:286
bool * processingCallbacksGuard_
Definition: HHWheelTimer.h:308
std::chrono::milliseconds defaultTimeout_
Definition: HHWheelTimer.h:282
std::size_t count_
Definition: HHWheelTimer.h:301
std::chrono::milliseconds interval_
Definition: HHWheelTimer.h:281
std::chrono::steady_clock::time_point getCurTime()
Definition: HHWheelTimer.h:311
folly::HHWheelTimer::~HHWheelTimer ( )
overrideprotected

Protected destructor.

Use destroy() instead. See the comments in DelayedDestruction for more details.

Definition at line 94 of file HHWheelTimer.cpp.

References cancelAll(), folly::makeGuard(), processingCallbacksGuard_, and timeouts.

Referenced by isDetachable().

94  {
95  // Ensure this gets done, but right before destruction finishes.
96  auto destructionPublisherGuard = folly::makeGuard([&] {
97  // Inform the subscriber that this instance is doomed.
100  }
101  });
102  while (!timeouts.empty()) {
103  auto* cb = &timeouts.front();
104  timeouts.pop_front();
105  cb->cancelTimeout();
106  cb->callbackCanceled();
107  }
108  cancelAll();
109 }
bool * processingCallbacksGuard_
Definition: HHWheelTimer.h:308
CallbackList timeouts
Definition: HHWheelTimer.h:309
FOLLY_NODISCARD detail::ScopeGuardImplDecay< F, true > makeGuard(F &&f) noexcept(noexcept(detail::ScopeGuardImplDecay< F, true >(static_cast< F && >(f))))
Definition: ScopeGuard.h:184
folly::HHWheelTimer::HHWheelTimer ( HHWheelTimer const &  )
privatedelete

Member Function Documentation

int64_t folly::HHWheelTimer::calcNextTick ( )
private

Definition at line 307 of file HHWheelTimer.cpp.

References getCurTime(), interval_, lastTick_, processingCallbacksGuard_, and startTime_.

Referenced by scheduleNextTimeout(), scheduleTimeoutImpl(), and timeoutExpired().

307  {
308  auto intervals = (getCurTime() - startTime_) / interval_;
309  // Slow eventbases will have skew between the actual time and the
310  // callback time. To avoid racing the next scheduleNextTimeout()
311  // call, always schedule new timeouts against the actual
312  // timeoutExpired() time.
314  return intervals;
315  } else {
316  return lastTick_;
317  }
318 }
std::chrono::steady_clock::time_point startTime_
Definition: HHWheelTimer.h:302
bool * processingCallbacksGuard_
Definition: HHWheelTimer.h:308
std::chrono::milliseconds interval_
Definition: HHWheelTimer.h:281
std::chrono::steady_clock::time_point getCurTime()
Definition: HHWheelTimer.h:311
size_t folly::HHWheelTimer::cancelAll ( )

Cancel all outstanding timeouts

Returns
the number of timeouts that were cancelled.

Definition at line 247 of file HHWheelTimer.cpp.

References buckets_, count(), count_, i, min, folly::f14::swap(), WHEEL_BUCKETS, and WHEEL_SIZE.

Referenced by TEST_F(), and ~HHWheelTimer().

247  {
248  size_t count = 0;
249 
250  if (count_ != 0) {
251  const std::size_t numElements = WHEEL_BUCKETS * WHEEL_SIZE;
252  auto maxBuckets = std::min(numElements, count_);
253  auto buckets = std::make_unique<CallbackList[]>(maxBuckets);
254  size_t countBuckets = 0;
255  for (auto& tick : buckets_) {
256  for (auto& bucket : tick) {
257  if (bucket.empty()) {
258  continue;
259  }
260  count += bucket.size();
261  std::swap(bucket, buckets[countBuckets++]);
262  if (count >= count_) {
263  break;
264  }
265  }
266  }
267 
268  for (size_t i = 0; i < countBuckets; ++i) {
269  auto& bucket = buckets[i];
270  while (!bucket.empty()) {
271  auto& cb = bucket.front();
272  cb.cancelTimeout();
273  cb.callbackCanceled();
274  }
275  }
276  }
277 
278  return count;
279 }
static constexpr int WHEEL_BUCKETS
Definition: HHWheelTimer.h:284
CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE]
Definition: HHWheelTimer.h:291
LogLevel min
Definition: LogLevel.cpp:30
static constexpr unsigned int WHEEL_SIZE
Definition: HHWheelTimer.h:286
std::size_t count() const
Definition: HHWheelTimer.h:252
void swap(SwapTrackingAlloc< T > &, SwapTrackingAlloc< T > &)
Definition: F14TestUtil.h:414
std::size_t count_
Definition: HHWheelTimer.h:301
bool folly::HHWheelTimer::cascadeTimers ( int  bucket,
int  tick 
)
private

Definition at line 171 of file HHWheelTimer.cpp.

References buckets_, getCurTime(), and scheduleTimeoutImpl().

Referenced by timeoutExpired(), and timeToWheelTicks().

171  {
172  CallbackList cbs;
173  cbs.swap(buckets_[bucket][tick]);
174  while (!cbs.empty()) {
175  auto* cb = &cbs.front();
176  cbs.pop_front();
177  scheduleTimeoutImpl(cb, cb->getTimeRemaining(getCurTime()));
178  }
179 
180  // If tick is zero, timeoutExpired will cascade the next bucket.
181  return tick == 0;
182 }
CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE]
Definition: HHWheelTimer.h:291
void scheduleTimeoutImpl(Callback *callback, std::chrono::milliseconds timeout)
Callback::List CallbackList
Definition: HHWheelTimer.h:290
std::chrono::steady_clock::time_point getCurTime()
Definition: HHWheelTimer.h:311
std::size_t folly::HHWheelTimer::count ( ) const
inline

Return the number of currently pending timeouts

Definition at line 252 of file HHWheelTimer.h.

References count_.

Referenced by cancelAll(), and TEST_F().

252  {
253  return count_;
254  }
std::size_t count_
Definition: HHWheelTimer.h:301
std::chrono::steady_clock::time_point folly::HHWheelTimer::getCurTime ( )
inlineprivate

Definition at line 311 of file HHWheelTimer.h.

References now().

Referenced by calcNextTick(), and cascadeTimers().

311  {
313  }
std::chrono::steady_clock::time_point now()
std::chrono::milliseconds folly::HHWheelTimer::getDefaultTimeout ( ) const
inline

Get the default timeout interval for this HHWheelTimer.

Returns the timeout interval in milliseconds.

Definition at line 193 of file HHWheelTimer.h.

References defaultTimeout_.

Referenced by TEST_F(), and proxygen::WheelTimerInstance::WheelTimerInstance().

193  {
194  return defaultTimeout_;
195  }
std::chrono::milliseconds defaultTimeout_
Definition: HHWheelTimer.h:282
std::chrono::milliseconds folly::HHWheelTimer::getTickInterval ( ) const
inline

Get the tick interval for this HHWheelTimer.

Returns the tick interval in milliseconds.

Definition at line 184 of file HHWheelTimer.h.

References interval_.

184  {
185  return interval_;
186  }
std::chrono::milliseconds interval_
Definition: HHWheelTimer.h:281
template<typename... Args>
static UniquePtr folly::HHWheelTimer::newTimer ( Args &&...  args)
inlinestatic

Definition at line 61 of file HHWheelTimer.h.

References HHWheelTimer().

Referenced by HTTPUpstreamTest< SPDY3CodecPair >::HTTPUpstreamTest(), proxygen::makeInternalTimeoutSet(), proxygen::makeTimeoutSet(), TEST_F(), folly::ThreadWheelTimekeeper::ThreadWheelTimekeeper(), TimeoutableHTTPUpstreamTest< C >::TimeoutableHTTPUpstreamTest(), and folly::EventBase::timer().

61  {
62  return UniquePtr(new HHWheelTimer(std::forward<Args>(args)...));
63  }
HHWheelTimer(folly::TimeoutManager *timeoutManager, std::chrono::milliseconds intervalMS=std::chrono::milliseconds(DEFAULT_TICK_INTERVAL), AsyncTimeout::InternalEnum internal=AsyncTimeout::InternalEnum::NORMAL, std::chrono::milliseconds defaultTimeoutMS=std::chrono::milliseconds(-1))
std::unique_ptr< HHWheelTimer, Destructor > UniquePtr
Definition: HHWheelTimer.h:57
HHWheelTimer& folly::HHWheelTimer::operator= ( HHWheelTimer const &  )
privatedelete

Referenced by isDetachable().

void folly::HHWheelTimer::scheduleNextTimeout ( )
private

Definition at line 281 of file HHWheelTimer.cpp.

References bitmap_, calcNextTick(), folly::AsyncTimeout::cancelTimeout(), count_, expireTick_, folly::findFirstSet(), int64_t, interval_, folly::AsyncTimeout::isScheduled(), folly::makeBitIterator(), folly::AsyncTimeout::scheduleTimeout(), WHEEL_MASK, and WHEEL_SIZE.

Referenced by scheduleTimeout(), and timeoutExpired().

281  {
282  auto nextTick = calcNextTick();
283  int64_t tick = 1;
284 
285  if (nextTick & WHEEL_MASK) {
286  auto bi = makeBitIterator(bitmap_.begin());
287  auto bi_end = makeBitIterator(bitmap_.end());
288  auto it = folly::findFirstSet(bi + (nextTick & WHEEL_MASK), bi_end);
289  if (it == bi_end) {
290  tick = WHEEL_SIZE - ((nextTick - 1) & WHEEL_MASK);
291  } else {
292  tick = std::distance(bi + (nextTick & WHEEL_MASK), it) + 1;
293  }
294  }
295 
296  if (count_ > 0) {
297  if (!this->AsyncTimeout::isScheduled() ||
298  (expireTick_ > tick + nextTick - 1)) {
300  expireTick_ = tick + nextTick - 1;
301  }
302  } else {
304  }
305 }
static constexpr unsigned int WHEEL_MASK
Definition: HHWheelTimer.h:287
BitIterator< BaseIter > findFirstSet(BitIterator< BaseIter >, BitIterator< BaseIter >)
Definition: BitIterator.h:170
BitIterator< BaseIter > makeBitIterator(const BaseIter &iter)
Definition: BitIterator.h:161
std::vector< std::size_t > bitmap_
Definition: HHWheelTimer.h:292
static constexpr unsigned int WHEEL_SIZE
Definition: HHWheelTimer.h:286
bool scheduleTimeout(uint32_t milliseconds)
bool isScheduled() const
std::size_t count_
Definition: HHWheelTimer.h:301
std::chrono::milliseconds interval_
Definition: HHWheelTimer.h:281
void folly::HHWheelTimer::scheduleTimeout ( Callback callback,
std::chrono::milliseconds  timeout 
)

Schedule the specified Callback to be invoked after the specified timeout interval.

If the callback is already scheduled, this cancels the existing timeout before scheduling the new timeout.

Definition at line 144 of file HHWheelTimer.cpp.

References folly::HHWheelTimer::Callback::cancelTimeout(), count_, processingCallbacksGuard_, folly::HHWheelTimer::Callback::requestContext_, folly::RequestContext::saveContext(), scheduleNextTimeout(), scheduleTimeoutImpl(), and folly::HHWheelTimer::Callback::setScheduled().

Referenced by proxygen::HTTPTransaction::maybeDelayForRateLimit(), proxygen::WheelTimerInstance::scheduleTimeout(), scheduleTimeout(), scheduleTimeoutFn(), setDefaultTimeout(), TEST_F(), and TestTimeout::TestTimeout().

146  {
147  // Cancel the callback if it happens to be scheduled already.
148  callback->cancelTimeout();
149 
150  callback->requestContext_ = RequestContext::saveContext();
151 
152  count_++;
153 
154  callback->setScheduled(this, timeout);
155  scheduleTimeoutImpl(callback, timeout);
156 
157  /* If we're calling callbacks, timer will be reset after all
158  * callbacks are called.
159  */
162  }
163 }
static std::shared_ptr< RequestContext > saveContext()
Definition: Request.h:196
void scheduleTimeoutImpl(Callback *callback, std::chrono::milliseconds timeout)
bool * processingCallbacksGuard_
Definition: HHWheelTimer.h:308
std::size_t count_
Definition: HHWheelTimer.h:301
void folly::HHWheelTimer::scheduleTimeout ( Callback callback)

Schedule the specified Callback to be invoked after the default timeout interval.

If the callback is already scheduled, this cancels the existing timeout before scheduling the new timeout.

This method uses CHECK() to make sure that the default timeout was specified on the object initialization.

Definition at line 165 of file HHWheelTimer.cpp.

References defaultTimeout_, and scheduleTimeout().

165  {
166  CHECK(std::chrono::milliseconds(-1) != defaultTimeout_)
167  << "Default timeout was not initialized";
168  scheduleTimeout(callback, defaultTimeout_);
169 }
void scheduleTimeout(Callback *callback, std::chrono::milliseconds timeout)
std::chrono::milliseconds defaultTimeout_
Definition: HHWheelTimer.h:282
template<class F >
void folly::HHWheelTimer::scheduleTimeoutFn ( fn,
std::chrono::milliseconds  timeout 
)
inline

Definition at line 229 of file HHWheelTimer.h.

References f, folly::gen::move, folly::pushmi::__adl::noexcept(), scheduleTimeout(), and folly::HHWheelTimer::Callback::timeoutExpired().

Referenced by folly::EventBase::scheduleAt(), and TEST_F().

229  {
230  struct Wrapper : Callback {
231  Wrapper(F f) : fn_(std::move(f)) {}
232  void timeoutExpired() noexcept override {
233  try {
234  fn_();
235  } catch (std::exception const& e) {
236  LOG(ERROR) << "HHWheelTimer timeout callback threw an exception: "
237  << e.what();
238  } catch (...) {
239  LOG(ERROR) << "HHWheelTimer timeout callback threw a non-exception.";
240  }
241  delete this;
242  }
243  F fn_;
244  };
245  Wrapper* w = new Wrapper(std::move(fn));
246  scheduleTimeout(w, timeout);
247  }
auto f
void timeoutExpired() noexceptoverride
constexpr detail::Map< Move > move
Definition: Base-inl.h:2567
STL namespace.
requires E e noexcept(noexcept(s.error(std::move(e))))
void scheduleTimeout(Callback *callback, std::chrono::milliseconds timeout)
void folly::HHWheelTimer::scheduleTimeoutImpl ( Callback callback,
std::chrono::milliseconds  timeout 
)

Definition at line 111 of file HHWheelTimer.cpp.

References bitmap_, folly::HHWheelTimer::Callback::bucket_, buckets_, calcNextTick(), diff(), int64_t, LARGEST_SLOT, bm::list, folly::makeBitIterator(), timeToWheelTicks(), WHEEL_BITS, WHEEL_MASK, and WHEEL_SIZE.

Referenced by cascadeTimers(), scheduleTimeout(), and setDefaultTimeout().

113  {
114  auto nextTick = calcNextTick();
115  int64_t due = timeToWheelTicks(timeout) + nextTick;
116  int64_t diff = due - nextTick;
118 
119  auto bi = makeBitIterator(bitmap_.begin());
120 
121  if (diff < 0) {
122  list = &buckets_[0][nextTick & WHEEL_MASK];
123  *(bi + (nextTick & WHEEL_MASK)) = true;
124  callback->bucket_ = nextTick & WHEEL_MASK;
125  } else if (diff < WHEEL_SIZE) {
126  list = &buckets_[0][due & WHEEL_MASK];
127  *(bi + (due & WHEEL_MASK)) = true;
128  callback->bucket_ = due & WHEEL_MASK;
129  } else if (diff < 1 << (2 * WHEEL_BITS)) {
130  list = &buckets_[1][(due >> WHEEL_BITS) & WHEEL_MASK];
131  } else if (diff < 1 << (3 * WHEEL_BITS)) {
132  list = &buckets_[2][(due >> 2 * WHEEL_BITS) & WHEEL_MASK];
133  } else {
134  /* in largest slot */
135  if (diff > LARGEST_SLOT) {
136  diff = LARGEST_SLOT;
137  due = diff + nextTick;
138  }
139  list = &buckets_[3][(due >> 3 * WHEEL_BITS) & WHEEL_MASK];
140  }
141  list->push_back(*callback);
142 }
static constexpr unsigned int WHEEL_MASK
Definition: HHWheelTimer.h:287
static constexpr int WHEEL_BITS
Definition: HHWheelTimer.h:285
BitIterator< BaseIter > makeBitIterator(const BaseIter &iter)
Definition: BitIterator.h:161
static constexpr uint32_t LARGEST_SLOT
Definition: HHWheelTimer.h:288
std::vector< std::size_t > bitmap_
Definition: HHWheelTimer.h:292
CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE]
Definition: HHWheelTimer.h:291
Encoder::MutableCompressedList list
static constexpr unsigned int WHEEL_SIZE
Definition: HHWheelTimer.h:286
uint64_t diff(uint64_t a, uint64_t b)
Definition: FutexTest.cpp:135
int64_t timeToWheelTicks(std::chrono::milliseconds t)
Definition: HHWheelTimer.h:294
Callback::List CallbackList
Definition: HHWheelTimer.h:290
void folly::HHWheelTimer::setDefaultTimeout ( std::chrono::milliseconds  timeout)
inline

Set the default timeout interval for this HHWheelTimer.

Definition at line 200 of file HHWheelTimer.h.

References defaultTimeout_, scheduleTimeout(), scheduleTimeoutImpl(), and folly::detail::timeout.

Referenced by TEST_F().

200  {
202  }
std::chrono::milliseconds defaultTimeout_
Definition: HHWheelTimer.h:282
void folly::HHWheelTimer::timeoutExpired ( )
overrideprivatevirtualnoexcept

timeoutExpired() is invoked when the timeout period has expired.

Implements folly::AsyncTimeout.

Definition at line 184 of file HHWheelTimer.cpp.

References bitmap_, buckets_, calcNextTick(), cascadeTimers(), count_, expireTick_, lastTick_, folly::makeBitIterator(), folly::makeGuard(), processingCallbacksGuard_, scheduleNextTimeout(), timeouts, WHEEL_BITS, and WHEEL_MASK.

184  {
185  auto nextTick = calcNextTick();
186 
187  // If the last smart pointer for "this" is reset inside the callback's
188  // timeoutExpired(), then the guard will detect that it is time to bail from
189  // this method.
190  auto isDestroyed = false;
191  // If scheduleTimeout is called from a callback in this function, it may
192  // cause inconsistencies in the state of this object. As such, we need
193  // to treat these calls slightly differently.
195  processingCallbacksGuard_ = &isDestroyed;
196  auto reEntryGuard = folly::makeGuard([&] {
197  if (!isDestroyed) {
198  processingCallbacksGuard_ = nullptr;
199  }
200  });
201 
202  // timeoutExpired() can only be invoked directly from the event base loop.
203  // It should never be invoked recursively.
204  //
206  while (lastTick_ < nextTick) {
207  int idx = lastTick_ & WHEEL_MASK;
208 
209  auto bi = makeBitIterator(bitmap_.begin());
210  *(bi + idx) = false;
211 
212  lastTick_++;
213  CallbackList* cbs = &buckets_[0][idx];
214  while (!cbs->empty()) {
215  auto* cb = &cbs->front();
216  cbs->pop_front();
217  timeouts.push_back(*cb);
218  }
219 
220  if (idx == 0) {
221  // Cascade timers
222  if (cascadeTimers(1, (lastTick_ >> WHEEL_BITS) & WHEEL_MASK) &&
223  cascadeTimers(2, (lastTick_ >> (2 * WHEEL_BITS)) & WHEEL_MASK)) {
224  cascadeTimers(3, (lastTick_ >> (3 * WHEEL_BITS)) & WHEEL_MASK);
225  }
226  }
227  }
228 
229  while (!timeouts.empty()) {
230  auto* cb = &timeouts.front();
231  timeouts.pop_front();
232  count_--;
233  cb->wheel_ = nullptr;
234  cb->expiration_ = {};
235  RequestContextScopeGuard rctx(cb->requestContext_);
236  cb->timeoutExpired();
237  if (isDestroyed) {
238  // The HHWheelTimer itself has been destroyed. The other callbacks
239  // will have been cancelled from the destructor. Bail before causing
240  // damage.
241  return;
242  }
243  }
245 }
static constexpr unsigned int WHEEL_MASK
Definition: HHWheelTimer.h:287
static constexpr int WHEEL_BITS
Definition: HHWheelTimer.h:285
BitIterator< BaseIter > makeBitIterator(const BaseIter &iter)
Definition: BitIterator.h:161
std::vector< std::size_t > bitmap_
Definition: HHWheelTimer.h:292
CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE]
Definition: HHWheelTimer.h:291
bool * processingCallbacksGuard_
Definition: HHWheelTimer.h:308
CallbackList timeouts
Definition: HHWheelTimer.h:309
FOLLY_NODISCARD detail::ScopeGuardImplDecay< F, true > makeGuard(F &&f) noexcept(noexcept(detail::ScopeGuardImplDecay< F, true >(static_cast< F && >(f))))
Definition: ScopeGuard.h:184
Callback::List CallbackList
Definition: HHWheelTimer.h:290
bool cascadeTimers(int bucket, int tick)
std::size_t count_
Definition: HHWheelTimer.h:301
int64_t folly::HHWheelTimer::timeToWheelTicks ( std::chrono::milliseconds  t)
inlineprivate

Definition at line 294 of file HHWheelTimer.h.

References cascadeTimers().

Referenced by scheduleTimeoutImpl().

294  {
295  return t.count() / interval_.count();
296  }
std::chrono::milliseconds interval_
Definition: HHWheelTimer.h:281

Member Data Documentation

std::vector<std::size_t> folly::HHWheelTimer::bitmap_
private
std::size_t folly::HHWheelTimer::count_
private
int folly::HHWheelTimer::DEFAULT_TICK_INTERVAL = 10
static

Create a new HHWheelTimer with the specified interval and the default timeout value set.

Objects created using this version of constructor can be used to schedule both variable interval timeouts using scheduleTimeout(callback, timeout) method, and default interval timeouts using scheduleTimeout(callback) method.

We want to select the default interval carefully. An interval of 10ms will give us 10ms * WHEEL_SIZE^WHEEL_BUCKETS for the largest timeout possible, or about 497 days.

For a lower bound, we want a reasonable limit on local IO, 10ms seems short enough

A shorter interval also has CPU implications, less than 1ms might start showing up in cpu perf. Also, it might not be possible to set tick interval less than 10ms on older kernels.

Definition at line 163 of file HHWheelTimer.h.

Referenced by HTTPUpstreamTest< SPDY3CodecPair >::HTTPUpstreamTest(), proxygen::makeInternalTimeoutSet(), proxygen::makeTimeoutSet(), ScopedServerTest::SetUp(), TEST(), TEST_F(), and TimeoutableHTTPUpstreamTest< C >::TimeoutableHTTPUpstreamTest().

std::chrono::milliseconds folly::HHWheelTimer::defaultTimeout_
private

Definition at line 282 of file HHWheelTimer.h.

Referenced by getDefaultTimeout(), scheduleTimeout(), and setDefaultTimeout().

int64_t folly::HHWheelTimer::expireTick_
private

Definition at line 300 of file HHWheelTimer.h.

Referenced by scheduleNextTimeout(), and timeoutExpired().

std::chrono::milliseconds folly::HHWheelTimer::interval_
private

Definition at line 281 of file HHWheelTimer.h.

Referenced by calcNextTick(), getTickInterval(), and scheduleNextTimeout().

constexpr uint32_t folly::HHWheelTimer::LARGEST_SLOT = 0xffffffffUL
staticprivate

Definition at line 288 of file HHWheelTimer.h.

Referenced by scheduleTimeoutImpl().

int64_t folly::HHWheelTimer::lastTick_
private

Definition at line 299 of file HHWheelTimer.h.

Referenced by calcNextTick(), and timeoutExpired().

bool* folly::HHWheelTimer::processingCallbacksGuard_
private

Definition at line 308 of file HHWheelTimer.h.

Referenced by calcNextTick(), scheduleTimeout(), timeoutExpired(), and ~HHWheelTimer().

std::chrono::steady_clock::time_point folly::HHWheelTimer::startTime_
private

Definition at line 302 of file HHWheelTimer.h.

Referenced by calcNextTick().

CallbackList folly::HHWheelTimer::timeouts
private

Definition at line 309 of file HHWheelTimer.h.

Referenced by timeoutExpired(), and ~HHWheelTimer().

constexpr int folly::HHWheelTimer::WHEEL_BITS = 8
staticprivate

Definition at line 285 of file HHWheelTimer.h.

Referenced by scheduleTimeoutImpl(), and timeoutExpired().

constexpr int folly::HHWheelTimer::WHEEL_BUCKETS = 4
staticprivate

Definition at line 284 of file HHWheelTimer.h.

Referenced by cancelAll().

constexpr unsigned int folly::HHWheelTimer::WHEEL_MASK = (WHEEL_SIZE - 1)
staticprivate

Definition at line 287 of file HHWheelTimer.h.

Referenced by scheduleNextTimeout(), scheduleTimeoutImpl(), and timeoutExpired().

constexpr unsigned int folly::HHWheelTimer::WHEEL_SIZE = (1 << WHEEL_BITS)
staticprivate

Definition at line 286 of file HHWheelTimer.h.

Referenced by cancelAll(), HHWheelTimer(), scheduleNextTimeout(), and scheduleTimeoutImpl().


The documentation for this class was generated from the following files: