abseil / abseil/abseil-cpp

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

未關閉
#975 4 則留言 0 個 reaction 已指派 1 人 已被 @sbenzaquen 認領 在 GitHub 檢視
bug
主要語言
C++
星號
18.1k
分支
3.2k
平均合併
20 小時 36 分鐘
30 天內合併 PR
1

描述

**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.

貢獻指南

開啟貢獻指南

評估

這個 Issue 還沒有評估資料。

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。