abseil / abseil/abseil-cpp

flat_hash_map 'm[k1] = m[k2]' is surprisingly unsafe

Open
#1,281 1 comment 6 reactions 0 assignees View on GitHub
bug
Dominant language
C++
Stars
18.1k
Forks
3.2k
Avg merge
20h 36m
Merged PRs (30d)
1

Description

**Describe the bug**

Suppose `m` is a `flat_hash_map`, which contains a key `k2` and does not contain any key `k1`. Then simple operations like `m.emplace(k1, m[k2])` or `m[k1] = m[k2]` might initialize the value associated with `k1` to something other than the value associated with `k2`. This occurs because the reference to `m[k2]` is computed before a new slot is allocated for `k1`; if allocating that new slot results in a rehash, then the reference to `m[k2]` is invalidated before it is read.

While this behavior could theoretically be deduced from the documented reference invalidation rules, it is extremely subtle and confusing in practice, especially when porting code that previously used `std::unordered_map`. I think it would go a long way for the hidden hazard in these safe-looking operations to at least be called out in the documentation. If there's some mechanism (with acceptable performance cost) by which either or both could actually be made safe, so much the better.

**Steps to reproduce the bug**

```
absl::flat_hash_map> m{};
m.emplace(1, std::make_shared(3));
m.emplace(2, m[1]);
for (const auto& item : m) {
std::cout << item.first << " " << item.second.get() << "\n";
}
```
sample output:
```
1 0x90aec0
2 0
```
The address and order of lines may differ, but the key is that m[1] holds a non-null pointer and m[2] does not. Adding `m.rehash(4);` before the `emplace()` operations results in the expected behavior where `m[1]` and `m[2]` are printed with the same value.

**What version of Abseil are you using?**

Initially observed on revision `3e1983c5c07eb8a43ad030e770cbae023a470a04` (from December 2021). Also reproduces on `godbolt.org` which claims to live at HEAD.

**What operating system and version are you using**

Linux (Debian 10.5)

**What compiler and version are you using?**

Reproduces on gcc 11.0, gcc trunk, clang 15.0.0.

**What build system are you using?**

Not relevant, reproduces when compiling directly.

**Additional context**

N/A

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.