aboutsummaryrefslogtreecommitdiff
path: root/src/net
diff options
context:
space:
mode:
Diffstat (limited to 'src/net')
-rw-r--r--src/net/CMakeLists.txt4
-rw-r--r--src/net/dandelionpp.cpp212
-rw-r--r--src/net/dandelionpp.h106
3 files changed, 320 insertions, 2 deletions
diff --git a/src/net/CMakeLists.txt b/src/net/CMakeLists.txt
index 738f858f0..24b707f77 100644
--- a/src/net/CMakeLists.txt
+++ b/src/net/CMakeLists.txt
@@ -26,8 +26,8 @@
# 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.
-set(net_sources error.cpp i2p_address.cpp parse.cpp socks.cpp socks_connect.cpp tor_address.cpp)
-set(net_headers error.h i2p_address.h parse.h socks.h socks_connect.h tor_address.h)
+set(net_sources dandelionpp.cpp error.cpp i2p_address.cpp parse.cpp socks.cpp socks_connect.cpp tor_address.cpp)
+set(net_headers dandelionpp.h error.h i2p_address.h parse.h socks.h socks_connect.h tor_address.h)
monero_add_library(net ${net_sources} ${net_headers})
target_link_libraries(net common epee ${Boost_ASIO_LIBRARY})
diff --git a/src/net/dandelionpp.cpp b/src/net/dandelionpp.cpp
new file mode 100644
index 000000000..4d2f75428
--- /dev/null
+++ b/src/net/dandelionpp.cpp
@@ -0,0 +1,212 @@
+// 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 "dandelionpp.h"
+
+#include <boost/container/small_vector.hpp>
+#include <boost/uuid/nil_generator.hpp>
+#include <chrono>
+
+#include "common/expect.h"
+#include "cryptonote_config.h"
+#include "crypto/crypto.h"
+
+namespace net
+{
+namespace dandelionpp
+{
+ namespace
+ {
+ constexpr const std::size_t expected_max_channels = CRYPTONOTE_NOISE_CHANNELS;
+
+ // could be in util somewhere
+ struct key_less
+ {
+ template<typename K, typename V>
+ bool operator()(const std::pair<K, V>& left, const K& right) const
+ {
+ return left.first < right;
+ }
+
+ template<typename K, typename V>
+ bool operator()(const K& left, const std::pair<K, V>& right) const
+ {
+ return left < right.first;
+ }
+ };
+
+ std::size_t select_stem(epee::span<const std::size_t> usage, epee::span<const boost::uuids::uuid> out_map)
+ {
+ assert(usage.size() < std::numeric_limits<std::size_t>::max()); // prevented in constructor
+ if (usage.size() < out_map.size())
+ return std::numeric_limits<std::size_t>::max();
+
+ // small_vector uses stack space if `expected_max_channels < capacity()`
+ std::size_t lowest = std::numeric_limits<std::size_t>::max();
+ boost::container::small_vector<std::size_t, expected_max_channels> choices;
+ static_assert(sizeof(choices) < 256, "choices is too large based on current configuration");
+
+ for (const boost::uuids::uuid& out : out_map)
+ {
+ if (!out.is_nil())
+ {
+ const std::size_t location = std::addressof(out) - out_map.begin();
+ if (usage[location] < lowest)
+ {
+ lowest = usage[location];
+ choices = {location};
+ }
+ else if (usage[location] == lowest)
+ choices.push_back(location);
+ }
+ }
+
+ switch (choices.size())
+ {
+ case 0:
+ return std::numeric_limits<std::size_t>::max();
+ case 1:
+ return choices[0];
+ default:
+ break;
+ }
+
+ return choices[crypto::rand_idx(choices.size())];
+ }
+ } // anonymous
+
+ connection_map::connection_map(std::vector<boost::uuids::uuid> out_connections, const std::size_t stems)
+ : out_mapping_(std::move(out_connections)),
+ in_mapping_(),
+ usage_count_()
+ {
+ // max value is used by `select_stem` as error case
+ if (stems == std::numeric_limits<std::size_t>::max())
+ MONERO_THROW(common_error::kInvalidArgument, "stems value cannot be max size_t");
+
+ usage_count_.resize(stems);
+ if (stems < out_mapping_.size())
+ {
+ for (unsigned i = 0; i < stems; ++i)
+ std::swap(out_mapping_[i], out_mapping_.at(i + crypto::rand_idx(out_mapping_.size() - i)));
+
+ out_mapping_.resize(stems);
+ }
+ else
+ {
+ std::shuffle(out_mapping_.begin(), out_mapping_.end(), crypto::random_device{});
+ }
+ }
+
+ connection_map::~connection_map() noexcept
+ {}
+
+ connection_map connection_map::clone() const
+ {
+ return {*this};
+ }
+
+ bool connection_map::update(std::vector<boost::uuids::uuid> current)
+ {
+ std::sort(current.begin(), current.end());
+
+ bool replace = false;
+ for (auto& existing_out : out_mapping_)
+ {
+ const auto elem = std::lower_bound(current.begin(), current.end(), existing_out);
+ if (elem == current.end() || *elem != existing_out)
+ {
+ existing_out = boost::uuids::nil_uuid();
+ replace = true;
+ }
+ else // already using connection, remove it from candidate list
+ current.erase(elem);
+ }
+
+ if (!replace && out_mapping_.size() == usage_count_.size())
+ return false;
+
+ const std::size_t existing_outs = out_mapping_.size();
+ for (std::size_t i = 0; i < usage_count_.size() && !current.empty(); ++i)
+ {
+ const bool increase_stems = out_mapping_.size() <= i;
+ if (increase_stems || out_mapping_[i].is_nil())
+ {
+ std::swap(current.back(), current.at(crypto::rand_idx(current.size())));
+ if (increase_stems)
+ out_mapping_.push_back(current.back());
+ else
+ out_mapping_[i] = current.back();
+ current.pop_back();
+ }
+ }
+
+ return replace || existing_outs < out_mapping_.size();
+ }
+
+ std::size_t connection_map::size() const noexcept
+ {
+ std::size_t count = 0;
+ for (const boost::uuids::uuid& connection : out_mapping_)
+ {
+ if (!connection.is_nil())
+ ++count;
+ }
+ return count;
+ }
+
+ boost::uuids::uuid connection_map::get_stem(const boost::uuids::uuid& source)
+ {
+ auto elem = std::lower_bound(in_mapping_.begin(), in_mapping_.end(), source, key_less{});
+ if (elem == in_mapping_.end() || elem->first != source)
+ {
+ const std::size_t index = select_stem(epee::to_span(usage_count_), epee::to_span(out_mapping_));
+ if (out_mapping_.size() < index)
+ return boost::uuids::nil_uuid();
+
+ elem = in_mapping_.emplace(elem, source, index);
+ usage_count_[index]++;
+ }
+ else if (out_mapping_.at(elem->second).is_nil()) // stem connection disconnected after mapping
+ {
+ usage_count_.at(elem->second)--;
+ const std::size_t index = select_stem(epee::to_span(usage_count_), epee::to_span(out_mapping_));
+ if (out_mapping_.size() < index)
+ {
+ in_mapping_.erase(elem);
+ return boost::uuids::nil_uuid();
+ }
+
+ elem->second = index;
+ usage_count_[index]++;
+ }
+
+ return out_mapping_[elem->second];
+ }
+} // dandelionpp
+} // net
diff --git a/src/net/dandelionpp.h b/src/net/dandelionpp.h
new file mode 100644
index 000000000..75b63bc0c
--- /dev/null
+++ b/src/net/dandelionpp.h
@@ -0,0 +1,106 @@
+// 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.
+
+#pragma once
+
+#include <boost/uuid/uuid.hpp>
+#include <cstddef>
+#include <memory>
+#include <utility>
+#include <vector>
+
+#include "span.h"
+
+namespace net
+{
+namespace dandelionpp
+{
+ //! Assists with mapping source -> stem and tracking connections for stem.
+ class connection_map
+ {
+ // Make sure to update clone method if changing members
+ std::vector<boost::uuids::uuid> out_mapping_; //<! Current outgoing uuid connection at index.
+ std::vector<std::pair<boost::uuids::uuid, std::size_t>> in_mapping_; //<! uuid source to an `out_mapping_` index.
+ std::vector<std::size_t> usage_count_;
+
+ // Use clone method to prevent "hidden" copies.
+ connection_map(const connection_map&) = default;
+
+ public:
+ using value_type = boost::uuids::uuid;
+ using size_type = std::vector<boost::uuids::uuid>::size_type;
+ using difference_type = std::vector<boost::uuids::uuid>::difference_type;
+ using reference = const boost::uuids::uuid&;
+ using const_reference = reference;
+ using iterator = std::vector<boost::uuids::uuid>::const_iterator;
+ using const_iterator = iterator;
+
+ //! Initialized with zero stem connections.
+ explicit connection_map()
+ : connection_map(std::vector<boost::uuids::uuid>{}, 0)
+ {}
+
+ //! Initialized with `out_connections` and `stem_count`.
+ explicit connection_map(std::vector<boost::uuids::uuid> out_connections, std::size_t stems);
+
+ connection_map(connection_map&&) = default;
+ ~connection_map() noexcept;
+ connection_map& operator=(connection_map&&) = default;
+ connection_map& operator=(const connection_map&) = delete;
+
+ //! \return An exact duplicate of `this` map.
+ connection_map clone() const;
+
+ //! \return First stem connection.
+ const_iterator begin() const noexcept
+ {
+ return out_mapping_.begin();
+ }
+
+ //! \return One-past the last stem connection.
+ const_iterator end() const noexcept
+ {
+ return out_mapping_.end();
+ }
+
+ /*! Merges in current connections with the previous set of connections.
+ If a connection died, a new one will take its place in the stem or
+ the stem is marked as dead.
+
+ \param connections Current outbound connection ids.
+ \return True if any updates to `get_connections()` was made. */
+ bool update(std::vector<boost::uuids::uuid> current);
+
+ //! \return Number of outgoing connections in use.
+ std::size_t size() const noexcept;
+
+ //! \return Current stem mapping for `source` or `nil_uuid()` if none is possible.
+ boost::uuids::uuid get_stem(const boost::uuids::uuid& source);
+ };
+} // dandelionpp
+} // net
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 09:10:41 +0000