[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

30

enum class ChunkState : u8 {

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

};

39

can you use your enums here instead of u64

42

why it uses u64 for 2bit fields?

58

does this have to be inline?

69

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

[cryptoad]

lib/scudo/standalone/chunk.h

42

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.

58

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.

69

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

69

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

69

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/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 {
+
+enum AllocType : u8 {
+  FromMalloc = 0,
+  FromNew = 1,
+  FromNewArray = 2,
+  FromMemalign = 3,
+};
+
+enum ChunkState : u8 {
+  ChunkAvailable = 0,
+  ChunkAllocated = 1,
+  ChunkQuarantine = 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;
+  u64 State : 2;
+  u64 AllocType : 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 AllocTypeMask = (1UL << 2) - 1;
+constexpr uptr OffsetMask = (1UL << 16) - 1;
+
+extern atomic_u8 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 (atomic_load_relaxed(&HashAlgorithm) == 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 {
+
+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;
+
+TEST(ScudoChunkTest, ChunkBasic) {
+  const scudo::uptr Size = 0x100U;
+  scudo::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) {
+  const scudo::uptr Size = 0x100U;
+  scudo::UnpackedHeader OldHeader = {};
+  OldHeader.AllocType = scudo::FromMalloc;
+  OldHeader.ClassId = 0x42U;
+  OldHeader.SizeOrUnusedBytes = Size;
+  OldHeader.State = scudo::ChunkAllocated;
+  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::UnpackedHeader NewHeader = OldHeader;
+  NewHeader.State = scudo::ChunkQuarantine;
+  scudo::Chunk::compareExchangeHeader(Cookie, P, &NewHeader, &OldHeader);
+  NewHeader = {};
+  EXPECT_TRUE(scudo::Chunk::isValid(Cookie, P, &NewHeader));
+  EXPECT_EQ(NewHeader.State, scudo::ChunkQuarantine);
+  EXPECT_FALSE(scudo::Chunk::isValid(InvalidCookie, P, &NewHeader));
+  free(Block);
+}
+
+TEST(ScudoChunkTest, CorruptHeader) {
+  const scudo::uptr Size = 0x100U;
+  scudo::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::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);
+}