diff options
Diffstat (limited to 'Documentation/technical')
| -rw-r--r-- | Documentation/technical/api-argv-array.txt | 8 | ||||
| -rw-r--r-- | Documentation/technical/api-builtin.txt | 13 | ||||
| -rw-r--r-- | Documentation/technical/api-config.txt | 31 | ||||
| -rw-r--r-- | Documentation/technical/api-gitattributes.txt | 2 | ||||
| -rw-r--r-- | Documentation/technical/api-hash.txt | 52 | ||||
| -rw-r--r-- | Documentation/technical/api-hashmap.txt | 280 | ||||
| -rw-r--r-- | Documentation/technical/api-parse-options.txt | 4 | ||||
| -rw-r--r-- | Documentation/technical/api-run-command.txt | 7 | ||||
| -rw-r--r-- | Documentation/technical/api-strbuf.txt | 28 | ||||
| -rw-r--r-- | Documentation/technical/api-string-list.txt | 7 | ||||
| -rw-r--r-- | Documentation/technical/api-trace.txt | 97 | ||||
| -rw-r--r-- | Documentation/technical/bitmap-format.txt | 164 | ||||
| -rw-r--r-- | Documentation/technical/http-protocol.txt | 8 | ||||
| -rw-r--r-- | Documentation/technical/index-format.txt | 35 | ||||
| -rw-r--r-- | Documentation/technical/pack-protocol.txt | 11 | ||||
| -rw-r--r-- | Documentation/technical/protocol-capabilities.txt | 18 | ||||
| -rw-r--r-- | Documentation/technical/protocol-common.txt | 2 |
17 files changed, 681 insertions, 86 deletions
diff --git a/Documentation/technical/api-argv-array.txt b/Documentation/technical/api-argv-array.txt index a6b7d83a8e..1a797812fb 100644 --- a/Documentation/technical/api-argv-array.txt +++ b/Documentation/technical/api-argv-array.txt @@ -53,11 +53,3 @@ Functions `argv_array_clear`:: Free all memory associated with the array and return it to the initial, empty state. - -`argv_array_detach`:: - Detach the argv array from the `struct argv_array`, transferring - ownership of the allocated array and strings. - -`argv_array_free_detached`:: - Free the memory allocated by a `struct argv_array` that was later - detached and is now no longer needed. diff --git a/Documentation/technical/api-builtin.txt b/Documentation/technical/api-builtin.txt index e3d6e7a79a..22a39b9299 100644 --- a/Documentation/technical/api-builtin.txt +++ b/Documentation/technical/api-builtin.txt @@ -22,11 +22,14 @@ Git: where options is the bitwise-or of: `RUN_SETUP`:: - - Make sure there is a Git directory to work on, and if there is a - work tree, chdir to the top of it if the command was invoked - in a subdirectory. If there is no work tree, no chdir() is - done. + If there is not a Git directory to work on, abort. If there + is a work tree, chdir to the top of it if the command was + invoked in a subdirectory. If there is no work tree, no + chdir() is done. + +`RUN_SETUP_GENTLY`:: + If there is a Git directory, chdir as per RUN_SETUP, otherwise, + don't chdir anywhere. `USE_PAGER`:: diff --git a/Documentation/technical/api-config.txt b/Documentation/technical/api-config.txt index 230b3a0f60..edd5018e15 100644 --- a/Documentation/technical/api-config.txt +++ b/Documentation/technical/api-config.txt @@ -137,4 +137,33 @@ int read_file_with_include(const char *file, config_fn_t fn, void *data) Writing Config Files -------------------- -TODO +Git gives multiple entry points in the Config API to write config values to +files namely `git_config_set_in_file` and `git_config_set`, which write to +a specific config file or to `.git/config` respectively. They both take a +key/value pair as parameter. +In the end they both call `git_config_set_multivar_in_file` which takes four +parameters: + +- the name of the file, as a string, to which key/value pairs will be written. + +- the name of key, as a string. This is in canonical "flat" form: the section, + subsection, and variable segments will be separated by dots, and the section + and variable segments will be all lowercase. + E.g., `core.ignorecase`, `diff.SomeType.textconv`. + +- the value of the variable, as a string. If value is equal to NULL, it will + remove the matching key from the config file. + +- the value regex, as a string. It will disregard key/value pairs where value + does not match. + +- a multi_replace value, as an int. If value is equal to zero, nothing or only + one matching key/value is replaced, else all matching key/values (regardless + how many) are removed, before the new pair is written. + +It returns 0 on success. + +Also, there are functions `git_config_rename_section` and +`git_config_rename_section_in_file` with parameters `old_name` and `new_name` +for renaming or removing sections in the config files. If NULL is passed +through `new_name` parameter, the section will be removed from the config file. diff --git a/Documentation/technical/api-gitattributes.txt b/Documentation/technical/api-gitattributes.txt index ce363b6305..2602668677 100644 --- a/Documentation/technical/api-gitattributes.txt +++ b/Documentation/technical/api-gitattributes.txt @@ -99,7 +99,7 @@ static void setup_check(void) The attribute is Unset, by listing the name of the attribute prefixed with a dash - for the path. } else if (ATTR_UNSET(value)) { - The attribute is not set nor unset for the path. + The attribute is neither set nor unset for the path. } else if (!strcmp(value, "input")) { If none of ATTR_TRUE(), ATTR_FALSE(), or ATTR_UNSET() is true, the value is a string set in the gitattributes diff --git a/Documentation/technical/api-hash.txt b/Documentation/technical/api-hash.txt deleted file mode 100644 index e5061e0677..0000000000 --- a/Documentation/technical/api-hash.txt +++ /dev/null @@ -1,52 +0,0 @@ -hash API -======== - -The hash API is a collection of simple hash table functions. Users are expected -to implement their own hashing. - -Data Structures ---------------- - -`struct hash_table`:: - - The hash table structure. The `array` member points to the hash table - entries. The `size` member counts the total number of valid and invalid - entries in the table. The `nr` member keeps track of the number of - valid entries. - -`struct hash_table_entry`:: - - An opaque structure representing an entry in the hash table. The `hash` - member is the entry's hash key and the `ptr` member is the entry's - value. - -Functions ---------- - -`init_hash`:: - - Initialize the hash table. - -`free_hash`:: - - Release memory associated with the hash table. - -`insert_hash`:: - - Insert a pointer into the hash table. If an entry with that hash - already exists, a pointer to the existing entry's value is returned. - Otherwise NULL is returned. This allows callers to implement - chaining, etc. - -`lookup_hash`:: - - Lookup an entry in the hash table. If an entry with that hash exists - the entry's value is returned. Otherwise NULL is returned. - -`for_each_hash`:: - - Call a function for each entry in the hash table. The function is - expected to take the entry's value as its only argument and return an - int. If the function returns a negative int the loop is aborted - immediately. Otherwise, the return value is accumulated and the sum - returned upon completion of the loop. diff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt new file mode 100644 index 0000000000..ad7a5bddd2 --- /dev/null +++ b/Documentation/technical/api-hashmap.txt @@ -0,0 +1,280 @@ +hashmap API +=========== + +The hashmap API is a generic implementation of hash-based key-value mappings. + +Data Structures +--------------- + +`struct hashmap`:: + + The hash table structure. Members can be used as follows, but should + not be modified directly: ++ +The `size` member keeps track of the total number of entries (0 means the +hashmap is empty). ++ +`tablesize` is the allocated size of the hash table. A non-0 value indicates +that the hashmap is initialized. It may also be useful for statistical purposes +(i.e. `size / tablesize` is the current load factor). ++ +`cmpfn` stores the comparison function specified in `hashmap_init()`. In +advanced scenarios, it may be useful to change this, e.g. to switch between +case-sensitive and case-insensitive lookup. + +`struct hashmap_entry`:: + + An opaque structure representing an entry in the hash table, which must + be used as first member of user data structures. Ideally it should be + followed by an int-sized member to prevent unused memory on 64-bit + systems due to alignment. ++ +The `hash` member is the entry's hash code and the `next` member points to the +next entry in case of collisions (i.e. if multiple entries map to the same +bucket). + +`struct hashmap_iter`:: + + An iterator structure, to be used with hashmap_iter_* functions. + +Types +----- + +`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`:: + + User-supplied function to test two hashmap entries for equality. Shall + return 0 if the entries are equal. ++ +This function is always called with non-NULL `entry` / `entry_or_key` +parameters that have the same hash code. When looking up an entry, the `key` +and `keydata` parameters to hashmap_get and hashmap_remove are always passed +as second and third argument, respectively. Otherwise, `keydata` is NULL. + +Functions +--------- + +`unsigned int strhash(const char *buf)`:: +`unsigned int strihash(const char *buf)`:: +`unsigned int memhash(const void *buf, size_t len)`:: +`unsigned int memihash(const void *buf, size_t len)`:: + + Ready-to-use hash functions for strings, using the FNV-1 algorithm (see + http://www.isthe.com/chongo/tech/comp/fnv). ++ +`strhash` and `strihash` take 0-terminated strings, while `memhash` and +`memihash` operate on arbitrary-length memory. ++ +`strihash` and `memihash` are case insensitive versions. + +`unsigned int sha1hash(const unsigned char *sha1)`:: + + Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code + for use in hash tables. Cryptographic hashes are supposed to have + uniform distribution, so in contrast to `memhash()`, this just copies + the first `sizeof(int)` bytes without shuffling any bits. Note that + the results will be different on big-endian and little-endian + platforms, so they should not be stored or transferred over the net. + +`void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`:: + + Initializes a hashmap structure. ++ +`map` is the hashmap to initialize. ++ +The `equals_function` can be specified to compare two entries for equality. +If NULL, entries are considered equal if their hash codes are equal. ++ +If the total number of entries is known in advance, the `initial_size` +parameter may be used to preallocate a sufficiently large table and thus +prevent expensive resizing. If 0, the table is dynamically resized. + +`void hashmap_free(struct hashmap *map, int free_entries)`:: + + Frees a hashmap structure and allocated memory. ++ +`map` is the hashmap to free. ++ +If `free_entries` is true, each hashmap_entry in the map is freed as well +(using stdlib's free()). + +`void hashmap_entry_init(void *entry, unsigned int hash)`:: + + Initializes a hashmap_entry structure. ++ +`entry` points to the entry to initialize. ++ +`hash` is the hash code of the entry. + +`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`:: + + Returns the hashmap entry for the specified key, or NULL if not found. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are passed +to `hashmap_cmp_fn` to decide whether the entry matches the key. + +`void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)`:: + + Returns the hashmap entry for the specified hash code and key data, + or NULL if not found. ++ +`map` is the hashmap structure. ++ +`hash` is the hash code of the entry to look up. ++ +If an entry with matching hash code is found, `keydata` is passed to +`hashmap_cmp_fn` to decide whether the entry matches the key. The +`entry_or_key` parameter points to a bogus hashmap_entry structure that +should not be used in the comparison. + +`void *hashmap_get_next(const struct hashmap *map, const void *entry)`:: + + Returns the next equal hashmap entry, or NULL if not found. This can be + used to iterate over duplicate entries (see `hashmap_add`). ++ +`map` is the hashmap structure. ++ +`entry` is the hashmap_entry to start the search from, obtained via a previous +call to `hashmap_get` or `hashmap_get_next`. + +`void hashmap_add(struct hashmap *map, void *entry)`:: + + Adds a hashmap entry. This allows to add duplicate entries (i.e. + separate values with the same key according to hashmap_cmp_fn). ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add. + +`void *hashmap_put(struct hashmap *map, void *entry)`:: + + Adds or replaces a hashmap entry. If the hashmap contains duplicate + entries equal to the specified entry, only one of them will be replaced. ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add or replace. ++ +Returns the replaced entry, or NULL if not found (i.e. the entry was added). + +`void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`:: + + Removes a hashmap entry matching the specified key. If the hashmap + contains duplicate entries equal to the specified key, only one of + them will be removed. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are +passed to `hashmap_cmp_fn` to decide whether the entry matches the key. ++ +Returns the removed entry, or NULL if not found. + +`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`:: +`void *hashmap_iter_next(struct hashmap_iter *iter)`:: +`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`:: + + Used to iterate over all entries of a hashmap. ++ +`hashmap_iter_init` initializes a `hashmap_iter` structure. ++ +`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no +more entries. ++ +`hashmap_iter_first` is a combination of both (i.e. initializes the iterator +and returns the first entry, if any). + +`const char *strintern(const char *string)`:: +`const void *memintern(const void *data, size_t len)`:: + + Returns the unique, interned version of the specified string or data, + similar to the `String.intern` API in Java and .NET, respectively. + Interned strings remain valid for the entire lifetime of the process. ++ +Can be used as `[x]strdup()` or `xmemdupz` replacement, except that interned +strings / data must not be modified or freed. ++ +Interned strings are best used for short strings with high probability of +duplicates. ++ +Uses a hashmap to store the pool of interned strings. + +Usage example +------------- + +Here's a simple usage example that maps long keys to double values. +------------ +struct hashmap map; + +struct long2double { + struct hashmap_entry ent; /* must be the first member! */ + long key; + double value; +}; + +static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) +{ + return !(e1->key == e2->key); +} + +void long2double_init(void) +{ + hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); +} + +void long2double_free(void) +{ + hashmap_free(&map, 1); +} + +static struct long2double *find_entry(long key) +{ + struct long2double k; + hashmap_entry_init(&k, memhash(&key, sizeof(long))); + k.key = key; + return hashmap_get(&map, &k, NULL); +} + +double get_value(long key) +{ + struct long2double *e = find_entry(key); + return e ? e->value : 0; +} + +void set_value(long key, double value) +{ + struct long2double *e = find_entry(key); + if (!e) { + e = malloc(sizeof(struct long2double)); + hashmap_entry_init(e, memhash(&key, sizeof(long))); + e->key = key; + hashmap_add(&map, e); + } + e->value = value; +} +------------ + +Using variable-sized keys +------------------------- + +The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary +`hashmap_entry` structure as key to find the correct entry. If the key data is +variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable +to create a full-fledged entry structure on the heap and copy all the key data +into the structure. + +In this case, the `keydata` parameter can be used to pass +variable-sized key data directly to the comparison function, and the `key` +parameter can be a stripped-down, fixed size entry structure allocated on the +stack. + +See test-hashmap.c for an example using arbitrary-length strings as keys. diff --git a/Documentation/technical/api-parse-options.txt b/Documentation/technical/api-parse-options.txt index be50cf4de3..1f2db31312 100644 --- a/Documentation/technical/api-parse-options.txt +++ b/Documentation/technical/api-parse-options.txt @@ -160,10 +160,6 @@ There are some macros to easily define options: `int_var` is set to `integer` with `--option`, and reset to zero with `--no-option`. -`OPT_SET_PTR(short, long, &ptr_var, description, ptr)`:: - Introduce a boolean option. - If used, set `ptr_var` to `ptr`. - `OPT_STRING(short, long, &str_var, arg_str, description)`:: Introduce an option with string argument. The string argument is put into `str_var`. diff --git a/Documentation/technical/api-run-command.txt b/Documentation/technical/api-run-command.txt index 5d7d7f2d32..69510ae57a 100644 --- a/Documentation/technical/api-run-command.txt +++ b/Documentation/technical/api-run-command.txt @@ -109,6 +109,13 @@ terminated), of which .argv[0] is the program name to run (usually without a path). If the command to run is a git command, set argv[0] to the command name without the 'git-' prefix and set .git_cmd = 1. +Note that the ownership of the memory pointed to by .argv stays with the +caller, but it should survive until `finish_command` completes. If the +.argv member is NULL, `start_command` will point it at the .args +`argv_array` (so you may use one or the other, but you must use exactly +one). The memory in .args will be cleaned up automatically during +`finish_command` (or during `start_command` when it is unsuccessful). + The members .in, .out, .err are used to redirect stdin, stdout, stderr as follows: diff --git a/Documentation/technical/api-strbuf.txt b/Documentation/technical/api-strbuf.txt index 3350d97dda..f9c06a7573 100644 --- a/Documentation/technical/api-strbuf.txt +++ b/Documentation/technical/api-strbuf.txt @@ -7,10 +7,10 @@ use the mem* functions than a str* one (memchr vs. strchr e.g.). Though, one has to be careful about the fact that str* functions often stop on NULs and that strbufs may have embedded NULs. -An strbuf is NUL terminated for convenience, but no function in the +A strbuf is NUL terminated for convenience, but no function in the strbuf API actually relies on the string being free of NULs. -strbufs has some invariants that are very important to keep in mind: +strbufs have some invariants that are very important to keep in mind: . The `buf` member is never NULL, so it can be used in any usual C string operations safely. strbuf's _have_ to be initialized either by @@ -56,8 +56,8 @@ Data structures * `struct strbuf` This is the string buffer structure. The `len` member can be used to -determine the current length of the string, and `buf` member provides access to -the string itself. +determine the current length of the string, and `buf` member provides +access to the string itself. Functions --------- @@ -121,10 +121,28 @@ Functions * Related to the contents of the buffer +`strbuf_trim`:: + + Strip whitespace from the beginning and end of a string. + Equivalent to performing `strbuf_rtrim()` followed by `strbuf_ltrim()`. + `strbuf_rtrim`:: Strip whitespace from the end of a string. +`strbuf_ltrim`:: + + Strip whitespace from the beginning of a string. + +`strbuf_reencode`:: + + Replace the contents of the strbuf with a reencoded form. Returns -1 + on error, 0 on success. + +`strbuf_tolower`:: + + Lowercase each character in the buffer using `tolower`. + `strbuf_cmp`:: Compare two buffers. Returns an integer less than, equal to, or greater @@ -184,7 +202,7 @@ strbuf_addstr(sb, "immediate string"); `strbuf_addbuf`:: - Copy the contents of an other buffer at the end of the current one. + Copy the contents of another buffer at the end of the current one. `strbuf_adddup`:: diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt index 20be348834..d51a6579c8 100644 --- a/Documentation/technical/api-string-list.txt +++ b/Documentation/technical/api-string-list.txt @@ -68,6 +68,11 @@ Functions * General ones (works with sorted and unsorted lists as well) +`string_list_init`:: + + Initialize the members of the string_list, set `strdup_strings` + member according to the value of the second parameter. + `filter_string_list`:: Apply a function to each item in a list, retaining only the @@ -200,3 +205,5 @@ Represents the list itself. You should not tamper with it. . Setting the `strdup_strings` member to 1 will strdup() the strings before adding them, see above. +. The `compare_strings_fn` member is used to specify a custom compare + function, otherwise `strcmp()` is used as the default function. diff --git a/Documentation/technical/api-trace.txt b/Documentation/technical/api-trace.txt new file mode 100644 index 0000000000..097a651d96 --- /dev/null +++ b/Documentation/technical/api-trace.txt @@ -0,0 +1,97 @@ +trace API +========= + +The trace API can be used to print debug messages to stderr or a file. Trace +code is inactive unless explicitly enabled by setting `GIT_TRACE*` environment +variables. + +The trace implementation automatically adds `timestamp file:line ... \n` to +all trace messages. E.g.: + +------------ +23:59:59.123456 git.c:312 trace: built-in: git 'foo' +00:00:00.000001 builtin/foo.c:99 foo: some message +------------ + +Data Structures +--------------- + +`struct trace_key`:: + + Defines a trace key (or category). The default (for API functions that + don't take a key) is `GIT_TRACE`. ++ +E.g. to define a trace key controlled by environment variable `GIT_TRACE_FOO`: ++ +------------ +static struct trace_key trace_foo = TRACE_KEY_INIT(FOO); + +static void trace_print_foo(const char *message) +{ + trace_print_key(&trace_foo, message); +} +------------ ++ +Note: don't use `const` as the trace implementation stores internal state in +the `trace_key` structure. + +Functions +--------- + +`int trace_want(struct trace_key *key)`:: + + Checks whether the trace key is enabled. Used to prevent expensive + string formatting before calling one of the printing APIs. + +`void trace_disable(struct trace_key *key)`:: + + Disables tracing for the specified key, even if the environment + variable was set. + +`void trace_printf(const char *format, ...)`:: +`void trace_printf_key(struct trace_key *key, const char *format, ...)`:: + + Prints a formatted message, similar to printf. + +`void trace_argv_printf(const char **argv, const char *format, ...)``:: + + Prints a formatted message, followed by a quoted list of arguments. + +`void trace_strbuf(struct trace_key *key, const struct strbuf *data)`:: + + Prints the strbuf, without additional formatting (i.e. doesn't + choke on `%` or even `\0`). + +`uint64_t getnanotime(void)`:: + + Returns nanoseconds since the epoch (01/01/1970), typically used + for performance measurements. ++ +Currently there are high precision timer implementations for Linux (using +`clock_gettime(CLOCK_MONOTONIC)`) and Windows (`QueryPerformanceCounter`). +Other platforms use `gettimeofday` as time source. + +`void trace_performance(uint64_t nanos, const char *format, ...)`:: +`void trace_performance_since(uint64_t start, const char *format, ...)`:: + + Prints the elapsed time (in nanoseconds), or elapsed time since + `start`, followed by a formatted message. Enabled via environment + variable `GIT_TRACE_PERFORMANCE`. Used for manual profiling, e.g.: ++ +------------ +uint64_t start = getnanotime(); +/* code section to measure */ +trace_performance_since(start, "foobar"); +------------ ++ +------------ +uint64_t t = 0; +for (;;) { + /* ignore */ + t -= getnanotime(); + /* code section to measure */ + t += getnanotime(); + /* ignore */ +} +trace_performance(t, "frotz"); +------------ diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt new file mode 100644 index 0000000000..f8c18a0f7a --- /dev/null +++ b/Documentation/technical/bitmap-format.txt @@ -0,0 +1,164 @@ +GIT bitmap v1 format +==================== + + - A header appears at the beginning: + + 4-byte signature: {'B', 'I', 'T', 'M'} + + 2-byte version number (network byte order) + The current implementation only supports version 1 + of the bitmap index (the same one as JGit). + + 2-byte flags (network byte order) + + The following flags are supported: + + - BITMAP_OPT_FULL_DAG (0x1) REQUIRED + This flag must always be present. It implies that the bitmap + index has been generated for a packfile with full closure + (i.e. where every single object in the packfile can find + its parent links inside the same packfile). This is a + requirement for the bitmap index format, also present in JGit, + that greatly reduces the complexity of the implementation. + + - BITMAP_OPT_HASH_CACHE (0x4) + If present, the end of the bitmap file contains + `N` 32-bit name-hash values, one per object in the + pack. The format and meaning of the name-hash is + described below. + + 4-byte entry count (network byte order) + + The total count of entries (bitmapped commits) in this bitmap index. + + 20-byte checksum + + The SHA1 checksum of the pack this bitmap index belongs to. + + - 4 EWAH bitmaps that act as type indexes + + Type indexes are serialized after the hash cache in the shape + of four EWAH bitmaps stored consecutively (see Appendix A for + the serialization format of an EWAH bitmap). + + There is a bitmap for each Git object type, stored in the following + order: + + - Commits + - Trees + - Blobs + - Tags + + In each bitmap, the `n`th bit is set to true if the `n`th object + in the packfile is of that type. + + The obvious consequence is that the OR of all 4 bitmaps will result + in a full set (all bits set), and the AND of all 4 bitmaps will + result in an empty bitmap (no bits set). + + - N entries with compressed bitmaps, one for each indexed commit + + Where `N` is the total amount of entries in this bitmap index. + Each entry contains the following: + + - 4-byte object position (network byte order) + The position **in the index for the packfile** where the + bitmap for this commit is found. + + - 1-byte XOR-offset + The xor offset used to compress this bitmap. For an entry + in position `x`, a XOR offset of `y` means that the actual + bitmap representing this commit is composed by XORing the + bitmap for this entry with the bitmap in entry `x-y` (i.e. + the bitmap `y` entries before this one). + + Note that this compression can be recursive. In order to + XOR this entry with a previous one, the previous entry needs + to be decompressed first, and so on. + + The hard-limit for this offset is 160 (an entry can only be + xor'ed against one of the 160 entries preceding it). This + number is always positive, and hence entries are always xor'ed + with **previous** bitmaps, not bitmaps that will come afterwards + in the index. + + - 1-byte flags for this bitmap + At the moment the only available flag is `0x1`, which hints + that this bitmap can be re-used when rebuilding bitmap indexes + for the repository. + + - The compressed bitmap itself, see Appendix A. + +== Appendix A: Serialization format for an EWAH bitmap + +Ewah bitmaps are serialized in the same protocol as the JAVAEWAH +library, making them backwards compatible with the JGit +implementation: + + - 4-byte number of bits of the resulting UNCOMPRESSED bitmap + + - 4-byte number of words of the COMPRESSED bitmap, when stored + + - N x 8-byte words, as specified by the previous field + + This is the actual content of the compressed bitmap. + + - 4-byte position of the current RLW for the compressed + bitmap + +All words are stored in network byte order for their corresponding +sizes. + +The compressed bitmap is stored in a form of run-length encoding, as +follows. It consists of a concatenation of an arbitrary number of +chunks. Each chunk consists of one or more 64-bit words + + H L_1 L_2 L_3 .... L_M + +H is called RLW (run length word). It consists of (from lower to higher +order bits): + + - 1 bit: the repeated bit B + + - 32 bits: repetition count K (unsigned) + + - 31 bits: literal word count M (unsigned) + +The bitstream represented by the above chunk is then: + + - K repetitions of B + + - The bits stored in `L_1` through `L_M`. Within a word, bits at + lower order come earlier in the stream than those at higher + order. + +The next word after `L_M` (if any) must again be a RLW, for the next +chunk. For efficient appending to the bitstream, the EWAH stores a +pointer to the last RLW in the stream. + + +== Appendix B: Optional Bitmap Sections + +These sections may or may not be present in the `.bitmap` file; their +presence is indicated by the header flags section described above. + +Name-hash cache +--------------- + +If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains +a cache of 32-bit values, one per object in the pack. The value at +position `i` is the hash of the pathname at which the `i`th object +(counting in index order) in the pack can be found. This can be fed +into the delta heuristics to compare objects with similar pathnames. + +The hash algorithm used is: + + hash = 0; + while ((c = *name++)) + if (!isspace(c)) + hash = (hash >> 2) + (c << 24); + +Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag. +If implementations want to choose a different hashing scheme, they are +free to do so, but MUST allocate a new header flag (because comparing +hashes made under two different schemes would be pointless). diff --git a/Documentation/technical/http-protocol.txt b/Documentation/technical/http-protocol.txt index 544373b16f..229f845dfa 100644 --- a/Documentation/technical/http-protocol.txt +++ b/Documentation/technical/http-protocol.txt @@ -60,7 +60,7 @@ Because Git repositories are accessed by standard path components server administrators MAY use directory based permissions within their HTTP server to control repository access. -Clients SHOULD support Basic authentication as described by RFC 2616. +Clients SHOULD support Basic authentication as described by RFC 2617. Servers SHOULD support Basic authentication by relying upon the HTTP server placed in front of the Git server software. @@ -374,7 +374,7 @@ C: Send one `$GIT_URL/git-upload-pack` request: C: 0000 The stream is organized into "commands", with each command -appearing by itself in a pkt-line. Within a command line +appearing by itself in a pkt-line. Within a command line, the text leading up to the first space is the command name, and the remainder of the line to the first LF is the value. Command lines are terminated with an LF as the last byte of @@ -500,7 +500,7 @@ TODO: Document this further. References ---------- -link:http://www.ietf.org/rfc/rfc1738.txt[RFC 1738: Uniform Resource Locators (URL)] -link:http://www.ietf.org/rfc/rfc2616.txt[RFC 2616: Hypertext Transfer Protocol -- HTTP/1.1] +http://www.ietf.org/rfc/rfc1738.txt[RFC 1738: Uniform Resource Locators (URL)] +http://www.ietf.org/rfc/rfc2616.txt[RFC 2616: Hypertext Transfer Protocol -- HTTP/1.1] link:technical/pack-protocol.html link:technical/protocol-capabilities.html diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index f352a9b22e..fe6f31667d 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -129,6 +129,9 @@ Git index format (Version 4) In version 4, the padding after the pathname does not exist. + Interpretation of index entries in split index mode is completely + different. See below for details. + == Extensions === Cached tree @@ -198,3 +201,35 @@ Git index format - At most three 160-bit object names of the entry in stages from 1 to 3 (nothing is written for a missing stage). +=== Split index + + In split index mode, the majority of index entries could be stored + in a separate file. This extension records the changes to be made on + top of that to produce the final index. + + The signature for this extension is { 'l', 'i, 'n', 'k' }. + + The extension consists of: + + - 160-bit SHA-1 of the shared index file. The shared index file path + is $GIT_DIR/sharedindex.<SHA-1>. If all 160 bits are zero, the + index does not require a shared index file. + + - An ewah-encoded delete bitmap, each bit represents an entry in the + shared index. If a bit is set, its corresponding entry in the + shared index will be removed from the final index. Note, because + a delete operation changes index entry positions, but we do need + original positions in replace phase, it's best to just mark + entries for removal, then do a mass deletion after replacement. + + - An ewah-encoded replace bitmap, each bit represents an entry in + the shared index. If a bit is set, its corresponding entry in the + shared index will be replaced with an entry in this index + file. All replaced entries are stored in sorted order in this + index. The first "1" bit in the replace bitmap corresponds to the + first index entry, the second "1" bit to the second entry and so + on. Replaced entries may have empty path names to save space. + + The remaining index entries after replaced ones will be added to the + final index. These added entries are also sorted by entry namme then + stage. diff --git a/Documentation/technical/pack-protocol.txt b/Documentation/technical/pack-protocol.txt index c73b62f5e1..18dea8d15f 100644 --- a/Documentation/technical/pack-protocol.txt +++ b/Documentation/technical/pack-protocol.txt @@ -237,10 +237,10 @@ The client now sends the maximum commit history depth it wants for this transaction, which is the number of commits it wants from the tip of the history, if any, as a 'deepen' line. A depth of 0 is the same as not making a depth request. The client does not want to receive -any commits beyond this depth, nor objects needed only to complete -those commits. Commits whose parents are not received as a result are -defined as shallow and marked as such in the server. This information -is sent back to the client in the next step. +any commits beyond this depth, nor does it want objects needed only to +complete those commits. Commits whose parents are not received as a +result are defined as shallow and marked as such in the server. This +information is sent back to the client in the next step. Once all the 'want's and 'shallow's (and optional 'deepen') are transferred, clients MUST send a flush-pkt, to tell the server side @@ -338,7 +338,8 @@ during a prior round. This helps to ensure that at least one common ancestor is found before we give up entirely. Once the 'done' line is read from the client, the server will either -send a final 'ACK obj-id' or it will send a 'NAK'. The server only sends +send a final 'ACK obj-id' or it will send a 'NAK'. 'obj-id' is the object +name of the last commit determined to be common. The server only sends ACK after 'done' if there is at least one common base and multi_ack or multi_ack_detailed is enabled. The server always sends NAK after 'done' if there is no common base found. diff --git a/Documentation/technical/protocol-capabilities.txt b/Documentation/technical/protocol-capabilities.txt index e3e792476e..e174343847 100644 --- a/Documentation/technical/protocol-capabilities.txt +++ b/Documentation/technical/protocol-capabilities.txt @@ -69,6 +69,24 @@ ends. Without multi_ack the client would have sent that c-b-a chain anyway, interleaved with S-R-Q. +multi_ack_detailed +------------------ +This is an extension of multi_ack that permits client to better +understand the server's in-memory state. See pack-protocol.txt, +section "Packfile Negotiation" for more information. + +no-done +------- +This capability should only be used with the smart HTTP protocol. If +multi_ack_detailed and no-done are both present, then the sender is +free to immediately send a pack following its first "ACK obj-id ready" +message. + +Without no-done in the smart HTTP protocol, the server session would +end and the client has to make another trip to send "done" before +the server can send the pack. no-done removes the last round and +thus slightly reduces latency. + thin-pack --------- diff --git a/Documentation/technical/protocol-common.txt b/Documentation/technical/protocol-common.txt index fb7ff084f8..889985f707 100644 --- a/Documentation/technical/protocol-common.txt +++ b/Documentation/technical/protocol-common.txt @@ -39,7 +39,7 @@ More specifically, they: caret `^`, colon `:`, question-mark `?`, asterisk `*`, or open bracket `[` anywhere. -. They cannot end with a slash `/` nor a dot `.`. +. They cannot end with a slash `/` or a dot `.`. . They cannot end with the sequence `.lock`. |