linux内核定时器
linux的定时器一般分为两种，一种是timeout类型，也就是在指定时间之前完成相应的任务即可，这种定时器对精度要求较低，晚几毫秒执行不会有很大的影响，而且一般这种类型的定时器要处理的任务在超时之前就已经完成，并且从定时器的队列中删除了，用不着真正的等到timeout然后由定时器模块来处理，这种较低精度要求的定时器一般使用timer wheel定时器。另一种类型的就是timer类型定时器，这就要求必须在指定的时间执行相应的任务，因此精度要求较高，这种场合一般适用高精度的定时器hrtimer。
timer wheel和hrtimer使用两种不同的机制实现定时器，timer wheel使用jiffies为基准来判断任务是否过期，由于jiffies计数系统的节拍，系统每次时钟中断都会将这个值加1，系统每秒的时钟中断的次数为HZ（宏定义的一个常量，一般为100），因此jiffies为timer wheel定时器提供了毫秒级的精度。而hrtimer需要高精度的时钟设备，为系统提供纳秒级的定时器。这两者都通过软中断来驱动，timer wheel定时器通过软中断TIMER_SOFTIRQ， 而hrtimer通过HRTIMER_SOFTIRQ来相应定时器。
1. timer wheel定时器timer wheel定时器的请求通过struct timer_list来抽象，然后按照定时器的过期时间和基准时间的差值将其组织在双链表中，且相同过期时间的定时器放在同一个链表中，当响应软中断时，则将过期时间在当前时间之前的定时器全部删除，并且执行相应的回调函数。struct timer_list对象是放在tv1--tv5中那个struct tvec上是通过timer_list.expire-tvec_base.timer_jiffies来确定的，也就是说，是通过过期时间和基准时间之间的差值来确定struct timer_list对象在哪个tvX上的。
若上面的差值可以在TVR_BITS位内表示出来，则将相应的timer_list放在tv1上，而TVR_BITS内的数值作为timer_list在tvec数组上的索引，将其串到双链表上，若可以在TVR_BITS + TVN_BITS位内表示差值，则将其放在tv2上，TVN_BITS位段内的值当做tv2数组内部的索引，然后依次类推，若差值大于1<<TVR_BITS+3*TVN_BTS，则将其全部放在tv5内，表示过期时间还很长，一段时间内轮不到其执行，最后的TVN_BITS位作为tv5内的索引。
插入定时器的操作可以清晰的看到上面的过程：void hrtimer_interrupt(struct clock_event_device *dev){struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);ktime_t expires_next, now, entry_time, delta;int i, retries = 0;BUG_ON(!cpu_base->hres_active);cpu_base->nr_events++;dev->next_event.tv64 = KTIME_MAX;entry_time = now = ktime_get(); //获得当前时间retry:expires_next.tv64 = KTIME_MAX;raw_spin_lock(&cpu_base->lock);/* * We set expires_next to KTIME_MAX here with cpu_base->lock * held to prevent that a timer is enqueued in our queue via * the migration code. This does not affect enqueueing of * timers which run their callback and need to be requeued on * this CPU. */cpu_base->expires_next.tv64 = KTIME_MAX;for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {struct hrtimer_clock_base *base;struct timerqueue_node *node;ktime_t basenow;if (!(cpu_base->active_bases & (1 << i)))continue;base = cpu_base->clock_base + i;basenow = ktime_add(now, base->offset); //修正获得一个递增的时间while ((node = timerqueue_getnext(&base->active))) { /*从红黑树上获得最左边的节点，这个指针缓存在timer_queue结构中，直接返回即可*/struct hrtimer *timer;timer = container_of(node, struct hrtimer, node); //contain_of机制获得timer对象/* * The immediate goal for using the softexpires is * minimizing wakeups, not running timers at the * earliest interrupt after their soft expiration. * This allows us to avoid using a Priority Search * Tree, which can answer a stabbing querry for * overlapping intervals and instead use the simple * BST we already have. * We don't add extra wakeups by delaying timers that * are right-of a not yet expired timer, because that * timer will have to trigger a wakeup anyway. */if (basenow.tv64 < hrtimer_get_softexpires_tv64(timer)) { /*过期时间比当前时间晚则在这个clock_base上不存在过期的对象，直接跳过这个clock_base，返回for循环*/ktime_t expires;expires = ktime_sub(hrtimer_get_expires(timer), base->offset);if (expires.tv64 < expires_next.tv64)expires_next = expires;break;}__run_hrtimer(timer, &basenow); //执行回调函数并且删除timer对象}}/* * Store the new expiry value so the migration code can verify * against it. */cpu_base->expires_next = expires_next; //由上面得出新的下一次过期时间raw_spin_unlock(&cpu_base->lock);/* Reprogramming necessary ? */if (expires_next.tv64 == KTIME_MAX || /*对时间设备重编程，若由于过长的回调函数消耗时间等原因导致expires_next是过去的时间，则重编程失败*/ !tick_program_event(expires_next, 0)) {cpu_base->hang_detected = 0;return;}/* * The next timer was already expired due to: * - tracing * - long lasting callbacks * - being scheduled away when running in a VM * * We need to prevent that we loop forever in the hrtimer * interrupt routine. We give it 3 attempts to avoid * overreacting on some spurious event. */now = ktime_get(); //重编程失败，则重试3次cpu_base->nr_retries++;if (++retries < 3)goto retry;/* * Give the system a chance to do something else than looping * here. We stored the entry time, so we know exactly how long * we spent here. We schedule the next event this amount of * time away. */cpu_base->nr_hangs++; //如果三次重试都失败，则当前cpu_base挂起cpu_base->hang_detected = 1;delta = ktime_sub(now, entry_time);if (delta.tv64 > cpu_base->max_hang_time.tv64)cpu_base->max_hang_time = delta;/* * Limit it to a sensible value as we enforce a longer * delay. Give the CPU at least 100ms to catch up. */if (delta.tv64 > 100 * NSEC_PER_MSEC)expires_next = ktime_add_ns(now, 100 * NSEC_PER_MSEC);elseexpires_next = ktime_add(now, delta);tick_program_event(expires_next, 1);/*给CPU最大100ms的时间的来处理cpu_base挂起，重编程时钟设备，在最多100ms后重新产生事件*/printk_once(KERN_WARNING "hrtimer: interrupt took %llu ns\n", ktime_to_ns(delta));}
