Re: [PATCH] commit-graph: fix truncated generation numbers

[Taylor Blau <me@ttaylorr.com>]

On Mon, Mar 27, 2023 at 10:08:25AM +0200, Patrick Steinhardt wrote:
> In 80c928d947 (commit-graph: simplify compute_generation_numbers(),
> 2023-03-20), the code to compute generation numbers was simplified to
> use the same infrastructure as is used to compute topological levels.
> This refactoring introduced a bug where the generation numbers are
> truncated when they exceed UINT32_MAX because we explicitly cast the
> computed generation number to `uint32_t`. This is not required though:
> both the computed value and the field of `struct commit_graph_data` are
> of the same type `timestamp_t` already, so casting to `uint32_t` will
> cause truncation.

Yes, well spotted and explained. Indeed, the `generation` field of the
`commit_graph_data` struct uses our custom `timestamp_t`, so this cast
is unnecessary.

And it's fine to have a value greater than 2<<32-1 here, since we can
represent values that require more than 32-bits of storage. For that we
rely on the extended offset table (in this case, GDA2).

> This cast can cause us to miscompute generation data overflows:
>
>     1. Given a commit with no parents and committer date
>        `UINT32_MAX + 1`.

FWIW, I don't think this is the only way to trigger this bug. It would
also work if there was a commit C whose maximum parent's generation
number is (2<<32-1), in which case C's generation number would be 2<<32,
and trigger our overflow here.

> This commit applies on top of cbfe360b14 (commit-reach: add
> tips_reachable_from_bases(), 2023-03-20), which has recently been merged
> to next.

This all looks good to me, I'd be happy to see this squashed into that
topic on 'next'.

Thanks,
Taylor