threads / discuss / 48794

Inconsistencies in commit-graph technical docs.

Subject: Inconsistencies in commit-graph technical docs.

## tl;dr

4 messages between Jun 28, 2018 and Jun 28, 2018.

replies: 3people: 2as markdown or json

Grant Welch· Jun 28, 2018, 05:11 UTC · lore

I recently read the "Supercharging the Git Commit Graph" blog by Derrick Stolee. I found the article interesting and wanted to verify the performance numbers for myself. Then that led me to want to know more about the implementation, so I read the technical design notes in commit-graph.txt, and then I jumped into the format documentation in commit-graph-format.txt.

Along the way, I noticed a few issues. They might just be errors in the documentation, but I figured it was worth documenting my entire process just to be sure.

"Supercharging the Git Commit Graph", by Derrick Stolee:
  https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/

# TL;DR

I found a few discrepencies between the documentation in commit-graph-format.txt and the results that I observed for myself.

1. The "Commit Data" chunk signature is documented to be 'CGET', but
it should be 'CDAT'.

commit-graph.c:18
  #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */

2. The "no parent" value is documented to be 0xffffffff, but is
actually 0x70000000.

commit-graph.c:34
  #define GRAPH_PARENT_NONE 0x70000000

3. The "generation" field isn't set on any of the commits. (I don't
know what to make of this.)

# Documented Process

Just to follow along, here are the details about my local repo. I don't have any local changes; I just track upstream.

repo: git/git remotes: git://git.kernel.org/pub/scm/git/git.git (origin) branch: master commit: ed843436dd4924c10669820cc73daf50f0b4dabd

os: MacOS 10.11.6 (El Capitan) git: 2.18.0

Just to be clear, I am following the details as described in:
  /Documentation/technical/commit-graph-format.txt

# Create the commit-graph File

As a setup step, I have to prepare the commit-graph file as described in the blog post.

  $ git show-ref -s | git commit-graph write --stdin-commits

# Verify SHA1 Checksum

Starting at the end first because like most (all?) of git's binary formats, there is a SHA1 checksum that verifies the integrity of the file. Everything checks out fine.

  $ < .git/objects/info/commit-graph tail -c 20 | xxd -p
  35507183b1e9546f9e4844f0796d630daebc85d8

  $ < .git/objects/info/commit-graph wc -c
  3037156

  $ < .git/objects/info/commit-graph head -c $((3037156-20)) | sha1sum
  35507183b1e9546f9e4844f0796d630daebc85d8  -

# Header

The header looks good:
* signature:   CGPH
* version:     1
* hash:        1 (SHA1)
* "chunks":    4
* "reserved":  (ignored)

  $ < .git/objects/info/commit-graph xxd -l8
  00000000: 4347 5048 0101 0400                      CGPH....

# Chunk Lookup, Problem: CGET/CDAT

I have all of the documented "chunks". but it appears, that the documentation is wrong for the "Commit Data" chunk. The document signature is 'CGET', but I'm getting 'CDAT'.

* OIDF, Object ID Fanout:   0x44
* OIDL, Object ID Lookup:   0x444
* CDAT, Commit Data:        0x108f58
* EDGE, Large Edge List:    0x2e577c
*     , terminating label:  0x2e57d0

  $ < .git/objects/info/commit-graph xxd -s8 -l$(((4+1)*12)) -c12 -g4
  00000008: 4f494446 00000000 00000044  OIDF.......D
  00000014: 4f49444c 00000000 00000444  OIDL.......D
  00000020: 43444154 00000000 00108f58  CDAT.......X
  0000002c: 45444745 00000000 002e567c  EDGE......V|
  00000038: 00000000 00000000 002e57d0  ..........W.

# OID Fanout

Not much to tell here, but since it's important, I'll just show last line so know how many commits are recorded in the file. Everything checks out that I have 54209 commits in my local repo.

  $ < .git/objects/info/commit-graph xxd -s0x44 -l$((256*4)) -c4 -g4
  ...
  00000440: 0000d3c1

  $ echo $((0x0000d3c1))
  54209

  $ git rev-list --all | wc -l
    54209

# OID Lookup

Again, not much to see here; just an alphanumeric, sequential list off all the commit ids.

  $ < .git/objects/info/commit-graph xxd -s0x444 -l$((54209*20)) -c20 -g20
  ...
  00108f44: fffe694d607ea683b5d08ee99a46d9b06cb74006  ..iM`~.......F..l.@.

  $ git cat-file -p fffe694d607ea683b5d08ee99a46d9b06cb74006
  tree 1241274386e9d5dabaf370477ff19ba0eb36c3c2
  parent 84dee6bbc9eb6dd8e613414ed0271d8290549e89
  author Eric Wong <normalperson@yhbt.net> 1168151155 -0800
  committer Junio C Hamano <junkio@cox.net> 1168152528 -0800
  ...

# Commit Data

This is where I start to see inconsistencies with the documented format.

  $ < .git/objects/info/commit-graph xxd -s0x108f58
-l$((54209*(20+16))) -c36 -g4
  ...
  002e5658: 12412743 86e9d5da baf37047 7ff19ba0 eb36c3c2 00006dea
70000000 00000000 45a097d0

From the above 'git cat-file' command, we can confirm the tree is correct.

tree: 1241274386e9d5dabaf370477ff19ba0eb36c3c2 parent1: 00006dea parent2: 70000000 generation: 00000000 timestamp: 45a097d0

As does the timestamp.

  $ date --date @$((0x45a097d0)) +%s
  1168152528

Parent #1 looks good as well.

  < .git/objects/info/commit-graph xxd -s$((0x444+(0x00006dea*20)))
-l20 -c20 -g20
  00089a8c: 84dee6bbc9eb6dd8e613414ed0271d8290549e89

## Problem: Parent #2

Parent #2 (70000000), however appears to be a mystery value. The value is way too high to actually be in the OID Lookup table. And, the only documented magic numbers are 0xffffffff (no parent) and 0x80000000|0x??????? (octopus merge; see: Last Edge List).

## Problem: Generation

Also, none of these objects have their 'generation' field set.

  $ < .git/objects/info/commit-graph xxd -s0x108f58
-l$((54209*(20+16))) -c36 -g4 | grep 00000000 | wc -l
    54209

## Check Octopus Merges

The final "chunk", Large Edge List, is for handling the extra data from octopus merge commits. Since I can't conceive of a fancy xxd command to that could list them, I have to go the long way round to find an example of one.

  $ git rev-list --all --min-parents=3 | wc -l
      35

  $ git rev-list --all --min-parents=3
  25bf951381a4880c43a3d1c65e6dce651e61148f
  ...

  $ < .git/objects/info/commit-graph xxd -s0x444 -l$((54209*20)) -c20
-g20 | grep 25bf951381a4880c43a3d1c65e6dce651e61148f
  0002706c: 25bf951381a4880c43a3d1c65e6dce651e61148f  %.......C...^m.e.a..

  $ echo $(((0x0002706c-0x444)/20))
  7938

  $ < .git/objects/info/commit-graph xxd -s$((0x444+(7938*20))) -l20 -c20 -g20
  0002706c: 25bf951381a4880c43a3d1c65e6dce651e61148f  %.......C...^m.e.a..

  $ < .git/objects/info/commit-graph xxd -s$((0x108f58+(7938*36))) -l36 -c36 -g4
  0014eba0: ce9488df 264bc29a 37b47932 0fad03c9 3a470db7 000004c7
80000011 00000000 594dbf30

  $ git dump 25bf951381a4880c43a3d1c65e6dce651e61148f
  tree ce9488df264bc29a37b479320fad03c93a470db7
  parent 05ec6e13aaf33b6a647e1321203a770e697eea9a
  parent a84f3e59ebde9e891275ef8325c432db6bdf950c
  parent dc8441fdb4598f54865a5c783d1f86c1e0bcb6dc
  author Junio C Hamano <gitster@pobox.com> 1498083644 -0700
  committer Junio C Hamano <gitster@pobox.com> 1498267440 -0700

  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x000004c7*20)))
-l20 -c20 -g20
  000063d0: 05ec6e13aaf33b6a647e1321203a770e697eea9a

In the above commands, I was able to find a merge commit with more than 2 parents using git-rev-list. From there, I was able to find that commit in the "OID Lookup" table and determine it's position. With that position, I was able to find the "Commit Data" associated with it. Finally, the git-cat-file confirms that the tree is correct and that the first parent commit is correct (after performing another OID lookup).

Now it's just a matter of reviewing the last chunk to learn more about 80000011.

## Naive Solution for Finding Octopus Merges

In a repo with very few octopus merges, I would expect this to work 100% of the time. However, I doubt that it will work for a repo like linux/linux that have a lot of commits that are merged through octopus merges.

This assumes that '80000' won't occur in the tree OID, parent1, generation, nor the timestamp. Seems like a fair bet, but qualifies as naive.

I tested using '8000', but it created too many false positives. For git/git, '800000' works just as well as '80000', but would more likely to under report elsewhere.

  $ < .git/objects/info/commit-graph xxd -s0x108f58
-l$((54209*(20+16))) -c36 -g4 | grep 80000 | wc -l
      35

  $ < .git/objects/info/commit-graph xxd -s0x108f58
-l$((54209*(20+16))) -c36 -g4 | grep 80000
  ...
  0014eba0: ce9488df 264bc29a 37b47932 0fad03c9 3a470db7 000004c7
80000011 00000000 594dbf30
  ...

# Last Edge List

Finally, I can get a list of all the commits that have been a parent2-N on an octopus merge.

  $ < .git/objects/info/commit-graph xxd -s0x2e567c
-l$((0x2e57d0-0x2e567c)) -c4 -g4 | wc -l
      85

And, I should be able to confirm the other parents from the example above. In the following command '0x11' comes from 80000011, '4' is the number of "bytes" that are used to for OID Lookup, and '2' for the number of N-1 parents that were on the octopus merge.

  $ < .git/objects/info/commit-graph xxd -s$((0x2e567c+0x11*4))
-l$((4*2)) -c4 -g4
  002e56c0: 00008ac3  ....
  002e56c4: 8000b603  ....

Which works out perfectly.

  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x00008ac0*20)))
-l20 -c20 -g20
  000adb44: a849d36cf2877a1890371851710382f463290978  .I.l..z..7.Qq...c).x

  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x0000b603*20)))
-l20 -c20 -g20
  000e3c80: dc8441fdb4598f54865a5c783d1f86c1e0bcb6dc  ..A..Y.T.Z\x=.......

# terminating label

With the 'terminating' chunk, we can see the SHA1 checksum which I already covered at the beginning.

  $ < .git/objects/info/commit-graph xxd -s0x2e57d0 -g20 -c20
  002e57d0: 35507183b1e9546f9e4844f0796d630daebc85d

-- -grant welch -gwelch925@gmail.com

Derrick Stolee· Jun 28, 2018, 12:49 UTC · re: Grant Welch · lore

Re: Inconsistencies in commit-graph technical docs.

On 6/28/2018 1:11 AM, Grant Welch wrote:

Show 24 quoted lines

> I recently read the "Supercharging the Git Commit Graph blog by
> Derrick Stolee. I found the article interesting and wanted to verify
> the performance numbers for myself. Then that led me to want to know
> more about the implementation, so I read the technical design notes in
> commit-graph.txt, and then I jumped into the format documentation in
> commit-graph-format.txt.
>
> Along the way, I noticed a few issues. They might just be errors in
> the documentation, but I figured it was worth documenting my entire
> process just to be sure.
>
> "Supercharging the Git Commit Graph", by Derrick Stolee:
>    https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/
>
> # TL;DR
>
> I found a few discrepencies between the documentation in
> commit-graph-format.txt and the results that I observed for myself.
>
> 1. The "Commit Data" chunk signature is documented to be 'CGET', but
> it should be 'CDAT'.
>
> commit-graph.c:18
>    #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */

Thanks for catching this! Thankfully, this is an easy fix, as we only need to update the documentation.

Show 5 quoted lines

> 2. The "no parent" value is documented to be 0xffffffff, but is
> actually 0x70000000.
>
> commit-graph.c:34
>    #define GRAPH_PARENT_NONE 0x70000000

This is a more important mistake, as it affects the data that was written in the commit-graph file.

Part of the problem is that leading hex digit of 0x7 which in binary is 0b0111. We already designed a limit of at most 2^{31}-1 (~2.1 billion) commits in the commit-graph because of the way we track octopus edges, but this mistake has cost us more: we cannot store more than ~1.8 billion commits.

I'm sorry for this mixup, mostly because it is aesthetically unpleasant. Those extra 300 million commits mean less to me than having a clean file format.

> 3. The "generation" field isn't set on any of the commits. (I don't
> know what to make of this.)

This is a difference between 2.18 and current 'master', which merged ds/generation-numbers. Commit-graphs written with Git 2.18 have all generation numbers listed as GENERATION_NUMBER_ZERO (0), which lets future versions know that the generation number is not computed yet, so the next commit-graph write will compute the correct generation number.

I'll send a patch soon fixing these doc issues.

Thanks, -Stolee

Derrick Stolee· Jun 28, 2018, 12:52 UTC · re: Derrick Stolee · lore

[PATCH] commit-graph: fix documentation inconsistencies

The commit-graph feature shipped in Git 2.18 has some inconsistencies in the constants used by the implementation and specified by the format document.

The commit data chunk uses the key "CDAT" in the file format, but was previously documented to say "CGET".

The commit data chunk stores commit parents using two 32-bit fields that typically store the integer position of the parent in the list of commit ids within the commit-graph file. When a parent does not exist, we had documented the value 0xffffffff, but implemented the value 0x70000000. This swap is easy to correct in the documentation, but unfortunately reduces the number of commits that we can store in the commit-graph. Update that estimate, too.

Reported-by: Grant Welch <gwelch925@gmail.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/commit-graph-format.txt | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
index ad6af8105c..91c2fbd86a 100644
--- a/Documentation/technical/commit-graph-format.txt
+++ b/Documentation/technical/commit-graph-format.txt
@@ -18,9 +18,9 @@ metadata, including:
   the graph file.
 
 These positional references are stored as unsigned 32-bit integers
-corresponding to the array position withing the list of commit OIDs. We
-use the most-significant bit for special purposes, so we can store at most
-(1 << 31) - 1 (around 2 billion) commits.
+corresponding to the array position withing the list of commit OIDs. Due
+to some special constants we use to track parents, we can store at most
+(1 << 30) + (1 << 29) + (1 << 28) - 1 (around 1.8 billion) commits.
 
 == Commit graph files have the following format:
 
@@ -70,10 +70,10 @@ CHUNK DATA:
   OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
       The OIDs for all commits in the graph, sorted in ascending order.
 
-  Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
+  Commit Data (ID: {'C', 'D', 'A', 'T' }) (N * (H + 16) bytes)
     * The first H bytes are for the OID of the root tree.
     * The next 8 bytes are for the positions of the first two parents
-      of the ith commit. Stores value 0xffffffff if no parent in that
+      of the ith commit. Stores value 0x7000000 if no parent in that
       position. If there are more than two parents, the second value
       has its most-significant bit on and the other bits store an array
       position into the Large Edge List chunk.

base-commit: ed843436dd4924c10669820cc73daf50f0b4dabd

-- 
2.18.0.24.g1b579a2ee9

Grant Welch· Jun 28, 2018, 16:54 UTC · re: Derrick Stolee · lore

Re: Inconsistencies in commit-graph technical docs.

Thanks for the quick response and for the patch.

I started writing such a long process document because I _thought_ that I found a major issue with the Large Edge List. But, in the end, it was user error. It turned out that I was looking at index '11' when I should have been looking at index '0x11' ('17'). Whoops! On Thu, Jun 28, 2018 at 5:49 AM Derrick Stolee <stolee@gmail.com> wrote:

Show 62 quoted lines

>
> On 6/28/2018 1:11 AM, Grant Welch wrote:
> > I recently read the "Supercharging the Git Commit Graph blog by
> > Derrick Stolee. I found the article interesting and wanted to verify
> > the performance numbers for myself. Then that led me to want to know
> > more about the implementation, so I read the technical design notes in
> > commit-graph.txt, and then I jumped into the format documentation in
> > commit-graph-format.txt.
> >
> > Along the way, I noticed a few issues. They might just be errors in
> > the documentation, but I figured it was worth documenting my entire
> > process just to be sure.
> >
> > "Supercharging the Git Commit Graph", by Derrick Stolee:
> >    https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/
> >
> > # TL;DR
> >
> > I found a few discrepencies between the documentation in
> > commit-graph-format.txt and the results that I observed for myself.
> >
> > 1. The "Commit Data" chunk signature is documented to be 'CGET', but
> > it should be 'CDAT'.
> >
> > commit-graph.c:18
> >    #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
>
> Thanks for catching this! Thankfully, this is an easy fix, as we only
> need to update the documentation.
>
> > 2. The "no parent" value is documented to be 0xffffffff, but is
> > actually 0x70000000.
> >
> > commit-graph.c:34
> >    #define GRAPH_PARENT_NONE 0x70000000
>
> This is a more important mistake, as it affects the data that was
> written in the commit-graph file.
>
> Part of the problem is that leading hex digit of 0x7 which in binary is
> 0b0111. We already designed a limit of at most 2^{31}-1 (~2.1 billion)
> commits in the commit-graph because of the way we track octopus edges,
> but this mistake has cost us more: we cannot store more than ~1.8
> billion commits.
>
> I'm sorry for this mixup, mostly because it is aesthetically unpleasant.
> Those extra 300 million commits mean less to me than having a clean file
> format.
>
> > 3. The "generation" field isn't set on any of the commits. (I don't
> > know what to make of this.)
>
> This is a difference between 2.18 and current 'master', which merged
> ds/generation-numbers. Commit-graphs written with Git 2.18 have all
> generation numbers listed as GENERATION_NUMBER_ZERO (0), which lets
> future versions know that the generation number is not computed yet, so
> the next commit-graph write will compute the correct generation number.
>
> I'll send a patch soon fixing these doc issues.
>
> Thanks,
> -Stolee

-- -grant welch -gwelch925@gmail.com