社内の輪読会に参加して発表した
輪読のお題はこちら
O'Reilly Japan - 詳解 Linuxカーネル 第3版
「5章 カーネルの同期処理」を担当しました
自分にとってはかなり難易度高めです
振り返り
Problem
資料がまとめきれず時間内に説明し終えることが出来なかった
もう少し早めに準備すべきだった
自分の言葉で表現できなかったので説明がふらふらしてしまった
もう一度読みなおして再構成する余裕があれば良かったかも
Keep
輪読会の参加者のレベルが高く有意義な時間を過ごせている
- 逆に自分の不甲斐なさが不安になるけど「一番の下手くそ」になれる環境は貴重だ
Try
とはいえ発表するとなると理解度が上がるので次回も自分なりにまとめておきたい
- 読むのにだいぶ時間がかかるのが難点かなー
この輪読会を企画していただいた事、参加させていただいた事に感謝 (｀･ω･´)ゞ
#http2study で libh2o の LT しました
実は初めての LT だったりします。
お聞き苦しい点があったかと思いますがご容赦ください。
スライドだけだとなんのこっちゃですが、h2o ドキュメント無いけど examples を見て xcode でデバッグしつつ頑張ればいろいろ出来そう ってなことを伝えたかった感じです。
だいたい include にある関数が使えると思われるのでいろいろやって みると楽しそうですよ！
追記：
初めての Ruby C 拡張だし、gem 書くのも初めてだったりします (汗
あと最後の方のスライドで(/ω・＼)ﾁﾗｯと触れていますが、今日リリースされた h2o 1.2.0 から openssl から LibreSSL に変更されてバンドルされるようになったのでコンパイルがより手軽になっているようです。
自分が作った Ruby の C 拡張、別環境に落としてきたらうまく動かない…
2014年の振り返り
来年は書けるようにしたい
picohttpparser の addon を書いてみた
はじめに
このエントリーは Node.js Advent Calendar 2014 - Qiita と h2o Advent Calendar 2014 - Qiita の 21 日目の記事です。
現時点の node.js の安定版は v0.10.34、開発版は v0.11.14 で、v8 のバージョンはそれぞれ 3.14.5、3.26.33 です。 nan (Native Abstractions for Node.js) のバージョンは 1.4.1 です。
Motivation
以前も Node.js の http_parser の実装を追ってみたことがあって興味があったし、HTTP/2 を追うことでやはり parser に触れてきました。自分は普段は Rails のアプリケーションエンジニアをやっているので Ruby にも興味があります。そして以前は Perl も書いていました。なので @kazuho さんの作られた picohttpparser については耳にしていましたし、h2o で使われているのも知っていました。そんな中 Perl コミュニティで有名な @kazeburo さんが Ruby の C 拡張として pico_http_parser をリリースされました。前々から Node.js の addon は書いてみたかったので、この機会に Ruby の C 拡張の仕組みに触れつつ、picohttpparser の理解を深めるチャンスだと思いやってみました。
What's hard?
ほとんど @kazeburo さんの実装をそのまま使っていて、一部 Node.js の作法に合わせる形で実装しました。普段 C/C++ は書かないのでちょっとしたところでつまづきやすかったです。また nan が v8 のバージョン間の差異を埋めてくれるんですが、きちんと理解して使っていないのでトライアンドエラーで探り探りでした。結果としてまだ開発版での build が成功していないという体たらくです、すいません。
v8 のドキュメントは聞いた話だとソースコードから doxygen で生成するしかないとのことでした。doxygen をあまり使ったことがないのでドキュメントの生成の仕方がよくわからず、Eclipse でやってみたりしたんですがどうも狙ったバージョンのリファレンスが生成出来ず、現時点でバージョン間の差異をきちんと把握することが出来ていません。この辺詳しい方がいらっしゃったらぜひ教えていただきたいです。
またデバッグは Mac 上で行っていて、この Mac は半年くらい前に乗り換えたばかりで gdb の cert の設定 OS XでGDBを使う（ためにコード署名をする） - Qiita 等をするのが面倒だったで lldb を使っていました。gdb でどうかはわかりませんが、lldb の p、po では v8::String をうまく見ることが出来ずはかどりませんでした。この辺も詳しい方教えてください！
おわりに
というわけで一応 github に公開していますが、勉強がてら書いてみたものなので npm にリリースする予定はありません。また出来れば C++ で書きなおしたり、引数に callback を渡すスタイルを検討したりしてみたいと思ったので時間がある時にやれたら良いなーと思っています。まだ multi line のリクエストもうまく動かせていないのでそのへんのデバッグもしないとなー。
kysnm/node-pico-http-parser · GitHub
謝辞
picohttpparser の作者の @kazuho さん、実装を参考にさせていただいた @kazeburo さんに感謝いたします。ありがとうございました！
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/2 や net/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
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" が正しい名称です.
