ceph/src/crimson/os/seastore/onode_manager/staged-fltree/stages/node_stage_layout.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #pragma once
   5
   6 #include "key_layout.h"
   7 #include "crimson/os/seastore/onode_manager/staged-fltree/node_types.h"
   8
   9 namespace crimson::os::seastore::onode {
  10
  11 class NodeExtentMutable;
  12
  13 struct node_header_t {
  14   static constexpr unsigned FIELD_TYPE_BITS = 6u;
  15   static_assert(static_cast<uint8_t>(field_type_t::_MAX) <= 1u << FIELD_TYPE_BITS);
  16   static constexpr unsigned NODE_TYPE_BITS = 1u;
  17   static constexpr unsigned B_LEVEL_TAIL_BITS = 1u;
  18   using bits_t = uint8_t;
  19
  20   node_header_t() {}
  21   std::optional<field_type_t> get_field_type() const {
  22     if (field_type >= FIELD_TYPE_MAGIC &&
  23         field_type < static_cast<uint8_t>(field_type_t::_MAX)) {
  24       return static_cast<field_type_t>(field_type);
  25     } else {
  26       return std::nullopt;
  27     }
  28   }
  29   node_type_t get_node_type() const {
  30     return static_cast<node_type_t>(node_type);
  31   }
  32   bool get_is_level_tail() const {
  33     return is_level_tail;
  34   }
  35
  36   static void bootstrap_extent(
  37       NodeExtentMutable&, field_type_t, node_type_t, bool, level_t);
  38
  39   static void update_is_level_tail(NodeExtentMutable&, const node_header_t&, bool);
  40
  41   bits_t field_type : FIELD_TYPE_BITS;
  42   bits_t node_type : NODE_TYPE_BITS;
  43   bits_t is_level_tail : B_LEVEL_TAIL_BITS;
  44   static_assert(sizeof(bits_t) * 8 ==
  45                 FIELD_TYPE_BITS + NODE_TYPE_BITS + B_LEVEL_TAIL_BITS);
  46   level_t level;
  47
  48  private:
  49   void set_field_type(field_type_t type) {
  50     field_type = static_cast<uint8_t>(type);
  51   }
  52   void set_node_type(node_type_t type) {
  53     node_type = static_cast<uint8_t>(type);
  54   }
  55   void set_is_level_tail(bool value) {
  56     is_level_tail = static_cast<uint8_t>(value);
  57   }
  58 } __attribute__((packed));
  59 inline std::ostream& operator<<(std::ostream& os, const node_header_t& header) {
  60   auto field_type = header.get_field_type();
  61   if (field_type.has_value()) {
  62     os << "header" << header.get_node_type() << *field_type
  63        << "(is_level_tail=" << header.get_is_level_tail()
  64        << ", level=" << (unsigned)header.level << ")";
  65   } else {
  66     os << "header(INVALID)";
  67   }
  68   return os;
  69 }
  70
  71 template <typename FixedKeyType, field_type_t _FIELD_TYPE>
  72 struct _slot_t {
  73   using key_t = FixedKeyType;
  74   static constexpr field_type_t FIELD_TYPE = _FIELD_TYPE;
  75   static constexpr node_offset_t OVERHEAD = sizeof(_slot_t) - sizeof(key_t);
  76
  77   key_t key;
  78   node_offset_t right_offset;
  79 } __attribute__((packed));
  80 using slot_0_t = _slot_t<shard_pool_crush_t, field_type_t::N0>;
  81 using slot_1_t = _slot_t<crush_t, field_type_t::N1>;
  82 using slot_3_t = _slot_t<snap_gen_t, field_type_t::N3>;
  83
  84 struct node_range_t {
  85   extent_len_t start;
  86   extent_len_t end;
  87 };
  88
  89 template <typename FieldType>
  90 const char* fields_start(const FieldType& node) {
  91   return reinterpret_cast<const char*>(&node);
  92 }
  93
  94 template <node_type_t NODE_TYPE, typename FieldType>
  95 node_range_t fields_free_range_before(
  96     const FieldType& node, index_t index, extent_len_t node_size) {
  97   assert(index <= node.num_keys);
  98   extent_len_t offset_start = node.get_key_start_offset(index, node_size);
  99   extent_len_t offset_end = node.get_item_end_offset(index, node_size);
 100   if constexpr (NODE_TYPE == node_type_t::INTERNAL) {
 101     if (node.is_level_tail() && index == node.num_keys) {
 102       offset_end -= sizeof(laddr_t);
 103     }
 104   }
 105   assert(offset_start <= offset_end);
 106   assert(offset_end - offset_start < node_size);
 107   return {offset_start, offset_end};
 108 }
 109
 110 /**
 111  * _node_fields_013_t (node_fields_0_t, node_fields_1_t, leaf_fields_3_t
 112  *
 113  * The STAGE_LEFT layout implementation for node N0/N1, or the STAGE_RIGHT
 114  * layout implementation for leaf node N3.
 115  *
 116  * The node layout storing n slots:
 117  *
 118  * # <----------------------------- node range --------------------------------------> #
 119  * #                                                 #<~># free space                  #
 120  * # <----- left part -----------------------------> # <~# <----- right slots -------> #
 121  * #               # <---- left slots -------------> #~> #                             #
 122  * #               #                slots [2, n) |<~>#   #<~>| right slots [2, n)      #
 123  * #               # <- slot 0 -> | <- slot 1 -> |   #   #   | <-- s1 --> | <-- s0 --> #
 124  * #               #              |              |   #   #   |            |            #
 125  * #        | num_ #     | right  |     | right  |   #   #   | next-stage | next-stage #
 126  * # header | keys # key | offset | key | offset |   #   #   | container  | container  #
 127  * #        |      # 0   | 0      | 1   | 1      |...#...#...| or onode 1 | or onode 0 #
 128  *                           |              |                ^            ^
 129  *                           |              |                |            |
 130  *                           |              +----------------+            |
 131  *                           +--------------------------------------------+
 132  */
 133 template <typename SlotType>
 134 struct _node_fields_013_t {
 135   // should be enough to index all keys under 64 KiB node
 136   using num_keys_t = uint16_t;
 137   using key_t = typename SlotType::key_t;
 138   using key_get_type = const key_t&;
 139   using me_t = _node_fields_013_t<SlotType>;
 140   static constexpr field_type_t FIELD_TYPE = SlotType::FIELD_TYPE;
 141   static constexpr node_offset_t HEADER_SIZE =
 142     sizeof(node_header_t) + sizeof(num_keys_t);
 143   static constexpr node_offset_t ITEM_OVERHEAD = SlotType::OVERHEAD;
 144
 145   bool is_level_tail() const { return header.get_is_level_tail(); }
 146   extent_len_t total_size(extent_len_t node_size) const {
 147     return node_size;
 148   }
 149   key_get_type get_key(
 150       index_t index, extent_len_t node_size) const {
 151     assert(index < num_keys);
 152     return slots[index].key;
 153   }
 154   node_offset_t get_key_start_offset(
 155       index_t index, extent_len_t node_size) const {
 156     assert(index <= num_keys);
 157     auto offset = HEADER_SIZE + sizeof(SlotType) * index;
 158     assert(offset < node_size);
 159     return offset;
 160   }
 161   node_offset_t get_item_start_offset(
 162       index_t index, extent_len_t node_size) const {
 163     assert(index < num_keys);
 164     auto offset = slots[index].right_offset;
 165     assert(offset < node_size);
 166     return offset;
 167   }
 168   const void* p_offset(index_t index) const {
 169     assert(index < num_keys);
 170     return &slots[index].right_offset;
 171   }
 172   extent_len_t get_item_end_offset(
 173       index_t index, extent_len_t node_size) const {
 174     return index == 0 ? node_size
 175                       : get_item_start_offset(index - 1, node_size);
 176   }
 177   template <node_type_t NODE_TYPE>
 178   node_offset_t free_size_before(
 179       index_t index, extent_len_t node_size) const {
 180     auto range = fields_free_range_before<NODE_TYPE>(*this, index, node_size);
 181     return range.end - range.start;
 182   }
 183
 184   static node_offset_t estimate_insert_one() { return sizeof(SlotType); }
 185   template <KeyT KT>
 186   static void insert_at(
 187       NodeExtentMutable&, const full_key_t<KT>& key,
 188       const me_t& node, index_t index, node_offset_t size_right);
 189   static node_offset_t erase_at(NodeExtentMutable&, const me_t&, index_t, const char*);
 190   static void update_size_at(
 191       NodeExtentMutable&, const me_t& node, index_t index, int change);
 192   static void append_key(
 193       NodeExtentMutable&, const key_t& key, char*& p_append);
 194   template <KeyT KT>
 195   static void append_key(
 196       NodeExtentMutable& mut, const full_key_t<KT>& key, char*& p_append) {
 197     append_key(mut, key_t::template from_key<KT>(key), p_append);
 198   }
 199   static void append_offset(
 200       NodeExtentMutable& mut, node_offset_t offset_to_right, char*& p_append);
 201
 202   node_header_t header;
 203   num_keys_t num_keys = 0u;
 204   SlotType slots[];
 205 } __attribute__((packed));
 206 using node_fields_0_t = _node_fields_013_t<slot_0_t>;
 207 using node_fields_1_t = _node_fields_013_t<slot_1_t>;
 208
 209 /**
 210  * node_fields_2_t
 211  *
 212  * The STAGE_STRING layout implementation for node N2.
 213  *
 214  * The node layout storing n slots:
 215  *
 216  * # <--------------------------------- node range ----------------------------------------> #
 217  * #                                     #<~># free space                                    #
 218  * # <------- left part ---------------> # <~# <--------- right slots ---------------------> #
 219  * #               # <---- offsets ----> #~> #<~>| slots [2, n)                              #
 220  * #               #  offsets [2, n) |<~>#   #   | <----- slot 1 ----> | <----- slot 0 ----> #
 221  * #               #                 |   #   #   |                     |                     #
 222  * #        | num_ # offset | offset |   #   #   | next-stage | ns-oid | next-stage | ns-oid #
 223  * # header | keys # 0      | 1      |...#...#...| container1 | 1      | container0 | 0      #
 224  *                     |        |                ^                     ^
 225  *                     |        |                |                     |
 226  *                     |        +----------------+                     |
 227  *                     +-----------------------------------------------+
 228  */
 229 struct node_fields_2_t {
 230   // should be enough to index all keys under 64 KiB node
 231   using num_keys_t = uint16_t;
 232   using key_t = ns_oid_view_t;
 233   using key_get_type = key_t;
 234   static constexpr field_type_t FIELD_TYPE = field_type_t::N2;
 235   static constexpr node_offset_t HEADER_SIZE =
 236     sizeof(node_header_t) + sizeof(num_keys_t);
 237   static constexpr node_offset_t ITEM_OVERHEAD = sizeof(node_offset_t);
 238
 239   bool is_level_tail() const { return header.get_is_level_tail(); }
 240   extent_len_t total_size(extent_len_t node_size) const {
 241     return node_size;
 242   }
 243   key_get_type get_key(
 244       index_t index, extent_len_t node_size) const {
 245     assert(index < num_keys);
 246     auto item_end_offset = get_item_end_offset(index, node_size);
 247     const char* p_start = fields_start(*this);
 248     return key_t(p_start + item_end_offset);
 249   }
 250   node_offset_t get_key_start_offset(
 251       index_t index, extent_len_t node_size) const {
 252     assert(index <= num_keys);
 253     auto offset = HEADER_SIZE + sizeof(node_offset_t) * num_keys;
 254     assert(offset < node_size);
 255     return offset;
 256   }
 257   node_offset_t get_item_start_offset(
 258       index_t index, extent_len_t node_size) const {
 259     assert(index < num_keys);
 260     auto offset = offsets[index];
 261     assert(offset < node_size);
 262     return offset;
 263   }
 264   const void* p_offset(index_t index) const {
 265     assert(index < num_keys);
 266     return &offsets[index];
 267   }
 268   extent_len_t get_item_end_offset(
 269       index_t index, extent_len_t node_size) const {
 270     return index == 0 ? node_size
 271                       : get_item_start_offset(index - 1, node_size);
 272   }
 273   template <node_type_t NODE_TYPE>
 274   node_offset_t free_size_before(
 275       index_t index, extent_len_t node_size) const {
 276     auto range = fields_free_range_before<NODE_TYPE>(*this, index, node_size);
 277     return range.end - range.start;
 278   }
 279
 280   static node_offset_t estimate_insert_one() { return sizeof(node_offset_t); }
 281   template <KeyT KT>
 282   static void insert_at(
 283       NodeExtentMutable& mut, const full_key_t<KT>& key,
 284       const node_fields_2_t& node, index_t index, node_offset_t size_right) {
 285     ceph_abort("not implemented");
 286   }
 287   static void update_size_at(
 288       NodeExtentMutable& mut, const node_fields_2_t& node, index_t index, int change) {
 289     ceph_abort("not implemented");
 290   }
 291   static void append_key(
 292       NodeExtentMutable& mut, const key_t& key, char*& p_append) {
 293     ns_oid_view_t::append(mut, key, p_append);
 294   }
 295   template <KeyT KT>
 296   static void append_key(
 297       NodeExtentMutable& mut, const full_key_t<KT>& key, char*& p_append) {
 298     ns_oid_view_t::append<KT>(mut, key, p_append);
 299   }
 300   static void append_offset(
 301       NodeExtentMutable& mut, node_offset_t offset_to_right, char*& p_append);
 302
 303   node_header_t header;
 304   num_keys_t num_keys = 0u;
 305   node_offset_t offsets[];
 306 } __attribute__((packed));
 307
 308 /**
 309  * internal_fields_3_t
 310  *
 311  * The STAGE_RIGHT layout implementation for N2.
 312  *
 313  * The node layout storing 3 children:
 314  *
 315  * # <---------------- node range ---------------------------> #
 316  * #               # <-- keys ---> # <---- laddrs -----------> #
 317  * #  free space:  #           |<~>#                       |<~>#
 318  * #               #           |   #                       |   #
 319  * #        | num_ # key | key |   # laddr | laddr | laddr |   #
 320  * # header | keys # 0   | 1   |...# 0     | 1     | 2     |...#
 321  */
 322 struct internal_fields_3_t {
 323   using key_get_type = const snap_gen_t&;
 324   // should be enough to index all keys under 64 KiB node
 325   using num_keys_t = uint16_t;
 326   static constexpr field_type_t FIELD_TYPE = field_type_t::N3;
 327   static constexpr node_offset_t HEADER_SIZE =
 328     sizeof(node_header_t) + sizeof(num_keys_t);
 329   static constexpr node_offset_t ITEM_SIZE =
 330     sizeof(snap_gen_t) + sizeof(laddr_t);
 331   static constexpr node_offset_t ITEM_OVERHEAD = 0u;
 332
 333   bool is_level_tail() const { return header.get_is_level_tail(); }
 334   extent_len_t total_size(extent_len_t node_size) const {
 335     if (is_level_tail()) {
 336       return node_size - sizeof(snap_gen_t);
 337     } else {
 338       return node_size;
 339     }
 340   }
 341   key_get_type get_key(
 342       index_t index, extent_len_t node_size) const {
 343     assert(index < num_keys);
 344     return keys[index];
 345   }
 346   template <node_type_t NODE_TYPE>
 347   std::enable_if_t<NODE_TYPE == node_type_t::INTERNAL, node_offset_t>
 348   free_size_before(index_t index, extent_len_t node_size) const {
 349     assert(index <= num_keys);
 350     assert(num_keys <= get_max_num_keys(node_size));
 351     extent_len_t free = total_size(node_size) - HEADER_SIZE -
 352                         index * ITEM_SIZE;
 353     if (is_level_tail() && index == num_keys) {
 354       free -= sizeof(laddr_t);
 355     }
 356     return free;
 357   }
 358
 359   const laddr_packed_t* get_p_child_addr(
 360       index_t index, extent_len_t node_size) const {
 361 #ifndef NDEBUG
 362     if (is_level_tail()) {
 363       assert(index <= num_keys);
 364     } else {
 365       assert(index < num_keys);
 366     }
 367 #endif
 368     auto p_addrs = reinterpret_cast<const laddr_packed_t*>(
 369         &keys[get_num_keys_limit(node_size)]);
 370     auto ret = p_addrs + index;
 371     assert((const char*)ret < fields_start(*this) + node_size);
 372     return ret;
 373   }
 374
 375   static node_offset_t estimate_insert_one() { return ITEM_SIZE; }
 376
 377   template <KeyT KT>
 378   static void insert_at(
 379       NodeExtentMutable& mut, const full_key_t<KT>& key,
 380       const internal_fields_3_t& node,
 381       index_t index, node_offset_t size_right) {
 382     ceph_abort("not implemented");
 383   }
 384   static void update_size_at(
 385       NodeExtentMutable& mut, const internal_fields_3_t& node,
 386       index_t index, int change) {
 387     ceph_abort("not implemented");
 388   }
 389
 390   node_header_t header;
 391   num_keys_t num_keys = 0u;
 392   snap_gen_t keys[];
 393
 394  private:
 395   num_keys_t get_max_num_keys(extent_len_t node_size) const {
 396     auto num_limit = get_num_keys_limit(node_size);
 397     return (is_level_tail() ? num_limit - 1 : num_limit);
 398   }
 399   static num_keys_t get_num_keys_limit(extent_len_t node_size) {
 400     return (node_size - HEADER_SIZE) / ITEM_SIZE;
 401   }
 402 } __attribute__((packed));
 403
 404 using leaf_fields_3_t = _node_fields_013_t<slot_3_t>;
 405
 406 }