Multi-pack-index (MIDX)

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/technical/midx.txt | 109 +++++++++++++++++++++++++++++++
 1 file changed, 109 insertions(+)
 create mode 100644 Documentation/technical/midx.txt

Documentation/technical/midx.txt new file +5 -0

new file mode 100644
index 0000000000..789f410d71
@@ -0,0 +1,109 @@
+Multi-Pack-Index (MIDX) Design Notes
+====================================
+
+The Git object directory contains a 'pack' directory containing
+packfiles (with suffix ".pack") and pack-indexes (with suffix

Documentation/technical/midx.txt new file +16 -0

+  even as the multi-pack-index is updated) then a reachability bitmap
+  could point to a multi-pack-index and be updated independently.
+
+- Packfiles can be marked as "special" using empty files that share
+  the initial name but replace ".pack" with ".keep" or ".promisor".
+  We can add an optional chunk of data to the multi-pack-index that
+  records flags of information about the packfiles. This allows new
+  states, such as 'repacked' or 'redeltified', that can help with
+  pack maintenance in a multi-pack environment. It may also be
+  helpful to organize packfiles by object type (commit, tree, blob,
+  etc.) and use this metadata to help that maintenance.
+
+- The partial clone feature records special "promisor" packs that
+  may point to objects that are not stored locally, but available
+  on request to a server. The multi-pack-index does not currently
+  track these promisor packs.

Quoted 23 lines · Derrick Stolee

Signed-off-by Derrick Stolee <[email protected]>

---
  Documentation/technical/midx.txt | 109 +++++++++++++++++++++++++++++++
  1 file changed, 109 insertions(+)

create mode 100644 Documentation/technical/midx.txt

Documentation/technical/midx.txt new file +11 -0

new file mode 100644
index 0000000000..789f410d71
@@ -0,0 +1,109 @@
+Multi-Pack-Index (MIDX) Design Notes
+====================================
+
+The Git object directory contains a 'pack' directory containing
+packfiles (with suffix ".pack") and pack-indexes (with suffix
+".idx"). The pack-indexes provide a way to lookup objects and
+navigate to their offset within the pack, but these must come
+in pairs with the packfiles. This pairing depends on the file
+names, as the pack-index differs only in suffix with its pack-
+file. While the pack-indexes provide fast lookup per packfile,
+this performance degrades as the number of packfiles increases,

Documentation/technical/midx.txt line 15

Quoted 4 lines

Documentation/technical/midx.txt new file +4 -0

+because abbreviations need to inspect every packfile and we are
+more likely to have a miss on our most-recently-used packfile.
+For some large repositories, repacking into a single packfile
+is not feasible due to storage space or excessive repack times.

This leads to the question how MIDX will cope with large repos or a large number of packs. As it is just an index and not a pack itself, I guess it is smaller by some orders of magnitude, such that it is ok for now.

Documentation/technical/midx.txt line 29

Quoted 13 lines

Documentation/technical/midx.txt new file +13 -0

+The multi-pack-index (MIDX for short) stores a list of objects
+and their offsets into multiple packfiles. It contains:
+
+- A list of packfile names.
+- A sorted list of object IDs.
+- A list of metadata for the ith object ID including:
+  - A value j referring to the jth packfile.
+  - An offset within the jth packfile for the object.
+- If large offsets are required, we use another list of large
+  offsets similar to version 2 pack-indexes.
+
+Thus, we can provide O(log N) lookup time for any number
+of packfiles.

This sounds great for the lookup case!
Though that is for the repo-read case.
Let's read on how the dynamics of a repository are dealt with, e.g. integrating new packs into the MIDX, or how we deal with objects in multiple packs.

Documentation/technical/midx.txt line 37

Quoted 8 lines

Documentation/technical/midx.txt new file +8 -0

+
+Design Details
+--------------
+
+- The MIDX is stored in a file named 'multi-pack-index' in the
+  .git/objects/pack directory. This could be stored in the pack
+  directory of an alternate. It refers only to packfiles in that
+  same directory.

So there is one and only one multi pack index?
That makes the case of preparing the next MIDX that contains more pack references more interesting, as then we have to atomically update that file.

Documentation/technical/midx.txt line 39

Quoted 2 lines

Documentation/technical/midx.txt new file +1 -0

+- The core.midx config setting must be on to consume MIDX files.

Looking through current config options, I would rename this to a more suggestive name. I searched for the core.idx counterpart that enables idx files -- it turns out that is named pack.indexVersion.

So maybe pack.MultiIndex ? That could start out as a boolean as in this series and then evolve into a version number or such later.

Documentation/technical/midx.txt line 47

Quoted 8 lines

Documentation/technical/midx.txt new file +7 -0

+- The file format includes parameters for the object ID hash
+  function, so a future change of hash algorithm does not require
+  a change in format.
+
+- The MIDX keeps only one record per object ID. If an object appears
+  in multiple packfiles, then the MIDX selects the copy in the most-
+  recently modified packfile.

Okay. That answers the question from above. Though this is just the tie breaking decision and not a hard limitation? (i.e. we could change this this later to that pack that has e.g. shortest delta chain for that object or such)

Documentation/technical/midx.txt line 51

Quoted 4 lines

Documentation/technical/midx.txt new file +3 -0

+- If there exist packfiles in the pack directory not registered in
+  the MIDX, then those packfiles are loaded into the `packed_git`
+  list and `packed_git_mru` cache.

Not sure I understand the implications of this?
Does that mean we first look at the multi index and if an object is not found, we'll search linearly through all packs that are not part of the MIDX? That would require the MIDX to be kepot up to date reasonably to be useful.

Documentation/technical/midx.txt line 55

Quoted 4 lines

Documentation/technical/midx.txt new file +3 -0

+- The pack-indexes (.idx files) remain in the pack directory so we
+  can delete the MIDX file, set core.midx to false, or downgrade
+  without any loss of information.

In the future will it be possible to have no .idx files and just have the .midx? (I guess that depends on the strategy of how to integrate new packs into the MIDX?)

Documentation/technical/midx.txt line 58

Quoted 2 lines

Documentation/technical/midx.txt new file +2 -0

+- The MIDX file format uses a chunk-based approach (similar to the
+  commit-graph file) that allows optional data to be added.

... or the index files v2 (or reftable files)? Sure, you are most familiar with commit-graph files, but others may find it easier to have some older file formats to relate to.

Quoted 6 lines

Documentation/technical/midx.txt new file +6 -0

+Future Work
+-----------
+
+- Add a 'verify' subcommand to the 'git midx' builtin to verify the
+  contents of the multi-pack-index file match the offsets listed in
+  the corresponding pack-indexes.

Documentation/technical/midx.txt

Quoted 5 lines

Documentation/technical/midx.txt new file +5 -0

+
+- The multi-pack-index allows many packfiles, especially in a context
+  where repacking is expensive (such as a very large repo), or
+  unexpected maintenance time is unacceptable (such as a high-demand
+  build machine).

Supposedly maintenance (git gc) can be run in the background without interfering with day-to-day life, how is the regeneration of commit graph or MIDX files impacting the work here?

Documentation/technical/midx.txt line 75

Quoted 7 lines

Documentation/technical/midx.txt new file +5 -0

     However, the multi-pack-index needs to be rewritten
+  in full every time. We can extend the format to be incremental, so
+  writes are fast. By storing a small "tip" multi-pack-index that
+  points to large "base" MIDX files, we can keep writes fast while
+  still reducing the number of binary searches required for object
+  lookups.

So we can have multiple MIDX files? How would that work? Would there be a chunk that refers to other MIDX files?

Documentation/technical/midx.txt line 82

Quoted 7 lines

+- The reachability bitmap is currently paired directly with a single

Documentation/technical/midx.txt new file +5 -0

+  packfile, using the pack-order as the object order to hopefully
+  compress the bitmaps well using run-length encoding. This could be
+  extended to pair a reachability bitmap with a multi-pack-index. If
+  the multi-pack-index is extended to store a "stable object order"
+  (a function Order(hash) = integer that is constant for a given hash,

This stable object order doesn't fly well with integrating new packs?

Quoted 17 lines

Documentation/technical/midx.txt new file +16 -0

+  even as the multi-pack-index is updated) then a reachability bitmap
+  could point to a multi-pack-index and be updated independently.
+
+- Packfiles can be marked as "special" using empty files that share
+  the initial name but replace ".pack" with ".keep" or ".promisor".
+  We can add an optional chunk of data to the multi-pack-index that
+  records flags of information about the packfiles. This allows new
+  states, such as 'repacked' or 'redeltified', that can help with
+  pack maintenance in a multi-pack environment. It may also be
+  helpful to organize packfiles by object type (commit, tree, blob,
+  etc.) and use this metadata to help that maintenance.
+
+- The partial clone feature records special "promisor" packs that
+  may point to objects that are not stored locally, but available
+  on request to a server. The multi-pack-index does not currently
+  track these promisor packs.

The multi-pack-index (MIDX) feature generalizes the existing pack- index (IDX) feature by indexing objects across multiple pack-files.

Describe the basic file format, using a 12-byte header followed by a lookup table for a list of "chunks" which will be described later. The file ends with a footer containing a checksum using the hash algorithm.

The header allows later versions to create breaking changes by advancing the version number. We can also change the hash algorithm using a different version value.

We will add the individual chunk format information as we introduce the code that writes that information.

Signed-off-by Derrick Stolee <[email protected]>

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

Documentation/technical/pack-format.txt +0 -0

index 70a99fd142..17666b4bfc 100644

Documentation/technical/pack-format.txt +7 -0

+In order to allow extensions that add extra data to the MIDX, we organize
+the body into "chunks" and provide a lookup table at the beginning of the
+body. The header includes certain length values, such as the number of packs,
+the number of base MIDX files, hash lengths and types.
+
+All 4-byte numbers are in network order.
+

Hi Derrick,

Quoted 27 lines · Derrick Stolee

The multi-pack-index (MIDX) feature generalizes the existing pack- index (IDX) feature by indexing objects across multiple pack-files.

Describe the basic file format, using a 12-byte header followed by a lookup table for a list of "chunks" which will be described later. The file ends with a footer containing a checksum using the hash algorithm.

The header allows later versions to create breaking changes by advancing the version number. We can also change the hash algorithm using a different version value.

We will add the individual chunk format information as we introduce the code that writes that information.

Signed-off-by Derrick Stolee <[email protected]>

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

Documentation/technical/pack-format.txt +0 -0

index 70a99fd142..17666b4bfc 100644
@@ -252,3 +252,52 @@ Pack file entry: <+
      corresponding packfile.
 

Documentation/technical/pack-format.txt Pack file entry: <+ · line 258

Quoted 5 lines

Documentation/technical/pack-format.txt +4 -0

      20-byte SHA-1-checksum of all of the above.
+
+== midx-*.midx files have the following format:
+
+The meta-index files refer to multiple pack-files and loose objects.

So is it meta or multi?

Quoted 8 lines

Documentation/technical/pack-format.txt +7 -0

+In order to allow extensions that add extra data to the MIDX, we organize
+the body into "chunks" and provide a lookup table at the beginning of the
+body. The header includes certain length values, such as the number of packs,
+the number of base MIDX files, hash lengths and types.
+
+All 4-byte numbers are in network order.
+

Documentation/technical/pack-format.txt Pack file entry: <+ · line 276

Quoted 10 lines

Documentation/technical/pack-format.txt +10 -0

+HEADER:
+
+       4-byte signature:
+           The signature is: {'M', 'I', 'D', 'X'}
+
+       1-byte version number:
+           Git only writes or recognizes version 1
+
+       1-byte Object Id Version
+           Git only writes or recognizes verion 1 (SHA-1)

s/verion/version/

Documentation/technical/pack-format.txt Pack file entry: <+ · line 281

Quoted 4 lines

Documentation/technical/pack-format.txt +4 -0

+       1-byte number (C) of "chunks"
+
+       1-byte number (I) of base multi-pack-index files:
+           This value is currently always zero.

Oh? Are meta-index and multi-index files different things?

Documentation/technical/pack-format.txt Pack file entry: <+ · line 291

Quoted 10 lines

Documentation/technical/pack-format.txt +9 -0

+       4-byte number (P) of pack files
+
+CHUNK LOOKUP:
+
+       (C + 1) * 12 bytes providing the chunk offsets:
+           First 4 bytes describe chunk id. Value 0 is a terminating label.
+           Other 8 bytes provide offset in current file for chunk to start.
+           (Chunks are provided in file-order, so you can infer the length
+           using the next chunk position if necessary.)

It is so nice to have the header also have 12 bytes, so it fits right into the lookup table. So an alternative point of view:

If a chunk needs to store more than 8 bytes, we'll have an offset after the first 4 bytes that describe the chunk, otherwise you can store the 8 bytes of information directly after the 4 bytes.
"MIDX" is a special chunk and must come first (does it?) and only once
as it contains the version number.

Documentation/technical/pack-format.txt Pack file entry: <+ · line 303

Quoted 11 lines

Documentation/technical/pack-format.txt +11 -0

+       The remaining data in the body is described one chunk at a time, and
+       these chunks may be given in any order. Chunks are required unless
+       otherwise specified.
+
+CHUNK DATA:
+
+       (This section intentionally left incomplete.)
+
+TRAILER:
+
+       H-byte HASH-checksum of all of the above.

This means we have to rehash the whole file for updating its contents. okay.

Quoted 8 lines

Documentation/technical/pack-format.txt Pack file entry: <+ · line 291

Quoted 5 lines

Documentation/technical/pack-format.txt +5 -0

+       (C + 1) * 12 bytes providing the chunk offsets:
+           First 4 bytes describe chunk id. Value 0 is a terminating label.
+           Other 8 bytes provide offset in current file for chunk to start.
+           (Chunks are provided in file-order, so you can infer the length
+           using the next chunk position if necessary.)

It is so nice to have the header also have 12 bytes, so it fits right into the lookup table. So an alternative point of view:

Quoted 5 lines

If a chunk needs to store more than 8 bytes, we'll have an offset after the first 4 bytes that describe the chunk, otherwise you can store the 8 bytes of information directly after the 4 bytes.
"MIDX" is a special chunk and must come first (does it?) and only once
as it contains the version number.

This sounds feasible, but unnecessarily complicated. I don't think any other chunk will be this small.

builtin/midx.c new file +5 -0

+#include "parse-options.h"
+
+static char const * const builtin_midx_usage[] ={
+       N_("git midx [--object-dir <dir>]"),
+       NULL

builtin/midx.c new file +17 -0

+               OPT_END(),
+       };
+
+       if (argc == 2 && !strcmp(argv[1], "-h"))
+               usage_with_options(builtin_midx_usage, builtin_midx_options);
+
+       git_config(git_default_config, NULL);
+
+       argc = parse_options(argc, argv, prefix,
+                            builtin_midx_options,
+                            builtin_midx_usage, 0);
+
+       if (!opts.object_dir)
+               opts.object_dir = get_object_directory();
+
+       return 0;
+}

git.c +0 -0

index c2f48d53dd..400fadd677 100644

git.c +0 -0

        { "mktag", cmd_mktag, RUN_SETUP | NO_PARSEOPT },
        { "mktree", cmd_mktree, RUN_SETUP },
        { "mv", cmd_mv, RUN_SETUP | NEED_WORK_TREE },

Documentation/git-midx.txt line 6

Quoted 12 lines · Derrick Stolee

Documentation/git-midx.txt new file +6 -0

new file mode 100644
index 0000000000..2bd886f1a2
@@ -0,0 +1,29 @@
+git-midx(1)
+============
+
+NAME
+----
+git-midx - Write and verify multi-pack-indexes (MIDX files).

No full stop. This head line is collected automatically with others and its having a full stop while the rest does not looks strange/

builtin/midx.c line 4

Quoted 10 lines

builtin/midx.c new file +4 -0

new file mode 100644
index 0000000000..59ea92178f
@@ -0,0 +1,38 @@
+#include "builtin.h"
+#include "cache.h"
+#include "config.h"
+#include "git-compat-util.h"

You only need either cache.h or git-compat-util.h. If cache.h is here, git-compat-util can be removed.

Quoted 11 lines

builtin/midx.c new file +11 -0

+#include "parse-options.h"
+
+static char const * const builtin_midx_usage[] ={
+       N_("git midx [--object-dir <dir>]"),
+       NULL
+};
+
+static struct opts_midx {
+       const char *object_dir;
+} opts;
+

builtin/midx.c line 19

Quoted 4 lines

builtin/midx.c new file +4 -0

+int cmd_midx(int argc, const char **argv, const char *prefix)
+{
+       static struct option builtin_midx_options[] = {
+               { OPTION_STRING, 0, "object-dir", &opts.object_dir,

For paths (including dir), OPTION_FILENAME may be a better option to handle correctly when the command is run in a subdir. See df217ed643 (parse-opts: add OPT_FILENAME and transition builtins - 2009-05-23) for more info.

builtin/midx.c line 21

Quoted 3 lines

builtin/midx.c new file +2 -0

+                 N_("dir"),
+                 N_("The object directory containing set of packfile and pack-index pairs.") },

Other help strings do not have full stop either (I only checked a couple commands though)

Also, doesn't OPT_STRING() work here too (if you avoid OPTION_FILENAME for some reason)?

Quoted 22 lines

builtin/midx.c new file +17 -0

+               OPT_END(),
+       };
+
+       if (argc == 2 && !strcmp(argv[1], "-h"))
+               usage_with_options(builtin_midx_usage, builtin_midx_options);
+
+       git_config(git_default_config, NULL);
+
+       argc = parse_options(argc, argv, prefix,
+                            builtin_midx_options,
+                            builtin_midx_usage, 0);
+
+       if (!opts.object_dir)
+               opts.object_dir = get_object_directory();
+
+       return 0;
+}

git.c +0 -0

index c2f48d53dd..400fadd677 100644
@@ -503,6 +503,7 @@ static struct cmd_struct commands[] = {

git.c static struct cmd_struct commands[] = { · line 506

Quoted 4 lines

git.c +1 -0

         { "merge-recursive-theirs", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE | NO_PARSEOPT },
         { "merge-subtree", cmd_merge_recursive, RUN_SETUP | NEED_WORK_TREE | NO_PARSEOPT },
         { "merge-tree", cmd_merge_tree, RUN_SETUP | NO_PARSEOPT },
+       { "midx", cmd_midx, RUN_SETUP },

If it's a plumbing and can take an --object-dir, then I don't think you should require it to run in a repo (with RUN_SETUP). RUN_SETUP_GENTLY may be better. You could even leave it empty here and only call setup_git_directory() only when --object-dir is not set.

Quoted 4 lines

git.c +0 -0

         { "mktag", cmd_mktag, RUN_SETUP | NO_PARSEOPT },
         { "mktree", cmd_mktree, RUN_SETUP },
         { "mv", cmd_mv, RUN_SETUP | NEED_WORK_TREE },

This new 'git midx' builtin will be the plumbing access for writing, reading, and checking multi-pack-index (MIDX) files. The initial implementation is a no-op.

Documentation/git-midx.txt new file +10 -0

+
+
+SYNOPSIS
+--------
+[verse]
+'git midx' [--object-dir <dir>]
+
+DESCRIPTION
+-----------
+Write or verify a MIDX file.

Hi Derrick,

Quoted 3 lines · Derrick Stolee

This new 'git midx' builtin will be the plumbing access for writing, reading, and checking multi-pack-index (MIDX) files. The initial implementation is a no-op.

Let's talk about the name for a second:

.idx files are written by git-index-pack or as part of git-pack-objects (which just calls write_idx_file as part of finish_tmp_packfile), and the name actually suggests it writes the index files. I have a hard time understanding what the git-midx command does[1].

With both commit graph as well as multi index we introduce a command that is centered around that concept (similar to git-remote or git-config that are centered around a concept, that is closely resembled by a file), but for indexes for packs it was integrated differently into Git. So I am not sure if I want to suggest to integrate it into the packfile commands as that doesn't really fit. But maybe we can have a name that is human readable instead of the file suffix? Maybe

git multi-pack-index ?

I suppose that eventually this command is not really used by users as it will be used by other porcelain commands in the background or even as part of repack/gc so I am not worried about a long name, but I'd be more worried about understandability.

[1] While these names are not perfect for the layman, it is okay? I am sure you are aware of https://git-man-page-generator.lokaltog.net/

Documentation/git-midx.txt line 6

Quoted 13 lines

new file mode 100644
index 0000000000..2bd886f1a2

Documentation/git-midx.txt new file +6 -0

@@ -0,0 +1,29 @@
+git-midx(1)
+============
+
+NAME
+----
+git-midx - Write and verify multi-pack-indexes (MIDX files).

The reading is done as part of all other commands.

Quoted 11 lines

Documentation/git-midx.txt new file +10 -0

+
+
+SYNOPSIS
+--------
+[verse]
+'git midx' [--object-dir <dir>]
+
+DESCRIPTION
+-----------
+Write or verify a MIDX file.

Documentation/git-midx.txt line 26

Quoted 10 lines

Documentation/git-midx.txt new file +10 -0

+
+OPTIONS
+-------
+
+--object-dir <dir>::
+       Use given directory for the location of Git objects. We check
+       <dir>/packs/multi-pack-index for the current MIDX file, and
+       <dir>/packs for the pack-files to index.
+
+

Maybe we could have a SEE ALSO section that points at the explanation of multi index files?
(c.f. man git-submodule that has a SEE ALSO gitsubmodules(7), gitmodules(5) explaining concepts(7) and the file(5))

But as this is plumbing and users should not need to worry about it this is optional, I would think.

Quoted 2 lines

But as this is plumbing and users should not need to worry about it this is optional, I would think.

The design document is also in 'Documentation/technical' instead of just 'Documentation/'. Do we have a pattern of linking to the technical documents?

Quoted 5 lines

Quoted 2 lines

But as this is plumbing and users should not need to worry about it this is optional, I would think.

The design document is also in 'Documentation/technical' instead of just 'Documentation/'. Do we have a pattern of linking to the technical documents?

Apparently we do (and I was not aware of it):

     $ git -C Documentation/ grep link:technical
     git-credential.txt:23:link:technical/api-credentials.html[the Git
credential API] for more
     git.txt:839:link:technical/api-index.html[Git API documentation].
     gitcredentials.txt:184:link:technical/api-credentials.html[credentials
API] for details.
     technical/http-protocol.txt:517:link:technical/pack-protocol.html
     technical/http-protocol.txt:518:link:technical/protocol-capabilities.html
     user-manual.txt:3220:found in link:technical/pack-format.html[pack format].

builtin/midx.c +2 -1

index 59ea92178f..dc0a5acd3f 100644
@@ -3,9 +3,10 @@
 #include "config.h"
 #include "git-compat-util.h"
 #include "parse-options.h"
+#include "midx.h"
 
 static char const * const builtin_midx_usage[] ={
-       N_("git midx [--object-dir <dir>]"),
+       N_("git midx [--object-dir <dir>] [write]"),
        NULL
 };
 

builtin/midx.c +4 -0

+
+       if (!strcmp(argv[0], "write"))
+               return write_midx_file(opts.object_dir);
+
        return 0;
 }

midx.c new file +0 -0

new file mode 100644
index 0000000000..616af66b13

midx.c new file +6 -0

+#include "midx.h"
+
+int write_midx_file(const char *object_dir)
+{
+       return 0;
+}

midx.h new file +0 -0

new file mode 100644
index 0000000000..3a63673952

midx.h new file +2 -0

+
+int write_midx_file(const char *object_dir);

t/t5319-midx.sh new file +0 -0

new file mode 100755
index 0000000000..a590137af7

t/t5319-midx.sh new file +4 -1

+       git midx --object-dir=. write
+'
+
+test_done
--

2.18.0.rc1

midx.c +5 -0

index 616af66b13..3e55422a21 100644
@@ -1,9 +1,62 @@
 #include "git-compat-util.h"
 #include "cache.h"
 #include "dir.h"
+#include "csum-file.h"
+#include "lockfile.h"
 #include "midx.h"
 
+#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
+#define MIDX_VERSION 1
+#define MIDX_HASH_VERSION 1 /* SHA-1 */

midx.c +7 -0

+       byte_values[2] = num_chunks;
+       byte_values[3] = 0; /* unused */
+       hashwrite(f, byte_values, sizeof(byte_values));
+       hashwrite_be32(f, num_packs);
+
+       return MIDX_HEADER_SIZE;
+}

Quoted 15 lines · Derrick Stolee

midx.c +5 -0

index 616af66b13..3e55422a21 100644
@@ -1,9 +1,62 @@
  #include "git-compat-util.h"
  #include "cache.h"
  #include "dir.h"
+#include "csum-file.h"
+#include "lockfile.h"
  #include "midx.h"
 
+#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
+#define MIDX_VERSION 1
+#define MIDX_HASH_VERSION 1 /* SHA-1 */

...

midx.c line 28

Quoted 8 lines

midx.c +8 -0

+static size_t write_midx_header(struct hashfile *f,
+                               unsigned char num_chunks,
+                               uint32_t num_packs)
+{
+       char byte_values[4];
+       hashwrite_be32(f, MIDX_SIGNATURE);
+       byte_values[0] = MIDX_VERSION;
+       byte_values[1] = MIDX_HASH_VERSION;

Quoting from "State of NewHash work, future directions, and discussion" [1]

* If you need to serialize an algorithm identifier into your data format, use the format_id field of struct git_hash_algo. It's designed specifically for that purpose.

[1] https://public-inbox.org/git/[email protected]/T/#m5fdd09dcaf31266c45343fb6c0beaaa3e928bc60

Quoted 27 lines · Duy Nguyen

Quoted 15 lines · Derrick Stolee

midx.c +5 -0

index 616af66b13..3e55422a21 100644
@@ -1,9 +1,62 @@
  #include "git-compat-util.h"
  #include "cache.h"
  #include "dir.h"
+#include "csum-file.h"
+#include "lockfile.h"
  #include "midx.h"
 
+#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
+#define MIDX_VERSION 1
+#define MIDX_HASH_VERSION 1 /* SHA-1 */

...

midx.c line 28

Quoted 8 lines

midx.c +8 -0

+static size_t write_midx_header(struct hashfile *f,
+                               unsigned char num_chunks,
+                               uint32_t num_packs)
+{
+       char byte_values[4];
+       hashwrite_be32(f, MIDX_SIGNATURE);
+       byte_values[0] = MIDX_VERSION;
+       byte_values[1] = MIDX_HASH_VERSION;

Quoting from "State of NewHash work, future directions, and discussion" [1]

Quoted 5 lines

* If you need to serialize an algorithm identifier into your data format, use the format_id field of struct git_hash_algo. It's designed specifically for that purpose.

[1] https://public-inbox.org/git/[email protected]/T/#m5fdd09dcaf31266c45343fb6c0beaaa3e928bc60

Thanks! I'll also use the_hash_algo->rawsz to infer the length of the hash function.

Quoted 33 lines · Derrick Stolee

Quoted 32 lines · Duy Nguyen

Quoted 15 lines · Derrick Stolee

midx.c +5 -0

index 616af66b13..3e55422a21 100644
@@ -1,9 +1,62 @@
   #include "git-compat-util.h"
   #include "cache.h"
   #include "dir.h"
+#include "csum-file.h"
+#include "lockfile.h"
   #include "midx.h"
 
+#define MIDX_SIGNATURE 0x4d494458 /* "MIDX" */
+#define MIDX_VERSION 1
+#define MIDX_HASH_VERSION 1 /* SHA-1 */

...

midx.c line 28

Quoted 8 lines

midx.c +8 -0

+static size_t write_midx_header(struct hashfile *f,
+                               unsigned char num_chunks,
+                               uint32_t num_packs)
+{
+       char byte_values[4];
+       hashwrite_be32(f, MIDX_SIGNATURE);
+       byte_values[0] = MIDX_VERSION;
+       byte_values[1] = MIDX_HASH_VERSION;

Quoting from "State of NewHash work, future directions, and discussion" [1]

* If you need to serialize an algorithm identifier into your data format, use the format_id field of struct git_hash_algo. It's designed specifically for that purpose.

[1] https://public-inbox.org/git/[email protected]/T/#m5fdd09dcaf31266c45343fb6c0beaaa3e928bc60

Quoted 2 lines

Thanks! I'll also use the_hash_algo->rawsz to infer the length of the hash function.

BTW, since you're the author of commit-graph.c and may notice it has the same problem. Don't touch that code. Brian already has some WIP changes [1]. We just make sure new code does not add extra work for him. I expect he'll send all those patches out soon.

[1] https://github.com/bk2204/git/commit/3f9031e06cfb21534eb7dfff7b54e7598ac1149f

As we build the multi-pack-index feature by adding chunks at a time, we want to test that the data is being written correctly.

Create struct midxed_git to store an in-memory representation of a

midx.h +4 -0

 #include "packfile.h"
 
+struct midxed_git *load_midxed_git(const char *object_dir);
+
 int write_midx_file(const char *object_dir);
+
+#endif

object-store.h +0 -0

index d683112fd7..77cb82621a 100644

object-store.h +5 -0

+
+       int fd;
+
+       const unsigned char *data;
+       size_t data_len;

object-store.h +2 -0

+};
+
 struct raw_object_store {
        /*
         * Path to the repository's object store.

Quoted 4 lines · Derrick Stolee

As we build the multi-pack-index feature by adding chunks at a time, we want to test that the data is being written correctly.

Create struct midxed_git to store an in-memory representation of a

A word play on 'packed_git'? Amusing. Some more descriptive name would be better though. midxed looks almost like random letters thrown together.

builtin/midx.c static struct opts_midx { · line 22

Quoted 9 lines

multi-pack-index and a memory-map of the binary file. Initialize this struct in load_midxed_git(object_dir).

builtin/midx.c +6 -0

+static int read_midx_file(const char *object_dir)
+{
+       struct midxed_git *m = load_midxed_git(object_dir);
+
+       if (!m)
+               return 0;

This looks like an error case, please don't just return zero, typically used to say "success". I don't know if this command stays "for debugging purposes" until the end. Of course in that case it does not really matter.

midx.c static char *get_midx_filename(const char *object_dir) · line 31

Quoted 8 lines

midx.c +8 -0

+struct midxed_git *load_midxed_git(const char *object_dir)
+{
+       struct midxed_git *m;
+       int fd;
+       struct stat st;
+       size_t midx_size;
+       void *midx_map;
+       const char *midx_name = get_midx_filename(object_dir);

mem leak? This function returns allocated memory if I remember correctly.

midx.c static char *get_midx_filename(const char *object_dir) · line 35

Quoted 4 lines

midx.c +4 -0

+
+       fd = git_open(midx_name);
+       if (fd < 0)
+               return NULL;

do an error_errno() so we know what went wrong at least.

midx.c static char *get_midx_filename(const char *object_dir) · line 38

Quoted 3 lines

midx.c +3 -0

+       if (fstat(fd, &st)) {
+               close(fd);
+               return NULL;

same here, we should know why fstat() fails.

midx.c static char *get_midx_filename(const char *object_dir) · line 44

Quoted 6 lines

midx.c +6 -0

+       }
+       midx_size = xsize_t(st.st_size);
+
+       if (midx_size < MIDX_MIN_SIZE) {
+               close(fd);
+               die("multi-pack-index file %s is too small", midx_name);

_()

The use of die() should be discouraged though. Many people still try (or wish) to libify code and new die() does not help. I think error() here would be enough then you can return NULL. Or you can go fancier and store the error string in a strbuf like refs code.

midx.c static char *get_midx_filename(const char *object_dir) · line 56

Quoted 12 lines

midx.c +12 -0

+       }
+
+       midx_map = xmmap(NULL, midx_size, PROT_READ, MAP_PRIVATE, fd, 0);
+
+       m = xcalloc(1, sizeof(*m) + strlen(object_dir) + 1);
+       strcpy(m->object_dir, object_dir);
+       m->data = midx_map;
+
+       m->signature = get_be32(m->data);
+       if (m->signature != MIDX_SIGNATURE) {
+               error("multi-pack-index signature %X does not match signature %X",
+                     m->signature, MIDX_SIGNATURE);

_(). Maybe 0x%08x instead of %x

midx.c static char *get_midx_filename(const char *object_dir) · line 60

Quoted 4 lines

midx.c +4 -0

+               goto cleanup_fail;
+       }
+
+       m->version = *(m->data + 4);

m->data[4] instead? shorter and easier to understand.

Same comment on "*(m->data + x)" and error() without _() for the rest.

midx.c static char *get_midx_filename(const char *object_dir) · line 63

Quoted 3 lines

midx.c +3 -0

+       if (m->version != MIDX_VERSION) {
+               error("multi-pack-index version %d not recognized",
+                     m->version);

_()

midx.c static char *get_midx_filename(const char *object_dir) · line 67

Quoted 4 lines

midx.c +4 -0

+               goto cleanup_fail;
+       }
+
+       m->hash_version = *(m->data + 5);

m->data[5]

midx.c static char *get_midx_filename(const char *object_dir) · line 83

Quoted 5 lines

midx.c +5 -0

+cleanup_fail:
+       FREE_AND_NULL(m);
+       munmap(midx_map, midx_size);
+       close(fd);
+       exit(1);

It's bad enough that you die() but exit() in this code seems too much. Please just return NULL and let the caller handle the error.

midx.h line 6

Quoted 12 lines

midx.h +5 -0

index 3a63673952..a1d18ed991 100644
@@ -1,4 +1,13 @@
+#ifndef MIDX_H
+#define MIDX_H
+
+#include "git-compat-util.h"
  #include "cache.h"
+#include "object-store.h"

I don't really think you need object-store here (git-compat-util.h too). "struct mixed_git;" would be enough for load_midxed_git declaration below.

Quoted 15 lines

midx.h +4 -0

  #include "packfile.h"
 
+struct midxed_git *load_midxed_git(const char *object_dir);
+
  int write_midx_file(const char *object_dir);
+
+#endif

object-store.h +0 -0

index d683112fd7..77cb82621a 100644
@@ -84,6 +84,25 @@ struct packed_git {
         char pack_name[FLEX_ARRAY]; /* more */
  };
 

object-store.h struct packed_git { · line 88

Quoted 2 lines

object-store.h +2 -0

+struct midxed_git {
+       struct midxed_git *next;

Do we really have multiple midx files?

Quoted 6 lines

object-store.h +5 -0

+
+       int fd;
+
+       const unsigned char *data;
+       size_t data_len;

object-store.h struct packed_git { · line 103

Quoted 10 lines

object-store.h +10 -0

+
+       uint32_t signature;
+       unsigned char version;
+       unsigned char hash_version;
+       unsigned char hash_len;
+       unsigned char num_chunks;
+       uint32_t num_packs;
+       uint32_t num_objects;
+
+       char object_dir[FLEX_ARRAY];

Why do you need to keep object_dir when it could be easily retrieved when the repo is available?

Quoted 5 lines

object-store.h +2 -0

+};
+
  struct raw_object_store {
         /*
          * Path to the repository's object store.

Quoted 8 lines · Derrick Stolee

Documentation/git-midx.txt +0 -0

index dcaeb1a91b..919283fdd8 100644
@@ -23,6 +23,11 @@ OPTIONS
         <dir>/packs/multi-pack-index for the current MIDX file, and
         <dir>/packs for the pack-files to index.
 

Documentation/git-midx.txt OPTIONS · line 29

Quoted 4 lines

Documentation/git-midx.txt +4 -0

+read::
+       When given as the verb, read the current MIDX file and output
+       basic information about its contents. Used for debugging
+       purposes only.

On second thought. If you just need a temporary debugging interface, adding a program in t/helper may be a better option. In the end we might still need 'read' to dump a file out, but we should have some stable output format (and json might be a good choice).

Quoted 9 lines · Duy Nguyen

Quoted 8 lines · Derrick Stolee

Documentation/git-midx.txt +0 -0

index dcaeb1a91b..919283fdd8 100644
@@ -23,6 +23,11 @@ OPTIONS
         <dir>/packs/multi-pack-index for the current MIDX file, and
         <dir>/packs for the pack-files to index.
 

Quoted 8 lines

Documentation/git-midx.txt OPTIONS · line 29

Quoted 4 lines

Documentation/git-midx.txt +4 -0

+read::
+       When given as the verb, read the current MIDX file and output
+       basic information about its contents. Used for debugging
+       purposes only.

On second thought. If you just need a temporary debugging interface, adding a program in t/helper may be a better option. In the end we might still need 'read' to dump a file out, but we should have some stable output format (and json might be a good choice).

My intention with this 'read' pattern in the MIDX (and commit-graph) is two-fold:

1. We can test that we are writing the correct data in our test suite. A test-tool builtin would suffice for this purpose.

2. We can help trouble-shoot users who may be having trouble with their MIDX files. Having the subcommand in a plumbing command allows us to do this in the shipped versions of Git.

Maybe this second purpose isn't enough to justify the feature in Git and we should move this to the test-tool, especially with the 'verify' mode coming in a second series. Note that a 'verify' mode doesn't satisfy item (1).

Quoted 24 lines · Derrick Stolee

Quoted 9 lines · Duy Nguyen

Quoted 8 lines · Derrick Stolee

Documentation/git-midx.txt +0 -0

index dcaeb1a91b..919283fdd8 100644
@@ -23,6 +23,11 @@ OPTIONS
          <dir>/packs/multi-pack-index for the current MIDX file, and
          <dir>/packs for the pack-files to index.
 

Quoted 8 lines

Documentation/git-midx.txt OPTIONS · line 29

Quoted 4 lines

Documentation/git-midx.txt +4 -0

+read::
+       When given as the verb, read the current MIDX file and output
+       basic information about its contents. Used for debugging
+       purposes only.

On second thought. If you just need a temporary debugging interface, adding a program in t/helper may be a better option. In the end we might still need 'read' to dump a file out, but we should have some stable output format (and json might be a good choice).

My intention with this 'read' pattern in the MIDX (and commit-graph) is two-fold:

1. We can test that we are writing the correct data in our test suite. A test-tool builtin would suffice for this purpose.

Quoted 8 lines

2. We can help trouble-shoot users who may be having trouble with their MIDX files. Having the subcommand in a plumbing command allows us to do this in the shipped versions of Git.

Maybe this second purpose isn't enough to justify the feature in Git and we should move this to the test-tool, especially with the 'verify' mode coming in a second series. Note that a 'verify' mode doesn't satisfy item (1).

Yeah I think normally we just have some "fsck" thing to verify when things go bad. If you need more than that I think you just ask the user to send the .midx to you (with full understanding of potentially revealing confidential info and stuff). It'll be faster than instructing them to "run this command", "ok, run another command".... I thought of suggesting a command to dump the midx file in readable form (like json), but I think if fsck fails then chances of that command successfully dumping may be very low.

Either way, if the command is meant for troubleshooting, I think it should be added at the end when the whole midx file is implemented and understood and we see what we need to troubleshoot. Adding small pieces of changes from patch to patch makes it really hard to see if it helps troubleshooting at all, it just helps the first purpose.

midx.c +19 -0

+               strbuf_release(&pack_dir);
+               return 1;
+       }
+
+       strbuf_addch(&pack_dir, '/');
+       pack_dir_len = pack_dir.len;
+       ALLOC_ARRAY(packs, alloc_packs);
+       while ((de = readdir(dir)) != NULL) {
+               if (is_dot_or_dotdot(de->d_name))
+                       continue;
+
+               if (ends_with(de->d_name, ".idx")) {
+                       ALLOC_GROW(packs, nr_packs + 1, alloc_packs);
+
+                       strbuf_setlen(&pack_dir, pack_dir_len);
+                       strbuf_addstr(&pack_dir, de->d_name);
+
+                       packs[nr_packs] = add_packed_git(pack_dir.buf,
+                                                        pack_dir.len,

midx.c +18 -0

+       char *pack_name;
+};
+
+static int pack_pair_compare(const void *_a, const void *_b)
+{
+       struct pack_pair *a = (struct pack_pair *)_a;
+       struct pack_pair *b = (struct pack_pair *)_b;
+       return strcmp(a->pack_name, b->pack_name);
+}
+
+static void sort_packs_by_name(char **pack_names, uint32_t nr_packs, uint32_t *perm)
+{
+       uint32_t i;
+       struct pack_pair *pairs;
+
+       ALLOC_ARRAY(pairs, nr_packs);
+
+       for (i = 0; i < nr_packs; i++) {

midx.c +10 -0

+}
+
+static size_t write_midx_pack_names(struct hashfile *f,
+                                   char **pack_names,
+                                   uint32_t num_packs)
+{
+       uint32_t i;
+       unsigned char padding[MIDX_CHUNK_ALIGNMENT];
+       size_t written = 0;
+

midx.c +16 -1

+       }
+
+       /* add padding to be aligned */
+       i = MIDX_CHUNK_ALIGNMENT - (written % MIDX_CHUNK_ALIGNMENT);
+       if (i < MIDX_CHUNK_ALIGNMENT) {
+               bzero(padding, sizeof(padding));
+               hashwrite(f, padding, i);
+               written += i;
+       }
+
+       return written;
+}
+
 int write_midx_file(const char *object_dir)
 {
-       unsigned char num_chunks = 0;
+       unsigned char cur_chunk, num_chunks = 0;
        char *midx_name;
        struct hashfile *f;
        struct lock_file lk;
        struct packed_git **packs = NULL;
+       char **pack_names = NULL;
+       uint32_t *pack_perm;

midx.c +39 -4

        midx_name = get_midx_filename(object_dir);
        if (safe_create_leading_directories(midx_name)) {

@@ -132,12 +233,14 @@ int write_midx_file(const char *object_dir)
        strbuf_addch(&pack_dir, '/');
        pack_dir_len = pack_dir.len;
        ALLOC_ARRAY(packs, alloc_packs);
+       ALLOC_ARRAY(pack_names, alloc_pack_names);
        while ((de = readdir(dir)) != NULL) {
                if (is_dot_or_dotdot(de->d_name))
                        continue;
 
                if (ends_with(de->d_name, ".idx")) {
                        ALLOC_GROW(packs, nr_packs + 1, alloc_packs);
+                       ALLOC_GROW(pack_names, nr_packs + 1, alloc_pack_names);
 
                        strbuf_setlen(&pack_dir, pack_dir_len);
                        strbuf_addstr(&pack_dir, de->d_name);

@@ -145,21 +248,83 @@ int write_midx_file(const char *object_dir)
                        packs[nr_packs] = add_packed_git(pack_dir.buf,
                                                         pack_dir.len,
                                                         0);
-                       if (!packs[nr_packs])
+                       if (!packs[nr_packs]) {
                                warning("failed to add packfile '%s'",
                                        pack_dir.buf);
-                       else
-                               nr_packs++;
+                               continue;
+                       }
+
+                       pack_names[nr_packs] = xstrdup(de->d_name);
+                       pack_name_concat_len += strlen(de->d_name) + 1;
+                       nr_packs++;
                }
        }
+
        closedir(dir);
        strbuf_release(&pack_dir);
 
+       if (pack_name_concat_len % MIDX_CHUNK_ALIGNMENT)
+               pack_name_concat_len += MIDX_CHUNK_ALIGNMENT -
+                                       (pack_name_concat_len % MIDX_CHUNK_ALIGNMENT);
+
+       ALLOC_ARRAY(pack_perm, nr_packs);
+       sort_packs_by_name(pack_names, nr_packs, pack_perm);
+
        hold_lock_file_for_update(&lk, midx_name, LOCK_DIE_ON_ERROR);
        f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
        FREE_AND_NULL(midx_name);
 
-       write_midx_header(f, num_chunks, nr_packs);
+       cur_chunk = 0;
+       num_chunks = 1;
+
+       written = write_midx_header(f, num_chunks, nr_packs);
+
+       chunk_ids[cur_chunk] = MIDX_CHUNKID_PACKNAMES;
+       chunk_offsets[cur_chunk] = written + (num_chunks + 1) * MIDX_CHUNKLOOKUP_WIDTH;
+
+       cur_chunk++;
+       chunk_ids[cur_chunk] = 0;
+       chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + pack_name_concat_len;
+
+       for (i = 0; i <= num_chunks; i++) {
+               if (i && chunk_offsets[i] < chunk_offsets[i - 1])
+                       BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,
+                           chunk_offsets[i - 1],
+                           chunk_offsets[i]);
+
+               if (chunk_offsets[i] % MIDX_CHUNK_ALIGNMENT)
+                       BUG("chunk offset %"PRIu64" is not properly aligned",
+                           chunk_offsets[i]);
+

midx.c +19 -0

+                           chunk_offsets[i],
+                           written,
+                           chunk_ids[i]);
+
+               switch (chunk_ids[i]) {
+                       case MIDX_CHUNKID_PACKNAMES:
+                               written += write_midx_pack_names(f, pack_names, nr_packs);
+                               break;
+
+                       default:
+                               BUG("trying to write unknown chunk id %"PRIx32,
+                                   chunk_ids[i]);
+               }
+       }
+
+       if (written != chunk_offsets[num_chunks])
+               BUG("incorrect final offset %"PRIu64" != %"PRIu64,
+                   written,
+                   chunk_offsets[num_chunks]);
 
        finalize_hashfile(f, NULL, CSUM_FSYNC | CSUM_HASH_IN_STREAM);
        commit_lock_file(&lk);

midx.c +0 -0

        return 0;
 }

midx.c struct midxed_git *load_midxed_git(const char *object_dir) · line 85

Quoted 7 lines · Derrick Stolee

midx.c +3 -0

@@ -74,6 +80,31 @@ struct midxed_git *load_midxed_git(const char *object_dir)
         m->num_chunks = *(m->data + 6);
         m->num_packs = get_be32(m->data + 8);
 
+       for (i = 0; i < m->num_chunks; i++) {
+               uint32_t chunk_id = get_be32(m->data + 12 + MIDX_CHUNKLOOKUP_WIDTH * i);
+               uint64_t chunk_offset = get_be64(m->data + 16 + MIDX_CHUNKLOOKUP_WIDTH * i);

Would be good to reduce magic numbers like 12 and 16, I think you have some header length constants for those already.

midx.c struct midxed_git *load_midxed_git(const char *object_dir) · line 93

Quoted 7 lines

midx.c +7 -0

+               switch (chunk_id) {
+                       case MIDX_CHUNKID_PACKNAMES:
+                               m->chunk_pack_names = m->data + chunk_offset;
+                               break;
+
+                       case 0:
+                               die("terminating MIDX chunk id appears earlier than expected");

_()

midx.c struct midxed_git *load_midxed_git(const char *object_dir) · line 100

Quoted 8 lines

midx.c +7 -0

+                               break;
+
+                       default:
+                               /*
+                                * Do nothing on unrecognized chunks, allowing future
+                                * extensions to add optional chunks.
+                                */

I wrote about the chunk term reminding me of PNG format then deleted it. But it may help to do similar to PNG here. The first letter can let us know if the chunk is optional and can be safely ignored. E.g. uppercase first letter cannot be ignored, lowercase go wild.

midx.c struct midxed_git *load_midxed_git(const char *object_dir) · line 106

Quoted 7 lines

midx.c +6 -0

+                               break;
+               }
+       }
+
+       if (!m->chunk_pack_names)
+               die("MIDX missing required pack-name chunk");

_()

Quoted 3 lines

midx.c +1 -0

+
         return m;
 

midx.c static size_t write_midx_header(struct hashfile *f, · line 134

Quoted 7 lines

midx.c +2 -0

  cleanup_fail:

@@ -99,18 +130,88 @@ static size_t write_midx_header(struct hashfile *f,
         return MIDX_HEADER_SIZE;
  }
 
+struct pack_pair {
+       uint32_t pack_int_id;

can this be just pack_id?

Quoted 22 lines

midx.c +21 -0

+       char *pack_name;
+};
+
+static int pack_pair_compare(const void *_a, const void *_b)
+{
+       struct pack_pair *a = (struct pack_pair *)_a;
+       struct pack_pair *b = (struct pack_pair *)_b;
+       return strcmp(a->pack_name, b->pack_name);
+}
+
+static void sort_packs_by_name(char **pack_names, uint32_t nr_packs, uint32_t *perm)
+{
+       uint32_t i;
+       struct pack_pair *pairs;
+
+       ALLOC_ARRAY(pairs, nr_packs);
+
+       for (i = 0; i < nr_packs; i++) {
+               pairs[i].pack_int_id = i;
+               pairs[i].pack_name = pack_names[i];
+       }

midx.c static size_t write_midx_header(struct hashfile *f, · line 162

Quoted 7 lines

midx.c +7 -0

+
+       QSORT(pairs, nr_packs, pack_pair_compare);
+
+       for (i = 0; i < nr_packs; i++) {
+               pack_names[i] = pairs[i].pack_name;
+               perm[pairs[i].pack_int_id] = i;
+       }

pairs[] is leaked?

Quoted 11 lines

midx.c +10 -0

+}
+
+static size_t write_midx_pack_names(struct hashfile *f,
+                                   char **pack_names,
+                                   uint32_t num_packs)
+{
+       uint32_t i;
+       unsigned char padding[MIDX_CHUNK_ALIGNMENT];
+       size_t written = 0;
+

midx.c static size_t write_midx_header(struct hashfile *f, · line 182

Quoted 10 lines

midx.c +10 -0

+       for (i = 0; i < num_packs; i++) {
+               size_t writelen = strlen(pack_names[i]) + 1;
+
+               if (i && strcmp(pack_names[i], pack_names[i - 1]) <= 0)
+                       BUG("incorrect pack-file order: %s before %s",
+                           pack_names[i - 1],
+                           pack_names[i]);
+
+               hashwrite(f, pack_names[i], writelen);
+               written += writelen;

side note. This pattern happens a lot. It may be a good idea to make hashwrite() return writelen so we can just write

written += hashwrite(f, ..., writelen);

Quoted 28 lines

midx.c +17 -1

+       }
+
+       /* add padding to be aligned */
+       i = MIDX_CHUNK_ALIGNMENT - (written % MIDX_CHUNK_ALIGNMENT);
+       if (i < MIDX_CHUNK_ALIGNMENT) {
+               bzero(padding, sizeof(padding));
+               hashwrite(f, padding, i);
+               written += i;
+       }
+
+       return written;
+}
+
  int write_midx_file(const char *object_dir)
  {
-       unsigned char num_chunks = 0;
+       unsigned char cur_chunk, num_chunks = 0;
         char *midx_name;
         struct hashfile *f;
         struct lock_file lk;
         struct packed_git **packs = NULL;
+       char **pack_names = NULL;
+       uint32_t *pack_perm;
         uint32_t i, nr_packs = 0, alloc_packs = 0;
+       uint32_t alloc_pack_names = 0;
         DIR *dir;
         struct dirent *de;

midx.c static size_t write_midx_header(struct hashfile *f, · line 214

Quoted 6 lines

midx.c +4 -0

         struct strbuf pack_dir = STRBUF_INIT;
         size_t pack_dir_len;
+       uint64_t pack_name_concat_len = 0;
+       uint64_t written = 0;
+       uint32_t chunk_ids[MIDX_MAX_CHUNKS + 1];
+       uint64_t chunk_offsets[MIDX_MAX_CHUNKS + 1];

This long list of local vars may be a good indicator that this function needs split up into smaller ones.

Quoted 73 lines

midx.c +39 -4

         midx_name = get_midx_filename(object_dir);
         if (safe_create_leading_directories(midx_name)) {

@@ -132,12 +233,14 @@ int write_midx_file(const char *object_dir)
         strbuf_addch(&pack_dir, '/');
         pack_dir_len = pack_dir.len;
         ALLOC_ARRAY(packs, alloc_packs);
+       ALLOC_ARRAY(pack_names, alloc_pack_names);
         while ((de = readdir(dir)) != NULL) {
                 if (is_dot_or_dotdot(de->d_name))
                         continue;
 
                 if (ends_with(de->d_name, ".idx")) {
                         ALLOC_GROW(packs, nr_packs + 1, alloc_packs);
+                       ALLOC_GROW(pack_names, nr_packs + 1, alloc_pack_names);
 
                         strbuf_setlen(&pack_dir, pack_dir_len);
                         strbuf_addstr(&pack_dir, de->d_name);

@@ -145,21 +248,83 @@ int write_midx_file(const char *object_dir)
                         packs[nr_packs] = add_packed_git(pack_dir.buf,
                                                          pack_dir.len,
                                                          0);
-                       if (!packs[nr_packs])
+                       if (!packs[nr_packs]) {
                                 warning("failed to add packfile '%s'",
                                         pack_dir.buf);
-                       else
-                               nr_packs++;
+                               continue;
+                       }
+
+                       pack_names[nr_packs] = xstrdup(de->d_name);
+                       pack_name_concat_len += strlen(de->d_name) + 1;
+                       nr_packs++;
                 }
         }
+
         closedir(dir);
         strbuf_release(&pack_dir);
 
+       if (pack_name_concat_len % MIDX_CHUNK_ALIGNMENT)
+               pack_name_concat_len += MIDX_CHUNK_ALIGNMENT -
+                                       (pack_name_concat_len % MIDX_CHUNK_ALIGNMENT);
+
+       ALLOC_ARRAY(pack_perm, nr_packs);
+       sort_packs_by_name(pack_names, nr_packs, pack_perm);
+
         hold_lock_file_for_update(&lk, midx_name, LOCK_DIE_ON_ERROR);
         f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
         FREE_AND_NULL(midx_name);
 
-       write_midx_header(f, num_chunks, nr_packs);
+       cur_chunk = 0;
+       num_chunks = 1;
+
+       written = write_midx_header(f, num_chunks, nr_packs);
+
+       chunk_ids[cur_chunk] = MIDX_CHUNKID_PACKNAMES;
+       chunk_offsets[cur_chunk] = written + (num_chunks + 1) * MIDX_CHUNKLOOKUP_WIDTH;
+
+       cur_chunk++;
+       chunk_ids[cur_chunk] = 0;
+       chunk_offsets[cur_chunk] = chunk_offsets[cur_chunk - 1] + pack_name_concat_len;
+
+       for (i = 0; i <= num_chunks; i++) {
+               if (i && chunk_offsets[i] < chunk_offsets[i - 1])
+                       BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,
+                           chunk_offsets[i - 1],
+                           chunk_offsets[i]);
+
+               if (chunk_offsets[i] % MIDX_CHUNK_ALIGNMENT)
+                       BUG("chunk offset %"PRIu64" is not properly aligned",
+                           chunk_offsets[i]);
+

midx.c int write_midx_file(const char *object_dir) · line 308

Quoted 10 lines

midx.c +10 -0

+               hashwrite_be32(f, chunk_ids[i]);
+               hashwrite_be32(f, chunk_offsets[i] >> 32);
+               hashwrite_be32(f, chunk_offsets[i]);
+
+               written += MIDX_CHUNKLOOKUP_WIDTH;
+       }
+
+       for (i = 0; i < num_chunks; i++) {
+               if (written != chunk_offsets[i])
+                       BUG("inccrrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,

incorrect

Quoted 25 lines

midx.c +19 -0

+                           chunk_offsets[i],
+                           written,
+                           chunk_ids[i]);
+
+               switch (chunk_ids[i]) {
+                       case MIDX_CHUNKID_PACKNAMES:
+                               written += write_midx_pack_names(f, pack_names, nr_packs);
+                               break;
+
+                       default:
+                               BUG("trying to write unknown chunk id %"PRIx32,
+                                   chunk_ids[i]);
+               }
+       }
+
+       if (written != chunk_offsets[num_chunks])
+               BUG("incorrect final offset %"PRIu64" != %"PRIu64,
+                   written,
+                   chunk_offsets[num_chunks]);
 
         finalize_hashfile(f, NULL, CSUM_FSYNC | CSUM_HASH_IN_STREAM);
         commit_lock_file(&lk);

@@ -170,5 +335,6 @@ int write_midx_file(const char *object_dir)
         }