From: Taylor Blau <hidden> Date: 2021-03-03 06:41:56
On Mon, Mar 01, 2021 at 08:17:53PM -0800, Jonathan Tan wrote:
I was initially confused that "preferred" was set twice, but this makes
sense - the first one is when an existing midx is reused, and the second
one is for objects in packs that the midx (if it exists) does not cover.
Yep. Those two paths permeate a lot of the MIDX writer code, since it
wants to reuse work from an existing MIDX if it can find one.
quoted
@@ -828,7 +869,19 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index * if (ctx.m && ctx.nr == ctx.m->num_packs && !packs_to_drop) goto cleanup;- ctx.entries = get_sorted_entries(ctx.m, ctx.info, ctx.nr, &ctx.entries_nr);+ if (preferred_pack_name) {+ for (i = 0; i < ctx.nr; i++) {+ if (!cmp_idx_or_pack_name(preferred_pack_name,+ ctx.info[i].pack_name)) {+ ctx.preferred_pack_idx = i;+ break;+ }+ }+ } else+ ctx.preferred_pack_idx = -1;
Looks safer to put "ctx.preferred_pack_idx = -1" before the "if", just
in case the given pack name does not exist?
I couldn't figure out why the preferred pack index needs to be
recalculated here, since the pack entries would have already been
sorted. Also, the tests still pass when I comment this part out. A
comment describing what's going on would be helpful.
Funny you mention that; I was wondering the same thing myself the other
day when reading these patches again before deploying them to a couple
of testing repositories at GitHub.
It is totally unnecessary: since we have already marked objects from the
preferred pack in get_sorted_entries(), the rest of the code doesn't
care if the preferred pack was permuted or not.
But we *do* care if the pack which was preferred expired. The 'git
repack --geometric --write-midx' caller (which will appear in a later
series) should never do that, so emitting a warning() is worthwhile. I
think ultimately you want something like this squashed in:
Any reason why we're using 2 separate "if" statements?
Other than that, this patch and patch 14 look good. Besides all my minor
comments, I think the overall patch set is in good shape and ready to be
merged. It's great that we could reuse some of the individual-pack reverse
index concepts and code too.
From: Taylor Blau <hidden> Date: 2021-03-03 06:41:57
On Mon, Mar 01, 2021 at 08:21:11PM -0800, Jonathan Tan wrote:
quoted
+== multi-pack-index reverse indexes
+
+Similar to the pack-based reverse index, the multi-pack index can also
+be used to generate a reverse index.
+
+Instead of mapping between offset, pack-, and index position, this
+reverse index maps between an object's position within the MIDX, and
+that object's position within a pseudo-pack that the MIDX describes.
+
+To clarify these three orderings
The paragraph seems to only describe 2 orderings - object's position
within the MIDX and object's position within the pseudo-pack. (Is the
third one the offset within the MIDX - which is, I believe, trivially
computable from the position within the MIDX?)
Sorry for the confusion. I was trying to distinguish between ordering
based on object offset, pack position, and index position.
I guess you could count that as 2, 3, or 4 different orderings (if you
classify "pack vs MIDX", "offset vs pack pos vs index pos" or the last
three plus "vs MIDX pos").
But I think that all of that is needlessly confusing, so I'd much rather
just say "To clarify the difference between these orderings".
Also, which are stored in the .rev file?
The paragraph above describes it a little bit "this reverse index maps
between ...", but I think it could be made clearer. (I was intentionally
brief there since I wanted to not get too far into the details before
explaining the relevant concepts, but I think I went too far).
How does this sound?
@@ -387,12 +387,15 @@ be used to generate a reverse index. Instead of mapping between offset, pack-, and index position, this reverse index maps between an object's position within the MIDX, and-that object's position within a pseudo-pack that the MIDX describes.+that object's position within a pseudo-pack that the MIDX describes+(i.e., the ith entry of the multi-pack reverse index holds the MIDX+position of ith object in pseudo-pack order).-To clarify these three orderings, consider a multi-pack reachability-bitmap (which does not yet exist, but is what we are building towards-here). Each bit needs to correspond to an object in the MIDX, and so we-need an efficient mapping from bit position to MIDX position.+To clarify the difference between these orderings, consider a multi-pack+reachability bitmap (which does not yet exist, but is what we are+building towards here). Each bit needs to correspond to an object in the+MIDX, and so we need an efficient mapping from bit position to MIDX+position. One solution is to let bits occupy the same position in the oid-sorted index stored by the MIDX. But because oids are effectively random, there
I think this way of writing is vulnerable to confusing errors if a
missing or extra backslash happens, so I would prefer the #define to be
outside the variable declaration.
Yeah, I can't say that I disagree with you. Of course, having the
#define's outside of the declaration makes the whole thing a little more
verbose, which isn't a huge deal.
But I was mirroring what Ævar was doing in the sub-thread he started at:
https://public-inbox.org/git/20210215184118.11306-1-avarab@gmail.com/
Unless you feel strongly, I think that what we have isn't so bad here.
quoted
+static int cmd_multi_pack_index_repack(int argc, const char **argv)
+{
+ struct option *options;
+ static struct option builtin_multi_pack_index_repack_options[] = {
OPT_MAGNITUDE(0, "batch-size", &opts.batch_size,
N_("during repack, collect pack-files of smaller size into a batch that is larger than this size")),
OPT_END(),
};
+ options = parse_options_dup(builtin_multi_pack_index_repack_options);
+ options = add_common_options(options);
I looked for where this was freed, but I guess freeing this struct is
not really something we're worried about (which makes sense).
From: Taylor Blau <hidden> Date: 2021-03-04 00:23:31
On Tue, Mar 02, 2021 at 10:36:20AM -0800, Jonathan Tan wrote:
quoted
midx_to_pack_pos() is the trickiest, since it needs to find an object's
position in the psuedo-pack order, but that order can only be recovered
in the .rev file itself. This mapping can be implemented with a binary
search, but note that the thing we're binary searching over isn't an
array, but rather a _permutation_.
So, when comparing two items, it's helpful to keep in mind the
difference. Instead of a traditional binary search, where you are
comparing two things directly, here we're comparing a (pack, offset)
tuple with an index into the multi-pack index. That index describes
another (pack, offset) tuple, and it is _those_ two tuples that are
compared.
Well, the binary search is indeed over an array :-)
:-). This might be more clearer as:
...isn't an array of values, but rather a permuted order of those values.
Any reason why we're using 2 separate "if" statements?
Yeah. This first if statement will turn into:
if (flags & (MIDX_WRITE_REV_INDEX | MIDX_WRITE_BITMAP))
so that the pack order is computed in either case (since both the
existing write_midx_reverse_index() and the eventual write_midx_bitmap()
will be able to use the pack order).
Arguably there is never a practical reason to write one without the
other (and writing a MIDX bitmap without a reverse index is a bug), so
perhaps these options should be consolidated.
But that's cleanup that I'd rather do after all of this has settled
(since it'd be weird to say: "here's the option to write bitmaps, except
we can't write multi-pack bitmaps yet, but setting it actually writes
this other thing").
Other than that, this patch and patch 14 look good. Besides all my minor
comments, I think the overall patch set is in good shape and ready to be
merged. It's great that we could reuse some of the individual-pack reverse
index concepts and code too.
Thanks, I am really glad that you had a chance to take a look at it. I
always find your review quite helpful.
Thanks,
Taylor
I think this way of writing is vulnerable to confusing errors if a
missing or extra backslash happens, so I would prefer the #define to be
outside the variable declaration.
Yeah, I can't say that I disagree with you. Of course, having the
#define's outside of the declaration makes the whole thing a little more
verbose, which isn't a huge deal.
I think it's the same verbosity - you just need to move the lines?
From: Jonathan Tan <hidden> Date: 2021-03-04 02:02:06
Funny you mention that; I was wondering the same thing myself the other
day when reading these patches again before deploying them to a couple
of testing repositories at GitHub.
It is totally unnecessary: since we have already marked objects from the
preferred pack in get_sorted_entries(), the rest of the code doesn't
care if the preferred pack was permuted or not.
But we *do* care if the pack which was preferred expired. The 'git
repack --geometric --write-midx' caller (which will appear in a later
series) should never do that, so emitting a warning() is worthwhile.
Ah, this makes sense.
quoted hunk
I
think ultimately you want something like this squashed in:
Any reason why we're using 2 separate "if" statements?
Yeah. This first if statement will turn into:
if (flags & (MIDX_WRITE_REV_INDEX | MIDX_WRITE_BITMAP))
so that the pack order is computed in either case (since both the
existing write_midx_reverse_index() and the eventual write_midx_bitmap()
will be able to use the pack order).
Ah, OK. That's what I was thinking of, but nice to have confirmation.
Maybe write in the commit message that these are separated because in
the future, one of the conditions will change.
@@ -387,12 +387,15 @@ be used to generate a reverse index. Instead of mapping between offset, pack-, and index position, this reverse index maps between an object's position within the MIDX, and-that object's position within a pseudo-pack that the MIDX describes.+that object's position within a pseudo-pack that the MIDX describes+(i.e., the ith entry of the multi-pack reverse index holds the MIDX+position of ith object in pseudo-pack order).-To clarify these three orderings, consider a multi-pack reachability-bitmap (which does not yet exist, but is what we are building towards-here). Each bit needs to correspond to an object in the MIDX, and so we-need an efficient mapping from bit position to MIDX position.+To clarify the difference between these orderings, consider a multi-pack+reachability bitmap (which does not yet exist, but is what we are+building towards here). Each bit needs to correspond to an object in the+MIDX, and so we need an efficient mapping from bit position to MIDX+position. One solution is to let bits occupy the same position in the oid-sorted index stored by the MIDX. But because oids are effectively random, there
I think this way of writing is vulnerable to confusing errors if a
missing or extra backslash happens, so I would prefer the #define to be
outside the variable declaration.
Yeah, I can't say that I disagree with you. Of course, having the
#define's outside of the declaration makes the whole thing a little more
verbose, which isn't a huge deal.
I think it's the same verbosity - you just need to move the lines?
Yeah, you're right. I'm being too subjective, and I don't really feel
strongly, either.
This was wrong in the original patch: ctx.preferred_pack is an integer,
and is set to -1 when no preferred pack was specified.
It's certainly unlikely that we'd have 2^31 packs, but silently
converting a signed type to an unsigned one is misleading.
From: Taylor Blau <hidden> Date: 2021-03-04 03:08:13
On Wed, Mar 03, 2021 at 06:04:44PM -0800, Jonathan Tan wrote:
quoted
quoted
Any reason why we're using 2 separate "if" statements?
Yeah. This first if statement will turn into:
if (flags & (MIDX_WRITE_REV_INDEX | MIDX_WRITE_BITMAP))
so that the pack order is computed in either case (since both the
existing write_midx_reverse_index() and the eventual write_midx_bitmap()
will be able to use the pack order).
Ah, OK. That's what I was thinking of, but nice to have confirmation.
Maybe write in the commit message that these are separated because in
the future, one of the conditions will change.
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:20
Now that there is a shared 'flags' member in the options structure,
there is no need to keep track of whether to force progress or not,
since ultimately the decision of whether or not to show a progress meter
is controlled by a bit in the flags member.
Manipulate that bit directly, and drop the now-unnecessary 'progress'
field while we're at it.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 8 +++-----
1 file changed, 3 insertions(+), 5 deletions(-)
@@ -23,7 +22,7 @@ int cmd_multi_pack_index(int argc, const char **argv,staticstructoptionbuiltin_multi_pack_index_options[]={OPT_FILENAME(0,"object-dir",&opts.object_dir,N_("object directory containing set of packfile and pack-index pairs")),-OPT_BOOL(0,"progress",&opts.progress,N_("force progress reporting")),+OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),OPT_MAGNITUDE(0,"batch-size",&opts.batch_size,N_("during repack, collect pack-files of smaller size into a batch that is larger than this size")),OPT_END(),
@@ -31,15 +30,14 @@ int cmd_multi_pack_index(int argc, const char **argv,git_config(git_default_config,NULL);-opts.progress=isatty(2);+if(isatty(2))+opts.flags|=MIDX_PROGRESS;argc=parse_options(argc,argv,prefix,builtin_multi_pack_index_options,builtin_multi_pack_index_usage,0);if(!opts.object_dir)opts.object_dir=get_object_directory();-if(opts.progress)-opts.flags|=MIDX_PROGRESS;if(argc==0)usage_with_options(builtin_multi_pack_index_usage,
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:20
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps. The previous version
was based on 'ds/chunked-file-api', but that topic has since been merged
to 'master'. This series is now built directly on top of 'master'.
Not much has changed since last time. Jonathan Tan reviewed the previous
version, and I incorporated feedback from his review:
- The usage macros in builtin/multi-pack-index.c were pulled out and
defined separately.
- Some sloppiness with converting a signed index referring to the
preferred pack into an unsigned value was cleaned up.
- Documentation clean-up, particularly in patches 12 and 13.
There are a couple of new things that we found while testing this out at
GitHub.
- We now call finalize_object_file() on the multi-pack reverse index
to set the correct permissions.
- Patch 14 removed a stray hunk that introduced a memory leak.
- Patch 16 (courtesy of Peff) is new. It improves the cache locality
of midx_pack_order_cmp(), which has a substantial impact on
repositories with many objects.
Thanks in advance for your review.
Jeff King (1):
midx.c: improve cache locality in midx_pack_order_cmp()
Taylor Blau (15):
builtin/multi-pack-index.c: inline 'flags' with options
builtin/multi-pack-index.c: don't handle 'progress' separately
builtin/multi-pack-index.c: define common usage with a macro
builtin/multi-pack-index.c: split sub-commands
builtin/multi-pack-index.c: don't enter bogus cmd_mode
builtin/multi-pack-index.c: display usage on unrecognized command
t/helper/test-read-midx.c: add '--show-objects'
midx: allow marking a pack as preferred
midx: don't free midx_name early
midx: keep track of the checksum
midx: make some functions non-static
Documentation/technical: describe multi-pack reverse indexes
pack-revindex: read multi-pack reverse indexes
pack-write.c: extract 'write_rev_file_order'
pack-revindex: write multi-pack reverse indexes
Documentation/git-multi-pack-index.txt | 14 +-
Documentation/technical/multi-pack-index.txt | 5 +-
Documentation/technical/pack-format.txt | 83 +++++++
builtin/multi-pack-index.c | 182 ++++++++++++---
builtin/repack.c | 2 +-
midx.c | 229 +++++++++++++++++--
midx.h | 11 +-
pack-revindex.c | 127 ++++++++++
pack-revindex.h | 53 +++++
pack-write.c | 36 ++-
pack.h | 1 +
packfile.c | 3 +
t/helper/test-read-midx.c | 24 +-
t/t5319-multi-pack-index.sh | 39 ++++
14 files changed, 740 insertions(+), 69 deletions(-)
Range-diff against v2:
1: 0527fa89a9 = 1: 43fc0ad276 builtin/multi-pack-index.c: inline 'flags' with options
2: a4e107b1f8 = 2: 181f11e4c5 builtin/multi-pack-index.c: don't handle 'progress' separately
3: 8679dfd212 = 3: 94c498f0e2 builtin/multi-pack-index.c: define common usage with a macro
4: bc42b56ea2 ! 4: d084f90466 builtin/multi-pack-index.c: split sub-commands
@@ Commit message
## builtin/multi-pack-index.c ##
@@
- #include "midx.h"
- #include "trace2.h"
+ #define BUILTIN_MIDX_REPACK_USAGE \
+ N_("git multi-pack-index [<options>] repack [--batch-size=<size>]")
+static char const * const builtin_multi_pack_index_write_usage[] = {
- #define BUILTIN_MIDX_WRITE_USAGE \
- N_("git multi-pack-index [<options>] write")
+ BUILTIN_MIDX_WRITE_USAGE,
+ NULL
+};
-
+static char const * const builtin_multi_pack_index_verify_usage[] = {
- #define BUILTIN_MIDX_VERIFY_USAGE \
- N_("git multi-pack-index [<options>] verify")
+ BUILTIN_MIDX_VERIFY_USAGE,
+ NULL
+};
-
+static char const * const builtin_multi_pack_index_expire_usage[] = {
- #define BUILTIN_MIDX_EXPIRE_USAGE \
- N_("git multi-pack-index [<options>] expire")
+ BUILTIN_MIDX_EXPIRE_USAGE,
+ NULL
+};
-
+static char const * const builtin_multi_pack_index_repack_usage[] = {
- #define BUILTIN_MIDX_REPACK_USAGE \
- N_("git multi-pack-index [<options>] repack [--batch-size=<size>]")
+ BUILTIN_MIDX_REPACK_USAGE,
+ NULL
+};
-
static char const * const builtin_multi_pack_index_usage[] = {
BUILTIN_MIDX_WRITE_USAGE,
+ BUILTIN_MIDX_VERIFY_USAGE,
@@ builtin/multi-pack-index.c: static struct opts_multi_pack_index {
unsigned flags;
} opts;
5: 5daa2946d3 = 5: bc3b6837f2 builtin/multi-pack-index.c: don't enter bogus cmd_mode
6: 98d9ea0770 = 6: f117e442c3 builtin/multi-pack-index.c: display usage on unrecognized command
7: 2fd9f4debf = 7: ae85a68ef2 t/helper/test-read-midx.c: add '--show-objects'
8: 223b899094 ! 8: 30194a6786 midx: allow marking a pack as preferred
@@ builtin/multi-pack-index.c
#include "trace2.h"
+#include "object-store.h"
- static char const * const builtin_multi_pack_index_write_usage[] = {
#define BUILTIN_MIDX_WRITE_USAGE \
- N_("git multi-pack-index [<options>] write")
+ N_("git multi-pack-index [<options>] write [--preferred-pack=<pack>]")
- BUILTIN_MIDX_WRITE_USAGE,
- NULL
- };
+
+ #define BUILTIN_MIDX_VERIFY_USAGE \
+ N_("git multi-pack-index [<options>] verify")
@@ builtin/multi-pack-index.c: static char const * const builtin_multi_pack_index_usage[] = {
static struct opts_multi_pack_index {
@@ midx.c: static void fill_pack_entry(uint32_t pack_int_id,
uint32_t nr_packs,
- uint32_t *nr_objects)
+ uint32_t *nr_objects,
-+ uint32_t preferred_pack)
++ int preferred_pack)
{
uint32_t cur_fanout, cur_pack, cur_object;
uint32_t alloc_fanout, alloc_objects, total_objects = 0;
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
goto cleanup;
- ctx.entries = get_sorted_entries(ctx.m, ctx.info, ctx.nr, &ctx.entries_nr);
++ ctx.preferred_pack_idx = -1;
+ if (preferred_pack_name) {
+ for (i = 0; i < ctx.nr; i++) {
+ if (!cmp_idx_or_pack_name(preferred_pack_name,
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
+ break;
+ }
+ }
-+ } else
-+ ctx.preferred_pack_idx = -1;
++ }
+
+ ctx.entries = get_sorted_entries(ctx.m, ctx.info, ctx.nr, &ctx.entries_nr,
+ ctx.preferred_pack_idx);
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
pack_name_concat_len += strlen(ctx.info[i].pack_name) + 1;
}
-+ /*
-+ * Recompute the preferred_pack_idx (if applicable) according to the
-+ * permuted pack order.
-+ */
-+ ctx.preferred_pack_idx = -1;
++ /* Check that the preferred pack wasn't expired (if given). */
+ if (preferred_pack_name) {
-+ ctx.preferred_pack_idx = lookup_idx_or_pack_name(ctx.info,
-+ ctx.nr,
-+ preferred_pack_name);
-+ if (ctx.preferred_pack_idx < 0)
++ int preferred_idx = lookup_idx_or_pack_name(ctx.info,
++ ctx.nr,
++ preferred_pack_name);
++ if (preferred_idx < 0)
+ warning(_("unknown preferred pack: '%s'"),
+ preferred_pack_name);
+ else {
-+ uint32_t orig = ctx.info[ctx.preferred_pack_idx].orig_pack_int_id;
++ uint32_t orig = ctx.info[preferred_idx].orig_pack_int_id;
+ uint32_t perm = ctx.pack_perm[orig];
+
-+ if (perm == PACK_EXPIRED) {
++ if (perm == PACK_EXPIRED)
+ warning(_("preferred pack '%s' is expired"),
+ preferred_pack_name);
-+ ctx.preferred_pack_idx = -1;
-+ } else
-+ ctx.preferred_pack_idx = perm;
+ }
+ }
+
9: 976848bc4b = 9: 5c5aca761a midx: don't free midx_name early
10: 5ed47f7e3a = 10: a22a1463a5 midx: keep track of the checksum
11: 0292508e12 = 11: efa54479b1 midx: make some functions non-static
12: 404d730498 ! 12: 4745bb8590 Documentation/technical: describe multi-pack reverse indexes
@@ Documentation/technical/pack-format.txt: CHUNK DATA:
+
+Instead of mapping between offset, pack-, and index position, this
+reverse index maps between an object's position within the MIDX, and
-+that object's position within a pseudo-pack that the MIDX describes.
++that object's position within a pseudo-pack that the MIDX describes
++(i.e., the ith entry of the multi-pack reverse index holds the MIDX
++position of ith object in pseudo-pack order).
+
-+To clarify these three orderings, consider a multi-pack reachability
-+bitmap (which does not yet exist, but is what we are building towards
-+here). Each bit needs to correspond to an object in the MIDX, and so we
-+need an efficient mapping from bit position to MIDX position.
++To clarify the difference between these orderings, consider a multi-pack
++reachability bitmap (which does not yet exist, but is what we are
++building towards here). Each bit needs to correspond to an object in the
++MIDX, and so we need an efficient mapping from bit position to MIDX
++position.
+
+One solution is to let bits occupy the same position in the oid-sorted
+index stored by the MIDX. But because oids are effectively random, there
13: d4e01a44e7 ! 13: a6ebd4be91 pack-revindex: read multi-pack reverse indexes
@@ Commit message
position in the psuedo-pack order, but that order can only be recovered
in the .rev file itself. This mapping can be implemented with a binary
search, but note that the thing we're binary searching over isn't an
- array, but rather a _permutation_.
+ array of values, but rather a permuted order of those values.
So, when comparing two items, it's helpful to keep in mind the
difference. Instead of a traditional binary search, where you are
14: ab7012b283 ! 14: f5314f1822 pack-write.c: extract 'write_rev_file_order'
@@ pack-write.c: const char *write_rev_file(const char *rev_name,
+ pack_order[i] = i;
+ QSORT_S(pack_order, nr_objects, pack_order_cmp, objects);
+
-+ if (!(flags & (WRITE_REV | WRITE_REV_VERIFY)))
-+ return NULL;
-+
+ ret = write_rev_file_order(rev_name, pack_order, nr_objects, hash,
+ flags);
+
15: 01bd6a35c6 ! 15: fa3acb5d5a pack-revindex: write multi-pack reverse indexes
@@ Commit message
for long, since subsequent patches will introduce the multi-pack bitmap,
which will begin passing this field.
+ (In midx.c:write_midx_internal(), the two adjacent if statements share a
+ conditional, but are written separately since the first one will
+ eventually also handle the MIDX_WRITE_BITMAP flag, which does not yet
+ exist.)
+
Signed-off-by: Taylor Blau [off-list ref]
## midx.c ##
@@ midx.c: static int write_midx_large_offsets(struct hashfile *f,
+ struct write_midx_context *ctx)
+{
+ struct strbuf buf = STRBUF_INIT;
++ const char *tmp_file;
+
+ strbuf_addf(&buf, "%s-%s.rev", midx_name, hash_to_hex(midx_hash));
+
-+ write_rev_file_order(buf.buf, ctx->pack_order, ctx->entries_nr,
-+ midx_hash, WRITE_REV);
++ tmp_file = write_rev_file_order(NULL, ctx->pack_order, ctx->entries_nr,
++ midx_hash, WRITE_REV);
++
++ if (finalize_object_file(tmp_file, buf.buf))
++ die(_("cannot store reverse index file"));
+
+ strbuf_release(&buf);
+}
-: ---------- > 16: 550e785f10 midx.c: improve cache locality in midx_pack_order_cmp()
--
2.30.0.667.g81c0cbc6fd
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:21
Subcommands of the 'git multi-pack-index' command (e.g., 'write',
'verify', etc.) will want to optionally change a set of shared flags
that are eventually passed to the MIDX libraries.
Right now, options and flags are handled separately. Inline them into
the same structure so that sub-commands can more easily share the
'flags' data.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 13 ++++++-------
1 file changed, 6 insertions(+), 7 deletions(-)
@@ -14,13 +14,12 @@ static struct opts_multi_pack_index {constchar*object_dir;unsignedlongbatch_size;intprogress;+unsignedflags;}opts;intcmd_multi_pack_index(intargc,constchar**argv,constchar*prefix){-unsignedflags=0;-staticstructoptionbuiltin_multi_pack_index_options[]={OPT_FILENAME(0,"object-dir",&opts.object_dir,N_("object directory containing set of packfile and pack-index pairs")),
@@ -40,7 +39,7 @@ int cmd_multi_pack_index(int argc, const char **argv,if(!opts.object_dir)opts.object_dir=get_object_directory();if(opts.progress)-flags|=MIDX_PROGRESS;+opts.flags|=MIDX_PROGRESS;if(argc==0)usage_with_options(builtin_multi_pack_index_usage,
@@ -55,16 +54,16 @@ int cmd_multi_pack_index(int argc, const char **argv,if(!strcmp(argv[0],"repack"))returnmidx_repack(the_repository,opts.object_dir,-(size_t)opts.batch_size,flags);+(size_t)opts.batch_size,opts.flags);if(opts.batch_size)die(_("--batch-size option is only for 'repack' subcommand"));if(!strcmp(argv[0],"write"))-returnwrite_midx_file(opts.object_dir,flags);+returnwrite_midx_file(opts.object_dir,opts.flags);if(!strcmp(argv[0],"verify"))-returnverify_midx_file(the_repository,opts.object_dir,flags);+returnverify_midx_file(the_repository,opts.object_dir,opts.flags);if(!strcmp(argv[0],"expire"))-returnexpire_midx_packs(the_repository,opts.object_dir,flags);+returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);die(_("unrecognized subcommand: %s"),argv[0]);}
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:53
Factor out the usage message into pieces corresponding to each mode.
This avoids options specific to one sub-command from being shared with
another in the usage.
A subsequent commit will use these #define macros to have usage
variables for each sub-command without duplicating their contents.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 17 ++++++++++++++++-
1 file changed, 16 insertions(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:53
Handle sub-commands of the 'git multi-pack-index' builtin (e.g.,
"write", "repack", etc.) separately from one another. This allows
sub-commands with unique options, without forcing cmd_multi_pack_index()
to reject invalid combinations itself.
This comes at the cost of some duplication and boilerplate. Luckily, the
duplication is reduced to a minimum, since common options are shared
among sub-commands due to a suggestion by Ævar. (Sub-commands do have to
retain the common options, too, since this builtin accepts common
options on either side of the sub-command).
Roughly speaking, cmd_multi_pack_index() parses options (including
common ones), and stops at the first non-option, which is the
sub-command. It then dispatches to the appropriate sub-command, which
parses the remaining options (also including common options).
Unknown options are kept by the sub-commands in order to detect their
presence (and complain that too many arguments were given).
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 131 ++++++++++++++++++++++++++++++-------
1 file changed, 106 insertions(+), 25 deletions(-)
@@ -31,25 +47,99 @@ static struct opts_multi_pack_index {unsignedflags;}opts;-intcmd_multi_pack_index(intargc,constchar**argv,-constchar*prefix)+staticstructoptioncommon_opts[]={+OPT_FILENAME(0,"object-dir",&opts.object_dir,+N_("object directory containing set of packfile and pack-index pairs")),+OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),+OPT_END(),+};++staticstructoption*add_common_options(structoption*prev){-staticstructoptionbuiltin_multi_pack_index_options[]={-OPT_FILENAME(0,"object-dir",&opts.object_dir,-N_("object directory containing set of packfile and pack-index pairs")),-OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),+structoption*with_common=parse_options_concat(common_opts,prev);+free(prev);+returnwith_common;+}++staticintcmd_multi_pack_index_write(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_write_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_write_usage,+options);++returnwrite_midx_file(opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_verify(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_verify_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_verify_usage,+options);++returnverify_midx_file(the_repository,opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_expire(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_expire_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_expire_usage,+options);++returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_repack(intargc,constchar**argv)+{+structoption*options;+staticstructoptionbuiltin_multi_pack_index_repack_options[]={OPT_MAGNITUDE(0,"batch-size",&opts.batch_size,N_("during repack, collect pack-files of smaller size into a batch that is larger than this size")),OPT_END(),};+options=parse_options_dup(builtin_multi_pack_index_repack_options);+options=add_common_options(options);++argc=parse_options(argc,argv,NULL,+options,+builtin_multi_pack_index_repack_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_repack_usage,+options);++returnmidx_repack(the_repository,opts.object_dir,+(size_t)opts.batch_size,opts.flags);+}++intcmd_multi_pack_index(intargc,constchar**argv,+constchar*prefix)+{+structoption*builtin_multi_pack_index_options=common_opts;+git_config(git_default_config,NULL);if(isatty(2))opts.flags|=MIDX_PROGRESS;argc=parse_options(argc,argv,prefix,builtin_multi_pack_index_options,-builtin_multi_pack_index_usage,0);+builtin_multi_pack_index_usage,+PARSE_OPT_STOP_AT_NON_OPTION);if(!opts.object_dir)opts.object_dir=get_object_directory();
@@ -58,25 +148,16 @@ int cmd_multi_pack_index(int argc, const char **argv,usage_with_options(builtin_multi_pack_index_usage,builtin_multi_pack_index_options);-if(argc>1){-die(_("too many arguments"));-return1;-}-trace2_cmd_mode(argv[0]);if(!strcmp(argv[0],"repack"))-returnmidx_repack(the_repository,opts.object_dir,-(size_t)opts.batch_size,opts.flags);-if(opts.batch_size)-die(_("--batch-size option is only for 'repack' subcommand"));--if(!strcmp(argv[0],"write"))-returnwrite_midx_file(opts.object_dir,opts.flags);-if(!strcmp(argv[0],"verify"))-returnverify_midx_file(the_repository,opts.object_dir,opts.flags);-if(!strcmp(argv[0],"expire"))-returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);--die(_("unrecognized subcommand: %s"),argv[0]);+returncmd_multi_pack_index_repack(argc,argv);+elseif(!strcmp(argv[0],"write"))+returncmd_multi_pack_index_write(argc,argv);+elseif(!strcmp(argv[0],"verify"))+returncmd_multi_pack_index_verify(argc,argv);+elseif(!strcmp(argv[0],"expire"))+returncmd_multi_pack_index_expire(argc,argv);+else+die(_("unrecognized subcommand: %s"),argv[0]);}
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:53
Even before the recent refactoring, 'git multi-pack-index' calls
'trace2_cmd_mode()' before verifying that the sub-command is recognized.
Push this call down into the individual sub-commands so that we don't
enter a bogus command mode.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 10 ++++++++--
1 file changed, 8 insertions(+), 2 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:54
A subsequent patch will need to refer back to 'midx_name' later on in
the function. In fact, this variable is already free()'d later on, so
this makes the later free() no longer redundant.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 1 -
1 file changed, 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:54
The 'read-midx' helper is used in places like t5319 to display basic
information about a multi-pack-index.
In the next patch, the MIDX writing machinery will learn a new way to
choose from which pack an object is selected when multiple copies of
that object exist.
To disambiguate which pack introduces an object so that this feature can
be tested, add a '--show-objects' option which displays additional
information about each object in the MIDX.
Signed-off-by: Taylor Blau <redacted>
---
t/helper/test-read-midx.c | 24 ++++++++++++++++++++----
1 file changed, 20 insertions(+), 4 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:54
When given a sub-command that it doesn't understand, 'git
multi-pack-index' dies with the following message:
$ git multi-pack-index bogus
fatal: unrecognized subcommand: bogus
Instead of 'die()'-ing, we can display the usage text, which is much
more helpful:
$ git.compile multi-pack-index bogus
usage: git multi-pack-index [<options>] write
or: git multi-pack-index [<options>] verify
or: git multi-pack-index [<options>] expire
or: git multi-pack-index [<options>] repack [--batch-size=<size>]
--object-dir <file> object directory containing set of packfile and pack-index pairs
--progress force progress reporting
While we're at it, clean up some duplication between the "no sub-command"
and "unrecognized sub-command" conditionals.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 7 ++++---
1 file changed, 4 insertions(+), 3 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:05:54
When multiple packs in the multi-pack index contain the same object, the
MIDX machinery must make a choice about which pack it associates with
that object. Prior to this patch, the lowest-ordered[1] pack was always
selected.
Pack selection for duplicate objects is relatively unimportant today,
but it will become important for multi-pack bitmaps. This is because we
can only invoke the pack-reuse mechanism when all of the bits for reused
objects come from the reuse pack (in order to ensure that all reused
deltas can find their base objects in the same pack).
To encourage the pack selection process to prefer one pack over another
(the pack to be preferred is the one a caller would like to later use as
a reuse pack), introduce the concept of a "preferred pack". When
provided, the MIDX code will always prefer an object found in a
preferred pack over any other.
No format changes are required to store the preferred pack, since it
will be able to be inferred with a corresponding MIDX bitmap, by looking
up the pack associated with the object in the first bit position (this
ordering is described in detail in a subsequent commit).
[1]: the ordering is specified by MIDX internals; for our purposes we
can consider the "lowest ordered" pack to be "the one with the
most-recent mtime.
Signed-off-by: Taylor Blau <redacted>
---
Documentation/git-multi-pack-index.txt | 14 ++-
Documentation/technical/multi-pack-index.txt | 5 +-
builtin/multi-pack-index.c | 18 +++-
builtin/repack.c | 2 +-
midx.c | 92 ++++++++++++++++++--
midx.h | 2 +-
t/t5319-multi-pack-index.sh | 39 +++++++++
7 files changed, 154 insertions(+), 18 deletions(-)
@@ -30,7 +31,16 @@ OPTIONS The following subcommands are available: write::- Write a new MIDX file.+ Write a new MIDX file. The following options are available for+ the `write` sub-command:+++--+ --preferred-pack=<pack>::+ Optionally specify the tie-breaking pack used when+ multiple packs contain the same object. If not given,+ ties are broken in favor of the pack with the lowest+ mtime.+-- verify:: Verify the contents of the MIDX file.
@@ -43,8 +43,9 @@ Design Details a change in format. - The MIDX keeps only one record per object ID. If an object appears- in multiple packfiles, then the MIDX selects the copy in the most-- recently modified packfile.+ in multiple packfiles, then the MIDX selects the copy in the+ preferred packfile, otherwise selecting from the most-recently+ modified packfile. - If there exist packfiles in the pack directory not registered in the MIDX, then those packfiles are loaded into the `packed_git`
@@ -500,6 +521,12 @@ static int midx_oid_compare(const void *_a, const void *_b)if(cmp)returncmp;+/* Sort objects in a preferred pack first when multiple copies exist. */+if(a->preferred>b->preferred)+return-1;+if(a->preferred<b->preferred)+return1;+if(a->pack_mtime>b->pack_mtime)return-1;elseif(a->pack_mtime<b->pack_mtime)
@@ -527,7 +554,8 @@ static int nth_midxed_pack_midx_entry(struct multi_pack_index *m,staticvoidfill_pack_entry(uint32_tpack_int_id,structpacked_git*p,uint32_tcur_object,-structpack_midx_entry*entry)+structpack_midx_entry*entry,+intpreferred){if(nth_packed_object_id(&entry->oid,p,cur_object)<0)die(_("failed to locate object %d in packfile"),cur_object);
@@ -234,6 +242,37 @@ test_expect_success 'warn on improper hash version' ')'+test_expect_success'midx picks objects from preferred pack''+test_when_finishedrm-rfpreferred.git&&+gitinit--barepreferred.git&&+(+cdpreferred.git&&++a=$(echo"a"|githash-object-w--stdin)&&+b=$(echo"b"|githash-object-w--stdin)&&+c=$(echo"c"|githash-object-w--stdin)&&++# Set up two packs, duplicating the object "B" at different+# offsets.+gitpack-objectsobjects/pack/test-AB<<-EOF&&+$a+$b+EOF+bc=$(gitpack-objectsobjects/pack/test-BC<<-EOF+$b+$c+EOF+)&&++gitmulti-pack-index--object-dir=objects\+write--preferred-pack=test-BC-$bc.idx2>err&&+test_must_be_emptyerr&&++ofs=$(gitshow-index<objects/pack/test-BC-$bc.idx|grep$b|+cut-d" "-f1)&&+midx_expect_object_offset$b$ofsobjects+)+' test_expect_success'verify multi-pack-index success''gitmulti-pack-indexverify--object-dir=$objdir
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:24
write_midx_internal() uses a hashfile to write the multi-pack index, but
discards its checksum. This makes sense, since nothing that takes place
after writing the MIDX cares about its checksum.
That is about to change in a subsequent patch, when the optional
reverse index corresponding to the MIDX will want to include the MIDX's
checksum.
Store the checksum of the MIDX in preparation for that.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:24
In a subsequent commit, pack-revindex.c will become responsible for
sorting a list of objects in the "MIDX pack order" (which will be
defined in the following patch). To do so, it will need to be know the
pack identifier and offset within that pack for each object in the MIDX.
The MIDX code already has functions for doing just that
(nth_midxed_offset() and nth_midxed_pack_int_id()), but they are
statically declared.
Since there is no reason that they couldn't be exposed publicly, and
because they are already doing exactly what the caller in
pack-revindex.c will want, expose them publicly so that they can be
reused there.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 4 ++--
midx.h | 2 ++
2 files changed, 4 insertions(+), 2 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:25
As a prerequisite to implementing multi-pack bitmaps, motivate and
describe the format and ordering of the multi-pack reverse index.
The subsequent patch will implement reading this format, and the patch
after that will implement writing it while producing a multi-pack index.
Co-authored-by: Jeff King [off-list ref]
Signed-off-by: Jeff King <redacted>
Signed-off-by: Taylor Blau <redacted>
---
Documentation/technical/pack-format.txt | 83 +++++++++++++++++++++++++
1 file changed, 83 insertions(+)
@@ -379,3 +379,86 @@ CHUNK DATA: TRAILER: Index checksum of the above contents.++== multi-pack-index reverse indexes++Similar to the pack-based reverse index, the multi-pack index can also+be used to generate a reverse index.++Instead of mapping between offset, pack-, and index position, this+reverse index maps between an object's position within the MIDX, and+that object's position within a pseudo-pack that the MIDX describes+(i.e., the ith entry of the multi-pack reverse index holds the MIDX+position of ith object in pseudo-pack order).++To clarify the difference between these orderings, consider a multi-pack+reachability bitmap (which does not yet exist, but is what we are+building towards here). Each bit needs to correspond to an object in the+MIDX, and so we need an efficient mapping from bit position to MIDX+position.++One solution is to let bits occupy the same position in the oid-sorted+index stored by the MIDX. But because oids are effectively random, there+resulting reachability bitmaps would have no locality, and thus compress+poorly. (This is the reason that single-pack bitmaps use the pack+ordering, and not the .idx ordering, for the same purpose.)++So we'd like to define an ordering for the whole MIDX based around+pack ordering, which has far better locality (and thus compresses more+efficiently). We can think of a pseudo-pack created by the concatenation+of all of the packs in the MIDX. E.g., if we had a MIDX with three packs+(a, b, c), with 10, 15, and 20 objects respectively, we can imagine an+ordering of the objects like:++ |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|++where the ordering of the packs is defined by the MIDX's pack list,+and then the ordering of objects within each pack is the same as the+order in the actual packfile.++Given the list of packs and their counts of objects, you can+naïvely reconstruct that pseudo-pack ordering (e.g., the object at+position 27 must be (c,1) because packs "a" and "b" consumed 25 of the+slots). But there's a catch. Objects may be duplicated between packs, in+which case the MIDX only stores one pointer to the object (and thus we'd+want only one slot in the bitmap).++Callers could handle duplicates themselves by reading objects in order+of their bit-position, but that's linear in the number of objects, and+much too expensive for ordinary bitmap lookups. Building a reverse index+solves this, since it is the logical inverse of the index, and that+index has already removed duplicates. But, building a reverse index on+the fly can be expensive. Since we already have an on-disk format for+pack-based reverse indexes, let's reuse it for the MIDX's pseudo-pack,+too.++Objects from the MIDX are ordered as follows to string together the+pseudo-pack. Let _pack(o)_ return the pack from which _o_ was selected+by the MIDX, and define an ordering of packs based on their numeric ID+(as stored by the MIDX). Let _offset(o)_ return the object offset of _o_+within _pack(o)_. Then, compare _o~1~_ and _o~2~_ as follows:++ - If one of _pack(o~1~)_ and _pack(o~2~)_ is preferred and the other+ is not, then the preferred one sorts first.+++(This is a detail that allows the MIDX bitmap to determine which+pack should be used by the pack-reuse mechanism, since it can ask+the MIDX for the pack containing the object at bit position 0).++ - If _pack(o~1~) ≠ pack(o~2~)_, then sort the two objects in+ descending order based on the pack ID.++ - Otherwise, _pack(o~1~) = pack(o~2~)_, and the objects are+ sorted in pack-order (i.e., _o~1~_ sorts ahead of _o~2~_ exactly+ when _offset(o~1~) < offset(o~2~)_).++In short, a MIDX's pseudo-pack is the de-duplicated concatenation of+objects in packs stored by the MIDX, laid out in pack order, and the+packs arranged in MIDX order (with the preferred pack coming first).++Finally, note that the MIDX's reverse index is not stored as a chunk in+the multi-pack-index itself. This is done because the reverse index+includes the checksum of the pack or MIDX to which it belongs, which+makes it impossible to write in the MIDX. To avoid races when rewriting+the MIDX, a MIDX reverse index includes the MIDX's checksum in its+filename (e.g., `multi-pack-index-xyz.rev`).
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:25
Implement reading for multi-pack reverse indexes, as described in the
previous patch.
Note that these functions don't yet have any callers, and won't until
multi-pack reachability bitmaps are introduced in a later patch series.
In the meantime, this patch implements some of the infrastructure
necessary to support multi-pack bitmaps.
There are three new functions exposed by the revindex API:
- load_midx_revindex(): loads the reverse index corresponding to the
given multi-pack index.
- midx_to_pack_pos() and pack_pos_to_midx(): these convert between the
multi-pack index and pseudo-pack order.
load_midx_revindex() and pack_pos_to_midx() are both relatively
straightforward.
load_midx_revindex() needs a few functions to be exposed from the midx
API. One to get the checksum of a midx, and another to get the .rev's
filename. Similar to recent changes in the packed_git struct, three new
fields are added to the multi_pack_index struct: one to keep track of
the size, one to keep track of the mmap'd pointer, and another to point
past the header and at the reverse index's data.
pack_pos_to_midx() simply reads the corresponding entry out of the
table.
midx_to_pack_pos() is the trickiest, since it needs to find an object's
position in the psuedo-pack order, but that order can only be recovered
in the .rev file itself. This mapping can be implemented with a binary
search, but note that the thing we're binary searching over isn't an
array of values, but rather a permuted order of those values.
So, when comparing two items, it's helpful to keep in mind the
difference. Instead of a traditional binary search, where you are
comparing two things directly, here we're comparing a (pack, offset)
tuple with an index into the multi-pack index. That index describes
another (pack, offset) tuple, and it is _those_ two tuples that are
compared.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 11 +++++
midx.h | 6 +++
pack-revindex.c | 127 ++++++++++++++++++++++++++++++++++++++++++++++++
pack-revindex.h | 53 ++++++++++++++++++++
packfile.c | 3 ++
5 files changed, 200 insertions(+)
@@ -292,6 +293,44 @@ int load_pack_revindex(struct packed_git *p)return-1;}+intload_midx_revindex(structmulti_pack_index*m)+{+char*revindex_name;+intret;+if(m->revindex_data)+return0;++revindex_name=get_midx_rev_filename(m);++ret=load_revindex_from_disk(revindex_name,+m->num_objects,+&m->revindex_map,+&m->revindex_len);+if(ret)+gotocleanup;++m->revindex_data=(constuint32_t*)((constchar*)m->revindex_map+RIDX_HEADER_SIZE);++cleanup:+free(revindex_name);+returnret;+}++intclose_midx_revindex(structmulti_pack_index*m)+{+if(!m)+return0;++if(munmap((void*)m->revindex_map,m->revindex_len))+return-1;++m->revindex_map=NULL;+m->revindex_data=NULL;+m->revindex_len=0;++return0;+}+intoffset_to_pack_pos(structpacked_git*p,off_tofs,uint32_t*pos){unsignedlo,hi;
@@ -346,3 +385,91 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)elsereturnnth_packed_object_offset(p,pack_pos_to_index(p,pos));}++uint32_tpack_pos_to_midx(structmulti_pack_index*m,uint32_tpos)+{+if(!m->revindex_data)+BUG("pack_pos_to_midx: reverse index not yet loaded");+if(m->num_objects<=pos)+BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32,pos);+returnget_be32((constchar*)m->revindex_data+(pos*sizeof(uint32_t)));+}++structmidx_pack_key{+uint32_tpack;+off_toffset;++uint32_tpreferred_pack;+structmulti_pack_index*midx;+};++staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb)+{+conststructmidx_pack_key*key=va;+structmulti_pack_index*midx=key->midx;++uint32_tversus=pack_pos_to_midx(midx,(uint32_t*)vb-(constuint32_t*)midx->revindex_data);+uint32_tversus_pack=nth_midxed_pack_int_id(midx,versus);+off_tversus_offset;++uint32_tkey_preferred=key->pack==key->preferred_pack;+uint32_tversus_preferred=versus_pack==key->preferred_pack;++/*+*First,comparethepreferred-ness,notingthatthepreferredpack+*comesfirst.+*/+if(key_preferred&&!versus_preferred)+return-1;+elseif(!key_preferred&&versus_preferred)+return1;++/* Then, break ties first by comparing the pack IDs. */+if(key->pack<versus_pack)+return-1;+elseif(key->pack>versus_pack)+return1;++/* Finally, break ties by comparing offsets within a pack. */+versus_offset=nth_midxed_offset(midx,versus);+if(key->offset<versus_offset)+return-1;+elseif(key->offset>versus_offset)+return1;++return0;+}++intmidx_to_pack_pos(structmulti_pack_index*m,uint32_tat,uint32_t*pos)+{+structmidx_pack_keykey;+uint32_t*found;++if(!m->revindex_data)+BUG("midx_to_pack_pos: reverse index not yet loaded");+if(m->num_objects<=at)+BUG("midx_to_pack_pos: out-of-bounds object at %"PRIu32,at);++key.pack=nth_midxed_pack_int_id(m,at);+key.offset=nth_midxed_offset(m,at);+key.midx=m;+/*+*Thepreferredpacksortsfirst,sodetermineitsidentifierby+*lookingatthefirstobjectinpseudo-packorder.+*+*Notethatifno--preferred-packisexplicitlygivenwhenwritinga+*multi-packindex,thenwhicheverpackhasthelowestidentifier+*implicitlyispreferred(andincludesallitsobjects,sincetiesare+*brokenfirstbypackidentifier).+*/+key.preferred_pack=nth_midxed_pack_int_id(m,pack_pos_to_midx(m,0));++found=bsearch(&key,m->revindex_data,m->num_objects,+sizeof(uint32_t),midx_pack_order_cmp);++if(!found)+returnerror("bad offset for revindex");++*pos=found-m->revindex_data;+return0;+}
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:25
Existing callers provide the reverse index code with an array of 'struct
pack_idx_entry *'s, which is then sorted by pack order (comparing the
offsets of each object within the pack).
Prepare for the multi-pack index to write a .rev file by providing a way
to write the reverse index without an array of pack_idx_entry (which the
MIDX code does not have).
Instead, callers can invoke 'write_rev_index_positions()', which takes
an array of uint32_t's. The ith entry in this array specifies the ith
object's (in index order) position within the pack (in pack order).
Expose this new function for use in a later patch, and rewrite the
existing write_rev_file() in terms of this new function.
Signed-off-by: Taylor Blau <redacted>
---
pack-write.c | 36 +++++++++++++++++++++++++-----------
pack.h | 1 +
2 files changed, 26 insertions(+), 11 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:25
Implement the writing half of multi-pack reverse indexes. This is
nothing more than the format describe a few patches ago, with a new set
of helper functions that will be used to clear out stale .rev files
corresponding to old MIDXs.
Unfortunately, a very similar comparison function as the one implemented
recently in pack-revindex.c is reimplemented here, this time accepting a
MIDX-internal type. An effort to DRY these up would create more
indirection and overhead than is necessary, so it isn't pursued here.
Currently, there are no callers which pass the MIDX_WRITE_REV_INDEX
flag, meaning that this is all dead code. But, that won't be the case
for long, since subsequent patches will introduce the multi-pack bitmap,
which will begin passing this field.
(In midx.c:write_midx_internal(), the two adjacent if statements share a
conditional, but are written separately since the first one will
eventually also handle the MIDX_WRITE_BITMAP flag, which does not yet
exist.)
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
midx.h | 1 +
2 files changed, 116 insertions(+)
@@ -826,6 +828,70 @@ static int write_midx_large_offsets(struct hashfile *f,return0;}+staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb,void*_ctx)+{+structwrite_midx_context*ctx=_ctx;++structpack_midx_entry*a=&ctx->entries[*(constuint32_t*)va];+structpack_midx_entry*b=&ctx->entries[*(constuint32_t*)vb];++uint32_tperm_a=ctx->pack_perm[a->pack_int_id];+uint32_tperm_b=ctx->pack_perm[b->pack_int_id];++/* Sort objects in the preferred pack ahead of any others. */+if(a->preferred>b->preferred)+return-1;+if(a->preferred<b->preferred)+return1;++/* Then, order objects by which packs they appear in. */+if(perm_a<perm_b)+return-1;+if(perm_a>perm_b)+return1;++/* Then, disambiguate by their offset within each pack. */+if(a->offset<b->offset)+return-1;+if(a->offset>b->offset)+return1;++return0;+}++staticuint32_t*midx_pack_order(structwrite_midx_context*ctx)+{+uint32_t*pack_order;+uint32_ti;++ALLOC_ARRAY(pack_order,ctx->entries_nr);+for(i=0;i<ctx->entries_nr;i++)+pack_order[i]=i;+QSORT_S(pack_order,ctx->entries_nr,midx_pack_order_cmp,ctx);++returnpack_order;+}++staticvoidwrite_midx_reverse_index(char*midx_name,unsignedchar*midx_hash,+structwrite_midx_context*ctx)+{+structstrbufbuf=STRBUF_INIT;+constchar*tmp_file;++strbuf_addf(&buf,"%s-%s.rev",midx_name,hash_to_hex(midx_hash));++tmp_file=write_rev_file_order(NULL,ctx->pack_order,ctx->entries_nr,+midx_hash,WRITE_REV);++if(finalize_object_file(tmp_file,buf.buf))+die(_("cannot store reverse index file"));++strbuf_release(&buf);+}++staticvoidclear_midx_files_ext(structrepository*r,constchar*ext,+unsignedchar*keep_hash);+staticintwrite_midx_internal(constchar*object_dir,structmulti_pack_index*m,structstring_list*packs_to_drop,constchar*preferred_pack_name,
From: Taylor Blau <hidden> Date: 2021-03-11 17:06:25
From: Jeff King <redacted>
There is a lot of pointer dereferencing in the pre-image version of
'midx_pack_order_cmp()', which this patch gets rid of.
Instead of comparing the pack preferred-ness and then the pack id, both
of these checks are done at the same time by using the high-order bit of
the pack id to represent whether it's preferred. Then the pack id and
offset are compared as usual.
This produces the same result so long as there are less than 2^31 packs,
which seems like a likely assumption to make in practice.
Signed-off-by: Jeff King <redacted>
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 55 +++++++++++++++++++++++++++++--------------------------
1 file changed, 29 insertions(+), 26 deletions(-)
@@ -828,46 +828,49 @@ static int write_midx_large_offsets(struct hashfile *f,return0;}-staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb,void*_ctx)+structmidx_pack_order_data{+uint32_tnr;+uint32_tpack;+off_toffset;+};++staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb){-structwrite_midx_context*ctx=_ctx;--structpack_midx_entry*a=&ctx->entries[*(constuint32_t*)va];-structpack_midx_entry*b=&ctx->entries[*(constuint32_t*)vb];--uint32_tperm_a=ctx->pack_perm[a->pack_int_id];-uint32_tperm_b=ctx->pack_perm[b->pack_int_id];--/* Sort objects in the preferred pack ahead of any others. */-if(a->preferred>b->preferred)+conststructmidx_pack_order_data*a=va,*b=vb;+if(a->pack<b->pack)return-1;-if(a->preferred<b->preferred)+elseif(a->pack>b->pack)return1;--/* Then, order objects by which packs they appear in. */-if(perm_a<perm_b)+elseif(a->offset<b->offset)return-1;-if(perm_a>perm_b)+elseif(a->offset>b->offset)return1;--/* Then, disambiguate by their offset within each pack. */-if(a->offset<b->offset)-return-1;-if(a->offset>b->offset)-return1;--return0;+else+return0;}staticuint32_t*midx_pack_order(structwrite_midx_context*ctx){+structmidx_pack_order_data*data;uint32_t*pack_order;uint32_ti;+ALLOC_ARRAY(data,ctx->entries_nr);+for(i=0;i<ctx->entries_nr;i++){+structpack_midx_entry*e=&ctx->entries[i];+data[i].nr=i;+data[i].pack=ctx->pack_perm[e->pack_int_id];+if(!e->preferred)+data[i].pack|=(1U<<31);+data[i].offset=e->offset;+}++QSORT(data,ctx->entries_nr,midx_pack_order_cmp);+ALLOC_ARRAY(pack_order,ctx->entries_nr);for(i=0;i<ctx->entries_nr;i++)-pack_order[i]=i;-QSORT_S(pack_order,ctx->entries_nr,midx_pack_order_cmp,ctx);+pack_order[i]=data[i].nr;+free(data);returnpack_order;}
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps. The previous version
was based on 'ds/chunked-file-api', but that topic has since been merged
to 'master'. This series is now built directly on top of 'master'.
Not much has changed since last time. Jonathan Tan reviewed the previous
version, and I incorporated feedback from his review:
- The usage macros in builtin/multi-pack-index.c were pulled out and
defined separately.
- Some sloppiness with converting a signed index referring to the
preferred pack into an unsigned value was cleaned up.
- Documentation clean-up, particularly in patches 12 and 13.
There are a couple of new things that we found while testing this out at
GitHub.
- We now call finalize_object_file() on the multi-pack reverse index
to set the correct permissions.
- Patch 14 removed a stray hunk that introduced a memory leak.
- Patch 16 (courtesy of Peff) is new. It improves the cache locality
of midx_pack_order_cmp(), which has a substantial impact on
repositories with many objects.
Thanks in advance for your review.
I've reviewed the changes since my last review and this one looks
good, including that new patch from Peff.
Thanks,
-Stolee
From: Jeff King <hidden> Date: 2021-03-29 11:21:45
On Thu, Mar 11, 2021 at 12:04:36PM -0500, Taylor Blau wrote:
Subcommands of the 'git multi-pack-index' command (e.g., 'write',
'verify', etc.) will want to optionally change a set of shared flags
that are eventually passed to the MIDX libraries.
Right now, options and flags are handled separately. Inline them into
the same structure so that sub-commands can more easily share the
'flags' data.
This "opts" struct is kind of funny. It is used to collect the options
in cmd_multi_pack_index(), but nobody ever passes it anywhere! Instead,
we pass individual components of it around.
So I'm not sure I buy "...so that sub-commands can more easily share the
flags data", since either way they are all receiving the individual
flags field already. And your patch 2 could just as easily do the same
simplification by modifying the function-local "flags" variable.
But. I think things get more interesting when you later introduce
common_opts, because now those options have to refer back to actuals
storage for each item. Which means that "flags" would have to become a
global variable. And there it's nicer to have all of the options stuffed
into a struct, even if it is a single global struct.
So I think this is the right direction, but it took me a minute to
realize quite why.
-Peff
From: Jeff King <hidden> Date: 2021-03-29 11:23:54
On Thu, Mar 11, 2021 at 12:04:40PM -0500, Taylor Blau wrote:
Now that there is a shared 'flags' member in the options structure,
there is no need to keep track of whether to force progress or not,
since ultimately the decision of whether or not to show a progress meter
is controlled by a bit in the flags member.
Just going back to what I wrote for patch 1, I think this "now that
there is a shared flags..." bit is what misled me.
You can easily have done this patch by just manipulating the local
"flags" variable. And the rationale for the patch is "we can get rid of
opts.progress, because nobody ever reads it except to set a bit
opts.flags".
Definitely not worth re-rolling or anything; I'm just explaining my
earlier comments. :)
-Peff
From: Jeff King <hidden> Date: 2021-03-29 11:37:15
On Thu, Mar 11, 2021 at 12:04:49PM -0500, Taylor Blau wrote:
Handle sub-commands of the 'git multi-pack-index' builtin (e.g.,
"write", "repack", etc.) separately from one another. This allows
sub-commands with unique options, without forcing cmd_multi_pack_index()
to reject invalid combinations itself.
This comes at the cost of some duplication and boilerplate. Luckily, the
duplication is reduced to a minimum, since common options are shared
among sub-commands due to a suggestion by Ævar. (Sub-commands do have to
retain the common options, too, since this builtin accepts common
options on either side of the sub-command).
Roughly speaking, cmd_multi_pack_index() parses options (including
common ones), and stops at the first non-option, which is the
sub-command. It then dispatches to the appropriate sub-command, which
parses the remaining options (also including common options).
Unknown options are kept by the sub-commands in order to detect their
presence (and complain that too many arguments were given).
Makes sense, and the implementation looks pretty clean.
A few small nits:
This free(prev) pattern is copied from builtin/checkout.c, where we have
multiple layers of options, each added by a function. So it requires
that callers duplicate the base set of options, and each subsequent
"add_foo_options()" concatenates that and frees the old one.
But here, we only have one layer, so in the caller which uses it:
we do a rather pointless dup() followed by free(). Perhaps not that big
a deal, and this would naturally extend to adding other option sets, so
it may even be considered future-proofing. But it did confuse me for a
moment.
However, we do end up leaking the return value from add_common_options()
at the end of the function:
This is definitely a harmless leak in the sense that we are going to
exit the program after midx_repack() returns anyway. But it might be
worth keeping things tidy, as we've recently seen a renewed effort to do
some leak-checking of the test suite. I _think_ we can just free the
options struct (even though we are still using the values themselves, we
don't care about the "struct options" anymore). But even if not, an
UNLEAK(options) annotation would do it.
(This doesn't apply to the other functions, because they just use
common_opts directly).
-Peff
From: Jeff King <hidden> Date: 2021-03-29 11:43:10
On Thu, Mar 11, 2021 at 12:04:57PM -0500, Taylor Blau wrote:
When given a sub-command that it doesn't understand, 'git
multi-pack-index' dies with the following message:
$ git multi-pack-index bogus
fatal: unrecognized subcommand: bogus
Instead of 'die()'-ing, we can display the usage text, which is much
more helpful:
$ git.compile multi-pack-index bogus
usage: git multi-pack-index [<options>] write
or: git multi-pack-index [<options>] verify
or: git multi-pack-index [<options>] expire
or: git multi-pack-index [<options>] repack [--batch-size=<size>]
--object-dir <file> object directory containing set of packfile and pack-index pairs
--progress force progress reporting
While we're at it, clean up some duplication between the "no sub-command"
and "unrecognized sub-command" conditionals.
I agree that it's much nicer to give the usage. But my preference in
general for cases like this is to _also_ explain what we found wrong
with the options we were given.
E.g., with a bogus option, we say so:
$ git multi-pack-index --foo
error: unknown option `foo'
usage: git multi-pack-index [<options>] write [--preferred-pack=<pack>]
[etc...]
but with a bogus sub-command, we get just the usage string:
$ git multi-pack-index foo
usage: git multi-pack-index [<options>] write [--preferred-pack=<pack>]
[etc...]
Sometimes it is quote obvious what is wrong, but sometimes typos can be
hard to spot, especially because the usage message is so long.
I.e., I'd suggest changing this:
From: Jeff King <hidden> Date: 2021-03-29 12:01:51
On Thu, Mar 11, 2021 at 12:05:07PM -0500, Taylor Blau wrote:
To encourage the pack selection process to prefer one pack over another
(the pack to be preferred is the one a caller would like to later use as
a reuse pack), introduce the concept of a "preferred pack". When
provided, the MIDX code will always prefer an object found in a
preferred pack over any other.
No format changes are required to store the preferred pack, since it
will be able to be inferred with a corresponding MIDX bitmap, by looking
up the pack associated with the object in the first bit position (this
ordering is described in detail in a subsequent commit).
I think in the long run we may want to add a midx chunk that gives the
order of the packs (and likewise allow the caller of "midx write" to
specify the exact order), since that may allow correlating locality
between history and object order within the .rev/.bitmap files.
But I think this is a nice stopping point for this series, since we're
not having to introduce any new on-disk formats to do it, and it seems
to give pretty good results in practice. I guess we'll have to support
--preferred-pack forever, but that's OK. Even if we do eventually
support arbitrary orderings, it's just a simple subset of that
functionality.
I don't think pack-objects guarantees that the pack ordering matches the
input it received. compute_write_order() uses a variety of heuristics to
reorder things. I think this will work in practice with the current
code, because the objects have the same type, there are no deltas, and
the fallback ordering is input-order (or traversal order, if --revs is
used).
So it's probably OK in practice, though if we wanted to be paranoid we
could check that show-index produces different results for the $b entry
of both packs. That said...
...what we really care about is that the object came from BC. And we are
just using the offset as a proxy for that. But doesn't "test-tool
read-midx" give us the actual pack name? We could just be checking that.
I also wondered if we should confirm that without the --preferred-pack
option, we choose the other pack. I think it will always be true because
the default order is to sort them lexically. A comment to that effect
might be worth it (near the "set up two packs" comment).
-Peff
From: Jeff King <hidden> Date: 2021-03-29 12:13:35
On Thu, Mar 11, 2021 at 12:05:25PM -0500, Taylor Blau wrote:
As a prerequisite to implementing multi-pack bitmaps, motivate and
describe the format and ordering of the multi-pack reverse index.
Nicely written overall. I found a few typos / formatting issues.
+One solution is to let bits occupy the same position in the oid-sorted
+index stored by the MIDX. But because oids are effectively random, there
s/there/their/
+Given the list of packs and their counts of objects, you can
+naïvely reconstruct that pseudo-pack ordering (e.g., the object at
An HTML entity seems to have snuck in. The source is utf8, so we can
just say ï.
+position 27 must be (c,1) because packs "a" and "b" consumed 25 of the
+slots). But there's a catch. Objects may be duplicated between packs, in
+which case the MIDX only stores one pointer to the object (and thus we'd
+want only one slot in the bitmap).
+
+Callers could handle duplicates themselves by reading objects in order
+of their bit-position, but that's linear in the number of objects, and
+much too expensive for ordinary bitmap lookups. Building a reverse index
+solves this, since it is the logical inverse of the index, and that
+index has already removed duplicates. But, building a reverse index on
+the fly can be expensive. Since we already have an on-disk format for
+pack-based reverse indexes, let's reuse it for the MIDX's pseudo-pack,
+too.
Yep, I think this nicely builds up the logic explaining the need for the
midx .rev file.
+Objects from the MIDX are ordered as follows to string together the
+pseudo-pack. Let _pack(o)_ return the pack from which _o_ was selected
+by the MIDX, and define an ordering of packs based on their numeric ID
+(as stored by the MIDX). Let _offset(o)_ return the object offset of _o_
+within _pack(o)_. Then, compare _o~1~_ and _o~2~_ as follows:
I guess the asciidoc-formatted version of this makes these nicely
italicized and subscripted. Personally I think pack(o) and o1 would be
more readable in the source (which is what I would tend to read). Or
maybe backticks if you want to be fancy.
+ - If _pack(o~1~) ≠ pack(o~2~)_, then sort the two objects in
+ descending order based on the pack ID.
+
+ - Otherwise, _pack(o~1~) = pack(o~2~)_, and the objects are
+ sorted in pack-order (i.e., _o~1~_ sorts ahead of _o~2~_ exactly
+ when _offset(o~1~) < offset(o~2~)_).
A few more HTML bits in the comparison operators.
-Peff
From: Jeff King <hidden> Date: 2021-03-29 12:44:34
On Thu, Mar 11, 2021 at 12:05:29PM -0500, Taylor Blau wrote:
Implement reading for multi-pack reverse indexes, as described in the
previous patch.
Looks good overall. I found a few tiny nits below.
+int load_midx_revindex(struct multi_pack_index *m)
+{
+ char *revindex_name;
+ int ret;
+ if (m->revindex_data)
+ return 0;
+
+ revindex_name = get_midx_rev_filename(m);
+
+ ret = load_revindex_from_disk(revindex_name,
+ m->num_objects,
+ &m->revindex_map,
+ &m->revindex_len);
+ if (ret)
+ goto cleanup;
On error, I wondered if m->revindex_map, etc, would be modified. But it
looks like no, load_revindex_from_disk() is careful not to touch them
unless it sees a valid revindex. Good.
It's hard to imagine why munmap() would fail. But if it does, we should
probably clear the struct fields anyway. I note that the matching code
for a "struct packed_git" does not bother even checking the return value
of munmap. Perhaps we should just do the same here.
The packed_git version also returned early if revindex_map is NULL. Here
the burden is placed on the caller (it's hard to tell if that matters
since there aren't any callers yet, but it probably makes sense to push
the check down into this function).
+uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos)
+{
+ if (!m->revindex_data)
+ BUG("pack_pos_to_midx: reverse index not yet loaded");
+ if (m->num_objects <= pos)
+ BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32, pos);
+ return get_be32((const char *)m->revindex_data + (pos * sizeof(uint32_t)));
+}
OK, this one is just a direct read of the .rev data, like
pack_pos_to_index() is. I think the final line can be simplified to:
return get_be32(m->revindex_data + pos);
just like pack_pos_to_index(). (I suspect this is a leftover from the
earlier version of your .rev series where the pointer was still a "void
*").
+int midx_to_pack_pos(struct multi_pack_index *m, uint32_t at, uint32_t *pos)
+{
+ struct midx_pack_key key;
+ uint32_t *found;
+
+ if (!m->revindex_data)
+ BUG("midx_to_pack_pos: reverse index not yet loaded");
+ if (m->num_objects <= at)
+ BUG("midx_to_pack_pos: out-of-bounds object at %"PRIu32, at);
+
+ key.pack = nth_midxed_pack_int_id(m, at);
+ key.offset = nth_midxed_offset(m, at);
+ key.midx = m;
+ /*
+ * The preferred pack sorts first, so determine its identifier by
+ * looking at the first object in pseudo-pack order.
+ *
+ * Note that if no --preferred-pack is explicitly given when writing a
+ * multi-pack index, then whichever pack has the lowest identifier
+ * implicitly is preferred (and includes all its objects, since ties are
+ * broken first by pack identifier).
+ */
+ key.preferred_pack = nth_midxed_pack_int_id(m, pack_pos_to_midx(m, 0));
+
+ found = bsearch(&key, m->revindex_data, m->num_objects,
+ sizeof(uint32_t), midx_pack_order_cmp);
OK, this one is _roughly_ equivalent to offset_to_pack_pos(), in that we
have to binary search within the pack-ordered list to find the entry.
Makes sense.
Probably sizeof(*m->revindex_data) would be slightly nicer in the
bsearch call (again, I suspect a holdover from when that was a void
pointer).
-Peff
From: Jeff King <hidden> Date: 2021-03-29 12:54:12
On Thu, Mar 11, 2021 at 12:05:38PM -0500, Taylor Blau wrote:
Implement the writing half of multi-pack reverse indexes. This is
nothing more than the format describe a few patches ago, with a new set
of helper functions that will be used to clear out stale .rev files
corresponding to old MIDXs.
This will clean up _any_ stale midx .rev file. So even if we miss one
when writing a new midx (due to a bug, race, power loss, etc), we'll
catch it later.
We _might_ want to also teach various tempfile-cleanup code run by gc to
likewise look for unattached midx .rev files, but I don't think we
necessarily have to do it now.
@@ -1049,6 +1162,8 @@ void clear_midx_file(struct repository *r) if (remove_path(midx)) die(_("failed to clear multi-pack-index at %s"), midx);+ clear_midx_files_ext(r, ".rev", NULL);+ free(midx);
The sole caller now doesn't pass the "keep" hash, so we'd always delete
all of them. I guess we'll see that change once somebody starts actually
writing them.
-Peff
From: Jeff King <hidden> Date: 2021-03-29 13:00:06
On Thu, Mar 11, 2021 at 12:05:42PM -0500, Taylor Blau wrote:
From: Jeff King <redacted>
There is a lot of pointer dereferencing in the pre-image version of
'midx_pack_order_cmp()', which this patch gets rid of.
Instead of comparing the pack preferred-ness and then the pack id, both
of these checks are done at the same time by using the high-order bit of
the pack id to represent whether it's preferred. Then the pack id and
offset are compared as usual.
This produces the same result so long as there are less than 2^31 packs,
which seems like a likely assumption to make in practice.
Obviously this patch is brilliant. ;)
Did we record any numbers to show the improvement here? I don't think it
can be demonstrated with this series (since most of the code is dead),
but I recall that this was motivated by a noticeable slowdown.
I briefly wondered whether the complicated midx_pack_order_cmp() in
pack-revindex.c, which is used for the bsearch() there, could benefit
from the same speedup. It's only log(n), of course, instead of n*log(n),
but one might imagine making "n" calls to it. I don't think it makes
sense, though. The pointer dereferencing there is into the midx mmap
itself. Creating an auxiliary array would defeat the purpose.
-Peff
From: Jeff King <hidden> Date: 2021-03-29 13:06:27
On Thu, Mar 11, 2021 at 12:04:31PM -0500, Taylor Blau wrote:
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps. The previous version
was based on 'ds/chunked-file-api', but that topic has since been merged
to 'master'. This series is now built directly on top of 'master'.
I gave the whole thing another careful read. Most of what I found were
small nits, but enough that I think one more re-roll is worth it.
The biggest question is what we want to happen next. As you note, the
concept of a midx .rev file is useless until we have the matching
.bitmap file. So we _could_ let this sit in next while the dependent
bitmap topic is reviewed, and then merge them down together. But I'm
inclined to treat this as an independent topic that can get merged to
master on its own, since the early cleanups are valuable on their own,
and the .rev parts at the end, even if dead, won't hurt anything.
If we did want to break it up, the useful line would be after "allow
marking a pack as preferred" (while it is mostly intended for the bitmap
selection, it is theoretically useful on its own to make it more likely
to find a copy of an object with a useful delta).
-Peff
From: Taylor Blau <hidden> Date: 2021-03-29 20:39:32
On Mon, Mar 29, 2021 at 07:36:21AM -0400, Jeff King wrote:
This is definitely a harmless leak in the sense that we are going to
exit the program after midx_repack() returns anyway. But it might be
worth keeping things tidy, as we've recently seen a renewed effort to do
some leak-checking of the test suite. I _think_ we can just free the
options struct (even though we are still using the values themselves, we
don't care about the "struct options" anymore). But even if not, an
UNLEAK(options) annotation would do it.
I see what you're saying. Let me make sure that I got the right idea in
mind after reading your email. I'm thinking of squashing the following
diff into this patch. For what it's worth, it causes 'valgrind
--leak-check=full ./git-multi-pack-index repack' to exit cleanly (when
it didn't before).
Does this match your expectations?
From: Taylor Blau <hidden> Date: 2021-03-29 21:16:37
On Mon, Mar 29, 2021 at 08:00:59AM -0400, Jeff King wrote:
I think in the long run we may want to add a midx chunk that gives the
order of the packs (and likewise allow the caller of "midx write" to
specify the exact order), since that may allow correlating locality
between history and object order within the .rev/.bitmap files.
But I think this is a nice stopping point for this series, since we're
not having to introduce any new on-disk formats to do it, and it seems
to give pretty good results in practice. I guess we'll have to support
--preferred-pack forever, but that's OK. Even if we do eventually
support arbitrary orderings, it's just a simple subset of that
functionality.
To add a little bit of extra detail, I think what you're getting at here
is that it would be nice to let the order of the packs be dictated by
mtime, not the order they appear in the MIDX (which is lexicographic by
their hash, and thus effectively random).
The reason there being the same as you pointed out in
https://lore.kernel.org/git/YDRdmh8oS5%2Fxq4rB@coredump.intra.peff.net/
which is that it effectively would lay objects out from newest to
oldest.
But, there's a problem, which is that the MIDX doesn't store the packs'
mtimes. That's fine for writing, since we can just look that information
up ourselves. But the reading side can get broken. That's because the
reader also has to know the pack order to go from MIDX- to bit-position.
So if a third party goes and touches some of the packs after the .rev
file was written, then the reader is going to think the packs ought to
appear in a different order than they actually do. So relying on having
to look up the mtimes again later on isn't good enough.
There are two solutions to the problem:
- You could write the mtimes in the MIDX itself. This would give you a
single point of reference, and resolve the TOCTOU race I just
described.
- Or, you could forget about mtimes entirely and let the MIDX dictate
the pack ordering itself. That resolves the race in a
similar-but-different way.
Of the two, I prefer the latter, but I think it introduces functionality
that we don't necessarily need yet. That's because the objects within
the packs are still ordered as such, and so the compression we get in
the packs is just as good as it is for single-pack bitmaps. It's only at
the objects between pack boundaries that any runs of 1s or 0s might be
interrupted, but there are far fewer pack boundaries than objects, so it
doesn't seem to matter in practice.
Anyway, I think that you know all of that already (mostly because we
thought aloud together when I originally brought this up), but I figure
that this detail may be interesting for other readers, too.
Could this just be replaced with bsearch() in the caller?
Great suggestion. Yes, it can be. FWIW, I think that I may have
originally thought that it couldn't be since we were comparing a fixed
string to an array of structs (each having a field which holds the value
we actually want to compare). But bsearch() always passes the key as the
first argument to the comparator, so this is possible to do.
...what we really care about is that the object came from BC. And we are
just using the offset as a proxy for that. But doesn't "test-tool
read-midx" give us the actual pack name? We could just be checking that.
I also wondered if we should confirm that without the --preferred-pack
option, we choose the other pack. I think it will always be true because
the default order is to sort them lexically. A comment to that effect
might be worth it (near the "set up two packs" comment).
From: Taylor Blau <hidden> Date: 2021-03-29 21:23:08
On Mon, Mar 29, 2021 at 08:12:39AM -0400, Jeff King wrote:
On Thu, Mar 11, 2021 at 12:05:25PM -0500, Taylor Blau wrote:
quoted
As a prerequisite to implementing multi-pack bitmaps, motivate and
describe the format and ordering of the multi-pack reverse index.
Nicely written overall. I found a few typos / formatting issues.
Thanks for the attention to detail. Everything you wrote makes sense to
me (including a quite-embarrassing mistake to switch "their" with
"there").
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-03-29 21:28:31
On Mon, Mar 29, 2021 at 08:43:39AM -0400, Jeff King wrote:
On Thu, Mar 11, 2021 at 12:05:29PM -0500, Taylor Blau wrote:
quoted
Implement reading for multi-pack reverse indexes, as described in the
previous patch.
Looks good overall. I found a few tiny nits below.
quoted
+int load_midx_revindex(struct multi_pack_index *m)
+{
+ char *revindex_name;
+ int ret;
+ if (m->revindex_data)
+ return 0;
+
+ revindex_name = get_midx_rev_filename(m);
+
+ ret = load_revindex_from_disk(revindex_name,
+ m->num_objects,
+ &m->revindex_map,
+ &m->revindex_len);
+ if (ret)
+ goto cleanup;
On error, I wondered if m->revindex_map, etc, would be modified. But it
looks like no, load_revindex_from_disk() is careful not to touch them
unless it sees a valid revindex. Good.
It's hard to imagine why munmap() would fail. But if it does, we should
probably clear the struct fields anyway. I note that the matching code
for a "struct packed_git" does not bother even checking the return value
of munmap. Perhaps we should just do the same here.
I tend to agree that we should match the behavior of
"packfile.c:close_pack_revindex()" and just not check the return value
of munmap. Either the call to munmap() worked, and we shouldn't be
reading revindex_map anymore, or it didn't, and something else is
probably wrong enough with the original mmap call that we probably also
shouldn't be reading it.
The packed_git version also returned early if revindex_map is NULL. Here
the burden is placed on the caller (it's hard to tell if that matters
since there aren't any callers yet, but it probably makes sense to push
the check down into this function).
Yeah, I think that that function actually is doing the worst of both
worlds (which is to check p->revindex_map, but not p itself).
I modified the MIDX version to check both m and m->revindex_map (but I
agree it's hard to tell with the caller coming in a later series).
quoted
+uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos)
+{
+ if (!m->revindex_data)
+ BUG("pack_pos_to_midx: reverse index not yet loaded");
+ if (m->num_objects <= pos)
+ BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32, pos);
+ return get_be32((const char *)m->revindex_data + (pos * sizeof(uint32_t)));
+}
OK, this one is just a direct read of the .rev data, like
pack_pos_to_index() is. I think the final line can be simplified to:
return get_be32(m->revindex_data + pos);
just like pack_pos_to_index(). (I suspect this is a leftover from the
earlier version of your .rev series where the pointer was still a "void
*").
Yes, definitely.
Probably sizeof(*m->revindex_data) would be slightly nicer in the
bsearch call (again, I suspect a holdover from when that was a void
pointer).
From: Taylor Blau <hidden> Date: 2021-03-29 21:31:21
On Mon, Mar 29, 2021 at 08:53:22AM -0400, Jeff King wrote:
On Thu, Mar 11, 2021 at 12:05:38PM -0500, Taylor Blau wrote:
quoted
Implement the writing half of multi-pack reverse indexes. This is
nothing more than the format describe a few patches ago, with a new set
of helper functions that will be used to clear out stale .rev files
corresponding to old MIDXs.
This will clean up _any_ stale midx .rev file. So even if we miss one
when writing a new midx (due to a bug, race, power loss, etc), we'll
catch it later.
We _might_ want to also teach various tempfile-cleanup code run by gc to
likewise look for unattached midx .rev files, but I don't think we
necessarily have to do it now.
@@ -1049,6 +1162,8 @@ void clear_midx_file(struct repository *r) if (remove_path(midx)) die(_("failed to clear multi-pack-index at %s"), midx);+ clear_midx_files_ext(r, ".rev", NULL);+ free(midx);
The sole caller now doesn't pass the "keep" hash, so we'd always delete
all of them. I guess we'll see that change once somebody starts actually
writing them.
That's right. I hope that the benefits of splitting the MIDX bitmaps
topic into two series has generally outweighed the drawbacks, but in
instances like these it can be kind of annoying.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-03-29 21:35:13
On Mon, Mar 29, 2021 at 08:59:12AM -0400, Jeff King wrote:
On Thu, Mar 11, 2021 at 12:05:42PM -0500, Taylor Blau wrote:
quoted
From: Jeff King <redacted>
There is a lot of pointer dereferencing in the pre-image version of
'midx_pack_order_cmp()', which this patch gets rid of.
Instead of comparing the pack preferred-ness and then the pack id, both
of these checks are done at the same time by using the high-order bit of
the pack id to represent whether it's preferred. Then the pack id and
offset are compared as usual.
This produces the same result so long as there are less than 2^31 packs,
which seems like a likely assumption to make in practice.
Obviously this patch is brilliant. ;)
Obviously.
Did we record any numbers to show the improvement here? I don't think it
can be demonstrated with this series (since most of the code is dead),
but I recall that this was motivated by a noticeable slowdown.
Looking through our messages, you wrote that this seemed to produce a
.8 second speed-up on a large-ish repository that we were testing.
That's not significant overall, the fact that we were spending so long
probably caught our attention when looking at a profiler.
I could go either way on mentioning it. It does feel a little like
cheating to say, "well, if you applied these other patches it would make
it about this much faster". So I'm mostly happy to just keep it vague
and say that it makes things a little faster, unless you feel strongly
otherwise.
I briefly wondered whether the complicated midx_pack_order_cmp() in
pack-revindex.c, which is used for the bsearch() there, could benefit
from the same speedup. It's only log(n), of course, instead of n*log(n),
but one might imagine making "n" calls to it. I don't think it makes
sense, though. The pointer dereferencing there is into the midx mmap
itself. Creating an auxiliary array would defeat the purpose.
From: Taylor Blau <hidden> Date: 2021-03-29 21:37:51
On Mon, Mar 29, 2021 at 09:05:33AM -0400, Jeff King wrote:
On Thu, Mar 11, 2021 at 12:04:31PM -0500, Taylor Blau wrote:
quoted
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps. The previous version
was based on 'ds/chunked-file-api', but that topic has since been merged
to 'master'. This series is now built directly on top of 'master'.
I gave the whole thing another careful read. Most of what I found were
small nits, but enough that I think one more re-roll is worth it.
Thanks. I agree that another re-roll is worth it. I have one prepared
locally, and I just had one outstanding question in:
https://lore.kernel.org/git/YGI6ySogGoYZi66A@nand.local/
that I'll wait on your reply to before sending a reroll.
The biggest question is what we want to happen next. As you note, the
concept of a midx .rev file is useless until we have the matching
.bitmap file. So we _could_ let this sit in next while the dependent
bitmap topic is reviewed, and then merge them down together. But I'm
inclined to treat this as an independent topic that can get merged to
master on its own, since the early cleanups are valuable on their own,
and the .rev parts at the end, even if dead, won't hurt anything.
That matches what I was hoping for. I think the clean-ups are worth it
on their own, but I also think it's a good idea to take the whole
series, since it means there's one less long-running branch in flight
while we review the MIDX bitmaps topic.
(FWIW, I can also see an argument in the other direction along the lines
of "we may discover something later on that requires us to change the
way multi-pack .rev files work". I think that such an outcome is fairly
unlikely, but worth considering anyway).
Thanks,
Taylor
From: Jeff King <hidden> Date: 2021-03-30 07:05:27
On Mon, Mar 29, 2021 at 04:38:33PM -0400, Taylor Blau wrote:
On Mon, Mar 29, 2021 at 07:36:21AM -0400, Jeff King wrote:
quoted
This is definitely a harmless leak in the sense that we are going to
exit the program after midx_repack() returns anyway. But it might be
worth keeping things tidy, as we've recently seen a renewed effort to do
some leak-checking of the test suite. I _think_ we can just free the
options struct (even though we are still using the values themselves, we
don't care about the "struct options" anymore). But even if not, an
UNLEAK(options) annotation would do it.
I see what you're saying. Let me make sure that I got the right idea in
mind after reading your email. I'm thinking of squashing the following
diff into this patch. For what it's worth, it causes 'valgrind
--leak-check=full ./git-multi-pack-index repack' to exit cleanly (when
it didn't before).
Does this match your expectations?
This simplification is orthogonal to the leak, and I'd be OK if you
wanted to retain it as it was before (because it future-proofs against
adding more add_foo_options() later, though for now it is a useless
dup/free pair).
From: Jeff King <hidden> Date: 2021-03-30 07:12:28
On Mon, Mar 29, 2021 at 05:15:12PM -0400, Taylor Blau wrote:
There are two solutions to the problem:
- You could write the mtimes in the MIDX itself. This would give you a
single point of reference, and resolve the TOCTOU race I just
described.
- Or, you could forget about mtimes entirely and let the MIDX dictate
the pack ordering itself. That resolves the race in a
similar-but-different way.
Of the two, I prefer the latter, but I think it introduces functionality
that we don't necessarily need yet.
Yeah, I'd strongly favor the latter over the former. The reason to go
with the solution you have in this series is that it doesn't require
changing anything in the on-disk midx format, and we think it is good
enough. But once we are going to change the on-disk format, we might as
well give the writing side as much flexibility as possible.
Of course the mtimes themselves are really just numbers, so in a sense
the two are really equivalent. ;)
That's because the objects within
the packs are still ordered as such, and so the compression we get in
the packs is just as good as it is for single-pack bitmaps. It's only at
the objects between pack boundaries that any runs of 1s or 0s might be
interrupted, but there are far fewer pack boundaries than objects, so it
doesn't seem to matter in practice.
Right. The absolute worst case is a large number of single-object packs,
in which case the bitmap order becomes essentially random with respect
to history (because it would be sorted by sha1 of the packs).
The effect _might_ be measurable in more real-world cases, like say one
big pack and 100 pushes each with a handful of commits. The big pack
would be in good shape, but you have a lot of extra pack boundaries that
hurt the bitmap compression.
But in practice, generating bitmaps is expensive enough that you'd
probably want to roll up some of the packs anyway (and that is certainly
what we are doing at GitHub, using your "repack --geometric"). So you'd
end usually with one big pack representing most of history, and then a
handful of roll-up packs.
So I'm a little curious whether one could even measure the impact of,
say, 100 little packs. But not enough to even run the experiment,
because even that is not a case that is really that interesting.
Anyway, I think that you know all of that already (mostly because we
thought aloud together when I originally brought this up), but I figure
that this detail may be interesting for other readers, too.
Indeed. And I know that you know everything I just wrote, but I agree
it's nice to get a record of these discussions onto the list. :)
-Peff
From: Jeff King <hidden> Date: 2021-03-30 07:15:44
On Mon, Mar 29, 2021 at 05:37:01PM -0400, Taylor Blau wrote:
quoted
The biggest question is what we want to happen next. As you note, the
concept of a midx .rev file is useless until we have the matching
.bitmap file. So we _could_ let this sit in next while the dependent
bitmap topic is reviewed, and then merge them down together. But I'm
inclined to treat this as an independent topic that can get merged to
master on its own, since the early cleanups are valuable on their own,
and the .rev parts at the end, even if dead, won't hurt anything.
That matches what I was hoping for. I think the clean-ups are worth it
on their own, but I also think it's a good idea to take the whole
series, since it means there's one less long-running branch in flight
while we review the MIDX bitmaps topic.
(FWIW, I can also see an argument in the other direction along the lines
of "we may discover something later on that requires us to change the
way multi-pack .rev files work". I think that such an outcome is fairly
unlikely, but worth considering anyway).
That would be my general worry, too, but in this case I am not too
concerned because I know the code has received substantial exercise
already on real-world production servers. So while we may clean up some
cosmetic bits or respond to review as it goes upstream, I'm much less
worried about seeing some brown-paper-bag bug that would be sufficient
to make us want to re-roll these .rev commits. And hopefully the
existing rounds have addressed the cosmetic/review bits.
-Peff
From: Jeff King <hidden> Date: 2021-03-30 07:16:50
On Mon, Mar 29, 2021 at 05:34:21PM -0400, Taylor Blau wrote:
quoted
Did we record any numbers to show the improvement here? I don't think it
can be demonstrated with this series (since most of the code is dead),
but I recall that this was motivated by a noticeable slowdown.
Looking through our messages, you wrote that this seemed to produce a
.8 second speed-up on a large-ish repository that we were testing.
That's not significant overall, the fact that we were spending so long
probably caught our attention when looking at a profiler.
That sounds about right from my recollection.
I could go either way on mentioning it. It does feel a little like
cheating to say, "well, if you applied these other patches it would make
it about this much faster". So I'm mostly happy to just keep it vague
and say that it makes things a little faster, unless you feel strongly
otherwise.
No, I don't feel strongly. I just wanted to give people reading a sense
of what to expect. Now we have.
-Peff
From: Taylor Blau <hidden> Date: 2021-03-30 13:38:13
On Tue, Mar 30, 2021 at 03:15:02AM -0400, Jeff King wrote:
On Mon, Mar 29, 2021 at 05:37:01PM -0400, Taylor Blau wrote:
quoted
(FWIW, I can also see an argument in the other direction along the lines
of "we may discover something later on that requires us to change the
way multi-pack .rev files work". I think that such an outcome is fairly
unlikely, but worth considering anyway).
That would be my general worry, too, but in this case I am not too
concerned because I know the code has received substantial exercise
already on real-world production servers. So while we may clean up some
cosmetic bits or respond to review as it goes upstream, I'm much less
worried about seeing some brown-paper-bag bug that would be sufficient
to make us want to re-roll these .rev commits. And hopefully the
existing rounds have addressed the cosmetic/review bits.
Yes. Another benefit is that it should give us substantial confidence in
the correctness not just of this topic, but of the multi-pack bitmaps
that are built on top, too.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:50
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps.
This reroll differs only in the feedback I incorporated from Peff's review. They
are mostly cosmetic; the most substantial change being that the --preferred-pack
code now uses bsearch() to locate the name of the preferred pack (instead of
implementing a binary search itself).
I think that this version is ready to go. I would hope that it can head for
'master' and avoid sitting in 'next' forever (since it has some worthwhile
cleanups outside of preparing for MIDX bitmaps).
But in either case, this is the last prereq series before MIDX bitmaps, which
I'll send shortly (based on this one).
Jeff King (1):
midx.c: improve cache locality in midx_pack_order_cmp()
Taylor Blau (15):
builtin/multi-pack-index.c: inline 'flags' with options
builtin/multi-pack-index.c: don't handle 'progress' separately
builtin/multi-pack-index.c: define common usage with a macro
builtin/multi-pack-index.c: split sub-commands
builtin/multi-pack-index.c: don't enter bogus cmd_mode
builtin/multi-pack-index.c: display usage on unrecognized command
t/helper/test-read-midx.c: add '--show-objects'
midx: allow marking a pack as preferred
midx: don't free midx_name early
midx: keep track of the checksum
midx: make some functions non-static
Documentation/technical: describe multi-pack reverse indexes
pack-revindex: read multi-pack reverse indexes
pack-write.c: extract 'write_rev_file_order'
pack-revindex: write multi-pack reverse indexes
Documentation/git-multi-pack-index.txt | 14 +-
Documentation/technical/multi-pack-index.txt | 5 +-
Documentation/technical/pack-format.txt | 83 +++++++
builtin/multi-pack-index.c | 182 ++++++++++++---
builtin/repack.c | 2 +-
midx.c | 219 +++++++++++++++++--
midx.h | 11 +-
pack-revindex.c | 126 +++++++++++
pack-revindex.h | 53 +++++
pack-write.c | 36 ++-
pack.h | 1 +
packfile.c | 3 +
t/helper/test-read-midx.c | 24 +-
t/t5319-multi-pack-index.sh | 43 ++++
14 files changed, 734 insertions(+), 68 deletions(-)
Range-diff against v3:
1: 43fc0ad276 ! 1: 90e021725f builtin/multi-pack-index.c: inline 'flags' with options
@@ Commit message
'verify', etc.) will want to optionally change a set of shared flags
that are eventually passed to the MIDX libraries.
- Right now, options and flags are handled separately. Inline them into
- the same structure so that sub-commands can more easily share the
- 'flags' data.
+ Right now, options and flags are handled separately. That's fine, since
+ the options structure is never passed around. But a future patch will
+ make it so that common options shared by all sub-commands are defined in
+ a common location. That means that "flags" would have to become a global
+ variable.
+
+ Group it with the options structure so that we reduce the number of
+ global variables we have overall.
Signed-off-by: Taylor Blau [off-list ref]
2: 181f11e4c5 = 2: 130c191b80 builtin/multi-pack-index.c: don't handle 'progress' separately
3: 94c498f0e2 = 3: 5a274b9096 builtin/multi-pack-index.c: define common usage with a macro
4: d084f90466 ! 4: b8c89cc239 builtin/multi-pack-index.c: split sub-commands
@@ builtin/multi-pack-index.c: static struct opts_multi_pack_index {
- OPT_FILENAME(0, "object-dir", &opts.object_dir,
- N_("object directory containing set of packfile and pack-index pairs")),
- OPT_BIT(0, "progress", &opts.flags, N_("force progress reporting"), MIDX_PROGRESS),
-+ struct option *with_common = parse_options_concat(common_opts, prev);
-+ free(prev);
-+ return with_common;
++ return parse_options_concat(common_opts, prev);
+}
+
+static int cmd_multi_pack_index_write(int argc, const char **argv)
@@ builtin/multi-pack-index.c: static struct opts_multi_pack_index {
OPT_END(),
};
-+ options = parse_options_dup(builtin_multi_pack_index_repack_options);
-+ options = add_common_options(options);
++ options = add_common_options(builtin_multi_pack_index_repack_options);
+
+ argc = parse_options(argc, argv, NULL,
+ options,
@@ builtin/multi-pack-index.c: static struct opts_multi_pack_index {
+ usage_with_options(builtin_multi_pack_index_repack_usage,
+ options);
+
++ FREE_AND_NULL(options);
++
+ return midx_repack(the_repository, opts.object_dir,
+ (size_t)opts.batch_size, opts.flags);
+}
5: bc3b6837f2 ! 5: d817920e2a builtin/multi-pack-index.c: don't enter bogus cmd_mode
@@ builtin/multi-pack-index.c: static int cmd_multi_pack_index_expire(int argc, con
options, builtin_multi_pack_index_expire_usage,
PARSE_OPT_KEEP_UNKNOWN);
@@ builtin/multi-pack-index.c: static int cmd_multi_pack_index_repack(int argc, const char **argv)
- options = parse_options_dup(builtin_multi_pack_index_repack_options);
- options = add_common_options(options);
+
+ options = add_common_options(builtin_multi_pack_index_repack_options);
+ trace2_cmd_mode(argv[0]);
+
6: f117e442c3 ! 6: 604a02ce85 builtin/multi-pack-index.c: display usage on unrecognized command
@@ Commit message
more helpful:
$ git.compile multi-pack-index bogus
+ error: unrecognized subcommand: bogus
usage: git multi-pack-index [<options>] write
or: git multi-pack-index [<options>] verify
or: git multi-pack-index [<options>] expire
@@ builtin/multi-pack-index.c: int cmd_multi_pack_index(int argc, const char **argv
if (!strcmp(argv[0], "repack"))
return cmd_multi_pack_index_repack(argc, argv);
@@ builtin/multi-pack-index.c: int cmd_multi_pack_index(int argc, const char **argv,
+ return cmd_multi_pack_index_verify(argc, argv);
else if (!strcmp(argv[0], "expire"))
return cmd_multi_pack_index_expire(argc, argv);
- else
+- else
- die(_("unrecognized subcommand: %s"), argv[0]);
++ else {
+usage:
++ error(_("unrecognized subcommand: %s"), argv[0]);
+ usage_with_options(builtin_multi_pack_index_usage,
+ builtin_multi_pack_index_options);
++ }
}
7: ae85a68ef2 = 7: 37e073ea27 t/helper/test-read-midx.c: add '--show-objects'
8: 30194a6786 ! 8: d061828e7e midx: allow marking a pack as preferred
@@ builtin/multi-pack-index.c: static struct option *add_common_options(struct opti
+ OPT_END(),
+ };
+
-+ options = parse_options_dup(builtin_multi_pack_index_write_options);
-+ options = add_common_options(options);
++ options = add_common_options(builtin_multi_pack_index_write_options);
trace2_cmd_mode(argv[0]);
@@ builtin/multi-pack-index.c: static int cmd_multi_pack_index_write(int argc, cons
options);
- return write_midx_file(opts.object_dir, opts.flags);
++ FREE_AND_NULL(options);
++
+ return write_midx_file(opts.object_dir, opts.preferred_pack,
+ opts.flags);
}
@@ midx.c: static int pack_info_compare(const void *_a, const void *_b)
return strcmp(a->pack_name, b->pack_name);
}
-+static int lookup_idx_or_pack_name(struct pack_info *info,
-+ uint32_t nr,
-+ const char *pack_name)
++static int idx_or_pack_name_cmp(const void *_va, const void *_vb)
+{
-+ uint32_t lo = 0, hi = nr;
-+ while (lo < hi) {
-+ uint32_t mi = lo + (hi - lo) / 2;
-+ int cmp = cmp_idx_or_pack_name(pack_name, info[mi].pack_name);
-+ if (cmp < 0)
-+ hi = mi;
-+ else if (cmp > 0)
-+ lo = mi + 1;
-+ else
-+ return mi;
-+ }
-+ return -1;
++ const char *pack_name = _va;
++ const struct pack_info *compar = _vb;
++
++ return cmp_idx_or_pack_name(pack_name, compar->pack_name);
+}
+
struct write_midx_context {
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
+ /* Check that the preferred pack wasn't expired (if given). */
+ if (preferred_pack_name) {
-+ int preferred_idx = lookup_idx_or_pack_name(ctx.info,
-+ ctx.nr,
-+ preferred_pack_name);
-+ if (preferred_idx < 0)
++ struct pack_info *preferred = bsearch(preferred_pack_name,
++ ctx.info, ctx.nr,
++ sizeof(*ctx.info),
++ idx_or_pack_name_cmp);
++
++ if (!preferred)
+ warning(_("unknown preferred pack: '%s'"),
+ preferred_pack_name);
+ else {
-+ uint32_t orig = ctx.info[preferred_idx].orig_pack_int_id;
-+ uint32_t perm = ctx.pack_perm[orig];
-+
++ uint32_t perm = ctx.pack_perm[preferred->orig_pack_int_id];
+ if (perm == PACK_EXPIRED)
+ warning(_("preferred pack '%s' is expired"),
+ preferred_pack_name);
@@ midx.h: int fill_midx_entry(struct repository *r, const struct object_id *oid, s
int expire_midx_packs(struct repository *r, const char *object_dir, unsigned flags);
## t/t5319-multi-pack-index.sh ##
-@@ t/t5319-multi-pack-index.sh: midx_read_expect () {
- test_cmp expect actual
- }
-
-+midx_expect_object_offset () {
-+ OID="$1"
-+ OFFSET="$2"
-+ OBJECT_DIR="$3"
-+ test-tool read-midx --show-objects $OBJECT_DIR >actual &&
-+ grep "^$OID $OFFSET" actual
-+}
-+
- test_expect_success 'setup' '
- test_oid_cache <<-EOF
- idxoff sha1:2999
@@ t/t5319-multi-pack-index.sh: test_expect_success 'warn on improper hash version' '
)
'
@@ t/t5319-multi-pack-index.sh: test_expect_success 'warn on improper hash version'
+
+ # Set up two packs, duplicating the object "B" at different
+ # offsets.
++ #
++ # Note that the "BC" pack (the one we choose as preferred) sorts
++ # lexically after the "AB" pack, meaning that omitting the
++ # --preferred-pack argument would cause this test to fail (since
++ # the MIDX code would select the copy of "b" in the "AB" pack).
+ git pack-objects objects/pack/test-AB <<-EOF &&
+ $a
+ $b
@@ t/t5319-multi-pack-index.sh: test_expect_success 'warn on improper hash version'
+ write --preferred-pack=test-BC-$bc.idx 2>err &&
+ test_must_be_empty err &&
+
++ echo hi &&
++ test-tool read-midx --show-objects objects >out &&
++
+ ofs=$(git show-index <objects/pack/test-BC-$bc.idx | grep $b |
+ cut -d" " -f1) &&
-+ midx_expect_object_offset $b $ofs objects
++ printf "%s %s\tobjects/pack/test-BC-%s.pack\n" \
++ "$b" "$ofs" "$bc" >expect &&
++ grep ^$b out >actual &&
++
++ test_cmp expect actual
+ )
+'
9: 5c5aca761a = 9: 33b8af97e7 midx: don't free midx_name early
10: a22a1463a5 = 10: 3fc9b83dc6 midx: keep track of the checksum
11: efa54479b1 = 11: 2ada397320 midx: make some functions non-static
12: 4745bb8590 ! 12: 8bb3dd24a7 Documentation/technical: describe multi-pack reverse indexes
@@ Documentation/technical/pack-format.txt: CHUNK DATA:
+position.
+
+One solution is to let bits occupy the same position in the oid-sorted
-+index stored by the MIDX. But because oids are effectively random, there
++index stored by the MIDX. But because oids are effectively random, their
+resulting reachability bitmaps would have no locality, and thus compress
+poorly. (This is the reason that single-pack bitmaps use the pack
+ordering, and not the .idx ordering, for the same purpose.)
@@ Documentation/technical/pack-format.txt: CHUNK DATA:
+order in the actual packfile.
+
+Given the list of packs and their counts of objects, you can
-+naïvely reconstruct that pseudo-pack ordering (e.g., the object at
++naïvely reconstruct that pseudo-pack ordering (e.g., the object at
+position 27 must be (c,1) because packs "a" and "b" consumed 25 of the
+slots). But there's a catch. Objects may be duplicated between packs, in
+which case the MIDX only stores one pointer to the object (and thus we'd
@@ Documentation/technical/pack-format.txt: CHUNK DATA:
+too.
+
+Objects from the MIDX are ordered as follows to string together the
-+pseudo-pack. Let _pack(o)_ return the pack from which _o_ was selected
++pseudo-pack. Let `pack(o)` return the pack from which `o` was selected
+by the MIDX, and define an ordering of packs based on their numeric ID
-+(as stored by the MIDX). Let _offset(o)_ return the object offset of _o_
-+within _pack(o)_. Then, compare _o~1~_ and _o~2~_ as follows:
++(as stored by the MIDX). Let `offset(o)` return the object offset of `o`
++within `pack(o)`. Then, compare `o1` and `o2` as follows:
+
-+ - If one of _pack(o~1~)_ and _pack(o~2~)_ is preferred and the other
++ - If one of `pack(o1)` and `pack(o2)` is preferred and the other
+ is not, then the preferred one sorts first.
++
+(This is a detail that allows the MIDX bitmap to determine which
+pack should be used by the pack-reuse mechanism, since it can ask
+the MIDX for the pack containing the object at bit position 0).
+
-+ - If _pack(o~1~) ≠ pack(o~2~)_, then sort the two objects in
-+ descending order based on the pack ID.
++ - If `pack(o1) ≠ pack(o2)`, then sort the two objects in descending
++ order based on the pack ID.
+
-+ - Otherwise, _pack(o~1~) = pack(o~2~)_, and the objects are
-+ sorted in pack-order (i.e., _o~1~_ sorts ahead of _o~2~_ exactly
-+ when _offset(o~1~) < offset(o~2~)_).
++ - Otherwise, `pack(o1) = pack(o2)`, and the objects are sorted in
++ pack-order (i.e., `o1` sorts ahead of `o2` exactly when `offset(o1)
++ < offset(o2)`).
+
+In short, a MIDX's pseudo-pack is the de-duplicated concatenation of
+objects in packs stored by the MIDX, laid out in pack order, and the
13: a6ebd4be91 ! 13: c070b9c99f pack-revindex: read multi-pack reverse indexes
@@ pack-revindex.c: int load_pack_revindex(struct packed_git *p)
+
+int close_midx_revindex(struct multi_pack_index *m)
+{
-+ if (!m)
++ if (!m || !m->revindex_map)
+ return 0;
+
-+ if (munmap((void*)m->revindex_map, m->revindex_len))
-+ return -1;
++ munmap((void*)m->revindex_map, m->revindex_len);
+
+ m->revindex_map = NULL;
+ m->revindex_data = NULL;
@@ pack-revindex.c: off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
+ BUG("pack_pos_to_midx: reverse index not yet loaded");
+ if (m->num_objects <= pos)
+ BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32, pos);
-+ return get_be32((const char *)m->revindex_data + (pos * sizeof(uint32_t)));
++ return get_be32(m->revindex_data + pos);
+}
+
+struct midx_pack_key {
@@ pack-revindex.c: off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
+ key.preferred_pack = nth_midxed_pack_int_id(m, pack_pos_to_midx(m, 0));
+
+ found = bsearch(&key, m->revindex_data, m->num_objects,
-+ sizeof(uint32_t), midx_pack_order_cmp);
++ sizeof(*m->revindex_data), midx_pack_order_cmp);
+
+ if (!found)
+ return error("bad offset for revindex");
14: f5314f1822 = 14: 9f40019eb3 pack-write.c: extract 'write_rev_file_order'
15: fa3acb5d5a = 15: 47409cc508 pack-revindex: write multi-pack reverse indexes
16: 550e785f10 = 16: 7b793e7d09 midx.c: improve cache locality in midx_pack_order_cmp()
--
2.30.0.667.g81c0cbc6fd
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:51
Subcommands of the 'git multi-pack-index' command (e.g., 'write',
'verify', etc.) will want to optionally change a set of shared flags
that are eventually passed to the MIDX libraries.
Right now, options and flags are handled separately. That's fine, since
the options structure is never passed around. But a future patch will
make it so that common options shared by all sub-commands are defined in
a common location. That means that "flags" would have to become a global
variable.
Group it with the options structure so that we reduce the number of
global variables we have overall.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 13 ++++++-------
1 file changed, 6 insertions(+), 7 deletions(-)
@@ -14,13 +14,12 @@ static struct opts_multi_pack_index {constchar*object_dir;unsignedlongbatch_size;intprogress;+unsignedflags;}opts;intcmd_multi_pack_index(intargc,constchar**argv,constchar*prefix){-unsignedflags=0;-staticstructoptionbuiltin_multi_pack_index_options[]={OPT_FILENAME(0,"object-dir",&opts.object_dir,N_("object directory containing set of packfile and pack-index pairs")),
@@ -40,7 +39,7 @@ int cmd_multi_pack_index(int argc, const char **argv,if(!opts.object_dir)opts.object_dir=get_object_directory();if(opts.progress)-flags|=MIDX_PROGRESS;+opts.flags|=MIDX_PROGRESS;if(argc==0)usage_with_options(builtin_multi_pack_index_usage,
@@ -55,16 +54,16 @@ int cmd_multi_pack_index(int argc, const char **argv,if(!strcmp(argv[0],"repack"))returnmidx_repack(the_repository,opts.object_dir,-(size_t)opts.batch_size,flags);+(size_t)opts.batch_size,opts.flags);if(opts.batch_size)die(_("--batch-size option is only for 'repack' subcommand"));if(!strcmp(argv[0],"write"))-returnwrite_midx_file(opts.object_dir,flags);+returnwrite_midx_file(opts.object_dir,opts.flags);if(!strcmp(argv[0],"verify"))-returnverify_midx_file(the_repository,opts.object_dir,flags);+returnverify_midx_file(the_repository,opts.object_dir,opts.flags);if(!strcmp(argv[0],"expire"))-returnexpire_midx_packs(the_repository,opts.object_dir,flags);+returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);die(_("unrecognized subcommand: %s"),argv[0]);}
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:51
Now that there is a shared 'flags' member in the options structure,
there is no need to keep track of whether to force progress or not,
since ultimately the decision of whether or not to show a progress meter
is controlled by a bit in the flags member.
Manipulate that bit directly, and drop the now-unnecessary 'progress'
field while we're at it.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 8 +++-----
1 file changed, 3 insertions(+), 5 deletions(-)
@@ -23,7 +22,7 @@ int cmd_multi_pack_index(int argc, const char **argv,staticstructoptionbuiltin_multi_pack_index_options[]={OPT_FILENAME(0,"object-dir",&opts.object_dir,N_("object directory containing set of packfile and pack-index pairs")),-OPT_BOOL(0,"progress",&opts.progress,N_("force progress reporting")),+OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),OPT_MAGNITUDE(0,"batch-size",&opts.batch_size,N_("during repack, collect pack-files of smaller size into a batch that is larger than this size")),OPT_END(),
@@ -31,15 +30,14 @@ int cmd_multi_pack_index(int argc, const char **argv,git_config(git_default_config,NULL);-opts.progress=isatty(2);+if(isatty(2))+opts.flags|=MIDX_PROGRESS;argc=parse_options(argc,argv,prefix,builtin_multi_pack_index_options,builtin_multi_pack_index_usage,0);if(!opts.object_dir)opts.object_dir=get_object_directory();-if(opts.progress)-opts.flags|=MIDX_PROGRESS;if(argc==0)usage_with_options(builtin_multi_pack_index_usage,
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:51
Handle sub-commands of the 'git multi-pack-index' builtin (e.g.,
"write", "repack", etc.) separately from one another. This allows
sub-commands with unique options, without forcing cmd_multi_pack_index()
to reject invalid combinations itself.
This comes at the cost of some duplication and boilerplate. Luckily, the
duplication is reduced to a minimum, since common options are shared
among sub-commands due to a suggestion by Ævar. (Sub-commands do have to
retain the common options, too, since this builtin accepts common
options on either side of the sub-command).
Roughly speaking, cmd_multi_pack_index() parses options (including
common ones), and stops at the first non-option, which is the
sub-command. It then dispatches to the appropriate sub-command, which
parses the remaining options (also including common options).
Unknown options are kept by the sub-commands in order to detect their
presence (and complain that too many arguments were given).
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 130 ++++++++++++++++++++++++++++++-------
1 file changed, 105 insertions(+), 25 deletions(-)
@@ -31,25 +47,98 @@ static struct opts_multi_pack_index {unsignedflags;}opts;-intcmd_multi_pack_index(intargc,constchar**argv,-constchar*prefix)+staticstructoptioncommon_opts[]={+OPT_FILENAME(0,"object-dir",&opts.object_dir,+N_("object directory containing set of packfile and pack-index pairs")),+OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),+OPT_END(),+};++staticstructoption*add_common_options(structoption*prev){-staticstructoptionbuiltin_multi_pack_index_options[]={-OPT_FILENAME(0,"object-dir",&opts.object_dir,-N_("object directory containing set of packfile and pack-index pairs")),-OPT_BIT(0,"progress",&opts.flags,N_("force progress reporting"),MIDX_PROGRESS),+returnparse_options_concat(common_opts,prev);+}++staticintcmd_multi_pack_index_write(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_write_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_write_usage,+options);++returnwrite_midx_file(opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_verify(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_verify_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_verify_usage,+options);++returnverify_midx_file(the_repository,opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_expire(intargc,constchar**argv)+{+structoption*options=common_opts;++argc=parse_options(argc,argv,NULL,+options,builtin_multi_pack_index_expire_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_expire_usage,+options);++returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);+}++staticintcmd_multi_pack_index_repack(intargc,constchar**argv)+{+structoption*options;+staticstructoptionbuiltin_multi_pack_index_repack_options[]={OPT_MAGNITUDE(0,"batch-size",&opts.batch_size,N_("during repack, collect pack-files of smaller size into a batch that is larger than this size")),OPT_END(),};+options=add_common_options(builtin_multi_pack_index_repack_options);++argc=parse_options(argc,argv,NULL,+options,+builtin_multi_pack_index_repack_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_multi_pack_index_repack_usage,+options);++FREE_AND_NULL(options);++returnmidx_repack(the_repository,opts.object_dir,+(size_t)opts.batch_size,opts.flags);+}++intcmd_multi_pack_index(intargc,constchar**argv,+constchar*prefix)+{+structoption*builtin_multi_pack_index_options=common_opts;+git_config(git_default_config,NULL);if(isatty(2))opts.flags|=MIDX_PROGRESS;argc=parse_options(argc,argv,prefix,builtin_multi_pack_index_options,-builtin_multi_pack_index_usage,0);+builtin_multi_pack_index_usage,+PARSE_OPT_STOP_AT_NON_OPTION);if(!opts.object_dir)opts.object_dir=get_object_directory();
@@ -58,25 +147,16 @@ int cmd_multi_pack_index(int argc, const char **argv,usage_with_options(builtin_multi_pack_index_usage,builtin_multi_pack_index_options);-if(argc>1){-die(_("too many arguments"));-return1;-}-trace2_cmd_mode(argv[0]);if(!strcmp(argv[0],"repack"))-returnmidx_repack(the_repository,opts.object_dir,-(size_t)opts.batch_size,opts.flags);-if(opts.batch_size)-die(_("--batch-size option is only for 'repack' subcommand"));--if(!strcmp(argv[0],"write"))-returnwrite_midx_file(opts.object_dir,opts.flags);-if(!strcmp(argv[0],"verify"))-returnverify_midx_file(the_repository,opts.object_dir,opts.flags);-if(!strcmp(argv[0],"expire"))-returnexpire_midx_packs(the_repository,opts.object_dir,opts.flags);--die(_("unrecognized subcommand: %s"),argv[0]);+returncmd_multi_pack_index_repack(argc,argv);+elseif(!strcmp(argv[0],"write"))+returncmd_multi_pack_index_write(argc,argv);+elseif(!strcmp(argv[0],"verify"))+returncmd_multi_pack_index_verify(argc,argv);+elseif(!strcmp(argv[0],"expire"))+returncmd_multi_pack_index_expire(argc,argv);+else+die(_("unrecognized subcommand: %s"),argv[0]);}
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:51
Factor out the usage message into pieces corresponding to each mode.
This avoids options specific to one sub-command from being shared with
another in the usage.
A subsequent commit will use these #define macros to have usage
variables for each sub-command without duplicating their contents.
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 17 ++++++++++++++++-
1 file changed, 16 insertions(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:51
When given a sub-command that it doesn't understand, 'git
multi-pack-index' dies with the following message:
$ git multi-pack-index bogus
fatal: unrecognized subcommand: bogus
Instead of 'die()'-ing, we can display the usage text, which is much
more helpful:
$ git.compile multi-pack-index bogus
error: unrecognized subcommand: bogus
usage: git multi-pack-index [<options>] write
or: git multi-pack-index [<options>] verify
or: git multi-pack-index [<options>] expire
or: git multi-pack-index [<options>] repack [--batch-size=<size>]
--object-dir <file> object directory containing set of packfile and pack-index pairs
--progress force progress reporting
While we're at it, clean up some duplication between the "no sub-command"
and "unrecognized sub-command" conditionals.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:52
Even before the recent refactoring, 'git multi-pack-index' calls
'trace2_cmd_mode()' before verifying that the sub-command is recognized.
Push this call down into the individual sub-commands so that we don't
enter a bogus command mode.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
Signed-off-by: Taylor Blau <redacted>
---
builtin/multi-pack-index.c | 10 ++++++++--
1 file changed, 8 insertions(+), 2 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:52
The 'read-midx' helper is used in places like t5319 to display basic
information about a multi-pack-index.
In the next patch, the MIDX writing machinery will learn a new way to
choose from which pack an object is selected when multiple copies of
that object exist.
To disambiguate which pack introduces an object so that this feature can
be tested, add a '--show-objects' option which displays additional
information about each object in the MIDX.
Signed-off-by: Taylor Blau <redacted>
---
t/helper/test-read-midx.c | 24 ++++++++++++++++++++----
1 file changed, 20 insertions(+), 4 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:04:52
When multiple packs in the multi-pack index contain the same object, the
MIDX machinery must make a choice about which pack it associates with
that object. Prior to this patch, the lowest-ordered[1] pack was always
selected.
Pack selection for duplicate objects is relatively unimportant today,
but it will become important for multi-pack bitmaps. This is because we
can only invoke the pack-reuse mechanism when all of the bits for reused
objects come from the reuse pack (in order to ensure that all reused
deltas can find their base objects in the same pack).
To encourage the pack selection process to prefer one pack over another
(the pack to be preferred is the one a caller would like to later use as
a reuse pack), introduce the concept of a "preferred pack". When
provided, the MIDX code will always prefer an object found in a
preferred pack over any other.
No format changes are required to store the preferred pack, since it
will be able to be inferred with a corresponding MIDX bitmap, by looking
up the pack associated with the object in the first bit position (this
ordering is described in detail in a subsequent commit).
[1]: the ordering is specified by MIDX internals; for our purposes we
can consider the "lowest ordered" pack to be "the one with the
most-recent mtime.
Signed-off-by: Taylor Blau <redacted>
---
Documentation/git-multi-pack-index.txt | 14 +++-
Documentation/technical/multi-pack-index.txt | 5 +-
builtin/multi-pack-index.c | 19 ++++-
builtin/repack.c | 2 +-
midx.c | 82 +++++++++++++++++---
midx.h | 2 +-
t/t5319-multi-pack-index.sh | 43 ++++++++++
7 files changed, 149 insertions(+), 18 deletions(-)
@@ -30,7 +31,16 @@ OPTIONS The following subcommands are available: write::- Write a new MIDX file.+ Write a new MIDX file. The following options are available for+ the `write` sub-command:+++--+ --preferred-pack=<pack>::+ Optionally specify the tie-breaking pack used when+ multiple packs contain the same object. If not given,+ ties are broken in favor of the pack with the lowest+ mtime.+-- verify:: Verify the contents of the MIDX file.
@@ -43,8 +43,9 @@ Design Details a change in format. - The MIDX keeps only one record per object ID. If an object appears- in multiple packfiles, then the MIDX selects the copy in the most-- recently modified packfile.+ in multiple packfiles, then the MIDX selects the copy in the+ preferred packfile, otherwise selecting from the most-recently+ modified packfile. - If there exist packfiles in the pack directory not registered in the MIDX, then those packfiles are loaded into the `packed_git`
@@ -500,6 +511,12 @@ static int midx_oid_compare(const void *_a, const void *_b)if(cmp)returncmp;+/* Sort objects in a preferred pack first when multiple copies exist. */+if(a->preferred>b->preferred)+return-1;+if(a->preferred<b->preferred)+return1;+if(a->pack_mtime>b->pack_mtime)return-1;elseif(a->pack_mtime<b->pack_mtime)
@@ -527,7 +544,8 @@ static int nth_midxed_pack_midx_entry(struct multi_pack_index *m,staticvoidfill_pack_entry(uint32_tpack_int_id,structpacked_git*p,uint32_tcur_object,-structpack_midx_entry*entry)+structpack_midx_entry*entry,+intpreferred){if(nth_packed_object_id(&entry->oid,p,cur_object)<0)die(_("failed to locate object %d in packfile"),cur_object);
@@ -234,6 +234,49 @@ test_expect_success 'warn on improper hash version' ')'+test_expect_success'midx picks objects from preferred pack''+test_when_finishedrm-rfpreferred.git&&+gitinit--barepreferred.git&&+(+cdpreferred.git&&++a=$(echo"a"|githash-object-w--stdin)&&+b=$(echo"b"|githash-object-w--stdin)&&+c=$(echo"c"|githash-object-w--stdin)&&++# Set up two packs, duplicating the object "B" at different+# offsets.+#+# Note that the "BC" pack (the one we choose as preferred) sorts+# lexically after the "AB" pack, meaning that omitting the+# --preferred-pack argument would cause this test to fail (since+# the MIDX code would select the copy of "b" in the "AB" pack).+gitpack-objectsobjects/pack/test-AB<<-EOF&&+$a+$b+EOF+bc=$(gitpack-objectsobjects/pack/test-BC<<-EOF+$b+$c+EOF+)&&++gitmulti-pack-index--object-dir=objects\+write--preferred-pack=test-BC-$bc.idx2>err&&+test_must_be_emptyerr&&++echohi&&+test-toolread-midx--show-objectsobjects>out&&++ofs=$(gitshow-index<objects/pack/test-BC-$bc.idx|grep$b|+cut-d" "-f1)&&+printf"%s %s\tobjects/pack/test-BC-%s.pack\n"\+"$b""$ofs""$bc">expect&&+grep^$bout>actual&&++test_cmpexpectactual+)+' test_expect_success'verify multi-pack-index success''gitmulti-pack-indexverify--object-dir=$objdir
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:22
write_midx_internal() uses a hashfile to write the multi-pack index, but
discards its checksum. This makes sense, since nothing that takes place
after writing the MIDX cares about its checksum.
That is about to change in a subsequent patch, when the optional
reverse index corresponding to the MIDX will want to include the MIDX's
checksum.
Store the checksum of the MIDX in preparation for that.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:22
A subsequent patch will need to refer back to 'midx_name' later on in
the function. In fact, this variable is already free()'d later on, so
this makes the later free() no longer redundant.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 1 -
1 file changed, 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
In a subsequent commit, pack-revindex.c will become responsible for
sorting a list of objects in the "MIDX pack order" (which will be
defined in the following patch). To do so, it will need to be know the
pack identifier and offset within that pack for each object in the MIDX.
The MIDX code already has functions for doing just that
(nth_midxed_offset() and nth_midxed_pack_int_id()), but they are
statically declared.
Since there is no reason that they couldn't be exposed publicly, and
because they are already doing exactly what the caller in
pack-revindex.c will want, expose them publicly so that they can be
reused there.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 4 ++--
midx.h | 2 ++
2 files changed, 4 insertions(+), 2 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
Existing callers provide the reverse index code with an array of 'struct
pack_idx_entry *'s, which is then sorted by pack order (comparing the
offsets of each object within the pack).
Prepare for the multi-pack index to write a .rev file by providing a way
to write the reverse index without an array of pack_idx_entry (which the
MIDX code does not have).
Instead, callers can invoke 'write_rev_index_positions()', which takes
an array of uint32_t's. The ith entry in this array specifies the ith
object's (in index order) position within the pack (in pack order).
Expose this new function for use in a later patch, and rewrite the
existing write_rev_file() in terms of this new function.
Signed-off-by: Taylor Blau <redacted>
---
pack-write.c | 36 +++++++++++++++++++++++++-----------
pack.h | 1 +
2 files changed, 26 insertions(+), 11 deletions(-)
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
As a prerequisite to implementing multi-pack bitmaps, motivate and
describe the format and ordering of the multi-pack reverse index.
The subsequent patch will implement reading this format, and the patch
after that will implement writing it while producing a multi-pack index.
Co-authored-by: Jeff King [off-list ref]
Signed-off-by: Jeff King <redacted>
Signed-off-by: Taylor Blau <redacted>
---
Documentation/technical/pack-format.txt | 83 +++++++++++++++++++++++++
1 file changed, 83 insertions(+)
@@ -379,3 +379,86 @@ CHUNK DATA: TRAILER: Index checksum of the above contents.++== multi-pack-index reverse indexes++Similar to the pack-based reverse index, the multi-pack index can also+be used to generate a reverse index.++Instead of mapping between offset, pack-, and index position, this+reverse index maps between an object's position within the MIDX, and+that object's position within a pseudo-pack that the MIDX describes+(i.e., the ith entry of the multi-pack reverse index holds the MIDX+position of ith object in pseudo-pack order).++To clarify the difference between these orderings, consider a multi-pack+reachability bitmap (which does not yet exist, but is what we are+building towards here). Each bit needs to correspond to an object in the+MIDX, and so we need an efficient mapping from bit position to MIDX+position.++One solution is to let bits occupy the same position in the oid-sorted+index stored by the MIDX. But because oids are effectively random, their+resulting reachability bitmaps would have no locality, and thus compress+poorly. (This is the reason that single-pack bitmaps use the pack+ordering, and not the .idx ordering, for the same purpose.)++So we'd like to define an ordering for the whole MIDX based around+pack ordering, which has far better locality (and thus compresses more+efficiently). We can think of a pseudo-pack created by the concatenation+of all of the packs in the MIDX. E.g., if we had a MIDX with three packs+(a, b, c), with 10, 15, and 20 objects respectively, we can imagine an+ordering of the objects like:++ |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|++where the ordering of the packs is defined by the MIDX's pack list,+and then the ordering of objects within each pack is the same as the+order in the actual packfile.++Given the list of packs and their counts of objects, you can+naïvely reconstruct that pseudo-pack ordering (e.g., the object at+position 27 must be (c,1) because packs "a" and "b" consumed 25 of the+slots). But there's a catch. Objects may be duplicated between packs, in+which case the MIDX only stores one pointer to the object (and thus we'd+want only one slot in the bitmap).++Callers could handle duplicates themselves by reading objects in order+of their bit-position, but that's linear in the number of objects, and+much too expensive for ordinary bitmap lookups. Building a reverse index+solves this, since it is the logical inverse of the index, and that+index has already removed duplicates. But, building a reverse index on+the fly can be expensive. Since we already have an on-disk format for+pack-based reverse indexes, let's reuse it for the MIDX's pseudo-pack,+too.++Objects from the MIDX are ordered as follows to string together the+pseudo-pack. Let `pack(o)` return the pack from which `o` was selected+by the MIDX, and define an ordering of packs based on their numeric ID+(as stored by the MIDX). Let `offset(o)` return the object offset of `o`+within `pack(o)`. Then, compare `o1` and `o2` as follows:++ - If one of `pack(o1)` and `pack(o2)` is preferred and the other+ is not, then the preferred one sorts first.+++(This is a detail that allows the MIDX bitmap to determine which+pack should be used by the pack-reuse mechanism, since it can ask+the MIDX for the pack containing the object at bit position 0).++ - If `pack(o1) ≠ pack(o2)`, then sort the two objects in descending+ order based on the pack ID.++ - Otherwise, `pack(o1) = pack(o2)`, and the objects are sorted in+ pack-order (i.e., `o1` sorts ahead of `o2` exactly when `offset(o1)+ < offset(o2)`).++In short, a MIDX's pseudo-pack is the de-duplicated concatenation of+objects in packs stored by the MIDX, laid out in pack order, and the+packs arranged in MIDX order (with the preferred pack coming first).++Finally, note that the MIDX's reverse index is not stored as a chunk in+the multi-pack-index itself. This is done because the reverse index+includes the checksum of the pack or MIDX to which it belongs, which+makes it impossible to write in the MIDX. To avoid races when rewriting+the MIDX, a MIDX reverse index includes the MIDX's checksum in its+filename (e.g., `multi-pack-index-xyz.rev`).
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
Implement reading for multi-pack reverse indexes, as described in the
previous patch.
Note that these functions don't yet have any callers, and won't until
multi-pack reachability bitmaps are introduced in a later patch series.
In the meantime, this patch implements some of the infrastructure
necessary to support multi-pack bitmaps.
There are three new functions exposed by the revindex API:
- load_midx_revindex(): loads the reverse index corresponding to the
given multi-pack index.
- midx_to_pack_pos() and pack_pos_to_midx(): these convert between the
multi-pack index and pseudo-pack order.
load_midx_revindex() and pack_pos_to_midx() are both relatively
straightforward.
load_midx_revindex() needs a few functions to be exposed from the midx
API. One to get the checksum of a midx, and another to get the .rev's
filename. Similar to recent changes in the packed_git struct, three new
fields are added to the multi_pack_index struct: one to keep track of
the size, one to keep track of the mmap'd pointer, and another to point
past the header and at the reverse index's data.
pack_pos_to_midx() simply reads the corresponding entry out of the
table.
midx_to_pack_pos() is the trickiest, since it needs to find an object's
position in the psuedo-pack order, but that order can only be recovered
in the .rev file itself. This mapping can be implemented with a binary
search, but note that the thing we're binary searching over isn't an
array of values, but rather a permuted order of those values.
So, when comparing two items, it's helpful to keep in mind the
difference. Instead of a traditional binary search, where you are
comparing two things directly, here we're comparing a (pack, offset)
tuple with an index into the multi-pack index. That index describes
another (pack, offset) tuple, and it is _those_ two tuples that are
compared.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 11 +++++
midx.h | 6 +++
pack-revindex.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++
pack-revindex.h | 53 ++++++++++++++++++++
packfile.c | 3 ++
5 files changed, 199 insertions(+)
@@ -293,6 +294,43 @@ int load_pack_revindex(struct packed_git *p)return-1;}+intload_midx_revindex(structmulti_pack_index*m)+{+char*revindex_name;+intret;+if(m->revindex_data)+return0;++revindex_name=get_midx_rev_filename(m);++ret=load_revindex_from_disk(revindex_name,+m->num_objects,+&m->revindex_map,+&m->revindex_len);+if(ret)+gotocleanup;++m->revindex_data=(constuint32_t*)((constchar*)m->revindex_map+RIDX_HEADER_SIZE);++cleanup:+free(revindex_name);+returnret;+}++intclose_midx_revindex(structmulti_pack_index*m)+{+if(!m||!m->revindex_map)+return0;++munmap((void*)m->revindex_map,m->revindex_len);++m->revindex_map=NULL;+m->revindex_data=NULL;+m->revindex_len=0;++return0;+}+intoffset_to_pack_pos(structpacked_git*p,off_tofs,uint32_t*pos){unsignedlo,hi;
@@ -347,3 +385,91 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)elsereturnnth_packed_object_offset(p,pack_pos_to_index(p,pos));}++uint32_tpack_pos_to_midx(structmulti_pack_index*m,uint32_tpos)+{+if(!m->revindex_data)+BUG("pack_pos_to_midx: reverse index not yet loaded");+if(m->num_objects<=pos)+BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32,pos);+returnget_be32(m->revindex_data+pos);+}++structmidx_pack_key{+uint32_tpack;+off_toffset;++uint32_tpreferred_pack;+structmulti_pack_index*midx;+};++staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb)+{+conststructmidx_pack_key*key=va;+structmulti_pack_index*midx=key->midx;++uint32_tversus=pack_pos_to_midx(midx,(uint32_t*)vb-(constuint32_t*)midx->revindex_data);+uint32_tversus_pack=nth_midxed_pack_int_id(midx,versus);+off_tversus_offset;++uint32_tkey_preferred=key->pack==key->preferred_pack;+uint32_tversus_preferred=versus_pack==key->preferred_pack;++/*+*First,comparethepreferred-ness,notingthatthepreferredpack+*comesfirst.+*/+if(key_preferred&&!versus_preferred)+return-1;+elseif(!key_preferred&&versus_preferred)+return1;++/* Then, break ties first by comparing the pack IDs. */+if(key->pack<versus_pack)+return-1;+elseif(key->pack>versus_pack)+return1;++/* Finally, break ties by comparing offsets within a pack. */+versus_offset=nth_midxed_offset(midx,versus);+if(key->offset<versus_offset)+return-1;+elseif(key->offset>versus_offset)+return1;++return0;+}++intmidx_to_pack_pos(structmulti_pack_index*m,uint32_tat,uint32_t*pos)+{+structmidx_pack_keykey;+uint32_t*found;++if(!m->revindex_data)+BUG("midx_to_pack_pos: reverse index not yet loaded");+if(m->num_objects<=at)+BUG("midx_to_pack_pos: out-of-bounds object at %"PRIu32,at);++key.pack=nth_midxed_pack_int_id(m,at);+key.offset=nth_midxed_offset(m,at);+key.midx=m;+/*+*Thepreferredpacksortsfirst,sodetermineitsidentifierby+*lookingatthefirstobjectinpseudo-packorder.+*+*Notethatifno--preferred-packisexplicitlygivenwhenwritinga+*multi-packindex,thenwhicheverpackhasthelowestidentifier+*implicitlyispreferred(andincludesallitsobjects,sincetiesare+*brokenfirstbypackidentifier).+*/+key.preferred_pack=nth_midxed_pack_int_id(m,pack_pos_to_midx(m,0));++found=bsearch(&key,m->revindex_data,m->num_objects,+sizeof(*m->revindex_data),midx_pack_order_cmp);++if(!found)+returnerror("bad offset for revindex");++*pos=found-m->revindex_data;+return0;+}
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
From: Jeff King <redacted>
There is a lot of pointer dereferencing in the pre-image version of
'midx_pack_order_cmp()', which this patch gets rid of.
Instead of comparing the pack preferred-ness and then the pack id, both
of these checks are done at the same time by using the high-order bit of
the pack id to represent whether it's preferred. Then the pack id and
offset are compared as usual.
This produces the same result so long as there are less than 2^31 packs,
which seems like a likely assumption to make in practice.
Signed-off-by: Jeff King <redacted>
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 55 +++++++++++++++++++++++++++++--------------------------
1 file changed, 29 insertions(+), 26 deletions(-)
@@ -818,46 +818,49 @@ static int write_midx_large_offsets(struct hashfile *f,return0;}-staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb,void*_ctx)+structmidx_pack_order_data{+uint32_tnr;+uint32_tpack;+off_toffset;+};++staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb){-structwrite_midx_context*ctx=_ctx;--structpack_midx_entry*a=&ctx->entries[*(constuint32_t*)va];-structpack_midx_entry*b=&ctx->entries[*(constuint32_t*)vb];--uint32_tperm_a=ctx->pack_perm[a->pack_int_id];-uint32_tperm_b=ctx->pack_perm[b->pack_int_id];--/* Sort objects in the preferred pack ahead of any others. */-if(a->preferred>b->preferred)+conststructmidx_pack_order_data*a=va,*b=vb;+if(a->pack<b->pack)return-1;-if(a->preferred<b->preferred)+elseif(a->pack>b->pack)return1;--/* Then, order objects by which packs they appear in. */-if(perm_a<perm_b)+elseif(a->offset<b->offset)return-1;-if(perm_a>perm_b)+elseif(a->offset>b->offset)return1;--/* Then, disambiguate by their offset within each pack. */-if(a->offset<b->offset)-return-1;-if(a->offset>b->offset)-return1;--return0;+else+return0;}staticuint32_t*midx_pack_order(structwrite_midx_context*ctx){+structmidx_pack_order_data*data;uint32_t*pack_order;uint32_ti;+ALLOC_ARRAY(data,ctx->entries_nr);+for(i=0;i<ctx->entries_nr;i++){+structpack_midx_entry*e=&ctx->entries[i];+data[i].nr=i;+data[i].pack=ctx->pack_perm[e->pack_int_id];+if(!e->preferred)+data[i].pack|=(1U<<31);+data[i].offset=e->offset;+}++QSORT(data,ctx->entries_nr,midx_pack_order_cmp);+ALLOC_ARRAY(pack_order,ctx->entries_nr);for(i=0;i<ctx->entries_nr;i++)-pack_order[i]=i;-QSORT_S(pack_order,ctx->entries_nr,midx_pack_order_cmp,ctx);+pack_order[i]=data[i].nr;+free(data);returnpack_order;}
From: Taylor Blau <hidden> Date: 2021-03-30 15:05:23
Implement the writing half of multi-pack reverse indexes. This is
nothing more than the format describe a few patches ago, with a new set
of helper functions that will be used to clear out stale .rev files
corresponding to old MIDXs.
Unfortunately, a very similar comparison function as the one implemented
recently in pack-revindex.c is reimplemented here, this time accepting a
MIDX-internal type. An effort to DRY these up would create more
indirection and overhead than is necessary, so it isn't pursued here.
Currently, there are no callers which pass the MIDX_WRITE_REV_INDEX
flag, meaning that this is all dead code. But, that won't be the case
for long, since subsequent patches will introduce the multi-pack bitmap,
which will begin passing this field.
(In midx.c:write_midx_internal(), the two adjacent if statements share a
conditional, but are written separately since the first one will
eventually also handle the MIDX_WRITE_BITMAP flag, which does not yet
exist.)
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
midx.h | 1 +
2 files changed, 116 insertions(+)
@@ -816,6 +818,70 @@ static int write_midx_large_offsets(struct hashfile *f,return0;}+staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb,void*_ctx)+{+structwrite_midx_context*ctx=_ctx;++structpack_midx_entry*a=&ctx->entries[*(constuint32_t*)va];+structpack_midx_entry*b=&ctx->entries[*(constuint32_t*)vb];++uint32_tperm_a=ctx->pack_perm[a->pack_int_id];+uint32_tperm_b=ctx->pack_perm[b->pack_int_id];++/* Sort objects in the preferred pack ahead of any others. */+if(a->preferred>b->preferred)+return-1;+if(a->preferred<b->preferred)+return1;++/* Then, order objects by which packs they appear in. */+if(perm_a<perm_b)+return-1;+if(perm_a>perm_b)+return1;++/* Then, disambiguate by their offset within each pack. */+if(a->offset<b->offset)+return-1;+if(a->offset>b->offset)+return1;++return0;+}++staticuint32_t*midx_pack_order(structwrite_midx_context*ctx)+{+uint32_t*pack_order;+uint32_ti;++ALLOC_ARRAY(pack_order,ctx->entries_nr);+for(i=0;i<ctx->entries_nr;i++)+pack_order[i]=i;+QSORT_S(pack_order,ctx->entries_nr,midx_pack_order_cmp,ctx);++returnpack_order;+}++staticvoidwrite_midx_reverse_index(char*midx_name,unsignedchar*midx_hash,+structwrite_midx_context*ctx)+{+structstrbufbuf=STRBUF_INIT;+constchar*tmp_file;++strbuf_addf(&buf,"%s-%s.rev",midx_name,hash_to_hex(midx_hash));++tmp_file=write_rev_file_order(NULL,ctx->pack_order,ctx->entries_nr,+midx_hash,WRITE_REV);++if(finalize_object_file(tmp_file,buf.buf))+die(_("cannot store reverse index file"));++strbuf_release(&buf);+}++staticvoidclear_midx_files_ext(structrepository*r,constchar*ext,+unsignedchar*keep_hash);+staticintwrite_midx_internal(constchar*object_dir,structmulti_pack_index*m,structstring_list*packs_to_drop,constchar*preferred_pack_name,
From: Jeff King <hidden> Date: 2021-03-30 15:46:19
On Tue, Mar 30, 2021 at 11:03:44AM -0400, Taylor Blau wrote:
Here is another reroll of my series to implement a reverse index in
preparation for multi-pack reachability bitmaps.
Thanks, this addresses all of my comments from the last round.
This reroll differs only in the feedback I incorporated from Peff's review. They
are mostly cosmetic; the most substantial change being that the --preferred-pack
code now uses bsearch() to locate the name of the preferred pack (instead of
implementing a binary search itself).
Yeah, I read over this part carefully, since it's actual new code (that
isn't run yet!), but I think it is correct.
One minor observation:
I'd probably have just skipped show-index entirely, and done:
grep "^$b .* objects/pack/test-BC" actual
which expresses the intent ($b came from that pack). But I don't mind
the more exacting version (and certainly it is not worth a re-roll even
if you prefer mine).
-Peff
From: Taylor Blau <hidden> Date: 2021-03-30 15:50:43
On Tue, Mar 30, 2021 at 11:45:19AM -0400, Jeff King wrote:
quoted
This reroll differs only in the feedback I incorporated from Peff's review. They
are mostly cosmetic; the most substantial change being that the --preferred-pack
code now uses bsearch() to locate the name of the preferred pack (instead of
implementing a binary search itself).
Yeah, I read over this part carefully, since it's actual new code (that
isn't run yet!), but I think it is correct.
Thankfully this does have coverage via any test that passes
`--preferred-pack` (like the one below).
I'd probably have just skipped show-index entirely, and done:
grep "^$b .* objects/pack/test-BC" actual
which expresses the intent ($b came from that pack). But I don't mind
the more exacting version (and certainly it is not worth a re-roll even
if you prefer mine).
I originally wrote it that way, but decided to write both expect and
actual to make debugging easier if this ever regresses. Not like it's
that hard to run the test-tool yourself in the trash directory, but
having a snapshot of that object from the MIDX's perspective might make
things a little easier.
Anyway, I agree with you that it doesn't probably matter a ton either
way.
From: Jeff King <hidden> Date: 2021-03-30 16:02:54
On Tue, Mar 30, 2021 at 11:49:59AM -0400, Taylor Blau wrote:
On Tue, Mar 30, 2021 at 11:45:19AM -0400, Jeff King wrote:
quoted
quoted
This reroll differs only in the feedback I incorporated from Peff's review. They
are mostly cosmetic; the most substantial change being that the --preferred-pack
code now uses bsearch() to locate the name of the preferred pack (instead of
implementing a binary search itself).
Yeah, I read over this part carefully, since it's actual new code (that
isn't run yet!), but I think it is correct.
Thankfully this does have coverage via any test that passes
`--preferred-pack` (like the one below).
Oh right, I forgot this was touching that early part. So now I'm doubly
confident in it.
-Peff
From: Taylor Blau <hidden> Date: 2021-04-01 00:33:03
Junio,
On Tue, Mar 30, 2021 at 11:04:11AM -0400, Taylor Blau wrote:
I accidentally left a stray debugging line in here, and managed to skip
over it when reading the range-diff. It's right...
@@ -234,6 +234,49 @@ test_expect_success 'warn on improper hash version' ')'+test_expect_success'midx picks objects from preferred pack''+test_when_finishedrm-rfpreferred.git&&+gitinit--barepreferred.git&&+(+cdpreferred.git&&++a=$(echo"a"|githash-object-w--stdin)&&+b=$(echo"b"|githash-object-w--stdin)&&+c=$(echo"c"|githash-object-w--stdin)&&++# Set up two packs, duplicating the object "B" at different+# offsets.+#+# Note that the "BC" pack (the one we choose as preferred) sorts+# lexically after the "AB" pack, meaning that omitting the+# --preferred-pack argument would cause this test to fail (since+# the MIDX code would select the copy of "b" in the "AB" pack).+gitpack-objectsobjects/pack/test-AB<<-EOF&&+$a+$b+EOF+bc=$(gitpack-objectsobjects/pack/test-BC<<-EOF+$b+$c+EOF+)&&++gitmulti-pack-index--object-dir=objects\+write--preferred-pack=test-BC-$bc.idx2>err&&+test_must_be_emptyerr&&++echohi&&
...here. Would you mind fixing it up locally before applying this to
next?
Sorry for the trouble.
Thanks,
Taylor