---
tags: LINUX KERNEL
---

# 藉由 spinlock 的調整，改善多核處理器建立 TCP 連線效能

資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
> 本文改寫自 [dog250 的文章](https://blog.csdn.net/dog250/article/details/80575731)，並補充相關資訊

單核處理器的運作時脈已逼近物理極限，於是人們希望藉由多核處理器 (為了行文便利，以下簡稱 SMP) 來提高吞吐量，亦即單位時間內系統能處理的任務總量，概念上貌似單純且合理，但在現實中，工程人員面對極大的挑戰。

1970 年代以來，多數的作業系統並非針對 SMP 特製，因此當它們遇到 SMP 的各種問題時，無一不是東填西補、摸石過河。本文探討 Linux 核心 TCP 通訊協定的可擴展能力 ([scalability](https://en.wikipedia.org/wiki/Scalability)) 議題，描述 Linux 在建立新的 TCP 連線時，針對可擴展能力提出的一系列改進措施。

在 Linux 核心網路通訊協定堆疊 (protocol stack) 的實作中，針對同一個 Listener 的 TCP 新連線處理，主要有以下二個瓶頸：
* 單一的 accept 佇列
* hash table: listener, establish

建立 TCP 新的連線時，會頻繁操作上述二個資料結構，為了確保 SMP 資料的一致性 (consistency)，無可避免要用到 lock，於是無論處理器再多，只要建立新的 TCP 連線時，必然只能循序 (serial) 地操作上述資料結構，當然並行能力就大打折扣。更甚者，lock 衝突也會隨著處理器數量的增長，變得更多！這樣意味著什麼？試想，在捷運車站中，人們從多個入口湧入，最終卻只有一個檢查站 (試想 COVID-19 疫情高峰時期的強制測量體溫措施)，過了這個檢查站又出現多個閘口，會影響整體的效率。

我們可預見，縱使處理器核數增長，效能並未線性增長，一切都是因為 lock。本文著重於如何拆解 lock 的粒度 ([granularity](https://en.wikipedia.org/wiki/Granularity))，後續可搭配 [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability) 研讀。

## 單一 accept 佇列問題的解鎖
這個問題已被 Linux 核心的 [SO_REUSEPORT](https://lwn.net/Articles/542629/) 機制解決。
> One of the features merged in the 3.9 development cycle was TCP and UDP support for the SO_REUSEPORT socket option; that support was implemented in a series of patches by Tom Herbert. The new socket option allows multiple sockets on the same host to bind to the same port, and is intended to improve the performance of multithreaded network server applications running on top of multicore systems.

## listener/establish hash table 的解鎖

短期的 TCP 連線會導致頻繁存取 establish hash table，至於 listener hash 則不必在意，因為 listener socket 比較穩定，不會頻繁產生和銷毀。其中 establish hash table 的效能熱點在以下二個 spinlock：

bool inet_ehash_insert(struct sock *sk, struct sock *osk)
{ 
    struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
    struct hlist_nulls_head *list;
    struct inet_ehash_bucket *head;
    spinlock_t *lock; 
    bool ret = true; 
    
    WARN_ON_ONCE(!sk_unhashed(sk)); 
    
    sk->sk_hash = sk_ehashfn(sk); 
    head = inet_ehash_bucket(hashinfo, sk->sk_hash); 
    list = &head->chain; 
    // 以hash bucket来lock！！ 
    lock = inet_ehash_lockp(hashinfo, sk->sk_hash);

    spin_lock(lock); // 串行化lock 
    if (osk) {
        WARN_ON_ONCE(sk->sk_hash != osk->sk_hash);
        ret = sk_nulls_del_node_init_rcu(osk);
    } 
    if (ret) 
        __sk_nulls_add_node_rcu(sk, list); 
    spin_unlock(lock); 
    return ret; 
}

從程式碼可見，在目前的 Linux TCP 實作中，每個 hash bucket 擁有一個 spinlock，其實粒度已夠細，示意圖如下:

上圖的窘境其實可消弭，只要把 per slot 的 spinlock 再做細分，改為 per slot per CPU 的 spinlock，其實是把每個 slot 的鏈結串列攤開成 per cpu 的即可。這裡決定一個 socket 應該給哪個 CPU 先使用最簡單的策略，即呼叫 `inet_hash` 時，哪個處理器在處理，就分配給該處理器。

為此，我們需要修改下面的資料結構：

struct inet_ehash_bucket {
    struct hlist_nulls_head chain;
};

這個資料結構便是上圖中 slot，我們需要將其改成：

struct inet_ehash_bucket {
    // struct hlist_nulls_head chain[NR_CPUS]
    struct hlist_nulls_head *chain;
};

我們略為修改 `inet_ehash_insert` 函式：

bool inet_ehash_insert(struct sock *sk, struct sock *osk)
{ 
    struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
    struct hlist_nulls_head *list;
    struct inet_ehash_bucket *head;
    spinlock_t *lock;
    bool ret = true; 
    // 取目前的 CPU！ 
    int cpu = smp_processor_id(); 

    WARN_ON_ONCE(!sk_unhashed(sk)); 

    sk->sk_hash = sk_ehashfn(sk); 
    sk->sk_hashcpu = cpu; 
    head = inet_ehash_bucket(hashinfo, sk->sk_hash);
    // 取出對應 CPU 的 list
    head = &head[cpu]; 
    list = &head->chain;
    lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
    // 取出對應 CPU 的 lock
    lock = &lock[cpu]; 
    
    spin_lock(lock);
    if (osk) { 
        WARN_ON_ONCE(sk->sk_hash != osk->sk_hash); 
        ret = sk_nulls_del_node_init_rcu(osk); 
    } 
    if (ret) 
        __sk_nulls_add_node_rcu(sk, list); 
    spin_unlock(lock); 
    return ret; 
}

是不是簡單快捷呢？對應的 lookup 也要修改，在 lookup 的過程中，不再重新檢查 slot 的一致性，而要重新檢驗處理器的一致性：

struct sock *__inet_lookup_established(struct net *net, struct inet_hashinfo *hashinfo,
                                       const __be32 saddr, const __be16 sport, const __be32 daddr,
                                       const u16 hnum, const int dif, const int sdif) {
    INET_ADDR_COOKIE(acookie, saddr, daddr); 
    const __portpair ports = INET_COMBINED_PORTS(sport, hnum);
    struct sock *sk;
    const struct hlist_nulls_node *node; 
    unsigned int hash = inet_ehashfn(net, daddr, hnum, saddr, sport); 
    unsigned int slot = hash & hashinfo->ehash_mask; 
    struct inet_ehash_bucket *head = &hashinfo->ehash[slot]; 
    int cpu = smp_processor_id(), self;
    // 從目前 CPU 開始！如果底層有做 CPU 绑定的话，這樣做就對了。 

    self = cpu;
begin: 
    head = &head[cpu]; 
    if (hlist_nulls_empty(&head->chain)) {
        goto recheck2; 
    }
    sk_nulls_for_each_rcu(sk, node, &head->chain) {
        ... // 邏輯不變，省略 
    } 
    if (get_nulls_value(node) != cpu) {
        cpu = 0;
        goto begin;
    } else if (get_nulls_value(node) == cpu) {
recheck2: 
        cpu ++; 
        if (cpu >= nr_cpu_ids)
            cpu = 0; 
        if (cpu == self) 
            goto out; 
        goto begin; 
    } 
out: 
    sk = NULL; 
found: 
    return sk; 
}

同時，`ehash` 的每個 slot 在初始化時，都要初始化成 per CPU 的操作，並且把 hlist 的尾端，改用 CPU id 來初始化！

於是，採用 per slot per CPU 新方案後，變成以下示意圖:

spinlock 過程中不能發生 context switch (即不可 sleep)，所有的處理器在呼叫 `inet_hash` 時，幾乎都可不用競爭、不自旋地立即完成。但你或許留意到，還沒提及 `inet_unhash` 的呼叫。`unhash` 也要持有 spinlock，如何保證 unhash 的呼叫者和當初 hash 的呼叫者，來自同一個處理器呢？

顯然無法保證！因此正如 `nf_conntrack` 裡 unconfirm list 和 dying list 的 per cpu 處理那般，在呼叫 `unhash` 時，`cpu` 變數必須從 `sk->sk_hashcpu` 裡面取出：

void inet_unhash(struct sock *sk)
{ 
    struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
    spinlock_t *lock;
    bool listener = false;
    int done;

    if (sk_unhashed(sk))         
        return;
    if (sk->sk_state == TCP_LISTEN) { 
        lock = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)].lock;
        listener = true;
    } else { 
        // 取出 hash 時的 cpu，確保從哪裡 insert，就從哪裡 remove，以確保一致性 
        int cpu = sk->sk_hashcpu;
        if (cpu != smp_processor_id()) { 
            DEBUG("Shit!:%d", misstat++); 
    } 
    lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
    lock = &lock[cpu];
    } 
    spin_lock_bh(lock);
    ... 
}

這導致新問題：由於 Linux 排程器的策略影響，很可能呼叫 `unhash` 時的處理器，已不是當初呼叫 hash 時的那個處理器，最終在別的處理器上執行的 `unhash` 過程，還是可能和其它呼叫 hash 過程的處理器競爭同一把鎖。於是，我們所能做的，僅是避免這種情況的發生，例如藉由外部的機制或者工具，對行程和處理器進行綁定，從而避免行程在多個處理器間來回，我們可以利用 `workqueue` 或 `smp_call_function_single` ，從 `sk->sk_hashcpu` 拿到當初插入時的 CPU，然後再安排一個工作到那顆 CPU 上去執行真正的 `inet_unhash`。