From 55e1924e3818e7fb574893372ba7dfad4fa54014 Mon Sep 17 00:00:00 2001 From: Xuehan Xu Date: Thu, 27 Oct 2022 15:21:32 +0800 Subject: [PATCH] crimson/os/seastore/btree: "templatize" btree leaf node to distinguish leaf nodes with(out) children Signed-off-by: Xuehan Xu --- .../os/seastore/backref/backref_tree_node.h | 3 +- .../seastore/backref/btree_backref_manager.h | 2 +- .../os/seastore/btree/fixed_kv_btree.h | 15 ++- src/crimson/os/seastore/btree/fixed_kv_node.h | 5 +- src/crimson/os/seastore/cache.cc | 4 +- src/crimson/os/seastore/cache.h | 2 + src/crimson/os/seastore/cached_extent.h | 6 +- src/crimson/os/seastore/lba_manager.cc | 6 +- src/crimson/os/seastore/lba_manager.h | 1 + .../lba_manager/btree/btree_lba_manager.cc | 98 ++++++++++--------- .../lba_manager/btree/btree_lba_manager.h | 16 ++- .../lba_manager/btree/lba_btree_node.h | 3 +- src/crimson/os/seastore/seastore_types.h | 30 +++--- .../seastore/test_btree_lba_manager.cc | 2 +- 14 files changed, 115 insertions(+), 78 deletions(-) diff --git a/src/crimson/os/seastore/backref/backref_tree_node.h b/src/crimson/os/seastore/backref/backref_tree_node.h index bebbc0aa4b2f5..db9f1febff125 100644 --- a/src/crimson/os/seastore/backref/backref_tree_node.h +++ b/src/crimson/os/seastore/backref/backref_tree_node.h @@ -76,7 +76,8 @@ class BackrefLeafNode paddr_t, paddr_le_t, backref_map_val_t, backref_map_val_le_t, BACKREF_NODE_SIZE, - BackrefLeafNode> { + BackrefLeafNode, + false> { public: template BackrefLeafNode(T&&... t) : diff --git a/src/crimson/os/seastore/backref/btree_backref_manager.h b/src/crimson/os/seastore/backref/btree_backref_manager.h index 95a1c03113db8..0306d0e8bbe30 100644 --- a/src/crimson/os/seastore/backref/btree_backref_manager.h +++ b/src/crimson/os/seastore/backref/btree_backref_manager.h @@ -33,7 +33,7 @@ public: using BackrefBtree = FixedKVBtree< paddr_t, backref_map_val_t, BackrefInternalNode, - BackrefLeafNode, BtreeBackrefPin, BACKREF_BLOCK_SIZE>; + BackrefLeafNode, BtreeBackrefPin, BACKREF_BLOCK_SIZE, false>; class BtreeBackrefManager : public BackrefManager { public: diff --git a/src/crimson/os/seastore/btree/fixed_kv_btree.h b/src/crimson/os/seastore/btree/fixed_kv_btree.h index 0e51d00ed7678..6c3372819f324 100644 --- a/src/crimson/os/seastore/btree/fixed_kv_btree.h +++ b/src/crimson/os/seastore/btree/fixed_kv_btree.h @@ -57,7 +57,8 @@ template < typename internal_node_t, typename leaf_node_t, typename pin_t, - size_t node_size> + size_t node_size, + bool leaf_has_children> class FixedKVBtree { static constexpr size_t MAX_DEPTH = 16; using self_type = FixedKVBtree< @@ -66,7 +67,8 @@ class FixedKVBtree { internal_node_t, leaf_node_t, pin_t, - node_size>; + node_size, + leaf_has_children>; public: using InternalNodeRef = TCachedExtentRef; using LeafNodeRef = TCachedExtentRef; @@ -866,7 +868,8 @@ public: n_fixed_kv_extent->set_modify_time(fixed_kv_extent.get_modify_time()); n_fixed_kv_extent->pin.set_range(n_fixed_kv_extent->get_node_meta()); - if (fixed_kv_extent.get_type() == internal_node_t::TYPE) { + if (fixed_kv_extent.get_type() == internal_node_t::TYPE || + leaf_node_t::do_has_children) { if (!fixed_kv_extent.is_pending()) { n_fixed_kv_extent->copy_sources.emplace(&fixed_kv_extent); n_fixed_kv_extent->prior_instance = &fixed_kv_extent; @@ -2008,7 +2011,8 @@ template < typename internal_node_t, typename leaf_node_t, typename pin_t, - size_t node_size> + size_t node_size, + bool leaf_has_children> struct is_fixed_kv_tree< FixedKVBtree< node_key_t, @@ -2016,7 +2020,8 @@ struct is_fixed_kv_tree< internal_node_t, leaf_node_t, pin_t, - node_size>> : std::true_type {}; + node_size, + leaf_has_children>> : std::true_type {}; template < typename tree_type_t, diff --git a/src/crimson/os/seastore/btree/fixed_kv_node.h b/src/crimson/os/seastore/btree/fixed_kv_node.h index bee5b2fa512eb..202a270a33602 100644 --- a/src/crimson/os/seastore/btree/fixed_kv_node.h +++ b/src/crimson/os/seastore/btree/fixed_kv_node.h @@ -915,7 +915,8 @@ template < typename VAL, typename VAL_LE, size_t node_size, - typename node_type_t> + typename node_type_t, + bool has_children> struct FixedKVLeafNode : FixedKVNode, common::FixedKVNodeLayout< @@ -942,6 +943,8 @@ struct FixedKVLeafNode : FixedKVNode(rhs), node_layout_t(this->get_bptr().c_str()) {} + static constexpr bool do_has_children = has_children; + uint16_t get_node_split_pivot() final { return this->get_split_pivot().get_offset(); } diff --git a/src/crimson/os/seastore/cache.cc b/src/crimson/os/seastore/cache.cc index b189b96c23848..65f7f1d400f3d 100644 --- a/src/crimson/os/seastore/cache.cc +++ b/src/crimson/os/seastore/cache.cc @@ -146,6 +146,7 @@ void Cache::register_metrics() {extent_types_t::ROOT, sm::label_instance("ext", "ROOT")}, {extent_types_t::LADDR_INTERNAL, sm::label_instance("ext", "LADDR_INTERNAL")}, {extent_types_t::LADDR_LEAF, sm::label_instance("ext", "LADDR_LEAF")}, + {extent_types_t::DINK_LADDR_LEAF, sm::label_instance("ext", "DINK_LADDR_LEAF")}, {extent_types_t::OMAP_INNER, sm::label_instance("ext", "OMAP_INNER")}, {extent_types_t::OMAP_LEAF, sm::label_instance("ext", "OMAP_LEAF")}, {extent_types_t::ONODE_BLOCK_STAGED, sm::label_instance("ext", "ONODE_BLOCK_STAGED")}, @@ -969,7 +970,8 @@ CachedExtentRef Cache::alloc_new_extent_by_type( case extent_types_t::LADDR_INTERNAL: return alloc_new_extent(t, length, hint, gen); case extent_types_t::LADDR_LEAF: - return alloc_new_extent(t, length, hint, gen); + return alloc_new_extent( + t, length, hint, gen); case extent_types_t::ONODE_BLOCK_STAGED: return alloc_new_extent(t, length, hint, gen); case extent_types_t::OMAP_INNER: diff --git a/src/crimson/os/seastore/cache.h b/src/crimson/os/seastore/cache.h index ec3c27b160674..0e004761bab89 100644 --- a/src/crimson/os/seastore/cache.h +++ b/src/crimson/os/seastore/cache.h @@ -1119,6 +1119,8 @@ public: switch (type) { case extent_types_t::LADDR_INTERNAL: [[fallthrough]]; + case extent_types_t::DINK_LADDR_LEAF: + [[fallthrough]]; case extent_types_t::LADDR_LEAF: stats.lba_tree_extents_num += delta; ceph_assert(stats.lba_tree_extents_num >= 0); diff --git a/src/crimson/os/seastore/cached_extent.h b/src/crimson/os/seastore/cached_extent.h index a2544d5e996b0..5ee08f9bbb609 100644 --- a/src/crimson/os/seastore/cached_extent.h +++ b/src/crimson/os/seastore/cached_extent.h @@ -30,7 +30,8 @@ template < typename internal_node_t, typename leaf_node_t, typename pin_t, - size_t node_size> + size_t node_size, + bool leaf_has_children> class FixedKVBtree; // #define DEBUG_CACHED_EXTENT_REF @@ -189,7 +190,8 @@ class CachedExtent typename internal_node_t, typename leaf_node_t, typename pin_t, - size_t node_size> + size_t node_size, + bool leaf_has_children> friend class FixedKVBtree; uint32_t last_committed_crc = 0; diff --git a/src/crimson/os/seastore/lba_manager.cc b/src/crimson/os/seastore/lba_manager.cc index 3e3251f062a52..b35e2d0ead8c3 100644 --- a/src/crimson/os/seastore/lba_manager.cc +++ b/src/crimson/os/seastore/lba_manager.cc @@ -22,8 +22,12 @@ LBAManager::update_mappings( }); } +template LBAManagerRef lba_manager::create_lba_manager(Cache &cache) { - return LBAManagerRef(new btree::BtreeLBAManager(cache)); + return LBAManagerRef(new btree::BtreeLBAManager(cache)); } +template LBAManagerRef lba_manager::create_lba_manager(Cache &cache); +template LBAManagerRef lba_manager::create_lba_manager(Cache &cache); + } diff --git a/src/crimson/os/seastore/lba_manager.h b/src/crimson/os/seastore/lba_manager.h index f512b73f677e1..f495eb0753483 100644 --- a/src/crimson/os/seastore/lba_manager.h +++ b/src/crimson/os/seastore/lba_manager.h @@ -206,6 +206,7 @@ using LBAManagerRef = std::unique_ptr; class Cache; namespace lba_manager { +template LBAManagerRef create_lba_manager(Cache &cache); } diff --git a/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.cc b/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.cc index 2c159535f3874..64dd3103ce2bf 100644 --- a/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.cc +++ b/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.cc @@ -21,18 +21,27 @@ SET_SUBSYS(seastore_lba); namespace crimson::os::seastore { -template<> -Transaction::tree_stats_t& get_tree_stats< - crimson::os::seastore::lba_manager::btree::LBABtree>(Transaction &t) { +template +Transaction::tree_stats_t& get_tree_stats(Transaction &t) +{ return t.get_lba_tree_stats(); } -template<> -phy_tree_root_t& get_phy_tree_root< - crimson::os::seastore::lba_manager::btree::LBABtree>(root_t &r) { +template Transaction::tree_stats_t& +get_tree_stats< + crimson::os::seastore::lba_manager::btree::LBABtree>( + Transaction &t); + +template +phy_tree_root_t& get_phy_tree_root(root_t &r) +{ return r.lba_root; } +template phy_tree_root_t& +get_phy_tree_root< + crimson::os::seastore::lba_manager::btree::LBABtree>(root_t &r); + template <> const get_phy_tree_root_node_ret get_phy_tree_root_node< crimson::os::seastore::lba_manager::btree::LBABtree>( @@ -89,7 +98,8 @@ void unlink_phy_tree_root_node(RootBlockRef &root_block) { namespace crimson::os::seastore::lba_manager::btree { -BtreeLBAManager::mkfs_ret BtreeLBAManager::mkfs( +BtreeLBAManager::mkfs_ret +BtreeLBAManager::mkfs( Transaction &t) { LOG_PREFIX(BtreeLBAManager::mkfs); @@ -125,7 +135,7 @@ BtreeLBAManager::get_mappings( if (pos.is_end() || pos.get_key() >= (offset + length)) { TRACET("{}~{} done with {} results", c.trans, offset, length, ret.size()); - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::yes); } @@ -133,14 +143,13 @@ BtreeLBAManager::get_mappings( c.trans, offset, length, pos.get_key(), pos.get_val()); ceph_assert((pos.get_key() + pos.get_val().len) > offset); ret.push_back(pos.get_pin()); - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::no); }); }); } - BtreeLBAManager::get_mappings_ret BtreeLBAManager::get_mappings( Transaction &t, @@ -155,7 +164,7 @@ BtreeLBAManager::get_mappings( l->begin(), l->end(), [this, &t, &ret](const auto &p) { - return get_mappings(t, p.first, p.second).si_then( + return this->get_mappings(t, p.first, p.second).si_then( [&ret](auto res) { ret.splice(ret.end(), res, res.begin(), res.end()); return get_mappings_iertr::now(); @@ -205,8 +214,8 @@ BtreeLBAManager::alloc_extent( struct state_t { laddr_t last_end; - std::optional insert_iter; - std::optional ret; + std::optional insert_iter; + std::optional ret; state_t(laddr_t hint) : last_end(hint) {} }; @@ -232,7 +241,7 @@ BtreeLBAManager::alloc_extent( stats.num_alloc_extents_iter_nexts - lookup_attempts, state.last_end); state.insert_iter = pos; - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::yes); } else if (pos.get_key() >= (state.last_end + len)) { @@ -243,7 +252,7 @@ BtreeLBAManager::alloc_extent( state.last_end, pos.get_val()); state.insert_iter = pos; - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::yes); } else { @@ -252,7 +261,7 @@ BtreeLBAManager::alloc_extent( t, addr, len, hint, pos.get_key(), pos.get_val().len, pos.get_val()); - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::no); } @@ -280,7 +289,8 @@ static bool is_lba_node(const CachedExtent &e) return is_lba_node(e.get_type()); } -btree_range_pin_t &BtreeLBAManager::get_pin(CachedExtent &e) +btree_range_pin_t &BtreeLBAManager::get_pin( + CachedExtent &e) { if (is_lba_node(e)) { return e.cast()->pin; @@ -338,7 +348,8 @@ void BtreeLBAManager::complete_transaction( } } -BtreeLBAManager::base_iertr::future<> _init_cached_extent( +BtreeLBAManager::base_iertr::template future<> +_init_cached_extent( op_context_t c, const CachedExtentRef &e, LBABtree &btree, @@ -377,7 +388,8 @@ BtreeLBAManager::base_iertr::future<> _init_cached_extent( } } -BtreeLBAManager::init_cached_extent_ret BtreeLBAManager::init_cached_extent( +BtreeLBAManager::init_cached_extent_ret +BtreeLBAManager::init_cached_extent( Transaction &t, CachedExtentRef e) { @@ -385,16 +397,19 @@ BtreeLBAManager::init_cached_extent_ret BtreeLBAManager::init_cached_extent( TRACET("{}", t, *e); return seastar::do_with(bool(), [this, e, &t](bool &ret) { auto c = get_context(t); - return with_btree(cache, c, [c, e, &ret](auto &btree) - -> base_iertr::future<> { - LOG_PREFIX(BtreeLBAManager::init_cached_extent); - DEBUGT("extent {}", c.trans, *e); - return _init_cached_extent(c, e, btree, ret); - }).si_then([&ret] { return ret; }); + return with_btree( + cache, c, + [c, e, &ret](auto &btree) -> base_iertr::future<> { + LOG_PREFIX(BtreeLBAManager::init_cached_extent); + DEBUGT("extent {}", c.trans, *e); + return _init_cached_extent(c, e, btree, ret); + } + ).si_then([&ret] { return ret; }); }); } -BtreeLBAManager::scan_mappings_ret BtreeLBAManager::scan_mappings( +BtreeLBAManager::scan_mappings_ret +BtreeLBAManager::scan_mappings( Transaction &t, laddr_t begin, laddr_t end, @@ -413,20 +428,21 @@ BtreeLBAManager::scan_mappings_ret BtreeLBAManager::scan_mappings( btree.upper_bound_right(c, begin), [f=std::move(f), begin, end](auto &pos) { if (pos.is_end() || pos.get_key() >= end) { - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::yes); } ceph_assert((pos.get_key() + pos.get_val().len) > begin); f(pos.get_key(), pos.get_val().paddr, pos.get_val().len); - return LBABtree::iterate_repeat_ret_inner( + return typename LBABtree::iterate_repeat_ret_inner( interruptible::ready_future_marker{}, seastar::stop_iteration::no); }); }); } -BtreeLBAManager::rewrite_extent_ret BtreeLBAManager::rewrite_extent( +BtreeLBAManager::rewrite_extent_ret +BtreeLBAManager::rewrite_extent( Transaction &t, CachedExtentRef extent) { @@ -504,18 +520,13 @@ BtreeLBAManager::get_physical_extent_if_live( if (type == extent_types_t::LADDR_INTERNAL) { return btree.get_internal_if_live(c, addr, laddr, len); } else { - assert(type == extent_types_t::LADDR_LEAF); + assert(type == extent_types_t::LADDR_LEAF || + type == extent_types_t::DINK_LADDR_LEAF); return btree.get_leaf_if_live(c, addr, laddr, len); } }); } -BtreeLBAManager::BtreeLBAManager(Cache &cache) - : cache(cache) -{ - register_metrics(); -} - void BtreeLBAManager::register_metrics() { LOG_PREFIX(BtreeLBAManager::register_metrics); @@ -539,7 +550,8 @@ void BtreeLBAManager::register_metrics() ); } -BtreeLBAManager::update_refcount_ret BtreeLBAManager::update_refcount( +BtreeLBAManager::update_refcount_ret +BtreeLBAManager::update_refcount( Transaction &t, laddr_t addr, int delta) @@ -565,7 +577,8 @@ BtreeLBAManager::update_refcount_ret BtreeLBAManager::update_refcount( }); } -BtreeLBAManager::_update_mapping_ret BtreeLBAManager::_update_mapping( +BtreeLBAManager::_update_mapping_ret +BtreeLBAManager::_update_mapping( Transaction &t, laddr_t addr, update_func_t &&f) @@ -606,13 +619,4 @@ BtreeLBAManager::_update_mapping_ret BtreeLBAManager::_update_mapping( }); } -BtreeLBAManager::~BtreeLBAManager() -{ - pin_set.scan([](auto &i) { - LOG_PREFIX(BtreeLBAManager::~BtreeLBAManager); - ERROR("Found {}, has_ref={} -- {}", - i, i.has_ref(), i.get_extent()); - }); -} - } diff --git a/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.h b/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.h index 3b0aa4aafd4ed..58dbe1e0581f3 100644 --- a/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.h +++ b/src/crimson/os/seastore/lba_manager/btree/btree_lba_manager.h @@ -42,7 +42,7 @@ public: using LBABtree = FixedKVBtree< laddr_t, lba_map_val_t, LBAInternalNode, - LBALeafNode, BtreeLBAPin, LBA_BLOCK_SIZE>; + LBALeafNode, BtreeLBAPin, LBA_BLOCK_SIZE, true>; /** * BtreeLBAManager @@ -63,7 +63,11 @@ using LBABtree = FixedKVBtree< */ class BtreeLBAManager : public LBAManager { public: - BtreeLBAManager(Cache &cache); + BtreeLBAManager(Cache &cache) + : cache(cache) + { + register_metrics(); + } mkfs_ret mkfs( Transaction &t) final; @@ -144,7 +148,13 @@ public: bpin->set_parent(nullptr); } - ~BtreeLBAManager(); + ~BtreeLBAManager() { + pin_set.scan([](auto &i) { + LOG_PREFIX(BtreeLBAManager::~BtreeLBAManager); + SUBERROR(seastore_lba, "Found {}, has_ref={} -- {}", + i, i.has_ref(), i.get_extent()); + }); + } private: Cache &cache; 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 571e906fa8fed..ff61829cb2e94 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 @@ -142,7 +142,8 @@ struct LBALeafNode laddr_t, laddr_le_t, lba_map_val_t, lba_map_val_le_t, LBA_BLOCK_SIZE, - LBALeafNode> { + LBALeafNode, + true> { using Ref = TCachedExtentRef; using internal_iterator_t = const_iterator; template diff --git a/src/crimson/os/seastore/seastore_types.h b/src/crimson/os/seastore/seastore_types.h index a1efc729b96fa..9b5e8801e3144 100644 --- a/src/crimson/os/seastore/seastore_types.h +++ b/src/crimson/os/seastore/seastore_types.h @@ -1062,23 +1062,24 @@ enum class extent_types_t : uint8_t { ROOT = 0, LADDR_INTERNAL = 1, LADDR_LEAF = 2, - OMAP_INNER = 3, - OMAP_LEAF = 4, - ONODE_BLOCK_STAGED = 5, - COLL_BLOCK = 6, - OBJECT_DATA_BLOCK = 7, - RETIRED_PLACEHOLDER = 8, + DINK_LADDR_LEAF = 3, + OMAP_INNER = 4, + OMAP_LEAF = 5, + ONODE_BLOCK_STAGED = 6, + COLL_BLOCK = 7, + OBJECT_DATA_BLOCK = 8, + RETIRED_PLACEHOLDER = 9, // the following two types are not extent types, // they are just used to indicates paddr allocation deltas - ALLOC_INFO = 9, - JOURNAL_TAIL = 10, + ALLOC_INFO = 10, + JOURNAL_TAIL = 11, // Test Block Types - TEST_BLOCK = 11, - TEST_BLOCK_PHYSICAL = 12, - BACKREF_INTERNAL = 13, - BACKREF_LEAF = 14, + TEST_BLOCK = 12, + TEST_BLOCK_PHYSICAL = 13, + BACKREF_INTERNAL = 14, + BACKREF_LEAF = 15, // None and the number of valid extent_types_t - NONE = 15, + NONE = 16, }; using extent_types_le_t = uint8_t; constexpr auto EXTENT_TYPES_MAX = static_cast(extent_types_t::NONE); @@ -1108,7 +1109,8 @@ constexpr bool is_retired_placeholder(extent_types_t type) constexpr bool is_lba_node(extent_types_t type) { return type == extent_types_t::LADDR_INTERNAL || - type == extent_types_t::LADDR_LEAF; + type == extent_types_t::LADDR_LEAF || + type == extent_types_t::DINK_LADDR_LEAF; } constexpr bool is_backref_node(extent_types_t type) diff --git a/src/test/crimson/seastore/test_btree_lba_manager.cc b/src/test/crimson/seastore/test_btree_lba_manager.cc index 3853d53e7a4ff..64a847f30a729 100644 --- a/src/test/crimson/seastore/test_btree_lba_manager.cc +++ b/src/test/crimson/seastore/test_btree_lba_manager.cc @@ -324,7 +324,7 @@ TEST_F(lba_btree_test, basic) } struct btree_lba_manager_test : btree_test_base { - BtreeLBAManagerRef lba_manager; + BtreeLBAManagerRef lba_manager; btree_lba_manager_test() = default; -- 2.39.5