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

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

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

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

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

用法

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

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

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

工作機(jī)制

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

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

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

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

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

出色的KFIFO

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

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

ringbuffer蘊(yùn)藏的巨大能量

消息隊(duì)列

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

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

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

下圖是PDCP和RLC線程的消息隊(duì)列實(shí)例：

內(nèi)存池

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

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

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

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

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

總結(jié)

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