Skip to content

BPS tree can get invalidated in rare cases in presense of a read view #11979

@mkostoevr

Description

@mkostoevr

We've removed touching garbage blocks on pop in 52b3d4b, this can lead to a bug similar to tarantool/tarantool-ee#1511. Unlike the BPS vector, here we probably can keep the change, but make sure there's no touches performed between a new block creation via bps_tree_garbage_pop and assignment of its last field. The problem seems to only exist in the insertion routine.

Here's reproduce.patch for a854a65 failing the debug check, apply with git apply --verbose reproduce.patch.
From 3c04400696224aebb3e14c3fa3cef39469e0495b Mon Sep 17 00:00:00 2001
From: Magomed Kostoev <m.kostoev@tarantool.org>
Date: Fri, 24 Oct 2025 15:06:10 +0300
Subject: [PATCH] Reproduce

---
 test/unit/bps_tree.cc | 75 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 73 insertions(+), 2 deletions(-)

diff --git a/test/unit/bps_tree.cc b/test/unit/bps_tree.cc
index 6a04facd64..d131dd01bd 100644
--- a/test/unit/bps_tree.cc
+++ b/test/unit/bps_tree.cc
@@ -82,6 +82,28 @@ compare(type_t a, type_t b);
 #undef bps_tree_key_t
 #undef bps_tree_arg_t
 
+/* the same tree with extent size x2 of block size */
+#define bx4_TREE_EXTENT_SIZE (SMALL_BLOCK_SIZE * 4)
+#define BPS_TREE_NAME test_bx4
+#define BPS_TREE_BLOCK_SIZE SMALL_BLOCK_SIZE
+#define BPS_TREE_EXTENT_SIZE bx4_TREE_EXTENT_SIZE
+#define BPS_TREE_IS_IDENTICAL(a, b) (a == b)
+#define BPS_TREE_COMPARE(a, b, arg) compare(a, b)
+#define BPS_TREE_COMPARE_KEY(a, b, arg) compare(a, b)
+#define bps_tree_elem_t type_t
+#define bps_tree_key_t type_t
+#define bps_tree_arg_t int
+#include "salad/bps_tree.h"
+#undef BPS_TREE_NAME
+#undef BPS_TREE_BLOCK_SIZE
+#undef BPS_TREE_EXTENT_SIZE
+#undef BPS_TREE_IS_IDENTICAL
+#undef BPS_TREE_COMPARE
+#undef BPS_TREE_COMPARE_KEY
+#undef bps_tree_elem_t
+#undef bps_tree_key_t
+#undef bps_tree_arg_t
+
 struct elem_t {
 	long info;
 	long marker;
@@ -179,11 +201,10 @@ static bool extent_alloc_failure = false;
 static void *
 extent_alloc(struct matras_allocator *allocator)
 {
-	(void)allocator;
 	if (extent_alloc_failure)
 		return NULL;
 	++extents_count;
-	return xmalloc(BPS_TREE_EXTENT_SIZE);
+	return xmalloc(allocator->extent_size);
 }
 
 static void
@@ -992,6 +1013,53 @@ gh_11788_oom_on_first_insertion_test()
 	check_plan();
 }
 
+static void
+gh_xxxxx_head_view_changes_test()
+{
+	plan(1);
+	header();
+
+	/* Create the test-specific allocator. */
+	struct matras_allocator bx4_allocator;
+	matras_allocator_create(&bx4_allocator, bx4_TREE_EXTENT_SIZE,
+				extent_alloc, extent_free);
+
+	test_bx4 tree;
+	test_bx4_view view;
+	struct test_bx4_iterator iterator;
+
+	test_bx4_create(&tree, 0, &bx4_allocator, NULL);
+	const int max_count_in_leaf = BPS_TREE_test_bx4_MAX_COUNT_IN_LEAF;
+	/* Four leafs initially. */
+	const int init_size = max_count_in_leaf * 4;
+	/* Insert into the third leaf for the test. */
+	const int to_insert = max_count_in_leaf * 2 + (max_count_in_leaf / 2);
+	type_t init_data[init_size];
+	/* Fill the tree of 4 leafs, but skip the value to be inserted. */
+	for (int i = 0; i < init_size; i++) {
+		if (i < to_insert)
+			init_data[i] = i;
+		else
+			init_data[i] = i + 1;
+	}
+	if (test_bx4_build(&tree, init_data, init_size))
+		fail("building failed", "true");
+	test_bx4_print(&tree, TYPE_F);
+	test_bx4_view_create(&view, &tree);
+	test_bx4_insert(&tree, to_insert, NULL, NULL);
+	test_bx4_print(&tree, TYPE_F);
+	if (test_bx4_debug_check(&tree) != 0)
+		fail("debug check non-zero", "true");
+	test_bx4_destroy(&tree);
+	ok(true, "head view changes");
+
+	/* Destroy the test-specific allocator. */
+	matras_allocator_destroy(&bx4_allocator);
+
+	footer();
+	check_plan();
+}
+
 int
 main(void)
 {
@@ -1001,6 +1069,9 @@ main(void)
 	matras_allocator_create(&allocator, BPS_TREE_EXTENT_SIZE,
 				extent_alloc, extent_free);
 
+	gh_xxxxx_head_view_changes_test();
+	return 0;
+
 	simple_check();
 	compare_with_sptree_check();
 	compare_with_sptree_check_branches();
-- 
2.43.0

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions