[sanitizer] Random shuffling of chunks for the 32-bit Primary Allocator

Summary:
The 64-bit primary has had random shuffling of chunks for a while, this
implements it for the 32-bit primary. Scudo is currently the only user of
`kRandomShuffleChunks`.

This change consists of a few modifications:
- move the random shuffling functions out of the 64-bit primary to
  `sanitizer_common.h`. Alternatively I could move them to
  `sanitizer_allocator.h` as they are only used in the allocator, I don't feel
  strongly either way;
- small change in the 64-bit primary to make the `rand_state` initialization
  `UNLIKELY`;
- addition of a `rand_state` in the 32-bit primary's `SizeClassInfo` and
  shuffling of chunks when populating the free list.
- enabling the `random_shuffle.cpp` test on platforms using the 32-bit primary
  for Scudo.

Some comments on why the shuffling is done that way. Initially I just
implemented a `Shuffle` function in the `TransferBatch` which was simpler but I
came to realize this wasn't good enough: for chunks of 10000 bytes for example,
with a `CompactSizeClassMap`, a batch holds only 1 chunk, meaning shuffling the
batch has no effect, while a region is usually 1MB, eg: 104 chunks of that size.
So I decided to "stage" the newly gathered chunks in a temporary array that
would be shuffled prior to placing the chunks in batches.
The result is looping twice through n_chunks even if shuffling is not enabled,
but I didn't notice any significant significant performance impact.

Reviewers: alekseyshl

Reviewed By: alekseyshl

Subscribers: srhines, llvm-commits, kubamracek

Differential Revision: https://reviews.llvm.org/D39244

llvm-svn: 316596

1 files changed, 13 insertions, 0 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h b/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h
index 8c5696ea789..38368361de6 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_allocator.h
@@ -56,6 +56,19 @@ struct NoOpMapUnmapCallback {
 // Callback type for iterating over chunks.
 typedef void (*ForEachChunkCallback)(uptr chunk, void *arg);
 
+INLINE u32 Rand(u32 *state) {  // ANSI C linear congruential PRNG.
+  return (*state = *state * 1103515245 + 12345) >> 16;
+}
+
+INLINE u32 RandN(u32 *state, u32 n) { return Rand(state) % n; }  // [0, n)
+
+template<typename T>
+INLINE void RandomShuffle(T *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)]);
+}
+
 #include "sanitizer_allocator_size_class_map.h"
 #include "sanitizer_allocator_stats.h"
 #include "sanitizer_allocator_primary64.h"