From b8d1ebb31cb6e2abdc6610e0f4aa1c34a656e1ce Mon Sep 17 00:00:00 2001 From: Xinyu Huang Date: Thu, 8 Sep 2022 01:16:15 +0000 Subject: [PATCH] crimson/os/seastore/omap: support two borders list method Signed-off-by: Xinyu Huang --- src/crimson/os/seastore/omap_manager.h | 11 +- .../omap_manager/btree/btree_omap_manager.cc | 18 ++- .../omap_manager/btree/btree_omap_manager.h | 3 +- .../omap_manager/btree/omap_btree_node.h | 3 +- .../btree/omap_btree_node_impl.cc | 147 +++++++++++------- .../omap_manager/btree/omap_btree_node_impl.h | 6 +- src/crimson/os/seastore/seastore.cc | 16 +- .../crimson/seastore/test_omap_manager.cc | 43 +++-- 8 files changed, 154 insertions(+), 93 deletions(-) diff --git a/src/crimson/os/seastore/omap_manager.h b/src/crimson/os/seastore/omap_manager.h index 6211d0bf0aefd..2520238a0b738 100644 --- a/src/crimson/os/seastore/omap_manager.h +++ b/src/crimson/os/seastore/omap_manager.h @@ -100,8 +100,12 @@ public: * * @param omap_root: omap btree root information * @param t: current transaction - * @param start: nullopt sorts before any string, behavior - * based on config.inclusive + * @param first: range start, nullopt sorts before any string, + * behavior based on config.inclusive, + * must alive during the call + * @param last: range end, nullopt sorts after any string, + * behavior based on config.inclusive, + * must alive during the call * @param config: see below for params * @retval listed key->value and bool indicating complete */ @@ -151,7 +155,8 @@ public: virtual omap_list_ret omap_list( const omap_root_t &omap_root, Transaction &t, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config = omap_list_config_t()) = 0; /** diff --git a/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.cc b/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.cc index e6d25fbda9b9f..bbc87965195bc 100644 --- a/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.cc +++ b/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.cc @@ -191,22 +191,30 @@ BtreeOMapManager::omap_list_ret BtreeOMapManager::omap_list( const omap_root_t &omap_root, Transaction &t, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) { LOG_PREFIX(BtreeOMapManager::omap_list); - if (start) { - DEBUGT("{}, start: {}", t, omap_root, *start); + if (first && last) { + DEBUGT("{}, first: {}, last: {}", t, omap_root, *first, *last); + assert(last >= first); + } else if (first) { + DEBUGT("{}, first: {}", t, omap_root, *first); + } else if (last) { + DEBUGT("{}, last: {}", t, omap_root, *last); } else { DEBUGT("{}", t, omap_root); } + return get_omap_root( get_omap_context(t, omap_root.hint), omap_root - ).si_then([this, config, &t, &start, &omap_root](auto extent) { + ).si_then([this, config, &t, &first, &last, &omap_root](auto extent) { return extent->list( get_omap_context(t, omap_root.hint), - start, + first, + last, config); }); } diff --git a/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.h b/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.h index 87ce68235a06b..a904951bd0821 100644 --- a/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.h +++ b/src/crimson/os/seastore/omap_manager/btree/btree_omap_manager.h @@ -90,7 +90,8 @@ public: omap_list_ret omap_list( const omap_root_t &omap_root, Transaction &t, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config = omap_list_config_t()) final; omap_clear_ret omap_clear( diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h index 5ac2c167f1b4e..795daeddb11c5 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h @@ -77,7 +77,8 @@ struct OMapNode : LogicalCachedExtent { using list_ret = OMapManager::omap_list_ret; virtual list_ret list( omap_context_t oc, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) = 0; using clear_iertr = base_iertr; diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc index 6d6a2570007f9..38b9dd66fadd3 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc @@ -195,76 +195,98 @@ OMapInnerNode::rm_key(omap_context_t oc, const std::string &key) OMapInnerNode::list_ret OMapInnerNode::list( omap_context_t oc, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) { LOG_PREFIX(OMapInnerNode::list); - if (start) { - DEBUGT("start={}, this: {}", oc.t, *start, *this); + if (first && last) { + DEBUGT("first: {}, last: {}, this: {}", oc.t, *first, *last, *this); + assert(*first <= *last); + } else if (first) { + DEBUGT("first: {}, this: {}", oc.t, *first, *this); + } else if (last) { + DEBUGT("last: {}, this: {}", oc.t, *last, *this); } else { DEBUGT("this: {}", oc.t, *this); } - auto child_iter = start ? - get_containing_child(*start) : + auto first_iter = first ? + get_containing_child(*first) : iter_cbegin(); - assert(child_iter != iter_cend()); + auto last_iter = last ? + get_containing_child(*last) + 1: + iter_cend(); + assert(first_iter != iter_cend()); return seastar::do_with( - child_iter, - iter_cend(), + first_iter, + last_iter, + iter_t(first_iter), list_bare_ret(false, {}), - true, - start, - [this, oc, config]( - auto &biter, - auto &eiter, - auto &ret, - bool &first_entry, - auto &start) + [this, &first, &last, oc, config]( + auto &fiter, + auto &liter, + auto &iter, + auto &ret) { auto &complete = std::get<0>(ret); auto &result = std::get<1>(ret); return trans_intr::repeat( - [&, config, oc, this]() -> list_iertr::future { - if (biter == eiter || result.size() == config.max_result_size) { - complete = biter == eiter; - return list_iertr::make_ready_future( - seastar::stop_iteration::yes); - } - auto laddr = biter->get_val(); - return omap_load_extent( - oc, laddr, - get_meta().depth - 1 - ).si_then([&, config, oc] (auto &&extent) { + [&, config, oc, this]() -> list_iertr::future + { + if (iter == liter || result.size() == config.max_result_size) { + complete = iter == liter; + return list_iertr::make_ready_future( + seastar::stop_iteration::yes); + } + auto laddr = iter->get_val(); + return omap_load_extent( + oc, laddr, + get_meta().depth - 1 + ).si_then([&, config, oc](auto &&extent) { + return seastar::do_with( + iter == fiter ? first : std::optional(std::nullopt), + iter == liter - 1 ? last : std::optional(std::nullopt), + [&result, extent = std::move(extent), config, oc]( + auto &nfirst, + auto &nlast) { return extent->list( oc, - first_entry ? start : std::nullopt, - config.with_reduced_max(result.size()) - ).si_then([&, config](auto &&child_ret) mutable { - boost::ignore_unused(config); // avoid clang warning; - auto &[child_complete, child_result] = child_ret; - if (result.size() && child_result.size()) { - assert(child_result.begin()->first > result.rbegin()->first); + nfirst, + nlast, + config.with_reduced_max(result.size())); + }).si_then([&, config](auto &&child_ret) mutable { + boost::ignore_unused(config); // avoid clang warning; + auto &[child_complete, child_result] = child_ret; + if (result.size() && child_result.size()) { + assert(child_result.begin()->first > result.rbegin()->first); + } + if (child_result.size() && first && iter == fiter) { + if (config.inclusive) { + assert(child_result.begin()->first >= *first); + } else { + assert(child_result.begin()->first > *first); } - if (child_result.size() && start && first_entry) { - if (config.inclusive) { - assert(child_result.begin()->first >= *start); - } else { - assert(child_result.begin()->first > *start); - } + } + if (child_result.size() && last && iter == liter - 1) { + auto biter = --(child_result.end()); + if (config.inclusive) { + assert(biter->first <= *last); + } else { + assert(biter->first < *last); } - result.merge(std::move(child_result)); - ++biter; - assert(child_complete || result.size() == config.max_result_size); - first_entry = false; - return list_iertr::make_ready_future( - seastar::stop_iteration::no); - }); - }); - }).si_then([&ret, ref = OMapNodeRef(this)] { - return list_iertr::make_ready_future(std::move(ret)); - }); + } + result.merge(std::move(child_result)); + ++iter; + assert(child_complete || result.size() == config.max_result_size); + return list_iertr::make_ready_future( + seastar::stop_iteration::no); + }); + }); + }).si_then([&ret, ref = OMapNodeRef(this)] { + return list_iertr::make_ready_future(std::move(ret)); + }); }); } @@ -586,31 +608,38 @@ OMapLeafNode::rm_key(omap_context_t oc, const std::string &key) OMapLeafNode::list_ret OMapLeafNode::list( omap_context_t oc, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) { LOG_PREFIX(OMapLeafNode::list); DEBUGT( - "start {} max_result_size {} inclusive {}, this: {}", + "first {} last {} max_result_size {} inclusive {}, this: {}", oc.t, - start ? start->c_str() : "", + first ? first->c_str() : "", + last ? last->c_str() : "", config.max_result_size, config.inclusive, *this ); auto ret = list_bare_ret(false, {}); auto &[complete, result] = ret; - auto iter = start ? + auto iter = first ? (config.inclusive ? - string_lower_bound(*start) : - string_upper_bound(*start)) : + string_lower_bound(*first) : + string_upper_bound(*first)) : iter_begin(); + auto liter = last ? + (config.inclusive ? + string_upper_bound(*last) : + string_lower_bound(*last)) : + iter_end(); - for (; iter != iter_end() && result.size() < config.max_result_size; iter++) { + for (; iter != liter && result.size() < config.max_result_size; iter++) { result.emplace(std::make_pair(iter->get_key(), iter->get_val())); } - complete = (iter == iter_end()); + complete = (iter == liter); return list_iertr::make_ready_future( std::move(ret)); diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h index 500939d5f5d4b..574f29bea9668 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h @@ -69,7 +69,8 @@ struct OMapInnerNode list_ret list( omap_context_t oc, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) final; clear_ret clear(omap_context_t oc) final; @@ -186,7 +187,8 @@ struct OMapLeafNode list_ret list( omap_context_t oc, - const std::optional &start, + const std::optional &first, + const std::optional &last, omap_list_config_t config) final; clear_ret clear( diff --git a/src/crimson/os/seastore/seastore.cc b/src/crimson/os/seastore/seastore.cc index 27c1cc515497a..34ea713891c42 100644 --- a/src/crimson/os/seastore/seastore.cc +++ b/src/crimson/os/seastore/seastore.cc @@ -897,9 +897,10 @@ SeaStore::_omap_list_ret SeaStore::_omap_list( BtreeOMapManager(*transaction_manager), root, start, - [&t, config](auto &manager, auto& root, auto& start) { - return manager.omap_list(root, t, start, config); - }); + std::optional(std::nullopt), + [&t, config](auto &manager, auto &root, auto &start, auto &end) { + return manager.omap_list(root, t, start, end, config); + }); } SeaStore::omap_get_values_ret_t SeaStore::omap_list( @@ -918,13 +919,13 @@ SeaStore::omap_get_values_ret_t SeaStore::omap_list( Transaction::src_t::READ, "omap_list", op_type_t::OMAP_LIST, - [this, config, &start](auto &t, auto &onode) { + [this, config, start](auto &t, auto &onode) { return _omap_list( onode, onode.get_layout().omap_root, t, start, config ); - }); + }); } SeaStore::omap_get_values_ret_t SeaStore::omap_get_values( @@ -932,8 +933,9 @@ SeaStore::omap_get_values_ret_t SeaStore::omap_get_values( const ghobject_t &oid, const std::optional &start) { - return seastar::do_with(oid, start, - [this, ch=std::move(ch)](auto& oid, auto& start) { + return seastar::do_with( + oid, + [this, start, ch=std::move(ch)](auto& oid) { return omap_list( ch, oid, start, OMapManager::omap_list_config_t::with_inclusive(false)); diff --git a/src/test/crimson/seastore/test_omap_manager.cc b/src/test/crimson/seastore/test_omap_manager.cc index f485097df4129..c6e4601a2c8f2 100644 --- a/src/test/crimson/seastore/test_omap_manager.cc +++ b/src/test/crimson/seastore/test_omap_manager.cc @@ -140,14 +140,19 @@ struct omap_manager_test_t : void list( const omap_root_t &omap_root, Transaction &t, - const std::optional &start, + const std::optional &first, + const std::optional &last, size_t max = 128, bool inclusive = false) { - if (start) { - logger().debug("list on {}", *start); + if (first && last) { + logger().debug("list on {} ~ {}", *first, *last); + } else if (first) { + logger().debug("list on {} ~ end", *first); + } else if (last) { + logger().debug("list on start ~ {}", *last); } else { - logger().debug("list on start"); + logger().debug("list on start ~ end"); } auto config = OMapManager::omap_list_config_t::with_max(max); @@ -157,17 +162,25 @@ struct omap_manager_test_t : auto [complete, results] = with_trans_intr( t, [&, this](auto &t) { - return omap_manager->omap_list(omap_root, t, start, config); + return omap_manager->omap_list(omap_root, t, first, last, config); }).unsafe_get0(); - test_omap_t::iterator it; - if (start) { + test_omap_t::iterator it, lit; + if (first) { it = config.inclusive ? - test_omap_mappings.lower_bound(*start) : - test_omap_mappings.upper_bound(*start); + test_omap_mappings.lower_bound(*first) : + test_omap_mappings.upper_bound(*first); } else { it = test_omap_mappings.begin(); } + if (last) { + lit = config.inclusive ? + test_omap_mappings.upper_bound(*last) : + test_omap_mappings.lower_bound(*last); + } else { + lit = test_omap_mappings.end(); + } + for (auto &&[k, v]: results) { EXPECT_NE(it, test_omap_mappings.end()); if (it == test_omap_mappings.end()) @@ -176,7 +189,7 @@ struct omap_manager_test_t : EXPECT_EQ(v, it->second); it++; } - if (it == test_omap_mappings.end()) { + if (it == lit) { EXPECT_TRUE(complete); } else { EXPECT_EQ(results.size(), max); @@ -397,17 +410,17 @@ TEST_F(omap_manager_test_t, force_split_listkeys_list_clear) { auto t = create_read_transaction(); - list(omap_root, *t, std::nullopt); + list(omap_root, *t, std::nullopt, std::nullopt); } { auto t = create_read_transaction(); - list(omap_root, *t, temp, 100); + list(omap_root, *t, temp, std::nullopt, 100); } { auto t = create_read_transaction(); - list(omap_root, *t, temp, 100, true); + list(omap_root, *t, temp, std::nullopt, 100, true); } { @@ -440,12 +453,12 @@ TEST_F(omap_manager_test_t, force_inner_node_split_list) { auto t = create_read_transaction(); - list(omap_root, *t, temp, 10240); + list(omap_root, *t, temp, std::nullopt, 10240); } { auto t = create_read_transaction(); - list(omap_root, *t, temp, 10240, true); + list(omap_root, *t, temp, std::nullopt, 10240, true); } { -- 2.39.5