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

原文作者：Corbet

原文時(shí)間：2004年7月14日

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

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

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

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

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

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

/* 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之前的那一刻，被引用對(duì)象的相關(guān)資源很可能被釋放掉了。kref代碼強(qiáng)制要求：對(duì)同一個(gè)引用對(duì)象不允許kref_get和kref_put并行運(yùn)行。也就是說(shuō)，這種強(qiáng)制性要求上述兩個(gè)函數(shù)都需要用鎖來(lái)避免對(duì)同一個(gè)引用對(duì)象的并行訪問(wèn)。

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

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

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

 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ù)，這是一個(gè)內(nèi)聯(lián)匯編函數(shù)，可以直接使用CPU的cmpxchg指令。這個(gè)函數(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提供的測(cè)試-設(shè)置原子指令。用cmpxchg實(shí)現(xiàn)的XXXX_get函數(shù)在不用鎖的情況下就可以實(shí)現(xiàn)引用計(jì)數(shù)器的獲取。

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

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

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