Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <chrono>
       4             : #include <stack>
       5             : 
       6             : #include "envoy/event/dispatcher.h"
       7             : #include "envoy/event/scaled_range_timer_manager.h"
       8             : #include "envoy/event/timer.h"
       9             : 
      10             : #include "absl/container/flat_hash_map.h"
      11             : 
      12             : namespace Envoy {
      13             : namespace Event {
      14             : 
      15             : /**
      16             :  * Implementation class for ScaledRangeTimerManager. Internally, this uses a set of queues to track
      17             :  * timers. When an enabled timer reaches its min duration, it adds a tracker object to the queue
      18             :  * corresponding to the duration (max - min). Each queue tracks timers of only a single duration,
      19             :  * and uses a real Timer object to schedule the expiration of the first timer in the queue. The
      20             :  * expectation is that the number of (max - min) values used to enable timers is small, so the
      21             :  * number of queues is tightly bounded. The queue-based implementation depends on that expectation
      22             :  * for efficient operation.
      23             :  */
      24             : class ScaledRangeTimerManagerImpl : public ScaledRangeTimerManager {
      25             : public:
      26             :   // Takes a Dispatcher and a map from timer type to scaled minimum value.
      27             :   ScaledRangeTimerManagerImpl(Dispatcher& dispatcher,
      28             :                               const ScaledTimerTypeMapConstSharedPtr& timer_minimums = nullptr);
      29             :   ~ScaledRangeTimerManagerImpl() override;
      30             : 
      31             :   // ScaledRangeTimerManager impl
      32             :   TimerPtr createTimer(ScaledTimerMinimum minimum, TimerCb callback) override;
      33             :   TimerPtr createTimer(ScaledTimerType timer_type, TimerCb callback) override;
      34             :   void setScaleFactor(UnitFloat scale_factor) override;
      35             : 
      36             : private:
      37             :   class RangeTimerImpl;
      38             : 
      39             :   // A queue object that maintains a list of timers with the same (max - min) values.
      40             :   struct Queue {
      41             :     struct Item {
      42             :       Item(RangeTimerImpl& timer, MonotonicTime active_time);
      43             :       // The timer owned by the caller being kept in the queue.
      44             :       RangeTimerImpl& timer_;
      45             :       // The time at which the timer became active (when its min duration expired).
      46             :       MonotonicTime active_time_;
      47             :     };
      48             : 
      49             :     // Typedef for convenience.
      50             :     using Iterator = std::list<Item>::iterator;
      51             : 
      52             :     Queue(std::chrono::milliseconds duration, ScaledRangeTimerManagerImpl& manager,
      53             :           Dispatcher& dispatcher);
      54             : 
      55             :     // The (max - min) value for all timers in range_timers_.
      56             :     const std::chrono::milliseconds duration_;
      57             : 
      58             :     // The list of active timers in this queue. This is implemented as a
      59             :     // std::list so that the iterators held in ScalingTimerHandle instances are
      60             :     // not invalidated by removal or insertion of other timers. The timers in
      61             :     // the list are in sorted order by active_time_ because they are only
      62             :     // inserted at the end of the list, and the time is monotonically increasing.
      63             :     std::list<Item> range_timers_;
      64             : 
      65             :     // A real Timer that tracks the expiration time of the first timer in the queue. This gets
      66             :     // adjusted
      67             :     //   1) at queue creation time
      68             :     //   2) on expiration
      69             :     //   3) when the scale factor changes
      70             :     const TimerPtr timer_;
      71             : 
      72             :     // A flag indicating whether the queue is currently processing timers. Used to guard against
      73             :     // queue deletion during timer processing.
      74             :     bool processing_timers_{false};
      75             :   };
      76             : 
      77             :   /**
      78             :    * An object passed back to RangeTimerImpl that can be used to remove it from its queue.
      79             :    */
      80             :   struct ScalingTimerHandle {
      81             :     ScalingTimerHandle(Queue& queue, Queue::Iterator iterator);
      82             :     Queue& queue_;
      83             :     Queue::Iterator iterator_;
      84             :   };
      85             : 
      86             :   struct Hash {
      87             :     // Magic declaration to allow heterogeneous lookup.
      88             :     using is_transparent = void; // NOLINT(readability-identifier-naming)
      89             : 
      90           0 :     size_t operator()(const std::chrono::milliseconds duration) const {
      91           0 :       return hash_(duration.count());
      92           0 :     }
      93           0 :     size_t operator()(const Queue& queue) const { return (*this)(queue.duration_); }
      94           0 :     size_t operator()(const std::unique_ptr<Queue>& queue) const { return (*this)(*queue); }
      95             :     std::hash<std::chrono::milliseconds::rep> hash_;
      96             :   };
      97             : 
      98             :   struct Eq {
      99             :     // Magic declaration to allow heterogeneous lookup.
     100             :     using is_transparent = void; // NOLINT(readability-identifier-naming)
     101             : 
     102           0 :     bool operator()(const std::unique_ptr<Queue>& lhs, std::chrono::milliseconds rhs) const {
     103           0 :       return lhs->duration_ == rhs;
     104           0 :     }
     105           0 :     bool operator()(const std::unique_ptr<Queue>& lhs, const Queue& rhs) const {
     106           0 :       return (*this)(lhs, rhs.duration_);
     107           0 :     }
     108           0 :     bool operator()(const std::unique_ptr<Queue>& lhs, const std::unique_ptr<Queue>& rhs) const {
     109           0 :       return (*this)(lhs, *rhs);
     110           0 :     }
     111             :   };
     112             : 
     113             :   static MonotonicTime computeTriggerTime(const Queue::Item& item,
     114             :                                           std::chrono::milliseconds duration,
     115             :                                           UnitFloat scale_factor);
     116             : 
     117             :   ScalingTimerHandle activateTimer(std::chrono::milliseconds duration, RangeTimerImpl& timer);
     118             : 
     119             :   void removeTimer(ScalingTimerHandle handle);
     120             : 
     121             :   void resetQueueTimer(Queue& queue, MonotonicTime now);
     122             : 
     123             :   void onQueueTimerFired(Queue& queue);
     124             : 
     125             :   Dispatcher& dispatcher_;
     126             :   const ScaledTimerTypeMapConstSharedPtr timer_minimums_;
     127             :   UnitFloat scale_factor_;
     128             :   absl::flat_hash_set<std::unique_ptr<Queue>, Hash, Eq> queues_;
     129             : };
     130             : 
     131             : } // namespace Event
     132             : } // namespace Envoy