From 1c3df6f1c7267ef06223480e20a71e93b6cf729a Mon Sep 17 00:00:00 2001 From: Samuel Just Date: Fri, 6 Nov 2020 15:00:20 -0800 Subject: [PATCH] crimson/os/seastore/.../lba_btree_node: collapse root on merge if down to one element Signed-off-by: Samuel Just --- .../lba_manager/btree/lba_btree_node.h | 7 +++ .../lba_manager/btree/lba_btree_node_impl.cc | 59 +++++++++++++++---- .../lba_manager/btree/lba_btree_node_impl.h | 13 +++- 3 files changed, 68 insertions(+), 11 deletions(-) diff --git a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node.h b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node.h index 040bcc49344..b6f33a1ae87 100644 --- a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node.h +++ b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node.h @@ -144,6 +144,8 @@ struct LBANode : CachedExtent { * If it returns nullopt, removes the value. * Caller must already have merged if at_min_capacity(). * + * Recursive calls use mutate_mapping_internal. + * * Precondition: !at_min_capacity() */ using mutate_mapping_ertr = crimson::errorator< @@ -159,6 +161,11 @@ struct LBANode : CachedExtent { op_context_t c, laddr_t laddr, mutate_func_t &&f) = 0; + virtual mutate_mapping_ret mutate_mapping_internal( + op_context_t c, + laddr_t laddr, + bool is_root, + mutate_func_t &&f) = 0; /** * mutate_internal_address diff --git a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.cc b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.cc index 7587cb9188e..5e400803bc1 100644 --- a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.cc +++ b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.cc @@ -108,6 +108,15 @@ LBAInternalNode::mutate_mapping_ret LBAInternalNode::mutate_mapping( op_context_t c, laddr_t laddr, mutate_func_t &&f) +{ + return mutate_mapping_internal(c, laddr, true, std::move(f)); +} + +LBAInternalNode::mutate_mapping_ret LBAInternalNode::mutate_mapping_internal( + op_context_t c, + laddr_t laddr, + bool is_root, + mutate_func_t &&f) { auto mutation_pt = get_containing_child(laddr); if (mutation_pt == end()) { @@ -119,19 +128,20 @@ LBAInternalNode::mutate_mapping_ret LBAInternalNode::mutate_mapping( get_meta().depth - 1, mutation_pt->get_val(), get_paddr() - ).safe_then([this, c, laddr, mutation_pt](LBANodeRef extent) { - if (extent->at_min_capacity()) { + ).safe_then([=](LBANodeRef extent) { + if (extent->at_min_capacity() && get_size() > 1) { return merge_entry( c, laddr, mutation_pt, - extent); + extent, + is_root); } else { return merge_ertr::make_ready_future( std::move(extent)); } }).safe_then([c, laddr, f=std::move(f)](LBANodeRef extent) mutable { - return extent->mutate_mapping(c, laddr, std::move(f)); + return extent->mutate_mapping_internal(c, laddr, false, std::move(f)); }); } @@ -322,12 +332,14 @@ LBAInternalNode::merge_ret LBAInternalNode::merge_entry( op_context_t c, laddr_t addr, - internal_iterator_t iter, LBANodeRef entry) + internal_iterator_t iter, + LBANodeRef entry, + bool is_root) { if (!is_pending()) { auto mut = c.cache.duplicate_for_write(c.trans, this)->cast(); auto mut_iter = mut->iter_idx(iter->get_offset()); - return mut->merge_entry(c, addr, mut_iter, entry); + return mut->merge_entry(c, addr, mut_iter, entry, is_root); } logger().debug( @@ -341,8 +353,7 @@ LBAInternalNode::merge_entry( get_meta().depth - 1, donor_iter->get_val(), get_paddr() - ).safe_then([this, c, addr, iter, entry, donor_iter, donor_is_left]( - auto donor) mutable { + ).safe_then([=](auto donor) mutable { auto [l, r] = donor_is_left ? std::make_pair(donor, entry) : std::make_pair(entry, donor); auto [liter, riter] = donor_is_left ? @@ -360,7 +371,25 @@ LBAInternalNode::merge_entry( c.cache.retire_extent(c.trans, l); c.cache.retire_extent(c.trans, r); - return merge_ertr::make_ready_future(replacement); + + if (is_root && get_size() == 1) { + return c.cache.get_root(c.trans).safe_then([=](RootBlockRef croot) { + { + auto mut_croot = c.cache.duplicate_for_write(c.trans, croot); + croot = mut_croot->cast(); + } + croot->root.lba_root_addr = begin()->get_val(); + logger().debug( + "LBAInternalNode::merge_entry: collapsing root {} to addr {}", + *this, + begin()->get_val()); + croot->root.lba_depth = get_meta().depth - 1; + c.cache.retire_extent(c.trans, this); + return merge_ertr::make_ready_future(replacement); + }); + } else { + return merge_ertr::make_ready_future(replacement); + } } else { logger().debug( "LBAInternalEntry::merge_entry balanced l {} r {}", @@ -474,6 +503,15 @@ LBALeafNode::mutate_mapping_ret LBALeafNode::mutate_mapping( op_context_t c, laddr_t laddr, mutate_func_t &&f) +{ + return mutate_mapping_internal(c, laddr, true, std::move(f)); +} + +LBALeafNode::mutate_mapping_ret LBALeafNode::mutate_mapping_internal( + op_context_t c, + laddr_t laddr, + bool is_root, + mutate_func_t &&f) { auto mutation_pt = find(laddr); if (mutation_pt == end()) { @@ -482,9 +520,10 @@ LBALeafNode::mutate_mapping_ret LBALeafNode::mutate_mapping( if (!is_pending()) { return c.cache.duplicate_for_write(c.trans, this)->cast( - )->mutate_mapping( + )->mutate_mapping_internal( c, laddr, + is_root, std::move(f)); } diff --git a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.h b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.h index e84e5f23d94..230eef68227 100644 --- a/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.h +++ b/src/crimson/os/seastore/lba_manager/btree/lba_btree_node_impl.h @@ -108,6 +108,11 @@ struct LBAInternalNode op_context_t c, laddr_t laddr, mutate_func_t &&f) final; + mutate_mapping_ret mutate_mapping_internal( + op_context_t c, + laddr_t laddr, + bool is_root, + mutate_func_t &&f) final; mutate_internal_address_ret mutate_internal_address( op_context_t c, @@ -284,7 +289,8 @@ struct LBAInternalNode op_context_t c, laddr_t addr, internal_iterator_t, - LBANodeRef entry); + LBANodeRef entry, + bool is_root); /// returns iterator for subtree containing laddr internal_iterator_t get_containing_child(laddr_t laddr); @@ -381,6 +387,11 @@ struct LBALeafNode op_context_t c, laddr_t laddr, mutate_func_t &&f) final; + mutate_mapping_ret mutate_mapping_internal( + op_context_t c, + laddr_t laddr, + bool is_root, + mutate_func_t &&f) final; mutate_internal_address_ret mutate_internal_address( op_context_t c, -- 2.39.5