How does linux handle overflow in jiffies?

Question

Suppose we have a following code:

if (timeout > jiffies)
{
    /* we did not time out, good ... */
}
else
{
    /* we timed out, error ...*
}

This code works fine when jiffies value do not overflow. However, when jiffies overflow and wrap around to zero, this code doesn't work properly.

Linux apparently provides macros for dealing with this overflow problem

#define time_before(unknown, known) ((long)(unkown) - (long)(known) < 0)

and code above is supposed to be safe against overflow when replaced with this macro:

// SAFE AGAINST OVERFLOW
if (time_before(jiffies, timeout)
{
    /* we did not time out, good ... */
}
else
{
    /* we timed out, error ...*
}    

But, what is the rationale behind time_before (and other time_ macros?

time_before(jiffies, timeout) will be expanded to

((long)(jiffies) - (long)(timeout) < 0)

How does this code prevent overflow problems?

Answer 1

Let's actually give it a try:

#define time_before(unknown, known) ((long)(unkown) - (long)(known) < 0)

I'll simplify things down a lot by saying that a long is only two bytes, so in hex it can have a value in the range [0, 0xFFFF].

Now, it's signed, so the range [0, 0xFFFF] can be broken into two separate ranges [0, 0x7FFF], [0x8000, 0xFFFF]. Those correspond to the values [0, 32767], [ -32768, -1]. Here's a diagram:

[0x0      -              -                  -               0xFFFF]
[0x0                       0x7FFF][0x8000                   0xFFFF]
[0                         32,767][-32,768                      -1]

Say timeout is 32,000. We want to check if we're inside our timeout, but in truth we overflowed, so jiffies is -31,000. So if we naively tried to evaluate jiffies < timeout we'd get True. But, plugging in the values:

   time_before(jiffies, offset)
== ((long)(jiffies) - (long)(offset) < 0)
== (-31000 - 32000 < 0)             // WTF is this. Clearly NOT -63000
== (-31000 - 1768 - 1 - 30231 < 0)  // simply expanded 32000
== (-32768 - 1 - 30232 < 0)         // this -1 causes an underflow
== (32767 - 30232 < 0)
== (2535 < 0)
== False

jiffies are 4 bytes, not 2, but the same principle applies. Does that help at all?