From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-sn1nam02on0137.outbound.protection.outlook.com ([104.47.36.137]:63678 "EHLO NAM02-SN1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1032234AbeCAPaa (ORCPT ); Thu, 1 Mar 2018 10:30:30 -0500 From: Sasha Levin To: "stable@vger.kernel.org" , "stable-commits@vger.kernel.org" CC: Joe Thornber , Mike Snitzer , Sasha Levin Subject: [added to the 4.1 stable tree] dm btree: fix serious bug in btree_split_beneath() Date: Thu, 1 Mar 2018 15:24:30 +0000 Message-ID: <20180301152116.1486-196-alexander.levin@microsoft.com> References: <20180301152116.1486-1-alexander.levin@microsoft.com> In-Reply-To: <20180301152116.1486-1-alexander.levin@microsoft.com> Content-Language: en-US Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: stable-owner@vger.kernel.org List-ID: From: Joe Thornber This patch has been added to the 4.1 stable tree. If you have any objections, please let us know. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D [ Upstream commit bc68d0a43560e950850fc69b58f0f8254b28f6d6 ] When inserting a new key/value pair into a btree we walk down the spine of btree nodes performing the following 2 operations: i) space for a new entry ii) adjusting the first key entry if the new key is lower than any in the= node. If the _root_ node is full, the function btree_split_beneath() allocates 2 = new nodes, and redistibutes the root nodes entries between them. The root node= is left with 2 entries corresponding to the 2 new nodes. btree_split_beneath() then adjusts the spine to point to one of the two new children. This means the first key is never adjusted if the new key was lo= wer, ie. operation (ii) gets missed out. This can result in the new key being 'lost' for a period; until another low valued key is inserted that will unc= over it. This is a serious bug, and quite hard to make trigger in normal use. A reproducing test case ("thin create devices-in-reverse-order") is available as part of the thin-provision-tools project: https://github.com/jthornber/thin-provisioning-tools/blob/master/function= al-tests/device-mapper/dm-tests.scm#L593 Fix the issue by changing btree_split_beneath() so it no longer adjusts the spine. Instead it unlocks both the new nodes, and lets the main loop in btree_insert_raw() relock the appropriate one and make any neccessary adjustments. Cc: stable@vger.kernel.org Reported-by: Monty Pavel Signed-off-by: Joe Thornber Signed-off-by: Mike Snitzer Signed-off-by: Sasha Levin --- drivers/md/persistent-data/dm-btree.c | 19 ++----------------- 1 file changed, 2 insertions(+), 17 deletions(-) diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-= data/dm-btree.c index 360c22d44647..f2a8e4c69d9f 100644 --- a/drivers/md/persistent-data/dm-btree.c +++ b/drivers/md/persistent-data/dm-btree.c @@ -572,23 +572,8 @@ static int btree_split_beneath(struct shadow_spine *s,= uint64_t key) pn->keys[1] =3D rn->keys[0]; memcpy_disk(value_ptr(pn, 1), &val, sizeof(__le64)); =20 - /* - * rejig the spine. This is ugly, since it knows too - * much about the spine - */ - if (s->nodes[0] !=3D new_parent) { - unlock_block(s->info, s->nodes[0]); - s->nodes[0] =3D new_parent; - } - if (key < le64_to_cpu(rn->keys[0])) { - unlock_block(s->info, right); - s->nodes[1] =3D left; - } else { - unlock_block(s->info, left); - s->nodes[1] =3D right; - } - s->count =3D 2; - + unlock_block(s->info, left); + unlock_block(s->info, right); return 0; } =20 --=20 2.14.1