flat_hash_map::try_emplace() is not exception safe

[bluescarni]

The current try_emplace() implementation in raw_hash_map.h reads:

  template <class K = key_type, class... Args>
  std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) {
    auto res = this->find_or_prepare_insert(k);
    if (res.second)
      this->emplace_at(res.first, std::piecewise_construct,
                       std::forward_as_tuple(std::forward<K>(k)),
                       std::forward_as_tuple(std::forward<Args>(args)...));
    return {this->iterator_at(res.first), res.second};
}

In case the key of the value being emplaced is not already in the table, find_or_prepare_insert() will prepare the table metadata for insertion before constructing in-place the value from the supplied arugments via emplace_at().

The problem is that if the construction of the value in emplace_at() throws, then the table will be left in a state which is inconsistent:: although according to the metadata a value is present, in reality no value was actually constructed because of the exception that was raised. This will lead to UB and erratic runtime behaviour (e.g., double free on table destruction).

I took a look at some abseil internals and it seems to me that there might be an easy fix in terms of the erase_meta_only() member function of raw_hash_set.h:

  template <class K = key_type, class... Args>
  std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) {
    auto res = this->find_or_prepare_insert(k);
    if (res.second)
      try {
        this->emplace_at(res.first, std::piecewise_construct,
                         std::forward_as_tuple(std::forward<K>(k)),
                         std::forward_as_tuple(std::forward<Args>(args)...));
      } catch (...) {
        this->erase_meta_only(this->iterator_at(res.first));
        throw;
      }
    return {this->iterator_at(res.first), res.second};
  }

The only problem is that erase_meta_only() needs to become a protected function, rather than private, in order for it to be usable in that context.

With this modification, my test case does not crash any more in face of exceptions thrown in try_emplace(). I suspect a similar problem (and perhaps a similar solution) exists in the insert() function.

Do you think this fix is correct? If so, would you like me to open a PR?

I would really like to get this behaviour fixed in my code, so, if you say the fix is ok, I could in the meantime patch my own copy of abseil while waiting for an official resolution.

Thanks!

[fowles]

While this will work for flat_hash_map, it will leak memory for node_hash_map.

[mksppopov]

Hello! Any updates on this issue?

[joka921]

@higher-performance I also stumbled upon this error in our codebase. If you could point me to the right direction I would also contribute a fix. The problem seems to be a bit in the architecture:

• There's one function for preparing the slot (prepare_insert) which sets the slot to a state where it assumes that there is a valid element.

• The (possible) allocation for a slot + the construction in the element are done in one go (via PolicityTraits::construct. There's the issue, that those two can fail independently (allocation(for the node based containers) or construction.

• In case the construction fails, we have to undo two steps: the (possible) allocation (to avoid the memory leaks mentioned above) and the setting of the metadata.

• The setting of the metadata can be undone from the raw_hash_set interface, one must just remember to call it on all cases.

• The memory leak for the node hash maps that would occur by this fix are a separate bug imho, namely the involved policies not being leak-free. So the fix would be to ensure this to also make sure those policies immediately deallocate in the case of failure before rethrowing.

Please let me know what you think about this issue (it seems doable, as the implementation of all the involved containers boils down to raw_hash_set.h), but I would first like to discuss the structure of a possible fix, as it somewhat would change the architecture of this central class.

[higher-performance]

Hi @joka921, thanks for the suggestions. I did take a look at this earlier actually, but it seems that ensuring exception safety for the class (not just this function) is a nontrivial task that requires a fair amount of investigation and bandwidth. I should probably assign this back to @derekmauro so he can determine how to proceed.

[derekmauro]

The performance of this class is critical Google. Google also somewhat famously does not use exceptions in its C++ code. The SwissTable maintainers think it is not in Google's interest to support exception safety in this class because it will make future optimizations (some of which are being worked on right now) more difficult to implement. Exception-safe implementations will likely either have a runtime cost in the non-exception-safe case, or two code paths would have to be maintained. Exception-safe implementations will likely be under-tested and prone to bugs.

I think for now we may want to document the fact this this class is not exception safe.

[derekmauro]

Expanded on here: https://github.com/abseil/abseil-cpp/issues/1690#issuecomment-2181371793

https://github.com/abseil/abseil-cpp/commit/e181410198b58b8dffe6e62e24ad56e5d78e2790 documents that these containers are not exception safe.