Skip to content

Compute and consume generation numbers

Derrick Stolee git 5 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v5 Latest11 patches 3 repliesIn review
  2. v410 patches 30 repliesSuperseded
  3. v39 patches 19 repliesSuperseded
Earlier versions · 2
VersionPostedPatchesRepliesStatus
v210 patches15 repliesSuperseded
v16 patches44 repliesSuperseded

Patches in v5 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/11ref-filter: fix outdated comment on in_commit_listref-filter.c+1 -10 replies
2/11commit: add generation number to struct commmitalloc.c commit-graph.c commit.h+7 -00 replies
3/11commit-graph: compute generation numberscommit-graph.c+43 -00 replies
4/11commit: use generations in paint_down_to_common()commit.c commit.h+20 -10 replies
5/11commit-graph: always load commit-graph informationcommit-graph.c commit-graph.h commit.c +3 more+47 -200 replies
6/11ref-filter: use generation number for --containsref-filter.c+20 -40 replies
7/11commit: use generation numbers for in_merge_bases()commit.c+8 -10 replies
8/11commit: add short-circuit to paint_down_to_common()commit.c+16 -40 replies
9/11commit: use generation number in remove_redundant()commit.c+6 -12 replies
10/11merge: check config before loading commitsbuiltin/merge.c t/t5318-commit-graph.sh+13 -30 replies
11/11commit-graph.txt: update design documentDocumentation/technical/commit-graph.txt+24 -50 replies

Reviews trailers per patch

None of the 11 patches has a Reviewed-by or Acked-by.

PatchJeff King
1/11
2/11
3/11
4/11
5/11
6/11Helped-by
7/11
8/11
9/11
10/11
11/11

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v5 thread

Cover letter [PATCH v5 00/11] Compute and consume generation numbers

Most of the changes from v4 are cosmetic, but there is one new commit:

commit: use generation number in remove_redundant()

Other changes are non-functional, but do clarify things.

Inter-diff from v4:

Documentation/technical/commit-graph.txt +2 -1
index d9f2713efa..e1a883eb46 100644
@@ -125,9 +125,10 @@ Future Work
   walks aware of generation numbers to gain the performance benefits they
   enable. This will mostly be accomplished by swapping a commit-date-ordered
   priority queue with one ordered by generation number. The following
-  operation is an important candidate:
+  operations are important candidates:
 
     - 'log --topo-order'
+    - 'tag --merged'
 
 - Currently, parse_commit_gently() requires filling in the root tree
   object for a commit. This passes through lookup_tree() and consequently
commit-graph.c +11 -12
index aebd242def..a8c337dd77 100644
@@ -248,6 +248,7 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,
 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;
 }
 

@@ -454,8 +455,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
                else
                        packedDate[0] = 0;
 
-               if ((*list)->generation != GENERATION_NUMBER_INFINITY)
-                       packedDate[0] |= htonl((*list)->generation << 2);
+               packedDate[0] |= htonl((*list)->generation << 2);
 
                packedDate[1] = htonl((*list)->date);
                hashwrite(f, packedDate, 8);

@@ -589,18 +589,17 @@ static void close_reachable(struct packed_oid_list *oids)
        }
 }
 
-static void compute_generation_numbers(struct commit** commits,
-                                      int nr_commits)
+static void compute_generation_numbers(struct packed_commit_list* commits)
 {
        int i;
        struct commit_list *list = NULL;
 
-       for (i = 0; i < nr_commits; i++) {
-               if (commits[i]->generation != GENERATION_NUMBER_INFINITY &&
-                   commits[i]->generation != GENERATION_NUMBER_ZERO)
+       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[i], &list);
+               commit_list_insert(commits->list[i], &list);
                while (list) {
                        struct commit *current = list->item;
                        struct commit_list *parent;

@@ -621,10 +620,10 @@ static void compute_generation_numbers(struct commit** commits,
                        if (all_parents_computed) {
                                current->generation = max_generation + 1;
                                pop_commit(&list);
-                       }
 
-                       if (current->generation > GENERATION_NUMBER_MAX)
-                               current->generation = GENERATION_NUMBER_MAX;
+                               if (current->generation > GENERATION_NUMBER_MAX)
+                                       current->generation = GENERATION_NUMBER_MAX;
+                       }
                }
        }
 }

@@ -752,7 +751,7 @@ 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.list, commits.nr);
+       compute_generation_numbers(&commits);
 
        graph_name = get_commit_graph_filename(obj_dir);
        fd = hold_lock_file_for_update(&lk, graph_name, 0);
commit.c +10 -3
index e2e16ea1a7..5064db4e61 100644
@@ -835,7 +835,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,
                int flags;
 
                if (commit->generation > last_gen)
-                       BUG("bad generation skip");
+                       BUG("bad generation skip %8x > %8x at %s",
+                           commit->generation, last_gen,
+                           oid_to_hex(&commit->object.oid));
                last_gen = commit->generation;
 
                if (commit->generation < min_generation)

@@ -947,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt)
                parse_commit(array[i]);
        for (i = 0; i < cnt; i++) {
                struct commit_list *common;
+               uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 
                if (redundant[i])
                        continue;

@@ -955,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt)
                                continue;
                        filled_index[filled] = j;
                        work[filled++] = array[j];
+
+                       if (array[j]->generation < min_generation)
+                               min_generation = array[j]->generation;
                }
-               common = paint_down_to_common(array[i], filled, work, 0);
+               common = paint_down_to_common(array[i], filled, work,
+                                             min_generation);
                if (array[i]->object.flags & PARENT2)
                        redundant[i] = 1;
                for (j = 0; j < filled; j++)

@@ -1073,7 +1080,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
        for (i = 0; i < nr_reference; i++) {
                if (parse_commit(reference[i]))
                        return ret;
-               if (min_generation > reference[i]->generation)
+               if (reference[i]->generation < min_generation)
                        min_generation = reference[i]->generation;
        }

-- >8 --

Derrick Stolee (11):
ref-filter: fix outdated comment on in_commit_list
commit: add generation number to struct commmit
commit-graph: compute generation numbers
commit: use generations in paint_down_to_common()
commit-graph: always load commit-graph information
ref-filter: use generation number for --contains
commit: use generation numbers for in_merge_bases()
commit: add short-circuit to paint_down_to_common()
commit: use generation number in remove_redundant()
merge: check config before loading commits commit-graph.txt: update design document

 Documentation/technical/commit-graph.txt | 30 ++++++--
 alloc.c                                  |  1 +
 builtin/merge.c                          |  7 +-
 commit-graph.c                           | 91 ++++++++++++++++++++----
 commit-graph.h                           |  8 +++
 commit.c                                 | 61 +++++++++++++---
 commit.h                                 |  7 +-
 object.c                                 |  2 +-
 ref-filter.c                             | 26 +++++--
 sha1_file.c                              |  2 +-
 t/t5318-commit-graph.sh                  |  9 +++
 11 files changed, 204 insertions(+), 40 deletions(-)

base-commit: 7b8a21dba1bce44d64bd86427d3d92437adc4707

Signature · 1 line
2.17.0.39.g685157f7fb

Read the cover letter in its thread