[Tarantool-patches] [PATCH rfc] rtree: added variable to store error information

[Tarantool-patches] [PATCH rfc] rtree: added variable to store error information

[Olga Arkhangelskaia]

There is no error handling during memory allocation operations in
rtree. This results in SEGV_MAPERR error.

There is any mechanism for error handling in libsalad, because it
should be independent from tarantool. However, in case of memory
errors(failed allocation) tarantool should notify user and stop
execution correctly. Now we immediately return and notify caller through
variable that error has happened.
Closes #4916
---
Branch:
https://github.com/tarantool/tarantool/tree/OKriw/gh-4619-RTREE-doesnt-handle-OOM-properly

 src/box/memtx_rtree.c       |  8 +++++++-
 src/lib/salad/rtree.c       | 13 ++++++++++++-
 src/lib/salad/rtree.h       |  3 ++-
 test/box-tap/cfg.test.lua   | 30 +++++++++++++++++++++++++++++-
 test/unit/rtree.cc          | 26 ++++++++++++++++++++------
 test/unit/rtree_iterator.cc | 22 +++++++++++++++++-----
 test/unit/rtree_multidim.cc |  5 ++++-
 7 files changed, 91 insertions(+), 16 deletions(-)

diff --git a/src/box/memtx_rtree.c b/src/box/memtx_rtree.c
index 8badad797..23db13c43 100644
--- a/src/box/memtx_rtree.c
+++ b/src/box/memtx_rtree.c
@@ -225,12 +225,18 @@ memtx_rtree_index_replace(struct index *base, struct tuple *old_tuple,
 			  struct tuple **result)
 {
 	(void)mode;
+	int err = 0;
 	struct memtx_rtree_index *index = (struct memtx_rtree_index *)base;
 	struct rtree_rect rect;
 	if (new_tuple) {
 		if (extract_rectangle(&rect, new_tuple, base->def) != 0)
 			return -1;
-		rtree_insert(&index->tree, &rect, new_tuple);
+		rtree_insert(&index->tree, &rect, new_tuple, &err);
+		if (err == 1) {
+			diag_set(OutOfMemory, sizeof(struct rtree),
+			 "rtree", "rtree_page");
+			return -1;
+		}
 	}
 	if (old_tuple) {
 		if (extract_rectangle(&rect, old_tuple, base->def) != 0)
diff --git a/src/lib/salad/rtree.c b/src/lib/salad/rtree.c
index 49f4206b8..ca900d88d 100644
--- a/src/lib/salad/rtree.c
+++ b/src/lib/salad/rtree.c
@@ -58,6 +58,10 @@ enum {
 	RTREE_BRANCH_DATA_SIZE = offsetof(struct rtree_page_branch, rect)
 };
 
+/* If during rtree_insert operation we have faced an error (oom most likely)
+ * we set rtree_err and return */
+bool rtree_err = false;
+
 struct rtree_page {
 	/* number of branches at page */
 	unsigned n;
@@ -548,6 +552,10 @@ rtree_split_page(struct rtree *tree, struct rtree_page *page,
 	unsigned k1 = tree->page_min_fill + k;
 	unsigned k2 = n - k1;
 	struct rtree_page *new_page = rtree_page_alloc(tree);
+	if (!new_page) {
+		rtree_err = true;
+		return NULL;
+	}
 	tree->n_pages++;
 	char taken[RTREE_MAXIMUM_BRANCHES_IN_PAGE];
 	memset(taken, 0, sizeof(taken));
@@ -982,7 +990,7 @@ rtree_destroy(struct rtree *tree)
 }
 
 void
-rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj)
+rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj, int *err)
 {
 	if (tree->root == NULL) {
 		tree->root = rtree_page_alloc(tree);
@@ -1000,6 +1008,9 @@ rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj)
 			tree->root = new_root;
 			tree->height++;
 			tree->n_pages++;
+		} if (rtree_err) {
+			*err = 1;
+			return;
 		}
 	}
 	tree->version++;
diff --git a/src/lib/salad/rtree.h b/src/lib/salad/rtree.h
index 995bbf502..8c829434f 100644
--- a/src/lib/salad/rtree.h
+++ b/src/lib/salad/rtree.h
@@ -271,9 +271,10 @@ rtree_search(const struct rtree *tree, const struct rtree_rect *rect,
  * @param tree - pointer to a tree
  * @param rect - rectangle to insert
  * @param obj - record to insert
+ * @param err - set in case of error during insertion
  */
 void
-rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj);
+rtree_insert(struct rtree *tree, struct rtree_rect *rect, record_t obj, int *err);
 
 /**
  * @brief Remove the record from a tree
diff --git a/test/box-tap/cfg.test.lua b/test/box-tap/cfg.test.lua
index d529447bb..b2625f986 100755
--- a/test/box-tap/cfg.test.lua
+++ b/test/box-tap/cfg.test.lua
@@ -6,7 +6,7 @@ local socket = require('socket')
 local fio = require('fio')
 local uuid = require('uuid')
 local msgpack = require('msgpack')
-test:plan(104)
+test:plan(106)
 
 --------------------------------------------------------------------------------
 -- Invalid values
@@ -592,6 +592,34 @@ box.cfg{read_only=true}
 ]]
 test:is(run_script(code), PANIC, "panic on bootstrapping a read-only instance as master")
 
+--
+-- gh-4619-RTREE-doesn't-handle-OOM-properly
+--
+code1 = string.format([[
+box.cfg{memtx_memory = %u}
+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
+box.snapshot()
+os.exit(0)
+]], 3221225472)
+code2 = "box.cfg{}"
+test:is(run_script(code1), 0, "allocate memory for rtree")
+test:is(run_script(code2), 0, "panic on out of memory")
 
 test:check()
 os.exit(0)
diff --git a/test/unit/rtree.cc b/test/unit/rtree.cc
index 81a9947e4..68f876292 100644
--- a/test/unit/rtree.cc
+++ b/test/unit/rtree.cc
@@ -36,7 +36,7 @@ simple_check()
 	struct rtree_iterator iterator;
 	rtree_iterator_init(&iterator);
 	const size_t rounds = 2000;
-
+	int err = 0;
 	header();
 
 	struct rtree tree;
@@ -53,7 +53,9 @@ simple_check()
 		if (rtree_search(&tree, &rect, SOP_EQUALS, &iterator)) {
 			fail("element already in tree (1)", "true");
 		}
-		rtree_insert(&tree, &rect, rec);
+		rtree_insert(&tree, &rect, rec, &err);
+		if (err == 1)
+			printf("Tree is out of memory\n");
 	}
 	if (rtree_number_of_records(&tree) != rounds) {
 		fail("Tree count mismatch (1)", "true");
@@ -92,7 +94,10 @@ simple_check()
 		if (rtree_search(&tree, &rect, SOP_EQUALS, &iterator)) {
 			fail("element already in tree (2)", "true");
 		}
-		rtree_insert(&tree, &rect, rec);
+		err = 0;
+		rtree_insert(&tree, &rect, rec, &err);
+		if (err == 1)
+			printf("Tree is out of memory\n");
 	}
 	if (rtree_number_of_records(&tree) != rounds) {
 		fail("Tree count mismatch (2)", "true");
@@ -132,7 +137,10 @@ simple_check()
 		if (rtree_search(&tree, &rect, SOP_BELONGS, &iterator)) {
 			fail("element already in tree (3)", "true");
 		}
-		rtree_insert(&tree, &rect, rec);
+		err = 0;
+		rtree_insert(&tree, &rect, rec, &err);
+		if (err == 1)
+			printf("Tree is out of memory\n");
 	}
 	if (rtree_number_of_records(&tree) != rounds) {
 		fail("Tree count mismatch (3)", "true");
@@ -172,7 +180,10 @@ simple_check()
 		if (rtree_search(&tree, &rect, SOP_CONTAINS, &iterator)) {
 			fail("element already in tree (4)", "true");
 		}
-		rtree_insert(&tree, &rect, rec);
+		err = 0;
+		rtree_insert(&tree, &rect, rec, &err);
+		if (err == 1)
+			printf("Tree is out of memory\n");
 	}
 	if (rtree_number_of_records(&tree) != rounds) {
 		fail("Tree count mismatch (4)", "true");
@@ -213,9 +224,12 @@ simple_check()
 static void
 rtree_test_build(struct rtree *tree, struct rtree_rect *arr, int count)
 {
+	int err = 0;
 	for (ssize_t i = 0; i < count; i++) {
 		record_t rec = (record_t)(i + 1);
-		rtree_insert(tree, &arr[i], rec);
+		rtree_insert(tree, &arr[i], rec, &err);
+		if (err == 1)
+			printf("Tree is out of memory\n");
 	}
 }
 
diff --git a/test/unit/rtree_iterator.cc b/test/unit/rtree_iterator.cc
index 5ab5b4f48..a4a1271ef 100644
--- a/test/unit/rtree_iterator.cc
+++ b/test/unit/rtree_iterator.cc
@@ -34,6 +34,7 @@ iterator_check()
 	header();
 
 	struct rtree tree;
+	int err = 0;
 	rtree_init(&tree, 2, extent_size,
 		   extent_alloc, extent_free, &extent_count,
 		   RTREE_EUCLID);
@@ -51,7 +52,9 @@ iterator_check()
 		coord_t coord = i * 2 * count2; /* note that filled with even numbers */
 		for (size_t j = 0; j < count2; j++) {
 			rtree_set2d(&rect, coord, coord, coord + j, coord + j);
-			rtree_insert(&tree, &rect, record_t(++count));
+			rtree_insert(&tree, &rect, record_t(++count), &err);
+			if (err == 1)
+				printf("Tree is out of memory\n");
 		}
 	}
 	printf("Test tree size: %d\n", (int)rtree_number_of_records(&tree));
@@ -207,7 +210,7 @@ iterator_invalidate_check()
 	const size_t attempt_count = 100;
 
 	struct rtree_rect rect;
-
+	int err = 0;
 	/* invalidation during deletion */
 	srand(0);
 	for (size_t attempt = 0; attempt < attempt_count; attempt++) {
@@ -226,7 +229,9 @@ iterator_invalidate_check()
 
 		for (size_t i = 0; i < test_size; i++) {
 			rtree_set2d(&rect, i, i, i, i);
-			rtree_insert(&tree, &rect, record_t(i+1));
+			rtree_insert(&tree, &rect, record_t(i+1), &err);
+			if (err == 1)
+				printf("Tree is out of memory\n");
 		}
 		rtree_set2d(&rect, 0, 0, test_size, test_size);
 		if (!rtree_search(&tree, &rect, SOP_BELONGS, &iterators[0]) ||
@@ -258,6 +263,7 @@ iterator_invalidate_check()
 
 	/* invalidation during insertion */
 	srand(0);
+	err = 0;
 	for (size_t attempt = 0; attempt < attempt_count; attempt++) {
 		size_t ins_pos = rand() % test_size;
 		size_t ins_cnt = rand() % max_insert_count + 1;
@@ -272,7 +278,10 @@ iterator_invalidate_check()
 
 		for (size_t i = 0; i < test_size; i++) {
 			rtree_set2d(&rect, i, i, i, i);
-			rtree_insert(&tree, &rect, record_t(i+1));
+			rtree_insert(&tree, &rect, record_t(i+1), &err);
+			if(err == 1)
+				printf("Tree is out of memory\n");
+
 		}
 		rtree_set2d(&rect, 0, 0, test_size, test_size);
 		rtree_search(&tree, &rect, SOP_BELONGS, &iterators[0]);
@@ -287,7 +296,10 @@ iterator_invalidate_check()
 		}
 		for (size_t i = ins_pos; i < ins_pos + ins_cnt; i++) {
 			rtree_set2d(&rect, i, i, i, i);
-			rtree_insert(&tree, &rect, record_t(test_size + i - ins_pos + 1));
+			err = 0;
+			rtree_insert(&tree, &rect, record_t(test_size + i - ins_pos + 1), &err);
+			if (err == 1)
+				printf("Tree is out of memory\n");
 		}
 		for (size_t i = 0; i < test_size; i++) {
 			if (rtree_iterator_next(&iterators[i])) {
diff --git a/test/unit/rtree_multidim.cc b/test/unit/rtree_multidim.cc
index 843b437e3..3e06b2e48 100644
--- a/test/unit/rtree_multidim.cc
+++ b/test/unit/rtree_multidim.cc
@@ -490,6 +490,7 @@ rand_test()
 	CBoxSet<DIMENSION> set;
 
 	struct rtree tree;
+	int err = 0;
 	rtree_init(&tree, DIMENSION, extent_size,
 		   extent_alloc, extent_free, &page_count,
 		   RTREE_EUCLID);
@@ -512,7 +513,9 @@ rand_test()
 			size_t id = set.AddBox(box);
 			struct rtree_rect rt;
 			box.FillRTreeRect(&rt);
-			rtree_insert(&tree, &rt, (void *)(id + 1));
+			rtree_insert(&tree, &rt, (void *)(id + 1), &err);
+			if (err == 1)
+				printf("Tree is out of memory\n");
 		} else {
 			size_t id = set.RandUsedID();
 			struct rtree_rect rt;
-- 
2.20.1 (Apple Git-117)

Re: [Tarantool-patches] [PATCH rfc] rtree: added variable to store error information

[Konstantin Osipov]

* Olga Arkhangelskaia <arkholga@tarantool.org> [19/11/14 13:51]:
> There is no error handling during memory allocation operations in
> rtree. This results in SEGV_MAPERR error.
> 
> There is any mechanism for error handling in libsalad, because it
> should be independent from tarantool. However, in case of memory
> errors(failed allocation) tarantool should notify user and stop
> execution correctly. Now we immediately return and notify caller through
> variable that error has happened.
> Closes #4916

rtree insert should not get started if it may run out of memory,
since it splits pages and needs to allocate memory on rollback
path.

The proper fix is to not start insert operation if there is no
memory.


-- 
Konstantin Osipov, Moscow, Russia