原文網(wǎng)址：https://lwn.net/Articles/93617

原文作者：Corbet

原文時間：2004年7月14日

內(nèi)核提供了一種用于實(shí)現(xiàn)引用計數(shù)的簡單機(jī)制kref；該機(jī)制是今年3月份完成的。kref機(jī)制的核心思想是，提供支持原子操作的計數(shù)器，用于對未決引用【outstanding references】進(jìn)行計數(shù)。如果計數(shù)器數(shù)值為零，內(nèi)核不再需要引用對象了，引用對象可以被釋放掉。

kref機(jī)制的函數(shù)很簡單，在引用對象數(shù)據(jù)結(jié)構(gòu)內(nèi)直接包含一個struct kref計數(shù)器或struct kref *計數(shù)器指針，在引用對象被操作之前調(diào)用kref_get函數(shù)，引用計數(shù)器遞增。

struct kref *kref_get(struct kref *kref)
{WARN_ON(!atomic_read(&kref->refcount));atomic_inc(&kref->refcount);return kref;
}

在對對象操作完成之后調(diào)用kref_put函數(shù)，引用計數(shù)器遞減，如果計數(shù)器數(shù)值為零，就調(diào)用回調(diào)函數(shù)釋放引用對象相關(guān)資源。

void kref_put(struct kref *kref)
{if (atomic_dec_and_test(&kref->refcount)) {kref->release(kref);   //release函數(shù)是回調(diào)函數(shù)}
}

對引用計數(shù)refcount域進(jìn)行原子操作，使得上述兩個函數(shù)可以安全地在多CPU或搶斷環(huán)境下直接調(diào)用，也就是說在這兩個環(huán)境下，引用計數(shù)器的數(shù)值總能獲得正確的結(jié)果。但是，如果兩個內(nèi)核線程在使用kref機(jī)制時，存在下面情況，kref機(jī)制也會出錯。

/* In kref_get() */
WARN_ON(!atomic_read(&kref->refcount));

kref_put(&kref);

atomic_inc(&kref->refcount);
return kref;

在上面的例子中，內(nèi)核線程1在調(diào)用atomic_inc之前的那一刻，被引用對象的相關(guān)資源很可能被釋放掉了。kref代碼強(qiáng)制要求：對同一個引用對象不允許kref_get和kref_put并行運(yùn)行。也就是說，這種強(qiáng)制性要求上述兩個函數(shù)都需要用鎖來避免對同一個引用對象的并行訪問。

但是關(guān)注高可擴(kuò)展性的程序員經(jīng)常會使用免鎖算法。因?yàn)樵诰€程數(shù)量比較大的時候，鎖往往會成為性能瓶頸，因此盡可能不用鎖，內(nèi)核的可擴(kuò)展性會更好。這也是內(nèi)核提供seqlock和RCU這兩種技術(shù)的原因。kref機(jī)制對鎖機(jī)制的需求，使得seqlock和RCU很難派上用途。

Ravikiran G Thirumalai最近提交了一份題為“Refcounting of objects part of a lockfree collection”的補(bǔ)丁，實(shí)現(xiàn)了一個新的鎖機(jī)制refcount_t，用于對象的免鎖管理。并用大量篇幅介紹了和RCU一起工作時引用計數(shù)過程，所有補(bǔ)丁構(gòu)建了一種類似kref的數(shù)據(jù)類型，這種數(shù)據(jù)類型不需要用鎖就能避免前面提到的競爭問題。

伴隨并行寫的過程【as currently written】，kref_get首先檢查引用計數(shù)數(shù)值；如果計數(shù)數(shù)值為零，表示對象已經(jīng)被釋放了。當(dāng)前的實(shí)現(xiàn)是，檢查到數(shù)值為零時，僅僅是抱怨一下【我理解為信息輸出，而不做更多的處理】；有人可能要說了，這種情況下應(yīng)該做進(jìn)一步的處理才好。然而，真正的問題是，對引用計數(shù)的測試和遞增如果不能在一個原子操作中實(shí)現(xiàn)，那么在這兩個操作之間就有可能插入其他操作。Ravikiran的補(bǔ)丁通過提供另一個XXXX_get函數(shù)來解決這個問題：

 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;}

上面函數(shù)的核心是cmpxchg函數(shù)，這是一個內(nèi)聯(lián)匯編函數(shù)，可以直接使用CPU的cmpxchg指令。這個函數(shù)的原型是：

int cmpxchg(int *location, int old, int new);

cmpxchg函數(shù)實(shí)現(xiàn)了以下基本功能：

1）用原子操作實(shí)現(xiàn)：比較location內(nèi)存單元數(shù)值和old變量數(shù)值；如果兩者數(shù)值相等，將location內(nèi)存單元設(shè)置為new變量數(shù)值。

2）如果上述原子操作成功，即判斷兩者數(shù)值相等后location內(nèi)存單元被修改，cmpxchg函數(shù)返回old變量數(shù)值；如果上述原子操作不成功，cmpxchg返回location內(nèi)存單元的數(shù)值。

cmpxchg指令是CPU提供的測試-設(shè)置原子指令。用cmpxchg實(shí)現(xiàn)的XXXX_get函數(shù)在不用鎖的情況下就可以實(shí)現(xiàn)引用計數(shù)器的獲取。

這里還是有點(diǎn)小問題?？紤]一種情況：內(nèi)核線程2對引用計數(shù)對象釋放后又重新使用該對象，然后內(nèi)核線程1才試圖去獲取引用計數(shù)。在這種情況下，內(nèi)核線程1可能看到的是一個隨機(jī)的引用計數(shù)，就誤以為成功獲取了引用計數(shù)。引入RCU機(jī)制，可以避免這種情況發(fā)生。引用對象的釋放是通過RCU回調(diào)函數(shù)來實(shí)現(xiàn)；這樣一來，引用對象就不會被真正釋放直到每一個處理器都發(fā)生了調(diào)度。只要內(nèi)核線程能通過指針找到引用對象，那么這個對象就一直存在，即使對象的引用計數(shù)數(shù)值為零。經(jīng)過一個完整靜默期，沒有內(nèi)核線程去訪問這樣的指針了，引用對象才會被安全地刪除。

另一個潛在的問題是，并不是所有的體系結(jié)構(gòu)都提供cmpxchg原子指令。針對這樣的系統(tǒng)，Ravikiran用到了一個從未見過但相當(dāng)巧妙的方案，用到了自旋鎖的哈希數(shù)組；如果你們好奇就自己去看補(bǔ)丁好了。

這些努力都是值得的；這個技術(shù)已經(jīng)用于文件描述符查找了，tiobench測試性能提高了13% ~ 21%。內(nèi)核系統(tǒng)里還有類似kref API一樣的對象，也有創(chuàng)建新的引用計數(shù)API。因此，補(bǔ)丁還可能會重寫。