[scudo][standalone] Implement checksumming functions

Summary:
This CL implements the checksumming functions. This departs from the
current Scudo code in one aspect: the software version is no longer
CRC32 but a BSD checksum. This is because the software CRC32 was too
impactful in terms of performances, the BSD checksum has no array
lookup which is better (and saves 1KB of data).

As with the current version, we only flip the CRC compiler flag for
a single compilation unit by default, to allow for a library compiled
with HW CRC32 to work on a system without HW CRC32.

There is some platform & hardware specific code in those files, but
since departs from a mere platform split, it felt right to me to have
it that way.

Reviewers: morehouse, eugenis, vitalybuka, hctim, mcgrathr

Reviewed By: morehouse

Subscribers: mgorny, delcypher, jfb, jdoerfert, #sanitizers, llvm-commits

Tags: #llvm, #sanitizers

Differential Revision: https://reviews.llvm.org/D59116

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@355923 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 216 insertions, 0 deletions

diff --git a/lib/scudo/standalone/CMakeLists.txt b/lib/scudo/standalone/CMakeLists.txt
index 12461c6fb..c655c3c59 100644
--- a/lib/scudo/standalone/CMakeLists.txt
+++ b/lib/scudo/standalone/CMakeLists.txt
@@ -34,13 +34,27 @@ if(ANDROID)
 endif()
 
 set(SCUDO_SOURCES
+  checksum.cc
+  crc32_hw.cc
   common.cc
   fuchsia.cc
   linux.cc)
 
+# Enable the SSE 4.2 instruction set for crc32_hw.cc, if available.
+if (COMPILER_RT_HAS_MSSE4_2_FLAG)
+  set_source_files_properties(crc32_hw.cc PROPERTIES COMPILE_FLAGS -msse4.2)
+endif()
+
+# Enable the AArch64 CRC32 feature for crc32_hw.cc, if available.
+# Note that it is enabled by default starting with armv8.1-a.
+if (COMPILER_RT_HAS_MCRC_FLAG)
+  set_source_files_properties(crc32_hw.cc PROPERTIES COMPILE_FLAGS -mcrc)
+endif()
+
 set(SCUDO_HEADERS
   atomic_helpers.h
   bytemap.h
+  checksum.h
   internal_defs.h
   linux.h
   list.h
diff --git a/lib/scudo/standalone/checksum.cc b/lib/scudo/standalone/checksum.cc
new file mode 100644
index 000000000..ff6462bcd
--- /dev/null
+++ b/lib/scudo/standalone/checksum.cc
@@ -0,0 +1,70 @@
+//===-- checksum.cc ---------------------------------------------*- 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 "checksum.h"
+#include "atomic_helpers.h"
+
+#if defined(__x86_64__) || defined(__i386__)
+#include <cpuid.h>
+#elif defined(__arm__) || defined(__aarch64__)
+#if SCUDO_FUCHSIA
+#include <zircon/features.h>
+#include <zircon/syscalls.h>
+#else
+#include <sys/auxv.h>
+#endif
+#endif
+
+namespace scudo {
+
+atomic_u8 HashAlgorithm = {BSDChecksum};
+
+#if defined(__x86_64__) || defined(__i386__)
+// i386 and x86_64 specific code to detect CRC32 hardware support via CPUID.
+// CRC32 requires the SSE 4.2 instruction set.
+#ifndef bit_SSE4_2
+#define bit_SSE4_2 bit_SSE42 // clang and gcc have different defines.
+#endif
+
+bool hasHardwareCRC32() {
+  u32 Eax, Ebx = 0, Ecx = 0, Edx = 0;
+  __get_cpuid(0, &Eax, &Ebx, &Ecx, &Edx);
+  const bool IsIntel = (Ebx == signature_INTEL_ebx) &&
+                       (Edx == signature_INTEL_edx) &&
+                       (Ecx == signature_INTEL_ecx);
+  const bool IsAMD = (Ebx == signature_AMD_ebx) && (Edx == signature_AMD_edx) &&
+                     (Ecx == signature_AMD_ecx);
+  if (!IsIntel && !IsAMD)
+    return false;
+  __get_cpuid(1, &Eax, &Ebx, &Ecx, &Edx);
+  return !!(Ecx & bit_SSE4_2);
+}
+
+#elif defined(__arm__) || defined(__aarch64__)
+#ifndef AT_HWCAP
+#define AT_HWCAP 16
+#endif
+#ifndef HWCAP_CRC32
+#define HWCAP_CRC32 (1U << 7) // HWCAP_CRC32 is missing on older platforms.
+#endif
+
+bool hasHardwareCRC32() {
+#if SCUDO_FUCHSIA
+  u32 HWCap;
+  const zx_status_t Status =
+      zx_system_get_features(ZX_FEATURE_KIND_CPU, &HWCap);
+  if (Status != ZX_OK)
+    return false;
+  return !!(HWCap & ZX_ARM64_FEATURE_ISA_CRC32);
+#else
+  return !!(getauxval(AT_HWCAP) & HWCAP_CRC32);
+#endif // SCUDO_FUCHSIA
+}
+#endif // defined(__x86_64__) || defined(__i386__)
+
+} // namespace scudo
diff --git a/lib/scudo/standalone/checksum.h b/lib/scudo/standalone/checksum.h
new file mode 100644
index 000000000..7c4afcd96
--- /dev/null
+++ b/lib/scudo/standalone/checksum.h
@@ -0,0 +1,54 @@
+//===-- checksum.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 SCUDO_CHECKSUM_H_
+#define SCUDO_CHECKSUM_H_
+
+#include "internal_defs.h"
+
+// 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.
+
+#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
+
+namespace scudo {
+
+enum ChecksumType : u8 {
+  BSDChecksum = 0,
+  HardwareCRC32 = 1,
+};
+
+// BSD checksum, unlike a software CRC32, doesn't use any array lookup. We save
+// significantly on memory accesses, as well as 1K of CRC32 table, on platforms
+// that do no support hardware CRC32. The checksum itself is 16-bit, which is at
+// odds with CRC32, but enough for our needs.
+INLINE u16 computeBSDChecksum(u16 Sum, uptr Data) {
+  for (u8 I = 0; I < sizeof(Data); I++) {
+    Sum = static_cast<u16>((Sum >> 1) | ((Sum & 1) << 15));
+    Sum = static_cast<u16>(Sum + (Data & 0xff));
+    Data >>= 8;
+  }
+  return Sum;
+}
+
+bool hasHardwareCRC32();
+WEAK u32 computeHardwareCRC32(u32 Crc, uptr Data);
+
+} // namespace scudo
+
+#endif // SCUDO_CHECKSUM_H_
diff --git a/lib/scudo/standalone/crc32_hw.cc b/lib/scudo/standalone/crc32_hw.cc
new file mode 100644
index 000000000..f4dae7b5f
--- /dev/null
+++ b/lib/scudo/standalone/crc32_hw.cc
@@ -0,0 +1,19 @@
+//===-- crc32_hw.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "checksum.h"
+
+namespace scudo {
+
+#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+u32 computeHardwareCRC32(u32 Crc, uptr Data) {
+  return static_cast<u32>(CRC32_INTRINSIC(Crc, Data));
+}
+#endif // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+
+} // namespace scudo
diff --git a/lib/scudo/standalone/tests/CMakeLists.txt b/lib/scudo/standalone/tests/CMakeLists.txt
index 908e51089..fa57db42d 100644
--- a/lib/scudo/standalone/tests/CMakeLists.txt
+++ b/lib/scudo/standalone/tests/CMakeLists.txt
@@ -51,6 +51,7 @@ endmacro()
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cc
   bytemap_test.cc
+  checksum_test.cc
   list_test.cc
   map_test.cc
   mutex_test.cc
diff --git a/lib/scudo/standalone/tests/checksum_test.cc b/lib/scudo/standalone/tests/checksum_test.cc
new file mode 100644
index 000000000..2e8dc8a7b
--- /dev/null
+++ b/lib/scudo/standalone/tests/checksum_test.cc
@@ -0,0 +1,58 @@
+//===-- checksum_test.cc ----------------------------------------*- 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 "checksum.h"
+
+#include "gtest/gtest.h"
+
+#include <string.h>
+
+scudo::u16 computeSoftwareChecksum(scudo::u32 Seed, scudo::uptr *Array,
+                                   scudo::uptr ArraySize) {
+  scudo::u16 Checksum = static_cast<scudo::u16>(Seed & 0xffff);
+  for (scudo::uptr I = 0; I < ArraySize; I++)
+    Checksum = scudo::computeBSDChecksum(Checksum, Array[I]);
+  return Checksum;
+}
+
+scudo::u16 computeHardwareChecksum(scudo::u32 Seed, scudo::uptr *Array,
+                                   scudo::uptr ArraySize) {
+  scudo::u32 Crc = Seed;
+  for (scudo::uptr I = 0; I < ArraySize; I++)
+    Crc = scudo::computeHardwareCRC32(Crc, Array[I]);
+  return static_cast<scudo::u16>((Crc & 0xffff) ^ (Crc >> 16));
+}
+
+typedef scudo::u16 (*ComputeChecksum)(scudo::u32, scudo::uptr *, scudo::uptr);
+
+// This verifies that flipping bits in the data being checksummed produces a
+// different checksum. We do not use random data to avoid flakyness.
+template <ComputeChecksum F> void verifyChecksumFunctionBitFlip() {
+  scudo::uptr Array[sizeof(scudo::u64) / sizeof(scudo::uptr)];
+  const scudo::uptr ArraySize = ARRAY_SIZE(Array);
+  memset(Array, 0xaa, sizeof(Array));
+  const scudo::u32 Seed = 0x41424343U;
+  const scudo::u16 Reference = F(Seed, Array, ArraySize);
+  scudo::u8 IdenticalChecksums = 0;
+  for (scudo::uptr I = 0; I < ArraySize; I++) {
+    for (scudo::uptr J = 0; J < SCUDO_WORDSIZE; J++) {
+      Array[I] ^= 1U << J;
+      if (F(Seed, Array, ArraySize) == Reference)
+        IdenticalChecksums++;
+      Array[I] ^= 1U << J;
+    }
+  }
+  // Allow for a couple of identical checksums over the whole set of flips.
+  EXPECT_LE(IdenticalChecksums, 2);
+}
+
+TEST(ScudoChecksumTest, ChecksumFunctions) {
+  verifyChecksumFunctionBitFlip<computeSoftwareChecksum>();
+  if (&scudo::computeHardwareCRC32 && scudo::hasHardwareCRC32())
+    verifyChecksumFunctionBitFlip<computeHardwareChecksum>();
+}