[scudo] Use MemMap in Vector

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/tests/vector_test.cpp

26–29

This is way too big. It'll simply increase the running time of the tests without verifying many stuff. Given the use of vector is restricted and the static buffer is hard coded and which is small. I think the original size is good enough.

compiler-rt/lib/scudo/standalone/vector.h

34

Can you move the destroy() to protected and only reset this to nullptr when it's using external buffer? Besides, we may want to call clear() before the buffer destruction

89

I think it's fine to omit the comment here and below in this function. The code is self-explained pretty clear.

106–107

I would merge the comment with the comment of VectorNoCtor and it will look like

// A low-level vector based on map. To reduce memory overhead for small vectors, it'll 
// use a local buffer when available. Otherwise, a external memory buffer will be used. 
// The current implementation supports only POD types.

[fabio-d]

compiler-rt/lib/scudo/standalone/tests/vector_test.cpp

26–29

Thanks, the original size (1000 elements) ended up testing 4000 bytes (1 page*) or 8000 bytes (2 pages*), depending of whether the architecture is a 32 or 64 bit one. * = assuming that a page is 4096 bytes, which is not universally true

I've modified the code so that it always tests with 2 pages on all platforms to address your performance concerns. This ensures that we always test both kinds of transitions:

• from the internal buffer to an external one
• from an external buffer to another larger external buffer

compiler-rt/lib/scudo/standalone/vector.h

34

1. If I make destroy() protected, direct users of VectorNoCtor will not be able to release its memory when they are done with it. On the other hand, there no such users today, as VectorNoCtor is only indirectly used through the Vector<T> class defined below, which subclasses it. That said, do you think that we should still make it protected (along with init, I'd say, for symmetry) and document that VectorNoCtor can only be used through its Vector<T> wrapper, or should we leave all the necessary methods public and available for direct usage?

2. About resetting Data to nullptr, my intent was to poison the object to catch use-after-destroy more easily, but I realized it wouldn't have worked in all the cases, so I removed it in this new revision of the CL. On a related note, we can't clear() from here as that would set Size = 0, and this function is also called when growing the vector, and we don't want to forget its size from there. If we want to poison it properly, we can separate this code path from the path that grows the vector, and ensure that destroy() always leaves it in pre-init state (i.e. with all the fields set to zero and no external buffer). What do you think?

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/tests/vector_test.cpp

26–29

I'm not concerning the performance of this test. I'm thinking of the necessity of doing this and what's the frequency/cost of having bugs in this vector. This is not a general used vector and have very limited use cases.

The scenarios you are trying to test depend on the buffer extension policy. What if we always prepare dynamic buffer with starting size 128K? Then we won't be able to cover the scenarios as mentioned.

Again, this is not a general used vector (nor having complex functions). In addition, other tests that use this vector also verify the functions indirectly. I'm not sure what's the benefit of testing these scenarios at this moment

compiler-rt/lib/scudo/standalone/vector.h

34

You're right, we can't use clear() directly here. Please ignore that suggestion.

I'm not sure why we have to *poison* the Data. Like you said, use-after-destroy is not a case we have to worry here.

As mentioned, this is designed to be generally used. The purpose of destroy() is ambiguous now. I would suggest that only use Vector and disallow the direct use of VectorNoCtor. I'm planning some changes on this but it has lower priority now anyway.

[fabio-d]

compiler-rt/lib/scudo/standalone/tests/vector_test.cpp

26–29

Done, I've removed all the changes to the test from this CL

compiler-rt/lib/scudo/standalone/vector.h

34

Done, I've made init() and destroy() protected and explained that direct usage of VectorNoCtor is disallowed in the comment at the top

[Chia-hungDuan]

Thanks!

compiler-rt/lib/scudo/standalone/tests/vector_test.cpp

TEST(ScudoVectorTest, Basic) {
   EXPECT_EQ(V[0], 42);
   V.push_back(43);
   EXPECT_EQ(V.size(), 2U);
   EXPECT_EQ(V[0], 42);
   EXPECT_EQ(V[1], 43);
 }
 
 TEST(ScudoVectorTest, Stride) {
+  // Fill two pages of elements, to exercise the code that grows the buffer as
+  // needed by allocating a bigger buffer and copying the old contents in it.
+  scudo::uptr NumElements =
+      2U * scudo::getPageSizeCached() / sizeof(scudo::uptr);
+
   scudo::Vector<scudo::uptr> V;
-  for (scudo::uptr I = 0; I < 1000; I++) {
+  for (scudo::uptr I = 0; I < NumElements; I++) {
     V.push_back(I);
     EXPECT_EQ(V.size(), I + 1U);
     EXPECT_EQ(V[I], I);
   }
-  for (scudo::uptr I = 0; I < 1000; I++)
+  for (scudo::uptr I = 0; I < NumElements; I++)
     EXPECT_EQ(V[I], I);
 }
 
 TEST(ScudoVectorTest, ResizeReduction) {
   scudo::Vector<int> V;
   V.push_back(0);
   V.push_back(0);
   EXPECT_EQ(V.size(), 2U);
   V.resize(1);
   EXPECT_EQ(V.size(), 1U);
 }

compiler-rt/lib/scudo/standalone/vector.h

 //===-- vector.h ------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_VECTOR_H_
 #define SCUDO_VECTOR_H_
 
-#include "common.h"
+#include "mem_map.h"
 
 #include <string.h>
 
 namespace scudo {
 
-// A low-level vector based on map. May incur a significant memory overhead for
-// small vectors. The current implementation supports only POD types.
+// A low-level vector based on map. It stores the contents inline up to a fixed
+// capacity, or in an external memory buffer if it grows bigger than that. May
+// incur a significant memory overhead for small vectors. The current
+// implementation supports only POD types.
 template <typename T> class VectorNoCtor {
 public:
   constexpr void init(uptr InitialCapacity = 0) {
     Data = &LocalData[0];
     CapacityBytes = sizeof(LocalData);
     if (InitialCapacity > capacity())
       reserve(InitialCapacity);
   }
   void destroy() {
     if (Data != &LocalData[0])
-      unmap(Data, CapacityBytes, 0, &MapData);
+      ExternalBuffer.unmap(ExternalBuffer.getBase(),
+                           ExternalBuffer.getCapacity());
   }
   T &operator[](uptr I) {
     DCHECK_LT(I, Size);
     return Data[I];
   }
   const T &operator[](uptr I) const {
     DCHECK_LT(I, Size);
     return Data[I];
   }
public:
   T *begin() { return data(); }
   const T *end() const { return data() + size(); }
   T *end() { return data() + size(); }
 
 private:
   void reallocate(uptr NewCapacity) {
     DCHECK_GT(NewCapacity, 0);
     DCHECK_LE(Size, NewCapacity);
+
+    MemMapT NewExternalBuffer;
     NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached());
-    T *NewData = reinterpret_cast<T *>(
-        map(nullptr, NewCapacity, "scudo:vector", 0, &MapData));
-    memcpy(NewData, Data, Size * sizeof(T));
+    NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector");
+    T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase());
+
+    memcpy(NewExternalData, Data, Size * sizeof(T));
     destroy();
-    Data = NewData;
+
+    Data = NewExternalData;
     CapacityBytes = NewCapacity;
+    ExternalBuffer = NewExternalBuffer;
   }
 
   T *Data = nullptr;
-  T LocalData[256 / sizeof(T)] = {};
   uptr CapacityBytes = 0;
   uptr Size = 0;
-  [[no_unique_address]] MapPlatformData MapData = {};
+
+  T LocalData[256 / sizeof(T)] = {};
+  MemMapT ExternalBuffer;
 };
 
 template <typename T> class Vector : public VectorNoCtor<T> {
 public:
   constexpr Vector() { VectorNoCtor<T>::init(); }
   explicit Vector(uptr Count) {
     VectorNoCtor<T>::init(Count);
     this->resize(Count);