All of lore.kernel.org
 help / color / mirror / Atom feed
* [dm-devel] [PATCH] Fix for find_lowest_key in dm-btree.c
@ 2017-04-07  2:09 Vinothkumar Raja
  0 siblings, 0 replies; only message in thread
From: Vinothkumar Raja @ 2017-04-07  2:09 UTC (permalink / raw)
  To: agk, snitzer
  Cc: dm-devel, shli, linux-raid, linux-kernel, ezk, npanpalia,
	tarasov, Vinothkumar Raja, Erez Zadok

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@fsl.cs.sunysb.edu>
Signed-off-by: Vinothkumar Raja <vinraja@cs.stonybrook.edu>
Signed-off-by: Nidhi Panpalia <npanpalia@cs.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


^ permalink raw reply related	[flat|nested] only message in thread

only message in thread, other threads:[~2017-04-07  2:09 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-07  2:09 [dm-devel] [PATCH] Fix for find_lowest_key in dm-btree.c Vinothkumar Raja

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.