* class.c, compile.c, eval.c, gc.h, insns.def, internal.h, method.h,

  variable.c, vm.c, vm_core.c, vm_insnhelper.c, vm_insnhelper.h,
  vm_method.c: Implement class hierarchy method cache invalidation.

  [ruby-core:55053] [Feature #8426] [GH-387]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42822 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

14 files changed, 324 insertions, 89 deletions

diff --git a/ChangeLog b/ChangeLog
index 17bcd5a170..522749c7d6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+Wed Sep  4 14:08:00 2013  Charlie Somerville  <charliesome@ruby-lang.org>
+
+	* class.c, compile.c, eval.c, gc.h, insns.def, internal.h, method.h,
+	  variable.c, vm.c, vm_core.c, vm_insnhelper.c, vm_insnhelper.h,
+	  vm_method.c: Implement class hierarchy method cache invalidation.
+
+	  [ruby-core:55053] [Feature #8426] [GH-387]
+
 Wed Sep  4 11:13:40 2013  Nobuyoshi Nakada  <nobu@ruby-lang.org>
 
 	* string.c (str_gsub): use BEG(0) for whole matched position not
diff --git a/class.c b/class.c
index f87d2bdcca..c07a20438a 100644
--- a/class.c
+++ b/class.c
@@ -34,6 +34,109 @@
 extern st_table *rb_class_tbl;
 #define id_attached id__attached__
 
+void
+rb_class_subclass_add(VALUE super, VALUE klass)
+{
+    rb_subclass_entry_t *entry, *head;
+
+    if (super && super != Qundef) {
+	entry = malloc(sizeof(*entry));
+	entry->klass = klass;
+	entry->next = NULL;
+
+	head = RCLASS_EXT(super)->subclasses;
+	if (head) {
+	    entry->next = head;
+	    RCLASS_EXT(head->klass)->parent_subclasses = &entry->next;
+	}
+
+	RCLASS_EXT(super)->subclasses = entry;
+	RCLASS_EXT(klass)->parent_subclasses = &RCLASS_EXT(super)->subclasses;
+    }
+}
+
+static void
+rb_module_add_to_subclasses_list(VALUE module, VALUE iclass)
+{
+    rb_subclass_entry_t *entry, *head;
+
+    entry = malloc(sizeof(*entry));
+    entry->klass = iclass;
+    entry->next = NULL;
+
+    head = RCLASS_EXT(module)->subclasses;
+    if (head) {
+	entry->next = head;
+	RCLASS_EXT(head->klass)->module_subclasses = &entry->next;
+    }
+
+    RCLASS_EXT(module)->subclasses = entry;
+    RCLASS_EXT(iclass)->module_subclasses = &RCLASS_EXT(module)->subclasses;
+}
+
+void
+rb_class_remove_from_super_subclasses(VALUE klass)
+{
+    rb_subclass_entry_t *entry;
+
+    if (RCLASS_EXT(klass)->parent_subclasses) {
+	entry = *RCLASS_EXT(klass)->parent_subclasses;
+
+	*RCLASS_EXT(klass)->parent_subclasses = entry->next;
+	if (entry->next) {
+	    RCLASS_EXT(entry->next->klass)->parent_subclasses = RCLASS_EXT(klass)->parent_subclasses;
+	}
+	free(entry);
+    }
+
+    RCLASS_EXT(klass)->parent_subclasses = NULL;
+}
+
+void
+rb_class_remove_from_module_subclasses(VALUE klass)
+{
+    rb_subclass_entry_t *entry;
+
+    if (RCLASS_EXT(klass)->module_subclasses) {
+	entry = *RCLASS_EXT(klass)->module_subclasses;
+	*RCLASS_EXT(klass)->module_subclasses = entry->next;
+
+	if (entry->next) {
+	    RCLASS_EXT(entry->next->klass)->module_subclasses = RCLASS_EXT(klass)->module_subclasses;
+	}
+
+	free(entry);
+    }
+
+    RCLASS_EXT(klass)->module_subclasses = NULL;
+}
+
+void
+rb_class_foreach_subclass(VALUE klass, void(*f)(VALUE))
+{
+    rb_subclass_entry_t *cur = RCLASS_EXT(klass)->subclasses;
+
+    /* do not be tempted to simplify this loop into a for loop, the order of
+       operations is important here if `f` modifies the linked list */
+    while (cur) {
+	VALUE curklass = cur->klass;
+	cur = cur->next;
+	f(curklass);
+    }
+}
+
+void
+rb_class_detach_subclasses(VALUE klass)
+{
+    rb_class_foreach_subclass(klass, rb_class_remove_from_super_subclasses);
+}
+
+void
+rb_class_detach_module_subclasses(VALUE klass)
+{
+    rb_class_foreach_subclass(klass, rb_class_remove_from_module_subclasses);
+}
+
 /**
  * Allocates a struct RClass for a new class.
  *
@@ -57,6 +160,13 @@ class_alloc(VALUE flags, VALUE klass)
     RCLASS_SET_SUPER((VALUE)obj, 0);
     RCLASS_ORIGIN(obj) = (VALUE)obj;
     RCLASS_IV_INDEX_TBL(obj) = 0;
+
+    RCLASS_EXT(obj)->subclasses = NULL;
+    RCLASS_EXT(obj)->parent_subclasses = NULL;
+    RCLASS_EXT(obj)->module_subclasses = NULL;
+    RCLASS_EXT(obj)->seq = rb_next_class_sequence();
+    RCLASS_EXT(obj)->mc_tbl = NULL;
+
     RCLASS_REFINED_CLASS(obj) = Qnil;
     RCLASS_EXT(obj)->allocator = 0;
     return (VALUE)obj;
@@ -723,7 +833,6 @@ rb_include_module(VALUE klass, VALUE module)
     changed = include_modules_at(klass, RCLASS_ORIGIN(klass), module);
     if (changed < 0)
 	rb_raise(rb_eArgError, "cyclic include detected");
-    if (changed) rb_clear_cache();
 }
 
 static int
@@ -736,8 +845,8 @@ add_refined_method_entry_i(st_data_t key, st_data_t value, st_data_t data)
 static int
 include_modules_at(const VALUE klass, VALUE c, VALUE module)
 {
-    VALUE p;
-    int changed = 0;
+    VALUE p, iclass;
+    int method_changed = 0, constant_changed = 0;
     const st_table *const klass_m_tbl = RCLASS_M_TBL(RCLASS_ORIGIN(klass));
 
     while (module) {
@@ -763,7 +872,15 @@ include_modules_at(const VALUE klass, VALUE c, VALUE module)
 		break;
 	    }
 	}
-	c = RCLASS_SET_SUPER(c, rb_include_class_new(module, RCLASS_SUPER(c)));
+	iclass = rb_include_class_new(module, RCLASS_SUPER(c));
+	c = RCLASS_SET_SUPER(c, iclass);
+
+	if (BUILTIN_TYPE(module) == T_ICLASS) {
+	    rb_module_add_to_subclasses_list(RBASIC(module)->klass, iclass);
+	} else {
+	    rb_module_add_to_subclasses_list(module, iclass);
+	}
+
 	if (FL_TEST(klass, RMODULE_IS_REFINEMENT)) {
 	    VALUE refined_class =
 		rb_refinement_module_get_refined_class(klass);
@@ -773,14 +890,17 @@ include_modules_at(const VALUE klass, VALUE c, VALUE module)
 	    FL_SET(c, RMODULE_INCLUDED_INTO_REFINEMENT);
 	}
 	if (RMODULE_M_TBL(module) && RMODULE_M_TBL(module)->num_entries)
-	    changed = 1;
+	    method_changed = 1;
 	if (RMODULE_CONST_TBL(module) && RMODULE_CONST_TBL(module)->num_entries)
-	    changed = 1;
+	    constant_changed = 1;
       skip:
 	module = RCLASS_SUPER(module);
     }
 
-    return changed;
+    if (method_changed) rb_clear_cache_by_class(klass);
+    if (constant_changed) rb_clear_cache();
+
+    return method_changed;
 }
 
 static int
@@ -839,7 +959,6 @@ rb_prepend_module(VALUE klass, VALUE module)
     if (changed < 0)
 	rb_raise(rb_eArgError, "cyclic prepend detected");
     if (changed) {
-	rb_clear_cache();
 	rb_vm_check_redefinition_by_prepend(klass);
     }
 }
diff --git a/compile.c b/compile.c
index 92791f82a2..418ba5e6c4 100644
--- a/compile.c
+++ b/compile.c
@@ -962,6 +962,7 @@ new_callinfo(rb_iseq_t *iseq, ID mid, int argc, VALUE block, unsigned long flag)
 	}
     }
     ci->vmstat = 0;
+    ci->seq = 0;
     ci->blockptr = 0;
     ci->recv = Qundef;
     ci->call = 0; /* TODO: should set default function? */
diff --git a/eval.c b/eval.c
index 2b0838a180..7d4ce1a21d 100644
--- a/eval.c
+++ b/eval.c
@@ -1262,7 +1262,7 @@ mod_using(VALUE self, VALUE module)
     }
     Check_Type(module, T_MODULE);
     rb_using_module(cref, module);
-    rb_clear_cache();
+    rb_clear_cache_by_class(rb_cObject);
     return self;
 }
 
@@ -1398,7 +1398,7 @@ top_using(VALUE self, VALUE module)
     }
     Check_Type(module, T_MODULE);
     rb_using_module(cref, module);
-    rb_clear_cache();
+    rb_clear_cache_by_class(rb_cObject);
     return self;
 }
 
diff --git a/gc.c b/gc.c
index 0c8069ea40..8c7db09f7b 100644
--- a/gc.c
+++ b/gc.c
@@ -1122,6 +1122,20 @@ rb_free_m_table(st_table *tbl)
 }
 
 static int
+free_method_cache_entry_i(ID key, method_cache_entry_t *entry, st_data_t data)
+{
+    free(entry);
+    return ST_CONTINUE;
+}
+
+void
+rb_free_mc_table(st_table *tbl)
+{
+    st_foreach(tbl, free_method_cache_entry_i, 0);
+    st_free_table(tbl);
+}
+
+static int
 free_const_entry_i(ID key, rb_const_entry_t *ce, st_data_t data)
 {
     xfree(ce);
@@ -1226,7 +1240,6 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
 	break;
       case T_MODULE:
       case T_CLASS:
-	rb_clear_cache_by_class((VALUE)obj);
         if (RCLASS_M_TBL(obj)) {
             rb_free_m_table(RCLASS_M_TBL(obj));
         }
@@ -1239,7 +1252,23 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
 	if (RCLASS_IV_INDEX_TBL(obj)) {
 	    st_free_table(RCLASS_IV_INDEX_TBL(obj));
 	}
-        xfree(RANY(obj)->as.klass.ptr);
+	if (RCLASS_EXT(obj)->subclasses) {
+	    if (BUILTIN_TYPE(obj) == T_MODULE) {
+		rb_class_detach_module_subclasses(obj);
+	    } else {
+		rb_class_detach_subclasses(obj);
+	    }
+	    RCLASS_EXT(obj)->subclasses = NULL;
+	}
+	if (RCLASS_EXT(obj)->mc_tbl) {
+	    rb_free_mc_table(RCLASS_EXT(obj)->mc_tbl);
+	    RCLASS_EXT(obj)->mc_tbl = NULL;
+	}
+	rb_class_remove_from_module_subclasses(obj);
+	rb_class_remove_from_super_subclasses(obj);
+	if (RANY(obj)->as.klass.ptr)
+	    xfree(RANY(obj)->as.klass.ptr);
+	RANY(obj)->as.klass.ptr = NULL;
 	break;
       case T_STRING:
 	rb_str_free(obj);
@@ -1291,7 +1320,14 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
 	break;
       case T_ICLASS:
 	/* iClass shares table with the module */
+	if (RCLASS_EXT(obj)->subclasses) {
+	    rb_class_detach_subclasses(obj);
+	    RCLASS_EXT(obj)->subclasses = NULL;
+	}
+	rb_class_remove_from_module_subclasses(obj);
+	rb_class_remove_from_super_subclasses(obj);
 	xfree(RANY(obj)->as.klass.ptr);
+	RANY(obj)->as.klass.ptr = NULL;
 	break;
 
       case T_FLOAT:
diff --git a/insns.def b/insns.def
index 20ba34f067..53e22223cd 100644
--- a/insns.def
+++ b/insns.def
@@ -218,7 +218,7 @@ setconstant
 {
     vm_check_if_namespace(cbase);
     rb_const_set(cbase, id, val);
-    INC_VM_STATE_VERSION();
+    rb_clear_cache_by_class(cbase);
 }
 
 /**
@@ -975,7 +975,7 @@ defineclass
 		  class_iseq->local_size, 0, class_iseq->stack_max);
     RESTORE_REGS();
 
-    INC_VM_STATE_VERSION();
+    rb_clear_cache_by_class(klass);
     NEXT_INSN();
 }
 
diff --git a/internal.h b/internal.h
index 51ce4f0943..267ae5d9db 100644
--- a/internal.h
+++ b/internal.h
@@ -236,15 +236,53 @@ struct rb_deprecated_classext_struct {
     char conflict[sizeof(VALUE) * 3];
 };
 
+struct rb_subclass_entry;
+typedef struct rb_subclass_entry rb_subclass_entry_t;
+
+struct rb_subclass_entry {
+    VALUE klass;
+    rb_subclass_entry_t *next;
+};
+
+#if HAVE_UINT64_T
+    typedef uint64_t vm_state_version_t;
+#else
+    typedef unsigned long long vm_state_version_t;
+#endif
+
+struct rb_method_entry_struct;
+
+typedef struct method_cache_entry {
+    vm_state_version_t vm_state;
+    vm_state_version_t seq;
+    ID mid;
+    VALUE defined_class;
+    struct rb_method_entry_struct *me;
+} method_cache_entry_t;
+
 struct rb_classext_struct {
     VALUE super;
     struct st_table *iv_tbl;
     struct st_table *const_tbl;
+    struct st_table *mc_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;
+    vm_state_version_t seq;
     VALUE origin;
     VALUE refined_class;
     rb_alloc_func_t allocator;
 };
 
+/* class.c */
+void rb_class_subclass_add(VALUE super, VALUE klass);
+void rb_class_remove_from_super_subclasses(VALUE);
+
 #define RCLASS_EXT(c) (RCLASS(c)->ptr)
 #define RCLASS_IV_TBL(c) (RCLASS_EXT(c)->iv_tbl)
 #define RCLASS_CONST_TBL(c) (RCLASS_EXT(c)->const_tbl)
@@ -263,6 +301,10 @@ RCLASS_SUPER(VALUE klass)
 static inline VALUE
 RCLASS_SET_SUPER(VALUE klass, VALUE super)
 {
+    if (super) {
+	rb_class_remove_from_super_subclasses(klass);
+	rb_class_subclass_add(super, klass);
+    }
     OBJ_WRITE(klass, &RCLASS_EXT(klass)->super, super);
     return super;
 }
@@ -282,6 +324,10 @@ VALUE rb_integer_float_cmp(VALUE x, VALUE y);
 VALUE rb_integer_float_eq(VALUE x, VALUE y);
 
 /* class.c */
+void rb_class_foreach_subclass(VALUE klass, void(*f)(VALUE));
+void rb_class_detach_subclasses(VALUE);
+void rb_class_detach_module_subclasses(VALUE);
+void rb_class_remove_from_module_subclasses(VALUE);
 VALUE rb_obj_methods(int argc, VALUE *argv, VALUE obj);
 VALUE rb_obj_protected_methods(int argc, VALUE *argv, VALUE obj);
 VALUE rb_obj_private_methods(int argc, VALUE *argv, VALUE obj);
@@ -588,6 +634,9 @@ void ruby_kill(rb_pid_t pid, int sig);
 /* thread_pthread.c, thread_win32.c */
 void Init_native_thread(void);
 
+/* vm_insnhelper.h */
+vm_state_version_t rb_next_class_sequence();
+
 /* vm.c */
 VALUE rb_obj_is_thread(VALUE obj);
 void rb_vm_mark(void *ptr);
diff --git a/method.h b/method.h
index f02925ee1d..60b72e2f87 100644
--- a/method.h
+++ b/method.h
@@ -11,6 +11,8 @@
 #ifndef METHOD_H
 #define METHOD_H
 
+#include "internal.h"
+
 #ifndef END_OF_ENUMERATION
 # ifdef __GNUC__
 #   define END_OF_ENUMERATION(key)
@@ -120,7 +122,7 @@ rb_method_entry_t *rb_method_entry_with_refinements(VALUE klass, ID id,
 rb_method_entry_t *rb_method_entry_without_refinements(VALUE klass, ID id,
 						       VALUE *defined_class_ptr);
 
-rb_method_entry_t *rb_method_entry_get_without_cache(VALUE klass, ID id, VALUE *define_class_ptr);
+rb_method_entry_t *rb_method_entry_get_without_cache(VALUE klass, ID id, VALUE *define_class_ptr, method_cache_entry_t *ent);
 rb_method_entry_t *rb_method_entry_set(VALUE klass, ID mid, const rb_method_entry_t *, rb_method_flag_t noex);
 
 int rb_method_entry_arity(const rb_method_entry_t *me);
diff --git a/variable.c b/variable.c
index af1d23a86b..b3d9b3f6e8 100644
--- a/variable.c
+++ b/variable.c
@@ -1939,7 +1939,7 @@ rb_const_remove(VALUE mod, ID id)
 		      rb_class_name(mod), QUOTE_ID(id));
     }
 
-    rb_vm_change_state();
+    rb_clear_cache();
 
     val = ((rb_const_entry_t*)v)->value;
     if (val == Qundef) {
@@ -2149,7 +2149,8 @@ rb_const_set(VALUE klass, ID id, VALUE val)
 		load = autoload_data(klass, id);
 		/* for autoloading thread, keep the defined value to autoloading storage */
 		if (load && (ele = check_autoload_data(load)) && (ele->thread == rb_thread_current())) {
-		    rb_vm_change_state();
+		    rb_clear_cache();
+
 		    ele->value = val; /* autoload_i is shady */
 		    return;
 		}
@@ -2172,7 +2173,8 @@ rb_const_set(VALUE klass, ID id, VALUE val)
 	}
     }
 
-    rb_vm_change_state();
+    rb_clear_cache();
+
 
     ce = ALLOC(rb_const_entry_t);
     MEMZERO(ce, rb_const_entry_t, 1);
@@ -2217,8 +2219,10 @@ set_const_visibility(VALUE mod, int argc, VALUE *argv, rb_const_flag_t flag)
 	VALUE val = argv[i];
 	id = rb_check_id(&val);
 	if (!id) {
-	    if (i > 0)
-		rb_clear_cache_by_class(mod);
+	    if (i > 0) {
+		rb_clear_cache();
+	    }
+
 	    rb_name_error_str(val, "constant %"PRIsVALUE"::%"PRIsVALUE" not defined",
 			      rb_class_name(mod), QUOTE(val));
 	}
@@ -2227,13 +2231,14 @@ set_const_visibility(VALUE mod, int argc, VALUE *argv, rb_const_flag_t flag)
 	    ((rb_const_entry_t*)v)->flag = flag;
 	}
 	else {
-	    if (i > 0)
-		rb_clear_cache_by_class(mod);
+	    if (i > 0) {
+		rb_clear_cache();
+	    }
 	    rb_name_error(id, "constant %"PRIsVALUE"::%"PRIsVALUE" not defined",
 			  rb_class_name(mod), QUOTE_ID(id));
 	}
     }
-    rb_clear_cache_by_class(mod);
+    rb_clear_cache();
 }
 
 /*
diff --git a/vm.c b/vm.c
index 9b7eaad09c..41e9542bde 100644
--- a/vm.c
+++ b/vm.c
@@ -71,6 +71,9 @@ static VALUE
 vm_invoke_proc(rb_thread_t *th, rb_proc_t *proc, VALUE self, VALUE defined_class,
 	       int argc, const VALUE *argv, const rb_block_t *blockptr);
 
+static vm_state_version_t ruby_vm_global_state_version = 1;
+static vm_state_version_t ruby_vm_sequence = 1;
+
 #include "vm_insnhelper.h"
 #include "vm_insnhelper.c"
 #include "vm_exec.h"
@@ -84,6 +87,12 @@ vm_invoke_proc(rb_thread_t *th, rb_proc_t *proc, VALUE self, VALUE defined_class
 #define BUFSIZE 0x100
 #define PROCDEBUG 0
 
+vm_state_version_t
+rb_next_class_sequence()
+{
+    return NEXT_CLASS_SEQUENCE();
+}
+
 VALUE rb_cRubyVM;
 VALUE rb_cThread;
 VALUE rb_cEnv;
@@ -97,14 +106,6 @@ rb_event_flag_t ruby_vm_event_flags;
 
 static void thread_free(void *ptr);
 
-void
-rb_vm_change_state(void)
-{
-    INC_VM_STATE_VERSION();
-}
-
-static void vm_clear_global_method_cache(void);
-
 static void
 vm_clear_all_inline_method_cache(void)
 {
@@ -117,7 +118,6 @@ vm_clear_all_inline_method_cache(void)
 static void
 vm_clear_all_cache()
 {
-    vm_clear_global_method_cache();
     vm_clear_all_inline_method_cache();
     ruby_vm_global_state_version = 1;
 }
@@ -2069,11 +2069,13 @@ vm_define_method(rb_thread_t *th, VALUE obj, ID id, VALUE iseqval,
     OBJ_WRITE(miseq->self, &miseq->klass, klass);
     miseq->defined_method_id = id;
     rb_add_method(klass, id, VM_METHOD_TYPE_ISEQ, miseq, noex);
+    rb_clear_cache_by_class(klass);
 
     if (!is_singleton && noex == NOEX_MODFUNC) {
-	rb_add_method(rb_singleton_class(klass), id, VM_METHOD_TYPE_ISEQ, miseq, NOEX_PUBLIC);
+	klass = rb_singleton_class(klass);
+	rb_add_method(klass, id, VM_METHOD_TYPE_ISEQ, miseq, NOEX_PUBLIC);
+	rb_clear_cache_by_class(klass);
     }
-    INC_VM_STATE_VERSION();
 }
 
 #define REWIND_CFP(expr) do { \
@@ -2122,7 +2124,8 @@ m_core_undef_method(VALUE self, VALUE cbase, VALUE sym)
 {
     REWIND_CFP({
 	rb_undef(cbase, SYM2ID(sym));
-	INC_VM_STATE_VERSION();
+	rb_clear_cache_by_class(cbase);
+	rb_clear_cache_by_class(self);
     });
     return Qnil;
 }
diff --git a/vm_core.h b/vm_core.h
index fd0fa0bf3b..4e46479940 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -127,7 +127,8 @@ typedef struct rb_compile_option_struct rb_compile_option_t;
 
 
 struct iseq_inline_cache_entry {
-    VALUE ic_vmstat;
+    vm_state_version_t ic_vmstat;
+    vm_state_version_t ic_seq;
     VALUE ic_class;
     union {
 	size_t index;
@@ -157,7 +158,8 @@ typedef struct rb_call_info_struct {
     rb_iseq_t *blockiseq;
 
     /* inline cache: keys */
-    VALUE vmstat;
+    vm_state_version_t vmstat;
+    vm_state_version_t seq;
     VALUE klass;
 
     /* inline cache: values */
diff --git a/vm_insnhelper.c b/vm_insnhelper.c
index fa7791e38a..a6166596b6 100644
--- a/vm_insnhelper.c
+++ b/vm_insnhelper.c
@@ -848,16 +848,18 @@ vm_search_method(rb_call_info_t *ci, VALUE recv)
     VALUE klass = CLASS_OF(recv);
 
 #if OPT_INLINE_METHOD_CACHE
-    if (LIKELY(GET_VM_STATE_VERSION() == ci->vmstat && klass == ci->klass)) {
+    if (LIKELY(GET_VM_STATE_VERSION() == ci->vmstat && RCLASS_EXT(klass)->seq == ci->seq && klass == ci->klass)) {
 	/* cache hit! */
 	return;
     }
 #endif
+
     ci->me = rb_method_entry(klass, ci->mid, &ci->defined_class);
-    ci->call = vm_call_general;
     ci->klass = klass;
+    ci->call = vm_call_general;
 #if OPT_INLINE_METHOD_CACHE
     ci->vmstat = GET_VM_STATE_VERSION();
+    ci->seq = RCLASS_EXT(klass)->seq;
 #endif
 }
 
diff --git a/vm_insnhelper.h b/vm_insnhelper.h
index a25bd1609f..220404cfb5 100644
--- a/vm_insnhelper.h
+++ b/vm_insnhelper.h
@@ -257,8 +257,7 @@ enum vm_regan_acttype {
     CALL_METHOD(ci); \
 } while (0)
 
-static VALUE ruby_vm_global_state_version = 1;
-
+#define NEXT_CLASS_SEQUENCE() (++ruby_vm_sequence)
 #define GET_VM_STATE_VERSION() (ruby_vm_global_state_version)
 #define INC_VM_STATE_VERSION() do { \
     ruby_vm_global_state_version = (ruby_vm_global_state_version + 1); \
diff --git a/vm_method.c b/vm_method.c
index a026699acb..b8b3b579aa 100644
--- a/vm_method.c
+++ b/vm_method.c
@@ -2,9 +2,7 @@
  * This file is included by vm.c
  */
 
-#define CACHE_SIZE 0x800
-#define CACHE_MASK 0x7ff
-#define EXPR1(c,m) ((((c)>>3)^(m))&CACHE_MASK)
+#include "method.h"
 
 #define NOEX_NOREDEF 0
 #ifndef NOEX_NOREDEF
@@ -22,53 +20,32 @@ static void rb_vm_check_redefinition_opt_method(const rb_method_entry_t *me, VAL
 #define singleton_undefined idSingleton_method_undefined
 #define attached            id__attached__
 
-struct cache_entry {		/* method hash table. */
-    VALUE filled_version;        /* filled state version */
-    ID mid;			/* method's id */
-    VALUE klass;		/* receiver's class */
-    rb_method_entry_t *me;
-    VALUE defined_class;
-};
-
-static struct cache_entry cache[CACHE_SIZE];
 #define ruby_running (GET_VM()->running)
 /* int ruby_running = 0; */
 
 static void
-vm_clear_global_method_cache(void)
+rb_class_clear_method_cache(VALUE klass)
 {
-    struct cache_entry *ent, *end;
-
-    ent = cache;
-    end = ent + CACHE_SIZE;
-    while (ent < end) {
-	ent->filled_version = 0;
-	ent++;
-    }
+    RCLASS_EXT(klass)->seq = rb_next_class_sequence();
+    rb_class_foreach_subclass(klass, rb_class_clear_method_cache);
 }
 
 void
 rb_clear_cache(void)
 {
-    rb_vm_change_state();
-}
-
-static void
-rb_clear_cache_for_undef(VALUE klass, ID id)
-{
-    rb_vm_change_state();
-}
-
-static void
-rb_clear_cache_by_id(ID id)
-{
-    rb_vm_change_state();
+    INC_VM_STATE_VERSION();
 }
 
 void
 rb_clear_cache_by_class(VALUE klass)
 {
-    rb_vm_change_state();
+    if (klass && klass != Qundef) {
+	if (klass == rb_cBasicObject || klass == rb_cObject || klass == rb_mKernel) {
+	    INC_VM_STATE_VERSION();
+	} else {
+	    rb_class_clear_method_cache(klass);
+	}
+    }
 }
 
 VALUE
@@ -310,7 +287,7 @@ rb_method_entry_make(VALUE klass, ID mid, rb_method_type_t type,
 
     me = ALLOC(rb_method_entry_t);
 
-    rb_clear_cache_by_id(mid);
+    rb_clear_cache_by_class(klass);
 
     me->flag = NOEX_WITH_SAFE(noex);
     me->mark = 0;
@@ -472,6 +449,7 @@ rb_add_method(VALUE klass, ID mid, rb_method_type_t type, void *opts, rb_method_
     if (type != VM_METHOD_TYPE_UNDEF && type != VM_METHOD_TYPE_REFINED) {
 	method_added(klass, mid);
     }
+    rb_clear_cache_by_class(klass);
     return me;
 }
 
@@ -540,26 +518,26 @@ rb_method_entry_at(VALUE klass, ID id)
  */
 rb_method_entry_t *
 rb_method_entry_get_without_cache(VALUE klass, ID id,
-				  VALUE *defined_class_ptr)
+				  VALUE *defined_class_ptr,
+				  method_cache_entry_t *ent)
 {
     VALUE defined_class;
     rb_method_entry_t *me = search_method(klass, id, &defined_class);
 
     if (ruby_running) {
-	struct cache_entry *ent;
-	ent = cache + EXPR1(klass, id);
-	ent->filled_version = GET_VM_STATE_VERSION();
-	ent->klass = klass;
-	ent->defined_class = defined_class;
+	ent->seq = RCLASS_EXT(klass)->seq;
+	ent->vm_state = GET_VM_STATE_VERSION();
 
 	if (UNDEFINED_METHOD_ENTRY_P(me)) {
 	    ent->mid = id;
 	    ent->me = 0;
+	    ent->defined_class = defined_class;
 	    me = 0;
 	}
 	else {
 	    ent->mid = id;
 	    ent->me = me;
+	    ent->defined_class = defined_class;
 	}
     }
 
@@ -568,22 +546,52 @@ rb_method_entry_get_without_cache(VALUE klass, ID id,
     return me;
 }
 
+#if VM_DEBUG_VERIFY_METHOD_CACHE
+static void
+verify_method_cache(VALUE klass, ID id, VALUE defined_class, rb_method_entry_t *me)
+{
+    VALUE actual_defined_class;
+    method_cache_entry_t ent;
+    rb_method_entry_t *actual_me =
+	rb_method_entry_get_without_cache(klass, id, &actual_defined_class, &ent);
+
+    if (me != actual_me || defined_class != actual_defined_class) {
+	rb_bug("method cache verification failed");
+    }
+}
+#endif
+
 rb_method_entry_t *
 rb_method_entry(VALUE klass, ID id, VALUE *defined_class_ptr)
 {
 #if OPT_GLOBAL_METHOD_CACHE
-    struct cache_entry *ent;
+    method_cache_entry_t *ent;
+
+    if (RCLASS_EXT(klass)->mc_tbl == NULL) {
+	RCLASS_EXT(klass)->mc_tbl = st_init_numtable();
+    }
 
-    ent = cache + EXPR1(klass, id);
-    if (ent->filled_version == GET_VM_STATE_VERSION() &&
-	ent->mid == id && ent->klass == klass) {
+    if (!st_lookup(RCLASS_EXT(klass)->mc_tbl, (st_index_t)id, (st_data_t *)&ent)) {
+	ent = calloc(1, sizeof(*ent));
+	st_insert(RCLASS_EXT(klass)->mc_tbl, (st_index_t)id, (st_data_t)ent);
+    }
+
+    if (ent->seq == RCLASS_EXT(klass)->seq &&
+	ent->vm_state == GET_VM_STATE_VERSION() &&
+	ent->mid == id) {
 	if (defined_class_ptr)
 	    *defined_class_ptr = ent->defined_class;
+#if VM_DEBUG_VERIFY_METHOD_CACHE
+	verify_method_cache(klass, id, ent->defined_class, ent->me);
+#endif
 	return ent->me;
     }
+#else
+    method_cache_entry_t ent_;
+    method_cache_entry_t* ent = &ent_;
 #endif
 
-    return rb_method_entry_get_without_cache(klass, id, defined_class_ptr);
+    return rb_method_entry_get_without_cache(klass, id, defined_class_ptr, ent);
 }
 
 static rb_method_entry_t *
@@ -687,7 +695,7 @@ remove_method(VALUE klass, ID mid)
     st_delete(RCLASS_M_TBL(klass), &key, &data);
 
     rb_vm_check_redefinition_opt_method(me, klass);
-    rb_clear_cache_for_undef(klass, mid);
+    rb_clear_cache_by_class(klass);
     rb_unlink_method_entry(me);
 
     CALL_METHOD_HOOK(self, removed, mid);
@@ -1220,6 +1228,7 @@ rb_alias(VALUE klass, ID name, ID def)
 
     if (flag == NOEX_UNDEF) flag = orig_me->flag;
     rb_method_entry_set(target_klass, name, orig_me, flag);
+    rb_clear_cache_by_class(target_klass);
 }
 
 /*