{"thread":{"id":"20466","subject":"[PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","startedAt":"2009-08-08T07:31:32Z","lastAt":"2009-08-16T22:41:52Z","messageCount":5,"participants":["Nick Edelen","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":6},"messages":[{"id":"119963","messageId":"op.uyb1uuu4tdk399@sirnot.private","threadId":"20466","inReplyTo":null,"subject":"[PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-08T07:31:32Z","receivedAt":"2009-08-08T07:31:32Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Before any code is introduced the full documentation is put forth.  This \nprovides a man page for the porcelain, and a technical doc in technical/.  The \nlatter describes the API, and discusses rev-cache's design, file format and \nmechanics.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\nSame as 1/5 in previous set.  The man page has been flushed out, and formatted \nmore congruently with git's other man pages.  The technical discussion has been \nupdated and tweaked for better formatting as well.  This has been in response \nto Sam's commentary.\n\n Documentation/git-rev-cache.txt       |   96 +++++++++\n Documentation/technical/rev-cache.txt |  379 +++++++++++++++++++++++++++++++++\n 2 files changed, 475 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100755\nindex 0000000..600cf64\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,96 @@\n+git-rev-cache(1)\n+================\n+\n+NAME\n+----\n+git-rev-cache - Add, walk and maintain revision cache slices.\n+\n+SYNOPSIS\n+--------\n+'git-rev-cache' COMMAND [options] [<commit>...]\n+\n+DESCRIPTION\n+-----------\n+A front end for the rev-cache API.  It is mainly intended for cache slice\n+generation and maintenance, but can also walk commits within a slice.  It\n+currently provides basic administrative functionality.\n+\n+COMMANDS\n+--------\n+\n+add\n+~~~\n+Add revisions to the cache by creating a new cache slice.  Reads a revision\n+list from the command line, formatted as: `START START ... \\--not END END ...`\n+\n+Options:\n+\n+\\--all::\n+\tInclude all branch heads in the new cache slice.\n+\n+\\--fresh::\n+\tExclude everything already in the revision cache.  \n+\n+\\--stdin::\n+\tRead newline-seperated revisions from the standard input.  Use \\--not\n+\tto exclude commits, as on the command line.\n+\n+\\--legs::\n+\tEnsure newly-generated cache slice is self-contained.  This means that\n+\tno commit has partially cached parents, in that all its parents are\n+\tcached or none of them are.\n+\n+\\--noobjects::\n+\tNon-commit objects are normally included along with the commit with\n+\twhich they were introduced.  This is obviously very benificial, but can\n+\ttake longer in cache slice generation.  Use this option to disable\n+\tnon-commit object caching.\n+\n+walk\n+~~~~\n+Walk a cache slice based on revision list, formatted like 'add'.\n+\n+Options:\n+\n+\\--objects::\n+\tLike 'git-rev-list', 'walk' will normally only list commits.  Use this\n+\toption to list non-commit objects as well.\n+\n+fuse\n+~~~~\n+Merge several cache slices into a single large slice.  On each invocation of\n+'add' a new file (\"slice\") is added to the revision cache directory, and after\n+several additions the directory may become populated with many, relatively\n+small slices.  Numerous smaller slices will yield poorer performance than a one\n+or two large ones, because of the overhead of loading new slices into memory.\n+\n+Running 'fuse' every once in a while will solve this problem by coalescing all\n+the cache slices into one larger slice.  For very large projects, using\n+\\--ignore-size is advisable to prevent overly large cache slices.\n+\n+Options:\n+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--add tells it to start walking from the branch\n+\theads, effectively an `add --all --fresh; fuse` (pseudo-command).\n+\n+\\--noobjects::\n+\tAs in 'add', this option disables inclusion of non-commit objects.  If\n+\tsome cache slices do contain such objects, the information will be lost.\n+\n+\\--ignore-size[=N]::\n+\tDo not merge cache slices of size >=N.  If N is not provided 'fuse'\n+\twill default to a size of ~25MB (be aware that slices must be mapped to\n+\tmemory).\n+\n+index\n+~~~~~\n+Regenerate the cache index.  If the index file associating objects with cache\n+slices gets corrupted, lost, or otherwise becomes unusable, 'index' will\n+quickly regenerate the file.  'fuse' will also regenerate the index.\n+\n+DISCUSSION\n+----------\n+For an explanation of the API and its inner workings, see\n+link:technical/rev-cache.txt[technical info on rev-cache].\ndiff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\nnew file mode 100755\nindex 0000000..78d7218\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,379 @@\n+rev-cache\n+=========\n+\n+The revision cache API ('rev-cache') provides a method for efficiently storing\n+and accessing commit branch sections.  Such branch slices are defined by a\n+series of top (interesting) and bottom (uninteresting) commits.  Each slice\n+contains, per commit:\n+\n+* All intra-slice topological relations, encoded into path \"channels\" (see\n+  'Mechanics' for full explanation).\n+* Object meta-data: type, SHA-1, size, date (for commits).\n+* Objects introduced in that commit, relative to slice (ie. only for non-start\n+  commits).\n+\n+Storage data structures are not exported, in part to keep git's global scope\n+clean, but largely because they're pretty much useless outside of rev-cache.\n+\n+The API\n+-------\n+\n+The API for 'rev-cache' is quite simple.  You can find the function prototypes\n+in `revision.h`.\n+\n+Data Structures\n+~~~~~~~~~~~~~~~\n+\n+The `rev_cache_info` struct holds all the options and flags for the API.\n+\n+----\n+struct rev_cache_info {\n+        /* generation flags */\n+        unsigned objects : 1,\n+                legs : 1,\n+                make_index : 1;\n+        \n+        /* traversal flags */\n+        unsigned save_unique : 1,\n+                add_to_pending : 1,\n+                add_names : 1;\n+        \n+        /* fuse options */\n+        unsigned int ignore_size;\n+};\n+----\n+\n+The fields:\n+\n+`objects`::\n+\tAdd non-commit objects to slice.\n+\n+`legs`::\n+\tEnsure end commits have no children.\n+\n+`make_index`::\n+\tIntegrate newly-made slice into index.\n+\n+`save_unique`::\n+\tLoad non-commit objects into `unique` field of their associated\n+\t`commit` object.\n+\n+`add_to_pending`::\n+\tAppend unique non-commit objects to the `pending` object list in the\n+\tpassed `rev_info` instance.\n+\n+`add_names`::\n+\tInclude non-commit object names in the pending object entries (if\n+\t`add_to_pending` is set), and set the `name` field of `blob` and `tree`\n+\tobjects (if `save_unique`).\n+\n+`ignore_size`::\n+\tIf non-zero, ignore slices with size greater or equal to this during\n+fusion.\n+\n+Functions\n+~~~~~~~~~\n+\n+`init_rci`::\n+        Initiate a `rev_cache_info` struct to default options.\n+\n+`make_cache_slice`::\n+        Create a cache based on an a `rev_info` instance or `commit_list` s of\n+        \"starts\" and \"ends\" (defaulting to latter if `rev_info` pointer is\n+        NULL), copying the cache SHA-1 into a passed pointer if non-zero.  A\n+        `rev_cache_info` struct pointer can be passed to set options, while\n+        passing NULL will set default options.  A last parameter can\n+        optionally recieve the final cache hash.\n+\n+`make_cache_index`::\n+        Add a slice to the cache index.  Requires a file descriptor, the cache\n+        hash and the file size.  Note that this is normally called by\n+        `make_cache_slice` under the `make_index` option.\n+\n+`get_cache_slice`::\n+        Given a commit SHA-1 `get_cache_slice` will search the slice index and\n+        return, if found, the cache-identifying SHA-1.\n+\n+`traverse_cache_slice`::\n+        Traverse a specified cache slice based on:\n+\n+        * `rev_info` instance; options set in the `rev_cache_info` field.\n+        * cache SHA-1 identifier\n+        * a starting commit and commit work list\n+        * date of oldest encountered interesting commit (passing 0 will tell\n+          rev-cache to use defaults)\n+        * current `slop` (this is a counter, a la `revision.c`, to determine\n+          when to stop traversing; typically you can just pass 0 and rev-cache\n+          will use default settings)\n+        \n++\n+The output is sent to a FILO `commit_list` \"queue\", while any end commits \n+are passed back into the work list.  If the walk is not contained within the \n+slice, commit boundaries are also inserted into \"work\".\n+\n+`start_from_slices`::\n+        Will mark all start-commits in the specified cache slices with a given\n+        flag, and add them to the rev pending list.  Will include all if no\n+        slices are specified.\n+\n+`coagulate_cache_slices`::\n+        Generate a slice based on the passed `rev_info` instance, replacing all\n+        encountered slices with one (larger) slice.  The `ignore_size` field in\n+        `rci`, if non-zero, will dictate which cache slice sizes to ignore in\n+        both traversal and replacement.\n+\n+`regenerate_index`::\n+        Remake cache index.\n+\n+Example Usage\n+-------------\n+\n+A few examples to demonstrate usage:\n+\n+.Creating a slice\n+----\n+/* pretend you're a porcelain for rev-cache reading from the command line */\n+struct rev_info revs;\n+struct rev_cache_info rci;\n+\n+init_revisions(&revs, 0);\n+init_rci(&rci);\n+\n+flags = 0;\n+for (i = 1; i < argc; i++) {\n+        if (!strcmp(argv[i], \"--not\"))\n+                flags ^= UNINTERESTING;\n+        else if(!strcmp(argv[i], \"--fresh\"))\n+                starts_from_slices(&revs, UNINTERESTING, 0, 0);\n+        else\n+                handle_revision_arg(argv[i], &revs, flags, 1);\n+}\n+\n+/* we want to explicitly set certain options */\n+rci.objects = 0;\n+\n+if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))\n+        printf(\"made slice!  it's called %s\\n\", sha1_to_hex(cache_sha1));\n+----\n+\n+.Traversing a slice\n+----\n+/* let's say you're walking the tree with a 'work' list of current heads and a \n+ * FILO output list 'out' */\n+out = 0;\n+outp = &out;\n+\n+while (work) {\n+        struct commit *commit = pop_commit(&work);\n+        struct object *object = &commit->object;\n+        unsigned char *cache_sha1;\n+        \n+        if (cache_sha1 = get_cache_slice(object->sha1)) {\n+                /* note that this will instatiate any topo-relations \n+                 * as it goes */\n+                if (traverse_cache_slice(&revs, cache_sha1,\n+                        commit, 0, 0, /* use defaults */\n+                        &outp, &work) < 0)\n+                        die(\"I'm overreacting to a non-fatal cache error\");\n+        } else {\n+                struct commit_list *parents = commit->parents;\n+                \n+                while (parents) {\n+                        struct commit *p = parents->item;\n+                        struct object *po = &p->object;\n+                        \n+                        parents = parents->next;\n+                        if (po->flags & UNINTERESTING)\n+                                continue;\n+                        \n+                        if (object->flags & UNINTERESTING)\n+                                po->flags |= UNINTERESTING;\n+                        else if (po->flags & SEEN)\n+                                continue;\n+                        \n+                        if (!po->parsed)\n+                                parse_commit(p);\n+                        insert_by_date(p, &work);\n+                }\n+                \n+                if (object->flags & (SEEN | UNINTERESTING) == 0)\n+                        outp = &commit_list_insert(commit, outp);\n+                object->flags |= SEEN;\n+        }\n+}\n+----\n+\n+Some Internals\n+--------------\n+\n+Although you really don't need to know anything about how rev-cache actually\n+does its magic shizz, a bit of background may go a long way if you're wading\n+through the source.\n+\n+File Formats\n+~~~~~~~~~~~~\n+\n+A slice has a basic fixed-size header, followed by a certain number of object\n+entries, then a NULL-seperated list of object names.  Commits are sorted in\n+topo-order, and each commit entry is followed by the objects added in that\n+commit.\n+\n+----\n+         -- +--------------------------------+\n+header      | object number, etc...          |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+...         ...                               \n+         -- +--------------------------------+\n+name list   | \\0some_file_name\\0             |\n+(note       +--------------------------------+\n+preceeding  | another_file\\0                 |\n+null)       ...                              |\n+            +--------------------------------+\n+----\n+\n+The index is a single file that associates SHA-1s with cache slices and file\n+positions.  It is somewhat similar to pack-file indexes, containing a fanout\n+table and a list of index entries sorted by hash.\n+\n+----\n+         -- +--------------------------------+\n+header      | object #, cache #, etc.        |\n+         -- +--------------------------------+\n+sha1s of    | SHA-1                          |\n+slices      | ...                            |\n+         -- +--------------------------------+\n+fanout      | fanout[0x00]                   |\n+table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+            | fanout[0xff]                   |\n+         -- +--------------------------------+\n+index       | SHA-1 of object                |\n+entries     | index of cache slice SHA-1     |\n+            | position in cache slice        |\n+            +--------------------------------+\n+            |                                |\n+            ...                               \n+            +--------------------------------+\n+----\n+\n+All the relavant structures are readily accessible in `rev-cache.c`\n+\n+Mechanics\n+~~~~~~~~~\n+\n+The most important part of rev-cache is its method of encoding topological\n+relations.  To ensure fluid traversal and reconstruction, commits are related\n+through high-level \"streams\"/\"channels\" rather than individual\n+interconnections.  Intuitively, rev-cache stores history the way gitk shows it:\n+commits strung up on lines, which interconnect at merges and branches.\n+\n+Each commit is associated to a given channel/path via a 'path id', and\n+variable-length fields govern which paths (if any) are closed or opened at that\n+object.  This means that topo-data can be preserved in only a few bytes extra\n+per object entry.  Other information stored per entry is the sha-1 hash, type,\n+date, size, name, and status in cache slice.  Here is format of an object\n+entry, both on-disk and in-memory:\n+\n+----\n+struct object_entry {\n+        unsigned type : 3;\n+        unsigned is_end : 1;\n+        unsigned is_start : 1;\n+        unsigned uninteresting : 1;\n+        unsigned include : 1;\n+        unsigned flags : 1;\n+        unsigned char sha1[20];\n+        \n+        unsigned merge_nr : 6;\n+        unsigned split_nr : 7;\n+        unsigned size_size : 3;\n+        unsigned name_size : 3;\n+        unsigned what_to_do : 5;\n+        \n+        uint32_t date;\n+        uint16_t path;\n+        \n+        /* merge paths */\n+        /* split paths */\n+        /* size */\n+        /* name index */\n+};\n+----\n+\n+An explanation of each field:\n+\n+`type`::\n+\tObject type\n+`is_end`::\n+\tThe commit has some parents outside the cache slice (all if slice has\n+\tlegs)\n+`is_start`::\n+\tThe commit has no children in cache slice\n+`uninteresting`::\n+\tRun-time flag, used in traversal\n+`include`::\n+\tRun-time flag, used in traversal (initialization)\n+`flags`::\n+\tCurrently unused, extra bit\n+`sha`::\n+\tObject SHA-1 hash\n+\n+`merge_nr`::\n+\tThe number of paths the current channel diverges into; the current path\n+\tends upon any merge.\n+`split_nr`::\n+\tThe number of paths this commit ends; used on both merging and\n+\tbranching.\n+`size_size`::\n+\tNumber of bytes the object size takes up.\n+`name_size`::\n+\tNumber of bytes the name index takes up.\n+`what_to_do`::\n+\tCurrently space-filler, to properly align the struct fields.  Can\n+\tpotentially be used for anything.\n+\n+merge paths::\n+\tThe path IDs (16-bit) that are to be created.\n+split paths::\n+\tThe path IDs (16-bit) that are to be ended.\n+size::\n+\tThe size split into the minimum number of bytes.\n+name index::\n+\tAn offset for the null-seperated, object name list at the end of the\n+\tcache slice.  Also split into the minimum number of bytes.\n+\n+Each path ID refers to an index in a 'path array', which stores the current\n+status (eg. active, interestingness) of each channel.\n+\n+Due to topo-relations and boundary tracking, all of a commit's parents must be\n+encountered before the path is reallocated.  This is achieved by using a\n+counter system per merge: starting at the parent number, the counter is\n+decremented as each parent is encountered (dictated by 'split paths'); at 0 the\n+path is cleared.\n+\n+Boundary tracking is necessary because non-commits are stored relative to the\n+commit in which they were introduced.  If a series of commits is not included\n+in the output, the last interesting commit must be parsed manually to ensure\n+all objects are accounted for.\n+\n+To prevent list-objects from recursing into trees that we've already taken care\n+of, the flag `FACE_VALUE` is introduced.  An object with this flag is not\n+explored (= \"taken at face value\"), significantly reducing I/O and processing\n+time.\n+\n+(NSE)\n-- \ntg: (6f604e7..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"120003","messageId":"7vbpmqi2d4.fsf@alter.siamese.dyndns.org","threadId":"20466","inReplyTo":"op.uyb1uuu4tdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-08T18:31:35Z","receivedAt":"2009-08-08T18:31:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Nick Edelen\" <sirnot@gmail.com> writes:\n\n> Before any code is introduced the full documentation is put forth.  This \n> provides a man page for the porcelain, and a technical doc in technical/.  The \n> latter describes the API, and discusses rev-cache's design, file format and \n> mechanics.\n>\n> Signed-off-by: Nick Edelen <sirnot@gmail.com>\n\nQuite respectable work, in that not many people try to start from\nspecification. \n\nI'll ask quite a many questions in the following.  I do not want you to\nexplain them to _me_ in your response.  I am asking them so that the v3\nand subsequent revision will remove the need for these questions to be\nasked by somebody (other than me) who reads the document.\n\n>  Documentation/git-rev-cache.txt       |   96 +++++++++\n>  Documentation/technical/rev-cache.txt |  379 +++++++++++++++++++++++++++++++++\n>  2 files changed, 475 insertions(+), 0 deletions(-)\n>\n> diff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\n> new file mode 100755\n\nAn executable documentation?\n\n> index 0000000..600cf64\n> --- /dev/null\n> +++ b/Documentation/git-rev-cache.txt\n> @@ -0,0 +1,96 @@\n> +git-rev-cache(1)\n> +================\n> +\n> +NAME\n> +----\n> +git-rev-cache - Add, walk and maintain revision cache slices.\n\nDrop the last '.'; also you may need to add this command to the command\nclassification list so that \"man git\" would know where to include this in\nits command list.\n\n> +SYNOPSIS\n> +--------\n> +'git-rev-cache' COMMAND [options] [<commit>...]\n> +\n> +DESCRIPTION\n> +-----------\n> +A front end for the rev-cache API.  It is mainly intended for cache slice\n> +generation and maintenance, but can also walk commits within a slice.  It\n> +currently provides basic administrative functionality.\n> +\n\nBriefly discuss\n\n - what rev-cache is for (e.g. \"an optional mechanism to speed up\n   revision traversal\");\n   \n - what a cache slice is (e.g. \"records such and such for a set of commit\n   objects\");\n\n - how these two relate to each other (e.g. \"one or more slices are tied\n   together with a single rev-cache-index to form a rev-cache); and\n\n - how a rev-cache relates to a repository or an object store (e.g. \"a\n   given repository can have up to N rev-cache that describes its\n   objects\")\n\nhere.\n\n> +COMMANDS\n> +--------\n> +\n> +add\n> +~~~\n> +Add revisions to the cache by creating a new cache slice.  Reads a revision\n> +list from the command line, formatted as: `START START ... \\--not END END ...`\n> +\n> +Options:\n> +\n> +\\--all::\n> +\tInclude all branch heads in the new cache slice.\n\nIs this \"all branch heads\"?  Shouldn't it be \"all refs?\"  If not, why not?\n\n> +\\--fresh::\n> +\tExclude everything already in the revision cache.  \n\nThis concept seems to correspond to --incremental in pack-objects parlance.\n\n> +\\--stdin::\n> +\tRead newline-seperated revisions from the standard input.  Use \\--not\n> +\tto exclude commits, as on the command line.\n> +\n> +\\--legs::\n> +\tEnsure newly-generated cache slice is self-contained.  This means that\n> +\tno commit has partially cached parents, in that all its parents are\n> +\tcached or none of them are.\n\nIf I am reading the description correctly what you mean is that for a\nhistory:\n\n\t---A---C---D\n              /\n          ---B\n\na slice is allowed to consist of (empty), (D), (C D), (A B C D), but not\n(A C D), if it wants to be \"--legs compliant\".\n\nBut without your definition in the second and third line, people would not\ncall (C D) \"self-contained\", as you cannot tell what C's parents are.\nBecause you do not use \"self-containedness\" in the rest of documentation\nto explain other things, you do not need to introduce such an unintuitive\ndefinition of a word.  I'd suggest dropping the first line.\n\nAlso for the lack of better word I said \"--legs compliant\" above.  We do\nneed a better word to express this concept, and use that as the option\nname.  Unfortunately, I can tell \"legs\" is not it, but I cannot offhand\nthink of what word should it be.\n\n> +\\--noobjects::\n> +\tNon-commit objects are normally included along with the commit with\n> +\twhich they were introduced.  This is obviously very benificial, but can\n> +\ttake longer in cache slice generation.  Use this option to disable\n> +\tnon-commit object caching.\n\n\"--no-objects\" (I think you meant reverse of --objects to rev-list).\n\nWhat is the ramification of using this option?  \"rev-list\" and \"gitk\" will\nstill be fast but \"pack-objects\" won't get as much speed-up?  Will use of\nthe option affect correctness?  Can a slice generated with this option\nlater fused with another generated without this option?  What are the\nperformance (or correctness) characteristics of a resulting slice of such\na fuse?\n\nIf the target audience of this manual page is Porcelain writers and API\nusers, these things need to be explained somewhere in this documentation.\n\n> +walk\n> +~~~~\n> +Walk a cache slice based on revision list, formatted like 'add'.\n\nWhat is formatted like 'add'?  The output from the command?  The command\nline arguments this subcommand takes?\n\nDefine \"walk\".  Is it \"dump the contents of a slice\"?  In a rev-cache with\nmore than one slice, which slice is chosen to be walked, and how?  How\ndoes the command line argument and options interract with cached data?\n\nFor example...\n\n> +Options:\n> +\n> +\\--objects::\n> +\tLike 'git-rev-list', 'walk' will normally only list commits.  Use this\n> +\toption to list non-commit objects as well.\n\n... how does walking with --objects option behave if you created all of\nyour slices with --no-objects?  Does it notice the lack of cached object\ninformation and falls back on reading from the objects?  If so how is this\ndifferent from rev-list itself?  If not, when is the walk command useful?\n\"while debugging the rev-cache machinery\" is a perfectly acceptable answer\nto the last question, but if that is the case please say so in the\ndocumentation.\n\n> +fuse\n> +~~~~\n> +Merge several cache slices into a single large slice.  On each invocation of\n> +'add' a new file (\"slice\") is added to the revision cache directory, and after\n> +several additions the directory may become populated with many, relatively\n> +small slices.  Numerous smaller slices will yield poorer performance than a one\n> +or two large ones, because of the overhead of loading new slices into memory.\n\nSomething like this is a perfect overview description that should have\nbeen given upfront (remember, I earlier said \"Briefly discuss...\"?).\n\nThis operation feels like \"repack\".\n\n> +Running 'fuse' every once in a while will solve this problem by coalescing all\n> +the cache slices into one larger slice.  For very large projects, using\n> +\\--ignore-size is advisable to prevent overly large cache slices.\n> +\n> +Options:\n> +\n> +\\--all::\n> +\tNormally fuse will only include everything that's already in the\n> +\trevision cache.  \\--add tells it to start walking from the branch\n> +\theads, effectively an `add --all --fresh; fuse` (pseudo-command).\n> +\n> +\\--noobjects::\n> +\tAs in 'add', this option disables inclusion of non-commit objects.  If\n> +\tsome cache slices do contain such objects, the information will be lost.\n> +\n> +\\--ignore-size[=N]::\n> +\tDo not merge cache slices of size >=N.  If N is not provided 'fuse'\n> +\twill default to a size of ~25MB (be aware that slices must be mapped to\n> +\tmemory).\n\nShould this autotune, perhaps relative to pack.windowMemory?  --ignore\nsounds misnomer; it is similar to \"keep\" flag that packfiles have.\n\n> +index\n> +~~~~~\n> +Regenerate the cache index.  If the index file associating objects with cache\n> +slices gets corrupted, lost, or otherwise becomes unusable, 'index' will\n> +quickly regenerate the file.  'fuse' will also regenerate the index.\n\nWe already have .git/index (the index), and .git/objects/pack/pack-*.idx\n(pack idx files).  At least please call this \"the rev-cache index\" so that\ntechnical documentations can differentiate when they want to talk about\nthis new index without having to worry about disambiguities.\n\nAt the beginning of your DESCRIPTION, you mentioned \"rev-cache\", then\n\"cache slice\", without explaining what they are, or how they relate to\neach other, leaving frustration to the readers.  The reader who reads on,\nsuppressing this frustration, is finally rewarded at the beginning of\n\"fuse\" description, where you mention that a rev-cache contains one or\nmore cache slices.  At that point, how these two concepts relate to each\nother is finally revealed.\n\nBut here, you introduce a new frustration.  There is no meantion in how\nthe rev-cache index relates to the other two concepts introduced earlier\n(the rev-cache itself, and cache slices).\n\nWhen is this \"reindex\" operation necessary under normal circumstances?  Is\nit primarily to recover bugs in rev-cache?  For example, \"repack -a -f\" is\nnot about recovering from bugs in \"repack\" but is a way to squeeze out\nmore redundancy from your pack because repeated \"repack -a\" may degrade\nthe pack efficiency over time.  Is \"reindex\" useful for a similar reason,\neven when the rev-cache mechanism is bug-free?\n\n> diff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\n> new file mode 100755\n\nExecutable documentation.\n\n> index 0000000..78d7218\n> --- /dev/null\n> +++ b/Documentation/technical/rev-cache.txt\n> @@ -0,0 +1,379 @@\n> +rev-cache\n> +=========\n> +\n> +The revision cache API ('rev-cache') provides a method for efficiently storing\n> +and accessing commit branch sections.  Such branch slices are defined by a\n> +series of top (interesting) and bottom (uninteresting) commits.  Each slice\n> +contains, per commit:\n> +\n> +* All intra-slice topological relations, encoded into path \"channels\" (see\n> +  'Mechanics' for full explanation).\n> +* Object meta-data: type, SHA-1, size, date (for commits).\n> +* Objects introduced in that commit, relative to slice (ie. only for non-start\n> +  commits).\n\n\"introduced\"?  That is a bit puzzling description to me, probably because\nof an untold assumption.\n\nDo you mean, in a two-commit history \"B builds on top of root A\", your\nslice lists objects by traversing topology from the top, so commit A is\nlisted, and the tree and its subtrees and blobs are \"introduced to the\nslice\", and then commit B is listed, along with its tree and associated\nobjects that have not been listed in the slice before commit B (namely,\nobjects commit B changed since commit A) are \"introduced to the slice (by\ncommit B)\"?\n\nYou can alley the above puzzlement by saying something like:\n\n\tEach slice stores information on commits and its associated\n\tobjects, in the topological order traversing from the top\n\tcommits.  For each commit, the following is recorded:\n\n> +Storage data structures are not exported, in part to keep git's global scope\n> +clean, but largely because they're pretty much useless outside of rev-cache.\n> +\n> +The API\n> +-------\n> +\n> +The API for 'rev-cache' is quite simple.  You can find the function prototypes\n> +in `revision.h`.\n\nDrop the first sentence and leave the judging of simplicity to the reader.\n\n> +Data Structures\n> +~~~~~~~~~~~~~~~\n> +\n> +The `rev_cache_info` struct holds all the options and flags for the API.\n> +\n> +----\n> +struct rev_cache_info {\n> +        /* generation flags */\n> +        unsigned objects : 1,\n> +                legs : 1,\n> +                make_index : 1;\n> +        \n> +        /* traversal flags */\n> +        unsigned save_unique : 1,\n> +                add_to_pending : 1,\n> +                add_names : 1;\n> +        \n> +        /* fuse options */\n> +        unsigned int ignore_size;\n> +};\n> +----\n> +\n> +The fields:\n> +\n> +`objects`::\n> +\tAdd non-commit objects to slice.\n> +\n> +`legs`::\n> +\tEnsure end commits have no children.\n\nWhat are \"end commits\"?\n\n> +`make_index`::\n> +\tIntegrate newly-made slice into index.\n> +\n> +`save_unique`::\n> +\tLoad non-commit objects into `unique` field of their associated\n> +\t`commit` object.\n\nWhat is \"unique\" field?  What is it used for?  Is it a list that can hold\nmany objects?\n\n> +`add_to_pending`::\n> +\tAppend unique non-commit objects to the `pending` object list in the\n> +\tpassed `rev_info` instance.\n> +\n> +`add_names`::\n> +\tInclude non-commit object names in the pending object entries (if\n> +\t`add_to_pending` is set), and set the `name` field of `blob` and `tree`\n> +\tobjects (if `save_unique`).\n> +\n> +`ignore_size`::\n> +\tIf non-zero, ignore slices with size greater or equal to this during\n> +fusion.\n> +\n> +Functions\n> +~~~~~~~~~\n> +\n> +`init_rci`::\n> +        Initiate a `rev_cache_info` struct to default options.\n\n\"Initialize\"?\n\nSpell it out like \"init_rev_cache_info()\".  It's not like you will be\ncalling this over and over again, and \"i\" is ambiguous between rev cache\ninfo and rev cache index.\n\n> +`make_cache_slice`::\n> +        Create a cache based on an a `rev_info` instance or `commit_list` s of\n> +        \"starts\" and \"ends\" (defaulting to latter if `rev_info` pointer is\n> +        NULL), copying the cache SHA-1 into a passed pointer if non-zero.  A\n\nWhat's \"cache SHA-1\"?  I imagine that rev-cache consists of one or more\ncache slices, and each slice is named after the hash value of its data,\nbut the documentation should not make _me_ guess.\n\nAlso a pointer is either NULL or non-NULL; it is never \"zero\".\n\n> +        `rev_cache_info` struct pointer can be passed to set options, while\n> +        passing NULL will set default options.  A last parameter can\n> +        optionally recieve the final cache hash.\n\nIs it just me who wish to see list of parameters on the head line, e.g.\n\n\tmake_cache_slice(struct rev_info *, ...)::\n\nto understand what the description is talking about better?\n\n> +`make_cache_index`::\n> +        Add a slice to the cache index.  Requires a file descriptor, the cache\n> +        hash and the file size.  Note that this is normally called by\n> +        `make_cache_slice` under the `make_index` option.\n\nA file descriptor points at what file?  The index is written to that\ndescriptor?  The slice is read from the descriptor?  What is \"cache hash\"?\nFile size of what file is taken as parameter?\n\n> +`get_cache_slice`::\n> +        Given a commit SHA-1 `get_cache_slice` will search the slice index and\n> +        return, if found, the cache-identifying SHA-1.\n\nIs there a \"slice index\"?  How does it relate to \"the cache index\" the\nearlier documentation mentioned in its description of the \"index\"\nsubcommand?\n\n> +`traverse_cache_slice`::\n> +        Traverse a specified cache slice based on:\n> +\n> +        * `rev_info` instance; options set in the `rev_cache_info` field.\n> +        * cache SHA-1 identifier\n> +        * a starting commit and commit work list\n> +        * date of oldest encountered interesting commit (passing 0 will tell\n> +          rev-cache to use defaults)\n> +        * current `slop` (this is a counter, a la `revision.c`, to determine\n> +          when to stop traversing; typically you can just pass 0 and rev-cache\n> +          will use default settings)\n> +        \n> ++\n> +The output is sent to a FILO `commit_list` \"queue\", while any end commits \n> +are passed back into the work list.  If the walk is not contained within the \n> +slice, commit boundaries are also inserted into \"work\".\n> +\n> +`start_from_slices`::\n> +        Will mark all start-commits in the specified cache slices with a given\n> +        flag, and add them to the rev pending list.  Will include all if no\n> +        slices are specified.\n> +\n> +`coagulate_cache_slices`::\n> +        Generate a slice based on the passed `rev_info` instance, replacing all\n> +        encountered slices with one (larger) slice.  The `ignore_size` field in\n> +        `rci`, if non-zero, will dictate which cache slice sizes to ignore in\n> +        both traversal and replacement.\n\n\"coagulate\"?  If you want to say \"fuse\", use that word consistently.\n\n> +Some Internals\n> +--------------\n> +\n> +Although you really don't need to know anything about how rev-cache actually\n> +does its magic shizz, a bit of background may go a long way if you're wading\n> +through the source.\n\nDrop these three lines.  People know that already when they are reading\nthis section.\n\n> +File Formats\n> +~~~~~~~~~~~~\n> +\n> +A slice has a basic fixed-size header, followed by a certain number of object\n> +entries, then a NULL-seperated list of object names.  Commits are sorted in\n> +topo-order, and each commit entry is followed by the objects added in that\n> +commit.\n\nWhat's in the header?  Is there a version number?\n\n> +struct object_entry {\n\nRename this to something more rev-cache specific, perhaps rev_cache_entry,\nas the name is already used for different purposes in pack-objects and\nfast-import.\n\n> +        unsigned type : 3;\n> +        unsigned is_end : 1;\n> +        unsigned is_start : 1;\n> +        unsigned uninteresting : 1;\n> +        unsigned include : 1;\n> +        unsigned flags : 1;\n> +        unsigned char sha1[20];\n> +        \n> +        unsigned merge_nr : 6;\n> +        unsigned split_nr : 7;\n> +        unsigned size_size : 3;\n> +        unsigned name_size : 3;\n> +        unsigned what_to_do : 5;\n> +        \n> +        uint32_t date;\n> +        uint16_t path;\n> +        \n> +        /* merge paths */\n> +        /* split paths */\n> +        /* size */\n> +        /* name index */\n> +};\n> +----\n> +\n> +An explanation of each field:\n> +\n> +`type`::\n> +\tObject type\n> +`is_end`::\n> +\tThe commit has some parents outside the cache slice (all if slice has\n> +\tlegs)\n> +`is_start`::\n> +\tThe commit has no children in cache slice\n\nYou said \"top\" and \"bottom\" in the documentation.  Perhaps use them\nhere as well for consistency?\n\n> +`uninteresting`::\n> +\tRun-time flag, used in traversal\n> +`include`::\n> +\tRun-time flag, used in traversal (initialization)\n> +`flags`::\n> +\tCurrently unused, extra bit\n> +`sha`::\n> +\tObject SHA-1 hash\n\nThat's `sha1` if I am reading the above display correctly.\n\n> +`merge_nr`::\n> +\tThe number of paths the current channel diverges into; the current path\n> +\tends upon any merge.\n> +`split_nr`::\n> +\tThe number of paths this commit ends; used on both merging and\n> +\tbranching.\n\nHow will an overflowing situation handled?\n\n> +`size_size`::\n> +\tNumber of bytes the object size takes up.\n> +`name_size`::\n> +\tNumber of bytes the name index takes up.\n> +`what_to_do`::\n> +\tCurrently space-filler, to properly align the struct fields.  Can\n> +\tpotentially be used for anything.\n\nYou seem to be assuming that 24-bit fields starting at merge_nr (begins at\noffset 21) will be packed and it is Ok that after this filler field date\nis aligned to multiple of 4.  I am not sure if that is a safe assumption.\n\nWe use 'unsigned long' for timestamps.  Is uint32_t sufficient?\n\nWhat is `path` (not \"merge paths\" nor \"split paths\" you explain next)?\nIs uint32_t sufficient?\n\n> +merge paths::\n> +\tThe path IDs (16-bit) that are to be created.\n> +split paths::\n> +\tThe path IDs (16-bit) that are to be ended.\n\nAre 65536 paths sufficient?  How will an overflowing situation handled?\n\n> +size::\n> +\tThe size split into the minimum number of bytes.\n> +name index::\n> +\tAn offset for the null-seperated, object name list at the end of the\n> +\tcache slice.  Also split into the minimum number of bytes.\n\nWhat does this mean?  1-to-8 bytes integer in network byte order?\n\nDid you consider using the variable-length size representation used by the\npack object layer (cf. encode_header() in builtin-pack-objects.c and\nunpack_object_header_buffer() in sha1_file.c)?\n\n> +\n> +Each path ID refers to an index in a 'path array', which stores the current\n> +status (eg. active, interestingness) of each channel.\n> +\n> +Due to topo-relations and boundary tracking, all of a commit's parents must be\n> +encountered before the path is reallocated.  This is achieved by using a\n> +counter system per merge: starting at the parent number, the counter is\n> +decremented as each parent is encountered (dictated by 'split paths'); at 0 the\n> +path is cleared.\n> +\n> +Boundary tracking is necessary because non-commits are stored relative to the\n> +commit in which they were introduced.  If a series of commits is not included\n> +in the output, the last interesting commit must be parsed manually to ensure\n> +all objects are accounted for.\n> +\n> +To prevent list-objects from recursing into trees that we've already taken care\n> +of, the flag `FACE_VALUE` is introduced.  An object with this flag is not\n> +explored (= \"taken at face value\"), significantly reducing I/O and processing\n> +time.\n\n> +(NSE)\n\nYou do not need this last line.  As 530e741 (Start preparing the API\ndocuments., 2007-11-24) mention, these were pointers to people who may\nknow enough information to fill in _undocumented_ territory.  You\ndocumented this API fairly completely.\n\nBesides, nobody would know who NSE is ;-).  Back then, there were only\nhandful of people, all of whom can be ientified by short names, who were\nresponsible for large body of internal API code that needed further\ndocumentation.\n"},{"id":"120053","messageId":"c77435a80908090701x3aa2584fq353df1886ed1b02@mail.gmail.com","threadId":"20466","inReplyTo":"7vbpmqi2d4.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-09T14:01:22Z","receivedAt":"2009-08-09T14:01:22Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Wow, thank you very much for your commentary!\n\nUnfortunately I don't have a stable internet connection this week\n(although I can get on at minimum once a day), but I'll rework the\ndocs today and upload a new patch for them tomorrow or the next day.\nI'll also fix the file permissions ;-)\n\nAs you said, I'll answer most of your questions in the revised docs,\nbut I have one question about the time field size.  git uses unsigned\nlong internally for its commit date, so it'd be limited by the 32bits\na long is on 32bit archs.  So, wouldn't the commit times effectively\nbe a uin32_t?  I mean if not I can change it; I just figured I'd save\nsome space.\n\nOther than that there shouldn't be an overflow problem, unless\nsomeone's merging over 63 branches in one go.  Maybe I'll expand that\na bit just in case though...\n\nThanks again,\n - Nick\n"},{"id":"120067","messageId":"7v63cw97jn.fsf@alter.siamese.dyndns.org","threadId":"20466","inReplyTo":"c77435a80908090701x3aa2584fq353df1886ed1b02@mail.gmail.com","subject":"Re: [PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-09T18:16:44Z","receivedAt":"2009-08-09T18:16:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nick Edelen <sirnot@gmail.com> writes:\n\n> As you said, I'll answer most of your questions in the revised docs,\n> but I have one question about the time field size.  git uses unsigned\n> long internally for its commit date, so it'd be limited by the 32bits\n> a long is on 32bit archs.  So, wouldn't the commit times effectively\n> be a uin32_t?\n\nThe current implementations may be either 32 or 64 bit, but at the on-disk\npermanent data structure level they are decimal integers of unlimited\nsize.  As the rev-cache, similarly to the index, is a local \"cache\" whose\nnature is transient (iow we can afford to say \"this new version of git\nupdates the file format for the rev-cache; your existing rev-cache will be\nconverted automatically\"), its data representation can have limitation\ntied to the implementation.  But the limitation should be documented.\n\nAs to defining the on-disk data format using C structure, I'd strongly\nsuggest looking at, learning from and mimicking how read-cache.c and\ncache.h handles struct ondisk_cache_entry.  I find writing out a structure\nwith bitfields as-is, like your patch does, quite iffy.\n\n> Other than that there shouldn't be an overflow problem, unless\n> someone's merging over 63 branches in one go.\n\nThe current Porcelains may not allow it, but at the data structure level\ncommit can have arbitrary number of parents, so that assumption is already\nbroken at the design level.  You need an escape hatch there.\n\n\"Because such a merge is so rare, walking the rev-cache that contains such\na commit gives a wrong result without any diagnosis to the caller\" is an\nunacceptable escape hatch.  It is perfectly fine if the escape hatch is\n\"because it is so rare, rev-cache marks commits involved in such a path,\nand walking the path falls back to actually reading the objects, without\nany performance benefit from the cache\".  It probably is also Ok if the\nescape hatch is \"because it is beyond the implementation limit, 'add'\ncommand errors out and rev-cache won't kick in for such a history.\"\n"},{"id":"120793","messageId":"op.uyr1b0w8tdk399@sirnot.private","threadId":"20466","inReplyTo":"op.uyb1uuu4tdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v2)] revision caching documentation: man page and technical discussion","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-16T22:41:52Z","receivedAt":"2009-08-16T22:41:52Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Before any code is introduced the full documentation is put forth.  This \nprovides a man page for the porcelain, and a technical doc in technical/.  The \nlatter describes the API, and discusses rev-cache's design, file format and \nmechanics.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n Documentation/git-rev-cache.txt       |  144 ++++++++\n Documentation/technical/rev-cache.txt |  614 +++++++++++++++++++++++++++++++++\n 2 files changed, 758 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..3479499\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,144 @@\n+git-rev-cache(1)\n+================\n+\n+NAME\n+----\n+git-rev-cache - Add, walk and maintain revision cache slices\n+\n+SYNOPSIS\n+--------\n+'git-rev-cache' COMMAND [options] [<commit>...]\n+\n+DESCRIPTION\n+-----------\n+The revision cache ('rev-cache') provides a mechanism for significantly\n+speeding up revision traversals.  It does this by creating an efficient\n+database (cache) of commits, their related objects and topological relations.\n+Independant of packs and the object store, this database is composed of\n+rev-cache \"slices\" -- each a different file storing a given segment of commit\n+history.  To map commits to their respective slices, a single index file is\n+kept for the rev-cache.\n+\n+'git-rev-cache' provides a front-end for the rev-cache mechanism, intended for\n+updating and maintaining rev-cache slices in the current repository.  New cache\n+slice files can be 'add'ed, to keep the cache up-to-date; individual slices can\n+be traversed; smaller slices can be 'fuse'd into a larger slice; and the\n+rev-cache index can be regenerated.\n+\n+COMMANDS\n+--------\n+\n+add\n+~~~\n+Add revisions to the cache by creating a new cache slice.  Reads a revision\n+list from the command line, formatted as: `START START ... \\--not END END ...`\n+\n+Options:\n+\n+\\--all::\n+\tInclude all refs in the new cache slice, like the \\--all option in\n+\t'rev-list'.\n+\n+\\--fresh::\n+\tExclude everything already in the revision cache, analogous to\n+\t\\--incremental in 'pack-objects'.\n+\n+\\--stdin::\n+\tRead newline-seperated revisions from the standard input.  Use \\--not\n+\tto exclude commits, as on the command line.\n+\n+\\--legs::\n+\tEnsure newly-generated cache slice has no partial ends.  This means that\n+\tno commit has partially cached parents, in that all its parents are\n+\tcached or none of them are.\n++\n+\\--legs will cause 'rev-cache' to expand potential slice end-points (creating\n+\"legs\") until this condition is met, simplifying the cache slice structure.\n+'rev-cache' itself does not care if a slice has legs or not, but the condition\n+may reduce the required complexity of other applications that might use the\n+revision cache.\n+\n+\\--no-objects::\n+\tNon-commit objects are normally included along with the commit with\n+\twhich they were introduced.  This is obviously very benificial, but can\n+\ttake longer in cache slice generation.  Using this option will disable\n+\tnon-commit object caching.\n++\n+\\--no-objects is mainly intended for debugging or development purposes, but may\n+find use in special situations (e.g. common traversal of only commits).\n+\n+walk\n+~~~~\n+Analogous to a slice-oriented 'rev-list', 'walk' will traverse a region in a\n+particular cache slice.  Interesting and uninteresting (delimited, as with\n+'rev-list', with \\--not) are specified on the command line, and output is the\n+same as vanilla 'rev-list'.\n+\n+Options:\n+\n+\\--objects::\n+\tLike 'rev-list', 'walk' will normally only list commits.  Use this\n+\toption to list non-commit objects as well, if they are present in the\n+\tcache slice.\n+\n+fuse\n+~~~~\n+Merge several cache slices into a single large slice, like 'repack' for\n+'rev-cache'.  On each invocation of 'add' a new file (\"slice\") is added to the\n+revision cache directory, and after several additions the directory may become\n+populated with many, relatively small slices.  Numerous smaller slices will\n+yield poorer performance than a one or two large ones, because of the overhead\n+of loading new slices into memory.\n+\n+Running 'fuse' every once in a while will solve this problem by coalescing all\n+the cache slices into one larger slice.  For very large projects, using\n+\\--ignore-size is advisable to prevent overly large cache slices.  Setting git\n+'config' option 'gc.revcache' to 1 will enable cache slice fusion upon garbage\n+collection.\n+\n+Note that 'fuse' uses the internal revision walker, so the options used in\n+fusion override those of the cache slices upon which it operates.  For example,\n+if some slices were generated with \\--no-objects, yet 'fuse' was performed with\n+non-commit objects, the resulting slice would still contain objects but would\n+take longer to generate.\n+\n+Options:\n+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--add tells it to start walking from the branch\n+\theads, effectively an `add --all --fresh; fuse` (pseudo-command).\n+\n+\\--no-objects::\n+\tAs in 'add', this option disables inclusion of non-commit objects.  If\n+\tsome cache slices do contain such objects, the information will be lost.\n+\n+\\--ignore-size[=N]::\n+\tDo not merge cache slices of size >=N (be aware that slices must be\n+\tmapped to memory).  N can have a suffix of \"k\" or \"m\", denoting N as\n+\tkilobytes and megabytes, respectively.  If N is not provided 'fuse'\n+\twill default to a size of ~25MB.\n+\n+index\n+~~~~~\n+Regenerate the revision cache index.  If the rev-cache index file associating\n+objects with cache slices gets corrupted, lost, or otherwise becomes unusable,\n+'index' will quickly regenerate the file.  It's most likely that this won't be\n+needed in every day use, as it is targeted towards debugging and development.\n+\n+alt\n+~~~\n+Create a cache slice pointer to another slice, identified by its full path:\n+`fuse path/to/other/slice`\n+\n+This command is useful if you have several repositories sharing a common\n+history.  Although space requirements for rev-cache are slim anyway, you can in\n+this situation reduce it further by using slice pointers, pointing to relavant\n+slices in other repositories.  Note that only one level of redirection is\n+allowed, and the slice pointer will break if the original slice is removed.\n+'fuse' will not touch slice pointers.\n+\n+DISCUSSION\n+----------\n+For an explanation of the API and its inner workings, see\n+link:technical/rev-cache.txt[technical info on rev-cache].\ndiff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\nnew file mode 100644\nindex 0000000..6e7c7f6\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,614 @@\n+rev-cache\n+=========\n+\n+The revision cache API ('rev-cache') provides a method for efficiently storing\n+and accessing commit branch sections.  Such branch slices are defined by a\n+series of start/top (interesting) and end/bottom (uninteresting) commits.  Each\n+slice contains information on commits in topological order.  Recorded with each\n+commit is:\n+\n+* All intra-slice topological relations, encoded into path \"channels\" (see\n+  'Mechanics' for full explanation).\n+* Object meta-data: type, SHA-1, size, date (for commits).\n+* Objects introduced by that commit, not present in the its cached parents.\n+\n+In addition to the API, basic structures are exported for the possibility of\n+direct access.\n+\n+The API\n+-------\n+You can find the function prototypes in `revision.h`.\n+\n+Data Structures\n+~~~~~~~~~~~~~~~\n+The `rev_cache_info` struct holds all the options and flags for the API.\n+\n+----\n+struct rev_cache_info {\n+\t/* generation flags */\n+\tunsigned objects : 1,\n+\t\tlegs : 1,\n+\t\tmake_index : 1,\n+\t\tfuse_me : 1;\n+\n+\t/* index inclusion */\n+\tunsigned overwrite_all : 1;\n+\n+\t/* traversal flags */\n+\tunsigned add_to_pending : 1;\n+\n+\t/* fuse options */\n+\tunsigned int ignore_size;\n+\n+\t/* reserved */\n+\tstruct rev_cache_slice_map *maps,\n+\t\t*last_map;\n+};\n+----\n+\n+The fields:\n+\n+`objects`::\n+\tAdd non-commit objects to slice.\n+\n+`legs`::\n+\tEnsure end/bottom commits have no children.\n+\n+`make_index`::\n+\tIntegrate newly-made slice into index.\n+\n+`fuse_me`::\n+\tThis is specified if a fuse is occuring, and slices are to be reused.\n+\tThis option requires `maps` and `last_maps` to be initialized.\n+\n+`overwrite_all`::\n+\tWhen a cache slice is added to the index, sometimes overlap occures\n+\tbetween it and other slices.  Normally, original index entries are kept\n+\tunless the new entry represents a start commit (older entries are more\n+\tlikely to lead to greater in-slice traversals).  This options overrides\n+\tthat, and updates all entries of the new slice.\n+\n+`add_to_pending`::\n+\tAppend unique non-commit objects to the `pending` object list in the\n+\tpassed `rev_info` instance.\n+\n+`add_names`::\n+\tInclude non-commit object names in the pending object entries if\n+\t`add_to_pending` is set.\n+\n+`ignore_size`::\n+\tIf non-zero, ignore slices with size greater or equal to this during\n+fusion.\n+\n+`maps`/`last_map`::\n+\tAn array of slice mappings, indexed by their id in the slice index\n+\theader, to be re-used with `fuse_me`.  `last_map` points to the last\n+\tmapping used, and should be initialized to 0.\n+\n+Functions\n+~~~~~~~~~\n+\n+init_rev_cache\n+^^^^^^^^^^^^^^\n+----\n+void init_rev_cache_info(\n+\tstruct rev_cache_info *rci OUT\n+)\n+----\n+\n+Initialize `rci` to default options.\n+\n+make_cache_slice\n+^^^^^^^^^^^^^^^^\n+----\n+int make_cache_slice(\n+\tstruct rev_cache_info *rci IN,\n+\tstruct rev_info *revs IN,\n+\tstruct commit_list **starts IN/OUT,\n+\tstruct commit_list **ends IN/OUT,\n+\tunsigned char *cache_sha1 OUT\n+)\n+----\n+\n+Create a cache slice based on either `revs` (if non-NULL) *or* the `starts` and\n+`ends` lists.  The actual list of start and end commits of the slice may be\n+different from the parameters, based on what defines the branch segment, and\n+this actual list is passed back through `starts` and `ends`.\n+\n+The cache slice is identified via a SHA-1 generated from the actual start/end\n+commit lists.  `cache_sha1`, if non-NULL, can recieve the cache slice name.\n+`rci` is used to specify generation options, but can be NULL if you want\n+`make_cache_slice` to fall back on defaults.  Returns 0 on success, non-zero on\n+failure.\n+\n+make_cache_index\n+^^^^^^^^^^^^^^^^\n+----\n+int make_cache_index(\n+\tstruct rev_cache_info *rci IN,\n+\tunsigned char *cache_sha1 IN,\n+\tint fd IN,\n+\tunsigned int size IN\n+)\n+----\n+\n+Add a slice to the rev-cache index.  `cache_sha1` is the identity hash of the\n+cache slice; `fd` is a file descriptor of the cache slice opened with\n+read/write privileges (the slice is not actually modified); `size` is the size\n+of the cache slice.  Although there are currently no options for index\n+updating, `rci` is a placeholder in case of future options.  Note that this\n+function is normally called by `make_cache_slice`.  Returns 0 on success,\n+non-zero on failure.\n+\n+open_cache_slice\n+^^^^^^^^^^^^^^^^\n+----\n+int open_cache_slice(\n+\tunsigned char *sha1 IN,\n+\tint flags IN\n+)\n+----\n+\n+Returns a file descriptor to a cache slice described by `sha1` hash, using\n+`flags` as the access mode.  This will follow cache slice pointers to one level\n+of indirection.\n+\n+get_cache_slice\n+^^^^^^^^^^^^^^^\n+----\n+unsigned char *get_cache_slice(\n+\tstruct commit *commit IN\n+)\n+----\n+\n+Given a commit object `get_cache_slice` will search the revision cache index\n+and return, if found, the cache slice SHA-1.\n+\n+traverse_cache_slice\n+^^^^^^^^^^^^^^^^^^^^\n+----\n+int traverse_cache_slice(\n+\tstruct rev_info *revs IN/OUT,\n+\tunsigned char *cache_sha1 IN,\n+\tstruct commit *commit IN,\n+\tunsigned long *date_so_far IN/OUT,\n+\tint *slop_so_far IN/OUT,\n+\tstruct commit_list ***queue OUT,\n+\tstruct commit_list **work IN/OUT\n+)\n+----\n+\n+Traverse a specified cache slice.  An explanation of the each field:\n+\n+`revs`::\n+\tThe revision walk instance.  `traverse_cache_slice` uses this for\n+\tgeneral options (e.g. which objects are included) and slice traversal\n+\toptions (in the `rev_cache_info` field).  If the `add_to_pending`\n+\toption is specified, non-commit objects are appended to the `pending`\n+\tobject list field.\n+\n+`cache_sha1`::\n+\tSHA-1 identifying the cache slice to use.  This can be taken directly\n+\tfrom `get_cache_slice`.\n+\n+`commit`::\n+\tThe current commit object in the revision walk, i.e. the commit which\n+\tinspired this slice traversal.  Although theoretically redundant in\n+\tview of the `work` list, this simplifies interaction with normal\n+\trevision walks, which pop commits from `work` before analyzing them.\n+\n+`date_so_far`::\n+\tThe date of the oldest encountered interesting commit.  Passing NULL\n+\twill let `traverse_cache_slice` use defaults.\n+\n+`slop_so_far`::\n+\tThe `slop` value, a la revision.c.  This is a counter used to determine\n+\twhen to stop traversing, based on how many extra uninteresting commits\n+\tshould be encountered.  NULL will enable defaults, as above.\n+\n+`queue`::\n+\tRefers to a pointer to the head of a FIFO commit list, recieving the\n+\tcommits we've seen and added.\n+\n+`work`::\n+\tA date-ordered list of commits that have yet to be processed (i.e. seen\n+\tbut not added).  Commits from here present in the slice are removed\n+\t(and, obviously, used as starting places for traversal), and any end\n+\tcommits encountered are inserted.\n+\n+starts_from_slices\n+^^^^^^^^^^^^^^^^^^\n+----\n+void starts_from_slices(\n+\tstruct rev_info *revs OUT,\n+\tunsigned int flags IN,\n+\tunsigned char *which IN,\n+\tint n IN\n+)\n+----\n+\n+Will mark start-commits in certain rev-cache slices with `flag`, and added them\n+to the pending list of `revs`.  If `n` is zero, `starts_from_slices` will use\n+all slices.  Otherwise `which` will specify an *unseperated* list of cache\n+SHA-1s to use (20 bytes each), and `n` will contain the number of slices (i.e.\n+20 * `n` = size of `which`).\n+\n+fuse_cache_slices\n+^^^^^^^^^^^^^^^^^\n+----\n+int fuse_cache_slices(\n+\tstruct rev_cache_info *rci IN,\n+\tstruct rev_info *revs IN\n+)\n+----\n+\n+Generate a slice based on `revs`, replacing all encountered slices with one\n+(larger) slice.  The `ignore_size` field in `rci`, if non-zero, will dictate\n+which cache slice sizes to ignore in both traversal and replacement.\n+\n+regenerate_cache_index\n+^^^^^^^^^^^^^^^^^^^^^^\n+----\n+int regenerate_cache_index(\n+\tstruct rev_cache_info *rci IN\n+)\n+----\n+\n+Remake the revision cache index, including all the slices.  Currently no\n+options in `rci` exist for index (re)generation, but some may develop in the\n+future.\n+\n+to/from_disked_rc_object/index_entry\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n+----\n+struct rc_object/index_entry *from_disked_rc_object/index_entry(\n+\tstruct rc_object/index_entry_ondisk *src IN,\n+\tstruct rc_object/index_entry *dst OUT\n+)\n+\n+struct rc_object/index_entry_ondisk *to_disked_rc_object/index_entry(\n+\tstruct rc_object/index_entry *src IN,\n+\tstruct rc_object/index_entry_ondisk *dst OUT\n+)\n+----\n+\n+Functions to convert between the internal and storage (`_ondisk`) versions of\n+object and index entry structures.  These are necessary for direct access to\n+the cache slices.  If NULL is provided for `dst` a statically allocated\n+structure is used, and a pointer to the struct is returned.  Otherwise the\n+functions return `dst`.\n+\n+Example Usage\n+-------------\n+\n+A few examples to demonstrate usage:\n+\n+.Creating a slice\n+----\n+/* pretend you're a porcelain for rev-cache reading from the command line */\n+struct rev_info revs;\n+struct rev_cache_info rci;\n+\n+init_revisions(&revs, 0);\n+init_rci(&rci);\n+\n+flags = 0;\n+for (i = 1; i < argc; i++) {\n+        if (!strcmp(argv[i], \"--not\"))\n+                flags ^= UNINTERESTING;\n+        else if(!strcmp(argv[i], \"--fresh\"))\n+                starts_from_slices(&revs, UNINTERESTING, 0, 0);\n+        else\n+                handle_revision_arg(argv[i], &revs, flags, 1);\n+}\n+\n+/* we want to explicitly set certain options */\n+rci.objects = 0;\n+\n+if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))\n+        printf(\"made slice!  it's called %s\\n\", sha1_to_hex(cache_sha1));\n+----\n+\n+.Traversing a slice\n+----\n+/* let's say you're walking the tree with a 'work' list of current heads and a\n+ * FILO output list 'out' */\n+out = 0;\n+outp = &out;\n+\n+while (work) {\n+        struct commit *commit = pop_commit(&work);\n+        struct object *object = &commit->object;\n+        unsigned char *cache_sha1;\n+\n+        if (cache_sha1 = get_cache_slice(object->sha1)) {\n+                /* note that this will instatiate any topo-relations\n+                 * as it goes */\n+                if (traverse_cache_slice(&revs, cache_sha1,\n+                        commit, 0, 0, /* use defaults */\n+                        &outp, &work) < 0)\n+                        die(\"I'm overreacting to a non-fatal cache error\");\n+        } else {\n+                struct commit_list *parents = commit->parents;\n+\n+                while (parents) {\n+                        struct commit *p = parents->item;\n+                        struct object *po = &p->object;\n+\n+                        parents = parents->next;\n+                        if (po->flags & UNINTERESTING)\n+                                continue;\n+\n+                        if (object->flags & UNINTERESTING)\n+                                po->flags |= UNINTERESTING;\n+                        else if (po->flags & SEEN)\n+                                continue;\n+\n+                        if (!po->parsed)\n+                                parse_commit(p);\n+                        insert_by_date(p, &work);\n+                }\n+\n+                if (object->flags & (SEEN | UNINTERESTING) == 0)\n+                        outp = &commit_list_insert(commit, outp)->next;\n+                object->flags |= SEEN;\n+        }\n+}\n+----\n+\n+Some Internals\n+--------------\n+For more advanced usage, the slice and index file(s) may be accessed directly.\n+Relavant structures are availabe in `rev-cache.h`.\n+\n+File Formats\n+~~~~~~~~~~~~\n+\n+Cache Slices\n+^^^^^^^^^^^^\n+A slice has a basic fixed-size header, followed by a certain number of object\n+entries, then a NULL-seperated list of object names.  Commits are sorted in\n+topo-order, and each commit entry is followed by the objects added in that\n+commit.\n+\n+----\n+         -- +--------------------------------+\n+header      | object number, etc...          |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+commit      | commit info                    |\n+entry       | path data                      |\n+            +--------------------------------+\n+            | tree/blob info                 |\n+            +--------------------------------+\n+            | ...                            |\n+         -- +--------------------------------+\n+...         ...\n+         -- +--------------------------------+\n+name list   | \\0some_file_name\\0             |\n+(note       +--------------------------------+\n+preceeding  | another_file\\0                 |\n+null)       ...                              |\n+            +--------------------------------+\n+----\n+\n+Here is the header:\n+\n+----\n+struct rc_cache_slice_header {\n+\tchar signature[8]; /* REVCACHE */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tuint16_t path_nr;\n+\tuint32_t size;\n+\n+\tunsigned char sha1[20];\n+\n+\tuint32_t names_size;\n+};\n+----\n+\n+Explanations:\n+\n+`signature`::\n+\tThe identifying signature of cache slice file.  Always \"REVCACHE\".\n+`version`::\n+\tThe version number, currently 1.\n+`ofs_objects`::\n+\tThe byte offset at which the commit/object listing starts.  Always\n+\tpresent at the 10th byte, regardless of file version.\n+`object_nr`::\n+\tThe total number of objects (commit + non-commit objects) present in\n+\tthe slice.\n+`path_nr`::\n+\tThe total number of paths/channels used in encoding the topological\n+\tdata.  Note that paths are reused (see 'Mechanics'), so there will\n+\tnever be more than a few hundred paths (if that) used.\n+`size`::\n+\tThe size of the slice *excluding* the name list.  In other words, the\n+\tsize of the portion mapped to memory.\n+`sha1`::\n+\tThe cache slice SHA-1.\n+`names_size`::\n+\tThe size of the name list.  `size` + `names_size` = size of slice\n+\n+Revision Cache Index\n+^^^^^^^^^^^^^^^^^^^^\n+The index is a single file that associates SHA-1s with cache slices and file\n+positions.  It is somewhat similar to pack-file indexes, containing a fanout\n+table and a list of index entries sorted by hash.\n+\n+----\n+         -- +--------------------------------+\n+header      | object #, cache #, etc.        |\n+         -- +--------------------------------+\n+sha1s of    | SHA-1                          |\n+slices      | ...                            |\n+         -- +--------------------------------+\n+fanout      | fanout[0x00]                   |\n+table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+            | fanout[0xff]                   |\n+         -- +--------------------------------+\n+index       | SHA-1 of object                |\n+entries     | index of cache slice SHA-1     |\n+            | position in cache slice        |\n+            +--------------------------------+\n+            |                                |\n+            ...\n+            +--------------------------------+\n+----\n+\n+The header:\n+\n+----\n+struct rc_index_header {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tunsigned char cache_nr;\n+\n+\tuint32_t max_date;\n+};\n+----\n+\n+Explanations:\n+\n+`signature`::\n+\tAlways \"REVINDEX\".\n+`version`::\n+\tVersion number, currently 1.\n+`ofs_objects`::\n+\tOffset at which the entry objects begin.  This is more obviously useful\n+\tin the index because the list of slice SHA-1s is variably-sized.\n+`object_nr`::\n+\tNumber of index entry objects present.\n+`cache_nr`::\n+\tNumber of cache slices to which the index maps, and hence the number of\n+slice SHA-1s listed.\n+`max_date`::\n+\tThe oldest commit represented in the index.  This is used to help speed\n+up lookup times by knowing what range of commits we definitely don't have\n+cached.  Normal usage of 'rev-cache' would leave no \"holes\" in its coverage of\n+commit history -- once a commit is cached, everything reachable from it should\n+be cached as well.  Most of the time refs are added to rev-cache simultaneous\n+as well.  This means that in most situations almost everything <= `max_date`\n+will be cached.\n+\n+Mechanics\n+~~~~~~~~~\n+\n+The most important part of rev-cache is its method of encoding topological\n+relations.  To ensure fluid traversal and reconstruction, commits are related\n+through high-level \"streams\"/\"channels\" rather than individual\n+interconnections.  Intuitively, rev-cache stores history the way gitk shows it:\n+commits strung up on lines, which interconnect at merges and branches.\n+\n+Each commit is associated to a given channel/path via a 'path id', and\n+variable-length fields govern which paths (if any) are closed or opened at that\n+object.  This means that topo-data can be preserved in only a few bytes extra\n+per object entry.  Other information stored per entry is the sha-1 hash, type,\n+date, size, name, and status in cache slice.  Here is format of an object\n+entry, both on-disk and in-memory:\n+\n+----\n+struct object_entry {\n+        unsigned type : 3;\n+        unsigned is_end : 1;\n+        unsigned is_start : 1;\n+        unsigned uninteresting : 1;\n+        unsigned include : 1;\n+        unsigned flags : 1;\n+        unsigned char sha1[20];\n+\n+        unsigned char merge_nr;\n+        unsigned char split_nr;\n+        unsigned size_size : 3;\n+        unsigned name_size : 3;\n+\n+        uint32_t date;\n+        uint16_t path;\n+\n+        /* merge paths */\n+        /* split paths */\n+        /* size */\n+        /* name index */\n+};\n+----\n+\n+An explanation of each field:\n+\n+`type`::\n+\tObject type\n+`is_end`::\n+\tThe commit has some parents outside the cache slice (all if slice has\n+\tlegs)\n+`is_start`::\n+\tThe commit has no children in cache slice\n+`uninteresting`::\n+\tRun-time flag, used in traversal\n+`include`::\n+\tRun-time flag, used in traversal (initialization)\n+`flags`::\n+\tCurrently unused, extra bit\n+`sha1`::\n+\tObject SHA-1 hash\n+\n+`merge_nr`::\n+\tThe number of paths the current channel diverges into; the current path\n+\tends upon any merge.\n+`split_nr`::\n+\tThe number of paths this commit ends; used on both merging and\n+\tbranching.\n+`size_size`::\n+\tNumber of bytes the object size takes up.\n+`name_size`::\n+\tNumber of bytes the name index takes up.\n+\n+`date`::\n+\tThe date of the commit.\n+`path`::\n+\tThe path ID of the channel with which this commit is associated.\n+\n+merge paths::\n+\tThe path IDs (16-bit) that are to be created.  Overflow is not a\n+\tproblem as path IDs are reused, leaving even complicated projects to\n+\tconsume no more than a few hundred IDs.\n+split paths::\n+\tThe path IDs (16-bit) that are to be ended.\n+size::\n+\tThe size split into the minimum number of bytes.  That is, 1-8 bytes\n+\trepresenting the size, least-significant byte first.\n+name index::\n+\tAn offset for the null-seperated, object name list at the end of the\n+\tcache slice.  Also split into the minimum number of bytes.\n+\n+Each path ID refers to an index in a 'path array', which stores the current\n+status (eg. active, interestingness) of each channel.\n+\n+Due to topo-relations and boundary tracking, all of a commit's parents must be\n+encountered before the path is reallocated.  This is achieved by using a\n+counter system per merge: starting at the parent number, the counter is\n+decremented as each parent is encountered (dictated by 'split paths'); at 0 the\n+path is cleared.\n+\n+Boundary tracking is necessary because non-commits are stored relative to the\n+commit in which they were introduced.  If a series of commits is not included\n+in the output, the last interesting commit must be parsed manually to ensure\n+all objects are accounted for.\n+\n+To prevent list-objects from recursing into trees that we've already taken care\n+of, the flag `FACE_VALUE` is introduced.  An object with this flag is not\n+explored (= \"taken at face value\"), significantly reducing I/O and processing\n+time.\n-- \ntg: (797cc19..) t/revcache/docs (depends on: t/revcache/integration)\n"}]}