Add some unit tests for KDAlloc

9 files changed, 750 insertions, 0 deletions

diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt
index 4ee90146..88d5de91 100644
--- a/unittests/CMakeLists.txt
+++ b/unittests/CMakeLists.txt
@@ -235,6 +235,7 @@ endfunction()
 # Unit Tests
 add_subdirectory(Assignment)
 add_subdirectory(Expr)
+add_subdirectory(KDAlloc)
 add_subdirectory(Ref)
 add_subdirectory(Solver)
 add_subdirectory(Searcher)
diff --git a/unittests/KDAlloc/CMakeLists.txt b/unittests/KDAlloc/CMakeLists.txt
new file mode 100644
index 00000000..2bb2ebe8
--- /dev/null
+++ b/unittests/KDAlloc/CMakeLists.txt
@@ -0,0 +1,10 @@
+add_klee_unit_test(KDAllocTest
+  allocate.cpp
+  randomtest.cpp
+  reuse.cpp
+  rusage.cpp
+  sample.cpp
+  stacktest.cpp)
+target_compile_definitions(KDAllocTest PUBLIC "-DKDALLOC_CHECKED" "-DUSE_KDALLOC" "-DUSE_GTEST_INSTEAD_OF_MAIN")
+target_compile_definitions(KDAllocTest PRIVATE ${KLEE_COMPONENT_CXX_DEFINES})
+target_compile_options(KDAllocTest PRIVATE ${KLEE_COMPONENT_CXX_FLAGS})
diff --git a/unittests/KDAlloc/allocate.cpp b/unittests/KDAlloc/allocate.cpp
new file mode 100644
index 00000000..895f8215
--- /dev/null
+++ b/unittests/KDAlloc/allocate.cpp
@@ -0,0 +1,66 @@
+//===-- allocate.cpp ------------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+#include "gtest/gtest.h"
+#endif
+
+#include <cassert>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+int allocate_sample_test() {
+#else
+int main() {
+#endif
+  // initialize a factory and an associated allocator (using the location "0"
+  // gives an OS-assigned location)
+  klee::kdalloc::AllocatorFactory factory(static_cast<std::size_t>(1) << 20, 0);
+  klee::kdalloc::Allocator allocator = factory.makeAllocator();
+
+  std::deque<void *> allocations;
+  for (std::size_t i = 0; i < 10; ++i) {
+    auto p = allocator.allocate(4);
+    allocations.emplace_back(p);
+    std::cout << "Allocated     " << std::right << std::setw(64 / 4) << std::hex
+              << (static_cast<char *>(p) -
+                  static_cast<char *>(factory.getMapping().getBaseAddress()))
+              << "\n";
+  }
+
+  {
+    auto p = allocations[2];
+    allocations.erase(allocations.begin() + 2);
+    std::cout << "Freeing       " << std::right << std::setw(64 / 4) << std::hex
+              << (static_cast<char *>(p) -
+                  static_cast<char *>(factory.getMapping().getBaseAddress()))
+              << "\n";
+    allocator.free(p, 4);
+  }
+
+  for (auto p : allocations) {
+    std::cout << "Freeing       " << std::right << std::setw(64 / 4) << std::hex
+              << (static_cast<char *>(p) -
+                  static_cast<char *>(factory.getMapping().getBaseAddress()))
+              << "\n";
+    allocator.free(p, 4);
+  }
+
+  exit(0);
+}
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+TEST(KDAllocDeathTest, AllocateSample) {
+  ASSERT_EXIT(allocate_sample_test(), ::testing::ExitedWithCode(0), "");
+}
+#endif
diff --git a/unittests/KDAlloc/randomtest.cpp b/unittests/KDAlloc/randomtest.cpp
new file mode 100644
index 00000000..1120ee4e
--- /dev/null
+++ b/unittests/KDAlloc/randomtest.cpp
@@ -0,0 +1,177 @@
+//===-- randomtest.cpp ----------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+#include "xoshiro.h"
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+#include "gtest/gtest.h"
+#endif
+
+#include <cassert>
+#include <chrono>
+#include <cmath>
+#include <cstdint>
+#include <cstdlib>
+#include <iomanip>
+#include <iostream>
+#include <random>
+#include <utility>
+#include <vector>
+
+namespace {
+class RandomTest {
+  xoshiro512 rng;
+
+#if defined(USE_KDALLOC)
+  klee::kdalloc::Allocator allocator;
+#endif
+
+  std::vector<std::pair<void *, std::size_t>> allocations;
+
+  std::geometric_distribution<std::size_t> allocation_bin_distribution;
+  std::geometric_distribution<std::size_t> large_allocation_distribution;
+
+public:
+  std::size_t maximum_concurrent_allocations = 0;
+  std::uint64_t allocation_count = 0;
+  std::uint64_t deallocation_count = 0;
+
+  RandomTest(std::uint64_t seed = 0x31337)
+      : rng(seed)
+#if defined(USE_KDALLOC)
+        ,
+        allocator(klee::kdalloc::AllocatorFactory(
+            static_cast<std::size_t>(1) << 42, 0))
+#endif
+        ,
+        allocation_bin_distribution(0.3),
+        large_allocation_distribution(0.00003) {
+  }
+
+  void run(std::uint64_t const iterations) {
+    std::uniform_int_distribution<std::uint32_t> choice(0, 999);
+    for (std::uint64_t i = 0; i < iterations; ++i) {
+      auto chosen = choice(rng);
+      if (chosen < 650) {
+        ++allocation_count;
+        allocate_sized();
+      } else if (chosen < 700) {
+        ++allocation_count;
+        allocate_large();
+      } else if (chosen < 1000) {
+        ++deallocation_count;
+        deallocate();
+      }
+    }
+    cleanup();
+  }
+
+  void cleanup() {
+    while (!allocations.empty()) {
+      auto choice = std::uniform_int_distribution<std::size_t>(
+          0, allocations.size() - 1)(rng);
+#if defined(USE_KDALLOC)
+      allocator.free(allocations[choice].first, allocations[choice].second);
+#else
+      free(allocations[choice].first);
+#endif
+      allocations[choice] = allocations.back();
+      allocations.pop_back();
+    }
+  }
+
+  void allocate_sized() {
+    auto bin = allocation_bin_distribution(rng);
+    while (bin >= 11) {
+      bin = allocation_bin_distribution(rng);
+    }
+    auto min = (bin == 0 ? 1 : (static_cast<std::size_t>(1) << (bin + 1)) + 1);
+    auto max = static_cast<std::size_t>(1) << (bin + 2);
+    auto size = std::uniform_int_distribution<std::size_t>(min, max)(rng);
+
+#if defined(USE_KDALLOC)
+    allocations.emplace_back(allocator.allocate(size), size);
+#else
+    allocations.emplace_back(std::malloc(size), size);
+#endif
+    if (allocations.size() > maximum_concurrent_allocations) {
+      maximum_concurrent_allocations = allocations.size();
+    }
+  }
+
+  void allocate_large() {
+    auto size = 0;
+    while (size <= 4096 || size > 1073741825) {
+      size = large_allocation_distribution(rng) + 4097;
+    }
+
+#if defined(USE_KDALLOC)
+    allocations.emplace_back(allocator.allocate(size), size);
+#else
+    allocations.emplace_back(std::malloc(size), size);
+#endif
+    if (allocations.size() > maximum_concurrent_allocations) {
+      maximum_concurrent_allocations = allocations.size();
+    }
+  }
+
+  void deallocate() {
+    if (allocations.empty()) {
+      return;
+    }
+    auto choice = std::uniform_int_distribution<std::size_t>(
+        0, allocations.size() - 1)(rng);
+#if defined(USE_KDALLOC)
+    allocator.free(allocations[choice].first, allocations[choice].second);
+#else
+    free(allocations[choice].first);
+#endif
+    allocations[choice] = allocations.back();
+    allocations.pop_back();
+  }
+};
+} // namespace
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+int random_test() {
+#else
+int main() {
+#endif
+#if defined(USE_KDALLOC)
+  std::cout << "Using kdalloc\n";
+#else
+  std::cout << "Using std::malloc\n";
+#endif
+  auto start = std::chrono::steady_clock::now();
+
+  RandomTest tester;
+  tester.run(10'000'000);
+
+  auto stop = std::chrono::steady_clock::now();
+  std::cout << std::dec
+            << std::chrono::duration_cast<std::chrono::milliseconds>(stop -
+                                                                     start)
+                   .count()
+            << " ms\n";
+  std::cout << "\n";
+
+  std::cout << "Allocations: " << tester.allocation_count << "\n";
+  std::cout << "Deallocations: " << tester.deallocation_count << "\n";
+  std::cout << "Maximum concurrent allocations: "
+            << tester.maximum_concurrent_allocations << "\n";
+
+  exit(0);
+}
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+TEST(KDAllocDeathTest, Random) {
+  ASSERT_EXIT(random_test(), ::testing::ExitedWithCode(0), "");
+}
+#endif
diff --git a/unittests/KDAlloc/reuse.cpp b/unittests/KDAlloc/reuse.cpp
new file mode 100644
index 00000000..d886a9d6
--- /dev/null
+++ b/unittests/KDAlloc/reuse.cpp
@@ -0,0 +1,134 @@
+//===-- reuse.cpp ---------------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+#include "gtest/gtest.h"
+#endif
+
+#include <cassert>
+#include <cstddef>
+#include <cstdlib>
+#include <iostream>
+#include <unordered_set>
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+int reuse_test() {
+#else
+int main() {
+#endif
+  {
+    static const std::size_t size = 8;
+    static const std::uint32_t quarantine = 0;
+    std::cout << "size = " << size << " quarantine = " << quarantine << "\n";
+    auto allocator =
+        static_cast<klee::kdalloc::Allocator>(klee::kdalloc::AllocatorFactory(
+            static_cast<std::size_t>(1) << 42, quarantine));
+    auto a = allocator.allocate(size);
+    allocator.free(a, size);
+    auto b = allocator.allocate(size);
+    allocator.free(b, size);
+    auto c = allocator.allocate(size);
+    allocator.free(c, size);
+    auto d = allocator.allocate(size);
+    allocator.free(d, size);
+
+    std::cout << "a: " << a << "\nb: " << b << "\nc: " << c << "\nd: " << d
+              << "\n";
+    assert(a == b);
+    assert(a == c);
+    assert(a == d);
+  }
+
+  std::cout << "\n\n";
+
+  {
+    static const std::size_t size = 8;
+    static const std::uint32_t quarantine = 1;
+    std::cout << "size = " << size << " quarantine = " << quarantine << "\n";
+    auto allocator =
+        static_cast<klee::kdalloc::Allocator>(klee::kdalloc::AllocatorFactory(
+            static_cast<std::size_t>(1) << 42, quarantine));
+    auto a = allocator.allocate(size);
+    allocator.free(a, size);
+    auto b = allocator.allocate(size);
+    allocator.free(b, size);
+    auto c = allocator.allocate(size);
+    allocator.free(c, size);
+    auto d = allocator.allocate(size);
+    allocator.free(d, size);
+
+    std::cout << "a: " << a << "\nb: " << b << "\nc: " << c << "\nd: " << d
+              << "\n";
+    assert(a != b);
+    assert(a == c);
+    assert(b == d);
+  }
+
+  std::cout << "\n\n";
+
+  {
+    static const std::size_t size = 8;
+    static const std::uint32_t quarantine = 2;
+    std::cout << "size = " << size << " quarantine = " << quarantine << "\n";
+    auto allocator =
+        static_cast<klee::kdalloc::Allocator>(klee::kdalloc::AllocatorFactory(
+            static_cast<std::size_t>(1) << 42, quarantine));
+    auto a = allocator.allocate(size);
+    allocator.free(a, size);
+    auto b = allocator.allocate(size);
+    allocator.free(b, size);
+    auto c = allocator.allocate(size);
+    allocator.free(c, size);
+    auto d = allocator.allocate(size);
+    allocator.free(d, size);
+
+    std::cout << "a: " << a << "\nb: " << b << "\nc: " << c << "\nd: " << d
+              << "\n";
+    assert(a != b);
+    assert(a != c);
+    assert(b != c);
+    assert(a == d);
+  }
+
+  std::cout << "\n\n";
+
+  {
+    static const std::size_t size = 8;
+    static const std::uint32_t quarantine =
+        klee::kdalloc::AllocatorFactory::unlimitedQuarantine;
+    std::cout << "size = " << size << " quarantine unlimited\n";
+    auto allocator =
+        static_cast<klee::kdalloc::Allocator>(klee::kdalloc::AllocatorFactory(
+            static_cast<std::size_t>(1) << 42, quarantine));
+
+#if KDALLOC_TRACE >= 2
+    static const std::size_t iterations = 10;
+#else
+    static const std::size_t iterations = 10'000;
+#endif
+    std::unordered_set<void *> allocations;
+    allocations.reserve(iterations);
+    for (std::size_t i = 0; i < iterations; ++i) {
+      auto *ptr = allocator.allocate(size);
+      allocator.free(ptr, 8);
+      auto emplaced = allocations.emplace(ptr);
+      assert(emplaced.second);
+    }
+  }
+
+  std::exit(0);
+}
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+TEST(KDAllocDeathTest, Reuse) {
+  ASSERT_EXIT(reuse_test(), ::testing::ExitedWithCode(0), "");
+}
+#endif
diff --git a/unittests/KDAlloc/rusage.cpp b/unittests/KDAlloc/rusage.cpp
new file mode 100644
index 00000000..fa755b73
--- /dev/null
+++ b/unittests/KDAlloc/rusage.cpp
@@ -0,0 +1,66 @@
+//===-- rusage.cpp --------------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+
+#include "gtest/gtest.h"
+
+#include <deque>
+
+#include <sys/resource.h>
+
+// This test is disabled for asan and msan because they create additional page
+// faults
+#if !defined(__has_feature) ||                                                 \
+    (!__has_feature(memory_sanitizer) && !__has_feature(address_sanitizer))
+
+std::size_t write_to_allocations(std::deque<void *> &allocations) {
+  struct rusage ru;
+  getrusage(RUSAGE_SELF, &ru);
+  auto initial = ru.ru_minflt;
+
+  for (auto p : allocations) {
+    auto pp = static_cast<char *>(p);
+    *pp = 1;
+  }
+
+  getrusage(RUSAGE_SELF, &ru);
+  return ru.ru_minflt - initial;
+}
+
+TEST(KDAllocTest, Rusage) {
+  // initialize a factory and an associated allocator (using the location "0"
+  // gives an OS-assigned location)
+  klee::kdalloc::AllocatorFactory factory(static_cast<std::size_t>(1) << 30,
+                                          0); // 1 GB
+  klee::kdalloc::Allocator allocator = factory.makeAllocator();
+
+  std::deque<void *> allocations;
+  for (std::size_t i = 0; i < 1000; ++i) {
+    auto p = allocator.allocate(16);
+    allocations.emplace_back(p);
+  }
+
+  auto pageFaults = write_to_allocations(allocations);
+
+  ASSERT_GT(pageFaults, static_cast<std::size_t>(0))
+      << "No page faults happened";
+  ASSERT_EQ(pageFaults, allocations.size())
+      << "Number of (minor) page faults and objects differs";
+
+  factory.getMapping().clear();
+
+  // try again: this should (again) trigger a minor page fault for every object
+  auto pageFaultsSecondTry = write_to_allocations(allocations);
+
+  ASSERT_EQ(pageFaults, pageFaultsSecondTry)
+      << "Number of minor page faults in second try differs";
+}
+
+#endif
diff --git a/unittests/KDAlloc/sample.cpp b/unittests/KDAlloc/sample.cpp
new file mode 100644
index 00000000..d4bed00b
--- /dev/null
+++ b/unittests/KDAlloc/sample.cpp
@@ -0,0 +1,68 @@
+//===-- sample.cpp --------------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+#include "gtest/gtest.h"
+#endif
+
+#include <cassert>
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+int sample_test() {
+#else
+int main() {
+#endif
+  // initialize a factory and an associated allocator (using the location "0"
+  // gives an OS-assigned location)
+  klee::kdalloc::AllocatorFactory factory(static_cast<std::size_t>(1) << 40, 0);
+  klee::kdalloc::Allocator allocator = factory.makeAllocator();
+
+  // let us create an integer
+  void *ptr = allocator.allocate(sizeof(int));
+  int *my_int = static_cast<int *>(ptr);
+  *my_int = 42;
+  assert(*my_int == 42 &&
+         "While we can use the addresses, this is not the point of kdalloc");
+
+  {
+    auto allocator2 = factory.makeAllocator();
+    int *my_second_int = static_cast<int *>(allocator2.allocate(sizeof(int)));
+    assert(reinterpret_cast<std::uintptr_t>(my_int) ==
+               reinterpret_cast<std::uintptr_t>(my_second_int) &&
+           "kdalloc is intended to produce reproducible addresses");
+    allocator2.free(my_second_int, sizeof(int));
+    assert(*my_int == 42 &&
+           "The original allocation (from allocator) is still valid");
+  }
+
+  // now let us clone the allocator state
+  {
+    auto allocator2 = allocator;
+    int *my_second_int = static_cast<int *>(allocator2.allocate(sizeof(int)));
+    assert(reinterpret_cast<std::uintptr_t>(my_int) !=
+               reinterpret_cast<std::uintptr_t>(my_second_int) &&
+           "the new address must be different, as allocator2 also contains the "
+           "previous allocation");
+    allocator2.free(my_second_int, sizeof(int));
+    assert(*my_int == 42 &&
+           "The original allocation (from allocator) is still valid");
+  }
+
+  // there is no need to return allocated memory, so we omit
+  // `allocator.free(my_int, sizeof(int));`
+  exit(0);
+}
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+TEST(KDAllocDeathTest, Sample) {
+  ASSERT_EXIT(sample_test(), ::testing::ExitedWithCode(0), "");
+}
+#endif
diff --git a/unittests/KDAlloc/stacktest.cpp b/unittests/KDAlloc/stacktest.cpp
new file mode 100644
index 00000000..2844bf11
--- /dev/null
+++ b/unittests/KDAlloc/stacktest.cpp
@@ -0,0 +1,172 @@
+//===-- stacktest.cpp -----------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "klee/KDAlloc/kdalloc.h"
+#include "xoshiro.h"
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+#include "gtest/gtest.h"
+#endif
+
+#include <cassert>
+#include <chrono>
+#include <cmath>
+#include <cstdint>
+#include <cstdlib>
+#include <iomanip>
+#include <iostream>
+#include <random>
+#include <utility>
+#include <vector>
+
+namespace {
+class RandomTest {
+  xoshiro512 rng;
+
+#if defined(USE_KDALLOC)
+  klee::kdalloc::StackAllocator allocator;
+#endif
+
+  std::vector<std::pair<void *, std::size_t>> allocations;
+
+  std::geometric_distribution<std::size_t> allocation_bin_distribution;
+  std::geometric_distribution<std::size_t> large_allocation_distribution;
+
+public:
+  std::size_t maximum_concurrent_allocations = 0;
+  std::uint64_t allocation_count = 0;
+  std::uint64_t deallocation_count = 0;
+
+  RandomTest(std::mt19937_64::result_type seed = 0x31337)
+      : rng(seed)
+#if defined(USE_KDALLOC)
+        ,
+        allocator(klee::kdalloc::StackAllocatorFactory(
+            static_cast<std::size_t>(1) << 42, 0))
+#endif
+        ,
+        allocation_bin_distribution(0.3),
+        large_allocation_distribution(0.00003) {
+  }
+
+  void run(std::uint64_t const iterations) {
+    allocations.reserve((iterations * 7) / 10);
+    std::uniform_int_distribution<std::uint32_t> choice(0, 999);
+    for (std::uint64_t i = 0; i < iterations; ++i) {
+      auto chosen = choice(rng);
+      if (chosen < 650) {
+        ++allocation_count;
+        allocate_sized();
+      } else if (chosen < 700) {
+        ++allocation_count;
+        allocate_large();
+      } else if (chosen < 1000) {
+        ++deallocation_count;
+        deallocate();
+      }
+    }
+    cleanup();
+  }
+
+  void cleanup() {
+    while (!allocations.empty()) {
+#if defined(USE_KDALLOC)
+      allocator.free(allocations.back().first, allocations.back().second);
+#else
+      free(allocations.back().first);
+#endif
+      allocations.pop_back();
+    }
+  }
+
+  void allocate_sized() {
+    auto bin = allocation_bin_distribution(rng);
+    while (bin >= 11) {
+      bin = allocation_bin_distribution(rng);
+    }
+    auto min = (bin == 0 ? 1 : (static_cast<std::size_t>(1) << (bin + 1)) + 1);
+    auto max = static_cast<std::size_t>(1) << (bin + 2);
+    auto size = std::uniform_int_distribution<std::size_t>(min, max)(rng);
+
+#if defined(USE_KDALLOC)
+    allocations.emplace_back(allocator.allocate(size), size);
+#else
+    allocations.emplace_back(std::malloc(size), size);
+#endif
+    if (allocations.size() > maximum_concurrent_allocations) {
+      maximum_concurrent_allocations = allocations.size();
+    }
+  }
+
+  void allocate_large() {
+    auto size = 0;
+    while (size <= 4096 || size > 1073741825) {
+      size = large_allocation_distribution(rng) + 4097;
+    }
+
+#if defined(USE_KDALLOC)
+    allocations.emplace_back(allocator.allocate(size), size);
+#else
+    allocations.emplace_back(std::malloc(size), size);
+#endif
+    if (allocations.size() > maximum_concurrent_allocations) {
+      maximum_concurrent_allocations = allocations.size();
+    }
+  }
+
+  void deallocate() {
+    if (allocations.empty()) {
+      return;
+    }
+#if defined(USE_KDALLOC)
+    allocator.free(allocations.back().first, allocations.back().second);
+#else
+    free(allocations.back().first);
+#endif
+    allocations.pop_back();
+  }
+};
+} // namespace
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+int stack_test() {
+#else
+int main() {
+#endif
+#if defined(USE_KDALLOC)
+  std::cout << "Using kdalloc\n";
+#else
+  std::cout << "Using std::malloc\n";
+#endif
+  auto start = std::chrono::steady_clock::now();
+
+  RandomTest tester;
+  tester.run(10'000'000);
+
+  auto stop = std::chrono::steady_clock::now();
+  std::cout << std::dec
+            << std::chrono::duration_cast<std::chrono::milliseconds>(stop -
+                                                                     start)
+                   .count()
+            << " ms\n";
+  std::cout << "\n";
+
+  std::cout << "Allocations: " << tester.allocation_count << "\n";
+  std::cout << "Deallocations: " << tester.deallocation_count << "\n";
+  std::cout << "Maximum concurrent allocations: "
+            << tester.maximum_concurrent_allocations << "\n";
+
+  exit(0);
+}
+
+#if defined(USE_GTEST_INSTEAD_OF_MAIN)
+TEST(KDAllocDeathTest, Stack) {
+  ASSERT_EXIT(stack_test(), ::testing::ExitedWithCode(0), "");
+}
+#endif
diff --git a/unittests/KDAlloc/xoshiro.h b/unittests/KDAlloc/xoshiro.h
new file mode 100644
index 00000000..465a83c9
--- /dev/null
+++ b/unittests/KDAlloc/xoshiro.h
@@ -0,0 +1,56 @@
+//===-- xoshiro.h ---------------------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <cstdint>
+
+/// A xoshiro512** generator
+class xoshiro512 {
+  static constexpr const ::std::uint64_t A = 11;
+  static constexpr const ::std::uint64_t B = 21;
+
+  static constexpr const ::std::uint64_t S = 5;
+  static constexpr const ::std::uint64_t R = 7;
+  static constexpr const ::std::uint64_t T = 9;
+
+  ::std::uint64_t s[8] = {0x243F6A8885A308D3u, 0x13198A2E03707344u,
+                          0xA4093822299F31D0u, 0x082EFA98EC4E6C89u,
+                          0x452821E638D01377u, 0xBE5466CF34E90C6Cu,
+                          0xC0AC29B7C97C50DDu, 0x3F84D5B5B5470917u};
+
+public:
+  explicit xoshiro512(std::uint64_t const seed) noexcept {
+    for (auto &x : s) {
+      x ^= seed;
+    }
+  }
+
+  using result_type = std::uint64_t;
+
+  std::uint64_t operator()() noexcept {
+    auto const t = s[1] * S;
+    auto const result = ((t << R) | (t >> (64 - R))) * T;
+    auto const u = s[1] << A;
+    s[2] ^= s[0];
+    s[5] ^= s[1];
+    s[1] ^= s[2];
+    s[7] ^= s[3];
+    s[3] ^= s[4];
+    s[4] ^= s[5];
+    s[0] ^= s[6];
+    s[6] ^= s[7];
+    s[6] ^= u;
+    s[7] = ((s[7] << B) | (s[7] >> (64 - B)));
+    return result;
+  }
+
+  static constexpr ::std::uint64_t(min)() noexcept { return 0; }
+  static constexpr ::std::uint64_t(max)() noexcept {
+    return static_cast<std::uint64_t>(0) - static_cast<std::uint64_t>(1);
+  }
+};