abseil / abseil/abseil-cpp

Use of uninitialized memory due to alias violation in (flat) map/set

Open
#975 4 comments 0 reactions 1 assignee Claimed by @sbenzaquen 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**

In short: The assumption stated at https://github.com/abseil/abseil-cpp/blob/311bbd2e50ea35e921a08186840d3b6ca279e880/absl/container/internal/container_memory.h#L322-L325 that accessing an inactive union member is allowed does not hold for at least GCC. This leads to reads of uninitialized memory which manifests in actual bugs and buffer-overruns (out-of-bounds access) in e.g. TensorFlow 2.4.1 with GCC 8.3-8.5. See https://github.com/tensorflow/tensorflow/issues/47179

The only solution is to remove this use of an union and in general do not alias classes in unions. It might be possible to work around this "mostly" with the `may_alias` GCC attribute, but that is also brittle and potentially inefficient.

**Detailed description**

The following code (simplified from TF) may read uninitialized memory and may place bogus values into the idx_vec (see the linked TF issue):
```
absl::flat_hash_map uniq;
Tensor Tin(N) = ...;
Tensor idx_vec out(N);
for (Eigen::Index i = 0, j = 0; i < N; ++i) {
auto it = uniq.emplace(Tin(i), j);
idx_vec(i) = it.first->second; // Invalid read here
if (it.second) {
++j;
}
}
```

The cause can be seen when removing all the abstractions happening inside the emplace and iterator dereferencing which boils down to:
```
// Preparation of flat_map
char* buffer = malloc(...);
slot_type* slot_buffer = reinterpret_cast(buffer);

// on emplace:
size_t x = ...;
slot_type* slot = slot_buffer + x;
new(slot) slot_type;
new(&slot->mutable_value) pair(k, v);
slot_type* slot2 = slot_buffer + x; // same as before, actually done through the iterator
const pair& element = slot->value; // https://github.com/abseil/abseil-cpp/blob/311bbd2e50ea35e921a08186840d3b6ca279e880/absl/container/internal/container_memory.h#L357
idx_vec[i] = element.second;
```

Not that `slot_type` is this union: https://github.com/abseil/abseil-cpp/blob/311bbd2e50ea35e921a08186840d3b6ca279e880/absl/container/internal/container_memory.h#L326-L337

Now the problem is that GCC does not implement "common initial sequence" exception referred to in https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 because it has major negative implications, see e.g. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65892 for some discussion on this topic.
GCC however does allow union-based aliasing if (and only if) accessed through the union, i.e. the following is explicitly supported by GCC:
```
union {
struct{ int x; } x;
struct{ int y; int z;} y;
} u;
u.x.x = 1;
return u.y.y;
```

What is not supported is taking pointers or accesses not involving the union:
```
union {
struct{ int x; } x;
struct{ int y; int z;} y;
} u;
auto& x = u.x;
auto& y = u.y;
x.x = 1;
return y.y;
```

Plausible reasoning: Type based alias analysis sees different types for x and y and hence assumes those do not alias.

This is what happens in the case of of the slot-type or in general with member functions:
`new(&slot->mutable_value) pair(k, v);` is "translated" to:
```
pair* p = &slot->mutable_value; // no-op placement new
p->pair::pair(k, v); // ctor call which in turn is expanded to:
this->first = k;
this->second = v;
```

As you can see the "access through union" rule gets violated in 2 places: a pointer to an (aliased) member is created, the pointer is used in a (special) member function (here: constructor). In both cases the "reference" to the union is lost and GCC assumes this pointer does not alias a pointer to another type.

So coming back to the Abseil code:

```
new(&slot->mutable_value) pair(k, v); // Uses a pointer of type: pair
slot_type* slot = slot_buffer + x; // same as before, actually done through the iterator
const pair& element = slot->value;
idx_vec[i] = element.second; // Uses a pointer/reference of type pair
```

Hence the compiler assumes at some point that the write of the ctor and the read of the iterator are independent and schedules the load of the latter before the former for increased performance which in fact reads the (initially) uninitialized memory allocated at https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h#L1554-L1555

See also my discussion with a GCC developer at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65892

Final note: Again this is not something hypothetical but comes from an actual bug created when compiling otherwise valid code with GCC 8 for skylake/icelake. Things like `-fno-strict-aliasing` make it disappear as do changes to the code that seemingly affect instruction scheduling. E.g. reading the iterator a second time returns the correct value, but that is only be coincidence.

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.