FreeBSD里的callwheel机制(补充前一篇)

FreeBSD里的定时器是基于一种callwheel机制，因为前一篇用到了timer，所以这里就简单介绍一下其基本原理。之所以单独成一篇，是由于前一篇篇幅太长了。

timer

来看下timer start的时候做了什么事, 在FreeBSD里timer是借助于callout API来实现的。callout是FreeBSD提供的一个kernel interface，它可以让一个函数在未来被调用。

在FreeBSD里面和时间有关的一些应用都会用到callout, 它在系统里面的一些应用如下：

对于callout的具体细节不在此讨论，只说一下和定时器有关的关键部分。

timer start函数如下所示：

1
2
3
4
5
6
7
8
9
10

timer_start (struct  callout *c, ...)
{
     ...
   // 首先计算出超时时刻
     expire = ticks + delay_ticks;
   // 将该callout结构体添加到callwheel里面对应的TAILQ中
   // callwheelmask是(callwheelsize - 1), 它由callout数目来决定
     TAILQ_INSERT_TAIL(&callwheel[expire & callwheelmask], c, ...);
     ...
}

可以看到，该callout是通过一种hash算法(expire & callwheelmask)来被添加到对应的TAILQ里面。callwheelsize是一个实验值，如果值太小的话显然会导致hash冲突比较多；而如果太大也不行，它会预先分配很多内存。所以FreeBSD Kernel Guys就采用了一个实验值，即假定一个进程（注意，在kernel里，进程和线程是没有区别的）以及一个打开的文件描述符都可以有一个callout。所以callout的最大值ncallout就被设置为了:

ncallout = 16 + maxproc + maxfiles;

callwheelsize是不大于ncallout的最大的2的幂值，比如如果ncallout是2076，那么callwheelsize就是2048。

callout是借助于时钟中断来实现的。

hardclock

首先要明白一个概念，什么是时钟中断上半部(hardclock)与时钟中断下半部(softclock).中断的上半部是不可以被打断的，它通常用来处理比较紧急且耗时短的任务；中断的下半部则是可以被打断的，它可以用来处理那些比较耗时的任务。比如timer，它就是在时钟中断的下半部处理的，即softclock里面。

以下代码皆摘自FreeBSD Kernel。FreeBSD Kernel时钟这部分的代码相对比较稳定，基本没有太大变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/*
* The real-time timer, interrupting hz times per second.
*/
// 时钟中断入口函数。1秒会有hz个中断。在BSD里面，hz默认配置的是1000或者100.
void
hardclock(frame)
   // 每来一次中断， ticks增加1.
     ticks++;.
   // 如果当前ticks对应的callwheel链表不为空，就说明有timer需要处理.
     if (TAILQ_FIRST(&callwheel[ticks & callwheelmask]) != NULL) {
          need_softclock = 1;
          // 否则（所有的timer都处理完了），就>让softticks跟ticks保持一致.（softticks是一直小于等于ticks的）
     } else if (softticks + 1 == ticks)
          ++softticks;

     // 如果需要时钟软中断，就在这里启动。 
     if (need_softclock)
        swi_sched(softclock_ih, 0);

Nota bene. 往右拉可以看到全部的注释文字。

softclock

软时钟中断的入口函数是softclock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/*
* Software (low priority) clock interrupt.
* Run periodic events from timeout queue.
*/
void
softclock(void *dummy)
   // softticks一直小于等于ticks   
     while (softticks != ticks) {
        // 来记录时钟软中断数    
          softticks++;
           /*
            * softticks may be modified by hard clock, so cache
            * it while we work on a given bucket.
            */
          curticks = softticks;
        // 取出当前softticks>对应的timer链表
          bucket = &callwheel[curticks & callwheelmask];
          c = TAILQ_FIRST(bucket);
          while (c) {
               if (c->c_time != curticks) {
                  // 保持该元素在链表里，持续的检查这个链表.
                    c = TAILQ_NEXT(c, c_links.tqe);
                    ++steps;
                    if (steps >= MAX_SOFTCLOCK_STEPS) {
                         nextsoftcheck = c;
                         ;
                         c = nextsoftcheck;
                         steps = 0;
                    }
               // 这个timer expire了  
               } else {
                  // 取下一个要判断的timer
                    nextsoftcheck = TAILQ_NEXT(c, c_links.tqe);
                    TAILQ_REMOVE(bucket, c, c_links.tqe);
                  // 执行相应的函数
                    c_func(c_arg);
                    c = nextsoftcheck;
               }
          }

一张图来描述callwheel结构体，就是这个样子的：

ref

Comments