ceph/src/crimson/os/seastore/onode_manager/staged-fltree/stages/item_iterator_stage.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 "crimson/os/seastore/onode_manager/staged-fltree/node_types.h"
   7 #include "key_layout.h"
   8 #include "stage_types.h"
   9
  10 namespace crimson::os::seastore::onode {
  11
  12 class NodeExtentMutable;
  13
  14 /**
  15  * item_iterator_t
  16  *
  17  * The STAGE_STRING implementation for node N0/N1, implements staged contract
  18  * as an iterative container to resolve crush hash conflicts.
  19  *
  20  * The layout of the contaner to index ns, oid strings storing n items:
  21  *
  22  * # <--------- container range ---------> #
  23  * #<~># items [i+1, n)                    #
  24  * #   #                  items [0, i) #<~>#
  25  * #   # <------ item i -------------> #   #
  26  * #   # <--- item_range ---> |        #   #
  27  * #   #                      |        #   #
  28  * #   # next-stage | ns-oid  | back_  #   #
  29  * #   #  contaner  | strings | offset #   #
  30  * #...#   range    |         |        #...#
  31  * ^   ^                           |       ^
  32  * |   |                           |       |
  33  * |   +---------------------------+       |
  34  * + p_items_start             p_items_end +
  35  */
  36 template <node_type_t NODE_TYPE>
  37 class item_iterator_t {
  38   using value_t = value_type_t<NODE_TYPE>;
  39  public:
  40   item_iterator_t(const memory_range_t& range)
  41       : p_items_start(range.p_start), p_items_end(range.p_end) {
  42     assert(p_items_start < p_items_end);
  43     next_item_range(p_items_end);
  44   }
  45
  46   const char* p_start() const { return item_range.p_start; }
  47   const char* p_end() const { return item_range.p_end + sizeof(node_offset_t); }
  48   const memory_range_t& get_item_range() const { return item_range; }
  49   node_offset_t get_back_offset() const { return back_offset; }
  50
  51   // container type system
  52   using key_get_type = const ns_oid_view_t&;
  53   static constexpr auto CONTAINER_TYPE = ContainerType::ITERATIVE;
  54   index_t index() const { return _index; }
  55   key_get_type get_key() const {
  56     if (!key.has_value()) {
  57       key = ns_oid_view_t(item_range.p_end);
  58       assert(item_range.p_start < (*key).p_start());
  59     }
  60     return *key;
  61   }
  62   node_offset_t size() const {
  63     size_t ret = item_range.p_end - item_range.p_start + sizeof(node_offset_t);
  64     assert(ret < NODE_BLOCK_SIZE);
  65     return ret;
  66   };
  67   node_offset_t size_to_nxt() const {
  68     size_t ret = get_key().size() + sizeof(node_offset_t);
  69     assert(ret < NODE_BLOCK_SIZE);
  70     return ret;
  71   }
  72   node_offset_t size_overhead() const {
  73     return sizeof(node_offset_t) + get_key().size_overhead();
  74   }
  75   memory_range_t get_nxt_container() const {
  76     return {item_range.p_start, get_key().p_start()};
  77   }
  78   bool has_next() const {
  79     assert(p_items_start <= item_range.p_start);
  80     return p_items_start < item_range.p_start;
  81   }
  82   const item_iterator_t<NODE_TYPE>& operator++() const {
  83     assert(has_next());
  84     next_item_range(item_range.p_start);
  85     key.reset();
  86     ++_index;
  87     return *this;
  88   }
  89   void encode(const char* p_node_start, ceph::bufferlist& encoded) const {
  90     int start_offset = p_items_start - p_node_start;
  91     int end_offset = p_items_end - p_node_start;
  92     assert(start_offset > 0 && start_offset < NODE_BLOCK_SIZE);
  93     assert(end_offset > 0 && end_offset <= NODE_BLOCK_SIZE);
  94     ceph::encode(static_cast<node_offset_t>(start_offset), encoded);
  95     ceph::encode(static_cast<node_offset_t>(end_offset), encoded);
  96     ceph::encode(_index, encoded);
  97   }
  98
  99   static item_iterator_t decode(const char* p_node_start,
 100                                 ceph::bufferlist::const_iterator& delta) {
 101     node_offset_t start_offset;
 102     ceph::decode(start_offset, delta);
 103     node_offset_t end_offset;
 104     ceph::decode(end_offset, delta);
 105     assert(start_offset < end_offset);
 106     assert(end_offset <= NODE_BLOCK_SIZE);
 107     index_t index;
 108     ceph::decode(index, delta);
 109
 110     item_iterator_t ret({p_node_start + start_offset,
 111                          p_node_start + end_offset});
 112     while (index > 0) {
 113       ++ret;
 114       --index;
 115     }
 116     return ret;
 117   }
 118
 119   static node_offset_t header_size() { return 0u; }
 120
 121   template <KeyT KT>
 122   static node_offset_t estimate_insert(
 123       const full_key_t<KT>& key, const value_t&) {
 124     return ns_oid_view_t::estimate_size<KT>(key) + sizeof(node_offset_t);
 125   }
 126
 127   template <KeyT KT>
 128   static memory_range_t insert_prefix(
 129       NodeExtentMutable& mut, const item_iterator_t<NODE_TYPE>& iter,
 130       const full_key_t<KT>& key, bool is_end,
 131       node_offset_t size, const char* p_left_bound);
 132
 133   static void update_size(
 134       NodeExtentMutable& mut, const item_iterator_t<NODE_TYPE>& iter, int change);
 135
 136   static node_offset_t trim_until(NodeExtentMutable&, const item_iterator_t<NODE_TYPE>&);
 137   static node_offset_t trim_at(
 138       NodeExtentMutable&, const item_iterator_t<NODE_TYPE>&, node_offset_t trimmed);
 139
 140   template <KeyT KT>
 141   class Appender;
 142
 143  private:
 144   void next_item_range(const char* p_end) const {
 145     auto p_item_end = p_end - sizeof(node_offset_t);
 146     assert(p_items_start < p_item_end);
 147     back_offset = reinterpret_cast<const node_offset_packed_t*>(p_item_end)->value;
 148     assert(back_offset);
 149     const char* p_item_start = p_item_end - back_offset;
 150     assert(p_items_start <= p_item_start);
 151     item_range = {p_item_start, p_item_end};
 152   }
 153
 154   const char* p_items_start;
 155   const char* p_items_end;
 156   mutable memory_range_t item_range;
 157   mutable node_offset_t back_offset;
 158   mutable std::optional<ns_oid_view_t> key;
 159   mutable index_t _index = 0u;
 160 };
 161
 162 template <node_type_t NODE_TYPE>
 163 template <KeyT KT>
 164 class item_iterator_t<NODE_TYPE>::Appender {
 165  public:
 166   Appender(NodeExtentMutable* p_mut, char* p_append)
 167     : p_mut{p_mut}, p_append{p_append} {}
 168   bool append(const item_iterator_t<NODE_TYPE>& src, index_t& items);
 169   char* wrap() { return p_append; }
 170   std::tuple<NodeExtentMutable*, char*> open_nxt(const key_get_type&);
 171   std::tuple<NodeExtentMutable*, char*> open_nxt(const full_key_t<KT>&);
 172   void wrap_nxt(char* _p_append);
 173
 174  private:
 175   NodeExtentMutable* p_mut;
 176   char* p_append;
 177   char* p_offset_while_open;
 178 };
 179
 180 }