rpc: improve get_output_distribution

It can now handle small reorgs without having to rescan the
whole blockchain.

Also add a test for it.

4 files changed, 34 insertions, 8 deletions

diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp
index c41fb37d8..20bfead28 100644
--- a/src/rpc/core_rpc_server.cpp
+++ b/src/rpc/core_rpc_server.cpp
@@ -2308,7 +2308,7 @@ namespace cryptonote
       const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1);
       for (uint64_t amount: req.amounts)
       {
-        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative);
+        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height());
         if (!data)
         {
           error_resp.code = CORE_RPC_ERROR_CODE_INTERNAL_ERROR;
@@ -2351,7 +2351,7 @@ namespace cryptonote
       const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1);
       for (uint64_t amount: req.amounts)
       {
-        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative);
+        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height());
         if (!data)
         {
           res.status = "Failed to get output distribution";
diff --git a/src/rpc/daemon_handler.cpp b/src/rpc/daemon_handler.cpp
index 7c8953930..f27c49ff8 100644
--- a/src/rpc/daemon_handler.cpp
+++ b/src/rpc/daemon_handler.cpp
@@ -778,7 +778,7 @@ namespace rpc
       const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1);
       for (std::uint64_t amount : req.amounts)
       {
-        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative);
+        auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height());
         if (!data)
         {
           res.distributions.clear();
diff --git a/src/rpc/rpc_handler.cpp b/src/rpc/rpc_handler.cpp
index e0a81c70f..af5cb98a3 100644
--- a/src/rpc/rpc_handler.cpp
+++ b/src/rpc/rpc_handler.cpp
@@ -26,26 +26,49 @@ namespace rpc
   }
 
   boost::optional<output_distribution_data>
-    RpcHandler::get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, bool cumulative)
+    RpcHandler::get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, const std::function<crypto::hash(uint64_t)> &get_hash, bool cumulative, uint64_t blockchain_height)
   {
       static struct D
       {
         boost::mutex mutex;
         std::vector<std::uint64_t> cached_distribution;
         std::uint64_t cached_from, cached_to, cached_start_height, cached_base;
+        crypto::hash cached_m10_hash;
+        crypto::hash cached_top_hash;
         bool cached;
-        D(): cached_from(0), cached_to(0), cached_start_height(0), cached_base(0), cached(false) {}
+        D(): cached_from(0), cached_to(0), cached_start_height(0), cached_base(0), cached_m10_hash(crypto::null_hash), cached_top_hash(crypto::null_hash), cached(false) {}
       } d;
       const boost::unique_lock<boost::mutex> lock(d.mutex);
 
-      if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to == to_height)
+      crypto::hash top_hash = crypto::null_hash;
+      if (d.cached_to < blockchain_height)
+        top_hash = get_hash(d.cached_to);
+      if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to == to_height && d.cached_top_hash == top_hash)
         return process_distribution(cumulative, d.cached_start_height, d.cached_distribution, d.cached_base);
 
       std::vector<std::uint64_t> distribution;
       std::uint64_t start_height, base;
 
       // see if we can extend the cache - a common case
-      if (d.cached && amount == 0 && d.cached_from == from_height && to_height > d.cached_to)
+      bool can_extend = d.cached && amount == 0 && d.cached_from == from_height && to_height > d.cached_to && top_hash == d.cached_top_hash;
+      if (!can_extend)
+      {
+        // we kept track of the hash 10 blocks below, if it exists, so if it matches,
+        // we can still pop the last 10 cached slots and try again
+        if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to - d.cached_from >= 10 && to_height > d.cached_to - 10)
+        {
+          crypto::hash hash10 = get_hash(d.cached_to - 10);
+          if (hash10 == d.cached_m10_hash)
+          {
+            d.cached_to -= 10;
+            d.cached_top_hash = hash10;
+            d.cached_m10_hash = crypto::null_hash;
+            d.cached_distribution.resize(d.cached_distribution.size() - 10);
+            can_extend = true;
+          }
+        }
+      }
+      if (can_extend)
       {
         std::vector<std::uint64_t> new_distribution;
         if (!f(amount, d.cached_to + 1, to_height, start_height, new_distribution, base))
@@ -74,6 +97,8 @@ namespace rpc
       {
         d.cached_from = from_height;
         d.cached_to = to_height;
+        d.cached_top_hash = get_hash(d.cached_to);
+        d.cached_m10_hash = d.cached_to >= 10 ? get_hash(d.cached_to - 10) : crypto::null_hash;
         d.cached_distribution = distribution;
         d.cached_start_height = start_height;
         d.cached_base = base;
diff --git a/src/rpc/rpc_handler.h b/src/rpc/rpc_handler.h
index 2439eaa58..b81983d28 100644
--- a/src/rpc/rpc_handler.h
+++ b/src/rpc/rpc_handler.h
@@ -32,6 +32,7 @@
 #include <cstdint>
 #include <string>
 #include <vector>
+#include "crypto/hash.h"
 
 namespace cryptonote
 {
@@ -56,7 +57,7 @@ class RpcHandler
     virtual std::string handle(const std::string& request) = 0;
 
     static boost::optional<output_distribution_data>
-      get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, bool cumulative);
+      get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, const std::function<crypto::hash(uint64_t)> &get_hash, bool cumulative, uint64_t blockchain_height);
 };