Chromium の hpack 実装をソースコードリーディング #http2study

はじめに

このエントリーは HTTP2 Advent Calendar の 14 日目の記事です。

Chromium の実装については現時点の最新の master を元にしています。

おおよそ 40.0.2214.42 相当と考えていただければ良いかと思います。

自分自身まだ完全に理解しきれていない部分が多いので説明を端折っている場合があります。

間違い等ございましたらご指摘いただけると幸いです。

ソースコードについて

Chromium の hpack 実装は net/spdy にあります。

% ls net/spdy | grep hpack
hpack_constants.cc
hpack_constants.h
hpack_decoder.cc
hpack_decoder.h
hpack_decoder_test.cc
hpack_encoder.cc
hpack_encoder.h
hpack_encoder_test.cc
hpack_entry.cc
hpack_entry.h
hpack_entry_test.cc
hpack_header_table.cc
hpack_header_table.h
hpack_header_table_test.cc
hpack_huffman_aggregator.cc
hpack_huffman_aggregator.h
hpack_huffman_aggregator_test.cc
hpack_huffman_table.cc
hpack_huffman_table.h
hpack_huffman_table_test.cc
hpack_input_stream.cc
hpack_input_stream.h
hpack_input_stream_test.cc
hpack_output_stream.cc
hpack_output_stream.h
hpack_output_stream_test.cc
hpack_round_trip_test.cc
hpack_static_table.cc
hpack_static_table.h
hpack_static_table_test.cc
hpack_string_util.cc
hpack_string_util.h
hpack_string_util_test.cc

今回は

net/spdy/hpack_huffman_table_test.cc - chromium/src - Git at Google

を中心に読んでみたいと思います。以下にテスト名称で説明していきます。

InitializeEdgeCases

HpackHuffmanSymbol の配列を初期化する際の一般的な正常系、異常系のテストが並んでいます。

内容はコメントを見ていただければだいたい分かるかと思います。

draft-ietf-httpbis-header-compression-09 - HPACK - Header Compression for HTTP/2net/spdy/hpack_huffman_table.cc - chromium/src - Git at Google の HpackHuffmanTable::Initialize の辺りを眺めていただくと雰囲気がつかめるのではないかと思います。

ValidateInternalsWithSmallCode

TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) {
  HpackHuffmanSymbol code[] = {
    {bits32("01100000000000000000000000000000"), 4, 0},  // 3rd.
    {bits32("01110000000000000000000000000000"), 4, 1},  // 4th.
    {bits32("00000000000000000000000000000000"), 2, 2},  // 1st assigned code.
    {bits32("01000000000000000000000000000000"), 3, 3},  // 2nd.
    {bits32("10000000000000000000000000000000"), 5, 4},  // 5th.
    {bits32("10001000000000000000000000000000"), 5, 5},  // 6th.
    {bits32("10011000000000000000000000000000"), 8, 6},  // 8th.
    {bits32("10010000000000000000000000000000"), 5, 7}};  // 7th.
  EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
  ASSERT_EQ(arraysize(code), peer_.code_by_id().size());
  ASSERT_EQ(arraysize(code), peer_.length_by_id().size());
  for (size_t i = 0; i < arraysize(code); ++i) {
    EXPECT_EQ(code[i].code, peer_.code_by_id()[i]);
    EXPECT_EQ(code[i].length, peer_.length_by_id()[i]);
  }

  EXPECT_EQ(1u, peer_.decode_tables().size());
  {
    std::vector<DecodeEntry> expected;
    expected.resize(128, DecodeEntry(0, 2, 2));  // Fills 128.
    expected.resize(192, DecodeEntry(0, 3, 3));  // Fills 64.
    expected.resize(224, DecodeEntry(0, 4, 0));  // Fills 32.
    expected.resize(256, DecodeEntry(0, 4, 1));  // Fills 32.
    expected.resize(272, DecodeEntry(0, 5, 4));  // Fills 16.
    expected.resize(288, DecodeEntry(0, 5, 5));  // Fills 16.
    expected.resize(304, DecodeEntry(0, 5, 7));  // Fills 16.
    expected.resize(306, DecodeEntry(0, 8, 6));  // Fills 2.
    expected.resize(512, DecodeEntry());  // Remainder is empty.

    EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]),
                Pointwise(DecodeEntryEq(), expected));
  }
  EXPECT_EQ(bits8("10011000"), peer_.pad_bits());

  char input_storage[] = {2, 3, 2, 7, 4};
  StringPiece input(input_storage, arraysize(input_storage));
  // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100.
  char expect_storage[] = {
    bits8("00010001"),
    bits8("00101000"),
    bits8("01001100")};
  StringPiece expect(expect_storage, arraysize(expect_storage));

  string buffer_in = EncodeString(input);
  EXPECT_EQ(expect, buffer_in);

  string buffer_out;
  HpackInputStream input_stream(kuint32max, buffer_in);
  EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(),  &buffer_out));
  EXPECT_EQ(buffer_out, input);
}

HpackHuffmanTable::Initialize の最後の方に HpackHuffmanTable::BuildDecodeTables と HpackHuffmanTable::BuildEncodeTable が実行されます。

まず HpackHuffmanTable::BuildDecodeTables の際に HpackHuffmanTable::DecodeTable と HpackHuffmanTable::DecodeEntry の配列が作成されます。

その際、先頭9ビット (kDecodeTableRootBits) から6ビット (kDecodeTableBranchBits) づつ処理されます。

このテストの場合 symbol が9ビット以内に収まっているため HpackHuffmanTable::BuildDecodeTables の配列は一つです。

decode_tables_: {
  prefix_length: 0, indexed_length:  9, entries_offset: 0
}

一番目の ”00" が長さ2なので9ビットから引いた数7ビット分で表される数は仕様上許されません。その分の127(0b1111111)を含んだ128個分 HpackHuffmanTable::DecodeEntry の配列が作成されます。

decode_entries_: {
  next_table_index: 0, length: 2, symbol_id: 2
  ... 以降インデックス 1 〜 127 まで同様

以降長さ3、4、5ビットの symbol も同様に処理されます。

最後の symbol は7ビットより長い必要があり、これは padding に利用されます。

なので peer_.pad_bits() が "10011000" になります。

※ peer_ はテスト用に private な変数にアクセス出来るようにしたクラス(friend class)で HpackHuffmanTablePeer のインスタンス

net/spdy/hpack_huffman_table.h - chromium/src - Git at Google

このテストの最終的な decode_tables と decode_entries について気になる方はこちらを参考にしてください。

https://gist.github.com/kysnm/4f0864f28f8dfb9dd72a

最後の EncodeString はごく単純で id の列を渡して HpackHuffmanTable::BuildEncodeTable 時に生成される code_by_id と length_by_id から対応する length と code を取り出して、先頭から順番にビット列に詰め込んでいくだけです。

ValidateMultiLevelDecodeTables

TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) {
  HpackHuffmanSymbol code[] = {
    {bits32("00000000000000000000000000000000"), 6, 0},
    {bits32("00000100000000000000000000000000"), 6, 1},
    {bits32("00001000000000000000000000000000"), 11, 2},
    {bits32("00001000001000000000000000000000"), 11, 3},
    {bits32("00001000010000000000000000000000"), 12, 4},
  };
  EXPECT_TRUE(table_.Initialize(code, arraysize(code)));

  EXPECT_EQ(2u, peer_.decode_tables().size());
  {
    std::vector<DecodeEntry> expected;
    expected.resize(8, DecodeEntry(0, 6, 0));  // Fills 8.
    expected.resize(16, DecodeEntry(0, 6, 1));  // Fills 8.
    expected.resize(17, DecodeEntry(1, 12, 0));  // Pointer. Fills 1.
    expected.resize(512, DecodeEntry());  // Remainder is empty.

    const DecodeTable& decode_table = peer_.decode_tables()[0];
    EXPECT_EQ(decode_table.prefix_length, 0);
    EXPECT_EQ(decode_table.indexed_length, 9);
    EXPECT_THAT(peer_.decode_entries(decode_table),
                Pointwise(DecodeEntryEq(), expected));
  }
  {
    std::vector<DecodeEntry> expected;
    expected.resize(2, DecodeEntry(1, 11, 2));  // Fills 2.
    expected.resize(4, DecodeEntry(1, 11, 3));  // Fills 2.
    expected.resize(5, DecodeEntry(1, 12, 4));  // Fills 1.
    expected.resize(8, DecodeEntry());  // Remainder is empty.

    const DecodeTable& decode_table = peer_.decode_tables()[1];
    EXPECT_EQ(decode_table.prefix_length, 9);
    EXPECT_EQ(decode_table.indexed_length, 3);
    EXPECT_THAT(peer_.decode_entries(decode_table),
                Pointwise(DecodeEntryEq(), expected));
  }
  EXPECT_EQ(bits8("00001000"), peer_.pad_bits());
}

このテストは長さ9ビットを超えた symbol がある場合のテストです。HpackHuffmanTable::BuildDecodeTables の配列が2つになります。

それ以外については上のテストと同様です。

SpecRequestExamples

TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));

  string buffer;
  string test_table[] = {
    a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"),
    "www.example.com",
    a2b_hex("a8eb10649cbf"),
    "no-cache",
    a2b_hex("25a849e95ba97d7f"),
    "custom-key",
    a2b_hex("25a849e95bb8e8b4bf"),
    "custom-value",
  };
  // Round-trip each test example.
  for (size_t i = 0; i != arraysize(test_table); i += 2) {
    const string& encodedFixture(test_table[i]);
    const string& decodedFixture(test_table[i+1]);
    HpackInputStream input_stream(kuint32max, encodedFixture);

    EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(),
                                    &buffer));
    EXPECT_EQ(decodedFixture, buffer);
    buffer = EncodeString(decodedFixture);
    EXPECT_EQ(encodedFixture, buffer);
  }
}

a2b_hex は16進数文字列をバイナリ変換する関数です。

実装は以下にありますので興味のある方は見てみてください。

net/spdy/spdy_test_utils.cc - chromium/src - Git at Google base/strings/string_number_conversions.cc - chromium/src - Git at Google

"a8eb10649cbf" だと "101010001110101100010000011001001001110010111111" の 48ビットになります。

Appendix C. Huffman Code を元に "no-cache" をエンコードすると "101010", "00111", "010110", "00100", "00011", "00100", "100111", "00101", "11111" (pad) で上の48ビットと同じですね。

HpackHuffmanTable::DecodeString の内部では各種初期化の後 HpackInputStream::PeekBits で uint32_t に先頭8ビットのみを読み込みます。

具体的には bits に 10101000000000000000000000000000 が代入されます。

ここから先頭の9ビット 101010000 が index になります。10進数で 336 です。

HpackHuffmanTable::Entry は return decode_entries[table.entries_offset + index]; するので decode_entries[336] が返ります。

この部分は kDecodeIterations (= static_cast(std::ceil((32.f - kDecodeTableRootBits) / kDecodeTableBranchBits)))、具体的には4回ループしますが、 decode_entries[336] の next_table_index は 0 なので同じ decode_tables[0] を参照するので { prefix_length: 0, indexed_length: 9, entries_offset: 0 } のままです。デコード対象の code が長くなると next_table_index で違うテーブルを参照し最終的に symbol_id にたどり着きます。

decode_entries_[336] は { next_table_index: 0, length: 6, symbol_id: 110 } なので entry.length は 6 で bits_available は HpackInputStream::PeekBits で設定された peeked_count なので 8 になっています。

peeked_success は true になっているので 331 行目の else 節に進みます。

out_capacity は decodedFixture.size() なのでデコード対象の文字列サイズを超えないようエラーチェックがあります。また symbol_id 256 は EOF になるのでそのチェックも行われます。

ここで entry.symbol_id 110 を char にキャストし出力用変数 out に "n" が代入されます。

次に HpackInputStream::ConsumeBits で読み込み済ビット長6ビットのを消費したということで、bit_offset_ が 6 に設定されます。2ビット残りがあり、先頭バイトは全て消費されていないのでこの時点では先頭バイトは削除されません。また bits から読み込み済の先頭 6ビットがビットシフトにより捨てられ、bit_available は entry.length 分引かれて 2 になります。

最後に HpackInputStream::PeekBits で追加の読み込みが行われます。peeked_count が 32 以上になるか bit_offset_ + peeked_count の合計がデコード対象の文字列サイズ以上になった場合に peeked_success がfalse になるので if 文の判定条件のところで return します。

これを繰り返すことにより "no-cache" の文字列をデコードします。

ちなみに net/spdy/hpack_constants.cc - chromium/src - Git at Google 用意された Huffman Code を元に Initialize された decode_tables と decode_entries が気になる方は以下のリンクをご確認ください。

https://gist.github.com/kysnm/0fdf0149f40a26f6703f

おわりに

時間が厳しくなってきたのでこのくらいで終わります。まだまだ全然理解が足りていませんし、読めていない部分も多いので引き続き読んでいきたいと思います。あとでできたら Chromium のコールドリーディングの tips 的なことも追記したいと思います。

C++ は普段使わない言語なのでここまで理解するのに結構時間がかかってしまいました。もっと詳しい方にいろいろ教えて欲しいのでもしよろしければお声がけください。使わない部分を潰す為に std::vector::resize で使っている部分とかパフォーマンス的にどうなのかとか気になります。

今年は http2 の年だったと言えるくらいいろいろな面でコミュニティの中心となる皆さんが頑張っていらっしゃいました。このエントリーで少しでも感謝が伝えられたらいいなと思います。

余談ですが, 現在の仕様では "HTTP2.0" ではなく "HTTP/2" もしくは "HTTP2" が正しい名称です.