Tarantool development patches archive
 help / color / mirror / Atom feed
From: Cyrill Gorcunov <gorcunov@gmail.com>
To: tml <tarantool-patches@freelists.org>
Subject: [tarantool-patches] [PATCH] Fix rechaining of pseudo-resurrected string keys.
Date: Wed,  8 May 2019 15:10:20 +0300	[thread overview]
Message-ID: <20190508121021.14968-3-gorcunov@gmail.com> (raw)
In-Reply-To: <20190508121021.14968-1-gorcunov@gmail.com>

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.
---
 src/lj_tab.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/src/lj_tab.c b/src/lj_tab.c
index 50f447e..f2f3c0b 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -457,6 +457,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

  parent reply	other threads:[~2019-05-08 12:11 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-05-08 12:10 [tarantool-patches] [PATCH 0/2] luajit: Backports fixes from vanilla repo Cyrill Gorcunov
2019-05-08 12:10 ` [tarantool-patches] [PATCH 1/2] Fix overflow of snapshot map offset Cyrill Gorcunov
2019-05-08 12:10 ` Cyrill Gorcunov [this message]
2019-05-08 12:10 ` [tarantool-patches] [PATCH 2/2] Fix rechaining of pseudo-resurrected string keys Cyrill Gorcunov
2019-05-08 12:43   ` [tarantool-patches] " Cyrill Gorcunov

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=20190508121021.14968-3-gorcunov@gmail.com \
    --to=gorcunov@gmail.com \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [tarantool-patches] [PATCH] Fix rechaining of pseudo-resurrected string keys.' \
    /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