linux-kernel - [PATCH v2 1/2] befs: remove unused BEFS_BT

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>] [thread-next>] [day] [month] [year] [list]
Date:	Fri,  5 Aug 2016 13:41:20 +0100
From:	Luis de Bethencourt <luisbg@....samsung.com>
To:	linux-kernel@...r.kernel.org
Cc:	akpm@...ux-foundation.org, viro@...iv.linux.org.uk,
	salah.triki@....org, Luis de Bethencourt <luisbg@....samsung.com>
Subject: [PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH

befs_btree_find(), the only caller of befs_find_key(), only cares about if
the return from that function is BEFS_BT_MATCH or not. It never uses the
partial match given with BEFS_BT_MATCH. Removing that return and don't set
the value that will go unused.

Signed-off-by: Luis de Bethencourt <luisbg@....samsung.com>
---
v2: fix overflow != not found
    keep a value for the while(!leafnode()) loop to find a leaf node and exit


Hi,

This is a correction. Now I understand the difference between returning
NOT_FOUND when the key is in a full node and we have to look in the overflow.
Compared to NOT_FOUND when the key doesn't exist.

For the former, we can set the key value to 0 and that means check the overflow.

For the latter, we need to return an existing value, even if not correct, so
the while loop [while (!befs_leafnode(this_node))] can find a leaf, exit and
then see it is not the correct node in the call of befs_find_next() right after
the loop body.

This makes the code more readable than a mysterious "partial match" that
actually means no match.

There is still an issue with the comparison of the strings in the binary
search. About to start looking into that but wanted to send this corrected
patch first before any of you reviewed the faulty first version.

Thanks,
Luis

 fs/befs/befs.h  |  1 -
 fs/befs/btree.c | 38 ++++++++++++++++----------------------
 2 files changed, 16 insertions(+), 23 deletions(-)

diff --git a/fs/befs/befs.h b/fs/befs/befs.h
index c5c6cd1..faf3fac 100644
--- a/fs/befs/befs.h
+++ b/fs/befs/befs.h
@@ -79,7 +79,6 @@ enum befs_err {
 	BEFS_BT_END,
 	BEFS_BT_EMPTY,
 	BEFS_BT_MATCH,
-	BEFS_BT_PARMATCH,
 	BEFS_BT_NOT_FOUND
 };
 
diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index 3f1a391..bc7efb0 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -281,9 +281,9 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
 
 	while (!befs_leafnode(this_node)) {
 		res = befs_find_key(sb, this_node, key, &node_off);
-		if (res == BEFS_BT_NOT_FOUND)
+		/* if no key set, try the overflow node */
+		if (node_off == 0)
 			node_off = this_node->head.overflow;
-		/* if no match, go to overflow node */
 		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
 			befs_error(sb, "befs_btree_find() failed to read "
 				   "node at %llu", node_off);
@@ -291,8 +291,7 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
 		}
 	}
 
-	/* at the correct leaf node now */
-
+	/* at a leaf node now, check if it is correct */
 	res = befs_find_key(sb, this_node, key, value);
 
 	brelse(this_node->bh);
@@ -321,18 +320,13 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
  * @sb: Filesystem superblock
  * @node: Node to find the key within
  * @findkey: Keystring to search for
- * @value: If key is found, the value stored with the key is put here
- *
- * finds exact match if one exists, and returns BEFS_BT_MATCH
- * If no exact match, finds first key in node that is greater
- * (alphabetically) than the search key and returns BEFS_BT_PARMATCH
- * (for partial match, I guess). Can you think of something better to
- * call it?
+ * @value: If key is found, the value stored with the key is put here.
+ *		If not, the value is returned as 0.
  *
- * If no key was a match or greater than the search key, return
- * BEFS_BT_NOT_FOUND.
+ * Finds exact match if one exists, and returns BEFS_BT_MATCH.
+ * If there is no exact match, it returns BEFS_BT_NOT_FOUND.
  *
- * Use binary search instead of a linear.
+ * Uses binary search instead of a linear.
  */
 static int
 befs_find_key(struct super_block *sb, struct befs_btree_node *node,
@@ -355,8 +349,8 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
 
 	eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
 	if (eq < 0) {
-		befs_error(sb, "<--- %s %s not found", __func__, findkey);
-		befs_debug(sb, "<--- %s ERROR", __func__);
+		*value = 0;
+		befs_debug(sb, "<--- node can't contain %s", findkey);
 		return BEFS_BT_NOT_FOUND;
 	}
 
@@ -385,12 +379,12 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
 		else
 			first = mid + 1;
 	}
-	if (eq < 0)
-		*value = fs64_to_cpu(sb, valarray[mid + 1]);
-	else
-		*value = fs64_to_cpu(sb, valarray[mid]);
-	befs_debug(sb, "<--- %s found %s at %d", __func__, thiskey, mid);
-	return BEFS_BT_PARMATCH;
+
+	/* return an existing value so caller can arrive to a leaf node */
+	*value = fs64_to_cpu(sb, valarray[mid]);
+	befs_error(sb, "<--- %s %s not found", __func__, findkey);
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_BT_NOT_FOUND;
 }
 
 /**
-- 
2.5.1