From patchwork Tue Jul 28 09:13:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688697 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 6771814B7 for ; Tue, 28 Jul 2020 09:13:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5050020829 for ; Tue, 28 Jul 2020 09:13:58 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="D+AAtWyG" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728287AbgG1JN5 (ORCPT ); Tue, 28 Jul 2020 05:13:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43308 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728021AbgG1JN4 (ORCPT ); Tue, 28 Jul 2020 05:13:56 -0400 Received: from mail-ej1-x642.google.com (mail-ej1-x642.google.com [IPv6:2a00:1450:4864:20::642]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 69364C061794 for ; Tue, 28 Jul 2020 02:13:56 -0700 (PDT) Received: by mail-ej1-x642.google.com with SMTP id f14so4036541ejb.2 for ; Tue, 28 Jul 2020 02:13:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=cJz965k/KbCTInwJwNvwRaLO7w8do9VOiZT/XRxiIzs=; b=D+AAtWyGMtLwXuA/kfgihycu/3PtIeqo+JH9ajkum8ual53o/lqR5+CP3cy891loih Qludv2r69X9/sEeYsb5v1oWRtJKgorLmwmB6l9DbajnryNcB0RC4XTRug8Wsj184kWF6 hXM0CicP6JkwHHcG4bjzk6RqI+1GtXgPe1GDP1Ny2Bae3EwAPn5mPoG/ThSus6SZ+SQf 7lPIutHV7+EaGVPUy7tHC6cWxfQqHPVyV6scXzFh0Z0/n8iSYLJVgXwJ7ow3oCPxS33j g0V+L2uVUBQ/yOJkcsk+Nda9Hpjy/hewVoAxRLB0ujELgivnb0BwmRpjTwjKLb5c8eSa +bxg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=cJz965k/KbCTInwJwNvwRaLO7w8do9VOiZT/XRxiIzs=; b=N8uzPUzsygiZCUKFFRrI67ltr1vliTGBTbxOps+1m9hCqckgMSN3A42xS9++Kxx2gI rIFj+qSW6cbIKkM6TNpejJWMrHApTnXj/5F9AWpZRws0zhAaXpKa5cWblkUA07M4TKAL /G2TjjXy+b6KIjPFxVimoSh0RSohjkF+BWPIyLAwyNYAcGqKD3Yl++GPXPHPkzhodYb9 teauRZxQHUwGo94li8DEKrBM23BdEv7rmESVLo00rF8yeiBTW09p01SNenIJ8OryGMzy UrTCkyl7LEkr9ZmkDg4GUod5qYbFVrDKKIeJHHnySxvBuV7Vgax2QJR0qXZlEhBWjb2R xRSg== X-Gm-Message-State: AOAM530bfVQ/+HR1OSSQs6f9v/3+6iSRutv5un9i2qCNep2yDIy3J1+p h5ijcPEaxpvx2VIjFMa9TWu1uLTL X-Google-Smtp-Source: ABdhPJzq6gjv2Jdm/eBzDoqaGknYevudAOpUI69U6heOfBIT0EdL5oPXDCiqt/lSkhjAvxvSnWkiIg== X-Received: by 2002:a17:907:72c8:: with SMTP id du8mr14032535ejc.237.1595927634964; Tue, 28 Jul 2020 02:13:54 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c18sm7921177eja.13.2020.07.28.02.13.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:54 -0700 (PDT) Message-Id: <91e6e97a66aff88e0b860e34659dddc3396c7f28.1595927632.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:46 +0000 Subject: [PATCH 1/6] commit-graph: fix regression when computing bloom filter Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar With 3d112755 (commit-graph: examine commits by generation number), Git knew to sort by generation number before examining the diff when not using pack order. c49c82aa (commit: move members graph_pos, generation to a slab, 2020-06-17) moved generation number into a slab and introduced a helper which returns GENERATION_NUMBER_INFINITY when writing the graph. Sorting is no longer useful and essentially reverts the earlier commit. Let's fix this by accessing generation number directly through the slab. Signed-off-by: Abhishek Kumar --- commit-graph.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 1af68c297d..5d3c9bd23c 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -144,8 +144,9 @@ static int commit_gen_cmp(const void *va, const void *vb) const struct commit *a = *(const struct commit **)va; const struct commit *b = *(const struct commit **)vb; - uint32_t generation_a = commit_graph_generation(a); - uint32_t generation_b = commit_graph_generation(b); + uint32_t generation_a = commit_graph_data_at(a)->generation; + uint32_t generation_b = commit_graph_data_at(b)->generation; + /* lower generation commits first */ if (generation_a < generation_b) return -1; From patchwork Tue Jul 28 09:13:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688699 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 791B214B7 for ; Tue, 28 Jul 2020 09:14:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5CAA220829 for ; Tue, 28 Jul 2020 09:14:00 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="eq7y3iW8" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728355AbgG1JN7 (ORCPT ); Tue, 28 Jul 2020 05:13:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43314 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728021AbgG1JN6 (ORCPT ); Tue, 28 Jul 2020 05:13:58 -0400 Received: from mail-ej1-x643.google.com (mail-ej1-x643.google.com [IPv6:2a00:1450:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 71C1CC061794 for ; Tue, 28 Jul 2020 02:13:57 -0700 (PDT) Received: by mail-ej1-x643.google.com with SMTP id w9so19876942ejc.8 for ; Tue, 28 Jul 2020 02:13:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=YXG6SyBGOOD+L6+7lkWUgaCbt1pU0UDLL+mn3ynHiH4=; b=eq7y3iW8uBfzAaglz1PfZIsGVTSd7Cb9ucwv1/Bbno1ReYIZgn4QcyCuyCTYQ2Ieqm 74MGPlU+IM390ISUnCkYO0yeuiEUPfcvIlwgEv3M5V0bBj1q/m3bCekQudkwWJ8WroXH iUMEGRm4jRz0HCYcLITstvlNmr/rYRpr3IZGAY3Ui5dlPHw8PB5j40denwfpeMZhOAmC Ts02+J8kB82Ga58N9Y0eiyV3L/kVD2xLfXj2zX2Z8RIbfXkCJ6Eeg4LCc7LdzX6hKD9s PZJv7b0dJ5/ChF0MXaNm9emcRIKwY4AjQrc4DgT9QD0pPmUnIA1qm86RkRQni48NqNii em2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=YXG6SyBGOOD+L6+7lkWUgaCbt1pU0UDLL+mn3ynHiH4=; b=UHehlN+dgKlQDcbgtwfebLTKqqzlpZfngoiuZmZHkboZ+6qXLxc1Jjz1PO+1su3GGR 5vmAJi9RTSwkNyR70XKIN/eenU2fxbcTra8l33K3yiv46Cjku7UFoeicbjdj9DnyWeQ3 RQruBH5oM1xps9iqpZO9RRdhuQwTj7BbivjbjqRd4e8iyW4gkCSyyavnUst2xG7HiUGc IXwyztDASt0HNgUM8Fh+T7ony/LE2Ld1Dlybr49YkmXFA0TXGM9z7P4xDXbpy4LhZEg/ MNcXa5+zHpSM6WoSeIWj4S8Njv7pd/SKksnyfyFH59C1QYksYZblZEahhWfcywZokATp l43g== X-Gm-Message-State: AOAM531WMONkif5qb/Zl0tAqHi7GQS1rceSLZUcVAqRGrXFEEymwj0pA kovHFyFkRsFuFyfJbzX4bHkas5q6 X-Google-Smtp-Source: ABdhPJy3gsPlzw4IpFBqSQJIpUtUeTwY+pAsOf1U3O3o1Zxk6NrPitmTqCcLD9PE2O4FQF330CWlGQ== X-Received: by 2002:a17:906:a284:: with SMTP id i4mr1177259ejz.490.1595927636011; Tue, 28 Jul 2020 02:13:56 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id cf10sm313554ejb.4.2020.07.28.02.13.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:55 -0700 (PDT) Message-Id: In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:47 +0000 Subject: [PATCH 2/6] revision: parse parent in indegree_walk_step() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar In indegree_walk_step(), we add unvisited parents to the indegree queue. However, parents are not guaranteed to be parsed. As the indegree queue sorts by generation number, let's parse parents before inserting them to ensure the correct priority order. Signed-off-by: Abhishek Kumar --- revision.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/revision.c b/revision.c index 6aa7f4f567..23287d26c3 100644 --- a/revision.c +++ b/revision.c @@ -3343,6 +3343,9 @@ static void indegree_walk_step(struct rev_info *revs) struct commit *parent = p->item; int *pi = indegree_slab_at(&info->indegree, parent); + if (parse_commit_gently(parent, 1) < 0) + return ; + if (*pi) (*pi)++; else From patchwork Tue Jul 28 09:13:48 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688701 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E612914B7 for ; Tue, 28 Jul 2020 09:14:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C7D7820809 for ; Tue, 28 Jul 2020 09:14:01 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="PdhBllA5" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728089AbgG1JOA (ORCPT ); Tue, 28 Jul 2020 05:14:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43320 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728321AbgG1JN6 (ORCPT ); Tue, 28 Jul 2020 05:13:58 -0400 Received: from mail-ed1-x541.google.com (mail-ed1-x541.google.com [IPv6:2a00:1450:4864:20::541]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 73FF0C0619D4 for ; Tue, 28 Jul 2020 02:13:58 -0700 (PDT) Received: by mail-ed1-x541.google.com with SMTP id a1so14203201edt.10 for ; Tue, 28 Jul 2020 02:13:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=RUaE+WxBy+3RZnyLvqcNd38rWb9xYJ+kF6E5n7+K2YQ=; b=PdhBllA5RL6Cr+l5Q7cG6oFL1RT0Q46pHxsziaViauEn8/LLz3E/7Z7QJ7XVbFM3UF HWZnQiAdNUUcXVgXfUhVWKpehN7hvlHNSHxHbSAXtGQeEHJAmSSZ6E39swi4Wpc1PeAK ym3SU6YS3XKK2RupcqDuYYBvkp/C6T78HT084tH5n/A9QTwc9Cwjm3WBgP4bka/D8mQT S+Ioc9MvkDuc13JBw2tdHrTmHUJXz+LXtsfu64Gu4MLF6Z6xgX61Y+VcDKlQS/wZA61n ILuZ8BRGTh9z0MsEYlcKjpDTEJXK5Q4thAYBAc+JXTrX/9rAizlg5KJnb8r/Idf2FYz8 DyXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=RUaE+WxBy+3RZnyLvqcNd38rWb9xYJ+kF6E5n7+K2YQ=; b=pKm2eR2Rnb73WsI761AXyXQZV1wkdbfsJMAoiZie+8XCXMnZPLAoIOneV4Zso1/eRM 1VWeehWCdMka1vP25cv0rkYKmXNj/HznYZhWsW/TNatrAc92DN6+rTyVy87FOempX9tW eqZwz2OUMgYh5VO/7U1xt7p631Yd/XL2/CjOIedXY14Q6Ht/OyCA2nPGSAl0NGpmb19h s21Vw8mLhyRUj+fiqpdTglbFNsLwPhwNrOcXKU9oi//g6oeeqCyEoZkZfoIgSWW/ikNU xBWa3zZsVObXo9buv9ttvmTht+ZJ6hKSZqVt4mVTrULKcoq2OE92v8y4ZW3KtMWV+yjf BiKA== X-Gm-Message-State: AOAM531C2BRV/9wfeaIJ+oazpVnSBigGxSVoauwHonMZXx+NNNU/XaSl BCW1piP4cxwDeoc1fmSZN1x/1hnk X-Google-Smtp-Source: ABdhPJwfeQU/lQ+KK8V+RoaR5vnSuAXTZ3Xvh6icduWVx5QcYE7uQL2HDhKX+BpbF70+NHUSj+L7xw== X-Received: by 2002:a50:e689:: with SMTP id z9mr25603243edm.131.1595927637011; Tue, 28 Jul 2020 02:13:57 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h24sm8776360ejk.117.2020.07.28.02.13.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:56 -0700 (PDT) Message-Id: <701f5912369c0fcc07cf604c3129cb5017a125ce.1595927632.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:48 +0000 Subject: [PATCH 3/6] commit-graph: consolidate fill_commit_graph_info Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar Both fill_commit_graph_info() and fill_commit_in_graph() parse information present in commit data chunk. Let's simplify the implementation by calling fill_commit_graph_info() within fill_commit_in_graph(). The test 'generate tar with future mtime' creates a commit with commit time of (2 ^ 36 + 1) seconds since EPOCH. The commit time overflows into generation number and has undefined behavior. The test used to pass as fill_commit_in_graph() did not read commit time from commit graph, reading commit date from odb instead. Let's fix that by setting commit time of (2 ^ 34 - 1) seconds. Signed-off-by: Abhishek Kumar --- commit-graph.c | 31 ++++++++++++------------------- t/t5000-tar-tree.sh | 4 ++-- 2 files changed, 14 insertions(+), 21 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 5d3c9bd23c..204eb454b2 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -735,15 +735,24 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, const unsigned char *commit_data; struct commit_graph_data *graph_data; uint32_t lex_index; + uint64_t date_high, date_low; while (pos < g->num_commits_in_base) g = g->base_graph; + if (pos >= g->num_commits + g->num_commits_in_base) + die(_("invalid commit position. commit-graph is likely corrupt")); + lex_index = pos - g->num_commits_in_base; commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; graph_data = commit_graph_data_at(item); graph_data->graph_pos = pos; + + date_high = get_be32(commit_data + g->hash_len + 8) & 0x3; + date_low = get_be32(commit_data + g->hash_len + 12); + item->date = (timestamp_t)((date_high << 32) | date_low); + graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2; } @@ -758,38 +767,22 @@ static int fill_commit_in_graph(struct repository *r, { uint32_t edge_value; uint32_t *parent_data_ptr; - uint64_t date_low, date_high; struct commit_list **pptr; - struct commit_graph_data *graph_data; const unsigned char *commit_data; uint32_t lex_index; + fill_commit_graph_info(item, g, pos); + while (pos < g->num_commits_in_base) g = g->base_graph; - if (pos >= g->num_commits + g->num_commits_in_base) - die(_("invalid commit position. commit-graph is likely corrupt")); - - /* - * Store the "full" position, but then use the - * "local" position for the rest of the calculation. - */ - graph_data = commit_graph_data_at(item); - graph_data->graph_pos = pos; lex_index = pos - g->num_commits_in_base; - - commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index; + commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; item->object.parsed = 1; set_commit_tree(item, NULL); - date_high = get_be32(commit_data + g->hash_len + 8) & 0x3; - date_low = get_be32(commit_data + g->hash_len + 12); - item->date = (timestamp_t)((date_high << 32) | date_low); - - graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2; - pptr = &item->parents; edge_value = get_be32(commit_data + g->hash_len); diff --git a/t/t5000-tar-tree.sh b/t/t5000-tar-tree.sh index 37655a237c..1986354fc3 100755 --- a/t/t5000-tar-tree.sh +++ b/t/t5000-tar-tree.sh @@ -406,7 +406,7 @@ test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' ' rm -f .git/index && echo content >file && git add file && - GIT_COMMITTER_DATE="@68719476737 +0000" \ + GIT_COMMITTER_DATE="@17179869183 +0000" \ git commit -m "tempori parendum" ' @@ -415,7 +415,7 @@ test_expect_success TIME_IS_64BIT 'generate tar with future mtime' ' ' test_expect_success TAR_HUGE,TIME_IS_64BIT,TIME_T_IS_64BIT 'system tar can read our future mtime' ' - echo 4147 >expect && + echo 2514 >expect && tar_info future.tar | cut -d" " -f2 >actual && test_cmp expect actual ' From patchwork Tue Jul 28 09:13:49 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688703 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 364AE6C1 for ; Tue, 28 Jul 2020 09:14:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1D9AB20829 for ; Tue, 28 Jul 2020 09:14:02 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="S0OZMON5" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728401AbgG1JOB (ORCPT ); Tue, 28 Jul 2020 05:14:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43324 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728353AbgG1JN7 (ORCPT ); Tue, 28 Jul 2020 05:13:59 -0400 Received: from mail-ej1-x643.google.com (mail-ej1-x643.google.com [IPv6:2a00:1450:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 22749C061794 for ; Tue, 28 Jul 2020 02:13:59 -0700 (PDT) Received: by mail-ej1-x643.google.com with SMTP id g7so11622623ejw.12 for ; Tue, 28 Jul 2020 02:13:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=hocohXiKSKJ8SJvTHe8NNCewPtWLSpIgIep9ENjbdEU=; b=S0OZMON5rW+ikoJHfHVE/M2KUnBNllrAY/fc4NAAPMJjp2b9YohLIP/rgHHi1EzWY/ ARefRAqh7BpGvBwRlj5hjh0L4xe2PwEUsC0Aff5hz4AIhCjJnTOynkWzr/ZHz8kuGoaB WhIm3Eno8J+9xYLx/gsJ9eeQ6pVph99FNg9crl7NpfEojHVwot55wRTB5ibK8OKjgeH/ sUUj7hRtWrF9i+ePoeL7VevrFVYdsid7dVxzRRAK137CX4n//xPA4FPG5wY+OUFJIpSZ deszNMcAY7sYaAN3zmRDpA+vho38yYdYn3rPFKtf9F7YOSsoUVI4NkUG2dvYSmt2Ji3I NA2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=hocohXiKSKJ8SJvTHe8NNCewPtWLSpIgIep9ENjbdEU=; b=CbH5DYdPGf+FJw2NaHyp4gW+xO7iOIZeoMTH5GglkRac7YD1KoacrCf+y4PBwM8hFj U+ZOedsXoh2n2ER4TKHJR0y4RKiDKi82b49iKfdOpkYaNb/xcGZs5J99hMtF/wVWgaY6 zxuFJlFWhr69q0BSlUZtqQ2qGlWEERs7nKTA8jzxEQWVr2GZGIl1qr9ngII4HVCA9yCL FTDkT4RxijRLvfjXcRdAi5Ih4EiSfC5J5G8FWBF5JzPTI+Otk0KyBRvKRVtsKwm9wMHY HYtGt+8EzVVqWrEfBB1dPoVfDBsMI00ADO30w5uLRf7epsgHFI8fZh1gwTlwZS1dHBSq /CaQ== X-Gm-Message-State: AOAM532EZZLbXfrg4uHefBmZSWbFALzlPoxgUBY36WCB1SBqiKRG7hNr uEtPHqaUgIWXYB0qtx5AfQcjwuQe X-Google-Smtp-Source: ABdhPJwXuvLEvLvgvpe+1suJ2GAWHjfF3aDeBQuCDZodynfs13m7GFoV2laDsiYPy+fHDXObDZB2tA== X-Received: by 2002:a17:906:a88b:: with SMTP id ha11mr8913620ejb.545.1595927637730; Tue, 28 Jul 2020 02:13:57 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id u13sm8606401ejc.72.2020.07.28.02.13.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:57 -0700 (PDT) Message-Id: <812fe75fc7252db0b7b6604f84b17dcf7324b922.1595927632.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:49 +0000 Subject: [PATCH 4/6] commit-graph: consolidate compare_commits_by_gen Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar Comparing commits by generation has been independently defined twice, in commit-reach and commit. Let's simplify the implementation by moving compare_commits_by_gen() to commit-graph. Signed-off-by: Abhishek Kumar --- commit-graph.c | 15 +++++++++++++++ commit-graph.h | 2 ++ commit-reach.c | 15 --------------- commit.c | 9 +++------ 4 files changed, 20 insertions(+), 21 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 204eb454b2..1c98f38d69 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -112,6 +112,21 @@ uint32_t commit_graph_generation(const struct commit *c) return data->generation; } +int compare_commits_by_gen(const void *_a, const void *_b) +{ + const struct commit *a = _a, *b = _b; + const uint32_t generation_a = commit_graph_generation(a); + const uint32_t generation_b = commit_graph_generation(b); + + /* older commits first */ + if (generation_a < generation_b) + return -1; + else if (generation_a > generation_b) + return 1; + + return 0; +} + static struct commit_graph_data *commit_graph_data_at(const struct commit *c) { unsigned int i, nth_slab; diff --git a/commit-graph.h b/commit-graph.h index 28f89cdf3e..98cc5a3b9d 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -145,4 +145,6 @@ struct commit_graph_data { */ uint32_t commit_graph_generation(const struct commit *); uint32_t commit_graph_position(const struct commit *); + +int compare_commits_by_gen(const void *_a, const void *_b); #endif diff --git a/commit-reach.c b/commit-reach.c index efd5925cbb..c83cc291e7 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -561,21 +561,6 @@ int commit_contains(struct ref_filter *filter, struct commit *commit, return repo_is_descendant_of(the_repository, commit, list); } -static int compare_commits_by_gen(const void *_a, const void *_b) -{ - const struct commit *a = *(const struct commit * const *)_a; - const struct commit *b = *(const struct commit * const *)_b; - - uint32_t generation_a = commit_graph_generation(a); - uint32_t generation_b = commit_graph_generation(b); - - if (generation_a < generation_b) - return -1; - if (generation_a > generation_b) - return 1; - return 0; -} - int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, diff --git a/commit.c b/commit.c index 7128895c3a..bed63b41fb 100644 --- a/commit.c +++ b/commit.c @@ -731,14 +731,11 @@ int compare_commits_by_author_date(const void *a_, const void *b_, int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused) { const struct commit *a = a_, *b = b_; - const uint32_t generation_a = commit_graph_generation(a), - generation_b = commit_graph_generation(b); + int ret_val = compare_commits_by_gen(a_, b_); /* newer commits first */ - if (generation_a < generation_b) - return 1; - else if (generation_a > generation_b) - return -1; + if (ret_val) + return -ret_val; /* use date as a heuristic when generations are equal */ if (a->date < b->date) From patchwork Tue Jul 28 09:13:50 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688705 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7621014B7 for ; Tue, 28 Jul 2020 09:14:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 58A3420809 for ; Tue, 28 Jul 2020 09:14:04 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nIISqK6B" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728408AbgG1JOD (ORCPT ); Tue, 28 Jul 2020 05:14:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43328 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728021AbgG1JOA (ORCPT ); Tue, 28 Jul 2020 05:14:00 -0400 Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com [IPv6:2a00:1450:4864:20::632]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0EF88C0619D2 for ; Tue, 28 Jul 2020 02:14:00 -0700 (PDT) Received: by mail-ej1-x632.google.com with SMTP id g7so11622659ejw.12 for ; Tue, 28 Jul 2020 02:13:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=+QbQ4QN29IH+0n3m+pbzSTcH1/8qcpMXDpD82L37N+M=; b=nIISqK6B200UFI5RIhcnTzI4uxbdKhgAb5UsoNDwdfHJkefOm1Fmzv02ZpGvaCBibz +VS5QtiEeBkI/sslMIYfQb+LCWbFM7VYIQhjVi1qRgiR3h0Y5YytSXRzY8uLG7BzGJok CKmU5mFleRNzOmFWdbP/YQuMi9sl8JFm22wZyWAhL7dCqqn2IQuoWHElkf8FWp1PfOKU 3KP9bO68VOmHUrqqVbwdM+Cvt6TVpQNwxCA1uJjQUng7MxR0UpewPWs6vN4UukNrYmbx XTyk4kJf/VxYTX2bTqfuuwuuT6JkcEpWS2GuUqeFelN7E25MQqR4YR5QfH1HME4sbdHW KfoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=+QbQ4QN29IH+0n3m+pbzSTcH1/8qcpMXDpD82L37N+M=; b=DpG5oXuoEHaxEQK8oQdIOBUpeHsue2rWePNIWwlutsQaH/foE+VEWWARLHdHu63LI/ M4M0XAvGXsTtiDJV3hun6xVTqqahr39On4pqE44dl9rKGGZoh0+Jzxwkrf6+PD1s5dw6 Cingu0duzq3QvtwVkHznD2Rj3zqs1Ly/Z8mRowS3hxEpNztjGMPRD8J+EaJZgqB4uNGu ncgMSsmNocLYsj70BC187hDQknHOteIEdTUx4NlH84f41nu0xYWcjKfnHQpFpck3W1g1 43klhCX+ms2zB3fdmnyDQggQ3F/t7f1JQPXAe++f19emKQn04G8ujzHbzI5w8ZYyQ1zQ HDFw== X-Gm-Message-State: AOAM5311P6wy9yz1uitJcgOcz7SmwSaHxxYUxaebtgN5SpVEknRRELhj H66BqtRCD61Rr6leVeTBKD8zBEzw X-Google-Smtp-Source: ABdhPJxh/3GRn91IroOaHVVLUOnHuc6q5GIztyPw8fPcle2dsNsmRbwEWuRZHqsKvU1eSGwtgdMfGg== X-Received: by 2002:a17:906:594c:: with SMTP id g12mr24549236ejr.255.1595927638487; Tue, 28 Jul 2020 02:13:58 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h18sm9513872edw.56.2020.07.28.02.13.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:57 -0700 (PDT) Message-Id: <80ea7da3435396edcb19423ab602962d31585209.1595927632.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:50 +0000 Subject: [PATCH 5/6] commit-graph: implement generation data chunk Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar One of the essential pre-requisites before implementing generation number as to distinguish between generation numbers v1 and v2 while still being compatible with old Git. We are going to introduce a new chunk called Generation Data chunk (or GDAT). GDAT stores generation number v2 (and any subsequent versions), whereas CDAT will still store topological level. Old Git does not understand GDAT chunk and would ignore it, reading topological levels from CDAT. Newer versions of Git can parse GDAT and take advantage of newer generation numbers, falling back to topological levels when GDAT chunk is missing (as it would happen with a commit graph written by old Git). Signed-off-by: Abhishek Kumar --- commit-graph.c | 33 +++++++++++++++++++++++++++++---- commit-graph.h | 1 + t/helper/test-read-graph.c | 2 ++ t/t4216-log-bloom.sh | 4 ++-- t/t5318-commit-graph.sh | 19 +++++++++++-------- t/t5324-split-commit-graph.sh | 12 ++++++------ 6 files changed, 51 insertions(+), 20 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 1c98f38d69..ab714f4a76 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -38,11 +38,12 @@ void git_test_write_commit_graph_or_die(void) #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */ #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */ #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */ +#define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */ #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */ #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */ #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */ #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */ -#define MAX_NUM_CHUNKS 7 +#define MAX_NUM_CHUNKS 8 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16) @@ -389,6 +390,13 @@ struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size) graph->chunk_commit_data = data + chunk_offset; break; + case GRAPH_CHUNKID_GENERATION_DATA: + if (graph->chunk_generation_data) + chunk_repeated = 1; + else + graph->chunk_generation_data = data + chunk_offset; + break; + case GRAPH_CHUNKID_EXTRAEDGES: if (graph->chunk_extra_edges) chunk_repeated = 1; @@ -768,7 +776,10 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, date_low = get_be32(commit_data + g->hash_len + 12); item->date = (timestamp_t)((date_high << 32) | date_low); - graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2; + if (g->chunk_generation_data) + graph_data->generation = get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index); + else + graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2; } static inline void set_commit_tree(struct commit *c, struct tree *t) @@ -1100,6 +1111,17 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len, } } +static void write_graph_chunk_generation_data(struct hashfile *f, + struct write_commit_graph_context *ctx) +{ + struct commit **list = ctx->commits.list; + int count; + for (count = 0; count < ctx->commits.nr; count++, list++) { + display_progress(ctx->progress, ++ctx->progress_cnt); + hashwrite_be32(f, commit_graph_data_at(*list)->generation); + } +} + static void write_graph_chunk_extra_edges(struct hashfile *f, struct write_commit_graph_context *ctx) { @@ -1605,7 +1627,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1]; const unsigned hashsz = the_hash_algo->rawsz; struct strbuf progress_title = STRBUF_INIT; - int num_chunks = 3; + int num_chunks = 4; struct object_id file_hash; const struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS; @@ -1656,6 +1678,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT; chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP; chunk_ids[2] = GRAPH_CHUNKID_DATA; + chunk_ids[3] = GRAPH_CHUNKID_GENERATION_DATA; if (ctx->num_extra_edges) { chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES; num_chunks++; @@ -1677,8 +1700,9 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE; chunk_offsets[2] = chunk_offsets[1] + hashsz * ctx->commits.nr; chunk_offsets[3] = chunk_offsets[2] + (hashsz + 16) * ctx->commits.nr; + chunk_offsets[4] = chunk_offsets[3] + sizeof(uint32_t) * ctx->commits.nr; - num_chunks = 3; + num_chunks = 4; if (ctx->num_extra_edges) { chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] + 4 * ctx->num_extra_edges; @@ -1728,6 +1752,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx) write_graph_chunk_fanout(f, ctx); write_graph_chunk_oids(f, hashsz, ctx); write_graph_chunk_data(f, hashsz, ctx); + write_graph_chunk_generation_data(f, ctx); if (ctx->num_extra_edges) write_graph_chunk_extra_edges(f, ctx); if (ctx->changed_paths) { diff --git a/commit-graph.h b/commit-graph.h index 98cc5a3b9d..e3d4ba96f4 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -67,6 +67,7 @@ struct commit_graph { const uint32_t *chunk_oid_fanout; const unsigned char *chunk_oid_lookup; const unsigned char *chunk_commit_data; + const unsigned char *chunk_generation_data; const unsigned char *chunk_extra_edges; const unsigned char *chunk_base_graphs; const unsigned char *chunk_bloom_indexes; diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 6d0c962438..1c2a5366c7 100644 --- a/t/helper/test-read-graph.c +++ b/t/helper/test-read-graph.c @@ -32,6 +32,8 @@ int cmd__read_graph(int argc, const char **argv) printf(" oid_lookup"); if (graph->chunk_commit_data) printf(" commit_metadata"); + if (graph->chunk_generation_data) + printf(" generation_data"); if (graph->chunk_extra_edges) printf(" extra_edges"); if (graph->chunk_bloom_indexes) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index c855bcd3e7..780855e691 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -33,11 +33,11 @@ test_expect_success 'setup test - repo, commits, commit graph, log outputs' ' git commit-graph write --reachable --changed-paths ' graph_read_expect () { - NUM_CHUNKS=5 + NUM_CHUNKS=6 cat >expect <<- EOF header: 43475048 1 1 $NUM_CHUNKS 0 num_commits: $1 - chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data + chunks: oid_fanout oid_lookup commit_metadata generation_data bloom_indexes bloom_data EOF test-tool read-graph >actual && test_cmp expect actual diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh index 26f332d6a3..3ec5248d70 100755 --- a/t/t5318-commit-graph.sh +++ b/t/t5318-commit-graph.sh @@ -71,16 +71,16 @@ graph_git_behavior 'no graph' full commits/3 commits/1 graph_read_expect() { OPTIONAL="" - NUM_CHUNKS=3 + NUM_CHUNKS=4 if test ! -z $2 then OPTIONAL=" $2" - NUM_CHUNKS=$((3 + $(echo "$2" | wc -w))) + NUM_CHUNKS=$((4 + $(echo "$2" | wc -w))) fi cat >expect <<- EOF header: 43475048 1 1 $NUM_CHUNKS 0 num_commits: $1 - chunks: oid_fanout oid_lookup commit_metadata$OPTIONAL + chunks: oid_fanout oid_lookup commit_metadata generation_data$OPTIONAL EOF test-tool read-graph >output && test_cmp expect output @@ -433,7 +433,7 @@ GRAPH_BYTE_HASH=5 GRAPH_BYTE_CHUNK_COUNT=6 GRAPH_CHUNK_LOOKUP_OFFSET=8 GRAPH_CHUNK_LOOKUP_WIDTH=12 -GRAPH_CHUNK_LOOKUP_ROWS=5 +GRAPH_CHUNK_LOOKUP_ROWS=6 GRAPH_BYTE_OID_FANOUT_ID=$GRAPH_CHUNK_LOOKUP_OFFSET GRAPH_BYTE_OID_LOOKUP_ID=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \ 1 * $GRAPH_CHUNK_LOOKUP_WIDTH)) @@ -451,11 +451,14 @@ GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET GRAPH_BYTE_COMMIT_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN)) GRAPH_BYTE_COMMIT_EXTRA_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 4)) GRAPH_BYTE_COMMIT_WRONG_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 3)) -GRAPH_BYTE_COMMIT_GENERATION=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 11)) GRAPH_BYTE_COMMIT_DATE=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 12)) GRAPH_COMMIT_DATA_WIDTH=$(($HASH_LEN + 16)) -GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \ - $GRAPH_COMMIT_DATA_WIDTH * $NUM_COMMITS)) +GRAPH_GENERATION_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \ + $GRAPH_COMMIT_DATA_WIDTH * $NUM_COMMITS)) +GRAPH_GENERATION_DATA_WIDTH=4 +GRAPH_BYTE_COMMIT_GENERATION=$(($GRAPH_GENERATION_DATA_OFFSET + 3)) +GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_GENERATION_DATA_OFFSET + \ + $GRAPH_GENERATION_DATA_WIDTH * $NUM_COMMITS)) GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4)) GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 * $NUM_OCTOPUS_EDGES)) @@ -594,7 +597,7 @@ test_expect_success 'detect incorrect generation number' ' ' test_expect_success 'detect incorrect generation number' ' - corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \ + corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\00" \ "non-zero generation number" ' diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh index 269d0964a3..096a96ec41 100755 --- a/t/t5324-split-commit-graph.sh +++ b/t/t5324-split-commit-graph.sh @@ -14,11 +14,11 @@ test_expect_success 'setup repo' ' graphdir="$infodir/commit-graphs" && test_oid_init && test_oid_cache <<-EOM - shallow sha1:1760 - shallow sha256:2064 + shallow sha1:2132 + shallow sha256:2436 - base sha1:1376 - base sha256:1496 + base sha1:1408 + base sha256:1528 EOM ' @@ -29,9 +29,9 @@ graph_read_expect() { NUM_BASE=$2 fi cat >expect <<- EOF - header: 43475048 1 1 3 $NUM_BASE + header: 43475048 1 1 4 $NUM_BASE num_commits: $1 - chunks: oid_fanout oid_lookup commit_metadata + chunks: oid_fanout oid_lookup commit_metadata generation_data EOF test-tool read-graph >output && test_cmp expect output From patchwork Tue Jul 28 09:13:51 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Koji Nakamaru via GitGitGadget X-Patchwork-Id: 11688707 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 80B396C1 for ; Tue, 28 Jul 2020 09:14:06 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5B21220829 for ; Tue, 28 Jul 2020 09:14:06 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="LFUkHBpD" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728422AbgG1JOF (ORCPT ); Tue, 28 Jul 2020 05:14:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43338 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728412AbgG1JOE (ORCPT ); Tue, 28 Jul 2020 05:14:04 -0400 Received: from mail-ej1-x641.google.com (mail-ej1-x641.google.com [IPv6:2a00:1450:4864:20::641]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A2F44C061794 for ; Tue, 28 Jul 2020 02:14:03 -0700 (PDT) Received: by mail-ej1-x641.google.com with SMTP id f14so4036840ejb.2 for ; Tue, 28 Jul 2020 02:14:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=lXy8OcRedLF4T4FMt2eLZyM4PAHRZUHBX9qp/tT3IaY=; b=LFUkHBpDyQR8EM1R9j2Eim9gKyRoCekBPzW51jF2LUXwEXv/JDjuvz01TjkOdiRXM1 xZg4Id/n3g6jco1ccEMJyN621M8aAuzi7IsTBOE3NgDK3NXjJcfGWz7rE7XAWVKKzDAz Yao8yst6ZnSRgQffRe45qkhHOj7GBZOaaPrhjezZ+rlF15frU5SCSYYp6jMJ1PHTD5M7 sytYY9MKDf0HDKMs1KiRvrCFOjzaTv3NDV1+TjR4DhtpuTJaMf6ooq7gOtvXnUnZRg6X Lw3ktAL5ecGWtFb4lqN7Hzn9pswn4G2ysMLNa4Un8YpKDm7/cziqkCdIuPx2+M5DRGUp yKOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=lXy8OcRedLF4T4FMt2eLZyM4PAHRZUHBX9qp/tT3IaY=; b=lqb1B9e3TOjAQaz15uSCh7FEdJ+gbQpSH66+21BlEykUbM8NiOPDDqR3JceMeUnTYu bgGfdb5ynI8FpBJWRxiaym4ef6xtsYunbKoom4U0bB95Gjid6fUBF01wvBueemRXVhCx OR4zmmfpLlpiYk7SL/yi0dInGM23UkQ/RlGYsm2IF+7M2ko7weyOM0BwR/xLFVj0YRCw cUfV27fYfkx4tyBJZVZLCuDCGzN+9VAUWtR5L3dq7WeuAZJoC7kGsvS+GuEKCX+GRSDm siVEP0LuNndAddRnhPrRfJmYsmF7k3wr+z23fabjoT3ThLmIbUaiD5FA/iUPZ2Ueg4II hgMQ== X-Gm-Message-State: AOAM532g0kgwrnOs4/pMGYpyXaXbi2leTwuJ9z8Co+isUY/xR1UujtmR Nv9EalFkvw87cd9Z616dzd6NBd6o X-Google-Smtp-Source: ABdhPJzdVPPk3hkHauLzN5UkhL8hcwNoGNLEDyGWWR1h+L6XnG94Sk6XAttF6qJ8dr1iy/YAeXk7nQ== X-Received: by 2002:a17:906:4e14:: with SMTP id z20mr19443717eju.541.1595927641852; Tue, 28 Jul 2020 02:14:01 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id dh16sm9221192edb.3.2020.07.28.02.13.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Jul 2020 02:13:58 -0700 (PDT) Message-Id: <647290d0368e385227614dd1822aa9083b0dba5e.1595927632.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Abhishek Kumar via GitGitGadget" Date: Tue, 28 Jul 2020 09:13:51 +0000 Subject: [PATCH 6/6] commit-graph: implement corrected commit date offset Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Derrick Stolee , Jakub =?utf-8?b?TmFyxJlic2tp?= , Abhishek Kumar , Abhishek Kumar Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhishek Kumar With preparations done, let's implement corrected commit date offset. We add a new commit-slab to store topological levels while writing commit graph and upgrade number of struct commit_graph_data to 64-bits. We have to touch many files, upgrading generation number from uint32_t to timestamp_t. We drop 'detect incorrect generation number' from t5318-commit-graph.sh, which tests if verify can detect if a commit graph have GENERATION_NUMBER_ZERO for a commit, followed by a non-zero generation. With corrected commit dates, GENERATION_NUMBER_ZERO is possible only if one of dates is Unix epoch zero. Signed-off-by: Abhishek Kumar --- blame.c | 2 +- commit-graph.c | 109 ++++++++++++++++++++++------------------ commit-graph.h | 4 +- commit-reach.c | 32 ++++++------ commit-reach.h | 2 +- commit.h | 3 ++ revision.c | 14 +++--- t/t5318-commit-graph.sh | 2 +- upload-pack.c | 2 +- 9 files changed, 93 insertions(+), 77 deletions(-) diff --git a/blame.c b/blame.c index 82fa16d658..48aa632461 100644 --- a/blame.c +++ b/blame.c @@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r, if (!bd) return 1; - if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY) + if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_V2_INFINITY) return 1; filter = get_bloom_filter(r, origin->commit, 0); diff --git a/commit-graph.c b/commit-graph.c index ab714f4a76..9647d9f0df 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -65,6 +65,8 @@ void git_test_write_commit_graph_or_die(void) /* Remember to update object flag allocation in object.h */ #define REACHABLE (1u<<15) +define_commit_slab(topo_level_slab, uint32_t); + /* Keep track of the order in which commits are added to our list. */ define_commit_slab(commit_pos, int); static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos); @@ -100,15 +102,15 @@ uint32_t commit_graph_position(const struct commit *c) return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH; } -uint32_t commit_graph_generation(const struct commit *c) +timestamp_t commit_graph_generation(const struct commit *c) { struct commit_graph_data *data = commit_graph_data_slab_peek(&commit_graph_data_slab, c); if (!data) - return GENERATION_NUMBER_INFINITY; + return GENERATION_NUMBER_V2_INFINITY; else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH) - return GENERATION_NUMBER_INFINITY; + return GENERATION_NUMBER_V2_INFINITY; return data->generation; } @@ -116,8 +118,8 @@ uint32_t commit_graph_generation(const struct commit *c) int compare_commits_by_gen(const void *_a, const void *_b) { const struct commit *a = _a, *b = _b; - const uint32_t generation_a = commit_graph_generation(a); - const uint32_t generation_b = commit_graph_generation(b); + const timestamp_t generation_a = commit_graph_generation(a); + const timestamp_t generation_b = commit_graph_generation(b); /* older commits first */ if (generation_a < generation_b) @@ -160,8 +162,8 @@ static int commit_gen_cmp(const void *va, const void *vb) const struct commit *a = *(const struct commit **)va; const struct commit *b = *(const struct commit **)vb; - uint32_t generation_a = commit_graph_data_at(a)->generation; - uint32_t generation_b = commit_graph_data_at(b)->generation; + timestamp_t generation_a = commit_graph_data_at(a)->generation; + timestamp_t generation_b = commit_graph_data_at(b)->generation; /* lower generation commits first */ if (generation_a < generation_b) @@ -169,11 +171,6 @@ static int commit_gen_cmp(const void *va, const void *vb) else if (generation_a > generation_b) return 1; - /* use date as a heuristic when generations are equal */ - if (a->date < b->date) - return -1; - else if (a->date > b->date) - return 1; return 0; } @@ -777,8 +774,13 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, item->date = (timestamp_t)((date_high << 32) | date_low); if (g->chunk_generation_data) - graph_data->generation = get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index); + { + /* Read corrected commit date offset from GDAT */ + graph_data->generation = item->date + + (timestamp_t) get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index); + } else + /* Read topological level from CDAT */ graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2; } @@ -950,6 +952,7 @@ struct write_commit_graph_context { struct progress *progress; int progress_done; uint64_t progress_cnt; + struct topo_level_slab *topo_levels; char *base_graph_name; int num_commit_graphs_before; @@ -1102,7 +1105,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len, else packedDate[0] = 0; - packedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2); + packedDate[0] |= htonl(*topo_level_slab_at(ctx->topo_levels, *list) << 2); packedDate[1] = htonl((*list)->date); hashwrite(f, packedDate, 8); @@ -1117,8 +1120,13 @@ static void write_graph_chunk_generation_data(struct hashfile *f, struct commit **list = ctx->commits.list; int count; for (count = 0; count < ctx->commits.nr; count++, list++) { + timestamp_t offset = commit_graph_data_at(*list)->generation - (*list)->date; display_progress(ctx->progress, ++ctx->progress_cnt); - hashwrite_be32(f, commit_graph_data_at(*list)->generation); + + if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) + offset = GENERATION_NUMBER_V2_OFFSET_MAX; + + hashwrite_be32(f, offset); } } @@ -1316,7 +1324,7 @@ static void close_reachable(struct write_commit_graph_context *ctx) stop_progress(&ctx->progress); } -static void compute_generation_numbers(struct write_commit_graph_context *ctx) +static void compute_corrected_commit_date_offsets(struct write_commit_graph_context *ctx) { int i; struct commit_list *list = NULL; @@ -1326,11 +1334,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) _("Computing commit graph generation numbers"), ctx->commits.nr); for (i = 0; i < ctx->commits.nr; i++) { - uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation; + uint32_t topo_level = *topo_level_slab_at(ctx->topo_levels, ctx->commits.list[i]); display_progress(ctx->progress, i + 1); - if (generation != GENERATION_NUMBER_INFINITY && - generation != GENERATION_NUMBER_ZERO) + if (topo_level != GENERATION_NUMBER_INFINITY && + topo_level != GENERATION_NUMBER_ZERO) continue; commit_list_insert(ctx->commits.list[i], &list); @@ -1338,29 +1346,38 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) struct commit *current = list->item; struct commit_list *parent; int all_parents_computed = 1; - uint32_t max_generation = 0; + uint32_t max_level = 0; + timestamp_t max_corrected_commit_date = current->date; for (parent = current->parents; parent; parent = parent->next) { - generation = commit_graph_data_at(parent->item)->generation; + topo_level = *topo_level_slab_at(ctx->topo_levels, parent->item); - if (generation == GENERATION_NUMBER_INFINITY || - generation == GENERATION_NUMBER_ZERO) { + if (topo_level == GENERATION_NUMBER_INFINITY || + topo_level == GENERATION_NUMBER_ZERO) { all_parents_computed = 0; commit_list_insert(parent->item, &list); break; - } else if (generation > max_generation) { - max_generation = generation; + } else { + struct commit_graph_data *data = commit_graph_data_at(parent->item); + + if (topo_level > max_level) + max_level = topo_level; + + if (data->generation > max_corrected_commit_date) + max_corrected_commit_date = data->generation; } } if (all_parents_computed) { struct commit_graph_data *data = commit_graph_data_at(current); - data->generation = max_generation + 1; - pop_commit(&list); + if (max_level > GENERATION_NUMBER_MAX - 1) + max_level = GENERATION_NUMBER_MAX - 1; + + *topo_level_slab_at(ctx->topo_levels, current) = max_level + 1; + data->generation = max_corrected_commit_date + 1; - if (data->generation > GENERATION_NUMBER_MAX) - data->generation = GENERATION_NUMBER_MAX; + pop_commit(&list); } } } @@ -2085,6 +2102,7 @@ int write_commit_graph(struct object_directory *odb, uint32_t i, count_distinct = 0; int res = 0; int replace = 0; + struct topo_level_slab topo_levels; if (!commit_graph_compatible(the_repository)) return 0; @@ -2099,6 +2117,9 @@ int write_commit_graph(struct object_directory *odb, ctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0; ctx->total_bloom_filter_data_size = 0; + init_topo_level_slab(&topo_levels); + ctx->topo_levels = &topo_levels; + if (ctx->split) { struct commit_graph *g; prepare_commit_graph(ctx->r); @@ -2197,7 +2218,7 @@ int write_commit_graph(struct object_directory *odb, } else ctx->num_commit_graphs_after = 1; - compute_generation_numbers(ctx); + compute_corrected_commit_date_offsets(ctx); if (ctx->changed_paths) compute_bloom_filters(ctx); @@ -2325,8 +2346,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) for (i = 0; i < g->num_commits; i++) { struct commit *graph_commit, *odb_commit; struct commit_list *graph_parents, *odb_parents; - uint32_t max_generation = 0; - uint32_t generation; + timestamp_t max_parent_corrected_commit_date = 0; + timestamp_t corrected_commit_date; display_progress(progress, i + 1); hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i); @@ -2365,9 +2386,9 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) oid_to_hex(&graph_parents->item->object.oid), oid_to_hex(&odb_parents->item->object.oid)); - generation = commit_graph_generation(graph_parents->item); - if (generation > max_generation) - max_generation = generation; + corrected_commit_date = commit_graph_generation(graph_parents->item); + if (corrected_commit_date > max_parent_corrected_commit_date) + max_parent_corrected_commit_date = corrected_commit_date; graph_parents = graph_parents->next; odb_parents = odb_parents->next; @@ -2389,20 +2410,12 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) if (generation_zero == GENERATION_ZERO_EXISTS) continue; - /* - * If one of our parents has generation GENERATION_NUMBER_MAX, then - * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid - * extra logic in the following condition. - */ - if (max_generation == GENERATION_NUMBER_MAX) - max_generation--; - - generation = commit_graph_generation(graph_commit); - if (generation != max_generation + 1) - graph_report(_("commit-graph generation for commit %s is %u != %u"), + corrected_commit_date = commit_graph_generation(graph_commit); + if (corrected_commit_date < max_parent_corrected_commit_date + 1) + graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime), oid_to_hex(&cur_oid), - generation, - max_generation + 1); + corrected_commit_date, + max_parent_corrected_commit_date + 1); if (graph_commit->date != odb_commit->date) graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime), diff --git a/commit-graph.h b/commit-graph.h index e3d4ba96f4..20c5848587 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -138,13 +138,13 @@ void disable_commit_graph(struct repository *r); struct commit_graph_data { uint32_t graph_pos; - uint32_t generation; + timestamp_t generation; }; /* * Commits should be parsed before accessing generation, graph positions. */ -uint32_t commit_graph_generation(const struct commit *); +timestamp_t commit_graph_generation(const struct commit *); uint32_t commit_graph_position(const struct commit *); int compare_commits_by_gen(const void *_a, const void *_b); diff --git a/commit-reach.c b/commit-reach.c index c83cc291e7..2ce9867ff3 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -32,12 +32,12 @@ static int queue_has_nonstale(struct prio_queue *queue) static struct commit_list *paint_down_to_common(struct repository *r, struct commit *one, int n, struct commit **twos, - int min_generation) + timestamp_t min_generation) { struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; struct commit_list *result = NULL; int i; - uint32_t last_gen = GENERATION_NUMBER_INFINITY; + timestamp_t last_gen = GENERATION_NUMBER_V2_INFINITY; if (!min_generation) queue.compare = compare_commits_by_commit_date; @@ -58,10 +58,10 @@ static struct commit_list *paint_down_to_common(struct repository *r, struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; int flags; - uint32_t generation = commit_graph_generation(commit); + timestamp_t generation = commit_graph_generation(commit); if (min_generation && generation > last_gen) - BUG("bad generation skip %8x > %8x at %s", + BUG("bad generation skip %"PRItime" > %"PRItime" at %s", generation, last_gen, oid_to_hex(&commit->object.oid)); last_gen = generation; @@ -177,12 +177,12 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt repo_parse_commit(r, array[i]); for (i = 0; i < cnt; i++) { struct commit_list *common; - uint32_t min_generation = commit_graph_generation(array[i]); + timestamp_t min_generation = commit_graph_generation(array[i]); if (redundant[i]) continue; for (j = filled = 0; j < cnt; j++) { - uint32_t curr_generation; + timestamp_t curr_generation; if (i == j || redundant[j]) continue; filled_index[filled] = j; @@ -321,7 +321,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, { struct commit_list *bases; int ret = 0, i; - uint32_t generation, min_generation = GENERATION_NUMBER_INFINITY; + timestamp_t generation, min_generation = GENERATION_NUMBER_V2_INFINITY; if (repo_parse_commit(r, commit)) return ret; @@ -470,7 +470,7 @@ static int in_commit_list(const struct commit_list *want, struct commit *c) static enum contains_result contains_test(struct commit *candidate, const struct commit_list *want, struct contains_cache *cache, - uint32_t cutoff) + timestamp_t cutoff) { enum contains_result *cached = contains_cache_at(cache, candidate); @@ -506,11 +506,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate, { struct contains_stack contains_stack = { 0, 0, NULL }; enum contains_result result; - uint32_t cutoff = GENERATION_NUMBER_INFINITY; + timestamp_t cutoff = GENERATION_NUMBER_V2_INFINITY; const struct commit_list *p; for (p = want; p; p = p->next) { - uint32_t generation; + timestamp_t generation; struct commit *c = p->item; load_commit_graph_info(the_repository, c); generation = commit_graph_generation(c); @@ -565,7 +565,7 @@ int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, time_t min_commit_date, - uint32_t min_generation) + timestamp_t min_generation) { struct commit **list = NULL; int i; @@ -666,13 +666,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0; struct commit_list *from_iter = from, *to_iter = to; int result; - uint32_t min_generation = GENERATION_NUMBER_INFINITY; + timestamp_t min_generation = GENERATION_NUMBER_V2_INFINITY; while (from_iter) { add_object_array(&from_iter->item->object, NULL, &from_objs); if (!parse_commit(from_iter->item)) { - uint32_t generation; + timestamp_t generation; if (from_iter->item->date < min_commit_date) min_commit_date = from_iter->item->date; @@ -686,7 +686,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, while (to_iter) { if (!parse_commit(to_iter->item)) { - uint32_t generation; + timestamp_t generation; if (to_iter->item->date < min_commit_date) min_commit_date = to_iter->item->date; @@ -726,13 +726,13 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit_list *found_commits = NULL; struct commit **to_last = to + nr_to; struct commit **from_last = from + nr_from; - uint32_t min_generation = GENERATION_NUMBER_INFINITY; + timestamp_t min_generation = GENERATION_NUMBER_V2_INFINITY; int num_to_find = 0; struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; for (item = to; item < to_last; item++) { - uint32_t generation; + timestamp_t generation; struct commit *c = *item; parse_commit(c); diff --git a/commit-reach.h b/commit-reach.h index b49ad71a31..148b56fea5 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -87,7 +87,7 @@ int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, time_t min_commit_date, - uint32_t min_generation); + timestamp_t min_generation); int can_all_from_reach(struct commit_list *from, struct commit_list *to, int commit_date_cutoff); diff --git a/commit.h b/commit.h index e901538909..dd17a81672 100644 --- a/commit.h +++ b/commit.h @@ -15,6 +15,9 @@ #define GENERATION_NUMBER_MAX 0x3FFFFFFF #define GENERATION_NUMBER_ZERO 0 +#define GENERATION_NUMBER_V2_INFINITY ((1ULL << 63) - 1) +#define GENERATION_NUMBER_V2_OFFSET_MAX 0xFFFFFFFF + struct commit_list { struct commit *item; struct commit_list *next; diff --git a/revision.c b/revision.c index 23287d26c3..b978e79601 100644 --- a/revision.c +++ b/revision.c @@ -725,7 +725,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs, if (!revs->repo->objects->commit_graph) return -1; - if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY) + if (commit_graph_generation(commit) == GENERATION_NUMBER_V2_INFINITY) return -1; filter = get_bloom_filter(revs->repo, commit, 0); @@ -3270,7 +3270,7 @@ define_commit_slab(indegree_slab, int); define_commit_slab(author_date_slab, timestamp_t); struct topo_walk_info { - uint32_t min_generation; + timestamp_t min_generation; struct prio_queue explore_queue; struct prio_queue indegree_queue; struct prio_queue topo_queue; @@ -3316,7 +3316,7 @@ static void explore_walk_step(struct rev_info *revs) } static void explore_to_depth(struct rev_info *revs, - uint32_t gen_cutoff) + timestamp_t gen_cutoff) { struct topo_walk_info *info = revs->topo_walk_info; struct commit *c; @@ -3359,7 +3359,7 @@ static void indegree_walk_step(struct rev_info *revs) } static void compute_indegrees_to_depth(struct rev_info *revs, - uint32_t gen_cutoff) + timestamp_t gen_cutoff) { struct topo_walk_info *info = revs->topo_walk_info; struct commit *c; @@ -3414,10 +3414,10 @@ static void init_topo_walk(struct rev_info *revs) info->explore_queue.compare = compare_commits_by_gen_then_commit_date; info->indegree_queue.compare = compare_commits_by_gen_then_commit_date; - info->min_generation = GENERATION_NUMBER_INFINITY; + info->min_generation = GENERATION_NUMBER_V2_INFINITY; for (list = revs->commits; list; list = list->next) { struct commit *c = list->item; - uint32_t generation; + timestamp_t generation; if (parse_commit_gently(c, 1)) continue; @@ -3478,7 +3478,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit) for (p = commit->parents; p; p = p->next) { struct commit *parent = p->item; int *pi; - uint32_t generation; + timestamp_t generation; if (parent->object.flags & UNINTERESTING) continue; diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh index 3ec5248d70..43801f07a5 100755 --- a/t/t5318-commit-graph.sh +++ b/t/t5318-commit-graph.sh @@ -596,7 +596,7 @@ test_expect_success 'detect incorrect generation number' ' "generation for commit" ' -test_expect_success 'detect incorrect generation number' ' +test_expect_failure 'detect incorrect generation number' ' corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\00" \ "non-zero generation number" ' diff --git a/upload-pack.c b/upload-pack.c index 951a2b23aa..db2332e687 100644 --- a/upload-pack.c +++ b/upload-pack.c @@ -489,7 +489,7 @@ static int got_oid(struct upload_pack_data *data, static int ok_to_give_up(struct upload_pack_data *data) { - uint32_t min_generation = GENERATION_NUMBER_ZERO; + timestamp_t min_generation = GENERATION_NUMBER_ZERO; if (!data->have_obj.nr) return 0;