From 5bd34cf1b3b9b30e69a68dfa3e52df8fe7338156 Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Fri, 5 Feb 2021 13:50:07 +0800 Subject: [PATCH] crimson/onode-staged-tree: cleanup -- implement and use get_next_slot() Signed-off-by: Yingxin Cheng --- .../onode_manager/staged-fltree/node.cc | 33 +++++++----- .../onode_manager/staged-fltree/node_impl.h | 31 ++++++++++- .../onode_manager/staged-fltree/node_layout.h | 50 +++++++++++++++--- .../staged-fltree/stages/stage.h | 51 +++++++++++++++++-- .../seastore/onode_tree/test_staged_fltree.cc | 2 - 5 files changed, 141 insertions(+), 26 deletions(-) diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc index 18fb9739d7fb0..2cea7a4210ef1 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc @@ -405,18 +405,23 @@ InternalNode::InternalNode(InternalNodeImpl* impl, NodeImplURef&& impl_ref) node_future> InternalNode::get_next_cursor(context_t c, const search_position_t& pos) { + assert(!impl->is_empty()); if (pos.is_end()) { assert(impl->is_level_tail()); return get_next_cursor_from_parent(c); } search_position_t next_pos = pos; - impl->next_position(next_pos); + const laddr_packed_t* p_child_addr = nullptr; + impl->get_next_slot(next_pos, nullptr, &p_child_addr); if (next_pos.is_end() && !impl->is_level_tail()) { return get_next_cursor_from_parent(c); } else { - laddr_t child_addr = impl->get_p_value(next_pos)->value; - return get_or_track_child(c, next_pos, child_addr + if (next_pos.is_end()) { + p_child_addr = impl->get_tail_value(); + } + assert(p_child_addr); + return get_or_track_child(c, next_pos, p_child_addr->value ).safe_then([c](auto child) { return child->lookup_smallest(c); }); @@ -544,6 +549,7 @@ InternalNode::lower_bound_tracked( node_future<> InternalNode::do_get_tree_stats( context_t c, tree_stats_t& stats) { + assert(!impl->is_empty()); auto nstats = impl->get_stats(); stats.size_persistent_internal += nstats.size_persistent; stats.size_filled_internal += nstats.size_filled; @@ -555,21 +561,23 @@ node_future<> InternalNode::do_get_tree_stats( Ref this_ref = this; return seastar::do_with( - search_position_t(), [this, this_ref, c, &stats](auto& pos) { + search_position_t(), (const laddr_packed_t*)(nullptr), + [this, this_ref, c, &stats](auto& pos, auto& p_child_addr) { pos = search_position_t::begin(); + impl->get_slot(pos, nullptr, &p_child_addr); return crimson::do_until( - [this, this_ref, c, &stats, &pos]() -> node_future { - auto child_addr = impl->get_p_value(pos)->value; - return get_or_track_child(c, pos, child_addr + [this, this_ref, c, &stats, &pos, &p_child_addr]() -> node_future { + return get_or_track_child(c, pos, p_child_addr->value ).safe_then([c, &stats](auto child) { return child->do_get_tree_stats(c, stats); - }).safe_then([this, this_ref, &pos] { + }).safe_then([this, this_ref, &pos, &p_child_addr] { if (pos.is_end()) { return node_ertr::make_ready_future(true); } else { - impl->next_position(pos); + impl->get_next_slot(pos, nullptr, &p_child_addr); if (pos.is_end()) { if (impl->is_level_tail()) { + p_child_addr = impl->get_tail_value(); return node_ertr::make_ready_future(false); } else { return node_ertr::make_ready_future(true); @@ -753,8 +761,11 @@ LeafNode::get_kv(const search_position_t& pos) const node_future> LeafNode::get_next_cursor(context_t c, const search_position_t& pos) { + assert(!impl->is_empty()); search_position_t next_pos = pos; - impl->next_position(next_pos); + key_view_t index_key; + const value_header_t* p_value_header = nullptr; + impl->get_next_slot(next_pos, &index_key, &p_value_header); if (next_pos.is_end()) { if (unlikely(is_level_tail())) { return node_ertr::make_ready_future>( @@ -763,8 +774,6 @@ LeafNode::get_next_cursor(context_t c, const search_position_t& pos) return get_next_cursor_from_parent(c); } } else { - key_view_t index_key; - auto p_value_header = impl->get_p_value(next_pos, &index_key); return node_ertr::make_ready_future>( get_or_track_cursor(next_pos, index_key, p_value_header)); } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.h index a7950c690661a..14b1fad2e9f02 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.h @@ -76,7 +76,6 @@ class NodeImpl { virtual node_offset_t free_size() const = 0; virtual key_view_t get_key_view(const search_position_t&) const = 0; virtual key_view_t get_largest_key_view() const = 0; - virtual void next_position(search_position_t&) const = 0; virtual node_stats_t get_stats() const = 0; virtual std::ostream& dump(std::ostream&) const = 0; @@ -100,6 +99,20 @@ class InternalNodeImpl : public NodeImpl { struct internal_marker_t {}; virtual ~InternalNodeImpl() = default; + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual void get_slot(const search_position_t&, // IN + key_view_t* = nullptr, // OUT + const laddr_packed_t** = nullptr) const { // OUT + ceph_abort("impossible path"); + } + + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual void get_next_slot(search_position_t&, // IN&OUT + key_view_t* = nullptr, // OUT + const laddr_packed_t** = nullptr) const { // OUT + ceph_abort("impossible path"); + } + #pragma GCC diagnostic ignored "-Woverloaded-virtual" virtual const laddr_packed_t* get_p_value( const search_position_t&, @@ -124,6 +137,8 @@ class InternalNodeImpl : public NodeImpl { ceph_abort("impossible path"); } + virtual const laddr_packed_t* get_tail_value() const = 0; + virtual void replace_child_addr(const search_position_t&, laddr_t dst, laddr_t src) = 0; virtual std::tuple evaluate_insert( const key_view_t&, const laddr_t&, search_position_t&) const = 0; @@ -152,6 +167,20 @@ class LeafNodeImpl : public NodeImpl { struct leaf_marker_t {}; virtual ~LeafNodeImpl() = default; + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual void get_slot(const search_position_t&, // IN + key_view_t* = nullptr, // OUT + const value_header_t** = nullptr) const { // OUT + ceph_abort("impossible path"); + } + + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual void get_next_slot(search_position_t&, // IN&OUT + key_view_t* = nullptr, // OUT + const value_header_t** = nullptr) const { // OUT + ceph_abort("impossible path"); + } + #pragma GCC diagnostic ignored "-Woverloaded-virtual" virtual const value_header_t* get_p_value( const search_position_t&, diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h index 4407e495a9111..db8a561bb6b21 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h @@ -107,14 +107,6 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { return index_key; } - void next_position(search_position_t& pos) const override { - assert(!pos.is_end()); - bool find_next = STAGE_T::next_position(extent.read(), cast_down(pos)); - if (find_next) { - pos = search_position_t::end(); - } - } - node_stats_t get_stats() const override { node_stats_t stats; auto& node_stage = extent.read(); @@ -198,6 +190,39 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { /* * Common */ + void get_slot(const search_position_t& pos, + key_view_t* p_index_key = nullptr, + const value_t** pp_value = nullptr) const override { + assert(!is_empty()); + assert(!pos.is_end()); + if (!p_index_key && pp_value) { + STAGE_T::template get_slot( + extent.read(), cast_down(pos), nullptr, pp_value); + } else { + ceph_abort("not implemented"); + } + } + + void get_next_slot(search_position_t& pos, + key_view_t* p_index_key = nullptr, + const value_t** pp_value = nullptr) const override { + assert(!is_empty()); + assert(!pos.is_end()); + bool find_next; + if (p_index_key && pp_value) { + find_next = STAGE_T::template get_next_slot( + extent.read(), cast_down(pos), p_index_key, pp_value); + } else if (!p_index_key && pp_value) { + find_next = STAGE_T::template get_next_slot( + extent.read(), cast_down(pos), nullptr, pp_value); + } else { + ceph_abort("not implemented"); + } + if (find_next) { + pos = search_position_t::end(); + } + } + const value_t* get_p_value(const search_position_t& position, key_view_t* index_key=nullptr, marker_t={}) const override { auto& node_stage = extent.read(); @@ -522,6 +547,15 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { /* * InternalNodeImpl */ + const laddr_packed_t* get_tail_value() const override { + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + assert(is_level_tail()); + return extent.read().get_end_p_laddr(); + } else { + ceph_abort("impossible path"); + } + } + void replace_child_addr( const search_position_t& pos, laddr_t dst, laddr_t src) override { if constexpr (NODE_TYPE == node_type_t::INTERNAL) { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage.h index 7e5d70a34238c..871add3068447 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage.h @@ -943,6 +943,36 @@ struct staged { } } + template + static void get_slot( + const container_t& container, // IN + const position_t& pos, // IN + full_key_t* p_index_key, // OUT + const value_t** pp_value) { // OUT + auto iter = iterator_t(container); + iter.seek_at(pos.index); + + if constexpr (GET_KEY) { + assert(p_index_key); + p_index_key->set(iter.get_key()); + } else { + assert(!p_index_key); + } + + if constexpr (!IS_BOTTOM) { + auto nxt_container = iter.get_nxt_container(); + NXT_STAGE_T::template get_slot( + nxt_container, pos.nxt, p_index_key, pp_value); + } else { + if constexpr (GET_VAL) { + assert(pp_value); + *pp_value = iter.get_p_value(); + } else { + assert(!pp_value); + } + } + } + static void get_key_view( const container_t& container, const position_t& position, @@ -1424,17 +1454,24 @@ struct staged { } while (true); } - static bool next_position(const container_t& container, position_t& pos) { + template + static bool get_next_slot( + const container_t& container, // IN + position_t& pos, // IN&OUT + full_key_t* p_index_key, // OUT + const value_t** pp_value) { // OUT auto iter = iterator_t(container); assert(!iter.is_end()); iter.seek_at(pos.index); bool find_next; if constexpr (!IS_BOTTOM) { auto nxt_container = iter.get_nxt_container(); - find_next = NXT_STAGE_T::next_position(nxt_container, pos.nxt); + find_next = NXT_STAGE_T::template get_next_slot( + nxt_container, pos.nxt, p_index_key, pp_value); } else { find_next = true; } + if (find_next) { if (iter.is_last()) { return true; @@ -1443,9 +1480,17 @@ struct staged { if constexpr (!IS_BOTTOM) { pos.nxt = NXT_STAGE_T::position_t::begin(); } + get_slot( + container, pos, p_index_key, pp_value); return false; } - } else { + } else { // !find_next && !IS_BOTTOM + if constexpr (GET_KEY) { + assert(p_index_key); + p_index_key->set(iter.get_key()); + } else { + assert(!p_index_key); + } return false; } } diff --git a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc index c0c0d9c96d877..384e824b22ec8 100644 --- a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc +++ b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc @@ -716,8 +716,6 @@ class DummyChildPool { ceph_abort("impossible path"); } key_view_t get_key_view(const search_position_t&) const override { ceph_abort("impossible path"); } - void next_position(search_position_t&) const override { - ceph_abort("impossible path"); } node_stats_t get_stats() const override { ceph_abort("impossible path"); } std::ostream& dump(std::ostream&) const override { -- 2.39.5