diff options
Diffstat (limited to '')
-rw-r--r-- | src/test/crimson/test_fixed_kv_node_layout.cc | 376 |
1 files changed, 376 insertions, 0 deletions
diff --git a/src/test/crimson/test_fixed_kv_node_layout.cc b/src/test/crimson/test_fixed_kv_node_layout.cc new file mode 100644 index 000000000..5f59c4e5e --- /dev/null +++ b/src/test/crimson/test_fixed_kv_node_layout.cc @@ -0,0 +1,376 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include <stdio.h> +#include <iostream> + +#include "gtest/gtest.h" + +#include "crimson/common/fixed_kv_node_layout.h" + +using namespace crimson; +using namespace crimson::common; + +struct test_val_t { + uint32_t t1 = 0; + int32_t t2 = 0; + + bool operator==(const test_val_t &rhs) const { + return rhs.t1 == t1 && rhs.t2 == t2; + } + bool operator!=(const test_val_t &rhs) const { + return !(*this == rhs); + } +}; + +struct test_val_le_t { + ceph_le32 t1 = init_le32(0); + ceph_les32 t2 = init_les32(0); + + test_val_le_t() = default; + test_val_le_t(const test_val_le_t &) = default; + test_val_le_t(const test_val_t &nv) + : t1(init_le32(nv.t1)), t2(init_les32(nv.t2)) {} + + operator test_val_t() const { + return test_val_t{t1, t2}; + } +}; + +struct test_meta_t { + uint32_t t1 = 0; + uint32_t t2 = 0; + + bool operator==(const test_meta_t &rhs) const { + return rhs.t1 == t1 && rhs.t2 == t2; + } + bool operator!=(const test_meta_t &rhs) const { + return !(*this == rhs); + } + + std::pair<test_meta_t, test_meta_t> split_into(uint32_t pivot) const { + return std::make_pair( + test_meta_t{t1, pivot}, + test_meta_t{pivot, t2}); + } + + static test_meta_t merge_from(const test_meta_t &lhs, const test_meta_t &rhs) { + return test_meta_t{lhs.t1, rhs.t2}; + } + + static std::pair<test_meta_t, test_meta_t> + rebalance(const test_meta_t &lhs, const test_meta_t &rhs, uint32_t pivot) { + return std::make_pair( + test_meta_t{lhs.t1, pivot}, + test_meta_t{pivot, rhs.t2}); + } +}; + +struct test_meta_le_t { + ceph_le32 t1 = init_le32(0); + ceph_le32 t2 = init_le32(0); + + test_meta_le_t() = default; + test_meta_le_t(const test_meta_le_t &) = default; + test_meta_le_t(const test_meta_t &nv) + : t1(init_le32(nv.t1)), t2(init_le32(nv.t2)) {} + + operator test_meta_t() const { + return test_meta_t{t1, t2}; + } +}; + +constexpr size_t CAPACITY = 339; + +struct TestNode : FixedKVNodeLayout< + CAPACITY, + test_meta_t, test_meta_le_t, + uint32_t, ceph_le32, + test_val_t, test_val_le_t> { + char buf[4096]; + TestNode() : FixedKVNodeLayout(buf) { + memset(buf, 0, sizeof(buf)); + set_meta({0, std::numeric_limits<uint32_t>::max()}); + } + TestNode(const TestNode &rhs) + : FixedKVNodeLayout(buf) { + ::memcpy(buf, rhs.buf, sizeof(buf)); + } + + TestNode &operator=(const TestNode &rhs) { + memcpy(buf, rhs.buf, sizeof(buf)); + return *this; + } +}; + +TEST(FixedKVNodeTest, basic) { + auto node = TestNode(); + ASSERT_EQ(node.get_size(), 0); + + auto val = test_val_t{ 1, 1 }; + node.journal_insert(node.begin(), 1, val, nullptr); + ASSERT_EQ(node.get_size(), 1); + + auto iter = node.begin(); + ASSERT_EQ(iter.get_key(), 1); + ASSERT_EQ(val, iter.get_val()); + + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), iter.get_next_key_or_max()); +} + +TEST(FixedKVNodeTest, at_capacity) { + auto node = TestNode(); + ASSERT_EQ(CAPACITY, node.get_capacity()); + + ASSERT_EQ(node.get_size(), 0); + + unsigned short num = 0; + auto iter = node.begin(); + while (num < CAPACITY) { + node.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + ASSERT_EQ(node.get_size(), CAPACITY); + + num = 0; + for (auto &i : node) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < (CAPACITY - 1)) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } +} + +TEST(FixedKVNodeTest, split) { + auto node = TestNode(); + + ASSERT_EQ(node.get_size(), 0); + + unsigned short num = 0; + auto iter = node.begin(); + while (num < CAPACITY) { + node.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + ASSERT_EQ(node.get_size(), CAPACITY); + + auto split_left = TestNode(); + auto split_right = TestNode(); + node.split_into(split_left, split_right); + + ASSERT_EQ(split_left.get_size() + split_right.get_size(), CAPACITY); + ASSERT_EQ(split_left.get_meta().t1, split_left.begin()->get_key()); + ASSERT_EQ(split_left.get_meta().t2, split_right.get_meta().t1); + ASSERT_EQ(split_right.get_meta().t2, std::numeric_limits<uint32_t>::max()); + + num = 0; + for (auto &i : split_left) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < split_left.get_size() - 1) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } + for (auto &i : split_right) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < CAPACITY - 1) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } + ASSERT_EQ(num, CAPACITY); +} + +TEST(FixedKVNodeTest, merge) { + auto node = TestNode(); + auto node2 = TestNode(); + + ASSERT_EQ(node.get_size(), 0); + ASSERT_EQ(node2.get_size(), 0); + + unsigned short num = 0; + auto iter = node.begin(); + while (num < CAPACITY/2) { + node.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + node.set_meta({0, num}); + node2.set_meta({num, std::numeric_limits<uint32_t>::max()}); + iter = node2.begin(); + while (num < (2 * (CAPACITY / 2))) { + node2.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + + ASSERT_EQ(node.get_size(), CAPACITY / 2); + ASSERT_EQ(node2.get_size(), CAPACITY / 2); + + auto total = node.get_size() + node2.get_size(); + + auto node_merged = TestNode(); + node_merged.merge_from(node, node2); + + ASSERT_EQ( + node_merged.get_meta(), + (test_meta_t{0, std::numeric_limits<uint32_t>::max()})); + + ASSERT_EQ(node_merged.get_size(), total); + num = 0; + for (auto &i : node_merged) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < node_merged.get_size() - 1) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } + ASSERT_EQ(num, total); +} + +void run_balance_test(unsigned left, unsigned right, bool prefer_left) +{ + auto node = TestNode(); + auto node2 = TestNode(); + + ASSERT_EQ(node.get_size(), 0); + ASSERT_EQ(node2.get_size(), 0); + + unsigned short num = 0; + auto iter = node.begin(); + while (num < left) { + node.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + node.set_meta({0, num}); + node2.set_meta({num, std::numeric_limits<uint32_t>::max()}); + iter = node2.begin(); + while (num < (left + right)) { + node2.journal_insert(iter, num, test_val_t{num, num}, nullptr); + ++num; + ++iter; + } + + ASSERT_EQ(node.get_size(), left); + ASSERT_EQ(node2.get_size(), right); + + auto total = node.get_size() + node2.get_size(); + + auto node_balanced = TestNode(); + auto node_balanced2 = TestNode(); + auto pivot = TestNode::balance_into_new_nodes( + node, + node2, + prefer_left, + node_balanced, + node_balanced2); + + ASSERT_EQ(total, node_balanced.get_size() + node_balanced2.get_size()); + + unsigned left_size, right_size; + if (total % 2) { + if (prefer_left) { + left_size = (total/2) + 1; + right_size = total/2; + } else { + left_size = total/2; + right_size = (total/2) + 1; + } + } else { + left_size = right_size = total/2; + } + ASSERT_EQ(pivot, left_size); + ASSERT_EQ(left_size, node_balanced.get_size()); + ASSERT_EQ(right_size, node_balanced2.get_size()); + + ASSERT_EQ( + node_balanced.get_meta(), + (test_meta_t{0, left_size})); + ASSERT_EQ( + node_balanced2.get_meta(), + (test_meta_t{left_size, std::numeric_limits<uint32_t>::max()})); + + num = 0; + for (auto &i: node_balanced) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < node_balanced.get_size() - 1) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } + for (auto &i: node_balanced2) { + ASSERT_EQ(i.get_key(), num); + ASSERT_EQ(i.get_val(), (test_val_t{num, num})); + if (num < total - 1) { + ASSERT_EQ(i.get_next_key_or_max(), num + 1); + } else { + ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); + } + ++num; + } +} + +TEST(FixedKVNodeTest, balanced) { + run_balance_test(CAPACITY / 2, CAPACITY, true); + run_balance_test(CAPACITY / 2, CAPACITY, false); + run_balance_test(CAPACITY, CAPACITY / 2, true); + run_balance_test(CAPACITY, CAPACITY / 2, false); + run_balance_test(CAPACITY - 1, CAPACITY / 2, true); + run_balance_test(CAPACITY / 2, CAPACITY - 1, false); + run_balance_test(CAPACITY / 2, CAPACITY / 2, false); +} + +void run_replay_test( + std::vector<std::function<void(TestNode&, TestNode::delta_buffer_t&)>> &&f +) { + TestNode node; + for (unsigned i = 0; i < f.size(); ++i) { + TestNode::delta_buffer_t buf; + TestNode replayed = node; + f[i](node, buf); + buf.replay(replayed); + ASSERT_EQ(node.get_size(), replayed.get_size()); + ASSERT_EQ(node, replayed); + } +} + +TEST(FixedKVNodeTest, replay) { + run_replay_test({ + [](auto &n, auto &b) { + n.journal_insert(n.lower_bound(1), 1, test_val_t{1, 1}, &b); + ASSERT_EQ(1, n.get_size()); + }, + [](auto &n, auto &b) { + n.journal_insert(n.lower_bound(3), 3, test_val_t{1, 2}, &b); + ASSERT_EQ(2, n.get_size()); + }, + [](auto &n, auto &b) { + n.journal_remove(n.find(3), &b); + ASSERT_EQ(1, n.get_size()); + }, + [](auto &n, auto &b) { + n.journal_insert(n.lower_bound(2), 2, test_val_t{5, 1}, &b); + ASSERT_EQ(2, n.get_size()); + } + }); + +} |