RCU安全引用计数
原文网址：https://lwn.net/Articles/93617
原文作者：Corbet
原文时间：2004年7月14日
内核提供了一种用于实现引用计数的简单机制kref；该机制是今年3月份完成的。kref机制的核心思想是，提供支持原子操作的计数器，用于对未决引用【outstanding references】进行计数。如果计数器数值为零，内核不再需要引用对象了，引用对象可以被释放掉。
kref机制的函数很简单，在引用对象数据结构内直接包含一个struct kref计数器或struct kref *计数器指针，在引用对象被操作之前调用kref_get函数，引用计数器递增。
struct kref *kref_get(struct kref *kref)
{WARN_ON(!atomic_read(&kref->refcount));atomic_inc(&kref->refcount);return kref;
}在对对象操作完成之后调用kref_put函数，引用计数器递减，如果计数器数值为零，就调用回调函数释放引用对象相关资源。
void kref_put(struct kref *kref)
{if (atomic_dec_and_test(&kref->refcount)) {kref->release(kref); //release函数是回调函数}
}对引用计数refcount域进行原子操作，使得上述两个函数可以安全地在多CPU或抢断环境下直接调用，也就是说在这两个环境下，引用计数器的数值总能获得正确的结果。但是，如果两个内核线程在使用kref机制时，存在下面情况，kref机制也会出错。
| 内核线程1 | 内核线程2 |
/* In kref_get() */ WARN_ON(!atomic_read(&kref->refcount)); | |
kref_put(&kref); | |
atomic_inc(&kref->refcount); return kref; |
在上面的例子中，内核线程1在调用atomic_inc之前的那一刻，被引用对象的相关资源很可能被释放掉了。kref代码强制要求：对同一个引用对象不允许kref_get和kref_put并行运行。也就是说，这种强制性要求上述两个函数都需要用锁来避免对同一个引用对象的并行访问。
但是关注高可扩展性的程序员经常会使用免锁算法。因为在线程数量比较大的时候，锁往往会成为性能瓶颈，因此尽可能不用锁，内核的可扩展性会更好。这也是内核提供seqlock和RCU这两种技术的原因。kref机制对锁机制的需求，使得seqlock和RCU很难派上用途。
Ravikiran G Thirumalai最近提交了一份题为“Refcounting of objects part of a lockfree collection”的补丁，实现了一个新的锁机制refcount_t，用于对象的免锁管理。并用大量篇幅介绍了和RCU一起工作时引用计数过程，所有补丁构建了一种类似kref的数据类型，这种数据类型不需要用锁就能避免前面提到的竞争问题。
伴随并行写的过程【as currently written】，kref_get首先检查引用计数数值；如果计数数值为零，表示对象已经被释放了。当前的实现是，检查到数值为零时，仅仅是抱怨一下【我理解为信息输出，而不做更多的处理】；有人可能要说了，这种情况下应该做进一步的处理才好。然而，真正的问题是，对引用计数的测试和递增如果不能在一个原子操作中实现，那么在这两个操作之间就有可能插入其他操作。Ravikiran的补丁通过提供另一个XXXX_get函数来解决这个问题：
static inline int refcount_get_rcu(refcount_t *rc){int c, old;c = atomic_read(&rc->count);while ( c && (old = cmpxchg(&rc->count.counter, c, c+1)) != c) c = old;return c;}上面函数的核心是cmpxchg函数，这是一个内联汇编函数，可以直接使用CPU的cmpxchg指令。这个函数的原型是：
int cmpxchg(int *location, int old, int new);cmpxchg函数实现了以下基本功能：
1）用原子操作实现：比较location内存单元数值和old变量数值；如果两者数值相等，将location内存单元设置为new变量数值。
2）如果上述原子操作成功，即判断两者数值相等后location内存单元被修改，cmpxchg函数返回old变量数值；如果上述原子操作不成功，cmpxchg返回location内存单元的数值。
cmpxchg指令是CPU提供的测试-设置原子指令。用cmpxchg实现的XXXX_get函数在不用锁的情况下就可以实现引用计数器的获取。
这里还是有点小问题。考虑一种情况：内核线程2对引用计数对象释放后又重新使用该对象，然后内核线程1才试图去获取引用计数。在这种情况下，内核线程1可能看到的是一个随机的引用计数，就误以为成功获取了引用计数。引入RCU机制，可以避免这种情况发生。引用对象的释放是通过RCU回调函数来实现；这样一来，引用对象就不会被真正释放直到每一个处理器都发生了调度。只要内核线程能通过指针找到引用对象，那么这个对象就一直存在，即使对象的引用计数数值为零。经过一个完整静默期，没有内核线程去访问这样的指针了，引用对象才会被安全地删除。
另一个潜在的问题是，并不是所有的体系结构都提供cmpxchg原子指令。针对这样的系统，Ravikiran用到了一个从未见过但相当巧妙的方案，用到了自旋锁的哈希数组；如果你们好奇就自己去看补丁好了。
这些努力都是值得的；这个技术已经用于文件描述符查找了，tiobench测试性能提高了13% ~ 21%。内核系统里还有类似kref API一样的对象，也有创建新的引用计数API。因此，补丁还可能会重写。