[scudo][standalone] Fix malloc_iterate

[cryptoad]

Summary

cferris's Bionic tests found an issue in Scudo's malloc_iterate.

We were inclusive of both boundaries, which resulted in a Block that
was located on said boundary to be possibly accounted for twice, or
just being accounted for while iterating on regions that are not ours
(usually the unmapped ones in between Primary regions).

The fix is to exclude the upper boundary in iterateOverChunks, and
add a regression test.

This additionally corrects a typo in a comment, and change the 64-bit
Primary iteration function to not assume that BatchClassId is 0.

[cryptoad]

Update the test.

[hctim]

lib/scudo/standalone/tests/wrappers_c_test.cpp

260

BoundaryP and Counter should be zeroed in the initialisation sequence for this test to make it end-to-end.

265

Nit: std::vector<std::unique_ptr>? to avoid manual cleanup later.

266

From what I see, it looks like the goal of this loop is to (hopefully) get a page-aligned allocation. All the other allocations seem to not be important.

Could this test be simplified by guaranteeing a page-aligned pointer through pvalloc()?

[cryptoad]

lib/scudo/standalone/tests/wrappers_c_test.cpp

260

Ack.

265

Ack.

266

Unfortunately the Block (backend) has to be aligned on a boundary (page is my choice, but it could be anything that matches the iteration), pvaloc would guarantee that the Chunk (frontend) is aligned. Hence the gymnastics with the delta.

[cryptoad]

• Additional comments to the test function
• Moving the initialization of the static variables within the test function

[cryptoad]

Is this good from the reviewers perspective?

[hctim]

lib/scudo/standalone/tests/wrappers_c_test.cpp

266

I see. Is there any way to guarantee that a Block is page-aligned without trial-and-error? If we set SpecialSize = PageSize - BlockDelta, would this guarantee this?

[cryptoad]

lib/scudo/standalone/tests/wrappers_c_test.cpp

266

This is indeed the case if we have a class size of PageSize, then all allocations of PageSize - BlockDelta would end up in it.
It's the case for the default one, I can go with it, and if the SizeClassMap ever changes, add a bailing condition.

[cryptoad]

Following Mitch's suggestion, modify the test to use a
PageSize - BlockDelta sized chunk, that in all likelihood will be
backed by a page-aligned block (dependent on the SizeClassMap but
works with our default).

Double-checked that this was returning a Count of 2 pre-patch, now 1.

[hctim]

LGTM. Thanks :)

lib/scudo/standalone/combined.h

public:
   // within the provided memory range. Said callback must not use this allocator
   // or a deadlock can ensue. This fits Android's malloc_iterate() needs.
   void iterateOverChunks(uptr Base, uptr Size, iterate_callback Callback,
                          void *Arg) {
     initThreadMaybe();
     const uptr From = Base;
     const uptr To = Base + Size;
     auto Lambda = [this, From, To, Callback, Arg](uptr Block) {
-      if (Block < From || Block > To)
+      if (Block < From || Block >= To)
         return;
       uptr ChunkSize;
       const uptr ChunkBase = getChunkFromBlock(Block, &ChunkSize);
       if (ChunkBase != InvalidChunk)
         Callback(ChunkBase, ChunkSize, Arg);
     };
     Primary.iterateOverBlocks(Lambda);
     Secondary.iterateOverBlocks(Lambda);

lib/scudo/standalone/primary64.h

 // they belong to. The Blocks created are shuffled to prevent predictable
 // address patterns (the predictability increases with the size of the Blocks).
 //
 // The 1st Region (for size class 0) holds the TransferBatches. This is a
 // structure used to transfer arrays of available pointers from the class size
 // freelist to the thread specific freelist, and back.
 //
 // The memory used by this allocator is never unmapped, but can be partially
-// released it the platform allows for it.
+// released if the platform allows for it.
 
 template <class SizeClassMapT, uptr RegionSizeLog> class SizeClassAllocator64 {
 public:
   typedef SizeClassMapT SizeClassMap;
   typedef SizeClassAllocator64<SizeClassMap, RegionSizeLog> ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;
 
public:
   }
 
   void enable() {
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--)
       getRegionInfo(static_cast<uptr>(I))->Mutex.unlock();
   }
 
   template <typename F> void iterateOverBlocks(F Callback) const {
-    for (uptr I = 1; I < NumClasses; I++) {
+    for (uptr I = 0; I < NumClasses; I++) {
+      if (I == SizeClassMap::BatchClassId)
+        continue;
       const RegionInfo *Region = getRegionInfo(I);
       const uptr BlockSize = getSizeByClassId(I);
       const uptr From = Region->RegionBeg;
       const uptr To = From + Region->AllocatedUser;
       for (uptr Block = From; Block < To; Block += BlockSize)
         Callback(Block);
     }
   }

lib/scudo/standalone/tests/wrappers_c_test.cpp

 //===-- wrappers_c_test.cpp -------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "platform.h"
 
 #include "gtest/gtest.h"
 
 #include <limits.h>
 #include <malloc.h>
 #include <unistd.h>
 
+extern "C" {
+void malloc_enable(void);
+void malloc_disable(void);
+int malloc_iterate(uintptr_t base, size_t size,
+                   void (*callback)(uintptr_t base, size_t size, void *arg),
+                   void *arg);
+}
+
 // Note that every C allocation function in the test binary will be fulfilled
 // by Scudo (this includes the gtest APIs, etc.), which is a test by itself.
 // But this might also lead to unexpected side-effects, since the allocation and
 // deallocation operations in the TEST functions will coexist with others (see
 // the EXPECT_DEATH comment below).
 
 // We have to use a small quarantine to make sure that our double-free tests
 // trigger. Otherwise EXPECT_DEATH ends up reallocating the chunk that was just
TEST(ScudoWrappersCTest, MallInfo) {
   MI = mallinfo();
   EXPECT_GE(static_cast<size_t>(MI.uordblks), Allocated + BypassQuarantineSize);
   EXPECT_GT(static_cast<size_t>(MI.hblkhd), 0U);
   size_t Free = MI.fordblks;
   free(P);
   MI = mallinfo();
   EXPECT_GE(static_cast<size_t>(MI.fordblks), Free + BypassQuarantineSize);
 }
+
+static uintptr_t BoundaryP = 0U;
+static size_t Counter = 0U;
+
+static void callback(uintptr_t Base, size_t Size, void *Arg) {
+  if (Base == BoundaryP)
+    Counter++;
+}
+
+// Verify that a block located on an iteration boundary is not mis-accounted.
+TEST(ScudoWrappersCTest, MallocIterateBoundary) {
+  const size_t BlockDelta = FIRST_32_SECOND_64(8U, 16U);
+  const size_t SpecialSize = 128U - BlockDelta;
+  const size_t PageSize = sysconf(_SC_PAGESIZE);
+
+  std::vector<void *> V;
+  while (V.size() < 512U) {
+    void *P = malloc(SpecialSize);
+    EXPECT_NE(P, nullptr);
+    V.push_back(P);
+    const uintptr_t Block = reinterpret_cast<uintptr_t>(P) - BlockDelta;
+    if ((Block & (PageSize - 1)) == 0) {
+      BoundaryP = reinterpret_cast<uintptr_t>(P);
+      break;
+    }
+  }
+  EXPECT_NE(BoundaryP, 0U);
+
+  const uintptr_t Boundary = BoundaryP - BlockDelta;
+  malloc_disable();
+  malloc_iterate(Boundary - PageSize, PageSize, callback, nullptr);
+  malloc_iterate(Boundary, PageSize, callback, nullptr);
+  malloc_enable();
+  EXPECT_EQ(Counter, 1U);
+
+  while (!V.empty()) {
+    free(V.back());
+    V.pop_back();
+  }
+}