linux 2.6.28推出了一種通用的ring-buffer實(shí)現(xiàn)觅够，但某些操作這種實(shí)現(xiàn)過(guò)多依賴鎖機(jī)制，導(dǎo)致性能不佳骡苞。目前DPDK使用的ring是基于Steven Rostedt提出的一種無(wú)鎖ring-buffer算法實(shí)現(xiàn)垂蜗，該算法消除了寫入時(shí)鎖依賴坑赡，為內(nèi)核的采集信息功能提供了快路徑，非常高效么抗。我們一起通過(guò)這篇文章學(xué)習(xí)下該算法的實(shí)現(xiàn)原理。
通用算法在linux上的使用如下：采集信息的功能由內(nèi)核來(lái)完成亚铁，因此需要存儲(chǔ)過(guò)程（寫操作）盡可能的耗時(shí)小蝇刀，保證對(duì)處理events的影響盡可能小。讀數(shù)據(jù)都是基于用戶空間完成徘溢，因此對(duì)性能要求相對(duì)低些吞琐。linux內(nèi)核提供的ring-buffer創(chuàng)建了一個(gè)環(huán)形、雙向頁(yè)面列表然爆，包括一個(gè)頭指針和尾指針站粟，寫基于尾指針，讀基于頭指針曾雕。當(dāng)ring-buffer寫滿時(shí)奴烙，有可能writers會(huì)覆蓋頭指針指向的頁(yè)面內(nèi)容，這將會(huì)導(dǎo)致讀操作數(shù)據(jù)異常剖张∏芯鳎基于上述原因，該算法提供一個(gè)獨(dú)立的reader頁(yè)面搔弄，該頁(yè)面完全獨(dú)立于雙向鏈表幅虑，這樣readers就不用擔(dān)心讀數(shù)據(jù)時(shí)會(huì)被writers將數(shù)據(jù)破壞。這種實(shí)現(xiàn)唯一的缺點(diǎn)是當(dāng)一個(gè)reader頁(yè)面處理完需要從鏈表中重新load一個(gè)頁(yè)面時(shí)顾犹，必須要將處理完的空page插到尾指針之后倒庵，同時(shí)將當(dāng)前的head page移除掉作為新的reader page，并將head page在鏈表上向前移動(dòng)炫刷，這個(gè)過(guò)程需要依賴鎖來(lái)保證安全擎宝。
Rostedt的算法中提出的ring-buffer結(jié)構(gòu)如下圖，H代表Header-flagged pointer：
當(dāng)存在多個(gè)writer時(shí)柬唯，writer A可以被其他的writer B打斷认臊，只要A能保證在B開始前完成其寫入動(dòng)作。該功能可有一種稱為interrupts stack機(jī)制來(lái)實(shí)現(xiàn)锄奢，當(dāng)一個(gè)wirter初始化時(shí)失晴，在尾指針之后預(yù)留空間來(lái)處理寫入事件，當(dāng)完成時(shí)更新尾指針位置拘央，同時(shí)引入另一個(gè)指針commit指針涂屁，用來(lái)標(biāo)記 最近的寫入完成指針。在一個(gè)空的ring-buffer中灰伟，reader page\tail page\commit page有可能指向同一處拆又。
為了消除寫過(guò)程的鎖依賴儒旬，提出了 cmpxchg() 原子操作如下：
R = cmpxchg(A, C, B)
- Assign A = B if A == C
- Return A at the time of the call, unconditionally
算法還假設(shè)雙向鏈表的指針是4字節(jié)對(duì)齊，預(yù)留低2bit給flags：
-HEADER --- 指針指向當(dāng)前的head page
-UPDATE --- 指針指向的page正在被寫入數(shù)據(jù)帖族，或者栈源，即將被設(shè)為head page
當(dāng)reader page消費(fèi)完成時(shí)，當(dāng)前的head page需要從ring-buffer中脫落下來(lái)變成新的reader page竖般。通過(guò)在next指針中使用HEADER bit甚垦，readers可以使用cmxchg()來(lái)要求HEADER flag被標(biāo)記，保證頁(yè)面內(nèi)容未被修改過(guò)涣雕。當(dāng)writers將flag設(shè)置為UPDATE或者清除時(shí)艰亮，表示該頁(yè)面內(nèi)容已被修改過(guò)，cmxchg()比較失敗挣郭，這樣reader會(huì)重新查找一個(gè)新的head page迄埃，從而避免使用鎖。
當(dāng)writers更新一個(gè)新的tail page時(shí)兑障，需要檢查next 指針的HEADER flag侄非。如果被設(shè)置，需要更新為UPDATE流译，表示該頁(yè)面正在被writers使用彩库，并會(huì)導(dǎo)致cmpxchg()檢查失敗，需要?jiǎng)冸x一個(gè)新的head page為reader page先蒋。這種狀態(tài)也意味著環(huán)接近寫滿狀態(tài)骇钦，僅剩一個(gè)頁(yè)面用來(lái)寫數(shù)據(jù)。
參考文獻(xiàn)：
