Re: [PATCH v6 01/10] Documentation/technical: add paint-down-to-common doc

From: Kristofer Karlsson <krka@spotify.com>
Date: Jul 26, 2026, 10:33 UTC
Message-ID: <CAL71e4Mve9EbTkuWoGdtNTJJC5oj_W9enfSceMvH0FFm4T8ALA@mail.gmail.com>
In-Reply-To: <CABPp-BGvoZArZ65ge_2qabb9GQDbtWG=pP=g4bZDmAvX=yF=xA@mail.gmail.com>

On Sun, 26 Jul 2026 at 08:59, Elijah Newren <newren@gmail.com> wrote:

Show 5 quoted lines

>
>
> Perhaps we could lump GENERATION_NUMBER_V1_MAX the same as INFINITY
> for this algorithm, since GENERATION_NUMBER_V1_MAX can also violate
> the ordering we want?

Oh, that's a nice catch. I had completely missed this V1_MAX saturation case! I spent some time thinking about this edge-case and fortunately I think it's very hard to trigger. You would need to construct a graph with 1B generations, which is a very big git graph indeed.

That said, regardless of how hard it is to trigger the code should be correct. I agree that we could lump GENERATION_NUMBER_V1_MAX together with GENERATION_NUMBER_INFINITY since they are both topologically unordered values and naturally must be topologically above any lower values.

I considered two approaches. Both are correct as far as I can tell and both only matter for very large v1 graphs, so in practice either should be fine.

Option A: remap V1_MAX to INFINITY at load time in fill_commit_graph_info(). On the read side:

    uint32_t level = get_be32(...) >> 2;
    if (level >= GENERATION_NUMBER_V1_MAX)
        graph_data->generation = GENERATION_NUMBER_INFINITY;
    else
        graph_data->generation = level;

This is a fairly small change and everything downstream just works. The write path already uses the separate topo_levels slab so it would keep writing V1_MAX for backward compatibility.

The downside is that it conflates two distinct concepts: "not in the commit-graph at all" and "in the graph but ordering has saturated." This specifically affects the bloom filter checks in blame.c, revision.c and last-modified.c where we check for gen == INFINITY to mean specifically "not in the graph" because a commit not in the graph cannot have a bloom filter. With the remap, V1_MAX commits would unnecessarily skip bloom filters. Not a correctness bug, but a performance regression for those commits. Perhaps not a very important case though -- if you have that many commits and notice performance issues you should probably upgrade to v2 anyway.

That said, even if it technically works today, maybe new code in the future would have stronger dependencies on the semantics so it feels fragile.

Option B: introduce commit_graph_generation_topo_ceiling(r) that returns the generation value where topological ordering is no longer guaranteed -- V1_MAX for v1 graphs, INFINITY for v2 or no graph. Then the early exit gates use:

    if (generation < state.topo_ceiling)
        /* in the topologically ordered region */

This keeps INFINITY meaning "not in the graph" and V1_MAX meaning "saturated but present." Bloom filter checks continue to work the same as before. It does introduce a new concept that callers of the ordering gates need to be aware of, but the concept maps directly to the underlying graph format difference.

I went with option B in my local v7 draft since it felt like a less intrusive change, though it would be nice to hide the v1/v2 differences more from the rest of the code.

Let me know if you have a preference or see issues with either approach.

Show 9 quoted lines

> I think what makes the min_generation cutoff safe is that callers
> passing a nonzero min_generation (remove_redundant() and
> repo_in_merge_bases_many()) don't need those deeper merge bases at
> all: they only need to determine reachability among the input commits,
> all of which sit at or above min_generation.
>
> Is there a risk that with the current wording of this paragraph that
> future callers might be tempted to pass a nonzero min_generation and
> still expect a complete MERGE_BASE_FIND_ALL result?

You are right, the wording is misleading. I can update it to something like this instead (will polish it more, just a draft):

    Note: A non-zero min_generation floor means that you are not
    guaranteed to find any merge-base, it is purely useful for
    determining the ancestry relation between the input commits.
    If it is set, the walk can terminate as soon as we have passed
    the bottom commit, because we then know that there is no direct
    ancestry.

Thanks, I really appreciate the careful review and spotting this edge case! Kristofer