TCP/IP的底層隊列是如何實現的？

自從上次學習了TCP/IP的擁塞控制算法后，我越發想要更加深入的了解TCP/IP的一些底層原理，搜索了很多網絡上的資料，收益頗多。今天就總結一下。

我自己比較了解Java語言，對Java網絡編程的理解就止于Netty框架的使用。 Netty的源碼貢獻者Norman Maurer對于Netty網絡開發有過一句建議，"Never block the event loop, reduce context-swtiching"。也就是盡量不要阻塞IO線程，也盡量減少線程切換。我們今天只關注前半句。

為什么不能阻塞讀取網絡信息的IO線程呢？這里就要從經典的網絡C10K開始理解，服務器如何支持并發1萬請求。C10K的根源在于網絡的IO模型。Linux 中網絡處理都用同步阻塞的方式，也就是每個請求都分配一個進程或者線程，那么要支持1萬并發，難道就要使用1萬個線程處理請求嘛？這1萬個線程的調度、上下文切換乃至它們占用的內存，都會成為瓶頸。解決C10K的通用辦法就是使用I/O 多路復用，Netty就是這樣。

Netty有負責服務端監聽建立連接的線程組(mainReactor)和負責連接讀寫操作的IO線程組(subReactor)，還可以有專門處理業務邏輯的Worker線程組(ThreadPool)。

三者相互獨立，這樣有很多好處。一是有專門的線程組負責監聽和處理網絡連接的建立，可以防止TCP/IP的半連接隊列(sync)和全連接隊列(acceptable)被占滿。二是IO線程組和Worker線程分開，雙方并行處理網絡I/O和業務邏輯，可以避免IO線程被阻塞，防止TCP/IP的接收報文的隊列被占滿。當然，如果業務邏輯較少，也就是IO 密集型的輕計算業務，可以將業務邏輯放在IO線程中處理，避免線程切換，這也就是Norman Maurer話的后半部分。

TCP/IP怎么就這么多隊列啊？今天我們就來細看一下TCP/IP的幾個隊列,包括建立連接時的半連接隊列(sync)，全連接隊列(accept)和接收報文時的receive、outoforder、prequeue以及backlog隊列。

建立連接時的隊列

如上圖所示，這里有兩個隊列：syns queue(半連接隊列)和accept queue(全連接隊列)。三次握手中，服務端接收到客戶端的SYN報文后，把相關信息放到半連接隊列中，同時回復SYN+ACK給客戶端。?第三步的時候服務端收到客戶端的ACK，如果這時全連接隊列沒滿，那么從半連接隊列拿出相關信息放入到全連接隊列中，否則按 tcp_abort_on_overflow的值來執行相關操作，直接拋棄或者過一段時間在重試。

接收報文時的隊列

相比于建立連接，TCP在接收報文時的處理邏輯更為復雜，相關的隊列和涉及的配置參數更多。

應用程序接收TCP報文和程序所在服務器系統接收網絡里發來的TCP報文是兩個獨立流程。二者都會操控socket實例，但是會通過鎖競爭來決定某一時刻由誰來操控，由此產生很多不同的場景。例如，應用程序正在接收報文時，操作系統通過網卡又接收到報文，這時該如何處理？若應用程序沒有調用read或者recv讀取報文時，操作系統收到報文又會如何處理？

我們接下來就以三張圖為主，介紹TCP接收報文時的三種場景，并在其中介紹四個接收相關的隊列。

接收報文場景一

上圖是TCP接收報文場景一的示意圖。操作系統首先接收報文，存儲到socket的receive隊列，然后用戶進程再調用recv進行讀取。

1) 當網卡接收報文并且判斷為TCP協議時，經過層層調用，最終會調用到內核的 tcp_v4_rcv方法。由于當前TCP要接收的下一個報文正是S1，所以 tcp_v4_rcv函數將其直接加入到 receive隊列中。 receive隊列是將已經接收到的TCP報文，去除了TCP頭部、排好序放入的、用戶進程可以直接按序讀取的隊列。由于socket不在用戶進程上下文中（也就是沒有用戶進程在讀socket），并且我們需要S1序號的報文，而恰好收到了S1報文，因此，它進入了 receive隊列。

2) 接收到S3報文，由于TCP要接收的下一個報文序號是S2，所以加入到 out_of_order隊列，所有亂序的報文會放在這里。

3) 接著，收到了TCP期望的S2報文，直接進入 recevie隊列。由于此時 out_of_order隊列不為空，需要檢查一下。

4) 每次向 receive隊列插入報文時都會檢查 out_of_order隊列，由于接收到S2報文后，期望的的序號為S3，所以 out_of_order隊列中的S3報文會被移到 receive隊列。

5) 用戶進程開始讀取socket，先在進程中分配一塊內存，然后調用 read或者 recv方法。socket有一系列的具有默認值的配置屬性，比如socket默認是阻塞式的，它的 SO_RCVLOWAT屬性值默認為1。當然，recv這樣的方法還會接收一個flag參數，它可以設置為 MSG_WAITALL、 MSG_PEEK、 MSG_TRUNK等等，這里我們假定為最常用的0。進程調用了 recv方法。

6) 調用 tcp_recvmsg方法

7) tcp_recvmsg方法會首先鎖住socket。socket是可以被多線程使用的，而且操作系統也會使用，所以必須處理并發問題。要操控socket，就先獲取鎖。

8) 此時， receive隊列已經有3個報文了，將第一個報文拷貝到用戶態內存中，由于第五步中socket的參數并沒有帶 MSG_PEEK，所以將第一個報文從隊列中移除，從內核態釋放掉。反之， MSG_PEEK標志位會導致 receive隊列不會刪除報文。所以， MSG_PEEK主要用于多進程讀取同一套接字的情形。

9) 拷貝第二個報文，當然，執行拷貝前都會檢查用戶態內存的剩余空間是否足以放下當前這個報文，不夠時會直接返回已經拷貝的字節數。

10) 拷貝第三個報文。

11) receive隊列已經為空，此時會檢查 SO_RCVLOWAT這個最小閾值。如果已經拷貝字節數小于它，進程會休眠，等待更多報文。默認的 SO_RCVLOWAT值為1，也就是讀取到報文就可以返回。

12) 檢查 backlog隊列， backlog隊列是用戶進程正在拷貝數據時，網卡收到的報文會進這個隊列。如果此時 backlog隊列有數據，就順帶處理下。 backlog隊列是沒有數據的，因此釋放鎖，準備返回用戶態。

13) 用戶進程代碼開始執行，此時recv等方法返回的就是從內核拷貝的字節數。

接收報文場景二

第二張圖給出了第二個場景，這里涉及了 prequeue隊列。用戶進程調用recv方法時，socket隊列中沒有任何報文，而socket是阻塞的，所以進程睡眠了。然后操作系統收到了報文，此時 prequeue隊列開始產生作用。該場景中， tcp_low_latency為默認的0，套接字socket的 SO_RCVLOWAT是默認的1，仍然是阻塞socket，如下圖。

其中1，2，3步驟的處理和之前一樣。我們直接從第四步開始。

4) 由于此時 receive, prequeue和 backlog隊列都為空，所以沒有拷貝一個字節到用戶內存中。而socket的配置要求至少拷貝 SO_RCVLOWAT也就是1字節的報文，因此進入阻塞式套接字的等待流程。最長等待時間為 SO_RCVTIMEO指定的時間。socket在進入等待前會釋放socket鎖，會使第五步中，新來的報文不再只能進入 backlog隊列。

5) 接到S1報文，將其加入 prequeue隊列中。

6) 插入到 prequeue隊列后，會喚醒在socket上休眠的進程。

7) 用戶進程被喚醒后，重新獲取socket鎖，此后再接收到的報文只能進入 backlog隊列。

8) 進程先檢查 receive隊列，當然仍然是空的；再去檢查 prequeue隊列，發現有報文S1，正好是正在等待序號的報文，于是直接從 prequeue隊列中拷貝到用戶內存，再釋放內核中的這個報文。

9) 目前已經拷貝了一個字節的報文到用戶內存，檢查這個長度是否超過了最低閾值，也就是len和 SO_RCVLOWAT的最小值。

10) 由于 SO_RCVLOWAT使用了默認值1，拷貝字節數大于最低閾值，準備返回用戶態，順便會查看一下backlog隊列中是否有數據，此時沒有，所以準備放回，釋放socket鎖。

11) 返回用戶已經拷貝的字節數。

接收報文場景三

在第三個場景中，系統參數 tcp_low_latency為1，socket上設置了 SO_RCVLOWAT屬性值。服務器先收到報文S1，但是其長度小于 SO_RCVLOWAT。用戶進程調用 recv方法讀取，雖然讀取到了一部分，但是沒有到達最小閾值，所以進程睡眠了。與此同時，在睡眠前接收的亂序的報文S3直接進入 backlog隊列。然后，報文S2到達，由于沒有使用 prequeue隊列（因為設置了tcplowlatency），而它起始序號正是下一個待拷貝的值，所以直接拷貝到用戶內存中，總共拷貝字節數已滿足 SO_RCVLOWAT的要求！最后在返回用戶前把 backlog隊列中S3報文也拷貝給用戶。

1) 接收到報文S1，正是準備接收的報文序號，因此，將它直接加入到有序的 receive隊列中。

2) 將系統屬性 tcp_low_latency設置為1，表明服務器希望程序能夠及時的接收到TCP報文。用戶調用的 recv接收阻塞socket上的報文，該socket的 SO_RCVLOWAT值大于第一個報文的大小，并且用戶分配了足夠大的長度為len的內存。

3) 調用 tcp_recvmsg方法來完成接收工作，先鎖住socket。

4) 準備處理內核各個接收隊列中的報文。

5) receive隊列中有報文可以直接拷貝，其大小小于len，直接拷貝到用戶內存。

6) 在進行第五步的同時，內核又接收到S3報文，此時socket被鎖，報文直接進入backlog隊列。這個報文并不是有序的。

7) 在第五步時，拷貝報文S1到用戶內存，它的大小小于 SO_RCVLOWAT的值。由于socket是阻塞型，所以用戶進程進入睡眠狀態。進入睡眠前，會先處理 backlog隊列的報文。因為S3報文是失序的，所以進入 out_of_order隊列。用戶進程進入休眠狀態前都會先處理一下 backlog隊列。

8) 進程休眠，直到超時或者 receive隊列不為空。

9) 內核接收到報文S2。注意，此時由于打開了 tcp_low_latency標志位，所以報文是不會進入 prequeue隊列等待進程處理。

10) 由于報文S2正是要接收的報文，同時，一個用戶進程在休眠等待該報文，所以直接將報文S2拷貝到用戶內存。

11) 每處理完一個有序報文后，無論是拷貝到 receive隊列還是直接復制到用戶內存，都會檢查 out_of_order隊列，看看是否有報文可以處理。報文S3拷貝到用戶內存，然后喚醒用戶進程。

12) 喚醒用戶進程。

13) 此時會檢查已拷貝的字節數是否大于 SO_RCVLOWAT，以及 backlog隊列是否為空。兩者皆滿足，準備返回。

總結一下四個隊列的作用。

• receive隊列是真正的接收隊列，操作系統收到的TCP數據包經過檢查和處理后，就會保存到這個隊列中。

• backlog是“備用隊列”。當socket處于用戶進程的上下文時（即用戶正在對socket進行系統調用，如recv），操作系統收到數據包時會將數據包保存到?backlog隊列中，然后直接返回。

• prequeue是“預存隊列”。當socket沒有正在被用戶進程使用時，也就是用戶進程調用了read或者recv系統調用，但是進入了睡眠狀態時，操作系統直接將收到的報文保存在?prequeue中，然后返回。

• out_of_order是“亂序隊列”。隊列存儲的是亂序的報文，操作系統收到的報文并不是TCP準備接收的下一個序號的報文，則放入?out_of_order隊列，等待后續處理。