LoginSignup
17
9

More than 5 years have passed since last update.

@k0kubun(Takashi Kokubun)

The Story of Method Lookup

Last updated at Posted at 2017-06-10

おおむね以下の点を理解することを目標に、CRubyのメソッド呼出がどのようなフローで実行されているかを見ていく。対象バージョンは2.4.1。

  • Rubyで定義されたメソッド、C拡張で定義されたメソッド、コア内部で実装されたCのメソッドはそれぞれCRuby内部でどういったデータ構造で保管されているか
  • それらはそれぞれどのようなアルゴリズムで検索されるか
  • それらはそれぞれどのような流れで実行されるか
  • メソッドキャッシュはどのように実装されており、どういう時使われるのか
  • バックトレースの管理などメソッド本体の処理以外には何が行なわれているのか
  • send命令とopt_send_without_block命令とrb_funcallの間では何が異なるのか

なおこの記事のタイトルは、RubyConf 2015の時 Messenger: The (Complete) Story of Method Lookupを当時この記事に書いてあるようなことを話してくれるのかなと思いながら現地で聞いていたが、単に普段Rubyを書いていれば理解しているはずの内容だった、というのが元ネタ。かわりに自分で調べるか、という気持ちで書いている。基本的に自分用のメモなのでCompleteに書くつもりはない(面倒なので人に読ませるつもりで書いてない)し、書いてあることは予想とか勝手な妄想を含んでいる可能性があるので注意してほしい。

YARV instruction dispatchの内容を前提とするのでリンクしておく。

opt_send_without_block

以下のように、ブロックを渡さない普通のメソッド呼び出しにはopt_send_without_blockが使われる。ちなみに以下のiseqだとメソッド定義の際にも、putspecialobject 1でスタックにpushされるFrozenCoreと呼ばれる隠しオブジェクトに対してcore#define_methodがopt_send_without_blockで呼び出されているため、メソッド定義の際にも使われることがわかる。

$ ruby --dump=insns -e "def a; 1; end; a"
== disasm: #<ISeq:<main>@-e>============================================
0000 trace            1                                               (   1)
0002 putspecialobject 1
0004 putobject        :a
0006 putiseq          a
0008 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0011 pop
0012 putself
0013 opt_send_without_block <callinfo!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0016 leave
== disasm: #<ISeq:a@-e>=================================================
0000 trace            8                                               (   1)
0002 trace            1
0004 putobject_OP_INT2FIX_O_1_C_
0005 trace            16
0007 leave

力尽きて全部のパターンを読まない可能性が高いので、実際のケースで一番多いパターンであろうopt_send_without_blockから見ていく。

ISeq上どのように表現されているか

上記aメソッドの呼び出しは、disasmだとopt_send_without_block <callinfo!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>と表現されており、ISeq#to_aだと[:opt_send_without_block, {:mid=>:a, :flag=>28, :orig_argc=>0}, false]が返ってくる。この2つからなんとなく想像はつくが、Cのコードレベルでどうなっているか一応見ておく。

パッと見、多分この辺でsend命令が作られ https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L1102-L1110 、

static INSN *
new_insn_send(rb_iseq_t *iseq, int line_no, ID id, VALUE argc, const rb_iseq_t *blockiseq, VALUE flag, struct rb_call_info_kw_arg *keywords)
{
    VALUE *operands = (VALUE *)compile_data_alloc(iseq, sizeof(VALUE) * 3);
    operands[0] = (VALUE)new_callinfo(iseq, id, FIX2INT(argc), FIX2INT(flag), keywords, blockiseq != NULL);
    operands[1] = Qfalse; /* cache */
    operands[2] = (VALUE)blockiseq;
    return new_insn_core(iseq, line_no, BIN(send), 3, operands);
}

iseq_specialized_instructionはsend命令の最適化を行うが、(ci->flag & VM_CALL_ARGS_BLOCKARG) == 0 && blockiseq == NULLな時にブロック向けのオペランドを削ってopt_send_without_block命令に変換してるように見える。 https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L2435-L2438

    if ((ci->flag & VM_CALL_ARGS_BLOCKARG) == 0 && blockiseq == NULL) {
        iobj->insn_id = BIN(opt_send_without_block);
        iobj->operand_size = insn_len(iobj->insn_id) - 1;
    }

で、new_insn_sendやnew_insn_coreが返している型INSNは以下のようになっていて、

typedef struct iseq_insn_data {
    LINK_ELEMENT link;
    enum ruby_vminsn_type insn_id;
    unsigned int line_no;
    int operand_size;
    int sc_state;
    VALUE *operands;
} INSN;

// LINK_ELEMENTはこれ
typedef struct iseq_link_element {
    enum {
        ISEQ_ELEMENT_NONE,
        ISEQ_ELEMENT_LABEL,
        ISEQ_ELEMENT_INSN,
        ISEQ_ELEMENT_ADJUST
    } type;
    struct iseq_link_element *next;
    struct iseq_link_element *prev;
} LINK_ELEMENT;

// ruby_vminsn_typeはinsns.incとして生成され、以下のような感じになっている
/* BIN : Basic Instruction Name */
#define BIN(n) YARVINSN_##n

enum ruby_vminsn_type {
  BIN(nop)                       = 0,
  BIN(getlocal)                  = 1,
  BIN(setlocal)                  = 2,
  BIN(getspecial)                = 3,
  BIN(setspecial)                = 4,
  // ...
  BIN(opt_send_without_block)    = 48,
  // ...
}

というわけで1命令はstruct iseq_insn_dataで表現されており、そのinsn_idが48になっていて、VALUEが2つ(実際には3つだが、operand_sizeは2)allocateされたアドレスがoperandsに入っていそう。VALUE 1つ目はnew_callinfoの結果で、VALUE 2つ目はQfalseだが、/* cache */とか書いてあるので後からそこにキャッシュが入りそうに見える。

で、ここまでメソッドの名前とかメソッド自体の引数の数とか全く出てこないので、全部new_callinfoの結果に突っ込まれてそうなことがわかる。

new_callinfoはこういう感じで、

static struct rb_call_info *
new_callinfo(rb_iseq_t *iseq, ID mid, int argc, unsigned int flag, struct rb_call_info_kw_arg *kw_arg, int has_blockiseq)
{
    size_t size = kw_arg != NULL ? sizeof(struct rb_call_info_with_kwarg) : sizeof(struct rb_call_info);
    struct rb_call_info *ci = (struct rb_call_info *)compile_data_alloc(iseq, size);
    struct rb_call_info_with_kwarg *ci_kw = (struct rb_call_info_with_kwarg *)ci;

    ci->mid = mid;
    ci->flag = flag;
    ci->orig_argc = argc;

    if (kw_arg) {
        ci->flag |= VM_CALL_KWARG;
        ci_kw->kw_arg = kw_arg;
        ci->orig_argc += kw_arg->keyword_len;
        iseq->body->ci_kw_size++;
    }
    else {
        iseq->body->ci_size++;
    }

    if (!(ci->flag & (VM_CALL_ARGS_SPLAT | VM_CALL_ARGS_BLOCKARG)) &&
        kw_arg == NULL && !has_blockiseq) {
        ci->flag |= VM_CALL_ARGS_SIMPLE;
    }
    return ci;
}

キーワード引数がない場合は以下のような情報だけが入った構造体が返され、

struct rb_call_info {
    /* fixed at compile time */
    ID mid;
    unsigned int flag;
    int orig_argc;
};

キーワード引数がある場合は以下のように格納するデータがちょっと大きくなるようだ。

struct rb_call_info_kw_arg {
    int keyword_len;
    VALUE keywords[1];
};

struct rb_call_info_with_kwarg {
    struct rb_call_info ci;
    struct rb_call_info_kw_arg *kw_arg;
};

midにはメソッドのIDが入り、orig_argcには引数の数が入る。フラグは多分この辺の値が入りそうに見える

#define VM_CALL_ARGS_SPLAT      (0x01 << 0) /* m(*args) */
#define VM_CALL_ARGS_BLOCKARG   (0x01 << 1) /* m(&block) */
#define VM_CALL_FCALL           (0x01 << 2) /* m(...) */
#define VM_CALL_VCALL           (0x01 << 3) /* m */
#define VM_CALL_ARGS_SIMPLE     (0x01 << 4) /* (ci->flag & (SPLAT|BLOCKARG)) && blockiseq == NULL && ci->kw_arg == NULL */
#define VM_CALL_BLOCKISEQ       (0x01 << 5) /* has blockiseq */
#define VM_CALL_KWARG           (0x01 << 6) /* has kwarg */
#define VM_CALL_TAILCALL        (0x01 << 7) /* located at tail position */
#define VM_CALL_SUPER           (0x01 << 8) /* super */
#define VM_CALL_OPT_SEND        (0x01 << 9) /* internal flag */

大体見方がわかった。どうやらISeq#to_aの結果は必要な情報を全部含んでいそうに見える。

メソッドキャッシュのキャッシュミス時にどのように実行されるか

insns.def上だとこうで、

/**
  @c optimize
  @e Invoke method without block
  @j Invoke method without block
 */
DEFINE_INSN
opt_send_without_block
(CALL_INFO ci, CALL_CACHE cc)
(...)
(VALUE val) // inc += -ci->orig_argc;
{
    struct rb_calling_info calling;
    calling.block_handler = VM_BLOCK_HANDLER_NONE;
    vm_search_method(ci, cc, calling.recv = TOPN(calling.argc = ci->orig_argc));
    CALL_METHOD(&calling, ci, cc);
}

vm.inc内ではこうなっている。

INSN_ENTRY(opt_send_without_block){
{
  VALUE val;
  CALL_CACHE cc = (CALL_CACHE)GET_OPERAND(2);
  CALL_INFO ci = (CALL_INFO)GET_OPERAND(1);

  DEBUG_ENTER_INSN("opt_send_without_block");
  ADD_PC(1+2);
  PREFETCH(GET_PC());
  #define CURRENT_INSN_opt_send_without_block 1
  #define INSN_IS_SC()     0
  #define INSN_LABEL(lab)  LABEL_opt_send_without_block_##lab
  #define LABEL_IS_SC(lab) LABEL_##lab##_##t
  COLLECT_USAGE_INSN(BIN(opt_send_without_block));
  COLLECT_USAGE_OPERAND(BIN(opt_send_without_block), 0, ci);
  COLLECT_USAGE_OPERAND(BIN(opt_send_without_block), 1, cc);
{
#line 1063 "insns.def"
    struct rb_calling_info calling;
    calling.block_handler = VM_BLOCK_HANDLER_NONE;
    vm_search_method(ci, cc, calling.recv = TOPN(calling.argc = ci->orig_argc));
    CALL_METHOD(&calling, ci, cc);

#line 1579 "vm.inc"
  CHECK_VM_STACK_OVERFLOW_FOR_INSN(REG_CFP, 1);
  PUSH(val);
#undef CURRENT_INSN_opt_send_without_block
#undef INSN_IS_SC
#undef INSN_LABEL
#undef LABEL_IS_SC
  END_INSN(opt_send_without_block);}}}

本体のブロックの外側は…あんまり関係ある部分がない気がするので貼りつけたけど無視する。

で、最初のこの部分だけど、

    struct rb_calling_info calling;
    calling.block_handler = VM_BLOCK_HANDLER_NONE;
    vm_search_method(ci, cc, calling.recv = TOPN(calling.argc = ci->orig_argc));

rb_calling_infoは以下のようになっている

struct rb_calling_info {
    VALUE block_handler;
    VALUE recv;
    int argc;
};

argc, block_handlerはまあ見たまんまという感じだが、TOPNというのはスタックの上からN個目を参照する奴で、スタックトップには引数たちがあり、その下にレシーバがpushされている状態になっていると思われる。

なおこの行で完成するcallingは、実際にはvm_search_methodには渡されていなくて、次のCALL_METHODで使われる。

というわけで、vm_search_methodは以下のような感じ(もちろんvalidなCのコードではない)で呼び出される。

vm_search_method(
  struct rb_call_info {
    ID mid; /* メソッドID */
    unsigned int flag; /* メソッドの呼び出し方のフラグ */
    int orig_argc; /* 引数の数 */
  },
  struct rb_call_cache { // 後述するが、Qfalseではなく、このstructが初期化された値が入る
    /* inline cache: keys */
    rb_serial_t method_state;
    rb_serial_t class_serial;

    /* inline cache: values */
    const rb_callable_method_entry_t *me;

    vm_call_handler call;

    union {
      unsigned int index; /* used by ivar */
      enum method_missing_reason method_missing_reason; /* used by method_missing */
      int inc_sp; /* used by cfunc */
    } aux;
  };,
  TOPN(rb_call_info->orig_argc) /* レシーバ */
)

vm_search_methodは何をするか

static void
vm_search_method(const struct rb_call_info *ci, struct rb_call_cache *cc, VALUE recv)
{
    VALUE klass = CLASS_OF(recv);

#if OPT_INLINE_METHOD_CACHE
    if (LIKELY(GET_GLOBAL_METHOD_STATE() == cc->method_state && RCLASS_SERIAL(klass) == cc->class_serial)) {
        /* cache hit! */
        VM_ASSERT(cc->call != NULL);
        return;
    }
#endif

    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;
#if OPT_INLINE_METHOD_CACHE
    cc->method_state = GET_GLOBAL_METHOD_STATE();
    cc->class_serial = RCLASS_SERIAL(klass);
#endif
}

vm_opts.hで#define OPT_INLINE_METHOD_CACHE 1となっているので、

static void
vm_search_method(const struct rb_call_info *ci, struct rb_call_cache *cc, VALUE recv)
{
    VALUE klass = CLASS_OF(recv);

    if (LIKELY(GET_GLOBAL_METHOD_STATE() == cc->method_state && RCLASS_SERIAL(klass) == cc->class_serial)) {
        /* cache hit! */
        VM_ASSERT(cc->call != NULL);
        return;
    }

    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;
    cc->method_state = GET_GLOBAL_METHOD_STATE();
    cc->class_serial = RCLASS_SERIAL(klass);
}

という感じになる。まあ、残しておいた方がどこがインラインメソッドキャッシュに使われるのかわかって便利な気もする。

キャッシュが効かないケースの動作

このセクションでは先にキャッシュ以外の場所を見ていく。

    VALUE klass = CLASS_OF(recv);
    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;

CLASS_OFは#define CLASS_OF(v) rb_class_of((VALUE)(v))だ。まあ、メソッド呼び出しの時は最初にクラスを取りにいく必要はありそう。
iseqのコンパイル時にQfalseが入ると説明したccに対してcc->meにいきなり代入を行なっているが、これは以下のようにiseqのコンパイル後の処理でccが初期化されるためである。

call cacheの初期化回り

デバッガで見てみたけどコンパイル時点ではQfalseが入っている。というか#to_aでシリアライズしてfalseが入ってるんだからコンパイル結果はそうなのだろう。

…ここで割と時間をかけて読んでたが全くわからないので一旦諦め、どこでcall cacheが最初にセットされるかは後で探す…

……いやもう一度見ていたがわからなかった……

あ、いや、わかった(ISeqのシリアライズにしか使われないんじゃないかと思っていたがまあそこしか生成してないよなみたいなところにブレークポイントをはって実行したところ止まったので、バックトレースを見てわかった)。まず、パースしたASTをiseqにコンパイルする際、rb_iseq_new_with_optが呼び出される。

preludeの例: https://github.com/ruby/ruby/blob/trunk/template/prelude.c.tmpl#L126-L127
(普通に実行しているファイルはどこを通るかは調べてないが、パッと見rb_iseq_new経由で叩きそうに見える)

で、rb_iseq_new_with_optの中で実際にコンパイルを行う部分はrb_iseq_compile_node(iseq, node);で、
https://github.com/ruby/ruby/blob/v2_4_1/iseq.c#L483

例えばpreludeの場合はrb_iseq_new_with_optを呼び出す時にISEQ_TYPE_TOPをtypeとして渡しているので、多分ここに来る。実際COMPILE(anchor, desc, node)はiseq_compile_each(iseq, (anchor), (node), 0)になるので、実際のiseqのコンパイルの処理の呼び出しはここで行なわれていることがわかる。
https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L620

で、そのコンパイルを抜けた後、必ずiseq_setupに到達する。
https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L673

iseq_setupはコンパイル後のiseqに対し最適化などをいろいろやっているが、iseq_set_sequenceというのを呼び出す。
https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L1159

完全に追いかけられているわけではないが、ここでallocした奴を
https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L1633

ここでセットしているんじゃないだろうか
https://github.com/ruby/ruby/blob/v2_4_1/compile.c#L1758-L1759

rb_callable_method_entry以降

気を取り直して続きを読んでいく。

    VALUE klass = CLASS_OF(recv);
    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;

call cacheの構造体の定義はこうだ。

struct rb_call_cache;
typedef VALUE (*vm_call_handler)(struct rb_thread_struct *th, struct rb_control_frame_struct *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc);

struct rb_call_cache {
    /* inline cache: keys */
    rb_serial_t method_state;
    rb_serial_t class_serial;

    /* inline cache: values */
    const rb_callable_method_entry_t *me;

    vm_call_handler call;

    union {
        unsigned int index; /* used by ivar */
        enum method_missing_reason method_missing_reason; /* used by method_missing */
        int inc_sp; /* used by cfunc */
    } aux;
};

typedef struct rb_call_cache *CALL_CACHE;

#if defined(HAVE_LONG_LONG)
typedef unsigned LONG_LONG rb_serial_t;
#define SERIALT2NUM ULL2NUM
#elif defined(HAVE_UINT64_T)
typedef uint64_t rb_serial_t;
#define SERIALT2NUM SIZET2NUM
#else
typedef unsigned long rb_serial_t;
#define SERIALT2NUM ULONG2NUM
#endif

環境によってサイズは異なるint値のmethod_state, class_serial、残りはポインタ2つとunionで、まあ最初はZALLOC_Nを呼び出した時に0で初期化されているのではないだろうか。method_stateとclass_serialはキャッシュがヒットしたかどうかの判定に使われており、まあ両方0ならこっちのフローに入ってきそう。

探索したklassとメソッドIDを引数にrb_callable_method_entryを呼び出す。

const rb_callable_method_entry_t *
rb_callable_method_entry(VALUE klass, ID id)
{
    VALUE defined_class;
    rb_method_entry_t *me = method_entry_get(klass, id, &defined_class);
    return prepare_callable_method_entry(defined_class, id, me);
}

クラスとメソッドIDからmethod_entry_getを行ってrb_method_entry_t *の値を取得した後、prepare_callable_method_entryをやるとrb_callable_method_entry_t *になるらしい。

なおmethod_entry_getやrb_callable_method_entryは、適当にrb_funcallでメソッド呼び出しをしまくるCのコードに対してperfをかけていると、rb_call系の関数の次に多くサンプリングされる関数になっている。
なお、次いで多く出現するrb_search_method_entryはCLASS_OFをした後NotImplementedErrorの判定をし、rb_callable_method_entryを呼び出すだけの関数であり、まあ多分この辺は重い処理だ(opt_send_without_blockでは通らないということになる)。これらをやっているvm_search_methodもまあ重い関数ということになるが、実際optcarrotだとvm_exec_coreの次くらい(5%)に来る。

これらの結果は以下のようなstructになっている。

typedef struct rb_method_entry_struct {
    VALUE flags;
    const VALUE defined_class;
    struct rb_method_definition_struct * const def;
    ID called_id;
    const VALUE owner;
} rb_method_entry_t;

typedef struct rb_callable_method_entry_struct { /* same fields with rb_method_entry_t */
    VALUE flags;
    const VALUE defined_class;
    struct rb_method_definition_struct * const def;
    ID called_id;
    const VALUE owner;
} rb_callable_method_entry_t;

どっちも中身は同じである。重要なのは実際のメソッド定義が入っている場所である。

typedef struct rb_method_definition_struct {
    rb_method_type_t type :  8; /* method type */
    int alias_count       : 28;
    int complemented_count: 28;

    union {
        rb_method_iseq_t iseq;
        rb_method_cfunc_t cfunc;
        rb_method_attr_t attr;
        rb_method_alias_t alias;
        rb_method_refined_t refined;

        const VALUE proc;                 /* should be marked */
        enum method_optimized_type {
            OPTIMIZED_METHOD_TYPE_SEND,
            OPTIMIZED_METHOD_TYPE_CALL,

            OPTIMIZED_METHOD_TYPE__MAX
        } optimize_type;
    } body;

    ID original_id;
} rb_method_definition_t;

rb_method_entry_t *の値は以下のようなツリーの呼び出しでrb_id_table_lookupに到達しセットされる。このdefにあたる部分を含めもともとセットされていて、メソッド探索時に作っているわけではなさそう。

  • rb_callable_method_entry
    • method_entry_get
      • method_entry_get_without_cache
        • search_method
          • lookup_method_table ← ここで呼ばれる

さて、実際のルックアップは後で見ることにするが、とりあえずメソッド定義のデータ構造がどうなっていて、どの関数で取得されるかというところまではわかった。

vm_call_generalのセット
    VALUE klass = CLASS_OF(recv);
    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;

typedef VALUE (*vm_call_handler)(struct rb_thread_struct *th, struct rb_control_frame_struct *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc);

struct rb_call_cache {
    /* inline cache: keys */
    rb_serial_t method_state;
    rb_serial_t class_serial;

    /* inline cache: values */
    const rb_callable_method_entry_t *me;

    vm_call_handler call;

    union {
        unsigned int index; /* used by ivar */
        enum method_missing_reason method_missing_reason; /* used by method_missing */
        int inc_sp; /* used by cfunc */
    } aux;
};

インラインキャッシュの判定に使われるmethod_stateとclass_serial、およびunionを除くとmeとcallがあるが、このうちメソッド定義にあたるmeのセットは終わった。callの方にはvm_call_generalを固定でセットしている。が、これはその中でvm_call_method_each_typeに到達した時にCI_SET_FASTPATHというマクロによってcall cacheのcallがすりかえられるため、2回目以降は呼び出しがちょっと速くなるはずである。

vm_call_generalの定義はこうなっている。

static VALUE
vm_call_general(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    return vm_call_method(th, reg_cfp, calling, ci, cc);
}

関数ポインタとしてcallにこれがつっこまれることになる。

CALL_METHODは何をするか

/**
  @c optimize
  @e Invoke method without block
  @j Invoke method without block
 */
DEFINE_INSN
opt_send_without_block
(CALL_INFO ci, CALL_CACHE cc)
(...)
(VALUE val) // inc += -ci->orig_argc;
{
    struct rb_calling_info calling;
    calling.block_handler = VM_BLOCK_HANDLER_NONE;
    vm_search_method(ci, cc, calling.recv = TOPN(calling.argc = ci->orig_argc));
    CALL_METHOD(&calling, ci, cc);
}

最後の呼び出しCALL_METHOD(&calling, ci, cc);のうち、callingは

struct rb_calling_info {
    VALUE block_handler; /* VM_BLOCK_HANDLER_NONE が入る */
    VALUE recv; /* スタックから取得されたレシーバが入る */
    int argc; /* opt_send_without_block命令の1つ目のオペランドcalling infoからargcがセットされる*/
};

であり、ciはコンパイル時に確定するオペランド1つ目で、

struct rb_call_info {
    ID mid; /* メソッドID */
    unsigned int flag; /* メソッド呼び出し方法のフラグ */
    int orig_argc; /* メソッド引数の数、calling.argc と同じ */
};

ccはコンパイル後初期化されているcall cacheであり、meとcallがvm_search_methodによってセットされている。

typedef VALUE (*vm_call_handler)(struct rb_thread_struct *th, struct rb_control_frame_struct *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc);

struct rb_call_cache {
    /* inline cache: keys */
    rb_serial_t method_state;
    rb_serial_t class_serial;

    /* inline cache: values */
    const rb_callable_method_entry_t *me; /* vm_search_methodの結果がここに入る */
    vm_call_handler call; /* vm_call_general の関数ポインタが固定で入る */

    union {
        unsigned int index; /* used by ivar */
        enum method_missing_reason method_missing_reason; /* used by method_missing */
        int inc_sp; /* used by cfunc */
    } aux;
};

typedef struct rb_callable_method_entry_struct {
    VALUE flags;
    const VALUE defined_class;
    struct rb_method_definition_struct * const def;
    ID called_id;
    const VALUE owner;
} rb_callable_method_entry_t;

typedef struct rb_method_definition_struct {
    rb_method_type_t type :  8; /* method type */
    int alias_count       : 28;
    int complemented_count: 28;

    union {
        rb_method_iseq_t iseq;
        rb_method_cfunc_t cfunc;
        rb_method_attr_t attr;
        rb_method_alias_t alias;
        rb_method_refined_t refined;

        const VALUE proc;                 /* should be marked */
        enum method_optimized_type {
            OPTIMIZED_METHOD_TYPE_SEND,
            OPTIMIZED_METHOD_TYPE_CALL,

            OPTIMIZED_METHOD_TYPE__MAX
        } optimize_type;
    } body;

    ID original_id;
} rb_method_definition_t;

まあ、必要な情報は全部揃ってそうだ。

で、CALL_METHODの定義はこうだ。「バックトレースの管理などメソッド本体の処理以外には何が行なわれているのか」は多分全てこちらに入っているので、それに気をつけながら読む。

#define CALL_METHOD(calling, ci, cc) do { \
    VALUE v = (*(cc)->call)(th, GET_CFP(), (calling), (ci), (cc)); \
    if (v == Qundef) { \
        RESTORE_REGS(); \
        NEXT_INSN(); \
    } \
    else { \
        val = v; \
    } \
} while (0)

(cc)->callの中にはvm_call_generalの関数ポインタが入っていることがわかっているので、vm_call_generalがvm_exec_coreが持つスレッド、コントロールフレームレジスタ(reg_cfp)、calling, ci, ccを引数に呼び出されることがわかる。

vm_call_generalの処理は以下のようになっている。

static VALUE
vm_call_general(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    return vm_call_method(th, reg_cfp, calling, ci, cc);
}

static inline VALUE
vm_call_method(rb_thread_t *th, rb_control_frame_t *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    VM_ASSERT(callable_method_entry_p(cc->me));

    if (cc->me != NULL) {
        switch (METHOD_ENTRY_VISI(cc->me)) {
          case METHOD_VISI_PUBLIC: /* likely */
            return vm_call_method_each_type(th, cfp, calling, ci, cc);

          case METHOD_VISI_PRIVATE:
            if (!(ci->flag & VM_CALL_FCALL)) {
                enum method_missing_reason stat = MISSING_PRIVATE;
                if (ci->flag & VM_CALL_VCALL) stat |= MISSING_VCALL;

                cc->aux.method_missing_reason = stat;
                CI_SET_FASTPATH(cc, vm_call_method_missing, 1);
                return vm_call_method_missing(th, cfp, calling, ci, cc);
            }
            return vm_call_method_each_type(th, cfp, calling, ci, cc);

          case METHOD_VISI_PROTECTED:
            if (!(ci->flag & VM_CALL_OPT_SEND)) {
                if (!rb_obj_is_kind_of(cfp->self, cc->me->defined_class)) {
                    cc->aux.method_missing_reason = MISSING_PROTECTED;
                    return vm_call_method_missing(th, cfp, calling, ci, cc);
                }
                else {
                    /* caching method info to dummy cc */
                    struct rb_call_cache cc_entry;
                    cc_entry = *cc;
                    cc = &cc_entry;

                    VM_ASSERT(cc->me != NULL);
                    return vm_call_method_each_type(th, cfp, calling, ci, cc);
                }
            }
            return vm_call_method_each_type(th, cfp, calling, ci, cc);

          default:
            rb_bug("unreachable");
        }
    }
    else {
        return vm_call_method_nome(th, cfp, calling, ci, cc);
    }
}

#define METHOD_ENTRY_VISI(me)  (rb_method_visibility_t)(((me)->flags & (IMEMO_FL_USER0 | IMEMO_FL_USER1)) >> (IMEMO_FL_USHIFT+0))

まずメソッドのvisibilityにより分岐する。cc->meにはvm_search_methodの結果が入っているので、メソッド定義の方の処理を追わないと正確にはわからないが、まあ見ればpublic, private, protectedで定義されたかのフラグが入っていてそれを見ているということがわかる。

なので、vm_call_method_each_type(th, cfp, calling, ci, cc);が呼び出されることになる。privateとかprotectedだと余計な処理が入るようだ。

static VALUE
vm_call_method_each_type(rb_thread_t *th, rb_control_frame_t *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    switch (cc->me->def->type) {
      case VM_METHOD_TYPE_ISEQ:
        CI_SET_FASTPATH(cc, vm_call_iseq_setup, TRUE);
        return vm_call_iseq_setup(th, cfp, calling, ci, cc);

      case VM_METHOD_TYPE_NOTIMPLEMENTED:
      case VM_METHOD_TYPE_CFUNC:
        CI_SET_FASTPATH(cc, vm_call_cfunc, TRUE);
        return vm_call_cfunc(th, cfp, calling, ci, cc);

        // ...
      }
    }

    rb_bug("vm_call_method: unsupported method type (%d)", cc->me->def->type);
}

VM_METHOD_TYPE_ISEQの場合

vm_call_iseq_setupが呼び出される

static VALUE
vm_call_iseq_setup(rb_thread_t *th, rb_control_frame_t *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    const rb_iseq_t *iseq = def_iseq_ptr(cc->me->def);
    const int param_size = iseq->body->param.size;
    const int local_size = iseq->body->local_table_size;
    const int opt_pc = vm_callee_setup_arg(th, calling, ci, cc, def_iseq_ptr(cc->me->def), cfp->sp - calling->argc, param_size, local_size);
    return vm_call_iseq_setup_2(th, cfp, calling, ci, cc, opt_pc, param_size, local_size);
}


static inline int
vm_callee_setup_arg(rb_thread_t *th, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc,
                    const rb_iseq_t *iseq, VALUE *argv, int param_size, int local_size)
{
    if (LIKELY(simple_iseq_p(iseq))) {
        rb_control_frame_t *cfp = th->cfp;

        CALLER_SETUP_ARG(cfp, calling, ci); /* splat arg */

        if (calling->argc != iseq->body->param.lead_num) {
            argument_arity_error(th, iseq, calling->argc, iseq->body->param.lead_num, iseq->body->param.lead_num);
        }

        CI_SET_FASTPATH(cc, vm_call_iseq_setup_func(ci, param_size, local_size),
                        (!IS_ARGS_SPLAT(ci) && !IS_ARGS_KEYWORD(ci) &&
                         !(METHOD_ENTRY_VISI(cc->me) == METHOD_VISI_PROTECTED)));
        return 0;
    }
    else {
        return setup_parameters_complex(th, iseq, calling, ci, argv, arg_setup_method);
    }
}

static inline VALUE
vm_call_iseq_setup_2(rb_thread_t *th, rb_control_frame_t *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc,
                     int opt_pc, int param_size, int local_size)
{
    if (LIKELY(!(ci->flag & VM_CALL_TAILCALL))) {
        return vm_call_iseq_setup_normal(th, cfp, calling, ci, cc, opt_pc, param_size, local_size); // こっち
    }
    else {
        return vm_call_iseq_setup_tailcall(th, cfp, calling, ci, cc, opt_pc);
    }
}

static inline VALUE
vm_call_iseq_setup_normal(rb_thread_t *th, rb_control_frame_t *cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc,
                          int opt_pc, int param_size, int local_size)
{
    const rb_callable_method_entry_t *me = cc->me;
    const rb_iseq_t *iseq = def_iseq_ptr(me->def);
    VALUE *argv = cfp->sp - calling->argc;
    VALUE *sp = argv + param_size;
    cfp->sp = argv - 1 /* recv */;

    vm_push_frame(th, iseq, VM_FRAME_MAGIC_METHOD | VM_ENV_FLAG_LOCAL, calling->recv,
                  calling->block_handler, (VALUE)me,
                  iseq->body->iseq_encoded + opt_pc, sp,
                  local_size - param_size,
                  iseq->body->stack_max);
    return Qundef;
}

static inline rb_control_frame_t *
vm_push_frame(rb_thread_t *th,
              const rb_iseq_t *iseq,
              VALUE type,
              VALUE self,
              VALUE specval,
              VALUE cref_or_me,
              const VALUE *pc,
              VALUE *sp,
              int local_size,
              int stack_max)
{
    rb_control_frame_t *const cfp = th->cfp - 1;
    int i;

    vm_check_frame(type, specval, cref_or_me, iseq);
    VM_ASSERT(local_size >= 0);

    /* check stack overflow */
    CHECK_VM_STACK_OVERFLOW0(cfp, sp, local_size + stack_max);

    th->cfp = cfp;

    /* setup new frame */
    cfp->pc = (VALUE *)pc;
    cfp->iseq = (rb_iseq_t *)iseq;
    cfp->self = self;
    cfp->block_code = NULL;

    /* setup vm value stack */

    /* initialize local variables */
    for (i=0; i < local_size; i++) {
        *sp++ = Qnil;
    }

    /* setup ep with managing data */
    VM_ASSERT(VM_ENV_DATA_INDEX_ME_CREF == -2);
    VM_ASSERT(VM_ENV_DATA_INDEX_SPECVAL == -1);
    VM_ASSERT(VM_ENV_DATA_INDEX_FLAGS   == -0);
    *sp++ = cref_or_me; /* ep[-2] / Qnil or T_IMEMO(cref) or T_IMEMO(ment) */
    *sp++ = specval     /* ep[-1] / block handler or prev env ptr */;
    *sp   = type;       /* ep[-0] / ENV_FLAGS */

    cfp->ep = sp;
    cfp->sp = sp + 1;

#if VM_DEBUG_BP_CHECK
    cfp->bp_check = sp + 1;
#endif

    if (VMDEBUG == 2) {
        SDR();
    }

    return cfp;
}

vm_callee_setup_argによって引数のセットアップを行い、探してきたメソッドのiseqを使ったコントロールフレームをvm_push_frameによってpushし、ローカル変数の初期化を行うようだ。

CALL_METHODの1行目であるVALUE v = (*(cc)->call)(th, GET_CFP(), (calling), (ci), (cc));では、後述するvm_call_cfunc(Cで実装されているメソッドの呼び出し)はそのメソッドの結果がVALUE vに入るのに対し、vm_call_iseq_setupだと全く実際の処理が始まらないことになる。

では、VALUE vの結果はどうなってしまうのか？ この場合、どのようにしてメソッドの実際の処理が走り、返り値が引き渡されるのか？

これを理解する上で注目しなければならないのは、以下の2点である。

  • vm_call_iseq_setup_normalはvm_push_frameを呼び出しており、vm_push_frameはth->cfpを新しいコントロールフレーム(th->cfp - 1)に変更する
  • vm_call_iseq_setup_normalはQundefを返す

再びCALL_METHODの定義を見返してみるとこうだ。

#define CALL_METHOD(calling, ci, cc) do { \
    VALUE v = (*(cc)->call)(th, GET_CFP(), (calling), (ci), (cc)); \
    if (v == Qundef) { \
        RESTORE_REGS(); \
        NEXT_INSN(); \
    } \
    else { \
        val = v; \
    } \
} while (0)

#define RESTORE_REGS() do { \
    VM_REG_CFP = th->cfp; \
} while (0)

#define NEXT_INSN() TC_DISPATCH(__NEXT_INSN__)
#define TC_DISPATCH(insn) \
  INSN_DISPATCH_SIG(insn); \
  goto *(void const *)GET_CURRENT_INSN(); \
#define INSN_DISPATCH_SIG(insn)
#define GET_CURRENT_INSN() (*GET_PC())
#define GET_PC()           (COLLECT_USAGE_REGISTER_HELPER(PC, GET, VM_REG_PC))
#define VM_REG_PC  (VM_REG_CFP->pc)
#define VM_REG_CFP (reg_cfp)

まず、Qundefが返されるので、opt_send_without_blockの最後の処理はRESTORE_REGS()とNEXT_INSN()であることになる。この命令は本来CALL_METHODの後にPUSH(val)でメソッド呼び出しの結果をスタックに積むのだが、NEXT_INSN()はgotoを行なうので、スタックに結果をプッシュせず次に行くことになる。

で、このRESTORE_REGSはreg_cfp = th->cfp;をやっているわけだが、これがどういう意味なのかが大分わかりにくい。YARVの中で、reg_cfpとth->cfpの結果は常に同じことを意味するわけではないのである。なのでYARVのコードを読む時、reg_cfpとth->cfpのどちらが参照されているかはかなり注意して読む必要がある。なお、VM_REG_*とかGET_*()系は全部reg_cfpをベースに参照している。

「vm_push_frameはth->cfpを新しいコントロールフレーム(th->cfp - 1)に変更する」ということを伸べた。容易に想像できることだが、vm_pop_frameはth->cfpを前のコントロールフレーム((cfp)+1)に変更する。

つまりRESTORE_REGSが何をするかというと、vm_push_frame/vm_pop_frameでth->cfpを変更した後に呼び出し、reg_cfpにth->cfpをセットすることで 現在のvm_exec_core呼び出しでpush/pop後のフレームの処理が始まるようにする のである。

reg_cfpをth->cfp - 1に移した後NEXT_INSN()`が呼ばれるわけだが、これは上記の定義から展開すると以下のようになる。

goto *(void const *)(*(reg_cfp->pc));

ここまで展開しておくと大分わかりやすい。プッシュしたフレームのプログラムカウンターが指している命令にgotoする。これによって呼び出したメソッドの処理がすぐ始まるわけである。

このメソッドの処理が終わった後呼び出し側に制御が戻る時にどのように元のスタックに結果が積まれるのかはまたあとで読む。

VM_METHOD_TYPE_CFUNCの場合

vm_call_cfuncが呼び出される

#if OPT_CALL_CFUNC_WITHOUT_FRAME
static VALUE
vm_call_cfunc_latter(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling)
{
    VALUE val;
    int argc = calling->argc;
    VALUE *argv = STACK_ADDR_FROM_TOP(argc);
    VALUE recv = calling->recv;
    const rb_method_cfunc_t *cfunc = vm_method_cfunc_entry(cc->me);

    th->passed_calling = calling;
    reg_cfp->sp -= argc + 1;
    ci->aux.inc_sp = argc + 1;
    VM_PROFILE_UP(R2C_CALL);
    val = (*cfunc->invoker)(cfunc->func, recv, argc, argv);

    /* check */
    if (reg_cfp == th->cfp) { /* no frame push */
        if (UNLIKELY(th->passed_ci != ci)) {
            rb_bug("vm_call_cfunc_latter: passed_ci error (ci: %p, passed_ci: %p)", ci, th->passed_ci);
        }
        th->passed_ci = 0;
    }
    else {
        if (UNLIKELY(reg_cfp != RUBY_VM_PREVIOUS_CONTROL_FRAME(th->cfp))) {
            rb_bug("vm_call_cfunc_latter: cfp consistency error (%p, %p)", reg_cfp, th->cfp+1);
        }
        vm_pop_frame(th, reg_cfp, reg_cfp->ep);
        VM_PROFILE_UP(R2C_POPF);
    }

    return val;
}

static VALUE
vm_call_cfunc(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling, const struct rb_call_info *ci)
{
    VALUE val;
    const rb_callable_method_entry_t *me = cc->me;
    int len = vm_method_cfunc_entry(me)->argc;
    VALUE recv = calling->recv;

    CALLER_SETUP_ARG(reg_cfp, calling, ci);
    if (len >= 0) rb_check_arity(calling->argc, len, len);

    RUBY_DTRACE_CMETHOD_ENTRY_HOOK(th, me->owner, me->called_id);
    EXEC_EVENT_HOOK(th, RUBY_EVENT_C_CALL, recv, me->called_id, me->owner, Qnil);

    if (!(cc->me->def->flag & METHOD_VISI_PROTECTED) &&
        !(ci->flag & VM_CALL_ARGS_SPLAT) &&
        !(ci->kw_arg != NULL)) {
        CI_SET_FASTPATH(cc, vm_call_cfunc_latter, 1);
    }
    val = vm_call_cfunc_latter(th, reg_cfp, calling);

    EXEC_EVENT_HOOK(th, RUBY_EVENT_C_RETURN, recv, me->called_id, me->owner, val);
    RUBY_DTRACE_CMETHOD_RETURN_HOOK(th, me->owner, me->called_id);

    return val;
}

void
rb_vm_call_cfunc_push_frame(rb_thread_t *th)
{
    struct rb_calling_info *calling = th->passed_calling;
    const rb_callable_method_entry_t *me = calling->me;
    th->passed_ci = 0;

    vm_push_frame(th, 0, VM_FRAME_MAGIC_CFUNC | VM_FRAME_FLAG_CFRAME | VM_ENV_FLAG_LOCAL,
                  calling->recv, calling->block_handler, (VALUE)me /* cref */,
                  0, th->cfp->sp + cc->aux.inc_sp, 0, 0);

    if (calling->call != vm_call_general) {
        calling->call = vm_call_cfunc_with_frame;
    }
}
#else /* OPT_CALL_CFUNC_WITHOUT_FRAME */
static VALUE
vm_call_cfunc(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    CALLER_SETUP_ARG(reg_cfp, calling, ci);
    return vm_call_cfunc_with_frame(th, reg_cfp, calling, ci, cc);
}
#endif

OPT_CALL_CFUNC_WITHOUT_FRAME はデフォルトでは切られている。なので、vm_call_cfunc_with_frameをするだけになる。

vm_call_cfunc_with_frameは、

static VALUE
vm_call_cfunc_with_frame(rb_thread_t *th, rb_control_frame_t *reg_cfp, struct rb_calling_info *calling, const struct rb_call_info *ci, struct rb_call_cache *cc)
{
    VALUE val;
    const rb_callable_method_entry_t *me = cc->me;
    const rb_method_cfunc_t *cfunc = vm_method_cfunc_entry(me);
    int len = cfunc->argc;

    VALUE recv = calling->recv;
    VALUE block_handler = calling->block_handler;
    int argc = calling->argc;

    RUBY_DTRACE_CMETHOD_ENTRY_HOOK(th, me->owner, me->def->original_id);
    EXEC_EVENT_HOOK(th, RUBY_EVENT_C_CALL, recv, me->def->original_id, ci->mid, me->owner, Qundef);

    vm_push_frame(th, NULL, VM_FRAME_MAGIC_CFUNC | VM_FRAME_FLAG_CFRAME | VM_ENV_FLAG_LOCAL, recv,
                  block_handler, (VALUE)me,
                  0, th->cfp->sp, 0, 0);

    if (len >= 0) rb_check_arity(argc, len, len);

    reg_cfp->sp -= argc + 1;
    VM_PROFILE_UP(R2C_CALL);
    val = (*cfunc->invoker)(cfunc->func, recv, argc, reg_cfp->sp + 1);

    if (reg_cfp != th->cfp + 1) {
        rb_bug("vm_call_cfunc - cfp consistency error");
    }

    rb_vm_pop_frame(th);

    EXEC_EVENT_HOOK(th, RUBY_EVENT_C_RETURN, recv, me->def->original_id, ci->mid, me->owner, val);
    RUBY_DTRACE_CMETHOD_RETURN_HOOK(th, me->owner, me->def->original_id);

    return val;
}

Rubyの場合と同じくフレームのpush, popを行なう。実際のメソッドの起動は(*cfunc->invoker)(cfunc->func, recv, argc, reg_cfp->sp + 1)である。

invokerは以下のように関数がセットされる。

static void
setup_method_cfunc_struct(rb_method_cfunc_t *cfunc, VALUE (*func)(), int argc)
{
    cfunc->func = func;
    cfunc->argc = argc;
    cfunc->invoker = call_cfunc_invoker_func(argc);
}

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);
    }
}


static VALUE
call_cfunc_m2(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv)
{
    return (*func)(recv, rb_ary_new4(argc, argv));
}

static VALUE
call_cfunc_m1(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv)
{
    return (*func)(argc, argv, recv);
}

static VALUE
call_cfunc_0(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv)
{
    return (*func)(recv);
}

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

// ...

大分素朴な実装という感じがする。argvを展開しているだけなので、argcも渡しているしva_argを使って実装できそうだが、まあこう書いて遅くなるということはなさそう。

メソッド探索はどのように行なわれるか

先ほど飛ばした以下のツリーに戻る。

  • rb_callable_method_entry
    • method_entry_get
      • method_entry_get_without_cache
        • search_method
          • lookup_method_table ← ここで呼ばれる

まず、method_entry_getにグローバルメソッドキャッシュの実装がある。

static rb_method_entry_t *
method_entry_get(VALUE klass, ID id, VALUE *defined_class_ptr)
{
#if OPT_GLOBAL_METHOD_CACHE
    struct cache_entry *ent;
    ent = GLOBAL_METHOD_CACHE(klass, id);
    if (ent->method_state == GET_GLOBAL_METHOD_STATE() &&
        ent->class_serial == RCLASS_SERIAL(klass) &&
        ent->mid == id) {
#if VM_DEBUG_VERIFY_METHOD_CACHE
        verify_method_cache(klass, id, ent->defined_class, ent->me);
#endif
        if (defined_class_ptr) *defined_class_ptr = ent->defined_class;
        return ent->me;
    }
#endif

    return method_entry_get_without_cache(klass, id, defined_class_ptr);
}

キャッシュの仕組み自体は次のセクションでインラインキャッシュとまとめて見ていくとして、本体の検索処理は、

static inline rb_method_entry_t*
search_method(VALUE klass, ID id, VALUE *defined_class_ptr)
{
    rb_method_entry_t *me;

    for (me = 0; klass; klass = RCLASS_SUPER(klass)) {
        if ((me = lookup_method_table(klass, id)) != 0) break;
    }

    if (defined_class_ptr)
        *defined_class_ptr = klass;
    return me;
}

見つかるまで親クラスをlookup_method_tableしながら辿っていくことがわかる。これはとてもわかりやすい。Ruby under a microscopeでも説明されている内容。

では、lookup_method_tableは何をやっているか。

static inline rb_method_entry_t *
lookup_method_table(VALUE klass, ID id)
{
    st_data_t body;
    struct rb_id_table *m_tbl = RCLASS_M_TBL(klass);

    if (rb_id_table_lookup(m_tbl, id, &body)) {
        return (rb_method_entry_t *) body;
    }
    else {
        return 0;
    }
}

#define RCLASS_M_TBL(c) (RCLASS(c)->m_tbl)
#define RCLASS(obj)  (R_CAST(RClass)(obj))
#define R_CAST(st)   (struct st*)

struct RClass {
    struct RBasic basic;
    VALUE super;
    rb_classext_t *ptr;
    struct rb_id_table *m_tbl;
};

ここまではいいが、rb_id_tableとrb_id_table_lookupの実態はgrepしても全くひっかからない。とりあえず以下のあたりが関係がありそう。

struct rb_id_table;

#define TOKEN_PASTE(x,y) x##y
#define IMPL1(name, op) TOKEN_PASTE(name, _id##op) /* expand `name' */
#define IMPL(op)        IMPL1(ID_TABLE_NAME, _table##op) /* but prevent `op' */

#define IMPL_TYPE1(type, prot, name, args) \
    RUBY_ALIAS_FUNCTION_TYPE(type, prot, name, args)
#define IMPL_TYPE(type, name, prot, args) \
    IMPL_TYPE1(type, rb_id_table_##name prot, IMPL(_##name), args)
#define id_tbl (ID_TABLE_IMPL_TYPE *)tbl

IMPL_TYPE(int, lookup, (struct rb_id_table *tbl, ID id, VALUE *valp),
      (id_tbl, id, valp))

#define RUBY_ALIAS_FUNCTION_TYPE(type, prot, name, args) \
    FUNC_MINIMIZED(type prot) {return (type)name args;}
#endif
#define FUNC_MINIMIZED(x) x

#define ID_TABLE_NAME mix
#define ID_TABLE_IMPL_TYPE struct mix_id_table

使っていない実装のための抽象化があるため読むのが難しいが、真ん中の奴を展開していくと、

IMPL_TYPE(int, lookup, (struct rb_id_table *tbl, ID id, VALUE *valp), (id_tbl, id, valp))
IMPL_TYPE1(int, rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp), IMPL(_lookup), (id_tbl, id, valp))
IMPL_TYPE1(int, rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp), IMPL1(ID_TABLE_NAME, _table_lookup), (id_tbl, id, valp))
IMPL_TYPE1(int, rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp), TOKEN_PASTE(ID_TABLE_NAME, _id_table_lookup), (id_tbl, id, valp))
IMPL_TYPE1(int, rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp), mix_id_table_lookup, (id_tbl, id, valp))
RUBY_ALIAS_FUNCTION_TYPE(int, rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp), mix_id_table_lookup, (id_tbl, id, valp))
FUNC_MINIMIZED(int rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp)) {return (int)mix_id_table_lookup(id_tbl, id, valp);}
int rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp) {return (int)mix_id_table_lookup(id_tbl, id, valp);}
int rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp) {return (int)mix_id_table_lookup((ID_TABLE_IMPL_TYPE *)tbl, id, valp);}

int rb_id_table_lookup (struct rb_id_table *tbl, ID id, VALUE *valp) {return (int)mix_id_table_lookup((struct mix_id_table *)tbl, id, valp);}

という感じになる。

rb_id_tableはすぐにキャストしてしまうため多分特に実体のない型だろう。キャスト先のstruct mix_id_tableが実際の実装になるため、

struct RClass {
    struct RBasic basic;
    VALUE super;
    rb_classext_t *ptr;
    struct mix_id_table *m_tbl;
};

struct mix_id_table {
    union {
    struct {
        int capa;
        int num;
    } size;
    struct list_id_table list;
    struct hash_id_table hash;
    } aux;
};

struct list_id_table {
    int capa;
    int num;
    id_key_t *keys;
#if ID_TABLE_USE_CALC_VALUES == 0
    VALUE *values_;
#endif
};

struct hash_id_table {
    int capa;
    int num;
    int used;
    item_t *items;
};

と思っておくのがよさそう。では、それを参照するmix_id_table_lookupはどうなっているか。

static int
mix_id_table_lookup(struct mix_id_table *tbl, ID id, VALUE *valp)
{
    if (LIST_P(tbl)) return list_id_table_lookup(&tbl->aux.list, id, valp);
    else             return hash_id_table_lookup(&tbl->aux.hash, id, valp);
}

#define LIST_P(mix)       ((mix)->aux.size.capa <= ID_TABLE_USE_MIX_LIST_MAX_CAPA)
#define ID_TABLE_USE_MIX_LIST_MAX_CAPA 64

要するにテーブルのサイズが64までの時はリスト探索し、それより大きい時はハッシュで探索するようだ。
もうちょっと深く見たいけど疲れたのでこれはこのへんで…

  • rb_callable_method_entry
    • method_entry_get
      • グローバルメソッドキャッシュにヒットした場合、それを使う
      • method_entry_get_without_cache
        • search_method: メソッドが見つかるまで親クラスを辿りながらメソッド探索を行なう
          • lookup_method_table: テーブルのサイズが64以下ならリスト探索、64より大きいならハッシュ探索
        • Rubyが実行中ならグローバルメソッドキャッシュのセットを行なう

メソッドキャッシュのキャッシュヒット時にどのように実行されるか

メソッドキャッシュがどのように取得され、どういう時に破棄されるかを見ていく。

グローバルメソッドキャッシュ

static rb_method_entry_t *
method_entry_get(VALUE klass, ID id, VALUE *defined_class_ptr)
{
#if OPT_GLOBAL_METHOD_CACHE
    struct cache_entry *ent;
    ent = GLOBAL_METHOD_CACHE(klass, id);
    if (ent->method_state == GET_GLOBAL_METHOD_STATE() &&
        ent->class_serial == RCLASS_SERIAL(klass) &&
        ent->mid == id) {
#if VM_DEBUG_VERIFY_METHOD_CACHE
        verify_method_cache(klass, id, ent->defined_class, ent->me);
#endif
        if (defined_class_ptr) *defined_class_ptr = ent->defined_class;
        return ent->me;
    }
#endif

    return method_entry_get_without_cache(klass, id, defined_class_ptr);
}

static struct {
    unsigned int size;
    unsigned int mask;
    struct cache_entry *entries;
} global_method_cache = {
    GLOBAL_METHOD_CACHE_SIZE,
    GLOBAL_METHOD_CACHE_MASK,
};

#define GLOBAL_METHOD_CACHE_SIZE 0x800
#define GLOBAL_METHOD_CACHE_MASK (GLOBAL_METHOD_CACHE_SIZE-1)

#define GLOBAL_METHOD_CACHE_KEY(c,m) ((((c)>>3)^(m))&(global_method_cache.mask))
#define GLOBAL_METHOD_CACHE(c,m) (global_method_cache.entries + GLOBAL_METHOD_CACHE_KEY(c,m))

static rb_method_entry_t *
method_entry_get_without_cache(VALUE klass, ID id,
                               VALUE *defined_class_ptr)
{
    VALUE defined_class;
    rb_method_entry_t *me = search_method(klass, id, &defined_class);

    if (ruby_running) {
        if (OPT_GLOBAL_METHOD_CACHE) {
            struct cache_entry *ent;
            ent = GLOBAL_METHOD_CACHE(klass, id);
            ent->class_serial = RCLASS_SERIAL(klass);
            ent->method_state = GET_GLOBAL_METHOD_STATE();
            ent->defined_class = defined_class;
            ent->mid = id;

            if (UNDEFINED_METHOD_ENTRY_P(me)) {
                me = ent->me = NULL;
            }
            else {
                ent->me = me;
            }
        }
        else if (UNDEFINED_METHOD_ENTRY_P(me)) {
            me = NULL;
        }
    }
    else if (UNDEFINED_METHOD_ENTRY_P(me)) {
        me = NULL;
    }

    if (defined_class_ptr)
        *defined_class_ptr = defined_class;
    return me;
}

GLOBAL_METHOD_CACHE_SIZEである0x800は10進数にすると2048だ。つまり2048個しかメソッドがグローバルキャッシュに登録できない。

これは2^11なので、2進数にすると0000100000000000であるから、そこから1を引いたGLOBAL_METHOD_CACHE_MASKは0000011111111111ということになる。

キャッシュエントリの取得の際、GLOBAL_METHOD_CACHE(klass, id)を行なうが、これは以下のように展開される。

GLOBAL_METHOD_CACHE(klass, id)
global_method_cache.entries + GLOBAL_METHOD_CACHE_KEY(klass, id)
global_method_cache.entries + ((((klass)>>3)^(id))&(global_method_cache.mask))

これは一体…
よくわからないので、どのようにキャッシュが生成されているのかを見てみる。

entriesというのはInit_Methodで初期化されている。

void
Init_Method(void)
{
#if OPT_GLOBAL_METHOD_CACHE
    char *ptr = getenv("RUBY_GLOBAL_METHOD_CACHE_SIZE");
    int val;

    if (ptr != NULL && (val = atoi(ptr)) > 0) {
        if ((val & (val - 1)) == 0) { /* ensure val is a power of 2 */
            global_method_cache.size = val;
            global_method_cache.mask = val - 1;
        }
        else {
           fprintf(stderr, "RUBY_GLOBAL_METHOD_CACHE_SIZE was set to %d but ignored because the value is not a power of 2.\n", val);
        }
    }

    global_method_cache.entries = (struct cache_entry *)calloc(global_method_cache.size, sizeof(struct cache_entry));
    if (global_method_cache.entries == NULL) {
        fprintf(stderr, "[FATAL] failed to allocate memory\n");
        exit(EXIT_FAILURE);
    }
#endif
}

キャッシュエントリの生成は以下のようになっている。

static rb_method_entry_t *
method_entry_get_without_cache(VALUE klass, ID id,
                               VALUE *defined_class_ptr)
{
    VALUE defined_class;
    rb_method_entry_t *me = search_method(klass, id, &defined_class);

    if (ruby_running) {
        if (OPT_GLOBAL_METHOD_CACHE) {
            struct cache_entry *ent;
            ent = GLOBAL_METHOD_CACHE(klass, id);
            ent->class_serial = RCLASS_SERIAL(klass);
            ent->method_state = GET_GLOBAL_METHOD_STATE();
            ent->defined_class = defined_class;
            ent->mid = id;

            if (UNDEFINED_METHOD_ENTRY_P(me)) {
                me = ent->me = NULL;
            }
            else {
                ent->me = me;
            }
        }
        else if (UNDEFINED_METHOD_ENTRY_P(me)) {
            me = NULL;
        }
    }
    else if (UNDEFINED_METHOD_ENTRY_P(me)) {
        me = NULL;
    }

    if (defined_class_ptr)
        *defined_class_ptr = defined_class;
    return me;
}

struct cache_entry {
    rb_serial_t method_state;
    rb_serial_t class_serial;
    ID mid;
    rb_method_entry_t* me;
    VALUE defined_class;
};

同じようにglobal_method_cache.entries + ((((klass)>>3)^(id))&(global_method_cache.mask))でstruct cache_entryを取ってきて、meに探索したメソッドをセットしているようだ。

なお、cacheを使うかどうかは以下のように判定されているため、

    if (ent->method_state == GET_GLOBAL_METHOD_STATE() &&
        ent->class_serial == RCLASS_SERIAL(klass) &&
        ent->mid == id) {

GET_GLOBAL_METHOD_STATEがキャッシュをセットした時から変わっていないかと、RCLASS_SERIAL(klass)が変わっていないかを見てcache invalidationを行なっている。

キャッシュキーには((klass)>>3)^(id))&(global_method_cache.mask)という値が使われている。klassはVALUE型であるからポインタなので、シフトしてるのはまあなんか下の方のビットが0で埋まってて余ってるのを削ることで空間効率を良くしているのだろう。

Rubyのオブジェクト構造体はmalloc()で確保されるので、 普通は4の倍数アドレスに配置される。
http://i.loveruby.net/ja/rhg/book/object.html

これだと2ビットしか余ってなさそうに見えるが、「言語のしくみ」とかだとtagged pointer法の説明で、「最下位2から3ビットが常にゼロである(ように多くのOSが実装されている)」と書いてある。

SIZEOF_VALUE >= SIZEOF_DOUBLEな時に#define USE_FLONUM 1になり、FloatもVALUEに埋め込まれた即値になるのだが、その判定に使われるRUBY_IMMEDIATE_MASKもこの環境だと0x07(下位3ビットが1)になっている。

Most architectures are byte-addressable (memory addresses are in bytes), but certain types of data will often be aligned to the size of the data, often a word or multiple thereof. This discrepancy leaves a few of the least significant bits of the pointer unused, which can be used for tags – most often as a bit field (each bit a separate tag) – as long as code that uses the pointer masks out these bits before accessing memory. E.g., on a 32-bit architecture (for both addresses and word size), a word is 32 bits = 4 bytes, so word-aligned addresses are always a multiple of 4, hence end in 00, leaving the last 2 bits available; while on a 64-bit architecture, a word is 64 bits word = 8 bytes, so word-aligned addresses end in 000, leaving the last 3 bits available.
https://en.wikipedia.org/wiki/Tagged_pointer

まあつまり64bit環境だと下位3ビットが0であり、それを削っているわけで、このキャッシュキーは64bit環境に最適化されているということになる。直してもいい気がするけど、32bit環境を持ってないのでベンチマークが取れない…

で、話を戻すと、このキャッシュキーはポインタをシフトした値とID(これはどうやって生成してるのか把握してない)を&した割といい加減な値(キャッシュキーは生成コストが低くないと意味がないので正しい)なので、まあまあ被りうることになる。なので、cache invalidationが必要になる。生成方法的に、同じクラス内では衝突しないため、同じクラスのメソッドを呼び続けている間は都合がいいキャッシュになっている。

キャッシュキーの生成方法的に、メソッドの再定義がなくても、呼び出しているうちに別のクラスのメソッドにキャッシュがすりかえられている可能性があるが、これはRCLASS_SERIAL(klass)があるため問題なさそう。

#define RCLASS_SERIAL(c) (RCLASS_EXT(c)->class_serial)
#define RCLASS_EXT(c) (RCLASS(c)->ptr)
#define RCLASS(obj)  (R_CAST(RClass)(obj))
#define R_CAST(st)   (struct st*)
struct RClass {
    struct RBasic basic;
    VALUE super;
    rb_classext_t *ptr;
    struct rb_id_table *m_tbl;
};

struct rb_classext_struct {
    struct st_table *iv_index_tbl;
    struct st_table *iv_tbl;
    struct rb_id_table *const_tbl;
    struct rb_id_table *callable_m_tbl;
    rb_subclass_entry_t *subclasses;
    rb_subclass_entry_t **parent_subclasses;
    /**
     * In the case that this is an `ICLASS`, `module_subclasses` points to the link
     * in the module's `subclasses` list that indicates that the klass has been
     * included. Hopefully that makes sense.
     */
    rb_subclass_entry_t **module_subclasses;
    rb_serial_t class_serial;
    const VALUE origin_;
    VALUE refined_class;
    rb_alloc_func_t allocator;
};
typedef struct rb_classext_struct rb_classext_t;

class_serialはどう作られているかというと、

static rb_serial_t ruby_vm_class_serial = 1;

rb_serial_t
rb_next_class_serial(void)
{
    return NEXT_CLASS_SERIAL();
}

#define NEXT_CLASS_SERIAL() (++ruby_vm_class_serial)

static VALUE
class_alloc(VALUE flags, VALUE klass)
{
    NEWOBJ_OF(obj, struct RClass, klass, (flags & T_MASK) | FL_PROMOTED1 /* start from age == 2 */ | (RGENGC_WB_PROTECTED_CLASS ? FL_WB_PROTECTED : 0));
    obj->ptr = ZALLOC(rb_classext_t);
    /* ZALLOC
      RCLASS_IV_TBL(obj) = 0;
      RCLASS_CONST_TBL(obj) = 0;
      RCLASS_M_TBL(obj) = 0;
      RCLASS_IV_INDEX_TBL(obj) = 0;
      RCLASS_SET_SUPER((VALUE)obj, 0);
      RCLASS_EXT(obj)->subclasses = NULL;
      RCLASS_EXT(obj)->parent_subclasses = NULL;
      RCLASS_EXT(obj)->module_subclasses = NULL;
     */
    RCLASS_SET_ORIGIN((VALUE)obj, (VALUE)obj);
    RCLASS_SERIAL(obj) = rb_next_class_serial();
    RCLASS_REFINED_CLASS(obj) = Qnil;
    RCLASS_EXT(obj)->allocator = 0;

    return (VALUE)obj;
}

static void
rb_class_clear_method_cache(VALUE klass, VALUE arg)
{
    RCLASS_SERIAL(klass) = rb_next_class_serial();
    // ...
}

まあこのへんである。クラスが作られる度にオートインクリメントされてセットされるので問題ない。

さて、同じクラス、同じメソッドIDのメソッドが再定義された場合のcache invalidationだが、class_serialが書き変わるか、GET_GLOBAL_METHOD_STATE()が変わっていれば良い。

とりあえず、GET_GLOBAL_METHOD_STATE()は以下のような定義になっている。

static rb_serial_t ruby_vm_global_method_state = 1;

#define GET_GLOBAL_METHOD_STATE() (ruby_vm_global_method_state)
#define INC_GLOBAL_METHOD_STATE() (++ruby_vm_global_method_state)

INC_GLOBAL_METHOD_STATEというのは一箇所でしか呼ばれない。

void
rb_clear_method_cache_by_class(VALUE klass)
{
    if (klass && klass != Qundef) {
        int global = klass == rb_cBasicObject || klass == rb_cObject || klass == rb_mKernel;

        RUBY_DTRACE_HOOK(METHOD_CACHE_CLEAR, (global ? "global" : rb_class2name(klass)));

        if (global) {
            INC_GLOBAL_METHOD_STATE();
        }
        else {
            rb_class_clear_method_cache(klass, Qnil);
        }
    }

    if (klass == rb_mKernel) {
        rb_subclass_entry_t *entry = RCLASS_EXT(klass)->subclasses;

        for (; entry != NULL; entry = entry->next) {
            struct rb_id_table *table = RCLASS_CALLABLE_M_TBL(entry->klass);
            if (table)rb_id_table_clear(table);
        }
    }
}

rb_clear_method_cache_by_class(klass)が呼ばれる時、klassがBasicObject, Object, Kernelの場合は全てのグローバルメソッドキャッシュが破棄される、ということになる。
klassがそれに該当しない場合、そのklassのclass_serialが新しいものに変わるので、そのクラスのメソッドのグローバルメソッドキャッシュが全て破棄されることになる。

じゃあrb_clear_method_cache_by_classがいつ呼ばれているかというと、全部追いかけるのは大変だが、例えばrefinementsのModule#usingを使うとrb_clear_method_cache_by_class(rb_cObject);が呼ばれるので全部破棄される。

で、rb_define_methodとかをやると、rb_add_method_cfunc、rb_add_method、rb_method_entry_makeを経由してrb_clear_method_cache_by_class(klass);が呼ばれる。
(この記事には関係ないが、rb_method_entry_makeで http://qiita.com/k0kubun/items/255b965637bfef9536cb で調査をサボったrb_vm_check_redefinition_opt_methodが呼ばれることに気付いた)

また、Rubyでメソッドを定義する時はFrozenCoreオブジェクトのcore#define_methodが呼ばれるわけだが、以下のような定義になっていて、

static VALUE
m_core_define_method(VALUE self, VALUE sym, VALUE iseqval)
{
    REWIND_CFP({
    vm_define_method(GET_THREAD(), Qnil, SYM2ID(sym), iseqval, FALSE);
    });
    return sym;
}

static void
vm_define_method(rb_thread_t *th, VALUE obj, ID id, VALUE iseqval, int is_singleton)
{
    VALUE klass;
    rb_method_visibility_t visi;
    rb_cref_t *cref = rb_vm_cref();

    if (!is_singleton) {
    klass = CREF_CLASS(cref);
    visi = rb_scope_visibility_get();
    }
    else { /* singleton */
    klass = rb_singleton_class(obj); /* class and frozen checked in this API */
    visi = METHOD_VISI_PUBLIC;
    }

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

    rb_add_method_iseq(klass, id, (const rb_iseq_t *)iseqval, cref, visi);

    if (!is_singleton && rb_scope_module_func_check()) {
    klass = rb_singleton_class(klass);
    rb_add_method_iseq(klass, id, (const rb_iseq_t *)iseqval, cref, METHOD_VISI_PUBLIC);
    }
}

void
rb_add_method_iseq(VALUE klass, ID mid, const rb_iseq_t *iseq, rb_cref_t *cref, rb_method_visibility_t visi)
{
    struct { /* should be same fields with rb_method_iseq_struct */
        const rb_iseq_t *iseqptr;
        rb_cref_t *cref;
    } iseq_body;

    iseq_body.iseqptr = iseq;
    iseq_body.cref = cref;
    rb_add_method(klass, mid, VM_METHOD_TYPE_ISEQ, &iseq_body, visi);
}

rb_add_methodをやっているのでklassのグローバルメソッドキャッシュが破棄されることがわかる。

インラインメソッドキャッシュ

以下の場所に戻る。

DEFINE_INSN
opt_send_without_block
(CALL_INFO ci, CALL_CACHE cc)
(...)
(VALUE val) // inc += -ci->orig_argc;
{
    struct rb_calling_info calling;
    calling.block_handler = VM_BLOCK_HANDLER_NONE;
    vm_search_method(ci, cc, calling.recv = TOPN(calling.argc = ci->orig_argc));
    CALL_METHOD(&calling, ci, cc);
}

static void
vm_search_method(const struct rb_call_info *ci, struct rb_call_cache *cc, VALUE recv)
{
    VALUE klass = CLASS_OF(recv);

#if OPT_INLINE_METHOD_CACHE
    if (LIKELY(GET_GLOBAL_METHOD_STATE() == cc->method_state && RCLASS_SERIAL(klass) == cc->class_serial)) {
        /* cache hit! */
        VM_ASSERT(cc->call != NULL);
        return;
    }
#endif

    cc->me = rb_callable_method_entry(klass, ci->mid);
    VM_ASSERT(callable_method_entry_p(cc->me));
    cc->call = vm_call_general;
#if OPT_INLINE_METHOD_CACHE
    cc->method_state = GET_GLOBAL_METHOD_STATE();
    cc->class_serial = RCLASS_SERIAL(klass);
#endif
}

グローバルメソッドキャッシュを読んだ後だとなんだか既視感のある判定だ。

rb_callable_method_entryは中でmethod_entry_getを呼び出すが、これがグローバルメソッドキャッシュを参照しているので、インラインメソッドキャッシュの方が優先的に使われることがわかる。
で、その結果をmeにつっこみ、またインラインメソッドキャッシュのcache invalidationのために必要なmethod_state, class_serialをsendおよびopt_send_without_block命令の第2オペランドになっているcall cacheにつっこむ。

インラインメソッドキャッシュでは、sendおよびopt_send_without_block命令1つごとにキャッシュが持てるので、ある行に同じクラスのオブジェクトが来続ける限りは、例えグローバルメソッドキャッシュが別クラスのキャッシュに上書きされても、インラインメソッドキャッシュの方は使えることがわかる。

GET_GLOBAL_METHOD_STATE()を参照するので、Object,Kernel,BasicObjectにメソッドを定義したりrefinementsを使った場合は全てのインラインメソッドキャッシュも破棄されてしまう。
一方、クラスにメソッドを追加した場合もインラインメソッドキャッシュはそのクラスに関しては全て破棄されることになる。

なおsend命令に関してもvm_search_methodが使われるので、どちらのキャッシュも全てのメソッド呼び出しに対して使われていることがわかる。

まとめ

Rubyで定義されたメソッド、C拡張で定義されたメソッド、コア内部で実装されたCのメソッドはそれぞれCRuby内部でどういったデータ構造で保管されているか

typedef enum {
    VM_METHOD_TYPE_ISEQ, // 多分Rubyで定義されたメソッドはこれ
    VM_METHOD_TYPE_CFUNC, // C拡張とコアは両方これだと思うけどちゃんと確認してない
    VM_METHOD_TYPE_ATTRSET,
    VM_METHOD_TYPE_IVAR,
    VM_METHOD_TYPE_BMETHOD,
    VM_METHOD_TYPE_ZSUPER,
    VM_METHOD_TYPE_ALIAS,
    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;

// Rubyで定義されたメソッドが入りそうな奴
typedef struct rb_method_iseq_struct {
    const rb_iseq_t * const iseqptr;              /* should be separated from iseqval */
    rb_cref_t * const cref;                       /* should be marked */
} rb_method_iseq_t; /* check rb_add_method_iseq() when modify the fields */

// C拡張で定義されたメソッド、コア内部で実装されたCのメソッドが入りそうな奴
typedef struct rb_method_cfunc_struct {
    VALUE (*func)(ANYARGS);
    VALUE (*invoker)(VALUE (*func)(ANYARGS), VALUE recv, int argc, const VALUE *argv); // argvを展開するだけの関数が
    int argc;
} rb_method_cfunc_t;

typedef struct rb_method_definition_struct {
    rb_method_type_t type :  8; /* method type */
    int alias_count       : 28;
    int complemented_count: 28;

    union {
        rb_method_iseq_t iseq; // Rubyで定義されたメソッドが入りそう
        rb_method_cfunc_t cfunc; // C拡張で定義されたメソッド、コア内部で実装されたCのメソッドが入りそう
        rb_method_attr_t attr;
        rb_method_alias_t alias;
        rb_method_refined_t refined;

        const VALUE proc;                 /* should be marked */
        enum method_optimized_type {
            OPTIMIZED_METHOD_TYPE_SEND,
            OPTIMIZED_METHOD_TYPE_CALL,

            OPTIMIZED_METHOD_TYPE__MAX
        } optimize_type;
    } body;

    ID original_id;
} rb_method_definition_t;

それらはそれぞれどのようなアルゴリズムで検索されるか

  • rb_callable_method_entry
    • method_entry_get
      • グローバルメソッドキャッシュにヒットした場合、それを使う
      • method_entry_get_without_cache
        • search_method: メソッドが見つかるまで親クラスを辿りながらメソッド探索を行なう
          • lookup_method_table: テーブルのサイズが64以下ならリスト探索、64より大きいならハッシュ探索
        • Rubyが実行中ならグローバルメソッドキャッシュのセットを行なう

それらはそれぞれどのような流れで実行されるか

  • rb_iseq_new_with_opt: AST→ISeqのコンパイルで呼び出される
    • rb_iseq_compile_node
      • iseq_compile_each
        • new_insn_send: send命令のINSN *が作られる。メソッドID、渡す引数の数、呼び方のフラグ、キーワード、ブロックなど、呼び出す側の情報が1つ目のオペランドにcall infoとして入る。2つ目はこの時点ではQfalse、3つ目にブロックが入る
    • iseq_setup
      • iseq_optimize
        • iseq_specialized_instruction: ブロックがない場合send→opt_send_without_blockへの変換が走り、3つ目のオペランドが削られる
      • iseq_set_sequence: send命令2つ目のオペランドのcall cacheが初期化される
  • vm_exec_core: ISeqの実行時に呼び出される
    • INSN_ENTRY(opt_send_without_block)
      • opt_send_without_block命令のオペランドから、1つ目をcall info, 2つ目をcall cacheとして取得
      • スタックから引数番目のオブジェクトをレシーバとし、実行時の呼び出し情報callingを作る
      • vm_search_method
        • call cacheのmeにrb_callable_method_entryの結果をセット、callにvm_call_generalをセットする
      • CALL_METHOD
        • vm_call_generalを使った呼び出し
          • コントロールフレームのpush
          • Rubyの場合はローカル変数の初期化
          • コントロールフレームのpop

メソッドキャッシュはどのように実装されており、どういう時使われるのか

グローバルメソッドキャッシュ

  • 2048個登録できる
  • ([クラスのアドレス]>>3)&[メソッドID]がキャッシュキー
    • なので、同じクラス同士ではキャッシュキーが被らない。逆に言うと、多くのクラスのメソッドを呼んでいたるとキャッシュが破棄される可能性が高い
    • クラスが定義されたり、そのクラスにメソッドが追加された時に更新されるclass_serialをcache invalidationに使っているので、別のクラスのメソッドキャッシュが来ても適切にinvalidateされる
  • あるクラスにメソッドを定義すると、そのクラスのグローバルメソッドキャッシュが全て飛ぶ
    • クラスにextend,includeをやった場合は、対象のモジュールがメソッドを持っていたらそのクラスのグローバルメソッドキャッシュは飛ぶ
    • Object,Kernel,BasicObjectにメソッドを生やした場合は全てのグローバルメソッドキャッシュが飛ぶ
    • refinementsを使っても全てのグローバルメソッドキャッシュが飛ぶ

インラインメソッドキャッシュ

  • キャッシュはYARVのsend, opt_send_without_block命令の第2オペランドに埋め込まれる
    • つまり、ソースコード中でメソッド呼び出しを行う場所の数だけキャッシュが作られる
    • 同じ行のレシーバにいろんなクラスのオブジェクトが来るとインラインキャッシュが使われにくくなる
  • あるクラスにメソッドを定義すると、そのクラスのインラインメソッドキャッシュも全て飛ぶ
    • クラスにextend,includeをやった場合は、対象のモジュールがメソッドを持っていたらそのクラスのインラインメソッドキャッシュが飛ぶ
    • Object,Kernel,BasicObjectにメソッドを生やした場合は全てのインラインメソッドキャッシュが飛ぶ
    • refinementsを使っても全てのインラインメソッドキャッシュが飛ぶ

バックトレースの管理などメソッド本体の処理以外には何が行なわれているのか

まずメソッドの探索を行う。
次に、複雑な引数を渡せるようにセットアップが必要になる(vm_callee_setup_arg)。

Rubyで定義されたメソッドを呼び出す場合、CALL_METHODの際にVM上にコントロールフレームが積まれ、そこでローカル変数の初期化を行った後、次の命令に進む。

Cで定義されたメソッドを呼び出す場合、コントロールフレームのpush,Cの関数の呼び出し,フレームのpopを行う。

send命令とopt_send_without_block命令とrb_funcallの間では何が異なるのか

ちゃんと読んでないけど、rb_funcallとop_send_without_blockの違いに関しては、rb_funcallは少なくともva_listの展開と、GET_THREAD、calling/call info/call cahceの作成を追加で行なう。インラインメソッドキャッシュは使えないが、グローバルメソッドキャッシュは使われる。

17
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
9