refactor: add overflow-safe CeilDiv helper and use it in unsigned callsites #34436

pull l0rinc wants to merge 1 commits into bitcoin:master from l0rinc:l0rinc/ceildiv-utxo-flush-gib changing 15 files +85 −19
  1. l0rinc commented at 9:47 pm on January 28, 2026: contributor

    Problem

    The codebase has many open-coded ceiling-division expressions (for example (x+y-1)/y) scattered across files. These are less readable, duplicate logic, and can be overflow-prone in edge cases.

    Fix

    Introduce a small overflow-safe integer helper, CeilDiv(), and use it in existing unsigned callsites where the conversion is straightforward and noise-free.

    What this PR does

    • Adds CeilDiv() to src/util/overflow.h for unsigned integral inputs.
    • Keeps the precondition check assert(divisor > 0).
    • Replaces selected unsigned ceiling-division expressions with CeilDiv(...).
    • Adds focused unit tests in src/test/util_tests.cpp for the migrated patterns.

    This is a pure refactor with no intended behavioral change. Signed arithmetic callsites are intentionally left unchanged in this PR. This PR changed a few more things originally but based on feedback reverted to the simplest cases only.

  2. DrahtBot commented at 9:47 pm on January 28, 2026: contributor

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK hodlinator

    If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #34628 (p2p: Replace per-peer transaction rate-limiting with global rate limits by ajtowns)
    • #31868 ([IBD] specialize block serialization by l0rinc)
    • #29678 (Bugfix: Correct first-run free space checks by luke-jr)

    If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

  3. DrahtBot added the label CI failed on Jan 28, 2026
  4. DrahtBot commented at 10:44 pm on January 28, 2026: contributor

    🚧 At least one of the CI tasks failed. Task tidy: https://github.com/bitcoin/bitcoin/actions/runs/21456706302/job/61799208927 LLM reason (✨ experimental): Link-time failure: arith_uint256.cpp.o depends on check.cpp.o symbol assertion_fail, triggering an “Unexpected dependencies were detected” error.

    Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

    • Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

    • A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

    • An intermittent issue.

    Leave a comment here, if you need help tracking down a confusing failure.

  5. l0rinc force-pushed on Jan 28, 2026
  6. l0rinc force-pushed on Jan 29, 2026
  7. l0rinc force-pushed on Jan 29, 2026
  8. fanquake commented at 11:18 am on January 29, 2026: member

    https://github.com/bitcoin/bitcoin/actions/runs/21474548168/job/61856382435?pr=34436#step:11:2456:

    0 fuzz: util/overflow.h:64: auto CeilDiv(const Dividend, const Divisor) [Dividend = long, Divisor = int]: Assertion `dividend >= 0 && divisor > 0' failed.
    
  9. l0rinc force-pushed on Jan 29, 2026
  10. l0rinc commented at 11:44 am on January 29, 2026: contributor
    0 fuzz: util/overflow.h:64: auto CeilDiv(const Dividend, const Divisor) [Dividend = long, Divisor = int]: Assertion `dividend >= 0 && divisor > 0' failed.
    

    Yeah, a few places (e.g. GetVirtualTransactionSize) were replaced originally in the PR, but turns out fuzzers sometimes create negative amounts for these - not sure if that’s possible in reality so I’ve reverted that one. Sorry for all the pushes, the extra validations in the new CeilDiv trigger a lot of these (invalid?) edge cases - so we can investigate and possibly migrate them in follow-up PRs instead.

  11. DrahtBot removed the label CI failed on Jan 29, 2026
  12. DrahtBot added the label Needs rebase on Feb 7, 2026
  13. l0rinc force-pushed on Feb 8, 2026
  14. DrahtBot removed the label Needs rebase on Feb 8, 2026
  15. sedited commented at 2:06 pm on February 11, 2026: contributor

    Sorry for all the pushes, the extra validations in the new CeilDiv trigger a lot of these (invalid?) edge cases - so we can investigate and possibly migrate them in follow-up PRs instead.

    It is kind of hard to ascertain that the assertion won’t be reached with the current change either. I tried constraining the divisor argument to an unsigned integer, but that brought a whole range of changes to the passed in types. My impression is those are already signed types to guard against unwanted underflows in the first place. Do we really need to assert in the first place? If so, it might be better to switch to an Assume. Maybe the changes can be constrained to cases where we are dealing with unsigned integers?

  16. l0rinc commented at 3:02 pm on February 11, 2026: contributor

    it might be better to switch to an Assume

    We can’t have that here, tried that and CI failed for some reason - but assert is fine, I will switch them over to just unsigned and we can migrate the remaining ones separately, if needed.

  17. l0rinc renamed this:
    refactor + log: use new `CeilDiv` helper in UTXO `Flushing` warning
    refactor: add overflow-safe `CeilDiv` helper and use it in unsigned callsites
    on Feb 11, 2026
  18. DrahtBot added the label Refactoring on Feb 11, 2026
  19. refactor: add overflow-safe `CeilDiv` helper
    Introduce `CeilDiv()` for integral ceiling division without the typical `(dividend + divisor - 1) / divisor` overflow, asserting a non-zero divisor.
    
    Replace existing ceiling-division expressions with `CeilDiv()` to centralize the preconditions.
    
    Add unit tests covering return type deduction, max-value behavior, and divisor checks.
    02d047fd5b
  20. l0rinc force-pushed on Feb 11, 2026
  21. l0rinc commented at 5:21 pm on February 11, 2026: contributor
    Simplified the PR to only do simplest CeilDiv cases - adjusted PR title and description, thanks for the hint.
  22. sedited requested review from hodlinator on Mar 2, 2026
  23. in src/util/overflow.h:66 in 02d047fd5b
    61+template <std::unsigned_integral Dividend, std::unsigned_integral Divisor>
    62+[[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
    63+{
    64+    assert(divisor > 0);
    65+    return dividend / divisor + (dividend % divisor != 0);
    66+}
    


    hodlinator commented at 11:10 am on March 2, 2026:

    It really sticks out to me that the divisor is a compile time constant in all cases except flatfile and feefrac.

    Have you considered having an overload to serve the most common usecase?

    0template <uint64_t Divisor, std::unsigned_integral Dividend>
    1[[nodiscard]] constexpr Dividend CeilDiv(const Dividend dividend)
    2{
    3    static_assert(Divisor > 0);
    4    return dividend / Divisor + (dividend % Divisor != 0);
    5}
    

    Only drawback I see is that the order of operands gets reversed:

    0-    str.reserve(CeilDiv(input.size(), 5u) * 8);
    1+    str.reserve(CeilDiv<5>(input.size()) * 8);
    

    l0rinc commented at 11:40 am on March 2, 2026:

    Compile-time division by zero would be a cool feature, but I wouldn’t expect it to catch anything in reality - we’d never explicitly add 0 as a divisor. Or if you mean that the division may not be optimized for powers of two, or that we would do the division needlessly twice (because of the modulo), please see https://godbolt.org/z/neM9E1Mae which indicates that both gcc and clang emit a single division and proper branchless shift sequences for powers of two, and assert-failure paths are placed out-of-line (without needing [[unlikely]]).

    Only drawback I see is that the order of operands gets reversed

    Agree, but maybe I don’t understand what advantage it would have, I only see downsides.


    hodlinator commented at 12:38 pm on March 2, 2026:
    Guess I wasn’t trusting the compiler-optimizers enough and wanting to be more explicit with nailing down the divisor for it. Tried adding my CeilDiv<Divisor>() variant (https://godbolt.org/z/c888Gcbc8) and diffing the assembly outputs and it doesn’t improve anything for neither GCC nor Clang. As you say, shifts and bitwise and’s are already used when possible for instance.
  24. in src/util/overflow.h:1 in 02d047fd5b


    hodlinator commented at 1:41 pm on March 2, 2026:

    Knew from before that there are multiple places using these types of expressions involving WITNESS_SCALE_FACTOR. Here is a somewhat minimal diff that applies to those places. It’s sad that we allow expressing negative transaction sizes and weights in many places even after this diff… but I agree with deferring fixing that.

      0diff --git a/src/consensus/consensus.h b/src/consensus/consensus.h
      1index 71b5fe2468..bcfc1a0140 100644
      2--- a/src/consensus/consensus.h
      3+++ b/src/consensus/consensus.h
      4@@ -18,7 +18,7 @@ static const int64_t MAX_BLOCK_SIGOPS_COST = 80000;
      5 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
      6 static const int COINBASE_MATURITY = 100;
      7 
      8-static const int WITNESS_SCALE_FACTOR = 4;
      9+constexpr unsigned int WITNESS_SCALE_FACTOR{4};
     10 
     11 static const size_t MIN_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 60; // 60 is the lower bound for the size of a valid serialized CTransaction
     12 static const size_t MIN_SERIALIZABLE_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 10; // 10 is the lower bound for the size of a serialized CTransaction
     13diff --git a/src/consensus/validation.h b/src/consensus/validation.h
     14index 37a40e767e..5cf0b45c86 100644
     15--- a/src/consensus/validation.h
     16+++ b/src/consensus/validation.h
     17@@ -129,15 +129,15 @@ class BlockValidationState : public ValidationState<BlockValidationResult> {};
     18 // using only serialization with and without witness data. As witness_size
     19 // is equal to total_size - stripped_size, this formula is identical to:
     20 // weight = (stripped_size * 3) + total_size.
     21-static inline int32_t GetTransactionWeight(const CTransaction& tx)
     22+static inline uint32_t GetTransactionWeight(const CTransaction& tx)
     23 {
     24     return ::GetSerializeSize(TX_NO_WITNESS(tx)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(tx));
     25 }
     26-static inline int64_t GetBlockWeight(const CBlock& block)
     27+static inline uint64_t GetBlockWeight(const CBlock& block)
     28 {
     29     return ::GetSerializeSize(TX_NO_WITNESS(block)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(block));
     30 }
     31-static inline int64_t GetTransactionInputWeight(const CTxIn& txin)
     32+static inline uint64_t GetTransactionInputWeight(const CTxIn& txin)
     33 {
     34     // scriptWitness size is added here because witnesses and txins are split up in segwit serialization.
     35     return ::GetSerializeSize(TX_NO_WITNESS(txin)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(txin)) + ::GetSerializeSize(txin.scriptWitness.stack);
     36diff --git a/src/core_io.cpp b/src/core_io.cpp
     37index 7492e9ca50..fdc9e2cbe7 100644
     38--- a/src/core_io.cpp
     39+++ b/src/core_io.cpp
     40@@ -28,6 +28,7 @@
     41 #include <undo.h>
     42 #include <univalue.h>
     43 #include <util/check.h>
     44+#include <util/overflow.h>
     45 #include <util/result.h>
     46 #include <util/strencodings.h>
     47 #include <util/string.h>
     48@@ -435,7 +436,7 @@ void TxToUniv(const CTransaction& tx, const uint256& block_hash, UniValue& entry
     49     entry.pushKV("hash", tx.GetWitnessHash().GetHex());
     50     entry.pushKV("version", tx.version);
     51     entry.pushKV("size", tx.ComputeTotalSize());
     52-    entry.pushKV("vsize", (GetTransactionWeight(tx) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR);
     53+    entry.pushKV("vsize", CeilDiv(GetTransactionWeight(tx), WITNESS_SCALE_FACTOR));
     54     entry.pushKV("weight", GetTransactionWeight(tx));
     55     entry.pushKV("locktime", tx.nLockTime);
     56 
     57diff --git a/src/kernel/mempool_entry.h b/src/kernel/mempool_entry.h
     58index 58824f7a80..cc3e64fa02 100644
     59--- a/src/kernel/mempool_entry.h
     60+++ b/src/kernel/mempool_entry.h
     61@@ -91,7 +91,7 @@ public:
     62         : TxGraph::Ref(std::move(ref)),
     63           tx{tx},
     64           nFee{fee},
     65-          nTxWeight{GetTransactionWeight(*tx)},
     66+          nTxWeight{static_cast<int32_t>(GetTransactionWeight(*tx))},
     67           nUsageSize{RecursiveDynamicUsage(tx)},
     68           nTime{time},
     69           entry_sequence{entry_sequence},
     70diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
     71index 46ec238c3b..4d20fe7c1e 100644
     72--- a/src/policy/policy.cpp
     73+++ b/src/policy/policy.cpp
     74@@ -373,22 +373,22 @@ bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& p
     75     return false;
     76 }
     77 
     78-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop)
     79+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
     80 {
     81     return std::max(weight, sigop_cost * bytes_per_sigop);
     82 }
     83 
     84-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop)
     85+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
     86 {
     87-    return (GetSigOpsAdjustedWeight(nWeight, nSigOpCost, bytes_per_sigop) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR;
     88+    return CeilDiv(GetSigOpsAdjustedWeight(weight, sigop_cost, bytes_per_sigop), WITNESS_SCALE_FACTOR);
     89 }
     90 
     91-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop)
     92+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop)
     93 {
     94-    return GetVirtualTransactionSize(GetTransactionWeight(tx), nSigOpCost, bytes_per_sigop);
     95+    return GetVirtualTransactionSize(GetTransactionWeight(tx), sigop_cost, bytes_per_sigop);
     96 }
     97 
     98-int64_t GetVirtualTransactionInputSize(const CTxIn& txin, int64_t nSigOpCost, unsigned int bytes_per_sigop)
     99+uint64_t GetVirtualTransactionInputSize(const CTxIn& txin, uint64_t sigop_cost, unsigned int bytes_per_sigop)
    100 {
    101-    return GetVirtualTransactionSize(GetTransactionInputWeight(txin), nSigOpCost, bytes_per_sigop);
    102+    return GetVirtualTransactionSize(GetTransactionInputWeight(txin), sigop_cost, bytes_per_sigop);
    103 }
    104diff --git a/src/policy/policy.h b/src/policy/policy.h
    105index 35189d7133..5f7877ba75 100644
    106--- a/src/policy/policy.h
    107+++ b/src/policy/policy.h
    108@@ -12,6 +12,7 @@
    109 #include <script/interpreter.h>
    110 #include <script/solver.h>
    111 #include <util/feefrac.h>
    112+#include <util/overflow.h>
    113 
    114 #include <cstdint>
    115 #include <string>
    116@@ -175,9 +176,9 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
    117 bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& prevouts);
    118 
    119 /** Compute the virtual transaction size (weight reinterpreted as bytes). */
    120-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop);
    121-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
    122-int64_t GetVirtualTransactionInputSize(const CTxIn& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
    123+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
    124+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
    125+uint64_t GetVirtualTransactionInputSize(const CTxIn& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
    126 
    127 static inline int64_t GetVirtualTransactionSize(const CTransaction& tx)
    128 {
    129@@ -189,8 +190,8 @@ static inline int64_t GetVirtualTransactionInputSize(const CTxIn& tx)
    130     return GetVirtualTransactionInputSize(tx, 0, 0);
    131 }
    132 
    133-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop);
    134+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
    135 
    136-static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, (feerate.size + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR}; }
    137+static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, static_cast<int32_t>(CeilDiv(static_cast<uint32_t>(feerate.size), WITNESS_SCALE_FACTOR))}; }
    138 
    139 #endif // BITCOIN_POLICY_POLICY_H
    140diff --git a/src/test/util/transaction_utils.cpp b/src/test/util/transaction_utils.cpp
    141index 7b1e2eb3ed..f69207774f 100644
    142--- a/src/test/util/transaction_utils.cpp
    143+++ b/src/test/util/transaction_utils.cpp
    144@@ -6,6 +6,7 @@
    145 #include <consensus/validation.h>
    146 #include <script/signingprovider.h>
    147 #include <test/util/transaction_utils.h>
    148+#include <util/overflow.h>
    149 
    150 CMutableTransaction BuildCreditingTransaction(const CScript& scriptPubKey, int nValue)
    151 {
    152@@ -71,14 +72,14 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
    153     return dummyTransactions;
    154 }
    155 
    156-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight)
    157+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight)
    158 {
    159     tx.vout.emplace_back(0, CScript() << OP_RETURN);
    160     auto unpadded_weight{GetTransactionWeight(CTransaction(tx))};
    161     assert(target_weight >= unpadded_weight);
    162 
    163     // determine number of needed padding bytes by converting weight difference to vbytes
    164-    auto dummy_vbytes = (target_weight - unpadded_weight + (WITNESS_SCALE_FACTOR - 1)) / WITNESS_SCALE_FACTOR;
    165+    auto dummy_vbytes = CeilDiv(target_weight - unpadded_weight, WITNESS_SCALE_FACTOR);
    166     // compensate for the increase of the compact-size encoded script length
    167     // (note that the length encoding of the unpadded output script needs one byte)
    168     dummy_vbytes -= GetSizeOfCompactSize(dummy_vbytes) - 1;
    169diff --git a/src/test/util/transaction_utils.h b/src/test/util/transaction_utils.h
    170index 867554f805..1b3df73e3d 100644
    171--- a/src/test/util/transaction_utils.h
    172+++ b/src/test/util/transaction_utils.h
    173@@ -29,7 +29,7 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
    174 
    175 // bulk transaction to reach a certain target weight,
    176 // by appending a single output with padded output script
    177-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight);
    178+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight);
    179 
    180 /**
    181  * Produce a satisfying script (scriptSig or witness).
    182diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
    183index edde923452..656f3e676d 100644
    184--- a/src/wallet/spend.cpp
    185+++ b/src/wallet/spend.cpp
    186@@ -167,7 +167,7 @@ TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *walle
    187     }
    188 
    189     // It's ok to use 0 as the number of sigops since we never create any pathological transaction.
    190-    return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight};
    191+    return TxSize{static_cast<int64_t>(GetVirtualTransactionSize(weight, 0, 0)), weight};
    192 }
    193 
    194 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control)
    

    Also found: https://github.com/bitcoin/bitcoin/blob/9cad97f6cdf1bd660732cd10e844a6a7e0771ea0/src/wallet/coinselection.cpp#L457 Which uses signed integers and I understand wanting to punt on it for now… although maybe providing a signed CeilDiv() overload could be an alternative?


    l0rinc commented at 2:58 pm on March 2, 2026:
    We should do all/most of these, I already had a few in this PR and reverted since it was getting too complicated to review - the risky ones should be done in separate commits/PRs. Thanks for checking them, my understanding is that you agree these should be done in a follow-up, to be safe, right?

    hodlinator commented at 9:41 pm on March 2, 2026:

    I already had a few in this PR and reverted since it was getting too complicated to review - the risky ones should be done in separate commits/PRs.

    Ah, I see. Went back and range-diffed 5bf64fbe6c6ced406027deaf2de964f228e7d806 to HEAD, I see you were on a similar track.

    my understanding is that you agree these should be done in a follow-up, to be safe, right?

    If the deadline to get this PR merged is tight (I saw #29678 depends on it), I agree it seems prudent to defer what is not currently included.

    In other cases, I think it would be preferable to attempt something more complete in the scope of this PR. At least have a CeilDiv() variant for signed integers which just de-inlines the repetitive code without any additional guarantees (unlike the unsigned one protecting from overflow). But it’s not a blocker.


    l0rinc commented at 9:44 pm on March 2, 2026:
    Thanks for checking. Strictly speaking it’s not that urgent, but I would like to separate the risk-free cheap refactor from doing it in risky places - my understand was that @sedited would prefer it be split. If not, I don’t mind doing it in separate commits or separate PRs.
  25. hodlinator approved
  26. hodlinator commented at 2:22 pm on March 2, 2026: contributor

    ACK 02d047fd5b93d96f159db2b8e95fc39450505159

    Introduces a clearer named primitive CeilDiv()1 in place of repeated verbose inlined expressions and fixes edge case with overflow/wrapping before division.


    1. Similar to ceildiv() in /test/functional/test_framework/util.py ↩︎


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-03-03 06:13 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me