fs/nilfs2: prevent int overflow in btree binary search
PATCH 1/1 fs/nilfs2: prevent int overflow in btree binary search
Should prevent int overflow if low + high > INT_MAX in big btree with nchildren in nilfs_btree_node_lookup() binary search.
--- fs/nilfs2/btree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
fs/nilfs2/btree.c +1 -1
@@ -300,7 +300,7 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, index =0 ; s =0 ;while (low <= high) { - index = (low + high) /2 ; + index = low + (high - low) /2 ; nkey =nilfs_btree_node_get_key (node, index);if (nkey == key) { s =0 ;
Signature · 1 line
2.34.1
Ryusuke Konishi
maintainerQuoted 23 lines · Sabyrzhan Tasbolatov
Should prevent int overflow if low + high >
INT_MAXin big btree with nchildren innilfs_btree_node_lookup()binary search.Signed-off-by Sabyrzhan Tasbolatov <[email protected]>--- fs/nilfs2/btree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)fs/nilfs2/btree.c +1
-2@@ -300,7 +300,7 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, index =0 ; s =0 ;while (low <= high) { - index = (low + high) /2 ; + index = low + (high - low) /2 ; nkey =nilfs_btree_node_get_key (node, index);if (nkey == key) { s =0 ; --
Quoted 2 lines
2.34.1
Hi Sabyrzhan,
Thank you for your interesting patch.
In this function, the value of the variable "high" is initialized with "nilfs_btree_node_get_nchildren() - 1", and "low" is initialized with 0.
nilfs_btree_node_get_nchildren() returns a value read from a 16-bit wide field, so it will never exceed U16_MAX.
These index calculations narrow the range between "low" and "high", so as long as INT_MAX is 32-bit or more, it seems that the calculation of this intermediate value will not overflow.
So while it's a good overflow avoidance technique, it doesn't seem to happen in practice.
Am I missing something?
Regards,
Ryusuke Konishi
Hi Ryusuke,
Quoted 2 lines
nilfs_btree_node_get_nchildren()returns a value read from a 16-bit wide field, so it will never exceedU16_MAX.
You're right, "high" indeed never exceeds INT_MAX as it's limited to 16-bit in 32-bit integer. Sorry for the confusion, It landed via my grepping tool.
Sabyrzhan Tasbolatov
Quoted 50 lines · Ryusuke Konishi
Quoted 23 lines · Sabyrzhan Tasbolatov
Should prevent int overflow if low + high >
INT_MAXin big btree with nchildren innilfs_btree_node_lookup()binary search.Signed-off-by Sabyrzhan Tasbolatov <[email protected]>--- fs/nilfs2/btree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)fs/nilfs2/btree.c +1
-2@@ -300,7 +300,7 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, index =0 ; s =0 ;while (low <= high) { - index = (low + high) /2 ; + index = low + (high - low) /2 ; nkey =nilfs_btree_node_get_key (node, index);if (nkey == key) { s =0 ; --Quoted 2 lines
2.34.1
Hi Sabyrzhan,
Thank you for your interesting patch.
In this function, the value of the variable "high" is initialized with "
nilfs_btree_node_get_nchildren()- 1", and "low" is initialized with 0.
nilfs_btree_node_get_nchildren()returns a value read from a 16-bit wide field, so it will never exceedU16_MAX.These index calculations narrow the range between "low" and "high", so as long as
INT_MAXis 32-bit or more, it seems that the calculation of this intermediate value will not overflow.So while it's a good overflow avoidance technique, it doesn't seem to happen in practice.
Am I missing something?
Regards,
Ryusuke Konishi