Skip to contentSkip to conversation

string.h: Add str_has_prefix() helper function

PATCH In review Steven Rostedt 3 participants 15 messages Dec 22, 2018 – Jan 11, 2019 Generic string library

lore
Share & tools
lore
#0 lore raw

PATCH v4 1/1 string.h: Add str_has_prefix() helper function

From: "Steven Rostedt (VMware)" <[email protected]>

A discussion came up in the trace triggers thread about converting a bunch of:

strncmp(str, "const", sizeof("const") - 1)

use cases into a helper macro. It started with:

strncmp(str, const, sizeof(const) - 1)

But then Joe Perches mentioned that if a const is not used, the sizeof() will be the size of a pointer, which can be bad. And that gcc will optimize strlen("const") into "sizeof("const") - 1".

Thinking about this more, a quick grep in the kernel tree found several (thousands!) of cases that use this construct. A quick grep also revealed that there's probably several bugs in that use case. Some are that people forgot the "- 1" (which I found) and others could be that the constant for the sizeof is different than the constant (although, I haven't found any of those, but I also didn't look hard).

I figured the best thing to do is to create a helper macro and place it into include/linux/string.h. And go around and fix all the open coded versions of it later.

Note, gcc appears to optimize this when we make it into an always_inline static function, which removes a lot of issues that a macro produces.

---

Since I haven't heard anything since Linus said he preferred the len to be the return value, I'm posting this last version before running it through my tests.

Changes since v3:

- Use size_t instead of int (Joe Perches)

 include/linux/string.h | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)
include/linux/string.h +20 -0
index 27d0482e5e05..7927b875f80c 100644
@@ -456,4 +456,24 @@ static inline void memcpy_and_pad(void *dest, size_t dest_len,
 		memcpy(dest, src, dest_len);
 }
 
+/**
+ * str_has_prefix - Test if a string has a given prefix
+ * @str: The string to test
+ * @prefix: The string to see if @str starts with
+ *
+ * A common way to test a prefix of a string is to do:
+ *  strncmp(str, prefix, sizeof(prefix) - 1)
+ *
+ * But this can lead to bugs due to typos, or if prefix is a pointer
+ * and not a constant. Instead use str_has_prefix().
+ *
+ * Returns: 0 if @str does not start with @prefix
+         strlen(@prefix) if @str does start with @prefix
+ */
+static __always_inline size_t str_has_prefix(const char *str, const char *prefix)
+{
+	size_t len = strlen(prefix);
+	return strncmp(str, prefix, len) == 0 ? len : 0;
+}
+
 #endif /* _LINUX_STRING_H_ */
Signature · 1 line
2.19.1
#1 lore raw
Quoted 69 lines · Steven Rostedt

From: "Steven Rostedt (VMware)" <[email protected]>

A discussion came up in the trace triggers thread about converting a bunch of:

strncmp(str, "const", sizeof("const") - 1)

use cases into a helper macro. It started with:

strncmp(str, const, sizeof(const) - 1)

But then Joe Perches mentioned that if a const is not used, the sizeof() will be the size of a pointer, which can be bad. And that gcc will optimize strlen("const") into "sizeof("const") - 1".

Thinking about this more, a quick grep in the kernel tree found several (thousands!) of cases that use this construct. A quick grep also revealed that there's probably several bugs in that use case. Some are that people forgot the "- 1" (which I found) and others could be that the constant for the sizeof is different than the constant (although, I haven't found any of those, but I also didn't look hard).

I figured the best thing to do is to create a helper macro and place it into include/linux/string.h. And go around and fix all the open coded versions of it later.

Note, gcc appears to optimize this when we make it into an always_inline static function, which removes a lot of issues that a macro produces.

---

Since I haven't heard anything since Linus said he preferred the len to be the return value, I'm posting this last version before running it through my tests.

Changes since v3:

- Use size_t instead of int (Joe Perches)

 include/linux/string.h | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)
include/linux/string.h +8 -0
index 27d0482e5e05..7927b875f80c 100644
@@ -456,4 +456,24 @@ static inline void memcpy_and_pad(void *dest, size_t dest_len,
 		memcpy(dest, src, dest_len);
 }
 
+/**
+ * str_has_prefix - Test if a string has a given prefix
+ * @str: The string to test
+ * @prefix: The string to see if @str starts with
+ *
+ * A common way to test a prefix of a string is to do:
+ *  strncmp(str, prefix, sizeof(prefix) - 1)
+ *

include/linux/string.h static inline void memcpy_and_pad(void *dest, size_t dest_len, · line 476

Quoted 10 lines
include/linux/string.h +10 -0
+ * But this can lead to bugs due to typos, or if prefix is a pointer
+ * and not a constant. Instead use str_has_prefix().
+ *
+ * Returns: 0 if @str does not start with @prefix
+         strlen(@prefix) if @str does start with @prefix
+ */
+static __always_inline size_t str_has_prefix(const char *str, const char *prefix)
+{
+	size_t len = strlen(prefix);
+	return strncmp(str, prefix, len) == 0 ? len : 0;

As it already knows the length (and it needs to use it for return value), isn't it (slightly) better using memcmp() instead?

Thanks,
Namhyung

Quoted 6 lines
include/linux/string.h +2 -0
+}
+
 #endif /* _LINUX_STRING_H_ */
Signature · 1 line
2.19.1
#2 lore raw
Quoted 7 lines · On Sat, 22 Dec 2018 18:33:46 +0900 Namhyung Kim <[email protected]> wrote:

include/linux/string.h static inline void memcpy_and_pad(void *dest, size_t dest_len, · line 476

Quoted 4 lines
include/linux/string.h +4 -0
+static __always_inline size_t str_has_prefix(const char *str, const char *prefix)
+{
+	size_t len = strlen(prefix);
+	return strncmp(str, prefix, len) == 0 ? len : 0;  

As it already knows the length (and it needs to use it for return value), isn't it (slightly) better using memcmp() instead?

No, because we don't know the length of str.

	[ str = "h\0[bad memory]" ]


	str_has_prefix(str, "TEST THIS BIG STRING AT FRONT")

If we use memcmp(), then we are testing way after str has ended, and that can cause a memory fault.

-- Steve

#3 lore raw
Quoted 14 lines · Steven Rostedt
Quoted 7 lines · On Sat, 22 Dec 2018 18:33:46 +0900 Namhyung Kim <[email protected]> wrote:

include/linux/string.h static inline void memcpy_and_pad(void *dest, size_t dest_len, · line 476

Quoted 4 lines
include/linux/string.h +4 -0
+static __always_inline size_t str_has_prefix(const char *str, const char *prefix)
+{
+	size_t len = strlen(prefix);
+	return strncmp(str, prefix, len) == 0 ? len : 0;  

As it already knows the length (and it needs to use it for return value), isn't it (slightly) better using memcmp() instead?

No, because we don't know the length of str.

Quoted 8 lines
	[ str = "h\0[bad memory]" ]


	str_has_prefix(str, "TEST THIS BIG STRING AT FRONT")

If we use memcmp(), then we are testing way after str has ended, and that can cause a memory fault.

I don't know what's the bad memory causing memory fault but anyway memcpy() should stop at the NUL character first as it's different, no?

Thanks,
Namhyung

#4 lore raw
Quoted 6 lines · On Sat, 22 Dec 2018 23:24:11 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 6 lines

No, because we don't know the length of str.

	[ str = "h\0[bad memory]" ]
Quoted 8 lines
Quoted 5 lines

str_has_prefix(str, "TEST THIS BIG STRING AT FRONT")

If we use memcmp(), then we are testing way after str has ended, and that can cause a memory fault.

I don't know what's the bad memory causing memory fault but anyway memcpy() should stop at the NUL character first as it's different, no?

No, that's the difference between memcpy() and strncpy(), memcpy() doesn't care about nul characters. It's copying memory not strings.

-- Steve

#5 lore raw
Quoted 11 lines · On Sat, 22 Dec 2018 10:12:44 -0500 Steven Rostedt <[email protected]> wrote:
Quoted 8 lines · On Sat, 22 Dec 2018 23:24:11 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 4 lines

No, because we don't know the length of str.

	[ str = "h\0[bad memory]" ]

I don't know what's the bad memory causing memory fault but anyway

What I meant by that is if a string is allocated at a end of a page, and the next page is marked as not present. A read into that page will cause a page fault, and since memcmp() does not stop at the '\0' it will read into that not-present memory and trigger a fault, and that read wont be in the exception table, and it will then BUG.

Quoted 4 lines
Quoted 1 line

memcpy() should stop at the NUL character first as it's different, no?

No, that's the difference between memcpy() and strncpy(), memcpy() doesn't care about nul characters. It's copying memory not strings.

I think we both meant s/cpy/cmp/ ;-)

-- Steve

#6 lore raw
Quoted 13 lines · Steven Rostedt
Quoted 10 lines · On Sat, 22 Dec 2018 10:12:44 -0500 Steven Rostedt <[email protected]> wrote:
Quoted 7 lines · On Sat, 22 Dec 2018 23:24:11 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 4 lines

No, because we don't know the length of str.

	[ str = "h\0[bad memory]" ]
Quoted 7 lines
Quoted 1 line
Quoted 1 line

I don't know what's the bad memory causing memory fault but anyway

What I meant by that is if a string is allocated at a end of a page, and the next page is marked as not present. A read into that page will cause a page fault, and since memcmp() does not stop at the '\0' it will read into that not-present memory and trigger a fault, and that read wont be in the exception table, and it will then BUG.

Why it doesn't stop at the '\0' if one has it and the other doesn't? It's not because it's '\0', it's because they are different. The '\0' should be in the prev page (otherwise it's already a BUG) so it should be detected and stopped before going to next page IMHO.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

memcpy() should stop at the NUL character first as it's different, no?

No, that's the difference between memcpy() and strncpy(), memcpy() doesn't care about nul characters. It's copying memory not strings.

I think we both meant s/cpy/cmp/ ;-)

Sure.. sorry about that.

I know the difference between memcpy() and strcpy(). But this is comparing so it should stop.

Thanks,
Namhyung

#7 lore raw
Quoted 11 lines · On Sun, 23 Dec 2018 01:46:05 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 5 lines

What I meant by that is if a string is allocated at a end of a page, and the next page is marked as not present. A read into that page will cause a page fault, and since memcmp() does not stop at the '\0' it will read into that not-present memory and trigger a fault, and that read wont be in the exception table, and it will then BUG.

Why it doesn't stop at the '\0' if one has it and the other doesn't? It's not because it's '\0', it's because they are different. The '\0' should be in the prev page (otherwise it's already a BUG) so it should be detected and stopped before going to next page IMHO.

Because memcmp() isn't required to test byte by byte. In fact, most implementations don't which is why memcmp is faster than strcncmp.

It can be checking in 8 byte chunks or more (although perhaps not likely). Perhaps there's an arch command that lets you compare 32 bytes at a time, if the size passed to memcmp is 32 or more, the implementation is allowed to read both src and dst of 32 bytes at a time. If there was a '\0' followed by not present memory, you will still get that fault.

-- Steve

#8 lore raw
Quoted 2 lines · On Sat, 22 Dec 2018 12:19:11 -0500 Steven Rostedt <[email protected]> wrote:

Because memcmp() isn't required to test byte by byte. In fact, most implementations don't which is why memcmp is faster than strcncmp.

In fact, if memcmp() was safe to use if we only knew the size of one of the parameters, then there would be no reason for strncmp to exist.

-- Steve

#9 lore raw
Quoted 9 lines · On Sat, 22 Dec 2018 12:23:35 -0500 Steven Rostedt <[email protected]> wrote:
Quoted 2 lines · On Sat, 22 Dec 2018 12:19:11 -0500 Steven Rostedt <[email protected]> wrote:

Because memcmp() isn't required to test byte by byte. In fact, most implementations don't which is why memcmp is faster than strcncmp.

In fact, if memcmp() was safe to use if we only knew the size of one of the parameters, then there would be no reason for strncmp to exist.

Also, I believe there are some memcmp implementations that start at the end of the memory locations, not the beginning. That is, it compares backwards. Which is also legit for memcmp to do.

-- Steve

#10 lore raw
Quoted 9 lines · Steven Rostedt
Quoted 6 lines · On Sat, 22 Dec 2018 12:23:35 -0500 Steven Rostedt <[email protected]> wrote:
Quoted 2 lines · On Sat, 22 Dec 2018 12:19:11 -0500 Steven Rostedt <[email protected]> wrote:

Because memcmp() isn't required to test byte by byte. In fact, most implementations don't which is why memcmp is faster than strcncmp.

Quoted 7 lines
Quoted 3 lines

In fact, if memcmp() was safe to use if we only knew the size of one of the parameters, then there would be no reason for strncmp to exist.

Also, I believe there are some memcmp implementations that start at the end of the memory locations, not the beginning. That is, it compares backwards. Which is also legit for memcmp to do.

I'm not sure, the man page says:

RETURN VALUE
The memcmp() function returns an integer less than, equal to, or greater than zero if the first n bytes of s1 is found, respectively, to be less than, to match, or be greater than the first n bytes of s2.

For a nonzero return value, the sign is determined by the sign of the difference between the first pair of bytes (interpreted as unsigned char) that differ in s1 and s2.

If n is zero, the return value is zero.

It should return difference in the first pair of bytes that differ so I guess implementations should compare from the beginning.

Thanks,
Namhyung

#11 lore raw
Quoted 16 lines · On Sun, 23 Dec 2018 12:13:43 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 3 lines

Also, I believe there are some memcmp implementations that start at the end of the memory locations, not the beginning. That is, it compares backwards. Which is also legit for memcmp to do.

I'm not sure, the man page says:

RETURN VALUE
The memcmp() function returns an integer less than, equal to, or greater than zero if the first n bytes of s1 is found, respectively, to be less than, to match, or be greater than the first n bytes of s2.

For a nonzero return value, the sign is determined by the sign of the difference between the first pair of bytes (interpreted as unsigned char) that differ in s1 and s2.

Quoted 5 lines

If n is zero, the return value is zero.

It should return difference in the first pair of bytes that differ so I guess implementations should compare from the beginning.

Ah, makes sense. I think I'm thinking of memcpy() which can start at the end, or maybe even the deprecated bcmp(). It's been a long time since I had to deal with the implementations of these.

-- Steve

#12 lore raw
In reply to Steven Rostedt
Quoted 19 lines · Steven Rostedt
Quoted 11 lines · On Sun, 23 Dec 2018 01:46:05 +0900 Namhyung Kim <[email protected]> wrote:
Quoted 5 lines

What I meant by that is if a string is allocated at a end of a page, and the next page is marked as not present. A read into that page will cause a page fault, and since memcmp() does not stop at the '\0' it will read into that not-present memory and trigger a fault, and that read wont be in the exception table, and it will then BUG.

Why it doesn't stop at the '\0' if one has it and the other doesn't? It's not because it's '\0', it's because they are different. The '\0' should be in the prev page (otherwise it's already a BUG) so it should be detected and stopped before going to next page IMHO.

Because memcmp() isn't required to test byte by byte. In fact, most implementations don't which is why memcmp is faster than strcncmp.

Quoted 6 lines

It can be checking in 8 byte chunks or more (although perhaps not likely). Perhaps there's an arch command that lets you compare 32 bytes at a time, if the size passed to memcmp is 32 or more, the implementation is allowed to read both src and dst of 32 bytes at a time. If there was a '\0' followed by not present memory, you will still get that fault.

I thought such implementation would check the alignment and not cross the page boundary in a single read. But it's implementation's choice and I found that glibc's default implementation for misaligned pointer reads next chunk as well to form an aligned chunk using shifts. So for the safety it'd be better to use strcmp()..

Thanks for your time and the explanation,
Namhyung

#13 lore raw
In reply to Steven Rostedt
Quoted 2 lines · On Fri, 21 Dec 2018 23:19:24 -0500 Steven Rostedt <[email protected]> wrote:
Cc Tom Zanussi <[email protected]>
Cc Linus Torvalds <[email protected]>

This should have been:

Suggestions-by: Linus Torvalds ...

But I went back to a further reflog when doing a reset --hard to get back to returning length from str_has_prefix, which didn't have this update.

-- Steve

Quoted 4 lines
#14 lore raw

[utility perl script] strncmp() -> str_has_prefix() conversions

In reply to Steven Rostedt
Quoted 1 line · Steven Rostedt

str_has_prefix

A coccinelle script could be more thorough but here is a trivial perl script that can do most of the

	strncmp() -> str_has_prefix()

conversions where there is a constant string as one of the first two arguments of strncmp like any of:

	strncmp(foo, "bar", 3)
	strncmp(foo, "bar", strlen("bar"))
	strncmp(foo, "bar", sizeof("bar") - 1)
	strncmp("foo", bar, 3)
	strncmp("foo", bar, strlen("foo"))
	strncmp("foo", bar",

sizeof("foo") - 1)

It could be used with a particular path or file:

$ git grep -w --name-only strncmp <path> | \
  grep -vP '^(tools|scripts)' | \
  while read file ; do \
    echo $file ; \
    perl -i ./strncmp.perl $file ; \
  done

It mostly works, but there are a few uses that are not converted properly when the non const string argument to strncmp is an expression like

	strncmp(a+b, "foo", 3)

There are also strncmp uses that remain after this script is run where strncmp should just be converted to strcmp instead like:

	strncmp(p, "foo", sizeof(foo))
and
	strncmp(p, "foo", 4)

The script converts the most common cases:

## counted length of string
# strncmp(arg, string, counted length of string) == 0 # strncmp(arg, string, counted length of string) != 0 # !strncmp(arg, string, counted length of string) # strncmp(arg, string, counted length of string)

## Reversed string/arg counted length of string uses # strncmp(string, arg, counted length of string) == 0 # strncmp(string, arg, counted length of string) != 0 # !strncmp(string, arg, counted length of string) # strncmp(string, arg, counted length of string)

## strlen uses
# strncmp(arg, string, strlen(string)) == 0 # !strncmp(arg, string, strlen(string))

## reversed string/arg strlen uses
# strncmp(string, arg, strlen(string)) == 0 # !strncmp(string, arg, strlen(string))

## 'sizeof(string) - 1' uses
# strncmp(arg, string, sizeof(string) - 1) == 0 # !strncmp(arg, string, sizeof(string) - 1)

On linux-next, running the script below

$ git grep -w --name-only strncmp | \
  grep -vP '^(tools|scripts)' | \
  while read file ; do \
    echo $file ; \
    perl -i ./strncmp.perl $file ; \
  done

produces:

$ git diff --shortstat
 437 files changed, 1483 insertions(+), 1500 deletions(-)