[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.

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

[alekseyshl]

lib/scudo/scudo_allocator.cpp

583

This change is unrelated, please revert.

lib/scudo/scudo_utils.h

86

Does this trick really help with performance?

[cryptoad]

lib/scudo/scudo_allocator.cpp

583

Ack. Slipped in from another one sorry.

lib/scudo/scudo_utils.h

86

The numbers do not differ enough to go one way or the other, but the u8 was taking up to extra 8bytes depending on architecture. It feels it should be faster, but it definitely save space.

[cryptoad]

Addressing comment: removing an UNLIKELY that slipped through.

[cryptoad]

lib/scudo/scudo_utils.h

86

Actually scratch that. My machine was too loaded to give correct results.
The initial version appears to be faster (with the u8):

kostyak@kostyak-linux:~$ clang++ -O3 rand.cc -o rand -DWITH_CACHEDBYTESAVAILABLE
kostyak@kostyak-linux:~$ ./rand                                                 
[?] duration: 4009332558ns
kostyak@kostyak-linux:~$ clang++ -O3 rand.cc -o rand
kostyak@kostyak-linux:~$ ./rand
[?] duration: 4788913046ns

For 1<<32 iterations of getU8, and quite stable over the course of multiple runs.

I am going to reintroduce it.

[cryptoad]

lib/scudo/scudo_utils.h

86

It's actually a lot more nuanced and tricky than I was expecting.
Seeding through /dev/urandom 1<< 12 times, and iterating 1<<20 times per seeding, we get the numbers below (stable over multiple runs).
With clang, 32-bit seems equivalent, 64-bit favors the CachedBytesAvailable version.
With gcc, 32-bit favors CachedBytesAvailable, 64-bit favors the other (and overall slower for either).

kostyak@kostyak-linux:~$ clang++ -m32 -O3 rand.cc -o rand -DWITH_CACHEDBYTESAVAILABLE                                                  
kostyak@kostyak-linux:~$ ./rand                                                                                                        
[?] duration: 4814670294ns
kostyak@kostyak-linux:~$ clang++ -m32 -O3 rand.cc -o rand
kostyak@kostyak-linux:~$ ./rand
[?] duration: 4830693788ns
kostyak@kostyak-linux:~$ clang++ -O3 rand.cc -o rand -DWITH_CACHEDBYTESAVAILABLE                                                       
kostyak@kostyak-linux:~$ ./rand
[?] duration: 3115400364ns
kostyak@kostyak-linux:~$ clang++ -O3 rand.cc -o rand
kostyak@kostyak-linux:~$ ./rand
[?] duration: 4394574294ns
kostyak@kostyak-linux:~$ g++ -m32 -O3 rand.cc -o rand -DWITH_CACHEDBYTESAVAILABLE                                                                                                                                                                                               
kostyak@kostyak-linux:~$ ./rand
[?] duration: 8782558601ns
kostyak@kostyak-linux:~$ g++ -m32 -O3 rand.cc -o rand
kostyak@kostyak-linux:~$ ./rand
[?] duration: 9332069877ns
kostyak@kostyak-linux:~$ g++ -O3 rand.cc -o rand -DWITH_CACHEDBYTESAVAILABLE                                                                                                                                                                                                    
kostyak@kostyak-linux:~$ ./rand
[?] duration: 5651244009ns
kostyak@kostyak-linux:~$ g++ -O3 rand.cc -o rand
kostyak@kostyak-linux:~$ ./rand
[?] duration: 4407575998ns

Doing some ARM & Aarch64 tests additionally.
At this point I still feel reintroducing CachedBytesAvailable might provide the most benefits. LMKWYT.

[alekseyshl]

lib/scudo/scudo_utils.h

86

Given the lack of the clear performance advantage, we should go with simpler and straightforward version (CachedBytesAvailable).

[cryptoad]

lib/scudo/scudo_utils.h

86

And to make things a bit more complicated, on ARM & Aarch64 (at least with the Android toolchain), the version without CachedBytesAvailable appears faster for 32-bit, way faster for 64-bit.

[cryptoad]

Reintroducing CachedBytesAvailable to assess the amount of bytes left in the
cached u64.

[alekseyshl]

lib/scudo/scudo_utils.h

85

sizeof(u64) -> sizeof(CachedBytes)

[cryptoad]

Addressing Aleksey's comment.

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 (UNLIKELY(!UserPtr))
       return false;
     uptr UserBeg = reinterpret_cast<uptr>(UserPtr);
if (UNLIKELY(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 (UNLIKELY(!Ptr))
       return FailureHandler::OnOOM();
 
     // If requested, we will zero out the entire contents of the returned chunk.
     if ((ForceZeroContents || ZeroContents) && FromPrimary)
if (UNLIKELY(Header.State != ChunkAllocated)) {
       dieWithMessage("ERROR: invalid chunk state when sizing address %p\n",
                      Ptr);
     }
     return Chunk->getUsableSize(&Header);
   }
 
   void *calloc(uptr NMemB, uptr Size) {
     initThreadMaybe();
     if (CheckForCallocOverflow(NMemB, Size))
       return FailureHandler::OnBadRequest();
     return allocate(NMemB * Size, MinAlignment, FromMalloc, true);
   }
 
   void commitBack(ScudoThreadContext *ThreadContext) {
     AllocatorCache *Cache = getAllocatorCache(ThreadContext);
     AllocatorQuarantine.Drain(getQuarantineCache(ThreadContext),
                               QuarantineCallback(Cache));

 }
 
 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 {
+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() {
+    if (UNLIKELY(!GetRandom(reinterpret_cast<void *>(State), sizeof(State)))) {
+      // Early processes (eg: init) do not have /dev/urandom yet, but we still
+      // have to provide them with some degree of entropy. Not having a secure
+      // seed is not as problematic for them, as they are less likely to be
+      // the target of heap based vulnerabilities exploitation attempts.
+      State[0] = NanoTime();
+      State[1] = 0;
+    }
+    fillCache();
   }
+  u8 getU8() {
+    if (UNLIKELY(isCacheEmpty()))
+      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;
+  }
+  bool isCacheEmpty() {
+    return CachedBytesAvailable == 0;
+  }
+  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