[ADT] Add resize_for_overwrite method to SmallVector.

[njames93]

Summary

Analagous to the std::make_(unqiue|shared)_for_overwrite added in c++20.
If T is POD, and the container gets larger, any new values added wont be initialized.
This is useful when using SmallVector as a buffer where its planned to overwrite any potential new values added.
If T is not POD, new (Storage) T functions identically to new (Storage) T() so this will function identically to resize(size_type).

[njames93]

Fix a lint warning

[dexonsmith]

I wonder if this can be tested, something like:

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
EXPECT_EQ(5, V.back());
V.pop_back();
V.resize(V.size() + 1);
EXPECT_EQ(0, V.back());

llvm/include/llvm/ADT/SmallVector.h

466

This whitespace change seems unrelated; can you commit separately?

[njames93]

In D93532#2463881, @dexonsmith wrote:

I wonder if this can be tested, something like:

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
EXPECT_EQ(5, V.back());
V.pop_back();
V.resize(V.size() + 1);
EXPECT_EQ(0, V.back());

Was thinking of a good way to test what is essentially undefined behaviour, how will this work under msan??

llvm/include/llvm/ADT/SmallVector.h

466

It's not strictly unrelated, but it was a clang format artefact

[dexonsmith]

In D93532#2463995, @njames93 wrote:

In D93532#2463881, @dexonsmith wrote:

I wonder if this can be tested, something like:

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
EXPECT_EQ(5, V.back());
V.pop_back();
V.resize(V.size() + 1);
EXPECT_EQ(0, V.back());

Was thinking of a good way to test what is essentially undefined behaviour, how will this work under msan??

Given that we own SmallVector and destroy_range is a no-op, is it undefined behaviour?

If the problem is the call to new (&*) T;, then can we add a function in SmallVectorTemplateCommon (or whatever it is that's specialized for PODs) called uninitialized_construct or something that's definitely a no-op?

llvm/include/llvm/ADT/SmallVector.h

466

Hmm... is it possible that git-diff gives clang-format a different diff than Phab is showing? Phab's version doesn't have this statement changing except for the whitespace... if clang-format is getting the same diff and formatting the line, that sounds like a bug in clang-format; alternatively, I wonder if you ran clang-format when the patch was different and at the time it looked like the statement had changed?

[njames93]

In D93532#2464225, @dexonsmith wrote:

Given that we own SmallVector and destroy_range is a no-op, is it undefined behaviour?

If the problem is the call to new (&*) T;, then can we add a function in SmallVectorTemplateCommon (or whatever it is that's specialized for PODs) called uninitialized_construct or something that's definitely a no-op?

If the call to new (&*) T; is tripping sanitisers up, I'm happy to keep that behaviour. After calling resize_for_overwrite it should be required that you write to any newly allocated items before you read them, Explicitly making it a no-op will hide that testing route.
For the record I can't seem to run gtest under msan, there seems to be a false-positive use-of-uninitialized-value occurring in basic_string::push_back, obviously not related to this change.

llvm/include/llvm/ADT/SmallVector.h

466

Thats what I mean when I say an artefact from clang-format. I often format as I go.

[njames93]

Added test case, remove format artefact.

[dblaikie]

In D93532#2464225, @dexonsmith wrote:

In D93532#2463995, @njames93 wrote:

In D93532#2463881, @dexonsmith wrote:

I wonder if this can be tested, something like:

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
EXPECT_EQ(5, V.back());
V.pop_back();
V.resize(V.size() + 1);
EXPECT_EQ(0, V.back());

Was thinking of a good way to test what is essentially undefined behaviour, how will this work under msan??

Given that we own SmallVector and destroy_range is a no-op, is it undefined behaviour?

Ish. We have used msan_* and asan_* functions to annotate LLVM's allocators so that uses of memory that hasn't been allocated into the pool, but not assigned to any user of the allocator can be detected (or memory used after it's returned to the allocator). We can/possibly should add such annotations to SmallVector and I think it could catch bugs like this.

[dexonsmith]

LGTM. I'm hopeful we can somehow keep the tests once we instrument SmallVector for the sanitizers (see my comment below); even if not, I suppose we can drop the tests at that time.

In D93532#2464555, @dblaikie wrote:

In D93532#2464225, @dexonsmith wrote:

In D93532#2463995, @njames93 wrote:

Was thinking of a good way to test what is essentially undefined behaviour, how will this work under msan??

Given that we own SmallVector and destroy_range is a no-op, is it undefined behaviour?

Ish. We have used msan_* and asan_* functions to annotate LLVM's allocators so that uses of memory that hasn't been allocated into the pool, but not assigned to any user of the allocator can be detected (or memory used after it's returned to the allocator). We can/possibly should add such annotations to SmallVector and I think it could catch bugs like this.

When that happens, will there be a way to update this testcase, maybe to something like this?

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
if (!is_sanitizer_poisoning_pop_back())
  EXPECT_EQ(5, V.back());

or:

V.resize_for_overwrite(V.size() + 1);
if (is_sanitizer_poisoning_pop_back())
  EXPECT_TRUE(is_sanitizer_poison(V.back()));
else
  EXPECT_EQ(5, V.back());

llvm/include/llvm/ADT/SmallVector.h

466

Ah, right, thanks.

llvm/unittests/ADT/SmallVectorTest.cpp

346

Nit: period at end of sentence.

357

Nit: period at end of sentence.

[njames93]

Period after comments.

[njames93]

In D93532#2466993, @dexonsmith wrote:

LGTM. I'm hopeful we can somehow keep the tests once we instrument SmallVector for the sanitizers (see my comment below); even if not, I suppose we can drop the tests at that time.

When that happens, will there be a way to update this testcase, maybe to something like this?

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
if (!is_sanitizer_poisoning_pop_back())
  EXPECT_EQ(5, V.back());

or:

V.resize_for_overwrite(V.size() + 1);
if (is_sanitizer_poisoning_pop_back())
  EXPECT_TRUE(is_sanitizer_poison(V.back()));
else
  EXPECT_EQ(5, V.back());

We can detect MSAN using

#if LLVM_MEMORY_SANITIZER_BUILD
// We have msan, don't run tests.
#else
<The test code>
#endif

If these tests are causing issues under msan, then just don't run them.
As an added bonus if the tests are failing under msan, that would mean that msan will help catch bugs when people abuse this by not writing to the new storage before reading.

[dblaikie]

In D93532#2466993, @dexonsmith wrote:

LGTM. I'm hopeful we can somehow keep the tests once we instrument SmallVector for the sanitizers (see my comment below); even if not, I suppose we can drop the tests at that time.

In D93532#2464555, @dblaikie wrote:

In D93532#2464225, @dexonsmith wrote:

In D93532#2463995, @njames93 wrote:

Was thinking of a good way to test what is essentially undefined behaviour, how will this work under msan??

Given that we own SmallVector and destroy_range is a no-op, is it undefined behaviour?

Ish. We have used msan_* and asan_* functions to annotate LLVM's allocators so that uses of memory that hasn't been allocated into the pool, but not assigned to any user of the allocator can be detected (or memory used after it's returned to the allocator). We can/possibly should add such annotations to SmallVector and I think it could catch bugs like this.

When that happens, will there be a way to update this testcase, maybe to something like this?

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
if (!is_sanitizer_poisoning_pop_back())
  EXPECT_EQ(5, V.back());

or:

V.resize_for_overwrite(V.size() + 1);
if (is_sanitizer_poisoning_pop_back())
  EXPECT_TRUE(is_sanitizer_poison(V.back()));
else
  EXPECT_EQ(5, V.back());

In D93532#2467643, @njames93 wrote:

In D93532#2466993, @dexonsmith wrote:

LGTM. I'm hopeful we can somehow keep the tests once we instrument SmallVector for the sanitizers (see my comment below); even if not, I suppose we can drop the tests at that time.

When that happens, will there be a way to update this testcase, maybe to something like this?

V.push_back(5);
V.pop_back();
V.resize_for_overwrite(V.size() + 1);
if (!is_sanitizer_poisoning_pop_back())
  EXPECT_EQ(5, V.back());

or:

V.resize_for_overwrite(V.size() + 1);
if (is_sanitizer_poisoning_pop_back())
  EXPECT_TRUE(is_sanitizer_poison(V.back()));
else
  EXPECT_EQ(5, V.back());

We can detect MSAN using

#if LLVM_MEMORY_SANITIZER_BUILD
// We have msan, don't run tests.
#else
<The test code>
#endif

If these tests are causing issues under msan, then just don't run them.
As an added bonus if the tests are failing under msan, that would mean that msan will help catch bugs when people abuse this by not writing to the new storage before reading.

Yep. Sounds good!

[grimar]

Nice! I've not realized this is a very new feature. Used it in D93761.

llvm/include/llvm/ADT/SmallVector.h

if (!this->isSmall())
       free(this->begin());
   }
 
   void clear() {
     this->destroy_range(this->begin(), this->end());
     this->Size = 0;
   }
 
-  void resize(size_type N) {
+private:
+  template <bool ForOverwrite> void resizeImpl(size_type N) {
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
       this->set_size(N);
     } else if (N > this->size()) {
       if (this->capacity() < N)
         this->grow(N);
       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
+        if (ForOverwrite)
+          new (&*I) T;
+        else
           new (&*I) T();
       this->set_size(N);
     }
   }
 
+public:
+  void resize(size_type N) { resizeImpl<false>(N); }
+
+  /// Like resize, but \ref T is POD, the new values won't be initialized.
+  void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
+
   void resize(size_type N, const T &NV) {
     if (N == this->size())
       return;
 
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
       this->set_size(N);
       return;

llvm/unittests/ADT/SmallVectorTest.cpp

 // Resize with fill value.
 TYPED_TEST(SmallVectorTest, ResizeFillTest) {
   SCOPED_TRACE("ResizeFillTest");
 
   this->theVector.resize(3, Constructable(77));
   this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
 }
 
+TEST(SmallVectorTest, ResizeForOverwrite) {
+  {
+    // Heap allocated storage.
+    SmallVector<unsigned, 0> V;
+    V.push_back(5);
+    V.pop_back();
+    V.resize_for_overwrite(V.size() + 1);
+    EXPECT_EQ(5, V.back());
+    V.pop_back();
+    V.resize(V.size() + 1);
+    EXPECT_EQ(0, V.back());
+  }
+  {
+    // Inline storage.
+    SmallVector<unsigned, 2> V;
+    V.push_back(5);
+    V.pop_back();
+    V.resize_for_overwrite(V.size() + 1);
+    EXPECT_EQ(5, V.back());
+    V.pop_back();
+    V.resize(V.size() + 1);
+    EXPECT_EQ(0, V.back());
+  }
+}
+
 // Overflow past fixed size.
 TYPED_TEST(SmallVectorTest, OverflowTest) {
   SCOPED_TRACE("OverflowTest");
 
   // Push more elements than the fixed size.
   this->makeSequence(this->theVector, 1, 10);
 
   // Test size and values.