[compiler-rt] Fix memory allocator for dynamic address space

[etienneb]

Summary

The sanitizer allocators can works with a dynamic address space
(i.e. specified with ~0ULL).

Unfortunately, the code was broken on GetMetadata and GetChunkIdx.

The current patch is moving the Win64 memory test to a dynamic
address space. There is a migration to move every concept to a
dynamic address space on windows.

To have a better coverage, the unittest are now testing
dynamic address space on other platforms too.

[rnk]

Kostya, can you review the allocator64 stuff or assign it to someone?

[kcc]

lib/sanitizer_common/sanitizer_allocator_primary64.h

122

Implement a separate function GetRegBeg or something

123

hide this logic inside GetChunkIdx

lib/sanitizer_common/tests/sanitizer_allocator_test.cc

33–36

Please explain why in the comment.

[etienneb]

address kcc comments

[kcc]

LGTM with two nits.
Thanks!

lib/sanitizer_common/sanitizer_allocator_primary64.h

99

this code tends to use reinterpret_cast

lib/sanitizer_common/sanitizer_win.cc

224

do you need two lines here (what will clang-format say?)

[etienneb]

fix nits

[kcc]

LGTM

lib/sanitizer_common/sanitizer_allocator_primary64.h

public:
 
   bool PointerIsMine(const void *p) {
     uptr P = reinterpret_cast<uptr>(p);
     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
       return P / kSpaceSize == kSpaceBeg / kSpaceSize;
     return P >= SpaceBeg() && P < SpaceEnd();
   }
 
+  uptr GetRegionBegin(const void *p) {
+    if (kUsingConstantSpaceBeg)
+      return (uptr)p & ~(kRegionSize - 1);
+    uptr space_beg = SpaceBeg();
+    return (((uptr)p - space_beg) & ~(kRegionSize - 1)) + space_beg;
+  }
+
   uptr GetSizeClass(const void *p) {
     if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0)
       return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded;
     return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) %
            kNumClassesRounded;
   }
 
   void *GetBlockBegin(const void *p) {
     uptr class_id = GetSizeClass(p);
     uptr size = SizeClassMap::Size(class_id);
     if (!size) return nullptr;
     uptr chunk_idx = GetChunkIdx((uptr)p, size);
-    uptr reg_beg = (uptr)p & ~(kRegionSize - 1);
+    uptr reg_beg = GetRegionBegin(p);    
     uptr beg = chunk_idx * size;
     uptr next_beg = beg + size;
     if (class_id >= kNumClasses) return nullptr;
     RegionInfo *region = GetRegionInfo(class_id);
     if (region->mapped_user >= next_beg)
       return reinterpret_cast<void*>(reg_beg + beg);
     return nullptr;
   }
 
   uptr GetActuallyAllocatedSize(void *p) {
     CHECK(PointerIsMine(p));
     return SizeClassMap::Size(GetSizeClass(p));
   }
 
   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
private:
 
   RegionInfo *GetRegionInfo(uptr class_id) {
     CHECK_LT(class_id, kNumClasses);
     RegionInfo *regions =
         reinterpret_cast<RegionInfo *>(SpaceBeg() + kSpaceSize);
     return &regions[class_id];
   }
 
-  static uptr GetChunkIdx(uptr chunk, uptr size) {
+  uptr GetChunkIdx(uptr chunk, uptr size) {
+    if (!kUsingConstantSpaceBeg)
+      chunk -= SpaceBeg();
+
     uptr offset = chunk % kRegionSize;
     // Here we divide by a non-constant. This is costly.
     // size always fits into 32-bits. If the offset fits too, use 32-bit div.
     if (offset >> (SANITIZER_WORDSIZE / 2))
       return offset / size;
     return (u32)offset / (u32)size;
   }
 

lib/sanitizer_common/sanitizer_win.cc

void *MmapFixedNoAccess(uptr fixed_addr, uptr size, const char *name) {
   if (res == 0)
     Report("WARNING: %s failed to "
            "mprotect %p (%zd) bytes at %p (error code: %d)\n",
            SanitizerToolName, size, size, fixed_addr, GetLastError());
   return res;
 }
 
 void *MmapNoAccess(uptr size) {
-  // FIXME: unsupported.
-  return nullptr;
+  void *res = VirtualAlloc(nullptr, size,
+                           MEM_RESERVE, PAGE_NOACCESS);
+  if (res == 0)
+    Report("WARNING: %s failed to "
+           "mprotect %p (%zd) bytes (error code: %d)\n",
+           SanitizerToolName, size, size, GetLastError());
+  return res;
 }
 
 bool MprotectNoAccess(uptr addr, uptr size) {
   DWORD old_protection;
   return VirtualProtect((LPVOID)addr, size, PAGE_NOACCESS, &old_protection);
 }
 
 

lib/sanitizer_common/tests/sanitizer_allocator_test.cc

 #include <vector>
 #include <set>
 
 // Too slow for debug build
 #if !SANITIZER_DEBUG
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 #if SANITIZER_WINDOWS
-static const uptr kAllocatorSpace = 0x10000000000ULL;
+// On Windows 64-bit there is no easy way to find a large enough fixed address
+// space that is always available. Thus, a dynamically allocated address space
+// is used instead (i.e. ~(uptr)0).
+static const uptr kAllocatorSpace = ~(uptr)0;
 static const uptr kAllocatorSize  =  0x10000000000ULL;  // 1T.
 static const u64 kAddressSpaceSize = 1ULL << 40;
 #else
 static const uptr kAllocatorSpace = 0x700000000000ULL;
 static const uptr kAllocatorSize  = 0x010000000000ULL;  // 1T.
 static const u64 kAddressSpaceSize = 1ULL << 47;
 #endif
 
 typedef SizeClassAllocator64<
   kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap> Allocator64;
+typedef SizeClassAllocator64<
+  ~(uptr)0, kAllocatorSize, 16, DefaultSizeClassMap> Allocator64Dynamic;
 
 typedef SizeClassAllocator64<
   kAllocatorSpace, kAllocatorSize, 16, CompactSizeClassMap> Allocator64Compact;
 #elif defined(__mips64)
 static const u64 kAddressSpaceSize = 1ULL << 40;
 #elif defined(__aarch64__)
 static const u64 kAddressSpaceSize = 1ULL << 39;
 #elif defined(__s390x__)
void TestSizeClassAllocator() {
   delete a;
 }
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator64) {
   TestSizeClassAllocator<Allocator64>();
 }
 
+TEST(SanitizerCommon, SizeClassAllocator64Dynamic) {
+  TestSizeClassAllocator<Allocator64Dynamic>();
+}
+
 TEST(SanitizerCommon, SizeClassAllocator64Compact) {
   TestSizeClassAllocator<Allocator64Compact>();
 }
 #endif
 
 TEST(SanitizerCommon, SizeClassAllocator32Compact) {
   TestSizeClassAllocator<Allocator32Compact>();
 }
void SizeClassAllocatorMetadataStress() {
   delete a;
 }
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator64MetadataStress) {
   SizeClassAllocatorMetadataStress<Allocator64>();
 }
 
+TEST(SanitizerCommon, SizeClassAllocator64DynamicMetadataStress) {
+  SizeClassAllocatorMetadataStress<Allocator64Dynamic>();
+}
+
 TEST(SanitizerCommon, SizeClassAllocator64CompactMetadataStress) {
   SizeClassAllocatorMetadataStress<Allocator64Compact>();
 }
 #endif  // SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator32CompactMetadataStress) {
   SizeClassAllocatorMetadataStress<Allocator32Compact>();
 }
 
void SizeClassAllocatorGetBlockBeginStress() {
   a->TestOnlyUnmap();
   delete a;
 }
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator64GetBlockBegin) {
   SizeClassAllocatorGetBlockBeginStress<Allocator64>();
 }
+TEST(SanitizerCommon, SizeClassAllocator64DynamicGetBlockBegin) {
+  SizeClassAllocatorGetBlockBeginStress<Allocator64Dynamic>();
+}
 TEST(SanitizerCommon, SizeClassAllocator64CompactGetBlockBegin) {
   SizeClassAllocatorGetBlockBeginStress<Allocator64Compact>();
 }
 TEST(SanitizerCommon, SizeClassAllocator32CompactGetBlockBegin) {
   SizeClassAllocatorGetBlockBeginStress<Allocator32Compact>();
 }
 #endif  // SANITIZER_CAN_USE_ALLOCATOR64
 

 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, CombinedAllocator64) {
   TestCombinedAllocator<Allocator64,
       LargeMmapAllocator<>,
       SizeClassAllocatorLocalCache<Allocator64> > ();
 }
 
+TEST(SanitizerCommon, CombinedAllocator64Dynamic) {
+  TestCombinedAllocator<Allocator64Dynamic,
+      LargeMmapAllocator<>,
+      SizeClassAllocatorLocalCache<Allocator64Dynamic> > ();
+}
+
 TEST(SanitizerCommon, CombinedAllocator64Compact) {
   TestCombinedAllocator<Allocator64Compact,
       LargeMmapAllocator<>,
       SizeClassAllocatorLocalCache<Allocator64Compact> > ();
 }
 #endif
 
 TEST(SanitizerCommon, CombinedAllocator32Compact) {

 }
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator64LocalCache) {
   TestSizeClassAllocatorLocalCache<
       SizeClassAllocatorLocalCache<Allocator64> >();
 }
 
+TEST(SanitizerCommon, SizeClassAllocator64DynamicLocalCache) {
+  TestSizeClassAllocatorLocalCache<
+      SizeClassAllocatorLocalCache<Allocator64Dynamic> >();
+}
+
 TEST(SanitizerCommon, SizeClassAllocator64CompactLocalCache) {
   TestSizeClassAllocatorLocalCache<
       SizeClassAllocatorLocalCache<Allocator64Compact> >();
 }
 #endif
 
 TEST(SanitizerCommon, SizeClassAllocator32CompactLocalCache) {
   TestSizeClassAllocatorLocalCache<
void TestSizeClassAllocatorIteration() {
   a->TestOnlyUnmap();
   delete a;
 }
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 TEST(SanitizerCommon, SizeClassAllocator64Iteration) {
   TestSizeClassAllocatorIteration<Allocator64>();
 }
+TEST(SanitizerCommon, SizeClassAllocator64DynamicIteration) {
+  TestSizeClassAllocatorIteration<Allocator64Dynamic>();
+}
 #endif
 
 TEST(SanitizerCommon, SizeClassAllocator32Iteration) {
   TestSizeClassAllocatorIteration<Allocator32Compact>();
 }
 
 TEST(SanitizerCommon, LargeMmapAllocatorIteration) {
   LargeMmapAllocator<> a;