[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

24

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

86

I think the most appropriate type would be uintptr_t.

[sivachandra]

libc/src/string/CMakeLists.txt

11

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

11

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

22

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

11

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

22

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

[sivachandra]

libc/src/string/CMakeLists.txt

11

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

60

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

36 ↗

(On Diff #478668)

is strlen here still precise after Diff 478668?

libc/src/string/string_utils.h

85

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

99

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

36 ↗

(On Diff #478695)

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

60

Nit: compare with \0.

85

This comment is not addressed yet.

92

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

101

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?

103

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

114

"find the match in the block" ?

[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

101

s/I/we

112

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/src/string/CMakeLists.txt

 add_subdirectory(memory_utils)
 
 add_header_library(
   string_utils
   HDRS
     string_utils.h
   DEPENDS
     libc.src.__support.CPP.bitset
     .memory_utils.memcpy_implementation
     .memory_utils.memset_implementation
+  FLAGS
+    LLVM_LIBC_STRLEN_UNSAFE
 )
 
 add_entrypoint_object(
   memccpy
   SRCS
     memccpy.cpp
   HDRS
     memccpy.h

 
 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/memcpy_implementations.h"
 #include "src/string/memory_utils/memset_implementations.h"
 #include <stddef.h> // 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 T> constexpr T repeat_byte(T byte) {
+  constexpr size_t BITS_IN_BYTE = 8;
+  T result = 0;
+  byte = byte & ((1 << BITS_IN_BYTE) - 1);
+  for (size_t i = 0; i < sizeof(T); ++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 T> constexpr bool has_zeroes(T block) {
+  constexpr T LOW_BITS = repeat_byte<T>(0x01);
+  constexpr T HIGH_BITS = repeat_byte<T>(0x80);
+  T subtracted = block - LOW_BITS;
+  T inverted = ~block;
+  return (subtracted & inverted & HIGH_BITS) != 0;
+}
+
+template <typename T>
+static inline size_t string_length_unsafe(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(T) != 0; ++char_ptr) {
+    if (*char_ptr == 0)
+      return char_ptr - src;
+  }
+  // Step 2: read blocks
+  for (const T *block_ptr = reinterpret_cast<const T *>(char_ptr);
+       !has_zeroes<T>(*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_safe(const char *src) {
   size_t length;
   for (length = 0; *src; ++src, ++length)
     ;
   return length;
 }
 
+// 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 LLVM_LIBC_STRLEN_UNSAFE
+  // TODO: pick size of var based on requested size.
+  return string_length_unsafe<size_t>(src);
+#else
+  return string_length_safe(src);
+#endif
+}
+
 // 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 n) {
   for (; n && *src != ch; --n, ++src)
     ;
   return n ? const_cast<unsigned char *>(src) : nullptr;
 }
 
 // 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);
   for (; *src && !bitset.test(*src); ++src)
     ;
   return src - initial;
 }
 
 // Given the similarities between strtok and strtok_r, we can implement both
 // using a utility function. On the first call, 'src' is scanned for the
 // first character not found in 'delimiter_string'. Once found, it scans until
 // the first character in the 'delimiter_string' or the null terminator is
 // found. We define this span as a token. The end of the token is appended with
 // a null terminator, and the token is returned. The point where the last token
 // is found is then stored within 'context' for subsequent calls. Subsequent
 // calls will use 'context' when a nullptr is passed in for 'src'. Once the null
 // terminating character is reached, returns a nullptr.