RSS的邏輯實(shí)現(xiàn)

在網(wǎng)卡領(lǐng)域，多隊(duì)列技術(shù)已經(jīng)是一項(xiàng)很常用的技術(shù)，而網(wǎng)絡(luò)報(bào)文的負(fù)載分流，常見的就是RSS。本文就索性仔細(xì)分析下RSS的邏輯實(shí)現(xiàn)，同時(shí)以SpinalHDL給出RSS中最為關(guān)鍵的Toeplitz Hash的實(shí)現(xiàn)。

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

??RSS Hash計(jì)算所采用的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需要一個(gè)RSK。在DPDK的實(shí)現(xiàn)里，key往往大小為40Byte。結(jié)合上述算法，320 bit的RSK對(duì)于Toeplitz Hash實(shí)現(xiàn)可滿足$320-32+1=289$ bit大小的Input輸入。在DPDK中，存有一張默認(rèn)的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,
};

??當(dāng)然，如果Input位寬大于289 bit，個(gè)人有觀察到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,
};

??對(duì)比可以看到這里的大表是上面40Byte表的復(fù)制

》對(duì)稱RSS

??采用上面的RSK存在一個(gè)問題就是同一個(gè)連接的不同方向使用這個(gè)默認(rèn)值計(jì)算出來的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} 計(jì)算出來的hash值是不一樣的，hash值不一樣就會(huì)導(dǎo)致兩個(gè)方向的報(bào)文被分發(fā)到不同的接收隊(duì)列，由不同的CPU進(jìn)行處理。
??在網(wǎng)絡(luò)應(yīng)用中，如果同一個(gè)連接的雙向報(bào)文在開啟RSS之后被分發(fā)到同一個(gè)CPU上處理，這種RSS就稱為對(duì)稱RSS。對(duì)于需要為連接保存一些信息的網(wǎng)絡(luò)應(yīng)用來說，對(duì)稱RSS對(duì)性能提升有很大幫助。如果同一個(gè)連接的雙向報(bào)文被分發(fā)到不同的CPU，那么兩個(gè)CPU之間共享這個(gè)連接的信息就會(huì)涉及到鎖，而鎖顯然是會(huì)影響性能的。
??在DPDK中，提供了一組用于實(shí)現(xiàn)對(duì)稱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,
};

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

》Toeplitz Hash算法實(shí)現(xiàn)

??在上面所提到的Toeplitz Hash算法，其無非一個(gè)for循環(huán)按位進(jìn)行異或處理。對(duì)于熟悉HLS的同學(xué)來講或許覺得這個(gè)實(shí)現(xiàn)是很簡(jiǎn)單的。然而HLS并非我的選擇。在for循環(huán)里面的if對(duì)于邏輯設(shè)計(jì)而言并非一個(gè)友好的實(shí)現(xiàn)。上面的算法可以略作修改:

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

??這個(gè)等價(jià)改動(dòng)很簡(jiǎn)單，學(xué)過數(shù)字電路的同學(xué)都明白。在最早的文章《= Yes or No》中曾詳細(xì)解析過在SpinalHDL中=的用法，那么這里就用得上了。上面的算法在SpinalHDL中也可以很容易的實(shí)現(xiàn):

在SpinalHDL中可以很輕松地實(shí)現(xiàn)類似軟件風(fēng)格的可綜合電路。這就是SpinalHDL這門語言的簡(jiǎn)潔優(yōu)雅之處。 》Toeplitz Hash算法實(shí)現(xiàn)進(jìn)階 ??上面的算法實(shí)現(xiàn)可以說是簡(jiǎn)單的算法翻譯。Toeplitz Hash算法本質(zhì)上是一個(gè)FG(2)矩陣乘:

??那么該電路可以實(shí)現(xiàn)為如下的方式:

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

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