積雲が映像制作したMV『RANGEFINDER』公開中
専門88IO

【C言語】L4チェックサム計算選手権

専門

TCPやUDPといったL4プロトコルのチェックサム計算量を比較したくなったので、複数の方法で実装して評価を行った。

以前の記事では

チェックサムは該当データを2バイトごとに加算した後に論理否定を取ったもの

と書いたが、チェックサムは1の補数和で計算するので結果がバイトオーダーに依存しない。そのため、32bitや64bit単位で加算して最終的に16bitまで集約する方針も取れる。

スポンサーリンク

計算手法

合計9つの手法で計算を行った。ソースコードはGitHub参照。

GitHub - 88IO/dpdk-l4-checksum: DPDKプロキシを用いたL4チェックサム計算時間の計測
DPDKプロキシを用いたL4チェックサム計算時間の計測. Contribute to 88IO/dpdk-l4-checksum development by creating an account on GitHub.

ADD16, ADD32, ADD64

1の補数和を求める関数を用い、16bit・32bit・64bit単位で加算した。

static inline uint16_t 
csum16_add(uint16_t a, uint16_t b) {
    a += b;
    return a + (a < b);
}

加算結果からオーバーフローを検知して追加で足し合わせる。

SUB16, SUB32, SUB64

上記の手法では、加算結果を用いてオーバーフローを検知するため実行順序に依存関係がある。

そこで、1の補数差を求める関数を用いる。

static inline uint16_t 
csum16_sub(uint16_t a, uint16_t b) {
    return a - b - (a < b);
}

この計算では引数に取る値でオーバーフローを検知できる。しかし、減算処理であるため引く数に論理否定を取る必要がある。

csum16_add(a, b) == csum16_sub(a, ~b)

ADD16AS32, ADD32AS64

上記の手法では、加算または減算毎にオーバーフローを検知して補正する必要があった。これは16bitの加算結果を16bit変数に格納するためオーバーフロー分の情報を保持できないためである。

そこで、16bitの加算結果を32bit変数に格納することでオーバーフロー検知分の計算量を削減する。

uint16_t *pos = tcph;
uint16_t *end = pos + l4_len / sizeof(uint16_t);
for (; pos != end; pos++)
    csum += *pos;

最終的にチェックサムフィールドの16bitに収めるため、補数和の関数を用いて集約を行う。

static inline uint16_t 
csum32_add_fold(uint32_t a) {
    return csum16_add(a >> 16, a & 0xFFFF);
}

RTE_DEFAULT

参考記録としてDPDKのL4チェックサム計算の関数rte_ipv4_udptcp_cksumを用いる。内部実装はADD16AS32に類似している。

スポンサーリンク

比較評価

DPDKでフォワーディングアプリケーションを作成し、struct timespecで時間計測を行った。パケット生成にはpktgenを用いた。

1,000万パケットを受信、L4チェックサム計算時間の平均を載せる。

図より、数値型のサイズが大きいほど加算回数が減少するため実行時間は短い。

  • ADD64 < ADD32 < ADD16
  • SUB64 < SUB32 < SUB16
  • ADD32AS64 < ADD16AS32

また、明示的に並列処理を行っていないため減算は加算より遅くなった。

  • ADD16 < SUB16

ADD32AS64が最速、続いてADD64の計算時間が短い結果となった。

コメント

タイトルとURLをコピーしました