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

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

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

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

計算手法

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

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

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

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

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

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

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)

上記の手法では、加算または減算毎にオーバーフローを検知して補正する必要があった。これは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);
}

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

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

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

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

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

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