Comments (6)
dvyukov
commented on May 22, 2024
Hi Francisco,
Because the code uses atomic clang decided to emit calls to libatomic for these (not sure why, but it seems to be the case). TSan does not support libatomic at the moment. So this is probably a dup of #816.
from sanitizers.
frankist
commented on May 22, 2024
Hi @dvyukov,
Thanks for the answer. I was using gcc, which was forcing me to link libatomic due to my node class that was made of two uint32_t members (I found this odd). I decided to change the node class to a simple uint64_t, and use bitmasks to represent the index and aba instead, and libtatomic stopped being a requirement in the linking. However, TSAN seems to still complain, both with gcc and clang. Can this outcome still be explained by #816? If so, what are my options?
This is the new class:
class lockfree_index_stack
{
public:
using index_type = uint32_t;
static constexpr index_type npos() { return std::numeric_limits<index_type>::max(); }
lockfree_index_stack(index_type nof_indexes) :
top(make_node(0U, 0U)), next_idx(nof_indexes)
{
// Initialize the stack of next indexes like [1, 2, 3, ..., nof_indexes - 1, npos]
for (index_type i = 1; i < nof_indexes; ++i) {
next_idx[i - 1] = i;
}
next_idx[nof_indexes - 1] = npos();
}
index_type capacity() const { return next_idx.size(); }
index_type try_pop()
{
node old_top{top.load(std::memory_order_seq_cst)};
if (get_index(old_top) == npos()) {
return npos();
}
node new_top = make_node(next_idx[get_index(old_top)], get_next_aba(old_top));
while (not top.compare_exchange_weak(old_top, new_top, std::memory_order_seq_cst, std::memory_order_seq_cst)) {
if (get_index(old_top) == npos()) {
return npos();
}
new_top = make_node(next_idx[get_index(old_top)], get_next_aba(old_top));
}
return get_index(old_top);
}
void push(index_type index)
{
node old_top{top.load(std::memory_order_seq_cst)};
next_idx[index] = get_index(old_top);
node new_top = make_node(index, get_aba(old_top));
while (not top.compare_exchange_weak(old_top, new_top, std::memory_order_seq_cst, std::memory_order_seq_cst)) {
set_aba(new_top, get_aba(old_top));
next_idx[index] = get_index(old_top);
}
}
private:
using node = uint64_t;
node make_node(index_type index, index_type aba) { return (static_cast<uint64_t>(aba) << 32U) | index; }
uint32_t get_index(node n) const { return n & 0xFFFFFFFF; }
void set_index(node& n, index_type index) { n = (n & 0xFFFFFFFF00000000) | index; }
void set_aba(node& n, index_type aba) { n = (n & 0xFFFFFFFF) | (static_cast<uint64_t>(aba) << 32U); }
uint32_t get_aba(node n) const { return static_cast<uint32_t>((n & 0xFFFFFFFF00000000) >> 32U); }
uint32_t get_next_aba(node n) const { return static_cast<uint32_t>((n & 0xFFFFFFFF00000000) >> 32U) + 1; }
std::atomic<node> top;
std::vector<index_type> next_idx;
};from sanitizers.
dvyukov
commented on May 22, 2024
Please post full report with line numbers mappable to the provided source code.
from sanitizers.
frankist
commented on May 22, 2024
Sure. Here is the report:
368: ==================
368: WARNING: ThreadSanitizer: data race (pid=8313)
368: Write of size 4 at 0x7b0c00000080 by thread T1:
368: #0 lockfree_index_stack::push(unsigned int) /...l/lockfree_object_pool.h:64:21 (lockfree_object_pool_test+0xdb596) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #1 lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0::operator()() const /.../lockfree_object_pool_test.cpp:40:19 (lockfree_object_pool_test+0xdb596)
368: #2 void std::__invoke_impl<void, lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>(std::__invoke_other, lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/invoke.h:61:14 (lockfree_object_pool_test+0xdb596)
368: #3 std::__invoke_result<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>::type std::__invoke<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>(lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/invoke.h:96:14 (lockfree_object_pool_test+0xdb596)
368: #4 void std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:279:13 (lockfree_object_pool_test+0xdb596)
368: #5 std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> >::operator()() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:286:11 (lockfree_object_pool_test+0xdb596)
368: #6 std::thread::_State_impl<std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> > >::_M_run() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:231:13 (lockfree_object_pool_test+0xdb596)
368: #7 <null> <null> (libstdc++.so.6+0xdc252) (BuildId: e37fe1a879783838de78cbc8c80621fa685d58a2)
368:
368: Previous read of size 4 at 0x7b0c00000080 by thread T2:
368: #0 lockfree_index_stack::try_pop() /.../lockfree_object_pool.h:51:30 (lockfree_object_pool_test+0xdb350) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #1 lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0::operator()() const /.../lockfree_object_pool_test.cpp:45:32 (lockfree_object_pool_test+0xdb350)
368: #2 void std::__invoke_impl<void, lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>(std::__invoke_other, lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/invoke.h:61:14 (lockfree_object_pool_test+0xdb350)
368: #3 std::__invoke_result<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>::type std::__invoke<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0>(lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/invoke.h:96:14 (lockfree_object_pool_test+0xdb350)
368: #4 void std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:279:13 (lockfree_object_pool_test+0xdb350)
368: #5 std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> >::operator()() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:286:11 (lockfree_object_pool_test+0xdb350)
368: #6 std::thread::_State_impl<std::thread::_Invoker<std::tuple<lockfree_index_stack_test_concurrent_push_pop_Test::TestBody()::$_0> > >::_M_run() /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/std_thread.h:231:13 (lockfree_object_pool_test+0xdb350)
368: #7 <null> <null> (libstdc++.so.6+0xdc252) (BuildId: e37fe1a879783838de78cbc8c80621fa685d58a2)
368:
368: Location is heap block of size 40 at 0x7b0c00000060 allocated by main thread:
368: #0 operator new(unsigned long) <null> (lockfree_object_pool_test+0xd9796) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #1 std::__new_allocator<unsigned int>::allocate(unsigned long, void const*) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/new_allocator.h:137:27 (lockfree_object_pool_test+0xda7cb) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #2 std::allocator_traits<std::allocator<unsigned int> >::allocate(std::allocator<unsigned int>&, unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/alloc_traits.h:464:20 (lockfree_object_pool_test+0xda7cb)
368: #3 std::_Vector_base<unsigned int, std::allocator<unsigned int> >::_M_allocate(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/stl_vector.h:378:20 (lockfree_object_pool_test+0xda7cb)
368: #4 std::_Vector_base<unsigned int, std::allocator<unsigned int> >::_M_create_storage(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/stl_vector.h:395:33 (lockfree_object_pool_test+0xda7cb)
368: #5 std::_Vector_base<unsigned int, std::allocator<unsigned int> >::_Vector_base(unsigned long, std::allocator<unsigned int> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/stl_vector.h:332:9 (lockfree_object_pool_test+0xda7cb)
368: #6 std::vector<unsigned int, std::allocator<unsigned int> >::vector(unsigned long, unsigned int const&, std::allocator<unsigned int> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/stl_vector.h:566:9 (lockfree_object_pool_test+0xda7cb)
368: #7 lockfree_index_stack(unsigned int) /.../lockfree_object_pool.h:33:76 (lockfree_object_pool_test+0xda7cb)
368: #8 lockfree_index_stack_test_concurrent_push_pop_Test::TestBody() /.../lockfree_object_pool_test.cpp:25:32 (lockfree_object_pool_test+0xda7cb)
368: #9 void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) <null> (lockfree_object_pool_test+0x10fb3e) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368:
368: Thread T1 (tid=8315, running) created by main thread at:
368: #0 pthread_create <null> (lockfree_object_pool_test+0x597dd) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xdc328) (BuildId: e37fe1a879783838de78cbc8c80621fa685d58a2)
368: #2 void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) <null> (lockfree_object_pool_test+0x10fb3e) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368:
368: Thread T2 (tid=8316, finished) created by main thread at:
368: #0 pthread_create <null> (lockfree_object_pool_test+0x597dd) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368: #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xdc328) (BuildId: e37fe1a879783838de78cbc8c80621fa685d58a2)
368: #2 void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) <null> (lockfree_object_pool_test+0x10fb3e) (BuildId: 03407d40baffb4da9861f82d0af15cbe8f8adf70)
368:
368: SUMMARY: ThreadSanitizer: data race /.../lockfree_object_pool.h:64:21 in lockfree_index_stack::push(unsigned int)
368: ==================
The reported line numbers correspond to the following code lines:
lockfree_object_pool.h:64:21-->next_idx[index] = get_index(old_top);lockfree_object_pool.h:51:30-->node new_top = make_node(next_idx[get_index(old_top)], get_next_aba(old_top));lockfree_index_stack(unsigned int) /.../lockfree_object_pool.h:33:76-->top(make_node(0U, 0U)), next_idx(nof_indexes)
So in summary, every time I touch next_idx[index] I get a TSAN warning. However, given that for the same index, the pop and push are done by the same thread (notice that the vector vals of the test is local to the thread), I don't see how this is a data race.
from sanitizers.
dvyukov
commented on May 22, 2024
The report looks legit. In the lock-free stack next links must also be atomic.
Consider, one thread is doing this in try_pop:
node new_top = make_node(next_idx[get_index(old_top)], get_next_aba(old_top));
now another thread pops the top element and pushes it again (potentially with another next link), this involves this write:
next_idx[index] = get_index(old_top);
This still runs concurrently with the read in the first thread.
from sanitizers.
frankist
commented on May 22, 2024
Ok, if I understood correctly, even if the cas operation will fail inside the first pop call (due to the other thread doing pop+push), this is considered a data race. In that case, the only way to avoid would be to make the array elements atomic and access them with relaxed memory ordering. Thanks, for clarifying this.
from sanitizers.
Related Issues (20)
- allocator_may_return_null=1 does not seem to work, hindering fuzzing for security issues
- AddressSanitizer: SEGV in malloc_trim
- can not be detected by asan HOT 5
- TestCases/stack-uas.c occasionally misclassified as stack-buffer-overflow
- Empty code randomly crashes with SEGV on unknown address HOT 5
- MSAN+libfuzzer reports error in libfuzzer code with '-jobs=X' (Uninitialized bytes in fputs) HOT 1
- Suppressing "heap-use-after-free" does not work in called functions
- What is -[ClassName objCMethodToSuppress:]??? HOT 1
- TSAN_OPTIONS="log_path=/var/log/xxxx_tsan" doesn't work, the logs still print on stdout
- [tsan] False positive when reading from a pipe in io_uring
- MSan false negatives due to "[SCCP] Don't mark edges feasible when resolving undefs"
- Feature Request: Allow a white list, as the black list based supression don't work well. HOT 3
- [ppc][compiler-rt] Potential miscompile in compiler-rt HOT 1
- test/tsan/getline_nohang.cpp hangs with HOT 7
- msan reports stat() result as undefined on glibc 2.37 HOT 5
- UseAfterReturn Wiki : Enabled By Default in GCC 13 (+ Clang 15)?
- Support for Multiple suppression files in TSAN
- How to output memory snapshots
- Debugging C++ Segmentation Fault in Leak Sanitizer - Need Help with Backtrace Analysis
- Is Asan compatible with -fstack-protector-strong ?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from sanitizers.