From 83073cc994cc3cd364f3f213478b9162476e8e44 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Wed, 25 Apr 2018 14:37:55 +0000 Subject: commit: add generation number to struct commit The generation number of a commit is defined recursively as follows: * If a commit A has no parents, then the generation number of A is one. * If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A. Add a uint32_t generation field to struct commit so we can pass this information to revision walks. We use three special values to signal the generation number is invalid: GENERATION_NUMBER_INFINITY 0xFFFFFFFF GENERATION_NUMBER_MAX 0x3FFFFFFF GENERATION_NUMBER_ZERO 0 The first (_INFINITY) means the generation number has not been loaded or computed. The second (_MAX) means the generation number is too large to store in the commit-graph file. The third (_ZERO) means the generation number was loaded from a commit graph file that was written by a version of git that did not support generation numbers. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- commit-graph.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 70fa1b25fd..9ad21c3ffb 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -262,6 +262,8 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin date_low = get_be32(commit_data + g->hash_len + 12); item->date = (timestamp_t)((date_high << 32) | date_low); + item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; + pptr = &item->parents; edge_value = get_be32(commit_data + g->hash_len); -- cgit v1.2.3 From 3258c66332abaf6e3e8fd81cab07ae804760cd08 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Tue, 1 May 2018 12:47:09 +0000 Subject: commit-graph: compute generation numbers While preparing commits to be written into a commit-graph file, compute the generation numbers using a depth-first strategy. The only commits that are walked in this depth-first search are those without a precomputed generation number. Thus, computation time will be relative to the number of new commits to the commit-graph file. If a computed generation number would exceed GENERATION_NUMBER_MAX, then use GENERATION_NUMBER_MAX instead. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- commit-graph.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 9ad21c3ffb..36d765e10a 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -439,6 +439,8 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len, else packedDate[0] = 0; + packedDate[0] |= htonl((*list)->generation << 2); + packedDate[1] = htonl((*list)->date); hashwrite(f, packedDate, 8); @@ -571,6 +573,45 @@ static void close_reachable(struct packed_oid_list *oids) } } +static void compute_generation_numbers(struct packed_commit_list* commits) +{ + int i; + struct commit_list *list = NULL; + + for (i = 0; i < commits->nr; i++) { + if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY && + commits->list[i]->generation != GENERATION_NUMBER_ZERO) + continue; + + commit_list_insert(commits->list[i], &list); + while (list) { + struct commit *current = list->item; + struct commit_list *parent; + int all_parents_computed = 1; + uint32_t max_generation = 0; + + for (parent = current->parents; parent; parent = parent->next) { + if (parent->item->generation == GENERATION_NUMBER_INFINITY || + parent->item->generation == GENERATION_NUMBER_ZERO) { + all_parents_computed = 0; + commit_list_insert(parent->item, &list); + break; + } else if (parent->item->generation > max_generation) { + max_generation = parent->item->generation; + } + } + + if (all_parents_computed) { + current->generation = max_generation + 1; + pop_commit(&list); + + if (current->generation > GENERATION_NUMBER_MAX) + current->generation = GENERATION_NUMBER_MAX; + } + } + } +} + void write_commit_graph(const char *obj_dir, const char **pack_indexes, int nr_packs, @@ -694,6 +735,8 @@ void write_commit_graph(const char *obj_dir, if (commits.nr >= GRAPH_PARENT_MISSING) die(_("too many commits to write graph")); + compute_generation_numbers(&commits); + graph_name = get_commit_graph_filename(obj_dir); fd = hold_lock_file_for_update(&lk, graph_name, 0); -- cgit v1.2.3 From e2838d85b6d35592ff5851d67f0232a78083ada7 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Tue, 1 May 2018 12:47:13 +0000 Subject: commit-graph: always load commit-graph information Most code paths load commits using lookup_commit() and then parse_commit(). In some cases, including some branch lookups, the commit is parsed using parse_object_buffer() which side-steps parse_commit() in favor of parse_commit_buffer(). With generation numbers in the commit-graph, we need to ensure that any commit that exists in the commit-graph file has its generation number loaded. Create new load_commit_graph_info() method to fill in the information for a commit that exists only in the commit-graph file. Call it from parse_commit_buffer() after loading the other commit information from the given buffer. Only fill this information when specified by the 'check_graph' parameter. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- commit-graph.c | 46 +++++++++++++++++++++++++++++++--------------- 1 file changed, 31 insertions(+), 15 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index 36d765e10a..a8c337dd77 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -245,6 +245,13 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g, return &commit_list_insert(c, pptr)->next; } +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; + item->graph_pos = pos; + item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; +} + static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos) { uint32_t edge_value; @@ -292,31 +299,40 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin return 1; } +static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos) +{ + if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) { + *pos = item->graph_pos; + return 1; + } else { + return bsearch_graph(g, &(item->object.oid), pos); + } +} + int parse_commit_in_graph(struct commit *item) { + uint32_t pos; + if (!core_commit_graph) return 0; if (item->object.parsed) return 1; - prepare_commit_graph(); - if (commit_graph) { - uint32_t pos; - int found; - if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) { - pos = item->graph_pos; - found = 1; - } else { - found = bsearch_graph(commit_graph, &(item->object.oid), &pos); - } - - if (found) - return fill_commit_in_graph(item, commit_graph, pos); - } - + if (commit_graph && find_commit_in_graph(item, commit_graph, &pos)) + return fill_commit_in_graph(item, commit_graph, pos); return 0; } +void load_commit_graph_info(struct commit *item) +{ + uint32_t pos; + if (!core_commit_graph) + return; + prepare_commit_graph(); + if (commit_graph && find_commit_in_graph(item, commit_graph, &pos)) + fill_commit_graph_info(item, commit_graph, pos); +} + static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c) { struct object_id oid; -- cgit v1.2.3 From 33286dcd6d79eeb81b74f36a324f260275582639 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Thu, 10 May 2018 17:42:52 +0000 Subject: commit-graph: fix UX issue when .lock file exists We use the lockfile API to avoid multiple Git processes from writing to the commit-graph file in the .git/objects/info directory. In some cases, this directory may not exist, so we check for its existence. The existing code does the following when acquiring the lock: 1. Try to acquire the lock. 2. If it fails, try to create the .git/object/info directory. 3. Try to acquire the lock, failing if necessary. The problem is that if the lockfile exists, then the mkdir fails, giving an error that doesn't help the user: "fatal: cannot mkdir .git/objects/info: File exists" While technically this honors the lockfile, it does not help the user. Instead, do the following: 1. Check for existence of .git/objects/info; create if necessary. 2. Try to acquire the lock, failing if necessary. The new output looks like: fatal: Unable to create '/.git/objects/info/commit-graph.lock': File exists. Another git process seems to be running in this repository, e.g. an editor opened by 'git commit'. Please make sure all processes are terminated then try again. If it still fails, a git process may have crashed in this repository earlier: remove the file manually to continue. Helped-by: Jeff King Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- commit-graph.c | 22 +++++----------------- 1 file changed, 5 insertions(+), 17 deletions(-) (limited to 'commit-graph.c') diff --git a/commit-graph.c b/commit-graph.c index a8c337dd77..bb54c1214c 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1,5 +1,6 @@ #include "cache.h" #include "config.h" +#include "dir.h" #include "git-compat-util.h" #include "lockfile.h" #include "pack.h" @@ -640,7 +641,6 @@ void write_commit_graph(const char *obj_dir, struct hashfile *f; uint32_t i, count_distinct = 0; char *graph_name; - int fd; struct lock_file lk = LOCK_INIT; uint32_t chunk_ids[5]; uint64_t chunk_offsets[5]; @@ -754,23 +754,11 @@ void write_commit_graph(const char *obj_dir, compute_generation_numbers(&commits); graph_name = get_commit_graph_filename(obj_dir); - fd = hold_lock_file_for_update(&lk, graph_name, 0); - - if (fd < 0) { - struct strbuf folder = STRBUF_INIT; - strbuf_addstr(&folder, graph_name); - strbuf_setlen(&folder, strrchr(folder.buf, '/') - folder.buf); - - if (mkdir(folder.buf, 0777) < 0) - die_errno(_("cannot mkdir %s"), folder.buf); - strbuf_release(&folder); - - fd = hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR); - - if (fd < 0) - die_errno("unable to create '%s'", graph_name); - } + if (safe_create_leading_directories(graph_name)) + die_errno(_("unable to create leading directories of %s"), + graph_name); + hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR); f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf); hashwrite_be32(f, GRAPH_SIGNATURE); -- cgit v1.2.3