this doesn't work:

• the base.offset is relative to clock.list.offset and all preceding timers in the list
• as is, this is racey, e.g., this fails horribly if the timer passes after the ztimer_is_set()

* the base.offset is relative to clock.list.offset and all preceding timers in the list

? Why ?

• the list is storing 32bit relative values in order to not use absolute target times
• there needs to be some absolute reference value, so list.base.offset is used
• the offsets are relative to the last entry, so updating the head offset doesn't require updating all timer offsets, just the one that's added and possibly the following.

Hm, a unittests (using ztimer_mock) would be preferred...

Please uncrustify.

My understanding is that this O(n) could be changed to O(1) if ztimer internally changed to storing absolute timestamps rather than differences (which it could without externally visible changes, AFAIU -- the offset field would become a now value whose epoch is defined by being at least the clock's last checked value), and the requirement is added that this is only run on timers that have been set at any point in time (thus utilizing the guarantees that are already there for ztimer_is_set).

Is that right? (I consider this addition useful, but much more so if it's O(1) -- so no reason to request O(1) immediately, but pointing out that after this the internal change might be useful.)

Maybe... to me the arithmetic with relative values seemed much clearer.

Currently, when updating the list base value, ztimer assumes that now() is not more than 2**32 ticks in front of the list base offset.
So after setting the list base offset to now, there's a difference of (now - old list base offset). now the list can be iterated. if the cumulated offset of any timer is smaller than the difference, the timer has expired.

With absolute values, we'd have the same difference between now and old list base. Now we can assume that the absolute value of each list entry should be within 2**32 ticks after the old list base. So in order to have the relative offset for a given entry (to gauge whether the timer has expired, and to where we'd sort in a new entry), we'd have to calculate the unsigned difference to the old list base offset, and if it is smaller than (now vs new difference), the timer has expired. this is not more difficult and would indeed enable O(1) ztimer_remaining().

I somehow assumed that the total sum of all relative offsets in the timer list could exceed 2**32, but as every ztimer_set() updates the head offset, that's not the case. So there's no need for the relative offsets.

I hope this will not lead to the backend clock stuff to get less reliable by setting the actual absolute target time (vs. relative as it does now), as that's something that xtimer didn't get right and it sometimes caused underflows.

It may be easier to think of the re-encoding as every timer's timestamp being some positive (0 <= d < 2^32) ticks ahead of just the timer before it -- but as long as we don't allow timers to be set 2^32 ticks in the future, that's always equivalent to being ahead of the old list base. (And for overly long timers we don't have the API to add them, and they would then also break O(1) ztimer_util before it even worked)

That is true only because we do update the head offset on each ztimer_set, but that's part of staying sane anyway, I presume. Rather than setting the already-expired-but-not-yet-triggered all to a delta of 0, they would be set to the new list base, and traversal can stop when any timer's difference to the old base is greater than the difference between the bases.

I agree that if we consider this, it will have to be done carefully -- but I think that switching from encoding deltas (relative to the old list base, as they are always encoded) and encoding old list base plus delta is more or less merely a matter of encoding positive numbers in a different way.

thanks for these carifications

That's not a requirement of the code (it works fine with an uninitialized timer), but a) we don't need to allow that (especially because uninitialized means it could take the slow path), and b) it helps keep the return value definition concise (which'd otherwise need to say "or has already triggered or was never set")

Would this be easier if _ztimer_update_head_offset would be called? Unless we're just in an interrupt-free state with pending timers, that'd just update the head pointer and first delta -- and then (in either case) it is known that the clock base is "now", and summation would be just over what's left in the timer queue.

[edit: clarified that the "and then" is true no matter whether we're in the simple case or not]

It might, I'd prefer though if this wouldn't change the clock's state.

i agree with kasper030 and like to avoid changing the list (have this a reader not a writer)

OK.

Might still have some potential for simplification, but that's on other lines.

thanks for spotting the error that was caused by not doing the head update

Both sum and now are absolute points in time whose sequence is unknown, I don't think it's meaningful to compare them.

Say the timer was set at 2**32-100 for 95 ticks (to trigger at 2**32-5), but we've been spending the time from 2**32-10 to 2**32+10 in ISRs (which is a reasonable time to spend). Still in the ISR, sum is 2**32-5, now is 10, and we return 2**32-15 rather than 0.

I think what would be correct to do would be to start sum at 0 (which is guaranteed not to wrap by construction of the timer chain, because nothing goes in more than 2**32 in the future), then calculate elapsed = now() - clock->list.offset (which is guaranteed to not wrap by the requirement that ztimer ISRs need a chance to fire at least twice a cycle), and then we can return (sum >= elapsed) ? sum - elapsed : 0;.