Linux的VFS实现 - 番外[一] - dcache

Linux中的VFS实现 [二]

dcache的构成

dcache中每一项的内容是一个路径到inode的映射关系，其数量众多，通过hash表的形式来管理是很自然的。既然是hash表，那就得有作为"key"的元素，在dentry的数据结构中，是通过类型为"qstr"的"name来充当key值，进而计算出hash表的索引（即"value"）。

struct qstr d_name;

d_hash(dentry->d_name.hash);

static inline struct hlist_bl_head *d_hash(unsigned int hash)
{
     return dentry_hashtable + (hash >> d_hash_shift);
}

如果一个dentry的引用计数（d_lockref.count）变为0，表明其不再被使用，但此时与之关联的inode并不会被立即释放。根据局部性原理，该inode之后还可能会用到，所以这些处于"unused"的状态dentries会被放入一个LRU链表，其所占据的内存在shrink的时候才被回收。

static void d_lru_add(struct dentry *dentry)
{
    dentry->d_flags |= DCACHE_LRU_LIST;
    this_cpu_inc(nr_dentry_unused);
    if (d_is_negative(dentry))
        this_cpu_inc(nr_dentry_negative);
    WARN_ON_ONCE(!list_lru_add(&dentry->d_sb->s_dentry_lru, &dentry->d_lru));
}

只要一个dentry是"cached"状态，那么它指向的inode也会被"cached"，这就构成了inode cache（简称 icache ），icache的每一项内容都是一个已挂载的文件系统中的文件inode。

即便是对应的inode已经被删除，之前的dentry也会以"negative entry"的形式记录在dcache里，这样下次在试图访问这个不存在的路径时，可以立即返回错误，不用再去磁盘瞎折腾一番。

【状态转换】

当创建一个新的dentry时，d_alloc()会为其申请内存空间，而后通过d_add()将这个新的dentry和对应的inode关联起来，并放入dcache的hash表中。

对dentry的使用以dget()和dput()来实现「引用计数」的加减。d_drop()直接将一个dentry从hash表中移除，而d_delete()的目标则是归还inode，并将一个dentry置于"negative"状态。

dcache的查找

当然，在dcache的所有操作里，“查找”是最频繁也最重要的。先来看下有了dcache后，路径查找的过程是怎样的吧。假设现在要打开一个路径为"/a/b/c"的文件，那么首先查看"/a/b/c"是否已经存在于dcache中，没有的话再尝试它的上级目录（即"parent"）是否在dcache中……以此类推（很像 paging structure caches ）。

查找并不涉及对dentry的修改，本质上是一个“读”的过程，但考虑到并行的需要，需要对途径的dentry的引用计数加1，而后再减1，由于涉及到 reference count 值的更新，所以这种方式被称为 "ref-walk" 。

频繁地加减reference count会带来什么问题呢？由于这是一个“写”操作，会刷新cache line，造成cacheline bouncing。此外，这种"ref-walk"的方式还需要持有所操作dentry的 spinlock （即"d_lock"），开销较大。

后来，内核开发者们借鉴RCU的思路，实现了在SMP系统中扩展性更强的 "rcu-walk " 。关于这两种模式在实现上的区别，还是回到代码上来，看看实现"ref-walk"的核心函数 __d_lookup() 和实现"rcu-walk"的 __d_lookup_rcu() 有何差异。

• 首先都是获取hash key和计算hash value，两者采用的方式略有不同，不过这并不是两者的关键差异。

• hash value准备好了，接下来就是遍历hash表的各个slot。这里，"rcu-walk"使用的seqlock，至于它的作用，将在稍后阐释。

一个运行的系统是动态的，在查找目标dentry的这段时间里，其"parent"可能发生了变化，所以需要再次校验。两者在这部分的代码相似度很高，但没有将相同的部分抽取出来聚合成函数，跟据代码中comment的说法，是为了防止"single threaded performance regressions"。

• 再往下走，是hash比对的环节，"ref-walk"不出意料地更新了ref count，而"rcu-walk"进行的则是seqlock中sequence的判断。采用seqlock的逻辑是：在开始RCU walk查找后，相关的目录可能被更改，这种场景下"rcu-walk"往往没法正确地处理，而判断“被更改”的依据就是sequence的变化。

没法处理可怎么办？"rcu-walk"本来就是以“快”取胜，有得必有失，处理不了也不强求，fall back到"ref-walk"的方式继续查找就是。那"ref-walk"也失败呢？说明要找的dentry不在dcache中。这时就只能调用inode的lookup，老老实实地顺着文件系统的directory tree去查找。

其实啊，在当前"ref-walk"的实现中，也能看到RCU的身影，它同样使用了rcu_read_lock()来防止正在使用的dentry被意外释放。而且，在某些context下，"ref-walk"也会用到seqlock，不过目的不同。

试想一下，一个CPU正在查找"/a/b"，然后该路径被其他CPU重命名成了"/a/c/b"，你没法防止这种情况的发生，只能通过seqlock检测出来，放弃之前的查找，再次尝试。因为这个seqlock主要用来处理“重命名”的问题，所以在代码中被命名为"rename_lock"。

从"ref-walk"到"rcu-walk"这一改动涉及到了VFS核心层的变化，因而Linus最初在考虑是否它merge进来的时候也是比较谨慎的。不过他随后做了一个实验，在home目录执行"find . -size"命令（该命令可以查找该目录下所有文件的stat信息），结果显示，改动后的设计将速度提升了35%。面对这么亮眼的数据，谁又能对它说“不”呢（参考这篇文章）。

参考：

• The dentry Cache - Linux Kernel Reference - Halo Linux Services
• Scaling dcache with RCU
• fs: rcu-walk for path lookup

原创文章，转载请注明出处。