# define jiffies    raid6_jiffies()
#define HZ 1000
//返回当前时间的毫秒值，比如时间戳
static inline uint32_t raid6_jiffies(void)
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec*1000 //tv_sec是秒，乘以1000转成毫秒
            + tv.tv_usec/1000;//tv_usec是微秒，除以1000转成毫秒
}

#define time_after(a,b)         \
        (typecheck(unsigned long, a) && \
         typecheck(unsigned long, b) && \
         ((long)(b) - (long)(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) - (long)(b) >= 0))
#define time_before_eq(a,b)     time_after_eq(b,a)

struct timer_list {
    /*
     * All fields that change during normal runtime grouped to the
     * same cacheline
     */
    struct hlist_node    entry;//链表结构，串接timer_list
    unsigned long        expires;//到期时间，一般用jiffies+5*HZ：表示5秒后触发定时器的回到函数
    void            (*function)(unsigned long);//定时器时间到后的回调函数
    unsigned long        data;//回调函数的参数
    u32            flags;

#ifdef CONFIG_TIMER_STATS
    int            start_pid;
    void            *start_site;
    char            start_comm[16];
#endif
#ifdef CONFIG_LOCKDEP
    struct lockdep_map    lockdep_map;
#endif
};

#include <linux/module.h>
#include <linux/timer.h>
#include <linux/jiffies.h>
 
void time_pre(struct timer_list *timer);
struct timer_list mytimer;
// DEFINE_TIMER(mytimer, time_pre);
void time_pre(struct timer_list *timer)
{
    printk("%s\n", __func__);
    mytimer.expires = jiffies + 500 * HZ/1000;  // 500ms 运行一次
    mod_timer(&mytimer, mytimer.expires);       // 2.2 如果需要周期性执行任务，在定时器回调函数中添加 mod_timer
}
 
// 驱动接口
int __init chr_init(void)
{
    timer_setup(&mytimer, time_pre, 0);        // 1. 初始化
    mytimer.expires = jiffies + 500 * HZ/1000;  //0.5秒触发一次
    add_timer(&mytimer);                       // 2.1 向内核中添加定时器
    printk("init success\n");
    return 0;
}
 
void __exit chr_exit(void)
{
    if(timer_pending(&mytimer))
    {
        del_timer(&mytimer);    // 3.释放定时器
    }
    printk("exit Success \n");
}
 
module_init(chr_init);
module_exit(chr_exit);
 
MODULE_LICENSE("GPL");
MODULE_AUTHOR("XXX");
MODULE_DESCRIPTION("a simple char device example");

static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
               enum hrtimer_mode mode)
{
    struct hrtimer_cpu_base *cpu_base;
    int base;

    memset(timer, 0, sizeof(struct hrtimer));
    //初始化hrtimer的base字段
    cpu_base = raw_cpu_ptr(&hrtimer_bases);

    if (clock_id == CLOCK_REALTIME && mode != HRTIMER_MODE_ABS)
        clock_id = CLOCK_MONOTONIC;

    base = hrtimer_clockid_to_base(clock_id);
    timer->base = &cpu_base->clock_base[base];
    //初始化红黑树的node节点
    timerqueue_init(&timer->node);

#ifdef CONFIG_TIMER_STATS
    timer->start_site = NULL;
    timer->start_pid = -1;
    memset(timer->start_comm, 0, TASK_COMM_LEN);
#endif
}

/**
 * hrtimer_start_range_ns - (re)start an hrtimer on the current CPU
 * @timer:    the timer to be added
 * @tim:    expiry time
 * @delta_ns:    "slack" range for the timer
 * @mode:    expiry mode: absolute (HRTIMER_MODE_ABS) or
 *        relative (HRTIMER_MODE_REL)
 */
void hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
                u64 delta_ns, const enum hrtimer_mode mode)
{
    struct hrtimer_clock_base *base, *new_base;
    unsigned long flags;
    int leftmost;

    base = lock_hrtimer_base(timer, &flags);

    /* Remove an active timer from the queue:
    最终是调用timerqueue_del函数从红黑树删除
    */
    remove_hrtimer(timer, base, true);
    /* 如果是相对时间，则需要加上当前时间，因为内部是使用绝对时间 */ 
    if (mode & HRTIMER_MODE_REL)
        tim = ktime_add_safe(tim, base->get_time());

    tim = hrtimer_update_lowres(timer, tim, mode);
    /* 设置到期的时间范围 */  
    hrtimer_set_expires_range_ns(timer, tim, delta_ns);

    /* Switch the timer base, if necessary: */
    new_base = switch_hrtimer_base(timer, base, mode & HRTIMER_MODE_PINNED);

    timer_stats_hrtimer_set_start_info(timer);
    /* 把hrtime按到期时间排序，加入到对应时间基准系统的红黑树中 */  
    /* 如果该定时器的是最早到期的，将会返回true 
    最终调用的是timerqueue_add函数
    */  
    leftmost = enqueue_hrtimer(timer, new_base);
    if (!leftmost)
        goto unlock;

    if (!hrtimer_is_hres_active(timer)) {
        /*
         * Kick to reschedule the next tick to handle the new timer
         * on dynticks target.
         */
        if (new_base->cpu_base->nohz_active)
            wake_up_nohz_cpu(new_base->cpu_base->cpu);
    } else {
        hrtimer_reprogram(timer, new_base);
    }
unlock:
    unlock_hrtimer_base(timer, &flags);
}

https://img2022.cnblogs.com/blog/2052730/202201/2052730-20220128120520815-1974947758.png

/*
 * High resolution timer interrupt
 * Called with interrupts disabled
 */
void hrtimer_interrupt(struct clock_event_device *dev)
{
    struct hrtimer_cpu_base *cpu_base = this_cpu_ptr(&hrtimer_bases);
    ktime_t expires_next, now, entry_time, delta;
    int retries = 0;

    BUG_ON(!cpu_base->hres_active);
    cpu_base->nr_events++;
    dev->next_event.tv64 = KTIME_MAX;

    raw_spin_lock(&cpu_base->lock);
    entry_time = now = hrtimer_update_base(cpu_base);
retry:
    cpu_base->in_hrtirq = 1;
    /*
     * 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;
    /*查看红黑树的最下节点，如果到期就执行回调函数，并删除该节点*/
    __hrtimer_run_queues(cpu_base, now);

    /* Reevaluate the clock bases for the next expiry 
    找到下一个到期的定时器
    */
    expires_next = __hrtimer_get_next_event(cpu_base);
    /*
     * Store the new expiry value so the migration code can verify
     * against it.
     */
    cpu_base->expires_next = expires_next;
    cpu_base->in_hrtirq = 0;
    raw_spin_unlock(&cpu_base->lock);

    /* Reprogramming necessary ? */
    if (!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.
     *
     * Acquire base lock for updating the offsets and retrieving
     * the current time.
     */
    raw_spin_lock(&cpu_base->lock);
    now = hrtimer_update_base(cpu_base);
    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->hang_detected = 1;
    raw_spin_unlock(&cpu_base->lock);
    delta = ktime_sub(now, entry_time);
    if ((unsigned int)delta.tv64 > cpu_base->max_hang_time)
        cpu_base->max_hang_time = (unsigned int) delta.tv64;
    /*
     * 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);
    else
        expires_next = ktime_add(now, delta);
    tick_program_event(expires_next, 1);
    printk_once(KERN_WARNING "hrtimer: interrupt took %llu ns\n",
            ktime_to_ns(delta));
}

/*
 * The write_seqcount_barrier()s in __run_hrtimer() split the thing into 3
 * distinct sections:
 *
 *  - queued:    the timer is queued
 *  - callback:    the timer is being ran
 *  - post:    the timer is inactive or (re)queued
 *
 * On the read side we ensure we observe timer->state and cpu_base->running
 * from the same section, if anything changed while we looked at it, we retry.
 * This includes timer->base changing because sequence numbers alone are
 * insufficient for that.
 *
 * The sequence numbers are required because otherwise we could still observe
 * a false negative if the read side got smeared over multiple consequtive
 * __run_hrtimer() invocations.
 */

static void __run_hrtimer(struct hrtimer_cpu_base *cpu_base,
              struct hrtimer_clock_base *base,
              struct hrtimer *timer, ktime_t *now)
{
    enum hrtimer_restart (*fn)(struct hrtimer *);
    int restart;

    lockdep_assert_held(&cpu_base->lock);

    debug_deactivate(timer);
    cpu_base->running = timer;

    /*
     * Separate the ->running assignment from the ->state assignment.
     *
     * As with a regular write barrier, this ensures the read side in
     * hrtimer_active() cannot observe cpu_base->running == NULL &&
     * timer->state == INACTIVE.
     */
    raw_write_seqcount_barrier(&cpu_base->seq);
    /*调用timerqueue_del从红黑树删除节点*/
    __remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE, 0);
    timer_stats_account_hrtimer(timer);
    /*最重要的回调函数*/
    fn = timer->function;

    /*
     * Clear the 'is relative' flag for the TIME_LOW_RES case. If the
     * timer is restarted with a period then it becomes an absolute
     * timer. If its not restarted it does not matter.
     */
    if (IS_ENABLED(CONFIG_TIME_LOW_RES))
        timer->is_rel = false;

    /*
     * Because we run timers from hardirq context, there is no chance
     * they get migrated to another cpu, therefore its safe to unlock
     * the timer base. 
     定时器是被硬件层面的时钟中断触发的，所以这个回调函数肯定是当前cpu执行的
     */
    raw_spin_unlock(&cpu_base->lock);
    trace_hrtimer_expire_entry(timer, now);
    //终于执行了回调函数
    restart = fn(timer);
    trace_hrtimer_expire_exit(timer);
    raw_spin_lock(&cpu_base->lock);

    /*
     * Note: We clear the running state after enqueue_hrtimer and
     * we do not reprogram the event hardware. Happens either in
     * hrtimer_start_range_ns() or in hrtimer_interrupt()
     *
     * Note: Because we dropped the cpu_base->lock above,
     * hrtimer_start_range_ns() can have popped in and enqueued the timer
     * for us already.
     */
    if (restart != HRTIMER_NORESTART &&
        !(timer->state & HRTIMER_STATE_ENQUEUED))
        enqueue_hrtimer(timer, base);//调用timerqueue_add把timer加入红黑树

    /*
     * Separate the ->running assignment from the ->state assignment.
     *
     * As with a regular write barrier, this ensures the read side in
     * hrtimer_active() cannot observe cpu_base->running == NULL &&
     * timer->state == INACTIVE.
     */
    raw_write_seqcount_barrier(&cpu_base->seq);

    WARN_ON_ONCE(cpu_base->running != timer);
    cpu_base->running = NULL;
}

static void __hrtimer_run_queues(struct hrtimer_cpu_base *cpu_base, ktime_t now)
{
    struct hrtimer_clock_base *base = cpu_base->clock_base;
    unsigned int active = cpu_base->active_bases;
    /*遍历各个时间基准系统，查询每个hrtimer_clock_base对应红黑树的左下节点，
    判断它的时间是否到期，如果到期，通过__run_hrtimer函数，对到期定时器进行处理，
    包括：调用定时器的回调函数、从红黑树中移除该定时器、
           根据回调函数的返回值决定是否重新启动该定时器*/
    for (; active; base++, active >>= 1) {
        struct timerqueue_node *node;
        ktime_t basenow;

        if (!(active & 0x01))
            continue;

        basenow = ktime_add(now, base->offset);
        /*
        返回红黑树中的左下节点，之所以可以在while循环中使用该函数，
        是因为__run_hrtimer会在移除旧的左下节点时，
        新的左下节点会被更新到base->active->next字段中，
        使得循环可以继续执行，直到没有新的到期定时器为止
        */
        while ((node = timerqueue_getnext(&base->active))) {
            struct hrtimer *timer;

            timer = container_of(node, struct hrtimer, node);

            /*
             * 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))
                break;

            __run_hrtimer(cpu_base, base, timer, &basenow);
        }
    }
}

/**
 * timerqueue_add - Adds timer to timerqueue.
 *
 * @head: head of timerqueue
 * @node: timer node to be added
 *
 * Adds the timer node to the timerqueue, sorted by the
 * node's expires value.
 */
bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
{
    struct rb_node **p = &head->head.rb_node;
    struct rb_node *parent = NULL;
    struct timerqueue_node  *ptr;

    /* Make sure we don't add nodes that are already added */
    WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));

    while (*p) {
        parent = *p;
        ptr = rb_entry(parent, struct timerqueue_node, node);
        if (node->expires.tv64 < ptr->expires.tv64)
            p = &(*p)->rb_left;
        else
            p = &(*p)->rb_right;
    }
    rb_link_node(&node->node, parent, p);
    rb_insert_color(&node->node, &head->head);

    if (!head->next || node->expires.tv64 < head->next->expires.tv64) {
        head->next = node;
        return true;
    }
    return false;
}
EXPORT_SYMBOL_GPL(timerqueue_add);

/**
 * timerqueue_del - Removes a timer from the timerqueue.
 *
 * @head: head of timerqueue
 * @node: timer node to be removed
 *
 * Removes the timer node from the timerqueue.
 */
bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
{
    WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));

    /* update next pointer */
    if (head->next == node) {
        struct rb_node *rbn = rb_next(&node->node);

        head->next = rbn ?
            rb_entry(rbn, struct timerqueue_node, node) : NULL;
    }
    rb_erase(&node->node, &head->head);
    RB_CLEAR_NODE(&node->node);
    return head->next != NULL;
}
EXPORT_SYMBOL_GPL(timerqueue_del);

/**
 * timerqueue_iterate_next - Returns the timer after the provided timer
 *
 * @node: Pointer to a timer.
 *
 * Provides the timer that is after the given node. This is used, when
 * necessary, to iterate through the list of timers in a timer list
 * without modifying the list.
 */
struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
{
    struct rb_node *next;

    if (!node)
        return NULL;
    next = rb_next(&node->node);
    if (!next)
        return NULL;
    return container_of(next, struct timerqueue_node, node);
}
EXPORT_SYMBOL_GPL(timerqueue_iterate_next);