最近在研究srsLTE的代碼,其中就發(fā)現(xiàn)一個有意思的數(shù)據(jù)結(jié)構(gòu)------ringbuffer。

雖然，這是一個很基本的數(shù)據(jù)結(jié)構(gòu)，但時，它在LTE這種通信協(xié)議棧系統(tǒng)中卻大行其道，也是很容易被協(xié)議開發(fā)人員忽略的。在整個通信協(xié)議的開發(fā)團(tuán)隊中，一般會有一個平臺中間件的團(tuán)隊，他們的任務(wù)是給業(yè)務(wù)部門提供高性能、高可靠性的中間件代碼，如內(nèi)存池、線程池、消息通信機(jī)制、日志系統(tǒng)等等。這篇文章就來討論下這個簡約而不簡單的ringbuffer。

ringbuffer數(shù)據(jù)結(jié)構(gòu)

環(huán)形緩沖器（ringr buffer），也稱作圓形隊列（circular queue），循環(huán)緩沖區(qū)（cyclic buffer），圓形緩沖區(qū)（circula buffer），是一種用于表示一個固定尺寸、頭尾相連的緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)，適合緩存數(shù)據(jù)流。

在通信程序中，經(jīng)常使用環(huán)形緩沖器作為數(shù)據(jù)結(jié)構(gòu)來存放通信中發(fā)送和接收的數(shù)據(jù)。環(huán)形緩沖區(qū)是一個先進(jìn)先出的循環(huán)緩沖區(qū)，可以向通信程序提供對緩沖區(qū)的互斥訪問。

用法

圓形緩沖區(qū)的一個有用特性是：當(dāng)一個數(shù)據(jù)元素被用掉后，其余數(shù)據(jù)元素不需要移動其存儲位置。相反，一個非圓形緩沖區(qū)（例如一個普通的隊列）在用掉一個數(shù)據(jù)元素后，其余數(shù)據(jù)元素需要向前搬移。換句話說，圓形緩沖區(qū)適合實現(xiàn)先進(jìn)先出緩沖區(qū)，而非圓形緩沖區(qū)適合后進(jìn)先出緩沖區(qū)。

圓形緩沖區(qū)適合于事先明確了緩沖區(qū)的最大容量的情形。擴(kuò)展一個圓形緩沖區(qū)的容量，需要搬移其中的數(shù)據(jù)。因此一個緩沖區(qū)如果需要經(jīng)常調(diào)整其容量，用鏈表實現(xiàn)更為合適。

寫操作覆蓋圓形緩沖區(qū)中未被處理的數(shù)據(jù)在某些情況下是允許的。特別是在多媒體處理時。例如，音頻的生產(chǎn)者可以覆蓋掉聲卡尚未來得及處理的音頻數(shù)據(jù)。

工作機(jī)制

一般的，圓形緩沖區(qū)需要4個指針 ：

• 在內(nèi)存中實際開始位置；
• 在內(nèi)存中實際結(jié)束位置，也可以用緩沖區(qū)長度代替；
• 存儲在緩沖區(qū)中的有效數(shù)據(jù)的開始位置（讀指針）；
• 存儲在緩沖區(qū)中的有效數(shù)據(jù)的結(jié)尾位置（寫指針）。
  讀指針、寫指針可以用整型值來表示。下例為一個未滿的緩沖區(qū)的讀寫指針：

下例為一個滿的緩沖區(qū)的讀寫指針:

區(qū)分緩沖區(qū)滿或者空

緩沖區(qū)是滿、或是空，都有可能出現(xiàn)讀指針與寫指針指向同一位置，有多種策略用于檢測緩沖區(qū)是滿、或是空。常用的做法是總是保持一個存儲單元為空，緩沖區(qū)中總是有一個存儲單元保持未使用狀態(tài)。緩沖區(qū)最多存入 size-1個數(shù)據(jù)。如果讀寫指針指向同一位置，則緩沖區(qū)為空。如果寫指針位于讀指針的相鄰后一個位置，則緩沖區(qū)為滿。這種策略的優(yōu)點是簡單、魯棒；缺點是語義上實際可存數(shù)據(jù)量與緩沖區(qū)容量不一致，測試緩沖區(qū)是否滿需要做取余數(shù)計算。

出色的KFIFO

kfifo是一種"First In First Out “數(shù)據(jù)結(jié)構(gòu)，它采用了前面提到的環(huán)形緩沖區(qū)來實現(xiàn)，提供一個無邊界的字節(jié)流服務(wù)。采用環(huán)形緩沖區(qū)的好處為，當(dāng)一個數(shù)據(jù)元素被用掉后，其余數(shù)據(jù)元素不需要移動其存儲位置，從而減少拷貝提高效率。更重要的是，kfifo采用了并行無鎖技術(shù)，kfifo實現(xiàn)的單生產(chǎn)/單消費模式的共享隊列是不需要加鎖同步的。

熟悉Linux內(nèi)核的讀者應(yīng)該對kfifo.c和kfifo.h并不陌生.kfifo經(jīng)過簡單改進(jìn)就可以在用戶態(tài)進(jìn)行使用，筆者在實際項目中多次使用，經(jīng)過實踐，代碼是穩(wěn)定、可靠、高效的。

ringbuffer蘊藏的巨大能量

消息隊列

ringbuffer的一個天生的高性能的消息隊列，特別是在單生產(chǎn)/單消費的模式下，它是無鎖的，這點非常重要。之前的文章曾介紹過，LTE的協(xié)議棧實現(xiàn)對時序是敏感的，這意味著代碼的執(zhí)行不能有阻塞的風(fēng)險，而線程間的通信幾乎是協(xié)議棧中必須的基本功能。因此，用ringbuffer去實現(xiàn)一個高性能的消息隊列是一種非常理想的方案。當(dāng)然，由于不同的線程的運行模型不同，例如PDCP線程屬于包驅(qū)動的線程，大部分時間它是屬于阻塞的，當(dāng)有數(shù)據(jù)到達(dá)，如RRC可以通過消息隊列給PDCP發(fā)送一個消息，這個時候需要喚醒PDCP進(jìn)行處理，這個是屬于線程同步的技術(shù)范疇，可以通過MUTEX、信號量等方案去實現(xiàn)。如果你的系統(tǒng)的Linux（rt-patch）,eventfd也是不錯的選擇，eventfd優(yōu)勢是可以使用poll、select、epoll等操作，這樣協(xié)議棧的線程實現(xiàn)的方式上較為簡潔，關(guān)鍵是eventfd性能也非常的快。

當(dāng)然這里需要劃一個重點，不同線程間需要獨立的消息隊列，來保證FIFO的無鎖特性，當(dāng)然缺點是會浪費一些內(nèi)容，但是這在協(xié)議棧的開發(fā)中往往不是什么大的問題，性能和穩(wěn)定永遠(yuǎn)是第一位的。由于FIFO通常是固定大小的數(shù)據(jù)結(jié)構(gòu)不太適合可變消息的發(fā)送，這里的技巧是隊列里面只放消息的指針，消息的內(nèi)容通常是在內(nèi)存池中申請不同大小的結(jié)構(gòu)。

srsLTE代碼的實現(xiàn)PDCP和RLC并不一定是以單獨的線程運行的，但是在實際項目中，為了性能的考慮，通常是需要線程化的，且上下行也要線程化，且綁定不同的CPU核，來保證性能。

下圖是PDCP和RLC線程的消息隊列實例：

內(nèi)存池

內(nèi)存池在通信協(xié)議棧和很多的軟件中都是常用的技術(shù)，它的好處是除了可以避免內(nèi)存碎片，更重要的一點是，內(nèi)存是預(yù)先申請的，并且自我管理，在申請和釋放的效率更快，這對協(xié)議棧的實現(xiàn)是十分重要的。

內(nèi)存池的實現(xiàn)在方式都是大同小異的，通常將內(nèi)存分為8字節(jié)、16字節(jié)、32字節(jié)… 1K等大小不同的內(nèi)存塊，并通過鏈表的方式進(jìn)行管理。具體的實現(xiàn)方式可以自行到github上搜索，實現(xiàn)方式都是類似的。

那么，ringbuffer和內(nèi)存池有什么關(guān)系呢？實際上，ringbuffer和內(nèi)存池的實現(xiàn)并無直接的關(guān)系，但是內(nèi)存池在實現(xiàn)上有個至關(guān)重要的問題，那就內(nèi)存的申請和釋放可能不是在同一個線程中。簡單的說就是，內(nèi)存的申請和釋放可能存在競爭的情況，通常的做法是進(jìn)行加鎖進(jìn)行保護(hù)。但是加鎖的操作可能對協(xié)議的時序產(chǎn)生不確定的影響，這對時序要求較高的協(xié)議實現(xiàn)（如CMAC）是無法接受的。

ringbuffer的優(yōu)秀的特性又一次被應(yīng)用的淋漓盡致，做法也是相當(dāng)?shù)暮唵危褪鞘褂胷ingbuffer單生產(chǎn)/單消費的模式的無鎖特性，釋放的線程可以將需要釋放的地址使用ringbuffer發(fā)送給申請的線程，由申請的線程進(jìn)行內(nèi)存的釋放，這就就不需要加鎖的操作，因為同一個線程不會出現(xiàn)并發(fā)的鏈表操作。

下圖是結(jié)合了消息隊列和內(nèi)存池技術(shù)的一次應(yīng)用，該方案是十分經(jīng)典和有效的，在很多大型的通信系統(tǒng)中都能看到這種方案的影子：

總結(jié)

本文是結(jié)合筆者的實際項目經(jīng)驗，介紹了ringbuffer在協(xié)議棧軟件開發(fā)中的一些應(yīng)用和技巧，主要是ringbuffer單生產(chǎn)/單消費的模式的無鎖特性在內(nèi)存池內(nèi)存釋放和消息隊列中的應(yīng)用技巧。如果讀者也有類似的性能方面的系統(tǒng)需求，可以不妨試試 ringbuffer，性能超乎你的想象，且沒有特別復(fù)雜的算法和CPU指令集的限制。