[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

29

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

10

mutex.h doesn't exist yet.

compiler-rt/lib/gwp_asan/random.cpp

17

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

compiler-rt/lib/gwp_asan/random.h

17

A random namespace might be overkill.

20

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

18

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

26

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

29

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

17

Fixed w/ function-local statics.

29

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

29

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?

compiler-rt/lib/gwp_asan/random.h

17

Removed.

20

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

[morehouse]

compiler-rt/lib/gwp_asan/random.cpp

29

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
+  mutex.h
+  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/definitions.h

+//===-- gwp_asan_definitions.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_DEFINITIONS_H_
+#define GWP_ASAN_DEFINITIONS_H_
+
+#define TLS_INITIAL_EXEC __thread __attribute__((tls_model("initial-exec")))
+
+#ifdef LIKELY
+# undef LIKELY
+#endif // defined(LIKELY)
+#define LIKELY(X) __builtin_expect(!!(X), 1)
+
+#ifdef UNLIKELY
+# undef UNLIKELY
+#endif // defined(UNLIKELY)
+#define UNLIKELY(X) __builtin_expect(!!(X), 0)
+
+#ifdef ALWAYS_INLINE
+# undef ALWAYS_INLINE
+#endif // defined(ALWAYS_INLINE)
+#define ALWAYS_INLINE inline __attribute__((always_inline))
+
+#ifdef ALIGNED
+# undef ALIGNED
+#endif // defined(ALIGNED)
+#define ALIGNED(X) __attribute__((aligned(X)))
+
+#endif // GWP_ASAN_DEFINITIONS_H_

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>
+
+#include "gwp_asan/definitions.h"
+
+namespace gwp_asan {
+namespace random {
+// TODO(hctim): This may have significant overhead for platforms where
+// 64-bit arithmetic is emulated. Do we need less than a 2^32 chance of
+// sampling?
+// xorshift128+ (64-bit output). Avoids multiplication.
+ALWAYS_INLINE uint64_t getRandomUnsigned64();
+} // namespace random
+} // 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 {
+namespace random {
+
+static thread_local uint64_t RandomStateA =
+    static_cast<uint64_t>(time(nullptr));
+
+// xorshift* (64-bit output). Used to seed the xorshift128+ generator.
+uint64_t xorShiftStar64() {
+  uint64_t A = RandomStateA;
+  A ^= A >> 12;
+  A ^= A << 25;
+  A ^= A >> 27;
+  RandomStateA = A;
+  return A * 0x2545F4914F6CDD1D;
+}
+
+static thread_local uint64_t RandomStateB = xorShiftStar64();
+
+ALWAYS_INLINE uint64_t getRandomUnsigned64() {
+  uint64_t A = RandomStateA;
+  const uint64_t B = RandomStateB;
+  RandomStateA = B;
+
+  A ^= A << 23;
+  A ^= A >> 17;
+  A ^= B ^ (B >> 26);
+
+  RandomStateB = A;
+  return A + B;
+}
+} // namespace random
+} // namespace gwp_asan