[scudo] PRNG makeover

Summary:
This follows the addition of `GetRandom` with D34412. We remove our
`/dev/urandom` code and use the new function. Additionally, change the PRNG for
a slightly faster version. One of the issues with the old code is that we have
64 full bits of randomness per "next", using only 8 of those for the Salt and
discarding the rest. So we add a cached u64 in the PRNG that can serve up to
8 u8 before having to call the "next" function again.

During some integration work, I also realized that some very early processes
(like `init`) do not benefit from `/dev/urandom` yet. So if there is no
`getrandom` syscall as well, we have to fallback to some sort of initialization
of the PRNG.

Now a few words on why XoRoShiRo and not something else. I have played a while
with various PRNGs on 32 & 64 bit platforms. Some results are below. LCG 32 & 64
are usually faster but produce respectively 15 & 31 bits of entropy, meaning
that to get a full 64-bit, you would need to call them several times. The simple
XorShift is fast, produces 32 bits but is mediocre with regard to PRNG test
suites, PCG is slower overall, and XoRoShiRo is faster than XorShift128+ and
produces full 64 bits.

%%%
root@tulip-chiphd:/data # ./randtest.arm
[+] starting xs32...
[?] xs32 duration: 22431833053ns
[+] starting lcg32...
[?] lcg32 duration: 14941402090ns
[+] starting pcg32...
[?] pcg32 duration: 44941973771ns
[+] starting xs128p...
[?] xs128p duration: 48889786981ns
[+] starting lcg64...
[?] lcg64 duration: 33831042391ns
[+] starting xos128p...
[?] xos128p duration: 44850878605ns

root@tulip-chiphd:/data # ./randtest.aarch64
[+] starting xs32...
[?] xs32 duration: 22425151678ns
[+] starting lcg32...
[?] lcg32 duration: 14954255257ns
[+] starting pcg32...
[?] pcg32 duration: 37346265726ns
[+] starting xs128p...
[?] xs128p duration: 22523807219ns
[+] starting lcg64...
[?] lcg64 duration: 26141304679ns
[+] starting xos128p...
[?] xos128p duration: 14937033215ns
%%%

Reviewers: alekseyshl

Reviewed By: alekseyshl

Subscribers: aemerson, kristof.beyls, llvm-commits

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

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

1 files changed, 8 insertions, 8 deletions

diff --git a/lib/scudo/scudo_allocator.cpp b/lib/scudo/scudo_allocator.cpp
index 00fa19218..ec9132f90 100644
--- a/lib/scudo/scudo_allocator.cpp
+++ b/lib/scudo/scudo_allocator.cpp
@@ -264,7 +264,7 @@ ScudoQuarantineCache *getQuarantineCache(ScudoThreadContext *ThreadContext) {
       ScudoQuarantineCache *>(ThreadContext->QuarantineCachePlaceHolder);
 }
 
-Xorshift128Plus *getPrng(ScudoThreadContext *ThreadContext) {
+ScudoPrng *getPrng(ScudoThreadContext *ThreadContext) {
   return &ThreadContext->Prng;
 }
 
@@ -283,7 +283,7 @@ struct ScudoAllocator {
   StaticSpinMutex FallbackMutex;
   AllocatorCache FallbackAllocatorCache;
   ScudoQuarantineCache FallbackQuarantineCache;
-  Xorshift128Plus FallbackPrng;
+  ScudoPrng FallbackPrng;
 
   bool DeallocationTypeMismatch;
   bool ZeroContents;
@@ -333,8 +333,8 @@ struct ScudoAllocator {
         static_cast<uptr>(Options.QuarantineSizeMb) << 20,
         static_cast<uptr>(Options.ThreadLocalQuarantineSizeKb) << 10);
     BackendAllocator.InitCache(&FallbackAllocatorCache);
-    FallbackPrng.initFromURandom();
-    Cookie = FallbackPrng.getNext();
+    FallbackPrng.init();
+    Cookie = FallbackPrng.getU64();
   }
 
   // Helper function that checks for a valid Scudo chunk. nullptr isn't.
@@ -373,19 +373,19 @@ struct ScudoAllocator {
     bool FromPrimary = PrimaryAllocator::CanAllocate(AlignedSize, MinAlignment);
 
     void *Ptr;
-    uptr Salt;
+    u8 Salt;
     uptr AllocationSize = FromPrimary ? AlignedSize : NeededSize;
     uptr AllocationAlignment = FromPrimary ? MinAlignment : Alignment;
     ScudoThreadContext *ThreadContext = getThreadContextAndLock();
     if (LIKELY(ThreadContext)) {
-      Salt = getPrng(ThreadContext)->getNext();
+      Salt = getPrng(ThreadContext)->getU8();
       Ptr = BackendAllocator.Allocate(getAllocatorCache(ThreadContext),
                                       AllocationSize, AllocationAlignment,
                                       FromPrimary);
       ThreadContext->unlock();
     } else {
       SpinMutexLock l(&FallbackMutex);
-      Salt = FallbackPrng.getNext();
+      Salt = FallbackPrng.getU8();
       Ptr = BackendAllocator.Allocate(&FallbackAllocatorCache, AllocationSize,
                                       AllocationAlignment, FromPrimary);
     }
@@ -612,7 +612,7 @@ static void initScudoInternal(const AllocatorOptions &Options) {
 
 void ScudoThreadContext::init() {
   getBackendAllocator().InitCache(&Cache);
-  Prng.initFromURandom();
+  Prng.init();
   memset(QuarantineCachePlaceHolder, 0, sizeof(QuarantineCachePlaceHolder));
 }