diff options
30 files changed, 1031 insertions, 93 deletions
diff --git a/contrib/depends/Makefile b/contrib/depends/Makefile index afa61b93b..6ab602ac0 100644 --- a/contrib/depends/Makefile +++ b/contrib/depends/Makefile @@ -22,9 +22,16 @@ host_toolchain:=$(HOST)- endif ifneq ($(DEBUG),) -release_type=debug +release_type=Debug else -release_type=release +release_type=Release +endif + +ifneq ($(TESTS),) +build_tests=ON +release_type=Debug +else +build_tests=OFF endif base_build_dir=$(BASEDIR)/work/build @@ -164,6 +171,8 @@ $(host_prefix)/share/toolchain.cmake : toolchain.cmake.in $(host_prefix)/.stamp_ -e 's|@LDFLAGS@|$(strip $(host_LDFLAGS) $(host_$(release_type)_LDFLAGS))|' \ -e 's|@allow_host_packages@|$(ALLOW_HOST_PACKAGES)|' \ -e 's|@debug@|$(DEBUG)|' \ + -e 's|@release_type@|$(release_type)|' \ + -e 's|@build_tests@|$(build_tests)|' \ -e 's|@depends@|$(host_cmake)|' \ -e 's|@prefix@|$($(host_arch)_$(host_os)_prefix)|'\ -e 's|@sdk@|$(SDK_PATH)|'\ diff --git a/contrib/depends/packages/gtest.mk b/contrib/depends/packages/gtest.mk new file mode 100644 index 000000000..5df07a32e --- /dev/null +++ b/contrib/depends/packages/gtest.mk @@ -0,0 +1,38 @@ +package=gtest +$(package)_version=1.8.1 +$(package)_download_path=https://github.com/google/googletest/archive/ +$(package)_file_name=release-$($(package)_version).tar.gz +$(package)_sha256_hash=9bf1fe5182a604b4135edc1a425ae356c9ad15e9b23f9f12a02e80184c3a249c +$(package)_cxxflags=-std=c++11 +$(package)_cxxflags_linux=-fPIC + +define $(package)_config_cmds + cd googletest && \ + CC="$(host_prefix)/native/bin/$($(package)_cc)" \ + CXX="$(host_prefix)/native/bin/$($(package)_cxx)" \ + AR="$(host_prefix)/native/bin/$($(package)_ar)" \ + RANLIB="$(host_prefix)/native/bin/$($(package)_ranlib)" \ + LIBTOOL="$(host_prefix)/native/bin/$($(package)_libtool)" \ + CXXFLAGS="$($(package)_cxxflags)" \ + CCFLAGS="$($(package)_ccflags)" \ + CPPFLAGS="$($(package)_cppflags)" \ + CFLAGS="$($(package)_cflags) $($(package)_cppflags)" \ + LDLAGS="$($(package)_ldflags)" \ + cmake -DCMAKE_INSTALL_PREFIX=$(build_prefix) \ + -DTOOLCHAIN_PREFIX=$(host_toolchain) \ + -DCMAKE_AR="$(host_prefix)/native/bin/$($(package)_ar)" \ + -DCMAKE_RANLIB="$(host_prefix)/native/bin/$($(package)_ranlib)" \ + -DCMAKE_CXX_FLAGS_DEBUG=ON +endef +# -DCMAKE_TOOLCHAIN_FILE=$(HOST)/share/toolchain.cmake + +define $(package)_build_cmds + cd googletest && CC="$(host_prefix)/native/bin/$($(package)_cc)" $(MAKE) +endef + +define $(package)_stage_cmds + mkdir $($(package)_staging_prefix_dir)/lib $($(package)_staging_prefix_dir)/include &&\ + cp googletest/libgtest.a $($(package)_staging_prefix_dir)/lib/ &&\ + cp googletest/libgtest_main.a $($(package)_staging_prefix_dir)/lib/ &&\ + cp -a googletest/include/* $($(package)_staging_prefix_dir)/include/ +endef diff --git a/contrib/depends/packages/native_cctools.mk b/contrib/depends/packages/native_cctools.mk index 44d238cc4..bcfe1af6b 100644 --- a/contrib/depends/packages/native_cctools.mk +++ b/contrib/depends/packages/native_cctools.mk @@ -52,6 +52,7 @@ endef define $(package)_stage_cmds $(MAKE) DESTDIR=$($(package)_staging_dir) install && \ + cp $($(package)_extract_dir)/cctools/misc/install_name_tool $($(package)_staging_prefix_dir)/bin/ &&\ cd $($(package)_extract_dir)/toolchain && \ mkdir -p $($(package)_staging_prefix_dir)/lib/clang/$($(package)_clang_version)/include && \ mkdir -p $($(package)_staging_prefix_dir)/bin $($(package)_staging_prefix_dir)/include && \ diff --git a/contrib/depends/packages/native_cmake-unused.mk b/contrib/depends/packages/native_cmake-unused.mk new file mode 100644 index 000000000..c9ab75711 --- /dev/null +++ b/contrib/depends/packages/native_cmake-unused.mk @@ -0,0 +1,23 @@ +package=native_cmake +$(package)_version=3.14.0 +$(package)_version_dot=v3.14 +$(package)_download_path=https://cmake.org/files/$($(package)_version_dot)/ +$(package)_file_name=cmake-$($(package)_version).tar.gz +$(package)_sha256_hash=aa76ba67b3c2af1946701f847073f4652af5cbd9f141f221c97af99127e75502 + +define $(package)_set_vars +$(package)_config_opts= +endef + +define $(package)_config_cmds + ./bootstrap &&\ + ./configure $($(package)_config_opts) +endef + +define $(package)_build_cmd + $(MAKE) +endef + +define $(package)_stage_cmds + $(MAKE) DESTDIR=$($(package)_staging_dir) install +endef diff --git a/contrib/depends/packages/packages.mk b/contrib/depends/packages/packages.mk index 1db50580b..a38819337 100644 --- a/contrib/depends/packages/packages.mk +++ b/contrib/depends/packages/packages.mk @@ -7,6 +7,10 @@ darwin_packages = sodium-darwin linux_packages = eudev qt_packages = qt +ifeq ($(build_tests),ON) +packages += gtest +endif + ifeq ($(host_os),linux) packages += unwind packages += sodium diff --git a/contrib/depends/toolchain.cmake.in b/contrib/depends/toolchain.cmake.in index b0af7bd6b..6b5434751 100644 --- a/contrib/depends/toolchain.cmake.in +++ b/contrib/depends/toolchain.cmake.in @@ -1,9 +1,16 @@ # Set the system name, either Darwin, Linux, or Windows SET(CMAKE_SYSTEM_NAME @depends@) -SET(CMAKE_BUILD_TYPE release) +SET(CMAKE_BUILD_TYPE @release_type@) -SET(STATIC true) -SET(UNBOUND_STATIC true) +OPTION(STATIC "Link libraries statically" ON) +OPTION(TREZOR_DEBUG "Main trezor debugging switch" OFF) +OPTION(BUILD_TESTS "Build tests." OFF) + +SET(STATIC ON) +SET(UNBOUND_STATIC ON) + +SET(BUILD_TESTS @build_tests@) +SET(TREZOR_DEBUG @build_tests@) # where is the target environment SET(CMAKE_FIND_ROOT_PATH @prefix@ /usr) diff --git a/contrib/epee/include/net/net_ssl.h b/contrib/epee/include/net/net_ssl.h index 957903ff8..5ef2ff59d 100644 --- a/contrib/epee/include/net/net_ssl.h +++ b/contrib/epee/include/net/net_ssl.h @@ -37,6 +37,8 @@ #include <boost/asio/ssl.hpp> #include <boost/system/error_code.hpp> +#define SSL_FINGERPRINT_SIZE 32 + namespace epee { namespace net_utils diff --git a/contrib/epee/include/rolling_median.h b/contrib/epee/include/rolling_median.h new file mode 100644 index 000000000..8b5a82a84 --- /dev/null +++ b/contrib/epee/include/rolling_median.h @@ -0,0 +1,236 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Adapted from source by AShelly: +// Copyright (c) 2011 ashelly.myopenid.com, licenced under the MIT licence +// https://stackoverflow.com/questions/5527437/rolling-median-in-c-turlach-implementation +// https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c +// https://ideone.com/XPbl6 + +#pragma once + +#include <stdlib.h> +#include <stdint.h> + +namespace epee +{ +namespace misc_utils +{ + +template<typename Item> +struct rolling_median_t +{ +private: + Item* data; //circular queue of values + int* pos; //index into `heap` for each value + int* heap; //max/median/min heap holding indexes into `data`. + int N; //allocated size. + int idx; //position in circular queue + int minCt; //count of items in min heap + int maxCt; //count of items in max heap + int sz; //count of items in heap + +private: + + //returns true if heap[i] < heap[j] + bool mmless(int i, int j) const + { + return data[heap[i]] < data[heap[j]]; + } + + //swaps items i&j in heap, maintains indexes + bool mmexchange(int i, int j) + { + const int t = heap[i]; + heap[i] = heap[j]; + heap[j] = t; + pos[heap[i]] = i; + pos[heap[j]] = j; + return 1; + } + + //swaps items i&j if i<j; returns true if swapped + bool mmCmpExch(int i, int j) + { + return mmless(i, j) && mmexchange(i, j); + } + + //maintains minheap property for all items below i. + void minSortDown(int i) + { + for (i *= 2; i <= minCt; i *= 2) + { + if (i < minCt && mmless(i + 1, i)) + ++i; + if (!mmCmpExch(i, i / 2)) + break; + } + } + + //maintains maxheap property for all items below i. (negative indexes) + void maxSortDown(int i) + { + for (i *= 2; i >= -maxCt; i *= 2) + { + if (i > -maxCt && mmless(i, i - 1)) + --i; + if (!mmCmpExch(i / 2, i)) + break; + } + } + + //maintains minheap property for all items above i, including median + //returns true if median changed + bool minSortUp(int i) + { + while (i > 0 && mmCmpExch(i, i / 2)) + i /= 2; + return i == 0; + } + + //maintains maxheap property for all items above i, including median + //returns true if median changed + bool maxSortUp(int i) + { + while (i < 0 && mmCmpExch(i / 2, i)) + i /= 2; + return i == 0; + } + +protected: + rolling_median_t &operator=(const rolling_median_t&) = delete; + rolling_median_t(const rolling_median_t&) = delete; + +public: + //creates new rolling_median_t: to calculate `nItems` running median. + rolling_median_t(size_t N): N(N) + { + int size = N * (sizeof(Item) + sizeof(int) * 2); + data = (Item*)malloc(size); + pos = (int*) (data + N); + heap = pos + N + (N / 2); //points to middle of storage. + clear(); + } + + rolling_median_t(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + } + rolling_median_t &operator=(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + return *this; + } + + ~rolling_median_t() + { + free(data); + } + + void clear() + { + idx = 0; + minCt = 0; + maxCt = 0; + sz = 0; + int nItems = N; + while (nItems--) //set up initial heap fill pattern: median,max,min,max,... + { + pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1); + heap[pos[nItems]] = nItems; + } + } + + int size() const + { + return sz; + } + + //Inserts item, maintains median in O(lg nItems) + void insert(Item v) + { + int p = pos[idx]; + Item old = data[idx]; + data[idx] = v; + idx = (idx + 1) % N; + sz = std::min<int>(sz + 1, N); + if (p > 0) //new item is in minHeap + { + if (minCt < (N - 1) / 2) + { + ++minCt; + } + else if (v > old) + { + minSortDown(p); + return; + } + if (minSortUp(p) && mmCmpExch(0, -1)) + maxSortDown(-1); + } + else if (p < 0) //new item is in maxheap + { + if (maxCt < N / 2) + { + ++maxCt; + } + else if (v < old) + { + maxSortDown(p); + return; + } + if (maxSortUp(p) && minCt && mmCmpExch(1, 0)) + minSortDown(1); + } + else //new item is at median + { + if (maxCt && maxSortUp(-1)) + maxSortDown(-1); + if (minCt && minSortUp(1)) + minSortDown(1); + } + } + + //returns median item (or average of 2 when item count is even) + Item median() const + { + Item v = data[heap[0]]; + if (minCt < maxCt) + { + v = (v + data[heap[-1]]) / 2; + } + return v; + } +}; + +} +} diff --git a/contrib/epee/src/net_ssl.cpp b/contrib/epee/src/net_ssl.cpp index 7bedb18ac..c17d86eca 100644 --- a/contrib/epee/src/net_ssl.cpp +++ b/contrib/epee/src/net_ssl.cpp @@ -321,7 +321,7 @@ bool ssl_options_t::has_fingerprint(boost::asio::ssl::verify_context &ctx) const unsigned int size{ 0 }; // create the digest from the certificate - if (!X509_digest(cert, EVP_sha1(), digest.data(), &size)) { + if (!X509_digest(cert, EVP_sha256(), digest.data(), &size)) { MERROR("Failed to create certificate fingerprint"); return false; } diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp index f733efb2f..32e94ad09 100644 --- a/src/cryptonote_core/blockchain.cpp +++ b/src/cryptonote_core/blockchain.cpp @@ -179,6 +179,7 @@ Blockchain::Blockchain(tx_memory_pool& tx_pool) : m_long_term_block_weights_window(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_long_term_effective_median_block_weight(0), m_long_term_block_weights_cache_tip_hash(crypto::null_hash), + m_long_term_block_weights_cache_rolling_median(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_difficulty_for_next_block_top_hash(crypto::null_hash), m_difficulty_for_next_block(1), m_btc_valid(false) @@ -519,7 +520,10 @@ bool Blockchain::init(BlockchainDB* db, const network_type nettype, bool offline } if (test_options && test_options->long_term_block_weight_window) + { m_long_term_block_weights_window = test_options->long_term_block_weight_window; + m_long_term_block_weights_cache_rolling_median = epee::misc_utils::rolling_median_t<uint64_t>(m_long_term_block_weights_window); + } { db_txn_guard txn_guard(m_db, m_db->is_read_only()); @@ -1283,21 +1287,20 @@ void Blockchain::get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_ weights = m_db->get_block_weights(start_offset, count); } //------------------------------------------------------------------ -void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const +uint64_t Blockchain::get_long_term_block_weight_median(uint64_t start_height, size_t count) const { LOG_PRINT_L3("Blockchain::" << __func__); CRITICAL_REGION_LOCAL(m_blockchain_lock); PERF_TIMER(get_long_term_block_weights); - if (count == 0) - return; + CHECK_AND_ASSERT_THROW_MES(count > 0, "count == 0"); bool cached = false; uint64_t blockchain_height = m_db->height(); uint64_t tip_height = start_height + count - 1; crypto::hash tip_hash = crypto::null_hash; - if (tip_height < blockchain_height && count == m_long_term_block_weights_cache.size()) + if (tip_height < blockchain_height && count == (size_t)m_long_term_block_weights_cache_rolling_median.size()) { tip_hash = m_db->get_block_hash_from_height(tip_height); cached = tip_hash == m_long_term_block_weights_cache_tip_hash; @@ -1306,32 +1309,30 @@ void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uin if (cached) { MTRACE("requesting " << count << " from " << start_height << ", cached"); - weights = m_long_term_block_weights_cache; - return; + return m_long_term_block_weights_cache_rolling_median.median(); } // in the vast majority of uncached cases, most is still cached, // as we just move the window one block up: - if (tip_height > 0 && count == m_long_term_block_weights_cache.size() && tip_height < blockchain_height) + if (tip_height > 0 && count == (size_t)m_long_term_block_weights_cache_rolling_median.size() && tip_height < blockchain_height) { crypto::hash old_tip_hash = m_db->get_block_hash_from_height(tip_height - 1); if (old_tip_hash == m_long_term_block_weights_cache_tip_hash) { - weights = m_long_term_block_weights_cache; - for (size_t i = 1; i < weights.size(); ++i) - weights[i - 1] = weights[i]; MTRACE("requesting " << count << " from " << start_height << ", incremental"); - weights.back() = m_db->get_block_long_term_weight(tip_height); - m_long_term_block_weights_cache = weights; m_long_term_block_weights_cache_tip_hash = tip_hash; - return; + m_long_term_block_weights_cache_rolling_median.insert(m_db->get_block_long_term_weight(tip_height)); + return m_long_term_block_weights_cache_rolling_median.median(); } } MTRACE("requesting " << count << " from " << start_height << ", uncached"); - weights = m_db->get_long_term_block_weights(start_height, count); - m_long_term_block_weights_cache = weights; + std::vector<uint64_t> weights = m_db->get_long_term_block_weights(start_height, count); m_long_term_block_weights_cache_tip_hash = tip_hash; + m_long_term_block_weights_cache_rolling_median.clear(); + for (uint64_t w: weights) + m_long_term_block_weights_cache_rolling_median.insert(w); + return m_long_term_block_weights_cache_rolling_median.median(); } //------------------------------------------------------------------ uint64_t Blockchain::get_current_cumulative_block_weight_limit() const @@ -3934,9 +3935,7 @@ uint64_t Blockchain::get_next_long_term_block_weight(uint64_t block_weight) cons if (hf_version < HF_VERSION_LONG_TERM_BLOCK_WEIGHT) return block_weight; - std::vector<uint64_t> weights; - get_long_term_block_weights(weights, db_height - nblocks, nblocks); - uint64_t long_term_median = epee::misc_utils::median(weights); + uint64_t long_term_median = get_long_term_block_weight_median(db_height - nblocks, nblocks); uint64_t long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); uint64_t short_term_constraint = long_term_effective_median_block_weight + long_term_effective_median_block_weight * 2 / 5; @@ -3968,7 +3967,6 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti { const uint64_t block_weight = m_db->get_block_weight(db_height - 1); - std::vector<uint64_t> weights, new_weights; uint64_t long_term_median; if (db_height == 1) { @@ -3979,9 +3977,7 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t nblocks = std::min<uint64_t>(m_long_term_block_weights_window, db_height); if (nblocks == db_height) --nblocks; - get_long_term_block_weights(weights, db_height - nblocks - 1, nblocks); - new_weights = weights; - long_term_median = epee::misc_utils::median(weights); + long_term_median = get_long_term_block_weight_median(db_height - nblocks - 1, nblocks); } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); @@ -3989,13 +3985,19 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t short_term_constraint = m_long_term_effective_median_block_weight + m_long_term_effective_median_block_weight * 2 / 5; long_term_block_weight = std::min<uint64_t>(block_weight, short_term_constraint); - if (new_weights.empty()) - new_weights.resize(1); - new_weights[0] = long_term_block_weight; - long_term_median = epee::misc_utils::median(new_weights); + if (db_height == 1) + { + long_term_median = long_term_block_weight; + } + else + { + m_long_term_block_weights_cache_tip_hash = m_db->get_block_hash_from_height(db_height - 1); + m_long_term_block_weights_cache_rolling_median.insert(long_term_block_weight); + long_term_median = m_long_term_block_weights_cache_rolling_median.median(); + } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); - weights.clear(); + std::vector<uint64_t> weights; get_last_n_blocks_weights(weights, CRYPTONOTE_REWARD_BLOCKS_WINDOW); uint64_t short_term_median = epee::misc_utils::median(weights); diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h index 244e2a89a..6200ec87e 100644 --- a/src/cryptonote_core/blockchain.h +++ b/src/cryptonote_core/blockchain.h @@ -37,7 +37,6 @@ #include <boost/multi_index/global_fun.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> -#include <boost/circular_buffer.hpp> #include <atomic> #include <functional> #include <unordered_map> @@ -46,6 +45,7 @@ #include "span.h" #include "syncobj.h" #include "string_tools.h" +#include "rolling_median.h" #include "cryptonote_basic/cryptonote_basic.h" #include "common/util.h" #include "cryptonote_protocol/cryptonote_protocol_defs.h" @@ -1064,7 +1064,7 @@ namespace cryptonote uint64_t m_long_term_block_weights_window; uint64_t m_long_term_effective_median_block_weight; mutable crypto::hash m_long_term_block_weights_cache_tip_hash; - mutable std::vector<uint64_t> m_long_term_block_weights_cache; + mutable epee::misc_utils::rolling_median_t<uint64_t> m_long_term_block_weights_cache_rolling_median; epee::critical_section m_difficulty_lock; crypto::hash m_difficulty_for_next_block_top_hash; @@ -1314,15 +1314,16 @@ namespace cryptonote void get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_t count) const; /** - * @brief gets recent block long term weights for median calculation + * @brief gets block long term weight median * - * get the block long term weights of the last <count> blocks, and return by reference <weights>. + * get the block long term weight median of <count> blocks starting at <start_height> * - * @param weights return-by-reference the list of weights * @param start_height the block height of the first block to query * @param count the number of blocks to get weights for + * + * @return the long term median block weight */ - void get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const; + uint64_t get_long_term_block_weight_median(uint64_t start_height, size_t count) const; /** * @brief checks if a transaction is unlocked (its outputs spendable) diff --git a/src/daemon/rpc_command_executor.cpp b/src/daemon/rpc_command_executor.cpp index 186296dc9..151baa33f 100644 --- a/src/daemon/rpc_command_executor.cpp +++ b/src/daemon/rpc_command_executor.cpp @@ -722,7 +722,7 @@ bool t_rpc_command_executor::print_blockchain_info(uint64_t start_block_index, u tools::msg_writer() << "" << std::endl; tools::msg_writer() << "height: " << header.height << ", timestamp: " << header.timestamp << " (" << tools::get_human_readable_timestamp(header.timestamp) << ")" - << ", size: " << header.block_size << ", weight: " << header.block_weight << ", transactions: " << header.num_txes << std::endl + << ", size: " << header.block_size << ", weight: " << header.block_weight << " (long term " << header.long_term_weight << "), transactions: " << header.num_txes << std::endl << "major version: " << (unsigned)header.major_version << ", minor version: " << (unsigned)header.minor_version << std::endl << "block id: " << header.hash << ", previous block id: " << header.prev_hash << std::endl << "difficulty: " << header.difficulty << ", nonce " << header.nonce << ", reward " << cryptonote::print_money(header.reward) << std::endl; diff --git a/src/device_trezor/device_trezor_base.cpp b/src/device_trezor/device_trezor_base.cpp index 5adadbfc4..b7adf433d 100644 --- a/src/device_trezor/device_trezor_base.cpp +++ b/src/device_trezor/device_trezor_base.cpp @@ -115,10 +115,14 @@ namespace trezor { MDEBUG("Enumerating Trezor devices..."); enumerate(trans); + sort_transports_by_env(trans); - MDEBUG("Enumeration yielded " << trans.size() << " devices"); + MDEBUG("Enumeration yielded " << trans.size() << " Trezor devices"); for (auto &cur : trans) { MDEBUG(" device: " << *(cur.get())); + } + + for (auto &cur : trans) { std::string cur_path = cur->get_path(); if (boost::starts_with(cur_path, this->name)) { MDEBUG("Device Match: " << cur_path); diff --git a/src/device_trezor/trezor/transport.cpp b/src/device_trezor/trezor/transport.cpp index dd9b0b52f..59b281f13 100644 --- a/src/device_trezor/trezor/transport.cpp +++ b/src/device_trezor/trezor/transport.cpp @@ -31,11 +31,13 @@ #include <libusb.h> #endif +#include <algorithm> #include <boost/endian/conversion.hpp> #include <boost/asio/io_service.hpp> #include <boost/asio/ip/udp.hpp> #include <boost/date_time/posix_time/posix_time_types.hpp> #include <boost/format.hpp> +#include "common/apply_permutation.h" #include "transport.hpp" #include "messages/messages-common.pb.h" @@ -95,6 +97,47 @@ namespace trezor{ return patch | (((uint64_t)minor) << bits_2) | (((uint64_t)major) << (bits_1 + bits_2)); } + typedef struct { + uint16_t trezor_type; + uint16_t id_vendor; + uint16_t id_product; + } trezor_usb_desc_t; + + static trezor_usb_desc_t TREZOR_DESC_T1 = {1, 0x534C, 0x0001}; + static trezor_usb_desc_t TREZOR_DESC_T2 = {2, 0x1209, 0x53C1}; + static trezor_usb_desc_t TREZOR_DESC_T2_BL = {3, 0x1209, 0x53C0}; + + static trezor_usb_desc_t TREZOR_DESCS[] = { + TREZOR_DESC_T1, + TREZOR_DESC_T2, + TREZOR_DESC_T2_BL, + }; + + static size_t TREZOR_DESCS_LEN = sizeof(TREZOR_DESCS)/sizeof(TREZOR_DESCS[0]); + + static ssize_t get_device_idx(uint16_t id_vendor, uint16_t id_product){ + for(size_t i = 0; i < TREZOR_DESCS_LEN; ++i){ + if (TREZOR_DESCS[i].id_vendor == id_vendor && TREZOR_DESCS[i].id_product == id_product){ + return i; + } + } + + return -1; + } + + static bool is_device_supported(ssize_t device_idx){ + CHECK_AND_ASSERT_THROW_MES(device_idx < (ssize_t)TREZOR_DESCS_LEN, "Device desc idx too big"); + if (device_idx < 0){ + return false; + } + +#ifdef TREZOR_1_SUPPORTED + return true; +#else + return TREZOR_DESCS[device_idx].trezor_type != 1; +#endif + } + // // Helpers // @@ -312,6 +355,24 @@ namespace trezor{ for(rapidjson::Value::ConstValueIterator itr = bridge_res.Begin(); itr != bridge_res.End(); ++itr){ auto element = itr->GetObject(); auto t = std::make_shared<BridgeTransport>(boost::make_optional(json_get_string(element["path"]))); + + auto itr_vendor = element.FindMember("vendor"); + auto itr_product = element.FindMember("product"); + if (itr_vendor != element.MemberEnd() && itr_product != element.MemberEnd() + && itr_vendor->value.IsNumber() && itr_product->value.IsNumber()){ + try { + const auto id_vendor = (uint16_t) itr_vendor->value.GetUint64(); + const auto id_product = (uint16_t) itr_product->value.GetUint64(); + const auto device_idx = get_device_idx(id_vendor, id_product); + if (!is_device_supported(device_idx)){ + MDEBUG("Device with idx " << device_idx << " is not supported. Vendor: " << id_vendor << ", product: " << id_product); + continue; + } + } catch(const std::exception &e){ + MERROR("Could not detect vendor & product: " << e.what()); + } + } + t->m_device_info.emplace(); t->m_device_info->CopyFrom(*itr, t->m_device_info->GetAllocator()); res.push_back(t); @@ -710,24 +771,20 @@ namespace trezor{ #ifdef WITH_DEVICE_TREZOR_WEBUSB static bool is_trezor1(libusb_device_descriptor * info){ - return info->idVendor == 0x534C && info->idProduct == 0x0001; + return info->idVendor == TREZOR_DESC_T1.id_vendor && info->idProduct == TREZOR_DESC_T1.id_product; } static bool is_trezor2(libusb_device_descriptor * info){ - return info->idVendor == 0x1209 && info->idProduct == 0x53C1; + return info->idVendor == TREZOR_DESC_T2.id_vendor && info->idProduct == TREZOR_DESC_T2.id_product; } static bool is_trezor2_bl(libusb_device_descriptor * info){ - return info->idVendor == 0x1209 && info->idProduct == 0x53C0; + return info->idVendor == TREZOR_DESC_T2_BL.id_vendor && info->idProduct == TREZOR_DESC_T2_BL.id_product; } - static uint8_t get_trezor_dev_mask(libusb_device_descriptor * info){ - uint8_t mask = 0; + static ssize_t get_trezor_dev_id(libusb_device_descriptor *info){ CHECK_AND_ASSERT_THROW_MES(info, "Empty device descriptor"); - mask |= is_trezor1(info) ? 1 : 0; - mask |= is_trezor2(info) ? 2 : 0; - mask |= is_trezor2_bl(info) ? 4 : 0; - return mask; + return get_device_idx(info->idVendor, info->idProduct); } static void set_libusb_log(libusb_context *ctx){ @@ -844,12 +901,12 @@ namespace trezor{ continue; } - const auto trezor_mask = get_trezor_dev_mask(&desc); - if (!trezor_mask){ + const auto trezor_dev_idx = get_trezor_dev_id(&desc); + if (!is_device_supported(trezor_dev_idx)){ continue; } - MTRACE("Found Trezor device: " << desc.idVendor << ":" << desc.idProduct << " mask " << (int)trezor_mask); + MTRACE("Found Trezor device: " << desc.idVendor << ":" << desc.idProduct << " dev_idx " << (int)trezor_dev_idx); auto t = std::make_shared<WebUsbTransport>(boost::make_optional(&desc)); t->m_bus_id = libusb_get_bus_number(devs[i]); @@ -909,8 +966,8 @@ namespace trezor{ continue; } - const auto trezor_mask = get_trezor_dev_mask(&desc); - if (!trezor_mask) { + const auto trezor_dev_idx = get_trezor_dev_id(&desc); + if (!is_device_supported(trezor_dev_idx)){ continue; } @@ -921,7 +978,7 @@ namespace trezor{ get_libusb_ports(devs[i], path); MTRACE("Found Trezor device: " << desc.idVendor << ":" << desc.idProduct - << ", mask: " << (int)trezor_mask + << ", dev_idx: " << (int)trezor_dev_idx << ". path: " << get_usb_path(bus_id, path)); if (bus_id == m_bus_id && path == m_port_numbers) { @@ -1110,6 +1167,39 @@ namespace trezor{ #endif } + void sort_transports_by_env(t_transport_vect & res){ + const char *env_trezor_path = getenv("TREZOR_PATH"); + if (!env_trezor_path){ + return; + } + + // Sort transports by the longest matching prefix with TREZOR_PATH + std::string trezor_path(env_trezor_path); + std::vector<size_t> match_idx(res.size()); + std::vector<size_t> path_permutation(res.size()); + + for(size_t i = 0; i < res.size(); ++i){ + auto cpath = res[i]->get_path(); + std::string * s1 = &trezor_path; + std::string * s2 = &cpath; + + // first has to be shorter in std::mismatch(). Returns first non-matching iterators. + if (s1->size() >= s2->size()){ + std::swap(s1, s2); + } + + const auto mism = std::mismatch(s1->begin(), s1->end(), s2->begin()); + match_idx[i] = mism.first - s1->begin(); + path_permutation[i] = i; + } + + std::sort(path_permutation.begin(), path_permutation.end(), [&](const size_t i0, const size_t i1) { + return match_idx[i0] > match_idx[i1]; + }); + + tools::apply_permutation(path_permutation, res); + } + std::shared_ptr<Transport> transport(const std::string & path){ if (boost::starts_with(path, BridgeTransport::PATH_PREFIX)){ return std::make_shared<BridgeTransport>(path.substr(strlen(BridgeTransport::PATH_PREFIX))); diff --git a/src/device_trezor/trezor/transport.hpp b/src/device_trezor/trezor/transport.hpp index cde862547..affd91553 100644 --- a/src/device_trezor/trezor/transport.hpp +++ b/src/device_trezor/trezor/transport.hpp @@ -303,6 +303,11 @@ namespace trezor { void enumerate(t_transport_vect & res); /** + * Sorts found transports by TREZOR_PATH environment variable. + */ + void sort_transports_by_env(t_transport_vect & res); + + /** * Transforms path to the transport */ std::shared_ptr<Transport> transport(const std::string & path); diff --git a/src/p2p/net_node.inl b/src/p2p/net_node.inl index be97edbe5..ba29d92c9 100644 --- a/src/p2p/net_node.inl +++ b/src/p2p/net_node.inl @@ -1955,7 +1955,7 @@ namespace nodetool const epee::net_utils::zone zone_type = context.m_remote_address.get_zone(); network_zone& zone = m_network_zones.at(zone_type); - zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new); + zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new, true); m_payload_handler.get_payload_sync_data(rsp.payload_data); /* Tor/I2P nodes receiving connections via forwarding (from tor/i2p daemon) @@ -2058,7 +2058,7 @@ namespace nodetool }); //fill response - zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new); + zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new, true); get_local_node_data(rsp.node_data, zone); m_payload_handler.get_payload_sync_data(rsp.payload_data); LOG_DEBUG_CC(context, "COMMAND_HANDSHAKE"); diff --git a/src/p2p/net_peerlist.h b/src/p2p/net_peerlist.h index 52814af94..f4fa921e2 100644 --- a/src/p2p/net_peerlist.h +++ b/src/p2p/net_peerlist.h @@ -102,7 +102,7 @@ namespace nodetool size_t get_white_peers_count(){CRITICAL_REGION_LOCAL(m_peerlist_lock); return m_peers_white.size();} size_t get_gray_peers_count(){CRITICAL_REGION_LOCAL(m_peerlist_lock); return m_peers_gray.size();} bool merge_peerlist(const std::vector<peerlist_entry>& outer_bs); - bool get_peerlist_head(std::vector<peerlist_entry>& bs_head, uint32_t depth = P2P_DEFAULT_PEERS_IN_HANDSHAKE); + bool get_peerlist_head(std::vector<peerlist_entry>& bs_head, bool anonymize, uint32_t depth = P2P_DEFAULT_PEERS_IN_HANDSHAKE); void get_peerlist(std::vector<peerlist_entry>& pl_gray, std::vector<peerlist_entry>& pl_white); void get_peerlist(peerlist_types& peers); bool get_white_peer_by_index(peerlist_entry& p, size_t i); @@ -263,23 +263,40 @@ namespace nodetool } //-------------------------------------------------------------------------------------------------- inline - bool peerlist_manager::get_peerlist_head(std::vector<peerlist_entry>& bs_head, uint32_t depth) + bool peerlist_manager::get_peerlist_head(std::vector<peerlist_entry>& bs_head, bool anonymize, uint32_t depth) { - CRITICAL_REGION_LOCAL(m_peerlist_lock); peers_indexed::index<by_time>::type& by_time_index=m_peers_white.get<by_time>(); uint32_t cnt = 0; - bs_head.reserve(depth); + + // picks a random set of peers within the first 120%, rather than a set of the first 100%. + // The intent is that if someone asks twice, they can't easily tell: + // - this address was not in the first list, but is in the second, so the only way this can be + // is if its last_seen was recently reset, so this means the target node recently had a new + // connection to that address + // - this address was in the first list, and not in the second, which means either the address + // was moved to the gray list (if it's not accessibe, which the attacker can check if + // the address accepts incoming connections) or it was the oldest to still fit in the 250 items, + // so its last_seen is old. + const uint32_t pick_depth = anonymize ? depth + depth / 5 : depth; + bs_head.reserve(pick_depth); for(const peers_indexed::value_type& vl: boost::adaptors::reverse(by_time_index)) { - if(!vl.last_seen) - continue; - - if(cnt++ >= depth) + if(cnt++ >= pick_depth) break; bs_head.push_back(vl); } + + if (anonymize) + { + std::random_shuffle(bs_head.begin(), bs_head.end()); + if (bs_head.size() > depth) + bs_head.resize(depth); + for (auto &e: bs_head) + e.last_seen = 0; + } + return true; } //-------------------------------------------------------------------------------------------------- diff --git a/src/p2p/p2p_protocol_defs.h b/src/p2p/p2p_protocol_defs.h index 59c6099d5..85774fcd5 100644 --- a/src/p2p/p2p_protocol_defs.h +++ b/src/p2p/p2p_protocol_defs.h @@ -81,7 +81,8 @@ namespace nodetool BEGIN_KV_SERIALIZE_MAP() KV_SERIALIZE(adr) KV_SERIALIZE(id) - KV_SERIALIZE(last_seen) + if (!is_store || this_ref.last_seen != 0) + KV_SERIALIZE_OPT(last_seen, (int64_t)0) KV_SERIALIZE_OPT(pruning_seed, (uint32_t)0) KV_SERIALIZE_OPT(rpc_port, (uint16_t)0) END_KV_SERIALIZE_MAP() @@ -132,7 +133,7 @@ namespace nodetool ss << pe.id << "\t" << pe.adr.str() << " \trpc port " << (pe.rpc_port > 0 ? std::to_string(pe.rpc_port) : "-") << " \tpruning seed " << pe.pruning_seed - << " \tlast_seen: " << epee::misc_utils::get_time_interval_string(now_time - pe.last_seen) + << " \tlast_seen: " << (pe.last_seen == 0 ? std::string("never") : epee::misc_utils::get_time_interval_string(now_time - pe.last_seen)) << std::endl; } return ss.str(); diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp index c41fb37d8..468fce9e8 100644 --- a/src/rpc/core_rpc_server.cpp +++ b/src/rpc/core_rpc_server.cpp @@ -28,6 +28,7 @@ // // Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers +#include <boost/preprocessor/stringize.hpp> #include "include_base_utils.h" #include "string_tools.h" using namespace epee; @@ -159,6 +160,14 @@ namespace cryptonote const std::vector<std::string> ssl_allowed_fingerprint_strings = command_line::get_arg(vm, arg_rpc_ssl_allowed_fingerprints); std::vector<std::vector<uint8_t>> ssl_allowed_fingerprints{ ssl_allowed_fingerprint_strings.size() }; std::transform(ssl_allowed_fingerprint_strings.begin(), ssl_allowed_fingerprint_strings.end(), ssl_allowed_fingerprints.begin(), epee::from_hex::vector); + for (const auto &fpr: ssl_allowed_fingerprints) + { + if (fpr.size() != SSL_FINGERPRINT_SIZE) + { + MERROR("SHA-256 fingerprint should be " BOOST_PP_STRINGIZE(SSL_FINGERPRINT_SIZE) " bytes long."); + return false; + } + } if (!ssl_ca_path.empty() || !ssl_allowed_fingerprints.empty()) ssl_options = epee::net_utils::ssl_options_t{std::move(ssl_allowed_fingerprints), std::move(ssl_ca_path)}; @@ -2308,7 +2317,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 +2360,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); }; diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp index bb2850901..ae980ce0f 100644 --- a/src/wallet/wallet2.cpp +++ b/src/wallet/wallet2.cpp @@ -39,6 +39,7 @@ #include <boost/algorithm/string/join.hpp> #include <boost/asio/ip/address.hpp> #include <boost/range/adaptor/transformed.hpp> +#include <boost/preprocessor/stringize.hpp> #include "include_base_utils.h" using namespace epee; @@ -131,6 +132,9 @@ using namespace cryptonote; #define GAMMA_SHAPE 19.28 #define GAMMA_SCALE (1/1.61) +#define DEFAULT_MIN_OUTPUT_COUNT 5 +#define DEFAULT_MIN_OUTPUT_VALUE (2*COIN) + static const std::string MULTISIG_SIGNATURE_MAGIC = "SigMultisigPkV1"; static const std::string MULTISIG_EXTRA_INFO_MAGIC = "MultisigxV1"; @@ -340,6 +344,11 @@ std::unique_ptr<tools::wallet2> make_basic(const boost::program_options::variabl { std::vector<std::vector<uint8_t>> ssl_allowed_fingerprints{ daemon_ssl_allowed_fingerprints.size() }; std::transform(daemon_ssl_allowed_fingerprints.begin(), daemon_ssl_allowed_fingerprints.end(), ssl_allowed_fingerprints.begin(), epee::from_hex::vector); + for (const auto &fpr: daemon_ssl_allowed_fingerprints) + { + THROW_WALLET_EXCEPTION_IF(fpr.size() != SSL_FINGERPRINT_SIZE, tools::error::wallet_internal_error, + "SHA-256 fingerprint should be " BOOST_PP_STRINGIZE(SSL_FINGERPRINT_SIZE) " bytes long."); + } ssl_options = epee::net_utils::ssl_options_t{ std::move(ssl_allowed_fingerprints), std::move(daemon_ssl_ca_file) @@ -9378,9 +9387,16 @@ std::vector<wallet2::pending_tx> wallet2::create_transactions_2(std::vector<cryp idx = pop_best_value(indices, tx.selected_transfers, true); // we might not want to add it if it's a large output and we don't have many left - if (m_transfers[idx].amount() >= m_min_output_value) { - if (get_count_above(m_transfers, *unused_transfers_indices, m_min_output_value) < m_min_output_count) { - LOG_PRINT_L2("Second output was not strictly needed, and we're running out of outputs above " << print_money(m_min_output_value) << ", not adding"); + uint64_t min_output_value = m_min_output_value; + uint32_t min_output_count = m_min_output_count; + if (min_output_value == 0 && min_output_count == 0) + { + min_output_value = DEFAULT_MIN_OUTPUT_VALUE; + min_output_count = DEFAULT_MIN_OUTPUT_COUNT; + } + if (m_transfers[idx].amount() >= min_output_value) { + if (get_count_above(m_transfers, *unused_transfers_indices, min_output_value) < min_output_count) { + LOG_PRINT_L2("Second output was not strictly needed, and we're running out of outputs above " << print_money(min_output_value) << ", not adding"); break; } } diff --git a/src/wallet/wallet_rpc_server.cpp b/src/wallet/wallet_rpc_server.cpp index 4076ae957..22eaffa6f 100644 --- a/src/wallet/wallet_rpc_server.cpp +++ b/src/wallet/wallet_rpc_server.cpp @@ -31,6 +31,7 @@ #include <boost/asio/ip/address.hpp> #include <boost/filesystem/operations.hpp> #include <boost/algorithm/string.hpp> +#include <boost/preprocessor/stringize.hpp> #include <cstdint> #include "include_base_utils.h" using namespace epee; @@ -254,6 +255,14 @@ namespace tools { std::vector<std::vector<uint8_t>> allowed_fingerprints{ rpc_ssl_allowed_fingerprints.size() }; std::transform(rpc_ssl_allowed_fingerprints.begin(), rpc_ssl_allowed_fingerprints.end(), allowed_fingerprints.begin(), epee::from_hex::vector); + for (const auto &fpr: rpc_ssl_allowed_fingerprints) + { + if (fpr.size() != SSL_FINGERPRINT_SIZE) + { + MERROR("SHA-256 fingerprint should be " BOOST_PP_STRINGIZE(SSL_FINGERPRINT_SIZE) " bytes long."); + return false; + } + } rpc_ssl_options = epee::net_utils::ssl_options_t{ std::move(allowed_fingerprints), std::move(rpc_ssl_ca_file) @@ -4069,9 +4078,10 @@ namespace tools { cryptonote::TESTNET, "testnet" }, { cryptonote::STAGENET, "stagenet" }, }; + if (!req.any_net_type && !m_wallet) return not_open(er); for (const auto &net_type: net_types) { - if (!req.any_net_type && net_type.type != m_wallet->nettype()) + if (!req.any_net_type && (!m_wallet || net_type.type != m_wallet->nettype())) continue; if (req.allow_openalias) { @@ -4153,6 +4163,7 @@ namespace tools { er.code = WALLET_RPC_ERROR_CODE_NO_DAEMON_CONNECTION; er.message = "SSL is enabled but no user certificate or fingerprints were provided"; + return false; } if (!m_wallet->set_daemon(req.address, boost::none, req.trusted, std::move(ssl_options))) @@ -4177,7 +4188,7 @@ namespace tools { er.code = WALLET_RPC_ERROR_CODE_INVALID_LOG_LEVEL; er.message = "Error: log level not valid"; - return true; + return false; } mlog_set_log_level(req.level); return true; diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt index bbb0bc051..afc69ee88 100644 --- a/tests/CMakeLists.txt +++ b/tests/CMakeLists.txt @@ -66,6 +66,7 @@ else () # Emulate the FindGTest module's variable. set(GTEST_LIBRARIES gtest gtest_main) + set(GTEST_BOTH_LIBRARIES gtest gtest_main) include_directories(SYSTEM "${CMAKE_CURRENT_SOURCE_DIR}/gtest/include") endif (GTest_FOUND) diff --git a/tests/functional_tests/functional_tests_rpc.py b/tests/functional_tests/functional_tests_rpc.py index 83b75a088..1a1fa5490 100755 --- a/tests/functional_tests/functional_tests_rpc.py +++ b/tests/functional_tests/functional_tests_rpc.py @@ -10,7 +10,7 @@ import string import os USAGE = 'usage: functional_tests_rpc.py <python> <srcdir> <builddir> [<tests-to-run> | all]' -DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs'] +DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs', 'get_output_distribution'] try: python = sys.argv[1] srcdir = sys.argv[2] @@ -98,6 +98,7 @@ FAIL = [] for test in tests: try: print('[TEST STARTED] ' + test) + sys.stdout.flush() cmd = [python, srcdir + '/' + test + ".py"] subprocess.check_call(cmd) PASS.append(test) diff --git a/tests/functional_tests/get_output_distribution.py b/tests/functional_tests/get_output_distribution.py new file mode 100755 index 000000000..2a0762d5e --- /dev/null +++ b/tests/functional_tests/get_output_distribution.py @@ -0,0 +1,217 @@ +#!/usr/bin/env python3 + +# Copyright (c) 2019 The Monero Project +# +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without modification, are +# permitted provided that the following conditions are met: +# +# 1. Redistributions of source code must retain the above copyright notice, this list of +# conditions and the following disclaimer. +# +# 2. Redistributions in binary form must reproduce the above copyright notice, this list +# of conditions and the following disclaimer in the documentation and/or other +# materials provided with the distribution. +# +# 3. Neither the name of the copyright holder nor the names of its contributors may be +# used to endorse or promote products derived from this software without specific +# prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +# THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +# STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +# THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +import time + +"""Test get_output_distribution RPC +""" + +from framework.daemon import Daemon +from framework.wallet import Wallet + +class GetOutputDistributionTest(): + def run_test(self): + self.reset() + self.create() + self.test_get_output_distribution() + + def reset(self): + print 'Resetting blockchain' + daemon = Daemon() + daemon.pop_blocks(1000) + daemon.flush_txpool() + + def create(self): + self.wallet = Wallet() + # close the wallet if any, will throw if none is loaded + try: self.wallet.close_wallet() + except: pass + res = self.wallet.restore_deterministic_wallet(seed = 'velvet lymph giddy number token physics poetry unquoted nibs useful sabotage limits benches lifestyle eden nitrogen anvil fewest avoid batch vials washing fences goat unquoted') + + def test_get_output_distribution(self): + print "Test get_output_distribution" + + daemon = Daemon() + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 0 + + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1) + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 2 + assert d.distribution[0] == 0 + assert d.distribution[1] == 1 + + res = daemon.pop_blocks(1) + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 0 + + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 3) + + res = daemon.get_output_distribution([0], 0, 0, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 4 + assert d.distribution[0] == 0 + assert d.distribution[1] == 1 + assert d.distribution[2] == 2 + assert d.distribution[3] == 3 + + # extend + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 80) + + res = daemon.get_output_distribution([0], 0, 0, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 84 + for h in range(len(d.distribution)): + assert d.distribution[h] == h + + # pop and replace, this will do through the "trim and extend" path + res = daemon.pop_blocks(2) + self.wallet.refresh() + dst = {'address': '42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 'amount': 1000000000000} + self.wallet.transfer([dst]) + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1) + for step in range(3): # the second will be cached, the third will also be cached, but we get it in non-cumulative mode + res = daemon.get_output_distribution([0], 0, 0, cumulative = step < 3) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 83 + for h in range(len(d.distribution)): + assert d.distribution[h] == (h if step < 3 else 1) + (2 if h == len(d.distribution) - 1 else 0) + + # start at 0, end earlier + res = daemon.get_output_distribution([0], 0, 40, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 41 + for h in range(len(d.distribution)): + assert d.distribution[h] == h + + # start after 0, end earlier + res = daemon.get_output_distribution([0], 10, 20, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 9 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 10 + h + + # straddling up + res = daemon.get_output_distribution([0], 15, 25, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 14 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 15 + h + + # straddling down + res = daemon.get_output_distribution([0], 8, 18, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 7 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 8 + h + + # encompassing + res = daemon.get_output_distribution([0], 5, 20, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 4 + assert d.binary == False + assert len(d.distribution) == 16 + for h in range(len(d.distribution)): + assert d.distribution[h] == 5 + h + + # single + res = daemon.get_output_distribution([0], 2, 2, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 1 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 2 + + # a non existent amount + res = daemon.get_output_distribution([1], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 1 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 83 + for h in range(len(d.distribution)): + assert d.distribution[h] == 0 + + +if __name__ == '__main__': + GetOutputDistributionTest().run_test() diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt index 56a1f8c4d..1c4c4384c 100644 --- a/tests/unit_tests/CMakeLists.txt +++ b/tests/unit_tests/CMakeLists.txt @@ -72,6 +72,7 @@ set(unit_tests_sources parse_amount.cpp pruning.cpp random.cpp + rolling_median.cpp serialization.cpp sha256.cpp slow_memmem.cpp diff --git a/tests/unit_tests/output_distribution.cpp b/tests/unit_tests/output_distribution.cpp index 45f2c135b..38f442c59 100644 --- a/tests/unit_tests/output_distribution.cpp +++ b/tests/unit_tests/output_distribution.cpp @@ -62,6 +62,13 @@ public: return d; } + std::vector<uint64_t> get_block_weights(uint64_t start_offset, size_t count) const override + { + std::vector<uint64_t> weights; + while (count--) weights.push_back(1); + return weights; + } + uint64_t blockchain_height; }; @@ -84,36 +91,43 @@ bool get_output_distribution(uint64_t amount, uint64_t from, uint64_t to, uint64 return r && bc->get_output_distribution(amount, from, to, start_height, distribution, base); } +crypto::hash get_block_hash(uint64_t height) +{ + crypto::hash hash; + *((uint64_t*)&hash) = height; + return hash; +} + TEST(output_distribution, extend) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 2); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 2); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 3); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 3); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 4); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2, 3})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 4); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57, 60})); @@ -123,7 +137,7 @@ TEST(output_distribution, one) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 1); ASSERT_EQ(res->distribution.back(), 0); @@ -133,7 +147,7 @@ TEST(output_distribution, full_cumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 32); ASSERT_EQ(res->distribution.back(), 60); @@ -143,7 +157,7 @@ TEST(output_distribution, full_noncumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 32); for (size_t i = 0; i < 32; ++i) @@ -154,7 +168,7 @@ TEST(output_distribution, part_cumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 5); ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 6, 7, 11})); @@ -164,7 +178,7 @@ TEST(output_distribution, part_noncumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 5); ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 5, 1, 4})); diff --git a/tests/unit_tests/rolling_median.cpp b/tests/unit_tests/rolling_median.cpp new file mode 100644 index 000000000..6d6adcc7d --- /dev/null +++ b/tests/unit_tests/rolling_median.cpp @@ -0,0 +1,202 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include <random> +#include "gtest/gtest.h" +#include "misc_language.h" +#include "rolling_median.h" +#include "crypto/crypto.h" + +TEST(rolling_median, one) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(18); + ASSERT_EQ(m.median(), 18); + m.insert(7483); + ASSERT_EQ(m.median(), 7483); +} + +TEST(rolling_median, two) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(2); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(45); + ASSERT_EQ(m.median(), 43); + m.insert(49); + ASSERT_EQ(m.median(), 47); + m.insert(41); + ASSERT_EQ(m.median(), 45); + m.insert(43); + ASSERT_EQ(m.median(), 42); + m.insert(40); + ASSERT_EQ(m.median(), 41); + m.insert(41); + ASSERT_EQ(m.median(), 40); +} + +TEST(rolling_median, series) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> v; + v.reserve(100); + for (int i = 0; i < 10000; ++i) + { + uint64_t r = rand(); + v.push_back(r); + if (v.size() > 100) + v.erase(v.begin()); + m.insert(r); + std::vector<uint64_t> vcopy = v; + ASSERT_EQ(m.median(), epee::misc_utils::median(vcopy)); + } +} + +TEST(rolling_median, clear_whole) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 0; i < 10000; ++i) + { + m.insert(random[i]); + ASSERT_EQ(median[i], m.median()); + } +} + +TEST(rolling_median, clear_partway) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 10000 - 100; i < 10000; ++i) + { + m.insert(random[i]); + } + ASSERT_EQ(median[10000-1], m.median()); +} + +TEST(rolling_median, order) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1000); + std::vector<uint64_t> random; + random.reserve(1000); + for (int i = 0; i < 1000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + } + const uint64_t med = m.median(); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a < b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a > b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::shuffle(random.begin(), random.end(), std::default_random_engine(crypto::rand<unsigned>())); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); +} + +TEST(rolling_median, history_blind) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + uint64_t median = 0; + for (int i = 0; i < 1000; ++i) + { + m.clear(); + int history_length = 743723 % (i+1); + while (history_length--) + m.insert(743284 % (i+1)); + for (int j = 0; j < 10; ++j) + m.insert(8924829384 % (j+1)); + if (i == 0) + median = m.median(); + else + ASSERT_EQ(median, m.median()); + } +} + +TEST(rolling_median, size) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + ASSERT_EQ(m.size(), 0); + m.insert(1); + ASSERT_EQ(m.size(), 1); + m.insert(2); + ASSERT_EQ(m.size(), 2); + m.clear(); + ASSERT_EQ(m.size(), 0); + for (int i = 0; i < 10; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), i + 1); + } + m.insert(1); + ASSERT_EQ(m.size(), 10); + m.insert(2); + ASSERT_EQ(m.size(), 10); + m.clear(); + ASSERT_EQ(m.size(), 0); + m.insert(4); + ASSERT_EQ(m.size(), 1); + for (int i = 0; i < 1000; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), std::min<int>(10, i + 2)); + } +} |