c - linux 如何处理 jiffies 中的溢出？

Question

假设我们有如下代码:

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

当 jiffies 值不溢出时，这段代码工作正常。但是，当 jiffies 溢出并回绕到零时，此代码无法正常工作。

Linux 显然提供了处理这个溢出问题的宏

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

当用这个宏替换时，上面的代码应该是安全的，不会溢出:

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

但是，time_before(和其他 time_ 宏)背后的基本原理是什么？

time_before(jiffies, timeout) 将扩展为

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

这段代码如何防止溢出问题？

Answer 1

让我们实际尝试一下:

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

我会通过说 long 来简化事情只有两个字节，所以在十六进制中它的值可以在 [0, 0xFFFF] 范围内.

现在，它是有符号的，所以范围 [0, 0xFFFF] 可以分成两个独立的范围 [0, 0x7FFF]，[0x8000, 0xFFFF]。这些对应于值 [0, 32767], [-32768, -1]。这是一个图表:

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

说 timeout是 32,000。我们想检查我们是否在超时内，但实际上我们溢出了，所以 jiffies是-31,000。因此，如果我们天真地尝试评估 jiffies < timeout我们会得到 True .但是，插入值:

   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是 4 个字节，而不是 2 个，但同样的原则适用。这有什么帮助吗？