From: Patrick Steinhardt <ps@pks.im>
Date: Mon, 16 Feb 2026 07:23:44 GMT
Subject: Re: [PATCH 4/4] ref-filter: avoid strrchr() in rstrip_ref_components()
Message-ID: <aZLGAMiDdZ_vplND@pks.im>
In-Reply-To: <20260215090744.GD695631@coredump.intra.peff.net>

On Sun, Feb 15, 2026 at 04:07:44AM -0500, Jeff King wrote:
> To strip path components from our refname string, we repeatedly call
> strrchr() to find the trailing slash, shortening the string each time by
> assigning NUL over it. This has two downsides:
> 
>   1. Calling strrchr() in a loop is quadratic, since each call has to
>      call strlen() under the hood to find the end of the string (even
>      though we know exactly where it is from the last loop iteration).

Ah, indeed, that's something I missed.

>   2. We need a temporary buffer, since we're munging the string with NUL
>      as we shorten it (which we must do, because strrchr() has no other
>      way of knowing what we consider the end of the string).

Right, upon reading the preceding patch I figured that we can improve
this function even further and avoid the call to `xstrdup()` in the case
where we have less components than we're being asked to strip.

> Using memrchr() would let us fix both of these, but it isn't portable.
> So instead, let's just open-code the string traversal from back to
> front as we loop.
> 
> I doubt that the quadratic nature is a serious concern. You can see it
> in practice with something like:
> 
>   git init
>   git commit --allow-empty -m foo
>   echo "$(git rev-parse HEAD) refs/heads$(perl -e 'print "/a" x 500_000')" >.git/packed-refs
>   time git for-each-ref --format='%(refname:rstrip=-1)'
> 
> That takes ~5.5s to run on my machine before this patch, and ~11ms
> after. But I don't think there's a reasonable way for somebody to infect
> you with such a garbage ref, as the wire protocol is limited to 64k
> pkt-lines. The difference is measurable for me for a 32k-component ref
> (about 19ms vs 7ms), so perhaps you could create some chaos by pushing a
> lot of them. But we also run into filesystem limits (if the loose
> backend is in use), and in practice it seems like there are probably
> simpler and more effective ways to waste CPU.

Agreed, not much of a concern, but good regardless to see it being
addressed.

> Likewise the extra allocation probably isn't really measurable. In fact,
> since our goal is to return an allocated string, we end up having to
> make the same allocation anyway (though it is sized to the result,
> rather than the input). My main goal was simplicity in avoiding the need
> to handle cleaning it up in the early return path.

Likewise.

> diff --git a/ref-filter.c b/ref-filter.c
> index 1008b2fd5a..ac32b0e6bb 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -2213,17 +2213,15 @@ static const char *lstrip_ref_components(const char *refname, int len)
>  static const char *rstrip_ref_components(const char *refname, int len)
>  {
>  	int remaining = normalize_component_count(refname, len);
> -	char *start = xstrdup(refname);
> +	const char *end = refname + strlen(refname);
>  
> -	while (remaining-- > 0) {
> -		char *p = strrchr(start, '/');
> -		if (!p) {
> -			free(start);
> +	while (remaining > 0) {
> +		if (end == refname)
>  			return xstrdup("");
> -		} else
> -			p[0] = '\0';
> +		if (*--end == '/')
> +			remaining--;

We start scannign from the trailing NUL byte, so this would also cause
us to detect if the refname had "/" as a suffix. But I assume that's a
case we don't even need to care about, as refs cannot end with a slash
anyway.

Another edge case is if we were passed the empty string, but as we
already abort in case we see that `end == refname` we're good there,
too.

>  	}
> -	return start;
> +	return xmemdupz(refname, end - refname);
>  }

So overall this and all the preceding patches look good to me. Thanks!

Patrick