{"thread":{"id":"48794","subject":"Inconsistencies in commit-graph technical docs.","startedAt":"2018-06-28T05:11:45Z","lastAt":"2018-06-28T16:54:55Z","messageCount":4,"participants":["Grant Welch","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"351183","messageId":"CAMYKhtUi3nCmTjZ8pXbNCxaKa6h9+1OSD7YitTeip+807w7dJA@mail.gmail.com","threadId":"48794","inReplyTo":null,"subject":"Inconsistencies in commit-graph technical docs.","fromName":"Grant Welch","fromEmail":"gwelch925@gmail.com","sentAt":"2018-06-28T05:11:03Z","receivedAt":"2018-06-28T05:11:45Z","isPatch":false,"sender":{"key":"gwelch925@gmail.com","avatar":null},"body":"I recently read the \"Supercharging the Git Commit Graph\" blog by\nDerrick Stolee. I found the article interesting and wanted to verify\nthe performance numbers for myself. Then that led me to want to know\nmore about the implementation, so I read the technical design notes in\ncommit-graph.txt, and then I jumped into the format documentation in\ncommit-graph-format.txt.\n\nAlong the way, I noticed a few issues. They might just be errors in\nthe documentation, but I figured it was worth documenting my entire\nprocess just to be sure.\n\n\"Supercharging the Git Commit Graph\", by Derrick Stolee:\n  https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/\n\n# TL;DR\n\nI found a few discrepencies between the documentation in\ncommit-graph-format.txt and the results that I observed for myself.\n\n1. The \"Commit Data\" chunk signature is documented to be 'CGET', but\nit should be 'CDAT'.\n\ncommit-graph.c:18\n  #define GRAPH_CHUNKID_DATA 0x43444154 /* \"CDAT\" */\n\n2. The \"no parent\" value is documented to be 0xffffffff, but is\nactually 0x70000000.\n\ncommit-graph.c:34\n  #define GRAPH_PARENT_NONE 0x70000000\n\n3. The \"generation\" field isn't set on any of the commits. (I don't\nknow what to make of this.)\n\n# Documented Process\n\nJust to follow along, here are the details about my local repo. I\ndon't have any local changes; I just track upstream.\n\nrepo:    git/git\nremotes: git://git.kernel.org/pub/scm/git/git.git (origin)\nbranch:  master\ncommit:  ed843436dd4924c10669820cc73daf50f0b4dabd\n\nos:      MacOS 10.11.6 (El Capitan)\ngit:     2.18.0\n\nJust to be clear, I am following the details as described in:\n  /Documentation/technical/commit-graph-format.txt\n\n# Create the commit-graph File\n\nAs a setup step, I have to prepare the commit-graph file as described\nin the blog post.\n\n  $ git show-ref -s | git commit-graph write --stdin-commits\n\n# Verify SHA1 Checksum\n\nStarting at the end first because like most (all?) of git's binary\nformats, there is a SHA1 checksum that verifies the integrity of the\nfile. Everything checks out fine.\n\n  $ < .git/objects/info/commit-graph tail -c 20 | xxd -p\n  35507183b1e9546f9e4844f0796d630daebc85d8\n\n  $ < .git/objects/info/commit-graph wc -c\n  3037156\n\n  $ < .git/objects/info/commit-graph head -c $((3037156-20)) | sha1sum\n  35507183b1e9546f9e4844f0796d630daebc85d8  -\n\n# Header\n\nThe header looks good:\n* signature:   CGPH\n* version:     1\n* hash:        1 (SHA1)\n* \"chunks\":    4\n* \"reserved\":  (ignored)\n\n  $ < .git/objects/info/commit-graph xxd -l8\n  00000000: 4347 5048 0101 0400                      CGPH....\n\n# Chunk Lookup, Problem: CGET/CDAT\n\nI have all of the documented \"chunks\". but it appears, that the\ndocumentation is wrong for the \"Commit Data\" chunk. The document\nsignature is 'CGET', but I'm getting 'CDAT'.\n\n* OIDF, Object ID Fanout:   0x44\n* OIDL, Object ID Lookup:   0x444\n* CDAT, Commit Data:        0x108f58\n* EDGE, Large Edge List:    0x2e577c\n*     , terminating label:  0x2e57d0\n\n  $ < .git/objects/info/commit-graph xxd -s8 -l$(((4+1)*12)) -c12 -g4\n  00000008: 4f494446 00000000 00000044  OIDF.......D\n  00000014: 4f49444c 00000000 00000444  OIDL.......D\n  00000020: 43444154 00000000 00108f58  CDAT.......X\n  0000002c: 45444745 00000000 002e567c  EDGE......V|\n  00000038: 00000000 00000000 002e57d0  ..........W.\n\n# OID Fanout\n\nNot much to tell here, but since it's important, I'll just show last\nline so know how many commits are recorded in the file. Everything\nchecks out that I have 54209 commits in my local repo.\n\n  $ < .git/objects/info/commit-graph xxd -s0x44 -l$((256*4)) -c4 -g4\n  ...\n  00000440: 0000d3c1\n\n  $ echo $((0x0000d3c1))\n  54209\n\n  $ git rev-list --all | wc -l\n    54209\n\n# OID Lookup\n\nAgain, not much to see here; just an alphanumeric, sequential list off\nall the commit ids.\n\n  $ < .git/objects/info/commit-graph xxd -s0x444 -l$((54209*20)) -c20 -g20\n  ...\n  00108f44: fffe694d607ea683b5d08ee99a46d9b06cb74006  ..iM`~.......F..l.@.\n\n  $ git cat-file -p fffe694d607ea683b5d08ee99a46d9b06cb74006\n  tree 1241274386e9d5dabaf370477ff19ba0eb36c3c2\n  parent 84dee6bbc9eb6dd8e613414ed0271d8290549e89\n  author Eric Wong <normalperson@yhbt.net> 1168151155 -0800\n  committer Junio C Hamano <junkio@cox.net> 1168152528 -0800\n  ...\n\n# Commit Data\n\nThis is where I start to see inconsistencies with the documented format.\n\n  $ < .git/objects/info/commit-graph xxd -s0x108f58\n-l$((54209*(20+16))) -c36 -g4\n  ...\n  002e5658: 12412743 86e9d5da baf37047 7ff19ba0 eb36c3c2 00006dea\n70000000 00000000 45a097d0\n\nFrom the above 'git cat-file' command, we can confirm the tree is correct.\n\ntree:        1241274386e9d5dabaf370477ff19ba0eb36c3c2\nparent1:     00006dea\nparent2:     70000000\ngeneration:  00000000\ntimestamp:   45a097d0\n\nAs does the timestamp.\n\n  $ date --date @$((0x45a097d0)) +%s\n  1168152528\n\nParent #1 looks good as well.\n\n  < .git/objects/info/commit-graph xxd -s$((0x444+(0x00006dea*20)))\n-l20 -c20 -g20\n  00089a8c: 84dee6bbc9eb6dd8e613414ed0271d8290549e89\n\n## Problem: Parent #2\n\nParent #2 (70000000), however appears to be a mystery value. The value\nis way too high to actually be in the OID Lookup table. And, the only\ndocumented magic numbers are 0xffffffff (no parent) and\n0x80000000|0x??????? (octopus merge; see: Last Edge List).\n\n## Problem: Generation\n\nAlso, none of these objects have their 'generation' field set.\n\n  $ < .git/objects/info/commit-graph xxd -s0x108f58\n-l$((54209*(20+16))) -c36 -g4 | grep 00000000 | wc -l\n    54209\n\n## Check Octopus Merges\n\nThe final \"chunk\", Large Edge List, is for handling the extra data\nfrom octopus merge commits. Since I can't conceive of a fancy xxd\ncommand to that could list them, I have to go the long way round to\nfind an example of one.\n\n  $ git rev-list --all --min-parents=3 | wc -l\n      35\n\n  $ git rev-list --all --min-parents=3\n  25bf951381a4880c43a3d1c65e6dce651e61148f\n  ...\n\n  $ < .git/objects/info/commit-graph xxd -s0x444 -l$((54209*20)) -c20\n-g20 | grep 25bf951381a4880c43a3d1c65e6dce651e61148f\n  0002706c: 25bf951381a4880c43a3d1c65e6dce651e61148f  %.......C...^m.e.a..\n\n  $ echo $(((0x0002706c-0x444)/20))\n  7938\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x444+(7938*20))) -l20 -c20 -g20\n  0002706c: 25bf951381a4880c43a3d1c65e6dce651e61148f  %.......C...^m.e.a..\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x108f58+(7938*36))) -l36 -c36 -g4\n  0014eba0: ce9488df 264bc29a 37b47932 0fad03c9 3a470db7 000004c7\n80000011 00000000 594dbf30\n\n  $ git dump 25bf951381a4880c43a3d1c65e6dce651e61148f\n  tree ce9488df264bc29a37b479320fad03c93a470db7\n  parent 05ec6e13aaf33b6a647e1321203a770e697eea9a\n  parent a84f3e59ebde9e891275ef8325c432db6bdf950c\n  parent dc8441fdb4598f54865a5c783d1f86c1e0bcb6dc\n  author Junio C Hamano <gitster@pobox.com> 1498083644 -0700\n  committer Junio C Hamano <gitster@pobox.com> 1498267440 -0700\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x000004c7*20)))\n-l20 -c20 -g20\n  000063d0: 05ec6e13aaf33b6a647e1321203a770e697eea9a\n\nIn the above commands, I was able to find a merge commit with more\nthan 2 parents using git-rev-list. From there, I was able to find that\ncommit in the \"OID Lookup\" table and determine it's position. With\nthat position, I was able to find the \"Commit Data\" associated with\nit. Finally, the git-cat-file confirms that the tree is correct and\nthat the first parent commit is correct (after performing another OID\nlookup).\n\nNow it's just a matter of reviewing the last chunk to learn more about 80000011.\n\n## Naive Solution for Finding Octopus Merges\n\nIn a repo with very few octopus merges, I would expect this to work\n100% of the time. However, I doubt that it will work for a repo like\nlinux/linux that have a lot of commits that are merged through octopus\nmerges.\n\nThis assumes that '80000' won't occur in the tree OID, parent1,\ngeneration, nor the timestamp. Seems like a fair bet, but qualifies as\nnaive.\n\nI tested using '8000', but it created too many false positives. For\ngit/git, '800000' works just as well as '80000', but would more likely\nto under report elsewhere.\n\n  $ < .git/objects/info/commit-graph xxd -s0x108f58\n-l$((54209*(20+16))) -c36 -g4 | grep 80000 | wc -l\n      35\n\n  $ < .git/objects/info/commit-graph xxd -s0x108f58\n-l$((54209*(20+16))) -c36 -g4 | grep 80000\n  ...\n  0014eba0: ce9488df 264bc29a 37b47932 0fad03c9 3a470db7 000004c7\n80000011 00000000 594dbf30\n  ...\n\n# Last Edge List\n\nFinally, I can get a list of all the commits that have been a\nparent2-N on an octopus merge.\n\n  $ < .git/objects/info/commit-graph xxd -s0x2e567c\n-l$((0x2e57d0-0x2e567c)) -c4 -g4 | wc -l\n      85\n\nAnd, I should be able to confirm the other parents from the example\nabove. In the following command '0x11' comes from 80000011, '4' is the\nnumber of \"bytes\" that are used to for OID Lookup, and '2' for the\nnumber of N-1 parents that were on the octopus merge.\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x2e567c+0x11*4))\n-l$((4*2)) -c4 -g4\n  002e56c0: 00008ac3  ....\n  002e56c4: 8000b603  ....\n\nWhich works out perfectly.\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x00008ac0*20)))\n-l20 -c20 -g20\n  000adb44: a849d36cf2877a1890371851710382f463290978  .I.l..z..7.Qq...c).x\n\n  $ < .git/objects/info/commit-graph xxd -s$((0x444+(0x0000b603*20)))\n-l20 -c20 -g20\n  000e3c80: dc8441fdb4598f54865a5c783d1f86c1e0bcb6dc  ..A..Y.T.Z\\x=.......\n\n# terminating label\n\nWith the 'terminating' chunk, we can see the SHA1 checksum which I\nalready covered at the beginning.\n\n  $ < .git/objects/info/commit-graph xxd -s0x2e57d0 -g20 -c20\n  002e57d0: 35507183b1e9546f9e4844f0796d630daebc85d\n\n\n--\n-grant welch\n-gwelch925@gmail.com\n"},{"id":"351201","messageId":"c48629f1-7b41-d516-84f5-c07ef7881e03@gmail.com","threadId":"48794","inReplyTo":"CAMYKhtUi3nCmTjZ8pXbNCxaKa6h9+1OSD7YitTeip+807w7dJA@mail.gmail.com","subject":"Re: Inconsistencies in commit-graph technical docs.","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-28T12:49:01Z","receivedAt":"2018-06-28T12:49:09Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/28/2018 1:11 AM, Grant Welch wrote:\n> I recently read the \"Supercharging the Git Commit Graph blog by\n> Derrick Stolee. I found the article interesting and wanted to verify\n> the performance numbers for myself. Then that led me to want to know\n> more about the implementation, so I read the technical design notes in\n> commit-graph.txt, and then I jumped into the format documentation in\n> commit-graph-format.txt.\n>\n> Along the way, I noticed a few issues. They might just be errors in\n> the documentation, but I figured it was worth documenting my entire\n> process just to be sure.\n>\n> \"Supercharging the Git Commit Graph\", by Derrick Stolee:\n>    https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/\n>\n> # TL;DR\n>\n> I found a few discrepencies between the documentation in\n> commit-graph-format.txt and the results that I observed for myself.\n>\n> 1. The \"Commit Data\" chunk signature is documented to be 'CGET', but\n> it should be 'CDAT'.\n>\n> commit-graph.c:18\n>    #define GRAPH_CHUNKID_DATA 0x43444154 /* \"CDAT\" */\n\nThanks for catching this! Thankfully, this is an easy fix, as we only \nneed to update the documentation.\n\n> 2. The \"no parent\" value is documented to be 0xffffffff, but is\n> actually 0x70000000.\n>\n> commit-graph.c:34\n>    #define GRAPH_PARENT_NONE 0x70000000\n\nThis is a more important mistake, as it affects the data that was \nwritten in the commit-graph file.\n\nPart of the problem is that leading hex digit of 0x7 which in binary is \n0b0111. We already designed a limit of at most 2^{31}-1 (~2.1 billion) \ncommits in the commit-graph because of the way we track octopus edges, \nbut this mistake has cost us more: we cannot store more than ~1.8 \nbillion commits.\n\nI'm sorry for this mixup, mostly because it is aesthetically unpleasant. \nThose extra 300 million commits mean less to me than having a clean file \nformat.\n\n> 3. The \"generation\" field isn't set on any of the commits. (I don't\n> know what to make of this.)\n\nThis is a difference between 2.18 and current 'master', which merged \nds/generation-numbers. Commit-graphs written with Git 2.18 have all \ngeneration numbers listed as GENERATION_NUMBER_ZERO (0), which lets \nfuture versions know that the generation number is not computed yet, so \nthe next commit-graph write will compute the correct generation number.\n\nI'll send a patch soon fixing these doc issues.\n\nThanks,\n-Stolee\n"},{"id":"351202","messageId":"20180628125235.77256-1-dstolee@microsoft.com","threadId":"48794","inReplyTo":"c48629f1-7b41-d516-84f5-c07ef7881e03@gmail.com","subject":"[PATCH] commit-graph: fix documentation inconsistencies","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-28T12:52:45Z","receivedAt":"2018-06-28T12:52:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The commit-graph feature shipped in Git 2.18 has some inconsistencies in\nthe constants used by the implementation and specified by the format\ndocument.\n\nThe commit data chunk uses the key \"CDAT\" in the file format, but was\npreviously documented to say \"CGET\".\n\nThe commit data chunk stores commit parents using two 32-bit fields that\ntypically store the integer position of the parent in the list of commit\nids within the commit-graph file. When a parent does not exist, we had\ndocumented the value 0xffffffff, but implemented the value 0x70000000.\nThis swap is easy to correct in the documentation, but unfortunately\nreduces the number of commits that we can store in the commit-graph.\nUpdate that estimate, too.\n\nReported-by: Grant Welch <gwelch925@gmail.com>\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n Documentation/technical/commit-graph-format.txt | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt\nindex ad6af8105c..91c2fbd86a 100644\n--- a/Documentation/technical/commit-graph-format.txt\n+++ b/Documentation/technical/commit-graph-format.txt\n@@ -18,9 +18,9 @@ metadata, including:\n   the graph file.\n \n These positional references are stored as unsigned 32-bit integers\n-corresponding to the array position withing the list of commit OIDs. We\n-use the most-significant bit for special purposes, so we can store at most\n-(1 << 31) - 1 (around 2 billion) commits.\n+corresponding to the array position withing the list of commit OIDs. Due\n+to some special constants we use to track parents, we can store at most\n+(1 << 30) + (1 << 29) + (1 << 28) - 1 (around 1.8 billion) commits.\n \n == Commit graph files have the following format:\n \n@@ -70,10 +70,10 @@ CHUNK DATA:\n   OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)\n       The OIDs for all commits in the graph, sorted in ascending order.\n \n-  Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)\n+  Commit Data (ID: {'C', 'D', 'A', 'T' }) (N * (H + 16) bytes)\n     * The first H bytes are for the OID of the root tree.\n     * The next 8 bytes are for the positions of the first two parents\n-      of the ith commit. Stores value 0xffffffff if no parent in that\n+      of the ith commit. Stores value 0x7000000 if no parent in that\n       position. If there are more than two parents, the second value\n       has its most-significant bit on and the other bits store an array\n       position into the Large Edge List chunk.\n\nbase-commit: ed843436dd4924c10669820cc73daf50f0b4dabd\n-- \n2.18.0.24.g1b579a2ee9\n\n"},{"id":"351236","messageId":"CAMYKhtUCm8+_vK2y3Fxd=Cj5Lq7=pkORNm0T1y+UFmdtwR6DMQ@mail.gmail.com","threadId":"48794","inReplyTo":"c48629f1-7b41-d516-84f5-c07ef7881e03@gmail.com","subject":"Re: Inconsistencies in commit-graph technical docs.","fromName":"Grant Welch","fromEmail":"gwelch925@gmail.com","sentAt":"2018-06-28T16:54:16Z","receivedAt":"2018-06-28T16:54:55Z","isPatch":false,"sender":{"key":"gwelch925@gmail.com","avatar":null},"body":"Thanks for the quick response and for the patch.\n\nI started writing such a long process document because I _thought_\nthat I found a major issue with the Large Edge List. But, in the end,\nit was user error. It turned out that I was looking at index '11' when\nI should have been looking at index '0x11' ('17'). Whoops!\nOn Thu, Jun 28, 2018 at 5:49 AM Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 6/28/2018 1:11 AM, Grant Welch wrote:\n> > I recently read the \"Supercharging the Git Commit Graph blog by\n> > Derrick Stolee. I found the article interesting and wanted to verify\n> > the performance numbers for myself. Then that led me to want to know\n> > more about the implementation, so I read the technical design notes in\n> > commit-graph.txt, and then I jumped into the format documentation in\n> > commit-graph-format.txt.\n> >\n> > Along the way, I noticed a few issues. They might just be errors in\n> > the documentation, but I figured it was worth documenting my entire\n> > process just to be sure.\n> >\n> > \"Supercharging the Git Commit Graph\", by Derrick Stolee:\n> >    https://blogs.msdn.microsoft.com/devops/2018/06/25/supercharging-the-git-commit-graph/\n> >\n> > # TL;DR\n> >\n> > I found a few discrepencies between the documentation in\n> > commit-graph-format.txt and the results that I observed for myself.\n> >\n> > 1. The \"Commit Data\" chunk signature is documented to be 'CGET', but\n> > it should be 'CDAT'.\n> >\n> > commit-graph.c:18\n> >    #define GRAPH_CHUNKID_DATA 0x43444154 /* \"CDAT\" */\n>\n> Thanks for catching this! Thankfully, this is an easy fix, as we only\n> need to update the documentation.\n>\n> > 2. The \"no parent\" value is documented to be 0xffffffff, but is\n> > actually 0x70000000.\n> >\n> > commit-graph.c:34\n> >    #define GRAPH_PARENT_NONE 0x70000000\n>\n> This is a more important mistake, as it affects the data that was\n> written in the commit-graph file.\n>\n> Part of the problem is that leading hex digit of 0x7 which in binary is\n> 0b0111. We already designed a limit of at most 2^{31}-1 (~2.1 billion)\n> commits in the commit-graph because of the way we track octopus edges,\n> but this mistake has cost us more: we cannot store more than ~1.8\n> billion commits.\n>\n> I'm sorry for this mixup, mostly because it is aesthetically unpleasant.\n> Those extra 300 million commits mean less to me than having a clean file\n> format.\n>\n> > 3. The \"generation\" field isn't set on any of the commits. (I don't\n> > know what to make of this.)\n>\n> This is a difference between 2.18 and current 'master', which merged\n> ds/generation-numbers. Commit-graphs written with Git 2.18 have all\n> generation numbers listed as GENERATION_NUMBER_ZERO (0), which lets\n> future versions know that the generation number is not computed yet, so\n> the next commit-graph write will compute the correct generation number.\n>\n> I'll send a patch soon fixing these doc issues.\n>\n> Thanks,\n> -Stolee\n\n\n\n--\n-grant welch\n-gwelch925@gmail.com\n"}]}