Re: [PATCH v4 00/21] Integrate commit-graph into 'fsck' and 'gc'

[Derrick Stolee <stolee@gmail.com>]

Sorry I forgot to --in-reply-to the previous version [1]

[1] 
https://public-inbox.org/git/20180524162504.158394-1-dstolee@microsoft.com/T/#u

On 6/4/2018 12:52 PM, Derrick Stolee wrote:
> Thanks for the feedback on v3. There were several small cleanups, but
> perhaps the biggest change is the addition of "commit-graph: use
> string-list API for input" which makes "commit-graph: add '--reachable'
> option" much simpler.
>
> The inter-diff is still reasonably large, but I'll send it in a
> follow-up PR.

s/PR/message

Here is that diff:


diff --git a/Documentation/config.txt b/Documentation/config.txt
index 9a3abd87e7..d2eb3c8e9b 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -900,7 +900,8 @@ the `GIT_NOTES_REF` environment variable.  See 
linkgit:git-notes[1].

  core.commitGraph::
         Enable git commit graph feature. Allows reading from the
-       commit-graph file.
+       commit-graph file. See `gc.commitGraph` for automatically
+       maintaining the file.

  core.sparseCheckout::
         Enable "sparse checkout" feature. See section "Sparse checkout" in
@@ -1554,10 +1555,11 @@ gc.autoDetach::
         if the system supports it. Default is true.

  gc.commitGraph::
-       If true, then gc will rewrite the commit-graph file after any
-       change to the object database. If '--auto' is used, then the
-       commit-graph will not be updated unless the threshold is met.
-       See linkgit:git-commit-graph[1] for details.
+       If true, then gc will rewrite the commit-graph file when
+       linkgit:git-gc[1] is run. When using linkgit:git-gc[1]
+       '--auto' the commit-graph will be updated if housekeeping is
+       required. Default is false. See linkgit:git-commit-graph[1]
+       for details.

  gc.logExpiry::
         If the file gc.log exists, then `git gc --auto` won't run
diff --git a/Documentation/git-gc.txt b/Documentation/git-gc.txt
index 17dd654a59..a6526b3592 100644
--- a/Documentation/git-gc.txt
+++ b/Documentation/git-gc.txt
@@ -119,9 +119,9 @@ The optional configuration variable `gc.packRefs` 
determines if
  it within all non-bare repos or it can be set to a boolean value.
  This defaults to true.

-The optional configuration variable 'gc.commitGraph' determines if
-'git gc' runs 'git commit-graph write'. This can be set to a boolean
-value. This defaults to false.
+The optional configuration variable `gc.commitGraph` determines if
+'git gc' should run 'git commit-graph write'. This can be set to a
+boolean value. This defaults to false.

  The optional configuration variable `gc.aggressiveWindow` controls how
  much time is spent optimizing the delta compression of the objects in
diff --git a/builtin/commit-graph.c b/builtin/commit-graph.c
index 20ce6437ae..76423b3fa5 100644
--- a/builtin/commit-graph.c
+++ b/builtin/commit-graph.c
@@ -39,7 +39,7 @@ static struct opts_commit_graph {

  static int graph_verify(int argc, const char **argv)
  {
-       struct commit_graph *graph = 0;
+       struct commit_graph *graph = NULL;
         char *graph_name;

         static struct option builtin_commit_graph_verify_options[] = {
@@ -119,13 +119,9 @@ static int graph_read(int argc, const char **argv)

  static int graph_write(int argc, const char **argv)
  {
-       const char **pack_indexes = NULL;
-       int packs_nr = 0;
-       const char **commit_hex = NULL;
-       int commits_nr = 0;
-       const char **lines = NULL;
-       int lines_nr = 0;
-       int lines_alloc = 0;
+       struct string_list *pack_indexes = NULL;
+       struct string_list *commit_hex = NULL;
+       struct string_list lines;

         static struct option builtin_commit_graph_write_options[] = {
                 OPT_STRING(0, "object-dir", &opts.obj_dir,
@@ -158,32 +154,23 @@ static int graph_write(int argc, const char **argv)

         if (opts.stdin_packs || opts.stdin_commits) {
                 struct strbuf buf = STRBUF_INIT;
-               lines_nr = 0;
-               lines_alloc = 128;
-               ALLOC_ARRAY(lines, lines_alloc);
-
-               while (strbuf_getline(&buf, stdin) != EOF) {
-                       ALLOC_GROW(lines, lines_nr + 1, lines_alloc);
-                       lines[lines_nr++] = strbuf_detach(&buf, NULL);
-               }
-
-               if (opts.stdin_packs) {
-                       pack_indexes = lines;
-                       packs_nr = lines_nr;
-               }
-               if (opts.stdin_commits) {
-                       commit_hex = lines;
-                       commits_nr = lines_nr;
-               }
+               string_list_init(&lines, 0);
+
+               while (strbuf_getline(&buf, stdin) != EOF)
+                       string_list_append(&lines, strbuf_detach(&buf, 
NULL));
+
+               if (opts.stdin_packs)
+                       pack_indexes = &lines;
+               if (opts.stdin_commits)
+                       commit_hex = &lines;
         }

         write_commit_graph(opts.obj_dir,
                            pack_indexes,
-                          packs_nr,
                            commit_hex,
-                          commits_nr,
                            opts.append);

+       string_list_clear(&lines, 0);
         return 0;
  }

@@ -207,10 +194,10 @@ int cmd_commit_graph(int argc, const char **argv, 
const char *prefix)
                              PARSE_OPT_STOP_AT_NON_OPTION);

         if (argc > 0) {
-               if (!strcmp(argv[0], "verify"))
-                       return graph_verify(argc, argv);
                 if (!strcmp(argv[0], "read"))
                         return graph_read(argc, argv);
+               if (!strcmp(argv[0], "verify"))
+                       return graph_verify(argc, argv);
                 if (!strcmp(argv[0], "write"))
                         return graph_write(argc, argv);
         }
diff --git a/commit-graph.c b/commit-graph.c
index 057d734926..946bcfa98c 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"
@@ -652,42 +653,26 @@ static void compute_generation_numbers(struct 
packed_commit_list* commits)
         }
  }

-struct hex_list {
-       char **hex_strs;
-       int hex_nr;
-       int hex_alloc;
-};
-
  static int add_ref_to_list(const char *refname,
                            const struct object_id *oid,
                            int flags, void *cb_data)
  {
-       struct hex_list *list = (struct hex_list*)cb_data;
-
-       ALLOC_GROW(list->hex_strs, list->hex_nr + 1, list->hex_alloc);
-       list->hex_strs[list->hex_nr] = xcalloc(GIT_MAX_HEXSZ + 1, 1);
-       strcpy(list->hex_strs[list->hex_nr], oid_to_hex(oid));
-       list->hex_nr++;
+       struct string_list *list = (struct string_list*)cb_data;
+       string_list_append(list, oid_to_hex(oid));
         return 0;
  }

  void write_commit_graph_reachable(const char *obj_dir, int append)
  {
-       struct hex_list list;
-       list.hex_nr = 0;
-       list.hex_alloc = 128;
-       ALLOC_ARRAY(list.hex_strs, list.hex_alloc);
-
+       struct string_list list;
+       string_list_init(&list, 1);
         for_each_ref(add_ref_to_list, &list);
-
-       write_commit_graph(obj_dir, NULL, 0, (const char 
**)list.hex_strs, list.hex_nr, append);
+       write_commit_graph(obj_dir, NULL, &list, append);
  }

  void write_commit_graph(const char *obj_dir,
-                       const char **pack_indexes,
-                       int nr_packs,
-                       const char **commit_hex,
-                       int nr_commits,
+                       struct string_list *pack_indexes,
+                       struct string_list *commit_hex,
                         int append)
  {
         struct packed_oid_list oids;
@@ -695,7 +680,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];
@@ -729,10 +713,10 @@ void write_commit_graph(const char *obj_dir,
                 int dirlen;
                 strbuf_addf(&packname, "%s/pack/", obj_dir);
                 dirlen = packname.len;
-               for (i = 0; i < nr_packs; i++) {
+               for (i = 0; i < pack_indexes->nr; i++) {
                         struct packed_git *p;
                         strbuf_setlen(&packname, dirlen);
-                       strbuf_addstr(&packname, pack_indexes[i]);
+                       strbuf_addstr(&packname, 
pack_indexes->items[i].string);
                         p = add_packed_git(packname.buf, packname.len, 1);
                         if (!p)
                                 die("error adding pack %s", packname.buf);
@@ -745,12 +729,13 @@ void write_commit_graph(const char *obj_dir,
         }

         if (commit_hex) {
-               for (i = 0; i < nr_commits; i++) {
+               for (i = 0; i < commit_hex->nr; i++) {
                         const char *end;
                         struct object_id oid;
                         struct commit *result;

-                       if (commit_hex[i] && 
parse_oid_hex(commit_hex[i], &oid, &end))
+                       if (commit_hex->items[i].string &&
+ parse_oid_hex(commit_hex->items[i].string, &oid, &end))
                                 continue;

                         result = lookup_commit_reference_gently(&oid, 1);
@@ -809,23 +794,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);
@@ -879,21 +852,22 @@ static int verify_commit_graph_error;
  static void graph_report(const char *fmt, ...)
  {
         va_list ap;
-       struct strbuf sb = STRBUF_INIT;
         verify_commit_graph_error = 1;

         va_start(ap, fmt);
-       strbuf_vaddf(&sb, fmt, ap);
-
-       fprintf(stderr, "%s\n", sb.buf);
-       strbuf_release(&sb);
+       vfprintf(stderr, fmt, ap);
+       fprintf(stderr, "\n");
         va_end(ap);
  }

+#define GENERATION_ZERO_EXISTS 1
+#define GENERATION_NUMBER_EXISTS 2
+
  int verify_commit_graph(struct commit_graph *g)
  {
         uint32_t i, cur_fanout_pos = 0;
         struct object_id prev_oid, cur_oid, checksum;
+       int generation_zero = 0;
         struct hashfile *f;
         int devnull;

@@ -1012,6 +986,18 @@ int verify_commit_graph(struct commit_graph *g)
                         graph_report("commit-graph parent list for 
commit %s terminates early",
                                      oid_to_hex(&cur_oid));

+               if (!graph_commit->generation) {
+                       if (generation_zero == GENERATION_NUMBER_EXISTS)
+                               graph_report("commit-graph has 
generation number zero for commit %s, but non-zero elsewhere",
+ oid_to_hex(&cur_oid));
+                       generation_zero = GENERATION_ZERO_EXISTS;
+               } else if (generation_zero == GENERATION_ZERO_EXISTS)
+                       graph_report("commit-graph has non-zero 
generation number for commit %s, but zero elsewhere",
+                                    oid_to_hex(&cur_oid));
+
+               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
diff --git a/commit-graph.h b/commit-graph.h
index 9a06a5f188..ee20f5e280 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -2,6 +2,7 @@
  #define COMMIT_GRAPH_H

  #include "git-compat-util.h"
+#include "string-list.h"

  char *get_commit_graph_filename(const char *obj_dir);

@@ -48,10 +49,8 @@ struct commit_graph *load_commit_graph_one(const char 
*graph_file);

  void write_commit_graph_reachable(const char *obj_dir, int append);
  void write_commit_graph(const char *obj_dir,
-                       const char **pack_indexes,
-                       int nr_packs,
-                       const char **commit_hex,
-                       int nr_commits,
+                       struct string_list *pack_indexes,
+                       struct string_list *commit_hex,
                         int append);

  int verify_commit_graph(struct commit_graph *g);
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index d20b17586f..b24e8b6689 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -33,8 +33,8 @@ test_expect_success 'create commits and repack' '
  '

  graph_git_two_modes() {
-       git -c core.graph=true $1 >output
-       git -c core.graph=false $1 >expect
+       git -c core.commitGraph=true $1 >output
+       git -c core.commitGraph=false $1 >expect
         test_cmp output expect
  }

@@ -245,7 +245,7 @@ test_expect_success 'perform fast-forward merge in 
full repo' '
         test_cmp expect output
  '

-test_expect_success 'check that gc clears commit-graph' '
+test_expect_success 'check that gc computes commit-graph' '
         cd "$TRASH_DIRECTORY/full" &&
         git commit --allow-empty -m "blank" &&
         git commit-graph write --reachable &&
@@ -281,29 +281,29 @@ GRAPH_CHUNK_LOOKUP_OFFSET=8
  GRAPH_CHUNK_LOOKUP_WIDTH=12
  GRAPH_CHUNK_LOOKUP_ROWS=5
  GRAPH_BYTE_OID_FANOUT_ID=$GRAPH_CHUNK_LOOKUP_OFFSET
-GRAPH_BYTE_OID_LOOKUP_ID=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
-                             1 \* $GRAPH_CHUNK_LOOKUP_WIDTH`
-GRAPH_BYTE_COMMIT_DATA_ID=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
-                               2 \* $GRAPH_CHUNK_LOOKUP_WIDTH`
-GRAPH_FANOUT_OFFSET=`expr $GRAPH_CHUNK_LOOKUP_OFFSET + \
-                         $GRAPH_CHUNK_LOOKUP_WIDTH \* 
$GRAPH_CHUNK_LOOKUP_ROWS`
-GRAPH_BYTE_FANOUT1=`expr $GRAPH_FANOUT_OFFSET + 4 \* 4`
-GRAPH_BYTE_FANOUT2=`expr $GRAPH_FANOUT_OFFSET + 4 \* 255`
-GRAPH_OID_LOOKUP_OFFSET=`expr $GRAPH_FANOUT_OFFSET + 4 \* 256`
-GRAPH_BYTE_OID_LOOKUP_ORDER=`expr $GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN 
\* 8`
-GRAPH_BYTE_OID_LOOKUP_MISSING=`expr $GRAPH_OID_LOOKUP_OFFSET + 
$HASH_LEN \* 4 + 10`
-GRAPH_COMMIT_DATA_OFFSET=`expr $GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 
$NUM_COMMITS`
+GRAPH_BYTE_OID_LOOKUP_ID=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
+                           1 \* $GRAPH_CHUNK_LOOKUP_WIDTH))
+GRAPH_BYTE_COMMIT_DATA_ID=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
+                            2 \* $GRAPH_CHUNK_LOOKUP_WIDTH))
+GRAPH_FANOUT_OFFSET=$(($GRAPH_CHUNK_LOOKUP_OFFSET + \
+                      $GRAPH_CHUNK_LOOKUP_WIDTH \* 
$GRAPH_CHUNK_LOOKUP_ROWS))
+GRAPH_BYTE_FANOUT1=$(($GRAPH_FANOUT_OFFSET + 4 \* 4))
+GRAPH_BYTE_FANOUT2=$(($GRAPH_FANOUT_OFFSET + 4 \* 255))
+GRAPH_OID_LOOKUP_OFFSET=$(($GRAPH_FANOUT_OFFSET + 4 \* 256))
+GRAPH_BYTE_OID_LOOKUP_ORDER=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 8))
+GRAPH_BYTE_OID_LOOKUP_MISSING=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN 
\* 4 + 10))
+GRAPH_COMMIT_DATA_OFFSET=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN \* 
$NUM_COMMITS))
  GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET
-GRAPH_BYTE_COMMIT_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN`
-GRAPH_BYTE_COMMIT_EXTRA_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + 
$HASH_LEN + 4`
-GRAPH_BYTE_COMMIT_WRONG_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + 
$HASH_LEN + 3`
-GRAPH_BYTE_COMMIT_GENERATION=`expr $GRAPH_COMMIT_DATA_OFFSET + 
$HASH_LEN + 8`
-GRAPH_BYTE_COMMIT_DATE=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 12`
-GRAPH_COMMIT_DATA_WIDTH=`expr $HASH_LEN + 16`
-GRAPH_OCTOPUS_DATA_OFFSET=`expr $GRAPH_COMMIT_DATA_OFFSET + \
-                               $GRAPH_COMMIT_DATA_WIDTH \* $NUM_COMMITS`
-GRAPH_BYTE_OCTOPUS=`expr $GRAPH_OCTOPUS_DATA_OFFSET + 4`
-GRAPH_BYTE_FOOTER=`expr $GRAPH_OCTOPUS_DATA_OFFSET + 4 \* 
$NUM_OCTOPUS_EDGES`
+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_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
+GRAPH_BYTE_FOOTER=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4 \* $NUM_OCTOPUS_EDGES))

  # usage: corrupt_graph_and_verify <position> <data> <string>
  # Manipulates the commit-graph file at the position
@@ -320,7 +320,7 @@ corrupt_graph_and_verify() {
         printf "$data" | dd of="$objdir/info/commit-graph" bs=1 
seek="$pos" conv=notrunc &&
         test_must_fail git commit-graph verify 2>test_err &&
         grep -v "^+" test_err >err
-       grep "$grepstr" err
+       test_i18ngrep "$grepstr" err
  }

  test_expect_success 'detect bad signature' '
@@ -338,9 +338,9 @@ test_expect_success 'detect bad hash version' '
                 "hash version"
  '

-test_expect_success 'detect bad chunk count' '
+test_expect_success 'detect low chunk count' '
         corrupt_graph_and_verify $GRAPH_BYTE_CHUNK_COUNT "\02" \
-               "missing the Commit Data chunk"
+               "missing the .* chunk"
  '

  test_expect_success 'detect missing OID fanout chunk' '
@@ -363,7 +363,7 @@ test_expect_success 'detect incorrect fanout' '
                 "fanout value"
  '

-test_expect_success 'detect incorrect fanout' '
+test_expect_success 'detect incorrect fanout final value' '
         corrupt_graph_and_verify $GRAPH_BYTE_FANOUT2 "\01" \
                 "fanout value"
  '
@@ -393,14 +393,19 @@ test_expect_success 'detect extra parent int-id' '
                 "is too long"
  '

-test_expect_success 'detect incorrect tree OID' '
+test_expect_success 'detect wrong parent' '
         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_WRONG_PARENT "\01" \
                 "commit-graph parent for"
  '

+test_expect_success 'detect incorrect generation number' '
+       corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\070" \
+               "generation for commit"
+'
+
  test_expect_success 'detect incorrect generation number' '
         corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \
-               "generation"
+               "non-zero generation number"
  '

  test_expect_success 'detect incorrect commit date' '