[Tarantool-patches] [PATCH v3] memtx: fix out of memory handling for rtree

[Tarantool-patches] [PATCH v3] memtx: fix out of memory handling for rtree

[Olga Arkhangelskaia]

When tarantool tries to recover rtree from a snapshot and memtx_memory value
is lower than it has been when the snapshot was created, server suffers from
segmentation fault. This happens because there is no out of memory error
handling in rtree lib. In another words, we do not check the result of
malloc operation.
The execution flow in case of recovery uses different way and the secondary
keys are build in batches. There is no separate implementations for rtree of
build_next function. And the way with no checks and reservation is used
(insex_replace). The patch adds memtx_rtree_build_next implementation to
check and insert keys. Although this gives us no additional optimization as in
case of memtx_tree, the memory reservation prevents tarantool from segmentation
fault.
If there is not enough memory to be reserved - server will fail
gently with the "Failed to allocate" error message.

Closes #4619
---
Branch: https://github.com/tarantool/tarantool/tree/OKriw/gh-RTREE-doesnt-handle-OOM-properly
Issue:https://github.com/tarantool/tarantool/issues/4619

v1:https://lists.tarantool.org/pipermail/tarantool-patches/2019-November/012391.html
v2:https://lists.tarantool.org/pipermail/tarantool-patches/2019-December/012958.html

Changes in v2:
- changed way of error handling, now we reserve pages before go to rtree
  lib
- changed test
- changed commit msg 

Changes in v3:
- added memtx_rtree_build_next function
- memory reservation is moved to memtx_rtree_build_next


 src/box/memtx_engine.h |  12 +++++
 src/box/memtx_rtree.c  |  20 +++++++-
 src/box/memtx_space.c  |  12 -----
 test/box/cfg.result    | 101 +++++++++++++++++++++++++++++++++++++++++
 test/box/cfg.test.lua  |  28 ++++++++++++
 5 files changed, 160 insertions(+), 13 deletions(-)

diff --git a/src/box/memtx_engine.h b/src/box/memtx_engine.h
index f562c66df..f6335cc66 100644
--- a/src/box/memtx_engine.h
+++ b/src/box/memtx_engine.h
@@ -87,6 +87,18 @@ enum memtx_recovery_state {
 /** Memtx extents pool, available to statistics. */
 extern struct mempool memtx_index_extent_pool;
 
+enum memtx_reserve_extents_num{
+	/**
+	 * This number is calculated based on the
+	 * max (realistic) number of insertions
+	 * a deletion from a B-tree or an R-tree
+	 * can lead to, and, as a result, the max
+	 * number of new block allocations.
+	 */
+	RESERVE_EXTENTS_BEFORE_DELETE = 8,
+	RESERVE_EXTENTS_BEFORE_REPLACE = 16
+};
+
 /**
  * The size of the biggest memtx iterator. Used with
  * mempool_create. This is the size of the block that will be
diff --git a/src/box/memtx_rtree.c b/src/box/memtx_rtree.c
index 8badad797..0d1283590 100644
--- a/src/box/memtx_rtree.c
+++ b/src/box/memtx_rtree.c
@@ -242,6 +242,24 @@ memtx_rtree_index_replace(struct index *base, struct tuple *old_tuple,
 	return 0;
 }
 
+static int memtx_rtree_index_build_next(struct index *base, struct tuple *tuple)
+{
+    /**
+     * There is no error handling in rtree lib. We need to be sure that
+     * memory allocation does not fail.
+     */
+    struct memtx_engine *memtx = (struct memtx_engine *)base->engine;
+    if (memtx_index_extent_reserve(memtx,
+                                   RESERVE_EXTENTS_BEFORE_REPLACE) != 0)
+    return -1;
+    struct memtx_rtree_index *index = (struct memtx_rtree_index *)base;
+    struct rtree_rect rect;
+    if (extract_rectangle(&rect, tuple, base->def) != 0)
+        return -1;
+    rtree_insert(&index->tree, &rect, tuple);
+        return 0;
+}
+
 static struct iterator *
 memtx_rtree_index_create_iterator(struct index *base,  enum iterator_type type,
 				  const char *key, uint32_t part_count)
@@ -334,7 +352,7 @@ static const struct index_vtab memtx_rtree_index_vtab = {
 	/* .reset_stat = */ generic_index_reset_stat,
 	/* .begin_build = */ generic_index_begin_build,
 	/* .reserve = */ generic_index_reserve,
-	/* .build_next = */ generic_index_build_next,
+	/* .build_next = */ memtx_rtree_index_build_next,
 	/* .end_build = */ generic_index_end_build,
 };
 
diff --git a/src/box/memtx_space.c b/src/box/memtx_space.c
index 6ef84e045..da20b9196 100644
--- a/src/box/memtx_space.c
+++ b/src/box/memtx_space.c
@@ -103,18 +103,6 @@ memtx_space_replace_no_keys(struct space *space, struct tuple *old_tuple,
 	return -1;
 }
 
-enum {
-	/**
-	 * This number is calculated based on the
-	 * max (realistic) number of insertions
-	 * a deletion from a B-tree or an R-tree
-	 * can lead to, and, as a result, the max
-	 * number of new block allocations.
-	 */
-	RESERVE_EXTENTS_BEFORE_DELETE = 8,
-	RESERVE_EXTENTS_BEFORE_REPLACE = 16
-};
-
 /**
  * A short-cut version of replace() used during bulk load
  * from snapshot.
diff --git a/test/box/cfg.result b/test/box/cfg.result
index 5370bb870..4ed8c9efe 100644
--- a/test/box/cfg.result
+++ b/test/box/cfg.result
@@ -580,3 +580,104 @@ test_run:cmd("cleanup server cfg_tester6")
  | ---
  | - true
  | ...
+
+--
+-- gh-4619-RTREE-doesn't-handle-OOM-properly
+--
+test_run:cmd('create server rtree with script = "box/lua/cfg_test1.lua"')
+ | ---
+ | - true
+ | ...
+test_run:cmd("start server rtree")
+ | ---
+ | - true
+ | ...
+test_run:cmd('switch rtree')
+ | ---
+ | - true
+ | ...
+box.cfg{memtx_memory = 3221225472}
+ | ---
+ | ...
+math = require("math")
+ | ---
+ | ...
+rtreespace = box.schema.create_space('rtree', {if_not_exists = true})
+ | ---
+ | ...
+rtreespace:create_index('pk', {if_not_exists = true})
+ | ---
+ | - unique: true
+ |   parts:
+ |   - type: unsigned
+ |     is_nullable: false
+ |     fieldno: 1
+ |   id: 0
+ |   space_id: 512
+ |   type: TREE
+ |   name: pk
+ | ...
+rtreespace:create_index('target', {type='rtree', dimension = 3, parts={2, 'array'},unique = false, if_not_exists = true,})
+ | ---
+ | - parts:
+ |   - type: array
+ |     is_nullable: false
+ |     fieldno: 2
+ |   dimension: 3
+ |   id: 1
+ |   type: RTREE
+ |   space_id: 512
+ |   name: target
+ | ...
+count = 2e6
+ | ---
+ | ...
+for i = 1, count do box.space.rtree:insert{i, {(i + 1) -\
+    math.floor((i + 1)/7000) * 7000, (i + 2) - math.floor((i + 2)/7000) * 7000,\
+    (i + 3) - math.floor((i + 3)/7000) * 7000}} end
+ | ---
+ | ...
+rtreespace:count()
+ | ---
+ | - 2000000
+ | ...
+box.snapshot()
+ | ---
+ | - ok
+ | ...
+test_run:cmd('switch default')
+ | ---
+ | - true
+ | ...
+test_run:cmd("stop server rtree")
+ | ---
+ | - true
+ | ...
+test_run:cmd("start server rtree with crash_expected=True")
+ | ---
+ | - false
+ | ...
+fio = require('fio')
+ | ---
+ | ...
+fh = fio.open(fio.pathjoin(fio.cwd(), 'cfg_test1.log'), {'O_RDONLY'})
+ | ---
+ | ...
+size = fh:seek(0, 'SEEK_END')
+ | ---
+ | ...
+fh:seek(-256, 'SEEK_END')
+ | ---
+ | - 11155
+ | ...
+line = fh:read(256)
+ | ---
+ | ...
+fh:close()
+ | ---
+ | - true
+ | ...
+string.match(line, 'Failed to allocate') ~= nil
+ | ---
+ | - true
+ | ...
diff --git a/test/box/cfg.test.lua b/test/box/cfg.test.lua
index 56ccb6767..b13f10c65 100644
--- a/test/box/cfg.test.lua
+++ b/test/box/cfg.test.lua
@@ -141,3 +141,31 @@ test_run:cmd("start server cfg_tester6")
 test_run:grep_log('cfg_tester6', 'set \'vinyl_memory\' configuration option to 1073741824', 1000)
 test_run:cmd("stop server cfg_tester6")
 test_run:cmd("cleanup server cfg_tester6")
+
+--
+-- gh-4619-RTREE-doesn't-handle-OOM-properly
+--
+test_run:cmd('create server rtree with script = "box/lua/cfg_test1.lua"')
+test_run:cmd("start server rtree")
+test_run:cmd('switch rtree')
+box.cfg{memtx_memory = 3221225472}
+math = require("math")
+rtreespace = box.schema.create_space('rtree', {if_not_exists = true})
+rtreespace:create_index('pk', {if_not_exists = true})
+rtreespace:create_index('target', {type='rtree', dimension = 3, parts={2, 'array'},unique = false, if_not_exists = true,})
+count = 2e6
+for i = 1, count do box.space.rtree:insert{i, {(i + 1) -\
+    math.floor((i + 1)/7000) * 7000, (i + 2) - math.floor((i + 2)/7000) * 7000,\
+    (i + 3) - math.floor((i + 3)/7000) * 7000}} end
+rtreespace:count()
+box.snapshot()
+test_run:cmd('switch default')
+test_run:cmd("stop server rtree")
+test_run:cmd("start server rtree with crash_expected=True")
+fio = require('fio')
+fh = fio.open(fio.pathjoin(fio.cwd(), 'cfg_test1.log'), {'O_RDONLY'})
+size = fh:seek(0, 'SEEK_END')
+fh:seek(-256, 'SEEK_END')
+line = fh:read(256)
+fh:close()
+string.match(line, 'Failed to allocate') ~= nil
-- 
2.17.2 (Apple Git-113)

Re: [Tarantool-patches] [PATCH v3] memtx: fix out of memory handling for rtree

[Konstantin Osipov]

* Olga Arkhangelskaia <arkholga@tarantool.org> [19/12/19 16:44]:
> When tarantool tries to recover rtree from a snapshot and memtx_memory value
> is lower than it has been when the snapshot was created, server suffers from
> segmentation fault. This happens because there is no out of memory error
> handling in rtree lib. In another words, we do not check the result of
> malloc operation.
> The execution flow in case of recovery uses different way and the secondary
> keys are build in batches. There is no separate implementations for rtree of
> build_next function. And the way with no checks and reservation is used
> (insex_replace). The patch adds memtx_rtree_build_next implementation to
> check and insert keys. Although this gives us no additional optimization as in
> case of memtx_tree, the memory reservation prevents tarantool from segmentation
> fault.
> If there is not enough memory to be reserved - server will fail
> gently with the "Failed to allocate" error message.

Why not add memtx_index_extent_reserve() to
generic_index_build_next(), this would be a shorter version which
does the same thing?


-- 
Konstantin Osipov, Moscow, Russia

Re: [Tarantool-patches] [PATCH v3] memtx: fix out of memory handling for rtree

[Olga Arkhangelskaia]

On 19/12/2019 17:14, Konstantin Osipov wrote:
> * Olga Arkhangelskaia <arkholga@tarantool.org> [19/12/19 16:44]:
>> When tarantool tries to recover rtree from a snapshot and memtx_memory value
>> is lower than it has been when the snapshot was created, server suffers from
>> segmentation fault. This happens because there is no out of memory error
>> handling in rtree lib. In another words, we do not check the result of
>> malloc operation.
>> The execution flow in case of recovery uses different way and the secondary
>> keys are build in batches. There is no separate implementations for rtree of
>> build_next function. And the way with no checks and reservation is used
>> (insex_replace). The patch adds memtx_rtree_build_next implementation to
>> check and insert keys. Although this gives us no additional optimization as in
>> case of memtx_tree, the memory reservation prevents tarantool from segmentation
>> fault.
>> If there is not enough memory to be reserved - server will fail
>> gently with the "Failed to allocate" error message.
> Why not add memtx_index_extent_reserve() to
> generic_index_build_next(), this would be a shorter version which
> does the same thing?
>
>
I can't agree - everything that has memtx_ should be in memtx, because 
generic is used by vinyl, and sysview.

And the only way I see do it generic - is to use index_reserve? Did you 
mean index_reserve, that has  memtx_index_extent_reserve( inside?

In this case it is not shorter.

Re: [Tarantool-patches] [PATCH v3] memtx: fix out of memory handling for rtree

[Konstantin Osipov]

* Olga Arkhangelskaia <arkholga@tarantool.org> [19/12/19 17:45]:
> I can't agree - everything that has memtx_ should be in memtx, because
> generic is used by vinyl, and sysview.

Neither vinyl nor sysview build secondary indexes using
build_next. This name - generic_* is a conversion mistake
introduced during C++ -> C transition, it should be
memtx_default_build_next. The generic build next should
assert(false), it should be never called. If, for whatever reason,
it's called, you still can split have a generic_memtx_build_next

> And the only way I see do it generic - is to use index_reserve? Did you mean
> index_reserve, that has  memtx_index_extent_reserve( inside?
> 
> In this case it is not shorter.
> 

-- 
Konstantin Osipov, Moscow, Russia