-
Notifications
You must be signed in to change notification settings - Fork 403
Closed
Labels
Description
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
Reactions are currently unavailable