Re: [Tarantool-patches] [PATCH luajit] Fix HREFK forwarding vs. table.clear().

[Sergey Bronnikov via Tarantool-patches <tarantool-patches@dev.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)