From d163f1f9d14f2f5e11a02939d4f02ab39f42e783 Mon Sep 17 00:00:00 2001 From: Yingxin Cheng Date: Tue, 8 Jun 2021 09:55:15 +0800 Subject: [PATCH] crimson/onode-staged-tree: use extent_len_t and node_offset_t correctly extent_len_t represents a value that may include the node size, but node_offset_t cannot and may overflow. Also add validations when try to cast a larger type to node_offset_t. Signed-off-by: Yingxin Cheng --- .../onode_manager/staged-fltree/node_impl.h | 4 +-- .../onode_manager/staged-fltree/node_layout.h | 11 +++++--- .../staged-fltree/stages/node_stage.cc | 25 +++++++++-------- .../staged-fltree/stages/node_stage.h | 9 ++++-- .../staged-fltree/stages/node_stage_layout.cc | 12 +++++--- .../staged-fltree/stages/node_stage_layout.h | 28 +++++++++---------- .../staged-fltree/stages/stage.h | 2 +- .../seastore/onode_tree/test_staged_fltree.cc | 4 +-- 8 files changed, 54 insertions(+), 41 deletions(-) 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 8a361dd270d..9a0ad143e22 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 @@ -82,14 +82,14 @@ class NodeImpl { virtual level_t level() const = 0; virtual node_offset_t free_size() const = 0; - virtual node_offset_t total_size() const = 0; + virtual extent_len_t total_size() const = 0; virtual bool is_extent_retired() const = 0; virtual std::optional get_pivot_index() const = 0; virtual bool is_size_underflow() const = 0; virtual std::tuple erase(const search_position_t&) = 0; virtual std::tuple evaluate_merge(NodeImpl&) = 0; - virtual search_position_t merge(NodeExtentMutable&, NodeImpl&, match_stage_t, node_offset_t) = 0; + virtual search_position_t merge(NodeExtentMutable&, NodeImpl&, match_stage_t, extent_len_t) = 0; virtual eagain_future rebuild_extent(context_t) = 0; virtual eagain_future<> retire_extent(context_t) = 0; virtual search_position_t make_tail() = 0; 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 2884474c062..0e75e7adfb8 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 @@ -130,7 +130,7 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { level_t level() const override { return extent.read().level(); } node_offset_t free_size() const override { return extent.read().free_size(); } - node_offset_t total_size() const override { return extent.read().total_size(); } + extent_len_t total_size() const override { return extent.read().total_size(); } bool is_extent_retired() const override { return extent.is_retired(); } std::optional get_pivot_index() const override { @@ -224,8 +224,11 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { return {merge_stage, merge_size}; } - search_position_t merge(NodeExtentMutable& mut, NodeImpl& _right_node, - match_stage_t merge_stage, node_offset_t merge_size) override { + search_position_t merge( + NodeExtentMutable& mut, + NodeImpl& _right_node, + match_stage_t merge_stage, + extent_len_t merge_size) override { LOG_PREFIX(OTree::Layout::merge); assert(NODE_TYPE == _right_node.node_type()); assert(FIELD_TYPE == _right_node.field_type()); @@ -872,7 +875,7 @@ class NodeLayoutT final : public InternalNodeImpl, public LeafNodeImpl { build_name(); } - node_offset_t filled_size() const { + extent_len_t filled_size() const { auto& node_stage = extent.read(); auto ret = node_stage.size_before(node_stage.keys()); assert(ret == node_stage.total_size() - node_stage.free_size()); 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 cb1d1db5314..4252b4dcb1f 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 @@ -51,9 +51,9 @@ container_range_t NODE_T::get_nxt_container(index_t index) const if constexpr (std::is_same_v) { ceph_abort("N3 internal node doesn't have the right part"); } else { - node_offset_t item_start_offset = p_fields->get_item_start_offset( + auto item_start_offset = p_fields->get_item_start_offset( index, node_size); - node_offset_t item_end_offset = p_fields->get_item_end_offset( + auto item_end_offset = p_fields->get_item_end_offset( index, node_size); assert(item_start_offset < item_end_offset); auto item_p_start = p_start() + item_start_offset; @@ -299,7 +299,7 @@ void APPEND_T::append(const node_extent_t& src, index_t from, index_t items) src.p_start() + offset_left_start, left_size); } else { node_offset_t step_size = FieldType::estimate_insert_one(); - node_offset_t offset_base = src.fields().get_item_end_offset( + extent_len_t offset_base = src.fields().get_item_end_offset( from, node_size); int offset_change = p_append_right - p_start - offset_base; auto p_offset_dst = p_append_left; @@ -311,10 +311,11 @@ void APPEND_T::append(const node_extent_t& src, index_t from, index_t items) p_offset_dst += sizeof(typename FieldType::key_t); } for (auto i = from; i < from + items; ++i) { - p_mut->copy_in_absolute( - p_offset_dst, - node_offset_t(src.fields().get_item_start_offset(i, node_size) + - offset_change)); + int new_offset = src.fields().get_item_start_offset(i, node_size) + + offset_change; + assert(new_offset > 0); + assert(new_offset < (int)node_size); + p_mut->copy_in_absolute(p_offset_dst, node_offset_t(new_offset)); p_offset_dst += step_size; } assert(p_append_left + left_size + sizeof(typename FieldType::key_t) == @@ -323,14 +324,16 @@ void APPEND_T::append(const node_extent_t& src, index_t from, index_t items) p_append_left += left_size; // append right part backwards - node_offset_t offset_right_start = src.fields().get_item_end_offset( + auto offset_right_start = src.fields().get_item_end_offset( from + items, node_size); - node_offset_t offset_right_end = src.fields().get_item_end_offset( + auto offset_right_end = src.fields().get_item_end_offset( from, node_size); - node_offset_t right_size = offset_right_end - offset_right_start; + int right_size = offset_right_end - offset_right_start; + assert(right_size > 0); + assert(right_size < (int)node_size); p_append_right -= right_size; p_mut->copy_in_absolute(p_append_right, - src.p_start() + offset_right_start, right_size); + src.p_start() + offset_right_start, node_offset_t(right_size)); } } diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.h index b3dd225282f..9084e954c6b 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage.h @@ -48,7 +48,7 @@ class node_extent_t { return p_fields->template free_size_before( keys(), node_size); } - node_offset_t total_size() const { + extent_len_t total_size() const { return p_fields->total_size(node_size); } const char* p_left_bound() const; @@ -75,7 +75,7 @@ class node_extent_t { key_get_type operator[] (index_t index) const { return p_fields->get_key(index, node_size); } - node_offset_t size_before(index_t index) const { + extent_len_t size_before(index_t index) const { auto free_size = p_fields->template free_size_before( index, node_size); assert(total_size() >= free_size); @@ -210,7 +210,10 @@ class node_extent_t::Appender { assert(p_append < p_append_right); assert(p_append_left < p_append); p_append_right = p_append; - FieldType::append_offset(*p_mut, p_append - p_start, p_append_left); + auto new_offset = p_append - p_start; + assert(new_offset > 0); + assert(new_offset < p_mut->get_length()); + FieldType::append_offset(*p_mut, new_offset, p_append_left); ++num_keys; } else { ceph_abort("not implemented"); diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc index 83b70f7ffa7..13a9e3c5f9e 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.cc @@ -48,9 +48,12 @@ void F013_T::update_size_at( p_slot < &node.slots[node.num_keys]; ++p_slot) { node_offset_t offset = p_slot->right_offset; + int new_offset = offset - change; + assert(new_offset > 0); + assert(new_offset < (int)node_size); mut.copy_in_absolute( (void*)&(p_slot->right_offset), - node_offset_t(offset - change)); + node_offset_t(new_offset)); } #ifndef NDEBUG // check overflow @@ -94,9 +97,10 @@ void F013_T::insert_at( mut.shift_absolute(p_insert, p_shift_end - p_insert, estimate_insert_one()); mut.copy_in_absolute((void*)&node.num_keys, num_keys_t(node.num_keys + 1)); append_key(mut, key_t::template from_key(key), p_insert); - append_offset(mut, - node.get_item_end_offset(index, node_size) - size_right, - p_insert); + int new_offset = node.get_item_end_offset(index, node_size) - size_right; + assert(new_offset > 0); + assert(new_offset < (int)node_size); + append_offset(mut, new_offset, p_insert); } #define IA_TEMPLATE(ST, KT) template void F013_INST(ST):: \ insert_at(NodeExtentMutable&, const full_key_t&, \ diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h index cf2bf199aec..f69b902dc33 100644 --- a/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h +++ b/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h @@ -71,8 +71,8 @@ using slot_1_t = _slot_t; using slot_3_t = _slot_t; struct node_range_t { - node_offset_t start; - node_offset_t end; + extent_len_t start; + extent_len_t end; }; template @@ -84,15 +84,15 @@ template node_range_t fields_free_range_before( const FieldType& node, index_t index, extent_len_t node_size) { assert(index <= node.num_keys); - node_offset_t offset_start = node.get_key_start_offset(index, node_size); - node_offset_t offset_end = node.get_item_end_offset(index, node_size); + extent_len_t offset_start = node.get_key_start_offset(index, node_size); + extent_len_t offset_end = node.get_item_end_offset(index, node_size); if constexpr (NODE_TYPE == node_type_t::INTERNAL) { if (node.is_level_tail() && index == node.num_keys) { offset_end -= sizeof(laddr_t); } } assert(offset_start <= offset_end); - assert(offset_end - offset_start < (int)node_size); + assert(offset_end - offset_start < node_size); return {offset_start, offset_end}; } @@ -132,7 +132,7 @@ struct _node_fields_013_t { static constexpr node_offset_t ITEM_OVERHEAD = SlotType::OVERHEAD; bool is_level_tail() const { return header.get_is_level_tail(); } - node_offset_t total_size(extent_len_t node_size) const { + extent_len_t total_size(extent_len_t node_size) const { return node_size; } key_get_type get_key( @@ -158,7 +158,7 @@ struct _node_fields_013_t { assert(index < num_keys); return &slots[index].right_offset; } - node_offset_t get_item_end_offset( + extent_len_t get_item_end_offset( index_t index, extent_len_t node_size) const { return index == 0 ? node_size : get_item_start_offset(index - 1, node_size); @@ -226,13 +226,13 @@ struct node_fields_2_t { static constexpr node_offset_t ITEM_OVERHEAD = sizeof(node_offset_t); bool is_level_tail() const { return header.get_is_level_tail(); } - node_offset_t total_size(extent_len_t node_size) const { + extent_len_t total_size(extent_len_t node_size) const { return node_size; } key_get_type get_key( index_t index, extent_len_t node_size) const { assert(index < num_keys); - node_offset_t item_end_offset = get_item_end_offset(index, node_size); + auto item_end_offset = get_item_end_offset(index, node_size); const char* p_start = fields_start(*this); return key_t(p_start + item_end_offset); } @@ -240,7 +240,7 @@ struct node_fields_2_t { index_t index, extent_len_t node_size) const { assert(index <= num_keys); auto offset = HEADER_SIZE + sizeof(node_offset_t) * num_keys; - assert(offset <= node_size); + assert(offset < node_size); return offset; } node_offset_t get_item_start_offset( @@ -254,7 +254,7 @@ struct node_fields_2_t { assert(index < num_keys); return &offsets[index]; } - node_offset_t get_item_end_offset( + extent_len_t get_item_end_offset( index_t index, extent_len_t node_size) const { return index == 0 ? node_size : get_item_start_offset(index - 1, node_size); @@ -320,7 +320,7 @@ struct internal_fields_3_t { static constexpr node_offset_t ITEM_OVERHEAD = 0u; bool is_level_tail() const { return header.get_is_level_tail(); } - node_offset_t total_size(extent_len_t node_size) const { + extent_len_t total_size(extent_len_t node_size) const { if (is_level_tail()) { return node_size - sizeof(snap_gen_t); } else { @@ -337,8 +337,8 @@ struct internal_fields_3_t { free_size_before(index_t index, extent_len_t node_size) const { assert(index <= num_keys); assert(num_keys <= get_max_num_keys(node_size)); - auto free = total_size(node_size) - HEADER_SIZE - - index * ITEM_SIZE; + extent_len_t free = total_size(node_size) - HEADER_SIZE - + index * ITEM_SIZE; if (is_level_tail() && index == num_keys) { free -= sizeof(laddr_t); } 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 818810b0e86..4ea88cadf75 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 @@ -208,7 +208,7 @@ struct staged { * CONTAINER_TYPE = ContainerType::INDEXABLE * keys() const -> index_t * operator[](index_t) const -> key_get_type - * size_before(index_t) const -> node_offset_t + * size_before(index_t) const -> extent_len_t * size_overhead_at(index_t) const -> node_offset_t * (IS_BOTTOM) get_p_value(index_t) const -> const value_t* * (!IS_BOTTOM) size_to_nxt_at(index_t) const -> node_offset_t 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 a7066c77cc3..4d222aedef0 100644 --- a/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc +++ b/src/test/crimson/seastore/onode_tree/test_staged_fltree.cc @@ -861,7 +861,7 @@ class DummyChildPool { ceph_abort("impossible path"); } node_offset_t free_size() const override { ceph_abort("impossible path"); } - node_offset_t total_size() const override { + extent_len_t total_size() const override { ceph_abort("impossible path"); } bool is_size_underflow() const override { ceph_abort("impossible path"); } @@ -869,7 +869,7 @@ class DummyChildPool { ceph_abort("impossible path"); } std::tuple evaluate_merge(NodeImpl&) override { ceph_abort("impossible path"); } - search_position_t merge(NodeExtentMutable&, NodeImpl&, match_stage_t, node_offset_t) override { + search_position_t merge(NodeExtentMutable&, NodeImpl&, match_stage_t, extent_len_t) override { ceph_abort("impossible path"); } eagain_future rebuild_extent(context_t) override { ceph_abort("impossible path"); } -- 2.39.5