文档选项 将此页作为电子邮件发送 未显示需要 JavaScript 的文档选项

级别： 初级

陈 撰 (zhuanchen@gmail.com), 硕士研究生, 中国科学院计算技术研究所

2008 年 9 月 18 日

在 Linux 文件系统中，元数据的引用计数主要用于管理元数据（如 inode, dentry 结构）在内存中的创建、使用和释放。了解这部分的机制，有利于深入认识文件系统的运行机制，以及Linux如何在内存中管理元数据。这部分内容也是构建分布式文件系统所必须的知识，由此才能保证元数据在分布式文件系统中的正确使用。

概述

元数据是一个文件系统的重要部分。很多书籍和文章都介绍过 dentry 和 inode 在 Linux 中的作用和机制，但却很少有文献涉及到它们的使用计数（ usage counter ）。使用计数的机制看似很简单：使用了一个元数据就递增，用完了就递减。但在这句简单的描述后面，具体的过程到底是如何进行的呢？这实际上贯穿了整个元数据的操作以及元数据在内存中的管理。了解这部分的机制，是一个很有意思的过程，可以让你看到 Linux 严谨缜密的思路，可以深入认识 Linux 文件系统的运行机制。这部分内容也是构建分布式文件系统所必须的知识。

本文仍然从两方面来介绍使用计数：增加和减少。最后再看一下在分布式环境中有哪些变化。

这里所引用的代码依据的是 Linux 内核 2.6.20 的版本。

使用计数的增加

创建操作

元数据的创建主要可以分为对文件的创建和对目录的创建。不管是文件还是目录，它们都对应同样的元数据结构，在内存中都有 inode 和 dentry 。

下面我们分别看一下主要的两个创建操作：创建文件和创建目录。

（1）创建文件

创建文件是通过系统调用 sys_open() ，并设置 O_CREATE 标志位来实现的。其调用过程如下：

sys_open() > do_sys_open() > do_filp_open() > open_namei()

在 open_namei() 中，会创建出 dentry 和 inode 结构。先看关于 dentry 的路径：

open_namei() > lookup_hash() > __lookup_hash()

这里会分成3种情况：

• 在 dcache 中查找： __lookup_hash() > cached_lookup() > d_lookup() > __d_lookup()
• 分配新的 dentry： __lookup_hash() > d_alloc() > atomic_set(&dentry -> d_count, 1);
• 在具体文件系统中查找： __lookup_hash() > i_op -> lookup()

和查找有关的内容我们在后面介绍，这里只看创建，也就 d_alloc() ，它会分配一个新的 dentry 结构，在分配的过程中，就会把 dentry 的使用计数初始化为1。在 d_alloc() 中，还会通过函数 dget() 递增父目录的使用计数，这是为了防止父目录在该 dentry 删除前被删除。（“/”除外，它没有父目录）：

d_alloc() > dget(parent) > atomic_inc(&dentry->d_count);

我们再看关于 inode 的路径：

open_namei() > open_namei_create() > vfs_create() > i_op->create()

最终会调用具体文件系统的 create 函数。这里以 Ext2 为例，其调用过程如下：

ext2_create() > ext2_new_inode() > new_inode() > 
alloc_inode() > atomic_set(&inode->i_count, 1);

具体文件系统在分配 inode 结构的时候，会通过初始化把 inode 的 i_count 域置为1。同时还把 inode 的 i_nlink 域置为1，这个域表示 inode 的 hard link 的数目，其值会被写入到具体文件系统的磁盘中。

总结一下，通过创建操作，会在内存中建立起 dentry 和 inode 结构，并且会把它们的使用计数都初始化为1。

（2）创建目录

创建目录和创建文件是类似的，这里我们简单看一下调用的路径就清楚了。

创建目录是通过系统调用 sys_mkdir() 来实现的。关于 dentry 的路径如下：

sys_mkdir() > sys_mkdirat() > lookup_create() > lookup_hash() > __lookup_hash()

可以看出，这与前面“创建文件”中介绍的是一样的。

关于 inode 的路径如下：

sys_mkdir() > sys_mkdirat() > vfs_mkdir() > i_op->mkdir()

最终会调用具体文件系统的 mkdir 函数。这里以 Ext2 为例，其调用过程如下：

ext2_mkdir() > ext2_new_inode() > new_inode() > alloc_inode() > atomic_set()

可以看出，这与前面“创建文件”中介绍的也是一样的。

由此也可以看出，从内存中的元数据结构来看，Linux对文件和目录的管理是一样的。

查找操作

创建了一个对象（文件或目录）后，要使用这个对象，就必须先进行查找。查找操作是元数据使用的关键操作，基本上所有元数据操作都会以查找操作为起始，因为只有找到了元数据才能进一步对其进行操作。即使对于创建操作，一开始也要进行查找，只不过因为要创建的对象还不存在，所以会查找失败，然后才进行创建。

查找操作的入口函数是 __link_path_walk() ，其调用过程如下：

__link_path_walk() > do_lookup()

到了这里，要做的事情主要是在内存中查找相应文件所对应的 dentry 结构。这会分为两种情况：

（1）该 dentry 结构在内存中

此时，通过哈希就可以获取该 dentry 结构，并将其使用计数递增。

do_lookup() > __d_lookup() > atomic_inc(&dentry->d_count)

（2）该 dentry 结构不在内存中

此时，该 dentry 结构可能从来就没在内存中建立起来，或者在内存中存在过，但已经从 LRU 队列 dentry_unused 中被换出内存。无论如何，都需要从磁盘读取元数据，在内存中建立起 dentry 和 inode 结构。这时所进行的步骤是：

首先在内存中分配一个dentry结构：

do_lookup() > real_lookup() > d_alloc() > atomic_set(&dentry->d_count, 1);

这里的 d_alloc() 和前面“创建操作”介绍的一样，会把 dentry 的使用计数初始化为1，并将其父目录的使用计数通过 dget() 递增。

分配了 dentry 结构后，就要从磁盘找出对应的元数据。这个过程因文件系统而异，所以通过父节点的 inode -> i_op 里的函数来进行。

real_lookup() > i_op->lookup()

这里以 Ext2 为例，调用的是 ext2_create() ，过程如下：

(1) ext2_lookup() > iget(dir->i_sb, ino);
(2) ext2_lookup() > d_splice_alias() > __d_find_alias() > __dget_locked() > 
     atomic_inc(&dentry->d_count);

前者调用 iget() ，首先通过 ino 在 inode cache 中查找 inode ，如果找到就返回并增加其引用计数；如果没有找到，就分配一个新的（调用 alloc_inode() ，会把使用计数初始化为1，参照前面“创建操作”），并从磁盘读入相应索引节点，在内存中建立起 inode 结构。

后者则把 dentry 与 inode 结构绑定，并递增了 dentry 的使用计数。

总结一下，查找操作的主要过程就是在内存中查找 dentry 结构，如果找到就递增其使用计数；如果找不到就到磁盘中去取，并在内存建立 dentry 和 inode 结构，同时将它们的使用计数初始化为1。因此查找操作都会增加 dentry 的使用计数，或者递增，或者初始化为1。

元数据操作对使用计数的运用

这里我们举例说明元数据操作对 dentry 使用计数的运用，让大家对其有个比较具体的认识和感觉。

元数据操作的实质就是对元数据进行使用。那么，要使用某个元数据时，必须在内存中为其建立相应的结构，即 inode 和 dentry 。但并不是所有的元数据每时每刻都会有对应的结构在内存中，只有需要时才会建立这些结构，并且在特定的时候又会被换出内存。那么如何管理内存元数据结构的使用，从而决定其何时在内存中，何时被换出，这就是通过 dentry 的使用计数来实现的。

下面我们以两个常见的元数据操作为例，来看 Linux 如何管理内存元数据结构的使用。

（1） getattr 操作

Linux 内核中有很多操作都会调用到 getattr ，我们举其中的一个来说明：sys_stat() > vfs_stat_fd() 。

函数 vfs_stat_fd() 比较短，我们将其内容都列出来：

int vfs_stat_fd(int dfd, char __user *name, struct kstat *stat)
{
    struct nameidata nd;
    int error;

    error = __user_walk_fd(dfd, name, LOOKUP_FOLLOW, &nd);
    if (!error) {
        error = vfs_getattr(nd.mnt, nd.dentry, stat);
        path_release(&nd);
    }
    return error;
}

这里先调用了 __user_walk_fd() ，这个函数继续走下去的路径是：

__user_walk_fd() > do_path_lookup() > link_path_walk() > __link_path_walk()

可以看出， __link_path_walk() 就是前面介绍过的查找操作。如果成功返回，就会增加 dentry 的使用计数，否则就不增加。而如果查找成功，就进行具体的 getattr 的工作，调用的是 vfs_stat_fd() 的主体函数 vfs_getattr() 。这之后，会调用 path_release() ，这个函数的路径是：

path_release(&nd) > dput(nd->dentry)

函数 dput() 会将 dentry 的使用计数减少，这个函数我们将在后面详细介绍。

总结一下， getattr 操作首先要查找元数据，找到后，就增加 dentry 的使用计数，只要 dentry 的使用计数不为0，它就会存在于 dcache 中，而不会被换出内存。当 getattr 的主要操作步骤完成后，就会减少 dentry 的使用计数，表明 getattr 操作已经完成，不再需要使用这个 dentry 了。

（2） link 操作

下面再看一个操作。 Link 操作用于创建一个对象链接。其调用路径为：

sys_link() > sys_linkat()

接下来可以分为七个部分：

(1) error = __user_walk_fd(olddfd, oldname,
                       flags & AT_SYMLINK_FOLLOW ? LOOKUP_FOLLOW : 0,
                       &old_nd);
(2) error = do_path_lookup(newdfd, to, LOOKUP_PARENT, &nd);
(3) new_dentry = lookup_create(&nd, 0);
(4) error = vfs_link(old_nd.dentry, nd.dentry->d_inode, new_dentry);
(5) dput(new_dentry);
(6) path_release(&nd);
(7) path_release(&old_nd);

第1步中， __user_walk_fd() 会查找要被链接的文件，这和前面 getattr 中的函数一样，会把这个文件对应的 dentry 的使用计数进行递增。它和第7步中的 path_release() 对应。

第2步中， do_path_lookup() 会查找要创建的链接的父目录，它同样会进行查找操作，递增 dentry 的使用计数。它和第6步中的 path_release() 对应。

第3步中， lookup_create() 会创建链接对象的 dentry 结构，这和前面“创建目录”中介绍的函数一样。它和第5步中的 dput() 对应。

这里我们再次看到，一个元数据操作中都会先查找涉及到的元数据，并增加其 dentry 的使用计数，然后在该操作结束的时候递减这些使用计数。

对于 link 操作，我们还要讲讲它的主体函数，也就是 vfs_link() ，其路径为：

vfs_link() > i_op->link()

以 Ext2 为例，调用的是 ext2_link() ，过程如下：

(1) ext2_link() > inode_inc_link_count() > inc_nlink()
(2) ext2_link() > atomic_inc(&inode->i_count);

先看前者，这里的 inode 结构对应的是被链接的文件， ext2_link() 会递增该 inode 的 i_nlink ，前面说过，这个域表示 inode 的 hard link 的数目，因为我们对这个文件建立了一个新的链接，所以会对这个域进行递增。

后者的 inode 结构依然对应的是被链接的文件， ext2_link() 会递增 inode 的使用计数。到目前位置，我们看到，各个操作对元数据使用计数的运用主要都是针对 dentry ，而很少针对 inode 。这是因为 dentry 主要用于内存中目录树结构的表示，而查找操作主要就是针对目录树结构来进行的，因此它频繁地对 dentry 的使用计数进行操作。对于 inode 的使用计数，它主要表示这个元数据的存在，因此一般只在创建这个 inode 的时候以及删除的时候才会用到。我们知道一个 inode 可以对应多个 dentry ，这是因为一个文件可以有多个链接，所以当多了一个链接时，就要递增 inode 的使用计数。

使用计数的减少

dput 函数

前面我们提到过，在元数据操作中，通过查找操作增加了 dentry 的使用计数，会在结尾处通过 dput() 进行递减。这里我们就来看看 dput() 的机制。

在 dput() 中，处理的步骤如下：

1. 对 dentry -> d_count 递减，如果不为0，就直接返回。
2. 判断具体文件系统是否定义了 d_op -> d_delete 这个接口函数。本地文件系统 Ext2, Ext3 都没有定义这个函数， NFS 定义了这个函数。对于该函数的具体作用我们在后面介绍。既然 Ext2 没有定义，我们就继续往下看。
3. 判断 dentry 是否从 dcache 的哈希链上移除了。（1）如果是，表示该元数据对应的对象已经被删除了，此时可以释放该元数据；（2）如果不是，表示该元数据对应的对象没有被删除，这时把 dentry 挂到 LRU 队列 dentry_unused 上，然后返回。
4. 如果进入释放元数据的那条路径，会释放 dentry 结构和 inode 结构。

其中，释放 inode 结构的调用路径是：

dput() > dentry_iput() > iput() > iput_final()

在 iput() 中，会递减 inode 的使用计数，如果递减完后为0，就进一步调用 iput_final()

iput_final() > generic_drop_inode()

在 generic_drop_inode() 中，会判断 inode -> i_nlink 的值。我们在前面说过， i_nlink 这个域表示 inode 的 hard link 数目，这里就是通过这个域来判断该 inode 能否被删除。

若 inode -> i_nlink 为0，说明没有 hard link 指向该 inode ，可以将其删除，路径为：

generic_drop_inode() > generic_delete_inode() > s_op->delete_inode()

若 inode -> i_nlink 不为0，说明仍有 hard link 指向该 inode ，不能将其删除，路径为：

generic_drop_inode() > generic_forget_inode()

释放 inode 结构的步骤就是这些。释放 dentry 的主要做的事情就是将 dentry与inode 脱离，然后释放 dentry 结构。要注意的是，每当释放了一个 dentry ，都要获取其原来父目录的 dentry ，然后又跳转到 dput() 的开头，继续对父目录的 dentry 进行释放操作。这是因为，前面也提过，每次创建一个 dentry 结构，除了增加自身的使用计数外，还会增加其父目录 dentry 的使用计数。所以当释放了一个 dentry 后也要将其父目录 dentry 使用计数递减，才能保证父目录为空时能够被释放。

unlink 函数

在 dput() 中我们提到过要判断 dentry 是否从 dcache 的哈希链上移除。在本地文件系统中，当删除一个文件时，就会将其对应的 dentry 从 dcache 的哈希链上移除，这是通过 unlink() 来实现。unlink() 的流程如下：

sys_unlink() > do_unlinkat() > 

在do_unlinkat()中，主要可以分为五个部分：

(1) dentry = lookup_hash(&nd);
(2) atomic_inc(&inode->i_count);
(3) vfs_unlink(nd.dentry->d_inode, dentry);
(4) dput(dentry);
(5) iput(inode);	/* truncate the inode here */

可以看出，主体函数 vfs_unlink() 前后，有配对的操作对 dentry 和 inode 进行增减。

我们先看 vfs_unlink() ，其路径为：

vfs_unlink() > d_delete()

在 d_delete() 中，如果 dentry 的使用计数为1，说明此时没有其他人引用该 dentry ，那么就尝试把该 dentry 的 inode 删除，这里调用的是 dentry_iput() ，这个函数已经在 dput() 那部分介绍过了。这个过程的实质就是把 dentry 转为 negative 状态，然后返回。转为 negative 的 dentry 依然在 dcache 的哈希链中，但删除操作已经完成，对应的代码为：

if (atomic_read(&dentry->d_count) == 1) {
    dentry_iput(dentry);
    ...
    return;
}

否则，即 dentry 的使用计数大于1（这里不可能小于1，因为 do_unlinkat() 中调用 lookup_hash() 时已经对 dentry 的使用计数进行了增加），说明有其他人引用该 dentry ，此时不能把这个 dentry 转为 negative ，那么就把这个 dentry 从 dcache 的哈希链中脱离，对应的代码为：

if (!d_unhashed(dentry))
    __d_drop(dentry);

那么什么时候删除这个 dentry 所对应的 inode 呢？大家可以回过头看一下 dput() 介绍过的内容。在 dput() 中，当 dentry 已经从 dcache 的哈希链上移除后，就会继续进行释放元数据的操作。所以只要当最后一个使用 dentry 的操作结束时调用 dput() ，就会调用 dentry_iput() 。

总结一下，删除 inode 必须由 unlink 的 d_delete 发起，如果可能就在 d_delete 中完成删除；否则就 unhash ，然后由最后一个使用者调用 dput() 删除。但只有在 d_delete 完成 unhash 之后， dput 才有可能删除 inode 。

看完主体函数 vfs_unlink() 后，我们关注一下对 inode 使用计数的增减。

在 do_unlinkat() 中，调用 vfs_unlink() 之前，递增了 inode -> i_count ，因此，如果刚进入 do_unlinkat() 时 dentry 的使用计数为1，真正的删除操作并不是在 vfs_unlink() 的 d_delete() 进行，而是在 vfs_unlink() 之后的 iput() 进行（源码里也在 iput() 旁边进行了注释）。

大家也许要问， vfs_unlink() 之后，在 iput() 之前不是还有一个 dput() 吗？那么会不会在这里就删除了 inode 呢？其实不会，我们分三种情况来讨论：

1. 如果 dentry 的使用计数为1，说明没有其他人在使用，则此前 vfs_unlink() 的 d_delete() 必然已经将 dentry 转为 negative ，但没有脱离 dcache 的哈希链，因此不会进行删除（参看 dput() 流程）。删除 inode 的时机是 do_unlinkat() 的 iput() 。
2. 如果 dentry 的使用计数大于1，说明有其他人在使用。若在 do_unlinkat() 调用 dput() 之前，其他使用者都调用了自己的 dput() ，则此时 dentry 的使用计数又变为了1。由于之前 vfs_unlink() 的 d_delete() 已经将 dentry 从哈希链上移除（但也因此没有走到 dentry_iput() 那步，没有递减 inode 的使用计数），因此在 do_unlinkat() 的 dput() 中会走到 dentry_iput() ，但由于 do_unlinkat() 一开始递增了 inode 的使用计数，所以这个 dput() 也不能删除 inode 。删除 inode 的时机仍然是 do_unlinkat() 的 iput() 。
3. 如果 dentry 的使用计数大于1，并且在 do_unlinkat() 调用 dput() 之前，其他使用者没有调用自己的 dput() ，则 do_unlinkat() 调用 dput() 递减了 dentry 的使用计数之后就直接返回了。删除 inode 的时机是其他使用者的 dput() 。

总结一下，这部分的操作比较繁杂，需要结合 dput() 和 unlink 操作一起来看，但理清思路后，也会发现其逻辑还是很清晰的，而这种机制也与使用计数的增加结合得非常好，共同构成了 Linux 文件系统管理内存元数据结构的机制。

分布式文件系统对使用计数机制的扩展

分布式文件系统和本地文件系统有所差别，典型的结构由三部分构成：客户端、元数据服务器、数据服务器。它的一个特点就是允许多客户端的模式，因此有些场景跟单机的模式不大一样。

查找后的 revalidate

前面提到过，在查找操作中，会先到内存去找，如果找不到还要到具体文件系统的磁盘上去取。在分布式环境中，当一个客户端更新了一个文件，从而相应地修改了其元数据，其他客户端并不能马上知道这个更新，于是当查找操作在内存中找到所要的元数据后，会判断一下文件系统是否实现了 d_op -> d_revalidate 这个接口函数，如果实现了，就会再到元数据服务器取一份最新的元数据，从而保证客户端缓存中数据的有效性，这也是这个操作名称叫做 revalidate 的原因。

本地文件系统如 Ext2, Ext3 都没有实现这个接口函数，也没有必要。 NFS 中是有实现的。

前面说过，查找操作会增加 dentry 的使用计数，也就是说不管走了什么路径，只要找到了所需的元数据，那么通过查找操作所返回的 dentry 结构，其使用计数是增加过的。所以具体文件系统的 d_revalidate 函数也要对 dentry 的使用计数进行增加，这样才能和 VFS 层正确衔接起来。

dput 函数的变动

大家是否还记得，前面介绍 dput() 函数时，曾经提到其处理步骤可分为五步，第2步中要判断具体文件系统是否定义了 d_op -> d_delete 这个接口函数。由于 Ext2, Ext3 都没有定义，我们也就跳过了这个判断。然而，在 NFS 中，是有定义这个接口函数的，但没有什么实质内容，基本就是直接返回。其实，是否定义这个函数是一个路口的转向。如果定义了， dput() 的流程就会直接跳转到函数 __d_drop() ，其作用是把 dentry 从哈希链上移除；再接下来就进入 dentry_iput() 尝试删除 inode 。

大家也许会奇怪，前面介绍了 dput() 和 unlink 操作之间那么多复杂的关系，怎么这里直接就都跳过了。这其实是分布式环境的一种解决方法。在分布式环境中，由于有多个客户端，只要有一个客户端进行了删除操作，相应的元数据就应该可以被删除。如果按照本地文件系统的那种机制，此时只有进行了删除操作的客户端才可以通过 dput() 最终走到函数 s_op -> delete_inode() ，从而在元数据服务器端释放元数据；其他客户端由于没有进行删除操作，它们的 dput() 都无法走到 dentry_iput() 那一步，更别说 s_op -> delete_inode() 了。所以在分布式环境中，就采用另一种思路：只要 dentry 的使用计数为1，此时调用 dput() 都可以走到 dentry_iput() ，如果此时 inode 的使用计数也为1，就能继续一直走到 generic_drop_inode() ， generic_drop_inode() 可以继续走到 s_op -> delete_inode() 。这样，元数据服务器就可以自己记录有哪些客户端使用了这个 dentry ，而各个客户端在递减 dentry 的使用计数为0时，都会通过 dput() 与元数据服务器通信。元数据服务器就可以知道某个时刻是否还有客户端在使用这个 dentry ，从而当元数据被删除时决定何时可以进行释放。

这里还有一个问题。前面介绍过， generic_drop_inode() 会根据 inode -> i_nlink 是否为0来判断要调用哪个函数：

若 inode -> i_nlink为0，说明没有 hard link 指向该 inode ，可以将其删除，路径为：

generic_drop_inode() > generic_delete_inode() > s_op->delete_inode()

若 inode->i_nlink 不为0，说明仍有 hard link 指向该 inode ，不能将其删除，路径为：

generic_drop_inode() > generic_forget_inode()

也就是说 generic_drop_inode() 不一定能走到 s_op -> delete_inode() 。而且 inode -> i_nlink 会记录在具体文件系统的磁盘上，它的值是一个全局的值，而不是针对某个客户端的。所以一种解决办法就是不以 s_op -> delete_inode() 作为客户端与元数据服务器的通信接口，而以 s_op -> clear_inode() 作为通信接口。对于 s_op -> clear_inode() ，无论 inode -> i_nlink 的值为多少，都会被调用：

(1) generic_drop_inode() > generic_delete_inode() > s_op->clear_inode()
(2) generic_drop_inode() > generic_forget_inode() > s_op->clear_inode()

总结

通过上面的介绍，我们看到了 Linux 如何对 dentry 和 inode 的使用计数进行操作：何时增加，何时减少。并且了解了元数据操作是如何通过这些使用计数来表明自己正在使用这些元数据的。我们也看到了当删除一个元数据后，如何等到所有使用者都把该元数据的使用计数递减为0之后，才真正对元数据进行释放。最后我们通过分布式文件系统的一些机制了解了在分布式环境下对使用计数的操作要做哪些相应的改变。

参考资料

• 有关源代码，请参考 Linux 内核源码（2.6.20版本）。
  
  
• Tim 的 “Linux 文件系统分析”（developerWorks，2007 年 10 月）向您介绍了 VFS 及其主要结构。Linux VFS 层使用通用的应用程序编程接口为各种受支持的底层文件系统提供了一个抽象层。
  
  
• 在 developerWorks Linux 专区，找到更多针对 Linux 开发人员的资源，并阅览我们的 最流行的文章和教程。
  
  
• 在 developerWorks 上查阅所有 Linux 技巧 和 Linux 教程。
  
  
• 阅读 developWorks 的 所有 Tim 所著的剖析…… 系列文章。

关于作者

		陈撰，目前是中科院计算所的硕士生，主要从事体系结构和文件系统相关的工作，对于文件系统及其容错技术有着浓厚的兴趣。

文档选项 打印本页 将此页作为电子邮件发送 未显示需要 JavaScript 的文档选项

级别： 初级

赵 健博 (zhaojianbo@ncic.ac.cn), 硕士, 中国科学院计算技术研究所

2008 年 9 月 11 日

在 Linux 操作系统中，很多活动都和时间有关，例如：进程调度和网络处理等等。所以说，了解 Linux 操作系统中的时钟处理机制有助于更好地了解 Linux 操作系统的运作方式。本文分析了 Linux 2.6.25 内核的时钟处理机制，首先介绍了在计算机系统中的一些硬件计时器，然后重点介绍了 Linux 操作系统中的硬件时钟和软件时钟的处理过程以及软件时钟的应用。最后对全文进行了总结。

1 计算机系统中的计时器

在计算机系统中存在着许多硬件计时器，例如 Real Timer Clock （ RTC ）、Time Stamp Counter （ TSC ） 和 Programmable Interval Timer （ PIT ） 等等。

这部分内容不是本文的中点，这里仅仅简单介绍几种，更多内容参见参考文献：

• Real Timer Clock （ RTC ）：
  • 独立于整个计算机系统（例如： CPU 和其他 chip ）
  • 内核利用其获取系统当前时间和日期
• Time Stamp Counter （ TSC ）：
  • 从 Pentium 起，提供一个寄存器 TSC，用来累计每一次外部振荡器产生的时钟信号
  • 通过指令 rdtsc 访问这个寄存器
  • 比起 PIT，TSC 可以提供更精确的时间测量
• Programmable Interval Timer （ PIT ）：
  • 时间测量设备
  • 内核使用的产生时钟中断的设备，产生的时钟中断依赖于硬件的体系结构，慢的为 10 ms 一次，快的为 1 ms 一次
• High Precision Event Timer （ HPET ）：
  • PIT 和 RTC 的替代者，和之前的计时器相比，HPET 提供了更高的时钟频率（至少10 MHz ）以及更宽的计数器宽度（64位）
  • 一个 HPET 包括了一个固定频率的数值增加的计数器以及3到32个独立的计时器，这每一个计时器有包涵了一个比较器和一个寄存器（保存一个数值，表示触发中断的时机）。每一个比较器都比较计数器中的数值和寄存器中的数值，当这两个数值相等时，将产生一个中断

回页首

2 硬件时钟处理

这里所说的硬件时钟处理特指的是硬件计时器时钟中断的处理过程。

2.1 数据结构

和硬件计时器（本文又称作硬件时钟，区别于软件时钟）相关的数据结构主要有两个：

• struct clocksource ：对硬件设备的抽象，描述时钟源信息
• struct clock_event_device ：时钟的事件信息，包括当硬件时钟中断发生时要执行那些操作（实际上保存了相应函数的指针）。本文将该结构称作为“时钟事件设备”。

上述两个结构内核源代码中有较详细的注解，分别位于文件 clocksource.h 和 clockchips.h 中。需要特别注意的是结构 clock_event_device 的成员 event_handler ，它指定了当硬件时钟中断发生时，内核应该执行那些操作，也就是真正的时钟中断处理函数。 在2.3节“时钟初始化”部分会介绍它真正指向哪个函数。

Linux 内核维护了两个链表，分别存储了系统中所有时钟源的信息和时钟事件设备的信息。这两个链表的表头在内核中分别是 clocksource_list 和 clockevent_devices 。图2-1显示了这两个链表。

2.2 通知链技术（ notification chain ）

在时钟处理这部分中，内核用到了所谓的“通知链（ notification chain ）”技术。所以在介绍时钟处理过程之前先来了解下“通知链”技术。

在 Linux 内核中，各个子系统之间有很强的相互关系，一些被一个子系统生成或者被探测到的事件，很可能是另一个或者多个子系统感兴趣的，也就是说这个事件的获取者必须能够通知所有对该事件感兴趣的子系统，并且还需要这种通知机制具有一定的通用性。基于这些， Linux 内核引入了“通知链”技术。

2.2.1 数据结构：

通知链有四种类型，

1. 原子通知链（ Atomic notifier chains ）：通知链元素的回调函数（当事件发生时要执行的函数）只能在中断上下文中运行，不允许阻塞
2. 可阻塞通知链（ Blocking notifier chains ）：通知链元素的回调函数在进程上下文中运行，允许阻塞
3. 原始通知链（ Raw notifier chains ）：对通知链元素的回调函数没有任何限制，所有锁和保护机制都由调用者维护
4. SRCU 通知链（ SRCU notifier chains ）：可阻塞通知链的一种变体

所以对应了四种通知链头结构：

• struct atomic_notifier_head ：原子通知链的链头
• struct blocking_notifier_head ：可阻塞通知链的链头
• struct raw_notifier_head ：原始通知链的链头
• struct srcu_notifier_head ： SRCU 通知链的链头

通知链元素的类型：

• struct notifier_block ：通知链中的元素，记录了当发出通知时，应该执行的操作（即回调函数）

链头中保存着指向元素链表的指针。通知链元素结构则保存着回调函数的类型以及优先级，参见 notifier.h 文件。

2.2.2 运作机制

通知链的运作机制包括两个角色：

1. 被通知者：对某一事件感兴趣一方。定义了当事件发生时，相应的处理函数，即回调函数。但需要事先将其注册到通知链中（被通知者注册的动作就是在通知链中增加一项）。
2. 通知者：事件的通知者。当检测到某事件，或者本身产生事件时，通知所有对该事件感兴趣的一方事件发生。他定义了一个通知链，其中保存了每一个被通知者对事件的处理函数（回调函数）。通知这个过程实际上就是遍历通知链中的每一项，然后调用相应的事件处理函数。

包括以下过程：

1. 通知者定义通知链
2. 被通知者向通知链中注册回调函数
3. 当事件发生时，通知者发出通知（执行通知链中所有元素的回调函数）

整个过程可以看作是“发布——订阅”模型（参见参考资料）

被通知者调用 notifier_chain_register 函数注册回调函数，该函数按照优先级将回调函数加入到通知链中 。注销回调函数则使用 notifier_chain_unregister 函数，即将回调函数从通知链中删除。2.2.1节讲述的4种通知链各有相应的注册和注销函数，但是他们最终都是调用上述两个函数完成注册和注销功能的。有兴趣的读者可以自行查阅内核代码。

通知者调用 notifier_call_chain 函数通知事件的到达，这个函数会遍历通知链中所有的元素，然后依次调用每一个的回调函数（即完成通知动作）。2.2.1节讲述的4种通知链也都有其对应的通知函数，这些函数也都是最终调用 notifier_call_chain 函数完成事件的通知。

更多关于通知链的内容，参见参考文献。

由以上的叙述，“通知链”技术可以概括为：事件的被通知者将事件发生时应该执行的操作通过函数指针方式保存在链表（通知链）中，然后当事件发生时通知者依次执行链表中每一个元素的回调函数完成通知。

2.3 时钟初始化

内核初始化部分（ start_kernel 函数）和时钟相关的过程主要有以下几个：

1. tick_init()
2. init_timers()
3. hrtimers_init()
4. time_init()

其中函数 hrtimers_init() 和高精度时钟相关（本文暂不介绍这部分内容）。下面将详细介绍剩下三个函数。

2.3.1 tick_init 函数

函数 tick_init() 很简单，调用 clockevents_register_notifier 函数向 clockevents_chain 通知链注册元素： tick_notifier。这个元素的回调函数指明了当时钟事件设备信息发生变化（例如新加入一个时钟事件设备等等）时，应该执行的操作，该回调函数为 tick_notify （参见2.4节）。

2.3.2 init_timers 函数

注：本文中所有代码均来自于Linux2.6.25 源代码

函数 init_timers() 的实现如清单2-1（省略了部分和

主要功能无关的内容，以后代码同样方式处理）

void __init init_timers(void)
{
    int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE, 
                                        (void *)(long)smp_processor_id());
    ……
    register_cpu_notifier(&timers_nb);
    open_softirq(TIMER_SOFTIRQ,run_timer_softirq, NULL);
}

代码解释：

• 初始化本 CPU 上的软件时钟相关的数据结构，参见3.2节
• 向 cpu_chain 通知链注册元素 timers_nb ，该元素的回调函数用于初始化指定 CPU 上的软件时钟相关的数据结构
• 初始化时钟的软中断处理函数

2.3.3 time_init 函数

函数 time_init 的实现如清单2-2

void __init time_init(void)
{
    ……
    init_tsc_clocksource();
    late_time_init = choose_time_init();
}

函数 init_tsc_clocksource 初始化 tsc 时钟源。choose_time_init 实际是函数 hpet_time_init ，其代码清单2-3

void __init hpet_time_init(void)
{
    if (!hpet_enable())
        setup_pit_timer();

    setup_irq(0, &irq0);
}

函数 hpet_enable 检测系统是否可以使用 hpet 时钟，如果可以则初始化 hpet 时钟。否则初始化 pit 时钟。最后设置硬件时钟发生时的处理函数（参见2.4节）。

初始化硬件时钟这个过程主要包括以下两个过程（参见 hpet_enable 的实现）：

1. 初始化时钟源信息（ struct clocksource 类型的变量），并将其添加到时钟源链表中，即 clocksource_list 链表（参见图2-1）。
2. 初始化时钟事件设备信息（ struct clock_event_device 类型的变量），并向通知链 clockevents_chain 发布通知：一个时钟事件设备要被添加到系统中。在通知（执行回调函数）结束后，该时钟事件设备被添加到时钟事件设备链表中，即 clockevent_devices 链表（参见图2-1）。有关通知链的内容参见2.2节。

需要注意的是在初始化时钟事件设备时，全局变量 global_clock_event 被赋予了相应的值。该变量保存着系统中当前正在使用的时钟事件设备（保存了系统当前使用的硬件时钟中断发生时，要执行的中断处理函数的指针）。

2.4 硬件时钟处理过程

由2.3.3可知硬件时钟中断的处理函数保存在静态变量 irq0 中，其定义如清单2-4

static struct irqaction irq0 = {
	.handler	= timer_event_interrupt,
	.flags		= IRQF_DISABLED | IRQF_IRQPOLL | IRQF_NOBALANCING,
	.mask		= CPU_MASK_NONE,
	.name		= "timer"
};

由定义可知：函数 timer_event_interrupt 为时钟中断处理函数，其定义如清单2-5

static irqreturn_t timer_event_interrupt(int irq, void *dev_id)
{
    add_pda(irq0_irqs, 1);
    global_clock_event->event_handler(global_clock_event);
    return IRQ_HANDLED;
}

从代码中可以看出：函数 timer_event_interrupt 实际上调用的是 global_clock_event 变量的 event_handler 成员。那 event_handler 成员指向哪里呢？

为了说明这个问题，不妨假设系统中使用的是 hpet 时钟。由2.3.3节可知 global_clock_event 指向 hpet 时钟事件设备（ hpet_clockevent ）。查看 hpet_enable 函数的代码并没有发现有对 event_handler 成员的赋值。所以继续查看时钟事件设备加入事件的处理函数 tick_notify ，该函数记录了当时钟事件设备发生变化（例如，新时钟事件设备的加入）时，执行那些操作（参见2.3.1节），代码如清单2-6

static int tick_notify(struct notifier_block *nb, unsigned long reason, void *dev)
{
    switch (reason) {
    case CLOCK_EVT_NOTIFY_ADD:
        return tick_check_new_device(dev);
    ……
    return NOTIFY_OK;
}

由代码可知：对于新加入时钟事件设备这个事件，将会调用函数 tick_check_new_device 。顺着该函数的调用序列向下查找。tick_set_periodic_handler 函数将时钟事件设备的 event_handler 成员赋值为 tick_handle_periodic 函数的地址。由此可知，函数 tick_handle_periodic 为硬件时钟中断发生时，真正的运行函数。

函数 tick_handle_periodic 的处理过程分成了以下两个部分：

1. 全局处理：整个系统中的信息处理
2. 局部处理：局部于本地 CPU 的处理

总结一下，一次时钟中断发生后， OS 主要执行的操作（ tick_handle_periodic ）：

• 全局处理（仅在一个 CPU 上运行）：

1. 更新 jiffies_64
2. 更新 xtimer 和当前时钟源信息等
3. 根据 tick 计算 avenrun 负载

• 局部处理（每个 CPU 都要运行）：
  1. 根据当前在用户态还是核心态，统计当前进程的时间：用户态时间还是核心态时间
  2. 唤醒 TIMER_SOFTIRQ 软中断
  3. 唤醒 RCU 软中断
  4. 调用 scheduler_tick （更新进程时间片等等操作，更多内容参见参考文献）
  5. profile_tick 函数调用

以上就介绍完了硬件时钟的处理过程，下面来看软件时钟。

回页首

3 软件时钟处理

这里所说“软件时钟”指的是软件定时器（ Software Timers ），是一个软件上的概念，是建立在硬件时钟基础之上的。它记录了未来某一时刻要执行的操作（函数），并使得当这一时刻真正到来时，这些操作（函数）能够被按时执行。举个例子说明：它就像生活中的闹铃，给闹铃设定振铃时间（未来的某一时间）后，当时间（相当于硬件时钟）更新到这个振铃时间后，闹铃就会振铃。这个振铃时间好比软件时钟的到期时间，振铃这个动作好比软件时钟到期后要执行的函数，而闹铃时间更新好比硬件时钟的更新。

实现软件时钟原理也比较简单：每一次硬件时钟中断到达时，内核更新的 jiffies ，然后将其和软件时钟的到期时间进行比较。如果 jiffies 等于或者大于软件时钟的到期时间，内核就执行软件时钟指定的函数。

接下来的几节会详细介绍 Linux2.6.25 是怎么实现软件时钟的。

3.1 相关数据结构

• struct timer_list ：软件时钟，记录了软件时钟的到期时间以及到期后要执行的操作。具体的成员以及含义见表3-1。
• struct tvec_base ：用于组织、管理软件时钟的结构。在 SMP 系统中，每个 CPU 有一个。具体的成员以及含义参见表3-2。

注：一个 tick 表示的时间长度为两次硬件时钟中断发生时的时间间隔

表3-2 struct tvec_base 类型的成员

域名	类型	描述
lock	spinlock_t	用于同步操作
running_timer	struct timer_list *	正在处理的软件时钟
timer_jiffies	unsigned long	当前正在处理的软件时钟到期时间
tv1	struct tvec_root	保存了到期时间从 timer_jiffies 到 timer_jiffies + 之间（包括边缘值）的所有软件时钟
tv2	struct tvec	保存了到期时间从 timer_jiffies + 到 timer_jiffies +之间（包括边缘值）的 所有软件时钟
tv3	struct tvec	保存了到期时间从 timer_jiffies +到 timer_jiffies +之间（包括边缘值）的所有软件时钟
tv4	struct tvec	保存了到期时间从 timer_jiffies +到 timer_jiffies +之间（包括边缘值）的所有软件时钟
tv5	struct tvec	保存了到期时间从 timer_jiffies +到 timer_jiffies +之间（包括边缘值）的所有软件时钟

其中 tv1 的类型为 struct tvec_root ，tv 2~ tv 5的类型为 struct tvec ，清单3-1显示它们的定义

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

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

可见它们实际上就是类型为 struct list_head 的数组，其中 TVN_SIZE 和 TVR_SIZE 在系统没有配置宏 CONFIG_BASE_SMALL 时分别被定义为64和256。

3.2 数据结构之间的关系

从图中可以清楚地看出：软件时钟（ struct timer_list ，在图中由 timer 表示）以双向链表（ struct list_head ）的形式，按照它们的到期时间保存相应的桶（ tv1~tv5 ）中。tv1 中保存了相对于 timer_jiffies 下256个 tick 时间内到期的所有软件时钟； tv2 中保存了相对于 timer_jiffies 下256*64个 tick 时间内到期的所有软件时钟； tv3 中保存了相对于 timer_jiffies 下256*64*64个 tick 时间内到期的所有软件时钟； tv4 中保存了相对于 timer_jiffies 下256*64*64*64个 tick 时间内到期的所有软件时钟； tv5 中保存了相对于 timer_jiffies 下256*64*64*64*64个 tick 时间内到期的所有软件时钟。具体的说，从静态的角度看，假设 timer_jiffies 为0，那么 tv1[0] 保存着当前到期（到期时间等于 timer_jiffies ）的软件时钟（需要马上被处理）， tv1[1] 保存着下一个 tick 到达时，到期的所有软件时钟， tv1[n] （0<= n <=255）保存着下 n 个 tick 到达时，到期的所有软件时钟。而 tv2[0] 则保存着下256到511个 tick 之间到期所有软件时钟， tv2[1] 保存着下512到767个 tick 之间到期的所有软件时钟， tv2[n] （0<= n <=63）保存着下256*(n+1)到256*(n+2)-1个 tick 之间到达的所有软件时钟。 tv3~tv5 依次类推。

注：一个tick的长度指的是两次硬件时钟中断发生之间的时间间隔

从上面的说明中可以看出：软件时钟是按照其到期时间相对于当前正在处理的软件时钟的到期时间（ timer_jiffies 的数值）保存在 struct tvec_base 变量中的。而且这个到期时间的最大相对值（到期时间 - timer_jiffies ）为 0xffffffffUL （ tv5 最后一个元素能够表示的相对到期时间的最大值）。

还需要注意的是软件时钟的处理是局部于 CPU 的，所以在 SMP 系统中每一个 CPU 都保存一个类型为 struct tvec_base 的变量，用来组织、管理本 CPU 的软件时钟。从图中也可以看出 struct tvec_base 变量是 per-CPU 的（关于 per-CPU 的变量原理和使用参见参考资料）。

由于以后的讲解经常要提到每个 CPU 相关的 struct tvec_base 变量，所以为了方便，称保存软件时钟的 struct tvec_base 变量为该软件时钟的 base ，或称 CPU 的 base 。

3.3 添加或删除软件时钟

在了解了软件时钟的数据组织关系之后，现在来看一下如何添加以及删除一个软件时钟。

3.3.1 添加软件时钟

在 Linux 内核中要添加一个软件时钟，首先必须分配 struct timer_list 类型的变量，然后调用函数 add_timer() 将该软件时钟添加到相应调用 add_timer 函数的 CPU 的 base 中。 Add_timer 是对函数 __mod_timer() 的一层包装。函数 __mod_timer() 的代码如清单3-2：

int __mod_timer(struct timer_list *timer, unsigned long expires)
{
    struct tvec_base *base, *new_base;
    unsigned long flags;
    int ret = 0;
    ……
    base = lock_timer_base(timer, &flags);
    if (timer_pending(timer)) {
        detach_timer(timer, 0);
        ret = 1;
    }
    new_base = __get_cpu_var(tvec_bases);

    if (base != new_base) {
        if (likely(base->running_timer != timer)) {
            /* See the comment in lock_timer_base() */
            timer_set_base(timer, NULL);
            spin_unlock(&base->lock);
            base = new_base;
            spin_lock(&base->lock);
            timer_set_base(timer, base);
        }
    }
    timer->expires = expires;
    internal_add_timer(base, timer);
    spin_unlock_irqrestore(&base->lock, flags);
    return ret;
}

代码解释：

注：卸载软件时钟的意思是指将软件时钟从软件时钟所在 base 中删除，以后所说的卸载软件时钟也都是这个意思

1. 取得软件时钟所在 base 上的同步锁（ struct tvec_base 变量中的自旋锁），并返回该软件时钟的 base ，保存在 base 变量中
2. 如果该软件时钟处在 pending 状态（在 base 中，准备执行），则卸载该软件时钟
3. 取得本 CPU 上的 base 指针（类型为 struct tvec_base* ），保存在 new_base 中
4. 如果 base 和 new_base 不一样，也就是说软件时钟发生了迁移（从一个 CPU 中移到了另一个 CPU 上），那么如果该软件时钟的处理函数当前没有在迁移之前的那个 CPU 上运行，则先将软件时钟的 base 设置为 NULL ，然后再将该软件时钟的 base 设置为 new_base 。否则，跳到5。
5. 设置软件时钟的到期时间
6. 调用 internal_add_timer 函数将软件时钟添加到软件时钟的 base 中（本 CPU 的 base ）
7. 释放锁

这里有必要详细说明一下软件时钟如何被添加到软件时钟的 base 中的（添加到本 CPU base 的 tv1~tv5 里面），因为这是软件时钟处理的基础。来看函数 internal_add_timer 函数的实现，如清单3-3

static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
{
    unsigned long expires = timer->expires;
    unsigned long idx = expires - base->timer_jiffies;
    struct list_head *vec;
    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) {
        vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
    } else {
        int i;
        if (idx > 0xffffffffUL) {
            idx = 0xffffffffUL;
            expires = idx + base->timer_jiffies;
        }
        i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        vec = base->tv5.vec + i;
    }
    list_add_tail(&timer->entry, vec);
}

代码解释：

• 计算该软件时钟的到期时间和 timer_jiffies （当前正在处理的软件时钟的到期时间）的差值，作为索引保存到 idx 变量中。
• 判断 idx 所在的区间，在
  • [0, ]或者( , 0)（该软件时钟已经到期），则将要添加到 tv1 中
  • [, ]，则将要添加到 tv2 中
  • [, ]，则将要添加到 tv3 中
  • [, ]，则将要添加到 tv4 中
  • [, )，则将要添加到 tv5 中，但实际上最大值为 0xffffffffUL
• 计算所要加入的具体位置（哪个链表中，即 tv1~tv5 的哪个子链表，参考图3-1）
• 最后将其添加到相应的链表中

从这个函数可以得知，内核中是按照软件时钟到期时间的相对值（相对于 timer_jiffies 的值）将软件时钟添加到软件时钟所在的 base 中的。

3.3.2 删除软件时钟

内核可调用 del_timer 函数删除软件时钟， del_timer 的代码如清单3-4

int del_timer(struct timer_list *timer)
{
    struct tvec_base *base;
    unsigned long flags;
    int ret = 0;
    ……
    if (timer_pending(timer)) {
        base = lock_timer_base(timer, &flags);
        if (timer_pending(timer)) {
            detach_timer(timer, 1);
            ret = 1;
        }
        spin_unlock_irqrestore(&base->lock, flags);
    }
    return ret;
}

代码解释：

1. 检测该软件时钟是否处在 pending 状态（在 base 中，准备运行），如果不是则直接函数返回
2. 如果处于 pending 状态，则获得锁
3. 再次检测软件时钟是否处于 pending 状态（该软件时钟可能被卸载了），不是则释放锁然后函数返回
4. 如果还是 pending 状态，则将其卸载，之后释放锁，函数返回

如果在 SMP 系统中，则需使用 del_timer_sync 函数来删除软件时钟。在讲解 del_timer_sync 函数之前，先来看下 try_to_del_timer_sync 函数的实现（该函数被 del_timer_sync 函数使用），其代码如清单3-5

int try_to_del_timer_sync(struct timer_list *timer)
{
    struct tvec_base *base;
    unsigned long flags;
    int ret = -1;
    base = lock_timer_base(timer, &flags);
    if (base->running_timer == timer)
        goto out;
    ret = 0;
    if (timer_pending(timer)) {
        detach_timer(timer, 1);
        ret = 1;
    }
out:
    spin_unlock_irqrestore(&base->lock, flags);
    return ret;
}

该函数检测当前运行的软件时钟是不是该软件时钟，如果是，则函数返回-1，表明目前不能删除该软件时钟；如果不是检测该软件时钟是否处于 pending 状态，如果不是，则函数返回0，表明软件时钟已经被卸载，如果处于 pending 状态再把软件时钟卸载，函数返回1，表明成功卸载该软件时钟。

接下来，再来看看函数 del_timer_sync 定义，如清单3-6

int del_timer_sync(struct timer_list *timer)
{
    for (;;) {
        int ret = try_to_del_timer_sync(timer);
        if (ret >= 0)
            return ret;
        cpu_relax();
    }
}

del_timer_sync 函数无限循环试图卸载该软件时钟，直到该软件时钟能够被成功卸载。从其实现中可以看出：如果一个软件时钟的处理函数正在执行时，对其的卸载操作将会失败。一直等到软件时钟的处理函数运行结束后，卸载操作才会成功。这样避免了在 SMP 系统中一个 CPU 正在执行软件时钟的处理函数，而另一个 CPU 则要将该软件时钟卸载所引发的问题。

3.3 时钟的软中断处理

软件时钟的处理是在时钟的软中断中进行的。

3.3.1 软中断初始化

软中断的一个重要的处理时机是在每个硬件中断处理完成后（参见 irq_exit 函数），且由2.4节的内容可知：在硬件时钟中断处理中，会唤醒时钟的软中断，所以每次硬件时钟中断处理函数执行完成后都要进行时钟的软中断处理。和时钟相关的软中断是 TIMER_SOFTIRQ ，其处理函数为 run_timer_softirq ，该函数用来处理所有的软件时钟。这部分初始化代码在函数 init_timers 中进行，如清单3-7

void __init init_timers(void)
{
    ……
    open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
}

3.3.2 处理过程

函数 run_timer_softirq 所作的工作就是找出所有到期的软件时钟，然后依次执行其处理函数。其代码如清单3-8

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

    hrtimer_run_pending();
    if (time_after_eq(jiffies, base->timer_jiffies))
        __run_timers(base);
}

函数首先获得到本地 CPU 的 base 。然后检测如果 jiffies

注： hrtimer_run_pending() 函数是高精度时钟的处理。本文暂没有涉及高精度时钟相关的内容。

大于等于 timer_jiffies ，说明可能已经有软件时钟到期了，此

时就要进行软件时钟的处理，调用函数 __run_timers 进行处

理。如果 jiffies 小于 timer_jiffies ，表明没有软件时钟到期，

则不用对软件时钟进行处理。函数返回。

接下来看一下函数 __run_timers 都作了些什么，如清单3-9

static inline void __run_timers(struct tvec_base *base)
{
    ……
    spin_lock_irq(&base->lock);
    while (time_after_eq(jiffies, base->timer_jiffies)) {
        ……
        int index = base->timer_jiffies & TVR_MASK;
        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));
        ++base->timer_jiffies;
        list_replace_init(base->tv1.vec + index, &work_list);
        while (!list_empty(head)) {
            ……
            timer = list_first_entry(head, struct timer_list,entry);
            fn = timer->function;
            data = timer->data;
            ……
            set_running_timer(base, timer);
            detach_timer(timer, 1);
            spin_unlock_irq(&base->lock);
            {
                int preempt_count = preempt_count();
                fn(data);
                ……
            }
			spin_lock_irq(&base->lock);
        }
    }
    set_running_timer(base, NULL);
    spin_unlock_irq(&base->lock);
}

代码解释：

1. 获得 base 的同步锁
2. 如果 jiffies 大于等于 timer_jiffies （当前正要处理的软件时钟的到期时间，说明可能有软件时钟到期了），就一直运行3~7，否则跳转至8
3. 计算得到 tv1 的索引，该索引指明当前到期的软件时钟所在 tv1 中的链表（结构参见3.2节），代码：

int index = base->timer_jiffies & TVR_MASK;

1. 调用 cascade 函数对软件时钟进行必要的调整（稍后会介绍调整的过程）
2. 使得 timer_jiffies 的数值增加1
3. 取出相应的软件时钟链表
4. 遍历该链表，对每个元素进行如下操作

• 设置当前软件时钟为 base 中正在运行的软件时钟（即保存当前软件时钟到 base-> running_timer 成员中）
• 将当前软件时钟从链表中删除，即卸载该软件时钟
• 释放锁，执行软件时钟处理程序
• 再次获得锁

1. 设置当前 base 中不存在正在运行的软件时钟
2. 释放锁

3.3.3 软件时钟调整过程

函数 cascade 用于调整软件时钟（这个调整过程是指：将马上就要到期的软件时钟从其所在的链表中删除，重新计算到期时间的相对值（到期时间 - timer_jiffies ），然后根据该值重新插入到 base 中）。注意到在软件时钟处理过程中，每次都是从 tv1 中取出一个链表进行处理，而不是从 tv2~tv5 中取，所以对软件时钟就要进行必要的调整。

在讲解 cascade 函数之前，再从直观上理解下为什么需要进行调整。所有软件时钟都是按照其到期时间的相对值（相对于 timer_jiffies ）被调加到 base 中的。但是 timer_jiffies 的数值都会在处理中增加1（如3.3.2节所示），也就是说这个相对值会随着处理发生变化，当这个相对值小于等于256时，就要将软件时钟从 tv2~tv5 中转移到 tv1 中（ tv1 中保存着下256个 tick 内到期的所有软件时钟）。

函数 cascade 的实现如清单3-10

static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
    struct timer_list *timer, *tmp;
    struct list_head tv_list;
    list_replace_init(tv->vec + index, &tv_list);
    list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
        ……
        internal_add_timer(base, timer);
    }
    return index;
}

该函数根据索引，取出相应的 tv （ tv2~tv5 ）中的链表，然后遍历链表每一个元素。按照其到期时间重新将软件时钟加入到软件时钟的 base 中。该函数返回 tv 中被调整的链表索引值（参见图3-1）。

清单3-9中调整软件时钟的代码如下：

int index = base->timer_jiffies & TVR_MASK;
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再到0时（ index 是对 timer_jiffies 取模），说明时间已经过了256个 tick ，这时要把 tv2 中软件时钟转移到 tv1 中。如果 index 和第一个 cascade 函数的返回值都从0再到到0时，说明时间已经过了256*64个 tick ，这时要把 tv3 中软件时钟转移到 tv1 或者 tv2 中。之后的调整过程依次类推。

3.4 自我激活

软件时钟可分为两种类型：

• 仅仅激活一次
• 激活多次或者周期性激活

多次激活的实现机制就是要在软件时钟处理函数中重新设置软件时钟的到期时间为将来的一个时间，这个过程通过调用 mod_timer 函数来实现。该函数的实现如清单3-11