tomFlowee
562eba5b64
The new SIGHASH_UTXO has a possible attack vector where prepared huge outputs are used and required to be hashed for the signing preimage. At most you can force the full node to prepare 20GB of (utxo) data _prior_ to creation of the preimage. Which is a big issue when it comes to memory usage of the node. What this change does is we ensure that the class used for this data is a ConstBuf as given to us from the utxo. Which are just pointers and not full data, the data is memory mapped. So we ensure shallow copies to avoid actually requiring the data to be in memory until the point where it is used. And it can get swapped out immediately after. This ensures we are immune to the SIGHASH_UTXO attack vector.
516 lines
17 KiB
C++
516 lines
17 KiB
C++
/*
|
|
* This file is part of the Flowee project
|
|
* Copyright (C) 2015 The Bitcoin Core developers
|
|
* Copyright (C) 2018 Tom Zander <tom@flowee.org>
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#ifndef _FLOWEE_PREVECTOR_H_
|
|
#define _FLOWEE_PREVECTOR_H_
|
|
|
|
#include <streaming/ConstBuffer.h>
|
|
|
|
#include <cstdlib>
|
|
#include <cstdint>
|
|
#include <cstring>
|
|
|
|
#include <iterator>
|
|
#include <assert.h>
|
|
|
|
#pragma pack(push, 1)
|
|
/** Implements a drop-in replacement for std::vector<T> which stores up to N
|
|
* elements directly (without heap allocation). The types Size and Diff are
|
|
* used to store element counts, and can be any unsigned + signed type.
|
|
*
|
|
* Storage layout is either:
|
|
* - Direct allocation:
|
|
* - Size _size: the number of used elements (between 0 and N)
|
|
* - T direct[N]: an array of N elements of type T
|
|
* (only the first _size are initialized).
|
|
* - Indirect allocation:
|
|
* - Size _size: the number of used elements plus N + 1
|
|
* - Size capacity: the number of allocated elements
|
|
* - T* indirect: a pointer to an array of capacity elements of type T
|
|
* (only the first _size are initialized).
|
|
*
|
|
* The data type T must be movable by memmove/realloc(). Once we switch to C++,
|
|
* move constructors can be used instead.
|
|
*/
|
|
template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
|
|
class prevector {
|
|
public:
|
|
typedef Size size_type;
|
|
typedef Diff difference_type;
|
|
typedef T value_type;
|
|
typedef value_type& reference;
|
|
typedef const value_type& const_reference;
|
|
typedef value_type* pointer;
|
|
typedef const value_type* const_pointer;
|
|
|
|
class iterator {
|
|
T* ptr;
|
|
public:
|
|
typedef Diff difference_type;
|
|
typedef T value_type;
|
|
typedef T* pointer;
|
|
typedef T& reference;
|
|
typedef std::random_access_iterator_tag iterator_category;
|
|
iterator(T* ptr_) : ptr(ptr_) {}
|
|
T& operator*() const { return *ptr; }
|
|
T* operator->() const { return ptr; }
|
|
T& operator[](size_type pos) { return ptr[pos]; }
|
|
const T& operator[](size_type pos) const { return ptr[pos]; }
|
|
iterator& operator++() { ptr++; return *this; }
|
|
iterator& operator--() { ptr--; return *this; }
|
|
iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
|
|
iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
|
|
difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
|
|
iterator operator+(size_type n) { return iterator(ptr + n); }
|
|
iterator& operator+=(size_type n) { ptr += n; return *this; }
|
|
iterator operator-(size_type n) { return iterator(ptr - n); }
|
|
iterator& operator-=(size_type n) { ptr -= n; return *this; }
|
|
bool operator==(iterator x) const { return ptr == x.ptr; }
|
|
bool operator!=(iterator x) const { return ptr != x.ptr; }
|
|
bool operator>=(iterator x) const { return ptr >= x.ptr; }
|
|
bool operator<=(iterator x) const { return ptr <= x.ptr; }
|
|
bool operator>(iterator x) const { return ptr > x.ptr; }
|
|
bool operator<(iterator x) const { return ptr < x.ptr; }
|
|
};
|
|
|
|
class reverse_iterator {
|
|
T* ptr;
|
|
public:
|
|
typedef Diff difference_type;
|
|
typedef T value_type;
|
|
typedef T* pointer;
|
|
typedef T& reference;
|
|
typedef std::bidirectional_iterator_tag iterator_category;
|
|
reverse_iterator(T* ptr_) : ptr(ptr_) {}
|
|
T& operator*() { return *ptr; }
|
|
const T& operator*() const { return *ptr; }
|
|
T* operator->() { return ptr; }
|
|
const T* operator->() const { return ptr; }
|
|
reverse_iterator& operator--() { ptr++; return *this; }
|
|
reverse_iterator& operator++() { ptr--; return *this; }
|
|
reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
|
|
reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
|
|
bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
|
|
bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
|
|
};
|
|
|
|
class const_iterator {
|
|
const T* ptr;
|
|
public:
|
|
typedef Diff difference_type;
|
|
typedef const T value_type;
|
|
typedef const T* pointer;
|
|
typedef const T& reference;
|
|
typedef std::random_access_iterator_tag iterator_category;
|
|
const_iterator(const T* ptr_) : ptr(ptr_) {}
|
|
const_iterator(iterator x) : ptr(&(*x)) {}
|
|
const T& operator*() const { return *ptr; }
|
|
const T* operator->() const { return ptr; }
|
|
const T& operator[](size_type pos) const { return ptr[pos]; }
|
|
const_iterator& operator++() { ptr++; return *this; }
|
|
const_iterator& operator--() { ptr--; return *this; }
|
|
const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
|
|
const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
|
|
difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
|
|
const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
|
|
const_iterator& operator+=(size_type n) { ptr += n; return *this; }
|
|
const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
|
|
const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
|
|
bool operator==(const_iterator x) const { return ptr == x.ptr; }
|
|
bool operator!=(const_iterator x) const { return ptr != x.ptr; }
|
|
bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
|
|
bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
|
|
bool operator>(const_iterator x) const { return ptr > x.ptr; }
|
|
bool operator<(const_iterator x) const { return ptr < x.ptr; }
|
|
};
|
|
|
|
class const_reverse_iterator {
|
|
const T* ptr;
|
|
public:
|
|
typedef Diff difference_type;
|
|
typedef const T value_type;
|
|
typedef const T* pointer;
|
|
typedef const T& reference;
|
|
typedef std::bidirectional_iterator_tag iterator_category;
|
|
const_reverse_iterator(T* ptr_) : ptr(ptr_) {}
|
|
const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
|
|
const T& operator*() const { return *ptr; }
|
|
const T* operator->() const { return ptr; }
|
|
const_reverse_iterator& operator--() { ptr++; return *this; }
|
|
const_reverse_iterator& operator++() { ptr--; return *this; }
|
|
const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
|
|
const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
|
|
bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
|
|
bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
|
|
};
|
|
|
|
private:
|
|
size_type _size;
|
|
union direct_or_indirect {
|
|
char direct[sizeof(T) * N];
|
|
struct {
|
|
size_type capacity;
|
|
char* indirect;
|
|
bool owned;
|
|
};
|
|
} _union;
|
|
|
|
T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
|
|
const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
|
|
T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
|
|
const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
|
|
bool is_direct() const { return _size <= N; }
|
|
|
|
void change_capacity(size_type new_capacity) {
|
|
if (new_capacity <= N) {
|
|
if (!is_direct()) {
|
|
T* indirect = indirect_ptr(0);
|
|
T* src = indirect;
|
|
T* dst = direct_ptr(0);
|
|
memcpy(dst, src, size() * sizeof(T));
|
|
free(indirect);
|
|
_size -= N + 1;
|
|
}
|
|
} else {
|
|
if (!is_direct()) {
|
|
_union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
|
|
_union.owned = true;
|
|
_union.capacity = new_capacity;
|
|
} else {
|
|
char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
|
|
T* src = direct_ptr(0);
|
|
T* dst = reinterpret_cast<T*>(new_indirect);
|
|
memcpy(dst, src, size() * sizeof(T));
|
|
_union.indirect = new_indirect;
|
|
_union.capacity = new_capacity;
|
|
_union.owned = true;
|
|
_size += N + 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
|
|
const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
|
|
|
|
public:
|
|
void assign(size_type n, const T& val) {
|
|
clear();
|
|
if (capacity() < n) {
|
|
change_capacity(n);
|
|
}
|
|
while (size() < n) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(val);
|
|
}
|
|
}
|
|
|
|
template<typename InputIterator>
|
|
void assign(InputIterator first, InputIterator last) {
|
|
size_type n = last - first;
|
|
clear();
|
|
if (capacity() < n) {
|
|
change_capacity(n);
|
|
}
|
|
while (first != last) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
|
|
++first;
|
|
}
|
|
}
|
|
|
|
prevector() : _size(0) {}
|
|
|
|
explicit prevector(size_type n) : _size(0) {
|
|
resize(n);
|
|
}
|
|
|
|
explicit prevector(size_type n, const T& val = T()) : _size(0) {
|
|
change_capacity(n);
|
|
while (size() < n) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(val);
|
|
}
|
|
}
|
|
|
|
template<typename InputIterator>
|
|
prevector(InputIterator first, InputIterator last) : _size(0) {
|
|
size_type n = last - first;
|
|
change_capacity(n);
|
|
while (first != last) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(*first);
|
|
++first;
|
|
}
|
|
}
|
|
|
|
prevector(const prevector<N, T, Size, Diff>& other) : _size(0) {
|
|
change_capacity(other.size());
|
|
const_iterator it = other.begin();
|
|
while (it != other.end()) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
|
|
++it;
|
|
}
|
|
}
|
|
prevector(const Streaming::ConstBuffer &buffer)
|
|
: _size(buffer.size() + N + 1)
|
|
{
|
|
static_assert(sizeof(T) == 1, "Can only be used for byte-arrays");
|
|
_union.capacity = buffer.size();
|
|
_union.owned = false;
|
|
_union.indirect = const_cast<char*>(buffer.begin());
|
|
}
|
|
|
|
prevector& operator=(const prevector<N, T, Size, Diff>& other) {
|
|
if (&other == this) {
|
|
return *this;
|
|
}
|
|
resize(0);
|
|
change_capacity(other.size());
|
|
const_iterator it = other.begin();
|
|
while (it != other.end()) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T(*it);
|
|
++it;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
size_type size() const {
|
|
return is_direct() ? _size : _size - N - 1;
|
|
}
|
|
|
|
bool empty() const {
|
|
return size() == 0;
|
|
}
|
|
|
|
iterator begin() { return iterator(item_ptr(0)); }
|
|
const_iterator begin() const { return const_iterator(item_ptr(0)); }
|
|
iterator end() { return iterator(item_ptr(size())); }
|
|
const_iterator end() const { return const_iterator(item_ptr(size())); }
|
|
|
|
reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
|
|
const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
|
|
reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
|
|
const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
|
|
|
|
size_t capacity() const {
|
|
if (is_direct()) {
|
|
return N;
|
|
} else {
|
|
return _union.capacity;
|
|
}
|
|
}
|
|
|
|
T& operator[](size_type pos) {
|
|
return *item_ptr(pos);
|
|
}
|
|
|
|
const T& operator[](size_type pos) const {
|
|
return *item_ptr(pos);
|
|
}
|
|
|
|
void resize(size_type new_size) {
|
|
if (size() > new_size) {
|
|
erase(item_ptr(new_size), end());
|
|
}
|
|
if (new_size > capacity()) {
|
|
change_capacity(new_size);
|
|
}
|
|
while (size() < new_size) {
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(size() - 1))) T();
|
|
}
|
|
}
|
|
|
|
void reserve(size_type new_capacity) {
|
|
if (new_capacity > capacity()) {
|
|
change_capacity(new_capacity);
|
|
}
|
|
}
|
|
|
|
void shrink_to_fit() {
|
|
change_capacity(size());
|
|
}
|
|
|
|
void clear() {
|
|
resize(0);
|
|
}
|
|
|
|
iterator insert(iterator pos, const T& value) {
|
|
size_type p = pos - begin();
|
|
size_type new_size = size() + 1;
|
|
if (capacity() < new_size) {
|
|
change_capacity(new_size + (new_size >> 1));
|
|
}
|
|
memmove(item_ptr(p + 1), item_ptr(p), (size() - p) * sizeof(T));
|
|
_size++;
|
|
new(static_cast<void*>(item_ptr(p))) T(value);
|
|
return iterator(item_ptr(p));
|
|
}
|
|
|
|
void insert(iterator pos, size_type count, const T& value) {
|
|
size_type p = pos - begin();
|
|
size_type new_size = size() + count;
|
|
if (capacity() < new_size) {
|
|
change_capacity(new_size + (new_size >> 1));
|
|
}
|
|
memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
|
|
_size += count;
|
|
for (size_type i = 0; i < count; i++) {
|
|
new(static_cast<void*>(item_ptr(p + i))) T(value);
|
|
}
|
|
}
|
|
|
|
template<typename InputIterator>
|
|
void insert(iterator pos, InputIterator first, InputIterator last) {
|
|
size_type p = pos - begin();
|
|
difference_type count = last - first;
|
|
size_type new_size = size() + count;
|
|
if (capacity() < new_size) {
|
|
change_capacity(new_size + (new_size >> 1));
|
|
}
|
|
memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
|
|
_size += count;
|
|
while (first != last) {
|
|
new(static_cast<void*>(item_ptr(p))) T(*first);
|
|
++p;
|
|
++first;
|
|
}
|
|
}
|
|
|
|
iterator erase(iterator pos) {
|
|
return erase(pos, pos + 1);
|
|
}
|
|
|
|
iterator erase(iterator first, iterator last) {
|
|
iterator p = first;
|
|
char* endp = (char*)&(*end());
|
|
while (p != last) {
|
|
(*p).~T();
|
|
_size--;
|
|
++p;
|
|
}
|
|
memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
|
|
return first;
|
|
}
|
|
|
|
void push_back(const T& value) {
|
|
size_type new_size = size() + 1;
|
|
if (capacity() < new_size) {
|
|
change_capacity(new_size + (new_size >> 1));
|
|
}
|
|
new(item_ptr(size())) T(value);
|
|
_size++;
|
|
}
|
|
|
|
void pop_back() {
|
|
erase(end() - 1, end());
|
|
}
|
|
|
|
T& front() {
|
|
return *item_ptr(0);
|
|
}
|
|
|
|
const T& front() const {
|
|
return *item_ptr(0);
|
|
}
|
|
|
|
T& back() {
|
|
return *item_ptr(size() - 1);
|
|
}
|
|
|
|
const T& back() const {
|
|
return *item_ptr(size() - 1);
|
|
}
|
|
|
|
void swap(prevector<N, T, Size, Diff>& other) {
|
|
std::swap(_union, other._union);
|
|
std::swap(_size, other._size);
|
|
}
|
|
|
|
~prevector() {
|
|
clear();
|
|
if (!is_direct()) {
|
|
if (_union.owned)
|
|
free(_union.indirect);
|
|
_union.indirect = NULL;
|
|
}
|
|
}
|
|
|
|
bool operator==(const prevector<N, T, Size, Diff>& other) const {
|
|
if (other.size() != size()) {
|
|
return false;
|
|
}
|
|
const_iterator b1 = begin();
|
|
const_iterator b2 = other.begin();
|
|
const_iterator e1 = end();
|
|
while (b1 != e1) {
|
|
if ((*b1) != (*b2)) {
|
|
return false;
|
|
}
|
|
++b1;
|
|
++b2;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool operator!=(const prevector<N, T, Size, Diff>& other) const {
|
|
return !(*this == other);
|
|
}
|
|
|
|
bool operator<(const prevector<N, T, Size, Diff>& other) const {
|
|
if (size() < other.size()) {
|
|
return true;
|
|
}
|
|
if (size() > other.size()) {
|
|
return false;
|
|
}
|
|
const_iterator b1 = begin();
|
|
const_iterator b2 = other.begin();
|
|
const_iterator e1 = end();
|
|
while (b1 != e1) {
|
|
if ((*b1) < (*b2)) {
|
|
return true;
|
|
}
|
|
if ((*b2) < (*b1)) {
|
|
return false;
|
|
}
|
|
++b1;
|
|
++b2;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
size_t allocated_memory() const {
|
|
if (is_direct()) {
|
|
return 0;
|
|
} else {
|
|
return ((size_t)(sizeof(T))) * _union.capacity;
|
|
}
|
|
}
|
|
};
|
|
#pragma pack(pop)
|
|
|
|
namespace Streaming {
|
|
ConstBuffer bufferFrom(const prevector<28, unsigned char> &v);
|
|
}
|
|
|
|
#endif
|