]>
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 <sys/mman.h> | |
5 | #include <string.h> | |
6 | ||
7 | #include <memory> | |
8 | #include <string.h> | |
9 | ||
10 | #include "include/buffer.h" | |
11 | #include "include/byteorder.h" | |
12 | #include "crimson/os/seastore/transaction_manager.h" | |
13 | #include "crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node.h" | |
14 | #include "crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h" | |
15 | ||
16 | namespace { | |
17 | seastar::logger& logger() { | |
18 | return crimson::get_logger(ceph_subsys_filestore); | |
19 | } | |
20 | } | |
21 | ||
22 | namespace crimson::os::seastore::extentmap_manager { | |
23 | ||
24 | std::ostream &ExtMapInnerNode::print_detail_l(std::ostream &out) const | |
25 | { | |
26 | return out << ", size=" << get_size() | |
27 | << ", depth=" << get_meta().depth; | |
28 | } | |
29 | ||
30 | ExtMapInnerNode::find_lextent_ret | |
31 | ExtMapInnerNode::find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) | |
32 | { | |
33 | auto [begin, end] = bound(lo, lo + len); | |
34 | auto result_up = std::make_unique<extent_map_list_t>(); | |
35 | auto &result = *result_up; | |
36 | return crimson::do_for_each( | |
37 | std::move(begin), | |
38 | std::move(end), | |
39 | [this, ec, &result, lo, len](const auto &val) mutable { | |
40 | return extmap_load_extent(ec, val.get_val(), get_meta().depth - 1).safe_then( | |
41 | [ec, &result, lo, len](auto extent) mutable { | |
42 | return extent->find_lextent(ec, lo, len).safe_then( | |
43 | [&result](auto item_list) mutable { | |
44 | result.splice(result.end(), item_list, | |
45 | item_list.begin(), item_list.end()); | |
46 | }); | |
47 | }); | |
48 | }).safe_then([result=std::move(result_up)] { | |
49 | return find_lextent_ret( | |
50 | find_lextent_ertr::ready_future_marker{}, | |
51 | std::move(*result)); | |
52 | }); | |
53 | } | |
54 | ||
55 | ExtMapInnerNode::insert_ret | |
56 | ExtMapInnerNode::insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) | |
57 | { | |
58 | auto insertion_pt = get_containing_child(lo); | |
59 | assert(insertion_pt != end()); | |
60 | return extmap_load_extent(ec, insertion_pt->get_val(), get_meta().depth - 1).safe_then( | |
61 | [this, ec, insertion_pt, lo, val=std::move(val)](auto extent) mutable { | |
62 | return extent->at_max_capacity() ? | |
63 | split_entry(ec, lo, insertion_pt, extent) : | |
64 | insert_ertr::make_ready_future<ExtMapNodeRef>(std::move(extent)); | |
65 | }).safe_then([ec, lo, val=std::move(val)](ExtMapNodeRef extent) mutable { | |
66 | return extent->insert(ec, lo, val); | |
67 | }); | |
68 | } | |
69 | ||
70 | ExtMapInnerNode::rm_lextent_ret | |
71 | ExtMapInnerNode::rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) | |
72 | { | |
73 | auto rm_pt = get_containing_child(lo); | |
74 | return extmap_load_extent(ec, rm_pt->get_val(), get_meta().depth - 1).safe_then( | |
75 | [this, ec, rm_pt, lo, val=std::move(val)](auto extent) mutable { | |
76 | if (extent->at_min_capacity() && get_node_size() > 1) { | |
77 | return merge_entry(ec, lo, rm_pt, extent); | |
78 | } else { | |
79 | return merge_entry_ertr::make_ready_future<ExtMapNodeRef>(std::move(extent)); | |
80 | } | |
81 | }).safe_then([ec, lo, val](ExtMapNodeRef extent) mutable { | |
82 | return extent->rm_lextent(ec, lo, val); | |
83 | }); | |
84 | } | |
85 | ||
86 | ExtMapInnerNode::split_children_ret | |
87 | ExtMapInnerNode::make_split_children(ext_context_t ec) | |
88 | { | |
89 | logger().debug("{}: {}", "ExtMapInnerNode", __func__); | |
90 | return extmap_alloc_2extents<ExtMapInnerNode>(ec, EXTMAP_BLOCK_SIZE) | |
91 | .safe_then([this] (auto &&ext_pair) { | |
92 | auto [left, right] = ext_pair; | |
93 | return split_children_ret( | |
94 | split_children_ertr::ready_future_marker{}, | |
95 | std::make_tuple(left, right, split_into(*left, *right))); | |
96 | }); | |
97 | } | |
98 | ||
99 | ExtMapInnerNode::full_merge_ret | |
100 | ExtMapInnerNode::make_full_merge(ext_context_t ec, ExtMapNodeRef right) | |
101 | { | |
102 | logger().debug("{}: {}", "ExtMapInnerNode", __func__); | |
103 | return extmap_alloc_extent<ExtMapInnerNode>(ec, EXTMAP_BLOCK_SIZE) | |
104 | .safe_then([this, right] (auto &&replacement) { | |
105 | replacement->merge_from(*this, *right->cast<ExtMapInnerNode>()); | |
106 | return full_merge_ret( | |
107 | full_merge_ertr::ready_future_marker{}, | |
108 | std::move(replacement)); | |
109 | }); | |
110 | } | |
111 | ||
112 | ExtMapInnerNode::make_balanced_ret | |
113 | ExtMapInnerNode::make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) | |
114 | { | |
115 | logger().debug("{}: {}", "ExtMapInnerNode", __func__); | |
116 | ceph_assert(_right->get_type() == type); | |
117 | return extmap_alloc_2extents<ExtMapInnerNode>(ec, EXTMAP_BLOCK_SIZE) | |
118 | .safe_then([this, _right, prefer_left] (auto &&replacement_pair){ | |
119 | auto [replacement_left, replacement_right] = replacement_pair; | |
120 | auto &right = *_right->cast<ExtMapInnerNode>(); | |
121 | return make_balanced_ret( | |
122 | make_balanced_ertr::ready_future_marker{}, | |
123 | std::make_tuple(replacement_left, replacement_right, | |
124 | balance_into_new_nodes(*this, right, prefer_left, | |
125 | *replacement_left, *replacement_right))); | |
126 | }); | |
127 | } | |
128 | ||
129 | ExtMapInnerNode::split_entry_ret | |
130 | ExtMapInnerNode::split_entry(ext_context_t ec, objaddr_t lo, | |
131 | internal_iterator_t iter, ExtMapNodeRef entry) | |
132 | { | |
133 | logger().debug("{}: {}", "ExtMapInnerNode", __func__); | |
134 | if (!is_pending()) { | |
135 | auto mut = ec.tm.get_mutable_extent(ec.t, this)->cast<ExtMapInnerNode>(); | |
136 | auto mut_iter = mut->iter_idx(iter->get_offset()); | |
137 | return mut->split_entry(ec, lo, mut_iter, entry); | |
138 | } | |
139 | ceph_assert(!at_max_capacity()); | |
140 | return entry->make_split_children(ec) | |
141 | .safe_then([this, ec, lo, iter, entry] (auto tuple){ | |
142 | auto [left, right, pivot] = tuple; | |
143 | journal_update(iter, left->get_laddr(), maybe_get_delta_buffer()); | |
144 | journal_insert(iter + 1, pivot, right->get_laddr(), maybe_get_delta_buffer()); | |
145 | logger().debug( | |
146 | "ExtMapInnerNode::split_entry *this {} entry {} into left {} right {}", | |
147 | *this, *entry, *left, *right); | |
148 | //retire extent | |
149 | return ec.tm.dec_ref(ec.t, entry->get_laddr()) | |
150 | .safe_then([lo, left = left, right = right, pivot = pivot] (auto ret) { | |
151 | return split_entry_ertr::make_ready_future<ExtMapNodeRef>( | |
152 | pivot > lo ? left : right); | |
153 | }); | |
154 | }); | |
155 | } | |
156 | ||
157 | ExtMapInnerNode::merge_entry_ret | |
158 | ExtMapInnerNode::merge_entry(ext_context_t ec, objaddr_t lo, | |
159 | internal_iterator_t iter, ExtMapNodeRef entry) | |
160 | { | |
161 | if (!is_pending()) { | |
162 | auto mut = ec.tm.get_mutable_extent(ec.t, this)->cast<ExtMapInnerNode>(); | |
163 | auto mut_iter = mut->iter_idx(iter->get_offset()); | |
164 | return mut->merge_entry(ec, lo, mut_iter, entry); | |
165 | } | |
166 | logger().debug("ExtMapInnerNode: merge_entry: {}, {}", *this, *entry); | |
167 | auto is_left = (iter + 1) == end(); | |
168 | auto donor_iter = is_left ? iter - 1 : iter + 1; | |
169 | return extmap_load_extent(ec, donor_iter->get_val(), get_meta().depth - 1) | |
170 | .safe_then([this, ec, lo, iter, entry, donor_iter, is_left] | |
171 | (auto &&donor) mutable { | |
172 | auto [l, r] = is_left ? | |
173 | std::make_pair(donor, entry) : std::make_pair(entry, donor); | |
174 | auto [liter, riter] = is_left ? | |
175 | std::make_pair(donor_iter, iter) : std::make_pair(iter, donor_iter); | |
176 | if (donor->at_min_capacity()) { | |
177 | return l->make_full_merge(ec, r) | |
178 | .safe_then([this, ec, entry, l = l, r = r, liter = liter, riter = riter] | |
179 | (auto &&replacement){ | |
180 | journal_update(liter, replacement->get_laddr(), maybe_get_delta_buffer()); | |
181 | journal_remove(riter, maybe_get_delta_buffer()); | |
182 | //retire extent | |
183 | std::list<laddr_t> dec_laddrs; | |
184 | dec_laddrs.push_back(l->get_laddr()); | |
185 | dec_laddrs.push_back(r->get_laddr()); | |
186 | return extmap_retire_node(ec, dec_laddrs) | |
187 | .safe_then([replacement] (auto &&ret) { | |
188 | return merge_entry_ertr::make_ready_future<ExtMapNodeRef>(replacement); | |
189 | }); | |
190 | }); | |
191 | } else { | |
192 | logger().debug("ExtMapInnerNode::merge_entry balanced l {} r {}", | |
193 | *l, *r); | |
194 | return l->make_balanced(ec, r, !is_left) | |
195 | .safe_then([this, ec, lo, entry, l = l, r = r, liter = liter, riter = riter] | |
196 | (auto tuple) { | |
197 | auto [replacement_l, replacement_r, pivot] = tuple; | |
198 | journal_update(liter, replacement_l->get_laddr(), maybe_get_delta_buffer()); | |
199 | journal_replace(riter, pivot, replacement_r->get_laddr(), | |
200 | maybe_get_delta_buffer()); | |
201 | // retire extent | |
202 | std::list<laddr_t> dec_laddrs; | |
203 | dec_laddrs.push_back(l->get_laddr()); | |
204 | dec_laddrs.push_back(r->get_laddr()); | |
205 | return extmap_retire_node(ec, dec_laddrs) | |
206 | .safe_then([lo, pivot = pivot, replacement_l = replacement_l, replacement_r = replacement_r] | |
207 | (auto &&ret) { | |
208 | return merge_entry_ertr::make_ready_future<ExtMapNodeRef>( | |
209 | lo >= pivot ? replacement_r : replacement_l); | |
210 | }); | |
211 | }); | |
212 | } | |
213 | }); | |
214 | } | |
215 | ||
216 | ||
217 | ExtMapInnerNode::internal_iterator_t | |
218 | ExtMapInnerNode::get_containing_child(objaddr_t lo) | |
219 | { | |
220 | // TODO: binary search | |
221 | for (auto i = begin(); i != end(); ++i) { | |
222 | if (i.contains(lo)) | |
223 | return i; | |
224 | } | |
225 | ceph_assert(0 == "invalid"); | |
226 | return end(); | |
227 | } | |
228 | ||
229 | std::ostream &ExtMapLeafNode::print_detail_l(std::ostream &out) const | |
230 | { | |
231 | return out << ", size=" << get_size() | |
232 | << ", depth=" << get_meta().depth; | |
233 | } | |
234 | ||
235 | ExtMapLeafNode::find_lextent_ret | |
236 | ExtMapLeafNode::find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) | |
237 | { | |
238 | logger().debug( | |
239 | "ExtMapLeafNode::find_lextent {}~{}", lo, len); | |
240 | auto ret = extent_map_list_t(); | |
241 | auto [from, to] = get_leaf_entries(lo, len); | |
242 | if (from == to && to != end()) | |
243 | ++to; | |
244 | for (; from != to; ++from) { | |
245 | auto val = (*from).get_val(); | |
246 | ret.emplace_back( | |
247 | extent_mapping_t( | |
248 | (*from).get_key(), | |
249 | val.laddr, | |
250 | val.length)); | |
251 | logger().debug("ExtMapLeafNode::find_lextent find {}~{}", lo, val.laddr); | |
252 | } | |
253 | return find_lextent_ertr::make_ready_future<extent_map_list_t>( | |
254 | std::move(ret)); | |
255 | } | |
256 | ||
257 | ExtMapLeafNode::insert_ret | |
258 | ExtMapLeafNode::insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) | |
259 | { | |
260 | ceph_assert(!at_max_capacity()); | |
261 | if (!is_pending()) { | |
262 | auto mut = ec.tm.get_mutable_extent(ec.t, this)->cast<ExtMapLeafNode>(); | |
263 | return mut->insert(ec, lo, val); | |
264 | } | |
265 | auto insert_pt = lower_bound(lo); | |
266 | journal_insert(insert_pt, lo, val, maybe_get_delta_buffer()); | |
267 | ||
268 | logger().debug( | |
269 | "ExtMapLeafNode::insert: inserted {}->{} {}", | |
270 | insert_pt.get_key(), | |
271 | insert_pt.get_val().laddr, | |
272 | insert_pt.get_val().length); | |
273 | return insert_ertr::make_ready_future<extent_mapping_t>( | |
274 | extent_mapping_t(lo, val.laddr, val.length)); | |
275 | } | |
276 | ||
277 | ExtMapLeafNode::rm_lextent_ret | |
278 | ExtMapLeafNode::rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) | |
279 | { | |
280 | if (!is_pending()) { | |
281 | auto mut = ec.tm.get_mutable_extent(ec.t, this)->cast<ExtMapLeafNode>(); | |
282 | return mut->rm_lextent(ec, lo, val); | |
283 | } | |
284 | ||
285 | auto [rm_pt, rm_end] = get_leaf_entries(lo, val.length); | |
286 | if (lo == rm_pt->get_key() && val.laddr == rm_pt->get_val().laddr | |
287 | && val.length == rm_pt->get_val().length) { | |
288 | journal_remove(rm_pt, maybe_get_delta_buffer()); | |
289 | logger().debug( | |
290 | "ExtMapLeafNode::rm_lextent: removed {}->{} {}", | |
291 | rm_pt.get_key(), | |
292 | rm_pt.get_val().laddr, | |
293 | rm_pt.get_val().length); | |
294 | return rm_lextent_ertr::make_ready_future<bool>(true); | |
295 | } else { | |
296 | return rm_lextent_ertr::make_ready_future<bool>(false); | |
297 | } | |
298 | } | |
299 | ||
300 | ExtMapLeafNode::split_children_ret | |
301 | ExtMapLeafNode::make_split_children(ext_context_t ec) | |
302 | { | |
303 | logger().debug("{}: {}", "ExtMapLeafNode", __func__); | |
304 | return extmap_alloc_2extents<ExtMapLeafNode>(ec, EXTMAP_BLOCK_SIZE) | |
305 | .safe_then([this] (auto &&ext_pair) { | |
306 | auto [left, right] = ext_pair; | |
307 | return split_children_ret( | |
308 | split_children_ertr::ready_future_marker{}, | |
309 | std::make_tuple(left, right, split_into(*left, *right))); | |
310 | }); | |
311 | } | |
312 | ||
313 | ExtMapLeafNode::full_merge_ret | |
314 | ExtMapLeafNode::make_full_merge(ext_context_t ec, ExtMapNodeRef right) | |
315 | { | |
316 | logger().debug("{}: {}", "ExtMapLeafNode", __func__); | |
317 | return extmap_alloc_extent<ExtMapLeafNode>(ec, EXTMAP_BLOCK_SIZE) | |
318 | .safe_then([this, right] (auto &&replacement) { | |
319 | replacement->merge_from(*this, *right->cast<ExtMapLeafNode>()); | |
320 | return full_merge_ret( | |
321 | full_merge_ertr::ready_future_marker{}, | |
322 | std::move(replacement)); | |
323 | }); | |
324 | } | |
325 | ExtMapLeafNode::make_balanced_ret | |
326 | ExtMapLeafNode::make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) | |
327 | { | |
328 | logger().debug("{}: {}", "ExtMapLeafNode", __func__); | |
329 | ceph_assert(_right->get_type() == type); | |
330 | return extmap_alloc_2extents<ExtMapLeafNode>(ec, EXTMAP_BLOCK_SIZE) | |
331 | .safe_then([this, _right, prefer_left] (auto &&replacement_pair) { | |
332 | auto [replacement_left, replacement_right] = replacement_pair; | |
333 | auto &right = *_right->cast<ExtMapLeafNode>(); | |
334 | return make_balanced_ret( | |
335 | make_balanced_ertr::ready_future_marker{}, | |
336 | std::make_tuple( | |
337 | replacement_left, replacement_right, | |
338 | balance_into_new_nodes( | |
339 | *this, right, prefer_left, | |
340 | *replacement_left, *replacement_right))); | |
341 | }); | |
342 | } | |
343 | ||
344 | ||
345 | std::pair<ExtMapLeafNode::internal_iterator_t, ExtMapLeafNode::internal_iterator_t> | |
346 | ExtMapLeafNode::get_leaf_entries(objaddr_t addr, extent_len_t len) | |
347 | { | |
348 | return bound(addr, addr + len); | |
349 | } | |
350 | ||
351 | ||
352 | TransactionManager::read_extent_ertr::future<ExtMapNodeRef> | |
353 | extmap_load_extent(ext_context_t ec, laddr_t laddr, depth_t depth) | |
354 | { | |
355 | ceph_assert(depth > 0); | |
356 | if (depth > 1) { | |
357 | return ec.tm.read_extents<ExtMapInnerNode>(ec.t, laddr, EXTMAP_BLOCK_SIZE).safe_then( | |
358 | [](auto&& extents) { | |
359 | assert(extents.size() == 1); | |
360 | [[maybe_unused]] auto [laddr, e] = extents.front(); | |
361 | return TransactionManager::read_extent_ertr::make_ready_future<ExtMapNodeRef>(std::move(e)); | |
362 | }); | |
363 | } else { | |
364 | return ec.tm.read_extents<ExtMapLeafNode>(ec.t, laddr, EXTMAP_BLOCK_SIZE).safe_then( | |
365 | [](auto&& extents) { | |
366 | assert(extents.size() == 1); | |
367 | [[maybe_unused]] auto [laddr, e] = extents.front(); | |
368 | return TransactionManager::read_extent_ertr::make_ready_future<ExtMapNodeRef>(std::move(e)); | |
369 | }); | |
370 | } | |
371 | } | |
372 | ||
373 | } |