{"thread":{"id":"20628","subject":"[PATCH 1/6 (v4)] man page and technical discussion for rev-cache","startedAt":"2009-08-17T12:31:18Z","lastAt":"2009-10-19T20:26:32Z","messageCount":8,"participants":["Nick Edelen","Nicolas Pitre","Junio C Hamano"],"isPatch":true,"patchVersion":4,"patchTotal":6},"messages":[{"id":"120871","messageId":"op.uys3qgmitdk399@sirnot.private","threadId":"20628","inReplyTo":null,"subject":"[PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-17T12:31:18Z","receivedAt":"2009-08-17T12:31:18Z","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: (c3b7310..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"121047","messageId":"alpine.LFD.2.00.0908172227040.6044@xanadu.home","threadId":"20628","inReplyTo":"op.uys3qgmitdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-18T02:34:52Z","receivedAt":"2009-08-18T02:34:52Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 17 Aug 2009, Nick Edelen wrote:\n\n> diff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\n> new file mode 100644\n> index 0000000..3479499\n> --- /dev/null\n> +++ b/Documentation/git-rev-cache.txt\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\nWhy not using --incremental here as wel then?\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\nI'm not sure I understand this.  As a user, should I care?\n\n\nNicolas\n"},{"id":"121084","messageId":"op.uyuwkmv0tdk399@sirnot.private","threadId":"20628","inReplyTo":"op.uys3qgmitdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-18T11:51:48Z","receivedAt":"2009-08-18T11:51:48Z","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       |  162 +++++++++\n Documentation/technical/rev-cache.txt |  614 +++++++++++++++++++++++++++++++++\n 2 files changed, 776 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..dcd2be5\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,162 @@\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/\\--incremental::\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.  99.9% of users can ignore this command.\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+Output:\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\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+Output:\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputed on `stderr`, the object hashes\n+and names on `stdout`.\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+Output:\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\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: (bc586d3..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"121379","messageId":"op.uyzwxpmbtdk399@sirnot","threadId":"20628","inReplyTo":"op.uyuwkmv0tdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-21T04:47:41Z","receivedAt":"2009-08-21T04:47:41Z","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---\nincluded notes on (inconsequential) discrepencies in the manners of walking\nbetween rev-cache and rev-list.\n\n Documentation/git-rev-cache.txt       |  176 +++++++++\n Documentation/technical/rev-cache.txt |  634 +++++++++++++++++++++++++++++++++\n 2 files changed, 810 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..936d1f3\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,176 @@\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/\\--incremental::\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.  99.9% of users can ignore this command.\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+Output:\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\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+Output:\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputed on `stderr`, the object hashes\n+and names on `stdout`.\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+Output:\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\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+NOTES\n+-----\n+In certain circumstances there may be some inconsistencies with object names\n+between cached and non-cached walks.  Specifically, if two objects in commit\n+tree have the same content (= same SHA-1); or if objects of the same SHA-1 are\n+introduced independantly in parallel branches.\n+\n+In the first case rev-cache will use the name of the youngest file, while\n+vanilla rev-list will return the name of the entry first encountered in walking\n+the tree.  The latter case is a result of rev-cache's internal topological\n+ordering: the difference is the same between sorted and unsorted revision walks.\n+\n+See 'Discussion' for the underlying reasons for the discrepencies.\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..91fce8b\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,634 @@\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+\n+Notes\n+~~~~~\n+\n+Due to rev-cache's internal storage format, walking may lead to some\n+discrepencies between cached and uncached repositories.  Although noticeable to\n+users directly calling rev-list, these are unused or corner cases and\n+internally a non-issue.\n+\n+First note that rev-cache records commits in topological order.  Large portions\n+of commit history will already be sorted topologically in the revision walk,\n+yielding a different output for unsorted calls to rev-list.  A more obscure\n+consquence occurs when two objects of the same SHA-1, but different name, are\n+introduced seperately in parallel branches: different names might be shown for\n+that object depending on which object entry was encountered first.\n+\n+A similar disparity arises when two objects of same SHA-1/different name are\n+present in the same tree structure.  rev-cache, walking objects as they were\n+introduced, lists the youngest file's name; rev-list, walking the full trees\n+each commit, shows the first file encountered.\n-- \ntg: (f55325c..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"121396","messageId":"7vab1tk4wh.fsf@alter.siamese.dyndns.org","threadId":"20628","inReplyTo":"op.uyzwxpmbtdk399@sirnot","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-21T07:22:22Z","receivedAt":"2009-08-21T07:22:22Z","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> +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\n\"independent\"\n\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\nWhat is the practical use of traversing a single individual slice?\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/\\--incremental::\n> +\tExclude everything already in the revision cache, analogous to\n> +\t\\--incremental in 'pack-objects'.\n\nWrite these on separate lines, like this:\n\n\t--fresh::\n        --incremental::\n        \tExclude ...\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.  99.9% of users can ignore this command.\n\nBad presentation.  I am sure 99.9% of readers would not understand what\nyou are talking about, and I am sure I am among them.\n\nA \"partial end\" is an unexplained and undefined term at this point, and\nyou use it to explain what --legs is about in the first sentence.  This\nresults in giving _no_ information to the reader with the first sentence.\nThen, the second sentence , by starting with \"This means that\", attempts\nto define the unexplained term \"partial end\" by rephrasing it differently.\n\nSuch a presentation structure is good only if\n\n  1. the rephrased explanation (\"all or none of the parents are cached\")\n     is much more understandable the new unfamiliar term (\"partial end\");\n\n  2. the new unfamiliar term is much concise; and\n\n  3. the new unfamiliar term is used repeatedly in other parts of the\n     documentation.\n\nBut the explanation of --legs does not satisfy any of the above three.  It\nis not clear what it means for a commit to get its parents \"cached\"; the\nrephasing explanation is not much longer than the \"partial end\", and you\ndo not use \"partial ends\" in order to further explain other things\nanywhere in the documentation.\n\nIn such a case, you are better off dropping the first cryptic \"has no\npartial ends\" together with \"This means\" and introduce the concept you are\nintroducing more directly.  And because you would be dropping the latter\nhalf of the first sentence and \"This means that\", you can do this with\nlonger and easier to understand explanation.  Perhaps...\n\n\t--legs::\n        \tMake sure each and every commit in the created cache slice\n        \teither has its all parents in the same slice, or none of\n        \tits parents in it.\n\nI said \"in the _same_ slice\" in my version, but I do not know if that is\nwhat you meant by \"cached\".  Maybe you meant \"in _some_ slice\" instead.\nThat is the kind of clarification you can afford to make, once you stop\nintroducing otherwise unused term like \"partial ends\" here.\n\nAlso, I do not find the word \"legs\" particularly \"click\" with the \"no\npartial ends\" concept you are trying to define.  It often is good to use a\nverb that can be made into adjective for things like this.  How about\ncalling this \"--close\"?\n\n\tClose the newly created cache slice. i.e. make sure that each and\n\tevery commit in the slice has its all parents in the same slice,\n\tor none of its parents in it.\n\nThen later you could use \"a closed slice\" (vs \"an open slice\"), if the\ndistinction between a slice that was created with --legs and without\nbecomes useful.\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> +Output:\n> +\n> +'walk' will simply dump the contents of the output commit list, work list, and\n> +pending object array.  The headers are outputed on `stderr`, the object hashes\n> +and names on `stdout`.\n\nWhat is the practical use of traversing a single individual slice?  For\nexample, if you have a slice created by an earlier 'add' that was run\nwith, say, v1.6.0..v1.6.1 as the parameter (so presumably it will know\nonly about the commits and their associated objects between these\nversions), and you tell the command to 'walk' v1.0.0..v1.3.0 on the slice,\nwhat happens?\n\nWhat I am getting at is if this command is also mainly intended for\ndebugging this command, just like --no-objects option above.\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\nAt this point, the reader has already read the explanation of what a slice\nis, so it is easier to read if you said \"... a new slice is added to the ...\"\nhere, without using ambiguous but more familiar word \"file\".\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\nI am still unhappy with the word \"--ignore-size\".  Its the threashold,\nexisting slices larger than which will be kept uncoalesced; the option is\nnot about \"ignoring\" the size, but means entirely opposite.  The command\nactively pays attention to the size while operating under this option.\nPerhaps --keep-size might be slightly more appropriate; even though \"size\"\ndoes not tell if it is a lower bound or upper bound, at least it makes it\nclear that it is about keeping them from getting collapsed.\n\n> +Note that 'fuse' uses the internal revision walker, so the options used in\n\nInternal to what?  Internal to git?  Internal to rev-cache creator?\nInternal to the fuze command implementation (and if so, why)?\n\n> +This command prints the SHA-1 of the new slice on `stdout`, and information\n> +about its work on `stderr` -- specifically which files it's removing.\n\nWhen talking about the \"standard output\" in general terms, I'd prefer\nspelling it out, reserving `stdout` as a precise technical term to refer\nto the standard output stream from programming environments used only when\ndiscussing actually programming naming the stream with that particular\nspelling.\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\nPerhaps \"reindex\"?\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\nHmm, why is this inconsistency?  I think other symbolic-link-like\nconstruct we have follow 5 levels or so...\n\nHow would you break the dependency once you make your rev-cache dependent\non another?\n\n\n\n> diff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt\n> new file mode 100644\n> index 0000000..91fce8b\n> --- /dev/null\n> +++ b/Documentation/technical/rev-cache.txt\n> @@ -0,0 +1,634 @@\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\nIt is often necessary to list synonyms like \"start/top (interesting)\" in\ndescription when a concept has been widely used before being formalized\nand different people used different words to refer to the same concept.\nBut here you are introducing the rev-cache and its related concepts for\nthe first time.  You don't have to give three words to each of these two\nconcepts from the beginning.  Instead, pick one unambiguous pair and stick\nto them everywhere, in the code, in the input/output to/from the commands,\nand in the documentation.\n\nIf it is important to be able to distinguish \"uninteresting\"-ness used by\nrev-list and \"bottom\"-ness used by rev-cache, then I would suggest to use\n\"top/bottom\".  Otherwise, I would suggest \"interesting/uninteresting\".\n"},{"id":"122631","messageId":"op.uzv4b4gxtdk399@sirnot.private","threadId":"20628","inReplyTo":"op.uyzwxpmbtdk399@sirnot","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-09-07T14:10:43Z","receivedAt":"2009-09-07T14:10:43Z","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---\nSlight clean-up of man page.\n\n Documentation/git-rev-cache.txt       |  190 ++++++++++\n Documentation/technical/rev-cache.txt |  634 +++++++++++++++++++++++++++++++++\n 2 files changed, 824 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..5a713ad\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,190 @@\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+\n+\\--all::\n+\tInclude all refs in the new cache slice, like the \\--all option in\n+\t'rev-list'.\n+\n+\\--fresh/\\--incremental::\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.  99.9% of users can ignore this command.\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+Output\n+^^^^^^\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\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+\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+Output\n+^^^^^^\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputed on `stderr`, the object hashes\n+and names on `stdout`.\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.  This can be\n+set to run on garbage collection; see 'Automation' for more info.\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+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--all tells it to start walking from the branch\n+\theads, effectively a `add --all --fresh; fuse`\n+\t(pseudo-revcache-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 specified in `revcache.ignoresize`, or ~25MB if\n+\tthe config var is not set.\n+\n+Output\n+^^^^^^\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\n+\n+Automation\n+^^^^^^^^^^\n+\n+Set the git configuration variable `gc.revcache` to run 'fuse' on garbage\n+collection.  The arguments passed are `fuse \\--all \\--ignore-size`; i.e. 'gc'\n+will keep everything cached into size-regulated slices.\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+NOTES\n+-----\n+In certain circumstances there may be some inconsistencies with object names\n+between cached and non-cached walks.  Specifically, if two objects in a commit\n+tree have the same content (= same SHA-1); or if objects of the same SHA-1 are\n+introduced independantly in parallel branches.\n+\n+In the first case rev-cache will use the name of the youngest file, while\n+vanilla rev-list will return the name of the entry first encountered in walking\n+the tree.  The latter case is a result of rev-cache's internal topological\n+ordering: the difference is the same between sorted and unsorted revision walks.\n+\n+See 'Discussion' for the underlying reasons for the discrepencies.\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..91fce8b\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,634 @@\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+\n+Notes\n+~~~~~\n+\n+Due to rev-cache's internal storage format, walking may lead to some\n+discrepencies between cached and uncached repositories.  Although noticeable to\n+users directly calling rev-list, these are unused or corner cases and\n+internally a non-issue.\n+\n+First note that rev-cache records commits in topological order.  Large portions\n+of commit history will already be sorted topologically in the revision walk,\n+yielding a different output for unsorted calls to rev-list.  A more obscure\n+consquence occurs when two objects of the same SHA-1, but different name, are\n+introduced seperately in parallel branches: different names might be shown for\n+that object depending on which object entry was encountered first.\n+\n+A similar disparity arises when two objects of same SHA-1/different name are\n+present in the same tree structure.  rev-cache, walking objects as they were\n+introduced, lists the youngest file's name; rev-list, walking the full trees\n+each commit, shows the first file encountered.\n-- \ntg: (0130fb5..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"124157","messageId":"op.u061a6ndtdk399@sirnot.ed.ac.uk","threadId":"20628","inReplyTo":"op.uyuwkmv0tdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-02T22:12:33Z","receivedAt":"2009-10-02T22:12:33Z","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---\nclean resend of patches.  this set fixes a small bug in graft handling, and\ntweaks test for compatability.\n\n  Documentation/git-rev-cache.txt       |  190 ++++++++++\n  Documentation/technical/rev-cache.txt |  634 +++++++++++++++++++++++++++++++++\n  2 files changed, 824 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..5a713ad\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,190 @@\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+\n+\\--all::\n+\tInclude all refs in the new cache slice, like the \\--all option in\n+\t'rev-list'.\n+\n+\\--fresh/\\--incremental::\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.  99.9% of users can ignore this command.\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+Output\n+^^^^^^\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\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+\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+Output\n+^^^^^^\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputed on `stderr`, the object hashes\n+and names on `stdout`.\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.  This can be\n+set to run on garbage collection; see 'Automation' for more info.\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+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--all tells it to start walking from the branch\n+\theads, effectively a `add --all --fresh; fuse`\n+\t(pseudo-revcache-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 specified in `revcache.ignoresize`, or ~25MB if\n+\tthe config var is not set.\n+\n+Output\n+^^^^^^\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\n+\n+Automation\n+^^^^^^^^^^\n+\n+Set the git configuration variable `gc.revcache` to run 'fuse' on garbage\n+collection.  The arguments passed are `fuse \\--all \\--ignore-size`; i.e. 'gc'\n+will keep everything cached into size-regulated slices.\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+NOTES\n+-----\n+In certain circumstances there may be some inconsistencies with object names\n+between cached and non-cached walks.  Specifically, if two objects in a commit\n+tree have the same content (= same SHA-1); or if objects of the same SHA-1 are\n+introduced independantly in parallel branches.\n+\n+In the first case rev-cache will use the name of the youngest file, while\n+vanilla rev-list will return the name of the entry first encountered in walking\n+the tree.  The latter case is a result of rev-cache's internal topological\n+ordering: the difference is the same between sorted and unsorted revision walks.\n+\n+See 'Discussion' for the underlying reasons for the discrepencies.\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..91fce8b\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,634 @@\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+\n+Notes\n+~~~~~\n+\n+Due to rev-cache's internal storage format, walking may lead to some\n+discrepencies between cached and uncached repositories.  Although noticeable to\n+users directly calling rev-list, these are unused or corner cases and\n+internally a non-issue.\n+\n+First note that rev-cache records commits in topological order.  Large portions\n+of commit history will already be sorted topologically in the revision walk,\n+yielding a different output for unsorted calls to rev-list.  A more obscure\n+consquence occurs when two objects of the same SHA-1, but different name, are\n+introduced seperately in parallel branches: different names might be shown for\n+that object depending on which object entry was encountered first.\n+\n+A similar disparity arises when two objects of same SHA-1/different name are\n+present in the same tree structure.  rev-cache, walking objects as they were\n+introduced, lists the youngest file's name; rev-list, walking the full trees\n+each commit, shows the first file encountered.\n-- \ntg: (5bbb081..) t/revcache/docs (depends on: t/revcache/integration)\n"},{"id":"125416","messageId":"4ADCCB78.8090201@gmail.com","threadId":"20628","inReplyTo":"op.uys3qgmitdk399@sirnot.private","subject":"Re: [PATCH 1/6 (v4)] man page and technical discussion for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-10-19T20:26:32Z","receivedAt":"2009-10-19T20:26: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---\nsorry about the long interval; I haven't got internet in my flat yet and uni\ntends to take you over.  anyway, clean resend of patches (attempt 2).  this set\nfixes a small bug in graft handling (ie. test t6001), and tweaks test for\ncompatability.\n\n Documentation/git-rev-cache.txt       |  190 ++++++++++\n Documentation/technical/rev-cache.txt |  634 +++++++++++++++++++++++++++++++++\n 2 files changed, 824 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/git-rev-cache.txt b/Documentation/git-rev-cache.txt\nnew file mode 100644\nindex 0000000..5a713ad\n--- /dev/null\n+++ b/Documentation/git-rev-cache.txt\n@@ -0,0 +1,190 @@\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+\n+\\--all::\n+\tInclude all refs in the new cache slice, like the \\--all option in\n+\t'rev-list'.\n+\n+\\--fresh/\\--incremental::\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.  99.9% of users can ignore this command.\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+Output\n+^^^^^^\n+\n+On `stderr` 'add' outputs general information about the generated slice,\n+including the number of objects and paths, and the start/end commits (prefix S\n+indicates start, E an end).  Through `stdout` it emits only the SHA-1 of the\n+slice.\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+\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+Output\n+^^^^^^\n+\n+'walk' will simply dump the contents of the output commit list, work list, and\n+pending object array.  The headers are outputed on `stderr`, the object hashes\n+and names on `stdout`.\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.  This can be\n+set to run on garbage collection; see 'Automation' for more info.\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+\n+\\--all::\n+\tNormally fuse will only include everything that's already in the\n+\trevision cache.  \\--all tells it to start walking from the branch\n+\theads, effectively a `add --all --fresh; fuse`\n+\t(pseudo-revcache-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 specified in `revcache.ignoresize`, or ~25MB if\n+\tthe config var is not set.\n+\n+Output\n+^^^^^^\n+\n+This command prints the SHA-1 of the new slice on `stdout`, and information\n+about its work on `stderr` -- specifically which files it's removing.\n+\n+Automation\n+^^^^^^^^^^\n+\n+Set the git configuration variable `gc.revcache` to run 'fuse' on garbage\n+collection.  The arguments passed are `fuse \\--all \\--ignore-size`; i.e. 'gc'\n+will keep everything cached into size-regulated slices.\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+NOTES\n+-----\n+In certain circumstances there may be some inconsistencies with object names\n+between cached and non-cached walks.  Specifically, if two objects in a commit\n+tree have the same content (= same SHA-1); or if objects of the same SHA-1 are\n+introduced independantly in parallel branches.\n+\n+In the first case rev-cache will use the name of the youngest file, while\n+vanilla rev-list will return the name of the entry first encountered in walking\n+the tree.  The latter case is a result of rev-cache's internal topological\n+ordering: the difference is the same between sorted and unsorted revision walks.\n+\n+See 'Discussion' for the underlying reasons for the discrepencies.\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..91fce8b\n--- /dev/null\n+++ b/Documentation/technical/rev-cache.txt\n@@ -0,0 +1,634 @@\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+\n+Notes\n+~~~~~\n+\n+Due to rev-cache's internal storage format, walking may lead to some\n+discrepencies between cached and uncached repositories.  Although noticeable to\n+users directly calling rev-list, these are unused or corner cases and\n+internally a non-issue.\n+\n+First note that rev-cache records commits in topological order.  Large portions\n+of commit history will already be sorted topologically in the revision walk,\n+yielding a different output for unsorted calls to rev-list.  A more obscure\n+consquence occurs when two objects of the same SHA-1, but different name, are\n+introduced seperately in parallel branches: different names might be shown for\n+that object depending on which object entry was encountered first.\n+\n+A similar disparity arises when two objects of same SHA-1/different name are\n+present in the same tree structure.  rev-cache, walking objects as they were\n+introduced, lists the youngest file's name; rev-list, walking the full trees\n+each commit, shows the first file encountered.\n-- \ntg: (e7578ba..) t/revcache/docs (depends on: t/revcache/integration)\n"}]}