CLANG-16 UBSan Error constructor call with insufficient space for an object of type 'node_t'

[maierlars]

Our sanitizer runs have produced the following errors. UBSan claims that an object is constructed in a memory region that is too small for the object.

Details

``` /immer/immer/detail/hamts/node.hpp:224:26: runtime error: constructor call on address 0x60300009a540 with insufficient space for an object of type 'node_t' (aka 'immer::detail::hamts::node, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>') 0x60300009a540: note: pointer points here 00 00 00 00 be be be be be be be be be be be be be be be be be be be be be be be be 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:224:26 in /immer/immer/detail/hamts/node.hpp:229:12: runtime error: member access within address 0x60300009a540 with insufficient space for an object of type 'node_t' (aka 'immer::detail::hamts::node, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>') 0x60300009a540: note: pointer points here 00 00 00 00 01 00 00 00 be be be be be be be be be be be be be be be be be be be be 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:229:12 in /immer/immer/detail/hamts/node.hpp:229:12: runtime error: member access within address 0x60300009a540 with insufficient space for an object of type 'impl_t' (aka 'immer::detail::csl::member_two, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>::impl_data_t, immer::detail::csl::member>>::type::ownee>::type>::type>::type') 0x60300009a540: note: pointer points here 00 00 00 00 01 00 00 00 be be be be be be be be be be be be be be be be be be be be 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:229:12 in /immer/immer/detail/hamts/node.hpp:229:17: runtime error: member access within address 0x60300009a548 with insufficient space for an object of type 'immer::detail::hamts::node, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>::impl_data_t' 0x60300009a548: note: pointer points here be be be be be be be be be be be be be be be be be be be be 00 00 00 00 00 00 00 00 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:229:17 in /immer/immer/detail/hamts/node.hpp:229:19: runtime error: member access within address 0x60300009a548 with insufficient space for an object of type 'data_t' 0x60300009a548: note: pointer points here be be be be be be be be be be be be be be be be be be be be 00 00 00 00 00 00 00 00 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:229:19 in /immer/immer/detail/hamts/node.hpp:229:24: runtime error: member access within address 0x60300009a548 with insufficient space for an object of type 'inner_t' 0x60300009a548: note: pointer points here be be be be be be be be be be be be be be be be be be be be 00 00 00 00 00 00 00 00 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:229:24 in /immer/immer/detail/hamts/node.hpp:230:12: runtime error: member access within address 0x60300009a540 with insufficient space for an object of type 'node_t' (aka 'immer::detail::hamts::node, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>') 0x60300009a540: note: pointer points here 00 00 00 00 01 00 00 00 be be be be 00 00 00 00 be be be be be be be be be be be be 00 00 00 00 ^ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /immer/immer/detail/hamts/node.hpp:230:12 in /immer/immer/detail/hamts/node.hpp:230:12: runtime error: member access within address 0x60300009a540 with insufficient space for an object of type 'impl_t' (aka 'immer::detail::csl::member_two, std::shared_ptr>, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::hash_key, immer::map, std::shared_ptr, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>>::equal_key, immer::memory_policy>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5>::impl_data_t, immer::detail::csl::member>>::type::ownee>::type>::type>::type') 0x60300009a540: note: pointer points here 00 00 00 00 01 00 00 00 be be be be 00 00 00 00 be be be be be be be be be be be be 00 00 00 00 ```

A backtrace is also available:

    #0 0x55fcb55776b2 in make_inner_n /immer/immer/detail/hamts/node.hpp:224
    #1 0x55fcb55776b2 in immer::detail::hamts::champ<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>, std::shared_ptr<arangodb::consensus::Node const>>, immer::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>, std::shared_ptr<arangodb::consensus::Node const>, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy<arangodb::consensus::Node::AccountingHeap<arangodb::immer::thread_local_free_list_heap_policy<immer::cpp_heap, 1024ul>>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5u>::hash_key, immer::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>, std::shared_ptr<arangodb::consensus::Node const>, arangodb::consensus::Node::TransparentHash, arangodb::consensus::Node::TransparentEqual, immer::memory_policy<arangodb::consensus::Node::AccountingHeap<arangodb::immer::thread_local_free_list_heap_policy<immer::cpp_heap, 1024ul>>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5u>::equal_key, immer::memory_policy<arangodb::consensus::Node::AccountingHeap<arangodb::immer::thread_local_free_list_heap_policy<immer::cpp_heap, 1024ul>>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5u>::empty() /immer/immer/detail/hamts/champ.hpp:142
    #2 0x55fcb55afe70 in map /immer/immer/map.hpp:547

I had a closed look at the code in question:

    static node_t* make_inner_n(count_t n)
    {
        assert(n <= branches<B>);
        auto m = heap::allocate(sizeof_inner_n(n));
        auto p = new (m) node_t;
        assert(p == (node_t*) m);

        p->impl.d.data.inner.nodemap = 0;
        p->impl.d.data.inner.datamap = 0;
        p->impl.d.data.inner.values  = nullptr;
        return p;
    }

The size of the allocated memory is calculated using size_of_inner_n in the same file, which looks like this

    constexpr static std::size_t sizeof_inner_n(count_t count)
    {
        return immer_offsetof(impl_t, d.data.inner.buffer) +
               sizeof(inner_t::buffer) * count;
    }

Now the part that confuses me: The type impl_t is

using impl_t = combine_standard_layout_t<impl_data_t, refs_t, ownee_t>;

Since refs_t and ownee_t are empty classes, they are optimized away by combine_standard_layout_t. impl_data_t remains and is defined as

    struct inner_t
    {
        bitmap_t nodemap;
        bitmap_t datamap;
        values_t* values;
        aligned_storage_for<node_t*> buffer;
    };

    union data_t
    {
        inner_t inner;
        collision_t collision;
    };

    struct impl_data_t
    {
        data_t data;
    };

For now lets ignore what happens if collision_t which depends on T is actually bigger than inner_t. If make_inner_n is called with n = 0, it does not allocate enough memory, because the member buffer is no longer accounted for.

This indeed happens here:

    static node_t* empty()
    {
        static const auto node = node_t::make_inner_n(0);
        return node->inc();
    }

Any ideas whether this bogus or, if the above analysis is correct, how it can be fixed?
My first guess would be to patch sizeof_inner_n and always use max(1, n) instead of n.

[maierlars]

Indeed, the allocation is to small.

     constexpr static std::size_t sizeof_inner_n(count_t count)
     {
         auto const inner_size = immer_offsetof(impl_t, d.data.inner.buffer) +
                sizeof(inner_t::buffer) * count;
         return std::max(sizeof(node_t), inner_size);
     }

Fix the issue at hand. However, I think there are many more places where not enough memory is allocated for the objects that are constructed.

[arximboldi]

That buffer object is never used when N=0 as it used to construct in it the actual elements of the node (it also does not have constructor nor touches the memory unless we do it explicitly).

I see the solution in @jsteemann PR and that should fix the UB, but at the cost of some memory waste. Maybe a solution is to take the buffer type completely out of the struct, and append it (with correct alignment) after the struct "manually".

[maierlars]

That could work, indeed. I might give it a try later today.