clearstackの話 - 兼雑記

https://turingcomplete.fm/19#t=26:39 で僕のやったことに言及してくれて、「使ったスタックを消すなにかを浜地が作ったが、それは全く公開されていない」という趣旨の事が言われていました。でも実際のところなんか書いたけど、単に誰も興味を持たなかったというだけのことでした。

http://shinh.hatenablog.com/entry/20130728/1374990526

実際はclang pluginで、かつすごく適当にでっち上げただけで、効率は完全度外視だし正しく動いてるんだかもよくわからない、って感じでした。クラッシュはしなかったくらいの何か。当時の記述はすごい適当ぽいので、2点書いておきます。

当時のモチベーション

保守的GCが「やや病的なケースでポインタに見える整数値の参照先を残してしまう」てのはよく聞くわけですが、Rubyのバグかなんかで見たのは違うケースで、実際に過去にポインタだったが、もう使ってないマシンスタックに残ってるものが解放されない、というような話でした。

具体的にCレベルで考えると、VMのループてのはおおむね

switch (op) {
  case OP_X: {
    VALUE x = ...
    なんかする...
  }
  case OP_Y: {
    VALUE y = ...
    なんかする...
  }
}

とかそういう感じになっているわけです。ここで VALUE てのは tagged-pointer ですが、まあ要はポインタです。 VALUE x とか VALUE y ですが、少なくとも当時の GCC は x と y を同じスタックに割り付けるということはせず、かつ VM ループを処理する関数が結構複雑な関数だったこともあり、かなりのローカル変数がレジスタだけでは処理できるずスタックに割り付けられていたと記憶してます。実際手元で vm_exec_core を見てみると

0000000000015050 <vm_exec_core>:
   15050:       41 57                   push   %r15
   15052:       41 56                   push   %r14
   15054:       41 55                   push   %r13
   15056:       41 54                   push   %r12
   15058:       55                      push   %rbp
   15059:       53                      push   %rbx
   1505a:       48 8d 1d 00 00 00 00    lea    0x0(%rip),%rbx        # 15061 <vm
_exec_core+0x11>
   15061:       48 81 ec 28 01 00 00    sub    $0x128,%rsp

とか言ってまして、296B のマシンスタックを確保しているわけです。

でもまあスタックが上がったり下がったりしてれば、そのうちマシンスタックは適宜再利用されて、たまたま残ってた VALUE とかも消えたりすると思うんですが、その時問題になってたと記憶しているのは

def init_server
  ... なんだか複雑な処理をして初期化をして、 serving に必要なデータを集めてきて、
  ... データの大部分は捨てるが serving に必要なものだけを残す
end

def execute_server(sock, data)
  while true  # 二度と戻らない
    ... serving する
  end
end

def run_server(data)
  sock = ...ソケットとか作る
  execute_server(sock, data)
end

data = init_server
run_server(data)

みたいな、単純化するとこういうケース。 init_server はなんだか複雑な処理をするので、マシンスタック上に不要になってるはずのポインタを残し、 run_server は init_server とは別のマシンスタック領域を使ったためにそのポインタが残っていて、それで execute_server 呼んじゃうので、 init_server のためのマシンスタックは未来永劫初期化されない、というような。

当時はやや場当たり的に、Rubyのこの部分を別の関数に分離したらよくなったよ、とかそういうことが報告されていました。現段階でどうなってるかは知らないです。

Boehm GC

は、この手のスタックに残ったポインタを定期的に適当なヒューリスティクスと乱数的なタイミングで消すってことをやっていたと思います。たぶんこれ

https://github.com/ivmai/bdwgc/blob/master/misc.c#L332

スタックが頻繁に上がり下がりしてるようなプログラムではすごく有効なはずで、なるほど GC というのはミューテータのアクセスパターンにひどく依存する難しいものだなぁと思った記憶があります。ミューテータ依存というと、他にはコンパイラとかも GC 泣かせだと聞いたことがあります。最初にがばっとメモリ確保して、その部分はあまり解放しないけどその後も確保と解放が続くとかなんとか。まあそれは世代別が緩和しそうな話ですね。

もとの話に戻して適当なタイミングでスタックを綺麗にする緩和は、当然ながら現在のスタックポインタより深いところにあるスタックは消しちゃいけないので、さっきの Ruby の例のように、マシンスタックの金輪際書き換えが起きない部分に残ってるポインタライクなものに対しては無力なのです。

いう2点がモチベーションだったと思います。