perfbook 读书笔记：livelock
注：本文以及后面的文章中提到的 perfbook 均是指大牛 Paul E. McKenney 的书，《Is Parallel Programming Hard, And, If So, What Can You Do About It?》，书名太长，故简写之。
最近一直在读这本 perfbook，它算是少有的全面而专门介绍 locking 的书，值得每个系统程序员去读。在读的过程中发现有的地方它介绍的并不是很详细，所以就写几篇读书笔记也算是对它的小小补充。
书中 6.1.2 节讲到了 livelock，即所谓的“活锁”，相对于死锁（deadlock）而言。因为上过操作系统课的原因，我估计很多人对 deadlock 并不陌生，但是 livelock 相对不那么熟悉。livelock 无非是饥饿（starvation）的极端情况。饥饿是由竞争引起，所谓竞争（contention）是指尝试获取一个已经被锁住的锁，长时间竞争会导致这些得不到锁的进程饥饿，所以饥饿的极端情况就是多个进程一直在尝试获取某一（几）把锁，但一直都得不到满足。
书中给出的例子很简单，解决方法是给两个进程加上不同延迟，也同时增加了 overhead，所以这个例子并不是很好。我们看一个现实中的例子，Linux 内核中的一个 livelock 的 bug：
commit eaf5f9073533cde21c7121c136f1c3f072d9cf59
Author: Miklos Szeredi
Date: Tue Jan 10 18:22:25 2012 +0100fix shrink_dcache_parent() livelock
发生 livelock 的地方是 shrink_dcache_parent()，看其定义：
[c]
void shrink_dcache_parent(struct dentry * parent)
{
LIST_HEAD(dispose);
int found;
while ((found = select_parent(parent, &dispose)) != 0)
shrink_dentry_list(&dispose);
}
[/c]
根据这个 commit 的描述，我们可以发现存在下面这种情况：
1. CPU0 上的进程调用 select_parent(P) 找到了 dentry C，并把它放入 dispose 链表中，返回1；
2. 与此同时，CPU1 上的另一个进程也调用了select_parent(P)，获取了 dentry P 的 ->d_lock；
3. CPU0 上的进程继续调用 shrink_dentry_list()，获取了 dentry C 的 ->d_lock，然后又调用 try_prune_one_dentry(C)，dentry_kill(C)：
[c]
…
if (inode && !spin_trylock(&inode->i_lock)) {
relock:
spin_unlock(&dentry->d_lock);
cpu_relax();
return dentry; / try again with same dentry /
}
if (IS_ROOT(dentry))
parent = NULL;
else
parent = dentry->d_parent;
if (parent && !spin_trylock(&parent->d_lock)) {
if (inode)
spin_unlock(&inode->i_lock);
goto relock;
}
[/c]
因为另一个进程持有dentry P的->d_lock，所以 dentry_kill() 中 spin_trylock(&parent->d_lock) 失败，转而 spin_unlock(&dentry->d_lock) 并返回；
4. CPU1 上的进程此时仍在调用 select_parent(P)，并找到了 dentry C，锁住了它的->d_lock，放入 dispose 链表并返回1（其实就是重复步骤(1)）；
5. CPU0 上的进程继续 shrink_dentry_list() 中的循环，发现 dispose 链表已经为空，退出循环并返回；
6. CPU1 的进程开始重复步骤(3)；
7. CPU0 的进程开始重复步骤(2)。
Livelock 产生了！
这里问题的关键在于那个 dispose list，如果 dentry C被某个进程加入到 dispose list 中，另外的进程不应该再找到它，所以修复就是加一个标志位 DCACHE_SHRINK_LIST，来标示这个 dentry 有没有被加入。