Skip to content

Commit 547f111

Browse files
byrootbyroot
committed
Refactor vm_lookup_cc to allow lock-free lookups in RClass.cc_tbl
In multi-ractor mode, the `cc_tbl` mutations use the RCU pattern, which allow lock-less reads. Based on the assumption that invalidations and misses should be increasingly rare as the process ages, locking on modification isn't a big concern.
1 parent f2a7e48 commit 547f111

File tree

6 files changed

+227
-103
lines changed

6 files changed

+227
-103
lines changed

‎bootstraptest/test_ractor.rb

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2315,3 +2315,33 @@ def Warning.warn(msg)
23152315
raise unless $msg.all?{/Ractor#take/ =~ it}
23162316
$msg.size
23172317
}
2318+
2319+
# Cause lots of inline CC misses.
2320+
assert_equal 'ok', <<~'RUBY'
2321+
class A; def test; 1 + 1; end; end
2322+
class B; def test; 1 + 1; end; end
2323+
class C; def test; 1 + 1; end; end
2324+
class D; def test; 1 + 1; end; end
2325+
class E; def test; 1 + 1; end; end
2326+
class F; def test; 1 + 1; end; end
2327+
class G; def test; 1 + 1; end; end
2328+
2329+
objs = [A.new, B.new, C.new, D.new, E.new, F.new, G.new].freeze
2330+
2331+
def call_test(obj)
2332+
obj.test
2333+
end
2334+
2335+
ractors = 7.times.map do
2336+
Ractor.new(objs) do |objs|
2337+
objs = objs.shuffle
2338+
100_000.times do
2339+
objs.each do |o|
2340+
call_test(o)
2341+
end
2342+
end
2343+
end
2344+
end
2345+
ractors.each(&:join)
2346+
:ok
2347+
RUBY

‎id_table.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -395,7 +395,7 @@ VALUE
395395
rb_managed_id_table_dup(VALUE old_table)
396396
{
397397
struct rb_id_table *new_tbl;
398-
VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, &rb_managed_id_table_type, new_tbl);
398+
VALUE obj = TypedData_Make_Struct(0, struct rb_id_table, RTYPEDDATA_TYPE(old_table), new_tbl);
399399
struct rb_id_table *old_tbl = managed_id_table_ptr(old_table);
400400
rb_id_table_init(new_tbl, old_tbl->num + 1);
401401
rb_id_table_foreach(old_tbl, managed_id_table_dup_i, new_tbl);

‎imemo.c

Lines changed: 0 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -515,41 +515,6 @@ rb_free_const_table(struct rb_id_table *tbl)
515515
rb_id_table_free(tbl);
516516
}
517517

518-
// alive: if false, target pointers can be freed already.
519-
static void
520-
vm_ccs_free(struct rb_class_cc_entries *ccs, int alive, VALUE klass)
521-
{
522-
if (ccs->entries) {
523-
for (int i=0; i<ccs->len; i++) {
524-
const struct rb_callcache *cc = ccs->entries[i].cc;
525-
if (!alive) {
526-
// ccs can be free'ed.
527-
if (rb_gc_pointer_to_heap_p((VALUE)cc) &&
528-
!rb_objspace_garbage_object_p((VALUE)cc) &&
529-
IMEMO_TYPE_P(cc, imemo_callcache) &&
530-
cc->klass == klass) {
531-
// OK. maybe target cc.
532-
}
533-
else {
534-
continue;
535-
}
536-
}
537-
538-
VM_ASSERT(!vm_cc_super_p(cc) && !vm_cc_refinement_p(cc));
539-
vm_cc_invalidate(cc);
540-
}
541-
ruby_xfree(ccs->entries);
542-
}
543-
ruby_xfree(ccs);
544-
}
545-
546-
void
547-
rb_vm_ccs_free(struct rb_class_cc_entries *ccs)
548-
{
549-
RB_DEBUG_COUNTER_INC(ccs_free);
550-
vm_ccs_free(ccs, true, Qundef);
551-
}
552-
553518
static inline void
554519
imemo_fields_free(struct rb_fields *fields)
555520
{

‎vm_callinfo.h

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -330,6 +330,8 @@ cc_check_class(VALUE klass)
330330
}
331331

332332
VALUE rb_vm_cc_table_create(size_t capa);
333+
VALUE rb_vm_cc_table_dup(VALUE old_table);
334+
void rb_vm_cc_table_delete(VALUE table, ID mid);
333335

334336
static inline const struct rb_callcache *
335337
vm_cc_new(VALUE klass,
@@ -600,11 +602,14 @@ vm_ccs_p(const struct rb_class_cc_entries *ccs)
600602
static inline bool
601603
vm_cc_check_cme(const struct rb_callcache *cc, const rb_callable_method_entry_t *cme)
602604
{
603-
if (vm_cc_cme(cc) == cme ||
604-
(cme->def->iseq_overload && vm_cc_cme(cc) == rb_vm_lookup_overloaded_cme(cme))) {
605+
bool valid;
606+
RB_VM_LOCKING() {
607+
valid = vm_cc_cme(cc) == cme ||
608+
(cme->def->iseq_overload && vm_cc_cme(cc) == rb_vm_lookup_overloaded_cme(cme));
609+
}
610+
if (valid) {
605611
return true;
606612
}
607-
else {
608613
#if 1
609614
// debug print
610615

@@ -616,13 +621,9 @@ vm_cc_check_cme(const struct rb_callcache *cc, const rb_callable_method_entry_t
616621
rp(vm_cc_cme(cc));
617622
rp(rb_vm_lookup_overloaded_cme(cme));
618623
#endif
619-
return false;
620-
}
624+
return false;
621625
}
622626

623627
#endif
624628

625-
// gc.c
626-
void rb_vm_ccs_free(struct rb_class_cc_entries *ccs);
627-
628629
#endif /* RUBY_VM_CALLINFO_H */

‎vm_insnhelper.c

Lines changed: 127 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -2060,58 +2060,49 @@ vm_ccs_verify(struct rb_class_cc_entries *ccs, ID mid, VALUE klass)
20602060

20612061
const rb_callable_method_entry_t *rb_check_overloaded_cme(const rb_callable_method_entry_t *cme, const struct rb_callinfo * const ci);
20622062

2063-
static const struct rb_callcache *
2064-
vm_search_cc(const VALUE klass, const struct rb_callinfo * const ci)
2063+
static void
2064+
vm_evict_cc(VALUE klass, VALUE cc_tbl, ID mid)
20652065
{
2066-
const ID mid = vm_ci_mid(ci);
2067-
VALUE cc_tbl = RCLASS_WRITABLE_CC_TBL(klass);
2068-
struct rb_class_cc_entries *ccs = NULL;
2069-
VALUE ccs_data;
2066+
ASSERT_vm_locking();
20702067

2071-
if (cc_tbl) {
2072-
// CCS data is keyed on method id, so we don't need the method id
2073-
// for doing comparisons in the `for` loop below.
2074-
if (rb_managed_id_table_lookup(cc_tbl, mid, &ccs_data)) {
2075-
ccs = (struct rb_class_cc_entries *)ccs_data;
2076-
const int ccs_len = ccs->len;
2077-
2078-
if (UNLIKELY(METHOD_ENTRY_INVALIDATED(ccs->cme))) {
2079-
rb_managed_id_table_delete(cc_tbl, mid);
2080-
rb_vm_ccs_free(ccs);
2081-
ccs = NULL;
2082-
}
2083-
else {
2084-
VM_ASSERT(vm_ccs_verify(ccs, mid, klass));
2068+
if (rb_multi_ractor_p()) {
2069+
if (RCLASS_WRITABLE_CC_TBL(klass) != cc_tbl) {
2070+
// Another ractor updated the CC table while we were waiting on the VM lock.
2071+
// We have to retry.
2072+
return;
2073+
}
20852074

2086-
// We already know the method id is correct because we had
2087-
// to look up the ccs_data by method id. All we need to
2088-
// compare is argc and flag
2089-
unsigned int argc = vm_ci_argc(ci);
2090-
unsigned int flag = vm_ci_flag(ci);
2075+
struct rb_class_cc_entries *ccs = NULL;
2076+
rb_managed_id_table_lookup(cc_tbl, mid, (VALUE *)&ccs);
20912077

2092-
for (int i=0; i<ccs_len; i++) {
2093-
unsigned int ccs_ci_argc = ccs->entries[i].argc;
2094-
unsigned int ccs_ci_flag = ccs->entries[i].flag;
2095-
const struct rb_callcache *ccs_cc = ccs->entries[i].cc;
2078+
if (!ccs || !METHOD_ENTRY_INVALIDATED(ccs->cme)) {
2079+
// Another ractor replaced that entry while we were waiting on the VM lock.
2080+
return;
2081+
}
20962082

2097-
VM_ASSERT(IMEMO_TYPE_P(ccs_cc, imemo_callcache));
2083+
VALUE new_table = rb_vm_cc_table_dup(cc_tbl);
2084+
rb_vm_cc_table_delete(new_table, mid);
2085+
RB_OBJ_ATOMIC_WRITE(klass, &RCLASS_WRITABLE_CC_TBL(klass), new_table);
2086+
}
2087+
else {
2088+
rb_vm_cc_table_delete(cc_tbl, mid);
2089+
}
2090+
}
20982091

2099-
if (ccs_ci_argc == argc && ccs_ci_flag == flag) {
2100-
RB_DEBUG_COUNTER_INC(cc_found_in_ccs);
2092+
static const struct rb_callcache *
2093+
vm_populate_cc(VALUE klass, const struct rb_callinfo * const ci, ID mid)
2094+
{
2095+
ASSERT_vm_locking();
21012096

2102-
VM_ASSERT(vm_cc_cme(ccs_cc)->called_id == mid);
2103-
VM_ASSERT(ccs_cc->klass == klass);
2104-
VM_ASSERT(!METHOD_ENTRY_INVALIDATED(vm_cc_cme(ccs_cc)));
2097+
VALUE cc_tbl = RCLASS_WRITABLE_CC_TBL(klass);
2098+
const VALUE original_cc_table = cc_tbl;
2099+
struct rb_class_cc_entries *ccs = NULL;
21052100

2106-
return ccs_cc;
2107-
}
2108-
}
2109-
}
2110-
}
2101+
if (!cc_tbl) {
2102+
cc_tbl = rb_vm_cc_table_create(1);
21112103
}
2112-
else {
2113-
cc_tbl = rb_vm_cc_table_create(2);
2114-
RCLASS_WRITE_CC_TBL(klass, cc_tbl);
2104+
else if (rb_multi_ractor_p()) {
2105+
cc_tbl = rb_vm_cc_table_dup(cc_tbl);
21152106
}
21162107

21172108
RB_DEBUG_COUNTER_INC(cc_not_found_in_ccs);
@@ -2143,11 +2134,7 @@ vm_search_cc(const VALUE klass, const struct rb_callinfo * const ci)
21432134
if (ccs == NULL) {
21442135
VM_ASSERT(cc_tbl);
21452136

2146-
if (LIKELY(rb_managed_id_table_lookup(cc_tbl, mid, &ccs_data))) {
2147-
// rb_callable_method_entry() prepares ccs.
2148-
ccs = (struct rb_class_cc_entries *)ccs_data;
2149-
}
2150-
else {
2137+
if (!LIKELY(rb_managed_id_table_lookup(cc_tbl, mid, (VALUE *)&ccs))) {
21512138
// TODO: required?
21522139
ccs = vm_ccs_create(klass, cc_tbl, mid, cme);
21532140
}
@@ -2162,6 +2149,91 @@ vm_search_cc(const VALUE klass, const struct rb_callinfo * const ci)
21622149
VM_ASSERT(cme->called_id == mid);
21632150
VM_ASSERT(vm_cc_cme(cc)->called_id == mid);
21642151

2152+
if (original_cc_table != cc_tbl) {
2153+
RB_OBJ_ATOMIC_WRITE(klass, &RCLASS_WRITABLE_CC_TBL(klass), cc_tbl);
2154+
}
2155+
2156+
return cc;
2157+
}
2158+
2159+
static const struct rb_callcache *
2160+
vm_lookup_cc(const VALUE klass, const struct rb_callinfo * const ci, ID mid)
2161+
{
2162+
VALUE cc_tbl;
2163+
struct rb_class_cc_entries *ccs;
2164+
retry:
2165+
cc_tbl = RUBY_ATOMIC_VALUE_LOAD(RCLASS_WRITABLE_CC_TBL(klass));
2166+
ccs = NULL;
2167+
2168+
if (cc_tbl) {
2169+
// CCS data is keyed on method id, so we don't need the method id
2170+
// for doing comparisons in the `for` loop below.
2171+
2172+
if (rb_managed_id_table_lookup(cc_tbl, mid, (VALUE *)&ccs)) {
2173+
const int ccs_len = ccs->len;
2174+
2175+
if (UNLIKELY(METHOD_ENTRY_INVALIDATED(ccs->cme))) {
2176+
RB_VM_LOCKING() {
2177+
vm_evict_cc(klass, cc_tbl, mid);
2178+
}
2179+
goto retry;
2180+
}
2181+
else {
2182+
VM_ASSERT(vm_ccs_verify(ccs, mid, klass));
2183+
2184+
// We already know the method id is correct because we had
2185+
// to look up the ccs_data by method id. All we need to
2186+
// compare is argc and flag
2187+
unsigned int argc = vm_ci_argc(ci);
2188+
unsigned int flag = vm_ci_flag(ci);
2189+
2190+
for (int i=0; i<ccs_len; i++) {
2191+
unsigned int ccs_ci_argc = ccs->entries[i].argc;
2192+
unsigned int ccs_ci_flag = ccs->entries[i].flag;
2193+
const struct rb_callcache *ccs_cc = ccs->entries[i].cc;
2194+
2195+
VM_ASSERT(IMEMO_TYPE_P(ccs_cc, imemo_callcache));
2196+
2197+
if (ccs_ci_argc == argc && ccs_ci_flag == flag) {
2198+
RB_DEBUG_COUNTER_INC(cc_found_in_ccs);
2199+
2200+
VM_ASSERT(vm_cc_cme(ccs_cc)->called_id == mid);
2201+
VM_ASSERT(ccs_cc->klass == klass);
2202+
VM_ASSERT(!METHOD_ENTRY_INVALIDATED(vm_cc_cme(ccs_cc)));
2203+
2204+
return ccs_cc;
2205+
}
2206+
}
2207+
}
2208+
}
2209+
}
2210+
2211+
RB_GC_GUARD(cc_tbl);
2212+
return NULL;
2213+
}
2214+
2215+
static const struct rb_callcache *
2216+
vm_search_cc(const VALUE klass, const struct rb_callinfo * const ci)
2217+
{
2218+
const ID mid = vm_ci_mid(ci);
2219+
2220+
const struct rb_callcache *cc = vm_lookup_cc(klass, ci, mid);
2221+
if (cc) {
2222+
return cc;
2223+
}
2224+
2225+
RB_VM_LOCKING() {
2226+
if (rb_multi_ractor_p()) {
2227+
// The CC may have been populated by another ractor while we were waiting on the lock,
2228+
// so we must lookup a second time.
2229+
cc = vm_lookup_cc(klass, ci, mid);
2230+
}
2231+
2232+
if (!cc) {
2233+
cc = vm_populate_cc(klass, ci, mid);
2234+
}
2235+
}
2236+
21652237
return cc;
21662238
}
21672239

@@ -2172,16 +2244,14 @@ rb_vm_search_method_slowpath(const struct rb_callinfo *ci, VALUE klass)
21722244

21732245
VM_ASSERT_TYPE2(klass, T_CLASS, T_ICLASS);
21742246

2175-
RB_VM_LOCKING() {
2176-
cc = vm_search_cc(klass, ci);
2247+
cc = vm_search_cc(klass, ci);
21772248

2178-
VM_ASSERT(cc);
2179-
VM_ASSERT(IMEMO_TYPE_P(cc, imemo_callcache));
2180-
VM_ASSERT(cc == vm_cc_empty() || cc->klass == klass);
2181-
VM_ASSERT(cc == vm_cc_empty() || callable_method_entry_p(vm_cc_cme(cc)));
2182-
VM_ASSERT(cc == vm_cc_empty() || !METHOD_ENTRY_INVALIDATED(vm_cc_cme(cc)));
2183-
VM_ASSERT(cc == vm_cc_empty() || vm_cc_cme(cc)->called_id == vm_ci_mid(ci));
2184-
}
2249+
VM_ASSERT(cc);
2250+
VM_ASSERT(IMEMO_TYPE_P(cc, imemo_callcache));
2251+
VM_ASSERT(cc == vm_cc_empty() || cc->klass == klass);
2252+
VM_ASSERT(cc == vm_cc_empty() || callable_method_entry_p(vm_cc_cme(cc)));
2253+
VM_ASSERT(cc == vm_cc_empty() || !METHOD_ENTRY_INVALIDATED(vm_cc_cme(cc)));
2254+
VM_ASSERT(cc == vm_cc_empty() || vm_cc_cme(cc)->called_id == vm_ci_mid(ci));
21852255

21862256
return cc;
21872257
}

0 commit comments

Comments
 (0)