| Message ID | c52d7e7b27a9add4f58b8334db4fe4498af1c90f.1701198172.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | pack-objects: multi-pack verbatim reuse | expand |
On Tue, Nov 28, 2023 at 02:08:08PM -0500, Taylor Blau wrote: > When a multi-pack bitmap is used to implement verbatim pack reuse (that > is, when verbatim chunks from an on-disk packfile are copied > directly[^1]), it does so by using its "preferred pack" as the source > for pack-reuse. > > This allows repositories to pack the majority of their objects into a > single (often large) pack, and then use it as the single source for > verbatim pack reuse. This increases the amount of objects that are > reused verbatim (and consequently, decrease the amount of time it takes > to generate many packs). But this performance comes at a cost, which is > that the preferred packfile must pace its growth with that of the entire > repository in order to maintain the utility of verbatim pack reuse. > > As repositories grow beyond what we can reasonably store in a single > packfile, the utility of verbatim pack reuse diminishes. Or, at the very > least, it becomes increasingly more expensive to maintain as the pack > grows larger and larger. > > It would be beneficial to be able to perform this same optimization over > multiple packs, provided some modest constraints (most importantly, that > the set of packs eligible for verbatim reuse are disjoint with respect > to the objects that they contain). > > If we assume that the packs which we treat as candidates for verbatim > reuse are disjoint with respect to their objects, we need to make only > modest modifications to the verbatim pack-reuse code itself. Most > notably, we need to remove the assumption that the bits in the > reachability bitmap corresponding to objects from the single reuse pack > begin at the first bit position. > > Future patches will unwind these assumptions and reimplement their > existing functionality as special cases of the more general assumptions > (e.g. that reuse bits can start anywhere within the bitset, but happen > to start at 0 for all existing cases). > > This patch does not yet relax any of those assumptions. Instead, it > implements a foundational data-structure, the "Disjoint Packs" (`DISP`) > chunk of the multi-pack index. The `DISP` chunk's contents are described > in detail here. Importantly, the `DISP` chunk contains information to > map regions of a multi-pack index's reachability bitmap to the packs > whose objects they represent. > > For now, this chunk is only written, not read (outside of the test-tool > used in this patch to test the new chunk's behavior). Future patches > will begin to make use of this new chunk. > > This patch implements reading (though no callers outside of the above > one perform any reading) and writing this new chunk. It also extends the > `--stdin-packs` format used by the `git multi-pack-index write` builtin > to be able to designate that a given pack is to be marked as "disjoint" > by prefixing it with a '+' character. > > [^1]: Modulo patching any `OFS_DELTA`'s that cross over a region of the > pack that wasn't used verbatim. > > Signed-off-by: Taylor Blau <me@ttaylorr.com> > --- > Documentation/git-multi-pack-index.txt | 4 + > Documentation/gitformat-pack.txt | 109 +++++++++++++++++++++++ > builtin/multi-pack-index.c | 10 ++- > midx.c | 116 ++++++++++++++++++++++--- > midx.h | 5 ++ > pack-bitmap.h | 9 ++ > t/helper/test-read-midx.c | 31 ++++++- > t/t5319-multi-pack-index.sh | 58 +++++++++++++ > 8 files changed, 325 insertions(+), 17 deletions(-) > > diff --git a/Documentation/git-multi-pack-index.txt b/Documentation/git-multi-pack-index.txt > index 3696506eb3..d130e65b28 100644 > --- a/Documentation/git-multi-pack-index.txt > +++ b/Documentation/git-multi-pack-index.txt > @@ -49,6 +49,10 @@ write:: > --stdin-packs:: > Write a multi-pack index containing only the set of > line-delimited pack index basenames provided over stdin. > + Lines beginning with a '+' character (followed by the > + pack index basename as before) have their pack marked as > + "disjoint". See the "`DISP` chunk and disjoint packs" > + section in linkgit:gitformat-pack[5] for more. > > --refs-snapshot=<path>:: > With `--bitmap`, optionally specify a file which > diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt > index 9fcb29a9c8..658682ddd5 100644 > --- a/Documentation/gitformat-pack.txt > +++ b/Documentation/gitformat-pack.txt > @@ -396,6 +396,22 @@ CHUNK DATA: > is padded at the end with between 0 and 3 NUL bytes to make the > chunk size a multiple of 4 bytes. > > + Disjoint Packfiles (ID: {'D', 'I', 'S', 'P'}) > + Stores a table of three 4-byte unsigned integers in network order. > + Each table entry corresponds to a single pack (in the order that > + they appear above in the `PNAM` chunk). The values for each table > + entry are as follows: > + - The first bit position (in psuedo-pack order, see below) to s/psuedo/pseudo/ > + contain an object from that pack. > + - The number of bits whose objects are selected from that pack. > + - A "meta" value, whose least-significant bit indicates whether or > + not the pack is disjoint with respect to other packs. The > + remaining bits are unused. > + Two packs are "disjoint" with respect to one another when they have > + disjoint sets of objects. In other words, any object found in a pack > + contained in the set of disjoint packfiles is guaranteed to be > + uniquely located among those packs. > + > OID Fanout (ID: {'O', 'I', 'D', 'F'}) > The ith entry, F[i], stores the number of OIDs with first > byte at most i. Thus F[255] stores the total > @@ -509,6 +525,99 @@ packs arranged in MIDX order (with the preferred pack coming first). > The MIDX's reverse index is stored in the optional 'RIDX' chunk within > the MIDX itself. > > +=== `DISP` chunk and disjoint packs > + > +The Disjoint Packfiles (`DISP`) chunk encodes additional information > +about the objects in the multi-pack index's reachability bitmap. Recall > +that objects from the MIDX are arranged in "pseudo-pack" order (see: The colon feels a bit out-of-place here, so: s/see:/see/ > +above) for reachability bitmaps. > + > +From the example above, suppose we have packs "a", "b", and "c", with > +10, 15, and 20 objects, respectively. In pseudo-pack order, those would > +be arranged as follows: > + > + |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19| > + > +When working with single-pack bitmaps (or, equivalently, multi-pack > +reachability bitmaps without any packs marked as disjoint), > +linkgit:git-pack-objects[1] performs ``verbatim'' reuse, attempting to > +reuse chunks of the existing packfile instead of adding objects to the > +packing list. I'm not sure I full understand this paragraph. In the context of a single pack bitmap it's clear enough. But I stumbled over the MIDX case, because here we potentially have multiple packfiles, so it's not exactly clear to me what you refer to with "the existing packfile" in that case. I'd think that we perform verbatim reuse of the preferred packfile, right? If so, we might want to make that a bit more explicit. > +When a chunk of bytes are reused from an existing pack, any objects s/are/is/, as it refers to the single chunk and not the plural bytes. > +contained therein do not need to be added to the packing list, saving > +memory and CPU time. But a chunk from an existing packfile can only be > +reused when the following conditions are met: > + > + - The chunk contains only objects which were requested by the caller > + (i.e. does not contain any objects which the caller didn't ask for > + explicitly or implicitly). > + > + - All objects stored as offset- or reference-deltas also include their > + base object in the resulting pack. > + > +Additionally, packfiles many not contain more than one copy of any given s/many/may > +object. This introduces an additional constraint over the set of packs > +we may want to reuse. The most straightforward approach is to mandate > +that the set of packs is disjoint with respect to the set of objects > +contained in each pack. In other words, for each object `o` in the union > +of all objects stored by the disjoint set of packs, `o` is contained in > +exactly one pack from the disjoint set. Is this a property that usually holds for our normal housekeeping, or does it require careful managing by the user/admin? How about geometric repacking? > +One alternative design choice for multi-pack reuse might instead involve > +imposing a chunk-level constraint that allows packs in the reusable set > +to contain multiple copies across different packs, but restricts each > +chunk against including more than one copy of such an object. This is in > +theory possible to implement, but significantly more complicated than > +forcing packs themselves to be disjoint. Most notably, we would have to > +keep track of which objects have already been sent during verbatim > +pack-reuse, defeating the main purpose of verbatim pack reuse (that we > +don't have to keep track of individual objects). > + > +The `DISP` chunk encodes the necessary information in order to implement > +multi-pack reuse over a disjoint set of packs as described above. > +Specifically, the `DISP` chunk encodes three pieces of information (all > +32-bit unsigned integers in network byte-order) for each packfile `p` > +that is stored in the MIDX, as follows: > + > +`bitmap_pos`:: The first bit position (in pseudo-pack order) in the > + multi-pack index's reachability bitmap occupied by an object from `p`. > + > +`bitmap_nr`:: The number of bit positions (including the one at > + `bitmap_pos`) that encode objects from that pack `p`. > + > +`disjoint`:: Metadata, including whether or not the pack `p` is > + ``disjoint''. The least significant bit stores whether or not the pack > + is disjoint. The remaining bits are reserved for future use. > + > +For example, the `DISP` chunk corresponding to the above example (with > +packs ``a'', ``b'', and ``c'') would look like: > + > +[cols="1,2,2,2"] > +|=== > +| |`bitmap_pos` |`bitmap_nr` |`disjoint` > + > +|packfile ``a'' > +|`0` > +|`10` > +|`0x1` > + > +|packfile ``b'' > +|`10` > +|`15` > +|`0x1` > + > +|packfile ``c'' > +|`25` > +|`20` > +|`0x1` > +|=== > + > +With these constraints and information in place, we can treat each > +packfile marked as disjoint as individually reusable in the same fashion > +as verbatim pack reuse is performed on individual packs prior to the > +implementation of the `DISP` chunk. > + > == cruft packs > > The cruft packs feature offer an alternative to Git's traditional mechanism of > diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c > index a72aebecaa..0f1dd4651d 100644 > --- a/builtin/multi-pack-index.c > +++ b/builtin/multi-pack-index.c > @@ -106,11 +106,17 @@ static int git_multi_pack_index_write_config(const char *var, const char *value, > return 0; > } > > +#define DISJOINT ((void*)(uintptr_t)1) > + > static void read_packs_from_stdin(struct string_list *to) > { > struct strbuf buf = STRBUF_INIT; > - while (strbuf_getline(&buf, stdin) != EOF) > - string_list_append(to, buf.buf); > + while (strbuf_getline(&buf, stdin) != EOF) { > + if (*buf.buf == '+') > + string_list_append(to, buf.buf + 1)->util = DISJOINT; > + else > + string_list_append(to, buf.buf); > + } > string_list_sort(to); > > strbuf_release(&buf); > diff --git a/midx.c b/midx.c > index 591b3c636e..f55020072f 100644 > --- a/midx.c > +++ b/midx.c > @@ -33,6 +33,7 @@ > > #define MIDX_CHUNK_ALIGNMENT 4 > #define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */ > +#define MIDX_CHUNKID_DISJOINTPACKS 0x44495350 /* "DISP" */ > #define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */ > #define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */ > #define MIDX_CHUNKID_OBJECTOFFSETS 0x4f4f4646 /* "OOFF" */ > @@ -182,6 +183,9 @@ struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local > > pair_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS, &m->chunk_large_offsets, > &m->chunk_large_offsets_len); > + pair_chunk(cf, MIDX_CHUNKID_DISJOINTPACKS, > + (const unsigned char **)&m->chunk_disjoint_packs, > + &m->chunk_disjoint_packs_len); > > if (git_env_bool("GIT_TEST_MIDX_READ_RIDX", 1)) > pair_chunk(cf, MIDX_CHUNKID_REVINDEX, &m->chunk_revindex, > @@ -275,6 +279,23 @@ int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t > return 0; > } > > +int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, > + struct bitmapped_pack *bp, uint32_t pack_int_id) > +{ > + if (!m->chunk_disjoint_packs) > + return error(_("MIDX does not contain the DISP chunk")); > + > + if (prepare_midx_pack(r, m, pack_int_id)) > + return error(_("could not load disjoint pack %"PRIu32), pack_int_id); > + > + bp->p = m->packs[pack_int_id]; > + bp->bitmap_pos = get_be32(m->chunk_disjoint_packs + 3 * pack_int_id); > + bp->bitmap_nr = get_be32(m->chunk_disjoint_packs + 3 * pack_int_id + 1); > + bp->disjoint = !!get_be32(m->chunk_disjoint_packs + 3 * pack_int_id + 2); > + > + return 0; > +} > + > int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, uint32_t *result) > { > return bsearch_hash(oid->hash, m->chunk_oid_fanout, m->chunk_oid_lookup, > @@ -457,11 +478,18 @@ static size_t write_midx_header(struct hashfile *f, > return MIDX_HEADER_SIZE; > } > > +#define BITMAP_POS_UNKNOWN (~((uint32_t)0)) > + > struct pack_info { > uint32_t orig_pack_int_id; > char *pack_name; > struct packed_git *p; > - unsigned expired : 1; > + > + uint32_t bitmap_pos; > + uint32_t bitmap_nr; > + > + unsigned expired : 1, > + disjoint : 1; > }; > > static void fill_pack_info(struct pack_info *info, > @@ -473,6 +501,7 @@ static void fill_pack_info(struct pack_info *info, > info->orig_pack_int_id = orig_pack_int_id; > info->pack_name = pack_name; > info->p = p; > + info->bitmap_pos = BITMAP_POS_UNKNOWN; > } > > static int pack_info_compare(const void *_a, const void *_b) > @@ -516,6 +545,7 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, > { > struct write_midx_context *ctx = data; > struct packed_git *p; > + struct string_list_item *item = NULL; > > if (ends_with(file_name, ".idx")) { > display_progress(ctx->progress, ++ctx->pack_paths_checked); > @@ -534,11 +564,13 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, > * should be performed independently (likely checking > * to_include before the existing MIDX). > */ > - if (ctx->m && midx_contains_pack(ctx->m, file_name)) > - return; > - else if (ctx->to_include && > - !string_list_has_string(ctx->to_include, file_name)) > + if (ctx->m && midx_contains_pack(ctx->m, file_name)) { > return; > + } else if (ctx->to_include) { > + item = string_list_lookup(ctx->to_include, file_name); > + if (!item) > + return; > + } > > ALLOC_GROW(ctx->info, ctx->nr + 1, ctx->alloc); > > @@ -559,6 +591,8 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, > > fill_pack_info(&ctx->info[ctx->nr], p, xstrdup(file_name), > ctx->nr); > + if (item) > + ctx->info[ctx->nr].disjoint = !!item->util; > ctx->nr++; > } > } > @@ -568,7 +602,8 @@ struct pack_midx_entry { > uint32_t pack_int_id; > time_t pack_mtime; > uint64_t offset; > - unsigned preferred : 1; > + unsigned preferred : 1, > + disjoint : 1; > }; > > static int midx_oid_compare(const void *_a, const void *_b) > @@ -586,6 +621,12 @@ static int midx_oid_compare(const void *_a, const void *_b) > if (a->preferred < b->preferred) > return 1; > > + /* Sort objects in a disjoint pack last when multiple copies exist. */ > + if (a->disjoint < b->disjoint) > + return -1; > + if (a->disjoint > b->disjoint) > + return 1; > + > if (a->pack_mtime > b->pack_mtime) > return -1; > else if (a->pack_mtime < b->pack_mtime) > @@ -671,6 +712,7 @@ static void midx_fanout_add_midx_fanout(struct midx_fanout *fanout, > &fanout->entries[fanout->nr], > cur_object); > fanout->entries[fanout->nr].preferred = 0; > + fanout->entries[fanout->nr].disjoint = 0; > fanout->nr++; > } > } > @@ -696,6 +738,7 @@ static void midx_fanout_add_pack_fanout(struct midx_fanout *fanout, > cur_object, > &fanout->entries[fanout->nr], > preferred); > + fanout->entries[fanout->nr].disjoint = info->disjoint; > fanout->nr++; > } > } > @@ -764,14 +807,22 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m, > * Take only the first duplicate. > */ > for (cur_object = 0; cur_object < fanout.nr; cur_object++) { > - if (cur_object && oideq(&fanout.entries[cur_object - 1].oid, > - &fanout.entries[cur_object].oid)) > - continue; > + struct pack_midx_entry *ours = &fanout.entries[cur_object]; > + if (cur_object) { > + struct pack_midx_entry *prev = &fanout.entries[cur_object - 1]; > + if (oideq(&prev->oid, &ours->oid)) { > + if (prev->disjoint && ours->disjoint) > + die(_("duplicate object '%s' among disjoint packs '%s', '%s'"), > + oid_to_hex(&prev->oid), > + info[prev->pack_int_id].pack_name, > + info[ours->pack_int_id].pack_name); Shouldn't we die if `prev->disjoint || ours->disjoint` instead of `&&`? Even if one of the packs isn't marked as disjoint, it's still wrong if the other one is and one of its objects exists in multiple packs. Or am I misunderstanding, and we only guarantee the disjoint property across packfiles that are actually marked as such? Patrick > + continue; > + } > + } > > ALLOC_GROW(deduplicated_entries, st_add(*nr_objects, 1), > alloc_objects); > - memcpy(&deduplicated_entries[*nr_objects], > - &fanout.entries[cur_object], > + memcpy(&deduplicated_entries[*nr_objects], ours, > sizeof(struct pack_midx_entry)); > (*nr_objects)++; > } > @@ -814,6 +865,27 @@ static int write_midx_pack_names(struct hashfile *f, void *data) > return 0; > } > > +static int write_midx_disjoint_packs(struct hashfile *f, void *data) > +{ > + struct write_midx_context *ctx = data; > + size_t i; > + > + for (i = 0; i < ctx->nr; i++) { > + struct pack_info *pack = &ctx->info[i]; > + if (pack->expired) > + continue; > + > + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN && pack->bitmap_nr) > + BUG("pack '%s' has no bitmap position, but has %d bitmapped object(s)", > + pack->pack_name, pack->bitmap_nr); > + > + hashwrite_be32(f, pack->bitmap_pos); > + hashwrite_be32(f, pack->bitmap_nr); > + hashwrite_be32(f, !!pack->disjoint); > + } > + return 0; > +} > + > static int write_midx_oid_fanout(struct hashfile *f, > void *data) > { > @@ -981,8 +1053,19 @@ static uint32_t *midx_pack_order(struct write_midx_context *ctx) > QSORT(data, ctx->entries_nr, midx_pack_order_cmp); > > ALLOC_ARRAY(pack_order, ctx->entries_nr); > - for (i = 0; i < ctx->entries_nr; i++) > + for (i = 0; i < ctx->entries_nr; i++) { > + struct pack_midx_entry *e = &ctx->entries[data[i].nr]; > + struct pack_info *pack = &ctx->info[ctx->pack_perm[e->pack_int_id]]; > + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN) > + pack->bitmap_pos = i; > + pack->bitmap_nr++; > pack_order[i] = data[i].nr; > + } > + for (i = 0; i < ctx->nr; i++) { > + struct pack_info *pack = &ctx->info[ctx->pack_perm[i]]; > + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN) > + pack->bitmap_pos = 0; > + } > free(data); > > trace2_region_leave("midx", "midx_pack_order", the_repository); > @@ -1283,6 +1366,7 @@ static int write_midx_internal(const char *object_dir, > struct hashfile *f = NULL; > struct lock_file lk; > struct write_midx_context ctx = { 0 }; > + int pack_disjoint_concat_len = 0; > int pack_name_concat_len = 0; > int dropped_packs = 0; > int result = 0; > @@ -1495,8 +1579,10 @@ static int write_midx_internal(const char *object_dir, > } > > for (i = 0; i < ctx.nr; i++) { > - if (!ctx.info[i].expired) > - pack_name_concat_len += strlen(ctx.info[i].pack_name) + 1; > + if (ctx.info[i].expired) > + continue; > + pack_name_concat_len += strlen(ctx.info[i].pack_name) + 1; > + pack_disjoint_concat_len += 3 * sizeof(uint32_t); > } > > /* Check that the preferred pack wasn't expired (if given). */ > @@ -1556,6 +1642,8 @@ static int write_midx_internal(const char *object_dir, > add_chunk(cf, MIDX_CHUNKID_REVINDEX, > st_mult(ctx.entries_nr, sizeof(uint32_t)), > write_midx_revindex); > + add_chunk(cf, MIDX_CHUNKID_DISJOINTPACKS, > + pack_disjoint_concat_len, write_midx_disjoint_packs); > } > > write_midx_header(f, get_num_chunks(cf), ctx.nr - dropped_packs); > diff --git a/midx.h b/midx.h > index a5d98919c8..cdd16a8378 100644 > --- a/midx.h > +++ b/midx.h > @@ -7,6 +7,7 @@ > struct object_id; > struct pack_entry; > struct repository; > +struct bitmapped_pack; > > #define GIT_TEST_MULTI_PACK_INDEX "GIT_TEST_MULTI_PACK_INDEX" > #define GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP \ > @@ -33,6 +34,8 @@ struct multi_pack_index { > > const unsigned char *chunk_pack_names; > size_t chunk_pack_names_len; > + const uint32_t *chunk_disjoint_packs; > + size_t chunk_disjoint_packs_len; > const uint32_t *chunk_oid_fanout; > const unsigned char *chunk_oid_lookup; > const unsigned char *chunk_object_offsets; > @@ -58,6 +61,8 @@ void get_midx_rev_filename(struct strbuf *out, struct multi_pack_index *m); > > struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local); > int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t pack_int_id); > +int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, > + struct bitmapped_pack *bp, uint32_t pack_int_id); > int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, uint32_t *result); > off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos); > uint32_t nth_midxed_pack_int_id(struct multi_pack_index *m, uint32_t pos); > diff --git a/pack-bitmap.h b/pack-bitmap.h > index 5273a6a019..b7fa1a42a9 100644 > --- a/pack-bitmap.h > +++ b/pack-bitmap.h > @@ -52,6 +52,15 @@ typedef int (*show_reachable_fn)( > > struct bitmap_index; > > +struct bitmapped_pack { > + struct packed_git *p; > + > + uint32_t bitmap_pos; > + uint32_t bitmap_nr; > + > + unsigned disjoint : 1; > +}; > + > struct bitmap_index *prepare_bitmap_git(struct repository *r); > struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx); > void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits, > diff --git a/t/helper/test-read-midx.c b/t/helper/test-read-midx.c > index e9a444ddba..4b44995dca 100644 > --- a/t/helper/test-read-midx.c > +++ b/t/helper/test-read-midx.c > @@ -100,10 +100,37 @@ static int read_midx_preferred_pack(const char *object_dir) > return 0; > } > > +static int read_midx_bitmapped_packs(const char *object_dir) > +{ > + struct multi_pack_index *midx = NULL; > + struct bitmapped_pack pack; > + uint32_t i; > + > + setup_git_directory(); > + > + midx = load_multi_pack_index(object_dir, 1); > + if (!midx) > + return 1; > + > + for (i = 0; i < midx->num_packs; i++) { > + if (nth_bitmapped_pack(the_repository, midx, &pack, i) < 0) > + return 1; > + > + printf("%s\n", pack_basename(pack.p)); > + printf(" bitmap_pos: %"PRIuMAX"\n", (uintmax_t)pack.bitmap_pos); > + printf(" bitmap_nr: %"PRIuMAX"\n", (uintmax_t)pack.bitmap_nr); > + printf(" disjoint: %s\n", pack.disjoint & 0x1 ? "yes" : "no"); > + } > + > + close_midx(midx); > + > + return 0; > +} > + > int cmd__read_midx(int argc, const char **argv) > { > if (!(argc == 2 || argc == 3)) > - usage("read-midx [--show-objects|--checksum|--preferred-pack] <object-dir>"); > + usage("read-midx [--show-objects|--checksum|--preferred-pack|--bitmap] <object-dir>"); > > if (!strcmp(argv[1], "--show-objects")) > return read_midx_file(argv[2], 1); > @@ -111,5 +138,7 @@ int cmd__read_midx(int argc, const char **argv) > return read_midx_checksum(argv[2]); > else if (!strcmp(argv[1], "--preferred-pack")) > return read_midx_preferred_pack(argv[2]); > + else if (!strcmp(argv[1], "--bitmap")) > + return read_midx_bitmapped_packs(argv[2]); > return read_midx_file(argv[1], 0); > } > diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh > index c4c6060cee..fd24e0c952 100755 > --- a/t/t5319-multi-pack-index.sh > +++ b/t/t5319-multi-pack-index.sh > @@ -1157,4 +1157,62 @@ test_expect_success 'reader notices too-small revindex chunk' ' > test_cmp expect.err err > ' > > +test_expect_success 'disjoint packs are stored via the DISP chunk' ' > + test_when_finished "rm -fr repo" && > + git init repo && > + ( > + cd repo && > + > + for i in 1 2 3 4 5 > + do > + test_commit "$i" && > + git repack -d || return 1 > + done && > + > + find $objdir/pack -type f -name "*.idx" | xargs -n 1 basename | sort >packs && > + > + git multi-pack-index write --stdin-packs <packs && > + test_must_fail test-tool read-midx --bitmap $objdir 2>err && > + cat >expect <<-\EOF && > + error: MIDX does not contain the DISP chunk > + EOF > + test_cmp expect err && > + > + sed -e "s/^/+/g" packs >in && > + git multi-pack-index write --stdin-packs --bitmap \ > + --preferred-pack="$(head -n1 <packs)" <in && > + test-tool read-midx --bitmap $objdir >actual && > + for i in $(test_seq $(wc -l <packs)) > + do > + sed -ne "${i}s/\.idx$/\.pack/p" packs && > + echo " bitmap_pos: $(( $(( $i - 1 )) * 3 ))" && > + echo " bitmap_nr: 3" && > + echo " disjoint: yes" || return 1 > + done >expect && > + test_cmp expect actual > + ) > +' > + > +test_expect_success 'non-disjoint packs are detected' ' > + test_when_finished "rm -fr repo" && > + git init repo && > + ( > + cd repo && > + > + test_commit base && > + git repack -d && > + test_commit other && > + git repack -a && > + > + ls -la .git/objects/pack/ && > + > + find $objdir/pack -type f -name "*.idx" | > + sed -e "s/.*\/\(.*\)$/+\1/g" >in && > + > + test_must_fail git multi-pack-index write --stdin-packs \ > + --bitmap <in 2>err && > + grep "duplicate object.* among disjoint packs" err > + ) > +' > + > test_done > -- > 2.43.0.24.g980b318f98 >
On Thu, Nov 30, 2023 at 11:18:45AM +0100, Patrick Steinhardt wrote: > > diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt > > index 9fcb29a9c8..658682ddd5 100644 > > --- a/Documentation/gitformat-pack.txt > > +++ b/Documentation/gitformat-pack.txt > > @@ -396,6 +396,22 @@ CHUNK DATA: > > is padded at the end with between 0 and 3 NUL bytes to make the > > chunk size a multiple of 4 bytes. > > > > + Disjoint Packfiles (ID: {'D', 'I', 'S', 'P'}) > > + Stores a table of three 4-byte unsigned integers in network order. > > + Each table entry corresponds to a single pack (in the order that > > + they appear above in the `PNAM` chunk). The values for each table > > + entry are as follows: > > + - The first bit position (in psuedo-pack order, see below) to > > s/psuedo/pseudo/ Good catch, thanks. Not sure how that escaped my spell-checker... > > +=== `DISP` chunk and disjoint packs > > + > > +The Disjoint Packfiles (`DISP`) chunk encodes additional information > > +about the objects in the multi-pack index's reachability bitmap. Recall > > +that objects from the MIDX are arranged in "pseudo-pack" order (see: > > The colon feels a bit out-of-place here, so: s/see:/see/ Thanks, I'll fix that up. > > +above) for reachability bitmaps. > > + > > +From the example above, suppose we have packs "a", "b", and "c", with > > +10, 15, and 20 objects, respectively. In pseudo-pack order, those would > > +be arranged as follows: > > + > > + |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19| > > + > > +When working with single-pack bitmaps (or, equivalently, multi-pack > > +reachability bitmaps without any packs marked as disjoint), > > +linkgit:git-pack-objects[1] performs ``verbatim'' reuse, attempting to > > +reuse chunks of the existing packfile instead of adding objects to the > > +packing list. > > I'm not sure I full understand this paragraph. In the context of a > single pack bitmap it's clear enough. But I stumbled over the MIDX case, > because here we potentially have multiple packfiles, so it's not exactly > clear to me what you refer to with "the existing packfile" in that case. > I'd think that we perform verbatim reuse of the preferred packfile, > right? If so, we might want to make that a bit more explicit. Yep, sorry, I can see how that would be confusing. Since we're talking about the existing behavior at this point in the series (before multi-pack reuse is implemented), I changed this to: "reuse chunks of the bitmapped or preferred packfile [...]" Thanks for carefully reading and spotting my errors ;-). > > +object. This introduces an additional constraint over the set of packs > > +we may want to reuse. The most straightforward approach is to mandate > > +that the set of packs is disjoint with respect to the set of objects > > +contained in each pack. In other words, for each object `o` in the union > > +of all objects stored by the disjoint set of packs, `o` is contained in > > +exactly one pack from the disjoint set. > > Is this a property that usually holds for our normal housekeeping, or > does it require careful managing by the user/admin? How about geometric > repacking? At this point in the series, it would require careful managing to ensure that this is the case. In practice MIDX'd packs generated with a geometric repack are mostly disjoint, but definitely not guaranteed to be. Further down in this series we'll introduce new options to generate packs which are guaranteed to be disjoint with respect to the currently-marked set of packs in the DISP chunk. > > @@ -764,14 +807,22 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m, > > * Take only the first duplicate. > > */ > > for (cur_object = 0; cur_object < fanout.nr; cur_object++) { > > - if (cur_object && oideq(&fanout.entries[cur_object - 1].oid, > > - &fanout.entries[cur_object].oid)) > > - continue; > > + struct pack_midx_entry *ours = &fanout.entries[cur_object]; > > + if (cur_object) { > > + struct pack_midx_entry *prev = &fanout.entries[cur_object - 1]; > > + if (oideq(&prev->oid, &ours->oid)) { > > + if (prev->disjoint && ours->disjoint) > > + die(_("duplicate object '%s' among disjoint packs '%s', '%s'"), > > + oid_to_hex(&prev->oid), > > + info[prev->pack_int_id].pack_name, > > + info[ours->pack_int_id].pack_name); > > Shouldn't we die if `prev->disjoint || ours->disjoint` instead of `&&`? > Even if one of the packs isn't marked as disjoint, it's still wrong if > the other one is and one of its objects exists in multiple packs. > > Or am I misunderstanding, and we only guarantee the disjoint property > across packfiles that are actually marked as such? Right, we only guarantee disjointed-ness among the set of packs that are marked disjoint. It's fine for the same object to appear in a disjoint and non-disjoint pack, and for both of those packs to end up in the MIDX. But that is only because we'll use the disjoint copy in our bitmap. If there were two packs that are marked as supposedly disjoint, but contain at least one duplicate of an object, then we will reject those packs as non-disjoint. Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: > diff --git a/Documentation/git-multi-pack-index.txt b/Documentation/git-multi-pack-index.txt > index 3696506eb3..d130e65b28 100644 > --- a/Documentation/git-multi-pack-index.txt > +++ b/Documentation/git-multi-pack-index.txt > @@ -49,6 +49,10 @@ write:: > --stdin-packs:: > Write a multi-pack index containing only the set of > line-delimited pack index basenames provided over stdin. > + Lines beginning with a '+' character (followed by the > + pack index basename as before) have their pack marked as > + "disjoint". See the "`DISP` chunk and disjoint packs" > + section in linkgit:gitformat-pack[5] for more. Makes one wonder who computes the set of packfiles, decides to prefix '+' to which ones, and how it does so, none of which appear in this step (which is understandable). As the flow of information is from the producer of individual "disjoint" packs (not in this step) to this new logic in "--stdin-packs" to the new "DISP" chunk writer (the primary focus of this step) to the final consumer of "DISP" chunk (not in this step), we are digging from the middle (hopefully to both directions in other steps). It is probably the easiest way to explain the idea to start from the primary data structures and "DISP" seems to be a good place to start. > + Two packs are "disjoint" with respect to one another when they have > + disjoint sets of objects. > + In other words, any object found in a pack > + contained in the set of disjoint packfiles is guaranteed to be > + uniquely located among those packs. I often advise people to rethink what they wrote _before_ "In other words", because the use of that phrase is a sign that the author considers the statement is hard to grok and needs rephrasing, in which case, the rephrased version may be a better way to explain the concept being presented without the harder-to-grok version. But I do not think this one is a good example to apply the advice. It is because "In other words," is somewhat misused in the sentence. Two "disjoint" packs do not store any common object (which is how you defined the adjective "disjoint" in the first sentence). "As a consequence"/"Hence", an object found in one pack among many "disjoint" packs will not appear in others. By the way, how strict does this disjointness have to be? Let's examine an extreme case. When you have two packs that are "mostly" disjoint, but have one single object in common, how would that object interfere with the bulk streaming of existing packdata out of these two packs? Would we be able to, say, safely pretend that the problematic single object lives only in one but not in the other (in other words, can we safely "ignore" the presence of the copy in the other pack)? I think it would break down if that ignored copy is used as a delta base of another object in the same pack, and the base object for the delta is recorded as OFS_DELTA (which most likely every delta is these days), because we no longer can stream out such deltified object without re-pointing its base to the other copy, which will in turn screw up the relative offset of other objects in the same stream. OK, so it seems they really need to be strictly disjoint in order to participate in the reuse of the existing packdata. > +When a chunk of bytes are reused from an existing pack, any objects > +contained therein do not need to be added to the packing list, saving > +memory and CPU time. But a chunk from an existing packfile can only be > +reused when the following conditions are met: > + > + - The chunk contains only objects which were requested by the caller > + (i.e. does not contain any objects which the caller didn't ask for > + explicitly or implicitly). OK. > + - All objects stored as offset- or reference-deltas also include their > + base object in the resulting pack. Are thin packs obsolete? > diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh > index c4c6060cee..fd24e0c952 100755 > --- a/t/t5319-multi-pack-index.sh > +++ b/t/t5319-multi-pack-index.sh > @@ -1157,4 +1157,62 @@ test_expect_success 'reader notices too-small revindex chunk' ' > test_cmp expect.err err > ' > > +test_expect_success 'disjoint packs are stored via the DISP chunk' ' > + test_when_finished "rm -fr repo" && > + git init repo && > + ( > + cd repo && > + > + for i in 1 2 3 4 5 > + do > + test_commit "$i" && > + git repack -d || return 1 > + done && > + > + find $objdir/pack -type f -name "*.idx" | xargs -n 1 basename | sort >packs && That is an overly-long line. > +test_expect_success 'non-disjoint packs are detected' ' > + test_when_finished "rm -fr repo" && > + git init repo && > + ( > + cd repo && > + > + test_commit base && > + git repack -d && > + test_commit other && > + git repack -a && > + > + ls -la .git/objects/pack/ && Is this line a leftover debugging aid? > + find $objdir/pack -type f -name "*.idx" | > + sed -e "s/.*\/\(.*\)$/+\1/g" >in && Lose "g"; it adds unnecessary cognitive burden to the readers if the patterh is expected to match multiple times, and you know that is not possible (your pattern is right anchored at the end). This may apply equally to other uses of "sed" in this patch. > + test_must_fail git multi-pack-index write --stdin-packs \ > + --bitmap <in 2>err && > + grep "duplicate object.* among disjoint packs" err > + ) > +' > + > test_done
On Sun, Dec 03, 2023 at 10:15:11PM +0900, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > diff --git a/Documentation/git-multi-pack-index.txt b/Documentation/git-multi-pack-index.txt > > index 3696506eb3..d130e65b28 100644 > > --- a/Documentation/git-multi-pack-index.txt > > +++ b/Documentation/git-multi-pack-index.txt > > @@ -49,6 +49,10 @@ write:: > > --stdin-packs:: > > Write a multi-pack index containing only the set of > > line-delimited pack index basenames provided over stdin. > > + Lines beginning with a '+' character (followed by the > > + pack index basename as before) have their pack marked as > > + "disjoint". See the "`DISP` chunk and disjoint packs" > > + section in linkgit:gitformat-pack[5] for more. > > Makes one wonder who computes the set of packfiles, decides to > prefix '+' to which ones, and how it does so, none of which appear > in this step (which is understandable). As the flow of information > is from the producer of individual "disjoint" packs (not in this > step) to this new logic in "--stdin-packs" to the new "DISP" chunk > writer (the primary focus of this step) to the final consumer of > "DISP" chunk (not in this step), we are digging from the middle > (hopefully to both directions in other steps). It is probably the > easiest way to explain the idea to start from the primary data > structures and "DISP" seems to be a good place to start. Thanks. I found that laying out this series was rather tricky, since all of the individual pieces really depend on the end state in order to make any sense. Hopefully you're satisfied with the way things are split up and organized currently, but if you have suggestions on other ways I could slice or dice this, please let me know. > > + Two packs are "disjoint" with respect to one another when they have > > + disjoint sets of objects. > > + In other words, any object found in a pack > > + contained in the set of disjoint packfiles is guaranteed to be > > + uniquely located among those packs. > > I often advise people to rethink what they wrote _before_ "In other > words", because the use of that phrase is a sign that the author > considers the statement is hard to grok and needs rephrasing, in > which case, the rephrased version may be a better way to explain the > concept being presented without the harder-to-grok version. > > But I do not think this one is a good example to apply the advice. > It is because "In other words," is somewhat misused in the sentence. > Two "disjoint" packs do not store any common object (which is how > you defined the adjective "disjoint" in the first sentence). "As a > consequence"/"Hence", an object found in one pack among many > "disjoint" packs will not appear in others. Thanks, I'll replace this with "As a consequence", and try to follow that general advice more often in the future ;-). > OK, so it seems they really need to be strictly disjoint in order to > participate in the reuse of the existing packdata. I think that's generally true, though there are some exceptions. I think the real condition here is that the *reused sections* must be disjoint with respect to one another, not necessarily the packs themselves. So having the packs be disjoint is a sufficient condition, since we know that no matter which section(s) we reuse, they are guaranteed to be disjoint. I think that there is opportunity to be more clever here, e.g., by allowing for different disjoint "groups" of packs, or mandating that you can only reuse certain sections from different combinations of packs in order to satisfy this property. That's part of the reason why I left more space than is needed for the "disjoint" state in the DISP chunk (it is 32 bits, of which we're only using one of them). I'm not sure that we would want more relaxed constraints here, since they'd be harder to satisfy. But my hope is that we would be able to learn from running this in production to figure out whether or not such a thing would be useful. > > + - All objects stored as offset- or reference-deltas also include their > > + base object in the resulting pack. > > Are thin packs obsolete? No, I think I should clarify this to make it more obvious that this only applies to non-thin packs. > > + find $objdir/pack -type f -name "*.idx" | xargs -n 1 basename | sort >packs && > > That is an overly-long line. Thanks for spotting. > > +test_expect_success 'non-disjoint packs are detected' ' > > + test_when_finished "rm -fr repo" && > > + git init repo && > > + ( > > + cd repo && > > + > > + test_commit base && > > + git repack -d && > > + test_commit other && > > + git repack -a && > > + > > + ls -la .git/objects/pack/ && > > Is this line a leftover debugging aid? Indeed, thanks. > > + find $objdir/pack -type f -name "*.idx" | > > + sed -e "s/.*\/\(.*\)$/+\1/g" >in && > > Lose "g"; it adds unnecessary cognitive burden to the readers if the > patterh is expected to match multiple times, and you know that is > not possible (your pattern is right anchored at the end). This may > apply equally to other uses of "sed" in this patch. Thanks, I dropped the 'g' in both instances. Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: > Hopefully you're satisfied with the way things are split up and > organized currently, but if you have suggestions on other ways I could > slice or dice this, please let me know. I did wonder how expensive to recompute and validate the "distinct" information (in other words, is it too expensive for the consumers of an existing midx file to see which packs are distinct on demand before they stream contents out of the underlying packs?), as the way the packs are marked as distinct looked rather error prone (you can very easily list packfiles with overlaps with "+" prefix and the DISK chunk writer does not even notice that you lied to it). As long as "git fsck" catches when two packs that are marked as distinct share an object, that is OK, but the arrangement did look rather brittle to me.
On Fri, Dec 08, 2023 at 05:40:29PM -0800, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > Hopefully you're satisfied with the way things are split up and > > organized currently, but if you have suggestions on other ways I could > > slice or dice this, please let me know. > > I did wonder how expensive to recompute and validate the "distinct" > information (in other words, is it too expensive for the consumers > of an existing midx file to see which packs are distinct on demand > before they stream contents out of the underlying packs?), as the > way the packs are marked as distinct looked rather error prone (you > can very easily list packfiles with overlaps with "+" prefix and the > DISK chunk writer does not even notice that you lied to it). As long > as "git fsck" catches when two packs that are marked as distinct share > an object, that is OK, but the arrangement did look rather brittle > to me. It's likely too expensive to do on the reading side for every pack-objects operation or MIDX load. But we do check this property when we write the MIDX, see these lines from midx.c::get_sorted_entries(): for (cur_object = 0; cur_object < fanout.nr; cur_object++) { struct pack_midx_entry *ours = &fanout.entries[cur_object]; if (cur_object) { struct pack_midx_entry *prev = &fanout.entries[cur_object - 1]; if (oideq(&prev->oid, &ours->oid)) { if (prev->disjoint && ours->disjoint) die(_("duplicate object '%s' among disjoint packs '%s', '%s'"), oid_to_hex(&prev->oid), info[prev->pack_int_id].pack_name, info[ours->pack_int_id].pack_name); continue; } } This series doesn't yet have a corresponding step in the fsck builtin, but I will investigate adding one. I'm happy to include it in a subsequent round here, but I worry that this series is already on the verge of being too complex as-is, so it may be nice as a follow-up, too. Thanks, Taylor
On Fri, Dec 08, 2023 at 09:30:07PM -0500, Taylor Blau wrote: > > I did wonder how expensive to recompute and validate the "distinct" > > information (in other words, is it too expensive for the consumers > > of an existing midx file to see which packs are distinct on demand > > before they stream contents out of the underlying packs?), as the > > way the packs are marked as distinct looked rather error prone (you > > can very easily list packfiles with overlaps with "+" prefix and the > > DISK chunk writer does not even notice that you lied to it). As long > > as "git fsck" catches when two packs that are marked as distinct share > > an object, that is OK, but the arrangement did look rather brittle > > to me. > > It's likely too expensive to do on the reading side for every > pack-objects operation or MIDX load. This made me think a bit. Obviously we can check for disjointedness in O(n log k), where n is the total number of objects and k is the number of packs, by doing a k-merge of the sorted lists. But that's a non-starter, because we may be serving a request that is much smaller than all "n" objects (e.g., any small fetch, but also even clones when the pack contains a bunch of irrelevant objects). But we can relax our condition a bit. The packs only need to be disjoint with respect to the set of objects that we are going to output (we'll call that "m"). So at the very least, you can do O(mk) lookups (each one itself "log n", of course). We know that the work is already going to be linear in "m". In theory we want to generally keep "k" small, but part of the point of using midx in this way is to let "k" grow a bit. So that might turn out pretty bad in practice. So let's take one more step back. One thing I didn't feel like I saw either in this patch or the cover letter is exactly why we care about disjointedness. IIRC, the main issue is making sure that for any object X we send verbatim, it is either a non-delta or its delta base is viable. And the two reasons I can think of for the base to be non-viable are: 1. We are not sending the base at all. 2. The base is in another pack, and we are worried about creating a cycle (i.e., in pack A we have X as a delta against Y, and in pack B we have Y as a delta against X, and we send both deltas). We already deal with (1) for the single-pack case by finding the base object offset, converting it to a pack position, and then making sure that position is also marked for verbatim reuse. The interesting one is (2), which is new for midx (since a single pack cannot have two copies of an object). But I'm not sure if it's possible. The verbatim reuse code depends on using bitmaps in the first place. And there is already a preference-order to the packs in the midx bitmaps. That is, we'll choose all of the objects for pack A over any duplicates in B, and duplicates from B over C, and so on. If we likewise try verbatim reuse in that order, then we know that an object in pack A can never have a base that is selected from pack B or C (because if they do have duplicates, we'd have selected A's copy to put in the midx bitmap). And likewise, a copy of an object in pack B will always have its base either in A or B, but never in C. So it kind of seems to me that this would "just work" if try_partial_reuse() did something like for the midx case: - convert offset of base object into an object id hash using the pack revindex (similar to offset_to_pack_pos) - look up the object id in the midx to get a pack/offset combo - use the midx revindex to convert that into a bit position - check if that bit is marked for verbatim reuse The assumption there is that in the second step, the midx has resolved duplicates by putting all of pack A before pack B, and so on, as above. It also assumes that we are trying verbatim reuse in the same order (though a different order would not produce wrong results, it would only result in less verbatim reuse). All of which makes me think I'm missing some other case that is a problem. While I wait for you to explain it, though, let's continue our thought experiment for a moment. If we assume that any cross-pack deltas are a problem, we could always just skip them for verbatim reuse. That is, once we look up the object id in the midx, we can see if it's in the same pack we're currently processing. If not, we could punt and let the non-verbatim code paths handle it as usual. That still leaves the problem of realizing we skipped over a chunk of the packfile (say we are pulling object X from pack B, and it is a delta of Y, but we already decided to reuse Y from pack A). But the reuse code already has to accommodate gaps. I think it happens naturally in write_reused_pack_one(), where we feed the actual byte offsets into record_reused_object(). You'd have to take some care not to go past gaps in the blind copy that happens write_reused_pack_verbatim(). So you might need to mark the first such gap somehow (if it's hard, I'd suggest just skipping write_reused_pack_verbatim() entirely; it is a fairly minor optimization compared to the rest of it). And of course there's a bunch of hard work teaching all of those functions about midx's and multiple packs in the first place, but you already had to do all that in the latter part of your series, and it would still be applicable. OK, this is the part where you tell me what I'm missing. ;) -Peff
Hi Peff, On Tue, Dec 12, 2023 at 03:03:32AM -0500, Jeff King wrote: > [...] Well this took me longer to respond to than I thought it would ;-). > So it kind of seems to me that this would "just work" if > try_partial_reuse() did something like for the midx case: > > - convert offset of base object into an object id hash using the pack > revindex (similar to offset_to_pack_pos) > > - look up the object id in the midx to get a pack/offset combo > > - use the midx revindex to convert that into a bit position > > - check if that bit is marked for verbatim reuse > > The assumption there is that in the second step, the midx has resolved > duplicates by putting all of pack A before pack B, and so on, as above. > It also assumes that we are trying verbatim reuse in the same order > (though a different order would not produce wrong results, it would only > result in less verbatim reuse). After much thinking, I agree with your conclusion here. Which is great news indeed, since it allows us to implement multi-pack reuse without requiring that the candidate packs be disjoint with respect to their objects. Even though we have some protections in place for ensuring these packs' disjointed-ness, I agree with Junio upthread that this is likely the most fragile part of this series. That is, even though we check in midx.c::get_sorted_entries() that the marked packs are disjoint, if we miss something, the results would be rather bad. At best it would result in sending a corrupt packfile to the client, and at worst it could result in permanent data corruption if repacking a repository with multi-pack reuse enabled. > If we assume that any cross-pack deltas are a problem, we could always > just skip them for verbatim reuse. That is, once we look up the object > id in the midx, we can see if it's in the same pack we're currently > processing. If not, we could punt and let the non-verbatim code paths > handle it as usual. Let me think aloud for a second, since it took me quite a lot of thinking to fully wrap my head around this. Suppose we have two packs, P1 and P2 where P1 has object A delta'd against B, and P2 has its own copy of object B. If the MIDX chose the copy of B from P2, but also decided to send P1 (which it chose from A), then if P1 is stored as an OFS delta, we would be sending a corrupt packfile to the client. I think there are a few things that we could reasonably do here: - Reject cross-pack deltas entirely (as you suggest). This is the easiest implementation choice in this already-complex series, and it doesn't paint us into a corner in the sense that we could relax these requirements in the future. - Turn any cross-pack deltas (which are stored as OFS_DELTAs) into REF_DELTAs. We already do this today when reusing an OFS_DELTA without `--delta-base-offset` enabled, so it's not a huge stretch to do the same for cross-pack deltas even when `--delta-base-offset` is enabled. This would work, but would obviously result in larger-than-necessary packs, as we in theory *could* represent these cross-pack deltas by patching an existing OFS_DELTA. But it's not clear how much that would matter in practice. I suspect it would have a lot to do with how you pack your repository in the first place. - Finally, we could patch OFS_DELTAs across packs in a similar fashion as we do today for OFS_DELTAs within a single pack on either side of a gap. This would result in the smallest packs of the three options here, but implementing this would be more involved. At minimum, you'd have to keep the reusable chunks list for all reused packs, not just the one we're currently processing. And you'd have to ensure that any bases which are a part of cross-pack deltas appear before the delta. I think this is possible to do, but would require assembling the reusable chunks list potentially in a different order than they appear in the source packs. > And of course there's a bunch of hard work teaching all of those > functions about midx's and multiple packs in the first place, but you > already had to do all that in the latter part of your series, and it > would still be applicable. Yep, all of that is still a requirement here, and lives on in the revised version of this series. The naive implementation where we call try_partial_reuse() on every object which is a candidate for reuse and check for cross-pack deltas would work, but have poor performance. The reason is that we would be doing a significant amount of cache-inefficient work to determine whether or not the base for some delta/base-pair resides in the same pack: - If you see a delta in some pack while processing a MIDX bitmap for reuse, you first have to figure out the location of its base in that same pack. (Note: this may or may not be the copy of the base object chosen by the MIDX). - To figure out whether or not the MIDX chose that copy, you would naively have to do something like: - Convert the base object's offset into a packfile position using the pack revindex. - Convert the base object's packfile position into an index position, which would then be used to obtain its OID. - Then binary search through the MIDX for that OID found in the previous step, filling out the MIDX entry for that object. - Toss out the cross-pack delta/base pair if the MIDX entry in the previous step indicates that the MIDX chose a copy of the base from a different pack than the one we're currently processing (i.e. where the delta resides). That's rather inefficient. But, we can do better. Instead of going back and forth through both the pack and MIDX's reverse index, we can simply binary search in the MIDX's reverse index for the (pack_id, offset) pair corresponding to the base. If we find a match, then we know that the MIDX chose its copy of the base object from the same pack, and we can reuse the delta/base-pair. If we don't, then we know that the MIDX chose its copy of the base object from a different pack, and we have to throw out the delta/base-pair. This is a bit more involved than the naive implementation, but it's (a) efficient, and (b) most of the code for it already exists in the form of midx_to_pack_pos(), which implements a binary search over the MIDX bitmap's pseudo-pack order. With some light refactoring, we can repurpose this code to perform a binary search for a given (pack, offset) pair instead of starting with a MIDX lex position and converting it into the (pack, offset) pair. So that works, and is what I've done in the revised version of this series. There is one other snag, which is that we can no longer blindly reuse whole-words from the reuse bitmap if we have non-disjoint packs. That is, we can't do something like: while (pos < result->word_alloc && result->words[pos] == (eword_t)~0) pos++; when processing anything but the first pack. The reason is that we know the first pack has all duplicate object ties broken in its favor, but we don't have the same guarantee for subsequent packs. So we have to be more careful about which bits we reuse from those subsequent packs, since we may inadvertently pick up a cross-pack delta/base pair without inspecting it more closely. As I mentioned, you can still perform this optimization over the first pack, and I think that will be sufficient for most repositories. It's not clear to me exactly how much this optimization is helping us in contrast to all of the other work that pack-objects is doing, but that is probably something worth measuring. Thanks for the terrific suggestion. I'll clean up the results of trying to implement it, and share it with the list soon (ideally before the end of this week, after which I'm on vacation until the new year). Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: > - Turn any cross-pack deltas (which are stored as OFS_DELTAs) into > REF_DELTAs. We already do this today when reusing an OFS_DELTA > without `--delta-base-offset` enabled, so it's not a huge stretch to > do the same for cross-pack deltas even when `--delta-base-offset` is > enabled. > > This would work, but would obviously result in larger-than-necessary > packs, as we in theory *could* represent these cross-pack deltas by > patching an existing OFS_DELTA. But it's not clear how much that > would matter in practice. I suspect it would have a lot to do with > how you pack your repository in the first place. I have to wonder if the cost of additional computation to see when is safe to allow cross-pack delta can be kept reasonably low, as you'd need to prove that you are not introducing a cycle by doing so. Compared to that, spending a dozen or so bytes for the offset for rare cases of having to express such a cross-pack delta pair would be much less worrisome to me. > Thanks for the terrific suggestion. I'll clean up the results of trying > to implement it, and share it with the list soon (ideally before the end > of this week, after which I'm on vacation until the new year). Good to hear that you'll be recharging soon. Enjoy.
diff --git a/Documentation/git-multi-pack-index.txt b/Documentation/git-multi-pack-index.txt index 3696506eb3..d130e65b28 100644 --- a/Documentation/git-multi-pack-index.txt +++ b/Documentation/git-multi-pack-index.txt @@ -49,6 +49,10 @@ write:: --stdin-packs:: Write a multi-pack index containing only the set of line-delimited pack index basenames provided over stdin. + Lines beginning with a '+' character (followed by the + pack index basename as before) have their pack marked as + "disjoint". See the "`DISP` chunk and disjoint packs" + section in linkgit:gitformat-pack[5] for more. --refs-snapshot=<path>:: With `--bitmap`, optionally specify a file which diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt index 9fcb29a9c8..658682ddd5 100644 --- a/Documentation/gitformat-pack.txt +++ b/Documentation/gitformat-pack.txt @@ -396,6 +396,22 @@ CHUNK DATA: is padded at the end with between 0 and 3 NUL bytes to make the chunk size a multiple of 4 bytes. + Disjoint Packfiles (ID: {'D', 'I', 'S', 'P'}) + Stores a table of three 4-byte unsigned integers in network order. + Each table entry corresponds to a single pack (in the order that + they appear above in the `PNAM` chunk). The values for each table + entry are as follows: + - The first bit position (in psuedo-pack order, see below) to + contain an object from that pack. + - The number of bits whose objects are selected from that pack. + - A "meta" value, whose least-significant bit indicates whether or + not the pack is disjoint with respect to other packs. The + remaining bits are unused. + Two packs are "disjoint" with respect to one another when they have + disjoint sets of objects. In other words, any object found in a pack + contained in the set of disjoint packfiles is guaranteed to be + uniquely located among those packs. + OID Fanout (ID: {'O', 'I', 'D', 'F'}) The ith entry, F[i], stores the number of OIDs with first byte at most i. Thus F[255] stores the total @@ -509,6 +525,99 @@ packs arranged in MIDX order (with the preferred pack coming first). The MIDX's reverse index is stored in the optional 'RIDX' chunk within the MIDX itself. +=== `DISP` chunk and disjoint packs + +The Disjoint Packfiles (`DISP`) chunk encodes additional information +about the objects in the multi-pack index's reachability bitmap. Recall +that objects from the MIDX are arranged in "pseudo-pack" order (see: +above) for reachability bitmaps. + +From the example above, suppose we have packs "a", "b", and "c", with +10, 15, and 20 objects, respectively. In pseudo-pack order, those would +be arranged as follows: + + |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19| + +When working with single-pack bitmaps (or, equivalently, multi-pack +reachability bitmaps without any packs marked as disjoint), +linkgit:git-pack-objects[1] performs ``verbatim'' reuse, attempting to +reuse chunks of the existing packfile instead of adding objects to the +packing list. + +When a chunk of bytes are reused from an existing pack, any objects +contained therein do not need to be added to the packing list, saving +memory and CPU time. But a chunk from an existing packfile can only be +reused when the following conditions are met: + + - The chunk contains only objects which were requested by the caller + (i.e. does not contain any objects which the caller didn't ask for + explicitly or implicitly). + + - All objects stored as offset- or reference-deltas also include their + base object in the resulting pack. + +Additionally, packfiles many not contain more than one copy of any given +object. This introduces an additional constraint over the set of packs +we may want to reuse. The most straightforward approach is to mandate +that the set of packs is disjoint with respect to the set of objects +contained in each pack. In other words, for each object `o` in the union +of all objects stored by the disjoint set of packs, `o` is contained in +exactly one pack from the disjoint set. + +One alternative design choice for multi-pack reuse might instead involve +imposing a chunk-level constraint that allows packs in the reusable set +to contain multiple copies across different packs, but restricts each +chunk against including more than one copy of such an object. This is in +theory possible to implement, but significantly more complicated than +forcing packs themselves to be disjoint. Most notably, we would have to +keep track of which objects have already been sent during verbatim +pack-reuse, defeating the main purpose of verbatim pack reuse (that we +don't have to keep track of individual objects). + +The `DISP` chunk encodes the necessary information in order to implement +multi-pack reuse over a disjoint set of packs as described above. +Specifically, the `DISP` chunk encodes three pieces of information (all +32-bit unsigned integers in network byte-order) for each packfile `p` +that is stored in the MIDX, as follows: + +`bitmap_pos`:: The first bit position (in pseudo-pack order) in the + multi-pack index's reachability bitmap occupied by an object from `p`. + +`bitmap_nr`:: The number of bit positions (including the one at + `bitmap_pos`) that encode objects from that pack `p`. + +`disjoint`:: Metadata, including whether or not the pack `p` is + ``disjoint''. The least significant bit stores whether or not the pack + is disjoint. The remaining bits are reserved for future use. + +For example, the `DISP` chunk corresponding to the above example (with +packs ``a'', ``b'', and ``c'') would look like: + +[cols="1,2,2,2"] +|=== +| |`bitmap_pos` |`bitmap_nr` |`disjoint` + +|packfile ``a'' +|`0` +|`10` +|`0x1` + +|packfile ``b'' +|`10` +|`15` +|`0x1` + +|packfile ``c'' +|`25` +|`20` +|`0x1` +|=== + +With these constraints and information in place, we can treat each +packfile marked as disjoint as individually reusable in the same fashion +as verbatim pack reuse is performed on individual packs prior to the +implementation of the `DISP` chunk. + == cruft packs The cruft packs feature offer an alternative to Git's traditional mechanism of diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c index a72aebecaa..0f1dd4651d 100644 --- a/builtin/multi-pack-index.c +++ b/builtin/multi-pack-index.c @@ -106,11 +106,17 @@ static int git_multi_pack_index_write_config(const char *var, const char *value, return 0; } +#define DISJOINT ((void*)(uintptr_t)1) + static void read_packs_from_stdin(struct string_list *to) { struct strbuf buf = STRBUF_INIT; - while (strbuf_getline(&buf, stdin) != EOF) - string_list_append(to, buf.buf); + while (strbuf_getline(&buf, stdin) != EOF) { + if (*buf.buf == '+') + string_list_append(to, buf.buf + 1)->util = DISJOINT; + else + string_list_append(to, buf.buf); + } string_list_sort(to); strbuf_release(&buf); diff --git a/midx.c b/midx.c index 591b3c636e..f55020072f 100644 --- a/midx.c +++ b/midx.c @@ -33,6 +33,7 @@ #define MIDX_CHUNK_ALIGNMENT 4 #define MIDX_CHUNKID_PACKNAMES 0x504e414d /* "PNAM" */ +#define MIDX_CHUNKID_DISJOINTPACKS 0x44495350 /* "DISP" */ #define MIDX_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */ #define MIDX_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */ #define MIDX_CHUNKID_OBJECTOFFSETS 0x4f4f4646 /* "OOFF" */ @@ -182,6 +183,9 @@ struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local pair_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS, &m->chunk_large_offsets, &m->chunk_large_offsets_len); + pair_chunk(cf, MIDX_CHUNKID_DISJOINTPACKS, + (const unsigned char **)&m->chunk_disjoint_packs, + &m->chunk_disjoint_packs_len); if (git_env_bool("GIT_TEST_MIDX_READ_RIDX", 1)) pair_chunk(cf, MIDX_CHUNKID_REVINDEX, &m->chunk_revindex, @@ -275,6 +279,23 @@ int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t return 0; } +int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, + struct bitmapped_pack *bp, uint32_t pack_int_id) +{ + if (!m->chunk_disjoint_packs) + return error(_("MIDX does not contain the DISP chunk")); + + if (prepare_midx_pack(r, m, pack_int_id)) + return error(_("could not load disjoint pack %"PRIu32), pack_int_id); + + bp->p = m->packs[pack_int_id]; + bp->bitmap_pos = get_be32(m->chunk_disjoint_packs + 3 * pack_int_id); + bp->bitmap_nr = get_be32(m->chunk_disjoint_packs + 3 * pack_int_id + 1); + bp->disjoint = !!get_be32(m->chunk_disjoint_packs + 3 * pack_int_id + 2); + + return 0; +} + int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, uint32_t *result) { return bsearch_hash(oid->hash, m->chunk_oid_fanout, m->chunk_oid_lookup, @@ -457,11 +478,18 @@ static size_t write_midx_header(struct hashfile *f, return MIDX_HEADER_SIZE; } +#define BITMAP_POS_UNKNOWN (~((uint32_t)0)) + struct pack_info { uint32_t orig_pack_int_id; char *pack_name; struct packed_git *p; - unsigned expired : 1; + + uint32_t bitmap_pos; + uint32_t bitmap_nr; + + unsigned expired : 1, + disjoint : 1; }; static void fill_pack_info(struct pack_info *info, @@ -473,6 +501,7 @@ static void fill_pack_info(struct pack_info *info, info->orig_pack_int_id = orig_pack_int_id; info->pack_name = pack_name; info->p = p; + info->bitmap_pos = BITMAP_POS_UNKNOWN; } static int pack_info_compare(const void *_a, const void *_b) @@ -516,6 +545,7 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, { struct write_midx_context *ctx = data; struct packed_git *p; + struct string_list_item *item = NULL; if (ends_with(file_name, ".idx")) { display_progress(ctx->progress, ++ctx->pack_paths_checked); @@ -534,11 +564,13 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, * should be performed independently (likely checking * to_include before the existing MIDX). */ - if (ctx->m && midx_contains_pack(ctx->m, file_name)) - return; - else if (ctx->to_include && - !string_list_has_string(ctx->to_include, file_name)) + if (ctx->m && midx_contains_pack(ctx->m, file_name)) { return; + } else if (ctx->to_include) { + item = string_list_lookup(ctx->to_include, file_name); + if (!item) + return; + } ALLOC_GROW(ctx->info, ctx->nr + 1, ctx->alloc); @@ -559,6 +591,8 @@ static void add_pack_to_midx(const char *full_path, size_t full_path_len, fill_pack_info(&ctx->info[ctx->nr], p, xstrdup(file_name), ctx->nr); + if (item) + ctx->info[ctx->nr].disjoint = !!item->util; ctx->nr++; } } @@ -568,7 +602,8 @@ struct pack_midx_entry { uint32_t pack_int_id; time_t pack_mtime; uint64_t offset; - unsigned preferred : 1; + unsigned preferred : 1, + disjoint : 1; }; static int midx_oid_compare(const void *_a, const void *_b) @@ -586,6 +621,12 @@ static int midx_oid_compare(const void *_a, const void *_b) if (a->preferred < b->preferred) return 1; + /* Sort objects in a disjoint pack last when multiple copies exist. */ + if (a->disjoint < b->disjoint) + return -1; + if (a->disjoint > b->disjoint) + return 1; + if (a->pack_mtime > b->pack_mtime) return -1; else if (a->pack_mtime < b->pack_mtime) @@ -671,6 +712,7 @@ static void midx_fanout_add_midx_fanout(struct midx_fanout *fanout, &fanout->entries[fanout->nr], cur_object); fanout->entries[fanout->nr].preferred = 0; + fanout->entries[fanout->nr].disjoint = 0; fanout->nr++; } } @@ -696,6 +738,7 @@ static void midx_fanout_add_pack_fanout(struct midx_fanout *fanout, cur_object, &fanout->entries[fanout->nr], preferred); + fanout->entries[fanout->nr].disjoint = info->disjoint; fanout->nr++; } } @@ -764,14 +807,22 @@ static struct pack_midx_entry *get_sorted_entries(struct multi_pack_index *m, * Take only the first duplicate. */ for (cur_object = 0; cur_object < fanout.nr; cur_object++) { - if (cur_object && oideq(&fanout.entries[cur_object - 1].oid, - &fanout.entries[cur_object].oid)) - continue; + struct pack_midx_entry *ours = &fanout.entries[cur_object]; + if (cur_object) { + struct pack_midx_entry *prev = &fanout.entries[cur_object - 1]; + if (oideq(&prev->oid, &ours->oid)) { + if (prev->disjoint && ours->disjoint) + die(_("duplicate object '%s' among disjoint packs '%s', '%s'"), + oid_to_hex(&prev->oid), + info[prev->pack_int_id].pack_name, + info[ours->pack_int_id].pack_name); + continue; + } + } ALLOC_GROW(deduplicated_entries, st_add(*nr_objects, 1), alloc_objects); - memcpy(&deduplicated_entries[*nr_objects], - &fanout.entries[cur_object], + memcpy(&deduplicated_entries[*nr_objects], ours, sizeof(struct pack_midx_entry)); (*nr_objects)++; } @@ -814,6 +865,27 @@ static int write_midx_pack_names(struct hashfile *f, void *data) return 0; } +static int write_midx_disjoint_packs(struct hashfile *f, void *data) +{ + struct write_midx_context *ctx = data; + size_t i; + + for (i = 0; i < ctx->nr; i++) { + struct pack_info *pack = &ctx->info[i]; + if (pack->expired) + continue; + + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN && pack->bitmap_nr) + BUG("pack '%s' has no bitmap position, but has %d bitmapped object(s)", + pack->pack_name, pack->bitmap_nr); + + hashwrite_be32(f, pack->bitmap_pos); + hashwrite_be32(f, pack->bitmap_nr); + hashwrite_be32(f, !!pack->disjoint); + } + return 0; +} + static int write_midx_oid_fanout(struct hashfile *f, void *data) { @@ -981,8 +1053,19 @@ static uint32_t *midx_pack_order(struct write_midx_context *ctx) QSORT(data, ctx->entries_nr, midx_pack_order_cmp); ALLOC_ARRAY(pack_order, ctx->entries_nr); - for (i = 0; i < ctx->entries_nr; i++) + for (i = 0; i < ctx->entries_nr; i++) { + struct pack_midx_entry *e = &ctx->entries[data[i].nr]; + struct pack_info *pack = &ctx->info[ctx->pack_perm[e->pack_int_id]]; + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN) + pack->bitmap_pos = i; + pack->bitmap_nr++; pack_order[i] = data[i].nr; + } + for (i = 0; i < ctx->nr; i++) { + struct pack_info *pack = &ctx->info[ctx->pack_perm[i]]; + if (pack->bitmap_pos == BITMAP_POS_UNKNOWN) + pack->bitmap_pos = 0; + } free(data); trace2_region_leave("midx", "midx_pack_order", the_repository); @@ -1283,6 +1366,7 @@ static int write_midx_internal(const char *object_dir, struct hashfile *f = NULL; struct lock_file lk; struct write_midx_context ctx = { 0 }; + int pack_disjoint_concat_len = 0; int pack_name_concat_len = 0; int dropped_packs = 0; int result = 0; @@ -1495,8 +1579,10 @@ static int write_midx_internal(const char *object_dir, } for (i = 0; i < ctx.nr; i++) { - if (!ctx.info[i].expired) - pack_name_concat_len += strlen(ctx.info[i].pack_name) + 1; + if (ctx.info[i].expired) + continue; + pack_name_concat_len += strlen(ctx.info[i].pack_name) + 1; + pack_disjoint_concat_len += 3 * sizeof(uint32_t); } /* Check that the preferred pack wasn't expired (if given). */ @@ -1556,6 +1642,8 @@ static int write_midx_internal(const char *object_dir, add_chunk(cf, MIDX_CHUNKID_REVINDEX, st_mult(ctx.entries_nr, sizeof(uint32_t)), write_midx_revindex); + add_chunk(cf, MIDX_CHUNKID_DISJOINTPACKS, + pack_disjoint_concat_len, write_midx_disjoint_packs); } write_midx_header(f, get_num_chunks(cf), ctx.nr - dropped_packs); diff --git a/midx.h b/midx.h index a5d98919c8..cdd16a8378 100644 --- a/midx.h +++ b/midx.h @@ -7,6 +7,7 @@ struct object_id; struct pack_entry; struct repository; +struct bitmapped_pack; #define GIT_TEST_MULTI_PACK_INDEX "GIT_TEST_MULTI_PACK_INDEX" #define GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP \ @@ -33,6 +34,8 @@ struct multi_pack_index { const unsigned char *chunk_pack_names; size_t chunk_pack_names_len; + const uint32_t *chunk_disjoint_packs; + size_t chunk_disjoint_packs_len; const uint32_t *chunk_oid_fanout; const unsigned char *chunk_oid_lookup; const unsigned char *chunk_object_offsets; @@ -58,6 +61,8 @@ void get_midx_rev_filename(struct strbuf *out, struct multi_pack_index *m); struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local); int prepare_midx_pack(struct repository *r, struct multi_pack_index *m, uint32_t pack_int_id); +int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m, + struct bitmapped_pack *bp, uint32_t pack_int_id); int bsearch_midx(const struct object_id *oid, struct multi_pack_index *m, uint32_t *result); off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos); uint32_t nth_midxed_pack_int_id(struct multi_pack_index *m, uint32_t pos); diff --git a/pack-bitmap.h b/pack-bitmap.h index 5273a6a019..b7fa1a42a9 100644 --- a/pack-bitmap.h +++ b/pack-bitmap.h @@ -52,6 +52,15 @@ typedef int (*show_reachable_fn)( struct bitmap_index; +struct bitmapped_pack { + struct packed_git *p; + + uint32_t bitmap_pos; + uint32_t bitmap_nr; + + unsigned disjoint : 1; +}; + struct bitmap_index *prepare_bitmap_git(struct repository *r); struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx); void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits, diff --git a/t/helper/test-read-midx.c b/t/helper/test-read-midx.c index e9a444ddba..4b44995dca 100644 --- a/t/helper/test-read-midx.c +++ b/t/helper/test-read-midx.c @@ -100,10 +100,37 @@ static int read_midx_preferred_pack(const char *object_dir) return 0; } +static int read_midx_bitmapped_packs(const char *object_dir) +{ + struct multi_pack_index *midx = NULL; + struct bitmapped_pack pack; + uint32_t i; + + setup_git_directory(); + + midx = load_multi_pack_index(object_dir, 1); + if (!midx) + return 1; + + for (i = 0; i < midx->num_packs; i++) { + if (nth_bitmapped_pack(the_repository, midx, &pack, i) < 0) + return 1; + + printf("%s\n", pack_basename(pack.p)); + printf(" bitmap_pos: %"PRIuMAX"\n", (uintmax_t)pack.bitmap_pos); + printf(" bitmap_nr: %"PRIuMAX"\n", (uintmax_t)pack.bitmap_nr); + printf(" disjoint: %s\n", pack.disjoint & 0x1 ? "yes" : "no"); + } + + close_midx(midx); + + return 0; +} + int cmd__read_midx(int argc, const char **argv) { if (!(argc == 2 || argc == 3)) - usage("read-midx [--show-objects|--checksum|--preferred-pack] <object-dir>"); + usage("read-midx [--show-objects|--checksum|--preferred-pack|--bitmap] <object-dir>"); if (!strcmp(argv[1], "--show-objects")) return read_midx_file(argv[2], 1); @@ -111,5 +138,7 @@ int cmd__read_midx(int argc, const char **argv) return read_midx_checksum(argv[2]); else if (!strcmp(argv[1], "--preferred-pack")) return read_midx_preferred_pack(argv[2]); + else if (!strcmp(argv[1], "--bitmap")) + return read_midx_bitmapped_packs(argv[2]); return read_midx_file(argv[1], 0); } diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh index c4c6060cee..fd24e0c952 100755 --- a/t/t5319-multi-pack-index.sh +++ b/t/t5319-multi-pack-index.sh @@ -1157,4 +1157,62 @@ test_expect_success 'reader notices too-small revindex chunk' ' test_cmp expect.err err ' +test_expect_success 'disjoint packs are stored via the DISP chunk' ' + test_when_finished "rm -fr repo" && + git init repo && + ( + cd repo && + + for i in 1 2 3 4 5 + do + test_commit "$i" && + git repack -d || return 1 + done && + + find $objdir/pack -type f -name "*.idx" | xargs -n 1 basename | sort >packs && + + git multi-pack-index write --stdin-packs <packs && + test_must_fail test-tool read-midx --bitmap $objdir 2>err && + cat >expect <<-\EOF && + error: MIDX does not contain the DISP chunk + EOF + test_cmp expect err && + + sed -e "s/^/+/g" packs >in && + git multi-pack-index write --stdin-packs --bitmap \ + --preferred-pack="$(head -n1 <packs)" <in && + test-tool read-midx --bitmap $objdir >actual && + for i in $(test_seq $(wc -l <packs)) + do + sed -ne "${i}s/\.idx$/\.pack/p" packs && + echo " bitmap_pos: $(( $(( $i - 1 )) * 3 ))" && + echo " bitmap_nr: 3" && + echo " disjoint: yes" || return 1 + done >expect && + test_cmp expect actual + ) +' + +test_expect_success 'non-disjoint packs are detected' ' + test_when_finished "rm -fr repo" && + git init repo && + ( + cd repo && + + test_commit base && + git repack -d && + test_commit other && + git repack -a && + + ls -la .git/objects/pack/ && + + find $objdir/pack -type f -name "*.idx" | + sed -e "s/.*\/\(.*\)$/+\1/g" >in && + + test_must_fail git multi-pack-index write --stdin-packs \ + --bitmap <in 2>err && + grep "duplicate object.* among disjoint packs" err + ) +' + test_done
When a multi-pack bitmap is used to implement verbatim pack reuse (that is, when verbatim chunks from an on-disk packfile are copied directly[^1]), it does so by using its "preferred pack" as the source for pack-reuse. This allows repositories to pack the majority of their objects into a single (often large) pack, and then use it as the single source for verbatim pack reuse. This increases the amount of objects that are reused verbatim (and consequently, decrease the amount of time it takes to generate many packs). But this performance comes at a cost, which is that the preferred packfile must pace its growth with that of the entire repository in order to maintain the utility of verbatim pack reuse. As repositories grow beyond what we can reasonably store in a single packfile, the utility of verbatim pack reuse diminishes. Or, at the very least, it becomes increasingly more expensive to maintain as the pack grows larger and larger. It would be beneficial to be able to perform this same optimization over multiple packs, provided some modest constraints (most importantly, that the set of packs eligible for verbatim reuse are disjoint with respect to the objects that they contain). If we assume that the packs which we treat as candidates for verbatim reuse are disjoint with respect to their objects, we need to make only modest modifications to the verbatim pack-reuse code itself. Most notably, we need to remove the assumption that the bits in the reachability bitmap corresponding to objects from the single reuse pack begin at the first bit position. Future patches will unwind these assumptions and reimplement their existing functionality as special cases of the more general assumptions (e.g. that reuse bits can start anywhere within the bitset, but happen to start at 0 for all existing cases). This patch does not yet relax any of those assumptions. Instead, it implements a foundational data-structure, the "Disjoint Packs" (`DISP`) chunk of the multi-pack index. The `DISP` chunk's contents are described in detail here. Importantly, the `DISP` chunk contains information to map regions of a multi-pack index's reachability bitmap to the packs whose objects they represent. For now, this chunk is only written, not read (outside of the test-tool used in this patch to test the new chunk's behavior). Future patches will begin to make use of this new chunk. This patch implements reading (though no callers outside of the above one perform any reading) and writing this new chunk. It also extends the `--stdin-packs` format used by the `git multi-pack-index write` builtin to be able to designate that a given pack is to be marked as "disjoint" by prefixing it with a '+' character. [^1]: Modulo patching any `OFS_DELTA`'s that cross over a region of the pack that wasn't used verbatim. Signed-off-by: Taylor Blau <me@ttaylorr.com> --- Documentation/git-multi-pack-index.txt | 4 + Documentation/gitformat-pack.txt | 109 +++++++++++++++++++++++ builtin/multi-pack-index.c | 10 ++- midx.c | 116 ++++++++++++++++++++++--- midx.h | 5 ++ pack-bitmap.h | 9 ++ t/helper/test-read-midx.c | 31 ++++++- t/t5319-multi-pack-index.sh | 58 +++++++++++++ 8 files changed, 325 insertions(+), 17 deletions(-)