{"thread":{"id":"47690","subject":"[PATCH 00/14] Serialized Commit Graph","startedAt":"2018-01-25T14:02:43Z","lastAt":"2018-01-26T22:04:56Z","messageCount":49,"participants":["Derrick Stolee","Ævar Arnfjörð Bjarmason","Stefan Beller","Junio C Hamano","Duy Nguyen","Andreas Schwab"],"isPatch":true,"patchVersion":1,"patchTotal":14},"messages":[{"id":"337366","messageId":"20180125140231.65604-1-dstolee@microsoft.com","threadId":"47690","inReplyTo":null,"subject":"[PATCH 00/14] Serialized Commit Graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:17Z","receivedAt":"2018-01-25T14:02:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As promised [1], this patch contains a way to serialize the commit graph.\nThe current implementation defines a new file format to store the graph\nstructure (parent relationships) and basic commit metadata (commit date,\nroot tree OID) in order to prevent parsing raw commits while performing\nbasic graph walks. For example, we do not need to parse the full commit\nwhen performing these walks:\n\n* 'git log --topo-order -1000' walks all reachable commits to avoid\n incorrect topological orders, but only needs the commit message for\n the top 1000 commits.\n\n* 'git merge-base ' may walk many commits to find the correct\n boundary between the commits reachable from A and those reachable\n from B. No commit messages are needed.\n\n* 'git branch -vv' checks ahead/behind status for all local branches\n compared to their upstream remote branches. This is essentially as\n hard as computing merge bases for each.\n\nThe current patch speeds up these calculations by injecting a check in\nparse_commit_gently() to check if there is a graph file and using that\nto provide the required metadata to the struct commit.\n\nThe file format has room to store generation numbers, which will be\nprovided as a patch after this framework is merged. Generation numbers\nare referenced by the design document but not implemented in order to\nmake the current patch focus on the graph construction process. Once\nthat is stable, it will be easier to add generation numbers and make\ngraph walks aware of generation numbers one-by-one.\n\nHere are some performance results for a copy of the Linux repository\nwhere 'master' has 704,766 reachable commits and is behind 'origin/master'\nby 19,610 commits.\n\n| Command | Before | After | Rel % |\n|----------------------------------|--------|--------|-------|\n| log --oneline --topo-order -1000 | 5.9s | 0.7s | -88% |\n| branch -vv | 0.42s | 0.27s | -35% |\n| rev-list --all | 6.4s | 1.0s | -84% |\n| rev-list --all --objects | 32.6s | 27.6s | -15% |\n\nTo test this yourself, run the following on your repo:\n\n\tgit config core.graph true\n\tgit show-ref -s | git graph --write --update-head\n\nThe second command writes a commit graph file containing every commit\nreachable from your refs. Now, all git commands that walk commits will\ncheck your graph first before consulting the ODB. You can run your own\nperformance comparisions by toggling the 'core.graph' setting.\n\n[1] https://public-inbox.org/git/d154319e-bb9e-b300-7c37-27b1dcd2a2ce@jeffhostetler.com/\n Re: What's cooking in git.git (Jan 2018, #03; Tue, 23)\n\n[2] https://github.com/derrickstolee/git/pull/2\n A GitHub pull request containing the latest version of this patch.\n\nP.S. I'm sending this patch from my gmail address to avoid Outlook\nmunging the URLs included in the design document.\n\nDerrick Stolee (14):\n graph: add packed graph design document\n packed-graph: add core.graph setting\n packed-graph: create git-graph builtin\n packed-graph: add format document\n packed-graph: implement construct_graph()\n packed-graph: implement git-graph --write\n packed-graph: implement git-graph --read\n graph: implement git-graph --update-head\n packed-graph: implement git-graph --clear\n packed-graph: teach git-graph --delete-expired\n commit: integrate packed graph with commit parsing\n packed-graph: read only from specific pack-indexes\n packed-graph: close under reachability\n packed-graph: teach git-graph to read commits\n\n Documentation/config.txt | 3 +\n Documentation/git-graph.txt | 102 ++++\n Documentation/technical/graph-format.txt | 88 ++++\n Documentation/technical/packed-graph.txt | 185 +++++++\n Makefile | 2 +\n alloc.c | 1 +\n builtin.h | 1 +\n builtin/graph.c | 231 +++++++++\n cache.h | 1 +\n command-list.txt | 1 +\n commit.c | 20 +-\n commit.h | 2 +\n config.c | 5 +\n environment.c | 1 +\n git.c | 1 +\n log-tree.c | 3 +-\n packed-graph.c | 840 +++++++++++++++++++++++++++++++\n packed-graph.h | 65 +++\n packfile.c | 4 +-\n packfile.h | 2 +\n t/t5319-graph.sh | 271 ++++++++++\n 21 files changed, 1822 insertions(+), 7 deletions(-)\n create mode 100644 Documentation/git-graph.txt\n create mode 100644 Documentation/technical/graph-format.txt\n create mode 100644 Documentation/technical/packed-graph.txt\n create mode 100644 builtin/graph.c\n create mode 100644 packed-graph.c\n create mode 100644 packed-graph.h\n create mode 100755 t/t5319-graph.sh\n\n-- \n2.16.0\n\n"},{"id":"337367","messageId":"20180125140231.65604-2-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 01/14] graph: add packed graph design document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:18Z","receivedAt":"2018-01-25T14:02:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Add Documentation/technical/packed-graph.txt with details of the planned\npacked graph feature, including future plans.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++\n 1 file changed, 185 insertions(+)\n create mode 100644 Documentation/technical/packed-graph.txt\n\ndiff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt\nnew file mode 100644\nindex 0000000000..fcc0c83874\n--- /dev/null\n+++ b/Documentation/technical/packed-graph.txt\n@@ -0,0 +1,185 @@\n+Git Packed Graph Design Notes\n+=============================\n+\n+Git walks the commit graph for many reasons, including:\n+\n+1. Listing and filtering commit history.\n+2. Computing merge bases.\n+\n+These operations can become slow as the commit count grows above 100K.\n+The merge base calculation shows up in many user-facing commands, such\n+as 'status' and 'fetch' and can take minutes to compute depending on\n+data shape. There are two main costs here:\n+\n+1. Decompressing and parsing commits.\n+2. Walking the entire graph to avoid topological order mistakes.\n+\n+The packed graph is a file that stores the commit graph structure along\n+with some extra metadata to speed up graph walks. This format allows a\n+consumer to load the following info for a commit:\n+\n+1. The commit OID.\n+2. The list of parents.\n+3. The commit date.\n+4. The root tree OID.\n+5. An integer ID for fast lookups in the graph.\n+6. The generation number (see definition below).\n+\n+Values 1-4 satisfy the requirements of parse_commit_gently().\n+\n+By providing an integer ID we can avoid lookups in the graph as we walk\n+commits. Specifically, we need to provide the integer ID of the parent\n+commits so we navigate directly to their information on request.\n+\n+Define the \"generation number\" of a commit recursively as follows:\n+ * A commit with no parents (a root commit) has generation number 1.\n+ * A commit with at least one parent has generation number 1 more than\n+ the largest generation number among its parents.\n+Equivalently, the generation number is one more than the length of a\n+longest path from the commit to a root commit. The recursive definition\n+is easier to use for computation and the following property:\n+\n+ If A and B are commits with generation numbers N and M, respectively,\n+ and N <= M, then A cannot reach B. That is, we know without searching\n+ that B is not an ancestor of A because it is further from a root commit\n+ than A.\n+\n+ Conversely, when checking if A is an ancestor of B, then we only need\n+ to walk commits until all commits on the walk boundary have generation\n+ number at most N. If we walk commits using a priority queue seeded by\n+ generation numbers, then we always expand the boundary commit with highest\n+ generation number and can easily detect the stopping condition.\n+\n+This property can be used to significantly reduce the time it takes to\n+walk commits and determine topological relationships. Without generation\n+numbers, the general heuristic is the following:\n+\n+ If A and B are commits with commit time X and Y, respectively, and\n+ X < Y, then A _probably_ cannot reach B.\n+\n+This heuristic is currently used whenever the computation can make\n+mistakes with topological orders (such as \"git log\" with default order),\n+but is not used when the topological order is required (such as merge\n+base calculations, \"git log --graph\").\n+\n+Design Details\n+--------------\n+\n+- A graph file is stored in a file named 'graph-.graph' in the pack\n+ directory. This could be stored in an alternate.\n+\n+- The most-recent graph file OID is stored in a 'graph-head' file for\n+ immediate access and storing backup graphs. This could be stored in an\n+ alternate, and refers to a 'graph-.graph' file in the same pack\n+ directory.\n+\n+- The core.graph config setting must be on to create or consume graph files.\n+\n+- The graph file is only a supplemental structure. If a user downgrades\n+ or disables the 'core.graph' config setting, then the existing ODB is\n+ sufficient.\n+\n+- The file format includes parameters for the object id length\n+ and hash algorithm, so a future change of hash algorithm does\n+ not require a change in format.\n+\n+Current Limitations\n+-------------------\n+\n+- Only one graph file is used at one time. This allows the integer ID to\n+ seek into the single graph file. It is possible to extend the model\n+ for multiple graph files, but that is currently not part of the design.\n+\n+- .graph files are managed only by the 'graph' builtin. These are not\n+ updated automatically during clone or fetch.\n+\n+- There is no '--verify' option for the 'graph' builtin to verify the\n+ contents of the graph file.\n+\n+- The graph only considers commits existing in packfiles and does not\n+ walk to fill in reachable commits. [Small]\n+\n+- When rewriting the graph, we do not check for a commit still existing\n+ in the ODB, so garbage collection may remove commits\n+\n+- Generation numbers are not computed in the current version. The file\n+ format supports storing them, along with a mechanism to upgrade from\n+ a file without generation numbers to one that uses them.\n+\n+Future Work\n+-----------\n+\n+- The file format includes room for precomputed generation numbers. These\n+ are not currently computed, so all generation numbers will be marked as\n+ 0 (or \"uncomputed\"). A later patch will include this calculation.\n+\n+- The current implementation of the 'graph' builtin walks all packed objects\n+ to find a complete list of commits in packfiles. If some commits are\n+ stored as loose objects, then these do not appear in the graph. This is\n+ handled gracefully by the file format, but it would cause incorrect\n+ generation number calculations. We should implement the construct_graph()\n+ method in a way that walks all commits reachable from some starting set\n+ and then can use complete information for generation numbers. (Some\n+ care must be taken around shallow clones.)\n+\n+- The graph is not currently integrated with grafts.\n+\n+- After computing and storing generation numbers, we must make graph\n+ walks aware of generation numbers to gain performance benefits. This\n+ will mostly be accomplished by swapping a commit-date-ordered priority\n+ queue with one ordered by generation number. The following operations\n+ are important candidates:\n+\n+ - paint_down_to_common()\n+ - 'log --topo-order'\n+\n+- The graph currently only adds commits to a previously existing graph.\n+ When writing a new graph, we could check that the ODB still contains\n+ the commits and choose to remove the commits that are deleted from the\n+ ODB. For performance reasons, this check should remain optional.\n+\n+- Currently, parse_commit_gently() requires filling in the root tree\n+ object for a commit. This passes through lookup_tree() and consequently\n+ lookup_object(). Also, it calls lookup_commit() when loading the parents.\n+ These method calls check the ODB for object existence, even if the\n+ consumer does not need the content. For example, we do not need the\n+ tree contents when computing merge bases. Now that commit parsing is\n+ removed from the computation time, these lookup operations are the\n+ slowest operations keeping graph walks from being fast. Consider\n+ loading these objects without verifying their existence in the ODB and\n+ only loading them fully when consumers need them. Consider a method\n+ such as \"ensure_tree_loaded(commit)\" that fully loads a tree before\n+ using commit->tree.\n+\n+- The current design uses the 'graph' builtin to generate the graph. When\n+ this feature stabilizes enough to recommend to most users, we should\n+ add automatic graph writes to common operations that create many commits.\n+ For example, one coulde compute a graph on 'clone' and 'fetch' commands.\n+\n+Related Links\n+-------------\n+\n+[0] https://bugs.chromium.org/p/git/issues/detail?id=8\n+ Chromium work item for: Serialized Commit Graph\n+\n+[1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/\n+ An abandoned patch that introduced generation numbers.\n+\n+[2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/\n+ Discussion about generation numbers on commits and how they interact\n+ with fsck.\n+\n+[3] https://public-inbox.org/git/20170907094718.b6kuzp2uhvkmwcso@sigill.intra.peff.net/t/#m7a2ea7b355aeda962e6b86404bcbadc648abfbba\n+ More discussion about generation numbers and not storing them inside\n+ commit objects. A valuable quote:\n+\n+ \"I think we should be moving more in the direction of keeping\n+ repo-local caches for optimizations. Reachability bitmaps have been\n+ a big performance win. I think we should be doing the same with our\n+ properties of commits. Not just generation numbers, but making it\n+ cheap to access the graph structure without zlib-inflating whole\n+ commit objects (i.e., packv4 or something like the \"metapacks\" I\n+ proposed a few years ago).\"\n+\n+[4] https://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u\n+ A patch to remove the ahead-behind calculation from 'status'.\n-- \n2.16.0\n\n"},{"id":"337368","messageId":"20180125140231.65604-4-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:20Z","receivedAt":"2018-01-25T14:02:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach Git the 'graph' builtin that will be used for writing and\nreading packed graph files. The current implementation is mostly\nempty, except for a check that the core.graph setting is enabled\nand a '--pack-dir' option.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 7 +++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/graph.c | 36 ++++++++++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n 6 files changed, 47 insertions(+)\n create mode 100644 Documentation/git-graph.txt\n create mode 100644 builtin/graph.c\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nnew file mode 100644\nindex 0000000000..de5a3c07e6\n--- /dev/null\n+++ b/Documentation/git-graph.txt\n@@ -0,0 +1,7 @@\n+git-graph(1)\n+============\n+\n+NAME\n+----\n+git-graph - Write and verify Git commit graphs (.graph files)\n+\ndiff --git a/Makefile b/Makefile\nindex 1a9b23b679..d8b0d0457a 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -965,6 +965,7 @@ BUILTIN_OBJS += builtin/for-each-ref.o\n BUILTIN_OBJS += builtin/fsck.o\n BUILTIN_OBJS += builtin/gc.o\n BUILTIN_OBJS += builtin/get-tar-commit-id.o\n+BUILTIN_OBJS += builtin/graph.o\n BUILTIN_OBJS += builtin/grep.o\n BUILTIN_OBJS += builtin/hash-object.o\n BUILTIN_OBJS += builtin/help.o\ndiff --git a/builtin.h b/builtin.h\nindex 42378f3aa4..ae7e816908 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -168,6 +168,7 @@ extern int cmd_format_patch(int argc, const char **argv, const char *prefix);\n extern int cmd_fsck(int argc, const char **argv, const char *prefix);\n extern int cmd_gc(int argc, const char **argv, const char *prefix);\n extern int cmd_get_tar_commit_id(int argc, const char **argv, const char *prefix);\n+extern int cmd_graph(int argc, const char **argv, const char *prefix);\n extern int cmd_grep(int argc, const char **argv, const char *prefix);\n extern int cmd_hash_object(int argc, const char **argv, const char *prefix);\n extern int cmd_help(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/graph.c b/builtin/graph.c\nnew file mode 100644\nindex 0000000000..a902dc8646\n--- /dev/null\n+++ b/builtin/graph.c\n@@ -0,0 +1,36 @@\n+#include \"builtin.h\"\n+#include \"cache.h\"\n+#include \"config.h\"\n+#include \"dir.h\"\n+#include \"git-compat-util.h\"\n+#include \"lockfile.h\"\n+#include \"packfile.h\"\n+#include \"parse-options.h\"\n+\n+static char const * const builtin_graph_usage[] ={\n+\tN_(\"git graph [--pack-dir ]\"),\n+\tNULL\n+};\n+\n+static struct opts_graph {\n+\tconst char *pack_dir;\n+} opts;\n+\n+int cmd_graph(int argc, const char **argv, const char *prefix)\n+{\n+\tstatic struct option builtin_graph_options[] = {\n+\t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n+\t\t\tN_(\"dir\"),\n+\t\t\tN_(\"The pack directory to store the graph\") },\n+\t\tOPT_END(),\n+\t};\n+\n+\tif (!core_graph)\n+\t\tdie(\"core.graph is false\");\n+\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(builtin_graph_usage, builtin_graph_options);\n+\n+\treturn 0;\n+}\n+\ndiff --git a/command-list.txt b/command-list.txt\nindex a1fad28fd8..d9c17cb9f8 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -61,6 +61,7 @@ git-format-patch mainporcelain\n git-fsck ancillaryinterrogators\n git-gc mainporcelain\n git-get-tar-commit-id ancillaryinterrogators\n+git-graph plumbingmanipulators\n git-grep mainporcelain info\n git-gui mainporcelain\n git-hash-object plumbingmanipulators\ndiff --git a/git.c b/git.c\nindex c870b9719c..29f8b6e7dd 100644\n--- a/git.c\n+++ b/git.c\n@@ -408,6 +408,7 @@ static struct cmd_struct commands[] = {\n \t{ \"fsck-objects\", cmd_fsck, RUN_SETUP },\n \t{ \"gc\", cmd_gc, RUN_SETUP },\n \t{ \"get-tar-commit-id\", cmd_get_tar_commit_id },\n+\t{ \"graph\", cmd_graph, RUN_SETUP_GENTLY },\n \t{ \"grep\", cmd_grep, RUN_SETUP_GENTLY },\n \t{ \"hash-object\", cmd_hash_object },\n \t{ \"help\", cmd_help },\n-- \n2.16.0\n\n"},{"id":"337369","messageId":"20180125140231.65604-3-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 02/14] packed-graph: add core.graph setting","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:19Z","receivedAt":"2018-01-25T14:02:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The packed graph feature is controlled by the new core.graph config\nsetting. This defaults to 0, so the feature is opt-in.\n\nThe intention of core.graph is that a user can always stop checking\nfor or parsing packed graph files if core.graph=0.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/config.txt | 3 +++\n cache.h | 1 +\n config.c | 5 +++++\n environment.c | 1 +\n 4 files changed, 10 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 0e25b2c92b..e7b98fa14f 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -898,6 +898,9 @@ core.notesRef::\n This setting defaults to \"refs/notes/commits\", and it can be overridden by\n the `GIT_NOTES_REF` environment variable. See linkgit:git-notes[1].\n \n+core.graph::\n+\tEnable git commit graph feature. Allows writing and reading from .graph files.\n+\n core.sparseCheckout::\n \tEnable \"sparse checkout\" feature. See section \"Sparse checkout\" in\n \tlinkgit:git-read-tree[1] for more information.\ndiff --git a/cache.h b/cache.h\nindex d8b975a571..655a81ac90 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -825,6 +825,7 @@ extern char *git_replace_ref_base;\n extern int fsync_object_files;\n extern int core_preload_index;\n extern int core_apply_sparse_checkout;\n+extern int core_graph;\n extern int precomposed_unicode;\n extern int protect_hfs;\n extern int protect_ntfs;\ndiff --git a/config.c b/config.c\nindex e617c2018d..fee90912d8 100644\n--- a/config.c\n+++ b/config.c\n@@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.graph\")) {\n+\t\tcore_graph = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.sparsecheckout\")) {\n \t\tcore_apply_sparse_checkout = git_config_bool(var, value);\n \t\treturn 0;\ndiff --git a/environment.c b/environment.c\nindex 63ac38a46f..0c56a3d869 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -61,6 +61,7 @@ enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;\n char *notes_ref_name;\n int grafts_replace_parents = 1;\n int core_apply_sparse_checkout;\n+int core_graph;\n int merge_log_config = -1;\n int precomposed_unicode = -1; /* see probe_utf8_pathname_composition() */\n unsigned long pack_size_limit_cfg;\n-- \n2.16.0\n\n"},{"id":"337370","messageId":"20180125140231.65604-5-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 04/14] packed-graph: add format document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:21Z","receivedAt":"2018-01-25T14:02:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Add document specifying the binary format for packed graphs. This\nformat allows for:\n\n* New versions.\n* New hash functions and hash lengths.\n* Optional extensions.\n\nBasic header information is followed by a binary table of contents\ninto \"chunks\" that include:\n\n* An ordered list of commit object IDs.\n* A 256-entry fanout into that list of OIDs.\n* A list of metadata for the commits.\n* A list of \"large edges\" to enable octopus merges.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n 1 file changed, 88 insertions(+)\n create mode 100644 Documentation/technical/graph-format.txt\n\ndiff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\nnew file mode 100644\nindex 0000000000..a15e1036d7\n--- /dev/null\n+++ b/Documentation/technical/graph-format.txt\n@@ -0,0 +1,88 @@\n+Git commit graph format\n+=======================\n+\n+The Git commit graph stores a list of commit OIDs and some associated\n+metadata, including:\n+\n+- The generation number of the commit. Commits with no parents have\n+ generation number 1; commits with parents have generation number\n+ one more than the maximum generation number of its parents. We\n+ reserve zero as special, and can be used to mark a generation\n+ number invalid or as \"not computed\".\n+\n+- The root tree OID.\n+\n+- The commit date.\n+\n+- The parents of the commit, stored using positional references within\n+ the graph file.\n+\n+== graph-*.graph files have the following format:\n+\n+In order to allow extensions that add extra data to the graph, we organize\n+the body into \"chunks\" and provide a binary lookup table at the beginning\n+of the body. The header includes certain values, such as number of chunks,\n+hash lengths and types.\n+\n+All 4-byte numbers are in network order.\n+\n+HEADER:\n+\n+\t4-byte signature:\n+\t The signature is: {'C', 'G', 'P', 'H'}\n+\n+\t1-byte version number:\n+\t Currently, the only valid version is 1.\n+\n+\t1-byte Object Id Version (1 = SHA-1)\n+\n+\t1-byte Object Id Length (H)\n+\n+\t1-byte number (C) of \"chunks\"\n+\n+CHUNK LOOKUP:\n+\n+\t(C + 1) * 12 bytes listing the table of contents for the chunks:\n+\t First 4 bytes describe chunk id. Value 0 is a terminating label.\n+\t Other 8 bytes provide offset in current file for chunk to start.\n+\t (Chunks are ordered contiguously in the file, so you can infer\n+\t\tthe length using the next chunk position if necessary.)\n+\n+\tThe remaining data in the body is described one chunk at a time, and\n+\tthese chunks may be given in any order. Chunks are required unless\n+\totherwise specified.\n+\n+CHUNK DATA:\n+\n+\tOID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)\n+\t The ith entry, F[i], stores the number of OIDs with first\n+\t byte at most i. Thus F[255] stores the total\n+\t number of commits (N).\n+\n+\tOID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)\n+\t The OIDs for all commits in the graph.\n+\n+\tCommit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)\n+\t * The first H bytes are for the OID of the root tree.\n+\t * The next 8 bytes are for the int-ids of the first two parents of\n+\t the ith commit. Stores value 0xffffffff if no parent in that position.\n+\t If there are more than two parents, the second value has its most-\n+\t significant bit on and the other bits store an offset into the Large\n+\t Edge List chunk.\n+\t * The next 8 bytes store the generation number of the commit and the\n+\t commit time in seconds since EPOCH. The generation number uses the\n+\t higher 30 bits of the first 4 bytes, while the commit time uses the\n+\t 32 bits of the second 4 bytes, along with the lowest 2 bits of the\n+\t lowest byte, storing the 33rd and 34th bit of the commit time.\n+\n+\t[Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})\n+\t This list of 4-byte values store the second through nth parents for\n+\t all octoput merges. The second parent value in the commit data is a\n+\t negative number pointing into this list. Then iterate through this\n+\t list starting at that position until reaching a value with the most-\n+\t significant bit on. The other bits correspond to the int-id of the\n+\t last parent.\n+\n+TRAILER:\n+\n+\tH-byte HASH-checksum of all of the above.\n-- \n2.16.0\n\n"},{"id":"337371","messageId":"20180125140231.65604-10-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 09/14] packed-graph: implement git-graph --clear","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:26Z","receivedAt":"2018-01-25T14:03:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach Git to delete the current 'graph_head' file and the packed graph\nit references. This is a good safety valve if somehow the file is\ncorrupted and needs to be recalculated. Since the packed graph is a\nsummary of contents already in the ODB, it can be regenerated.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 16 ++++++++++++++--\n builtin/graph.c | 31 ++++++++++++++++++++++++++++++-\n t/t5319-graph.sh | 7 ++++++-\n 3 files changed, 50 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex ac20aa67a9..f690699570 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -11,6 +11,7 @@ SYNOPSIS\n [verse]\n 'git graph' --write [--pack-dir ]\n 'git graph' --read [--pack-dir ]\n+'git graph' --clear [--pack-dir ]\n \n OPTIONS\n -------\n@@ -18,16 +19,21 @@ OPTIONS\n \tUse given directory for the location of packfiles, graph-head,\n \tand graph files.\n \n+--clear::\n+\tDelete the graph-head file and the graph file it references.\n+\t(Cannot be combined with --read or --write.)\n+\n --read::\n \tRead a graph file given by the graph-head file and output basic\n-\tdetails about the graph file. (Cannot be combined with --write.)\n+\tdetails about the graph file. (Cannot be combined with --clear\n+\tor --write.)\n \n --graph-id::\n \tWhen used with --read, consider the graph file graph-.graph.\n \n --write::\n \tWrite a new graph file to the pack directory. (Cannot be combined\n-\twith --read.)\n+\twith --clear or --read.)\n \n --update-head::\n \tWhen used with --write, update the graph-head file to point to\n@@ -61,6 +67,12 @@ $ git graph --write --update-head\n $ git graph --read --graph-id=\n ------------------------------------------------\n \n+* Delete /graph-head and the file it references.\n++\n+------------------------------------------------\n+$ git graph --clear --pack-dir=\n+------------------------------------------------\n+\n CONFIGURATION\n -------------\n \ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex 0760d99f43..ac15febc46 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -10,6 +10,7 @@\n \n static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n+\tN_(\"git graph --clear [--pack-dir ]\"),\n \tN_(\"git graph --read [--graph-id=]\"),\n \tN_(\"git graph --write [--pack-dir ] [--update-head]\"),\n \tNULL\n@@ -17,6 +18,7 @@ static char const * const builtin_graph_usage[] ={\n \n static struct opts_graph {\n \tconst char *pack_dir;\n+\tint clear;\n \tint read;\n \tconst char *graph_id;\n \tint write;\n@@ -25,6 +27,29 @@ static struct opts_graph {\n \tstruct object_id old_graph_oid;\n } opts;\n \n+static int graph_clear(void)\n+{\n+\tstruct strbuf head_path = STRBUF_INIT;\n+\tchar *old_path;\n+\n+\tif (!opts.has_existing)\n+\t\treturn 0;\n+\n+\tstrbuf_addstr(&head_path, opts.pack_dir);\n+\tstrbuf_addstr(&head_path, \"/\");\n+\tstrbuf_addstr(&head_path, \"graph-head\");\n+\tif (remove_path(head_path.buf))\n+\t\tdie(\"failed to remove path %s\", head_path.buf);\n+\tstrbuf_release(&head_path);\n+\n+\told_path = get_graph_filename_oid(opts.pack_dir, &opts.old_graph_oid);\n+\tif (remove_path(old_path))\n+\t\tdie(\"failed to remove path %s\", old_path);\n+\tfree(old_path);\n+\n+\treturn 0;\n+}\n+\n static int graph_read(void)\n {\n \tstruct object_id graph_oid;\n@@ -105,6 +130,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n \t\t\tN_(\"dir\"),\n \t\t\tN_(\"The pack directory to store the graph\") },\n+\t\tOPT_BOOL('c', \"clear\", &opts.clear,\n+\t\t\tN_(\"clear graph file and graph-head\")),\n \t\tOPT_BOOL('r', \"read\", &opts.read,\n \t\t\tN_(\"read graph file\")),\n \t\tOPT_BOOL('w', \"write\", &opts.write,\n@@ -129,7 +156,7 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\t builtin_graph_options,\n \t\t\t builtin_graph_usage, 0);\n \n-\tif (opts.write + opts.read > 1)\n+\tif (opts.write + opts.read + opts.clear > 1)\n \t\tusage_with_options(builtin_graph_usage, builtin_graph_options);\n \n \tif (!opts.pack_dir) {\n@@ -141,6 +168,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \n \topts.has_existing = !!get_graph_head_oid(opts.pack_dir, &opts.old_graph_oid);\n \n+\tif (opts.clear)\n+\t\treturn graph_clear();\n \tif (opts.read)\n \t\treturn graph_read();\n \tif (opts.write)\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 3919a3ad73..311fb9dd67 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -80,6 +80,11 @@ test_expect_success 'write graph with merges' \\\n _graph_read_expect \"18\" \"${packdir}\" &&\n cmp expect output'\n \n+test_expect_success 'clear graph' \\\n+ 'git graph --clear &&\n+ test_path_is_missing ${packdir}/graph-${graph2}.graph &&\n+ test_path_is_missing ${packdir}/graph-head'\n+\n test_expect_success 'setup bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n@@ -89,7 +94,7 @@ test_expect_success 'setup bare repo' \\\n baredir=\"./objects/pack\"'\n \n test_expect_success 'write graph in bare repo' \\\n- 'graphbare=$(git graph --write) &&\n+ 'graphbare=$(git graph --write --update-head) &&\n test_path_is_file ${baredir}/graph-${graphbare}.graph &&\n test_path_is_file ${baredir}/graph-head &&\n echo ${graphbare} >expect &&\n-- \n2.16.0\n\n"},{"id":"337372","messageId":"20180125140231.65604-6-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:22Z","receivedAt":"2018-01-25T14:03:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach Git to write a packed graph file by checking all packed objects\nto see if they are commits, then store the file in the given pack\ndirectory.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n packed-graph.c | 375 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n packed-graph.h | 20 +++\n 3 files changed, 396 insertions(+)\n create mode 100644 packed-graph.c\n create mode 100644 packed-graph.h\n\ndiff --git a/Makefile b/Makefile\nindex d8b0d0457a..59439e13a1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -841,6 +841,7 @@ LIB_OBJS += notes-utils.o\n LIB_OBJS += object.o\n LIB_OBJS += oidmap.o\n LIB_OBJS += oidset.o\n+LIB_OBJS += packed-graph.o\n LIB_OBJS += packfile.o\n LIB_OBJS += pack-bitmap.o\n LIB_OBJS += pack-bitmap-write.o\ndiff --git a/packed-graph.c b/packed-graph.c\nnew file mode 100644\nindex 0000000000..9be9811667\n--- /dev/null\n+++ b/packed-graph.c\n@@ -0,0 +1,375 @@\n+#include \"cache.h\"\n+#include \"config.h\"\n+#include \"git-compat-util.h\"\n+#include \"pack.h\"\n+#include \"packfile.h\"\n+#include \"commit.h\"\n+#include \"object.h\"\n+#include \"packed-graph.h\"\n+\n+#define GRAPH_SIGNATURE 0x43475048 /* \"CGPH\" */\n+#define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* \"OIDF\" */\n+#define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* \"OIDL\" */\n+#define GRAPH_CHUNKID_DATA 0x43444154 /* \"CDAT\" */\n+#define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* \"EDGE\" */\n+\n+#define GRAPH_DATA_WIDTH 36\n+\n+#define GRAPH_VERSION_1 0x1\n+#define GRAPH_VERSION GRAPH_VERSION_1\n+\n+#define GRAPH_OID_VERSION_SHA1 1\n+#define GRAPH_OID_LEN_SHA1 20\n+#define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1\n+#define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1\n+\n+#define GRAPH_LARGE_EDGES_NEEDED 0x80000000\n+#define GRAPH_PARENT_MISSING 0x7fffffff\n+#define GRAPH_EDGE_LAST_MASK 0x7fffffff\n+#define GRAPH_PARENT_NONE 0x70000000\n+\n+#define GRAPH_LAST_EDGE 0x80000000\n+\n+char* get_graph_filename_oid(const char *pack_dir,\n+\t\t\t\t struct object_id *oid)\n+{\n+\tsize_t len;\n+\tstruct strbuf head_path = STRBUF_INIT;\n+\tstrbuf_addstr(&head_path, pack_dir);\n+\tstrbuf_addstr(&head_path, \"/graph-\");\n+\tstrbuf_addstr(&head_path, oid_to_hex(oid));\n+\tstrbuf_addstr(&head_path, \".graph\");\n+\n+\treturn strbuf_detach(&head_path, &len);\n+}\n+\n+static void write_graph_chunk_fanout(\n+\tstruct sha1file *f,\n+\tstruct commit **commits, int nr_commits)\n+{\n+\tuint32_t i, count = 0;\n+\tstruct commit **list = commits;\n+\tstruct commit **last = commits + nr_commits;\n+\n+\t/*\n+\t* Write the first-level table (the list is sorted,\n+\t* but we use a 256-entry lookup to be able to avoid\n+\t* having to do eight extra binary search iterations).\n+\t*/\n+\tfor (i = 0; i < 256; i++) {\n+\t\tuint32_t swap_count;\n+\n+\t\twhile (list < last) {\n+\t\t\tif ((*list)->object.oid.hash[0] != i)\n+\t\t\t\tbreak;\n+\t\t\tcount++;\n+\t\t\tlist++;\n+\t\t}\n+\n+\t\tswap_count = htonl(count);\n+\t\tsha1write(f, &swap_count, 4);\n+\t}\n+}\n+\n+static void write_graph_chunk_oids(\n+\tstruct sha1file *f, int hash_len,\n+\tstruct commit **commits, int nr_commits)\n+{\n+\tstruct commit **list = commits;\n+\tuint32_t i;\n+\tfor (i = 0; i < nr_commits; i++) {\n+\t\tsha1write(f, (*list)->object.oid.hash, (int)hash_len);\n+\t\tlist++;\n+\t}\n+}\n+\n+static int commit_pos(struct commit **commits, int nr_commits, const struct object_id *oid, uint32_t *pos)\n+{\n+\tuint32_t first = 0, last = nr_commits;\n+\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tstruct object_id *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = &(commits[mid]->object.oid);\n+\t\tcmp = oidcmp(oid, current);\n+\t\tif (!cmp) {\n+\t\t\t*pos = mid;\n+\t\t\treturn 1;\n+\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\t*pos = first;\n+\treturn 0;\n+}\n+\n+static void write_graph_chunk_data(\n+\tstruct sha1file *f, int hash_len,\n+\tstruct commit **commits, int nr_commits)\n+{\n+\tstruct commit **list = commits;\n+\tstruct commit **last = commits + nr_commits;\n+\tuint32_t num_large_edges = 0;\n+\n+\twhile (list < last) {\n+\t\tstruct commit_list *parent;\n+\t\tuint32_t intId, swapIntId;\n+\t\tuint32_t packedDate[2];\n+\n+\t\tparse_commit(*list);\n+\t\tsha1write(f, (*list)->tree->object.oid.hash, hash_len);\n+\n+\t\tparent = (*list)->parents;\n+\n+\t\tif (!parent)\n+\t\t\tswapIntId = htonl(GRAPH_PARENT_NONE);\n+\t\telse if (commit_pos(commits, nr_commits, &(parent->item->object.oid), &intId))\n+\t\t\tswapIntId = htonl(intId);\n+\t\telse\n+\t\t\tswapIntId = htonl(GRAPH_PARENT_MISSING);\n+\n+\t\tsha1write(f, &swapIntId, 4);\n+\n+\t\tif (parent)\n+\t\t\tparent = parent->next;\n+\n+\t\tif (!parent)\n+\t\t\tswapIntId = htonl(GRAPH_PARENT_NONE);\n+\t\telse if (parent->next)\n+\t\t\tswapIntId = htonl(GRAPH_LARGE_EDGES_NEEDED | num_large_edges);\n+\t\telse if (commit_pos(commits, nr_commits, &(parent->item->object.oid), &intId))\n+\t\t\tswapIntId = htonl(intId);\n+\t\telse\n+\t\t\tswapIntId = htonl(GRAPH_PARENT_MISSING);\n+\n+\t\tsha1write(f, &swapIntId, 4);\n+\n+\t\tif (parent && parent->next) {\n+\t\t\tdo {\n+\t\t\t\tnum_large_edges++;\n+\t\t\t\tparent = parent->next;\n+\t\t\t} while (parent);\n+\t\t}\n+\n+\t\tpackedDate[0] = htonl((*list)->date >> 32);\n+\t\tpackedDate[1] = htonl((*list)->date);\n+\t\tsha1write(f, packedDate, 8);\n+\n+\t\tlist++;\n+\t}\n+}\n+\n+static void write_graph_chunk_large_edges(\n+\tstruct sha1file *f,\n+\tstruct commit **commits, int nr_commits)\n+{\n+\tstruct commit **list = commits;\n+\tstruct commit **last = commits + nr_commits;\n+\tstruct commit_list *parent;\n+\n+\twhile (list < last) {\n+\t\tint num_parents = 0;\n+\t\tfor (parent = (*list)->parents; num_parents < 3 && parent; parent = parent->next)\n+\t\t\tnum_parents++;\n+\n+\t\tif (num_parents <= 2) {\n+\t\t\tlist++;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tfor (parent = (*list)->parents; parent; parent = parent->next)\n+\t\t{\n+\t\t\tif (parent != (*list)->parents)\n+\t\t\t{\n+\t\t\t\tuint32_t intId, swapIntId;\n+\t\t\t\tuint32_t lastEdge = 0;\n+\n+\t\t\t\tif (!parent->next)\n+\t\t\t\t\tlastEdge |= GRAPH_LAST_EDGE;\n+\n+\t\t\t\tif (commit_pos(commits, nr_commits, &(parent->item->object.oid), &intId))\n+\t\t\t\t\tswapIntId = htonl(intId | lastEdge);\n+\t\t\t\telse\n+\t\t\t\t\tswapIntId = htonl(GRAPH_PARENT_MISSING | lastEdge);\n+\n+\t\t\t\tsha1write(f, &swapIntId, 4);\n+\t\t\t}\n+\t\t}\n+\n+\t\tlist++;\n+\t}\n+}\n+\n+static int commit_compare(const void *_a, const void *_b)\n+{\n+\tstruct object_id *a = *(struct object_id **)_a;\n+\tstruct object_id *b = *(struct object_id **)_b;\n+\treturn oidcmp(a, b);\n+}\n+\n+struct packed_commit_list {\n+\tstruct commit **list;\n+\tint num;\n+\tint size;\n+};\n+\n+struct packed_oid_list {\n+\tstruct object_id **list;\n+\tint num;\n+\tint size;\n+};\n+\n+static int if_packed_commit_add_to_list(const struct object_id *oid,\n+\t\t\t\t\tstruct packed_git *pack,\n+\t\t\t\t\tuint32_t pos,\n+\t\t\t\t\tvoid *data)\n+{\n+\tstruct packed_oid_list *list = (struct packed_oid_list*)data;\n+\tenum object_type type;\n+\tunsigned long size;\n+\tvoid *inner_data;\n+\toff_t offset = nth_packed_object_offset(pack, pos);\n+\tinner_data = unpack_entry(pack, offset, &type, &size);\n+\n+\tif (inner_data)\n+\t\tfree(inner_data);\n+\n+\tif (type != OBJ_COMMIT)\n+\t\treturn 0;\n+\n+\tALLOC_GROW(list->list, list->num + 1, list->size);\n+\tlist->list[list->num] = (struct object_id *)malloc(sizeof(struct object_id));\n+\toidcpy(list->list[list->num], oid);\n+\t(list->num)++;\n+\n+\treturn 0;\n+}\n+\n+struct object_id *construct_graph(const char *pack_dir)\n+{\n+\t// Find a list of oids, adding the pointer to a list.\n+\tstruct packed_oid_list oids;\n+\tstruct packed_commit_list commits;\n+\tstruct packed_graph_header hdr;\n+\tstruct sha1file *f;\n+\tint i, count_distinct = 0;\n+\tstruct strbuf tmp_file = STRBUF_INIT;\n+\tunsigned char final_hash[GIT_MAX_RAWSZ];\n+\tchar *graph_name;\n+\tint fd;\n+\tuint32_t chunk_ids[5];\n+\tuint64_t chunk_offsets[5];\n+\tint num_long_edges;\n+\tstruct object_id *f_oid;\n+\tchar *fname;\n+\tstruct commit_list *parent;\n+\n+\tif (!core_graph)\n+\t\treturn 0;\n+\n+\toids.num = 0;\n+\toids.size = 1024;\n+\tALLOC_ARRAY(oids.list, oids.size);\n+\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n+\tQSORT(oids.list, oids.num, commit_compare);\n+\n+\tcount_distinct = 1;\n+\tfor (i = 1; i < oids.num; i++)\n+\t{\n+\t\tif (oidcmp(oids.list[i-1], oids.list[i]))\n+\t\t\tcount_distinct++;\n+\t}\n+\n+\tcommits.num = 0;\n+\tcommits.size = count_distinct;\n+\tALLOC_ARRAY(commits.list, commits.size);\n+\n+\tnum_long_edges = 0;\n+\tfor (i = 0; i < oids.num; i++)\n+\t{\n+\t\tint num_parents = 0;\n+\t\tif (i > 0 && !oidcmp(oids.list[i-1], oids.list[i]))\n+\t\t\tcontinue;\n+\n+\t\tcommits.list[commits.num] = lookup_commit(oids.list[i]);\n+\t\tparse_commit(commits.list[commits.num]);\n+\n+\t\tfor (parent = commits.list[commits.num]->parents; parent; parent = parent->next) {\n+\t\t\tnum_parents++;\n+\t\t}\n+\n+\t\tif (num_parents > 2)\n+\t\t\tnum_long_edges += num_parents - 1;\n+\n+\t\tcommits.num++;\n+\t}\n+\n+\t// Create header (including chunk lengths?!?)\n+\tstrbuf_addstr(&tmp_file, pack_dir);\n+\tstrbuf_addstr(&tmp_file, \"/tmp_graph_XXXXXX\");\n+\n+\tfd = git_mkstemp_mode(tmp_file.buf, 0444);\n+\tif (fd < 0)\n+\t\tdie_errno(\"unable to create '%s'\", tmp_file.buf);\n+\n+\tgraph_name = strbuf_detach(&tmp_file, NULL);\n+\tf = sha1fd(fd, graph_name);\n+\n+\t/* fill header info */\n+\thdr.graph_signature = htonl(GRAPH_SIGNATURE);\n+\thdr.graph_version = GRAPH_VERSION;\n+\thdr.hash_version = GRAPH_OID_VERSION;\n+\thdr.hash_len = GRAPH_OID_LEN;\n+\thdr.num_chunks = 4;\n+\n+\t/* write header to file */\n+\tassert(sizeof(hdr) == 8);\n+\tsha1write(f, &hdr, sizeof(hdr));\n+\n+\tchunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;\n+\tchunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;\n+\tchunk_ids[2] = GRAPH_CHUNKID_DATA;\n+\tchunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;\n+\tchunk_ids[4] = 0;\n+\n+\tchunk_offsets[0] = sizeof(hdr) + 12 * 5; // Skip header and chunk list\n+\tchunk_offsets[1] = chunk_offsets[0] + 256 * 4; // fanout table size\n+\tchunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.num; // lookup size\n+\tchunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.num; // data size\n+\tchunk_offsets[4] = chunk_offsets[3] + 4 * num_long_edges;\n+\n+\tfor (i = 0; i <= hdr.num_chunks; i++) {\n+\t\tuint32_t chunk_write[3];\n+\n+\t\tchunk_write[0] = htonl(chunk_ids[i]);\n+\t\tchunk_write[1] = htonl(chunk_offsets[i] >> 32);\n+\t\tchunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);\n+\t\tsha1write(f, chunk_write, 12);\n+\t}\n+\n+\twrite_graph_chunk_fanout(f, commits.list, commits.num);\n+\twrite_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.num);\n+\twrite_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.num);\n+\twrite_graph_chunk_large_edges(f, commits.list, commits.num);\n+\n+\tsha1close(f, final_hash, CSUM_CLOSE | CSUM_FSYNC);\n+\n+\tf_oid = (struct object_id *)malloc(sizeof(struct object_id));\n+\tmemcpy(f_oid->hash, final_hash, GIT_MAX_RAWSZ);\n+\tfname = get_graph_filename_oid(pack_dir, f_oid);\n+\n+\tif (rename(graph_name, fname))\n+\t\tdie(\"failed to rename %s to %s\", graph_name, fname);\n+\n+\tfree(oids.list);\n+\toids.size = 0;\n+\toids.num = 0;\n+\n+\treturn f_oid;\n+}\ndiff --git a/packed-graph.h b/packed-graph.h\nnew file mode 100644\nindex 0000000000..d4e10fb612\n--- /dev/null\n+++ b/packed-graph.h\n@@ -0,0 +1,20 @@\n+#ifndef PACKED_GRAPH_H\n+#define PACKED_GRAPH_H\n+\n+#include \"git-compat-util.h\"\n+#include \"commit.h\"\n+\n+extern char* get_graph_filename_oid(const char *pack_dir,\n+\t\t\t\t struct object_id *oid);\n+\n+struct packed_graph_header {\n+\tuint32_t graph_signature;\n+\tunsigned char graph_version;\n+\tunsigned char hash_version;\n+\tunsigned char hash_len;\n+\tunsigned char num_chunks;\n+};\n+\n+extern struct object_id *construct_graph(const char *pack_dir);\n+\n+#endif\n-- \n2.16.0\n\n"},{"id":"337373","messageId":"20180125140231.65604-7-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 06/14] packed-graph: implement git-graph --write","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:23Z","receivedAt":"2018-01-25T14:03:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach git-graph to write graph files. Create new test script to verify\nthis command succeeds without failure.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 26 ++++++++++++++\n builtin/graph.c | 37 ++++++++++++++++++--\n t/t5319-graph.sh | 83 +++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 143 insertions(+), 3 deletions(-)\n create mode 100755 t/t5319-graph.sh\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex de5a3c07e6..be6bc38814 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -5,3 +5,29 @@ NAME\n ----\n git-graph - Write and verify Git commit graphs (.graph files)\n \n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git graph' --write [--pack-dir ]\n+\n+EXAMPLES\n+--------\n+\n+* Write a graph file for the packed commits in your local .git folder.\n++\n+------------------------------------------------\n+$ git midx --write\n+------------------------------------------------\n+\n+CONFIGURATION\n+-------------\n+\n+core.graph::\n+\tThe graph command will fail if core.graph is false.\n+\tAlso, the written graph files will be ignored by other commands\n+\tunless core.graph is true.\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\n\\ No newline at end of file\ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex a902dc8646..09f5552338 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -6,31 +6,62 @@\n #include \"lockfile.h\"\n #include \"packfile.h\"\n #include \"parse-options.h\"\n+#include \"packed-graph.h\"\n \n static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n+\tN_(\"git graph --write [--pack-dir ]\"),\n \tNULL\n };\n \n static struct opts_graph {\n \tconst char *pack_dir;\n+\tint write;\n } opts;\n \n+static int graph_write(void)\n+{\n+\tstruct object_id *graph_id = construct_graph(opts.pack_dir);\n+\n+\tif (graph_id)\n+\t\tprintf(\"%s\\n\", oid_to_hex(graph_id));\n+\n+\tfree(graph_id);\n+\treturn 0;\n+}\n+\n int cmd_graph(int argc, const char **argv, const char *prefix)\n {\n \tstatic struct option builtin_graph_options[] = {\n \t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n \t\t\tN_(\"dir\"),\n \t\t\tN_(\"The pack directory to store the graph\") },\n+\t\tOPT_BOOL('w', \"write\", &opts.write,\n+\t\t\tN_(\"write graph file\")),\n \t\tOPT_END(),\n \t};\n \n-\tif (!core_graph)\n-\t\tdie(\"core.graph is false\");\n-\n \tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n \t\tusage_with_options(builtin_graph_usage, builtin_graph_options);\n \n+\tgit_config(git_default_config, NULL);\n+\tif (!core_graph)\n+\t\tdie(\"git-graph requires core.graph=true.\");\n+\n+\targc = parse_options(argc, argv, prefix,\n+\t\t\t builtin_graph_options,\n+\t\t\t builtin_graph_usage, 0);\n+\n+\tif (!opts.pack_dir) {\n+\t\tstruct strbuf path = STRBUF_INIT;\n+\t\tstrbuf_addstr(&path, get_object_directory());\n+\t\tstrbuf_addstr(&path, \"/pack\");\n+\t\topts.pack_dir = strbuf_detach(&path, NULL);\n+\t}\n+\n+\tif (opts.write)\n+\t\treturn graph_write();\n+\n \treturn 0;\n }\n \ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nnew file mode 100755\nindex 0000000000..52e979dfd3\n--- /dev/null\n+++ b/t/t5319-graph.sh\n@@ -0,0 +1,83 @@\n+#!/bin/sh\n+\n+test_description='packed graph'\n+. ./test-lib.sh\n+\n+test_expect_success \\\n+ 'setup full repo' \\\n+ 'rm -rf .git &&\n+ mkdir full &&\n+ cd full &&\n+ git init &&\n+ git config core.graph true &&\n+ git config pack.threads 1 &&\n+ packdir=\".git/objects/pack\"'\n+\n+test_expect_success \\\n+ 'write graph with no packs' \\\n+ 'git graph --write --pack-dir .'\n+\n+test_expect_success \\\n+ 'create commits and repack' \\\n+ 'for i in $(test_seq 5)\n+ do\n+ echo $i >$i.txt &&\n+ git add $i.txt &&\n+ git commit -m \"commit $i\" &&\n+ git branch commits/$i\n+ done &&\n+ git repack'\n+\n+test_expect_success \\\n+ 'write graph' \\\n+ 'graph1=$(git graph --write) &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph'\n+\n+test_expect_success \\\n+ 'Add more commits' \\\n+ 'git reset --hard commits/3 &&\n+ for i in $(test_seq 6 10)\n+ do\n+ echo $i >$i.txt &&\n+ git add $i.txt &&\n+ git commit -m \"commit $i\" &&\n+ git branch commits/$i\n+ done &&\n+ git reset --hard commits/7 &&\n+ for i in $(test_seq 11 15)\n+ do\n+ echo $i >$i.txt &&\n+ git add $i.txt &&\n+ git commit -m \"commit $i\" &&\n+ git branch commits/$i\n+ done &&\n+ git reset --hard commits/7 &&\n+ git merge commits/4 &&\n+ git branch merge/1 &&\n+ git reset --hard commits/8 &&\n+ git merge commits/11 &&\n+ git branch merge/2 &&\n+ git reset --hard commits/9 &&\n+ git merge commits/5 commits/13 &&\n+ git repack'\n+\n+test_expect_success \\\n+ 'write graph with merges' \\\n+ 'graph2=$(git graph --write) &&\n+ test_path_is_file ${packdir}/graph-${graph2}.graph'\n+\n+test_expect_success \\\n+ 'setup bare repo' \\\n+ 'cd .. &&\n+ git clone --bare full bare &&\n+ cd bare &&\n+ git config core.graph true &&\n+ git config pack.threads 1 &&\n+ baredir=\"objects/pack\"'\n+\n+test_expect_success \\\n+ 'write graph in bare repo' \\\n+ 'graphbare=$(git graph --write) &&\n+ test_path_is_file ${baredir}/graph-${graphbare}.graph'\n+\n+test_done\n-- \n2.16.0\n\n"},{"id":"337374","messageId":"20180125140231.65604-15-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 14/14] packed-graph: teach git-graph to read commits","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:31Z","receivedAt":"2018-01-25T14:03:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach git-graph to read commits from stdin when the --stdin-commits\nflag is specified. Commits reachable from these commits are added to\nthe graph. This is a much faster way to construct the graph than\ninspecting all packed objects, but is restricted to known tips.\n\nFor the Linux repository, 700,000+ commits were added to the graph\nfile starting from 'master' in 7-9 seconds, depending on the number\nof packfiles in the repo (1, 24, or 120).\n\nSigned-off-by: Derrick Stolee \n---\n builtin/graph.c | 33 +++++++++++++++++++++++++--------\n packed-graph.c | 18 +++++++++++++++---\n packed-graph.h | 3 ++-\n t/t5319-graph.sh | 18 ++++++++++++++++++\n 4 files changed, 60 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex 3cace3a18c..708889677b 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -12,7 +12,7 @@ static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n \tN_(\"git graph --clear [--pack-dir ]\"),\n \tN_(\"git graph --read [--graph-id=]\"),\n-\tN_(\"git graph --write [--pack-dir ] [--update-head] [--delete-expired] [--stdin-packs]\"),\n+\tN_(\"git graph --write [--pack-dir ] [--update-head] [--delete-expired] [--stdin-packs|--stdin-commits]\"),\n \tNULL\n };\n \n@@ -25,6 +25,7 @@ static struct opts_graph {\n \tint update_head;\n \tint delete_expired;\n \tint stdin_packs;\n+\tint stdin_commits;\n \tint has_existing;\n \tstruct object_id old_graph_oid;\n } opts;\n@@ -116,22 +117,36 @@ static int graph_write(void)\n {\n \tstruct object_id *graph_id;\n \tchar **pack_indexes = NULL;\n+\tchar **commits = NULL;\n \tint num_packs = 0;\n-\tint size_packs = 0;\n+\tint num_commits = 0;\n+\tchar **lines = NULL;\n+\tint num_lines = 0;\n+\tint size_lines = 0;\n \n-\tif (opts.stdin_packs) {\n+\tif (opts.stdin_packs || opts.stdin_commits) {\n \t\tstruct strbuf buf = STRBUF_INIT;\n-\t\tsize_packs = 128;\n-\t\tALLOC_ARRAY(pack_indexes, size_packs);\n+\t\tsize_lines = 128;\n+\t\tALLOC_ARRAY(lines, size_lines);\n \n \t\twhile (strbuf_getline(&buf, stdin) != EOF) {\n-\t\t\tALLOC_GROW(pack_indexes, num_packs + 1, size_packs);\n-\t\t\tpack_indexes[num_packs++] = buf.buf;\n+\t\t\tALLOC_GROW(lines, num_lines + 1, size_lines);\n+\t\t\tlines[num_lines++] = buf.buf;\n \t\t\tstrbuf_detach(&buf, NULL);\n \t\t}\n+\n+\t\tif (opts.stdin_packs) {\n+\t\t\tpack_indexes = lines;\n+\t\t\tnum_packs = num_lines;\n+\t\t}\n+\t\tif (opts.stdin_commits) {\n+\t\t\tcommits = lines;\n+\t\t\tnum_commits = num_lines;\n+\t\t}\n \t}\n \n-\tgraph_id = construct_graph(opts.pack_dir, pack_indexes, num_packs);\n+\tgraph_id = construct_graph(opts.pack_dir, pack_indexes, num_packs,\n+\t\t\t\t commits, num_commits);\n \n \tif (opts.update_head)\n \t\tupdate_head_file(opts.pack_dir, graph_id);\n@@ -170,6 +185,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"delete expired head graph file\")),\n \t\tOPT_BOOL('s', \"stdin-packs\", &opts.stdin_packs,\n \t\t\tN_(\"only scan packfiles listed by stdin\")),\n+\t\tOPT_BOOL('C', \"stdin-commits\", &opts.stdin_commits,\n+\t\t\tN_(\"start walk at commits listed by stdin\")),\n \t\t{ OPTION_STRING, 'G', \"graph-id\", &opts.graph_id,\n \t\t\tN_(\"oid\"),\n \t\t\tN_(\"An OID for a specific graph file in the pack-dir.\"),\ndiff --git a/packed-graph.c b/packed-graph.c\nindex c93515f18e..94e1a97000 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -662,7 +662,8 @@ static void close_reachable(struct packed_oid_list *oids)\n \t}\n }\n \n-struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs)\n+struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs,\n+\t\t\t\t char **commit_hex, int nr_commits)\n {\n \t// Find a list of oids, adding the pointer to a list.\n \tstruct packed_oid_list oids;\n@@ -719,10 +720,21 @@ struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int\n \t\t\tfor_each_object_in_pack(p, if_packed_commit_add_to_list, &oids);\n \t\t\tclose_pack(p);\n \t\t}\n-\t} else {\n-\t\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n \t}\n \n+\tif (commit_hex) {\n+\t\tfor (i = 0; i < nr_commits; i++) {\n+\t\t\tconst char *end;\n+\t\t\tALLOC_GROW(oids.list, oids.num + 1, oids.size);\n+\t\t\toids.list[oids.num] = malloc(sizeof(struct object_id));\n+\t\t\tparse_oid_hex(commit_hex[i], oids.list[oids.num], &end);\n+\t\t\toids.num++;\n+\t\t}\n+\t}\n+\n+\tif (!pack_indexes && !commit_hex)\n+\t\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n+\n \tclose_reachable(&oids);\n \tQSORT(oids.list, oids.num, commit_compare);\n \ndiff --git a/packed-graph.h b/packed-graph.h\nindex 97ce1e2652..9c766411be 100644\n--- a/packed-graph.h\n+++ b/packed-graph.h\n@@ -58,7 +58,8 @@ extern struct object_id *get_nth_commit_oid(struct packed_graph *g,\n \t\t\t\t\t uint32_t n,\n \t\t\t\t\t struct object_id *oid);\n \n-extern struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs);\n+extern struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs,\n+\t\t\t\t\t char **commits, int nr_commits);\n extern int close_graph(struct packed_graph *g);\n \n #endif\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 8bf5a0c993..b12d2477ba 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -226,6 +226,24 @@ test_expect_success 'build graph from latest pack with closure' \\\n _graph_git_behavior commits/20 merge/1\n _graph_git_behavior commits/20 merge/2\n \n+test_expect_success 'build graph from commits with closure' \\\n+ 'git rev-parse commits/20 >commits-in &&\n+ git rev-parse merge/1 >>commits-in &&\n+ git rev-parse merge/2 >>commits-in &&\n+ graph6=$(cat commits-in | git graph --write --update-head --delete-expired --stdin-commits) &&\n+ test_path_is_file ${packdir}/graph-${graph6}.graph &&\n+ test_path_is_missing ${packdir}/graph-${graph5}.graph &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ test_path_is_file ${packdir}/graph-head &&\n+ echo ${graph6} >expect &&\n+ cmp -n 40 expect ${packdir}/graph-head &&\n+ git graph --read --graph-id=${graph6} >output &&\n+ _graph_read_expect \"23\" \"${packdir}\" &&\n+ cmp expect output'\n+\n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'setup bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n-- \n2.16.0\n\n"},{"id":"337375","messageId":"20180125140231.65604-9-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 08/14] graph: implement git-graph --update-head","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:25Z","receivedAt":"2018-01-25T14:03:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"It is possible to have multiple packed graph files in a pack directory,\nbut only one is important at a time. Use a 'graph_head' file to point\nto the important file. Teach git-graph to write 'graph_head' upon\nwriting a new packed graph file.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 38 ++++++++++++++++++++++++++++++++++++--\n builtin/graph.c | 38 +++++++++++++++++++++++++++++++++++---\n packed-graph.c | 25 +++++++++++++++++++++++++\n packed-graph.h | 1 +\n t/t5319-graph.sh | 12 ++++++++++--\n 5 files changed, 107 insertions(+), 7 deletions(-)\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex 0939c3f1be..ac20aa67a9 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -12,19 +12,53 @@ SYNOPSIS\n 'git graph' --write [--pack-dir ]\n 'git graph' --read [--pack-dir ]\n \n+OPTIONS\n+-------\n+--pack-dir::\n+\tUse given directory for the location of packfiles, graph-head,\n+\tand graph files.\n+\n+--read::\n+\tRead a graph file given by the graph-head file and output basic\n+\tdetails about the graph file. (Cannot be combined with --write.)\n+\n+--graph-id::\n+\tWhen used with --read, consider the graph file graph-.graph.\n+\n+--write::\n+\tWrite a new graph file to the pack directory. (Cannot be combined\n+\twith --read.)\n+\n+--update-head::\n+\tWhen used with --write, update the graph-head file to point to\n+\tthe written graph file.\n+\n EXAMPLES\n --------\n \n+* Output the OID of the graph file pointed to by /graph-head.\n++\n+------------------------------------------------\n+$ git graph --pack-dir=\n+------------------------------------------------\n+\n * Write a graph file for the packed commits in your local .git folder.\n +\n ------------------------------------------------\n-$ git midx --write\n+$ git graph --write\n+------------------------------------------------\n+\n+* Write a graph file for the packed commits in your local .git folder,\n+* and update graph-head.\n++\n+------------------------------------------------\n+$ git graph --write --update-head\n ------------------------------------------------\n \n * Read basic information from a graph file.\n +\n ------------------------------------------------\n-$ git midx --read --graph-id=\n+$ git graph --read --graph-id=\n ------------------------------------------------\n \n CONFIGURATION\ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex bc66722924..0760d99f43 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -11,7 +11,7 @@\n static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n \tN_(\"git graph --read [--graph-id=]\"),\n-\tN_(\"git graph --write [--pack-dir ]\"),\n+\tN_(\"git graph --write [--pack-dir ] [--update-head]\"),\n \tNULL\n };\n \n@@ -20,6 +20,9 @@ static struct opts_graph {\n \tint read;\n \tconst char *graph_id;\n \tint write;\n+\tint update_head;\n+\tint has_existing;\n+\tstruct object_id old_graph_oid;\n } opts;\n \n static int graph_read(void)\n@@ -30,8 +33,8 @@ static int graph_read(void)\n \n \tif (opts.graph_id && strlen(opts.graph_id) == GIT_MAX_HEXSZ)\n \t\tget_oid_hex(opts.graph_id, &graph_oid);\n-\telse\n-\t\tdie(\"no graph id specified\");\n+\telse if (!get_graph_head_oid(opts.pack_dir, &graph_oid))\n+\t\tdie(\"no graph-head exists.\");\n \n \tgraph_file = get_graph_filename_oid(opts.pack_dir, &graph_oid);\n \tgraph = load_packed_graph_one(graph_file, opts.pack_dir);\n@@ -62,10 +65,33 @@ static int graph_read(void)\n \treturn 0;\n }\n \n+static void update_head_file(const char *pack_dir, const struct object_id *graph_id)\n+{\n+\tstruct strbuf head_path = STRBUF_INIT;\n+\tint fd;\n+\tstruct lock_file lk = LOCK_INIT;\n+\n+\tstrbuf_addstr(&head_path, pack_dir);\n+\tstrbuf_addstr(&head_path, \"/\");\n+\tstrbuf_addstr(&head_path, \"graph-head\");\n+\n+\tfd = hold_lock_file_for_update(&lk, head_path.buf, LOCK_DIE_ON_ERROR);\n+\tstrbuf_release(&head_path);\n+\n+\tif (fd < 0)\n+\t\tdie_errno(\"unable to open graph-head\");\n+\n+\twrite_in_full(fd, oid_to_hex(graph_id), GIT_MAX_HEXSZ);\n+\tcommit_lock_file(&lk);\n+}\n+\n static int graph_write(void)\n {\n \tstruct object_id *graph_id = construct_graph(opts.pack_dir);\n \n+\tif (opts.update_head)\n+\t\tupdate_head_file(opts.pack_dir, graph_id);\n+\n \tif (graph_id)\n \t\tprintf(\"%s\\n\", oid_to_hex(graph_id));\n \n@@ -83,6 +109,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"read graph file\")),\n \t\tOPT_BOOL('w', \"write\", &opts.write,\n \t\t\tN_(\"write graph file\")),\n+\t\tOPT_BOOL('u', \"update-head\", &opts.update_head,\n+\t\t\tN_(\"update graph-head to written graph file\")),\n \t\t{ OPTION_STRING, 'M', \"graph-id\", &opts.graph_id,\n \t\t\tN_(\"oid\"),\n \t\t\tN_(\"An OID for a specific graph file in the pack-dir.\"),\n@@ -111,11 +139,15 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\topts.pack_dir = strbuf_detach(&path, NULL);\n \t}\n \n+\topts.has_existing = !!get_graph_head_oid(opts.pack_dir, &opts.old_graph_oid);\n+\n \tif (opts.read)\n \t\treturn graph_read();\n \tif (opts.write)\n \t\treturn graph_write();\n \n+\tif (opts.has_existing)\n+\t\tprintf(\"%s\\n\", oid_to_hex(&opts.old_graph_oid));\n \treturn 0;\n }\n \ndiff --git a/packed-graph.c b/packed-graph.c\nindex eaa656becb..5723f163ae 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -35,6 +35,31 @@\n #define GRAPH_MIN_SIZE (GRAPH_CHUNKLOOKUP_SIZE + GRAPH_FANOUT_SIZE + \\\n \t\t\tGRAPH_OID_LEN + sizeof(struct packed_graph_header))\n \n+struct object_id *get_graph_head_oid(const char *pack_dir, struct object_id *oid)\n+{\n+\tstruct strbuf head_filename = STRBUF_INIT;\n+\tchar oid_hex[GIT_MAX_HEXSZ + 1];\n+\tFILE *f;\n+\n+\tstrbuf_addstr(&head_filename, pack_dir);\n+\tstrbuf_addstr(&head_filename, \"/graph-head\");\n+\n+\tf = fopen(head_filename.buf, \"r\");\n+\tstrbuf_release(&head_filename);\n+\n+\tif (!f)\n+\t\treturn 0;\n+\n+\tif (!fgets(oid_hex, sizeof(oid_hex), f))\n+\t\tdie(\"failed to read graph-head\");\n+\n+\tfclose(f);\n+\n+\tif (get_oid_hex(oid_hex, oid))\n+\t\treturn 0;\n+\treturn oid;\n+}\n+\n char* get_graph_filename_oid(const char *pack_dir,\n \t\t\t\t struct object_id *oid)\n {\ndiff --git a/packed-graph.h b/packed-graph.h\nindex 1a7eaa2a46..ad561863c8 100644\n--- a/packed-graph.h\n+++ b/packed-graph.h\n@@ -4,6 +4,7 @@\n #include \"git-compat-util.h\"\n #include \"commit.h\"\n \n+extern struct object_id *get_graph_head_oid(const char *pack_dir, struct object_id *oid);\n extern char* get_graph_filename_oid(const char *pack_dir,\n \t\t\t\t struct object_id *oid);\n \ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 4975f65dee..3919a3ad73 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -13,7 +13,8 @@ test_expect_success 'setup full repo' \\\n packdir=\".git/objects/pack\"'\n \n test_expect_success 'write graph with no packs' \\\n- 'git graph --write --pack-dir .'\n+ 'git graph --write --pack-dir . &&\n+ test_path_is_missing graph-head'\n \n test_expect_success 'create commits and repack' \\\n 'for i in $(test_seq 5)\n@@ -37,6 +38,7 @@ EOF\n test_expect_success 'write graph' \\\n 'graph1=$(git graph --write) &&\n test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ test_path_is_missing ${packdir}/graph-head &&\n git graph --read --graph-id=${graph1} >output &&\n _graph_read_expect \"5\" \"${packdir}\" &&\n cmp expect output'\n@@ -69,8 +71,11 @@ test_expect_success 'Add more commits' \\\n git repack'\n \n test_expect_success 'write graph with merges' \\\n- 'graph2=$(git graph --write) &&\n+ 'graph2=$(git graph --write --update-head) &&\n test_path_is_file ${packdir}/graph-${graph2}.graph &&\n+ test_path_is_file ${packdir}/graph-head &&\n+ echo ${graph2} >expect &&\n+ cmp -n 40 expect ${packdir}/graph-head &&\n git graph --read --graph-id=${graph2} >output &&\n _graph_read_expect \"18\" \"${packdir}\" &&\n cmp expect output'\n@@ -86,6 +91,9 @@ test_expect_success 'setup bare repo' \\\n test_expect_success 'write graph in bare repo' \\\n 'graphbare=$(git graph --write) &&\n test_path_is_file ${baredir}/graph-${graphbare}.graph &&\n+ test_path_is_file ${baredir}/graph-head &&\n+ echo ${graphbare} >expect &&\n+ cmp -n 40 expect ${baredir}/graph-head &&\n git graph --read --graph-id=${graphbare} >output &&\n _graph_read_expect \"18\" \"${baredir}\" &&\n cmp expect output'\n-- \n2.16.0\n\n"},{"id":"337376","messageId":"20180125140231.65604-8-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 07/14] packed-graph: implement git-graph --read","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:24Z","receivedAt":"2018-01-25T14:03:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach git-graph to read packed graph files and summarize their contents.\n\nUse the --read option to verify the contents of a graph file in the\ngraph tests.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 7 +++\n builtin/graph.c | 54 ++++++++++++++++\n packed-graph.c | 147 +++++++++++++++++++++++++++++++++++++++++++-\n packed-graph.h | 25 ++++++++\n t/t5319-graph.sh | 50 +++++++++------\n 5 files changed, 260 insertions(+), 23 deletions(-)\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex be6bc38814..0939c3f1be 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -10,6 +10,7 @@ SYNOPSIS\n --------\n [verse]\n 'git graph' --write [--pack-dir ]\n+'git graph' --read [--pack-dir ]\n \n EXAMPLES\n --------\n@@ -20,6 +21,12 @@ EXAMPLES\n $ git midx --write\n ------------------------------------------------\n \n+* Read basic information from a graph file.\n++\n+------------------------------------------------\n+$ git midx --read --graph-id=\n+------------------------------------------------\n+\n CONFIGURATION\n -------------\n \ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex 09f5552338..bc66722924 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -10,15 +10,58 @@\n \n static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n+\tN_(\"git graph --read [--graph-id=]\"),\n \tN_(\"git graph --write [--pack-dir ]\"),\n \tNULL\n };\n \n static struct opts_graph {\n \tconst char *pack_dir;\n+\tint read;\n+\tconst char *graph_id;\n \tint write;\n } opts;\n \n+static int graph_read(void)\n+{\n+\tstruct object_id graph_oid;\n+\tstruct packed_graph *graph = 0;\n+\tconst char *graph_file;\n+\n+\tif (opts.graph_id && strlen(opts.graph_id) == GIT_MAX_HEXSZ)\n+\t\tget_oid_hex(opts.graph_id, &graph_oid);\n+\telse\n+\t\tdie(\"no graph id specified\");\n+\n+\tgraph_file = get_graph_filename_oid(opts.pack_dir, &graph_oid);\n+\tgraph = load_packed_graph_one(graph_file, opts.pack_dir);\n+\n+\tif (!graph)\n+\t\tdie(\"graph file %s does not exist.\\n\", graph_file);\n+\n+\tprintf(\"header: %08x %02x %02x %02x %02x\\n\",\n+\t\tntohl(graph->hdr->graph_signature),\n+\t\tgraph->hdr->graph_version,\n+\t\tgraph->hdr->hash_version,\n+\t\tgraph->hdr->hash_len,\n+\t\tgraph->hdr->num_chunks);\n+\tprintf(\"num_commits: %u\\n\", graph->num_commits);\n+\tprintf(\"chunks:\");\n+\n+\tif (graph->chunk_oid_fanout)\n+\t\tprintf(\" oid_fanout\");\n+\tif (graph->chunk_oid_lookup)\n+\t\tprintf(\" oid_lookup\");\n+\tif (graph->chunk_commit_data)\n+\t\tprintf(\" commit_metadata\");\n+\tif (graph->chunk_large_edges)\n+\t\tprintf(\" large_edges\");\n+\tprintf(\"\\n\");\n+\n+\tprintf(\"pack_dir: %s\\n\", graph->pack_dir);\n+\treturn 0;\n+}\n+\n static int graph_write(void)\n {\n \tstruct object_id *graph_id = construct_graph(opts.pack_dir);\n@@ -36,8 +79,14 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n \t\t\tN_(\"dir\"),\n \t\t\tN_(\"The pack directory to store the graph\") },\n+\t\tOPT_BOOL('r', \"read\", &opts.read,\n+\t\t\tN_(\"read graph file\")),\n \t\tOPT_BOOL('w', \"write\", &opts.write,\n \t\t\tN_(\"write graph file\")),\n+\t\t{ OPTION_STRING, 'M', \"graph-id\", &opts.graph_id,\n+\t\t\tN_(\"oid\"),\n+\t\t\tN_(\"An OID for a specific graph file in the pack-dir.\"),\n+\t\t\tPARSE_OPT_OPTARG, NULL, (intptr_t) \"\" },\n \t\tOPT_END(),\n \t};\n \n@@ -52,6 +101,9 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\t builtin_graph_options,\n \t\t\t builtin_graph_usage, 0);\n \n+\tif (opts.write + opts.read > 1)\n+\t\tusage_with_options(builtin_graph_usage, builtin_graph_options);\n+\n \tif (!opts.pack_dir) {\n \t\tstruct strbuf path = STRBUF_INIT;\n \t\tstrbuf_addstr(&path, get_object_directory());\n@@ -59,6 +111,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\topts.pack_dir = strbuf_detach(&path, NULL);\n \t}\n \n+\tif (opts.read)\n+\t\treturn graph_read();\n \tif (opts.write)\n \t\treturn graph_write();\n \ndiff --git a/packed-graph.c b/packed-graph.c\nindex 9be9811667..eaa656becb 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -30,6 +30,11 @@\n \n #define GRAPH_LAST_EDGE 0x80000000\n \n+#define GRAPH_FANOUT_SIZE (4*256)\n+#define GRAPH_CHUNKLOOKUP_SIZE (5 * 12)\n+#define GRAPH_MIN_SIZE (GRAPH_CHUNKLOOKUP_SIZE + GRAPH_FANOUT_SIZE + \\\n+\t\t\tGRAPH_OID_LEN + sizeof(struct packed_graph_header))\n+\n char* get_graph_filename_oid(const char *pack_dir,\n \t\t\t\t struct object_id *oid)\n {\n@@ -43,6 +48,142 @@ char* get_graph_filename_oid(const char *pack_dir,\n \treturn strbuf_detach(&head_path, &len);\n }\n \n+static struct packed_graph *alloc_packed_graph(int extra)\n+{\n+\tstruct packed_graph *g = xmalloc(st_add(sizeof(*g), extra));\n+\tmemset(g, 0, sizeof(*g));\n+\tg->graph_fd = -1;\n+\n+\treturn g;\n+}\n+\n+int close_graph(struct packed_graph *g)\n+{\n+\tif (g->graph_fd < 0)\n+\t\treturn 0;\n+\n+\tmunmap((void *)g->data, g->data_len);\n+\tg->data = 0;\n+\n+\tclose(g->graph_fd);\n+\tg->graph_fd = -1;\n+\n+\treturn 1;\n+}\n+\n+static void free_packed_graph(struct packed_graph **g)\n+{\n+\tif (!g || !*g)\n+\t\treturn;\n+\n+\tclose_graph(*g);\n+\n+\tfree(*g);\n+\t*g = NULL;\n+}\n+\n+struct packed_graph *load_packed_graph_one(const char *graph_file, const char *pack_dir)\n+{\n+\tvoid *graph_map;\n+\tconst unsigned char *data;\n+\tstruct packed_graph_header *hdr;\n+\tsize_t graph_size;\n+\tstruct stat st;\n+\tuint32_t i;\n+\tstruct packed_graph *graph;\n+\tint fd = git_open(graph_file);\n+\tuint64_t last_chunk_offset;\n+\tuint32_t last_chunk_id;\n+\n+\tif (fd < 0)\n+\t\treturn 0;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn 0;\n+\t}\n+\tgraph_size = xsize_t(st.st_size);\n+\n+\tif (graph_size < GRAPH_MIN_SIZE) {\n+\t\tclose(fd);\n+\t\tdie(\"graph file %s is too small\", graph_file);\n+\t}\n+\tgraph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tdata = (const unsigned char *)graph_map;\n+\n+\thdr = graph_map;\n+\tif (ntohl(hdr->graph_signature) != GRAPH_SIGNATURE) {\n+\t\tuint32_t signature = ntohl(hdr->graph_signature);\n+\t\tmunmap(graph_map, graph_size);\n+\t\tclose(fd);\n+\t\tdie(\"graph signature %X does not match signature %X\",\n+\t\t\tsignature, GRAPH_SIGNATURE);\n+\t}\n+\tif (hdr->graph_version != GRAPH_VERSION) {\n+\t\tunsigned char version = hdr->graph_version;\n+\t\tmunmap(graph_map, graph_size);\n+\t\tclose(fd);\n+\t\tdie(\"graph version %X does not match version %X\",\n+\t\t\tversion, GRAPH_VERSION);\n+\t}\n+\n+\tgraph = alloc_packed_graph(strlen(pack_dir) + 1);\n+\n+\tgraph->hdr = hdr;\n+\tgraph->graph_fd = fd;\n+\tgraph->data = graph_map;\n+\tgraph->data_len = graph_size;\n+\n+\tlast_chunk_id = 0;\n+\tlast_chunk_offset = (uint64_t)sizeof(*hdr);\n+\tfor (i = 0; i < hdr->num_chunks; i++) {\n+\t\tuint32_t chunk_id = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i));\n+\t\tuint64_t chunk_offset1 = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i + 4));\n+\t\tuint32_t chunk_offset2 = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i + 8));\n+\t\tuint64_t chunk_offset = (chunk_offset1 << 32) | chunk_offset2;\n+\n+\t\tif (chunk_offset > graph_size - GIT_MAX_RAWSZ)\n+\t\t\tdie(\"improper chunk offset %08x%08x\", (uint32_t)(chunk_offset >> 32),\n+\t\t\t (uint32_t)chunk_offset);\n+\n+\t\tswitch (chunk_id) {\n+\t\t\tcase GRAPH_CHUNKID_OIDFANOUT:\n+\t\t\t\tgraph->chunk_oid_fanout = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase GRAPH_CHUNKID_OIDLOOKUP:\n+\t\t\t\tgraph->chunk_oid_lookup = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase GRAPH_CHUNKID_DATA:\n+\t\t\t\tgraph->chunk_commit_data = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase GRAPH_CHUNKID_LARGEEDGES:\n+\t\t\t\tgraph->chunk_large_edges = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase 0:\n+\t\t\t\tbreak;\n+\n+\t\t\tdefault:\n+\t\t\t\tfree_packed_graph(&graph);\n+\t\t\t\tdie(\"unrecognized graph chunk id: %08x\", chunk_id);\n+\t\t}\n+\n+\t\tif (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)\n+\t\t{\n+\t\t\tgraph->num_commits = (chunk_offset - last_chunk_offset)\n+\t\t\t\t\t / hdr->hash_len;\n+\t\t}\n+\n+\t\tlast_chunk_id = chunk_id;\n+\t\tlast_chunk_offset = chunk_offset;\n+\t}\n+\n+\tstrcpy(graph->pack_dir, pack_dir);\n+\treturn graph;\n+}\n+\n static void write_graph_chunk_fanout(\n \tstruct sha1file *f,\n \tstruct commit **commits, int nr_commits)\n@@ -338,8 +479,8 @@ struct object_id *construct_graph(const char *pack_dir)\n \tchunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;\n \tchunk_ids[4] = 0;\n \n-\tchunk_offsets[0] = sizeof(hdr) + 12 * 5; // Skip header and chunk list\n-\tchunk_offsets[1] = chunk_offsets[0] + 256 * 4; // fanout table size\n+\tchunk_offsets[0] = sizeof(hdr) + GRAPH_CHUNKLOOKUP_SIZE;\n+\tchunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;\n \tchunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.num; // lookup size\n \tchunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.num; // data size\n \tchunk_offsets[4] = chunk_offsets[3] + 4 * num_long_edges;\n@@ -361,7 +502,7 @@ struct object_id *construct_graph(const char *pack_dir)\n \tsha1close(f, final_hash, CSUM_CLOSE | CSUM_FSYNC);\n \n \tf_oid = (struct object_id *)malloc(sizeof(struct object_id));\n-\tmemcpy(f_oid->hash, final_hash, GIT_MAX_RAWSZ);\n+\thashcpy(f_oid->hash, final_hash);\n \tfname = get_graph_filename_oid(pack_dir, f_oid);\n \n \tif (rename(graph_name, fname))\ndiff --git a/packed-graph.h b/packed-graph.h\nindex d4e10fb612..1a7eaa2a46 100644\n--- a/packed-graph.h\n+++ b/packed-graph.h\n@@ -15,6 +15,31 @@ struct packed_graph_header {\n \tunsigned char num_chunks;\n };\n \n+extern struct packed_graph {\n+\tint graph_fd;\n+\n+\tconst unsigned char *data;\n+\tsize_t data_len;\n+\n+\tconst struct packed_graph_header *hdr;\n+\n+\tstruct object_id oid;\n+\n+\tuint32_t num_commits;\n+\n+\tconst unsigned char *chunk_oid_fanout;\n+\tconst unsigned char *chunk_oid_lookup;\n+\tconst unsigned char *chunk_commit_data;\n+\tconst unsigned char *chunk_large_edges;\n+\n+\t/* something like \".git/objects/pack\" */\n+\tchar pack_dir[FLEX_ARRAY]; /* more */\n+} *packed_graph;\n+\n+extern int close_graph(struct packed_graph *g);\n+\n+extern struct packed_graph *load_packed_graph_one(const char *graph_file, const char *pack_dir);\n+\n extern struct object_id *construct_graph(const char *pack_dir);\n \n #endif\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 52e979dfd3..4975f65dee 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -3,8 +3,7 @@\n test_description='packed graph'\n . ./test-lib.sh\n \n-test_expect_success \\\n- 'setup full repo' \\\n+test_expect_success 'setup full repo' \\\n 'rm -rf .git &&\n mkdir full &&\n cd full &&\n@@ -13,12 +12,10 @@ test_expect_success \\\n git config pack.threads 1 &&\n packdir=\".git/objects/pack\"'\n \n-test_expect_success \\\n- 'write graph with no packs' \\\n+test_expect_success 'write graph with no packs' \\\n 'git graph --write --pack-dir .'\n \n-test_expect_success \\\n- 'create commits and repack' \\\n+test_expect_success 'create commits and repack' \\\n 'for i in $(test_seq 5)\n do\n echo $i >$i.txt &&\n@@ -28,13 +25,23 @@ test_expect_success \\\n done &&\n git repack'\n \n-test_expect_success \\\n- 'write graph' \\\n+_graph_read_expect() {\n+ cat >expect <<- EOF\n+header: 43475048 01 01 14 04\n+num_commits: $1\n+chunks: oid_fanout oid_lookup commit_metadata large_edges\n+pack_dir: $2\n+EOF\n+}\n+\n+test_expect_success 'write graph' \\\n 'graph1=$(git graph --write) &&\n- test_path_is_file ${packdir}/graph-${graph1}.graph'\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ git graph --read --graph-id=${graph1} >output &&\n+ _graph_read_expect \"5\" \"${packdir}\" &&\n+ cmp expect output'\n \n-test_expect_success \\\n- 'Add more commits' \\\n+test_expect_success 'Add more commits' \\\n 'git reset --hard commits/3 &&\n for i in $(test_seq 6 10)\n do\n@@ -61,23 +68,26 @@ test_expect_success \\\n git merge commits/5 commits/13 &&\n git repack'\n \n-test_expect_success \\\n- 'write graph with merges' \\\n+test_expect_success 'write graph with merges' \\\n 'graph2=$(git graph --write) &&\n- test_path_is_file ${packdir}/graph-${graph2}.graph'\n+ test_path_is_file ${packdir}/graph-${graph2}.graph &&\n+ git graph --read --graph-id=${graph2} >output &&\n+ _graph_read_expect \"18\" \"${packdir}\" &&\n+ cmp expect output'\n \n-test_expect_success \\\n- 'setup bare repo' \\\n+test_expect_success 'setup bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n cd bare &&\n git config core.graph true &&\n git config pack.threads 1 &&\n- baredir=\"objects/pack\"'\n+ baredir=\"./objects/pack\"'\n \n-test_expect_success \\\n- 'write graph in bare repo' \\\n+test_expect_success 'write graph in bare repo' \\\n 'graphbare=$(git graph --write) &&\n- test_path_is_file ${baredir}/graph-${graphbare}.graph'\n+ test_path_is_file ${baredir}/graph-${graphbare}.graph &&\n+ git graph --read --graph-id=${graphbare} >output &&\n+ _graph_read_expect \"18\" \"${baredir}\" &&\n+ cmp expect output'\n \n test_done\n-- \n2.16.0\n\n"},{"id":"337377","messageId":"20180125140231.65604-11-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 10/14] packed-graph: teach git-graph --delete-expired","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:27Z","receivedAt":"2018-01-25T14:03:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach git-graph to delete the graph previously referenced by 'graph_head'\nwhen writing a new graph file and updating 'graph_head'. This prevents\ndata creep by storing a list of useless graphs. Be careful to not delete\nthe graph if the file did not change.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 8 ++++++--\n builtin/graph.c | 14 +++++++++++++-\n t/t5319-graph.sh | 37 +++++++++++++++++++++++++++++++++++--\n 3 files changed, 54 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex f690699570..f4f1048d28 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -39,6 +39,10 @@ OPTIONS\n \tWhen used with --write, update the graph-head file to point to\n \tthe written graph file.\n \n+--delete-expired::\n+\tWhen used with --write and --update-head, delete the graph file\n+\tpreviously referenced by graph-head.\n+\n EXAMPLES\n --------\n \n@@ -55,10 +59,10 @@ $ git graph --write\n ------------------------------------------------\n \n * Write a graph file for the packed commits in your local .git folder,\n-* and update graph-head.\n+* update graph-head, and delete the old graph-.graph file.\n +\n ------------------------------------------------\n-$ git graph --write --update-head\n+$ git graph --write --update-head --delete-expired\n ------------------------------------------------\n \n * Read basic information from a graph file.\ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex ac15febc46..adf779b601 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -12,7 +12,7 @@ static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n \tN_(\"git graph --clear [--pack-dir ]\"),\n \tN_(\"git graph --read [--graph-id=]\"),\n-\tN_(\"git graph --write [--pack-dir ] [--update-head]\"),\n+\tN_(\"git graph --write [--pack-dir ] [--update-head] [--delete-expired]\"),\n \tNULL\n };\n \n@@ -23,6 +23,7 @@ static struct opts_graph {\n \tconst char *graph_id;\n \tint write;\n \tint update_head;\n+\tint delete_expired;\n \tint has_existing;\n \tstruct object_id old_graph_oid;\n } opts;\n@@ -120,6 +121,15 @@ static int graph_write(void)\n \tif (graph_id)\n \t\tprintf(\"%s\\n\", oid_to_hex(graph_id));\n \n+\tif (opts.delete_expired && opts.update_head && opts.has_existing &&\n+\t oidcmp(graph_id, &opts.old_graph_oid)) {\n+\t\tchar *old_path = get_graph_filename_oid(opts.pack_dir, &opts.old_graph_oid);\n+\t\tif (remove_path(old_path))\n+\t\t\tdie(\"failed to remove path %s\", old_path);\n+\n+\t\tfree(old_path);\n+\t}\n+\n \tfree(graph_id);\n \treturn 0;\n }\n@@ -138,6 +148,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"write graph file\")),\n \t\tOPT_BOOL('u', \"update-head\", &opts.update_head,\n \t\t\tN_(\"update graph-head to written graph file\")),\n+\t\tOPT_BOOL('d', \"delete-expired\", &opts.delete_expired,\n+\t\t\tN_(\"delete expired head graph file\")),\n \t\t{ OPTION_STRING, 'M', \"graph-id\", &opts.graph_id,\n \t\t\tN_(\"oid\"),\n \t\t\tN_(\"An OID for a specific graph file in the pack-dir.\"),\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 311fb9dd67..a70c7bbb02 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -80,9 +80,42 @@ test_expect_success 'write graph with merges' \\\n _graph_read_expect \"18\" \"${packdir}\" &&\n cmp expect output'\n \n+test_expect_success 'Add more commits' \\\n+ 'git reset --hard commits/3 &&\n+ for i in $(test_seq 16 20)\n+ do\n+ git commit --allow-empty -m \"commit $i\" &&\n+ git branch commits/$i\n+ done &&\n+ git repack'\n+\n+test_expect_success 'write graph with merges' \\\n+ 'graph3=$(git graph --write --update-head --delete-expired) &&\n+ test_path_is_file ${packdir}/graph-${graph3}.graph &&\n+ test_path_is_missing ${packdir}/graph-${graph2}.graph &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ test_path_is_file ${packdir}/graph-head &&\n+ echo ${graph3} >expect &&\n+ cmp -n 40 expect ${packdir}/graph-head &&\n+ git graph --read --graph-id=${graph3} >output &&\n+ _graph_read_expect \"23\" \"${packdir}\" &&\n+ cmp expect output'\n+\n+test_expect_success 'write graph with nothing new' \\\n+ 'graph4=$(git graph --write --update-head --delete-expired) &&\n+ test_path_is_file ${packdir}/graph-${graph4}.graph &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ test_path_is_file ${packdir}/graph-head &&\n+ echo ${graph4} >expect &&\n+ cmp -n 40 expect ${packdir}/graph-head &&\n+ git graph --read --graph-id=${graph4} >output &&\n+ _graph_read_expect \"23\" \"${packdir}\" &&\n+ cmp expect output'\n+\n test_expect_success 'clear graph' \\\n 'git graph --clear &&\n- test_path_is_missing ${packdir}/graph-${graph2}.graph &&\n+ test_path_is_missing ${packdir}/graph-${graph3}.graph &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n test_path_is_missing ${packdir}/graph-head'\n \n test_expect_success 'setup bare repo' \\\n@@ -100,7 +133,7 @@ test_expect_success 'write graph in bare repo' \\\n echo ${graphbare} >expect &&\n cmp -n 40 expect ${baredir}/graph-head &&\n git graph --read --graph-id=${graphbare} >output &&\n- _graph_read_expect \"18\" \"${baredir}\" &&\n+ _graph_read_expect \"23\" \"${baredir}\" &&\n cmp expect output'\n \n test_done\n-- \n2.16.0\n\n"},{"id":"337378","messageId":"20180125140231.65604-13-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 12/14] packed-graph: read only from specific pack-indexes","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:29Z","receivedAt":"2018-01-25T14:03:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach git-graph to inspect the objects only in a certain list of\npack-indexes within the given pack directory. This allows updating\nthe graph iteratively, since we add all commits stored in a previous\npacked graph.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-graph.txt | 12 ++++++++++++\n builtin/graph.c | 26 +++++++++++++++++++++++---\n packed-graph.c | 27 +++++++++++++++++++++++----\n packed-graph.h | 2 +-\n packfile.c | 4 ++--\n packfile.h | 2 ++\n t/t5319-graph.sh | 10 ++++++----\n 7 files changed, 69 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/git-graph.txt b/Documentation/git-graph.txt\nindex f4f1048d28..b68a61ddea 100644\n--- a/Documentation/git-graph.txt\n+++ b/Documentation/git-graph.txt\n@@ -43,6 +43,11 @@ OPTIONS\n \tWhen used with --write and --update-head, delete the graph file\n \tpreviously referenced by graph-head.\n \n+--stdin-packs::\n+\tWhen used with --write, generate the new graph by walking objects\n+\tonly in the specified packfiles and any commits in the\n+\texisting graph-head.\n+\n EXAMPLES\n --------\n \n@@ -65,6 +70,13 @@ $ git graph --write\n $ git graph --write --update-head --delete-expired\n ------------------------------------------------\n \n+* Write a graph file, extending the current graph file using commits\n+* in , update graph-head, and delete the old graph-.graph file.\n++\n+------------------------------------------------\n+$ echo | git graph --write --update-head --delete-expired --stdin-packs\n+------------------------------------------------\n+\n * Read basic information from a graph file.\n +\n ------------------------------------------------\ndiff --git a/builtin/graph.c b/builtin/graph.c\nindex adf779b601..3cace3a18c 100644\n--- a/builtin/graph.c\n+++ b/builtin/graph.c\n@@ -12,7 +12,7 @@ static char const * const builtin_graph_usage[] ={\n \tN_(\"git graph [--pack-dir ]\"),\n \tN_(\"git graph --clear [--pack-dir ]\"),\n \tN_(\"git graph --read [--graph-id=]\"),\n-\tN_(\"git graph --write [--pack-dir ] [--update-head] [--delete-expired]\"),\n+\tN_(\"git graph --write [--pack-dir ] [--update-head] [--delete-expired] [--stdin-packs]\"),\n \tNULL\n };\n \n@@ -24,6 +24,7 @@ static struct opts_graph {\n \tint write;\n \tint update_head;\n \tint delete_expired;\n+\tint stdin_packs;\n \tint has_existing;\n \tstruct object_id old_graph_oid;\n } opts;\n@@ -113,7 +114,24 @@ static void update_head_file(const char *pack_dir, const struct object_id *graph\n \n static int graph_write(void)\n {\n-\tstruct object_id *graph_id = construct_graph(opts.pack_dir);\n+\tstruct object_id *graph_id;\n+\tchar **pack_indexes = NULL;\n+\tint num_packs = 0;\n+\tint size_packs = 0;\n+\n+\tif (opts.stdin_packs) {\n+\t\tstruct strbuf buf = STRBUF_INIT;\n+\t\tsize_packs = 128;\n+\t\tALLOC_ARRAY(pack_indexes, size_packs);\n+\n+\t\twhile (strbuf_getline(&buf, stdin) != EOF) {\n+\t\t\tALLOC_GROW(pack_indexes, num_packs + 1, size_packs);\n+\t\t\tpack_indexes[num_packs++] = buf.buf;\n+\t\t\tstrbuf_detach(&buf, NULL);\n+\t\t}\n+\t}\n+\n+\tgraph_id = construct_graph(opts.pack_dir, pack_indexes, num_packs);\n \n \tif (opts.update_head)\n \t\tupdate_head_file(opts.pack_dir, graph_id);\n@@ -150,7 +168,9 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"update graph-head to written graph file\")),\n \t\tOPT_BOOL('d', \"delete-expired\", &opts.delete_expired,\n \t\t\tN_(\"delete expired head graph file\")),\n-\t\t{ OPTION_STRING, 'M', \"graph-id\", &opts.graph_id,\n+\t\tOPT_BOOL('s', \"stdin-packs\", &opts.stdin_packs,\n+\t\t\tN_(\"only scan packfiles listed by stdin\")),\n+\t\t{ OPTION_STRING, 'G', \"graph-id\", &opts.graph_id,\n \t\t\tN_(\"oid\"),\n \t\t\tN_(\"An OID for a specific graph file in the pack-dir.\"),\n \t\t\tPARSE_OPT_OPTARG, NULL, (intptr_t) \"\" },\ndiff --git a/packed-graph.c b/packed-graph.c\nindex 343b231973..0dc68a077e 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -401,7 +401,7 @@ static int fill_packed_commit(struct commit *item, struct packed_graph *g, uint3\n * 2. date\n * 3. parents.\n *\n- * Returns 1 iff the commit was found in the packed graph.\n+ * Returns 1 if and only if the commit was found in the packed graph.\n *\n * See parse_commit_buffer() for the fallback after this call.\n */\n@@ -427,7 +427,7 @@ int parse_packed_commit(struct commit *item)\n \t\t\treturn fill_packed_commit(item, packed_graph, pos);\n \t}\n \n-\treturn parse_commit_internal(item, 0, 0);\n+\treturn 0;\n }\n \n static void write_graph_chunk_fanout(\n@@ -638,7 +638,7 @@ static int if_packed_commit_add_to_list(const struct object_id *oid,\n \treturn 0;\n }\n \n-struct object_id *construct_graph(const char *pack_dir)\n+struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs)\n {\n \t// Find a list of oids, adding the pointer to a list.\n \tstruct packed_oid_list oids;\n@@ -678,7 +678,26 @@ struct object_id *construct_graph(const char *pack_dir)\n \t\toids.num = packed_graph->num_commits;\n \t}\n \n-\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n+\tif (pack_indexes) {\n+\t\tint pack_dir_len = strlen(pack_dir) + 1;\n+\t\tstruct strbuf packname = STRBUF_INIT;\n+\t\tstrbuf_add(&packname, pack_dir, pack_dir_len - 1);\n+\t\tstrbuf_addch(&packname, '/');\n+\t\tfor (i = 0; i < nr_packs; i++) {\n+\t\t\tstruct packed_git *p;\n+\t\t\tstrbuf_setlen(&packname, pack_dir_len);\n+\t\t\tstrbuf_addstr(&packname, pack_indexes[i]);\n+\t\t\tp = add_packed_git(packname.buf, packname.len, 1);\n+\t\t\tif (!p)\n+\t\t\t\tdie(\"error adding pack %s\", packname.buf);\n+\t\t\tif (open_pack_index(p))\n+\t\t\t\tdie(\"error opening index for %s\", packname.buf);\n+\t\t\tfor_each_object_in_pack(p, if_packed_commit_add_to_list, &oids);\n+\t\t\tclose_pack(p);\n+\t\t}\n+\t} else {\n+\t\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n+\t}\n \tQSORT(oids.list, oids.num, commit_compare);\n \n \tcount_distinct = 1;\ndiff --git a/packed-graph.h b/packed-graph.h\nindex 6010ce3e53..97ce1e2652 100644\n--- a/packed-graph.h\n+++ b/packed-graph.h\n@@ -58,7 +58,7 @@ extern struct object_id *get_nth_commit_oid(struct packed_graph *g,\n \t\t\t\t\t uint32_t n,\n \t\t\t\t\t struct object_id *oid);\n \n-extern struct object_id *construct_graph(const char *pack_dir);\n+extern struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs);\n extern int close_graph(struct packed_graph *g);\n \n #endif\ndiff --git a/packfile.c b/packfile.c\nindex 4a5fe7ab18..48133bd669 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -299,7 +299,7 @@ void close_pack_index(struct packed_git *p)\n \t}\n }\n \n-static void close_pack(struct packed_git *p)\n+void close_pack(struct packed_git *p)\n {\n \tclose_pack_windows(p);\n \tclose_pack_fd(p);\n@@ -1860,7 +1860,7 @@ int has_pack_index(const unsigned char *sha1)\n \treturn 1;\n }\n \n-static int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)\n+int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)\n {\n \tuint32_t i;\n \tint r = 0;\ndiff --git a/packfile.h b/packfile.h\nindex 0cdeb54dcd..cde868feb6 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -61,6 +61,7 @@ extern void close_pack_index(struct packed_git *);\n \n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n extern void close_pack_windows(struct packed_git *);\n+extern void close_pack(struct packed_git *);\n extern void close_all_packs(void);\n extern void unuse_pack(struct pack_window **);\n extern void clear_delta_base_cache(void);\n@@ -133,6 +134,7 @@ typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n \t\t\t\t uint32_t pos,\n \t\t\t\t void *data);\n+extern int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data);\n extern int for_each_packed_object(each_packed_object_fn, void *, unsigned flags);\n \n #endif\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 4552795179..969150cd21 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -34,8 +34,8 @@ _graph_git_two_modes() {\n \n _graph_git_behavior() {\n test_expect_success 'check normal git operations' \\\n- '_graph_git_two_modes \"log --oneline master\" &&\n- _graph_git_two_modes \"log --topo-order master\" &&\n+ '_graph_git_two_modes \"log --oneline $1\" &&\n+ _graph_git_two_modes \"log --topo-order $1\" &&\n _graph_git_two_modes \"log --graph $1 $2\" &&\n _graph_git_two_modes \"branch -vv\" &&\n _graph_git_two_modes \"merge-base -a $1 $2\"'\n@@ -136,7 +136,9 @@ test_expect_success 'Add more commits' \\\n git commit -m \"commit $i\" &&\n git branch commits/$i\n done &&\n- git repack'\n+ ls ${packdir} | grep idx >existing-idx &&\n+ git repack &&\n+ ls ${packdir} | grep idx | grep -v --file=existing-idx >new-idx'\n \n # Current graph structure:\n #\n@@ -173,7 +175,7 @@ _graph_git_behavior commits/20 merge/1\n _graph_git_behavior commits/20 merge/2\n \n test_expect_success 'write graph with merges' \\\n- 'graph3=$(git graph --write --update-head --delete-expired) &&\n+ 'graph3=$(cat new-idx | git graph --write --update-head --delete-expired --stdin-packs) &&\n test_path_is_file ${packdir}/graph-${graph3}.graph &&\n test_path_is_missing ${packdir}/graph-${graph2}.graph &&\n test_path_is_file ${packdir}/graph-${graph1}.graph &&\n-- \n2.16.0\n\n"},{"id":"337379","messageId":"20180125140231.65604-14-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 13/14] packed-graph: close under reachability","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:30Z","receivedAt":"2018-01-25T14:03:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach construct_graph() to walk all parents from the commits discovered in\npackfiles. This prevents gaps given by loose objects or previously-missed\npackfiles.\n\nSigned-off-by: Derrick Stolee \n---\n packed-graph.c | 26 ++++++++++++++++++++++++++\n t/t5319-graph.sh | 14 ++++++++++++++\n 2 files changed, 40 insertions(+)\n\ndiff --git a/packed-graph.c b/packed-graph.c\nindex 0dc68a077e..c93515f18e 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -5,6 +5,7 @@\n #include \"packfile.h\"\n #include \"commit.h\"\n #include \"object.h\"\n+#include \"revision.h\"\n #include \"packed-graph.h\"\n \n #define GRAPH_SIGNATURE 0x43475048 /* \"CGPH\" */\n@@ -638,6 +639,29 @@ static int if_packed_commit_add_to_list(const struct object_id *oid,\n \treturn 0;\n }\n \n+static void close_reachable(struct packed_oid_list *oids)\n+{\n+\tint i;\n+\tstruct rev_info revs;\n+\tstruct commit *commit;\n+\tinit_revisions(&revs, NULL);\n+\n+\tfor (i = 0; i < oids->num; i++) {\n+\t\tcommit = lookup_commit(oids->list[i]);\n+\t\tif (commit && !parse_commit(commit))\n+\t\t\trevs.commits = commit_list_insert(commit, &revs.commits);\n+\t}\n+\n+\tif (prepare_revision_walk(&revs))\n+\t\tdie(_(\"revision walk setup failed\"));\n+\n+\twhile ((commit = get_revision(&revs)) != NULL) {\n+\t\tALLOC_GROW(oids->list, oids->num + 1, oids->size);\n+\t\toids->list[oids->num] = &(commit->object.oid);\n+\t\t(oids->num)++;\n+\t}\n+}\n+\n struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int nr_packs)\n {\n \t// Find a list of oids, adding the pointer to a list.\n@@ -698,6 +722,8 @@ struct object_id *construct_graph(const char *pack_dir, char **pack_indexes, int\n \t} else {\n \t\tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n \t}\n+\n+\tclose_reachable(&oids);\n \tQSORT(oids.list, oids.num, commit_compare);\n \n \tcount_distinct = 1;\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex 969150cd21..8bf5a0c993 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -212,6 +212,20 @@ test_expect_success 'clear graph' \\\n _graph_git_behavior commits/20 merge/1\n _graph_git_behavior commits/20 merge/2\n \n+test_expect_success 'build graph from latest pack with closure' \\\n+ 'graph5=$(cat new-idx | git graph --write --update-head --stdin-packs) &&\n+ test_path_is_file ${packdir}/graph-${graph5}.graph &&\n+ test_path_is_file ${packdir}/graph-${graph1}.graph &&\n+ test_path_is_file ${packdir}/graph-head &&\n+ echo ${graph5} >expect &&\n+ cmp -n 40 expect ${packdir}/graph-head &&\n+ git graph --read --graph-id=${graph5} >output &&\n+ _graph_read_expect \"21\" \"${packdir}\" &&\n+ cmp expect output'\n+\n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'setup bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n-- \n2.16.0\n\n"},{"id":"337380","messageId":"20180125140231.65604-12-dstolee@microsoft.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"[PATCH 11/14] commit: integrate packed graph with commit parsing","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T14:02:28Z","receivedAt":"2018-01-25T14:03:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Teach Git to inspect a packed graph to supply the contents of a\nstruct commit when calling parse_commit_gently(). This implementation\nsatisfies all post-conditions on the struct commit, including loading\nparents, the root tree, and the commit date. The only loosely-expected\ncondition is that the commit buffer is loaded into the cache. This\nwas checked in log-tree.c:show_log(), but the \"return;\" on failure\nproduced unexpected results (i.e. the message line was never terminated).\nThe new behavior of loading the buffer when needed prevents the\nunexpected behavior.\n\nIf core.graph is false, then do not load the graph and behave as usual.\n\nIn test script t5319-graph.sh, add output-matching conditions on read-\nonly graph operations.\n\nBy loading commits from the graph instead of parsing commit buffers, we\nsave a lot of time on long commits walks. Here are some performance\nresults for a copy of the Linux repository where 'master' has 704,766\nreachable commits and is behind 'origin/master' by 19,610 commits.\n\n| Command | Before | After | Rel % |\n|----------------------------------|--------|--------|-------|\n| log --oneline --topo-order -1000 | 5.9s | 0.7s | -88% |\n| branch -vv | 0.42s | 0.27s | -35% |\n| rev-list --all | 6.4s | 1.0s | -84% |\n| rev-list --all --objects | 32.6s | 27.6s | -15% |\n\nSigned-off-by: Derrick Stolee \n---\n alloc.c | 1 +\n commit.c | 20 ++++-\n commit.h | 2 +\n log-tree.c | 3 +-\n packed-graph.c | 242 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n packed-graph.h | 18 +++++\n t/t5319-graph.sh | 114 ++++++++++++++++++++++++--\n 7 files changed, 387 insertions(+), 13 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 12afadfacd..4a4dcfa2b7 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -93,6 +93,7 @@ void *alloc_commit_node(void)\n \tstruct commit *c = alloc_node(&commit_state, sizeof(struct commit));\n \tc->object.type = OBJ_COMMIT;\n \tc->index = alloc_commit_index();\n+\tc->graphId = 0xFFFFFFFF;\n \treturn c;\n }\n \ndiff --git a/commit.c b/commit.c\nindex cab8d4455b..253c102808 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -12,6 +12,7 @@\n #include \"prio-queue.h\"\n #include \"sha1-lookup.h\"\n #include \"wt-status.h\"\n+#include \"packed-graph.h\"\n \n static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);\n \n@@ -374,7 +375,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \treturn 0;\n }\n \n-int parse_commit_gently(struct commit *item, int quiet_on_missing)\n+int parse_commit_internal(struct commit *item, int quiet_on_missing, int check_packed)\n {\n \tenum object_type type;\n \tvoid *buffer;\n@@ -383,19 +384,27 @@ int parse_commit_gently(struct commit *item, int quiet_on_missing)\n \n \tif (!item)\n \t\treturn -1;\n+\n+\t// If we already parsed, but got it from the graph, then keep going!\n \tif (item->object.parsed)\n \t\treturn 0;\n+\n+\tif (check_packed && parse_packed_commit(item))\n+\t\treturn 0;\n+\n \tbuffer = read_sha1_file(item->object.oid.hash, &type, &size);\n \tif (!buffer)\n \t\treturn quiet_on_missing ? -1 :\n \t\t\terror(\"Could not read %s\",\n-\t\t\t oid_to_hex(&item->object.oid));\n+\t\t\toid_to_hex(&item->object.oid));\n \tif (type != OBJ_COMMIT) {\n \t\tfree(buffer);\n \t\treturn error(\"Object %s not a commit\",\n-\t\t\t oid_to_hex(&item->object.oid));\n+\t\t\toid_to_hex(&item->object.oid));\n \t}\n+\n \tret = parse_commit_buffer(item, buffer, size);\n+\n \tif (save_commit_buffer && !ret) {\n \t\tset_commit_buffer(item, buffer, size);\n \t\treturn 0;\n@@ -404,6 +413,11 @@ int parse_commit_gently(struct commit *item, int quiet_on_missing)\n \treturn ret;\n }\n \n+int parse_commit_gently(struct commit *item, int quiet_on_missing)\n+{\n+\treturn parse_commit_internal(item, quiet_on_missing, 1);\n+}\n+\n void parse_commit_or_die(struct commit *item)\n {\n \tif (parse_commit(item))\ndiff --git a/commit.h b/commit.h\nindex 8c68ca1a5a..02f5f2a182 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -21,6 +21,7 @@ struct commit {\n \ttimestamp_t date;\n \tstruct commit_list *parents;\n \tstruct tree *tree;\n+\tuint32_t graphId;\n };\n \n extern int save_commit_buffer;\n@@ -60,6 +61,7 @@ struct commit *lookup_commit_reference_by_name(const char *name);\n struct commit *lookup_commit_or_die(const struct object_id *oid, const char *ref_name);\n \n int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size);\n+extern int parse_commit_internal(struct commit *item, int quiet_on_missing, int check_packed);\n int parse_commit_gently(struct commit *item, int quiet_on_missing);\n static inline int parse_commit(struct commit *item)\n {\ndiff --git a/log-tree.c b/log-tree.c\nindex fca29d4799..156aed4541 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -659,8 +659,7 @@ void show_log(struct rev_info *opt)\n \t\tshow_mergetag(opt, commit);\n \t}\n \n-\tif (!get_cached_commit_buffer(commit, NULL))\n-\t\treturn;\n+\tget_commit_buffer(commit, NULL);\n \n \tif (opt->show_notes) {\n \t\tint raw;\ndiff --git a/packed-graph.c b/packed-graph.c\nindex 5723f163ae..343b231973 100644\n--- a/packed-graph.c\n+++ b/packed-graph.c\n@@ -34,6 +34,8 @@\n #define GRAPH_CHUNKLOOKUP_SIZE (5 * 12)\n #define GRAPH_MIN_SIZE (GRAPH_CHUNKLOOKUP_SIZE + GRAPH_FANOUT_SIZE + \\\n \t\t\tGRAPH_OID_LEN + sizeof(struct packed_graph_header))\n+/* global storage */\n+struct packed_graph *packed_graph = 0;\n \n struct object_id *get_graph_head_oid(const char *pack_dir, struct object_id *oid)\n {\n@@ -209,6 +211,225 @@ struct packed_graph *load_packed_graph_one(const char *graph_file, const char *p\n \treturn graph;\n }\n \n+static void prepare_packed_graph_one(const char *obj_dir)\n+{\n+\tchar *graph_file;\n+\tstruct object_id oid;\n+\tstruct strbuf pack_dir = STRBUF_INIT;\n+\tstrbuf_addstr(&pack_dir, obj_dir);\n+\tstrbuf_add(&pack_dir, \"/pack\", 5);\n+\n+\tif (!get_graph_head_oid(pack_dir.buf, &oid))\n+\t\treturn;\n+\n+\tgraph_file = get_graph_filename_oid(pack_dir.buf, &oid);\n+\n+\tpacked_graph = load_packed_graph_one(graph_file, pack_dir.buf);\n+\tstrbuf_release(&pack_dir);\n+}\n+\n+static int prepare_packed_graph_run_once = 0;\n+void prepare_packed_graph(void)\n+{\n+\tstruct alternate_object_database *alt;\n+\tchar *obj_dir;\n+\n+\tif (prepare_packed_graph_run_once)\n+\t\treturn;\n+\tprepare_packed_graph_run_once = 1;\n+\n+\tobj_dir = get_object_directory();\n+\tprepare_packed_graph_one(obj_dir);\n+\tprepare_alt_odb();\n+\tfor (alt = alt_odb_list; !packed_graph && alt; alt = alt->next)\n+\t\tprepare_packed_graph_one(alt->path);\n+}\n+\n+static int bsearch_graph(struct packed_graph *g, struct object_id *oid, uint32_t *pos)\n+{\n+\tuint32_t last, first = 0;\n+\n+\tif (oid->hash[0])\n+\t\tfirst = ntohl(*(uint32_t*)(g->chunk_oid_fanout + 4 * (oid->hash[0] - 1)));\n+\tlast = ntohl(*(uint32_t*)(g->chunk_oid_fanout + 4 * oid->hash[0]));\n+\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tconst unsigned char *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = g->chunk_oid_lookup + g->hdr->hash_len * mid;\n+\t\tcmp = hashcmp(oid->hash, current);\n+\t\tif (!cmp) {\n+\t\t\t*pos = mid;\n+\t\t\treturn 1;\n+\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\t*pos = first;\n+\treturn 0;\n+}\n+\n+struct object_id *get_nth_commit_oid(struct packed_graph *g,\n+\t\t\t\t\t uint32_t n,\n+\t\t\t\t\t struct object_id *oid)\n+{\n+\thashcpy(oid->hash, g->chunk_oid_lookup + g->hdr->hash_len * n);\n+\treturn oid;\n+}\n+\n+static int full_parse_commit(struct commit *item, struct packed_graph *g,\n+\t\t\t uint32_t pos, const unsigned char *commit_data)\n+{\n+\tstruct object_id oid;\n+\tstruct commit *new_parent;\n+\tuint32_t new_parent_pos;\n+\tuint32_t *parent_data_ptr;\n+\tuint64_t date_low, date_high;\n+\tstruct commit_list **pptr;\n+\n+\titem->object.parsed = 1;\n+\titem->graphId = pos;\n+\n+\thashcpy(oid.hash, commit_data);\n+\titem->tree = lookup_tree(&oid);\n+\n+\tdate_high = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 8));\n+\tdate_low = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 12));\n+\titem->date = (timestamp_t)((date_high << 32) | date_low);\n+\n+\tpptr = &item->parents;\n+\n+\t// First Parent\n+\tnew_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len));\n+\tif (new_parent_pos == GRAPH_PARENT_NONE)\n+\t\treturn 1;\n+\tget_nth_commit_oid(g, new_parent_pos, &oid);\n+\tnew_parent = lookup_commit(&oid);\n+\tif (new_parent) {\n+\t\tnew_parent->graphId = new_parent_pos;\n+\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n+\t} else {\n+\t\tdie(\"could not find commit %s\", oid_to_hex(&oid));\n+\t}\n+\n+\t// Second Parent\n+\tnew_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 4));\n+\tif (new_parent_pos == GRAPH_PARENT_NONE)\n+\t\treturn 1;\n+\tif (!(new_parent_pos & GRAPH_LARGE_EDGES_NEEDED)) {\n+\t\tget_nth_commit_oid(g, new_parent_pos, &oid);\n+\t\tnew_parent = lookup_commit(&oid);\n+\t\tif (new_parent) {\n+\t\t\tnew_parent->graphId = new_parent_pos;\n+\t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n+\t\t} else\n+\t\t\tdie(\"could not find commit %s\", oid_to_hex(&oid));\n+\t\treturn 1;\n+\t}\n+\n+\tparent_data_ptr = (uint32_t*)(g->chunk_large_edges + 4 * (new_parent_pos ^ GRAPH_LARGE_EDGES_NEEDED));\n+\tdo {\n+\t\tnew_parent_pos = ntohl(*parent_data_ptr);\n+\n+\t\tget_nth_commit_oid(g, new_parent_pos & GRAPH_EDGE_LAST_MASK, &oid);\n+\t\tnew_parent = lookup_commit(&oid);\n+\t\tif (new_parent) {\n+\t\t\tnew_parent->graphId = new_parent_pos & GRAPH_EDGE_LAST_MASK;\n+\t\t\tpptr = &commit_list_insert(new_parent, pptr)->next;\n+\t\t} else\n+\t\t\tdie(\"could not find commit %s\", oid_to_hex(&oid));\n+\t\tparent_data_ptr++;\n+\t} while (!(new_parent_pos & GRAPH_LAST_EDGE));\n+\n+\treturn 1;\n+}\n+\n+/**\n+ * Fill 'item' to contain all information that would be parsed by parse_commit_buffer.\n+ */\n+static int fill_packed_commit(struct commit *item, struct packed_graph *g, uint32_t pos)\n+{\n+\tuint32_t new_parent_pos;\n+\tuint32_t *parent_data_ptr;\n+\tconst unsigned char *commit_data = g->chunk_commit_data + (g->hdr->hash_len + 16) * pos;\n+\n+\t// Determine if we have ALL of our edges, otherwise we will return as unparsed.\n+\n+\t// Check constant-width parents first.\n+\tnew_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len));\n+\n+\tif (new_parent_pos == GRAPH_PARENT_MISSING)\n+\t\treturn 0;\n+\n+\tif (new_parent_pos == GRAPH_PARENT_NONE)\n+\t\treturn full_parse_commit(item, g, pos, commit_data);\n+\n+\tnew_parent_pos = ntohl(*(uint32_t*)(commit_data + g->hdr->hash_len + 4));\n+\n+\tif (new_parent_pos == GRAPH_PARENT_MISSING)\n+\t\treturn 0;\n+\tif (!(new_parent_pos & GRAPH_LARGE_EDGES_NEEDED))\n+\t\treturn full_parse_commit(item, g, pos, commit_data);\n+\n+\tnew_parent_pos = new_parent_pos ^ GRAPH_LARGE_EDGES_NEEDED;\n+\n+\tif (new_parent_pos == GRAPH_PARENT_MISSING)\n+\t\treturn 0;\n+\n+\tparent_data_ptr = (uint32_t*)(g->chunk_large_edges + 4 * new_parent_pos);\n+\tdo {\n+\t\tnew_parent_pos = ntohl(*parent_data_ptr);\n+\n+\t\tif ((new_parent_pos & GRAPH_EDGE_LAST_MASK) == GRAPH_PARENT_MISSING)\n+\t\t\treturn 0;\n+\n+\t\tparent_data_ptr++;\n+\t} while (!(new_parent_pos & GRAPH_LAST_EDGE));\n+\n+\treturn full_parse_commit(item, g, pos, commit_data);\n+}\n+\n+/**\n+ * Given a commit struct, try to fill the commit struct info, including:\n+ * 1. tree object\n+ * 2. date\n+ * 3. parents.\n+ *\n+ * Returns 1 iff the commit was found in the packed graph.\n+ *\n+ * See parse_commit_buffer() for the fallback after this call.\n+ */\n+int parse_packed_commit(struct commit *item)\n+{\n+\tif (!core_graph)\n+\t\treturn 0;\n+\tif (item->object.parsed)\n+\t\treturn 1;\n+\n+\tprepare_packed_graph();\n+\tif (packed_graph) {\n+\t\tuint32_t pos;\n+\t\tint found;\n+\t\tif (item->graphId != 0xFFFFFFFF) {\n+\t\t\tpos = item->graphId;\n+\t\t\tfound = 1;\n+\t\t} else {\n+\t\t\tfound = bsearch_graph(packed_graph, &(item->object.oid), &pos);\n+\t\t}\n+\n+\t\tif (found)\n+\t\t\treturn fill_packed_commit(item, packed_graph, pos);\n+\t}\n+\n+\treturn parse_commit_internal(item, 0, 0);\n+}\n+\n static void write_graph_chunk_fanout(\n \tstruct sha1file *f,\n \tstruct commit **commits, int nr_commits)\n@@ -439,9 +660,24 @@ struct object_id *construct_graph(const char *pack_dir)\n \tif (!core_graph)\n \t\treturn 0;\n \n+\tprepare_packed_graph();\n+\n \toids.num = 0;\n \toids.size = 1024;\n+\n+\tif (packed_graph && oids.size < packed_graph->num_commits)\n+\t\toids.size = packed_graph->num_commits;\n+\n \tALLOC_ARRAY(oids.list, oids.size);\n+\n+\tif (packed_graph) {\n+\t\tfor (i = 0; i < packed_graph->num_commits; i++) {\n+\t\t\toids.list[i] = malloc(sizeof(struct object_id));\n+\t\t\tget_nth_commit_oid(packed_graph, i, oids.list[i]);\n+\t\t}\n+\t\toids.num = packed_graph->num_commits;\n+\t}\n+\n \tfor_each_packed_object(if_packed_commit_add_to_list, &oids, 0);\n \tQSORT(oids.list, oids.num, commit_compare);\n \n@@ -530,6 +766,11 @@ struct object_id *construct_graph(const char *pack_dir)\n \thashcpy(f_oid->hash, final_hash);\n \tfname = get_graph_filename_oid(pack_dir, f_oid);\n \n+\tif (packed_graph) {\n+\t\tclose_graph(packed_graph);\n+\t\tFREE_AND_NULL(packed_graph);\n+\t}\n+\n \tif (rename(graph_name, fname))\n \t\tdie(\"failed to rename %s to %s\", graph_name, fname);\n \n@@ -539,3 +780,4 @@ struct object_id *construct_graph(const char *pack_dir)\n \n \treturn f_oid;\n }\n+\ndiff --git a/packed-graph.h b/packed-graph.h\nindex ad561863c8..6010ce3e53 100644\n--- a/packed-graph.h\n+++ b/packed-graph.h\n@@ -4,6 +4,18 @@\n #include \"git-compat-util.h\"\n #include \"commit.h\"\n \n+/**\n+ * Given a commit struct, try to fill the commit struct info, including:\n+ * 1. tree object\n+ * 2. date\n+ * 3. parents.\n+ *\n+ * Returns 1 iff the commit was found in the packed graph.\n+ *\n+ * See parse_commit_buffer() for the fallback after this call.\n+ */\n+extern int parse_packed_commit(struct commit *item);\n+\n extern struct object_id *get_graph_head_oid(const char *pack_dir, struct object_id *oid);\n extern char* get_graph_filename_oid(const char *pack_dir,\n \t\t\t\t struct object_id *oid);\n@@ -40,7 +52,13 @@ extern struct packed_graph {\n extern int close_graph(struct packed_graph *g);\n \n extern struct packed_graph *load_packed_graph_one(const char *graph_file, const char *pack_dir);\n+extern void prepare_packed_graph(void);\n+\n+extern struct object_id *get_nth_commit_oid(struct packed_graph *g,\n+\t\t\t\t\t uint32_t n,\n+\t\t\t\t\t struct object_id *oid);\n \n extern struct object_id *construct_graph(const char *pack_dir);\n+extern int close_graph(struct packed_graph *g);\n \n #endif\ndiff --git a/t/t5319-graph.sh b/t/t5319-graph.sh\nindex a70c7bbb02..4552795179 100755\n--- a/t/t5319-graph.sh\n+++ b/t/t5319-graph.sh\n@@ -26,6 +26,23 @@ test_expect_success 'create commits and repack' \\\n done &&\n git repack'\n \n+_graph_git_two_modes() {\n+ git -c core.graph=true $1 >output\n+ git -c core.graph=false $1 >expect\n+ cmp output expect\n+}\n+\n+_graph_git_behavior() {\n+ test_expect_success 'check normal git operations' \\\n+ '_graph_git_two_modes \"log --oneline master\" &&\n+ _graph_git_two_modes \"log --topo-order master\" &&\n+ _graph_git_two_modes \"log --graph $1 $2\" &&\n+ _graph_git_two_modes \"branch -vv\" &&\n+ _graph_git_two_modes \"merge-base -a $1 $2\"'\n+}\n+\n+_graph_git_behavior commits/3 commits/4\n+\n _graph_read_expect() {\n cat >expect <<- EOF\n header: 43475048 01 01 14 04\n@@ -43,6 +60,8 @@ test_expect_success 'write graph' \\\n _graph_read_expect \"5\" \"${packdir}\" &&\n cmp expect output'\n \n+_graph_git_behavior commits/3 commits/4\n+\n test_expect_success 'Add more commits' \\\n 'git reset --hard commits/3 &&\n for i in $(test_seq 6 10)\n@@ -52,7 +71,7 @@ test_expect_success 'Add more commits' \\\n git commit -m \"commit $i\" &&\n git branch commits/$i\n done &&\n- git reset --hard commits/7 &&\n+ git reset --hard commits/3 &&\n for i in $(test_seq 11 15)\n do\n echo $i >$i.txt &&\n@@ -61,15 +80,40 @@ test_expect_success 'Add more commits' \\\n git branch commits/$i\n done &&\n git reset --hard commits/7 &&\n- git merge commits/4 &&\n+ git merge commits/11 &&\n git branch merge/1 &&\n git reset --hard commits/8 &&\n- git merge commits/11 &&\n+ git merge commits/12 &&\n git branch merge/2 &&\n- git reset --hard commits/9 &&\n- git merge commits/5 commits/13 &&\n+ git reset --hard commits/5 &&\n+ git merge commits/10 commits/15 &&\n+ git branch merge/3 &&\n git repack'\n \n+# Current graph structure:\n+#\n+# M3\n+# / |\\_____\n+# / 10 15\n+# / | |\n+# / 9 M2 14\n+# | |/ \\ \\|\n+# | 8 M1 | 13\n+# | |/ | \\_|\n+# 5 7 | 12\n+# | | \\__|\n+# 4 6 11\n+# |____/______/\n+# 3\n+# |\n+# 2\n+# |\n+# 1\n+\n+_graph_git_behavior merge/1 merge/2\n+_graph_git_behavior merge/1 merge/3\n+_graph_git_behavior merge/2 merge/3\n+\n test_expect_success 'write graph with merges' \\\n 'graph2=$(git graph --write --update-head) &&\n test_path_is_file ${packdir}/graph-${graph2}.graph &&\n@@ -80,15 +124,54 @@ test_expect_success 'write graph with merges' \\\n _graph_read_expect \"18\" \"${packdir}\" &&\n cmp expect output'\n \n+_graph_git_behavior merge/1 merge/2\n+_graph_git_behavior merge/1 merge/3\n+_graph_git_behavior merge/2 merge/3\n+\n test_expect_success 'Add more commits' \\\n- 'git reset --hard commits/3 &&\n- for i in $(test_seq 16 20)\n+ 'for i in $(test_seq 16 20)\n do\n- git commit --allow-empty -m \"commit $i\" &&\n+ echo $i >$i.txt &&\n+ git add $i.txt &&\n+ git commit -m \"commit $i\" &&\n git branch commits/$i\n done &&\n git repack'\n \n+# Current graph structure:\n+#\n+# 20\n+# |\n+# 19\n+# |\n+# 18\n+# |\n+# 17\n+# |\n+# 16\n+# |\n+# M3\n+# / |\\_____\n+# / 10 15\n+# / | |\n+# / 9 M2 14\n+# | |/ \\ \\|\n+# | 8 M1 | 13\n+# | |/ | \\_|\n+# 5 7 | 12\n+# | | \\__|\n+# 4 6 11\n+# |____/______/\n+# 3\n+# |\n+# 2\n+# |\n+# 1\n+\n+# Test behavior while in mixed mode\n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'write graph with merges' \\\n 'graph3=$(git graph --write --update-head --delete-expired) &&\n test_path_is_file ${packdir}/graph-${graph3}.graph &&\n@@ -101,6 +184,9 @@ test_expect_success 'write graph with merges' \\\n _graph_read_expect \"23\" \"${packdir}\" &&\n cmp expect output'\n \n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'write graph with nothing new' \\\n 'graph4=$(git graph --write --update-head --delete-expired) &&\n test_path_is_file ${packdir}/graph-${graph4}.graph &&\n@@ -112,12 +198,18 @@ test_expect_success 'write graph with nothing new' \\\n _graph_read_expect \"23\" \"${packdir}\" &&\n cmp expect output'\n \n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'clear graph' \\\n 'git graph --clear &&\n test_path_is_missing ${packdir}/graph-${graph3}.graph &&\n test_path_is_file ${packdir}/graph-${graph1}.graph &&\n test_path_is_missing ${packdir}/graph-head'\n \n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'setup bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n@@ -126,6 +218,9 @@ test_expect_success 'setup bare repo' \\\n git config pack.threads 1 &&\n baredir=\"./objects/pack\"'\n \n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_expect_success 'write graph in bare repo' \\\n 'graphbare=$(git graph --write --update-head) &&\n test_path_is_file ${baredir}/graph-${graphbare}.graph &&\n@@ -136,4 +231,7 @@ test_expect_success 'write graph in bare repo' \\\n _graph_read_expect \"23\" \"${baredir}\" &&\n cmp expect output'\n \n+_graph_git_behavior commits/20 merge/1\n+_graph_git_behavior commits/20 merge/2\n+\n test_done\n-- \n2.16.0\n\n"},{"id":"337384","messageId":"871siex7pc.fsf@evledraar.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-1-dstolee@microsoft.com","subject":"Re: [PATCH 00/14] Serialized Commit Graph","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-25T15:46:07Z","receivedAt":"2018-01-25T15:46:16Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jan 25 2018, Derrick Stolee jotted:\n\n> * 'git log --topo-order -1000' walks all reachable commits to avoid\n> incorrect topological orders, but only needs the commit message for\n> the top 1000 commits.\n>\n> * 'git merge-base ' may walk many commits to find the correct\n> boundary between the commits reachable from A and those reachable\n> from B. No commit messages are needed.\n>\n> * 'git branch -vv' checks ahead/behind status for all local branches\n> compared to their upstream remote branches. This is essentially as\n> hard as computing merge bases for each.\n\nThis is great, spotted / questions so far:\n\n* git graph --blah says you need to enable the config, should say\n \"unknown option --blah \". I.e. overzelous config guard.\n\n* On a big repo (git show-ref -s | ~/g/git/git-graph --write\n --update-head) is as of writing this still hanging for me, but strace\n shows it's brk()-ing. Presumably just still busy, a progress bar would\n be very nice.\n\n* Shouldn't there be a pack.useGraph option so this gets auto-updated on\n repack? I understand this series is a WIP, so that's more a \"is that\n the UI\" than \"it needs now\".\n"},{"id":"337385","messageId":"fe9d20da-eb70-d725-0530-cab1c029a0c8@gmail.com","threadId":"47690","inReplyTo":"871siex7pc.fsf@evledraar.gmail.com","subject":"Re: [PATCH 00/14] Serialized Commit Graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T16:09:56Z","receivedAt":"2018-01-25T16:10:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 10:46 AM, Ævar Arnfjörð Bjarmason wrote:\n> On Thu, Jan 25 2018, Derrick Stolee jotted:\n>\n>> * 'git log --topo-order -1000' walks all reachable commits to avoid\n>> incorrect topological orders, but only needs the commit message for\n>> the top 1000 commits.\n>>\n>> * 'git merge-base ' may walk many commits to find the correct\n>> boundary between the commits reachable from A and those reachable\n>> from B. No commit messages are needed.\n>>\n>> * 'git branch -vv' checks ahead/behind status for all local branches\n>> compared to their upstream remote branches. This is essentially as\n>> hard as computing merge bases for each.\n> This is great, spotted / questions so far:\n>\n> * git graph --blah says you need to enable the config, should say\n> \"unknown option --blah \". I.e. overzelous config guard.\n\nThis is a good point.\n\n> * On a big repo (git show-ref -s | ~/g/git/git-graph --write\n> --update-head) is as of writing this still hanging for me, but strace\n> shows it's brk()-ing. Presumably just still busy, a progress bar would\n> be very nice.\n\nOops! This is my mistake. The correct command should be:\n\n     git show-ref -s | git graph --write --update-head --stdin-commits\n\nWithout \"--stdin-commits\" the command will walk all packed objects\nto look for commits and then build the graph. That's why it's taking\nso long. That method takes several minutes on the Linux repo, but with\n--stdin-commits it should take as long as \"git log >/dev/null\".\n\n> * Shouldn't there be a pack.useGraph option so this gets auto-updated on\n> repack? I understand this series is a WIP, so that's more a \"is that\n> the UI\" than \"it needs now\".\n\nThis will definitely be part of a follow-up patch.\n\nThanks,\n-Stolee\n"},{"id":"337400","messageId":"CAGZ79kbVoJpP3d_jgJ9Ekn=9NBMaKVNoapjygz7BxABxP2dCBg@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-2-dstolee@microsoft.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T20:04:45Z","receivedAt":"2018-01-25T20:04:52Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> Add Documentation/technical/packed-graph.txt with details of the planned\n> packed graph feature, including future plans.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++\n> 1 file changed, 185 insertions(+)\n> create mode 100644 Documentation/technical/packed-graph.txt\n>\n> diff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt\n> new file mode 100644\n> index 0000000000..fcc0c83874\n> --- /dev/null\n> +++ b/Documentation/technical/packed-graph.txt\n> @@ -0,0 +1,185 @@\n> +Git Packed Graph Design Notes\n> +=============================\n> +\n> +Git walks the commit graph for many reasons, including:\n> +\n> +1. Listing and filtering commit history.\n> +2. Computing merge bases.\n> +\n> +These operations can become slow as the commit count grows above 100K.\n\nHow did you come up with that specific number? (Is it platform dependent?)\nI'd avoid a specific number to not derail the reader here into wondering\nhow this got measured.\n\n> +The merge base calculation shows up in many user-facing commands, such\n> +as 'status' and 'fetch' and can take minutes to compute depending on\n> +data shape. There are two main costs here:\n\nstatus needs the walk for the ahead/behind computation which is (1)?\n(I forget how status would need to compute a merge-base)\n\nfetch is a networked command, which traditionally in Git is understood as\n\"can be slow\" because you might be in Australia, or the connection is slow\notherwise. So giving this as an example it is not obvious that the DAG walking\nis the bottleneck. Maybe git-merge or \"git show --remerge-diff\" [1] are better\nexamples for walk-intensive commands?\n\n[1] https://public-inbox.org/git/cover.1409860234.git.tr@thomasrast.ch/\n never landed, so maybe that is a bad example. But for me that command\n is more obviously dependent on cheap walking the DAG compared to fetch.\n So, take my comments with a grain of salt!\n\n> +1. Decompressing and parsing commits.\n> +2. Walking the entire graph to avoid topological order mistakes.\n> +\n> +The packed graph is a file that stores the commit graph structure along\n> +with some extra metadata to speed up graph walks. This format allows a\n> +consumer to load the following info for a commit:\n> +\n> +1. The commit OID.\n> +2. The list of parents.\n> +3. The commit date.\n> +4. The root tree OID.\n> +5. An integer ID for fast lookups in the graph.\n> +6. The generation number (see definition below).\n> +\n> +Values 1-4 satisfy the requirements of parse_commit_gently().\n\n\nThis new format is specifically removing the cost of decompression and parsing\n(1) completely, whereas (2) we still have to walk the entire graph for now as\nthe generation numbers are not fully used as of yet, but provided.\n\n> +By providing an integer ID we can avoid lookups in the graph as we walk\n> +commits. Specifically, we need to provide the integer ID of the parent\n> +commits so we navigate directly to their information on request.\n\nDoes this mean we decrease the pressure on fast lookups in\npackfiles/loose objects?\n\n> +Define the \"generation number\" of a commit recursively as follows:\n> + * A commit with no parents (a root commit) has generation number 1.\n> + * A commit with at least one parent has generation number 1 more than\n> + the largest generation number among its parents.\n> +Equivalently, the generation number is one more than the length of a\n> +longest path from the commit to a root commit. The recursive definition\n> +is easier to use for computation and the following property:\n> +\n> + If A and B are commits with generation numbers N and M, respectively,\n> + and N <= M, then A cannot reach B. That is, we know without searching\n> + that B is not an ancestor of A because it is further from a root commit\n> + than A.\n> +\n> + Conversely, when checking if A is an ancestor of B, then we only need\n> + to walk commits until all commits on the walk boundary have generation\n> + number at most N. If we walk commits using a priority queue seeded by\n> + generation numbers, then we always expand the boundary commit with highest\n> + generation number and can easily detect the stopping condition.\n\nThanks for including the definition and potential benefits!\n\n> +\n> +This property can be used to significantly reduce the time it takes to\n> +walk commits and determine topological relationships. Without generation\n> +numbers, the general heuristic is the following:\n> +\n> + If A and B are commits with commit time X and Y, respectively, and\n> + X < Y, then A _probably_ cannot reach B.\n> +\n> +This heuristic is currently used whenever the computation can make\n> +mistakes with topological orders (such as \"git log\" with default order),\n> +but is not used when the topological order is required (such as merge\n> +base calculations, \"git log --graph\").\n> +\n> +Design Details\n> +--------------\n> +\n> +- A graph file is stored in a file named 'graph-.graph' in the pack\n> + directory.\n\n(guessing)\nwhere every commit up to is included in the file.\n\n> This could be stored in an alternate.\n\nSo I can 'borrow' not just the objects itself, but also the file about object\nproperties from an alternate. Makes sense, though I wonder if it is\nworth stating\nthis as the first bullet point in the design detail section?\n\n> +- The most-recent graph file OID is stored in a 'graph-head' file for\n> + immediate access and storing backup graphs. This could be stored in an\n> + alternate, and refers to a 'graph-.graph' file in the same pack\n> + directory.\n\nSo we have two copies of the latest in both 'graph-head.graph'\nas well as 'graph-.graph'? Would a link be ok? So instead\nwe might have a 'graph-head.link' file that just contains 'oid: ' ?\n\nBut then again, we can get the oid from HEAD, and these graph files\ncan contain all information up to multiple tips (i.e. there is just one graph\nfile needed, even if you have 2 branches, neither of them to be\nfast-forwardable to the other).\n\nSo maybe I do not understand the after all, yet.\n\n> +- The core.graph config setting must be on to create or consume graph files.\n\nWe already have other local files that speed up things, such as idx files.\nSearching our config options for \"idx\" I find 'pack.indexVersion', which\nonly controls the write side of idx. Reading idx seems automatic if they are\nthere, otherwise we fallback to non-idx.\n\nBy having the setting a boolean we cannot control the version yet, but we can\nlater upgrade the config to a boolean-or-int that specifies which graph\nversion is written out.\n\nWhy do we need this config option to control the reading side as well?\nAFAICT the user can just delete all graphs if the graphs make problems and\nthen regenerate them if git is too slow?\n\nAs these files need to be manually generated as of this series, I'd further\nargue that the reading should be unguarded by the config option.\n\n> +- The graph file is only a supplemental structure. If a user downgrades\n> + or disables the 'core.graph' config setting, then the existing ODB is\n> + sufficient.\n\n(Maybe mention idx files as a comparable design?)\n\n> +- The file format includes parameters for the object id length\n> + and hash algorithm, so a future change of hash algorithm does\n> + not require a change in format.\n\nCool.\n\n> +\n> +Current Limitations\n> +-------------------\n> +\n> +- Only one graph file is used at one time. This allows the integer ID to\n> + seek into the single graph file. It is possible to extend the model\n> + for multiple graph files, but that is currently not part of the design.\n> +\n> +- .graph files are managed only by the 'graph' builtin. These are not\n> + updated automatically during clone or fetch.\n> +\n> +- There is no '--verify' option for the 'graph' builtin to verify the\n> + contents of the graph file.\n\nc.f. git index-pack --verify (which is not documented :/)\n\n> +- The graph only considers commits existing in packfiles and does not\n> + walk to fill in reachable commits. [Small]\n\nsmall?\n\n> +- When rewriting the graph, we do not check for a commit still existing\n> + in the ODB, so garbage collection may remove commits\n> +\n> +- Generation numbers are not computed in the current version. The file\n> + format supports storing them, along with a mechanism to upgrade from\n> + a file without generation numbers to one that uses them.\n\nMaybe move the definition and explanation of the generation numbers above to\nthe \"Future Work\" section?\n\n\n> +\n> +Future Work\n> +-----------\n> +\n> +- The file format includes room for precomputed generation numbers. These\n> + are not currently computed, so all generation numbers will be marked as\n> + 0 (or \"uncomputed\"). A later patch will include this calculation.\n> +\n> +- The current implementation of the 'graph' builtin walks all packed objects\n> + to find a complete list of commits in packfiles. If some commits are\n> + stored as loose objects, then these do not appear in the graph. This is\n> + handled gracefully by the file format, but it would cause incorrect\n> + generation number calculations. We should implement the construct_graph()\n> + method in a way that walks all commits reachable from some starting set\n> + and then can use complete information for generation numbers. (Some\n> + care must be taken around shallow clones.)\n> +\n> +- The graph is not currently integrated with grafts.\n\nnot integrated? Does that mean we error out on grafts, or gracefully fallback\nto a sane thing?\n\n> +- After computing and storing generation numbers, we must make graph\n> + walks aware of generation numbers to gain performance benefits. This\n> + will mostly be accomplished by swapping a commit-date-ordered priority\n> + queue with one ordered by generation number. The following operations\n> + are important candidates:\n> +\n> + - paint_down_to_common()\n> + - 'log --topo-order'\n> +\n> +- The graph currently only adds commits to a previously existing graph.\n> + When writing a new graph, we could check that the ODB still contains\n> + the commits and choose to remove the commits that are deleted from the\n> + ODB. For performance reasons, this check should remain optional.\n> +\n> +- Currently, parse_commit_gently() requires filling in the root tree\n> + object for a commit. This passes through lookup_tree() and consequently\n> + lookup_object(). Also, it calls lookup_commit() when loading the parents.\n> + These method calls check the ODB for object existence, even if the\n> + consumer does not need the content. For example, we do not need the\n> + tree contents when computing merge bases. Now that commit parsing is\n> + removed from the computation time, these lookup operations are the\n> + slowest operations keeping graph walks from being fast. Consider\n> + loading these objects without verifying their existence in the ODB and\n> + only loading them fully when consumers need them. Consider a method\n> + such as \"ensure_tree_loaded(commit)\" that fully loads a tree before\n> + using commit->tree.\n> +\n> +- The current design uses the 'graph' builtin to generate the graph. When\n> + this feature stabilizes enough to recommend to most users, we should\n> + add automatic graph writes to common operations that create many commits.\n> + For example, one coulde compute a graph on 'clone' and 'fetch' commands.\n\ntypo \"could\"\n\nOnce we have incrementally-update-able graphs, we certainly want commit/merge\nto also write out updates? (or batch them after a long rebase).\n\nThanks,\nStefan\n"},{"id":"337402","messageId":"CAGZ79kbUr-iQghL8qXxCq7noiYR9-MrxmTB4_v3D7WyXLPwUjA@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-3-dstolee@microsoft.com","subject":"Re: [PATCH 02/14] packed-graph: add core.graph setting","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T20:17:04Z","receivedAt":"2018-01-25T20:17:10Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> The packed graph feature is controlled by the new core.graph config\n> setting. This defaults to 0, so the feature is opt-in.\n>\n> The intention of core.graph is that a user can always stop checking\n> for or parsing packed graph files if core.graph=0.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/config.txt | 3 +++\n> cache.h | 1 +\n> config.c | 5 +++++\n> environment.c | 1 +\n> 4 files changed, 10 insertions(+)\n>\n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index 0e25b2c92b..e7b98fa14f 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -898,6 +898,9 @@ core.notesRef::\n> This setting defaults to \"refs/notes/commits\", and it can be overridden by\n> the `GIT_NOTES_REF` environment variable. See linkgit:git-notes[1].\n>\n> +core.graph::\n> + Enable git commit graph feature. Allows writing and reading from .graph files.\n> +\n> core.sparseCheckout::\n> Enable \"sparse checkout\" feature. See section \"Sparse checkout\" in\n> linkgit:git-read-tree[1] for more information.\n> diff --git a/cache.h b/cache.h\n> index d8b975a571..655a81ac90 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -825,6 +825,7 @@ extern char *git_replace_ref_base;\n> extern int fsync_object_files;\n> extern int core_preload_index;\n> extern int core_apply_sparse_checkout;\n> +extern int core_graph;\n\nPutting it here instead of say the_repository makes sense as you'd want\nto use this feature globally. However you can still have the config\ndifferent per repository (e.g. version number of the graph setting,\nas one might be optimized for speed and the other for file size of\nthe .graph file or such).\n\nSo not sure if we'd rather want to put this into the repository struct.\nBut then again the other core settings aren't there either and this\nfeature sounds like it is repository specific only in the experimental\nphase; later it is expected to be on everywhere?\n\n> extern int precomposed_unicode;\n> extern int protect_hfs;\n> extern int protect_ntfs;\n> diff --git a/config.c b/config.c\n> index e617c2018d..fee90912d8 100644\n> --- a/config.c\n> +++ b/config.c\n> @@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)\n> return 0;\n> }\n>\n> + if (!strcmp(var, \"core.graph\")) {\n> + core_graph = git_config_bool(var, value);\n> + return 0;\n> + }\n> +\n> if (!strcmp(var, \"core.sparsecheckout\")) {\n> core_apply_sparse_checkout = git_config_bool(var, value);\n> return 0;\n> diff --git a/environment.c b/environment.c\n> index 63ac38a46f..0c56a3d869 100644\n> --- a/environment.c\n> +++ b/environment.c\n> @@ -61,6 +61,7 @@ enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;\n> char *notes_ref_name;\n> int grafts_replace_parents = 1;\n> int core_apply_sparse_checkout;\n> +int core_graph;\n> int merge_log_config = -1;\n> int precomposed_unicode = -1; /* see probe_utf8_pathname_composition() */\n> unsigned long pack_size_limit_cfg;\n> --\n> 2.16.0\n>\n"},{"id":"337406","messageId":"d69b7eab-0aa2-6fed-7750-2fdf1ac8269f@gmail.com","threadId":"47690","inReplyTo":"CAGZ79kbUr-iQghL8qXxCq7noiYR9-MrxmTB4_v3D7WyXLPwUjA@mail.gmail.com","subject":"Re: [PATCH 02/14] packed-graph: add core.graph setting","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-25T20:40:12Z","receivedAt":"2018-01-25T20:40:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 3:17 PM, Stefan Beller wrote:\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>> The packed graph feature is controlled by the new core.graph config\n>> setting. This defaults to 0, so the feature is opt-in.\n>>\n>> The intention of core.graph is that a user can always stop checking\n>> for or parsing packed graph files if core.graph=0.\n>>\n>> @@ -825,6 +825,7 @@ extern char *git_replace_ref_base;\n>> extern int fsync_object_files;\n>> extern int core_preload_index;\n>> extern int core_apply_sparse_checkout;\n>> +extern int core_graph;\n> Putting it here instead of say the_repository makes sense as you'd want\n> to use this feature globally. However you can still have the config\n> different per repository (e.g. version number of the graph setting,\n> as one might be optimized for speed and the other for file size of\n> the .graph file or such).\n>\n> So not sure if we'd rather want to put this into the repository struct.\n> But then again the other core settings aren't there either and this\n> feature sounds like it is repository specific only in the experimental\n> phase; later it is expected to be on everywhere?\n\nI do think that more things should go in the repository struct. \nUnfortunately, that is not the world we live in.\n\nHowever, to make things clearer I'm following the pattern currently in \nmaster. You'll see the same with the global 'packed_graph' pointer, \nsimilar to 'packed_git'. I think these should be paired together until \nthe repository absorbs them.\n\nIf other 'core_*' variables move to the repository, I'm happy to move \ncore_graph.\nIf 'packed_git' moves to the repository, I'm happy to move 'packed_git'.\n\nHowever, if there is significant interest in moving all new state to the \nrepository, then I'll move these values there. Let's have that \ndiscussion here instead of spread around the rest of the patch.\n\nThanks,\n-Stolee\n\n"},{"id":"337408","messageId":"xmqqzi518wu3.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"20180125140231.65604-2-dstolee@microsoft.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-25T21:14:44Z","receivedAt":"2018-01-25T21:14:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Add Documentation/technical/packed-graph.txt with details of the planned\n> packed graph feature, including future plans.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++\n> 1 file changed, 185 insertions(+)\n> create mode 100644 Documentation/technical/packed-graph.txt\n\nI really wanted to like having this patch at the beginning, but\nunfortunatelly I didn't see the actual file format description,\nwhich was a bit disappointing. An example of the things that I was\ncurious about was how the \"integer ID\" is used to access into the\nfile. If we could somehow use \"integer ID\" as an index into an\narray of fixed size elements, it would be ideal to gain \"fast\nlookups\", but because of the \"list of parents\" thing, it needs some\ntrickery to do so, and that was among the things that I wanted to\nsee how much thought went into the design, for example.\n\n> diff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt\n> new file mode 100644\n> index 0000000000..fcc0c83874\n> --- /dev/null\n> +++ b/Documentation/technical/packed-graph.txt\n> @@ -0,0 +1,185 @@\n> +Git Packed Graph Design Notes\n> +=============================\n> +\n> +Git walks the commit graph for many reasons, including:\n> +\n> +1. Listing and filtering commit history.\n> +2. Computing merge bases.\n> +\n> +These operations can become slow as the commit count grows above 100K.\n> +The merge base calculation shows up in many user-facing commands, such\n> +as 'status' and 'fetch' and can take minutes to compute depending on\n> +data shape. There are two main costs here:\n\ns/data shape/history shape/ may make it even clearer.\n\n> +1. The commit OID.\n> +2. The list of parents.\n> +3. The commit date.\n> +4. The root tree OID.\n> +5. An integer ID for fast lookups in the graph.\n> +6. The generation number (see definition below).\n> +\n> +Values 1-4 satisfy the requirements of parse_commit_gently().\n> +\n> +By providing an integer ID we can avoid lookups in the graph as we walk\n> +commits. Specifically, we need to provide the integer ID of the parent\n> +commits so we navigate directly to their information on request.\n\nCommits created after a packed graph file is built may of course not\nappear in a packed graph file, but that is OK because they never need\nto be listed as parents of commits in the file. So \"list of parents\"\ncan always refer to the parents using the \"integer ID for fast lookup\".\n\nMakes sense. Item 2. might want to say \"The list of parents, using\nthe fast lookup integer ID (see 5.) as reference instead of OID\",\nthough.\n\n> +Define the \"generation number\" of a commit recursively as follows:\n> + * A commit with no parents (a root commit) has generation number 1.\n> + * A commit with at least one parent has generation number 1 more than\n> + the largest generation number among its parents.\n> +Equivalently, the generation number is one more than the length of a\n> +longest path from the commit to a root commit.\n\nWhen a commit A can reach roots X and Y, and Y is further than X,\nthe distance between Y and A becomes A's generation number. \"One\nmore than the length of the path from the commit to the furthest\nroot commit it can reach\", in other words.\n\n> +The recursive definition\n> +is easier to use for computation and the following property:\n> +\n> + If A and B are commits with generation numbers N and M, respectively,\n> + and N <= M, then A cannot reach B. That is, we know without searching\n> + that B is not an ancestor of A because it is further from a root commit\n> + than A.\n> +\n> + Conversely, when checking if A is an ancestor of B, then we only need\n> + to walk commits until all commits on the walk boundary have generation\n> + number at most N. If we walk commits using a priority queue seeded by\n> + generation numbers, then we always expand the boundary commit with highest\n> + generation number and can easily detect the stopping condition.\n\nThese are both true. It would be nice if an optimized walker\nalgorithm can also deal with history with recent commits for which\nwe do not yet know the generation numbers (i.e. you first traverse\nand assign generation numbers and record in packed graph, then\nhistory grows but we haven't added the new commits to the packed\ngraph yet).\n\n> +- A graph file is stored in a file named 'graph-.graph' in the pack\n> + directory. This could be stored in an alternate.\n\nIs that really an object name? The that appears in the\nname of a packfile pack-.pack is *not* an , and I somehow\nsuspect that you are doing a similar \"use hash of (some) contents to\nmake it uniquely identify the content\", not \"information about a\nsingle object that is identified by the \".\n\n> +- The graph file is only a supplemental structure. If a user downgrades\n> + or disables the 'core.graph' config setting, then the existing ODB is\n> + sufficient.\n\nOK, that is exactly what I meant to say in a few paragraphs above\nthat I wanted to see.\n\n> +Current Limitations\n> +-------------------\n> +\n> +- Only one graph file is used at one time. This allows the integer ID to\n> + seek into the single graph file. It is possible to extend the model\n> + for multiple graph files, but that is currently not part of the design.\n> +\n> +- .graph files are managed only by the 'graph' builtin. These are not\n> + updated automatically during clone or fetch.\n\nIn addition to \"clone or fetch\", I presume operations that locally\ncreate commits do not automatically create them, right?\n\n> +- After computing and storing generation numbers, we must make graph\n> + walks aware of generation numbers to gain performance benefits. This\n> + will mostly be accomplished by swapping a commit-date-ordered priority\n> + queue with one ordered by generation number. The following operations\n> + are important candidates:\n> +\n> + - paint_down_to_common()\n> + - 'log --topo-order'\n\nDo you mean that this round only writes \"graph\" without any actualy\nconsumers? It is somewhat hard to assess the value of what is\nstored in the new file without the consumers.\n\nAnyway, thanks for starting this. Let's read on.\n\n"},{"id":"337410","messageId":"xmqqvafp8vib.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"20180125140231.65604-3-dstolee@microsoft.com","subject":"Re: [PATCH 02/14] packed-graph: add core.graph setting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-25T21:43:24Z","receivedAt":"2018-01-25T21:43:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> The packed graph feature is controlled by the new core.graph config\n> setting. This defaults to 0, so the feature is opt-in.\n>\n> The intention of core.graph is that a user can always stop checking\n> for or parsing packed graph files if core.graph=0.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/config.txt | 3 +++\n> cache.h | 1 +\n> config.c | 5 +++++\n> environment.c | 1 +\n> 4 files changed, 10 insertions(+)\n\nBefore you get too married to the name \"graph\", is it reasonable to\nassume that the commit ancestry graph is the primary \"graph\" that\nshould come to users' minds when a simple word \"graph\" is used in\nthe context of discussing Git? I suspect not.\n\nLet's not just call this \"core.graph\" and \"packed-graph\", and in\naddition give some adjective before \"graph\".\n\n\n\n\n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index 0e25b2c92b..e7b98fa14f 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -898,6 +898,9 @@ core.notesRef::\n> This setting defaults to \"refs/notes/commits\", and it can be overridden by\n> the `GIT_NOTES_REF` environment variable. See linkgit:git-notes[1].\n> \n> +core.graph::\n> +\tEnable git commit graph feature. Allows writing and reading from .graph files.\n> +\n> core.sparseCheckout::\n> \tEnable \"sparse checkout\" feature. See section \"Sparse checkout\" in\n> \tlinkgit:git-read-tree[1] for more information.\n> diff --git a/cache.h b/cache.h\n> index d8b975a571..655a81ac90 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -825,6 +825,7 @@ extern char *git_replace_ref_base;\n> extern int fsync_object_files;\n> extern int core_preload_index;\n> extern int core_apply_sparse_checkout;\n> +extern int core_graph;\n> extern int precomposed_unicode;\n> extern int protect_hfs;\n> extern int protect_ntfs;\n> diff --git a/config.c b/config.c\n> index e617c2018d..fee90912d8 100644\n> --- a/config.c\n> +++ b/config.c\n> @@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)\n> \t\treturn 0;\n> \t}\n> \n> +\tif (!strcmp(var, \"core.graph\")) {\n> +\t\tcore_graph = git_config_bool(var, value);\n> +\t\treturn 0;\n> +\t}\n> +\n> \tif (!strcmp(var, \"core.sparsecheckout\")) {\n> \t\tcore_apply_sparse_checkout = git_config_bool(var, value);\n> \t\treturn 0;\n> diff --git a/environment.c b/environment.c\n> index 63ac38a46f..0c56a3d869 100644\n> --- a/environment.c\n> +++ b/environment.c\n> @@ -61,6 +61,7 @@ enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;\n> char *notes_ref_name;\n> int grafts_replace_parents = 1;\n> int core_apply_sparse_checkout;\n> +int core_graph;\n> int merge_log_config = -1;\n> int precomposed_unicode = -1; /* see probe_utf8_pathname_composition() */\n> unsigned long pack_size_limit_cfg;\n"},{"id":"337411","messageId":"CAGZ79ka61UCXWAP4X8CTdCSiPUBnsO1_-wNSkGmV0VjZyAqcpw@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-4-dstolee@microsoft.com","subject":"Re: [PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T21:45:55Z","receivedAt":"2018-01-25T21:46:02Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> Teach Git the 'graph' builtin that will be used for writing and\n> reading packed graph files. The current implementation is mostly\n> empty, except for a check that the core.graph setting is enabled\n> and a '--pack-dir' option.\n\nI wonder if this builtin should not respect the boolean core graph,\nas this new builtin commands' whole existence\nis to deal with these new files?\n\nAs you assume this builtin as a plumbing command, I would\nexpect it to pay less attention to config rather than more.\n\n\n> @@ -408,6 +408,7 @@ static struct cmd_struct commands[] = {\n> { \"fsck-objects\", cmd_fsck, RUN_SETUP },\n> { \"gc\", cmd_gc, RUN_SETUP },\n> { \"get-tar-commit-id\", cmd_get_tar_commit_id },\n> + { \"graph\", cmd_graph, RUN_SETUP_GENTLY },\n\nWhy gently, though?\n\nFrom reading the docs (and assumptions on further patches)\nwe'd want to abort if there is no .git dir to be found?\n\nOr is a future patch having manual logic? (e.g. if pack-dir is\ngiven, the command may be invoked from outside a git dir)\n\nStefan\n"},{"id":"337412","messageId":"xmqqr2qd8ug8.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"20180125140231.65604-5-dstolee@microsoft.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-25T22:06:15Z","receivedAt":"2018-01-25T22:06:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Add document specifying the binary format for packed graphs. This\n> format allows for:\n>\n> * New versions.\n> * New hash functions and hash lengths.\n> * Optional extensions.\n>\n> Basic header information is followed by a binary table of contents\n> into \"chunks\" that include:\n>\n> * An ordered list of commit object IDs.\n> * A 256-entry fanout into that list of OIDs.\n> * A list of metadata for the commits.\n> * A list of \"large edges\" to enable octopus merges.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n> 1 file changed, 88 insertions(+)\n> create mode 100644 Documentation/technical/graph-format.txt\n>\n> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\n> new file mode 100644\n> index 0000000000..a15e1036d7\n> --- /dev/null\n> +++ b/Documentation/technical/graph-format.txt\n> @@ -0,0 +1,88 @@\n> +Git commit graph format\n> +=======================\n\nGood that this is not saying \"graph format\" but is explicit that it\nis about \"commit\". Do the same for the previous steps. Especially,\nbuiltin/graph.c that does not have much to do with graph.c is not a\ngood way forward ;-)\n\nI do like the fact that later parents of octopus merges are moved\nout of way to make the majority of records fixed length, but I am\nnot sure if the \"up to two parents are recorded in line\" is truly\nthe best arrangement. Aren't majority of commits single-parent,\nthereby wasting 4 bytes almost always?\n\nWill 32-bit stay to be enough for everybody? Wouldn't it make sense\nto at least define them to be indices into arrays (i.e. scaled to\nelement size), not \"offsets\", to recover a few lost bits?\n\nWhat's the point of storing object id length? If you do not\nunderstand the object ID scheme, knowing only the length would not\ndo you much good anyway, no? And if you know the hashing scheme\nspecified by Object ID version, you already know the length, no?\n"},{"id":"337413","messageId":"CAGZ79kap0bdpcHqLM128mc_f2aEoemRJSFUNpU2xvegtOMcTkg@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-5-dstolee@microsoft.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T22:07:33Z","receivedAt":"2018-01-25T22:07:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> Add document specifying the binary format for packed graphs. This\n> format allows for:\n>\n> * New versions.\n> * New hash functions and hash lengths.\n> * Optional extensions.\n>\n> Basic header information is followed by a binary table of contents\n> into \"chunks\" that include:\n>\n> * An ordered list of commit object IDs.\n> * A 256-entry fanout into that list of OIDs.\n> * A list of metadata for the commits.\n> * A list of \"large edges\" to enable octopus merges.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n\nSo this is different from Documentation/technical/packed-graph.txt,\nwhich gives high level design and this gives the details on how\nto set bits.\n\n> 1 file changed, 88 insertions(+)\n> create mode 100644 Documentation/technical/graph-format.txt\n>\n> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\n> new file mode 100644\n> index 0000000000..a15e1036d7\n> --- /dev/null\n> +++ b/Documentation/technical/graph-format.txt\n> @@ -0,0 +1,88 @@\n> +Git commit graph format\n> +=======================\n> +\n> +The Git commit graph stores a list of commit OIDs and some associated\n> +metadata, including:\n> +\n> +- The generation number of the commit. Commits with no parents have\n> + generation number 1; commits with parents have generation number\n> + one more than the maximum generation number of its parents. We\n> + reserve zero as special, and can be used to mark a generation\n> + number invalid or as \"not computed\".\n> +\n> +- The root tree OID.\n> +\n> +- The commit date.\n> +\n> +- The parents of the commit, stored using positional references within\n> + the graph file.\n> +\n> +== graph-*.graph files have the following format:\n> +\n> +In order to allow extensions that add extra data to the graph, we organize\n> +the body into \"chunks\" and provide a binary lookup table at the beginning\n> +of the body. The header includes certain values, such as number of chunks,\n> +hash lengths and types.\n> +\n> +All 4-byte numbers are in network order.\n> +\n> +HEADER:\n> +\n> + 4-byte signature:\n> + The signature is: {'C', 'G', 'P', 'H'}\n> +\n> + 1-byte version number:\n> + Currently, the only valid version is 1.\n> +\n> + 1-byte Object Id Version (1 = SHA-1)\n> +\n> + 1-byte Object Id Length (H)\n\n This is 20 or 40 for sha1 ? (binary or text representation?)\n\n> + 1-byte number (C) of \"chunks\"\n> +\n> +CHUNK LOOKUP:\n> +\n> + (C + 1) * 12 bytes listing the table of contents for the chunks:\n> + First 4 bytes describe chunk id. Value 0 is a terminating label.\n> + Other 8 bytes provide offset in current file for chunk to start.\n\n... offset [in bytes/words/4k blocks?] in ...\n\n\n> + (Chunks are ordered contiguously in the file, so you can infer\n> + the length using the next chunk position if necessary.)\n> +\n> + The remaining data in the body is described one chunk at a time, and\n> + these chunks may be given in any order. Chunks are required unless\n> + otherwise specified.\n\n> +\n> +CHUNK DATA:\n> +\n> + OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)\n> + The ith entry, F[i], stores the number of OIDs with first\n> + byte at most i. Thus F[255] stores the total\n> + number of commits (N).\n\nSo F[0] > 0 for git.git for example.\n\nOr another way: To lookup a 01xxx, I need to look at\nentry(F[00] + 1 )...entry(F[01]).\n\nMakes sense.\n\n> +\n> + OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)\n> + The OIDs for all commits in the graph.\n\n... sorted ascending.\n\n\n> + Commit Data (ID: {'C', 'G', 'E', '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 int-ids of the first two parents of\n> + the ith commit. Stores value 0xffffffff if no parent in that position.\n> + If there are more than two parents, the second value has its most-\n> + significant bit on and the other bits store an offset into the Large\n> + Edge List chunk.\n\ns/an offset into/position in/ ? (otherwise offset in bytes?)\n\n> + * The next 8 bytes store the generation number of the commit and the\n> + commit time in seconds since EPOCH. The generation number uses the\n> + higher 30 bits of the first 4 bytes, while the commit time uses the\n> + 32 bits of the second 4 bytes, along with the lowest 2 bits of the\n> + lowest byte, storing the 33rd and 34th bit of the commit time.\n\nThis allows for a maximum generation number of\n1.073.741.823 (2^30 -1) = 1 billion,\nand a max time stamp of later than 2100.\n\nDo you allow negative time stamps?\n\n\n> +\n> + [Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})\n> + This list of 4-byte values store the second through nth parents for\n> + all octoput merges. The second parent value in the commit data is a\n\noctopus\n\n> + negative number pointing into this list. Then iterate through this\n> + list starting at that position until reaching a value with the most-\n> + significant bit on. The other bits correspond to the int-id of the\n> + last parent.\n> +\n> +TRAILER:\n> +\n> + H-byte HASH-checksum of all of the above.\n> --\n> 2.16.0\n>\n"},{"id":"337414","messageId":"CAGZ79kZkhCmmF9hPRaf7RygDuWJd3edMDiAki8CDTJw3xG6BCg@mail.gmail.com","threadId":"47690","inReplyTo":"xmqqr2qd8ug8.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T22:18:09Z","receivedAt":"2018-01-25T22:18:16Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 2:06 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> Add document specifying the binary format for packed graphs. This\n>> format allows for:\n>>\n>> * New versions.\n>> * New hash functions and hash lengths.\n>> * Optional extensions.\n>>\n>> Basic header information is followed by a binary table of contents\n>> into \"chunks\" that include:\n>>\n>> * An ordered list of commit object IDs.\n>> * A 256-entry fanout into that list of OIDs.\n>> * A list of metadata for the commits.\n>> * A list of \"large edges\" to enable octopus merges.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n>> 1 file changed, 88 insertions(+)\n>> create mode 100644 Documentation/technical/graph-format.txt\n>>\n>> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\n>> new file mode 100644\n>> index 0000000000..a15e1036d7\n>> --- /dev/null\n>> +++ b/Documentation/technical/graph-format.txt\n>> @@ -0,0 +1,88 @@\n>> +Git commit graph format\n>> +=======================\n>\n> Good that this is not saying \"graph format\" but is explicit that it\n> is about \"commit\". Do the same for the previous steps. Especially,\n> builtin/graph.c that does not have much to do with graph.c is not a\n> good way forward ;-)\n>\n> I do like the fact that later parents of octopus merges are moved\n> out of way to make the majority of records fixed length, but I am\n> not sure if the \"up to two parents are recorded in line\" is truly\n> the best arrangement. Aren't majority of commits single-parent,\n> thereby wasting 4 bytes almost always?\n\ngit.git has ~37k non-merge commits and ~12k merge commits,\n(35 of them have 3 or more parents).\n\nSo 75% would waste the 4 bytes of the second parent.\n\nHowever the first parent is still there, so any operation that only needs\nthe first parent (git bisect --first-parent?) would still be fast.\nNot sure if that is common.\n\nThe downside of just having one parent or pointer into the edge list\nwould be to penalize 25% of the commit lookups with an indirection\ncompared to ~0% (the 35 octopus'). I'd rather want to optimize for\nspeed than disk size? (4 bytes for 37k is 145kB for git.git, which I\nfind is not a lot).\n"},{"id":"337415","messageId":"xmqqmv118tde.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"CAGZ79kZkhCmmF9hPRaf7RygDuWJd3edMDiAki8CDTJw3xG6BCg@mail.gmail.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-25T22:29:33Z","receivedAt":"2018-01-25T22:29:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> The downside of just having one parent or pointer into the edge list\n> would be to penalize 25% of the commit lookups with an indirection\n> compared to ~0% (the 35 octopus'). I'd rather want to optimize for\n> speed than disk size? (4 bytes for 37k is 145kB for git.git, which I\n> find is not a lot).\n\nMy comment is not about disk size but is about the size of working\nset (or \"size of array element\").\n"},{"id":"337416","messageId":"xmqqinbp8rw3.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"20180125140231.65604-4-dstolee@microsoft.com","subject":"Re: [PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-25T23:01:32Z","receivedAt":"2018-01-25T23:01:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Teach Git the 'graph' builtin that will be used for writing and\n> reading packed graph files. The current implementation is mostly\n> empty, except for a check that the core.graph setting is enabled\n> and a '--pack-dir' option.\n\nJust to set my expectation straight.\n\nIs it fair to say that in the ideal endgame state, this will be like\n\"git pack-objects\" in that end users won't have to know about it,\nbut would serve as a crucial building block that is invoked by other\nfront-end commands that are more familiar to end users (just like\npack-objects are used behind the scenes by repack, push, etc.)?\n"},{"id":"337417","messageId":"87wp05wnaw.fsf@evledraar.gmail.com","threadId":"47690","inReplyTo":"fe9d20da-eb70-d725-0530-cab1c029a0c8@gmail.com","subject":"Re: [PATCH 00/14] Serialized Commit Graph","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-25T23:06:47Z","receivedAt":"2018-01-25T23:06:55Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jan 25 2018, Derrick Stolee jotted:\n\n> On 1/25/2018 10:46 AM, Ævar Arnfjörð Bjarmason wrote:\n>> On Thu, Jan 25 2018, Derrick Stolee jotted:\n>>\n>>> * 'git log --topo-order -1000' walks all reachable commits to avoid\n>>> incorrect topological orders, but only needs the commit message for\n>>> the top 1000 commits.\n>>>\n>>> * 'git merge-base ' may walk many commits to find the correct\n>>> boundary between the commits reachable from A and those reachable\n>>> from B. No commit messages are needed.\n>>>\n>>> * 'git branch -vv' checks ahead/behind status for all local branches\n>>> compared to their upstream remote branches. This is essentially as\n>>> hard as computing merge bases for each.\n>> This is great, spotted / questions so far:\n>>\n>> * git graph --blah says you need to enable the config, should say\n>> \"unknown option --blah \". I.e. overzelous config guard.\n>\n> This is a good point.\n>\n>> * On a big repo (git show-ref -s | ~/g/git/git-graph --write\n>> --update-head) is as of writing this still hanging for me, but strace\n>> shows it's brk()-ing. Presumably just still busy, a progress bar would\n>> be very nice.\n>\n> Oops! This is my mistake. The correct command should be:\n>\n> git show-ref -s | git graph --write --update-head --stdin-commits\n>\n> Without \"--stdin-commits\" the command will walk all packed objects\n> to look for commits and then build the graph. That's why it's taking\n> so long. That method takes several minutes on the Linux repo, but with\n> --stdin-commits it should take as long as \"git log >/dev/null\".\n\nThanks, it took around 15m to finish with the command I initially ran on\nmy test repo.\n\nThen the `merge-base --is-ancestor` performance problem I was\ncomplaining about in\nhttps://public-inbox.org/git/87608bawoa.fsf@evledraar.gmail.com/ takes\naround 1s with your series, 5s without it. Nice.\n"},{"id":"337418","messageId":"CAGZ79kaNj-+oBNmbTKtOE8P-ZFcBVZSaBtwzrB4RQTWnYXcoqA@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-6-dstolee@microsoft.com","subject":"Re: [PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T23:21:33Z","receivedAt":"2018-01-25T23:21:38Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n\n> +struct object_id *construct_graph(const char *pack_dir)\n> +{\n> + // Find a list of oids, adding the pointer to a list.\n\nComment style.\nHere is where the bike shedding begins. ;)\n"},{"id":"337419","messageId":"CAGZ79kYQfHc398w5QMATotLYaCZW+sPiY05gGx9pGFm4GzBE+A@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-7-dstolee@microsoft.com","subject":"Re: [PATCH 06/14] packed-graph: implement git-graph --write","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T23:28:32Z","receivedAt":"2018-01-25T23:28:41Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n\n> +------------------------------------------------\n> +$ git midx --write\n\nmidx?\n\n> +test_done\n\nThe tests basically tests that there is no segfault?\nMakes sense.\n"},{"id":"337420","messageId":"CAGZ79kY9GD+ZiFCmAfUsJOqYOQg_a8FUzCiKwVST-_oLUPSnHg@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-10-dstolee@microsoft.com","subject":"Re: [PATCH 09/14] packed-graph: implement git-graph --clear","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-25T23:35:22Z","receivedAt":"2018-01-25T23:35:31Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> Teach Git to delete the current 'graph_head' file and the packed graph\n> it references. This is a good safety valve if somehow the file is\n> corrupted and needs to be recalculated. Since the packed graph is a\n> summary of contents already in the ODB, it can be regenerated.\n>\n> Signed-off-by: Derrick Stolee \n\n\n> static int graph_read(void)\n> {\n> struct object_id graph_oid;\n> @@ -105,6 +130,8 @@ int cmd_graph(int argc, const char **argv, const char *prefix)\n> { OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n> N_(\"dir\"),\n> N_(\"The pack directory to store the graph\") },\n> + OPT_BOOL('c', \"clear\", &opts.clear,\n> + N_(\"clear graph file and graph-head\")),\n\nGiven the docs building up a large list of \"Cannot be combined with\",\nmaybe these OPT_BOOLS want to be OPT_CMDMODE ?\n"},{"id":"337464","messageId":"b06bed0e-59e6-c678-792b-4fe57c849037@gmail.com","threadId":"47690","inReplyTo":"87wp05wnaw.fsf@evledraar.gmail.com","subject":"Re: [PATCH 00/14] Serialized Commit Graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T12:15:25Z","receivedAt":"2018-01-26T12:15:33Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 6:06 PM, Ævar Arnfjörð Bjarmason wrote:\n> On Thu, Jan 25 2018, Derrick Stolee jotted:\n>> Oops! This is my mistake. The correct command should be:\n>>\n>> git show-ref -s | git graph --write --update-head --stdin-commits\n>>\n>> Without \"--stdin-commits\" the command will walk all packed objects\n>> to look for commits and then build the graph. That's why it's taking\n>> so long. That method takes several minutes on the Linux repo, but with\n>> --stdin-commits it should take as long as \"git log >/dev/null\".\n> Thanks, it took around 15m to finish with the command I initially ran on\n> my test repo.\n>\n> Then the `merge-base --is-ancestor` performance problem I was\n> complaining about in\n> https://public-inbox.org/git/87608bawoa.fsf@evledraar.gmail.com/ takes\n> around 1s with your series, 5s without it. Nice.\n\nThanks for testing this! May I ask how many commits are in your repo? \nOne way to find out is to run 'git graph --read' and it will tell you \nhow many commits are in the serialized graph.\n\nThanks,\n-Stolee\n"},{"id":"337476","messageId":"6b72406f-90cd-194e-1f5f-02a43b7b60a5@gmail.com","threadId":"47690","inReplyTo":"CAGZ79kbVoJpP3d_jgJ9Ekn=9NBMaKVNoapjygz7BxABxP2dCBg@mail.gmail.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T12:49:01Z","receivedAt":"2018-01-26T12:49:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 3:04 PM, Stefan Beller wrote:\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>> Add Documentation/technical/packed-graph.txt with details of the planned\n>> packed graph feature, including future plans.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++\n>> 1 file changed, 185 insertions(+)\n>> create mode 100644 Documentation/technical/packed-graph.txt\n>>\n>> diff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt\n>> new file mode 100644\n>> index 0000000000..fcc0c83874\n>> --- /dev/null\n>> +++ b/Documentation/technical/packed-graph.txt\n>> @@ -0,0 +1,185 @@\n>> +Git Packed Graph Design Notes\n>> +=============================\n>> +\n>> +Git walks the commit graph for many reasons, including:\n>> +\n>> +1. Listing and filtering commit history.\n>> +2. Computing merge bases.\n>> +\n>> +These operations can become slow as the commit count grows above 100K.\n> How did you come up with that specific number? (Is it platform dependent?)\n> I'd avoid a specific number to not derail the reader here into wondering\n> how this got measured.\n\nUsing a specific number was a mistake. Git can walk ~100K commits per \nsecond by parsing commits, in my tests on my machine. I'll instead say \n\"commit count grows.\"\n\n>> +The merge base calculation shows up in many user-facing commands, such\n>> +as 'status' and 'fetch' and can take minutes to compute depending on\n>> +data shape. There are two main costs here:\n> status needs the walk for the ahead/behind computation which is (1)?\n> (I forget how status would need to compute a merge-base)\n\n'status' computes the ahead/behind counts using paint_down_to_common(). \nThis is a more robust method than simply computing merge bases, but the \npossible merge bases are found as a result.\n\n> fetch is a networked command, which traditionally in Git is understood as\n> \"can be slow\" because you might be in Australia, or the connection is slow\n> otherwise. So giving this as an example it is not obvious that the DAG walking\n> is the bottleneck. Maybe git-merge or \"git show --remerge-diff\" [1] are better\n> examples for walk-intensive commands?\n>\n> [1] https://public-inbox.org/git/cover.1409860234.git.tr@thomasrast.ch/\n> never landed, so maybe that is a bad example. But for me that command\n> is more obviously dependent on cheap walking the DAG compared to fetch.\n> So, take my comments with a grain of salt!\n\nActually, a 'fetch' command does the same ahead/behind calculation as \n'status', and in GVFS repos we have seen that walk take 30s per branch \nwhen comparing local and remote copies a fast-moving branch. Yes, there \nare other (usually) more expensive things in 'fetch' so I'll drop that \nreference..\n\n>> +1. Decompressing and parsing commits.\n>> +2. Walking the entire graph to avoid topological order mistakes.\n>> +\n>> +The packed graph is a file that stores the commit graph structure along\n>> +with some extra metadata to speed up graph walks. This format allows a\n>> +consumer to load the following info for a commit:\n>> +\n>> +1. The commit OID.\n>> +2. The list of parents.\n>> +3. The commit date.\n>> +4. The root tree OID.\n>> +5. An integer ID for fast lookups in the graph.\n>> +6. The generation number (see definition below).\n>> +\n>> +Values 1-4 satisfy the requirements of parse_commit_gently().\n>\n> This new format is specifically removing the cost of decompression and parsing\n> (1) completely, whereas (2) we still have to walk the entire graph for now as\n> the generation numbers are not fully used as of yet, but provided.\n\nA major goal of this work is to provide a place to store computed \ngeneration numbers so we can not walk the entire graph. I mention this \nhere because 'git log -' is O(n) (due to commit-date heuristics that \nprevent walking the entire graph) while 'git log --topo-order -' is \nO(T) where T is the total number of reachable commits.\n\n>> +By providing an integer ID we can avoid lookups in the graph as we walk\n>> +commits. Specifically, we need to provide the integer ID of the parent\n>> +commits so we navigate directly to their information on request.\n> Does this mean we decrease the pressure on fast lookups in\n> packfiles/loose objects?\n\nYes, we do. In fact, when profiling 'git log --topo-order -1000', I \nnoticed that 30-50% of the time (after this patch) is spent in \nlookup_tree(). If we can prevent checking the ODB for the existence of \nthese trees until they are needed, we can get additional speedups. It is \na bit wasteful that we are loading these trees even when we will never \nuse them (such as computing merge bases).\n\n>\n>> +Define the \"generation number\" of a commit recursively as follows:\n>> + * A commit with no parents (a root commit) has generation number 1.\n>> + * A commit with at least one parent has generation number 1 more than\n>> + the largest generation number among its parents.\n>> +Equivalently, the generation number is one more than the length of a\n>> +longest path from the commit to a root commit. The recursive definition\n>> +is easier to use for computation and the following property:\n>> +\n>> + If A and B are commits with generation numbers N and M, respectively,\n>> + and N <= M, then A cannot reach B. That is, we know without searching\n>> + that B is not an ancestor of A because it is further from a root commit\n>> + than A.\n>> +\n>> + Conversely, when checking if A is an ancestor of B, then we only need\n>> + to walk commits until all commits on the walk boundary have generation\n>> + number at most N. If we walk commits using a priority queue seeded by\n>> + generation numbers, then we always expand the boundary commit with highest\n>> + generation number and can easily detect the stopping condition.\n> Thanks for including the definition and potential benefits!\n>\n>> +\n>> +This property can be used to significantly reduce the time it takes to\n>> +walk commits and determine topological relationships. Without generation\n>> +numbers, the general heuristic is the following:\n>> +\n>> + If A and B are commits with commit time X and Y, respectively, and\n>> + X < Y, then A _probably_ cannot reach B.\n>> +\n>> +This heuristic is currently used whenever the computation can make\n>> +mistakes with topological orders (such as \"git log\" with default order),\n>> +but is not used when the topological order is required (such as merge\n>> +base calculations, \"git log --graph\").\n>> +\n>> +Design Details\n>> +--------------\n>> +\n>> +- A graph file is stored in a file named 'graph-.graph' in the pack\n>> + directory.\n> (guessing)\n> where every commit up to is included in the file.\n\nSorry, the is the hash of the graph contents (up to its trailing \nbytes that contain in binary).\n\n>> This could be stored in an alternate.\n> So I can 'borrow' not just the objects itself, but also the file about object\n> properties from an alternate. Makes sense, though I wonder if it is\n> worth stating\n> this as the first bullet point in the design detail section?\n\nI could bring it up earlier. For GVFS, we plan to place the graph next \nto the packfiles in the \"gitObjectCache\" which is an alternate for all \nenlistements in the same drive.\n\n>\n>> +- The most-recent graph file OID is stored in a 'graph-head' file for\n>> + immediate access and storing backup graphs. This could be stored in an\n>> + alternate, and refers to a 'graph-.graph' file in the same pack\n>> + directory.\n> So we have two copies of the latest in both 'graph-head.graph'\n> as well as 'graph-.graph'? Would a link be ok? So instead\n> we might have a 'graph-head.link' file that just contains 'oid: ' ?\n>\n> But then again, we can get the oid from HEAD, and these graph files\n> can contain all information up to multiple tips (i.e. there is just one graph\n> file needed, even if you have 2 branches, neither of them to be\n> fast-forwardable to the other).\n>\n> So maybe I do not understand the after all, yet.\n\nPerhaps I should instead use instead of , since it is not an \nactual Git object but instead the hash of the graph contents. The \n'graph_head' file simply stores the as plain-text hex characters.\n\nWhen updating the graph using 'git graph --write --update-head \n--delete-expired', we follow this pattern:\n\n1. write new graph-.graph file\n2. write graph_head to contain \n3. delete old graph-.graph file.\n\n>> +- The core.graph config setting must be on to create or consume graph files.\n> We already have other local files that speed up things, such as idx files.\n> Searching our config options for \"idx\" I find 'pack.indexVersion', which\n> only controls the write side of idx. Reading idx seems automatic if they are\n> there, otherwise we fallback to non-idx.\n>\n> By having the setting a boolean we cannot control the version yet, but we can\n> later upgrade the config to a boolean-or-int that specifies which graph\n> version is written out.\n>\n> Why do we need this config option to control the reading side as well?\n> AFAICT the user can just delete all graphs if the graphs make problems and\n> then regenerate them if git is too slow?\n>\n> As these files need to be manually generated as of this series, I'd further\n> argue that the reading should be unguarded by the config option.\n\nI see this config option as temporary as the feature is hardened. In the \n(hopefully unlikely) case of a bug, I'd rather unblock a user by giving \nthem a config setting to disable instead of telling them to downgrade. \nAs the feature is more robust and covered by other test cases (such as \nwhen the graph is automatically generated during repack or after a \nfetch) then we can afford to drop this \"kill switch\".\n\n>> +- The graph file is only a supplemental structure. If a user downgrades\n>> + or disables the 'core.graph' config setting, then the existing ODB is\n>> + sufficient.\n> (Maybe mention idx files as a comparable design?)\n\nI was actually thinking this is more comparable to the reachability \nbitmaps. The only difference is that the graph is not paired to a \npackfile. While dropping an IDX file is recoverable through 'git \nindex-pack', the contents of that packfile are not available until you \ndo so. If you run 'git graph --clear' and delete your graph file, all \ngit commands will work as before.\n\n>> +- The file format includes parameters for the object id length\n>> + and hash algorithm, so a future change of hash algorithm does\n>> + not require a change in format.\n> Cool.\n>\n>> +\n>> +Current Limitations\n>> +-------------------\n>> +\n>> +- Only one graph file is used at one time. This allows the integer ID to\n>> + seek into the single graph file. It is possible to extend the model\n>> + for multiple graph files, but that is currently not part of the design.\n>> +\n>> +- .graph files are managed only by the 'graph' builtin. These are not\n>> + updated automatically during clone or fetch.\n>> +\n>> +- There is no '--verify' option for the 'graph' builtin to verify the\n>> + contents of the graph file.\n> c.f. git index-pack --verify (which is not documented :/)\n>\n>> +- The graph only considers commits existing in packfiles and does not\n>> + walk to fill in reachable commits. [Small]\n> small?\n\nSorry for this in two ways: I left this \"small\" note to myself, and then \nforgot to remove it from the limitations after I implemented it (see \npatch 13/14).\n\n>> +- When rewriting the graph, we do not check for a commit still existing\n>> + in the ODB, so garbage collection may remove commits\n>> +\n>> +- Generation numbers are not computed in the current version. The file\n>> + format supports storing them, along with a mechanism to upgrade from\n>> + a file without generation numbers to one that uses them.\n> Maybe move the definition and explanation of the generation numbers above to\n> the \"Future Work\" section?\n\nI'm hesitant to move them to \"Future Work\" because generation numbers \nare so important to the design of the feature. If this design could not \nprovide generation numbers as an easy second patch, then the design is \nbad and should not be used.\n\n>> +\n>> +Future Work\n>> +-----------\n>> +\n>> +- The file format includes room for precomputed generation numbers. These\n>> + are not currently computed, so all generation numbers will be marked as\n>> + 0 (or \"uncomputed\"). A later patch will include this calculation.\n>> +\n>> +- The current implementation of the 'graph' builtin walks all packed objects\n>> + to find a complete list of commits in packfiles. If some commits are\n>> + stored as loose objects, then these do not appear in the graph. This is\n>> + handled gracefully by the file format, but it would cause incorrect\n>> + generation number calculations. We should implement the construct_graph()\n>> + method in a way that walks all commits reachable from some starting set\n>> + and then can use complete information for generation numbers. (Some\n>> + care must be taken around shallow clones.)\n>> +\n>> +- The graph is not currently integrated with grafts.\n> not integrated? Does that mean we error out on grafts, or gracefully fallback\n> to a sane thing?\n\nI have no idea what would happen if you tried to use this commit graph \nfeature with grafts enabled. I'm not familiar enough with the feature to \nknow how it works and to plan for it.\n\nThe issue right now is that there is graft code in parse_commit_buffer() \nthat I did not duplicate in parse_packed_commit() [see patch 11/14]. \nSince currently grafts and packed-grafts are opt-in features that need \nto be set by a user (i.e. you do not get them automatically by cloning) \nI thought it sufficient to say these features are incompatible.\n\n>> +- After computing and storing generation numbers, we must make graph\n>> + walks aware of generation numbers to gain performance benefits. This\n>> + will mostly be accomplished by swapping a commit-date-ordered priority\n>> + queue with one ordered by generation number. The following operations\n>> + are important candidates:\n>> +\n>> + - paint_down_to_common()\n>> + - 'log --topo-order'\n>> +\n>> +- The graph currently only adds commits to a previously existing graph.\n>> + When writing a new graph, we could check that the ODB still contains\n>> + the commits and choose to remove the commits that are deleted from the\n>> + ODB. For performance reasons, this check should remain optional.\n>> +\n>> +- Currently, parse_commit_gently() requires filling in the root tree\n>> + object for a commit. This passes through lookup_tree() and consequently\n>> + lookup_object(). Also, it calls lookup_commit() when loading the parents.\n>> + These method calls check the ODB for object existence, even if the\n>> + consumer does not need the content. For example, we do not need the\n>> + tree contents when computing merge bases. Now that commit parsing is\n>> + removed from the computation time, these lookup operations are the\n>> + slowest operations keeping graph walks from being fast. Consider\n>> + loading these objects without verifying their existence in the ODB and\n>> + only loading them fully when consumers need them. Consider a method\n>> + such as \"ensure_tree_loaded(commit)\" that fully loads a tree before\n>> + using commit->tree.\n>> +\n>> +- The current design uses the 'graph' builtin to generate the graph. When\n>> + this feature stabilizes enough to recommend to most users, we should\n>> + add automatic graph writes to common operations that create many commits.\n>> + For example, one coulde compute a graph on 'clone' and 'fetch' commands.\n> typo \"could\"\n>\n> Once we have incrementally-update-able graphs, we certainly want commit/merge\n> to also write out updates? (or batch them after a long rebase).\n\nI think batching will always be a good idea. It is feasible to have some \nthreshold where there are enough reachable commits that are not in the \ngraph to trigger a write (incremental or not). My gut feel is that \nnumber is at least 100.\n\nThanks,\n-Stolee\n"},{"id":"337477","messageId":"e74758fe-f645-0a75-51fd-2b2e39289ce4@gmail.com","threadId":"47690","inReplyTo":"xmqqzi518wu3.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:06:27Z","receivedAt":"2018-01-26T13:06:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 4:14 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> Add Documentation/technical/packed-graph.txt with details of the planned\n>> packed graph feature, including future plans.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++\n>> 1 file changed, 185 insertions(+)\n>> create mode 100644 Documentation/technical/packed-graph.txt\n> I really wanted to like having this patch at the beginning, but\n> unfortunatelly I didn't see the actual file format description,\n> which was a bit disappointing. An example of the things that I was\n> curious about was how the \"integer ID\" is used to access into the\n> file. If we could somehow use \"integer ID\" as an index into an\n> array of fixed size elements, it would be ideal to gain \"fast\n> lookups\", but because of the \"list of parents\" thing, it needs some\n> trickery to do so, and that was among the things that I wanted to\n> see how much thought went into the design, for example.\n\nThere is definitely a chicken-or-the-egg situation here. I'm happy to \nstart with the format before the design document.\n\nI can try to expand this \"integer ID\" concept, but you can see how I use \nit in the following method from patch 11/14:\n\n+int parse_packed_commit(struct commit *item)\n+{\n+        if (!core_graph)\n+                return 0;\n+        if (item->object.parsed)\n+                return 1;\n+\n+        prepare_packed_graph();\n+        if (packed_graph) {\n+                uint32_t pos;\n+                int found;\n+                if (item->graphId != 0xFFFFFFFF) {\n+                        pos = item->graphId;\n+                        found = 1;\n+                } else {\n+                        found = bsearch_graph(packed_graph, \n&(item->object.oid), &pos);\n+                }\n+\n+                if (found)\n+                        return fill_packed_commit(item, packed_graph, pos);\n+        }\n+\n+        return 0;\n+}\n\nNote that if item->graphId has a \"real\" value (not 0xFFFFFFFF which in \nhindsight should be a macro) then we navigate directly to that position \nin the graph. Otherwise, we use binary search to query the graph's \ncommit list to find the position (if the commit is packed).\n\n>> diff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt\n>> new file mode 100644\n>> index 0000000000..fcc0c83874\n>> --- /dev/null\n>> +++ b/Documentation/technical/packed-graph.txt\n>> @@ -0,0 +1,185 @@\n>> +Git Packed Graph Design Notes\n>> +=============================\n>> +\n>> +Git walks the commit graph for many reasons, including:\n>> +\n>> +1. Listing and filtering commit history.\n>> +2. Computing merge bases.\n>> +\n>> +These operations can become slow as the commit count grows above 100K.\n>> +The merge base calculation shows up in many user-facing commands, such\n>> +as 'status' and 'fetch' and can take minutes to compute depending on\n>> +data shape. There are two main costs here:\n> s/data shape/history shape/ may make it even clearer.\n>\n>> +1. The commit OID.\n>> +2. The list of parents.\n>> +3. The commit date.\n>> +4. The root tree OID.\n>> +5. An integer ID for fast lookups in the graph.\n>> +6. The generation number (see definition below).\n>> +\n>> +Values 1-4 satisfy the requirements of parse_commit_gently().\n>> +\n>> +By providing an integer ID we can avoid lookups in the graph as we walk\n>> +commits. Specifically, we need to provide the integer ID of the parent\n>> +commits so we navigate directly to their information on request.\n> Commits created after a packed graph file is built may of course not\n> appear in a packed graph file, but that is OK because they never need\n> to be listed as parents of commits in the file. So \"list of parents\"\n> can always refer to the parents using the \"integer ID for fast lookup\".\n\nOne thing I need to test locally is what happens with boundary commits \nof a shallow clone. The commit's parents are not in the repo, so they \nwill not be in the graph. I think that parse_commit_buffer() drops the \nparents, so the graph will treat them as root commits.\n\n> Makes sense. Item 2. might want to say \"The list of parents, using\n> the fast lookup integer ID (see 5.) as reference instead of OID\",\n> though.\n\nThat will be more specific, thanks.\n\n>> +Define the \"generation number\" of a commit recursively as follows:\n>> + * A commit with no parents (a root commit) has generation number 1.\n>> + * A commit with at least one parent has generation number 1 more than\n>> + the largest generation number among its parents.\n>> +Equivalently, the generation number is one more than the length of a\n>> +longest path from the commit to a root commit.\n> When a commit A can reach roots X and Y, and Y is further than X,\n> the distance between Y and A becomes A's generation number. \"One\n> more than the length of the path from the commit to the furthest\n> root commit it can reach\", in other words.\n\nMy \"Equivalently,...\" sentence is mangled. What I mean is:\n\n     Equivalently, the generation number of A is one more than\n     the length of a longest path from A to a root commit.\n\nI intended to make a non-recursive definition, and the \"one more than\" \nhere could easily be conflated with the \"one more than\" in the recursive \ndefinition. The reason for \"one more than\" is that root commits have a \npath of length zero but generation number one.\n\nReminder to self: use \"one\" instead of \"1\" in the recursive definition.\n\n>> +The recursive definition\n>> +is easier to use for computation and the following property:\n>> +\n>> + If A and B are commits with generation numbers N and M, respectively,\n>> + and N <= M, then A cannot reach B. That is, we know without searching\n>> + that B is not an ancestor of A because it is further from a root commit\n>> + than A.\n>> +\n>> + Conversely, when checking if A is an ancestor of B, then we only need\n>> + to walk commits until all commits on the walk boundary have generation\n>> + number at most N. If we walk commits using a priority queue seeded by\n>> + generation numbers, then we always expand the boundary commit with highest\n>> + generation number and can easily detect the stopping condition.\n> These are both true. It would be nice if an optimized walker\n> algorithm can also deal with history with recent commits for which\n> we do not yet know the generation numbers (i.e. you first traverse\n> and assign generation numbers and record in packed graph, then\n> history grows but we haven't added the new commits to the packed\n> graph yet).\n\nMy forward-thinking intention is that we will perform walks using a \npriority queue whose priority first compares generation number (which \nwill be 0xFFFFFFFF for commits not in the graph) and then compares by \ncommit date on equal generation number. For walks that require \ntopological constraints, we cannot stop the walk until all commits in \nthe queue have a \"real\" generation number. This will allow our \nalgorithms to work with a mix of packed commits and unpacked commits.\n\n>\n>> +- A graph file is stored in a file named 'graph-.graph' in the pack\n>> + directory. This could be stored in an alternate.\n> Is that really an object name? The that appears in the\n> name of a packfile pack-.pack is *not* an , and I somehow\n> suspect that you are doing a similar \"use hash of (some) contents to\n> make it uniquely identify the content\", not \"information about a\n> single object that is identified by the \".\n\nThis is definitely a mistake on my part and I'll switch this to use \n in the documents. I do use 'struct object_id' in the code for \nthis value. Is that OK?\n\n>\n>> +- The graph file is only a supplemental structure. If a user downgrades\n>> + or disables the 'core.graph' config setting, then the existing ODB is\n>> + sufficient.\n> OK, that is exactly what I meant to say in a few paragraphs above\n> that I wanted to see.\n\nI'll move this to the top!\n\n>\n>> +Current Limitations\n>> +-------------------\n>> +\n>> +- Only one graph file is used at one time. This allows the integer ID to\n>> + seek into the single graph file. It is possible to extend the model\n>> + for multiple graph files, but that is currently not part of the design.\n>> +\n>> +- .graph files are managed only by the 'graph' builtin. These are not\n>> + updated automatically during clone or fetch.\n> In addition to \"clone or fetch\", I presume operations that locally\n> create commits do not automatically create them, right?\n\nNo. Writing a graph file is too expensive for one commit operation. \nPerhaps some threshold of new commits could trigger the graph calculation.\n\n>\n>> +- After computing and storing generation numbers, we must make graph\n>> + walks aware of generation numbers to gain performance benefits. This\n>> + will mostly be accomplished by swapping a commit-date-ordered priority\n>> + queue with one ordered by generation number. The following operations\n>> + are important candidates:\n>> +\n>> + - paint_down_to_common()\n>> + - 'log --topo-order'\n> Do you mean that this round only writes \"graph\" without any actualy\n> consumers? It is somewhat hard to assess the value of what is\n> stored in the new file without the consumers.\n>\n> Anyway, thanks for starting this. Let's read on.\n>\n\nSee Patch 11/14 for consumption by EVERY commit-graph walk. This patch \nincludes significant performance improvements for every walk by avoiding \nparsing, but to get the benefit of generation numbers we will need to \nchange the algorithms that operate on the commit graph.\n\nWhile that integration with algorithms may seem daunting, the good news \nis that we can make iterative changes to improve each algorithm one-by-one.\n\nThanks,\n-Stolee\n\n"},{"id":"337478","messageId":"de0577f6-e076-873f-7573-d284423597ae@gmail.com","threadId":"47690","inReplyTo":"xmqqvafp8vib.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 02/14] packed-graph: add core.graph setting","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:08:13Z","receivedAt":"2018-01-26T13:08:20Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 4:43 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> The packed graph feature is controlled by the new core.graph config\n>> setting. This defaults to 0, so the feature is opt-in.\n>>\n>> The intention of core.graph is that a user can always stop checking\n>> for or parsing packed graph files if core.graph=0.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/config.txt | 3 +++\n>> cache.h | 1 +\n>> config.c | 5 +++++\n>> environment.c | 1 +\n>> 4 files changed, 10 insertions(+)\n> Before you get too married to the name \"graph\", is it reasonable to\n> assume that the commit ancestry graph is the primary \"graph\" that\n> should come to users' minds when a simple word \"graph\" is used in\n> the context of discussing Git? I suspect not.\n>\n> Let's not just call this \"core.graph\" and \"packed-graph\", and in\n> addition give some adjective before \"graph\".\n\nI was too focused that I wanted the word \"graph\" but \"graph.c\" already \nexisted in source root that I came up with \"packed-graph.c\" just to have \na separate filename. Clearly, \"commit-graph\" should be used instead. In \nv2, I'll use \"/commit-graph.c\" and \"/builtin/commit-graph.c\".\n\nThanks,\n-Stolee\n"},{"id":"337479","messageId":"a29fc66e-8063-d134-b6d2-4be38de161f4@gmail.com","threadId":"47690","inReplyTo":"CAGZ79ka61UCXWAP4X8CTdCSiPUBnsO1_-wNSkGmV0VjZyAqcpw@mail.gmail.com","subject":"Re: [PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:13:14Z","receivedAt":"2018-01-26T13:13:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 4:45 PM, Stefan Beller wrote:\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>> Teach Git the 'graph' builtin that will be used for writing and\n>> reading packed graph files. The current implementation is mostly\n>> empty, except for a check that the core.graph setting is enabled\n>> and a '--pack-dir' option.\n> I wonder if this builtin should not respect the boolean core graph,\n> as this new builtin commands' whole existence\n> is to deal with these new files?\n>\n> As you assume this builtin as a plumbing command, I would\n> expect it to pay less attention to config rather than more.\n\nMy thought was to alert the caller \"This graph isn't going to be good \nfor anything!\" and fail quickly before doing work. You do have a good \npoint, and I think we can remove that condition here. When we integrate \nwith other commands ('repack', 'fetch', 'clone') we will want a \ndifferent setting that signals automatically writing the graph and we \ndon't want those to fail because they are not aware of a second config \nsetting.\n\n>\n>> @@ -408,6 +408,7 @@ static struct cmd_struct commands[] = {\n>> { \"fsck-objects\", cmd_fsck, RUN_SETUP },\n>> { \"gc\", cmd_gc, RUN_SETUP },\n>> { \"get-tar-commit-id\", cmd_get_tar_commit_id },\n>> + { \"graph\", cmd_graph, RUN_SETUP_GENTLY },\n> Why gently, though?\n>\n> From reading the docs (and assumptions on further patches)\n> we'd want to abort if there is no .git dir to be found?\n>\n> Or is a future patch having manual logic? (e.g. if pack-dir is\n> given, the command may be invoked from outside a git dir)\n\nYou are right. I inherited this from my MIDX patch which can operate on \na list of IDX files without a .git folder. The commit graph operations \nneed an ODB.\n\nThanks,\n-Stolee\n\n"},{"id":"337480","messageId":"37d84775-174f-02fc-159c-0810df458b5a@gmail.com","threadId":"47690","inReplyTo":"xmqqinbp8rw3.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:14:01Z","receivedAt":"2018-01-26T13:14:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 6:01 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> Teach Git the 'graph' builtin that will be used for writing and\n>> reading packed graph files. The current implementation is mostly\n>> empty, except for a check that the core.graph setting is enabled\n>> and a '--pack-dir' option.\n> Just to set my expectation straight.\n>\n> Is it fair to say that in the ideal endgame state, this will be like\n> \"git pack-objects\" in that end users won't have to know about it,\n> but would serve as a crucial building block that is invoked by other\n> front-end commands that are more familiar to end users (just like\n> pack-objects are used behind the scenes by repack, push, etc.)?\n\nThat is my hope. Leaving that integration for later, after this feature \nhas proven itself.\n"},{"id":"337481","messageId":"c6ccbd6f-ef97-3240-7cdc-6ef7a3f95cf6@gmail.com","threadId":"47690","inReplyTo":"xmqqmv118tde.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:22:38Z","receivedAt":"2018-01-26T13:22:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 5:06 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n>> Add document specifying the binary format for packed graphs. This\n>> format allows for:\n>>\n>> * New versions.\n>> * New hash functions and hash lengths.\n>> * Optional extensions.\n>>\n>> Basic header information is followed by a binary table of contents\n>> into \"chunks\" that include:\n>>\n>> * An ordered list of commit object IDs.\n>> * A 256-entry fanout into that list of OIDs.\n>> * A list of metadata for the commits.\n>> * A list of \"large edges\" to enable octopus merges.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n>> 1 file changed, 88 insertions(+)\n>> create mode 100644 Documentation/technical/graph-format.txt\n>>\n>> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\n>> new file mode 100644\n>> index 0000000000..a15e1036d7\n>> --- /dev/null\n>> +++ b/Documentation/technical/graph-format.txt\n>> @@ -0,0 +1,88 @@\n>> +Git commit graph format\n>> +=======================\n> Good that this is not saying \"graph format\" but is explicit that it\n> is about \"commit\". Do the same for the previous steps. Especially,\n> builtin/graph.c that does not have much to do with graph.c is not a\n> good way forward ;-)\n\n:+1:\n\n> I do like the fact that later parents of octopus merges are moved\n> out of way to make the majority of records fixed length, but I am\n> not sure if the \"up to two parents are recorded in line\" is truly\n> the best arrangement. Aren't majority of commits single-parent,\n> thereby wasting 4 bytes almost always?\n>\n> Will 32-bit stay to be enough for everybody? Wouldn't it make sense\n> to at least define them to be indices into arrays (i.e. scaled to\n> element size), not \"offsets\", to recover a few lost bits?\n\nI incorrectly used the word \"offset\" when I mean \"array position\" for \nthe edge values.\n\n> What's the point of storing object id length? If you do not\n> understand the object ID scheme, knowing only the length would not\n> do you much good anyway, no? And if you know the hashing scheme\n> specified by Object ID version, you already know the length, no?\n\nI'll go read the OID transition document to learn more, but I didn't \nknow if there were plans for things like \"Use SHA3 but with different \nhash lengths depending on user requirements\". One side benefit is that \nwe immediately know the width of our commit and tree references within \nthe commit graph file without needing to consult a table of hash \ndefinitions.\n\n\nOn 1/25/2018 5:18 PM, Stefan Beller wrote:\n> git.git has ~37k non-merge commits and ~12k merge commits,\n> (35 of them have 3 or more parents).\n>\n> So 75% would waste the 4 bytes of the second parent.\n>\n> However the first parent is still there, so any operation that only needs\n> the first parent (git bisect --first-parent?) would still be fast.\n> Not sure if that is common.\n\nThe current API boundary does not support this, as parse_commit_gently() \nis not aware of the --first-parent option. The benefits of injecting \nthat information are probably not worth the complication.\n\nOn 1/25/2018 5:29 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> The downside of just having one parent or pointer into the edge list\n>> would be to penalize 25% of the commit lookups with an indirection\n>> compared to ~0% (the 35 octopus'). I'd rather want to optimize for\n>> speed than disk size? (4 bytes for 37k is 145kB for git.git, which I\n>> find is not a lot).\n> My comment is not about disk size but is about the size of working\n> set (or \"size of array element\").\nI do want to optimize for speed over space, at least for two-parent \ncommits. Hopefully my clarification about offset/array position \nclarifies Junio's concerns here.\n\nThanks,\n-Stolee\n\n"},{"id":"337482","messageId":"5d70ca39-e844-3565-42ed-c09cb1529d34@gmail.com","threadId":"47690","inReplyTo":"CAGZ79kap0bdpcHqLM128mc_f2aEoemRJSFUNpU2xvegtOMcTkg@mail.gmail.com","subject":"Re: [PATCH 04/14] packed-graph: add format document","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:25:11Z","receivedAt":"2018-01-26T13:25:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 5:07 PM, Stefan Beller wrote:\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>> Add document specifying the binary format for packed graphs. This\n>> format allows for:\n>>\n>> * New versions.\n>> * New hash functions and hash lengths.\n>> * Optional extensions.\n>>\n>> Basic header information is followed by a binary table of contents\n>> into \"chunks\" that include:\n>>\n>> * An ordered list of commit object IDs.\n>> * A 256-entry fanout into that list of OIDs.\n>> * A list of metadata for the commits.\n>> * A list of \"large edges\" to enable octopus merges.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++\n> So this is different from Documentation/technical/packed-graph.txt,\n> which gives high level design and this gives the details on how\n> to set bits.\n>\n>> 1 file changed, 88 insertions(+)\n>> create mode 100644 Documentation/technical/graph-format.txt\n>>\n>> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt\n>> new file mode 100644\n>> index 0000000000..a15e1036d7\n>> --- /dev/null\n>> +++ b/Documentation/technical/graph-format.txt\n>> @@ -0,0 +1,88 @@\n>> +Git commit graph format\n>> +=======================\n>> +\n>> +The Git commit graph stores a list of commit OIDs and some associated\n>> +metadata, including:\n>> +\n>> +- The generation number of the commit. Commits with no parents have\n>> + generation number 1; commits with parents have generation number\n>> + one more than the maximum generation number of its parents. We\n>> + reserve zero as special, and can be used to mark a generation\n>> + number invalid or as \"not computed\".\n>> +\n>> +- The root tree OID.\n>> +\n>> +- The commit date.\n>> +\n>> +- The parents of the commit, stored using positional references within\n>> + the graph file.\n>> +\n>> +== graph-*.graph files have the following format:\n>> +\n>> +In order to allow extensions that add extra data to the graph, we organize\n>> +the body into \"chunks\" and provide a binary lookup table at the beginning\n>> +of the body. The header includes certain values, such as number of chunks,\n>> +hash lengths and types.\n>> +\n>> +All 4-byte numbers are in network order.\n>> +\n>> +HEADER:\n>> +\n>> + 4-byte signature:\n>> + The signature is: {'C', 'G', 'P', 'H'}\n>> +\n>> + 1-byte version number:\n>> + Currently, the only valid version is 1.\n>> +\n>> + 1-byte Object Id Version (1 = SHA-1)\n>> +\n>> + 1-byte Object Id Length (H)\n> This is 20 or 40 for sha1 ? (binary or text representation?)\n\n20 for binary.\n\n>\n>> + 1-byte number (C) of \"chunks\"\n>> +\n>> +CHUNK LOOKUP:\n>> +\n>> + (C + 1) * 12 bytes listing the table of contents for the chunks:\n>> + First 4 bytes describe chunk id. Value 0 is a terminating label.\n>> + Other 8 bytes provide offset in current file for chunk to start.\n> ... offset [in bytes/words/4k blocks?] in ...\n\nbytes.\n\n>\n>> + (Chunks are ordered contiguously in the file, so you can infer\n>> + the length using the next chunk position if necessary.)\n>> +\n>> + The remaining data in the body is described one chunk at a time, and\n>> + these chunks may be given in any order. Chunks are required unless\n>> + otherwise specified.\n>> +\n>> +CHUNK DATA:\n>> +\n>> + OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)\n>> + The ith entry, F[i], stores the number of OIDs with first\n>> + byte at most i. Thus F[255] stores the total\n>> + number of commits (N).\n> So F[0] > 0 for git.git for example.\n>\n> Or another way: To lookup a 01xxx, I need to look at\n> entry(F[00] + 1 )...entry(F[01]).\n>\n> Makes sense.\n>\n>> +\n>> + OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)\n>> + The OIDs for all commits in the graph.\n> ... sorted ascending.\n>\n>\n>> + Commit Data (ID: {'C', 'G', 'E', '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 int-ids of the first two parents of\n>> + the ith commit. Stores value 0xffffffff if no parent in that position.\n>> + If there are more than two parents, the second value has its most-\n>> + significant bit on and the other bits store an offset into the Large\n>> + Edge List chunk.\n> s/an offset into/position in/ ? (otherwise offset in bytes?)\n>\n>> + * The next 8 bytes store the generation number of the commit and the\n>> + commit time in seconds since EPOCH. The generation number uses the\n>> + higher 30 bits of the first 4 bytes, while the commit time uses the\n>> + 32 bits of the second 4 bytes, along with the lowest 2 bits of the\n>> + lowest byte, storing the 33rd and 34th bit of the commit time.\n> This allows for a maximum generation number of\n> 1.073.741.823 (2^30 -1) = 1 billion,\n> and a max time stamp of later than 2100.\n>\n> Do you allow negative time stamps?\n>\n>\n>> +\n>> + [Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})\n>> + This list of 4-byte values store the second through nth parents for\n>> + all octoput merges. The second parent value in the commit data is a\n> octopus\n>\n>> + negative number pointing into this list. Then iterate through this\n>> + list starting at that position until reaching a value with the most-\n>> + significant bit on. The other bits correspond to the int-id of the\n>> + last parent.\n>> +\n>> +TRAILER:\n>> +\n>> + H-byte HASH-checksum of all of the above.\n>> --\n>> 2.16.0\n>>\n\nThanks for the detailed comments here!\n-Stolee\n\n\n"},{"id":"337483","messageId":"fbf1fcbf-752c-c558-6f47-e254656d8978@gmail.com","threadId":"47690","inReplyTo":"CAGZ79kYQfHc398w5QMATotLYaCZW+sPiY05gGx9pGFm4GzBE+A@mail.gmail.com","subject":"Re: [PATCH 06/14] packed-graph: implement git-graph --write","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-26T13:28:13Z","receivedAt":"2018-01-26T13:28:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/25/2018 6:28 PM, Stefan Beller wrote:\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>\n>> +------------------------------------------------\n>> +$ git midx --write\n> midx?\n\nLooks like I missed some replacements as I was building this. Now you \nsee how I hope the feedback from this patch will inform the MIDX patch. ;)\n\n>\n>> +test_done\n> The tests basically tests that there is no segfault?\n> Makes sense.\n\nAlso checks that files are written based on the output hash. The next \ncommits gives inspection ability.\n\nThanks,\n-Stolee\n"},{"id":"337484","messageId":"CACsJy8D8ofq+G8XrN-i2MTxGWESfE8_TZm6sAEJe9=mUjpipRg@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-2-dstolee@microsoft.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-01-26T14:13:33Z","receivedAt":"2018-01-26T14:14:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Jan 25, 2018 at 9:02 PM, Derrick Stolee wrote:\n> +Git walks the commit graph for many reasons, including:\n> +\n> +1. Listing and filtering commit history.\n> +2. Computing merge bases.\n> +\n> +These operations can become slow as the commit count grows above 100K.\n> +The merge base calculation shows up in many user-facing commands, such\n> +as 'status' and 'fetch' and can take minutes to compute depending on\n> +data shape. There are two main costs here:\n> +\n> +1. Decompressing and parsing commits.\n> +2. Walking the entire graph to avoid topological order mistakes.\n> +\n> +The packed graph is a file that stores the commit graph structure along\n> +with some extra metadata to speed up graph walks. This format allows a\n> +consumer to load the following info for a commit:\n> +\n> +1. The commit OID.\n> +2. The list of parents.\n> +3. The commit date.\n> +4. The root tree OID.\n> +5. An integer ID for fast lookups in the graph.\n> +6. The generation number (see definition below).\n\nI didn't look closely to compare, but perhaps you should check out\npack file format version 4 [1]. It tried to address the same thing but\nit never got to the point where we could replace our current pack\nformat with it. At some point I wanted to push it even as a local\noptimization (pack transfer is still in old format) but I never had\nenough time or energy for it. How it stores commits though can\nprobably be reused.\n\n[1] https://github.com/pclouds/git/commit/23cb8ae5bdd968c1a290ff8d0fd7cb6b4d572a43\n-- \nDuy\n"},{"id":"337485","messageId":"CACsJy8BS3Gi2rZq=JXz+o+g4cOJCg0sKShqSG0p9kFXCjwNtWg@mail.gmail.com","threadId":"47690","inReplyTo":"37d84775-174f-02fc-159c-0810df458b5a@gmail.com","subject":"Re: [PATCH 03/14] packed-graph: create git-graph builtin","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-01-26T14:16:09Z","receivedAt":"2018-01-26T14:16:45Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jan 26, 2018 at 8:14 PM, Derrick Stolee wrote:\n> On 1/25/2018 6:01 PM, Junio C Hamano wrote:\n>>\n>> Derrick Stolee writes:\n>>\n>>> Teach Git the 'graph' builtin that will be used for writing and\n>>> reading packed graph files. The current implementation is mostly\n>>> empty, except for a check that the core.graph setting is enabled\n>>> and a '--pack-dir' option.\n>>\n>> Just to set my expectation straight.\n>>\n>> Is it fair to say that in the ideal endgame state, this will be like\n>> \"git pack-objects\" in that end users won't have to know about it,\n>> but would serve as a crucial building block that is invoked by other\n>> front-end commands that are more familiar to end users (just like\n>> pack-objects are used behind the scenes by repack, push, etc.)?\n>\n>\n> That is my hope. Leaving that integration for later, after this feature has\n> proven itself.\n\nThen I suggest you use a more specific command name (commit-graph?\npacked-graph?) and leave the pretty name \"graph\" out, it could be used\nfor some UI-facing thing someday, maybe.\n-- \nDuy\n"},{"id":"337494","messageId":"CAGZ79kZUYW-NJYUfPco_SUDdO29Wo_cKW1-gxsFGvR0-3vV0NQ@mail.gmail.com","threadId":"47690","inReplyTo":"6b72406f-90cd-194e-1f5f-02a43b7b60a5@gmail.com","subject":"Re: [PATCH 01/14] graph: add packed graph design document","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-26T18:17:13Z","receivedAt":"2018-01-26T18:17:19Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":">>> +- A graph file is stored in a file named 'graph-.graph' in the pack\n>>> + directory.\n>>\n>> (guessing)\n>> where every commit up to is included in the file.\n>\n>\n> Sorry, the is the hash of the graph contents (up to its trailing bytes\n> that contain in binary).\n\n>> So maybe I do not understand the after all, yet.\n>\n>\n> Perhaps I should instead use instead of , since it is not an\n> actual Git object but instead the hash of the graph contents. The\n> 'graph_head' file simply stores the as plain-text hex characters.\n\nYes, please use hash. Oid (object id) means to me the identification of\na Git object, whereas here we only use the hash to\n(1) check if that file is valid (consistent, no bit flips in that;\n --verify would do this)\n(2) to have a different file name for each file such that we can have\n multiple graph files at once, e.g. build the next file in the background\n while using the old file to keep working.\n(3) any other use case?\n\nFor (2) we could use `mkstemp` as well, but the property of (1) is nice\nto have.\n\nWhen using you probably mean sha1. When writing the hash\ntransition document, we discussed about uses of sha1 apart from\nobject naming, such as the use here or in the new pack file format\nand we thought it would be ok to keep sha1 for the purpose of (1),\nbut as we may want to lose the sha1 code in the far future, it may be\neasier to migrate that hash to the new hash function, too. So\nit is easy to confuse that hash with OIDs because it is the same hash\nfunction throughout time.\n\nThanks,\nStefan\n"},{"id":"337519","messageId":"CAGZ79kbR_GUGRhXBU187LchHKqxFd42Rc=w+jOEfrigmEAgNaw@mail.gmail.com","threadId":"47690","inReplyTo":"20180125140231.65604-12-dstolee@microsoft.com","subject":"Re: [PATCH 11/14] commit: integrate packed graph with commit parsing","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-26T19:38:51Z","receivedAt":"2018-01-26T19:38:59Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n> Teach Git to inspect a packed graph to supply the contents of a\n> struct commit when calling parse_commit_gently(). This implementation\n> satisfies all post-conditions on the struct commit, including loading\n> parents, the root tree, and the commit date. The only loosely-expected\n> condition is that the commit buffer is loaded into the cache. This\n> was checked in log-tree.c:show_log(), but the \"return;\" on failure\n> produced unexpected results (i.e. the message line was never terminated).\n> The new behavior of loading the buffer when needed prevents the\n> unexpected behavior.\n>\n> If core.graph is false, then do not load the graph and behave as usual.\n>\n> In test script t5319-graph.sh, add output-matching conditions on read-\n> only graph operations.\n>\n> By loading commits from the graph instead of parsing commit buffers, we\n> save a lot of time on long commits walks. Here are some performance\n> results for a copy of the Linux repository where 'master' has 704,766\n> reachable commits and is behind 'origin/master' by 19,610 commits.\n>\n> | Command | Before | After | Rel % |\n> |----------------------------------|--------|--------|-------|\n> | log --oneline --topo-order -1000 | 5.9s | 0.7s | -88% |\n> | branch -vv | 0.42s | 0.27s | -35% |\n> | rev-list --all | 6.4s | 1.0s | -84% |\n> | rev-list --all --objects | 32.6s | 27.6s | -15% |\n\nThis sounds impressive!\n\n> @@ -383,19 +384,27 @@ int parse_commit_gently(struct commit *item, int quiet_on_missing)\n>\n> if (!item)\n> return -1;\n> +\n> + // If we already parsed, but got it from the graph, then keep going!\n\ncomment style.\n\n> if (item->object.parsed)\n> return 0;\n> +\n> + if (check_packed && parse_packed_commit(item))\n> + return 0;\n> +\n> buffer = read_sha1_file(item->object.oid.hash, &type, &size);\n> if (!buffer)\n> return quiet_on_missing ? -1 :\n> error(\"Could not read %s\",\n> - oid_to_hex(&item->object.oid));\n> + oid_to_hex(&item->object.oid));\n> if (type != OBJ_COMMIT) {\n> free(buffer);\n> return error(\"Object %s not a commit\",\n> - oid_to_hex(&item->object.oid));\n> + oid_to_hex(&item->object.oid));\n> }\n> +\n> ret = parse_commit_buffer(item, buffer, size);\n> +\n\nI guess the new lines are for readability?\nNot sure if will play out nicely with merges in this area, though.\n(I touch this area of the code as well in the not yet sent out series\nadding the repository as an argument all over the place. Not your\nproblem, just me getting anxious)\n\n> @@ -34,6 +34,8 @@\n> #define GRAPH_CHUNKLOOKUP_SIZE (5 * 12)\n> #define GRAPH_MIN_SIZE (GRAPH_CHUNKLOOKUP_SIZE + GRAPH_FANOUT_SIZE + \\\n> GRAPH_OID_LEN + sizeof(struct packed_graph_header))\n> +/* global storage */\n> +struct packed_graph *packed_graph = 0;\n>\n> struct object_id *get_graph_head_oid(const char *pack_dir, struct object_id *oid)\n> {\n> @@ -209,6 +211,225 @@ struct packed_graph *load_packed_graph_one(const char *graph_file, const char *p\n> return graph;\n> }\n>\n> +static void prepare_packed_graph_one(const char *obj_dir)\n> +{\n> + char *graph_file;\n> + struct object_id oid;\n> + struct strbuf pack_dir = STRBUF_INIT;\n> + strbuf_addstr(&pack_dir, obj_dir);\n> + strbuf_add(&pack_dir, \"/pack\", 5);\n> +\n> + if (!get_graph_head_oid(pack_dir.buf, &oid))\n> + return;\n> +\n> + graph_file = get_graph_filename_oid(pack_dir.buf, &oid);\n> +\n> + packed_graph = load_packed_graph_one(graph_file, pack_dir.buf);\n> + strbuf_release(&pack_dir);\n> +}\n> +\n> +static int prepare_packed_graph_run_once = 0;\n\nOkay. :(\nSeeing new globals like these, gives me extra motivation to\nget the object store series going.\n"},{"id":"337548","messageId":"xmqqbmhg73fg.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"CAGZ79kaNj-+oBNmbTKtOE8P-ZFcBVZSaBtwzrB4RQTWnYXcoqA@mail.gmail.com","subject":"Re: [PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-26T20:47:31Z","receivedAt":"2018-01-26T20:47:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee wrote:\n>\n>> +struct object_id *construct_graph(const char *pack_dir)\n>> +{\n>> + // Find a list of oids, adding the pointer to a list.\n>\n> Comment style.\n> Here is where the bike shedding begins. ;)\n\nI also saw some violations of the usual formatting conventions, e.g.\n\n\tif (condition) {\n\t\tblock\n\nshould not be\n\n\tif (condition)\n\t{\n\t\tblock\n\n"},{"id":"337549","messageId":"xmqq607o732t.fsf@gitster.mtv.corp.google.com","threadId":"47690","inReplyTo":"20180125140231.65604-6-dstolee@microsoft.com","subject":"Re: [PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-26T20:55:06Z","receivedAt":"2018-01-26T20:55:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> +\t\tpackedDate[0] = htonl((*list)->date >> 32);\n> +\t\tpackedDate[1] = htonl((*list)->date);\n\nHow forward-looking do we want to be? The commit.date field happens\nto be unsigned so there is no point masking the result of right\nshifting it, but that would not stay to be the case once we start\nsupporting negative timestamps, for example.\n\nAlso, I recall that you plan to squeeze generation number in 30 bits\nor so of one of these words. Wouldn't it mean that higher order\nbits of commit.date must be masked out anyway, even though we do not\nhave to worry about right shift propagating the sign-bit down?\n\nAlso, would >>32 be a problem if commit.date is an uint32 (and\nshifting all its bits out to the right)?\n\n"},{"id":"337551","messageId":"87vafowce2.fsf@linux-m68k.org","threadId":"47690","inReplyTo":"xmqq607o732t.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Andreas Schwab","fromEmail":"schwab@linux-m68k.org","sentAt":"2018-01-26T21:14:45Z","receivedAt":"2018-01-26T21:14:55Z","isPatch":true,"sender":{"key":"schwab@linux-m68k.org","avatar":"https://avatars.githubusercontent.com/u/2175493?v=4"},"body":"On Jan 26 2018, Junio C Hamano wrote:\n\n> Also, would >>32 be a problem if commit.date is an uint32 (and\n> shifting all its bits out to the right)?\n\nIt would be undefined.\n\nAndreas.\n\n-- \nAndreas Schwab, schwab@linux-m68k.org\nGPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5\n\"And now for something completely different.\"\n"},{"id":"337554","messageId":"xmqq1sicuvi6.fsf@gitster-ct.c.googlers.com","threadId":"47690","inReplyTo":"87vafowce2.fsf@linux-m68k.org","subject":"Re: [PATCH 05/14] packed-graph: implement construct_graph()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-26T22:04:49Z","receivedAt":"2018-01-26T22:04:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Schwab writes:\n\n> On Jan 26 2018, Junio C Hamano wrote:\n>\n>> Also, would >>32 be a problem if commit.date is an uint32 (and\n>> shifting all its bits out to the right)?\n>\n> It would be undefined.\n\nYup, exactly. Thanks.\n"}]}