[GWP-ASan] Initial build files, implementation of PRNG [1].

[hctim]

Summary

See D60593 for further information.
This patch slices off the PRNG implementation and the initial build files for GWP-ASan.

[hctim]

Note that the empty compiler-rt/test/gwp_asan/CMakeLists.txt is required, as there are automatic build rules that build the tests for all sanitizers which fail if there is no test directory for gwp_asan.

[hctim]

function-static vs global-static TLS variables: http://quick-bench.com/te2xYFbzDW0dqt-ql0fOQMieFEM

Looks like the optimiser has a hard time with both of these instances (TLS check on the load and subsequent save vs. excessive register spills). Turns out the perf is about even though, with the implemented version here just nudging it out (but within the noise).

[eugenis]

compiler-rt/lib/gwp_asan/random.cpp

30

I thought we switched to __thread?
Does the generated code become more compact if these two are combined in a single thread-local aggregate?

[morehouse]

compiler-rt/lib/gwp_asan/CMakeLists.txt

11

mutex.h doesn't exist yet.

compiler-rt/lib/gwp_asan/random.cpp

18

We have double-initialization if getRandomUnsigned64 is called before these initializers run.

compiler-rt/lib/gwp_asan/random.h

18

A random namespace might be overkill.

21

1 in 2 billion is very rare. I don't see a use case for less frequent sampling than that.

[hctim]

• Updated to 32-bit PRNG, removed unneccessary definitions.h

[morehouse]

compiler-rt/lib/gwp_asan/random.cpp

17

I think static is actually implicit in this context. So static thread_local is equivalent to thread_local.

25

Since this is a compile-time constant, static doesn't do anything.

28

This seems like a lot of state to keep. Not a big deal, but is there a simpler RNG we can use? What about just xorshift32?

[hctim]

• /s/static thread_local/thread_local

[hctim]

compiler-rt/lib/gwp_asan/random.cpp

18

Fixed w/ function-local statics.

28

xorwow has a period of 2 ** 192 - 2**32, versus xorshift32 having a period of 2 ** 32. Also, surprisingly, it's about 1.2x faster than xorshift32 (http://quick-bench.com/mYmSCp5jJ_NLo3yyPXt-2N3TuHg) on my x86_64.

I personally think the 20B extra TLS/thread is worth it (given that it's likely zero overhead anyway unless the 20B pushes someone to alloc a new page for TLS). WDYT?

30

As discussed offline, the slow path + guaranteed always-correct PRNG.

compiler-rt/lib/gwp_asan/random.h

18

Removed.

21

Changed to 32-bit (using a slightly different algorithm).

[morehouse]

compiler-rt/lib/gwp_asan/random.cpp

28

2^32 seems plenty large to me. Speed isn't a huge concern since we're on the slow path, so I personally would prefer simpler. In fact if the RNG func is small enough, it might be simpler to put it directly in GPA.cc instead and reduce the number of files.

[hctim]

• Updated getRandomUnsigned32() to simply use xorshift32, instead of xorwow.

[hctim]

• Merged in master ready for submission.

compiler-rt/cmake/config-ix.cmake

 set(ALL_CRT_SUPPORTED_ARCH ${X86} ${X86_64} ${ARM32} ${ARM64})
 set(ALL_DFSAN_SUPPORTED_ARCH ${X86_64} ${MIPS64} ${ARM64})
 if(LINUX)
   set(ALL_FUZZER_SUPPORTED_ARCH ${X86} ${X86_64} ${ARM64})
 else()
   set(ALL_FUZZER_SUPPORTED_ARCH ${X86_64} ${ARM64})
 endif()
 
+set(ALL_GWP_ASAN_SUPPORTED_ARCH ${X86} ${X86_64} ${ARM64} ${ARM32})
 if(APPLE)
   set(ALL_LSAN_SUPPORTED_ARCH ${X86} ${X86_64} ${MIPS64} ${ARM64})
 else()
   set(ALL_LSAN_SUPPORTED_ARCH ${X86} ${X86_64} ${MIPS64} ${ARM64} ${ARM32} ${PPC64})
 endif()
 set(ALL_MSAN_SUPPORTED_ARCH ${X86_64} ${MIPS64} ${ARM64} ${PPC64})
 set(ALL_HWASAN_SUPPORTED_ARCH ${X86_64} ${ARM64})
 set(ALL_PROFILE_SUPPORTED_ARCH ${X86} ${X86_64} ${ARM32} ${ARM64} ${PPC64}
if(APPLE)
   set(LSAN_COMMON_SUPPORTED_ARCH ${SANITIZER_COMMON_SUPPORTED_ARCH})
   set(UBSAN_COMMON_SUPPORTED_ARCH ${SANITIZER_COMMON_SUPPORTED_ARCH})
   list_intersect(ASAN_SUPPORTED_ARCH
     ALL_ASAN_SUPPORTED_ARCH
     SANITIZER_COMMON_SUPPORTED_ARCH)
   list_intersect(DFSAN_SUPPORTED_ARCH
     ALL_DFSAN_SUPPORTED_ARCH
     SANITIZER_COMMON_SUPPORTED_ARCH)
+  list_intersect(GWP_ASAN_SUPPORTED_ARCH
+    ALL_GWP_ASAN_SUPPORTED_ARCH
+    SANITIZER_COMMON_SUPPORTED_ARCH)
   list_intersect(LSAN_SUPPORTED_ARCH
     ALL_LSAN_SUPPORTED_ARCH
     SANITIZER_COMMON_SUPPORTED_ARCH)
   list_intersect(MSAN_SUPPORTED_ARCH
     ALL_MSAN_SUPPORTED_ARCH
     SANITIZER_COMMON_SUPPORTED_ARCH)
   list_intersect(HWASAN_SUPPORTED_ARCH
     ALL_HWASAN_SUPPORTED_ARCH
else()
   filter_available_targets(SAFESTACK_SUPPORTED_ARCH
     ${ALL_SAFESTACK_SUPPORTED_ARCH})
   filter_available_targets(CFI_SUPPORTED_ARCH ${ALL_CFI_SUPPORTED_ARCH})
   filter_available_targets(SCUDO_SUPPORTED_ARCH ${ALL_SCUDO_SUPPORTED_ARCH})
   filter_available_targets(SCUDO_STANDALONE_SUPPORTED_ARCH ${ALL_SCUDO_STANDALONE_SUPPORTED_ARCH})
   filter_available_targets(XRAY_SUPPORTED_ARCH ${ALL_XRAY_SUPPORTED_ARCH})
   filter_available_targets(SHADOWCALLSTACK_SUPPORTED_ARCH
     ${ALL_SHADOWCALLSTACK_SUPPORTED_ARCH})
+  filter_available_targets(GWP_ASAN_SUPPORTED_ARCH ${ALL_GWP_ASAN_SUPPORTED_ARCH})
 endif()
 
 if (MSVC)
   # See if the DIA SDK is available and usable.
   set(MSVC_DIA_SDK_DIR "$ENV{VSINSTALLDIR}DIA SDK")
   if (IS_DIRECTORY ${MSVC_DIA_SDK_DIR})
     set(CAN_SYMBOLIZE 1)
   else()

 message(STATUS "Compiler-RT supported architectures: ${COMPILER_RT_SUPPORTED_ARCH}")
 
 if(ANDROID)
   set(OS_NAME "Android")
 else()
   set(OS_NAME "${CMAKE_SYSTEM_NAME}")
 endif()
 
-set(ALL_SANITIZERS asan;dfsan;msan;hwasan;tsan;safestack;cfi;scudo;ubsan_minimal)
+set(ALL_SANITIZERS asan;dfsan;msan;hwasan;tsan;safestack;cfi;scudo;ubsan_minimal;gwp_asan)
 set(COMPILER_RT_SANITIZERS_TO_BUILD all CACHE STRING
     "sanitizers to build if supported on the target (all;${ALL_SANITIZERS})")
 list_replace(COMPILER_RT_SANITIZERS_TO_BUILD all "${ALL_SANITIZERS}")
 
 if (SANITIZER_COMMON_SUPPORTED_ARCH AND NOT LLVM_USE_SANITIZER AND
     (OS_NAME MATCHES "Android|Darwin|Linux|FreeBSD|NetBSD|OpenBSD|Fuchsia|SunOS" OR
     (OS_NAME MATCHES "Windows" AND NOT CYGWIN AND
         (NOT MINGW OR CMAKE_CXX_COMPILER_ID MATCHES "Clang"))))

 endif()
 
 if (COMPILER_RT_HAS_SANITIZER_COMMON AND SHADOWCALLSTACK_SUPPORTED_ARCH AND
     OS_NAME MATCHES "Linux|Android")
   set(COMPILER_RT_HAS_SHADOWCALLSTACK TRUE)
 else()
   set(COMPILER_RT_HAS_SHADOWCALLSTACK FALSE)
 endif()
+
+# Note: Fuchsia and Windows are not currently supported by GWP-ASan. Support
+# is planned for these platforms. Darwin is also not supported due to TLS
+# calling malloc on first use.
+if (GWP_ASAN_SUPPORTED_ARCH AND OS_NAME MATCHES "Android|Linux")
+  set(COMPILER_RT_HAS_GWP_ASAN TRUE)
+else()
+  set(COMPILER_RT_HAS_GWP_ASAN FALSE)
+endif()
+pythonize_bool(COMPILER_RT_HAS_GWP_ASAN)

compiler-rt/lib/gwp_asan/CMakeLists.txt

+add_compiler_rt_component(gwp_asan)
+
+include_directories(..)
+
+set(GWP_ASAN_SOURCES
+  random.cpp
+)
+
+set(GWP_ASAN_HEADERS
+  random.h
+)
+
+# Disable RTTI and exception support, as we want these libraries to be
+# C-compatible. Regular C source files can be linked against the generated
+# GwpAsan libraries using the Clang C compiler.
+set(GWP_ASAN_CFLAGS -fno-rtti -fno-exceptions)
+
+if (COMPILER_RT_HAS_GWP_ASAN)
+  foreach(arch ${GWP_ASAN_SUPPORTED_ARCH})
+    add_compiler_rt_runtime(
+      clang_rt.gwp_asan
+      STATIC
+      ARCHS ${arch}
+      SOURCES ${GWP_ASAN_SOURCES}
+      ADDITIONAL_HEADERS ${GWP_ASAN_HEADERS}
+      CFLAGS ${GWP_ASAN_CFLAGS}
+      PARENT_TARGET gwp_asan
+    )
+  endforeach()
+
+  add_compiler_rt_object_libraries(RTGwpAsan
+      ARCHS ${GWP_ASAN_SUPPORTED_ARCH}
+      SOURCES ${GWP_ASAN_SOURCES}
+      ADDITIONAL_HEADERS ${GWP_ASAN_HEADERS}
+      CFLAGS ${GWP_ASAN_CFLAGS})
+endif()

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 <cstdint>
+
+namespace gwp_asan {
+// xorwow (32-bit output), extremely fast PRNG that uses arithmetic operations
+// only. Seeded using walltime mixed with xorshift32.
+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 <ctime>
+
+namespace gwp_asan {
+// xorShift32, used to initialise the PRNG state for getRandomUnsigned32.
+uint32_t xorShift32() {
+  static thread_local uint32_t RandomState =
+      static_cast<uint64_t>(time(nullptr));
+  RandomState ^= RandomState << 13;
+  RandomState ^= RandomState >> 17;
+  RandomState ^= RandomState << 5;
+  return RandomState;
+}
+
+uint32_t getRandomUnsigned32() {
+  static constexpr uint32_t WeylConstant = 362437;
+  static thread_local uint32_t RandomState[6] = {xorShift32(), xorShift32(),
+                                                 xorShift32(), xorShift32(),
+                                                 xorShift32(), xorShift32()};
+  uint32_t Temp = RandomState[0] ^ (RandomState[0] >> 2);
+  RandomState[0] = RandomState[1];
+  RandomState[1] = RandomState[2];
+  RandomState[2] = RandomState[3];
+  RandomState[3] = RandomState[4];
+  RandomState[4] =
+      RandomState[4] ^ (RandomState[4] << 4) ^ (Temp ^ (Temp << 1));
+  RandomState[5] += WeylConstant;
+  return RandomState[5] + RandomState[4];
+}
+} // namespace gwp_asan