linux 2.6.28推出了一種通用的ring-buffer實現(xiàn)，但某些操作這種實現(xiàn)過多依賴鎖機制，導(dǎo)致性能不佳。目前DPDK使用的ring是基于Steven Rostedt提出的一種無鎖ring-buffer算法實現(xiàn)，該算法消除了寫入時鎖依賴，為內(nèi)核的采集信息功能提供了快路徑，非常高效。我們一起通過這篇文章學(xué)習(xí)下該算法的實現(xiàn)原理。
通用算法在linux上的使用如下：采集信息的功能由內(nèi)核來完成，因此需要存儲過程（寫操作）盡可能的耗時小，保證對處理events的影響盡可能小。讀數(shù)據(jù)都是基于用戶空間完成，因此對性能要求相對低些。linux內(nèi)核提供的ring-buffer創(chuàng)建了一個環(huán)形、雙向頁面列表，包括一個頭指針和尾指針，寫基于尾指針，讀基于頭指針。當ring-buffer寫滿時，有可能writers會覆蓋頭指針指向的頁面內(nèi)容，這將會導(dǎo)致讀操作數(shù)據(jù)異常?；谏鲜鲈?，該算法提供一個獨立的reader頁面，該頁面完全獨立于雙向鏈表，這樣readers就不用擔心讀數(shù)據(jù)時會被writers將數(shù)據(jù)破壞。這種實現(xiàn)唯一的缺點是當一個reader頁面處理完需要從鏈表中重新load一個頁面時，必須要將處理完的空page插到尾指針之后，同時將當前的head page移除掉作為新的reader page，并將head page在鏈表上向前移動，這個過程需要依賴鎖來保證安全。
Rostedt的算法中提出的ring-buffer結(jié)構(gòu)如下圖，H代表Header-flagged pointer：
當存在多個writer時，writer A可以被其他的writer B打斷，只要A能保證在B開始前完成其寫入動作。該功能可有一種稱為interrupts stack機制來實現(xiàn)，當一個wirter初始化時，在尾指針之后預(yù)留空間來處理寫入事件，當完成時更新尾指針位置，同時引入另一個指針commit指針，用來標記 最近的寫入完成指針。在一個空的ring-buffer中，reader page\tail page\commit page有可能指向同一處。
為了消除寫過程的鎖依賴，提出了 cmpxchg() 原子操作如下：
R = cmpxchg(A, C, B)
- Assign A = B if A == C
- Return A at the time of the call, unconditionally
算法還假設(shè)雙向鏈表的指針是4字節(jié)對齊，預(yù)留低2bit給flags：
-HEADER --- 指針指向當前的head page
-UPDATE --- 指針指向的page正在被寫入數(shù)據(jù)，或者，即將被設(shè)為head page
當reader page消費完成時，當前的head page需要從ring-buffer中脫落下來變成新的reader page。通過在next指針中使用HEADER bit，readers可以使用cmxchg()來要求HEADER flag被標記，保證頁面內(nèi)容未被修改過。當writers將flag設(shè)置為UPDATE或者清除時，表示該頁面內(nèi)容已被修改過，cmxchg()比較失敗，這樣reader會重新查找一個新的head page，從而避免使用鎖。
當writers更新一個新的tail page時，需要檢查next 指針的HEADER flag。如果被設(shè)置，需要更新為UPDATE，表示該頁面正在被writers使用，并會導(dǎo)致cmpxchg()檢查失敗，需要剝離一個新的head page為reader page。這種狀態(tài)也意味著環(huán)接近寫滿狀態(tài)，僅剩一個頁面用來寫數(shù)據(jù)。
參考文獻：
