[sanitizer] Align & pad the allocator structures to the cacheline size

[cryptoad]

Summary

Both SizeClassInfo structures for the 32-bit primary & RegionInfo
structures for the 64-bit primary can be used by different threads, and as such
they should be aligned & padded to the cacheline size to avoid false sharing.
The former was padded but the array was not aligned, the latter was not padded
but we lucked up as the size of the structure was 192 bytes, and aligned by
the properties of mmap.

I plan on adding a couple of fields to the RegionInfo, and some highly
threaded tests pointed out that without proper padding & alignment, performance
was getting a hit - and it is going away with proper padding.

This patch makes sure that we are properly padded & aligned for both. I used
a template to avoid padding if the size is already a multiple of the cacheline
size. There might be a better way to do this, I am open to suggestions.

[alekseyshl]

I think just declaring "struct ALIGNED(kCacheLineSize) ..." is enough. Compiler should take take care of the rest, the structure size will be extended to the multiple of the alignment, the array will be aligned appropriately, right?

[cryptoad]

In D44261#1031736, @alekseyshl wrote:

I think just declaring "struct ALIGNED(kCacheLineSize) ..." is enough. Compiler should take take care of the rest, the structure size will be extended to the multiple of the alignment, the array will be aligned appropriately, right?

So this would work with C++11's alignas but not with __attribute__((align())). Currently alignas is only used in LibFuzzer & XRay, I am not sure what the stance is about bringing it to sanitizer_common.

[cryptoad]

In D44261#1031779, @cryptoad wrote:

In D44261#1031736, @alekseyshl wrote:

I think just declaring "struct ALIGNED(kCacheLineSize) ..." is enough. Compiler should take take care of the rest, the structure size will be extended to the multiple of the alignment, the array will be aligned appropriately, right?

So this would work with C++11's alignas but not with __attribute__((align())). Currently alignas is only used in LibFuzzer & XRay, I am not sure what the stance is about bringing it to sanitizer_common.

Nevermind, this seems to work!

[cryptoad]

Using @alekseyshl's much simpler solution.
Added a couple of DCHECKs for good measure.
Also forgotten in the initial description: I changed 2 CHECKs to DCHECKs
as they are either called from functions that perform the CHECK or from for
loops that bound the value properly.

[alekseyshl]

lib/sanitizer_common/sanitizer_allocator_primary32.h

274–275

In other places we do "struct ALIGNED(N) TypeName { ...". Why after the struct body here?

369–370

The alignment of an array is the alignment of its elements, no need to specify it here.

[cryptoad]

Addressing 1 comment.

[cryptoad]

Addressing the other comment.

[thakis]

compiler-rt/trunk/lib/sanitizer_common/sanitizer_allocator_primary32.h

269 ↗

(On Diff #137758)

This doesn't build on our bots: https://logs.chromium.org/v/?s=chromium%2Fbb%2Fchromium.clang%2FToTLinux%2F1811%2F%2B%2Frecipes%2Fsteps%2Fgclient_runhooks%2F0%2Fstdout

FAILED: lib/sanitizer_common/CMakeFiles/RTSanitizerCommon.i386.dir/sanitizer_allocator.cc.o
/b/c/b/ToTLinux/src/third_party/llvm-build-tools/gcc485precise/bin/g++ -DHAVE_RPC_XDR_H=0 -DHAVE_TIRPC_RPC_XDR_H=0 -I/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/.. -DLLVM_FORCE_HEAD_REVISION -Wall -std=c++11 -Wno-unused-parameter -O3 -DNDEBUG -DLLVM_FORCE_HEAD_REVISION -Wall -std=c++11 -Wno-unused-parameter -m32 -fPIC -fno-builtin -fno-exceptions -fomit-frame-pointer -funwind-tables -fno-stack-protector -fvisibility=hidden -fno-lto -O3 -g -Wno-variadic-macros -Wno-non-virtual-dtor -fno-rtti -Wframe-larger-than=570 -MMD -MT lib/sanitizer_common/CMakeFiles/RTSanitizerCommon.i386.dir/sanitizer_allocator.cc.o -MF lib/sanitizer_common/CMakeFiles/RTSanitizerCommon.i386.dir/sanitizer_allocator.cc.o.d -o lib/sanitizer_common/CMakeFiles/RTSanitizerCommon.i386.dir/sanitizer_allocator.cc.o -c /b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc
In file included from /b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h:76:0,

from /b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:15:

/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h: In instantiation of ‘struct sanitizer::SizeClassAllocator32<sanitizer::AP32>::SizeClassInfo’:
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h:274:3: required from ‘class sanitizer::SizeClassAllocator32<sanitizer::AP32>’
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h:193:20: required from ‘class sanitizer::CombinedAllocator<sanitizer::SizeClassAllocator32<sanitizer::AP32>, sanitizer::SizeClassAllocatorLocalCache<sanitizer::SizeClassAllocator32<sanitizer::AP32> >, sanitizer::LargeMmapAllocator<sanitizer::NoOpMapUnmapCallback, __sanitizer::LargeMmapAllocatorPtrArrayStatic> >’
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:84:76: required from here
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h:269:34: error: requested alignment is not an integer constant

struct ALIGNED(kCacheLineSize) SizeClassInfo {
                               ^

In file included from /b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h:17:0,

from /b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:15:

/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h: In instantiation of ‘class sanitizer::SizeClassAllocator32<sanitizer::AP32>’:
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h:193:20: required from ‘class sanitizer::CombinedAllocator<sanitizer::SizeClassAllocator32<sanitizer::AP32>, sanitizer::SizeClassAllocatorLocalCache<sanitizer::SizeClassAllocator32<sanitizer::AP32> >, sanitizer::LargeMmapAllocator<sanitizer::NoOpMapUnmapCallback, __sanitizer::LargeMmapAllocatorPtrArrayStatic> >’
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:84:76: required from here
/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h:330:72: error: size of array is negative

typedef char IMPL_PASTE(assertion_failed_##_, line)[2*(int)(pred)-1]
                                                                   ^

/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_internal_defs.h:324:30: note: in expansion of macro ‘IMPL_COMPILER_ASSERT’
#define COMPILER_CHECK(pred) IMPL_COMPILER_ASSERT(pred, LINE)

^

/b/c/b/ToTLinux/src/third_party/llvm/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h:274:3: note: in expansion of macro ‘COMPILER_CHECK’

COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);

lib/sanitizer_common/sanitizer_allocator_primary32.h

  private:
   static const uptr kRegionSize = 1 << kRegionSizeLog;
   static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
 
   struct SizeClassInfo {
     SpinMutex mutex;
     IntrusiveList<TransferBatch> free_list;
     u32 rand_state;
-    char padding[kCacheLineSize - 2 * sizeof(uptr) -
-                 sizeof(IntrusiveList<TransferBatch>)];
   };
-  COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize);
+  typedef padded_t<SizeClassInfo> PaddedSizeClassInfo;
+  COMPILER_CHECK(sizeof(PaddedSizeClassInfo) % kCacheLineSize == 0);
 
   uptr ComputeRegionId(uptr mem) {
     const uptr res = mem >> kRegionSizeLog;
     CHECK_LT(res, kNumPossibleRegions);
     return res;
   }
 
   uptr ComputeRegionBeg(uptr mem) {
uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
     MapUnmapCallback().OnMap(res, kRegionSize);
     stat->Add(AllocatorStatMapped, kRegionSize);
     CHECK(IsAligned(res, kRegionSize));
     possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
     return res;
   }
 
   SizeClassInfo *GetSizeClassInfo(uptr class_id) {
-    CHECK_LT(class_id, kNumClasses);
-    return &size_class_info_array[class_id];
+    DCHECK_LT(class_id, kNumClasses);
+    return &size_class_info_array[class_id].object;
   }
 
   bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
                        TransferBatch **current_batch, uptr max_count,
                        uptr *pointers_array, uptr count) {
     // If using a separate class for batches, we do not need to shuffle it.
     if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
         class_id != SizeClassMap::kBatchClassID))
bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
     if (b) {
       CHECK_GT(b->Count(), 0);
       sci->free_list.push_back(b);
     }
     return true;
   }
 
   ByteMap possible_regions;
-  SizeClassInfo size_class_info_array[kNumClasses];
+  ALIGNED(kCacheLineSize)
+  PaddedSizeClassInfo size_class_info_array[kNumClasses];
 };

lib/sanitizer_common/sanitizer_allocator_primary64.h

void ForEachChunk(ForEachChunkCallback callback, void *arg) {
     }
   }
 
   static uptr ClassIdToSize(uptr class_id) {
     return SizeClassMap::Size(class_id);
   }
 
   static uptr AdditionalSize() {
-    return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded,
+    return RoundUpTo(sizeof(PaddedRegionInfo) * kNumClassesRounded,
                      GetPageSizeCached());
   }
 
   typedef SizeClassMap SizeClassMapT;
   static const uptr kNumClasses = SizeClassMap::kNumClasses;
   static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
 
   // A packed array of counters. Each counter occupies 2^n bits, enough to store
struct RegionInfo {
     uptr allocated_meta;  // Bytes allocated for metadata.
     uptr mapped_user;  // Bytes mapped for user memory.
     uptr mapped_meta;  // Bytes mapped for metadata.
     u32 rand_state;  // Seed for random shuffle, used if kRandomShuffleChunks.
     bool exhausted;  // Whether region is out of space for new chunks.
     Stats stats;
     ReleaseToOsInfo rtoi;
   };
-  COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize);
+  typedef padded_t<RegionInfo> PaddedRegionInfo;
+  COMPILER_CHECK(sizeof(PaddedRegionInfo) % kCacheLineSize == 0);
 
   RegionInfo *GetRegionInfo(uptr class_id) const {
-    CHECK_LT(class_id, kNumClasses);
-    RegionInfo *regions =
-        reinterpret_cast<RegionInfo *>(SpaceBeg() + kSpaceSize);
-    return &regions[class_id];
+    DCHECK_LT(class_id, kNumClasses);
+    PaddedRegionInfo *regions =
+        reinterpret_cast<PaddedRegionInfo *>(SpaceBeg() + kSpaceSize);
+    return &regions[class_id].object;
   }
 
   uptr GetMetadataEnd(uptr region_beg) const {
     return region_beg + kRegionSize - kFreeArraySize;
   }
 
   uptr GetChunkIdx(uptr chunk, uptr size) const {
     if (!kUsingConstantSpaceBeg)

lib/sanitizer_common/sanitizer_common.h

 struct SignalContext;
 struct StackTrace;
 
 // Constants.
 const uptr kWordSize = SANITIZER_WORDSIZE / 8;
 const uptr kWordSizeInBits = 8 * kWordSize;
 
 #if defined(__powerpc__) || defined(__powerpc64__)
-  const uptr kCacheLineSize = 128;
+  constexpr uptr kCacheLineSize = 128;
 #else
-  const uptr kCacheLineSize = 64;
+  constexpr uptr kCacheLineSize = 64;
 #endif
 
+constexpr uptr CacheLinePad(uptr object_size) {
+  return ((object_size / kCacheLineSize) * kCacheLineSize) +
+      (((object_size % kCacheLineSize) != 0) * kCacheLineSize) -
+      object_size;
+}
+
+template<class T, bool = false>
+struct padded {
+  using type = struct {
+    ALIGNED(kCacheLineSize) T object;
+    char pad_[CacheLinePad(sizeof(T))];
+  };
+};
+
+template<class T>
+struct padded<T, true> {
+  using type = struct {
+    ALIGNED(kCacheLineSize) T object;
+  };
+};
+
+template<class T>
+using padded_t = typename padded<T, (sizeof(T) % kCacheLineSize == 0)>::type;
+
 const uptr kMaxPathLength = 4096;
 
 const uptr kMaxThreadStackSize = 1 << 30;  // 1Gb
 
 static const uptr kErrorMessageBufferSize = 1 << 16;
 
 // Denotes fake PC values that come from JIT/JAVA/etc.
 // For such PC values __tsan_symbolize_external() will be called.