Concurrent extraction leads to undefined behavior

[WarrantyVoid]

For parallel_flat_hash_map, calling extract(Key) on elements with the same key from multiple threads at once appears to lead to an assertion and undefined behavior regardless of mutex/lock type being used.

Assertion happens in function:
void erase_meta_only(const_iterator it) :
assert(IsFull(*it.inner_.ctrl_) && "erasing a dangling iterator");

Is this expected? Or am I misusing the class? It is the class implementation itself which leaves the iterator dangling, so I can't see any leverage on my side. I would have expected as graceful behavior in such a situation, that the concurrent extract(Key) of same element simply returns an empty node handle as if the element never existed in the first place.

[greg7mdp]

Yes, using iterators is not thread-safe. see the last sentence of:

parallel-hashmap/README.md

Line 308 in 0cd57d2

- The *parallel* tables can be made internally thread-safe for concurrent read and write access, by providing a synchronization type (for example [std::mutex](https://en.cppreference.com/w/cpp/thread/mutex)) as the last template argument. Because locking is performed at the *submap* level, a high level of concurrency can still be achieved. Read access can be done safely using `if_contains()`, which passes a reference value to the callback while holding the *submap* lock. Similarly, write access can be done safely using `modify_if`, `try_emplace_l` or `lazy_emplace_l`. However, please be aware that iterators or references returned by standard APIs are not protected by the mutex, so they cannot be used reliably on a hash map which can be changed by another thread.

How do you get the iterator before calling extract()? That same part of the README above lists some functions that can be used to safely access from multiple threads.

[WarrantyVoid]

Thanks for the quick reply greg, it's very appreciated. As described though, I was calling extract(Key), with a key as parameter, only the hash map implementation itself internally calls subfunctions with iterators. With "regardless of mutex/lock type being used" I wanted to state that I have been trying boosts and absl mutex as last parameter in parallel_flat_hash_map, but the assertion keeps occurring regardless. This is one of the type definitions I've tried:

using Map = phmap::parallel_node_hash_map<Key, Value, Hash, KeyEqual, phmap::priv::Allocator<phmap::priv::Pair<const Key, Node>>, 4Ui64, absl::Mutex>;

I have gone through the readme prior to posting this ticket, as I didn't want to waste your time, but I just don't know how to help myself rn. On another note: Did you bench versus follys ConcurrentHashMap at some point?

[greg7mdp]

Hi @WarrantyVoid , my mistake, I didn't realize you were using the second version of extract that takes a key.
I just pushed a tentative fix for this issue. Can you give it a try? Thanks!

[WarrantyVoid]

Nevermind greg, I'm really grateful for your efforts. #280 doesn't appear to do the trick though, it still shows the very same behavior with this change (first assertion, then undefined behavior). In my perspective, the issue is that the thread context break happens in between line 3563 and 3564. So after find() was executed, the returned iterator can be concurrently invalidated, before it is passed to the inner extract(iterator) function. This is why the added shared lock to find() has not the desired effect. In my (unfortunately not so minimal) test setup, I basically just have a 'parallel_flat_hash_map' preinitialized with 1m values, then in 10 threads, 10 identical 'for' loops attempt to extract all values. It crashes within first second. Erasing elements has the same effect.

[greg7mdp]

Yes, you are right, iterators are not protected. What was I thinking!

There should be a way tioo do it using if_contains, but maybe I have to rearrange the code some, let me have a look when I have a minute later today.

[greg7mdp]

Well, on second thoughts, it should have worked as is. The call to find does lock the set mutex, and then moves it (without releasing the lock) to the SharedLock declared at line 3562:

parallel-hashmap/parallel_hashmap/phmap.h

Lines 3562 to 3564 in b56fe78

	SharedLock m;
	auto it = this->template find<K, SharedLock>(key, this->hash(key), m);
	return it == end() ? node_type() : extract(const_iterator{it});

which should hold the lock, and thus preventing the iterator from being invalidated, at least until the end of the function. I am surprised that you would hit the same assertion in erase_meta_only.

However, upon the return of extract, the mutex is released, but since you use the parallel_node_hash_map, accessing the returned pointer should be safe.
I don't know what the issue could be. If you can provide me with a small sample program reproducing the issue, I'll look into it further.

[greg7mdp]

@WarrantyVoid , I was using UniqueLock in extract() instead of SharedLock. Makes no difference for std::mutex, but since you are using absl::Mutex it was incorrect.

[WarrantyVoid]

You're right, the locking section extent wasn't the problem, the type of lock might be the issue.
I think instead of a SharedLock, maybe UniqueLock needs to be used.
At least that's how I got the crash to disappear.
I do not understand the implementation entirely in all detail, but my ratio is, that the lock acquired through find(), is later also used for writing/erasing, which is why shared locking is not enough.

[greg7mdp]

that the lock acquired through find(), is later also used for writing/erasing, which is why shared locking is not enough.

Yes, exactly, the erase_meta_only() modifies the map, so we need a unique lock.

[greg7mdp]

Thank you for reporting the issue, @WarrantyVoid , glad it is fixed.

[WarrantyVoid]

Thanks for your help as well.
Teamwork :)

[WarrantyVoid]

Oh. damn..no. I think the extract() function itself might be solved, but I fear the structural problem runs way deeper.
E.g. look at code of 'at(Key)' function:

template <class K = key_type, class P = Policy>
MappedConstReference<P> at(const key_arg<K>& key) const {
    auto it = this->find(key);
    if (it == this->end())
        phmap::base_internal::ThrowStdOutOfRange("phmap at(): lookup non-existent key");
    return Policy::value(&*it);
}

Same underlying issue: The iterator returned by find() could be invalidated by a concurrent erase at any point of time in the function. There is no way to safely access values though iterators returned by 'find(Key)', while there are concurrent deletions, especially not outside of map implementation itself. At this point, I fear, this implementation simply cannot be used with concurrent erasing of elements and I have to find something different. I will not create another issue for this, but I still want to make you aware of the general limitation.