From c9360d414fc24326b66fc992cd09cbd8bed04f0e Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Wed, 3 Mar 2021 15:48:16 +0800 Subject: [PATCH] crimson/onode-staged-tree: implement tree-level erase interfaces Define and implement erase related interfaces from BTree, BTree::Cursor, tree_cursor_t, Node to LeafNode. Signed-off-by: Yingxin Cheng --- .../staged-fltree/fltree_onode_manager.cc | 2 +- .../onode_manager/staged-fltree/node.cc | 32 +++++++++ .../onode_manager/staged-fltree/node.h | 23 +++++++ .../onode_manager/staged-fltree/tree.h | 68 ++++++++++++------- .../onode_manager/staged-fltree/value.h | 3 + 5 files changed, 102 insertions(+), 26 deletions(-) diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/fltree_onode_manager.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/fltree_onode_manager.cc index 031bf42e7ae..b80e237e763 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/fltree_onode_manager.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/fltree_onode_manager.cc @@ -105,7 +105,7 @@ FLTreeOnodeManager::write_dirty_ret FLTreeOnodeManager::write_dirty( return seastar::now(); } case FLTreeOnode::status_t::DELETED: { - return tree.erase(trans, flonode).safe_then([](auto) {}); + return tree.erase(trans, flonode); } case FLTreeOnode::status_t::STABLE: { return seastar::now(); 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 2c64f94810d..578e9101178 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.cc @@ -95,6 +95,13 @@ void tree_cursor_t::assert_next_to( #endif } +tree_cursor_t::future> +tree_cursor_t::erase(context_t c, bool get_next) +{ + assert(is_tracked()); + return ref_leaf_node->erase(c, position, get_next); +} + MatchKindCMP tree_cursor_t::compare_to( const tree_cursor_t& o, value_magic_t magic) const { @@ -322,6 +329,23 @@ node_future, bool>> Node::insert( ); } +node_future Node::erase( + context_t c, const key_hobj_t& key) +{ + return lower_bound(c, key).safe_then([c] (auto result) { + if (result.match() != MatchKindBS::EQ) { + return node_ertr::make_ready_future(0); + } + auto ref_cursor = result.p_cursor; + return ref_cursor->erase(c, false + ).safe_then([ref_cursor] (auto next_cursor) { + assert(ref_cursor->is_invalid()); + assert(!next_cursor); + return std::size_t(1); + }); + }); +} + node_future Node::get_tree_stats(context_t c) { return seastar::do_with( @@ -870,6 +894,14 @@ LeafNode::get_next_cursor(context_t c, const search_position_t& pos) } } +node_future> +LeafNode::erase(context_t c, const search_position_t& pos, bool get_next) +{ + ceph_abort("not implemented"); + return node_ertr::make_ready_future>( + tree_cursor_t::get_invalid()); +} + node_future<> LeafNode::extend_value( context_t c, const search_position_t& pos, value_size_t extend_size) { 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 7bca8f3ec63..778d386c066 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node.h @@ -128,6 +128,9 @@ class tree_cursor_t final /// Check that this is next to prv void assert_next_to(const tree_cursor_t&, value_magic_t) const; + /// Erases the key-value pair from tree. + future> erase(context_t, bool get_next); + MatchKindCMP compare_to(const tree_cursor_t&, value_magic_t) const; // public to Value @@ -352,6 +355,15 @@ class Node node_future, bool>> insert( context_t, const key_hobj_t&, value_config_t); + /** + * erase + * + * Removes a key-value pair from the sub-tree formed by this node. + * + * Returns the number of erased key-value pairs (0 or 1). + */ + node_future erase(context_t, const key_hobj_t&); + /// Recursively collects the statistics of the sub-tree formed by this node node_future get_tree_stats(context_t); @@ -559,6 +571,17 @@ class LeafNode final : public Node { std::tuple get_kv(const search_position_t&) const; node_future> get_next_cursor(context_t, const search_position_t&); + /** + * erase + * + * Removes a key-value pair from the position. + * + * If get_next is true, returns the cursor pointing to the next key-value + * pair that followed the erased element, which can be nullptr if is end. + */ + node_future> erase( + context_t, const search_position_t&, bool get_next); + template void do_track_cursor(tree_cursor_t& cursor) { if constexpr (VALIDATE) { diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h b/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h index 298698d4d47..06e9ca11429 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/tree.h @@ -18,14 +18,11 @@ /** * tree.h * - * An example implementation to expose tree interfaces to users. The current - * interface design is based on: - * - ceph::os::Transaction::create/touch/remove() - * - ceph::ObjectStore::collection_list() - * - ceph::BlueStore::get_onode() - * - db->get_iterator(PREFIIX_OBJ) by ceph::BlueStore::fsck() - * - * TODO: Redesign the interfaces based on real onode manager requirements. + * A special-purpose and b-tree-based implementation that: + * - Fulfills requirements of OnodeManager to index ordered onode key-values; + * - Runs above seastore block and transaction layer; + * - Specially optimized for onode key structures and seastore + * delta/transaction semantics; */ namespace crimson::os::seastore::onode { @@ -113,6 +110,21 @@ class Btree { }); } + btree_future erase(Transaction& t) { + assert(!is_end()); + auto this_obj = *this; + return p_cursor->erase(p_tree->get_context(t), true + ).safe_then([this_obj, this] (Ref next_cursor) { + assert(p_cursor->is_invalid()); + if (next_cursor) { + assert(!next_cursor->is_end()); + return Cursor{p_tree, next_cursor}; + } else { + return Cursor{p_tree}; + } + }); + } + private: Cursor(Btree* p_tree, Ref _p_cursor) : p_tree(p_tree) { if (_p_cursor->is_invalid()) { @@ -213,6 +225,10 @@ class Btree { ); } + btree_future get_next(Transaction& t, Cursor& cursor) { + return cursor.get_next(t); + } + /* * modifiers */ @@ -236,27 +252,29 @@ class Btree { ); } - btree_future erase(Transaction& t, const ghobject_t& obj) { - // TODO - return btree_ertr::make_ready_future(0u); - } - - btree_future erase(Transaction &t, Cursor& pos) { - // TODO - return btree_ertr::make_ready_future( - Cursor::make_end(this)); + btree_future erase(Transaction& t, const ghobject_t& obj) { + return seastar::do_with( + full_key_t(obj), + [this, &t](auto& key) -> btree_future { + return get_root(t).safe_then([this, &t, &key](auto root) { + return root->erase(get_context(t), key); + }); + } + ); } - btree_future erase(Transaction &t, Cursor& first, Cursor& last) { - // TODO - return btree_ertr::make_ready_future( - Cursor::make_end(this)); + btree_future erase(Transaction& t, Cursor& pos) { + return pos.erase(t); } - btree_future erase(Transaction &t, Value &value) { - // TODO - return btree_ertr::make_ready_future( - Cursor::make_end(this)); + btree_future<> erase(Transaction& t, Value& value) { + assert(value.is_tracked()); + auto ref_cursor = value.p_cursor; + return ref_cursor->erase(get_context(t), false + ).safe_then([ref_cursor] (auto next_cursor) { + assert(ref_cursor->is_invalid()); + assert(!next_cursor); + }); } /* diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/value.h b/src/crimson/os/seastore/onode_manager/staged-fltree/value.h index 4cbdd482595..207e3c58eb8 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/value.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/value.h @@ -233,6 +233,9 @@ class Value { NodeExtentManager& nm; const ValueBuilder& vb; Ref p_cursor; + + template + friend class Btree; }; /** -- 2.39.5