linux-kernel - [dm-devel] [PATCH] Fix for find_lowest

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-Id: <1491530978-6215-1-git-send-email-vinraja@cs.stonybrook.edu>
Date:   Thu,  6 Apr 2017 22:09:38 -0400
From:   Vinothkumar Raja <vinraja@...stonybrook.edu>
To:     agk@...hat.com, snitzer@...hat.com
Cc:     dm-devel@...hat.com, shli@...nel.org, linux-raid@...r.kernel.org,
        linux-kernel@...r.kernel.org, ezk@...stonybrook.edu,
        npanpalia@...stonybrook.edu, tarasov@...ily.name,
        Vinothkumar Raja <vinraja@...stonybrook.edu>,
        Erez Zadok <ezk@....cs.sunysb.edu>
Subject: [dm-devel] [PATCH] Fix for find_lowest_key in dm-btree.c

We are working on dm-dedup which is a device-mapper's dedup target that 
provides transparent data deduplication of block devices. Every write 
coming to a dm-dedup instance is deduplicated against previously written 
data.  We’ve been working on this project for several years now. The 
Github link for the same is https://github.com/dmdedup. Detailed design 
and performance evaluation can be found in the following paper: 
http://www.fsl.cs.stonybrook.edu/docs/ols-dmdedup/dmdedup-ols14.pdf.

We are currently working on garbage collection for which we traverse our 
btrees from lowest key to highest key. While using find_lowest_key and 
find_highest_key, we noticed that find_lowest_key is giving incorrect 
results. While the function find_key traverses the btree correctly for 
finding the highest key, we found that there is an error in the way it 
traverses the btree for retrieving the lowest key. The find_lowest_key 
function fetches the first key of the rightmost block of the btree 
instead of fetching the first key from the leftmost block. This patch 
fixes the bug and gives us the correct result.  

Signed-off-by: Erez Zadok <ezk@....cs.sunysb.edu>
Signed-off-by: Vinothkumar Raja <vinraja@...stonybrook.edu>
Signed-off-by: Nidhi Panpalia <npanpalia@...stonybrook.edu>

---
 drivers/md/persistent-data/dm-btree.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-data/dm-btree.c
index 02e2ee0..83121d1 100644
--- a/drivers/md/persistent-data/dm-btree.c
+++ b/drivers/md/persistent-data/dm-btree.c
@@ -902,9 +902,12 @@ static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,
 		else
 			*result_key = le64_to_cpu(ro_node(s)->keys[0]);

-		if (next_block || flags & INTERNAL_NODE)
-			block = value64(ro_node(s), i);
-
+		if (next_block || flags & INTERNAL_NODE) {
+			if (find_highest)
+				block = value64(ro_node(s), i);
+			else
+				block = value64(ro_node(s), 0);
+		}
 	} while (flags & INTERNAL_NODE);

 	if (next_block)
-- 
1.8.3.1