endian: add constant versions.
[ccan] / 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.