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