From 617b87228f7f8b87dcaf406e39abe59691676b12 Mon Sep 17 00:00:00 2001 From: Samuel Just Date: Mon, 25 Oct 2021 07:47:16 +0000 Subject: [PATCH] crimson/os/seastore/.../lba_btree: fix min_capacity condition Reducing the size of split_merge_multi has an interesting side effect of causing removes to happen on some leaf nodes immediately after split. After split, child nodes would have size 72 or 73. At size 72, the node would be at_min_size() and a remove would put it below causing the at_min_size() condition to fail and hande_merge to misbehave. Replace at_min_capacity() with below_min_capacity(). below_min_capacity() will not be true for any child of a split, and asserts that the child is below capacity by no more than 1. Signed-off-by: Samuel Just --- .../seastore/lba_manager/btree/lba_btree.cc | 8 ++++---- .../os/seastore/lba_manager/btree/lba_btree.h | 4 ++-- .../lba_manager/btree/lba_btree_node.h | 20 +++++++++++++++---- 3 files changed, 22 insertions(+), 10 deletions(-) diff --git a/src/crimson/os/seastore/lba_manager/btree/lba_btree.cc b/src/crimson/os/seastore/lba_manager/btree/lba_btree.cc index 3190d59d48b7a..0263698b06968 100644 --- a/src/crimson/os/seastore/lba_manager/btree/lba_btree.cc +++ b/src/crimson/os/seastore/lba_manager/btree/lba_btree.cc @@ -666,7 +666,7 @@ LBABtree::handle_merge_ret merge_level( auto [liter, riter] = donor_is_left ? std::make_pair(donor_iter, iter) : std::make_pair(iter, donor_iter); - if (donor->at_min_capacity()) { + if (donor->below_min_capacity()) { auto replacement = l->make_full_merge(c, r); parent_pos.node->update( @@ -727,8 +727,8 @@ LBABtree::handle_merge_ret LBABtree::handle_merge( iterator &iter) { LOG_PREFIX(LBATree::handle_merge); - if (!iter.leaf.node->at_min_capacity() || - iter.get_depth() == 1) { + if (iter.get_depth() == 1 || + !iter.leaf.node->below_min_capacity()) { DEBUGT( "no need to merge leaf, leaf size {}, depth {}", c.trans, @@ -775,7 +775,7 @@ LBABtree::handle_merge_ret LBABtree::handle_merge( DEBUGT("no need to collapse root", c.trans); } return seastar::stop_iteration::yes; - } else if (pos.node->at_min_capacity()) { + } else if (pos.node->below_min_capacity()) { DEBUGT( "continuing, next node {} depth {} at min", c.trans, diff --git a/src/crimson/os/seastore/lba_manager/btree/lba_btree.h b/src/crimson/os/seastore/lba_manager/btree/lba_btree.h index dedf8e239e42a..078113c09d425 100644 --- a/src/crimson/os/seastore/lba_manager/btree/lba_btree.h +++ b/src/crimson/os/seastore/lba_manager/btree/lba_btree.h @@ -157,11 +157,11 @@ public: } depth_t check_merge() const { - if (!leaf.node->at_min_capacity()) { + if (!leaf.node->below_min_capacity()) { return 0; } for (depth_t merge_from = 1; merge_from < get_depth(); ++merge_from) { - if (!get_internal(merge_from + 1).node->at_min_capacity()) + if (!get_internal(merge_from + 1).node->below_min_capacity()) return merge_from; } return get_depth(); 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 72aebaa385950..09a9a1f44c665 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 @@ -313,12 +313,18 @@ struct LBAInternalNode resolve_relative_addrs(base); } + constexpr static size_t get_min_capacity() { + return (get_capacity() - 1) / 2; + } + bool at_max_capacity() const { + assert(get_size() <= get_capacity()); return get_size() == get_capacity(); } - bool at_min_capacity() const { - return get_size() == (get_capacity() / 2); + bool below_min_capacity() const { + assert(get_size() >= (get_min_capacity() - 1)); + return get_size() < get_min_capacity(); } }; using LBAInternalNodeRef = LBAInternalNode::Ref; @@ -530,12 +536,18 @@ struct LBALeafNode std::ostream &print_detail(std::ostream &out) const final; + constexpr static size_t get_min_capacity() { + return (get_capacity() - 1) / 2; + } + bool at_max_capacity() const { + assert(get_size() <= get_capacity()); return get_size() == get_capacity(); } - bool at_min_capacity() const { - return get_size() == (get_capacity() / 2); + bool below_min_capacity() const { + assert(get_size() >= (get_min_capacity() - 1)); + return get_size() < get_min_capacity(); } }; using LBALeafNodeRef = TCachedExtentRef; -- 2.39.5