[tarantool-patches] [PATCH v2 0/4] luajit: Bacport patches from openrusty

[tarantool-patches] [PATCH v2 0/4] luajit: Bacport patches from openrusty

[Cyrill Gorcunov]

This series should help us with https://github.com/tarantool/tarantool/issues/4171

Note the first three patches are for our luajit submodule, the last
one is for tarantool to test the changes.

Part-of #4171
-- 
2.20.1

[tarantool-patches] [PATCH luajit v2 1/4] Fix overflow of snapshot map offset.

[Cyrill Gorcunov]

Backport of openresty/luajit2
commit 380e4409a70725df85034f02c968b6ebd7a5e513

Part-of #4171
---
 src/lj_jit.h      | 10 +++++-----
 src/lj_opt_loop.c |  8 ++++----
 src/lj_snap.c     |  6 +++---
 3 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/src/lj_jit.h b/src/lj_jit.h
index 92054e3..7eb3d2a 100644
--- a/src/lj_jit.h
+++ b/src/lj_jit.h
@@ -160,7 +160,7 @@ typedef uint32_t MCode;
 
 /* Stack snapshot header. */
 typedef struct SnapShot {
-  uint16_t mapofs;	/* Offset into snapshot map. */
+  uint32_t mapofs;	/* Offset into snapshot map. */
   IRRef1 ref;		/* First IR ref for this snapshot. */
   uint8_t nslots;	/* Number of valid slots. */
   uint8_t topslot;	/* Maximum frame extent. */
@@ -227,8 +227,7 @@ typedef enum {
 /* Trace object. */
 typedef struct GCtrace {
   GCHeader;
-  uint8_t topslot;	/* Top stack slot already checked to be allocated. */
-  uint8_t linktype;	/* Type of link. */
+  uint16_t nsnap;	/* Number of snapshots. */
   IRRef nins;		/* Next IR instruction. Biased with REF_BIAS. */
 #if LJ_GC64
   uint32_t unused_gc64;
@@ -236,8 +235,7 @@ typedef struct GCtrace {
   GCRef gclist;
   IRIns *ir;		/* IR instructions/constants. Biased with REF_BIAS. */
   IRRef nk;		/* Lowest IR constant. Biased with REF_BIAS. */
-  uint16_t nsnap;	/* Number of snapshots. */
-  uint16_t nsnapmap;	/* Number of snapshot map elements. */
+  uint32_t nsnapmap;	/* Number of snapshot map elements. */
   SnapShot *snap;	/* Snapshot array. */
   SnapEntry *snapmap;	/* Snapshot map. */
   GCRef startpt;	/* Starting prototype. */
@@ -254,6 +252,8 @@ typedef struct GCtrace {
   TraceNo1 nextroot;	/* Next root trace for same prototype. */
   TraceNo1 nextside;	/* Next side trace of same root trace. */
   uint8_t sinktags;	/* Trace has SINK tags. */
+  uint8_t topslot;	/* Top stack slot already checked to be allocated. */
+  uint8_t linktype;	/* Type of link. */
   uint8_t unused1;
 #ifdef LUAJIT_USE_GDBJIT
   void *gdbjit_entry;	/* GDB JIT entry. */
diff --git a/src/lj_opt_loop.c b/src/lj_opt_loop.c
index 04c6d06..441b8ad 100644
--- a/src/lj_opt_loop.c
+++ b/src/lj_opt_loop.c
@@ -223,7 +223,7 @@ static void loop_subst_snap(jit_State *J, SnapShot *osnap,
   }
   J->guardemit.irt = 0;
   /* Setup new snapshot. */
-  snap->mapofs = (uint16_t)nmapofs;
+  snap->mapofs = (uint32_t)nmapofs;
   snap->ref = (IRRef1)J->cur.nins;
   snap->nslots = nslots;
   snap->topslot = osnap->topslot;
@@ -251,7 +251,7 @@ static void loop_subst_snap(jit_State *J, SnapShot *osnap,
   nmap += nn;
   while (omap < nextmap)  /* Copy PC + frame links. */
     *nmap++ = *omap++;
-  J->cur.nsnapmap = (uint16_t)(nmap - J->cur.snapmap);
+  J->cur.nsnapmap = (uint32_t)(nmap - J->cur.snapmap);
 }
 
 typedef struct LoopState {
@@ -369,7 +369,7 @@ static void loop_unroll(LoopState *lps)
     }
   }
   if (!irt_isguard(J->guardemit))  /* Drop redundant snapshot. */
-    J->cur.nsnapmap = (uint16_t)J->cur.snap[--J->cur.nsnap].mapofs;
+    J->cur.nsnapmap = (uint32_t)J->cur.snap[--J->cur.nsnap].mapofs;
   lua_assert(J->cur.nsnapmap <= J->sizesnapmap);
   *psentinel = J->cur.snapmap[J->cur.snap[0].nent];  /* Restore PC. */
 
@@ -383,7 +383,7 @@ static void loop_undo(jit_State *J, IRRef ins, SnapNo nsnap, MSize nsnapmap)
   SnapShot *snap = &J->cur.snap[nsnap-1];
   SnapEntry *map = J->cur.snapmap;
   map[snap->mapofs + snap->nent] = map[J->cur.snap[0].nent];  /* Restore PC. */
-  J->cur.nsnapmap = (uint16_t)nsnapmap;
+  J->cur.nsnapmap = (uint32_t)nsnapmap;
   J->cur.nsnap = nsnap;
   J->guardemit.irt = 0;
   lj_ir_rollback(J, ins);
diff --git a/src/lj_snap.c b/src/lj_snap.c
index bb063c2..18ce715 100644
--- a/src/lj_snap.c
+++ b/src/lj_snap.c
@@ -161,11 +161,11 @@ static void snapshot_stack(jit_State *J, SnapShot *snap, MSize nsnapmap)
   nent = snapshot_slots(J, p, nslots);
   snap->nent = (uint8_t)nent;
   nent += snapshot_framelinks(J, p + nent, &snap->topslot);
-  snap->mapofs = (uint16_t)nsnapmap;
+  snap->mapofs = (uint32_t)nsnapmap;
   snap->ref = (IRRef1)J->cur.nins;
   snap->nslots = (uint8_t)nslots;
   snap->count = 0;
-  J->cur.nsnapmap = (uint16_t)(nsnapmap + nent);
+  J->cur.nsnapmap = (uint32_t)(nsnapmap + nent);
 }
 
 /* Add or merge a snapshot. */
@@ -326,7 +326,7 @@ void lj_snap_shrink(jit_State *J)
   snap->nent = (uint8_t)m;
   nlim = J->cur.nsnapmap - snap->mapofs - 1;
   while (n <= nlim) map[m++] = map[n++];  /* Move PC + frame links down. */
-  J->cur.nsnapmap = (uint16_t)(snap->mapofs + m);  /* Free up space in map. */
+  J->cur.nsnapmap = (uint32_t)(snap->mapofs + m);  /* Free up space in map. */
 }
 
 /* -- Snapshot access ----------------------------------------------------- */
-- 
2.20.1

[tarantool-patches] [PATCH luajit v2 2/4] Fix rechaining of pseudo-resurrected string keys.

[Cyrill Gorcunov]

From: Mike Pall <mike>

This is a serious bug. But extremely hard to reproduce, so it went
undetected for 8 years. One needs two resurrections with different
main nodes, which are both in a hash chain which gets relinked on
key insertion where the colliding node is in a non-main position. Phew.

Thanks to lbeiming.

Backport of @openrusty/liajit2
commit 046129dbdda5261c1b17469a2895a113d14c070a

Part-of #4171
---
 src/lj_tab.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/src/lj_tab.c b/src/lj_tab.c
index 47c0cfd..c51666d 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -491,6 +491,29 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
 	  freenode->next = nn->next;
 	  nn->next = n->next;
 	  setmref(n->next, nn);
+	  /*
+	  ** Rechaining a resurrected string key creates a new dilemma:
+	  ** Another string key may have originally been resurrected via
+	  ** _any_ of the previous nodes as a chain anchor. Including
+	  ** a node that had to be moved, which makes them unreachable.
+	  ** It's not feasible to check for all previous nodes, so rechain
+	  ** any string key that's currently in a non-main positions.
+	  */
+	  while ((nn = nextnode(freenode))) {
+	    if (tvisstr(&nn->key) && !tvisnil(&nn->val)) {
+	      Node *mn = hashstr(t, strV(&nn->key));
+	      if (mn != freenode) {
+		freenode->next = nn->next;
+		nn->next = mn->next;
+		setmref(mn->next, nn);
+	      } else {
+		freenode = nn;
+	      }
+	    } else {
+	      freenode = nn;
+	    }
+	  }
+	  break;
 	} else {
 	  freenode = nn;
 	}
-- 
2.20.1

[tarantool-patches] [PATCH luajit v2 3/4] bugfix: LuaJIT tables' hash chains might get corrupted leading to infinite loops while fetching, missing keys, and etc.

[Cyrill Gorcunov]

From: "Yichun Zhang (agentzh)" <yichun@openresty.com>

Thanks Julien Desgats for the report and Peter Cawley for the patch.

See LuaJIT/LuaJIT#494 for the full discussion on the issues and fixes.

The test covering this bug was submitted to the openresty/luajit2-test-suite
repo as commit ce2c916d55.

Backport of @openrusty/luajit2
commit 9e338fe1cd854065cc9b29b2a863cc3c742a3404

Part-of #4171
---
 src/lj_tab.c | 81 ++++++++++++++++++++++++++++++++++------------------
 1 file changed, 53 insertions(+), 28 deletions(-)

diff --git a/src/lj_tab.c b/src/lj_tab.c
index c51666d..ff216f3 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -474,6 +474,7 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
     lua_assert(freenode != &G(L)->nilnode);
     collide = hashkey(t, &n->key);
     if (collide != n) {  /* Colliding node not the main node? */
+      Node *nn;
       while (noderef(collide->next) != n)  /* Find predecessor. */
 	collide = nextnode(collide);
       setmref(collide->next, freenode);  /* Relink chain. */
@@ -483,39 +484,63 @@ TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
       freenode->next = n->next;
       setmref(n->next, NULL);
       setnilV(&n->val);
-      /* Rechain pseudo-resurrected string keys with colliding hashes. */
-      while (nextnode(freenode)) {
-	Node *nn = nextnode(freenode);
-	if (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
-	    hashstr(t, strV(&nn->key)) == n) {
-	  freenode->next = nn->next;
-	  nn->next = n->next;
-	  setmref(n->next, nn);
-	  /*
-	  ** Rechaining a resurrected string key creates a new dilemma:
-	  ** Another string key may have originally been resurrected via
-	  ** _any_ of the previous nodes as a chain anchor. Including
-	  ** a node that had to be moved, which makes them unreachable.
-	  ** It's not feasible to check for all previous nodes, so rechain
-	  ** any string key that's currently in a non-main positions.
-	  */
-	  while ((nn = nextnode(freenode))) {
-	    if (tvisstr(&nn->key) && !tvisnil(&nn->val)) {
-	      Node *mn = hashstr(t, strV(&nn->key));
-	      if (mn != freenode) {
-		freenode->next = nn->next;
-		nn->next = mn->next;
-		setmref(mn->next, nn);
+      /*
+      ** Nodes after n might have n as their main node, and need rechaining
+      ** back onto n. We make use of the following property of tables: for all
+      ** nodes m, at least one of the following four statements is true:
+      **  1. tvisnil(&m->key)  NB: tvisnil(&m->val) is a stronger statement
+      **  2. tvisstr(&m->key)
+      **  3. tvisstr(&main(m)->key)
+      **  4. main(m) == main(main(m))
+      ** Initially, we need to rechain any nn which has main(nn) == n. As
+      ** main(n) != n (because collide != n earlier), main(nn) == n requires
+      ** either statement 2 or statement 3 to be true about nn.
+      */
+      if (!tvisstr(&n->key)) {
+	/* Statement 3 is not true, so only need to consider string keys. */
+	while ((nn = nextnode(freenode))) {
+	  if (tvisstr(&nn->key) && !tvisnil(&nn->val) &&
+	      hashstr(t, strV(&nn->key)) == n) {
+	    goto rechain;
+	  }
+	  freenode = nn;
+	}
+      } else {
+	/* Statement 3 is true, so need to consider all types of key. */
+	while ((nn = nextnode(freenode))) {
+	  if (!tvisnil(&nn->val) && hashkey(t, &nn->key) == n) {
+	  rechain:
+	    freenode->next = nn->next;
+	    nn->next = n->next;
+	    setmref(n->next, nn);
+	    /*
+	    ** Rechaining one node onto n creates a new dilemma: we now need
+	    ** to rechain any nn which has main(nn) == n OR has main(nn) equal
+	    ** to any node which has already been rechained. Furthermore, at
+	    ** least one of n and n->next will have a string key, so all types
+	    ** of nn key need to be considered. Rather than testing whether
+	    ** main(nn) definitely _is_ in the new chain, we test whether it
+	    ** might _not_ be in the old chain, and if so re-link it into
+	    ** the correct chain.
+	    */
+	    while ((nn = nextnode(freenode))) {
+	      if (!tvisnil(&nn->val)) {
+		Node *mn = hashkey(t, &nn->key);
+		if (mn != freenode && mn != nn) {
+		  freenode->next = nn->next;
+		  nn->next = mn->next;
+		  setmref(mn->next, nn);
+		} else {
+		  freenode = nn;
+		}
 	      } else {
 		freenode = nn;
 	      }
-	    } else {
-	      freenode = nn;
 	    }
+	    break;
+	  } else {
+	    freenode = nn;
 	  }
-	  break;
-	} else {
-	  freenode = nn;
 	}
       }
     } else {  /* Otherwise use free node. */
-- 
2.20.1

[tarantool-patches] [PATCH tarantool v2 4/4] test/luajit-tap: Add table_chain_bug_LuaJIT_494.test.lua

[Cyrill Gorcunov]

Backport of openresty/luajit2-test-suite
commit ce2c916d5582914edeb9499f487d9fa812632c5c

To test hash chain bug.

Part-of #4171
---
 .../table_chain_bug_LuaJIT_494.test.lua       | 178 ++++++++++++++++++
 1 file changed, 178 insertions(+)
 create mode 100755 test/luajit-tap/table_chain_bug_LuaJIT_494.test.lua

diff --git a/test/luajit-tap/table_chain_bug_LuaJIT_494.test.lua b/test/luajit-tap/table_chain_bug_LuaJIT_494.test.lua
new file mode 100755
index 000000000..06c0f0d29
--- /dev/null
+++ b/test/luajit-tap/table_chain_bug_LuaJIT_494.test.lua
@@ -0,0 +1,178 @@
+#!/usr/bin/env tarantool
+
+tap = require('tap')
+
+test = tap.test("494")
+test:plan(1)
+
+-- Test file to demonstrate Lua table hash chain bugs discussed in
+--     https://github.com/LuaJIT/LuaJIT/issues/494
+-- Credit: prepared by Peter Cawley here with minor edits:
+--     https://gist.github.com/corsix/1fc9b13a2dd5f3659417b62dd54d4500
+
+--- Plumbing
+ffi = require"ffi"
+ffi.cdef"char* strstr(const char*, const char*)"
+strstr = ffi.C.strstr
+cast = ffi.cast
+str_hash_offset = cast("uint32_t*", strstr("*", ""))[-2] == 1 and 3 or 2
+function str_hash(s)
+    return cast("uint32_t*", strstr(s, "")) - str_hash_offset
+end
+table_new = require"table.new"
+
+--- Prepare some objects
+victims = {}
+orig_hash = {}
+for c in ("abcdef"):gmatch"." do
+    v = c .. "{09add58a-13a4-44e0-a52c-d44d0f9b2b95}"
+    victims[c] = v
+    orig_hash[c] = str_hash(v)[0]
+end
+collectgarbage()
+
+do --- Basic version of the problem
+    for k, v in pairs(victims) do
+        str_hash(v)[0] = 0
+    end
+    t = table_new(0, 8)
+    -- Make chain a -> b -> c -> d, all with a as primary
+    t[victims.a] = true
+    t[victims.d] = true
+    t[victims.c] = true
+    t[victims.b] = true
+    -- Change c's primary to b, and d's primary to c
+    t[victims.d] = nil
+    t[victims.c] = nil
+    str_hash(victims.c)[0] = 5
+    str_hash(victims.d)[0] = 6
+    t[victims.c] = true
+    t[victims.d] = true
+    -- Insert something with b as primary
+    str_hash(victims.e)[0] = 5
+    t[victims.e] = true
+    -- Check for consistency
+    for c in ("abcde"):gmatch"." do
+        assert(t[victims[c]], c)
+    end
+end
+collectgarbage()
+
+do --- Just `mn != freenode` can lead to infinite loops
+    for k, v in pairs(victims) do
+        str_hash(v)[0] = 0
+    end
+    t = table_new(0, 8)
+    -- Make chain a -> b -> c -> d, all with a as primary
+    t[victims.a] = true
+    t[victims.d] = true
+    t[victims.c] = true
+    t[victims.b] = true
+    -- Change c's primary to b, and d's primary to d
+    t[victims.d] = nil
+    t[victims.c] = nil
+    str_hash(victims.c)[0] = 5
+    str_hash(victims.d)[0] = 7
+    t[victims.c] = true
+    t[victims.d] = true
+    -- Insert something with b as primary
+    str_hash(victims.e)[0] = 5
+    t[victims.e] = true
+    -- Insert something with d as primary (infinite lookup loop)
+    str_hash(victims.f)[0] = 7
+    t[victims.f] = true
+end
+collectgarbage()
+
+do --- Just `mn != nn` can lead to infinite loops
+    for k, v in pairs(victims) do
+        str_hash(v)[0] = 0
+    end
+    t = table_new(0, 8)
+    -- Make chain a -> b -> c -> d -> e, all with a as primary
+    t[victims.a] = true
+    t[victims.e] = true
+    t[victims.d] = true
+    t[victims.c] = true
+    t[victims.b] = true
+    -- Change c's primary to b, d's primary to d, and e's primary to d
+    t[victims.e] = nil
+    t[victims.d] = nil
+    t[victims.c] = nil
+    str_hash(victims.c)[0] = 4
+    str_hash(victims.d)[0] = 6
+    str_hash(victims.e)[0] = 6
+    t[victims.c] = true
+    t[victims.d] = true
+    t[victims.e] = true
+    -- Insert something with b as primary (infinite rechaining loop)
+    str_hash(victims.f)[0] = 4
+    t[victims.f] = true
+end
+
+for i = 0, 10 do --- Non-strings can need rechaining too
+    collectgarbage()
+
+    k = tonumber((("0x%xp-1074"):format(i)))
+    str_hash(victims.a)[0] = 0
+    str_hash(victims.b)[0] = 0
+    t = table_new(0, 4)
+    -- a -> b, both with a as primary
+    t[victims.a] = true
+    t[victims.b] = true
+    -- Change b's primary to b
+    t[victims.b] = nil
+    str_hash(victims.b)[0] = 3
+    t[victims.b] = true
+    -- Might get a -> b -> k, with k's primary as b
+    t[k] = true
+    -- Change b's primary to a
+    t[victims.b] = nil
+    str_hash(victims.b)[0] = 0
+    t[victims.b] = true
+    -- Insert something with b as primary
+    str_hash(victims.c)[0] = 3
+    t[victims.c] = true
+    -- Check for consistency
+    assert(t[k], i)
+end
+
+for i = 0, 10 do --- Non-strings can be moved to freenode
+    collectgarbage()
+
+    k = false
+    str_hash(victims.a)[0] = 0
+    str_hash(victims.b)[0] = 0
+    t = table_new(0, 4)
+    -- a -> k -> b, all with a as primary
+    t[victims.a] = true
+    t[victims.b] = true
+    t[k] = true
+    -- Change b's primary to k
+    t[victims.b] = nil
+    str_hash(victims.b)[0] = 2
+    t[victims.b] = true
+    -- Insert a non-string with primary of k
+    t[tonumber((("0x%xp-1074"):format(i)))] = true
+    -- Check for consistency
+    assert(t[victims.b], i)
+end
+collectgarbage()
+
+do --- Do not forget to advance freenode in the not-string case
+    t = table_new(0, 4)
+    -- Chain of colliding numbers
+    t[0x0p-1074] = true
+    t[0x4p-1074] = true
+    t[0x8p-1074] = true
+    -- Steal middle node of the chain to be a main node (infinite walking loop)
+    t[0x2p-1074] = true
+end
+collectgarbage()
+
+--- Restore interpreter invariants, just in case
+for c, v in pairs(victims) do
+    str_hash(v)[0] = orig_hash[c]
+end
+
+test:ok("PASS")
-- 
2.20.1

[tarantool-patches] Re: [PATCH v2 0/4] luajit: Bacport patches from openrusty

[Kirill Yukhin]

Hello,

On 22 May 22:05, Cyrill Gorcunov wrote:
> This series should help us with https://github.com/tarantool/tarantool/issues/4171
> 
> Note the first three patches are for our luajit submodule, the last
> one is for tarantool to test the changes.
> 
> Part-of #4171

I've checked the patchset into 1.10, 2.1 and master branches.

--
Regards, Kirill Yukhin

[tarantool-patches] Re: [PATCH v2 0/4] luajit: Bacport patches from openrusty

[Cyrill Gorcunov]

On Thu, May 23, 2019 at 01:32:53PM +0300, Kirill Yukhin wrote:
> Hello,
> 
> On 22 May 22:05, Cyrill Gorcunov wrote:
> > This series should help us with https://github.com/tarantool/tarantool/issues/4171
> > 
> > Note the first three patches are for our luajit submodule, the last
> > one is for tarantool to test the changes.
> > 
> > Part-of #4171
> 
> I've checked the patchset into 1.10, 2.1 and master branches.

Thanks! Lets wait it to pass all travis tests. Please ping me if
something goes wrong.

You know I've noticed that openrusy has another bug fix for that
named unsink 64bit pointers, I backported it too but didn't reveal
any difference when was running tests, so I desided to not include
it for a while.

[tarantool-patches] Re: [PATCH v2 0/4] luajit: Bacport patches from openrusty

[Kirill Yukhin]

On 23 May 13:37, Cyrill Gorcunov wrote:
> On Thu, May 23, 2019 at 01:32:53PM +0300, Kirill Yukhin wrote:
> > Hello,
> > 
> > On 22 May 22:05, Cyrill Gorcunov wrote:
> > > This series should help us with https://github.com/tarantool/tarantool/issues/4171
> > > 
> > > Note the first three patches are for our luajit submodule, the last
> > > one is for tarantool to test the changes.
> > > 
> > > Part-of #4171
> > 
> > I've checked the patchset into 1.10, 2.1 and master branches.

> You know I've noticed that openrusy has another bug fix for that
> named unsink 64bit pointers, I backported it too but didn't reveal
> any difference when was running tests, so I desided to not include
> it for a while.

I guess that's connected to GC64, which is enabled on OSX only for
Tarantool. IMHO, need to give it a try on OSX.

--
Regards, Kirill Yukhin

[tarantool-patches] Re: [PATCH v2 0/4] luajit: Bacport patches from openrusty

[Cyrill Gorcunov]

On Thu, May 23, 2019 at 01:57:03PM +0300, Kirill Yukhin wrote:
> 
> > You know I've noticed that openrusy has another bug fix for that
> > named unsink 64bit pointers, I backported it too but didn't reveal
> > any difference when was running tests, so I desided to not include
> > it for a while.
> 
> I guess that's connected to GC64, which is enabled on OSX only for
> Tarantool. IMHO, need to give it a try on OSX.

OK, I'll send it as a separate today evening.