[Boost-bugs] [Boost C++ Libraries] #11968: Undefined behavior in `boost::lockfree::queue`: nodes are always misaligned

Subject: [Boost-bugs] [Boost C++ Libraries] #11968: Undefined behavior in `boost::lockfree::queue`: nodes are always misaligned
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-02-09 13:22:03

#11968: Undefined behavior in `boost::lockfree::queue`: nodes are always misaligned
-------------------------------------+--------------------------
 Reporter:  yury.zaytsev@…           |      Owner:  timblechmann
     Type:  Bugs                     |     Status:  new
Milestone:  To Be Determined         |  Component:  lockfree
  Version:  Boost Development Trunk  |   Severity:  Showstopper
 Keywords:                           |
-------------------------------------+--------------------------
 Here is a minimal reproducer to illustrate the problem:

 {{{
 #include <boost/lockfree/queue.hpp>

 struct entry {
     int x = -1;
 };

 int main() {

     boost::lockfree::queue<entry, boost::lockfree::capacity<1>> queue;

     queue.push({0});

     entry d;
     queue.pop(d);

 }
 }}}

 {{{
 zaytsev_at_work:~/src/gcc$ g++ -std=c++14 -fsanitize=undefined lockfree.cpp
 zaytsev_at_work:~/src/gcc$ ./a.out
 /usr/include/boost/lockfree/detail/freelist.hpp:442:9: runtime error:
 constructor call on misaligned address 0x7fffd0831720 for type 'struct
 node', which requires 64 byte alignment
 0x7fffd0831720: note: pointer points here
  00 00 00 00  00 00 a6 5b 2a 7f 00 00  ff ff 00 00 01 00 00 00  40 17 83
 d0 ff 7f 00 00  f8 0a 40 00
               ^
 /usr/include/boost/lockfree/detail/freelist.hpp:454:9: runtime error:
 constructor call on misaligned address 0x7fffd08316e0 for type 'struct
 node', which requires 64 byte alignment
 0x7fffd08316e0: note: pointer points here
  ff 7f 00 00  02 00 60 00 00 00 00 00  70 08 40 00 00 00 00 00  88 50 60
 00 00 00 00 00  d9 64 a9 5b
               ^
 /usr/include/boost/lockfree/queue.hpp:102:19: runtime error: member access
 within misaligned address 0x7fffd08316e0 for type 'struct node', which
 requires 64 byte alignment
 0x7fffd08316e0: note: pointer points here
  ff 7f 00 00  02 00 60 00 00 00 00 00  70 08 40 00 00 00 00 00  88 50 60
 00 00 00 00 00  d9 64 a9 5b
               ^
 }}}

 This happens because nodes are declared to be cache line aligned in
 `queue.hpp`:

 {{{
 struct BOOST_LOCKFREE_CACHELINE_ALIGNMENT node { ... };
 }}}

 However, alignment to 64 bytes makes node an over-aligned type, and for
 such types the behavior is implementation defined. In particular, GCC 5.3,
 which was used for this test, doesn't seem to take alignment requirements
 of over-aligned types into account when allocating on the heap.

 Apparently, nobody has noticed this so far, because on x86 this will
 simply cause a slowdown, but on other targets, such as ARM, the program
 would be terminated with a `SIGBUS` if a misaligned read occurs. It could
 be that the problem reported here:
 https://github.com/boostorg/lockfree/issues/11 is a manifestation of this
 larger issue.

 Now, I would be happy to suggest a fix, but the problem is rather tricky.

 1. If the storage for nodes is allocated on the heap, then probably the
 fix is as simple as replacing the default `std::allocator` with
 `boost::aligned_allocator`.

 2. However, what makes `boost::lockfree::queue` particularly interesting
 is the support for compile-time sized storage. In this case, the situation
 is not so simple. One can get aligned storage with something like
 `boost::aligned_storage<size * sizeof(T), BOOST_LOCKFREE_CACHELINE_BYTES>
 data`, but is only part of the solution.[[br]][[br]]Indeed,
 `compiletime_sized_freelist_storage` should not only align `data`, but
 also over-allocate it, and the node allocator from the
 `fixed_size_freelist` should place nodes in `data` at appropriate
 positions so that not only the first, but also subsequent nodes remain
 aligned.

 3. In addition to that, `BOOST_LOCKFREE_CACHELINE_BYTES` should be exposed
 publicly as a constant and those who are passing custom allocators to the
 `boost::lockfree::queue` should use that together with
 `boost::aligned_allocator_adaptor` to make sure that their allocators
 honor the desired alignment.

 So, before investing any time in a patch, the problem has first to be
 discussed in more details... Maybe it also makes sense to change
 Boost.Lockfree to use Boost.Align, which was probably not used before
 because the former predated the latter.

 For now, the easiest stop gap solution that I can think of would be to
 patch out the alignment requirement, as it simply doesn't work as
 expected, but potentially causes problems for other architectures as x86.
 This would be something I would suggest doing ASAP for Boost 1.61.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11968>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.