[ceph.git] / ceph / src / test / crimson / seastore / onode_tree / test_node.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab

#include <gtest/gtest.h>

#include "crimson/os/seastore/onode_manager/simple-fltree/onode_node.h"

using crimson::os::seastore::Onode;
using crimson::os::seastore::OnodeRef;

TEST(OnodeNode, denc)
{
  Onode onode{"hello"};
  bufferlist bl;
  ceph::encode(onode, bl);
  bl.rebuild();
  auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
  auto actual_onode = flattened->decode();
  ASSERT_EQ(*actual_onode, onode);
}

TEST(OnodeNode, lookup)
{
  static constexpr size_t BLOCK_SIZE = 512;
  char buf[BLOCK_SIZE];
  using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
  auto leaf = new (buf) leaf_node_0;
  ghobject_t oid{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
  {
    auto [slot, found] = leaf->lower_bound(oid);
    ASSERT_FALSE(found);
    ASSERT_EQ(0, slot);
  }
  Onode onode{"hello"};
  bufferlist bl;
  ceph::encode(onode, bl);
  bl.rebuild();
  auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
  leaf->insert_at(0, oid, *flattened);
  {
    auto [slot, found] = leaf->lower_bound(oid);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
    const auto& [key1, key2] = leaf->key_at(slot);
    auto& item = leaf->item_at(key1);
    auto actual_onode = item.decode();
    ASSERT_EQ(*actual_onode, onode);
  }
}

TEST(OnodeNode, grab_from_right)
{
  static constexpr size_t BLOCK_SIZE = 512;
  char buf1[BLOCK_SIZE];
  char buf2[BLOCK_SIZE];
  using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
  auto leaf1 = new (buf1) leaf_node_0;
  auto leaf2 = new (buf2) leaf_node_0;
  auto& dummy_parent = *leaf1;

  ghobject_t oid1{hobject_t{object_t{"earth"}, "", 0, 0, 0, "solar"}};
  ghobject_t oid2{hobject_t{object_t{"jupiter"}, "", 0, 0, 0, "solar"}};
  ghobject_t oid3{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
  Onode onode{"hello"};
  bufferlist bl;
  ceph::encode(onode, bl);
  bl.rebuild();
  auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
  // so they are ordered as they should
  leaf1->insert_at(0, oid1, *flattened);
  ASSERT_EQ(1, leaf1->count);
  {
    auto [slot, found] = leaf1->lower_bound(oid1);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
  }
  {
    leaf2->insert_at(0, oid2, *flattened);
    auto [slot, found] = leaf2->lower_bound(oid2);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
  }
  {
    leaf2->insert_at(1, oid3, *flattened);
    auto [slot, found] = leaf2->lower_bound(oid3);
    ASSERT_TRUE(found);
    ASSERT_EQ(1, slot);
  }
  ASSERT_EQ(2, leaf2->count);

  // normally we let left merge right, so we just need to remove an
  // entry in parent, let's keep this convention here
  auto mover = make_mover(dummy_parent, *leaf2, *leaf1, 0);
  // just grab a single item from right
  mover.move_from(0, 1, 1);
  auto to_delta = mover.to_delta();
  ASSERT_EQ(to_delta.op_t::insert_back, to_delta.op);
  leaf1->insert_back(std::move(to_delta.keys), std::move(to_delta.cells));

  ASSERT_EQ(2, leaf1->count);
  {
    auto [slot, found] = leaf1->lower_bound(oid2);
    ASSERT_TRUE(found);
    ASSERT_EQ(1, slot);
  }

  auto from_delta = mover.from_delta();
  ASSERT_EQ(from_delta.op_t::shift_left, from_delta.op);
  leaf2->shift_left(from_delta.n, 0);
  ASSERT_EQ(1, leaf2->count);
}

TEST(OnodeNode, merge_right)
{
  static constexpr size_t BLOCK_SIZE = 512;
  char buf1[BLOCK_SIZE];
  char buf2[BLOCK_SIZE];
  using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
  auto leaf1 = new (buf1) leaf_node_0;
  auto leaf2 = new (buf2) leaf_node_0;
  auto& dummy_parent = leaf1;

  ghobject_t oid1{hobject_t{object_t{"earth"}, "", 0, 0, 0, "solar"}};
  ghobject_t oid2{hobject_t{object_t{"jupiter"}, "", 0, 0, 0, "solar"}};
  ghobject_t oid3{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
  Onode onode{"hello"};
  bufferlist bl;
  ceph::encode(onode, bl);
  bl.rebuild();
  auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
  // so they are ordered as they should
  leaf1->insert_at(0, oid1, *flattened);
  ASSERT_EQ(1, leaf1->count);
  {
    auto [slot, found] = leaf1->lower_bound(oid1);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
  }
  {
    leaf2->insert_at(0, oid2, *flattened);
    auto [slot, found] = leaf2->lower_bound(oid2);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
  }
  {
    leaf2->insert_at(1, oid3, *flattened);
    auto [slot, found] = leaf2->lower_bound(oid3);
    ASSERT_TRUE(found);
    ASSERT_EQ(1, slot);
  }
  ASSERT_EQ(2, leaf2->count);

  // normally we let left merge right, so we just need to remove an
  // entry in parent, let's keep this convention here
  auto mover = make_mover(dummy_parent, *leaf2, *leaf1, 0);
  // just grab a single item from right
  mover.move_from(0, 1, 2);
  auto to_delta = mover.to_delta();
  ASSERT_EQ(to_delta.op_t::insert_back, to_delta.op);
  leaf1->insert_back(std::move(to_delta.keys), std::move(to_delta.cells));

  ASSERT_EQ(3, leaf1->count);
  {
    auto [slot, found] = leaf1->lower_bound(oid2);
    ASSERT_TRUE(found);
    ASSERT_EQ(1, slot);
  }
  {
    auto [slot, found] = leaf1->lower_bound(oid3);
    ASSERT_TRUE(found);
    ASSERT_EQ(2, slot);
  }

  // its onode tree's responsibility to retire the node
  auto from_delta = mover.from_delta();
  ASSERT_EQ(from_delta.op_t::nop, from_delta.op);
}

TEST(OnodeNode, remove_basic)
{
  static constexpr size_t BLOCK_SIZE = 512;
  char buf[BLOCK_SIZE];
  using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
  auto leaf = new (buf) leaf_node_0;
  ghobject_t oid{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
  {
    auto [slot, found] = leaf->lower_bound(oid);
    ASSERT_FALSE(found);
    ASSERT_EQ(0, slot);
  }
  Onode onode{"hello"};
  bufferlist bl;
  ceph::encode(onode, bl);
  bl.rebuild();
  auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
  leaf->insert_at(0, oid, *flattened);
  {
    auto [slot, found] = leaf->lower_bound(oid);
    ASSERT_TRUE(found);
    ASSERT_EQ(0, slot);
    leaf->remove_from(slot);
  }
  {
    auto [slot, found] = leaf->lower_bound(oid);
    ASSERT_FALSE(found);
  }
}
Commit	Line	Data
f67539c2 TL	1	// -- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t --
	2	// vim: ts=8 sw=2 smarttab
	3
	4	#include <gtest/gtest.h>
	5
	6	#include "crimson/os/seastore/onode_manager/simple-fltree/onode_node.h"
	7
	8	using crimson::os::seastore::Onode;
	9	using crimson::os::seastore::OnodeRef;
	10
	11	TEST(OnodeNode, denc)
	12	{
	13	Onode onode{"hello"};
	14	bufferlist bl;
	15	ceph::encode(onode, bl);
	16	bl.rebuild();
	17	auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
	18	auto actual_onode = flattened->decode();
	19	ASSERT_EQ(*actual_onode, onode);
	20	}
	21
	22	TEST(OnodeNode, lookup)
	23	{
	24	static constexpr size_t BLOCK_SIZE = 512;
	25	char buf[BLOCK_SIZE];
	26	using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
	27	auto leaf = new (buf) leaf_node_0;
	28	ghobject_t oid{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
	29	{
	30	auto [slot, found] = leaf->lower_bound(oid);
	31	ASSERT_FALSE(found);
	32	ASSERT_EQ(0, slot);
	33	}
	34	Onode onode{"hello"};
	35	bufferlist bl;
	36	ceph::encode(onode, bl);
	37	bl.rebuild();
	38	auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
	39	leaf->insert_at(0, oid, *flattened);
	40	{
	41	auto [slot, found] = leaf->lower_bound(oid);
	42	ASSERT_TRUE(found);
	43	ASSERT_EQ(0, slot);
	44	const auto& [key1, key2] = leaf->key_at(slot);
	45	auto& item = leaf->item_at(key1);
	46	auto actual_onode = item.decode();
	47	ASSERT_EQ(*actual_onode, onode);
	48	}
	49	}
	50
	51	TEST(OnodeNode, grab_from_right)
	52	{
	53	static constexpr size_t BLOCK_SIZE = 512;
	54	char buf1[BLOCK_SIZE];
	55	char buf2[BLOCK_SIZE];
	56	using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
	57	auto leaf1 = new (buf1) leaf_node_0;
	58	auto leaf2 = new (buf2) leaf_node_0;
	59	auto& dummy_parent = *leaf1;
	60
	61	ghobject_t oid1{hobject_t{object_t{"earth"}, "", 0, 0, 0, "solar"}};
	62	ghobject_t oid2{hobject_t{object_t{"jupiter"}, "", 0, 0, 0, "solar"}};
	63	ghobject_t oid3{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
	64	Onode onode{"hello"};
65	bufferlist bl;
66	ceph::encode(onode, bl);
67	bl.rebuild();
68	auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
69	// so they are ordered as they should
70	leaf1->insert_at(0, oid1, *flattened);
71	ASSERT_EQ(1, leaf1->count);
72	{
73	auto [slot, found] = leaf1->lower_bound(oid1);
74	ASSERT_TRUE(found);
75	ASSERT_EQ(0, slot);
76	}
77	{
78	leaf2->insert_at(0, oid2, *flattened);
79	auto [slot, found] = leaf2->lower_bound(oid2);
80	ASSERT_TRUE(found);
81	ASSERT_EQ(0, slot);
82	}
83	{
84	leaf2->insert_at(1, oid3, *flattened);
85	auto [slot, found] = leaf2->lower_bound(oid3);
86	ASSERT_TRUE(found);
87	ASSERT_EQ(1, slot);
88	}
89	ASSERT_EQ(2, leaf2->count);
90
91	// normally we let left merge right, so we just need to remove an
92	// entry in parent, let's keep this convention here
93	auto mover = make_mover(dummy_parent, leaf2, leaf1, 0);
94	// just grab a single item from right
95	mover.move_from(0, 1, 1);
96	auto to_delta = mover.to_delta();
97	ASSERT_EQ(to_delta.op_t::insert_back, to_delta.op);
98	leaf1->insert_back(std::move(to_delta.keys), std::move(to_delta.cells));
99
100	ASSERT_EQ(2, leaf1->count);
101	{
102	auto [slot, found] = leaf1->lower_bound(oid2);
103	ASSERT_TRUE(found);
104	ASSERT_EQ(1, slot);
105	}
106
107	auto from_delta = mover.from_delta();
108	ASSERT_EQ(from_delta.op_t::shift_left, from_delta.op);
109	leaf2->shift_left(from_delta.n, 0);
110	ASSERT_EQ(1, leaf2->count);
111	}
112
113	TEST(OnodeNode, merge_right)
114	{
115	static constexpr size_t BLOCK_SIZE = 512;
116	char buf1[BLOCK_SIZE];
117	char buf2[BLOCK_SIZE];
118	using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
119	auto leaf1 = new (buf1) leaf_node_0;
120	auto leaf2 = new (buf2) leaf_node_0;
121	auto& dummy_parent = leaf1;
122
123	ghobject_t oid1{hobject_t{object_t{"earth"}, "", 0, 0, 0, "solar"}};
124	ghobject_t oid2{hobject_t{object_t{"jupiter"}, "", 0, 0, 0, "solar"}};
125	ghobject_t oid3{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
126	Onode onode{"hello"};
127	bufferlist bl;
128	ceph::encode(onode, bl);
129	bl.rebuild();
130	auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
131	// so they are ordered as they should
132	leaf1->insert_at(0, oid1, *flattened);
133	ASSERT_EQ(1, leaf1->count);
134	{
135	auto [slot, found] = leaf1->lower_bound(oid1);
136	ASSERT_TRUE(found);
137	ASSERT_EQ(0, slot);
138	}
139	{
140	leaf2->insert_at(0, oid2, *flattened);
141	auto [slot, found] = leaf2->lower_bound(oid2);
142	ASSERT_TRUE(found);
143	ASSERT_EQ(0, slot);
144	}
145	{
146	leaf2->insert_at(1, oid3, *flattened);
147	auto [slot, found] = leaf2->lower_bound(oid3);
148	ASSERT_TRUE(found);
149	ASSERT_EQ(1, slot);
150	}
151	ASSERT_EQ(2, leaf2->count);
152
153	// normally we let left merge right, so we just need to remove an
154	// entry in parent, let's keep this convention here
155	auto mover = make_mover(dummy_parent, leaf2, leaf1, 0);
156	// just grab a single item from right
157	mover.move_from(0, 1, 2);
158	auto to_delta = mover.to_delta();
159	ASSERT_EQ(to_delta.op_t::insert_back, to_delta.op);
160	leaf1->insert_back(std::move(to_delta.keys), std::move(to_delta.cells));
161
162	ASSERT_EQ(3, leaf1->count);
163	{
164	auto [slot, found] = leaf1->lower_bound(oid2);
165	ASSERT_TRUE(found);
166	ASSERT_EQ(1, slot);
167	}
168	{
169	auto [slot, found] = leaf1->lower_bound(oid3);
170	ASSERT_TRUE(found);
171	ASSERT_EQ(2, slot);
172	}
173
174	// its onode tree's responsibility to retire the node
175	auto from_delta = mover.from_delta();
176	ASSERT_EQ(from_delta.op_t::nop, from_delta.op);
177	}
178
179	TEST(OnodeNode, remove_basic)
180	{
181	static constexpr size_t BLOCK_SIZE = 512;
182	char buf[BLOCK_SIZE];
183	using leaf_node_0 = node_t<BLOCK_SIZE, 0, ntype_t::leaf>;
184	auto leaf = new (buf) leaf_node_0;
185	ghobject_t oid{hobject_t{object_t{"saturn"}, "", 0, 0, 0, "solar"}};
186	{
187	auto [slot, found] = leaf->lower_bound(oid);
188	ASSERT_FALSE(found);
189	ASSERT_EQ(0, slot);
190	}
191	Onode onode{"hello"};
192	bufferlist bl;
193	ceph::encode(onode, bl);
194	bl.rebuild();
195	auto flattened = reinterpret_cast<const onode_t*>(bl.c_str());
196	leaf->insert_at(0, oid, *flattened);
197	{
198	auto [slot, found] = leaf->lower_bound(oid);
199	ASSERT_TRUE(found);
200	ASSERT_EQ(0, slot);
201	leaf->remove_from(slot);
202	}
203	{
204	auto [slot, found] = leaf->lower_bound(oid);
205	ASSERT_FALSE(found);
206	}
207	}