Re: [PATCH 1/5] revision caching documentation: man page and technical discussion

> Before any code is introduced the full documentation is put forth.  This 
> provides a man page for the porcelain, and a technical doc in technical/.  The 
> latter describes the API, and discusses rev-cache's design, file format and 
> mechanics.
>
> Signed-off-by: Nick Edelen <sirnot@gmail.com>
>
> ---
>  Documentation/rev-cache.txt           |   51 +++++
>  Documentation/technical/rev-cache.txt |  336 +++++++++++++++++++++++++++++++++
>  2 files changed, 387 insertions(+), 0 deletions(-)
>   

> diff --git a/Documentation/rev-cache.txt b/Documentation/rev-cache.txt
> new file mode 100755
> index 0000000..64bd051
> --- /dev/null
> +++ b/Documentation/rev-cache.txt
> @@ -0,0 +1,51 @@
> +rev-cache porcelain
> +===================
> +
> +A front end for the rev-cache API is provided with the builtin utility 
> +`rev-cache`.  It is mainly intended for cache slice generation and maintenance, 
> +but can also walk commits within a slice.  At the moment it is not particularly 
> +advanced, but is sufficient for repository administration.
>   

> +
> +It's general syntax is:
> +
> +`git-rev-cache COMMAND [options] [<commit-id>...]`
> +
> +With the commands:
>   

> +
> +`add`::
> +	Add revisions to the cache.  Reads commit ids from stdin, formatted as:
> +	`END END ... \--not START START ...`
>   

> ++
> +Options:
> +
> +`\--all`:: Include all heads as ends.
> +`\--fresh`:: Exclude everything already in a cache slice.
>   

> +`\--noobjects`:: Don't include non-commit objects.
> +
> +`walk`::
> +	Walk a cache slice based on set of commits; formatted as add.
>   

> ++
> +Options:
> +
> +`\--objects`:: Include non-commit objects in traversal.
> +
>   

> ++
> +Options:
> +
> +`\--all`:: Include all objects in repository.  Will only traverse as of cache 
> +ends if this is not specified.
>   

> +`\--noobjects`:: Don't include non-commit objects.
> +`\--ignore-size[=N]`:: Do not fuse slices of file size >= `N`.  If `N` is not 
> +given the cutoff size defaults to ~5MB.
> +
> +`index`::
> +	Regenerate the cache index.
> +
> +
> +For an explanation of the API and its inner workings, see 
> +link:technical/rev-cache.txt[technical info on rev-cache]
> diff --git a/Documentation/technical/rev-cache.txt b/Documentation/technical/rev-cache.txt
> new file mode 100755
> index 0000000..e95ec89
> --- /dev/null
> +++ b/Documentation/technical/rev-cache.txt
> @@ -0,0 +1,336 @@
> +rev-cache
> +=========
> +
> +The revision cache API ('rev-cache') provides a method for efficiently storing 
> +and accessing commit branch sections.  Such branch slices are defined by a 
> +series of top (interesting) and bottom (uninteresting) commits.  Each slice 
> +contains, per commit:
> +
> +* All intra-slice topological relations, encoded into path "channels" (see 
> +  'Mechanics' for full explanation).
> +* Object meta-data: type, SHA-1, size, date (for commits).
> +* Objects introduced in that commit, relative to slice (ie. only for non-start 
> +  commits).
> +
> +Storage data structures are not exported, in part to keep git's global scope 
> +clean, but largely because they're pretty much useless outside of rev-cache.
> +
> +The API
> +-------
> +
> +The API for 'rev-cache' is quite simple.  You can find the function prototypes 
> +in `revision.h`.
> +
> +Data Structures
> +~~~~~~~~~~~~~~~
> +
> +The `rev_cache_info` struct holds all the options and flags for the API.
> +
> +----
> +struct rev_cache_info {
> +        /* generation flags */
> +        unsigned objects : 1, 
> +                legs : 1, 
> +                make_index : 1;
> +        
> +        /* traversal flags */
> +        unsigned save_unique : 1, 
> +                add_to_pending : 1;
> +        
> +        /* fuse options */
> +        unsigned int ignore_size;
> +};
> +----
> +
> +The fields:
> +
> +`objects`:: Add non-commit objects to slice.
> +`legs`:: Ensure bottoms have no childrens.
>   

> +Functions
> +~~~~~~~~~
> +
> +`init_rci`::
> +
> +        Initiate a `rev_cache_info` struct to default options.  
> +
> +`make_cache_slice`::
> +
> +        Create a cache based on an a `rev_info` instance or `commit_list` s of 
> +        "tops" and "bottoms" (defaulting to latter if `rev_info` pointer is 
> +        NULL), copying the cache SHA-1 into a passed pointer if non-zero.  A 
> +        `rev_cache_info` struct pointer can be passed to set options, while 
> +        passing NULL will set default options.  A last parameter can 
> +        optionally recieve the final cache hash.
> +
> +`make_cache_index`::
> +
> +        Add a slice to the cache index.  Requires a file descriptor, the cache 
> +        hash and the file size.  Note that this is normally called by 
> +        `make_cache_slice` under the `make_index` option.
> +
> +`get_cache_slice`::
> +
> +        Given a commit SHA-1 `get_cache_slice` will search the slice index and 
> +        return, if found, the cache-identifying SHA-1.
> +
> +`traverse_cache_slice`::
> +
> +        Traverse a specified cache slice based on:
> +
> +        * `rev_cache_info` instance (optional)
> +        * cache SHA-1 identifier
> +        * `rev_info` instance
> +        * a starting commit and commit work list
> +        * date of oldest encountered interesting commit
> +        * current `slop` (this and above mainly used in integration with 
> +          revision walker)
>   

> +        
> ++
> +The output is sent to a FILO `commit_list` "queue", while any bottom commits 
> +are passed back into the work list.  If the walk is not contained within the 
> +slice, commit boundaries are also inserted into "work".
> +
> +`tops_from_slices`::
> +
> +        Will mark all top-commits in the specified cache slices with a given 
> +        flag, and add them to the rev pending list.  Will include all if no 
> +        slices are specified.
> +
> +`coagulate_cache_slices`::
> +
> +        Generate a slice based on the passed `rev_info` instance, replacing all 
> +        encountered slices with one (larger) slice.  The `ignore_size` field in 
> +        `rci`, if non-zero, will dictate which cache slice sizes to ignore in 
> +        both traversal and replacement.
> +
> +`regenerate_index`::
> +
> +        Remake cache index.
> +
> +Example Usage
> +-------------
> +
> +A few examples to demonstrate usage:
> +
> +.Creating a slice
> +----
> +/* pretend you're a porcelain for rev-cache reading from the command line */
> +struct rev_info revs;
> +struct rev_cache_info rci;
> +
> +init_revisions(&revs, 0);
> +init_rci(&rci);
> +
> +flags = 0;
> +for (i = 1; i < argc; i++) {
> +        if (!strcmp(argv[i], "--not"))
> +                flags ^= UNINTERESTING;
> +        else if(!strcmp(argv[i], "--fresh"))
> +                starts_from_slices(&revs, UNINTERESTING, 0, 0);
> +        else
> +                handle_revision_arg(argv[i], &revs, flags, 1);
> +}
> +
> +/* we want to explicitly set certain options */
> +rci.objects = 0;
> +
> +if (!make_cache_slice(&rci, &revs, 0, 0, cache_sha1))
> +        printf("made slice!  it's called %s\n", sha1_to_hex(cache_sha1));
>   

> +----
> +
> +.Traversing a slice
> +----
> +/* let's say you're walking the tree with a 'work' list of current heads and a 
> + * FILO output list 'out' */
> +out = 0;
> +outp = &out;
> +
> +while (work) {
> +        struct commit *commit = pop_commit(&work);
> +        struct object *object = &commit->object;
> +        unsigned char *cache_sha1;
> +        
> +        if (cache_sha1 = get_cache_slice(object->sha1)) {
> +                /* note that this will instatiate any topo-relations 
> +                 * as it goes */
> +                if (traverse_cache_slice(&revs, cache_sha1, 
> +                        commit, 0, 0, /* use defaults */
> +                        &outp, &work) < 0)
> +                        die("I'm overreacting to a non-fatal cache error");
> +        } else {
> +                struct commit_list *parents = commit->parents;
> +                
> +                while (parents) {
> +                        struct commit *p = parents->item;
> +                        struct object *po = &p->object;
> +                        
> +                        parents = parents->next;
> +                        if (po->flags & UNINTERESTING)
> +                                continue;
> +                        
> +                        if (object->flags & UNINTERESTING)
> +                                po->flags |= UNINTERESTING;
> +                        else if (po->flags & SEEN)
> +                                continue;
> +                        
> +                        if (!po->parsed)
> +                                parse_commit(p);
> +                        insert_by_date(p, &work);
> +                }
> +                
> +                if (object->flags & (SEEN | UNINTERESTING) == 0)
> +                        outp = &commit_list_insert(commit, outp);
> +                object->flags |= SEEN;
> +        }
> +}
> +----
>   

> +
> +Some Internals
> +--------------
> +
> +Although you really don't need to know anything about how rev-cache actually 
> +does its magic shizz, a bit of background may go a long way if you're wading 
> +through the source.
>   

> +
> +File Formats
> +~~~~~~~~~~~~
> +
> +A slice has a basic fixed-size header, followed by a certain number of object 
> +entries.  Commits are sorted in topo-order, and each commit entry is followed 
> +by the objects added in that commit.
>   

> +
> +----
> +         -- +--------------------------------+
> +header      | object number, etc...          |
> +         -- +--------------------------------+
> +commit      | commit info                    |
> +entry       | path data                      |
> +            +--------------------------------+
> +            | tree/blob info                 |
> +            +--------------------------------+
> +            | tree/blob info                 |
> +            +--------------------------------+
> +            | ...                            |
> +         -- +--------------------------------+
> +commit      | commit info                    |
> +entry       | path data                      |
> +            +--------------------------------+
> +            | tree/blob info                 |
> +            +--------------------------------+
> +            | ...                            |
> +         -- +--------------------------------+
> +...         ...                               
> +            +--------------------------------+
> +----
> +
> +The index is somewhat similar to pack-file indexes, containing a fanout table 
> +and a list of index entries sorted by hash.
> +
> +----
> +         -- +--------------------------------+
> +header      | object #, cache #, etc.        |
> +         -- +--------------------------------+
> +cache       | SHA-1                          |
> +sha1s       | ...                            |
> +         -- +--------------------------------+
> +fanout      | fanout[0x00]                   |
> +table       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> +            | fanout[0xff]                   |
> +         -- +--------------------------------+
> +index       | entry SHA-1                    |
> +entries     | cache sha1 index               |
> +            +--------------------------------+
> +            |                                |
> +            ...                               
> +            +--------------------------------+
> +----
> +
> +All the relavant structures are readily accessible in `rev-cache.c`
> +
>   

> +Mechanics
> +~~~~~~~~~
> +
> +The most important part of rev-cache is its method of encoding topological 
> +relations.  To ensure fluid traversal and reconstruction,

>  commits are related 
> +through high-level "streams"/"channels" rather than individual 
> +interconnections.  Intuitively, rev-cache stores history the way gitk shows it: 
> +commits strung up on lines, which interconnect at merges and branches.
> +
> +Each commit is associated to a given channel/path via a 'path id', and 
> +variable-length fields govern which paths (if any) are closed or opened at that 
> +object.  This means that topo-data can be preserved in only a few bytes extra 
> +per object entry.  Other information stored per entry is the sha-1 hash, type, 
> +date, size, and status in cache slice.  Here is format of an object entry, both 
> +on-disk and in-memory:
> +
> +----
> +struct object_entry {
> +        unsigned type : 3;
> +        unsigned is_end : 1;
> +        unsigned is_start : 1;
> +        unsigned uninteresting : 1;
> +        unsigned include : 1;
> +        unsigned flags : 1;
> +        unsigned char sha1[20];
> +        
> +        unsigned merge_nr : 6;
> +        unsigned split_nr : 7;
> +        unsigned size_size : 3;
> +        
> +	uint32_t date;
> +	uint16_t path;
> +        
> +        /* merge paths */
> +        /* split paths */
> +        /* size */
> +};
> +----
> +
> +An explanation of each field:
> +
> +`type`:: Object type
> +`is_end`:: The commit has some parents outside the cache slice (all if slice 
> +has legs)
> +`is_start`:: The commit has no children in cache slice
> +`uninteresting`:: Run-time flag, used in traversal
> +`include`:: Run-time flag, used in traversal (initialization)
> +`flags`:: Currently unused, extra bit
> +`sha`:: Object SHA-1 hash
> +
> +`merge_nr`:: The number of paths the current channel diverges into; the current 
> +path ends upon any merge.
> +`split_nr`:: The number of paths this commit ends; used on both merging and 
> +branching.
> +`size_size`:: Number of bytes the object size takes up.
> +
> +merge paths:: The path IDs (16-bit) that are to be created.
> +split paths:: The path IDs (16-bit) that are to be ended.
> +size:: The size split into the minimum number of bytes.
> +
> +Each path ID refers to an index in a 'path array', which stores the current 
> +status (eg. active, interestingness) of each channel.
> +
> +Due to topo-relations and boundary tracking, all of a commit's parents must be 
> +encountered before the path is reallocated.  This is achieved by using a 
> +counter system per merge: starting at the parent number, the counter is 
> +decremented as each parent is encountered (dictated by 'split paths'); at 0 the 
> +path is cleared.
> +
> +Boundary tracking is necessary because non-commits are stored relative to the 
> +commit in which they were introduced.  If a series of commits is not included 
> +in the output, the last interesting commit must be parsed manually to ensure 
> +all objects are accounted for.
> +
> +To prevent list-objects from recursing into trees that we've already taken care 
> +of, the flag `FACE_VALUE` is introduced.  An object with this flag is not 
> +explored (= "taken at face value"), significantly reducing I/O and processing 
> +time.
> +
> +(NSE)
>