[转] linux内核定时器的实现

[转] http://simohayha.iteye.com/blog/507576

由于linux还不是一个实时的操作系统,因此如果需要更高精度,或者更精确的定时的话,可能就需要打一些实时的补丁,或者用商用版的实时linux,.

这里内的定时器最小间隔也就是1个tick.

这里还有一个要注意的,我这里的分析并没有分析内核新的hrt 定时器.这个定时器是Monta Vista加入到内核的一个高精度的定时器的实现.

先来看几个相关的数据结构.
///这个是一个最主要的数据结构,表示一个完整的定时器级联表

struct tvec_base {
    ///自旋锁
    spinlock_t lock;
    ///表示由本地cpu正在处理的定时器链表
    struct timer_list *running_timer;
    ///这个表示当前的定时器级联表中最快要超时的定时器的jiffer
    unsigned long timer_jiffies;
    ///下面表示了5级的定时器级联表.
    struct tvec_root tv1;
    struct tvec tv2;
    struct tvec tv3;
    struct tvec tv4;
    struct tvec tv5;
    } ____cacheline_aligned;

下面来看tvec和tvec_root的结构:

struct tvec {
    struct list_head vec[TVN_SIZE];
    };

    struct tvec_root {
    struct list_head vec[TVR_SIZE];
    };

可以看到这两个结构也就是hash链表.每次通过超时jiffies来计算slot,然后插入到链表.这里链表是FIFO的.这里除了tv5外其他几个都是简单的与TVR_MASK按位与计算.

struct timer_list {
struct list_head entry;
//超时节拍数
unsigned long expires;
//定时器将要执行的回调函数
void (*function)(unsigned long);
//传递给回调函数的参数
unsigned long data;
//从属于那个base
struct tvec_base *base;
};

定义了一个per cpu变量.这里要知道定时器的注册和触发执行一定是在相同的cpu上的.
struct tvec_base boot_tvec_bases;
static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases;

内核注册定时器最终都会通过调用internal_add_timer来实现.具体的工作方式是这样的:

1 如果定时器在接下来的0~255个jiffies中到期,则将定时器添加到tv1.

2 如果定时器是在接下来的256*64个jiffies中到期,则将定时器添加到tv2.

3 如果定时器是在接下来的256*64*64个jiffies中到期,则将定时器添加到tv3.

4 如果定时器是在接下来的256*64*64*64个jiffies中到期,则将定时器添加到tv4.

5 如果更大的超时,则利用0xffffffff来计算hash,然后插入到tv5(这个只会出现在64的系统).

看下面的图就能比较清晰了:


接下来看源码:

static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
    ///取出超时jiffies
    unsigned long expires = timer->expires;
    ///得到定时器还有多长时间到期(这里是相比于最短的那个定时器)
    unsigned long idx = expires - base->timer_jiffies;
    struct list_head *vec;

    ///开始判断该把定时器加入到那个队列.依次为tv1到tv5
    if (idx < TVR_SIZE) {
        int i = expires & TVR_MASK;
        vec = base->tv1.vec + i;
    } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
        int i = (expires >> TVR_BITS) & TVN_MASK;
        vec = base->tv2.vec + i;
    } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
        int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
        vec = base->tv3.vec + i;
    } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
        int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
        vec = base->tv4.vec + i;
    } else if ((signed long) idx < 0) {
    /*
    * Can happen if you add a timer with expires == jiffies,
    * or you set a timer to go off in the past
        */
        vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
    } else {
        int i;
        /* If the timeout is larger than 0xffffffff on 64-bit
        * architectures then we use the maximum timeout:
        */
        if (idx > 0xffffffffUL) {
            idx = 0xffffffffUL;
            expires = idx + base->timer_jiffies;
        }
        i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        vec = base->tv5.vec + i;
    }
    /*
    * Timers are FIFO:
    */
    ///最终加入链表
    list_add_tail(&timer->entry, vec);
}

这里要知道内核中的软定时器是用软中断来实现的,软中断的注册以及实现可以看我前面的blog,这里就不介绍了.我们来看timer模块的初始化:

void __init init_timers(void)
{
    ///主要是初始化boot_tvec_bases(如果是smp,则会初始化所有cpu上的boot_tvec_bases)
    int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
        (void *)(long)smp_processor_id());
    init_timer_stats();

    BUG_ON(err == NOTIFY_BAD);
    ///注册到cpu的notify chain(这个我前面的blog也有介绍)
    register_cpu_notifier(&timers_nb);
    ///注册软中断
    open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
}

ok,接下来我们就来看timer_cpu_notify这个函数,其实这个函数还是定时器注册的cpu的notify chain的action:

static struct notifier_block __cpuinitdata timers_nb = {
    .notifier_call  = timer_cpu_notify,
};

static int __cpuinit timer_cpu_notify(struct notifier_block *self,
                                      unsigned long action, void *hcpu)
{
    long cpu = (long)hcpu;
    switch(action) {
    case CPU_UP_PREPARE:
    case CPU_UP_PREPARE_FROZEN:
        ///模块初始化的时候就会调用这个函数
        if (init_timers_cpu(cpu) < 0)
            return NOTIFY_BAD;
        break;
        ....................................
    return NOTIFY_OK;
 }

其他的部分我们忽略,我们就发现定时器模块会调用init_timers_cpu来初始化.我们来分析这个函数.

这个函数最主要的功能就是初始化boot_tvec_bases,也就是全局的定时器表:

static int __cpuinit init_timers_cpu(int cpu)
{
int j;
struct tvec_base *base;
///可以看到这个是一个静态变量.它保存了每个cpu上的那个boot_tvec_bases.
static char __cpuinitdata tvec_base_done[NR_CPUS];

///如果为空,说明这个cpu上的定时器表还没有初始化,因此需要初始化
if (!tvec_base_done[cpu]) {
/*这个也是一个静态变量.它表示了cpu是否初始化完毕.这个函数有一个宏__cpuinit,这个将 *这个函数放置到cpuinit这个段,因此也就是说这个函数会先在cpu初始化时调用,也就是第一**次会先给boot_done赋值,然后再调用这个函数才会进入kmalloc. */
static char boot_done;

if (boot_done) {
/*
* The APs use this path later in boot
*/
///malloc一个tvec_base
base = kmalloc_node(sizeof(*base),
GFP_KERNEL | __GFP_ZERO,
cpu_to_node(cpu));
if (!base)
return -ENOMEM;

/* Make sure that tvec_base is 2 byte aligned */
if (tbase_get_deferrable(base)) {
WARN_ON(1);
kfree(base);
return -ENOMEM;
}
///由于在per cpu的变量中类型为tvec_bases的,只有boot_tvec_bases,因此,也就是将base这个指针付给boot_tvec_bases.
per_cpu(tvec_bases, cpu) = base;
} else {
///cpu初始化完毕后会进入这里,标记了cpu已经boot完毕.此时内存初始化完毕.
boot_done = 1;
base = &boot_tvec_bases;
}
tvec_base_done[cpu] = 1;
} else {
///取出tvec_base付给base
base = per_cpu(tvec_bases, cpu);
}
///开始初始化
spin_lock_init(&base->lock);

///开始初始化5个定时器表
for (j = 0; j < TVN_SIZE; j++) {
INIT_LIST_HEAD(base->tv5.vec + j);
INIT_LIST_HEAD(base->tv4.vec + j);
INIT_LIST_HEAD(base->tv3.vec + j);
INIT_LIST_HEAD(base->tv2.vec + j);
}
for (j = 0; j < TVR_SIZE; j++)
INIT_LIST_HEAD(base->tv1.vec + j);

///默认值为初始化时的jiffes
base->timer_jiffies = jiffies;
return 0;
}

通过上面的定时器初始化函数我们知道定时器软中断所对应的action是run_timer_softirq,也就是当时钟中断到来,软中断启动时,就会调用这个函数,因此我们来看这个函数:

这个函数功能很简单,它的最关键就是调用__run_timers,这个函数才是真正处理定时器的函数.

static void run_timer_softirq(struct softirq_action *h)
{
    struct tvec_base *base = __get_cpu_var(tvec_bases);

    ///这个函数应该是提供给2.6.31内核的新特性Performance Counters.
    perf_counter_do_pending();
    ///处理hrt timer
    hrtimer_run_pending();

    ///判断当前的jiffies是否大于等于最小的那个超时jiffies.是的话就进入定时器处理
    if (time_after_eq(jiffies, base->timer_jiffies))
        __run_timers(base);
}

__run_timers这个函数的主要功能是运行所有超时的定时器:

static inline void __run_timers(struct tvec_base *base)
{
    struct timer_list *timer;
    ///关闭中断并且开启自旋锁
    spin_lock_irq(&base->lock);

    ///然后遍历定时器级联表
    while (time_after_eq(jiffies, base->timer_jiffies)) {
        ///这里的head和work_list其实表示的就是已经超时的定时器,也就是我们将要处理的定时器.
        struct list_head work_list;
        struct list_head *head = &work_list;

        ///从timer_jiffies得到所在index,其实也就是在tv1中的index
        int index = base->timer_jiffies & TVR_MASK;

        ///开始处理层叠定时器,这里的这个cascade是一个关键的函数,我们下面会分析,这里只需要知道这个函数其实也就是用来一层层的得到这个定时器处于哪个级别中.
        if (!index &&
            (!cascade(base, &base->tv2, INDEX(0))) &&
            (!cascade(base, &base->tv3, INDEX(1))) &&
            !cascade(base, &base->tv4, INDEX(2)))
            cascade(base, &base->tv5, INDEX(3));
        ///更新timer_jiffies.
        ++base->timer_jiffies;
        ///用work_list替换掉base->tv1.vec + index.这里因为上面的处理中,就算定时器不在base->tv1中,可是通过cascade的调节,会将base->tv2加入到base->tv1中,或者说base->tv3,以此类推.
        list_replace_init(base->tv1.vec + index, &work_list);

        ///如果这个值不为空说明有已经超时的定时器.这里head也就是work_list,也就是base->tv1
        while (!list_empty(head)) {
            void (*fn)(unsigned long);
            unsigned long data;
            ///取出定时器.
            timer = list_first_entry(head, struct timer_list,entry);
            fn = timer->function;
            data = timer->data;

            timer_stats_account_timer(timer);

            ///设置当前正在处理的定时器为timer(这个主要是针对smp的架构),因为我们是在软中断中进行的,因此要防止多个cpu的并发.
            set_running_timer(base, timer);
            ///删除这个定时器.
            detach_timer(timer, 1);

            spin_unlock_irq(&base->lock);
            {
                int preempt_count = preempt_count();
                lock_map_acquire(&lockdep_map);
                ///执行定时器回调函数
                fn(data);

                .............................................
            }
            spin_lock_irq(&base->lock);
        }
    }
    ///修改base->running_timer为空
    set_running_timer(base, NULL);
    spin_unlock_irq(&base->lock);
}

ok我们接下来来看下定时器超时的机制,关键在这段代码:

if (!index &&
            (!cascade(base, &base->tv2, INDEX(0))) &&
                (!cascade(base, &base->tv3, INDEX(1))) &&
                    !cascade(base, &base->tv4, INDEX(2)))
            cascade(base, &base->tv5, INDEX(3));

index为0就说明当前要处理的定时器不在base->tv1 中.因此我们需要cascade来进行调解.

///得到在N级(也就是tv2,tv3...)的定时器表中的slot.这里可以对照我们前面的internal_add_timer加入定时器的情况.
#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)

static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
    /* cascade all the timers from tv up one level */
    struct timer_list *timer, *tmp;
    struct list_head tv_list;

    ///这里实例化tv_list为我们将要处理的链表.并将老的list重新初始化为空.
    list_replace_init(tv->vec + index, &tv_list);

    /*
    * We are removing _all_ timers from the list, so we
    * don't have to detach them individually.
    */
    list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
        BUG_ON(tbase_get_base(timer->base) != base);
        ///重新加入定时器,也就是加入到自己对应的位置
        internal_add_timer(base, timer);
    }
    ///然后返回index,这里可以看到如果index为空则说明这个级别的定时器也已经都处理过了,因此我们需要再处理下一个级别.
    return index;
}

可以看到定时器处理始终都是在处理tv1,如果tv1已经处理完了,则将tv2添加到tv1,以此类推.


而定时器软中断如何触发呢,是用update_process_times来触发的,这个函数比较简单,主要是调用run_local_timers来触发软中断:

void run_local_timers(void)
{
    hrtimer_run_queues();
    ///触发软中断.
    raise_softirq(TIMER_SOFTIRQ);
    softlockup_tick();
}

[转] http://simohayha.iteye.com/blog/507576