From: "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: peff@peff.net, avarab@gmail.com, git@jeffhostetler.com,
jrnieder@google.com, steadmon@google.com,
johannes.schindelin@gmx.de, philipoakley@iee.org,
Junio C Hamano <gitster@pobox.com>,
Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH v5 02/16] commit-graph: prepare for commit-graph chains
Date: Fri, 07 Jun 2019 11:38:22 -0700 (PDT) [thread overview]
Message-ID: <ce139d80df9c6f847d9a88be0d0ff35a2670c600.1559932699.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.184.v5.git.gitgitgadget@gmail.com>
From: Derrick Stolee <dstolee@microsoft.com>
To prepare for a chain of commit-graph files, augment the
commit_graph struct to point to a base commit_graph. As we load
commits from the graph, we may actually want to read from a base
file according to the graph position.
The "graph position" of a commit is given by concatenating the
lexicographic commit orders from each of the commit-graph files in
the chain. This means that we must distinguish two values:
* lexicographic index : the position within the lexicographic
order in a single commit-graph file.
* graph position: the position within the concatenated order
of multiple commit-graph files
Given the lexicographic index of a commit in a graph, we can
compute the graph position by adding the number of commits in
the lower-level graphs. To find the lexicographic index of
a commit, we subtract the number of commits in lower-level graphs.
While here, change insert_parent_or_die() to take a uint32_t
position, as that is the type used by its only caller and that
makes more sense with the limits in the commit-graph format.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
commit-graph.c | 89 +++++++++++++++++++++++++++++++++++++++++++-------
commit-graph.h | 3 ++
2 files changed, 81 insertions(+), 11 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index 7723156964..8c3598037b 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -359,9 +359,18 @@ int generation_numbers_enabled(struct repository *r)
return !!first_generation;
}
+static void close_commit_graph_one(struct commit_graph *g)
+{
+ if (!g)
+ return;
+
+ close_commit_graph_one(g->base_graph);
+ free_commit_graph(g);
+}
+
void close_commit_graph(struct repository *r)
{
- free_commit_graph(r->objects->commit_graph);
+ close_commit_graph_one(r->objects->commit_graph);
r->objects->commit_graph = NULL;
}
@@ -371,18 +380,38 @@ static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t
g->chunk_oid_lookup, g->hash_len, pos);
}
+static void load_oid_from_graph(struct commit_graph *g,
+ uint32_t pos,
+ struct object_id *oid)
+{
+ uint32_t lex_index;
+
+ while (g && pos < g->num_commits_in_base)
+ g = g->base_graph;
+
+ if (!g)
+ BUG("NULL commit-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;
+
+ hashcpy(oid->hash, g->chunk_oid_lookup + g->hash_len * lex_index);
+}
+
static struct commit_list **insert_parent_or_die(struct repository *r,
struct commit_graph *g,
- uint64_t pos,
+ uint32_t pos,
struct commit_list **pptr)
{
struct commit *c;
struct object_id oid;
- if (pos >= g->num_commits)
- die("invalid parent position %"PRIu64, pos);
+ if (pos >= g->num_commits + g->num_commits_in_base)
+ die("invalid parent position %"PRIu32, pos);
- hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
+ load_oid_from_graph(g, pos, &oid);
c = lookup_commit(r, &oid);
if (!c)
die(_("could not find commit %s"), oid_to_hex(&oid));
@@ -392,7 +421,14 @@ static struct commit_list **insert_parent_or_die(struct repository *r,
static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
{
- const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
+ const unsigned char *commit_data;
+ uint32_t lex_index;
+
+ while (pos < g->num_commits_in_base)
+ g = g->base_graph;
+
+ lex_index = pos - g->num_commits_in_base;
+ commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
item->graph_pos = pos;
item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
}
@@ -405,10 +441,25 @@ static int fill_commit_in_graph(struct repository *r,
uint32_t *parent_data_ptr;
uint64_t date_low, date_high;
struct commit_list **pptr;
- const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * pos;
+ const unsigned char *commit_data;
+ uint32_t lex_index;
- item->object.parsed = 1;
+ 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.
+ */
item->graph_pos = pos;
+ lex_index = pos - g->num_commits_in_base;
+
+ commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
+
+ item->object.parsed = 1;
item->maybe_tree = NULL;
@@ -452,7 +503,18 @@ static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uin
*pos = item->graph_pos;
return 1;
} else {
- return bsearch_graph(g, &(item->object.oid), pos);
+ struct commit_graph *cur_g = g;
+ uint32_t lex_index;
+
+ while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index))
+ cur_g = cur_g->base_graph;
+
+ if (cur_g) {
+ *pos = lex_index + cur_g->num_commits_in_base;
+ return 1;
+ }
+
+ return 0;
}
}
@@ -492,8 +554,13 @@ static struct tree *load_tree_for_commit(struct repository *r,
struct commit *c)
{
struct object_id oid;
- const unsigned char *commit_data = g->chunk_commit_data +
- GRAPH_DATA_WIDTH * (c->graph_pos);
+ const unsigned char *commit_data;
+
+ while (c->graph_pos < g->num_commits_in_base)
+ g = g->base_graph;
+
+ commit_data = g->chunk_commit_data +
+ GRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);
hashcpy(oid.hash, commit_data);
c->maybe_tree = lookup_tree(r, &oid);
diff --git a/commit-graph.h b/commit-graph.h
index 70f4caf0c7..f9fe32ebe3 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -48,6 +48,9 @@ struct commit_graph {
uint32_t num_commits;
struct object_id oid;
+ uint32_t num_commits_in_base;
+ struct commit_graph *base_graph;
+
const uint32_t *chunk_oid_fanout;
const unsigned char *chunk_oid_lookup;
const unsigned char *chunk_commit_data;
--
gitgitgadget
next prev parent reply other threads:[~2019-06-07 18:38 UTC|newest]
Thread overview: 136+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-08 15:53 [PATCH 00/17] [RFC] Commit-graph: Write incremental files Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 01/17] commit-graph: fix the_repository reference Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 02/17] commit-graph: return with errors during write Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 04/17] commit-graph: remove Future Work section Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 03/17] commit-graph: collapse parameters into flags Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 05/17] commit-graph: create write_commit_graph_context Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 06/17] commit-graph: extract fill_oids_from_packs() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 07/17] commit-graph: extract fill_oids_from_commit_hex() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 08/17] commit-graph: extract fill_oids_from_all_packs() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 10/17] commit-graph: extract copy_oids_to_commits() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 09/17] commit-graph: extract count_distinct_commits() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 11/17] commit-graph: extract write_commit_graph_file() Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 12/17] Documentation: describe split commit-graphs Derrick Stolee via GitGitGadget
2019-05-08 17:20 ` SZEDER Gábor
2019-05-08 19:00 ` Derrick Stolee
2019-05-08 20:11 ` Ævar Arnfjörð Bjarmason
2019-05-09 4:49 ` Junio C Hamano
2019-05-09 12:25 ` Derrick Stolee
2019-05-09 13:45 ` Derrick Stolee
2019-05-09 15:48 ` Ævar Arnfjörð Bjarmason
2019-05-09 17:08 ` Derrick Stolee
2019-05-09 21:45 ` Ævar Arnfjörð Bjarmason
2019-05-10 12:44 ` Derrick Stolee
2019-05-08 15:53 ` [PATCH 13/17] commit-graph: lay groundwork for incremental files Derrick Stolee via GitGitGadget
2019-05-08 15:53 ` [PATCH 14/17] commit-graph: load split commit-graph files Derrick Stolee via GitGitGadget
2019-05-08 15:54 ` [PATCH 15/17] commit-graph: write " Derrick Stolee via GitGitGadget
2019-05-08 15:54 ` [PATCH 16/17] commit-graph: add --split option Derrick Stolee via GitGitGadget
2019-05-08 15:54 ` [PATCH 17/17] fetch: add fetch.writeCommitGraph config setting Derrick Stolee via GitGitGadget
2019-05-09 8:07 ` Ævar Arnfjörð Bjarmason
2019-05-09 14:21 ` Derrick Stolee
2019-05-08 19:27 ` [PATCH 00/17] [RFC] Commit-graph: Write incremental files Ævar Arnfjörð Bjarmason
2019-05-22 19:53 ` [PATCH v2 00/11] " Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 01/11] commit-graph: document commit-graph chains Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 02/11] commit-graph: prepare for " Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 03/11] commit-graph: rename commit_compare to oid_compare Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 04/11] commit-graph: load commit-graph chains Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 05/11] commit-graph: add base graphs chunk Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 06/11] commit-graph: rearrange chunk count logic Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 08/11] commit-graph: add --split option to builtin Derrick Stolee via GitGitGadget
2019-05-27 11:28 ` SZEDER Gábor
2019-05-22 19:53 ` [PATCH v2 07/11] commit-graph: write commit-graph chains Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 09/11] commit-graph: merge " Derrick Stolee via GitGitGadget
2019-05-23 0:43 ` Ævar Arnfjörð Bjarmason
2019-05-23 13:00 ` Derrick Stolee
2019-05-22 19:53 ` [PATCH v2 10/11] commit-graph: allow cross-alternate chains Derrick Stolee via GitGitGadget
2019-05-22 19:53 ` [PATCH v2 11/11] commit-graph: expire commit-graph files Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 00/14] Commit-graph: Write incremental files Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 01/14] commit-graph: document commit-graph chains Derrick Stolee via GitGitGadget
2019-06-05 17:22 ` Junio C Hamano
2019-06-05 18:09 ` Derrick Stolee
2019-06-06 12:10 ` Philip Oakley
2019-06-06 17:09 ` Derrick Stolee
2019-06-06 21:59 ` Philip Oakley
2019-06-03 16:03 ` [PATCH v3 02/14] commit-graph: prepare for " Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 03/14] commit-graph: rename commit_compare to oid_compare Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 04/14] commit-graph: load commit-graph chains Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 06/14] commit-graph: rearrange chunk count logic Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 05/14] commit-graph: add base graphs chunk Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 07/14] commit-graph: write commit-graph chains Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 08/14] commit-graph: add --split option to builtin Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 09/14] commit-graph: merge commit-graph chains Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 10/14] commit-graph: allow cross-alternate chains Derrick Stolee via GitGitGadget
2019-06-03 16:03 ` [PATCH v3 11/14] commit-graph: expire commit-graph files Derrick Stolee via GitGitGadget
2019-06-03 16:04 ` [PATCH v3 12/14] commit-graph: create options for split files Derrick Stolee via GitGitGadget
2019-06-03 16:04 ` [PATCH v3 13/14] commit-graph: verify chains with --shallow mode Derrick Stolee via GitGitGadget
2019-06-03 16:04 ` [PATCH v3 14/14] commit-graph: clean up chains after flattened write Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 00/14] Commit-graph: Write incremental files Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 01/14] commit-graph: document commit-graph chains Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 02/14] commit-graph: prepare for " Derrick Stolee via GitGitGadget
2019-06-06 15:19 ` Philip Oakley
2019-06-06 21:28 ` Junio C Hamano
2019-06-07 12:44 ` Derrick Stolee
2019-06-06 14:15 ` [PATCH v4 03/14] commit-graph: rename commit_compare to oid_compare Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 04/14] commit-graph: load commit-graph chains Derrick Stolee via GitGitGadget
2019-06-06 22:20 ` Junio C Hamano
2019-06-07 12:53 ` Derrick Stolee
2019-06-06 14:15 ` [PATCH v4 05/14] commit-graph: add base graphs chunk Derrick Stolee via GitGitGadget
2019-06-07 18:15 ` Junio C Hamano
2019-06-06 14:15 ` [PATCH v4 06/14] commit-graph: rearrange chunk count logic Derrick Stolee via GitGitGadget
2019-06-07 18:23 ` Junio C Hamano
2019-06-06 14:15 ` [PATCH v4 07/14] commit-graph: write commit-graph chains Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 08/14] commit-graph: add --split option to builtin Derrick Stolee via GitGitGadget
2019-06-07 21:57 ` Junio C Hamano
2019-06-11 12:51 ` Derrick Stolee
2019-06-11 19:45 ` Junio C Hamano
2019-06-06 14:15 ` [PATCH v4 09/14] commit-graph: merge commit-graph chains Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 10/14] commit-graph: allow cross-alternate chains Derrick Stolee via GitGitGadget
2019-06-06 17:00 ` Philip Oakley
2019-06-06 14:15 ` [PATCH v4 11/14] commit-graph: expire commit-graph files Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 12/14] commit-graph: create options for split files Derrick Stolee via GitGitGadget
2019-06-06 18:41 ` Ramsay Jones
2019-06-06 14:15 ` [PATCH v4 13/14] commit-graph: verify chains with --shallow mode Derrick Stolee via GitGitGadget
2019-06-06 14:15 ` [PATCH v4 14/14] commit-graph: clean up chains after flattened write Derrick Stolee via GitGitGadget
2019-06-06 16:57 ` [PATCH v4 00/14] Commit-graph: Write incremental files Junio C Hamano
2019-06-07 12:37 ` Derrick Stolee
2019-06-07 18:38 ` [PATCH v5 00/16] " Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 01/16] commit-graph: document commit-graph chains Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` Derrick Stolee via GitGitGadget [this message]
2019-06-07 18:38 ` [PATCH v5 04/16] commit-graph: load " Derrick Stolee via GitGitGadget
2019-06-10 21:47 ` Junio C Hamano
2019-06-10 23:41 ` Derrick Stolee
2019-06-07 18:38 ` [PATCH v5 03/16] commit-graph: rename commit_compare to oid_compare Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 05/16] commit-graph: add base graphs chunk Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 06/16] commit-graph: rearrange chunk count logic Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 07/16] commit-graph: write commit-graph chains Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 08/16] commit-graph: add --split option to builtin Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 09/16] commit-graph: merge commit-graph chains Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 10/16] commit-graph: allow cross-alternate chains Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 11/16] commit-graph: expire commit-graph files Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 12/16] commit-graph: create options for split files Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 13/16] commit-graph: verify chains with --shallow mode Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 14/16] commit-graph: clean up chains after flattened write Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 15/16] commit-graph: test octopus merges with --split Derrick Stolee via GitGitGadget
2019-06-07 18:38 ` [PATCH v5 16/16] commit-graph: test --split across alternate without --split Derrick Stolee via GitGitGadget
2019-06-17 15:02 ` [PATCH] commit-graph: normalize commit-graph filenames Derrick Stolee
2019-06-17 15:07 ` Derrick Stolee
2019-06-17 18:07 ` [PATCH v2] " Derrick Stolee
2019-06-18 18:14 ` [PATCH v6 00/18] Commit-graph: Write incremental files Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 01/18] commit-graph: document commit-graph chains Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 02/18] commit-graph: prepare for " Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 03/18] commit-graph: rename commit_compare to oid_compare Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 04/18] commit-graph: load commit-graph chains Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 05/18] commit-graph: add base graphs chunk Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 06/18] commit-graph: rearrange chunk count logic Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 07/18] commit-graph: write commit-graph chains Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 08/18] commit-graph: add --split option to builtin Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 09/18] commit-graph: merge commit-graph chains Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 10/18] commit-graph: allow cross-alternate chains Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 11/18] commit-graph: expire commit-graph files Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 13/18] commit-graph: verify chains with --shallow mode Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 12/18] commit-graph: create options for split files Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 14/18] commit-graph: clean up chains after flattened write Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 15/18] commit-graph: test octopus merges with --split Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 16/18] commit-graph: test --split across alternate without --split Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 18/18] commit-graph: test verify across alternates Derrick Stolee via GitGitGadget
2019-06-18 18:14 ` [PATCH v6 17/18] commit-graph: normalize commit-graph filenames Derrick Stolee via GitGitGadget
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ce139d80df9c6f847d9a88be0d0ff35a2670c600.1559932699.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=avarab@gmail.com \
--cc=dstolee@microsoft.com \
--cc=git@jeffhostetler.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=johannes.schindelin@gmx.de \
--cc=jrnieder@google.com \
--cc=peff@peff.net \
--cc=philipoakley@iee.org \
--cc=steadmon@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
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 read-only IMAP folder(s) and NNTP newsgroup(s).