From: Sergey Bronnikov via Tarantool-patches <tarantool-patches@dev.tarantool.org>
To: Sergey Kaplun <skaplun@tarantool.org>,
Maxim Kokryashkin <m.kokryashkin@tarantool.org>
Cc: tarantool-patches@dev.tarantool.org
Subject: Re: [Tarantool-patches] [PATCH luajit] Fix HREFK forwarding vs. table.clear().
Date: Wed, 22 Nov 2023 18:25:33 +0300 [thread overview]
Message-ID: <b9fef8f2-bea3-4369-9bd4-f5a46ce2edae@tarantool.org> (raw)
In-Reply-To: <20231109122628.19853-1-skaplun@tarantool.org>
Sergey,
thanks for the patch! LGTM
On 11/9/23 15:26, Sergey Kaplun wrote:
> From: Mike Pall <mike>
>
> Reported by XmiliaH.
>
> (cherry-picked from commit d5a237eae03d2ad346f82390836371a952e9a286)
>
> When performing HREFK (and also ALOAD, HLOAD) forwarding optimization,
> the `table.clear()` function call may be performed on the table operand
> from HREFK between table creation and IR, from which value is forwarded.
> This call isn't taken in the account, so it may lead to too optimistic
> value-forwarding from NEWREF (and also ASTORE, HSTORE), or the omitted
> type guard for HREFK operation. Therefore, this leads to incorrect trace
> behaviour (for example, taking a non-nil value from the cleared table).
>
> This patch adds necessary checks for `table.clear()` calls.
>
> 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-792-hrefk-table-clear
> Tarantool PR: https://github.com/tarantool/tarantool/pull/9351
> Relate issues:
> * https://github.com/LuaJIT/LuaJIT/issues/792
> * https://github.com/tarantool/tarantool/issues/9145
>
> src/lj_opt_mem.c | 63 +++---
> .../lj-792-hrefk-table-clear.test.lua | 181 ++++++++++++++++++
> 2 files changed, 213 insertions(+), 31 deletions(-)
> create mode 100644 test/tarantool-tests/lj-792-hrefk-table-clear.test.lua
>
> diff --git a/src/lj_opt_mem.c b/src/lj_opt_mem.c
> index a83558ac..24a490d5 100644
> --- a/src/lj_opt_mem.c
> +++ b/src/lj_opt_mem.c
> @@ -72,6 +72,34 @@ static AliasRet aa_table(jit_State *J, IRRef ta, IRRef tb)
> return aa_escape(J, taba, tabb);
> }
>
> +/* Check whether there's no aliasing table.clear. */
> +static int fwd_aa_tab_clear(jit_State *J, IRRef lim, IRRef ta)
> +{
> + IRRef ref = J->chain[IR_CALLS];
> + while (ref > lim) {
> + IRIns *calls = IR(ref);
> + if (calls->op2 == IRCALL_lj_tab_clear &&
> + (ta == calls->op1 || aa_table(J, ta, calls->op1) != ALIAS_NO))
> + return 0; /* Conflict. */
> + ref = calls->prev;
> + }
> + return 1; /* No conflict. Can safely FOLD/CSE. */
> +}
> +
> +/* Check whether there's no aliasing NEWREF/table.clear for the left operand. */
> +int LJ_FASTCALL lj_opt_fwd_tptr(jit_State *J, IRRef lim)
> +{
> + IRRef ta = fins->op1;
> + IRRef ref = J->chain[IR_NEWREF];
> + while (ref > lim) {
> + IRIns *newref = IR(ref);
> + if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO)
> + return 0; /* Conflict. */
> + ref = newref->prev;
> + }
> + return fwd_aa_tab_clear(J, lim, ta);
> +}
> +
> /* Alias analysis for array and hash access using key-based disambiguation. */
> static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb)
> {
> @@ -154,7 +182,8 @@ static TRef fwd_ahload(jit_State *J, IRRef xref)
> IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr;
> IRRef tab = ir->op1;
> ir = IR(tab);
> - if (ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) {
> + if ((ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) &&
> + fwd_aa_tab_clear(J, tab, tab)) {
> /* A NEWREF with a number key may end up pointing to the array part.
> ** But it's referenced from HSTORE and not found in the ASTORE chain.
> ** Or a NEWREF may rehash the table and move unrelated number keys.
> @@ -275,7 +304,7 @@ TRef LJ_FASTCALL lj_opt_fwd_hrefk(jit_State *J)
> while (ref > tab) {
> IRIns *newref = IR(ref);
> if (tab == newref->op1) {
> - if (fright->op1 == newref->op2)
> + if (fright->op1 == newref->op2 && fwd_aa_tab_clear(J, ref, tab))
> return ref; /* Forward from NEWREF. */
> else
> goto docse;
> @@ -285,7 +314,7 @@ TRef LJ_FASTCALL lj_opt_fwd_hrefk(jit_State *J)
> ref = newref->prev;
> }
> /* No conflicting NEWREF: key location unchanged for HREFK of TDUP. */
> - if (IR(tab)->o == IR_TDUP)
> + if (IR(tab)->o == IR_TDUP && fwd_aa_tab_clear(J, tab, tab))
> fins->t.irt &= ~IRT_GUARD; /* Drop HREFK guard. */
> docse:
> return CSEFOLD;
> @@ -319,34 +348,6 @@ int LJ_FASTCALL lj_opt_fwd_href_nokey(jit_State *J)
> return 1; /* No conflict. Can fold to niltv. */
> }
>
> -/* Check whether there's no aliasing table.clear. */
> -static int fwd_aa_tab_clear(jit_State *J, IRRef lim, IRRef ta)
> -{
> - IRRef ref = J->chain[IR_CALLS];
> - while (ref > lim) {
> - IRIns *calls = IR(ref);
> - if (calls->op2 == IRCALL_lj_tab_clear &&
> - (ta == calls->op1 || aa_table(J, ta, calls->op1) != ALIAS_NO))
> - return 0; /* Conflict. */
> - ref = calls->prev;
> - }
> - return 1; /* No conflict. Can safely FOLD/CSE. */
> -}
> -
> -/* Check whether there's no aliasing NEWREF/table.clear for the left operand. */
> -int LJ_FASTCALL lj_opt_fwd_tptr(jit_State *J, IRRef lim)
> -{
> - IRRef ta = fins->op1;
> - IRRef ref = J->chain[IR_NEWREF];
> - while (ref > lim) {
> - IRIns *newref = IR(ref);
> - if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO)
> - return 0; /* Conflict. */
> - ref = newref->prev;
> - }
> - return fwd_aa_tab_clear(J, lim, ta);
> -}
> -
> /* ASTORE/HSTORE elimination. */
> TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J)
> {
> diff --git a/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua b/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua
> new file mode 100644
> index 00000000..e662e0cc
> --- /dev/null
> +++ b/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua
> @@ -0,0 +1,181 @@
> +local tap = require('tap')
> +
> +-- Test file to demonstrate LuaJIT incorrect optimizations across
> +-- the `table.clear()` call.
> +-- See also: https://github.com/LuaJIT/LuaJIT/issues/792.
> +
> +local test = tap.test('lj-792-hrefk-table-clear'):skipcond({
> + ['Test requires JIT enabled'] = not jit.status(),
> +})
> +local table_clear = require('table.clear')
> +
> +test:plan(7)
> +
> +local NITERATIONS = 4
> +local MAGIC = 42
> +
> +local function test_aref_fwd_tnew(tab_number)
> + local field_value_after_clear
> + for i = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + -- Initialize the first field to work with the array part.
> + local tab = {i}
> + -- Use an additional table to alias the created table with the
> + -- `1` key.
> + local tab_array = {tab, {0}}
> + -- AREF to be forwarded.
> + tab[1] = MAGIC
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since table is cleared.
> + field_value_after_clear = tab[1]
> + end
> + return field_value_after_clear
> +end
> +
> +local function test_aref_fwd_tdup(tab_number)
> + local field_value_after_clear
> + for _ = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + local tab = {nil}
> + -- Use an additional table to alias the created table with the
> + -- `1` key.
> + local tab_array = {tab, {0}}
> + -- AREF to be forwarded.
> + tab[1] = MAGIC
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since table is cleared.
> + field_value_after_clear = tab[1]
> + end
> + return field_value_after_clear
> +end
> +
> +local function test_href_fwd_tnew(tab_number)
> + local field_value_after_clear
> + for _ = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + local tab = {}
> + -- Use an additional table to alias the created table with the
> + -- `8` key.
> + local tab_array = {tab, {0}}
> + -- HREF to be forwarded. Use 8 to be in the hash part.
> + tab[8] = MAGIC
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since table is cleared.
> + field_value_after_clear = tab[8]
> + end
> + return field_value_after_clear
> +end
> +
> +local function test_href_fwd_tdup(tab_number)
> + local field_value_after_clear
> + for _ = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + local tab = {nil}
> + -- Use an additional table to alias the created table with the
> + -- `8` key.
> + local tab_array = {tab, {0}}
> + -- HREF to be forwarded. Use 8 to be in the hash part.
> + tab[8] = MAGIC
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since table is cleared.
> + field_value_after_clear = tab[8]
> + end
> + return field_value_after_clear
> +end
> +
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with a clearing not-interesting table.
> +test_aref_fwd_tnew(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- AREF.
> +test:is(test_aref_fwd_tnew(1), nil, 'AREF forward from TNEW')
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with a clearing not-interesting table.
> +test_aref_fwd_tdup(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- AREF.
> +test:is(test_aref_fwd_tdup(1), nil, 'AREF forward from TDUP')
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with a clearing not-interesting table.
> +test_href_fwd_tnew(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- HREF.
> +test:is(test_href_fwd_tnew(1), nil, 'HREF forward from TNEW')
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with a clearing not-interesting table.
> +test_href_fwd_tdup(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- HREF.
> +test:is(test_href_fwd_tdup(1), nil, 'HREF forward from TDUP')
> +
> +local function test_not_forwarded_hrefk_val_from_newref(tab_number)
> + local field_value_after_clear
> + for _ = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + local tab = {}
> + -- NEWREF to be forwarded.
> + tab.hrefk = MAGIC
> + -- Use an additional table to alias the created table with the
> + -- `hrefk` key.
> + local tab_array = {tab, {hrefk = 0}}
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since it is cleared.
> + field_value_after_clear = tab.hrefk
> + end
> + return field_value_after_clear
> +end
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with a clearing not-interesting table.
> +test_not_forwarded_hrefk_val_from_newref(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- HREFK.
> +local value_from_cleared_tab = test_not_forwarded_hrefk_val_from_newref(1)
> +
> +test:is(value_from_cleared_tab, nil,
> + 'not forward the field value across table.clear')
> +
> +local function test_not_dropped_guard_on_hrefk(tab_number)
> + local tab, field_value_after_clear
> + for _ = 1, NITERATIONS do
> + -- Create a table on trace to make the optimization work.
> + tab = {hrefk = MAGIC}
> + -- Use an additional table to alias the created table with the
> + -- `hrefk` key.
> + local tab_array = {tab, {hrefk = 0}}
> + table_clear(tab_array[tab_number])
> + -- It should be `nil`, since it is cleared.
> + -- If the guard is dropped for HREFK, the value from the TDUP
> + -- table is taken instead, without the type check. This leads
> + -- to incorrect (swapped) returned values.
> + field_value_after_clear = tab.hrefk
> + tab.hrefk = MAGIC
> + end
> + return field_value_after_clear, tab.hrefk
> +end
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +-- First compile the trace with clearing not interesting table.
> +test_not_dropped_guard_on_hrefk(2)
> +-- Now run the trace with the clearing table, from which we take
> +-- HREFK.
> +local field_value_after_clear, tab_hrefk = test_not_dropped_guard_on_hrefk(1)
> +
> +test:is(field_value_after_clear, nil, 'correct field value after table.clear')
> +test:is(tab_hrefk, MAGIC, 'correct value set in the table that was cleared')
> +
> +test:done(true)
next prev parent reply other threads:[~2023-11-22 15:25 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-09 12:26 Sergey Kaplun via Tarantool-patches
2023-11-10 12:49 ` Maxim Kokryashkin via Tarantool-patches
2023-11-13 7:37 ` Sergey Kaplun via Tarantool-patches
2023-11-15 11:46 ` Maxim Kokryashkin via Tarantool-patches
2023-11-22 15:25 ` Sergey Bronnikov via Tarantool-patches [this message]
2024-01-10 8:51 ` Igor Munkin 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=b9fef8f2-bea3-4369-9bd4-f5a46ce2edae@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 HREFK forwarding vs. table.clear().' \
/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