Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Fix UB in CustomRandom #260

Open
polyntsov opened this issue Aug 28, 2023 · 0 comments
Open

Fix UB in CustomRandom #260

polyntsov opened this issue Aug 28, 2023 · 0 comments
Assignees
@Mstrutov
Labels
bug Something isn't working

Comments

@polyntsov
Copy link
Collaborator

CustomRandom implements a random number generator by porting Java.Random. As Java.Random, it uses signed integer to represent hash value, however, overflow of signed integer is UB in C++. And right now in Pyro tests overflow happens, which should be fixed. It can be fixed either by using unsigned integers or by explicitly checking for possible overflow of arithmetic operations, which will probably slow the generator. I'm not sure which approach is better and how to fix this without losing the equivalency to Java implementation.
Some logs showing the problems:

$ UBSAN_OPTIONS=print_stacktrace=1 ./Desbordante_test --gtest_filter='AlgorithmTest/AlgorithmTest/1.LightDatasetsConsistentHash'
Note: Google Test filter = AlgorithmTest/AlgorithmTest/1.LightDatasetsConsistentHash
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from AlgorithmTest/AlgorithmTest/1, where TypeParam = algos::Pyro
[ RUN      ] AlgorithmTest/AlgorithmTest/1.LightDatasetsConsistentHash
/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 25214899796 * 25214903917 cannot be represented in type 'long long int'
    #0 0x55b4fdfc1b0a in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fdfd2d9d in CustomRandom::NextLL() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:37
    #2 0x55b4fdfd2d9d in CustomRandom::NextULL() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:42
    #3 0x55b4fdfd2d9d in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:114
    #4 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #5 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #6 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #7 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #8 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #9 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #10 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #11 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #12 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #13 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #14 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #15 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #16 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #17 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #18 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #19 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #20 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #21 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #22 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #23 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #24 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 144455641405230 * 25214903917 cannot be represented in type 'long long int'
    #0 0x55b4fdfc1d81 in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fdfc1d81 in CustomRandom::NextInt(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:56
    #2 0x55b4fdfd183f in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:121
    #3 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #4 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #5 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #6 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #7 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #8 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #9 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #10 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #11 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #12 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #13 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #14 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #15 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #16 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #17 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #18 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #19 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #20 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #21 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #22 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #23 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:37:48: runtime error: left shift of negative value -716867186
    #0 0x55b4fdfd1475 in CustomRandom::NextLL() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:37
    #1 0x55b4fdfd1475 in CustomRandom::NextULL() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:42
    #2 0x55b4fdfd1475 in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:114
    #3 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #4 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #5 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #6 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #7 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #8 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #9 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #10 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #11 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #12 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #13 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #14 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #15 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #16 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #17 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #18 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #19 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #20 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #21 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #22 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #23 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 168297002286140 * 25214903917 cannot be represented in type 'long long int'
    #0 0x55b4fdfd1ab8 in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fdfd1ab8 in CustomRandom::NextInt(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:56
    #2 0x55b4fdfd1ab8 in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:124
    #3 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #4 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #5 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #6 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #7 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #8 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #9 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #10 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #11 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #12 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #13 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #14 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #15 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #16 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #17 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #18 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #19 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #20 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #21 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #22 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #23 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:61:59: runtime error: signed integer overflow: 2147475231 + 9998 cannot be represented in type 'int'
    #0 0x55b4fdfc200a in CustomRandom::NextInt(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:61
    #1 0x55b4fdfd1932 in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:122
    #2 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #3 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #4 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #5 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #6 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #7 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #8 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #9 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #10 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #11 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #12 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #13 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #14 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #15 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #16 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #17 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #18 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #19 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #20 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #21 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #22 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 25214903917 * 281474526641830 cannot be represented in type 'long long int'
    #0 0x55b4fdfc1ea5 in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fdfc1ea5 in CustomRandom::NextInt(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:61
    #2 0x55b4fdfd1932 in std::unique_ptr<model::ListAgreeSetSample, std::default_delete<model::ListAgreeSetSample> > model::AgreeSetSample::CreateFocusedFor<model::ListAgreeSetSample>(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/agree_set_sample_impl.h:122
    #3 0x55b4fdfc0f7d in model::ListAgreeSetSample::CreateFocusedFor(ColumnLayoutRelationData const*, Vertical const&, model::PositionListIndex const*, unsigned int, CustomRandom&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/list_agree_set_sample.cpp:11
    #4 0x55b4fe521ce1 in ProfilingContext::CreateColumnFocusedSample(Vertical const&, model::PositionListIndex const*, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:159
    #5 0x55b4fe5269c4 in ProfilingContext::ProfilingContext(pyro::Parameters, ColumnLayoutRelationData*, std::function<void (PartialKey const&)> const&, std::function<void (PartialFD const&)> const&, CachingMethod const&, CacheEvictionMethod const&, double) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.cpp:37
    #6 0x55b4fdfdbb61 in std::__detail::_MakeUniq<ProfilingContext>::__single_object std::make_unique<ProfilingContext, pyro::Parameters&, ColumnLayoutRelationData*, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&>(pyro::Parameters&, ColumnLayoutRelationData*&&, std::function<void (PartialKey const&)>&, std::function<void (PartialFD const&)>&, CachingMethod&, CacheEvictionMethod&, double&) /usr/include/c++/13.2.1/bits/unique_ptr.h:1070
    #7 0x55b4fdfdbb61 in algos::Pyro::ExecuteInternal() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:56
    #8 0x55b4fdc2491d in algos::Algorithm::Execute() /home/arno/prog/proj/Desbordante/src/core/algorithms/algorithm.cpp:76
    #9 0x55b4fd8aaf29 in gtest_suite_AlgorithmTest_::LightDatasetsConsistentHash<algos::Pyro>::TestBody() /home/arno/prog/proj/Desbordante/src/tests/test_algorithm.cpp:112
    #10 0x55b4fe6c4c75 in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #11 0x55b4fe6c4c75 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #12 0x55b4fe64d887 in testing::Test::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2696
    #13 0x55b4fe64e639 in testing::TestInfo::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2845
    #14 0x55b4fe64f430 in testing::TestSuite::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:3004
    #15 0x55b4fe67ceb8 in testing::internal::UnitTestImpl::RunAllTests() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5890
    #16 0x55b4fe6c61f9 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2621
    #17 0x55b4fe6c61f9 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:2657
    #18 0x55b4fe6501a2 in testing::UnitTest::Run() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/src/gtest.cc:5455
    #19 0x55b4fd7579e2 in RUN_ALL_TESTS() /home/arno/prog/proj/Desbordante/lib/googletest/googletest/include/gtest/gtest.h:2314
    #20 0x55b4fd7579e2 in main /home/arno/prog/proj/Desbordante/src/tests/main.cpp:20
    #21 0x7fc946a27ccf  (/usr/lib/libc.so.6+0x27ccf) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #22 0x7fc946a27d89 in __libc_start_main (/usr/lib/libc.so.6+0x27d89) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #23 0x55b4fd757874 in _start (/home/arno/prog/proj/Desbordante/build/target/Desbordante_test+0x2909874) (BuildId: a25d3fd5a2440409502d7cce1ab5194c86e21a44)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 31870604798286 * 25214903917 cannot be represented in type 'long long int'
    #0 0x55b4fe57f279 in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fe57f279 in CustomRandom::NextDouble() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:69
    #2 0x55b4fe57f279 in ProfilingContext::NextDouble() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.h:78
    #3 0x55b4fe57f279 in model::PLICache::CachingProcess(Vertical const&, std::unique_ptr<model::PositionListIndex, std::default_delete<model::PositionListIndex> >, ProfilingContext*) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/pli_cache.cpp:184
    #4 0x55b4fe58d9e7 in model::PLICache::GetOrCreateFor(Vertical const&, ProfilingContext*) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/pli_cache.cpp:160
    #5 0x55b4fe50fc8f in FdG1Strategy::CalculateError(Vertical const&) const /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/fd_g1_strategy.cpp:74
    #6 0x55b4fe55d2ed in SearchSpace::Ascend(DependencyCandidate const&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/search_space.cpp:196
    #7 0x55b4fe54ae4f in SearchSpace::Discover() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/search_space.cpp:22
    #8 0x55b4fdfd7b40 in operator() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:120
    #9 0x55b4fdfd7b40 in __invoke_impl<void, algos::Pyro::ExecuteInternal()::<lambda(std::__cxx11::list<std::unique_ptr<SearchSpace> >&, ProfilingContext*, int)>, std::reference_wrapper<std::__cxx11::list<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> >, std::allocator<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> > > > >, ProfilingContext*, int> /usr/include/c++/13.2.1/bits/invoke.h:61
    #10 0x55b4fdfd7b40 in __invoke<algos::Pyro::ExecuteInternal()::<lambda(std::__cxx11::list<std::unique_ptr<SearchSpace> >&, ProfilingContext*, int)>, std::reference_wrapper<std::__cxx11::list<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> >, std::allocator<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> > > > >, ProfilingContext*, int> /usr/include/c++/13.2.1/bits/invoke.h:96
    #11 0x55b4fdfd7b40 in _M_invoke<0, 1, 2, 3> /usr/include/c++/13.2.1/bits/std_thread.h:292
    #12 0x55b4fdfd7b40 in operator() /usr/include/c++/13.2.1/bits/std_thread.h:299
    #13 0x55b4fdfd7b40 in _M_run /usr/include/c++/13.2.1/bits/std_thread.h:244
    #14 0x7fc9476e1942 in execute_native_thread_routine /usr/src/debug/gcc/gcc/libstdc++-v3/src/c++11/thread.cc:104
    #15 0x7fc946a8c9ea  (/usr/lib/libc.so.6+0x8c9ea) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #16 0x7fc946b10dfb  (/usr/lib/libc.so.6+0x110dfb) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)

/home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32:24: runtime error: signed integer overflow: 278150806137409 * 25214903917 cannot be represented in type 'long long int'
    #0 0x55b4fe57f374 in CustomRandom::Next(int) /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:32
    #1 0x55b4fe57f374 in CustomRandom::NextDouble() /home/arno/prog/proj/Desbordante/src/core/util/custom_random.h:69
    #2 0x55b4fe57f374 in ProfilingContext::NextDouble() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/profiling_context.h:78
    #3 0x55b4fe57f374 in model::PLICache::CachingProcess(Vertical const&, std::unique_ptr<model::PositionListIndex, std::default_delete<model::PositionListIndex> >, ProfilingContext*) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/pli_cache.cpp:184
    #4 0x55b4fe58d9e7 in model::PLICache::GetOrCreateFor(Vertical const&, ProfilingContext*) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/model/pli_cache.cpp:160
    #5 0x55b4fe50fc8f in FdG1Strategy::CalculateError(Vertical const&) const /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/fd_g1_strategy.cpp:74
    #6 0x55b4fe55d2ed in SearchSpace::Ascend(DependencyCandidate const&) /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/search_space.cpp:196
    #7 0x55b4fe54ae4f in SearchSpace::Discover() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/core/search_space.cpp:22
    #8 0x55b4fdfd7b40 in operator() /home/arno/prog/proj/Desbordante/src/core/algorithms/fd/pyro/pyro.cpp:120
    #9 0x55b4fdfd7b40 in __invoke_impl<void, algos::Pyro::ExecuteInternal()::<lambda(std::__cxx11::list<std::unique_ptr<SearchSpace> >&, ProfilingContext*, int)>, std::reference_wrapper<std::__cxx11::list<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> >, std::allocator<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> > > > >, ProfilingContext*, int> /usr/include/c++/13.2.1/bits/invoke.h:61
    #10 0x55b4fdfd7b40 in __invoke<algos::Pyro::ExecuteInternal()::<lambda(std::__cxx11::list<std::unique_ptr<SearchSpace> >&, ProfilingContext*, int)>, std::reference_wrapper<std::__cxx11::list<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> >, std::allocator<std::unique_ptr<SearchSpace, std::default_delete<SearchSpace> > > > >, ProfilingContext*, int> /usr/include/c++/13.2.1/bits/invoke.h:96
    #11 0x55b4fdfd7b40 in _M_invoke<0, 1, 2, 3> /usr/include/c++/13.2.1/bits/std_thread.h:292
    #12 0x55b4fdfd7b40 in operator() /usr/include/c++/13.2.1/bits/std_thread.h:299
    #13 0x55b4fdfd7b40 in _M_run /usr/include/c++/13.2.1/bits/std_thread.h:244
    #14 0x7fc9476e1942 in execute_native_thread_routine /usr/src/debug/gcc/gcc/libstdc++-v3/src/c++11/thread.cc:104
    #15 0x7fc946a8c9ea  (/usr/lib/libc.so.6+0x8c9ea) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)
    #16 0x7fc946b10dfb  (/usr/lib/libc.so.6+0x110dfb) (BuildId: 316d0d3666387f0e8fb98773f51aa1801027c5ab)

For debugging code can be ran under UB sanitizer by rebasing on the branch in #180.
@polyntsov polyntsov added the bug Something isn't working label Aug 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Mstrutov Mstrutov

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@Mstrutov @polyntsov