Inside Bitcoin

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
20namespace cluster_linearize {
21
22using 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
97struct DepGraphFormatter
98{
99    /** Convert x>=0 to 2x (even), x<0 to -2x-1 (odd). */
100    static uint64_t SignedToUnsigned(int64_t x) noexcept
101    {
102        if (x < 0) {
103            return 2 * uint64_t(-(x + 1)) + 1;
104        } else {
105            return 2 * uint64_t(x);
106        }
107    }
108
109    /** Convert even x to x/2 (>=0), odd x to -(x/2)-1 (<0). */
110    static int64_t UnsignedToSigned(uint64_t x) noexcept
111    {
112        if (x & 1) {
113            return -int64_t(x / 2) - 1;
114        } else {
115            return int64_t(x / 2);
116        }
117    }
118
119    template <typename Stream, typename SetType>
120    static void Ser(Stream& s, const DepGraph<SetType>& depgraph)
121    {
122        /** Construct a topological order to serialize the transactions in. */
123        std::vector<DepGraphIndex> topo_order;
124        topo_order.reserve(depgraph.TxCount());
125        for (auto i : depgraph.Positions()) topo_order.push_back(i);
126        std::sort(topo_order.begin(), topo_order.end(), [&](DepGraphIndex a, DepGraphIndex b) {
127            auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count();
128            if (anc_a != anc_b) return anc_a < anc_b;
129            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        SetType done;
135
136        // Loop over the transactions in topological order.
137        for (DepGraphIndex topo_idx = 0; topo_idx < topo_order.size(); ++topo_idx) {
138            /** Which depgraph index we are currently writing. */
139            DepGraphIndex idx = topo_order[topo_idx];
140            // Write size, which must be larger than 0.
141            s << VARINT_MODE(depgraph.FeeRate(idx).size, VarIntMode::NONNEGATIVE_SIGNED);
142            // Write fee, encoded as an unsigned varint (odd=negative, even=non-negative).
143            s << VARINT(SignedToUnsigned(depgraph.FeeRate(idx).fee));
144            // Write dependency information.
145            SetType written_parents;
146            uint64_t diff = 0; //!< How many potential parent/child relations we have skipped over.
147            for (DepGraphIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) {
148                /** Which depgraph index we are currently considering as parent of idx. */
149                DepGraphIndex dep_idx = topo_order[topo_idx - 1 - dep_dist];
150                // Ignore transactions which are already known to be ancestors.
151                if (depgraph.Descendants(dep_idx).Overlaps(written_parents)) continue;
152                if (depgraph.Ancestors(idx)[dep_idx]) {
153                    // When an actual parent is encountered, encode how many non-parents were skipped
154                    // before it.
155                    s << VARINT(diff);
156                    diff = 0;
157                    written_parents.Set(dep_idx);
158                } else {
159                    // When a non-parent is encountered, increment the skip counter.
160                    ++diff;
161                }
162            }
163            // Write position information.
164            auto add_holes = SetType::Fill(idx) - done - depgraph.Positions();
165            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                auto skips = (done - SetType::Fill(idx)).Count();
169                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                s << VARINT(diff + done.Count() + add_holes.Count());
175                done |= add_holes;
176            }
177            done.Set(idx);
178        }
179
180        // Output a final 0 to denote the end of the graph.
181        s << uint8_t{0};
182    }
183
184    template <typename Stream, typename SetType>
185    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        DepGraph<SetType> topo_depgraph;
190        /** Mapping from serialization order to cluster order, used later to reconstruct the
191         *  cluster order. */
192        std::vector<DepGraphIndex> reordering;
193        /** How big the entries vector in the reconstructed depgraph will be (including holes). */
194        DepGraphIndex total_size{0};
195
196        // Read transactions in topological order.
197        while (true) {
198            FeeFrac new_feerate; //!< The new transaction's fee and size.
199            SetType new_ancestors; //!< The new transaction's ancestors (excluding itself).
200            uint64_t diff{0}; //!< How many potential parents/insertions we have to skip.
201            bool read_error{false};
202            try {
203                // Read size. Size 0 signifies the end of the DepGraph.
204                int32_t size;
205                s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED);
206                size &= 0x3FFFFF; // Enough for size up to 4M.
207                static_assert(0x3FFFFF >= 4000000);
208                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                s >> VARINT(coded_fee);
212                coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC.
213                static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000);
214                new_feerate = {UnsignedToSigned(coded_fee), size};
215                // Read dependency information.
216                auto topo_idx = reordering.size();
217                s >> VARINT(diff);
218                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                    DepGraphIndex dep_topo_idx = topo_idx - 1 - dep_dist;
221                    // Ignore transactions which are already known ancestors of topo_idx.
222                    if (new_ancestors[dep_topo_idx]) continue;
223                    if (diff == 0) {
224                        // When the skip counter has reached 0, add an actual dependency.
225                        new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx);
226                        // And read the number of skips after it.
227                        s >> VARINT(diff);
228                    } else {
229                        // Otherwise, dep_topo_idx is not a parent. Decrement and continue.
230                        --diff;
231                    }
232                }
233            } catch (const std::ios_base::failure&) {
234                // Continue even if a read error was encountered.
235                read_error = true;
236            }
237            // Construct a new transaction whenever we made it past the new_feerate construction.
238            if (new_feerate.IsEmpty()) break;
239            assert(reordering.size() < SetType::Size());
240            auto topo_idx = topo_depgraph.AddTransaction(new_feerate);
241            topo_depgraph.AddDependencies(new_ancestors, topo_idx);
242            if (total_size < SetType::Size()) {
243                // Normal case.
244                diff %= SetType::Size();
245                if (diff <= total_size) {
246                    // Insert the new transaction at distance diff back from the end.
247                    for (auto& pos : reordering) {
248                        pos += (pos >= total_size - diff);
249                    }
250                    reordering.push_back(total_size++ - diff);