Page MenuHomePhabricator

Add AddInt63OverflowEmulated and SubInt63OverflowEmulated
ClosedPublic

Authored by tobias_ruck on Aug 5 2021, 02:08.

Details

Reviewers
deadalnix
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Restricted Project
Commits
rABC31dd07e9b675: Add AddInt63OverflowEmulated and SubInt63OverflowEmulated
Summary

Computes 63+sign-bit addition and subtraction with overflow checks, without using built-ins. It's a fallback for when __builtin_saddll_overflow and __builtin_ssubll_overflow are not available.

Allows 63+sign-bit integers in Script down the line.

Test Plan

ninja check

Event Timeline

Owners added a reviewer: Restricted Owners Package.Aug 5 2021, 02:08
deadalnix requested changes to this revision.Aug 5 2021, 11:55
deadalnix added inline comments.
src/script/intmath.cpp
13

The name doesn't say what it does. Documenting it in the comment is a poor substitude, especially since the comment is in the implementation, so one has to go to the implementation to know what that does. The point of adding abstraction is exactly so that people don't need to do that.

18

This is likely UB too.

26
if (condition) {
    return true;
} else {
    return false;
}

Maybe could simply be

return condition;

No?

35

I'm pretty sure this is UB. have you run this code through ubsan?

src/script/intmath.h
11

You probably want this to be header only so that implementation can be inlined.

src/test/intmath_util.h
1

This is not the copyright notice we are using.

Also, I'm not sure what the purpose of this header is.

This revision now requires changes to proceed.Aug 5 2021, 11:55

Inlined and removed intmath.cpp and intmath_util.h. Renamed functions in intmath.h. Fixed copyright notice. Simplified conditional code.

Verified lack of UB with the following:

set(CMAKE_CXX_FLAGS "-fsanitize=undefined") in CMakeLists.txt

ninja test_bitcoin && ./src/test/test_bitcoin -t intmath_tests results in no runtime errors.

Moving result = a + b; and result = a - b; in intmath.h in front of the overflow checks and testing again results in:

Running 1 test case...
../src/./script/intmath.h:34:16: runtime error: signed integer overflow: -126 - 9223372036854775807 cannot be represented in type 'long long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/./script/intmath.h:34:16 in 
../src/./script/intmath.h:16:16: runtime error: signed integer overflow: 9223372036854775807 + 15325750 cannot be represented in type 'long long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/./script/intmath.h:16:16 in
tobias_ruck retitled this revision from Add AddInt63Emulated and SubInt63Emulated to Add AddInt63OverflowEmulated and SubInt63OverflowEmulated.Aug 5 2021, 22:11
deadalnix requested changes to this revision.Aug 6 2021, 01:34
deadalnix added inline comments.
src/test/intmath_tests.cpp
122 ↗(On Diff #29340)

lcg give you chunk of 32 bits, why do you discard 3/4 of that ?

126 ↗(On Diff #29340)

Discard the value instead. This is the only way to handle random numbers, or in this case pseudorandom, without skewing the distribution.

130 ↗(On Diff #29340)

That does not seem useful.

This revision now requires changes to proceed.Aug 6 2021, 01:34

Improve GenInt63, generates random positive uniform 63-bit number first, then maps to random uniform bit-length and then negates with 50% chance.

deadalnix requested changes to this revision.Aug 7 2021, 00:06
deadalnix added inline comments.
src/test/intmath_tests.cpp
125 ↗(On Diff #29341)

I still don't see what any of this accomplishes over:

int64_t val = (int64_t(lcg.next()) << 32) | lcg.next();
// Make bit-length uniformly distributed for better test coverage.
return val >> (lcg.next() % 64);
This revision now requires changes to proceed.Aug 7 2021, 00:06

Simplified GenInt63 using apparently non-UB

This revision is now accepted and ready to land.Aug 14 2021, 23:54

Fixed GenInt63 out of bounds case

Use assignment operator for bitshift in GenInt63

Failed tests logs:

====== Bitcoin ABC functional tests: abc_p2p_proof_inventory.py ======

------- Stdout: -------
2021-08-19T08:42:07.494000Z TestFramework (INFO): Initializing test directory /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210819_084204/abc_p2p_proof_inventory_1
2021-08-19T08:42:10.219000Z TestFramework (INFO): Test sending a proof to our peers
2021-08-19T08:42:15.519000Z TestFramework (INFO): Test that we don't send the same inv several times
2021-08-19T08:42:19.717000Z TestFramework (INFO): Test a peer is created on proof reception
2021-08-19T08:42:19.970000Z TestFramework (INFO): Test receiving a proof with missing utxo is orphaned
2021-08-19T08:42:36.595000Z TestFramework (INFO): Nodes should eventually get the proof from their peer
2021-08-19T08:43:37.040000Z TestFramework (ERROR): Assertion failed
Traceback (most recent call last):
  File "/work/test/functional/test_framework/test_framework.py", line 127, in main
    self.run_test()
  File "/work/test/functional/abc_p2p_proof_inventory.py", line 309, in run_test
    self.test_proof_relay()
  File "/work/test/functional/abc_p2p_proof_inventory.py", line 194, in test_proof_relay
    self.sync_proofs()
  File "/work/test/functional/test_framework/test_framework.py", line 598, in sync_proofs
    "".join("\n  {!r}".format(m) for m in nodes_proofs),
AssertionError: Proofs sync timed out after 60s:
  {6602570144918074808348643829737375459277018741439688339068130810910165091525, 4855606214566755611854941872008953586797068519770192445106571173944961724226}
  {6602570144918074808348643829737375459277018741439688339068130810910165091525, 4855606214566755611854941872008953586797068519770192445106571173944961724226}
  {13973555143603491866073812417028997900378547346586411321916985318209461542133, 48966920474268920273518024000965517207941241018457762983682481056232661307578, 54765853492931327955993243584528671492237549707396256159560862334732186751282, 4855606214566755611854941872008953586797068519770192445106571173944961724226}
  {13973555143603491866073812417028997900378547346586411321916985318209461542133, 48966920474268920273518024000965517207941241018457762983682481056232661307578, 54765853492931327955993243584528671492237549707396256159560862334732186751282, 4855606214566755611854941872008953586797068519770192445106571173944961724226}
  {13973555143603491866073812417028997900378547346586411321916985318209461542133, 4855606214566755611854941872008953586797068519770192445106571173944961724226, 54765853492931327955993243584528671492237549707396256159560862334732186751282, 48966920474268920273518024000965517207941241018457762983682481056232661307578}
2021-08-19T08:43:37.090000Z TestFramework (INFO): Stopping nodes
2021-08-19T08:43:37.295000Z TestFramework (WARNING): Not cleaning up dir /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210819_084204/abc_p2p_proof_inventory_1
2021-08-19T08:43:37.295000Z TestFramework (ERROR): Test failed. Test logging available at /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210819_084204/abc_p2p_proof_inventory_1/test_framework.log
2021-08-19T08:43:37.295000Z TestFramework (ERROR): 
2021-08-19T08:43:37.295000Z TestFramework (ERROR): Hint: Call /work/test/functional/combine_logs.py '/work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210819_084204/abc_p2p_proof_inventory_1' to consolidate all logs
2021-08-19T08:43:37.295000Z TestFramework (ERROR): 
2021-08-19T08:43:37.295000Z TestFramework (ERROR): If this failure happened unexpectedly or intermittently, please file a bug and provide a link or upload of the combined log.
2021-08-19T08:43:37.295000Z TestFramework (ERROR): https://github.com/Bitcoin-ABC/bitcoin-abc/issues
2021-08-19T08:43:37.295000Z TestFramework (ERROR):

Each failure log is accessible here:
Bitcoin ABC functional tests: abc_p2p_proof_inventory.py

deadalnix requested changes to this revision.Aug 24 2021, 23:40
deadalnix added inline comments.
src/test/intmath_tests.cpp
123 ↗(On Diff #29460)

You should make this a loop.

This revision now requires changes to proceed.Aug 24 2021, 23:40

Use loop in GenInt63 instead of recursion

This revision is now accepted and ready to land.Aug 25 2021, 02:17