Targeted Cache Control のライブラリをC言語で書いた

はじめに

C11 のような最近(と言っても2022年だと11年前ですが)のC言語の勉強を兼ねて RFC 8941 - Structured Field Values for HTTP のライブラリを書いてみました。 さらに RFC 9213 - Targeted HTTP Cache Control のフィールド値をパースする関数も書いてみました。

ビルドツールはこれも勉強を兼ねて CMake を使いました。

得られた知見などをメモしておきます。なお、例によって間違っていたり、もっと良い方法が他にあるかもしれませんが、その場合はやさしくご指摘いただけるとありがたいです。

ライブラリは hnakamur/http-sfv で公開しています。 ただ、RFC 8941 - Structured Field Values for HTTP のほうは毎回メモリ割り当てする素朴な実装なので実用向きではないです。 RFC 9213 - Targeted HTTP Cache Control のフィールド値をパースする関数のほうはメモリ割り当て不要で実用でも使えそうかと思ってますが、まだ実際には使ってないです。

参考書籍

「Cクイックリファレンス」はC99とC11の言語とライブラリについてコンパクトにまとめられていて、C言語は一応知っているけど、C11のような最近の標準を知らない私にはとても良い本でした。

C11 (C standard revision) - Wikipedia からリンクされている C11 の最終ドラフト N1570 の PDF も少し参照しました。

Professional CMake のほうは 7th Edition は持っていたのですが Release Notes を見て 12th Edition まで出ているということで買ってみました。

実装メモ

Zigのスタイルを取り入れ

Zigを勉強したのでそれの影響を受けたスタイルにしてみました。

その他の実装メモ

C99の利点

今回感じた利点は以下のとおりです。

http-sfv/bare_item.c at main · hnakamur/http-sfv

const char hsfv_key_trailing_char_map[256] = {
    ['*'] = '\1',
    ['-'] = '\1', ['.'] = '\1',
    ['0'] = '\1', '\1', '\1', '\1', '\1', '\1', '\1', '\1', '\1', '\1', // to '9'
// …(略)…

ちなみに C89 で書かれている nginx ではこんな技を使っているのを見つけました。

nginx/ngx_http_parse.c at release-1.23.0 · nginx/nginx

    /* the last '\0' is not needed because string is zero terminated */

    static u_char  lowcase[] =
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0"
        "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
        "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";

最後の行だけ1文字わざと短くしていて文字列の終端の NUL 文字を添字255の要素として使うというものです。この手の表は添え字255の要素の値はたいてい0なので、この技は C89 では便利かもと思いました。

最近接偶数への丸め

RFC 8941 3.3.2. Decimals では Decimal は以下の形式と定められています。

sf-decimal  = ["-"] 1*12DIGIT "." 1*3DIGIT

IEEE 754 - WikipediaBasic and interchange formats の binary64 の Decimal digits 列の値は 15.95 とあります。 Decimal は整数部12桁、小数部3桁で合計15桁でこれを考慮しているのだなと思います。

RFC 8941 4.1.5. Serializing a Decimal には Decimal をシリアライズする場合は小数部3桁で最近接偶数へ丸めると書かれています。

最初 snprintf"%.3f" という書式で実装してみたら httpwg/structured-field-tests: Tests for HTTP Structured Field Values のテストが通りませんでした。

そこで fesetroundrint を使って実装するように変更しました。

fegetround で現在の丸めモードを取得して最近接偶数への丸め FE_TONEAREST でない場合は fesetround でモードを切り替えて、 rint で丸めます。丸めモードを変更した場合は元に戻します。

http-sfv/bare_item.c at main · hnakamur/http-sfv

#pragma STDC FENV_ACCESS ON
hsfv_err_t hsfv_serialize_decimal(double decimal, hsfv_allocator_t *allocator, hsfv_buffer_t *dest)
{
    int prev_rounding = fegetround();
    if (prev_rounding != FE_TONEAREST && fesetround(FE_TONEAREST)) {
        return HSFV_ERR_FLOAT_ROUNDING_MODE;
    }

    double rounded = rint(decimal * 1000);

    if (prev_rounding != FE_TONEAREST && fesetround(prev_rounding)) {
        return HSFV_ERR_FLOAT_ROUNDING_MODE;
    }

    char tmp[decimal_tmp_bufsize];
    int n = snprintf(tmp, decimal_tmp_bufsize, "%.3f", rounded / 1000);
// …(略)…
    return HSFV_OK;
}
#pragma STDC FENV_ACCESS OFF

テスト

テストライブラリは Catch2 の v3.0.1 を使ってみた

catchorg/Catch2: A modern, C++-native, test framework for unit-tests, TDD and BDD - using C++14, C++17 and later (C++11 support is in v2.x branch, and C++03 on the Catch1.x branch)

Catch2 自体は C++ で書かれていますが、私のテストコードは C で書きました。使い方がシンプルで良かったです。

メモリ割り当て失敗時のテスト

Zig の lib/std/testing/failing_allocator.zig を参考に指定した回に失敗するようなアロケータ hsfv_failing_allocator を実装してそれを使ってテストしました。

Address Sanitizer を使ってみた

テストコードでメモリリークや二重解放などがあるとソースコードの行数とともに教えてくれるので便利でした。 Zigのstd.testing.allocator で出来てて便利と思っていたのですが、Cでも出来たんですね。

Clangの Source-based Code Coverage を使ってみた

Source-based Code Coverage

行より細かいリージョンという単位でカバレッジが見れて便利でした。

JSONファイルの読み込みには yyjson を使用

mattn さんの Big Sky :: RapidJSON や simdjson よりも速いC言語から使えるJSONライブラリ「yyjson」 を読みつつ ibireme/yyjson: The fastest C JSON library を使ってみました。使いやすい API で良かったです。 httpwg/structured-field-tests: Tests for HTTP Structured Field Values のテストデータはJSONファイルで提供されているのでそれを読み込む必要があります。

base32 もサードパーティのライブラリを使用

httpwg/structured-field-tests: Tests for HTTP Structured Field Values のJSONファイル内でbase32が使用されているので paolostivanin/libbaseencode: Library written in C for encoding and decoding data using base32 or base64 (RFC-4648) を使いました。

Targeted HTTP Cache Control のフィールド値のパース関数の実装メモ

Structured Field Values for HTTP のパーサとシリアライザがとりあえず動くようになった後、データ構造やメモリ割り当ての効率化をどうしようかなと考えていたときに RFC 8941 A.1. Why Not JSON? を見て、JSONのライブラリがどうやってるか見ると参考になるかもと思いました。

で、yyjson: Data Structures を見るといろいろ工夫されていて勉強になりました。

が、The simdjson library のベンチマークのグラフを見ると、 simdjson のほうが3倍以上速かったので、こちらも見てみました。このベンチマークでは The Basics: Loading and Parsing JSON Documents で説明されている ondemand::parser というが使われていました。これは JSON 全体を解釈してデータ構造を作るのではなく、利用側のコードで参照する箇所だけ局所的に解釈するようになっています。yyjsonのパースはJSON全体のデータ構造を作るのでこのベンチマークは apple to apple な比較にはなっていないのではという気もしますが、JSONを読み込んで一部のキーだけ参照するという利用ケースを想定するのであれば妥当なのかもしれません。

それはともかく、Targeted HTTP Cache Control のフィールド値のパースのことを考えてみると、これも必要なキー以外は無視することになるので、全体のデータ構造を作る必要はないことに気づきました。

RFC 9213 2.1. Syntax を見ると Target Cached Control のフィールド値は Structured Field Values の Dictionary として解釈するという仕様です。仕様通りパースできない場合はフィールド全体を無視せよとあります。

max-age に整数値ではなく少数付きのdecimal値が指定されていた場合もエラーにするという厳格な方針になっています。

昔はネットワークのプロトコルは送信側は仕様に厳格に沿うが受信側は寛容にするというスタイルがあったが、近年ではセキュリティ上問題になるので受信側も厳格にするという流れになっています。intarchboard/draft-protocol-maintenance: Don’t apply the robustness principle, look after your protocol instead

ということで、以下の方針としました。

Target Cached Control のフィールドが複数ある場合はカンマで連結後パースすることになります。実装上は実際に連結しなくても各フィールドを順にパースすれば同等の処理になります。

この結果、動的メモリ割り当てを全く行わずにパースする実装ができました。

CMake 関連メモ

cmake-format

cmake の実行時に cmake-formatCMakeLists.txt をフォーマットするようにしてみました。

clang-format

make の実行時に clang-format でソースコードをフォーマットにするようにしてみました。

Address Sanitizer

上でも書きましたが、テストのコードを -fsanitize=address つきでビルドして Address Sanitizer を有効にしました。

Source-based Code Coverage

上でも書きましたが、テスト実行後にカバレッジを取得するカスタムターゲットを追加し、 make check で実行できるようにしました。