Handling timers during tick wrap

Developers
1

My trip through the Klipper MCU code continues.

Now, I am trying to understand how Klipper handles ordering of the timers list, especially when wake times wrap around.

From what I can understand, Klipper maintain a singly-linked list of timers where each successive timer has a higher wake time than the previous one. It uses the wake times to decide where to insert the new timer (edited for brevity):

static void __always_inline
insert_timer(struct timer *pos, struct timer *t, uint32_t waketime)
{
    struct timer *prev;
    for (;;) {
        prev = pos;
        pos = pos->next;
        if (timer_is_before(waketime, pos->waketime))
            break;
    }
    t->next = pos;
    prev->next = t;
}

Now, suppose that the current clock tick value is close to (1 << 32) - 1. So, it’s possible that waketime (the new time tha a timer needs to be woken at) has wrapped around. So, waketime will be before pos->waketime.

In this case, the new timer will be inserted before pos. However, it is supposed to trigger after pos.

The sched_timer_dispatch() function executes a single timer at a time (the one at the head of the list). So, on the next call, it will execute t (the newly inserted timer) instead of pos.

So, how does Klpper ensure that timers are order properly when the clock and wake times are around the wrap point?

2

Timers are always added in the future, if not then Timer Too Close happens.
Also, there is a timer_is_before().
Rescheduling is a little more tricky, it happens inside timer_dispatch_many.
Generally speaking, if the timer is rescheduled as the next one, it will be executed as the next one.
If timers a lagging behind, they will be executed “faster”.
If they fall too far behind - “Rescheduled timer in the past” happens.

3

I understand that they are always inserted in the future but the value of the future is not monotonically increasing. What happens when the waketime wraps?

4

I understand that they are always inserted in the future but the value of the future is not monotonically increasing. What happens when the waketime wraps?

timer_is_before() handles that, as long as the difference is less than (1<<31), we can easily compare timers.

So, for us, time is always in the future.
If it is in the too far future > (1<<31), it is a wrap, and something will brake.

(and we never schedule or reschedule in such far future).

5

I think that you are misunderstanding me:

Suppose that the current tick value is (1 << 32) - 20. There is a timer that is scheduled for (1 << 32) - 10 (timer A). A timer (timer B) is executed, which reschedules itself to wake up at current_tick + 50. So, the new wake time in absolute ticks is 30.

When sched_add_timer() is called to add timer B, it compares against timer A and finds that timer_is_before(B, A) is true. So, it inserts B before A.

As a result, A executes much, much later that it should because the ticks have to wrap all the way around to (1 << 32) - 10.

6

The new B timer value is 30.
The A timer value is 4294967286.

// Return true if time1 is before time2.  Always use this function to
// compare times as regular C comparisons can fail if the counter
// rolls over.
uint8_t
timer_is_before(uint32_t time1, uint32_t time2)
{
    return (int32_t)(time1 - time2) < 0;
}

timer_is_before(B, A)

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main() {
    uint32_t A = UINT_MAX - 10;
    uint32_t B = 30;
    printf("%i\n", (int32_t)(B-A));
}

Output:

41

Which is not less than 0, so false, so B is in the future.

1 Like
7

Well, this is embarrassing!!

Signed/unsigned math gets me again. Thanks for setting me straight. I’ve been struggling to understand how Klipper is not crashing and burning :smiley:

1 Like
8

Using your example code:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main() {
    uint32_t A = 2221580162;
    uint32_t B = 76474112;
    printf("%i\n", (int32_t)(B - A));
}

Output:

-2145106050

In this example, A is not very close to UINT_MAX but the comparison should still hold, should it?

9

Well, everything is correct here, B is before A.
As I said, as long as the difference is less than (1<<31) there is no wrap.
If you schedule the timer in the future in such way, that it is more than (1<<31) (what you did here), it is happen to be in the past.