1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
2 // vim: ts=8 sw=2 smarttab
11 #include "crimson/common/log.h"
12 #include "crimson/os/seastore/onode_manager/staged-fltree/node.h"
13 #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h"
14 #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/seastore.h"
15 #include "crimson/os/seastore/onode_manager/staged-fltree/node_layout.h"
16 #include "crimson/os/seastore/onode_manager/staged-fltree/tree.h"
17 #include "crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h"
19 #include "test/crimson/gtest_seastar.h"
20 #include "test/crimson/seastore/transaction_manager_test_state.h"
21 #include "test_value.h"
23 using namespace crimson::os::seastore::onode
;
25 #define INTR(fun, t) \
33 #define INTR_R(fun, t, args...) \
37 return fun(tr, args); \
41 #define INTR_WITH_PARAM(fun, c, b, v) \
45 return fun(c, L_ADDR_MIN, b, v); \
50 constexpr bool IS_DUMMY_SYNC
= false;
51 using DummyManager
= DummyNodeExtentManager
<IS_DUMMY_SYNC
>;
53 using UnboundedBtree
= Btree
<UnboundedValue
>;
55 [[maybe_unused
]] seastar::logger
& logger() {
56 return crimson::get_logger(ceph_subsys_test
);
59 ghobject_t
make_ghobj(
60 shard_t shard
, pool_t pool
, crush_hash_t crush
,
61 std::string ns
, std::string oid
, snap_t snap
, gen_t gen
) {
62 return ghobject_t
{shard_id_t
{shard
}, pool
, crush
, ns
, oid
, snap
, gen
};
65 // return a key_view_t and its underlying memory buffer.
66 // the buffer needs to be freed manually.
67 std::pair
<key_view_t
, void*> build_key_view(const ghobject_t
& hobj
) {
68 key_hobj_t
key_hobj(hobj
);
69 size_t key_size
= sizeof(shard_pool_crush_t
) + sizeof(snap_gen_t
) +
70 ns_oid_view_t::estimate_size
<KeyT::HOBJ
>(key_hobj
);
71 void* p_mem
= std::malloc(key_size
);
74 char* p_fill
= (char*)p_mem
+ key_size
;
76 auto spc
= shard_pool_crush_t::from_key
<KeyT::HOBJ
>(key_hobj
);
77 p_fill
-= sizeof(shard_pool_crush_t
);
78 std::memcpy(p_fill
, &spc
, sizeof(shard_pool_crush_t
));
79 key_view
.set(*reinterpret_cast<const shard_pool_crush_t
*>(p_fill
));
81 auto p_ns_oid
= p_fill
;
82 ns_oid_view_t::test_append
<KeyT::HOBJ
>(key_hobj
, p_fill
);
83 ns_oid_view_t
ns_oid_view(p_ns_oid
);
84 key_view
.set(ns_oid_view
);
86 auto sg
= snap_gen_t::from_key
<KeyT::HOBJ
>(key_hobj
);
87 p_fill
-= sizeof(snap_gen_t
);
88 ceph_assert(p_fill
== (char*)p_mem
);
89 std::memcpy(p_fill
, &sg
, sizeof(snap_gen_t
));
90 key_view
.set(*reinterpret_cast<const snap_gen_t
*>(p_fill
));
92 return {key_view
, p_mem
};
96 struct a_basic_test_t
: public seastar_test_suite_t
{};
98 TEST_F(a_basic_test_t
, 1_basic_sizes
)
102 " node_header_t: {}\n"
103 " shard_pool_t: {}\n"
104 " shard_pool_crush_t: {}\n"
110 " node_fields_0_t: {}\n"
111 " node_fields_1_t: {}\n"
112 " node_fields_2_t: {}\n"
113 " internal_fields_3_t: {}\n"
114 " leaf_fields_3_t: {}\n"
115 " internal_sub_item_t: {}",
116 sizeof(node_header_t
), sizeof(shard_pool_t
),
117 sizeof(shard_pool_crush_t
), sizeof(crush_t
), sizeof(snap_gen_t
),
118 sizeof(slot_0_t
), sizeof(slot_1_t
), sizeof(slot_3_t
),
119 sizeof(node_fields_0_t
), sizeof(node_fields_1_t
), sizeof(node_fields_2_t
),
120 sizeof(internal_fields_3_t
), sizeof(leaf_fields_3_t
), sizeof(internal_sub_item_t
)
123 auto hobj
= make_ghobj(0, 0, 0, "n", "o", 0, 0);
124 key_hobj_t
key(hobj
);
125 auto [key_view
, p_mem
] = build_key_view(hobj
);
126 value_config_t value
;
127 value
.payload_size
= 8;
128 #define _STAGE_T(NodeType) node_to_stage_t<typename NodeType::node_stage_t>
129 #define NXT_T(StageType) staged<typename StageType::next_param_t>
132 "Bytes of a key-value insertion (full-string):\n"
133 " s-p-c, 'n'-'o', s-g => value_payload(8): typically internal 43B, leaf 59B\n"
134 " InternalNode0: {} {} {}\n"
135 " InternalNode1: {} {} {}\n"
136 " InternalNode2: {} {}\n"
137 " InternalNode3: {}\n"
138 " LeafNode0: {} {} {}\n"
139 " LeafNode1: {} {} {}\n"
140 " LeafNode2: {} {}\n"
142 _STAGE_T(InternalNode0
)::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
143 NXT_T(_STAGE_T(InternalNode0
))::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
144 NXT_T(NXT_T(_STAGE_T(InternalNode0
)))::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
145 _STAGE_T(InternalNode1
)::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
146 NXT_T(_STAGE_T(InternalNode1
))::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
147 NXT_T(NXT_T(_STAGE_T(InternalNode1
)))::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
148 _STAGE_T(InternalNode2
)::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
149 NXT_T(_STAGE_T(InternalNode2
))::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
150 _STAGE_T(InternalNode3
)::template insert_size
<KeyT::VIEW
>(key_view
, i_value
),
151 _STAGE_T(LeafNode0
)::template insert_size
<KeyT::HOBJ
>(key
, value
),
152 NXT_T(_STAGE_T(LeafNode0
))::template insert_size
<KeyT::HOBJ
>(key
, value
),
153 NXT_T(NXT_T(_STAGE_T(LeafNode0
)))::template insert_size
<KeyT::HOBJ
>(key
, value
),
154 _STAGE_T(LeafNode1
)::template insert_size
<KeyT::HOBJ
>(key
, value
),
155 NXT_T(_STAGE_T(LeafNode1
))::template insert_size
<KeyT::HOBJ
>(key
, value
),
156 NXT_T(NXT_T(_STAGE_T(LeafNode1
)))::template insert_size
<KeyT::HOBJ
>(key
, value
),
157 _STAGE_T(LeafNode2
)::template insert_size
<KeyT::HOBJ
>(key
, value
),
158 NXT_T(_STAGE_T(LeafNode2
))::template insert_size
<KeyT::HOBJ
>(key
, value
),
159 _STAGE_T(LeafNode3
)::template insert_size
<KeyT::HOBJ
>(key
, value
)
164 TEST_F(a_basic_test_t
, 2_node_sizes
)
167 auto nm
= NodeExtentManager::create_dummy(IS_DUMMY_SYNC
);
168 auto t
= make_test_transaction();
169 ValueBuilderImpl
<UnboundedValue
> vb
;
170 context_t c
{*nm
, vb
, *t
};
171 std::array
<std::pair
<NodeImplURef
, NodeExtentMutable
>, 16> nodes
= {
172 INTR_WITH_PARAM(InternalNode0::allocate
, c
, false, 1u).unsafe_get0().make_pair(),
173 INTR_WITH_PARAM(InternalNode1::allocate
, c
, false, 1u).unsafe_get0().make_pair(),
174 INTR_WITH_PARAM(InternalNode2::allocate
, c
, false, 1u).unsafe_get0().make_pair(),
175 INTR_WITH_PARAM(InternalNode3::allocate
, c
, false, 1u).unsafe_get0().make_pair(),
176 INTR_WITH_PARAM(InternalNode0::allocate
, c
, true, 1u).unsafe_get0().make_pair(),
177 INTR_WITH_PARAM(InternalNode1::allocate
, c
, true, 1u).unsafe_get0().make_pair(),
178 INTR_WITH_PARAM(InternalNode2::allocate
, c
, true, 1u).unsafe_get0().make_pair(),
179 INTR_WITH_PARAM(InternalNode3::allocate
, c
, true, 1u).unsafe_get0().make_pair(),
180 INTR_WITH_PARAM(LeafNode0::allocate
, c
, false, 0u).unsafe_get0().make_pair(),
181 INTR_WITH_PARAM(LeafNode1::allocate
, c
, false, 0u).unsafe_get0().make_pair(),
182 INTR_WITH_PARAM(LeafNode2::allocate
, c
, false, 0u).unsafe_get0().make_pair(),
183 INTR_WITH_PARAM(LeafNode3::allocate
, c
, false, 0u).unsafe_get0().make_pair(),
184 INTR_WITH_PARAM(LeafNode0::allocate
, c
, true, 0u).unsafe_get0().make_pair(),
185 INTR_WITH_PARAM(LeafNode1::allocate
, c
, true, 0u).unsafe_get0().make_pair(),
186 INTR_WITH_PARAM(LeafNode2::allocate
, c
, true, 0u).unsafe_get0().make_pair(),
187 INTR_WITH_PARAM(LeafNode3::allocate
, c
, true, 0u).unsafe_get0().make_pair()
189 std::ostringstream oss
;
190 oss
<< "\nallocated nodes:";
191 for (auto iter
= nodes
.begin(); iter
!= nodes
.end(); ++iter
) {
193 auto& ref_node
= iter
->first
;
194 ref_node
->dump_brief(oss
);
196 logger().info("{}", oss
.str());
200 struct b_dummy_tree_test_t
: public seastar_test_suite_t
{
201 TransactionRef ref_t
;
202 std::unique_ptr
<UnboundedBtree
> tree
;
204 b_dummy_tree_test_t() = default;
206 seastar::future
<> set_up_fut() override final
{
207 ref_t
= make_test_transaction();
209 new UnboundedBtree(NodeExtentManager::create_dummy(IS_DUMMY_SYNC
))
211 return INTR(tree
->mkfs
, *ref_t
).handle_error(
212 crimson::ct_error::all_same_way([] {
213 ASSERT_FALSE("Unable to mkfs");
218 seastar::future
<> tear_down_fut() final
{
221 return seastar::now();
225 TEST_F(b_dummy_tree_test_t
, 3_random_insert_erase_leaf_node
)
228 logger().info("\n---------------------------------------------"
229 "\nrandomized leaf node insert:\n");
230 auto key_s
= ghobject_t();
231 auto key_e
= ghobject_t::get_max();
232 ASSERT_TRUE(INTR_R(tree
->find
, *ref_t
, key_s
).unsafe_get0().is_end());
233 ASSERT_TRUE(INTR(tree
->begin
, *ref_t
).unsafe_get0().is_end());
234 ASSERT_TRUE(INTR(tree
->last
, *ref_t
).unsafe_get0().is_end());
237 std::tuple
<test_item_t
, UnboundedBtree::Cursor
>> insert_history
;
239 auto f_validate_insert_new
= [this, &insert_history
] (
240 const ghobject_t
& key
, const test_item_t
& value
) {
241 auto conf
= UnboundedBtree::tree_value_config_t
{value
.get_payload_size()};
242 auto [cursor
, success
] = INTR_R(tree
->insert
,
243 *ref_t
, key
, conf
).unsafe_get0();
244 initialize_cursor_from_item(*ref_t
, key
, value
, cursor
, success
);
245 insert_history
.emplace(key
, std::make_tuple(value
, cursor
));
246 auto cursor_
= INTR_R(tree
->find
, *ref_t
, key
).unsafe_get0();
247 ceph_assert(cursor_
!= tree
->end());
248 ceph_assert(cursor_
.value() == cursor
.value());
249 validate_cursor_from_item(key
, value
, cursor_
);
250 return cursor
.value();
253 auto f_validate_erase
= [this, &insert_history
] (const ghobject_t
& key
) {
254 auto cursor_erase
= INTR_R(tree
->find
, *ref_t
, key
).unsafe_get0();
255 auto cursor_next
= INTR(cursor_erase
.get_next
, *ref_t
).unsafe_get0();
256 auto cursor_ret
= INTR_R(tree
->erase
, *ref_t
, cursor_erase
).unsafe_get0();
257 ceph_assert(cursor_erase
.is_end());
258 ceph_assert(cursor_ret
== cursor_next
);
259 auto cursor_lb
= INTR_R(tree
->lower_bound
, *ref_t
, key
).unsafe_get0();
260 ceph_assert(cursor_lb
== cursor_next
);
261 auto it
= insert_history
.find(key
);
262 ceph_assert(std::get
<1>(it
->second
).is_end());
263 insert_history
.erase(it
);
266 auto f_insert_erase_insert
= [&f_validate_insert_new
, &f_validate_erase
] (
267 const ghobject_t
& key
, const test_item_t
& value
) {
268 f_validate_insert_new(key
, value
);
269 f_validate_erase(key
);
270 return f_validate_insert_new(key
, value
);
273 auto values
= Values
<test_item_t
>(15);
275 // insert key1, value1 at STAGE_LEFT
276 auto key1
= make_ghobj(3, 3, 3, "ns3", "oid3", 3, 3);
277 auto value1
= values
.pick();
278 auto test_value1
= f_insert_erase_insert(key1
, value1
);
282 auto cursor1_s
= INTR_R(tree
->lower_bound
, *ref_t
, key_s
).unsafe_get0();
283 ASSERT_EQ(cursor1_s
.get_ghobj(), key1
);
284 ASSERT_EQ(cursor1_s
.value(), test_value1
);
285 auto cursor1_e
= INTR_R(tree
->lower_bound
, *ref_t
, key_e
).unsafe_get0();
286 ASSERT_TRUE(cursor1_e
.is_end());
289 // insert the same key1 with a different value
291 auto value1_dup
= values
.pick();
292 auto conf
= UnboundedBtree::tree_value_config_t
{value1_dup
.get_payload_size()};
293 auto [cursor1_dup
, ret1_dup
] = INTR_R(tree
->insert
,
294 *ref_t
, key1
, conf
).unsafe_get0();
295 ASSERT_FALSE(ret1_dup
);
296 validate_cursor_from_item(key1
, value1
, cursor1_dup
);
299 // insert key2, value2 to key1's left at STAGE_LEFT
300 // insert node front at STAGE_LEFT
301 auto key2
= make_ghobj(2, 2, 2, "ns3", "oid3", 3, 3);
302 auto value2
= values
.pick();
303 f_insert_erase_insert(key2
, value2
);
305 // insert key3, value3 to key1's right at STAGE_LEFT
306 // insert node last at STAGE_LEFT
307 auto key3
= make_ghobj(4, 4, 4, "ns3", "oid3", 3, 3);
308 auto value3
= values
.pick();
309 f_insert_erase_insert(key3
, value3
);
311 // insert key4, value4 to key1's left at STAGE_STRING (collision)
312 auto key4
= make_ghobj(3, 3, 3, "ns2", "oid2", 3, 3);
313 auto value4
= values
.pick();
314 f_insert_erase_insert(key4
, value4
);
316 // insert key5, value5 to key1's right at STAGE_STRING (collision)
317 auto key5
= make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3);
318 auto value5
= values
.pick();
319 f_insert_erase_insert(key5
, value5
);
321 // insert key6, value6 to key1's left at STAGE_RIGHT
322 auto key6
= make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2);
323 auto value6
= values
.pick();
324 f_insert_erase_insert(key6
, value6
);
326 // insert key7, value7 to key1's right at STAGE_RIGHT
327 auto key7
= make_ghobj(3, 3, 3, "ns3", "oid3", 4, 4);
328 auto value7
= values
.pick();
329 f_insert_erase_insert(key7
, value7
);
331 // insert node front at STAGE_RIGHT
332 auto key8
= make_ghobj(2, 2, 2, "ns3", "oid3", 2, 2);
333 auto value8
= values
.pick();
334 f_insert_erase_insert(key8
, value8
);
336 // insert node front at STAGE_STRING (collision)
337 auto key9
= make_ghobj(2, 2, 2, "ns2", "oid2", 3, 3);
338 auto value9
= values
.pick();
339 f_insert_erase_insert(key9
, value9
);
341 // insert node last at STAGE_RIGHT
342 auto key10
= make_ghobj(4, 4, 4, "ns3", "oid3", 4, 4);
343 auto value10
= values
.pick();
344 f_insert_erase_insert(key10
, value10
);
346 // insert node last at STAGE_STRING (collision)
347 auto key11
= make_ghobj(4, 4, 4, "ns4", "oid4", 3, 3);
348 auto value11
= values
.pick();
349 f_insert_erase_insert(key11
, value11
);
351 // insert key, value randomly until a perfect 3-ary tree is formed
352 std::vector
<std::pair
<ghobject_t
, test_item_t
>> kvs
{
353 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2), values
.pick()},
354 {make_ghobj(2, 2, 2, "ns2", "oid2", 4, 4), values
.pick()},
355 {make_ghobj(2, 2, 2, "ns3", "oid3", 4, 4), values
.pick()},
356 {make_ghobj(2, 2, 2, "ns4", "oid4", 2, 2), values
.pick()},
357 {make_ghobj(2, 2, 2, "ns4", "oid4", 3, 3), values
.pick()},
358 {make_ghobj(2, 2, 2, "ns4", "oid4", 4, 4), values
.pick()},
359 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2), values
.pick()},
360 {make_ghobj(3, 3, 3, "ns2", "oid2", 4, 4), values
.pick()},
361 {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2), values
.pick()},
362 {make_ghobj(3, 3, 3, "ns4", "oid4", 4, 4), values
.pick()},
363 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2), values
.pick()},
364 {make_ghobj(4, 4, 4, "ns2", "oid2", 3, 3), values
.pick()},
365 {make_ghobj(4, 4, 4, "ns2", "oid2", 4, 4), values
.pick()},
366 {make_ghobj(4, 4, 4, "ns3", "oid3", 2, 2), values
.pick()},
367 {make_ghobj(4, 4, 4, "ns4", "oid4", 2, 2), values
.pick()},
368 {make_ghobj(4, 4, 4, "ns4", "oid4", 4, 4), values
.pick()}};
369 auto [smallest_key
, smallest_value
] = kvs
[0];
370 auto [largest_key
, largest_value
] = kvs
[kvs
.size() - 1];
371 std::random_shuffle(kvs
.begin(), kvs
.end());
372 std::for_each(kvs
.begin(), kvs
.end(), [&f_insert_erase_insert
] (auto& kv
) {
373 f_insert_erase_insert(kv
.first
, kv
.second
);
375 ASSERT_EQ(INTR(tree
->height
, *ref_t
).unsafe_get0(), 1);
376 ASSERT_FALSE(tree
->test_is_clean());
378 for (auto& [k
, val
] : insert_history
) {
380 // validate values in tree keep intact
381 auto cursor
= with_trans_intr(*ref_t
, [this, &k
=k
](auto& tr
) {
382 return tree
->find(tr
, k
);
384 EXPECT_NE(cursor
, tree
->end());
385 validate_cursor_from_item(k
, v
, cursor
);
386 // validate values in cursors keep intact
387 validate_cursor_from_item(k
, v
, c
);
390 auto cursor
= INTR_R(tree
->lower_bound
, *ref_t
, key_s
).unsafe_get0();
391 validate_cursor_from_item(smallest_key
, smallest_value
, cursor
);
394 auto cursor
= INTR(tree
->begin
, *ref_t
).unsafe_get0();
395 validate_cursor_from_item(smallest_key
, smallest_value
, cursor
);
398 auto cursor
= INTR(tree
->last
, *ref_t
).unsafe_get0();
399 validate_cursor_from_item(largest_key
, largest_value
, cursor
);
402 // validate range query
405 for (auto& [k
, val
] : insert_history
) {
407 kvs
.emplace_back(k
, v
);
409 insert_history
.clear();
410 std::sort(kvs
.begin(), kvs
.end(), [](auto& l
, auto& r
) {
411 return l
.first
< r
.first
;
413 auto cursor
= INTR(tree
->begin
, *ref_t
).unsafe_get0();
414 for (auto& [k
, v
] : kvs
) {
415 ASSERT_FALSE(cursor
.is_end());
416 validate_cursor_from_item(k
, v
, cursor
);
417 cursor
= INTR(cursor
.get_next
, *ref_t
).unsafe_get0();
419 ASSERT_TRUE(cursor
.is_end());
422 std::ostringstream oss
;
423 tree
->dump(*ref_t
, oss
);
424 logger().info("\n{}\n", oss
.str());
426 // randomized erase until empty
427 std::random_shuffle(kvs
.begin(), kvs
.end());
428 for (auto& [k
, v
] : kvs
) {
429 auto e_size
= with_trans_intr(*ref_t
, [this, &k
=k
](auto& tr
) {
430 return tree
->erase(tr
, k
);
432 ASSERT_EQ(e_size
, 1);
434 auto cursor
= INTR(tree
->begin
, *ref_t
).unsafe_get0();
435 ASSERT_TRUE(cursor
.is_end());
436 ASSERT_EQ(INTR(tree
->height
, *ref_t
).unsafe_get0(), 1);
440 static std::set
<ghobject_t
> build_key_set(
441 std::pair
<unsigned, unsigned> range_2
,
442 std::pair
<unsigned, unsigned> range_1
,
443 std::pair
<unsigned, unsigned> range_0
,
444 std::string padding
= "",
445 bool is_internal
= false) {
446 ceph_assert(range_1
.second
<= 10);
447 std::set
<ghobject_t
> ret
;
449 for (unsigned i
= range_2
.first
; i
< range_2
.second
; ++i
) {
450 for (unsigned j
= range_1
.first
; j
< range_1
.second
; ++j
) {
451 for (unsigned k
= range_0
.first
; k
< range_0
.second
; ++k
) {
452 std::ostringstream os_ns
;
454 std::ostringstream os_oid
;
455 os_oid
<< "oid" << j
<< padding
;
456 key
= make_ghobj(i
, i
, i
, os_ns
.str(), os_oid
.str(), k
, k
);
462 ret
.insert(make_ghobj(9, 9, 9, "ns~last", "oid~last", 9, 9));
470 : moved_nm
{NodeExtentManager::create_dummy(IS_DUMMY_SYNC
)},
471 ref_t
{make_test_transaction()},
474 tree
{std::move(moved_nm
)},
477 seastar::future
<> build_tree(
478 std::pair
<unsigned, unsigned> range_2
,
479 std::pair
<unsigned, unsigned> range_1
,
480 std::pair
<unsigned, unsigned> range_0
,
482 return seastar::async([this, range_2
, range_1
, range_0
, value_size
] {
483 INTR(tree
.mkfs
, t
).unsafe_get0();
484 //logger().info("\n---------------------------------------------"
485 // "\nbefore leaf node split:\n");
486 auto keys
= build_key_set(range_2
, range_1
, range_0
);
487 for (auto& key
: keys
) {
488 auto value
= values
.create(value_size
);
489 insert_tree(key
, value
).get0();
491 ASSERT_EQ(INTR(tree
.height
, t
).unsafe_get0(), 1);
492 ASSERT_FALSE(tree
.test_is_clean());
493 //std::ostringstream oss;
495 //logger().info("\n{}\n", oss.str());
499 seastar::future
<> build_tree(
500 const std::vector
<ghobject_t
>& keys
, const std::vector
<test_item_t
>& values
) {
501 return seastar::async([this, keys
, values
] {
502 INTR(tree
.mkfs
, t
).unsafe_get0();
503 //logger().info("\n---------------------------------------------"
504 // "\nbefore leaf node split:\n");
505 ASSERT_EQ(keys
.size(), values
.size());
506 auto key_iter
= keys
.begin();
507 auto value_iter
= values
.begin();
508 while (key_iter
!= keys
.end()) {
509 insert_tree(*key_iter
, *value_iter
).get0();
513 ASSERT_EQ(INTR(tree
.height
, t
).unsafe_get0(), 1);
514 ASSERT_FALSE(tree
.test_is_clean());
515 //std::ostringstream oss;
517 //logger().info("\n{}\n", oss.str());
521 seastar::future
<> split_merge(
522 const ghobject_t
& key
,
523 const test_item_t
& value
,
524 const split_expectation_t
& expected
,
525 std::optional
<ghobject_t
> next_key
) {
526 return seastar::async([this, key
, value
, expected
, next_key
] {
528 auto ref_dummy
= NodeExtentManager::create_dummy(IS_DUMMY_SYNC
);
529 auto p_dummy
= static_cast<DummyManager
*>(ref_dummy
.get());
530 UnboundedBtree
tree_clone(std::move(ref_dummy
));
531 auto ref_t_clone
= make_test_transaction();
532 Transaction
& t_clone
= *ref_t_clone
;
533 INTR_R(tree_clone
.test_clone_from
, t_clone
, t
, tree
).unsafe_get0();
536 logger().info("\n\nINSERT-SPLIT {}:", key_hobj_t(key
));
537 auto conf
= UnboundedBtree::tree_value_config_t
{value
.get_payload_size()};
538 auto [cursor
, success
] = INTR_R(tree_clone
.insert
,
539 t_clone
, key
, conf
).unsafe_get0();
540 initialize_cursor_from_item(t
, key
, value
, cursor
, success
);
543 std::ostringstream oss
;
544 tree_clone
.dump(t_clone
, oss
);
545 logger().info("dump new root:\n{}", oss
.str());
547 EXPECT_EQ(INTR(tree_clone
.height
, t_clone
).unsafe_get0(), 2);
549 for (auto& [k
, val
] : insert_history
) {
551 auto result
= with_trans_intr(t_clone
, [&tree_clone
, &k
=k
] (auto& tr
) {
552 return tree_clone
.find(tr
, k
);
554 EXPECT_NE(result
, tree_clone
.end());
555 validate_cursor_from_item(k
, v
, result
);
557 auto result
= INTR_R(tree_clone
.find
, t_clone
, key
).unsafe_get0();
558 EXPECT_NE(result
, tree_clone
.end());
559 validate_cursor_from_item(key
, value
, result
);
560 EXPECT_TRUE(last_split
.match(expected
));
561 EXPECT_EQ(p_dummy
->size(), 3);
564 logger().info("\n\nERASE-MERGE {}:", key_hobj_t(key
));
565 auto nxt_cursor
= with_trans_intr(t_clone
, [&cursor
=cursor
](auto& tr
) {
566 return cursor
.erase
<true>(tr
);
570 // track root again to dump
571 auto begin
= INTR(tree_clone
.begin
, t_clone
).unsafe_get0();
573 std::ostringstream oss
;
574 tree_clone
.dump(t_clone
, oss
);
575 logger().info("dump root:\n{}", oss
.str());
578 if (next_key
.has_value()) {
579 auto found
= insert_history
.find(*next_key
);
580 ceph_assert(found
!= insert_history
.end());
581 validate_cursor_from_item(
582 *next_key
, std::get
<0>(found
->second
), nxt_cursor
);
584 EXPECT_TRUE(nxt_cursor
.is_end());
587 for (auto& [k
, val
] : insert_history
) {
589 auto result
= with_trans_intr(t_clone
, [&tree_clone
, &k
=k
](auto& tr
) {
590 return tree_clone
.find(tr
, k
);
592 EXPECT_NE(result
, tree_clone
.end());
593 validate_cursor_from_item(k
, v
, result
);
595 EXPECT_EQ(INTR(tree_clone
.height
, t_clone
).unsafe_get0(), 1);
596 EXPECT_EQ(p_dummy
->size(), 1);
600 test_item_t
create_value(size_t size
) {
601 return values
.create(size
);
605 seastar::future
<> insert_tree(const ghobject_t
& key
, const test_item_t
& value
) {
606 return seastar::async([this, &key
, &value
] {
607 auto conf
= UnboundedBtree::tree_value_config_t
{value
.get_payload_size()};
608 auto [cursor
, success
] = INTR_R(tree
.insert
,
609 t
, key
, conf
).unsafe_get0();
610 initialize_cursor_from_item(t
, key
, value
, cursor
, success
);
611 insert_history
.emplace(key
, std::make_tuple(value
, cursor
));
615 NodeExtentManagerURef moved_nm
;
616 TransactionRef ref_t
;
618 ValueBuilderImpl
<UnboundedValue
> vb
;
621 Values
<test_item_t
> values
;
623 std::tuple
<test_item_t
, UnboundedBtree::Cursor
>> insert_history
;
626 struct c_dummy_test_t
: public seastar_test_suite_t
{};
628 TEST_F(c_dummy_test_t
, 4_split_merge_leaf_node
)
633 test
.build_tree({2, 5}, {2, 5}, {2, 5}, 120).get0();
635 auto value
= test
.create_value(1144);
636 logger().info("\n---------------------------------------------"
637 "\nsplit at stage 2; insert to left front at stage 2, 1, 0\n");
638 test
.split_merge(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value
,
639 {2u, 2u, true, InsertType::BEGIN
},
640 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
641 test
.split_merge(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value
,
642 {2u, 1u, true, InsertType::BEGIN
},
643 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
644 test
.split_merge(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value
,
645 {2u, 0u, true, InsertType::BEGIN
},
646 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
648 logger().info("\n---------------------------------------------"
649 "\nsplit at stage 2; insert to left back at stage 0, 1, 2, 1, 0\n");
650 test
.split_merge(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value
,
651 {2u, 0u, true, InsertType::LAST
},
652 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
653 test
.split_merge(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value
,
654 {2u, 1u, true, InsertType::LAST
},
655 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
656 test
.split_merge(make_ghobj(2, 3, 3, "ns3", "oid3", 3, 3), value
,
657 {2u, 2u, true, InsertType::LAST
},
658 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
659 test
.split_merge(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value
,
660 {2u, 1u, true, InsertType::LAST
},
661 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
662 test
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value
,
663 {2u, 0u, true, InsertType::LAST
},
664 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
666 auto value0
= test
.create_value(1416);
667 logger().info("\n---------------------------------------------"
668 "\nsplit at stage 2; insert to right front at stage 0, 1, 2, 1, 0\n");
669 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value0
,
670 {2u, 0u, false, InsertType::BEGIN
},
671 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
672 test
.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value0
,
673 {2u, 1u, false, InsertType::BEGIN
},
674 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
675 test
.split_merge(make_ghobj(3, 4, 4, "ns3", "oid3", 3, 3), value0
,
676 {2u, 2u, false, InsertType::BEGIN
},
677 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
678 test
.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value0
,
679 {2u, 1u, false, InsertType::BEGIN
},
680 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
681 test
.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value0
,
682 {2u, 0u, false, InsertType::BEGIN
},
683 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
685 logger().info("\n---------------------------------------------"
686 "\nsplit at stage 2; insert to right back at stage 0, 1, 2\n");
687 test
.split_merge(make_ghobj(4, 4, 4, "ns4", "oid4", 5, 5), value0
,
688 {2u, 0u, false, InsertType::LAST
},
689 std::nullopt
).get0();
690 test
.split_merge(make_ghobj(4, 4, 4, "ns5", "oid5", 3, 3), value0
,
691 {2u, 1u, false, InsertType::LAST
},
692 std::nullopt
).get0();
693 test
.split_merge(make_ghobj(5, 5, 5, "ns3", "oid3", 3, 3), value0
,
694 {2u, 2u, false, InsertType::LAST
},
695 std::nullopt
).get0();
697 auto value1
= test
.create_value(316);
698 logger().info("\n---------------------------------------------"
699 "\nsplit at stage 1; insert to left middle at stage 0, 1, 2, 1, 0\n");
700 test
.split_merge(make_ghobj(2, 2, 2, "ns4", "oid4", 5, 5), value1
,
701 {1u, 0u, true, InsertType::MID
},
702 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
703 test
.split_merge(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), value1
,
704 {1u, 1u, true, InsertType::MID
},
705 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
706 test
.split_merge(make_ghobj(2, 2, 3, "ns3", "oid3", 3, 3), value1
,
707 {1u, 2u, true, InsertType::MID
},
708 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
709 test
.split_merge(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), value1
,
710 {1u, 1u, true, InsertType::MID
},
711 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
712 test
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 1, 1), value1
,
713 {1u, 0u, true, InsertType::MID
},
714 {make_ghobj(3, 3, 3, "ns2", "oid2", 2, 2)}).get0();
716 logger().info("\n---------------------------------------------"
717 "\nsplit at stage 1; insert to left back at stage 0, 1, 0\n");
718 test
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 5, 5), value1
,
719 {1u, 0u, true, InsertType::LAST
},
720 {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0();
721 test
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3), value1
,
722 {1u, 1u, true, InsertType::LAST
},
723 {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0();
724 test
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 1, 1), value1
,
725 {1u, 0u, true, InsertType::LAST
},
726 {make_ghobj(3, 3, 3, "ns3", "oid3", 2, 2)}).get0();
728 auto value2
= test
.create_value(452);
729 logger().info("\n---------------------------------------------"
730 "\nsplit at stage 1; insert to right front at stage 0, 1, 0\n");
731 test
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 5, 5), value2
,
732 {1u, 0u, false, InsertType::BEGIN
},
733 {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0();
734 test
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid4", 3, 3), value2
,
735 {1u, 1u, false, InsertType::BEGIN
},
736 {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0();
737 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 1, 1), value2
,
738 {1u, 0u, false, InsertType::BEGIN
},
739 {make_ghobj(3, 3, 3, "ns4", "oid4", 2, 2)}).get0();
741 logger().info("\n---------------------------------------------"
742 "\nsplit at stage 1; insert to right middle at stage 0, 1, 2, 1, 0\n");
743 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value2
,
744 {1u, 0u, false, InsertType::MID
},
745 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
746 test
.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value2
,
747 {1u, 1u, false, InsertType::MID
},
748 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
749 test
.split_merge(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value2
,
750 {1u, 2u, false, InsertType::MID
},
751 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
752 test
.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value2
,
753 {1u, 1u, false, InsertType::MID
},
754 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
755 test
.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value2
,
756 {1u, 0u, false, InsertType::MID
},
757 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
759 auto value3
= test
.create_value(834);
760 logger().info("\n---------------------------------------------"
761 "\nsplit at stage 0; insert to right middle at stage 0, 1, 2, 1, 0\n");
762 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 5, 5), value3
,
763 {0u, 0u, false, InsertType::MID
},
764 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
765 test
.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), value3
,
766 {0u, 1u, false, InsertType::MID
},
767 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
768 test
.split_merge(make_ghobj(3, 3, 4, "ns3", "oid3", 3, 3), value3
,
769 {0u, 2u, false, InsertType::MID
},
770 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
771 test
.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), value3
,
772 {0u, 1u, false, InsertType::MID
},
773 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
774 test
.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2", 1, 1), value3
,
775 {0u, 0u, false, InsertType::MID
},
776 {make_ghobj(4, 4, 4, "ns2", "oid2", 2, 2)}).get0();
778 logger().info("\n---------------------------------------------"
779 "\nsplit at stage 0; insert to right front at stage 0\n");
780 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 2, 3), value3
,
781 {0u, 0u, false, InsertType::BEGIN
},
782 {make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3)}).get0();
784 auto value4
= test
.create_value(572);
785 logger().info("\n---------------------------------------------"
786 "\nsplit at stage 0; insert to left back at stage 0\n");
787 test
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2", 3, 4), value4
,
788 {0u, 0u, true, InsertType::LAST
},
789 {make_ghobj(3, 3, 3, "ns2", "oid2", 4, 4)}).get0();
794 test
.build_tree({2, 4}, {2, 4}, {2, 4}, 232).get0();
795 auto value
= test
.create_value(1996);
796 logger().info("\n---------------------------------------------"
797 "\nsplit at [0, 0, 0]; insert to left front at stage 2, 1, 0\n");
798 test
.split_merge(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), value
,
799 {2u, 2u, true, InsertType::BEGIN
},
800 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
801 EXPECT_TRUE(last_split
.match_split_pos({0, {0, {0}}}));
802 test
.split_merge(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), value
,
803 {2u, 1u, true, InsertType::BEGIN
},
804 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
805 EXPECT_TRUE(last_split
.match_split_pos({0, {0, {0}}}));
806 test
.split_merge(make_ghobj(2, 2, 2, "ns2", "oid2", 1, 1), value
,
807 {2u, 0u, true, InsertType::BEGIN
},
808 {make_ghobj(2, 2, 2, "ns2", "oid2", 2, 2)}).get0();
809 EXPECT_TRUE(last_split
.match_split_pos({0, {0, {0}}}));
814 std::vector
<ghobject_t
> keys
= {
815 make_ghobj(2, 2, 2, "ns3", "oid3", 3, 3),
816 make_ghobj(3, 3, 3, "ns3", "oid3", 3, 3)};
817 std::vector
<test_item_t
> values
= {
818 test
.create_value(1360),
819 test
.create_value(1632)};
820 test
.build_tree(keys
, values
).get0();
821 auto value
= test
.create_value(1640);
822 logger().info("\n---------------------------------------------"
823 "\nsplit at [END, END, END]; insert to right at stage 0, 1, 2\n");
824 test
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3", 4, 4), value
,
825 {0u, 0u, false, InsertType::BEGIN
},
826 std::nullopt
).get0();
827 EXPECT_TRUE(last_split
.match_split_pos({1, {0, {1}}}));
828 test
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4", 3, 3), value
,
829 {1u, 1u, false, InsertType::BEGIN
},
830 std::nullopt
).get0();
831 EXPECT_TRUE(last_split
.match_split_pos({1, {1, {0}}}));
832 test
.split_merge(make_ghobj(4, 4, 4, "ns3", "oid3", 3, 3), value
,
833 {2u, 2u, false, InsertType::BEGIN
},
834 std::nullopt
).get0();
835 EXPECT_TRUE(last_split
.match_split_pos({2, {0, {0}}}));
840 namespace crimson::os::seastore::onode
{
842 class DummyChildPool
{
843 class DummyChildImpl final
: public NodeImpl
{
845 using URef
= std::unique_ptr
<DummyChildImpl
>;
846 DummyChildImpl(const std::set
<ghobject_t
>& keys
, bool is_level_tail
, laddr_t laddr
)
847 : keys
{keys
}, _is_level_tail
{is_level_tail
}, _laddr
{laddr
} {
848 std::tie(key_view
, p_mem_key_view
) = build_key_view(*keys
.crbegin());
851 ~DummyChildImpl() override
{
852 std::free(p_mem_key_view
);
855 const std::set
<ghobject_t
>& get_keys() const { return keys
; }
857 void reset(const std::set
<ghobject_t
>& _keys
, bool level_tail
) {
859 _is_level_tail
= level_tail
;
860 std::free(p_mem_key_view
);
861 std::tie(key_view
, p_mem_key_view
) = build_key_view(*keys
.crbegin());
866 laddr_t
laddr() const override
{ return _laddr
; }
867 bool is_level_tail() const override
{ return _is_level_tail
; }
868 std::optional
<key_view_t
> get_pivot_index() const override
{ return {key_view
}; }
869 bool is_extent_retired() const override
{ return _is_extent_retired
; }
870 const std::string
& get_name() const override
{ return name
; }
871 search_position_t
make_tail() override
{
872 _is_level_tail
= true;
874 return search_position_t::end();
876 eagain_ifuture
<> retire_extent(context_t
) override
{
877 assert(!_is_extent_retired
);
878 _is_extent_retired
= true;
879 return eagain_iertr::now();
883 node_type_t
node_type() const override
{ return node_type_t::LEAF
; }
884 field_type_t
field_type() const override
{ return field_type_t::N0
; }
885 const char* read() const override
{
886 ceph_abort("impossible path"); }
887 extent_len_t
get_node_size() const override
{
888 ceph_abort("impossible path"); }
889 nextent_state_t
get_extent_state() const override
{
890 ceph_abort("impossible path"); }
891 level_t
level() const override
{ return 0u; }
892 void prepare_mutate(context_t
) override
{
893 ceph_abort("impossible path"); }
894 void validate_non_empty() const override
{
895 ceph_abort("impossible path"); }
896 bool is_keys_empty() const override
{
897 ceph_abort("impossible path"); }
898 bool has_single_value() const override
{
899 ceph_abort("impossible path"); }
900 node_offset_t
free_size() const override
{
901 ceph_abort("impossible path"); }
902 extent_len_t
total_size() const override
{
903 ceph_abort("impossible path"); }
904 bool is_size_underflow() const override
{
905 ceph_abort("impossible path"); }
906 std::tuple
<match_stage_t
, search_position_t
> erase(const search_position_t
&) override
{
907 ceph_abort("impossible path"); }
908 std::tuple
<match_stage_t
, std::size_t> evaluate_merge(NodeImpl
&) override
{
909 ceph_abort("impossible path"); }
910 search_position_t
merge(NodeExtentMutable
&, NodeImpl
&, match_stage_t
, extent_len_t
) override
{
911 ceph_abort("impossible path"); }
912 eagain_ifuture
<NodeExtentMutable
> rebuild_extent(context_t
) override
{
913 ceph_abort("impossible path"); }
914 node_stats_t
get_stats() const override
{
915 ceph_abort("impossible path"); }
916 std::ostream
& dump(std::ostream
&) const override
{
917 ceph_abort("impossible path"); }
918 std::ostream
& dump_brief(std::ostream
&) const override
{
919 ceph_abort("impossible path"); }
920 void validate_layout() const override
{
921 ceph_abort("impossible path"); }
922 void test_copy_to(NodeExtentMutable
&) const override
{
923 ceph_abort("impossible path"); }
924 void test_set_tail(NodeExtentMutable
&) override
{
925 ceph_abort("impossible path"); }
929 std::ostringstream sos
;
931 << "@0x" << std::hex
<< laddr() << std::dec
932 << "Lv" << (unsigned)level()
933 << (is_level_tail() ? "$" : "")
934 << "(" << key_view
<< ")";
938 std::set
<ghobject_t
> keys
;
942 bool _is_extent_retired
= false;
945 void* p_mem_key_view
;
948 class DummyChild final
: public Node
{
950 ~DummyChild() override
= default;
952 key_view_t
get_pivot_key() const { return *impl
->get_pivot_index(); }
954 eagain_ifuture
<> populate_split(
955 context_t c
, std::set
<Ref
<DummyChild
>>& splitable_nodes
) {
956 ceph_assert(can_split());
957 ceph_assert(splitable_nodes
.find(this) != splitable_nodes
.end());
960 const auto& keys
= impl
->get_keys();
961 if (keys
.size() == 2) {
964 index
= rd() % (keys
.size() - 2) + 1;
966 auto iter
= keys
.begin();
967 std::advance(iter
, index
);
969 std::set
<ghobject_t
> left_keys(keys
.begin(), iter
);
970 std::set
<ghobject_t
> right_keys(iter
, keys
.end());
971 bool right_is_tail
= impl
->is_level_tail();
972 impl
->reset(left_keys
, false);
973 auto right_child
= DummyChild::create_new(right_keys
, right_is_tail
, pool
);
975 splitable_nodes
.erase(this);
977 if (right_child
->can_split()) {
978 splitable_nodes
.insert(right_child
);
980 Ref
<Node
> this_ref
= this;
981 return apply_split_to_parent(
982 c
, std::move(this_ref
), std::move(right_child
), false);
985 eagain_ifuture
<> insert_and_split(
986 context_t c
, const ghobject_t
& insert_key
,
987 std::set
<Ref
<DummyChild
>>& splitable_nodes
) {
988 const auto& keys
= impl
->get_keys();
989 ceph_assert(keys
.size() == 1);
990 auto& key
= *keys
.begin();
991 ceph_assert(insert_key
< key
);
993 std::set
<ghobject_t
> new_keys
;
994 new_keys
.insert(insert_key
);
995 new_keys
.insert(key
);
996 impl
->reset(new_keys
, impl
->is_level_tail());
998 splitable_nodes
.clear();
999 splitable_nodes
.insert(this);
1000 auto fut
= populate_split(c
, splitable_nodes
);
1001 ceph_assert(splitable_nodes
.size() == 0);
1005 eagain_ifuture
<> merge(context_t c
, Ref
<DummyChild
>&& this_ref
) {
1006 return parent_info().ptr
->get_child_peers(c
, parent_info().position
1007 ).si_then([c
, this_ref
= std::move(this_ref
), this] (auto lr_nodes
) mutable {
1008 auto& [lnode
, rnode
] = lr_nodes
;
1011 Ref
<DummyChild
> r_dummy(static_cast<DummyChild
*>(rnode
.get()));
1013 pool
.untrack_node(r_dummy
);
1014 assert(r_dummy
->use_count() == 1);
1015 return do_merge(c
, std::move(this_ref
), std::move(r_dummy
), true);
1018 Ref
<DummyChild
> l_dummy(static_cast<DummyChild
*>(lnode
.get()));
1019 pool
.untrack_node(this_ref
);
1020 assert(this_ref
->use_count() == 1);
1021 return do_merge(c
, std::move(l_dummy
), std::move(this_ref
), false);
1026 eagain_ifuture
<> fix_key(context_t c
, const ghobject_t
& new_key
) {
1027 const auto& keys
= impl
->get_keys();
1028 ceph_assert(keys
.size() == 1);
1029 assert(impl
->is_level_tail() == false);
1031 std::set
<ghobject_t
> new_keys
;
1032 new_keys
.insert(new_key
);
1033 impl
->reset(new_keys
, impl
->is_level_tail());
1034 Ref
<Node
> this_ref
= this;
1035 return fix_parent_index
<true>(c
, std::move(this_ref
), false);
1038 bool match_pos(const search_position_t
& pos
) const {
1039 ceph_assert(!is_root());
1040 return pos
== parent_info().position
;
1043 static Ref
<DummyChild
> create(
1044 const std::set
<ghobject_t
>& keys
, bool is_level_tail
,
1045 laddr_t addr
, DummyChildPool
& pool
) {
1046 auto ref_impl
= std::make_unique
<DummyChildImpl
>(keys
, is_level_tail
, addr
);
1047 return new DummyChild(ref_impl
.get(), std::move(ref_impl
), pool
);
1050 static Ref
<DummyChild
> create_new(
1051 const std::set
<ghobject_t
>& keys
, bool is_level_tail
, DummyChildPool
& pool
) {
1052 static laddr_t seed
= 0;
1053 return create(keys
, is_level_tail
, seed
++, pool
);
1056 static eagain_ifuture
<Ref
<DummyChild
>> create_initial(
1057 context_t c
, const std::set
<ghobject_t
>& keys
,
1058 DummyChildPool
& pool
, RootNodeTracker
& root_tracker
) {
1059 auto initial
= create_new(keys
, true, pool
);
1060 return c
.nm
.get_super(c
.t
, root_tracker
1061 ).handle_error_interruptible(
1062 eagain_iertr::pass_further
{},
1063 crimson::ct_error::assert_all
{"Invalid error during create_initial()"}
1064 ).si_then([c
, initial
](auto super
) {
1065 initial
->make_root_new(c
, std::move(super
));
1066 return initial
->upgrade_root(c
, L_ADDR_MIN
).si_then([initial
] {
1073 eagain_ifuture
<> test_clone_non_root(
1074 context_t
, Ref
<InternalNode
> new_parent
) const override
{
1075 ceph_assert(!is_root());
1076 auto p_pool_clone
= pool
.pool_clone_in_progress
;
1077 ceph_assert(p_pool_clone
!= nullptr);
1078 auto clone
= create(
1079 impl
->get_keys(), impl
->is_level_tail(), impl
->laddr(), *p_pool_clone
);
1080 clone
->as_child(parent_info().position
, new_parent
);
1081 return eagain_iertr::now();
1083 eagain_ifuture
<Ref
<tree_cursor_t
>> lookup_smallest(context_t
) override
{
1084 ceph_abort("impossible path"); }
1085 eagain_ifuture
<Ref
<tree_cursor_t
>> lookup_largest(context_t
) override
{
1086 ceph_abort("impossible path"); }
1087 eagain_ifuture
<> test_clone_root(context_t
, RootNodeTracker
&) const override
{
1088 ceph_abort("impossible path"); }
1089 eagain_ifuture
<search_result_t
> lower_bound_tracked(
1090 context_t
, const key_hobj_t
&, MatchHistory
&) override
{
1091 ceph_abort("impossible path"); }
1092 eagain_ifuture
<> do_get_tree_stats(context_t
, tree_stats_t
&) override
{
1093 ceph_abort("impossible path"); }
1094 bool is_tracking() const override
{ return false; }
1095 void track_merge(Ref
<Node
>, match_stage_t
, search_position_t
&) override
{
1096 ceph_abort("impossible path"); }
1099 DummyChild(DummyChildImpl
* impl
, DummyChildImpl::URef
&& ref
, DummyChildPool
& pool
)
1100 : Node(std::move(ref
)), impl
{impl
}, pool
{pool
} {
1101 pool
.track_node(this);
1104 bool can_split() const { return impl
->get_keys().size() > 1; }
1106 static eagain_ifuture
<> do_merge(
1107 context_t c
, Ref
<DummyChild
>&& left
, Ref
<DummyChild
>&& right
, bool stole_key
) {
1108 assert(right
->use_count() == 1);
1109 assert(left
->impl
->get_keys().size() == 1);
1110 assert(right
->impl
->get_keys().size() == 1);
1111 bool left_is_tail
= right
->impl
->is_level_tail();
1112 const std::set
<ghobject_t
>* p_keys
;
1114 p_keys
= &right
->impl
->get_keys();
1116 p_keys
= &left
->impl
->get_keys();
1118 left
->impl
->reset(*p_keys
, left_is_tail
);
1119 auto left_addr
= left
->impl
->laddr();
1120 return left
->parent_info().ptr
->apply_children_merge
<true>(
1121 c
, std::move(left
), left_addr
, std::move(right
), !stole_key
);
1124 DummyChildImpl
* impl
;
1125 DummyChildPool
& pool
;
1126 mutable std::random_device rd
;
1130 DummyChildPool() = default;
1131 ~DummyChildPool() { reset(); }
1133 auto build_tree(const std::set
<ghobject_t
>& keys
) {
1136 auto ref_dummy
= NodeExtentManager::create_dummy(IS_DUMMY_SYNC
);
1137 p_dummy
= static_cast<DummyManager
*>(ref_dummy
.get());
1138 p_btree
.emplace(std::move(ref_dummy
));
1139 return with_trans_intr(get_context().t
, [this, &keys
] (auto &tr
) {
1140 return DummyChild::create_initial(get_context(), keys
, *this, *p_btree
->root_tracker
1141 ).si_then([this](auto initial_child
) {
1143 splitable_nodes
.insert(initial_child
);
1144 return trans_intr::repeat([this] ()
1145 -> eagain_ifuture
<seastar::stop_iteration
> {
1146 if (splitable_nodes
.empty()) {
1147 return seastar::make_ready_future
<seastar::stop_iteration
>(
1148 seastar::stop_iteration::yes
);
1150 auto index
= rd() % splitable_nodes
.size();
1151 auto iter
= splitable_nodes
.begin();
1152 std::advance(iter
, index
);
1153 Ref
<DummyChild
> child
= *iter
;
1154 return child
->populate_split(get_context(), splitable_nodes
1156 return seastar::stop_iteration::no
;
1160 //std::ostringstream oss;
1161 //p_btree->dump(t(), oss);
1162 //logger().info("\n{}\n", oss.str());
1163 return p_btree
->height(t());
1164 }).si_then([](auto height
) {
1165 ceph_assert(height
== 2);
1170 seastar::future
<> split_merge(ghobject_t key
, search_position_t pos
,
1171 const split_expectation_t
& expected
) {
1172 return seastar::async([this, key
, pos
, expected
] {
1173 DummyChildPool pool_clone
;
1174 clone_to(pool_clone
);
1177 logger().info("\n\nINSERT-SPLIT {} at pos({}):", key_hobj_t(key
), pos
);
1178 auto node_to_split
= pool_clone
.get_node_by_pos(pos
);
1179 with_trans_intr(pool_clone
.get_context().t
, [&] (auto &t
) {
1180 return node_to_split
->insert_and_split(
1181 pool_clone
.get_context(), key
, pool_clone
.splitable_nodes
);
1184 std::ostringstream oss
;
1185 pool_clone
.p_btree
->dump(pool_clone
.t(), oss
);
1186 logger().info("dump new root:\n{}", oss
.str());
1188 auto &pt
= pool_clone
.t();
1189 EXPECT_EQ(INTR(pool_clone
.p_btree
->height
, pt
).unsafe_get0(), 3);
1190 EXPECT_TRUE(last_split
.match(expected
));
1191 EXPECT_EQ(pool_clone
.p_dummy
->size(), 3);
1194 auto pivot_key
= node_to_split
->get_pivot_key();
1195 logger().info("\n\nERASE-MERGE {}:", node_to_split
->get_name());
1196 assert(pivot_key
.compare_to(key_hobj_t(key
)) == MatchKindCMP::EQ
);
1197 with_trans_intr(pool_clone
.get_context().t
, [&] (auto &t
) {
1198 return node_to_split
->merge(
1199 pool_clone
.get_context(), std::move(node_to_split
));
1201 auto &pt2
= pool_clone
.t();
1202 EXPECT_EQ(INTR(pool_clone
.p_btree
->height
,pt2
).unsafe_get0(), 2);
1203 EXPECT_EQ(pool_clone
.p_dummy
->size(), 1);
1207 seastar::future
<> fix_index(
1208 ghobject_t new_key
, search_position_t pos
, bool expect_split
) {
1209 return seastar::async([this, new_key
, pos
, expect_split
] {
1210 DummyChildPool pool_clone
;
1211 clone_to(pool_clone
);
1214 auto node_to_fix
= pool_clone
.get_node_by_pos(pos
);
1215 auto old_key
= node_to_fix
->get_pivot_key().to_ghobj();
1216 logger().info("\n\nFIX pos({}) from {} to {}, expect_split={}:",
1217 pos
, node_to_fix
->get_name(), key_hobj_t(new_key
), expect_split
);
1218 with_trans_intr(pool_clone
.get_context().t
, [&] (auto &t
) {
1219 return node_to_fix
->fix_key(pool_clone
.get_context(), new_key
);
1222 std::ostringstream oss
;
1223 pool_clone
.p_btree
->dump(pool_clone
.t(), oss
);
1224 logger().info("dump new root:\n{}", oss
.str());
1225 auto &pt
= pool_clone
.t();
1226 EXPECT_EQ(INTR(pool_clone
.p_btree
->height
, pt
).unsafe_get0(), 3);
1227 EXPECT_EQ(pool_clone
.p_dummy
->size(), 3);
1229 auto &pt
= pool_clone
.t();
1230 EXPECT_EQ(INTR(pool_clone
.p_btree
->height
, pt
).unsafe_get0(), 2);
1231 EXPECT_EQ(pool_clone
.p_dummy
->size(), 1);
1235 logger().info("\n\nFIX pos({}) from {} back to {}:",
1236 pos
, node_to_fix
->get_name(), key_hobj_t(old_key
));
1237 with_trans_intr(pool_clone
.get_context().t
, [&] (auto &t
) {
1238 return node_to_fix
->fix_key(pool_clone
.get_context(), old_key
);
1240 auto &pt
= pool_clone
.t();
1241 EXPECT_EQ(INTR(pool_clone
.p_btree
->height
, pt
).unsafe_get0(), 2);
1242 EXPECT_EQ(pool_clone
.p_dummy
->size(), 1);
1247 void clone_to(DummyChildPool
& pool_clone
) {
1248 pool_clone_in_progress
= &pool_clone
;
1249 auto ref_dummy
= NodeExtentManager::create_dummy(IS_DUMMY_SYNC
);
1250 pool_clone
.p_dummy
= static_cast<DummyManager
*>(ref_dummy
.get());
1251 pool_clone
.p_btree
.emplace(std::move(ref_dummy
));
1252 auto &pt
= pool_clone
.t();
1253 [[maybe_unused
]] auto &tr
= t();
1254 INTR_R(pool_clone
.p_btree
->test_clone_from
,
1255 pt
, tr
, *p_btree
).unsafe_get0();
1256 pool_clone_in_progress
= nullptr;
1260 ceph_assert(pool_clone_in_progress
== nullptr);
1261 if (tracked_children
.size()) {
1262 ceph_assert(!p_btree
->test_is_clean());
1263 tracked_children
.clear();
1264 ceph_assert(p_btree
->test_is_clean());
1268 ceph_assert(!p_btree
.has_value());
1270 splitable_nodes
.clear();
1273 void track_node(Ref
<DummyChild
> node
) {
1274 ceph_assert(tracked_children
.find(node
) == tracked_children
.end());
1275 tracked_children
.insert(node
);
1278 void untrack_node(Ref
<DummyChild
> node
) {
1279 auto ret
= tracked_children
.erase(node
);
1280 ceph_assert(ret
== 1);
1283 Ref
<DummyChild
> get_node_by_pos(const search_position_t
& pos
) const {
1284 auto iter
= std::find_if(
1285 tracked_children
.begin(), tracked_children
.end(), [&pos
](auto& child
) {
1286 return child
->match_pos(pos
);
1288 ceph_assert(iter
!= tracked_children
.end());
1292 context_t
get_context() {
1293 ceph_assert(p_dummy
!= nullptr);
1294 return {*p_dummy
, vb
, t()};
1297 Transaction
& t() const { return *ref_t
; }
1299 std::set
<Ref
<DummyChild
>> tracked_children
;
1300 std::optional
<UnboundedBtree
> p_btree
;
1301 DummyManager
* p_dummy
= nullptr;
1302 ValueBuilderImpl
<UnboundedValue
> vb
;
1303 TransactionRef ref_t
= make_test_transaction();
1305 std::random_device rd
;
1306 std::set
<Ref
<DummyChild
>> splitable_nodes
;
1308 DummyChildPool
* pool_clone_in_progress
= nullptr;
1313 TEST_F(c_dummy_test_t
, 5_split_merge_internal_node
)
1316 DummyChildPool pool
;
1318 logger().info("\n---------------------------------------------"
1319 "\nbefore internal node insert:\n");
1320 auto padding
= std::string(250, '_');
1321 auto keys
= build_key_set({2, 6}, {2, 5}, {2, 5}, padding
, true);
1322 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 2, 2));
1323 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 3, 3));
1324 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 4, 4));
1325 keys
.erase(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 2, 2));
1326 keys
.erase(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 3, 3));
1327 keys
.erase(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 4, 4));
1328 auto padding_s
= std::string(257, '_');
1329 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 2, 2));
1330 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 3, 3));
1331 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 4, 4));
1332 auto padding_e
= std::string(247, '_');
1333 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding_e
, 2, 2));
1334 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding_e
, 3, 3));
1335 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding_e
, 4, 4));
1336 pool
.build_tree(keys
).unsafe_get0();
1338 logger().info("\n---------------------------------------------"
1339 "\nsplit at stage 2; insert to right front at stage 0, 1, 2, 1, 0\n");
1340 pool
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4" + padding
, 5, 5), {2, {0, {0}}},
1341 {2u, 0u, false, InsertType::BEGIN
}).get();
1342 pool
.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), {2, {0, {0}}},
1343 {2u, 1u, false, InsertType::BEGIN
}).get();
1344 pool
.split_merge(make_ghobj(3, 4, 4, "ns3", "oid3", 3, 3), {2, {0, {0}}},
1345 {2u, 2u, false, InsertType::BEGIN
}).get();
1346 pool
.split_merge(make_ghobj(4, 4, 4, "ns1", "oid1", 3, 3), {2, {0, {0}}},
1347 {2u, 1u, false, InsertType::BEGIN
}).get();
1348 pool
.split_merge(make_ghobj(4, 4, 4, "ns2", "oid2" + padding
, 1, 1), {2, {0, {0}}},
1349 {2u, 0u, false, InsertType::BEGIN
}).get();
1351 logger().info("\n---------------------------------------------"
1352 "\nsplit at stage 2; insert to right middle at stage 0, 1, 2, 1, 0\n");
1353 pool
.split_merge(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 5, 5), {3, {0, {0}}},
1354 {2u, 0u, false, InsertType::MID
}).get();
1355 pool
.split_merge(make_ghobj(4, 4, 4, "ns5", "oid5", 3, 3), {3, {0, {0}}},
1356 {2u, 1u, false, InsertType::MID
}).get();
1357 pool
.split_merge(make_ghobj(4, 4, 5, "ns3", "oid3", 3, 3), {3, {0, {0}}},
1358 {2u, 2u, false, InsertType::MID
}).get();
1359 pool
.split_merge(make_ghobj(5, 5, 5, "ns1", "oid1", 3, 3), {3, {0, {0}}},
1360 {2u, 1u, false, InsertType::MID
}).get();
1361 pool
.split_merge(make_ghobj(5, 5, 5, "ns2", "oid2" + padding
, 1, 1), {3, {0, {0}}},
1362 {2u, 0u, false, InsertType::MID
}).get();
1364 logger().info("\n---------------------------------------------"
1365 "\nsplit at stage 2; insert to right back at stage 0, 1, 2\n");
1366 pool
.split_merge(make_ghobj(5, 5, 5, "ns4", "oid4" + padding_e
, 5, 5), search_position_t::end() ,
1367 {2u, 0u, false, InsertType::LAST
}).get();
1368 pool
.split_merge(make_ghobj(5, 5, 5, "ns5", "oid5", 3, 3), search_position_t::end(),
1369 {2u, 1u, false, InsertType::LAST
}).get();
1370 pool
.split_merge(make_ghobj(6, 6, 6, "ns3", "oid3", 3, 3), search_position_t::end(),
1371 {2u, 2u, false, InsertType::LAST
}).get();
1373 logger().info("\n---------------------------------------------"
1374 "\nsplit at stage 0; insert to left front at stage 2, 1, 0\n");
1375 pool
.split_merge(make_ghobj(1, 1, 1, "ns3", "oid3", 3, 3), {0, {0, {0}}},
1376 {0u, 2u, true, InsertType::BEGIN
}).get();
1377 pool
.split_merge(make_ghobj(2, 2, 2, "ns1", "oid1", 3, 3), {0, {0, {0}}},
1378 {0u, 1u, true, InsertType::BEGIN
}).get();
1379 pool
.split_merge(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 1, 1), {0, {0, {0}}},
1380 {0u, 0u, true, InsertType::BEGIN
}).get();
1382 logger().info("\n---------------------------------------------"
1383 "\nsplit at stage 0; insert to left middle at stage 0, 1, 2, 1, 0\n");
1384 pool
.split_merge(make_ghobj(2, 2, 2, "ns4", "oid4" + padding
, 5, 5), {1, {0, {0}}},
1385 {0u, 0u, true, InsertType::MID
}).get();
1386 pool
.split_merge(make_ghobj(2, 2, 2, "ns5", "oid5", 3, 3), {1, {0, {0}}},
1387 {0u, 1u, true, InsertType::MID
}).get();
1388 pool
.split_merge(make_ghobj(2, 2, 3, "ns3", "oid3" + std::string(80, '_'), 3, 3), {1, {0, {0}}} ,
1389 {0u, 2u, true, InsertType::MID
}).get();
1390 pool
.split_merge(make_ghobj(3, 3, 3, "ns1", "oid1", 3, 3), {1, {0, {0}}},
1391 {0u, 1u, true, InsertType::MID
}).get();
1392 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2" + padding
, 1, 1), {1, {0, {0}}},
1393 {0u, 0u, true, InsertType::MID
}).get();
1395 logger().info("\n---------------------------------------------"
1396 "\nsplit at stage 0; insert to left back at stage 0\n");
1397 pool
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4" + padding
, 3, 4), {1, {2, {2}}},
1398 {0u, 0u, true, InsertType::LAST
}).get();
1402 logger().info("\n---------------------------------------------"
1403 "\nbefore internal node insert (1):\n");
1404 auto padding
= std::string(244, '_');
1405 auto keys
= build_key_set({2, 6}, {2, 5}, {2, 5}, padding
, true);
1406 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 5, 5));
1407 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 6, 6));
1408 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 7, 7));
1409 pool
.build_tree(keys
).unsafe_get0();
1411 logger().info("\n---------------------------------------------"
1412 "\nsplit at stage 2; insert to left back at stage 0, 1, 2, 1\n");
1413 pool
.split_merge(make_ghobj(3, 3, 3, "ns4", "oid4" + padding
, 5, 5), {2, {0, {0}}},
1414 {2u, 0u, true, InsertType::LAST
}).get();
1415 pool
.split_merge(make_ghobj(3, 3, 3, "ns5", "oid5", 3, 3), {2, {0, {0}}},
1416 {2u, 1u, true, InsertType::LAST
}).get();
1417 pool
.split_merge(make_ghobj(3, 4, 4, "n", "o", 3, 3), {2, {0, {0}}},
1418 {2u, 2u, true, InsertType::LAST
}).get();
1419 pool
.split_merge(make_ghobj(4, 4, 4, "n", "o", 3, 3), {2, {0, {0}}},
1420 {2u, 1u, true, InsertType::LAST
}).get();
1422 logger().info("\n---------------------------------------------"
1423 "\nsplit at stage 2; insert to left middle at stage 2\n");
1424 pool
.split_merge(make_ghobj(2, 3, 3, "n", "o", 3, 3), {1, {0, {0}}},
1425 {2u, 2u, true, InsertType::MID
}).get();
1429 logger().info("\n---------------------------------------------"
1430 "\nbefore internal node insert (2):\n");
1431 auto padding
= std::string(243, '_');
1432 auto keys
= build_key_set({2, 6}, {2, 5}, {2, 5}, padding
, true);
1433 keys
.insert(make_ghobj(4, 4, 4, "n", "o", 3, 3));
1434 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 5, 5));
1435 keys
.insert(make_ghobj(5, 5, 5, "ns4", "oid4" + padding
, 6, 6));
1436 pool
.build_tree(keys
).unsafe_get0();
1438 logger().info("\n---------------------------------------------"
1439 "\nsplit at stage 2; insert to left back at stage (0, 1, 2, 1,) 0\n");
1440 pool
.split_merge(make_ghobj(4, 4, 4, "n", "o", 2, 2), {2, {0, {0}}},
1441 {2u, 0u, true, InsertType::LAST
}).get();
1445 logger().info("\n---------------------------------------------"
1446 "\nbefore internal node insert (3):\n");
1447 auto padding
= std::string(419, '_');
1448 auto keys
= build_key_set({2, 5}, {2, 5}, {2, 5}, padding
, true);
1449 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 2, 2));
1450 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 3, 3));
1451 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 4, 4));
1452 pool
.build_tree(keys
).unsafe_get0();
1454 logger().info("\n---------------------------------------------"
1455 "\nsplit at stage 1; insert to right front at stage 0, 1, 0\n");
1456 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2" + padding
, 5, 5), {1, {1, {0}}},
1457 {1u, 0u, false, InsertType::BEGIN
}).get();
1458 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3), {1, {1, {0}}},
1459 {1u, 1u, false, InsertType::BEGIN
}).get();
1460 pool
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3" + padding
, 1, 1), {1, {1, {0}}},
1461 {1u, 0u, false, InsertType::BEGIN
}).get();
1465 logger().info("\n---------------------------------------------"
1466 "\nbefore internal node insert (4):\n");
1467 auto padding
= std::string(361, '_');
1468 auto keys
= build_key_set({2, 5}, {2, 5}, {2, 5}, padding
, true);
1469 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 2, 2));
1470 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 3, 3));
1471 keys
.erase(make_ghobj(2, 2, 2, "ns2", "oid2" + padding
, 4, 4));
1472 auto padding_s
= std::string(386, '_');
1473 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 2, 2));
1474 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 3, 3));
1475 keys
.insert(make_ghobj(2, 2, 2, "ns2", "oid2" + padding_s
, 4, 4));
1476 pool
.build_tree(keys
).unsafe_get0();
1478 logger().info("\n---------------------------------------------"
1479 "\nsplit at stage 1; insert to left back at stage 0, 1\n");
1480 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid2" + padding
, 5, 5), {1, {1, {0}}},
1481 {1u, 0u, true, InsertType::LAST
}).get();
1482 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3), {1, {1, {0}}},
1483 {1u, 1u, true, InsertType::LAST
}).get();
1485 logger().info("\n---------------------------------------------"
1486 "\nfix end index from stage 0 to 0, 1, 2\n");
1487 auto padding1
= std::string(400, '_');
1488 pool
.fix_index(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 5, 5),
1489 {2, {2, {2}}}, false).get();
1490 pool
.fix_index(make_ghobj(4, 4, 4, "ns5", "oid5" + padding1
, 3, 3),
1491 {2, {2, {2}}}, true).get();
1492 pool
.fix_index(make_ghobj(5, 5, 5, "ns3", "oid3" + padding1
, 3, 3),
1493 {2, {2, {2}}}, true).get();
1497 logger().info("\n---------------------------------------------"
1498 "\nbefore internal node insert (5):\n");
1499 auto padding
= std::string(412, '_');
1500 auto keys
= build_key_set({2, 5}, {2, 5}, {2, 5}, padding
);
1501 keys
.insert(make_ghobj(3, 3, 3, "ns2", "oid3", 3, 3));
1502 keys
.insert(make_ghobj(4, 4, 4, "ns3", "oid3" + padding
, 5, 5));
1503 keys
.insert(make_ghobj(9, 9, 9, "ns~last", "oid~last", 9, 9));
1504 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 2, 2));
1505 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 3, 3));
1506 keys
.erase(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 4, 4));
1507 pool
.build_tree(keys
).unsafe_get0();
1509 logger().info("\n---------------------------------------------"
1510 "\nsplit at stage 1; insert to left back at stage (0, 1,) 0\n");
1511 pool
.split_merge(make_ghobj(3, 3, 3, "ns2", "oid3", 2, 2), {1, {1, {0}}},
1512 {1u, 0u, true, InsertType::LAST
}).get();
1516 logger().info("\n---------------------------------------------"
1517 "\nbefore internal node insert (6):\n");
1518 auto padding
= std::string(328, '_');
1519 auto keys
= build_key_set({2, 5}, {2, 5}, {2, 5}, padding
);
1520 keys
.insert(make_ghobj(5, 5, 5, "ns3", "oid3" + std::string(270, '_'), 3, 3));
1521 keys
.insert(make_ghobj(9, 9, 9, "ns~last", "oid~last", 9, 9));
1522 pool
.build_tree(keys
).unsafe_get0();
1524 logger().info("\n---------------------------------------------"
1525 "\nsplit at stage 0; insert to right front at stage 0\n");
1526 pool
.split_merge(make_ghobj(3, 3, 3, "ns3", "oid3" + padding
, 2, 3), {1, {1, {1}}},
1527 {0u, 0u, false, InsertType::BEGIN
}).get();
1529 logger().info("\n---------------------------------------------"
1530 "\nfix end index from stage 2 to 0, 1, 2\n");
1531 auto padding1
= std::string(400, '_');
1532 pool
.fix_index(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 5, 5),
1533 {3, {0, {0}}}, false).get();
1534 pool
.fix_index(make_ghobj(4, 4, 4, "ns5", "oid5" + padding1
, 3, 3),
1535 {3, {0, {0}}}, true).get();
1536 pool
.fix_index(make_ghobj(5, 5, 5, "ns4", "oid4" + padding1
, 3, 3),
1537 {3, {0, {0}}}, true).get();
1541 logger().info("\n---------------------------------------------"
1542 "\nbefore internal node insert (7):\n");
1543 auto padding
= std::string(323, '_');
1544 auto keys
= build_key_set({2, 5}, {2, 5}, {2, 5}, padding
);
1545 keys
.insert(make_ghobj(4, 4, 4, "ns5", "oid5" + padding
, 3, 3));
1546 keys
.insert(make_ghobj(9, 9, 9, "ns~last", "oid~last", 9, 9));
1547 pool
.build_tree(keys
).unsafe_get0();
1549 logger().info("\n---------------------------------------------"
1550 "\nfix end index from stage 1 to 0, 1, 2\n");
1551 auto padding1
= std::string(400, '_');
1552 pool
.fix_index(make_ghobj(4, 4, 4, "ns4", "oid4" + padding
, 5, 5),
1553 {2, {3, {0}}}, false).get();
1554 pool
.fix_index(make_ghobj(4, 4, 4, "ns6", "oid6" + padding1
, 3, 3),
1555 {2, {3, {0}}}, true).get();
1556 pool
.fix_index(make_ghobj(5, 5, 5, "ns3", "oid3" + padding1
, 3, 3),
1557 {2, {3, {0}}}, true).get();
1560 // Impossible to split at {0, 0, 0}
1561 // Impossible to split at [END, END, END]
1565 struct d_seastore_tm_test_t
:
1566 public seastar_test_suite_t
, TMTestState
{
1567 seastar::future
<> set_up_fut() override final
{
1570 seastar::future
<> tear_down_fut() override final
{
1571 return tm_teardown();
1575 TEST_F(d_seastore_tm_test_t
, 6_random_tree_insert_erase
)
1578 constexpr bool TEST_SEASTORE
= true;
1579 constexpr bool TRACK_CURSORS
= true;
1580 auto kvs
= KVPool
<test_item_t
>::create_raw_range(
1581 {8, 11, 64, 256, 301, 320},
1582 {8, 11, 64, 256, 301, 320},
1583 {8, 16, 128, 512, 576, 640},
1584 {0, 16}, {0, 10}, {0, 4});
1585 auto moved_nm
= (TEST_SEASTORE
? NodeExtentManager::create_seastore(*tm
)
1586 : NodeExtentManager::create_dummy(IS_DUMMY_SYNC
));
1587 auto p_nm
= moved_nm
.get();
1588 auto tree
= std::make_unique
<TreeBuilder
<TRACK_CURSORS
, BoundedValue
>>(
1589 kvs
, std::move(moved_nm
));
1591 auto t
= create_mutate_transaction();
1592 INTR(tree
->bootstrap
, *t
).unsafe_get();
1593 submit_transaction(std::move(t
));
1594 segment_cleaner
->run_until_halt().get0();
1599 auto t
= create_mutate_transaction();
1600 INTR(tree
->insert
, *t
).unsafe_get();
1601 submit_transaction(std::move(t
));
1602 segment_cleaner
->run_until_halt().get0();
1605 auto t
= create_read_transaction();
1606 INTR(tree
->get_stats
, *t
).unsafe_get();
1608 if constexpr (TEST_SEASTORE
) {
1609 logger().info("seastore replay insert begin");
1611 tree
->reload(NodeExtentManager::create_seastore(*tm
));
1612 logger().info("seastore replay insert end");
1615 // Note: create_weak_transaction() can also work, but too slow.
1616 auto t
= create_read_transaction();
1617 INTR(tree
->validate
, *t
).unsafe_get();
1622 auto t
= create_mutate_transaction();
1623 auto size
= kvs
.size() / 4 * 3;
1624 INTR_R(tree
->erase
, *t
, size
).unsafe_get();
1625 submit_transaction(std::move(t
));
1626 segment_cleaner
->run_until_halt().get0();
1629 auto t
= create_read_transaction();
1630 INTR(tree
->get_stats
, *t
).unsafe_get();
1632 if constexpr (TEST_SEASTORE
) {
1633 logger().info("seastore replay erase-1 begin");
1635 tree
->reload(NodeExtentManager::create_seastore(*tm
));
1636 logger().info("seastore replay erase-1 end");
1639 auto t
= create_read_transaction();
1640 INTR(tree
->validate
, *t
).unsafe_get();
1643 // test erase remaining
1645 auto t
= create_mutate_transaction();
1646 auto size
= kvs
.size();
1647 INTR_R(tree
->erase
, *t
, size
).unsafe_get();
1648 submit_transaction(std::move(t
));
1649 segment_cleaner
->run_until_halt().get0();
1652 auto t
= create_read_transaction();
1653 INTR(tree
->get_stats
, *t
).unsafe_get();
1655 if constexpr (TEST_SEASTORE
) {
1656 logger().info("seastore replay erase-2 begin");
1658 tree
->reload(NodeExtentManager::create_seastore(*tm
));
1659 logger().info("seastore replay erase-2 end");
1662 auto t
= create_read_transaction();
1663 INTR(tree
->validate
, *t
).unsafe_get();
1664 EXPECT_EQ(INTR(tree
->height
, *t
).unsafe_get0(), 1);
1667 if constexpr (!TEST_SEASTORE
) {
1668 auto p_dummy
= static_cast<DummyManager
*>(p_nm
);
1669 EXPECT_EQ(p_dummy
->size(), 1);
1675 TEST_F(d_seastore_tm_test_t
, 7_tree_insert_erase_eagain
)
1678 constexpr double EAGAIN_PROBABILITY
= 0.1;
1679 constexpr bool TRACK_CURSORS
= false;
1680 auto kvs
= KVPool
<test_item_t
>::create_raw_range(
1681 {8, 11, 64, 128, 255, 256},
1682 {8, 13, 64, 512, 2035, 2048},
1683 {8, 16, 128, 576, 992, 1200},
1684 {0, 8}, {0, 10}, {0, 4});
1685 auto moved_nm
= NodeExtentManager::create_seastore(
1686 *tm
, L_ADDR_MIN
, EAGAIN_PROBABILITY
);
1687 auto p_nm
= static_cast<SeastoreNodeExtentManager
<true>*>(moved_nm
.get());
1688 auto tree
= std::make_unique
<TreeBuilder
<TRACK_CURSORS
, ExtendedValue
>>(
1689 kvs
, std::move(moved_nm
));
1690 unsigned num_ops
= 0;
1691 unsigned num_ops_eagain
= 0;
1695 repeat_eagain([this, &tree
, &num_ops_eagain
] {
1697 return seastar::do_with(
1698 create_mutate_transaction(),
1699 [this, &tree
](auto &t
) {
1700 return INTR(tree
->bootstrap
, *t
1701 ).safe_then([this, &t
] {
1702 return submit_transaction_fut(*t
);
1706 segment_cleaner
->run_until_halt().get0();
1709 logger().warn("start inserting {} kvs ...", kvs
.size());
1711 auto iter
= kvs
.random_begin();
1712 while (iter
!= kvs
.random_end()) {
1714 repeat_eagain([this, &tree
, &num_ops_eagain
, &iter
] {
1716 return seastar::do_with(
1717 create_mutate_transaction(),
1718 [this, &tree
, &iter
](auto &t
) {
1719 return INTR_R(tree
->insert_one
, *t
, iter
1720 ).safe_then([this, &t
](auto cursor
) {
1721 cursor
.invalidate();
1722 return submit_transaction_fut(*t
);
1726 segment_cleaner
->run_until_halt().get0();
1732 p_nm
->set_generate_eagain(false);
1733 auto t
= create_read_transaction();
1734 INTR(tree
->get_stats
, *t
).unsafe_get0();
1735 p_nm
->set_generate_eagain(true);
1739 logger().warn("start lookup {} kvs ...", kvs
.size());
1741 auto iter
= kvs
.begin();
1742 while (iter
!= kvs
.end()) {
1744 repeat_eagain([this, &tree
, &num_ops_eagain
, &iter
] {
1746 auto t
= create_read_transaction();
1747 return INTR_R(tree
->validate_one
, *t
, iter
1748 ).safe_then([t
=std::move(t
)]{});
1755 logger().warn("start erase {} kvs ...", kvs
.size());
1758 auto iter
= kvs
.random_begin();
1759 while (iter
!= kvs
.random_end()) {
1761 repeat_eagain([this, &tree
, &num_ops_eagain
, &iter
] {
1763 return seastar::do_with(
1764 create_mutate_transaction(),
1765 [this, &tree
, &iter
](auto &t
) {
1766 return INTR_R(tree
->erase_one
, *t
, iter
1767 ).safe_then([this, &t
] () mutable {
1768 return submit_transaction_fut(*t
);
1772 segment_cleaner
->run_until_halt().get0();
1775 kvs
.erase_from_random(kvs
.random_begin(), kvs
.random_end());
1779 p_nm
->set_generate_eagain(false);
1780 auto t
= create_read_transaction();
1781 INTR(tree
->get_stats
, *t
).unsafe_get0();
1782 INTR(tree
->validate
, *t
).unsafe_get0();
1783 EXPECT_EQ(INTR(tree
->height
,*t
).unsafe_get0(), 1);
1786 // we can adjust EAGAIN_PROBABILITY to get a proper eagain_rate
1787 double eagain_rate
= num_ops_eagain
;
1788 eagain_rate
/= num_ops
;
1789 logger().info("eagain rate: {}", eagain_rate
);