1 files changed, 274 insertions, 0 deletions
diff --git a/src/crimson/os/seastore/lba_manager/btree/btree_range_pin.h b/src/crimson/os/seastore/lba_manager/btree/btree_range_pin.h
new file mode 100644
index 000000000..3fa218fc8
--- /dev/null
+++ b/src/crimson/os/seastore/lba_manager/btree/btree_range_pin.h
@@ -0,0 +1,274 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+#pragma once
+
+#include <boost/intrusive/set.hpp>
+
+#include "crimson/os/seastore/cached_extent.h"
+#include "crimson/os/seastore/seastore_types.h"
+
+namespace crimson::os::seastore::lba_manager::btree {
+
+class LBANode;
+using LBANodeRef = TCachedExtentRef<LBANode>;
+
+struct lba_node_meta_t {
+  laddr_t begin = 0;
+  laddr_t end = 0;
+  depth_t depth = 0;
+
+  bool is_parent_of(const lba_node_meta_t &other) const {
+    return (depth == other.depth + 1) &&
+      (begin <= other.begin) &&
+      (end >= other.end);
+  }
+
+  std::pair<lba_node_meta_t, lba_node_meta_t> split_into(laddr_t pivot) const {
+    return std::make_pair(
+      lba_node_meta_t{begin, pivot, depth},
+      lba_node_meta_t{pivot, end, depth});
+  }
+
+  static lba_node_meta_t merge_from(
+    const lba_node_meta_t &lhs, const lba_node_meta_t &rhs) {
+    assert(lhs.depth == rhs.depth);
+    return lba_node_meta_t{lhs.begin, rhs.end, lhs.depth};
+  }
+
+  static std::pair<lba_node_meta_t, lba_node_meta_t>
+  rebalance(const lba_node_meta_t &lhs, const lba_node_meta_t &rhs, laddr_t pivot) {
+    assert(lhs.depth == rhs.depth);
+    return std::make_pair(
+      lba_node_meta_t{lhs.begin, pivot, lhs.depth},
+      lba_node_meta_t{pivot, rhs.end, lhs.depth});
+  }
+
+  bool is_root() const {
+    return begin == 0 && end == L_ADDR_MAX;
+  }
+};
+
+inline std::ostream &operator<<(
+  std::ostream &lhs,
+  const lba_node_meta_t &rhs)
+{
+  return lhs << "btree_node_meta_t("
+	     << "begin=" << rhs.begin
+	     << ", end=" << rhs.end
+	     << ", depth=" << rhs.depth
+	     << ")";
+}
+
+/**
+ * btree_range_pin_t
+ *
+ * Element tracked by btree_pin_set_t below.  Encapsulates the intrusive_set
+ * hook, the lba_node_meta_t representing the lba range covered by a node,
+ * and extent and ref members intended to hold a reference when the extent
+ * should be pinned.
+ */
+class btree_pin_set_t;
+class btree_range_pin_t : public boost::intrusive::set_base_hook<> {
+  friend class btree_pin_set_t;
+  lba_node_meta_t range;
+
+  btree_pin_set_t *pins = nullptr;
+
+  // We need to be able to remember extent without holding a reference,
+  // but we can do it more compactly -- TODO
+  CachedExtent *extent = nullptr;
+  CachedExtentRef ref;
+
+  using index_t = boost::intrusive::set<btree_range_pin_t>;
+
+  static auto get_tuple(const lba_node_meta_t &meta) {
+    return std::make_tuple(-meta.depth, meta.begin);
+  }
+
+  void acquire_ref() {
+    ref = CachedExtentRef(extent);
+  }
+
+  void drop_ref() {
+    ref.reset();
+  }
+
+public:
+  btree_range_pin_t() = default;
+  btree_range_pin_t(CachedExtent *extent)
+    : extent(extent) {}
+  btree_range_pin_t(const btree_range_pin_t &rhs, CachedExtent *extent)
+    : range(rhs.range), extent(extent) {}
+
+  bool has_ref() const {
+    return !!ref;
+  }
+
+  bool is_root() const {
+    return range.is_root();
+  }
+
+  void set_range(const lba_node_meta_t &nrange) {
+    range = nrange;
+  }
+  void set_extent(CachedExtent *nextent) {
+    assert(!extent);
+    extent = nextent;
+  }
+
+  void take_pin(btree_range_pin_t &other);
+
+  friend bool operator<(
+    const btree_range_pin_t &lhs, const btree_range_pin_t &rhs) {
+    return get_tuple(lhs.range) < get_tuple(rhs.range);
+  }
+  friend bool operator>(
+    const btree_range_pin_t &lhs, const btree_range_pin_t &rhs) {
+    return get_tuple(lhs.range) > get_tuple(rhs.range);
+  }
+  friend bool operator==(
+    const btree_range_pin_t &lhs, const btree_range_pin_t &rhs) {
+    return get_tuple(lhs.range) == rhs.get_tuple(rhs.range);
+  }
+
+  struct meta_cmp_t {
+    bool operator()(
+      const btree_range_pin_t &lhs, const lba_node_meta_t &rhs) const {
+      return get_tuple(lhs.range) < get_tuple(rhs);
+    }
+    bool operator()(
+      const lba_node_meta_t &lhs, const btree_range_pin_t &rhs) const {
+      return get_tuple(lhs) < get_tuple(rhs.range);
+    }
+  };
+
+  friend std::ostream &operator<<(
+    std::ostream &lhs,
+    const btree_range_pin_t &rhs) {
+    return lhs << "btree_range_pin_t("
+	       << "begin=" << rhs.range.begin
+	       << ", end=" << rhs.range.end
+	       << ", depth=" << rhs.range.depth
+	       << ", extent=" << rhs.extent
+	       << ")";
+  }
+
+  friend class BtreeLBAPin;
+  ~btree_range_pin_t();
+};
+
+/**
+ * btree_pin_set_t
+ *
+ * Ensures that for every cached node, all parent LBANodes required
+ * to map it are present in cache.  Relocating these nodes can
+ * therefore be done without further reads or cache space.
+ *
+ * Contains a btree_range_pin_t for every clean or dirty LBANode
+ * or LogicalCachedExtent instance in cache at any point in time.
+ * For any LBANode, the contained btree_range_pin_t will hold
+ * a reference to that node pinning it in cache as long as that
+ * node has children in the set.  This invariant can be violated
+ * only by calling retire_extent and is repaired by calling
+ * check_parent synchronously after adding any new extents.
+ */
+class btree_pin_set_t {
+  friend class btree_range_pin_t;
+  using pins_t = btree_range_pin_t::index_t;
+  pins_t pins;
+
+  pins_t::iterator get_iter(btree_range_pin_t &pin) {
+    return pins_t::s_iterator_to(pin);
+  }
+
+  /// Removes pin from set optionally checking whether parent has other children
+  void remove_pin(btree_range_pin_t &pin, bool check_parent);
+
+  void replace_pin(btree_range_pin_t &to, btree_range_pin_t &from);
+
+  /// Returns parent pin if exists
+  btree_range_pin_t *maybe_get_parent(const lba_node_meta_t &pin);
+
+  /// Returns earliest child pin if exist
+  const btree_range_pin_t *maybe_get_first_child(const lba_node_meta_t &pin) const;
+
+  /// Releases pin if it has no children
+  void release_if_no_children(btree_range_pin_t &pin);
+
+public:
+  /// Adds pin to set, assumes set is consistent
+  void add_pin(btree_range_pin_t &pin);
+
+  /**
+   * retire/check_parent
+   *
+   * See BtreeLBAManager::complete_transaction.
+   * retire removes the specified pin from the set, but does not
+   * check parents.  After any new extents are added to the set,
+   * the caller is required to call check_parent to restore the
+   * invariant.
+   */
+  void retire(btree_range_pin_t &pin);
+  void check_parent(btree_range_pin_t &pin);
+
+  ~btree_pin_set_t() {
+    assert(pins.empty());
+  }
+};
+
+class BtreeLBAPin : public LBAPin {
+  friend class BtreeLBAManager;
+
+  /**
+   * parent
+   *
+   * populated until link_extent is called to ensure cache residence
+   * until add_pin is called.
+   */
+  CachedExtentRef parent;
+
+  paddr_t paddr;
+  btree_range_pin_t pin;
+
+public:
+  BtreeLBAPin() = default;
+
+  BtreeLBAPin(
+    CachedExtentRef parent,
+    paddr_t paddr,
+    lba_node_meta_t &&meta)
+    : parent(parent), paddr(paddr) {
+    pin.set_range(std::move(meta));
+  }
+
+  void link_extent(LogicalCachedExtent *ref) final {
+    pin.set_extent(ref);
+  }
+
+  extent_len_t get_length() const final {
+    assert(pin.range.end > pin.range.begin);
+    return pin.range.end - pin.range.begin;
+  }
+
+  paddr_t get_paddr() const final {
+    return paddr;
+  }
+
+  laddr_t get_laddr() const final {
+    return pin.range.begin;
+  }
+
+  LBAPinRef duplicate() const final {
+    auto ret = std::unique_ptr<BtreeLBAPin>(new BtreeLBAPin);
+    ret->pin.set_range(pin.range);
+    ret->paddr = paddr;
+    return ret;
+  }
+
+  void take_pin(LBAPin &opin) final {
+    pin.take_pin(static_cast<BtreeLBAPin&>(opin).pin);
+  }
+};
+
+}