[Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Sergey Kaplun via Tarantool-patches]

From: Mike Pall <mike>

Reported by pwnhacker0x18. Fixed by Peter Cawley.

(cherry picked from commit 7369eff67d46d7f5fac9ee064e3fbf97a15458de)

The `IR_ABC` has 2 different types:
* `IRT_INT` for generic condition check.
* `IRT_P32` as a marker for the invariant checks for upper and lower
  boundaries of the loop index. These checks may be dropped during the
  folding optimization in recording the variant part of the loop.
The checks may be dropped if the instruction is not PHI, the first
operand is invariant, and the upper bound of the array part of the table
isn't changed, or the table itself isn't changed on the trace.

The checks in the `abc_invar` fold rule assume that the constant values
of the first operand of ABC may be dropped. But when this constant value
comes from the folding chain that does CSE, the check is still necessary
if the original instruction (not resulting after loop optimization
substitution and the folding chain) isn't a constant.

Hence, this patch additionally singularizes the `IRT_U32` type for the
`IR_ABC` in the case when the asize is a constant on the trace so it can
be simply dropped from the invariant part of the loop. For `IRT_P32`
type, this patch adds a check that the first operand isn't a constant to
be sure that it isn't a result of the fold chain.

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-1194-abc-hoisting
Related issues:
* https://github.com/LuaJIT/LuaJIT/issues/1194
* https://github.com/tarantool/tarantool/issues/11055

 src/lj_opt_fold.c                             |  5 +-
 src/lj_record.c                               |  5 +-
 .../lj-1194-abc-hoisting.test.lua             | 77 +++++++++++++++++++
 3 files changed, 83 insertions(+), 4 deletions(-)
 create mode 100644 test/tarantool-tests/lj-1194-abc-hoisting.test.lua

diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
index cd4395bb..83105816 100644
--- a/src/lj_opt_fold.c
+++ b/src/lj_opt_fold.c
@@ -1906,9 +1906,10 @@ LJFOLDF(abc_k)
 LJFOLD(ABC any any)
 LJFOLDF(abc_invar)
 {
-  /* Invariant ABC marked as PTR. Drop if op1 is invariant, too. */
+  /* Invariant ABC marked as P32 or U32. Drop if op1 is invariant too. */
   if (!irt_isint(fins->t) && fins->op1 < J->chain[IR_LOOP] &&
-      !irt_isphi(IR(fins->op1)->t))
+      (irt_isu32(fins->t) ||
+       (!irref_isk(fins->op1) && !irt_isphi(IR(fins->op1)->t))))
     return DROPFOLD;
   return NEXTFOLD;
 }
diff --git a/src/lj_record.c b/src/lj_record.c
index 5345fa63..3dc6e840 100644
--- a/src/lj_record.c
+++ b/src/lj_record.c
@@ -1315,12 +1315,13 @@ static void rec_idx_abc(jit_State *J, TRef asizeref, TRef ikey, uint32_t asize)
       /* Runtime value for stop of loop is within bounds? */
       if ((uint64_t)stop + ofs < (uint64_t)asize) {
 	/* Emit invariant bounds check for stop. */
-	emitir(IRTG(IR_ABC, IRT_P32), asizeref, ofs == 0 ? J->scev.stop :
+	uint32_t abc = IRTG(IR_ABC, tref_isk(asizeref) ? IRT_U32 : IRT_P32);
+	emitir(abc, asizeref, ofs == 0 ? J->scev.stop :
 	       emitir(IRTI(IR_ADD), J->scev.stop, ofsref));
 	/* Emit invariant bounds check for start, if not const or negative. */
 	if (!(J->scev.dir && J->scev.start &&
 	      (int64_t)IR(J->scev.start)->i + ofs >= 0))
-	  emitir(IRTG(IR_ABC, IRT_P32), asizeref, ikey);
+	  emitir(abc, asizeref, ikey);
 	return;
       }
     }
diff --git a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
new file mode 100644
index 00000000..3a78c34e
--- /dev/null
+++ b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
@@ -0,0 +1,77 @@
+local tap = require('tap')
+
+-- Test file to demonstrate LuaJIT's incorrect hoisting out of the
+-- loop for Array Bound Check.
+-- See also https://github.com/LuaJIT/LuaJIT/issues/1194.
+
+local test = tap.test('lj-1194-abc-hoisting'):skipcond({
+  ['Test requires JIT enabled'] = not jit.status(),
+})
+
+test:plan(1)
+
+local table_new = require('table.new')
+
+-- Before the patch, the `for` cycle in the `test_func()` below
+-- produces the following trace:
+--
+-- | 0006    int FLOAD  0005  tab.asize
+-- | 0007 >  p32 ABC    0006  0001
+-- | 0008    p32 FLOAD  0005  tab.array
+-- | 0009    p32 AREF   0008  0003
+-- | 0010    tab FLOAD  0005  tab.meta
+-- | 0011 >  tab EQ     0010  NULL
+-- | 0012    nil ASTORE 0009  nil
+-- | 0013 >+ tab TNEW   #0    #0
+-- | 0014  + int ADD    0003  +1
+-- | 0015 >  int LE     0014  0001
+-- | 0016 ------ LOOP ------------
+-- | 0017 >  int NE     0014  +0
+-- | 0018    p32 FLOAD  0013  tab.array
+-- | 0019    p32 AREF   0018  0014
+-- | 0020    nil ASTORE 0019  nil
+--
+-- As you can see, the `0007 ABC` instruction is dropped from the
+-- variant part of the loop.
+
+-- Disable fusing to simplify the reproducer it now will be crash
+-- on loading of an address from the `t->array`.
+jit.opt.start('hotloop=1', '-fuse')
+
+local function test_func()
+  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant
+  -- and variant parts of the loop. The trace is run via an
+  -- additional call to this function.
+  local limit = 3
+  -- Create a table with a fixed array size (`limit` + 1), so all
+  -- access to it fits into the array part.
+  local s = table_new(limit, 0)
+  for i = 1, limit do
+    -- Don't change the table on hotcount warm-up.
+    if i ~= 1 then
+      -- `0020 ASTORE` causes the SegFault on the trace on the
+      -- last (3rd) iteration, since the table (set on the first
+      -- iteration) has `asize == 0`, and t->array == NULL`.
+      -- luacheck: no unused
+      s[i] = nil
+      s = {}
+    end
+  end
+end
+
+-- Compile the `for` trace inside `test_func()`.
+-- The invariant part of this trace contains the ABC check, while
+-- the invariant does not. So, first compile the trace, then use
+-- the second call to run it from the beginning with all guards
+-- passing in the invariant part.
+test_func()
+
+-- Avoid compilation of any other traces.
+jit.off()
+
+-- Run that trace.
+test_func()
+
+test:ok(true, 'no crash on the trace due to incorrect ABC hoisting')
+
+test:done(true)
-- 
2.48.1

Re: [Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Sergey Bronnikov via Tarantool-patches]

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

Hi, Sergey!

thanks for the patch! LGTM with minor comments that can be ignored.

Sergey

On 27.02.2025 19:00, Sergey Kaplun wrote:
> From: Mike Pall <mike>
>
> Reported by pwnhacker0x18. Fixed by Peter Cawley.
>
> (cherry picked from commit 7369eff67d46d7f5fac9ee064e3fbf97a15458de)
>
> The `IR_ABC` has 2 different types:
> * `IRT_INT` for generic condition check.
> * `IRT_P32` as a marker for the invariant checks for upper and lower
>    boundaries of the loop index. These checks may be dropped during the
>    folding optimization in recording the variant part of the loop.
> The checks may be dropped if the instruction is not PHI, the first
> operand is invariant, and the upper bound of the array part of the table
> isn't changed, or the table itself isn't changed on the trace.
>
> The checks in the `abc_invar` fold rule assume that the constant values
> of the first operand of ABC may be dropped. But when this constant value
> comes from the folding chain that does CSE, the check is still necessary
> if the original instruction (not resulting after loop optimization
> substitution and the folding chain) isn't a constant.
>
> Hence, this patch additionally singularizes the `IRT_U32` type for the
> `IR_ABC` in the case when the asize is a constant on the trace so it can
> be simply dropped from the invariant part of the loop. For `IRT_P32`
> type, this patch adds a check that the first operand isn't a constant to
> be sure that it isn't a result of the fold chain.
>
> 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-1194-abc-hoisting
> Related issues:
> *https://github.com/LuaJIT/LuaJIT/issues/1194
> *https://github.com/tarantool/tarantool/issues/11055
>
>   src/lj_opt_fold.c                             |  5 +-
>   src/lj_record.c                               |  5 +-
>   .../lj-1194-abc-hoisting.test.lua             | 77 +++++++++++++++++++
>   3 files changed, 83 insertions(+), 4 deletions(-)
>   create mode 100644 test/tarantool-tests/lj-1194-abc-hoisting.test.lua
>
> diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
> index cd4395bb..83105816 100644
> --- a/src/lj_opt_fold.c
> +++ b/src/lj_opt_fold.c
> @@ -1906,9 +1906,10 @@ LJFOLDF(abc_k)
>   LJFOLD(ABC any any)
>   LJFOLDF(abc_invar)
>   {
> -  /* Invariant ABC marked as PTR. Drop if op1 is invariant, too. */
> +  /* Invariant ABC marked as P32 or U32. Drop if op1 is invariant too. */
>     if (!irt_isint(fins->t) && fins->op1 < J->chain[IR_LOOP] &&
> -      !irt_isphi(IR(fins->op1)->t))
> +      (irt_isu32(fins->t) ||
> +       (!irref_isk(fins->op1) && !irt_isphi(IR(fins->op1)->t))))
>       return DROPFOLD;
>     return NEXTFOLD;
>   }
> diff --git a/src/lj_record.c b/src/lj_record.c
> index 5345fa63..3dc6e840 100644
> --- a/src/lj_record.c
> +++ b/src/lj_record.c
> @@ -1315,12 +1315,13 @@ static void rec_idx_abc(jit_State *J, TRef asizeref, TRef ikey, uint32_t asize)
>         /* Runtime value for stop of loop is within bounds? */
>         if ((uint64_t)stop + ofs < (uint64_t)asize) {
>   	/* Emit invariant bounds check for stop. */
> -	emitir(IRTG(IR_ABC, IRT_P32), asizeref, ofs == 0 ? J->scev.stop :
> +	uint32_t abc = IRTG(IR_ABC, tref_isk(asizeref) ? IRT_U32 : IRT_P32);
> +	emitir(abc, asizeref, ofs == 0 ? J->scev.stop :
>   	       emitir(IRTI(IR_ADD), J->scev.stop, ofsref));
>   	/* Emit invariant bounds check for start, if not const or negative. */
>   	if (!(J->scev.dir && J->scev.start &&
>   	      (int64_t)IR(J->scev.start)->i + ofs >= 0))
> -	  emitir(IRTG(IR_ABC, IRT_P32), asizeref, ikey);
> +	  emitir(abc, asizeref, ikey);
>   	return;
>         }
>       }
> diff --git a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
> new file mode 100644
> index 00000000..3a78c34e
> --- /dev/null
> +++ b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
> @@ -0,0 +1,77 @@
> +local tap = require('tap')
> +
> +-- Test file to demonstrate LuaJIT's incorrect hoisting out of the
> +-- loop for Array Bound Check.
> +-- See alsohttps://github.com/LuaJIT/LuaJIT/issues/1194.
> +
> +local test = tap.test('lj-1194-abc-hoisting'):skipcond({
> +  ['Test requires JIT enabled'] = not jit.status(),
> +})
> +
> +test:plan(1)
> +
> +local table_new = require('table.new')
> +
> +-- Before the patch, the `for` cycle in the `test_func()` below
> +-- produces the following trace:
> +--
> +-- | 0006    int FLOAD  0005  tab.asize
> +-- | 0007 >  p32 ABC    0006  0001
> +-- | 0008    p32 FLOAD  0005  tab.array
> +-- | 0009    p32 AREF   0008  0003
> +-- | 0010    tab FLOAD  0005  tab.meta
> +-- | 0011 >  tab EQ     0010  NULL
> +-- | 0012    nil ASTORE 0009  nil
> +-- | 0013 >+ tab TNEW   #0    #0
> +-- | 0014  + int ADD    0003  +1
> +-- | 0015 >  int LE     0014  0001
> +-- | 0016 ------ LOOP ------------
> +-- | 0017 >  int NE     0014  +0
> +-- | 0018    p32 FLOAD  0013  tab.array
> +-- | 0019    p32 AREF   0018  0014
> +-- | 0020    nil ASTORE 0019  nil
> +--
> +-- As you can see, the `0007 ABC` instruction is dropped from the
> +-- variant part of the loop.
> +
> +-- Disable fusing to simplify the reproducer it now will be crash
> +-- on loading of an address from the `t->array`.
> +jit.opt.start('hotloop=1', '-fuse')
> +
> +local function test_func()
> +  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant

As usually we care about readers, I propose to make text more 
human-firendly:

s/1/The first/

s/2 and 3/second and third/

> +  -- and variant parts of the loop. The trace is run via an
> +  -- additional call to this function.
> +  local limit = 3
> +  -- Create a table with a fixed array size (`limit` + 1), so all
> +  -- access to it fits into the array part.
> +  local s = table_new(limit, 0)
> +  for i = 1, limit do
> +    -- Don't change the table on hotcount warm-up.
> +    if i ~= 1 then
> +      -- `0020 ASTORE` causes the SegFault on the trace on the
> +      -- last (3rd) iteration, since the table (set on the first
> +      -- iteration) has `asize == 0`, and t->array == NULL`.
> +      -- luacheck: no unused
> +      s[i] = nil
> +      s = {}
> +    end
> +  end
> +end
> +
> +-- Compile the `for` trace inside `test_func()`.
> +-- The invariant part of this trace contains the ABC check, while
> +-- the invariant does not. So, first compile the trace, then use
> +-- the second call to run it from the beginning with all guards
> +-- passing in the invariant part.
> +test_func()
> +
> +-- Avoid compilation of any other traces.
> +jit.off()
> +
> +-- Run that trace.
> +test_func()
> +
> +test:ok(true, 'no crash on the trace due to incorrect ABC hoisting')
> +
> +test:done(true)

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

Re: [Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Sergey Kaplun via Tarantool-patches]

Hi, Sergey!
Thanks for the review!
Fixed your comments, rebased the branch on the tarantool/master
and force-pushed it.

On 20.03.25, Sergey Bronnikov wrote:
> Hi, Sergey!
> 
> thanks for the patch! LGTM with minor comments that can be ignored.
> 
> Sergey
> 
> On 27.02.2025 19:00, Sergey Kaplun wrote:
> > From: Mike Pall <mike>

<snipped>

> > +local function test_func()
> > +  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant
> 
> As usually we care about readers, I propose to make text more 
> human-firendly:
> 
> s/1/The first/
> 
> s/2 and 3/second and third/
> 

Fixed, see the iterative patch below.
===================================================================
diff --git a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
index 3a78c34e..57fbc584 100644
--- a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
+++ b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
@@ -39,9 +39,10 @@ local table_new = require('table.new')
 jit.opt.start('hotloop=1', '-fuse')
 
 local function test_func()
-  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant
-  -- and variant parts of the loop. The trace is run via an
-  -- additional call to this function.
+  -- The first iteration for hotcount warm-up. The second and
+  -- third are needed to record invariant and variant parts of the
+  -- loop. The trace is run via an additional call to this
+  -- function.
   local limit = 3
   -- Create a table with a fixed array size (`limit` + 1), so all
   -- access to it fits into the array part.
===================================================================

> > +  -- and variant parts of the loop. The trace is run via an

<snipped>

-- 
Best regards,
Sergey Kaplun

Re: [Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Sergey Bronnikov via Tarantool-patches]

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

Thanks! LGTM

On 20.03.2025 15:38, Sergey Kaplun wrote:
> Hi, Sergey!
> Thanks for the review!
> Fixed your comments, rebased the branch on the tarantool/master
> and force-pushed it.
>
> On 20.03.25, Sergey Bronnikov wrote:
>> Hi, Sergey!
>>
>> thanks for the patch! LGTM with minor comments that can be ignored.
>>
>> Sergey
>>
>> On 27.02.2025 19:00, Sergey Kaplun wrote:
>>> From: Mike Pall <mike>
> <snipped>
>
>>> +local function test_func()
>>> +  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant
>> As usually we care about readers, I propose to make text more
>> human-firendly:
>>
>> s/1/The first/
>>
>> s/2 and 3/second and third/
>>
> Fixed, see the iterative patch below.
> ===================================================================
> diff --git a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
> index 3a78c34e..57fbc584 100644
> --- a/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
> +++ b/test/tarantool-tests/lj-1194-abc-hoisting.test.lua
> @@ -39,9 +39,10 @@ local table_new = require('table.new')
>   jit.opt.start('hotloop=1', '-fuse')
>   
>   local function test_func()
> -  -- 1 iteration for hotcount warm-up. 2 and 3 to record invariant
> -  -- and variant parts of the loop. The trace is run via an
> -  -- additional call to this function.
> +  -- The first iteration for hotcount warm-up. The second and
> +  -- third are needed to record invariant and variant parts of the
> +  -- loop. The trace is run via an additional call to this
> +  -- function.
>     local limit = 3
>     -- Create a table with a fixed array size (`limit` + 1), so all
>     -- access to it fits into the array part.
> ===================================================================
>
>>> +  -- and variant parts of the loop. The trace is run via an
> <snipped>
>

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

Re: [Tarantool-patches] [PATCH luajit] Fix IR_ABC hoisting.

[Sergey Kaplun via Tarantool-patches]

I've applied the patch into all long-term branches in tarantool/luajit
and bumped a new version in master [1], release/3.3 [2], release/3.2 [3]
and release/2.11 [4].

[1]: https://github.com/tarantool/tarantool/pull/11281
[2]: https://github.com/tarantool/tarantool/pull/11282
[3]: https://github.com/tarantool/tarantool/pull/11283
[4]: https://github.com/tarantool/tarantool/pull/11284

-- 
Best regards,
Sergey Kaplun