[libc] add unsafe mode to strlen

[michaelrj]

Summary

The only safe way to implement strlen involves reading the string one
char at a time. It is faster to read in larger blocks, but this leads to
reading beyond the string boundary, which is undefined behavior. This
patch adds an implementation and flag to use this fast but unsafe
version of strlen.

[sivachandra]

libc/src/string/string_utils.h

29

If you know BITS_IN_BYTE, then you as well know the BYTE_MASK. So, why not just use a BYTE_MASK?

93

I think the most appropriate type would be uintptr_t.

[sivachandra]

libc/src/string/CMakeLists.txt

12

I do not think this will do anything at all without a flag applier implemented somewhere. Also, can we consider a design without the FLAGS feature for comparison?

[lntue]

libc/src/string/CMakeLists.txt

12

To make FLAGS property become a compile flag, you'll need to update _get_common_compile_options at https://github.com/llvm/llvm-project/blob/main/libc/cmake/modules/LLVMLibCObjectRules.cmake#L3 similar to FMA_OPT. In your case the compile option to be append should be -DLLVM_LIBC_STRLEN_UNSAFE for gcc/clang and /DLLVM_LIBC_STRLEN_UNSAFE for MSVC.

[tschuett]

libc/src/string/string_utils.h

27

It is set in stone that a byte has 8 bits for all llvm-libc variants? In LLVM there is always somebody with other ideas.

[michaelrj]

address comments and clarify constants

[michaelrj]

libc/src/string/CMakeLists.txt

12

I'm not sure what you mean by "a design without the FLAGS feature", do you mean just having the flag in the code and letting users add it to their build manually?

libc/src/string/string_utils.h

27

Yes. 1 byte is 8 bits is true for all supported platforms.

[sivachandra]

libc/src/string/CMakeLists.txt

12

The setting to use the unsafe path or not has to be done via some config time CMake option. So, there has to be some manual setting somewhere. For most users, we will have a default making the manual setting unnecessary.

By, "a design without the FLAGS feature", I mean that we should provide a CMake option which does not go through the FLAGS machinery.

[michaelrj]

change from using FLAGS to using a full cmake option. Currently it defaults to off, so if we want to test this on the bots then we'll either need to change the default or adjust the cmake command the bots use.

[nickdesaulniers]

In D129808#3660990, @michaelrj wrote:

change from using FLAGS to using a full cmake option. Currently it defaults to off, so if we want to test this on the bots then we'll either need to change the default or adjust the cmake command the bots use.

IIRC, @michaelrj and I had a discussion about how this relates to sanitizers. For LIBC_FAST_UNSAFE_STRLEN could this be the default unless an existing cmake flag is used to build llvm-libc sanitized? (I assume there's an existing cmake flag for denoting that I would like a build of llvm-libc instrumented with *SAN?)

[nickdesaulniers]

libc/src/string/string_utils.h

65

Dunno how similar memchr is to strlen, but I'd bet that the implementations are pretty similar. Maybe the value being searched for could be a parameter, then similar code shared between the two?

[sivachandra]

In D129808#3954947, @nickdesaulniers wrote:

In D129808#3660990, @michaelrj wrote:

change from using FLAGS to using a full cmake option. Currently it defaults to off, so if we want to test this on the bots then we'll either need to change the default or adjust the cmake command the bots use.

IIRC, @michaelrj and I had a discussion about how this relates to sanitizers. For LIBC_FAST_UNSAFE_STRLEN could this be the default unless an existing cmake flag is used to build llvm-libc sanitized? (I assume there's an existing cmake flag for denoting that I would like a build of llvm-libc instrumented with *SAN?)

Reading a word vs reading a byte can be employed at places beyond strlen I think. So, we should probably name the flag more generic like, LIBC_FAST_UNSAFE_WORD_READ. Also, we will want the default behavior to be the opposite. As in, it should be OFF by default and should be switched ON explicitly. There is an LLVM CMake flag for sanitizers - -DLLVM_USE_SANITIZER=<...>. I would think this flag and the unsafe word reading flag should not be mixed.

[michaelrj]

add unsafe version to memchr
move to using just one set of compile flags

[nickdesaulniers]

In D129808#3957855, @michaelrj wrote:

add unsafe version to memchr
move to using just one set of compile flags

Thanks! How about strchr? Looks like there's a TODO about this in libc/src/string/strchr.cpp?

For fun, can we do anything like this for strrchr? (We're on to the point of diminishing returns here; I only truly care about strlen here).

In D129808#3955420, @sivachandra wrote:

Also, we will want the default behavior to be the opposite. As in, it should be OFF by default and should be switched ON explicitly.

So slower by default? :( Not my circus, not my monkeys; but I'll take an implementation over no implementation.

libc/CMakeLists.txt

29

is strlen here still precise after Diff 478668?

libc/src/string/string_utils.h

92

What requested size? I don't follow what this comment means. Can you expand on it, inline?

140

Is n the "requested size"? If so, care to break out the crayons and be super explicit in the comment?

[tschuett]

Do you have numbers that unsafe is faster than safe?

[michaelrj]

minor optimization

[sivachandra]

libc/CMakeLists.txt

29

Move the listing of such tuning parameters to a separate file, say common_tuners.cmake and include it here. When we have tuners specific to certain functions, for example printf related tuners, they will be listed next to the printf implementation as they will not affect LIBC_COMPILER_OPTIONS_DEFAULT.

libc/src/string/string_utils.h

65

Nit: compare with \0.

92

This comment is not addressed yet.

99

Nit: Using the typename Word instead of T improves the readability.

121

"find the match in the block" ?

142

ch_mask is a local var of another function. Can you rephrase this comment so that it will not go stale when the other function changes?

144

Same as above - not sure what this comment is talking about.

[michaelrj]

address comments

[michaelrj]

Re tschuett: Performance numbers here: https://quick-bench.com/q/Z7wq6I3K6xUIeAIogIpHpPgBwSw but the TL;DR is that once strings get larger than about 32 bytes it's faster to read a block at a time, and if the string can't be assumed to be word-aligned then it's faster to work with 32 bits (on x64 machines). I've adjusted the code to account for this.

Re nickdesaulniers: I think strchr and strrchr will have to wait for a followup patch, this patch is getting rather large as it is. As for slower by default, yes but it's also less likely to cause issues (e.g. with sanitizers, memory tagging, etc.).

Re sivachandra: I've set up the cmake to enforce wide strlen NAND sanitizers.

[sivachandra]

OK after addressing the comments which are mostly nits.

libc/cmake/modules/LLVMLibCCommonTuners.cmake

1 ↗

(On Diff #479065)

This file is not a CMake infrastructure component so it should live in the libc directory and can have a simple name like common_libc_tuners.cmake.

7 ↗

(On Diff #479065)

The earlier name of LIBC_UNSAFE_WORD_READ was more suggestive than this name. Also, I think the description should be more generic instead of referring to strlen and memchr.

libc/src/string/string_utils.h

94

s/I/we

153

Nit: I think this unsigned int is to be in sync with the template unsigned int argument. So, define a local type say, using BlockType = unsigned int;.

[michaelrj]

address final comments

libc/cmake/modules/LLVMLibCCommonTuners.cmake

7 ↗

(On Diff #479065)

I compromised on LIBC_STRING_UNSAFE_WIDE_READ which I think has all the relevant information.

libc/CMakeLists.txt

 endif()
 
 # Path libc/scripts directory.
 set(LIBC_BUILD_SCRIPTS_DIR "${LIBC_SOURCE_DIR}/utils/build_scripts")
 
 # Flags to pass down to the compiler while building the libc functions.
 set(LIBC_COMPILE_OPTIONS_DEFAULT "" CACHE STRING "Architecture to tell clang to optimize for (e.g. -march=... or -mcpu=...)")
 
+include(common_libc_tuners.cmake)
+
+list(APPEND LIBC_COMPILE_OPTIONS_DEFAULT ${LIBC_COMMON_TUNE_OPTIONS})
+
 # Check --print-resource-dir to find the compiler resource dir if this flag
 # is supported by the compiler.
 execute_process(
   OUTPUT_STRIP_TRAILING_WHITESPACE
   COMMAND ${CMAKE_CXX_COMPILER} --print-resource-dir
   RESULT_VARIABLE COMMAND_RETURN_CODE
   OUTPUT_VARIABLE COMPILER_RESOURCE_DIR
 )

libc/common_libc_tuners.cmake

+# ------------------------------------------------------------------------------
+# Common tuning option definitions.
+# ------------------------------------------------------------------------------
+
+set(LIBC_COMMON_TUNE_OPTIONS "")
+
+option(LIBC_UNSAFE_STRING_WIDE_READ "Functions searching for the first character in a string such as strlen will read the string as int sized blocks instead of bytes. This relies on undefined behavior and may fail on some systems, but improves performance on long strings." OFF)
+if(LIBC_UNSAFE_STRING_WIDE_READ)
+  if(LLVM_USE_SANITIZER)
+    message(FATAL_ERROR "LIBC_UNSAFE_STRING_WIDE_READ is set at the same time as a sanitizer. LIBC_UNSAFE_STRING_WIDE_READ causes strlen and memchr to read beyond the end of their target strings, which is undefined behavior caught by sanitizers.")
+  else()
+    list(APPEND LIBC_COMMON_TUNE_OPTIONS "-DLIBC_UNSAFE_STRING_WIDE_READ")
+    endif()
+endif()

libc/src/string/CMakeLists.txt

 add_subdirectory(memory_utils)
 
 add_header_library(
   string_utils
   HDRS
     string_utils.h
   DEPENDS
     libc.include.stdlib
     libc.src.__support.CPP.bitset
     .memory_utils.memcpy_implementation
     .memory_utils.bzero_implementation
 )
 
 add_header_library(
   allocating_string_utils
   HDRS
     allocating_string_utils.h
   DEPENDS
     libc.include.stdlib
     .memory_utils.memcpy_implementation

 
 add_entrypoint_object(
   strlen
   SRCS
     strlen.cpp
   HDRS
     strlen.h
   DEPENDS
+    .string_utils
     libc.include.string
 )
 
 add_entrypoint_object(
   strncat
   SRCS
     strncat.cpp
   HDRS

libc/src/string/string_utils.h

 #include "src/__support/common.h"
 #include "src/string/memory_utils/bzero_implementations.h"
 #include "src/string/memory_utils/memcpy_implementations.h"
 #include <stddef.h> // For size_t
 
 namespace __llvm_libc {
 namespace internal {
 
-// Returns the length of a string, denoted by the first occurrence
-// of a null terminator.
-static inline size_t string_length(const char *src) {
+template <typename Word> constexpr Word repeat_byte(Word byte) {
+  constexpr size_t BITS_IN_BYTE = 8;
+  constexpr size_t BYTE_MASK = 0xff;
+  Word result = 0;
+  byte = byte & BYTE_MASK;
+  for (size_t i = 0; i < sizeof(Word); ++i)
+    result = (result << BITS_IN_BYTE) | byte;
+  return result;
+}
+
+// The goal of this function is to take in a block of arbitrary size and return
+// if it has any bytes equal to zero without branching. This is done by
+// transforming the block such that zero bytes become non-zero and non-zero
+// bytes become zero.
+// The first transformation relies on the properties of carrying in arithmetic
+// subtraction. Specifically, if 0x01 is subtracted from a byte that is 0x00,
+// then the result for that byte must be equal to 0xff (or 0xfe if the next byte
+// needs a carry as well).
+// The next transformation is a simple mask. All zero bytes will have the high
+// bit set after the subtraction, so each byte is masked with 0x80. This narrows
+// the set of bytes that result in a non-zero value to only zero bytes and bytes
+// with the high bit and any other bit set.
+// The final transformation masks the result of the previous transformations
+// with the inverse of the original byte. This means that any byte that had the
+// high bit set will no longer have it set, narrowing the list of bytes which
+// result in non-zero values to just the zero byte.
+template <typename Word> constexpr bool has_zeroes(Word block) {
+  constexpr Word LOW_BITS = repeat_byte<Word>(0x01);
+  constexpr Word HIGH_BITS = repeat_byte<Word>(0x80);
+  Word subtracted = block - LOW_BITS;
+  Word inverted = ~block;
+  return (subtracted & inverted & HIGH_BITS) != 0;
+}
+
+template <typename Word>
+static inline size_t string_length_wide_read(const char *src) {
+  const char *char_ptr = src;
+  // Step 1: read 1 byte at a time to align to block size
+  for (; reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0;
+       ++char_ptr) {
+    if (*char_ptr == '\0')
+      return char_ptr - src;
+  }
+  // Step 2: read blocks
+  for (const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);
+       !has_zeroes<Word>(*block_ptr); ++block_ptr) {
+    char_ptr = reinterpret_cast<const char *>(block_ptr);
+  }
+  // Step 3: find the zero in the block
+  for (; *char_ptr != '\0'; ++char_ptr) {
+    ;
+  }
+  return char_ptr - src;
+}
+
+static inline size_t string_length_byte_read(const char *src) {
   size_t length;
   for (length = 0; *src; ++src, ++length)
     ;
   return length;
 }
 
-// Returns the first occurrence of 'ch' within the first 'n' characters of
-// 'src'. If 'ch' is not found, returns nullptr.
-static inline void *find_first_character(const unsigned char *src,
+// Returns the length of a string, denoted by the first occurrence
+// of a null terminator.
+static inline size_t string_length(const char *src) {
+#ifdef LIBC_UNSAFE_STRING_WIDE_READ
+  // Unsigned int is the default size for most processors, and on x86-64 it
+  // performs better than larger sizes when the src pointer can't be assumed to
+  // be aligned to a word boundary, so it's the size we use for reading the
+  // string a block at a time.
+  return string_length_wide_read<unsigned int>(src);
+#else
+  return string_length_byte_read(src);
+#endif
+}
+
+template <typename Word>
+static inline void *find_first_character_wide_read(const unsigned char *src,
+                                                   unsigned char ch, size_t n) {
+  const unsigned char *char_ptr = src;
+  size_t cur = 0;
+
+  // Step 1: read 1 byte at a time to align to block size
+  for (; reinterpret_cast<uintptr_t>(char_ptr) % sizeof(Word) != 0 && cur < n;
+       ++char_ptr, ++cur) {
+    if (*char_ptr == ch)
+      return const_cast<unsigned char *>(char_ptr);
+  }
+
+  const Word ch_mask = repeat_byte<Word>(ch);
+
+  // Step 2: read blocks
+  for (const Word *block_ptr = reinterpret_cast<const Word *>(char_ptr);
+       !has_zeroes<Word>((*block_ptr) ^ ch_mask) && cur < n;
+       ++block_ptr, cur += sizeof(Word)) {
+    char_ptr = reinterpret_cast<const unsigned char *>(block_ptr);
+  }
+
+  // Step 3: find the match in the block
+  for (; *char_ptr != ch && cur < n; ++char_ptr, ++cur) {
+    ;
+  }
+
+  if (*char_ptr != ch || cur >= n)
+    return static_cast<void *>(nullptr);
+
+  return const_cast<unsigned char *>(char_ptr);
+}
+
+static inline void *find_first_character_byte_read(const unsigned char *src,
                                                    unsigned char ch, size_t n) {
   for (; n && *src != ch; --n, ++src)
     ;
   return n ? const_cast<unsigned char *>(src) : nullptr;
 }
 
+// Returns the first occurrence of 'ch' within the first 'n' characters of
+// 'src'. If 'ch' is not found, returns nullptr.
+static inline void *find_first_character(const unsigned char *src,
+                                         unsigned char ch, size_t max_strlen) {
+#ifdef LIBC_UNSAFE_STRING_WIDE_READ
+  // If the maximum size of the string is small, the overhead of aligning to a
+  // word boundary and generating a bitmask of the appropriate size may be
+  // greater than the gains from reading larger chunks. Based on some testing,
+  // the crossover point between when it's faster to just read bytewise and read
+  // blocks is somewhere between 16 and 32, so 4 times the size of the block
+  // should be in that range.
+  // Unsigned int is used for the same reason as in strlen.
+  using BlockType = unsigned int;
+  if (max_strlen > (sizeof(BlockType) * 4)) {
+    return find_first_character_wide_read<BlockType>(src, ch, max_strlen);
+  }
+#endif
+  return find_first_character_byte_read(src, ch, max_strlen);
+}
+
 // Returns the maximum length span that contains only characters not found in
 // 'segment'. If no characters are found, returns the length of 'src'.
 static inline size_t complementary_span(const char *src, const char *segment) {
   const char *initial = src;
   cpp::bitset<256> bitset;
 
   for (; *segment; ++segment)
     bitset.set(*segment);