[讨论]内核里的timer中分级排序的一个问题，我觉得可以做得更好

lin_style

include/timer.h
kernel/timer.c

C/C++ code
static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
    unsigned long expires = timer->expires;
    unsigned long idx = expires - base->timer_jiffies;
    struct list_head *vec;

    if (idx < TVR_SIZE) {
        int i = expires & TVR_MASK;
        vec = base->tv1.vec + i;
    }



见这段， timer的原理是分级。但是在这个级别里是乱序的，采取的算法是expires & TVR_MASK.

三个段其实就是
0x100≤interval≤0x3fff         interval>>8
0x100000≤interval≤0x3ffffff interval>>8＋6＋6
0x4000000≤interval≤0xffffffff interval>>8＋6＋6＋6

我的疑问，为什么不直接interval>>8，得出一个值，这样就形成一个排序。
0下标的时间肯定大于1的小标，1的肯定大于2，这样每次只要执行0下标所悬挂的timer,如果有一个执行不成功，就表示无需执行小标为1的。而不需要遍历整个root。

这个算法也很容易证明
C/C++ code
    for(int i=0; i<0x3fff; ++i)
    {
        printf("%d, ", i>>8);
        if( i%30==0 )
        {
            printf("\n");
        }
    }

lin_style

最后那个算法证明，笑脸是 interval>>n, 后面的n

lin_style

看了2.6的内核，方法已经改了，而且更精确。揭贴

Godbach

发贴的时候禁用 Smiles 就不会出现笑脸了