From 5269043b2fd6db968ef4fa4f8ae52ddf9d8b0a96 Mon Sep 17 00:00:00 2001 From: Samuel Just Date: Thu, 16 Jul 2020 15:25:45 -0700 Subject: [PATCH] crimson/os/seastore/lba_manager/btree: wire in btree pin set Signed-off-by: Samuel Just --- .../lba_manager/btree/btree_lba_manager.cc | 82 ++++++++++++++++++- .../lba_manager/btree/btree_lba_manager.h | 7 +- .../lba_manager/btree/lba_btree_node.h | 6 +- .../lba_manager/btree/lba_btree_node_impl.cc | 23 ++++-- .../lba_manager/btree/lba_btree_node_impl.h | 45 ++++++---- 5 files changed, 135 insertions(+), 28 deletions(-) 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 7e6df859fae..e5ba69a0bc7 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 @@ -28,7 +28,9 @@ BtreeLBAManager::mkfs_ret BtreeLBAManager::mkfs( t, LBA_BLOCK_SIZE); root_leaf->set_size(0); - root_leaf->set_meta({0, L_ADDR_MAX, 1}); + lba_node_meta_t meta{0, L_ADDR_MAX, 1}; + root_leaf->set_meta(meta); + root_leaf->pin.set_range(meta); croot->get_lba_root() = root_t{ 1, @@ -157,11 +159,83 @@ BtreeLBAManager::set_extent( }); } +static bool is_lba_node(const CachedExtent &e) +{ + return e.get_type() == extent_types_t::LADDR_INTERNAL || + e.get_type() == extent_types_t::LADDR_LEAF; +} + +btree_range_pin_t &BtreeLBAManager::get_pin(CachedExtent &e) +{ + if (is_lba_node(e)) { + return e.cast()->pin; + } else if (e.is_logical()) { + return static_cast( + e.cast()->get_pin()).pin; + } else { + assert(0 == "impossible"); + return *static_cast(nullptr); + } +} + +static depth_t get_depth(const CachedExtent &e) +{ + if (is_lba_node(e)) { + return e.cast()->get_node_meta().depth; + } else if (e.is_logical()) { + return 0; + } else { + ceph_assert(0 == "currently impossible"); + return 0; + } +} + BtreeLBAManager::complete_transaction_ret BtreeLBAManager::complete_transaction( Transaction &t) { - // This is a noop for now and may end up not being necessary + std::vector to_clear; + to_clear.reserve(t.get_retired_set().size()); + for (auto &e: t.get_retired_set()) { + if (e->is_logical() || is_lba_node(*e)) + to_clear.push_back(e); + } + // need to call check_parent from leaf->parent + std::sort( + to_clear.begin(), to_clear.end(), + [](auto &l, auto &r) { return get_depth(*l) < get_depth(*r); }); + + for (auto &e: to_clear) { + auto &pin = get_pin(*e); + logger().debug("{}: retiring {}, {}", __func__, *e, pin); + pin_set.retire(pin); + } + + // ...but add_pin from parent->leaf + std::vector to_link; + to_link.reserve( + t.get_fresh_block_list().size() + + t.get_mutated_block_list().size()); + for (auto &l: {t.get_fresh_block_list(), t.get_mutated_block_list()}) { + for (auto &e: l) { + if (e->is_valid() && (is_lba_node(*e) || e->is_logical())) + to_link.push_back(e); + } + } + std::sort( + to_link.begin(), to_link.end(), + [](auto &l, auto &r) -> bool { return get_depth(*l) > get_depth(*r); }); + + for (auto &e : to_link) { + logger().debug("{}: linking {}", __func__, *e); + pin_set.add_pin(get_pin(*e)); + } + + for (auto &e: to_clear) { + auto &pin = get_pin(*e); + logger().debug("{}: checking {}, {}", __func__, *e, pin); + pin_set.check_parent(pin); + } return complete_transaction_ertr::now(); } @@ -191,7 +265,9 @@ BtreeLBAManager::insert_mapping_ret BtreeLBAManager::insert_mapping( croot = mut_croot->cast(); } auto nroot = cache.alloc_new_extent(t, LBA_BLOCK_SIZE); - nroot->set_meta({0, L_ADDR_MAX, croot->root.lba_depth + 1}); + lba_node_meta_t meta{0, L_ADDR_MAX, root->get_node_meta().depth + 1}; + nroot->set_meta(meta); + nroot->pin.set_range(meta); nroot->journal_insert( nroot->begin(), L_ADDR_MIN, 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 f064d26df5d..c32af3aab6a 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 @@ -87,10 +87,15 @@ private: SegmentManager &segment_manager; Cache &cache; + btree_pin_set_t pin_set; + op_context_t get_context(Transaction &t) { - return op_context_t{cache, t}; + return op_context_t{cache, pin_set, t}; } + static btree_range_pin_t &get_pin(CachedExtent &e); + + /** * get_root * 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 9b9b6b06621..e1ebb25c748 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 @@ -14,6 +14,7 @@ namespace crimson::os::seastore::lba_manager::btree { struct op_context_t { Cache &cache; + btree_pin_set_t &pins; Transaction &trans; }; @@ -49,10 +50,11 @@ struct LBANode : CachedExtent { using lookup_range_ertr = LBAManager::get_mapping_ertr; using lookup_range_ret = LBAManager::get_mapping_ret; + btree_range_pin_t pin; - LBANode(ceph::bufferptr &&ptr) : CachedExtent(std::move(ptr)) {} + LBANode(ceph::bufferptr &&ptr) : CachedExtent(std::move(ptr)), pin(this) {} LBANode(const LBANode &rhs) - : CachedExtent(rhs) {} + : CachedExtent(rhs), pin(rhs.pin, this) {} virtual lba_node_meta_t get_node_meta() const = 0; 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 7342ecffb0d..1641a87d8bf 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 @@ -44,7 +44,6 @@ LBAInternalNode::lookup_range_ret LBAInternalNode::lookup_range( val.get_val(), get_paddr()).safe_then( [c, &result, addr, len](auto extent) mutable { - // TODO: add backrefs to ensure cache residence of parents return extent->lookup_range( c, addr, @@ -318,12 +317,12 @@ LBALeafNode::lookup_range_ret LBALeafNode::lookup_range( auto ret = lba_pin_list_t(); auto [i, end] = get_leaf_entries(addr, len); for (; i != end; ++i) { - auto val = (*i).get_val(); + auto val = i->get_val(); + auto begin = i->get_key(); ret.emplace_back( std::make_unique( val.paddr, - (*i).get_key(), - val.len)); + lba_node_meta_t{ begin, begin + val.len, 0})); } return lookup_range_ertr::make_ready_future( std::move(ret)); @@ -356,12 +355,12 @@ LBALeafNode::insert_ret LBALeafNode::insert( insert_pt.get_key(), insert_pt.get_val().len, insert_pt.get_val().paddr); + auto begin = insert_pt.get_key(); return insert_ret( insert_ertr::ready_future_marker{}, std::make_unique( val.paddr, - laddr, - val.len)); + lba_node_meta_t{ begin, begin + val.len, 0})); } LBALeafNode::mutate_mapping_ret LBALeafNode::mutate_mapping( @@ -465,12 +464,16 @@ Cache::get_extent_ertr::future get_lba_btree_extent( return c.cache.get_extent( c.trans, offset, - LBA_BLOCK_SIZE).safe_then([depth](auto ret) { + LBA_BLOCK_SIZE).safe_then([c](auto ret) { auto meta = ret->get_meta(); if (ret->get_size()) { ceph_assert(meta.begin <= ret->begin()->get_key()); ceph_assert(meta.end > (ret->end() - 1)->get_key()); } + if (!ret->is_pending() && !ret->pin.is_linked()) { + ret->pin.set_range(meta); + c.pins.add_pin(ret->pin); + } return LBANodeRef(ret.detach(), /* add_ref = */ false); }); } else { @@ -481,7 +484,7 @@ Cache::get_extent_ertr::future get_lba_btree_extent( return c.cache.get_extent( c.trans, offset, - LBA_BLOCK_SIZE).safe_then([offset, depth](auto ret) { + LBA_BLOCK_SIZE).safe_then([offset, c](auto ret) { logger().debug( "get_lba_btree_extent: read leaf at offset {}", offset); @@ -490,6 +493,10 @@ Cache::get_extent_ertr::future get_lba_btree_extent( ceph_assert(meta.begin <= ret->begin()->get_key()); ceph_assert(meta.end > (ret->end() - 1)->get_key()); } + if (!ret->is_pending() && !ret->pin.is_linked()) { + ret->pin.set_range(meta); + c.pins.add_pin(ret->pin); + } return LBANodeRef(ret.detach(), /* add_ref = */ false); }); } 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 ba5d9edce16..431a894ec8e 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 @@ -119,10 +119,13 @@ struct LBAInternalNode c.trans, LBA_BLOCK_SIZE); auto right = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); + auto pivot = split_into(*left, *right); + left->pin.set_range(left->get_meta()); + right->pin.set_range(right->get_meta()); return std::make_tuple( left, right, - split_into(*left, *right)); + pivot); } LBANodeRef make_full_merge( @@ -131,6 +134,7 @@ struct LBAInternalNode auto replacement = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); replacement->merge_from(*this, *right->cast()); + replacement->pin.set_range(replacement->get_meta()); return replacement; } @@ -146,15 +150,19 @@ struct LBAInternalNode auto replacement_right = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); + auto pivot = balance_into_new_nodes( + *this, + right, + prefer_left, + *replacement_left, + *replacement_right); + + replacement_left->pin.set_range(replacement_left->get_meta()); + replacement_right->pin.set_range(replacement_right->get_meta()); return std::make_tuple( replacement_left, replacement_right, - balance_into_new_nodes( - *this, - right, - prefer_left, - *replacement_left, - *replacement_right)); + pivot); } /** @@ -358,10 +366,13 @@ struct LBALeafNode c.trans, LBA_BLOCK_SIZE); auto right = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); + auto pivot = split_into(*left, *right); + left->pin.set_range(left->get_meta()); + right->pin.set_range(right->get_meta()); return std::make_tuple( left, right, - split_into(*left, *right)); + pivot); } LBANodeRef make_full_merge( @@ -370,6 +381,7 @@ struct LBALeafNode auto replacement = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); replacement->merge_from(*this, *right->cast()); + replacement->pin.set_range(replacement->get_meta()); return replacement; } @@ -384,15 +396,20 @@ struct LBALeafNode c.trans, LBA_BLOCK_SIZE); auto replacement_right = c.cache.alloc_new_extent( c.trans, LBA_BLOCK_SIZE); + + auto pivot = balance_into_new_nodes( + *this, + right, + prefer_left, + *replacement_left, + *replacement_right); + + replacement_left->pin.set_range(replacement_left->get_meta()); + replacement_right->pin.set_range(replacement_right->get_meta()); return std::make_tuple( replacement_left, replacement_right, - balance_into_new_nodes( - *this, - right, - prefer_left, - *replacement_left, - *replacement_right)); + pivot); } // See LBAInternalNode, same concept -- 2.39.5