Re: [PATCH 11/15] find multi-byte comment chars in unterminated buffers

["René Scharfe" <l.s.r@web.de>]

Am 07.03.24 um 10:26 schrieb Jeff King:
> As with the previous patch, we need to swap out single-byte matching for
> something like starts_with() to match all bytes of a multi-byte comment
> character. But for cases where the buffer is not NUL-terminated (and we
> instead have an explicit size or end pointer), it's not safe to use
> starts_with(), as it might walk off the end of the buffer.
>
> Let's introduce a new starts_with_mem() that does the same thing but
> also accepts the length of the "haystack" str and makes sure not to walk
> past it.
>
> Note that in most cases the existing code did not need a length check at
> all, since it was written in a way that knew we had at least one byte
> available (and that was all we checked). So I had to read each one to
> find the appropriate bounds. The one exception is sequencer.c's
> add_commented_lines(), where we can actually get rid of the length
> check. Just like starts_with(), our starts_with_mem() handles an empty
> haystack variable by not matching (assuming a non-empty prefix).
>
> A few notes on the implementation of starts_with_mem():
>
>   - it would be equally correct to take an "end" pointer (and indeed,
>     many of the callers have this and have to subtract to come up with
>     the length). I think taking a ptr/size combo is a more usual
>     interface for our codebase, though, and has the added benefit that
>     the function signature makes it harder to mix up the three
>     parameters.
>
>   - we could obviously build starts_with() on top of this by passing
>     strlen(str) as the length. But it's possible that starts_with() is a
>     relatively hot code path, and it should not pay that penalty (it can
>     generally return an answer proportional to the size of the prefix,
>     not the whole string).
>
>   - it naively feels like xstrncmpz() should be able to do the same
>     thing, but that's not quite true. If you pass the length of the
>     haystack buffer, then strncmp() finds that a shorter prefix string
>     is "less than" than the haystack, even if the haystack starts with
>     the prefix. If you pass the length of the prefix, then you risk
>     reading past the end of the haystack if it is shorter than the
>     prefix. So I think we really do need a new function.

Yes.  xstrncmpz() compares a NUL-terminated string and a length-limited
string.  If you want to check whether the former is a prefix of the
latter then you need to stop comparing when reaching its NUL, and also
after exhausting the latter.  So you need to take both lengths into
account:

int starts_with_mem(const char *str, size_t len, const char *prefix)
{
	size_t prefixlen = strlen(prefix);
	return prefixlen <= len && !xstrncmpz(prefix, str, prefixlen);
}

Using memcmp() here is equivalent and simpler:

int starts_with_mem(const char *str, size_t len, const char *prefix)
{
	size_t prefixlen = strlen(prefix);
	return prefixlen <= len && !memcmp(str, prefix, prefixlen);
}

And your version below avoids function calls and avoids traversing the
strings beyond their common prefix, of course.

>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> Arguably starts_with() and this new function should both be inlined,
> like we do for skip_prefix(), but I think that's out of scope for this
> series.

Inlining would allow the compiler to unroll the loop for string
constants.  I doubt it would do that for variables, as in the code
below.

Inlining the strlen()+memcmp() version above might allow the compiler
to push the strlen() call out of a loop.

Would any of that improve performance noticeably?  For the call sites
below I doubt it.  But it would probably increase the object text size.

> And it's possible I was simply too dumb to figure out xstrncmpz() here.
> I'm waiting for René to show up and tell me how to do it. ;)

Nah, it's not a good fit, as it requires the two strings to have the
same length.

>
> IMHO this is the trickiest commit of the whole series, as it would be
> easy to get the length computations subtly wrong.
>
>  commit.c    |  3 ++-
>  sequencer.c |  4 ++--
>  strbuf.c    | 11 +++++++++++
>  strbuf.h    |  1 +
>  trailer.c   |  4 ++--
>  5 files changed, 18 insertions(+), 5 deletions(-)
>
> diff --git a/commit.c b/commit.c
> index ef679a0b93..531a666cba 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -1796,7 +1796,8 @@ size_t ignored_log_message_bytes(const char *buf, size_t len)
>  		else
>  			next_line++;
>
> -		if (buf[bol] == comment_line_char || buf[bol] == '\n') {
> +		if (starts_with_mem(buf + bol, cutoff - bol, comment_line_str) ||
> +		    buf[bol] == '\n') {
>  			/* is this the first of the run of comments? */
>  			if (!boc)
>  				boc = bol;
> diff --git a/sequencer.c b/sequencer.c
> index 991a2dbe96..664986e3b2 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -1840,7 +1840,7 @@ static int is_fixup_flag(enum todo_command command, unsigned flag)
>  static void add_commented_lines(struct strbuf *buf, const void *str, size_t len)
>  {
>  	const char *s = str;
> -	while (len > 0 && s[0] == comment_line_char) {
> +	while (starts_with_mem(s, len, comment_line_str)) {
>  		size_t count;
>  		const char *n = memchr(s, '\n', len);
>  		if (!n)
> @@ -2562,7 +2562,7 @@ static int parse_insn_line(struct repository *r, struct todo_item *item,
>  	/* left-trim */
>  	bol += strspn(bol, " \t");
>
> -	if (bol == eol || *bol == '\r' || *bol == comment_line_char) {
> +	if (bol == eol || *bol == '\r' || starts_with_mem(bol, eol - bol, comment_line_str)) {

If the strspn() call is safe (which it is, as the caller expects the
string to be NUL-terminated) then you could use starts_with() here and
avoid the length calculation.  But that would also match
comment_line_str values that contain LF, which the _mem version does not
and that's better.

Not sure why lines that start with CR are considered comment lines,
though.

>  		item->command = TODO_COMMENT;
>  		item->commit = NULL;
>  		item->arg_offset = bol - buf;
> diff --git a/strbuf.c b/strbuf.c
> index 7c8f582127..291bdc2a65 100644
> --- a/strbuf.c
> +++ b/strbuf.c
> @@ -24,6 +24,17 @@ int istarts_with(const char *str, const char *prefix)
>  			return 0;
>  }
>
> +int starts_with_mem(const char *str, size_t len, const char *prefix)
> +{
> +	const char *end = str + len;
> +	for (; ; str++, prefix++) {
> +		if (!*prefix)
> +			return 1;
> +		else if (str == end || *str != *prefix)
> +			return 0;
> +	}
> +}

So this checks whether a length-limited string has a prefix given as a
NUL-terminated string.  I'd have called it mem_starts_with() and have
expected starts_with_mem() to check a NUL-terminated string for a
length-limited prefix (think !strncmp(str, prefix, prefixlen)).

> +
>  int skip_to_optional_arg_default(const char *str, const char *prefix,
>  				 const char **arg, const char *def)
>  {
> diff --git a/strbuf.h b/strbuf.h
> index 58dddf2777..3156d6ea8c 100644
> --- a/strbuf.h
> +++ b/strbuf.h
> @@ -673,6 +673,7 @@ char *xstrfmt(const char *fmt, ...);
>
>  int starts_with(const char *str, const char *prefix);
>  int istarts_with(const char *str, const char *prefix);
> +int starts_with_mem(const char *str, size_t len, const char *prefix);
>
>  /*
>   * If the string "str" is the same as the string in "prefix", then the "arg"
> diff --git a/trailer.c b/trailer.c
> index fe18faf6c5..f59c90b4b5 100644
> --- a/trailer.c
> +++ b/trailer.c
> @@ -882,7 +882,7 @@ static size_t find_trailer_block_start(const char *buf, size_t len)
>
>  	/* The first paragraph is the title and cannot be trailers */
>  	for (s = buf; s < buf + len; s = next_line(s)) {
> -		if (s[0] == comment_line_char)
> +		if (starts_with_mem(s, buf + len - s, comment_line_str))
>  			continue;
>  		if (is_blank_line(s))

Another case where starts_with() would be safe to use, as
is_blank_line() expects (and gets) a NUL-terminated string, but it would
allow matching comment_line_str values that contain LF.

>  			break;
> @@ -902,7 +902,7 @@ static size_t find_trailer_block_start(const char *buf, size_t len)
>  		const char **p;
>  		ssize_t separator_pos;
>
> -		if (bol[0] == comment_line_char) {
> +		if (starts_with_mem(bol, buf + end_of_title - bol, comment_line_str)) {

We're in the same buffer, so the above comment applies here as well.

>  			non_trailer_lines += possible_continuation_lines;
>  			possible_continuation_lines = 0;
>  			continue;