rippled
SHAMapDelta.cpp
1 //------------------------------------------------------------------------------
2 /*
3  This file is part of rippled: https://github.com/ripple/rippled
4  Copyright (c) 2012, 2013 Ripple Labs Inc.
5 
6  Permission to use, copy, modify, and/or distribute this software for any
7  purpose with or without fee is hereby granted, provided that the above
8  copyright notice and this permission notice appear in all copies.
9 
10  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  ANY SPECIAL , DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18 //==============================================================================
19 
20 #include <ripple/basics/contract.h>
21 #include <ripple/shamap/SHAMap.h>
22 
23 #include <array>
24 #include <stack>
25 #include <vector>
26 
27 namespace ripple {
28 
29 // This code is used to compare another node's transaction tree
30 // to our own. It returns a map containing all items that are different
31 // between two SHA maps. It is optimized not to descend down tree
32 // branches with the same branch hash. A limit can be passed so
33 // that we will abort early if a node sends a map to us that
34 // makes no sense at all. (And our sync algorithm will avoid
35 // synchronizing matching branches too.)
36 
37 bool
38 SHAMap::walkBranch(
39  SHAMapTreeNode* node,
40  boost::intrusive_ptr<SHAMapItem const> const& otherMapItem,
41  bool isFirstMap,
42  Delta& differences,
43  int& maxCount) const
44 {
45  // Walk a branch of a SHAMap that's matched by an empty branch or single
46  // item in the other map
47  std::stack<SHAMapTreeNode*, std::vector<SHAMapTreeNode*>> nodeStack;
48  nodeStack.push(node);
49 
50  bool emptyBranch = !otherMapItem;
51 
52  while (!nodeStack.empty())
53  {
54  node = nodeStack.top();
55  nodeStack.pop();
56 
57  if (node->isInner())
58  {
59  // This is an inner node, add all non-empty branches
60  auto inner = static_cast<SHAMapInnerNode*>(node);
61  for (int i = 0; i < 16; ++i)
62  if (!inner->isEmptyBranch(i))
63  nodeStack.push({descendThrow(inner, i)});
64  }
65  else
66  {
67  // This is a leaf node, process its item
68  auto item = static_cast<SHAMapLeafNode*>(node)->peekItem();
69 
70  if (emptyBranch || (item->key() != otherMapItem->key()))
71  {
72  // unmatched
73  if (isFirstMap)
74  differences.insert(
75  std::make_pair(item->key(), DeltaRef(item, nullptr)));
76  else
77  differences.insert(
78  std::make_pair(item->key(), DeltaRef(nullptr, item)));
79 
80  if (--maxCount <= 0)
81  return false;
82  }
83  else if (item->slice() != otherMapItem->slice())
84  {
85  // non-matching items with same tag
86  if (isFirstMap)
87  differences.insert(std::make_pair(
88  item->key(), DeltaRef(item, otherMapItem)));
89  else
90  differences.insert(std::make_pair(
91  item->key(), DeltaRef(otherMapItem, item)));
92 
93  if (--maxCount <= 0)
94  return false;
95 
96  emptyBranch = true;
97  }
98  else
99  {
100  // exact match
101  emptyBranch = true;
102  }
103  }
104  }
105 
106  if (!emptyBranch)
107  {
108  // otherMapItem was unmatched, must add
109  if (isFirstMap) // this is first map, so other item is from second
110  differences.insert(std::make_pair(
111  otherMapItem->key(), DeltaRef(nullptr, otherMapItem)));
112  else
113  differences.insert(std::make_pair(
114  otherMapItem->key(), DeltaRef(otherMapItem, nullptr)));
115 
116  if (--maxCount <= 0)
117  return false;
118  }
119 
120  return true;
121 }
122 
123 bool
124 SHAMap::compare(SHAMap const& otherMap, Delta& differences, int maxCount) const
125 {
126  // compare two hash trees, add up to maxCount differences to the difference
127  // table return value: true=complete table of differences given, false=too
128  // many differences throws on corrupt tables or missing nodes CAUTION:
129  // otherMap is not locked and must be immutable
130 
131  assert(isValid() && otherMap.isValid());
132 
133  if (getHash() == otherMap.getHash())
134  return true;
135 
136  using StackEntry = std::pair<SHAMapTreeNode*, SHAMapTreeNode*>;
137  std::stack<StackEntry, std::vector<StackEntry>>
138  nodeStack; // track nodes we've pushed
139 
140  nodeStack.push({root_.get(), otherMap.root_.get()});
141  while (!nodeStack.empty())
142  {
143  auto [ourNode, otherNode] = nodeStack.top();
144  nodeStack.pop();
145 
146  if (!ourNode || !otherNode)
147  {
148  assert(false);
149  Throw<SHAMapMissingNode>(type_, uint256());
150  }
151 
152  if (ourNode->isLeaf() && otherNode->isLeaf())
153  {
154  // two leaves
155  auto ours = static_cast<SHAMapLeafNode*>(ourNode);
156  auto other = static_cast<SHAMapLeafNode*>(otherNode);
157  if (ours->peekItem()->key() == other->peekItem()->key())
158  {
159  if (ours->peekItem()->slice() != other->peekItem()->slice())
160  {
161  differences.insert(std::make_pair(
162  ours->peekItem()->key(),
163  DeltaRef(ours->peekItem(), other->peekItem())));
164  if (--maxCount <= 0)
165  return false;
166  }
167  }
168  else
169  {
170  differences.insert(std::make_pair(
171  ours->peekItem()->key(),
172  DeltaRef(ours->peekItem(), nullptr)));
173  if (--maxCount <= 0)
174  return false;
175 
176  differences.insert(std::make_pair(
177  other->peekItem()->key(),
178  DeltaRef(nullptr, other->peekItem())));
179  if (--maxCount <= 0)
180  return false;
181  }
182  }
183  else if (ourNode->isInner() && otherNode->isLeaf())
184  {
185  auto ours = static_cast<SHAMapInnerNode*>(ourNode);
186  auto other = static_cast<SHAMapLeafNode*>(otherNode);
187  if (!walkBranch(
188  ours, other->peekItem(), true, differences, maxCount))
189  return false;
190  }
191  else if (ourNode->isLeaf() && otherNode->isInner())
192  {
193  auto ours = static_cast<SHAMapLeafNode*>(ourNode);
194  auto other = static_cast<SHAMapInnerNode*>(otherNode);
195  if (!otherMap.walkBranch(
196  other, ours->peekItem(), false, differences, maxCount))
197  return false;
198  }
199  else if (ourNode->isInner() && otherNode->isInner())
200  {
201  auto ours = static_cast<SHAMapInnerNode*>(ourNode);
202  auto other = static_cast<SHAMapInnerNode*>(otherNode);
203  for (int i = 0; i < 16; ++i)
204  if (ours->getChildHash(i) != other->getChildHash(i))
205  {
206  if (other->isEmptyBranch(i))
207  {
208  // We have a branch, the other tree does not
209  SHAMapTreeNode* iNode = descendThrow(ours, i);
210  if (!walkBranch(
211  iNode, nullptr, true, differences, maxCount))
212  return false;
213  }
214  else if (ours->isEmptyBranch(i))
215  {
216  // The other tree has a branch, we do not
217  SHAMapTreeNode* iNode = otherMap.descendThrow(other, i);
218  if (!otherMap.walkBranch(
219  iNode, nullptr, false, differences, maxCount))
220  return false;
221  }
222  else // The two trees have different non-empty branches
223  nodeStack.push(
224  {descendThrow(ours, i),
225  otherMap.descendThrow(other, i)});
226  }
227  }
228  else
229  assert(false);
230  }
231 
232  return true;
233 }
234 
235 void
236 SHAMap::walkMap(std::vector<SHAMapMissingNode>& missingNodes, int maxMissing)
237  const
238 {
239  if (!root_->isInner()) // root_ is only node, and we have it
240  return;
241 
242  using StackEntry = std::shared_ptr<SHAMapInnerNode>;
243  std::stack<StackEntry, std::vector<StackEntry>> nodeStack;
244 
245  nodeStack.push(std::static_pointer_cast<SHAMapInnerNode>(root_));
246 
247  while (!nodeStack.empty())
248  {
249  std::shared_ptr<SHAMapInnerNode> node = std::move(nodeStack.top());
250  nodeStack.pop();
251 
252  for (int i = 0; i < 16; ++i)
253  {
254  if (!node->isEmptyBranch(i))
255  {
256  std::shared_ptr<SHAMapTreeNode> nextNode =
257  descendNoStore(node, i);
258 
259  if (nextNode)
260  {
261  if (nextNode->isInner())
262  nodeStack.push(
263  std::static_pointer_cast<SHAMapInnerNode>(
264  nextNode));
265  }
266  else
267  {
268  missingNodes.emplace_back(type_, node->getChildHash(i));
269  if (--maxMissing <= 0)
270  return;
271  }
272  }
273  }
274  }
275 }
276 
277 bool
278 SHAMap::walkMapParallel(
279  std::vector<SHAMapMissingNode>& missingNodes,
280  int maxMissing) const
281 {
282  if (!root_->isInner()) // root_ is only node, and we have it
283  return false;
284 
285  using StackEntry = std::shared_ptr<SHAMapInnerNode>;
286  std::array<std::shared_ptr<SHAMapTreeNode>, 16> topChildren;
287  {
288  auto const& innerRoot =
289  std::static_pointer_cast<SHAMapInnerNode>(root_);
290  for (int i = 0; i < 16; ++i)
291  {
292  if (!innerRoot->isEmptyBranch(i))
293  topChildren[i] = descendNoStore(innerRoot, i);
294  }
295  }
296  std::vector<std::thread> workers;
297  workers.reserve(16);
298  std::vector<SHAMapMissingNode> exceptions;
299  exceptions.reserve(16);
300 
301  std::array<std::stack<StackEntry, std::vector<StackEntry>>, 16> nodeStacks;
302 
303  // This mutex is used inside the worker threads to protect `missingNodes`
304  // and `maxMissing` from race conditions
305  std::mutex m;
306 
307  for (int rootChildIndex = 0; rootChildIndex < 16; ++rootChildIndex)
308  {
309  auto const& child = topChildren[rootChildIndex];
310  if (!child || !child->isInner())
311  continue;
312 
313  nodeStacks[rootChildIndex].push(
314  std::static_pointer_cast<SHAMapInnerNode>(child));
315 
316  JLOG(journal_.debug()) << "starting worker " << rootChildIndex;
317  workers.push_back(std::thread(
318  [&m, &missingNodes, &maxMissing, &exceptions, this](
319  std::stack<StackEntry, std::vector<StackEntry>> nodeStack) {
320  try
321  {
322  while (!nodeStack.empty())
323  {
324  std::shared_ptr<SHAMapInnerNode> node =
325  std::move(nodeStack.top());
326  assert(node);
327  nodeStack.pop();
328 
329  for (int i = 0; i < 16; ++i)
330  {
331  if (node->isEmptyBranch(i))
332  continue;
333  std::shared_ptr<SHAMapTreeNode> nextNode =
334  descendNoStore(node, i);
335 
336  if (nextNode)
337  {
338  if (nextNode->isInner())
339  nodeStack.push(std::static_pointer_cast<
340  SHAMapInnerNode>(nextNode));
341  }
342  else
343  {
344  std::lock_guard l{m};
345  missingNodes.emplace_back(
346  type_, node->getChildHash(i));
347  if (--maxMissing <= 0)
348  return;
349  }
350  }
351  }
352  }
353  catch (SHAMapMissingNode const& e)
354  {
355  std::lock_guard l(m);
356  exceptions.push_back(e);
357  }
358  },
359  std::move(nodeStacks[rootChildIndex])));
360  }
361 
362  for (std::thread& worker : workers)
363  worker.join();
364 
365  std::lock_guard l(m);
366  if (exceptions.empty())
367  return true;
368  std::stringstream ss;
369  ss << "Exception(s) in ledger load: ";
370  for (auto const& e : exceptions)
371  ss << e.what() << ", ";
372  JLOG(journal_.error()) << ss.str();
373  return false;
374 }
375 
376 } // namespace ripple
ripple::SHAMap::isValid
bool isValid() const
Definition: SHAMap.h:625
std::shared_ptr
STL class.
ripple::SHAMap::getHash
SHAMapHash getHash() const
Definition: SHAMap.cpp:852
ripple::SHAMap::peekItem
boost::intrusive_ptr< SHAMapItem const > const & peekItem(uint256 const &id) const
Definition: SHAMap.cpp:592
std::pair
std::vector::reserve
T reserve(T... args)
vector
stack
std::stringstream
STL class.
std::lock_guard
STL class.
ripple::SHAMapTreeNode::isInner
virtual bool isInner() const =0
Determines if this is an inner node.
ripple::SHAMapLeafNode
Definition: SHAMapLeafNode.h:32
ripple::SHAMapMissingNode
Definition: SHAMapMissingNode.h:55
std::vector::push_back
T push_back(T... args)
ripple::base_uint< 256 >
ripple::SHAMap::DeltaRef
std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > > DeltaRef
Definition: SHAMap.h:373
std::thread
STL class.
ripple::SHAMapInnerNode
Definition: SHAMapInnerNode.h:41
ripple::SHAMap
A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
Definition: SHAMap.h:95
std::stack::pop
T pop(T... args)
std::stack::top
T top(T... args)
ripple::SHAMapTreeNode
Definition: SHAMapTreeNode.h:53
array
ripple::SHAMap::descendThrow
SHAMapTreeNode * descendThrow(SHAMapInnerNode *, int branch) const
Definition: SHAMap.cpp:289
ripple::SHAMap::walkBranch
bool walkBranch(SHAMapTreeNode *node, boost::intrusive_ptr< SHAMapItem const > const &otherMapItem, bool isFirstMap, Delta &differences, int &maxCount) const
Definition: SHAMapDelta.cpp:38
std::map
STL class.
std::vector::emplace_back
T emplace_back(T... args)
ripple
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition: RCLCensorshipDetector.h:29
std::map::insert
T insert(T... args)
std::stack::empty
T empty(T... args)
std::stack::push
T push(T... args)
std::mutex
STL class.
std::stringstream::str
T str(T... args)
std::make_pair
T make_pair(T... args)
std::thread::join
T join(T... args)
ripple::SHAMap::root_
std::shared_ptr< SHAMapTreeNode > root_
Definition: SHAMap.h:107
Generated by   doxygen 1.8.17