ceph/src/crimson/os/seastore/btree/btree_range_pin.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
   6 #include <boost/intrusive/set.hpp>
   7
   8 #include "crimson/common/log.h"
   9
  10 #include "crimson/os/seastore/cache.h"
  11 #include "crimson/os/seastore/cached_extent.h"
  12 #include "crimson/os/seastore/seastore_types.h"
  13
  14 namespace crimson::os::seastore {
  15
  16 template <typename node_key_t>
  17 struct op_context_t {
  18   Cache &cache;
  19   Transaction &trans;
  20 };
  21
  22 constexpr uint16_t MAX_FIXEDKVBTREE_DEPTH = 8;
  23
  24 template <typename T>
  25 struct min_max_t {};
  26
  27 template <>
  28 struct min_max_t<laddr_t> {
  29   static constexpr laddr_t max = L_ADDR_MAX;
  30   static constexpr laddr_t min = L_ADDR_MIN;
  31 };
  32
  33 template <>
  34 struct min_max_t<paddr_t> {
  35   static constexpr paddr_t max = P_ADDR_MAX;
  36   static constexpr paddr_t min = P_ADDR_MIN;
  37 };
  38
  39 template <typename bound_t>
  40 struct fixed_kv_node_meta_t {
  41   bound_t begin = min_max_t<bound_t>::min;
  42   bound_t end = min_max_t<bound_t>::min;
  43   depth_t depth = 0;
  44
  45   bool is_parent_of(const fixed_kv_node_meta_t &other) const {
  46     return (depth == other.depth + 1) &&
  47       (begin <= other.begin) &&
  48       (end > other.begin);
  49   }
  50
  51   bool is_in_range(const bound_t key) const {
  52     return begin <= key && end > key;
  53   }
  54
  55   std::pair<fixed_kv_node_meta_t, fixed_kv_node_meta_t> split_into(bound_t pivot) const {
  56     return std::make_pair(
  57       fixed_kv_node_meta_t{begin, pivot, depth},
  58       fixed_kv_node_meta_t{pivot, end, depth});
  59   }
  60
  61   static fixed_kv_node_meta_t merge_from(
  62     const fixed_kv_node_meta_t &lhs, const fixed_kv_node_meta_t &rhs) {
  63     ceph_assert(lhs.depth == rhs.depth);
  64     return fixed_kv_node_meta_t{lhs.begin, rhs.end, lhs.depth};
  65   }
  66
  67   static std::pair<fixed_kv_node_meta_t, fixed_kv_node_meta_t>
  68   rebalance(const fixed_kv_node_meta_t &lhs, const fixed_kv_node_meta_t &rhs, bound_t pivot) {
  69     ceph_assert(lhs.depth == rhs.depth);
  70     return std::make_pair(
  71       fixed_kv_node_meta_t{lhs.begin, pivot, lhs.depth},
  72       fixed_kv_node_meta_t{pivot, rhs.end, lhs.depth});
  73   }
  74
  75   bool is_root() const {
  76     return begin == min_max_t<bound_t>::min && end == min_max_t<bound_t>::max;
  77   }
  78 };
  79
  80 template <typename bound_t>
  81 inline std::ostream &operator<<(
  82   std::ostream &lhs,
  83   const fixed_kv_node_meta_t<bound_t> &rhs)
  84 {
  85   return lhs << "btree_node_meta_t("
  86              << "begin=" << rhs.begin
  87              << ", end=" << rhs.end
  88              << ", depth=" << rhs.depth
  89              << ")";
  90 }
  91
  92 /**
  93  * fixed_kv_node_meta_le_t
  94  *
  95  * On disk layout for fixed_kv_node_meta_t
  96  */
  97 template <typename bound_le_t>
  98 struct fixed_kv_node_meta_le_t {
  99   bound_le_t begin = bound_le_t(0);
 100   bound_le_t end = bound_le_t(0);
 101   depth_le_t depth = init_depth_le(0);
 102
 103   fixed_kv_node_meta_le_t() = default;
 104   fixed_kv_node_meta_le_t(
 105     const fixed_kv_node_meta_le_t<bound_le_t> &) = default;
 106   explicit fixed_kv_node_meta_le_t(
 107     const fixed_kv_node_meta_t<typename bound_le_t::orig_type> &val)
 108     : begin(val.begin),
 109       end(val.end),
 110       depth(init_depth_le(val.depth)) {}
 111
 112   operator fixed_kv_node_meta_t<typename bound_le_t::orig_type>() const {
 113     return fixed_kv_node_meta_t<typename bound_le_t::orig_type>{
 114             begin, end, depth };
 115   }
 116 };
 117
 118 template <typename key_t, typename val_t>
 119 class BtreeNodeMapping : public PhysicalNodeMapping<key_t, val_t> {
 120
 121   op_context_t<key_t> ctx;
 122   /**
 123    * parent
 124    *
 125    * populated until link_extent is called to ensure cache residence
 126    * until add_pin is called.
 127    */
 128   CachedExtentRef parent;
 129
 130   val_t value;
 131   extent_len_t len;
 132   fixed_kv_node_meta_t<key_t> range;
 133   uint16_t pos = std::numeric_limits<uint16_t>::max();
 134
 135 public:
 136   using val_type = val_t;
 137   BtreeNodeMapping(op_context_t<key_t> ctx) : ctx(ctx) {}
 138
 139   BtreeNodeMapping(
 140     op_context_t<key_t> ctx,
 141     CachedExtentRef parent,
 142     uint16_t pos,
 143     val_t &value,
 144     extent_len_t len,
 145     fixed_kv_node_meta_t<key_t> &&meta)
 146     : ctx(ctx),
 147       parent(parent),
 148       value(value),
 149       len(len),
 150       range(std::move(meta)),
 151       pos(pos)
 152   {
 153     if (!parent->is_pending()) {
 154       this->child_pos = {parent, pos};
 155     }
 156   }
 157
 158   CachedExtentRef get_parent() const final {
 159     return parent;
 160   }
 161
 162   CachedExtentRef get_parent() {
 163     return parent;
 164   }
 165
 166   void set_parent(CachedExtentRef ext) {
 167     parent = ext;
 168   }
 169
 170   uint16_t get_pos() const final {
 171     return pos;
 172   }
 173
 174   extent_len_t get_length() const final {
 175     ceph_assert(range.end > range.begin);
 176     return len;
 177   }
 178
 179   extent_types_t get_type() const override {
 180     ceph_abort("should never happen");
 181     return extent_types_t::ROOT;
 182   }
 183
 184   val_t get_val() const final {
 185     return value;
 186   }
 187
 188   key_t get_key() const final {
 189     return range.begin;
 190   }
 191
 192   PhysicalNodeMappingRef<key_t, val_t> duplicate() const final {
 193     auto ret = std::unique_ptr<BtreeNodeMapping<key_t, val_t>>(
 194       new BtreeNodeMapping<key_t, val_t>(ctx));
 195     ret->range = range;
 196     ret->value = value;
 197     ret->parent = parent;
 198     ret->len = len;
 199     ret->pos = pos;
 200     return ret;
 201   }
 202
 203   bool has_been_invalidated() const final {
 204     return parent->has_been_invalidated();
 205   }
 206
 207   get_child_ret_t<LogicalCachedExtent> get_logical_extent(Transaction&) final;
 208 };
 209
 210 }