[GWP-ASan] Move random-related code in the allocator

[cryptoad]

Summary

We need to have all thread specific data packed into a single uint64_t
for the upcoming Fuchsia support. We can move the RandomState into the
ThreadLocalPackedVariables, reducing the size of NextSampleCounter
to 31 bits (or we could reduce RandomState to 31 bits).

We move getRandomUnsigned32 into the platform agnostic part of the
class, and initPRNG in the platform specific part.

ScopedBoolean is replaced by actual assignments since non-const
references to bitfields are prohibited.

random.{h,cpp} are removed.

[cryptoad]

• Update options check to account for 31 bits.
• Use an initializer for RandomState that yield 0xffffffff on first XorShift iteration.

[cryptoad]

• Restoring the old constants because some test failed with mine.

[hctim]

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp

150–151

While we're here, can you also add ThreadLocals.NextSampleCounter = AdjustedSampleRatePlusOne - 1; to keep on the slow path for 2^31 more allocations after 2^31 have been done?

160

I'd prefer if this could be a private class like ScopedRecursiveGuard inside GPA where the c'tor sets ThreadLocals.RecursiveGuard = true; and the d'tor sets ThreadLocals.RecursiveGuard = false;.

281

Originally the goal was to keep this PRNG as platform-specific implementation and just provide xorshift as a default (so if someone wanted their own proper PRNG they could provide it). After thinking, this is fine anyway, as if we want to provide platform-specific sampling then we want to allow other methods like 1-in-N-bytes and so will need a refactor anyway.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.h

222

nit: Seeded using platform-specific mechanisms by initPRNG().

[cryptoad]

Addressing review comments.

[hctim]

LGTM!

[nikic]

I've reverted this in https://github.com/llvm/llvm-project/commit/04e42f62548d4c0367664188a938b609435718e2 due to a build failure with GCC. The code seems a bit sensitive, so I didn't want to introduce random casts.

[cryptoad]

In D89908#2348293, @nikic wrote:

I've reverted this in https://github.com/llvm/llvm-project/commit/04e42f62548d4c0367664188a938b609435718e2 due to a build failure with GCC. The code seems a bit sensitive, so I didn't want to introduce random casts.

Thank you, will fix it and reland.

compiler-rt/lib/gwp_asan/CMakeLists.txt

 add_compiler_rt_component(gwp_asan)
 
 include_directories(..)
 
 set(GWP_ASAN_SOURCES
   common.cpp
   crash_handler.cpp
   platform_specific/common_posix.cpp
   platform_specific/guarded_pool_allocator_posix.cpp
   platform_specific/mutex_posix.cpp
   platform_specific/utilities_posix.cpp
   guarded_pool_allocator.cpp
-  random.cpp
   stack_trace_compressor.cpp
   utilities.cpp
 )
 
 set(GWP_ASAN_HEADERS
   common.h
   crash_handler.h
   definitions.h
   guarded_pool_allocator.h
   mutex.h
   options.h
   options.inc
-  random.h
   stack_trace_compressor.h
   utilities.h
 )
 
 # Ensure that GWP-ASan meets the delegated requirements of some supporting
 # allocators. Some supporting allocators (e.g. scudo standalone) cannot use any
 # parts of the C++ standard library.
 set(GWP_ASAN_CFLAGS ${SANITIZER_COMMON_CFLAGS} -fno-rtti -fno-exceptions

compiler-rt/lib/gwp_asan/guarded_pool_allocator.h

 //===-- guarded_pool_allocator.h --------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
 #define GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_
 
 #include "gwp_asan/common.h"
 #include "gwp_asan/definitions.h"
 #include "gwp_asan/mutex.h"
 #include "gwp_asan/options.h"
-#include "gwp_asan/random.h"
 #include "gwp_asan/stack_trace_compressor.h"
 
 #include <stddef.h>
 #include <stdint.h>
 
 namespace gwp_asan {
 // This class is the primary implementation of the allocator portion of GWP-
 // ASan. It is the sole owner of the pool of sequentially allocated guarded
private:
   // GWP-ASan is disabled, we wish to never spend wasted cycles recalculating
   // the sample rate.
   uint32_t AdjustedSampleRatePlusOne = 0;
 
   // Pack the thread local variables into a struct to ensure that they're in
   // the same cache line for performance reasons. These are the most touched
   // variables in GWP-ASan.
   struct alignas(8) ThreadLocalPackedVariables {
-    constexpr ThreadLocalPackedVariables() {}
+    constexpr ThreadLocalPackedVariables()
+        : RandomState(0xff82eb50), NextSampleCounter(0), RecursiveGuard(false) {
+    }
+    // Initialised to a magic constant so that an uninitialised GWP-ASan won't
+    // regenerate its sample counter for as long as possible. The xorshift32()
+    // algorithm used below results in getRandomUnsigned32(0xff82eb50) ==
+    // 0xfffffea4.
+    uint32_t RandomState;
     // Thread-local decrementing counter that indicates that a given allocation
     // should be sampled when it reaches zero.
-    uint32_t NextSampleCounter = 0;
+    uint32_t NextSampleCounter : 31;
     // Guard against recursivity. Unwinders often contain complex behaviour that
     // may not be safe for the allocator (i.e. the unwinder calls dlopen(),
     // which calls malloc()). When recursive behaviour is detected, we will
     // automatically fall back to the supporting allocator to supply the
     // allocation.
-    bool RecursiveGuard = false;
+    bool RecursiveGuard : 1;
+  };
+  static_assert(sizeof(ThreadLocalPackedVariables) == sizeof(uint64_t),
+                "thread local data does not fit in a uint64_t");
+
+  class ScopedRecursiveGuard {
+  public:
+    ScopedRecursiveGuard() { ThreadLocals.RecursiveGuard = true; }
+    ~ScopedRecursiveGuard() { ThreadLocals.RecursiveGuard = false; }
   };
+
+  // Initialise the PRNG, platform-specific.
+  void initPRNG();
+
+  // xorshift (32-bit output), extremely fast PRNG that uses arithmetic
+  // operations only. Seeded using platform-specific mechanisms by initPRNG().
+  uint32_t getRandomUnsigned32();
+
   static GWP_ASAN_TLS_INITIAL_EXEC ThreadLocalPackedVariables ThreadLocals;
 };
 } // namespace gwp_asan
 
 #endif // GWP_ASAN_GUARDED_POOL_ALLOCATOR_H_

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp

 //===-- guarded_pool_allocator.cpp ------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "gwp_asan/guarded_pool_allocator.h"
 
 #include "gwp_asan/optional/segv_handler.h"
 #include "gwp_asan/options.h"
-#include "gwp_asan/random.h"
 #include "gwp_asan/utilities.h"
 
 // RHEL creates the PRIu64 format macro (for printing uint64_t's) only when this
 // macro is defined before including <inttypes.h>.
 #ifndef __STDC_FORMAT_MACROS
 #define __STDC_FORMAT_MACROS 1
 #endif
 

 namespace gwp_asan {
 namespace {
 // Forward declare the pointer to the singleton version of this class.
 // Instantiated during initialisation, this allows the signal handler
 // to find this class in order to deduce the root cause of failures. Must not be
 // referenced by users outside this translation unit, in order to avoid
 // init-order-fiasco.
 GuardedPoolAllocator *SingletonPtr = nullptr;
-
-class ScopedBoolean {
-public:
-  ScopedBoolean(bool &B) : Bool(B) { Bool = true; }
-  ~ScopedBoolean() { Bool = false; }
-
-private:
-  bool &Bool;
-};
 } // anonymous namespace
 
 // Gets the singleton implementation of this class. Thread-compatible until
 // init() is called, thread-safe afterwards.
 GuardedPoolAllocator *GuardedPoolAllocator::getSingleton() {
   return SingletonPtr;
 }
 
 void GuardedPoolAllocator::init(const options::Options &Opts) {
   // Note: We return from the constructor here if GWP-ASan is not available.
   // This will stop heap-allocation of class members, as well as mmap() of the
   // guarded slots.
   if (!Opts.Enabled || Opts.SampleRate == 0 ||
       Opts.MaxSimultaneousAllocations == 0)
     return;
 
   Check(Opts.SampleRate >= 0, "GWP-ASan Error: SampleRate is < 0.");
-  Check(Opts.SampleRate <= INT32_MAX, "GWP-ASan Error: SampleRate is > 2^31.");
+  Check(Opts.SampleRate < (1 << 30), "GWP-ASan Error: SampleRate is >= 2^30.");
   Check(Opts.MaxSimultaneousAllocations >= 0,
         "GWP-ASan Error: MaxSimultaneousAllocations is < 0.");
 
   SingletonPtr = this;
   Backtrace = Opts.Backtrace;
 
   State.MaxSimultaneousAllocations = Opts.MaxSimultaneousAllocations;
 

 
 static uintptr_t getPageAddr(uintptr_t Ptr, uintptr_t PageSize) {
   return Ptr & ~(PageSize - 1);
 }
 
 void *GuardedPoolAllocator::allocate(size_t Size) {
   // GuardedPagePoolEnd == 0 when GWP-ASan is disabled. If we are disabled, fall
   // back to the supporting allocator.
-  if (State.GuardedPagePoolEnd == 0)
+  if (State.GuardedPagePoolEnd == 0) {
+    ThreadLocals.NextSampleCounter = AdjustedSampleRatePlusOne - 1;
     return nullptr;
+  }
 
   // Protect against recursivity.
   if (ThreadLocals.RecursiveGuard)
     return nullptr;
-  ScopedBoolean SB(ThreadLocals.RecursiveGuard);
+  ScopedRecursiveGuard SRG;
 
   if (Size == 0 || Size > State.maximumAllocationSize())
     return nullptr;
 
   size_t Index;
   {
     ScopedLock L(PoolMutex);
     Index = reserveSlot();
   }
 
   if (Index == kInvalidSlotID)
     return nullptr;
// pool during the expensive markInaccessible() call.
     // Ensure that the deallocation is recorded before marking the page as
     // inaccessible. Otherwise, a racy use-after-free will have inconsistent
     // metadata.
     Meta->RecordDeallocation();
 
     // Ensure that the unwinder is not called if the recursive flag is set,
     // otherwise non-reentrant unwinders may deadlock.
     if (!ThreadLocals.RecursiveGuard) {
-      ScopedBoolean B(ThreadLocals.RecursiveGuard);
+      ScopedRecursiveGuard SRG;
       Meta->DeallocationTrace.RecordBacktrace(Backtrace);
     }
   }
 
   markInaccessible(reinterpret_cast<void *>(SlotStart),
                    State.maximumAllocationSize(), kGwpAsanGuardPageName);
 
   // And finally, lock again to release the slot back into the pool.
size_t GuardedPoolAllocator::reserveSlot() {
   return SlotIndex;
 }
 
 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) {
   assert(FreeSlotsLength < State.MaxSimultaneousAllocations);
   FreeSlots[FreeSlotsLength++] = SlotIndex;
 }
 
+uint32_t GuardedPoolAllocator::getRandomUnsigned32() {
+  uint32_t RandomState = ThreadLocals.RandomState;
+  RandomState ^= RandomState << 13;
+  RandomState ^= RandomState >> 17;
+  RandomState ^= RandomState << 5;
+  ThreadLocals.RandomState = RandomState;
+  return RandomState;
+}
+
 GWP_ASAN_TLS_INITIAL_EXEC
 GuardedPoolAllocator::ThreadLocalPackedVariables
     GuardedPoolAllocator::ThreadLocals;
 } // namespace gwp_asan

compiler-rt/lib/gwp_asan/options.inc

 
 GWP_ASAN_OPTION(int, MaxSimultaneousAllocations, 16,
                 "Number of simultaneously-guarded allocations available in the "
                 "pool. Defaults to 16.")
 
 GWP_ASAN_OPTION(int, SampleRate, 5000,
                 "The probability (1 / SampleRate) that an allocation is "
                 "selected for GWP-ASan sampling. Default is 5000. Sample rates "
-                "up to (2^31 - 1) are supported.")
+                "up to (2^30 - 1) are supported.")
 
 // Developer note - This option is not actually processed by GWP-ASan itself. It
 // is included here so that a user can specify whether they want signal handlers
 // or not. The supporting allocator should inspect this value to see whether
 // signal handlers need to be installed, and then use
 // crash_handler::installSignalHandlers() in order to install the handlers. Note
 // that in order to support signal handlers, you will need to link against the
 // optional crash_handler component.

compiler-rt/lib/gwp_asan/platform_specific/guarded_pool_allocator_posix.cpp

 
 #include <assert.h>
 #include <errno.h>
 #include <signal.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/mman.h>
 #include <sys/types.h>
+#include <time.h>
 #include <unistd.h>
 
 #ifdef ANDROID
 #include <sys/prctl.h>
 #define PR_SET_VMA 0x53564d41
 #define PR_SET_VMA_ANON_NAME 0
 #endif // ANDROID
 
 void MaybeSetMappingName(void *Mapping, size_t Size, const char *Name) {
 #ifdef ANDROID
   prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, Mapping, Size, Name);
 #endif // ANDROID
   // Anonymous mapping names are only supported on Android.
   return;
 }
 
 namespace gwp_asan {
+
+void GuardedPoolAllocator::initPRNG() {
+  ThreadLocals.RandomState = time(nullptr) + getThreadID();
+}
+
 void *GuardedPoolAllocator::mapMemory(size_t Size, const char *Name) const {
   void *Ptr =
       mmap(nullptr, Size, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
   Check(Ptr != MAP_FAILED, "Failed to map guarded pool allocator memory");
   MaybeSetMappingName(Ptr, Size, Name);
   return Ptr;
 }
 

compiler-rt/lib/gwp_asan/random.h

-//===-- random.h ------------------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef GWP_ASAN_RANDOM_H_
-#define GWP_ASAN_RANDOM_H_
-
-#include <stdint.h>
-
-namespace gwp_asan {
-// Initialise the PRNG, using time and thread ID as the seed.
-void initPRNG();
-
-// xorshift (32-bit output), extremely fast PRNG that uses arithmetic operations
-// only. Seeded using walltime.
-uint32_t getRandomUnsigned32();
-} // namespace gwp_asan
-
-#endif // GWP_ASAN_RANDOM_H_

compiler-rt/lib/gwp_asan/random.cpp

-//===-- random.cpp ----------------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "gwp_asan/random.h"
-#include "gwp_asan/common.h"
-
-#include <time.h>
-
-// Initialised to a magic constant so that an uninitialised GWP-ASan won't
-// regenerate its sample counter for as long as possible. The xorshift32()
-// algorithm used below results in getRandomUnsigned32(0xff82eb50) ==
-// 0xfffffea4.
-GWP_ASAN_TLS_INITIAL_EXEC uint32_t RandomState = 0xff82eb50;
-
-namespace gwp_asan {
-void initPRNG() { RandomState = time(nullptr) + getThreadID(); }
-
-uint32_t getRandomUnsigned32() {
-  RandomState ^= RandomState << 13;
-  RandomState ^= RandomState >> 17;
-  RandomState ^= RandomState << 5;
-  return RandomState;
-}
-} // namespace gwp_asan