linux-kernel - Re: [PATCH] setlocalversion: Add workaround for "git describe" performance issue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20241031122456.GB593548@coredump.intra.peff.net>
Date: Thu, 31 Oct 2024 08:24:56 -0400
From: Jeff King <peff@...f.net>
To: Rasmus Villemoes <ravi@...vas.dk>
Cc: Josh Poimboeuf <jpoimboe@...nel.org>,
	Masahiro Yamada <masahiroy@...nel.org>,
	linux-kernel@...r.kernel.org, linux-kbuild@...r.kernel.org,
	git@...r.kernel.org
Subject: Re: [PATCH] setlocalversion: Add workaround for "git describe"
 performance issue

On Thu, Oct 31, 2024 at 07:42:10AM -0400, Jeff King wrote:

> That works, but I have a feeling that figured out what the heck is going
> on with gave_up_on might produce a more elegant solution.

OK, I think I might have made some sense of this.

In finish_depth_computation(), we traverse down "list" forever, passing
flags up to our parents, until we find a commit that is marked with the
same "within" flag as our candidate. And then if everything left has
that same "within" flag set, we can bail.

So I _think_ the point is to basically count up what we'd get from this
traversal:

  $tag..$commit

where "$tag" is the candidate tag we found, and "$commit" is what we're
trying to describe (so imagine "git describe --match=$tag $commit").

We can't just use the depth we found while traversing down to $tag,
because there might be side branches we need to count up, too. And we
don't start a new traversal, because we'd be repeating the bits we
already went over when finding $tag in the first place.

And we feed that "list" from the original traversal state. So if we
break out of the traversal early but don't set gave_up_on, then we have
nothing in that state that holds the "within" flag. So we just walk all
of the commits down to the root, because nobody is propagating the flag
to them.

We have to feed at least one commit with the "within" flag into the
traversal so that it can let us end things. But I don't think it really
matters if that commit is the one we found, or if it's a parent of one
that we happened to pass "within" bits down to.

So I think we can just set "gave_up_on" to the final element we found
(whether from max_candidates or from finding every possible name). I.e.,
what I showed earlier, or what you were proposing.

I was also a bit puzzled how this works when there are multiple tags.
We feed only one "best" candidate to finish_depth_computation(), but
gave_up_on does not necessarily have its flag set. But I think that case
the point is that _some_ commit in the list does, and we literally add
every commit to that list.

I'm actually a bit skeptical that any of this is faster than simply
starting over a new traversal of $tag..$commit to find the depth, since
we are considering each commit anew. And there's a bunch of accidentally
quadratic bits of finish_depth_computation(). But frankly I'm somewhat
afraid to touch any of this more than necessary.

-Peff