[PATCH 0/4] vinyl: fix crash in vinyl_iterator_secondary_next()

[PATCH 0/4] vinyl: fix crash in vinyl_iterator_secondary_next()

[Vladimir Davydov]

Hopefully, this will fix the crash happening at Mail.Ru Cloud deployment.

https://github.com/tarantool/tarantool/issues/3393
https://github.com/tarantool/tarantool/commits/gh-3393-vy-fix-crash-in-sk-select

Vladimir Davydov (4):
  vinyl: fix EQ check in run iterator
  vinyl: fix lost key on dump completion
  vinyl: do not panic if secondary index is inconsistent with primary
  test: improve vinyl/select_consistency

 src/box/vinyl.c                        | 23 +++++++++++++++++++----
 src/box/vy_run.c                       | 13 ++++++++++++-
 src/box/vy_scheduler.c                 |  3 ++-
 test/vinyl/select_consistency.result   | 11 +++++++----
 test/vinyl/select_consistency.test.lua |  9 +++++----
 5 files changed, 45 insertions(+), 14 deletions(-)

-- 
2.11.0

[PATCH 1/4] vinyl: fix EQ check in run iterator

[Vladimir Davydov]

vy_run_iterator_seek() is supposed to check that the resulting statement
matches the search key in case of ITER_EQ, but if the search key lies at
the beginning of the slice, it doesn't. As a result, vy_point_lookup()
may fail to find an existing tuple as demonstrated below.

Suppose we are looking for key {10} in the primary index which consists
of an empty mem and two runs:

    run 1: DELETE{15}
    run 2: INSERT{10}

vy_run_iterator_next() returns DELETE{15} for run 1 because of the
missing EQ check and vy_point_lookup() stops at run 1 (since the
terminal statement is found) and mistakenly returns NULL.

The issue manifests itself as crash in vinyl_iterator_secondary_next(),
when we fail to find the tuple in the primary index corresponding to a
statement found in a secondary index.

Part of #3393
---
 src/box/vy_run.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 587cb002..8c922895 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1316,6 +1316,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
 {
 	const struct key_def *cmp_def = itr->cmp_def;
 	struct vy_slice *slice = itr->slice;
+	const struct tuple *check_eq_key = NULL;
 	int cmp;
 
 	if (slice->begin != NULL &&
@@ -1340,6 +1341,8 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
 			return 0;
 		}
 		if (cmp < 0 || (cmp == 0 && iterator_type != ITER_GT)) {
+			if (iterator_type == ITER_EQ)
+				check_eq_key = key;
 			iterator_type = ITER_GE;
 			key = slice->begin;
 		}
@@ -1365,7 +1368,15 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
 		}
 	}
 
-	return vy_run_iterator_do_seek(itr, iterator_type, key, ret);
+	if (vy_run_iterator_do_seek(itr, iterator_type, key, ret) != 0)
+		return -1;
+
+	if (check_eq_key != NULL && *ret != NULL &&
+	    vy_stmt_compare(check_eq_key, *ret, cmp_def) != 0) {
+		vy_run_iterator_stop(itr);
+		*ret = NULL;
+	}
+	return 0;
 }
 
 /* }}} vy_run_iterator vy_run_iterator support functions */
-- 
2.11.0

Re: [PATCH 1/4] vinyl: fix EQ check in run iterator

[Konstantin Osipov]

* Vladimir Davydov <vdavydov.dev@gmail.com> [18/05/15 17:10]:

I am pushing this as is now, please a couple of comments below.

> vy_run_iterator_seek() is supposed to check that the resulting statement
> matches the search key in case of ITER_EQ, but if the search key lies at
> the beginning of the slice, it doesn't. As a result, vy_point_lookup()
> may fail to find an existing tuple as demonstrated below.
> 
> Suppose we are looking for key {10} in the primary index which consists
> of an empty mem and two runs:
> 
>     run 1: DELETE{15}
>     run 2: INSERT{10}
> 
> vy_run_iterator_next() returns DELETE{15} for run 1 because of the
> missing EQ check and vy_point_lookup() stops at run 1 (since the
> terminal statement is found) and mistakenly returns NULL.
> 
> The issue manifests itself as crash in vinyl_iterator_secondary_next(),
> when we fail to find the tuple in the primary index corresponding to a
> statement found in a secondary index.

I believe this explanation belongs to the code, not only to the
changeset comment.

Ideally, this special case should be covered in a unit test, not
just in the code or in CS comment.

> Part of #3393
> ---
>  src/box/vy_run.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
> 
> diff --git a/src/box/vy_run.c b/src/box/vy_run.c
> index 587cb002..8c922895 100644
> --- a/src/box/vy_run.c
> +++ b/src/box/vy_run.c
> @@ -1316,6 +1316,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
>  {
>  	const struct key_def *cmp_def = itr->cmp_def;
>  	struct vy_slice *slice = itr->slice;
> +	const struct tuple *check_eq_key = NULL;
>  	int cmp;
>  
>  	if (slice->begin != NULL &&
> @@ -1340,6 +1341,8 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
>  			return 0;
>  		}
>  		if (cmp < 0 || (cmp == 0 && iterator_type != ITER_GT)) {
> +			if (iterator_type == ITER_EQ)
> +				check_eq_key = key;
>  			iterator_type = ITER_GE;
>  			key = slice->begin;
>  		}
> @@ -1365,7 +1368,15 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
>  		}
>  	}
>  
> -	return vy_run_iterator_do_seek(itr, iterator_type, key, ret);
> +	if (vy_run_iterator_do_seek(itr, iterator_type, key, ret) != 0)
> +		return -1;
> +
> +	if (check_eq_key != NULL && *ret != NULL &&
> +	    vy_stmt_compare(check_eq_key, *ret, cmp_def) != 0) {
> +		vy_run_iterator_stop(itr);
> +		*ret = NULL;
> +	}

As far as I understand the code flow, this adds an extra check for
cases when key != slice->begin. This is 99.9% of cases. Can we
avoid an extra check if it is not needed?

> +	return 0;
>  }

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [PATCH 1/4] vinyl: fix EQ check in run iterator

[Vladimir Davydov]

On Tue, May 15, 2018 at 10:05:12PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [18/05/15 17:10]:
> 
> I am pushing this as is now, please a couple of comments below.
> 
> > vy_run_iterator_seek() is supposed to check that the resulting statement
> > matches the search key in case of ITER_EQ, but if the search key lies at
> > the beginning of the slice, it doesn't. As a result, vy_point_lookup()
> > may fail to find an existing tuple as demonstrated below.
> > 
> > Suppose we are looking for key {10} in the primary index which consists
> > of an empty mem and two runs:
> > 
> >     run 1: DELETE{15}
> >     run 2: INSERT{10}
> > 
> > vy_run_iterator_next() returns DELETE{15} for run 1 because of the
> > missing EQ check and vy_point_lookup() stops at run 1 (since the
> > terminal statement is found) and mistakenly returns NULL.
> > 
> > The issue manifests itself as crash in vinyl_iterator_secondary_next(),
> > when we fail to find the tuple in the primary index corresponding to a
> > statement found in a secondary index.
> 
> I believe this explanation belongs to the code, not only to the
> changeset comment.

Well, all those ITER_EQ checks are scattered throughout iterator code
and none of them has a comment as they all are pretty self-explaining.
Adding a comment to just one of them looks pointless IMO.

Actually, I was thinking about extracting all the EQ checks out of
source iterators and moving them to vy_read_iterator as this would allow
to reduce the number of EQ comparisons, but I didn't get my hands on it
as there were some problems with the cache iterator. May be, later.

> 
> Ideally, this special case should be covered in a unit test, not
> just in the code or in CS comment.

After the last patch in the series is applied, vinyl/select_consistency
functional test triggers this bug in 100% cases. Anyway, I'll think
about a unit test.

> 
> > Part of #3393
> > ---
> >  src/box/vy_run.c | 13 ++++++++++++-
> >  1 file changed, 12 insertions(+), 1 deletion(-)
> > 
> > diff --git a/src/box/vy_run.c b/src/box/vy_run.c
> > index 587cb002..8c922895 100644
> > --- a/src/box/vy_run.c
> > +++ b/src/box/vy_run.c
> > @@ -1316,6 +1316,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
> >  {
> >  	const struct key_def *cmp_def = itr->cmp_def;
> >  	struct vy_slice *slice = itr->slice;
> > +	const struct tuple *check_eq_key = NULL;
> >  	int cmp;
> >  
> >  	if (slice->begin != NULL &&
> > @@ -1340,6 +1341,8 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
> >  			return 0;
> >  		}
> >  		if (cmp < 0 || (cmp == 0 && iterator_type != ITER_GT)) {
> > +			if (iterator_type == ITER_EQ)
> > +				check_eq_key = key;
> >  			iterator_type = ITER_GE;
> >  			key = slice->begin;
> >  		}
> > @@ -1365,7 +1368,15 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
> >  		}
> >  	}
> >  
> > -	return vy_run_iterator_do_seek(itr, iterator_type, key, ret);
> > +	if (vy_run_iterator_do_seek(itr, iterator_type, key, ret) != 0)
> > +		return -1;
> > +
> > +	if (check_eq_key != NULL && *ret != NULL &&
> > +	    vy_stmt_compare(check_eq_key, *ret, cmp_def) != 0) {
> > +		vy_run_iterator_stop(itr);
> > +		*ret = NULL;
> > +	}
> 
> As far as I understand the code flow, this adds an extra check for
> cases when key != slice->begin. This is 99.9% of cases. Can we
> avoid an extra check if it is not needed?

We do this extra tuple comparison only if cmp == 0 and the original
iterator_type is ITER_EQ. The (cmp < 0) case is excluded, because we
stop the iteration in this case for ITER_EQ - see several lines above:

> 		cmp = vy_stmt_compare_with_key(key, slice->begin, cmp_def);
> 		if (cmp < 0 && iterator_type == ITER_EQ) {
> 			vy_run_iterator_stop(itr);
> 			return 0;
> 		}
> 		if (cmp < 0 || (cmp == 0 && iterator_type != ITER_GT)) {
> 			if (iterator_type == ITER_EQ)
> 				check_eq_key = key;

				^^^^^^^^^^^^^^^^^^
cmp can't be < 0 if this assignment takes place

> 			iterator_type = ITER_GE;
> 			key = slice->begin;
> 		}

Looks rather messy, but then again I think we should try to clean up
this mess by extracting ITER_EQ check out of source iterators.

Thanks.

[PATCH 2/4] vinyl: fix lost key on dump completion

[Vladimir Davydov]

vy_task_dump_complete() creates a slice per each range overlapping with
the newly written run. It uses vy_range_tree_psearch(min_key) to find
the first overlapping range and nsearch(max_key) to find the range
immediately following the last overlapping range. This is incorrect as
nsearch rb tree method returns the element matching the search key if it
is present in the tree. That is, if the max key written to a run turns
out to be equal the beginning of a range, the slice won't be created for
it and it will be silently and persistently lost.

The issue manifests itself as crash in vinyl_iterator_secondary_next(),
when we fail to find the tuple in the primary index corresponding to a
statement found in a secondary index.

Part of #3393
---
 src/box/vy_scheduler.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index 912d9028..b76db587 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -741,7 +741,8 @@ vy_task_dump_complete(struct vy_scheduler *scheduler, struct vy_task *task)
 		goto fail;
 	}
 	begin_range = vy_range_tree_psearch(lsm->tree, min_key);
-	end_range = vy_range_tree_nsearch(lsm->tree, max_key);
+	end_range = vy_range_tree_psearch(lsm->tree, max_key);
+	end_range = vy_range_tree_next(lsm->tree, end_range);
 	tuple_unref(min_key);
 	tuple_unref(max_key);
 
-- 
2.11.0

Re: [PATCH 2/4] vinyl: fix lost key on dump completion

[Konstantin Osipov]

* Vladimir Davydov <vdavydov.dev@gmail.com> [18/05/15 17:10]:

I rebased the patch to 1.9, added a comment and pushed the patch.

Once again, a separate unit test for this edge case would be
greatly appreciated.

> vy_task_dump_complete() creates a slice per each range overlapping with
> the newly written run. It uses vy_range_tree_psearch(min_key) to find
> the first overlapping range and nsearch(max_key) to find the range
> immediately following the last overlapping range. This is incorrect as
> nsearch rb tree method returns the element matching the search key if it
> is present in the tree. That is, if the max key written to a run turns
> out to be equal the beginning of a range, the slice won't be created for
> it and it will be silently and persistently lost.
> 
> The issue manifests itself as crash in vinyl_iterator_secondary_next(),
> when we fail to find the tuple in the primary index corresponding to a
> statement found in a secondary index.
> 
> Part of #3393
> ---
>  src/box/vy_scheduler.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
> index 912d9028..b76db587 100644
> --- a/src/box/vy_scheduler.c
> +++ b/src/box/vy_scheduler.c
> @@ -741,7 +741,8 @@ vy_task_dump_complete(struct vy_scheduler *scheduler, struct vy_task *task)
>  		goto fail;
>  	}
>  	begin_range = vy_range_tree_psearch(lsm->tree, min_key);
> -	end_range = vy_range_tree_nsearch(lsm->tree, max_key);
> +	end_range = vy_range_tree_psearch(lsm->tree, max_key);
> +	end_range = vy_range_tree_next(lsm->tree, end_range);
>  	tuple_unref(min_key);
>  	tuple_unref(max_key);
>  
> -- 
> 2.11.0

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [PATCH 2/4] vinyl: fix lost key on dump completion

[Vladimir Davydov]

On Tue, May 15, 2018 at 10:20:43PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [18/05/15 17:10]:
> 
> I rebased the patch to 1.9, added a comment and pushed the patch.
> 
> Once again, a separate unit test for this edge case would be
> greatly appreciated.

It's rather tricky to write a unit test for this as vy_scheduler depends
on a lot of things. However, this bug is triggered in ~90% cases by
vinyl/select_consistency functional test after the last patch in the
series is applied (and this one is reverted, apparently).

Thanks.

[PATCH 3/4] vinyl: do not panic if secondary index is inconsistent with primary

[Vladimir Davydov]

Although the bug in vy_task_dump_complete() due to which a tuple could
be lost during dump was fixed, there still may be affected deployments
as the bug was persisted on disk. To avoid occasional crashes on such
deployments, let's make vinyl_iterator_secondary_next() skip tuples that
are present in a secondary index but missing in the primary.

Closes #3393
---
 src/box/vinyl.c | 23 +++++++++++++++++++----
 1 file changed, 19 insertions(+), 4 deletions(-)

diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index ff4c2831..05aab30b 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -3844,6 +3844,7 @@ vinyl_iterator_secondary_next(struct iterator *base, struct tuple **ret)
 	assert(it->lsm->index_id > 0);
 	struct tuple *tuple;
 
+next:
 	if (it->tx == NULL) {
 		diag_set(ClientError, ER_CURSOR_NO_TRANSACTION);
 		goto fail;
@@ -3853,7 +3854,6 @@ vinyl_iterator_secondary_next(struct iterator *base, struct tuple **ret)
 		goto fail;
 	}
 
-
 	if (vy_read_iterator_next(&it->iterator, &tuple) != 0)
 		goto fail;
 
@@ -3876,11 +3876,26 @@ vinyl_iterator_secondary_next(struct iterator *base, struct tuple **ret)
 	 * Note, there's no need in vy_tx_track() as the
 	 * tuple is already tracked in the secondary index.
 	 */
+	struct tuple *full_tuple;
 	if (vy_point_lookup(it->lsm->pk, it->tx, vy_tx_read_view(it->tx),
-			    tuple, &tuple) != 0)
+			    tuple, &full_tuple) != 0)
 		goto fail;
-	*ret = tuple_bless(tuple);
-	tuple_unref(tuple);
+	if (full_tuple == NULL) {
+		/*
+		 * All indexes of a space must be consistent, i.e.
+		 * if a tuple is present in one index, it must be
+		 * present in all other indexes as well, so we can
+		 * get here only if there's a bug somewhere in vinyl.
+		 * Don't abort as core dump won't really help us in
+		 * this case. Just warn the user and proceed to the
+		 * next tuple.
+		 */
+		say_warn("%s: key %s missing in primary index",
+			 vy_lsm_name(it->lsm), vy_stmt_str(tuple));
+		goto next;
+	}
+	*ret = tuple_bless(full_tuple);
+	tuple_unref(full_tuple);
 	if (*ret != NULL)
 		return 0;
 fail:
-- 
2.11.0

[PATCH 4/4] test: improve vinyl/select_consistency

[Vladimir Davydov]

Improve the test by decreasing range_size so that it creates a lot of
ranges for test indexes, not just one. This helped find bugs causing
the crash described in #3393.

Follow-up #3393
---
 test/vinyl/select_consistency.result   | 11 +++++++----
 test/vinyl/select_consistency.test.lua |  9 +++++----
 2 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/test/vinyl/select_consistency.result b/test/vinyl/select_consistency.result
index 537f0613..c8f19cac 100644
--- a/test/vinyl/select_consistency.result
+++ b/test/vinyl/select_consistency.result
@@ -10,13 +10,13 @@ math.randomseed(os.time())
 s = box.schema.space.create('test', {engine = 'vinyl'})
 ---
 ...
-_ = s:create_index('pk', {parts = {1, 'unsigned'}})
+_ = s:create_index('pk', {parts = {1, 'unsigned'}, page_size = 64, range_size = 256})
 ---
 ...
-_ = s:create_index('i1', {unique = true, parts = {2, 'unsigned', 3, 'unsigned'}})
+_ = s:create_index('i1', {unique = true, parts = {2, 'unsigned', 3, 'unsigned'}, page_size = 64, range_size = 256})
 ---
 ...
-_ = s:create_index('i2', {unique = true, parts = {2, 'unsigned', 4, 'unsigned'}})
+_ = s:create_index('i2', {unique = true, parts = {2, 'unsigned', 4, 'unsigned'}, page_size = 64, range_size = 256})
 ---
 ...
 --
@@ -29,13 +29,16 @@ MAX_KEY = 100
 MAX_VAL = 10
 ---
 ...
+PADDING = string.rep('x', 100)
+---
+...
 test_run:cmd("setopt delimiter ';'")
 ---
 - true
 ...
 function gen_insert()
     pcall(s.insert, s, {math.random(MAX_KEY), math.random(MAX_VAL),
-                        math.random(MAX_VAL), math.random(MAX_VAL), 1})
+                        math.random(MAX_VAL), math.random(MAX_VAL), PADDING})
 end;
 ---
 ...
diff --git a/test/vinyl/select_consistency.test.lua b/test/vinyl/select_consistency.test.lua
index c29cb8ac..90fcf67e 100644
--- a/test/vinyl/select_consistency.test.lua
+++ b/test/vinyl/select_consistency.test.lua
@@ -5,9 +5,9 @@ fiber = require 'fiber'
 math.randomseed(os.time())
 
 s = box.schema.space.create('test', {engine = 'vinyl'})
-_ = s:create_index('pk', {parts = {1, 'unsigned'}})
-_ = s:create_index('i1', {unique = true, parts = {2, 'unsigned', 3, 'unsigned'}})
-_ = s:create_index('i2', {unique = true, parts = {2, 'unsigned', 4, 'unsigned'}})
+_ = s:create_index('pk', {parts = {1, 'unsigned'}, page_size = 64, range_size = 256})
+_ = s:create_index('i1', {unique = true, parts = {2, 'unsigned', 3, 'unsigned'}, page_size = 64, range_size = 256})
+_ = s:create_index('i2', {unique = true, parts = {2, 'unsigned', 4, 'unsigned'}, page_size = 64, range_size = 256})
 
 --
 -- If called from a transaction, i1:select({k}) and i2:select({k})
@@ -16,12 +16,13 @@ _ = s:create_index('i2', {unique = true, parts = {2, 'unsigned', 4, 'unsigned'}}
 
 MAX_KEY = 100
 MAX_VAL = 10
+PADDING = string.rep('x', 100)
 
 test_run:cmd("setopt delimiter ';'")
 
 function gen_insert()
     pcall(s.insert, s, {math.random(MAX_KEY), math.random(MAX_VAL),
-                        math.random(MAX_VAL), math.random(MAX_VAL), 1})
+                        math.random(MAX_VAL), math.random(MAX_VAL), PADDING})
 end;
 
 function gen_delete()
-- 
2.11.0