From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id B7C126EC55; Sat, 24 Jul 2021 20:47:23 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org B7C126EC55 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1627148843; bh=Y94ckrY3pPy7uQBRu0FrERdBLb+DZ/z7k6uSDtbM0yg=; h=To:Date:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=k8bRKTYjXn/AK4iZlb47GqreWeL4YtRCm7ivpfQG0ygsvozF27Ir+ZwkMNAQVpGE7 bTwAFeFzs0oTGVC0C3MnrERHvyknIhx+8PXV9iRR+FvnggP4J0Frgup6jIGJq6rpcz JfcKm2Xoc0ppwdyfVdfaXG04HMhI3e/fnJhk05iQ= Received: from smtpng1.i.mail.ru (smtpng1.i.mail.ru [94.100.181.251]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 25F906EC55 for ; Sat, 24 Jul 2021 20:47:22 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 25F906EC55 Received: by smtpng1.m.smailru.net with esmtpa (envelope-from ) id 1m7Lk8-0005VD-Mq; Sat, 24 Jul 2021 20:47:21 +0300 To: Sergey Ostanevich , Sergey Kaplun Date: Sat, 24 Jul 2021 20:23:46 +0300 Message-Id: <5fdb4899061156f0fb4c53027d55f93be3a24759.1627144350.git.imun@tarantool.org> X-Mailer: git-send-email 2.25.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD941C43E597735A9C30288BCF456A452EC92BAB6D044D5CCDE182A05F538085040BEBEAE127FD50B259F039B44D0F6D76663471555607A63AAD3D5ADFD021C1F57 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE71BDE6A359BD5B800EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F790063761B0653E4D5FA7998638F802B75D45FF36EB9D2243A4F8B5A6FCA7DBDB1FC311F39EFFDF887939037866D6147AF826D897EAD1AF21590934768F1BD890AF15CE117882F4460429724CE54428C33FAD305F5C1EE8F4F765FC2EE5AD8F952D28FBA471835C12D1D9774AD6D5ED66289B52BA9C0B312567BB23117882F446042972877693876707352033AC447995A7AD18618001F51B5FD3F9D2E47CDBA5A96583BA9C0B312567BB231DD303D21008E29813377AFFFEAFD269A417C69337E82CC2E827F84554CEF50127C277FBC8AE2E8BA83251EDC214901ED5E8D9A59859A8B642416645EBD45DC2089D37D7C0E48F6C5571747095F342E88FB05168BE4CE3AF X-C1DE0DAB: C20DE7B7AB408E4181F030C43753B8186998911F362727C414F749A5E30D975C7941123239F78504499B4ECA478B0D7C801896BBA77CA8AB9C2B6934AE262D3EE7EAB7254005DCEDD844BA284C397EC11E0A4E2319210D9B64D260DF9561598F01A9E91200F654B0AEA200A0D3D80EA68E8E86DC7131B365E7726E8460B7C23C X-C8649E89: 4E36BF7865823D7055A7F0CF078B5EC49A30900B95165D34A246DFF68F0EE19E4F38AC05902C85F27788AF2C655516014F99E7732148E1690715110845E05C511D7E09C32AA3244C8B982225B17545DA7D34BF66FAA14045435BF7150578642F927AC6DF5659F194 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojbL9S8ysBdXgccGzra/FXaskG3or/CNw4 X-Mailru-Sender: 689FA8AB762F7393C37E3C1AEC41BA5D65109BA71F6E930D573ED38C2CB0D983A7C8D0F45F857DBFE9F1EFEE2F478337FB559BB5D741EB964C8C2C849690F8E70A04DAD6CC59E33667EA787935ED9F1B X-Mras: Ok Subject: [Tarantool-patches] [PATCH luajit] Detect inconsistent renames even in the presence of sunk values. X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Igor Munkin via Tarantool-patches Reply-To: Igor Munkin Cc: tarantool-patches@dev.tarantool.org Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" From: Mike Pall 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 . However, the previous 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 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 --- 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') + +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