githubにssh keyを設定

githubにpushしようと思ったところ、なぜかid/password認証に失敗します。

githubのヘルプページを見ると、gitはバージョン1.7.10以上を使えと書いてあります。Cygwinのgitはバージョン1.7.9で、このためでしょうか。アップデートしようとしましたが、Cygwin最新は1.7.9らしいので、公式サイトからgitのWindowsバージョンをインストールして試してみましたが、解決せず。

理由はよくわかりませんが、SSH経由に切り替えてみたところ、うまくいったのでメモしておきます。

とはいえ、以下のサイトの手順をそのまま実行しただけです。
http://blog.suz-lab.com/2012/12/githubsshgit-clone.html

一点詰まったのは、ssh-keygenやsshはキーを置く場所として/home/ユーザー名/.sshディレクトリを読もうとするので、/home以下にホームディレクトリを置いていないとエラーになります。$HOMEは読まないようです。これは/home以下に自分のホームディレクトリのリンクを張って解決しました。

これでgit pushできるようになったので、Visual Studioプロジェクトなど、いくつかコミットしておきました。MRIのバージョン2.1.0からrbjitという名前のブランチを切っています。

https://github.com/msumimz/ruby/tree/rbjit

githubにプロジェクトを作成

今まではwww.ruby-lang.orgからv2.1.0のソース一式をtar.gz形式でダウンロードして手元でいろいろいじっていたのですが、そろそろコードを書き始めています。今後のバージョン追随のためにも、MRIのソースコードとはなるべく独立するようにしていますが、多少は直接変更する必要がある部分もでてきました。そこで、早めにgitプロジェクトを作って差分管理することにします。

といってもgithubにあるMRIのレポジトリからフォークしただけです。まだまとまって動くものはないので、コミットは何もしてません。
http://github.com/msumimz/ruby

レポジトリからcloneしたコードをビルドするにはbisonとsedが必要になります。Windowsでもセットアップできますが、面倒なのでCygwinでビルドしてしまいます。一度必要なファイルが作成されれば、以後はWindowsでもbisonなしでビルドできます。

以下のコマンドで、何も考えずにビルドできてしまいます。

autoconf
./configure
make

ただし全部ビルドすると時間がかかります。RDocのビルドが始まった時点で止めてしまいました。探せば必要なファイルだけ作成するmakeターゲットもあるのでしょうが、調べるのが面倒です。

[~/work/rbjit/ruby]$./ruby -v
ruby 2.1.0p0 (2013-12-25 revision 44417) [x86_64-cygwin]

できているようです。

さて、せっかく作ったCygwin版rubyですが、目的は達したので消してしまいます。

make clean

ここからVisual Studio版のビルドです。今まではCygwinのシェル上で実行していましたが、Visual Stduioコマンドプロンプトを立ち上げます。こちらも作業は簡単で、以下のコマンドを入力すればビルドできます。

win32\configure.bat
nmake

C:\Users\msumi\Documents\work\rbjit\ruby>ruby -v
ruby 2.1.0p0 (2013-12-25 revision 44417) [i386-mswin32_100]

無事できました。

これに以前作ったVisual Studioのプロジェクトファイルをコピーして終わりです。フォルダ構成が変わったので、*.vcxprojを直接修正しました。

MRIソースコードを読む その1 メソッド定義の実装（下）

vm_method.c:rb_add_method()ですが、エラーチェックしながらデータを設定しているだけです。せっかくですのでJITコンパイラを実装するために必要そうな知識を整理しておきます。

メソッド定義に関係するデータ構造は、rb_method_entry_tとrb_method_definition_tで、method.hで定義されています。

まずrb_method_entry_tです。一見複雑そうですが、メソッドの種類ごとの本体データが共用体になっているだけです。

typedef struct rb_method_definition_struct {
    rb_method_type_t type; /* method type */
    ID original_id;
    union {
	rb_iseq_t * const iseq;            /* should be mark */
	rb_method_cfunc_t cfunc;
	rb_method_attr_t attr;
	const VALUE proc;                 /* should be mark */
	enum method_optimized_type {
	    OPTIMIZED_METHOD_TYPE_SEND,
	    OPTIMIZED_METHOD_TYPE_CALL,

	    OPTIMIZED_METHOD_TYPE__MAX
	} optimize_type;
	struct rb_method_entry_struct *orig_me;
    } body;
    int alias_count;
} rb_method_definition_t;

typeメンバでメソッドの種類を表します。MRIの内部では、メソッドは以下の11種類に分類されます。

typedef enum {
    VM_METHOD_TYPE_ISEQ,
    VM_METHOD_TYPE_CFUNC,
    VM_METHOD_TYPE_ATTRSET,
    VM_METHOD_TYPE_IVAR,
    VM_METHOD_TYPE_BMETHOD,
    VM_METHOD_TYPE_ZSUPER,
    VM_METHOD_TYPE_UNDEF,
    VM_METHOD_TYPE_NOTIMPLEMENTED,
    VM_METHOD_TYPE_OPTIMIZED, /* Kernel#send, Proc#call, etc */
    VM_METHOD_TYPE_MISSING,   /* wrapper for method_missing(id) */
    VM_METHOD_TYPE_REFINED,

    END_OF_ENUMERATION(VM_METHOD_TYPE)
} rb_method_type_t;

いずれすべての種類を理解しなければいけませんが、当面必要なのはVM_METHOD_TYPE_ISEQとVM_METHOD_TYPE_CFUNCの2つです。VM_METHOD_TYPE_ISEQはスクリプトで定義されたメソッドで、メソッド本体はiseqです。

VM_METHOD_TYPE_CFUNCはCで実装されたメソッドで、メソッドの実体はrb_method_func_t型のcfuncです（method.hで定義）。

typedef struct rb_method_cfunc_struct {
    VALUE (*func)(ANYARGS);
    VALUE (*invoker)(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv);
    int argc;
} rb_method_cfunc_t;

invokerが少し面白いメンバで、vm_method.c:rb_add_method()からvm_method.c:setup_method_cfunct_strct()経由で呼び出されるvm_method.c:call_cfunc_invoker_func()で設定されます。実装は以下の通りです。

static VALUE
(*call_cfunc_invoker_func(int argc))(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *)
{
    switch (argc) {
      case -2: return &call_cfunc_m2;
      case -1: return &call_cfunc_m1;
      case 0: return &call_cfunc_0;
      case 1: return &call_cfunc_1;
      case 2: return &call_cfunc_2;
      case 3: return &call_cfunc_3;
      case 4: return &call_cfunc_4;
      case 5: return &call_cfunc_5;
      case 6: return &call_cfunc_6;
      case 7: return &call_cfunc_7;
      case 8: return &call_cfunc_8;
      case 9: return &call_cfunc_9;
      case 10: return &call_cfunc_10;
      case 11: return &call_cfunc_11;
      case 12: return &call_cfunc_12;
      case 13: return &call_cfunc_13;
      case 14: return &call_cfunc_14;
      case 15: return &call_cfunc_15;
      default:
	rb_bug("call_cfunc_func: unsupported length: %d", argc);
    }
}

つまり、メソッドの引数ごとに呼び出すヘルパメソッドを設定しています。例えばcall_cfunc_3を見てみると(vm_insnhelper.cで定義）、以下のような実装です。

static VALUE
call_cfunc_3(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv)
{
    return (*func)(recv, argv[0], argv[1], argv[2]);
}

そのままですね。

次にrb_method_entry_tですが、定義は以下の通りです。

typedef struct rb_method_entry_struct {
    rb_method_flag_t flag;
    char mark;
    rb_method_definition_t *def;
    ID called_id;
    VALUE klass;                    /* should be mark */
} rb_method_entry_t;

このrb_method_entry_tが、クラスのメソッドテーブル（mtbl）というハッシュに定義されます。flagはメソッドのvisibilityなどの状態を保持するビット列です。called_idは呼び出されるメソッド名で、エイリアスによって別名定義された場合に元の名前とは異なる名前になります。rb_method_definition_tにあるoriginal_idが元の名前です。

MRIソースコードを読む その1 メソッド定義の実装（中）

さて、（上）に続いてメソッド定義の実装を見ていきます。

core#define_methodの実体はvm.c:m_core_define_method()です。

#define REWIND_CFP(expr) do { \
    rb_thread_t *th__ = GET_THREAD(); \
    th__->cfp++; expr; th__->cfp--; \
} while (0)

static VALUE
m_core_define_method(VALUE self, VALUE cbase, VALUE sym, VALUE iseqval)
{
    REWIND_CFP({
	vm_define_method(GET_THREAD(), cbase, SYM2ID(sym), iseqval, 0, rb_vm_cref());
    });
    return sym;
}

REWIND_CFPは、コントロールフレームを一時的に一段巻き戻した上で処理を行うマクロです。core#define_method自身のコントロールフレームが積まれていますので、それを巻き戻すということでしょう。

vm.c:rb_vm_cref()はその名の通りcrefを求める関数です。定義は以下の通りです。

NODE *
rb_vm_cref(void)
{
    rb_thread_t *th = GET_THREAD();
    rb_control_frame_t *cfp = rb_vm_get_ruby_level_next_cfp(th, th->cfp);

    if (cfp == 0) {
	return NULL;
    }
    return rb_vm_get_cref(cfp->iseq, cfp->ep);
}

先ほど巻き戻したコントロールフレームですが、vm.c:rb_vm_get_ruby_level_next_cfp()を呼んでさらに巻き戻しています。メソッド名からするとスクリプトレベルのコントロールフレームに巻き戻しているようですが、内容がよくわかりませんでした。そのようにして求めたコントロールフレームに対して、前回記事で説明したrb_vm_get_cref()を呼んでいます。

今回のサンプルコードでvm.c:rb_vm_cref()を実行した結果は、前回、cbaseを求める過程で求めたcrefと同じ値でした。きちんと調べるのであれば、2つのcrefが異なるときにブレークするような条件文を挿入して適当なスクリプトを実行してみればよさそうですが、今回は省略します。

さて、vm.c:vm_define_method()の実装は以下の通りです。

static void
vm_define_method(rb_thread_t *th, VALUE obj, ID id, VALUE iseqval,
		 rb_num_t is_singleton, NODE *cref)
{
    VALUE klass = cref->nd_clss;
    int noex = (int)cref->nd_visi; // (A)
    rb_iseq_t *miseq;
    GetISeqPtr(iseqval, miseq); // (B)

    if (miseq->klass) { // (C)
	RB_GC_GUARD(iseqval) = rb_iseq_clone(iseqval, 0);
	GetISeqPtr(iseqval, miseq);
    }

    if (NIL_P(klass)) {
	rb_raise(rb_eTypeError, "no class/module to add method");
    }

    if (is_singleton) {
	klass = rb_singleton_class(obj); /* class and frozen checked in this API */
	noex = NOEX_PUBLIC;
    }

    /* dup */
    COPY_CREF(miseq->cref_stack, cref); // (D-1)
    miseq->cref_stack->nd_visi = NOEX_PUBLIC; // (D-2)
    RB_OBJ_WRITE(miseq->self, &miseq->klass, klass);
    miseq->defined_method_id = id;
    rb_add_method(klass, id, VM_METHOD_TYPE_ISEQ, miseq, noex); // (E)

    if (!is_singleton && noex == NOEX_MODFUNC) { // (F)
	klass = rb_singleton_class(klass);
	rb_add_method(klass, id, VM_METHOD_TYPE_ISEQ, miseq, NOEX_PUBLIC);
    }
}

いろいろやっていますが、基本的には(E)でメソッドを定義しているだけです。

(A)で、既定のvisibilityを取得しています。

(B)のGetISeqPtrはMRIでよくある種類のマクロで、GetISeqPtr(a, b)で、単にb = (rb_seq_t*)aを表します。このマクロを定義している理由は、デバッグ時に型チェックを行う追加処理を入れるためのようです（vm_core.hで定義）。

(C)は、miseq->klassが定義済みとは、他のメソッドで使われているISeqという意味でしょう。ISeqを別のメソッド定義で再利用する場合は、rb_iseq_clone()でコピーしてから使っています（共用できないのは、インラインメソッドキャッシュのためでしょうか）。

(D-1)、(D-2)でcrefをコピーしたうえでvisibilityをNOEX_PUBLICにしているのは、例えば以下の場合でしょうか。

class C
  private
  def m1
    def m2
      1
    end
  end
end

C.new.m1        # => NoMethodError: private method `m1' called for C
C.new.send(:m1) # => クラスCにpublicなメソッドm2が定義される
C.new.m2        # => 1

クラススコープで設定された既定のvisibilityはメソッド内部には伝播せず、メソッド内部でメソッドを定義すると常にpublicになります。

(F)は、module_functionの処理でしょう。クラスの特異クラスに同じメソッドを定義しています。こちらはISeqを共用していますね。

(E)のrb_add_method()については次回。

MRIソースコードを読む その1 メソッド定義の実装（上）

自分向けの備忘録として、MRIのソースコードを読んだ結果メモを記録しておきます。

以下のソースコードは

def m
  1
end

次のISeqにコンパイルされます。

== disasm: <RubyVM::InstructionSequence:<main>@-e>======================
0000 trace            1                                               (   1)
0002 putspecialobject 1
0004 putspecialobject 2
0006 putobject        :m
0008 putiseq          m
0010 opt_send_simple  <callinfo!mid:core#define_method, argc:3, ARGS_SKIP>
0012 leave

putspecialobjectはその名の通り特殊なオブジェクトをスタックにプッシュします。引数で種類を指定します。種類はそれぞれ

値	名称	オブジェクト
1	VM_SPECIAL_OBJECT_VMCORE	VMを表す内部オブジェクト
2	VM_SPECIAL_OBJECT_CBASE	メソッドが定義されるクラス
3	VM_SPECIAL_OBJECT_CONST_BASE	定数検索ののベースとなるクラス

です。insn.defのputspecialobjectの定義参照。

メソッド定義で使うのは1と2です。1はVMを表すオブジェクトですが、このオブジェクトはvm.c:Init_VM()で定義されており、グローバル変数rb_mRubyVMFrozenCoreに入っています。グローバル変数をわざわざ引数として渡しているのは将来のマルチVM化の複線かもしれません。

2はメソッドが定義されるべきクラスで、vm_insnhelper.c:vm_get_cbase()で取得されています。

static inline VALUE
vm_get_cbase(const rb_iseq_t *iseq, const VALUE *ep)
{
    NODE *cref = rb_vm_get_cref(iseq, ep);
    VALUE klass = Qundef;

    while (cref) {
	if ((klass = cref->nd_clss) != 0) {
	    break;
	}
	cref = cref->nd_next;
    }

    return klass;
}

この関数では、まずvm_insnhelper.c:rb_vm_get_cref()を呼んでcrefなるものを取得しています。これは、「Rubyソースコード徹底解説」によればクラスのネスト関係を表すリストだそうです。VALUE型の変数ですが、nd_clssがクラスを表し、nd_nextで外側のクラスを表します。どうやらnd_clssは0になることがあるようで、関数の後半部分ではnd_clssが0の間、外側のクラスを辿っています。

vm_insnhelper.c:rb_vm_get_cref()ですが、ソースコードは以下の通りです。

NODE *
rb_vm_get_cref(const rb_iseq_t *iseq, const VALUE *ep)
{
    NODE *cref = vm_get_cref0(iseq, ep);

    if (cref == 0) {
	rb_bug("rb_vm_get_cref: unreachable");
    }
    return cref;
}

さらにvm_insnhelper.c:vm_get_cref0()は以下の通りです。

static NODE *
vm_get_cref0(const rb_iseq_t *iseq, const VALUE *ep)
{
    while (1) {
	if (VM_EP_LEP_P(ep)) {
	    if (!RUBY_VM_NORMAL_ISEQ_P(iseq)) return NULL;
	    return iseq->cref_stack;
	}
	else if (ep[-1] != Qnil) {
	    return (NODE *)ep[-1];
	}
	ep = VM_EP_PREV_EP(ep);
    }
}

ここでiseqとepという変数が使われていますが、iseqはコンパイルされたメソッドの実体で、そこにメソッドが定義された場所のcrefが保管されているようです。rb_iseq_tの定義はvm_core.hにあります。

epはValue Stack（YARVでは2本のスタックが使われており、そのうちの1本です）上のメソッドのローカルフレームを指すポインタです。x86ではebp/rbpで管理されるローカルフレームに相当します。どうやらそのep[-1]にもcrefが保管されているようです。

どちらのcrefを使うかはVM_EP_LEP_P()なるマクロで判別します。この定義はvm_core.hにあり、

/*
 * block frame:
 *  ep[ 0]: prev frame
 *  ep[-1]: CREF (for *_eval)
 *
 * method frame:
 *  ep[ 0]: block pointer (ptr | VM_ENVVAL_BLOCK_PTR_FLAG)
 */

#define VM_ENVVAL_BLOCK_PTR_FLAG 0x02
#define VM_ENVVAL_BLOCK_PTR_P(v)   ((v) & VM_ENVVAL_BLOCK_PTR_FLAG)

#define VM_EP_LEP_P(ep)     VM_ENVVAL_BLOCK_PTR_P((ep)[0])

となっています。ep[0]に入っているのがブロックポインタかどうか判定することで、今いる場所がメソッドかどうかを判定しているようです。メソッドであればiseqに保管されたcrefを使い、ブロックであれば、ブロックのコンパイル時に構築されるiseqにcrefは定義されないので、フレームに積まれたcrefを使うということになります。

これで最初の2つの引数が何か明らかになりました。それ以外の引数は、それぞれメソッド名とメソッドの実体です。これらの引数でcore#define_methodを読んでいます。
長くなったのでcore#define_methodは次の記事で。

Ruby Under a Microscope買いました

他の方のレビューでは、ソースコードと結びつけた記述は少ないそうですが、スタックフレームの取り扱いやブロックの処理などのイメージをつかむのに役立ちそうです。

Ruby Under a Microscope: An Illustrated Guide to Ruby Internals

RubyでASTやIRを表示する

JITコンパイラを書くには、まずRubyの生成するASTを調べる必要があります。そのためのツールとして、以前に読んだ「Rubyソースコード完全解説」でnodedumpという外部ライブラリを使っていました。
じゃあそれを使おうと思ってググってみましたが、どうも最新バージョンには対応していないらしく、自分で作らないといけないかと思っていました。
が、実は最近のRubyには--dumpという隠しオプションがあり、ASTやIRを表示できるのでした。
例えば、ASTを表示させたいときは--dump=parsetreeを指定します。

[~/work/rbjit]$vc10/Debug/miniruby.exe --dump=parsetree -e "1 + 2"
###########################################################
## Do NOT use this node dump for any purpose other than  ##
## debug and research.  Compatibility is not guaranteed. ##
###########################################################

# @ NODE_SCOPE (line: 1)
# +- nd_tbl: (empty)
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_CALL (line: 1)
#     +- nd_mid: :+
#     +- nd_recv:
#     |   @ NODE_LIT (line: 1)
#     |   +- nd_lit: 1
#     +- nd_args:
#         @ NODE_ARRAY (line: 1)
#         +- nd_alen: 1
#         +- nd_head:
#         |   @ NODE_LIT (line: 1)
#         |   +- nd_lit: 2
#         +- nd_next:
#             (null node)

大きく警告が表示されますが、確かにASTが出力されています。
さらに、--dump=parsetree_with_commentを使うと、説明つきのASTが表示されるようです。
また、IRを表示するときは--dump=insnsです。

[~/work/rbjit]$vc10/Debug/miniruby.exe --dump=insns -e "1 + 2"
== disasm: @-e>======================
0000 trace            1                                               (   1)
0002 putobject_OP_INT2FIX_O_1_C_
0003 putobject        2
0005 opt_plus         
0007 leave

便利ですね！