ceph/src/crimson/os/seastore/onode_manager/staged-fltree/tree.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include "tree.h"
   5
   6 #include "node.h"
   7 #include "node_extent_manager.h"
   8 #include "stages/key_layout.h"
   9 #include "super.h"
  10
  11 namespace crimson::os::seastore::onode {
  12
  13 using btree_ertr = Btree::btree_ertr;
  14 template <class ValueT=void>
  15 using btree_future = Btree::btree_future<ValueT>;
  16 using Cursor = Btree::Cursor;
  17
  18 Cursor::Cursor(Btree* p_tree, Ref<tree_cursor_t> _p_cursor)
  19   : p_tree(p_tree) {
  20   if (_p_cursor->is_end()) {
  21     // no need to hold the leaf node
  22   } else {
  23     p_cursor = _p_cursor;
  24   }
  25 }
  26 Cursor::Cursor(Btree* p_tree) : p_tree{p_tree} {}
  27 Cursor::Cursor(const Cursor&) = default;
  28 Cursor::Cursor(Cursor&&) noexcept = default;
  29 Cursor& Cursor::operator=(const Cursor&) = default;
  30 Cursor& Cursor::operator=(Cursor&&) = default;
  31 Cursor::~Cursor() = default;
  32
  33 bool Cursor::is_end() const {
  34   if (p_cursor) {
  35     assert(!p_cursor->is_end());
  36     return false;
  37   } else {
  38     return true;
  39   }
  40 }
  41
  42 ghobject_t Cursor::get_ghobj() const {
  43   return p_cursor->get_key_view().to_ghobj();
  44 }
  45
  46 const onode_t* Cursor::value() const {
  47   return p_cursor->get_p_value();
  48 }
  49
  50 bool Cursor::operator==(const Cursor& x) const {
  51   return p_cursor == x.p_cursor;
  52 }
  53
  54 Cursor& Cursor::operator++() {
  55   // TODO
  56   return *this;
  57 }
  58
  59 Cursor Cursor::operator++(int) {
  60   Cursor tmp = *this;
  61   ++*this;
  62   return tmp;
  63 }
  64
  65 Cursor Cursor::make_end(Btree* p_tree) {
  66   return {p_tree};
  67 }
  68
  69 Btree::Btree(NodeExtentManagerURef&& _nm)
  70   : nm{std::move(_nm)},
  71     root_tracker{RootNodeTracker::create(nm->is_read_isolated())} {}
  72
  73 Btree::~Btree() { assert(root_tracker->is_clean()); }
  74
  75 btree_future<> Btree::mkfs(Transaction& t) {
  76   return Node::mkfs(get_context(t), *root_tracker);
  77 }
  78
  79 btree_future<Cursor> Btree::begin(Transaction& t) {
  80   return get_root(t).safe_then([this, &t](auto root) {
  81     return root->lookup_smallest(get_context(t));
  82   }).safe_then([this](auto cursor) {
  83     return Cursor{this, cursor};
  84   });
  85 }
  86
  87 btree_future<Cursor> Btree::last(Transaction& t) {
  88   return get_root(t).safe_then([this, &t](auto root) {
  89     return root->lookup_largest(get_context(t));
  90   }).safe_then([this](auto cursor) {
  91     return Cursor(this, cursor);
  92   });
  93 }
  94
  95 Cursor Btree::end() {
  96   return Cursor::make_end(this);
  97 }
  98
  99 btree_future<bool>
 100 Btree::contains(Transaction& t, const ghobject_t& obj) {
 101   return seastar::do_with(
 102     full_key_t<KeyT::HOBJ>(obj),
 103     [this, &t](auto& key) -> btree_future<bool> {
 104       return get_root(t).safe_then([this, &t, &key](auto root) {
 105         // TODO: improve lower_bound()
 106         return root->lower_bound(get_context(t), key);
 107       }).safe_then([](auto result) {
 108         return MatchKindBS::EQ == result.match();
 109       });
 110     }
 111   );
 112 }
 113
 114 btree_future<Cursor>
 115 Btree::find(Transaction& t, const ghobject_t& obj) {
 116   return seastar::do_with(
 117     full_key_t<KeyT::HOBJ>(obj),
 118     [this, &t](auto& key) -> btree_future<Cursor> {
 119       return get_root(t).safe_then([this, &t, &key](auto root) {
 120         // TODO: improve lower_bound()
 121         return root->lower_bound(get_context(t), key);
 122       }).safe_then([this](auto result) {
 123         if (result.match() == MatchKindBS::EQ) {
 124           return Cursor(this, result.p_cursor);
 125         } else {
 126           return Cursor::make_end(this);
 127         }
 128       });
 129     }
 130   );
 131 }
 132
 133 btree_future<Cursor>
 134 Btree::lower_bound(Transaction& t, const ghobject_t& obj) {
 135   return seastar::do_with(
 136     full_key_t<KeyT::HOBJ>(obj),
 137     [this, &t](auto& key) -> btree_future<Cursor> {
 138       return get_root(t).safe_then([this, &t, &key](auto root) {
 139         return root->lower_bound(get_context(t), key);
 140       }).safe_then([this](auto result) {
 141         return Cursor(this, result.p_cursor);
 142       });
 143     }
 144   );
 145 }
 146
 147 btree_future<std::pair<Cursor, bool>>
 148 Btree::insert(Transaction& t, const ghobject_t& obj, const onode_t& value) {
 149   return seastar::do_with(
 150     full_key_t<KeyT::HOBJ>(obj),
 151     [this, &t, &value](auto& key) -> btree_future<std::pair<Cursor, bool>> {
 152       return get_root(t).safe_then([this, &t, &key, &value](auto root) {
 153         return root->insert(get_context(t), key, value);
 154       }).safe_then([this](auto ret) {
 155         auto& [cursor, success] = ret;
 156         return std::make_pair(Cursor(this, cursor), success);
 157       });
 158     }
 159   );
 160 }
 161
 162 btree_future<size_t> Btree::erase(Transaction& t, const ghobject_t& obj) {
 163   // TODO
 164   return btree_ertr::make_ready_future<size_t>(0u);
 165 }
 166
 167 btree_future<Cursor> Btree::erase(Cursor& pos) {
 168   // TODO
 169   return btree_ertr::make_ready_future<Cursor>(
 170       Cursor::make_end(this));
 171 }
 172
 173 btree_future<Cursor>
 174 Btree::erase(Cursor& first, Cursor& last) {
 175   // TODO
 176   return btree_ertr::make_ready_future<Cursor>(
 177       Cursor::make_end(this));
 178 }
 179
 180 btree_future<size_t> Btree::height(Transaction& t) {
 181   return get_root(t).safe_then([](auto root) {
 182     return size_t(root->level() + 1);
 183   });
 184 }
 185
 186 btree_future<tree_stats_t> Btree::get_stats_slow(Transaction& t) {
 187   return get_root(t).safe_then([this, &t](auto root) {
 188     unsigned height = root->level() + 1;
 189     return root->get_tree_stats(get_context(t)
 190     ).safe_then([height](auto stats) {
 191       stats.height = height;
 192       return btree_ertr::make_ready_future<tree_stats_t>(stats);
 193     });
 194   });
 195 }
 196
 197 std::ostream& Btree::dump(Transaction& t, std::ostream& os) {
 198   auto root = root_tracker->get_root(t);
 199   if (root) {
 200     root->dump(os);
 201   } else {
 202     os << "empty tree!";
 203   }
 204   return os;
 205 }
 206
 207 std::ostream& Btree::print(std::ostream& os) const {
 208   return os << "BTree-" << *nm;
 209 }
 210
 211 btree_future<Ref<Node>> Btree::get_root(Transaction& t) {
 212   auto root = root_tracker->get_root(t);
 213   if (root) {
 214     return btree_ertr::make_ready_future<Ref<Node>>(root);
 215   } else {
 216     return Node::load_root(get_context(t), *root_tracker);
 217   }
 218 }
 219
 220 bool Btree::test_is_clean() const {
 221   return root_tracker->is_clean();
 222 }
 223
 224 btree_future<> Btree::test_clone_from(
 225     Transaction& t, Transaction& t_from, Btree& from) {
 226   // Note: assume the tree to clone is tracked correctly in memory.
 227   // In some unit tests, parts of the tree are stubbed out that they
 228   // should not be loaded from NodeExtentManager.
 229   return from.get_root(t_from
 230   ).safe_then([this, &t](auto root_from) {
 231     return root_from->test_clone_root(get_context(t), *root_tracker);
 232   });
 233 }
 234
 235 }