[hwasan] Switch to 64 allocator with a dense size class map.

[eugenis]

Summary

Replace the 32-bit allocator with a 64-bit one with a non-constant
base address, and reduce both the number of size classes and the maximum
size of per-thread caches.

As measured on [1], this reduces average weighted memory overhead
(MaxRSS) from 26% to 12% over stock android allocator. These numbers
include overhead from code instrumentation and hwasan shadow (i.e. not a
pure allocator benchmark).

This switch also enables release-to-OS functionality, which is not
implemented in the 32-bit allocator. I have not seen any effect from
that on the benchmark.

[1] https://android.googlesource.com/platform/system/extras/+/master/memory_replay/

[eugenis]

update tests

[eugenis]

compiler-rt/test/hwasan/TestCases/heap-buffer-overflow.c

46

@kcc btw these checks rely on the fact that this allocation is not the first in its size class. This assumption can be broken even w/o llvm/compiler-rt code changes - ex. by a change in libc startup code.

Not sure what to do about this. Maybe we should also describe the chunk that we think is the source of the overflow (that would be an improvement regardless) and test for that.

compiler-rt/lib/hwasan/hwasan_allocator.h

void OnUnmap(uptr p, uptr size) const {
     // We are about to unmap a chunk of user memory.
     // It can return as user-requested mmap() or another thread stack.
     // Make it accessible with zero-tagged pointer.
     TagMemory(p, size, 0);
   }
 };
 
 static const uptr kMaxAllowedMallocSize = 2UL << 30;  // 2G
-static const uptr kRegionSizeLog = 20;
-static const uptr kNumRegions = SANITIZER_MMAP_RANGE_SIZE >> kRegionSizeLog;
-typedef TwoLevelByteMap<(kNumRegions >> 12), 1 << 12> ByteMap;
-
-struct AP32 {
-  static const uptr kSpaceBeg = 0;
-  static const u64 kSpaceSize = SANITIZER_MMAP_RANGE_SIZE;
+
+struct AP64 {
+  static const uptr kSpaceBeg = ~0ULL;
+  static const uptr kSpaceSize = 0x2000000000ULL;
   static const uptr kMetadataSize = sizeof(Metadata);
-  typedef __sanitizer::CompactSizeClassMap SizeClassMap;
-  static const uptr kRegionSizeLog = __hwasan::kRegionSizeLog;
+  typedef __sanitizer::VeryDenseSizeClassMap SizeClassMap;
   using AddressSpaceView = LocalAddressSpaceView;
-  using ByteMap = __hwasan::ByteMap;
   typedef HwasanMapUnmapCallback MapUnmapCallback;
   static const uptr kFlags = 0;
 };
-typedef SizeClassAllocator32<AP32> PrimaryAllocator;
+typedef SizeClassAllocator64<AP64> PrimaryAllocator;
 typedef SizeClassAllocatorLocalCache<PrimaryAllocator> AllocatorCache;
 typedef LargeMmapAllocator<HwasanMapUnmapCallback> SecondaryAllocator;
 typedef CombinedAllocator<PrimaryAllocator, AllocatorCache,
                           SecondaryAllocator> Allocator;
 
-
 void AllocatorSwallowThreadLocalCache(AllocatorCache *cache);
 
 class HwasanChunkView {
  public:
   HwasanChunkView() : block_(0), metadata_(nullptr) {}
   HwasanChunkView(uptr block, Metadata *metadata)
       : block_(block), metadata_(metadata) {}
   bool IsAllocated() const;    // Checks if the memory is currently allocated

compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h

public:
   static_assert(is_same<AddressSpaceView,
                         typename PrimaryAllocator::AddressSpaceView>::value,
                 "PrimaryAllocator is using wrong AddressSpaceView");
   static_assert(is_same<AddressSpaceView,
                         typename SecondaryAllocator::AddressSpaceView>::value,
                 "SecondaryAllocator is using wrong AddressSpaceView");
 
   void InitLinkerInitialized(s32 release_to_os_interval_ms) {
+    stats_.InitLinkerInitialized();
     primary_.Init(release_to_os_interval_ms);
     secondary_.InitLinkerInitialized();
-    stats_.InitLinkerInitialized();
   }
 
   void Init(s32 release_to_os_interval_ms) {
+    stats_.Init();
     primary_.Init(release_to_os_interval_ms);
     secondary_.Init();
-    stats_.Init();
   }
 
   void *Allocate(AllocatorCache *cache, uptr size, uptr alignment) {
     // Returning 0 on malloc(0) may break a lot of code.
     if (size == 0)
       size = 1;
     if (size + alignment < size) {
       Report("WARNING: %s: CombinedAllocator allocation overflow: "

compiler-rt/lib/sanitizer_common/sanitizer_allocator_size_class_map.h

 typedef SizeClassMap<3, 4, 8, 17, 128, 16> DefaultSizeClassMap;
 typedef SizeClassMap<3, 4, 8, 17, 64, 14> CompactSizeClassMap;
 typedef SizeClassMap<2, 5, 9, 16, 64, 14> VeryCompactSizeClassMap;
 
 // The following SizeClassMap only holds a way small number of cached entries,
 // allowing for denser per-class arrays, smaller memory footprint and usually
 // better performances in threaded environments.
 typedef SizeClassMap<3, 4, 8, 17, 8, 10> DenseSizeClassMap;
+// Similar to VeryCompact map above, this one has a small number of different
+// size classes, and also reduced thread-local caches.
+typedef SizeClassMap<2, 5, 9, 16, 8, 10> VeryDenseSizeClassMap;

compiler-rt/test/hwasan/TestCases/heap-buffer-overflow.c

 // CHECK40-RIGHT: allocated heap chunk; size: 32 offset:
 // CHECK40-RIGHT: is located 10 bytes to the right of 30-byte region
 //
 // CHECK80-LEFT: allocated heap chunk; size: 32 offset: 16
 // CHECK80-LEFT: is located 50 bytes to the right of 30-byte region
 // CHECK80-RIGHT: allocated heap chunk; size: 32 offset:
 // CHECK80-RIGHT: is located 50 bytes to the right of 30-byte region
 //
-// CHECKm30: allocated heap chunk; size: 32 offset: 2
 // CHECKm30: is located 30 bytes to the left of 30-byte region
 //
 // CHECKMm30: is a large allocated heap chunk; size: 1003520 offset: -30
 // CHECKMm30: is located 30 bytes to the left of 1000000-byte region
 //
 // CHECKM: is a large allocated heap chunk; size: 1003520 offset: 1000000
 // CHECKM: is located 0 bytes to the right of 1000000-byte region
 //
 // CHECK31: is located 1 bytes to the right of 30-byte region
 //
 // CHECK20-RIGHT8: is located 10 bytes to the right of 20-byte region [0x{{.*}}8,0x{{.*}}c)
 //
 // CHECK-WRONG-FLAG: ERROR: unsupported value of malloc_align_right flag: 42
   free(x);
 }

compiler-rt/test/hwasan/TestCases/use-after-free.c

int main() {
   __hwasan_disable_allocator_tagging();
   fprintf(stderr, "Going to do a %s\n", ISREAD ? "READ" : "WRITE");
   // CHECK: Going to do a [[TYPE:[A-Z]*]]
   int r = 0;
   if (ISREAD) r = x[5]; else x[5] = 42;  // should be on the same line.
   // CHECK: [[TYPE]] of size 1 at {{.*}} tags: [[PTR_TAG:[0-9a-f][0-9a-f]]]/[[MEM_TAG:[0-9a-f][0-9a-f]]] (ptr/mem)
   // CHECK: #0 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-2]]
   // Offset is 5 or 11 depending on left/right alignment.
-  // CHECK: is a small unallocated heap chunk; size: 16 offset: {{5|11}}
+  // CHECK: is a small unallocated heap chunk; size: 32 offset: {{5|11}}
   // CHECK: is located 5 bytes inside of 10-byte region
   //
   // CHECK: freed by thread {{.*}} here:
   // CHECK: #0 {{.*}} in {{.*}}free{{.*}} {{.*}}hwasan_interceptors.cc
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-14]]
 
   // CHECK: previously allocated here:
   // CHECK: #0 {{.*}} in {{.*}}malloc{{.*}} {{.*}}hwasan_interceptors.cc
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-19]]
   // CHECK: Memory tags around the buggy address (one tag corresponds to 16 bytes):
   // CHECK: =>{{.*}}[[MEM_TAG]]
   // CHECK: SUMMARY: HWAddressSanitizer: tag-mismatch {{.*}} in main
   return r;
 }