src/dasynq/dasynq-timerbase.h

   1 #ifndef DASYNQ_TIMERBASE_H_INCLUDED
   2 #define DASYNQ_TIMERBASE_H_INCLUDED
   3
   4 #include <utility>
   5
   6 #include "dasynq-naryheap.h"
   7
   8 namespace dasynq {
   9
  10 // time_val provides a wrapper around struct timespec, which overloads operators appropriately.
  11 class time_val
  12 {
  13     struct timespec time;
  14
  15     public:
  16     using second_t = decltype(time.tv_sec);
  17     using nsecond_t = decltype(time.tv_nsec);
  18
  19     time_val()
  20     {
  21         // uninitialised!
  22     }
  23
  24     time_val(const struct timespec &t)
  25     {
  26         time = t;
  27     }
  28
  29     time_val(second_t s, nsecond_t ns)
  30     {
  31         time.tv_sec = s;
  32         time.tv_nsec = ns;
  33     }
  34
  35     second_t seconds() const { return time.tv_sec; }
  36     nsecond_t nseconds() const { return time.tv_nsec; }
  37
  38     second_t & seconds() { return time.tv_sec; }
  39     nsecond_t & nseconds() { return time.tv_nsec; }
  40
  41     //void set_seconds(second_t s) { time.tv_sec = s; }
  42     //void set_nseconds(nsecond_t ns) { time.tv_nsec = ns; }
  43     //void dec_seconds() { time.tv_sec--; }
  44     //void inc_seconds() { time.tv_sec++; }
  45
  46     operator timespec() const
  47     {
  48        return time;
  49     }
  50 };
  51
  52 inline time_val operator-(const time_val &t1, const time_val &t2)
  53 {
  54     time_val diff;
  55     diff.seconds() = t1.seconds() - t2.seconds();
  56     if (t1.nseconds() > t2.nseconds()) {
  57         diff.nseconds() = t1.nseconds() - t2.nseconds();
  58     }
  59     else {
  60         diff.nseconds() = 1000000000 - t2.nseconds() + t1.nseconds();
  61         diff.seconds()--;
  62     }
  63     return diff;
  64 }
  65
  66 inline time_val operator+(const time_val &t1, const time_val &t2)
  67 {
  68     auto ns = t1.nseconds() + t2.nseconds();
  69     auto s = t1.seconds() + t2.seconds();
  70     static_assert(std::numeric_limits<decltype(ns)>::max() >= 2000000000, "type too small");
  71     if (ns >= 1000000000) {
  72         ns -= 1000000000;
  73         s++;
  74     }
  75     return time_val(s, ns);
  76 }
  77
  78 inline time_val &operator+=(time_val &t1, const time_val &t2)
  79 {
  80     auto nsum = t1.nseconds() + t2.nseconds();
  81     t1.seconds() = t1.seconds() + t2.seconds();
  82     if (nsum >= 1000000000) {
  83         nsum -= 1000000000;
  84         t1.seconds()++;
  85     }
  86     t1.nseconds() = nsum;
  87     return t1;
  88 }
  89
  90 inline bool operator<(const time_val &t1, const time_val &t2)
  91 {
  92     if (t1.seconds() < t2.seconds()) return true;
  93     if (t1.seconds() == t2.seconds() && t1.nseconds() < t2.nseconds()) return true;
  94     return false;
  95 }
  96
  97 inline bool operator==(const time_val &t1, const time_val &t2)
  98 {
  99     return (t1.seconds() == t2.seconds() && t1.nseconds() == t2.nseconds());
 100 }
 101
 102 inline bool operator<=(const time_val &t1, const time_val &t2)
 103 {
 104     if (t1.seconds() < t2.seconds()) return true;
 105     if (t1.seconds() == t2.seconds() && t1.nseconds() <= t2.nseconds()) return true;
 106     return false;
 107 }
 108
 109 inline bool operator!=(const time_val &t1, const time_val &t2) { return !(t1 == t2); }
 110 inline bool operator>(const time_val &t1, const time_val &t2) { return t2 < t1; }
 111 inline bool operator>=(const time_val &t1, const time_val &t2) { return t2 <= t1; }
 112
 113 // Data corresponding to a single timer
 114 class timer_data
 115 {
 116     public:
 117     time_val interval_time; // interval (if 0, one-off timer)
 118     int expiry_count;  // number of times expired
 119     bool enabled;   // whether timer reports events
 120     void *userdata;
 121
 122     timer_data(void *udata = nullptr) : interval_time(0,0), expiry_count(0), enabled(true), userdata(udata)
 123     {
 124         // constructor
 125     }
 126 };
 127
 128 class compare_timespec
 129 {
 130     public:
 131     bool operator()(const struct timespec &a, const struct timespec &b)
 132     {
 133         if (a.tv_sec < b.tv_sec) {
 134             return true;
 135         }
 136
 137         if (a.tv_sec == b.tv_sec) {
 138             return a.tv_nsec < b.tv_nsec;
 139         }
 140
 141         return false;
 142     }
 143 };
 144
 145 using timer_queue_t = NaryHeap<timer_data, struct timespec, compare_timespec>;
 146 using timer_handle_t = timer_queue_t::handle_t;
 147
 148 static inline void init_timer_handle(timer_handle_t &hnd) noexcept
 149 {
 150     timer_queue_t::init_handle(hnd);
 151 }
 152
 153 static inline int divide_timespec(const struct timespec &num, const struct timespec &den, struct timespec &rem)
 154 {
 155     if (num.tv_sec < den.tv_sec) {
 156         rem = num;
 157         return 0;
 158     }
 159
 160     if (num.tv_sec == den.tv_sec) {
 161         if (num.tv_nsec < den.tv_nsec) {
 162             rem = num;
 163             return 0;
 164         }
 165         if (num.tv_sec == 0) {
 166             rem.tv_sec = 0;
 167             rem.tv_nsec = num.tv_nsec % den.tv_nsec;
 168             return num.tv_nsec / den.tv_nsec;
 169         }
 170         // num.tv_sec == den.tv_sec and both are >= 1.
 171         // The result can only be 1:
 172         rem.tv_sec = 0;
 173         rem.tv_nsec = num.tv_nsec - den.tv_nsec;
 174         return 1;
 175     }
 176
 177     // At this point, num.tv_sec >= 1.
 178
 179     auto &r_sec = rem.tv_sec;
 180     auto &r_nsec = rem.tv_nsec;
 181     r_sec = num.tv_sec;
 182     r_nsec = num.tv_nsec;
 183     auto d_sec = den.tv_sec;
 184     auto d_nsec = den.tv_nsec;
 185
 186     r_sec -= d_sec;
 187     if (r_nsec >= d_nsec) {
 188         r_nsec -= d_nsec;
 189     }
 190     else {
 191         r_nsec += (1000000000ULL - d_nsec);
 192         r_sec -= 1;
 193     }
 194
 195     // Check now for common case: one timer expiry with no overrun
 196     if (r_sec < d_sec || (r_sec == d_sec && r_nsec < d_nsec)) {
 197         return 1;
 198     }
 199
 200     int nval = 1;
 201     int rval = 1; // we have subtracted 1*D already
 202
 203     // shift denominator until it is greater than/equal to numerator:
 204     while (d_sec < r_sec) {
 205         d_sec *= 2;
 206         d_nsec *= 2;
 207         if (d_nsec >= 1000000000) {
 208             d_nsec -= 1000000000;
 209             d_sec++;
 210         }
 211         nval *= 2;
 212     }
 213
 214     while (nval > 0) {
 215         if (d_sec < r_sec || (d_sec == r_sec && d_nsec <= r_nsec)) {
 216             // subtract:
 217             r_sec -= d_sec;
 218             if (d_nsec > r_nsec) {
 219                 r_nsec += 1000000000;
 220                 r_sec--;
 221             }
 222             r_nsec -= d_nsec;
 223
 224             rval += nval;
 225         }
 226
 227         bool low = d_sec & 1;
 228         d_nsec /= 2;
 229         d_nsec += low ? 500000000ULL : 0;
 230         d_sec /= 2;
 231         nval /= 2;
 232     }
 233
 234     return rval;
 235 }
 236
 237 template <typename Base> class timer_base : public Base
 238 {
 239     protected:
 240
 241     void process_timer_queue(timer_queue_t &queue, const struct timespec &curtime)
 242     {
 243         // Peek timer queue; calculate difference between current time and timeout
 244         const struct timespec * timeout = &queue.get_root_priority();
 245         while (timeout->tv_sec < curtime.tv_sec || (timeout->tv_sec == curtime.tv_sec &&
 246                 timeout->tv_nsec <= curtime.tv_nsec)) {
 247             auto & thandle = queue.get_root();
 248             timer_data &data = queue.node_data(thandle);
 249             time_val &interval = data.interval_time;
 250             data.expiry_count++;
 251             queue.pull_root();
 252             if (interval.seconds() == 0 && interval.nseconds() == 0) {
 253                 // Non periodic timer
 254                 if (data.enabled) {
 255                     data.enabled = false;
 256                     int expiry_count = data.expiry_count;
 257                     data.expiry_count = 0;
 258                     Base::receiveTimerExpiry(thandle, data.userdata, expiry_count);
 259                 }
 260                 if (queue.empty()) {
 261                     break;
 262                 }
 263             }
 264             else {
 265                 // First calculate the overrun in time:
 266                 time_val overrun = time_val(curtime) - time_val(*timeout);
 267
 268                 // Now we have to divide the time overrun by the period to find the
 269                 // interval overrun. This requires a division of a value not representable
 270                 // as a long...
 271                 struct timespec rem;
 272                 data.expiry_count += divide_timespec(overrun, interval, rem);
 273
 274                 // new time is current time + interval - remainder:
 275                 time_val newtime = curtime + interval - rem;
 276
 277                 queue.insert(thandle, newtime);
 278                 if (data.enabled) {
 279                     data.enabled = false;
 280                     int expiry_count = data.expiry_count;
 281                     data.expiry_count = 0;
 282                     Base::receiveTimerExpiry(thandle, data.userdata, expiry_count);
 283                 }
 284             }
 285
 286             // repeat until all expired timeouts processed
 287             timeout = &queue.get_root_priority();
 288         }
 289     }
 290 };
 291
 292 }
 293
 294 #endif /* DASYNQ_TIMERBASE_H_INCLUDED */