abcdefGets

ゲッツ!

WeJS2周年おめでとうございます

久しぶりのブログはこちらのアドベントカレンダー

adventar.org

WeJSについて

We are Javascritpers

wajs.connpass.com

初心者登壇歓迎なJavascript勉強会
最近はJS初心者歓迎も兼ねていて、多方面で参加しやすい勉強会になってる

思い出

21Cafeでやってるときに参加して依頼、だいたい行ってると思う
3回目くらいからかな?

全ての勉強会の中でここで最もLTしてると思う
いつもお世話になっております

ここでいろんな人と知り合いになれました

良いなと思っていること

今の時代にjavascriptで初心者歓迎なLT会は貴重

とにかく登壇の敷居を下げてくれているので登壇しやすい
特に一度も登壇したことない人はぜひ申し込んで登壇してほしい

ただ、倍率が高いので抽選通るまで頑張ろう

あと毎回賑やかでよい
懇親会とかすごく話しやすい雰囲気だなぁと毎回思う

これもひとえに主催者の方々の人柄ですね

これからWeJSでLTする方へ

自分のネタがしょぼいかなとか、みんな知ってるしとか考えなくていいよ!
まずは自分が楽しもう

昔WeJSでLTした心得的なやつ

speakerdeck.com

最後に

いつもありがとうございます。毎月楽しみにしてます。感謝。

JSのproposal-numeric-separatorを実装したよ

タイトルの通りなんだけど、書くのが遅れてしまった。
V8 のmasterにマージされた。

機能

javascriptのプロポーザルで数値リテラルの間にアンダースコアを挿入できるやつ

現在stage3にあってまだ正式に採用されているわけではない。

github.com

このスライドにも書いた

speakerdeck.com

例.

1_0_00_0
0xFF_FF_FF
0b0101_01_01
0o7_7_7

16進数、10進数、8進数、2進数の各リテラルに対応している。

あとBigIntにも当然対応している

39_950_934n

ただ、実装したあとに修正してもらったんだけど、implicit octalには対応していない。

0777_7 // Error!

あと、以下の場合はすべてエラー

0x_000 // Error !
0b_01 // Error !
0o_10 // Error !

アンダースコアの重複と末尾もだめ

12__00 // Error !
1200_ // Error !

制限

キャストされる数値には使えません!

Number('1_0_0') // Error !
parseInt('1_0_0', 10) // Error !

以下のIssueに詳しい

Numeric separator supported in implicit coercions, e.g., `+"0_0"`? · Issue #32 · tc39/proposal-numeric-separator · GitHub

簡単に話すと今までは

IsNaN(Number('1_0_0')) // true

だったので急にアンダースコアを数値として使えるようになると、NaNであることを期待しているコードが壊れるからという理由。
そのようなコードが一体どれほどあるのか知らないけど安全側に倒した。
breaking webを避けるためには仕方ないかなと言う感じ。

以上です。

V8の Object.entries/values を高速化した

V8のObject.entries/valuesを高速化したよというお話

Object.entires/values

そもそもObject.entriesObject.valuesとは何かというと、
GitHub - tc39/proposal-object-values-entries: ECMAScript Proposal, specs, and reference implementation for Object.values/Object.entriesで提案されていた仕様である。
見事stage4まで到達して採用された。

仕様

機能をおさらいしておく

Object.entries(O)

const ret = Object.entries({a: 1, b: 2, c: 3});
console.log(ret) // [['a', 1], ['b', 2], ['c', 3]];

キーと値をすべて配列に書き出してくれる。

Object.values(O)

const ret = Object.values({a: 1, b: 2, c: 3});
console.log(ret) // [1, 2, 3];

値のみを配列に書き出してくれる。

Ecma262のspecによると以下のように動作が規定されている

  • ToObject(O)を呼び出す
  • EnumerableOwnList(O)を呼び出して結果をnameListに格納
    • Type(O)がObjectかチェック
    • O.[[OwnPropertyKeys]]()を呼び出してキー一覧をownKeysに代入
    • properties配列を初期化
      • for each key of ownKeys
        • Type(key)が文字列なら続行
          • descにプロパティデスクリプタをO.[[GetOwnProperty]](key)を呼び出して代入
          • descundefinedではなくdesc.[[Enumerable]]なら
            • もしObject.keysならkeypropertiesに追加
            • Object.values/entriesなら
              • Get(O, key)を呼び出してvalueに代入
              • Object.valuesの場合にはvaluepropertiesに代入
              • Object.entriesの場合にはCreateArrayFromList(« key, value »).を呼び出してentryに代入
              • propertiesentryを追加
  • CreateArrayFromList(nameList)を呼び出してReturn

コードで表すと

function ObjectEntries(O) {
  O = ToObject(O);
  const nameList = EnumerableOwnList(O, 'entry');
  return new JSArray(nameList);
}

function ObjectValues(O) {
  O = ToObject(O);
  const nameList = EnumerableOwnList(O, 'value');
  return new JSArray(nameList);
}

function EnumerableOwnList(O, kind) {
  const ownKeys = O.[[OwnPropertyKeys]]();
  const properties = [];
  for (const key of ownKeys) {
    if (Type(key) === String) {
      const desc = O.[[GetOwnProperty]](key);
      if (desc && desc.[[Enumerable]]) {
        if (kind === 'key') {
          properties.push(key);
        } else {
          const value = Get(O, key);
          if (kind === 'value') {
            properties.push(value);
          } else {
            const entry = [key, value];
            properties.push(entry);
          }
        }
      }
    }
  }
  return properties;
}

て感じの動作になる。

基本的にはキー一覧を取得してからPropertyDescriptorを各々取得していって、Enumerableなら配列に追加していく形になる。

Too Slow

V8のObject.entries/valuesV6.5.172までは非常に遅くて使うのを躊躇するほどだった。

ベンチマークをとるとこんな感じ

Fast Path

forIn: 134 ms.
objectKeys: 552 ms.
objectKeysAndValues: 1010 ms.
objectEntries: 2541 ms.

Slow Path

forIn: 3117 ms.
objectKeys: 837 ms.
objectKeysAndValues: 1740 ms.
objectEntries: 2536 ms.

objectEntriesobjectKeysAndValuesforInに対して10倍以上遅いのがわかる。
ちなみにFast Pathはプロパティのみを含む通常のシンプルなオブジェクトで、Slow PathはSymbolGetterを含んでいる。

なぜこんなに遅いのか

こんなに遅い理由はRuntimeですべて実装されていたためである。
RuntimeとはC++で書かれたコードでC++コードとして静的にコンパイルされる。
一見C++ならば早そうに見えるが、やはり直にアセンブリに変換されるCSA等と比べると遅く、
さらにjavascriptの世界から呼び出す際にも大きなオーバーヘッドがある。

どのように高速化したか

CSA(CodeStubAssembler)に移植した。
ちなみにRuntimeとかCSAに関してはV8 javascript engineについての細かい話 (Node.js Advent Calendar 2017) - abcdefGetsに記載している。

ただし、完全にすべてのコードを移植したわけではない。

V8の方針

最初、私はRuntimeにあったObject.entries/valuesのすべての実装をCSAで書き直した。
これは一見うまく行ったのだが、いくつかの問題をはらんでいた。

  • 高速化したのだがCSAの本来のポテンシャルを活かしきれていない
  • 小さなRuntime呼び出しを残さざるを得なかった
  • 修正箇所が多すぎる

高速化したのだがCSAの本来のポテンシャルを活かしきれていない

これは私のCSA力不足が原因だった。
確かに最初の実装で信じられないほど高速化した。以下のベンチマークを見ていただきたい。

Fast Path

forIn: 136 ms.
objectKeys: 561 ms.
objectKeysAndValues: 472 ms.
objectEntries: 617 ms.

Slow Path

forIn: 1307 ms.
objectKeys: 946 ms.
objectKeysAndValues: 1526 ms.
objectEntries: 1623 ms.

確かにFast Pathのコードは非常に高速化しているものの、
Slow Pathの方は微かに高速化しただけだ。
これはFast Pathでさえ本来のCSAのポテンシャルで考えるとまだまだ遅いものだった。
しかもこのバージョンのコードは以下の問題を抱えていた。

小さなRuntime呼び出しを残さざるを得なかった

確かにCSAに移植はしたものの、CSAで記述するには明らかに複雑すぎるコード(数値プロパティの要素を取得するためのコードと、Slow Pathのコード)を含んでいたため、
結局小さなRuntimeを別途実装してCSAからRuntimeを呼び出すコードになっていた。
CSAからRuntimeを呼び出すのはjavascriptの世界から呼び出すのと同じくコンテキストスイッチのオーバーヘッドがかなり大きい。
そのためFast PathもSlow Pathも非効率なコードになっていた。
そしてさらに問題だったのはコード量だった。

修正箇所が多すぎる

明らかにV8という世界規模のOSSにコミットするコードとしては修正量が大きすぎた。
最初はレビュアーもなんとなく見てくれていたが、さすがにこれは一旦方針を変えようという話になった。

小さくすすめる

大切なのはいきなり大きな変更をしないことだ。
V8ほど複雑なコードベースなら尚更だ。
V8はすでに一部分の変更がどう影響するか、机上のみで推測するのは不可能なほどの複雑さを持っていた。
そこでレビュアーと話し合って、以下の方針で再実装することにした。

  • 既存のRuntimeは残す
  • Slow Pathは移植しない
  • 数値プロパティ検索も移植しない
  • もし途中でSlow Pathに入る場合にはRuntime呼び出しを行い、Runtimeですべて行う。

結局泣く泣くSlow Pathのコードを全削除し、Fast Pathで最速のケースのみをCSAに移植した。

終結

上述の過程を踏まえた上でコードを修正した結果以下の様になった。

Fast Path

forIn: 134 ms.
objectKeys: 525 ms.
objectKeysAndValues: 320 ms.
objectEntries: 469 ms.

Slow Path

forIn: 1307 ms.
objectKeys: 945 ms.
objectKeysAndValues: 1304 ms.
objectEntries: 2043 ms.

Slow Pathは以前と変わらない速度だが、Fast Pathに至っては、

  • Object.etnries2541 ms から 469 ms
  • Object.values1010 ms から 320 ms

という結果に。約3 ~ 5.5倍ほど高速化した。

やはりSlow Pathの移植を一旦止めて、Fast Pathのみに絞ったことがより洗練されたコードを可能にし、
その結果としてCSAの力を振り絞ることができたようだ。
ちなみにSlow Pathに関しては今のところはそこまで高速化するチャンスがないのと、使用用途的にあまり通らないパターンが多いので、
また議論が起きたときに高速化する予定。

なので、現状の実装は以下のパターンの場合のみ超高速に動作する。

  • Symbolを含まない
  • Getterを含まない
  • 数値プロパティを含まない
  • Proxyではない

まとめ

V8ほどの規模になると、小さく始めていくのがレビュアーにとっても実装者にとっても重要である。
という学びを得た。

ちなみにこのコードはV8 6.5.173にShipされました。

ベンチマークに使ったコードは以下のものです。

Fast Path
object-entries-values-fast-path-bench.js · GitHub

Slow Path
object-entries-values-slow-path-bench.js · GitHub

ブラウザベンダーのSpectre and Meltdown対応

Spectre and Meltdownについては前回書いたが、
各ブラウザベンダーがとっている対応について今回は書く。

といっても大したことではないのだが。

対応一覧

  • Google Chrome
    • SharedArrayBufferのデフォルト無効化とPerformance.nowの解像度を下げる(どこまでかは不明)
    • Per Site Isolationを有効化
  • Firefox
    • SharedArrayBufferのデフォルト無効化とPerformance.nowの解像度を20μsまで下げる
  • Safari
    • SharedArrayBufferのデフォルト無効化とPerformance.nowの解像度を1msまで下げる

SharedArrayBufferとPerformance.nowの関係

なぜブラウザベンダーがSharedArrayBufferのデフォルト無効化とPerformance.nowの解像度を下げるかというと、今回の脆弱性の攻撃手法に関係がある。
SpectreとMeltdownは両方共、攻撃時にL1キャッシュメモリの推測を行う必要がある。(具体的には、メモリアクセスを行い、かかった時間を計測してキャッシュされている値を推測する。これをSide-Channel-Attackと呼ぶ。)

このSide-Channel-AttackSharedArrayBufferperformance.nowを使うことでかなり効率化できる。

// Worker

self.on('message', (e) => {
  const buf = new SharedUint32Array(e.data.buffer);
  do {
    Atomic.store(buf, 0, performance.now() - buf[0]);
  } while(true)
});

// main

// Create worker before.

const sab = new SharedUint32Array(1);
sab[0] = peformance.now();
worker.postMessage({buffer: sab.buffer}, [sab.buffer]);

// do memory access.

console.log(Atomic.load(buf, 0)); // Get high resolution relative time.

こんな感じでワーカースレッドでクロックを実装し、performance.nowの高精度タイマーでSharedArrayBufferに結果を書き込むことで、高精度なクロックを実装することができる。
このクロックを使うことで、そこそこ正確なメモリアクセスの相対時間を計測することができ、キャッシュメモリのチェックに利用することが可能であった。
このソフトウェアクロックの実装精度を下げるためにSharedArrayBufferの無効化とperformance.nowの精度変更が行われた。

それ以外

Per Site Isolation

ドメインレンダリングプロセスを分離する。ただしメモリ使用量が20%ほど増える。

それ以外の部分での対応、BTBの制御やOut-of-orderの抑制は不可能かパフォーマンスペナルティがでかすぎるため、Side-Channel-Attackを非効率化することにとりあえず重点が置かれている。

まとめ

これも完全な対応ではない上に、
SharedArrayBufferが使えなくなるというWebの後退が起きてしまった。

Spectre and Meltdownについて

今回CPUに依存する脆弱性が発見されて大きな問題となっている。
そこで正月休みを使ってこの問題の解説を試みる。

Disclaimer

私はセキュリティの専門家ではないので間違えた情報があるかもしれない。
一次情報を載せておくので怪しい場合にはそこにアクセスして自分で確認するように。
この情報を鵜呑みにしておきたいかなる問題にも責任は負いかねる。

今回の脆弱性についてのWEBページ
業務で問題の解決を行う場合にはこのページを参照すること。

Meltdown and Spectre

概要

今回は2つの脆弱性が問題になっている。
1つ目はMeltdownと名付けられており、CPUのout-of-order実行を利用したもの。
2つ目はSpectreというCPUの投機的実行を利用したもの。
今回この問題が深刻なのは、どちらもCPUのパフォーマンス最適化のために存在する機構であり、モダンなほぼすべてのCPUに存在すること、
悪意のあるコードとそうでないコードの見極めが非常に難しいことなどから、解決の難しい問題となっている。

Meltdown

Meltdownから解説していく。
Meltdownと名付けられたこの問題はCPUのout-of-order実行の隙を突いた攻撃方法である。

out-of-order

out-of-orderと言うのはモダンなCPUが搭載しているパフォーマンス最適化手段である。
現在のCPUはアセンブリ命令をμOpsという更に小さなCPUのオペレーションに分割して実行する。
このμOpsに分解された命令はReorder-BufferSchedulerによってデータの依存関係が計算されて、実行順が変更される。
結果としてそれぞれ依存関係から独立した命令は順序に関係なく実行され、依存がある部分は依存先の命令が完了次第即実行される。

以下が今回の問題となる疑似コードだが、

gist4ad97b3858f184ca74efbbfe54e845ef

4行目のmov命令と5行目のshl命令は依存関係があるものの、それ以外はすべて予めμOpsに分解されて実行される。

以下はWikipediaからの引用

OoOでは、命令及び実行結果を一時溜めておく場所を作り、命令の実行を次のように細分化する。

1 命令フェッチ。
2 命令にリオーダ・バッファ(reorder buffer)のエントリを割り当てる。
3 命令を命令待ち行列または命令発行キュー(reservation station, issue queue)に送る(dispatch)。
4 命令待ち行列内の命令は、入力オペランドが得られるまで実行されない。入力オペランドが得られた段階で、待ち行列内にそれより古い命令があっても先に待ち行列から取り除かれ、実行されることになる。
5 命令が適当な実行ユニットに対して発行(issue)され、実行される。
6 実行結果がリオーダ・バッファに格納される。
7 リオーダ・バッファ内の命令のうち、最も古い命令の実行が完了すると、その実行結果はレジスタファイルに書き戻され、命令はリオーダ・バッファから取り除かれる。これを卒業ないしリタイア(graduation, retire)ステージと呼ぶ。命令待ち行列とは異なり、より新しい命令が実行完了状態であっても、それより古い命令がリオーダ・バッファ内にリタイアせずに残っている場合は、その(より新しい)命令がリタイアすることはできない。

アウト・オブ・オーダー実行 - Wikipedia

Preventing reading Karnel Memory from User space

上の例で示した疑似コードは実行するとカーネルの特権メモリをユーザースペースで読み込んでいるため例外を発生させる。
そのため、当然ユーザースペースからカーネルメモリを読み込むことは不可能である。
しかし後に述べるTransient Instructionを経由することでカーネルメモリをCPUキャッシュに載せることが可能になる。

Transient Instruction

ちょっとどう翻訳していいかわからないのだが、これはout-of-order実行によって実行される、
本来の実行パスでは実行されるはずのない命令である。

以下に擬似コードを示す。
このコードは擬似コードであり実際には動作しない。

int main() {
  char arr[1];
  Exception e;
  throw e;
  arr[data * 4096]
}

この擬似コードarr[data * 4096]は本来throw eが例外を投げることによって実行が中断されるため実行されないのだが、
out-of-orderによってarr[data * 4096]のメモリアクセスが実行される。

Reading Privilleged Memory

以上のテクニックを駆使することによって特権がなくても特権が必要なメモリの値をロードすることができる。

コードを再掲する。

gist4ad97b3858f184ca74efbbfe54e845ef

  • まずはline 4mov命令を発行しrcxにあるカーネルメモリの内容を読み込む
  • line 5alに格納した命令にアクセスして依存を生成する
  • line 6は最適化に対する対応なので無視
  • line 7raxつまり、先程カーネルメモリの内容を読み込んだアドレスに対して間接参照をする。

これらの処理がμOpsに分解されout-of-orderによって、line 7line 5/6の命令完了待ち状態になり、
line 5で例外が発生するよりも先にline 7が実行される。
こうすることで例外が発生するよりも先に格納されたメモリにアクセスするすることが可能になる。

Side-Channel-Attack

しかし、上記の方法を利用してもout-of-orderの実行結果は巻き戻されて取得ができない。
ここでSide-Channel-Attackを利用する。
Side-Channel-Attackとは外からハードやCPUの状態を観測することで値を取得するという方法である。
今回のペーパーではFlush+Reloadという方法を利用していた。
Flush+Reloadについては以下

https://eprint.iacr.org/2013/448.pdf

この方法を使うことでline 7でのメモリアクセスを計測し、
キャッシュメモリを調べて、そのメモリアクセスにかかった時間を計測することでどのアドレスがキャッシュされているかを取得できれば、
秘密の値のみに依存したアドレスが取得できるようだ。

また攻撃手法として例外を握りつぶすためにプロセスのforkを行い、その中でこれらの攻撃を行い、
メインプロセスでメモリアドレスを調べる方法が提案されている。

Spectre

こちらはCPUの投機的実行という機能を利用したものでMeltdownと似ているが、より実行しやすい。

投機的実行 (Speculative Execution)

CPUは分岐命令(if文とか)を実行する際に、パフォーマンス最適化のために過去に分岐した履歴から分岐先を予想して、
条件分岐の結果評価が完了する前にthen節やelse節を実行する。
その後条件分岐が確定し、投機的実行した結果の値が必要なくなれば、その結果はそのまま捨てられる。
つまりMeltdownみたいに実行されてほしくないコードが実行されることがありうる。 ちょっと嫌な雰囲気になってきたね。

Side-Channel-Attack

やはりここでもCPUキャッシュの状態を観測することで値を取得する。
以下に擬似コードを示す。

if (x < array1_size)
  y = array2[array1[x] * 256];

以下はペーパーに記載されていたシナリオである。

ここでarray2[array1[x] * 256]x < array1_sizeが確定する前に実行されるとし、xは取得したいアドレスの値とする。
するとarray1[x]がキャッシュから取得され、アドレスkが手に入る。
その後array2[k]にアクセスすることで、キャッシュミスが起こり、その間にx < array1_sizeが確定することで、すべての結果が破棄される。
しかしarray2[k]への投機的実行はすでにCPUキャッシュに変化を起こしてしまっているのでそれを観測することで目的のデータを取得することができる。

Javascirpt

ペーパーによるとjavascriptでも実行できるためそれなりに危険そうである。
V8のデバッグシェルであるd8で実行して成功したようなので結構ダメそう。

Vendors

まとめ

ちょっと内容が複雑なため間違いを含んでいる箇所があったら申し訳ない!
とにかく基本は1次情報にあたってほしい。

より詳しい方、コメント等で修正があったらしていただけると助かります。

もう一度掲載しとく

Meltdown and Spectre

V8 javascript engineについての細かい話 (Node.js Advent Calendar 2017)

Node.js Advent Calendar 2017 25日目の記事です。トリとなります。

さて先日11/26・27日に行われたNode学園祭でv8について発表させて頂いたが、
30分という制約上色々カットせざるを得なかった。
またv8のコードを読む・コントリビュートする上で伝えられる事も色々と溜まったので一度アウトプットすることにした。
というわけでまとまりのない記事になる可能性が高いがご容赦いただけると助かります。

事前資料

以下のスライドがNode学園祭の発表資料なので読んどいていただけると理解がはやいかも

speakerdeck.com

前準備

チェックアウト

v8はGitHubに直接はホスティングされていない。
GitHub上にあるv8リポジトリはミラーで実際にはchromium.googlesource.comホスティングされている。
ただし開発の際にはGitHubリポジトリをフォークしてgit remote add fork git@github.com:<user-name>/v8.gitとかしてforkリモートを追加してやるとよい。 あとは実際にpushして保存したい場合にはこのGitHubのフォークに対して行う。
なぜこんな面倒な事をしているかというと、v8のリポジトリGitHubではないためgit pushを使わない。
git clというコマンドを利用するのだが、このコマンドでgit cl uploadとしてもGerritにレビューを送るだけでpush相当のことはできない。
その為GitHubをブランチの保存先に利用している。

さて、v8を実際に開発するためには最初にこのページを確認すると良い。
Contributing · v8/v8 Wiki · GitHub

ただしあんまり親切ではないので軽く説明すると、まず最初に以下のステップに従ってdepot_toolsをインストールする
depot_tools_tutorial(7)
インストールしてパスを通したら、gclientコマンドが叩けるか確認する。
その後コードを以下の要領でチェックアウトする。
Using Git · v8/v8 Wiki · GitHub
あとはgit checkout -b foo-branchで適当なブランチを作って作業を開始する。

ビルド

一旦チェックアウトできたらビルドをしてみる。
現在v8はGNというメタプロジェクトビルドツールを利用しており、以下のpythonコマンドでビルド設定を出力できる。

X64の例

DEBUG

./tools/dev/v8gen.py x64.debug -vv

OPT_DEBUG

./tools/dev/v8gen.py x64.optdebug -vv

RELEASE

./tools/dev/v8gen.py x64.release -vv

次にビルドを行うのだが、ビルドにはNinjaというビルドツールを利用しており、以下のコマンドでビルドが開始できる。

DEBUG

ninja -C out.gn/x64.debug

OPT_DEBUG

ninja -C out.gn/x64.optdebug

RELEASE

ninja -C out.gn/x64.release

後はビルド完了を待つだけ。
ちなみにフルビルドには2.5 GHz Intel Core i7 16GB Memoryで30分近くかかるので辛抱強く待つ。

コミット

作業が完了したらいつも通りgit add .して、git commitでコミットコメントを書く。
コードをコミットする場合にはgit cl formatで最初に全ファイルをフォーマットし、git cl uploadでコードをGerritにコミットする。
この際chromium.orgメールアドレスを持っていないとWarningが表示されるもののここはYを押して先に進む。
その後コミットメッセージの入力を求められるが、gitのコミットメッセージを利用する場合にはそのままEnterでオッケー。

レビュー

もしレビューを開始する場合にはgit cl ownersコマンドでレビュアーを探し出して、GerritのReviewsにそのレビュアーを追加して待つ。

エディタ・IDE

自分はEmacs + RTagsを利用している。 この辺の記事が参考になった。C++11時代のEmacs C++コーディング環境 - Qiita
またv8のコミッターに直接聞いたところ、CLionを使ってると言っていた。CLion: A Cross-Platform IDE for C and C++ by JetBrains
ただし、自分の環境ではしょっちゅうフリーズしていたので諦めた。
あとはvimが多いみたいだが、vimはよくわからんので頑張ってC++環境作ってください。
VSCodeは無理だった。
Atomってなんだっけ?

v8のコード構成

ディレクトリ構成概要

v8のソースコードは全てsrcディレクトリに格納されており、以下のような構成になっている。

src ---+
       |
       +---arm
       +---arm64
       +---mips
       +---mips64
A      +---ia32
       +---x64
       +---ppc
       +---s390
       +---wasm
       +---asmjs
       |
       +---ast
       +---compiler
B      +---compiler-dispatcher
       +---interpreter
       +---parsing
       |
       +---js
       +---builtins
C      +---runtime
       +---snapshot
       +---regexp
       +---profiler
       |
D      +---ic
       |
       +---heap
E      +---heap-symbols.h
       +---zone
       +---objects
       |
F      +---inspector
       |
       +---base
       +---debug
       +---tracing
       +---extensions
G      +---libplatform
       +---libsampler
       +---third_party
       +---trap-handler
       |
       +---*.cc/*.h
       .
       .
       .

ファイル数が非常に多くすべてを説明し切るのは非常に難しいので一旦概略を述べると、

  • Aグループ
    • ディレクトリ群はassemblerコードやdisassembler、macro-assembler、simulator等、CPU毎の個別コードが格納されている。
  • Bグループ
  • Cグループ
    • JSのビルトイン関数・v8内部の実行時ヘルパ関数等が格納されている。
  • Dグループ
    • Inline Cache周りのコードが格納されている。
  • E
    • オブジェクトモデルとメモリ周りのコードが格納されている。
  • F
    • インスペクタ
  • G
    • デバッグやプラットフォーム抽象化層のコードを格納している。

とこんな感じで分類できる。
ただしこれも結構苦しい分類で実際にはどこのディレクトリにも属していないsrc直下のファイルが各グループに相当するコードを実装していたりと、結構見境がない感じ。

主要ファイル

恐らくよく見ることになるソースを列挙しておく。

  • api.h/api.cc
    • Embedder向けのAPIが定義されている。
  • objects.h/objects.cc
    • v8のオブジェクトモデルすべてが定義されており objects.ccに関しては19366行ある。
  • compiler/compiler.cc
    • コンパイルのエントリポイントになるのでここからコードを追うことが多い。
  • compiler/pipeline.cc
    • compiler.ccからつながってここにたどり着く。TurboFanと呼ばれている箇所
  • runtime/runtime-*.cc
    • ランタイム関数が定義されている。ここもよく見る。
  • builtins/builtin-*.cc
    • より高速なランタイム関数群。CodeStubAssembler(あとで解説)かAssemblerで記述されている。
  • interpreter/*.cc
    • いわゆるIgnitionのコードがここに収まっている。
  • ic/*.cc
    • Inline Caching周りの実装・ランタイムが格納されている。

v8の内部実装

ここからは実際に内部で使われている主要な機能を紹介していく。

公開API

v8::HandleScope

v8のGCから割り当てられたオブジェクトをC++の世界でも監視するための仮想スコープを生成する。
下のv8::Localで詳しく解説する。

v8::Local

おそらく最もよく見ることになるクラス。
v8はGCを持っているが、C++にはGCは無い。
代わりにRAII(Resource Acquisition Is Initialization)と呼ばれるリソースの確保・破棄をメモリと紐付けて行う方法が一般的である。
C++にはデストラクタと呼ばれる、スタックに割り当てられたクラスがスコープを抜けて破棄される際に必ず呼ばれる関数があり、
そのクラスでポインタをラップすることでスコープを抜けた時に一緒にポインタを破棄するという使い方をよくする。いわゆるスマートポインタと呼ばれる機能である。
v8::Localはヒープに割り当てたオブジェクトをC++の世界で監視するためのラッパクラスで、デストラクタが呼ばれれたタイミングで現在のHandleScopeと共に削除される。

例.

void test() {
  v8::Isolate* isolate = v8::Isolate::GetCurrent();
  v8::HandleScope handle_scope;

  v8::Local<v8::Array> array = v8::Array::New(isolate, 3);
  ...
}

一度v8::HandleScopeが生成されるとv8::Localはすべてそのv8::HandleScopeに割り当てられる。
そのため、test関数が終了したタイミングでhandle_scopeのデストラクタが呼び出されると、そのv8::HandleScopeに紐づくすべてのv8::Localも同時に削除される。

v8::Handle

v8::Localでラップされているが、実際にv8::HandleScopeに紐付いているクラス。
apiによってはこっちのv8::Handleを返すやつもあるが、まあ基本的にはv8::Localと同じように使えば良い。

v8::Isolate

最初に説明すべきか悩んだが、一旦v8::Localを先に回した。
v8::Isolateはv8のコードベースを貫く基礎になる部分でかなり特殊な作りになっている。
もともとv8はstaticメソッドが非常に多く、マルチスレッドについてあまり考えていない作りになっていた。
まあ、これはChromium側でプロセス分離してv8を起動すればよかったので問題はなかったのだが。
さて、いざEmbedder側でマルチスレッド化しようとするとかなり問題を引き起こすことがわかった。
そのため、このv8::Isolateという仕組みを結構無理やり組み込んだ。

v8::Isolateがどんなものかというと、Thread Local Storage(Tls)に格納された巨大なオブジェクトになっており、
実行コンテキストに紐づくグローバルな情報をほぼ全て格納している。
Tlsに格納されているのでスレッド毎に違うv8::Isolateを透過的に持つことが可能でEmbedder側はスレッドをあまり意識せずにコードを書くことが可能になっている。
内部で利用する様々なオブジェクト(FixedArray)やHidden Classを表すMapクラス等もこのv8::Isolateから生成している。
このクラスはほぼすべての箇所に渡されていて、v8::Isolate無しではコードを書くのは難しい状態になっている。

上記のサンプルコードを再度使うと

void test() {
  v8::Isolate* isolate = v8::Isolate::GetCurrent();
  v8::HandleScope handle_scope;

  v8::Local<v8::Array> array = v8::Array::New(isolate, 3);
  ...
}

この関数でもv8::Isolateを渡しているのがわかる。
v8::Array::Newなどとしているが実際にArrayを生成しているのはv8::Isoalteである。
そのため、v8の内部ではあまりスレッドの競合について考える必要が無く、まあなかなか便利な仕組みである。

v8::internal

外部公開API以外のクラス等はすべてv8::internal名前空間に定義されている。
長いのでv8::iに省略する。

オブジェクトモデル

v8は非常に特殊な作りになっており、C++の中に独自のオブジェクトモデルを作り出している。
そのオブジェクトモデルはsrc/objects.hの冒頭コメントに記載されており、
それを簡略化して抽出するとこうなる。

  • Object
    • Smi (immediate small integer)
    • HeapObject (superclass for everything allocated in the heap)
      • JSReceiver (suitable for property access)
        • JSObject
        • JSProxy
      • FixedArrayBase
        • ByteArray
        • BytecodeArray
        • FixedArray
        • FixedDoubleArray
      • Name
        • String
        • Symbol
      • HeapNumber
      • BigInt
      • Cell
      • PropertyCell
      • PropertyArray
      • Code
      • AbstractCode, a wrapper around Code or BytecodeArray
      • Map
      • Oddball
      • Foreign
      • SmallOrderedHashTable
      • SharedFunctionInfo
      • Struct
      • WeakCell
      • FeedbackVector

v8::i::Objectを基底クラスとしたオブジェクトツリーを作り出しており、
v8内部で使用されるほぼすべてのクラスはv8::i::Objectを継承している。javaみたいだね。
こういうわかりやすいヒエラルキーがあるのでさぞ読みやすいかと思いきや、コードは非常に複雑で...まあ読みやすくはない。
v8はこのオブジェクトモデルをうまく機能させるためにC++のやり方に従わない。
どういうことかと言うとこれらのクラスはフィールドをC++のクラスを通じて実装していない。
これらのクラスはあくまでメモリレイアウトをC++の世界で表現するためだけに存在しており、すべてのフィールドはthisポインタに対して直接オフセット指定して取得している。
つまりC++のオブジェクトレイアウトを無視して、自分たちで完全にメモリレイアウトをコントロールしている。
擬似コードで表現すると以下のようになる。

class SomeObject {
  Value* get_field1() {
    char* self = reinterpret_cast<char*>(this);
    self += header_offset;
    return Value::Cast(self);
  }
  void Initialize() {
    char* self = reinterpret_cast<char*>(this);
    self += header_offset;
    *self = Smi::Cast(1);
  }
};
static const size_t OBJECT_SIZE = sizeof(char) * 32;
SomeObject* object = reinterpret_cast<SomeObject*>(malloc(OBJECT_SIZE));
object->Initialize();
object->get_filed1(); // 1

この様に自分でフィールドのオフセットを制御している。
さて、このオブジェクト階層の頂点からチェックしていこう。
まずv8::i::Objectは以下の2つに分岐する。

  • Smi
    • 31ビット整数、ポインタアドレスの末尾は常に0
    • ヒープに確保されることはない
  • HeapObject
    • 4バイトアライメントの32ビットポインタ。アドレス末尾は1
    • ヒープに確保されたオブジェクト。GCの対象になる。

HeapObject

まずはv8::i::HeapObjectから。
v8::i::Objectは上述のように直接メモリレイアウトをいじっているので
HeapObjectを継承したオブジェクトはフィールドにアクセスする場合には以下のようなマクロを使っている。

#define FIELD_ADDR(p, offset) \
  (reinterpret_cast<byte*>(p) + offset - kHeapObjectTag)

#define READ_FIELD(p, offset) \
  (*reinterpret_cast<Object* const*>(FIELD_ADDR_CONST(p, offset)))

// こちらはGCのConcurrentマーキングがONになっている場合にアトミックにフィールドを更新するために  
// AtomicWordを使ったバージョンと通常のものに分岐している。
#ifdef v8_CONCURRENT_MARKING
#define WRITE_FIELD(p, offset, value)                             \
  base::Relaxed_Store(                                            \
      reinterpret_cast<base::AtomicWord*>(FIELD_ADDR(p, offset)), \
      reinterpret_cast<base::AtomicWord>(value));
#else
#define WRITE_FIELD(p, offset, value) \
  (*reinterpret_cast<Object**>(FIELD_ADDR(p, offset)) = value)
#endif

SMI_ACCESSORS(FixedArrayBase, length, kLengthOffset)

#define SMI_ACCESSORS_CHECKED(holder, name, offset, condition) \
  int holder::name() const {                                   \
    DCHECK(condition);                                         \
    Object* value = READ_FIELD(this, offset);                  \
    return Smi::ToInt(value);                                  \
  }                                                            \
  void holder::set_##name(int value) {                         \
    DCHECK(condition);                                         \
    WRITE_FIELD(this, offset, Smi::FromInt(value));            \
  }

// 実際には以下のように展開される。

int FixedArrayBase::length() const {
  DCHECK(condition);
  Object* value = (*reinterpret_cast<Object* const*>(
  reinterpret_cast<const byte*>(this) + kLengthOffset - kHeapObjectTag)
  return Smi::ToInt(value);
}

int FixedArrayBase::set_length(int value) const {
  DCHECK(condition);
  base::Relaxed_Store(
      reinterpret_cast<base::AtomicWord*>(
          reinterpret_cast<byte*>(this) + kLengthOffset - kHeapObjectTag);
      reinterpret_cast<base::AtomicWord>(Smi::FromInt(value)));
}

重要なのは、

reinterpret_cast<const byte*>(this) + kLengthOffset - kHeapObjectTag

の部分で、thisポインタに特定のフィールドのオフセットを足したあと、kHeapObjectTagを引いているのがわかる。
ちなみにkHeapObjectTagの定義は以下。

const int kHeapObjectTag = 1

ただの1、つまりポインタアドレス末尾に1を立てるだけ。
v8::i::HeapObjectは割り当て時にkHeapObjectTag分多めに確保してから割り当てる。
以下がサンプルコード

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

const int kHeapObjectTag = 1;
const int kHeapObjectTagSize = 2;
const intptr_t kHeapObjectTagMask = (1 << kHeapObjectTagSize) - 1;

inline static bool HasHeapObjectTag(const char* value) {
  return ((reinterpret_cast<intptr_t>(value) & kHeapObjectTagMask) ==
          kHeapObjectTag);
}

int main() {
  auto allocated = reinterpret_cast<char*>(
      malloc(sizeof(char) * (2 + kHeapObjectTag)));
  auto heap_object = allocated + kHeapObjectTag;
  heap_object[0] = 'm';
  heap_object[1] = 'v';
  printf("%ld %ld %p %p %d\n", reinterpret_cast<intptr_t>(allocated),
         reinterpret_cast<intptr_t>(heap_object), allocated, heap_object,
         HasHeapObjectTag(heap_object));
  free(allocated);
}

実行すると私の環境では以下の結果になる。

140289524108464 140289524108465 0x7f97b3400cb0 0x7f97b3400cb1 1
見事にアドレスの末尾1が立っている。

またv8::i::HeapObjectは自分自身の型を識別するためにHidden Classを表すv8::Mapオブジェクトを先頭に持っている。

そのためv8::i::HeapObjectもメモリレイアウトは以下のようになる。

+-----+-----------------------+--------+
| Map | Derived Object Header | values |
+-----+-----------------------+--------+

必ず先頭に型を表すv8::Mapを持っているため、そこを見ればv8::i::HeapObjectの型がわかる。
またDerived Object Headerと書かれている部分は継承先のオブジェクトによって異なる(v8::i::FixedArrayならlengthフィールドだったり)。

以下がMapとJSObjectを簡略化した表したC++コード

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

const int kHeapObjectTag = 1;
const int kHeapObjectTagSize = 2;
const intptr_t kHeapObjectTagMask = (1 << kHeapObjectTagSize) - 1;

inline static bool HasHeapObjectTag(const char* value) {
  return ((reinterpret_cast<intptr_t>(value) & kHeapObjectTagMask) ==
          kHeapObjectTag);
}

class Map {
 public:
  enum InstanceType {
    JS_OBJECT,
    JS_ARRAY,
    JS_STRING
  };

  void set_instance_type(InstanceType instance_type) {
    instance_type_ = instance_type;
  }

  InstanceType instance_type() {
    return instance_type_;
  }
 private:
  InstanceType instance_type_;
};

const int kHeaderSize = sizeof(Map);
typedef char byte;
typedef char* Address;

class HeapObject {
 public:
  char value() {return reinterpret_cast<Address>(this)[0];}
  Map::InstanceType instance_type() {
    return reinterpret_cast<Map*>(
        reinterpret_cast<Address>(this) - kHeaderSize)->instance_type();
  }
  void Free() {
    auto top = reinterpret_cast<Address>(this) - kHeaderSize - kHeapObjectTag;
    free(top);
  }
 protected:
  static Address NewType(Map::InstanceType instance_type, size_t size) {
    auto allocated = reinterpret_cast<Address>(
        malloc(sizeof(byte) * (size + kHeaderSize + kHeapObjectTag)));
    auto map = reinterpret_cast<Map*>(allocated);
    map->set_instance_type(instance_type);
    return allocated + kHeaderSize + kHeapObjectTag;
  }
};

class JSObject: public HeapObject {
 public:
  static JSObject* New() {
    auto a = NewType(Map::JS_OBJECT, 1);
    a[0] = 'o';
    return reinterpret_cast<JSObject*>(a);
  }
};

class JSArray: public JSObject {
 public:
  static JSArray* New() {
    auto a = NewType(Map::JS_ARRAY, 1);
    a[0] = 'a';
    return reinterpret_cast<JSArray*>(a);
  }
};

class JSString: public JSObject {
 public:
  static JSString* New() {
    auto a = NewType(Map::JS_STRING, 1);
    a[0] = 's';
    return reinterpret_cast<JSString*>(a);
  }
};

int main() {
  JSObject* objects[] = {
    JSObject::New(),
    JSArray::New(),
    JSString::New()
  };

  for (int i = 0; i < 3; i++) {
    auto o = objects[i];
    switch (o->instance_type()) {
      case Map::JS_OBJECT:
        printf("JSObject => %c\n", o->value());
        break;
      case Map::JS_ARRAY:
        printf("JSArray => %c\n", o->value());
        break;
      case Map::JS_STRING:
        printf("JSString => %c\n", o->value());
        break;
    }
  }

  for (int i = 0; i < 3; i++) {
    objects[i]->Free();
  }
}

実行するとJSObject => o, JSArray => a, JSString => sが出力される。
かなり例が巨大になってしまったが、これでヒープに割り当てられたオブジェクトの型を正確に分類できているのがわかると思う。

さらにSmiが何かを説明しよう。

Smi

SmiはSmall Integerの略で、31ビットまでの整数を直接ポインタ領域に確保する。
またRubyでも同じ手法が取られているようだ。
通常ポインタはそれだけで32ビットCPUなら4バイト、64CPUなら8バイトを使う。
つまり31ビットまでの整数ならば直接ポインタの代わりに格納できるわけだ。
このようにポインタ領域に確保してヒープを使わないことでメモリ節約・高速化の両方を成し遂げている。

さてどのように格納するかというと直接int値をreinterpret_cast<T*>してポインタに変換してしまう。

class Smi {
 public:
  static Smi* FromInt(int value) {
    return reinterpret_cast<Smi*>(value);
  }

  int value() {
    return reinterpret_cast<intptr_t>(this);
  }
};

Smi* NewSmi(int value) {
  return Smi::FromInt(value);
}

int main() {
  printf("%d %d\n", NewSmi(120)->value(), NewSmi(110)->value());
  // out 120 110
}

上記の例を見ていただければわかるだろう。
さらにv8::i::HeapObjectの場合には下位1ビットを立てたが、Smiの場合には末尾0をタグとして利用しているので、
キャストしただけで直接数値演算が可能である。そのためオーバーヘッドもない。
また64ビットCPUならばポインタは64ビットなのでより大きな整数が格納できるが、32ビットとの互換性のため31ビットの領域しか使用しない。
64ビットの場合のビットレイアウト

+----------------+-----------------+------------------+
| 31 bit integer | 32 bit zero bit | 1 bit smi tag(0) |
+----------------+-----------------+------------------+

単純に下位32ビットをゼロ埋めするだけ。

JSReceiver

プロパティアクセス可能なJSオブジェクトを表す。つまりほぼすべてのJSオブジェクトを表す。
JSReceiverの下には上述のJSObjectが存在し、これがjsのObjectクラスを表す。
さらにJSObjectの下には以下のような階層がある。

  • JSArray
  • JSArrayBuffer
  • JSArrayBufferView
    • JSTypedArray
    • JSDataView
  • JSBoundFunction
  • JSCollection
    • JSSet
    • JSMap
  • JSStringIterator
  • JSSetIterator
  • JSMapIterator
  • JSWeakCollection
    • JSWeakMap
    • JSWeakSet
  • JSRegExp
  • JSFunction
  • JSGeneratorObject
  • JSGlobalObject
  • JSGlobalProxy
  • JSValue
    • JSDate
  • JSMessageObject
  • JSModuleNamespace
  • WasmInstanceObject
  • WasmMemoryObject
  • WasmModuleObject
  • WasmTableObject

これらのv8::i::JS~クラスは我々EmbedderがAPI経由で利用するv8::Stringv8::Array等のクラスの本当の姿で、
v8::String等のクラスはただのラッパークラスでしかない。
実際の実装はすべてv8::i::JS~クラスが持っている。

FixedArrayBase

v8で頻出するクラスであるv8::i::FixedArrayのベースとなる実装。
v8は内部のいたるところでこの固定長配列を利用しており、何度もお目にかかることになる。 v8::i::FixedArrayは更に以下の様な階層を持っている。

  • DescriptorArray
  • FrameArray
  • HashTable
    • Dictionary
    • StringTable
    • StringSet
    • CompilationCacheTable
    • MapCache
  • OrderedHashTable
    • OrderedHashSet
    • OrderedHashMap
  • Context
  • FeedbackMetadata
  • TemplateList
  • TransitionArray
  • ScopeInfo
  • ModuleInfo
  • ScriptContextTable
  • WeakFixedArray
  • WasmSharedModuleData
  • WasmCompiledModule

特にv8::i::DescriptorArrayはプロパティディスクリプタを格納している配列で、
プロパティアクセスの際によく取得する。

オブジェクトに関しては1記事では限界があるので次に進む。
次はv8内部のコード生成部分に関して

CodeGeneration of v8

v8はいくつかのコード生成方法がある。
v8-devグループでスライドがあったのでそれを参考にまとめると、

  • C++
    • cons
      • C++から呼び出すのが高速
      • 実行も高速
      • 比較的読みやすい
      • 拡張、デバッグがやりやすい
      • メモリがすべてのIsolateを通して共有されるためOSがメモリ不足になった場合に破棄される。
    • pros
      • JSから呼び出すのが遅い
    • summary
      • 巨大な関数やパフォーマンスクリティカルではない箇所には良い
  • C++(External Reference)
    • runtimeではなく直接C++の関数を登録する方式で登録した関数しか呼び出せないが直接C関数として呼べるので高速
    • cons
      • JSから呼び出すのが通常のC++と比べて早い
    • pros
      • allocationができない
      • 初期化が結構面倒
    • summary
      • 頻繁に呼ばれるような小さな関数には便利
  • CodeStubAssembler(CSA)
    • pros
      • JSから呼び出すのが早い、JSに戻るのも早い
      • 実行も高速
    • cons
      • 冗長
      • デバッグが厳しい
      • C++から呼び出すと遅い
      • isolate毎にメモリを圧迫する
    • summary
      • 小さな関数やパフォーマンスが必要な箇所に向いている
  • Javascript
    • pros
      • JSから呼び出すのが高速
    • cons
      • 意図せぬ型情報の汚染が起こりうる。パフォーマンス問題も起きがち。
      • セキュア(getter関数を意図せず呼び出したり、monky-patchingされてしまったり)に作るのが非常に難しい
      • Compiler組み込み関数やruntime関数呼び出しが必要で、これが高コスト
    • summary
      • 使わないこと!
  • アセンブリ
    • pros
      • とにかく早い
      • コールスタックを操作できる
    • cons
    • summary
      • 使わないこと!

という感じでコードを書く手段がC++, C++(Ex)、CSA、javascriptアセンブリの約5種類ある。
javascriptアセンブリはすでに新規で書かれることはほぼない。
以前はv8はjavascriptでランタイムを書いていた時期があったがほぼなくなった。
現在は低速でも問題ない箇所や新たに実装されるSpecに関してはC++で、それ以外のパフォーマンスが必要な箇所に関してはCSAで記述される。

さて次はCSAを解説する。

CodeStubAssembler (CSA)

v8の内部で利用されるDSL言語。
実はv8ではすでに新しくアセンブリ言語を記述することはあまりない。
その代わりアセンブリを出力するCSAを記述することでよりメンテナンス性が高く高速なコードを出力することができる。

以下にCSAの例を示す。

function fibonacci(num){
  var a = 1, b = 0, temp;
  const result = [];

  while (num >= 0){
    result.push(a);
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }

  return result;
}

C言語入門 - フィボナッチ数の計算 - サンプルプログラム - Webkaru

このフィボナッチ数を計算して配列に格納するjavascript関数をCSAに変換すると以下のようなコードになる。

TNode<JSArray> Fibonacci(TNode<Context> context) {
  TVARIABLE(var_a, MachineType::PointerRepresentation(), IntPtrConstant(0));
  TVARIABLE(var_b, MachineType::PointerRepresentation(), IntPtrConstant(1));
  TVARIABLE(var_temp, MachineType::PointerRepresentation());
  TVARIABLE(var_index, MachineType::PointerRepresentation());

  Node* fixed_array = AllocateFixedArray(PACKED_ELEMENTS, IntPtrConstant(11),
                           INTPTR_PARAMETERS, kAllowLargeObjectAllocation)

  Label loop(this), after_loop(this);

  Branch(IntPtrGreaterThan(IntPtrConstant(100), var_index), &loop, &after_loop);
  BIND(&loop);
  {
    StoreFixedArrayElement(fixed_array, SmiTag(var_index), var_a,
                           SKIP_WRITE_BARRIER);
    var_temp.Bind(var_a);
    var_a.Bind(IntPtrAdd(var_a, var_b));
    var_b.Bind(var_temp);
    Increment(&var_index, 1);
    Branch(IntPtrGreaterThan(IntPtrConstant(100), var_index),
           &loop, &after_loop);
  }
  BIND(&after_loop);
  Node* native_context = LoadNativeContext(context);
  Node* array_map = LoadJSArrayElementsMap(PACKED_ELEMENTS, native_context);
  Node* array = AllocateUninitializedJSArrayWithoutElements(
      array_map, SmiConstant(12), nullptr);
  StoreObjectField(array, JSArray::kElementsOffset, fixed_array);
  return array;
}

ある程度抽象化されているとは言えどうしても冗長なコードになってしまうが、アセンブリよりは遥かに読みやすいのではないだろうか?
これらは直接値を出力するのではなく、実行予定ツリーを組み立ててからツリーを巡回し、一つ一つの命令が自動的にアセンブリに置き換えられる。
ちなみにコンパイルしていないのでもしかしたらコンパイルエラーが出るかもしれない。

長くなりすぎたので内部の解説はこのあたりで終了する。

コードを読む

v8のコードを読むのは非常に面倒だが、いくつか方法がある。
まずはそれぞれのエディタのコードジャンプを使う。
まあこれでとりあえず定義とかはある程度見れるはず。
ただしv8は大量のマクロを使っており、クラスの関数定義すらマクロで行う場合があるので、どうしても定義が見つからない場合にはfind | grepも駆使したほうが良い。
またマクロで文字列結合されている場合もあるので、find src | grep '##FooBar'みたいな感じで##を使ってgrepする必要があるかもしれない。

デバッグする

コードを読んでも実行時の状態がわからなかったり呼び出し階層がわからない場合もあるので、ランタイムでは以下の方法でチェックすると良い。

  • C++
    • src/base/debug/stack_trace.hStackTraceクラスがあるので呼び出された箇所でStackTrace st;st.Print()を呼ぶと良い。
    • またv8::Objectクラスを継承しているオブジェクトはもれなくPrintメソッドを持っているので、a->Print()を呼ぶと中身が見れる。
  • CSA
    • Print()関数がCodeStubAssemblerに定義されているので、そこにNode*を渡すことでa->Print()を行うコードを出力してくれる。ただし、IntPtrTを渡すと落ちるので注意。その場合はSmiTagすれば良い。

あとはこれを繰り返すしかない。

まとめ

なんか本当にまとまりのない文章になってしまった。申し訳ない。
まあつまりv8のコード見るのも書くのも大変だってことです。

mallocを再実装した話

C++ AdventCalendarの12日目

普段私はWEBのフロントエンドを仕事にしている。
つまり使う言語はjavascript/typescript等のScript言語だ。
ただ前職や趣味、OSS等でC++によく触っていたので昔実装したmallocの話をすることにした。

mallocとは

mallocとはC言語のstdlib.hに含まれるメモリ割り当て関数のことで、
C++やその他の多くの言語で内部的に利用されている。
ヒープを割り当てる方法はいくつかあるが、このmallocがもっともメジャーといえるだろう。

mallocを再実装した

今回はmallocを自分で再実装してちょっと早くした話を書く。
再実装した理由は色々あるが最も大きな理由はただの好奇心。
yatscというtypescriptコンパイラC++で書こうと思って実装を始めたときに作った。
ただしyatsc自体は未完で飽きて終了。
作ってみて思ったが、実際にプロダクトで使う場合はシンプルなメモリプールとか作ったほうがよっぽど利口だと思う。

Inside malloc

malloc関数は現在のモダンな環境ではmmapを利用してメモリを確保、それを各チャンクに分けて管理しているはず。
細かいことは以下のスライドに詳しい。

www.slideshare.net

Direction of implementations

今回はGoogleのTLMallocの実装と上記のスライドをベースにjust-fitアロケータを作成することにした。

基本的な構成は以下の通り。
メインスレッドにあるCentralArenaが各スレッドのLocalArenaを管理しており、
それぞれのArenaはTls(Thread Local Storage)に格納されている。
また、各LocalArenaはスレッドが終了すると、free-listに格納されて空き状態となり、
新たにスレッドが生成された場合に再利用される。
LocalArena自体もlinked-listになっており、nextポインタで各スレッドのLocalArenaはつながっている。
さらにLocalArenaは内部にChunkを持ち、それらはChunkHeaderと後続の複数のHeapHeaderによって管理されている。

Tlsにヒープを格納することでスレッド毎にヒープ領域を分割し、スレッド競合を防ぎつつjust-fitアロケータでメモリの無駄も防ぐ。
というのが、このmalloc実装のキーポイントになる。
ちなみにTlsを実装するのは面倒だったので、AndroidTls実装をコピーした。
Tlsのコールバックまで実装されており非常に便利。サンキューGoogle

以下はCentralArenaからLocalArenaまでの図

+----------------+  +---------------+
|  CentralArena  |--|  Main Thread  |
+----------------+  +---------------+
      |     |  +------------+  +--------------+
      |     +--|  Thread-1  |--|  LocalArena  |
      |     |  +------------+  +--------------+
      |     |  +------------+  +--------------+
      |     +--|  Thread-2  |--|  LocalArena  |
      |     |  +------------+  +--------------+
      |     |  +------------+  +--------------+
      |     +--|  Thread-3  |--|  LocalArena  |
      |        +------------+  +--------------+
      +------------+  +--------------+  +--------------+
      |  free list |--|  LocalArena  |--|  LocalArena  |-- ...
      +------------+  +--------------+  +--------------+

CentralArena

CentralArenaはメモリのアロケーションを要求されると、 GetLocalArena関数を呼び出して、TlsからLocalArenaを取り出すか空いているLocalArenaをfree-listから探し出して割り当てる。

以下のような感じでAtomicにlockを行ってスレッド競合を防いでいる。

LocalArena* CentralArena::FindUnlockedArena() YATSC_NOEXCEPT {
  // If released_arena_count_ is zero,
  // that mean free arena is not exists.
  // So we simply allocate new LocalArena.
  if (released_arena_count_.load() == 0) {
    return StoreNewLocalArena();
  }

  LocalArena* current = local_arena_.load(std::memory_order_relaxed);

  while (current != nullptr) {
    // Released arena is found.
    if (current->AcquireLock()) {
      return current;
    }
    current = current->next();
  }

  // If released arena is not found,
  // allocate new LocalArena.
  return StoreNewLocalArena();
}

ちなみにAcquireLockは以下のような感じ。Atomicにロックしている。

YATSC_INLINE bool AcquireLock() YATSC_NOEXCEPT {
  bool ret = !lock_.test_and_set();
  if (ret) {
    central_arena_->NotifyLockAcquired();
  }
  return ret;
}

さて上記FindUnlockedArenaを使って空いたLocalArenaを探し出すのに失敗した場合、 そこで初めてメモリを割り当てることになる。
このメモリ割り当ては以下のような感じで行う。

LocalArena* CentralArena::StoreNewLocalArena() YATSC_NOEXCEPT {
  Byte* block = reinterpret_cast<Byte*>(
      GetInternalHeap(sizeof(LocalArena) + sizeof(InternalHeap)));

  LocalArena* arena = new (block) LocalArena(
      this, new(block + sizeof(LocalArena)) InternalHeap(
          block + sizeof(LocalArena) + sizeof(InternalHeap)));
  arena->AcquireLock();

  LocalArena* arena_head = local_arena_.load(std::memory_order_acquire);

  // Run CAS operation.
  // This case ABA problem is not the matter,
  // because the local_arena_ allowed only one-way operation
  // that is append new LocalArena.
  // So head of local_arena_ is change only when new local arena is appended.
  do {
    arena->set_next(arena_head);
  } while (!local_arena_.compare_exchange_weak(arena_head, arena));

  return arena;
}

// Get heap space that used to allocate LocalArena and ChunkHeader.
YATSC_INLINE void* CentralArena::GetInternalHeap(size_t additional) {
  return VirtualHeapAllocator::Map(
      nullptr, sizeof(ChunkHeader) * kChunkHeaderAllocatableCount + additional,
      VirtualHeapAllocator::Prot::WRITE | VirtualHeapAllocator::Prot::READ,
      VirtualHeapAllocator::Flags::ANONYMOUS
      | VirtualHeapAllocator::Flags::PRIVATE);
}

解説すると、まず最初にVirtualHeapAllocatorを利用してメモリを割り当てる。
このVirtualHeapAllocatormmapのプラットフォーム毎の差分を吸収したクラス。
このVirtualHeapAllocatorからLocalArenaInternalHeapという内部向けの管理ヘッダ分のメモリを割り当てる。
それをinplacement newを利用してLocalArenaに割り当てる。
つまりLocalArenaは以下のようなメモリレイアウトになる。

  sizeof(InternalHeap)            + sizeof(LocalArena)
+-------------------------------+   +--------------+
|  InternalHeap(hidden header)  |---|  LocalArena  |
+-------------------------------+   +--------------+

あとは割り当てたLocalArenaのロックを獲得して、local-arenaのリストに格納する。
このリストに追加するのも当然atomicに行わなければならないので、CAS(Compare And Swap)を利用してリストに追加する。
CASを使うとABA問題を気にしなければならないが、コメントにある通りlocal_arena_のリストは追加しか行わないのでABA問題は気にしなくて良い。
これでめでたくCentralArenaからロックフリーでLocalArenaを確保することに成功した。
次はLocalArenaを実装する。

LocalArena

LocalArenaこそがメモリ割り当てのコアになっていて、この部分が一番面倒くさい。
LocalArenaはメモリ割り当て要求を受けるとsmall_bin_とよばれる小さなメモリ専用のツリーにメモリを割り当てていく。
今回はこのツリーはRedBlackTreeを利用した。
このsmall_bin_に要求メモリサイズ毎のリストを作りそこに割り当てていく。

+--------------+
|  LocalArena  |
+--------------+
       |
       |        +--------------+
       +--------|  small_bin_  |
                +--------------+
                        |
            +-----------------------+
            |                       |
        +-------+               +-------+
        | 1byte |               | 2byte |
        +-------+               +-------+
            |                       |          
      +-----------+           +-----------+    
      |           |           |           |    
  +-------+   +-------+   +-------+   +-------+
  | 3byte |   | 4byte |   | 5byte |   | 6byte |
  +-------+   +-------+   +-------+   +-------+

こんな感じでsmall_bin_には各サイズ毎のchunkのリストが格納される。
これでjust-fitなアロケータになる。
ただし面倒だったのは、このsmall_bin_をstd::mapとかで実装するのはちょっと難しく、
結局自分でRBTreeを実装する羽目になった。
何故かと言うと、今はメモリアロケーションの途中なのでヒープから値を確保することは不可能で、
各Chunkに追加のメモリ割り当てで格納できるコンテナが必要だったからである。
自分で実装したRBTreeはIntrusiveRBTreeというクラスで、ある条件を満たせばヒープからメモリのアロケーションをしなくてもツリーを構成することができる。 その条件とは格納される値自身がコンテナの実装をしていること。 つまり格納される値がRbTreeNodeというRedBlackTreeのNodeを継承していれば、
RBTree自身はそれをつなぎ合わせるアルゴリズムの実装のみでよく、
メモリ割り当てを必要としないで済む。

ただし、small_bin_は名の通り小さなメモリのみを格納する場所なので、64KBを制限とし、
それを超える場合には直接CentralArenaから巨大なメモリ領域をmmapで割り当てる。
そのときにはSpinLockでロックをかけるので当然遅くなる。

これでjust-fitなbinが実装できた。
さてsmall_bin_に格納されるメモリを実装していく。
small_bin_に格納されるメモリはChunkHeaderという管理ヘッダと実際に値を割り当てる後続のブロックで構成される。

ChunkHeader

ChunkHeaderクラスは実際に値を割り当てるヒープを管理している。
ChunkHeaderの後ろには各Heapを管理するHeapHeaderがつながっている。 確保されているヒープはheap_list_に格納され、
空いているヒープはfree_list_に格納される。

+---------------+
|  ChunkHeader  |
+---------------+
     |     |
     |     +--------------+  +------------+  +------------+  +------------+
     |     |  heap_list_  |--| HeapHeader |--| HeapHeader |--| HeapHeader |
     |     +--------------+  +------------+  +------------+  +------------+
     | 
     |
     +--------------+  +------------+  +------------+  +------------+
     |  free_list_  |--| HeapHeader |--| HeapHeader |--| HeapHeader |
     +--------------+  +------------+  +------------+  +------------+

そしてChunkHeaderはメモリ確保の要求が来ると、最初にfree_list_を探索する。
もしfree_list_にHeapHeaderがあればそれをheap_list_にAtomicに繋いで返す。
空きがなければ、最後につながれたHeapHeaderの使用量を確認して、まだ格納できるのであればHeapHeaderに値を追加する。
もしHeapHeaderに空きが無ければ、新たにHeapHeaderを割り当てる。

YATSC_INLINE void* ChunkHeader::Distribute() {
  auto free_list_head = free_list_.load(std::memory_order_acquire);
  if (free_list_head == nullptr) {
    // If heap is not filled.
    if (heap_list_->used() < max_allocatable_size_) {
      // Calc next positon.
      Byte* block = reinterpret_cast<Byte*>(heap_list_) + heap_list_->used();
      // Update heap used value.
      heap_list_->set_used(heap_list_->used() + size_class_);
      return block;
    } else {
      // If heap is exhausted allocate new memory.
      Byte* block = InitHeap(AllocateBlock());
      auto heap_header = reinterpret_cast<HeapHeader*>(
          block - sizeof(HeapHeader));
      heap_header->set_used(heap_header->used() + size_class_);
      return block;
    }
  }

  // Swap free list.
  while (!free_list_.compare_exchange_weak(
             free_list_head, free_list_head->next())) {}
  return reinterpret_cast<void*>(free_list_head);
}

HeapHeader

HeapHeaderクラスは実際にヒープの値を直接管理しているクラス。
このHeapHeaderChunkHeaderから割り当てられる、1 MBでアライメントされたメモリブロックとなっている。
なぜ1 MBでアライメントするかというと、メモリの節約のためにHeapHeaderが確保しているメモリブロックは管理ヘッダを持っていない。
本来はメモリを削除する場合にHeapHeaderを参照するための情報が必要なのだが、1 MBでアライメントすることによって、
メモリの下位16ビットをマスクするだけで、HeapHeaderの先頭アドレスを取得することができるようになる。
こうすることで1割当ごとにX64なら最低でも8 byte、x86なら4 byteの節約になる。

CentralArenaにメモリのfree要求が来た場合には以下のようにポインタのアドレス下位16ビットをマスクして、
HeapHeaderを取得する。

ChunkHeader::kAddrMask~0xFFFF

auto h = reinterpret_cast<HeapHeader*>(
    reinterpret_cast<uintptr_t>(ptr) & ChunkHeader::kAddrMask);
ASSERT(true, h != nullptr);
ChunkHeader* chunk_header = h->chunk_header();
ASSERT(true, chunk_header != nullptr);
chunk_header->Dealloc(ptr);

構造は以下の図の通り

+----------------------------+  +----------------------+  +-----------------------+
|  HeapHeader(0x103e600000)  |--|  value(0x103e600008) |--|  value(0x103e000010)  | 
+----------------------------+  +----------------------+  +-----------------------+

削除する場合

+----------------------+                                +----------------------------+
|  value(0x103e600008) | => 0x103e600008             => |  HeapHeader(0x103e600000)  |
+----------------------+           ^^^^^ Mask heare.    +----------------------------+

概ねこんな感じでjust-fitでロックを必要としないメモリアロケータを実装することができた。
パフォーマンスだが、シングルスレッドではmallocの約5倍ほど高速化することができたが、
マルチスレッドでは1.2 ~ 1.1倍ほどしか高速化せずちょっとなぁ〜という感じ。
また64 KB以上のビックな割当を行うとほとんどmallocと変わらないのでここは改善の余地がありそう。

という感じでmallocを再実装した話でした。

全体像は以下のようになる。

+----------------+  +---------------+
|  CentralArena  |--|  Main Thread  |
+----------------+  +---------------+
      |     |  +------------+  +--------------+
      |     +--|  Thread-1  |--|  LocalArena  |
      |     |  +------------+  +--------------+
      |     |                         |                                                  
      |     |                         |        +--------------+                
      |     |                         ---------|  small_bin_  |                
      |     |                                  +--------------+                
      |     |                                          |                       
      |     |                              ------------+------------           
      |     |                              |                       |           
      |     |                          +-------+               +-------+       
      |     |                          | 1byte |               | 2byte |       
      |     |                          +-------+               +-------+       
      |     |                              |                       |           
      |     |                        ------+------           ------+------     
      |     |                        |           |           |           |     
      |     |                    +-------+   +-------+   +-------+   +-------+
      |     |                    | 3byte |   | 4byte |   | 5byte |   | 6byte |
      |     |                    +-------+   +-------+   +-------+   +-------+
      |     |                    +---------------+                                                             
      |     |                    |  ChunkHeader  |                                                             
      |     |                    +---------------+                                                             
      |     |                         |     |                                                                  
      |     |                         |     +--------------+  +------------+  +------------+  +------------+   
      |     |                         |     |  heap_list_  |--| HeapHeader |--| HeapHeader |--| HeapHeader |   
      |     |                         |     +--------------+  +------------+  +------------+  +------------+   
      |     |                         |                           +----------------------------+  +----------------------+  +-----------------------+  
      |     |                         |                           |  HeapHeader(0x103e600000)  |--|  value(0x103e600008) |--|  value(0x103e000010)  |  
      |     |                         |                           +----------------------------+  +----------------------+  +-----------------------+  
      |     |                         |                                                                        
      |     |                         +--------------+  +------------+  +------------+  +------------+         
      |     |                         |  free_list_  |--| HeapHeader |--| HeapHeader |--| HeapHeader |         
      |     |                         +--------------+  +------------+  +------------+  +------------+         
      |     |  +------------+  +--------------+
      |     +--|  Thread-2  |--|  LocalArena  |
      |     |  +------------+  +--------------+
      |     |  +------------+  +--------------+
      |     +--|  Thread-3  |--|  LocalArena  |
      |        +------------+  +--------------+
      +------------+  +--------------+  +--------------+ 
      |  free list |--|  LocalArena  |--|  LocalArena  |-- ...
      +------------+  +--------------+  +--------------+ 

まとめ

結果得られたのはロックフリーな実装の難しさとメモリ割当関連のバグは発見が不可能に近いという教訓であった。
意味不明なSegvがきつい。

参考

https://www.slideshare.net/kosaki55tea/glibc-malloc

ソースは https://github.com/brn/yatsc/tree/master/src/memory どす〜