| 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
| ||
|
Message-ID: <57A63029.9010806@osg.samsung.com>
Date: Sat, 06 Aug 2016 19:44:57 +0100
From: Luis de Bethencourt <luisbg@....samsung.com>
To: Salah Triki <salah.triki@...il.com>
CC: linux-kernel@...r.kernel.org, akpm@...ux-foundation.org,
viro@...iv.linux.org.uk
Subject: Re: [PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH
On 06/08/16 19:34, Salah Triki wrote:
> On Fri, Aug 05, 2016 at 01:41:20PM +0100, Luis de Bethencourt wrote:
>> 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
>>
>
> Hi,
>
>> For the former, we can set the key value to 0 and that means check the overflow.
>
> Making befs_find_tree return BEFS_BT_OVERFLOW is more readable than checking the key value.
>
> Nacked.
>
> Thanx,
> Salah
>
Hi,
Yeah, I agree. The ternary property of the function due to one call wanting to see if it
is overflow or not, and the second call wanting to see if it is found or not. This makes
it good to have BEFS_BT_MATCH, BEFS_BT_NOT_FOUND, and BEFS_BT_OVERFLOW as returns. Better
readability.
Will send a corrected patch soon.
Thanks for the review,
Luis
Powered by blists - more mailing lists