{"thread":{"id":"59482","subject":"[PATCH] commit-graph: fix truncated generation numbers","startedAt":"2023-03-27T08:08:36Z","lastAt":"2023-03-28T18:39:58Z","messageCount":4,"participants":["Patrick Steinhardt","Junio C Hamano","Derrick Stolee","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"474220","messageId":"f8a0a869e8b0882f05cac49d78f49ba3553d3c44.1679904401.git.ps@pks.im","threadId":"59482","inReplyTo":null,"subject":"[PATCH] commit-graph: fix truncated generation numbers","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-03-27T08:08:25Z","receivedAt":"2023-03-27T08:08:36Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 80c928d947 (commit-graph: simplify compute_generation_numbers(),\n2023-03-20), the code to compute generation numbers was simplified to\nuse the same infrastructure as is used to compute topological levels.\nThis refactoring introduced a bug where the generation numbers are\ntruncated when they exceed UINT32_MAX because we explicitly cast the\ncomputed generation number to `uint32_t`. This is not required though:\nboth the computed value and the field of `struct commit_graph_data` are\nof the same type `timestamp_t` already, so casting to `uint32_t` will\ncause truncation.\n\nThis cast can cause us to miscompute generation data overflows:\n\n    1. Given a commit with no parents and committer date\n       `UINT32_MAX + 1`.\n\n    2. We compute its generation number as `UINT32_MAX + 1`, but\n       truncate it to `1`.\n\n    3. We calculate the generation offset via `$generation - $date`,\n       which is thus `1 - (UINT32_MAX + 1)`. The computation underflows\n       and we thus end up with an offset that is bigger than the maximum\n       allowed offset.\n\nAs a result, we'd be writing generation data overflow information into\nthe commit-graph that is bogus and ultimately not even required.\n\nFix this bug by removing the needless cast.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n\nThis commit applies on top of cbfe360b14 (commit-reach: add\ntips_reachable_from_bases(), 2023-03-20), which has recently been merged\nto next.\n\n commit-graph.c                     | 2 +-\n t/t5328-commit-graph-64bit-time.sh | 9 +++++++++\n 2 files changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 172e679db1..b96509354e 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1565,7 +1565,7 @@ static timestamp_t get_generation_from_graph_data(struct commit *c, void *data)\n static void set_generation_v2(struct commit *c, timestamp_t t, void *data)\n {\n \tstruct commit_graph_data *g = commit_graph_data_at(c);\n-\tg->generation = (uint32_t)t;\n+\tg->generation = t;\n }\n \n static void compute_generation_numbers(struct write_commit_graph_context *ctx)\ndiff --git a/t/t5328-commit-graph-64bit-time.sh b/t/t5328-commit-graph-64bit-time.sh\nindex 093f0c067a..57e4d9c699 100755\n--- a/t/t5328-commit-graph-64bit-time.sh\n+++ b/t/t5328-commit-graph-64bit-time.sh\n@@ -63,4 +63,13 @@ test_expect_success 'set up and verify repo with generation data overflow chunk'\n \n graph_git_behavior 'overflow 2' repo left right\n \n+test_expect_success 'single commit with generation data exceeding UINT32_MAX' '\n+\tgit init repo-uint32-max &&\n+\tcd repo-uint32-max &&\n+\ttest_commit --date \"@4294967297 +0000\" 1 &&\n+\tgit commit-graph write --reachable &&\n+\tgraph_read_expect 1 \"generation_data\" &&\n+\tgit commit-graph verify\n+'\n+\n test_done\n-- \n2.40.0\n\n"},{"id":"474335","messageId":"xmqqfs9og47y.fsf@gitster.g","threadId":"59482","inReplyTo":"f8a0a869e8b0882f05cac49d78f49ba3553d3c44.1679904401.git.ps@pks.im","subject":"Re: [PATCH] commit-graph: fix truncated generation numbers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-03-28T17:45:05Z","receivedAt":"2023-03-28T17:45:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> In 80c928d947 (commit-graph: simplify compute_generation_numbers(),\n> 2023-03-20), the code to compute generation numbers was simplified to\n> use the same infrastructure as is used to compute topological levels.\n> This refactoring introduced a bug where the generation numbers are\n> truncated when they exceed UINT32_MAX because we explicitly cast the\n> computed generation number to `uint32_t`. This is not required though:\n> both the computed value and the field of `struct commit_graph_data` are\n> of the same type `timestamp_t` already, so casting to `uint32_t` will\n> cause truncation.\n>\n> This cast can cause us to miscompute generation data overflows:\n>\n>     1. Given a commit with no parents and committer date\n>        `UINT32_MAX + 1`.\n>\n>     2. We compute its generation number as `UINT32_MAX + 1`, but\n>        truncate it to `1`.\n>\n>     3. We calculate the generation offset via `$generation - $date`,\n>        which is thus `1 - (UINT32_MAX + 1)`. The computation underflows\n>        and we thus end up with an offset that is bigger than the maximum\n>        allowed offset.\n>\n> As a result, we'd be writing generation data overflow information into\n> the commit-graph that is bogus and ultimately not even required.\n>\n> Fix this bug by removing the needless cast.\n>\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>\n> This commit applies on top of cbfe360b14 (commit-reach: add\n> tips_reachable_from_bases(), 2023-03-20), which has recently been merged\n> to next.\n\nThe patch is clearly explained and the change looks quite\nstraight-forward.  Derrick, Ack?\n\nThanks.\n"},{"id":"474351","messageId":"ca1f77db-a483-8b32-8e34-9bce1ea8afc3@github.com","threadId":"59482","inReplyTo":"xmqqfs9og47y.fsf@gitster.g","subject":"Re: [PATCH] commit-graph: fix truncated generation numbers","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-03-28T18:32:40Z","receivedAt":"2023-03-28T18:32:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/28/23 1:45 PM, Junio C Hamano wrote:\n> Patrick Steinhardt <ps@pks.im> writes:\n> \n>> In 80c928d947 (commit-graph: simplify compute_generation_numbers(),\n>> 2023-03-20), the code to compute generation numbers was simplified to\n>> use the same infrastructure as is used to compute topological levels.\n>> This refactoring introduced a bug where the generation numbers are\n>> truncated when they exceed UINT32_MAX because we explicitly cast the\n>> computed generation number to `uint32_t`. This is not required though:\n>> both the computed value and the field of `struct commit_graph_data` are\n>> of the same type `timestamp_t` already, so casting to `uint32_t` will\n>> cause truncation.\n>>\n>> This cast can cause us to miscompute generation data overflows:\n>>\n>>     1. Given a commit with no parents and committer date\n>>        `UINT32_MAX + 1`.\n>>\n>>     2. We compute its generation number as `UINT32_MAX + 1`, but\n>>        truncate it to `1`.\n>>\n>>     3. We calculate the generation offset via `$generation - $date`,\n>>        which is thus `1 - (UINT32_MAX + 1)`. The computation underflows\n>>        and we thus end up with an offset that is bigger than the maximum\n>>        allowed offset.\n>>\n>> As a result, we'd be writing generation data overflow information into\n>> the commit-graph that is bogus and ultimately not even required.\n>>\n>> Fix this bug by removing the needless cast.\n>>\n>> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n>> ---\n>>\n>> This commit applies on top of cbfe360b14 (commit-reach: add\n>> tips_reachable_from_bases(), 2023-03-20), which has recently been merged\n>> to next.\n> \n> The patch is clearly explained and the change looks quite\n> straight-forward.  Derrick, Ack?\n\nYes, looks good. What a silly mistake, but thanks for going\nthe extra mile to introduce a test that will prevent it in\nthe future.\n\nThanks,\n-Stolee\n\n"},{"id":"474353","messageId":"ZCM0eYGKWc8UusZ7@nand.local","threadId":"59482","inReplyTo":"f8a0a869e8b0882f05cac49d78f49ba3553d3c44.1679904401.git.ps@pks.im","subject":"Re: [PATCH] commit-graph: fix truncated generation numbers","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-03-28T18:39:53Z","receivedAt":"2023-03-28T18:39:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Mar 27, 2023 at 10:08:25AM +0200, Patrick Steinhardt wrote:\n> In 80c928d947 (commit-graph: simplify compute_generation_numbers(),\n> 2023-03-20), the code to compute generation numbers was simplified to\n> use the same infrastructure as is used to compute topological levels.\n> This refactoring introduced a bug where the generation numbers are\n> truncated when they exceed UINT32_MAX because we explicitly cast the\n> computed generation number to `uint32_t`. This is not required though:\n> both the computed value and the field of `struct commit_graph_data` are\n> of the same type `timestamp_t` already, so casting to `uint32_t` will\n> cause truncation.\n\nYes, well spotted and explained. Indeed, the `generation` field of the\n`commit_graph_data` struct uses our custom `timestamp_t`, so this cast\nis unnecessary.\n\nAnd it's fine to have a value greater than 2<<32-1 here, since we can\nrepresent values that require more than 32-bits of storage. For that we\nrely on the extended offset table (in this case, GDA2).\n\n> This cast can cause us to miscompute generation data overflows:\n>\n>     1. Given a commit with no parents and committer date\n>        `UINT32_MAX + 1`.\n\nFWIW, I don't think this is the only way to trigger this bug. It would\nalso work if there was a commit C whose maximum parent's generation\nnumber is (2<<32-1), in which case C's generation number would be 2<<32,\nand trigger our overflow here.\n\n> This commit applies on top of cbfe360b14 (commit-reach: add\n> tips_reachable_from_bases(), 2023-03-20), which has recently been merged\n> to next.\n\nThis all looks good to me, I'd be happy to see this squashed into that\ntopic on 'next'.\n\nThanks,\nTaylor\n"}]}