xrpld
Loading...
Searching...
No Matches
SHAMapInnerNode.cpp
1#include <xrpl/shamap/SHAMapInnerNode.h>
2
3#include <xrpl/basics/IntrusivePointer.h> // IWYU pragma: keep
4#include <xrpl/basics/IntrusivePointer.ipp> // IWYU pragma: keep
5#include <xrpl/basics/SHAMapHash.h>
6#include <xrpl/basics/Slice.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/basics/contract.h>
9#include <xrpl/basics/spinlock.h>
10#include <xrpl/beast/utility/instrumentation.h>
11#include <xrpl/protocol/HashPrefix.h>
12#include <xrpl/protocol/Serializer.h>
13#include <xrpl/protocol/digest.h>
14#include <xrpl/shamap/SHAMapNodeID.h>
15#include <xrpl/shamap/SHAMapTreeNode.h>
16#include <xrpl/shamap/detail/TaggedPointer.h>
17#include <xrpl/shamap/detail/TaggedPointer.ipp>
18
19#include <atomic>
20#include <cstddef>
21#include <cstdint>
22#include <mutex>
23#include <optional>
24#include <stdexcept>
25#include <string>
26#include <tuple>
27#include <utility>
28
29namespace xrpl {
30
35
37
38void
40{
41 SHAMapTreeNodePtr* children = nullptr;
42 // structured bindings can't be captured in c++ 17; use tie instead
43 std::tie(std::ignore, std::ignore, children) = hashesAndChildren_.getHashesAndChildren();
44 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) { children[indexNum].reset(); });
45}
46
47template <class F>
48void
53
54template <class F>
55void
57{
58 hashesAndChildren_.iterNonEmptyChildIndexes(isBranch_, std::forward<F>(f));
59}
60
61void
66
68SHAMapInnerNode::getChildIndex(unsigned int i) const
69{
70 return hashesAndChildren_.getChildIndex(isBranch_, i);
71}
72
75{
76 auto const branchCount = getBranchCount();
77 auto const thisIsSparse = !hashesAndChildren_.isDense();
78 auto p = intr_ptr::makeShared<SHAMapInnerNode>(cowid, branchCount);
79 p->hash_ = hash_;
80 p->isBranch_ = isBranch_;
81 // Relaxed, as everywhere. p is not reachable by another thread until this returns.
82 p->fullBelowGen_.store(
83 fullBelowGen_.load(std::memory_order_relaxed), std::memory_order_relaxed);
84 SHAMapHash* cloneHashes = nullptr;
85 SHAMapHash* thisHashes = nullptr;
86 SHAMapTreeNodePtr* cloneChildren = nullptr;
87 SHAMapTreeNodePtr* thisChildren = nullptr;
88 // structured bindings can't be captured in c++ 17; use tie instead
89 std::tie(std::ignore, cloneHashes, cloneChildren) =
90 p->hashesAndChildren_.getHashesAndChildren();
91 std::tie(std::ignore, thisHashes, thisChildren) = hashesAndChildren_.getHashesAndChildren();
92
93 if (thisIsSparse)
94 {
95 auto cloneChildIndex = 0u;
96 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
97 cloneHashes[cloneChildIndex++] = thisHashes[indexNum];
98 });
99 }
100 else
101 {
103 [&](auto branchNum, auto indexNum) { cloneHashes[branchNum] = thisHashes[indexNum]; });
104 }
105
106 Spinlock sl(lock_);
107 std::scoped_lock const lock(sl);
108
109 if (thisIsSparse)
110 {
111 auto cloneChildIndex = 0u;
112 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
113 cloneChildren[cloneChildIndex++] = thisChildren[indexNum];
114 });
115 }
116 else
117 {
118 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
119 cloneChildren[branchNum] = thisChildren[indexNum];
120 });
121 }
122
123 return p;
124}
125
127SHAMapInnerNode::makeFullInner(Slice data, SHAMapHash const& hash, bool hashValid)
128{
129 // A full inner node is serialized as 16 256-bit hashes, back to back:
130 if (data.size() != kBranchFactor * UInt256::kBytes)
131 Throw<std::runtime_error>("Invalid FI node");
132
134
135 SerialIter si(data);
136
137 auto hashes = ret->hashesAndChildren_.getHashes();
138
139 for (auto i = 0u; i < kBranchFactor; ++i)
140 {
141 hashes[i].asUInt256() = si.getBitString<256>();
142
143 if (hashes[i].isNonZero())
144 ret->isBranch_ |= (1u << i);
145 }
146
147 ret->resizeChildArrays(ret->getBranchCount());
148
149 if (hashValid)
150 {
151 ret->hash_ = hash;
152 }
153 else
154 {
155 ret->updateHash();
156 }
157
158 return ret;
159}
160
163{
164 // A compressed inner node is serialized as a series of 33 byte chunks,
165 // representing a one byte "position" and a 256-bit hash:
166 static constexpr std::size_t kChunkSize = UInt256::kBytes + 1;
167
168 if (auto const s = data.size(); (s % kChunkSize != 0) || (s > kChunkSize * kBranchFactor))
169 Throw<std::runtime_error>("Invalid CI node");
170
171 SerialIter si(data);
172
174
175 auto hashes = ret->hashesAndChildren_.getHashes();
176
177 while (!si.empty())
178 {
179 auto const hash = si.getBitString<256>();
180 auto const pos = si.get8();
181
182 if (pos >= kBranchFactor)
183 Throw<std::runtime_error>("invalid CI node");
184
185 hashes[pos].asUInt256() = hash;
186
187 if (hashes[pos].isNonZero())
188 ret->isBranch_ |= (1u << pos);
189 }
190
191 ret->resizeChildArrays(ret->getBranchCount());
192 ret->updateHash();
193 return ret;
194}
195
196void
198{
199 UInt256 nh;
200 if (isBranch_ != 0)
201 {
203 using beast::hash_append;
205 iterChildren([&](SHAMapHash const& hh) { hash_append(h, hh); });
206 nh = static_cast<Sha512HalfHasher::result_type>(h);
207 }
208 hash_ = SHAMapHash{nh};
209}
210
211void
213{
214 SHAMapHash* hashes = nullptr;
215 SHAMapTreeNodePtr* children = nullptr;
216 // structured bindings can't be captured in c++ 17; use tie instead
217 std::tie(std::ignore, hashes, children) = hashesAndChildren_.getHashesAndChildren();
218 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
219 if (auto p = children[indexNum].get())
220 hashes[indexNum] = p->getHash();
221 });
222 updateHash();
223}
224
225void
227{
228 XRPL_ASSERT(!isEmpty(), "xrpl::SHAMapInnerNode::serializeForWire : is non-empty");
229
230 // If the node is sparse, then only send non-empty branches:
231 if (getBranchCount() < 12)
232 {
233 // compressed node
234 auto hashes = hashesAndChildren_.getHashes();
235 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
236 s.addBitString(hashes[indexNum].asUInt256());
237 s.add8(branchNum);
238 });
240 }
241 else
242 {
243 iterChildren([&](SHAMapHash const& hh) { s.addBitString(hh.asUInt256()); });
245 }
246}
247
248void
250{
251 XRPL_ASSERT(!isEmpty(), "xrpl::SHAMapInnerNode::serializeWithPrefix : is non-empty");
252
254 iterChildren([&](SHAMapHash const& hh) { s.addBitString(hh.asUInt256()); });
255}
256
259{
261 auto hashes = hashesAndChildren_.getHashes();
262 iterNonEmptyChildIndexes([&](auto branchNum, auto indexNum) {
263 ret += "\nb";
264 ret += std::to_string(branchNum);
265 ret += " = ";
266 ret += to_string(hashes[indexNum]);
267 });
268 return ret;
269}
270
271// We are modifying an inner node
272void
274{
275 XRPL_ASSERT(branch < kBranchFactor, "xrpl::SHAMapInnerNode::setChild : valid branch input");
276 XRPL_ASSERT(cowid_, "xrpl::SHAMapInnerNode::setChild : nonzero cowid");
277 XRPL_ASSERT(child.get() != this, "xrpl::SHAMapInnerNode::setChild : valid child input");
278
279 auto const dstIsBranch = [&] {
280 if (child)
281 {
282 return isBranch_ | (1u << branch);
283 }
284
285 return isBranch_ & ~(1u << branch);
286 }();
287
288 auto const dstToAllocate = popcnt16(dstIsBranch);
289 // change hashesAndChildren to remove the element, or make room for the
290 // added element, if necessary
292 TaggedPointer(std::move(hashesAndChildren_), isBranch_, dstIsBranch, dstToAllocate);
293
294 isBranch_ = dstIsBranch;
295
296 if (child)
297 {
298 // NOLINTNEXTLINE(bugprone-unchecked-optional-access) isBranch_ set above
299 auto const childIndex = *getChildIndex(branch);
300 auto [_, hashes, children] = hashesAndChildren_.getHashesAndChildren();
301 hashes[childIndex].zero();
302 children[childIndex] = std::move(child);
303 }
304
305 hash_.zero();
306
307 XRPL_ASSERT(
308 getBranchCount() <= hashesAndChildren_.capacity(),
309 "xrpl::SHAMapInnerNode::setChild : maximum branch count");
310}
311
312// finished modifying, now make shareable
313void
314SHAMapInnerNode::shareChild(unsigned int branch, SHAMapTreeNodePtr const& child)
315{
316 XRPL_ASSERT(branch < kBranchFactor, "xrpl::SHAMapInnerNode::shareChild : valid branch input");
317 XRPL_ASSERT(cowid_, "xrpl::SHAMapInnerNode::shareChild : nonzero cowid");
318 XRPL_ASSERT(child, "xrpl::SHAMapInnerNode::shareChild : non-null child input");
319 XRPL_ASSERT(child.get() != this, "xrpl::SHAMapInnerNode::shareChild : valid child input");
320
321 XRPL_ASSERT(
322 !isEmptyBranch(branch), "xrpl::SHAMapInnerNode::shareChild : non-empty branch input");
323 // NOLINTNEXTLINE(bugprone-unchecked-optional-access) assert above
324 hashesAndChildren_.getChildren()[*getChildIndex(branch)] = child;
325}
326
329{
330 XRPL_ASSERT(
331 branch < kBranchFactor, "xrpl::SHAMapInnerNode::getChildPointer : valid branch input");
332 XRPL_ASSERT(
333 !isEmptyBranch(branch), "xrpl::SHAMapInnerNode::getChildPointer : non-empty branch input");
334
335 auto const index =
336 *getChildIndex(branch); // NOLINT(bugprone-unchecked-optional-access) assert above
337
338 PackedSpinlock sl(lock_, index);
339 std::scoped_lock const lock(sl);
340 return hashesAndChildren_.getChildren()[index].get();
341}
342
344SHAMapInnerNode::getChild(unsigned int branch)
345{
346 XRPL_ASSERT(branch < kBranchFactor, "xrpl::SHAMapInnerNode::getChild : valid branch input");
347 XRPL_ASSERT(!isEmptyBranch(branch), "xrpl::SHAMapInnerNode::getChild : non-empty branch input");
348
349 auto const index =
350 *getChildIndex(branch); // NOLINT(bugprone-unchecked-optional-access) assert above
351
352 PackedSpinlock sl(lock_, index);
353 std::scoped_lock const lock(sl);
354 return hashesAndChildren_.getChildren()[index];
355}
356
357SHAMapHash const&
358SHAMapInnerNode::getChildHash(unsigned int branch) const
359{
360 XRPL_ASSERT(branch < kBranchFactor, "xrpl::SHAMapInnerNode::getChildHash : valid branch input");
361 if (auto const i = getChildIndex(branch))
362 return hashesAndChildren_.getHashes()[*i];
363
364 return kZeroShaMapHash;
365}
366
369{
370 XRPL_ASSERT(
371 branch < kBranchFactor, "xrpl::SHAMapInnerNode::canonicalizeChild : valid branch input");
372 XRPL_ASSERT(node != nullptr, "xrpl::SHAMapInnerNode::canonicalizeChild : valid node input");
373 XRPL_ASSERT(
374 !isEmptyBranch(branch),
375 "xrpl::SHAMapInnerNode::canonicalizeChild : non-empty branch input");
376 auto const childIndex =
377 *getChildIndex(branch); // NOLINT(bugprone-unchecked-optional-access) assert above
378 auto [_, hashes, children] = hashesAndChildren_.getHashesAndChildren();
379 XRPL_ASSERT(
380 node->getHash() == hashes[childIndex],
381 "xrpl::SHAMapInnerNode::canonicalizeChild : node and branch inputs "
382 "hash do match");
383
384 PackedSpinlock sl(lock_, childIndex);
385 std::scoped_lock const lock(sl);
386
387 if (children[childIndex])
388 {
389 // There is already a node hooked up, return it
390 node = children[childIndex];
391 }
392 else
393 {
394 // Hook this node up
395 children[childIndex] = node;
396 }
397 return node;
398}
399
400void
402{
403 [[maybe_unused]] unsigned count = 0;
404 auto [numAllocated, hashes, children] = hashesAndChildren_.getHashesAndChildren();
405
406 if (numAllocated != kBranchFactor)
407 {
408 auto const branchCount = getBranchCount();
409 for (auto i = 0u; i < branchCount; ++i)
410 {
411 XRPL_ASSERT(
412 hashes[i].isNonZero(),
413 "xrpl::SHAMapInnerNode::invariants : nonzero hash in branch");
414 if (children[i] != nullptr)
415 children[i]->invariants();
416 ++count;
417 }
418 }
419 else
420 {
421 for (auto i = 0u; i < kBranchFactor; ++i)
422 {
423 if (hashes[i].isNonZero())
424 {
425 XRPL_ASSERT(
426 (isBranch_ & (1u << i)),
427 "xrpl::SHAMapInnerNode::invariants : valid branch when "
428 "nonzero hash");
429 if (children[i] != nullptr)
430 children[i]->invariants();
431 ++count;
432 }
433 else
434 {
435 XRPL_ASSERT(
436 (isBranch_ & (1u << i)) == 0u,
437 "xrpl::SHAMapInnerNode::invariants : valid branch when "
438 "zero hash");
439 }
440 }
441 }
442
443 if (!isRoot)
444 {
445 XRPL_ASSERT(hash_.isNonZero(), "xrpl::SHAMapInnerNode::invariants : nonzero hash");
446 XRPL_ASSERT(count >= 1, "xrpl::SHAMapInnerNode::invariants : minimum count");
447 }
448 XRPL_ASSERT(
449 (count == 0) ? hash_.isZero() : hash_.isNonZero(),
450 "xrpl::SHAMapInnerNode::invariants : hash and count do match");
451}
452
453} // namespace xrpl
static constexpr std::size_t kBytes
Definition base_uint.h:100
Classes to handle arrays of spinlocks packed into a single atomic integer:
Definition spinlock.h:78
UInt256 const & asUInt256() const
Definition SHAMapHash.h:26
std::optional< unsigned int > getChildIndex(unsigned int i) const
Get the child's index inside the hashes or children array (stored in hashesAndChildren_.
void serializeWithPrefix(Serializer &) const override
Serialize the node in a format appropriate for hashing.
void updateHash() override
Recalculate the hash of this node.
TaggedPointer hashesAndChildren_
Opaque type that contains the hashes array (array of type SHAMapHash) and the children array (array o...
SHAMapHash const & getChildHash(unsigned int branch) const
unsigned int getBranchCount() const
static constexpr unsigned int kBranchFactor
Each inner node has 16 children (the 'radix tree' part of the map).
~SHAMapInnerNode() override
void updateHashDeep()
Recalculate the hash of all children and this node.
void iterNonEmptyChildIndexes(F &&f) const
Call the f callback for all non-empty branches.
SHAMapTreeNodePtr clone(std::uint32_t cowid) const override
Make a copy of this node, setting the owner.
void shareChild(unsigned int branch, SHAMapTreeNodePtr const &child)
static SHAMapTreeNodePtr makeCompressedInner(Slice data)
std::string getString(SHAMapNodeID const &) const override
SHAMapInnerNode(std::uint32_t cowid, std::uint8_t numAllocatedChildren=2)
void iterChildren(F &&f) const
Call the f callback for all 16 (branchFactor) branches - even if the branch is empty.
void resizeChildArrays(std::uint8_t toAllocate)
Convert arrays stored in hashesAndChildren_ so they can store the requested number of children.
void invariants(bool isRoot=false) const override
std::atomic< std::uint32_t > fullBelowGen_
Written from more than one thread, since canonicalization shares a node between maps and a walk can r...
void setChild(unsigned int branch, SHAMapTreeNodePtr child)
void partialDestructor() override
SHAMapTreeNodePtr getChild(unsigned int branch)
std::atomic< std::uint16_t > lock_
A bitlock for the children of this node, with one bit per child.
SHAMapTreeNode * getChildPointer(unsigned int branch)
void serializeForWire(Serializer &) const override
Serialize the node in a format appropriate for sending over the wire.
SHAMapTreeNodePtr canonicalizeChild(unsigned int branch, SHAMapTreeNodePtr node)
static SHAMapTreeNodePtr makeFullInner(Slice data, SHAMapHash const &hash, bool hashValid)
bool isEmptyBranch(unsigned int branch) const
Identifies a node inside a SHAMap.
std::uint32_t cowid_
Determines the owning SHAMap, if any.
SHAMapTreeNode(std::uint32_t cowid) noexcept
Construct a node.
virtual std::string getString(SHAMapNodeID const &) const
BaseUInt< Bits, Tag > getBitString()
Definition Serializer.h:597
bool empty() const noexcept
Definition Serializer.h:499
int addBitString(BaseUInt< Bits, Tag > const &v)
Definition Serializer.h:202
int add8(unsigned char byteValue)
void reset()
Set the pointer to null, decrement the strong count, and run the appropriate release action.
An immutable linear range of bytes.
Definition Slice.h:28
A spinlock implemented on top of an atomic integer.
Definition spinlock.h:155
TaggedPointer is a combination of a pointer and a mask stored in the lowest two bits.
T forward(T... args)
std::uint32_t cowid() const
Returns the SHAMap that owns this node.
void hash_append(Hasher &h, T const &t) noexcept
Logically concatenate input data to a Hasher.
SharedPtr< T > makeShared(A &&... args)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
T get(Section const &section, std::string const &name, T const &defaultValue=T{})
Retrieve a key/value pair from a section.
static constexpr unsigned char const kWireTypeCompressedInner
std::string to_string(BaseUInt< Bits, Tag > const &a)
Definition base_uint.h:658
BaseUInt< 256 > UInt256
Definition base_uint.h:581
unsigned int popcnt16(std::uint16_t a)
detail::BasicSha512HalfHasher< false > Sha512HalfHasher
Definition digest.h:203
void hash_append(Hasher &h, Slice const &v)
Definition Slice.h:194
@ InnerNode
inner node in V1 tree
Definition HashPrefix.h:54
static constexpr unsigned char const kWireTypeInner
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)
Definition contract.h:52
T tie(T... args)
T to_string(T... args)