Valgrind error in lockfree::queue

[adam@…]

The following code

#include <boost/lockfree/queue.hpp>

int main()
{
        int i = 0;
        boost::lockfree::queue<int*> q(128);

        q.push(&i);
        q.push(&i);

        return 0;
}

compiled with

g++ -o test test.cpp -I/opt/boost/include

produces the following valgrind output

==32040== Memcheck, a memory error detector
==32040== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==32040== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==32040== Command: ./test
==32040== 
==32040== Conditional jump or move depends on uninitialised value(s)
==32040==    at 0x401E77: boost::atomics::detail::base_atomic<boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>, void, 8u, false>::compare_exchange_strong(boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>&, boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node> const&, boost::memory_order, boost::memory_order) volatile (in /tmp/test)
==32040==    by 0x401DD9: boost::atomics::detail::base_atomic<boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>, void, 8u, false>::compare_exchange_weak(boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>&, boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node> const&, boost::memory_order, boost::memory_order) volatile (in /tmp/test)
==32040==    by 0x4019E0: boost::atomics::detail::base_atomic<boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>, void, 8u, false>::compare_exchange_weak(boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>&, boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node>, boost::memory_order) volatile (in /tmp/test)
==32040==    by 0x40121C: bool boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::do_push<false>(int* const&) (in /tmp/test)
==32040==    by 0x400CF6: boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::push(int* const&) (in /tmp/test)
==32040==    by 0x40097E: main (in /tmp/test)
==32040== 
==32040== Conditional jump or move depends on uninitialised value(s)
==32040==    at 0x40121F: bool boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::do_push<false>(int* const&) (in /tmp/test)
==32040==    by 0x400CF6: boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::push(int* const&) (in /tmp/test)
==32040==    by 0x40097E: main (in /tmp/test)
==32040== 
==32040== 
==32040== HEAP SUMMARY:
==32040==     in use at exit: 0 bytes in 0 blocks
==32040==   total heap usage: 129 allocs, 129 frees, 8,256 bytes allocated
==32040== 
==32040== All heap blocks were freed -- no leaks are possible
==32040== 
==32040== For counts of detected and suppressed errors, rerun with: -v
==32040== Use --track-origins=yes to see where uninitialised values come from
==32040== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 2 from 2)

This might be an issue with the atomic library, but I have not been able to track it further.

OS is Fedora F18 (3.8.3-203.fc18.x86_64)

G++ is g++ (GCC) 4.7.2 20121109 (Red Hat 4.7.2-8)

Valgrind is valgrind-3.8.1

[adam@…]

Patch to correct valgrind issue (as applied to version 1.53)

[adam@…]

I've attached a patch (attachment:lockfree.patch​) that resolves the issue for me.

Note that this basically involves uncommenting the initialisation of the next pointer in the queue::node structure. However, it looks very much like the code relies on this being uninitialised - so this patch probably breaks something else.

[timblechmann]

i will have to review this specific part carefully. the uninitialized part is related to the ABA prevention counter, simply initializing it may silent the valgrind warning, but introduce an ABA problem, so this patch might break the data structure in a very subtle way.

this issue could possibly be considered as `false positive' and the better way to silence the warning, might be to initialize the memory region, not in the constructor, but when allocating memory from the OS.

might take me some time to review all the code ...

[adam@…]

Revised patch that uses a custom allocator to zero initialise nodes.

[adam@…]

Having delved a little further I concur, the patch was more of a confirmation for me of where the warning was coming from.

On further analysis:

The warning does not occur if the container is not given a size at construction:

boost::lockfree::queue<int*> q;

and appears to be caused by the allocation, but not construction, of all the nodes in the freelist class.

If I understand correctly, it doesn't matter that the next tag is uninitialised, the only important thing is that the new tag is different to the old tag for tags that reside at the same address - so in that sense, this is a false positive (and the patch is bad!).

One option would be to add a constructor or policy to the freelist class that caused it to zero initialise memory on allocation, or to use a custom allocator with the same behaviour, which I think would suppress the warning. I don't think this would cause any issues because the freelist doesn't do any "real" deallocation until destruction.

I've attached another patch (attachment:lockfree2.patch​) that implements the custom allocator strategy. Again, this appears to successfully suppress the valgrind warning, I can't say whether or not there are other unintended side effects though.

[breese@…]

I get the same valgrind report. Furthermore, I get a similar report if I change the queue to use boost::lockfree::capacity<128>.

I am not so sure that valgrind is reporting a false positive. An uninitialized value means that it could be any value, including the one that causes the ABA problem.

Unfortunately, applying the second patch to the develop branch does not make the reports disappear.

[w.goesgens@…]

Is there any news on this? The patches wouldn't fix it for me, and the noise in valgrind is really anoying...

[anonymous]

Same here.Valgrind outputs a 'Conditional jump or move depends on uninitialised value(s)' about it.

[anonymous]

Same here with boost 1.58. Compiled in debug with --track-origins=yes, I have:

==10410== Conditional jump or move depends on uninitialised value(s)
==10410==    at 0x401939: compare_exchange_weak (ops_gcc_atomic.hpp:132)
==10410==    by 0x401939: compare_exchange_weak (atomic_template.hpp:386)
==10410==    by 0x401939: compare_exchange_weak (atomic_template.hpp:393)
==10410==    by 0x401939: bool boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::do_push<false>(int* const&) (queue.hpp:307)
==10410==    by 0x400C48: boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::push(int* const&) (queue.hpp:267)
==10410==    by 0x4008DC: main (plap.cpp:9)
==10410==  Uninitialised value was created by a stack allocation
==10410==    at 0x40361E: boost::atomics::atomic<boost::lockfree::detail::tagged_ptr<boost::lockfree::queue<int*, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::node> >::atomic() (atomic_template.hpp:680)