git.ozlabs.org Git - ccan/blob - ccan/timer/design.txt

   1 Cascading timer design.
   2
   3 Inspired by the Linux kernel approach, documented roughly at:
   4         https://lwn.net/Articles/152436/
   5
   6 For easy description, we use whole seconds and powers of 10: in the
   7 implementation, we use powers of 2 (eg. 256 entries) and smaller
   8 granularities.
   9
  10 We start with a simple data structure:
  11
  12 struct timer_level {
  13         struct timer_level *next;
  14
  15         /* Ten buckets:         [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] */
  16         struct list_head bucket[10];
  17 };
  18
  19 struct timers {
  20         /* We can never have a timer before this, aka "now". */
  21         time_t offset;
  22
  23         struct timer_level *level;
  24
  25         /* Anything too far in the future. */
  26         struct list_head far;
  27 }
  28
  29 The first level of timers holds anything which will happen in the next
  30 10 seconds.  The next level holds things which will happen in the next
  31 100 seconds.  And so on.
  32
  33 When we want to add a new timer into the structure, we need to figure
  34 out first what level it goes into, and second, which bucket.  Say our
  35 offset is 500,000,001 (about Tue Nov 5, 1985 in Unix time).  And our
  36 timer is set to go off in 5 seconds, ie. 500,000,006.
  37
  38 The level is easy: the difference between the timer and the offset is
  39 5, and that's less than 10, so it's in the first level.  The position,
  40 however, depends on the absolute time, in this case the last digit 6,
  41 so it's in bucket 6.
  42
  43 Adding a timer at 500,000,123?  The difference is > 100 and < 1000, so
  44 it's in the third level.  The bucket is 1.  If there's no third level,
  45 we just add it to the 'far' list for stuff which is in the far future.
  46
  47 Deleting a timer is as simple as removing it; there is no external
  48 bookkeeping in this scheme.  This matters, since timers used for
  49 timeouts are almost always deleted before they expire.
  50
  51 Now, when a second passes, we need to know if there are any timers
  52 which are due.  We increment the offset to 500,000,002, and look in
  53 the first level, bucket 2 for any timers, so lookup is simple.
  54
  55 We do this eight more times, and we increment the offset to
  56 500,000,010.  We've swept around back to bucket 0, though it may not
  57 be empty if we added more timers as we were going.
  58
  59 But we need to look into the next level since a timer at 500,000,010
  60 added when the offset was 500,000,000 would have gone up there.  We
  61 empty bucket 1 (due to the '1' in 500,000,010) into these buckets,
  62 which will contain timers between 500,000,010 and 500,000,019, which
  63 all now are less than 10 seconds away, so belong in the bottom level.
  64
  65 Similarly, at 500,000,020 we will empty bucket 1 of the second level
  66 into the first level.  And at 500,000,100 we will empty bucket 1 of
  67 the third level into the second level then bucket 0 of the second
  68 level into the first level.  We do it in this order, since emptying
  69 bucket 1 on the third level (500,000,100 - 500,000,199) may put more
  70 entries (500,000,100 - 500,000,109) into bucket 0 on the second level.
  71
  72 When we get to 500,001,000 we should empty the fourth level.  If there
  73 is no fourth level, that's when we sort through the 'far' list and
  74 empty any which are less than 500,002,000.  If there are many entries
  75 in the far list, we should add more levels to reduce the number, or at
  76 least the frequency we have to check it.