From dce3e2f3f46d92c0a6a7f95e9e258ad6a2d95afd Mon Sep 17 00:00:00 2001
From: Igor Fedotov <ifedotov@suse.com>
Date: Thu, 25 Oct 2018 21:24:14 +0300
Subject: [PATCH] os/bluestore: optimize mapping offset to extent in BlueFS.

Signed-off-by: Igor Fedotov <ifedotov@suse.com>
---
 src/os/bluestore/BlueFS.cc       |  9 ++++-----
 src/os/bluestore/bluefs_types.cc | 12 ++++++++++++
 src/os/bluestore/bluefs_types.h  | 21 ++++++++++++++++-----
 3 files changed, 32 insertions(+), 10 deletions(-)

diff --git a/src/os/bluestore/BlueFS.cc b/src/os/bluestore/BlueFS.cc
index fd483431b7a..15201ee3dbd 100644
--- a/src/os/bluestore/BlueFS.cc
+++ b/src/os/bluestore/BlueFS.cc
@@ -1634,10 +1634,9 @@ void BlueFS::_rewrite_log_sync(bool allocate_with_fallback,
   uint64_t need = bl.length() + cct->_conf->bluefs_max_log_runway;
   dout(20) << __func__ << " need " << need << dendl;
 
-  mempool::bluefs::vector<bluefs_extent_t> old_extents;
-  uint64_t old_allocated = 0;
+  bluefs_fnode_t old_fnode;
   int r;
-  log_file->fnode.swap_extents(old_extents, old_allocated);
+  log_file->fnode.swap_extents(old_fnode);
   if (allocate_with_fallback) {
     r = _allocate(log_dev, need, &log_file->fnode);
     ceph_assert(r == 0);
@@ -1684,8 +1683,8 @@ void BlueFS::_rewrite_log_sync(bool allocate_with_fallback,
   _write_super(super_dev);
   flush_bdev();
 
-  dout(10) << __func__ << " release old log extents " << old_extents << dendl;
-  for (auto& r : old_extents) {
+  dout(10) << __func__ << " release old log extents " << old_fnode.extents << dendl;
+  for (auto& r : old_fnode.extents) {
     pending_release[r.bdev].insert(r.offset, r.length);
   }
 }
diff --git a/src/os/bluestore/bluefs_types.cc b/src/os/bluestore/bluefs_types.cc
index d1f5edf173c..aad2fc11ed9 100644
--- a/src/os/bluestore/bluefs_types.cc
+++ b/src/os/bluestore/bluefs_types.cc
@@ -1,6 +1,7 @@
 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
 // vim: ts=8 sw=2 smarttab
 
+#include <algorithm>
 #include "bluefs_types.h"
 #include "common/Formatter.h"
 #include "include/uuid.h"
@@ -86,6 +87,17 @@ mempool::bluefs::vector<bluefs_extent_t>::iterator bluefs_fnode_t::seek(
   uint64_t offset, uint64_t *x_off)
 {
   auto p = extents.begin();
+
+  if (extents_index.size() > 4) {
+    auto it = std::upper_bound(extents_index.begin(), extents_index.end(),
+      offset);
+    assert(it != extents_index.begin());
+    --it;
+    assert(offset >= *it);
+    p += it - extents_index.begin();
+    offset -= *it;
+  }
+
   while (p != extents.end()) {
     if ((int64_t) offset >= p->length) {
       offset -= p->length;
diff --git a/src/os/bluestore/bluefs_types.h b/src/os/bluestore/bluefs_types.h
index 43246f64195..dca0de61ca5 100644
--- a/src/os/bluestore/bluefs_types.h
+++ b/src/os/bluestore/bluefs_types.h
@@ -40,6 +40,11 @@ struct bluefs_fnode_t {
   utime_t mtime;
   uint8_t prefer_bdev;
   mempool::bluefs::vector<bluefs_extent_t> extents;
+
+  // precalculated logical offsets for extents vector entries
+  // allows fast lookup for extent index by the offset value via upper_bound()
+  mempool::bluefs::vector<uint64_t> extents_index;
+
   uint64_t allocated;
 
   bluefs_fnode_t() : ino(0), size(0), prefer_bdev(0), allocated(0) {}
@@ -50,8 +55,11 @@ struct bluefs_fnode_t {
 
   void recalc_allocated() {
     allocated = 0;
-    for (auto& p : extents)
+    extents_index.reserve(extents.size());
+    for (auto& p : extents) {
+      extents_index.emplace_back(allocated);
       allocated += p.length;
+    }
   }
 
   DENC_HELPERS
@@ -79,6 +87,7 @@ struct bluefs_fnode_t {
   }
 
   void append_extent(const bluefs_extent_t& ext) {
+    extents_index.emplace_back(allocated);
     extents.push_back(ext);
     allocated += ext.length;
   }
@@ -86,18 +95,20 @@ struct bluefs_fnode_t {
   void pop_front_extent() {
     auto it = extents.begin();
     allocated -= it->length;
+    extents_index.erase(extents_index.begin());
+    for (auto& i: extents_index) {
+      i -= it->length;
+    }
     extents.erase(it);
   }
   
   void swap_extents(bluefs_fnode_t& other) {
     other.extents.swap(extents);
+    other.extents_index.swap(extents_index);
     std::swap(allocated, other.allocated);
   }
-  void swap_extents(mempool::bluefs::vector<bluefs_extent_t>& swap_to, uint64_t& new_allocated) {
-    swap_to.swap(extents);
-    std::swap(allocated, new_allocated);
-  }
   void clear_extents() {
+    extents_index.clear();
     extents.clear();
     allocated = 0;
   }
-- 
2.39.5