HackMD
Linux 核心專題: 並行程式設計相關測驗題
Reviewed by Andrewtangtang
你提到目前是 SPSC 的 ring buffer，那這份程式是怎麼確保 worker 讀到的 socket 是正確的？有用鎖或其他同步機制嗎？如果 producer 很快塞資料，會不會在 consumer 還沒讀之前就被覆寫？
Max042004
此程式不會發生 ABA 問題，因為每一個 ring buffer 為 worker 所擁有，consumer 僅有單一 worker。producer 是唯一的 listener。ring buffer 的單位是 socket 的指標:
struct socket *slot[RING_SIZE]，listener 會在每一次accept後試圖把建立的 socket 放入 ring buffer，而 worker 會試圖從 ring buffer 一次取一個 socket。因此 head 和 tail 的遞增單位皆為 1。所以只需要在每一次放入 socket 前，利用next比對是否已滿，若當下已滿就不再放入新的 socket。
要確保 worker(consumer) 不會錯誤讀取，producer 必須使用 release 確保 socket 已放入後才更新 head 指標，然後 consumer 要使用 acquire 讀取 head 指標。在這份 Linux docs 說明:after an ACQUIRE on a given variable, all memory accesses preceding any prior RELEASE on that same variable are guaranteed to be visible.
所以當 consumer 用 acquire 讀取 head 時，可以保證 release 前一行的
r->slot[head] = s已執行完畢，避免當 consumer 以為 ring buffer 非空但 producer 還沒把 socket 放入的錯誤。要確保 producer 不會覆蓋掉資料，要避免的情況就是指令重排導致當 tail 先更新了，讓 producer 以為有空位，但 consumer 卻還沒將 socket 讀取出來，導致 producer 把未讀取的 socket 覆蓋掉，consumer 因此讀取到覆蓋原有 socket 的新 socket。
因此解決辦法是 tail 的讀取與寫入也使用 release/acquire，consumer 在struct socket *s = r->slot[tail]之後用smp_store_release(tail, (tail + 1) & RING_MASK)，然後 producer 讀取 tail 使用smp_load_acquire(tail)，這樣可以確保 producer 讀取 tail 之前，consumer 已經把 socket 讀取出來。
Reviewed by 'Ian-Yen'
TASK_INTERUPPTIBLE少了一個 R 應為TASK_INTERRUPPTIBLE
Max042004 已更正，謝謝
Reviewed by alexc-313
值得注意的是，
thread_ctx並沒有區分 listener 執行緒 或 worker 執行緒，皆使用相同的封裝。
你認為為何不區分 listener 執行緒 或 worker 執行緒?
另外，注意排版，例如 review 不應該在 TODO 裡面。
TODO: 第 11 週測驗題
測驗題和延伸問題
不要列出參考題解，專注於程式碼和你的洞見
在一般的 ring buffer 實作，會遞增 write 和 read 指標再取餘數使其達到環形的效果，而取餘數運算本身運算成本高，所以把 ring buffer 大小設定為 2 的 10 次方，這樣就能用遮罩達到取餘數的效果。
ring buffer 儲存的是 socket，所以每一個 ring buffer 可存放 1024 個 socket。
觀察 ascii 對照表：
發現小寫英文字母剛好比大寫字母多 32，於是大小寫的轉換能通過 0x00000020 遮罩完成。
kthread_run 用來建立一個核心執行緒，執行 worker 函式。在 kweb_init 將會迴圈呼叫 start_worker 以建立指定數量的 worker 核心執行緒。
核心空間伺服器的好處
在核心空間運行的伺服器可以減少系統呼叫權限切換，使用者空間的資料傳遞的成本。
thread_ctx
整份程式碼主要邏輯包辦在 listener 與 worker、分別作為 SPSC 的生產者和消費者，而這兩個操作對象皆為 thread_ctx。每一個執行緒皆有一個私有的 thread_ctx，包裝各個核心執行緒的資訊。
值得注意的是，thread_ctx 並沒有區分 listener 執行緒 或 worker 執行緒，皆使用相同的封裝。
建立 listener
create_listen 函式用來建立 listener，首先其呼叫核心空間建立 socket 的函式 sock_create_kern，傳入的參數分別是 net namespace, protocol family(PF_INET), communication type (SOCK_STREAM), protocol, new socket，此處傳入 socket 指標的地址，使用間接指標，避免只操作到指標的副本。
若為使用者空間的 socket 可以使用 setsocketopt(2) 設定 socket 的功能，而在 Linux 核心則使用 sock_setsockopt(s, SOL_SOCKET, SO_REUSEADDR, kopt, sizeof(opt));，解讀幾個重要參數，第二個參數 SOL_SOCKET 定義該 sock_setsockopt() 函式的選項變更範圍屬於 socket 層次 (該參數也可設定為 TCP/IP 層次)。當伺服器關閉後兩分鐘內在同一個連接埠和 IP 位址重啟，會得到 "address already in use" 錯誤，因此第三個參數 SO_REUSEADDR 則可以解決此問題。
每一個 TCP 連線，以這五個資料區隔每個連線:
- protocol
- source address
- source port
- destination address
- destination port
每個系統呼叫分別設定了: socket() 設定 protocol，bind() 設定 src addr, src port。connect() 設定 dest addr, dest port。
若要設定伺服器端的 socket，必須經過 socket()，bind()，listen()，然後才能使用 accept() 系統呼叫開始等待連線請求。
若要設定客戶端的 socket，則必須經過 socket()，connect()。
accept(2) v.s kernel_accept()
使用者空間的 accept 系統呼叫的作用與核心空間的 kernel_accept 函式有幾處不同:
- 參數:
觀察第二個參數
accept系統呼叫為struct sockaddr *addr，當連線成功後addr會被設定成客戶的 socket 地址。
kernel_accept為struct socket **newsock，當連線成功後，會建立一個新的 connected socket 並由newsock指向它。 - 返回值:
accept系統呼叫的返回值為connfd，connfd描述的是accept系統呼叫建立的一個新連線的 socket。
kernel_accept返回值為 0 或 error。
此外後續操作對象也不同，對於 accept 系統呼叫，使用者空間裡操作對象為其返回值 connfd，如果要讀取客戶的請求，便 read 這個 connfd。而 kernel_accept 並不返回 fd，在核心空間裡直接操作的對象是傳入的參數，連線中的 socket。
由於 accept 具阻塞的性質，因此在呼叫 accept 前會使用 select(), poll, epoll() 等 Non blocking I/O，確保有客戶試圖連線後再進行 accept，但是，此時要注意有可能在 accept 被呼叫前，發生意外導致網路連線取消，如果此時試圖 accept 會阻塞直到下一次客戶連線前，因此設定 accept 為 O_NONBLOCK 可解決此意外。
worker
handle_cli 的 kernel_recvmsg 用來接收請求內容，然後 parse_http 會解析內容，kernel_sendmsg 用來向客戶端發送回應
接受連線請求的流程
當有客戶端進行連線請求，kernel_accept 便會依上述提及的流程處理連線請求，將新建立的 connected socket 儲存在 cs:
接著將 cs 放入對應的 worker 的 ring buffer，尋找對應的 worker 依循 round-robin 規則。因為 thread_ctx 彼此以陣列擺放，因此 round robin 的實作便是遞增 listener 的 thread_ctx 指標值並取餘數:
假如該 worker 的 ring buffer 已滿，就關閉剛剛建立的新 connected socket，等於此次客戶端的連線請求失敗。
recv/send v.s. read/write
當 recv 的旗標參數設定為 0 時，其行為基本上等同於 read，不過 recv 專門用來接收 socket 傳送過來的資料。同理 send。
這裡則將 recv/send 旗標設定為 MSG_DONTWAIT，因此作用與 read 不同，它使其不會阻塞程式進行，效果與 fcntl(2) 設定 O_NONBLOCK 相同。
除此之外，若 socket 為 NON_BLOCK，也會使 recv 不會阻塞，但差別是 socket 的 NON_BLOCK 屬於 socket 層面，MSG_DONTWAIT 屬於每次 recv/send 呼叫的層面。
順帶一題，因為 socket 結構體中也屬於 struct file，雖專門用 recv, send，但 read/write 也能適用。
適度的休息
接受連線請求採用事件驅動。在 listener 中，以迴圈包覆 vfs_poll 這個非阻塞函式，如果未接收到連線時就會把 listener 執行緒設定為可中斷睡眠，讓出 CPU 資源。
在 worker 中也有相似做法，如果 worker 輪詢每個監控的 socket，但都沒有請求，則 active 維持否，然後設定為可中斷睡眠，那假如有客戶端發送請求讓 active 為是，處理完之後同樣自願排程讓出 CPU 資源，避免 Softlockup:
短時間處理大量請求
對於伺服器而言，能否及時回應外界的連線請求，是衡量伺服器服務品質的指標。在此伺服器接受請求的方法為事件驅動處理
當 accept 後建立一個與客戶端連線的 socket，若要接收來自客戶端的封包，必須呼叫 recv 系列函式，但問題是 recv 和 accept 一樣都是 blocking 函式，因此在客戶端封包抵達前，recv 會一直阻塞程式進行。
因此依靠 vfs_poll 非阻塞式 I/O 監控是否有請求。
效能瓶頸
第一個瓶頸是 listener poll 的效率，就是總機轉接電話的速度，影響回應客戶端連線請求的速度。
在這裡使用的是 vfs_poll 其一次只能查詢一個檔案的讀寫狀態，vfs_poll 是一個封裝過後的 helper 函式，它檢查該 file 是否支援 poll 操作，若有則將 poll 操作轉由 file 各自定義的實作執行。
使用者空間的 select() 和 poll() 等的 I/O multiplexing 底層實作就是藉由 vfs_poll 一次監控一個檔案，然後不斷的迴圈走訪。
務必依循課程規範的術語，見: https://hackmd.io/@sysprog/it-vocabulary
第二個瓶頸是 worker 監控多個客戶端封包請求，因為 poll 需要線性搜索每一個客戶端是否發送封包，因此當 worker 監控的客戶端數量高時，線性搜索的成本成為瓶頸。
而 vfs_poll 呼叫底層的 socket poll tcp_poll。
第三個瓶頸，對於 worker 而言，處理客戶端封包會呼叫 handle_cli。假如連線數量非常多，ring buffer 一下就被塞滿，但 worker 在執行 handle_cli 的時候，造成無法繼續處理連線請求，多餘的就被捨棄變成連線失敗。參考 事件驅動伺服器：原理和實例
可實驗驗證上述猜測，若建立一個 thread pool 給 handle_cli 能否解決。
vfs_poll
在 worker 與 listener 的 vfs_poll 在參數傳遞有所不同:
生產者與消費者問題
在這個程式中，涉及生產者與消費者問題的是傳輸連線的 socket，當 listener accept 後建立連線的 socket，這個 socket 需要由 worker 來監控客戶端傳輸過來的封包，因此 listener 需要把 socket 的位址交給 worker。
每一個 thread 皆有一個 thread_ctx 結構體，其中包含一個 ring buffer，對於每一個 worker thread 而言，這個各自擁有的 ring buffer 存放 listener 建立的連線 socket：
因此在這過程中， listener 扮演單一生產者的角色，而每一個 worker 為單一消費者。為 SPSC 模式。
那考慮另一種實作，若所有的 worker 共用同一個 ring buffer，那就是 SPMC（單一生產者，多個消費者）模式。此情況下需要考慮多個 worker 對共享的 ring buffer 的存取，要做同步處理，比如使用 mutex lock、或是 lock-free 的 atomic CAS。
https://github.com/sysprog21/concurrent-programs?tab=readme-ov-file
struct file 在核心空間與使用者空間的檔案描述子不同，使用者空間的檔案描述子會將檔案封裝，並且幫助行程管理檔案。但核心空間沒有這些機制。
socket 可否做 lseek
VFS 如何更新 open file table?
TODO: 第 8 週測驗題
測驗題和延伸問題
與第 11 周測驗題的 kweb 有多處實作上的差異不同。
- 可用 sysfs 讀寫來控制 server 的啟動與關閉。
- 使用 workqueue 機制，每一個 worker 代表著正處理一個客戶端連線或封包
- 連線的生命週期，每一次回傳封包給客戶端後，該連線 socket 就釋放
因此相比第 11 周測驗題的 kweb，並行性較差
workqueue
workqueue 內的單位是 work item，可被排程
為什麼需要 workqueue，要解決的問題就是 top half, bottom half 議題。
TODO: 第 6 週測驗題
測驗題
1和延伸問題
閱讀 Beej's Guide to Network Programming 第五章提及 getaddrinfo 函式:
其中 node 是網路域名 (或 IP 地址)，service 是 port 號 (或從 /etc/services 裡註冊的服務如 telnet, http, ftp)，hints 是要符合的條件。
getaddrinfo 的作用是返回一系列網路服務的 IP 位址，其域名、埠號、addrinfo 皆符合給定的參數條件，使用目的是增加使用者空間的伺服器更具維護性、可搬移性。使用 getaddrinfo 避免手動初始化 struct sockaddr_in (若要支援 IPv6 則又要初始化 struct sockaddr_in6)。getaddrinfo 會自行把給定的 IP 位址、埠號填入最後一個參數指向的 struct addrinfo，其後建立 socket 時就能直接使用此 struct addrinfo 的資料，因此 getaddrinfo 的用處是讓網路程式獨立於特定的 IP 協定。
以下範例是建立一個伺服器 socket 時使用 getaddrinfo。
hints 僅允許設定 ai_family，ai_socktype，ai_protocol，ai_flags，其中設定 ai_flags 為 AI_PASSIVE，getaddrinfo 第一個參數設定為 NULL，這樣 res 的 ai_addr 就會是 wildcard 位址，告訴核心這個伺服器會接受這個宿主所有 IP 位址的請求，作用跟手動設定 INADDR_ANY 一樣。
假如不使用 getaddrinfo 要達到同樣目的，程式碼會是:
以下另一個範例是客戶端要建立一個連線到伺服器的 socket，使用 getaddrinfo，其作用是返回一系列適合與伺服器連線的 struct addrinfo，因此接下來就是一一走訪每一個 struct addrinfo 直到可以成功建立連線。可以發現程式碼過程沒有涉及任何 IP 協定的 hardcode (比如 IPv4 和 IPv6)，讓這份程式會更有乾淨可攜:
以下則是使用 getaddrinfo 建立 listening socket:
showip.c 為使用 getaddrinfo 的簡單示範程式碼:
getaddrinfo 最後一個參數返回會指向一個儲存 addrinfo 的鏈結串列，假如一個域名可能有多個不同位址的宿主，如 www.youtube.com ，那麼可以走訪這個鏈結串列得到每一個宿主的 IP 位址。
若使用 tracerounte，碰到如 www.youtube.com 時，只會追溯其中一個 IP 位址途經的連線位址。
TODO: 第 10 週測驗題
測驗題
1和延伸問題
