X-Git-Url: https://git.proxmox.com/?a=blobdiff_plain;f=ceph%2Fsrc%2Fcrimson%2Fos%2Fseastore%2Frandom_block_manager%2Favlallocator.h;fp=ceph%2Fsrc%2Fcrimson%2Fos%2Fseastore%2Frandom_block_manager%2Favlallocator.h;h=d1a4fabca5a4c550316a058b33e41ed70575027f;hb=1e59de90020f1d8d374046ef9cca56ccd4e806e2;hp=0000000000000000000000000000000000000000;hpb=bd41e436e25044e8e83156060a37c23cb661c364;p=ceph.git

diff --git a/ceph/src/crimson/os/seastore/random_block_manager/avlallocator.h b/ceph/src/crimson/os/seastore/random_block_manager/avlallocator.h
new file mode 100644
index 000000000..d1a4fabca
--- /dev/null
+++ b/ceph/src/crimson/os/seastore/random_block_manager/avlallocator.h
@@ -0,0 +1,174 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
+// vim: ts=8 sw=2 smarttab expandtab
+
+#pragma once
+
+#include "extent_allocator.h"
+#include "include/ceph_assert.h"
+#include "include/buffer_fwd.h"
+#include "crimson/osd/exceptions.h"
+
+#include "crimson/os/seastore/transaction.h"
+#include <string.h>
+#include "include/buffer.h"
+
+#include <boost/intrusive/avl_set.hpp>
+#include <optional>
+#include <vector>
+
+namespace crimson::os::seastore {
+
+struct extent_range_t {
+  rbm_abs_addr start;
+  rbm_abs_addr end;
+
+  extent_range_t(rbm_abs_addr start, rbm_abs_addr end) :
+    start(start), end(end)
+  {}
+
+  struct before_t {
+    template<typename KeyLeft, typename KeyRight>
+    bool operator()(const KeyLeft& lhs, const KeyRight& rhs) const {
+      return lhs.end <= rhs.start;
+    }
+  };
+  boost::intrusive::avl_set_member_hook<> offset_hook;
+
+  struct shorter_t {
+    template<typename KeyType>
+    bool operator()(const extent_range_t& lhs, const KeyType& rhs) const {
+      auto lhs_size = lhs.length(); 
+      auto rhs_size = rhs.end - rhs.start;
+      if (lhs_size < rhs_size) {
+	return true;
+      } else if (lhs_size > rhs_size) {
+	return false;
+      } else {
+	return lhs.start < rhs.start;
+      }
+    }
+  };
+
+  size_t length() const {
+    return end - start;
+  }
+  boost::intrusive::avl_set_member_hook<> size_hook;
+};
+
+/*
+ * This is the simplest version of avlallocator from bluestore's avlallocator
+ */
+class AvlAllocator : public ExtentAllocator {
+public:
+  AvlAllocator(bool detailed) :
+    detailed(detailed) {}
+  std::optional<interval_set<rbm_abs_addr>> alloc_extent(
+    size_t size) final;
+
+  void free_extent(rbm_abs_addr addr, size_t size) final;
+  void mark_extent_used(rbm_abs_addr addr, size_t size) final;
+  void init(rbm_abs_addr addr, size_t size, size_t b_size);
+
+  struct dispose_rs {
+    void operator()(extent_range_t* p)
+    {
+      delete p;
+    }
+  };
+
+  ~AvlAllocator() {
+    close();
+  }
+
+  void close() {
+    if (!detailed) {
+      assert(reserved_extent_tracker.size() == 0);
+    }
+    extent_size_tree.clear();
+    extent_tree.clear_and_dispose(dispose_rs{});
+    total_size = 0;
+    block_size = 0;
+    available_size = 0;
+    base_addr = 0;
+  }
+
+  uint64_t get_available_size() const final {
+    return available_size;
+  }
+
+  uint64_t get_max_alloc_size() const final {
+    return max_alloc_size;
+  }
+
+  bool is_free_extent(rbm_abs_addr start, size_t size);
+
+  void complete_allocation(rbm_abs_addr start, size_t size) final {
+    if (detailed) {
+      assert(reserved_extent_tracker.contains(start, size));
+      reserved_extent_tracker.erase(start, size);
+    }
+  }
+
+  bool is_reserved_extent(rbm_abs_addr start, size_t size) {
+    if (detailed) {
+      return reserved_extent_tracker.contains(start, size);
+    } 
+    return false;
+  }
+
+  rbm_extent_state_t get_extent_state(rbm_abs_addr addr, size_t size) final {
+    if (is_reserved_extent(addr, size)) {
+      return rbm_extent_state_t::RESERVED;
+    } else if (is_free_extent(addr, size)) {
+      return rbm_extent_state_t::FREE;
+    }
+    return rbm_extent_state_t::ALLOCATED;
+  }
+
+private:
+  void _add_to_tree(rbm_abs_addr start, size_t size);
+
+  void _extent_size_tree_rm(extent_range_t& r) {
+    ceph_assert(available_size >= r.length());
+    available_size -= r.length();
+    extent_size_tree.erase(r);
+  }
+
+  void _extent_size_tree_try_insert(extent_range_t& r) {
+    extent_size_tree.insert(r);
+    available_size += r.length();
+  }
+
+  void _remove_from_tree(rbm_abs_addr start, rbm_abs_addr size);
+  rbm_abs_addr find_block(size_t size);
+
+  using extent_tree_t = 
+    boost::intrusive::avl_set<
+      extent_range_t,
+      boost::intrusive::compare<extent_range_t::before_t>,
+      boost::intrusive::member_hook<
+	extent_range_t,
+	boost::intrusive::avl_set_member_hook<>,
+	&extent_range_t::offset_hook>>;
+  extent_tree_t extent_tree;    
+
+  using extent_size_tree_t = 
+    boost::intrusive::avl_set<
+      extent_range_t,
+      boost::intrusive::compare<extent_range_t::shorter_t>,
+      boost::intrusive::member_hook<
+	extent_range_t,
+	boost::intrusive::avl_set_member_hook<>,
+	&extent_range_t::size_hook>>;
+  extent_size_tree_t extent_size_tree;
+
+  uint64_t block_size = 0;
+  uint64_t available_size = 0;
+  uint64_t total_size = 0;
+  uint64_t base_addr = 0;
+  uint64_t max_alloc_size = 4 << 20;
+  bool detailed;
+  interval_set<rbm_abs_addr> reserved_extent_tracker; 
+};
+
+}