git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 08/12] commit-graph: verify commit contents against odb

From
Derrick Stolee <stolee@gmail.com>
Date
May 14, 2018, 13:44 UTC
Message-ID
<a7637e48-b7a7-54fe-a085-b98f84df106e@gmail.com>
In-Reply-To
<CAN0heSo2sTgVSoxUiugSaEjev+0eyzCRA5ZmQVr6FRtKkyGJsQ@mail.gmail.com>
On 5/12/2018 5:17 PM, Martin Ågren wrote:
Show 136 quoted lines
> On 11 May 2018 at 23:15, Derrick Stolee <dstolee@microsoft.com> wrote:
>> When running 'git commit-graph verify', compare the contents of the
>> commits that are loaded from the commit-graph file with commits that are
>> loaded directly from the object database. This includes checking the
>> root tree object ID, commit date, and parents.
>>
>> Parse the commit from the graph during the initial loop through the
>> object IDs to guarantee we parse from the commit-graph file.
>>
>> In addition, verify the generation number calculation is correct for all
>> commits in the commit-graph file.
>>
>> While testing, we discovered that mutating the integer value for a
>> parent to be outside the accepted range causes a segmentation fault. Add
>> a new check in insert_parent_or_die() that prevents this fault. Check
>> for that error during the test, both in the typical parents and in the
>> list of parents for octopus merges.
> This paragraph and the corresponding fix and test feel like a separate
> patch to me. (The commit message of it could be "To test the next patch,
> we threw invalid data at `git commit-graph verify, and it crashed in
> pre-existing code, so let's fix that first" -- there is definitely a
> connection.) Is this important enough to fast-track to master in time
> for 2.18? My guess would be no.
>
>> +
>> +       if (pos >= g->num_commits)
>> +               die("invalide parent position %"PRIu64, pos);
> s/invalide/invalid/
>
>> @@ -875,6 +879,8 @@ int verify_commit_graph(struct commit_graph *g)
>>                  return 1;
>>
>>          for (i = 0; i < g->num_commits; i++) {
>> +               struct commit *graph_commit;
>> +
>>                  hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
>>
>>                  if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
>> @@ -892,6 +898,10 @@ int verify_commit_graph(struct commit_graph *g)
>>
>>                          cur_fanout_pos++;
>>                  }
>> +
>> +               graph_commit = lookup_commit(&cur_oid);
>> +               if (!parse_commit_in_graph_one(g, graph_commit))
>> +                       graph_report("failed to parse %s from commit-graph", oid_to_hex(&cur_oid));
>>          }
> Could this end up giving ridiculous amounts of output? It would depend
> on the input, I guess.
>
>>          while (cur_fanout_pos < 256) {
>> @@ -904,5 +914,95 @@ int verify_commit_graph(struct commit_graph *g)
>>                  cur_fanout_pos++;
>>          }
>>
>> +       if (verify_commit_graph_error)
>> +               return 1;
> Well, here we give up before running into *too* much problem.
>
>> +       for (i = 0; i < g->num_commits; i++) {
>> +               struct commit *graph_commit, *odb_commit;
>> +               struct commit_list *graph_parents, *odb_parents;
>> +               int num_parents = 0;
>> +
>> +               hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
>> +
>> +               graph_commit = lookup_commit(&cur_oid);
>> +               odb_commit = (struct commit *)create_object(cur_oid.hash, alloc_commit_node());
>> +               if (parse_commit_internal(odb_commit, 0, 0)) {
>> +                       graph_report("failed to parse %s from object database", oid_to_hex(&cur_oid));
>> +                       continue;
>> +               }
>> +
>> +               if (oidcmp(&get_commit_tree_in_graph_one(g, graph_commit)->object.oid,
>> +                          get_commit_tree_oid(odb_commit)))
>> +                       graph_report("root tree object ID for commit %s in commit-graph is %s != %s",
>> +                                    oid_to_hex(&cur_oid),
>> +                                    oid_to_hex(get_commit_tree_oid(graph_commit)),
>> +                                    oid_to_hex(get_commit_tree_oid(odb_commit)));
>> +
>> +               if (graph_commit->date != odb_commit->date)
>> +                       graph_report("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime"",
>> +                                    oid_to_hex(&cur_oid),
>> +                                    graph_commit->date,
>> +                                    odb_commit->date);
>> +
>> +
>> +               graph_parents = graph_commit->parents;
>> +               odb_parents = odb_commit->parents;
>> +
>> +               while (graph_parents) {
>> +                       num_parents++;
>> +
>> +                       if (odb_parents == NULL)
>> +                               graph_report("commit-graph parent list for commit %s is too long (%d)",
>> +                                            oid_to_hex(&cur_oid),
>> +                                            num_parents);
>> +
>> +                       if (oidcmp(&graph_parents->item->object.oid, &odb_parents->item->object.oid))
>> +                               graph_report("commit-graph parent for %s is %s != %s",
>> +                                            oid_to_hex(&cur_oid),
>> +                                            oid_to_hex(&graph_parents->item->object.oid),
>> +                                            oid_to_hex(&odb_parents->item->object.oid));
>> +
>> +                       graph_parents = graph_parents->next;
>> +                       odb_parents = odb_parents->next;
>> +               }
>> +
>> +               if (odb_parents != NULL)
>> +                       graph_report("commit-graph parent list for commit %s terminates early",
>> +                                    oid_to_hex(&cur_oid));
>> +
>> +               if (graph_commit->generation) {
>> +                       uint32_t max_generation = 0;
>> +                       graph_parents = graph_commit->parents;
>> +
>> +                       while (graph_parents) {
>> +                               if (graph_parents->item->generation == GENERATION_NUMBER_ZERO ||
>> +                                   graph_parents->item->generation == GENERATION_NUMBER_INFINITY)
>> +                                       graph_report("commit-graph has valid generation for %s but not its parent, %s",
>> +                                                    oid_to_hex(&cur_oid),
>> +                                                    oid_to_hex(&graph_parents->item->object.oid));
>> +                               if (graph_parents->item->generation > max_generation)
>> +                                       max_generation = graph_parents->item->generation;
>> +                               graph_parents = graph_parents->next;
>> +                       }
>> +
>> +                       if (max_generation == GENERATION_NUMBER_MAX)
>> +                               max_generation--;
> I'm not too familiar with these concepts. Is this a trick in preparation
> for this:
>
>> +
>> +                       if (graph_commit->generation != max_generation + 1)
> Any way that could give a false negative? (I'm not sure it would matter
> much.) Maybe "if (!MAX && generation != max + 1)".
You're right that this is confusing. Seems worth a comment.

When we have a commit-graph with computed generation numbers, the generation number for a commit is exactly one more than the maximum generation number of its parents EXCEPT in the case that we would have a generation number too large to store in the commit-graph. In this case (that is not currently possible with any repo in existence) we "squash" the generation number at GENERATION_NUMBER_MAX, so we have equality between the generation at the commit and the generation of a parent.

Show 22 quoted lines
>
>> +                               graph_report("commit-graph has incorrect generation for %s",
>> +                                            oid_to_hex(&cur_oid));
>> +               } else {
>> +                       graph_parents = graph_commit->parents;
>> +
>> +                       while (graph_parents) {
>> +                               if (graph_parents->item->generation)
>> +                                       graph_report("commit-graph has generation ZERO for %s but not its parent, %s",
>> +                                                    oid_to_hex(&cur_oid),
>> +                                                    oid_to_hex(&graph_parents->item->object.oid));
>> +                               graph_parents = graph_parents->next;
>> +                       }
>> +               }
>> +       }
>> +
>>          return verify_commit_graph_error;
>>   }
> At this point, I should admit that I went through the above thinking
> "right, makes sense, ok, sure". I was not really going "hmm, I wonder
> ..." This looks like the real meat of "verify", and I'll try to look it
> over with a fresh pair of eyes tomorrow.
I appreciate the level of inspection you are giving this series!
Show 12 quoted lines
>
>> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
>> +       corrupt_data $objdir/info/commit-graph 1134 "\01" &&
>> +       corrupt_data $objdir/info/commit-graph 1312 "\01" &&
>> +       corrupt_data $objdir/info/commit-graph 1332 "\01" &&
>> +       corrupt_data $objdir/info/commit-graph 1712 "\01" &&
>> +       corrupt_data $objdir/info/commit-graph 1340 "\01" &&
>> +       corrupt_data $objdir/info/commit-graph 1344 "\01" &&
> Could you document these numbers somehow? (Maybe even calculate them
> from constant inputs, although that might be a form of premature
> optimization.) When some poor soul has to derive the corresponding
> numbers for a commit-graph with NewHash, they will thank you.

Yeah, this is a bit of a mess. The arithmetic to get these numbers is not hard, so I could do that math in the script (at run time instead of at dev time).

I also realize that the way I write the commit-graph to be "fixed" before these tests is not so fixed: if a new ref is added, then the tests break. I'll update the commit-graph to be reachable from commits/8 so we have a more concrete example:

git rev-parse commits/8 | git commit-graph write --stdin-commits

(This already changes the written commit-graph because of the 'git pull' test, so it will "help" me be sure my math is correct when recomputing the new offsets for the corruption tests.)

Thanks, -Stolee

Previous: Martin ÅgrenNext: Martin Ågren
Message 77 of 149 in “Integrate commit-graph into 'fsck' and 'gc'”
  1. 00/12 Integrate commit-graph into 'fsck' and 'gc'Derrick Stolee, Apr 17, 2018
  2. 01/12 fixup! commit-graph: always load commit-graph informationDerrick Stolee, Apr 17, 2018
  3. 04/12 commit-graph: parse commit from chosen graphDerrick Stolee, Apr 17, 2018
  4. Jakub NarebskiApr 19, 2018
  5. 06/12 commit: force commit to parse from object databaseDerrick Stolee, Apr 17, 2018
  6. Jakub NarebskiApr 20, 2018
  7. 07/12 commit-graph: load a root tree from specific graphDerrick Stolee, Apr 17, 2018
  8. Jakub NarebskiApr 20, 2018
  9. 10/12 commit-graph: add '--reachable' optionDerrick Stolee, Apr 17, 2018
  10. Jakub NarebskiApr 20, 2018
  11. 12/12 commit-graph: update design documentDerrick Stolee, Apr 17, 2018
  12. Jakub NarebskiApr 20, 2018
  13. 11/12 gc: automatically write commit-graph filesDerrick Stolee, Apr 17, 2018
  14. Jakub NarebskiApr 20, 2018
  15. Ævar Arnfjörð BjarmasonApr 20, 2018
  16. 09/12 fsck: check commit-graphDerrick Stolee, Apr 17, 2018
  17. Jakub NarebskiApr 20, 2018
  18. 08/12 commit-graph: verify commit contents against odbDerrick Stolee, Apr 17, 2018
  19. Jakub NarebskiApr 20, 2018
  20. 02/12 commit-graph: add 'check' subcommandDerrick Stolee, Apr 17, 2018
  21. Jakub NarebskiApr 19, 2018
  22. 03/12 commit-graph: check file header informationDerrick Stolee, Apr 17, 2018
  23. Jakub NarebskiApr 19, 2018
  24. 05/12 commit-graph: check fanout and lookup tableDerrick Stolee, Apr 17, 2018
  25. Jakub NarebskiApr 20, 2018
  26. Derrick StoleeApr 17, 2018
  27. 00/12 Integrate commit-graph into fsck, gc, and fetchDerrick Stolee, May 10, 2018
  28. 01/12 commit-graph: add 'verify' subcommandDerrick Stolee, May 10, 2018
  29. Martin ÅgrenMay 10, 2018
  30. 02/12 commit-graph: verify file header informationDerrick Stolee, May 10, 2018
  31. Martin ÅgrenMay 10, 2018
  32. 04/12 commit-graph: verify fanout and lookup tableDerrick Stolee, May 10, 2018
  33. Martin ÅgrenMay 10, 2018
  34. Derrick StoleeMay 11, 2018
  35. 06/12 commit-graph: load a root tree from specific graphDerrick Stolee, May 10, 2018
  36. 08/12 fsck: verify commit-graphDerrick Stolee, May 10, 2018
  37. 12/12 commit-graph: update design documentDerrick Stolee, May 10, 2018
  38. 11/12 fetch: compute commit-graph by defaultDerrick Stolee, May 10, 2018
  39. 07/12 commit-graph: verify commit contents against odbDerrick Stolee, May 10, 2018
  40. 09/12 commit-graph: add '--reachable' optionDerrick Stolee, May 10, 2018
  41. 10/12 gc: automatically write commit-graph filesDerrick Stolee, May 10, 2018
  42. 05/12 commit: force commit to parse from object databaseDerrick Stolee, May 10, 2018
  43. 03/12 commit-graph: parse commit from chosen graphDerrick Stolee, May 10, 2018
  44. Martin ÅgrenMay 10, 2018
  45. Stefan BellerMay 10, 2018
  46. Derrick StoleeMay 11, 2018
  47. Martin ÅgrenMay 11, 2018
  48. Ævar Arnfjörð BjarmasonMay 10, 2018
  49. Derrick StoleeMay 11, 2018
  50. 00/12 Integrate commit-graph into fsck and gcDerrick Stolee, May 11, 2018
  51. 02/12 commit-graph: verify file header informationDerrick Stolee, May 11, 2018
  52. Martin ÅgrenMay 12, 2018
  53. Derrick StoleeMay 14, 2018
  54. Jakub NarebskiMay 20, 2018
  55. 01/12 commit-graph: add 'verify' subcommandDerrick Stolee, May 11, 2018
  56. Martin ÅgrenMay 12, 2018
  57. Derrick StoleeMay 14, 2018
  58. Jakub NarebskiMay 20, 2018
  59. 03/12 commit-graph: test that 'verify' finds corruptionDerrick Stolee, May 11, 2018
  60. Martin ÅgrenMay 12, 2018
  61. Jakub NarebskiMay 21, 2018
  62. Derrick StoleeMay 24, 2018
  63. 04/12 commit-graph: parse commit from chosen graphDerrick Stolee, May 11, 2018
  64. Martin ÅgrenMay 12, 2018
  65. 05/12 commit-graph: verify fanout and lookup tableDerrick Stolee, May 11, 2018
  66. 06/12 commit: force commit to parse from object databaseDerrick Stolee, May 11, 2018
  67. Martin ÅgrenMay 12, 2018
  68. 09/12 fsck: verify commit-graphDerrick Stolee, May 11, 2018
  69. Martin ÅgrenMay 17, 2018
  70. 11/12 gc: automatically write commit-graph filesDerrick Stolee, May 11, 2018
  71. Martin ÅgrenMay 17, 2018
  72. 12/12 commit-graph: update design documentDerrick Stolee, May 11, 2018
  73. 07/12 commit-graph: load a root tree from specific graphDerrick Stolee, May 11, 2018
  74. Martin ÅgrenMay 12, 2018
  75. 08/12 commit-graph: verify commit contents against odbDerrick Stolee, May 11, 2018
  76. Martin ÅgrenMay 12, 2018
  77. Derrick StoleeMay 14, 2018
  78. Martin ÅgrenMay 15, 2018
  79. 10/12 commit-graph: add '--reachable' optionDerrick Stolee, May 11, 2018
  80. Martin ÅgrenMay 17, 2018
  81. 00/20 Integrate commit-graph into 'fsck' and 'gc'Derrick Stolee, May 24, 2018
  82. 01/20 commit-graph: UNLEAK before die()Derrick Stolee, May 24, 2018
  83. Stefan BellerMay 24, 2018
  84. Derrick StoleeMay 25, 2018
  85. 04/20 commit: force commit to parse from object databaseDerrick Stolee, May 24, 2018
  86. Jakub NarebskiMay 27, 2018
  87. 03/20 commit-graph: parse commit from chosen graphDerrick Stolee, May 24, 2018
  88. Jakub NarebskiMay 27, 2018
  89. Derrick StoleeMay 29, 2018
  90. 06/20 commit-graph: add 'verify' subcommandDerrick Stolee, May 24, 2018
  91. Jakub NarebskiMay 27, 2018
  92. Derrick StoleeMay 30, 2018
  93. Jakub NarebskiJun 2, 2018
  94. Derrick StoleeJun 4, 2018
  95. 07/20 commit-graph: verify catches corrupt signatureDerrick Stolee, May 24, 2018
  96. Jakub NarebskiMay 28, 2018
  97. Derrick StoleeMay 29, 2018
  98. Jakub NarebskiJun 2, 2018
  99. 05/20 commit-graph: load a root tree from specific graphDerrick Stolee, May 24, 2018
  100. Jakub NarebskiMay 27, 2018
  101. 08/20 commit-graph: verify required chunks are presentDerrick Stolee, May 24, 2018
  102. Jakub NarebskiMay 28, 2018
  103. 02/20 commit-graph: fix GRAPH_MIN_SIZEDerrick Stolee, May 24, 2018
  104. Jakub NarebskiMay 26, 2018
  105. brian m. carlsonMay 26, 2018
  106. Jakub NarebskiJun 2, 2018
  107. 09/20 commit-graph: verify corrupt OID fanout and lookupDerrick Stolee, May 24, 2018
  108. Jakub NarebskiMay 30, 2018
  109. Derrick StoleeMay 30, 2018
  110. Duy NguyenJun 2, 2018
  111. Derrick StoleeJun 4, 2018
  112. Duy NguyenJun 4, 2018
  113. 10/20 commit-graph: verify objects existDerrick Stolee, May 24, 2018
  114. Jakub NarebskiMay 30, 2018
  115. Derrick StoleeMay 31, 2018
  116. 11/20 commit-graph: verify root tree OIDsDerrick Stolee, May 24, 2018
  117. Jakub NarebskiMay 30, 2018
  118. Derrick StoleeMay 31, 2018
  119. Jakub NarebskiJun 2, 2018
  120. 12/20 commit-graph: verify parent listDerrick Stolee, May 24, 2018
  121. Jakub NarebskiJun 1, 2018
  122. 14/20 commit-graph: verify commit dateDerrick Stolee, May 24, 2018
  123. Jakub NarebskiJun 2, 2018
  124. 16/20 commit-graph: verify contents match checksumDerrick Stolee, May 24, 2018
  125. SZEDER GáborMay 30, 2018
  126. Jakub NarebskiJun 2, 2018
  127. Derrick StoleeJun 4, 2018
  128. 19/20 gc: automatically write commit-graph filesDerrick Stolee, May 24, 2018
  129. Jakub NarebskiJun 2, 2018
  130. Derrick StoleeJun 4, 2018
  131. 20/20 commit-graph: update design documentDerrick Stolee, May 24, 2018
  132. Jakub NarebskiJun 2, 2018
  133. 17/20 fsck: verify commit-graphDerrick Stolee, May 24, 2018
  134. Jakub NarebskiJun 2, 2018
  135. Derrick StoleeJun 4, 2018
  136. 15/20 commit-graph: test for corrupted octopus edgeDerrick Stolee, May 24, 2018
  137. Jakub NarebskiJun 2, 2018
  138. Derrick StoleeJun 4, 2018
  139. 18/20 commit-graph: add '--reachable' optionDerrick Stolee, May 24, 2018
  140. Jakub NarebskiJun 2, 2018
  141. Derrick StoleeJun 4, 2018
  142. 13/20 commit-graph: verify generation numberDerrick Stolee, May 24, 2018
  143. Jakub NarebskiJun 2, 2018
  144. Derrick StoleeJun 4, 2018
  145. Ævar Arnfjörð BjarmasonMay 24, 2018
  146. Junio C HamanoMay 25, 2018
  147. Junio C HamanoMay 29, 2018
  148. Derrick StoleeMay 29, 2018
  149. Junio C HamanoMay 29, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.