[BUG] Segmentation fault after move assign of map with different allocator

[tokiura]

A move assignment of map_A, which uses allocator A, to map_B, which uses allocator B, terminates the program by SIGSEGV.

Here is simple code to reproduce it on Compiler Explorer. (Exits with double free or corruption)
https://gcc.godbolt.org/z/hGh8v1xfM

This is probably because the move assignment (or move constructor) replaces the m_bucket with m_bucket of the "other".

unordered_dense/include/ankerl/unordered_dense.h

Lines 1223 to 1224 in e88dd1c

	m_values = std::move(other.m_values);
	m_buckets = std::exchange(other.m_buckets, nullptr);

The default behavior of std::vector move assignment is not to propagate the allocator. So, if the allocator of m_values is different from the one allocating other.m_backet, it appears that subsequent allocate() and deallocate() for m_backet will not work correctly.

[martinus]

Hi @tokiura, thanks a lot for finding this, especially the reproducer! I'll merge a fix soon.

[martinus]

Fixed in release v4.0.2.

[tokiura]

First of all, thanks for the quick fix and release!

But. I am sorry to say that I have found an omission in my test case.
A similar problem was found to occur with move constructs with allocator arguments.

I have added the following pattern based on your added tests.

    {
        int_str_map map_default_resource_construct(
            return_hello_world(&pool), ANKERL_UNORDERED_DENSE_PMR::new_delete_resource());
        std::cout << map_default_resource.contains(0) << std::endl;
    }

https://gcc.godbolt.org/z/f8a54rYYP

Also, and this may be my misunderstanding, there may be a possible memory leak in fix a9893b3.

After the buckets are copied, other.m_num_buckets is set 0.

            m_num_buckets = std::exchange(other.m_num_buckets, 0);

So it seems that the second argument of the following deallocate is always set to zero during the "other" destruction.

    ~table() {
        if (nullptr != m_buckets) {
            auto ba = bucket_alloc(m_values.get_allocator());
            bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());   // bucket_count() is zero after move assignment
        }
    }

However, Valgrind did not find any leaks. I could not determine if there was actually no problem or if it was just a coincidence that it did not leak.

[martinus]

thanks, on a second look I saw that as well. Also it doesn't work yet for segmented_map. I'll fix that when I have time.

[martinus]

I've got another update, @tokiura could you try the version from the PR #81: https://raw.githubusercontent.com/martinus/unordered_dense/2023-07-fix-more-move-allocator-issues/include/ankerl/unordered_dense.h

[phprus]

@martinus

unordered_dense/include/ankerl/unordered_dense.h

Lines 1232 to 1238 in a9893b3

	m_num_buckets = std::exchange(other.m_num_buckets, 0);
	m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
	m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor);
	m_hash = std::exchange(other.m_hash, {});
	m_equal = std::exchange(other.m_equal, {});
	m_shifts = std::exchange(other.m_shifts, initial_shifts);
	other.m_values.clear();

I think the exchange should only be when moving. When copying buckets, there should be copying of parameters, as here:

unordered_dense/include/ankerl/unordered_dense.h

Lines 1205 to 1214 in a9893b3

	auto operator=(table const& other) -> table& {
	if (&other != this) {
	deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
	m_values = other.m_values;
	m_max_load_factor = other.m_max_load_factor;
	m_hash = other.m_hash;
	m_equal = other.m_equal;
	m_shifts = initial_shifts;
	copy_buckets(other);
	}

[tokiura]

Thank you, @martinus.
I have confirmed that SIGSEGV is gone at all. But, it appears that the very large number of assignments caused the memory leakage that was a concern.

So I checked again with a simple case.
In my environment, 1 GB of RAM was used during the following 10 million assignments.

        for (int i=0; i<10000000; i++)
            map_default_resource = return_hello_world(&pool);

(In this case, the memory pool increases monotonically, but is eventually released by the destructor of the pool allocator, so Valgrind says "no leaks are possible".)

I think @phprus ' suggestion is one possible solution. I have confirmed that simply copying "other" eliminates memory leaks.
Or calling deallocate_buckets() of other may another solution.

    auto operator=(table&& other) noexcept(
        noexcept(std::is_nothrow_move_assignable_v<value_container_type>&& std::is_nothrow_move_assignable_v<Hash>&&
                     std::is_nothrow_move_assignable_v<KeyEqual>)) -> table& {
        if (&other != this) {
            deallocate_buckets(); // deallocate before m_values is set (might have another allocator)
            m_values = std::move(other.m_values);

            // we can only reuse m_buckets over when both maps have the same allocator!
            if (get_allocator() == other.get_allocator()) {
                m_buckets = std::exchange(other.m_buckets, nullptr);
                m_num_buckets = std::exchange(other.m_num_buckets, 0);
                m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
            } else {
                copy_buckets(other);
                // Deallocate bucket to avoid memory leak.
                // m_num_buckets and m_max_bucket_capacity of other are set simultaneously.
                other.deallocate_buckets();
            }
            m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor);
            m_hash = std::exchange(other.m_hash, {});
            m_equal = std::exchange(other.m_equal, {});
            m_shifts = std::exchange(other.m_shifts, initial_shifts);
            other.m_values.clear();
        }
        return *this;
    }

Both work fine.

[martinus]

Ah, it took me a long time now to see how that really is a memory leak. Thanks again for the reproducer! The issue is jus this line

m_num_buckets = std::exchange(other.m_num_buckets, 0);

The problem was that the destructor uses bucket_count() so it used the wrong size for the deallocate.

I've updated the code, I believe all these problems errors are now fixed. Please try again:

https://raw.githubusercontent.com/martinus/unordered_dense/2023-07-fix-more-move-allocator-issues/include/ankerl/unordered_dense.h

[tokiura]

I too have confirmed that all issues have been resolved.
Thank you very much!

[martinus]

I'll release version 4.0.4 with the fix.