[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

0 files changed, 0 insertions, 0 deletions