linux时间子系统（七）

简单介绍linux下的时间子系统。包括clocksource，timekeeper和定时器的内容。

3.2 高精度定时器

  随着内核的不断升级和硬件的不断发展，由于低精度定时器有一定的局限性，内核从2.6.16开始加入了高精度定时器架构。在实现方式上，高精度定时器的实现代码几乎没有借用低精度定时器的数据结构和代码，原因有以下几点：

  1 低精度定时器的代码和jiffies的关系太过紧密，并且默认按照32为进行设计，如果要基于它来实现高精度时钟，必然会打破原有的time wheel的概念，而且会引入大量的#if #else判断。

  2 虽然大部分时间里，time wheel可以实现O(1)的时间复杂度，但是如果有进位发生，不可预测的O(n)定时器级联迁移，大大的影响了高精度定时器的精度。

  3 低精度定时器几乎为超时而设计，为此对它进行了大量的优化，精确时间并不是它的主要目的。

  为此，内核为高精度定时器重新设计了一套软件架构，他可以为我们提供纳秒级的定时精度，以满足对精确时间有迫切需求的应用和内核驱动，如多媒体应用，音频设备的驱动程序等等。

3.2.1 hrtimer重要的数据结构

  低精度定时器使用5个链表数组来组织timer_list结构，形成了著名的时间轮的概念。而高精度时钟，为了具备稳定而快速的查找、快速的插入和删除定时器的能力以及排序功能，内核的开发者最后选定红黑树，来组织hrtimer。随着系统的运行，hrtimer不断的被创建和销毁，新的hrtimer按照到期时间被插入到红黑树中，红黑树的最左下节点即为最快到期的定时器。内核使用hrtimer结构表示一个高精度定时器。

struct hrtimer {

        struct timerqueue_node          node;

        ktime_t                         _softexpires;

        enum hrtimer_restart            (*function)(struct hrtimer *);

        struct hrtimer_clock_base       *base;

        unsigned long                   state;

        struct list_head                cb_entry;

        int                             irqsafe;

#ifdef CONFIG_TIMER_STATS

        int                             start_pid;

        void                            *start_site;

        char                            start_comm[16];

#endif                  

};

   _softexpires,表示到期时间。

  function，定时器到期时的回调函数。其返回值是一个枚举值，决定了该定时器是否需要被重新激活。如果返回值为HRTIMER_RESTART，表明需要重新激活。如果为HRTIMER_NORESTART，表明不需要重新激活。

  state，用于表示hrtimer当前的状态。

#define HRTIMER_STATE_INACTIVE  0x00    //定时器未激活

#define HRTIMER_STATE_ENQUEUED  0x01    // 定时器已经排入红黑树中

#define HRTIMER_STATE_CALLBACK  0x02    // 定时器的回调函数正在被调用

#define HRTIMER_STATE_MIGRATE   0x04    // 定时器正在cpu间做迁移

   base，表示当前定时器是基于哪一种时间基准的。hrtimer到期时间可以基于以下几种时间基准

enum  hrtimer_base_type {

        HRTIMER_BASE_MONOTONIC,    //monotonic time

        HRTIMER_BASE_REALTIME,    //wall time

        HRTIMER_BASE_BOOTTIME,    //boot time

        HRTIMER_MAX_CLOCK_BASES,

};

3.2.2 红黑树

  与低精度时钟一样，处于效率和互斥的考虑，每个cpu单独管理属于自己的hrtimer。为此，专门定义了一个结构hrtimer_cpu_base:

struct hrtimer_cpu_base {

        raw_spinlock_t                  lock;

        unsigned long                   active_bases;

#ifdef CONFIG_HIGH_RES_TIMERS

        ktime_t                         expires_next;  //三种时间基准的定时器最先到期定时器的时间

        int                             hres_active;

        int                             hang_detected;

        unsigned long                   nr_events;

        unsigned long                   nr_retries;

        unsigned long                   nr_hangs;

        ktime_t                         max_hang_time;

#endif

#ifdef CONFIG_PREEMPT_RT_BASE

        wait_queue_head_t               wait;

#endif

        struct hrtimer_clock_base       clock_base[HRTIMER_MAX_CLOCK_BASES];  //每个cpu都有三种时间基准的高精度定时器列表

};

struct hrtimer_clock_base {            

      struct hrtimer_cpu_base *cpu_base;  //指向所属cpu的hrtimer_cpu_base结构

        int                     index;  

        clockid_t               clockid;  //确定基于哪种时间基准

        struct timerqueue_head  active;   //红黑树，含定时器列表

        struct list_head        expired;  

        ktime_t                 resolution;

        ktime_t                 (*get_time)(void);

        ktime_t                 softirq_time;

        ktime_t                 offset;

};

struct timerqueue_node {

        struct rb_node node;

        ktime_t expires;

};

struct timerqueue_head {

        struct rb_root head;

        struct timerqueue_node *next;

};

   timequeue_head结构在红黑树的基础上，增加了一个next字段，用于保存红黑树中最先到期的定时器节点，实际上就是红黑树的最左下节点。有了next字段，系统就不必遍历整个红黑树，只要取出next字段对应的节点处理即可。