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