Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_TEST_UTIL_CLUSTER_LINEARIZE_H
6 : : #define BITCOIN_TEST_UTIL_CLUSTER_LINEARIZE_H
7 : :
8 : : #include <cluster_linearize.h>
9 : : #include <serialize.h>
10 : : #include <span.h>
11 : : #include <streams.h>
12 : : #include <util/bitset.h>
13 : : #include <util/feefrac.h>
14 : :
15 : : #include <cstdint>
16 : : #include <numeric>
17 : : #include <utility>
18 : : #include <vector>
19 : :
20 : : namespace cluster_linearize {
21 : :
22 : : using TestBitSet = BitSet<32>;
23 : :
24 : : /** A formatter for a bespoke serialization for acyclic DepGraph objects.
25 : : *
26 : : * The serialization format outputs information about transactions in a topological order (parents
27 : : * before children), together with position information so transactions can be moved back to their
28 : : * correct position on deserialization.
29 : : *
30 : : * - For each transaction t in the DepGraph (in some topological order);
31 : : * - The size: VARINT(t.size), which cannot be 0.
32 : : * - The fee: VARINT(SignedToUnsigned(t.fee)), see below for SignedToUnsigned.
33 : : * - For each direct dependency:
34 : : * - VARINT(skip)
35 : : * - The position of t in the cluster: VARINT(skip)
36 : : * - The end of the graph: VARINT(0)
37 : : *
38 : : * The list of skip values encodes the dependencies of t, as well as its position in the cluster.
39 : : * Each skip value is the number of possibilities that were available, but were not taken. These
40 : : * possibilities are, in order:
41 : : * - For each previous transaction in the graph, in reverse serialization order, whether it is a
42 : : * direct parent of t (but excluding transactions which are already implied to be dependencies
43 : : * by parent relations that were serialized before it).
44 : : * - The various insertion positions in the cluster, from the very end of the cluster, to the
45 : : * front.
46 : : * - The appending of 1, 2, 3, ... holes at the end of the cluster, followed by appending the new
47 : : * transaction.
48 : : *
49 : : * Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,_,G,E,_,D
50 : : * (where _ represent holes; unused positions within the DepGraph) but serialized in order
51 : : * A,B,C,D,E,F,G, because that happens to be a topological ordering. By the time G gets serialized,
52 : : * what has been serialized already represents the cluster F,A,C,B,_,E,_,D (in that order). G has B
53 : : * and E as direct parents, and E depends on C.
54 : : *
55 : : * In this case, the possibilities are, in order:
56 : : * - [ ] the dependency G->F
57 : : * - [X] the dependency G->E
58 : : * - [ ] the dependency G->D
59 : : * - [X] the dependency G->B
60 : : * - [ ] the dependency G->A
61 : : * - [ ] put G at the end of the cluster
62 : : * - [ ] put G before D
63 : : * - [ ] put G before the hole before D
64 : : * - [X] put G before E
65 : : * - [ ] put G before the hole before E
66 : : * - [ ] put G before B
67 : : * - [ ] put G before C
68 : : * - [ ] put G before A
69 : : * - [ ] put G before F
70 : : * - [ ] add 1 hole at the end of the cluster, followed by G
71 : : * - [ ] add 2 holes at the end of the cluster, followed by G
72 : : * - [ ] add ...
73 : : *
74 : : * The skip values in this case are 1 (G->F), 1 (G->D), 4 (G->A, G at end, G before D, G before
75 : : * hole). No skip after 4 is needed (or permitted), because there can only be one position for G.
76 : : * Also note that G->C is not included in the list of possibilities, as it is implied by the
77 : : * included G->E and E->C that came before it. On deserialization, if the last skip value was 8 or
78 : : * larger (putting G before the beginning of the cluster), it is interpreted as wrapping around
79 : : * back to the end.
80 : : *
81 : : *
82 : : * Rationale:
83 : : * - Why VARINTs? They are flexible enough to represent large numbers where needed, but more
84 : : * compact for smaller numbers. The serialization format is designed so that simple structures
85 : : * involve smaller numbers, so smaller size maps to simpler graphs.
86 : : * - Why use SignedToUnsigned? It results in small unsigned values for signed values with small
87 : : * absolute value. This way we can encode negative fees in graphs, but still let small negative
88 : : * numbers have small encodings.
89 : : * - Why are the parents emitted in reverse order compared to the transactions themselves? This
90 : : * naturally lets us skip parents-of-parents, as they will be reflected as implied dependencies.
91 : : * - Why encode skip values and not a bitmask to convey the list positions? It turns out that the
92 : : * most complex graphs (in terms of linearization complexity) are ones with ~1 dependency per
93 : : * transaction. The current encoding uses ~1 byte per transaction for dependencies in this case,
94 : : * while a bitmask would require ~N/2 bits per transaction.
95 : : */
96 : :
97 : : struct DepGraphFormatter
98 : : {
99 : : /** Convert x>=0 to 2x (even), x<0 to -2x-1 (odd). */
100 : 25055 : static uint64_t SignedToUnsigned(int64_t x) noexcept
101 : : {
102 : 25055 : if (x < 0) {
103 : 5131 : return 2 * uint64_t(-(x + 1)) + 1;
104 : : } else {
105 : 19924 : return 2 * uint64_t(x);
106 : : }
107 : : }
108 : :
109 : : /** Convert even x to x/2 (>=0), odd x to -(x/2)-1 (<0). */
110 : 75105 : static int64_t UnsignedToSigned(uint64_t x) noexcept
111 : : {
112 : 75105 : if (x & 1) {
113 : 15384 : return -int64_t(x / 2) - 1;
114 : : } else {
115 : 59721 : return int64_t(x / 2);
116 : : }
117 : : }
118 : :
119 : : template <typename Stream, typename SetType>
120 : 945 : static void Ser(Stream& s, const DepGraph<SetType>& depgraph)
121 : : {
122 : : /** Construct a topological order to serialize the transactions in. */
123 [ + - ]: 945 : std::vector<DepGraphIndex> topo_order;
124 [ + - ]: 945 : topo_order.reserve(depgraph.TxCount());
125 [ + + + + : 26364 : for (auto i : depgraph.Positions()) topo_order.push_back(i);
+ + ]
126 : 132330 : std::sort(topo_order.begin(), topo_order.end(), [&](DepGraphIndex a, DepGraphIndex b) {
127 [ + + + + : 262770 : auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count();
+ + + + +
+ + + + +
+ + + + +
+ ]
128 [ + + + + : 131385 : if (anc_a != anc_b) return anc_a < anc_b;
+ + + + +
+ ]
129 : 67190 : return a < b;
130 : : });
131 : :
132 : : /** Which positions (incl. holes) the deserializer already knows when it has deserialized
133 : : * what has been serialized here so far. */
134 : 945 : SetType done;
135 : :
136 : : // Loop over the transactions in topological order.
137 [ - + + + ]: 26000 : for (DepGraphIndex topo_idx = 0; topo_idx < topo_order.size(); ++topo_idx) {
138 : : /** Which depgraph index we are currently writing. */
139 [ + - ]: 25055 : DepGraphIndex idx = topo_order[topo_idx];
140 : : // Write size, which must be larger than 0.
141 [ + - + + ]: 50110 : s << VARINT_MODE(depgraph.FeeRate(idx).size, VarIntMode::NONNEGATIVE_SIGNED);
142 : : // Write fee, encoded as an unsigned varint (odd=negative, even=non-negative).
143 [ + + + - ]: 50110 : s << VARINT(SignedToUnsigned(depgraph.FeeRate(idx).fee));
144 : : // Write dependency information.
145 : 25055 : SetType written_parents;
146 : 25055 : uint64_t diff = 0; //!< How many potential parent/child relations we have skipped over.
147 [ + + ]: 474368 : for (DepGraphIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) {
148 : : /** Which depgraph index we are currently considering as parent of idx. */
149 [ + + ]: 449313 : DepGraphIndex dep_idx = topo_order[topo_idx - 1 - dep_dist];
150 : : // Ignore transactions which are already known to be ancestors.
151 [ + + ]: 742014 : if (depgraph.Descendants(dep_idx).Overlaps(written_parents)) continue;
152 [ + + ]: 387827 : if (depgraph.Ancestors(idx)[dep_idx]) {
153 : : // When an actual parent is encountered, encode how many non-parents were skipped
154 : : // before it.
155 [ + - ]: 74876 : s << VARINT(diff);
156 : 74876 : diff = 0;
157 : 74876 : written_parents.Set(dep_idx);
158 : : } else {
159 : : // When a non-parent is encountered, increment the skip counter.
160 : 312951 : ++diff;
161 : : }
162 : : }
163 : : // Write position information.
164 [ + + ]: 25055 : auto add_holes = SetType::Fill(idx) - done - depgraph.Positions();
165 [ + + ]: 25055 : if (add_holes.None()) {
166 : : // The new transaction is to be inserted N positions back from the end of the
167 : : // cluster. Emit N to indicate that that many insertion choices are skipped.
168 [ + - ]: 25024 : auto skips = (done - SetType::Fill(idx)).Count();
169 [ + - ]: 34104 : s << VARINT(diff + skips);
170 : : } else {
171 : : // The new transaction is to be appended at the end of the cluster, after N holes.
172 : : // Emit current_cluster_size + N, to indicate all insertion choices are skipped,
173 : : // plus N possibilities for the number of holes.
174 [ + - + + ]: 140 : s << VARINT(diff + done.Count() + add_holes.Count());
175 : 15990 : done |= add_holes;
176 : : }
177 : 25055 : done.Set(idx);
178 : : }
179 : :
180 : : // Output a final 0 to denote the end of the graph.
181 [ + - ]: 1890 : s << uint8_t{0};
182 : 945 : }
183 : :
184 : : template <typename Stream, typename SetType>
185 : 2814 : void Unser(Stream& s, DepGraph<SetType>& depgraph)
186 : : {
187 : : /** The dependency graph which we deserialize into first, with transactions in
188 : : * topological serialization order, not original cluster order. */
189 : 2814 : DepGraph<SetType> topo_depgraph;
190 : : /** Mapping from serialization order to cluster order, used later to reconstruct the
191 : : * cluster order. */
192 : 2814 : std::vector<DepGraphIndex> reordering;
193 : : /** How big the entries vector in the reconstructed depgraph will be (including holes). */
194 : 2814 : DepGraphIndex total_size{0};
195 : :
196 : : // Read transactions in topological order.
197 : : while (true) {
198 : 77919 : FeeFrac new_feerate; //!< The new transaction's fee and size.
199 : 77919 : SetType new_ancestors; //!< The new transaction's ancestors (excluding itself).
200 : 77919 : uint64_t diff{0}; //!< How many potential parents/insertions we have to skip.
201 [ + + ]: 77919 : bool read_error{false};
202 : : try {
203 : : // Read size. Size 0 signifies the end of the DepGraph.
204 : : int32_t size;
205 [ + + ]: 77919 : s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED);
206 : 76981 : size &= 0x3FFFFF; // Enough for size up to 4M.
207 : : static_assert(0x3FFFFF >= 4000000);
208 [ + + + - ]: 76981 : if (size == 0 || topo_depgraph.TxCount() == SetType::Size()) break;
209 : : // Read fee, encoded as an unsigned varint (odd=negative, even=non-negative).
210 : : uint64_t coded_fee;
211 [ + - ]: 75105 : s >> VARINT(coded_fee);
212 : 75105 : coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC.
213 : : static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000);
214 [ + + - + ]: 150210 : new_feerate = {UnsignedToSigned(coded_fee), size};
215 : : // Read dependency information.
216 [ + - ]: 75105 : auto topo_idx = reordering.size();
217 [ + - ]: 75105 : s >> VARINT(diff);
218 [ + + ]: 1422954 : for (DepGraphIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) {
219 : : /** Which topo_depgraph index we are currently considering as parent of topo_idx. */
220 [ + + ]: 1347849 : DepGraphIndex dep_topo_idx = topo_idx - 1 - dep_dist;
221 : : // Ignore transactions which are already known ancestors of topo_idx.
222 [ + + ]: 1347849 : if (new_ancestors[dep_topo_idx]) continue;
223 [ + + ]: 1163406 : if (diff == 0) {
224 : : // When the skip counter has reached 0, add an actual dependency.
225 [ + - ]: 370059 : new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx);
226 : : // And read the number of skips after it.
227 [ + - ]: 1572435 : s >> VARINT(diff);
228 : : } else {
229 : : // Otherwise, dep_topo_idx is not a parent. Decrement and continue.
230 : 938820 : --diff;
231 : : }
232 : : }
233 [ - + ]: 938 : } catch (const std::ios_base::failure&) {
234 : : // Continue even if a read error was encountered.
235 : 938 : read_error = true;
236 : : }
237 : : // Construct a new transaction whenever we made it past the new_feerate construction.
238 [ + + ]: 76043 : if (new_feerate.IsEmpty()) break;
239 [ - + ]: 75105 : assert(reordering.size() < SetType::Size());
240 : 75105 : auto topo_idx = topo_depgraph.AddTransaction(new_feerate);
241 : 75105 : topo_depgraph.AddDependencies(new_ancestors, topo_idx);
242 [ + - ]: 75105 : if (total_size < SetType::Size()) {
243 : : // Normal case.
244 : 75105 : diff %= SetType::Size();
245 [ + + ]: 75105 : if (diff <= total_size) {
246 : : // Insert the new transaction at distance diff back from the end.
247 [ + + ]: 1422132 : for (auto& pos : reordering) {
248 : 1347111 : pos += (pos >= total_size - diff);
249 : : }
250 [ + - ]: 75021 : reordering.push_back(total_size++ - diff);
251 : : } else {
252 : : // Append diff - total_size holes at the end, plus the new transaction.
253 : 84 : total_size = diff;
254 [ + - ]: 84 : reordering.push_back(total_size++);
255 : : }
256 : : } else {
257 : : // In case total_size == SetType::Size, it is not possible to insert the new
258 : : // transaction without exceeding SetType's size. Instead, interpret diff as an
259 : : // index into the holes, and overwrite a position there. This branch is never used
260 : : // when deserializing the output of the serializer, but gives meaning to otherwise
261 : : // invalid input.
262 : 0 : diff %= (SetType::Size() - reordering.size());
263 : 0 : SetType holes = SetType::Fill(SetType::Size());
264 [ # # ]: 0 : for (auto pos : reordering) holes.Reset(pos);
265 [ # # # # ]: 0 : for (auto pos : holes) {
266 [ # # ]: 0 : if (diff == 0) {
267 [ # # ]: 0 : reordering.push_back(pos);
268 : : break;
269 : : }
270 : 0 : --diff;
271 : : }
272 : : }
273 : : // Stop if a read error was encountered during deserialization.
274 [ + - ]: 75105 : if (read_error) break;
275 : : }
276 : :
277 : : // Construct the original cluster order depgraph.
278 : 2814 : depgraph = DepGraph(topo_depgraph, reordering, total_size);
279 : 2814 : }
280 : : };
281 : :
282 : : /** Perform a sanity/consistency check on a DepGraph. */
283 : : template<typename SetType>
284 : 938 : void SanityCheck(const DepGraph<SetType>& depgraph)
285 : : {
286 : : // Verify Positions and PositionRange consistency.
287 : 938 : DepGraphIndex num_positions{0};
288 [ + + ]: 938 : DepGraphIndex position_range{0};
289 [ + + + + ]: 26331 : for (DepGraphIndex i : depgraph.Positions()) {
290 : 25035 : ++num_positions;
291 : 25035 : position_range = i + 1;
292 : : }
293 [ - + ]: 938 : assert(num_positions == depgraph.TxCount());
294 [ - + ]: 938 : assert(position_range == depgraph.PositionRange());
295 [ - + ]: 938 : assert(position_range >= num_positions);
296 [ - + ]: 938 : assert(position_range <= SetType::Size());
297 : : // Consistency check between ancestors internally.
298 [ + + + + : 26331 : for (DepGraphIndex i : depgraph.Positions()) {
+ + ]
299 : : // Transactions include themselves as ancestors.
300 [ - + ]: 25035 : assert(depgraph.Ancestors(i)[i]);
301 : : // If a is an ancestor of b, then b's ancestors must include all of a's ancestors.
302 [ + + - + : 195473 : for (auto a : depgraph.Ancestors(i)) {
+ + ]
303 [ - + ]: 265550 : assert(depgraph.Ancestors(i).IsSupersetOf(depgraph.Ancestors(a)));
304 : : }
305 : : }
306 : : // Consistency check between ancestors and descendants.
307 [ + + + - : 26331 : for (DepGraphIndex i : depgraph.Positions()) {
+ + ]
308 [ + + + + : 957696 : for (DepGraphIndex j : depgraph.Positions()) {
+ + ]
309 [ - + ]: 923601 : assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]);
310 : : }
311 : : // No transaction is a parent or child of itself.
312 : 25035 : auto parents = depgraph.GetReducedParents(i);
313 [ - + ]: 25035 : auto children = depgraph.GetReducedChildren(i);
314 [ - + ]: 25035 : assert(!parents[i]);
315 [ - + ]: 25035 : assert(!children[i]);
316 : : // Parents of a transaction do not have ancestors inside those parents (except itself).
317 : : // Note that even the transaction itself may be missing (if it is part of a cycle).
318 [ + + - + : 107025 : for (auto parent : parents) {
+ + ]
319 [ - + ]: 123353 : assert((depgraph.Ancestors(parent) & parents).IsSubsetOf(SetType::Singleton(parent)));
320 : : }
321 : : // Similar for children and descendants.
322 [ + + - + : 104529 : for (auto child : children) {
+ + ]
323 [ - + ]: 123353 : assert((depgraph.Descendants(child) & children).IsSubsetOf(SetType::Singleton(child)));
324 : : }
325 : : }
326 [ + - ]: 938 : if (depgraph.IsAcyclic()) {
327 : : // If DepGraph is acyclic, serialize + deserialize must roundtrip.
328 : 938 : std::vector<unsigned char> ser;
329 [ + - ]: 938 : VectorWriter writer(ser, 0);
330 [ + - - + ]: 1876 : writer << Using<DepGraphFormatter>(depgraph);
331 : 938 : SpanReader reader(ser);
332 [ + - ]: 938 : DepGraph<SetType> decoded_depgraph;
333 [ + - ]: 938 : reader >> Using<DepGraphFormatter>(decoded_depgraph);
334 [ - + ]: 938 : assert(depgraph == decoded_depgraph);
335 [ - + ]: 938 : assert(reader.empty());
336 : : // It must also deserialize correctly without the terminal 0 byte (as the deserializer
337 : : // will upon EOF still return what it read so far).
338 [ + - - + ]: 938 : assert(ser.size() >= 1 && ser.back() == 0);
339 [ - + ]: 938 : ser.pop_back();
340 : 938 : reader = SpanReader{ser};
341 [ + - ]: 938 : decoded_depgraph = {};
342 [ + - ]: 938 : reader >> Using<DepGraphFormatter>(decoded_depgraph);
343 [ - + ]: 938 : assert(depgraph == decoded_depgraph);
344 [ - + ]: 938 : assert(reader.empty());
345 : :
346 : : // In acyclic graphs, the union of parents with parents of parents etc. yields the
347 : : // full ancestor set (and similar for children and descendants).
348 [ + - + - ]: 1876 : std::vector<SetType> parents(depgraph.PositionRange()), children(depgraph.PositionRange());
349 [ + + + + ]: 26331 : for (DepGraphIndex i : depgraph.Positions()) {
350 : 25035 : parents[i] = depgraph.GetReducedParents(i);
351 : 25035 : children[i] = depgraph.GetReducedChildren(i);
352 : : }
353 [ + + + + ]: 26331 : for (auto i : depgraph.Positions()) {
354 : : // Initialize the set of ancestors with just the current transaction itself.
355 : 25035 : SetType ancestors = SetType::Singleton(i);
356 : : // Iteratively add parents of all transactions in the ancestor set to itself.
357 : : while (true) {
358 : 69150 : const auto old_ancestors = ancestors;
359 [ + + + + ]: 474184 : for (auto j : ancestors) ancestors |= parents[j];
360 : : // Stop when no more changes are being made.
361 [ + + ]: 69150 : if (old_ancestors == ancestors) break;
362 : : }
363 [ + - ]: 25035 : assert(ancestors == depgraph.Ancestors(i));
364 : :
365 : : // Initialize the set of descendants with just the current transaction itself.
366 : 25035 : SetType descendants = SetType::Singleton(i);
367 : : // Iteratively add children of all transactions in the descendant set to itself.
368 : : while (true) {
369 : 56547 : const auto old_descendants = descendants;
370 [ + + + + ]: 447968 : for (auto j : descendants) descendants |= children[j];
371 : : // Stop when no more changes are being made.
372 [ + + ]: 56547 : if (old_descendants == descendants) break;
373 : : }
374 [ - + ]: 25035 : assert(descendants == depgraph.Descendants(i));
375 : : }
376 : 938 : }
377 : 938 : }
378 : :
379 : : /** Perform a sanity check on a linearization. */
380 : : template<typename SetType>
381 [ - + ]: 186200 : void SanityCheck(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization)
382 : : {
383 : : // Check completeness.
384 [ - + ]: 186200 : assert(linearization.size() == depgraph.TxCount());
385 : 186200 : SetType done;
386 [ + + ]: 5189200 : for (auto i : linearization) {
387 : : // Check transaction position is in range.
388 [ - + ]: 5003000 : assert(depgraph.Positions()[i]);
389 : : // Check topology and lack of duplicates.
390 [ + - ]: 5003000 : assert((depgraph.Ancestors(i) - done) == SetType::Singleton(i));
391 : 5003000 : done.Set(i);
392 : : }
393 : 186200 : }
394 : :
395 : 186200 : inline uint64_t MaxOptimalLinearizationCost(DepGraphIndex cluster_count)
396 : : {
397 : : // These are the largest numbers seen returned as cost by Linearize(), in a large randomized
398 : : // trial. There exist almost certainly far worse cases, but they are unlikely to be
399 : : // encountered in randomized tests. The purpose of these numbers is guaranteeing that for
400 : : // *some* reasonable cost bound, optimal linearizations are always found.
401 : 186200 : static constexpr uint64_t COSTS[65] = {
402 : : 0,
403 : : 0, 545, 928, 1633, 2647, 4065, 5598, 8258,
404 : : 9505, 11471, 14137, 19553, 20460, 26191, 28397, 32599,
405 : : 41631, 47419, 56329, 57767, 72196, 63652, 95366, 96537,
406 : : 115653, 125407, 131734, 145090, 156349, 164665, 194224, 203953,
407 : : 207710, 225878, 239971, 252284, 256534, 222142, 251332, 357098,
408 : : 325788, 295867, 410053, 497483, 533892, 576572, 577845, 572400,
409 : : 592536, 455082, 609249, 659130, 714091, 544507, 718788, 562378,
410 : : 601926, 1025081, 732725, 708896, 738224, 900445, 1092519, 1139946
411 : : };
412 [ - + ]: 186200 : assert(cluster_count < std::size(COSTS));
413 : : // Multiply the table number by two, to account for the fact that they are not absolutes.
414 : 186200 : return COSTS[cluster_count] * 2;
415 : : }
416 : :
417 : : } // namespace cluster_linearize
418 : :
419 : : #endif // BITCOIN_TEST_UTIL_CLUSTER_LINEARIZE_H
|
