[libc][test] Drastically reduce mem test runtime

[gchatelet]

• fixed a double increment

[gchatelet]

• diff against origin/main

[gchatelet]

Thx for the review Tue!

libc/test/src/string/bcmp_test.cpp

 }
 
 TEST(LlvmLibcBcmpTest, LhsAfterRhsLexically) {
   const char *lhs = "ac";
   const char *rhs = "ab";
   ASSERT_NE(__llvm_libc::bcmp(lhs, rhs, 2), 0);
 }
 
-// Adapt CheckBcmp signature to op implementation signatures.
-template <auto FnImpl>
-int CmpAdaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
-  return FnImpl(p1.begin(), p2.begin(), size);
+// Adapt CheckBcmp signature to bcmp.
+static inline int Adaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
+  return __llvm_libc::bcmp(p1.begin(), p2.begin(), size);
 }
 
 TEST(LlvmLibcBcmpTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CmpAdaptor<__llvm_libc::bcmp>;
+  static constexpr size_t kMaxSize = 400;
   Buffer Buffer1(kMaxSize);
   Buffer Buffer2(kMaxSize);
   Randomize(Buffer1.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto span1 = Buffer1.span().subspan(0, size);
     auto span2 = Buffer2.span().subspan(0, size);
-    const bool OK = CheckBcmp<Impl>(span1, span2, size);
+    const bool OK = CheckBcmp<Adaptor>(span1, span2, size);
     if (!OK)
       testing::tlog << "Failed at size=" << size << '\n';
     ASSERT_TRUE(OK);
   }
 }
 
 } // namespace __llvm_libc

libc/test/src/string/bcopy_test.cpp

 #include "memory_utils/memory_check_utils.h"
 #include "src/__support/CPP/span.h"
 #include "test/UnitTest/MemoryMatcher.h"
 #include "test/UnitTest/Test.h"
 
 using __llvm_libc::cpp::array;
 using __llvm_libc::cpp::span;
 
+namespace __llvm_libc {
+
 TEST(LlvmLibcBcopyTest, MoveZeroByte) {
   char Buffer[] = {'a', 'b', 'y', 'z'};
   const char Expected[] = {'a', 'b', 'y', 'z'};
   void *const Dst = Buffer;
   __llvm_libc::bcopy(Buffer + 2, Dst, 0);
   ASSERT_MEM_EQ(Buffer, Expected);
 }
 

 TEST(LlvmLibcBcopyTest, DstFollowSrc) {
   char Buffer[] = {'z', 'a', 'b', 'z'};
   const char Expected[] = {'z', 'a', 'a', 'z'};
   void *const Dst = Buffer + 2;
   __llvm_libc::bcopy(Buffer + 1, Dst, 1);
   ASSERT_MEM_EQ(Buffer, Expected);
 }
 
-static constexpr int kMaxSize = 512;
+// Adapt CheckMemmove signature to bcopy.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::bcopy(src.begin(), dst.begin(), size);
+}
 
 TEST(LlvmLibcBcopyTest, SizeSweep) {
-  using LargeBuffer = array<char, 3 * kMaxSize>;
-  LargeBuffer GroundTruth;
-  __llvm_libc::Randomize(GroundTruth);
-  for (int Size = 0; Size < kMaxSize; ++Size) {
-    for (int Offset = -Size; Offset < Size; ++Offset) {
-      LargeBuffer Buffer = GroundTruth;
-      LargeBuffer Expected = GroundTruth;
-      size_t DstOffset = kMaxSize;
-      size_t SrcOffset = kMaxSize + Offset;
-      for (int I = 0; I < Size; ++I)
-        Expected[DstOffset + I] = GroundTruth[SrcOffset + I];
-      void *const Dst = Buffer.data() + DstOffset;
-      __llvm_libc::bcopy(Buffer.data() + SrcOffset, Dst, Size);
-      ASSERT_MEM_EQ(Buffer, Expected);
-    }
+  static constexpr int kMaxSize = 400;
+  static constexpr int kDenseOverlap = 15;
+  using LargeBuffer = array<char, 2 * kMaxSize + 1>;
+  LargeBuffer Buffer;
+  Randomize(Buffer);
+  for (int Size = 0; Size < kMaxSize; ++Size)
+    for (int Overlap = -1; Overlap < Size;) {
+      ASSERT_TRUE(CheckMemmove<Adaptor>(Buffer, Size, Overlap));
+      // Prevent quadratic behavior by skipping offset above kDenseOverlap.
+      if (Overlap > kDenseOverlap)
+        Overlap *= 2;
+      else
+        ++Overlap;
     }
 }
+
+} // namespace __llvm_libc

libc/test/src/string/bzero_test.cpp

 //===-- Unittests for bzero -----------------------------------------------===//
 //
 // 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 "memory_utils/memory_check_utils.h"
 #include "src/string/bzero.h"
 #include "test/UnitTest/Test.h"
 
 namespace __llvm_libc {
 
-// Adapt CheckMemset signature to op implementation signatures.
-template <auto FnImpl>
-void BzeroAdaptor(cpp::span<char> p1, uint8_t value, size_t size) {
-  FnImpl(p1.begin(), size);
+// Adapt CheckMemset signature to bzero.
+static inline void Adaptor(cpp::span<char> p1, uint8_t value, size_t size) {
+  __llvm_libc::bzero(p1.begin(), size);
 }
 
 TEST(LlvmLibcBzeroTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = BzeroAdaptor<__llvm_libc::bzero>;
+  static constexpr size_t kMaxSize = 400;
   Buffer DstBuffer(kMaxSize);
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE((CheckMemset<Impl>(dst, 0, size)));
+    ASSERT_TRUE((CheckMemset<Adaptor>(dst, 0, size)));
   }
 }
 
 } // namespace __llvm_libc

libc/test/src/string/memcmp_test.cpp

 }
 
 TEST(LlvmLibcMemcmpTest, LhsAfterRhsLexically) {
   const char *lhs = "az";
   const char *rhs = "ab";
   EXPECT_GT(__llvm_libc::memcmp(lhs, rhs, 2), 0);
 }
 
-// Adapt CheckMemcmp signature to op implementation signatures.
-template <auto FnImpl>
-int CmpAdaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
-  return FnImpl(p1.begin(), p2.begin(), size);
+// Adapt CheckMemcmp signature to memcmp.
+static inline int Adaptor(cpp::span<char> p1, cpp::span<char> p2, size_t size) {
+  return __llvm_libc::memcmp(p1.begin(), p2.begin(), size);
 }
 
 TEST(LlvmLibcMemcmpTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CmpAdaptor<__llvm_libc::memcmp>;
+  static constexpr size_t kMaxSize = 400;
   Buffer Buffer1(kMaxSize);
   Buffer Buffer2(kMaxSize);
   Randomize(Buffer1.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto span1 = Buffer1.span().subspan(0, size);
     auto span2 = Buffer2.span().subspan(0, size);
-    const bool OK = CheckMemcmp<Impl>(span1, span2, size);
+    const bool OK = CheckMemcmp<Adaptor>(span1, span2, size);
     if (!OK)
       testing::tlog << "Failed at size=" << size << '\n';
     ASSERT_TRUE(OK);
   }
 }
 
 } // namespace __llvm_libc

libc/test/src/string/memcpy_test.cpp

 //===-- Unittests for memcpy ----------------------------------------------===//
 //
 // 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 "memory_utils/memory_check_utils.h"
 #include "src/string/memcpy.h"
 #include "test/UnitTest/Test.h"
 
 namespace __llvm_libc {
 
-// Adapt CheckMemcpy signature to op implementation signatures.
-template <auto FnImpl>
-void CopyAdaptor(cpp::span<char> dst, cpp::span<char> src, size_t size) {
-  FnImpl(dst.begin(), src.begin(), size);
+// Adapt CheckMemcpy signature to memcpy.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::memcpy(dst.begin(), src.begin(), size);
 }
 
 TEST(LlvmLibcMemcpyTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = CopyAdaptor<__llvm_libc::memcpy>;
+  static constexpr size_t kMaxSize = 400;
   Buffer SrcBuffer(kMaxSize);
   Buffer DstBuffer(kMaxSize);
   Randomize(SrcBuffer.span());
   for (size_t size = 0; size < kMaxSize; ++size) {
     auto src = SrcBuffer.span().subspan(0, size);
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE(CheckMemcpy<Impl>(dst, src, size));
+    ASSERT_TRUE(CheckMemcpy<Adaptor>(dst, src, size));
   }
 }
 
 } // namespace __llvm_libc

libc/test/src/string/memmove_test.cpp

 #include "memory_utils/memory_check_utils.h"
 #include "src/__support/CPP/span.h"
 #include "test/UnitTest/MemoryMatcher.h"
 #include "test/UnitTest/Test.h"
 
 using __llvm_libc::cpp::array;
 using __llvm_libc::cpp::span;
 
+namespace __llvm_libc {
+
 TEST(LlvmLibcMemmoveTest, MoveZeroByte) {
   char Buffer[] = {'a', 'b', 'y', 'z'};
   const char Expected[] = {'a', 'b', 'y', 'z'};
   void *const Dst = Buffer;
   void *const Ret = __llvm_libc::memmove(Dst, Buffer + 2, 0);
   EXPECT_EQ(Ret, Dst);
   ASSERT_MEM_EQ(Buffer, Expected);
 }
TEST(LlvmLibcMemmoveTest, DstFollowSrc) {
   char Buffer[] = {'z', 'a', 'b', 'z'};
   const char Expected[] = {'z', 'a', 'a', 'z'};
   void *const Dst = Buffer + 2;
   void *const Ret = __llvm_libc::memmove(Dst, Buffer + 1, 1);
   EXPECT_EQ(Ret, Dst);
   ASSERT_MEM_EQ(Buffer, Expected);
 }
 
-static constexpr int kMaxSize = 512;
+// Adapt CheckMemmove signature to op implementation signatures.
+static inline void Adaptor(cpp::span<char> dst, cpp::span<char> src,
+                           size_t size) {
+  __llvm_libc::memmove(dst.begin(), src.begin(), size);
+}
 
 TEST(LlvmLibcMemmoveTest, SizeSweep) {
-  using LargeBuffer = array<char, 3 * kMaxSize>;
-  LargeBuffer GroundTruth;
-  __llvm_libc::Randomize(GroundTruth);
-  for (int Size = 0; Size < kMaxSize; ++Size) {
-    for (int Offset = -Size; Offset < Size; ++Offset) {
-      LargeBuffer Buffer = GroundTruth;
-      LargeBuffer Expected = GroundTruth;
-      size_t DstOffset = kMaxSize;
-      size_t SrcOffset = kMaxSize + Offset;
-      for (int I = 0; I < Size; ++I)
-        Expected[DstOffset + I] = GroundTruth[SrcOffset + I];
-      void *const Dst = Buffer.data() + DstOffset;
-      void *const Ret =
-          __llvm_libc::memmove(Dst, Buffer.data() + SrcOffset, Size);
-      EXPECT_EQ(Ret, Dst);
-      ASSERT_MEM_EQ(Buffer, Expected);
-    }
+  static constexpr int kMaxSize = 400;
+  static constexpr int kDenseOverlap = 15;
+  using LargeBuffer = array<char, 2 * kMaxSize + 1>;
+  LargeBuffer Buffer;
+  Randomize(Buffer);
+  for (int Size = 0; Size < kMaxSize; ++Size)
+    for (int Overlap = -1; Overlap < Size;) {
+      ASSERT_TRUE(CheckMemmove<Adaptor>(Buffer, Size, Overlap));
+      // Prevent quadratic behavior by skipping offset above kDenseOverlap.
+      if (Overlap > kDenseOverlap)
+        Overlap *= 2;
+      else
+        ++Overlap;
     }
 }
+
+} // namespace __llvm_libc

libc/test/src/string/memory_utils/memory_check_utils.h

 //===-- Utils to test conformance of mem functions ------------------------===//
 //
 // 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 LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H
 #define LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H
 
 #include "src/__support/CPP/span.h"
+#include "src/__support/libc_assert.h"
 #include "src/__support/macros/sanitizer.h"
 #include "src/string/memory_utils/utils.h"
 #include <stddef.h> // size_t
 #include <stdint.h> // uintxx_t
 #include <stdlib.h> // malloc/free
 
 namespace __llvm_libc {
 

 
 // Copy one span to another.
 static inline void ReferenceCopy(cpp::span<char> dst,
                                  const cpp::span<char> src) {
   for (size_t i = 0; i < dst.size(); ++i)
     dst[i] = src[i];
 }
 
+static inline bool IsEqual(const cpp::span<char> a, const cpp::span<char> b) {
+  LIBC_ASSERT(a.size() == b.size());
+  for (size_t i = 0; i < a.size(); ++i)
+    if (a[i] != b[i])
+      return false;
+  return true;
+}
+
 // Checks that FnImpl implements the memcpy semantic.
 template <auto FnImpl>
 bool CheckMemcpy(cpp::span<char> dst, cpp::span<char> src, size_t size) {
   Randomize(dst);
   FnImpl(dst, src, size);
-  for (size_t i = 0; i < size; ++i)
-    if (dst[i] != src[i])
-      return false;
-  return true;
+  return IsEqual(dst, src);
 }
 
 // Checks that FnImpl implements the memset semantic.
 template <auto FnImpl>
 bool CheckMemset(cpp::span<char> dst, uint8_t value, size_t size) {
   Randomize(dst);
   FnImpl(dst, value, size);
   for (char c : dst)
if (ground_truth > 0) {
       if (int cmp = FnImpl(span2, span1, size); cmp <= 0)
         return false;
     }
     --span2[i];
   }
   return true;
 }
 
-// TODO: Also implement the memmove semantic
+uint16_t Checksum(cpp::span<char> dst) {
+  // We use Fletcher16 as it is trivial to implement.
+  uint16_t sum1 = 0;
+  uint16_t sum2 = 0;
+  for (char c : dst) {
+    sum1 = (sum1 + c) % 255U;
+    sum2 = (sum2 + sum1) % 255U;
+  }
+  return (sum2 << 8) | sum1;
+}
+
+template <auto FnImpl>
+bool CheckMemmove(cpp::span<char> dst, cpp::span<char> src) {
+  LIBC_ASSERT(dst.size() == src.size());
+  // Memmove can override the src buffer. Technically we should save it into a
+  // temporary buffer so we can check that 'dst' is equal to what 'src' was
+  // before we called the function. To save on allocation and copy we use a
+  // checksum instead.
+  const auto src_checksum = Checksum(src);
+  FnImpl(dst, src, dst.size());
+  return Checksum(dst) == src_checksum;
+}
+
+// Checks that FnImpl implements the memmove semantic.
+//  - Buffer size should be greater than 2 * size + 1.
+//  - Overlap refers to the number of bytes in common between the two buffers:
+//    - Negative means buffers are disjoint
+//    - zero mean they overlap exactly
+//  - Caller is responsible for randomizing the buffer.
+template <auto FnImpl>
+bool CheckMemmove(cpp::span<char> buffer, size_t size, int overlap) {
+  LIBC_ASSERT(buffer.size() > (2 * size + 1));
+  const size_t half_size = buffer.size() / 2;
+  LIBC_ASSERT((size_t)(overlap >= 0 ? overlap : -overlap) < half_size);
+  cpp::span<char> head = buffer.first(half_size + overlap).last(size);
+  cpp::span<char> tail = buffer.last(half_size).first(size);
+  LIBC_ASSERT(head.size() == size);
+  LIBC_ASSERT(tail.size() == size);
+  // dst before src
+  if (!CheckMemmove<FnImpl>(head, tail))
+    return false;
+  // dst after src
+  if (!CheckMemmove<FnImpl>(tail, head))
+    return false;
+  return true;
+}
 
 } // namespace __llvm_libc
 
 #endif // LIBC_TEST_SRC_STRING_MEMORY_UTILS_MEMORY_CHECK_UTILS_H

libc/test/src/string/memset_test.cpp

 //===-- Unittests for memset ----------------------------------------------===//
 //
 // 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 "memory_utils/memory_check_utils.h"
 #include "src/string/memset.h"
 #include "test/UnitTest/Test.h"
 
 namespace __llvm_libc {
 
-// Adapt CheckMemset signature to op implementation signatures.
-template <auto FnImpl>
-void SetAdaptor(cpp::span<char> p1, uint8_t value, size_t size) {
-  FnImpl(p1.begin(), value, size);
+// Adapt CheckMemset signature to memset.
+static inline void Adaptor(cpp::span<char> p1, uint8_t value, size_t size) {
+  __llvm_libc::memset(p1.begin(), value, size);
 }
 
 TEST(LlvmLibcMemsetTest, SizeSweep) {
-  static constexpr size_t kMaxSize = 1024;
-  static constexpr auto Impl = SetAdaptor<__llvm_libc::memset>;
+  static constexpr size_t kMaxSize = 400;
   Buffer DstBuffer(kMaxSize);
   for (size_t size = 0; size < kMaxSize; ++size) {
     const char value = size % 10;
     auto dst = DstBuffer.span().subspan(0, size);
-    ASSERT_TRUE((CheckMemset<Impl>(dst, value, size)));
+    ASSERT_TRUE((CheckMemset<Adaptor>(dst, value, size)));
   }
 }
 
 } // namespace __llvm_libc

utils/bazel/llvm-project-overlay/libc/test/src/string/BUILD.bazel

libc_test(
     ],
 )
 
 cc_library(
     name = "memory_check_utils",
     hdrs = ["memory_utils/memory_check_utils.h"],
     deps = [
         "//libc:__support_cpp_span",
+        "//libc:__support_libc_assert",
         "//libc:__support_macros_sanitizer",
         "//libc:string_memory_utils",
     ],
 )
 
 libc_test(
     name = "memcpy_test",
     srcs = ["memcpy_test.cpp"],