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
  60 template <typename FixedKeyType, field_type_t _FIELD_TYPE>
  61 struct _slot_t {
  62   using key_t = FixedKeyType;
  63   static constexpr field_type_t FIELD_TYPE = _FIELD_TYPE;
  64   static constexpr node_offset_t OVERHEAD = sizeof(_slot_t) - sizeof(key_t);
  65
  66   key_t key;
  67   node_offset_t right_offset;
  68 } __attribute__((packed));
  69 using slot_0_t = _slot_t<shard_pool_crush_t, field_type_t::N0>;
  70 using slot_1_t = _slot_t<crush_t, field_type_t::N1>;
  71 using slot_3_t = _slot_t<snap_gen_t, field_type_t::N3>;
  72
  73 struct node_range_t {
  74   node_offset_t start;
  75   node_offset_t end;
  76 };
  77
  78 template <typename FieldType>
  79 const char* fields_start(const FieldType& node) {
  80   return reinterpret_cast<const char*>(&node);
  81 }
  82
  83 template <node_type_t NODE_TYPE, typename FieldType>
  84 node_range_t fields_free_range_before(
  85     const FieldType& node, index_t index) {
  86   assert(index <= node.num_keys);
  87   node_offset_t offset_start = node.get_key_start_offset(index);
  88   node_offset_t offset_end =
  89     (index == 0 ? FieldType::SIZE
  90                    : node.get_item_start_offset(index - 1));
  91   if constexpr (NODE_TYPE == node_type_t::INTERNAL) {
  92     if (node.is_level_tail() && index == node.num_keys) {
  93       offset_end -= sizeof(laddr_t);
  94     }
  95   }
  96   assert(offset_start <= offset_end);
  97   assert(offset_end - offset_start < FieldType::SIZE);
  98   return {offset_start, offset_end};
  99 }
 100
 101 /**
 102  * _node_fields_013_t (node_fields_0_t, node_fields_1_t, leaf_fields_3_t
 103  *
 104  * The STAGE_LEFT layout implementation for node N0/N1, or the STAGE_RIGHT
 105  * layout implementation for leaf node N3.
 106  *
 107  * The node layout storing n slots:
 108  *
 109  * # <----------------------------- node range --------------------------------------> #
 110  * #                                                 #<~># free space                  #
 111  * # <----- left part -----------------------------> # <~# <----- right slots -------> #
 112  * #               # <---- left slots -------------> #~> #                             #
 113  * #               #                slots [2, n) |<~>#   #<~>| right slots [2, n)      #
 114  * #               # <- slot 0 -> | <- slot 1 -> |   #   #   | <-- s1 --> | <-- s0 --> #
 115  * #               #              |              |   #   #   |            |            #
 116  * #        | num_ #     | right  |     | right  |   #   #   | next-stage | next-stage #
 117  * # header | keys # key | offset | key | offset |   #   #   | container  | container  #
 118  * #        |      # 0   | 0      | 1   | 1      |...#...#...| or onode 1 | or onode 0 #
 119  *                           |              |                ^            ^
 120  *                           |              |                |            |
 121  *                           |              +----------------+            |
 122  *                           +--------------------------------------------+
 123  */
 124 template <typename SlotType>
 125 struct _node_fields_013_t {
 126   // TODO: decide by NODE_BLOCK_SIZE, sizeof(SlotType), sizeof(laddr_t)
 127   // and the minimal size of variable_key.
 128   using num_keys_t = uint8_t;
 129   using key_t = typename SlotType::key_t;
 130   using key_get_type = const key_t&;
 131   using me_t = _node_fields_013_t<SlotType>;
 132   static constexpr field_type_t FIELD_TYPE = SlotType::FIELD_TYPE;
 133   static constexpr node_offset_t SIZE = NODE_BLOCK_SIZE;
 134   static constexpr node_offset_t HEADER_SIZE =
 135     sizeof(node_header_t) + sizeof(num_keys_t);
 136   static constexpr node_offset_t ITEM_OVERHEAD = SlotType::OVERHEAD;
 137
 138   bool is_level_tail() const { return header.get_is_level_tail(); }
 139   node_offset_t total_size() const { return SIZE; }
 140   key_get_type get_key(index_t index) const {
 141     assert(index < num_keys);
 142     return slots[index].key;
 143   }
 144   node_offset_t get_key_start_offset(index_t index) const {
 145     assert(index <= num_keys);
 146     auto offset = HEADER_SIZE + sizeof(SlotType) * index;
 147     assert(offset < SIZE);
 148     return offset;
 149   }
 150   node_offset_t get_item_start_offset(index_t index) const {
 151     assert(index < num_keys);
 152     auto offset = slots[index].right_offset;
 153     assert(offset <= SIZE);
 154     return offset;
 155   }
 156   const void* p_offset(index_t index) const {
 157     assert(index < num_keys);
 158     return &slots[index].right_offset;
 159   }
 160   node_offset_t get_item_end_offset(index_t index) const {
 161     return index == 0 ? SIZE : get_item_start_offset(index - 1);
 162   }
 163   template <node_type_t NODE_TYPE>
 164   node_offset_t free_size_before(index_t index) const {
 165     auto range = fields_free_range_before<NODE_TYPE>(*this, index);
 166     return range.end - range.start;
 167   }
 168
 169   static node_offset_t estimate_insert_one() { return sizeof(SlotType); }
 170   template <KeyT KT>
 171   static void insert_at(
 172       NodeExtentMutable&, const full_key_t<KT>& key,
 173       const me_t& node, index_t index, node_offset_t size_right);
 174   static void update_size_at(
 175       NodeExtentMutable&, const me_t& node, index_t index, int change);
 176   static void append_key(
 177       NodeExtentMutable&, const key_t& key, char*& p_append);
 178   template <KeyT KT>
 179   static void append_key(
 180       NodeExtentMutable& mut, const full_key_t<KT>& key, char*& p_append) {
 181     append_key(mut, key_t::template from_key<KT>(key), p_append);
 182   }
 183   static void append_offset(
 184       NodeExtentMutable& mut, node_offset_t offset_to_right, char*& p_append);
 185
 186   node_header_t header;
 187   num_keys_t num_keys = 0u;
 188   SlotType slots[];
 189 } __attribute__((packed));
 190 using node_fields_0_t = _node_fields_013_t<slot_0_t>;
 191 using node_fields_1_t = _node_fields_013_t<slot_1_t>;
 192
 193 /**
 194  * node_fields_2_t
 195  *
 196  * The STAGE_STRING layout implementation for node N2.
 197  *
 198  * The node layout storing n slots:
 199  *
 200  * # <--------------------------------- node range ----------------------------------------> #
 201  * #                                     #<~># free space                                    #
 202  * # <------- left part ---------------> # <~# <--------- right slots ---------------------> #
 203  * #               # <---- offsets ----> #~> #<~>| slots [2, n)                              #
 204  * #               #  offsets [2, n) |<~>#   #   | <----- slot 1 ----> | <----- slot 0 ----> #
 205  * #               #                 |   #   #   |                     |                     #
 206  * #        | num_ # offset | offset |   #   #   | next-stage | ns-oid | next-stage | ns-oid #
 207  * # header | keys # 0      | 1      |...#...#...| container1 | 1      | container0 | 0      #
 208  *                     |        |                ^                     ^
 209  *                     |        |                |                     |
 210  *                     |        +----------------+                     |
 211  *                     +-----------------------------------------------+
 212  */
 213 struct node_fields_2_t {
 214   // TODO: decide by NODE_BLOCK_SIZE, sizeof(node_off_t), sizeof(laddr_t)
 215   // and the minimal size of variable_key.
 216   using num_keys_t = uint8_t;
 217   using key_t = ns_oid_view_t;
 218   using key_get_type = key_t;
 219   static constexpr field_type_t FIELD_TYPE = field_type_t::N2;
 220   static constexpr node_offset_t SIZE = NODE_BLOCK_SIZE;
 221   static constexpr node_offset_t HEADER_SIZE =
 222     sizeof(node_header_t) + sizeof(num_keys_t);
 223   static constexpr node_offset_t ITEM_OVERHEAD = sizeof(node_offset_t);
 224
 225   bool is_level_tail() const { return header.get_is_level_tail(); }
 226   node_offset_t total_size() const { return SIZE; }
 227   key_get_type get_key(index_t index) const {
 228     assert(index < num_keys);
 229     node_offset_t item_end_offset =
 230       (index == 0 ? SIZE : offsets[index - 1]);
 231     assert(item_end_offset <= SIZE);
 232     const char* p_start = fields_start(*this);
 233     return key_t(p_start + item_end_offset);
 234   }
 235   node_offset_t get_key_start_offset(index_t index) const {
 236     assert(index <= num_keys);
 237     auto offset = HEADER_SIZE + sizeof(node_offset_t) * num_keys;
 238     assert(offset <= SIZE);
 239     return offset;
 240   }
 241   node_offset_t get_item_start_offset(index_t index) const {
 242     assert(index < num_keys);
 243     auto offset = offsets[index];
 244     assert(offset <= SIZE);
 245     return offset;
 246   }
 247   const void* p_offset(index_t index) const {
 248     assert(index < num_keys);
 249     return &offsets[index];
 250   }
 251   node_offset_t get_item_end_offset(index_t index) const {
 252     return index == 0 ? SIZE : get_item_start_offset(index - 1);
 253   }
 254   template <node_type_t NODE_TYPE>
 255   node_offset_t free_size_before(index_t index) const {
 256     auto range = fields_free_range_before<NODE_TYPE>(*this, index);
 257     return range.end - range.start;
 258   }
 259
 260   static node_offset_t estimate_insert_one() { return sizeof(node_offset_t); }
 261   template <KeyT KT>
 262   static void insert_at(
 263       NodeExtentMutable& mut, const full_key_t<KT>& key,
 264       const node_fields_2_t& node, index_t index, node_offset_t size_right) {
 265     ceph_abort("not implemented");
 266   }
 267   static void update_size_at(
 268       NodeExtentMutable& mut, const node_fields_2_t& node, index_t index, int change) {
 269     ceph_abort("not implemented");
 270   }
 271   static void append_key(
 272       NodeExtentMutable& mut, const key_t& key, char*& p_append) {
 273     ns_oid_view_t::append(mut, key, p_append);
 274   }
 275   template <KeyT KT>
 276   static void append_key(
 277       NodeExtentMutable& mut, const full_key_t<KT>& key, char*& p_append) {
 278     ns_oid_view_t::append<KT>(mut, key, p_append);
 279   }
 280   static void append_offset(
 281       NodeExtentMutable& mut, node_offset_t offset_to_right, char*& p_append);
 282
 283   node_header_t header;
 284   num_keys_t num_keys = 0u;
 285   node_offset_t offsets[];
 286 } __attribute__((packed));
 287
 288 /**
 289  * internal_fields_3_t
 290  *
 291  * The STAGE_RIGHT layout implementation for N2.
 292  *
 293  * The node layout storing 3 children:
 294  *
 295  * # <---------------- node range ---------------------------> #
 296  * #               # <-- keys ---> # <---- laddrs -----------> #
 297  * #  free space:  #           |<~>#                       |<~>#
 298  * #               #           |   #                       |   #
 299  * #        | num_ # key | key |   # laddr | laddr | laddr |   #
 300  * # header | keys # 0   | 1   |...# 0     | 1     | 2     |...#
 301  */
 302 // TODO: decide by NODE_BLOCK_SIZE, sizeof(snap_gen_t), sizeof(laddr_t)
 303 static constexpr unsigned MAX_NUM_KEYS_I3 = 170u;
 304 template <unsigned MAX_NUM_KEYS>
 305 struct _internal_fields_3_t {
 306   using key_get_type = const snap_gen_t&;
 307   using me_t = _internal_fields_3_t<MAX_NUM_KEYS>;
 308   // TODO: decide by NODE_BLOCK_SIZE, sizeof(snap_gen_t), sizeof(laddr_t)
 309   using num_keys_t = uint8_t;
 310   static constexpr field_type_t FIELD_TYPE = field_type_t::N3;
 311   static constexpr node_offset_t SIZE = sizeof(me_t);
 312   static constexpr node_offset_t HEADER_SIZE =
 313     sizeof(node_header_t) + sizeof(num_keys_t);
 314   static constexpr node_offset_t ITEM_OVERHEAD = 0u;
 315
 316   bool is_level_tail() const { return header.get_is_level_tail(); }
 317   node_offset_t total_size() const {
 318     if (is_level_tail()) {
 319       return SIZE - sizeof(snap_gen_t);
 320     } else {
 321       return SIZE;
 322     }
 323   }
 324   key_get_type get_key(index_t index) const {
 325     assert(index < num_keys);
 326     return keys[index];
 327   }
 328   template <node_type_t NODE_TYPE>
 329   std::enable_if_t<NODE_TYPE == node_type_t::INTERNAL, node_offset_t>
 330   free_size_before(index_t index) const {
 331     assert(index <= num_keys);
 332     assert(num_keys <= (is_level_tail() ? MAX_NUM_KEYS - 1 : MAX_NUM_KEYS));
 333     auto free = (MAX_NUM_KEYS - index) * (sizeof(snap_gen_t) + sizeof(laddr_t));
 334     if (is_level_tail() && index == num_keys) {
 335       free -= (sizeof(snap_gen_t) + sizeof(laddr_t));
 336     }
 337     assert(free < SIZE);
 338     return free;
 339   }
 340
 341   static node_offset_t estimate_insert_one() {
 342     return sizeof(snap_gen_t) + sizeof(laddr_t);
 343   }
 344   template <KeyT KT>
 345   static void insert_at(
 346       NodeExtentMutable& mut, const full_key_t<KT>& key,
 347       const me_t& node, index_t index, node_offset_t size_right) {
 348     ceph_abort("not implemented");
 349   }
 350   static void update_size_at(
 351       NodeExtentMutable& mut, const me_t& node, index_t index, int change) {
 352     ceph_abort("not implemented");
 353   }
 354
 355   node_header_t header;
 356   num_keys_t num_keys = 0u;
 357   snap_gen_t keys[MAX_NUM_KEYS];
 358   laddr_packed_t child_addrs[MAX_NUM_KEYS];
 359 } __attribute__((packed));
 360 static_assert(_internal_fields_3_t<MAX_NUM_KEYS_I3>::SIZE <= NODE_BLOCK_SIZE &&
 361               _internal_fields_3_t<MAX_NUM_KEYS_I3 + 1>::SIZE > NODE_BLOCK_SIZE);
 362 using internal_fields_3_t = _internal_fields_3_t<MAX_NUM_KEYS_I3>;
 363
 364 using leaf_fields_3_t = _node_fields_013_t<slot_3_t>;
 365
 366 }