Messages in this thread | | | From | Ryusuke Konishi <> | Date | Wed, 3 Apr 2024 05:55:30 +0900 | Subject | Re: [PATCH] fs/nilfs2: prevent int overflow in btree binary search |
| |
On Wed, Apr 3, 2024 at 3:00 AM Sabyrzhan Tasbolatov wrote: > > Should prevent int overflow if low + high > INT_MAX in big btree with > nchildren in nilfs_btree_node_lookup() binary search. > > Signed-off-by: Sabyrzhan Tasbolatov <snovitoll@gmail.com> > --- > fs/nilfs2/btree.c | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c > index 65659fa03..39ee4fe11 100644 > --- a/fs/nilfs2/btree.c > +++ b/fs/nilfs2/btree.c > @@ -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; > -- > 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
| |