patch, 8 partspack-revindex: introduce on-disk '.rev' format

Hi,

This is the second of two series to implement support for an on-disk format for storing the reverse index. (It depends on the patches in the previous series [1]).

The format is described in the first patch, but it is roughly as follows:

  - It begins with a 12-byte header, containing a magic string, a version
    identifier, and a hash function identifier.

  - It then contains a 4 * N (where 'N' is the number of objects) table of index
    positions, sorted by each object's offset within the corresponding packfile.

  - Finally, a trailer contains a checksum of the corresponding packfile, and a
    checksum of the above contents.

Since this is a large change, a new 'pack.writeReverseIndex' option is introduced, which defaults to 'false'. When false, `*.rev` files are not written, and Git gracefully falls back to generate each reverse index in memory. This could optionally be tied to the "feature.experimental" option, and eventually the defalt changed to 'true' in a couple of releases.

To test these new changes, the test suite now understands 'GIT_TEST_WRITE_REV_INDEX' to mean that 'pack.writeReverseIndex' should be 'true' everywhere. Some minor test fall-out is addressed in the sixth patch before enabling this new mode in the seventh patch.

One option that is _not_ persued in this series is to store the (pack) offset of each object in the `.rev` file. This would at worst triple the size of the file (by having to store an additional eight bytes per entry), and add complexity (like storing an extended offset table as in the `*.idx` format). An extensive discussion about why this option was not persued can be found in the first patch.

Thanks in advance for your review.

[1]: https://lore.kernel.org/git/cover.1610129796.git.me@ttaylorr.com/

Taylor Blau (8):
  packfile: prepare for the existence of '*.rev' files
  pack-write.c: prepare to write 'pack-*.rev' files
  builtin/index-pack.c: write reverse indexes
  builtin/pack-objects.c: respect 'pack.writeReverseIndex'
  Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
  t: prepare for GIT_TEST_WRITE_REV_INDEX
  t: support GIT_TEST_WRITE_REV_INDEX
  pack-revindex: ensure that on-disk reverse indexes are given
    precedence

 Documentation/config/pack.txt           |   7 ++
 Documentation/git-index-pack.txt        |  20 ++--
 Documentation/technical/pack-format.txt |  17 ++++
 builtin/index-pack.c                    |  67 +++++++++++--
 builtin/pack-objects.c                  |   9 ++
 builtin/repack.c                        |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 116 ++++++++++++++++++++--
 pack-revindex.h                         |   3 +
 pack-write.c                            | 123 +++++++++++++++++++++++-
 pack.h                                  |   4 +
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 t/README                                |   3 +
 t/t5319-multi-pack-index.sh             |   2 +-
 t/t5325-reverse-index.sh                |  94 ++++++++++++++++++
 t/t5604-clone-reference.sh              |   2 +-
 t/t5702-protocol-v2.sh                  |   4 +-
 t/t6500-gc.sh                           |   4 +-
 t/t9300-fast-import.sh                  |   2 +-
 tmp-objdir.c                            |   4 +-
 21 files changed, 463 insertions(+), 36 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

This patch prepares for callers to be able to write reverse index files to disk.

It adds the necessary machinery to write a format-compliant .rev file from within 'write_rev_file()', which is called from 'finish_tmp_packfile()'.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-write.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 pack.h       |   4 ++
 2 files changed, 126 insertions(+), 1 deletion(-)

When an on-disk reverse index exists, there is no need to generate one in memory. In fact, doing so can be slow, and require large amounts of the heap.

Let's make sure that we treat the on-disk reverse index with precedence (i.e., that when it exists, we don't bother trying to generate an equivalent one in memory) by teaching Git how to conditionally die() when generating a reverse index in memory.

Then, add a test to ensure that when (a) an on-disk reverse index exists, and (b) when setting GIT_TEST_REV_INDEX_DIE_IN_MEMORY, that we do not die, implying that we read from the on-disk one.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-revindex.c          | 4 ++++
 pack-revindex.h          | 1 +
 t/t5325-reverse-index.sh | 8 ++++++++
 3 files changed, 13 insertions(+)

Teach 'git index-pack' to optionally write and verify reverse index with '--[no-]rev-index', as well as respecting the 'pack.writeReverseIndex' configuration option.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-index-pack.txt | 20 ++++++---
 builtin/index-pack.c             | 64 ++++++++++++++++++++++++-----
 t/t5325-reverse-index.sh         | 69 ++++++++++++++++++++++++++++++++
 3 files changed, 137 insertions(+), 16 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

Specify the format of the on-disk reverse index 'pack-*.rev' file, as well as prepare the code for the existence of such files.

The reverse index maps from pack relative positions (i.e., an index into the array of object which is sorted by their offsets within the packfile) to their position within the 'pack-*.idx' file. Today, this is done by building up a list of (off_t, uint32_t) tuples for each object (the off_t corresponding to that object's offset, and the uint32_t corresponding to its position in the index). To convert between pack and index position quickly, this array of tuples is radix sorted based on its offset.

This has two major drawbacks:

First, the in-memory cost scales linearly with the number of objects in a pack. Each 'struct revindex_entry' is sizeof(off_t) + sizeof(uint32_t) + padding bytes for a total of 16.

To observe this, force Git to load the reverse index by, for e.g., running 'git cat-file --batch-check="%(objectsize:disk)"'. When asking for a single object in a fresh clone of the kernel, Git needs to allocate 120+ MB of memory in order to hold the reverse index in memory.

Second, the cost to sort also scales with the size of the pack. Luckily, this is a linear function since 'load_pack_revindex()' uses a radix sort, but this cost still must be paid once per pack per process.

As an example, it takes ~60x longer to print the _size_ of an object as it does to print that entire object's _contents_:

  Benchmark #1: git.compile cat-file --batch <obj
    Time (mean ± σ):       3.4 ms ±   0.1 ms    [User: 3.3 ms, System: 2.1 ms]
    Range (min … max):     3.2 ms …   3.7 ms    726 runs

  Benchmark #2: git.compile cat-file --batch-check="%(objectsize:disk)" <obj
    Time (mean ± σ):     210.3 ms ±   8.9 ms    [User: 188.2 ms, System: 23.2 ms]
    Range (min … max):   193.7 ms … 224.4 ms    13 runs

Instead, avoid computing and sorting the revindex once per process by writing it to a file when the pack itself is generated.

The format is relatively straightforward. It contains an array of uint32_t's, the length of which is equal to the number of objects in the pack. The ith entry in this table contains the index position of the ith object in the pack, where "ith object in the pack" is determined by pack offset.

One thing that the on-disk format does _not_ contain is the full (up to) eight-byte offset corresponding to each object. This is something that the in-memory revindex contains (it stores an off_t in 'struct revindex_entry' along with the same uint32_t that the on-disk format has). Omit it in the on-disk format, since knowing the index position for some object is sufficient to get a constant-time lookup in the pack-*.idx file to ask for an object's offset within the pack.

This trades off between the on-disk size of the 'pack-*.rev' file for runtime to chase down the offset for some object. Even though the lookup is constant time, the constant is heavier, since it can potentially involve two pointer walks in v2 indexes (one to access the 4-byte offset table, and potentially a second to access the double wide offset table).

Consider trying to map an object's pack offset to a relative position within that pack. In a cold-cache scenario, more page faults occur while switching between binary searching through the reverse index and searching through the *.idx file for an object's offset. Sure enough, with a cold cache (writing '3' into '/proc/sys/vm/drop_caches' after 'sync'ing), printing out the entire object's contents is still marginally faster than printing its size:

  Benchmark #1: git.compile cat-file --batch-check="%(objectsize:disk)" <obj >/dev/null
    Time (mean ± σ):      22.6 ms ±   0.5 ms    [User: 2.4 ms, System: 7.9 ms]
    Range (min … max):    21.4 ms …  23.5 ms    41 runs

  Benchmark #2: git.compile cat-file --batch <obj >/dev/null
    Time (mean ± σ):      17.2 ms ±   0.7 ms    [User: 2.8 ms, System: 5.5 ms]
    Range (min … max):    15.6 ms …  18.2 ms    45 runs

(Numbers taken in the kernel after cheating and using the next patch to generate a reverse index). There are a couple of approaches to improve cold cache performance not pursued here:

  - We could include the object offsets in the reverse index format.
    Predictably, this does result in fewer page faults, but it triples
    the size of the file, while simultaneously duplicating a ton of data
    already available in the .idx file. (This was the original way I
    implemented the format, and it did show
    `--batch-check='%(objectsize:disk)'` winning out against `--batch`.)

    On the other hand, this increase in size also results in a large
    block-cache footprint, which could potentially hurt other workloads.

  - We could store the mapping from pack to index position in more
    cache-friendly way, like constructing a binary search tree from the
    table and writing the values in breadth-first order. This would
    result in much better locality, but the price you pay is trading
    O(1) lookup in 'pack_pos_to_index()' for an O(log n) one (since you
    can no longer directly index the table).

So, neither of these approaches are taken here. (Thankfully, the format is versioned, so we are free to pursue these in the future.) But, cold cache performance likely isn't interesting outside of one-off cases like asking for the size of an object directly. In real-world usage, Git is often performing many operations in the revindex,

The trade-off is worth it, since we will avoid the vast majority of the cost of generating the revindex that the extra pointer chase will look like noise in the following patch's benchmarks.

This patch describes the format and prepares callers (like in pack-revindex.c) to be able to read *.rev files once they exist. An implementation of the writer will appear in the next patch, and callers will gradually begin to start using the writer in the patches that follow after that.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/technical/pack-format.txt |  17 ++++
 builtin/repack.c                        |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 112 +++++++++++++++++++++---
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 tmp-objdir.c                            |   4 +-
 7 files changed, 139 insertions(+), 12 deletions(-)

Now that we have an implementation that can write the new reverse index format, enable writing a .rev file in 'git pack-objects' by consulting the pack.writeReverseIndex configuration variable.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c   |  7 +++++++
 t/t5325-reverse-index.sh | 13 +++++++++++++
 2 files changed, 20 insertions(+)

Add a new option that unconditionally enables the pack.writeReverseIndex setting in order to run the whole test suite in a mode that generates on-disk reverse indexes.

Once on-disk reverse indexes are proven out over several releases, we can change the default value of that configuration to 'true', and drop this patch.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/index-pack.c   | 5 ++++-
 builtin/pack-objects.c | 2 ++
 pack-revindex.h        | 2 ++
 t/README               | 3 +++
 4 files changed, 11 insertions(+), 1 deletion(-)

On 1/8/2021 1:20 PM, Taylor Blau wrote:

...

Should this also be added to the second run of the test suite with optional variables?

On Tue, Jan 12, 2021 at 11:49:40AM -0500, Derrick Stolee wrote:

Ah, I wasn't aware of this script myself. Yes, it should be there, thanks.

Thanks, Taylor

On Fri, Jan 08 2021, Taylor Blau wrote:

Why not make an explicit GIT_TEST_WRITE_REV_INDEX=false meaningful? It's also sometimes handy to turn these off in the tests.

    rev_index = git_env_bool("GIT_TEST_WRITE_REV_INDEX",
    	!!(opts.flags & (WRITE_REV_VERIFY | WRITE_REV)));

Micro style nit: FWIW I'm not a fan of this macro->string indirection a few GIT_TEST_* names have had since 859fdc0c3c (commit-graph: define GIT_TEST_COMMIT_GRAPH, 2018-08-29).

Most of them just use git_env_bool("GIT_TEST_[...]") which IMO makes it easier to eyeball a "git grep"

Re the git_env_bool() default value comment above: I see our other boolean GIT_TEST_* docs say "when true", but mostly they mean things like:

    GIT_TEST_WRITE_REV_INDEX=<boolean>, when set, configures the
    'pack.writeReverseIndex' setting. Defaults to 'false'.

On 1/12/2021 12:18 PM, Ævar Arnfjörð Bjarmason wrote:

 
This will cause tests that explicitly request a rev-index to fail when
GIT_TEST_WRITE_REF_INDEX=false. I'm not sure that's a good pattern to
follow.

In the case of GIT_TEST_COMMIT_GRAPH, there are multiple places that check the environment variable, and it is probably best to have the strings consistent through a macro.

For something like GIT_TEST_WRITE_REV_INDEX, this macro is less important because it is checked only once.

Thanks, -Stolee

On Tue, Jan 12, 2021 at 12:39:37PM -0500, Derrick Stolee wrote:

I agree that this wouldn't work; the second parameter is the default value, not a substitute for "false".

It _would_ work currently, since there aren't any tests in this series that explicitly

    export GIT_TEST_WRITE_REF_INDEX=false

t5325 does 'sane_unset GIT_TEST_WRITE_REV_INDEX', which accomplishes the same thing without setting a value. If we instead used the export form, this would break, so I think the implementation is more robust as-is.

FWIW, I'm not a huge fan of the indirection either, but I think that its use here is warranted, since it is checked twice (in index-pack, and pack-objects).

It _could_ be checked lower in the call stack, but I tried this when developing this series and it ended up being far messier than what is presented here. The trickiness is with the extra verification mode (which ensures that an existing '.rev' file was written correctly), and having to indicate that at each caller.

Thanks, Taylor

In the next patch, we'll add support for unconditionally enabling the 'pack.writeReverseIndex' setting with a new GIT_TEST_WRITE_REV_INDEX environment variable.

This causes a little bit of fallout with tests that, for example, compare the list of files in the pack directory being unprepared to see .rev files in its output.

For now, sprinkle these locations with a 'grep -v "\.rev$"' to ignore them. Once the pack.writeReverseIndex option has been thoroughly tested, we will default it to 'true', removing GIT_TEST_WRITE_REV_INDEX, and making it possible to revert this patch.

At that time, we'll have to adjust the expected output to contain the relevant .rev files, but for now this will do just fine.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5319-multi-pack-index.sh | 2 +-
 t/t5325-reverse-index.sh    | 4 ++++
 t/t5604-clone-reference.sh  | 2 +-
 t/t5702-protocol-v2.sh      | 4 ++--
 t/t6500-gc.sh               | 4 ++--
 t/t9300-fast-import.sh      | 2 +-
 6 files changed, 11 insertions(+), 7 deletions(-)

On Fri, Jan 08 2021, Taylor Blau wrote:

Maybe some of it we can change/revert, but some of it just seems to be test warts we can fix:

This seems to be testing "a *.keep file made my pack not expire". Can't it just check for *.{pack,idx,keep} or even just *.pack?

There's an existing loop just below that where we grep out /commit-graph/, /multi-pack-index/ etc. whith other test modes add to the objects directory with sed. Seems like this belongs there, not in the find above it.

Maybe just check *.{pack,idx,keep}. I was looking at that code the other day and it's really just being overly specific. It really just cares about the *.pack files.

ditto.

This is all part of account where we later use comm/wc -l to check how many new packs we have,so just check *.pack?

Yay, there the existing multi-pack-index case is amended in a future-proof way :)

Hi Ævar,

Your suggestions are quite helpful, and I'm glad to apply them, especially if it means that this "clean up" patch can actually harden us from similar changes in the future.

On Tue, Jan 12, 2021 at 06:11:00PM +0100, Ævar Arnfjörð Bjarmason wrote:

Yeah, and I think the simplest thing to do here is just check that these files exist at all. Something like:

Now that the pack.writeReverseIndex configuration is respected in both 'git index-pack' and 'git pack-objects' (and therefore, all of their callers), we can safely advertise it for use in the git-config manual.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/config/pack.txt | 7 +++++++
 1 file changed, 7 insertions(+)

Hi,

This is the second of two series to implement support for an on-disk format for storing the reverse index. Note that this depends on the patches in the previous series [1], which was recently updated).

This version is largely unchanged from the original, with the following exceptions:

  - It has been rebased onto the patches in the first series.
  - The operands of two comparisons in 'offset_to_pack_pos()' were swapped so
    that the smaller of the two appears on the left-hand side of the comparison.
  - A brown-paper-bag bug was fixed in tests so that they pass on Windows (last
    night's integration broke 'seen' on Windows).
  - The GIT_TEST_WRITE_REV_INDEX mode was enabled in the "all-features" test.

Thanks in advance for your review.

[1]: https://lore.kernel.org/git/cover.1610129796.git.me@ttaylorr.com/

Taylor Blau (8):
  packfile: prepare for the existence of '*.rev' files
  pack-write.c: prepare to write 'pack-*.rev' files
  builtin/index-pack.c: write reverse indexes
  builtin/pack-objects.c: respect 'pack.writeReverseIndex'
  Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
  t: prepare for GIT_TEST_WRITE_REV_INDEX
  t: support GIT_TEST_WRITE_REV_INDEX
  pack-revindex: ensure that on-disk reverse indexes are given
    precedence

 Documentation/config/pack.txt           |   7 ++
 Documentation/git-index-pack.txt        |  20 ++--
 Documentation/technical/pack-format.txt |  17 ++++
 builtin/index-pack.c                    |  67 +++++++++++--
 builtin/pack-objects.c                  |   9 ++
 builtin/repack.c                        |   1 +
 ci/run-build-and-tests.sh               |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 116 ++++++++++++++++++++--
 pack-revindex.h                         |  10 +-
 pack-write.c                            | 123 +++++++++++++++++++++++-
 pack.h                                  |   4 +
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 t/README                                |   3 +
 t/t5319-multi-pack-index.sh             |   5 +-
 t/t5325-reverse-index.sh                |  97 +++++++++++++++++++
 t/t5604-clone-reference.sh              |   2 +-
 t/t5702-protocol-v2.sh                  |  12 ++-
 t/t6500-gc.sh                           |   6 +-
 t/t9300-fast-import.sh                  |   5 +-
 tmp-objdir.c                            |   4 +-
 22 files changed, 485 insertions(+), 41 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

 -:  ---------- >  1:  e1aa89244a pack-revindex: introduce a new API
 -:  ---------- >  2:  0fca7d5812 write_reuse_object(): convert to new revindex API
 -:  ---------- >  3:  7676822a54 write_reused_pack_one(): convert to new revindex API
 -:  ---------- >  4:  dd7133fdb7 write_reused_pack_verbatim(): convert to new revindex API
 -:  ---------- >  5:  8e93ca3886 check_object(): convert to new revindex API
 -:  ---------- >  6:  084bbf2145 bitmap_position_packfile(): convert to new revindex API
 -:  ---------- >  7:  68794e9484 show_objects_for_type(): convert to new revindex API
 -:  ---------- >  8:  31ac6f5703 get_size_by_pos(): convert to new revindex API
 -:  ---------- >  9:  acd80069a2 try_partial_reuse(): convert to new revindex API
 -:  ---------- > 10:  569acdca7f rebuild_existing_bitmaps(): convert to new revindex API
 -:  ---------- > 11:  9881637724 get_delta_base_oid(): convert to new revindex API
 -:  ---------- > 12:  df8bb571a5 retry_bad_packed_offset(): convert to new revindex API
 -:  ---------- > 13:  41b2e00947 packed_object_info(): convert to new revindex API
 -:  ---------- > 14:  8ad49d231f unpack_entry(): convert to new revindex API
 -:  ---------- > 15:  e757476351 for_each_object_in_pack(): convert to new revindex API
 -:  ---------- > 16:  a500311e33 builtin/gc.c: guess the size of the revindex
 -:  ---------- > 17:  67d14da04a pack-revindex: remove unused 'find_pack_revindex()'
 -:  ---------- > 18:  3b5c92be68 pack-revindex: remove unused 'find_revindex_position()'
 -:  ---------- > 19:  cabafce4a1 pack-revindex: hide the definition of 'revindex_entry'
 -:  ---------- > 20:  8400ff6c96 pack-revindex.c: avoid direct revindex access in 'offset_to_pack_pos()'
 1:  ddf47a0a50 ! 21:  6742c15c84 packfile: prepare for the existence of '*.rev' files
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
     +
      int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
      {
    - 	int lo = 0;
    + 	unsigned lo, hi;
     @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)

      uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos)
    @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
     -	if (!p->revindex)
     +	if (!(p->revindex || p->revindex_data))
      		BUG("pack_pos_to_index: reverse index not yet loaded");
    - 	if (pos >= p->num_objects)
    + 	if (p->num_objects <= pos)
      		BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos);
     -	return p->revindex[pos].nr;
     +
    @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
     -	if (!p->revindex)
     +	if (!(p->revindex || p->revindex_data))
      		BUG("pack_pos_to_index: reverse index not yet loaded");
    - 	if (pos > p->num_objects)
    + 	if (p->num_objects < pos)
      		BUG("pack_pos_to_offset: out-of-bounds object at %"PRIu32, pos);
     -	return p->revindex[pos].offset;
     +
    @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
     +		return nth_packed_object_offset(p, pack_pos_to_index(p, pos));
      }

    + ## pack-revindex.h ##
    +@@ pack-revindex.h: struct packed_git;
    + /*
    +  * load_pack_revindex populates the revindex's internal data-structures for the
    +  * given pack, returning zero on success and a negative value otherwise.
    ++ *
    ++ * If a '.rev' file is present, it is checked for consistency, mmap'd, and
    ++ * pointers are assigned into it (instead of using the in-memory variant).
    +  */
    + int load_pack_revindex(struct packed_git *p);
    +
    +@@ pack-revindex.h: uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);
    +  * If the reverse index has not yet been loaded, or the position is out of
    +  * bounds, this function aborts.
    +  *
    +- * This function runs in constant time.
    ++ * This function runs in constant time under both in-memory and on-disk reverse
    ++ * indexes, but an additional step is taken to consult the corresponding .idx
    ++ * file when using the on-disk format.
    +  */
    + off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
    +
    +
      ## packfile.c ##
     @@ packfile.c: void close_pack_index(struct packed_git *p)
      	}
 2:  88393e2662 = 22:  8648c87fa7 pack-write.c: prepare to write 'pack-*.rev' files
 3:  b0a7329824 ! 23:  5b18ada611 builtin/index-pack.c: write reverse indexes
    @@ t/t5325-reverse-index.sh (new)
     +	rm -f $rev &&
     +	conf=$1 &&
     +	shift &&
    ++	# remove the index since Windows won't overwrite an existing file
    ++	rm $packdir/pack-$pack.idx &&
     +	git -c pack.writeReverseIndex=$conf index-pack "$@" \
     +		$packdir/pack-$pack.pack
     +}
 4:  e297a31875 = 24:  68bde3ea97 builtin/pack-objects.c: respect 'pack.writeReverseIndex'
 5:  5d3e96a498 = 25:  38a253d0ce Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
 6:  2288571fbe <  -:  ---------- t: prepare for GIT_TEST_WRITE_REV_INDEX
 -:  ---------- > 26:  12cdf2d67a t: prepare for GIT_TEST_WRITE_REV_INDEX
 7:  3525c4d114 ! 27:  6b647d9775 t: support GIT_TEST_WRITE_REV_INDEX
    @@ Commit message

         Add a new option that unconditionally enables the pack.writeReverseIndex
         setting in order to run the whole test suite in a mode that generates
    -    on-disk reverse indexes.
    +    on-disk reverse indexes. Additionally, enable this mode in the second
    +    run of tests under linux-gcc in 'ci/run-build-and-tests.sh'.

         Once on-disk reverse indexes are proven out over several releases, we
         can change the default value of that configuration to 'true', and drop
    @@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const
      	progress = isatty(2);
      	argc = parse_options(argc, argv, prefix, pack_objects_options,

    + ## ci/run-build-and-tests.sh ##
    +@@ ci/run-build-and-tests.sh: linux-gcc)
    + 	export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
    + 	export GIT_TEST_MULTI_PACK_INDEX=1
    + 	export GIT_TEST_ADD_I_USE_BUILTIN=1
    ++	export GIT_TEST_WRITE_REV_INDEX=1
    + 	make test
    + 	;;
    + linux-clang)
    +
      ## pack-revindex.h ##
     @@
    - #ifndef PACK_REVINDEX_H
    - #define PACK_REVINDEX_H
    +  *   can be found
    +  */

     +#define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
     +
      struct packed_git;

    - int load_pack_revindex(struct packed_git *p);
    + /*

      ## t/README ##
     @@ t/README: GIT_TEST_DEFAULT_HASH=<hash-algo> specifies which hash algorithm to
 8:  6e580d43d1 ! 28:  48926ae182 pack-revindex: ensure that on-disk reverse indexes are given precedence
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)

      ## pack-revindex.h ##
     @@
    - #define PACK_REVINDEX_H
    +  */

      #define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
     +#define GIT_TEST_REV_INDEX_DIE_IN_MEMORY "GIT_TEST_REV_INDEX_DIE_IN_MEMORY"
    @@ t/t5325-reverse-index.sh: test_expect_success 'pack-objects respects pack.writeR
      '

     +test_expect_success 'reverse index is not generated when available on disk' '
    -+	git index-pack --rev-index $packdir/pack-$pack.pack &&
    ++	test_index_pack true &&
    ++	test_path_is_file $rev &&
     +
     +	git rev-parse HEAD >tip &&
     +	GIT_TEST_REV_INDEX_DIE_IN_MEMORY=1 git cat-file \
--
2.30.0.138.g6d7191ea01

When an on-disk reverse index exists, there is no need to generate one in memory. In fact, doing so can be slow, and require large amounts of the heap.

Let's make sure that we treat the on-disk reverse index with precedence (i.e., that when it exists, we don't bother trying to generate an equivalent one in memory) by teaching Git how to conditionally die() when generating a reverse index in memory.

Then, add a test to ensure that when (a) an on-disk reverse index exists, and (b) when setting GIT_TEST_REV_INDEX_DIE_IN_MEMORY, that we do not die, implying that we read from the on-disk one.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-revindex.c          | 4 ++++
 pack-revindex.h          | 1 +
 t/t5325-reverse-index.sh | 9 +++++++++
 3 files changed, 14 insertions(+)

In the next patch, we'll add support for unconditionally enabling the 'pack.writeReverseIndex' setting with a new GIT_TEST_WRITE_REV_INDEX environment variable.

This causes a little bit of fallout with tests that, for example, compare the list of files in the pack directory being unprepared to see .rev files in its output.

Those locations can be cleaned up to look for specific file extensions, rather than take everything in the pack directory (for instance) and then grep out unwanted items.

Once the pack.writeReverseIndex option has been thoroughly tested, we will default it to 'true', removing GIT_TEST_WRITE_REV_INDEX, and making it possible to revert this patch.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5319-multi-pack-index.sh |  5 +++--
 t/t5325-reverse-index.sh    |  4 ++++
 t/t5604-clone-reference.sh  |  2 +-
 t/t5702-protocol-v2.sh      | 12 ++++++++----
 t/t6500-gc.sh               |  6 +++---
 t/t9300-fast-import.sh      |  5 ++++-
 6 files changed, 23 insertions(+), 11 deletions(-)

Specify the format of the on-disk reverse index 'pack-*.rev' file, as well as prepare the code for the existence of such files.

The reverse index maps from pack relative positions (i.e., an index into the array of object which is sorted by their offsets within the packfile) to their position within the 'pack-*.idx' file. Today, this is done by building up a list of (off_t, uint32_t) tuples for each object (the off_t corresponding to that object's offset, and the uint32_t corresponding to its position in the index). To convert between pack and index position quickly, this array of tuples is radix sorted based on its offset.

This has two major drawbacks:

First, the in-memory cost scales linearly with the number of objects in a pack. Each 'struct revindex_entry' is sizeof(off_t) + sizeof(uint32_t) + padding bytes for a total of 16.

To observe this, force Git to load the reverse index by, for e.g., running 'git cat-file --batch-check="%(objectsize:disk)"'. When asking for a single object in a fresh clone of the kernel, Git needs to allocate 120+ MB of memory in order to hold the reverse index in memory.

Second, the cost to sort also scales with the size of the pack. Luckily, this is a linear function since 'load_pack_revindex()' uses a radix sort, but this cost still must be paid once per pack per process.

As an example, it takes ~60x longer to print the _size_ of an object as it does to print that entire object's _contents_:

  Benchmark #1: git.compile cat-file --batch <obj
    Time (mean ± σ):       3.4 ms ±   0.1 ms    [User: 3.3 ms, System: 2.1 ms]
    Range (min … max):     3.2 ms …   3.7 ms    726 runs

  Benchmark #2: git.compile cat-file --batch-check="%(objectsize:disk)" <obj
    Time (mean ± σ):     210.3 ms ±   8.9 ms    [User: 188.2 ms, System: 23.2 ms]
    Range (min … max):   193.7 ms … 224.4 ms    13 runs

Instead, avoid computing and sorting the revindex once per process by writing it to a file when the pack itself is generated.

The format is relatively straightforward. It contains an array of uint32_t's, the length of which is equal to the number of objects in the pack. The ith entry in this table contains the index position of the ith object in the pack, where "ith object in the pack" is determined by pack offset.

One thing that the on-disk format does _not_ contain is the full (up to) eight-byte offset corresponding to each object. This is something that the in-memory revindex contains (it stores an off_t in 'struct revindex_entry' along with the same uint32_t that the on-disk format has). Omit it in the on-disk format, since knowing the index position for some object is sufficient to get a constant-time lookup in the pack-*.idx file to ask for an object's offset within the pack.

This trades off between the on-disk size of the 'pack-*.rev' file for runtime to chase down the offset for some object. Even though the lookup is constant time, the constant is heavier, since it can potentially involve two pointer walks in v2 indexes (one to access the 4-byte offset table, and potentially a second to access the double wide offset table).

Consider trying to map an object's pack offset to a relative position within that pack. In a cold-cache scenario, more page faults occur while switching between binary searching through the reverse index and searching through the *.idx file for an object's offset. Sure enough, with a cold cache (writing '3' into '/proc/sys/vm/drop_caches' after 'sync'ing), printing out the entire object's contents is still marginally faster than printing its size:

  Benchmark #1: git.compile cat-file --batch-check="%(objectsize:disk)" <obj >/dev/null
    Time (mean ± σ):      22.6 ms ±   0.5 ms    [User: 2.4 ms, System: 7.9 ms]
    Range (min … max):    21.4 ms …  23.5 ms    41 runs

  Benchmark #2: git.compile cat-file --batch <obj >/dev/null
    Time (mean ± σ):      17.2 ms ±   0.7 ms    [User: 2.8 ms, System: 5.5 ms]
    Range (min … max):    15.6 ms …  18.2 ms    45 runs

(Numbers taken in the kernel after cheating and using the next patch to generate a reverse index). There are a couple of approaches to improve cold cache performance not pursued here:

  - We could include the object offsets in the reverse index format.
    Predictably, this does result in fewer page faults, but it triples
    the size of the file, while simultaneously duplicating a ton of data
    already available in the .idx file. (This was the original way I
    implemented the format, and it did show
    `--batch-check='%(objectsize:disk)'` winning out against `--batch`.)

    On the other hand, this increase in size also results in a large
    block-cache footprint, which could potentially hurt other workloads.

  - We could store the mapping from pack to index position in more
    cache-friendly way, like constructing a binary search tree from the
    table and writing the values in breadth-first order. This would
    result in much better locality, but the price you pay is trading
    O(1) lookup in 'pack_pos_to_index()' for an O(log n) one (since you
    can no longer directly index the table).

So, neither of these approaches are taken here. (Thankfully, the format is versioned, so we are free to pursue these in the future.) But, cold cache performance likely isn't interesting outside of one-off cases like asking for the size of an object directly. In real-world usage, Git is often performing many operations in the revindex,

The trade-off is worth it, since we will avoid the vast majority of the cost of generating the revindex that the extra pointer chase will look like noise in the following patch's benchmarks.

This patch describes the format and prepares callers (like in pack-revindex.c) to be able to read *.rev files once they exist. An implementation of the writer will appear in the next patch, and callers will gradually begin to start using the writer in the patches that follow after that.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/technical/pack-format.txt |  17 ++++
 builtin/repack.c                        |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 112 +++++++++++++++++++++---
 pack-revindex.h                         |   7 +-
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 tmp-objdir.c                            |   4 +-
 8 files changed, 145 insertions(+), 13 deletions(-)

Taylor Blau <me@ttaylorr.com> writes:

These two are presumably 4-byte-wide network byte order integers. We should spell it out.

Likewise, how wide is each entry and in what byte order, and how many entries are there in the table?

	... oh, what about the "one beyond the last"?  We cannot
	go back to the forward index to learn the offset of such
	an non-existent object, can we?

Again, I expect it to be 4-byte-wide network byte order integer.

I said it when I saw the beginning of v1 API patches, but it is a bit unreasonable to call the act of "computing from the forward index" "to load from memory". Loading from disk perfectly works as a phrase, though.

We've seen hardcoded constant "12" twice so far in this patch.

We need a C proprocessor macro "#define RIDX_FILE_HEADER_SIZE 12" or something, perhaps?

Good. We are using 32-bit uint in network byte order. We should document it as such.

Let's not strip const away while casting, though. get_be32() ensures that it only reads and never writes thru the pointer, and p->revindex_data is a "const void *".

OK, here is the answer to my previous question. We should document that the table has num_objects entries in the on-disk file (we do not need to say that there is no sentinel entry in the table at the end).

Hmph, I missed where it got checked for consistency, though. If the file is corrupt and has say duplicated entries, we'd happily grab the data via get_be32(), for example.

Again, I know this is a kind of detail that is interesting to those who implemented the function, but I wonder how it would help those who wonder if they should call it or use some other method to achieve what they want.

On 1/14/2021 2:22 AM, Junio C Hamano wrote:

In the past, we've included the sentence "All multi-byte numbers are in network byte order." to clarify this. These two entries need to specify that the "identifier" is actually an integer. Perhaps these three values could be provided as:

+== pack-*.rev files have the format:
+
+  - A 4-byte identifier '0x52494458' ('RIDX').
+
+  - A 4-byte integer version (= 1)
+
+  - A 4-byte integer hash function version (= 1 for SHA-1, 2 for SHA-256)

Even if the consistency check is just verifying the trailing hash, that seems like something that requires O(N) before performing a lookup. Perhaps this was copied from somewhere else, or means something different?

Thanks, -Stolee

On Thu, Jan 14, 2021 at 07:07:08AM -0500, Derrick Stolee wrote:

For the .idx file, we check that the size is what we expect. This is important because it lets us access the mapped bytes in normal use without having to do a bounds check.

It looks like we do the same for the .rev file here, which is good. If calling that "checked for consistency" is too strong, I don't think it's a big deal to drop the wording (we do not make any such claim for open_pack_index()).

-Peff

On Wed, Jan 13, 2021 at 11:22:53PM -0800, Junio C Hamano wrote:

Yep, all entries are network order. I added a sentence at the bottom of this sub-section to say as much.

Good idea, thanks.

Agreed, and thanks for the suggestion. I take it that what you mean is:

- return get_be32((char *)p->revindex_data + (pos * sizeof(uint32_t))); + return get_be32((const char *)p->revindex_data + (pos * sizeof(uint32_t)));

...yes?

It doesn't, I'm mistaken. I removed that incorrect detail from this comment. Thanks for catching it.

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

We've changed the pack .idx file format once as the file format is versioned. I wonder if you considered placing the reverse index information in the same file, with version bump, in the .idx?

On Wed, Jan 13, 2021 at 11:26:59PM -0800, Junio C Hamano wrote:

Funny enough, I couldn't remember whether I considered this or not. Peff reminded me off-list that he and I *had* considered this, but decided against it.

The main benefit to introducing a new '.rev' format is that we can have packs that can be upgraded to write a reverse index without having to rewrite their forward index. It would also allow us to avoid teaching other implementations about a new version of the index file (since they can ignore it and continue to build their equivalent of the reverse index file in memory by reading the forward index).

(Peff reminds me that dumb-http does look at remote .idx files, so this new format would leak across to clients, whether or not that's something to be concerned about...).

Of course, having the contents of the .rev file be included in the .idx file nets us one fewer file to manage, but I'm not sure that's a reason to do things one way or another.

Your response did pique my interest, since I was wondering if we could improve the cold cache performance if the .rev file's contents were included in the .idx, but after giving it some thought I don't think we can. Reasons are:

  - If the reverse index's contents appears at the end of the .idx file,
    then in any .idx file large enough to matter, we'll almost certainly
    still be evicting cache lines back and forth when swapping between
    reading the forward- and reverse-indexes. So, no gains to be had
    there.

  - If, on the other hand, we included the reverse index's contents by
    interleaving it with the forward index's offsets, then we'd be
    worsening the cache performance of the forward index.

So, I'm more in favor of a new .rev file rather than a v3 .idx version. Apologies for not including more of a rationale "why" in the cover letter (had I not forgotten that I'd even considered it, I would have).

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

Yes, that was the primary thing I was wondering. As long as it was considered and rejected for good reason, that is good.

Thanks.

On Wed, Jan 13, 2021 at 05:28:06PM -0500, Taylor Blau wrote:

I think you've nicely covered the arguments for and against the extra offset here. This final paragraph ends in a comma, which makes me wonder if you wanted to say something more. I'd guess it is along the lines that most commands will be looking up more than one object, so that cold-cache effort is amortized.

Or another way of thinking about it: 17ms versus 25ms in the cold-cache for a _single_ object is not that big a deal, because the extra 8ms does not scale as we ask about more objects. Here's an actual argument in numbers (test repo is linux.git after building a .rev file using your series):

For a single object, the extra cold-cache costs give --batch a slight edge:

  $ git rev-parse HEAD >obj
  $ hyperfine -p 'echo 3 | sudo tee /proc/sys/vm/drop_caches' \
                 'git cat-file --buffer --batch-check="%(objectsize:disk)" <obj' \
                 'git cat-file --buffer --batch <obj'

  Benchmark #1: git cat-file --buffer --batch-check="%(objectsize:disk)" <obj
    Time (mean ± σ):      37.2 ms ±   8.3 ms    [User: 2.6 ms, System: 4.6 ms]
    Range (min … max):    28.5 ms …  55.6 ms    10 runs
   
  Benchmark #2: git cat-file --buffer --batch <obj
    Time (mean ± σ):      27.4 ms ±   3.4 ms    [User: 2.9 ms, System: 2.5 ms]
    Range (min … max):    23.2 ms …  37.1 ms    51 runs
   
  Summary
    'git cat-file --buffer --batch <obj' ran
      1.36 ± 0.35 times faster than 'git cat-file --buffer --batch-check="%(objectsize:disk)" <obj'

But with even a moderate number of objects, that's reversed:

  $ git cat-file --batch-all-objects --batch-check='%(objectname)' |
    shuffle | head -1000 >obj-1000
  $ hyperfine -p 'echo 3 | sudo tee /proc/sys/vm/drop_caches' \
                 'git cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000' \
		 'git cat-file --buffer --batch <obj-1000'
  
  Benchmark #1: git cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000
    Time (mean ± σ):      1.599 s ±  0.285 s    [User: 22.4 ms, System: 334.5 ms]
    Range (min … max):    0.816 s …  1.762 s    10 runs
   
  Benchmark #2: git cat-file --buffer --batch <obj-1000
    Time (mean ± σ):      1.972 s ±  0.225 s    [User: 343.5 ms, System: 404.2 ms]
    Range (min … max):    1.691 s …  2.283 s    10 runs
   
  Summary
    'git cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000' ran
      1.23 ± 0.26 times faster than 'git cat-file --buffer --batch <obj-1000'

Of course this isn't exactly an apples-to-apples comparison in the first place, since the --batch one is doing a lot more. So "winning" with objectsize:disk is not much of an accomplishment. A more interesting comparison would be the same operation on a repo with your series, versus one with the offset embedded in the .rev file, as the number of objects grows.

But since we don't have that readily available, another interesting comparison is stock git (with no .rev file) against your new .rev file, with a cold cache.

At 1000 objects, the old code has a slight win, because it has less to fault in from the disk (instead it's recreating the same data in RAM). "git.compile" is your branch below; "git" is a stock build of "next":

  Benchmark #1: git cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000
    Time (mean ± σ):      1.483 s ±  0.260 s    [User: 148.9 ms, System: 301.2 ms]
    Range (min … max):    0.792 s …  1.725 s    10 runs
   
  Benchmark #2: git.compile cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000
    Time (mean ± σ):      1.820 s ±  0.138 s    [User: 27.7 ms, System: 399.3 ms]
    Range (min … max):    1.610 s …  2.012 s    10 runs
   
  Summary
    'git cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000' ran
      1.23 ± 0.23 times faster than 'git.compile cat-file --buffer --batch-check="%(objectsize:disk)" <obj-1000'

But that edge drops to 1.08x at 10,000 objects, and then at 100,000 objects your code is a win (by 1.16x). And of course it's a giant win when the cache is already warm.

And in a cold cache, we'd expect a .rev file with offsets in it to be much worse, since there's many more bytes to pull from the disk.

All of which is a really verbose way of saying: you might want to add a few words after the comma:

  In real-world usage, Git is often performing many operations in the
  revindex (i.e., rather than asking about a single object, we'd
  generally ask about a range of history).

:) But hopefully it shows that including the offsets is not really making things better for the cold cache anyway.

Oh, there's a patch here, too. :)

It mostly looks good to me. I agree with Junio that "compute" is a better verb than "load" for generating the in-memory revindex.

Junio mentioned once spot where we lose constness through a cast. This is another. I wonder if revindex_map should just be a "char *" to make pointer arithmetic easier without having to cast.

But also...

If p->revindex_data were "const uint32_t *", then this line would just be:

  return get_be32(p->revindex_data + pos);

Not a huge deal either way since the whole point is to abstract this behind a function where it only has to be written once. I don't think there is any downside from the compiler's view (and we already use this trick for the bitmap name-hash cache).

Thinking out loud a bit: a .rev file means we're spending an extra map per pack (but not a descriptor, since we close after mmap). And like the .idx files (but unlike .pack file maps), we don't keep track of these and try to close them when under memory pressure. I think that's probably OK in terms of bytes. It may mean running up against operating system number-of-mmap limits more quickly when you have a very large number of packs, as mentioned in:

  https://lore.kernel.org/git/20200601044511.GA2529317@coredump.intra.peff.net/

But this is probably bumping the number of problematic packs from 30k to 20k. Both are sufficiently ridiculous that I don't think it matters in practice.

Probably not super important, but: should the .idx file still come last here? Simultaneous readers won't start using the pack until the .idx file is present. We'd probably prefer they see the whole thing atomically, than see a .idx missing its .rev (they won't ever produce a wrong answer, but they'll generate the in-core revindex on the fly when they don't need to).

I guess one could argue that .bitmap files should get similar treatment, but we'd not generally see those in the quarantine objdir anyway, so nobody ever gave it much thought.

-Peff

On Fri, Jan 22, 2021 at 05:54:18PM -0500, Jeff King wrote:

Thanks for including a compelling argument in favor of the approach that I took in this patch.

I added something along the lines of what you suggested to the final paragraph, so now it concludes nicely instead of ending in a comma. I briefly considered whether I should add something about how these operations scale and how the warming efforts are really amortized across all of the objects, but I decided against it.

I think that this argument is already documented here, and that there's no way to concisely state it in an already long patch. Interested readers will easily be able to find our discussion here, which is good.

:-).

Yeah, I settled on load_pack_revindex() either calling "create_pack_revindex_in_memory()" or "load_pack_revindex_from_disk()".

Honestly, I'm not a huge fan of implicitly scaling pos by sizeof(*p->revindex_data), but I can understand why it reads more clearly here. I don't really feel strongly either way, so I'm happy to change it in favor of your suggestion.

Of course, since RIDX_HEADER_SIZE is in bytes, not uint32_t's (and it has to be, since it's also used in the RIDX_MIN_SIZE macro, which is compared against the st_size of stating the .rev file), you have to do gross stuff like:

  p->revindex_data = (const uint32_t *)((const char *)p->revindex_map + RIDX_HEADER_SIZE);

But I guess the tradeoff is worth it, since the readers are easier to parse.

Agreed.

Yeah, you're right (.idx files should come last, and probably an argument to include .bitmap files here, too, exists. I'll leave the latter as #leftoverbits).

Thanks, Taylor

On Mon, Jan 25, 2021 at 12:44:53PM -0500, Taylor Blau wrote:

That sounds good. It is sort of arguing against a strawman anyway.

Perfect.

Yeah, that is definitely a downside. Perhaps keeping everything in bytes makes things a bit more obvious. In which case I might suggest that revindex_data just be a "const char *". You'd have to scale any pointer computations at the point of use then, but you'd avoid needing to do any extra casting.

-Peff

Taylor Blau <me@ttaylorr.com> writes:

At some point, we may want to 

 - introduce .idx version 3 that is more extensible, so that the
   reverse info is included in one of its chunks;

 - make the .rev data for all packs stored as a chunk in .midx, so
   we can first check with .midx and not open any .rev files.

either of which would reduce the numberfrom 30k down to 10k ;-)

On Mon, Jan 25, 2021 at 11:04:33AM -0800, Junio C Hamano wrote:

I'm not opposed to doing so outside of this series. I'd be fine with resurrecting the series that Stolee posted a while ago to extract a "chunk writer" API (for using in the commit-graph and MIDX code) to also be used here.

That got stalled out because of the conflicts that it would have produced with Abhishek's work, but now that that's getting picked up it could move forward.

But brian is also working on an index v3 for some hash transition stuff, so I'd rather let that settle first.

Of course, you could combine those efforts, but I don't think that what we have here is such a bad interim state.

This is trickier than you might think because of how the MIDX selects a pack when more than one pack contains a given object. There is also the concept of a "multi-pack reverse index" which you can think of as the reverse index for a pack that is more-or-less concatenating all of the objects in the MIDX together (in pack order). That is the same order we'll use to lay out the bits of a multi-pack bitmap, eventually.

Your ";-)" is a good reminder that there are probably many other problems with having 30k (or even 10k!) packs that would make solving this (index v3 + MIDX chunk) not worthwhile.

Thanks, Taylor

Now that the pack.writeReverseIndex configuration is respected in both 'git index-pack' and 'git pack-objects' (and therefore, all of their callers), we can safely advertise it for use in the git-config manual.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/config/pack.txt | 7 +++++++
 1 file changed, 7 insertions(+)

Now that we have an implementation that can write the new reverse index format, enable writing a .rev file in 'git pack-objects' by consulting the pack.writeReverseIndex configuration variable.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c   |  7 +++++++
 t/t5325-reverse-index.sh | 13 +++++++++++++
 2 files changed, 20 insertions(+)

On Wed, Jan 13, 2021 at 05:28:19PM -0500, Taylor Blau wrote:

This turned out delightfully simple. And I guess this is the "why is WRITE_REV" caller I asked about from patch 2. It is finish_tmp_packfile() where the magic happens. That unconditionally calls write_rev_file(), but it's a noop if WRITE_REV isn't specified.

Makes sense.

-Peff

On Fri, Jan 22, 2021 at 06:57:35PM -0500, Jeff King wrote:

Oh, one subtlety here: this is in pack-objects itself, _not_ in git-repack. This has bit us before with options like repack.writebitmaps, which was originally pack.writebitmaps and introduced all sorts of awkwardness (because pack-objects serves many other purposes besides repacks).

I think this _might_ be OK, because we wouldn't even hit the code-paths that handle this unless we are also writing a .idx (and really, the point is that the two should always be written together or not at all).

So probably it's fine, but I wonder if we should err on the side of conservatism by saying that pack-objects will not change behavior without receiving a new command-line option, and that repack should trigger that option. I dunno. I guess that it makes it weird with respect to index-pack, which wants to see a very low-level option, too. So maybe this is the best way forward.

(Sorry for being non-committal; I'm mostly thinking out loud).

-Peff

On Fri, Jan 22, 2021 at 07:08:30PM -0500, Jeff King wrote:

I'd think that we'd want a single option to control whether or not reverse indexes are written to disk. I briefly considered (and I believe that you and I even discussed) having options to control this behavior per command, but it got out of hand quickly.

And that might have been OK, but I don't think the complexity was even warranted, because really on-disk reverse indexes are an all-or-nothing thing. That is: either you want to have revindexes accompanying .packs, or you don't. IOW, it doesn't matter whether those packs were pushed to us, or generated during repack, or from another pack-objects or what have you.

Thanks, Taylor

On Mon, Jan 25, 2021 at 03:21:17PM -0500, Taylor Blau wrote:

Yeah, I think per-command is something we should avoid.

My concern is mostly that pack-objects in a non-repack setting would accidentally try to write a .rev file (or complain that it cannot). But again, we already have the same potential issue for .idx files, so by following those code paths as you did, we should be OK.

And certainly we test that code path a lot in the normal test suite (i.e., every fetch or push), so your run-the-test-suite-with-rev-files patches from later would presumably catch it otherwise.

Right, I agree with all of that.

-Peff

This patch prepares for callers to be able to write reverse index files to disk.

It adds the necessary machinery to write a format-compliant .rev file from within 'write_rev_file()', which is called from 'finish_tmp_packfile()'.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-write.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 pack.h       |   4 ++
 2 files changed, 126 insertions(+), 1 deletion(-)

On Wed, Jan 13, 2021 at 05:28:11PM -0500, Taylor Blau wrote:

qsort? Don't we have a perfectly good radix sort for this exact purpose? :)

I guess it is awkward to use because it hard-codes the assumption that we are sorting revindex_entry structs, with their offsets directly available.

We _could_ actually just generate an in-memory revindex array, and then use that to write out the .rev file. That has the nice property that we'd continue exercising the fallback code in the tests.

But a revindex_entry is much larger than the uint32_t's we need here. So we'd be incurring extra memory costs during the generation, which is probably not worth it. If we want better test coverage, we probably should explicitly run a series of tests both with and without a .rev file.

It's possible we'd still benefit from using a more generalized radix sort, but it probably isn't worth the trouble. The timings from 8b8dfd5132 (pack-revindex: radix-sort the revindex, 2013-07-11) claim a 4x speedup on sorting 3M entries (the size matters because we are comparing an O(n) sort versus an O(n log n) one). We can imagine that at 10M entries for the current kernel, it might even be 8x. But the absolute numbers are pretty small. The radix sort takes ~150ms for linux.git on my machine. At 8x, that's 1.2s. For a repack of the kernel, that is mostly a drop in the bucket. It mattered a lot more when many processes were doing it on the fly.

Dereferencing a pointer to index another array always makes me nervous that we may have a bounds problem with bogus data.

In this case we know it is OK because we filled the array ourselves with in-bound numbers in write_rev_index_positions.

I was surprised we didn't define these already on the reading side, but it looks like we didn't. In patch 1, we probably should be checking RIDX_SIGNATURE in load_revindex_from_disk(). But much more importantly, we should be checking that we find version 1, since that's what will make it safe to later invent a version 2.

I forgot to comment on this in patch 1, but: I think the format is really independent of the hash size. The contents are identical for a sha-1 versus sha-256 file.

That said, I don't overly mind having a hash identifier if it might help debug things (OTOH, how the heck do you end up with one that matches the trailer's packfile but _doesn't_ match the trailer's contents?).

If we do have it, should we also be checking it in the loading function?

So if the caller gave us a name, we force-overwrite it. That seemed weird to me at first, but it makes sense; the atomic rename-into-place writers will not be passing in the name. And this is exactly how write_idx_file() works.

I wonder if we could factor out some of this repeated logic, but I suspect it is mostly diminishing returns. Maybe this "open a pack file for writing" could become a helper function, though.

It is a little funny that the write-rev function has both WRITE_REV and WRITE_REV_VERIFY (which we must be sure are not both provided), but we do not need both for the IDX.

I thought maybe the reason is that we'd pass these flags to write_idx_file() or similar, and it would need to know whether to write just an idx, or both. That doesn't seem to happen in this patch, but maybe it does in a future one...

-Peff

On Fri, Jan 22, 2021 at 06:24:59PM -0500, Jeff King wrote:

Yeah, I think your argument against it (which I agree with is basically):

  We could, and it would be faster, but it would (1) require allocating
  twice as much data, and (2) the speed increase is a drop in the bucket
  on any repository with enough objects to even notice it.

I'll add something to that effect to the commit message.

Right.

:-). Thanks for noticing, fixed.

Right; the format is identical. That is, the fields are the same, but the hashes are longer.

I'm not opposed to it, but I imagined that this field would be primarily for debugging purposes. I was surprised to learn that we _don't_ verify the checksum for .idx files. So, I'm reluctant to start doing so here, honestly.

Yep.

Yeah. I tried factoring it out before replying, and it's a little gross. Most of my discomfort with it lies in the complexity of the parameters.

Consider extracting the code in write_idx_file():

  - There would need to be a double pointer for 'index_name' (which is
    sometimes read, and sometimes written to).

  - There would be an unsigned bit for "verify" (i.e., "open with
    hashfd_check() or not").

  - There would be a "pattern" variable if we were creating a new
    temporary file with odb_mkstemp().

Having the caller be forced to juggle the combinations of passing NULL/0 or not for each of those three makes me leery that this is worth doing, so I tend to agree with your judgement that this provides a diminishing return.

Thanks, Taylor

On Mon, Jan 25, 2021 at 02:15:18PM -0500, Taylor Blau wrote:

Yep, that's accurate.

It might make more of a difference when we eventually have a revindex cache for a midx (because there we're mostly doing things linear in the number of objects, and not actually traversing). But I'm quite happy to punt it until then (or later; even there I'd guess it might shave one second off a 10-15 second operation. That's not nothing, but if nobody ever cares enough to implement it, I won't be sad).

Hmm. Actually, I wasn't thinking it through completely. I thought the file would literally have the exact same bytes in it, but the packfile hash as well as the hashfd() trailing hash would both be different sizes. So even if it doesn't match the packfile (which obviously is a bug), it would hard to even be able to figure that out without knowing the hash identifier.

I think we're talking about two different things. I just meant that if we see a .rev file that says "I'm sha256", we should make sure we are in a sha256 repo (since that is what we'd be assuming for the .idx and .pack files!).

We can't do that same check for .idx files, because they don't have a hash identifier field in them.

Checking that the pack hash matches the trailer from the packfile is a separate matter. I also think that's worth doing, but am likewise surprised that we don't check it for the .idx. I'm OK leaving it out since we don't do it there, either.

Thanks for taking a look. I'm not too surprised it turned out ugly.

-Peff

Add a new option that unconditionally enables the pack.writeReverseIndex setting in order to run the whole test suite in a mode that generates on-disk reverse indexes. Additionally, enable this mode in the second run of tests under linux-gcc in 'ci/run-build-and-tests.sh'.

Once on-disk reverse indexes are proven out over several releases, we can change the default value of that configuration to 'true', and drop this patch.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/index-pack.c      | 5 ++++-
 builtin/pack-objects.c    | 2 ++
 ci/run-build-and-tests.sh | 1 +
 pack-revindex.h           | 2 ++
 t/README                  | 3 +++
 5 files changed, 12 insertions(+), 1 deletion(-)

Teach 'git index-pack' to optionally write and verify reverse index with '--[no-]rev-index', as well as respecting the 'pack.writeReverseIndex' configuration option.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-index-pack.txt | 20 ++++++---
 builtin/index-pack.c             | 64 +++++++++++++++++++++++-----
 t/t5325-reverse-index.sh         | 71 ++++++++++++++++++++++++++++++++
 3 files changed, 139 insertions(+), 16 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

On Wed, Jan 13, 2021 at 05:28:15PM -0500, Taylor Blau wrote:

I wondered which option was incompatible, but couldn't see from the context. It is "index-pack -o", which kind of makes sense. We can derive "foo.rev" from "foo.idx", but normally "-o" does not do any deriving.

So I was all set to say "OK, we can live without it", but...

...here we do end up deriving ".rev" from ".idx" anyway. So I guess we probably could support "-o". I also wonder what happens with "git index-pack -o foo.idx" when pack.writeReverseIndex is set. It looks like it would just work because of this block. But then shouldn't "--rev-index" work, too? And indeed, there is a test for that at the end of the patch! So is the documentation just wrong?

I admit to finding the use of opts.flags versus the rev_index option a bit confusing. It seems like they are doing roughly the same thing, but influenced by different sources. It seems like we should be able to have a single local variable (then that goes on to set opts.flags for any sub-functions we call). Or maybe two, if we need to distinguish config versus command-line, but then they should have clear names (rev_index_config and rev_index_cmdline or something).

As an aside, looking at derive_filename(), it seems a bit weird that one argument has a dot in the suffix and the other does not. I guess you are following the convention from write_special_file(), which omits it in the newly-added suffix. But it is slightly awkward to omit it for the old suffix in derive_filename(), because we want to strip_suffix() it all at once.

Probably not that big a deal, but if anybody feels strongly, then derive_filename() could do:

  if (!strip_suffix(pack_name, strip, &len) ||
      !len || pack_name[len] != '.')
	die("does not end in .%s", strip);

IMHO we'll eventually want to turn this feature on by default. In which case we'll have to update every caller which is checking the config manually. Should we hide this in a function that looks up the config, and sets the default? Or alternatively, I guess, they could all use some shared initializer for "flags".

This isn't that subtle of a corruption, because we are corrupting the first 4 bytes, which is the magic signature. Maybe something further in the actual data would be interesting instead of or in addition?

I dunno. There are a lot of edge cases around corruption (likewise, we might care how the normal reading code-path perceives a signature corruption like this). I'm not sure it's all that interesting to test all of them.

Hey, we _do_ support "--rev-index -o". Is it just the documentation that is wrong?

-Peff

On Fri, Jan 22, 2021 at 06:53:11PM -0500, Jeff King wrote:

Hah! The documentation is just plain wrong. It's been a while, but I have a vague recollection of writing this documentation before changing the implementation of index-pack to allow this. Clearly, I forgot to go back to update the broken documentation.

Hilariously, there is even a test in t5325 that demonstrates this working! 'git index-pack --rev-index -o other.idx' writes both 'other.idx' and 'other.rev'. That was easy :-).

Yeah, I know. It's because we already pass a pointer to a struct pack_idx_option to git_index_pack_config(), so in effect the 'flags' on that struct *is* rev_index_config.

It's a little ugly, I agree, but I'm skeptical that the effort to clean it up is worth it, mostly because the pack_idx_option struct probably shouldn't be part of the index-pack builtin in the first place.

That does make the callers look nicer, but it needs an extra two things:

Hi,

Here is a third reroll of my series to introduce an on-disk format for the reverse index. Since the first series (to introduce a new API) has been merged to 'next', this series has been rebased onto 'next', too.

This version is largely unchanged from the previous, with the following exceptions:

  - Some commit messages and documentation have been clarified to address
    reviewer questions (including why we don't want to store offsets in the .rev
    file, and that all four-byte numbers are in network order, etc.).

  - A few more things are done on opening the revindex file, namely checking
    that the version/hash ID are known.

  - The idiom "load in memory" has been removed.

  - Other minor changes.

A range diff is below.

Thanks in advance for your review.

Taylor Blau (10):
  packfile: prepare for the existence of '*.rev' files
  pack-write.c: prepare to write 'pack-*.rev' files
  builtin/index-pack.c: allow stripping arbitrary extensions
  builtin/index-pack.c: write reverse indexes
  builtin/pack-objects.c: respect 'pack.writeReverseIndex'
  Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
  t: prepare for GIT_TEST_WRITE_REV_INDEX
  t: support GIT_TEST_WRITE_REV_INDEX
  pack-revindex: ensure that on-disk reverse indexes are given
    precedence
  t5325: check both on-disk and in-memory reverse index

 Documentation/config/pack.txt           |   7 ++
 Documentation/git-index-pack.txt        |  18 ++-
 Documentation/technical/pack-format.txt |  20 ++++
 builtin/index-pack.c                    |  69 +++++++++--
 builtin/pack-objects.c                  |   9 ++
 builtin/repack.c                        |   1 +
 ci/run-build-and-tests.sh               |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 148 ++++++++++++++++++++++--
 pack-revindex.h                         |  14 ++-
 pack-write.c                            | 120 ++++++++++++++++++-
 pack.h                                  |   4 +
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 t/README                                |   3 +
 t/t5319-multi-pack-index.sh             |   5 +-
 t/t5325-reverse-index.sh                | 142 +++++++++++++++++++++++
 t/t5604-clone-reference.sh              |   2 +-
 t/t5702-protocol-v2.sh                  |  12 +-
 t/t6500-gc.sh                           |   6 +-
 t/t9300-fast-import.sh                  |   5 +-
 tmp-objdir.c                            |   6 +-
 22 files changed, 567 insertions(+), 42 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

Range-diff against v2:
21:  6742c15c84 !  1:  6f8b70ab27 packfile: prepare for the existence of '*.rev' files
    @@ Commit message
         is versioned, so we are free to pursue these in the future.) But, cold
         cache performance likely isn't interesting outside of one-off cases like
         asking for the size of an object directly. In real-world usage, Git is
    -    often performing many operations in the revindex,
    +    often performing many operations in the revindex (i.e., asking about
    +    many objects rather than a single one).

         The trade-off is worth it, since we will avoid the vast majority of the
         cost of generating the revindex that the extra pointer chase will look
    @@ Documentation/technical/pack-format.txt: Pack file entry: <+
     +
     +  - A 4-byte magic number '0x52494458' ('RIDX').
     +
    -+  - A 4-byte version identifier (= 1)
    ++  - A 4-byte version identifier (= 1).
     +
    -+  - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256)
    ++  - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256).
     +
    -+  - A table of index positions, sorted by their corresponding offsets in the
    -+    packfile.
    ++  - A table of index positions (one per packed object, num_objects in
    ++    total, each a 4-byte unsigned integer in network order), sorted by
    ++    their corresponding offsets in the packfile.
     +
     +  - A trailer, containing a:
     +
     +    checksum of the corresponding packfile, and
     +
     +    a checksum of all of the above.
    ++
    ++All 4-byte numbers are in network order.
     +
      == multi-pack-index (MIDX) files have the following format:

    @@ object-store.h: struct packed_git {
      		 multi_pack_index:1;
      	unsigned char hash[GIT_MAX_RAWSZ];
      	struct revindex_entry *revindex;
    -+	const void *revindex_data;
    -+	const void *revindex_map;
    ++	const uint32_t *revindex_data;
    ++	const uint32_t *revindex_map;
     +	size_t revindex_size;
      	/* something like ".git/objects/pack/xxxxx.pack" */
      	char pack_name[FLEX_ARRAY]; /* more */
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
      }

     -int load_pack_revindex(struct packed_git *p)
    -+static int load_pack_revindex_from_memory(struct packed_git *p)
    ++static int create_pack_revindex_in_memory(struct packed_git *p)
      {
     -	if (!p->revindex) {
     -		if (open_pack_index(p))
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
     +	return xstrfmt("%.*s.rev", (int)len, p->pack_name);
     +}
     +
    -+#define RIDX_MIN_SIZE (12 + (2 * the_hash_algo->rawsz))
    ++#define RIDX_HEADER_SIZE (12)
    ++#define RIDX_MIN_SIZE (RIDX_HEADER_SIZE + (2 * the_hash_algo->rawsz))
    ++
    ++struct revindex_header {
    ++	uint32_t signature;
    ++	uint32_t version;
    ++	uint32_t hash_id;
    ++};
     +
     +static int load_revindex_from_disk(char *revindex_name,
     +				   uint32_t num_objects,
    -+				   const void **data, size_t *len)
    ++				   const uint32_t **data_p, size_t *len_p)
     +{
     +	int fd, ret = 0;
     +	struct stat st;
    ++	void *data = NULL;
     +	size_t revindex_size;
    ++	struct revindex_header *hdr;
     +
     +	fd = git_open(revindex_name);
     +
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
     +		goto cleanup;
     +	}
     +
    -+	*len = revindex_size;
    -+	*data = xmmap(NULL, revindex_size, PROT_READ, MAP_PRIVATE, fd, 0);
    ++	data = xmmap(NULL, revindex_size, PROT_READ, MAP_PRIVATE, fd, 0);
    ++	hdr = data;
    ++
    ++	if (ntohl(hdr->signature) != RIDX_SIGNATURE) {
    ++		ret = error(_("reverse-index file %s has unknown signature"), revindex_name);
    ++		goto cleanup;
    ++	}
    ++	if (ntohl(hdr->version) != 1) {
    ++		ret = error(_("reverse-index file %s has unsupported version %"PRIu32),
    ++			    revindex_name, ntohl(hdr->version));
    ++		goto cleanup;
    ++	}
    ++	if (!(ntohl(hdr->hash_id) == 1 || ntohl(hdr->hash_id) == 2)) {
    ++		ret = error(_("reverse-index file %s has unsupported hash id %"PRIu32),
    ++			    revindex_name, ntohl(hdr->hash_id));
    ++		goto cleanup;
    ++	}
     +
     +cleanup:
    ++	if (ret) {
    ++		if (data)
    ++			munmap(data, revindex_size);
    ++	} else {
    ++		*len_p = revindex_size;
    ++		*data_p = (const uint32_t *)data;
    ++	}
    ++
     +	close(fd);
     +	return ret;
     +}
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
     +	if (ret)
     +		goto cleanup;
     +
    -+	p->revindex_data = (char *)p->revindex_map + 12;
    ++	p->revindex_data = (const uint32_t *)((const char *)p->revindex_map + RIDX_HEADER_SIZE);
     +
     +cleanup:
     +	free(revindex_name);
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)
     +
     +	if (!load_pack_revindex_from_disk(p))
     +		return 0;
    -+	else if (!load_pack_revindex_from_memory(p))
    ++	else if (!create_pack_revindex_in_memory(p))
     +		return 0;
     +	return -1;
     +}
    @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
     +	if (p->revindex)
     +		return p->revindex[pos].nr;
     +	else
    -+		return get_be32((char *)p->revindex_data + (pos * sizeof(uint32_t)));
    ++		return get_be32(p->revindex_data + pos);
      }

      off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
    @@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_
      }

      ## pack-revindex.h ##
    -@@ pack-revindex.h: struct packed_git;
    +@@
    +  *   can be found
    +  */
    +
    ++#define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
    ++#define RIDX_VERSION 1
    ++
    + struct packed_git;
    +
      /*
       * load_pack_revindex populates the revindex's internal data-structures for the
       * given pack, returning zero on success and a negative value otherwise.
     + *
    -+ * If a '.rev' file is present, it is checked for consistency, mmap'd, and
    -+ * pointers are assigned into it (instead of using the in-memory variant).
    ++ * If a '.rev' file is present it is mmap'd, and pointers are assigned into it
    ++ * (instead of using the in-memory variant).
       */
      int load_pack_revindex(struct packed_git *p);

    @@ packfile.h: uint32_t get_pack_fanout(struct packed_git *p, uint32_t value);

      ## tmp-objdir.c ##
     @@ tmp-objdir.c: static int pack_copy_priority(const char *name)
    + 		return 1;
    + 	if (ends_with(name, ".pack"))
      		return 2;
    - 	if (ends_with(name, ".idx"))
    +-	if (ends_with(name, ".idx"))
    ++	if (ends_with(name, ".rev"))
      		return 3;
     -	return 4;
    -+	if (ends_with(name, ".rev"))
    ++	if (ends_with(name, ".idx"))
     +		return 4;
     +	return 5;
      }
22:  8648c87fa7 !  2:  5efc870742 pack-write.c: prepare to write 'pack-*.rev' files
    @@ Commit message
         from within 'write_rev_file()', which is called from
         'finish_tmp_packfile()'.

    +    Similar to the process by which the reverse index is computed in memory,
    +    these new paths also have to sort a list of objects by their offsets
    +    within a packfile. These new paths use a qsort() (as opposed to a radix
    +    sort), since our specialized radix sort requires a full revindex_entry
    +    struct per object, which is more memory than we need to allocate.
    +
    +    The qsort is obviously slower, but the theoretical slowdown would
    +    require a repository with a large amount of objects, likely implying
    +    that the time spent in, say, pack-objects during a repack would dominate
    +    the overall runtime.
    +
         Signed-off-by: Taylor Blau <me@ttaylorr.com>

      ## pack-write.c ##
    @@ pack-write.c: const char *write_idx_file(const char *index_name, struct pack_idx
     +	return 0;
     +}
     +
    -+#define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
    -+#define RIDX_VERSION 1
    -+
     +static void write_rev_header(struct hashfile *f)
     +{
     +	uint32_t oid_version;
    @@ pack-write.c: void finish_tmp_packfile(struct strbuf *name_buffer,
     +
      	free((void *)idx_tmp_name);
      }
    +

      ## pack.h ##
     @@ pack.h: struct pack_idx_option {
    @@ pack.h: struct pack_idx_option {

      	uint32_t version;
      	uint32_t off32_limit;
    -@@ pack.h: off_t write_pack_header(struct hashfile *f, uint32_t);
    - void fixup_pack_header_footer(int, unsigned char *, const char *, uint32_t, unsigned char *, off_t);
    - char *index_pack_lockfile(int fd);
    +@@ pack.h: struct ref;
    +
    + void write_promisor_file(const char *promisor_name, struct ref **sought, int nr_sought);

     +const char *write_rev_file(const char *rev_name, struct pack_idx_entry **objects, uint32_t nr_objects, const unsigned char *hash, unsigned flags);
     +
 -:  ---------- >  3:  8a3e70454b builtin/index-pack.c: allow stripping arbitrary extensions
23:  5b18ada611 !  4:  a8ee59fccf builtin/index-pack.c: write reverse indexes
    @@ Documentation/git-index-pack.txt: git-index-pack - Build pack index file for an

      OPTIONS
     @@ Documentation/git-index-pack.txt: OPTIONS
    - 	file is constructed from the name of packed archive
    - 	file by replacing .pack with .idx (and the program
      	fails if the name of packed archive does not end
    --	with .pack).
    -+	with .pack). Incompatible with `--rev-index`.
    -+
    + 	with .pack).
    +
     +--[no-]rev-index::
     +	When this flag is provided, generate a reverse index
     +	(a `.rev` file) corresponding to the given pack. If
     +	`--verify` is given, ensure that the existing
     +	reverse index is correct. Takes precedence over
     +	`pack.writeReverseIndex`.
    -
    ++
      --stdin::
      	When this flag is provided, the pack is read from stdin
    + 	instead and a copy is then written to <pack-file>. If

      ## builtin/index-pack.c ##
     @@
    @@ builtin/index-pack.c

      struct object_entry {
      	struct pack_idx_entry idx;
    -@@ builtin/index-pack.c: static void fix_unresolved_deltas(struct hashfile *f)
    - 	free(sorted_by_pos);
    - }
    -
    --static const char *derive_filename(const char *pack_name, const char *suffix,
    --				   struct strbuf *buf)
    -+static const char *derive_filename(const char *pack_name, const char *strip,
    -+				   const char *suffix, struct strbuf *buf)
    - {
    - 	size_t len;
    --	if (!strip_suffix(pack_name, ".pack", &len))
    --		die(_("packfile name '%s' does not end with '.pack'"),
    --		    pack_name);
    -+	if (!strip_suffix(pack_name, strip, &len))
    -+		die(_("packfile name '%s' does not end with '%s'"),
    -+		    pack_name, strip);
    - 	strbuf_add(buf, pack_name, len);
    - 	strbuf_addch(buf, '.');
    - 	strbuf_addstr(buf, suffix);
    -@@ builtin/index-pack.c: static void write_special_file(const char *suffix, const char *msg,
    - 	int msg_len = strlen(msg);
    -
    - 	if (pack_name)
    --		filename = derive_filename(pack_name, suffix, &name_buf);
    -+		filename = derive_filename(pack_name, ".pack", suffix, &name_buf);
    - 	else
    - 		filename = odb_pack_name(&name_buf, hash, suffix);
    -
     @@ builtin/index-pack.c: static void write_special_file(const char *suffix, const char *msg,

      static void final(const char *final_pack_name, const char *curr_pack_name,
    @@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char
      				usage(index_pack_usage);
      			continue;
     @@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char *prefix)
    - 	if (from_stdin && hash_algo)
    - 		die(_("--object-format cannot be used with --stdin"));
      	if (!index_name && pack_name)
    --		index_name = derive_filename(pack_name, "idx", &index_name_buf);
    -+		index_name = derive_filename(pack_name, ".pack", "idx", &index_name_buf);
    -+
    + 		index_name = derive_filename(pack_name, "pack", "idx", &index_name_buf);
    +
     +	opts.flags &= ~(WRITE_REV | WRITE_REV_VERIFY);
     +	if (rev_index) {
     +		opts.flags |= verify ? WRITE_REV_VERIFY : WRITE_REV;
     +		if (index_name)
     +			rev_index_name = derive_filename(index_name,
    -+							 ".idx", "rev",
    ++							 "idx", "rev",
     +							 &rev_index_name_buf);
     +	}
    -
    ++
      	if (verify) {
      		if (!index_name)
    + 			die(_("--verify with no packfile name given"));
     @@ builtin/index-pack.c: int cmd_index_pack(int argc, const char **argv, const char *prefix)
      	for (i = 0; i < nr_objects; i++)
      		idx_objects[i] = &objects[i].idx;
24:  68bde3ea97 =  5:  5bebe05a16 builtin/pack-objects.c: respect 'pack.writeReverseIndex'
25:  38a253d0ce =  6:  7e29f2d3a0 Documentation/config/pack.txt: advertise 'pack.writeReverseIndex'
26:  12cdf2d67a =  7:  7cf16485cc t: prepare for GIT_TEST_WRITE_REV_INDEX
27:  6b647d9775 !  8:  02550a251d t: support GIT_TEST_WRITE_REV_INDEX
    @@ builtin/pack-objects.c: int cmd_pack_objects(int argc, const char **argv, const

      ## ci/run-build-and-tests.sh ##
     @@ ci/run-build-and-tests.sh: linux-gcc)
    - 	export GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1
      	export GIT_TEST_MULTI_PACK_INDEX=1
      	export GIT_TEST_ADD_I_USE_BUILTIN=1
    + 	export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master
     +	export GIT_TEST_WRITE_REV_INDEX=1
      	make test
      	;;
    @@ pack-revindex.h
       *   can be found
       */

    ++
    + #define RIDX_SIGNATURE 0x52494458 /* "RIDX" */
    + #define RIDX_VERSION 1
    +
     +#define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
     +
      struct packed_git;
28:  48926ae182 !  9:  a66d2f9f7c pack-revindex: ensure that on-disk reverse indexes are given precedence
    @@ pack-revindex.c
      	off_t offset;
     @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)

    - static int load_pack_revindex_from_memory(struct packed_git *p)
    + static int create_pack_revindex_in_memory(struct packed_git *p)
      {
     +	if (git_env_bool(GIT_TEST_REV_INDEX_DIE_IN_MEMORY, 0))
     +		die("dying as requested by '%s'",
    @@ pack-revindex.c: static void create_pack_revindex(struct packed_git *p)

      ## pack-revindex.h ##
     @@
    -  */
    + #define RIDX_VERSION 1

      #define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX"
     +#define GIT_TEST_REV_INDEX_DIE_IN_MEMORY "GIT_TEST_REV_INDEX_DIE_IN_MEMORY"
 -:  ---------- > 10:  38c8afabf2 t5325: check both on-disk and in-memory reverse index
--
2.30.0.138.g6d7191ea01

Specify the format of the on-disk reverse index 'pack-*.rev' file, as well as prepare the code for the existence of such files.

The reverse index maps from pack relative positions (i.e., an index into the array of object which is sorted by their offsets within the packfile) to their position within the 'pack-*.idx' file. Today, this is done by building up a list of (off_t, uint32_t) tuples for each object (the off_t corresponding to that object's offset, and the uint32_t corresponding to its position in the index). To convert between pack and index position quickly, this array of tuples is radix sorted based on its offset.

This has two major drawbacks:

First, the in-memory cost scales linearly with the number of objects in a pack. Each 'struct revindex_entry' is sizeof(off_t) + sizeof(uint32_t) + padding bytes for a total of 16.

To observe this, force Git to load the reverse index by, for e.g., running 'git cat-file --batch-check="%(objectsize:disk)"'. When asking for a single object in a fresh clone of the kernel, Git needs to allocate 120+ MB of memory in order to hold the reverse index in memory.

Second, the cost to sort also scales with the size of the pack. Luckily, this is a linear function since 'load_pack_revindex()' uses a radix sort, but this cost still must be paid once per pack per process.

As an example, it takes ~60x longer to print the _size_ of an object as it does to print that entire object's _contents_:

  Benchmark #1: git.compile cat-file --batch <obj
    Time (mean ± σ):       3.4 ms ±   0.1 ms    [User: 3.3 ms, System: 2.1 ms]
    Range (min … max):     3.2 ms …   3.7 ms    726 runs

  Benchmark #2: git.compile cat-file --batch-check="%(objectsize:disk)" <obj
    Time (mean ± σ):     210.3 ms ±   8.9 ms    [User: 188.2 ms, System: 23.2 ms]
    Range (min … max):   193.7 ms … 224.4 ms    13 runs

Instead, avoid computing and sorting the revindex once per process by writing it to a file when the pack itself is generated.

The format is relatively straightforward. It contains an array of uint32_t's, the length of which is equal to the number of objects in the pack. The ith entry in this table contains the index position of the ith object in the pack, where "ith object in the pack" is determined by pack offset.

One thing that the on-disk format does _not_ contain is the full (up to) eight-byte offset corresponding to each object. This is something that the in-memory revindex contains (it stores an off_t in 'struct revindex_entry' along with the same uint32_t that the on-disk format has). Omit it in the on-disk format, since knowing the index position for some object is sufficient to get a constant-time lookup in the pack-*.idx file to ask for an object's offset within the pack.

This trades off between the on-disk size of the 'pack-*.rev' file for runtime to chase down the offset for some object. Even though the lookup is constant time, the constant is heavier, since it can potentially involve two pointer walks in v2 indexes (one to access the 4-byte offset table, and potentially a second to access the double wide offset table).

Consider trying to map an object's pack offset to a relative position within that pack. In a cold-cache scenario, more page faults occur while switching between binary searching through the reverse index and searching through the *.idx file for an object's offset. Sure enough, with a cold cache (writing '3' into '/proc/sys/vm/drop_caches' after 'sync'ing), printing out the entire object's contents is still marginally faster than printing its size:

  Benchmark #1: git.compile cat-file --batch-check="%(objectsize:disk)" <obj >/dev/null
    Time (mean ± σ):      22.6 ms ±   0.5 ms    [User: 2.4 ms, System: 7.9 ms]
    Range (min … max):    21.4 ms …  23.5 ms    41 runs

  Benchmark #2: git.compile cat-file --batch <obj >/dev/null
    Time (mean ± σ):      17.2 ms ±   0.7 ms    [User: 2.8 ms, System: 5.5 ms]
    Range (min … max):    15.6 ms …  18.2 ms    45 runs

(Numbers taken in the kernel after cheating and using the next patch to generate a reverse index). There are a couple of approaches to improve cold cache performance not pursued here:

  - We could include the object offsets in the reverse index format.
    Predictably, this does result in fewer page faults, but it triples
    the size of the file, while simultaneously duplicating a ton of data
    already available in the .idx file. (This was the original way I
    implemented the format, and it did show
    `--batch-check='%(objectsize:disk)'` winning out against `--batch`.)

    On the other hand, this increase in size also results in a large
    block-cache footprint, which could potentially hurt other workloads.

  - We could store the mapping from pack to index position in more
    cache-friendly way, like constructing a binary search tree from the
    table and writing the values in breadth-first order. This would
    result in much better locality, but the price you pay is trading
    O(1) lookup in 'pack_pos_to_index()' for an O(log n) one (since you
    can no longer directly index the table).

So, neither of these approaches are taken here. (Thankfully, the format is versioned, so we are free to pursue these in the future.) But, cold cache performance likely isn't interesting outside of one-off cases like asking for the size of an object directly. In real-world usage, Git is often performing many operations in the revindex (i.e., asking about many objects rather than a single one).

The trade-off is worth it, since we will avoid the vast majority of the cost of generating the revindex that the extra pointer chase will look like noise in the following patch's benchmarks.

This patch describes the format and prepares callers (like in pack-revindex.c) to be able to read *.rev files once they exist. An implementation of the writer will appear in the next patch, and callers will gradually begin to start using the writer in the patches that follow after that.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/technical/pack-format.txt |  20 ++++
 builtin/repack.c                        |   1 +
 object-store.h                          |   3 +
 pack-revindex.c                         | 144 ++++++++++++++++++++++--
 pack-revindex.h                         |  10 +-
 packfile.c                              |  13 ++-
 packfile.h                              |   1 +
 tmp-objdir.c                            |   6 +-
 8 files changed, 184 insertions(+), 14 deletions(-)

On Mon, Jan 25, 2021 at 06:37:14PM -0500, Taylor Blau wrote:

I guess this technique was pulled from the .idx code paths, but IMHO we should avoid this kind of struct-casting. It relies on the compiler's struct packing, and I'm not 100% sure it doesn't violate some weird pointer-aliasing rules.

OTOH, as long as we do not ever care about sizeof(revindex_header), this is likely to work in practice, since every field is at least 4-byte aligned (but there is probably an extra 4 bytes of padding at the end).

The "right" way is probably something like:

  const char *header = data;
  if (get_be32(header) != RIDX_SIGNATURE)
          error...;
  header += 4;
  if (get_be32(header) != 1)
          error...;
  header += 4;
  ...etc...

I thought we had helpers to read and advance the pointer, but it looks like those are specific to the bitmap code (e.g., read_be32(), though it uses a separate offset variable).

I dunno. Maybe I am being overly picky. The .idx code already does it like this, and I believe the index (as in .git/index) does, too. We have run into problems (as in b5007211b6 (pack-bitmap: do not use gcc packed attribute, 2014-11-27)), but that was due to a more odd-sized struct, as well as using sizeof().

The rest of the patch looks good to me.

-Peff

On Thu, Jan 28, 2021 at 07:27:09PM -0500, Jeff King wrote:

Yeah, that's exactly where it came from. I briefly wondered about this myself, but decided not to worry since (a) it closely follows an existing pattern and (b) no compiler should ever pad anywhere but the end of this struct since all other fields are aligned without padding.

Makes sense.

How about a set of follow-up patches to address all of these spots at the same time? That would allow us to move forward here (which is safe to do, as you note), and address all of these instances together uniformly.

Sound good?

Thanks, Taylor

On Thu, Jan 28, 2021 at 08:14:41PM -0500, Taylor Blau wrote:

That sounds fine to me. TBH, I am probably OK if that cleanup never happens, as long as nobody finds that it is a problem on there platform.

I do wonder if we should provide more guidance about what is OK and what is not in CodingGuidelines, but I have a feeling it would end up to esoteric to be generally useful.

-Peff

Add a new option that unconditionally enables the pack.writeReverseIndex setting in order to run the whole test suite in a mode that generates on-disk reverse indexes. Additionally, enable this mode in the second run of tests under linux-gcc in 'ci/run-build-and-tests.sh'.

Once on-disk reverse indexes are proven out over several releases, we can change the default value of that configuration to 'true', and drop this patch.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/index-pack.c      | 5 ++++-
 builtin/pack-objects.c    | 2 ++
 ci/run-build-and-tests.sh | 1 +
 pack-revindex.h           | 3 +++
 t/README                  | 3 +++
 5 files changed, 13 insertions(+), 1 deletion(-)

On Mon, Jan 25, 2021 at 06:37:42PM -0500, Taylor Blau wrote:

Sounds like a good plan.

Funny stray whitespace.

-Peff

In the next patch, we'll add support for unconditionally enabling the 'pack.writeReverseIndex' setting with a new GIT_TEST_WRITE_REV_INDEX environment variable.

This causes a little bit of fallout with tests that, for example, compare the list of files in the pack directory being unprepared to see .rev files in its output.

Those locations can be cleaned up to look for specific file extensions, rather than take everything in the pack directory (for instance) and then grep out unwanted items.

Once the pack.writeReverseIndex option has been thoroughly tested, we will default it to 'true', removing GIT_TEST_WRITE_REV_INDEX, and making it possible to revert this patch.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5319-multi-pack-index.sh |  5 +++--
 t/t5325-reverse-index.sh    |  4 ++++
 t/t5604-clone-reference.sh  |  2 +-
 t/t5702-protocol-v2.sh      | 12 ++++++++----
 t/t6500-gc.sh               |  6 +++---
 t/t9300-fast-import.sh      |  5 ++++-
 6 files changed, 23 insertions(+), 11 deletions(-)

On Mon, Jan 25, 2021 at 06:37:38PM -0500, Taylor Blau wrote:

I find the post-image here more readable than the original. It probably runs faster, too (zero processes instead of three).

I think we had a discussion a while ago about sane_unset outside of an &&-chain, where it does nothing that regular "unset" would not. But I don't know if we reached any kind of conclusion. I actually argued that it was fine in:

  https://lore.kernel.org/git/20200630185536.GA1888406@coredump.intra.peff.net/

So I guess I should probably stand by that. ;)

This one is less readable than before. :) I'm not sure how to really improve that, though.

Hmm. Too bad we can't rely on shell brace expansion, as:

  ls http_child/.git/objects/pack/*.{pack,idx}

would be more readable. You could still do it in a single "ls" by writing out both arguments manually, but it's probably not that important.

Likewise. But...

This one is making the test a bit looser (it would miss a case where we somehow failed to generate the .idx). That seems like an unlikely bug, but I wonder if we can keep the original behavior. I guess:

  ls .git/objects/pack/*.pack \
     .git/objects/pack/*.idx |
     sort >post_packs

would work?

Another case where I don't think we're losing anything (actually, we are gaining just slightly; if a bug somehow created 6 packs and 2 idx files, we'd now notice!).

-Peff

On Thu, Jan 28, 2021 at 7:49 PM Jeff King <peff@peff.net> wrote:

I recall that discussion. The fact that sane_unset() outside of a test caused a hiccup in your reading of the patch which led you to dig through the mail archive and spend time writing about it in your review could be interpreted as yet another argument against its use outside of tests (specifically, it wastes reviewer time). Of course, it's such a minor thing, though, not at all worth a re-roll.

On Thu, Jan 28, 2021 at 07:45:37PM -0500, Jeff King wrote:

I think I probably took this from the trace2 tests? Not sure. I'm glad that it's not wrong, strictly speaking.

This is another instance that I'd be happy to send a follow-up patch to get rid of all of these at once, unless you feel strongly that it should be changed in this series before applying.

Yeah, this follows from a suggestion that Ævar gave in:

  https://lore.kernel.org/git/878s8y5bdn.fsf@evledraar.gmail.com/

FWIW, I found that his suggestion was *clearer* than what was in v2. But I get that others may feel differently, too.

Agreed on all of that.

Sure, I see what you're saying. To be honest, I'm skeptical that we'd have a bug which failed only this one test, so I'm hesitant to send a replacement/reroll for this alone.

If you feel strongly, though, I'm happy to change it. (But, I'll err on the side of leaving it as-is, since you indicated in your response to v3's cover letter that you'd be OK if I discarded some or all of your suggestions).

Yay!

Thanks, Taylor

On Thu, Jan 28, 2021 at 08:21:50PM -0500, Taylor Blau wrote:

Nope, I don't feel strongly.

Nope, I don't feel strongly. Junio even argued elsewhere that these tests may be better off just looking for pack files (which is looser than what they do now, but as we've said, unlikely to matter for any realistic bug). So I'm happy enough with what you have.

-Peff

Jeff King <peff@peff.net> writes:

This part looks a bit familiar as I had to fix the interaction with Jonathan's topic, IIRC. We need to update the comment. It is not ensuring "exact 6"---it merely is interested in having three pack/idx pair, and carefully expressing that by preparing for the presence of other cruft in objects/pack/ directory other people may create (like ".rev", but we may gain more).

I wonder if we even _care_ about .idx. Why not just count .pack, to prepare for a possible distant future where we do not even write .idx but append to existing multi-pack-index as we download a new pack stream and store it in a .pack, or something?

I guess we are looking at the same issue from opposite angle. I suspect that it might even be a good thing to only care about .pack and ignore everything else in the longer run.

Now that we have an implementation that can write the new reverse index format, enable writing a .rev file in 'git pack-objects' by consulting the pack.writeReverseIndex configuration variable.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c   |  7 +++++++
 t/t5325-reverse-index.sh | 13 +++++++++++++
 2 files changed, 20 insertions(+)

When an on-disk reverse index exists, there is no need to generate one in memory. In fact, doing so can be slow, and require large amounts of the heap.

Let's make sure that we treat the on-disk reverse index with precedence (i.e., that when it exists, we don't bother trying to generate an equivalent one in memory) by teaching Git how to conditionally die() when generating a reverse index in memory.

Then, add a test to ensure that when (a) an on-disk reverse index exists, and (b) when setting GIT_TEST_REV_INDEX_DIE_IN_MEMORY, that we do not die, implying that we read from the on-disk one.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-revindex.c          | 4 ++++
 pack-revindex.h          | 1 +
 t/t5325-reverse-index.sh | 9 +++++++++
 3 files changed, 14 insertions(+)

On Mon, Jan 25, 2021 at 06:37:46PM -0500, Taylor Blau wrote:

I don't love this kind of hackery, as it will have to live forever if we want to keep testing this feature. But I also don't know how else to tell in the regular test suite that we are avoiding the slow path.

Would it be enough to instead add a t/perf test which checks the speed of:

  echo HEAD | git cat-file --batch-check='%(objectsize:disk)'

? I hate relying on the perf suite, because it gets run way less often (and requires a lot of squinting to interpret the results). But it wouldn't require any extra code the binary, as it's observing the actual user-visible thing we care about: speed.

(I guess we care as much or more about peak heap usage, but measuring that is a whole other can of worms).

-Peff

On Thu, Jan 28, 2021 at 07:53:34PM -0500, Jeff King wrote:

Yeah, I think that the thing we care most about is peak RSS, but I agree that I don't really want to wade into figuring out how to measure that reliably during test time (I think there is a separate and less relevant argument about whether that is something that we should be testing or not).

But, getting back to your original comment, I think that I actually prefer to have the GIT_TEST_XYZ_DIE stuff in the binary than I do relying on the perf suite to catch stuff like this.

I understand your concern about the binary size. I guess you could #ifdef this out and only build it in during the test suite, but then you're testing a different binary, and so that calls into question the integrity of the test suite itself, etc. etc.

So, I guess that's all to say that I while I do find this to be hack-y and gross, I don't think that it's all that bad when you compare it to the alternatives.

As usual, I'm happy to change it if you feel strongly that it should be changed.

Thanks, Taylor

On Thu, Jan 28, 2021 at 08:25:30PM -0500, Taylor Blau wrote:

I care less about binary size, and more just that the production binary people use day-to-day has a bunch of weird test-only behaviors baked into it. I guess nobody is likely to trigger this by accident, though, and anybody who can maliciously impact the environment can do a lot worse. So it's not the end of the world to keep. It just offends my sense of cleanliness and simplicity. ;)

I agree the alternatives are pretty lousy. I don't feel strongly enough to complain further. :)

-Peff

Right now, the test suite can be run with 'GIT_TEST_WRITE_REV_INDEX=1' in the environment, which causes all operations which write a pack to also write a .rev file.

To prepare for when that eventually becomes the default, we should continue to test the in-memory reverse index, too, in order to avoid losing existing coverage. Unfortuantely, explicit existing coverage is rather sparse, so only a basic test is added.

The new test is parameterized over whether or not the .rev file should be written, and is run in both modes by t5325 (without having to touch GIT_TEST_WRITE_REV_INDEX).

Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5325-reverse-index.sh | 45 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

On Mon, Jan 25, 2021 at 06:37:51PM -0500, Taylor Blau wrote:

Thanks, I think this is worth having.

These sizes aren't really guaranteed to be stable. I think you've eliminated most variables by not having the opportunity for deltas, though we're still subject to the whims of zlib, for example.

I think what we care about most is just that the on-disk and fallback cases generate the same results. If they do, we can assume those results are probably sane. If they're not, then a lot of _other_ stuff is going to be broken (like, say, pack-objects, which is writing out N bytes based on the sizes claimed by the revindex).

What do you think about just doing this:

  ...setup some commits... &&
  git rev-list --objects --no-object-names --all >objects &&

  git -c pack.writeReverseIndex=false repack -ad &&
  test_path_is_missing .git/objects/pack/*.rev &&
  git cat-file --batch-check="%(objectsize:disk) %(objectname)" \
          <objects >in-core &&

  git -c pack.writeReverseIndex=true repack -ad &&
  test_path_is_file .git/objects/pack/*.rev &&
  git cat-file --batch-check="%(objectsize:disk) %(objectname)" \
          <objects >on-disk &&

  test_cmp on-disk in-core

Are we autotools now? :) I think we can assume that on_disk contains something sensible. Perhaps even:

  git config pack.writeReverseIndex $on_disk

though if you take my advice above, all of this goes away.

-Peff

On Mon, Jan 25, 2021 at 06:37:51PM -0500, Taylor Blau wrote:

Oh, I forgot to mention: if re-rolling, s/fortuan/fortuna/.

-Peff

On Thu, Jan 28, 2021 at 08:05:41PM -0500, Jeff King wrote:

I do like your suggestion quite a lot: it gets rid of some ugliness, while making the overall test structure simpler. Here's a replacement for the final series.

Junio: when queuing, please apply this one instead of the original v3
10/10.

Thanks, Taylor

--- >8 ---

Subject: [PATCH] t5325: check both on-disk and in-memory reverse index

Right now, the test suite can be run with 'GIT_TEST_WRITE_REV_INDEX=1' in the environment, which causes all operations which write a pack to also write a .rev file.

To prepare for when that eventually becomes the default, we should continue to test the in-memory reverse index, too, in order to avoid losing existing coverage. Unfortunately, explicit existing coverage is rather sparse, so only a basic test is added that compares the result of

    git rev-list --objects --no-object-names --all |
    git cat-file --batch-check='%(objectsize:disk) %(objectname)'

with and without an on-disk reverse index.

Suggested-by: Jeff King <peff@peff.net>
Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 t/t5325-reverse-index.sh | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

On Thu, Jan 28, 2021 at 08:32:02PM -0500, Taylor Blau wrote:

Thanks, this looks good to me.

-Peff

Now that the pack.writeReverseIndex configuration is respected in both 'git index-pack' and 'git pack-objects' (and therefore, all of their callers), we can safely advertise it for use in the git-config manual.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/config/pack.txt | 7 +++++++
 1 file changed, 7 insertions(+)

On Mon, Jan 25, 2021 at 06:37:34PM -0500, Taylor Blau wrote:

We may want to teach fast-import about this, too, but I think it's OK to draw the line here for now (it's already reasonably well known that the generated packs aren't amazing and benefit from repacking).

-Peff

On Thu, Jan 28, 2021 at 07:30:56PM -0500, Jeff King wrote:

Maybe this was worth explaining in the documentation, but this choice was intentional. I'm not aware of any use-case that keeps the packs generated by fast-import around for very long (i.e., I'd expect any 'git fast-import' to be pretty quickly followed by a 'git repack -ad'), so I don't think we'd want to spend time generating a reverse index for a pack structure that we're about to immediately discard.

Thanks, Taylor

On Thu, Jan 28, 2021 at 08:17:40PM -0500, Taylor Blau wrote:

One case where I imagine they are kept is in remote-helpers that use the import/export mechanism (e.g., something interacting with remote-hg). I suspect people there just live with the somewhat lousy packs, and then perhaps occasionally "git repack -adf". That would give them .rev files then, too.

But as I said, I think it's OK to ignore this for now. If somebody with an interest in fast-import wants to add support later, they can.

-Peff

This patch prepares for callers to be able to write reverse index files to disk.

It adds the necessary machinery to write a format-compliant .rev file from within 'write_rev_file()', which is called from 'finish_tmp_packfile()'.

Similar to the process by which the reverse index is computed in memory, these new paths also have to sort a list of objects by their offsets within a packfile. These new paths use a qsort() (as opposed to a radix sort), since our specialized radix sort requires a full revindex_entry struct per object, which is more memory than we need to allocate.

The qsort is obviously slower, but the theoretical slowdown would require a repository with a large amount of objects, likely implying that the time spent in, say, pack-objects during a repack would dominate the overall runtime.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-write.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 pack.h       |   4 ++
 2 files changed, 123 insertions(+), 1 deletion(-)

Teach 'git index-pack' to optionally write and verify reverse index with '--[no-]rev-index', as well as respecting the 'pack.writeReverseIndex' configuration option.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 Documentation/git-index-pack.txt | 18 +++++---
 builtin/index-pack.c             | 50 ++++++++++++++++++++--
 t/t5325-reverse-index.sh         | 71 ++++++++++++++++++++++++++++++++
 3 files changed, 131 insertions(+), 8 deletions(-)
 create mode 100755 t/t5325-reverse-index.sh

To derive the filename for a .idx file, 'git index-pack' uses derive_filename() to strip the '.pack' suffix and add the new suffix.

Prepare for stripping off suffixes other than '.pack' by making the suffix to strip a parameter of derive_filename(). In order to make this consistent with the "suffix" parameter which does not begin with a ".", an additional check in derive_filename.

Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/index-pack.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

On Mon, Jan 25, 2021 at 06:37:22PM -0500, Taylor Blau wrote:

Maybe "add" missing from the final line?

Looks good to me.

-Peff

On Thu, Jan 28, 2021 at 07:28:32PM -0500, Jeff King wrote:

Oops, yeah. I'm happy to send a replacement to help with queuing, if the maintainer thinks that would be helpful.

Thanks, Taylor

Taylor Blau <me@ttaylorr.com> writes:

Ehh, does that mean you are OK to see the remainder of 'next' to take this topic hostage?

Unless you use some new features that came from other topics in 'next', I'd discourage such a rebasing. If the API topic gained some fix-up patches on top since it was merged to 'next', it is perfectly sensible to rebase this series on top of the updated API topic---it does not change the fact that this topic is dependent on the API topic.

As it happens that the API topic is now in 'master', none of the above complaint should actually apply, even if this new round of patches do not cleanly apply to the tip of the API topic, as long as they apply cleanly to tonight's 'master'. It will make the topic ineligible to be merged later to 'maint', but this is a new feature, so nothing is lost.

So, I'll try to apply them first on top of the tip of the API topic, which is at 779412b9 (for_each_object_in_pack(): clarify pack vs index ordering, 2021-01-14), and if I do not feel like spending time to resolve conflicts, I'll then try to apply them on top of tonight's master. We'll see what happens.

Thanks.

On Mon, Jan 25, 2021 at 06:36:43PM -0800, Junio C Hamano wrote:

Ah; my apologies. I thought that rebasing onto next would make it easier for you to merge this topic, but after reading what you wrote I can see that's not the case.

The only dependency that this topic should have is on the API one, which I am glad to see in 'master'.

I'm happy to send another version based on 'master', but I expect that this should apply cleanly either way.

Thanks, Taylor

On Mon, Jan 25, 2021 at 06:37:09PM -0500, Taylor Blau wrote:

Thanks, these all seemed like improvements to me. I hadn't read carefully through the test patches yet, so I did so now (in addition to checking out the changes in the earlier patches).

My comments range between "musings" and "suggestions". I wouldn't be too torn up if they are all discarded and this applies as-is, but in aggregate there may be enough to merit one more re-roll.

-Peff

On Thu, Jan 28, 2021 at 08:06:11PM -0500, Jeff King wrote:

Thank you; I appreciate your close review :-).

Thanks again. I discarded a fair amount of them, which I hope you don't mind. I think a few of them could be reasonably dealt with outside of this series. Mostly because they have implications on other parts of the codebase. So I'd like to deal with them all at once, but without adding to the scope of this series.

I did especially like your final suggestion about the new test in t5325, so I sent a replacement patch that takes that suggestion (as well as the typofix that you pointed out).

Unless you have any objections, I think that this is ready to get picked up.

Thanks, Taylor