[scudo][standalone] Introduce the chunk header

[cryptoad]

Summary

... and its related functions.

The structure and its functionalities are identical to existing ones.
The header stores information on a scudo::Chunk to be able to detect
inconsitencies or potential corruption attempts. It is checksummed for
that purpose.

[vitalybuka]

lib/scudo/standalone/chunk.h

31

enum class ChunkState : u8 {

Available = 0,
Allocated = 1,
Quarantine = 2,

};

40

can you use your enums here instead of u64

43

why it uses u64 for 2bit fields?

59

does this have to be inline?

70

So you cant guaranty that it does not call computeChecksum before init() so you can avoid atomic operation?

[cryptoad]

lib/scudo/standalone/chunk.h

43

I remembered having issues where the end structure was not ending up on a u64, but it seems to work with enums.
I changed the type as well to be a class enum.

59

Yes. This does matter when compiled with SSE4.2 for example, the resulting compiled code end up being 2 successive crc32 instructions without any extraneous calls.

70

I am not sure I understand this, do you mean I should not use atomics?
The function should never be called prior to initialization (malloc will call the allocator's init() before servicing an allocation).

[cryptoad]

Updated to use class enums, and put some structures that uses to
be in the scudo namespace into the scudo::Chunk one, as it
makes more sense.

[vitalybuka]

lib/scudo/standalone/chunk.h

70

If all threads will be blocked on init() and released after it's done, and global never changes after that then atomic is not needed

[cryptoad]

lib/scudo/standalone/chunk.h

70

This is indeed the case, I will remove the atomic use.

[vitalybuka]

lib/scudo/standalone/tests/chunk_test.cc

24

you can wrap everything into
namespace scudo::Chunk {
or just add using scudo::Chunk;

[cryptoad]

lib/scudo/standalone/tests/chunk_test.cc

24

While I agree that this would simplify a bit the code, I think not using using or putting the tests in the namespace allows for more clarity as to where class and functions are located within the hierarchy of the project. I actually like it better and it forced me to rethink a bit some of the code organization when I was writing the tests.

[cryptoad]

The HashAlgorithm global variable doesn't have to be atomic since
all alloc operations are stalled until init completes. Update things
accordingly (thanks Vitaly).

[cryptoad]

Rename AllocTypeMask to OriginMask.

[cryptoad]

Actually remove 2 unused masks.

[cryptoad]

Working out some kinks on Fuchsia. Will update once it's ironed out.

[cryptoad]

I had to backpedal on some of changes due to some errors uncovered
while testing on Fuchsia.

The main reason is https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61414
which complains that the number of bits used to store the enum class
is not enough (while it is, really). musl being compiled strictly on
Fuchsia, this ends up in an error. Keeping State and Origin as
enum class, except in the UnpackedHeader ended up requiring a
whole lot of static_cast.

In the end, to make it work on everything, I reverted back Origin
and State to standard enum, and added a comment explaining the
situation.

lib/scudo/standalone/CMakeLists.txt

 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
+  chunk.h
   flags.h
   flags_parser.h
   fuchsia.h
   interface.h
   internal_defs.h
   linux.h
   list.h
   mutex.h

lib/scudo/standalone/checksum.h

 #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,
+enum class Checksum : u8 {
+  BSD = 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) {

lib/scudo/standalone/checksum.cc

 #include <zircon/syscalls.h>
 #else
 #include <sys/auxv.h>
 #endif
 #endif
 
 namespace scudo {
 
-atomic_u8 HashAlgorithm = {BSDChecksum};
+Checksum HashAlgorithm = {Checksum::BSD};
 
 #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
 

lib/scudo/standalone/chunk.h

+//===-- chunk.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_CHUNK_H_
+#define SCUDO_CHUNK_H_
+
+#include "platform.h"
+
+#include "atomic_helpers.h"
+#include "checksum.h"
+#include "common.h"
+#include "report.h"
+
+namespace scudo {
+
+extern Checksum HashAlgorithm;
+
+INLINE u16 computeChecksum(u32 Seed, uptr Value, uptr *Array, uptr ArraySize) {
+  // If the hardware CRC32 feature is defined here, it was enabled everywhere,
+  // as opposed to only for crc32_hw.cc. This means that other hardware specific
+  // instructions were likely emitted at other places, and as a result there is
+  // no reason to not use it here.
+#if defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+  u32 Crc = static_cast<u32>(CRC32_INTRINSIC(Seed, Value));
+  for (uptr I = 0; I < ArraySize; I++)
+    Crc = static_cast<u32>(CRC32_INTRINSIC(Crc, Array[I]));
+  return static_cast<u16>((Crc & 0xffff) ^ (Crc >> 16));
+#else
+  if (HashAlgorithm == Checksum::HardwareCRC32) {
+    u32 Crc = computeHardwareCRC32(Seed, Value);
+    for (uptr I = 0; I < ArraySize; I++)
+      Crc = computeHardwareCRC32(Crc, Array[I]);
+    return static_cast<u16>((Crc & 0xffff) ^ (Crc >> 16));
+  } else {
+    u16 Checksum = computeBSDChecksum(static_cast<u16>(Seed & 0xffff), Value);
+    for (uptr I = 0; I < ArraySize; I++)
+      Checksum = computeBSDChecksum(Checksum, Array[I]);
+    return Checksum;
+  }
+#endif // defined(__SSE4_2__) || defined(__ARM_FEATURE_CRC32)
+}
+
+namespace Chunk {
+
+enum class Origin : u8 {
+  Malloc = 0,
+  New = 1,
+  NewArray = 2,
+  Memalign = 3,
+};
+
+enum class State : u8 { Available = 0, Allocated = 1, Quarantined = 2 };
+
+typedef u64 PackedHeader;
+// Update the 'Mask' constants to reflect changes in this structure.
+struct UnpackedHeader {
+  u64 Checksum : 16;
+  u64 ClassId : 8;
+  u64 SizeOrUnusedBytes : 20;
+  State State : 2;
+  Origin Origin : 2;
+  u64 Offset : 16;
+};
+typedef atomic_u64 AtomicPackedHeader;
+COMPILER_CHECK(sizeof(UnpackedHeader) == sizeof(PackedHeader));
+
+// Those constants are required to silence some -Werror=conversion errors when
+// assigning values to the related bitfield variables.
+constexpr uptr ChecksumMask = (1UL << 16) - 1;
+constexpr uptr ClassIdMask = (1UL << 8) - 1;
+constexpr uptr SizeOrUnusedBytesMask = (1UL << 20) - 1;
+// constexpr uptr StateMask = (1UL << 2) - 1;  // Currently unused.
+constexpr uptr OriginMask = (1UL << 2) - 1;
+constexpr uptr OffsetMask = (1UL << 16) - 1;
+
+constexpr uptr getHeaderSize() {
+  return roundUpTo(sizeof(PackedHeader), 1U << SCUDO_MIN_ALIGNMENT_LOG);
+}
+
+INLINE AtomicPackedHeader *getAtomicHeader(void *Ptr) {
+  return reinterpret_cast<AtomicPackedHeader *>(reinterpret_cast<uptr>(Ptr) -
+                                                getHeaderSize());
+}
+
+INLINE
+const AtomicPackedHeader *getConstAtomicHeader(const void *Ptr) {
+  return reinterpret_cast<const AtomicPackedHeader *>(
+      reinterpret_cast<uptr>(Ptr) - getHeaderSize());
+}
+
+INLINE void *getBlockBegin(const void *Ptr, UnpackedHeader *Header) {
+  return reinterpret_cast<void *>(reinterpret_cast<uptr>(Ptr) -
+                                  getHeaderSize() -
+                                  (Header->Offset << SCUDO_MIN_ALIGNMENT_LOG));
+}
+
+// We do not need a cryptographically strong hash for the checksum, but a CRC
+// type function that can alert us in the event a header is invalid or
+// corrupted. Ideally slightly better than a simple xor of all fields.
+static INLINE u16 computeHeaderChecksum(u32 Cookie, const void *Ptr,
+                                        UnpackedHeader *Header) {
+  UnpackedHeader ZeroChecksumHeader = *Header;
+  ZeroChecksumHeader.Checksum = 0;
+  uptr HeaderHolder[sizeof(UnpackedHeader) / sizeof(uptr)];
+  memcpy(&HeaderHolder, &ZeroChecksumHeader, sizeof(HeaderHolder));
+  return computeChecksum(Cookie, reinterpret_cast<uptr>(Ptr), HeaderHolder,
+                         ARRAY_SIZE(HeaderHolder));
+}
+
+INLINE void storeHeader(u32 Cookie, void *Ptr,
+                        UnpackedHeader *NewUnpackedHeader) {
+  NewUnpackedHeader->Checksum =
+      computeHeaderChecksum(Cookie, Ptr, NewUnpackedHeader);
+  PackedHeader NewPackedHeader = bit_cast<PackedHeader>(*NewUnpackedHeader);
+  atomic_store_relaxed(getAtomicHeader(Ptr), NewPackedHeader);
+}
+
+INLINE
+void loadHeader(u32 Cookie, const void *Ptr,
+                UnpackedHeader *NewUnpackedHeader) {
+  PackedHeader NewPackedHeader = atomic_load_relaxed(getConstAtomicHeader(Ptr));
+  *NewUnpackedHeader = bit_cast<UnpackedHeader>(NewPackedHeader);
+  if (UNLIKELY(NewUnpackedHeader->Checksum !=
+               computeHeaderChecksum(Cookie, Ptr, NewUnpackedHeader)))
+    reportHeaderCorruption(const_cast<void *>(Ptr));
+}
+
+INLINE void compareExchangeHeader(u32 Cookie, void *Ptr,
+                                  UnpackedHeader *NewUnpackedHeader,
+                                  UnpackedHeader *OldUnpackedHeader) {
+  NewUnpackedHeader->Checksum =
+      computeHeaderChecksum(Cookie, Ptr, NewUnpackedHeader);
+  PackedHeader NewPackedHeader = bit_cast<PackedHeader>(*NewUnpackedHeader);
+  PackedHeader OldPackedHeader = bit_cast<PackedHeader>(*OldUnpackedHeader);
+  if (UNLIKELY(!atomic_compare_exchange_strong(
+          getAtomicHeader(Ptr), &OldPackedHeader, NewPackedHeader,
+          memory_order_relaxed)))
+    reportHeaderRace(Ptr);
+}
+
+INLINE
+bool isValid(u32 Cookie, const void *Ptr, UnpackedHeader *NewUnpackedHeader) {
+  PackedHeader NewPackedHeader = atomic_load_relaxed(getConstAtomicHeader(Ptr));
+  *NewUnpackedHeader = bit_cast<UnpackedHeader>(NewPackedHeader);
+  return NewUnpackedHeader->Checksum ==
+         computeHeaderChecksum(Cookie, Ptr, NewUnpackedHeader);
+}
+
+} // namespace Chunk
+
+} // namespace scudo
+
+#endif // SCUDO_CHUNK_H_

lib/scudo/standalone/tests/CMakeLists.txt

if(COMPILER_RT_HAS_SCUDO_STANDALONE)
     endforeach()
   endif()
 endmacro()
 
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cc
   bytemap_test.cc
   checksum_test.cc
+  chunk_test.cc
   flags_test.cc
   list_test.cc
   map_test.cc
   mutex_test.cc
   quarantine_test.cc
   release_test.cc
   report_test.cc
   secondary_test.cc
   size_class_map_test.cc
   stats_test.cc
   strings_test.cc
   vector_test.cc
   scudo_unit_test_main.cc)
 
 add_scudo_unittest(ScudoUnitTest
   SOURCES ${SCUDO_UNIT_TEST_SOURCES})

lib/scudo/standalone/tests/chunk_test.cc

+//===-- chunk_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 "chunk.h"
+
+#include "gtest/gtest.h"
+
+#include <stdlib.h>
+
+static constexpr scudo::uptr HeaderSize = scudo::Chunk::getHeaderSize();
+static constexpr scudo::u32 Cookie = 0x41424344U;
+static constexpr scudo::u32 InvalidCookie = 0x11223344U;
+
+static void initChecksum(void) {
+  if (&scudo::computeHardwareCRC32 && scudo::hasHardwareCRC32())
+    scudo::HashAlgorithm = scudo::Checksum::HardwareCRC32;
+}
+
+TEST(ScudoChunkTest, ChunkBasic) {
+  initChecksum();
+  const scudo::uptr Size = 0x100U;
+  scudo::Chunk::UnpackedHeader Header = {};
+  void *Block = malloc(HeaderSize + Size);
+  void *P = reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(Block) +
+                                     HeaderSize);
+  scudo::Chunk::storeHeader(Cookie, P, &Header);
+  memset(P, 'A', Size);
+  EXPECT_EQ(scudo::Chunk::getBlockBegin(P, &Header), Block);
+  scudo::Chunk::loadHeader(Cookie, P, &Header);
+  EXPECT_TRUE(scudo::Chunk::isValid(Cookie, P, &Header));
+  EXPECT_FALSE(scudo::Chunk::isValid(InvalidCookie, P, &Header));
+  EXPECT_DEATH(scudo::Chunk::loadHeader(InvalidCookie, P, &Header), "");
+  free(Block);
+}
+
+TEST(ScudoChunkTest, ChunkCmpXchg) {
+  initChecksum();
+  const scudo::uptr Size = 0x100U;
+  scudo::Chunk::UnpackedHeader OldHeader = {};
+  OldHeader.Origin = scudo::Chunk::Origin::Malloc;
+  OldHeader.ClassId = 0x42U;
+  OldHeader.SizeOrUnusedBytes = Size;
+  OldHeader.State = scudo::Chunk::State::Allocated;
+  void *Block = malloc(HeaderSize + Size);
+  void *P = reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(Block) +
+                                     HeaderSize);
+  scudo::Chunk::storeHeader(Cookie, P, &OldHeader);
+  memset(P, 'A', Size);
+  scudo::Chunk::UnpackedHeader NewHeader = OldHeader;
+  NewHeader.State = scudo::Chunk::State::Quarantined;
+  scudo::Chunk::compareExchangeHeader(Cookie, P, &NewHeader, &OldHeader);
+  NewHeader = {};
+  EXPECT_TRUE(scudo::Chunk::isValid(Cookie, P, &NewHeader));
+  EXPECT_EQ(NewHeader.State, scudo::Chunk::State::Quarantined);
+  EXPECT_FALSE(scudo::Chunk::isValid(InvalidCookie, P, &NewHeader));
+  free(Block);
+}
+
+TEST(ScudoChunkTest, CorruptHeader) {
+  initChecksum();
+  const scudo::uptr Size = 0x100U;
+  scudo::Chunk::UnpackedHeader Header = {};
+  void *Block = malloc(HeaderSize + Size);
+  void *P = reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(Block) +
+                                     HeaderSize);
+  scudo::Chunk::storeHeader(Cookie, P, &Header);
+  memset(P, 'A', Size);
+  EXPECT_EQ(scudo::Chunk::getBlockBegin(P, &Header), Block);
+  scudo::Chunk::loadHeader(Cookie, P, &Header);
+  // Simulate a couple of corrupted bits per byte of header data.
+  for (scudo::uptr I = 0; I < sizeof(scudo::Chunk::PackedHeader); I++) {
+    *(reinterpret_cast<scudo::u8 *>(Block) + I) ^= 0x42U;
+    EXPECT_DEATH(scudo::Chunk::loadHeader(Cookie, P, &Header), "");
+    *(reinterpret_cast<scudo::u8 *>(Block) + I) ^= 0x42U;
+  }
+  free(Block);
+}