[Tarantool-patches] [PATCH luajit] Fix detection of inconsistent renames due to sunk values.

[Tarantool-patches] [PATCH luajit] Fix detection of inconsistent renames due to sunk values.

[Sergey Kaplun via Tarantool-patches]

From: Mike Pall <mike>

Thanks to Sergey Kaplun.

(cherry picked from commit 811e448daa0f8f06e946fb607a98ace85c43b574)

This commit is a follow-up to the commit
3a2e4847ca257f5fda903e9374762049670b7bc0 ("Detect inconsistent renames
even in the presence of sunk values."). Due to the reversed assembling
order of a trace, all registers are allocated from the bottom of the
trace to the top. Furthermore, if the snapshot contains sunk values, IRs
for them will contain the `RID_SUNK` after the first processing. If
there is another snapshot (with a smaller number) containing this sunk
IR, this IR will not be processed during the bloom filter marking in the
allocation of the slot that escapes this snapshot (since it is already
sunk). Hence, such IRs still may lead to the rename invariant violation
like in the aforementioned commit.

This patch prevents scanning from stopping when already sunk IR is faced
during snapshot processing so bloom filters contain actual information.
The disadvantage of this approach is that it assumes that any sunk
table-typed IR can't refer to the same table inside it (so there should
not be any cycling references in the sunk table).

Sergey Kaplun:
* added the description and the test for the problem

Part of tarantool/tarantool#11055
---

Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-1295-bad-renames-for-sunk-values
Related issues:
* https://github.com/LuaJIT/LuaJIT/issues/584
* https://github.com/LuaJIT/LuaJIT/issues/1295
* https://github.com/tarantool/tarantool/issues/10746
* https://github.com/tarantool/aeon/issues/282
* https://github.com/tarantool/tarantool/issues/11055

 src/lj_asm.c                                  |   4 +-
 ...-1295-bad-renames-for-sunk-values.test.lua | 111 ++++++++++++++++++
 2 files changed, 113 insertions(+), 2 deletions(-)
 create mode 100644 test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua

diff --git a/src/lj_asm.c b/src/lj_asm.c
index f7540165..9e81dbc9 100644
--- a/src/lj_asm.c
+++ b/src/lj_asm.c
@@ -903,11 +903,11 @@ static int asm_sunk_store(ASMState *as, IRIns *ira, IRIns *irs)
 static void asm_snap_alloc1(ASMState *as, IRRef ref)
 {
   IRIns *ir = IR(ref);
-  if (!irref_isk(ref) && ir->r != RID_SUNK) {
+  if (!irref_isk(ref)) {
     bloomset(as->snapfilt1, ref);
     bloomset(as->snapfilt2, hashrot(ref, ref + HASH_BIAS));
     if (ra_used(ir)) return;
-    if (ir->r == RID_SINK) {
+    if (ir->r == RID_SINK || ir->r == RID_SUNK) {
       ir->r = RID_SUNK;
 #if LJ_HASFFI
       if (ir->o == IR_CNEWI) {  /* Allocate CNEWI value. */
diff --git a/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua b/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua
new file mode 100644
index 00000000..9291fca4
--- /dev/null
+++ b/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua
@@ -0,0 +1,111 @@
+local tap = require('tap')
+
+-- Test file to demonstrate LuaJIT assembler misbehaviour.
+-- For more info, proceed to the issues:
+-- * https://github.com/LuaJIT/LuaJIT/issues/584,
+-- * https://github.com/LuaJIT/LuaJIT/issues/1295,
+-- * https://github.com/tarantool/tarantool/issues/10746.
+
+local test = tap.test('lj-1295-bad-renames-for-sunk-values'):skipcond({
+  ['Test requires JIT enabled'] = not jit.status(),
+})
+
+test:plan(1)
+
+-- XXX: The reproducer requires specific snapshotting and register
+-- allocations, so the reproducer mostly copies the relevant code
+-- from https://github.com/luafun/luafun.
+
+----- Related part of luafun.lua. --------------------------------
+
+local iterator_mt = {
+  -- Usually called by the for-in loop.
+  __call = function(self, param, state)
+    return self.gen(param, state)
+  end,
+}
+
+local wrap = function(gen, param, state)
+  return setmetatable({
+    gen = gen,
+    param = param,
+    state = state
+  }, iterator_mt), param, state
+end
+
+-- These functions call each other to implement a flat iterator
+-- over the several iterable objects.
+local chain_gen_r1
+local chain_gen_r2 = function(param, state, state_x, ...)
+  if state_x == nil then
+    local i = state[1]
+    i = i + 1
+    if param[3 * i - 2] == nil then
+      return nil
+    end
+    return chain_gen_r1(param, {i, param[3 * i]})
+  end
+  return {state[1], state_x}, ...
+end
+
+chain_gen_r1 = function(param, state)
+  local i, _ = state[1], state[2]
+  local gen_x, param_x = param[3 * i - 2], param[3 * i - 1]
+  return chain_gen_r2(param, state, gen_x(param_x, state[2]))
+end
+
+local chain = function(...)
+  local n = select('#', ...)
+  local param = { [3 * n] = 0 }
+  local gen_x, param_x, state_x
+  for i = 1, n do
+    local elem = select(i, ...)
+    -- Put gen, param, state into param table.
+    gen_x, param_x, state_x = wrap(ipairs(elem))
+    param[3 * i - 2] = gen_x
+    param[3 * i - 1] = param_x
+    param[3 * i] = state_x
+  end
+
+  return wrap(chain_gen_r1, param, {1, param[3]})
+end
+
+----- Reproducer. ------------------------------------------------
+
+-- XXX: Should be different tables.
+local a = {{'a'}, {'a'}}
+local b = {{'a'}, {'a'}}
+
+-- XXX: Here one can find the rationale for the 'hotloop' value.
+-- 1. The innermost loop in a bunch of calls tries to compile the
+-- `__call` metamethod first, but this trace is aborted due to
+-- leaving the `for _ in` loop.
+-- 2. The trace we are interested in started to compile: this is
+-- the inner `for _ in` loop with the full inlined body.
+--
+-- The chain loop in this case iterates over 4 elements. Hence, 2
+-- iterations of the outer loop are not enough. The trace
+-- mentioned in 2 is recorded on the 8th inner cycle iteration but
+-- never started. Hence, let's run 3 iterations of the outer loop
+-- instead.
+
+-- JIT fine-tuning via the 'hotloop' option allows us to catch
+-- this elusive case, which we achieved in the last bullet. The
+-- reason why this case leads to misbehaviour while restoring the
+-- guest stack at the trace exit is described in the following
+-- LuaJIT issue: https://github.com/LuaJIT/LuaJIT/issues/1295.
+
+-- Specific `hotloop` to get only one trace we are interested in.
+jit.opt.start('hotloop=7')
+
+xpcall(function()
+  for _ = 1, 3 do
+    for _ in chain(a, b) do
+    end
+  end
+  test:ok('All emitted RENAMEs are fine')
+end, function()
+  test:fail('Invalid Lua stack has been restored')
+end)
+
+test:done(true)
-- 
2.47.1

Re: [Tarantool-patches] [PATCH luajit] Fix detection of inconsistent renames due to sunk values.

[Sergey Bronnikov via Tarantool-patches]

[-- Attachment #1: Type: text/plain, Size: 6787 bytes --]

Hello, Sergey,


LGTM, thanks!


Sergey

On 03.02.2025 19:17, Sergey Kaplun wrote:
> From: Mike Pall <mike>
>
> Thanks to Sergey Kaplun.
>
> (cherry picked from commit 811e448daa0f8f06e946fb607a98ace85c43b574)
>
> This commit is a follow-up to the commit
> 3a2e4847ca257f5fda903e9374762049670b7bc0 ("Detect inconsistent renames
> even in the presence of sunk values."). Due to the reversed assembling
> order of a trace, all registers are allocated from the bottom of the
> trace to the top. Furthermore, if the snapshot contains sunk values, IRs
> for them will contain the `RID_SUNK` after the first processing. If
> there is another snapshot (with a smaller number) containing this sunk
> IR, this IR will not be processed during the bloom filter marking in the
> allocation of the slot that escapes this snapshot (since it is already
> sunk). Hence, such IRs still may lead to the rename invariant violation
> like in the aforementioned commit.
>
> This patch prevents scanning from stopping when already sunk IR is faced
> during snapshot processing so bloom filters contain actual information.
> The disadvantage of this approach is that it assumes that any sunk
> table-typed IR can't refer to the same table inside it (so there should
> not be any cycling references in the sunk table).
>
> Sergey Kaplun:
> * added the description and the test for the problem
>
> Part of tarantool/tarantool#11055
> ---
>
> Branch:https://github.com/tarantool/luajit/tree/skaplun/lj-1295-bad-renames-for-sunk-values
> Related issues:
> *https://github.com/LuaJIT/LuaJIT/issues/584
> *https://github.com/LuaJIT/LuaJIT/issues/1295
> *https://github.com/tarantool/tarantool/issues/10746
> *https://github.com/tarantool/aeon/issues/282
> *https://github.com/tarantool/tarantool/issues/11055
>
>   src/lj_asm.c                                  |   4 +-
>   ...-1295-bad-renames-for-sunk-values.test.lua | 111 ++++++++++++++++++
>   2 files changed, 113 insertions(+), 2 deletions(-)
>   create mode 100644 test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua
>
> diff --git a/src/lj_asm.c b/src/lj_asm.c
> index f7540165..9e81dbc9 100644
> --- a/src/lj_asm.c
> +++ b/src/lj_asm.c
> @@ -903,11 +903,11 @@ static int asm_sunk_store(ASMState *as, IRIns *ira, IRIns *irs)
>   static void asm_snap_alloc1(ASMState *as, IRRef ref)
>   {
>     IRIns *ir = IR(ref);
> -  if (!irref_isk(ref) && ir->r != RID_SUNK) {
> +  if (!irref_isk(ref)) {
>       bloomset(as->snapfilt1, ref);
>       bloomset(as->snapfilt2, hashrot(ref, ref + HASH_BIAS));
>       if (ra_used(ir)) return;
> -    if (ir->r == RID_SINK) {
> +    if (ir->r == RID_SINK || ir->r == RID_SUNK) {
>         ir->r = RID_SUNK;
>   #if LJ_HASFFI
>         if (ir->o == IR_CNEWI) {  /* Allocate CNEWI value. */
> diff --git a/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua b/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua
> new file mode 100644
> index 00000000..9291fca4
> --- /dev/null
> +++ b/test/tarantool-tests/lj-1295-bad-renames-for-sunk-values.test.lua
> @@ -0,0 +1,111 @@
> +local tap = require('tap')
> +
> +-- Test file to demonstrate LuaJIT assembler misbehaviour.
> +-- For more info, proceed to the issues:
> +-- *https://github.com/LuaJIT/LuaJIT/issues/584,
> +-- *https://github.com/LuaJIT/LuaJIT/issues/1295,
> +-- *https://github.com/tarantool/tarantool/issues/10746.
> +
> +local test = tap.test('lj-1295-bad-renames-for-sunk-values'):skipcond({
> +  ['Test requires JIT enabled'] = not jit.status(),
> +})
> +
> +test:plan(1)
> +
> +-- XXX: The reproducer requires specific snapshotting and register
> +-- allocations, so the reproducer mostly copies the relevant code
> +-- fromhttps://github.com/luafun/luafun.
> +
> +----- Related part of luafun.lua. --------------------------------
> +
> +local iterator_mt = {
> +  -- Usually called by the for-in loop.
> +  __call = function(self, param, state)
> +    return self.gen(param, state)
> +  end,
> +}
> +
> +local wrap = function(gen, param, state)
> +  return setmetatable({
> +    gen = gen,
> +    param = param,
> +    state = state
> +  }, iterator_mt), param, state
> +end
> +
> +-- These functions call each other to implement a flat iterator
> +-- over the several iterable objects.
> +local chain_gen_r1
> +local chain_gen_r2 = function(param, state, state_x, ...)
> +  if state_x == nil then
> +    local i = state[1]
> +    i = i + 1
> +    if param[3 * i - 2] == nil then
> +      return nil
> +    end
> +    return chain_gen_r1(param, {i, param[3 * i]})
> +  end
> +  return {state[1], state_x}, ...
> +end
> +
> +chain_gen_r1 = function(param, state)
> +  local i, _ = state[1], state[2]
> +  local gen_x, param_x = param[3 * i - 2], param[3 * i - 1]
> +  return chain_gen_r2(param, state, gen_x(param_x, state[2]))
> +end
> +
> +local chain = function(...)
> +  local n = select('#', ...)
> +  local param = { [3 * n] = 0 }
> +  local gen_x, param_x, state_x
> +  for i = 1, n do
> +    local elem = select(i, ...)
> +    -- Put gen, param, state into param table.
> +    gen_x, param_x, state_x = wrap(ipairs(elem))
> +    param[3 * i - 2] = gen_x
> +    param[3 * i - 1] = param_x
> +    param[3 * i] = state_x
> +  end
> +
> +  return wrap(chain_gen_r1, param, {1, param[3]})
> +end
> +
> +----- Reproducer. ------------------------------------------------
> +
> +-- XXX: Should be different tables.
> +local a = {{'a'}, {'a'}}
> +local b = {{'a'}, {'a'}}
> +
> +-- XXX: Here one can find the rationale for the 'hotloop' value.
> +-- 1. The innermost loop in a bunch of calls tries to compile the
> +-- `__call` metamethod first, but this trace is aborted due to
> +-- leaving the `for _ in` loop.
> +-- 2. The trace we are interested in started to compile: this is
> +-- the inner `for _ in` loop with the full inlined body.
> +--
> +-- The chain loop in this case iterates over 4 elements. Hence, 2
> +-- iterations of the outer loop are not enough. The trace
> +-- mentioned in 2 is recorded on the 8th inner cycle iteration but
> +-- never started. Hence, let's run 3 iterations of the outer loop
> +-- instead.
> +
> +-- JIT fine-tuning via the 'hotloop' option allows us to catch
> +-- this elusive case, which we achieved in the last bullet. The
> +-- reason why this case leads to misbehaviour while restoring the
> +-- guest stack at the trace exit is described in the following
> +-- LuaJIT issue:https://github.com/LuaJIT/LuaJIT/issues/1295.
> +
> +-- Specific `hotloop` to get only one trace we are interested in.
> +jit.opt.start('hotloop=7')
> +
> +xpcall(function()
> +  for _ = 1, 3 do
> +    for _ in chain(a, b) do
> +    end
> +  end
> +  test:ok('All emitted RENAMEs are fine')
> +end, function()
> +  test:fail('Invalid Lua stack has been restored')
> +end)
> +
> +test:done(true)

[-- Attachment #2: Type: text/html, Size: 8019 bytes --]