[tarantool-patches] [PATCH 0/3] luajit: Fixes in sake of #4171

[tarantool-patches] [PATCH 0/3] luajit: Fixes in sake of #4171

[Cyrill Gorcunov]

These are backports from openresty/luajit2 repo, should
help for #4171, but requires intensive testing.

Mike Pall (2):
  Fix overflow of snapshot map offset.
  Fix rechaining of pseudo-resurrected string keys.

Yichun Zhang (agentzh) (1):
  bugfix: LuaJIT tables' hash chains might get corrupted leading to
    infinite loops while fetching, missing keys, and etc.

 src/lj_jit.h      | 10 +++----
 src/lj_opt_loop.c |  8 +++---
 src/lj_snap.c     |  6 ++---
 src/lj_tab.c      | 66 ++++++++++++++++++++++++++++++++++++++++-------
 4 files changed, 69 insertions(+), 21 deletions(-)

-- 
2.20.1

[tarantool-patches] [PATCH 1/3] Fix overflow of snapshot map offset.

[Cyrill Gorcunov]

From: Mike Pall <mike>

Thanks to Yichun Zhang.

backport https://github.com/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..3ff8dd4 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 + 1 + J->framedepth);
 }
 
 /* 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 2/3] 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 https://github.com/openresty/luajit2/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 3/3] 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.

gorcunov@:
backport https://github.com/openresty/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] Re: [PATCH 0/3] luajit: Fixes in sake of #4171

[Alexander Turenko]

Can we backport related tests too?

At least I see this one around:
https://github.com/openresty/luajit2-test-suite/pull/7/files

WBR, Alexander Turenko.

On Sat, May 18, 2019 at 03:33:53PM +0300, Cyrill Gorcunov wrote:
> These are backports from openresty/luajit2 repo, should
> help for #4171, but requires intensive testing.
> 
> Mike Pall (2):
>   Fix overflow of snapshot map offset.
>   Fix rechaining of pseudo-resurrected string keys.
> 
> Yichun Zhang (agentzh) (1):
>   bugfix: LuaJIT tables' hash chains might get corrupted leading to
>     infinite loops while fetching, missing keys, and etc.
> 
>  src/lj_jit.h      | 10 +++----
>  src/lj_opt_loop.c |  8 +++---
>  src/lj_snap.c     |  6 ++---
>  src/lj_tab.c      | 66 ++++++++++++++++++++++++++++++++++++++++-------
>  4 files changed, 69 insertions(+), 21 deletions(-)
> 
> -- 
> 2.20.1
> 
> 

[tarantool-patches] Re: [PATCH 0/3] luajit: Fixes in sake of #4171

[Cyrill Gorcunov]

On Sun, May 19, 2019 at 09:13:04PM +0300, Alexander Turenko wrote:
> Can we backport related tests too?
> 
> At least I see this one around:
> https://github.com/openresty/luajit2-test-suite/pull/7/files

Sure, I'll take a look. But to not mess with this series I'll
send them as separate on top.