[Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Nikita Pettik]

vy_page_find_key() assumes that equal_key parameter is initialized since
it is used unconditionally. There are several places where
vy_page_find_key() is called:

- vy_slice_stream_search() calls vy_page_find_key();
- vy_run_iterator_read() calls vy_run_iterator_load_page(),
which in turn calls vy_page_find_key();
- vy_run_iterator_search() also calls vy_run_iterator_load_page().

First two fixes are obvious - lifespan of parameter passed to
*_find_key() is clear and restricted by caller. In the last case
firstly vy_page_find_key() is called, but equal_key output value is not
used. Then it is re-assigned with task->equal_found which is the result
of another on vy_page_find_key() invocation in vy_page_read_cb. So it is
safe to initialize equal_found parameter with 'false' value as well.

Closes #5078
---
Branch: https://github.com/tarantool/tarantool/tree/np/gh-5078-uninit-var-sanitizer
Issue: https://github.com/tarantool/tarantool/issues/5078

 src/box/vy_run.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 54cf028d0..db4565954 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1095,7 +1095,7 @@ vy_run_iterator_read(struct vy_run_iterator *itr,
 		     struct vy_entry *ret)
 {
 	struct vy_page *page;
-	bool equal_found;
+	bool equal_found = false;
 	uint32_t pos_in_page;
 	int rc = vy_run_iterator_load_page(itr, pos.page_no, vy_entry_none(),
 					   ITER_GE, &page, &pos_in_page,
@@ -1129,7 +1129,7 @@ vy_run_iterator_search(struct vy_run_iterator *itr,
 					       equal_key);
 	if (pos->page_no == itr->slice->run->info.page_count)
 		return 1;
-	bool equal_in_page;
+	bool equal_in_page = false;
 	struct vy_page *page;
 	int rc = vy_run_iterator_load_page(itr, pos->page_no, key,
 					   iterator_type, &page,
@@ -2615,7 +2615,7 @@ vy_slice_stream_search(struct vy_stmt_stream *virt_stream)
 	if (vy_slice_stream_read_page(stream) != 0)
 		return -1;
 
-	bool unused;
+	bool unused = false;
 	stream->pos_in_page = vy_page_find_key(stream->page,
 					       stream->slice->begin,
 					       stream->cmp_def,
-- 
2.17.1

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Vladislav Shpilevoy]

Hi! Thanks for the patch!

On 15/06/2020 20:42, Nikita Pettik wrote:
> vy_page_find_key() assumes that equal_key parameter is initialized since
> it is used unconditionally. There are several places where
> vy_page_find_key() is called:
> 
> - vy_slice_stream_search() calls vy_page_find_key();
> - vy_run_iterator_read() calls vy_run_iterator_load_page(),
> which in turn calls vy_page_find_key();
> - vy_run_iterator_search() also calls vy_run_iterator_load_page().
> 
> First two fixes are obvious - lifespan of parameter passed to
> *_find_key() is clear and restricted by caller. In the last case
> firstly vy_page_find_key() is called, but equal_key output value is not
> used. Then it is re-assigned with task->equal_found which is the result
> of another on vy_page_find_key() invocation in vy_page_read_cb. So it is
> safe to initialize equal_found parameter with 'false' value as well.

You said that in the last case vy_page_find_key() is called first, but
I don't see where. vy_run_iterator_search() does not call vy_page_find_key().

What is bothering me, is that this not initialized bool was almost always
true on my machine (due to not-zero garbage). I changed it to true, and
the tests passed. Reverted back to false - passed as well.

So there either is missing a good test on that, or vy_run_iterator_load_page()
does not need the parameter 'bool *equal_found'. Because its input and
output values don't matter. In both invocation places this parameter does
not affect anything.

> diff --git a/src/box/vy_run.c b/src/box/vy_run.c
> index 54cf028d0..db4565954 100644
> --- a/src/box/vy_run.c
> +++ b/src/box/vy_run.c
> @@ -1129,7 +1129,7 @@ vy_run_iterator_search(struct vy_run_iterator *itr,
>  					       equal_key);
>  	if (pos->page_no == itr->slice->run->info.page_count)
>  		return 1;
> -	bool equal_in_page;
> +	bool equal_in_page = false;

This I changed to true, and all the tests passed.

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Nikita Pettik]

On 17 Jun 01:10, Vladislav Shpilevoy wrote:
> Hi! Thanks for the patch!
> 
> On 15/06/2020 20:42, Nikita Pettik wrote:
> > vy_page_find_key() assumes that equal_key parameter is initialized since
> > it is used unconditionally. There are several places where
> > vy_page_find_key() is called:
> > 
> > - vy_slice_stream_search() calls vy_page_find_key();
> > - vy_run_iterator_read() calls vy_run_iterator_load_page(),
> > which in turn calls vy_page_find_key();
> > - vy_run_iterator_search() also calls vy_run_iterator_load_page().
> > 
> > First two fixes are obvious - lifespan of parameter passed to
> > *_find_key() is clear and restricted by caller. In the last case
> > firstly vy_page_find_key() is called, but equal_key output value is not
> > used. Then it is re-assigned with task->equal_found which is the result
> > of another on vy_page_find_key() invocation in vy_page_read_cb. So it is
> > safe to initialize equal_found parameter with 'false' value as well.
> 
> You said that in the last case vy_page_find_key() is called first, but
> I don't see where. vy_run_iterator_search() does not call vy_page_find_key().

vy_run_iterator_search()
  --> vy_run_iterator_load_page()
        --> 1021 vy_page_find_key()
        --> 1051 task->equal_found = false;
        --> 1056 *equal_found = task->equal_found;

Also see b907231713a75d716793505ad727ecea9415d774
Analogue of equal_key was equal_in_page which was 'false' by default.
It's pretty sad that tests do not cover this path. Could you please
file an issue to provide proper test? I'll try to come up with test some day.
 
> What is bothering me, is that this not initialized bool was almost always
> true on my machine (due to not-zero garbage). I changed it to true, and
> the tests passed. Reverted back to false - passed as well.
> 
> So there either is missing a good test on that, or vy_run_iterator_load_page()
> does not need the parameter 'bool *equal_found'. Because its input and
> output values don't matter. In both invocation places this parameter does
> not affect anything.
> 
> > diff --git a/src/box/vy_run.c b/src/box/vy_run.c
> > index 54cf028d0..db4565954 100644
> > --- a/src/box/vy_run.c
> > +++ b/src/box/vy_run.c
> > @@ -1129,7 +1129,7 @@ vy_run_iterator_search(struct vy_run_iterator *itr,
> >  					       equal_key);
> >  	if (pos->page_no == itr->slice->run->info.page_count)
> >  		return 1;
> > -	bool equal_in_page;
> > +	bool equal_in_page = false;
> 
> This I changed to true, and all the tests passed.

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Vladislav Shpilevoy]

>> On 15/06/2020 20:42, Nikita Pettik wrote:
>>> vy_page_find_key() assumes that equal_key parameter is initialized since
>>> it is used unconditionally. There are several places where
>>> vy_page_find_key() is called:
>>>
>>> - vy_slice_stream_search() calls vy_page_find_key();
>>> - vy_run_iterator_read() calls vy_run_iterator_load_page(),
>>> which in turn calls vy_page_find_key();
>>> - vy_run_iterator_search() also calls vy_run_iterator_load_page().
>>>
>>> First two fixes are obvious - lifespan of parameter passed to
>>> *_find_key() is clear and restricted by caller. In the last case
>>> firstly vy_page_find_key() is called, but equal_key output value is not
>>> used. Then it is re-assigned with task->equal_found which is the result
>>> of another on vy_page_find_key() invocation in vy_page_read_cb. So it is
>>> safe to initialize equal_found parameter with 'false' value as well.
>>
>> You said that in the last case vy_page_find_key() is called first, but
>> I don't see where. vy_run_iterator_search() does not call vy_page_find_key().
> 
> vy_run_iterator_search()
>   --> vy_run_iterator_load_page()
>         --> 1021 vy_page_find_key()
>         --> 1051 task->equal_found = false;
>         --> 1056 *equal_found = task->equal_found;

But I see, that the variable is used, if vy_page_find_key() is called.
Consider this path:

	vy_run_iterator_search()
	    vy_run_iterator_load_page(&equal_in_page)
	        vy_page_find_key(&equal_in_page)
	    *equal_key = equal_in_page;

equal_in_page after all becomes output value of
vy_run_iterator_search().

If you still think it should be false, then probably we need to
make the initialization inside vy_run_iterator_load_page(). Anyway
in both invocations a caller now need to set it to false.

Perhaps even vy_page_find_key() could do that. Why is it needed
not to reset it to false on each vy_page_find_key() call?

> Also see b907231713a75d716793505ad727ecea9415d774
> Analogue of equal_key was equal_in_page which was 'false' by default.
> It's pretty sad that tests do not cover this path. Could you please
> file an issue to provide proper test? I'll try to come up with test some day.

I think we can just keep this issue open, but still push this
commit as 'Part of'. To fix the builds. Because a new issue anyway
would be exactly the same + a comment saying "need to test".

The commit LGTM, if "Closes" -> "Part of".

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Nikita Pettik]

On 17 Jun 23:56, Vladislav Shpilevoy wrote:
> >> On 15/06/2020 20:42, Nikita Pettik wrote:
> >>> vy_page_find_key() assumes that equal_key parameter is initialized since
> >>> it is used unconditionally. There are several places where
> >>> vy_page_find_key() is called:
> >>>
> >>> - vy_slice_stream_search() calls vy_page_find_key();
> >>> - vy_run_iterator_read() calls vy_run_iterator_load_page(),
> >>> which in turn calls vy_page_find_key();
> >>> - vy_run_iterator_search() also calls vy_run_iterator_load_page().
> >>>
> >>> First two fixes are obvious - lifespan of parameter passed to
> >>> *_find_key() is clear and restricted by caller. In the last case
> >>> firstly vy_page_find_key() is called, but equal_key output value is not
> >>> used. Then it is re-assigned with task->equal_found which is the result
> >>> of another on vy_page_find_key() invocation in vy_page_read_cb. So it is
> >>> safe to initialize equal_found parameter with 'false' value as well.
> >>
> >> You said that in the last case vy_page_find_key() is called first, but
> >> I don't see where. vy_run_iterator_search() does not call vy_page_find_key().
> > 
> > vy_run_iterator_search()
> >   --> vy_run_iterator_load_page()
> >         --> 1021 vy_page_find_key()
> >         --> 1051 task->equal_found = false;
> >         --> 1056 *equal_found = task->equal_found;
> 
> But I see, that the variable is used, if vy_page_find_key() is called.
> Consider this path:
> 
> 	vy_run_iterator_search()
> 	    vy_run_iterator_load_page(&equal_in_page)
> 	        vy_page_find_key(&equal_in_page)
> 	    *equal_key = equal_in_page;
> 
> equal_in_page after all becomes output value of
> vy_run_iterator_search().
> 
> If you still think it should be false, then probably we need to
> make the initialization inside vy_run_iterator_load_page(). Anyway
> in both invocations a caller now need to set it to false.
> 
> Perhaps even vy_page_find_key() could do that. Why is it needed
> not to reset it to false on each vy_page_find_key() call?

Agree, let's do it. New patch is:

diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 54cf028d0..b9822dc3e 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -790,7 +790,7 @@ vy_page_stmt(struct vy_page *page, uint32_t stmt_no,
  * Binary search in page
  * In terms of STL, makes lower_bound for EQ,GE,LT and upper_bound for GT,LE
  * Additionally *equal_key argument is set to true if the found value is
- * equal to given key (untouched otherwise)
+ * equal to given key (set to false otherwise).
  * @retval position in the page
  */
 static uint32_t
@@ -800,6 +800,7 @@ vy_page_find_key(struct vy_page *page, struct vy_entry key,
 {
        uint32_t beg = 0;
        uint32_t end = page->row_count;
+       *equal_key = false;
        /* for upper bound we change zero comparison result to -1 */
        int zero_cmp = (iterator_type == ITER_GT ||
                        iterator_type == ITER_LE ? -1 : 0);

 
> > Also see b907231713a75d716793505ad727ecea9415d774
> > Analogue of equal_key was equal_in_page which was 'false' by default.
> > It's pretty sad that tests do not cover this path. Could you please
> > file an issue to provide proper test? I'll try to come up with test some day.
> 
> I think we can just keep this issue open, but still push this
> commit as 'Part of'. To fix the builds. Because a new issue anyway
> would be exactly the same + a comment saying "need to test".
> 
> The commit LGTM, if "Closes" -> "Part of".

I've dived a bit in git history and found original patch introducing
this function: b7724150b3017af60b28e3491d971d9eab1d709e
(it was called vy_run_iterator_search_in_page()). Its the only usage
was with equal_key initialized to 'false'. I believe it is the
right way this function should be used.

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Vladislav Shpilevoy]

LGTM.

Re: [Tarantool-patches] [PATCH] vinyl: fix passing uninitialized parameter to vy_page_find_key()

[Nikita Pettik]

On 23 Jun 00:54, Vladislav Shpilevoy wrote:
> LGTM.

Pushed to master, 2.4, 2.3 and 1.10. Branch is dropped.