linux jiffies 回绕问题

在科学应用中，jiffies通常表示各种时间间隔。在linux中jiffies定义如下：
extern unsigned long volatile jiffies;
jiffies变量总是无符号长整数。因此，在32位体系结构上是32位，在64位体系结构上是64位。对于32位无符号长整数，取值范围为0~0xffffffff(2^32-1=4294967295),如果jiffies到达最大值后还要继续增加的话，它的值会回绕到0.
1. 一个回绕的例子：
jiffies_error.c

#include <stdio.h>
#include <stdlib.h>
unsigned long jiffies = 4294967294;

unsigned long timeout;

int main(int argc, char* argv[])
{

    timeout = jiffies + 1;
    if(timeout > jiffies) {
        printf("no timeout\n");
    }else {
        printf("timeout\n");
    }


    jiffies++;
    jiffies++;

    if(timeout > jiffies) {
        printf("wrap around: no timeout\n");
    }else {
        printf("wrap around: no timeout\n");
    }


    return 0;
}

编译运行：

[e-mail]:~/test/jiffies>gcc -g  jiffies_error.c -o jiffies_error
[e-mail]:~/test/jiffies>./jiffies_error
no timeout
wrap around: no timeout--------------but in fact, it is wrap around, and jiffies should be large than timeout

2. 为了解决回绕问题，linux内核提供了四个宏来帮助比较jiffies，
2.1 内核中的版本如下：

/*
 * These inlines deal with timer wrapping correctly. You are
 * strongly encouraged to use them
 * 1. Because people otherwise forget
 * 2. Because if the timer wrap changes in future you won't have to
 * alter your driver code.
 *
 * time_after(a,b) returns true if the time a is after time b.
 *
 * Do this with "<0" and ">=0" to only test the sign of the result. A
 * good compiler would generate better code (and a really good compiler
 * wouldn't care). Gcc is currently neither.
 */
#define time_after(a,b) \
        (typecheck(unsigned long, a) && \
         typecheck(unsigned long, b) && \
         ((long)((b) - (a)) < 0))
#define time_before(a,b) time_after(b,a)

#define time_after_eq(a,b) \
        (typecheck(unsigned long, a) && \
         typecheck(unsigned long, b) && \
         ((long)((a) - (b)) >= 0))
#define time_before_eq(a,b) time_after_eq(b,a)

2.2 简化版如下：

#define time_after(a,b) ((long)(b)-(long)(a) < 0)
#define time_before(a,b) ((long)(a)-(long)(b) < 0)
#define time_after_eq(a,b) ((long)(a)-(long)(b) >= 0)
#define time_before_eq(a,b) ((long)(b)-(long)(a) >= 0)

time_after(a,b)和time_after_eq(a,b), 当a超过b时，返回真，否则返回假
time_before(a,b)和time_before_eq(a,b),当b超过a时，返回真，否则返回假。
2.3 解决回绕问题的原理
      下面研究一下time_after(a,b),time_before(a,b)解决回绕问题的原理。
     在理想的情况下，时间是可以不停增长的，后来的时间值一定比前面的值大。然后计算机的世界不是一个理想的世界，所有的值都有其位数限制的。
在32位平台上，
1）unsigned long的位数为32位，从0到0xffffffff值都是递增的。
十六进制：   0-------------------0xffffffff
十进制：      0-------------------4294967295
2）long的位数为32位。按照二进制补码的表示方式，从0到0x7fffffff的区间，值是逐渐递增的。
从0x80000000到0xFFFFFFFF这个区间，值也是递增的。
十六进制：     0x0-----------0x7fffffff----0x80000000-------------0xffffffff
十进制：          0---------2147483647----(-2147483648)----------(-1)           

我们假设时间值a，b都是unsigned long， 而且b发生在a之后， 表示b一定要大于a。如果单纯用unsigned long类型进行a和b大小的比较的话，当a和b的值超过0xffffffff会回绕成0。会导致比较失败。
time_after,time_before使用了有符号long型来解决这个问题。
这里有以下几种情况：
1)a和b都在区间0x0-----------0x7fffffff
 在前提条件（a和b的绝对时间差值不能太大，防止b回绕后比a小）下 ，(long)(a)-(long)(b) < 0必然成立。
2)a在区间0x0-----------0x7fffffff，b在区间0x80000000-------------0xffffffff
  当a-b > 0x80000000时，(long)(a)-(long)(b) < 0必然成立
  举例，假设b = 0x90000000, a = 0x00000001,则 (long)(a)-(long)(b) = 1879048193(0x70000001 < 0x80000000)
             假设b = 0x90000000, a = 0x20000001,则 (long)(a)-(long)(b) = -1879048191(0x9000001 > 0x80000000)
3)a和b都在区间0x80000000-------------0xffffffff
   在前提条件（a和b的绝对时间差值不能太大，防止b回绕后比a小）下 ，(long)(a)-(long)(b) < 0必然成立。
4)a在区间0x80000000-------------0xffffffff，b在区间0x0-----------0x7fffffff
   当a-b > 0x80000000时,此时说明a与b靠的比较近，(long)(a)-(long)(b) < 0必然成立
   举例，假设a = 0x90000000, b = 0x00000001,则 (long)(a)-(long)(b) = -1879048193(0x8fffffff > 0x80000000)
             假设a = 0x90000000, b = 0x20000001,则 (long)(a)-(long)(b) = 1879048191(0x6ffffffff < 0x80000000)
 

所以linux内核采用有符号数的减法来避免回绕的问题。前提是，a和b两个的时间差不能太大，而一般情况下，linux定时器不会有这么大的差出现，所以不成问题。
2.4 举例
    jiffies_ok.c

#include <stdio.h>
#include <stdlib.h>
#define time_before(unknown,known) (long)((long)(unknown) - (long)(known)<0)
unsigned long jiffies = 4294967294;

unsigned long timeout;

int main(int argc, char* argv[])
{

    timeout = jiffies + 1;

    printf("time_before=%d\n",time_before(jiffies,timeout));

    jiffies++;
    jiffies++;

    printf("wrap around: time_before=%d\n",time_before(jiffies,timeout));

    return 0;
}

 编译运行：

[e-mail]:~/test/jiffies>gcc -g jiffies_ok.c -o jiffies_ok
[e-mail]:~/test/jiffies>./jiffies_ok
time_before=1                    ----no timeout
wrap around: time_before=0       --------------timeout