[scudo] Initial standalone skeleton check-in

Summary:
This is the initial check-in for the Standalone version of Scudo.

The project is initially going to live in scudo/standalone then will
replace scudo. See http://lists.llvm.org/pipermail/llvm-dev/2019-January/129113.html
for details.

This initial CL is meant to lay out the project structure, of both
code & tests, providing a minimal amount of functionalities, namely
various definitions, some atomic helpers and an intrusive list.
(empty.cc is just here to have a compilation unit, but will go away
in the upcoming CLs).

Initial support is restricted to Linux i386 & x86_64 in make files
and will be extended once things land & work.

We will grow organically from here, adding functionalities in limited
amounts.

Reviewers: morehouse, eugenis, vitalybuka, kcc, mcgrathr, flowerhack

Reviewed By: morehouse, vitalybuka

Subscribers: srhines, mgorny, krytarowski, delcypher, jfb, #sanitizers, llvm-commits

Tags: #llvm, #sanitizers

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

llvm-svn: 353055

4 files changed, 361 insertions, 0 deletions

diff --git a/compiler-rt/lib/scudo/standalone/tests/CMakeLists.txt b/compiler-rt/lib/scudo/standalone/tests/CMakeLists.txt
new file mode 100644
index 00000000000..93938136103
--- /dev/null
+++ b/compiler-rt/lib/scudo/standalone/tests/CMakeLists.txt
@@ -0,0 +1,50 @@
+include_directories(..)
+
+add_custom_target(ScudoUnitTests)
+set_target_properties(ScudoUnitTests PROPERTIES
+  FOLDER "Compiler-RT Tests")
+
+set(SCUDO_UNITTEST_CFLAGS
+  ${COMPILER_RT_UNITTEST_CFLAGS}
+  ${COMPILER_RT_GTEST_CFLAGS}
+  -I${COMPILER_RT_SOURCE_DIR}/include
+  -I${COMPILER_RT_SOURCE_DIR}/lib
+  -I${COMPILER_RT_SOURCE_DIR}/lib/scudo/standalone
+  -DGTEST_HAS_RTTI=0)
+
+set(SCUDO_TEST_ARCH ${SCUDO_SUPPORTED_ARCH})
+
+# gtests requires c++
+set(LINK_FLAGS -lstdc++ -pthread)
+
+set(TEST_HEADERS)
+foreach (header ${SCUDO_HEADERS})
+  list(APPEND TEST_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}/../${header})
+endforeach()
+
+# add_scudo_unittest(<name>
+#                   SOURCES <sources list>
+#                   HEADERS <extra headers list>)
+macro(add_scudo_unittest testname)
+  cmake_parse_arguments(TEST "" "" "SOURCES;HEADERS" ${ARGN})
+  if(COMPILER_RT_HAS_SCUDO_STANDALONE)
+    foreach(arch ${SCUDO_TEST_ARCH})
+      set(ScudoUnitTestsObjects)
+      generate_compiler_rt_tests(ScudoUnitTestsObjects ScudoUnitTests
+        "${testname}-${arch}-Test" ${arch}
+        SOURCES ${TEST_SOURCES} ${COMPILER_RT_GTEST_SOURCE} 
+        COMPILE_DEPS ${TEST_HEADERS}
+        DEPS gtest scudo_standalone
+        CFLAGS ${SCUDO_UNITTEST_CFLAGS}
+        LINK_FLAGS ${LINK_FLAGS})
+    endforeach()
+  endif()
+endmacro()
+
+set(SCUDO_UNIT_TEST_SOURCES
+  atomic_test.cc
+  list_test.cc
+  scudo_unit_test_main.cc)
+
+add_scudo_unittest(ScudoUnitTest
+  SOURCES ${SCUDO_UNIT_TEST_SOURCES})
diff --git a/compiler-rt/lib/scudo/standalone/tests/atomic_test.cc b/compiler-rt/lib/scudo/standalone/tests/atomic_test.cc
new file mode 100644
index 00000000000..0ef0fa7512b
--- /dev/null
+++ b/compiler-rt/lib/scudo/standalone/tests/atomic_test.cc
@@ -0,0 +1,112 @@
+//===-- atomic_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 "scudo/standalone/atomic_helpers.h"
+#include "gtest/gtest.h"
+
+namespace scudo {
+
+template <typename T> struct ValAndMagic {
+  typename T::Type Magic0;
+  T A;
+  typename T::Type Magic1;
+
+  static ValAndMagic<T> *Sink;
+};
+
+template <typename T> ValAndMagic<T> *ValAndMagic<T>::Sink;
+
+template <typename T, memory_order LoadMO, memory_order StoreMO>
+void checkStoreLoad() {
+  typedef typename T::Type Type;
+  ValAndMagic<T> Val;
+  // Prevent the compiler from scalarizing the struct.
+  ValAndMagic<T>::Sink = &Val;
+  // Ensure that surrounding memory is not overwritten.
+  Val.Magic0 = Val.Magic1 = (Type)-3;
+  for (u64 I = 0; I < 100; I++) {
+    // Generate A value that occupies all bytes of the variable.
+    u64 V = I;
+    V |= V << 8;
+    V |= V << 16;
+    V |= V << 32;
+    Val.A.ValDoNotUse = (Type)V;
+    EXPECT_EQ(atomic_load(&Val.A, LoadMO), (Type)V);
+    Val.A.ValDoNotUse = (Type)-1;
+    atomic_store(&Val.A, (Type)V, StoreMO);
+    EXPECT_EQ(Val.A.ValDoNotUse, (Type)V);
+  }
+  EXPECT_EQ(Val.Magic0, (Type)-3);
+  EXPECT_EQ(Val.Magic1, (Type)-3);
+}
+
+TEST(ScudoStandalone, AtomicStoreLoad) {
+  checkStoreLoad<atomic_u8, memory_order_relaxed, memory_order_relaxed>();
+  checkStoreLoad<atomic_u8, memory_order_consume, memory_order_relaxed>();
+  checkStoreLoad<atomic_u8, memory_order_acquire, memory_order_relaxed>();
+  checkStoreLoad<atomic_u8, memory_order_relaxed, memory_order_release>();
+  checkStoreLoad<atomic_u8, memory_order_seq_cst, memory_order_seq_cst>();
+
+  checkStoreLoad<atomic_u16, memory_order_relaxed, memory_order_relaxed>();
+  checkStoreLoad<atomic_u16, memory_order_consume, memory_order_relaxed>();
+  checkStoreLoad<atomic_u16, memory_order_acquire, memory_order_relaxed>();
+  checkStoreLoad<atomic_u16, memory_order_relaxed, memory_order_release>();
+  checkStoreLoad<atomic_u16, memory_order_seq_cst, memory_order_seq_cst>();
+
+  checkStoreLoad<atomic_u32, memory_order_relaxed, memory_order_relaxed>();
+  checkStoreLoad<atomic_u32, memory_order_consume, memory_order_relaxed>();
+  checkStoreLoad<atomic_u32, memory_order_acquire, memory_order_relaxed>();
+  checkStoreLoad<atomic_u32, memory_order_relaxed, memory_order_release>();
+  checkStoreLoad<atomic_u32, memory_order_seq_cst, memory_order_seq_cst>();
+
+  checkStoreLoad<atomic_u64, memory_order_relaxed, memory_order_relaxed>();
+  checkStoreLoad<atomic_u64, memory_order_consume, memory_order_relaxed>();
+  checkStoreLoad<atomic_u64, memory_order_acquire, memory_order_relaxed>();
+  checkStoreLoad<atomic_u64, memory_order_relaxed, memory_order_release>();
+  checkStoreLoad<atomic_u64, memory_order_seq_cst, memory_order_seq_cst>();
+
+  checkStoreLoad<atomic_uptr, memory_order_relaxed, memory_order_relaxed>();
+  checkStoreLoad<atomic_uptr, memory_order_consume, memory_order_relaxed>();
+  checkStoreLoad<atomic_uptr, memory_order_acquire, memory_order_relaxed>();
+  checkStoreLoad<atomic_uptr, memory_order_relaxed, memory_order_release>();
+  checkStoreLoad<atomic_uptr, memory_order_seq_cst, memory_order_seq_cst>();
+}
+
+template <typename T> void checkAtomicCompareExchange() {
+  typedef typename T::Type Type;
+  {
+    Type OldVal = 42;
+    Type NewVal = 24;
+    Type V = OldVal;
+    EXPECT_TRUE(atomic_compare_exchange_strong(
+        reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed));
+    EXPECT_FALSE(atomic_compare_exchange_strong(
+        reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed));
+    EXPECT_EQ(NewVal, OldVal);
+  }
+  {
+    Type OldVal = 42;
+    Type NewVal = 24;
+    Type V = OldVal;
+    EXPECT_TRUE(atomic_compare_exchange_weak(reinterpret_cast<T *>(&V), &OldVal,
+                                             NewVal, memory_order_relaxed));
+    EXPECT_FALSE(atomic_compare_exchange_weak(
+        reinterpret_cast<T *>(&V), &OldVal, NewVal, memory_order_relaxed));
+    EXPECT_EQ(NewVal, OldVal);
+  }
+}
+
+TEST(ScudoStandalone, AtomicCompareExchangeTest) {
+  checkAtomicCompareExchange<atomic_u8>();
+  checkAtomicCompareExchange<atomic_u16>();
+  checkAtomicCompareExchange<atomic_u32>();
+  checkAtomicCompareExchange<atomic_u64>();
+  checkAtomicCompareExchange<atomic_uptr>();
+}
+
+} // namespace scudo
diff --git a/compiler-rt/lib/scudo/standalone/tests/list_test.cc b/compiler-rt/lib/scudo/standalone/tests/list_test.cc
new file mode 100644
index 00000000000..bf3d71fa150
--- /dev/null
+++ b/compiler-rt/lib/scudo/standalone/tests/list_test.cc
@@ -0,0 +1,185 @@
+//===-- list_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 "scudo/standalone/list.h"
+#include "gtest/gtest.h"
+
+struct ListItem {
+  ListItem *Next;
+};
+
+typedef scudo::IntrusiveList<ListItem> List;
+
+static List StaticList;
+
+static void setList(List *L, ListItem *X = nullptr, ListItem *Y = nullptr,
+                    ListItem *Z = nullptr) {
+  L->clear();
+  if (X)
+    L->push_back(X);
+  if (Y)
+    L->push_back(Y);
+  if (Z)
+    L->push_back(Z);
+}
+
+static void checkList(List *L, ListItem *I1, ListItem *I2 = nullptr,
+                      ListItem *I3 = nullptr, ListItem *I4 = nullptr,
+                      ListItem *I5 = nullptr, ListItem *I6 = nullptr) {
+  if (I1) {
+    EXPECT_EQ(L->front(), I1);
+    L->pop_front();
+  }
+  if (I2) {
+    EXPECT_EQ(L->front(), I2);
+    L->pop_front();
+  }
+  if (I3) {
+    EXPECT_EQ(L->front(), I3);
+    L->pop_front();
+  }
+  if (I4) {
+    EXPECT_EQ(L->front(), I4);
+    L->pop_front();
+  }
+  if (I5) {
+    EXPECT_EQ(L->front(), I5);
+    L->pop_front();
+  }
+  if (I6) {
+    EXPECT_EQ(L->front(), I6);
+    L->pop_front();
+  }
+  EXPECT_TRUE(L->empty());
+}
+
+TEST(ScudoSandalone, IntrusiveList) {
+  ListItem Items[6];
+  EXPECT_EQ(StaticList.size(), 0U);
+
+  List L;
+  L.clear();
+
+  ListItem *X = &Items[0];
+  ListItem *Y = &Items[1];
+  ListItem *Z = &Items[2];
+  ListItem *A = &Items[3];
+  ListItem *B = &Items[4];
+  ListItem *C = &Items[5];
+
+  EXPECT_EQ(L.size(), 0U);
+  L.push_back(X);
+  EXPECT_EQ(L.size(), 1U);
+  EXPECT_EQ(L.back(), X);
+  EXPECT_EQ(L.front(), X);
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
+  L.checkConsistency();
+
+  L.push_front(X);
+  EXPECT_EQ(L.size(), 1U);
+  EXPECT_EQ(L.back(), X);
+  EXPECT_EQ(L.front(), X);
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
+  L.checkConsistency();
+
+  L.push_front(X);
+  L.push_front(Y);
+  L.push_front(Z);
+  EXPECT_EQ(L.size(), 3U);
+  EXPECT_EQ(L.front(), Z);
+  EXPECT_EQ(L.back(), X);
+  L.checkConsistency();
+
+  L.pop_front();
+  EXPECT_EQ(L.size(), 2U);
+  EXPECT_EQ(L.front(), Y);
+  EXPECT_EQ(L.back(), X);
+  L.pop_front();
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
+  L.checkConsistency();
+
+  L.push_back(X);
+  L.push_back(Y);
+  L.push_back(Z);
+  EXPECT_EQ(L.size(), 3U);
+  EXPECT_EQ(L.front(), X);
+  EXPECT_EQ(L.back(), Z);
+  L.checkConsistency();
+
+  L.pop_front();
+  EXPECT_EQ(L.size(), 2U);
+  EXPECT_EQ(L.front(), Y);
+  EXPECT_EQ(L.back(), Z);
+  L.pop_front();
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
+  L.checkConsistency();
+
+  L.push_back(X);
+  L.push_back(Y);
+  L.push_back(Z);
+  L.extract(X, Y);
+  EXPECT_EQ(L.size(), 2U);
+  EXPECT_EQ(L.front(), X);
+  EXPECT_EQ(L.back(), Z);
+  L.checkConsistency();
+  L.extract(X, Z);
+  EXPECT_EQ(L.size(), 1U);
+  EXPECT_EQ(L.front(), X);
+  EXPECT_EQ(L.back(), X);
+  L.checkConsistency();
+  L.pop_front();
+  EXPECT_TRUE(L.empty());
+
+  List L1, L2;
+  L1.clear();
+  L2.clear();
+
+  L1.append_front(&L2);
+  EXPECT_TRUE(L1.empty());
+  EXPECT_TRUE(L2.empty());
+
+  L1.append_back(&L2);
+  EXPECT_TRUE(L1.empty());
+  EXPECT_TRUE(L2.empty());
+
+  setList(&L1, X);
+  checkList(&L1, X);
+
+  setList(&L1, X, Y, Z);
+  setList(&L2, A, B, C);
+  L1.append_back(&L2);
+  checkList(&L1, X, Y, Z, A, B, C);
+  EXPECT_TRUE(L2.empty());
+
+  setList(&L1, X, Y);
+  setList(&L2);
+  L1.append_front(&L2);
+  checkList(&L1, X, Y);
+  EXPECT_TRUE(L2.empty());
+}
+
+TEST(ScudoStandalone, IntrusiveListAppendEmpty) {
+  ListItem I;
+  List L;
+  L.clear();
+  L.push_back(&I);
+  List L2;
+  L2.clear();
+  L.append_back(&L2);
+  EXPECT_EQ(L.back(), &I);
+  EXPECT_EQ(L.front(), &I);
+  EXPECT_EQ(L.size(), 1U);
+  L.append_front(&L2);
+  EXPECT_EQ(L.back(), &I);
+  EXPECT_EQ(L.front(), &I);
+  EXPECT_EQ(L.size(), 1U);
+}
diff --git a/compiler-rt/lib/scudo/standalone/tests/scudo_unit_test_main.cc b/compiler-rt/lib/scudo/standalone/tests/scudo_unit_test_main.cc
new file mode 100644
index 00000000000..16398e5da7e
--- /dev/null
+++ b/compiler-rt/lib/scudo/standalone/tests/scudo_unit_test_main.cc
@@ -0,0 +1,14 @@
+//===-- scudo_unit_test_main.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 "gtest/gtest.h"
+
+int main(int argc, char **argv) {
+  testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}