Re: [PATCH 4/4] ref-filter: avoid strrchr() in rstrip_ref_components()
On Sun, Feb 15, 2026 at 04:07:44AM -0500, Jeff King wrote:
Show 7 quoted lines
> 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.
Show 20 quoted lines
> 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.
Show 5 quoted lines
> 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.
Show 22 quoted lines
> 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
Collin Funk
