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

From: Taylor Blau <me@ttaylorr.com>
Date: Mar 28, 2023, 18:39 UTC
Message-ID: <ZCM0eYGKWc8UusZ7@nand.local>
In-Reply-To: <f8a0a869e8b0882f05cac49d78f49ba3553d3c44.1679904401.git.ps@pks.im>

On Mon, Mar 27, 2023 at 10:08:25AM +0200, Patrick Steinhardt wrote:

Show 9 quoted lines

> 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