{"thread":{"id":"47560","subject":"[RFC PATCH 00/18] Multi-pack index (MIDX)","startedAt":"2018-01-07T18:15:11Z","lastAt":"2018-06-06T12:05:03Z","messageCount":48,"participants":["Derrick Stolee","Ævar Arnfjörð Bjarmason","Jeff King","Johannes Schindelin","Jonathan Tan","Stefan Beller","Junio C Hamano","Martin Fick","Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":18},"messages":[{"id":"336087","messageId":"20180107181459.222909-1-dstolee@microsoft.com","threadId":"47560","inReplyTo":null,"subject":"[RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:41Z","receivedAt":"2018-01-07T18:15:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This RFC includes a new way to index the objects in multiple packs\nusing one file, called the multi-pack index (MIDX).\n\nThe commits are split into parts as follows:\n\n[01] - A full design document.\n\n[02] - The full file format for MIDX files.\n\n[03] - Creation of core.midx config setting.\n\n[04-12] - Creation of \"midx\" builtin that writes, reads, and deletes\n MIDX files.\n\n[13-18] - Consume MIDX files for abbreviations and object loads.\n\nThe main goals of this RFC are:\n\n* Determine interest in this feature.\n\n* Find other use cases for the MIDX feature.\n\n* Design a proper command-line interface for constructing and checking\n MIDX files. The current \"midx\" builtin is probably inadequate.\n\n* Determine what additional changes are needed before the feature can\n be merged. Specifically, I'm interested in the interactions with\n repack and fsck. The current patch also does not update the MIDX on\n a fetch (which adds a packfile) but would be valuable. Whenever\n possible, I tried to leave out features that could be added in a\n later patch.\n\n* Consider splitting this patch into multiple patches, such as:\n\n i. The MIDX design document.\n ii. The command-line interface for building and reading MIDX files.\n iii. Integrations with abbreviations and object lookups.\n\nPlease do not send any style nits to this patch, as I expect the code to\nchange dramatically before we consider merging.\n\nI created three copies of the Linux repo with 1, 24, and 127 packfiles\neach using 'git repack -adfF --max-pack-size=[64m|16m]'. These copies\ngave significant performance improvements on the following comand:\n\n git log --oneline --raw --parents\n\nNum Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n----------+-------------+------------+--------+----------\n 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n\nThe last column is the relative difference between the MIDX-enabled repo\nand the single-pack repo. The goal of the MIDX feature is to present the\nODB as if it was fully repacked, so there is still room for improvement.\n\nChanging the command to\n\n git log --oneline --raw --parents --abbrev=40\n\nhas no observable difference (sub 1% change in all cases). This is likely\ndue to the repack I used putting commits and trees in a small number of\npackfiles so the MRU cache workes very well. On more naturally-created\nlists of packfiles, there can be up to 20% improvement on this command.\n\nWe are using a version of this patch with an upcoming release of GVFS.\nThis feature is particularly important in that space since GVFS performs\na \"prefetch\" step that downloads a pack of commits and trees on a daily\nbasis. These packfiles are placed in an alternate that is shared by all\nenlistments. Some users have 150+ packfiles and the MRU misses and\nabbreviation computations are significant. Now, GVFS manages the MIDX file\nafter adding new prefetch packfiles using the following command:\n\n git midx --write --update-head --delete-expired --pack-dir=\n\nAs that release deploys we will gather more specific numbers on the\nperformance improvements and report them in this thread.\n\nDerrick Stolee (18):\n docs: Multi-Pack Index (MIDX) Design Notes\n midx: specify midx file format\n midx: create core.midx config setting\n midx: write multi-pack indexes for an object list\n midx: create midx builtin with --write mode\n midx: add t5318-midx.sh test script\n midx: teach midx --write to update midx-head\n midx: teach git-midx to read midx file details\n midx: find details of nth object in midx\n midx: use existing midx when writing\n midx: teach git-midx to clear midx files\n midx: teach git-midx to delete expired files\n t5318-midx.h: confirm git actions are stable\n midx: load midx files when loading packs\n midx: use midx for approximate object count\n midx: nth_midxed_object_oid() and bsearch_midx()\n sha1_name: use midx for abbreviations\n packfile: use midx for object loads\n\n .gitignore | 1 +\n Documentation/config.txt | 3 +\n Documentation/git-midx.txt | 106 ++++\n Documentation/technical/multi-pack-index.txt | 149 +++++\n Documentation/technical/pack-format.txt | 85 +++\n Makefile | 2 +\n builtin.h | 1 +\n builtin/midx.c | 352 +++++++++++\n cache.h | 1 +\n command-list.txt | 1 +\n config.c | 5 +\n environment.c | 2 +\n git.c | 1 +\n midx.c | 850 +++++++++++++++++++++++++++\n midx.h | 136 +++++\n packfile.c | 79 ++-\n packfile.h | 2 +\n sha1_name.c | 70 ++-\n t/t5318-midx.sh | 189 ++++++\n 19 files changed, 2020 insertions(+), 15 deletions(-)\n create mode 100644 Documentation/git-midx.txt\n create mode 100644 Documentation/technical/multi-pack-index.txt\n create mode 100644 builtin/midx.c\n create mode 100644 midx.c\n create mode 100644 midx.h\n create mode 100755 t/t5318-midx.sh\n\n-- \n2.15.0\n\n"},{"id":"336088","messageId":"20180107181459.222909-2-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:42Z","receivedAt":"2018-01-07T18:15:15Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Commentary: This file format uses the large offsets from the pack-index\nversion 2 format, but drops the CRC32 hashes from that format.\n\nAlso: I included the HASH footer at the end only because it is already in\nthe pack and pack-index formats, but not because it is particularly useful\nhere. If possible, I'd like to remove it and speed up MIDX writes.\n\n-- >8 --\n\nAdd a technical documentation file describing the design\nfor the multi-pack index (MIDX). Includes current limitations\nand future work.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/multi-pack-index.txt | 149 +++++++++++++++++++++++++++\n 1 file changed, 149 insertions(+)\n create mode 100644 Documentation/technical/multi-pack-index.txt\n\ndiff --git a/Documentation/technical/multi-pack-index.txt b/Documentation/technical/multi-pack-index.txt\nnew file mode 100644\nindex 0000000000..d31b03dec5\n--- /dev/null\n+++ b/Documentation/technical/multi-pack-index.txt\n@@ -0,0 +1,149 @@\n+Multi-Pack-Index (MIDX) Design Notes\n+====================================\n+\n+The Git object directory contains a 'pack' directory containing\n+packfiles (with suffix \".pack\") and pack-indexes (with suffix\n+\".idx\"). The pack-indexes provide a way to lookup objects and\n+navigate to their offset within the pack, but these must come\n+in pairs with the packfiles. This pairing depends on the file\n+names, as the pack-index differs only in suffix with its pack-\n+file. While the pack-indexes provide fast lookup per packfile,\n+this performance degrades as the number of packfiles increases,\n+because abbreviations need to inspect every packfile and we are\n+more likely to have a miss on our most-recently-used packfile.\n+For some large repositories, repacking into a single packfile\n+is not feasible due to storage space or excessive repack times.\n+\n+The multi-pack-index (MIDX for short, with suffix \".midx\")\n+stores a list of objects and their offsets into multiple pack-\n+files. It contains:\n+\n+- A list of packfile names.\n+- A sorted list of object IDs.\n+- A list of metadata for the ith object ID including:\n+ - A value j referring to the jth packfile.\n+ - An offset within the jth packfile for the object.\n+- If large offsets are required, we use another list of large\n+ offsets similar to version 2 pack-indexes.\n+\n+Thus, we can provide O(log N) lookup time for any number\n+of packfiles.\n+\n+A new config setting 'core.midx' must be enabled before writing\n+or reading MIDX files.\n+\n+The MIDX files are updated by the 'midx' builtin with the\n+following common parameter combinations:\n+\n+- 'git midx' gives the hash of the current MIDX head.\n+- 'git midx --write --update-head --delete-expired' writes a new\n+ MIDX file, points the MIDX head to that file, and deletes the\n+ existing MIDX file if out-of-date.\n+- 'git midx --read' lists some basic information about the current\n+ MIDX head. Used for basic tests.\n+- 'git midx --clear' deletes the current MIDX head.\n+\n+Design Details\n+--------------\n+\n+- The MIDX file refers only to packfiles in the same directory\n+ as the MIDX file.\n+\n+- A special file, 'midx-head', stores the hash of the latest\n+ MIDX file so we can load the file without performing a dirstat.\n+ This file is especially important with incremental MIDX files,\n+ pointing to the newest file.\n+\n+- If a packfile exists in the pack directory but is not referenced\n+ by the MIDX file, then the packfile is loaded into the packed_git\n+ list and Git can access the objects as usual. This behavior is\n+ necessary since other tools could add packfiles to the pack\n+ directory without notifying Git.\n+\n+- The MIDX file should be only a supplemental structure. If a\n+ user downgrades or disables the `core.midx` config setting,\n+ then the existing .idx and .pack files should be sufficient\n+ to operate correctly.\n+\n+- The file format includes parameters for the object id length\n+ and hash algorithm, so a future change of hash algorithm does\n+ not require a change in format.\n+\n+- If an object appears in multiple packfiles, then only one copy\n+ is stored in the MIDX. This has a possible performance issue:\n+ If an object appears as the delta-base of multiple objects from\n+ multiple packs, then cross-pack delta calculations may slow down.\n+ This is currently only theoretical and has not been demonstrated\n+ to be a measurable issue.\n+\n+Current Limitations\n+-------------------\n+\n+- MIDX files are managed only by the midx builtin and is not\n+ automatically updated on clone or fetch.\n+\n+- There is no '--verify' option for the midx builtin to verify\n+ the contents of the MIDX file against the pack contents.\n+\n+- Constructing a MIDX file currently requires the single-pack\n+ index for every pack being added to the MIDX.\n+\n+- The fsck builtin does not check MIDX files, but should.\n+\n+- The repack builtin is not aware of the MIDX files, and may\n+ invalidate the MIDX files by deleting existing packfiles. The\n+ MIDX may also be extended in the future to store metadata about\n+ a packfile that can be used for faster repack commands.\n+\n+- The naive Git HTTP server advertises lists of packfiles using\n+ the file system directly.\n+\n+Future Work\n+-----------\n+\n+- The current file-format requires between 28 and 36 bytes per\n+ object. As the repository grows, the MIDX file can become\n+ very large and become a bottleneck when updating the file. To\n+ fix this \"big write\" problem, we can make the MIDX file\n+ incremental. Instead of just one MIDX file, we will have a\n+ sequence of MIDX files that can be unioned together. Then\n+ on write we take the new objects to add and consider how many\n+ existing files should be merged into a new file containing\n+ the latest objects.\n+\n+ This list of \"base indexes\" will be presented as an optional\n+ chunk in the MIDX format and contains the OIDs for the base\n+ files. Thus, the `midx_head` file only stores the OID for the\n+ \"tip\" MIDX file and then the rest are loaded based on those\n+ pointers, such as the following figure:\n+\n+ [ BIG ] <- [ MEDIUM ] <- [tiny] <- midx_head\n+\t ^___________________________|\n+\n+ The plan being that every write replaces the \"tiny\" index,\n+ and when that index becomes large enough it merges with the\n+ \"medium\" index and a new tiny index is created in the next\n+ write. Very rarely, the \"big\" index would be updated, causing\n+ a slow write.\n+\n+- After the MIDX feature is sufficiently hardened and widely used,\n+ consider making Git more fully depend on the MIDX file. If MIDX\n+ is the default, then we can delete the single-pack-indexes from\n+ the pack directory. We could also allow thin packs in the pack\n+ directory.\n+\n+- The MIDX could be extended to store a \"stable object order\" such\n+ that adding objects to the order does not change the existing\n+ objects. This would enable re-using the reachability bitmaps after\n+ repacking and updating the MIDX file.\n+\n+Related Links\n+-------------\n+\n+[0] https://bugs.chromium.org/p/git/issues/detail?id=6\n+ Chromium work item for: Multi-Pack Index (MIDX)\n+\n+[1] https://public-inbox.org/git/CB5074CF.3AD7A%25joshua.redstone@fb.com/T/#u\n+ Subject: Git performance results on a large repository\n+ Date: 3 Feb 2012\n+\n-- \n2.15.0\n\n"},{"id":"336089","messageId":"20180107181459.222909-3-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 02/18] midx: specify midx file format","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:43Z","receivedAt":"2018-01-07T18:15:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"A multi-pack-index (MIDX) file indexes the objects in multiple\npackfiles in a single pack directory. After a simple fixed-size\nheader, the version 1 file format uses chunks to specify\ndifferent regions of the data that correspond to different types\nof data, including:\n\n- List of OIDs in lex-order\n- A fanout table into the OID list\n- List of packfile names (relative to pack directory)\n- List of object metadata\n- Large offsets (if needed)\n\nBy adding extra optional chunks, we can easily extend this format\nwithout invalidating written v1 files.\n\nOne value in the header corresponds to a number of \"base MIDX files\"\nand will always be zero until the value is used in a later patch.\n\nWe considered using a hashtable format instead of an ordered list\nof objects to reduce the O(log N) lookups to O(1) lookups, but two\nmain issues arose that lead us to abandon the idea:\n\n- Extra space required to ensure collision counts were low.\n- We need to identify the two lexicographically closest OIDs for\n fast abbreviations. Binary search allows this.\n\nThe current solution presents multiple packfiles as if they were\npacked into a single packfile with one pack-index.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/pack-format.txt | 85 +++++++++++++++++++++++++++++++++\n 1 file changed, 85 insertions(+)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 8e5bf60be3..ab459ef142 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -160,3 +160,88 @@ Pack file entry: <+\n corresponding packfile.\n \n 20-byte SHA-1-checksum of all of the above.\n+\n+== midx-*.midx files have the following format:\n+\n+The multi-pack-index (MIDX) files refer to multiple pack-files.\n+\n+In order to allow extensions that add extra data to the MIDX format, we\n+organize the body into \"chunks\" and provide a lookup table at the beginning\n+of the body. The header includes certain length values, such as the number\n+of packs, the number of base MIDX files, hash lengths and types.\n+\n+All 4-byte numbers are in network order.\n+\n+HEADER:\n+\n+\t4-byte signature:\n+\t The signature is: {'M', 'I', 'D', 'X'}\n+\n+\t4-byte version number:\n+\t Git currently only supports version 1.\n+\n+\t1-byte Object Id Version (1 = SHA-1)\n+\n+\t1-byte Object Id Length (H)\n+\n+\t1-byte number (I) of base multi-pack-index files:\n+\t This value is currently always zero.\n+\n+\t1-byte number (C) of \"chunks\"\n+\n+\t4-byte number (P) of pack files\n+\n+CHUNK LOOKUP:\n+\n+\t(C + 1) * 12 bytes providing the chunk offsets:\n+\t First 4 bytes describe chunk id. Value 0 is a terminating label.\n+\t Other 8 bytes provide offset in current file for chunk to start.\n+\t (Chunks are provided in file-order, so you can infer the length\n+\t using the next chunk position if necessary.)\n+\n+\tThe remaining data in the body is described one chunk at a time, and\n+\tthese chunks may be given in any order. Chunks are required unless\n+\totherwise specified.\n+\n+CHUNK DATA:\n+\n+\tOID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)\n+\t The ith entry, F[i], stores the number of OIDs with first\n+\t byte at most i. Thus F[255] stores the total\n+\t number of objects (N). The number of objects with first byte\n+\t value i is (F[i] - F[i-1]) for i > 0.\n+\n+\tOID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)\n+\t The OIDs for all objects in the MIDX are stored in lexicographic\n+\t order in this chunk.\n+\n+\tObject Offsets (ID: {'O', 'O', 'F', 'F'}) (N * 8 bytes)\n+\t Stores two 4-byte values for every object.\n+\t 1: The pack-int-id for the pack storing this object.\n+\t 2: The offset within the pack.\n+\t\tIf all offsets are less than 2^31, then the large offset chunk\n+\t\twill not exist and offsets are stored as in IDX v1.\n+\t\tIf there is at least one offset value larger than 2^32-1, then\n+\t\tthe large offset chunk must exist. If the large offset chunk\n+\t\texists and the 31st bit is on, then removing that bit reveals\n+\t\tthe row in the large offsets containing the 8-byte offset of\n+\t\tthis object.\n+\n+\t[Optional] Object Large Offsets (ID: {'L', 'O', 'F', 'F'})\n+\t 8-byte offsets into large packfiles.\n+\n+\tPackfile Name Lookup (ID: {'P', 'L', 'O', 'O'}) (P * 4 bytes)\n+\t P * 4 bytes storing the offset in the packfile name chunk for\n+\t the null-terminated string containing the filename for the\n+\t ith packfile. The filename is relative to the MIDX file's parent\n+\t directory.\n+\n+\tPackfile Names (ID: {'P', 'N', 'A', 'M'})\n+\t Stores the packfile names as concatenated, null-terminated strings.\n+\t Packfiles must be listed in lexicographic order for fast lookups by\n+\t name. This is the only chunk not guaranteed to be a multiple of four\n+\t bytes in length, so it should be the last chunk for alignment reasons.\n+\n+TRAILER:\n+\n+\tH-byte HASH-checksum of all of the above.\n-- \n2.15.0\n\n"},{"id":"336090","messageId":"20180107181459.222909-7-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 06/18] midx: add t5318-midx.sh test script","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:47Z","receivedAt":"2018-01-07T18:15:20Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Test interactions between the midx builtin and other Git operations.\n\nUse both a full repo and a bare repo to ensure the pack directory\nredirection works correctly.\n\nSigned-off-by: Derrick Stolee \n---\n t/t5318-midx.sh | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 100 insertions(+)\n create mode 100755 t/t5318-midx.sh\n\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nnew file mode 100755\nindex 0000000000..869bbea29c\n--- /dev/null\n+++ b/t/t5318-midx.sh\n@@ -0,0 +1,100 @@\n+#!/bin/sh\n+\n+test_description='multi-pack indexes'\n+. ./test-lib.sh\n+\n+test_expect_success 'config' \\\n+ 'rm -rf .git &&\n+ mkdir full &&\n+ cd full &&\n+ git init &&\n+ git config core.midx true &&\n+ git config pack.threads 1 &&\n+ packdir=.git/objects/pack'\n+\n+test_expect_success 'write-midx with no packs' \\\n+ 'midx0=$(git midx --write) &&\n+ test \"a$midx0\" = \"a\"'\n+\n+test_expect_success 'create objects' \\\n+ 'for i in $(test_seq 100)\n+ do\n+ echo $i >file-1-$i\n+ done &&\n+ git add file-* &&\n+ test_tick &&\n+ git commit -m \"test data 1\" &&\n+ git branch commit1 HEAD'\n+\n+test_expect_success 'write-midx from index version 1' \\\n+ 'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&\n+ midx1=$(git midx --write) &&\n+ test_path_is_file ${packdir}/midx-${midx1}.midx'\n+\n+test_expect_success 'write-midx from index version 2' \\\n+ 'rm \"${packdir}/test-1-${pack1}.pack\" &&\n+ pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&\n+ midx2=$(git midx --write) &&\n+ test_path_is_file ${packdir}/midx-${midx2}.midx'\n+\n+test_expect_success 'Create more objects' \\\n+ 'for i in $(test_seq 100)\n+ do\n+ echo $i >file-2-$i\n+ done &&\n+ git add file-* &&\n+ test_tick &&\n+ git commit -m \"test data 2\" &&\n+ git branch commit2 HEAD'\n+\n+test_expect_success 'write-midx with two packs' \\\n+ 'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&\n+ midx3=$(git midx --write) &&\n+ test_path_is_file ${packdir}/midx-${midx3}.midx'\n+\n+test_expect_success 'Add more packs' \\\n+ 'for j in $(test_seq 10)\n+ do\n+ jjj=$(printf '%03i' $j)\n+ test-genrandom \"bar\" 200 > wide_delta_$jjj &&\n+ test-genrandom \"baz $jjj\" 50 >> wide_delta_$jjj &&\n+ test-genrandom \"foo\"$j 100 > deep_delta_$jjj &&\n+ test-genrandom \"foo\"$(expr $j + 1) 100 >> deep_delta_$jjj &&\n+ test-genrandom \"foo\"$(expr $j + 2) 100 >> deep_delta_$jjj &&\n+ echo $jjj >file_$jjj &&\n+ test-genrandom \"$jjj\" 8192 >>file_$jjj &&\n+ git update-index --add file_$jjj deep_delta_$jjj wide_delta_$jjj &&\n+ { echo 101 && test-genrandom 100 8192; } >file_101 &&\n+ git update-index --add file_101 &&\n+ commit=$(git commit-tree $EMPTY_TREE -p HEADobj-list &&\n+ echo commit_packs_$j = $commit &&\n+\t git branch commit_packs_$j $commit &&\n+ git update-ref HEAD $commit &&\n+ git pack-objects --index-version=2 ${packdir}/test-pack \n---\n midx.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n midx.h | 15 +++++++++++++++\n 2 files changed, 70 insertions(+)\n\ndiff --git a/midx.c b/midx.c\nindex c631be451f..4e0df0285a 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -202,6 +202,61 @@ struct pack_midx_details_internal {\n \tuint32_t internal_offset;\n };\n \n+struct pack_midx_details *nth_midxed_object_details(struct midxed_git *m,\n+\t\t\t\t\t\t uint32_t n,\n+\t\t\t\t\t\t struct pack_midx_details *d)\n+{\n+\tstruct pack_midx_details_internal *d_internal;\n+\tconst unsigned char *details = m->chunk_object_offsets;\n+\n+\tif (n >= m->num_objects)\n+\t\treturn NULL;\n+\n+\td_internal = (struct pack_midx_details_internal*)(details + 8 * n);\n+\td->pack_int_id = ntohl(d_internal->pack_int_id);\n+\td->offset = ntohl(d_internal->internal_offset);\n+\n+\tif (m->chunk_large_offsets && d->offset & MIDX_LARGE_OFFSET_NEEDED) {\n+\t\tuint32_t large_offset = d->offset ^ MIDX_LARGE_OFFSET_NEEDED;\n+\t\tconst unsigned char *large_offsets = m->chunk_large_offsets + 8 * large_offset;\n+\n+\t\td->offset = (((uint64_t)ntohl(*((uint32_t *)(large_offsets + 0)))) << 32) |\n+\t\t\t\t\t ntohl(*((uint32_t *)(large_offsets + 4)));\n+\t}\n+\n+\treturn d;\n+}\n+\n+struct pack_midx_entry *nth_midxed_object_entry(struct midxed_git *m,\n+\t\t\t\t\t\tuint32_t n,\n+\t\t\t\t\t\tstruct pack_midx_entry *e)\n+{\n+\tstruct pack_midx_details details;\n+\tconst unsigned char *index = m->chunk_oid_lookup;\n+\n+\tif (!nth_midxed_object_details(m, n, &details))\n+\t\treturn NULL;\n+\n+\tmemcpy(e->oid.hash, index + m->hdr->hash_len * n, m->hdr->hash_len);\n+\te->pack_int_id = details.pack_int_id;\n+\te->offset = details.offset;\n+\n+\treturn e;\n+}\n+\n+const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n+\t\t\t\t\t struct midxed_git *m,\n+\t\t\t\t\t uint32_t n)\n+{\n+\tstruct pack_midx_entry e;\n+\n+\tif (!nth_midxed_object_entry(m, n, &e))\n+\t\treturn 0;\n+\n+\thashcpy(oid->hash, e.oid.hash);\n+\treturn oid;\n+}\n+\n static int midx_sha1_compare(const void *_a, const void *_b)\n {\n \tstruct pack_midx_entry *a = *(struct pack_midx_entry **)_a;\ndiff --git a/midx.h b/midx.h\nindex 92b74e49db..9255909ae8 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -85,6 +85,21 @@ struct midxed_git {\n \n extern struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid);\n \n+struct pack_midx_details {\n+\tuint32_t pack_int_id;\n+\toff_t offset;\n+};\n+\n+extern struct pack_midx_details *nth_midxed_object_details(struct midxed_git *m,\n+\t\t\t\t\t\t\t uint32_t n,\n+\t\t\t\t\t\t\t struct pack_midx_details *d);\n+extern struct pack_midx_entry *nth_midxed_object_entry(struct midxed_git *m,\n+\t\t\t\t\t\t uint32_t n,\n+\t\t\t\t\t\t struct pack_midx_entry *e);\n+extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n+\t\t\t\t\t\t struct midxed_git *m,\n+\t\t\t\t\t\t uint32_t n);\n+\n /*\n * Write a single MIDX file storing the given entries for the\n * given list of packfiles. If midx_name is null, then a temp\n-- \n2.15.0\n\n"},{"id":"336092","messageId":"20180107181459.222909-12-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 11/18] midx: teach git-midx to clear midx files","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:52Z","receivedAt":"2018-01-07T18:15:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As a way to troubleshoot unforeseen problems with MIDX files, provide\na way to delete \"midx-head\" and the MIDX it references.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-midx.txt | 12 +++++++++++-\n builtin/midx.c | 31 ++++++++++++++++++++++++++++++-\n t/t5318-midx.sh | 9 +++++++++\n 3 files changed, 50 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-midx.txt b/Documentation/git-midx.txt\nindex 3eeed1d969..c184d3a593 100644\n--- a/Documentation/git-midx.txt\n+++ b/Documentation/git-midx.txt\n@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).\n SYNOPSIS\n --------\n [verse]\n-'git midx' [--write|--read] [--pack-dir ]\n+'git midx' [--write|--read|--clear] [--pack-dir ]\n \n DESCRIPTION\n -----------\n@@ -22,6 +22,10 @@ OPTIONS\n \tUse given directory for the location of packfiles, pack-indexes,\n \tand MIDX files.\n \n+--clear::\n+\tIf specified, delete the midx file specified by midx-head, and\n+\tmidx-head. (Cannot be combined with --write or --read.)\n+\n --read::\n \tIf specified, read a midx file specified by the midx-head file\n \tand output basic details about the midx file. (Cannot be combined\n@@ -79,6 +83,12 @@ $ git midx --read\n $ git midx --read --midx-id 3e50d982a2257168c7fd0ff12ffe5cf6af38c74e\n --------------------------------------------------------------------\n \n+* Delete the current midx-head and the file it references.\n++\n+-----------------------------------------------\n+$ git midx --clear\n+-----------------------------------------------\n+\n CONFIGURATION\n -------------\n \ndiff --git a/builtin/midx.c b/builtin/midx.c\nindex aff2085771..b30ef36ff8 100644\n--- a/builtin/midx.c\n+++ b/builtin/midx.c\n@@ -11,11 +11,13 @@\n static char const * const builtin_midx_usage[] = {\n \tN_(\"git midx [--pack-dir ]\"),\n \tN_(\"git midx --write [--update-head] [--pack-dir ]\"),\n+\tN_(\"git midx --clear [--pack-dir ]\"),\n \tNULL\n };\n \n static struct opts_midx {\n \tconst char *pack_dir;\n+\tint clear;\n \tint read;\n \tconst char *midx_id;\n \tint write;\n@@ -24,6 +26,29 @@ static struct opts_midx {\n \tstruct object_id old_midx_oid;\n } opts;\n \n+static int midx_clear(void)\n+{\n+\tstruct strbuf head_path = STRBUF_INIT;\n+\tchar *old_path;\n+\n+\tif (!opts.has_existing)\n+\t\treturn 0;\n+\n+\tstrbuf_addstr(&head_path, opts.pack_dir);\n+\tstrbuf_addstr(&head_path, \"/\");\n+\tstrbuf_addstr(&head_path, \"midx-head\");\n+\tif (remove_path(head_path.buf))\n+\t\tdie(\"failed to remove path %s\", head_path.buf);\n+\tstrbuf_release(&head_path);\n+\n+\told_path = get_midx_filename_oid(opts.pack_dir, &opts.old_midx_oid);\n+\tif (remove_path(old_path))\n+\t\tdie(\"failed to remove path %s\", old_path);\n+\tfree(old_path);\n+\n+\treturn 0;\n+}\n+\n static int midx_read(void)\n {\n \tstruct object_id midx_oid;\n@@ -263,6 +288,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n \t\t\tN_(\"dir\"),\n \t\t\tN_(\"The pack directory containing set of packfile and pack-index pairs.\") },\n+\t\tOPT_BOOL('c', \"clear\", &opts.clear,\n+\t\t\tN_(\"clear midx file and midx-head\")),\n \t\tOPT_BOOL('r', \"read\", &opts.read,\n \t\t\tN_(\"read midx file\")),\n \t\t{ OPTION_STRING, 'M', \"midx-id\", &opts.midx_id,\n@@ -287,7 +314,7 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t\t builtin_midx_options,\n \t\t\t builtin_midx_usage, 0);\n \n-\tif (opts.write + opts.read > 1)\n+\tif (opts.write + opts.read + opts.clear > 1)\n \t\tusage_with_options(builtin_midx_usage, builtin_midx_options);\n \n \tif (!opts.pack_dir) {\n@@ -299,6 +326,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \n \topts.has_existing = !!get_midx_head_oid(opts.pack_dir, &opts.old_midx_oid);\n \n+\tif (opts.clear)\n+\t\treturn midx_clear();\n \tif (opts.read)\n \t\treturn midx_read();\n \tif (opts.write)\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nindex 2e52389442..9337355ab3 100755\n--- a/t/t5318-midx.sh\n+++ b/t/t5318-midx.sh\n@@ -143,4 +143,13 @@ test_expect_success 'write-midx in bare repo' \\\n git midx --read >output &&\n cmp output expect'\n \n+test_expect_success 'midx --clear' \\\n+ 'git midx --clear &&\n+ test_path_is_missing \"${baredir}/midx-${midx4}.midx\" &&\n+ test_path_is_missing \"${baredir}/midx-head\" &&\n+ cd ../full &&\n+ git midx --clear &&\n+ test_path_is_missing \"${packdir}/midx-${midx4}.midx\" &&\n+ test_path_is_missing \"${packdir}/midx-head\"'\n+\n test_done\n-- \n2.15.0\n\n"},{"id":"336093","messageId":"20180107181459.222909-13-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 12/18] midx: teach git-midx to delete expired files","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:53Z","receivedAt":"2018-01-07T18:15:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As we write new MIDX files, the existing files are probably not needed. Supply\nthe \"--delete-expired\" flag to remove these files during the \"--write\" sub-\ncommand.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-midx.txt | 4 ++++\n builtin/midx.c | 15 ++++++++++++++-\n midx.c | 26 ++++++++++++++++++++++++++\n midx.h | 2 ++\n packfile.c | 2 +-\n packfile.h | 1 +\n t/t5318-midx.sh | 9 ++++++---\n 7 files changed, 54 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/git-midx.txt b/Documentation/git-midx.txt\nindex c184d3a593..4635247d0d 100644\n--- a/Documentation/git-midx.txt\n+++ b/Documentation/git-midx.txt\n@@ -43,6 +43,10 @@ OPTIONS\n \tIf specified with --write, update the midx-head file to point to\n \tthe written midx file.\n \n+--delete-expired::\n+\tIf specified with --write and --update-head, delete the midx file\n+\tpreviously pointed to by midx-head (if changed).\n+\n EXAMPLES\n --------\n \ndiff --git a/builtin/midx.c b/builtin/midx.c\nindex b30ef36ff8..6f56f39390 100644\n--- a/builtin/midx.c\n+++ b/builtin/midx.c\n@@ -10,7 +10,7 @@\n \n static char const * const builtin_midx_usage[] = {\n \tN_(\"git midx [--pack-dir ]\"),\n-\tN_(\"git midx --write [--update-head] [--pack-dir ]\"),\n+\tN_(\"git midx --write [--update-head [--delete-expired]] [--pack-dir ]\"),\n \tN_(\"git midx --clear [--pack-dir ]\"),\n \tNULL\n };\n@@ -22,6 +22,7 @@ static struct opts_midx {\n \tconst char *midx_id;\n \tint write;\n \tint update_head;\n+\tint delete_expired;\n \tint has_existing;\n \tstruct object_id old_midx_oid;\n } opts;\n@@ -276,6 +277,16 @@ static int midx_write(void)\n \tif (opts.update_head)\n \t\tupdate_head_file(opts.pack_dir, midx_id);\n \n+\tif (opts.delete_expired && opts.update_head && opts.has_existing &&\n+\t strcmp(midx_id, oid_to_hex(&opts.old_midx_oid))) {\n+\t\tchar *old_path = get_midx_filename_oid(opts.pack_dir, &opts.old_midx_oid);\n+\t\tclose_midx(midx);\n+\t\tif (remove_path(old_path))\n+\t\t\tdie(\"failed to remove path %s\", old_path);\n+\n+\t\tfree(old_path);\n+\t}\n+\n cleanup:\n \tif (pack_names)\n \t\tFREE_AND_NULL(pack_names);\n@@ -300,6 +311,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"write midx file\")),\n \t\tOPT_BOOL('u', \"update-head\", &opts.update_head,\n \t\t\tN_(\"update midx-head to written midx file\")),\n+\t\tOPT_BOOL('d', \"delete-expired\", &opts.delete_expired,\n+\t\t\tN_(\"delete expired head midx file\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/midx.c b/midx.c\nindex 53eb29dac3..3ce2b736ea 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -651,3 +651,29 @@ const char *write_midx_file(const char *pack_dir,\n \n \treturn final_hex;\n }\n+\n+int close_midx(struct midxed_git *m)\n+{\n+\tint i;\n+\tif (m->midx_fd < 0)\n+\t\treturn 0;\n+\n+\tfor (i = 0; i < m->num_packs; i++) {\n+\t\tif (m->packs[i]) {\n+\t\t\tclose_pack(m->packs[i]);\n+\t\t\tfree(m->packs[i]);\n+\t\t\tm->packs[i] = NULL;\n+\t\t}\n+\t}\n+\n+\tmunmap((void *)m->data, m->data_len);\n+\tm->data = 0;\n+\n+\tclose(m->midx_fd);\n+\tm->midx_fd = -1;\n+\n+\tfree(m->packs);\n+\tfree(m->pack_names);\n+\n+\treturn 1;\n+}\ndiff --git a/midx.h b/midx.h\nindex 1e7a94651c..27d48163e9 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -117,4 +117,6 @@ extern const char *write_midx_file(const char *pack_dir,\n \t\t\t\t struct pack_midx_entry **objects,\n \t\t\t\t uint32_t nr_objects);\n \n+extern int close_midx(struct midxed_git *m);\n+\n #endif\ndiff --git a/packfile.c b/packfile.c\nindex 4a5fe7ab18..c36420b33f 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -299,7 +299,7 @@ void close_pack_index(struct packed_git *p)\n \t}\n }\n \n-static void close_pack(struct packed_git *p)\n+void close_pack(struct packed_git *p)\n {\n \tclose_pack_windows(p);\n \tclose_pack_fd(p);\ndiff --git a/packfile.h b/packfile.h\nindex 0cdeb54dcd..7cf4771029 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -61,6 +61,7 @@ extern void close_pack_index(struct packed_git *);\n \n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n extern void close_pack_windows(struct packed_git *);\n+extern void close_pack(struct packed_git *p);\n extern void close_all_packs(void);\n extern void unuse_pack(struct pack_window **);\n extern void clear_delta_base_cache(void);\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nindex 9337355ab3..42d103c879 100755\n--- a/t/t5318-midx.sh\n+++ b/t/t5318-midx.sh\n@@ -75,6 +75,7 @@ test_expect_success 'write-midx with two packs' \\\n 'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&\n midx3=$(git midx --write --update-head) &&\n test_path_is_file ${packdir}/midx-${midx3}.midx &&\n+ test_path_is_file ${packdir}/midx-${midx2}.midx &&\n test_path_is_file ${packdir}/midx-head &&\n test $(cat ${packdir}/midx-head) = \"$midx3\" &&\n _midx_read_expect \\\n@@ -107,8 +108,10 @@ test_expect_success 'Add more packs' \\\n done'\n \n test_expect_success 'write-midx with twelve packs' \\\n- 'midx4=$(git midx --write --update-head) &&\n+ 'midx4=$(git midx --write --update-head --delete-expired) &&\n test_path_is_file ${packdir}/midx-${midx4}.midx &&\n+ test_path_is_missing ${packdir}/midx-${midx3}.midx &&\n+ test_path_is_file ${packdir}/midx-${midx2}.midx &&\n test_path_is_file ${packdir}/midx-head &&\n test $(cat ${packdir}/midx-head) = \"$midx4\" &&\n _midx_read_expect \\\n@@ -118,7 +121,7 @@ test_expect_success 'write-midx with twelve packs' \\\n cmp output expect'\n \n test_expect_success 'write-midx with no new packs' \\\n- 'midx5=$(git midx --write --update-head) &&\n+ 'midx5=$(git midx --write --update-head --delete-expired) &&\n test_path_is_file ${packdir}/midx-${midx5}.midx &&\n test \"a$midx4\" = \"a$midx5\" &&\n test_path_is_file ${packdir}/midx-head &&\n@@ -133,7 +136,7 @@ test_expect_success 'create bare repo' \\\n baredir=./objects/pack'\n \n test_expect_success 'write-midx in bare repo' \\\n- 'midxbare=$(git midx --write --update-head) &&\n+ 'midxbare=$(git midx --write --update-head --delete-expired) &&\n test_path_is_file ${baredir}/midx-${midxbare}.midx &&\n test_path_is_file ${baredir}/midx-head &&\n test $(cat ${baredir}/midx-head) = \"$midxbare\" &&\n-- \n2.15.0\n\n"},{"id":"336094","messageId":"20180107181459.222909-14-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 13/18] t5318-midx.h: confirm git actions are stable","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:54Z","receivedAt":"2018-01-07T18:15:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Perform some basic read-only operations that load objects and find\nabbreviations. As this functionality begins to reference MIDX files,\nensure the output matches when using MIDX files and when not using them.\n\nSigned-off-by: Derrick Stolee \n---\n t/t5318-midx.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nindex 42d103c879..00be852ed3 100755\n--- a/t/t5318-midx.sh\n+++ b/t/t5318-midx.sh\n@@ -37,6 +37,19 @@ _midx_read_expect() {\n \tEOF\n }\n \n+_midx_git_two_modes() {\n+\tgit -c core.midx=true $1 >output\n+\tgit -c core.midx=false $1 >expect\n+}\n+\n+_midx_git_behavior() {\n+\ttest_expect_success 'check normal git operations' \\\n+\t '_midx_git_two_modes \"log --patch master\" &&\n+\t cmp output expect &&\n+\t _midx_git_two_modes \"rev-list --all --objects\" &&\n+\t cmp output expect'\n+}\n+\n test_expect_success 'write-midx from index version 1' \\\n 'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&\n midx1=$(git midx --write) &&\n@@ -48,6 +61,8 @@ test_expect_success 'write-midx from index version 1' \\\n git midx --read --midx-id=${midx1} >output &&\n cmp output expect'\n \n+_midx_git_behavior\n+\n test_expect_success 'write-midx from index version 2' \\\n 'rm \"${packdir}/test-1-${pack1}.pack\" &&\n pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&\n@@ -61,6 +76,8 @@ test_expect_success 'write-midx from index version 2' \\\n git midx --read> output &&\n cmp output expect'\n \n+_midx_git_behavior\n+\n test_expect_success 'Create more objects' \\\n 'for i in $(test_seq 100)\n do\n@@ -71,6 +88,8 @@ test_expect_success 'Create more objects' \\\n git commit -m \"test data 2\" &&\n git branch commit2 HEAD'\n \n+_midx_git_behavior\n+\n test_expect_success 'write-midx with two packs' \\\n 'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&\n midx3=$(git midx --write --update-head) &&\n@@ -84,6 +103,8 @@ test_expect_success 'write-midx with two packs' \\\n git midx --read >output &&\n cmp output expect'\n \n+_midx_git_behavior\n+\n test_expect_success 'Add more packs' \\\n 'for i in $(test_seq 10)\n do\n@@ -107,6 +128,8 @@ test_expect_success 'Add more packs' \\\n git pack-objects --index-version=2 ${packdir}/test-pack output &&\n cmp output expect'\n \n+_midx_git_behavior\n+\n test_expect_success 'write-midx with no new packs' \\\n 'midx5=$(git midx --write --update-head --delete-expired) &&\n test_path_is_file ${packdir}/midx-${midx5}.midx &&\n@@ -127,6 +152,8 @@ test_expect_success 'write-midx with no new packs' \\\n test_path_is_file ${packdir}/midx-head &&\n test $(cat ${packdir}/midx-head) = \"$midx4\"'\n \n+_midx_git_behavior\n+\n test_expect_success 'create bare repo' \\\n 'cd .. &&\n git clone --bare full bare &&\n@@ -146,6 +173,8 @@ test_expect_success 'write-midx in bare repo' \\\n git midx --read >output &&\n cmp output expect'\n \n+_midx_git_behavior\n+\n test_expect_success 'midx --clear' \\\n 'git midx --clear &&\n test_path_is_missing \"${baredir}/midx-${midx4}.midx\" &&\n@@ -155,4 +184,6 @@ test_expect_success 'midx --clear' \\\n test_path_is_missing \"${packdir}/midx-${midx4}.midx\" &&\n test_path_is_missing \"${packdir}/midx-head\"'\n \n+_midx_git_behavior\n+\n test_done\n-- \n2.15.0\n\n"},{"id":"336095","messageId":"20180107181459.222909-16-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 15/18] midx: use midx for approximate object count","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:56Z","receivedAt":"2018-01-07T18:15:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The MIDX files contain a complete object count, so we can report the number\nof objects in the MIDX. The count remains approximate as there may be overlap\nbetween the packfiles not referenced by the MIDX.\n\nSigned-off-by: Derrick Stolee \n---\n packfile.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 1c0822878b..866a1f30dd 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -803,7 +803,8 @@ static void prepare_packed_git_one(char *objdir, int local)\n \t\tif (ends_with(de->d_name, \".idx\") ||\n \t\t ends_with(de->d_name, \".pack\") ||\n \t\t ends_with(de->d_name, \".bitmap\") ||\n-\t\t ends_with(de->d_name, \".keep\"))\n+\t\t ends_with(de->d_name, \".keep\") ||\n+\t\t ends_with(de->d_name, \".midx\"))\n \t\t\tstring_list_append(&garbage, path.buf);\n \t\telse\n \t\t\treport_garbage(PACKDIR_FILE_GARBAGE, path.buf);\n@@ -828,9 +829,12 @@ unsigned long approximate_object_count(void)\n \tstatic unsigned long count;\n \tif (!approximate_object_count_valid) {\n \t\tstruct packed_git *p;\n+\t\tstruct midxed_git *m;\n \n-\t\tprepare_packed_git();\n+\t\tprepare_packed_git_internal(1);\n \t\tcount = 0;\n+\t\tfor (m = midxed_git; m; m = m->next)\n+\t\t\tcount += m->num_objects;\n \t\tfor (p = packed_git; p; p = p->next) {\n \t\t\tif (open_pack_index(p))\n \t\t\t\tcontinue;\n-- \n2.15.0\n\n"},{"id":"336096","messageId":"20180107181459.222909-19-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 18/18] packfile: use midx for object loads","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:59Z","receivedAt":"2018-01-07T18:15:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When looking for a packed object, first check the MIDX for that object.\nThis reduces thrashing in the MRU list of packfiles.\n\nSigned-off-by: Derrick Stolee \n---\n midx.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n midx.h | 3 +++\n packfile.c | 5 +++-\n 3 files changed, 91 insertions(+), 1 deletion(-)\n\ndiff --git a/midx.c b/midx.c\nindex 8c643caa92..4b2398b3ee 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -329,6 +329,90 @@ int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos)\n \treturn 0;\n }\n \n+static int prepare_midx_pack(struct midxed_git *m, uint32_t pack_int_id)\n+{\n+\tstruct strbuf pack_name = STRBUF_INIT;\n+\n+\tif (pack_int_id >= m->hdr->num_packs)\n+\t\treturn 1;\n+\n+\tif (m->packs[pack_int_id])\n+\t\treturn 0;\n+\n+\tstrbuf_addstr(&pack_name, m->pack_dir);\n+\tstrbuf_addstr(&pack_name, \"/\");\n+\tstrbuf_addstr(&pack_name, m->pack_names[pack_int_id]);\n+\tstrbuf_strip_suffix(&pack_name, \".pack\");\n+\tstrbuf_addstr(&pack_name, \".idx\");\n+\n+\tm->packs[pack_int_id] = add_packed_git(pack_name.buf, pack_name.len, 1);\n+\tstrbuf_release(&pack_name);\n+\treturn !m->packs[pack_int_id];\n+}\n+\n+static int find_pack_entry_midx(const unsigned char *sha1,\n+\t\t\t\tstruct midxed_git *m,\n+\t\t\t\tstruct packed_git **p,\n+\t\t\t\toff_t *offset)\n+{\n+\tuint32_t pos;\n+\tstruct pack_midx_details d;\n+\n+\tif (!bsearch_midx(m, sha1, &pos) ||\n+\t !nth_midxed_object_details(m, pos, &d))\n+\t\treturn 0;\n+\n+\tif (d.pack_int_id >= m->num_packs)\n+\t\tdie(_(\"bad pack-int-id %d\"), d.pack_int_id);\n+\n+\t/* load packfile, if necessary */\n+\tif (prepare_midx_pack(m, d.pack_int_id))\n+\t\treturn 0;\n+\n+\t*p = m->packs[d.pack_int_id];\n+\t*offset = d.offset;\n+\n+\treturn 1;\n+}\n+\n+int fill_pack_entry_midx(const unsigned char *sha1,\n+\t\t\t struct pack_entry *e)\n+{\n+\tstruct packed_git *p;\n+\tstruct midxed_git *m;\n+\n+\tif (!core_midx)\n+\t\treturn 0;\n+\n+\tm = midxed_git;\n+\twhile (m)\n+\t{\n+\t\toff_t offset;\n+\t\tif (!find_pack_entry_midx(sha1, m, &p, &offset)) {\n+\t\t\tm = m->next;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t* We are about to tell the caller where they can locate the\n+\t\t* requested object. We better make sure the packfile is\n+\t\t* still here and can be accessed before supplying that\n+\t\t* answer, as it may have been deleted since the MIDX was\n+\t\t* loaded!\n+\t\t*/\n+\t\tif (!is_pack_valid(p))\n+\t\t\treturn 0;\n+\n+\t\te->offset = offset;\n+\t\te->p = p;\n+\t\thashcpy(e->sha1, sha1);\n+\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n int contains_pack(struct midxed_git *m, const char *pack_name)\n {\n \tuint32_t first = 0, last = m->num_packs;\ndiff --git a/midx.h b/midx.h\nindex 5598799189..b7e8b15fe4 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -11,6 +11,9 @@ extern char *get_midx_head_filename(const char *pack_dir);\n \n extern struct object_id *get_midx_head_oid(const char *pack_dir, struct object_id *oid);\n \n+extern int fill_pack_entry_midx(const unsigned char *sha1,\n+\t\t\t\tstruct pack_entry *e);\n+\n struct pack_midx_entry {\n \tstruct object_id oid;\n \tuint32_t pack_int_id;\ndiff --git a/packfile.c b/packfile.c\nindex 866a1f30dd..9ec39a83e9 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1883,7 +1883,10 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)\n {\n \tstruct mru_entry *p;\n \n-\tprepare_packed_git();\n+\tprepare_packed_git_internal(1);\n+\tif (fill_pack_entry_midx(sha1, e))\n+\t\treturn 1;\n+\n \tif (!packed_git)\n \t\treturn 0;\n \n-- \n2.15.0\n\n"},{"id":"336097","messageId":"20180107181459.222909-18-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 17/18] sha1_name: use midx for abbreviations","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:58Z","receivedAt":"2018-01-07T18:15:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Create unique_in_midx() to mimic behavior of unique_in_pack().\n\nCreate find_abbrev_len_for_midx() to mimic behavior of\nfind_abbrev_len_for_pack().\n\nConsume these methods when interacting with abbreviations.\n\nSigned-off-by: Derrick Stolee \n---\n sha1_name.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 68 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 611c7d24dd..2f426e136e 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -10,6 +10,7 @@\n #include \"dir.h\"\n #include \"sha1-array.h\"\n #include \"packfile.h\"\n+#include \"midx.h\"\n \n static int get_oid_oneline(const char *, struct object_id *, struct commit_list *);\n \n@@ -190,11 +191,40 @@ static void unique_in_pack(struct packed_git *p,\n \t}\n }\n \n+static void unique_in_midx(struct midxed_git *m,\n+\t\t\t struct disambiguate_state *ds)\n+{\n+\tuint32_t num, i, first = 0;\n+\tconst struct object_id *current = NULL;\n+\n+\tif (!m->num_objects)\n+\t\treturn;\n+\n+\tnum = m->num_objects;\n+\tbsearch_midx(m, ds->bin_pfx.hash, &first);\n+\n+\t/*\n+\t * At this point, \"first\" is the location of the lowest object\n+\t * with an object name that could match \"bin_pfx\". See if we have\n+\t * 0, 1 or more objects that actually match(es).\n+\t */\n+\tfor (i = first; i < num && !ds->ambiguous; i++) {\n+\t\tstruct object_id oid;\n+\t\tcurrent = nth_midxed_object_oid(&oid, m, i);\n+\t\tif (!match_sha(ds->len, ds->bin_pfx.hash, current->hash))\n+\t\t\tbreak;\n+\t\tupdate_candidates(ds, current);\n+\t}\n+}\n+\n static void find_short_packed_object(struct disambiguate_state *ds)\n {\n \tstruct packed_git *p;\n+\tstruct midxed_git *m;\n \n-\tprepare_packed_git();\n+\tprepare_packed_git_internal(1);\n+\tfor (m = midxed_git; m && !ds->ambiguous; m = m->next)\n+\t\tunique_in_midx(m, ds);\n \tfor (p = packed_git; p && !ds->ambiguous; p = p->next)\n \t\tunique_in_pack(p, ds);\n }\n@@ -508,6 +538,39 @@ static int extend_abbrev_len(const struct object_id *oid, void *cb_data)\n \treturn 0;\n }\n \n+static void find_abbrev_len_for_midx(struct midxed_git *m,\n+\t\t\t\t struct min_abbrev_data *mad)\n+{\n+\tint match = 0;\n+\tuint32_t first = 0;\n+\tstruct object_id oid;\n+\n+\tif (!m->num_objects)\n+\t\treturn;\n+\n+\tmatch = bsearch_midx(m, mad->hash, &first);\n+\n+\t/*\n+\t * first is now the position in the packfile where we would insert\n+\t * mad->hash if it does not exist (or the position of mad->hash if\n+\t * it does exist). Hence, we consider a maximum of three objects\n+\t * nearby for the abbreviation length.\n+\t */\n+\tmad->init_len = 0;\n+\tif (!match) {\n+\t\tnth_midxed_object_oid(&oid, m, first);\n+\t\textend_abbrev_len(&oid, mad);\n+\t} else if (first < m->num_objects - 1) {\n+\t\tnth_midxed_object_oid(&oid, m, first + 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tif (first > 0) {\n+\t\tnth_midxed_object_oid(&oid, m, first - 1);\n+\t\textend_abbrev_len(&oid, mad);\n+\t}\n+\tmad->init_len = mad->cur_len;\n+}\n+\n static void find_abbrev_len_for_pack(struct packed_git *p,\n \t\t\t\t struct min_abbrev_data *mad)\n {\n@@ -563,8 +626,11 @@ static void find_abbrev_len_for_pack(struct packed_git *p,\n static void find_abbrev_len_packed(struct min_abbrev_data *mad)\n {\n \tstruct packed_git *p;\n+\tstruct midxed_git *m;\n \n-\tprepare_packed_git();\n+\tprepare_packed_git_internal(1);\n+\tfor (m = midxed_git; m; m = m->next)\n+\t\tfind_abbrev_len_for_midx(m, mad);\n \tfor (p = packed_git; p; p = p->next)\n \t\tfind_abbrev_len_for_pack(p, mad);\n }\n-- \n2.15.0\n\n"},{"id":"336098","messageId":"20180107181459.222909-9-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 08/18] midx: teach git-midx to read midx file details","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:49Z","receivedAt":"2018-01-07T18:15:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Commentary: I included the pack directory of the MIDX file as a FLEX_ARRAY\nat the end of the midxed_git struct, similar to how the pack name appears\nat the end of the packed_git struct. A colleague mentioned this pattern is\nconfusing and possibly dangerous so I should consider changing it. If there\nis no strong reason for this, then I will modify the struct before the v1\npatch to use a char*.\n\n-- >8 --\n\nAdd a \"--read\" subcommand to the midx builtin to report summary information\non the head MIDX file or a MIDX file specified by the supplied \"--midx-id\"\nparameter.\n\nThis subcommand is used by t5318-midx.sh to verify the indexed objects are\nas expected.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-midx.txt | 23 +++++++-\n builtin/midx.c | 59 ++++++++++++++++++++\n midx.c | 132 +++++++++++++++++++++++++++++++++++++++++++++\n midx.h | 58 ++++++++++++++++++++\n t/t5318-midx.sh | 79 +++++++++++++++++++--------\n 5 files changed, 328 insertions(+), 23 deletions(-)\n\ndiff --git a/Documentation/git-midx.txt b/Documentation/git-midx.txt\nindex 01f79cbba5..3eeed1d969 100644\n--- a/Documentation/git-midx.txt\n+++ b/Documentation/git-midx.txt\n@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).\n SYNOPSIS\n --------\n [verse]\n-'git midx' --write [--pack-dir ]\n+'git midx' [--write|--read] [--pack-dir ]\n \n DESCRIPTION\n -----------\n@@ -22,9 +22,18 @@ OPTIONS\n \tUse given directory for the location of packfiles, pack-indexes,\n \tand MIDX files.\n \n+--read::\n+\tIf specified, read a midx file specified by the midx-head file\n+\tand output basic details about the midx file. (Cannot be combined\n+\twith --write.)\n+\n+--midx-id ::\n+\tIf specified with --read, use the given oid to read midx-[oid].midx\n+\tinstead of using midx-head.\n --write::\n \tIf specified, write a new midx file to the pack directory using\n \tthe packfiles present. Outputs the hash of the result midx file.\n+\t(Cannot be combined with --read.)\n \n --update-head::\n \tIf specified with --write, update the midx-head file to point to\n@@ -58,6 +67,18 @@ $ git midx --write --update-head\n $ git midx --write --pack-dir ../../alt/pack/\n ---------------------------------------------------------\n \n+* Read the current midx-head.\n++\n+-----------------------------------------------\n+$ git midx --read\n+-----------------------------------------------\n+\n+* Read a specific MIDX file in the local .git folder.\n++\n+--------------------------------------------------------------------\n+$ git midx --read --midx-id 3e50d982a2257168c7fd0ff12ffe5cf6af38c74e\n+--------------------------------------------------------------------\n+\n CONFIGURATION\n -------------\n \ndiff --git a/builtin/midx.c b/builtin/midx.c\nindex 84ce6588a2..ee9234583d 100644\n--- a/builtin/midx.c\n+++ b/builtin/midx.c\n@@ -16,12 +16,60 @@ static char const * const builtin_midx_usage[] = {\n \n static struct opts_midx {\n \tconst char *pack_dir;\n+\tint read;\n+\tconst char *midx_id;\n \tint write;\n \tint update_head;\n \tint has_existing;\n \tstruct object_id old_midx_oid;\n } opts;\n \n+static int midx_read(void)\n+{\n+\tstruct object_id midx_oid;\n+\tstruct midxed_git *midx;\n+\tuint32_t i;\n+\n+\tif (opts.midx_id && strlen(opts.midx_id) == GIT_MAX_HEXSZ)\n+\t\tget_oid_hex(opts.midx_id, &midx_oid);\n+\telse if (!get_midx_head_oid(opts.pack_dir, &midx_oid))\n+\t\tdie(\"No midx-head exists.\");\n+\n+\tmidx = get_midxed_git(opts.pack_dir, &midx_oid);\n+\n+\tprintf(\"header: %08x %x %d %d %d %d %d\\n\",\n+\t\tntohl(midx->hdr->midx_signature),\n+\t\tntohl(midx->hdr->midx_version),\n+\t\tmidx->hdr->hash_version,\n+\t\tmidx->hdr->hash_len,\n+\t\tmidx->hdr->num_base_midx,\n+\t\tmidx->hdr->num_chunks,\n+\t\tntohl(midx->hdr->num_packs));\n+\tprintf(\"num_objects: %d\\n\", midx->num_objects);\n+\tprintf(\"chunks:\");\n+\n+\tif (midx->chunk_pack_lookup)\n+\t\tprintf(\" pack_lookup\");\n+\tif (midx->chunk_pack_names)\n+\t\tprintf(\" pack_names\");\n+\tif (midx->chunk_oid_fanout)\n+\t\tprintf(\" oid_fanout\");\n+\tif (midx->chunk_oid_lookup)\n+\t\tprintf(\" oid_lookup\");\n+\tif (midx->chunk_object_offsets)\n+\t\tprintf(\" object_offsets\");\n+\tif (midx->chunk_large_offsets)\n+\t\tprintf(\" large_offsets\");\n+\tprintf(\"\\n\");\n+\n+\tprintf(\"pack_names:\\n\");\n+\tfor (i = 0; i < midx->num_packs; i++)\n+\t\tprintf(\"%s\\n\", midx->pack_names[i]);\n+\n+\tprintf(\"pack_dir: %s\\n\", midx->pack_dir);\n+\treturn 0;\n+}\n+\n static int build_midx_from_packs(\n \tconst char *pack_dir,\n \tconst char **pack_names, uint32_t nr_packs,\n@@ -187,6 +235,12 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n \t\t\tN_(\"dir\"),\n \t\t\tN_(\"The pack directory containing set of packfile and pack-index pairs.\") },\n+\t\tOPT_BOOL('r', \"read\", &opts.read,\n+\t\t\tN_(\"read midx file\")),\n+\t\t{ OPTION_STRING, 'M', \"midx-id\", &opts.midx_id,\n+\t\t\tN_(\"oid\"),\n+\t\t\tN_(\"An OID for a specific midx file in the pack-dir.\"),\n+\t\t\tPARSE_OPT_OPTARG, NULL, (intptr_t) \"\" },\n \t\tOPT_BOOL('w', \"write\", &opts.write,\n \t\t\tN_(\"write midx file\")),\n \t\tOPT_BOOL('u', \"update-head\", &opts.update_head,\n@@ -205,6 +259,9 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t\t builtin_midx_options,\n \t\t\t builtin_midx_usage, 0);\n \n+\tif (opts.write + opts.read > 1)\n+\t\tusage_with_options(builtin_midx_usage, builtin_midx_options);\n+\n \tif (!opts.pack_dir) {\n \t\tstruct strbuf path = STRBUF_INIT;\n \t\tstrbuf_addstr(&path, get_object_directory());\n@@ -214,6 +271,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \n \topts.has_existing = !!get_midx_head_oid(opts.pack_dir, &opts.old_midx_oid);\n \n+\tif (opts.read)\n+\t\treturn midx_read();\n \tif (opts.write)\n \t\treturn midx_write();\n \ndiff --git a/midx.c b/midx.c\nindex f4178c1b81..c631be451f 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -65,6 +65,138 @@ struct object_id *get_midx_head_oid(const char *pack_dir,\n \treturn oid;\n }\n \n+static struct midxed_git *alloc_midxed_git(int extra)\n+{\n+\tstruct midxed_git *m = xmalloc(st_add(sizeof(*m), extra));\n+\tmemset(m, 0, sizeof(*m));\n+\tm->midx_fd = -1;\n+\n+\treturn m;\n+}\n+\n+static struct midxed_git *load_midxed_git_one(const char *midx_file, const char *pack_dir)\n+{\n+\tvoid *midx_map;\n+\tconst unsigned char *data;\n+\tstruct pack_midx_header *hdr;\n+\tsize_t midx_size, packs_len;\n+\tstruct stat st;\n+\tuint32_t i;\n+\tstruct midxed_git *midx;\n+\tint fd = git_open(midx_file);\n+\n+\tif (fd < 0)\n+\t\treturn 0;\n+\tif (fstat(fd, &st)) {\n+\t\tclose(fd);\n+\t\treturn 0;\n+\t}\n+\tmidx_size = xsize_t(st.st_size);\n+\n+\tif (midx_size < 16 + 8 * 5 + 4 * 256 + GIT_MAX_RAWSZ) {\n+\t\tclose(fd);\n+\t\tdie(\"midx file %s is too small\", midx_file);\n+\t}\n+\tmidx_map = xmmap(NULL, midx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tdata = (const unsigned char *)midx_map;\n+\n+\thdr = midx_map;\n+\tif (ntohl(hdr->midx_signature) != MIDX_SIGNATURE) {\n+\t\tmunmap(midx_map, midx_size);\n+\t\tclose(fd);\n+\t\tdie(\"MIDX signature %X does not match signature %X\",\n+\t\t ntohl(hdr->midx_signature), MIDX_SIGNATURE);\n+\t}\n+\n+\tif (ntohl(hdr->midx_version) != MIDX_VERSION) {\n+\t\tmunmap(midx_map, midx_size);\n+\t\tdie(\"MIDX version %X does not match version %X\",\n+\t\t ntohl(hdr->midx_version), MIDX_VERSION);\n+\t}\n+\n+\tmidx = alloc_midxed_git(strlen(pack_dir) + 1);\n+\n+\tmidx->hdr = hdr;\n+\tmidx->midx_fd = fd;\n+\tmidx->data = midx_map;\n+\tmidx->data_len = midx_size;\n+\n+\tfor (i = 0; i <= hdr->num_chunks; i++) {\n+\t\tuint32_t chunk_id = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i));\n+\t\tuint64_t chunk_offset1 = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i + 4));\n+\t\tuint32_t chunk_offset2 = ntohl(*(uint32_t*)(data + sizeof(*hdr) + 12 * i + 8));\n+\t\tuint64_t chunk_offset = (chunk_offset1 << 32) | chunk_offset2;\n+\n+\t\tif (sizeof(data) == 4 && chunk_offset >> 32) {\n+\t\t\tmunmap(midx_map, midx_size);\n+\t\t\tclose(fd);\n+\t\t\tdie(_(\"unable to memory-map in 32-bit address space\"));\n+\t\t}\n+\n+\t\tswitch (chunk_id) {\n+\t\t\tcase MIDX_CHUNKID_PACKLOOKUP:\n+\t\t\t\tmidx->chunk_pack_lookup = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase MIDX_CHUNKID_PACKNAMES:\n+\t\t\t\tmidx->chunk_pack_names = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase MIDX_CHUNKID_OIDFANOUT:\n+\t\t\t\tmidx->chunk_oid_fanout = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase MIDX_CHUNKID_OIDLOOKUP:\n+\t\t\t\tmidx->chunk_oid_lookup = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase MIDX_CHUNKID_OBJECTOFFSETS:\n+\t\t\t\tmidx->chunk_object_offsets = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase MIDX_CHUNKID_LARGEOFFSETS:\n+\t\t\t\tmidx->chunk_large_offsets = data + chunk_offset;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase 0:\n+\t\t\t\tbreak;\n+\n+\t\t\tdefault:\n+\t\t\t\tmunmap(midx_map, midx_size);\n+\t\t\t\tclose(fd);\n+\t\t\t\tdie(\"unrecognized MIDX chunk id: %08x\", chunk_id);\n+\t\t}\n+\t}\n+\n+\tmidx->num_objects = ntohl(*((uint32_t*)(midx->chunk_oid_fanout + 255 * 4)));\n+\tmidx->num_packs = ntohl(midx->hdr->num_packs);\n+\n+\tpacks_len = st_mult(sizeof(struct packed_git*), midx->num_packs);\n+\n+\tif (packs_len) {\n+\t\tALLOC_ARRAY(midx->packs, midx->num_packs);\n+\t\tALLOC_ARRAY(midx->pack_names, midx->num_packs);\n+\t\tmemset(midx->packs, 0, packs_len);\n+\n+\t\tfor (i = 0; i < midx->num_packs; i++) {\n+\t\t\tuint32_t name_offset = ntohl(*(uint32_t*)(midx->chunk_pack_lookup + 4 * i));\n+\t\t\tmidx->pack_names[i] = (const char*)(midx->chunk_pack_names + name_offset);\n+\t\t}\n+\t}\n+\n+\tstrcpy(midx->pack_dir, pack_dir);\n+\treturn midx;\n+}\n+\n+struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid)\n+{\n+\tstruct midxed_git *m;\n+\tchar *fname = get_midx_filename_oid(pack_dir, oid);\n+\tm = load_midxed_git_one(fname, pack_dir);\n+\tfree(fname);\n+\treturn m;\n+}\n+\n struct pack_midx_details_internal {\n \tuint32_t pack_int_id;\n \tuint32_t internal_offset;\ndiff --git a/midx.h b/midx.h\nindex 9d9ab85261..92b74e49db 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -27,6 +27,64 @@ struct pack_midx_header {\n \tuint32_t num_packs;\n };\n \n+struct midxed_git {\n+\tstruct midxed_git *next;\n+\n+\tint midx_fd;\n+\n+\t/* the mmap'd data for the midx file */\n+\tconst unsigned char *data;\n+\tsize_t data_len;\n+\n+\t/* points into the mmap'd data */\n+\tstruct pack_midx_header *hdr;\n+\n+\t/* can construct filename from obj_dir + \"/packs/midx-\" + oid + \".midx\" */\n+\tstruct object_id oid;\n+\n+\t/* derived from the fanout chunk */\n+\tuint32_t num_objects;\n+\n+\t/* converted number of packs */\n+\tuint32_t num_packs;\n+\n+\t/* hdr->num_packs * 4 bytes */\n+\tconst unsigned char *chunk_pack_lookup;\n+\tconst unsigned char *chunk_pack_names;\n+\n+\t/* 256 * 4 bytes */\n+\tconst unsigned char *chunk_oid_fanout;\n+\n+\t/* num_objects * hdr->hash_len bytes */\n+\tconst unsigned char *chunk_oid_lookup;\n+\n+\t/* num_objects * 8 bytes */\n+\tconst unsigned char *chunk_object_offsets;\n+\n+\t/*\n+\t * 8 bytes per large offset.\n+\t * (Optional: may be null.)\n+\t */\n+\tconst unsigned char *chunk_large_offsets;\n+\n+\t/*\n+\t * Points into mmap'd data storing the pack filenames.\n+\t */\n+\tconst char **pack_names;\n+\n+\t/*\n+\t * Store an array of pack-pointers. If NULL, then the\n+\t * pack has not been loaded yet. The array indices\n+\t * correspond to the pack_int_ids from the midx storage.\n+\t */\n+\tstruct packed_git **packs;\n+\n+\t/* something like \".git/objects/pack\" */\n+\tchar pack_dir[FLEX_ARRAY]; /* more */\n+};\n+\n+extern struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid);\n+\n /*\n * Write a single MIDX file storing the given entries for the\n * given list of packfiles. If midx_name is null, then a temp\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nindex b66efcdce9..2e52389442 100755\n--- a/t/t5318-midx.sh\n+++ b/t/t5318-midx.sh\n@@ -26,11 +26,27 @@ test_expect_success 'create objects' \\\n git commit -m \"test data 1\" &&\n git branch commit1 HEAD'\n \n+_midx_read_expect() {\n+\tcat >expect <<- EOF\n+\theader: 4d494458 1 1 20 0 5 $1\n+\tnum_objects: $2\n+\tchunks: pack_lookup pack_names oid_fanout oid_lookup object_offsets\n+\tpack_names:\n+\t$(ls $3 | grep pack | grep -v idx | sort)\n+\tpack_dir: $3\n+\tEOF\n+}\n+\n test_expect_success 'write-midx from index version 1' \\\n 'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&\n midx1=$(git midx --write) &&\n test_path_is_file ${packdir}/midx-${midx1}.midx &&\n- test_path_is_missing ${packdir}/midx-head'\n+ test_path_is_missing ${packdir}/midx-head &&\n+ _midx_read_expect \\\n+ \"1\" \"102\" \\\n+ \"${packdir}\" &&\n+ git midx --read --midx-id=${midx1} >output &&\n+ cmp output expect'\n \n test_expect_success 'write-midx from index version 2' \\\n 'rm \"${packdir}/test-1-${pack1}.pack\" &&\n@@ -38,12 +54,17 @@ test_expect_success 'write-midx from index version 2' \\\n midx2=$(git midx --write --update-head) &&\n test_path_is_file ${packdir}/midx-${midx2}.midx &&\n test_path_is_file ${packdir}/midx-head &&\n- test $(cat ${packdir}/midx-head) = \"$midx2\"'\n+ test $(cat ${packdir}/midx-head) = \"$midx2\" &&\n+ _midx_read_expect \\\n+ \"1\" \"102\" \\\n+ \"${packdir}\" &&\n+ git midx --read> output &&\n+ cmp output expect'\n \n test_expect_success 'Create more objects' \\\n 'for i in $(test_seq 100)\n do\n- echo $i >file-2-$i\n+ echo extra-$i >file-2-$i\n done &&\n git add file-* &&\n test_tick &&\n@@ -55,28 +76,32 @@ test_expect_success 'write-midx with two packs' \\\n midx3=$(git midx --write --update-head) &&\n test_path_is_file ${packdir}/midx-${midx3}.midx &&\n test_path_is_file ${packdir}/midx-head &&\n- test $(cat ${packdir}/midx-head) = \"$midx3\"'\n+ test $(cat ${packdir}/midx-head) = \"$midx3\" &&\n+ _midx_read_expect \\\n+ \"2\" \"204\" \\\n+\t \"${packdir}\" &&\n+ git midx --read >output &&\n+ cmp output expect'\n \n test_expect_success 'Add more packs' \\\n- 'for j in $(test_seq 10)\n+ 'for i in $(test_seq 10)\n do\n- jjj=$(printf '%03i' $j)\n- test-genrandom \"bar\" 200 > wide_delta_$jjj &&\n- test-genrandom \"baz $jjj\" 50 >> wide_delta_$jjj &&\n- test-genrandom \"foo\"$j 100 > deep_delta_$jjj &&\n- test-genrandom \"foo\"$(expr $j + 1) 100 >> deep_delta_$jjj &&\n- test-genrandom \"foo\"$(expr $j + 2) 100 >> deep_delta_$jjj &&\n- echo $jjj >file_$jjj &&\n- test-genrandom \"$jjj\" 8192 >>file_$jjj &&\n- git update-index --add file_$jjj deep_delta_$jjj wide_delta_$jjj &&\n+ iii=$(printf '%03i' $i)\n+ test-genrandom \"bar\" 200 > wide_delta_$iii &&\n+ test-genrandom \"baz $iii\" 50 >> wide_delta_$iii &&\n+ test-genrandom \"foo\"$i 100 > deep_delta_$iii &&\n+ test-genrandom \"foo\"$(expr $i + 1) 100 >> deep_delta_$iii &&\n+ test-genrandom \"foo\"$(expr $i + 2) 100 >> deep_delta_$iii &&\n+ echo $iii >file_$iii &&\n+ test-genrandom \"$iii\" 8192 >>file_$iii &&\n+ git update-index --add file_$iii deep_delta_$iii wide_delta_$iii &&\n { echo 101 && test-genrandom 100 8192; } >file_101 &&\n git update-index --add file_101 &&\n- commit=$(git commit-tree $EMPTY_TREE -p HEADobj-list &&\n- echo commit_packs_$j = $commit &&\n-\t git branch commit_packs_$j $commit &&\n git update-ref HEAD $commit &&\n git pack-objects --index-version=2 ${packdir}/test-pack output &&\n+ cmp output expect'\n \n test_expect_success 'write-midx with no new packs' \\\n 'midx5=$(git midx --write --update-head) &&\n@@ -100,12 +130,17 @@ test_expect_success 'create bare repo' \\\n cd bare &&\n git config core.midx true &&\n git config pack.threads 1 &&\n- baredir=objects/pack'\n+ baredir=./objects/pack'\n \n test_expect_success 'write-midx in bare repo' \\\n 'midxbare=$(git midx --write --update-head) &&\n test_path_is_file ${baredir}/midx-${midxbare}.midx &&\n test_path_is_file ${baredir}/midx-head &&\n- test $(cat ${baredir}/midx-head) = \"$midxbare\"'\n+ test $(cat ${baredir}/midx-head) = \"$midxbare\" &&\n+ _midx_read_expect \\\n+ \"12\" \"245\" \\\n+ \"${baredir}\" &&\n+ git midx --read >output &&\n+ cmp output expect'\n \n test_done\n-- \n2.15.0\n\n"},{"id":"336099","messageId":"20180107181459.222909-15-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 14/18] midx: load midx files when loading packs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:55Z","receivedAt":"2018-01-07T18:15:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Replace prepare_packed_git() with prepare_packed_git_internal(use_midx) to\nallow some consumers of prepare_packed_git() with a way to load MIDX files.\nConsumers should only use the new method if they are prepared to use the\nmidxed_git struct alongside the packed_git struct.\n\nIf a packfile is found that is not referenced by the current MIDX, then add\nit to the packed_git struct. This is important to keep the MIDX useful after\nadding packs due to \"fetch\" commands and when third-party tools (such as\nlibgit2) add packs directly to the repo.\n\nIf prepare_packed_git_internal is called with use_midx = 0, then unload the\nMIDX file and reload the packfiles in to the packed_git struct.\n\nSigned-off-by: Derrick Stolee \n---\n midx.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n midx.h | 6 ++++--\n packfile.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++---------\n packfile.h | 1 +\n 4 files changed, 117 insertions(+), 11 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex 3ce2b736ea..a66763b9e3 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -22,6 +22,9 @@\n \n #define MIDX_LARGE_OFFSET_NEEDED 0x80000000\n \n+/* MIDX-git global storage */\n+struct midxed_git *midxed_git = 0;\n+\n char* get_midx_filename_oid(const char *pack_dir,\n \t\t\t struct object_id *oid)\n {\n@@ -197,6 +200,45 @@ struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid)\n \treturn m;\n }\n \n+static char* get_midx_filename_dir(const char *pack_dir)\n+{\n+\tstruct object_id oid;\n+\tif (!get_midx_head_oid(pack_dir, &oid))\n+\t\treturn 0;\n+\n+\treturn get_midx_filename_oid(pack_dir, &oid);\n+}\n+\n+static int prepare_midxed_git_head(char *pack_dir, int local)\n+{\n+\tstruct midxed_git *m = midxed_git;\n+\tchar *midx_head_path = get_midx_filename_dir(pack_dir);\n+\n+\tif (!core_midx)\n+\t\treturn 1;\n+\n+\tif (midx_head_path) {\n+\t\tmidxed_git = load_midxed_git_one(midx_head_path, pack_dir);\n+\t\tmidxed_git->next = m;\n+\t\tFREE_AND_NULL(midx_head_path);\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+int prepare_midxed_git_objdir(char *obj_dir, int local)\n+{\n+\tint ret;\n+\tstruct strbuf pack_dir = STRBUF_INIT;\n+\tstrbuf_addstr(&pack_dir, obj_dir);\n+\tstrbuf_add(&pack_dir, \"/pack\", 5);\n+\n+\tret = prepare_midxed_git_head(pack_dir.buf, local);\n+\tstrbuf_release(&pack_dir);\n+\treturn ret;\n+}\n+\n struct pack_midx_details_internal {\n \tuint32_t pack_int_id;\n \tuint32_t internal_offset;\n@@ -677,3 +719,18 @@ int close_midx(struct midxed_git *m)\n \n \treturn 1;\n }\n+\n+void close_all_midx(void)\n+{\n+\tstruct midxed_git *m = midxed_git;\n+\tstruct midxed_git *next;\n+\n+\twhile (m) {\n+\t\tnext = m->next;\n+\t\tclose_midx(m);\n+\t\tfree(m);\n+\t\tm = next;\n+\t}\n+\n+\tmidxed_git = 0;\n+}\ndiff --git a/midx.h b/midx.h\nindex 27d48163e9..d8ede8121c 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -27,7 +27,7 @@ struct pack_midx_header {\n \tuint32_t num_packs;\n };\n \n-struct midxed_git {\n+extern struct midxed_git {\n \tstruct midxed_git *next;\n \n \tint midx_fd;\n@@ -81,9 +81,10 @@ struct midxed_git {\n \n \t/* something like \".git/objects/pack\" */\n \tchar pack_dir[FLEX_ARRAY]; /* more */\n-};\n+} *midxed_git;\n \n extern struct midxed_git *get_midxed_git(const char *pack_dir, struct object_id *oid);\n+extern int prepare_midxed_git_objdir(char *obj_dir, int local);\n \n struct pack_midx_details {\n \tuint32_t pack_int_id;\n@@ -118,5 +119,6 @@ extern const char *write_midx_file(const char *pack_dir,\n \t\t\t\t uint32_t nr_objects);\n \n extern int close_midx(struct midxed_git *m);\n+extern void close_all_midx(void);\n \n #endif\ndiff --git a/packfile.c b/packfile.c\nindex c36420b33f..1c0822878b 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -8,6 +8,7 @@\n #include \"list.h\"\n #include \"streaming.h\"\n #include \"sha1-lookup.h\"\n+#include \"midx.h\"\n \n char *odb_pack_name(struct strbuf *buf,\n \t\t const unsigned char *sha1,\n@@ -309,10 +310,22 @@ void close_pack(struct packed_git *p)\n void close_all_packs(void)\n {\n \tstruct packed_git *p;\n+\tstruct midxed_git *m;\n+\n+\tfor (m = midxed_git; m; m = m->next) {\n+\t\tint i;\n+\t\tfor (i = 0; i < m->num_packs; i++) {\n+\t\t\tp = m->packs[i];\n+\t\t\tif (p && p->do_not_close)\n+\t\t\t\tBUG(\"want to close pack marked 'do-not-close'\");\n+\t\t\telse if (p)\n+\t\t\t\tclose_pack(p);\n+\t\t}\n+\t}\n \n \tfor (p = packed_git; p; p = p->next)\n \t\tif (p->do_not_close)\n-\t\t\tdie(\"BUG: want to close pack marked 'do-not-close'\");\n+\t\t\tBUG(\"want to close pack marked 'do-not-close'\");\n \t\telse\n \t\t\tclose_pack(p);\n }\n@@ -748,6 +761,7 @@ static void prepare_packed_git_one(char *objdir, int local)\n \tdirnamelen = path.len;\n \twhile ((de = readdir(dir)) != NULL) {\n \t\tstruct packed_git *p;\n+\t\tstruct midxed_git *m;\n \t\tsize_t base_len;\n \n \t\tif (is_dot_or_dotdot(de->d_name))\n@@ -758,15 +772,23 @@ static void prepare_packed_git_one(char *objdir, int local)\n \n \t\tbase_len = path.len;\n \t\tif (strip_suffix_mem(path.buf, &base_len, \".idx\")) {\n+\t\t\tstrbuf_setlen(&path, base_len + 1);\n+\t\t\tstrbuf_add(&path, \"pack\", 4);\n+\n \t\t\t/* Don't reopen a pack we already have. */\n+\t\t\tfor (m = midxed_git; m; m = m->next)\n+\t\t\t\tif (!memcmp(m->pack_dir, path.buf, dirnamelen - 1) &&\n+\t\t\t\t contains_pack(m, path.buf + dirnamelen))\n+\t\t\t\t\tbreak;\n \t\t\tfor (p = packed_git; p; p = p->next) {\n-\t\t\t\tsize_t len;\n-\t\t\t\tif (strip_suffix(p->pack_name, \".pack\", &len) &&\n-\t\t\t\t len == base_len &&\n-\t\t\t\t !memcmp(p->pack_name, path.buf, len))\n+\t\t\t\tif (!strcmp(p->pack_name, path.buf))\n \t\t\t\t\tbreak;\n \t\t\t}\n-\t\t\tif (p == NULL &&\n+\n+\t\t\tstrbuf_setlen(&path, base_len + 1);\n+\t\t\tstrbuf_add(&path, \"idx\", 3);\n+\n+\t\t\tif (m == NULL && p == NULL &&\n \t\t\t /*\n \t\t\t * See if it really is a valid .idx file with\n \t\t\t * corresponding .pack file that we can map.\n@@ -872,21 +894,45 @@ static void prepare_packed_git_mru(void)\n }\n \n static int prepare_packed_git_run_once = 0;\n-void prepare_packed_git(void)\n+static int prepare_midxed_git_run_once = 0;\n+void prepare_packed_git_internal(int use_midx)\n {\n \tstruct alternate_object_database *alt;\n+\tchar *obj_dir;\n+\n+\tif (prepare_midxed_git_run_once) {\n+\t\tif (!use_midx) {\n+\t\t\tprepare_midxed_git_run_once = 0;\n+\t\t\tclose_all_midx();\n+\t\t\treprepare_packed_git();\n+\t\t}\n+\t\treturn;\n+\t}\n \n \tif (prepare_packed_git_run_once)\n \t\treturn;\n-\tprepare_packed_git_one(get_object_directory(), 1);\n+\n+\tobj_dir = get_object_directory();\n+\n+\tif (use_midx)\n+\t\tprepare_midxed_git_objdir(obj_dir, 1);\n+\tprepare_packed_git_one(obj_dir, 1);\n \tprepare_alt_odb();\n-\tfor (alt = alt_odb_list; alt; alt = alt->next)\n+\tfor (alt = alt_odb_list; alt; alt = alt->next) {\n+\t\tif (use_midx)\n+\t\t\tprepare_midxed_git_objdir(alt->path, 0);\n \t\tprepare_packed_git_one(alt->path, 0);\n+\t}\n \trearrange_packed_git();\n \tprepare_packed_git_mru();\n \tprepare_packed_git_run_once = 1;\n+\tprepare_midxed_git_run_once = use_midx;\n }\n \n+void prepare_packed_git(void)\n+{\n+\tprepare_packed_git_internal(0);\n+}\n void reprepare_packed_git(void)\n {\n \tapproximate_object_count_valid = 0;\ndiff --git a/packfile.h b/packfile.h\nindex 7cf4771029..25bac91efb 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -32,6 +32,7 @@ extern struct packed_git *parse_pack_index(unsigned char *sha1, const char *idx_\n #define PACKDIR_FILE_GARBAGE 4\n extern void (*report_garbage)(unsigned seen_bits, const char *path);\n \n+extern void prepare_packed_git_internal(int use_midx);\n extern void prepare_packed_git(void);\n extern void reprepare_packed_git(void);\n extern void install_packed_git(struct packed_git *pack);\n-- \n2.15.0\n\n"},{"id":"336100","messageId":"20180107181459.222909-11-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 10/18] midx: use existing midx when writing","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:51Z","receivedAt":"2018-01-07T18:15:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"When writing a new MIDX file, it is faster to use an existing MIDX file\nto load the object list and pack offsets and to only inspect pack-indexes\nfor packs not already covered by the MIDX file.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/midx.c | 34 +++++++++++++++++++++++++++++++---\n midx.c | 23 +++++++++++++++++++++++\n midx.h | 2 ++\n 3 files changed, 56 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/midx.c b/builtin/midx.c\nindex ee9234583d..aff2085771 100644\n--- a/builtin/midx.c\n+++ b/builtin/midx.c\n@@ -73,7 +73,7 @@ static int midx_read(void)\n static int build_midx_from_packs(\n \tconst char *pack_dir,\n \tconst char **pack_names, uint32_t nr_packs,\n-\tconst char **midx_id)\n+\tconst char **midx_id, struct midxed_git *midx)\n {\n \tstruct packed_git **packs;\n \tconst char **installed_pack_names;\n@@ -86,6 +86,9 @@ static int build_midx_from_packs(\n \tstruct strbuf pack_path = STRBUF_INIT;\n \tint baselen;\n \n+\tif (midx)\n+\t\tnr_total_packs += midx->num_packs;\n+\n \tif (!nr_total_packs) {\n \t\t*midx_id = NULL;\n \t\treturn 0;\n@@ -94,6 +97,12 @@ static int build_midx_from_packs(\n \tALLOC_ARRAY(packs, nr_total_packs);\n \tALLOC_ARRAY(installed_pack_names, nr_total_packs);\n \n+\tif (midx) {\n+\t\tfor (i = 0; i < midx->num_packs; i++)\n+\t\t\tinstalled_pack_names[nr_installed_packs++] = midx->pack_names[i];\n+\t\tpack_offset = midx->num_packs;\n+\t}\n+\n \tstrbuf_addstr(&pack_path, pack_dir);\n \tstrbuf_addch(&pack_path, '/');\n \tbaselen = pack_path.len;\n@@ -101,6 +110,9 @@ static int build_midx_from_packs(\n \t\tstrbuf_setlen(&pack_path, baselen);\n \t\tstrbuf_addstr(&pack_path, pack_names[i]);\n \n+\t\tif (midx && contains_pack(midx, pack_names[i]))\n+\t\t\tcontinue;\n+\n \t\tstrbuf_strip_suffix(&pack_path, \".pack\");\n \t\tstrbuf_addstr(&pack_path, \".idx\");\n \n@@ -120,13 +132,24 @@ static int build_midx_from_packs(\n \tif (!nr_objects || !nr_installed_packs) {\n \t\tFREE_AND_NULL(packs);\n \t\tFREE_AND_NULL(installed_pack_names);\n-\t\t*midx_id = NULL;\n+\n+\t\tif (opts.has_existing)\n+\t\t\t*midx_id = oid_to_hex(&opts.old_midx_oid);\n+\t\telse\n+\t\t\t*midx_id = NULL;\n+\n \t\treturn 0;\n \t}\n \n+\tif (midx)\n+\t\tnr_objects += midx->num_objects;\n+\n \tALLOC_ARRAY(objects, nr_objects);\n \tnr_objects = 0;\n \n+\tfor (i = 0; midx && i < midx->num_objects; i++)\n+\t\tnth_midxed_object_entry(midx, i, &objects[nr_objects++]);\n+\n \tfor (i = pack_offset; i < nr_installed_packs; i++) {\n \t\tstruct packed_git *p = packs[i];\n \n@@ -184,6 +207,10 @@ static int midx_write(void)\n \tconst char *midx_id = 0;\n \tDIR *dir;\n \tstruct dirent *de;\n+\tstruct midxed_git *midx = NULL;\n+\n+\tif (opts.has_existing)\n+\t\tmidx = get_midxed_git(opts.pack_dir, &opts.old_midx_oid);\n \n \tdir = opendir(opts.pack_dir);\n \tif (!dir) {\n@@ -212,7 +239,8 @@ static int midx_write(void)\n \tif (!nr_packs)\n \t\tgoto cleanup;\n \n-\tif (build_midx_from_packs(opts.pack_dir, pack_names, nr_packs, &midx_id))\n+\tif (build_midx_from_packs(opts.pack_dir, pack_names,\n+\t\t\t\t nr_packs, &midx_id, midx))\n \t\tdie(\"failed to build MIDX\");\n \n \tif (midx_id == NULL)\ndiff --git a/midx.c b/midx.c\nindex 4e0df0285a..53eb29dac3 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -257,6 +257,29 @@ const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n \treturn oid;\n }\n \n+int contains_pack(struct midxed_git *m, const char *pack_name)\n+{\n+\tuint32_t first = 0, last = m->num_packs;\n+\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tconst char *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = m->pack_names[mid];\n+\t\tcmp = strcmp(pack_name, current);\n+\t\tif (!cmp)\n+\t\t\treturn 1;\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int midx_sha1_compare(const void *_a, const void *_b)\n {\n \tstruct pack_midx_entry *a = *(struct pack_midx_entry **)_a;\ndiff --git a/midx.h b/midx.h\nindex 9255909ae8..1e7a94651c 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -100,6 +100,8 @@ extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n \t\t\t\t\t\t struct midxed_git *m,\n \t\t\t\t\t\t uint32_t n);\n \n+extern int contains_pack(struct midxed_git *m, const char *pack_name);\n+\n /*\n * Write a single MIDX file storing the given entries for the\n * given list of packfiles. If midx_name is null, then a temp\n-- \n2.15.0\n\n"},{"id":"336101","messageId":"20180107181459.222909-17-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 16/18] midx: nth_midxed_object_oid() and bsearch_midx()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:57Z","receivedAt":"2018-01-07T18:15:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Using a binary search, we can navigate to the position n within a\nMIDX file where an object appears in the ordered list of objects.\n\nSigned-off-by: Derrick Stolee \n---\n midx.c | 30 ++++++++++++++++++++++++++++++\n midx.h | 9 +++++++++\n 2 files changed, 39 insertions(+)\n\ndiff --git a/midx.c b/midx.c\nindex a66763b9e3..8c643caa92 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -299,6 +299,36 @@ const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n \treturn oid;\n }\n \n+int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos)\n+{\n+\tuint32_t last, first = 0;\n+\n+\tif (sha1[0])\n+\t\tfirst = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * (sha1[0] - 1)));\n+\tlast = ntohl(*(uint32_t*)(m->chunk_oid_fanout + 4 * sha1[0]));\n+\n+\twhile (first < last) {\n+\t\tuint32_t mid = first + (last - first) / 2;\n+\t\tconst unsigned char *current;\n+\t\tint cmp;\n+\n+\t\tcurrent = m->chunk_oid_lookup + m->hdr->hash_len * mid;\n+\t\tcmp = hashcmp(sha1, current);\n+\t\tif (!cmp) {\n+\t\t\t*pos = mid;\n+\t\t\treturn 1;\n+\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\tfirst = mid + 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = mid;\n+\t}\n+\n+\t*pos = first;\n+\treturn 0;\n+}\n+\n int contains_pack(struct midxed_git *m, const char *pack_name)\n {\n \tuint32_t first = 0, last = m->num_packs;\ndiff --git a/midx.h b/midx.h\nindex d8ede8121c..5598799189 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -101,6 +101,15 @@ extern const struct object_id *nth_midxed_object_oid(struct object_id *oid,\n \t\t\t\t\t\t struct midxed_git *m,\n \t\t\t\t\t\t uint32_t n);\n \n+/*\n+ * Perform a binary search on the object list in a MIDX file for the given sha1.\n+ *\n+ * If the object exists, then return 1 and set *pos to the position of the sha1.\n+ * Otherwise, return 0 and set *pos to the position of the lex-first object greater\n+ * than the given sha1.\n+ */\n+extern int bsearch_midx(struct midxed_git *m, const unsigned char *sha1, uint32_t *pos);\n+\n extern int contains_pack(struct midxed_git *m, const char *pack_name);\n \n /*\n-- \n2.15.0\n\n"},{"id":"336102","messageId":"20180107181459.222909-4-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 03/18] midx: create core.midx config setting","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:44Z","receivedAt":"2018-01-07T18:15:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"As the multi-pack-index feature is being developed, we use a config\nsetting 'core.midx' to enable all use of MIDX files.\n\nSince MIDX files are designed as a way to augment the existing data\nstores in Git, turning this setting off will revert to previous\nbehavior without needing to downgrade. This can also be a repo-\nspecific setting if the MIDX is misbehaving in only one repo.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/config.txt | 3 +++\n cache.h | 1 +\n config.c | 5 +++++\n environment.c | 2 ++\n 4 files changed, 11 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 64c1dbba94..dc7cb4b900 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -896,6 +896,9 @@ core.notesRef::\n This setting defaults to \"refs/notes/commits\", and it can be overridden by\n the `GIT_NOTES_REF` environment variable. See linkgit:git-notes[1].\n \n+core.midx::\n+\tEnable \"multi-pack-index\" feature. Set to true to read and write MIDX files.\n+\n core.sparseCheckout::\n \tEnable \"sparse checkout\" feature. See section \"Sparse checkout\" in\n \tlinkgit:git-read-tree[1] for more information.\ndiff --git a/cache.h b/cache.h\nindex a2ec8c0b55..f4943d3136 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -820,6 +820,7 @@ extern int precomposed_unicode;\n extern int protect_hfs;\n extern int protect_ntfs;\n extern const char *core_fsmonitor;\n+extern int core_midx;\n \n /*\n * Include broken refs in all ref iterations, which will\ndiff --git a/config.c b/config.c\nindex e617c2018d..17f560ddc4 100644\n--- a/config.c\n+++ b/config.c\n@@ -1223,6 +1223,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.midx\")) {\n+\t\tcore_midx = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.sparsecheckout\")) {\n \t\tcore_apply_sparse_checkout = git_config_bool(var, value);\n \t\treturn 0;\ndiff --git a/environment.c b/environment.c\nindex 63ac38a46f..57a3943849 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -78,6 +78,8 @@ int protect_hfs = PROTECT_HFS_DEFAULT;\n int protect_ntfs = PROTECT_NTFS_DEFAULT;\n const char *core_fsmonitor;\n \n+int core_midx;\n+\n /*\n * The character that begins a commented line in user-editable file\n * that is subject to stripspace.\n-- \n2.15.0\n\n"},{"id":"336103","messageId":"20180107181459.222909-8-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 07/18] midx: teach midx --write to update midx-head","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:48Z","receivedAt":"2018-01-07T18:15:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"There may be multiple MIDX files in a single pack directory. The primary\nfile is pointed to by a pointer file \"midx-head\" that contains an OID.\nThe MIDX file to load is then given by \"midx-.midx\".\n\nThis head file will be especially important when the MIDX files are\nextended to be incremental and we expect multiple MIDX files at any\npoint.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-midx.txt | 19 ++++++++++++++++++-\n builtin/midx.c | 32 ++++++++++++++++++++++++++++++--\n midx.c | 31 +++++++++++++++++++++++++++++++\n midx.h | 3 +++\n t/t5318-midx.sh | 33 ++++++++++++++++++++++-----------\n 5 files changed, 104 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/git-midx.txt b/Documentation/git-midx.txt\nindex 17464222c1..01f79cbba5 100644\n--- a/Documentation/git-midx.txt\n+++ b/Documentation/git-midx.txt\n@@ -9,7 +9,7 @@ git-midx - Write and verify multi-pack-indexes (MIDX files).\n SYNOPSIS\n --------\n [verse]\n-'git midx' --write [--pack-dir ]\n+'git midx' --write [--pack-dir ]\n \n DESCRIPTION\n -----------\n@@ -26,15 +26,32 @@ OPTIONS\n \tIf specified, write a new midx file to the pack directory using\n \tthe packfiles present. Outputs the hash of the result midx file.\n \n+--update-head::\n+\tIf specified with --write, update the midx-head file to point to\n+\tthe written midx file.\n+\n EXAMPLES\n --------\n \n+* Read the midx-head file and output the OID of the head MIDX file.\n++\n+------------------------------------------------\n+$ git midx\n+------------------------------------------------\n+\n * Write a MIDX file for the packfiles in your local .git folder.\n +\n ------------------------------------------------\n $ git midx --write\n ------------------------------------------------\n \n+* Write a MIDX file for the packfiles in your local .git folder and\n+* update the midx-head file.\n++\n+------------------------------------------------\n+$ git midx --write --update-head\n+------------------------------------------------\n+\n * Write a MIDX file for the packfiles in a different folder\n +\n ---------------------------------------------------------\ndiff --git a/builtin/midx.c b/builtin/midx.c\nindex 4aae14cf8e..84ce6588a2 100644\n--- a/builtin/midx.c\n+++ b/builtin/midx.c\n@@ -9,13 +9,17 @@\n #include \"midx.h\"\n \n static char const * const builtin_midx_usage[] = {\n-\tN_(\"git midx --write [--pack-dir ]\"),\n+\tN_(\"git midx [--pack-dir ]\"),\n+\tN_(\"git midx --write [--update-head] [--pack-dir ]\"),\n \tNULL\n };\n \n static struct opts_midx {\n \tconst char *pack_dir;\n \tint write;\n+\tint update_head;\n+\tint has_existing;\n+\tstruct object_id old_midx_oid;\n } opts;\n \n static int build_midx_from_packs(\n@@ -109,6 +113,22 @@ static int build_midx_from_packs(\n \treturn 0;\n }\n \n+static void update_head_file(const char *pack_dir, const char *midx_id)\n+{\n+\tint fd;\n+\tstruct lock_file lk = LOCK_INIT;\n+\tchar *head_path = get_midx_head_filename(pack_dir);\n+\n+\tfd = hold_lock_file_for_update(&lk, head_path, LOCK_DIE_ON_ERROR);\n+\tFREE_AND_NULL(head_path);\n+\n+\tif (fd < 0)\n+\t\tdie_errno(\"unable to open midx-head\");\n+\n+\twrite_in_full(fd, midx_id, GIT_MAX_HEXSZ);\n+\tcommit_lock_file(&lk);\n+}\n+\n static int midx_write(void)\n {\n \tconst char **pack_names = NULL;\n@@ -152,6 +172,9 @@ static int midx_write(void)\n \n \tprintf(\"%s\\n\", midx_id);\n \n+\tif (opts.update_head)\n+\t\tupdate_head_file(opts.pack_dir, midx_id);\n+\n cleanup:\n \tif (pack_names)\n \t\tFREE_AND_NULL(pack_names);\n@@ -166,6 +189,8 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\t\tN_(\"The pack directory containing set of packfile and pack-index pairs.\") },\n \t\tOPT_BOOL('w', \"write\", &opts.write,\n \t\t\tN_(\"write midx file\")),\n+\t\tOPT_BOOL('u', \"update-head\", &opts.update_head,\n+\t\t\tN_(\"update midx-head to written midx file\")),\n \t\tOPT_END(),\n \t};\n \n@@ -187,9 +212,12 @@ int cmd_midx(int argc, const char **argv, const char *prefix)\n \t\topts.pack_dir = strbuf_detach(&path, NULL);\n \t}\n \n+\topts.has_existing = !!get_midx_head_oid(opts.pack_dir, &opts.old_midx_oid);\n+\n \tif (opts.write)\n \t\treturn midx_write();\n \n-\tusage_with_options(builtin_midx_usage, builtin_midx_options);\n+\tif (opts.has_existing)\n+\t\tprintf(\"%s\\n\", oid_to_hex(&opts.old_midx_oid));\n \treturn 0;\n }\ndiff --git a/midx.c b/midx.c\nindex 5c320726ed..f4178c1b81 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -34,6 +34,37 @@ char* get_midx_filename_oid(const char *pack_dir,\n \treturn strbuf_detach(&head_path, NULL);\n }\n \n+char *get_midx_head_filename(const char *pack_dir)\n+{\n+\tstruct strbuf head_filename = STRBUF_INIT;\n+\tstrbuf_addstr(&head_filename, pack_dir);\n+\tstrbuf_addstr(&head_filename, \"/midx-head\");\n+\treturn strbuf_detach(&head_filename, NULL);\n+}\n+\n+struct object_id *get_midx_head_oid(const char *pack_dir,\n+\t\t\t\t struct object_id *oid)\n+{\n+\tchar oid_hex[GIT_MAX_HEXSZ + 1];\n+\tFILE *f;\n+\tchar *head_filename = get_midx_head_filename(pack_dir);\n+\n+\tf = fopen(head_filename, \"r\");\n+\tFREE_AND_NULL(head_filename);\n+\n+\tif (!f)\n+\t\treturn 0;\n+\n+\tif (!fgets(oid_hex, sizeof(oid_hex), f))\n+\t\tdie(\"failed to read midx-head\");\n+\n+\tfclose(f);\n+\n+\tif (get_oid_hex(oid_hex, oid))\n+\t\treturn 0;\n+\treturn oid;\n+}\n+\n struct pack_midx_details_internal {\n \tuint32_t pack_int_id;\n \tuint32_t internal_offset;\ndiff --git a/midx.h b/midx.h\nindex 4b00463651..9d9ab85261 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -7,6 +7,9 @@\n \n extern char *get_midx_filename_oid(const char *pack_dir,\n \t\t\t\t struct object_id *oid);\n+extern char *get_midx_head_filename(const char *pack_dir);\n+\n+extern struct object_id *get_midx_head_oid(const char *pack_dir, struct object_id *oid);\n \n struct pack_midx_entry {\n \tstruct object_id oid;\ndiff --git a/t/t5318-midx.sh b/t/t5318-midx.sh\nindex 869bbea29c..b66efcdce9 100755\n--- a/t/t5318-midx.sh\n+++ b/t/t5318-midx.sh\n@@ -29,13 +29,16 @@ test_expect_success 'create objects' \\\n test_expect_success 'write-midx from index version 1' \\\n 'pack1=$(git rev-list --all --objects | git pack-objects --index-version=1 ${packdir}/test-1) &&\n midx1=$(git midx --write) &&\n- test_path_is_file ${packdir}/midx-${midx1}.midx'\n+ test_path_is_file ${packdir}/midx-${midx1}.midx &&\n+ test_path_is_missing ${packdir}/midx-head'\n \n test_expect_success 'write-midx from index version 2' \\\n 'rm \"${packdir}/test-1-${pack1}.pack\" &&\n pack2=$(git rev-list --all --objects | git pack-objects --index-version=2 ${packdir}/test-2) &&\n- midx2=$(git midx --write) &&\n- test_path_is_file ${packdir}/midx-${midx2}.midx'\n+ midx2=$(git midx --write --update-head) &&\n+ test_path_is_file ${packdir}/midx-${midx2}.midx &&\n+ test_path_is_file ${packdir}/midx-head &&\n+ test $(cat ${packdir}/midx-head) = \"$midx2\"'\n \n test_expect_success 'Create more objects' \\\n 'for i in $(test_seq 100)\n@@ -49,8 +52,10 @@ test_expect_success 'Create more objects' \\\n \n test_expect_success 'write-midx with two packs' \\\n 'pack3=$(git rev-list --objects commit2 ^commit1 | git pack-objects --index-version=2 ${packdir}/test-3) &&\n- midx3=$(git midx --write) &&\n- test_path_is_file ${packdir}/midx-${midx3}.midx'\n+ midx3=$(git midx --write --update-head) &&\n+ test_path_is_file ${packdir}/midx-${midx3}.midx &&\n+ test_path_is_file ${packdir}/midx-head &&\n+ test $(cat ${packdir}/midx-head) = \"$midx3\"'\n \n test_expect_success 'Add more packs' \\\n 'for j in $(test_seq 10)\n@@ -77,13 +82,17 @@ test_expect_success 'Add more packs' \\\n done'\n \n test_expect_success 'write-midx with twelve packs' \\\n- 'midx4=$(git midx --write) &&\n- test_path_is_file ${packdir}/midx-${midx4}.midx'\n+ 'midx4=$(git midx --write --update-head) &&\n+ test_path_is_file ${packdir}/midx-${midx4}.midx &&\n+ test_path_is_file ${packdir}/midx-head &&\n+ test $(cat ${packdir}/midx-head) = \"$midx4\"'\n \n test_expect_success 'write-midx with no new packs' \\\n- 'midx5=$(git midx --write) &&\n+ 'midx5=$(git midx --write --update-head) &&\n test_path_is_file ${packdir}/midx-${midx5}.midx &&\n- test \"a$midx4\" = \"a$midx5\"'\n+ test \"a$midx4\" = \"a$midx5\" &&\n+ test_path_is_file ${packdir}/midx-head &&\n+ test $(cat ${packdir}/midx-head) = \"$midx4\"'\n \n test_expect_success 'create bare repo' \\\n 'cd .. &&\n@@ -94,7 +103,9 @@ test_expect_success 'create bare repo' \\\n baredir=objects/pack'\n \n test_expect_success 'write-midx in bare repo' \\\n- 'midxbare=$(git midx --write) &&\n- test_path_is_file ${baredir}/midx-${midxbare}.midx'\n+ 'midxbare=$(git midx --write --update-head) &&\n+ test_path_is_file ${baredir}/midx-${midxbare}.midx &&\n+ test_path_is_file ${baredir}/midx-head &&\n+ test $(cat ${baredir}/midx-head) = \"$midxbare\"'\n \n test_done\n-- \n2.15.0\n\n"},{"id":"336104","messageId":"20180107181459.222909-5-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 04/18] midx: write multi-pack indexes for an object list","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:45Z","receivedAt":"2018-01-07T18:15:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The write_midx_file() method takes a list of packfiles and indexed\nobjects with offset information and writes according to the format\nin Documentation/technical/pack-format.txt. The chunks are separated\ninto methods.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n midx.c | 412 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n midx.h | 42 +++++++\n 3 files changed, 455 insertions(+)\n create mode 100644 midx.c\n create mode 100644 midx.h\n\ndiff --git a/Makefile b/Makefile\nindex 2a81ae22e9..d0d810951f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -827,6 +827,7 @@ LIB_OBJS += merge.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += midx.o\n LIB_OBJS += mru.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\ndiff --git a/midx.c b/midx.c\nnew file mode 100644\nindex 0000000000..5c320726ed\n--- /dev/null\n+++ b/midx.c\n@@ -0,0 +1,412 @@\n+#include \"cache.h\"\n+#include \"git-compat-util.h\"\n+#include \"pack.h\"\n+#include \"packfile.h\"\n+#include \"midx.h\"\n+\n+#define MIDX_SIGNATURE 0x4d494458 /* \"MIDX\" */\n+#define MIDX_CHUNKID_PACKLOOKUP 0x504c4f4f /* \"PLOO\" */\n+#define MIDX_CHUNKID_PACKNAMES 0x504e414d /* \"PNAM\" */\n+#define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* \"OIDF\" */\n+#define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* \"OIDL\" */\n+#define MIDX_CHUNKID_OBJECTOFFSETS 0x4f4f4646 /* \"OOFF\" */\n+#define MIDX_CHUNKID_LARGEOFFSETS 0x4c4f4646 /* \"LOFF\" */\n+\n+#define MIDX_VERSION_1 1\n+#define MIDX_VERSION MIDX_VERSION_1\n+\n+#define MIDX_OID_VERSION_SHA1 1\n+#define MIDX_OID_LEN_SHA1 20\n+#define MIDX_OID_VERSION MIDX_OID_VERSION_SHA1\n+#define MIDX_OID_LEN MIDX_OID_LEN_SHA1\n+\n+#define MIDX_LARGE_OFFSET_NEEDED 0x80000000\n+\n+char* get_midx_filename_oid(const char *pack_dir,\n+\t\t\t struct object_id *oid)\n+{\n+\tstruct strbuf head_path = STRBUF_INIT;\n+\tstrbuf_addstr(&head_path, pack_dir);\n+\tstrbuf_addstr(&head_path, \"/midx-\");\n+\tstrbuf_addstr(&head_path, oid_to_hex(oid));\n+\tstrbuf_addstr(&head_path, \".midx\");\n+\n+\treturn strbuf_detach(&head_path, NULL);\n+}\n+\n+struct pack_midx_details_internal {\n+\tuint32_t pack_int_id;\n+\tuint32_t internal_offset;\n+};\n+\n+static int midx_sha1_compare(const void *_a, const void *_b)\n+{\n+\tstruct pack_midx_entry *a = *(struct pack_midx_entry **)_a;\n+\tstruct pack_midx_entry *b = *(struct pack_midx_entry **)_b;\n+\treturn oidcmp(&a->oid, &b->oid);\n+}\n+\n+static void write_midx_chunk_packlookup(\n+\tstruct sha1file *f,\n+\tconst char **pack_names, uint32_t nr_packs)\n+{\n+\tuint32_t i, cur_len = 0;\n+\n+\tfor (i = 0; i < nr_packs; i++) {\n+\t\tuint32_t swap_len = htonl(cur_len);\n+\t\tsha1write(f, &swap_len, 4);\n+\t\tcur_len += strlen(pack_names[i]) + 1;\n+\t}\n+}\n+\n+static void write_midx_chunk_packnames(\n+\tstruct sha1file *f,\n+\tconst char **pack_names, uint32_t nr_packs)\n+{\n+\tuint32_t i;\n+\tfor (i = 0; i < nr_packs; i++)\n+\t\tsha1write(f, pack_names[i], strlen(pack_names[i]) + 1);\n+}\n+\n+static void write_midx_chunk_oidfanout(\n+\tstruct sha1file *f,\n+\tstruct pack_midx_entry **objects, uint32_t nr_objects)\n+{\n+\tstruct pack_midx_entry **list = objects;\n+\tstruct pack_midx_entry **last = objects + nr_objects;\n+\tuint32_t count_distinct = 0;\n+\tuint32_t i;\n+\n+\t/*\n+\t* Write the first-level table (the list is sorted,\n+\t* but we use a 256-entry lookup to be able to avoid\n+\t* having to do eight extra binary search iterations).\n+\t*/\n+\tfor (i = 0; i < 256; i++) {\n+\t\tstruct pack_midx_entry **next = list;\n+\t\tstruct pack_midx_entry *prev = 0;\n+\t\tuint32_t swap_distinct;\n+\n+\t\twhile (next < last) {\n+\t\t\tstruct pack_midx_entry *obj = *next;\n+\t\t\tif (obj->oid.hash[0] != i)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (!prev || oidcmp(&(prev->oid), &(obj->oid)))\n+\t\t\t\tcount_distinct++;\n+\n+\t\t\tprev = obj;\n+\t\t\tnext++;\n+\t\t}\n+\n+\t\tswap_distinct = htonl(count_distinct);\n+\t\tsha1write(f, &swap_distinct, 4);\n+\t\tlist = next;\n+\t}\n+}\n+\n+static void write_midx_chunk_oidlookup(\n+\tstruct sha1file *f, unsigned char hash_len,\n+\tstruct pack_midx_entry **objects, uint32_t nr_objects)\n+{\n+\tstruct pack_midx_entry **list = objects;\n+\tstruct object_id *last_oid = 0;\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tstruct pack_midx_entry *obj = *list++;\n+\n+\t\tif (last_oid && !oidcmp(last_oid, &obj->oid))\n+\t\t\tcontinue;\n+\n+\t\tlast_oid = &obj->oid;\n+\t\tsha1write(f, obj->oid.hash, (int)hash_len);\n+\t}\n+}\n+\n+static void write_midx_chunk_objectoffsets(\n+\tstruct sha1file *f, int large_offset_needed,\n+\tstruct pack_midx_entry **objects, uint32_t nr_objects, uint32_t *pack_perm)\n+{\n+\tstruct pack_midx_entry **list = objects;\n+\tstruct object_id *last_oid = 0;\n+\tuint32_t i, nr_large_offset = 0;\n+\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tstruct pack_midx_details_internal details;\n+\t\tstruct pack_midx_entry *obj = *list++;\n+\n+\t\tif (last_oid && !oidcmp(last_oid, &obj->oid))\n+\t\t\tcontinue;\n+\n+\t\tlast_oid = &obj->oid;\n+\n+\t\tdetails.pack_int_id = htonl(pack_perm[obj->pack_int_id]);\n+\n+\t\tif (large_offset_needed && obj->offset >> 31)\n+\t\t\tdetails.internal_offset = (MIDX_LARGE_OFFSET_NEEDED | nr_large_offset++);\n+\t\telse\n+\t\t\tdetails.internal_offset = (uint32_t)obj->offset;\n+\n+\t\tdetails.internal_offset = htonl(details.internal_offset);\n+\t\tsha1write(f, &details, 8);\n+\t}\n+}\n+\n+static void write_midx_chunk_largeoffsets(\n+\tstruct sha1file *f, uint32_t nr_large_offset,\n+\tstruct pack_midx_entry **objects, uint32_t nr_objects)\n+{\n+\tstruct pack_midx_entry **list = objects;\n+\tstruct object_id *last_oid = 0;\n+\n+\twhile (nr_large_offset) {\n+\t\tstruct pack_midx_entry *obj = *list++;\n+\t\tuint64_t offset = obj->offset;\n+\t\tuint32_t split[2];\n+\n+\t\tif (last_oid && !oidcmp(last_oid, &obj->oid))\n+\t\t\tcontinue;\n+\n+\t\tlast_oid = &obj->oid;\n+\n+\t\tif (!(offset >> 31))\n+\t\t\tcontinue;\n+\n+\t\tsplit[0] = htonl(offset >> 32);\n+\t\tsplit[1] = htonl(offset & 0xffffffff);\n+\n+\t\tsha1write(f, split, 8);\n+\t\tnr_large_offset--;\n+\t}\n+}\n+\n+struct pack_pair {\n+\tuint32_t pack_int_id;\n+\tconst char *pack_name;\n+};\n+\n+static int pack_pair_compare(const void *_a, const void *_b)\n+{\n+\tstruct pack_pair *a = (struct pack_pair *)_a;\n+\tstruct pack_pair *b = (struct pack_pair *)_b;\n+\treturn strcmp(a->pack_name, b->pack_name);\n+}\n+\n+static void sort_packs_by_name(const char **pack_names, uint32_t nr_packs, uint32_t *perm)\n+{\n+\tuint32_t i;\n+\tstruct pack_pair *pairs;\n+\n+\tALLOC_ARRAY(pairs, nr_packs);\n+\n+\tfor (i = 0; i < nr_packs; i++) {\n+\t\tpairs[i].pack_int_id = i;\n+\t\tpairs[i].pack_name = pack_names[i];\n+\t}\n+\n+\tQSORT(pairs, nr_packs, pack_pair_compare);\n+\n+\tfor (i = 0; i < nr_packs; i++) {\n+\t\tpack_names[i] = pairs[i].pack_name;\n+\t\tperm[pairs[i].pack_int_id] = i;\n+\t}\n+}\n+\n+const char *write_midx_file(const char *pack_dir,\n+\t\t\t const char *midx_name,\n+\t\t\t const char **pack_names,\n+\t\t\t uint32_t nr_packs,\n+\t\t\t struct pack_midx_entry **objects,\n+\t\t\t uint32_t nr_objects)\n+{\n+\tstruct sha1file *f;\n+\tstruct pack_midx_entry **sorted_by_sha;\n+\tint i, chunk, fd;\n+\tstruct pack_midx_header hdr;\n+\tuint32_t chunk_ids[7];\n+\tuint64_t chunk_offsets[7];\n+\tunsigned char large_offset_needed = 0;\n+\tunsigned int nr_large_offset = 0;\n+\tunsigned char final_hash[GIT_MAX_RAWSZ];\n+\tconst char *final_hex;\n+\tint rename_needed = 0;\n+\tuint32_t count_distinct = 0;\n+\tint total_name_len = 0;\n+\tuint32_t *pack_perm;\n+\n+\tif (!core_midx)\n+\t\treturn 0;\n+\n+\t/* Sort packs */\n+\tif (nr_packs) {\n+\t\tALLOC_ARRAY(pack_perm, nr_packs);\n+\t\tsort_packs_by_name(pack_names, nr_packs, pack_perm);\n+\t} else {\n+\t\tpack_perm = 0;\n+\t}\n+\n+\t/* Sort objects */\n+\tif (nr_objects) {\n+\t\tsorted_by_sha = objects;\n+\n+\t\tQSORT(sorted_by_sha, nr_objects, midx_sha1_compare);\n+\n+\t\tfor (i = 0; i < nr_objects; i++) {\n+\t\t\tif (i &&\n+\t\t\t !oidcmp(&sorted_by_sha[i-1]->oid, &sorted_by_sha[i]->oid))\n+\t\t\t\tcontinue;\n+\n+\t\t\tcount_distinct++;\n+\n+\t\t\tif (sorted_by_sha[i]->offset > 0x7fffffff)\n+\t\t\t\tnr_large_offset++;\n+\t\t\tif (sorted_by_sha[i]->offset > 0xffffffff)\n+\t\t\t\tlarge_offset_needed = 1;\n+\t\t}\n+\t} else {\n+\t\tsorted_by_sha = NULL;\n+\t}\n+\n+\tfor (i = 0; i < nr_packs; i++)\n+\t\ttotal_name_len += strlen(pack_names[i]) + 1;\n+\n+\t/* open temp file, or direct file if given */\n+\tif (!midx_name) {\n+\t\tstruct strbuf tmp_file = STRBUF_INIT;\n+\t\tstrbuf_addstr(&tmp_file, pack_dir);\n+\t\tstrbuf_addstr(&tmp_file, \"/tmp_midx_XXXXXX\");\n+\n+\t\tfd = git_mkstemp_mode(tmp_file.buf, 0444);\n+\t\tif (fd < 0)\n+\t\t\tdie_errno(\"unable to create '%s'\", tmp_file.buf);\n+\n+\t\tmidx_name = strbuf_detach(&tmp_file, NULL);\n+\t\trename_needed = 1;\n+\t} else {\n+\t\tunlink(midx_name);\n+\t\tfd = open(midx_name, O_CREAT|O_EXCL|O_WRONLY, 0600);\n+\t\tif (fd < 0)\n+\t\t\tdie_errno(\"unable to create '%s'\", midx_name);\n+\t}\n+\tf = sha1fd(fd, midx_name);\n+\n+\t/* fill header info */\n+\thdr.midx_signature = htonl(MIDX_SIGNATURE);\n+\thdr.midx_version = htonl(MIDX_VERSION);\n+\n+\thdr.hash_version = MIDX_OID_VERSION;\n+\thdr.hash_len = MIDX_OID_LEN;\n+\thdr.num_base_midx = 0;\n+\thdr.num_packs = htonl(nr_packs);\n+\n+\t/*\n+\t * We expect the following chunks, which are required:\n+\t *\n+\t * Packfile Name Lookup\n+\t * Packfile Names\n+\t * OID Fanout\n+\t * OID Lookup\n+\t * Object Offsets\n+\t */\n+\thdr.num_chunks = large_offset_needed ? 6 : 5;\n+\n+\t/* write header to file */\n+\tassert(sizeof(hdr) == 16);\n+\tsha1write(f, &hdr, sizeof(hdr));\n+\n+\t/*\n+\t * Fill initial chunk values using offsets\n+\t * relative to first chunk.\n+\t */\n+\tchunk_offsets[0] = sizeof(hdr) + 12 * (hdr.num_chunks + 1);\n+\tchunk_ids[0] = MIDX_CHUNKID_PACKLOOKUP;\n+\tchunk_offsets[1] = chunk_offsets[0] + nr_packs * 4;\n+\tchunk_ids[1] = MIDX_CHUNKID_OIDFANOUT;\n+\tchunk_offsets[2] = chunk_offsets[1] + 256 * 4;\n+\tchunk_ids[2] = MIDX_CHUNKID_OIDLOOKUP;\n+\tchunk_offsets[3] = chunk_offsets[2] + (uint64_t)count_distinct\n+\t\t\t\t\t * (uint64_t)hdr.hash_len;\n+\tchunk_ids[3] = MIDX_CHUNKID_OBJECTOFFSETS;\n+\tchunk_offsets[4] = chunk_offsets[3] + 8 * (uint64_t)count_distinct;\n+\n+\tif (large_offset_needed) {\n+\t\tchunk_ids[4] = MIDX_CHUNKID_LARGEOFFSETS;\n+\t\tchunk_offsets[5] = chunk_offsets[4] + 8 * (uint64_t)nr_large_offset;\n+\t\tchunk_ids[5] = MIDX_CHUNKID_PACKNAMES;\n+\t\tchunk_offsets[6] = chunk_offsets[5] + total_name_len;\n+\t\tchunk_ids[6] = 0;\n+\t} else {\n+\t\tchunk_ids[4] = MIDX_CHUNKID_PACKNAMES;\n+\t\tchunk_offsets[5] = chunk_offsets[4] + total_name_len;\n+\t\tchunk_ids[5] = 0;\n+\t}\n+\n+\tfor (i = 0; i <= hdr.num_chunks; i++) {\n+\t\tuint32_t chunk_write[3];\n+\n+\t\tchunk_write[0] = htonl(chunk_ids[i]);\n+\t\tchunk_write[1] = htonl(chunk_offsets[i] >> 32);\n+\t\tchunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);\n+\t\tsha1write(f, chunk_write, 12);\n+\t}\n+\n+\tfor (chunk = 0; chunk < hdr.num_chunks; chunk++) {\n+\t\tswitch (chunk_ids[chunk]) {\n+\t\tcase MIDX_CHUNKID_PACKLOOKUP:\n+\t\t\twrite_midx_chunk_packlookup(f, pack_names, nr_packs);\n+\t\t\tbreak;\n+\n+\t\tcase MIDX_CHUNKID_PACKNAMES:\n+\t\t\twrite_midx_chunk_packnames(f, pack_names, nr_packs);\n+\t\t\tbreak;\n+\n+\t\tcase MIDX_CHUNKID_OIDFANOUT:\n+\t\t\twrite_midx_chunk_oidfanout(f, sorted_by_sha, nr_objects);\n+\t\t\tbreak;\n+\n+\t\tcase MIDX_CHUNKID_OIDLOOKUP:\n+\t\t\twrite_midx_chunk_oidlookup(f, hdr.hash_len, sorted_by_sha,\n+\t\t\t\t\t\t nr_objects);\n+\t\t\tbreak;\n+\n+\t\tcase MIDX_CHUNKID_OBJECTOFFSETS:\n+\t\t\twrite_midx_chunk_objectoffsets(f, large_offset_needed,\n+\t\t\t\t\t\t sorted_by_sha, nr_objects,\n+\t\t\t\t\t\t pack_perm);\n+\t\t\tbreak;\n+\n+\t\tcase MIDX_CHUNKID_LARGEOFFSETS:\n+\t\t\twrite_midx_chunk_largeoffsets(f, nr_large_offset,\n+\t\t\t\t\t\t sorted_by_sha, nr_objects);\n+\t\t\tbreak;\n+\n+\t\tcase 0:\n+\t\t\tbreak;\n+\n+\t\tdefault:\n+\t\t\tdie(\"unrecognized MIDX chunk id: %08x\", chunk_ids[chunk]);\n+\t\t}\n+\t}\n+\n+\tsha1close(f, final_hash, CSUM_CLOSE | CSUM_FSYNC);\n+\n+\tif (rename_needed)\n+\t{\n+\t\tstruct object_id oid;\n+\t\tchar *fname;\n+\n+\t\tmemcpy(oid.hash, final_hash, GIT_MAX_RAWSZ);\n+\t\tfname = get_midx_filename_oid(pack_dir, &oid);\n+\t\tfinal_hex = sha1_to_hex(final_hash);\n+\n+\t\tif (rename(midx_name, fname))\n+\t\t\tdie(\"failed to rename %s to %s\", midx_name, fname);\n+\n+\t\tfree(fname);\n+\t} else {\n+\t\tfinal_hex = midx_name;\n+\t}\n+\n+\treturn final_hex;\n+}\ndiff --git a/midx.h b/midx.h\nnew file mode 100644\nindex 0000000000..4b00463651\n--- /dev/null\n+++ b/midx.h\n@@ -0,0 +1,42 @@\n+#ifndef MIDX_H\n+#define MIDX_H\n+\n+#include \"git-compat-util.h\"\n+#include \"object.h\"\n+#include \"csum-file.h\"\n+\n+extern char *get_midx_filename_oid(const char *pack_dir,\n+\t\t\t\t struct object_id *oid);\n+\n+struct pack_midx_entry {\n+\tstruct object_id oid;\n+\tuint32_t pack_int_id;\n+\toff_t offset;\n+};\n+\n+struct pack_midx_header {\n+\tuint32_t midx_signature;\n+\tuint32_t midx_version;\n+\tunsigned char hash_version;\n+\tunsigned char hash_len;\n+\tunsigned char num_base_midx;\n+\tunsigned char num_chunks;\n+\tuint32_t num_packs;\n+};\n+\n+/*\n+ * Write a single MIDX file storing the given entries for the\n+ * given list of packfiles. If midx_name is null, then a temp\n+ * file will be created and swapped using the result hash value.\n+ * Otherwise, write directly to midx_name.\n+ *\n+ * Returns the final name of the MIDX file within pack_dir.\n+ */\n+extern const char *write_midx_file(const char *pack_dir,\n+\t\t\t\t const char *midx_name,\n+\t\t\t\t const char **pack_names,\n+\t\t\t\t uint32_t nr_packs,\n+\t\t\t\t struct pack_midx_entry **objects,\n+\t\t\t\t uint32_t nr_objects);\n+\n+#endif\n-- \n2.15.0\n\n"},{"id":"336105","messageId":"20180107181459.222909-6-dstolee@microsoft.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"[RFC PATCH 05/18] midx: create midx builtin with --write mode","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-07T18:14:46Z","receivedAt":"2018-01-07T18:16:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Commentary: As we extend the function of the midx builtin, I expand the\nSYNOPSIS row of \"git-midx.txt\" but do not create multiple rows. If this\nbuiltin doesn't change too much, I will rewrite the SYNOPSIS to be multi-\nlined, such as in \"git-branch.txt\".\n\n-- >8 --\n\nCreate, document, and implement the first ability of the midx builtin.\n\nThe --write subcommand creates a multi-pack-index for all indexed\npackfiles within a given pack directory. If none is provided, the\nobjects/pack directory is implied. The arguments allow specifying the\npack directory so we can add MIDX files to alternates.\n\nThe packfiles are expected to be paired with pack-indexes and are\notherwise ignored. This simplifies the implementation and also keeps\ncompatibility with older versions of Git (or changing core.midx to\nfalse).\n\nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-midx.txt | 54 +++++++++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/midx.c | 195 +++++++++++++++++++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n 7 files changed, 254 insertions(+)\n create mode 100644 Documentation/git-midx.txt\n create mode 100644 builtin/midx.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 833ef3b0b7..545e195f2a 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -95,6 +95,7 @@\n /git-merge-subtree\n /git-mergetool\n /git-mergetool--lib\n+/git-midx\n /git-mktag\n /git-mktree\n /git-name-rev\ndiff --git a/Documentation/git-midx.txt b/Documentation/git-midx.txt\nnew file mode 100644\nindex 0000000000..17464222c1\n--- /dev/null\n+++ b/Documentation/git-midx.txt\n@@ -0,0 +1,54 @@\n+git-midx(1)\n+============\n+\n+NAME\n+----\n+git-midx - Write and verify multi-pack-indexes (MIDX files).\n+\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git midx' --write [--pack-dir ]\n+\n+DESCRIPTION\n+-----------\n+Write a MIDX file.\n+\n+OPTIONS\n+-------\n+\n+--pack-dir ::\n+\tUse given directory for the location of packfiles, pack-indexes,\n+\tand MIDX files.\n+\n+--write::\n+\tIf specified, write a new midx file to the pack directory using\n+\tthe packfiles present. Outputs the hash of the result midx file.\n+\n+EXAMPLES\n+--------\n+\n+* Write a MIDX file for the packfiles in your local .git folder.\n++\n+------------------------------------------------\n+$ git midx --write\n+------------------------------------------------\n+\n+* Write a MIDX file for the packfiles in a different folder\n++\n+---------------------------------------------------------\n+$ git midx --write --pack-dir ../../alt/pack/\n+---------------------------------------------------------\n+\n+CONFIGURATION\n+-------------\n+\n+core.midx::\n+\tThe midx command will fail if core.midx is false.\n+\tAlso, the written MIDX files will be ignored by other commands\n+\tunless core.midx is true.\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Makefile b/Makefile\nindex d0d810951f..5c458705c1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -980,6 +980,7 @@ BUILTIN_OBJS += builtin/merge-index.o\n BUILTIN_OBJS += builtin/merge-ours.o\n BUILTIN_OBJS += builtin/merge-recursive.o\n BUILTIN_OBJS += builtin/merge-tree.o\n+BUILTIN_OBJS += builtin/midx.o\n BUILTIN_OBJS += builtin/mktag.o\n BUILTIN_OBJS += builtin/mktree.o\n BUILTIN_OBJS += builtin/mv.o\ndiff --git a/builtin.h b/builtin.h\nindex 42378f3aa4..880383e341 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -188,6 +188,7 @@ extern int cmd_merge_ours(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_file(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_recursive(int argc, const char **argv, const char *prefix);\n extern int cmd_merge_tree(int argc, const char **argv, const char *prefix);\n+extern int cmd_midx(int argc, const char **argv, const char *prefix);\n extern int cmd_mktag(int argc, const char **argv, const char *prefix);\n extern int cmd_mktree(int argc, const char **argv, const char *prefix);\n extern int cmd_mv(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/midx.c b/builtin/midx.c\nnew file mode 100644\nindex 0000000000..4aae14cf8e\n--- /dev/null\n+++ b/builtin/midx.c\n@@ -0,0 +1,195 @@\n+#include \"builtin.h\"\n+#include \"cache.h\"\n+#include \"config.h\"\n+#include \"dir.h\"\n+#include \"git-compat-util.h\"\n+#include \"lockfile.h\"\n+#include \"packfile.h\"\n+#include \"parse-options.h\"\n+#include \"midx.h\"\n+\n+static char const * const builtin_midx_usage[] = {\n+\tN_(\"git midx --write [--pack-dir ]\"),\n+\tNULL\n+};\n+\n+static struct opts_midx {\n+\tconst char *pack_dir;\n+\tint write;\n+} opts;\n+\n+static int build_midx_from_packs(\n+\tconst char *pack_dir,\n+\tconst char **pack_names, uint32_t nr_packs,\n+\tconst char **midx_id)\n+{\n+\tstruct packed_git **packs;\n+\tconst char **installed_pack_names;\n+\tuint32_t i, j, nr_installed_packs = 0;\n+\tuint32_t nr_objects = 0;\n+\tstruct pack_midx_entry *objects;\n+\tstruct pack_midx_entry **obj_ptrs;\n+\tuint32_t nr_total_packs = nr_packs;\n+\tuint32_t pack_offset = 0;\n+\tstruct strbuf pack_path = STRBUF_INIT;\n+\tint baselen;\n+\n+\tif (!nr_total_packs) {\n+\t\t*midx_id = NULL;\n+\t\treturn 0;\n+\t}\n+\n+\tALLOC_ARRAY(packs, nr_total_packs);\n+\tALLOC_ARRAY(installed_pack_names, nr_total_packs);\n+\n+\tstrbuf_addstr(&pack_path, pack_dir);\n+\tstrbuf_addch(&pack_path, '/');\n+\tbaselen = pack_path.len;\n+\tfor (i = 0; i < nr_packs; i++) {\n+\t\tstrbuf_setlen(&pack_path, baselen);\n+\t\tstrbuf_addstr(&pack_path, pack_names[i]);\n+\n+\t\tstrbuf_strip_suffix(&pack_path, \".pack\");\n+\t\tstrbuf_addstr(&pack_path, \".idx\");\n+\n+\t\tpacks[nr_installed_packs] = add_packed_git(pack_path.buf, pack_path.len, 0);\n+\n+\t\tif (packs[nr_installed_packs] != NULL) {\n+\t\t\tif (open_pack_index(packs[nr_installed_packs]))\n+\t\t\t\tcontinue;\n+\n+\t\t\tnr_objects += packs[nr_installed_packs]->num_objects;\n+\t\t\tinstalled_pack_names[nr_installed_packs] = pack_names[i];\n+\t\t\tnr_installed_packs++;\n+\t\t}\n+\t}\n+\tstrbuf_release(&pack_path);\n+\n+\tif (!nr_objects || !nr_installed_packs) {\n+\t\tFREE_AND_NULL(packs);\n+\t\tFREE_AND_NULL(installed_pack_names);\n+\t\t*midx_id = NULL;\n+\t\treturn 0;\n+\t}\n+\n+\tALLOC_ARRAY(objects, nr_objects);\n+\tnr_objects = 0;\n+\n+\tfor (i = pack_offset; i < nr_installed_packs; i++) {\n+\t\tstruct packed_git *p = packs[i];\n+\n+\t\tfor (j = 0; j < p->num_objects; j++) {\n+\t\t\tstruct pack_midx_entry entry;\n+\n+\t\t\tif (!nth_packed_object_oid(&entry.oid, p, j))\n+\t\t\t\tdie(\"unable to get sha1 of object %u in %s\",\n+\t\t\t\t i, p->pack_name);\n+\n+\t\t\tentry.pack_int_id = i;\n+\t\t\tentry.offset = nth_packed_object_offset(p, j);\n+\n+\t\t\tobjects[nr_objects] = entry;\n+\t\t\tnr_objects++;\n+\t\t}\n+\t}\n+\n+\tALLOC_ARRAY(obj_ptrs, nr_objects);\n+\tfor (i = 0; i < nr_objects; i++)\n+\t\tobj_ptrs[i] = &objects[i];\n+\n+\t*midx_id = write_midx_file(pack_dir, NULL,\n+\t\tinstalled_pack_names, nr_installed_packs,\n+\t\tobj_ptrs, nr_objects);\n+\n+\tFREE_AND_NULL(packs);\n+\tFREE_AND_NULL(installed_pack_names);\n+\tFREE_AND_NULL(obj_ptrs);\n+\tFREE_AND_NULL(objects);\n+\n+\treturn 0;\n+}\n+\n+static int midx_write(void)\n+{\n+\tconst char **pack_names = NULL;\n+\tuint32_t i, nr_packs = 0;\n+\tconst char *midx_id = 0;\n+\tDIR *dir;\n+\tstruct dirent *de;\n+\n+\tdir = opendir(opts.pack_dir);\n+\tif (!dir) {\n+\t\terror_errno(\"unable to open object pack directory: %s\",\n+\t\t\t opts.pack_dir);\n+\t\treturn 1;\n+\t}\n+\n+\tnr_packs = 256;\n+\tALLOC_ARRAY(pack_names, nr_packs);\n+\n+\ti = 0;\n+\twhile ((de = readdir(dir)) != NULL) {\n+\t\tif (is_dot_or_dotdot(de->d_name))\n+\t\t\tcontinue;\n+\n+\t\tif (ends_with(de->d_name, \".pack\")) {\n+\t\t\tALLOC_GROW(pack_names, i + 1, nr_packs);\n+\t\t\tpack_names[i++] = xstrdup(de->d_name);\n+\t\t}\n+\t}\n+\n+\tnr_packs = i;\n+\tclosedir(dir);\n+\n+\tif (!nr_packs)\n+\t\tgoto cleanup;\n+\n+\tif (build_midx_from_packs(opts.pack_dir, pack_names, nr_packs, &midx_id))\n+\t\tdie(\"failed to build MIDX\");\n+\n+\tif (midx_id == NULL)\n+\t\tgoto cleanup;\n+\n+\tprintf(\"%s\\n\", midx_id);\n+\n+cleanup:\n+\tif (pack_names)\n+\t\tFREE_AND_NULL(pack_names);\n+\treturn 0;\n+}\n+\n+int cmd_midx(int argc, const char **argv, const char *prefix)\n+{\n+\tstatic struct option builtin_midx_options[] = {\n+\t\t{ OPTION_STRING, 'p', \"pack-dir\", &opts.pack_dir,\n+\t\t\tN_(\"dir\"),\n+\t\t\tN_(\"The pack directory containing set of packfile and pack-index pairs.\") },\n+\t\tOPT_BOOL('w', \"write\", &opts.write,\n+\t\t\tN_(\"write midx file\")),\n+\t\tOPT_END(),\n+\t};\n+\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(builtin_midx_usage, builtin_midx_options);\n+\n+\tgit_config(git_default_config, NULL);\n+\tif (!core_midx)\n+\t\tdie(_(\"git-midx requires core.midx=true\"));\n+\n+\targc = parse_options(argc, argv, prefix,\n+\t\t\t builtin_midx_options,\n+\t\t\t builtin_midx_usage, 0);\n+\n+\tif (!opts.pack_dir) {\n+\t\tstruct strbuf path = STRBUF_INIT;\n+\t\tstrbuf_addstr(&path, get_object_directory());\n+\t\tstrbuf_addstr(&path, \"/pack\");\n+\t\topts.pack_dir = strbuf_detach(&path, NULL);\n+\t}\n+\n+\tif (opts.write)\n+\t\treturn midx_write();\n+\n+\tusage_with_options(builtin_midx_usage, builtin_midx_options);\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex a1fad28fd8..a7b9412182 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -87,6 +87,7 @@ git-merge-index plumbingmanipulators\n git-merge-one-file purehelpers\n git-mergetool ancillarymanipulators\n git-merge-tree ancillaryinterrogators\n+git-midx plumbingmanipulators\n git-mktag plumbingmanipulators\n git-mktree plumbingmanipulators\n git-mv mainporcelain worktree\ndiff --git a/git.c b/git.c\nindex c870b9719c..87fbda8463 100644\n--- a/git.c\n+++ b/git.c\n@@ -431,6 +431,7 @@ static struct cmd_struct commands[] = {\n \t{ \"merge-recursive-theirs\", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },\n \t{ \"merge-subtree\", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE },\n \t{ \"merge-tree\", cmd_merge_tree, RUN_SETUP },\n+\t{ \"midx\", cmd_midx, RUN_SETUP },\n \t{ \"mktag\", cmd_mktag, RUN_SETUP },\n \t{ \"mktree\", cmd_mktree, RUN_SETUP },\n \t{ \"mv\", cmd_mv, RUN_SETUP | NEED_WORK_TREE },\n-- \n2.15.0\n\n"},{"id":"336113","messageId":"87k1wtb8a4.fsf@evledraar.gmail.com","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-07T22:42:27Z","receivedAt":"2018-01-07T22:42:35Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sun, Jan 07 2018, Derrick Stolee jotted:\n\n> git log --oneline --raw --parents\n>\n> Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n> ----------+-------------+------------+--------+----------\n> 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n> 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n> 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n>\n> The last column is the relative difference between the MIDX-enabled repo\n> and the single-pack repo. The goal of the MIDX feature is to present the\n> ODB as if it was fully repacked, so there is still room for improvement.\n>\n> Changing the command to\n>\n> git log --oneline --raw --parents --abbrev=40\n>\n> has no observable difference (sub 1% change in all cases). This is likely\n> due to the repack I used putting commits and trees in a small number of\n> packfiles so the MRU cache workes very well. On more naturally-created\n> lists of packfiles, there can be up to 20% improvement on this command.\n>\n> We are using a version of this patch with an upcoming release of GVFS.\n> This feature is particularly important in that space since GVFS performs\n> a \"prefetch\" step that downloads a pack of commits and trees on a daily\n> basis. These packfiles are placed in an alternate that is shared by all\n> enlistments. Some users have 150+ packfiles and the MRU misses and\n> abbreviation computations are significant. Now, GVFS manages the MIDX file\n> after adding new prefetch packfiles using the following command:\n>\n> git midx --write --update-head --delete-expired --pack-dir=\n\n(Not a critique of this, just a (stupid) question)\n\nWhat's the practical use-case for this feature? Since it doesn't help\nwith --abbrev=40 the speedup is all in the part that ensures we don't\nshow an ambiguous SHA-1.\n\nThe reason we do that at all is because it makes for a prettier UI.\n\nAre there things that both want the pretty SHA-1 and also care about the\nthroughput? I'd have expected machine parsing to just use\n--no-abbrev-commit.\n\nIf something cares about both throughput and e.g. is saving the\nabbreviated SHA-1s isn't it better off picking some arbitrary size\n(e.g. --abbrev=20), after all the default abbreviation is going to show\nsomething as small as possible, which may soon become ambigous after the\nnext commit.\n"},{"id":"336116","messageId":"c08416f1-bbec-2037-34a6-f454d85de439@gmail.com","threadId":"47560","inReplyTo":"87k1wtb8a4.fsf@evledraar.gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-08T00:08:54Z","receivedAt":"2018-01-08T00:09:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/7/2018 5:42 PM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Sun, Jan 07 2018, Derrick Stolee jotted:\n> \n>> git log --oneline --raw --parents\n>>\n>> Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n>> ----------+-------------+------------+--------+----------\n>> 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n>> 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n>> 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n>>\n>> The last column is the relative difference between the MIDX-enabled repo\n>> and the single-pack repo. The goal of the MIDX feature is to present the\n>> ODB as if it was fully repacked, so there is still room for improvement.\n>>\n>> Changing the command to\n>>\n>> git log --oneline --raw --parents --abbrev=40\n>>\n>> has no observable difference (sub 1% change in all cases). This is likely\n>> due to the repack I used putting commits and trees in a small number of\n>> packfiles so the MRU cache workes very well. On more naturally-created\n>> lists of packfiles, there can be up to 20% improvement on this command.\n>>\n>> We are using a version of this patch with an upcoming release of GVFS.\n>> This feature is particularly important in that space since GVFS performs\n>> a \"prefetch\" step that downloads a pack of commits and trees on a daily\n>> basis. These packfiles are placed in an alternate that is shared by all\n>> enlistments. Some users have 150+ packfiles and the MRU misses and\n>> abbreviation computations are significant. Now, GVFS manages the MIDX file\n>> after adding new prefetch packfiles using the following command:\n>>\n>> git midx --write --update-head --delete-expired --pack-dir=\n> \n> (Not a critique of this, just a (stupid) question)\n> \n> What's the practical use-case for this feature? Since it doesn't help\n> with --abbrev=40 the speedup is all in the part that ensures we don't\n> show an ambiguous SHA-1.\n\nThe point of including the --abbrev=40 is to point out that object \nlookups do not get slower with the MIDX feature. Using these \"git log\" \noptions is a good way to balance object lookups and abbreviations with \nobject parsing and diff machinery. And while the public data shape I \nshared did not show a difference, our private testing of the Windows \nrepository did show a valuable improvement when isolating to object \nlookups and ignoring abbreviation calculations.\n\n> The reason we do that at all is because it makes for a prettier UI.\n\nWe tried setting core.abbrev=40 on GVFS enlistments to speed up \nperformance and the users rebelled against the hideous output. They \nwould rather have slower speeds than long hashes.\n\n> Are there things that both want the pretty SHA-1 and also care about the\n> throughput? I'd have expected machine parsing to just use\n> --no-abbrev-commit.\n\nThe --raw flag outputs blob hashes, so the --abbrev=40 covers all hashes.\n\n> If something cares about both throughput and e.g. is saving the\n> abbreviated SHA-1s isn't it better off picking some arbitrary size\n> (e.g. --abbrev=20), after all the default abbreviation is going to show\n> something as small as possible, which may soon become ambigous after the\n> next commit.\n\nUnfortunately, with the way the abbreviation algorithms work, using \n--abbrev=20 will have similar performance problems because you still \nneed to inspect all packfiles to ensure there isn't a collision in the \nfirst 20 hex characters.\n\nThanks,\n-Stolee\n\n\n"},{"id":"336124","messageId":"20180108102029.GA21232@sigill.intra.peff.net","threadId":"47560","inReplyTo":"c08416f1-bbec-2037-34a6-f454d85de439@gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-08T10:20:29Z","receivedAt":"2018-01-08T10:20:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jan 07, 2018 at 07:08:54PM -0500, Derrick Stolee wrote:\n\n> > (Not a critique of this, just a (stupid) question)\n> > \n> > What's the practical use-case for this feature? Since it doesn't help\n> > with --abbrev=40 the speedup is all in the part that ensures we don't\n> > show an ambiguous SHA-1.\n> \n> The point of including the --abbrev=40 is to point out that object lookups\n> do not get slower with the MIDX feature. Using these \"git log\" options is a\n> good way to balance object lookups and abbreviations with object parsing and\n> diff machinery. And while the public data shape I shared did not show a\n> difference, our private testing of the Windows repository did show a\n> valuable improvement when isolating to object lookups and ignoring\n> abbreviation calculations.\n\nJust to make sure I'm parsing this correctly: normal lookups do get faster\nwhen you have a single index, given the right setup?\n\nI'm curious what that setup looked like. Is it just tons and tons of\npacks? Is it ones where the packs do not follow the mru patterns very\nwell?\n\nI think it's worth thinking a bit about, because...\n\n> > If something cares about both throughput and e.g. is saving the\n> > abbreviated SHA-1s isn't it better off picking some arbitrary size\n> > (e.g. --abbrev=20), after all the default abbreviation is going to show\n> > something as small as possible, which may soon become ambigous after the\n> > next commit.\n> \n> Unfortunately, with the way the abbreviation algorithms work, using\n> --abbrev=20 will have similar performance problems because you still need to\n> inspect all packfiles to ensure there isn't a collision in the first 20 hex\n> characters.\n\n...if what we primarily care about speeding up is abbreviations, is it\ncrazy to consider disabling the disambiguation step entirely?\n\nThe results of find_unique_abbrev are already a bit of a probability\ngame. They're guaranteed at the moment of generation, but as more\nobjects are added, ambiguities may be introduced. Likewise, what's\nunambiguous for you may not be for somebody else you're communicating\nwith, if they have their own clone.\n\nSince we now scale the default abbreviation with the size of the repo,\nthat gives us a bounded and pretty reasonable probability that we won't\nhit a collision at all[1].\n\nI.e., what if we did something like this:\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 611c7d24dd..04c661ba85 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -600,6 +600,15 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n \n+\t/*\n+\t * A default length of 10 implies a repository big enough that it's\n+\t * getting expensive to double check the ambiguity of each object,\n+\t * and the chance that any particular object of interest has a\n+\t * collision is low.\n+\t */\n+\tif (len >= 10)\n+\t\treturn len;\n+\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n\nIf I repack my linux.git with \"--max-pack-size=64m\", I get 67 packs. The\npatch above drops \"git log --oneline --raw\" on the resulting repo from\n~150s to ~30s.\n\nWith a single pack, it goes from ~33s ~29s. Less impressive, but there's\nstill some benefit.\n\nThere may be other reasons to want MIDX or something like it, but I just\nwonder if we can do this much simpler thing to cover the abbreviation\ncase. I guess the question is whether somebody is going to be annoyed in\nthe off chance that they hit a collision.\n\n-Peff\n\n[1] I'd have to check the numbers, but IIRC we've set the scaling so\n that the chance of having a _single_ collision in the repository is\n less than 50%, and rounding to the conservative side (since each hex\n char gives us 4 bits). And indeed, \"git log --oneline --raw\" on\n linux.git does not seem to have any collisions at its default of 12\n characters, at least in my clone.\n\n We could also consider switching core.disambiguate to \"commit\",\n which makes even a collision less likely to annoy the user.\n"},{"id":"336126","messageId":"20180108102708.GA19461@sigill.intra.peff.net","threadId":"47560","inReplyTo":"20180108102029.GA21232@sigill.intra.peff.net","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-08T10:27:08Z","receivedAt":"2018-01-08T10:27:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 08, 2018 at 05:20:29AM -0500, Jeff King wrote:\n\n> I.e., what if we did something like this:\n> \n> diff --git a/sha1_name.c b/sha1_name.c\n> index 611c7d24dd..04c661ba85 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -600,6 +600,15 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n> \tif (len == GIT_SHA1_HEXSZ || !len)\n> \t\treturn GIT_SHA1_HEXSZ;\n> \n> +\t/*\n> +\t * A default length of 10 implies a repository big enough that it's\n> +\t * getting expensive to double check the ambiguity of each object,\n> +\t * and the chance that any particular object of interest has a\n> +\t * collision is low.\n> +\t */\n> +\tif (len >= 10)\n> +\t\treturn len;\n> +\n\nOops, this really needs to terminate the string in addition to returning\nthe length (so it was always printing 40 characters in most cases). The\ncorrect patch is below, but it performs the same.\n\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 611c7d24dd..5921298a80 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -600,6 +600,17 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n \n+\t/*\n+\t * A default length of 10 implies a repository big enough that it's\n+\t * getting expensive to double check the ambiguity of each object,\n+\t * and the chance that any particular object of interest has a\n+\t * collision is low.\n+\t */\n+\tif (len >= 10) {\n+\t\thex[len] = 0;\n+\t\treturn len;\n+\t}\n+\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n"},{"id":"336132","messageId":"87fu7gbmoy.fsf@evledraar.gmail.com","threadId":"47560","inReplyTo":"c08416f1-bbec-2037-34a6-f454d85de439@gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-08T11:43:25Z","receivedAt":"2018-01-08T11:43:33Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Jan 08 2018, Derrick Stolee jotted:\n\n> On 1/7/2018 5:42 PM, Ævar Arnfjörð Bjarmason wrote:\n>> If something cares about both throughput and e.g. is saving the\n>> abbreviated SHA-1s isn't it better off picking some arbitrary size\n>> (e.g. --abbrev=20), after all the default abbreviation is going to show\n>> something as small as possible, which may soon become ambigous after the\n>> next commit.\n>\n> Unfortunately, with the way the abbreviation algorithms work, using\n> --abbrev=20 will have similar performance problems because you still\n> need to inspect all packfiles to ensure there isn't a collision in the\n> first 20 hex characters.\n\nI meant (but forgot to write) that this would be some new mode,\ne.g. --abbrev=20 --no-abbrev-check which would just perform a substr()\nof the 40 character SHA-1. It might be interesting to add that for\nreasons completely unrelated to your series.\n\nThanks for answering the rest.\n"},{"id":"336137","messageId":"87efn0bkls.fsf@evledraar.gmail.com","threadId":"47560","inReplyTo":"20180108102708.GA19461@sigill.intra.peff.net","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-01-08T12:28:31Z","receivedAt":"2018-01-08T12:28:42Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Jan 08 2018, Jeff King jotted:\n\n> On Mon, Jan 08, 2018 at 05:20:29AM -0500, Jeff King wrote:\n>\n>> I.e., what if we did something like this:\n>>\n>> diff --git a/sha1_name.c b/sha1_name.c\n>> index 611c7d24dd..04c661ba85 100644\n>> --- a/sha1_name.c\n>> +++ b/sha1_name.c\n>> @@ -600,6 +600,15 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n>> \tif (len == GIT_SHA1_HEXSZ || !len)\n>> \t\treturn GIT_SHA1_HEXSZ;\n>>\n>> +\t/*\n>> +\t * A default length of 10 implies a repository big enough that it's\n>> +\t * getting expensive to double check the ambiguity of each object,\n>> +\t * and the chance that any particular object of interest has a\n>> +\t * collision is low.\n>> +\t */\n>> +\tif (len >= 10)\n>> +\t\treturn len;\n>> +\n>\n> Oops, this really needs to terminate the string in addition to returning\n> the length (so it was always printing 40 characters in most cases). The\n> correct patch is below, but it performs the same.\n>\n> diff --git a/sha1_name.c b/sha1_name.c\n> index 611c7d24dd..5921298a80 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -600,6 +600,17 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n> \tif (len == GIT_SHA1_HEXSZ || !len)\n> \t\treturn GIT_SHA1_HEXSZ;\n>\n> +\t/*\n> +\t * A default length of 10 implies a repository big enough that it's\n> +\t * getting expensive to double check the ambiguity of each object,\n> +\t * and the chance that any particular object of interest has a\n> +\t * collision is low.\n> +\t */\n> +\tif (len >= 10) {\n> +\t\thex[len] = 0;\n> +\t\treturn len;\n> +\t}\n> +\n> \tmad.init_len = len;\n> \tmad.cur_len = len;\n> \tmad.hex = hex;\n\nThat looks much more sensible, leaving aside other potential benefits of\nMIDX.\n\nGiven the argument Linus made in e6c587c733 (\"abbrev: auto size the\ndefault abbreviation\", 2016-09-30) maybe we should add a small integer\nto the length for good measure, i.e. something like:\n\n\tif (len >= 10) {\n\t\tint extra = 2; /* or just 1? or maybe 0 ... */\n\t\thex[len + extra] = 0;\n\t\treturn len + extra;\n\t}\n\nI tried running:\n\n git log --pretty=format:%h --abbrev=7 | perl -nE 'chomp; say length'|sort|uniq -c|sort -nr\n\nOn several large repos, which forces something like the disambiguation\nwe had before Linus's patch, on e.g. David Turner's\n2015-04-03-1M-git.git test repo it's:\n\n 952858 7\n 44541 8\n 2861 9\n 168 10\n 17 11\n 2 12\n\nAnd the default abbreviation picks 12. I haven't yet found a case where\nit's wrong, but if we wanted to be extra safe we could just add a byte\nor two to the SHA-1.\n"},{"id":"336139","messageId":"nycvar.QRO.7.76.6.1801081438470.31@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47560","inReplyTo":"20180108102029.GA21232@sigill.intra.peff.net","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-01-08T13:43:00Z","receivedAt":"2018-01-08T13:43:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 8 Jan 2018, Jeff King wrote:\n\n> On Sun, Jan 07, 2018 at 07:08:54PM -0500, Derrick Stolee wrote:\n> \n> > > (Not a critique of this, just a (stupid) question)\n> > > \n> > > What's the practical use-case for this feature? Since it doesn't\n> > > help with --abbrev=40 the speedup is all in the part that ensures we\n> > > don't show an ambiguous SHA-1.\n> > \n> > The point of including the --abbrev=40 is to point out that object\n> > lookups do not get slower with the MIDX feature. Using these \"git log\"\n> > options is a good way to balance object lookups and abbreviations with\n> > object parsing and diff machinery. And while the public data shape I\n> > shared did not show a difference, our private testing of the Windows\n> > repository did show a valuable improvement when isolating to object\n> > lookups and ignoring abbreviation calculations.\n> \n> Just to make sure I'm parsing this correctly: normal lookups do get\n> faster when you have a single index, given the right setup?\n> \n> I'm curious what that setup looked like. Is it just tons and tons of\n> packs? Is it ones where the packs do not follow the mru patterns very\n> well?\n> \n> I think it's worth thinking a bit about, because...\n> \n> > > If something cares about both throughput and e.g. is saving the\n> > > abbreviated SHA-1s isn't it better off picking some arbitrary size\n> > > (e.g. --abbrev=20), after all the default abbreviation is going to show\n> > > something as small as possible, which may soon become ambigous after the\n> > > next commit.\n> > \n> > Unfortunately, with the way the abbreviation algorithms work, using\n> > --abbrev=20 will have similar performance problems because you still need to\n> > inspect all packfiles to ensure there isn't a collision in the first 20 hex\n> > characters.\n> \n> ...if what we primarily care about speeding up is abbreviations, is it\n> crazy to consider disabling the disambiguation step entirely?\n\nNot crazy. But it would break stuff. Because...\n\n> The results of find_unique_abbrev are already a bit of a probability\n> game. They're guaranteed at the moment of generation, but as more\n> objects are added, ambiguities may be introduced. Likewise, what's\n> unambiguous for you may not be for somebody else you're communicating\n> with, if they have their own clone.\n\n... this is only a probability game in the long term, when you consider\nnew objects to enter from *somewhere*.\n\nBut in purely local settings, when we expect no new objects to be\nintroduced, we do use known-unambiguous abbreviations.\n\nTake the interactive rebase for example. It generates todo lists with\nabbreviated commit names, for readability (and it is *really* important to\nkeep this readable). As we expect new objects to be introduced by the\ninteractive rebase, we convert that todo list to unabbreviated commit\nnames before executing the interactive rebase.\n\nYour idea (to not care about unambiguous abbreviations) would break that.\n\nCiao,\nDscho\n"},{"id":"336140","messageId":"d00ba196-715d-4613-530c-ef7f7c4562f4@gmail.com","threadId":"47560","inReplyTo":"20180108102029.GA21232@sigill.intra.peff.net","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-08T13:43:44Z","receivedAt":"2018-01-08T13:43:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/8/2018 5:20 AM, Jeff King wrote:\n> On Sun, Jan 07, 2018 at 07:08:54PM -0500, Derrick Stolee wrote:\n>\n>>> (Not a critique of this, just a (stupid) question)\n>>>\n>>> What's the practical use-case for this feature? Since it doesn't help\n>>> with --abbrev=40 the speedup is all in the part that ensures we don't\n>>> show an ambiguous SHA-1.\n>> The point of including the --abbrev=40 is to point out that object lookups\n>> do not get slower with the MIDX feature. Using these \"git log\" options is a\n>> good way to balance object lookups and abbreviations with object parsing and\n>> diff machinery. And while the public data shape I shared did not show a\n>> difference, our private testing of the Windows repository did show a\n>> valuable improvement when isolating to object lookups and ignoring\n>> abbreviation calculations.\n> Just to make sure I'm parsing this correctly: normal lookups do get faster\n> when you have a single index, given the right setup?\n>\n> I'm curious what that setup looked like. Is it just tons and tons of\n> packs? Is it ones where the packs do not follow the mru patterns very\n> well?\n\nThe way I repacked the Linux repo creates an artificially good set of \npacks for the MRU cache. When the packfiles are partitioned instead by \nthe time the objects were pushed to a remote, the MRU cache performs \npoorly. Improving these object lookups are a primary reason for the MIDX \nfeature, and almost all commands improve because of it. 'git log' is \njust the simplest to use for demonstration.\n\n> I think it's worth thinking a bit about, because...\n>\n>>> If something cares about both throughput and e.g. is saving the\n>>> abbreviated SHA-1s isn't it better off picking some arbitrary size\n>>> (e.g. --abbrev=20), after all the default abbreviation is going to show\n>>> something as small as possible, which may soon become ambigous after the\n>>> next commit.\n>> Unfortunately, with the way the abbreviation algorithms work, using\n>> --abbrev=20 will have similar performance problems because you still need to\n>> inspect all packfiles to ensure there isn't a collision in the first 20 hex\n>> characters.\n> ...if what we primarily care about speeding up is abbreviations, is it\n> crazy to consider disabling the disambiguation step entirely?\n>\n> The results of find_unique_abbrev are already a bit of a probability\n> game. They're guaranteed at the moment of generation, but as more\n> objects are added, ambiguities may be introduced. Likewise, what's\n> unambiguous for you may not be for somebody else you're communicating\n> with, if they have their own clone.\n>\n> Since we now scale the default abbreviation with the size of the repo,\n> that gives us a bounded and pretty reasonable probability that we won't\n> hit a collision at all[1].\n>\n> I.e., what if we did something like this:\n>\n> diff --git a/sha1_name.c b/sha1_name.c\n> index 611c7d24dd..04c661ba85 100644\n> --- a/sha1_name.c\n> +++ b/sha1_name.c\n> @@ -600,6 +600,15 @@ int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len)\n> \tif (len == GIT_SHA1_HEXSZ || !len)\n> \t\treturn GIT_SHA1_HEXSZ;\n> \n> +\t/*\n> +\t * A default length of 10 implies a repository big enough that it's\n> +\t * getting expensive to double check the ambiguity of each object,\n> +\t * and the chance that any particular object of interest has a\n> +\t * collision is low.\n> +\t */\n> +\tif (len >= 10)\n> +\t\treturn len;\n> +\n> \tmad.init_len = len;\n> \tmad.cur_len = len;\n> \tmad.hex = hex;\n>\n> If I repack my linux.git with \"--max-pack-size=64m\", I get 67 packs. The\n> patch above drops \"git log --oneline --raw\" on the resulting repo from\n> ~150s to ~30s.\n>\n> With a single pack, it goes from ~33s ~29s. Less impressive, but there's\n> still some benefit.\n>\n> There may be other reasons to want MIDX or something like it, but I just\n> wonder if we can do this much simpler thing to cover the abbreviation\n> case. I guess the question is whether somebody is going to be annoyed in\n> the off chance that they hit a collision.\n\nNo only are users going to be annoyed when they hit collisions after \ncopy-pasting an abbreviated hash, there are also a large number of tools \nthat people build that use abbreviated hashes (either for presenting to \nusers or because they didn't turn off abbreviations).\n\nAbbreviations cause performance issues in other commands, too (like \n'fetch'!), so whatever short-circuit you put in, it would need to be \nglobal. A flag on one builtin would not suffice.\n\n> -Peff\n>\n> [1] I'd have to check the numbers, but IIRC we've set the scaling so\n> that the chance of having a _single_ collision in the repository is\n> less than 50%, and rounding to the conservative side (since each hex\n> char gives us 4 bits). And indeed, \"git log --oneline --raw\" on\n> linux.git does not seem to have any collisions at its default of 12\n> characters, at least in my clone.\n>\n> We could also consider switching core.disambiguate to \"commit\",\n> which makes even a collision less likely to annoy the user.\n\n\n"},{"id":"336175","messageId":"20180108113226.da265814e5c1deea1f8c404d@google.com","threadId":"47560","inReplyTo":"20180107181459.222909-2-dstolee@microsoft.com","subject":"Re: [RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-01-08T19:32:26Z","receivedAt":"2018-01-08T19:32:34Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Sun, 7 Jan 2018 13:14:42 -0500\nDerrick Stolee wrote:\n\n> +Design Details\n> +--------------\n> +\n> +- The MIDX file refers only to packfiles in the same directory\n> + as the MIDX file.\n> +\n> +- A special file, 'midx-head', stores the hash of the latest\n> + MIDX file so we can load the file without performing a dirstat.\n> + This file is especially important with incremental MIDX files,\n> + pointing to the newest file.\n\nI presume that the actual MIDX files are named by hash? (You might have\nwritten this somewhere that I somehow missed.)\n\nAlso, I notice that in the \"Future Work\" section, the possibility of\nmultiple MIDX files is raised. Could this 'midx-head' file be allowed to\nstore multiple such files? That way, we avoid a bit of file format\nchurn (in that we won't need to define a new \"chunk\" in the future).\n\n> +- If a packfile exists in the pack directory but is not referenced\n> + by the MIDX file, then the packfile is loaded into the packed_git\n> + list and Git can access the objects as usual. This behavior is\n> + necessary since other tools could add packfiles to the pack\n> + directory without notifying Git.\n> +\n> +- The MIDX file should be only a supplemental structure. If a\n> + user downgrades or disables the `core.midx` config setting,\n> + then the existing .idx and .pack files should be sufficient\n> + to operate correctly.\n\nLet me try to summarize: so, at this point, there are no\nbackwards-incompatible changes to the repo disk format. Unupdated code\npaths (and old versions of Git) can just read the .idx and .pack files,\nas always. Updated code paths will look at the .midx and .idx files, and\nwill sort them as follows:\n - .midx files go into a data structure\n - .idx files not referenced by any .midx files go into the\n existing packed_git data structure\n\nA writer can either merely write a new packfile (like old versions of\nGit) or write a packfile and update the .midx file, and everything above\nwill still work. In the event that a writer deletes an existing packfile\nreferenced by a .midx (for example, old versions of Git during a\nrepack), we will lose the advantages of the .midx file - we will detect\nthat the .midx no longer works when attempting to read an object given\nits information, but in this case, we can recover by dropping the .midx\nfile and loading all the .idx files it references that still exist.\n\nAs a reviewer, I think this is a very good approach, and this does make\nthings easier to review (as opposed to, say, an approach where a lot of\nthe code must be aware of .midx files).\n"},{"id":"336190","messageId":"4d7a1fb2-84ca-6bf9-811c-29ad21b4c5a6@gmail.com","threadId":"47560","inReplyTo":"20180108113226.da265814e5c1deea1f8c404d@google.com","subject":"Re: [RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-08T20:35:59Z","receivedAt":"2018-01-08T20:36:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/8/2018 2:32 PM, Jonathan Tan wrote:\n> On Sun, 7 Jan 2018 13:14:42 -0500\n> Derrick Stolee wrote:\n>\n>> +Design Details\n>> +--------------\n>> +\n>> +- The MIDX file refers only to packfiles in the same directory\n>> + as the MIDX file.\n>> +\n>> +- A special file, 'midx-head', stores the hash of the latest\n>> + MIDX file so we can load the file without performing a dirstat.\n>> + This file is especially important with incremental MIDX files,\n>> + pointing to the newest file.\n> I presume that the actual MIDX files are named by hash? (You might have\n> written this somewhere that I somehow missed.)\n>\n> Also, I notice that in the \"Future Work\" section, the possibility of\n> multiple MIDX files is raised. Could this 'midx-head' file be allowed to\n> store multiple such files? That way, we avoid a bit of file format\n> churn (in that we won't need to define a new \"chunk\" in the future).\n\nI hadn't considered this idea, and I like it. I'm not sure this is a \nrobust solution, since isolated MIDX files don't contain information \nthat they could use other MIDX files, or what order they should be in. I \nthink the \"order\" of incremental MIDX files is important in a few ways \n(such as the \"stable object order\" idea).\n\nI will revisit this idea when I come back with the incremental MIDX \nfeature. For now, the only reference to \"number of base MIDX files\" is \nin one byte of the MIDX header. We should consider changing that byte \nfor this patch.\n\n>> +- If a packfile exists in the pack directory but is not referenced\n>> + by the MIDX file, then the packfile is loaded into the packed_git\n>> + list and Git can access the objects as usual. This behavior is\n>> + necessary since other tools could add packfiles to the pack\n>> + directory without notifying Git.\n>> +\n>> +- The MIDX file should be only a supplemental structure. If a\n>> + user downgrades or disables the `core.midx` config setting,\n>> + then the existing .idx and .pack files should be sufficient\n>> + to operate correctly.\n> Let me try to summarize: so, at this point, there are no\n> backwards-incompatible changes to the repo disk format. Unupdated code\n> paths (and old versions of Git) can just read the .idx and .pack files,\n> as always. Updated code paths will look at the .midx and .idx files, and\n> will sort them as follows:\n> - .midx files go into a data structure\n> - .idx files not referenced by any .midx files go into the\n> existing packed_git data structure\n>\n> A writer can either merely write a new packfile (like old versions of\n> Git) or write a packfile and update the .midx file, and everything above\n> will still work. In the event that a writer deletes an existing packfile\n> referenced by a .midx (for example, old versions of Git during a\n> repack), we will lose the advantages of the .midx file - we will detect\n> that the .midx no longer works when attempting to read an object given\n> its information, but in this case, we can recover by dropping the .midx\n> file and loading all the .idx files it references that still exist.\n>\n> As a reviewer, I think this is a very good approach, and this does make\n> things easier to review (as opposed to, say, an approach where a lot of\n> the code must be aware of .midx files).\n\nThanks! That is certainly the idea. If you know about MIDX, then you can \nbenefit from it. If you do not, then you have all the same data \navailable to you do to your work. Having a MIDX file will not break \nother tools (libgit2, JGit, etc.).\n\nOne thing I'd like to determine before this patch goes to v1 is how much \nwe should make the other packfile-aware commands also midx-aware. My gut \nreaction right now is to have git-repack call 'git midx --clear' if \ncore.midx=true and a packfile was deleted. However, this could easily be \nchanged with 'git midx --clear' followed by 'git midx --write \n--update-head' if midx-head exists.\n\nThanks,\n-Stolee\n"},{"id":"336206","messageId":"20180108140631.1205a837baab24cb0fe021bc@google.com","threadId":"47560","inReplyTo":"4d7a1fb2-84ca-6bf9-811c-29ad21b4c5a6@gmail.com","subject":"Re: [RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-01-08T22:06:31Z","receivedAt":"2018-01-08T22:06:38Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, 8 Jan 2018 15:35:59 -0500\nDerrick Stolee wrote:\n\n> Thanks! That is certainly the idea. If you know about MIDX, then you can \n> benefit from it. If you do not, then you have all the same data \n> available to you do to your work. Having a MIDX file will not break \n> other tools (libgit2, JGit, etc.).\n> \n> One thing I'd like to determine before this patch goes to v1 is how much \n> we should make the other packfile-aware commands also midx-aware. My gut \n> reaction right now is to have git-repack call 'git midx --clear' if \n> core.midx=true and a packfile was deleted. However, this could easily be \n> changed with 'git midx --clear' followed by 'git midx --write \n> --update-head' if midx-head exists.\n\nMy opinion is that these are sufficient:\n (a) functionality to create a .midx file from scratch (deleting any\n existing ones)\n (b) either:\n - update of packfile.c to read (one or more) midx files (like in\n patch 18), and possibly usage in a benchmark, or\n - any other usage of midx file (e.g. abbreviations, like in patch\n 17)\n\nIn general, a way to create them (so that they can be used from a\ncronjob, etc.), and a way to consume them to show that the new way works\nand is indeed faster. This functionality in itself might be sufficient\nto merge in - this would already be useful in situations where it is\nundesirable for repacks to happen often, and we can \"bridge\" the\nintervals between repacks using a cronjob that periodically generates\n.midx files in order to keep up the object lookup performance.\n\nIn particular, I think that it is fine to omit a more sophisticated\n\"repack\" for now - the .midx mechanism must tolerate packs referenced by\n.midx files suddenly disappearing anyway, and in this way, at least we\ncan demonstrate that the .midx mechanism still works in this case.\n"},{"id":"336221","messageId":"20180109065018.GA32257@sigill.intra.peff.net","threadId":"47560","inReplyTo":"nycvar.QRO.7.76.6.1801081438470.31@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-09T06:50:18Z","receivedAt":"2018-01-09T06:50:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 08, 2018 at 02:43:00PM +0100, Johannes Schindelin wrote:\n\n> Take the interactive rebase for example. It generates todo lists with\n> abbreviated commit names, for readability (and it is *really* important to\n> keep this readable). As we expect new objects to be introduced by the\n> interactive rebase, we convert that todo list to unabbreviated commit\n> names before executing the interactive rebase.\n> \n> Your idea (to not care about unambiguous abbreviations) would break that.\n\nI think that could be easily worked around for rebase by asking git to\ncheck ambiguity during the conversion. Speed is much less of a problem\nthere, because we're doing a relatively small number of abbreviations\n(compared to \"git log --oneline --raw\", which is abbreviating almost\nevery object in the repository).\n\nBut I agree it's a potential problem for other scripts that we might not\nhave control over. I hadn't really intended this to be the default\nbehavior (my patch was just trying to show the direction). But it does\nmake for a pretty awful interface if callers have to opt into it\nmanually (\"git log --oneline --no-really-go-fast\").\n\nI am a bit curious if there's a bounded probability that people would\nfind acceptable for Git to give an ambiguous abbreviation. We already\naccept 1 in 2^160, of course. But would, e.g., one in a million be OK?\n\n-Peff\n"},{"id":"336222","messageId":"20180109071208.GB32257@sigill.intra.peff.net","threadId":"47560","inReplyTo":"d00ba196-715d-4613-530c-ef7f7c4562f4@gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-09T07:12:08Z","receivedAt":"2018-01-09T07:12:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jan 08, 2018 at 08:43:44AM -0500, Derrick Stolee wrote:\n\n> > Just to make sure I'm parsing this correctly: normal lookups do get faster\n> > when you have a single index, given the right setup?\n> > \n> > I'm curious what that setup looked like. Is it just tons and tons of\n> > packs? Is it ones where the packs do not follow the mru patterns very\n> > well?\n> \n> The way I repacked the Linux repo creates an artificially good set of packs\n> for the MRU cache. When the packfiles are partitioned instead by the time\n> the objects were pushed to a remote, the MRU cache performs poorly.\n> Improving these object lookups are a primary reason for the MIDX feature,\n> and almost all commands improve because of it. 'git log' is just the\n> simplest to use for demonstration.\n\nInteresting.\n\nThe idea of the pack mru (and the \"last pack looked in\" before it) is\nthat there would be good locality for time-segmented packs (like those\ngenerated by pushes), since most operations also tend to visit history\nin chronological-ish order (e.g., log). Tree-wide operations would be an\nexception there, though, since files would have many ages across the\ntree (though in practice, one would hope that pretty-ancient history\nwould eventually be replaced in a modern tree).\n\nI've often wondered, though, if the mru (and \"last pack\") work mainly\nbecause the \"normal\" distribution for a repository is to have one big\npack with most of history, and then a couple of smaller ones (what\nhasn't been packed yet). Even something as naive as \"look in the last\npack\" works there, because it turns into \"look in the biggest pack\". If\nit has most of the objects, it's the most likely place for the previous\nand the next objects to be.\n\nBut from my understanding of how you handle the Windows repository, you\nhave tons of equal-sized packs that are never coalesced. Which is quite\na different pattern.\n\nI would expect your \"--max-pack-size\" thing to end up with something\nroughly segmented like pushes, though, just because we do order the\nwrite phase in reverse chronological order. Well, mostly. We do each\nobject type in its own chunks, and there's some reordering based on\ndeltas. So given the sizes, it's likely that most of your trees all end\nup in a few packs.\n\n> > There may be other reasons to want MIDX or something like it, but I just\n> > wonder if we can do this much simpler thing to cover the abbreviation\n> > case. I guess the question is whether somebody is going to be annoyed in\n> > the off chance that they hit a collision.\n> \n> No only are users going to be annoyed when they hit collisions after\n> copy-pasting an abbreviated hash, there are also a large number of tools\n> that people build that use abbreviated hashes (either for presenting to\n> users or because they didn't turn off abbreviations).\n>\n> Abbreviations cause performance issues in other commands, too (like\n> 'fetch'!), so whatever short-circuit you put in, it would need to be global.\n> A flag on one builtin would not suffice.\n\nYeah, I agree it's potentially problematic for a lot of reasons. I was\njust hoping we could bound the probabilities in a way that is\nacceptable. Maybe it's a fool's errand.\n\n-Peff\n"},{"id":"336229","messageId":"nycvar.QRO.7.76.6.1801091357560.37@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47560","inReplyTo":"20180109065018.GA32257@sigill.intra.peff.net","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-01-09T13:05:09Z","receivedAt":"2018-01-09T13:05:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Tue, 9 Jan 2018, Jeff King wrote:\n\n> On Mon, Jan 08, 2018 at 02:43:00PM +0100, Johannes Schindelin wrote:\n> \n> > Take the interactive rebase for example. It generates todo lists with\n> > abbreviated commit names, for readability (and it is *really* important to\n> > keep this readable). As we expect new objects to be introduced by the\n> > interactive rebase, we convert that todo list to unabbreviated commit\n> > names before executing the interactive rebase.\n> > \n> > Your idea (to not care about unambiguous abbreviations) would break that.\n> \n> I think that could be easily worked around for rebase by asking git to\n> check ambiguity during the conversion.\n\nSure.\n\nIt also points to a flaw in your reasoning, and you should take my example\nfurther: previously, we guaranteed unique abbreviations, and who is to say\nthat there is no script out there relying on that guarantee? You?\n\n> But I agree it's a potential problem for other scripts that we might not\n> have control over. I hadn't really intended this to be the default\n> behavior (my patch was just trying to show the direction). But it does\n> make for a pretty awful interface if callers have to opt into it\n> manually (\"git log --oneline --no-really-go-fast\").\n\nExactly.\n\n> I am a bit curious if there's a bounded probability that people would\n> find acceptable for Git to give an ambiguous abbreviation. We already\n> accept 1 in 2^160, of course. But would, e.g., one in a million be OK?\n\nWhat is that going to solve?\n\nI think a better alternative would be to introduce a new abbreviation mode\nthat is *intended* to stop caring about unique abbreviations.\n\nIn web interfaces, for example, it makes tons of sense to show, say, 8\ndigits in link texts and have the full name in the actual link URL.\n\nCurrently, we have no way to tell Git: look, I want to have a short label\nfor this, but I do not really care that this is unambiguous, I just want\nsomething to talk about.\n\n(And you are correct, of course, that the uniqueness of abbreviations will\nno longer be guaranteed for partial clones, and it is already not\nguaranteed for shallow clones, and it will only be possible to guarantee\nthis, ever, for one particular repository at a particular time.)\n\nI am just hesitant to change things that would break existing setups.\n\nJust to throw this out there: --abbrev=8! would be one possible convention\nto state \"I want exactly 8 hex digits, don't bother checking for\nuniqueness\".\n\nNot sure how urgent such a feature is.\n\nCiao,\nDscho\n"},{"id":"336308","messageId":"CAGZ79kYdgD2h7QjjJe0aA4eMATCGkH62XYvziUNvAPsBJDXOCA@mail.gmail.com","threadId":"47560","inReplyTo":"nycvar.QRO.7.76.6.1801091357560.37@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-09T19:51:06Z","receivedAt":"2018-01-09T19:51:13Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Jan 9, 2018 at 5:05 AM, Johannes Schindelin\n wrote:\n> Hi Peff,\n>\n> On Tue, 9 Jan 2018, Jeff King wrote:\n>\n>> On Mon, Jan 08, 2018 at 02:43:00PM +0100, Johannes Schindelin wrote:\n>>\n>> > Take the interactive rebase for example. It generates todo lists with\n>> > abbreviated commit names, for readability (and it is *really* important to\n>> > keep this readable). As we expect new objects to be introduced by the\n>> > interactive rebase, we convert that todo list to unabbreviated commit\n>> > names before executing the interactive rebase.\n>> >\n>> > Your idea (to not care about unambiguous abbreviations) would break that.\n>>\n>> I think that could be easily worked around for rebase by asking git to\n>> check ambiguity during the conversion.\n>\n> Sure.\n>\n> It also points to a flaw in your reasoning, and you should take my example\n> further: previously, we guaranteed unique abbreviations, and who is to say\n> that there is no script out there relying on that guarantee? You?\n>\n>> But I agree it's a potential problem for other scripts that we might not\n>> have control over. I hadn't really intended this to be the default\n>> behavior (my patch was just trying to show the direction). But it does\n>> make for a pretty awful interface if callers have to opt into it\n>> manually (\"git log --oneline --no-really-go-fast\").\n>\n> Exactly.\n>\n>> I am a bit curious if there's a bounded probability that people would\n>> find acceptable for Git to give an ambiguous abbreviation. We already\n>> accept 1 in 2^160, of course. But would, e.g., one in a million be OK?\n>\n> What is that going to solve?\n>\n> I think a better alternative would be to introduce a new abbreviation mode\n> that is *intended* to stop caring about unique abbreviations.\n>\n> In web interfaces, for example, it makes tons of sense to show, say, 8\n> digits in link texts and have the full name in the actual link URL.\n>\n> Currently, we have no way to tell Git: look, I want to have a short label\n> for this, but I do not really care that this is unambiguous, I just want\n> something to talk about.\n>\n> (And you are correct, of course, that the uniqueness of abbreviations will\n> no longer be guaranteed for partial clones, and it is already not\n> guaranteed for shallow clones, and it will only be possible to guarantee\n> this, ever, for one particular repository at a particular time.)\n>\n> I am just hesitant to change things that would break existing setups.\n>\n> Just to throw this out there: --abbrev=8! would be one possible convention\n> to state \"I want exactly 8 hex digits, don't bother checking for\n> uniqueness\".\n>\n> Not sure how urgent such a feature is.\n\nYou seem to have spent some time on rebase, including lamenting on the\nin-expressiveness of the instruction sheet (c.f. \"rebase a mergy history sucks\")\n\nAnd in that light, I'd like to propose a new naming scheme:\n\n(a) assume that we \"tag\" HEAD at the start of the rebase\n(b) any abbreviation must be given as committish anchored to said ref:\n\npick REBASE_HEAD~1 commit subject\npick REBASE_HEAD~2 distak the gostim\npick REBASE_HEAD~3 Document foo\npick REBASE_HEAD~4 Testing the star-gazer\n\nAnd as we have the full descriptiveness of the committishs there,\neach commit can be described in a unique way using the graph relationship.\nI am just throwing the name REBASE_HEAD out there to trigger some associations\n(\"similar to FETCH_HEAD\"), but I dislike the name.\n\n(c) this would not solve the problem of mergy history, yet. For that we'd need\n to introduce more keywords, that allow us to move around in the DAG,\n such that we can reset to a specific revision or name revisions on the fly.\n So maybe all we need is \"reset\", \"name\" (== short lived tag),\n \"merge\" (rewrite parents of HEAD) to be expressive enough, but still keep\n the line oriented interface?\n\nStefan\n"},{"id":"336311","messageId":"xmqqtvvu4wr2.fsf@gitster.mtv.corp.google.com","threadId":"47560","inReplyTo":"CAGZ79kYdgD2h7QjjJe0aA4eMATCGkH62XYvziUNvAPsBJDXOCA@mail.gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-09T20:12:33Z","receivedAt":"2018-01-09T20:12:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> And in that light, I'd like to propose a new naming scheme:\n>\n> (a) assume that we \"tag\" HEAD at the start of the rebase\n> (b) any abbreviation must be given as committish anchored to said ref:\n>\n> pick REBASE_HEAD~1 commit subject\n> pick REBASE_HEAD~2 distak the gostim\n> pick REBASE_HEAD~3 Document foo\n> pick REBASE_HEAD~4 Testing the star-gazer\n>\n> And as we have the full descriptiveness of the committishs there,\n> each commit can be described in a unique way using the graph relationship.\n> I am just throwing the name REBASE_HEAD out there to trigger some associations\n> (\"similar to FETCH_HEAD\"), but I dislike the name.\n>\n> (c) this would not solve the problem of mergy history, yet. For that we'd need\n> to introduce more keywords, that allow us to move around in the DAG,\n> such that we can reset to a specific revision or name revisions on the fly.\n> So maybe all we need is \"reset\", \"name\" (== short lived tag),\n> \"merge\" (rewrite parents of HEAD) to be expressive enough, but still keep\n> the line oriented interface?\n\nIt is correct to say that (c) is an issue that is not solved by (b),\nbut with the current scheme, the commits are internally referenced\nby full object names, and just before it is presented to the end\nusers, these names are abbreviated down to unique prefix. The\nmachinery expands these abbreviated names back to the full names\nbefore going forward, so it is not an issue that we are creating new\ncommits during the rebase.\n\nDoes it make it easier to read if we used ~$n notation based on a\nfixed point, instead of shortened unique object names? What\nimprovement is (b) trying to achieve?\n\n\n\n"},{"id":"336312","messageId":"CAGZ79kajChFqJRxLAaFnUeikW28kJQXLj7JG6G3=Td4u-zxTwg@mail.gmail.com","threadId":"47560","inReplyTo":"xmqqtvvu4wr2.fsf@gitster.mtv.corp.google.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-01-09T20:16:41Z","receivedAt":"2018-01-09T20:16:48Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Jan 9, 2018 at 12:12 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> And in that light, I'd like to propose a new naming scheme:\n>>\n>> (a) assume that we \"tag\" HEAD at the start of the rebase\n>> (b) any abbreviation must be given as committish anchored to said ref:\n>>\n>> pick REBASE_HEAD~1 commit subject\n>> pick REBASE_HEAD~2 distak the gostim\n>> pick REBASE_HEAD~3 Document foo\n>> pick REBASE_HEAD~4 Testing the star-gazer\n>>\n>> And as we have the full descriptiveness of the committishs there,\n>> each commit can be described in a unique way using the graph relationship.\n>> I am just throwing the name REBASE_HEAD out there to trigger some associations\n>> (\"similar to FETCH_HEAD\"), but I dislike the name.\n>>\n>> (c) this would not solve the problem of mergy history, yet. For that we'd need\n>> to introduce more keywords, that allow us to move around in the DAG,\n>> such that we can reset to a specific revision or name revisions on the fly.\n>> So maybe all we need is \"reset\", \"name\" (== short lived tag),\n>> \"merge\" (rewrite parents of HEAD) to be expressive enough, but still keep\n>> the line oriented interface?\n>\n> It is correct to say that (c) is an issue that is not solved by (b),\n> but with the current scheme, the commits are internally referenced\n> by full object names, and just before it is presented to the end\n> users, these names are abbreviated down to unique prefix. The\n> machinery expands these abbreviated names back to the full names\n> before going forward, so it is not an issue that we are creating new\n> commits during the rebase.\n>\n> Does it make it easier to read if we used ~$n notation based on a\n> fixed point, instead of shortened unique object names? What\n> improvement is (b) trying to achieve?\n>\n\nJohannes wrote:\n> I think a better alternative would be to introduce a new abbreviation mode\n> that is *intended* to stop caring about unique abbreviations.\n>\n> In web interfaces, for example, it makes tons of sense to show, say, 8\n> digits in link texts and have the full name in the actual link URL.\n\nAnd that is what (b) would solve, as it is shorter than the full hash and\nyet exact.\n\n(c) was mostly speculation on top of (b) if we can take it any further.\n"},{"id":"336319","messageId":"xmqq373e4t3x.fsf@gitster.mtv.corp.google.com","threadId":"47560","inReplyTo":"CAGZ79kajChFqJRxLAaFnUeikW28kJQXLj7JG6G3=Td4u-zxTwg@mail.gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-09T21:31:14Z","receivedAt":"2018-01-09T21:31:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> Johannes wrote:\n>> I think a better alternative would be to introduce a new abbreviation mode\n>> that is *intended* to stop caring about unique abbreviations.\n>>\n>> In web interfaces, for example, it makes tons of sense to show, say, 8\n>> digits in link texts and have the full name in the actual link URL.\n>\n> And that is what (b) would solve, as it is shorter than the full hash and\n> yet exact.\n\nI still do not get it, even though I fully agree that in Web UI what\nDscho envisions makes tons of sense. Use some short handle that\ndoes not need to be unique inside repository to display, but have a\nfull information that can be used by machines. The shortened ones\nneed to be unique _within_ a given todo list, to be displayed as\ntext to be \"clicked\", where the A element's href attribute that\nsurrounds that \"clickable\" text has fully unambiguous information.\n\nAnd that fully unambiguous information, because it is for machine\nconsumption, can be a full object name without any shortening.\n\nI do not see a need for REBASE_HEAD~$n to make it less robust\n(i.e. we now need to worry about making sure it is not lost or moved\nwhile we need it and clean it up when we are done, etc.)\n"},{"id":"336374","messageId":"20180110105723.GB18553@sigill.intra.peff.net","threadId":"47560","inReplyTo":"nycvar.QRO.7.76.6.1801091357560.37@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-10T10:57:23Z","receivedAt":"2018-01-10T10:57:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 09, 2018 at 02:05:09PM +0100, Johannes Schindelin wrote:\n\n> > I think that could be easily worked around for rebase by asking git to\n> > check ambiguity during the conversion.\n> \n> Sure.\n> \n> It also points to a flaw in your reasoning, and you should take my example\n> further: previously, we guaranteed unique abbreviations, and who is to say\n> that there is no script out there relying on that guarantee? You?\n\nI'm not sure what you think my reasoning was, since I made the same\npoint directly after. ;)\n\n> > I am a bit curious if there's a bounded probability that people would\n> > find acceptable for Git to give an ambiguous abbreviation. We already\n> > accept 1 in 2^160, of course. But would, e.g., one in a million be OK?\n> \n> What is that going to solve?\n\nI'm not sure I understand your question. We can bound the probability of\na collision by increasing the size of the abbreviation. My question was\nwhether there is a size where that tradeoff makes sense. So it \"solves\"\nthe problem of worrying about collisions.\n\n> I think a better alternative would be to introduce a new abbreviation mode\n> that is *intended* to stop caring about unique abbreviations.\n> \n> In web interfaces, for example, it makes tons of sense to show, say, 8\n> digits in link texts and have the full name in the actual link URL.\n\nI'm not sure if that would be useful option or not. I certainly agree\nthat static abbreviations are a useful thing to want. But for scripted\ncallers, it's usually easy to cut down the abbreviation yourself. I\nthink your web interface example is a good one. The caller will ask Git\nfor the full 40-hex hash, and then cut it down itself when generating\nthe link (and I just so happen to have worked on a web interface that\ndoes this[1]).\n\nSo would it be useful for humans to use? That's what I'm not sure about.\nIt seems cumbersome to have to add \"--abbrev=8!\" on the command line to\neach invocation. But if it were triggered by config, it seems like we\nwould risk breaking scripts.\n\n> I am just hesitant to change things that would break existing setups.\n\nMe too. I'm not sure if I'm seriously advocating the \"bound the\nprobability\" thing. It's just something I think is worth pondering a\nlittle.\n\n-Peff\n\n[1] Actually, there _is_ something that it's useful for Git to tell the\n caller, which is the approximate number of objects in the\n repository. Eight digits is not enough for the kernel, for example,\n and these days we use 12 digits by default. I'm not sure if such a\n web interface would rather ask for \"%H %h\" and generate the link\n text from the second half, or it would rather just get a ballpark on\n the number of objects, and do the simple abbreviation math itself\n (right now GitHub does not do either; I don't know about other\n interfaces).\n"},{"id":"336394","messageId":"nycvar.QRO.7.76.6.1801101756140.31@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47560","inReplyTo":"CAGZ79kYdgD2h7QjjJe0aA4eMATCGkH62XYvziUNvAPsBJDXOCA@mail.gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-01-10T17:05:25Z","receivedAt":"2018-01-10T17:05:57Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Stefan,\n\nOn Tue, 9 Jan 2018, Stefan Beller wrote:\n\n> On Tue, Jan 9, 2018 at 5:05 AM, Johannes Schindelin\n> wrote:\n>\n> > Just to throw this out there: --abbrev=8! would be one possible\n> > convention to state \"I want exactly 8 hex digits, don't bother\n> > checking for uniqueness\".\n> >\n> > Not sure how urgent such a feature is.\n> \n> You seem to have spent some time on rebase, including lamenting on the\n> in-expressiveness of the instruction sheet (c.f. \"rebase a mergy history\n> sucks\")\n\nLet's call it \"todo list\" again?\n\nAnd yes, I spend a *lot* of time in rebase. It's part of my duties as Git\nfor Windows maintainer.\n\n> And in that light, I'd like to propose a new naming scheme:\n> \n> (a) assume that we \"tag\" HEAD at the start of the rebase\n> (b) any abbreviation must be given as committish anchored to said ref:\n> \n> pick REBASE_HEAD~1 commit subject\n> pick REBASE_HEAD~2 distak the gostim\n> pick REBASE_HEAD~3 Document foo\n> pick REBASE_HEAD~4 Testing the star-gazer\n\nI do not necessarily agree that this is better because it is valid only\nlocally, only in the current rebase (and you enter new problems because\nyou implicitly require REBASE_HEAD to be worktree-local lest you prevent\nsimultaneous rebases in related worktrees).\n\nThat prevents you from, say, chatting to your colleague and mentioning\nthat commit that you are uncertain about. Imagine asking \"Hey Todd, do you\nknow what REBASE_HEAD~2 is all about?\". Granted, if you ask about\n\"deadbeef\" and it just so happens that this shortened name is ambiguous in\nTodd's repository. But that is pretty unlikely, isn't it?\n\n> And as we have the full descriptiveness of the committishs there, each\n> commit can be described in a unique way using the graph relationship. I\n> am just throwing the name REBASE_HEAD out there to trigger some\n> associations (\"similar to FETCH_HEAD\"), but I dislike the name.\n\nNot only that. It would also be confusing to read after reordering...\n\n> (c) this would not solve the problem of mergy history, yet. For that\n> we'd need to introduce more keywords, that allow us to move around in\n> the DAG, [...]\n\nYou probably missed my hint that I have a working solution for that.\nPlease have a look at\n\n\thttps://github.com/git/git/pull/447\n\nShort version: for a commit topology like this:\n\n\tA - B - C\n\t \\ /\n\t D\n\nthe generated list would look like this:\n\n\t# branch D\n\tpick 0123 A\n\tlabel branch-point\n\tpick 1234 D\n\tlabel D\n\n\treset branch-point\n\tpick 2345 B\n\tmerge 3456 D C\n\nCiao,\nDscho\n"},{"id":"336403","messageId":"2648064.NJaMxHkljU@mfick-lnx","threadId":"47560","inReplyTo":"20180107181459.222909-1-dstolee@microsoft.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2018-01-10T18:25:47Z","receivedAt":"2018-01-10T18:25:55Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Sunday, January 07, 2018 01:14:41 PM Derrick Stolee \nwrote:\n> This RFC includes a new way to index the objects in\n> multiple packs using one file, called the multi-pack\n> index (MIDX).\n...\n> The main goals of this RFC are:\n> \n> * Determine interest in this feature.\n> \n> * Find other use cases for the MIDX feature.\n\nMy interest in this feature would be to speed up fetches \nwhen there is more than one large pack-file with many of the \nsame objects that are in other pack-files. What does your \nMIDX design do when it encounters multiple copies of the \nsame object in different pack files? Does it index them all, \nor does it keep a single copy?\n\nIn our Gerrit instance (Gerrit uses jgit), we have multiple \ncopies of the linux kernel repos linked together via the \nalternatives file mechanism. These repos have many different \nreferences (mostly Gerrit change references), but they share \nmost of the common objects from the mainline. I have found \nthat during a large fetch such as a clone, jgit spends a \nsignificant amount of extra time by having the extra large \npack-files from the other repos visible to it, usually around \nan extra minute per instance of these (without them, the \nclone takes around 7mins). This adds up easily with a few \nrepos extra repos, it can almost double the time.\n\nMy investigations have shown that this is due to jgit \nsearching each of these pack files to decide which version of \neach object to send. I don't fully understand its selection \ncriteria, however if I shortcut it to just pick the first \ncopy of an object that it finds, I regain my lost time. I \ndon't know if git suffers from a similar problem? If git \ndoesn't suffer from this then it likely just uses the first \ncopy of an object it finds (which may not be the best object \nto send?)\n\nIt would be nice if this use case could be improved with \nMIDX. To do so, it seems that it would either require that \nMIDX either only put \"the best\" version of an object (i.e. \npre-select which one to use), or include the extra \ninformation to help make the selection process of which copy \nto use (perhaps based on the operation being performed) \nfast.\n\nThis also leads me to ask, what other additional information \n(bitmaps?) for other operations, besides object location, \nmight suddenly be valuable in an index that potentially \npoints to multiple copies of objects? Would such \ninformation be appropriate in MIDX, or would it be better in \nanother index?\n\nThanks,\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n\n"},{"id":"336411","messageId":"7b3df316-8a35-0dcf-da17-64202f600821@gmail.com","threadId":"47560","inReplyTo":"2648064.NJaMxHkljU@mfick-lnx","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-01-10T19:39:13Z","receivedAt":"2018-01-10T19:39:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/10/2018 1:25 PM, Martin Fick wrote:\n> On Sunday, January 07, 2018 01:14:41 PM Derrick Stolee\n> wrote:\n>> This RFC includes a new way to index the objects in\n>> multiple packs using one file, called the multi-pack\n>> index (MIDX).\n> ...\n>> The main goals of this RFC are:\n>>\n>> * Determine interest in this feature.\n>>\n>> * Find other use cases for the MIDX feature.\n> My interest in this feature would be to speed up fetches\n> when there is more than one large pack-file with many of the\n> same objects that are in other pack-files. What does your\n> MIDX design do when it encounters multiple copies of the\n> same object in different pack files? Does it index them all,\n> or does it keep a single copy?\n\nThe MIDX currently keeps only one reference to each object. Duplicates \nare dropped during writing. (See the care taken in commit 04/18 to avoid \nduplicates.) Since midx_sha1_compare() does not use anything other than \nthe OID to order the objects, there is no decision being made about \nwhich pack is \"better\". The MIDX writes the first copy it finds and \ndiscards the others.\n\nIt would not be difficult to include a check in midx_sha1_compare() to \nfavor one packfile over another based on some measurement (size? \nmtime?). Since this would be a heuristic at best, I left it out of the \ncurrent patch.\n\n> In our Gerrit instance (Gerrit uses jgit), we have multiple\n> copies of the linux kernel repos linked together via the\n> alternatives file mechanism.\n\nGVFS also uses alternates for sharing packfiles across multiple copies \nof the repo. The MIDX is designed to cover all packfiles in the same \ndirectory, but is not designed to cover packfiles in multiple \nalternates; currently, each alternate would need its own MIDX file. Does \nthat cause issues with your setup?\n\n> These repos have many different\n> references (mostly Gerrit change references), but they share\n> most of the common objects from the mainline. I have found\n> that during a large fetch such as a clone, jgit spends a\n> significant amount of extra time by having the extra large\n> pack-files from the other repos visible to it, usually around\n> an extra minute per instance of these (without them, the\n> clone takes around 7mins). This adds up easily with a few\n> repos extra repos, it can almost double the time.\n>\n> My investigations have shown that this is due to jgit\n> searching each of these pack files to decide which version of\n> each object to send. I don't fully understand its selection\n> criteria, however if I shortcut it to just pick the first\n> copy of an object that it finds, I regain my lost time. I\n> don't know if git suffers from a similar problem? If git\n> doesn't suffer from this then it likely just uses the first\n> copy of an object it finds (which may not be the best object\n> to send?)\n>\n> It would be nice if this use case could be improved with\n> MIDX. To do so, it seems that it would either require that\n> MIDX either only put \"the best\" version of an object (i.e.\n> pre-select which one to use), or include the extra\n> information to help make the selection process of which copy\n> to use (perhaps based on the operation being performed)\n> fast.\n\nI'm not sure if there is sufficient value in storing multiple references \nto the same object stored in multiple packfiles. There could be value in \ncarefully deciding which copy is \"best\" during the MIDX write, but \nduring read is not a good time to make such a decision. It also \nincreases the size of the file to store multiple copies.\n\n> This also leads me to ask, what other additional information\n> (bitmaps?) for other operations, besides object location,\n> might suddenly be valuable in an index that potentially\n> points to multiple copies of objects? Would such\n> information be appropriate in MIDX, or would it be better in\n> another index?\n\nFor applications to bitmaps, it is probably best that we only include \none copy of each object. Otherwise, we need to include extra bits in the \nbitmaps for those copies (when asking \"is this object in the bitmap?\").\n\nThanks for the context with Gerrit's duplicate object problem. I'll try \nto incorporate it in to the design document (commit 01/18) for the v1 patch.\n\nThanks,\n-Stolee\n\n"},{"id":"336425","messageId":"7273121.kKAycuMGzH@mfick-lnx","threadId":"47560","inReplyTo":"7b3df316-8a35-0dcf-da17-64202f600821@gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2018-01-10T21:01:28Z","receivedAt":"2018-01-10T21:01:37Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Wednesday, January 10, 2018 02:39:13 PM Derrick Stolee \nwrote:\n> On 1/10/2018 1:25 PM, Martin Fick wrote:\n> > On Sunday, January 07, 2018 01:14:41 PM Derrick Stolee\n> > \n> > wrote:\n> >> This RFC includes a new way to index the objects in\n> >> multiple packs using one file, called the multi-pack\n> >> index (MIDX).\n> > \n> > ...\n> > \n> >> The main goals of this RFC are:\n> >> \n> >> * Determine interest in this feature.\n> >> \n> >> * Find other use cases for the MIDX feature.\n> > \n> > My interest in this feature would be to speed up fetches\n> > when there is more than one large pack-file with many of\n> > the same objects that are in other pack-files. What\n> > does your MIDX design do when it encounters multiple\n> > copies of the same object in different pack files? \n> > Does it index them all, or does it keep a single copy?\n> \n> The MIDX currently keeps only one reference to each\n> object. Duplicates are dropped during writing. (See the\n> care taken in commit 04/18 to avoid duplicates.) Since\n> midx_sha1_compare() does not use anything other than the\n> OID to order the objects, there is no decision being made\n> about which pack is \"better\". The MIDX writes the first\n> copy it finds and discards the others.\n\nThis would likely speed things up then, even if the chosen \nobjects are suboptimal.\n\n> It would not be difficult to include a check in\n> midx_sha1_compare() to favor one packfile over another\n> based on some measurement (size? mtime?). Since this\n> would be a heuristic at best, I left it out of the\n> current patch.\n\nYeah, I didn't know what heuristic to use either, I tended \nto think that the bigger pack-file would be valuable because \nit is more likely to share deltas with other objects in that \npack, so more easy to send them. However, that is likely \nonly true during clones or other large fetches when we want \nmost objects. During small \"update\" fetches, the newer \npacks might be better?\n\nI also thought that objects in alternates should be \nconsidered less valuable for my use case, however in the \ngithub fork use case, the alternates might be more valuable?\n\nSo yes heuristics, and I don't know what is best. Perhaps \nsome config options could be used to set heuristics like \nthis. Whatever the heuristics are, since they would be a \npart of the MIDX packing process it would be easy to change. \nThis assumes that keeping only one copy in the index is the \nright thing. The question would be, what if we need \ndifferent heuristics for different operations? Would it make \nsense to have multiple MIDX files covering the same packs \nthen, one for fetch, one for merge...?\n\n> > In our Gerrit instance (Gerrit uses jgit), we have\n> > multiple copies of the linux kernel repos linked\n> > together via the alternatives file mechanism.\n> \n> GVFS also uses alternates for sharing packfiles across\n> multiple copies of the repo. The MIDX is designed to\n> cover all packfiles in the same directory, but is not\n> designed to cover packfiles in multiple alternates;\n> currently, each alternate would need its own MIDX file.\n> Does that cause issues with your setup?\n\nNo, since the other large packfiles are all in other repos \n(alternates). Is there a reason the MIDX would not want to \ncover the alternates? If you don't then you would seemingly \nloose any benefits of the MIDX when you have alternates in \nuse.\n\n...\n> > It would be nice if this use case could be improved with\n> > MIDX. To do so, it seems that it would either require\n> > that MIDX either only put \"the best\" version of an\n> > object (i.e. pre-select which one to use), or include\n> > the extra information to help make the selection\n> > process of which copy to use (perhaps based on the\n> > operation being performed) fast.\n> \n> I'm not sure if there is sufficient value in storing\n> multiple references to the same object stored in multiple\n> packfiles. There could be value in carefully deciding\n> which copy is \"best\" during the MIDX write, but during\n> read is not a good time to make such a decision. It also\n> increases the size of the file to store multiple copies.\n\nYes, I am not sure either, it would be good to have input \nfrom experts here.\n\n> > This also leads me to ask, what other additional\n> > information (bitmaps?) for other operations, besides\n> > object location, might suddenly be valuable in an index\n> > that potentially points to multiple copies of objects? \n> > Would such information be appropriate in MIDX, or would\n> > it be better in another index?\n> \n> For applications to bitmaps, it is probably best that we\n> only include one copy of each object. Otherwise, we need\n> to include extra bits in the bitmaps for those copies\n> (when asking \"is this object in the bitmap?\").\n\nAgreed. Would the MIDX potentially pave the way to create \nmulti-pack bitmaps?\n\n> Thanks for the context with Gerrit's duplicate object\n> problem. I'll try to incorporate it in to the design\n> document (commit 01/18) for the v1 patch.\n\nFYI, this is not a typical Gerrit thing, it is something \nspecial we do in our installation.\n\nThanks for your thoughts,\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n\n"},{"id":"349462","messageId":"87lgbsz61p.fsf@evledraar.gmail.com","threadId":"47560","inReplyTo":"c08416f1-bbec-2037-34a6-f454d85de439@gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-06T08:13:22Z","receivedAt":"2018-06-06T08:13:30Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Jan 08 2018, Derrick Stolee wrote:\n\n> On 1/7/2018 5:42 PM, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Sun, Jan 07 2018, Derrick Stolee jotted:\n>>\n>>> git log --oneline --raw --parents\n>>>\n>>> Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n>>> ----------+-------------+------------+--------+----------\n>>> 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n>>> 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n>>> 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n>>>\n>>> The last column is the relative difference between the MIDX-enabled repo\n>>> and the single-pack repo. The goal of the MIDX feature is to present the\n>>> ODB as if it was fully repacked, so there is still room for improvement.\n>>>\n>>> Changing the command to\n>>>\n>>> git log --oneline --raw --parents --abbrev=40\n>>>\n>>> has no observable difference (sub 1% change in all cases). This is likely\n>>> due to the repack I used putting commits and trees in a small number of\n>>> packfiles so the MRU cache workes very well. On more naturally-created\n>>> lists of packfiles, there can be up to 20% improvement on this command.\n>>>\n>>> We are using a version of this patch with an upcoming release of GVFS.\n>>> This feature is particularly important in that space since GVFS performs\n>>> a \"prefetch\" step that downloads a pack of commits and trees on a daily\n>>> basis. These packfiles are placed in an alternate that is shared by all\n>>> enlistments. Some users have 150+ packfiles and the MRU misses and\n>>> abbreviation computations are significant. Now, GVFS manages the MIDX file\n>>> after adding new prefetch packfiles using the following command:\n>>>\n>>> git midx --write --update-head --delete-expired --pack-dir=\n>>\n>> (Not a critique of this, just a (stupid) question)\n>>\n>> What's the practical use-case for this feature? Since it doesn't help\n>> with --abbrev=40 the speedup is all in the part that ensures we don't\n>> show an ambiguous SHA-1.\n>\n> The point of including the --abbrev=40 is to point out that object\n> lookups do not get slower with the MIDX feature. Using these \"git log\"\n> options is a good way to balance object lookups and abbreviations with\n> object parsing and diff machinery.[...]\n\n[snip]\n\n> [...]And while the public data shape I shared did not show a\n> difference, our private testing of the Windows repository did show a\n> valuable improvement when isolating to object lookups and ignoring\n> abbreviation calculations.\n\nReplying to this old thread since I see you're prepearing the MIDX for\nsubmission again and this seemed like the best venue.\n\nYour WIP branch (github.com/git/derrickstolee/midx/upstream) still only\nreferences the speedups in abbreviation calculations, but here you\nallude to other improvements. It would be very nice to have some summary\nof that in docs / commit messages when you submit this.\n\nI've been meaning to get around to submitting something like I mentioned\nin https://public-inbox.org/git/87efn0bkls.fsf@evledraar.gmail.com/\ni.e. a way to expand the abbrev mode to not check disambiguations, which\nwould look something like:\n\n core.abbrev = 20\n core.validateAbbrev = false\n\nOr:\n\n core.abbrev = +2\n core.validateAbbrev = false\n\nSo, using the example from the above referenced E-Mail +2 would make\nlinux.git emit hashes of 14 characters, without any abbreviation\nchecking (just trusting in statistics to work in your favor).\n\nAs noted by JS in this thread that wouldn't be acceptable for your\nuse-case, but there's plenty of people (including me) who'd appreciate\nthe speedup without being a 100% sure we're emitting unambiguous hashes,\nsince that trade-off is better than time spent generating another index\non-disk. So I see it as a complimentary & orthogonal feature.\n\nBut with that implemented I wouldn't get any benefit from things that\nuse the MIDX that aren't abbreviations, so what are those?\n\n>> The reason we do that at all is because it makes for a prettier UI.\n>\n> We tried setting core.abbrev=40 on GVFS enlistments to speed up\n> performance and the users rebelled against the hideous output. They\n> would rather have slower speeds than long hashes.\n>\n>> Are there things that both want the pretty SHA-1 and also care about the\n>> throughput? I'd have expected machine parsing to just use\n>> --no-abbrev-commit.\n>\n> The --raw flag outputs blob hashes, so the --abbrev=40 covers all hashes.\n>\n>> If something cares about both throughput and e.g. is saving the\n>> abbreviated SHA-1s isn't it better off picking some arbitrary size\n>> (e.g. --abbrev=20), after all the default abbreviation is going to show\n>> something as small as possible, which may soon become ambigous after the\n>> next commit.\n>\n> Unfortunately, with the way the abbreviation algorithms work, using\n> --abbrev=20 will have similar performance problems because you still\n> need to inspect all packfiles to ensure there isn't a collision in the\n> first 20 hex characters.\n>\n> Thanks,\n> -Stolee\n"},{"id":"349467","messageId":"20180606102719.27145-1-avarab@gmail.com","threadId":"47560","inReplyTo":"87lgbsz61p.fsf@evledraar.gmail.com","subject":"[RFC PATCH 0/2] unconditional O(1) SHA-1 abbreviation","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-06T10:27:17Z","receivedAt":"2018-06-06T10:27:35Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Wed, Jun 06 2018, Ævar Arnfjörð Bjarmason wrote:\n\n> On Mon, Jan 08 2018, Derrick Stolee wrote:\n>\n>> On 1/7/2018 5:42 PM, Ævar Arnfjörð Bjarmason wrote:\n>>>\n>>> On Sun, Jan 07 2018, Derrick Stolee jotted:\n>>>\n>>>> git log --oneline --raw --parents\n>>>>\n>>>> Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n>>>> ----------+-------------+------------+--------+----------\n>>>> 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n>>>> 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n>>>> 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n>>>>\n>>>> The last column is the relative difference between the MIDX-enabled repo\n>>>> and the single-pack repo. The goal of the MIDX feature is to present the\n>>>> ODB as if it was fully repacked, so there is still room for improvement.\n>>>>\n>>>> Changing the command to\n>>>>\n>>>> git log --oneline --raw --parents --abbrev=40\n>>>>\n>>>> has no observable difference (sub 1% change in all cases). This is likely\n>>>> due to the repack I used putting commits and trees in a small number of\n>>>> packfiles so the MRU cache workes very well. On more naturally-created\n>>>> lists of packfiles, there can be up to 20% improvement on this command.\n>>>>\n>>>> We are using a version of this patch with an upcoming release of GVFS.\n>>>> This feature is particularly important in that space since GVFS performs\n>>>> a \"prefetch\" step that downloads a pack of commits and trees on a daily\n>>>> basis. These packfiles are placed in an alternate that is shared by all\n>>>> enlistments. Some users have 150+ packfiles and the MRU misses and\n>>>> abbreviation computations are significant. Now, GVFS manages the MIDX file\n>>>> after adding new prefetch packfiles using the following command:\n>>>>\n>>>> git midx --write --update-head --delete-expired --pack-dir=\n>>>\n>>> (Not a critique of this, just a (stupid) question)\n>>>\n>>> What's the practical use-case for this feature? Since it doesn't help\n>>> with --abbrev=40 the speedup is all in the part that ensures we don't\n>>> show an ambiguous SHA-1.\n>>\n>> The point of including the --abbrev=40 is to point out that object\n>> lookups do not get slower with the MIDX feature. Using these \"git log\"\n>> options is a good way to balance object lookups and abbreviations with\n>> object parsing and diff machinery.[...]\n>\n> [snip]\n>\n>> [...]And while the public data shape I shared did not show a\n>> difference, our private testing of the Windows repository did show a\n>> valuable improvement when isolating to object lookups and ignoring\n>> abbreviation calculations.\n>\n> Replying to this old thread since I see you're prepearing the MIDX for\n> submission again and this seemed like the best venue.\n>\n> Your WIP branch (github.com/git/derrickstolee/midx/upstream) still only\n> references the speedups in abbreviation calculations, but here you\n> allude to other improvements. It would be very nice to have some summary\n> of that in docs / commit messages when you submit this.\n>\n> I've been meaning to get around to submitting something like I mentioned\n> in https://public-inbox.org/git/87efn0bkls.fsf@evledraar.gmail.com/\n> i.e. a way to expand the abbrev mode to not check disambiguations, which\n> would look something like:\n>\n> core.abbrev = 20\n> core.validateAbbrev = false\n>\n> Or:\n>\n> core.abbrev = +2\n> core.validateAbbrev = false\n>\n> So, using the example from the above referenced E-Mail +2 would make\n> linux.git emit hashes of 14 characters, without any abbreviation\n> checking (just trusting in statistics to work in your favor).\n>\n> As noted by JS in this thread that wouldn't be acceptable for your\n> use-case, but there's plenty of people (including me) who'd appreciate\n> the speedup without being a 100% sure we're emitting unambiguous hashes,\n> since that trade-off is better than time spent generating another index\n> on-disk. So I see it as a complimentary & orthogonal feature.\n>\n> But with that implemented I wouldn't get any benefit from things that\n> use the MIDX that aren't abbreviations, so what are those?\n\nI won't have time to finish this today, but it's already in a shape\nthat I think is useful for discussion to see what others think.\n\nI still need to make this be supported by --abbrev=* and have\ne.g. --abbrev=+2 work. I got as far as this with that:\n\n diff --git a/parse-options-cb.c b/parse-options-cb.c\n index 0f9f311a7a..7cc9d3dfe6 100644\n --- a/parse-options-cb.c\n +++ b/parse-options-cb.c\n @@ -16,13 +16,23 @@ int parse_opt_abbrev_cb(const struct option *opt, const char *arg, int unset)\n \tif (!arg) {\n \t\tv = unset ? 0 : DEFAULT_ABBREV;\n \t} else {\n +\t\tconst char *origarg = arg;\n \t\tv = strtol(arg, (char **)&arg, 10);\n \t\tif (*arg)\n \t\t\treturn opterror(opt, \"expects a numerical value\", 0);\n -\t\tif (v && v < MINIMUM_ABBREV)\n +\t\tif (*origarg == '+' || *origarg == '-') {\n +\t\t\tif (v == 0) {\n +\t\t\t\treturn opterror(opt, \"relative abbrev must be non-zero\", 0);\n +\t\t\t} else {\n +\t\t\t\tdefault_abbrev_relative = v;\n +\t\t\t\tv = -1;\n +\t\t\t}\n +\t\t} else if (v && v < MINIMUM_ABBREV) {\n \t\t\tv = MINIMUM_ABBREV;\n -\t\telse if (v > 40)\n +\t\t} else if (v > 40) {\n \t\t\tv = 40;\n +\t\t}\n \t}\n \t*(int *)(opt->value) = v;\n \treturn 0;\n\nBut e.g. blame would print 40 character SHA-1s on +2, I didn't have\ntime to dig into why.\n\nThis'll also need tests, I haven't added any yet, and finally it's\nprobably a good idea to split off the core.abbrev=[+-]NUM feature into\na seperate patch from core.validateAbbrev, although with my 2/2 the\ntwo can be used in isolation, or together.\n\nÆvar Arnfjörð Bjarmason (2):\n config.c: use braces on multiple conditional arms\n sha1-name: add core.validateAbbrev & relative core.abbrev\n\n Documentation/config.txt | 46 ++++++++++++++++++++++++++++++++++++++++\n cache.h | 2 ++\n config.c | 18 ++++++++++++++--\n environment.c | 2 ++\n sha1-name.c | 15 +++++++++++++\n 5 files changed, 81 insertions(+), 2 deletions(-)\n\n-- \n2.17.0.290.gded63e768a\n\n"},{"id":"349468","messageId":"20180606102719.27145-2-avarab@gmail.com","threadId":"47560","inReplyTo":"20180606102719.27145-1-avarab@gmail.com","subject":"[RFC PATCH 1/2] config.c: use braces on multiple conditional arms","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-06T10:27:18Z","receivedAt":"2018-06-06T10:27:36Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Adjust this code that'll be modified in a subsequent change per the\nCodingGuidelines.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n config.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/config.c b/config.c\nindex fbbf0f8e9f..12f762ad92 100644\n--- a/config.c\n+++ b/config.c\n@@ -1149,9 +1149,9 @@ static int git_default_core_config(const char *var, const char *value)\n \tif (!strcmp(var, \"core.abbrev\")) {\n \t\tif (!value)\n \t\t\treturn config_error_nonbool(var);\n-\t\tif (!strcasecmp(value, \"auto\"))\n+\t\tif (!strcasecmp(value, \"auto\")) {\n \t\t\tdefault_abbrev = -1;\n-\t\telse {\n+\t\t} else {\n \t\t\tint abbrev = git_config_int(var, value);\n \t\t\tif (abbrev < minimum_abbrev || abbrev > 40)\n \t\t\t\treturn error(\"abbrev length out of range: %d\", abbrev);\n-- \n2.17.0.290.gded63e768a\n\n"},{"id":"349469","messageId":"20180606102719.27145-3-avarab@gmail.com","threadId":"47560","inReplyTo":"20180606102719.27145-1-avarab@gmail.com","subject":"[RFC PATCH 2/2] sha1-name: add core.validateAbbrev & relative core.abbrev","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-06T10:27:19Z","receivedAt":"2018-06-06T10:27:39Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Since Linus added auto-sizing for abbreviations in\ne6c587c733 (\"abbrev: auto size the default abbreviation\", 2016-09-30)\nwe've been less likely to produce a short SHA-1 today that'll collide\non the same repository tomorrow, since before we'd always pick the\nbare minimum we could get away with.\n\nBut we still do a full disambiguation check, which can be very\nexpensive in some cases. There's a work-in-progress MIDX\nimplementation to address that[1].\n\nThis change adds an alternate method of achieving some of the same\nends (but possibly not all, see [2] and replies to the original thread\nat [1]).\n\nNow, as described in the docs the user can set a relative abbreviation\nlength via core.abbrev, e.g. on linux.git core.abbrev=+2 will produce\nSHA-1s that are 14 characters (as opposed to the implicit 12).\n\nThis in combination with core.validateAbbrev=false (off by default)\nallows for picking a trade-off between performance, and the odds that\nfuture or remote (or current and local) short SHA-1 will be ambiguous.\n\n1. https://public-inbox.org/git/20180107181459.222909-1-dstolee@microsoft.com/\n2. https://public-inbox.org/git/87lgbsz61p.fsf@evledraar.gmail.com/\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n Documentation/config.txt | 46 ++++++++++++++++++++++++++++++++++++++++\n cache.h | 2 ++\n config.c | 14 ++++++++++++\n environment.c | 2 ++\n sha1-name.c | 15 +++++++++++++\n 5 files changed, 79 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex ab641bf5a9..8624110818 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -919,6 +919,52 @@ core.abbrev::\n \tin your repository, which hopefully is enough for\n \tabbreviated object names to stay unique for some time.\n \tThe minimum length is 4.\n++\n+This can also be set to relative values such as `+2` or `-2`, which\n+means to add or subtract N characters from the SHA-1 that Git would\n+otherwise print. This is useful in combination with the\n+`core.validateAbbrev` setting, or to get more future-proof hashes to\n+reference in the future in a repository whose number of objects is\n+expected to grow.\n+\n+core.validateAbbrev::\n+\tIf set to false (true by default) don't do any validation when\n+\tprinting abbreviated object names to see if they're really\n+\tunique. This makes printing objects more performant at the\n+\tcost of potentially printing object names that aren't unique\n+\twithin the current repository.\n++\n+When printing abbreviated object names Git needs to look through the\n+local object store. This is an `O(log N)` operation assuming all the\n+objects are in a single pack file, but `X * O(log N)` given `X` pack\n+files, which can get expensive on some larger repositories.\n++\n+This setting changes that to `O(1)`, but with the trade-off that\n+depending on the value of `core.abbrev` way may be printing\n+abbreviated hashes that collide. Too see how likely this is, try\n+running:\n++\n+-----------------------------------------------------------------------------------------------------------\n+git log --all --pretty=format:%h --abbrev=4 | perl -nE 'chomp; say length' | sort | uniq -c | sort -nr\n+-----------------------------------------------------------------------------------------------------------\n++\n+This shows how many commits were found at each abbreviation length. On\n+linux.git in June 2018 this shows a bit more than 750,000 commits,\n+with just 4 needing 11 characters to be fully abbreviated, and the\n+default heuristic picks a length of 12.\n++\n+Even without `core.validateAbbrev=false` the results abbreviation\n+already a bit of a probability game. They're guaranteed at the moment\n+of generation, but as more objects are added, ambiguities may be\n+introduced. Likewise, what's unambiguous for you may not be for\n+somebody else you're communicating with, if they have their own clone.\n++\n+Therefore the default of `core.validateAbbrev=true` may not save you\n+in practice if you're sharing the SHA-1 or noting it now to use after\n+a `git fetch`. You may be better off setting `core.abbrev` to\n+e.g. `+2` to add 2 extra characters to the SHA-1 in combination with\n+`core.validateAbbrev=false` to get a reasonable trade-off between\n+safety and performance.\n \n add.ignoreErrors::\n add.ignore-errors (deprecated)::\ndiff --git a/cache.h b/cache.h\nindex 89a107a7f7..6dc5af9482 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -772,6 +772,8 @@ extern int check_stat;\n extern int quote_path_fully;\n extern int has_symlinks;\n extern int minimum_abbrev, default_abbrev;\n+extern int default_abbrev_relative;\n+extern int validate_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n extern int prefer_symlink_refs;\ndiff --git a/config.c b/config.c\nindex 12f762ad92..b6e0d17af1 100644\n--- a/config.c\n+++ b/config.c\n@@ -1146,11 +1146,25 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.validateabbrev\")) {\n+\t\tif (!value)\n+\t\t\treturn config_error_nonbool(var);\n+\t\tvalidate_abbrev = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.abbrev\")) {\n \t\tif (!value)\n \t\t\treturn config_error_nonbool(var);\n \t\tif (!strcasecmp(value, \"auto\")) {\n \t\t\tdefault_abbrev = -1;\n+\t\t} else if (*value == '+' || *value == '-') {\n+\t\t\tint relative = git_config_int(var, value);\n+\t\t\tif (relative == 0)\n+\t\t\t\tdie(_(\"bad core.abbrev value %s. \"\n+\t\t\t\t \"relative values must be non-zero\"),\n+\t\t\t\t value);\n+\t\t\tdefault_abbrev_relative = relative;\n \t\t} else {\n \t\t\tint abbrev = git_config_int(var, value);\n \t\t\tif (abbrev < minimum_abbrev || abbrev > 40)\ndiff --git a/environment.c b/environment.c\nindex 2a6de2330b..4a24d8126b 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -22,6 +22,8 @@ int trust_ctime = 1;\n int check_stat = 1;\n int has_symlinks = 1;\n int minimum_abbrev = 4, default_abbrev = -1;\n+int default_abbrev_relative = 0;\n+int validate_abbrev = 1;\n int ignore_case;\n int assume_unchanged;\n int prefer_symlink_refs;\ndiff --git a/sha1-name.c b/sha1-name.c\nindex 60d9ef3c7e..aa7ccea14d 100644\n--- a/sha1-name.c\n+++ b/sha1-name.c\n@@ -576,6 +576,7 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n \tstruct disambiguate_state ds;\n \tstruct min_abbrev_data mad;\n \tstruct object_id oid_ret;\n+\tint dar = default_abbrev_relative;\n \tif (len < 0) {\n \t\tunsigned long count = approximate_object_count();\n \t\t/*\n@@ -602,6 +603,20 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n \tif (len == GIT_SHA1_HEXSZ || !len)\n \t\treturn GIT_SHA1_HEXSZ;\n \n+\tif (dar) {\n+\t\tif (len + dar < MINIMUM_ABBREV) {\n+\t\t\tlen = MINIMUM_ABBREV;\n+\t\t\tdar = 0;\n+\t\t}\n+\n+\t\tif (validate_abbrev) {\n+\t\t\tlen += dar;\n+\t\t} else {\n+\t\t\thex[len + dar] = 0;\n+\t\t\treturn len + dar;\n+\t\t}\n+\t}\n+\n \tmad.init_len = len;\n \tmad.cur_len = len;\n \tmad.hex = hex;\n-- \n2.17.0.290.gded63e768a\n\n"},{"id":"349472","messageId":"e8cc9269-39b0-119d-80d6-dc62807fda67@gmail.com","threadId":"47560","inReplyTo":"87lgbsz61p.fsf@evledraar.gmail.com","subject":"Re: [RFC PATCH 00/18] Multi-pack index (MIDX)","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-06T11:24:13Z","receivedAt":"2018-06-06T11:24:18Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/6/2018 4:13 AM, Ævar Arnfjörð Bjarmason wrote:\n> On Mon, Jan 08 2018, Derrick Stolee wrote:\n>\n>> On 1/7/2018 5:42 PM, Ævar Arnfjörð Bjarmason wrote:\n>>> On Sun, Jan 07 2018, Derrick Stolee jotted:\n>>>\n>>>> git log --oneline --raw --parents\n>>>>\n>>>> Num Packs | Before MIDX | After MIDX | Rel % | 1 pack %\n>>>> ----------+-------------+------------+--------+----------\n>>>> 1 | 35.64 s | 35.28 s | -1.0% | -1.0%\n>>>> 24 | 90.81 s | 40.06 s | -55.9% | +12.4%\n>>>> 127 | 257.97 s | 42.25 s | -83.6% | +18.6%\n>>>>\n>>>> The last column is the relative difference between the MIDX-enabled repo\n>>>> and the single-pack repo. The goal of the MIDX feature is to present the\n>>>> ODB as if it was fully repacked, so there is still room for improvement.\n>>>>\n>>>> Changing the command to\n>>>>\n>>>> git log --oneline --raw --parents --abbrev=40\n>>>>\n>>>> has no observable difference (sub 1% change in all cases). This is likely\n>>>> due to the repack I used putting commits and trees in a small number of\n>>>> packfiles so the MRU cache workes very well. On more naturally-created\n>>>> lists of packfiles, there can be up to 20% improvement on this command.\n>>>>\n>>>> We are using a version of this patch with an upcoming release of GVFS.\n>>>> This feature is particularly important in that space since GVFS performs\n>>>> a \"prefetch\" step that downloads a pack of commits and trees on a daily\n>>>> basis. These packfiles are placed in an alternate that is shared by all\n>>>> enlistments. Some users have 150+ packfiles and the MRU misses and\n>>>> abbreviation computations are significant. Now, GVFS manages the MIDX file\n>>>> after adding new prefetch packfiles using the following command:\n>>>>\n>>>> git midx --write --update-head --delete-expired --pack-dir=\n>>> (Not a critique of this, just a (stupid) question)\n>>>\n>>> What's the practical use-case for this feature? Since it doesn't help\n>>> with --abbrev=40 the speedup is all in the part that ensures we don't\n>>> show an ambiguous SHA-1.\n>> The point of including the --abbrev=40 is to point out that object\n>> lookups do not get slower with the MIDX feature. Using these \"git log\"\n>> options is a good way to balance object lookups and abbreviations with\n>> object parsing and diff machinery.[...]\n> [snip]\n>\n>> [...]And while the public data shape I shared did not show a\n>> difference, our private testing of the Windows repository did show a\n>> valuable improvement when isolating to object lookups and ignoring\n>> abbreviation calculations.\n> Replying to this old thread since I see you're prepearing the MIDX for\n> submission again and this seemed like the best venue.\n\nYou're really good at tracking new commits in my GitHub page ;)\n\n>\n> Your WIP branch (github.com/git/derrickstolee/midx/upstream) still only\n> references the speedups in abbreviation calculations, but here you\n> allude to other improvements. It would be very nice to have some summary\n> of that in docs / commit messages when you submit this.\n\nThe new version is essentially a complete rewrite of the feature, since \nwe learned a lot about how to add a new data store from the commit-graph \nseries. The design document [1] refers to some of the immediate benefits \nand future benefits. Some of these future benefits were discussed at the \ncontributor's summit [2].\n\n[1] \nhttps://github.com/derrickstolee/git/blob/midx/upstream/Documentation/technical/midx.txt\n\n[2] \nhttps://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n     Git Merge 2018 Contributor's summit notes (includes discussion of MIDX)\n\n>\n> I've been meaning to get around to submitting something like I mentioned\n> in https://public-inbox.org/git/87efn0bkls.fsf@evledraar.gmail.com/\n> i.e. a way to expand the abbrev mode to not check disambiguations, which\n> would look something like:\n>\n> core.abbrev = 20\n> core.validateAbbrev = false\n>\n> Or:\n>\n> core.abbrev = +2\n> core.validateAbbrev = false\n>\n> So, using the example from the above referenced E-Mail +2 would make\n> linux.git emit hashes of 14 characters, without any abbreviation\n> checking (just trusting in statistics to work in your favor).\n>\n> As noted by JS in this thread that wouldn't be acceptable for your\n> use-case, but there's plenty of people (including me) who'd appreciate\n> the speedup without being a 100% sure we're emitting unambiguous hashes,\n> since that trade-off is better than time spent generating another index\n> on-disk. So I see it as a complimentary & orthogonal feature.\n>\n> But with that implemented I wouldn't get any benefit from things that\n> use the MIDX that aren't abbreviations, so what are those?\n\nThe MIDX is built for handling many packfiles. As opposed to the \ncommit-graph feature, your repo needs to be _really_big_ to need the \nMIDX. Most just repack into one packfile on a regular basis.\n\nOne case for vanilla Git: we've heard from lots of customers disabling \ngc.auto in their build machines because they didn't want to wait for a \nrepack/gc after a fetch and before a build. Then, they end up in a \nmany-pack situation because they never scheduled time for that repack/gc.\n\nFor GVFS, we virtualize the repo, so objects can be downloaded from the \nserver on-demand. Since round-trips to the server are expensive, we have \nthe notion of a \"prefetch pack\". Our cache servers precompute packfiles \ncontaining all of the commits and trees introduced to the server that \nday. On a 'git fetch' command, GVFS intercepts via a hook and downloads \nthe list of daily prefetch packs since the last prefetch. These are \nplaced in an alternate (the \"shared object cache\"), so multiple \nenlistments can point to the same, fixed list of packs. The cache \nservers fold these packs together after 30 days, so users on a fresh \nclone start with 31 packs and users who go on vacation for a month get \nat most 31 packs in a single download.\n\nThe performance gains from the MIDX for abbrevations are the easiest to \ndemonstrate. It's not hard to see why the single binary search to find \nthe two closest OIDs is better than iterating through all of the \npackfiles and running a binary search on each.\n\nThe other thing that the MIDX does right now is be a single source for \nobject lookups. This is harder to demonstrate the benefit in Git on its \nown, because using `git repack -adfF --max-pack-size=128m` repacks in a \n\"good\" way. This repack actually makes the MRU packfile list really \neffective.\n\nOne reason the MIDX is important for object lookups in the GVFS case is \ntwo-fold:\n\n1. The time-based organization of the prefetch packs makes the trees \nnecessary for a 'checkout' spread across many packfiles. Even with the \nworking directory virtualization, every 'checkout' needs to recompute \nthe .git/index, and that requires walking lots of trees.\n\n2. When we are looking for a blob that is not in the local cache, we \nneed to check that the blob is on-disk before requesting it from the \nserver. In a many-pack scenario, those object misses are as expensive as \nthe abbreviation case. This may affect partial clone, so I'll talk with \nJeff H about that situation.\n\nI expect to send my v1 today. I'm just trying to create a synthetic \nenvironment that demonstrates this benefit to object lookups using the \nLinux repository.\n\nThanks,\n-Stolee\n"},{"id":"349497","messageId":"CAP8UFD1VcQceStBFp9A_j5ts5W2GT12n=jE91osHvhYqKPGrHA@mail.gmail.com","threadId":"47560","inReplyTo":"20180606102719.27145-3-avarab@gmail.com","subject":"Re: [RFC PATCH 2/2] sha1-name: add core.validateAbbrev & relative core.abbrev","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-06-06T12:04:59Z","receivedAt":"2018-06-06T12:05:03Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Wed, Jun 6, 2018 at 12:27 PM, Ævar Arnfjörð Bjarmason\n wrote:\n\n> +This setting changes that to `O(1)`, but with the trade-off that\n> +depending on the value of `core.abbrev` way may be printing\n\ns/way may be printing/we may be printing/\n\n> +abbreviated hashes that collide. Too see how likely this is, try\n\ns/Too see/To see/\n\n> +running:\n\n[...]\n\n> +Even without `core.validateAbbrev=false` the results abbreviation\n> +already a bit of a probability game.\n\ns/the results abbreviation already a bit of/the resulting abbreviation\nis already a bit of/ maybe?\n\n> diff --git a/sha1-name.c b/sha1-name.c\n> index 60d9ef3c7e..aa7ccea14d 100644\n> --- a/sha1-name.c\n> +++ b/sha1-name.c\n> @@ -576,6 +576,7 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n> struct disambiguate_state ds;\n> struct min_abbrev_data mad;\n> struct object_id oid_ret;\n> + int dar = default_abbrev_relative;\n> if (len < 0) {\n> unsigned long count = approximate_object_count();\n> /*\n> @@ -602,6 +603,20 @@ int find_unique_abbrev_r(char *hex, const struct object_id *oid, int len)\n> if (len == GIT_SHA1_HEXSZ || !len)\n> return GIT_SHA1_HEXSZ;\n>\n> + if (dar) {\n> + if (len + dar < MINIMUM_ABBREV) {\n> + len = MINIMUM_ABBREV;\n> + dar = 0;\n> + }\n> +\n> + if (validate_abbrev) {\n> + len += dar;\n> + } else {\n> + hex[len + dar] = 0;\n> + return len + dar;\n> + }\n\nI wonder what happens if len + dar > GIT_SHA1_HEXSZ\n\n> + }\n"}]}