]>
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 <stdio.h> | |
5 | #include <iostream> | |
6 | ||
7 | #include "gtest/gtest.h" | |
8 | ||
9 | #include "crimson/common/fixed_kv_node_layout.h" | |
10 | ||
11 | using namespace crimson; | |
12 | using namespace crimson::common; | |
13 | ||
14 | struct test_val_t { | |
15 | uint32_t t1 = 0; | |
16 | int32_t t2 = 0; | |
17 | ||
18 | bool operator==(const test_val_t &rhs) const { | |
19 | return rhs.t1 == t1 && rhs.t2 == t2; | |
20 | } | |
21 | bool operator!=(const test_val_t &rhs) const { | |
22 | return !(*this == rhs); | |
23 | } | |
24 | }; | |
25 | ||
26 | struct test_val_le_t { | |
27 | ceph_le32 t1 = init_le32(0); | |
28 | ceph_les32 t2 = init_les32(0); | |
29 | ||
30 | test_val_le_t() = default; | |
31 | test_val_le_t(const test_val_le_t &) = default; | |
32 | test_val_le_t(const test_val_t &nv) | |
33 | : t1(init_le32(nv.t1)), t2(init_les32(nv.t2)) {} | |
34 | ||
35 | operator test_val_t() const { | |
36 | return test_val_t{t1, t2}; | |
37 | } | |
38 | }; | |
39 | ||
40 | struct test_meta_t { | |
41 | uint32_t t1 = 0; | |
42 | uint32_t t2 = 0; | |
43 | ||
44 | bool operator==(const test_meta_t &rhs) const { | |
45 | return rhs.t1 == t1 && rhs.t2 == t2; | |
46 | } | |
47 | bool operator!=(const test_meta_t &rhs) const { | |
48 | return !(*this == rhs); | |
49 | } | |
50 | ||
51 | std::pair<test_meta_t, test_meta_t> split_into(uint32_t pivot) const { | |
52 | return std::make_pair( | |
53 | test_meta_t{t1, pivot}, | |
54 | test_meta_t{pivot, t2}); | |
55 | } | |
56 | ||
57 | static test_meta_t merge_from(const test_meta_t &lhs, const test_meta_t &rhs) { | |
58 | return test_meta_t{lhs.t1, rhs.t2}; | |
59 | } | |
60 | ||
61 | static std::pair<test_meta_t, test_meta_t> | |
62 | rebalance(const test_meta_t &lhs, const test_meta_t &rhs, uint32_t pivot) { | |
63 | return std::make_pair( | |
64 | test_meta_t{lhs.t1, pivot}, | |
65 | test_meta_t{pivot, rhs.t2}); | |
66 | } | |
67 | }; | |
68 | ||
69 | struct test_meta_le_t { | |
70 | ceph_le32 t1 = init_le32(0); | |
71 | ceph_le32 t2 = init_le32(0); | |
72 | ||
73 | test_meta_le_t() = default; | |
74 | test_meta_le_t(const test_meta_le_t &) = default; | |
75 | test_meta_le_t(const test_meta_t &nv) | |
76 | : t1(init_le32(nv.t1)), t2(init_le32(nv.t2)) {} | |
77 | ||
78 | operator test_meta_t() const { | |
79 | return test_meta_t{t1, t2}; | |
80 | } | |
81 | }; | |
82 | ||
83 | constexpr size_t CAPACITY = 339; | |
84 | ||
85 | struct TestNode : FixedKVNodeLayout< | |
86 | CAPACITY, | |
87 | test_meta_t, test_meta_le_t, | |
88 | uint32_t, ceph_le32, | |
89 | test_val_t, test_val_le_t> { | |
90 | char buf[4096]; | |
91 | TestNode() : FixedKVNodeLayout(buf) { | |
92 | memset(buf, 0, sizeof(buf)); | |
93 | set_meta({0, std::numeric_limits<uint32_t>::max()}); | |
94 | } | |
95 | TestNode(const TestNode &rhs) | |
96 | : FixedKVNodeLayout(buf) { | |
97 | ::memcpy(buf, rhs.buf, sizeof(buf)); | |
98 | } | |
99 | ||
100 | TestNode &operator=(const TestNode &rhs) { | |
101 | memcpy(buf, rhs.buf, sizeof(buf)); | |
102 | return *this; | |
103 | } | |
104 | }; | |
105 | ||
106 | TEST(FixedKVNodeTest, basic) { | |
107 | auto node = TestNode(); | |
108 | ASSERT_EQ(node.get_size(), 0); | |
109 | ||
110 | auto val = test_val_t{ 1, 1 }; | |
111 | node.journal_insert(node.begin(), 1, val, nullptr); | |
112 | ASSERT_EQ(node.get_size(), 1); | |
113 | ||
114 | auto iter = node.begin(); | |
115 | ASSERT_EQ(iter.get_key(), 1); | |
116 | ASSERT_EQ(val, iter.get_val()); | |
117 | ||
118 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), iter.get_next_key_or_max()); | |
119 | } | |
120 | ||
121 | TEST(FixedKVNodeTest, at_capacity) { | |
122 | auto node = TestNode(); | |
123 | ASSERT_EQ(CAPACITY, node.get_capacity()); | |
124 | ||
125 | ASSERT_EQ(node.get_size(), 0); | |
126 | ||
127 | unsigned short num = 0; | |
128 | auto iter = node.begin(); | |
129 | while (num < CAPACITY) { | |
130 | node.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
131 | ++num; | |
132 | ++iter; | |
133 | } | |
134 | ASSERT_EQ(node.get_size(), CAPACITY); | |
135 | ||
136 | num = 0; | |
137 | for (auto &i : node) { | |
138 | ASSERT_EQ(i.get_key(), num); | |
139 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
140 | if (num < (CAPACITY - 1)) { | |
141 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
142 | } else { | |
143 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
144 | } | |
145 | ++num; | |
146 | } | |
147 | } | |
148 | ||
149 | TEST(FixedKVNodeTest, split) { | |
150 | auto node = TestNode(); | |
151 | ||
152 | ASSERT_EQ(node.get_size(), 0); | |
153 | ||
154 | unsigned short num = 0; | |
155 | auto iter = node.begin(); | |
156 | while (num < CAPACITY) { | |
157 | node.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
158 | ++num; | |
159 | ++iter; | |
160 | } | |
161 | ASSERT_EQ(node.get_size(), CAPACITY); | |
162 | ||
163 | auto split_left = TestNode(); | |
164 | auto split_right = TestNode(); | |
165 | node.split_into(split_left, split_right); | |
166 | ||
167 | ASSERT_EQ(split_left.get_size() + split_right.get_size(), CAPACITY); | |
168 | ASSERT_EQ(split_left.get_meta().t1, split_left.begin()->get_key()); | |
169 | ASSERT_EQ(split_left.get_meta().t2, split_right.get_meta().t1); | |
170 | ASSERT_EQ(split_right.get_meta().t2, std::numeric_limits<uint32_t>::max()); | |
171 | ||
172 | num = 0; | |
173 | for (auto &i : split_left) { | |
174 | ASSERT_EQ(i.get_key(), num); | |
175 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
176 | if (num < split_left.get_size() - 1) { | |
177 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
178 | } else { | |
179 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
180 | } | |
181 | ++num; | |
182 | } | |
183 | for (auto &i : split_right) { | |
184 | ASSERT_EQ(i.get_key(), num); | |
185 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
186 | if (num < CAPACITY - 1) { | |
187 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
188 | } else { | |
189 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
190 | } | |
191 | ++num; | |
192 | } | |
193 | ASSERT_EQ(num, CAPACITY); | |
194 | } | |
195 | ||
196 | TEST(FixedKVNodeTest, merge) { | |
197 | auto node = TestNode(); | |
198 | auto node2 = TestNode(); | |
199 | ||
200 | ASSERT_EQ(node.get_size(), 0); | |
201 | ASSERT_EQ(node2.get_size(), 0); | |
202 | ||
203 | unsigned short num = 0; | |
204 | auto iter = node.begin(); | |
205 | while (num < CAPACITY/2) { | |
206 | node.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
207 | ++num; | |
208 | ++iter; | |
209 | } | |
210 | node.set_meta({0, num}); | |
211 | node2.set_meta({num, std::numeric_limits<uint32_t>::max()}); | |
212 | iter = node2.begin(); | |
213 | while (num < (2 * (CAPACITY / 2))) { | |
214 | node2.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
215 | ++num; | |
216 | ++iter; | |
217 | } | |
218 | ||
219 | ASSERT_EQ(node.get_size(), CAPACITY / 2); | |
220 | ASSERT_EQ(node2.get_size(), CAPACITY / 2); | |
221 | ||
222 | auto total = node.get_size() + node2.get_size(); | |
223 | ||
224 | auto node_merged = TestNode(); | |
225 | node_merged.merge_from(node, node2); | |
226 | ||
227 | ASSERT_EQ( | |
228 | node_merged.get_meta(), | |
229 | (test_meta_t{0, std::numeric_limits<uint32_t>::max()})); | |
230 | ||
231 | ASSERT_EQ(node_merged.get_size(), total); | |
232 | num = 0; | |
233 | for (auto &i : node_merged) { | |
234 | ASSERT_EQ(i.get_key(), num); | |
235 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
236 | if (num < node_merged.get_size() - 1) { | |
237 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
238 | } else { | |
239 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
240 | } | |
241 | ++num; | |
242 | } | |
243 | ASSERT_EQ(num, total); | |
244 | } | |
245 | ||
246 | void run_balance_test(unsigned left, unsigned right, bool prefer_left) | |
247 | { | |
248 | auto node = TestNode(); | |
249 | auto node2 = TestNode(); | |
250 | ||
251 | ASSERT_EQ(node.get_size(), 0); | |
252 | ASSERT_EQ(node2.get_size(), 0); | |
253 | ||
254 | unsigned short num = 0; | |
255 | auto iter = node.begin(); | |
256 | while (num < left) { | |
257 | node.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
258 | ++num; | |
259 | ++iter; | |
260 | } | |
261 | node.set_meta({0, num}); | |
262 | node2.set_meta({num, std::numeric_limits<uint32_t>::max()}); | |
263 | iter = node2.begin(); | |
264 | while (num < (left + right)) { | |
265 | node2.journal_insert(iter, num, test_val_t{num, num}, nullptr); | |
266 | ++num; | |
267 | ++iter; | |
268 | } | |
269 | ||
270 | ASSERT_EQ(node.get_size(), left); | |
271 | ASSERT_EQ(node2.get_size(), right); | |
272 | ||
273 | auto total = node.get_size() + node2.get_size(); | |
274 | ||
275 | auto node_balanced = TestNode(); | |
276 | auto node_balanced2 = TestNode(); | |
277 | auto pivot = TestNode::balance_into_new_nodes( | |
278 | node, | |
279 | node2, | |
280 | prefer_left, | |
281 | node_balanced, | |
282 | node_balanced2); | |
283 | ||
284 | ASSERT_EQ(total, node_balanced.get_size() + node_balanced2.get_size()); | |
285 | ||
286 | unsigned left_size, right_size; | |
287 | if (total % 2) { | |
288 | if (prefer_left) { | |
289 | left_size = (total/2) + 1; | |
290 | right_size = total/2; | |
291 | } else { | |
292 | left_size = total/2; | |
293 | right_size = (total/2) + 1; | |
294 | } | |
295 | } else { | |
296 | left_size = right_size = total/2; | |
297 | } | |
298 | ASSERT_EQ(pivot, left_size); | |
299 | ASSERT_EQ(left_size, node_balanced.get_size()); | |
300 | ASSERT_EQ(right_size, node_balanced2.get_size()); | |
301 | ||
302 | ASSERT_EQ( | |
303 | node_balanced.get_meta(), | |
304 | (test_meta_t{0, left_size})); | |
305 | ASSERT_EQ( | |
306 | node_balanced2.get_meta(), | |
307 | (test_meta_t{left_size, std::numeric_limits<uint32_t>::max()})); | |
308 | ||
309 | num = 0; | |
310 | for (auto &i: node_balanced) { | |
311 | ASSERT_EQ(i.get_key(), num); | |
312 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
313 | if (num < node_balanced.get_size() - 1) { | |
314 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
315 | } else { | |
316 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
317 | } | |
318 | ++num; | |
319 | } | |
320 | for (auto &i: node_balanced2) { | |
321 | ASSERT_EQ(i.get_key(), num); | |
322 | ASSERT_EQ(i.get_val(), (test_val_t{num, num})); | |
323 | if (num < total - 1) { | |
324 | ASSERT_EQ(i.get_next_key_or_max(), num + 1); | |
325 | } else { | |
326 | ASSERT_EQ(std::numeric_limits<uint32_t>::max(), i.get_next_key_or_max()); | |
327 | } | |
328 | ++num; | |
329 | } | |
330 | } | |
331 | ||
332 | TEST(FixedKVNodeTest, balanced) { | |
333 | run_balance_test(CAPACITY / 2, CAPACITY, true); | |
334 | run_balance_test(CAPACITY / 2, CAPACITY, false); | |
335 | run_balance_test(CAPACITY, CAPACITY / 2, true); | |
336 | run_balance_test(CAPACITY, CAPACITY / 2, false); | |
337 | run_balance_test(CAPACITY - 1, CAPACITY / 2, true); | |
338 | run_balance_test(CAPACITY / 2, CAPACITY - 1, false); | |
339 | run_balance_test(CAPACITY / 2, CAPACITY / 2, false); | |
340 | } | |
341 | ||
342 | void run_replay_test( | |
343 | std::vector<std::function<void(TestNode&, TestNode::delta_buffer_t&)>> &&f | |
344 | ) { | |
345 | TestNode node; | |
346 | for (unsigned i = 0; i < f.size(); ++i) { | |
347 | TestNode::delta_buffer_t buf; | |
348 | TestNode replayed = node; | |
349 | f[i](node, buf); | |
350 | buf.replay(replayed); | |
351 | ASSERT_EQ(node.get_size(), replayed.get_size()); | |
352 | ASSERT_EQ(node, replayed); | |
353 | } | |
354 | } | |
355 | ||
356 | TEST(FixedKVNodeTest, replay) { | |
357 | run_replay_test({ | |
358 | [](auto &n, auto &b) { | |
359 | n.journal_insert(n.lower_bound(1), 1, test_val_t{1, 1}, &b); | |
360 | ASSERT_EQ(1, n.get_size()); | |
361 | }, | |
362 | [](auto &n, auto &b) { | |
363 | n.journal_insert(n.lower_bound(3), 3, test_val_t{1, 2}, &b); | |
364 | ASSERT_EQ(2, n.get_size()); | |
365 | }, | |
366 | [](auto &n, auto &b) { | |
367 | n.journal_remove(n.find(3), &b); | |
368 | ASSERT_EQ(1, n.get_size()); | |
369 | }, | |
370 | [](auto &n, auto &b) { | |
371 | n.journal_insert(n.lower_bound(2), 2, test_val_t{5, 1}, &b); | |
372 | ASSERT_EQ(2, n.get_size()); | |
373 | } | |
374 | }); | |
375 | ||
376 | } |