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: <20241101113910.GA2301440@coredump.intra.peff.net>
Date: Fri, 1 Nov 2024 07:39:10 -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 Fri, Nov 01, 2024 at 11:23:05AM +0100, Rasmus Villemoes wrote:

> Perhaps we could on the kernel side replace the "git describe --match"
> calls with a helper, something like this (needs a lot of polishing):

Yeah, if you are describing off of a single tag, it may just be easier
to query things about the tag directly. Though I do still think
git-describe should be faster here. I'm still pondering what to do about
the disjoint history tests, but otherwise have a polished series to
send.

> ===
> # Produce output similar to what "git describe --match=$tag 2>
> # /dev/null" would.  It doesn't have to match exactly as the caller is
> # only interested in whether $tag == HEAD, and if not, the number
> # between the tag and the short sha1.
> describe()
> {
>     # Is $tag an annotated tag? Could/should probably be written using
>     # some plumbing instead of git describe, but with --exact-match,
>     # we avoid the walk-to-the-start-of-history behaviour, so fine for
>     # this demo.
>     git describe --exact-match --match=$tag $tag >/dev/null 2>/dev/null || return 1

Probably "git cat-file -t $tag" is the simplest way to see if it points
to a tag.

>     # Can it be used to describe HEAD, i.e. is it an ancestor of HEAD?
>     git merge-base --is-ancestor $tag HEAD || return 1
> 
>     # Find the number that "git describe" would append.
>     count=$(git rev-list --count $tag..HEAD)
>     if [ $count -eq 0 ] ; then
>         echo "$tag"
>     else
>         echo "$tag-$count-$head"
>     fi

You can query both of these at once with:

  git rev-list --count --left-right $tag...HEAD

That will traverse down to the merge base and give you two counts. If
the first one is 0, then $tag is a direct ancestor. And the second one
is the count of what's in HEAD.

At first glance, it seems like you'd waste time counting the HEAD side
when the --is-ancestor check could have rejected the tag earlier. But in
practice I think the time will always be dominated by walking down to
the merge base in all commands.

> I also don't know if either the --is-ancestor or the rev-list count
> could end up doing the same walk-all-commits we're trying to avoid.

It shouldn't. In all of those cases we'll generally walk breadth-first
down to the merge base. They're also operations that can take advantage
of other optimizations that git-describe never learned about. E.g.,
generation numbers in the commit graph.

We can even do fast --count with reachability bitmaps, though I wouldn't
expect most dev repos to have bitmaps built. Also, it looks like
"--left-right --count" does not support bitmaps. IMHO that is a bug. ;)

-Peff