在網卡領域，多隊列技術已經是一項很常用的技術，而網絡報文的負載分流，常見的就是RSS。本文就索性仔細分析下RSS的邏輯實現，同時以SpinalHDL給出RSS中最為關鍵的Toeplitz Hash的實現。

》RSS(receive side scaling) RSS（receive side scaling）是由微軟提出的一種負載分流方法，通過計算網絡數據報文中的網絡層&傳輸層二/三/四元組HASH值，取HASH值的最低有效位(LSB)用于索引間接尋址表RETA(Redirection Table)，間接尋址表RETA中的保存索引值用于分配數據報文到不同的CPU接收處理。現階段RSS基本已有硬件實現，通過這項技術能夠將網絡流量分載到多個CPU上，降低操作系統單個CPU的占用率。RSS的整體實現如下圖所示:

??RSS Hash計算所采用的Hash算法為Toeplitz Hash。Toeplitz Hash算法定義如下:

function ComputeRssHash(Input[],RSK)
    ret=0;
    for each bit b in Input[] do
        if b==1 then
            ret^=(left-most 32 bit of RSK)
        shift RSK left 1 bit position
    end for

Toeplitz Hash需要一個RSK。在DPDK的實現里，key往往大小為40Byte。結合上述算法，320 bit的RSK對于Toeplitz Hash實現可滿足$320-32+1=289$ bit大小的Input輸入。在DPDK中，存有一張默認的RSK，定義如下:

uint8_t default_rss_key[] = {
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
};

??當然，如果Input位寬大于289 bit，個人有觀察到DPDK代碼中也提供了一張RSK 大表:

static const uint8_t big_rss_key[] = {
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa,
};

??對比可以看到這里的大表是上面40Byte表的復制

》對稱RSS

??采用上面的RSK存在一個問題就是同一個連接的不同方向使用這個默認值計算出來的hash值是不一樣的。具體講就是{src: 1.1.1.1, dst: 2.2.2.2, srcport: 123, dstport: 456}和{src: 2.2.2.2, dst: 1.1.1.1, srcport: 456, dstport: 123} 計算出來的hash值是不一樣的，hash值不一樣就會導致兩個方向的報文被分發到不同的接收隊列，由不同的CPU進行處理。
??在網絡應用中，如果同一個連接的雙向報文在開啟RSS之后被分發到同一個CPU上處理，這種RSS就稱為對稱RSS。對于需要為連接保存一些信息的網絡應用來說，對稱RSS對性能提升有很大幫助。如果同一個連接的雙向報文被分發到不同的CPU，那么兩個CPU之間共享這個連接的信息就會涉及到鎖，而鎖顯然是會影響性能的。
??在DPDK中，提供了一組用于實現對稱RSS的RSK:

static const uint8_t toeplitz_symmetric_key[] = {
0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A,
0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A,
0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A,
0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A,
0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A, 0x6D, 0x5A,
};

??關于對稱RSK是如何推導的，感興趣的小伙伴可以去搜索這篇論文:《Scalable TCP Session monitoring with Symmetric Receive-side Scaling》,這里不做理論上的推導。

》Toeplitz Hash算法實現

??在上面所提到的Toeplitz Hash算法，其無非一個for循環按位進行異或處理。對于熟悉HLS的同學來講或許覺得這個實現是很簡單的。然而HLS并非我的選擇。在for循環里面的if對于邏輯設計而言并非一個友好的實現。上面的算法可以略作修改:

function ComputeRssHash(Input[],RSK)
    ret=0;
    for each bit b in Input[] do
        ret^=(left-most 32 bit of RSK)&{32{b}}
        shift RSK left 1 bit position
    end for

??這個等價改動很簡單，學過數字電路的同學都明白。在最早的文章《= Yes or No》中曾詳細解析過在SpinalHDL中=的用法，那么這里就用得上了。上面的算法在SpinalHDL中也可以很容易的實現:

在SpinalHDL中可以很輕松地實現類似軟件風格的可綜合電路。這就是SpinalHDL這門語言的簡潔優雅之處。 》Toeplitz Hash算法實現進階 ??上面的算法實現可以說是簡單的算法翻譯。Toeplitz Hash算法本質上是一個FG(2)矩陣乘:

??那么該電路可以實現為如下的方式:

??這兩種方式是等價的，其綜合出來的電路也是一致的，至于傾向使用哪種方式，小伙伴們可以自行選擇了。 》RSS hash的邏輯設計 ??對于Toeplitz Hash算法實現，雖然邏輯級數并不高，但如果RSK完全由軟件進行配置，那么消耗的資源還是相對較多的。針對大多數場景，一般只使用對稱RSK或者非對稱RSK，且一般應用中選擇DPDK中指定的RSK，那么在邏輯實現里將RSK給固定下來綜合所使用的邏輯資源就很少了。而針對需要選擇變換對稱RSK或者非對稱RSK的情況，可以選擇在邏輯中制作一個開關用于指定選擇對稱還是非對稱RSK。以上面所提到的DPDK中的兩個KEY為例，邏輯實現如下圖所示:

??值得注意的是,只例化一個ToeplitzHashCal而根據symmetric的值選擇輸入的rsk則消耗的資源相對較多。