Basic block invalidation mechanism #21

maximecb · 2021-01-11T21:44:46Z

There are a few situations in which it might be useful to invalidate basic block versions:

Primitive op (eg: plus/minus) redefined
Method redefined on class, throw away code calling that method
A method uses binding to modify local types in a caller

In the case of primitive op redefinitions, we might be better off throwing away all the compiled code, but class method redefinitions might happen too often for that to be practical. We could instead implement a strategy that allows invalidating generated code for one specific basic block version. I think it makes sense to figure out a solution for this early on, to avoid tedious refactorings later down the road.

To invalidate an individual basic block:

All branches jumping to the block should be atomically patched with jumps going to a stub instead.
There can also be other blocks falling through to the invalidated block because they immediately precede it.
- If an incoming fall-through branch is too short to be patched, we may need to invalidate its block
  - This may not be an issue in practice, because the block we go to could have space
  - We can force any block that may need to be invalidated to have sufficient space to contain a jump to a stub
If the block is an entry point, it needs to be unmapped from its iseq
- Unmap/remap anything at this iseq/idx
- Optional: may want to recompile a new deoptimized entry point
Call continuation addresses on the stack can also be atomically replaced by jumps going to the stub.

Need:

list of blocks making cc/cme assumptions
- Alan already created a hash table
- Should contain blockid (iseq/idx) to invalidate
For a given block version, list of incoming branch entries (branch idxs)
- This could be stored in a hash map or on some block version object
- We only care about the branches that are actually patched, already executed
  - Jump to stubs can stay as-is

Question: would it be useful to have block version objects?

It looks like a blockid_t is not sufficient, we need a specific version
For invalidation, we need per-block metadata such as incoming branches
Branches may need a pointer to their parent block

The text was updated successfully, but these errors were encountered:

maximecb · 2021-01-15T22:13:39Z

I've sketched the code for this, but we are currently failing the method invalidation test Alan wrote:

make test-all TESTS=test/ruby/test_microjit.rb

I'll keep investigating.

maximecb · 2021-01-20T17:33:39Z

The test is working :)

This commit adds a check on the ep just like in the mark function. The env can contain null bytes if allocation tracing is enabled. We're seeing errors during autocompaction like this: ``` (lldb) bt 40 * thread #1, name = 'ruby', stop reason = signal SIGABRT frame #0: 0x00007f7d64b6018b libc.so.6`raise + 203 frame #1: 0x00007f7d64b3f859 libc.so.6`abort + 299 frame #2: 0x000055af5f2fefc9 ruby`die at error.c:764:5 frame #3: 0x000055af5f2ff1ac ruby`rb_bug_for_fatal_signal(default_sighandler=0x0000000000000000, sig=11, ctx=0x000055af60bc3340, fmt="") at error.c:804:5 frame #4: 0x000055af5f4bd08f ruby`sigsegv(sig=11, info=0x000055af60bc3470, ctx=0x000055af60bc3340) at signal.c:960:5 frame #5: 0x00007f7d64ebe3c0 libpthread.so.0`__restore_rt frame #6: 0x000055af5f339b0a ruby`gc_ref_update_imemo(objspace=0x000055af60b2b040, obj=0x00007f7d5b513fd0) at gc.c:9046:13 frame #7: 0x000055af5f339172 ruby`gc_update_object_references(objspace=0x000055af60b2b040, obj=0x00007f7d5b513fd0) at gc.c:9307:9 frame #8: 0x000055af5f338e79 ruby`gc_ref_update(vstart=0x00007f7d5b510010, vend=0x00007f7d5b513ff8, stride=40, objspace=0x000055af60b2b040, page=0x000055af62577aa0) at gc.c:9452:21 frame #9: 0x000055af5f337846 ruby`gc_update_references(objspace=0x000055af60b2b040, heap=0x000055af60b2b068) at gc.c:9481:9 frame #10: 0x000055af5f336569 ruby`gc_compact_finish(objspace=0x000055af60b2b040, heap=0x000055af60b2b068) at gc.c:4840:5 frame #11: 0x000055af5f335efb ruby`gc_page_sweep(objspace=0x000055af60b2b040, heap=0x000055af60b2b068, sweep_page=0x000055af63a1eb30) at gc.c:5046:13 frame #12: 0x000055af5f3355c5 ruby`gc_sweep_step(objspace=0x000055af60b2b040, heap=0x000055af60b2b068) at gc.c:5214:19 frame #13: 0x000055af5f33daf6 ruby`gc_sweep_rest(objspace=0x000055af60b2b040) at gc.c:5271:2 frame #14: 0x000055af5f33cacd ruby`gc_sweep(objspace=0x000055af60b2b040) at gc.c:5389:2 frame #15: 0x000055af5f33c21d ruby`gc_marks_rest(objspace=0x000055af60b2b040) at gc.c:7555:5 frame #16: 0x000055af5f324d41 ruby`gc_rest(objspace=0x000055af60b2b040) at gc.c:8457:13 frame #17: 0x000055af5f3297d8 ruby`garbage_collect(objspace=0x000055af60b2b040, reason=45568) at gc.c:8318:9 frame #18: 0x000055af5f344ece ruby`garbage_collect_with_gvl(objspace=0x000055af60b2b040, reason=45568) at gc.c:8632:9 frame #19: 0x000055af5f344e61 ruby`objspace_malloc_gc_stress(objspace=0x000055af60b2b040) at gc.c:10592:9 frame #20: 0x000055af5f32ced1 ruby`objspace_xmalloc0(objspace=0x000055af60b2b040, size=64) at gc.c:10767:5 frame #21: 0x000055af5f32ce11 ruby`ruby_xmalloc0(size=64) at gc.c:10988:12 frame #22: 0x000055af5f32cdac ruby`ruby_xmalloc_body(size=64) at gc.c:10997:12 frame #23: 0x000055af5f329415 ruby`ruby_xmalloc(size=64) at gc.c:12942:12 frame #24: 0x00007f7d611c4fe5 objspace.so`newobj_i(tpval=0x00007f7d5b553770, data=0x000055af639031a0) at object_tracing.c:101:35 frame #25: 0x000055af5f5b283f ruby`tp_call_trace(tpval=0x00007f7d5b553770, trace_arg=0x00007fff1016d398) at vm_trace.c:1115:2 frame #26: 0x000055af5f5b50ec ruby`exec_hooks_body(ec=0x000055af60b2b700, list=0x000055af60b2b920, trace_arg=0x00007fff1016d398) at vm_trace.c:304:3 frame #27: 0x000055af5f5b0f24 ruby`exec_hooks_unprotected(ec=0x000055af60b2b700, list=0x000055af60b2b920, trace_arg=0x00007fff1016d398) at vm_trace.c:333:5 frame #28: 0x000055af5f5b0da8 ruby`rb_exec_event_hooks(trace_arg=0x00007fff1016d398, hooks=0x000055af60b2b920, pop_p=0) at vm_trace.c:378:13 frame #29: 0x000055af5f33f8e2 ruby`rb_exec_event_hook_orig(ec=0x000055af60b2b700, hooks=0x000055af60b2b920, flag=1048576, self=0x00007f7d5b5c08c0, id=0, called_id=0, klass=0x0000000000000000, data=0x00007f7d5b513fd0, pop_p=0) at vm_core.h:1989:5 frame #30: 0x000055af5f334975 ruby`gc_event_hook_body(ec=0x000055af60b2b700, objspace=0x000055af60b2b040, event=1048576, data=0x00007f7d5b513fd0) at gc.c:2083:5 * frame #31: 0x000055af5f3342df ruby`newobj_slowpath_wb_protected [inlined] newobj_slowpath(klass=0x00007f7d5b9d19c8, flags=0x000000000000001a, objspace=0x000055af60b2b040, cr=0x000055af60b2b910, wb_protected=1) at gc.c:2284:9 frame #32: 0x000055af5f33410f ruby`newobj_slowpath_wb_protected(klass=0x00007f7d5b9d19c8, flags=0x000000000000001a, objspace=0x000055af60b2b040, cr=0x000055af60b2b910) at gc.c:2299 frame #33: 0x000055af5f333de9 ruby`newobj_of0(klass=0x00007f7d5b9d19c8, flags=0x000000000000001a, wb_protected=1, cr=0x000055af60b2b910) at gc.c:2338:11 frame #34: 0x000055af5f3227ae ruby`newobj_of(klass=0x00007f7d5b9d19c8, flags=0x000000000000001a, v1=0x000055af657d88a0, v2=0x000055af657d8890, v3=0x0000000000000000, wb_protected=1) at gc.c:2348:17 frame #35: 0x000055af5f322c5b ruby`rb_imemo_new(type=imemo_env, v1=0x000055af657d88a0, v2=0x000055af657d8890, v3=0x0000000000000000, v0=0x00007f7d5b9d19c8) at gc.c:2434:12 frame #36: 0x000055af5f5a3925 ruby`vm_env_new(env_ep=0x000055af657d88a0, env_body=0x000055af657d8890, env_size=4, iseq=0x00007f7d5b9d19c8) at vm_core.h:1363:33 frame #37: 0x000055af5f5a3808 ruby`vm_make_env_each(ec=0x000055af60b2b700, cfp=0x00007f7d6482fc90) at vm.c:801:11 frame #38: 0x000055af5f5a368d ruby`vm_make_env_each(ec=0x000055af60b2b700, cfp=0x00007f7d6482fc20) at vm.c:752:13 frame #39: 0x000055af5f5a368d ruby`vm_make_env_each(ec=0x000055af60b2b700, cfp=0x00007f7d6482fbb0) at vm.c:752:13 (lldb) f 31 frame #31: 0x000055af5f3342df ruby`newobj_slowpath_wb_protected [inlined] newobj_slowpath(klass=0x00007f7d5b9d19c8, flags=0x000000000000001a, objspace=0x000055af60b2b040, cr=0x000055af60b2b910, wb_protected=1) at gc.c:2284:9 2281 } 2282 GC_ASSERT(obj != 0); 2283 newobj_init(klass, flags, wb_protected, objspace, obj); -> 2284 gc_event_hook_prep(objspace, RUBY_INTERNAL_EVENT_NEWOBJ, obj, newobj_fill(obj, 0, 0, 0)); 2285 } 2286 RB_VM_LOCK_LEAVE_CR_LEV(cr, &lev); 2287 (lldb) p obj (VALUE) $3 = 0x00007f7d5b513fd0 (lldb) f 6 frame #6: 0x000055af5f339b0a ruby`gc_ref_update_imemo(objspace=0x000055af60b2b040, obj=0x00007f7d5b513fd0) at gc.c:9046:13 9043 { 9044 rb_env_t *env = (rb_env_t *)obj; 9045 TYPED_UPDATE_IF_MOVED(objspace, rb_iseq_t *, env->iseq); -> 9046 UPDATE_IF_MOVED(objspace, env->ep[VM_ENV_DATA_INDEX_ENV]); 9047 gc_update_values(objspace, (long)env->env_size, (VALUE *)env->env); 9048 } 9049 break; (lldb) p obj (VALUE) $4 = 0x00007f7d5b513fd0 (lldb) ```

maximecb created this issue from a note in YJIT (Todo) Jan 11, 2021

maximecb moved this from Todo to In progress in YJIT Jan 11, 2021

maximecb self-assigned this Jan 11, 2021

maximecb added the enhancement New feature or request label Jan 12, 2021

maximecb moved this from In progress to Done in YJIT Jan 15, 2021

maximecb moved this from Done to In progress in YJIT Jan 15, 2021

maximecb moved this from In progress to Done in YJIT Jan 19, 2021

maximecb closed this as completed Jan 20, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Basic block invalidation mechanism #21

Basic block invalidation mechanism #21

maximecb commented Jan 11, 2021 •

edited

Loading

maximecb commented Jan 15, 2021

maximecb commented Jan 20, 2021

Basic block invalidation mechanism #21

Basic block invalidation mechanism #21

Comments

maximecb commented Jan 11, 2021 • edited Loading

maximecb commented Jan 15, 2021

maximecb commented Jan 20, 2021

maximecb commented Jan 11, 2021 •

edited

Loading