flex_vector does not respect type alignment requirements

[sissow2]

Essentially, flex_vector can (always?) allocates objects at addresses that do not align with the type's alignment requirements. I uncovered this while using Eigen with immer, which causes some nasty segfaults when there are alignment violations on vectorized types.

I added a repro case here: sissow2@9d295b8 . The sanity check with std::vector passes always, while the immer::flex_vector variant always fails :

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flex_vector-alignment is a Catch v2.13.7 host application.
Run with -? for options

-------------------------------------------------------------------------------
direct alignment
-------------------------------------------------------------------------------
/home/sissow2/projects/immer/test/flex_vector/alignment.cpp:32
...............................................................................

... snip ...

/home/sissow2/projects/immer/test/flex_vector/alignment.cpp:41: FAILED:
  CHECK( v[i].is_aligned() )
with expansion:
  false

===============================================================================
test cases: 2 | 1 passed | 1 failed
assertions: 8 | 4 passed | 4 failed

This might be related to #228, but the reporter's repro case is for a non-vectorized type so I'm not sure it's the same issue.

I might be able to create a PR with a fix, but wondering if you have any ideas before I dive into it.

Also: I'm really liking this library! This and lager have been making my life so much easier. Also thanks for providing a nix-shell environment, it made creating this repro case a breeze.

[arximboldi]

Thanks a lot! Yes had issues with Eigen before which made me suspect for some time that this was the case. I somehow thought that I fixed this in the past but it is clearly still there. Thanks for the nice words and for finding a small repro case!

[sissow2]

So I did a bit of digging on this.

First, the current state. It looks like you've definitely thought about this before, since in rbts::node you wrap T in a std::aligned_storage_t. This does correctly change the alignof(node) to the appropriate value. Unfortunately, it looks like this mechanism is defeated because the buffer itself is initialized by a placement-new expression on an unaligned block of memory returned by MemoryPolicy::HeapPolicy::allocate. I think this is a loophole that erases the alignment requirements posed by the aligned_storage_t and therefore node.

I can see a couple solutions here:

• in rbts::node, add some machinery around leaf_t::buffer that over-sizes the buffer (based on alignment requirements), and adjust rbts::node::leaf() to apply an offset from the beginning of this buffer to ensure alignment.
• Make the allocators alignment-aware somehow. I don't have a specific proposal here.

If you want I can take a pass at either of these options, or something else that you have in mind. Or I can leave it be; I have a workaround I can use at the call site (turning off alignment optimizations for eigen types I store in immer containers).

[arximboldi]

Hi @sissow2!

Your assesment seems very much on point. Thanks a lot for looking into this. Either of the two approaches sounds good. Maybe the latter could be better as to keep the data-structure code simpler, but happy to take the other route if you feel like it's actually not much effort.

I don't have much time to look into this over the next few days, so if you wanna start the work it would be he greatly appreciated.

Also: can you reproduce this issue with some of the other data-structures?

[sissow2]

Re other data structures: I updated the repro case to check all the data structures, as well as different alignments: master...sissow2:immer:sissow2-alignment-flex-vector-bug. Here's what I found:

• with 16-byte alignment, I only observed failures with vector and flex_vector. Notably, vector<box<T>> was fine 🤔
• with 32-byte alignment, I observed failures with all data structures (intermittently)

The natural alignment of the compiler in nix-shell is 16 bytes. Since this is the case, it makes sense at the 32-byte case has more failures. What's surprising to me is that there are failures at all for the 16-byte case. Digging even deeper, it looks like the RBTS-based structures will use an optimized free list for their heap, while HAMTS structures do not do this optimization and will use debug_size_heap<cpp_heap> (which is 16-byte aligned). The 8 bytes of misalignment is therefore unique to the free list, which makes sense because free list nodes start with a pointer.

Re the allocator solution: Writing an allocator that is guaranteed to return aligned pointers seems to be quite the exercise, but fortunately c++17 added overloads to operator new (see 3) that accept a desired alignment as input. Working backwards from this, the API would change to HeapPolicy::[de]allocate(size_t size, std::align_val_t alignment). This unfortunately would bump the c++ version from 14 to 17. Some potential workarounds:

• Can do some #define magic to only enforce alignment in cpp_heap if C++17 is used
• Can replace cpp_heap with a custom alignment-aware implementation to work with C++14 as well. I'd need to do a bit of research on the state-of-the-art here though.

[arximboldi]

I do no think we need the C++17 alignment API since we use our own allocator API?

Memory allocated with new is alligned by default to alignof(std::max_align_t). It is us (me 😅) that broke the alignment with the metadata that heaps like debug_size_heap and free_list_heap. I think changing the HeapPolicy API and fixing those heaps adaptors should be enough.

[sissow2]

Hey, it just hit me I forgot to communicate back here-
I found a workaround that I can use in my own codebase, so I de-prioritized this as I needed to move on. I don't know when I'll have time to get back to this, so I just wanted to let you know not to wait on me!

Again, sorry for leaving this in limbo for so long.

[arximboldi]

No worries, I wasn't waiting for you. Thanks for checking in!