ceph/src/crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node_impl.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #pragma once
   5 #include "include/buffer.h"
   6
   7 #include "crimson/common/fixed_kv_node_layout.h"
   8 #include "crimson/common/errorator.h"
   9 #include "crimson/os/seastore/extentmap_manager.h"
  10 #include "crimson/os/seastore/seastore_types.h"
  11 #include "crimson/os/seastore/extentmap_manager/btree/extentmap_btree_node.h"
  12
  13 namespace crimson::os::seastore::extentmap_manager {
  14
  15 struct extmap_node_meta_le_t {
  16   depth_le_t depth = init_les32(0);
  17
  18   extmap_node_meta_le_t() = default;
  19   extmap_node_meta_le_t(const extmap_node_meta_le_t &) = default;
  20   explicit extmap_node_meta_le_t(const extmap_node_meta_t &val)
  21     : depth(init_les32(val.depth)) {}
  22
  23   operator extmap_node_meta_t() const {
  24     return extmap_node_meta_t{ depth };
  25   }
  26 };
  27
  28 /**
  29  * ExtMapInnerNode
  30  *
  31  * Abstracts operations on and layout of internal nodes for the
  32  * Extentmap Tree.
  33  *
  34  * Layout (4k):
  35  *   num_entries: uint32_t           4b
  36  *   meta       : depth              4b
  37  *   (padding)  :                    8b
  38  *   keys       : objaddr_t[340]     (340*4)b
  39  *   values     : laddr_t[340]       (340*8)b
  40  *                                    = 4096
  41  */
  42 constexpr size_t INNER_NODE_CAPACITY =
  43                  (EXTMAP_BLOCK_SIZE - sizeof(uint32_t) - sizeof(extmap_node_meta_t))
  44                  / (sizeof (objaddr_t) + sizeof(laddr_t));
  45
  46 struct ExtMapInnerNode
  47   : ExtMapNode,
  48     common::FixedKVNodeLayout<
  49       INNER_NODE_CAPACITY,
  50       extmap_node_meta_t, extmap_node_meta_le_t,
  51       objaddr_t, ceph_le32,
  52       laddr_t, laddr_le_t> {
  53   using internal_iterator_t = const_iterator;
  54   template <typename... T>
  55   ExtMapInnerNode(T&&... t) :
  56     ExtMapNode(std::forward<T>(t)...),
  57     FixedKVNodeLayout(get_bptr().c_str()) {}
  58
  59   static constexpr extent_types_t type = extent_types_t::EXTMAP_INNER;
  60
  61   extmap_node_meta_t get_node_meta() const final {return get_meta();}
  62
  63   CachedExtentRef duplicate_for_write() final {
  64     assert(delta_buffer.empty());
  65     return CachedExtentRef(new ExtMapInnerNode(*this));
  66   };
  67
  68   delta_buffer_t delta_buffer;
  69   delta_buffer_t *maybe_get_delta_buffer() {
  70     return is_mutation_pending() ? &delta_buffer : nullptr;
  71   }
  72
  73   find_lextent_ret find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) final;
  74
  75   insert_ret insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
  76
  77   rm_lextent_ret rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
  78
  79   split_children_ret make_split_children(ext_context_t ec) final;
  80
  81   full_merge_ret make_full_merge(ext_context_t ec, ExtMapNodeRef right) final;
  82
  83   make_balanced_ret make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) final;
  84
  85   std::ostream &print_detail_l(std::ostream &out) const final;
  86
  87   extent_types_t get_type() const final {
  88     return type;
  89   }
  90
  91   ceph::bufferlist get_delta() final {
  92     assert(!delta_buffer.empty());
  93     ceph::buffer::ptr bptr(delta_buffer.get_bytes());
  94     delta_buffer.copy_out(bptr.c_str(), bptr.length());
  95     ceph::bufferlist bl;
  96     bl.push_back(bptr);
  97     return bl;
  98   }
  99
 100   void apply_delta(const ceph::bufferlist &_bl) final {
 101     assert(_bl.length());
 102     ceph::bufferlist bl = _bl;
 103     bl.rebuild();
 104     delta_buffer_t buffer;
 105     buffer.copy_in(bl.front().c_str(), bl.front().length());
 106     buffer.replay(*this);
 107   }
 108
 109   bool at_max_capacity() const final {
 110     return get_size() == get_capacity();
 111   }
 112
 113   bool at_min_capacity() const {
 114     return get_size() == get_capacity() / 2;
 115   }
 116
 117   unsigned get_node_size() const {
 118     return get_size();
 119   }
 120
 121   /* get the iterator containing [l, r]
 122    */
 123   std::pair<internal_iterator_t, internal_iterator_t> bound(
 124     objaddr_t l, objaddr_t r) {
 125     auto retl = begin();
 126     for (; retl != end(); ++retl) {
 127       if (retl->get_next_key_or_max() > l)
 128         break;
 129     }
 130     auto retr = retl;
 131     for (; retr != end(); ++retr) {
 132       if (retr->get_key() >= r)
 133         break;
 134     }
 135     return {retl, retr};
 136   }
 137
 138   using split_entry_ertr = TransactionManager::read_extent_ertr;
 139   using split_entry_ret = split_entry_ertr::future<ExtMapNodeRef>;
 140   split_entry_ret split_entry(ext_context_t ec, objaddr_t lo,
 141                               internal_iterator_t, ExtMapNodeRef entry);
 142   using merge_entry_ertr = TransactionManager::read_extent_ertr;
 143   using merge_entry_ret = merge_entry_ertr::future<ExtMapNodeRef>;
 144   merge_entry_ret merge_entry(ext_context_t ec, objaddr_t lo,
 145                               internal_iterator_t iter, ExtMapNodeRef entry);
 146   internal_iterator_t get_containing_child(objaddr_t lo);
 147
 148 };
 149
 150 /**
 151  * ExtMapLeafNode
 152  *
 153  * Abstracts operations on and layout of leaf nodes for the
 154  * ExtentMap Tree.
 155  *
 156  * Layout (4k):
 157  *   num_entries: uint32_t               4b
 158  *   meta       : depth                  4b
 159  *   (padding)  :                        8b
 160  *   keys       : objaddr_t[204]         (204*4)b
 161  *   values     : lext_map_val_t[204]    (204*16)b
 162  *                                       = 4096
 163  */
 164 constexpr size_t LEAF_NODE_CAPACITY =
 165                  (EXTMAP_BLOCK_SIZE - sizeof(uint32_t) - sizeof(extmap_node_meta_t))
 166                  / (sizeof(objaddr_t) + sizeof(lext_map_val_t));
 167
 168 struct lext_map_val_le_t {
 169   laddr_le_t laddr;
 170   extent_len_le_t  length = init_extent_len_le_t(0);
 171
 172   lext_map_val_le_t() = default;
 173   lext_map_val_le_t(const lext_map_val_le_t &) = default;
 174   explicit lext_map_val_le_t(const lext_map_val_t &val)
 175     : laddr(laddr_le_t(val.laddr)),
 176       length(init_extent_len_le_t(val.length)) {}
 177
 178   operator lext_map_val_t() const {
 179     return lext_map_val_t{laddr, length};
 180   }
 181 };
 182
 183 struct ExtMapLeafNode
 184   : ExtMapNode,
 185     common::FixedKVNodeLayout<
 186       LEAF_NODE_CAPACITY,
 187       extmap_node_meta_t, extmap_node_meta_le_t,
 188       objaddr_t, ceph_le32,
 189       lext_map_val_t, lext_map_val_le_t> {
 190   using internal_iterator_t = const_iterator;
 191   template <typename... T>
 192   ExtMapLeafNode(T&&... t) :
 193     ExtMapNode(std::forward<T>(t)...),
 194     FixedKVNodeLayout(get_bptr().c_str()) {}
 195
 196   static constexpr extent_types_t type = extent_types_t::EXTMAP_LEAF;
 197
 198   extmap_node_meta_t get_node_meta() const final { return get_meta(); }
 199
 200   CachedExtentRef duplicate_for_write() final {
 201     assert(delta_buffer.empty());
 202     return CachedExtentRef(new ExtMapLeafNode(*this));
 203   };
 204
 205   delta_buffer_t delta_buffer;
 206   delta_buffer_t *maybe_get_delta_buffer() {
 207     return is_mutation_pending() ? &delta_buffer : nullptr;
 208   }
 209
 210   find_lextent_ret find_lextent(ext_context_t ec, objaddr_t lo, extent_len_t len) final;
 211
 212   insert_ret insert(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
 213
 214   rm_lextent_ret rm_lextent(ext_context_t ec, objaddr_t lo, lext_map_val_t val) final;
 215
 216   split_children_ret make_split_children(ext_context_t ec) final;
 217
 218   full_merge_ret make_full_merge(ext_context_t ec, ExtMapNodeRef right) final;
 219
 220   make_balanced_ret make_balanced(ext_context_t ec, ExtMapNodeRef _right, bool prefer_left) final;
 221
 222   extent_types_t get_type() const final {
 223     return type;
 224   }
 225
 226   ceph::bufferlist get_delta() final {
 227     assert(!delta_buffer.empty());
 228     ceph::buffer::ptr bptr(delta_buffer.get_bytes());
 229     delta_buffer.copy_out(bptr.c_str(), bptr.length());
 230     ceph::bufferlist bl;
 231     bl.push_back(bptr);
 232     return bl;
 233   }
 234
 235   void apply_delta(const ceph::bufferlist &_bl) final {
 236     assert(_bl.length());
 237     ceph::bufferlist bl = _bl;
 238     bl.rebuild();
 239     delta_buffer_t buffer;
 240     buffer.copy_in(bl.front().c_str(), bl.front().length());
 241     buffer.replay(*this);
 242   }
 243
 244   std::ostream &print_detail_l(std::ostream &out) const final;
 245
 246   bool at_max_capacity() const final {
 247     return get_size() == get_capacity();
 248   }
 249
 250   bool at_min_capacity() const final {
 251     return get_size() == get_capacity() / 2;
 252   }
 253
 254   unsigned get_node_size() const {
 255     return get_size();
 256   }
 257
 258   /* get the iterator containing [l, r]
 259    */
 260   std::pair<internal_iterator_t, internal_iterator_t> bound(
 261     objaddr_t l, objaddr_t r) {
 262     auto retl = begin();
 263     for (; retl != end(); ++retl) {
 264       if (retl->get_key() >= l || (retl->get_key() + retl->get_val().length) > l)
 265         break;
 266     }
 267     auto retr = retl;
 268     for (; retr != end(); ++retr) {
 269       if (retr->get_key() >= r)
 270         break;
 271     }
 272     return {retl, retr};
 273   }
 274
 275   std::pair<internal_iterator_t, internal_iterator_t>
 276   get_leaf_entries(objaddr_t lo, extent_len_t len);
 277
 278 };
 279 using ExtentMapLeafNodeRef = TCachedExtentRef<ExtMapLeafNode>;
 280
 281 }