From 35ff3af36240afb4b13cea6243e53fcfd97863a2 Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Tue, 15 Sep 2020 14:07:05 +0800 Subject: [PATCH] crimson/onode-staged-tree: decouple Node and Layout classes * Implement has-a relationship between Node and NodeImpl classes; * Implement NodeLayoutT for templated Layout implementations; * Reorganize cross-node logic into Node classes; * Update tests with the new dependencies; * MISC related cleanup; Signed-off-by: Yingxin Cheng --- src/crimson/os/seastore/CMakeLists.txt | 3 +- .../onode_manager/staged-fltree/fwd.h | 15 +- .../onode_manager/staged-fltree/node.cc | 615 +++++++++++++-- .../onode_manager/staged-fltree/node.h | 404 ++++------ .../staged-fltree/node_extent_manager.h | 7 +- .../staged-fltree/node_extent_manager/dummy.h | 10 +- .../node_extent_manager/seastore.h | 12 +- .../staged-fltree/node_extent_visitor.h | 104 +-- .../onode_manager/staged-fltree/node_impl.cc | 72 ++ .../onode_manager/staged-fltree/node_impl.h | 734 +++--------------- .../onode_manager/staged-fltree/node_layout.h | 344 ++++++++ ..._replayable.h => node_layout_replayable.h} | 11 +- .../onode_manager/staged-fltree/node_types.h | 2 - .../staged-fltree/stages/key_layout.h | 8 +- .../staged-fltree/stages/node_stage.cc | 2 +- .../{node_layout.cc => node_stage_layout.cc} | 2 +- .../{node_layout.h => node_stage_layout.h} | 0 .../staged-fltree/stages/stage.h | 156 ++-- .../staged-fltree/stages/stage_types.h | 52 ++ .../seastore/onode_tree/test_staged_fltree.cc | 194 +++-- 20 files changed, 1529 insertions(+), 1218 deletions(-) create mode 100644 src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.cc create mode 100644 src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h rename src/crimson/os/seastore/onode_manager/staged-fltree/{node_impl_replayable.h => node_layout_replayable.h} (87%) rename src/crimson/os/seastore/onode_manager/staged-fltree/stages/{node_layout.cc => node_stage_layout.cc} (99%) rename src/crimson/os/seastore/onode_manager/staged-fltree/stages/{node_layout.h => node_stage_layout.h} (100%) diff --git a/src/crimson/os/seastore/CMakeLists.txt b/src/crimson/os/seastore/CMakeLists.txt index f13d7b5cb4c66..a486e0fc89f03 100644 --- a/src/crimson/os/seastore/CMakeLists.txt +++ b/src/crimson/os/seastore/CMakeLists.txt @@ -18,9 +18,10 @@ add_library(crimson-seastore STATIC onode_manager/staged-fltree/node.cc onode_manager/staged-fltree/node_extent_manager.cc onode_manager/staged-fltree/node_extent_mutable.cc + onode_manager/staged-fltree/node_impl.cc onode_manager/staged-fltree/stages/item_iterator_stage.cc onode_manager/staged-fltree/stages/key_layout.cc - onode_manager/staged-fltree/stages/node_layout.cc + onode_manager/staged-fltree/stages/node_stage_layout.cc onode_manager/staged-fltree/stages/node_stage.cc onode_manager/staged-fltree/stages/sub_items_stage.cc onode_manager/staged-fltree/super.cc diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h b/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h index f66fe57c1ff5c..c25d92fb8de50 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h @@ -10,6 +10,7 @@ #include #include "crimson/common/errorator.h" +#include "crimson/os/seastore/cached_extent.h" #include "crimson/os/seastore/seastore_types.h" #include "crimson/os/seastore/transaction.h" @@ -23,15 +24,25 @@ using crimson::os::seastore::L_ADDR_MIN; using crimson::os::seastore::L_ADDR_NULL; using crimson::os::seastore::extent_len_t; +class NodeExtent; class NodeExtentManager; class RootNodeTracker; +using NodeExtentRef = crimson::os::seastore::TCachedExtentRef; +using NodeExtentManagerURef = std::unique_ptr; +using RootNodeTrackerURef = std::unique_ptr; struct context_t { NodeExtentManager& nm; Transaction& t; }; -using NodeExtentManagerURef = std::unique_ptr; -using RootNodeTrackerURef = std::unique_ptr; +class LeafNodeImpl; +class InternalNodeImpl; +class NodeImpl; +using LeafNodeImplURef = std::unique_ptr; +using InternalNodeImplURef = std::unique_ptr; +using NodeImplURef = std::unique_ptr; + +using level_t = uint8_t; constexpr auto INDEX_END = std::numeric_limits::max(); // TODO: decide by NODE_BLOCK_SIZE 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 e6fcb382530b7..0af1fda5ae662 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc @@ -5,8 +5,12 @@ #include #include +#include +#include "common/likely.h" +#include "node_extent_manager.h" #include "node_impl.h" +#include "stages/node_stage_layout.h" namespace crimson::os::seastore::onode { @@ -14,6 +18,10 @@ using node_ertr = Node::node_ertr; template using node_future = Node::node_future; +/* + * tree_cursor_t + */ + tree_cursor_t::tree_cursor_t( Ref node, const search_position_t& pos, const onode_t* p_value) : leaf_node{node}, position{pos}, p_value{p_value} { @@ -30,6 +38,16 @@ tree_cursor_t::~tree_cursor_t() { } } +const onode_t* tree_cursor_t::get_p_value() const { + assert(!is_end()); + if (!p_value) { + // NOTE: the leaf node is always present when we hold its reference. + p_value = leaf_node->get_p_value(position); + } + assert(p_value); + return p_value; +} + void tree_cursor_t::update_track( Ref node, const search_position_t& pos) { // already untracked @@ -42,16 +60,20 @@ void tree_cursor_t::update_track( leaf_node->do_track_cursor(*this); } -const onode_t* tree_cursor_t::get_p_value() const { - assert(!is_end()); +void tree_cursor_t::set_p_value(const onode_t* _p_value) { if (!p_value) { - // NOTE: the leaf node is always present when we hold its reference. - p_value = leaf_node->get_p_value(position); + p_value = _p_value; + } else { + assert(p_value == _p_value); } - assert(p_value); - return p_value; } +/* + * Node + */ + +Node::Node(NodeImplURef&& impl) : impl{std::move(impl)} {} + Node::~Node() { // XXX: tolerate failure between allocate() and as_child() if (is_root()) { @@ -61,41 +83,24 @@ Node::~Node() { } } -node_future<> Node::upgrade_root(context_t c) { - assert(is_root()); - assert(is_level_tail()); - assert(field_type() == field_type_t::N0); - super->do_untrack_root(*this); - return InternalNode0::allocate_root(c, level(), laddr(), std::move(super) - ).safe_then([this](auto new_root) { - as_child(search_position_t::end(), new_root); - }); +level_t Node::level() const { + return impl->level(); } -template -void Node::as_child(const search_position_t& pos, Ref parent_node) { - assert(!super); - _parent_info = parent_info_t{pos, parent_node}; - parent_info().ptr->do_track_child(*this); -} -template void Node::as_child(const search_position_t&, Ref); -template void Node::as_child(const search_position_t&, Ref); - - -node_future -Node::lower_bound(context_t c, const key_hobj_t& key) { +node_future Node::lower_bound( + context_t c, const key_hobj_t& key) { return seastar::do_with( MatchHistory(), [this, c, &key](auto& history) { - return do_lower_bound(c, key, history); + return lower_bound_tracked(c, key, history); } ); } -node_future, bool>> -Node::insert(context_t c, const key_hobj_t& key, const onode_t& value) { +node_future, bool>> Node::insert( + context_t c, const key_hobj_t& key, const onode_t& value) { return seastar::do_with( MatchHistory(), [this, c, &key, &value](auto& history) { - return do_lower_bound(c, key, history + return lower_bound_tracked(c, key, history ).safe_then([c, &key, &value, &history](auto result) { if (result.match == MatchKindBS::EQ) { return node_ertr::make_ready_future, bool>>( @@ -114,20 +119,34 @@ Node::insert(context_t c, const key_hobj_t& key, const onode_t& value) { ); } +std::ostream& Node::dump(std::ostream& os) const { + return impl->dump(os); +} + +std::ostream& Node::dump_brief(std::ostream& os) const { + return impl->dump_brief(os); +} + +void Node::test_make_destructable( + context_t c, NodeExtentMutable& mut, Super::URef&& _super) { + impl->test_set_tail(mut); + make_root(c, std::move(_super)); +} + node_future<> Node::mkfs(context_t c, RootNodeTracker& root_tracker) { - return LeafNode0::mkfs(c, root_tracker); + return LeafNode::allocate_root(c, root_tracker + ).safe_then([](auto ret) { /* FIXME: discard_result(); */ }); } -node_future> -Node::load_root(context_t c, RootNodeTracker& root_tracker) { +node_future> Node::load_root(context_t c, RootNodeTracker& root_tracker) { return c.nm.get_super(c.t, root_tracker ).safe_then([c, &root_tracker](auto&& _super) { auto root_addr = _super->get_root_laddr(); assert(root_addr != L_ADDR_NULL); - return load_node(c, root_addr, true + return Node::load(c, root_addr, true ).safe_then([c, _super = std::move(_super), &root_tracker](auto root) mutable { - assert(root->field_type() == field_type_t::N0); + assert(root->impl->field_type() == field_type_t::N0); root->as_root(std::move(_super)); assert(root == root_tracker.get_root(c.t)); return node_ertr::make_ready_future>(root); @@ -135,12 +154,221 @@ Node::load_root(context_t c, RootNodeTracker& root_tracker) { }); } +void Node::make_root(context_t c, Super::URef&& _super) { + _super->write_root_laddr(c, impl->laddr()); + as_root(std::move(_super)); +} + +void Node::as_root(Super::URef&& _super) { + assert(!super && !_parent_info); + assert(_super->get_root_laddr() == impl->laddr()); + assert(impl->is_level_tail()); + super = std::move(_super); + super->do_track_root(*this); +} + +node_future<> Node::upgrade_root(context_t c) { + assert(is_root()); + assert(impl->is_level_tail()); + assert(impl->field_type() == field_type_t::N0); + super->do_untrack_root(*this); + return InternalNode::allocate_root(c, impl->level(), impl->laddr(), std::move(super) + ).safe_then([this](auto new_root) { + as_child(search_position_t::end(), new_root); + }); +} + +template +void Node::as_child(const search_position_t& pos, Ref parent_node) { + assert(!super); + _parent_info = parent_info_t{pos, parent_node}; + parent_info().ptr->do_track_child(*this); +} +template void Node::as_child(const search_position_t&, Ref); +template void Node::as_child(const search_position_t&, Ref); + node_future<> Node::insert_parent(context_t c, Ref right_node) { assert(!is_root()); // TODO(cross-node string dedup) - auto my_key = get_largest_key_view(); return parent_info().ptr->apply_child_split( - c, parent_info().position, my_key, this, right_node); + c, parent_info().position, this, right_node); +} + +node_future> Node::load( + context_t c, laddr_t addr, bool expect_is_level_tail) { + // NOTE: + // *option1: all types of node have the same length; + // option2: length is defined by node/field types; + // option3: length is totally flexible; + return c.nm.read_extent(c.t, addr, NODE_BLOCK_SIZE + ).safe_then([expect_is_level_tail](auto extent) { + const auto header = reinterpret_cast(extent->get_read()); + auto node_type = header->get_node_type(); + auto field_type = header->get_field_type(); + if (!field_type.has_value()) { + throw std::runtime_error("load failed: bad field type"); + } + if (node_type == node_type_t::LEAF) { + auto impl = LeafNodeImpl::load(extent, *field_type, expect_is_level_tail); + return Ref(new LeafNode(impl.get(), std::move(impl))); + } else if (node_type == node_type_t::INTERNAL) { + auto impl = InternalNodeImpl::load(extent, *field_type, expect_is_level_tail); + return Ref(new InternalNode(impl.get(), std::move(impl))); + } else { + assert(false && "impossible path"); + } + }); +} + +/* + * InternalNode + */ + +InternalNode::InternalNode(InternalNodeImpl* impl, NodeImplURef&& impl_ref) + : Node(std::move(impl_ref)), impl{impl} {} + +node_future<> InternalNode::apply_child_split( + context_t c, const search_position_t& pos, + Ref left_child, Ref right_child) { +#ifndef NDEBUG + if (pos.is_end()) { + assert(impl->is_level_tail()); + } +#endif + impl->prepare_mutate(c); + + // update pos => left_child to pos => right_child + auto left_child_addr = left_child->impl->laddr(); + auto right_child_addr = right_child->impl->laddr(); + impl->replace_child_addr(pos, right_child_addr, left_child_addr); + replace_track(pos, right_child, left_child); + + auto left_key = left_child->impl->get_largest_key_view(); + search_position_t insert_pos = pos; + auto [insert_stage, insert_size] = impl->evaluate_insert( + left_key, left_child_addr, insert_pos); + auto free_size = impl->free_size(); + if (free_size >= insert_size) { + // insert + auto p_value = impl->insert(left_key, left_child_addr, + insert_pos, insert_stage, insert_size); + assert(impl->free_size() == free_size - insert_size); + assert(insert_pos <= pos); + assert(*p_value == left_child_addr); + track_insert(insert_pos, insert_stage, left_child, right_child); + validate_tracked_children(); + return node_ertr::now(); + } + // split and insert + std::cout << " try insert at: " << insert_pos + << ", insert_stage=" << (int)insert_stage + << ", insert_size=" << insert_size + << ", values=0x" << std::hex << left_child_addr + << ",0x" << right_child_addr << std::dec << std::endl; + Ref this_ref = this; + return (is_root() ? upgrade_root(c) : node_ertr::now() + ).safe_then([this, c] { + return InternalNode::allocate( + c, impl->field_type(), impl->is_level_tail(), impl->level()); + }).safe_then([this_ref, this, c, left_key, left_child, right_child, + insert_pos, insert_stage, insert_size](auto fresh_right) mutable { + auto right_node = fresh_right.node; + auto left_child_addr = left_child->impl->laddr(); + auto [split_pos, is_insert_left, p_value] = impl->split_insert( + fresh_right.mut, *right_node->impl, left_key, left_child_addr, + insert_pos, insert_stage, insert_size); + assert(*p_value == left_child_addr); + track_split(split_pos, right_node); + if (is_insert_left) { + track_insert(insert_pos, insert_stage, left_child); + } else { + right_node->track_insert(insert_pos, insert_stage, left_child); + } + validate_tracked_children(); + right_node->validate_tracked_children(); + + // propagate index to parent + return insert_parent(c, right_node); + // TODO (optimize) + // try to acquire space from siblings before split... see btrfs + }); +} + +node_future> InternalNode::allocate_root( + context_t c, level_t old_root_level, + laddr_t old_root_addr, Super::URef&& super) { + return InternalNode::allocate(c, field_type_t::N0, true, old_root_level + 1 + ).safe_then([c, old_root_addr, + super = std::move(super)](auto fresh_node) mutable { + auto root = fresh_node.node; + const laddr_t* p_value = root->impl->get_p_value(search_position_t::end()); + fresh_node.mut.copy_in_absolute( + const_cast(p_value), old_root_addr); + root->make_root_from(c, std::move(super), old_root_addr); + return root; + }); +} + +node_future> +InternalNode::lookup_smallest(context_t c) { + auto position = search_position_t::begin(); + laddr_t child_addr = *impl->get_p_value(position); + return get_or_track_child(c, position, child_addr + ).safe_then([c](auto child) { + return child->lookup_smallest(c); + }); +} + +node_future> +InternalNode::lookup_largest(context_t c) { + // NOTE: unlike LeafNode::lookup_largest(), this only works for the tail + // internal node to return the tail child address. + auto position = search_position_t::end(); + laddr_t child_addr = *impl->get_p_value(position); + return get_or_track_child(c, position, child_addr).safe_then([c](auto child) { + return child->lookup_largest(c); + }); +} + +node_future +InternalNode::lower_bound_tracked( + context_t c, const key_hobj_t& key, MatchHistory& history) { + auto result = impl->lower_bound(key, history); + return get_or_track_child(c, result.position, *result.p_value + ).safe_then([c, &key, &history](auto child) { + // XXX(multi-type): pass result.mstat to child + return child->lower_bound_tracked(c, key, history); + }); +} + +node_future<> InternalNode::test_clone_root( + context_t c_other, RootNodeTracker& tracker_other) const { + assert(is_root()); + assert(impl->is_level_tail()); + assert(impl->field_type() == field_type_t::N0); + Ref this_ref = this; + return InternalNode::allocate(c_other, field_type_t::N0, true, impl->level() + ).safe_then([this, c_other, &tracker_other](auto fresh_other) { + impl->test_copy_to(fresh_other.mut); + auto cloned_root = fresh_other.node; + return c_other.nm.get_super(c_other.t, tracker_other + ).safe_then([c_other, cloned_root](auto&& super_other) { + cloned_root->make_root_new(c_other, std::move(super_other)); + return cloned_root; + }); + }).safe_then([this_ref, this, c_other](auto cloned_root) { + // clone tracked children + // In some unit tests, the children are stubbed out that they + // don't exist in NodeExtentManager, and are only tracked in memory. + return crimson::do_for_each( + tracked_child_nodes.begin(), + tracked_child_nodes.end(), + [this_ref, c_other, cloned_root](auto& kv) { + assert(kv.first == kv.second->parent_info().position); + return kv.second->test_clone_non_root(c_other, cloned_root); + } + ); + }); } node_future> InternalNode::get_or_track_child( @@ -148,37 +376,328 @@ node_future> InternalNode::get_or_track_child( bool level_tail = position.is_end(); Ref child; auto found = tracked_child_nodes.find(position); + Ref this_ref = this; return (found == tracked_child_nodes.end() - ? load_node(c, child_addr, level_tail + ? Node::load(c, child_addr, level_tail ).safe_then([this, position] (auto child) { child->as_child(position, this); return child; }) : node_ertr::make_ready_future>(found->second) - ).safe_then([this, position, child_addr] (auto child) { - assert(child_addr == child->laddr()); + ).safe_then([this_ref, this, position, child_addr] (auto child) { + assert(child_addr == child->impl->laddr()); assert(position == child->parent_info().position); validate_child(*child); return child; }); } +void InternalNode::track_insert( + const search_position_t& insert_pos, match_stage_t insert_stage, + Ref insert_child, Ref nxt_child) { + // update tracks + auto pos_upper_bound = insert_pos; + pos_upper_bound.index_by_stage(insert_stage) = INDEX_END; + auto first = tracked_child_nodes.lower_bound(insert_pos); + auto last = tracked_child_nodes.lower_bound(pos_upper_bound); + std::vector nodes; + std::for_each(first, last, [&nodes](auto& kv) { + nodes.push_back(kv.second); + }); + tracked_child_nodes.erase(first, last); + for (auto& node : nodes) { + auto _pos = node->parent_info().position; + assert(!_pos.is_end()); + ++_pos.index_by_stage(insert_stage); + node->as_child(_pos, this); + } + // track insert + insert_child->as_child(insert_pos, this); + +#ifndef NDEBUG + // validate left_child is before right_child + if (nxt_child) { + auto iter = tracked_child_nodes.find(insert_pos); + ++iter; + assert(iter->second == nxt_child); + } +#endif +} + +void InternalNode::replace_track( + const search_position_t& position, Ref new_child, Ref old_child) { + assert(tracked_child_nodes[position] == old_child); + tracked_child_nodes.erase(position); + new_child->as_child(position, this); + assert(tracked_child_nodes[position] == new_child); +} + +void InternalNode::track_split( + const search_position_t& split_pos, Ref right_node) { + auto first = tracked_child_nodes.lower_bound(split_pos); + auto iter = first; + while (iter != tracked_child_nodes.end()) { + search_position_t new_pos = iter->first; + new_pos -= split_pos; + iter->second->as_child(new_pos, right_node); + ++iter; + } + tracked_child_nodes.erase(first, tracked_child_nodes.end()); +} + void InternalNode::validate_child(const Node& child) const { #ifndef NDEBUG - assert(this->level() - 1 == child.level()); + assert(impl->level() - 1 == child.impl->level()); assert(this == child.parent_info().ptr); auto& child_pos = child.parent_info().position; - assert(*get_p_value(child_pos) == child.laddr()); + assert(*impl->get_p_value(child_pos) == child.impl->laddr()); if (child_pos.is_end()) { - assert(this->is_level_tail()); - assert(child.is_level_tail()); + assert(impl->is_level_tail()); + assert(child.impl->is_level_tail()); } else { - assert(!child.is_level_tail()); - assert(get_key_view(child_pos) == child.get_largest_key_view()); + assert(!child.impl->is_level_tail()); + assert(impl->get_key_view(child_pos) == child.impl->get_largest_key_view()); } // XXX(multi-type) - assert(this->field_type() <= child.field_type()); + assert(impl->field_type() <= child.impl->field_type()); #endif } +node_future InternalNode::allocate( + context_t c, field_type_t field_type, bool is_level_tail, level_t level) { + return InternalNodeImpl::allocate(c, field_type, is_level_tail, level + ).safe_then([](auto&& fresh_impl) { + auto node = Ref(new InternalNode( + fresh_impl.impl.get(), std::move(fresh_impl.impl))); + return fresh_node_t{node, fresh_impl.mut}; + }); +} + +/* + * LeafNode + */ + +LeafNode::LeafNode(LeafNodeImpl* impl, NodeImplURef&& impl_ref) + : Node(std::move(impl_ref)), impl{impl} {} + +const onode_t* LeafNode::get_p_value(const search_position_t& pos) const { + return impl->get_p_value(pos); +} + +node_future> +LeafNode::lookup_smallest(context_t) { + search_position_t pos; + const onode_t* p_value; + if (unlikely(impl->is_empty())) { + assert(is_root()); + pos = search_position_t::end(); + p_value = nullptr; + } else { + pos = search_position_t::begin(); + p_value = impl->get_p_value(pos); + } + return node_ertr::make_ready_future>( + get_or_track_cursor(pos, p_value)); +} + +node_future> +LeafNode::lookup_largest(context_t) { + search_position_t pos; + const onode_t* p_value = nullptr; + if (unlikely(impl->is_empty())) { + assert(is_root()); + pos = search_position_t::end(); + } else { + impl->get_largest_value(pos, p_value); + assert(p_value != nullptr); + } + return node_ertr::make_ready_future>( + get_or_track_cursor(pos, p_value)); +} + +node_future +LeafNode::lower_bound_tracked( + context_t c, const key_hobj_t& key, MatchHistory& history) { + auto result = impl->lower_bound(key, history); + auto cursor_ref = get_or_track_cursor(result.position, result.p_value); + return node_ertr::make_ready_future( + search_result_t{cursor_ref, result.match()}); +} + +node_future<> LeafNode::test_clone_root( + context_t c_other, RootNodeTracker& tracker_other) const { + assert(is_root()); + assert(impl->is_level_tail()); + assert(impl->field_type() == field_type_t::N0); + Ref this_ref = this; + return LeafNode::allocate(c_other, field_type_t::N0, true + ).safe_then([this, c_other, &tracker_other](auto fresh_other) { + impl->test_copy_to(fresh_other.mut); + auto cloned_root = fresh_other.node; + return c_other.nm.get_super(c_other.t, tracker_other + ).safe_then([c_other, cloned_root](auto&& super_other) { + cloned_root->make_root_new(c_other, std::move(super_other)); + }); + }).safe_then([this_ref]{}); +} + +node_future> LeafNode::insert_value( + context_t c, const key_hobj_t& key, const onode_t& value, + const search_position_t& pos, const MatchHistory& history) { +#ifndef NDEBUG + if (pos.is_end()) { + assert(impl->is_level_tail()); + } +#endif + impl->prepare_mutate(c); + + search_position_t insert_pos = pos; + auto [insert_stage, insert_size] = impl->evaluate_insert( + key, value, history, insert_pos); + auto free_size = impl->free_size(); + if (free_size >= insert_size) { + // insert + auto p_value = impl->insert(key, value, insert_pos, insert_stage, insert_size); + assert(impl->free_size() == free_size - insert_size); + assert(insert_pos <= pos); + assert(p_value->size == value.size); + auto ret = track_insert(insert_pos, insert_stage, p_value); + validate_tracked_cursors(); + return node_ertr::make_ready_future>(ret); + } + // split and insert + std::cout << " try insert at: " << insert_pos + << ", insert_stage=" << (int)insert_stage + << ", insert_size=" << insert_size + << std::endl; + Ref this_ref = this; + return (is_root() ? upgrade_root(c) : node_ertr::now() + ).safe_then([this, c] { + return LeafNode::allocate(c, impl->field_type(), impl->is_level_tail()); + }).safe_then([this_ref, this, c, &key, &value, &history, + insert_pos, insert_stage, insert_size](auto fresh_right) mutable { + auto right_node = fresh_right.node; + auto [split_pos, is_insert_left, p_value] = impl->split_insert( + fresh_right.mut, *right_node->impl, key, value, + insert_pos, insert_stage, insert_size); + assert(p_value->size == value.size); + track_split(split_pos, right_node); + Ref ret; + if (is_insert_left) { + ret = track_insert(insert_pos, insert_stage, p_value); + } else { + ret = right_node->track_insert(insert_pos, insert_stage, p_value); + } + validate_tracked_cursors(); + right_node->validate_tracked_cursors(); + + // propagate insert to parent + return insert_parent(c, right_node).safe_then([ret] { + return ret; + }); + // TODO (optimize) + // try to acquire space from siblings before split... see btrfs + }); +} + +node_future> LeafNode::allocate_root( + context_t c, RootNodeTracker& root_tracker) { + return LeafNode::allocate(c, field_type_t::N0, true + ).safe_then([c, &root_tracker](auto fresh_node) { + auto root = fresh_node.node; + return c.nm.get_super(c.t, root_tracker + ).safe_then([c, root](auto&& super) { + root->make_root_new(c, std::move(super)); + return root; + }); + }); +} + +Ref LeafNode::get_or_track_cursor( + const search_position_t& position, const onode_t* p_value) { + if (position.is_end()) { + assert(impl->is_level_tail()); + assert(!p_value); + // we need to return the leaf node to insert + return new tree_cursor_t(this, position, p_value); + } + + Ref p_cursor; + auto found = tracked_cursors.find(position); + if (found == tracked_cursors.end()) { + p_cursor = new tree_cursor_t(this, position, p_value); + } else { + p_cursor = found->second; + assert(p_cursor->get_leaf_node() == this); + assert(p_cursor->get_position() == position); + p_cursor->set_p_value(p_value); + } + return p_cursor; +} + +Ref LeafNode::track_insert( + const search_position_t& insert_pos, match_stage_t insert_stage, + const onode_t* p_onode) { + // invalidate cursor value + // TODO: version based invalidation + auto pos_invalidate_begin = insert_pos; + pos_invalidate_begin.index_by_stage(STAGE_RIGHT) = 0; + auto begin_invalidate = tracked_cursors.lower_bound(pos_invalidate_begin); + std::for_each(begin_invalidate, tracked_cursors.end(), [](auto& kv) { + kv.second->invalidate_p_value(); + }); + + // update cursor position + auto pos_upper_bound = insert_pos; + pos_upper_bound.index_by_stage(insert_stage) = INDEX_END; + auto first = tracked_cursors.lower_bound(insert_pos); + auto last = tracked_cursors.lower_bound(pos_upper_bound); + std::vector p_cursors; + std::for_each(first, last, [&p_cursors](auto& kv) { + p_cursors.push_back(kv.second); + }); + tracked_cursors.erase(first, last); + for (auto& p_cursor : p_cursors) { + search_position_t new_pos = p_cursor->get_position(); + ++new_pos.index_by_stage(insert_stage); + p_cursor->update_track(this, new_pos); + } + + // track insert + return new tree_cursor_t(this, insert_pos, p_onode); +} + +void LeafNode::track_split( + const search_position_t& split_pos, Ref right_node) { + // invalidate cursor value + // TODO: version based invalidation + auto pos_invalidate_begin = split_pos; + pos_invalidate_begin.index_by_stage(STAGE_RIGHT) = 0; + auto begin_invalidate = tracked_cursors.lower_bound(pos_invalidate_begin); + std::for_each(begin_invalidate, tracked_cursors.end(), [](auto& kv) { + kv.second->invalidate_p_value(); + }); + + // update cursor ownership and position + auto first = tracked_cursors.lower_bound(split_pos); + auto iter = first; + while (iter != tracked_cursors.end()) { + search_position_t new_pos = iter->first; + new_pos -= split_pos; + iter->second->update_track(right_node, new_pos); + ++iter; + } + tracked_cursors.erase(first, tracked_cursors.end()); +} + +node_future LeafNode::allocate( + context_t c, field_type_t field_type, bool is_level_tail) { + return LeafNodeImpl::allocate(c, field_type, is_level_tail + ).safe_then([](auto&& fresh_impl) { + auto node = Ref(new LeafNode( + fresh_impl.impl.get(), std::move(fresh_impl.impl))); + return fresh_node_t{node, fresh_impl.mut}; + }); +} + } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h index c1c96eb5bbbb9..60a437d81b42a 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h @@ -4,12 +4,13 @@ #pragma once #include +#include #include #include #include "crimson/common/type_helpers.h" -#include "node_types.h" +#include "node_extent_mutable.h" #include "stages/stage_types.h" #include "super.h" #include "tree_types.h" @@ -33,15 +34,21 @@ namespace crimson::os::seastore::onode { * LeafNode --> tree_cursor_t* */ +struct key_hobj_t; class LeafNode; class InternalNode; -class NodeExtentMutable; class tree_cursor_t final : public boost::intrusive_ref_counter< - tree_cursor_t, boost::thread_unsafe_counter> { + tree_cursor_t, boost::thread_unsafe_counter> { public: + // public to Btree ~tree_cursor_t(); + tree_cursor_t(const tree_cursor_t&) = delete; + tree_cursor_t(tree_cursor_t&&) = delete; + tree_cursor_t& operator=(const tree_cursor_t&) = delete; + tree_cursor_t& operator=(tree_cursor_t&&) = delete; + bool is_end() const { return position.is_end(); } const onode_t* get_p_value() const; @@ -52,14 +59,9 @@ class tree_cursor_t final // TODO: version based invalidation void invalidate_p_value() { p_value = nullptr; } void update_track(Ref, const search_position_t&); - void set_p_value(const onode_t* _p_value) { - if (!p_value) { - p_value = _p_value; - } else { - assert(p_value == _p_value); - } - } + void set_p_value(const onode_t* _p_value); + private: Ref leaf_node; search_position_t position; mutable const onode_t* p_value; @@ -68,12 +70,11 @@ class tree_cursor_t final friend class Node; // get_position(), get_leaf_node() }; -struct key_view_t; -struct key_hobj_t; - class Node - : public boost::intrusive_ref_counter { + : public boost::intrusive_ref_counter< + Node, boost::thread_unsafe_counter> { public: + // public to Btree using node_ertr = crimson::errorator< crimson::ct_error::input_output_error, crimson::ct_error::invarg, @@ -81,7 +82,6 @@ class Node crimson::ct_error::erange>; template using node_future = node_ertr::future; - struct search_result_t { bool is_end() const { return p_cursor->is_end(); } Ref p_cursor; @@ -89,55 +89,43 @@ class Node }; virtual ~Node(); - virtual level_t level() const = 0; + Node(const Node&) = delete; + Node(Node&&) = delete; + Node& operator=(const Node&) = delete; + Node& operator=(Node&&) = delete; + + level_t level() const; virtual node_future> lookup_smallest(context_t) = 0; virtual node_future> lookup_largest(context_t) = 0; - node_future lower_bound(context_t, const key_hobj_t& key); - - node_future, bool>> - insert(context_t, const key_hobj_t&, const onode_t&); + node_future lower_bound(context_t c, const key_hobj_t& key); + node_future, bool>> insert( + context_t, const key_hobj_t&, const onode_t&); + std::ostream& dump(std::ostream&) const; + std::ostream& dump_brief(std::ostream&) const; - virtual std::ostream& dump(std::ostream&) const = 0; - virtual std::ostream& dump_brief(std::ostream&) const = 0; + void test_make_destructable(context_t, NodeExtentMutable&, Super::URef&&); + virtual node_future<> test_clone_root(context_t, RootNodeTracker&) const = 0; static node_future<> mkfs(context_t, RootNodeTracker&); - static node_future> load_root(context_t, RootNodeTracker&); - virtual void test_make_destructable( - context_t, NodeExtentMutable&, Super::URef&&) = 0; - virtual node_future<> test_clone_root(context_t, RootNodeTracker&) const { - assert(false && "impossible path"); - } + protected: virtual node_future<> test_clone_non_root(context_t, Ref) const { assert(false && "impossible path"); } - - public: // used by node_impl.h, XXX: protected? - virtual bool is_level_tail() const = 0; - virtual field_type_t field_type() const = 0; - virtual laddr_t laddr() 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 node_future - do_lower_bound(context_t, const key_hobj_t&, MatchHistory&) = 0; + virtual node_future lower_bound_tracked( + context_t, const key_hobj_t&, MatchHistory&) = 0; protected: - Node() {} - - struct parent_info_t { - search_position_t position; - Ref ptr; - }; + Node(NodeImplURef&&); bool is_root() const { assert((super && !_parent_info.has_value()) || (!super && _parent_info.has_value())); return !_parent_info.has_value(); } - void make_root(context_t c, Super::URef&& _super) { - _super->write_root_laddr(c, laddr()); - as_root(std::move(_super)); - } + + // as root + void make_root(context_t c, Super::URef&& _super); void make_root_new(context_t c, Super::URef&& _super) { assert(_super->get_root_laddr() == L_ADDR_NULL); make_root(c, std::move(_super)); @@ -146,126 +134,47 @@ class Node assert(_super->get_root_laddr() == from_addr); make_root(c, std::move(_super)); } - void as_root(Super::URef&& _super) { - assert(!super && !_parent_info); - assert(_super->get_root_laddr() == laddr()); - assert(is_level_tail()); - super = std::move(_super); - super->do_track_root(*this); - } + void as_root(Super::URef&& _super); node_future<> upgrade_root(context_t); + + // as child/non-root template void as_child(const search_position_t&, Ref); + struct parent_info_t { + search_position_t position; + Ref ptr; + }; const parent_info_t& parent_info() const { return *_parent_info; } node_future<> insert_parent(context_t, Ref right_node); - static node_future> load( - context_t, laddr_t, bool expect_is_level_tail); - private: - // as child/non-root - std::optional _parent_info; // as root Super::URef super; + // as child/non-root + std::optional _parent_info; + private: + static node_future> load(context_t, laddr_t, bool expect_is_level_tail); + + NodeImplURef impl; friend class InternalNode; }; inline std::ostream& operator<<(std::ostream& os, const Node& node) { return node.dump_brief(os); } -// TODO: remove virtual inheritance once decoupled with layout -class InternalNode : virtual public Node { +class InternalNode final : public Node { public: - virtual ~InternalNode() { assert(tracked_child_nodes.empty()); } - - protected: - // XXX: extract a common tracker for InternalNode to track Node, - // and LeafNode to track tree_cursor_t. - node_future> get_or_track_child( - context_t, const search_position_t&, laddr_t); - - void track_insert( - const search_position_t& insert_pos, match_stage_t insert_stage, - Ref insert_child, Ref nxt_child = nullptr) { - // update tracks - auto pos_upper_bound = insert_pos; - pos_upper_bound.index_by_stage(insert_stage) = INDEX_END; - auto first = tracked_child_nodes.lower_bound(insert_pos); - auto last = tracked_child_nodes.lower_bound(pos_upper_bound); - std::vector nodes; - std::for_each(first, last, [&nodes](auto& kv) { - nodes.push_back(kv.second); - }); - tracked_child_nodes.erase(first, last); - for (auto& node : nodes) { - auto _pos = node->parent_info().position; - assert(!_pos.is_end()); - ++_pos.index_by_stage(insert_stage); - node->as_child(_pos, this); - } - // track insert - insert_child->as_child(insert_pos, this); - -#ifndef NDEBUG - // validate left_child is before right_child - if (nxt_child) { - auto iter = tracked_child_nodes.find(insert_pos); - ++iter; - assert(iter->second == nxt_child); - } -#endif - } - - void replace_track( - const search_position_t& position, - Ref old_child, Ref new_child) { - assert(tracked_child_nodes[position] == old_child); - tracked_child_nodes.erase(position); - new_child->as_child(position, this); - assert(tracked_child_nodes[position] == new_child); - } - - void track_split( - const search_position_t& split_pos, Ref right_node) { - auto first = tracked_child_nodes.lower_bound(split_pos); - auto iter = first; - while (iter != tracked_child_nodes.end()) { - search_position_t new_pos = iter->first; - new_pos -= split_pos; - iter->second->as_child(new_pos, right_node); - ++iter; - } - tracked_child_nodes.erase(first, tracked_child_nodes.end()); - } - - void validate_tracked_children() const { -#ifndef NDEBUG - for (auto& kv : tracked_child_nodes) { - assert(kv.first == kv.second->parent_info().position); - validate_child(*kv.second); - } -#endif - } - - node_future<> test_clone_children( - context_t c_other, Ref clone) const { - Ref this_ref = this; - return crimson::do_for_each( - tracked_child_nodes.begin(), - tracked_child_nodes.end(), - [this_ref, c_other, clone](auto& kv) { - assert(kv.first == kv.second->parent_info().position); - return kv.second->test_clone_non_root(c_other, clone); - } - ); - } - - private: - virtual node_future<> apply_child_split( - context_t, const search_position_t&, const key_view_t&, Ref, Ref) = 0; - virtual const laddr_t* get_p_value(const search_position_t&) const = 0; - void validate_child(const Node& child) const; + // public to Node + InternalNode(InternalNodeImpl*, NodeImplURef&&); + ~InternalNode() override { assert(tracked_child_nodes.empty()); } + InternalNode(const InternalNode&) = delete; + InternalNode(InternalNode&&) = delete; + InternalNode& operator=(const InternalNode&) = delete; + InternalNode& operator=(InternalNode&&) = delete; + + node_future<> apply_child_split( + context_t, const search_position_t&, Ref left, Ref right); template void do_track_child(Node& child) { if constexpr (VALIDATE) { @@ -282,98 +191,98 @@ class InternalNode : virtual public Node { assert(removed); } - // XXX: leverage intrusive data structure to control memory overhead - // track the current living child nodes by position - std::map tracked_child_nodes; + static node_future> allocate_root( + context_t, level_t, laddr_t, Super::URef&&); - friend class Node; -}; + protected: + node_future> lookup_smallest(context_t) override; + node_future> lookup_largest(context_t) override; + node_future lower_bound_tracked( + context_t, const key_hobj_t&, MatchHistory&) override; -// TODO: remove virtual inheritance once decoupled with layout -class LeafNode : virtual public Node { - public: - virtual ~LeafNode() { assert(tracked_cursors.empty()); } + node_future<> test_clone_root(context_t, RootNodeTracker&) const override; - protected: + private: // XXX: extract a common tracker for InternalNode to track Node, // and LeafNode to track tree_cursor_t. - Ref get_or_track_cursor( - const search_position_t& position, const onode_t* p_value) { - if (position.is_end()) { - assert(this->is_level_tail()); - assert(!p_value); - // we need to return the leaf node to insert - return new tree_cursor_t(this, position, p_value); - } - - Ref p_cursor; - auto found = tracked_cursors.find(position); - if (found == tracked_cursors.end()) { - p_cursor = new tree_cursor_t(this, position, p_value); - } else { - p_cursor = found->second; - assert(p_cursor->get_leaf_node() == this); - assert(p_cursor->get_position() == position); - p_cursor->set_p_value(p_value); + node_future> get_or_track_child(context_t, const search_position_t&, laddr_t); + void track_insert( + const search_position_t&, match_stage_t, Ref, Ref nxt_child = nullptr); + void replace_track(const search_position_t&, Ref new_child, Ref old_child); + void track_split(const search_position_t&, Ref); + void validate_tracked_children() const { +#ifndef NDEBUG + for (auto& kv : tracked_child_nodes) { + assert(kv.first == kv.second->parent_info().position); + validate_child(*kv.second); } - return p_cursor; +#endif } + void validate_child(const Node& child) const; - Ref track_insert( - const search_position_t& insert_pos, match_stage_t insert_stage, - const onode_t* p_onode) { - // invalidate cursor value - // TODO: version based invalidation - auto pos_invalidate_begin = insert_pos; - pos_invalidate_begin.index_by_stage(STAGE_RIGHT) = 0; - auto begin_invalidate = tracked_cursors.lower_bound(pos_invalidate_begin); - std::for_each(begin_invalidate, tracked_cursors.end(), [](auto& kv) { - kv.second->invalidate_p_value(); - }); - - // update cursor position - auto pos_upper_bound = insert_pos; - pos_upper_bound.index_by_stage(insert_stage) = INDEX_END; - auto first = tracked_cursors.lower_bound(insert_pos); - auto last = tracked_cursors.lower_bound(pos_upper_bound); - std::vector p_cursors; - std::for_each(first, last, [&p_cursors](auto& kv) { - p_cursors.push_back(kv.second); - }); - tracked_cursors.erase(first, last); - for (auto& p_cursor : p_cursors) { - search_position_t new_pos = p_cursor->get_position(); - ++new_pos.index_by_stage(insert_stage); - p_cursor->update_track(this, new_pos); + struct fresh_node_t { + Ref node; + NodeExtentMutable mut; + std::pair, NodeExtentMutable> make_pair() { + return std::make_pair(Ref(node), mut); } + }; + static node_future allocate(context_t, field_type_t, bool, level_t); - // track insert - return new tree_cursor_t(this, insert_pos, p_onode); - } + private: + // XXX: leverage intrusive data structure to control memory overhead + // track the current living child nodes by position + std::map tracked_child_nodes; + InternalNodeImpl* impl; +}; - void track_split( - const search_position_t& split_pos, Ref right_node) { - // invalidate cursor value - // TODO: version based invalidation - auto pos_invalidate_begin = split_pos; - pos_invalidate_begin.index_by_stage(STAGE_RIGHT) = 0; - auto begin_invalidate = tracked_cursors.lower_bound(pos_invalidate_begin); - std::for_each(begin_invalidate, tracked_cursors.end(), [](auto& kv) { - kv.second->invalidate_p_value(); - }); - - // update cursor ownership and position - auto first = tracked_cursors.lower_bound(split_pos); - auto iter = first; - while (iter != tracked_cursors.end()) { - search_position_t new_pos = iter->first; - new_pos -= split_pos; - iter->second->update_track(right_node, new_pos); - ++iter; - } - tracked_cursors.erase(first, tracked_cursors.end()); +class LeafNode final : public Node { + public: + // public to tree_cursor_t + ~LeafNode() override { assert(tracked_cursors.empty()); } + LeafNode(const LeafNode&) = delete; + LeafNode(LeafNode&&) = delete; + LeafNode& operator=(const LeafNode&) = delete; + LeafNode& operator=(LeafNode&&) = delete; + + const onode_t* get_p_value(const search_position_t&) const; + void do_track_cursor(tree_cursor_t& cursor) { + validate_cursor(cursor); + auto& cursor_pos = cursor.get_position(); + assert(tracked_cursors.find(cursor_pos) == tracked_cursors.end()); + tracked_cursors[cursor_pos] = &cursor; } + void do_untrack_cursor(tree_cursor_t& cursor) { + validate_cursor(cursor); + auto& cursor_pos = cursor.get_position(); + assert(tracked_cursors.find(cursor_pos)->second == &cursor); + auto removed = tracked_cursors.erase(cursor_pos); + assert(removed); + } + + protected: + node_future> lookup_smallest(context_t) override; + node_future> lookup_largest(context_t) override; + node_future lower_bound_tracked( + context_t, const key_hobj_t&, MatchHistory&) override; + + node_future<> test_clone_root(context_t, RootNodeTracker&) const override; + + private: + LeafNode(LeafNodeImpl*, NodeImplURef&&); + node_future> insert_value( + context_t, const key_hobj_t&, const onode_t&, + const search_position_t&, const MatchHistory&); + static node_future> allocate_root(context_t, RootNodeTracker&); + friend class Node; + private: + // XXX: extract a common tracker for InternalNode to track Node, + // and LeafNode to track tree_cursor_t. + Ref get_or_track_cursor(const search_position_t&, const onode_t*); + Ref track_insert( + const search_position_t&, match_stage_t, const onode_t*); + void track_split(const search_position_t&, Ref); void validate_tracked_cursors() const { #ifndef NDEBUG for (auto& kv : tracked_cursors) { @@ -382,39 +291,26 @@ class LeafNode : virtual public Node { } #endif } - - private: - virtual node_future> insert_value( - context_t, - const key_hobj_t&, - const onode_t&, - const search_position_t&, - const MatchHistory&) = 0; - friend class Node; - - virtual const onode_t* get_p_value(const search_position_t&) const = 0; void validate_cursor(tree_cursor_t& cursor) const { assert(this == cursor.get_leaf_node().get()); assert(!cursor.is_end()); assert(get_p_value(cursor.get_position()) == cursor.get_p_value()); } - void do_track_cursor(tree_cursor_t& cursor) { - validate_cursor(cursor); - auto& cursor_pos = cursor.get_position(); - assert(tracked_cursors.find(cursor_pos) == tracked_cursors.end()); - tracked_cursors[cursor_pos] = &cursor; - } - void do_untrack_cursor(tree_cursor_t& cursor) { - validate_cursor(cursor); - auto& cursor_pos = cursor.get_position(); - assert(tracked_cursors.find(cursor_pos)->second == &cursor); - auto removed = tracked_cursors.erase(cursor_pos); - assert(removed); - } + + struct fresh_node_t { + Ref node; + NodeExtentMutable mut; + std::pair, NodeExtentMutable> make_pair() { + return std::make_pair(Ref(node), mut); + } + }; + static node_future allocate(context_t, field_type_t, bool); + + private: // XXX: leverage intrusive data structure to control memory overhead // track the current living cursors by position std::map tracked_cursors; - friend class tree_cursor_t; + LeafNodeImpl* impl; }; } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h index f5f37af4d9cdf..1973b80b15925 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h @@ -16,7 +16,6 @@ namespace crimson::os::seastore::onode { using crimson::os::seastore::LogicalCachedExtent; class NodeExtent : public LogicalCachedExtent { public: - using Ref = crimson::os::seastore::TCachedExtentRef; virtual ~NodeExtent() = default; const char* get_read() const { return get_bptr().c_str(); @@ -25,7 +24,7 @@ class NodeExtent : public LogicalCachedExtent { assert(is_pending()); return NodeExtentMutable(*this); } - virtual Ref mutate(context_t/* DeltaBuffer::Ref */) = 0; + virtual NodeExtentRef mutate(context_t/* DeltaBuffer::Ref */) = 0; protected: template @@ -56,9 +55,9 @@ class NodeExtentManager { using tm_future = tm_ertr::future; virtual bool is_read_isolated() const = 0; - virtual tm_future read_extent( + virtual tm_future read_extent( Transaction&, laddr_t, extent_len_t) = 0; - virtual tm_future alloc_extent(Transaction&, extent_len_t) = 0; + virtual tm_future alloc_extent(Transaction&, extent_len_t) = 0; virtual tm_future get_super(Transaction&, RootNodeTracker&) = 0; static NodeExtentManagerURef create_dummy(); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h index 394db8c2e109b..49c56357b56f5 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/dummy.h @@ -27,7 +27,7 @@ class DummyNodeExtent final: public NodeExtent { } ~DummyNodeExtent() override = default; protected: - Ref mutate(context_t) override { + NodeExtentRef mutate(context_t) override { assert(false && "impossible path"); } CachedExtentRef duplicate_for_write() override { assert(false && "impossible path"); } @@ -46,15 +46,15 @@ class DummyNodeExtentManager final: public NodeExtentManager { protected: bool is_read_isolated() const { return false; } - tm_future read_extent( + tm_future read_extent( Transaction& t, laddr_t addr, extent_len_t len) { auto iter = allocate_map.find(addr); assert(iter != allocate_map.end()); assert(iter->second->get_length() == len); - return tm_ertr::make_ready_future(iter->second); + return tm_ertr::make_ready_future(iter->second); } - tm_future alloc_extent( + tm_future alloc_extent( Transaction& t, extent_len_t len) { assert(len % ALIGNMENT == 0); auto r = ceph::buffer::create_aligned(len, ALIGNMENT); @@ -64,7 +64,7 @@ class DummyNodeExtentManager final: public NodeExtentManager { extent->set_laddr(addr); assert(allocate_map.find(extent->get_laddr()) == allocate_map.end()); allocate_map.insert({extent->get_laddr(), extent}); - return tm_ertr::make_ready_future(extent); + return tm_ertr::make_ready_future(extent); } tm_future get_super(Transaction& t, RootNodeTracker& tracker) { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/seastore.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/seastore.h index 0ceae18dc6761..e01cf4c534445 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/seastore.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager/seastore.h @@ -34,7 +34,7 @@ class SeastoreNodeExtent final: public NodeExtent { : NodeExtent(other) {} ~SeastoreNodeExtent() override = default; protected: - Ref mutate(context_t c) override; + NodeExtentRef mutate(context_t c) override; CachedExtentRef duplicate_for_write() override { return CachedExtentRef(new SeastoreNodeExtent(*this)); } @@ -61,21 +61,21 @@ class SeastoreNodeExtentManager final: public NodeExtentManager { protected: bool is_read_isolated() const { return true; } - tm_future read_extent( + tm_future read_extent( Transaction& t, laddr_t addr, extent_len_t len) { return tm.read_extents(t, addr, len ).safe_then([](auto&& extents) { assert(extents.size() == 1); [[maybe_unused]] auto [laddr, e] = extents.front(); - return NodeExtent::Ref(e); + return NodeExtentRef(e); }); } - tm_future alloc_extent( + tm_future alloc_extent( Transaction& t, extent_len_t len) { return tm.alloc_extent(t, addr_min, len ).safe_then([](auto extent) { - return NodeExtent::Ref(extent); + return NodeExtentRef(extent); }); } @@ -89,7 +89,7 @@ class SeastoreNodeExtentManager final: public NodeExtentManager { const laddr_t addr_min; }; -inline NodeExtent::Ref SeastoreNodeExtent::mutate(context_t c) { +inline NodeExtentRef SeastoreNodeExtent::mutate(context_t c) { auto nm = static_cast(&c.nm); auto ret = nm->get_tm().get_mutable_extent(c.t, this); return ret->cast(); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_visitor.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_visitor.h index 9607546855340..30e65a46f397b 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_visitor.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_extent_visitor.h @@ -4,18 +4,12 @@ #pragma once #include "node_extent_manager.h" -#include "node_impl_replayable.h" +#include "node_layout_replayable.h" namespace crimson::os::seastore::onode { template class NodeExtentT { - enum class state_t { - NO_RECORDING, // extent_state_t::INITIAL_WRITE_PENDING - RECORDING, // extent_state_t::MUTATION_PENDING - PENDING_MUTATE // extent_state_t::CLEAN/DIRTY - }; - public: using layout_t = NodeLayoutReplayableT; using node_stage_t = typename layout_t::node_stage_t; @@ -23,19 +17,34 @@ class NodeExtentT { using StagedIterator = typename layout_t::StagedIterator; using value_t = typename layout_t::value_t; static constexpr auto FIELD_TYPE = layout_t::FIELD_TYPE; + enum class state_t { + NO_RECORDING, // extent_state_t::INITIAL_WRITE_PENDING + RECORDING, // extent_state_t::MUTATION_PENDING + PENDING_MUTATE // extent_state_t::CLEAN/DIRTY + }; - // TODO: remove - NodeExtentT() = default; - NodeExtentT(NodeExtentT&& other) noexcept { - *this = std::move(other); - } - NodeExtentT& operator=(NodeExtentT&& other) noexcept { - extent = std::move(other.extent); - state = std::move(other.state); - node_stage = std::move(other.node_stage); - mut.emplace(*other.mut); - return *this; + NodeExtentT(state_t state, NodeExtentRef extent) + : state{state}, extent{extent}, + node_stage{reinterpret_cast(extent->get_read())} { + if (state == state_t::NO_RECORDING) { + assert(!mut.has_value()); + mut.emplace(extent->get_mutable()); + // TODO: recorder = nullptr; + } else if (state == state_t::RECORDING) { + assert(!mut.has_value()); + mut.emplace(extent->get_mutable()); + // TODO: get recorder from extent + } else if (state == state_t::PENDING_MUTATE) { + // TODO: recorder = nullptr; + } else { + ceph_abort("impossible path"); + } } + ~NodeExtentT() = default; + NodeExtentT(const NodeExtentT&) = delete; + NodeExtentT(NodeExtentT&&) = delete; + NodeExtentT& operator=(const NodeExtentT&) = delete; + NodeExtentT& operator=(NodeExtentT&&) = delete; const node_stage_t& read() const { return node_stage; } laddr_t get_laddr() const { return extent->get_laddr(); } @@ -91,14 +100,11 @@ class NodeExtentT { insert_pos, insert_stage, insert_size); } - void prepare_internal_split_replayable( - const laddr_t left_child_addr, - const laddr_t right_child_addr, - laddr_t* p_split_addr) { + void update_child_addr_replayable( + const laddr_t new_addr, laddr_t* p_addr) { assert(state != state_t::PENDING_MUTATE); // TODO: encode params to recorder as delta - return layout_t::prepare_internal_split( - *mut, read(), left_child_addr, right_child_addr, p_split_addr); + return layout_t::update_child_addr(*mut, new_addr, p_addr); } void test_copy_to(NodeExtentMutable& to) const { @@ -106,7 +112,7 @@ class NodeExtentT { std::memcpy(to.get_write(), extent->get_read(), extent->get_length()); } - static NodeExtentT load(NodeExtent::Ref extent) { + static state_t loaded(NodeExtentRef extent) { state_t state; if (extent->is_initial_pending()) { state = state_t::NO_RECORDING; @@ -117,51 +123,21 @@ class NodeExtentT { } else { ceph_abort("invalid extent"); } - return NodeExtentT(extent, state); + return state; } - struct fresh_extent_t { - NodeExtentT extent; - NodeExtentMutable mut; - }; - using alloc_ertr = NodeExtentManager::tm_ertr; - static alloc_ertr::future - allocate(context_t c, level_t level, bool is_level_tail) { - // NOTE: - // *option1: all types of node have the same length; - // option2: length is defined by node/field types; - // option3: length is totally flexible; - return c.nm.alloc_extent(c.t, node_stage_t::EXTENT_SIZE - ).safe_then([level, is_level_tail](auto extent) { - assert(extent->is_initial_pending()); - auto mut = extent->get_mutable(); - node_stage_t::bootstrap_extent( - mut, FIELD_TYPE, NODE_TYPE, is_level_tail, level); - return fresh_extent_t{NodeExtentT(extent, state_t::NO_RECORDING), mut}; - }); + static std::tuple allocated( + NodeExtentRef extent, bool is_level_tail, level_t level) { + assert(extent->is_initial_pending()); + auto mut = extent->get_mutable(); + node_stage_t::bootstrap_extent( + mut, FIELD_TYPE, NODE_TYPE, is_level_tail, level); + return {state_t::NO_RECORDING, mut}; } private: - NodeExtentT(NodeExtent::Ref extent, state_t state) - : extent{extent}, state{state}, - node_stage{reinterpret_cast(extent->get_read())} { - if (state == state_t::NO_RECORDING) { - assert(!mut.has_value()); - mut.emplace(extent->get_mutable()); - // TODO: recorder = nullptr; - } else if (state == state_t::RECORDING) { - assert(!mut.has_value()); - mut.emplace(extent->get_mutable()); - // TODO: get recorder from extent - } else if (state == state_t::PENDING_MUTATE) { - // TODO: recorder = nullptr; - } else { - ceph_abort("impossible path"); - } - } - - NodeExtent::Ref extent; state_t state; + NodeExtentRef extent; node_stage_t node_stage; std::optional mut; // TODO: DeltaRecorderT* recorder; diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.cc new file mode 100644 index 0000000000000..d26e5bc8b7b1d --- /dev/null +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl.cc @@ -0,0 +1,72 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include "node_impl.h" +#include "node_layout.h" + +namespace crimson::os::seastore::onode { + +// XXX: branchless allocation +InternalNodeImpl::alloc_ertr::future +InternalNodeImpl::allocate( + context_t c, field_type_t type, bool is_level_tail, level_t level) { + if (type == field_type_t::N0) { + return InternalNode0::allocate(c, is_level_tail, level); + } else if (type == field_type_t::N1) { + return InternalNode1::allocate(c, is_level_tail, level); + } else if (type == field_type_t::N2) { + return InternalNode2::allocate(c, is_level_tail, level); + } else if (type == field_type_t::N3) { + return InternalNode3::allocate(c, is_level_tail, level); + } else { + assert(false && "impossible path"); + } +} + +LeafNodeImpl::alloc_ertr::future +LeafNodeImpl::allocate( + context_t c, field_type_t type, bool is_level_tail) { + if (type == field_type_t::N0) { + return LeafNode0::allocate(c, is_level_tail, 0); + } else if (type == field_type_t::N1) { + return LeafNode1::allocate(c, is_level_tail, 0); + } else if (type == field_type_t::N2) { + return LeafNode2::allocate(c, is_level_tail, 0); + } else if (type == field_type_t::N3) { + return LeafNode3::allocate(c, is_level_tail, 0); + } else { + assert(false && "impossible path"); + } +} + +InternalNodeImplURef InternalNodeImpl::load( + NodeExtentRef extent, field_type_t type, bool expect_is_level_tail) { + if (type == field_type_t::N0) { + return InternalNode0::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N1) { + return InternalNode1::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N2) { + return InternalNode2::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N3) { + return InternalNode3::load(extent, expect_is_level_tail); + } else { + assert(false && "impossible path"); + } +} + +LeafNodeImplURef LeafNodeImpl::load( + NodeExtentRef extent, field_type_t type, bool expect_is_level_tail) { + if (type == field_type_t::N0) { + return LeafNode0::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N1) { + return LeafNode1::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N2) { + return LeafNode2::load(extent, expect_is_level_tail); + } else if (type == field_type_t::N3) { + return LeafNode3::load(extent, expect_is_level_tail); + } else { + assert(false && "impossible path"); + } +} + +} 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 f99c090b1631a..d39e678427032 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 @@ -3,662 +3,136 @@ #pragma once -// TODO: remove -#include #include -#include "common/likely.h" -#include "node.h" -#include "node_extent_visitor.h" -#include "stages/node_layout.h" +#include "node_extent_mutable.h" +#include "node_types.h" +#include "stages/stage_types.h" namespace crimson::os::seastore::onode { +struct key_hobj_t; +struct key_view_t; class NodeExtentMutable; -// TODO: decouple NodeT with Node - -template -class NodeT : virtual public Node { +class NodeImpl { public: - using extent_t = NodeExtentT; - using node_ertr = Node::node_ertr; - template - using node_future = Node::node_future; - using node_stage_t = typename extent_t::node_stage_t; - using position_t = typename extent_t::position_t; - using value_t = typename extent_t::value_t; - static constexpr auto FIELD_TYPE = extent_t::FIELD_TYPE; - static constexpr auto NODE_TYPE = _NODE_TYPE; - - struct fresh_node_t { - Ref node; - NodeExtentMutable mut; - std::pair, NodeExtentMutable> make_pair() { - return std::make_pair(Ref(node), mut); - } - }; - - virtual ~NodeT() = default; - - bool is_level_tail() const override final { return extent.read().is_level_tail(); } - field_type_t field_type() const override final { return FIELD_TYPE; } - laddr_t laddr() const override final { return extent.get_laddr(); } - level_t level() const override final { return extent.read().level(); } - - full_key_t get_key_view( - const search_position_t& position) const override final { - full_key_t ret; - STAGE_T::get_key_view( - extent.read(), cast_down(position), ret); - return ret; - } - - full_key_t get_largest_key_view() const override final { - full_key_t key_view; - STAGE_T::lookup_largest_index(extent.read(), key_view); - return key_view; - } - - std::ostream& dump(std::ostream& os) const override final { - auto& node_stage = extent.read(); - auto p_start = node_stage.p_start(); - os << *this << ":"; - os << "\n header: " << node_stage_t::header_size() << "B"; - size_t size = 0u; - if (node_stage.keys()) { - STAGE_T::dump(node_stage, os, " ", size, p_start); - } else { - if constexpr (NODE_TYPE == node_type_t::LEAF) { - return os << " empty!"; - } else { // internal node - if (!is_level_tail()) { - return os << " empty!"; - } else { - size += node_stage_t::header_size(); - } - } - } - if constexpr (NODE_TYPE == node_type_t::INTERNAL) { - if (is_level_tail()) { - size += sizeof(laddr_t); - auto value_ptr = node_stage.get_end_p_laddr(); - int offset = reinterpret_cast(value_ptr) - p_start; - os << "\n tail value: 0x" - << std::hex << *value_ptr << std::dec - << " " << size << "B" - << " @" << offset << "B"; - } - } - return os; - } - - std::ostream& dump_brief(std::ostream& os) const override final { - auto& node_stage = extent.read(); - os << "Node" << NODE_TYPE << FIELD_TYPE - << "@0x" << std::hex << laddr() - << "+" << node_stage_t::EXTENT_SIZE << std::dec - << (is_level_tail() ? "$" : "") - << "(level=" << (unsigned)level() - << ", filled=" << node_stage.total_size() - node_stage.free_size() << "B" - << ", free=" << node_stage.free_size() << "B" - << ")"; - return os; - } - - const value_t* get_value_ptr(const search_position_t& position) const { - auto& node_stage = extent.read(); - if constexpr (NODE_TYPE == node_type_t::INTERNAL) { - if (position.is_end()) { - assert(is_level_tail()); - return node_stage.get_end_p_laddr(); - } - } else { - assert(!position.is_end()); - } - return STAGE_T::get_p_value(node_stage, cast_down(position)); - } - - void test_make_destructable( - context_t c, NodeExtentMutable& mut, Super::URef&& _super) override final { - node_stage_t::update_is_level_tail(mut, extent.read(), true); - make_root(c, std::move(_super)); - } - - static Ref load(NodeExtent::Ref extent, bool expect_is_level_tail) { - Ref ret = new ConcreteType(); - ret->extent = extent_t::load(extent); - assert(ret->is_level_tail() == expect_is_level_tail); - return ret; - } + using alloc_ertr = crimson::errorator< + crimson::ct_error::input_output_error, + crimson::ct_error::invarg, + crimson::ct_error::enoent, + crimson::ct_error::erange>; + virtual ~NodeImpl() = default; + + virtual field_type_t field_type() const = 0; + virtual laddr_t laddr() const = 0; + virtual void prepare_mutate(context_t) = 0; + virtual bool is_level_tail() const = 0; + virtual bool is_empty() const = 0; + virtual level_t level() const = 0; + 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 std::ostream& dump(std::ostream&) const = 0; + virtual std::ostream& dump_brief(std::ostream&) const = 0; + + virtual void test_copy_to(NodeExtentMutable&) const = 0; + virtual void test_set_tail(NodeExtentMutable&) = 0; protected: - // TODO: constructor - extent_t extent; + NodeImpl() = default; }; -template -class InternalNodeT : public InternalNode, - public NodeT { +class InternalNodeImpl : public NodeImpl { public: - using parent_t = NodeT; - using extent_t = typename parent_t::extent_t; - using fresh_node_t = typename parent_t::fresh_node_t; - using node_stage_t = typename parent_t::node_stage_t; - using position_t = typename parent_t::position_t; - - virtual ~InternalNodeT() = default; + struct internal_marker_t {}; + virtual ~InternalNodeImpl() = default; - node_future do_lower_bound( - context_t c, const full_key_t& key, - MatchHistory& history) override final { - auto result = STAGE_T::lower_bound_normalized( - this->extent.read(), key, history); - auto& position = result.position; - laddr_t child_addr; - if (position.is_end()) { - assert(this->is_level_tail()); - child_addr = *this->get_value_ptr(position); - } else { - assert(result.p_value); - child_addr = *result.p_value; - } - return get_or_track_child(c, position, child_addr - ).safe_then([c, &key, &history](auto child) { - // XXX(multi-type): pass result.mstat to child - return child->do_lower_bound(c, key, history); - }); + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual const laddr_t* get_p_value( + const search_position_t&, internal_marker_t={}) const { + assert(false && "impossible path"); } - - node_future> lookup_smallest(context_t c) override final { - auto position = search_position_t::begin(); - laddr_t child_addr = *this->get_value_ptr(position); - return get_or_track_child(c, position, child_addr).safe_then([c](auto child) { - return child->lookup_smallest(c); - }); + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual lookup_result_t lower_bound( + const key_hobj_t&, MatchHistory&, internal_marker_t={}) const { + assert(false && "impossible path"); } - - node_future> lookup_largest(context_t c) override final { - // NOTE: unlike LeafNodeT::lookup_largest(), this only works for the tail - // internal node to return the tail child address. - auto position = search_position_t::end(); - laddr_t child_addr = *this->get_value_ptr(position); - return get_or_track_child(c, position, child_addr).safe_then([c](auto child) { - return child->lookup_largest(c); - }); + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual const laddr_t* insert( + const key_view_t&, const laddr_t&, search_position_t&, match_stage_t&, node_offset_t&) { + assert(false && "impossible path"); } - - node_future<> apply_child_split( - context_t c, const search_position_t& pos, - const full_key_t& left_key, Ref left_child, - Ref right_child) override final { - this->extent.prepare_mutate(c); - auto& node_stage = this->extent.read(); - - // update pos => l_addr to r_addr - auto left_laddr = left_child->laddr(); - auto right_laddr = right_child->laddr(); - const laddr_t* p_rvalue = this->get_value_ptr(pos); - this->extent.prepare_internal_split_replayable( - left_laddr, right_laddr, const_cast(p_rvalue)); - this->replace_track(pos, left_child, right_child); - - // evaluate insertion - position_t insert_pos = cast_down(pos); - match_stage_t insert_stage; - node_offset_t insert_size; - if (unlikely(!node_stage.keys())) { - assert(insert_pos.is_end()); - insert_stage = STAGE_T::STAGE; - insert_size = STAGE_T::template insert_size(left_key, left_laddr); - } else { - std::tie(insert_stage, insert_size) = - STAGE_T::evaluate_insert(node_stage, left_key, left_laddr, insert_pos, true); - } - - // TODO: common part begin, move to NodeT - auto free_size = node_stage.free_size(); - if (free_size >= insert_size) { - auto p_value = this->extent.template insert_replayable( - left_key, left_laddr, insert_pos, insert_stage, insert_size); - assert(node_stage.free_size() == free_size - insert_size); - // TODO: common part end, move to NodeT - - assert(*p_value == left_laddr); - auto insert_pos_normalized = normalize(std::move(insert_pos)); - assert(insert_pos_normalized <= pos); - assert(get_key_view(insert_pos_normalized) == left_key); - track_insert(insert_pos_normalized, insert_stage, left_child, right_child); - this->validate_tracked_children(); - return node_ertr::now(); - } - - std::cout << " try insert at: " << insert_pos - << ", insert_stage=" << (int)insert_stage - << ", insert_size=" << insert_size - << ", values=0x" << std::hex << left_laddr - << ",0x" << right_laddr << std::dec << std::endl; - - Ref this_ref = this; - return (is_root() ? this->upgrade_root(c) : node_ertr::now() - ).safe_then([this, c] { - return ConcreteType::allocate(c, this->level(), this->is_level_tail()); - }).safe_then([this_ref, this, c, left_key, left_child, right_child, left_laddr, - insert_pos, insert_stage, insert_size](auto fresh_right) mutable { - auto& node_stage = this->extent.read(); - size_t empty_size = node_stage.size_before(0); - size_t available_size = node_stage.total_size() - empty_size; - size_t target_split_size = empty_size + (available_size + insert_size) / 2; - // TODO adjust NODE_BLOCK_SIZE according to this requirement - assert(insert_size < available_size / 2); - typename STAGE_T::StagedIterator split_at; - bool insert_left = STAGE_T::locate_split( - node_stage, target_split_size, insert_pos, insert_stage, insert_size, split_at); - - std::cout << " split at: " << split_at << ", insert_left=" << insert_left - << ", now insert at: " << insert_pos - << std::endl; - - auto append_at = split_at; - // TODO(cross-node string dedup) - typename STAGE_T::template StagedAppender right_appender; - right_appender.init(&fresh_right.mut, fresh_right.mut.get_write()); - const laddr_t* p_value = nullptr; - if (!insert_left) { - // right node: append [start(append_at), insert_pos) - STAGE_T::template append_until( - append_at, right_appender, insert_pos, insert_stage); - std::cout << "insert to right: " << insert_pos - << ", insert_stage=" << (int)insert_stage << std::endl; - // right node: append [insert_pos(key, value)] - bool is_front_insert = (insert_pos == position_t::begin()); - bool is_end = STAGE_T::template append_insert( - left_key, left_laddr, append_at, right_appender, - is_front_insert, insert_stage, p_value); - assert(append_at.is_end() == is_end); - } - - // right node: append (insert_pos, end) - auto pos_end = position_t::end(); - STAGE_T::template append_until( - append_at, right_appender, pos_end, STAGE_T::STAGE); - assert(append_at.is_end()); - right_appender.wrap(); - fresh_right.node->dump(std::cout) << std::endl; - - // mutate left node - if (insert_left) { - p_value = this->extent.template split_insert_replayable( - split_at, left_key, left_laddr, insert_pos, insert_stage, insert_size); - } else { - this->extent.split_replayable(split_at); - } - this->dump(std::cout) << std::endl; - assert(p_value); - // TODO: common part end, move to NodeT - - auto split_pos_normalized = normalize(split_at.get_pos()); - auto insert_pos_normalized = normalize(std::move(insert_pos)); - std::cout << "split at " << split_pos_normalized - << ", insert at " << insert_pos_normalized - << ", insert_left=" << insert_left - << ", insert_stage=" << (int)insert_stage << std::endl; - track_split(split_pos_normalized, fresh_right.node); - if (insert_left) { - track_insert(insert_pos_normalized, insert_stage, left_child); - } else { - fresh_right.node->track_insert(insert_pos_normalized, insert_stage, left_child); - } - - this->validate_tracked_children(); - fresh_right.node->validate_tracked_children(); - - // propagate index to parent - return this->insert_parent(c, fresh_right.node); - // TODO (optimize) - // try to acquire space from siblings before split... see btrfs - }); - } - - static node_future allocate( - context_t c, level_t level, bool is_level_tail) { - assert(level != 0u); - return extent_t::allocate(c, level, is_level_tail - ).safe_then([](auto&& fresh_extent) { - auto ret = Ref(new ConcreteType()); - ret->extent = std::move(fresh_extent.extent); - return fresh_node_t{ret, fresh_extent.mut}; - }); - } - - private: - const laddr_t* get_p_value(const search_position_t& pos) const override final { - return this->get_value_ptr(pos); + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual std::tuple split_insert( + NodeExtentMutable&, NodeImpl&, const key_view_t&, const laddr_t&, + search_position_t&, match_stage_t&, node_offset_t&) { + assert(false && "impossible path"); } -}; + 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; -class InternalNode0 final : public InternalNodeT { - public: - node_future<> test_clone_root( - context_t c_other, RootNodeTracker& tracker_other) const override final { - assert(is_root()); - assert(is_level_tail()); - Ref this_ref = this; - return InternalNode0::allocate(c_other, level(), true - ).safe_then([this, c_other, &tracker_other](auto fresh_other) { - this->extent.test_copy_to(fresh_other.mut); - auto cloned_root = fresh_other.node; - return c_other.nm.get_super(c_other.t, tracker_other - ).safe_then([c_other, cloned_root](auto&& super_other) { - cloned_root->make_root_new(c_other, std::move(super_other)); - return cloned_root; - }); - }).safe_then([this_ref, this, c_other](auto cloned_root) { - // In some unit tests, the children are stubbed out that they - // don't exist in NodeExtentManager, and are only tracked in memory. - return test_clone_children(c_other, cloned_root); - }); - } + struct fresh_impl_t { + InternalNodeImplURef impl; + NodeExtentMutable mut; + std::pair make_pair() { + return {std::move(impl), mut}; + } + }; + static alloc_ertr::future allocate(context_t, field_type_t, bool, level_t); + static InternalNodeImplURef load(NodeExtentRef, field_type_t, bool); - static node_future> allocate_root( - context_t c, level_t old_root_level, - laddr_t old_root_addr, Super::URef&& super) { - return allocate(c, old_root_level + 1, true - ).safe_then([c, old_root_addr, - super = std::move(super)](auto fresh_root) mutable { - auto root = fresh_root.node; - const laddr_t* p_value = root->get_value_ptr(search_position_t::end()); - fresh_root.mut.copy_in_absolute( - const_cast(p_value), old_root_addr); - root->make_root_from(c, std::move(super), old_root_addr); - return root; - }); - } + protected: + InternalNodeImpl() = default; }; -class InternalNode1 final : public InternalNodeT {}; -class InternalNode2 final : public InternalNodeT {}; -class InternalNode3 final : public InternalNodeT {}; - -template -class LeafNodeT: public LeafNode, - public NodeT { +class LeafNodeImpl : public NodeImpl { public: - using parent_t = NodeT; - using extent_t = typename parent_t::extent_t; - using fresh_node_t = typename parent_t::fresh_node_t; - using node_stage_t = typename parent_t::node_stage_t; - using position_t = typename parent_t::position_t; - - virtual ~LeafNodeT() = default; - - node_future do_lower_bound( - context_t, const full_key_t& key, - MatchHistory& history) override final { - auto& node_stage = this->extent.read(); - if (unlikely(node_stage.keys() == 0)) { - assert(this->is_root()); - history.set(MatchKindCMP::NE); - auto p_cursor = get_or_track_cursor(search_position_t::end(), nullptr); - return node_ertr::make_ready_future( - search_result_t{p_cursor, MatchKindBS::NE}); - } - - auto result = STAGE_T::lower_bound_normalized(node_stage, key, history); - if (result.is_end()) { - assert(this->is_level_tail()); - } else { - assert(result.p_value); - } - auto p_cursor = get_or_track_cursor(result.position, result.p_value); - return node_ertr::make_ready_future( - search_result_t{p_cursor, result.match()}); - } - - node_future> lookup_smallest(context_t) override final { - auto& node_stage = this->extent.read(); - if (unlikely(node_stage.keys() == 0)) { - assert(this->is_root()); - auto pos = search_position_t::end(); - return node_ertr::make_ready_future>( - get_or_track_cursor(pos, nullptr)); - } - - auto pos = search_position_t::begin(); - const onode_t* p_value = this->get_value_ptr(pos); - return node_ertr::make_ready_future>( - get_or_track_cursor(pos, p_value)); - } - - node_future> lookup_largest(context_t) override final { - auto& node_stage = this->extent.read(); - if (unlikely(node_stage.keys() == 0)) { - assert(this->is_root()); - auto pos = search_position_t::end(); - return node_ertr::make_ready_future>( - get_or_track_cursor(pos, nullptr)); - } - - search_position_t pos; - const onode_t* p_value = nullptr; - STAGE_T::lookup_largest_normalized(node_stage, pos, p_value); - return node_ertr::make_ready_future>( - get_or_track_cursor(pos, p_value)); - } - - node_future> insert_value( - context_t c, const full_key_t& key, const onode_t& value, - const search_position_t& pos, const MatchHistory& history) override final { -#ifndef NDEBUG - if (pos.is_end()) { - assert(this->is_level_tail()); - } -#endif - this->extent.prepare_mutate(c); - auto& node_stage = this->extent.read(); - - position_t insert_pos = cast_down(pos); - auto [insert_stage, insert_size] = - STAGE_T::evaluate_insert(key, value, history, insert_pos); - - // TODO: common part begin, move to NodeT - auto free_size = node_stage.free_size(); - if (free_size >= insert_size) { - auto p_value = this->extent.template insert_replayable( - key, value, insert_pos, insert_stage, insert_size); - assert(node_stage.free_size() == free_size - insert_size); - // TODO: common part end, move to NodeT - - assert(p_value->size == value.size); - auto insert_pos_normalized = normalize(std::move(insert_pos)); - assert(insert_pos_normalized <= pos); - assert(get_key_view(insert_pos_normalized) == key); - auto ret = track_insert(insert_pos_normalized, insert_stage, p_value); - this->validate_tracked_cursors(); - return node_ertr::make_ready_future>(ret); + struct leaf_marker_t {}; + virtual ~LeafNodeImpl() = default; + + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual const onode_t* get_p_value( + const search_position_t&, leaf_marker_t={}) const { + assert(false && "impossible path"); + } + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual lookup_result_t lower_bound( + const key_hobj_t&, MatchHistory&, leaf_marker_t={}) const { + assert(false && "impossible path"); + } + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual const onode_t* insert( + const key_hobj_t&, const onode_t&, search_position_t&, match_stage_t&, node_offset_t&) { + assert(false && "impossible path"); + } + #pragma GCC diagnostic ignored "-Woverloaded-virtual" + virtual std::tuple split_insert( + NodeExtentMutable&, NodeImpl&, const key_hobj_t&, const onode_t&, + search_position_t&, match_stage_t&, node_offset_t&) { + assert(false && "impossible path"); + } + + virtual void get_largest_value(search_position_t&, const onode_t*&) const = 0; + virtual std::tuple evaluate_insert( + const key_hobj_t&, const onode_t&, + const MatchHistory&, search_position_t&) const = 0; + + struct fresh_impl_t { + LeafNodeImplURef impl; + NodeExtentMutable mut; + std::pair make_pair() { + return {std::move(impl), mut}; } + }; + static alloc_ertr::future allocate(context_t, field_type_t, bool); + static LeafNodeImplURef load(NodeExtentRef, field_type_t, bool); - std::cout << " try insert at: " << insert_pos - << ", insert_stage=" << (int)insert_stage - << ", insert_size=" << insert_size - << std::endl; - - Ref this_ref = this; - return (is_root() ? this->upgrade_root(c) : node_ertr::now() - ).safe_then([this, c] { - return ConcreteType::allocate(c, this->is_level_tail()); - }).safe_then([this_ref, this, c, &key, &value, &history, - insert_pos, insert_stage, insert_size](auto fresh_right) mutable { - auto& node_stage = this->extent.read(); - size_t empty_size = node_stage.size_before(0); - size_t available_size = node_stage.total_size() - empty_size; - size_t target_split_size = empty_size + (available_size + insert_size) / 2; - // TODO adjust NODE_BLOCK_SIZE according to this requirement - assert(insert_size < available_size / 2); - typename STAGE_T::StagedIterator split_at; - bool insert_left = STAGE_T::locate_split( - node_stage, target_split_size, insert_pos, insert_stage, insert_size, split_at); - - std::cout << " split at: " << split_at << ", insert_left=" << insert_left - << ", now insert at: " << insert_pos - << std::endl; - - auto append_at = split_at; - // TODO(cross-node string dedup) - typename STAGE_T::template StagedAppender right_appender; - right_appender.init(&fresh_right.mut, fresh_right.mut.get_write()); - const onode_t* p_value = nullptr; - if (!insert_left) { - // right node: append [start(append_at), insert_pos) - STAGE_T::template append_until( - append_at, right_appender, insert_pos, insert_stage); - std::cout << "insert to right: " << insert_pos - << ", insert_stage=" << (int)insert_stage << std::endl; - // right node: append [insert_pos(key, value)] - bool is_front_insert = (insert_pos == position_t::begin()); - bool is_end = STAGE_T::template append_insert( - key, value, append_at, right_appender, - is_front_insert, insert_stage, p_value); - assert(append_at.is_end() == is_end); - } - - // right node: append (insert_pos, end) - auto pos_end = position_t::end(); - STAGE_T::template append_until( - append_at, right_appender, pos_end, STAGE_T::STAGE); - assert(append_at.is_end()); - right_appender.wrap(); - fresh_right.node->dump(std::cout) << std::endl; - - // mutate left node - if (insert_left) { - p_value = this->extent.template split_insert_replayable( - split_at, key, value, insert_pos, insert_stage, insert_size); - } else { - this->extent.split_replayable(split_at); - } - this->dump(std::cout) << std::endl; - assert(p_value); - // TODO: common part end, move to NodeT - - auto split_pos_normalized = normalize(split_at.get_pos()); - auto insert_pos_normalized = normalize(std::move(insert_pos)); - std::cout << "split at " << split_pos_normalized - << ", insert at " << insert_pos_normalized - << ", insert_left=" << insert_left - << ", insert_stage=" << (int)insert_stage << std::endl; - track_split(split_pos_normalized, fresh_right.node); - Ref ret; - if (insert_left) { - assert(this->get_key_view(insert_pos_normalized) == key); - ret = track_insert(insert_pos_normalized, insert_stage, p_value); - } else { - assert(fresh_right.node->get_key_view(insert_pos_normalized) == key); - ret = fresh_right.node->track_insert(insert_pos_normalized, insert_stage, p_value); - } - - this->validate_tracked_cursors(); - fresh_right.node->validate_tracked_cursors(); - - // propagate index to parent - return this->insert_parent(c, fresh_right.node).safe_then([ret] { - return ret; - }); - // TODO (optimize) - // try to acquire space from siblings before split... see btrfs - }); - } - - static node_future allocate(context_t c, bool is_level_tail) { - return extent_t::allocate(c, 0u, is_level_tail - ).safe_then([](auto&& fresh_extent) { - auto ret = Ref(new ConcreteType()); - ret->extent = std::move(fresh_extent.extent); - return fresh_node_t{ret, fresh_extent.mut}; - }); - } - - private: - const onode_t* get_p_value(const search_position_t& pos) const override final { - return this->get_value_ptr(pos); - } -}; -class LeafNode0 final : public LeafNodeT { - public: - node_future<> test_clone_root( - context_t c_other, RootNodeTracker& tracker_other) const override final { - assert(this->is_root()); - assert(is_level_tail()); - Ref this_ref = this; - return LeafNode0::allocate(c_other, true - ).safe_then([this, c_other, &tracker_other](auto fresh_other) { - this->extent.test_copy_to(fresh_other.mut); - auto cloned_root = fresh_other.node; - return c_other.nm.get_super(c_other.t, tracker_other - ).safe_then([c_other, cloned_root](auto&& super_other) { - cloned_root->make_root_new(c_other, std::move(super_other)); - }); - }).safe_then([this_ref]{}); - } - - static node_future<> mkfs(context_t c, RootNodeTracker& root_tracker) { - return allocate(c, true - ).safe_then([c, &root_tracker](auto fresh_node) { - auto root = fresh_node.node; - return c.nm.get_super(c.t, root_tracker - ).safe_then([c, root](auto&& super) { - root->make_root_new(c, std::move(super)); - }); - }); - } + protected: + LeafNodeImpl() = default; }; -class LeafNode1 final : public LeafNodeT {}; -class LeafNode2 final : public LeafNodeT {}; -class LeafNode3 final : public LeafNodeT {}; - -inline Node::node_future> load_node( - context_t c, laddr_t addr, bool expect_is_level_tail) { - // NOTE: - // *option1: all types of node have the same length; - // option2: length is defined by node/field types; - // option3: length is totally flexible; - return c.nm.read_extent(c.t, addr, NODE_BLOCK_SIZE - ).safe_then([expect_is_level_tail](auto extent) { - const auto header = reinterpret_cast(extent->get_read()); - auto _field_type = header->get_field_type(); - if (!_field_type.has_value()) { - throw std::runtime_error("load failed: bad field type"); - } - auto _node_type = header->get_node_type(); - if (_field_type == field_type_t::N0) { - if (_node_type == node_type_t::LEAF) { - return LeafNode0::load(extent, expect_is_level_tail); - } else { - return InternalNode0::load(extent, expect_is_level_tail); - } - } else if (_field_type == field_type_t::N1) { - if (_node_type == node_type_t::LEAF) { - return LeafNode1::load(extent, expect_is_level_tail); - } else { - return InternalNode1::load(extent, expect_is_level_tail); - } - } else if (_field_type == field_type_t::N2) { - if (_node_type == node_type_t::LEAF) { - return LeafNode2::load(extent, expect_is_level_tail); - } else { - return InternalNode2::load(extent, expect_is_level_tail); - } - } else if (_field_type == field_type_t::N3) { - if (_node_type == node_type_t::LEAF) { - return LeafNode3::load(extent, expect_is_level_tail); - } else { - return InternalNode3::load(extent, expect_is_level_tail); - } - } else { - assert(false); - } - }); -} } 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 new file mode 100644 index 0000000000000..35e0c32c320ab --- /dev/null +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h @@ -0,0 +1,344 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +// TODO: remove +#include +#include + +#include "common/likely.h" +#include "node_extent_visitor.h" +#include "node_impl.h" +#include "stages/node_stage_layout.h" + +namespace crimson::os::seastore::onode { + +template struct insert_key_type; +template <> struct insert_key_type { + static constexpr auto type = KeyT::VIEW; }; +template <> struct insert_key_type { + static constexpr auto type = KeyT::HOBJ; }; + +template struct node_impl_type; +template <> struct node_impl_type { + using type = InternalNodeImpl; }; +template <> struct node_impl_type { + using type = LeafNodeImpl; }; + +template struct node_marker_type; +template <> struct node_marker_type { + using type = InternalNodeImpl::internal_marker_t; }; +template <> struct node_marker_type { + using type = LeafNodeImpl::leaf_marker_t; }; + +template +class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { + public: + using URef = std::unique_ptr; + using extent_t = NodeExtentT; + using parent_t = typename node_impl_type::type; + using marker_t = typename node_marker_type::type; + using node_stage_t = typename extent_t::node_stage_t; + using position_t = typename extent_t::position_t; + using value_t = typename extent_t::value_t; + static constexpr auto FIELD_TYPE = extent_t::FIELD_TYPE; + static constexpr auto KEY_TYPE = insert_key_type::type; + static constexpr auto STAGE = STAGE_T::STAGE; + + NodeLayoutT(const NodeLayoutT&) = delete; + NodeLayoutT(NodeLayoutT&&) = delete; + NodeLayoutT& operator=(const NodeLayoutT&) = delete; + NodeLayoutT& operator=(NodeLayoutT&&) = delete; + ~NodeLayoutT() override = default; + + static URef load(NodeExtentRef extent, bool expect_is_level_tail) { + std::unique_ptr ret( + new NodeLayoutT(extent_t::loaded(extent), extent)); + assert(ret->is_level_tail() == expect_is_level_tail); + return ret; + } + + using alloc_ertr = NodeExtentManager::tm_ertr; + static alloc_ertr::future allocate( + context_t c, bool is_level_tail, level_t level) { + // NOTE: + // *option1: all types of node have the same length; + // option2: length is defined by node/field types; + // option3: length is totally flexible; + return c.nm.alloc_extent(c.t, node_stage_t::EXTENT_SIZE + ).safe_then([is_level_tail, level](auto extent) { + auto [state, mut] = extent_t::allocated(extent, is_level_tail, level); + return typename parent_t::fresh_impl_t{ + std::unique_ptr(new NodeLayoutT(state, extent)), mut}; + }); + } + + protected: + /* + * NodeImpl + */ + field_type_t field_type() const override { return FIELD_TYPE; } + laddr_t laddr() const override { return extent.get_laddr(); } + void prepare_mutate(context_t c) override { return extent.prepare_mutate(c); } + bool is_level_tail() const override { return extent.read().is_level_tail(); } + bool is_empty() const override { return extent.read().keys() == 0; } + level_t level() const override { return extent.read().level(); } + node_offset_t free_size() const override { return extent.read().free_size(); } + + key_view_t get_key_view(const search_position_t& position) const override { + key_view_t ret; + STAGE_T::get_key_view(extent.read(), cast_down(position), ret); + return ret; + } + + key_view_t get_largest_key_view() const override { + key_view_t ret; + STAGE_T::lookup_largest_index(extent.read(), ret); + return ret; + } + + std::ostream& dump(std::ostream& os) const override { + auto& node_stage = extent.read(); + auto p_start = node_stage.p_start(); + dump_brief(os); + os << ":\n header: " << node_stage_t::header_size() << "B"; + size_t size = 0u; + if (node_stage.keys()) { + STAGE_T::dump(node_stage, os, " ", size, p_start); + } else { + if constexpr (NODE_TYPE == node_type_t::LEAF) { + return os << " empty!"; + } else { // internal node + if (!node_stage.is_level_tail()) { + return os << " empty!"; + } else { + size += node_stage_t::header_size(); + } + } + } + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + if (node_stage.is_level_tail()) { + size += sizeof(laddr_t); + auto value_ptr = node_stage.get_end_p_laddr(); + int offset = reinterpret_cast(value_ptr) - p_start; + os << "\n tail value: 0x" + << std::hex << *value_ptr << std::dec + << " " << size << "B" + << " @" << offset << "B"; + } + } + return os; + } + + std::ostream& dump_brief(std::ostream& os) const override { + auto& node_stage = extent.read(); + os << "Node" << NODE_TYPE << FIELD_TYPE + << "@0x" << std::hex << extent.get_laddr() + << "+" << node_stage_t::EXTENT_SIZE << std::dec + << (node_stage.is_level_tail() ? "$" : "") + << "(level=" << (unsigned)node_stage.level() + << ", filled=" << node_stage.total_size() - node_stage.free_size() << "B" + << ", free=" << node_stage.free_size() << "B" + << ")"; + return os; + } + + void test_copy_to(NodeExtentMutable& to) const override { + extent.test_copy_to(to); + } + + void test_set_tail(NodeExtentMutable& mut) override { + node_stage_t::update_is_level_tail(mut, extent.read(), true); + } + + /* + * Common + */ + const value_t* get_p_value( + const search_position_t& position, marker_t={}) const override { + auto& node_stage = extent.read(); + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + if (position.is_end()) { + assert(is_level_tail()); + return node_stage.get_end_p_laddr(); + } + } else { + assert(!position.is_end()); + } + return STAGE_T::get_p_value(node_stage, cast_down(position)); + } + + lookup_result_t lower_bound( + const key_hobj_t& key, MatchHistory& history, marker_t={}) const override { + auto& node_stage = extent.read(); + if constexpr (NODE_TYPE == node_type_t::LEAF) { + if (unlikely(node_stage.keys() == 0)) { + history.set(MatchKindCMP::NE); + return lookup_result_t::end(); + } + } + auto result = STAGE_T::lower_bound_normalized(node_stage, key, history); + if (result.is_end()) { + assert(node_stage.is_level_tail()); + assert(result.p_value == nullptr); + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + result.p_value = node_stage.get_end_p_laddr(); + } + } else { + assert(result.p_value != nullptr); + } + return result; + } + + const value_t* insert( + const full_key_t& key, const value_t& value, + search_position_t& insert_pos, match_stage_t& insert_stage, + node_offset_t& insert_size) override { + auto ret = extent.template insert_replayable( + key, value, cast_down(insert_pos), insert_stage, insert_size); + assert(get_key_view(insert_pos) == key); + return ret; + } + + std::tuple split_insert( + NodeExtentMutable& right_mut, NodeImpl& right_impl, + const full_key_t& key, const value_t& value, + search_position_t& _insert_pos, match_stage_t& insert_stage, + node_offset_t& insert_size) override { + auto& insert_pos = cast_down(_insert_pos); + auto& node_stage = extent.read(); + size_t empty_size = node_stage.size_before(0); + size_t available_size = node_stage.total_size() - empty_size; + size_t target_split_size = empty_size + (available_size + insert_size) / 2; + // TODO adjust NODE_BLOCK_SIZE according to this requirement + assert(insert_size < available_size / 2); + typename STAGE_T::StagedIterator split_at; + bool is_insert_left = STAGE_T::locate_split( + node_stage, target_split_size, insert_pos, insert_stage, insert_size, split_at); + + std::cout << " split at: " << split_at << ", is_insert_left=" << is_insert_left + << ", now insert at: " << insert_pos + << std::endl; + + auto append_at = split_at; + // TODO(cross-node string dedup) + typename STAGE_T::template StagedAppender right_appender; + right_appender.init(&right_mut, right_mut.get_write()); + const value_t* p_value = nullptr; + if (!is_insert_left) { + // right node: append [start(append_at), insert_pos) + STAGE_T::template append_until( + append_at, right_appender, insert_pos, insert_stage); + std::cout << "insert to right: " << insert_pos + << ", insert_stage=" << (int)insert_stage << std::endl; + // right node: append [insert_pos(key, value)] + bool is_front_insert = (insert_pos == position_t::begin()); + bool is_end = STAGE_T::template append_insert( + key, value, append_at, right_appender, + is_front_insert, insert_stage, p_value); + assert(append_at.is_end() == is_end); + } + + // right node: append (insert_pos, end) + auto pos_end = position_t::end(); + STAGE_T::template append_until( + append_at, right_appender, pos_end, STAGE); + assert(append_at.is_end()); + right_appender.wrap(); + right_impl.dump(std::cout) << std::endl; + + // mutate left node + if (is_insert_left) { + p_value = extent.template split_insert_replayable( + split_at, key, value, insert_pos, insert_stage, insert_size); + assert(get_key_view(_insert_pos) == key); + } else { + assert(right_impl.get_key_view(_insert_pos) == key); + extent.split_replayable(split_at); + } + dump(std::cout) << std::endl; + assert(p_value); + + auto split_pos = normalize(split_at.get_pos()); + std::cout << "split at " << split_pos + << ", insert at " << _insert_pos + << ", is_insert_left=" << is_insert_left + << ", insert_stage=" << (int)insert_stage << std::endl; + return {split_pos, is_insert_left, p_value}; + } + + /* + * InternalNodeImpl + */ + void replace_child_addr( + const search_position_t& pos, laddr_t dst, laddr_t src) override { + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + const laddr_t* p_value = get_p_value(pos); + assert(*p_value == src); + extent.update_child_addr_replayable(dst, const_cast(p_value)); + } else { + assert(false && "impossible path"); + } + } + + std::tuple evaluate_insert( + const key_view_t& key, const laddr_t& value, + search_position_t& insert_pos) const override { + if constexpr (NODE_TYPE == node_type_t::INTERNAL) { + auto& node_stage = extent.read(); + match_stage_t insert_stage; + node_offset_t insert_size; + if (unlikely(!node_stage.keys())) { + assert(insert_pos.is_end()); + insert_stage = STAGE; + insert_size = STAGE_T::template insert_size(key, value); + } else { + std::tie(insert_stage, insert_size) = STAGE_T::evaluate_insert( + node_stage, key, value, cast_down(insert_pos), true); + } + return {insert_stage, insert_size}; + } else { + assert(false && "impossible path"); + } + } + + /* + * LeafNodeImpl + */ + void get_largest_value(search_position_t& pos, const onode_t*& p_value) const override { + if constexpr (NODE_TYPE == node_type_t::LEAF) { + STAGE_T::lookup_largest_normalized(extent.read(), pos, p_value); + } else { + assert(false && "impossible path"); + } + } + + std::tuple evaluate_insert( + const key_hobj_t& key, const onode_t& value, const MatchHistory& history, + search_position_t& insert_pos) const override { + if constexpr (NODE_TYPE == node_type_t::LEAF) { + return STAGE_T::evaluate_insert( + key, value, history, cast_down(insert_pos)); + } else { + assert(false && "impossible path"); + } + } + + private: + NodeLayoutT(typename extent_t::state_t state, NodeExtentRef extent) + : extent{state, extent} {} + + extent_t extent; +}; + +using InternalNode0 = NodeLayoutT; +using InternalNode1 = NodeLayoutT; +using InternalNode2 = NodeLayoutT; +using InternalNode3 = NodeLayoutT; +using LeafNode0 = NodeLayoutT; +using LeafNode1 = NodeLayoutT; +using LeafNode2 = NodeLayoutT; +using LeafNode3 = NodeLayoutT; + +} diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl_replayable.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout_replayable.h similarity index 87% rename from src/crimson/os/seastore/onode_manager/staged-fltree/node_impl_replayable.h rename to src/crimson/os/seastore/onode_manager/staged-fltree/node_layout_replayable.h index cc7b55e211907..ef01d2cc7b419 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_impl_replayable.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout_replayable.h @@ -63,15 +63,10 @@ struct NodeLayoutReplayableT { return p_value; } - static void prepare_internal_split( - NodeExtentMutable& mut, - const node_stage_t& node_stage, - const laddr_t left_child_addr, - const laddr_t right_child_addr, - laddr_t* p_split_addr) { + static void update_child_addr( + NodeExtentMutable& mut, const laddr_t new_addr, laddr_t* p_addr) { assert(NODE_TYPE == node_type_t::INTERNAL); - assert(*p_split_addr == left_child_addr); - mut.copy_in_absolute(p_split_addr, right_child_addr); + mut.copy_in_absolute(p_addr, new_addr); } }; diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_types.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_types.h index 17878d8e4b95d..2466588e3f0ad 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_types.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_types.h @@ -43,6 +43,4 @@ inline std::ostream& operator<<(std::ostream &os, const node_type_t& type) { return os; } -using level_t = uint8_t; - } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/key_layout.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/key_layout.h index 77d5e6705bd6c..81e756eb33353 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/key_layout.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/key_layout.h @@ -17,11 +17,11 @@ class NodeExtentMutable; class key_view_t; class key_hobj_t; enum class KeyT { VIEW, HOBJ }; -template struct _key_type; -template<> struct _key_type { using type = key_view_t; }; -template<> struct _key_type { using type = key_hobj_t; }; +template struct _full_key_type; +template<> struct _full_key_type { using type = key_view_t; }; +template<> struct _full_key_type { using type = key_hobj_t; }; template -using full_key_t = typename _key_type::type; +using full_key_t = typename _full_key_type::type; // TODO: consider alignments struct shard_pool_t { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.cc index 8ee21db86c296..d1c1394a051fd 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.cc @@ -4,7 +4,7 @@ #include "node_stage.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_mutable.h" -#include "node_layout.h" +#include "node_stage_layout.h" namespace crimson::os::seastore::onode { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_layout.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc similarity index 99% rename from src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_layout.cc rename to src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc index 2dc828f69edeb..2809803eb55f4 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_layout.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc @@ -1,7 +1,7 @@ // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- // vim: ts=8 sw=2 smarttab -#include "node_layout.h" +#include "node_stage_layout.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_mutable.h" diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_layout.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h similarity index 100% rename from src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_layout.h rename to src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h 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 f6ea16bfd6119..7d5b51978133f 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 @@ -65,17 +65,6 @@ search_result_bs_t binary_search_r( return {rbegin, MatchKindBS::NE}; } -using match_stat_t = int8_t; -constexpr match_stat_t MSTAT_END = -2; // index is search_position_t::end() -constexpr match_stat_t MSTAT_EQ = -1; // key == index -constexpr match_stat_t MSTAT_NE0 = 0; // key == index [pool/shard crush ns/oid]; key < index [snap/gen] -constexpr match_stat_t MSTAT_NE1 = 1; // key == index [pool/shard crush]; key < index [ns/oid] -constexpr match_stat_t MSTAT_NE2 = 2; // key < index [pool/shard crush ns/oid] || - // key == index [pool/shard]; key < index [crush] -constexpr match_stat_t MSTAT_NE3 = 3; // key < index [pool/shard] -constexpr match_stat_t MSTAT_MIN = MSTAT_END; -constexpr match_stat_t MSTAT_MAX = MSTAT_NE3; - inline bool matchable(field_type_t type, match_stat_t mstat) { assert(mstat >= MSTAT_MIN && mstat <= MSTAT_MAX); /* @@ -143,96 +132,6 @@ inline void assert_mstat( } } -template -struct staged_result_t { - using me_t = staged_result_t; - bool is_end() const { return position.is_end(); } - MatchKindBS match() const { - assert(mstat >= MSTAT_MIN && mstat <= MSTAT_MAX); - return (mstat == MSTAT_EQ ? MatchKindBS::EQ : MatchKindBS::NE); - } - - static me_t end() { - return {staged_position_t::end(), nullptr, MSTAT_END}; - } - template - static std::enable_if_t from_nxt( - size_t index, const staged_result_t& nxt_stage_result) { - return {{index, nxt_stage_result.position}, - nxt_stage_result.p_value, - nxt_stage_result.mstat}; - } - - staged_position_t position; - const value_type_t* p_value; - match_stat_t mstat; -}; - -template -staged_result_t&& normalize( - staged_result_t&& result) { return std::move(result); } - -template > -staged_result_t normalize( - staged_result_t&& result) { - // FIXME: assert result.mstat correct - return {normalize(std::move(result.position)), result.p_value, result.mstat}; -} - -/* - * staged infrastructure - */ - -template -struct staged_params_subitems { - using container_t = sub_items_t<_NODE_TYPE>; - static constexpr auto NODE_TYPE = _NODE_TYPE; - static constexpr auto STAGE = STAGE_RIGHT; - - // dummy type in order to make our type system work - // any better solution to get rid of this? - using next_param_t = staged_params_subitems; -}; - -template -struct staged_params_item_iterator { - using container_t = item_iterator_t<_NODE_TYPE>; - static constexpr auto NODE_TYPE = _NODE_TYPE; - static constexpr auto STAGE = STAGE_STRING; - - using next_param_t = staged_params_subitems; -}; - -template -struct staged_params_node_01 { - using container_t = NodeType; - static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; - static constexpr auto STAGE = STAGE_LEFT; - - using next_param_t = staged_params_item_iterator; -}; - -template -struct staged_params_node_2 { - using container_t = NodeType; - static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; - static constexpr auto STAGE = STAGE_STRING; - - using next_param_t = staged_params_subitems; -}; - -template -struct staged_params_node_3 { - using container_t = NodeType; - static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; - static constexpr auto STAGE = STAGE_RIGHT; - - // dummy type in order to make our type system work - // any better solution to get rid of this? - using next_param_t = staged_params_node_3; -}; - #define NXT_STAGE_T staged enum class TrimType { BEFORE, AFTER, AT }; @@ -1314,7 +1213,7 @@ struct staged { assert(false); } - static staged_result_t lower_bound_normalized( + static lookup_result_t lower_bound_normalized( const container_t& container, const full_key_t& key, MatchHistory& history) { @@ -1868,6 +1767,59 @@ struct staged { } }; +/* + * staged infrastructure + */ + +template +struct staged_params_subitems { + using container_t = sub_items_t<_NODE_TYPE>; + static constexpr auto NODE_TYPE = _NODE_TYPE; + static constexpr auto STAGE = STAGE_RIGHT; + + // dummy type in order to make our type system work + // any better solution to get rid of this? + using next_param_t = staged_params_subitems; +}; + +template +struct staged_params_item_iterator { + using container_t = item_iterator_t<_NODE_TYPE>; + static constexpr auto NODE_TYPE = _NODE_TYPE; + static constexpr auto STAGE = STAGE_STRING; + + using next_param_t = staged_params_subitems; +}; + +template +struct staged_params_node_01 { + using container_t = NodeType; + static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; + static constexpr auto STAGE = STAGE_LEFT; + + using next_param_t = staged_params_item_iterator; +}; + +template +struct staged_params_node_2 { + using container_t = NodeType; + static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; + static constexpr auto STAGE = STAGE_STRING; + + using next_param_t = staged_params_subitems; +}; + +template +struct staged_params_node_3 { + using container_t = NodeType; + static constexpr auto NODE_TYPE = NodeType::NODE_TYPE; + static constexpr auto STAGE = STAGE_RIGHT; + + // dummy type in order to make our type system work + // any better solution to get rid of this? + using next_param_t = staged_params_node_3; +}; + template struct _node_to_stage_t; template struct _node_to_stage_t #include "crimson/os/seastore/onode_manager/staged-fltree/fwd.h" +#include "crimson/os/seastore/onode_manager/staged-fltree/node_types.h" namespace crimson::os::seastore::onode { @@ -274,4 +275,55 @@ template<> struct value_type { using type = onode_t; }; template using value_type_t = typename value_type::type; +using match_stat_t = int8_t; +constexpr match_stat_t MSTAT_END = -2; // index is search_position_t::end() +constexpr match_stat_t MSTAT_EQ = -1; // key == index +constexpr match_stat_t MSTAT_NE0 = 0; // key == index [pool/shard crush ns/oid]; key < index [snap/gen] +constexpr match_stat_t MSTAT_NE1 = 1; // key == index [pool/shard crush]; key < index [ns/oid] +constexpr match_stat_t MSTAT_NE2 = 2; // key < index [pool/shard crush ns/oid] || + // key == index [pool/shard]; key < index [crush] +constexpr match_stat_t MSTAT_NE3 = 3; // key < index [pool/shard] +constexpr match_stat_t MSTAT_MIN = MSTAT_END; +constexpr match_stat_t MSTAT_MAX = MSTAT_NE3; + +template +struct staged_result_t { + using me_t = staged_result_t; + bool is_end() const { return position.is_end(); } + MatchKindBS match() const { + assert(mstat >= MSTAT_MIN && mstat <= MSTAT_MAX); + return (mstat == MSTAT_EQ ? MatchKindBS::EQ : MatchKindBS::NE); + } + + static me_t end() { + return {staged_position_t::end(), nullptr, MSTAT_END}; + } + template + static std::enable_if_t from_nxt( + size_t index, const staged_result_t& nxt_stage_result) { + return {{index, nxt_stage_result.position}, + nxt_stage_result.p_value, + nxt_stage_result.mstat}; + } + + staged_position_t position; + const value_type_t* p_value; + match_stat_t mstat; +}; + +template +using lookup_result_t = staged_result_t; + +template +lookup_result_t&& normalize( + lookup_result_t&& result) { return std::move(result); } + +template > +lookup_result_t normalize( + staged_result_t&& result) { + // FIXME: assert result.mstat correct + return {normalize(std::move(result.position)), result.p_value, result.mstat}; +} + } 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 dbcb256f2e945..6bd131cc3ce7b 100644 --- a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc +++ b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc @@ -1,6 +1,7 @@ // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*- // vim: ts=8 sw=2 smarttab +#include #include #include #include @@ -9,10 +10,9 @@ #include #include "crimson/common/log.h" +#include "crimson/os/seastore/onode_manager/staged-fltree/node.h" #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_manager.h" -#include "crimson/os/seastore/onode_manager/staged-fltree/node_impl.h" -#include "crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.h" -#include "crimson/os/seastore/onode_manager/staged-fltree/stages/stage.h" +#include "crimson/os/seastore/onode_manager/staged-fltree/node_layout.h" #include "crimson/os/seastore/onode_manager/staged-fltree/tree.h" #include "test/crimson/gtest_seastar.h" @@ -129,37 +129,30 @@ TEST_F(a_basic_test_t, 2_node_sizes) auto nm = NodeExtentManager::create_dummy(); auto t = make_transaction(); context_t c{*nm, *t}; - std::vector, NodeExtentMutable>> nodes = { - InternalNode0::allocate(c, 1u, false).unsafe_get0().make_pair(), - InternalNode1::allocate(c, 1u, false).unsafe_get0().make_pair(), - InternalNode2::allocate(c, 1u, false).unsafe_get0().make_pair(), - InternalNode3::allocate(c, 1u, false).unsafe_get0().make_pair(), - InternalNode0::allocate(c, 1u, true).unsafe_get0().make_pair(), - InternalNode1::allocate(c, 1u, true).unsafe_get0().make_pair(), - InternalNode2::allocate(c, 1u, true).unsafe_get0().make_pair(), - InternalNode3::allocate(c, 1u, true).unsafe_get0().make_pair(), - LeafNode0::allocate(c, false).unsafe_get0().make_pair(), - LeafNode1::allocate(c, false).unsafe_get0().make_pair(), - LeafNode2::allocate(c, false).unsafe_get0().make_pair(), - LeafNode3::allocate(c, false).unsafe_get0().make_pair(), - LeafNode0::allocate(c, true).unsafe_get0().make_pair(), - LeafNode1::allocate(c, true).unsafe_get0().make_pair(), - LeafNode2::allocate(c, true).unsafe_get0().make_pair(), - LeafNode3::allocate(c, true).unsafe_get0().make_pair() + std::array, 16> nodes = { + InternalNode0::allocate(c, false, 1u).unsafe_get0().make_pair(), + InternalNode1::allocate(c, false, 1u).unsafe_get0().make_pair(), + InternalNode2::allocate(c, false, 1u).unsafe_get0().make_pair(), + InternalNode3::allocate(c, false, 1u).unsafe_get0().make_pair(), + InternalNode0::allocate(c, true, 1u).unsafe_get0().make_pair(), + InternalNode1::allocate(c, true, 1u).unsafe_get0().make_pair(), + InternalNode2::allocate(c, true, 1u).unsafe_get0().make_pair(), + InternalNode3::allocate(c, true, 1u).unsafe_get0().make_pair(), + LeafNode0::allocate(c, false, 0u).unsafe_get0().make_pair(), + LeafNode1::allocate(c, false, 0u).unsafe_get0().make_pair(), + LeafNode2::allocate(c, false, 0u).unsafe_get0().make_pair(), + LeafNode3::allocate(c, false, 0u).unsafe_get0().make_pair(), + LeafNode0::allocate(c, true, 0u).unsafe_get0().make_pair(), + LeafNode1::allocate(c, true, 0u).unsafe_get0().make_pair(), + LeafNode2::allocate(c, true, 0u).unsafe_get0().make_pair(), + LeafNode3::allocate(c, true, 0u).unsafe_get0().make_pair() }; std::ostringstream oss; oss << "\nallocated nodes:"; - auto node_tracker = RootNodeTracker::create(c.nm.is_read_isolated()); - assert(node_tracker->is_clean()); for (auto iter = nodes.begin(); iter != nodes.end(); ++iter) { + oss << "\n "; auto& ref_node = iter->first; - auto& mut = iter->second; - oss << "\n " << *ref_node; - ref_node->test_make_destructable( - c, mut, c.nm.get_super(c.t, *node_tracker).unsafe_get0()); - assert(!node_tracker->is_clean()); - iter->first.reset(); - assert(node_tracker->is_clean()); + ref_node->dump_brief(oss); } logger().info("{}", oss.str()); }); @@ -567,18 +560,71 @@ TEST_F(b_dummy_tree_test_t, 4_split_leaf_node) namespace crimson::os::seastore::onode { class DummyChildPool { - class DummyChild final : public Node { + class DummyChildImpl final : public NodeImpl { public: - virtual ~DummyChild() { + using URef = std::unique_ptr; + DummyChildImpl(const std::set& keys, bool is_level_tail, laddr_t laddr) + : keys{keys}, _is_level_tail{is_level_tail}, _laddr{laddr} { + std::tie(key_view, p_mem_key_view) = build_key_view(*keys.crbegin()); + } + ~DummyChildImpl() override { + std::free(p_mem_key_view); + } + + const std::set& get_keys() const { return keys; } + + void reset(const std::set& _keys, bool level_tail) { + keys = _keys; + _is_level_tail = level_tail; std::free(p_mem_key_view); + std::tie(key_view, p_mem_key_view) = build_key_view(*keys.crbegin()); } + public: + laddr_t laddr() const override { return _laddr; } + bool is_level_tail() const override { return _is_level_tail; } + + protected: + field_type_t field_type() const override { return field_type_t::N0; } + level_t level() const override { return 0u; } + key_view_t get_largest_key_view() const override { return key_view; } + void prepare_mutate(context_t) override { + assert(false && "impossible path"); } + bool is_empty() const override { + assert(false && "impossible path"); } + node_offset_t free_size() const override { + assert(false && "impossible path"); } + key_view_t get_key_view(const search_position_t&) const override { + assert(false && "impossible path"); } + std::ostream& dump(std::ostream&) const override { + assert(false && "impossible path"); } + std::ostream& dump_brief(std::ostream&) const override { + assert(false && "impossible path"); } + void test_copy_to(NodeExtentMutable&) const override { + assert(false && "impossible path"); } + void test_set_tail(NodeExtentMutable&) override { + assert(false && "impossible path"); } + + private: + std::set keys; + bool _is_level_tail; + laddr_t _laddr; + + key_view_t key_view; + void* p_mem_key_view; + }; + + class DummyChild final : public Node { + public: + ~DummyChild() override = default; + node_future<> populate_split( context_t c, std::set>& splitable_nodes) { assert(can_split()); assert(splitable_nodes.find(this) != splitable_nodes.end()); size_t index; + const auto& keys = impl->get_keys(); if (keys.size() == 2) { index = 1; } else { @@ -589,21 +635,22 @@ class DummyChildPool { std::set left_keys(keys.begin(), iter); std::set right_keys(iter, keys.end()); - bool right_is_tail = _is_level_tail; - reset(left_keys, false); - auto right_child = DummyChild::create(right_keys, right_is_tail, pool); + bool right_is_tail = impl->is_level_tail(); + impl->reset(left_keys, false); + auto right_child = DummyChild::create_new(right_keys, right_is_tail, pool); if (!can_split()) { splitable_nodes.erase(this); } if (right_child->can_split()) { splitable_nodes.insert(right_child); } - return this->insert_parent(c, right_child); + return insert_parent(c, right_child); } node_future<> insert_and_split( context_t c, const onode_key_t& insert_key, std::set>& splitable_nodes) { + const auto& keys = impl->get_keys(); assert(keys.size() == 1); auto& key = *keys.begin(); assert(insert_key < key); @@ -611,7 +658,7 @@ class DummyChildPool { std::set new_keys; new_keys.insert(insert_key); new_keys.insert(key); - reset(new_keys, _is_level_tail); + impl->reset(new_keys, impl->is_level_tail()); splitable_nodes.clear(); splitable_nodes.insert(this); @@ -626,15 +673,22 @@ class DummyChildPool { } static Ref create( + const std::set& keys, bool is_level_tail, + laddr_t addr, DummyChildPool& pool) { + auto ref_impl = std::make_unique(keys, is_level_tail, addr); + return new DummyChild(ref_impl.get(), std::move(ref_impl), pool); + } + + static Ref create_new( const std::set& keys, bool is_level_tail, DummyChildPool& pool) { static laddr_t seed = 0; - return new DummyChild(keys, is_level_tail, seed++, pool); + return create(keys, is_level_tail, seed++, pool); } static node_future> create_initial( context_t c, const std::set& keys, DummyChildPool& pool, RootNodeTracker& root_tracker) { - auto initial = create(keys, true, pool); + auto initial = create_new(keys, true, pool); return c.nm.get_super(c.t, root_tracker ).safe_then([c, &pool, initial](auto super) { initial->make_root_new(c, std::move(super)); @@ -644,70 +698,38 @@ class DummyChildPool { }); } - static Ref create_clone( - const std::set& keys, bool is_level_tail, - laddr_t addr, DummyChildPool& pool) { - return new DummyChild(keys, is_level_tail, addr, pool); - } - protected: - bool is_level_tail() const override { return _is_level_tail; } - field_type_t field_type() const override { return field_type_t::N0; } - laddr_t laddr() const override { return _laddr; } - level_t level() const override { return 0u; } - key_view_t get_key_view(const search_position_t&) const override { - assert(false && "impossible path"); } - key_view_t get_largest_key_view() const override { return key_view; } - std::ostream& dump(std::ostream&) const override { - assert(false && "impossible path"); } - std::ostream& dump_brief(std::ostream&) const override { - assert(false && "impossible path"); } - node_future do_lower_bound( - context_t, const key_hobj_t&, MatchHistory&) override { - assert(false && "impossible path"); } - node_future> lookup_smallest(context_t) override { - assert(false && "impossible path"); } - node_future> lookup_largest(context_t) override { - assert(false && "impossible path"); } - void test_make_destructable( - context_t, NodeExtentMutable&, Super::URef&&) override { - assert(false && "impossible path"); } node_future<> test_clone_non_root( context_t, Ref new_parent) const override { assert(!is_root()); auto p_pool_clone = pool.pool_clone_in_progress; assert(p_pool_clone); - auto clone = create_clone(keys, _is_level_tail, _laddr, *p_pool_clone); + auto clone = create( + impl->get_keys(), impl->is_level_tail(), impl->laddr(), *p_pool_clone); clone->as_child(parent_info().position, new_parent); - clone->_laddr = _laddr; return node_ertr::now(); } + node_future> lookup_smallest(context_t) override { + assert(false && "impossible path"); } + node_future> lookup_largest(context_t) override { + assert(false && "impossible path"); } + node_future<> test_clone_root(context_t, RootNodeTracker&) const override { + assert(false && "impossible path"); } + node_future lower_bound_tracked( + context_t, const key_hobj_t&, MatchHistory&) override { + assert(false && "impossible path"); } private: - DummyChild(const std::set& keys, - bool is_level_tail, laddr_t laddr, DummyChildPool& pool) - : keys{keys}, _is_level_tail{is_level_tail}, _laddr{laddr}, pool{pool} { - std::tie(key_view, p_mem_key_view) = build_key_view(*keys.crbegin()); + DummyChild(DummyChildImpl* impl, DummyChildImpl::URef&& ref, DummyChildPool& pool) + : Node(std::move(ref)), impl{impl}, pool{pool} { pool.track_node(this); } - bool can_split() const { return keys.size() > 1; } + bool can_split() const { return impl->get_keys().size() > 1; } - void reset(const std::set& _keys, bool level_tail) { - keys = _keys; - _is_level_tail = level_tail; - std::free(p_mem_key_view); - std::tie(key_view, p_mem_key_view) = build_key_view(*keys.crbegin()); - } - - mutable std::random_device rd; - std::set keys; - bool _is_level_tail; - laddr_t _laddr; + DummyChildImpl* impl; DummyChildPool& pool; - - key_view_t key_view; - void* p_mem_key_view; + mutable std::random_device rd; }; public: -- 2.39.5