refactor: add overflow-safe CeilDiv helper and use it in unsigned callsites#34436
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please copy-paste ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
l0rinc
force-pushed
the
l0rinc/ceildiv-utxo-flush-gib
branch
from
999ccbc to
94d2feb
Compare
l0rinc
force-pushed
the
l0rinc/ceildiv-utxo-flush-gib
branch
2 times, most recently
from
5bf64fb to
a77d047
Compare
|
https://github.com/bitcoin/bitcoin/actions/runs/21474548168/job/61856382435?pr=34436#step:11:2456: fuzz: util/overflow.h:64: auto CeilDiv(const Dividend, const Divisor) [Dividend = long, Divisor = int]: Assertion `dividend >= 0 && divisor > 0' failed. |
l0rinc
force-pushed
the
l0rinc/ceildiv-utxo-flush-gib
branch
from
a77d047 to
977610e
Compare
Yeah, a few places (e.g. |
l0rinc
force-pushed
the
l0rinc/ceildiv-utxo-flush-gib
branch
from
977610e to
d9b0708
Compare
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 |
We can't have that here, tried that and CI failed for some reason - but |
l0rinc
changed the title
CeilDiv helper in UTXO Flushing warningCeilDiv helper and use it in unsigned callsites
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.
l0rinc
force-pushed
the
l0rinc/ceildiv-utxo-flush-gib
branch
from
d9b0708 to
02d047f
Compare
|
Simplified the PR to only do simplest |
There was a problem hiding this comment.
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.
Diff, maybe makes sense as a second commit?
diff --git a/src/consensus/consensus.h b/src/consensus/consensus.h
index 71b5fe2468..bcfc1a0140 100644
--- a/src/consensus/consensus.h
+++ b/src/consensus/consensus.h
@@ -18,7 +18,7 @@ static const int64_t MAX_BLOCK_SIGOPS_COST = 80000;
/** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
static const int COINBASE_MATURITY = 100;
-static const int WITNESS_SCALE_FACTOR = 4;
+constexpr unsigned int WITNESS_SCALE_FACTOR{4};
static const size_t MIN_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 60; // 60 is the lower bound for the size of a valid serialized CTransaction
static const size_t MIN_SERIALIZABLE_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 10; // 10 is the lower bound for the size of a serialized CTransaction
diff --git a/src/consensus/validation.h b/src/consensus/validation.h
index 37a40e767e..5cf0b45c86 100644
--- a/src/consensus/validation.h
+++ b/src/consensus/validation.h
@@ -129,15 +129,15 @@ class BlockValidationState : public ValidationState<BlockValidationResult> {};
// using only serialization with and without witness data. As witness_size
// is equal to total_size - stripped_size, this formula is identical to:
// weight = (stripped_size * 3) + total_size.
-static inline int32_t GetTransactionWeight(const CTransaction& tx)
+static inline uint32_t GetTransactionWeight(const CTransaction& tx)
{
return ::GetSerializeSize(TX_NO_WITNESS(tx)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(tx));
}
-static inline int64_t GetBlockWeight(const CBlock& block)
+static inline uint64_t GetBlockWeight(const CBlock& block)
{
return ::GetSerializeSize(TX_NO_WITNESS(block)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(block));
}
-static inline int64_t GetTransactionInputWeight(const CTxIn& txin)
+static inline uint64_t GetTransactionInputWeight(const CTxIn& txin)
{
// scriptWitness size is added here because witnesses and txins are split up in segwit serialization.
return ::GetSerializeSize(TX_NO_WITNESS(txin)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(txin)) + ::GetSerializeSize(txin.scriptWitness.stack);
diff --git a/src/core_io.cpp b/src/core_io.cpp
index 7492e9ca50..fdc9e2cbe7 100644
--- a/src/core_io.cpp
+++ b/src/core_io.cpp
@@ -28,6 +28,7 @@
#include <undo.h>
#include <univalue.h>
#include <util/check.h>
+#include <util/overflow.h>
#include <util/result.h>
#include <util/strencodings.h>
#include <util/string.h>
@@ -435,7 +436,7 @@ void TxToUniv(const CTransaction& tx, const uint256& block_hash, UniValue& entry
entry.pushKV("hash", tx.GetWitnessHash().GetHex());
entry.pushKV("version", tx.version);
entry.pushKV("size", tx.ComputeTotalSize());
- entry.pushKV("vsize", (GetTransactionWeight(tx) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR);
+ entry.pushKV("vsize", CeilDiv(GetTransactionWeight(tx), WITNESS_SCALE_FACTOR));
entry.pushKV("weight", GetTransactionWeight(tx));
entry.pushKV("locktime", tx.nLockTime);
diff --git a/src/kernel/mempool_entry.h b/src/kernel/mempool_entry.h
index 58824f7a80..cc3e64fa02 100644
--- a/src/kernel/mempool_entry.h
+++ b/src/kernel/mempool_entry.h
@@ -91,7 +91,7 @@ public:
: TxGraph::Ref(std::move(ref)),
tx{tx},
nFee{fee},
- nTxWeight{GetTransactionWeight(*tx)},
+ nTxWeight{static_cast<int32_t>(GetTransactionWeight(*tx))},
nUsageSize{RecursiveDynamicUsage(tx)},
nTime{time},
entry_sequence{entry_sequence},
diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
index 46ec238c3b..4d20fe7c1e 100644
--- a/src/policy/policy.cpp
+++ b/src/policy/policy.cpp
@@ -373,22 +373,22 @@ bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& p
return false;
}
-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop)
+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
{
return std::max(weight, sigop_cost * bytes_per_sigop);
}
-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
{
- return (GetSigOpsAdjustedWeight(nWeight, nSigOpCost, bytes_per_sigop) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR;
+ return CeilDiv(GetSigOpsAdjustedWeight(weight, sigop_cost, bytes_per_sigop), WITNESS_SCALE_FACTOR);
}
-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop)
{
- return GetVirtualTransactionSize(GetTransactionWeight(tx), nSigOpCost, bytes_per_sigop);
+ return GetVirtualTransactionSize(GetTransactionWeight(tx), sigop_cost, bytes_per_sigop);
}
-int64_t GetVirtualTransactionInputSize(const CTxIn& txin, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionInputSize(const CTxIn& txin, uint64_t sigop_cost, unsigned int bytes_per_sigop)
{
- return GetVirtualTransactionSize(GetTransactionInputWeight(txin), nSigOpCost, bytes_per_sigop);
+ return GetVirtualTransactionSize(GetTransactionInputWeight(txin), sigop_cost, bytes_per_sigop);
}
diff --git a/src/policy/policy.h b/src/policy/policy.h
index 35189d7133..5f7877ba75 100644
--- a/src/policy/policy.h
+++ b/src/policy/policy.h
@@ -12,6 +12,7 @@
#include <script/interpreter.h>
#include <script/solver.h>
#include <util/feefrac.h>
+#include <util/overflow.h>
#include <cstdint>
#include <string>
@@ -175,9 +176,9 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& prevouts);
/** Compute the virtual transaction size (weight reinterpreted as bytes). */
-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop);
-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
-int64_t GetVirtualTransactionInputSize(const CTxIn& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionInputSize(const CTxIn& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
static inline int64_t GetVirtualTransactionSize(const CTransaction& tx)
{
@@ -189,8 +190,8 @@ static inline int64_t GetVirtualTransactionInputSize(const CTxIn& tx)
return GetVirtualTransactionInputSize(tx, 0, 0);
}
-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
-static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, (feerate.size + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR}; }
+static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, static_cast<int32_t>(CeilDiv(static_cast<uint32_t>(feerate.size), WITNESS_SCALE_FACTOR))}; }
#endif // BITCOIN_POLICY_POLICY_H
diff --git a/src/test/util/transaction_utils.cpp b/src/test/util/transaction_utils.cpp
index 7b1e2eb3ed..f69207774f 100644
--- a/src/test/util/transaction_utils.cpp
+++ b/src/test/util/transaction_utils.cpp
@@ -6,6 +6,7 @@
#include <consensus/validation.h>
#include <script/signingprovider.h>
#include <test/util/transaction_utils.h>
+#include <util/overflow.h>
CMutableTransaction BuildCreditingTransaction(const CScript& scriptPubKey, int nValue)
{
@@ -71,14 +72,14 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
return dummyTransactions;
}
-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight)
+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight)
{
tx.vout.emplace_back(0, CScript() << OP_RETURN);
auto unpadded_weight{GetTransactionWeight(CTransaction(tx))};
assert(target_weight >= unpadded_weight);
// determine number of needed padding bytes by converting weight difference to vbytes
- auto dummy_vbytes = (target_weight - unpadded_weight + (WITNESS_SCALE_FACTOR - 1)) / WITNESS_SCALE_FACTOR;
+ auto dummy_vbytes = CeilDiv(target_weight - unpadded_weight, WITNESS_SCALE_FACTOR);
// compensate for the increase of the compact-size encoded script length
// (note that the length encoding of the unpadded output script needs one byte)
dummy_vbytes -= GetSizeOfCompactSize(dummy_vbytes) - 1;
diff --git a/src/test/util/transaction_utils.h b/src/test/util/transaction_utils.h
index 867554f805..1b3df73e3d 100644
--- a/src/test/util/transaction_utils.h
+++ b/src/test/util/transaction_utils.h
@@ -29,7 +29,7 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
// bulk transaction to reach a certain target weight,
// by appending a single output with padded output script
-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight);
+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight);
/**
* Produce a satisfying script (scriptSig or witness).
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index edde923452..656f3e676d 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -167,7 +167,7 @@ TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *walle
}
// It's ok to use 0 as the number of sigops since we never create any pathological transaction.
- return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight};
+ return TxSize{static_cast<int64_t>(GetVirtualTransactionSize(weight, 0, 0)), weight};
}
TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control)Also found:
bitcoin/src/wallet/coinselection.cpp
Line 457 in 9cad97f
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?
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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 5bf64fb 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.
There was a problem hiding this comment.
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.
|
I think we can do better and use -template <std::unsigned_integral Dividend, std::unsigned_integral Divisor>
-[[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
+template <int Divisor, std::unsigned_integral Dividend>
+[[nodiscard]] constexpr auto CeilDiv(const Dividend dividend)
{
- assert(divisor > 0);
- return dividend / divisor + (dividend % divisor != 0);
+ static_assert(Divisor > 0, "CeilDiv: divisor must be a positive, unsigned integer.");
+ return dividend / Divisor + (dividend % Divisor != 0);
}Which results in, for example: CeilDiv<ELEM_ALIGN_BYTES>(bytes)And for the case of unknown divisors the function could perhaps be overloaded. |
|
Previous comment was addressed. I have a direct need for this function in my current work and I think the change is sufficiently motivated. ACK 02d047f |
6 participants
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
CeilDiv()tosrc/util/overflow.hfor unsigned integral inputs.assert(divisor > 0).CeilDiv(...).src/test/util_tests.cppfor 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.