src/dasynq/dasynq-timerbase.h

   1 #ifndef DASYNQ_TIMERBASE_H_INCLUDED
   2 #define DASYNQ_TIMERBASE_H_INCLUDED
   3
   4 #include <utility>
   5 #include <mutex>
   6
   7 #include "dasynq-daryheap.h"
   8
   9 namespace dasynq {
  10
  11 // time_val provides a wrapper around struct timespec, which overloads operators appropriately.
  12 class time_val
  13 {
  14     struct timespec time;
  15
  16     public:
  17     using second_t = decltype(time.tv_sec);
  18     using nsecond_t = decltype(time.tv_nsec);
  19
  20     time_val() noexcept
  21     {
  22         // uninitialised!
  23     }
  24
  25     time_val(const struct timespec &t) noexcept
  26     {
  27         time = t;
  28     }
  29
  30     time_val(second_t s, nsecond_t ns) noexcept
  31     {
  32         time.tv_sec = s;
  33         time.tv_nsec = ns;
  34     }
  35
  36     second_t seconds() const noexcept{ return time.tv_sec; }
  37     nsecond_t nseconds() const noexcept { return time.tv_nsec; }
  38
  39     second_t & seconds() noexcept { return time.tv_sec; }
  40     nsecond_t & nseconds() noexcept { return time.tv_nsec; }
  41
  42     timespec & get_timespec() noexcept
  43     {
  44         return time;
  45     }
  46
  47     const timespec & get_timespec() const noexcept
  48     {
  49         return time;
  50     }
  51
  52     operator timespec() const noexcept
  53     {
  54        return time;
  55     }
  56 };
  57
  58 inline time_val operator-(const time_val &t1, const time_val &t2) noexcept
  59 {
  60     time_val diff;
  61     diff.seconds() = t1.seconds() - t2.seconds();
  62     if (t1.nseconds() >= t2.nseconds()) {
  63         diff.nseconds() = t1.nseconds() - t2.nseconds();
  64     }
  65     else {
  66         diff.nseconds() = 1000000000 - t2.nseconds() + t1.nseconds();
  67         diff.seconds()--;
  68     }
  69     return diff;
  70 }
  71
  72 inline time_val operator+(const time_val &t1, const time_val &t2) noexcept
  73 {
  74     auto ns = t1.nseconds() + t2.nseconds();
  75     auto s = t1.seconds() + t2.seconds();
  76     static_assert(std::numeric_limits<decltype(ns)>::max() >= 2000000000, "type too small");
  77     if (ns >= 1000000000) {
  78         ns -= 1000000000;
  79         s++;
  80     }
  81     return time_val(s, ns);
  82 }
  83
  84 inline time_val &operator+=(time_val &t1, const time_val &t2) noexcept
  85 {
  86     auto nsum = t1.nseconds() + t2.nseconds();
  87     t1.seconds() = t1.seconds() + t2.seconds();
  88     if (nsum >= 1000000000) {
  89         nsum -= 1000000000;
  90         t1.seconds()++;
  91     }
  92     t1.nseconds() = nsum;
  93     return t1;
  94 }
  95
  96 inline time_val &operator-=(time_val &t1, const time_val &t2) noexcept
  97 {
  98     time_val diff;
  99     t1.seconds() = t1.seconds() - t2.seconds();
 100     if (t1.nseconds() >= t2.nseconds()) {
 101         t1.nseconds() = t1.nseconds() - t2.nseconds();
 102     }
 103     else {
 104         t1.nseconds() = 1000000000 - t2.nseconds() + t1.nseconds();
 105         t1.seconds()--;
 106     }
 107     return t1;
 108 }
 109
 110 inline bool operator<(const time_val &t1, const time_val &t2) noexcept
 111 {
 112     if (t1.seconds() < t2.seconds()) return true;
 113     if (t1.seconds() == t2.seconds() && t1.nseconds() < t2.nseconds()) return true;
 114     return false;
 115 }
 116
 117 inline bool operator==(const time_val &t1, const time_val &t2) noexcept
 118 {
 119     return (t1.seconds() == t2.seconds() && t1.nseconds() == t2.nseconds());
 120 }
 121
 122 inline bool operator<=(const time_val &t1, const time_val &t2) noexcept
 123 {
 124     if (t1.seconds() < t2.seconds()) return true;
 125     if (t1.seconds() == t2.seconds() && t1.nseconds() <= t2.nseconds()) return true;
 126     return false;
 127 }
 128
 129 inline bool operator!=(const time_val &t1, const time_val &t2) noexcept { return !(t1 == t2); }
 130 inline bool operator>(const time_val &t1, const time_val &t2) noexcept { return t2 < t1; }
 131 inline bool operator>=(const time_val &t1, const time_val &t2) noexcept { return t2 <= t1; }
 132
 133 static inline int divide_timespec(const struct timespec &num, const struct timespec &den, struct timespec &rem) noexcept;
 134
 135 inline int operator/(const time_val &t1, const time_val &t2) noexcept
 136 {
 137     struct timespec remainder;
 138     return divide_timespec(t1.get_timespec(), t2.get_timespec(), remainder);
 139 }
 140
 141 inline time_val & operator<<=(time_val &t, int n) noexcept
 142 {
 143     for (int i = 0; i < n; i++) {
 144         t.seconds() *= 2;
 145         t.nseconds() *= 2;
 146         if (t.nseconds() >= 1000000000) {
 147             t.nseconds() -= 1000000000;
 148             t.seconds()++;
 149         }
 150     }
 151     return t;
 152 }
 153
 154 inline time_val operator<<(time_val &t, int n) noexcept
 155 {
 156     auto r = t;
 157     r <<= n;
 158     return r;
 159 }
 160
 161 inline time_val & operator>>=(time_val &t, int n) noexcept
 162 {
 163     for (int i = 0; i < n; i++) {
 164         bool low = t.seconds() & 1;
 165         t.nseconds() /= 2;
 166         t.nseconds() += low ? 500000000ULL : 0;
 167         t.seconds() /= 2;
 168     }
 169     return t;
 170 }
 171
 172 inline time_val operator>>(time_val &t, int n) noexcept
 173 {
 174     auto r = t;
 175     r >>= n;
 176     return r;
 177 }
 178
 179 // Data corresponding to a single timer
 180 class timer_data
 181 {
 182     public:
 183     time_val interval_time; // interval (if 0, one-off timer)
 184     int expiry_count;  // number of times expired
 185     bool enabled;   // whether timer reports events
 186     void *userdata;
 187
 188     timer_data(void *udata = nullptr) noexcept : interval_time(0,0), expiry_count(0), enabled(true), userdata(udata)
 189     {
 190         // constructor
 191     }
 192 };
 193
 194 class compare_timespec
 195 {
 196     public:
 197     bool operator()(const struct timespec &a, const struct timespec &b) noexcept
 198     {
 199         if (a.tv_sec < b.tv_sec) {
 200             return true;
 201         }
 202
 203         if (a.tv_sec == b.tv_sec) {
 204             return a.tv_nsec < b.tv_nsec;
 205         }
 206
 207         return false;
 208     }
 209 };
 210
 211 using timer_queue_t = dary_heap<timer_data, time_val, compare_timespec>;
 212 using timer_handle_t = timer_queue_t::handle_t;
 213
 214 static inline void init_timer_handle(timer_handle_t &hnd) noexcept
 215 {
 216     timer_queue_t::init_handle(hnd);
 217 }
 218
 219 static inline int divide_timespec(const struct timespec &num, const struct timespec &den, struct timespec &rem) noexcept
 220 {
 221     if (num.tv_sec < den.tv_sec) {
 222         rem = num;
 223         return 0;
 224     }
 225
 226     if (num.tv_sec == den.tv_sec) {
 227         if (num.tv_nsec < den.tv_nsec) {
 228             rem = num;
 229             return 0;
 230         }
 231         if (num.tv_sec == 0) {
 232             rem.tv_sec = 0;
 233             rem.tv_nsec = num.tv_nsec % den.tv_nsec;
 234             return num.tv_nsec / den.tv_nsec;
 235         }
 236         // num.tv_sec == den.tv_sec and both are >= 1.
 237         // The result can only be 1:
 238         rem.tv_sec = 0;
 239         rem.tv_nsec = num.tv_nsec - den.tv_nsec;
 240         return 1;
 241     }
 242
 243     // At this point, num.tv_sec >= 1.
 244
 245     time_val n = { num.tv_sec, num.tv_nsec };
 246     time_val d = { den.tv_sec, den.tv_nsec };
 247     time_val r = n;
 248
 249     // starting with numerator, subtract 1*denominator
 250     r -= d;
 251
 252     // Check now for common case: one timer expiry with no overrun
 253     if (r < d) {
 254         rem = r;
 255         return 1;
 256     }
 257
 258     int nval = 1;
 259     int rval = 1; // we have subtracted 1*D already
 260
 261     // shift denominator until it is greater than / roughly equal to numerator:
 262     while (d.seconds() < r.seconds()) {
 263         d <<= 1;
 264         nval *= 2;
 265     }
 266
 267     while (nval > 0) {
 268         if (d <= r) {
 269             r -= d;
 270             rval += nval;
 271         }
 272
 273         d >>= 1;
 274         nval /= 2;
 275     }
 276
 277     rem = r;
 278     return rval;
 279 }
 280
 281 template <typename Base> class timer_base : public Base
 282 {
 283     private:
 284     timer_queue_t timer_queue;
 285
 286 #if defined(CLOCK_MONOTONIC)
 287     timer_queue_t mono_timer_queue;
 288
 289     protected:
 290     inline timer_queue_t &queue_for_clock(clock_type clock)
 291     {
 292         if (clock == clock_type::MONOTONIC) {
 293             return mono_timer_queue;
 294         }
 295         else {
 296             return timer_queue;
 297         }
 298     }
 299
 300     inline bool timer_queues_empty()
 301     {
 302         return timer_queue.empty() && mono_timer_queue.empty();
 303     }
 304 #else
 305     protected:
 306     inline timer_queue_t &queue_for_clock(clock_type clock)
 307     {
 308         return timer_queue;
 309     }
 310
 311     inline bool timer_queues_empty()
 312     {
 313         return timer_queue.empty();
 314     }
 315 #endif
 316
 317     // For the specified timer queue, issue expirations for all timers set to expire on or before the given
 318     // time (curtime). The timer queue must not be empty.
 319     void process_timer_queue(timer_queue_t &queue, const struct timespec &curtime) noexcept
 320     {
 321         // Peek timer queue; calculate difference between current time and timeout
 322         const time_val * timeout = &queue.get_root_priority();
 323         time_val curtime_tv = curtime;
 324         while (*timeout <= curtime_tv) {
 325             auto & thandle = queue.get_root();
 326             timer_data &data = queue.node_data(thandle);
 327             time_val &interval = data.interval_time;
 328             data.expiry_count++;
 329             queue.pull_root();
 330             if (interval.seconds() == 0 && interval.nseconds() == 0) {
 331                 // Non periodic timer
 332                 if (data.enabled) {
 333                     data.enabled = false;
 334                     int expiry_count = data.expiry_count;
 335                     data.expiry_count = 0;
 336                     Base::receive_timer_expiry(thandle, data.userdata, expiry_count);
 337                 }
 338                 if (queue.empty()) {
 339                     break;
 340                 }
 341             }
 342             else {
 343                 // First calculate the overrun in time:
 344                 time_val overrun = time_val(curtime) - time_val(*timeout);
 345
 346                 // Now we have to divide the time overrun by the period to find the
 347                 // interval overrun. This requires a division of a value not representable
 348                 // as a long...
 349                 struct timespec rem;
 350                 data.expiry_count += divide_timespec(overrun, interval, rem);
 351
 352                 // new time is current time + interval - remainder:
 353                 time_val newtime = curtime + interval - rem;
 354
 355                 queue.insert(thandle, newtime);
 356                 if (data.enabled) {
 357                     data.enabled = false;
 358                     int expiry_count = data.expiry_count;
 359                     data.expiry_count = 0;
 360                     Base::receive_timer_expiry(thandle, data.userdata, expiry_count);
 361                 }
 362             }
 363
 364             // repeat until all expired timeouts processed
 365             timeout = &queue.get_root_priority();
 366         }
 367     }
 368
 369     public:
 370
 371     void get_time(time_val &tv, clock_type clock, bool force_update) noexcept
 372     {
 373         get_time(tv.get_timespec(), clock, force_update);
 374     }
 375
 376 #ifdef CLOCK_MONOTONIC
 377     void get_time(timespec &ts, clock_type clock, bool force_update) noexcept
 378     {
 379         clockid_t posix_clock_id = (clock == clock_type::MONOTONIC) ? CLOCK_MONOTONIC : CLOCK_REALTIME;
 380         clock_gettime(posix_clock_id, &ts);
 381     }
 382 #else
 383     // If CLOCK_MONOTONIC is not defined, assume we only have gettimeofday():
 384     void get_time(timespec &ts, clock_type clock, bool force_update) noexcept
 385     {
 386         struct timeval curtime_tv;
 387         gettimeofday(&curtime_tv, nullptr);
 388         ts.tv_sec = curtime_tv.tv_sec;
 389         ts.tv_nsec = curtime_tv.tv_usec * 1000;
 390     }
 391 #endif
 392
 393     void add_timer_nolock(timer_handle_t &h, void *userdata, clock_type clock = clock_type::MONOTONIC)
 394     {
 395         this->queue_for_clock(clock).allocate(h, userdata);
 396     }
 397
 398     void remove_timer(timer_handle_t &timer_id, clock_type clock = clock_type::MONOTONIC) noexcept
 399     {
 400         std::lock_guard<decltype(Base::lock)> guard(Base::lock);
 401         remove_timer_nolock(timer_id, clock);
 402     }
 403
 404     void remove_timer_nolock(timer_handle_t &timer_id, clock_type clock = clock_type::MONOTONIC) noexcept
 405     {
 406         auto &timer_queue = this->queue_for_clock(clock);
 407         if (timer_queue.is_queued(timer_id)) {
 408             timer_queue.remove(timer_id);
 409         }
 410         timer_queue.deallocate(timer_id);
 411     }
 412
 413     // Enables or disabling report of timeouts (does not stop timer)
 414     void enable_timer(timer_handle_t &timer_id, bool enable, clock_type clock = clock_type::MONOTONIC) noexcept
 415     {
 416         std::lock_guard<decltype(Base::lock)> guard(Base::lock);
 417         enable_timer_nolock(timer_id, enable, clock);
 418     }
 419
 420     void enable_timer_nolock(timer_handle_t &timer_id, bool enable, clock_type clock = clock_type::MONOTONIC) noexcept
 421     {
 422         auto &timer_queue = this->queue_for_clock(clock);
 423         auto &node_data = timer_queue.node_data(timer_id);
 424         auto expiry_count = node_data.expiry_count;
 425         if (expiry_count != 0 && enable) {
 426             node_data.expiry_count = 0;
 427             Base::receive_timer_expiry(timer_id, node_data.userdata, expiry_count);
 428         }
 429         else {
 430             timer_queue.node_data(timer_id).enabled = enable;
 431         }
 432     }
 433 };
 434
 435 }
 436
 437 #endif /* DASYNQ_TIMERBASE_H_INCLUDED */