1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 #include "crimson/common/log.h"
5 #include "crimson/os/seastore/logging.h"
7 #include "crimson/os/seastore/lba_manager/btree/lba_btree.h"
9 SET_SUBSYS(seastore_lba
);
11 namespace crimson::os::seastore::lba_manager::btree
{
13 LBABtree::mkfs_ret
LBABtree::mkfs(op_context_t c
)
15 auto root_leaf
= c
.cache
.alloc_new_extent
<LBALeafNode
>(
18 root_leaf
->set_size(0);
19 lba_node_meta_t meta
{0, L_ADDR_MAX
, 1};
20 root_leaf
->set_meta(meta
);
21 root_leaf
->pin
.set_range(meta
);
22 c
.trans
.get_lba_tree_stats().depth
= 1u;
23 return lba_root_t
{root_leaf
->get_paddr(), 1u};
26 LBABtree::iterator::handle_boundary_ret
LBABtree::iterator::handle_boundary(
28 mapped_space_visitor_t
*visitor
)
30 assert(at_boundary());
31 depth_t depth_with_space
= 2;
32 for (; depth_with_space
<= get_depth(); ++depth_with_space
) {
33 if ((get_internal(depth_with_space
).pos
+ 1) <
34 get_internal(depth_with_space
).node
->get_size()) {
39 if (depth_with_space
<= get_depth()) {
40 return seastar::do_with(
41 [](const LBAInternalNode
&internal
) { return internal
.begin(); },
42 [](const LBALeafNode
&leaf
) { return leaf
.begin(); },
43 [this, c
, depth_with_space
, visitor
](auto &li
, auto &ll
) {
44 for (depth_t depth
= 2; depth
< depth_with_space
; ++depth
) {
45 get_internal(depth
).reset();
48 get_internal(depth_with_space
).pos
++;
49 // note, cannot result in at_boundary() by construction
50 return lookup_depth_range(
51 c
, *this, depth_with_space
- 1, 0, li
, ll
, visitor
56 return seastar::now();
60 LBABtree::iterator_fut
LBABtree::iterator::next(
62 mapped_space_visitor_t
*visitor
) const
69 if (ret
.at_boundary()) {
70 return seastar::do_with(
72 [c
, visitor
](auto &ret
) mutable {
73 return ret
.handle_boundary(
76 return std::move(ret
);
81 interruptible::ready_future_marker
{},
87 LBABtree::iterator_fut
LBABtree::iterator::prev(op_context_t c
) const
94 if (ret
.leaf
.pos
> 0) {
97 interruptible::ready_future_marker
{},
101 depth_t depth_with_space
= 2;
102 for (; depth_with_space
<= get_depth(); ++depth_with_space
) {
103 if (ret
.get_internal(depth_with_space
).pos
> 0) {
108 assert(depth_with_space
<= ret
.get_depth()); // must not be begin()
109 return seastar::do_with(
111 [](const LBAInternalNode
&internal
) { return --internal
.end(); },
112 [](const LBALeafNode
&leaf
) { return --leaf
.end(); },
113 [c
, depth_with_space
](auto &ret
, auto &li
, auto &ll
) {
114 for (depth_t depth
= 2; depth
< depth_with_space
; ++depth
) {
115 ret
.get_internal(depth
).reset();
118 ret
.get_internal(depth_with_space
).pos
--;
119 // note, cannot result in at_boundary() by construction
120 return lookup_depth_range(
121 c
, ret
, depth_with_space
- 1, 0, li
, ll
, nullptr
123 assert(!ret
.at_boundary());
124 return std::move(ret
);
129 LBABtree::iterator_fut
LBABtree::lower_bound(
132 mapped_space_visitor_t
*visitor
) const
134 LOG_PREFIX(LBATree::lower_bound
);
137 [addr
](const LBAInternalNode
&internal
) {
138 assert(internal
.get_size() > 0);
139 auto iter
= internal
.upper_bound(addr
);
140 assert(iter
!= internal
.begin());
144 [FNAME
, c
, addr
](const LBALeafNode
&leaf
) {
145 auto ret
= leaf
.lower_bound(addr
);
147 "leaf addr {}, got ret offset {}, size {}, end {}",
156 ).si_then([FNAME
, c
](auto &&ret
) {
162 return std::move(ret
);
166 LBABtree::insert_ret
LBABtree::insert(
172 LOG_PREFIX(LBATree::insert
);
174 "inserting laddr {} at iter {}",
177 iter
.is_end() ? L_ADDR_MAX
: iter
.get_key());
178 return seastar::do_with(
180 [this, c
, laddr
, val
](auto &ret
) {
181 return find_insertion(
183 ).si_then([this, c
, laddr
, val
, &ret
] {
184 if (!ret
.at_boundary() && ret
.get_key() == laddr
) {
186 interruptible::ready_future_marker
{},
187 std::make_pair(ret
, false));
189 ++(c
.trans
.get_lba_tree_stats().num_inserts
);
192 ).si_then([c
, laddr
, val
, &ret
] {
193 if (!ret
.leaf
.node
->is_pending()) {
194 CachedExtentRef mut
= c
.cache
.duplicate_for_write(
195 c
.trans
, ret
.leaf
.node
197 ret
.leaf
.node
= mut
->cast
<LBALeafNode
>();
199 auto iter
= LBALeafNode::const_iterator(
200 ret
.leaf
.node
.get(), ret
.leaf
.pos
);
201 assert(iter
== ret
.leaf
.node
->lower_bound(laddr
));
202 assert(iter
== ret
.leaf
.node
->end() || iter
->get_key() > laddr
);
203 assert(laddr
>= ret
.leaf
.node
->get_meta().begin
&&
204 laddr
< ret
.leaf
.node
->get_meta().end
);
205 ret
.leaf
.node
->insert(iter
, laddr
, val
);
207 interruptible::ready_future_marker
{},
208 std::make_pair(ret
, true));
215 LBABtree::update_ret
LBABtree::update(
220 LOG_PREFIX(LBATree::update
);
222 "update element at {}",
224 iter
.is_end() ? L_ADDR_MAX
: iter
.get_key());
225 if (!iter
.leaf
.node
->is_pending()) {
226 CachedExtentRef mut
= c
.cache
.duplicate_for_write(
227 c
.trans
, iter
.leaf
.node
229 iter
.leaf
.node
= mut
->cast
<LBALeafNode
>();
231 iter
.leaf
.node
->update(
232 iter
.leaf
.node
->iter_idx(iter
.leaf
.pos
),
235 interruptible::ready_future_marker
{},
239 LBABtree::remove_ret
LBABtree::remove(
243 LOG_PREFIX(LBATree::remove
);
245 "remove element at {}",
247 iter
.is_end() ? L_ADDR_MAX
: iter
.get_key());
248 assert(!iter
.is_end());
249 ++(c
.trans
.get_lba_tree_stats().num_erases
);
250 return seastar::do_with(
252 [this, c
](auto &ret
) {
253 if (!ret
.leaf
.node
->is_pending()) {
254 CachedExtentRef mut
= c
.cache
.duplicate_for_write(
255 c
.trans
, ret
.leaf
.node
257 ret
.leaf
.node
= mut
->cast
<LBALeafNode
>();
259 ret
.leaf
.node
->remove(
260 ret
.leaf
.node
->iter_idx(ret
.leaf
.pos
));
268 LBABtree::init_cached_extent_ret
LBABtree::init_cached_extent(
272 LOG_PREFIX(LBATree::init_cached_extent
);
273 DEBUGT("extent {}", c
.trans
, *e
);
274 if (e
->is_logical()) {
275 auto logn
= e
->cast
<LogicalCachedExtent
>();
279 ).si_then([FNAME
, e
, c
, logn
](auto iter
) {
280 if (!iter
.is_end() &&
281 iter
.get_key() == logn
->get_laddr() &&
282 iter
.get_val().paddr
== logn
->get_paddr()) {
283 logn
->set_pin(iter
.get_pin());
284 ceph_assert(iter
.get_val().len
== e
->get_length());
287 static_cast<BtreeLBAPin
&>(logn
->get_pin()).pin
);
289 DEBUGT("logical extent {} live, initialized", c
.trans
, *logn
);
292 DEBUGT("logical extent {} not live, dropping", c
.trans
, *logn
);
293 c
.cache
.drop_from_cache(logn
);
294 return CachedExtentRef();
297 } else if (e
->get_type() == extent_types_t::LADDR_INTERNAL
) {
298 auto eint
= e
->cast
<LBAInternalNode
>();
300 c
, eint
->get_node_meta().begin
301 ).si_then([FNAME
, e
, c
, eint
](auto iter
) {
302 // Note, this check is valid even if iter.is_end()
303 depth_t cand_depth
= eint
->get_node_meta().depth
;
304 if (cand_depth
<= iter
.get_depth() &&
305 &*iter
.get_internal(cand_depth
).node
== &*eint
) {
306 DEBUGT("extent {} is live", c
.trans
, *eint
);
309 DEBUGT("extent {} is not live", c
.trans
, *eint
);
310 c
.cache
.drop_from_cache(eint
);
311 return CachedExtentRef();
314 } else if (e
->get_type() == extent_types_t::LADDR_LEAF
) {
315 auto eleaf
= e
->cast
<LBALeafNode
>();
317 c
, eleaf
->get_node_meta().begin
318 ).si_then([FNAME
, c
, e
, eleaf
](auto iter
) {
319 // Note, this check is valid even if iter.is_end()
320 if (iter
.leaf
.node
== &*eleaf
) {
321 DEBUGT("extent {} is live", c
.trans
, *eleaf
);
324 DEBUGT("extent {} is not live", c
.trans
, *eleaf
);
325 c
.cache
.drop_from_cache(eleaf
);
326 return CachedExtentRef();
331 "found other extent {} type {}",
335 return init_cached_extent_ret(
336 interruptible::ready_future_marker
{},
341 LBABtree::get_internal_if_live_ret
342 LBABtree::get_internal_if_live(
348 LOG_PREFIX(BtreeLBAManager::get_leaf_if_live
);
351 ).si_then([FNAME
, c
, addr
, laddr
, len
](auto iter
) {
352 for (depth_t d
= 2; d
<= iter
.get_depth(); ++d
) {
353 CachedExtent
&node
= *iter
.get_internal(d
).node
;
354 auto internal_node
= node
.cast
<LBAInternalNode
>();
355 if (internal_node
->get_paddr() == addr
) {
357 "extent laddr {} addr {}~{} found: {}",
363 assert(internal_node
->get_node_meta().begin
== laddr
);
364 return CachedExtentRef(internal_node
);
368 "extent laddr {} addr {}~{} is not live, no matching internal node",
373 return CachedExtentRef();
377 LBABtree::get_leaf_if_live_ret
378 LBABtree::get_leaf_if_live(
384 LOG_PREFIX(BtreeLBAManager::get_leaf_if_live
);
387 ).si_then([FNAME
, c
, addr
, laddr
, len
](auto iter
) {
388 if (iter
.leaf
.node
->get_paddr() == addr
) {
390 "extent laddr {} addr {}~{} found: {}",
396 return CachedExtentRef(iter
.leaf
.node
);
399 "extent laddr {} addr {}~{} is not live, does not match node {}",
405 return CachedExtentRef();
411 LBABtree::rewrite_lba_extent_ret
LBABtree::rewrite_lba_extent(
415 LOG_PREFIX(LBABtree::rewrite_lba_extent
);
416 assert(e
->get_type() == extent_types_t::LADDR_INTERNAL
||
417 e
->get_type() == extent_types_t::LADDR_LEAF
);
419 auto do_rewrite
= [&](auto &lba_extent
) {
420 auto nlba_extent
= c
.cache
.alloc_new_extent
<
421 std::remove_reference_t
<decltype(lba_extent
)>
424 lba_extent
.get_length());
425 lba_extent
.get_bptr().copy_out(
427 lba_extent
.get_length(),
428 nlba_extent
->get_bptr().c_str());
429 nlba_extent
->pin
.set_range(nlba_extent
->get_node_meta());
431 /* This is a bit underhanded. Any relative addrs here must necessarily
432 * be record relative as we are rewriting a dirty extent. Thus, we
433 * are using resolve_relative_addrs with a (likely negative) block
434 * relative offset to correct them to block-relative offsets adjusted
435 * for our new transaction location.
437 * Upon commit, these now block relative addresses will be interpretted
438 * against the real final address.
440 nlba_extent
->resolve_relative_addrs(
441 make_record_relative_paddr(0) - nlba_extent
->get_paddr());
444 "rewriting {} into {}",
449 return update_internal_mapping(
451 nlba_extent
->get_node_meta().depth
,
452 nlba_extent
->get_node_meta().begin
,
454 nlba_extent
->get_paddr()
456 c
.cache
.retire_extent(c
.trans
, e
);
460 CachedExtentRef nlba_extent
;
461 if (e
->get_type() == extent_types_t::LADDR_INTERNAL
) {
462 auto lint
= e
->cast
<LBAInternalNode
>();
463 return do_rewrite(*lint
);
465 assert(e
->get_type() == extent_types_t::LADDR_LEAF
);
466 auto lleaf
= e
->cast
<LBALeafNode
>();
467 return do_rewrite(*lleaf
);
471 LBABtree::get_internal_node_ret
LBABtree::get_internal_node(
478 LOG_PREFIX(LBATree::get_internal_node
);
480 "reading internal at offset {}, depth {}, begin {}, end {}",
487 auto init_internal
= [c
, depth
, begin
, end
](LBAInternalNode
&node
) {
488 assert(!node
.is_pending());
489 assert(!node
.pin
.is_linked());
490 node
.pin
.set_range(lba_node_meta_t
{begin
, end
, depth
});
492 c
.pins
->add_pin(node
.pin
);
495 return c
.cache
.get_extent
<LBAInternalNode
>(
500 ).si_then([FNAME
, c
, offset
, init_internal
, depth
, begin
, end
](
501 LBAInternalNodeRef ret
) {
503 "read internal at offset {} {}",
507 // This can only happen during init_cached_extent
508 if (c
.pins
&& !ret
->is_pending() && !ret
->pin
.is_linked()) {
509 assert(ret
->is_dirty());
512 auto meta
= ret
->get_meta();
513 if (ret
->get_size()) {
514 ceph_assert(meta
.begin
<= ret
->begin()->get_key());
515 ceph_assert(meta
.end
> (ret
->end() - 1)->get_key());
517 ceph_assert(depth
== meta
.depth
);
518 ceph_assert(begin
== meta
.begin
);
519 ceph_assert(end
== meta
.end
);
520 return get_internal_node_ret(
521 interruptible::ready_future_marker
{},
526 LBABtree::get_leaf_node_ret
LBABtree::get_leaf_node(
532 LOG_PREFIX(LBATree::get_leaf_node
);
534 "reading leaf at offset {}, begin {}, end {}",
539 auto init_leaf
= [c
, begin
, end
](LBALeafNode
&node
) {
540 assert(!node
.is_pending());
541 assert(!node
.pin
.is_linked());
542 node
.pin
.set_range(lba_node_meta_t
{begin
, end
, 1});
544 c
.pins
->add_pin(node
.pin
);
547 return c
.cache
.get_extent
<LBALeafNode
>(
552 ).si_then([FNAME
, c
, offset
, init_leaf
, begin
, end
](LBALeafNodeRef ret
) {
554 "read leaf at offset {} {}",
558 // This can only happen during init_cached_extent
559 if (c
.pins
&& !ret
->is_pending() && !ret
->pin
.is_linked()) {
560 assert(ret
->is_dirty());
563 auto meta
= ret
->get_meta();
564 if (ret
->get_size()) {
565 ceph_assert(meta
.begin
<= ret
->begin()->get_key());
566 ceph_assert(meta
.end
> (ret
->end() - 1)->get_key());
568 ceph_assert(1 == meta
.depth
);
569 ceph_assert(begin
== meta
.begin
);
570 ceph_assert(end
== meta
.end
);
571 return get_leaf_node_ret(
572 interruptible::ready_future_marker
{},
577 LBABtree::find_insertion_ret
LBABtree::find_insertion(
582 assert(iter
.is_end() || iter
.get_key() >= laddr
);
583 if (!iter
.is_end() && iter
.get_key() == laddr
) {
584 return seastar::now();
585 } else if (iter
.leaf
.node
->get_node_meta().begin
<= laddr
) {
588 if (p
.leaf
.pos
> 0) {
590 assert(p
.get_key() < laddr
);
593 return seastar::now();
595 assert(iter
.leaf
.pos
== 0);
598 ).si_then([laddr
, &iter
](auto p
) {
599 assert(p
.leaf
.node
->get_node_meta().begin
<= laddr
);
600 assert(p
.get_key() < laddr
);
601 // Note, this is specifically allowed to violate the iterator
602 // invariant that pos is a valid index for the node in the event
603 // that the insertion point is at the end of a node.
605 assert(p
.at_boundary());
607 return seastar::now();
612 LBABtree::handle_split_ret
LBABtree::handle_split(
616 LOG_PREFIX(LBATree::handle_split
);
618 depth_t split_from
= iter
.check_split();
620 DEBUGT("split_from {}, depth {}", c
.trans
, split_from
, iter
.get_depth());
622 if (split_from
== iter
.get_depth()) {
623 auto nroot
= c
.cache
.alloc_new_extent
<LBAInternalNode
>(
624 c
.trans
, LBA_BLOCK_SIZE
);
625 lba_node_meta_t meta
{0, L_ADDR_MAX
, iter
.get_depth() + 1};
626 nroot
->set_meta(meta
);
627 nroot
->pin
.set_range(meta
);
628 nroot
->journal_insert(
633 iter
.internal
.push_back({nroot
, 0});
635 root
.set_location(nroot
->get_paddr());
636 root
.set_depth(iter
.get_depth());
637 c
.trans
.get_lba_tree_stats().depth
= iter
.get_depth();
641 /* pos may be either node_position_t<LBALeafNode> or
642 * node_position_t<LBAInternalNode> */
643 auto split_level
= [&](auto &parent_pos
, auto &pos
) {
644 LOG_PREFIX(LBATree::handle_split
);
645 auto [left
, right
, pivot
] = pos
.node
->make_split_children(c
);
647 auto parent_node
= parent_pos
.node
;
648 auto parent_iter
= parent_pos
.get_iter();
658 DEBUGT("splitted {} into left: {}, right: {}",
663 c
.cache
.retire_extent(c
.trans
, pos
.node
);
665 return std::make_pair(left
, right
);
668 for (; split_from
> 0; --split_from
) {
669 auto &parent_pos
= iter
.get_internal(split_from
+ 1);
670 if (!parent_pos
.node
->is_pending()) {
671 parent_pos
.node
= c
.cache
.duplicate_for_write(
672 c
.trans
, parent_pos
.node
673 )->cast
<LBAInternalNode
>();
676 if (split_from
> 1) {
677 auto &pos
= iter
.get_internal(split_from
);
678 DEBUGT("splitting internal {} at depth {}, parent: {} at pos: {}",
684 auto [left
, right
] = split_level(parent_pos
, pos
);
686 if (pos
.pos
< left
->get_size()) {
690 pos
.pos
-= left
->get_size();
695 auto &pos
= iter
.leaf
;
696 DEBUGT("splitting leaf {}, parent: {} at pos: {}",
701 auto [left
, right
] = split_level(parent_pos
, pos
);
703 /* right->get_node_meta().begin == pivot == right->begin()->get_key()
704 * Thus, if pos.pos == left->get_size(), we want iter to point to
705 * left with pos.pos at the end rather than right with pos.pos = 0
706 * since the insertion would be to the left of the first element
707 * of right and thus necessarily less than right->get_node_meta().begin.
709 if (pos
.pos
<= left
->get_size()) {
713 pos
.pos
-= left
->get_size();
720 return seastar::now();
723 template <typename NodeType
>
724 LBABtree::base_iertr::future
<typename
NodeType::Ref
> get_node(
732 LBABtree::base_iertr::future
<LBALeafNodeRef
> get_node
<LBALeafNode
>(
739 return LBABtree::get_leaf_node(c
, addr
, begin
, end
);
743 LBABtree::base_iertr::future
<LBAInternalNodeRef
> get_node
<LBAInternalNode
>(
749 return LBABtree::get_internal_node(c
, depth
, addr
, begin
, end
);
752 template <typename NodeType
>
753 LBABtree::handle_merge_ret
merge_level(
756 LBABtree::node_position_t
<LBAInternalNode
> &parent_pos
,
757 LBABtree::node_position_t
<NodeType
> &pos
)
759 LOG_PREFIX(LBABtree::merge_level
);
760 if (!parent_pos
.node
->is_pending()) {
761 parent_pos
.node
= c
.cache
.duplicate_for_write(
762 c
.trans
, parent_pos
.node
763 )->cast
<LBAInternalNode
>();
766 auto iter
= parent_pos
.get_iter();
767 assert(iter
.get_offset() < parent_pos
.node
->get_size());
768 bool donor_is_left
= ((iter
.get_offset() + 1) == parent_pos
.node
->get_size());
769 auto donor_iter
= donor_is_left
? (iter
- 1) : (iter
+ 1);
770 auto next_iter
= donor_iter
+ 1;
771 auto begin
= donor_iter
->get_key();
772 auto end
= next_iter
== parent_pos
.node
->end()
773 ? parent_pos
.node
->get_node_meta().end
774 : next_iter
->get_key();
776 DEBUGT("parent: {}, node: {}", c
.trans
, *parent_pos
.node
, *pos
.node
);
777 return get_node
<NodeType
>(
780 donor_iter
.get_val().maybe_relative_to(parent_pos
.node
->get_paddr()),
783 ).si_then([c
, iter
, donor_iter
, donor_is_left
, &parent_pos
, &pos
](
784 typename
NodeType::Ref donor
) {
785 LOG_PREFIX(LBABtree::merge_level
);
786 auto [l
, r
] = donor_is_left
?
787 std::make_pair(donor
, pos
.node
) : std::make_pair(pos
.node
, donor
);
789 auto [liter
, riter
] = donor_is_left
?
790 std::make_pair(donor_iter
, iter
) : std::make_pair(iter
, donor_iter
);
792 if (donor
->at_min_capacity()) {
793 auto replacement
= l
->make_full_merge(c
, r
);
795 parent_pos
.node
->update(
797 replacement
->get_paddr());
798 parent_pos
.node
->remove(riter
);
800 pos
.node
= replacement
;
802 pos
.pos
+= r
->get_size();
806 DEBUGT("l: {}, r: {}, replacement: {}", c
.trans
, *l
, *r
, *replacement
);
807 c
.cache
.retire_extent(c
.trans
, l
);
808 c
.cache
.retire_extent(c
.trans
, r
);
810 LOG_PREFIX(LBABtree::merge_level
);
811 auto [replacement_l
, replacement_r
, pivot
] =
817 parent_pos
.node
->update(
819 replacement_l
->get_paddr());
820 parent_pos
.node
->replace(
823 replacement_r
->get_paddr());
826 assert(parent_pos
.pos
> 0);
830 auto orig_position
= donor_is_left
?
831 l
->get_size() + pos
.pos
:
833 if (orig_position
< replacement_l
->get_size()) {
834 pos
.node
= replacement_l
;
835 pos
.pos
= orig_position
;
838 pos
.node
= replacement_r
;
839 pos
.pos
= orig_position
- replacement_l
->get_size();
842 DEBUGT("l: {}, r: {}, replacement_l: {}, replacement_r: {}",
843 c
.trans
, *l
, *r
, *replacement_l
, *replacement_r
);
844 c
.cache
.retire_extent(c
.trans
, l
);
845 c
.cache
.retire_extent(c
.trans
, r
);
848 return seastar::now();
852 LBABtree::handle_merge_ret
LBABtree::handle_merge(
856 LOG_PREFIX(LBATree::handle_merge
);
857 if (iter
.get_depth() == 1 ||
858 !iter
.leaf
.node
->below_min_capacity()) {
860 "no need to merge leaf, leaf size {}, depth {}",
862 iter
.leaf
.node
->get_size(),
864 return seastar::now();
867 return seastar::do_with(
869 [FNAME
, this, c
, &iter
](auto &to_merge
) {
870 return trans_intr::repeat(
871 [FNAME
, this, c
, &iter
, &to_merge
] {
876 auto &parent_pos
= iter
.get_internal(to_merge
+ 1);
877 auto merge_fut
= handle_merge_iertr::now();
879 auto &pos
= iter
.get_internal(to_merge
);
880 merge_fut
= merge_level(c
, to_merge
, parent_pos
, pos
);
882 auto &pos
= iter
.leaf
;
883 merge_fut
= merge_level(c
, to_merge
, parent_pos
, pos
);
886 return merge_fut
.si_then([FNAME
, this, c
, &iter
, &to_merge
] {
888 auto &pos
= iter
.get_internal(to_merge
);
889 if (to_merge
== iter
.get_depth()) {
890 if (pos
.node
->get_size() == 1) {
891 DEBUGT("collapsing root", c
.trans
);
892 c
.cache
.retire_extent(c
.trans
, pos
.node
);
893 assert(pos
.pos
== 0);
894 auto node_iter
= pos
.get_iter();
896 node_iter
->get_val().maybe_relative_to(pos
.node
->get_paddr()));
897 iter
.internal
.pop_back();
898 root
.set_depth(iter
.get_depth());
899 c
.trans
.get_lba_tree_stats().depth
= iter
.get_depth();
902 DEBUGT("no need to collapse root", c
.trans
);
904 return seastar::stop_iteration::yes
;
905 } else if (pos
.node
->below_min_capacity()) {
907 "continuing, next node {} depth {} at min",
911 return seastar::stop_iteration::no
;
914 "complete, next node {} depth {} not min",
918 return seastar::stop_iteration::yes
;
925 LBABtree::update_internal_mapping_ret
LBABtree::update_internal_mapping(
932 LOG_PREFIX(LBATree::update_internal_mapping
);
934 "updating laddr {} at depth {} from {} to {}",
943 ).si_then([=](auto iter
) {
944 assert(iter
.get_depth() >= depth
);
945 if (depth
== iter
.get_depth()) {
946 DEBUGT("update at root", c
.trans
);
950 "updating root laddr {} at depth {} from {} to {},"
957 root
.get_location());
958 ceph_assert(0 == "impossible");
961 if (root
.get_location() != old_addr
) {
963 "updating root laddr {} at depth {} from {} to {},"
964 "root addr {} does not match",
970 root
.get_location());
971 ceph_assert(0 == "impossible");
974 root
.set_location(new_addr
);
977 auto &parent
= iter
.get_internal(depth
+ 1);
979 assert(parent
.pos
< parent
.node
->get_size());
980 auto piter
= parent
.node
->iter_idx(parent
.pos
);
982 if (piter
->get_key() != laddr
) {
984 "updating laddr {} at depth {} from {} to {},"
985 "node {} pos {} val pivot addr {} does not match",
994 ceph_assert(0 == "impossible");
998 if (piter
->get_val() != old_addr
) {
1000 "updating laddr {} at depth {} from {} to {},"
1001 "node {} pos {} val addr {} does not match",
1010 ceph_assert(0 == "impossible");
1013 CachedExtentRef mut
= c
.cache
.duplicate_for_write(
1017 LBAInternalNodeRef mparent
= mut
->cast
<LBAInternalNode
>();
1018 mparent
->update(piter
, new_addr
);
1020 /* Note, iter is now invalid as we didn't udpate either the parent
1021 * node reference to the new mutable instance nor did we update the
1022 * child pointer to the new node. Not a problem as we'll now just
1026 return seastar::now();