timing.c

   1 /*
   2  * timing.c
   3  *
   4  * This module tracks any timers set up by schedule_timer(). It
   5  * keeps all the currently active timers in a list; it informs the
   6  * front end of when the next timer is due to go off if that
   7  * changes; and, very importantly, it tracks the context pointers
   8  * passed to schedule_timer(), so that if a context is freed all
   9  * the timers associated with it can be immediately annulled.
  10  *
  11  *
  12  * The problem is that computer clocks aren't perfectly accurate.
  13  * The GETTICKCOUNT function returns a 32bit number that normally
  14  * increases by about 1000 every second. On windows this uses the PC's
  15  * interrupt timer and so is only accurate to around 20ppm.  On unix it's
  16  * a value that's calculated from the current UTC time and so is in theory
  17  * accurate in the long term but may jitter and jump in the short term.
  18  *
  19  * What PuTTY needs from these timers is simply a way of delaying the
  20  * calling of a function for a little while, if it's occasionally called a
  21  * little early or late that's not a problem. So to protect against clock
  22  * jumps schedule_timer records the time that it was called in the timer
  23  * structure. With this information the run_timers function can see when
  24  * the current GETTICKCOUNT value is after the time the event should be
  25  * fired OR before the time it was set. In the latter case the clock must
  26  * have jumped, the former is (probably) just the normal passage of time.
  27  *
  28  */
  29
  30 #include <assert.h>
  31 #include <stdio.h>
  32
  33 #include "putty.h"
  34 #include "tree234.h"
  35
  36 struct timer {
  37     timer_fn_t fn;
  38     void *ctx;
  39     unsigned long now;
  40     unsigned long when_set;
  41 };
  42
  43 static tree234 *timers = NULL;
  44 static tree234 *timer_contexts = NULL;
  45 static unsigned long now = 0L;
  46
  47 static int compare_timers(void *av, void *bv)
  48 {
  49     struct timer *a = (struct timer *)av;
  50     struct timer *b = (struct timer *)bv;
  51     long at = a->now - now;
  52     long bt = b->now - now;
  53
  54     if (at < bt)
  55         return -1;
  56     else if (at > bt)
  57         return +1;
  58
  59     /*
  60      * Failing that, compare on the other two fields, just so that
  61      * we don't get unwanted equality.
  62      */
  63 #if defined(__LCC__) || defined(__clang__)
  64     /* lcc won't let us compare function pointers. Legal, but annoying. */
  65     {
  66         int c = memcmp(&a->fn, &b->fn, sizeof(a->fn));
  67         if (c)
  68             return c;
  69     }
  70 #else
  71     if (a->fn < b->fn)
  72         return -1;
  73     else if (a->fn > b->fn)
  74         return +1;
  75 #endif
  76
  77     if (a->ctx < b->ctx)
  78         return -1;
  79     else if (a->ctx > b->ctx)
  80         return +1;
  81
  82     /*
  83      * Failing _that_, the two entries genuinely are equal, and we
  84      * never have a need to store them separately in the tree.
  85      */
  86     return 0;
  87 }
  88
  89 static int compare_timer_contexts(void *av, void *bv)
  90 {
  91     char *a = (char *)av;
  92     char *b = (char *)bv;
  93     if (a < b)
  94         return -1;
  95     else if (a > b)
  96         return +1;
  97     return 0;
  98 }
  99
 100 static void init_timers(void)
 101 {
 102     if (!timers) {
 103         timers = newtree234(compare_timers);
 104         timer_contexts = newtree234(compare_timer_contexts);
 105         now = GETTICKCOUNT();
 106     }
 107 }
 108
 109 unsigned long schedule_timer(int ticks, timer_fn_t fn, void *ctx)
 110 {
 111     unsigned long when;
 112     struct timer *t, *first;
 113
 114     init_timers();
 115
 116     now = GETTICKCOUNT();
 117     when = ticks + now;
 118
 119     /*
 120      * Just in case our various defences against timing skew fail
 121      * us: if we try to schedule a timer that's already in the
 122      * past, we instead schedule it for the immediate future.
 123      */
 124     if (when - now <= 0)
 125         when = now + 1;
 126
 127     t = snew(struct timer);
 128     t->fn = fn;
 129     t->ctx = ctx;
 130     t->now = when;
 131     t->when_set = now;
 132
 133     if (t != add234(timers, t)) {
 134         sfree(t);                      /* identical timer already exists */
 135     } else {
 136         add234(timer_contexts, t->ctx);/* don't care if this fails */
 137     }
 138
 139     first = (struct timer *)index234(timers, 0);
 140     if (first == t) {
 141         /*
 142          * This timer is the very first on the list, so we must
 143          * notify the front end.
 144          */
 145         timer_change_notify(first->now);
 146     }
 147
 148     return when;
 149 }
 150
 151 unsigned long timing_last_clock(void)
 152 {
 153     /*
 154      * Return the last value we stored in 'now'. In particular,
 155      * calling this just after schedule_timer returns the value of
 156      * 'now' that was used to decide when the timer you just set would
 157      * go off.
 158      */
 159     return now;
 160 }
 161
 162 /*
 163  * Call to run any timers whose time has reached the present.
 164  * Returns the time (in ticks) expected until the next timer after
 165  * that triggers.
 166  */
 167 int run_timers(unsigned long anow, unsigned long *next)
 168 {
 169     struct timer *first;
 170
 171     init_timers();
 172
 173     now = GETTICKCOUNT();
 174
 175     while (1) {
 176         first = (struct timer *)index234(timers, 0);
 177
 178         if (!first)
 179             return FALSE;              /* no timers remaining */
 180
 181         if (find234(timer_contexts, first->ctx, NULL) == NULL) {
 182             /*
 183              * This timer belongs to a context that has been
 184              * expired. Delete it without running.
 185              */
 186             delpos234(timers, 0);
 187             sfree(first);
 188         } else if (now - (first->when_set - 10) >
 189                    first->now - (first->when_set - 10)) {
 190             /*
 191              * This timer is active and has reached its running
 192              * time. Run it.
 193              */
 194             delpos234(timers, 0);
 195             first->fn(first->ctx, first->now);
 196             sfree(first);
 197         } else {
 198             /*
 199              * This is the first still-active timer that is in the
 200              * future. Return how long it has yet to go.
 201              */
 202             *next = first->now;
 203             return TRUE;
 204         }
 205     }
 206 }
 207
 208 /*
 209  * Call to expire all timers associated with a given context.
 210  */
 211 void expire_timer_context(void *ctx)
 212 {
 213     init_timers();
 214
 215     /*
 216      * We don't bother to check the return value; if the context
 217      * already wasn't in the tree (presumably because no timers
 218      * ever actually got scheduled for it) then that's fine and we
 219      * simply don't need to do anything.
 220      */
 221     del234(timer_contexts, ctx);
 222 }