Page MenuHomePhabricator

Use best-fit strategy in Arena, now O(log(n)) instead O(n)
ClosedPublic

Authored by nakihito on Aug 16 2019, 23:53.

Details

Summary

PR12048:
5fbf7c4 fix nits: variable naming, typos (Martin Ankerl)
1e0ee90 Use best-fit strategy in Arena, now O(log(n)) instead O(n) (Martin Ankerl)

Pull request description:

This replaces the first-fit algorithm used in the Arena with a best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review", Wilson et. al. 1995, http://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, both startegies work well in practice.

The advantage of using best-fit is that we can switch the O(n) allocation to O(log(n)). Additionally, some previously O(log(n)) operations are now O(1) operations by using hash maps. The end effect is that the benchmark runs about 2.5 times faster on my machine:

    # Benchmark, evals, iterations, total, min, max, median
    old: BenchLockedPool, 5, 530, 5.25749, 0.00196938, 0.00199755, 0.00198172
    new: BenchLockedPool, 5, 1300, 5.11313, 0.000781493, 0.000793314, 0.00078606

I've run all unit tests and benchmarks, and increased the number of iterations so that BenchLockedPool takes about 5 seconds again.

Tree-SHA512: 6551e384671f93f10c60df530a29a1954bd265cc305411f665a8756525e5afe2873a8032c797d00b6e8c07e16d9827465d0b662875433147381474a44119ccce

Also included PR16161 which fixes a bug introduced by PR12048:

Changes in #12048 cause a compilation error in Arena::walk() when
ARENA_DEBUG is defined. Specifically, Arena's chunks_free map was
changed to have a different value type.

Additionally, missing includes cause other compilation errors when
ARENA_DEBUG is defined.

Second commit fixes segfault in allocator_tests/arena_tests
The test uses reinterpret_cast<void*> on unallocated memory. Using this
memory in printchunk as char* causes a segfault, so have printchunk take
void* instead.

Reproduced with:

make CPPFLAGS=-DARENA_DEBUG

Backport of Core PR12048 and PR16161
https://github.com/bitcoin/bitcoin/pull/12048/
https://github.com/bitcoin/bitcoin/pull/16161/

Reviewer note: the last commit in PR16161 is TRAVIS related and was therefore modified to our code base. The new flag was excluded from our TSAN build after discussing with Fabien.

Test Plan
make check
test_runner.py
./bitcoin-qt -> settings -> Encrypt Wallet -> set password and/or change password if already encrypted
./bench_bitcoin

old: BenchLockedPool, 5, 530, 5.15069, 0.00192059, 0.00199956, 0.00193796
new: BenchLockedPool, 5, 1300, 4.44411, 0.00067821, 0.000698535, 0.000678916

../configure CPPFLAGS=-DARENA_DEBUG
make check
test_runner.py
ABC_BUILD_NAME=build-asan build-configurations.sh

Diff Detail

Repository
rABC Bitcoin ABC
Branch
PR12048
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 7179
Build 12403: Bitcoin ABC Buildbot (legacy)
Build 12402: arc lint + arc unit

Event Timeline

Owners added a reviewer: Restricted Owners Package.Aug 16 2019, 23:53
Fabien requested changes to this revision.Aug 19 2019, 19:21

Please test password usage with the wallet and bitcoin-qt for sanity, as this is where this allocation thing is used and the unit test coverage seems pretty limited.

Note that this introduces a regression (https://github.com/bitcoin/bitcoin/pull/16161), but I don't think it's a big deal and it can probably wait for core to merge a fix.

Otherwise LGTM.

src/support/lockedpool.cpp
137

Braces

This revision now requires changes to proceed.Aug 19 2019, 19:21

It looks like Core is almost done with the patch for the regression this will add. I will update later once it is finished so they can be landed (hopefully) around the same time.

This revision now requires changes to proceed.Sep 25 2019, 17:35

Still waiting for PR16161.

deadalnix requested changes to this revision.Nov 28 2019, 13:43

Back on the queue.

This revision now requires changes to proceed.Nov 28 2019, 13:43
deadalnix requested changes to this revision.Dec 9 2019, 00:45

PR16161 was merged.

This revision now requires changes to proceed.Dec 9 2019, 00:45
deadalnix requested changes to this revision.Dec 11 2019, 02:41

It overall looks, good, expect the fact that many nits should have been done prior to the back port, and not have a handful of them in.

I would also like to know the reason why this is included as this, even though this is known to have bug.

src/support/lockedpool.cpp
137 ↗(On Diff #14594)

Doing a pass over the file to fix these on their own would have been a good first step.

This revision now requires changes to proceed.Dec 11 2019, 02:41
nakihito edited the test plan for this revision. (Show Details)

Originally I had to two separated because it would be easier for review and I had already previously discussed it with Fabien. I have now combined this and D4548 together after updating the summary, test plan, and title and rebasing.

src/support/lockedpool.cpp
137 ↗(On Diff #14594)

Moved these changes to D4704.

nakihito retitled this revision from Merge #12048: Use best-fit strategy in Arena, now O(log(n)) instead O(n) to Use best-fit strategy in Arena, now O(log(n)) instead O(n).Dec 12 2019, 22:28
nakihito edited the summary of this revision. (Show Details)

Needs rebase.

Snippet of first build failure:

[18:35:55] :	 [Step 1/1] *** Output of /tmp/sanitizer_logs/lsan.log.5542 ***
[18:35:55] :	 [Step 1/1] =================================================================
[18:35:55] :	 [Step 1/1] ==5542==ERROR: AddressSanitizer: SEGV on unknown address 0x00006a09e5e7 (pc 0x557701832be1 bp 0x7ffe9c418d60 sp 0x7ffe9c418bf0 T0)
[18:35:55] :	 [Step 1/1] ==5542==The signal is caused by a WRITE memory access.
[18:35:55] :	 [Step 1/1]     #0 0x557701832be0 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long) ../src/crypto/sha256_sse4.cpp:953
[18:35:55] :	 [Step 1/1]     #1 0x5577018303f3 in SelfTest ../src/crypto/sha256.cpp:690
[18:35:55] :	 [Step 1/1]     #2 0x557701830d05 in SHA256AutoDetect[abi:cxx11]() ../src/crypto/sha256.cpp:812
[18:35:55] :	 [Step 1/1]     #3 0x5576ffde713a in BasicTestingSetup::BasicTestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:54
[18:35:55] :	 [Step 1/1]     #4 0x557700a279fd in uint256_tests::basics::basics() ../src/test/uint256_tests.cpp:67
[18:35:55] :	 [Step 1/1]     #5 0x5577009f7927 in basics_invoker ../src/test/uint256_tests.cpp:67
[18:35:55] :	 [Step 1/1]     #6 0x5576ffe3c485 in boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) /usr/include/boost/function/function_template.hpp:118
[18:35:55] :	 [Step 1/1]     #7 0x7f51763fef5d in boost::detail::function::function_obj_invoker0<boost::detail::forward, int>::invoke(boost::detail::function::function_buffer&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54f5d)
[18:35:55] :	 [Step 1/1]     #8 0x7f51763feb64 in boost::execution_monitor::catch_signals(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54b64)
[18:35:55] :	 [Step 1/1]     #9 0x7f51763fec30 in boost::execution_monitor::execute(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54c30)
[18:35:55] :	 [Step 1/1]     #10 0x7f51763fecfc in boost::execution_monitor::vexecute(boost::function<void ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54cfc)
[18:35:55] :	 [Step 1/1]     #11 0x7f51764268a8 in boost::unit_test::unit_test_monitor_t::execute_and_translate(boost::function<void ()> const&, unsigned int) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7c8a8)
[18:35:55] :	 [Step 1/1]     #12 0x7f517640146a  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5746a)
[18:35:55] :	 [Step 1/1]     #13 0x7f517640172e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #14 0x7f517640172e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #15 0x7f5176403fd4 in boost::unit_test::framework::run(unsigned long, bool) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x59fd4)
[18:35:55] :	 [Step 1/1]     #16 0x7f5176424317 in boost::unit_test::unit_test_main(bool (*)(), int, char**) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7a317)
[18:35:55] :	 [Step 1/1]     #17 0x5576ffe2ba9f in main ../src/test/test_bitcoin_main.cpp:48
[18:35:55] :	 [Step 1/1]     #18 0x7f51752c409a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
[18:35:55] :	 [Step 1/1]     #19 0x5576ffdbd749 in _start (/home/teamcity/buildAgent/work/c4a5708f2bae7929/build/src/test/test_bitcoin+0x3b5749)
[18:35:55] :	 [Step 1/1] 
[18:35:55] :	 [Step 1/1] AddressSanitizer can not provide additional info.
[18:35:55] :	 [Step 1/1] SUMMARY: AddressSanitizer: SEGV ../src/crypto/sha256_sse4.cpp:953 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long)
[18:35:55] :	 [Step 1/1] ==5542==ABORTING
[18:35:55] :	 [Step 1/1] *** Output of /tmp/sanitizer_logs/lsan.log.5547 ***
[18:35:55] :	 [Step 1/1] =================================================================
[18:35:55] :	 [Step 1/1] ==5547==ERROR: AddressSanitizer: SEGV on unknown address 0x00006a09e5e7 (pc 0x55cec7e20be1 bp 0x7fff8db1bf80 sp 0x7fff8db1be10 T0)
[18:35:55] :	 [Step 1/1] ==5547==The signal is caused by a WRITE memory access.
[18:35:55] :	 [Step 1/1]     #0 0x55cec7e20be0 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long) ../src/crypto/sha256_sse4.cpp:953
[18:35:55] :	 [Step 1/1]     #1 0x55cec7e1e3f3 in SelfTest ../src/crypto/sha256.cpp:690
[18:35:55] :	 [Step 1/1]     #2 0x55cec7e1ed05 in SHA256AutoDetect[abi:cxx11]() ../src/crypto/sha256.cpp:812
[18:35:55] :	 [Step 1/1]     #3 0x55cec63d513a in BasicTestingSetup::BasicTestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:54
[18:35:55] :	 [Step 1/1]     #4 0x55cec63d5a37 in TestingSetup::TestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:79
[18:35:55] :	 [Step 1/1]     #5 0x55cec63d6c73 in TestChain100Setup::TestChain100Setup() ../src/test/test_bitcoin.cpp:146
[18:35:55] :	 [Step 1/1]     #6 0x55cec6fe36ec in txvalidationcache_tests::tx_mempool_block_doublespend::tx_mempool_block_doublespend() ../src/test/txvalidationcache_tests.cpp:39
[18:35:55] :	 [Step 1/1]     #7 0x55cec6fcf779 in tx_mempool_block_doublespend_invoker ../src/test/txvalidationcache_tests.cpp:39
[18:35:55] :	 [Step 1/1]     #8 0x55cec642a485 in boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) /usr/include/boost/function/function_template.hpp:118
[18:35:55] :	 [Step 1/1]     #9 0x7f1e9c7a0f5d in boost::detail::function::function_obj_invoker0<boost::detail::forward, int>::invoke(boost::detail::function::function_buffer&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54f5d)
[18:35:55] :	 [Step 1/1]     #10 0x7f1e9c7a0b64 in boost::execution_monitor::catch_signals(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54b64)
[18:35:55] :	 [Step 1/1]     #11 0x7f1e9c7a0c30 in boost::execution_monitor::execute(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54c30)
[18:35:55] :	 [Step 1/1]     #12 0x7f1e9c7a0cfc in boost::execution_monitor::vexecute(boost::function<void ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54cfc)
[18:35:55] :	 [Step 1/1]     #13 0x7f1e9c7c88a8 in boost::unit_test::unit_test_monitor_t::execute_and_translate(boost::function<void ()> const&, unsigned int) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7c8a8)
[18:35:55] :	 [Step 1/1]     #14 0x7f1e9c7a346a  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5746a)
[18:35:55] :	 [Step 1/1]     #15 0x7f1e9c7a372e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #16 0x7f1e9c7a372e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #17 0x7f1e9c7a5fd4 in boost::unit_test::framework::run(unsigned long, bool) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x59fd4)
[18:35:55] :	 [Step 1/1]     #18 0x7f1e9c7c6317 in boost::unit_test::unit_test_main(bool (*)(), int, char**) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7a317)
[18:35:55] :	 [Step 1/1]     #19 0x55cec6419a9f in main ../src/test/test_bitcoin_main.cpp:48
[18:35:55] :	 [Step 1/1]     #20 0x7f1e9b66609a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
[18:35:55] :	 [Step 1/1]     #21 0x55cec63ab749 in _start (/home/teamcity/buildAgent/work/c4a5708f2bae7929/build/src/test/test_bitcoin+0x3b5749)
[18:35:55] :	 [Step 1/1] 
[18:35:55] :	 [Step 1/1] AddressSanitizer can not provide additional info.
[18:35:55] :	 [Step 1/1] SUMMARY: AddressSanitizer: SEGV ../src/crypto/sha256_sse4.cpp:953 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long)
[18:35:55] :	 [Step 1/1] ==5547==ABORTING
[18:35:55]W:	 [Step 1/1] Process exited with code 1
[18:35:55]E:	 [Step 1/1] Process exited with code 1 (Step: Command Line)
This revision is now accepted and ready to land.Jan 8 2020, 22:05
markblundeberg added inline comments.
contrib/teamcity/build-configurations.sh
64 ↗(On Diff #15282)

Note that in combination with D5042, it means we now see the following kind of thing (harmless) in asan CI build log.

https://build.bitcoinabc.org/viewLog.html?buildId=29441&buildTypeId=BitcoinABC_Master_BitcoinAbcMasterAsan&tab=buildLog&_focus=1053&state=59#_state=59

[10:39:54]
[Step 1/1] Running 455 test cases...
[10:39:54]
[Step 1/1] 0x00000000x80ffc10 0x00000000000003f0 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc10 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x0000000000100000 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x0
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x0
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x0000000000100000 0x0
[10:39:54]
[Step 1/1]