_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2Ev: 68| 5.65k| DepGraph() noexcept = default; _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7TxCountEv: 118| 35.2k| auto TxCount() const noexcept { return m_used.Count(); } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9PositionsEv: 114| 171k| const SetType& Positions() const noexcept { return m_used; } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj: 122| 30.9k| FeeFrac& FeeRate(ClusterIndex i) noexcept { return entries[i].feerate; } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9AncestorsEj: 124| 2.28M| const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE14AddTransactionERK7FeeFrac: 134| 60.2k| { 135| 60.2k| static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size()); 136| 60.2k| auto available = ALL_POSITIONS - m_used; 137| 60.2k| Assume(available.Any()); ------------------ | | 97| 60.2k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 138| 60.2k| ClusterIndex new_idx = available.First(); 139| 60.2k| if (new_idx == entries.size()) { ------------------ | Branch (139:13): [True: 54.8k, False: 5.43k] ------------------ 140| 54.8k| entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); 141| 54.8k| } else { 142| 5.43k| entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); 143| 5.43k| } 144| 60.2k| m_used.Set(new_idx); 145| 60.2k| return new_idx; 146| 60.2k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2ERK7FeeFracRKS3_SA_: 46| 60.2k| Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {} _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE15AddDependenciesERKS3_j: 178| 103k| { 179| 103k| Assume(m_used[child]); ------------------ | | 97| 103k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 180| 103k| Assume(parents.IsSubsetOf(m_used)); ------------------ | | 97| 103k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 181| | // Compute the ancestors of parents that are not already ancestors of child. 182| 103k| SetType par_anc; 183| 103k| for (auto par : parents - Ancestors(child)) { ------------------ | Branch (183:23): [True: 92.6k, False: 103k] ------------------ 184| 92.6k| par_anc |= Ancestors(par); 185| 92.6k| } 186| 103k| par_anc -= Ancestors(child); 187| | // Bail out if there are no such ancestors. 188| 103k| if (par_anc.None()) return; ------------------ | Branch (188:13): [True: 84.6k, False: 18.5k] ------------------ 189| | // To each such ancestor, add as descendants the descendants of the child. 190| 18.5k| const auto& chl_des = entries[child].descendants; 191| 125k| for (auto anc_of_par : par_anc) { ------------------ | Branch (191:30): [True: 125k, False: 18.5k] ------------------ 192| 125k| entries[anc_of_par].descendants |= chl_des; 193| 125k| } 194| | // To each descendant of the child, add those ancestors. 195| 41.7k| for (auto dec_of_chl : Descendants(child)) { ------------------ | Branch (195:30): [True: 41.7k, False: 18.5k] ------------------ 196| 41.7k| entries[dec_of_chl].ancestors |= par_anc; 197| 41.7k| } 198| 18.5k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE18RemoveTransactionsERKS3_: 158| 6.08k| { 159| 6.08k| m_used -= del; 160| | // Remove now-unused trailing entries. 161| 10.2k| while (!entries.empty() && !m_used[entries.size() - 1]) { ------------------ | Branch (161:16): [True: 9.41k, False: 838] | Branch (161:36): [True: 4.16k, False: 5.24k] ------------------ 162| 4.16k| entries.pop_back(); 163| 4.16k| } 164| | // Remove the deleted transactions from ancestors/descendants of other transactions. Note 165| | // that the deleted positions will retain old feerate and dependency information. This does 166| | // not matter as they will be overwritten by AddTransaction if they get used again. 167| 60.5k| for (auto& entry : entries) { ------------------ | Branch (167:26): [True: 60.5k, False: 6.08k] ------------------ 168| 60.5k| entry.ancestors &= m_used; 169| 60.5k| entry.descendants &= m_used; 170| 60.5k| } 171| 6.08k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj: 120| 29.3k| const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; } _ZN17cluster_linearizeeqERKNS_8DepGraphIN13bitset_detail9IntBitSetIjEEEES6_: 58| 2.16k| { 59| 2.16k| if (a.m_used != b.m_used) return false; ------------------ | Branch (59:13): [True: 0, False: 2.16k] ------------------ 60| | // Only compare the used positions within the entries vector. 61| 29.3k| for (auto idx : a.m_used) { ------------------ | Branch (61:23): [True: 29.3k, False: 2.16k] ------------------ 62| 29.3k| if (a.entries[idx] != b.entries[idx]) return false; ------------------ | Branch (62:17): [True: 0, False: 29.3k] ------------------ 63| 29.3k| } 64| 2.16k| return true; 65| 2.16k| } _ZN17cluster_linearizeeqERKNS_8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryES7_: 41| 586k| friend bool operator==(const Entry&, const Entry&) noexcept = default; ------------------ | Branch (41:77): [True: 117k, False: 0] | Branch (41:77): [True: 117k, False: 0] | Branch (41:77): [True: 117k, False: 0] ------------------ _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEaSEOS4_: 72| 3.24k| DepGraph& operator=(DepGraph&&) noexcept = default; _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2ERKS4_4SpanIKjEj: 89| 2.16k| DepGraph(const DepGraph& depgraph, Span mapping, ClusterIndex pos_range) noexcept : entries(pos_range) 90| 2.16k| { 91| 2.16k| Assume(mapping.size() == depgraph.PositionRange()); ------------------ | | 97| 2.16k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 92| 2.16k| Assume((pos_range == 0) == (depgraph.TxCount() == 0)); ------------------ | | 97| 2.16k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 93| 29.3k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (93:29): [True: 29.3k, False: 2.16k] ------------------ 94| 29.3k| auto new_idx = mapping[i]; 95| 29.3k| Assume(new_idx < pos_range); ------------------ | | 97| 29.3k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 96| | // Add transaction. 97| 29.3k| entries[new_idx].ancestors = SetType::Singleton(new_idx); 98| 29.3k| entries[new_idx].descendants = SetType::Singleton(new_idx); 99| 29.3k| m_used.Set(new_idx); 100| | // Fill in fee and size. 101| 29.3k| entries[new_idx].feerate = depgraph.entries[i].feerate; 102| 29.3k| } 103| 29.3k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (103:29): [True: 29.3k, False: 2.16k] ------------------ 104| | // Fill in dependencies by mapping direct parents. 105| 29.3k| SetType parents; 106| 29.3k| for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]); ------------------ | Branch (106:25): [True: 20.5k, False: 29.3k] ------------------ 107| 29.3k| AddDependencies(parents, mapping[i]); 108| 29.3k| } 109| | // Verify that the provided pos_range was correct (no unused positions at the end). 110| 2.16k| Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1)); ------------------ | | 97| 4.32k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) | | ------------------ | | | Branch (97:51): [True: 110, False: 2.05k] | | ------------------ ------------------ 111| 2.16k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2Ev: 44| 32.7k| Entry() noexcept = default; _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11DescendantsEj: 126| 799k| const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE13PositionRangeEv: 116| 5.65k| ClusterIndex PositionRange() const noexcept { return entries.size(); } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE18GetReducedChildrenEj: 230| 34.2k| { 231| 34.2k| SetType children = Descendants(i); 232| 34.2k| children.Reset(i); 233| 69.7k| for (auto child : children) { ------------------ | Branch (233:25): [True: 69.7k, False: 34.2k] ------------------ 234| 69.7k| if (children[child]) { ------------------ | Branch (234:17): [True: 29.2k, False: 40.4k] ------------------ 235| 29.2k| children -= Descendants(child); 236| 29.2k| children.Set(child); 237| 29.2k| } 238| 69.7k| } 239| 34.2k| return children; 240| 34.2k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE17GetReducedParentsEj: 209| 63.5k| { 210| 63.5k| SetType parents = Ancestors(i); 211| 63.5k| parents.Reset(i); 212| 102k| for (auto parent : parents) { ------------------ | Branch (212:26): [True: 102k, False: 63.5k] ------------------ 213| 102k| if (parents[parent]) { ------------------ | Branch (213:17): [True: 60.6k, False: 41.6k] ------------------ 214| 60.6k| parents -= Ancestors(parent); 215| 60.6k| parents.Set(parent); 216| 60.6k| } 217| 102k| } 218| 63.5k| return parents; 219| 63.5k| } _ZN15CheckVarIntModeIL10VarIntMode0EmEC2Ev: 410| 118k| { 411| 118k| static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned::value, "Unsigned type required with mode DEFAULT."); 412| 118k| static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed::value, "Signed type required with mode NONNEGATIVE_SIGNED."); 413| 118k| } _ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmEC2ES3_: 481| 118k| explicit Wrapper(T obj) : m_object(obj) {} _ZN15CheckVarIntModeIL10VarIntMode1EiEC2Ev: 410| 46.1k| { 411| 46.1k| static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned::value, "Unsigned type required with mode DEFAULT."); 412| 46.1k| static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed::value, "Signed type required with mode NONNEGATIVE_SIGNED."); 413| 46.1k| } _ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiEC2ES3_: 481| 31.5k| explicit Wrapper(T obj) : m_object(obj) {} cluster_linearize.cpp:_Z9SerializeI12VectorWriter7WrapperIN12_GLOBAL__N_117DepGraphFormatterERKN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEQ12SerializableIT0_T_EEvRSE_RKSD_: 753| 1.08k|{ 754| 1.08k| a.Serialize(os); 755| 1.08k|} cluster_linearize.cpp:_ZNK7WrapperIN12_GLOBAL__N_117DepGraphFormatterERKN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE9SerializeI12VectorWriterEEvRT_: 482| 1.08k| template void Serialize(Stream &s) const { Formatter().Ser(s, m_object); } _Z9SerializeI12VectorWriter7WrapperI15VarIntFormatterIL10VarIntMode1EERKiEQ12SerializableIT0_T_EEvRS9_RKS8_: 753| 14.6k|{ 754| 14.6k| a.Serialize(os); 755| 14.6k|} _ZNK7WrapperI15VarIntFormatterIL10VarIntMode1EERKiE9SerializeI12VectorWriterEEvRT_: 482| 14.6k| template void Serialize(Stream &s) const { Formatter().Ser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode1EE3SerI12VectorWriteriEEvRT_T0_: 509| 14.6k| { 510| 14.6k| WriteVarInt::type>(s, v); 511| 14.6k| } _Z11WriteVarIntI12VectorWriterL10VarIntMode1EiEvRT_T1_: 435| 14.6k|{ 436| 14.6k| CheckVarIntMode(); 437| 14.6k| unsigned char tmp[(sizeof(n)*8+6)/7]; 438| 14.6k| int len=0; 439| 33.9k| while(true) { ------------------ | Branch (439:11): [Folded - Ignored] ------------------ 440| 33.9k| tmp[len] = (n & 0x7F) | (len ? 0x80 : 0x00); ------------------ | Branch (440:34): [True: 19.2k, False: 14.6k] ------------------ 441| 33.9k| if (n <= 0x7F) ------------------ | Branch (441:13): [True: 14.6k, False: 19.2k] ------------------ 442| 14.6k| break; 443| 19.2k| n = (n >> 7) - 1; 444| 19.2k| len++; 445| 19.2k| } 446| 33.9k| do { 447| 33.9k| ser_writedata8(os, tmp[len]); 448| 33.9k| } while(len--); ------------------ | Branch (448:13): [True: 19.2k, False: 14.6k] ------------------ 449| 14.6k|} _Z14ser_writedata8I12VectorWriterEvRT_h: 55| 175k|{ 56| 175k| s.write(AsBytes(Span{&obj, 1})); 57| 175k|} cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode1EERKiE7WrapperIT_RT0_EOS7_: 497| 14.6k|static inline Wrapper Using(T&& t) { return Wrapper(t); } _ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERKiEC2ES4_: 481| 14.6k| explicit Wrapper(T obj) : m_object(obj) {} _Z9SerializeI12VectorWriter7WrapperI15VarIntFormatterIL10VarIntMode0EERmEQ12SerializableIT0_T_EEvRS8_RKS7_: 753| 39.6k|{ 754| 39.6k| a.Serialize(os); 755| 39.6k|} _ZNK7WrapperI15VarIntFormatterIL10VarIntMode0EERmE9SerializeI12VectorWriterEEvRT_: 482| 39.6k| template void Serialize(Stream &s) const { Formatter().Ser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode0EE3SerI12VectorWritermEEvRT_T0_: 509| 39.6k| { 510| 39.6k| WriteVarInt::type>(s, v); 511| 39.6k| } _Z11WriteVarIntI12VectorWriterL10VarIntMode0EmEvRT_T1_: 435| 39.6k|{ 436| 39.6k| CheckVarIntMode(); 437| 39.6k| unsigned char tmp[(sizeof(n)*8+6)/7]; 438| 39.6k| int len=0; 439| 140k| while(true) { ------------------ | Branch (439:11): [Folded - Ignored] ------------------ 440| 140k| tmp[len] = (n & 0x7F) | (len ? 0x80 : 0x00); ------------------ | Branch (440:34): [True: 101k, False: 39.6k] ------------------ 441| 140k| if (n <= 0x7F) ------------------ | Branch (441:13): [True: 39.6k, False: 101k] ------------------ 442| 39.6k| break; 443| 101k| n = (n >> 7) - 1; 444| 101k| len++; 445| 101k| } 446| 140k| do { 447| 140k| ser_writedata8(os, tmp[len]); 448| 140k| } while(len--); ------------------ | Branch (448:13): [True: 101k, False: 39.6k] ------------------ 449| 39.6k|} cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode0EEmE7WrapperIT_RT0_EOS5_: 497| 29.3k|static inline Wrapper Using(T&& t) { return Wrapper(t); } _Z9SerializeI12VectorWriterEvRT_h: 258| 1.08k|template inline void Serialize(Stream& s, uint8_t a ) { ser_writedata8(s, a); } cluster_linearize.cpp:_ZL5UsingIN12_GLOBAL__N_117DepGraphFormatterERKN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE7WrapperIT_RT0_EOSC_: 497| 1.08k|static inline Wrapper Using(T&& t) { return Wrapper(t); } cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERKN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEC2ES9_: 481| 1.08k| explicit Wrapper(T obj) : m_object(obj) {} cluster_linearize.cpp:_ZL5UsingIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE7WrapperIT_RT0_EOSB_: 497| 2.16k|static inline Wrapper Using(T&& t) { return Wrapper(t); } cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEC2ES8_: 481| 2.16k| explicit Wrapper(T obj) : m_object(obj) {} cluster_linearize.cpp:_Z11UnserializeI10SpanReaderR7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEQ14UnserializableIT0_T_EEvRSE_OSD_: 762| 2.16k|{ 763| 2.16k| a.Unserialize(is); 764| 2.16k|} cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE11UnserializeI10SpanReaderEEvRT_: 483| 2.16k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } _Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode1EERiEQ14UnserializableIT0_T_EEvRS9_OS8_: 762| 31.5k|{ 763| 31.5k| a.Unserialize(is); 764| 31.5k|} _ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiE11UnserializeI10SpanReaderEEvRT_: 483| 31.5k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode1EE5UnserI10SpanReaderiEEvRT_RT0_: 514| 31.5k| { 515| 31.5k| v = ReadVarInt::type>(s); 516| 31.5k| } _Z10ReadVarIntI10SpanReaderL10VarIntMode1EiET1_RT_: 453| 31.5k|{ 454| 31.5k| CheckVarIntMode(); 455| 31.5k| I n = 0; 456| 70.0k| while(true) { ------------------ | Branch (456:11): [Folded - Ignored] ------------------ 457| 70.0k| unsigned char chData = ser_readdata8(is); 458| 70.0k| if (n > (std::numeric_limits::max() >> 7)) { ------------------ | Branch (458:13): [True: 0, False: 70.0k] ------------------ 459| 0| throw std::ios_base::failure("ReadVarInt(): size too large"); 460| 0| } 461| 70.0k| n = (n << 7) | (chData & 0x7F); 462| 70.0k| if (chData & 0x80) { ------------------ | Branch (462:13): [True: 38.5k, False: 31.5k] ------------------ 463| 38.5k| if (n == std::numeric_limits::max()) { ------------------ | Branch (463:17): [True: 0, False: 38.5k] ------------------ 464| 0| throw std::ios_base::failure("ReadVarInt(): size too large"); 465| 0| } 466| 38.5k| n++; 467| 38.5k| } else { 468| 31.5k| return n; 469| 31.5k| } 470| 70.0k| } 471| 31.5k|} _Z13ser_readdata8I10SpanReaderEhRT_: 84| 351k|{ 85| 351k| uint8_t obj; 86| 351k| s.read(AsWritableBytes(Span{&obj, 1})); 87| 351k| return obj; 88| 351k|} cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode1EERiE7WrapperIT_RT0_EOS6_: 497| 31.5k|static inline Wrapper Using(T&& t) { return Wrapper(t); } cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode0EERmE7WrapperIT_RT0_EOS6_: 497| 89.5k|static inline Wrapper Using(T&& t) { return Wrapper(t); } _Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode0EERmEQ14UnserializableIT0_T_EEvRS9_OS8_: 762| 79.2k|{ 763| 79.2k| a.Unserialize(is); 764| 79.2k|} _ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmE11UnserializeI10SpanReaderEEvRT_: 483| 79.2k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode0EE5UnserI10SpanReadermEEvRT_RT0_: 514| 79.2k| { 515| 79.2k| v = ReadVarInt::type>(s); 516| 79.2k| } _Z10ReadVarIntI10SpanReaderL10VarIntMode0EmET1_RT_: 453| 79.2k|{ 454| 79.2k| CheckVarIntMode(); 455| 79.2k| I n = 0; 456| 281k| while(true) { ------------------ | Branch (456:11): [Folded - Ignored] ------------------ 457| 281k| unsigned char chData = ser_readdata8(is); 458| 281k| if (n > (std::numeric_limits::max() >> 7)) { ------------------ | Branch (458:13): [True: 0, False: 281k] ------------------ 459| 0| throw std::ios_base::failure("ReadVarInt(): size too large"); 460| 0| } 461| 281k| n = (n << 7) | (chData & 0x7F); 462| 281k| if (chData & 0x80) { ------------------ | Branch (462:13): [True: 202k, False: 79.2k] ------------------ 463| 202k| if (n == std::numeric_limits::max()) { ------------------ | Branch (463:17): [True: 0, False: 202k] ------------------ 464| 0| throw std::ios_base::failure("ReadVarInt(): size too large"); 465| 0| } 466| 202k| n++; 467| 202k| } else { 468| 79.2k| return n; 469| 79.2k| } 470| 281k| } 471| 79.2k|} _Z9UCharCastPKSt4byte: 287| 351k|inline const unsigned char* UCharCast(const std::byte* c) { return reinterpret_cast(c); } _ZNK4SpanIKSt4byteE4sizeEv: 187| 703k| constexpr std::size_t size() const noexcept { return m_size; } _ZNK4SpanIKSt4byteE4dataEv: 174| 351k| constexpr C* data() const noexcept { return m_data; } _ZNK4SpanIKhE4sizeEv: 187| 353k| constexpr std::size_t size() const noexcept { return m_size; } _ZNK4SpanIhE4dataEv: 174| 527k| constexpr C* data() const noexcept { return m_data; } _ZNK4SpanIKhE4dataEv: 174| 350k| constexpr C* data() const noexcept { return m_data; } _ZNK4SpanISt4byteE4sizeEv: 187| 1.40M| constexpr std::size_t size() const noexcept { return m_size; } _ZNK4SpanIKhE5emptyEv: 189| 2.16k| constexpr bool empty() const noexcept { return size() == 0; } _ZNK4SpanISt4byteE4dataEv: 174| 350k| constexpr C* data() const noexcept { return m_data; } _ZNK4SpanIKhE7subspanEm: 196| 350k| { 197| 350k| ASSERT_IF_DEBUG(size() >= offset); 198| 350k| return Span(m_data + offset, m_size - offset); 199| 350k| } _ZN4SpanIKSt4byteEC2IS1_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S1_EE5valueEiE4typeELi0EEEPS6_m: 119| 175k| constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} _ZN4SpanIKhEC2INSt3__16vectorIhNS3_9allocatorIhEEEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS8_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS9_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS9_EE4sizeEEmEE5valueEDnE4typeE: 165| 2.16k| : m_data(other.data()), m_size(other.size()){} _ZNK4SpanIhE10size_bytesEv: 188| 527k| constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; } _Z7AsBytesIhE4SpanIKSt4byteES0_IT_E: 259| 175k|{ 260| 175k| return {reinterpret_cast(s.data()), s.size_bytes()}; 261| 175k|} _ZN4SpanIKhEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m: 119| 350k| constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} _ZN4SpanISt4byteEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m: 119| 351k| constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} _Z15AsWritableBytesIhE4SpanISt4byteES0_IT_E: 264| 351k|{ 265| 351k| return {reinterpret_cast(s.data()), s.size_bytes()}; 266| 351k|} _ZN4SpanIhEC2IhTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_hEE5valueEiE4typeELi0EEEPS4_m: 119| 527k| constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} _ZN4SpanIKjEC2INSt3__16vectorIjNS3_9allocatorIjEEEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS8_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS9_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS9_EE4sizeEEmEE5valueEDnE4typeE: 165| 2.16k| : m_data(other.data()), m_size(other.size()){} _ZNK4SpanIKjE4sizeEv: 187| 2.16k| constexpr std::size_t size() const noexcept { return m_size; } _ZNK4SpanIKjEixEm: 191| 79.2k| { 192| 79.2k| ASSERT_IF_DEBUG(size() > pos); 193| 79.2k| return m_data[pos]; 194| 79.2k| } _ZN12VectorWriterC2ERNSt3__16vectorIhNS0_9allocatorIhEEEEm: 60| 1.08k| VectorWriter(std::vector& vchDataIn, size_t nPosIn) : vchData{vchDataIn}, nPos{nPosIn} 61| 1.08k| { 62| 1.08k| if(nPos > vchData.size()) ------------------ | Branch (62:12): [True: 0, False: 1.08k] ------------------ 63| 0| vchData.resize(nPos); 64| 1.08k| } _ZN12VectorWriter5writeE4SpanIKSt4byteE: 75| 175k| { 76| 175k| assert(nPos <= vchData.size()); 77| 175k| size_t nOverwrite = std::min(src.size(), vchData.size() - nPos); 78| 175k| if (nOverwrite) { ------------------ | Branch (78:13): [True: 0, False: 175k] ------------------ 79| 0| memcpy(vchData.data() + nPos, src.data(), nOverwrite); 80| 0| } 81| 175k| if (nOverwrite < src.size()) { ------------------ | Branch (81:13): [True: 175k, False: 0] ------------------ 82| 175k| vchData.insert(vchData.end(), UCharCast(src.data()) + nOverwrite, UCharCast(src.data() + src.size())); 83| 175k| } 84| 175k| nPos += src.size(); 85| 175k| } _ZN10SpanReaderC2E4SpanIKhE: 109| 2.16k| explicit SpanReader(Span data) : m_data{data} {} _ZNK10SpanReader5emptyEv: 119| 2.16k| bool empty() const { return m_data.empty(); } _ZN10SpanReader4readE4SpanISt4byteE: 122| 351k| { 123| 351k| if (dst.size() == 0) { ------------------ | Branch (123:13): [True: 0, False: 351k] ------------------ 124| 0| return; 125| 0| } 126| | 127| | // Read from the beginning of the buffer 128| 351k| if (dst.size() > m_data.size()) { ------------------ | Branch (128:13): [True: 1.08k, False: 350k] ------------------ 129| 1.08k| throw std::ios_base::failure("SpanReader::read(): end of data"); 130| 1.08k| } 131| 350k| memcpy(dst.data(), m_data.data(), dst.size()); 132| 350k| m_data = m_data.subspan(dst.size()); 133| 350k| } cluster_linearize.cpp:_ZN12VectorWriterlsI7WrapperIN12_GLOBAL__N_117DepGraphFormatterERKN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEEERS_RKT_: 88| 1.08k| { 89| 1.08k| ::Serialize(*this, obj); 90| 1.08k| return (*this); 91| 1.08k| } _ZN12VectorWriterlsI7WrapperI15VarIntFormatterIL10VarIntMode1EERKiEEERS_RKT_: 88| 14.6k| { 89| 14.6k| ::Serialize(*this, obj); 90| 14.6k| return (*this); 91| 14.6k| } _ZN12VectorWriterlsI7WrapperI15VarIntFormatterIL10VarIntMode0EERmEEERS_RKT_: 88| 39.6k| { 89| 39.6k| ::Serialize(*this, obj); 90| 39.6k| return (*this); 91| 39.6k| } _ZN12VectorWriterlsIhEERS_RKT_: 88| 1.08k| { 89| 1.08k| ::Serialize(*this, obj); 90| 1.08k| return (*this); 91| 1.08k| } cluster_linearize.cpp:_ZN10SpanReaderrsI7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEEERS_OT_: 113| 2.16k| { 114| 2.16k| ::Unserialize(*this, obj); 115| 2.16k| return (*this); 116| 2.16k| } _ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode1EERiEEERS_OT_: 113| 31.5k| { 114| 31.5k| ::Unserialize(*this, obj); 115| 31.5k| return (*this); 116| 31.5k| } _ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode0EERmEEERS_OT_: 113| 79.2k| { 114| 79.2k| ::Unserialize(*this, obj); 115| 79.2k| return (*this); 116| 79.2k| } _ZN18FuzzedDataProviderC2EPKhm: 37| 1.32k| : data_ptr_(data), remaining_bytes_(size) {} _ZN18FuzzedDataProvider22ConsumeIntegralInRangeIlEET_S1_S1_: 205| 30.9k|T FuzzedDataProvider::ConsumeIntegralInRange(T min, T max) { 206| 30.9k| static_assert(std::is_integral::value, "An integral type is required."); 207| 30.9k| static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type."); 208| | 209| 30.9k| if (min > max) ------------------ | Branch (209:7): [True: 0, False: 30.9k] ------------------ 210| 0| abort(); 211| | 212| | // Use the biggest type possible to hold the range and the result. 213| 30.9k| uint64_t range = static_cast(max) - static_cast(min); 214| 30.9k| uint64_t result = 0; 215| 30.9k| size_t offset = 0; 216| | 217| 245k| while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 && ------------------ | Branch (217:10): [True: 245k, False: 0] | Branch (217:43): [True: 214k, False: 30.5k] ------------------ 218| 245k| remaining_bytes_ != 0) { ------------------ | Branch (218:10): [True: 214k, False: 366] ------------------ 219| | // Pull bytes off the end of the seed data. Experimentally, this seems to 220| | // allow the fuzzer to more easily explore the input space. This makes 221| | // sense, since it works by modifying inputs that caused new code to run, 222| | // and this data is often used to encode length of data read by 223| | // |ConsumeBytes|. Separating out read lengths makes it easier modify the 224| | // contents of the data that is actually read. 225| 214k| --remaining_bytes_; 226| 214k| result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_]; 227| 214k| offset += CHAR_BIT; 228| 214k| } 229| | 230| | // Avoid division by 0, in case |range + 1| results in overflow. 231| 30.9k| if (range != std::numeric_limits::max()) ------------------ | Branch (231:7): [True: 30.9k, False: 0] ------------------ 232| 30.9k| result = result % (range + 1); 233| | 234| 30.9k| return static_cast(static_cast(min) + result); 235| 30.9k|} _ZN18FuzzedDataProvider22ConsumeIntegralInRangeImEET_S1_S1_: 205| 50.6k|T FuzzedDataProvider::ConsumeIntegralInRange(T min, T max) { 206| 50.6k| static_assert(std::is_integral::value, "An integral type is required."); 207| 50.6k| static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type."); 208| | 209| 50.6k| if (min > max) ------------------ | Branch (209:7): [True: 0, False: 50.6k] ------------------ 210| 0| abort(); 211| | 212| | // Use the biggest type possible to hold the range and the result. 213| 50.6k| uint64_t range = static_cast(max) - static_cast(min); 214| 50.6k| uint64_t result = 0; 215| 50.6k| size_t offset = 0; 216| | 217| 208k| while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 && ------------------ | Branch (217:10): [True: 208k, False: 0] | Branch (217:43): [True: 158k, False: 50.0k] ------------------ 218| 208k| remaining_bytes_ != 0) { ------------------ | Branch (218:10): [True: 158k, False: 531] ------------------ 219| | // Pull bytes off the end of the seed data. Experimentally, this seems to 220| | // allow the fuzzer to more easily explore the input space. This makes 221| | // sense, since it works by modifying inputs that caused new code to run, 222| | // and this data is often used to encode length of data read by 223| | // |ConsumeBytes|. Separating out read lengths makes it easier modify the 224| | // contents of the data that is actually read. 225| 158k| --remaining_bytes_; 226| 158k| result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_]; 227| 158k| offset += CHAR_BIT; 228| 158k| } 229| | 230| | // Avoid division by 0, in case |range + 1| results in overflow. 231| 50.6k| if (range != std::numeric_limits::max()) ------------------ | Branch (231:7): [True: 50.6k, False: 0] ------------------ 232| 50.6k| result = result % (range + 1); 233| | 234| 50.6k| return static_cast(static_cast(min) + result); 235| 50.6k|} _ZN18FuzzedDataProvider22ConsumeIntegralInRangeIiEET_S1_S1_: 205| 30.9k|T FuzzedDataProvider::ConsumeIntegralInRange(T min, T max) { 206| 30.9k| static_assert(std::is_integral::value, "An integral type is required."); 207| 30.9k| static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type."); 208| | 209| 30.9k| if (min > max) ------------------ | Branch (209:7): [True: 0, False: 30.9k] ------------------ 210| 0| abort(); 211| | 212| | // Use the biggest type possible to hold the range and the result. 213| 30.9k| uint64_t range = static_cast(max) - static_cast(min); 214| 30.9k| uint64_t result = 0; 215| 30.9k| size_t offset = 0; 216| | 217| 122k| while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 && ------------------ | Branch (217:10): [True: 122k, False: 0] | Branch (217:43): [True: 91.9k, False: 30.4k] ------------------ 218| 122k| remaining_bytes_ != 0) { ------------------ | Branch (218:10): [True: 91.4k, False: 479] ------------------ 219| | // Pull bytes off the end of the seed data. Experimentally, this seems to 220| | // allow the fuzzer to more easily explore the input space. This makes 221| | // sense, since it works by modifying inputs that caused new code to run, 222| | // and this data is often used to encode length of data read by 223| | // |ConsumeBytes|. Separating out read lengths makes it easier modify the 224| | // contents of the data that is actually read. 225| 91.4k| --remaining_bytes_; 226| 91.4k| result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_]; 227| 91.4k| offset += CHAR_BIT; 228| 91.4k| } 229| | 230| | // Avoid division by 0, in case |range + 1| results in overflow. 231| 30.9k| if (range != std::numeric_limits::max()) ------------------ | Branch (231:7): [True: 30.9k, False: 0] ------------------ 232| 30.9k| result = result % (range + 1); 233| | 234| 30.9k| return static_cast(static_cast(min) + result); 235| 30.9k|} _ZN18FuzzedDataProvider22ConsumeIntegralInRangeIjEET_S1_S1_: 205| 44.5k|T FuzzedDataProvider::ConsumeIntegralInRange(T min, T max) { 206| 44.5k| static_assert(std::is_integral::value, "An integral type is required."); 207| 44.5k| static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type."); 208| | 209| 44.5k| if (min > max) ------------------ | Branch (209:7): [True: 0, False: 44.5k] ------------------ 210| 0| abort(); 211| | 212| | // Use the biggest type possible to hold the range and the result. 213| 44.5k| uint64_t range = static_cast(max) - static_cast(min); 214| 44.5k| uint64_t result = 0; 215| 44.5k| size_t offset = 0; 216| | 217| 84.8k| while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 && ------------------ | Branch (217:10): [True: 84.8k, False: 0] | Branch (217:43): [True: 40.3k, False: 44.4k] ------------------ 218| 84.8k| remaining_bytes_ != 0) { ------------------ | Branch (218:10): [True: 40.2k, False: 41] ------------------ 219| | // Pull bytes off the end of the seed data. Experimentally, this seems to 220| | // allow the fuzzer to more easily explore the input space. This makes 221| | // sense, since it works by modifying inputs that caused new code to run, 222| | // and this data is often used to encode length of data read by 223| | // |ConsumeBytes|. Separating out read lengths makes it easier modify the 224| | // contents of the data that is actually read. 225| 40.2k| --remaining_bytes_; 226| 40.2k| result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_]; 227| 40.2k| offset += CHAR_BIT; 228| 40.2k| } 229| | 230| | // Avoid division by 0, in case |range + 1| results in overflow. 231| 44.5k| if (range != std::numeric_limits::max()) ------------------ | Branch (231:7): [True: 44.5k, False: 0] ------------------ 232| 44.5k| result = result % (range + 1); 233| | 234| 44.5k| return static_cast(static_cast(min) + result); 235| 44.5k|} _ZN18FuzzedDataProvider15ConsumeIntegralIhEET_v: 195| 81.5k|template T FuzzedDataProvider::ConsumeIntegral() { 196| 81.5k| return ConsumeIntegralInRange(std::numeric_limits::min(), 197| 81.5k| std::numeric_limits::max()); 198| 81.5k|} _ZN18FuzzedDataProvider22ConsumeIntegralInRangeIhEET_S1_S1_: 205| 81.5k|T FuzzedDataProvider::ConsumeIntegralInRange(T min, T max) { 206| 81.5k| static_assert(std::is_integral::value, "An integral type is required."); 207| 81.5k| static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type."); 208| | 209| 81.5k| if (min > max) ------------------ | Branch (209:7): [True: 0, False: 81.5k] ------------------ 210| 0| abort(); 211| | 212| | // Use the biggest type possible to hold the range and the result. 213| 81.5k| uint64_t range = static_cast(max) - static_cast(min); 214| 81.5k| uint64_t result = 0; 215| 81.5k| size_t offset = 0; 216| | 217| 163k| while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 && ------------------ | Branch (217:10): [True: 81.5k, False: 81.5k] | Branch (217:43): [True: 81.5k, False: 0] ------------------ 218| 163k| remaining_bytes_ != 0) { ------------------ | Branch (218:10): [True: 81.5k, False: 0] ------------------ 219| | // Pull bytes off the end of the seed data. Experimentally, this seems to 220| | // allow the fuzzer to more easily explore the input space. This makes 221| | // sense, since it works by modifying inputs that caused new code to run, 222| | // and this data is often used to encode length of data read by 223| | // |ConsumeBytes|. Separating out read lengths makes it easier modify the 224| | // contents of the data that is actually read. 225| 81.5k| --remaining_bytes_; 226| 81.5k| result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_]; 227| 81.5k| offset += CHAR_BIT; 228| 81.5k| } 229| | 230| | // Avoid division by 0, in case |range + 1| results in overflow. 231| 81.5k| if (range != std::numeric_limits::max()) ------------------ | Branch (231:7): [True: 81.5k, False: 0] ------------------ 232| 81.5k| result = result % (range + 1); 233| | 234| 81.5k| return static_cast(static_cast(min) + result); 235| 81.5k|} _ZN18FuzzedDataProvider15remaining_bytesEv: 85| 82.8k| size_t remaining_bytes() { return remaining_bytes_; } _Z35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEE: 245| 1.32k|{ 246| | // Simulation test to verify the full behavior of DepGraph. 247| | 248| 1.32k| FuzzedDataProvider provider(buffer.data(), buffer.size()); 249| | 250| | /** Real DepGraph being tested. */ 251| 1.32k| DepGraph real; 252| | /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise, 253| | * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */ 254| 1.32k| std::array>, TestBitSet::Size()> sim; 255| | /** The number of non-nullopt position in sim. */ 256| 1.32k| ClusterIndex num_tx_sim{0}; 257| | 258| | /** Read a valid index of a transaction from the provider. */ 259| 1.32k| auto idx_fn = [&]() { 260| 1.32k| auto offset = provider.ConsumeIntegralInRange(0, num_tx_sim - 1); 261| 1.32k| for (ClusterIndex i = 0; i < sim.size(); ++i) { 262| 1.32k| if (!sim[i].has_value()) continue; 263| 1.32k| if (offset == 0) return i; 264| 1.32k| --offset; 265| 1.32k| } 266| 1.32k| assert(false); 267| 1.32k| return ClusterIndex(-1); 268| 1.32k| }; 269| | 270| | /** Read a valid subset of the transactions from the provider. */ 271| 1.32k| auto subset_fn = [&]() { 272| 1.32k| auto range = (uint64_t{1} << num_tx_sim) - 1; 273| 1.32k| const auto mask = provider.ConsumeIntegralInRange(0, range); 274| 1.32k| auto mask_shifted = mask; 275| 1.32k| TestBitSet subset; 276| 1.32k| for (ClusterIndex i = 0; i < sim.size(); ++i) { 277| 1.32k| if (!sim[i].has_value()) continue; 278| 1.32k| if (mask_shifted & 1) { 279| 1.32k| subset.Set(i); 280| 1.32k| } 281| 1.32k| mask_shifted >>= 1; 282| 1.32k| } 283| 1.32k| assert(mask_shifted == 0); 284| 1.32k| return subset; 285| 1.32k| }; 286| | 287| | /** Read any set of transactions from the provider (including unused positions). */ 288| 1.32k| auto set_fn = [&]() { 289| 1.32k| auto range = (uint64_t{1} << sim.size()) - 1; 290| 1.32k| const auto mask = provider.ConsumeIntegralInRange(0, range); 291| 1.32k| TestBitSet set; 292| 1.32k| for (ClusterIndex i = 0; i < sim.size(); ++i) { 293| 1.32k| if ((mask >> i) & 1) { 294| 1.32k| set.Set(i); 295| 1.32k| } 296| 1.32k| } 297| 1.32k| return set; 298| 1.32k| }; 299| | 300| | /** Propagate ancestor information in sim. */ 301| 1.32k| auto anc_update_fn = [&]() { 302| 1.32k| while (true) { 303| 1.32k| bool updates{false}; 304| 1.32k| for (ClusterIndex chl = 0; chl < sim.size(); ++chl) { 305| 1.32k| if (!sim[chl].has_value()) continue; 306| 1.32k| for (auto par : sim[chl]->second) { 307| 1.32k| if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) { 308| 1.32k| sim[chl]->second |= sim[par]->second; 309| 1.32k| updates = true; 310| 1.32k| } 311| 1.32k| } 312| 1.32k| } 313| 1.32k| if (!updates) break; 314| 1.32k| } 315| 1.32k| }; 316| | 317| | /** Compare the state of transaction i in the simulation with the real one. */ 318| 1.32k| auto check_fn = [&](ClusterIndex i) { 319| | // Compare used positions. 320| 1.32k| assert(real.Positions()[i] == sim[i].has_value()); 321| 1.32k| if (sim[i].has_value()) { 322| | // Compare feerate. 323| 1.32k| assert(real.FeeRate(i) == sim[i]->first); 324| | // Compare ancestors (note that SanityCheck verifies correspondence between ancestors 325| | // and descendants, so we can restrict ourselves to ancestors here). 326| 1.32k| assert(real.Ancestors(i) == sim[i]->second); 327| 1.32k| } 328| 1.32k| }; 329| | 330| 81.5k| LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) { ------------------ | | 23| 82.8k| for (unsigned _count{limit}; (condition) && _count; --_count) | | ------------------ | | | Branch (23:34): [True: 81.6k, False: 1.28k] | | | Branch (23:49): [True: 81.5k, False: 44] | | ------------------ ------------------ 331| 81.5k| uint8_t command = provider.ConsumeIntegral(); 332| 81.5k| if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) { ------------------ | Branch (332:13): [True: 2.10k, False: 79.4k] | Branch (332:33): [True: 51.2k, False: 28.2k] | Branch (332:55): [True: 28.8k, False: 22.3k] ------------------ 333| | // AddTransaction. 334| 30.9k| auto fee = provider.ConsumeIntegralInRange(-0x8000000000000, 0x7ffffffffffff); 335| 30.9k| auto size = provider.ConsumeIntegralInRange(1, 0x3fffff); 336| 30.9k| FeeFrac feerate{fee, size}; 337| | // Apply to DepGraph. 338| 30.9k| auto idx = real.AddTransaction(feerate); 339| | // Verify that the returned index is correct. 340| 30.9k| assert(!sim[idx].has_value()); 341| 379k| for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) { ------------------ | Branch (341:38): [True: 379k, False: 0] ------------------ 342| 379k| if (!sim[i].has_value()) { ------------------ | Branch (342:21): [True: 30.9k, False: 348k] ------------------ 343| 30.9k| assert(idx == i); 344| 30.9k| break; 345| 30.9k| } 346| 379k| } 347| | // Update sim. 348| 30.9k| sim[idx] = {feerate, TestBitSet::Singleton(idx)}; 349| 30.9k| ++num_tx_sim; 350| 30.9k| continue; 351| 30.9k| } 352| 50.6k| if ((command % 3) <= 1 && num_tx_sim > 0) { ------------------ | Branch (352:13): [True: 44.5k, False: 6.08k] | Branch (352:35): [True: 44.5k, False: 0] ------------------ 353| | // AddDependencies. 354| 44.5k| ClusterIndex child = idx_fn(); 355| 44.5k| auto parents = subset_fn(); 356| | // Apply to DepGraph. 357| 44.5k| real.AddDependencies(parents, child); 358| | // Apply to sim. 359| 44.5k| sim[child]->second |= parents; 360| 44.5k| continue; 361| 44.5k| } 362| 6.08k| if (num_tx_sim > 0) { ------------------ | Branch (362:13): [True: 6.08k, False: 0] ------------------ 363| | // Remove transactions. 364| 6.08k| auto del = set_fn(); 365| | // Propagate all ancestry information before deleting anything in the simulation (as 366| | // intermediary transactions may be deleted which impact connectivity). 367| 6.08k| anc_update_fn(); 368| | // Compare the state of the transactions being deleted. 369| 82.4k| for (auto i : del) check_fn(i); ------------------ | Branch (369:25): [True: 82.4k, False: 6.08k] ------------------ 370| | // Apply to DepGraph. 371| 6.08k| real.RemoveTransactions(del); 372| | // Apply to sim. 373| 200k| for (ClusterIndex i = 0; i < sim.size(); ++i) { ------------------ | Branch (373:38): [True: 194k, False: 6.08k] ------------------ 374| 194k| if (sim[i].has_value()) { ------------------ | Branch (374:21): [True: 43.9k, False: 150k] ------------------ 375| 43.9k| if (del[i]) { ------------------ | Branch (375:25): [True: 11.4k, False: 32.5k] ------------------ 376| 11.4k| --num_tx_sim; 377| 11.4k| sim[i] = std::nullopt; 378| 32.5k| } else { 379| 32.5k| sim[i]->second -= del; 380| 32.5k| } 381| 43.9k| } 382| 194k| } 383| 6.08k| continue; 384| 6.08k| } 385| | // This should be unreachable (one of the 3 above actions should always be possible). 386| 0| assert(false); 387| 0| } 388| | 389| | // Compare the real obtained depgraph against the simulation. 390| 1.32k| anc_update_fn(); 391| 43.7k| for (ClusterIndex i = 0; i < sim.size(); ++i) check_fn(i); ------------------ | Branch (391:30): [True: 42.4k, False: 1.32k] ------------------ 392| 1.32k| assert(real.TxCount() == num_tx_sim); 393| | // Sanity check the result (which includes round-tripping serialization, if applicable). 394| 1.32k| SanityCheck(real); 395| 1.32k|} cluster_linearize.cpp:_ZZ35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_0clEv: 259| 44.5k| auto idx_fn = [&]() { 260| 44.5k| auto offset = provider.ConsumeIntegralInRange(0, num_tx_sim - 1); 261| 276k| for (ClusterIndex i = 0; i < sim.size(); ++i) { ------------------ | Branch (261:34): [True: 276k, False: 0] ------------------ 262| 276k| if (!sim[i].has_value()) continue; ------------------ | Branch (262:17): [True: 18.7k, False: 257k] ------------------ 263| 257k| if (offset == 0) return i; ------------------ | Branch (263:17): [True: 44.5k, False: 212k] ------------------ 264| 212k| --offset; 265| 212k| } 266| 0| assert(false); 267| 0| return ClusterIndex(-1); 268| 0| }; cluster_linearize.cpp:_ZZ35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_1clEv: 271| 44.5k| auto subset_fn = [&]() { 272| 44.5k| auto range = (uint64_t{1} << num_tx_sim) - 1; 273| 44.5k| const auto mask = provider.ConsumeIntegralInRange(0, range); 274| 44.5k| auto mask_shifted = mask; 275| 44.5k| TestBitSet subset; 276| 1.46M| for (ClusterIndex i = 0; i < sim.size(); ++i) { ------------------ | Branch (276:34): [True: 1.42M, False: 44.5k] ------------------ 277| 1.42M| if (!sim[i].has_value()) continue; ------------------ | Branch (277:17): [True: 429k, False: 995k] ------------------ 278| 995k| if (mask_shifted & 1) { ------------------ | Branch (278:17): [True: 173k, False: 821k] ------------------ 279| 173k| subset.Set(i); 280| 173k| } 281| 995k| mask_shifted >>= 1; 282| 995k| } 283| 44.5k| assert(mask_shifted == 0); 284| 44.5k| return subset; 285| 44.5k| }; cluster_linearize.cpp:_ZZ35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_2clEv: 288| 6.08k| auto set_fn = [&]() { 289| 6.08k| auto range = (uint64_t{1} << sim.size()) - 1; 290| 6.08k| const auto mask = provider.ConsumeIntegralInRange(0, range); 291| 6.08k| TestBitSet set; 292| 200k| for (ClusterIndex i = 0; i < sim.size(); ++i) { ------------------ | Branch (292:34): [True: 194k, False: 6.08k] ------------------ 293| 194k| if ((mask >> i) & 1) { ------------------ | Branch (293:17): [True: 82.4k, False: 112k] ------------------ 294| 82.4k| set.Set(i); 295| 82.4k| } 296| 194k| } 297| 6.08k| return set; 298| 6.08k| }; cluster_linearize.cpp:_ZZ35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_3clEv: 301| 7.40k| auto anc_update_fn = [&]() { 302| 9.10k| while (true) { ------------------ | Branch (302:16): [Folded - Ignored] ------------------ 303| 9.10k| bool updates{false}; 304| 300k| for (ClusterIndex chl = 0; chl < sim.size(); ++chl) { ------------------ | Branch (304:40): [True: 291k, False: 9.10k] ------------------ 305| 291k| if (!sim[chl].has_value()) continue; ------------------ | Branch (305:21): [True: 195k, False: 96.1k] ------------------ 306| 404k| for (auto par : sim[chl]->second) { ------------------ | Branch (306:31): [True: 404k, False: 96.1k] ------------------ 307| 404k| if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) { ------------------ | Branch (307:25): [True: 9.66k, False: 394k] ------------------ 308| 9.66k| sim[chl]->second |= sim[par]->second; 309| 9.66k| updates = true; 310| 9.66k| } 311| 404k| } 312| 96.1k| } 313| 9.10k| if (!updates) break; ------------------ | Branch (313:17): [True: 7.40k, False: 1.70k] ------------------ 314| 9.10k| } 315| 7.40k| }; cluster_linearize.cpp:_ZZ35clusterlin_depgraph_sim_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_4clEj: 318| 124k| auto check_fn = [&](ClusterIndex i) { 319| | // Compare used positions. 320| 124k| assert(real.Positions()[i] == sim[i].has_value()); 321| 124k| if (sim[i].has_value()) { ------------------ | Branch (321:13): [True: 30.9k, False: 93.8k] ------------------ 322| | // Compare feerate. 323| 30.9k| assert(real.FeeRate(i) == sim[i]->first); 324| | // Compare ancestors (note that SanityCheck verifies correspondence between ancestors 325| | // and descendants, so we can restrict ourselves to ancestors here). 326| 30.9k| assert(real.Ancestors(i) == sim[i]->second); 327| 30.9k| } 328| 124k| }; LLVMFuzzerTestOneInput: 222| 1.32k|{ 223| 1.32k| test_one_input({data, size}); 224| 1.32k| return 0; 225| 1.32k|} fuzz.cpp:_ZL14test_one_inputNSt3__14spanIKhLm18446744073709551615EEE: 83| 1.32k|{ 84| 1.32k| CheckGlobals check{}; 85| 1.32k| (*Assert(g_test_one_input))(buffer); ------------------ | | 85| 1.32k|#define Assert(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 86| 1.32k|} _ZN12CheckGlobalsC2Ev: 56| 1.32k|CheckGlobals::CheckGlobals() : m_impl(std::make_unique()) {} _ZN12CheckGlobalsD2Ev: 57| 1.32k|CheckGlobals::~CheckGlobals() = default; _ZN16CheckGlobalsImplC2Ev: 17| 1.32k| { 18| 1.32k| g_used_g_prng = false; 19| 1.32k| g_seeded_g_prng_zero = false; 20| 1.32k| g_used_system_time = false; 21| 1.32k| SetMockTime(0s); 22| 1.32k| } _ZN16CheckGlobalsImplD2Ev: 24| 1.32k| { 25| 1.32k| if (g_used_g_prng && !g_seeded_g_prng_zero) { ------------------ | Branch (25:13): [True: 0, False: 1.32k] | Branch (25:30): [True: 0, False: 0] ------------------ 26| 0| std::cerr << "\n\n" 27| 0| "The current fuzz target used the global random state.\n\n" 28| | 29| 0| "This is acceptable, but requires the fuzz target to call \n" 30| 0| "SeedRandomStateForTest(SeedRand::ZEROS) in the first line \n" 31| 0| "of the FUZZ_TARGET function.\n\n" 32| | 33| 0| "An alternative solution would be to avoid any use of globals.\n\n" 34| | 35| 0| "Without a solution, fuzz instability and non-determinism can lead \n" 36| 0| "to non-reproducible bugs or inefficient fuzzing.\n\n" 37| 0| << std::endl; 38| 0| std::abort(); // Abort, because AFL may try to recover from a std::exit 39| 0| } 40| | 41| 1.32k| if (g_used_system_time) { ------------------ | Branch (41:13): [True: 0, False: 1.32k] ------------------ 42| 0| std::cerr << "\n\n" 43| 0| "The current fuzz target accessed system time.\n\n" 44| | 45| 0| "This is acceptable, but requires the fuzz target to call \n" 46| 0| "SetMockTime() at the beginning of processing the fuzz input.\n\n" 47| | 48| 0| "Without setting mock time, time-dependent behavior can lead \n" 49| 0| "to non-reproducible bugs or inefficient fuzzing.\n\n" 50| 0| << std::endl; 51| 0| std::abort(); 52| 0| } 53| 1.32k| } cluster_linearize.cpp:_ZN12_GLOBAL__N_111SanityCheckIN13bitset_detail9IntBitSetIjEEEEvRKN17cluster_linearize8DepGraphIT_EE: 299| 1.32k|{ 300| | // Verify Positions and PositionRange consistency. 301| 1.32k| ClusterIndex num_positions{0}; 302| 1.32k| ClusterIndex position_range{0}; 303| 19.5k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (303:25): [True: 19.5k, False: 1.32k] ------------------ 304| 19.5k| ++num_positions; 305| 19.5k| position_range = i + 1; 306| 19.5k| } 307| 1.32k| assert(num_positions == depgraph.TxCount()); 308| 1.32k| assert(position_range == depgraph.PositionRange()); 309| 1.32k| assert(position_range >= num_positions); 310| 1.32k| assert(position_range <= SetType::Size()); 311| | // Consistency check between ancestors internally. 312| 19.5k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (312:25): [True: 19.5k, False: 1.32k] ------------------ 313| | // Transactions include themselves as ancestors. 314| 19.5k| 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| 73.0k| for (auto a : depgraph.Ancestors(i)) { ------------------ | Branch (316:21): [True: 73.0k, False: 19.5k] ------------------ 317| 73.0k| assert(depgraph.Ancestors(i).IsSupersetOf(depgraph.Ancestors(a))); 318| 73.0k| } 319| 19.5k| } 320| | // Consistency check between ancestors and descendants. 321| 19.5k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (321:25): [True: 19.5k, False: 1.32k] ------------------ 322| 496k| for (ClusterIndex j : depgraph.Positions()) { ------------------ | Branch (322:29): [True: 496k, False: 19.5k] ------------------ 323| 496k| assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]); 324| 496k| } 325| | // No transaction is a parent or child of itself. 326| 19.5k| auto parents = depgraph.GetReducedParents(i); 327| 19.5k| auto children = depgraph.GetReducedChildren(i); 328| 19.5k| assert(!parents[i]); 329| 19.5k| 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| 19.5k| for (auto parent : parents) { ------------------ | Branch (332:26): [True: 12.3k, False: 19.5k] ------------------ 333| 12.3k| assert((depgraph.Ancestors(parent) & parents).IsSubsetOf(SetType::Singleton(parent))); 334| 12.3k| } 335| | // Similar for children and descendants. 336| 19.5k| for (auto child : children) { ------------------ | Branch (336:25): [True: 14.9k, False: 19.5k] ------------------ 337| 14.9k| assert((depgraph.Descendants(child) & children).IsSubsetOf(SetType::Singleton(child))); 338| 14.9k| } 339| 19.5k| } 340| 1.32k| if (IsAcyclic(depgraph)) { ------------------ | Branch (340:9): [True: 1.08k, False: 243] ------------------ 341| | // If DepGraph is acyclic, serialize + deserialize must roundtrip. 342| 1.08k| std::vector ser; 343| 1.08k| VectorWriter writer(ser, 0); 344| 1.08k| writer << Using(depgraph); 345| 1.08k| SpanReader reader(ser); 346| 1.08k| DepGraph decoded_depgraph; 347| 1.08k| reader >> Using(decoded_depgraph); 348| 1.08k| assert(depgraph == decoded_depgraph); 349| 1.08k| 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| 1.08k| assert(ser.size() >= 1 && ser.back() == 0); 353| 1.08k| ser.pop_back(); 354| 1.08k| reader = SpanReader{ser}; 355| 1.08k| decoded_depgraph = {}; 356| 1.08k| reader >> Using(decoded_depgraph); 357| 1.08k| assert(depgraph == decoded_depgraph); 358| 1.08k| 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| 1.08k| std::vector parents(depgraph.PositionRange()), children(depgraph.PositionRange()); 363| 14.6k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (363:29): [True: 14.6k, False: 1.08k] ------------------ 364| 14.6k| parents[i] = depgraph.GetReducedParents(i); 365| 14.6k| children[i] = depgraph.GetReducedChildren(i); 366| 14.6k| } 367| 14.6k| for (auto i : depgraph.Positions()) { ------------------ | Branch (367:21): [True: 14.6k, False: 1.08k] ------------------ 368| | // Initialize the set of ancestors with just the current transaction itself. 369| 14.6k| SetType ancestors = SetType::Singleton(i); 370| | // Iteratively add parents of all transactions in the ancestor set to itself. 371| 19.0k| while (true) { ------------------ | Branch (371:20): [Folded - Ignored] ------------------ 372| 19.0k| const auto old_ancestors = ancestors; 373| 45.2k| for (auto j : ancestors) ancestors |= parents[j]; ------------------ | Branch (373:29): [True: 45.2k, False: 19.0k] ------------------ 374| | // Stop when no more changes are being made. 375| 19.0k| if (old_ancestors == ancestors) break; ------------------ | Branch (375:21): [True: 14.6k, False: 4.39k] ------------------ 376| 19.0k| } 377| 14.6k| assert(ancestors == depgraph.Ancestors(i)); 378| | 379| | // Initialize the set of descendants with just the current transaction itself. 380| 14.6k| SetType descendants = SetType::Singleton(i); 381| | // Iteratively add children of all transactions in the descendant set to itself. 382| 26.0k| while (true) { ------------------ | Branch (382:20): [Folded - Ignored] ------------------ 383| 26.0k| const auto old_descendants = descendants; 384| 54.8k| for (auto j : descendants) descendants |= children[j]; ------------------ | Branch (384:29): [True: 54.8k, False: 26.0k] ------------------ 385| | // Stop when no more changes are being made. 386| 26.0k| if (old_descendants == descendants) break; ------------------ | Branch (386:21): [True: 14.6k, False: 11.3k] ------------------ 387| 26.0k| } 388| 14.6k| assert(descendants == depgraph.Descendants(i)); 389| 14.6k| } 390| 1.08k| } 391| 1.32k|} cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter3SerI12VectorWriterN13bitset_detail9IntBitSetIjEEEEvRT_RKN17cluster_linearize8DepGraphIT0_EE: 135| 1.08k| { 136| | /** Construct a topological order to serialize the transactions in. */ 137| 1.08k| std::vector topo_order; 138| 1.08k| topo_order.reserve(depgraph.TxCount()); 139| 14.6k| for (auto i : depgraph.Positions()) topo_order.push_back(i); ------------------ | Branch (139:21): [True: 14.6k, False: 1.08k] ------------------ 140| 1.08k| std::sort(topo_order.begin(), topo_order.end(), [&](ClusterIndex a, ClusterIndex b) { 141| 1.08k| auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count(); 142| 1.08k| if (anc_a != anc_b) return anc_a < anc_b; 143| 1.08k| return a < b; 144| 1.08k| }); 145| | 146| | /** Which positions (incl. holes) the deserializer already knows when it has deserialized 147| | * what has been serialized here so far. */ 148| 1.08k| SetType done; 149| | 150| | // Loop over the transactions in topological order. 151| 15.7k| for (ClusterIndex topo_idx = 0; topo_idx < topo_order.size(); ++topo_idx) { ------------------ | Branch (151:41): [True: 14.6k, False: 1.08k] ------------------ 152| | /** Which depgraph index we are currently writing. */ 153| 14.6k| ClusterIndex idx = topo_order[topo_idx]; 154| | // Write size, which must be larger than 0. 155| 14.6k| s << VARINT_MODE(depgraph.FeeRate(idx).size, VarIntMode::NONNEGATIVE_SIGNED); ------------------ | | 499| 14.6k|#define VARINT_MODE(obj, mode) Using>(obj) ------------------ 156| | // Write fee, encoded as an unsigned varint (odd=negative, even=non-negative). 157| 14.6k| s << VARINT(SignedToUnsigned(depgraph.FeeRate(idx).fee)); ------------------ | | 500| 14.6k|#define VARINT(obj) Using>(obj) ------------------ 158| | // Write dependency information. 159| 14.6k| SetType written_parents; 160| 14.6k| uint64_t diff = 0; //!< How many potential parent/child relations we have skipped over. 161| 190k| for (ClusterIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) { ------------------ | Branch (161:45): [True: 176k, False: 14.6k] ------------------ 162| | /** Which depgraph index we are currently considering as parent of idx. */ 163| 176k| ClusterIndex dep_idx = topo_order[topo_idx - 1 - dep_dist]; 164| | // Ignore transactions which are already known to be ancestors. 165| 176k| if (depgraph.Descendants(dep_idx).Overlaps(written_parents)) continue; ------------------ | Branch (165:21): [True: 5.95k, False: 170k] ------------------ 166| 170k| if (depgraph.Ancestors(idx)[dep_idx]) { ------------------ | Branch (166:21): [True: 10.2k, False: 159k] ------------------ 167| | // When an actual parent is encountered, encode how many non-parents were skipped 168| | // before it. 169| 10.2k| s << VARINT(diff); ------------------ | | 500| 10.2k|#define VARINT(obj) Using>(obj) ------------------ 170| 10.2k| diff = 0; 171| 10.2k| written_parents.Set(dep_idx); 172| 159k| } else { 173| | // When a non-parent is encountered, increment the skip counter. 174| 159k| ++diff; 175| 159k| } 176| 170k| } 177| | // Write position information. 178| 14.6k| auto add_holes = SetType::Fill(idx) - done - depgraph.Positions(); 179| 14.6k| if (add_holes.None()) { ------------------ | Branch (179:17): [True: 14.2k, False: 422] ------------------ 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| 14.2k| auto skips = (done - SetType::Fill(idx)).Count(); 183| 14.2k| s << VARINT(diff + skips); ------------------ | | 500| 14.2k|#define VARINT(obj) Using>(obj) ------------------ 184| 14.2k| } 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| 422| s << VARINT(diff + done.Count() + add_holes.Count()); ------------------ | | 500| 422|#define VARINT(obj) Using>(obj) ------------------ 189| 422| done |= add_holes; 190| 422| } 191| 14.6k| done.Set(idx); 192| 14.6k| } 193| | 194| | // Output a final 0 to denote the end of the graph. 195| 1.08k| s << uint8_t{0}; 196| 1.08k| } cluster_linearize.cpp:_ZZN12_GLOBAL__N_117DepGraphFormatter3SerI12VectorWriterN13bitset_detail9IntBitSetIjEEEEvRT_RKN17cluster_linearize8DepGraphIT0_EEENKUljjE_clEjj: 140| 456k| std::sort(topo_order.begin(), topo_order.end(), [&](ClusterIndex a, ClusterIndex b) { 141| 456k| auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count(); 142| 456k| if (anc_a != anc_b) return anc_a < anc_b; ------------------ | Branch (142:17): [True: 98.0k, False: 358k] ------------------ 143| 358k| return a < b; 144| 456k| }); cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter16SignedToUnsignedEl: 115| 14.6k| { 116| 14.6k| if (x < 0) { ------------------ | Branch (116:13): [True: 8.66k, False: 6.00k] ------------------ 117| 8.66k| return 2 * uint64_t(-(x + 1)) + 1; 118| 8.66k| } else { 119| 6.00k| return 2 * uint64_t(x); 120| 6.00k| } 121| 14.6k| } cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter5UnserI10SpanReaderN13bitset_detail9IntBitSetIjEEEEvRT_RN17cluster_linearize8DepGraphIT0_EE: 200| 2.16k| { 201| | /** The dependency graph which we deserialize into first, with transactions in 202| | * topological serialization order, not original cluster order. */ 203| 2.16k| DepGraph topo_depgraph; 204| | /** Mapping from serialization order to cluster order, used later to reconstruct the 205| | * cluster order. */ 206| 2.16k| std::vector reordering; 207| | /** How big the entries vector in the reconstructed depgraph will be (including holes). */ 208| 2.16k| ClusterIndex total_size{0}; 209| | 210| | // Read transactions in topological order. 211| 31.5k| while (true) { ------------------ | Branch (211:16): [Folded - Ignored] ------------------ 212| 31.5k| FeeFrac new_feerate; //!< The new transaction's fee and size. 213| 31.5k| SetType new_ancestors; //!< The new transaction's ancestors (excluding itself). 214| 31.5k| uint64_t diff{0}; //!< How many potential parents/insertions we have to skip. 215| 31.5k| bool read_error{false}; 216| 31.5k| try { 217| | // Read size. Size 0 signifies the end of the DepGraph. 218| 31.5k| int32_t size; 219| 31.5k| s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED); ------------------ | | 499| 31.5k|#define VARINT_MODE(obj, mode) Using>(obj) ------------------ 220| 31.5k| size &= 0x3FFFFF; // Enough for size up to 4M. 221| 31.5k| static_assert(0x3FFFFF >= 4000000); 222| 31.5k| if (size == 0 || topo_depgraph.TxCount() == SetType::Size()) break; ------------------ | Branch (222:21): [True: 2.16k, False: 29.3k] | Branch (222:34): [True: 0, False: 29.3k] ------------------ 223| | // Read fee, encoded as an unsigned varint (odd=negative, even=non-negative). 224| 30.4k| uint64_t coded_fee; 225| 30.4k| s >> VARINT(coded_fee); ------------------ | | 500| 30.4k|#define VARINT(obj) Using>(obj) ------------------ 226| 30.4k| coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC. 227| 30.4k| static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000); 228| 30.4k| new_feerate = {UnsignedToSigned(coded_fee), size}; 229| | // Read dependency information. 230| 30.4k| auto topo_idx = reordering.size(); 231| 30.4k| s >> VARINT(diff); ------------------ | | 500| 30.4k|#define VARINT(obj) Using>(obj) ------------------ 232| 382k| for (ClusterIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) { ------------------ | Branch (232:49): [True: 352k, False: 30.4k] ------------------ 233| | /** Which topo_depgraph index we are currently considering as parent of topo_idx. */ 234| 352k| ClusterIndex dep_topo_idx = topo_idx - 1 - dep_dist; 235| | // Ignore transactions which are already known ancestors of topo_idx. 236| 352k| if (new_ancestors[dep_topo_idx]) continue; ------------------ | Branch (236:25): [True: 11.9k, False: 340k] ------------------ 237| 340k| if (diff == 0) { ------------------ | Branch (237:25): [True: 20.5k, False: 319k] ------------------ 238| | // When the skip counter has reached 0, add an actual dependency. 239| 20.5k| new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx); 240| | // And read the number of skips after it. 241| 20.5k| s >> VARINT(diff); ------------------ | | 500| 20.5k|#define VARINT(obj) Using>(obj) ------------------ 242| 319k| } else { 243| | // Otherwise, dep_topo_idx is not a parent. Decrement and continue. 244| 319k| --diff; 245| 319k| } 246| 340k| } 247| 30.4k| } catch (const std::ios_base::failure&) { 248| | // Continue even if a read error was encountered. 249| 1.08k| read_error = true; 250| 1.08k| } 251| | // Construct a new transaction whenever we made it past the new_feerate construction. 252| 30.4k| if (new_feerate.IsEmpty()) break; ------------------ | Branch (252:17): [True: 1.08k, False: 29.3k] ------------------ 253| 29.3k| assert(reordering.size() < SetType::Size()); 254| 29.3k| auto topo_idx = topo_depgraph.AddTransaction(new_feerate); 255| 29.3k| topo_depgraph.AddDependencies(new_ancestors, topo_idx); 256| 29.3k| if (total_size < SetType::Size()) { ------------------ | Branch (256:17): [True: 29.3k, False: 0] ------------------ 257| | // Normal case. 258| 29.3k| diff %= SetType::Size(); 259| 29.3k| if (diff <= total_size) { ------------------ | Branch (259:21): [True: 28.4k, False: 844] ------------------ 260| | // Insert the new transaction at distance diff back from the end. 261| 349k| for (auto& pos : reordering) { ------------------ | Branch (261:36): [True: 349k, False: 28.4k] ------------------ 262| 349k| pos += (pos >= total_size - diff); 263| 349k| } 264| 28.4k| reordering.push_back(total_size++ - diff); 265| 28.4k| } else { 266| | // Append diff - total_size holes at the end, plus the new transaction. 267| 844| total_size = diff; 268| 844| reordering.push_back(total_size++); 269| 844| } 270| 29.3k| } 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| 0| diff %= (SetType::Size() - reordering.size()); 277| 0| SetType holes = SetType::Fill(SetType::Size()); 278| 0| for (auto pos : reordering) holes.Reset(pos); ------------------ | Branch (278:31): [True: 0, False: 0] ------------------ 279| 0| for (auto pos : holes) { ------------------ | Branch (279:31): [True: 0, False: 0] ------------------ 280| 0| if (diff == 0) { ------------------ | Branch (280:25): [True: 0, False: 0] ------------------ 281| 0| reordering.push_back(pos); 282| 0| break; 283| 0| } 284| 0| --diff; 285| 0| } 286| 0| } 287| | // Stop if a read error was encountered during deserialization. 288| 29.3k| if (read_error) break; ------------------ | Branch (288:17): [True: 0, False: 29.3k] ------------------ 289| 29.3k| } 290| | 291| | // Construct the original cluster order depgraph. 292| 2.16k| depgraph = DepGraph(topo_depgraph, reordering, total_size); 293| 2.16k| } cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter16UnsignedToSignedEm: 125| 29.3k| { 126| 29.3k| if (x & 1) { ------------------ | Branch (126:13): [True: 17.3k, False: 12.0k] ------------------ 127| 17.3k| return -int64_t(x / 2) - 1; 128| 17.3k| } else { 129| 12.0k| return int64_t(x / 2); 130| 12.0k| } 131| 29.3k| } cluster_linearize.cpp:_ZN12_GLOBAL__N_19IsAcyclicIN13bitset_detail9IntBitSetIjEEEEbRKN17cluster_linearize8DepGraphIT_EE: 29| 1.32k|{ 30| 15.3k| for (ClusterIndex i : depgraph.Positions()) { ------------------ | Branch (30:25): [True: 15.3k, False: 1.08k] ------------------ 31| 15.3k| if ((depgraph.Ancestors(i) & depgraph.Descendants(i)) != SetType::Singleton(i)) { ------------------ | Branch (31:13): [True: 243, False: 15.1k] ------------------ 32| 243| return false; 33| 243| } 34| 15.3k| } 35| 1.08k| return true; 36| 1.32k|} _ZN13bitset_detail9IntBitSetIjE4SizeEv: 177| 549k| static constexpr unsigned Size() noexcept { return MAX_SIZE; } _ZNK13bitset_detail9IntBitSetIjEixEj: 170| 2.02M| { 171| 2.02M| Assume(pos < MAX_SIZE); ------------------ | | 97| 2.02M|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 172| 2.02M| return (m_val >> pos) & 1U; 173| 2.02M| } _ZN13bitset_detail9IntBitSetIjE3SetEj: 152| 480k| { 153| 480k| Assume(pos < MAX_SIZE); ------------------ | | 97| 480k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 154| 480k| m_val |= I{1U} << pos; 155| 480k| } _ZN13bitset_detail9IntBitSetIjE5ResetEj: 164| 97.7k| { 165| 97.7k| Assume(pos < MAX_SIZE); ------------------ | | 97| 97.7k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 166| 97.7k| m_val &= ~I(I{1U} << pos); 167| 97.7k| } _ZN13bitset_detail9IntBitSetIjE9SingletonEj: 138| 282k| { 139| 282k| Assume(i < MAX_SIZE); ------------------ | | 97| 282k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 140| 282k| return IntBitSet(I(1U) << i); 141| 282k| } _ZN13bitset_detail9IntBitSetIjEC2Ej: 71| 531k| IntBitSet(I val) noexcept : m_val{val} {} _ZNK13bitset_detail9IntBitSetIjE3AnyEv: 181| 60.2k| constexpr bool Any() const noexcept { return !None(); } _ZNK13bitset_detail9IntBitSetIjE4NoneEv: 179| 180k| constexpr bool None() const noexcept { return m_val == 0; } _ZNK13bitset_detail9IntBitSetIjE5FirstEv: 188| 60.2k| { 189| 60.2k| Assume(m_val != 0); ------------------ | | 97| 60.2k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 190| 60.2k| return std::countr_zero(m_val); 191| 60.2k| } _ZNK13bitset_detail9IntBitSetIjE4LastEv: 194| 2.05k| { 195| 2.05k| Assume(m_val != 0); ------------------ | | 97| 2.05k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 196| 2.05k| return std::bit_width(m_val) - 1; 197| 2.05k| } _ZNK13bitset_detail9IntBitSetIjE5CountEv: 175| 962k| constexpr unsigned Count() const noexcept { return PopCount(m_val); } _ZN13bitset_detail8PopCountIjEEjT_: 39| 962k|{ 40| 962k| static_assert(std::is_integral_v && std::is_unsigned_v && std::numeric_limits::radix == 2); 41| 962k| constexpr auto BITS = std::numeric_limits::digits; 42| | // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation. 43| | // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64. 44| 962k| if constexpr (BITS <= 32) { 45| 962k| v -= (v >> 1) & 0x55555555; 46| 962k| v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 47| 962k| v = (v + (v >> 4)) & 0x0f0f0f0f; 48| 962k| if constexpr (BITS > 8) v += v >> 8; 49| 962k| if constexpr (BITS > 16) v += v >> 16; 50| 962k| return v & 0x3f; 51| | } else { 52| | static_assert(BITS <= 64); 53| | v -= (v >> 1) & 0x5555555555555555; 54| | v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); 55| | v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f; 56| | return (v * uint64_t{0x0101010101010101}) >> 56; 57| | } 58| 962k|} _ZN13bitset_detail9IntBitSetIjEC2Ev: 119| 365k| constexpr IntBitSet() noexcept : m_val{0} {} _ZN13bitset_detail9IntBitSetIjE4FillEj: 144| 28.9k| { 145| 28.9k| IntBitSet ret; 146| 28.9k| Assume(count <= MAX_SIZE); ------------------ | | 97| 28.9k|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 147| 28.9k| if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count); ------------------ | Branch (147:13): [True: 27.0k, False: 1.85k] ------------------ 148| 28.9k| return ret; 149| 28.9k| } _ZNK13bitset_detail9IntBitSetIjE5beginEv: 183| 507k| constexpr Iterator begin() const noexcept { return Iterator(m_val); } _ZN13bitset_detail9IntBitSetIjE8IteratorC2Ej: 86| 507k| constexpr Iterator(I val) noexcept : m_val(val), m_pos(0) 87| 507k| { 88| 507k| if (m_val != 0) m_pos = std::countr_zero(m_val); ------------------ | Branch (88:17): [True: 309k, False: 198k] ------------------ 89| 507k| } _ZN13bitset_detaileqERKNS_9IntBitSetIjE8IteratorERKNS1_11IteratorEndE: 98| 2.35M| { 99| 2.35M| return a.m_val == 0; 100| 2.35M| } _ZNK13bitset_detail9IntBitSetIjE3endEv: 185| 507k| constexpr IteratorEnd end() const noexcept { return IteratorEnd(); } _ZNK13bitset_detail9IntBitSetIjE8IteratordeEv: 111| 1.84M| { 112| 1.84M| Assume(m_val != 0); ------------------ | | 97| 1.84M|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 113| 1.84M| return m_pos; 114| 1.84M| } _ZN13bitset_detail9IntBitSetIjE8IteratorppEv: 103| 1.84M| { 104| 1.84M| Assume(m_val != 0); ------------------ | | 97| 1.84M|#define Assume(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 105| 1.84M| m_val &= m_val - I{1U}; 106| 1.84M| if (m_val != 0) m_pos = std::countr_zero(m_val); ------------------ | Branch (106:17): [True: 1.53M, False: 308k] ------------------ 107| 1.84M| return *this; 108| 1.84M| } _ZN13bitset_detail9IntBitSetIjEoRERKS1_: 199| 435k| constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; } _ZN13bitset_detail9IntBitSetIjEaNERKS1_: 201| 121k| constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; } _ZN13bitset_detail9IntBitSetIjEmIERKS1_: 203| 231k| constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; } _ZN13bitset_detailanERKNS_9IntBitSetIjEES3_: 209| 42.6k| friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); } _ZN13bitset_detailmiERKNS_9IntBitSetIjEES3_: 213| 207k| friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); } _ZNK13bitset_detail9IntBitSetIjE12IsSupersetOfERKS1_: 219| 477k| constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; } _ZNK13bitset_detail9IntBitSetIjE10IsSubsetOfERKS1_: 221| 130k| constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; } _ZN13bitset_detaileqERKNS_9IntBitSetIjEES3_: 217| 181k| friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default; _ZNK13bitset_detail9IntBitSetIjE8OverlapsERKS1_: 207| 176k| constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; } _Z22inline_assertion_checkILb0EbEOT0_S1_PKciS3_S3_: 52| 6.96M|{ 53| 6.96M| if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING ------------------ | Branch (53:9): [Folded - Ignored] | Branch (53:22): [Folded - Ignored] | Branch (53:54): [Folded - Ignored] ------------------ 54| |#ifdef ABORT_ON_FAILED_ASSUME 55| | || true 56| |#endif 57| 6.96M| ) { 58| 6.96M| if (!val) { ------------------ | Branch (58:13): [True: 0, False: 6.96M] ------------------ 59| 0| assertion_fail(file, line, func, assertion); 60| 0| } 61| 6.96M| } 62| 6.96M| return std::forward(val); 63| 6.96M|} _Z22inline_assertion_checkILb1EbEOT0_S1_PKciS3_S3_: 52| 1.32k|{ 53| 1.32k| if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING ------------------ | Branch (53:9): [Folded - Ignored] | Branch (53:22): [Folded - Ignored] | Branch (53:54): [Folded - Ignored] ------------------ 54| |#ifdef ABORT_ON_FAILED_ASSUME 55| | || true 56| |#endif 57| 1.32k| ) { 58| 1.32k| if (!val) { ------------------ | Branch (58:13): [True: 0, False: 1.32k] ------------------ 59| 0| assertion_fail(file, line, func, assertion); 60| 0| } 61| 1.32k| } 62| 1.32k| return std::forward(val); 63| 1.32k|} _Z22inline_assertion_checkILb1ERPKNSt3__18functionIFvNS0_4spanIKhLm18446744073709551615EEEEEEEOT0_SB_PKciSD_SD_: 52| 1.32k|{ 53| 1.32k| if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING ------------------ | Branch (53:9): [Folded - Ignored] | Branch (53:22): [Folded - Ignored] | Branch (53:54): [Folded - Ignored] ------------------ 54| |#ifdef ABORT_ON_FAILED_ASSUME 55| | || true 56| |#endif 57| 1.32k| ) { 58| 1.32k| if (!val) { ------------------ | Branch (58:13): [True: 0, False: 1.32k] ------------------ 59| 0| assertion_fail(file, line, func, assertion); 60| 0| } 61| 1.32k| } 62| 1.32k| return std::forward(val); 63| 1.32k|} _ZN7FeeFracC2Ev: 67| 64.2k| constexpr inline FeeFrac() noexcept : fee{0}, size{0} {} _ZN7FeeFracC2Eli: 70| 60.2k| constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {} _ZNK7FeeFrac7IsEmptyEv: 76| 30.4k| bool inline IsEmpty() const noexcept { 77| 30.4k| return size == 0; 78| 30.4k| } _ZeqRK7FeeFracS1_: 108| 60.2k| { 109| 60.2k| return a.fee == b.fee && a.size == b.size; ------------------ | Branch (109:16): [True: 60.2k, False: 0] | Branch (109:34): [True: 60.2k, False: 0] ------------------ 110| 60.2k| } _Z11SetMockTimeNSt3__16chrono8durationIxNS_5ratioILl1ELl1EEEEE: 42| 1.32k|{ 43| 1.32k| Assert(mock_time_in >= 0s); ------------------ | | 85| 1.32k|#define Assert(val) inline_assertion_check(val, __FILE__, __LINE__, __func__, #val) ------------------ 44| 1.32k| g_mock_time.store(mock_time_in, std::memory_order_relaxed); 45| 1.32k|}