[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

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@316596 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 0 insertions, 2 deletions

diff --git a/test/scudo/random_shuffle.cpp b/test/scudo/random_shuffle.cpp
index da004484a..54768a578 100644
--- a/test/scudo/random_shuffle.cpp
+++ b/test/scudo/random_shuffle.cpp
@@ -7,8 +7,6 @@
 // RUN: %run %t 10000 > %T/random_shuffle_tmp_dir/out2
 // RUN: not diff %T/random_shuffle_tmp_dir/out?
 // RUN: rm -rf %T/random_shuffle_tmp_dir
-// UNSUPPORTED: i386-linux,arm-linux,armhf-linux,aarch64-linux,mips-linux,mipsel-linux,mips64-linux,mips64el-linux
-// UNSUPPORTED: android
 
 // Tests that the allocator shuffles the chunks before returning to the user.