From ec80f1c9940ba46793f797e645eaac0c1142eea9 Mon Sep 17 00:00:00 2001 From: Samuel Just Date: Tue, 2 Mar 2021 12:25:13 -0800 Subject: [PATCH] crimson/os/seastore/omap_manager: generalize omap_list to support lower_bound The iterator interface needs both lower and upper bound, generalize list() to support both. Signed-off-by: Samuel Just --- src/crimson/os/seastore/omap_manager.h | 40 +++++++++++++++++-- .../omap_manager/btree/btree_omap_manager.cc | 12 ++++-- .../omap_manager/btree/btree_omap_manager.h | 2 +- .../omap_manager/btree/omap_btree_node.h | 3 +- .../btree/omap_btree_node_impl.cc | 29 +++++++------- .../omap_manager/btree/omap_btree_node_impl.h | 4 +- .../crimson/seastore/test_omap_manager.cc | 6 ++- 7 files changed, 69 insertions(+), 27 deletions(-) diff --git a/src/crimson/os/seastore/omap_manager.h b/src/crimson/os/seastore/omap_manager.h index 721103e8302..914d5856203 100644 --- a/src/crimson/os/seastore/omap_manager.h +++ b/src/crimson/os/seastore/omap_manager.h @@ -18,7 +18,6 @@ namespace crimson::os::seastore { -constexpr size_t MAX_SIZE = std::numeric_limits::max(); std::ostream &operator<<(std::ostream &out, const std::list &rhs); std::ostream &operator<<(std::ostream &out, const std::map &rhs); @@ -97,16 +96,51 @@ public: * it it is not set, list all keys after string start. * @retval listed key->value mapping and next key */ + struct omap_list_config_t { + size_t max_result_size = 128; + bool inclusive = false; + + omap_list_config_t( + size_t max_result_size, + bool inclusive) + : max_result_size(max_result_size), + inclusive(inclusive) {} + omap_list_config_t() {} + omap_list_config_t(const omap_list_config_t &) = default; + omap_list_config_t(omap_list_config_t &&) = default; + omap_list_config_t &operator=(const omap_list_config_t &) = default; + omap_list_config_t &operator=(omap_list_config_t &&) = default; + + static omap_list_config_t with_max(size_t max) { + omap_list_config_t ret{}; + ret.max_result_size = max; + return ret; + } + + static omap_list_config_t with_inclusive(bool inclusive) { + omap_list_config_t ret{}; + ret.inclusive = inclusive; + return ret; + } + + auto with_reduced_max(size_t reduced_by) const { + assert(reduced_by <= max_result_size); + return omap_list_config_t( + max_result_size - reduced_by, + inclusive + ); + } + }; using omap_list_ertr = base_ertr; using omap_list_bare_ret = std::pair< bool, - std::map>; + std::map>>; using omap_list_ret = omap_list_ertr::future; virtual omap_list_ret omap_list( const omap_root_t &omap_root, Transaction &t, const std::optional &start, - size_t max_result_size = MAX_SIZE) = 0; + omap_list_config_t config = omap_list_config_t()) = 0; /** * clear all omap tree key->value mapping 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 75b8f30b385..1c787504dcc 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 @@ -31,7 +31,8 @@ BtreeOMapManager::initialize_omap(Transaction &t) root_extent->set_size(0); omap_node_meta_t meta{1}; root_extent->set_meta(meta); - omap_root_t omap_root = omap_root_t(root_extent->get_laddr(), 1); + omap_root_t omap_root; + omap_root.update(root_extent->get_laddr(), 1); return initialize_omap_ertr::make_ready_future(omap_root); }); } @@ -164,14 +165,17 @@ BtreeOMapManager::omap_list( const omap_root_t &omap_root, Transaction &t, const std::optional &start, - size_t max_result_size = MAX_SIZE) + omap_list_config_t config) { logger().debug("{}", __func__); return get_omap_root( get_omap_context(t), omap_root - ).safe_then([this, &t, &start, max_result_size](auto extent) { - return extent->list(get_omap_context(t), start, max_result_size); + ).safe_then([this, config, &t, &start](auto extent) { + return extent->list( + get_omap_context(t), + start, + 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 6762bdd661b..40f8e525a47 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 @@ -86,7 +86,7 @@ public: const omap_root_t &omap_root, Transaction &t, const std::optional &start, - size_t max_result_size) final; + omap_list_config_t config = omap_list_config_t()) final; omap_clear_ret omap_clear( omap_root_t &omap_root, 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 d508887f3dd..67865b19bcc 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 @@ -70,13 +70,14 @@ struct OMapNode : LogicalCachedExtent { omap_context_t oc, const std::string &key) = 0; + using omap_list_config_t = OMapManager::omap_list_config_t; using list_ertr = base_ertr; using list_bare_ret = OMapManager::omap_list_bare_ret; using list_ret = OMapManager::omap_list_ret; virtual list_ret list( omap_context_t oc, const std::optional &start, - size_t max_result_size) = 0; + omap_list_config_t config) = 0; using clear_ertr = base_ertr; using clear_ret = clear_ertr::future<>; 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 e71260ffd8c..59d8050a212 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 @@ -193,7 +193,7 @@ OMapInnerNode::list_ret OMapInnerNode::list( omap_context_t oc, const std::optional &start, - size_t max_result_size) + omap_list_config_t config) { logger().debug("OMapInnerNode: {}", __func__); @@ -209,9 +209,8 @@ OMapInnerNode::list( [=, &start](auto &biter, auto &eiter, auto &ret) { auto &[complete, result] = ret; return crimson::do_until( - [&, &complete=complete, &result=result, max_result_size, oc, this]() - -> list_ertr::future { - if (biter == eiter || result.size() == max_result_size) { + [&, config, oc, this]() -> list_ertr::future { + if (biter == eiter || result.size() == config.max_result_size) { complete = biter == eiter; return list_ertr::make_ready_future(true); } @@ -219,12 +218,12 @@ OMapInnerNode::list( return omap_load_extent( oc, laddr, get_meta().depth - 1 - ).safe_then([&, max_result_size, oc] (auto &&extent) { + ).safe_then([&, config, oc, this] (auto &&extent) { return extent->list( oc, start, - max_result_size - result.size() - ).safe_then([&, max_result_size](auto &&child_ret) mutable { + config.with_reduced_max(result.size()) + ).safe_then([&, config, this](auto &&child_ret) mutable { auto &[child_complete, child_result] = child_ret; if (result.size() && child_result.size()) { assert(child_result.begin()->first > result.rbegin()->first); @@ -236,8 +235,7 @@ OMapInnerNode::list( child_result.begin(), child_result.end()); biter++; - (void)max_result_size; - assert(child_complete || result.size() == max_result_size); + assert(child_complete || result.size() == config.max_result_size); return list_ertr::make_ready_future(false); }); }); @@ -518,21 +516,24 @@ OMapLeafNode::list_ret OMapLeafNode::list( omap_context_t oc, const std::optional &start, - size_t max_result_size) + omap_list_config_t config) { logger().debug( - "OMapLeafNode::{} start {} max_result_size {}", + "OMapLeafNode::{} start {} max_result_size {} inclusive {}", __func__, start ? start->c_str() : "", - max_result_size + config.max_result_size, + config.inclusive ); auto ret = list_bare_ret(false, {}); auto &[complete, result] = ret; auto iter = start ? - string_upper_bound(*start) : + (config.inclusive ? + string_lower_bound(*start) : + string_upper_bound(*start)) : iter_begin(); - for (; iter != iter_end() && result.size() < max_result_size; iter++) { + for (; iter != iter_end() && result.size() < config.max_result_size; iter++) { result.emplace(std::make_pair(iter->get_key(), iter->get_val())); } 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 fdd6f0a0c94..07e9b3c2c45 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,7 @@ struct OMapInnerNode list_ret list( omap_context_t oc, const std::optional &start, - size_t max_result_size) final; + omap_list_config_t config) final; clear_ret clear(omap_context_t oc) final; @@ -183,7 +183,7 @@ struct OMapLeafNode list_ret list( omap_context_t oc, const std::optional &start, - size_t max_result_size) final; + omap_list_config_t config) final; clear_ret clear( omap_context_t oc) final; diff --git a/src/test/crimson/seastore/test_omap_manager.cc b/src/test/crimson/seastore/test_omap_manager.cc index eacaf4b939a..699ea3a086a 100644 --- a/src/test/crimson/seastore/test_omap_manager.cc +++ b/src/test/crimson/seastore/test_omap_manager.cc @@ -129,7 +129,7 @@ struct omap_manager_test_t : const omap_root_t &omap_root, Transaction &t, const std::optional &start, - size_t max = MAX_SIZE) { + size_t max = 128) { if (start) { logger().debug("list on {}", *start); @@ -137,8 +137,10 @@ struct omap_manager_test_t : logger().debug("list on start"); } + auto config = OMapManager::omap_list_config_t::with_max(max); + config.max_result_size = max; auto [complete, results] = omap_manager->omap_list( - omap_root, t, start, max + omap_root, t, start, config ).unsafe_get0(); auto it = start ? -- 2.39.5