* [PATCH] commit-graph: fix truncated generation numbers
@ 2023-03-27 8:08 Patrick Steinhardt
2023-03-28 17:45 ` Junio C Hamano
2023-03-28 18:39 ` Taylor Blau
0 siblings, 2 replies; 4+ messages in thread
From: Patrick Steinhardt @ 2023-03-27 8:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Taylor Blau
[-- Attachment #1: Type: text/plain, Size: 2820 bytes --]
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.
This cast can cause us to miscompute generation data overflows:
1. Given a commit with no parents and committer date
`UINT32_MAX + 1`.
2. We compute its generation number as `UINT32_MAX + 1`, but
truncate it to `1`.
3. We calculate the generation offset via `$generation - $date`,
which is thus `1 - (UINT32_MAX + 1)`. The computation underflows
and we thus end up with an offset that is bigger than the maximum
allowed offset.
As a result, we'd be writing generation data overflow information into
the commit-graph that is bogus and ultimately not even required.
Fix this bug by removing the needless cast.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
This commit applies on top of cbfe360b14 (commit-reach: add
tips_reachable_from_bases(), 2023-03-20), which has recently been merged
to next.
commit-graph.c | 2 +-
t/t5328-commit-graph-64bit-time.sh | 9 +++++++++
2 files changed, 10 insertions(+), 1 deletion(-)
diff --git a/commit-graph.c b/commit-graph.c
index 172e679db1..b96509354e 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1565,7 +1565,7 @@ static timestamp_t get_generation_from_graph_data(struct commit *c, void *data)
static void set_generation_v2(struct commit *c, timestamp_t t, void *data)
{
struct commit_graph_data *g = commit_graph_data_at(c);
- g->generation = (uint32_t)t;
+ g->generation = t;
}
static void compute_generation_numbers(struct write_commit_graph_context *ctx)
diff --git a/t/t5328-commit-graph-64bit-time.sh b/t/t5328-commit-graph-64bit-time.sh
index 093f0c067a..57e4d9c699 100755
--- a/t/t5328-commit-graph-64bit-time.sh
+++ b/t/t5328-commit-graph-64bit-time.sh
@@ -63,4 +63,13 @@ test_expect_success 'set up and verify repo with generation data overflow chunk'
graph_git_behavior 'overflow 2' repo left right
+test_expect_success 'single commit with generation data exceeding UINT32_MAX' '
+ git init repo-uint32-max &&
+ cd repo-uint32-max &&
+ test_commit --date "@4294967297 +0000" 1 &&
+ git commit-graph write --reachable &&
+ graph_read_expect 1 "generation_data" &&
+ git commit-graph verify
+'
+
test_done
--
2.40.0
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] commit-graph: fix truncated generation numbers
2023-03-27 8:08 [PATCH] commit-graph: fix truncated generation numbers Patrick Steinhardt
@ 2023-03-28 17:45 ` Junio C Hamano
2023-03-28 18:32 ` Derrick Stolee
2023-03-28 18:39 ` Taylor Blau
1 sibling, 1 reply; 4+ messages in thread
From: Junio C Hamano @ 2023-03-28 17:45 UTC (permalink / raw)
To: Derrick Stolee, Patrick Steinhardt; +Cc: git, Taylor Blau
Patrick Steinhardt <ps@pks.im> writes:
> 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.
>
> This cast can cause us to miscompute generation data overflows:
>
> 1. Given a commit with no parents and committer date
> `UINT32_MAX + 1`.
>
> 2. We compute its generation number as `UINT32_MAX + 1`, but
> truncate it to `1`.
>
> 3. We calculate the generation offset via `$generation - $date`,
> which is thus `1 - (UINT32_MAX + 1)`. The computation underflows
> and we thus end up with an offset that is bigger than the maximum
> allowed offset.
>
> As a result, we'd be writing generation data overflow information into
> the commit-graph that is bogus and ultimately not even required.
>
> Fix this bug by removing the needless cast.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
>
> This commit applies on top of cbfe360b14 (commit-reach: add
> tips_reachable_from_bases(), 2023-03-20), which has recently been merged
> to next.
The patch is clearly explained and the change looks quite
straight-forward. Derrick, Ack?
Thanks.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] commit-graph: fix truncated generation numbers
2023-03-28 17:45 ` Junio C Hamano
@ 2023-03-28 18:32 ` Derrick Stolee
0 siblings, 0 replies; 4+ messages in thread
From: Derrick Stolee @ 2023-03-28 18:32 UTC (permalink / raw)
To: Junio C Hamano, Patrick Steinhardt; +Cc: git, Taylor Blau
On 3/28/23 1:45 PM, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
>
>> 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.
>>
>> This cast can cause us to miscompute generation data overflows:
>>
>> 1. Given a commit with no parents and committer date
>> `UINT32_MAX + 1`.
>>
>> 2. We compute its generation number as `UINT32_MAX + 1`, but
>> truncate it to `1`.
>>
>> 3. We calculate the generation offset via `$generation - $date`,
>> which is thus `1 - (UINT32_MAX + 1)`. The computation underflows
>> and we thus end up with an offset that is bigger than the maximum
>> allowed offset.
>>
>> As a result, we'd be writing generation data overflow information into
>> the commit-graph that is bogus and ultimately not even required.
>>
>> Fix this bug by removing the needless cast.
>>
>> Signed-off-by: Patrick Steinhardt <ps@pks.im>
>> ---
>>
>> This commit applies on top of cbfe360b14 (commit-reach: add
>> tips_reachable_from_bases(), 2023-03-20), which has recently been merged
>> to next.
>
> The patch is clearly explained and the change looks quite
> straight-forward. Derrick, Ack?
Yes, looks good. What a silly mistake, but thanks for going
the extra mile to introduce a test that will prevent it in
the future.
Thanks,
-Stolee
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] commit-graph: fix truncated generation numbers
2023-03-27 8:08 [PATCH] commit-graph: fix truncated generation numbers Patrick Steinhardt
2023-03-28 17:45 ` Junio C Hamano
@ 2023-03-28 18:39 ` Taylor Blau
1 sibling, 0 replies; 4+ messages in thread
From: Taylor Blau @ 2023-03-28 18:39 UTC (permalink / raw)
To: Patrick Steinhardt; +Cc: git, Derrick Stolee
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2023-03-28 18:39 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-03-27 8:08 [PATCH] commit-graph: fix truncated generation numbers Patrick Steinhardt
2023-03-28 17:45 ` Junio C Hamano
2023-03-28 18:32 ` Derrick Stolee
2023-03-28 18:39 ` Taylor Blau
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).