最近在研究srsLTE的代碼,其中就發現一個有意思的數據結構------ringbuffer。

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

ringbuffer數據結構

環形緩沖器（ringr buffer），也稱作圓形隊列（circular queue），循環緩沖區（cyclic buffer），圓形緩沖區（circula buffer），是一種用于表示一個固定尺寸、頭尾相連的緩沖區的數據結構，適合緩存數據流。

在通信程序中，經常使用環形緩沖器作為數據結構來存放通信中發送和接收的數據。環形緩沖區是一個先進先出的循環緩沖區，可以向通信程序提供對緩沖區的互斥訪問。

用法

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

圓形緩沖區適合于事先明確了緩沖區的最大容量的情形。擴展一個圓形緩沖區的容量，需要搬移其中的數據。因此一個緩沖區如果需要經常調整其容量，用鏈表實現更為合適。

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

工作機制

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

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

下例為一個滿的緩沖區的讀寫指針:

區分緩沖區滿或者空

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

出色的KFIFO

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

熟悉Linux內核的讀者應該對kfifo.c和kfifo.h并不陌生.kfifo經過簡單改進就可以在用戶態進行使用，筆者在實際項目中多次使用，經過實踐，代碼是穩定、可靠、高效的。

ringbuffer蘊藏的巨大能量

消息隊列

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

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

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

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

內存池

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

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

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

ringbuffer的優秀的特性又一次被應用的淋漓盡致，做法也是相當的簡單，就是使用ringbuffer單生產/單消費的模式的無鎖特性，釋放的線程可以將需要釋放的地址使用ringbuffer發送給申請的線程，由申請的線程進行內存的釋放，這就就不需要加鎖的操作，因為同一個線程不會出現并發的鏈表操作。

下圖是結合了消息隊列和內存池技術的一次應用，該方案是十分經典和有效的，在很多大型的通信系統中都能看到這種方案的影子：

總結

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