summaryrefslogtreecommitdiffstats
path: root/src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h')
-rw-r--r--src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h281
1 files changed, 281 insertions, 0 deletions
diff --git a/src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h b/src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h
new file mode 100644
index 000000000..f5da8cdc2
--- /dev/null
+++ b/src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h
@@ -0,0 +1,281 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+#pragma once
+#include "include/buffer.h"
+
+#include "crimson/common/fixed_kv_node_layout.h"
+#include "crimson/common/errorator.h"
+#include "crimson/os/seastore/extentmap_manager.h"
+#include "crimson/os/seastore/seastore_types.h"
+#include "crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node.h"
+
+namespace crimson::os::seastore::extentmap_manager {
+
+struct extmap_node_meta_le_t {
+ depth_le_t depth = init_les32(0);
+
+ extmap_node_meta_le_t() = default;
+ extmap_node_meta_le_t(const extmap_node_meta_le_t &) = default;
+ explicit extmap_node_meta_le_t(const extmap_node_meta_t &val)
+ : depth(init_les32(val.depth)) {}
+
+ operator extmap_node_meta_t() const {
+ return extmap_node_meta_t{ depth };
+ }
+};
+
+/**
+ * ExtMapInnerNode
+ *
+ * Abstracts operations on and layout of internal nodes for the
+ * Extentmap Tree.
+ *
+ * Layout (4k):
+ * num_entries: uint32_t 4b
+ * meta : depth 4b
+ * (padding) : 8b
+ * keys : objaddr_t[340] (340*4)b
+ * values : laddr_t[340] (340*8)b
+ * = 4096
+ */
+constexpr size_t INNER_NODE_CAPACITY =
+ (EXTMAP_BLOCK_SIZE - sizeof(uint32_t) - sizeof(extmap_node_meta_t))
+ / (sizeof (objaddr_t) + sizeof(laddr_t));
+
+struct ExtMapInnerNode
+ : ExtMapNode,
+ common::FixedKVNodeLayout<
+ INNER_NODE_CAPACITY,
+ extmap_node_meta_t, extmap_node_meta_le_t,
+ objaddr_t, ceph_le32,
+ laddr_t, laddr_le_t> {
+ using internal_iterator_t = const_iterator;
+ template <typename... T>
+ ExtMapInnerNode(T&&... t) :
+ ExtMapNode(std::forward<T>(t)...),
+ FixedKVNodeLayout(get_bptr().c_str()) {}
+
+ static constexpr extent_types_t type = extent_types_t::EXTMAP_INNER;
+
+ extmap_node_meta_t get_node_meta() const final {return get_meta();}
+
+ CachedExtentRef duplicate_for_write() final {
+ assert(delta_buffer.empty());
+ return CachedExtentRef(new ExtMapInnerNode(*this));
+ };
+
+ delta_buffer_t delta_buffer;
+ delta_buffer_t *maybe_get_delta_buffer() {
+ return is_mutation_pending() ? &delta_buffer : nullptr;
+ }
+
+ find_lextent_ret find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) final;
+
+ insert_ret insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
+
+ rm_lextent_ret rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
+
+ split_children_ret make_split_children(ext_context_t ec) final;
+
+ full_merge_ret make_full_merge(ext_context_t ec, ExtMapNodeRef right) final;
+
+ make_balanced_ret make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) final;
+
+ std::ostream &print_detail_l(std::ostream &out) const final;
+
+ extent_types_t get_type() const final {
+ return type;
+ }
+
+ ceph::bufferlist get_delta() final {
+ assert(!delta_buffer.empty());
+ ceph::buffer::ptr bptr(delta_buffer.get_bytes());
+ delta_buffer.copy_out(bptr.c_str(), bptr.length());
+ ceph::bufferlist bl;
+ bl.push_back(bptr);
+ return bl;
+ }
+
+ void apply_delta(const ceph::bufferlist &_bl) final {
+ assert(_bl.length());
+ ceph::bufferlist bl = _bl;
+ bl.rebuild();
+ delta_buffer_t buffer;
+ buffer.copy_in(bl.front().c_str(), bl.front().length());
+ buffer.replay(*this);
+ }
+
+ bool at_max_capacity() const final {
+ return get_size() == get_capacity();
+ }
+
+ bool at_min_capacity() const {
+ return get_size() == get_capacity() / 2;
+ }
+
+ unsigned get_node_size() const {
+ return get_size();
+ }
+
+ /* get the iterator containing [l, r]
+ */
+ std::pair<internal_iterator_t, internal_iterator_t> bound(
+ objaddr_t l, objaddr_t r) {
+ auto retl = begin();
+ for (; retl != end(); ++retl) {
+ if (retl->get_next_key_or_max() > l)
+ break;
+ }
+ auto retr = retl;
+ for (; retr != end(); ++retr) {
+ if (retr->get_key() >= r)
+ break;
+ }
+ return {retl, retr};
+ }
+
+ using split_entry_ertr = TransactionManager::read_extent_ertr;
+ using split_entry_ret = split_entry_ertr::future<ExtMapNodeRef>;
+ split_entry_ret split_entry(ext_context_t ec, objaddr_t lo,
+ internal_iterator_t, ExtMapNodeRef entry);
+ using merge_entry_ertr = TransactionManager::read_extent_ertr;
+ using merge_entry_ret = merge_entry_ertr::future<ExtMapNodeRef>;
+ merge_entry_ret merge_entry(ext_context_t ec, objaddr_t lo,
+ internal_iterator_t iter, ExtMapNodeRef entry);
+ internal_iterator_t get_containing_child(objaddr_t lo);
+
+};
+
+/**
+ * ExtMapLeafNode
+ *
+ * Abstracts operations on and layout of leaf nodes for the
+ * ExtentMap Tree.
+ *
+ * Layout (4k):
+ * num_entries: uint32_t 4b
+ * meta : depth 4b
+ * (padding) : 8b
+ * keys : objaddr_t[204] (204*4)b
+ * values : lext_map_val_t[204] (204*16)b
+ * = 4096
+ */
+constexpr size_t LEAF_NODE_CAPACITY =
+ (EXTMAP_BLOCK_SIZE - sizeof(uint32_t) - sizeof(extmap_node_meta_t))
+ / (sizeof(objaddr_t) + sizeof(lext_map_val_t));
+
+struct lext_map_val_le_t {
+ laddr_le_t laddr;
+ extent_len_le_t length = init_extent_len_le_t(0);
+
+ lext_map_val_le_t() = default;
+ lext_map_val_le_t(const lext_map_val_le_t &) = default;
+ explicit lext_map_val_le_t(const lext_map_val_t &val)
+ : laddr(laddr_le_t(val.laddr)),
+ length(init_extent_len_le_t(val.length)) {}
+
+ operator lext_map_val_t() const {
+ return lext_map_val_t{laddr, length};
+ }
+};
+
+struct ExtMapLeafNode
+ : ExtMapNode,
+ common::FixedKVNodeLayout<
+ LEAF_NODE_CAPACITY,
+ extmap_node_meta_t, extmap_node_meta_le_t,
+ objaddr_t, ceph_le32,
+ lext_map_val_t, lext_map_val_le_t> {
+ using internal_iterator_t = const_iterator;
+ template <typename... T>
+ ExtMapLeafNode(T&&... t) :
+ ExtMapNode(std::forward<T>(t)...),
+ FixedKVNodeLayout(get_bptr().c_str()) {}
+
+ static constexpr extent_types_t type = extent_types_t::EXTMAP_LEAF;
+
+ extmap_node_meta_t get_node_meta() const final { return get_meta(); }
+
+ CachedExtentRef duplicate_for_write() final {
+ assert(delta_buffer.empty());
+ return CachedExtentRef(new ExtMapLeafNode(*this));
+ };
+
+ delta_buffer_t delta_buffer;
+ delta_buffer_t *maybe_get_delta_buffer() {
+ return is_mutation_pending() ? &delta_buffer : nullptr;
+ }
+
+ find_lextent_ret find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) final;
+
+ insert_ret insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
+
+ rm_lextent_ret rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
+
+ split_children_ret make_split_children(ext_context_t ec) final;
+
+ full_merge_ret make_full_merge(ext_context_t ec, ExtMapNodeRef right) final;
+
+ make_balanced_ret make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) final;
+
+ extent_types_t get_type() const final {
+ return type;
+ }
+
+ ceph::bufferlist get_delta() final {
+ assert(!delta_buffer.empty());
+ ceph::buffer::ptr bptr(delta_buffer.get_bytes());
+ delta_buffer.copy_out(bptr.c_str(), bptr.length());
+ ceph::bufferlist bl;
+ bl.push_back(bptr);
+ return bl;
+ }
+
+ void apply_delta(const ceph::bufferlist &_bl) final {
+ assert(_bl.length());
+ ceph::bufferlist bl = _bl;
+ bl.rebuild();
+ delta_buffer_t buffer;
+ buffer.copy_in(bl.front().c_str(), bl.front().length());
+ buffer.replay(*this);
+ }
+
+ std::ostream &print_detail_l(std::ostream &out) const final;
+
+ bool at_max_capacity() const final {
+ return get_size() == get_capacity();
+ }
+
+ bool at_min_capacity() const final {
+ return get_size() == get_capacity() / 2;
+ }
+
+ unsigned get_node_size() const {
+ return get_size();
+ }
+
+ /* get the iterator containing [l, r]
+ */
+ std::pair<internal_iterator_t, internal_iterator_t> bound(
+ objaddr_t l, objaddr_t r) {
+ auto retl = begin();
+ for (; retl != end(); ++retl) {
+ if (retl->get_key() >= l || (retl->get_key() + retl->get_val().length) > l)
+ break;
+ }
+ auto retr = retl;
+ for (; retr != end(); ++retr) {
+ if (retr->get_key() >= r)
+ break;
+ }
+ return {retl, retr};
+ }
+
+ std::pair<internal_iterator_t, internal_iterator_t>
+ get_leaf_entries(objaddr_t lo, extent_len_t len);
+
+};
+using ExtentMapLeafNodeRef = TCachedExtentRef<ExtMapLeafNode>;
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 15:14:46 +0000