From 19fcec84d8d7d21e796c7624e521b60d28ee21ed Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Sun, 7 Apr 2024 20:45:59 +0200
Subject: Adding upstream version 16.2.11+ds.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 .../onode_manager/staged-fltree/tree_utils.h       | 333 +++++++++++++++++++++
 1 file changed, 333 insertions(+)
 create mode 100644 src/crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h

(limited to 'src/crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h')

diff --git a/src/crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h b/src/crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h
new file mode 100644
index 000000000..536052003
--- /dev/null
+++ b/src/crimson/os/seastore/onode_manager/staged-fltree/tree_utils.h
@@ -0,0 +1,333 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
+// vim: ts=8 sw=2 smarttab
+
+#pragma once
+
+#include <cassert>
+#include <cstring>
+#include <random>
+#include <string>
+#include <sstream>
+#include <utility>
+#include <vector>
+
+#include "crimson/common/log.h"
+#include "stages/key_layout.h"
+#include "tree.h"
+
+/**
+ * tree_utils.h
+ *
+ * Contains shared logic for unit tests and perf tool.
+ */
+
+namespace crimson::os::seastore::onode {
+
+class Onodes {
+ public:
+  Onodes(size_t n) {
+    for (size_t i = 1; i <= n; ++i) {
+      auto p_onode = &create(i * 8);
+      onodes.push_back(p_onode);
+    }
+  }
+
+  Onodes(std::vector<size_t> sizes) {
+    for (auto& size : sizes) {
+      auto p_onode = &create(size);
+      onodes.push_back(p_onode);
+    }
+  }
+
+  ~Onodes() = default;
+
+  const onode_t& create(size_t size) {
+    ceph_assert(size <= std::numeric_limits<uint16_t>::max());
+    onode_t config{static_cast<uint16_t>(size), id++};
+    auto onode = onode_t::allocate(config);
+    auto p_onode = onode.get();
+    tracked_onodes.push_back(std::move(onode));
+    return *reinterpret_cast<onode_t*>(p_onode);
+  }
+
+  const onode_t& pick() const {
+    auto index = rd() % onodes.size();
+    return *onodes[index];
+  }
+
+  const onode_t& pick_largest() const {
+    return *onodes[onodes.size() - 1];
+  }
+
+  static void validate_cursor(
+      const Btree::Cursor& cursor, const ghobject_t& key, const onode_t& onode) {
+    ceph_assert(!cursor.is_end());
+    ceph_assert(cursor.get_ghobj() == key);
+    ceph_assert(cursor.value());
+    ceph_assert(cursor.value() != &onode);
+    ceph_assert(*cursor.value() == onode);
+    onode_t::validate_tail_magic(*cursor.value());
+  }
+
+ private:
+  uint16_t id = 0;
+  mutable std::random_device rd;
+  std::vector<const onode_t*> onodes;
+  std::vector<std::unique_ptr<char[]>> tracked_onodes;
+};
+
+class KVPool {
+  struct kv_conf_t {
+    unsigned index2;
+    unsigned index1;
+    unsigned index0;
+    size_t ns_size;
+    size_t oid_size;
+    const onode_t* p_value;
+
+    ghobject_t get_ghobj() const {
+      assert(index1 < 10);
+      std::ostringstream os_ns;
+      os_ns << "ns" << index1;
+      unsigned current_size = (unsigned)os_ns.tellp();
+      assert(ns_size >= current_size);
+      os_ns << std::string(ns_size - current_size, '_');
+
+      std::ostringstream os_oid;
+      os_oid << "oid" << index1;
+      current_size = (unsigned)os_oid.tellp();
+      assert(oid_size >= current_size);
+      os_oid << std::string(oid_size - current_size, '_');
+
+      return ghobject_t(shard_id_t(index2), index2, index2,
+                        os_ns.str(), os_oid.str(), index0, index0);
+    }
+  };
+  using kv_vector_t = std::vector<kv_conf_t>;
+
+ public:
+  using kv_t = std::pair<ghobject_t, const onode_t*>;
+
+  KVPool(const std::vector<size_t>& str_sizes,
+         const std::vector<size_t>& onode_sizes,
+         const std::pair<unsigned, unsigned>& range2,
+         const std::pair<unsigned, unsigned>& range1,
+         const std::pair<unsigned, unsigned>& range0)
+      : str_sizes{str_sizes}, onodes{onode_sizes} {
+    ceph_assert(range2.first < range2.second);
+    ceph_assert(range2.second - 1 <= (unsigned)std::numeric_limits<shard_t>::max());
+    ceph_assert(range2.second - 1 <= std::numeric_limits<crush_hash_t>::max());
+    ceph_assert(range1.first < range1.second);
+    ceph_assert(range1.second - 1 <= 9);
+    ceph_assert(range0.first < range0.second);
+    std::random_device rd;
+    for (unsigned i = range2.first; i < range2.second; ++i) {
+      for (unsigned j = range1.first; j < range1.second; ++j) {
+        auto ns_size = (unsigned)str_sizes[rd() % str_sizes.size()];
+        auto oid_size = (unsigned)str_sizes[rd() % str_sizes.size()];
+        for (unsigned k = range0.first; k < range0.second; ++k) {
+          kvs.emplace_back(kv_conf_t{i, j, k, ns_size, oid_size, &onodes.pick()});
+        }
+      }
+    }
+    random_kvs = kvs;
+    std::random_shuffle(random_kvs.begin(), random_kvs.end());
+  }
+
+  class iterator_t {
+   public:
+    iterator_t() = default;
+    iterator_t(const iterator_t&) = default;
+    iterator_t(iterator_t&&) = default;
+    iterator_t& operator=(const iterator_t&) = default;
+    iterator_t& operator=(iterator_t&&) = default;
+
+    kv_t get_kv() const {
+      assert(!is_end());
+      auto& conf = (*p_kvs)[i];
+      return std::make_pair(conf.get_ghobj(), conf.p_value);
+    }
+    bool is_end() const { return !p_kvs || i >= p_kvs->size(); }
+    size_t index() const { return i; }
+
+    iterator_t& operator++() {
+      assert(!is_end());
+      ++i;
+      return *this;
+    }
+
+    iterator_t operator++(int) {
+      iterator_t tmp = *this;
+      ++*this;
+      return tmp;
+    }
+
+   private:
+    iterator_t(const kv_vector_t& kvs) : p_kvs{&kvs} {}
+
+    const kv_vector_t* p_kvs = nullptr;
+    size_t i = 0;
+    friend class KVPool;
+  };
+
+  iterator_t begin() const {
+    return iterator_t(kvs);
+  }
+
+  iterator_t random_begin() const {
+    return iterator_t(random_kvs);
+  }
+
+  size_t size() const {
+    return kvs.size();
+  }
+
+ private:
+  std::vector<size_t> str_sizes;
+  Onodes onodes;
+  kv_vector_t kvs;
+  kv_vector_t random_kvs;
+};
+
+template <bool TRACK>
+class TreeBuilder {
+ public:
+  using ertr = Btree::btree_ertr;
+  template <class ValueT=void>
+  using future = ertr::future<ValueT>;
+
+  TreeBuilder(KVPool& kvs, NodeExtentManagerURef&& nm)
+      : kvs{kvs} {
+    tree.emplace(std::move(nm));
+  }
+
+  future<> bootstrap(Transaction& t) {
+    std::ostringstream oss;
+#ifndef NDEBUG
+    oss << "debug=on, ";
+#else
+    oss << "debug=off, ";
+#endif
+#ifdef UNIT_TESTS_BUILT
+    oss << "UNIT_TEST_BUILT=on, ";
+#else
+    oss << "UNIT_TEST_BUILT=off, ";
+#endif
+    if constexpr (TRACK) {
+      oss << "track=on, ";
+    } else {
+      oss << "track=off, ";
+    }
+    oss << *tree;
+    logger().warn("TreeBuilder: {}, bootstrapping ...", oss.str());
+    return tree->mkfs(t);
+  }
+
+  future<> insert(Transaction& t) {
+    kv_iter = kvs.random_begin();
+    auto cursors = seastar::make_lw_shared<std::vector<Btree::Cursor>>();
+    logger().warn("start inserting {} kvs ...", kvs.size());
+    auto start_time = mono_clock::now();
+    return crimson::do_until([&t, this, cursors]() -> future<bool> {
+      if (kv_iter.is_end()) {
+        return ertr::make_ready_future<bool>(true);
+      }
+      auto [key, p_value] = kv_iter.get_kv();
+      logger().debug("[{}] {} -> {}", kv_iter.index(), key_hobj_t{key}, *p_value);
+      return tree->insert(t, key, *p_value
+      ).safe_then([&t, this, cursors](auto ret) {
+        auto& [cursor, success] = ret;
+        assert(success == true);
+        if constexpr (TRACK) {
+          cursors->emplace_back(cursor);
+        }
+#ifndef NDEBUG
+        auto [key, p_value] = kv_iter.get_kv();
+        Onodes::validate_cursor(cursor, key, *p_value);
+        return tree->lower_bound(t, key).safe_then([this, cursor](auto cursor_) {
+          auto [key, p_value] = kv_iter.get_kv();
+          ceph_assert(cursor_.get_ghobj() == key);
+          ceph_assert(cursor_.value() == cursor.value());
+          ++kv_iter;
+          return ertr::make_ready_future<bool>(false);
+        });
+#else
+        ++kv_iter;
+        return ertr::make_ready_future<bool>(false);
+#endif
+      });
+    }).safe_then([&t, this, start_time, cursors] {
+      std::chrono::duration<double> duration = mono_clock::now() - start_time;
+      logger().warn("Insert done! {}s", duration.count());
+      if (!cursors->empty()) {
+        logger().info("Verifing tracked cursors ...");
+        kv_iter = kvs.random_begin();
+        return seastar::do_with(
+            cursors->begin(), [&t, this, cursors](auto& c_iter) {
+          return crimson::do_until([&t, this, &c_iter, cursors]() -> future<bool> {
+            if (kv_iter.is_end()) {
+              logger().info("Verify done!");
+              return ertr::make_ready_future<bool>(true);
+            }
+            assert(c_iter != cursors->end());
+            auto [k, v] = kv_iter.get_kv();
+            // validate values in tree keep intact
+            return tree->lower_bound(t, k).safe_then([this, &c_iter](auto cursor) {
+              auto [k, v] = kv_iter.get_kv();
+              Onodes::validate_cursor(cursor, k, *v);
+              // validate values in cursors keep intact
+              Onodes::validate_cursor(*c_iter, k, *v);
+              ++kv_iter;
+              ++c_iter;
+              return ertr::make_ready_future<bool>(false);
+            });
+          });
+        });
+      } else {
+        return ertr::now();
+      }
+    });
+  }
+
+  future<> get_stats(Transaction& t) {
+    return tree->get_stats_slow(t
+    ).safe_then([this](auto stats) {
+      logger().warn("{}", stats);
+    });
+  }
+
+  void reload(NodeExtentManagerURef&& nm) {
+    tree.emplace(std::move(nm));
+  }
+
+  future<> validate(Transaction& t) {
+    logger().info("Verifing insertion ...");
+    return seastar::do_with(
+        kvs.begin(), [&t, this] (auto& kvs_iter) {
+      return crimson::do_until([&t, this, &kvs_iter]() -> future<bool> {
+        if (kvs_iter.is_end()) {
+          logger().info("Verify done!");
+          return ertr::make_ready_future<bool>(true);
+        }
+        auto [k, v] = kvs_iter.get_kv();
+        return tree->lower_bound(t, k
+        ).safe_then([&kvs_iter, k=k, v=v] (auto cursor) {
+          Onodes::validate_cursor(cursor, k, *v);
+          ++kvs_iter;
+          return ertr::make_ready_future<bool>(false);
+        });
+      });
+    });
+  }
+
+ private:
+  static seastar::logger& logger() {
+    return crimson::get_logger(ceph_subsys_filestore);
+  }
+
+  KVPool& kvs;
+  std::optional<Btree> tree;
+  KVPool::iterator_t kv_iter;
+};
+
+}
-- 
cgit v1.2.3