From 7eb43fa41d14aa7a66df777a6fa928823d098039 Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Mon, 7 Dec 2020 09:40:31 +0800 Subject: [PATCH] crimson/staged-onode-tree: use LT, EQ, GT for comparison results Signed-off-by: Yingxin Cheng --- .../onode_manager/staged-fltree/fwd.h | 14 ++--- .../onode_manager/staged-fltree/node_layout.h | 10 +-- .../onode_manager/staged-fltree/node_types.h | 10 +-- .../staged-fltree/stages/key_layout.h | 8 +-- .../staged-fltree/stages/stage.h | 62 +++++++++---------- .../staged-fltree/stages/stage_types.h | 36 +++++------ 6 files changed, 70 insertions(+), 70 deletions(-) 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 89214af1c105f..c45d60505dbef 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/fwd.h @@ -57,12 +57,12 @@ constexpr node_offset_t NODE_BLOCK_SIZE = DISK_BLOCK_SIZE * 1u; enum class MatchKindBS : int8_t { NE = -1, EQ = 0 }; -enum class MatchKindCMP : int8_t { NE = -1, EQ = 0, PO }; +enum class MatchKindCMP : int8_t { LT = -1, EQ = 0, GT }; inline MatchKindCMP toMatchKindCMP(int value) { if (value > 0) { - return MatchKindCMP::PO; + return MatchKindCMP::GT; } else if (value < 0) { - return MatchKindCMP::NE; + return MatchKindCMP::LT; } else { return MatchKindCMP::EQ; } @@ -79,10 +79,10 @@ inline MatchKindCMP toMatchKindCMP( } inline MatchKindCMP reverse(MatchKindCMP cmp) { - if (cmp == MatchKindCMP::NE) { - return MatchKindCMP::PO; - } else if (cmp == MatchKindCMP::PO) { - return MatchKindCMP::NE; + if (cmp == MatchKindCMP::LT) { + return MatchKindCMP::GT; + } else if (cmp == MatchKindCMP::GT) { + return MatchKindCMP::LT; } else { return cmp; } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h index b651cc0cf12f3..4cf691675e8bf 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/node_layout.h @@ -223,7 +223,7 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { auto& node_stage = extent.read(); if constexpr (NODE_TYPE == node_type_t::LEAF) { if (unlikely(node_stage.keys() == 0)) { - history.set(MatchKindCMP::NE); + history.set(MatchKindCMP::LT); return lookup_result_t::end(); } } @@ -252,16 +252,16 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { } #endif - // calculate MSTAT_NE3 + // calculate MSTAT_LT3 if constexpr (FIELD_TYPE == field_type_t::N0) { // currently only internal node checks mstat if constexpr (NODE_TYPE == node_type_t::INTERNAL) { - if (result_raw.mstat == MSTAT_NE2) { + if (result_raw.mstat == MSTAT_LT2) { auto cmp = compare_to( key, node_stage[result_raw.position.index].shard_pool); - assert(cmp != MatchKindCMP::PO); + assert(cmp != MatchKindCMP::GT); if (cmp != MatchKindCMP::EQ) { - result_raw.mstat = MSTAT_NE3; + result_raw.mstat = MSTAT_LT3; } } } 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 512dcaece94ba..8452168e40cc7 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 @@ -50,12 +50,12 @@ struct laddr_packed_t { 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] || +constexpr match_stat_t MSTAT_LT0 = 0; // key == index [pool/shard crush ns/oid]; key < index [snap/gen] +constexpr match_stat_t MSTAT_LT1 = 1; // key == index [pool/shard crush]; key < index [ns/oid] +constexpr match_stat_t MSTAT_LT2 = 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_LT3 = 3; // key < index [pool/shard] constexpr match_stat_t MSTAT_MIN = MSTAT_END; -constexpr match_stat_t MSTAT_MAX = MSTAT_NE3; +constexpr match_stat_t MSTAT_MAX = MSTAT_LT3; } 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 9212d81645422..d4e994ec46dfd 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 @@ -294,9 +294,9 @@ inline MatchKindCMP compare_to(const string_view_masked_t& l, const string_view_ } else if (l_type == r_type) { return MatchKindCMP::EQ; } else if (l_type == Type::MIN || r_type == Type::MAX) { - return MatchKindCMP::NE; + return MatchKindCMP::LT; } else { // l_type == Type::MAX || r_type == Type::MIN - return MatchKindCMP::PO; + return MatchKindCMP::GT; } } inline MatchKindCMP compare_to(std::string_view l, const string_view_masked_t& r) { @@ -304,9 +304,9 @@ inline MatchKindCMP compare_to(std::string_view l, const string_view_masked_t& r assert(l.length()); auto r_type = r.get_type(); if (r_type == Type::MIN) { - return MatchKindCMP::PO; + return MatchKindCMP::GT; } else if (r_type == Type::MAX) { - return MatchKindCMP::NE; + return MatchKindCMP::LT; } else { // r_type == Type::STR assert(r.size()); return toMatchKindCMP(l, r.to_string_view()); 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 ceaf2992ad5f2..9d8a5e1abd4fb 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 @@ -31,9 +31,9 @@ search_result_bs_t binary_search( // do not copy if return value is reference decltype(f_get_key(mid)) target = f_get_key(mid); auto match = compare_to(key, target); - if (match == MatchKindCMP::NE) { + if (match == MatchKindCMP::LT) { end = mid; - } else if (match == MatchKindCMP::PO) { + } else if (match == MatchKindCMP::GT) { begin = mid + 1; } else { return {mid, MatchKindBS::EQ}; @@ -87,23 +87,23 @@ inline void assert_mstat( const full_key_t& key, const full_key_t& index, match_stat_t mstat) { - assert(mstat >= MSTAT_MIN && mstat <= MSTAT_NE2); + assert(mstat >= MSTAT_MIN && mstat <= MSTAT_LT2); // key < index ... switch (mstat) { case MSTAT_EQ: break; - case MSTAT_NE0: - assert(compare_to(key, index.snap_gen_packed()) == MatchKindCMP::NE); + case MSTAT_LT0: + assert(compare_to(key, index.snap_gen_packed()) == MatchKindCMP::LT); break; - case MSTAT_NE1: - assert(compare_to(key, index.ns_oid_view()) == MatchKindCMP::NE); + case MSTAT_LT1: + assert(compare_to(key, index.ns_oid_view()) == MatchKindCMP::LT); break; - case MSTAT_NE2: + case MSTAT_LT2: if (index.has_shard_pool()) { assert(compare_to(key, shard_pool_crush_t{ - index.shard_pool_packed(), index.crush_packed()}) == MatchKindCMP::NE); + index.shard_pool_packed(), index.crush_packed()}) == MatchKindCMP::LT); } else { - assert(compare_to(key, index.crush_packed()) == MatchKindCMP::NE); + assert(compare_to(key, index.crush_packed()) == MatchKindCMP::LT); } break; default: @@ -113,12 +113,12 @@ inline void assert_mstat( switch (mstat) { case MSTAT_EQ: assert(compare_to(key, index.snap_gen_packed()) == MatchKindCMP::EQ); - case MSTAT_NE0: + case MSTAT_LT0: if (!index.has_ns_oid()) break; assert(index.ns_oid_view().type() == ns_oid_view_t::Type::MAX || compare_to(key, index.ns_oid_view()) == MatchKindCMP::EQ); - case MSTAT_NE1: + case MSTAT_LT1: if (!index.has_crush()) break; assert(compare_to(key, index.crush_packed()) == MatchKindCMP::EQ); @@ -303,7 +303,7 @@ struct staged { if (exclude_last) { assert(end_index); --end_index; - assert(compare_to(key, container[end_index]) == MatchKindCMP::NE); + assert(compare_to(key, container[end_index]) == MatchKindCMP::LT); } auto ret = binary_search(key, _index, end_index, [this] (size_t index) { return container[index]; }); @@ -570,11 +570,11 @@ struct staged { assert(index() == 0); do { if (exclude_last && is_last()) { - assert(compare_to(key, get_key()) == MatchKindCMP::NE); + assert(compare_to(key, get_key()) == MatchKindCMP::LT); return MatchKindBS::NE; } auto match = compare_to(key, get_key()); - if (match == MatchKindCMP::NE) { + if (match == MatchKindCMP::LT) { return MatchKindBS::NE; } else if (match == MatchKindCMP::EQ) { return MatchKindBS::EQ; @@ -920,21 +920,21 @@ struct staged { // lookup is short-circuited if constexpr (!IS_BOTTOM) { assert(history.get().has_value()); - if (history.is_PO()) { + if (history.is_GT()) { auto iter = iterator_t(container); bool test_key_equal; if constexpr (STAGE == STAGE_STRING) { // TODO(cross-node string dedup) // test_key_equal = (iter.get_key().type() == ns_oid_view_t::Type::MIN); auto cmp = compare_to(key, iter.get_key()); - assert(cmp != MatchKindCMP::PO); + assert(cmp != MatchKindCMP::GT); test_key_equal = (cmp == MatchKindCMP::EQ); } else { auto cmp = compare_to(key, iter.get_key()); // From history, key[stage] == parent[stage][index - 1] // which should be the smallest possible value for all // index[stage][*] - assert(cmp != MatchKindCMP::PO); + assert(cmp != MatchKindCMP::GT); test_key_equal = (cmp == MatchKindCMP::EQ); } if (test_key_equal) { @@ -945,7 +945,7 @@ struct staged { } } } - // IS_BOTTOM || !history.is_PO() + // IS_BOTTOM || !history.is_GT() auto iter = iterator_t(container); iter.seek_last(); if constexpr (STAGE == STAGE_STRING) { @@ -965,12 +965,12 @@ struct staged { auto nxt_container = iter.get_nxt_container(); auto nxt_result = NXT_STAGE_T::template lower_bound( nxt_container, key, history, index_key); - // !history.is_PO() means + // !history.is_GT() means // key[stage+1 ...] <= index[stage+1 ...][*] assert(!nxt_result.is_end()); return result_t::from_nxt(iter.index(), nxt_result); } - } else if (*history.get() == MatchKindCMP::NE) { + } else if (*history.get() == MatchKindCMP::LT) { exclude_last = true; } } @@ -979,18 +979,18 @@ struct staged { if (iter.is_end()) { assert(!exclude_last); assert(bs_match == MatchKindBS::NE); - history.set(MatchKindCMP::PO); + history.set(MatchKindCMP::GT); return result_t::end(); } history.set(bs_match == MatchKindBS::EQ ? - MatchKindCMP::EQ : MatchKindCMP::NE); + MatchKindCMP::EQ : MatchKindCMP::LT); if constexpr (IS_BOTTOM) { if constexpr (GET_KEY) { index_key->set(iter.get_key()); } auto value_ptr = iter.get_p_value(); return result_t{{iter.index()}, value_ptr, - (bs_match == MatchKindBS::EQ ? MSTAT_EQ : MSTAT_NE0)}; + (bs_match == MatchKindBS::EQ ? MSTAT_EQ : MSTAT_LT0)}; } else { if (bs_match == MatchKindBS::EQ) { return nxt_lower_bound(key, iter, history, index_key); @@ -1047,7 +1047,7 @@ struct staged { nxt_container, key, value, position.nxt, false); } } else { - assert(match == MatchKindCMP::NE); + assert(match == MatchKindCMP::LT); if (index == 0) { // already the first index, so insert at the current index return {STAGE, insert_size(key, value)}; @@ -1061,7 +1061,7 @@ struct staged { // XXX(multi-type): when key is from a different type of node auto match = compare_to(key, iter.get_key()); - if (match == MatchKindCMP::PO) { + if (match == MatchKindCMP::GT) { // key doesn't match both indexes, so insert at the current index ++index; return {STAGE, insert_size(key, value)}; @@ -1132,17 +1132,17 @@ struct staged { --insert_stage; } - if (history.is_PO()) { + if (history.is_GT()) { if (position.is_end()) { // no need to compensate insert position assert(insert_stage <= STAGE && "impossible insert stage"); } else if (position == position_t::begin()) { // I must be short-circuited by staged::smallest_result() // in staged::lower_bound(), so we need to rely on mstat instead - assert(mstat >= MSTAT_NE0 && mstat <= MSTAT_NE3); - if (mstat == MSTAT_NE0) { + assert(mstat >= MSTAT_LT0 && mstat <= MSTAT_LT3); + if (mstat == MSTAT_LT0) { insert_stage = STAGE_RIGHT; - } else if (mstat == MSTAT_NE1) { + } else if (mstat == MSTAT_LT1) { insert_stage = STAGE_STRING; } else { insert_stage = STAGE_LEFT; @@ -1336,7 +1336,7 @@ struct staged { break; } else { ++iter; - assert(compare_to(key, iter.get_key()) == MatchKindCMP::NE); + assert(compare_to(key, iter.get_key()) == MatchKindCMP::LT); key = iter.get_key(); } } while (true); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h index e7c9826deaf57..2bd90d3e5ac27 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/stage_types.h @@ -23,13 +23,13 @@ constexpr auto STAGE_BOTTOM = STAGE_RIGHT; // TODO: replace by // using match_history_t = int8_t; // left_m, str_m, right_m -// 3: PO, -// 2: EQ, PO, -// 1: EQ, EQ, PO +// 3: GT, +// 2: EQ, GT, +// 1: EQ, EQ, GT // 0: EQ, EQ, EQ -// -1: EQ, EQ, NE -// -2: EQ, NE, -// -3: NE, +// -1: EQ, EQ, LT +// -2: EQ, LT, +// -3: LT, struct MatchHistory { template @@ -57,7 +57,7 @@ struct MatchHistory { } template - const bool is_PO() const; + const bool is_GT() const; template void set(MatchKindCMP match) { @@ -81,12 +81,12 @@ struct MatchHistory { std::ostream& os, const std::optional& match) const { if (!match.has_value()) { return os << "--"; - } else if (*match == MatchKindCMP::NE) { - return os << "NE"; + } else if (*match == MatchKindCMP::LT) { + return os << "LT"; } else if (*match == MatchKindCMP::EQ) { return os << "EQ"; - } else if (*match == MatchKindCMP::PO) { - return os << "PO"; + } else if (*match == MatchKindCMP::GT) { + return os << "GT"; } else { ceph_abort("impossble path"); } @@ -101,28 +101,28 @@ inline std::ostream& operator<<(std::ostream& os, const MatchHistory& pos) { } template -struct _check_PO_t { +struct _check_GT_t { static bool eval(const MatchHistory* history) { return history->get() && - (*history->get() == MatchKindCMP::PO || + (*history->get() == MatchKindCMP::GT || (*history->get() == MatchKindCMP::EQ && - _check_PO_t::eval(history))); + _check_GT_t::eval(history))); } }; template <> -struct _check_PO_t { +struct _check_GT_t { static bool eval(const MatchHistory* history) { return history->get() && - *history->get() == MatchKindCMP::PO; + *history->get() == MatchKindCMP::GT; } }; template -const bool MatchHistory::is_PO() const { +const bool MatchHistory::is_GT() const { static_assert(STAGE >= STAGE_BOTTOM && STAGE <= STAGE_TOP); if constexpr (STAGE < STAGE_TOP) { assert(get() == MatchKindCMP::EQ); } - return _check_PO_t::eval(this); + return _check_GT_t::eval(this); } template -- 2.39.5