The Story of Method Lookup

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

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

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

[YARV instruction dispatch](http://qiita.com/k0kubun/items/dbb2f0979f19f76eed26)の内容を前提とするのでリンクしておく。

# 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 、

```c
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

```c
	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`は以下のようになっていて、

```c
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`はこういう感じで、

```c
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;
}
```

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

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

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

```c
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には引数の数が入る。フラグは多分この辺の値が入りそうに見える

```c
#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
/**
  @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内ではこうなっている。

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

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

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

```c
    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`は以下のようになっている

```c
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のコードではない)で呼び出される。

```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は何をするか
```c
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`となっているので、

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

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

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

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

```c
    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以降
気を取り直して続きを読んでいく。

```c
    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の構造体の定義はこうだ。

```c 
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`を呼び出す。

```c 
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になっている。

```c
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;
```

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

```c 
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のセット

```c
    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;
```

```c
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`の定義はこうなっている。

```c 
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 
/**
  @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は

```c 
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つ目で、

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

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

```c 
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`の処理は以下のようになっている。

```c 
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だと余計な処理が入るようだ。

```c 
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`が呼び出される

```c 
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`の定義を見返してみるとこうだ。

```c
#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()`が呼ばれるわけだが、これは上記の定義から展開すると以下のようになる。

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

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

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

#### VM_METHOD_TYPE_CFUNCの場合
`vm_call_cfunc`が呼び出される

```c 
#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`は、

```c 
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は以下のように関数がセットされる。

```c 
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`にグローバルメソッドキャッシュの実装がある。

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

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

```c 
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`は何をやっているか。

```c 
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しても全くひっかからない。とりあえず以下のあたりが関係がありそう。

```c 
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
```

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

```c 
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`が実際の実装になるため、

```c 
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`はどうなっているか。

```c
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が実行中ならグローバルメソッドキャッシュのセットを行なう

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

### グローバルメソッドキャッシュ
```c 
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`で初期化されている。

```c 
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
}
```

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

```c
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を使うかどうかは以下のように判定されているため、

```c 
    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)`があるため問題なさそう。

```c 
#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はどう作られているかというと、

```c 
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()`は以下のような定義になっている。

```c 
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`というのは一箇所でしか呼ばれない。

```c 
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`が呼ばれるわけだが、以下のような定義になっていて、

```c  
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のグローバルメソッドキャッシュが破棄されることがわかる。

### インラインメソッドキャッシュ
以下の場所に戻る。

```c
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内部でどういったデータ構造で保管されているか
```c 
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の作成を追加で行なう。インラインメソッドキャッシュは使えないが、グローバルメソッドキャッシュは使われる。