This is an archive of the discontinued LLVM Phabricator instance.

[libc] add unsafe mode to strlen
ClosedPublic

Authored by michaelrj on Jul 14 2022, 3:21 PM.

Details

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.

Diff Detail

Event Timeline

michaelrj created this revision.Jul 14 2022, 3:21 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptJul 14 2022, 3:21 PM
michaelrj requested review of this revision.Jul 14 2022, 3:21 PM
sivachandra added inline comments.Jul 15 2022, 12:54 AM
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 added inline comments.Jul 15 2022, 1:08 AM
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 added inline comments.Jul 15 2022, 6:18 AM
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 added inline comments.Jul 15 2022, 9:35 AM
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 marked 3 inline comments as done.

address comments and clarify constants

michaelrj added inline comments.Jul 15 2022, 11:29 AM
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 added inline comments.Jul 15 2022, 11:37 AM
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 updated this revision to Diff 445626.Jul 18 2022, 2:23 PM

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.

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?)

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 added a comment.EditedNov 28 2022, 3:33 PM

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.

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

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).

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?

Do you have numbers that unsafe is faster than safe?

minor optimization

sivachandra added inline comments.Nov 29 2022, 3:43 PM
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 updated this revision to Diff 479065.Nov 30 2022, 1:57 PM
michaelrj marked 14 inline comments as done.

address comments

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.

dxf added a subscriber: dxf.Nov 30 2022, 2:02 PM
sivachandra accepted this revision.Nov 30 2022, 3:40 PM

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;.

This revision is now accepted and ready to land.Nov 30 2022, 3:40 PM
michaelrj updated this revision to Diff 479101.Nov 30 2022, 4:44 PM
michaelrj marked 4 inline comments as done.

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.

This revision was landed with ongoing or failed builds.Nov 30 2022, 4:48 PM
This revision was automatically updated to reflect the committed changes.