K.Sasada's Home Page

Diary - 2012 July

研究日記

文月

_20(Fri)

Python の JIT コンパイラ作りたい,って人が python-dev にあらわれ,色々意見が飛び交っているスレッドが面白い.

これまで,どんな努力が行われてきており,そこから得られた知見とはなんだったのか,などを言い合ってる.おおむねそんなところだろうなぁ,という話が多い.互換性が問題になるのはどこも一緒,とか.LLVM についての議論もある.

Python ってこんなにコンパイラがあったんだな.


シグナルはスタックを汚すか,という話を住井先生の https://twitter.com/esumii/status/226282543912214529 を見て確認してみた.

#include <stdio.h>
#include <string.h>
#include <signal.h>
#include <stdlib.h>

char *
g(void)
{
    char str[1024];
    memset(str, 'x', 1024);
    return str;
}

int g_index;

void
f(void)
{
    char *str = g();
    int miss = 0;

    while (miss == 0) {
	for (g_index=0; g_index<1024; g_index++) {
	    if (str[g_index] != 'x') {
		printf("modified (%d: 0x%x)\n", g_index, (int)str[g_index]);
		miss += 1;
	    }
	}
    }
}

#define ALTSTACK_SIZE (4096 * 1024)
char altstack[ALTSTACK_SIZE];

void 
handler(int sig)
{
    char str[1024];
    printf("SIGINT received\n");
    g_index = 0;
    memset(str, 'y', 1024);
}

main(int argc, char *argv[])
{
    if (argc > 1) {
	stack_t stack;
	stack.ss_sp = altstack;
	stack.ss_flags = 0;
	stack.ss_size = ALTSTACK_SIZE;

	if (sigaltstack(&stack, 0) != 0) {
	    perror("sigaltstack");
	    exit(1);
	}
	printf("use sigaltstack(2)\n");
    }

    if (argc > 1 && strcmp(argv[1], "signal") == 0) {
	signal(SIGINT, handler);
	printf("use signal(2)\n");
    }
    else {
	struct sigaction act;
	act.sa_handler = handler;
	act.sa_flags = SA_ONSTACK;
	sigaction(SIGINT, &act, 0);
	printf("use sigaction(2)\n");
    }
    f();
}

シグナルで汚す.

  • 無引数:signal(2) だけ
  • signal を引数に:sigaltstack(2) + signal(2)
  • sigaction を引数に:sigaltstack(2) + sigaction(2) + SA_ONSTACK

と設定して,Ctrl-C をフック.その時,スタックが汚れてたら終了する.

3番目は見事に汚さないことがわかる(kill -9 しないと止まらなくなるので注意).

x86 において,割り込み時に CPU が PC をどうストアするのか,よく覚えていない.というか,どうなるんだっけ.

_maeda(Sat Jul 21 09:12:44 +0900 2012)

(kill -9 しないと止まらなくなるので注意).

どうでもいいツッコミですが、Quit (Ctrl-\)で止まるかと。

_ささだ(Mon Jul 23 13:19:13 +0900 2012)

 な,なんだってー.(以前見たことがあるんですが,すっかり忘れていました,ありがとうございます.)

_13(Fri)

ACM の会員費がexpireしてた(しそうだった?)ので,慌てて入金.折角金払ってるんだから,論文読むかってことで.


Fine-Grained Modularity and Reuse of Virtual Machine Components

VM のコンポーネントをバラバラにする話.なんでこの話で VMkit への参照がない?

https://wikis.oracle.com/display/MaxineVM/Publications にある https://wikis.oracle.com/download/attachments/41846038/ECOOPSummerSchool2012.pdf?version=1&modificationDate=1340845232000 がとてもわかりやすくてよかった.


■[[Adding dynamically-typed language support to a statically-typed language compiler: performance evaluation, analysis, and tradeoffs

|http://dl.acm.org/citation.cfm?id=2151024.2151047&coll=DL&dl=GUIDE&CFID=95417406&CFTOKEN=94416497]]

IBMの方の話.

真面目にコンパイラ作ってる話に見える(for python).これ,base にしたのは J9 かー.とても丁寧に書いているので読みやすい(流し読みしかしていないが).CFG を簡単にするのはなるほどと,と思うが,具体的には関連研究よめ,と書いてあってようわからん.


Swift: A Register-based JIT Compiler for Embedded JVMs

組込み Java (Android の DEX)向けに作った JIT コンパイラ.どの辺が凄いのか,よくわからんかった.

So registerbased bytecode may be a better choice to distribute applications than stack-based bytecode, especially in embedded systems.

の根拠も,結局わからず.うーん,そうかも,って思うところも無いことも無いが.


Unpicking the knot: teasing apart VM/application interdependencies

これも meta-circular の話なのか.なんか,流行ってたのかな.


メモが面倒くさくなった.

_6(Fri)

require の整理.

拡張子が与えられない時,$: を "2回調べる" という挙動を知らなかった.なんだこの仕様.

つまり,まず $: のパスに feature + '.rb' がないか調べて,なかったら $: のパスに feature + '.so' が無いか調べる.


というわけで,現状は多分こんな感じ.

# 現在
def require feature
  fullpath = nil

  # ロードするファイルを特定する
  if feature.absolute_path?
    fullpath = feature
  else
    feature_ext = File.extname(feature)
    if ext.empty?
      exts = %w(.rb .so)
    else
      exts = [feature_ext]
    end

    try(:found){
      exts.each{|ext| # .rb で $: を探し,無かったら改めて .so を $: から探す
        $:.each{|path|
          if File.exist?(path+feature+ext)
            fullpath = path+feature+ext
            throw :found
          end
        }
      }
    }
  end

  raise LoadError unless fullpath

  # 重複をチェックする
  if $LOADED_FEATURE.include? ...
    return false
  end

  # 実際にロードする
  once = ($LOADING_TABLE[full_path] ||= Once.new)
  once.once{
    load full_path
  }
  $LOADING_TABLE[full_path] = nil
  $LOADED_FEATURE << full_path
end

で,これを拡張可能にしたいわけです.例えば,zip ファイルの中の .rb ファイルをロードしたりとかしたいわけです.独自に暗号化した .rb.encrypted なファイルをロードしたいわけです.

処理をよく見ると,(1) fullpath を調べるところ,(2) 重複を調べるところ(すでに require しているかどうかをチェックするところ),そして (3) 実際にロードするところに分かれていることがわかります.

今回拡張したいのは (1) のフルパスを調べるところ(どこからロードするか,決めるところ),(3) どうやって実際にロードするか,になります.というわけで,2つの拡張が書きやすい仕組みを導入出来ないか検討して,Finder,Loader の2つの仕組みを導入出来ないか検討しました.

で,検討結果が下記です.

class Finder
  def self.responsible? path, ext
    false
  end

  attr_reader :path, :ext

  def initialize path, ext
    @path = path
    @ext = ext
  end

  def lookup feature, ext
    # return appropriate Loader object
    nil
  end
end

class Loader
  attr_reader :finder, :feature, :path
  def initialize finder, feature, path
    @finder = finder
    @feature = feature
    @path = path
  end

  def fullpath
    
  end

  def filename
    
  end

  def load
    # execute loading
    # for .rb script, then eval(script)
  end

  def load_script_string script_string, file
  end

  def laod_script_file filename, file = filename
  end

  module_function :load_script_string
  module_function :load_script_file

  ## __LOADER__.require_relative(feature)
  def require_relative feature
    loader = @finder.lookup(feature)
  end
end

$FINDER_CACHE = {}
$FINDER_CLASSES = [CompiledRubyScriptFileFinder, RubyScriptFileFinder, ExtFileFinder]

def require feature
  loader = require_find_loader(feature)
  require_latter loader
end

def find_finder path, ext, feature
  if $FINDER_CACHE.has_key? [path, ext]
    $FINDER_CACHE[[path, ext]]
  else
    finders = []
    $FINDER_CLASSES.each{|finder_class|
      if finder_class.responsible?(path, ext)
        finders << finder_class.new(path, ext)
      end
    }
    $FINDER_CACHE[[path, ext]] = finders
  end
end

def require_find_loader feature
  feature_ext = File.extname(feature)

  if feature_ext.empty?
    exts = ['.rb', '.so']
  else
    exts = [feature_ext]
  end

  # loader の探索
  loader = nil
  exts.each{|ext|
    $:.each{|path|
      finders = find_finders path, ext
      finders.each{|finder|
        break if loader = finder.lookup(feature)
      }
    }
  }
  raise LoadError unless loader
  loader
end

def require_latter loader
  # 重複のチェック
  return false if $LOADED_FEATURES.include?(loader.filename)
  return false if $LOADED_FEATURES.include?(loader.fullpath)

  # 実際のロード
  once = ($LOADING[loader.fullpath] ||= Once.new)
  once.once{
    loader.load
  }
  $LOADING[loader.fullpath] = nil
end

まず,Finder オブジェクトは $LOAD_PATH の各パスに対応します.対応するパスであれば,Finder オブジェクトを生成します.この処理は,require ごとに走るため,$FINDER_CACHE というものでキャッシュしています.

ここでは,拡張子もキャッシュのキーになっているのが大事です.

で,生成された Finder オブジェクトを利用して, Finder#lookup(feature) でロード出来るかチェックします.ロード出来るようだったら,Loader オブジェクトを生成し,返します.

Loader オブジェクトは,適当な fullpath を返すようにします.これで,重複チェックを行い,また最後に $LOADED_FEATURE への追加を行います.

Loader オブジェクトは,Ruby スクリプト(に相当する何か)を独自の方法で load します.

デフォルトで,RubyScriptFileFinder と ExtFileFinder,そしてそれにそれぞれ対応する RubyScriptFileLoader,ExtFileLoader を用意.従来と完全互換です.


というのを考えたんだけど,複雑過ぎるかなぁ.

重複のチェックは,もしかして Finder#lookup でやらせるべきなんだろうか.

_5(Thu)

Ruby core でいくつか Feature 提案をしているんだけど,返事がないので,なんとなく,するっと追加されちゃうに違いない.

TracePoint は,名前が微妙なんだよな.

_2(Mon)

もう7月ですよ!


アンディとミックスの合体がさっぱり無視されていてげんなりした.


require の順番をこう変えるのはどうだろうか.

require 'foo/bar' としたとき:

  • (1) require したファイルが 'foo/baz.rb' として require されていたとき,そしてそれが /a/b/foo/bar.rb を読んでいたら,'/a/b/foo/bar.rb' を探す(つまり,baz.rb は,foo/baz で require されていたことを覚えておく).
  • (2) require したファイルが 'foo.rb' だったとき,そしてそれが /a/b/foo/bar.rb を読んでいたら,'/a/b/foo/bar.rb' を探す.
  • (3) $: から探す(これまでと同じ)

つまり,同じディレクトリ名だったら相対ディレクトリだろう,という推測による.

require 元のファイルを __REQUIREE__ とすして(上の例だと foo/baz だったり,foo だったりする),require するファイルを feature とすると:

def require feature
  if (dir = File.dirname(__REQUIREE__)).start_with?(File.dirname(feature))
    return true if require_from(dir + feature)
  end
  requre_orig feature
end

こんなかんじ.

と,思ったんだけど,これだと標準ライブラリから require したファイルで,標準ライブラリにある場合は,かならず標準ライブラリから読まれてしまうからダメか....残念.

(2) を外せばいいかな.同じディレクトリ名を持つ場合は自分との相対パスでまず調査.


tracing の復習.というか,なんでこんなに絶望的なほどに複雑なんだ.全部書き換えるかな.

  • Terminology
    • グローバルフック:全ての Thread で有効なフック
      • vm->event_hooks に設定
      • th->event_flags | RUBY_EVENT_VM があれば,グローバルフックがあると判断
    • スレッドローカルローカルフック:特定のスレッドで有効なフック
    • Rubyフック:set_trace_func,Thread#set_trace_func で設定したフック
    • Cフック:C API で設定したフック
  • public types and functions
    • rb_event_hook_t in ruby.h
      • 各スレッドが持つ hook のための連結リスト
      • flag, hook, data を持つ.
      • if (flag & event) fook(data) みたいな感じ.
      • これ,公開する必要あるんか?
    • void rb_add_event_hook(rb_event_hook_func_t func, rb_event_flag_t events, VALUE data);
      • グローバルにイベントフックを追加
    • int rb_remove_event_hook(rb_event_hook_func_t func);
      • グローバルに指定した hook を削除.
  • local types and functions
    • struct event_call_args
      • set_trace_func 用構造体(多分)
    • static rb_event_hook_t *alloc_event_hook(rb_event_hook_func_t func, rb_event_flag_t events, VALUE data)
      • rb_event_hook_t を割り当て
    • static void thread_reset_event_flags(rb_thread_t *th)
      • flag を hook->flag の or にする.これは reset というのか?
    • static void rb_threadptr_add_event_hook(rb_thread_t *th, rb_event_hook_func_t func, rb_event_flag_t events, VALUE data)
      • スレッドローカルフック(C フック)を設定する.
    • void rb_thread_add_event_hook(VALUE thval, rb_event_hook_func_t func, rb_event_flag_t events, VALUE data)
      • スレッドローカルフック(C フック)を設定する.public API のはずなんだが,ruby.h 等に入っていないので気づかれ無さそう.
    • static void set_threads_event_flags(int flag)
      • グローバルフックがあるか無いか,全生きているスレッドに通知する.
    • static inline int exec_event_hooks(const rb_event_hook_t *hook, rb_event_flag_t flag, VALUE self, ID id, VALUE klass)
      • set_trace_func で登録された hook を起動.引数は self, id, klass および data.
      • なぜか removed な数を数えているのだが,なぜだろうか.
      • 実際に呼ばれたときに削除しているようだ.なぜ消すのを遅延させるんだろうか?
    • static VALUE thread_exec_event_hooks(VALUE args, int running)
      • ええと,よくわからない.
    • void rb_threadptr_exec_event_hooks(rb_thread_t *th, rb_event_flag_t flag, VALUE self, ID id, VALUE klass)
      • 実際にイベントが発生するところに埋め込まれている実体.
      • こいつが thread_suppress_tracing() で thread_exec_event_hooks() を呼び出している
    • static int defer_remove_event_hook(rb_event_hook_t *hook, rb_event_hook_func_t func)
      • hook 連結リストに対して,func で指定できるブロックを削除フラグを付けて回る
    • static int remove_event_hook(rb_event_hook_t **root, rb_event_hook_func_t func)
      • func が 0,もしくは func が指定された func,もしくは remove フラグがたっている hook を削除.
      • これ,root の設定方法間違ってない?
      • なんでこんなに難しいんだろう.
    • static int remove_defered_event_hook(rb_event_hook_t **root)
      • func が無い remove_event_hook() な気がする.
      • remove フラグが突いている奴を xfree している
      • これも root に対して何をしているんだかわからん
    • static int rb_threadptr_remove_event_hook(rb_thread_t *th, rb_event_hook_func_t func)
      • th の func な hook を削除.tracing 中に削除された場合は defer しているようだ.
    • int rb_thread_remove_event_hook(VALUE thval, rb_event_hook_func_t func)
      • 上の thval 版
      • これも,公式 API な気もするんだけど,どこからも参照がない.
    • static rb_event_hook_t *search_live_hook(rb_event_hook_t *hook)
      • 生きている hook を探して返す.
    • static int running_vm_event_hooks(st_data_t key, st_data_t val, st_data_t data)
      • 次の関数で使う iter 関数
    • static rb_thread_t *vm_event_hooks_running_thread(rb_vm_t *vm)
      • trace 中のスレッドがあれば,それらのうちどれかを返す
      • 何に使うんだと思ったら,次のグローバルフックを外す処理で defer するかどうかの選択に必要らしい
      • 全部 defer しちゃえばいいような気もするんだが
    • int rb_remove_event_hook(rb_event_hook_func_t func)
      • グローバルフックに設定した func な hook を削除
    • static int clear_trace_func_i(st_data_t key, st_data_t val, st_data_t flag)
      • 次の関数で使う iter 関数
    • void rb_clear_trace_func(void)
      • グローバルフックを全部削除
    • static VALUE set_trace_func(VALUE obj, VALUE trace)
      • Kernel#set_trace_func の実体
    • static void thread_add_trace_func(rb_thread_t *th, VALUE trace)
      • 指定されたスレッドに trace を追加
      • threadptr にするべきでは....
    • static VALUE thread_add_trace_func_m(VALUE obj, VALUE trace)
      • Thread#set_trace_func の実体
    • static const char *get_event_name(rb_event_flag_t event)
      • event_flag に応じたC文字列を返す
    • static VALUE call_trace_proc(VALUE args, int tracing)
      • set_trace_func で設定した Proc を起動
    • static void call_trace_func(rb_event_flag_t event, VALUE proc, VALUE self, ID id, VALUE klass)
      • set_trace_func で設定した Proc を起動する関数を ruby_suppress_tracing() 経由で起動
    • VALUE ruby_suppress_tracing(VALUE (*func)(VALUE, int), VALUE arg, int always)
      • current thread で thread_suppress_tracing() を呼ぶ
    • static VALUE thread_suppress_tracing(rb_thread_t *th, int ev, VALUE (*func)(VALUE, int), VALUE arg, int always)
      • 同じイベント hook の再帰を防ぐ.ただし,always フラグが立っていれば実行する
      • あれ,ここで PUSH_TAG(),EXEC_TAG() している?

  • イベントが発生したら,具体的に何をするか?
    • rb_threadptr_exec_event_hooks()
    • thread_suppress_tracing() 経由で thread_exec_event_hooks() を呼ぶ
    • exec_event_hooks() で全てのスレッドローカルフックを呼び出す
      • th->tracing に EVENT_RUNNING_THREAD を設定しておく
      • 各種フックを呼び出す
      • th->tracing から EVENT_RUNNING_THREAD をクリアする
      • もし,defer されているフックがあれば,消去する
    • RUBY_EVENT_VM が設定されていれば,exec_event_hooks() を用いてフックを実行する
      • th->tracing に EVENT_RUNNING_VM を設定しておく
      • exec_event_hooks() でグローバルフックを実行すべてする
      • th->tracing から EVENT_RUNNING_VM をクリアする
      • もし,defer されているフックがあれば,消去する
    • 終わり

つまり,全ての hook が thread_suppress_tracing() 経由で呼ばれているので, setjmp が挟まってる.C でフック書きたい人は,そんなの要らんのじゃないの?

Sasada Koichi / ko1 at atdot dot net
$Date: 2003/04/28 10:27:51 $