summaryrefslogtreecommitdiffstats
path: root/src/test/crimson/test_fixed_kv_node_layout.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/test/crimson/test_fixed_kv_node_layout.cc')
-rw-r--r--src/test/crimson/test_fixed_kv_node_layout.cc376
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());
+ }
+ });
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-11 16:42:30 +0000