Tarantool development patches archive
 help / color / mirror / Atom feed
From: Sergey Kaplun via Tarantool-patches <tarantool-patches@dev.tarantool.org>
To: Maxim Kokryashkin <m.kokryashkin@tarantool.org>,
	Sergey Bronnikov <sergeyb@tarantool.org>
Cc: tarantool-patches@dev.tarantool.org
Subject: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.
Date: Mon, 13 Nov 2023 18:05:01 +0300	[thread overview]
Message-ID: <20231113150501.28143-1-skaplun@tarantool.org> (raw)

From: Mike Pall <mike>

Reported by XmiliaH.

(cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)

`fold_abc_k()` doesn't patch the first ABC check when the right constant
operand is negative. This leads to out-of-bounds access from the array
on a trace. This patch casts to uint32_t the operands to compare. If the
right IR contains a negative integer, the second IR will always be
patched. Also, because the ABC check on the trace is unordered, this
guard will always fail.

Also, this fold rule creates new instructions that reference operands
across PHIs. This opens the room for other optimizations (like DCE), so
some guards become eliminated, and we use out-of-bounds access from the
array part of the table on trace. This patch adds the missing
`PHIBARRIER()` check.

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

Part of tarantool/tarantool#9145
---
Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
Related issues:
* https://github.com/LuaJIT/LuaJIT/issues/794
* https://github.com/tarantool/tarantool/issues/9145

 src/lj_opt_fold.c                             |  5 +-
 .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
 2 files changed, 88 insertions(+), 2 deletions(-)
 create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua

diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
index 944a9ecc..6175f7c1 100644
--- a/src/lj_opt_fold.c
+++ b/src/lj_opt_fold.c
@@ -1877,14 +1877,15 @@ LJFOLDF(abc_fwd)
 LJFOLD(ABC any KINT)
 LJFOLDF(abc_k)
 {
+  PHIBARRIER(fleft);
   if (LJ_LIKELY(J->flags & JIT_F_OPT_ABC)) {
     IRRef ref = J->chain[IR_ABC];
     IRRef asize = fins->op1;
     while (ref > asize) {
       IRIns *ir = IR(ref);
       if (ir->op1 == asize && irref_isk(ir->op2)) {
-	int32_t k = IR(ir->op2)->i;
-	if (fright->i > k)
+	uint32_t k = (uint32_t)IR(ir->op2)->i;
+	if ((uint32_t)fright->i > k)
 	  ir->op2 = fins->op2;
 	return DROPFOLD;
       }
diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
new file mode 100644
index 00000000..f8609933
--- /dev/null
+++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
@@ -0,0 +1,85 @@
+local tap = require('tap')
+
+-- Test file to demonstrate LuaJIT's incorrect fold optimization
+-- for Array Bound Check for constants.
+-- ABC(asize, k1), ABC(asize k2) ==> ABC(asize, max(k1, k2)).
+-- See also https://github.com/LuaJIT/LuaJIT/issues/794.
+
+local test = tap.test('lj-794-abc-fold-constants'):skipcond({
+  ['Test requires JIT enabled'] = not jit.status(),
+})
+
+local MAGIC_UNUSED = 42
+test:plan(2)
+
+local function abc_check_sign()
+  local tab = {MAGIC_UNUSED}
+  local return_value = 0
+  local abc_limit = 1
+  -- No need to run the loop on the first call. We will take
+  -- the side exit anyway.
+  for i = 1, 3 do
+    -- Add an additional ABC check to be merged with.
+    if i > 1 then
+      -- luacheck: ignore
+      return_value = tab[1]
+      return_value = tab[abc_limit]
+      -- XXX: Just use some negative number.
+      abc_limit = -1000000
+    end
+  end
+  return return_value
+end
+
+jit.opt.start('hotloop=1')
+
+-- Compile the loop.
+abc_check_sign()
+-- Run the loop.
+test:is(abc_check_sign(), nil, 'correct ABC constant rule for negative values')
+
+-- Now test the second issue, when ABC optimization applies for
+-- operands across PHIs.
+
+-- XXX: Reset hotcounters to avoid collisions.
+jit.opt.start('hotloop=1')
+
+local tab_array = {}
+local small_tab = {MAGIC_UNUSED}
+local full_tab = {}
+
+-- First, create tables with different asizes, to be used in PHI.
+-- Create a large enough array part for the noticeable
+-- out-of-bounds access.
+for i = 1, 8 do
+  full_tab[i] = MAGIC_UNUSED
+end
+
+-- We need 5 iterations to execute both the variant and the
+-- invariant parts of the trace below.
+for i = 1, 5 do
+  -- On the 3rd iteration, the recording is started.
+  if i > 3 then
+    tab_array[i] = small_tab
+  else
+    tab_array[i] = full_tab
+  end
+end
+
+local result
+local alias_tab = tab_array[1]
+-- Compile a trace.
+-- Run 5 iterations to execute both the variant and the invariant
+-- parts.
+for i = 1, 5 do
+  local local_tab = alias_tab
+  alias_tab = tab_array[i]
+  -- Additional ABC check to fold.
+  -- luacheck: ignore
+  result = alias_tab[1]
+  result = local_tab[8]
+end
+
+test:is(result, nil, 'correct ABC constant rule across PHI')
+
+test:done(true)
-- 
2.42.0


             reply	other threads:[~2023-11-13 15:09 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-11-13 15:05 Sergey Kaplun via Tarantool-patches [this message]
2023-11-17 11:27 ` Maxim Kokryashkin via Tarantool-patches
2023-11-20 10:58   ` Sergey Kaplun via Tarantool-patches
2023-11-20 17:06     ` Maxim Kokryashkin via Tarantool-patches
2023-11-18 16:24 ` Sergey Bronnikov via Tarantool-patches
2023-11-20 11:12   ` Sergey Kaplun via Tarantool-patches
2023-11-20 12:08     ` Sergey Bronnikov via Tarantool-patches

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20231113150501.28143-1-skaplun@tarantool.org \
    --to=tarantool-patches@dev.tarantool.org \
    --cc=m.kokryashkin@tarantool.org \
    --cc=sergeyb@tarantool.org \
    --cc=skaplun@tarantool.org \
    --subject='Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox