[libc] Add memmove implementation.

[cheng.w]

Summary

Use memcpy rather than copying bytes one by one, for there might be large
size structs to move.

[cheng.w]

Rebase.

[sivachandra]

Sorry for the delay. And yes, you did the right thing, @gchatelet is the best reviewer for this. Overall, this LGTM, but I prefer @gchatelet to approve it.

[gchatelet]

My apologies for the late reply. I've made a bunch of comments.

libc/src/string/memmove.cpp

22

assert(count <= SSIZE_MAX);

@sivachandra I don't remember if we allow asserts in the library?

23

nit: subscript operator is clearer IMHO dest_m[offset] = src_m[offset]

38

Technically the pointer difference type is ptrdiff_t, you may want to rewrite this as:

#include "src/stdlib/abs_utils.h" // __llvm_libc::integer_abs
#include <cstdint> // ptrdiff_t, PTRDIFF_MAX
...
assert(count <= PTRDIFF_MAX);
if (__llvm_libc::integer_abs(src_c - dest_c) >= static_cast<ptrdiff_t>(count))

Also update the comment above.

53–56

The code generated here seems suboptimal and quite large https://godbolt.org/z/fMnfv8.
This can be bad for icache pressure (i.e. calling memmove from time to time will evict precious cache lines from iL1).

That said, we can keep this version for now and optimize later on.

libc/test/src/string/memmove_test.cpp

43

typo

[michaelrj]

libc/src/string/memmove.cpp

26

This line should be LLVM_LIBC_FUNCTION(void *, memmove, (void *dest, const void *src, size_t count)) { since we recently changed the macro that's used for external functions.

[cheng.w]

Address comments.

libc/src/string/memmove.cpp

38

It should be careful with pointer operations and limits. Is assert more like a debug or test macro?

53–56

Yes, it is verbose. Maybe inline asm like cld/std, rep movsb would help. I leave a TODO here.

[gchatelet]

LGTM, can you please wait for @sivachandra answer about using assert in code before submitting? Thx!

libc/src/string/memmove.cpp

31

remove or update

[sivachandra]

In D93195#2492555, @gchatelet wrote:

LGTM, can you please wait for @sivachandra answer about using assert in code before submitting? Thx!

Sorry I missed this earlier. But, I don't see any assert now. Was it removed?

I don't think there is a hard and fast rule about assert but we should try to avoid them in order not to couple parts of the libc. For error conditions, if we align with the standards' requirements and add tests for them, I think that is sufficient.

But of course, if there is real benefit got by using an assert, we can use it.

libc/src/string/memmove.cpp

14

I think you should add a DEPS for this header in the CMake file?

[sivachandra]

libc/src/string/memmove.cpp

15

Newline?

libc/config/linux/aarch64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.labs
     libc.src.stdlib.llabs
 
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmove
     libc.src.string.memset
     libc.src.string.memrchr
     libc.src.string.strcat
     libc.src.string.strchr
     libc.src.string.strcpy
     libc.src.string.strcspn
     libc.src.string.strlen
     libc.src.string.strncpy

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     libc.src.stdlib.labs
     libc.src.stdlib.llabs
 
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memchr
     libc.src.string.memcmp
     libc.src.string.memcpy
+    libc.src.string.memmove
     libc.src.string.memrchr
     libc.src.string.memset
     libc.src.string.strcat
     libc.src.string.strchr
     libc.src.string.strcmp
     libc.src.string.strcpy
     libc.src.string.strcspn
     libc.src.string.strlen

libc/src/string/CMakeLists.txt

add_entrypoint_object(
   memcmp
   SRCS
     memcmp.cpp
   HDRS
     memcmp.h
 )
 
 add_entrypoint_object(
+  memmove
+  SRCS
+    memmove.cpp
+  HDRS
+    memmove.h
+  DEPENDS
+    libc.src.stdlib.abs_utils
+    libc.src.string.memcpy
+)
+
+add_entrypoint_object(
   strchr
   SRCS
     strchr.cpp
   HDRS
     strchr.h
 )
 
 add_entrypoint_object(

libc/src/string/memmove.h

+//===-- Implementation header for memmove -----------------------*- 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 LLVM_LIBC_SRC_STRING_MEMMOVE_H
+#define LLVM_LIBC_SRC_STRING_MEMMOVE_H
+
+#include <stddef.h> // size_t
+
+namespace __llvm_libc {
+
+void *memmove(void *dest, const void *src, size_t count);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMMOVE_H

libc/src/string/memmove.cpp

+//===-- Implementation of memmove -----------------------------------------===//
+//
+// 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 "src/string/memmove.h"
+#include "src/__support/common.h"
+#include "src/stdlib/abs_utils.h"
+#include "src/string/memcpy.h"
+#include <stddef.h> // size_t, ptrdiff_t
+#include <unistd.h> // ssize_t
+
+namespace __llvm_libc {
+
+// src_m and dest_m might be the beginning or end.
+static inline void move_byte(unsigned char *dest_m, const unsigned char *src_m,
+                             size_t count, ssize_t direction) {
+  for (ssize_t offset = 0; count; --count, offset += direction)
+    dest_m[offset] = src_m[offset];
+}
+
+LLVM_LIBC_FUNCTION(void *, memmove,
+                   (void *dest, const void *src, size_t count)) {
+  unsigned char *dest_c = reinterpret_cast<unsigned char *>(dest);
+  const unsigned char *src_c = reinterpret_cast<const unsigned char *>(src);
+
+  // If the distance between src_c and dest_c is equal to or greater
+  // than count (labs(src_c - dest_c) >= count), they would not overlap.
+  // e.g.   greater     equal       overlapping
+  //        [12345678]  [12345678]  [12345678]
+  // src_c: [_ab_____]  [_ab_____]  [_ab_____]
+  // dest_c:[_____yz_]  [___yz___]  [__yz____]
+
+  // Use memcpy if src_c and dest_c do not overlap.
+  if (__llvm_libc::integer_abs(src_c - dest_c) >= static_cast<ptrdiff_t>(count))
+    return __llvm_libc::memcpy(dest_c, src_c, count);
+
+  // Overlap cases.
+  // If dest_c starts before src_c (dest_c < src_c), copy forward(pointer add 1)
+  // from beginning to end.
+  // If dest_c starts after src_c (dest_c > src_c), copy backward(pointer add
+  // -1) from end to beginning.
+  // If dest_c and src_c start at the same address (dest_c == src_c),
+  // just return dest.
+  // e.g.    forward      backward
+  //             *-->        <--*
+  // src_c : [___abcde_]  [_abcde___]
+  // dest_c: [_abc--___]  [___--cde_]
+
+  // TODO: Optimize `move_byte(...)` function.
+  if (dest_c < src_c)
+    move_byte(dest_c, src_c, count, /*pointer add*/ 1);
+  if (dest_c > src_c)
+    move_byte(dest_c + count - 1, src_c + count - 1, count, /*pointer add*/ -1);
+  return dest;
+}
+
+} // namespace __llvm_libc

libc/test/src/string/CMakeLists.txt

SUITE
     libc_string_unittests
   SRCS
     memcmp_test.cpp
   DEPENDS
     libc.src.string.memcmp
 )
 
 add_libc_unittest(
+  memmove_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    memmove_test.cpp
+  DEPENDS
+    libc.src.string.memcmp
+    libc.src.string.memmove
+)
+
+add_libc_unittest(
   strchr_test
   SUITE
     libc_string_unittests
   SRCS
     strchr_test.cpp
   DEPENDS
     libc.src.string.strchr
 )

libc/test/src/string/memmove_test.cpp

+//===-- Unittests for memmove ---------------------------------------------===//
+//
+// 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 "src/string/memcmp.h"
+#include "src/string/memmove.h"
+#include "utils/CPP/ArrayRef.h"
+#include "utils/UnitTest/Test.h"
+
+class MemmoveTest : public __llvm_libc::testing::Test {
+public:
+  void check_memmove(void *dest, const void *src, size_t count, const void *str,
+                     const __llvm_libc::cpp::ArrayRef<unsigned char> expected) {
+    void *result = __llvm_libc::memmove(dest, src, count);
+    // Making sure the pointer returned is same with dest.
+    EXPECT_EQ(result, dest);
+    // expected is designed according to str.
+    // dest and src might be part of str.
+    // Making sure the str is same with expected.
+    EXPECT_EQ(__llvm_libc::memcmp(str, expected.data(), expected.size()), 0);
+  }
+};
+
+TEST_F(MemmoveTest, MoveZeroByte) {
+  unsigned char dest[] = {'a', 'b'};
+  const unsigned char src[] = {'y', 'z'};
+  const unsigned char expected[] = {'a', 'b'};
+  check_memmove(dest, src, 0, dest, expected);
+}
+
+TEST_F(MemmoveTest, OverlapThatDestAndSrcPointToSameAddress) {
+  unsigned char str[] = {'a', 'b'};
+  const unsigned char expected[] = {'a', 'b'};
+  check_memmove(str, str, 1, str, expected);
+}
+
+TEST_F(MemmoveTest, OverlapThatDestStartsBeforeSrc) {
+  // Set boundary at beginning and end for not overstepping when
+  // copy forward or backward.
+  unsigned char str[] = {'z', 'a', 'b', 'c', 'z'};
+  const unsigned char expected[] = {'z', 'b', 'c', 'c', 'z'};
+  // dest is &str[1].
+  check_memmove(&str[1], &str[2], 2, str, expected);
+}
+
+TEST_F(MemmoveTest, OverlapThatDestStartsAfterSrc) {
+  unsigned char str[] = {'z', 'a', 'b', 'c', 'z'};
+  const unsigned char expected[] = {'z', 'a', 'a', 'b', 'z'};
+  check_memmove(&str[2], &str[1], 2, str, expected);
+}
+
+// e.g. dest follow src.
+// str: [abcdefghij]
+//      [__src_____]
+//      [_____dest_]
+TEST_F(MemmoveTest, SrcFollowDest) {
+  unsigned char str[] = {'z', 'a', 'b', 'z'};
+  const unsigned char expected[] = {'z', 'b', 'b', 'z'};
+  check_memmove(&str[1], &str[2], 1, str, expected);
+}
+
+TEST_F(MemmoveTest, DestFollowSrc) {
+  unsigned char str[] = {'z', 'a', 'b', 'z'};
+  const unsigned char expected[] = {'z', 'a', 'a', 'z'};
+  check_memmove(&str[2], &str[1], 1, str, expected);
+}