8 files changed, 40 insertions, 0 deletions
diff --git a/lib/asan/asan_allocator.h b/lib/asan/asan_allocator.h
index 407639fe1..625e6edfd 100644
--- a/lib/asan/asan_allocator.h
+++ b/lib/asan/asan_allocator.h
@@ -135,6 +135,7 @@ struct AP64 {  // Allocator64 parameters. Deliberately using a short name.
   static const uptr kMetadataSize = 0;
   typedef __asan::SizeClassMap SizeClassMap;
   typedef AsanMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 typedef SizeClassAllocator64<AP64> PrimaryAllocator;
diff --git a/lib/lsan/lsan_allocator.cc b/lib/lsan/lsan_allocator.cc
index 094ebe19f..915e99d4b 100644
--- a/lib/lsan/lsan_allocator.cc
+++ b/lib/lsan/lsan_allocator.cc
@@ -50,6 +50,7 @@ struct AP64 {  // Allocator64 parameters. Deliberately using a short name.
   static const uptr kMetadataSize = sizeof(ChunkMetadata);
   typedef DefaultSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 typedef SizeClassAllocator64<AP64> PrimaryAllocator;
diff --git a/lib/msan/msan_allocator.cc b/lib/msan/msan_allocator.cc
index 3d57fba2d..9eb945af5 100644
--- a/lib/msan/msan_allocator.cc
+++ b/lib/msan/msan_allocator.cc
@@ -64,6 +64,7 @@ struct MsanMapUnmapCallback {
     static const uptr kMetadataSize = sizeof(Metadata);
     typedef DefaultSizeClassMap SizeClassMap;
     typedef MsanMapUnmapCallback MapUnmapCallback;
+    static const uptr kFlags = 0;
   };
 
   typedef SizeClassAllocator64<AP64> PrimaryAllocator;
diff --git a/lib/sanitizer_common/sanitizer_allocator_primary64.h b/lib/sanitizer_common/sanitizer_allocator_primary64.h
index 10d840a37..2af2684da 100644
--- a/lib/sanitizer_common/sanitizer_allocator_primary64.h
+++ b/lib/sanitizer_common/sanitizer_allocator_primary64.h
@@ -37,6 +37,12 @@ template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache;
 // A Region looks like this:
 // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray
 
+struct SizeClassAllocator64FlagMasks {  //  Bit masks.
+  enum {
+    kRandomShuffleChunks = 1,
+  };
+};
+
 template <class Params>
 class SizeClassAllocator64 {
  public:
@@ -46,6 +52,9 @@ class SizeClassAllocator64 {
   typedef typename Params::SizeClassMap SizeClassMap;
   typedef typename Params::MapUnmapCallback MapUnmapCallback;
 
+  static const bool kRandomShuffleChunks =
+      Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
+
   typedef SizeClassAllocator64<Params> ThisT;
   typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache;
 
@@ -307,10 +316,23 @@ class SizeClassAllocator64 {
     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.
     uptr n_allocated, n_freed;  // Just stats.
   };
   COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize);
 
+  u32 Rand(u32 *state) {  // ANSI C linear congruential PRNG.
+    return (*state = *state * 1103515245 + 12345) >> 16;
+  }
+
+  u32 RandN(u32 *state, u32 n) { return Rand(state) % n; }  // [0, n)
+
+  void RandomShuffle(u32 *a, u32 n, u32 *rand_state) {
+    if (n <= 1) return;
+    for (u32 i = n - 1; i > 0; i--)
+      Swap(a[i], a[RandN(rand_state, i + 1)]);
+  }
+
   RegionInfo *GetRegionInfo(uptr class_id) {
     CHECK_LT(class_id, kNumClasses);
     RegionInfo *regions =
@@ -362,6 +384,8 @@ class SizeClassAllocator64 {
     uptr end_idx = beg_idx + requested_count * size;
     uptr region_beg = GetRegionBeginBySizeClass(class_id);
     if (end_idx + size > region->mapped_user) {
+      if (!kUsingConstantSpaceBeg && region->mapped_user == 0)
+        region->rand_state = region_beg;  // Comes from ASLR.
       // Do the mmap for the user memory.
       uptr map_size = kUserMapSize;
       while (end_idx + size > region->mapped_user + map_size)
@@ -380,6 +404,9 @@ class SizeClassAllocator64 {
       free_array[num_freed_chunks + total_count - 1 - i] =
           PointerToCompactPtr(0, chunk);
     }
+    if (kRandomShuffleChunks)
+      RandomShuffle(&free_array[num_freed_chunks], total_count,
+                    &region->rand_state);
     region->num_freed_chunks += total_count;
     region->allocated_user += total_count * size;
     CHECK_LE(region->allocated_user, region->mapped_user);
diff --git a/lib/sanitizer_common/tests/sanitizer_allocator_test.cc b/lib/sanitizer_common/tests/sanitizer_allocator_test.cc
index d495d4f98..443dee52e 100644
--- a/lib/sanitizer_common/tests/sanitizer_allocator_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_allocator_test.cc
@@ -48,6 +48,7 @@ struct AP64 {  // Allocator Params. Short name for shorter demangled names..
   static const uptr kMetadataSize = 16;
   typedef DefaultSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 struct AP64Dyn {
@@ -56,6 +57,7 @@ struct AP64Dyn {
   static const uptr kMetadataSize = 16;
   typedef DefaultSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 struct AP64Compact {
@@ -64,6 +66,7 @@ struct AP64Compact {
   static const uptr kMetadataSize = 16;
   typedef DefaultSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 typedef SizeClassAllocator64<AP64> Allocator64;
@@ -315,6 +318,7 @@ struct AP64WithCallback {
     static const uptr kMetadataSize = 16;
     typedef DefaultSizeClassMap SizeClassMap;
     typedef TestMapUnmapCallback MapUnmapCallback;
+    static const uptr kFlags = 0;
 };
 
 TEST(SanitizerCommon, SizeClassAllocator64MapUnmapCallback) {
@@ -879,6 +883,7 @@ struct AP64_SpecialSizeClassMap {
   static const uptr kMetadataSize = 0;
   typedef SpecialSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 
 // Regression test for out-of-memory condition in PopulateFreeList().
diff --git a/lib/sanitizer_common/tests/sanitizer_allocator_testlib.cc b/lib/sanitizer_common/tests/sanitizer_allocator_testlib.cc
index 64fb19b00..c6dd3c4bb 100644
--- a/lib/sanitizer_common/tests/sanitizer_allocator_testlib.cc
+++ b/lib/sanitizer_common/tests/sanitizer_allocator_testlib.cc
@@ -43,6 +43,8 @@ struct __AP64 {
   static const uptr kMetadataSize = 0;
   typedef CompactSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags =
+      SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
 };
 
 namespace {
diff --git a/lib/scudo/scudo_allocator.cpp b/lib/scudo/scudo_allocator.cpp
index b5d8fc8bf..d5284a53e 100644
--- a/lib/scudo/scudo_allocator.cpp
+++ b/lib/scudo/scudo_allocator.cpp
@@ -38,6 +38,8 @@ struct AP {
   static const uptr kMetadataSize = 0;
   typedef DefaultSizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags =
+      SizeClassAllocator64FlagMasks::kRandomShuffleChunks;
 };
 
 typedef SizeClassAllocator64<AP> PrimaryAllocator;
diff --git a/lib/tsan/rtl/tsan_rtl.h b/lib/tsan/rtl/tsan_rtl.h
index 889a79da1..c2bddd8d7 100644
--- a/lib/tsan/rtl/tsan_rtl.h
+++ b/lib/tsan/rtl/tsan_rtl.h
@@ -72,6 +72,7 @@ struct AP64 {  // Allocator64 parameters. Deliberately using a short name.
   static const uptr kMetadataSize = 0;
   typedef DefaultSizeClassMap SizeClassMap;
   typedef __tsan::MapUnmapCallback MapUnmapCallback;
+  static const uptr kFlags = 0;
 };
 typedef SizeClassAllocator64<AP64> PrimaryAllocator;
 #endif