[scudo][standalone] Implement checksumming functions

[cryptoad]

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.

[mgorny]

If you have to bundle a new hash, have you considered using one of the modern fast hashes (such as xxHash, CityHash, …)?

[cryptoad]

In D59116#1422442, @mgorny wrote:

If you have to bundle a new hash, have you considered using one of the modern fast hashes (such as xxHash, CityHash, …)?

For Scudo, we need something that will checksum 96bits on 32-bit & 160 bits on 64-bit with as few cycles as possible, and that can (hopefully) detect corruption.
CityHash & xxHash are, in my opinion, way too complex for our use case, and likely slower than the BSD checksum for software. HW CRC32 ends up being a couple of asm instructions and is super quick for our purpose.
So in the end, I do not think that those hashes would be worth using here.

[eugenis]

Could this be done with a target("sse4.2") function attribute instead of cmake conditions?

[hctim]

Is it possible to update the document at llvm/docs/ScudoHardenedAllocator.rst to reflect these changes?

[morehouse]

lib/scudo/standalone/checksum.cc

69

Perhaps comments with the matching ifdefs would be helpful here, especially since this last one matches way up at line 27.

lib/scudo/standalone/checksum.h

11

SCUDO_CHECKSUM_H

21

The outer if-defined looks unnecessary.

39

s/That/BSD

46

Are these static_casts necessary?

[cryptoad]

In D59116#1422986, @eugenis wrote:

Could this be done with a target("sse4.2") function attribute instead of cmake conditions?

I have had no success with early tries with attribute target, mostly due to discrepancies between clang & gcc (depending on versions). Like target("+crc") doesn't seem to work with my clangs (https://gcc.gnu.org/onlinedocs/gcc/ARM-Function-Attributes.html).
Additional concern about this is the resolver function that is used on every invocation of the function (at least with g++).
While this could be addressed with a function pointer, I am trying to avoid a writable function pointer in a critical path of the allocator as it could be leveraged for exploitation purposes.

[cryptoad]

In D59116#1423009, @hctim wrote:

Is it possible to update the document at llvm/docs/ScudoHardenedAllocator.rst to reflect these changes?

In theory, this still doc still applies to the "current" version of Scudo which is coexisting with the standalone one.
A solution would be to write a standalone-doc where this would go, but as of now the repo doesn't have a functional standalone allocator so this might be too early.

[cryptoad]

Addressing review comments.

[cryptoad]

lib/scudo/standalone/checksum.h

46

Apparently the result of the operations were promoted (I wouldn't have thought) and lead to the following (with strict W options):

error: implicit conversion loses integer precision: 'int' to 'scudo::u16' (aka 'unsigned short') [-Werror,-Wimplicit-int-conversion]
error: conversion from 'scudo::uptr' {aka 'long unsigned int'} to 'scudo::u16' {aka 'short unsigned int'} may change value [-Werror=conversion]

[morehouse]

LGTM

lib/scudo/standalone/CMakeLists.txt

 
 if(ANDROID)
 # Put the shared library in the global group. For more details, see
 # android-changes-for-ndk-developers.md#changes-to-library-search-order
   append_list_if(COMPILER_RT_HAS_Z_GLOBAL -Wl,-z,global SCUDO_LINK_FLAGS)
 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
   mutex.h
   platform.h
   stats.h
   vector.h)
 

lib/scudo/standalone/checksum.h

+//===-- 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_

lib/scudo/standalone/checksum.cc

+//===-- 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

lib/scudo/standalone/crc32_hw.cc

+//===-- 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

lib/scudo/standalone/tests/CMakeLists.txt

foreach(arch ${SCUDO_TEST_ARCH})
         LINK_FLAGS ${LINK_FLAGS})
     endforeach()
   endif()
 endmacro()
 
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cc
   bytemap_test.cc
+  checksum_test.cc
   list_test.cc
   map_test.cc
   mutex_test.cc
   stats_test.cc
   vector_test.cc
   scudo_unit_test_main.cc)
 
 add_scudo_unittest(ScudoUnitTest
   SOURCES ${SCUDO_UNIT_TEST_SOURCES})

lib/scudo/standalone/tests/checksum_test.cc

+//===-- 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>();
+}