[scudo] PRNG makeover

[cryptoad]

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.

[cryptoad]

Abandoning for now, this seems to have a non negligible performance impact.
I will revisit this when things settle on other fronts.

lib/scudo/scudo_allocator.cpp

AllocatorCache *getAllocatorCache(ScudoThreadContext *ThreadContext) {
   return &ThreadContext->Cache;
 }
 
 ScudoQuarantineCache *getQuarantineCache(ScudoThreadContext *ThreadContext) {
   return reinterpret_cast<
       ScudoQuarantineCache *>(ThreadContext->QuarantineCachePlaceHolder);
 }
 
-Xorshift128Plus *getPrng(ScudoThreadContext *ThreadContext) {
+ScudoPrng *getPrng(ScudoThreadContext *ThreadContext) {
   return &ThreadContext->Prng;
 }
 
 struct ScudoAllocator {
   static const uptr MaxAllowedMallocSize =
       FIRST_32_SECOND_64(2UL << 30, 1ULL << 40);
 
   typedef ReturnNullOrDieOnFailure FailureHandler;
 
   ScudoBackendAllocator BackendAllocator;
   ScudoQuarantine AllocatorQuarantine;
 
   // The fallback caches are used when the thread local caches have been
   // 'detroyed' on thread tear-down. They are protected by a Mutex as they can
   // be accessed by different threads.
   StaticSpinMutex FallbackMutex;
   AllocatorCache FallbackAllocatorCache;
   ScudoQuarantineCache FallbackQuarantineCache;
-  Xorshift128Plus FallbackPrng;
+  ScudoPrng FallbackPrng;
 
   bool DeallocationTypeMismatch;
   bool ZeroContents;
   bool DeleteSizeMismatch;
 
   explicit ScudoAllocator(LinkerInitialized)
     : AllocatorQuarantine(LINKER_INITIALIZED),
       FallbackQuarantineCache(LINKER_INITIALIZED) {}
void init(const AllocatorOptions &Options) {
     DeleteSizeMismatch = Options.DeleteSizeMismatch;
     ZeroContents = Options.ZeroContents;
     SetAllocatorMayReturnNull(Options.MayReturnNull);
     BackendAllocator.Init(Options.ReleaseToOSIntervalMs);
     AllocatorQuarantine.Init(
         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.
   bool isValidPointer(const void *UserPtr) {
     initThreadMaybe();
     if (!UserPtr)
       return false;
     uptr UserBeg = reinterpret_cast<uptr>(UserPtr);
if (AlignedSize >= MaxAllowedMallocSize)
       return FailureHandler::OnBadRequest();
 
     // Primary and Secondary backed allocations have a different treatment. We
     // deal with alignment requirements of Primary serviced allocations here,
     // but the Secondary will take care of its own alignment needs.
     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);
     }
     if (!Ptr)
       return FailureHandler::OnOOM();
 
     // If requested, we will zero out the entire contents of the returned chunk.
     if ((ForceZeroContents || ZeroContents) && FromPrimary)
if (FromPrimary) {
       // The secondary fits the allocations to a page, so the amount of unused
       // bytes is the difference between the end of the user allocation and the
       // next page boundary.
       uptr PageSize = GetPageSizeCached();
       uptr TrailingBytes = (UserBeg + Size) & (PageSize - 1);
       if (TrailingBytes)
         Header.SizeOrUnusedBytes = PageSize - TrailingBytes;
     }
-    Header.Salt = static_cast<u8>(Salt);
+    Header.Salt = Salt;
     getScudoChunk(UserBeg)->storeHeader(&Header);
     void *UserPtr = reinterpret_cast<void *>(UserBeg);
     // if (&__sanitizer_malloc_hook) __sanitizer_malloc_hook(UserPtr, Size);
     return UserPtr;
   }
 
   // Place a chunk in the quarantine. In the event of a zero-sized quarantine,
   // we directly deallocate the chunk, otherwise the flow would lead to the

 }
 
 static void initScudoInternal(const AllocatorOptions &Options) {
   Instance.init(Options);
 }
 
 void ScudoThreadContext::init() {
   getBackendAllocator().InitCache(&Cache);
-  Prng.initFromURandom();
+  Prng.init();
   memset(QuarantineCachePlaceHolder, 0, sizeof(QuarantineCachePlaceHolder));
 }
 
 void ScudoThreadContext::commitBack() {
   Instance.commitBack(this);
 }
 
 void *scudoMalloc(uptr Size, AllocType Type) {

lib/scudo/scudo_tls.h

 namespace __scudo {
 
 // Platform specific base thread context definitions.
 #include "scudo_tls_context_android.inc"
 #include "scudo_tls_context_linux.inc"
 
 struct ALIGNED(64) ScudoThreadContext : public ScudoThreadContextPlatform {
   AllocatorCache Cache;
-  Xorshift128Plus Prng;
+  ScudoPrng Prng;
   uptr QuarantineCachePlaceHolder[4];
   void init();
   void commitBack();
 };
 
 void initThread();
 
 // Platform specific dastpath functions definitions.
 #include "scudo_tls_android.inc"
 #include "scudo_tls_linux.inc"
 
 }  // namespace __scudo
 
 #endif  // SCUDO_TLS_H_

lib/scudo/scudo_utils.h

 }
 
 void NORETURN dieWithMessage(const char *Format, ...);
 
 enum CPUFeature {
   CRC32CPUFeature = 0,
   MaxCPUFeature,
 };
+
 bool testCPUFeature(CPUFeature feature);
 
-// Tiny PRNG based on https://en.wikipedia.org/wiki/Xorshift#xorshift.2B
-// The state (128 bits) will be stored in thread local storage.
-struct Xorshift128Plus {
+static INLINE u64 rotl(const u64 X, int K) {
+  return (X << K) | (X >> (64 - K));
+}
+
+// XoRoShiRo128+ PRNG (http://xoroshiro.di.unimi.it/).
+struct XoRoShiRo128Plus {
  public:
-  void initFromURandom();
-  u64 getNext() {
-    u64 x = State[0];
-    const u64 y = State[1];
-    State[0] = y;
-    x ^= x << 23;
-    State[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
-    return State[1] + y;
+  void init() {
+    CHECK(GetRandom(reinterpret_cast<void *>(State), sizeof(State)));
+    fillCache();
+  }
+  u8 getU8() {
+    if (UNLIKELY(CachedBytesAvailable == 0))
+      fillCache();
+    const u8 Result = static_cast<u8>(CachedBytes & 0xff);
+    CachedBytes >>= 8;
+    CachedBytesAvailable--;
+    return Result;
   }
+  u64 getU64() { return next(); }
  private:
+  u8 CachedBytesAvailable;
+  u64 CachedBytes;
   u64 State[2];
+  u64 next() {
+    const u64 S0 = State[0];
+    u64 S1 = State[1];
+    const u64 Result = S0 + S1;
+    S1 ^= S0;
+    State[0] = rotl(S0, 55) ^ S1 ^ (S1 << 14);
+    State[1] = rotl(S1, 36);
+    return Result;
+ }
+  void fillCache() {
+    CachedBytes = next();
+    CachedBytesAvailable = sizeof(CachedBytes);
+  }
 };
 
+typedef XoRoShiRo128Plus ScudoPrng;
+
 }  // namespace __scudo
 
 #endif  // SCUDO_UTILS_H_

lib/scudo/scudo_utils.cpp

bool testCPUFeature(CPUFeature Feature) {
   return false;
 }
 #else
 bool testCPUFeature(CPUFeature Feature) {
   return false;
 }
 #endif  // defined(__x86_64__) || defined(__i386__)
 
-// readRetry will attempt to read Count bytes from the Fd specified, and if
-// interrupted will retry to read additional bytes to reach Count.
-static ssize_t readRetry(int Fd, u8 *Buffer, size_t Count) {
-  ssize_t AmountRead = 0;
-  while (static_cast<size_t>(AmountRead) < Count) {
-    ssize_t Result = read(Fd, Buffer + AmountRead, Count - AmountRead);
-    if (Result > 0)
-      AmountRead += Result;
-    else if (!Result)
-      break;
-    else if (errno != EINTR) {
-      AmountRead = -1;
-      break;
-    }
-  }
-  return AmountRead;
-}
-
-static void fillRandom(u8 *Data, ssize_t Size) {
-  int Fd = open("/dev/urandom", O_RDONLY);
-  if (Fd < 0) {
-    dieWithMessage("ERROR: failed to open /dev/urandom.\n");
-  }
-  bool Success = readRetry(Fd, Data, Size) == Size;
-  close(Fd);
-  if (!Success) {
-    dieWithMessage("ERROR: failed to read enough data from /dev/urandom.\n");
-  }
-}
-
-// Seeds the xorshift state with /dev/urandom.
-// TODO(kostyak): investigate using getrandom() if available.
-void Xorshift128Plus::initFromURandom() {
-  fillRandom(reinterpret_cast<u8 *>(State), sizeof(State));
-}
-
 }  // namespace __scudo