Clang UBSAN alignment error in tbb::concurrent_hash_map

[BigBigos]

tbb::concurrent_hash_map uses an invalid pointer (rehash_req_flag == 3) to flag a node pointer that it should not be followed and rehash is required.

In advance_to_next_bucket() a pointer is loaded into a node* variable and then checked if it is valid:

my_node = static_cast<node*>( my_bucket->node_list.load(std::memory_order_relaxed) );
if( map_base::is_valid(my_node) ) {
    my_index = k; return;
}

However, at the point of the static_cast we already enter undefined behavior zone. It is undefined to have a pointer with a value that is not aligned according to the type requirements. Since node is 8-byte aligned and the pointer is 0x3, it is not aligned.

I guess tagged-pointers should be stored as uintptr_t and not T*.

Tested on Clang 13.0.0 and 14.0.5 (on Fedora) and tbb-2019_U2 and current master branch on this repository.

Reproducer (build using clang++ -g -fsanitize=undefined tbb-concurrent_hash_map-ubsan.cpp -o tbb-concurrent_hash_map-ubsan -ltbb):

#include <tbb/concurrent_hash_map.h>

int
main()
{
  tbb::concurrent_hash_map<int, int> map;

  map.insert({0, 0});
  auto it = map.begin();
  ++it;

  return 0;
}

UBSAN error:

/home/user/packages/tbb/include/tbb/../oneapi/tbb/concurrent_hash_map.h:446:23: runtime error: downcast of misaligned address 0x000000000003 for type 'tbb::detail::d2::hash_map_iterator<tbb::detail::d2::concurrent_hash_map<int, int>, std::pair<const int, int>>::node' (aka 'tbb::detail::d2::concurrent_hash_map<int, int>::node'), which requires 8 byte alignment
0x000000000003: note: pointer points here
<memory cannot be printed>
    #0 0x44a074 in tbb::detail::d2::hash_map_iterator<tbb::detail::d2::concurrent_hash_map<int, int, tbb::detail::d1::tbb_hash_compare<int>, tbb::detail::d1::tbb_allocator<std::pair<int const, int> > >, std::pair<int const, int> >::advance_to_next_bucket() /home/user/packages/tbb/include/tbb/../oneapi/tbb/concurrent_hash_map.h:446:23
    #1 0x43cc38 in tbb::detail::d2::hash_map_iterator<tbb::detail::d2::concurrent_hash_map<int, int, tbb::detail::d1::tbb_hash_compare<int>, tbb::detail::d1::tbb_allocator<std::pair<int const, int> > >, std::pair<int const, int> >::operator++() /home/user/packages/tbb/include/tbb/../oneapi/tbb/concurrent_hash_map.h:412:24
    #2 0x43c564 in main /home/user/tmp/tbb-concurrent_hash_map-ubsan.cpp:10:3
    #3 0x7f0a8542954f in __libc_start_call_main /usr/src/debug/glibc-2.35-15.fc36.x86_64/csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #4 0x7f0a85429608 in __libc_start_main@GLIBC_2.2.5 /usr/src/debug/glibc-2.35-15.fc36.x86_64/csu/../csu/libc-start.c:389:3
    #5 0x40c3d4 in _start (/home/user/tmp/tbb-concurrent_hash_map-ubsan+0x40c3d4) (BuildId: 041dac978f7d645ceb818ca3652899c4e21c0e8c)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/user/packages/tbb/include/tbb/../oneapi/tbb/concurrent_hash_map.h:446:23 in

[isaevil]

Fixed by #959.