Multi-pack index (MIDX)

This RFC includes a new way to index the objects in multiple packs using one file, called the multi-pack index (MIDX).

The commits are split into parts as follows:

[01] - A full design document.

[02] - The full file format for MIDX files.

[03] - Creation of core.midx config setting.

[04-12] - Creation of "midx" builtin that writes, reads, and deletes
MIDX files.

[13-18] - Consume MIDX files for abbreviations and object loads.

The main goals of this RFC are:

* Determine interest in this feature.

* Find other use cases for the MIDX feature.

* Design a proper command-line interface for constructing and checking MIDX files. The current "midx" builtin is probably inadequate.

* Determine what additional changes are needed before the feature can be merged. Specifically, I'm interested in the interactions with repack and fsck. The current patch also does not update the MIDX on a fetch (which adds a packfile) but would be valuable. Whenever possible, I tried to leave out features that could be added in a later patch.

* Consider splitting this patch into multiple patches, such as:

i. The MIDX design document.
ii. The command-line interface for building and reading MIDX files.
iii. Integrations with abbreviations and object lookups.

Please do not send any style nits to this patch, as I expect the code to change dramatically before we consider merging.

I created three copies of the Linux repo with 1, 24, and 127 packfiles each using 'git repack -adfF --max-pack-size=[64m|16m]'. These copies gave significant performance improvements on the following comand:

    git log --oneline --raw --parents

Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %
----------+-------------+------------+--------+----------

        1 |     35.64 s |    35.28 s |  -1.0% |   -1.0%
       24 |     90.81 s |    40.06 s | -55.9% |  +12.4%
      127 |    257.97 s |    42.25 s | -83.6% |  +18.6%

The last column is the relative difference between the MIDX-enabled repo and the single-pack repo. The goal of the MIDX feature is to present the ODB as if it was fully repacked, so there is still room for improvement.

Changing the command to

    git log --oneline --raw --parents --abbrev=40

has no observable difference (sub 1% change in all cases). This is likely due to the repack I used putting commits and trees in a small number of packfiles so the MRU cache workes very well. On more naturally-created lists of packfiles, there can be up to 20% improvement on this command.

We are using a version of this patch with an upcoming release of GVFS. This feature is particularly important in that space since GVFS performs a "prefetch" step that downloads a pack of commits and trees on a daily basis. These packfiles are placed in an alternate that is shared by all enlistments. Some users have 150+ packfiles and the MRU misses and abbreviation computations are significant. Now, GVFS manages the MIDX file after adding new prefetch packfiles using the following command:

    git midx --write --update-head --delete-expired --pack-dir=<alt>

As that release deploys we will gather more specific numbers on the performance improvements and report them in this thread.

Derrick Stolee (18):
docs: Multi-Pack Index (MIDX) Design Notes
midx: specify midx file format
midx: create core.midx config setting
midx: write multi-pack indexes for an object list
midx: create midx builtin with --write mode
midx: add t5318-midx.sh test script
midx: teach midx --write to update midx-head
midx: teach git-midx to read midx file details
midx: find details of nth object in midx
midx: use existing midx when writing
midx: teach git-midx to clear midx files
midx: teach git-midx to delete expired files t5318-midx.h: confirm git actions are stable
midx: load midx files when loading packs
midx: use midx for approximate object count
midx: nth_midxed_object_oid() and bsearch_midx()
sha1_name: use midx for abbreviations
packfile: use midx for object loads

 .gitignore                                   |   1 +
 Documentation/config.txt                     |   3 +
 Documentation/git-midx.txt                   | 106 ++++
 Documentation/technical/multi-pack-index.txt | 149 +++++
 Documentation/technical/pack-format.txt      |  85 +++
 Makefile                                     |   2 +
 builtin.h                                    |   1 +
 builtin/midx.c                               | 352 +++++++++++
 cache.h                                      |   1 +
 command-list.txt                             |   1 +
 config.c                                     |   5 +
 environment.c                                |   2 +
 git.c                                        |   1 +
 midx.c                                       | 850 +++++++++++++++++++++++++++
 midx.h                                       | 136 +++++
 packfile.c                                   |  79 ++-
 packfile.h                                   |   2 +
 sha1_name.c                                  |  70 ++-
 t/t5318-midx.sh                              | 189 ++++++
 19 files changed, 2020 insertions(+), 15 deletions(-)
 create mode 100644 Documentation/git-midx.txt
 create mode 100644 Documentation/technical/multi-pack-index.txt
 create mode 100644 builtin/midx.c
 create mode 100644 midx.c
 create mode 100644 midx.h
 create mode 100755 t/t5318-midx.sh

2.15.0

Commentary: This file format uses the large offsets from the pack-index version 2 format, but drops the CRC32 hashes from that format.

Also: I included the HASH footer at the end only because it is already in the pack and pack-index formats, but not because it is particularly useful here. If possible, I'd like to remove it and speed up MIDX writes.

-- >8 --

Add a technical documentation file describing the design for the multi-pack index (MIDX). Includes current limitations and future work.

---
 Documentation/technical/multi-pack-index.txt | 149 +++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)
 create mode 100644 Documentation/technical/multi-pack-index.txt

new file mode 100644
index 0000000000..d31b03dec5
@@ -0,0 +1,149 @@
+Multi-Pack-Index (MIDX) Design Notes
+====================================
+
+The Git object directory contains a 'pack' directory containing
+packfiles (with suffix ".pack") and pack-indexes (with suffix
+".idx"). The pack-indexes provide a way to lookup objects and
+navigate to their offset within the pack, but these must come
+in pairs with the packfiles. This pairing depends on the file
+names, as the pack-index differs only in suffix with its pack-
+file. While the pack-indexes provide fast lookup per packfile,
+this performance degrades as the number of packfiles increases,
+because abbreviations need to inspect every packfile and we are
+more likely to have a miss on our most-recently-used packfile.
+For some large repositories, repacking into a single packfile
+is not feasible due to storage space or excessive repack times.
+
+The multi-pack-index (MIDX for short, with suffix ".midx")
+stores a list of objects and their offsets into multiple pack-
+files. It contains:
+
+- A list of packfile names.
+- A sorted list of object IDs.
+- A list of metadata for the ith object ID including:
+  - A value j referring to the jth packfile.
+  - An offset within the jth packfile for the object.
+- If large offsets are required, we use another list of large
+  offsets similar to version 2 pack-indexes.
+
+Thus, we can provide O(log N) lookup time for any number
+of packfiles.
+
+A new config setting 'core.midx' must be enabled before writing
+or reading MIDX files.
+
+The MIDX files are updated by the 'midx' builtin with the
+following common parameter combinations:
+
+- 'git midx' gives the hash of the current MIDX head.
+- 'git midx --write --update-head --delete-expired' writes a new
+  MIDX file, points the MIDX head to that file, and deletes the
+  existing MIDX file if out-of-date.
+- 'git midx --read' lists some basic information about the current
+  MIDX head. Used for basic tests.
+- 'git midx --clear' deletes the current MIDX head.
+
+Design Details
+--------------
+
+- The MIDX file refers only to packfiles in the same directory
+  as the MIDX file.
+
+- A special file, 'midx-head', stores the hash of the latest
+  MIDX file so we can load the file without performing a dirstat.
+  This file is especially important with incremental MIDX files,
+  pointing to the newest file.
+
+- If a packfile exists in the pack directory but is not referenced
+  by the MIDX file, then the packfile is loaded into the packed_git
+  list and Git can access the objects as usual. This behavior is
+  necessary since other tools could add packfiles to the pack
+  directory without notifying Git.
+
+- The MIDX file should be only a supplemental structure. If a
+  user downgrades or disables the `core.midx` config setting,
+  then the existing .idx and .pack files should be sufficient
+  to operate correctly.
+
+- The file format includes parameters for the object id length
+  and hash algorithm, so a future change of hash algorithm does
+  not require a change in format.
+
+- If an object appears in multiple packfiles, then only one copy
+  is stored in the MIDX. This has a possible performance issue:
+  If an object appears as the delta-base of multiple objects from
+  multiple packs, then cross-pack delta calculations may slow down.
+  This is currently only theoretical and has not been demonstrated
+  to be a measurable issue.
+
+Current Limitations
+-------------------
+
+- MIDX files are managed only by the midx builtin and is not
+  automatically updated on clone or fetch.
+
+- There is no '--verify' option for the midx builtin to verify
+  the contents of the MIDX file against the pack contents.
+
+- Constructing a MIDX file currently requires the single-pack
+  index for every pack being added to the MIDX.
+
+- The fsck builtin does not check MIDX files, but should.
+
+- The repack builtin is not aware of the MIDX files, and may
+  invalidate the MIDX files by deleting existing packfiles. The
+  MIDX may also be extended in the future to store metadata about
+  a packfile that can be used for faster repack commands.
+
+- The naive Git HTTP server advertises lists of packfiles using
+  the file system directly.
+
+Future Work
+-----------
+
+- The current file-format requires between 28 and 36 bytes per
+  object. As the repository grows, the MIDX file can become
+  very large and become a bottleneck when updating the file. To
+  fix this "big write" problem, we can make the MIDX file
+  incremental. Instead of just one MIDX file, we will have a
+  sequence of MIDX files that can be unioned together. Then
+  on write we take the new objects to add and consider how many
+  existing files should be merged into a new file containing
+  the latest objects.
+
+  This list of "base indexes" will be presented as an optional
+  chunk in the MIDX format and contains the OIDs for the base
+  files. Thus, the `midx_head` file only stores the OID for the
+  "tip" MIDX file and then the rest are loaded based on those
+  pointers, such as the following figure:
+
+  [     BIG     ] <- [ MEDIUM ] <- [tiny] <- midx_head
+	 ^___________________________|
+
+  The plan being that every write replaces the "tiny" index,
+  and when that index becomes large enough it merges with the
+  "medium" index and a new tiny index is created in the next
+  write. Very rarely, the "big" index would be updated, causing
+  a slow write.
+
+- After the MIDX feature is sufficiently hardened and widely used,
+  consider making Git more fully depend on the MIDX file. If MIDX
+  is the default, then we can delete the single-pack-indexes from
+  the pack directory. We could also allow thin packs in the pack
+  directory.
+
+- The MIDX could be extended to store a "stable object order" such
+  that adding objects to the order does not change the existing
+  objects. This would enable re-using the reachability bitmaps after
+  repacking and updating the MIDX file.
+
+Related Links
+-------------
+
+[0] https://bugs.chromium.org/p/git/issues/detail?id=6
+    Chromium work item for: Multi-Pack Index (MIDX)
+
+[1] https://public-inbox.org/git/CB5074CF.3AD7A%[email protected]/T/#u
+    Subject: Git performance results on a large repository
+    Date: 3 Feb 2012
+

2.15.0

I hadn't considered this idea, and I like it. I'm not sure this is a robust solution, since isolated MIDX files don't contain information that they could use other MIDX files, or what order they should be in. I think the "order" of incremental MIDX files is important in a few ways (such as the "stable object order" idea).

I will revisit this idea when I come back with the incremental MIDX feature. For now, the only reference to "number of base MIDX files" is in one byte of the MIDX header. We should consider changing that byte for this patch.

Thanks! That is certainly the idea. If you know about MIDX, then you can benefit from it. If you do not, then you have all the same data available to you do to your work. Having a MIDX file will not break other tools (libgit2, JGit, etc.).

One thing I'd like to determine before this patch goes to v1 is how much we should make the other packfile-aware commands also midx-aware. My gut reaction right now is to have git-repack call 'git midx --clear' if core.midx=true and a packfile was deleted. However, this could easily be changed with 'git midx --clear' followed by 'git midx --write --update-head' if midx-head exists.

Thanks,
-Stolee

My opinion is that these are sufficient:
(a) functionality to create a .midx file from scratch (deleting any existing ones)
(b) either:
- update of packfile.c to read (one or more) midx files (like in patch 18), and possibly usage in a benchmark, or
- any other usage of midx file (e.g. abbreviations, like in patch
17)

In general, a way to create them (so that they can be used from a cronjob, etc.), and a way to consume them to show that the new way works and is indeed faster. This functionality in itself might be sufficient to merge in - this would already be useful in situations where it is undesirable for repacks to happen often, and we can "bridge" the intervals between repacks using a cronjob that periodically generates .midx files in order to keep up the object lookup performance.

In particular, I think that it is fine to omit a more sophisticated "repack" for now - the .midx mechanism must tolerate packs referenced by .midx files suddenly disappearing anyway, and in this way, at least we can demonstrate that the .midx mechanism still works in this case.

A multi-pack-index (MIDX) file indexes the objects in multiple packfiles in a single pack directory. After a simple fixed-size header, the version 1 file format uses chunks to specify different regions of the data that correspond to different types of data, including:

- List of OIDs in lex-order
- A fanout table into the OID list
- List of packfile names (relative to pack directory)
- List of object metadata
- Large offsets (if needed)

By adding extra optional chunks, we can easily extend this format without invalidating written v1 files.

One value in the header corresponds to a number of "base MIDX files" and will always be zero until the value is used in a later patch.

We considered using a hashtable format instead of an ordered list of objects to reduce the O(log N) lookups to O(1) lookups, but two main issues arose that lead us to abandon the idea:

- Extra space required to ensure collision counts were low.
- We need to identify the two lexicographically closest OIDs for fast abbreviations. Binary search allows this.

The current solution presents multiple packfiles as if they were packed into a single packfile with one pack-index.

---
 Documentation/technical/pack-format.txt | 85 +++++++++++++++++++++++++++++++++
 1 file changed, 85 insertions(+)

index 8e5bf60be3..ab459ef142 100644
@@ -160,3 +160,88 @@ Pack file entry: <+
     corresponding packfile.
 
     20-byte SHA-1-checksum of all of the above.
+
+== midx-*.midx files have the following format:
+
+The multi-pack-index (MIDX) files refer to multiple pack-files.
+
+In order to allow extensions that add extra data to the MIDX format, we
+organize the body into "chunks" and provide a lookup table at the beginning
+of the body. The header includes certain length values, such as the number
+of packs, the number of base MIDX files, hash lengths and types.
+
+All 4-byte numbers are in network order.
+
+HEADER:
+
+	4-byte signature:
+	    The signature is: {'M', 'I', 'D', 'X'}
+
+	4-byte version number:
+	    Git currently only supports version 1.
+
+	1-byte Object Id Version (1 = SHA-1)
+
+	1-byte Object Id Length (H)
+
+	1-byte number (I) of base multi-pack-index files:
+	    This value is currently always zero.
+
+	1-byte number (C) of "chunks"
+
+	4-byte number (P) of pack files
+
+CHUNK LOOKUP:
+
+	(C + 1) * 12 bytes providing the chunk offsets:
+	    First 4 bytes describe chunk id. Value 0 is a terminating label.
+	    Other 8 bytes provide offset in current file for chunk to start.
+	    (Chunks are provided in file-order, so you can infer the length
+	    using the next chunk position if necessary.)
+
+	The remaining data in the body is described one chunk at a time, and
+	these chunks may be given in any order. Chunks are required unless
+	otherwise specified.
+
+CHUNK DATA:
+
+	OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)
+	    The ith entry, F[i], stores the number of OIDs with first
+	    byte at most i. Thus F[255] stores the total
+	    number of objects (N). The number of objects with first byte
+	    value i is (F[i] - F[i-1]) for i > 0.
+
+	OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
+	    The OIDs for all objects in the MIDX are stored in lexicographic
+	    order in this chunk.
+
+	Object Offsets (ID: {'O', 'O', 'F', 'F'}) (N * 8 bytes)
+	    Stores two 4-byte values for every object.
+	    1: The pack-int-id for the pack storing this object.
+	    2: The offset within the pack.
+		If all offsets are less than 2^31, then the large offset chunk
+		will not exist and offsets are stored as in IDX v1.
+		If there is at least one offset value larger than 2^32-1, then
+		the large offset chunk must exist. If the large offset chunk
+		exists and the 31st bit is on, then removing that bit reveals
+		the row in the large offsets containing the 8-byte offset of
+		this object.
+
+	[Optional] Object Large Offsets (ID: {'L', 'O', 'F', 'F'})
+	    8-byte offsets into large packfiles.
+
+	Packfile Name Lookup (ID: {'P', 'L', 'O', 'O'}) (P * 4 bytes)
+	    P * 4 bytes storing the offset in the packfile name chunk for
+	    the null-terminated string containing the filename for the
+	    ith packfile. The filename is relative to the MIDX file's parent
+	    directory.
+
+	Packfile Names (ID: {'P', 'N', 'A', 'M'})
+	    Stores the packfile names as concatenated, null-terminated strings.
+	    Packfiles must be listed in lexicographic order for fast lookups by
+	    name. This is the only chunk not guaranteed to be a multiple of four
+	    bytes in length, so it should be the last chunk for alignment reasons.
+
+TRAILER:
+
+	H-byte HASH-checksum of all of the above.

2.15.0

As the multi-pack-index feature is being developed, we use a config setting 'core.midx' to enable all use of MIDX files.

Since MIDX files are designed as a way to augment the existing data stores in Git, turning this setting off will revert to previous behavior without needing to downgrade. This can also be a repo- specific setting if the MIDX is misbehaving in only one repo.

---
 Documentation/config.txt | 3 +++
 cache.h                  | 1 +
 config.c                 | 5 +++++
 environment.c            | 2 ++
 4 files changed, 11 insertions(+)

index 64c1dbba94..dc7cb4b900 100644
@@ -896,6 +896,9 @@ core.notesRef::
 This setting defaults to "refs/notes/commits", and it can be overridden by
 the `GIT_NOTES_REF` environment variable.  See linkgit:git-notes[1].
 
+core.midx::
+	Enable "multi-pack-index" feature. Set to true to read and write MIDX files.
+
 core.sparseCheckout::
 	Enable "sparse checkout" feature. See section "Sparse checkout" in
 	linkgit:git-read-tree[1] for more information.

index a2ec8c0b55..f4943d3136 100644
@@ -820,6 +820,7 @@ extern int precomposed_unicode;
 extern int protect_hfs;
 extern int protect_ntfs;
 extern const char *core_fsmonitor;
+extern int core_midx;
 
 /*
  * Include broken refs in all ref iterations, which will

index e617c2018d..17f560ddc4 100644
@@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.midx")) {
+		core_midx = git_config_bool(var, value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.sparsecheckout")) {
 		core_apply_sparse_checkout = git_config_bool(var, value);
 		return 0;

index 63ac38a46f..57a3943849 100644
@@ -78,6 +78,8 @@ int protect_hfs = PROTECT_HFS_DEFAULT;
 int protect_ntfs = PROTECT_NTFS_DEFAULT;
 const char *core_fsmonitor;
 
+int core_midx;
+
 /*
  * The character that begins a commented line in user-editable file
  * that is subject to stripspace.

2.15.0

The write_midx_file() method takes a list of packfiles and indexed objects with offset information and writes according to the format in Documentation/technical/pack-format.txt. The chunks are separated into methods.

---
 Makefile |   1 +
 midx.c   | 412 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 midx.h   |  42 +++++++
 3 files changed, 455 insertions(+)
 create mode 100644 midx.c
 create mode 100644 midx.h

index 2a81ae22e9..d0d810951f 100644
@@ -827,6 +827,7 @@ LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
+LIB_OBJS += midx.o
 LIB_OBJS += mru.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o

2.15.0

Commentary: As we extend the function of the midx builtin, I expand the SYNOPSIS row of "git-midx.txt" but do not create multiple rows. If this builtin doesn't change too much, I will rewrite the SYNOPSIS to be multi- lined, such as in "git-branch.txt".

-- >8 --

Create, document, and implement the first ability of the midx builtin.

The --write subcommand creates a multi-pack-index for all indexed packfiles within a given pack directory. If none is provided, the objects/pack directory is implied. The arguments allow specifying the pack directory so we can add MIDX files to alternates.

The packfiles are expected to be paired with pack-indexes and are otherwise ignored. This simplifies the implementation and also keeps compatibility with older versions of Git (or changing core.midx to false).

---
 .gitignore                 |   1 +
 Documentation/git-midx.txt |  54 +++++++++++++
 Makefile                   |   1 +
 builtin.h                  |   1 +
 builtin/midx.c             | 195 +++++++++++++++++++++++++++++++++++++++++++++
 command-list.txt           |   1 +
 git.c                      |   1 +
 7 files changed, 254 insertions(+)
 create mode 100644 Documentation/git-midx.txt
 create mode 100644 builtin/midx.c

index 833ef3b0b7..545e195f2a 100644
@@ -95,6 +95,7 @@
 /git-merge-subtree
 /git-mergetool
 /git-mergetool--lib
+/git-midx
 /git-mktag
 /git-mktree
 /git-name-rev

index d0d810951f..5c458705c1 100644
@@ -980,6 +980,7 @@ BUILTIN_OBJS += builtin/merge-index.o
 BUILTIN_OBJS += builtin/merge-ours.o
 BUILTIN_OBJS += builtin/merge-recursive.o
 BUILTIN_OBJS += builtin/merge-tree.o
+BUILTIN_OBJS += builtin/midx.o
 BUILTIN_OBJS += builtin/mktag.o
 BUILTIN_OBJS += builtin/mktree.o
 BUILTIN_OBJS += builtin/mv.o

index 42378f3aa4..880383e341 100644
@@ -188,6 +188,7 @@ extern int cmd_merge_ours(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_file(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_recursive(int argc, const char **argv, const char *prefix);
 extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);
+extern int cmd_midx(int argc, const char **argv, const char *prefix);
 extern int cmd_mktag(int argc, const char **argv, const char *prefix);
 extern int cmd_mktree(int argc, const char **argv, const char *prefix);
 extern int cmd_mv(int argc, const char **argv, const char *prefix);

index a1fad28fd8..a7b9412182 100644
@@ -87,6 +87,7 @@ git-merge-index                         plumbingmanipulators
 git-merge-one-file                      purehelpers
 git-mergetool                           ancillarymanipulators
 git-merge-tree                          ancillaryinterrogators
+git-midx                                plumbingmanipulators
 git-mktag                               plumbingmanipulators
 git-mktree                              plumbingmanipulators
 git-mv                                  mainporcelain           worktree

index c870b9719c..87fbda8463 100644
@@ -431,6 +431,7 @@ static struct cmd_struct commands[] = {
 	{ "merge-recursive-theirs", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },
 	{ "merge-subtree", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },
 	{ "merge-tree", cmd_merge_tree, RUN_SETUP },
+	{ "midx", cmd_midx, RUN_SETUP },
 	{ "mktag", cmd_mktag, RUN_SETUP },
 	{ "mktree", cmd_mktree, RUN_SETUP },
 	{ "mv", cmd_mv, RUN_SETUP | NEED_WORK_TREE },

2.15.0

Test interactions between the midx builtin and other Git operations.

Use both a full repo and a bare repo to ensure the pack directory redirection works correctly.

---
 t/t5318-midx.sh | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
 create mode 100755 t/t5318-midx.sh

new file mode 100755
index 0000000000..869bbea29c
@@ -0,0 +1,100 @@
+#!/bin/sh
+
+test_description='multi-pack indexes'
+. ./test-lib.sh
+
+test_expect_success 'config' \
+    'rm -rf .git &&
+     mkdir full &&
+     cd full &&
+     git init &&
+     git config core.midx true &&
+     git config pack.threads 1 &&
+     packdir=.git/objects/pack'
+
+test_expect_success 'write-midx with no packs' \
+    'midx0=$(git midx --write) &&
+     test "a$midx0" = "a"'
+
+test_expect_success 'create objects' \
+    'for i in $(test_seq 100)
+     do
+         echo $i >file-1-$i
+     done &&
+     git add file-* &&
+     test_tick &&
+     git commit -m "test data 1" &&
+     git branch commit1 HEAD'
+
+test_expect_success 'write-midx from index version 1' \
+    'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&
+     midx1=$(git midx --write) &&
+     test_path_is_file ${packdir}/midx-${midx1}.midx'
+
+test_expect_success 'write-midx from index version 2' \
+    'rm "${packdir}/test-1-${pack1}.pack" &&
+     pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&
+     midx2=$(git midx --write) &&
+     test_path_is_file ${packdir}/midx-${midx2}.midx'
+
+test_expect_success 'Create more objects' \
+    'for i in $(test_seq 100)
+     do
+         echo $i >file-2-$i
+     done &&
+     git add file-* &&
+     test_tick &&
+     git commit -m "test data 2" &&
+     git branch commit2 HEAD'
+
+test_expect_success 'write-midx with two packs' \
+    'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&
+     midx3=$(git midx --write) &&
+     test_path_is_file ${packdir}/midx-${midx3}.midx'
+
+test_expect_success 'Add more packs' \
+    'for j in $(test_seq 10)
+     do
+         jjj=$(printf '%03i' $j)
+         test-genrandom "bar" 200 > wide_delta_$jjj &&
+         test-genrandom "baz $jjj" 50 >> wide_delta_$jjj &&
+         test-genrandom "foo"$j 100 > deep_delta_$jjj &&
+         test-genrandom "foo"$(expr $j + 1) 100 >> deep_delta_$jjj &&
+         test-genrandom "foo"$(expr $j + 2) 100 >> deep_delta_$jjj &&
+         echo $jjj >file_$jjj &&
+         test-genrandom "$jjj" 8192 >>file_$jjj &&
+         git update-index --add file_$jjj deep_delta_$jjj wide_delta_$jjj &&
+         { echo 101 && test-genrandom 100 8192; } >file_101 &&
+         git update-index --add file_101 &&
+         commit=$(git commit-tree $EMPTY_TREE -p HEAD</dev/null) && {
+         echo $EMPTY_TREE &&
+         git ls-tree $EMPTY_TREE | sed -e "s/.* \\([0-9a-f]*\\)	.*/\\1/"
+         } >obj-list &&
+         echo commit_packs_$j = $commit &&
+	 git branch commit_packs_$j $commit &&
+         git update-ref HEAD $commit &&
+         git pack-objects --index-version=2 ${packdir}/test-pack <obj-list
+     done'
+
+test_expect_success 'write-midx with twelve packs' \
+    'midx4=$(git midx --write) &&
+     test_path_is_file ${packdir}/midx-${midx4}.midx'
+
+test_expect_success 'write-midx with no new packs' \
+    'midx5=$(git midx --write) &&
+     test_path_is_file ${packdir}/midx-${midx5}.midx &&
+     test "a$midx4" = "a$midx5"'
+
+test_expect_success 'create bare repo' \
+    'cd .. &&
+     git clone --bare full bare &&
+     cd bare &&
+     git config core.midx true &&
+     git config pack.threads 1 &&
+     baredir=objects/pack'
+
+test_expect_success 'write-midx in bare repo' \
+    'midxbare=$(git midx --write) &&
+     test_path_is_file ${baredir}/midx-${midxbare}.midx'
+
+test_done

2.15.0

There may be multiple MIDX files in a single pack directory. The primary file is pointed to by a pointer file "midx-head" that contains an OID. The MIDX file to load is then given by "midx-<OID>.midx".

This head file will be especially important when the MIDX files are extended to be incremental and we expect multiple MIDX files at any point.

---
 Documentation/git-midx.txt | 19 ++++++++++++++++++-
 builtin/midx.c             | 32 ++++++++++++++++++++++++++++++--
 midx.c                     | 31 +++++++++++++++++++++++++++++++
 midx.h                     |  3 +++
 t/t5318-midx.sh            | 33 ++++++++++++++++++++++-----------
 5 files changed, 104 insertions(+), 14 deletions(-)

index 17464222c1..01f79cbba5 100644
@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).
 SYNOPSIS
 --------
 [verse]
-'git midx' --write [--pack-dir <pack_dir>]
+'git midx' --write <options> [--pack-dir <pack_dir>]
 
 DESCRIPTION
 -----------

@@ -26,15 +26,32 @@ OPTIONS
 	If specified, write a new midx file to the pack directory using
 	the packfiles present. Outputs the hash of the result midx file.
 
+--update-head::
+	If specified with --write, update the midx-head file to point to
+	the written midx file.
+
 EXAMPLES
 --------
 
+* Read the midx-head file and output the OID of the head MIDX file.
++
+------------------------------------------------
+$ git midx
+------------------------------------------------
+
 * Write a MIDX file for the packfiles in your local .git folder.
 +
 ------------------------------------------------
 $ git midx --write
 ------------------------------------------------
 
+* Write a MIDX file for the packfiles in your local .git folder and
+* update the midx-head file.
++
+------------------------------------------------
+$ git midx --write --update-head
+------------------------------------------------
+
 * Write a MIDX file for the packfiles in a different folder
 +
 ---------------------------------------------------------

index 4aae14cf8e..84ce6588a2 100644
@@ -9,13 +9,17 @@
 #include "midx.h"
 
 static char const * const builtin_midx_usage[] = {
-	N_("git midx --write [--pack-dir <packdir>]"),
+	N_("git midx [--pack-dir <packdir>]"),
+	N_("git midx --write [--update-head] [--pack-dir <packdir>]"),
 	NULL
 };
 
 static struct opts_midx {
 	const char *pack_dir;
 	int write;
+	int update_head;
+	int has_existing;
+	struct object_id old_midx_oid;
 } opts;
 
 static int build_midx_from_packs(

@@ -109,6 +113,22 @@ static int build_midx_from_packs(
 	return 0;
 }
 
+static void update_head_file(const char *pack_dir, const char *midx_id)
+{
+	int fd;
+	struct lock_file lk = LOCK_INIT;
+	char *head_path = get_midx_head_filename(pack_dir);
+
+	fd = hold_lock_file_for_update(&lk, head_path, LOCK_DIE_ON_ERROR);
+	FREE_AND_NULL(head_path);
+
+	if (fd < 0)
+		die_errno("unable to open midx-head");
+
+	write_in_full(fd, midx_id, GIT_MAX_HEXSZ);
+	commit_lock_file(&lk);
+}
+
 static int midx_write(void)
 {
 	const char **pack_names = NULL;

@@ -152,6 +172,9 @@ static int midx_write(void)
 
 	printf("%s\n", midx_id);
 
+	if (opts.update_head)
+		update_head_file(opts.pack_dir, midx_id);
+
 cleanup:
 	if (pack_names)
 		FREE_AND_NULL(pack_names);

@@ -166,6 +189,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 			N_("The pack directory containing set of packfile and pack-index pairs.") },
 		OPT_BOOL('w', "write", &opts.write,
 			N_("write midx file")),
+		OPT_BOOL('u', "update-head", &opts.update_head,
+			N_("update midx-head to written midx file")),
 		OPT_END(),
 	};
 

@@ -187,9 +212,12 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 		opts.pack_dir = strbuf_detach(&path, NULL);
 	}
 
+	opts.has_existing = !!get_midx_head_oid(opts.pack_dir, &opts.old_midx_oid);
+
 	if (opts.write)
 		return midx_write();
 
-	usage_with_options(builtin_midx_usage, builtin_midx_options);
+	if (opts.has_existing)
+		printf("%s\n", oid_to_hex(&opts.old_midx_oid));
 	return 0;
 }

index 5c320726ed..f4178c1b81 100644
@@ -34,6 +34,37 @@ char* get_midx_filename_oid(const char *pack_dir,
 	return strbuf_detach(&head_path, NULL);
 }
 
+char *get_midx_head_filename(const char *pack_dir)
+{
+	struct strbuf head_filename = STRBUF_INIT;
+	strbuf_addstr(&head_filename, pack_dir);
+	strbuf_addstr(&head_filename, "/midx-head");
+	return strbuf_detach(&head_filename, NULL);
+}
+
+struct object_id *get_midx_head_oid(const char *pack_dir,
+				    struct object_id *oid)
+{
+	char oid_hex[GIT_MAX_HEXSZ + 1];
+	FILE *f;
+	char *head_filename = get_midx_head_filename(pack_dir);
+
+	f = fopen(head_filename, "r");
+	FREE_AND_NULL(head_filename);
+
+	if (!f)
+		return 0;
+
+	if (!fgets(oid_hex, sizeof(oid_hex), f))
+		die("failed to read midx-head");
+
+	fclose(f);
+
+	if (get_oid_hex(oid_hex, oid))
+		return 0;
+	return oid;
+}
+
 struct pack_midx_details_internal {
 	uint32_t pack_int_id;
 	uint32_t internal_offset;

index 4b00463651..9d9ab85261 100644
@@ -7,6 +7,9 @@
 
 extern char *get_midx_filename_oid(const char *pack_dir,
 				   struct object_id *oid);
+extern char *get_midx_head_filename(const char *pack_dir);
+
+extern struct object_id *get_midx_head_oid(const char *pack_dir, struct object_id *oid);
 
 struct pack_midx_entry {
 	struct object_id oid;

index 869bbea29c..b66efcdce9 100755
@@ -29,13 +29,16 @@ test_expect_success 'create objects' \
 test_expect_success 'write-midx from index version 1' \
     'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&
      midx1=$(git midx --write) &&
-     test_path_is_file ${packdir}/midx-${midx1}.midx'
+     test_path_is_file ${packdir}/midx-${midx1}.midx &&
+     test_path_is_missing ${packdir}/midx-head'
 
 test_expect_success 'write-midx from index version 2' \
     'rm "${packdir}/test-1-${pack1}.pack" &&
      pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&
-     midx2=$(git midx --write) &&
-     test_path_is_file ${packdir}/midx-${midx2}.midx'
+     midx2=$(git midx --write --update-head) &&
+     test_path_is_file ${packdir}/midx-${midx2}.midx &&
+     test_path_is_file ${packdir}/midx-head &&
+     test $(cat ${packdir}/midx-head) = "$midx2"'
 
 test_expect_success 'Create more objects' \
     'for i in $(test_seq 100)

@@ -49,8 +52,10 @@ test_expect_success 'Create more objects' \
 
 test_expect_success 'write-midx with two packs' \
     'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&
-     midx3=$(git midx --write) &&
-     test_path_is_file ${packdir}/midx-${midx3}.midx'
+     midx3=$(git midx --write --update-head) &&
+     test_path_is_file ${packdir}/midx-${midx3}.midx &&
+     test_path_is_file ${packdir}/midx-head &&
+     test $(cat ${packdir}/midx-head) = "$midx3"'
 
 test_expect_success 'Add more packs' \
     'for j in $(test_seq 10)

@@ -77,13 +82,17 @@ test_expect_success 'Add more packs' \
      done'
 
 test_expect_success 'write-midx with twelve packs' \
-    'midx4=$(git midx --write) &&
-     test_path_is_file ${packdir}/midx-${midx4}.midx'
+    'midx4=$(git midx --write --update-head) &&
+     test_path_is_file ${packdir}/midx-${midx4}.midx &&
+     test_path_is_file ${packdir}/midx-head &&
+     test $(cat ${packdir}/midx-head) = "$midx4"'
 
 test_expect_success 'write-midx with no new packs' \
-    'midx5=$(git midx --write) &&
+    'midx5=$(git midx --write --update-head) &&
      test_path_is_file ${packdir}/midx-${midx5}.midx &&
-     test "a$midx4" = "a$midx5"'
+     test "a$midx4" = "a$midx5" &&
+     test_path_is_file ${packdir}/midx-head &&
+     test $(cat ${packdir}/midx-head) = "$midx4"'
 
 test_expect_success 'create bare repo' \
     'cd .. &&

@@ -94,7 +103,9 @@ test_expect_success 'create bare repo' \
      baredir=objects/pack'
 
 test_expect_success 'write-midx in bare repo' \
-    'midxbare=$(git midx --write) &&
-     test_path_is_file ${baredir}/midx-${midxbare}.midx'
+    'midxbare=$(git midx --write --update-head) &&
+     test_path_is_file ${baredir}/midx-${midxbare}.midx  &&
+     test_path_is_file ${baredir}/midx-head &&
+     test $(cat ${baredir}/midx-head) = "$midxbare"'
 
 test_done

2.15.0

Commentary: I included the pack directory of the MIDX file as a FLEX_ARRAY at the end of the midxed_git struct, similar to how the pack name appears at the end of the packed_git struct. A colleague mentioned this pattern is confusing and possibly dangerous so I should consider changing it. If there is no strong reason for this, then I will modify the struct before the v1 patch to use a char*.

-- >8 --

Add a "--read" subcommand to the midx builtin to report summary information on the head MIDX file or a MIDX file specified by the supplied "--midx-id" parameter.

This subcommand is used by t5318-midx.sh to verify the indexed objects are as expected.

---
 Documentation/git-midx.txt |  23 +++++++-
 builtin/midx.c             |  59 ++++++++++++++++++++
 midx.c                     | 132 +++++++++++++++++++++++++++++++++++++++++++++
 midx.h                     |  58 ++++++++++++++++++++
 t/t5318-midx.sh            |  79 +++++++++++++++++++--------
 5 files changed, 328 insertions(+), 23 deletions(-)

index 01f79cbba5..3eeed1d969 100644
@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).
 SYNOPSIS
 --------
 [verse]
-'git midx' --write <options> [--pack-dir <pack_dir>]
+'git midx' [--write|--read] <options> [--pack-dir <pack_dir>]
 
 DESCRIPTION
 -----------

@@ -22,9 +22,18 @@ OPTIONS
 	Use given directory for the location of packfiles, pack-indexes,
 	and MIDX files.
 
+--read::
+	If specified, read a midx file specified by the midx-head file
+	and output basic details about the midx file. (Cannot be combined
+	with --write.)
+
+--midx-id <oid>::
+	If specified with --read, use the given oid to read midx-[oid].midx
+	instead of using midx-head.
 --write::
 	If specified, write a new midx file to the pack directory using
 	the packfiles present. Outputs the hash of the result midx file.
+	(Cannot be combined with --read.)
 
 --update-head::
 	If specified with --write, update the midx-head file to point to

@@ -58,6 +67,18 @@ $ git midx --write --update-head
 $ git midx --write --pack-dir ../../alt/pack/
 ---------------------------------------------------------
 
+* Read the current midx-head.
++
+-----------------------------------------------
+$ git midx --read
+-----------------------------------------------
+
+* Read a specific MIDX file in the local .git folder.
++
+--------------------------------------------------------------------
+$ git midx --read --midx-id 3e50d982a2257168c7fd0ff12ffe5cf6af38c74e
+--------------------------------------------------------------------
+
 CONFIGURATION
 -------------
 

2.15.0

The MIDX file stores pack offset information for a list of objects. The nth_midxed_object_* methods provide ways to extract this information.

---
 midx.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 midx.h | 15 +++++++++++++++
 2 files changed, 70 insertions(+)

index c631be451f..4e0df0285a 100644
@@ -202,6 +202,61 @@ struct pack_midx_details_internal {
 	uint32_t internal_offset;
 };
 
+struct pack_midx_details *nth_midxed_object_details(struct midxed_git *m,
+						    uint32_t n,
+						    struct pack_midx_details *d)
+{
+	struct pack_midx_details_internal *d_internal;
+	const unsigned char *details = m->chunk_object_offsets;
+
+	if (n >= m->num_objects)
+		return NULL;
+
+	d_internal = (struct pack_midx_details_internal*)(details + 8 * n);
+	d->pack_int_id = ntohl(d_internal->pack_int_id);
+	d->offset = ntohl(d_internal->internal_offset);
+
+	if (m->chunk_large_offsets && d->offset & MIDX_LARGE_OFFSET_NEEDED) {
+		uint32_t large_offset = d->offset ^ MIDX_LARGE_OFFSET_NEEDED;
+		const unsigned char *large_offsets = m->chunk_large_offsets + 8 * large_offset;
+
+		d->offset =  (((uint64_t)ntohl(*((uint32_t *)(large_offsets + 0)))) << 32) |
+					 ntohl(*((uint32_t *)(large_offsets + 4)));
+	}
+
+	return d;
+}
+
+struct pack_midx_entry *nth_midxed_object_entry(struct midxed_git *m,
+						uint32_t n,
+						struct pack_midx_entry *e)
+{
+	struct pack_midx_details details;
+	const unsigned char *index = m->chunk_oid_lookup;
+
+	if (!nth_midxed_object_details(m, n, &details))
+		return NULL;
+
+	memcpy(e->oid.hash, index + m->hdr->hash_len * n, m->hdr->hash_len);
+	e->pack_int_id = details.pack_int_id;
+	e->offset = details.offset;
+
+	return e;
+}
+
+const struct object_id *nth_midxed_object_oid(struct object_id *oid,
+					      struct midxed_git *m,
+					      uint32_t n)
+{
+	struct pack_midx_entry e;
+
+	if (!nth_midxed_object_entry(m, n, &e))
+		return 0;
+
+	hashcpy(oid->hash, e.oid.hash);
+	return oid;
+}
+
 static int midx_sha1_compare(const void *_a, const void *_b)
 {
 	struct pack_midx_entry *a = *(struct pack_midx_entry **)_a;

index 92b74e49db..9255909ae8 100644
@@ -85,6 +85,21 @@ struct midxed_git {
 
 extern struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid);
 
+struct pack_midx_details {
+	uint32_t pack_int_id;
+	off_t offset;
+};
+
+extern struct pack_midx_details *nth_midxed_object_details(struct midxed_git *m,
+							   uint32_t n,
+							   struct pack_midx_details *d);
+extern struct pack_midx_entry *nth_midxed_object_entry(struct midxed_git *m,
+						       uint32_t n,
+						       struct pack_midx_entry *e);
+extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,
+						     struct midxed_git *m,
+						     uint32_t n);
+
 /*
  * Write a single MIDX file storing the given entries for the
  * given list of packfiles. If midx_name is null, then a temp

2.15.0

When writing a new MIDX file, it is faster to use an existing MIDX file to load the object list and pack offsets and to only inspect pack-indexes for packs not already covered by the MIDX file.

---
 builtin/midx.c | 34 +++++++++++++++++++++++++++++++---
 midx.c         | 23 +++++++++++++++++++++++
 midx.h         |  2 ++
 3 files changed, 56 insertions(+), 3 deletions(-)

index ee9234583d..aff2085771 100644
@@ -73,7 +73,7 @@ static int midx_read(void)
 static int build_midx_from_packs(
 	const char *pack_dir,
 	const char **pack_names, uint32_t nr_packs,
-	const char **midx_id)
+	const char **midx_id, struct midxed_git *midx)
 {
 	struct packed_git **packs;
 	const char **installed_pack_names;

@@ -86,6 +86,9 @@ static int build_midx_from_packs(
 	struct strbuf pack_path = STRBUF_INIT;
 	int baselen;
 
+	if (midx)
+		nr_total_packs += midx->num_packs;
+
 	if (!nr_total_packs) {
 		*midx_id = NULL;
 		return 0;

@@ -94,6 +97,12 @@ static int build_midx_from_packs(
 	ALLOC_ARRAY(packs, nr_total_packs);
 	ALLOC_ARRAY(installed_pack_names, nr_total_packs);
 
+	if (midx) {
+		for (i = 0; i < midx->num_packs; i++)
+			installed_pack_names[nr_installed_packs++] = midx->pack_names[i];
+		pack_offset = midx->num_packs;
+	}
+
 	strbuf_addstr(&pack_path, pack_dir);
 	strbuf_addch(&pack_path, '/');
 	baselen = pack_path.len;

@@ -101,6 +110,9 @@ static int build_midx_from_packs(
 		strbuf_setlen(&pack_path, baselen);
 		strbuf_addstr(&pack_path, pack_names[i]);
 
+		if (midx && contains_pack(midx, pack_names[i]))
+			continue;
+
 		strbuf_strip_suffix(&pack_path, ".pack");
 		strbuf_addstr(&pack_path, ".idx");
 

@@ -120,13 +132,24 @@ static int build_midx_from_packs(
 	if (!nr_objects || !nr_installed_packs) {
 		FREE_AND_NULL(packs);
 		FREE_AND_NULL(installed_pack_names);
-		*midx_id = NULL;
+
+		if (opts.has_existing)
+			*midx_id = oid_to_hex(&opts.old_midx_oid);
+		else
+			*midx_id = NULL;
+
 		return 0;
 	}
 
+	if (midx)
+		nr_objects += midx->num_objects;
+
 	ALLOC_ARRAY(objects, nr_objects);
 	nr_objects = 0;
 
+	for (i = 0; midx && i < midx->num_objects; i++)
+		nth_midxed_object_entry(midx, i, &objects[nr_objects++]);
+
 	for (i = pack_offset; i < nr_installed_packs; i++) {
 		struct packed_git *p = packs[i];
 

@@ -184,6 +207,10 @@ static int midx_write(void)
 	const char *midx_id = 0;
 	DIR *dir;
 	struct dirent *de;
+	struct midxed_git *midx = NULL;
+
+	if (opts.has_existing)
+		midx = get_midxed_git(opts.pack_dir, &opts.old_midx_oid);
 
 	dir = opendir(opts.pack_dir);
 	if (!dir) {

@@ -212,7 +239,8 @@ static int midx_write(void)
 	if (!nr_packs)
 		goto cleanup;
 
-	if (build_midx_from_packs(opts.pack_dir, pack_names, nr_packs, &midx_id))
+	if (build_midx_from_packs(opts.pack_dir, pack_names,
+				  nr_packs, &midx_id, midx))
 		die("failed to build MIDX");
 
 	if (midx_id == NULL)

index 4e0df0285a..53eb29dac3 100644
@@ -257,6 +257,29 @@ const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 	return oid;
 }
 
+int contains_pack(struct midxed_git *m, const char *pack_name)
+{
+	uint32_t first = 0, last = m->num_packs;
+
+	while (first < last) {
+		uint32_t mid = first + (last - first) / 2;
+		const char *current;
+		int cmp;
+
+		current = m->pack_names[mid];
+		cmp = strcmp(pack_name, current);
+		if (!cmp)
+			return 1;
+		if (cmp > 0) {
+			first = mid + 1;
+			continue;
+		}
+		last = mid;
+	}
+
+	return 0;
+}
+
 static int midx_sha1_compare(const void *_a, const void *_b)
 {
 	struct pack_midx_entry *a = *(struct pack_midx_entry **)_a;

index 9255909ae8..1e7a94651c 100644
@@ -100,6 +100,8 @@ extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 						     struct midxed_git *m,
 						     uint32_t n);
 
+extern int contains_pack(struct midxed_git *m, const char *pack_name);
+
 /*
  * Write a single MIDX file storing the given entries for the
  * given list of packfiles. If midx_name is null, then a temp

2.15.0

As a way to troubleshoot unforeseen problems with MIDX files, provide a way to delete "midx-head" and the MIDX it references.

---
 Documentation/git-midx.txt | 12 +++++++++++-
 builtin/midx.c             | 31 ++++++++++++++++++++++++++++++-
 t/t5318-midx.sh            |  9 +++++++++
 3 files changed, 50 insertions(+), 2 deletions(-)

index 3eeed1d969..c184d3a593 100644
@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).
 SYNOPSIS
 --------
 [verse]
-'git midx' [--write|--read] <options> [--pack-dir <pack_dir>]
+'git midx' [--write|--read|--clear] <options> [--pack-dir <pack_dir>]
 
 DESCRIPTION
 -----------

@@ -22,6 +22,10 @@ OPTIONS
 	Use given directory for the location of packfiles, pack-indexes,
 	and MIDX files.
 
+--clear::
+	If specified, delete the midx file specified by midx-head, and
+	midx-head. (Cannot be combined with --write or --read.)
+
 --read::
 	If specified, read a midx file specified by the midx-head file
 	and output basic details about the midx file. (Cannot be combined

@@ -79,6 +83,12 @@ $ git midx --read
 $ git midx --read --midx-id 3e50d982a2257168c7fd0ff12ffe5cf6af38c74e
 --------------------------------------------------------------------
 
+* Delete the current midx-head and the file it references.
++
+-----------------------------------------------
+$ git midx --clear
+-----------------------------------------------
+
 CONFIGURATION
 -------------
 

index aff2085771..b30ef36ff8 100644
@@ -11,11 +11,13 @@
 static char const * const builtin_midx_usage[] = {
 	N_("git midx [--pack-dir <packdir>]"),
 	N_("git midx --write [--update-head] [--pack-dir <packdir>]"),
+	N_("git midx --clear [--pack-dir <packdir>]"),
 	NULL
 };
 
 static struct opts_midx {
 	const char *pack_dir;
+	int clear;
 	int read;
 	const char *midx_id;
 	int write;

@@ -24,6 +26,29 @@ static struct opts_midx {
 	struct object_id old_midx_oid;
 } opts;
 
+static int midx_clear(void)
+{
+	struct strbuf head_path = STRBUF_INIT;
+	char *old_path;
+
+	if (!opts.has_existing)
+		return 0;
+
+	strbuf_addstr(&head_path, opts.pack_dir);
+	strbuf_addstr(&head_path, "/");
+	strbuf_addstr(&head_path, "midx-head");
+	if (remove_path(head_path.buf))
+		die("failed to remove path %s", head_path.buf);
+	strbuf_release(&head_path);
+
+	old_path = get_midx_filename_oid(opts.pack_dir, &opts.old_midx_oid);
+	if (remove_path(old_path))
+		die("failed to remove path %s", old_path);
+	free(old_path);
+
+	return 0;
+}
+
 static int midx_read(void)
 {
 	struct object_id midx_oid;

@@ -263,6 +288,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 		{ OPTION_STRING, 'p', "pack-dir", &opts.pack_dir,
 			N_("dir"),
 			N_("The pack directory containing set of packfile and pack-index pairs.") },
+		OPT_BOOL('c', "clear", &opts.clear,
+			N_("clear midx file and midx-head")),
 		OPT_BOOL('r', "read", &opts.read,
 			N_("read midx file")),
 		{ OPTION_STRING, 'M', "midx-id", &opts.midx_id,

@@ -287,7 +314,7 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 			     builtin_midx_options,
 			     builtin_midx_usage, 0);
 
-	if (opts.write + opts.read > 1)
+	if (opts.write + opts.read + opts.clear > 1)
 		usage_with_options(builtin_midx_usage, builtin_midx_options);
 
 	if (!opts.pack_dir) {

@@ -299,6 +326,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 
 	opts.has_existing = !!get_midx_head_oid(opts.pack_dir, &opts.old_midx_oid);
 
+	if (opts.clear)
+		return midx_clear();
 	if (opts.read)
 		return midx_read();
 	if (opts.write)

index 2e52389442..9337355ab3 100755
@@ -143,4 +143,13 @@ test_expect_success 'write-midx in bare repo' \
      git midx --read >output &&
      cmp output expect'
 
+test_expect_success 'midx --clear' \
+    'git midx --clear &&
+     test_path_is_missing "${baredir}/midx-${midx4}.midx" &&
+     test_path_is_missing "${baredir}/midx-head" &&
+     cd ../full &&
+     git midx --clear &&
+     test_path_is_missing "${packdir}/midx-${midx4}.midx" &&
+     test_path_is_missing "${packdir}/midx-head"'
+
 test_done

2.15.0

As we write new MIDX files, the existing files are probably not needed. Supply the "--delete-expired" flag to remove these files during the "--write" sub- command.

---
 Documentation/git-midx.txt |  4 ++++
 builtin/midx.c             | 15 ++++++++++++++-
 midx.c                     | 26 ++++++++++++++++++++++++++
 midx.h                     |  2 ++
 packfile.c                 |  2 +-
 packfile.h                 |  1 +
 t/t5318-midx.sh            |  9 ++++++---
 7 files changed, 54 insertions(+), 5 deletions(-)

index c184d3a593..4635247d0d 100644
@@ -43,6 +43,10 @@ OPTIONS
 	If specified with --write, update the midx-head file to point to
 	the written midx file.
 
+--delete-expired::
+	If specified with --write and --update-head, delete the midx file
+	previously pointed to by midx-head (if changed).
+
 EXAMPLES
 --------
 

index b30ef36ff8..6f56f39390 100644
@@ -10,7 +10,7 @@
 
 static char const * const builtin_midx_usage[] = {
 	N_("git midx [--pack-dir <packdir>]"),
-	N_("git midx --write [--update-head] [--pack-dir <packdir>]"),
+	N_("git midx --write [--update-head [--delete-expired]] [--pack-dir <packdir>]"),
 	N_("git midx --clear [--pack-dir <packdir>]"),
 	NULL
 };

@@ -22,6 +22,7 @@ static struct opts_midx {
 	const char *midx_id;
 	int write;
 	int update_head;
+	int delete_expired;
 	int has_existing;
 	struct object_id old_midx_oid;
 } opts;

@@ -276,6 +277,16 @@ static int midx_write(void)
 	if (opts.update_head)
 		update_head_file(opts.pack_dir, midx_id);
 
+	if (opts.delete_expired && opts.update_head && opts.has_existing &&
+	    strcmp(midx_id, oid_to_hex(&opts.old_midx_oid))) {
+		char *old_path = get_midx_filename_oid(opts.pack_dir, &opts.old_midx_oid);
+		close_midx(midx);
+		if (remove_path(old_path))
+			die("failed to remove path %s", old_path);
+
+		free(old_path);
+	}
+
 cleanup:
 	if (pack_names)
 		FREE_AND_NULL(pack_names);

@@ -300,6 +311,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)
 			N_("write midx file")),
 		OPT_BOOL('u', "update-head", &opts.update_head,
 			N_("update midx-head to written midx file")),
+		OPT_BOOL('d', "delete-expired", &opts.delete_expired,
+			N_("delete expired head midx file")),
 		OPT_END(),
 	};
 

index 53eb29dac3..3ce2b736ea 100644
@@ -651,3 +651,29 @@ const char *write_midx_file(const char *pack_dir,
 
 	return final_hex;
 }
+
+int close_midx(struct midxed_git *m)
+{
+	int i;
+	if (m->midx_fd < 0)
+		return 0;
+
+	for (i = 0; i < m->num_packs; i++) {
+		if (m->packs[i]) {
+			close_pack(m->packs[i]);
+			free(m->packs[i]);
+			m->packs[i] = NULL;
+		}
+	}
+
+	munmap((void *)m->data, m->data_len);
+	m->data = 0;
+
+	close(m->midx_fd);
+	m->midx_fd = -1;
+
+	free(m->packs);
+	free(m->pack_names);
+
+	return 1;
+}

index 1e7a94651c..27d48163e9 100644
@@ -117,4 +117,6 @@ extern const char *write_midx_file(const char *pack_dir,
 				   struct pack_midx_entry **objects,
 				   uint32_t nr_objects);
 
+extern int close_midx(struct midxed_git *m);
+
 #endif

index 4a5fe7ab18..c36420b33f 100644
@@ -299,7 +299,7 @@ void close_pack_index(struct packed_git *p)
 	}
 }
 
-static void close_pack(struct packed_git *p)
+void close_pack(struct packed_git *p)
 {
 	close_pack_windows(p);
 	close_pack_fd(p);

index 0cdeb54dcd..7cf4771029 100644
@@ -61,6 +61,7 @@ extern void close_pack_index(struct packed_git *);
 
 extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);
 extern void close_pack_windows(struct packed_git *);
+extern void close_pack(struct packed_git *p);
 extern void close_all_packs(void);
 extern void unuse_pack(struct pack_window **);
 extern void clear_delta_base_cache(void);

index 9337355ab3..42d103c879 100755
@@ -75,6 +75,7 @@ test_expect_success 'write-midx with two packs' \
     'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&
      midx3=$(git midx --write --update-head) &&
      test_path_is_file ${packdir}/midx-${midx3}.midx &&
+     test_path_is_file ${packdir}/midx-${midx2}.midx &&
      test_path_is_file ${packdir}/midx-head &&
      test $(cat ${packdir}/midx-head) = "$midx3" &&
      _midx_read_expect \

@@ -107,8 +108,10 @@ test_expect_success 'Add more packs' \
      done'
 
 test_expect_success 'write-midx with twelve packs' \
-    'midx4=$(git midx --write --update-head) &&
+    'midx4=$(git midx --write --update-head --delete-expired) &&
      test_path_is_file ${packdir}/midx-${midx4}.midx &&
+     test_path_is_missing ${packdir}/midx-${midx3}.midx &&
+     test_path_is_file ${packdir}/midx-${midx2}.midx &&
      test_path_is_file ${packdir}/midx-head &&
      test $(cat ${packdir}/midx-head) = "$midx4" &&
      _midx_read_expect \

@@ -118,7 +121,7 @@ test_expect_success 'write-midx with twelve packs' \
      cmp output expect'
 
 test_expect_success 'write-midx with no new packs' \
-    'midx5=$(git midx --write --update-head) &&
+    'midx5=$(git midx --write --update-head --delete-expired) &&
      test_path_is_file ${packdir}/midx-${midx5}.midx &&
      test "a$midx4" = "a$midx5" &&
      test_path_is_file ${packdir}/midx-head &&

@@ -133,7 +136,7 @@ test_expect_success 'create bare repo' \
      baredir=./objects/pack'
 
 test_expect_success 'write-midx in bare repo' \
-    'midxbare=$(git midx --write --update-head) &&
+    'midxbare=$(git midx --write --update-head --delete-expired) &&
      test_path_is_file ${baredir}/midx-${midxbare}.midx  &&
      test_path_is_file ${baredir}/midx-head &&
      test $(cat ${baredir}/midx-head) = "$midxbare" &&

2.15.0

Perform some basic read-only operations that load objects and find abbreviations. As this functionality begins to reference MIDX files, ensure the output matches when using MIDX files and when not using them.

---
 t/t5318-midx.sh | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

index 42d103c879..00be852ed3 100755
@@ -37,6 +37,19 @@ _midx_read_expect() {
 	EOF
 }
 
+_midx_git_two_modes() {
+	git -c core.midx=true $1 >output
+	git -c core.midx=false $1 >expect
+}
+
+_midx_git_behavior() {
+	test_expect_success 'check normal git operations' \
+	    '_midx_git_two_modes "log --patch master" &&
+	     cmp output expect &&
+	     _midx_git_two_modes "rev-list --all --objects" &&
+	     cmp output expect'
+}
+
 test_expect_success 'write-midx from index version 1' \
     'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&
      midx1=$(git midx --write) &&

@@ -48,6 +61,8 @@ test_expect_success 'write-midx from index version 1' \
      git midx --read --midx-id=${midx1} >output &&
      cmp output expect'
 
+_midx_git_behavior
+
 test_expect_success 'write-midx from index version 2' \
     'rm "${packdir}/test-1-${pack1}.pack" &&
      pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&

@@ -61,6 +76,8 @@ test_expect_success 'write-midx from index version 2' \
      git midx --read> output &&
      cmp output expect'
 
+_midx_git_behavior
+
 test_expect_success 'Create more objects' \
     'for i in $(test_seq 100)
      do

@@ -71,6 +88,8 @@ test_expect_success 'Create more objects' \
      git commit -m "test data 2" &&
      git branch commit2 HEAD'
 
+_midx_git_behavior
+
 test_expect_success 'write-midx with two packs' \
     'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&
      midx3=$(git midx --write --update-head) &&

@@ -84,6 +103,8 @@ test_expect_success 'write-midx with two packs' \
      git midx --read >output &&
      cmp output expect'
 
+_midx_git_behavior
+
 test_expect_success 'Add more packs' \
     'for i in $(test_seq 10)
      do

@@ -107,6 +128,8 @@ test_expect_success 'Add more packs' \
          git pack-objects --index-version=2 ${packdir}/test-pack <obj-list
      done'
 
+_midx_git_behavior
+
 test_expect_success 'write-midx with twelve packs' \
     'midx4=$(git midx --write --update-head --delete-expired) &&
      test_path_is_file ${packdir}/midx-${midx4}.midx &&

@@ -120,6 +143,8 @@ test_expect_success 'write-midx with twelve packs' \
      git midx --read >output &&
      cmp output expect'
 
+_midx_git_behavior
+
 test_expect_success 'write-midx with no new packs' \
     'midx5=$(git midx --write --update-head --delete-expired) &&
      test_path_is_file ${packdir}/midx-${midx5}.midx &&

@@ -127,6 +152,8 @@ test_expect_success 'write-midx with no new packs' \
      test_path_is_file ${packdir}/midx-head &&
      test $(cat ${packdir}/midx-head) = "$midx4"'
 
+_midx_git_behavior
+
 test_expect_success 'create bare repo' \
     'cd .. &&
      git clone --bare full bare &&

@@ -146,6 +173,8 @@ test_expect_success 'write-midx in bare repo' \
      git midx --read >output &&
      cmp output expect'
 
+_midx_git_behavior
+
 test_expect_success 'midx --clear' \
     'git midx --clear &&
      test_path_is_missing "${baredir}/midx-${midx4}.midx" &&

@@ -155,4 +184,6 @@ test_expect_success 'midx --clear' \
      test_path_is_missing "${packdir}/midx-${midx4}.midx" &&
      test_path_is_missing "${packdir}/midx-head"'
 
+_midx_git_behavior
+
 test_done

2.15.0

Replace prepare_packed_git() with prepare_packed_git_internal(use_midx) to allow some consumers of prepare_packed_git() with a way to load MIDX files. Consumers should only use the new method if they are prepared to use the midxed_git struct alongside the packed_git struct.

If a packfile is found that is not referenced by the current MIDX, then add it to the packed_git struct. This is important to keep the MIDX useful after adding packs due to "fetch" commands and when third-party tools (such as libgit2) add packs directly to the repo.

If prepare_packed_git_internal is called with use_midx = 0, then unload the MIDX file and reload the packfiles in to the packed_git struct.

---
 midx.c     | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 midx.h     |  6 ++++--
 packfile.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++---------
 packfile.h |  1 +
 4 files changed, 117 insertions(+), 11 deletions(-)

index 3ce2b736ea..a66763b9e3 100644
@@ -22,6 +22,9 @@
 
 #define MIDX_LARGE_OFFSET_NEEDED 0x80000000
 
+/* MIDX-git global storage */
+struct midxed_git *midxed_git = 0;
+
 char* get_midx_filename_oid(const char *pack_dir,
 			    struct object_id *oid)
 {

@@ -197,6 +200,45 @@ struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid)
 	return m;
 }
 
+static char* get_midx_filename_dir(const char *pack_dir)
+{
+	struct object_id oid;
+	if (!get_midx_head_oid(pack_dir, &oid))
+		return 0;
+
+	return get_midx_filename_oid(pack_dir, &oid);
+}
+
+static int prepare_midxed_git_head(char *pack_dir, int local)
+{
+	struct midxed_git *m = midxed_git;
+	char *midx_head_path = get_midx_filename_dir(pack_dir);
+
+	if (!core_midx)
+		return 1;
+
+	if (midx_head_path) {
+		midxed_git = load_midxed_git_one(midx_head_path, pack_dir);
+		midxed_git->next = m;
+		FREE_AND_NULL(midx_head_path);
+		return 1;
+	}
+
+	return 0;
+}
+
+int prepare_midxed_git_objdir(char *obj_dir, int local)
+{
+	int ret;
+	struct strbuf pack_dir = STRBUF_INIT;
+	strbuf_addstr(&pack_dir, obj_dir);
+	strbuf_add(&pack_dir, "/pack", 5);
+
+	ret = prepare_midxed_git_head(pack_dir.buf, local);
+	strbuf_release(&pack_dir);
+	return ret;
+}
+
 struct pack_midx_details_internal {
 	uint32_t pack_int_id;
 	uint32_t internal_offset;

@@ -677,3 +719,18 @@ int close_midx(struct midxed_git *m)
 
 	return 1;
 }
+
+void close_all_midx(void)
+{
+	struct midxed_git *m = midxed_git;
+	struct midxed_git *next;
+
+	while (m) {
+		next = m->next;
+		close_midx(m);
+		free(m);
+		m = next;
+	}
+
+	midxed_git = 0;
+}

index 27d48163e9..d8ede8121c 100644
@@ -27,7 +27,7 @@ struct pack_midx_header {
 	uint32_t num_packs;
 };
 
-struct midxed_git {
+extern struct midxed_git {
 	struct midxed_git *next;
 
 	int midx_fd;

@@ -81,9 +81,10 @@ struct midxed_git {
 
 	/* something like ".git/objects/pack" */
 	char pack_dir[FLEX_ARRAY]; /* more */
-};
+} *midxed_git;
 
 extern struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid);
+extern int prepare_midxed_git_objdir(char *obj_dir, int local);
 
 struct pack_midx_details {
 	uint32_t pack_int_id;

@@ -118,5 +119,6 @@ extern const char *write_midx_file(const char *pack_dir,
 				   uint32_t nr_objects);
 
 extern int close_midx(struct midxed_git *m);
+extern void close_all_midx(void);
 
 #endif

index 7cf4771029..25bac91efb 100644
@@ -32,6 +32,7 @@ extern struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_
 #define PACKDIR_FILE_GARBAGE 4
 extern void (*report_garbage)(unsigned seen_bits, const char *path);
 
+extern void prepare_packed_git_internal(int use_midx);
 extern void prepare_packed_git(void);
 extern void reprepare_packed_git(void);
 extern void install_packed_git(struct packed_git *pack);

2.15.0

The MIDX files contain a complete object count, so we can report the number of objects in the MIDX. The count remains approximate as there may be overlap between the packfiles not referenced by the MIDX.

---
 packfile.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

index 1c0822878b..866a1f30dd 100644
@@ -803,7 +803,8 @@ static void prepare_packed_git_one(char *objdir, int local)
 		if (ends_with(de->d_name, ".idx") ||
 		    ends_with(de->d_name, ".pack") ||
 		    ends_with(de->d_name, ".bitmap") ||
-		    ends_with(de->d_name, ".keep"))
+		    ends_with(de->d_name, ".keep") ||
+		    ends_with(de->d_name, ".midx"))
 			string_list_append(&garbage, path.buf);
 		else
 			report_garbage(PACKDIR_FILE_GARBAGE, path.buf);

@@ -828,9 +829,12 @@ unsigned long approximate_object_count(void)
 	static unsigned long count;
 	if (!approximate_object_count_valid) {
 		struct packed_git *p;
+		struct midxed_git *m;
 
-		prepare_packed_git();
+		prepare_packed_git_internal(1);
 		count = 0;
+		for (m = midxed_git; m; m = m->next)
+			count += m->num_objects;
 		for (p = packed_git; p; p = p->next) {
 			if (open_pack_index(p))
 				continue;

2.15.0

Using a binary search, we can navigate to the position n within a MIDX file where an object appears in the ordered list of objects.

---
 midx.c | 30 ++++++++++++++++++++++++++++++
 midx.h |  9 +++++++++
 2 files changed, 39 insertions(+)

index a66763b9e3..8c643caa92 100644
@@ -299,6 +299,36 @@ const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 	return oid;
 }
 
+int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos)
+{
+	uint32_t last, first = 0;
+
+	if (sha1[0])
+		first = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * (sha1[0] - 1)));
+	last = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * sha1[0]));
+
+	while (first < last) {
+		uint32_t mid = first + (last - first) / 2;
+		const unsigned char *current;
+		int cmp;
+
+		current = m->chunk_oid_lookup + m->hdr->hash_len * mid;
+		cmp = hashcmp(sha1, current);
+		if (!cmp) {
+			*pos = mid;
+			return 1;
+		}
+		if (cmp > 0) {
+			first = mid + 1;
+			continue;
+		}
+		last = mid;
+	}
+
+	*pos = first;
+	return 0;
+}
+
 int contains_pack(struct midxed_git *m, const char *pack_name)
 {
 	uint32_t first = 0, last = m->num_packs;

index d8ede8121c..5598799189 100644
@@ -101,6 +101,15 @@ extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,
 						     struct midxed_git *m,
 						     uint32_t n);
 
+/*
+ * Perform a binary search on the object list in a MIDX file for the given sha1.
+ *
+ * If the object exists, then return 1 and set *pos to the position of the sha1.
+ * Otherwise, return 0 and set *pos to the position of the lex-first object greater
+ * than the given sha1.
+ */
+extern int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos);
+
 extern int contains_pack(struct midxed_git *m, const char *pack_name);
 
 /*

2.15.0

Create unique_in_midx() to mimic behavior of unique_in_pack().

Create find_abbrev_len_for_midx() to mimic behavior of find_abbrev_len_for_pack().

Consume these methods when interacting with abbreviations.

---
 sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 68 insertions(+), 2 deletions(-)

index 611c7d24dd..2f426e136e 100644
@@ -10,6 +10,7 @@
 #include "dir.h"
 #include "sha1-array.h"
 #include "packfile.h"
+#include "midx.h"
 
 static int get_oid_oneline(const char *, struct object_id *, struct commit_list *);
 

@@ -190,11 +191,40 @@ static void unique_in_pack(struct packed_git *p,
 	}
 }
 
+static void unique_in_midx(struct midxed_git *m,
+			   struct disambiguate_state *ds)
+{
+	uint32_t num, i, first = 0;
+	const struct object_id *current = NULL;
+
+	if (!m->num_objects)
+		return;
+
+	num = m->num_objects;
+	bsearch_midx(m, ds->bin_pfx.hash, &first);
+
+	/*
+	 * At this point, "first" is the location of the lowest object
+	 * with an object name that could match "bin_pfx".  See if we have
+	 * 0, 1 or more objects that actually match(es).
+	 */
+	for (i = first; i < num && !ds->ambiguous; i++) {
+		struct object_id oid;
+		current = nth_midxed_object_oid(&oid, m, i);
+		if (!match_sha(ds->len, ds->bin_pfx.hash, current->hash))
+			break;
+		update_candidates(ds, current);
+	}
+}
+
 static void find_short_packed_object(struct disambiguate_state *ds)
 {
 	struct packed_git *p;
+	struct midxed_git *m;
 
-	prepare_packed_git();
+	prepare_packed_git_internal(1);
+	for (m = midxed_git; m && !ds->ambiguous; m = m->next)
+		unique_in_midx(m, ds);
 	for (p = packed_git; p && !ds->ambiguous; p = p->next)
 		unique_in_pack(p, ds);
 }

@@ -508,6 +538,39 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 	return 0;
 }
 
+static void find_abbrev_len_for_midx(struct midxed_git *m,
+				     struct min_abbrev_data *mad)
+{
+	int match = 0;
+	uint32_t first = 0;
+	struct object_id oid;
+
+	if (!m->num_objects)
+		return;
+
+	match = bsearch_midx(m, mad->hash, &first);
+
+	/*
+	 * first is now the position in the packfile where we would insert
+	 * mad->hash if it does not exist (or the position of mad->hash if
+	 * it does exist). Hence, we consider a maximum of three objects
+	 * nearby for the abbreviation length.
+	 */
+	mad->init_len = 0;
+	if (!match) {
+		nth_midxed_object_oid(&oid, m, first);
+		extend_abbrev_len(&oid, mad);
+	} else if (first < m->num_objects - 1) {
+		nth_midxed_object_oid(&oid, m, first + 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	if (first > 0) {
+		nth_midxed_object_oid(&oid, m, first - 1);
+		extend_abbrev_len(&oid, mad);
+	}
+	mad->init_len = mad->cur_len;
+}
+
 static void find_abbrev_len_for_pack(struct packed_git *p,
 				     struct min_abbrev_data *mad)
 {

@@ -563,8 +626,11 @@ static void find_abbrev_len_for_pack(struct packed_git *p,
 static void find_abbrev_len_packed(struct min_abbrev_data *mad)
 {
 	struct packed_git *p;
+	struct midxed_git *m;
 
-	prepare_packed_git();
+	prepare_packed_git_internal(1);
+	for (m = midxed_git; m; m = m->next)
+		find_abbrev_len_for_midx(m, mad);
 	for (p = packed_git; p; p = p->next)
 		find_abbrev_len_for_pack(p, mad);
 }

2.15.0

When looking for a packed object, first check the MIDX for that object. This reduces thrashing in the MRU list of packfiles.

---
 midx.c     | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 midx.h     |  3 +++
 packfile.c |  5 +++-
 3 files changed, 91 insertions(+), 1 deletion(-)

index 8c643caa92..4b2398b3ee 100644
@@ -329,6 +329,90 @@ int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos)
 	return 0;
 }
 
+static int prepare_midx_pack(struct midxed_git *m, uint32_t pack_int_id)
+{
+	struct strbuf pack_name = STRBUF_INIT;
+
+	if (pack_int_id >= m->hdr->num_packs)
+		return 1;
+
+	if (m->packs[pack_int_id])
+		return 0;
+
+	strbuf_addstr(&pack_name, m->pack_dir);
+	strbuf_addstr(&pack_name, "/");
+	strbuf_addstr(&pack_name, m->pack_names[pack_int_id]);
+	strbuf_strip_suffix(&pack_name, ".pack");
+	strbuf_addstr(&pack_name, ".idx");
+
+	m->packs[pack_int_id] = add_packed_git(pack_name.buf, pack_name.len, 1);
+	strbuf_release(&pack_name);
+	return !m->packs[pack_int_id];
+}
+
+static int find_pack_entry_midx(const unsigned char *sha1,
+				struct midxed_git *m,
+				struct packed_git **p,
+				off_t *offset)
+{
+	uint32_t pos;
+	struct pack_midx_details d;
+
+	if (!bsearch_midx(m, sha1, &pos) ||
+	    !nth_midxed_object_details(m, pos, &d))
+		return 0;
+
+	if (d.pack_int_id >= m->num_packs)
+		die(_("bad pack-int-id %d"), d.pack_int_id);
+
+	/* load packfile, if necessary */
+	if (prepare_midx_pack(m, d.pack_int_id))
+		return 0;
+
+	*p = m->packs[d.pack_int_id];
+	*offset = d.offset;
+
+	return 1;
+}
+
+int fill_pack_entry_midx(const unsigned char *sha1,
+			 struct pack_entry *e)
+{
+	struct packed_git *p;
+	struct midxed_git *m;
+
+	if (!core_midx)
+		return 0;
+
+	m = midxed_git;
+	while (m)
+	{
+		off_t offset;
+		if (!find_pack_entry_midx(sha1, m, &p, &offset)) {
+			m = m->next;
+			continue;
+		}
+
+		/*
+		* We are about to tell the caller where they can locate the
+		* requested object.  We better make sure the packfile is
+		* still here and can be accessed before supplying that
+		* answer, as it may have been deleted since the MIDX was
+		* loaded!
+		*/
+		if (!is_pack_valid(p))
+			return 0;
+
+		e->offset = offset;
+		e->p = p;
+		hashcpy(e->sha1, sha1);
+
+		return 1;
+	}
+
+	return 0;
+}
+
 int contains_pack(struct midxed_git *m, const char *pack_name)
 {
 	uint32_t first = 0, last = m->num_packs;

index 5598799189..b7e8b15fe4 100644
@@ -11,6 +11,9 @@ extern char *get_midx_head_filename(const char *pack_dir);
 
 extern struct object_id *get_midx_head_oid(const char *pack_dir, struct object_id *oid);
 
+extern int fill_pack_entry_midx(const unsigned char *sha1,
+				struct pack_entry *e);
+
 struct pack_midx_entry {
 	struct object_id oid;
 	uint32_t pack_int_id;

index 866a1f30dd..9ec39a83e9 100644
@@ -1883,7 +1883,10 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 {
 	struct mru_entry *p;
 
-	prepare_packed_git();
+	prepare_packed_git_internal(1);
+	if (fill_pack_entry_midx(sha1, e))
+		return 1;
+
 	if (!packed_git)
 		return 0;
 

2.15.0

On Sun, Jan 07 2018, Derrick Stolee jotted:

(Not a critique of this, just a (stupid) question)

What's the practical use-case for this feature? Since it doesn't help with --abbrev=40 the speedup is all in the part that ensures we don't show an ambiguous SHA-1.

The reason we do that at all is because it makes for a prettier UI.

Are there things that both want the pretty SHA-1 and also care about the throughput? I'd have expected machine parsing to just use --no-abbrev-commit.

If something cares about both throughput and e.g. is saving the abbreviated SHA-1s isn't it better off picking some arbitrary size (e.g. --abbrev=20), after all the default abbreviation is going to show something as small as possible, which may soon become ambigous after the next commit.

The point of including the --abbrev=40 is to point out that object lookups do not get slower with the MIDX feature. Using these "git log" options is a good way to balance object lookups and abbreviations with object parsing and diff machinery. And while the public data shape I shared did not show a difference, our private testing of the Windows repository did show a valuable improvement when isolating to object lookups and ignoring abbreviation calculations.

We tried setting core.abbrev=40 on GVFS enlistments to speed up performance and the users rebelled against the hideous output. They would rather have slower speeds than long hashes.

The --raw flag outputs blob hashes, so the --abbrev=40 covers all hashes.

Unfortunately, with the way the abbreviation algorithms work, using --abbrev=20 will have similar performance problems because you still need to inspect all packfiles to ensure there isn't a collision in the first 20 hex characters.

Thanks,
-Stolee

Just to make sure I'm parsing this correctly: normal lookups do get faster when you have a single index, given the right setup?

I'm curious what that setup looked like. Is it just tons and tons of packs? Is it ones where the packs do not follow the mru patterns very well?

I think it's worth thinking a bit about, because...

...if what we primarily care about speeding up is abbreviations, is it crazy to consider disabling the disambiguation step entirely?

The results of find_unique_abbrev are already a bit of a probability game. They're guaranteed at the moment of generation, but as more objects are added, ambiguities may be introduced. Likewise, what's unambiguous for you may not be for somebody else you're communicating with, if they have their own clone.

Since we now scale the default abbreviation with the size of the repo, that gives us a bounded and pretty reasonable probability that we won't hit a collision at all[1].

I.e., what if we did something like this:

index 611c7d24dd..04c661ba85 100644
@@ -600,6 +600,15 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)
 	if (len == GIT_SHA1_HEXSZ || !len)
 		return GIT_SHA1_HEXSZ;
 
+	/*
+	 * A default length of 10 implies a repository big enough that it's
+	 * getting expensive to double check the ambiguity of each object,
+	 * and the chance that any particular object of interest has a
+	 * collision is low.
+	 */
+	if (len >= 10)
+		return len;
+
 	mad.init_len = len;
 	mad.cur_len = len;
 	mad.hex = hex;

If I repack my linux.git with "--max-pack-size=64m", I get 67 packs. The patch above drops "git log --oneline --raw" on the resulting repo from ~150s to ~30s.

With a single pack, it goes from ~33s ~29s. Less impressive, but there's still some benefit.

There may be other reasons to want MIDX or something like it, but I just wonder if we can do this much simpler thing to cover the abbreviation case. I guess the question is whether somebody is going to be annoyed in the off chance that they hit a collision.

-Peff

[1] I'd have to check the numbers, but IIRC we've set the scaling so that the chance of having a _single_ collision in the repository is less than 50%, and rounding to the conservative side (since each hex char gives us 4 bits). And indeed, "git log --oneline --raw" on linux.git does not seem to have any collisions at its default of 12 characters, at least in my clone.

We could also consider switching core.disambiguate to "commit", which makes even a collision less likely to annoy the user.

On Mon, Jan 08 2018, Jeff King jotted:

	if (len >= 10) {
		int extra = 2; /* or  just 1? or maybe 0 ... */
		hex[len + extra] = 0;
		return len + extra;
	}

    git log --pretty=format:%h --abbrev=7 | perl -nE 'chomp; say length'|sort|uniq -c|sort -nr

     952858 7
      44541 8
       2861 9
        168 10
         17 11
          2 12

Hi Peff,

Not crazy. But it would break stuff. Because...

... this is only a probability game in the long term, when you consider new objects to enter from *somewhere*.

But in purely local settings, when we expect no new objects to be introduced, we do use known-unambiguous abbreviations.

Take the interactive rebase for example. It generates todo lists with abbreviated commit names, for readability (and it is *really* important to keep this readable). As we expect new objects to be introduced by the interactive rebase, we convert that todo list to unabbreviated commit names before executing the interactive rebase.

Your idea (to not care about unambiguous abbreviations) would break that.

Ciao,
Dscho

I think that could be easily worked around for rebase by asking git to check ambiguity during the conversion. Speed is much less of a problem there, because we're doing a relatively small number of abbreviations (compared to "git log --oneline --raw", which is abbreviating almost every object in the repository).

But I agree it's a potential problem for other scripts that we might not have control over. I hadn't really intended this to be the default behavior (my patch was just trying to show the direction). But it does make for a pretty awful interface if callers have to opt into it manually ("git log --oneline --no-really-go-fast").

I am a bit curious if there's a bounded probability that people would find acceptable for Git to give an ambiguous abbreviation. We already accept 1 in 2^160, of course. But would, e.g., one in a million be OK?

-Peff

Hi Peff,

Sure.

It also points to a flaw in your reasoning, and you should take my example
further: previously, we guaranteed unique abbreviations, and who is to say that there is no script out there relying on that guarantee? You?

Exactly.

What is that going to solve?

I think a better alternative would be to introduce a new abbreviation mode that is *intended* to stop caring about unique abbreviations.

In web interfaces, for example, it makes tons of sense to show, say, 8 digits in link texts and have the full name in the actual link URL.

Currently, we have no way to tell Git: look, I want to have a short label for this, but I do not really care that this is unambiguous, I just want something to talk about.

(And you are correct, of course, that the uniqueness of abbreviations will no longer be guaranteed for partial clones, and it is already not guaranteed for shallow clones, and it will only be possible to guarantee this, ever, for one particular repository at a particular time.)

I am just hesitant to change things that would break existing setups.

Just to throw this out there: --abbrev=8! would be one possible convention to state "I want exactly 8 hex digits, don't bother checking for uniqueness".

Not sure how urgent such a feature is.

Ciao,
Dscho

You seem to have spent some time on rebase, including lamenting on the in-expressiveness of the instruction sheet (c.f. "rebase a mergy history sucks")

And in that light, I'd like to propose a new naming scheme:

(a) assume that we "tag" HEAD at the start of the rebase
(b) any abbreviation must be given as committish anchored to said ref:

pick REBASE_HEAD~1 commit subject
pick REBASE_HEAD~2 distak the gostim
pick REBASE_HEAD~3 Document foo
pick REBASE_HEAD~4 Testing the star-gazer

And as we have the full descriptiveness of the committishs there, each commit can be described in a unique way using the graph relationship. I am just throwing the name REBASE_HEAD out there to trigger some associations ("similar to FETCH_HEAD"), but I dislike the name.

(c) this would not solve the problem of mergy history, yet. For that we'd need to introduce more keywords, that allow us to move around in the DAG, such that we can reset to a specific revision or name revisions on the fly. So maybe all we need is "reset", "name" (== short lived tag), "merge" (rewrite parents of HEAD) to be expressive enough, but still keep the line oriented interface?

Stefan

It is correct to say that (c) is an issue that is not solved by (b), but with the current scheme, the commits are internally referenced by full object names, and just before it is presented to the end users, these names are abbreviated down to unique prefix. The machinery expands these abbreviated names back to the full names before going forward, so it is not an issue that we are creating new commits during the rebase.

Does it make it easier to read if we used ~$n notation based on a fixed point, instead of shortened unique object names? What improvement is (b) trying to achieve?

And that is what (b) would solve, as it is shorter than the full hash and yet exact.

(c) was mostly speculation on top of (b) if we can take it any further.

I still do not get it, even though I fully agree that in Web UI what Dscho envisions makes tons of sense. Use some short handle that does not need to be unique inside repository to display, but have a full information that can be used by machines. The shortened ones need to be unique _within_ a given todo list, to be displayed as text to be "clicked", where the A element's href attribute that surrounds that "clickable" text has fully unambiguous information.

And that fully unambiguous information, because it is for machine consumption, can be a full object name without any shortening.

I do not see a need for REBASE_HEAD~$n to make it less robust (i.e. we now need to worry about making sure it is not lost or moved while we need it and clean it up when we are done, etc.)

Hi Stefan,

Let's call it "todo list" again?

And yes, I spend a *lot* of time in rebase. It's part of my duties as Git for Windows maintainer.

I do not necessarily agree that this is better because it is valid only locally, only in the current rebase (and you enter new problems because you implicitly require REBASE_HEAD to be worktree-local lest you prevent simultaneous rebases in related worktrees).

That prevents you from, say, chatting to your colleague and mentioning that commit that you are uncertain about. Imagine asking "Hey Todd, do you know what REBASE_HEAD~2 is all about?". Granted, if you ask about "deadbeef" and it just so happens that this shortened name is ambiguous in Todd's repository. But that is pretty unlikely, isn't it?

Not only that. It would also be confusing to read after reordering...

You probably missed my hint that I have a working solution for that. Please have a look at

	https://github.com/git/git/pull/447

Short version: for a commit topology like this:

	A - B - C
	  \   /
	    D

the generated list would look like this:

	# branch D
	pick 0123 A
	label branch-point
	pick 1234 D
	label D

	reset branch-point
	pick 2345 B
	merge 3456 D C

Ciao,
Dscho

I'm not sure what you think my reasoning was, since I made the same point directly after. ;)

I'm not sure I understand your question. We can bound the probability of a collision by increasing the size of the abbreviation. My question was whether there is a size where that tradeoff makes sense. So it "solves" the problem of worrying about collisions.

I'm not sure if that would be useful option or not. I certainly agree that static abbreviations are a useful thing to want. But for scripted callers, it's usually easy to cut down the abbreviation yourself. I think your web interface example is a good one. The caller will ask Git for the full 40-hex hash, and then cut it down itself when generating the link (and I just so happen to have worked on a web interface that does this[1]).

So would it be useful for humans to use? That's what I'm not sure about. It seems cumbersome to have to add "--abbrev=8!" on the command line to each invocation. But if it were triggered by config, it seems like we would risk breaking scripts.

Me too. I'm not sure if I'm seriously advocating the "bound the probability" thing. It's just something I think is worth pondering a little.

-Peff

[1] Actually, there _is_ something that it's useful for Git to tell the caller, which is the approximate number of objects in the repository. Eight digits is not enough for the kernel, for example, and these days we use 12 digits by default. I'm not sure if such a web interface would rather ask for "%H %h" and generate the link text from the second half, or it would rather just get a ballpark on the number of objects, and do the simple abbreviation math itself (right now GitHub does not do either; I don't know about other interfaces).

The way I repacked the Linux repo creates an artificially good set of packs for the MRU cache. When the packfiles are partitioned instead by the time the objects were pushed to a remote, the MRU cache performs poorly. Improving these object lookups are a primary reason for the MIDX feature, and almost all commands improve because of it. 'git log' is just the simplest to use for demonstration.

No only are users going to be annoyed when they hit collisions after copy-pasting an abbreviated hash, there are also a large number of tools that people build that use abbreviated hashes (either for presenting to users or because they didn't turn off abbreviations).

Abbreviations cause performance issues in other commands, too (like 'fetch'!), so whatever short-circuit you put in, it would need to be global. A flag on one builtin would not suffice.

Interesting.

The idea of the pack mru (and the "last pack looked in" before it) is that there would be good locality for time-segmented packs (like those generated by pushes), since most operations also tend to visit history in chronological-ish order (e.g., log). Tree-wide operations would be an exception there, though, since files would have many ages across the tree (though in practice, one would hope that pretty-ancient history would eventually be replaced in a modern tree).

I've often wondered, though, if the mru (and "last pack") work mainly because the "normal" distribution for a repository is to have one big pack with most of history, and then a couple of smaller ones (what hasn't been packed yet). Even something as naive as "look in the last pack" works there, because it turns into "look in the biggest pack". If it has most of the objects, it's the most likely place for the previous and the next objects to be.

But from my understanding of how you handle the Windows repository, you have tons of equal-sized packs that are never coalesced. Which is quite a different pattern.

I would expect your "--max-pack-size" thing to end up with something roughly segmented like pushes, though, just because we do order the write phase in reverse chronological order. Well, mostly. We do each object type in its own chunks, and there's some reordering based on deltas. So given the sizes, it's likely that most of your trees all end up in a few packs.

Yeah, I agree it's potentially problematic for a lot of reasons. I was just hoping we could bound the probabilities in a way that is acceptable. Maybe it's a fool's errand.

-Peff

On Mon, Jan 08 2018, Derrick Stolee jotted:

I meant (but forgot to write) that this would be some new mode, e.g. --abbrev=20 --no-abbrev-check which would just perform a substr() of the 40 character SHA-1. It might be interesting to add that for reasons completely unrelated to your series.

Thanks for answering the rest.

[snip]

Replying to this old thread since I see you're prepearing the MIDX for submission again and this seemed like the best venue.

Your WIP branch (github.com/git/derrickstolee/midx/upstream) still only references the speedups in abbreviation calculations, but here you allude to other improvements. It would be very nice to have some summary of that in docs / commit messages when you submit this.

I've been meaning to get around to submitting something like I mentioned in https://public-inbox.org/git/[email protected]/
i.e. a way to expand the abbrev mode to not check disambiguations, which would look something like:

core.abbrev = 20
core.validateAbbrev = false

Or:

core.abbrev = +2
core.validateAbbrev = false

So, using the example from the above referenced E-Mail +2 would make linux.git emit hashes of 14 characters, without any abbreviation checking (just trusting in statistics to work in your favor).

As noted by JS in this thread that wouldn't be acceptable for your use-case, but there's plenty of people (including me) who'd appreciate the speedup without being a 100% sure we're emitting unambiguous hashes, since that trade-off is better than time spent generating another index on-disk. So I see it as a complimentary & orthogonal feature.

But with that implemented I wouldn't get any benefit from things that use the MIDX that aren't abbreviations, so what are those?

I won't have time to finish this today, but it's already in a shape that I think is useful for discussion to see what others think.

I still need to make this be supported by --abbrev=* and have e.g. --abbrev=+2 work. I got as far as this with that:

    diff --git a/parse-options-cb.c b/parse-options-cb.c
    index 0f9f311a7a..7cc9d3dfe6 100644
    --- a/parse-options-cb.c
    +++ b/parse-options-cb.c
    @@ -16,13 +16,23 @@ int parse_opt_abbrev_cb(const struct option *opt, const char *arg, int unset)
     	if (!arg) {
     		v = unset ? 0 : DEFAULT_ABBREV;
     	} else {
    +		const char *origarg = arg;
     		v = strtol(arg, (char **)&arg, 10);
     		if (*arg)
     			return opterror(opt, "expects a numerical value", 0);
    -		if (v && v < MINIMUM_ABBREV)
    +		if (*origarg == '+' || *origarg == '-') {
    +			if (v == 0) {
    +				return opterror(opt, "relative abbrev must be non-zero", 0);
    +			} else {
    +				default_abbrev_relative = v;
    +				v = -1;
    +			}
    +		} else if (v && v < MINIMUM_ABBREV) {
     			v = MINIMUM_ABBREV;
    -		else if (v > 40)
    +		} else if (v > 40) {
     			v = 40;
    +		}
     	}
     	*(int *)(opt->value) = v;
     	return 0;

But e.g. blame would print 40 character SHA-1s on +2, I didn't have time to dig into why.

This'll also need tests, I haven't added any yet, and finally it's probably a good idea to split off the core.abbrev=[+-]NUM feature into a seperate patch from core.validateAbbrev, although with my 2/2 the two can be used in isolation, or together.

Ævar Arnfjörð Bjarmason (2):
config.c: use braces on multiple conditional arms
sha1-name: add core.validateAbbrev & relative core.abbrev

 Documentation/config.txt | 46 ++++++++++++++++++++++++++++++++++++++++
 cache.h                  |  2 ++
 config.c                 | 18 ++++++++++++++--
 environment.c            |  2 ++
 sha1-name.c              | 15 +++++++++++++
 5 files changed, 81 insertions(+), 2 deletions(-)

2.17.0.290.gded63e768a

Adjust this code that'll be modified in a subsequent change per the CodingGuidelines.

---
 config.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index fbbf0f8e9f..12f762ad92 100644
@@ -1149,9 +1149,9 @@ static int git_default_core_config(const char *var, const char *value)
 	if (!strcmp(var, "core.abbrev")) {
 		if (!value)
 			return config_error_nonbool(var);
-		if (!strcasecmp(value, "auto"))
+		if (!strcasecmp(value, "auto")) {
 			default_abbrev = -1;
-		else {
+		} else {
 			int abbrev = git_config_int(var, value);
 			if (abbrev < minimum_abbrev || abbrev > 40)
 				return error("abbrev length out of range: %d", abbrev);

2.17.0.290.gded63e768a

Since Linus added auto-sizing for abbreviations in e6c587c733 ("abbrev: auto size the default abbreviation", 2016-09-30) we've been less likely to produce a short SHA-1 today that'll collide on the same repository tomorrow, since before we'd always pick the bare minimum we could get away with.

But we still do a full disambiguation check, which can be very expensive in some cases. There's a work-in-progress MIDX implementation to address that[1].

This change adds an alternate method of achieving some of the same ends (but possibly not all, see [2] and replies to the original thread at [1]).

Now, as described in the docs the user can set a relative abbreviation length via core.abbrev, e.g. on linux.git core.abbrev=+2 will produce SHA-1s that are 14 characters (as opposed to the implicit 12).

This in combination with core.validateAbbrev=false (off by default) allows for picking a trade-off between performance, and the odds that future or remote (or current and local) short SHA-1 will be ambiguous.

1. https://public-inbox.org/git/[email protected]/
2. https://public-inbox.org/git/[email protected]/

---
 Documentation/config.txt | 46 ++++++++++++++++++++++++++++++++++++++++
 cache.h                  |  2 ++
 config.c                 | 14 ++++++++++++
 environment.c            |  2 ++
 sha1-name.c              | 15 +++++++++++++
 5 files changed, 79 insertions(+)

index ab641bf5a9..8624110818 100644
@@ -919,6 +919,52 @@ core.abbrev::
 	in your repository, which hopefully is enough for
 	abbreviated object names to stay unique for some time.
 	The minimum length is 4.
++
+This can also be set to relative values such as `+2` or `-2`, which
+means to add or subtract N characters from the SHA-1 that Git would
+otherwise print. This is useful in combination with the
+`core.validateAbbrev` setting, or to get more future-proof hashes to
+reference in the future in a repository whose number of objects is
+expected to grow.
+
+core.validateAbbrev::
+	If set to false (true by default) don't do any validation when
+	printing abbreviated object names to see if they're really
+	unique. This makes printing objects more performant at the
+	cost of potentially printing object names that aren't unique
+	within the current repository.
++
+When printing abbreviated object names Git needs to look through the
+local object store. This is an `O(log N)` operation assuming all the
+objects are in a single pack file, but `X * O(log N)` given `X` pack
+files, which can get expensive on some larger repositories.
++
+This setting changes that to `O(1)`, but with the trade-off that
+depending on the value of `core.abbrev` way may be printing
+abbreviated hashes that collide. Too see how likely this is, try
+running:
++
+-----------------------------------------------------------------------------------------------------------
+git log --all --pretty=format:%h --abbrev=4 | perl -nE 'chomp; say length' | sort | uniq -c | sort -nr
+-----------------------------------------------------------------------------------------------------------
++
+This shows how many commits were found at each abbreviation length. On
+linux.git in June 2018 this shows a bit more than 750,000 commits,
+with just 4 needing 11 characters to be fully abbreviated, and the
+default heuristic picks a length of 12.
++
+Even without `core.validateAbbrev=false` the results abbreviation
+already a bit of a probability game. They're guaranteed at the moment
+of generation, but as more objects are added, ambiguities may be
+introduced. Likewise, what's unambiguous for you may not be for
+somebody else you're communicating with, if they have their own clone.
++
+Therefore the default of `core.validateAbbrev=true` may not save you
+in practice if you're sharing the SHA-1 or noting it now to use after
+a `git fetch`. You may be better off setting `core.abbrev` to
+e.g. `+2` to add 2 extra characters to the SHA-1 in combination with
+`core.validateAbbrev=false` to get a reasonable trade-off between
+safety and performance.
 
 add.ignoreErrors::
 add.ignore-errors (deprecated)::

index 89a107a7f7..6dc5af9482 100644
@@ -772,6 +772,8 @@ extern int check_stat;
 extern int quote_path_fully;
 extern int has_symlinks;
 extern int minimum_abbrev, default_abbrev;
+extern int default_abbrev_relative;
+extern int validate_abbrev;
 extern int ignore_case;
 extern int assume_unchanged;
 extern int prefer_symlink_refs;

index 12f762ad92..b6e0d17af1 100644
@@ -1146,11 +1146,25 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.validateabbrev")) {
+		if (!value)
+			return config_error_nonbool(var);
+		validate_abbrev =  git_config_bool(var, value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.abbrev")) {
 		if (!value)
 			return config_error_nonbool(var);
 		if (!strcasecmp(value, "auto")) {
 			default_abbrev = -1;
+		} else if (*value == '+' || *value == '-') {
+			int relative = git_config_int(var, value);
+			if (relative == 0)
+				die(_("bad core.abbrev value %s. "
+				      "relative values must be non-zero"),
+				    value);
+			default_abbrev_relative = relative;
 		} else {
 			int abbrev = git_config_int(var, value);
 			if (abbrev < minimum_abbrev || abbrev > 40)

index 2a6de2330b..4a24d8126b 100644
@@ -22,6 +22,8 @@ int trust_ctime = 1;
 int check_stat = 1;
 int has_symlinks = 1;
 int minimum_abbrev = 4, default_abbrev = -1;
+int default_abbrev_relative = 0;
+int validate_abbrev = 1;
 int ignore_case;
 int assume_unchanged;
 int prefer_symlink_refs;

index 60d9ef3c7e..aa7ccea14d 100644
@@ -576,6 +576,7 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)
 	struct disambiguate_state ds;
 	struct min_abbrev_data mad;
 	struct object_id oid_ret;
+	int dar = default_abbrev_relative;
 	if (len < 0) {
 		unsigned long count = approximate_object_count();
 		/*

@@ -602,6 +603,20 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)
 	if (len == GIT_SHA1_HEXSZ || !len)
 		return GIT_SHA1_HEXSZ;
 
+	if (dar) {
+		if (len + dar < MINIMUM_ABBREV) {
+			len = MINIMUM_ABBREV;
+			dar = 0;
+		}
+
+		if (validate_abbrev) {
+			len += dar;
+		} else {
+			hex[len + dar] = 0;
+			return len + dar;
+		}
+	}
+
 	mad.init_len = len;
 	mad.cur_len = len;
 	mad.hex = hex;

2.17.0.290.gded63e768a

s/Too see/To see/

[...]

You're really good at tracking new commits in my GitHub page ;)

The new version is essentially a complete rewrite of the feature, since we learned a lot about how to add a new data store from the commit-graph series. The design document [1] refers to some of the immediate benefits and future benefits. Some of these future benefits were discussed at the contributor's summit [2].

[1] https://github.com/derrickstolee/git/blob/midx/upstream/Documentation/technical/midx.txt

[2] https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/
    Git Merge 2018 Contributor's summit notes (includes discussion of MIDX)

The MIDX is built for handling many packfiles. As opposed to the commit-graph feature, your repo needs to be _really_big_ to need the MIDX. Most just repack into one packfile on a regular basis.

One case for vanilla Git: we've heard from lots of customers disabling gc.auto in their build machines because they didn't want to wait for a repack/gc after a fetch and before a build. Then, they end up in a many-pack situation because they never scheduled time for that repack/gc.

For GVFS, we virtualize the repo, so objects can be downloaded from the server on-demand. Since round-trips to the server are expensive, we have the notion of a "prefetch pack". Our cache servers precompute packfiles containing all of the commits and trees introduced to the server that day. On a 'git fetch' command, GVFS intercepts via a hook and downloads the list of daily prefetch packs since the last prefetch. These are placed in an alternate (the "shared object cache"), so multiple enlistments can point to the same, fixed list of packs. The cache servers fold these packs together after 30 days, so users on a fresh clone start with 31 packs and users who go on vacation for a month get at most 31 packs in a single download.

The performance gains from the MIDX for abbrevations are the easiest to demonstrate. It's not hard to see why the single binary search to find the two closest OIDs is better than iterating through all of the packfiles and running a binary search on each.

The other thing that the MIDX does right now is be a single source for object lookups. This is harder to demonstrate the benefit in Git on its own, because using git repack -adfF --max-pack-size=128m repacks in a "good" way. This repack actually makes the MRU packfile list really effective.

One reason the MIDX is important for object lookups in the GVFS case is two-fold:

1. The time-based organization of the prefetch packs makes the trees necessary for a 'checkout' spread across many packfiles. Even with the working directory virtualization, every 'checkout' needs to recompute the .git/index, and that requires walking lots of trees.

2. When we are looking for a blob that is not in the local cache, we need to check that the blob is on-disk before requesting it from the server. In a many-pack scenario, those object misses are as expensive as the abbreviation case. This may affect partial clone, so I'll talk with Jeff H about that situation.

I expect to send my v1 today. I'm just trying to create a synthetic environment that demonstrates this benefit to object lookups using the Linux repository.

Thanks,
-Stolee

...

My interest in this feature would be to speed up fetches when there is more than one large pack-file with many of the
same objects that are in other pack-files. What does your
MIDX design do when it encounters multiple copies of the same object in different pack files? Does it index them all, or does it keep a single copy?

In our Gerrit instance (Gerrit uses jgit), we have multiple copies of the linux kernel repos linked together via the alternatives file mechanism. These repos have many different references (mostly Gerrit change references), but they share most of the common objects from the mainline. I have found that during a large fetch such as a clone, jgit spends a significant amount of extra time by having the extra large pack-files from the other repos visible to it, usually around an extra minute per instance of these (without them, the clone takes around 7mins). This adds up easily with a few repos extra repos, it can almost double the time.

My investigations have shown that this is due to jgit searching each of these pack files to decide which version of each object to send. I don't fully understand its selection criteria, however if I shortcut it to just pick the first copy of an object that it finds, I regain my lost time. I don't know if git suffers from a similar problem? If git doesn't suffer from this then it likely just uses the first copy of an object it finds (which may not be the best object to send?)

It would be nice if this use case could be improved with MIDX. To do so, it seems that it would either require that MIDX either only put "the best" version of an object (i.e. pre-select which one to use), or include the extra information to help make the selection process of which copy to use (perhaps based on the operation being performed) fast.

This also leads me to ask, what other additional information (bitmaps?) for other operations, besides object location, might suddenly be valuable in an index that potentially points to multiple copies of objects? Would such information be appropriate in MIDX, or would it be better in another index?

Thanks,

-Martin

The Qualcomm Innovation Center, Inc. is a member of Code 
Aurora Forum, hosted by The Linux Foundation

The MIDX currently keeps only one reference to each object. Duplicates are dropped during writing. (See the care taken in commit 04/18 to avoid duplicates.) Since midx_sha1_compare() does not use anything other than the OID to order the objects, there is no decision being made about which pack is "better". The MIDX writes the first copy it finds and discards the others.

It would not be difficult to include a check in midx_sha1_compare() to favor one packfile over another based on some measurement (size? mtime?). Since this would be a heuristic at best, I left it out of the current patch.

GVFS also uses alternates for sharing packfiles across multiple copies of the repo. The MIDX is designed to cover all packfiles in the same directory, but is not designed to cover packfiles in multiple alternates; currently, each alternate would need its own MIDX file. Does that cause issues with your setup?

I'm not sure if there is sufficient value in storing multiple references to the same object stored in multiple packfiles. There could be value in carefully deciding which copy is "best" during the MIDX write, but during read is not a good time to make such a decision. It also increases the size of the file to store multiple copies.

For applications to bitmaps, it is probably best that we only include one copy of each object. Otherwise, we need to include extra bits in the bitmaps for those copies (when asking "is this object in the bitmap?").

Thanks for the context with Gerrit's duplicate object problem. I'll try to incorporate it in to the design document (commit 01/18) for the v1 patch.

Thanks,
-Stolee

This would likely speed things up then, even if the chosen objects are suboptimal.

Yeah, I didn't know what heuristic to use either, I tended to think that the bigger pack-file would be valuable because it is more likely to share deltas with other objects in that pack, so more easy to send them. However, that is likely only true during clones or other large fetches when we want most objects. During small "update" fetches, the newer packs might be better?

I also thought that objects in alternates should be considered less valuable for my use case, however in the github fork use case, the alternates might be more valuable?

So yes heuristics, and I don't know what is best. Perhaps some config options could be used to set heuristics like this. Whatever the heuristics are, since they would be a part of the MIDX packing process it would be easy to change. This assumes that keeping only one copy in the index is the right thing. The question would be, what if we need different heuristics for different operations? Would it make sense to have multiple MIDX files covering the same packs then, one for fetch, one for merge...?

No, since the other large packfiles are all in other repos (alternates). Is there a reason the MIDX would not want to cover the alternates? If you don't then you would seemingly loose any benefits of the MIDX when you have alternates in use.

...

Yes, I am not sure either, it would be good to have input from experts here.

Agreed. Would the MIDX potentially pave the way to create multi-pack bitmaps?

FYI, this is not a typical Gerrit thing, it is something special we do in our installation.

Thanks for your thoughts,

-Martin

The Qualcomm Innovation Center, Inc. is a member of Code 
Aurora Forum, hosted by The Linux Foundation