接收一個網絡包到底會用到多少個隊列?
今天這篇文章，主要嘗試回答下面兩個問題：
- 內核從網卡那里收到一個網絡包，到最終將其所攜帶的payload完整遞交給應用層，中間涉及到多少個隊列?
- 為什么需要這么多各種各樣的隊列呢?
來吧，進入正題。
1. 大圖介紹
照例，先來介紹一下為本文所準備的大圖。這張圖是在之前的文章用圖之上修改而來，主要是添加了在TCP層所涉及到的隊列。據說這叫重復利用。
這張圖用來描繪內核從物理網卡以及虛擬網卡接收到網絡包之后的數據流。
估計你注意到了圖中的 1(1.a、1.b)，2(2.a、2.b、2.c)，3 這樣的標號。對內核而言，1和2是網絡包的接收入口，而3是網絡包的處理入口。
具體來說，1和2表示線路1和線路2，它倆分別代表網絡包從物理網卡進入內核以及從虛擬網卡進入內核所涉及到的一些關鍵操作。標號3表示的是內核線程從這個入口位置獲取待處理網絡設備。
圖中最右邊是TCP/IP協議棧。對于一個skb而言，協議棧對其的處理是在內核線程這個上下文中進行的。了解到這點很重要，我們總得知道到底是誰在替我們負重前行。
圖中的藍色寬箭頭表示網絡包流向用戶態的數據通道。但箭頭在TCP層由實心變成了空心，這是因為對于不同類型的網路包，用戶態所拿到的數據是不一樣的。在TCP層之下的所有層，大家處理的數據結構都是skb。而到了TCP層則需要關心這個skb到底是與握手相關還是與數據包相關。
如你所料，skb穿過鏈路層和IP層的時候，會涉及到bridge-netfilter和netfilter(iptables)所設置的基于規則的過濾過程，還有路由過程。
圖 1：數據接收流程中的隊列鳥瞰圖
我們從左到右，從下至上，順著網絡包流過的路徑，看看沿途中會碰到哪些隊列。
我們說Network namespace用來隔離包括網卡(Network Interface)、回環設備(Loopback Device)、網絡棧、IP地址、端口等等在內的網絡資源。下文所提的各類隊列也是這樣一種被隔離了的資源，所以圖1中所畫的所有這些隊列在不同的network ns中都各有一份。
2. RingBuffer
每個網卡在內存里會有若干個隊列，每個這樣的隊列叫做RingBuffer。顧名思義，它是一個環形緩沖區。當物理網卡收到網絡包，會通過DMA將其拷貝到RingBuffer。當RingBuffer滿的時候，新來的數據包將給丟棄。
這是網絡包碰到的第一個隊列。那么誰負責將這個隊列里面的網絡包消費掉呢?答案是內核線程，也即圖中的ksoftirqd。詳見后文。
3. Per CPU 隊列
每個CPU有一個自己專屬的數據結構softnet_data。其上附有兩個隊列poll_list和input_pkt_queue。這兩個隊列里的內容都由ksoftirqd來消費。圖1中所標示的ksoftirqd/4表示這個內核線程與第4個CPU核綁定在一起，也即它只會處理這個核所擁有的softnet_data上的數據。
3.1 input_pkt_queue
物理網卡由RingBuffer來緩存網絡包，那虛擬網卡要發送出去的數據暫存在哪里呢?如圖1中2.a所示，放在input_pkt_queue這個隊列里。這個過程是在函數enqueue_to_backlog()中完成的。
3.2 poll_list
所有的待處理的網卡會掛到每個CPU專屬的poll_list上。我們可以將poll_list想象成晾曬香腸的架子，而每個網絡設備則如同香腸一樣掛到架子上面等待ksoftirqd處理。
待處理的網卡包括物理網卡和虛擬網卡。簡單地來說，只要需要圖1中的內核線程處理網絡包，就需要將這個網卡掛載到poll_list隊列上。
那么這個掛載動作是由誰完成的呢?
- 對于物理網卡，由中斷服務程序負責將網卡掛到poll_list上。如圖1中步驟1.a所示。
- 對于虛擬網卡，如veth或者lo，則在enqueue_to_backlog()函數中將虛擬網卡掛到poll_list上。如圖1中步驟2.b所示。
到這里，我們已經碰到了三種不同的隊列了，前兩者緩存數據，而后者緩存設備列表。其中RingBuffer和input_pkt_queue隊列都用于緩存網絡包，只是一個服務的對象是物理網卡而另一個則是虛擬網卡。poll_list隊列用于緩存需要內核線程處理的設備。
無論網絡包是位于哪個隊列里，內核線程的啟動意味著網絡包開始進入TCP/IP協議棧。下面我們來看看在協議棧處理過程中用到的隊列有哪幾個。
4. listening socket所用隊列
對于服務器而言，一個典型的架構是 “監聽線程+工作線程池” 組合。下面是偽代碼。
void main(){
int listening_socket = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
// 綁定 ip 和端口
bind(listening_socket, ...);
// 監聽
listen(listening_socket, 3 /*backlog*/);
while(accept_socket = accept(listening_socket)){
// 將accept_socket交給一個worker thread去讀取網絡數據
pthread_t worker_thread;
new_sock = malloc(sizeof(int));
*new_sock = client_sock;
// 創建一個工作線程
if( pthread_create( &worker_thread , NULL , connection_handler , (void*) new_sock) < 0)
{
return 1;
}
...
}
}
這段代碼的骨架挺簡單，主線程為listening thread，用于創建一個listening_socket，并負責基于它來接收客戶端的TCP連接。每一次客戶端與服務器的成功連接都會使得accept()函數返回一個accept_socket，listening thread還會創建一個work thread并讓它基于accept_socket與客戶端通信。
這些work thread匯聚成了一個工作線程池。當然，實際工作的代碼可不會創建無數個work thread，當已創建的work thread數量到達一個閾值后，創建動作就需要轉變成從線程池中提溜一個線程出來這樣的操作。
我將這段代碼中與本文相關的關鍵點列在這里：
- 這段代碼完成了 “監聽線程+工作線程池” 組合這樣的骨架。
- 監聽線程操作的socket是listening_socket。
- 監聽線程針對listening_socket，設置了一個大小為3的backlog。
- 工作線程操作的socket是accept_socket。
在內核中，為每個listening socket 維護了兩個隊列，它們都與連接管理相關。
- 已經建立了連接的隊列，這些連接暫時還沒有被work thread領走。隊列里面的每個連接已經完成了三次握手，且處于ESTABLISHED狀態。這個隊列的名字叫 icsk_accept_queue，如圖1中accept_queue所示 。
- 還沒有完全建立連接的隊列，隊列里面的每個連接還沒有完成三次握手，處于 SYN_REVD 的狀態。這個隊列也叫半連接隊列，syn queue。
示例代碼中，在調用listen()函數的時候，將backlog設置為3。它的作用其實是在控制這個icsk_accept_queue的大小。而syn queue大小則可以通過 /proc/sys/net/ipv4/tcp_max_syn_backlog配置。
服務端調用 accept() 函數，其實是從第一個隊列icsk_accept_queue中拿出一個已經完成的連接進行數據處理。如果這個隊列里是空的，那表示目前還沒有已完成握手的連接，那就把listening thread阻塞等待吧，反正它暫時也沒其它事可做。
5. accept socket所用隊列
每個accept socket包含有4種不同的隊列：backlog隊列、prequeue隊列、sk_receive_queue隊列和out_of_order_queue隊列。
其中prequeue隊列在17年后的Linux版本中已經取消了，故本文略過這個隊列。
5.1 backlog 隊列
當網絡包到達TCP，但是與之相關的accpet socket沒有被用戶態進程讀取中，那么協議棧會調用tcp_add_backlog()將這個網絡包暫存至backlog隊列中。這樣做的目的是讓內核線程可以盡快處理下一個網絡包。
什么情況下會出現accpet socket沒有被用戶態進程讀取呢?比如work thread通過read()讀取到一段數據后便開始直接處理這段數據而耽擱了下一段數據的讀取。
注意這個地方的backlog隊列和前文listening socket處所提及的backlog參數是兩回事。
5.2 sk_receive_queue和out_of_order_queue隊列
當然如果work thread因為調用read()被阻塞了，表示它正在這個accpet socket上急切地等待數據的到來，這個時候協議棧就會把網絡包優先通過函數skb_copy_datagram_msg()直接給它了。但work thread處理能力也有限度，一直給它喂數據也會噎死它，那更多的網絡包就需要sk_receive_queue隊列和out_of_order_queue隊列的幫忙了。
sk_receive_queue隊列的作用很好理解，它里面存放的是按照seq number排好序的數據。但我們都知道跨internet的傳輸會使得網絡包以亂序方式到達，這個時候就需要把這些亂序的包先放到out_of_order_queue隊列排隊了。
應用程序可以讀取到sk_receive_queue隊列和backlog隊列中的內容，但無法直接訪問out_of_order_queue隊列。為了體現這一點，二哥在圖1中特意做了處理：out_of_order_queue隊列沒有出現在通往用戶態的數據通道上。當協議棧發現out_of_order_queue隊列中的亂續包和新到的包可以拼湊成完整有序的數據流后，就將網絡包從out_of_order_queue隊列移動到sk_receive_queue隊列。
5.3 消費隊列
work thread所調用的read()函數在內核態最終通過函數tcp_recvmsg()來讀取暫存在sk_receive_queue中的數據。
每次這個sk_receive_queue隊列中的內容處理完畢后，tcp_recvmsg()還會繼續處理backlog隊列里面累積的網絡包。
6. 為什么需要隊列
行文至此，我們來回答文首的第二個問題：為什么需要這么多各種各樣的隊列呢?
答案是：效率。
把整個面向TCP連接的網絡包接收處理流程稍作總結，我們會發現重要的參與者有如下幾個：
- 網卡，包括物理的和虛擬的網卡：負責接收網絡包。
- 內核線程：消費網絡包，負責調用TCP/IP協議棧函數將亂序到達的網絡包整理還原成data streaming。
- 應用程序：接收、消費data streaming。
網卡和內核線程操作的對象都是網絡包，只是各自關注的焦點不同而已。它們完成自己負責的操作任務后，需要盡快地將網絡包交給繼任者，以便抽身去處理下一個網絡包。遞交網絡包的時候，繼任者可能正在忙，你總不能在那邊傻等對吧?這個時候隊列的出現就起到了很好的緩沖作用。
比如圖1中的內核線程就是這樣，它不斷地從poll_list里面拿出需要處理的網卡并處理網卡里的網絡包。處理好的網絡包送進下文所說的幾個隊列中留待繼任者繼續處理。
我們還可以將所有這些參與者想象成制造業價值流(源于精益原則)中不同的工作中心。在這個價值流中，不同的工作中心之間通常會轉移各自的輸出(半)成品，并通過倉庫來進行一定程度的緩存，倉庫類似本文的隊列。
7. 總結
文末做一個總結。
為了可以高效地處理網絡包，同時又可以讓接收數據的各個重要組成模塊以松耦合的方式合作，各式各樣的隊列參與了網絡包的接收過程。
- RingBuffer和input_pkt_queue最先用于緩存網卡所接收到的網絡包。
- poll_list用于告訴內核線程，當前有哪些網絡設備正在排隊等待它的處理。
- Server端一般用到listening socket和accept socket。
listening socket用于監聽客戶端的連接并負責生成后者，它維護了兩個隊列，分別用于緩存已經握手成功的但還沒有被工作線程領走的連接和還未完成三次握手的連接。
accept socket用于針對具體的連接進行數據通信。它用到了backlog、sk_receive_queue和out_of_order_queue這三個隊列。
文中所用高清大圖已傳至二哥的github：https://github.com/LanceHBZhang/LanceAndCloudnative。
