[scudo] Separate hardware CRC32 routines

[cryptoad]

Summary

As raised in D28304, enabling SSE 4.2 for the whole Scudo tree leads to the
emission of SSE 4.2 instructions everywhere, while the runtime checks only
applied to the CRC32 computing function.

This patch separates the CRC32 function taking advantage of the hardware into
its own file, and only enabled -msse4.2 for that file, if detected to be
supported by the compiler.

Another consequence of removing SSE4.2 globally is realizing that memcpy were
not being optimized, which turned out to be due to the -fno-builtin in
SANITIZER_COMMON_CFLAGS. So we now explicitely enable builtins for Scudo.

The resulting assembly looks good, with some CALLs are introduced instead of
the CRC32 code being inlined.

[mgorny]

lib/scudo/scudo_allocator.cpp

85

Stray empty line, it seems.

lib/scudo/scudo_crc32.cpp

42

This is still not entirely correct. Strictly speaking, the compiler can emit SSE4.2 instructions here, i.e. making them apply to pre-hardware or non-hardware call branch. However, it's highly unlikely it will use SSE4.2 to do comparison or function call, so I'm not going to insist on moving this elsewhere.

However, indirection into two function calls may actually affect performance, I think. Since hardware and software variants have the same signature, maybe it'd be better to replace the enum with function pointer, store hardware or software function in it and just call that function pointer in scudo_allocator?

Also, this reminds me I wanted to point out that ARM hardware variant is never used since hardware function is only called when SSE4.2 is available.

[cryptoad]

Removing empty line.

lib/scudo/scudo_crc32.cpp

42

Thank you Michal for your comments, I appreciate you having a look.

You are right about the function pointer, it would make things easier. The reasoning behind ot using one was that a call to a writeable function pointer at the core of the allocator could be leveraged by an attacker for arbitrary code execution purposes - which we are trying to avoid. Hence me trying to jump through hoops to avoid that.

Regarding the code generation, I tried to re-arrange things different ways without be able to get rid of the calls. If a solution jumps at you, I'll be happy to change things.

As for ARM, the reason there is no hardware path available yet is only due to me not having the correct devices to test it properly yet. I have an ARM32 board (without CRC capabilities), and just managed to get an AArch64 compliant OS on a Raspberry Pi 3, so it will get there shortly. I managed to get things working with -march=armv8.1-a+crc, and a runtime check based on getauxval(AT_HWCAP).

[mgorny]

Well, I've tested it and it seems to work for me. I think it's good enough to go as-is.

For a potential future improvement, this is how I'd do it:

1. Make the external file purely computeHardwareCRC32(),
2. Create an inline function in allocator that has the conditionals and calls computeHardwareCRC32 or computeSoftwareCRC32 appropriately.

This way, the hardware file is used only when hardware is selected, and the inline function can be inlined to avoid extra recurrence.

Furthermore, I would consider just skipping the runtime detection and using hardware code if __SSE4_2__ is defined in allocator, i.e. -march= used to build compiler-rt already enables SSE4.2. In this case random bits of code may require SSE4.2 already, so there's no point in excluding the CRC32.

[cryptoad]

Thank you Michal.
Good idea about skipping the detection is SSE4.2 is enabled in the allocator.

[alekseyshl]

cmake/config-ix.cmake

 check_cxx_compiler_flag(-frtti               COMPILER_RT_HAS_FRTTI_FLAG)
 check_cxx_compiler_flag(-fno-rtti            COMPILER_RT_HAS_FNO_RTTI_FLAG)
 check_cxx_compiler_flag(-ffreestanding       COMPILER_RT_HAS_FFREESTANDING_FLAG)
 check_cxx_compiler_flag("-Werror -fno-function-sections" COMPILER_RT_HAS_FNO_FUNCTION_SECTIONS_FLAG)
 check_cxx_compiler_flag(-std=c++11           COMPILER_RT_HAS_STD_CXX11_FLAG)
 check_cxx_compiler_flag(-ftls-model=initial-exec COMPILER_RT_HAS_FTLS_MODEL_INITIAL_EXEC)
 check_cxx_compiler_flag(-fno-lto             COMPILER_RT_HAS_FNO_LTO_FLAG)
 check_cxx_compiler_flag("-Werror -msse3" COMPILER_RT_HAS_MSSE3_FLAG)
+check_cxx_compiler_flag("-Werror -msse4.2"   COMPILER_RT_HAS_MSSE4_2_FLAG)
 check_cxx_compiler_flag(--sysroot=.          COMPILER_RT_HAS_SYSROOT_FLAG)
 
 if(NOT WIN32 AND NOT CYGWIN)
   # MinGW warns if -fvisibility-inlines-hidden is used.
   check_cxx_compiler_flag("-fvisibility-inlines-hidden" COMPILER_RT_HAS_FVISIBILITY_INLINES_HIDDEN_FLAG)
 endif()
 
 check_cxx_compiler_flag(/GR COMPILER_RT_HAS_GR_FLAG)

lib/scudo/CMakeLists.txt

 add_compiler_rt_component(scudo)
 
 include_directories(..)
 
 set(SCUDO_CFLAGS ${SANITIZER_COMMON_CFLAGS})
+# SANITIZER_COMMON_CFLAGS include -fno-builtin, but we actually want builtins!
+list(APPEND SCUDO_CFLAGS -fbuiltin)
 append_rtti_flag(OFF SCUDO_CFLAGS)
 
 set(SCUDO_SOURCES
   scudo_allocator.cpp
   scudo_flags.cpp
+  scudo_crc32.cpp
   scudo_interceptors.cpp
   scudo_new_delete.cpp
   scudo_termination.cpp
   scudo_utils.cpp)
 
+if (COMPILER_RT_HAS_MSSE4_2_FLAG)
+  set_source_files_properties(scudo_crc32.cpp PROPERTIES COMPILE_FLAGS -msse4.2)
+endif()
+
 if(COMPILER_RT_HAS_SCUDO)
   foreach(arch ${SCUDO_SUPPORTED_ARCH})
     add_compiler_rt_runtime(clang_rt.scudo
       STATIC
       ARCHS ${arch}
       SOURCES ${SCUDO_SOURCES}
               $<TARGET_OBJECTS:RTInterception.${arch}>
               $<TARGET_OBJECTS:RTSanitizerCommonNoTermination.${arch}>
               $<TARGET_OBJECTS:RTSanitizerCommonLibc.${arch}>
       CFLAGS ${SCUDO_CFLAGS}
       PARENT_TARGET scudo)
   endforeach()
 endif()

lib/scudo/scudo_allocator.cpp

 /// Scudo Hardened Allocator implementation.
 /// It uses the sanitizer_common allocator as a base and aims at mitigating
 /// heap corruption vulnerabilities. It provides a checksum-guarded chunk
 /// header, a delayed free list, and additional sanity checks.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "scudo_allocator.h"
+#include "scudo_crc32.h"
 #include "scudo_utils.h"
 
 #include "sanitizer_common/sanitizer_allocator_interface.h"
 #include "sanitizer_common/sanitizer_quarantine.h"
 
 #include <limits.h>
 #include <pthread.h>
 
 #include <cstring>
 
-// Hardware CRC32 is supported at compilation via the following:
-// - for i386 & x86_64: -msse4.2
-// - for ARM & AArch64: -march=armv8-a+crc
-// An additional check must be performed at runtime as well to make sure the
-// emitted instructions are valid on the target host.
-#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
-# ifdef __SSE4_2__
-#  include <smmintrin.h>
-#  define HW_CRC32 FIRST_32_SECOND_64(_mm_crc32_u32, _mm_crc32_u64)
-# endif
-# ifdef __ARM_FEATURE_CRC32
-#  include <arm_acle.h>
-#  define HW_CRC32 FIRST_32_SECOND_64(__crc32cw, __crc32cd)
-# endif
-#endif
-
 namespace __scudo {
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 const uptr AllocatorSpace = ~0ULL;
 const uptr AllocatorSize = 0x40000000000ULL;
 typedef DefaultSizeClassMap SizeClassMap;
 struct AP {
   static const uptr kSpaceBeg = AllocatorSpace;
typedef CombinedAllocator<PrimaryAllocator, AllocatorCache, SecondaryAllocator>
   ScudoAllocator;
 
 static ScudoAllocator &getAllocator();
 
 static thread_local Xorshift128Plus Prng;
 // Global static cookie, initialized at start-up.
 static uptr Cookie;
 
-enum : u8 {
-  CRC32Software = 0,
-  CRC32Hardware = 1,
-};
 // We default to software CRC32 if the alternatives are not supported, either
 // at compilation or at runtime.
 static atomic_uint8_t HashAlgorithm = { CRC32Software };
 
 // Helper function that will compute the chunk checksum, being passed all the
 // the needed information as uptrs. It will opt for the hardware version of
 // the checksumming function if available.
 INLINE u32 hashUptrs(uptr Pointer, uptr *Array, uptr ArraySize, u8 HashType) {
   u32 Crc;
-#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
-  if (HashType == CRC32Hardware) {
-    Crc = HW_CRC32(Cookie, Pointer);
-    for (uptr i = 0; i < ArraySize; i++)
-      Crc = HW_CRC32(Crc, Array[i]);
-    return Crc;
-  }
-#endif
-  Crc = computeCRC32(Cookie, Pointer);
+  Crc = computeCRC32(Cookie, Pointer, HashType);
   for (uptr i = 0; i < ArraySize; i++)
-    Crc = computeCRC32(Crc, Array[i]);
+    Crc = computeCRC32(Crc, Array[i], HashType);
   return Crc;
+
 }
 
 struct ScudoChunk : UnpackedHeader {
   // We can't use the offset member of the chunk itself, as we would double
   // fetch it without any warranty that it wouldn't have been tampered. To
   // prevent this, we work with a local copy of the header.
   void *getAllocBeg(UnpackedHeader *Header) {
     return reinterpret_cast<void *>(

lib/scudo/scudo_crc32.h

+//===-- scudo_crc32.h -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// Header for scudo_crc32.cpp.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_CRC32_H_
+#define SCUDO_CRC32_H_
+
+#include "sanitizer_common/sanitizer_internal_defs.h"
+
+namespace __scudo {
+
+enum : u8 {
+  CRC32Software = 0,
+  CRC32Hardware = 1,
+};
+
+u32 computeCRC32(u32 Crc, uptr Data, u8 HashType);
+
+}  // namespace __scudo
+
+#endif  // SCUDO_CRC32_H_

lib/scudo/scudo_crc32.cpp

+//===-- scudo_crc32.cpp -----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// CRC32 function leveraging hardware specific instructions. This has to be
+/// kept separated to restrict the use of compiler specific flags to this file.
+///
+//===----------------------------------------------------------------------===//
+
+// Hardware CRC32 is supported at compilation via the following:
+// - for i386 & x86_64: -msse4.2
+// - for ARM & AArch64: -march=armv8-a+crc or -mcrc
+// An additional check must be performed at runtime as well to make sure the
+// emitted instructions are valid on the target host.
+#include "scudo_crc32.h"
+#include "scudo_utils.h"
+
+#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+# ifdef __SSE4_2__
+#  include <smmintrin.h>
+#  define CRC32_INTRINSIC FIRST_32_SECOND_64(_mm_crc32_u32, _mm_crc32_u64)
+# endif
+# ifdef __ARM_FEATURE_CRC32
+#  include <arm_acle.h>
+#  define CRC32_INTRINSIC FIRST_32_SECOND_64(__crc32cw, __crc32cd)
+# endif
+#endif  // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+
+namespace __scudo {
+
+#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+INLINE u32 computeHardwareCRC32(u32 Crc, uptr Data) {
+  return CRC32_INTRINSIC(Crc, Data);
+}
+
+u32 computeCRC32(u32 Crc, uptr Data, u8 HashType) {
+  if (HashType == CRC32Hardware) {
+    return computeHardwareCRC32(Crc, Data);
+  }
+  return computeSoftwareCRC32(Crc, Data);
+}
+#else
+u32 computeCRC32(u32 Crc, uptr Data, u8 HashType) {
+  return computeSoftwareCRC32(Crc, Data);
+}
+#endif  // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+
+}  // namespace __scudo

lib/scudo/scudo_utils.h

u64 Next() {
     x ^= x << 23;
     State[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
     return State[1] + y;
   }
  private:
   u64 State[2];
 };
 
-// Software CRC32 functions, to be used when SSE 4.2 support is not detected.
-u32 computeCRC32(u32 Crc, uptr Data);
+// Software CRC32 functions, to be used when hardware support is not detected.
+u32 computeSoftwareCRC32(u32 Crc, uptr Data);
 
 }  // namespace __scudo
 
 #endif  // SCUDO_UTILS_H_

lib/scudo/scudo_utils.cpp

const static u32 CRC32Table[] = {
   0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
   0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
   0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 };
 
-u32 computeCRC32(u32 Crc, uptr Data)
-{
+u32 computeSoftwareCRC32(u32 Crc, uptr Data) {
   for (uptr i = 0; i < sizeof(Data); i++) {
     Crc = CRC32Table[(Crc ^ Data) & 0xff] ^ (Crc >> 8);
     Data >>= 8;
   }
   return Crc;
 }
 
 }  // namespace __scudo