]>
Commit | Line | Data |
---|---|---|
f67539c2 TL |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #pragma once | |
5 | ||
6 | #include <cassert> | |
7 | #include <cstring> | |
8 | #include <random> | |
9 | #include <string> | |
10 | #include <sstream> | |
11 | #include <utility> | |
12 | #include <vector> | |
13 | ||
14 | #include "crimson/common/log.h" | |
15 | #include "stages/key_layout.h" | |
16 | #include "tree.h" | |
17 | ||
18 | /** | |
19 | * tree_utils.h | |
20 | * | |
21 | * Contains shared logic for unit tests and perf tool. | |
22 | */ | |
23 | ||
24 | namespace crimson::os::seastore::onode { | |
25 | ||
26 | class Onodes { | |
27 | public: | |
28 | Onodes(size_t n) { | |
29 | for (size_t i = 1; i <= n; ++i) { | |
30 | auto p_onode = &create(i * 8); | |
31 | onodes.push_back(p_onode); | |
32 | } | |
33 | } | |
34 | ||
35 | Onodes(std::vector<size_t> sizes) { | |
36 | for (auto& size : sizes) { | |
37 | auto p_onode = &create(size); | |
38 | onodes.push_back(p_onode); | |
39 | } | |
40 | } | |
41 | ||
42 | ~Onodes() = default; | |
43 | ||
44 | const onode_t& create(size_t size) { | |
45 | ceph_assert(size <= std::numeric_limits<uint16_t>::max()); | |
46 | onode_t config{static_cast<uint16_t>(size), id++}; | |
47 | auto onode = onode_t::allocate(config); | |
48 | auto p_onode = onode.get(); | |
49 | tracked_onodes.push_back(std::move(onode)); | |
50 | return *reinterpret_cast<onode_t*>(p_onode); | |
51 | } | |
52 | ||
53 | const onode_t& pick() const { | |
54 | auto index = rd() % onodes.size(); | |
55 | return *onodes[index]; | |
56 | } | |
57 | ||
58 | const onode_t& pick_largest() const { | |
59 | return *onodes[onodes.size() - 1]; | |
60 | } | |
61 | ||
62 | static void validate_cursor( | |
63 | const Btree::Cursor& cursor, const ghobject_t& key, const onode_t& onode) { | |
64 | ceph_assert(!cursor.is_end()); | |
65 | ceph_assert(cursor.get_ghobj() == key); | |
66 | ceph_assert(cursor.value()); | |
67 | ceph_assert(cursor.value() != &onode); | |
68 | ceph_assert(*cursor.value() == onode); | |
69 | onode_t::validate_tail_magic(*cursor.value()); | |
70 | } | |
71 | ||
72 | private: | |
73 | uint16_t id = 0; | |
74 | mutable std::random_device rd; | |
75 | std::vector<const onode_t*> onodes; | |
76 | std::vector<std::unique_ptr<char[]>> tracked_onodes; | |
77 | }; | |
78 | ||
79 | class KVPool { | |
80 | struct kv_conf_t { | |
81 | unsigned index2; | |
82 | unsigned index1; | |
83 | unsigned index0; | |
84 | size_t ns_size; | |
85 | size_t oid_size; | |
86 | const onode_t* p_value; | |
87 | ||
88 | ghobject_t get_ghobj() const { | |
89 | assert(index1 < 10); | |
90 | std::ostringstream os_ns; | |
91 | os_ns << "ns" << index1; | |
92 | unsigned current_size = (unsigned)os_ns.tellp(); | |
93 | assert(ns_size >= current_size); | |
94 | os_ns << std::string(ns_size - current_size, '_'); | |
95 | ||
96 | std::ostringstream os_oid; | |
97 | os_oid << "oid" << index1; | |
98 | current_size = (unsigned)os_oid.tellp(); | |
99 | assert(oid_size >= current_size); | |
100 | os_oid << std::string(oid_size - current_size, '_'); | |
101 | ||
102 | return ghobject_t(shard_id_t(index2), index2, index2, | |
103 | os_ns.str(), os_oid.str(), index0, index0); | |
104 | } | |
105 | }; | |
106 | using kv_vector_t = std::vector<kv_conf_t>; | |
107 | ||
108 | public: | |
109 | using kv_t = std::pair<ghobject_t, const onode_t*>; | |
110 | ||
111 | KVPool(const std::vector<size_t>& str_sizes, | |
112 | const std::vector<size_t>& onode_sizes, | |
113 | const std::pair<unsigned, unsigned>& range2, | |
114 | const std::pair<unsigned, unsigned>& range1, | |
115 | const std::pair<unsigned, unsigned>& range0) | |
116 | : str_sizes{str_sizes}, onodes{onode_sizes} { | |
117 | ceph_assert(range2.first < range2.second); | |
118 | ceph_assert(range2.second - 1 <= (unsigned)std::numeric_limits<shard_t>::max()); | |
119 | ceph_assert(range2.second - 1 <= std::numeric_limits<crush_hash_t>::max()); | |
120 | ceph_assert(range1.first < range1.second); | |
121 | ceph_assert(range1.second - 1 <= 9); | |
122 | ceph_assert(range0.first < range0.second); | |
123 | std::random_device rd; | |
124 | for (unsigned i = range2.first; i < range2.second; ++i) { | |
125 | for (unsigned j = range1.first; j < range1.second; ++j) { | |
126 | auto ns_size = (unsigned)str_sizes[rd() % str_sizes.size()]; | |
127 | auto oid_size = (unsigned)str_sizes[rd() % str_sizes.size()]; | |
128 | for (unsigned k = range0.first; k < range0.second; ++k) { | |
129 | kvs.emplace_back(kv_conf_t{i, j, k, ns_size, oid_size, &onodes.pick()}); | |
130 | } | |
131 | } | |
132 | } | |
133 | random_kvs = kvs; | |
134 | std::random_shuffle(random_kvs.begin(), random_kvs.end()); | |
135 | } | |
136 | ||
137 | class iterator_t { | |
138 | public: | |
139 | iterator_t() = default; | |
140 | iterator_t(const iterator_t&) = default; | |
141 | iterator_t(iterator_t&&) = default; | |
142 | iterator_t& operator=(const iterator_t&) = default; | |
143 | iterator_t& operator=(iterator_t&&) = default; | |
144 | ||
145 | kv_t get_kv() const { | |
146 | assert(!is_end()); | |
147 | auto& conf = (*p_kvs)[i]; | |
148 | return std::make_pair(conf.get_ghobj(), conf.p_value); | |
149 | } | |
150 | bool is_end() const { return !p_kvs || i >= p_kvs->size(); } | |
151 | size_t index() const { return i; } | |
152 | ||
153 | iterator_t& operator++() { | |
154 | assert(!is_end()); | |
155 | ++i; | |
156 | return *this; | |
157 | } | |
158 | ||
159 | iterator_t operator++(int) { | |
160 | iterator_t tmp = *this; | |
161 | ++*this; | |
162 | return tmp; | |
163 | } | |
164 | ||
165 | private: | |
166 | iterator_t(const kv_vector_t& kvs) : p_kvs{&kvs} {} | |
167 | ||
168 | const kv_vector_t* p_kvs = nullptr; | |
169 | size_t i = 0; | |
170 | friend class KVPool; | |
171 | }; | |
172 | ||
173 | iterator_t begin() const { | |
174 | return iterator_t(kvs); | |
175 | } | |
176 | ||
177 | iterator_t random_begin() const { | |
178 | return iterator_t(random_kvs); | |
179 | } | |
180 | ||
181 | size_t size() const { | |
182 | return kvs.size(); | |
183 | } | |
184 | ||
185 | private: | |
186 | std::vector<size_t> str_sizes; | |
187 | Onodes onodes; | |
188 | kv_vector_t kvs; | |
189 | kv_vector_t random_kvs; | |
190 | }; | |
191 | ||
192 | template <bool TRACK> | |
193 | class TreeBuilder { | |
194 | public: | |
195 | using ertr = Btree::btree_ertr; | |
196 | template <class ValueT=void> | |
197 | using future = ertr::future<ValueT>; | |
198 | ||
199 | TreeBuilder(KVPool& kvs, NodeExtentManagerURef&& nm) | |
200 | : kvs{kvs} { | |
201 | tree.emplace(std::move(nm)); | |
202 | } | |
203 | ||
204 | future<> bootstrap(Transaction& t) { | |
205 | std::ostringstream oss; | |
206 | #ifndef NDEBUG | |
207 | oss << "debug=on, "; | |
208 | #else | |
209 | oss << "debug=off, "; | |
210 | #endif | |
211 | #ifdef UNIT_TESTS_BUILT | |
212 | oss << "UNIT_TEST_BUILT=on, "; | |
213 | #else | |
214 | oss << "UNIT_TEST_BUILT=off, "; | |
215 | #endif | |
216 | if constexpr (TRACK) { | |
217 | oss << "track=on, "; | |
218 | } else { | |
219 | oss << "track=off, "; | |
220 | } | |
221 | oss << *tree; | |
222 | logger().warn("TreeBuilder: {}, bootstrapping ...", oss.str()); | |
223 | return tree->mkfs(t); | |
224 | } | |
225 | ||
226 | future<> insert(Transaction& t) { | |
227 | kv_iter = kvs.random_begin(); | |
228 | auto cursors = seastar::make_lw_shared<std::vector<Btree::Cursor>>(); | |
229 | logger().warn("start inserting {} kvs ...", kvs.size()); | |
230 | auto start_time = mono_clock::now(); | |
231 | return crimson::do_until([&t, this, cursors]() -> future<bool> { | |
232 | if (kv_iter.is_end()) { | |
233 | return ertr::make_ready_future<bool>(true); | |
234 | } | |
235 | auto [key, p_value] = kv_iter.get_kv(); | |
236 | logger().debug("[{}] {} -> {}", kv_iter.index(), key_hobj_t{key}, *p_value); | |
237 | return tree->insert(t, key, *p_value | |
238 | ).safe_then([&t, this, cursors](auto ret) { | |
239 | auto& [cursor, success] = ret; | |
240 | assert(success == true); | |
241 | if constexpr (TRACK) { | |
242 | cursors->emplace_back(cursor); | |
243 | } | |
244 | #ifndef NDEBUG | |
245 | auto [key, p_value] = kv_iter.get_kv(); | |
246 | Onodes::validate_cursor(cursor, key, *p_value); | |
247 | return tree->lower_bound(t, key).safe_then([this, cursor](auto cursor_) { | |
248 | auto [key, p_value] = kv_iter.get_kv(); | |
249 | ceph_assert(cursor_.get_ghobj() == key); | |
250 | ceph_assert(cursor_.value() == cursor.value()); | |
251 | ++kv_iter; | |
252 | return ertr::make_ready_future<bool>(false); | |
253 | }); | |
254 | #else | |
255 | ++kv_iter; | |
256 | return ertr::make_ready_future<bool>(false); | |
257 | #endif | |
258 | }); | |
259 | }).safe_then([&t, this, start_time, cursors] { | |
260 | std::chrono::duration<double> duration = mono_clock::now() - start_time; | |
261 | logger().warn("Insert done! {}s", duration.count()); | |
262 | if (!cursors->empty()) { | |
263 | logger().info("Verifing tracked cursors ..."); | |
264 | kv_iter = kvs.random_begin(); | |
265 | return seastar::do_with( | |
266 | cursors->begin(), [&t, this, cursors](auto& c_iter) { | |
267 | return crimson::do_until([&t, this, &c_iter, cursors]() -> future<bool> { | |
268 | if (kv_iter.is_end()) { | |
269 | logger().info("Verify done!"); | |
270 | return ertr::make_ready_future<bool>(true); | |
271 | } | |
272 | assert(c_iter != cursors->end()); | |
273 | auto [k, v] = kv_iter.get_kv(); | |
274 | // validate values in tree keep intact | |
275 | return tree->lower_bound(t, k).safe_then([this, &c_iter](auto cursor) { | |
276 | auto [k, v] = kv_iter.get_kv(); | |
277 | Onodes::validate_cursor(cursor, k, *v); | |
278 | // validate values in cursors keep intact | |
279 | Onodes::validate_cursor(*c_iter, k, *v); | |
280 | ++kv_iter; | |
281 | ++c_iter; | |
282 | return ertr::make_ready_future<bool>(false); | |
283 | }); | |
284 | }); | |
285 | }); | |
286 | } else { | |
287 | return ertr::now(); | |
288 | } | |
289 | }); | |
290 | } | |
291 | ||
292 | future<> get_stats(Transaction& t) { | |
293 | return tree->get_stats_slow(t | |
294 | ).safe_then([this](auto stats) { | |
295 | logger().warn("{}", stats); | |
296 | }); | |
297 | } | |
298 | ||
299 | void reload(NodeExtentManagerURef&& nm) { | |
300 | tree.emplace(std::move(nm)); | |
301 | } | |
302 | ||
303 | future<> validate(Transaction& t) { | |
304 | logger().info("Verifing insertion ..."); | |
305 | return seastar::do_with( | |
306 | kvs.begin(), [&t, this] (auto& kvs_iter) { | |
307 | return crimson::do_until([&t, this, &kvs_iter]() -> future<bool> { | |
308 | if (kvs_iter.is_end()) { | |
309 | logger().info("Verify done!"); | |
310 | return ertr::make_ready_future<bool>(true); | |
311 | } | |
312 | auto [k, v] = kvs_iter.get_kv(); | |
313 | return tree->lower_bound(t, k | |
314 | ).safe_then([&kvs_iter, k=k, v=v] (auto cursor) { | |
315 | Onodes::validate_cursor(cursor, k, *v); | |
316 | ++kvs_iter; | |
317 | return ertr::make_ready_future<bool>(false); | |
318 | }); | |
319 | }); | |
320 | }); | |
321 | } | |
322 | ||
323 | private: | |
324 | static seastar::logger& logger() { | |
325 | return crimson::get_logger(ceph_subsys_filestore); | |
326 | } | |
327 | ||
328 | KVPool& kvs; | |
329 | std::optional<Btree> tree; | |
330 | KVPool::iterator_t kv_iter; | |
331 | }; | |
332 | ||
333 | } |