[scudo] Rework Vector/String

[cryptoad]

Summary

Some platforms (eg: Trusty) are extremelly memory constrained, which
doesn't necessarily work well with some of Scudo's current assumptions.

Vector by default (and as such String and ScopedString) maps a
page, which is a bit of a waste. This CL changes Vector to use a
buffer local to the class first, then potentially map more memory if
needed (ScopedString currently are all stack based so it would be
stack data). We also want to allow a platform to prevent any dynamic
resizing, so I added a CanGrow templated parameter that for now is
always true but would be set to false on Trusty.

[cryptoad]

Correcting a couple of ScopedString constructors.

[cryptoad]

Corrected, with a test now.

[hctim]

CanGrow templated parameter that for now is
always true but would be set to false on Trusty.

Are we seeing OOMs on Trusty due to ScopedString? I had a quick look and it seemed like there's no non-ephemeral buffers (and really, this shouldn't be called very often at all), and it concerns me a little that push_back can silently fail on a ScopedErrorReport and truncate the text and it seems hard to test "all failure conditions log successfully".

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

22

With InitialSize == 0, isn't this OOB?

[vitalybuka]

Local buffer is LGTM, but CantGrow looks like unrelated change and a good candidate for a separate patch.

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

21

Interface will be cleaner without InitialSize, we removed it sanitizer_common some time ago.

maybe for a separate patch:
uptr length() const { return buffer_.size() - 1; } can retire Length

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

20

As is seems all users of VectorNoCtor will need to re-think consequences of failed push_back.
Interface mimics std::vector, but it's unexpected that after N push_back() container may be smaller than N.

Maybe we can we rather set max grow size for Trusty and crash if it's reached. Which also a problem, but at least easy to detect.

another alternative is to assume that Trusty will can handle Grow in most cases and when it cant, we can handle that explicitly on caller side by checking container size before push_back

[cryptoad]

In D103641#2797247, @hctim wrote:

CanGrow templated parameter that for now is
always true but would be set to false on Trusty.

Are we seeing OOMs on Trusty due to ScopedString? I had a quick look and it seemed like there's no non-ephemeral buffers (and really, this shouldn't be called very often at all), and it concerns me a little that push_back can silently fail on a ScopedErrorReport and truncate the text and it seems hard to test "all failure conditions log successfully".

Some Trusty apps have a heap of 1 page (yup), and all maps end up in the sbrk space. So in it's current shape, a ScopedString is taking way too much space in the heap.
push_back is only used in tests so far, formatString failing might be a little more problematic. I think there will be some truncation for larger strings, but more of the simple ones will go through, and that's probably the price to pay when you have such a small heap.

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

22

Well we always have at least the local buffer worth of space, so it won't OOB, but I see how this isn't obvious.
I am going to add a check.

[hctim]

Some Trusty apps have a heap of 1 page (yup),

Wow!

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

22

Yeah, logical bug. But if I'm reading correctly, it should currently trip the DCHECK :).

[cryptoad]

Based on feedback, remove for now the CanGrow aspect of the vector.

[cryptoad]

Remove stray comment.

[cryptoad]

Remove InitialSize as suggested.

[cryptoad]

and I forgot to copy over the test file.

[hctim]

LGTM w/ nits.

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

27

why /s/int/uptr? I mean, okay to keep the change, but if so also change the type of the Vector

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

104

Is stack size a problem?

If so, we could typedef this (template <typename T, int StackBufferBytes = 256> class VectorNoCtor) and in places where we know the upper bound, we can bound the stack buffer size as well.

[cryptoad]

Change type in vector test.

[cryptoad]

Switching 2 lines around.

[cryptoad]

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

104

Apparently stack is 1 page as well. 256 should be fine, but I will revisit with CanGrow as well.

[kda]

This looks like it broke the sanitizer-x86_64-linux-qemu.
https://lab.llvm.org/buildbot/#/builders/169/builds/501

[cryptoad]

In D103641#2799782, @kda wrote:

This looks like it broke the sanitizer-x86_64-linux-qemu.
https://lab.llvm.org/buildbot/#/builders/169/builds/501

Found the issue, testing the fix.

[cryptoad]

In D103641#2799871, @cryptoad wrote:

In D103641#2799782, @kda wrote:

This looks like it broke the sanitizer-x86_64-linux-qemu.
https://lab.llvm.org/buildbot/#/builders/169/builds/501

Found the issue, testing the fix.

Should be fixed with https://reviews.llvm.org/D103716

[kda]

thank you!

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

#endif
   }
 
   // The function returns the amount of bytes required to store the statistics,
   // which might be larger than the amount of bytes provided. Note that the
   // statistics buffer is not necessarily constant between calls to this
   // function. This can be called with a null buffer or zero size for buffer
   // sizing purposes.
   uptr getStats(char *Buffer, uptr Size) {
-    ScopedString Str(1024);
+    ScopedString Str;
     disable();
     const uptr Length = getStats(&Str) + 1;
     enable();
     if (Length < Size)
       Size = Length;
     if (Buffer && Size) {
       memcpy(Buffer, Str.data(), Size);
       Buffer[Size - 1] = '\0';
     }
     return Length;
   }
 
   void printStats() {
-    ScopedString Str(1024);
+    ScopedString Str;
     disable();
     getStats(&Str);
     enable();
     Str.output();
   }
 
   void releaseToOS() {
     initThreadMaybe();

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

NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
     if (TotalUserBytes > MappedUser) {
       // Do the mmap for the user memory.
       const uptr MapSize =
           roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement);
       const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
       if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) {
         if (!Region->Exhausted) {
           Region->Exhausted = true;
-          ScopedString Str(1024);
+          ScopedString Str;
           getStats(&Str);
           Str.append(
               "Scudo OOM: The process has exhausted %zuM for size class %zu.\n",
               RegionSize >> 20, Size);
           Str.output();
         }
         return nullptr;
       }

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

#else
   static const uptr MaxBytesCachedLog = 10;
   static const uptr SizeDelta = Chunk::getHeaderSize();
 #endif
 };
 
 typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap;
 
 template <typename SCMap> inline void printMap() {
-  ScopedString Buffer(1024);
+  ScopedString Buffer;
   uptr PrevS = 0;
   uptr TotalCached = 0;
   for (uptr I = 0; I < SCMap::NumClasses; I++) {
     if (I == SCMap::BatchClassId)
       continue;
     const uptr S = SCMap::getSizeByClassId(I);
     const uptr D = S - PrevS;
     const uptr P = PrevS ? (D * 100 / PrevS) : 0;

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

 #include "vector.h"
 
 #include <stdarg.h>
 
 namespace scudo {
 
 class ScopedString {
 public:
-  explicit ScopedString(uptr MaxLength) : String(MaxLength), Length(0) {
+  explicit ScopedString(uptr InitialSize = 0) : String(InitialSize) {
     String[0] = '\0';
   }
   uptr length() { return Length; }
   const char *data() { return String.data(); }
   void clear() {
     String[0] = '\0';
     Length = 0;
   }
   void append(const char *Format, va_list Args);
   void append(const char *Format, ...);
   void output() const { outputRaw(String.data()); }
 
 private:
   Vector<char> String;
-  uptr Length;
+  uptr Length = 0;
 };
 
 int formatString(char *Buffer, uptr BufferLength, const char *Format, ...);
 void Printf(const char *Format, ...);
 
 } // namespace scudo
 
 #endif // SCUDO_STRING_UTILS_H_

compiler-rt/lib/scudo/standalone/string_utils.cpp

int formatString(char *Buffer, uptr BufferLength, const char *Format, ...) {
   va_list Args;
   va_start(Args, Format);
   int Res = formatString(Buffer, BufferLength, Format, Args);
   va_end(Args);
   return Res;
 }
 
 void ScopedString::append(const char *Format, va_list Args) {
-  DCHECK_LT(Length, String.size());
+  RAW_CHECK(Length <= String.size());
   va_list ArgsCopy;
   va_copy(ArgsCopy, Args);
   // formatString doesn't currently support a null buffer or zero buffer length,
   // so in order to get the resulting formatted string length, we use a one-char
   // buffer.
   char C[1];
   const uptr AdditionalLength =
       static_cast<uptr>(formatString(C, sizeof(C), Format, Args)) + 1;
-  String.resize(Length + AdditionalLength);
+  // append will silently fail if the underlying Vector can't grow.
+  if (String.resize(Length + AdditionalLength)) {
     formatString(String.data() + Length, AdditionalLength, Format, ArgsCopy);
-  va_end(ArgsCopy);
     Length = strlen(String.data());
-  CHECK_LT(Length, String.size());
+    RAW_CHECK(Length < String.size());
+  }
+  va_end(ArgsCopy);
 }
 
 FORMAT(2, 3)
 void ScopedString::append(const char *Format, ...) {
   va_list Args;
   va_start(Args, Format);
   append(Format, Args);
   va_end(Args);
 }
 
 FORMAT(1, 2)
 void Printf(const char *Format, ...) {
   va_list Args;
   va_start(Args, Format);
-  ScopedString Msg(1024);
+  ScopedString Msg;
   Msg.append(Format, Args);
   outputRaw(Msg.data());
   va_end(Args);
 }
 
 } // namespace scudo

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

for (scudo::uptr J = 0; J < NumberOfAllocations; J++) {
       memset(P, 'B', Size);
       Pointers[J] = P;
     }
     for (scudo::uptr J = 0; J < NumberOfAllocations; J++)
       Cache.deallocate(ClassId, Pointers[J]);
   }
   Cache.destroy(nullptr);
   Allocator->releaseToOS();
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Allocator->getStats(&Str);
   Str.output();
 }
 
 struct SmallRegionsConfig {
   using SizeClassMap = scudo::DefaultSizeClassMap;
   static const scudo::uptr PrimaryRegionSizeLog = 20U;
   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
for (scudo::uptr I = 0; I < 10000U; I++) {
     Batches.push_back(B);
   }
   while (!Batches.empty()) {
     Allocator.pushBatch(ClassId, Batches.back());
     Batches.pop_back();
   }
   Cache.destroy(nullptr);
   Allocator.releaseToOS();
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Allocator.getStats(&Str);
   Str.output();
   EXPECT_EQ(AllocationFailed, true);
   Allocator.unmapTestOnly();
 }
 
 SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryIterate) {
   using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryIterate) {
   EXPECT_EQ(Found, V.size());
   while (!V.empty()) {
     auto Pair = V.back();
     Cache.deallocate(Pair.first, Pair.second);
     V.pop_back();
   }
   Cache.destroy(nullptr);
   Allocator->releaseToOS();
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Allocator->getStats(&Str);
   Str.output();
 }
 
 SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryThreaded) {
   using Primary = TestAllocator<TypeParam, scudo::SvelteSizeClassMap>;
   std::unique_ptr<Primary> Allocator(new Primary);
   Allocator->init(/*ReleaseToOsInterval=*/-1);
SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryThreaded) {
   {
     std::unique_lock<std::mutex> Lock(Mutex);
     Ready = true;
     Cv.notify_all();
   }
   for (auto &T : Threads)
     T.join();
   Allocator->releaseToOS();
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Allocator->getStats(&Str);
   Str.output();
 }
 
 // Through a simple allocation that spans two pages, verify that releaseToOS
 // actually releases some bytes (at least one page worth). This is a regression
 // test for an error in how the release criteria were computed.
 SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {

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

if (!DrainOccurred && Cache.getSize() < CacheSize)
       DrainOccurred = true;
     CacheSize = Cache.getSize();
   }
   EXPECT_TRUE(DrainOccurred);
 
   Quarantine.drainAndRecycle(&Cache, Cb);
   EXPECT_EQ(Cache.getSize(), 0UL);
 
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Quarantine.getStats(&Str);
   Str.output();
 }
 
 struct PopulateQuarantineThread {
   pthread_t Thread;
   QuarantineT *Quarantine;
   CacheT Cache;
TEST(ScudoQuarantineTest, ThreadedGlobalQuarantine) {
   PopulateQuarantineThread T[NumberOfThreads];
   for (scudo::uptr I = 0; I < NumberOfThreads; I++) {
     T[I].Quarantine = &Quarantine;
     pthread_create(&T[I].Thread, 0, populateQuarantine, &T[I]);
   }
   for (scudo::uptr I = 0; I < NumberOfThreads; I++)
     pthread_join(T[I].Thread, 0);
 
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   Quarantine.getStats(&Str);
   Str.output();
 
   for (scudo::uptr I = 0; I < NumberOfThreads; I++)
     Quarantine.drainAndRecycle(&T[I].Cache, Cb);
 }

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

template <typename Config> static void testSecondaryBasic(void) {
   std::vector<void *> V;
   for (scudo::uptr I = 0; I < 32U; I++)
     V.push_back(L->allocate(scudo::Options{}, Size));
   std::shuffle(V.begin(), V.end(), std::mt19937(std::random_device()()));
   while (!V.empty()) {
     L->deallocate(scudo::Options{}, V.back());
     V.pop_back();
   }
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   L->getStats(&Str);
   Str.output();
   L->unmapTestOnly();
 }
 
 struct NoCacheConfig {
   typedef scudo::MapAllocatorNoCache SecondaryCache;
   static const bool MaySupportMemoryTagging = false;
for (scudo::uptr AlignLog = FIRST_32_SECOND_64(3, 4); AlignLog <= 16;
         EXPECT_NE(P, nullptr);
         void *AlignedP = reinterpret_cast<void *>(
             scudo::roundUpTo(reinterpret_cast<scudo::uptr>(P), Align));
         memset(AlignedP, 0xff, UserSize);
         L->deallocate(scudo::Options{}, P);
       }
     }
   }
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   L->getStats(&Str);
   Str.output();
   L->unmapTestOnly();
 }
 
 TEST(ScudoSecondaryTest, SecondaryIterate) {
   std::unique_ptr<LargeAllocator> L(new LargeAllocator);
   L->init(nullptr);
   std::vector<void *> V;
   const scudo::uptr PageSize = scudo::getPageSizeCached();
   for (scudo::uptr I = 0; I < 32U; I++)
     V.push_back(L->allocate(scudo::Options{}, (std::rand() % 16) * PageSize));
   auto Lambda = [V](scudo::uptr Block) {
     EXPECT_NE(std::find(V.begin(), V.end(), reinterpret_cast<void *>(Block)),
               V.end());
   };
   L->disable();
   L->iterateOverBlocks(Lambda);
   L->enable();
   while (!V.empty()) {
     L->deallocate(scudo::Options{}, V.back());
     V.pop_back();
   }
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   L->getStats(&Str);
   Str.output();
   L->unmapTestOnly();
 }
 
 TEST(ScudoSecondaryTest, SecondaryOptions) {
   std::unique_ptr<LargeAllocator> L(new LargeAllocator);
   L->init(nullptr);
for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++)
     Threads[I] = std::thread(performAllocations, L.get());
   {
     std::unique_lock<std::mutex> Lock(Mutex);
     Ready = true;
     Cv.notify_all();
   }
   for (auto &T : Threads)
     T.join();
-  scudo::ScopedString Str(1024);
+  scudo::ScopedString Str;
   L->getStats(&Str);
   Str.output();
   L->unmapTestOnly();
 }

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

TEST(ScudoVectorTest, Basic) {
   V.push_back(43);
   EXPECT_EQ(V.size(), 2U);
   EXPECT_EQ(V[0], 42);
   EXPECT_EQ(V[1], 43);
 }
 
 TEST(ScudoVectorTest, Stride) {
   scudo::Vector<int> V;
-  for (int i = 0; i < 1000; i++) {
-    V.push_back(i);
-    EXPECT_EQ(V.size(), i + 1U);
-    EXPECT_EQ(V[i], i);
+  for (scudo::uptr I = 0; I < 1000; I++) {
+    V.push_back(I);
+    EXPECT_EQ(V.size(), I + 1U);
+    EXPECT_EQ(V[I], I);
   }
-  for (int i = 0; i < 1000; i++)
-    EXPECT_EQ(V[i], i);
+  for (scudo::uptr I = 0; I < 1000; 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);
 }
+
+TEST(ScudoVectorTest, CantGrow) {
+  scudo::Vector<int, false> V;
+  scudo::uptr Capacity = V.capacity();
+  for (scudo::uptr I = 0; I < Capacity; I++)
+    V.push_back(0);
+  EXPECT_EQ(V.size(), Capacity);
+  // push_back silently fails when the Vector is at capacity.
+  V.push_back(0);
+  EXPECT_EQ(V.size(), Capacity);
+}

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

 #include "common.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.
-template <typename T> class VectorNoCtor {
+template <typename T, bool CanGrow> class VectorNoCtor {
 public:
-  void init(uptr InitialCapacity) {
-    CapacityBytes = 0;
-    Size = 0;
-    Data = nullptr;
+  void init(uptr InitialCapacity = 0) {
+    Data = reinterpret_cast<T *>(&LocalData[0]);
+    CapacityBytes = sizeof(LocalData);
     reserve(InitialCapacity);
   }
   void destroy() {
-    if (Data)
+    if (Data != reinterpret_cast<T *>(&LocalData[0]))
       unmap(Data, CapacityBytes);
   }
   T &operator[](uptr I) {
     DCHECK_LT(I, Size);
     return Data[I];
   }
   const T &operator[](uptr I) const {
     DCHECK_LT(I, Size);
     return Data[I];
   }
   void push_back(const T &Element) {
     DCHECK_LE(Size, capacity());
     if (Size == capacity()) {
+      // For now, push_back will silently fail if the Vector can't grow.
+      if (!CanGrow)
+        return;
       const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1);
       reallocate(NewCapacity);
     }
     memcpy(&Data[Size++], &Element, sizeof(T));
   }
   T &back() {
     DCHECK_GT(Size, 0);
     return Data[Size - 1];
   }
   void pop_back() {
     DCHECK_GT(Size, 0);
     Size--;
   }
   uptr size() const { return Size; }
   const T *data() const { return Data; }
   T *data() { return Data; }
   uptr capacity() const { return CapacityBytes / sizeof(T); }
-  void reserve(uptr NewSize) {
+  bool reserve(uptr NewSize) {
     // Never downsize internal buffer.
-    if (NewSize > capacity())
+    if (NewSize > capacity()) {
+      if (!CanGrow)
+        return false;
       reallocate(NewSize);
     }
-  void resize(uptr NewSize) {
+    return true;
+  }
+  bool resize(uptr NewSize) {
     if (NewSize > Size) {
-      reserve(NewSize);
+      if (!reserve(NewSize))
+        return false;
       memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
     }
     Size = NewSize;
+    return true;
   }
 
   void clear() { Size = 0; }
   bool empty() const { return size() == 0; }
 
   const T *begin() const { return data(); }
   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);
-    const uptr NewCapacityBytes =
-        roundUpTo(NewCapacity * sizeof(T), getPageSizeCached());
+    NewCapacity = roundUpTo(NewCapacity * sizeof(T), getPageSizeCached());
     T *NewData =
-        reinterpret_cast<T *>(map(nullptr, NewCapacityBytes, "scudo:vector"));
-    if (Data) {
-      memcpy(NewData, Data, Size * sizeof(T));
+        reinterpret_cast<T *>(map(nullptr, NewCapacity, "scudo:vector"));
+    if (Data != reinterpret_cast<T *>(&LocalData[0]))
       unmap(Data, CapacityBytes);
-    }
     Data = NewData;
-    CapacityBytes = NewCapacityBytes;
+    CapacityBytes = NewCapacity;
   }
 
-  T *Data;
-  uptr CapacityBytes;
-  uptr Size;
+  T *Data = nullptr;
+  u8 LocalData[256] = {};
+  uptr CapacityBytes = 0;
+  uptr Size = 0;
 };
 
-template <typename T> class Vector : public VectorNoCtor<T> {
+template <typename T, bool CanGrow = true>
+class Vector : public VectorNoCtor<T, CanGrow> {
 public:
-  Vector() { VectorNoCtor<T>::init(1); }
+  Vector() { VectorNoCtor<T, CanGrow>::init(); }
   explicit Vector(uptr Count) {
-    VectorNoCtor<T>::init(Count);
+    VectorNoCtor<T, CanGrow>::init(Count);
     this->resize(Count);
   }
-  ~Vector() { VectorNoCtor<T>::destroy(); }
+  ~Vector() { VectorNoCtor<T, CanGrow>::destroy(); }
   // Disallow copies and moves.
   Vector(const Vector &) = delete;
   Vector &operator=(const Vector &) = delete;
   Vector(Vector &&) = delete;
   Vector &operator=(Vector &&) = delete;
 };
 
 } // namespace scudo
 
 #endif // SCUDO_VECTOR_H_