[Tarantool-patches] [PATCH luajit] Detect inconsistent renames even in the presence of sunk values.

[Sergey Ostanevich]

Hi! Thanks for the patch!

Just a small nit to the test. I won’t comment Mike’s code :)

LGTM

Sergos

> On 24 Jul 2021, at 20:23, Igor Munkin <imun at tarantool.org> wrote:
> 
> From: Mike Pall <mike>
> 
> Reported by Igor Munkin.
> 
> (cherry picked from commit 33e3f4badfde8cd9c202cedd1f4ed9275bc92e7d)
> 
> Side exits with the same exitno use the same snapshot for restoring
> guest stack values. This obliges all guards related to the particular
> snapshot use the same RegSP mapping for the values to be restored at the
> trace exit. RENAME emitted prior to the guard for the same snapshot
> leads to the aforementioned invariant violation. The easy way to save
> the snapshot consistency is spilling the renamed IR reference, that is
> done in scope of <asm_snap_checkrename>.
> 
> However, the previous <asm_snap_checkrename> implementation considers
> only the IR references explicitly mentioned in the snapshot. E.g. if
> there is a sunk[1] object to be restored at the trace exit, and the
> renamed reference is a *STORE to that object, the spill slot is not
> allocated. As a result an invalid value is stored while unsinking that
> object at all corresponding side exits prior to the emitted renaming.
> 
> To handle also those IR references implicitly used in the snapshot, all
> non-constant and non-sunk references are added to the Bloom filter (it's
> worth to mention that two hash functions are used to reduce collisions
> for the cases when the number of IR references emitted between two
> different snapshots exceeds the filter size). New <asm_snap_checkrename>
> implementation tests whether the renamed IR reference is in the filter
> and forces a spill slot for it as a result.
> 
> [1]: http://wiki.luajit.org/Allocation-Sinking-Optimization
> 
> Igor Munkin:
> * added the description and the test for the problem
> 
> Resolves tarantool/tarantool#5118
> Follows up tarantool/tarantool#4252
> 
> Signed-off-by: Igor Munkin <imun at tarantool.org>
> ---
> 
> Related issues:
> * https://github.com/tarantool/tarantool/issues/5118
> * https://github.com/tarantool/tarantool/issues/4252
> * https://github.com/LuaJIT/LuaJIT/issues/584
> Branch: https://github.com/tarantool/luajit/tree/imun/lj-584-bad-renames-for-sunk-values
> CI: https://github.com/tarantool/tarantool/commit/b35e2ee
> 
> src/lj_asm.c                                  | 25 ++++---
> ...j-584-bad-renames-for-sunk-values.test.lua | 69 +++++++++++++++++++
> 2 files changed, 81 insertions(+), 13 deletions(-)
> create mode 100644 test/tarantool-tests/lj-584-bad-renames-for-sunk-values.test.lua
> 
> diff --git a/src/lj_asm.c b/src/lj_asm.c
> index c2cf5a95..9267448e 100644
> --- a/src/lj_asm.c
> +++ b/src/lj_asm.c
> @@ -72,6 +72,7 @@ typedef struct ASMState {
>   IRRef snaprename;	/* Rename highwater mark for snapshot check. */
>   SnapNo snapno;	/* Current snapshot number. */
>   SnapNo loopsnapno;	/* Loop snapshot number. */
> +  BloomFilter snapfilt1, snapfilt2;	/* Filled with snapshot refs. */
> 
>   IRRef fuseref;	/* Fusion limit (loopref, 0 or FUSE_DISABLED). */
>   IRRef sectref;	/* Section base reference (loopref or 0). */
> @@ -876,7 +877,10 @@ 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) && (!(ra_used(ir) || ir->r == RID_SUNK))) {
> +  if (!irref_isk(ref) && ir->r != RID_SUNK) {
> +    bloomset(as->snapfilt1, ref);
> +    bloomset(as->snapfilt2, hashrot(ref, ref + HASH_BIAS));
> +    if (ra_used(ir)) return;

>     if (ir->r == RID_SINK) {
>       ir->r = RID_SUNK;
> #if LJ_HASFFI
> @@ -933,6 +937,7 @@ static void asm_snap_alloc(ASMState *as)
>   SnapShot *snap = &as->T->snap[as->snapno];
>   SnapEntry *map = &as->T->snapmap[snap->mapofs];
>   MSize n, nent = snap->nent;
> +  as->snapfilt1 = as->snapfilt2 = 0;
>   for (n = 0; n < nent; n++) {
>     SnapEntry sn = map[n];
>     IRRef ref = snap_ref(sn);
> @@ -955,18 +960,12 @@ static void asm_snap_alloc(ASMState *as)
> */
> static int asm_snap_checkrename(ASMState *as, IRRef ren)
> {
> -  SnapShot *snap = &as->T->snap[as->snapno];
> -  SnapEntry *map = &as->T->snapmap[snap->mapofs];
> -  MSize n, nent = snap->nent;
> -  for (n = 0; n < nent; n++) {
> -    SnapEntry sn = map[n];
> -    IRRef ref = snap_ref(sn);
> -    if (ref == ren || (LJ_SOFTFP && (sn & SNAP_SOFTFPNUM) && ++ref == ren)) {
> -      IRIns *ir = IR(ref);
> -      ra_spill(as, ir);  /* Register renamed, so force a spill slot. */
> -      RA_DBGX((as, "snaprensp $f $s", ref, ir->s));
> -      return 1;  /* Found. */
> -    }
> +  if (bloomtest(as->snapfilt1, ren) &&
> +      bloomtest(as->snapfilt2, hashrot(ren, ren + HASH_BIAS))) {
> +    IRIns *ir = IR(ren);
> +    ra_spill(as, ir);  /* Register renamed, so force a spill slot. */
> +    RA_DBGX((as, "snaprensp $f $s", ren, ir->s));
> +    return 1;  /* Found. */
>   }
>   return 0;  /* Not found. */
> }
> diff --git a/test/tarantool-tests/lj-584-bad-renames-for-sunk-values.test.lua b/test/tarantool-tests/lj-584-bad-renames-for-sunk-values.test.lua
> new file mode 100644
> index 00000000..8aad3438
> --- /dev/null
> +++ b/test/tarantool-tests/lj-584-bad-renames-for-sunk-values.test.lua
> @@ -0,0 +1,69 @@
> +local tap = require('tap')
> +
> +local test = tap.test('lj-584-bad-renames-for-sunk-values')
> +test:plan(1)
> +
> +-- Test file to demonstrate LuaJIT assembler misbehaviour.
> +-- For more info, proceed to the issues:
> +-- * https://github.com/LuaJIT/LuaJIT/issues/584
> +-- * https://github.com/tarantool/tarantool/issues/4252
> +
> +----- Related part of luafun.lua. --------------------------------
> +
> +local iterator_mt = {
> +  __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, chain_gen_r2
> +
> +chain_gen_r2 = function(param, state, state_x, ...)
> +  if state_x ~= nil then return { state[1], state_x }, ...  end
> +  local i = state[1] + 1
> +  if param[3 * i - 1] == nil then return nil end
> +  return chain_gen_r1(param, { i, param[3 * i] })
> +end
> +
> +chain_gen_r1 = function(param, state)
> +  local i, state_x = 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_x))
> +end
> +
> +local chain = function(...)
> +  local param = { }
> +  for i = 1, select('#', ...) do
> +    -- Put gen, param, state into param table.
> +    param[3 * i - 2], param[3 * i - 1], param[3 * i]
> +      = wrap(ipairs(select(i, ...)))
> +  end
> +  return wrap(chain_gen_r1, param, { 1, param[3] })
> +end
> +
> +----- Reproducer. ------------------------------------------------
> +
> +jit.opt.start(3, 'hotloop=3')

I don’t like both numbers here. opt_level is 3 by default - why bother setting it?
And the second one should be factored out as an argument for both opt.start and the
loop below?

> +
> +xpcall(function()
> +  for _ = 1, 3 do
> +    local gen_x, param_x, state_x = chain({ 'a', 'b', 'c' }, { 'q', 'w', 'e' })
> +    while true do
> +      state_x = gen_x(param_x, state_x)
> +      if state_x == nil then break end
> +    end
> +  end
> +  test:ok('All emitted RENAMEs are fine')
> +end, function()
> +  test:fail('Invalid Lua stack has been restored')
> +end)
> +
> +os.exit(test:check() and 0 or 1)
> -- 
> 2.25.0
>