From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id DB0D62FD1F for ; Sat, 18 May 2019 08:38:28 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id z_hOktr2Y3Fd for ; Sat, 18 May 2019 08:38:28 -0400 (EDT) Received: from mail-lj1-f196.google.com (mail-lj1-f196.google.com [209.85.208.196]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 777002FCCC for ; Sat, 18 May 2019 08:38:28 -0400 (EDT) Received: by mail-lj1-f196.google.com with SMTP id h21so8534579ljk.13 for ; Sat, 18 May 2019 05:38:28 -0700 (PDT) Date: Sat, 18 May 2019 15:38:25 +0300 From: Cyrill Gorcunov Subject: [tarantool-patches] [PATCH 3/3] bugfix: LuaJIT tables' hash chains might get corrupted leading to infinite loops while fetching, missing keys, and etc. Message-ID: <20190518123825.GA2497@uranus.lan> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20190518123356.15780-1-gorcunov@gmail.com> Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: tml Cc: Alexander Turenko , Kirill Yukhin , Cyrill Gorcunov From: "Yichun Zhang (agentzh)" 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