X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fio%2Fasync%2FHHWheelTimer.h;h=844ff906bbbfa4107755832efa91603908ab046e;hb=532b8c01aa05334af612233137a836bfe45c3c78;hp=c8602336e8ff363543b2c7aa4f38a446a69a8beb;hpb=09a84b282cc6d0d5498877eb16e50bc7f5c9869f;p=folly.git

diff --git a/folly/io/async/HHWheelTimer.h b/folly/io/async/HHWheelTimer.h
index c8602336..844ff906 100644
--- a/folly/io/async/HHWheelTimer.h
+++ b/folly/io/async/HHWheelTimer.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -33,14 +33,6 @@ namespace folly {
 /**
  * Hashed Hierarchical Wheel Timer
  *
- * Comparison:
- * AsyncTimeout - a single timeout.
- * HHWheelTimer - a set of efficient timeouts with different interval,
- *    but timeouts are not exact.
- *
- * All of the above are O(1) in insertion, tick update and cancel
-
- * This implementation ticks once every 10ms.
  * 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.
@@ -53,8 +45,11 @@ namespace folly {
  * into a different bucket.
  *
  * This technique results in a very cheap mechanism for
- * maintaining time and timers, provided that we can maintain
- * a consistent rate of ticks.
+ * maintaining time and timers.
+ *
+ * Unlike the original timer wheel paper, this implementation does
+ * *not* tick constantly, and instead calculates the exact next wakeup
+ * time.
  */
 class HHWheelTimer : private folly::AsyncTimeout,
                      public folly::DelayedDestruction {
@@ -71,12 +66,11 @@ class HHWheelTimer : private folly::AsyncTimeout,
   /**
    * A callback to be notified when a timeout has expired.
    */
-  class Callback {
+  class Callback
+      : public boost::intrusive::list_base_hook<
+            boost::intrusive::link_mode<boost::intrusive::auto_unlink>> {
    public:
-    Callback()
-      : wheel_(nullptr)
-      , expiration_(0) {}
-
+    Callback() = default;
     virtual ~Callback();
 
     /**
@@ -116,36 +110,31 @@ class HHWheelTimer : private folly::AsyncTimeout,
      * Don't override this unless you're doing a test. This is mainly here so
      * that we can override it to simulate lag in steady_clock.
      */
-    virtual std::chrono::milliseconds getCurTime() {
-      return std::chrono::duration_cast<std::chrono::milliseconds>(
-        std::chrono::steady_clock::now().time_since_epoch());
+    virtual std::chrono::steady_clock::time_point getCurTime() {
+      return std::chrono::steady_clock::now();
     }
 
    private:
     // Get the time remaining until this timeout expires
     std::chrono::milliseconds getTimeRemaining(
-          std::chrono::milliseconds now) const {
+        std::chrono::steady_clock::time_point now) const {
       if (now >= expiration_) {
         return std::chrono::milliseconds(0);
       }
-      return expiration_ - now;
+      return std::chrono::duration_cast<std::chrono::milliseconds>(
+          expiration_ - now);
     }
 
     void setScheduled(HHWheelTimer* wheel,
                       std::chrono::milliseconds);
     void cancelTimeoutImpl();
 
-    HHWheelTimer* wheel_;
-    std::chrono::milliseconds expiration_;
-
-    typedef boost::intrusive::list_member_hook<
-      boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
-
-    ListHook hook_;
+    HHWheelTimer* wheel_{nullptr};
+    std::chrono::steady_clock::time_point expiration_{};
+    int bucket_{-1};
 
     typedef boost::intrusive::list<
       Callback,
-      boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
       boost::intrusive::constant_time_size<false> > List;
 
     std::shared_ptr<RequestContext> context_;
@@ -286,18 +275,28 @@ class HHWheelTimer : private folly::AsyncTimeout,
 
   typedef Callback::List CallbackList;
   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
+  std::vector<uint64_t> bitmap_;
 
   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
     return t.count() / interval_.count();
   }
 
   bool cascadeTimers(int bucket, int tick);
-  int64_t nextTick_;
+  int64_t lastTick_;
+  int64_t expireTick_;
   uint64_t count_;
-  std::chrono::milliseconds now_;
+  std::chrono::steady_clock::time_point startTime_;
+
+  int64_t calcNextTick();
+
+  void scheduleNextTimeout();
 
   bool* processingCallbacksGuard_;
   CallbackList timeouts; // Timeouts queued to run
+
+  std::chrono::steady_clock::time_point getCurTime() {
+    return std::chrono::steady_clock::now();
+  }
 };
 
 } // folly