From: Taylor Blau <hidden> Date: 2021-02-10 23:03:21
This series describes and implements a reverse index for the multi-pack index,
based on a "pseudo-pack" which can be uniquely described by the multi-pack
index.
The details of the pseudo-pack, and multi-pack reverse index are laid out in
detail in the sixth patch.
This is in support of multi-pack reachability bitmaps, which contain objects
from the multi-pack index. Likewise, an object's bit position in a multi-pack
reachability bitmap is determined by its position with that multi-pack index's
pseudo pack.
In this series, there are no users of the multi-pack index, so this series is
mainly about laying the groundwork for implementing multi-pack bitmaps. This
series is the final prerequisite needed before we can implement multi-pack
bitmaps, which will come in the next series[1].
Since tb/pack-revindex-on-disk is queued to be merged to 'master', but hasn't
yet been merged, this series is based on that branch.
Thanks in advance for your review of this series, and all of the many other
series in support of multi-pack bitmaps.
[1]: If you're curious, you can find the patches in the tb/multi-pack-bitmaps
branch of my fork at https://github.com/ttaylorr/git.
Taylor Blau (9):
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 | 11 +-
Documentation/technical/multi-pack-index.txt | 5 +-
Documentation/technical/pack-format.txt | 83 +++++++
builtin/multi-pack-index.c | 10 +-
builtin/repack.c | 2 +-
midx.c | 239 ++++++++++++++++++-
midx.h | 11 +-
pack-revindex.c | 112 +++++++++
pack-revindex.h | 46 ++++
pack-write.c | 39 ++-
pack.h | 1 +
packfile.c | 3 +
t/helper/test-read-midx.c | 24 +-
t/t5319-multi-pack-index.sh | 39 +++
14 files changed, 591 insertions(+), 34 deletions(-)
--
2.30.0.667.g81c0cbc6fd
From: Taylor Blau <hidden> Date: 2021-02-10 23:03:21
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-02-10 23:03:30
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 | 11 ++-
Documentation/technical/multi-pack-index.txt | 5 +-
builtin/multi-pack-index.c | 10 +-
builtin/repack.c | 2 +-
midx.c | 97 ++++++++++++++++++--
midx.h | 2 +-
t/t5319-multi-pack-index.sh | 39 ++++++++
7 files changed, 151 insertions(+), 15 deletions(-)
@@ -27,6 +28,14 @@ OPTIONS Turn progress on/off explicitly. If neither is specified, progress is shown if standard error is connected to a terminal.+--preferred-pack=<pack>::+ When using the `write` subcommand, optionally specify the+ tie-breaking pack used when multiple packs contain the same+ object. Incompatible with other subcommands, including `repack`,+ which may repack the pack marked as preferred. If not given, the+ preferred pack is inferred from an existing `multi-pack-index`,+ if one exists, otherwise the pack with the lowest mtime.+ The following subcommands are available: write::
@@ -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`
@@ -24,6 +26,8 @@ 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_STRING(0,"preferred-pack",&opts.preferred_pack,N_("preferred-pack"),+N_("pack for reuse when computing a multi-pack bitmap")),OPT_BOOL(0,"progress",&opts.progress,N_("force progress reporting")),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")),
@@ -60,7 +67,8 @@ int cmd_multi_pack_index(int argc, const char **argv,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.preferred_pack,+flags);if(!strcmp(argv[0],"verify"))returnverify_midx_file(the_repository,opts.object_dir,flags);if(!strcmp(argv[0],"expire"))
@@ -513,6 +532,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)
@@ -540,7 +565,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\+--preferred-pack=test-BC-$bc.idxwrite2>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-02-10 23:03:46
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-02-10 23:03:48
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-02-10 23:04:11
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-02-10 23:04:44
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(+)
@@ -376,3 +376,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.+Crucially, the objects' positions within this pseudo-pack are the same+as their bit positions in a multi-pack reachability bitmap.++As a motivating example, consider the multi-pack reachability bitmap+(which does not yet exist, but is what we are building towards here). We+need each bit to correspond to an object covered by the midx, and we+need to be able to convert bit positions back to index positions (from+which we can get the oid, etc).++One solution is to let each bit position in the index correspond to+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. We can think of it as 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-02-10 23:05:01
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, 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.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 11 +++++
midx.h | 6 +++
pack-revindex.c | 112 ++++++++++++++++++++++++++++++++++++++++++++++++
pack-revindex.h | 46 ++++++++++++++++++++
packfile.c | 3 ++
5 files changed, 178 insertions(+)
@@ -292,6 +293,29 @@ 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;+}+intoffset_to_pack_pos(structpacked_git*p,off_tofs,uint32_t*pos){unsignedlo,hi;
@@ -346,3 +370,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-02-10 23:05:07
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 | 39 ++++++++++++++++++++++++++++-----------
pack.h | 1 +
2 files changed, 29 insertions(+), 11 deletions(-)
From: Taylor Blau <hidden> Date: 2021-02-10 23:05:28
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.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
midx.h | 1 +
2 files changed, 124 insertions(+)
@@ -841,6 +842,78 @@ static size_t write_midx_large_offsets(struct hashfile *f, uint32_t nr_large_offreturnwritten;}+structmidx_pack_order_data{+structpack_midx_entry*entries;+uint32_t*pack_perm;+};++staticintmidx_pack_order_cmp(constvoid*va,constvoid*vb,void*_data)+{+structmidx_pack_order_data*data=_data;++structpack_midx_entry*a=&data->entries[*(constuint32_t*)va];+structpack_midx_entry*b=&data->entries[*(constuint32_t*)vb];++uint32_tperm_a=data->pack_perm[a->pack_int_id];+uint32_tperm_b=data->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(structpack_midx_entry*entries,+uint32_t*pack_perm,+uint32_tentries_nr)+{+structmidx_pack_order_datadata;+uint32_t*pack_order;+uint32_ti;++data.entries=entries;+data.pack_perm=pack_perm;++ALLOC_ARRAY(pack_order,entries_nr);+for(i=0;i<entries_nr;i++)+pack_order[i]=i;+QSORT_S(pack_order,entries_nr,midx_pack_order_cmp,&data);++returnpack_order;+}++staticvoidwrite_midx_reverse_index(char*midx_name,unsignedchar*midx_hash,+uint32_t*pack_order,+uint32_tentries_nr)+{+structstrbufbuf=STRBUF_INIT;++strbuf_addf(&buf,"%s-%s.rev",midx_name,hash_to_hex(midx_hash));++write_rev_file_order(buf.buf,pack_order,entries_nr,midx_hash,+WRITE_REV);++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,
It seems a little odd to me that the list of objects happens after
the header information. Probably doesn't matter in your test cases,
but I sometimes use the test helpers to diagnose data during development
and could see piping this output into 'less' and wanting the header
at the top.
Thanks,
-Stolee
I was initially thinking we should use something like
'struct object_id' here, but the hash we are storing
doesn't correspond to an object, which would be
confusing. I suppose this is the most correct thing
to do.
It seems a little odd to me that the list of objects happens after
the header information. Probably doesn't matter in your test cases,
but I sometimes use the test helpers to diagnose data during development
and could see piping this output into 'less' and wanting the header
at the top.
Indeed. In theory you could pipe to tail instead (or to less and
immediately hit 'G'), but I can't think of a good reason that this would
have appeared above the header when I originally wrote the patch.
Anyway, it doesn't seem that the tests care about where this is (they're
just looking for for a line that begins with the object id and ends with
its offset), so I think this could probably be moved without thinking
too hard about it.
From: Taylor Blau <hidden> Date: 2021-02-11 02:36:35
On Wed, Feb 10, 2021 at 09:33:36PM -0500, Derrick Stolee wrote:
On 2/10/21 6:02 PM, Taylor Blau wrote:
quoted
+ unsigned char midx_hash[GIT_MAX_RAWSZ];
I was initially thinking we should use something like
'struct object_id' here, but the hash we are storing
doesn't correspond to an object, which would be
confusing. I suppose this is the most correct thing
to do.
Yeah. There are a number of places that abuse the unsigned char array
inside of object_id, but there's no good reason to.
Thanks,
Taylor
On 2/10/21 6:03 PM, Taylor Blau wrote:> +Instead of mapping between offset, pack-, and index position, this
The "pack-," should be paired with "index-position" or drop the
hyphen in both cases. Perhaps just be explicit, especially since
"position" doesn't match with "offset":
Instead of mapping between pack offset, pack position, and index
position, ...
+reverse index maps between an object's position within the midx, and
+that object's position within a pseudo-pack that the midx describes.
nit: use multi-pack-index or MIDX, not lower-case 'midx'.
+Crucially, the objects' positions within this pseudo-pack are the same
+as their bit positions in a multi-pack reachability bitmap.
+
+As a motivating example, consider the multi-pack reachability bitmap
+(which does not yet exist, but is what we are building towards here). We
+need each bit to correspond to an object covered by the midx, and we
+need to be able to convert bit positions back to index positions (from
+which we can get the oid, etc).
These paragraphs are awkward. Instead of operating in the hypothetical
world of reachability bitmaps, focus on the fact that bitmaps need
a bidirectional mapping between "bit position" and an object ID.
Here is an attempt to reword some of the context you are using here.
Feel free to take as much or as little as you want.
The multi-pack-index stores the object IDs in lexicographical order
(lex-order) to allow binary search. To allow compressible reachability
bitmaps to pair with a multi-pack-index, a different ordering is
required. When paired with a single packfile, the order used is the
object order within the packfile (called the pack-order). Construct
a "pseudo-pack" by concatenating all tracked packfiles in the
multi-pack-index. We now need a mapping between the lex-order and the
pseudo-pack-order.
+One solution is to let each bit position in the index correspond to
+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. We can think of it as 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`).
The rest of these details make sense and sufficiently motivate the
ordering, once the concept is clear.
Thanks,
-Stolee
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, 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.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 11 +++++
midx.h | 6 +++
pack-revindex.c | 112 ++++++++++++++++++++++++++++++++++++++++++++++++
pack-revindex.h | 46 ++++++++++++++++++++
packfile.c | 3 ++
5 files changed, 178 insertions(+)
'struct multi_pack_index' has a 'hash_len' member that you could
use here. It would allow a different hash length in the stored
file than the one required by the repository. Except...
...this assumes the hash is of the same length as the_hash_algo,
so you are doing the right thing. Currently, I think we check
that 'm->hash_len == the_hash_algo->rawsz' on load. We'll need
to check this again later when in the transition phase of the
new hash work.
(No changes are needed to your patch.)
Thanks,
-Stolee
This series describes and implements a reverse index for the multi-pack index,
based on a "pseudo-pack" which can be uniquely described by the multi-pack
index.
The details of the pseudo-pack, and multi-pack reverse index are laid out in
detail in the sixth patch.
This is in support of multi-pack reachability bitmaps, which contain objects
from the multi-pack index. Likewise, an object's bit position in a multi-pack
reachability bitmap is determined by its position with that multi-pack index's
pseudo pack.
This has been a lot of work, but I'm impressed with the progress here.
This series is good prep, and my comments are very minor.
Since the need for these multi-pack-index-<hash>.rev files doesn't show
up until the reachability bitmaps can be paired with MIDX files, it
would make sense to hold this series in 'next' until that one also
stabilizes and they merge to 'master' together.
Thanks,
-Stolee
From: Taylor Blau <hidden> Date: 2021-02-11 03:04:11
On Wed, Feb 10, 2021 at 09:48:20PM -0500, Derrick Stolee wrote:
nit: use multi-pack-index or MIDX, not lower-case 'midx'.
Thanks.
quoted
+Crucially, the objects' positions within this pseudo-pack are the same
+as their bit positions in a multi-pack reachability bitmap.
+
+As a motivating example, consider the multi-pack reachability bitmap
+(which does not yet exist, but is what we are building towards here). We
+need each bit to correspond to an object covered by the midx, and we
+need to be able to convert bit positions back to index positions (from
+which we can get the oid, etc).
These paragraphs are awkward. Instead of operating in the hypothetical
world of reachability bitmaps, focus on the fact that bitmaps need
a bidirectional mapping between "bit position" and an object ID.
Hmm. I could buy that these paragraphs are awkward, but I'm not sure
that what you proposed makes it less so.
I may be a bad person to judge what you wrote, since I am familiar with
the details of what it's describing. But my thoughts on that second and
third paragraph are basically:
- define the valid orderings we might consider objects in a MIDX by,
indicating which of those orderings we're going to use for
multi-pack bitmaps
- motivate the need for a mapping between lexicographic order and
pseudo-pack order
Here is an attempt to reword some of the context you are using here.
Feel free to take as much or as little as you want.
The multi-pack-index stores the object IDs in lexicographical order
(lex-order) to allow binary search. To allow compressible reachability
bitmaps to pair with a multi-pack-index, a different ordering is
required. When paired with a single packfile, the order used is the
object order within the packfile (called the pack-order). Construct
a "pseudo-pack" by concatenating all tracked packfiles in the
multi-pack-index. We now need a mapping between the lex-order and the
pseudo-pack-order.
I struggled with what you wrote because I couldn't seem to neatly
place/replace that paragraph in with the existing text without referring
to yet-undefined concepts.
Maybe the confusion lies in the fact that we stray too far from the
point in the second and third paragraphs. What if we reordered the
second, third, and fourth paragraph like this:
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, 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:
[snip]
The rest of these details make sense and sufficiently motivate the
ordering, once the concept is clear.
Thanks,
-Stolee
From: Taylor Blau <hidden> Date: 2021-02-11 03:05:36
On Wed, Feb 10, 2021 at 09:53:23PM -0500, Derrick Stolee wrote:
...this assumes the hash is of the same length as the_hash_algo,
so you are doing the right thing. Currently, I think we check
that 'm->hash_len == the_hash_algo->rawsz' on load. We'll need
to check this again later when in the transition phase of the
new hash work.
(No changes are needed to your patch.)
From: Taylor Blau <hidden> Date: 2021-02-11 03:07:46
On Wed, Feb 10, 2021 at 09:58:18PM -0500, Derrick Stolee wrote:
This series is good prep, and my comments are very minor.
Thanks for your review, especially on a series like this one that adds
lots of code without any users :).
Since the need for these multi-pack-index-<hash>.rev files doesn't show
up until the reachability bitmaps can be paired with MIDX files, it
would make sense to hold this series in 'next' until that one also
stabilizes and they merge to 'master' together.
That's fine with me. It would be OK to merge this down to 'master', too,
since this is all dead code. In fact, that may be easier to work with,
since the next topic can be based directly off 'master' instead of
having to keep this branch around forever.
Either is fine, though.
Thanks,
Taylor
@@ -27,6 +28,14 @@ OPTIONS Turn progress on/off explicitly. If neither is specified, progress is shown if standard error is connected to a terminal.+--preferred-pack=<pack>::+ When using the `write` subcommand, optionally specify the+ tie-breaking pack used when multiple packs contain the same+ object. Incompatible with other subcommands, including `repack`,
I think this shouldn't be an option of the 'git multi-pack-index'
command but an option of its 'write' subcommand.
From: Taylor Blau <hidden> Date: 2021-02-15 16:05:03
On Thu, Feb 11, 2021 at 08:33:14PM +0100, SZEDER Gábor wrote:
quoted
+--preferred-pack=<pack>::
+ When using the `write` subcommand, optionally specify the
+ tie-breaking pack used when multiple packs contain the same
+ object. Incompatible with other subcommands, including `repack`,
I think this shouldn't be an option of the 'git multi-pack-index'
command but an option of its 'write' subcommand.
:-/. I wrote a lengthy response on Friday, but Gmail must have eaten it.
The gist of my response was that the intermingling of sub-commands with
options from other sub-commands goes deeper than just the documentation,
since command-line arguments are only parsed once in
builtin/multi-pack-index.c.
I explored whether or not it would be worth it to parse the common
options first, and then have separate options for each of the
sub-commands (as is done in the commit-graph builtin). But, this is
tricky, since we accept common options on either side of the sub-command
(i.e., we'd expect both 'git multi-pack-index --object-dir=... write' to
behave the same as 'git multi-pack-index write --object-dir=...').
So you could let the first call to parse_options() parse all of the
arguments, but then specialized arguments (e.g., 'repack --batch-size')
would cause the parse-options API to barf because the first call to
parse_options() doesn't recognize '--batch-size'.
I think the easiest way to do it would be to pass
PARSE_OPT_STOP_AT_NON_OPTION, and then let the subsequent calls to
parse_options() pass an array of option structs that also includes the
common options so they can be parsed on either side of the sub-command.
Obviously this leads to a lot of rather unfortunate duplication. So,
I'm content to leave it all as-is, and let the multi-pack-index
builtin check the disallowed combinations itself (e.g., if you passed
'--preferred-pack' but aren't in 'write' mode, then we should complain).
I can certainly move this piece of documentation into the 'write'
section, though, which should alleviate your immediate concern.
Thanks,
Taylor
On Thu, Feb 11, 2021 at 08:33:14PM +0100, SZEDER Gábor wrote:
quoted
quoted
+--preferred-pack=<pack>::
+ When using the `write` subcommand, optionally specify the
+ tie-breaking pack used when multiple packs contain the same
+ object. Incompatible with other subcommands, including `repack`,
I think this shouldn't be an option of the 'git multi-pack-index'
command but an option of its 'write' subcommand.
:-/. I wrote a lengthy response on Friday, but Gmail must have eaten it.
The gist of my response was that the intermingling of sub-commands with
options from other sub-commands goes deeper than just the documentation,
since command-line arguments are only parsed once in
builtin/multi-pack-index.c.
I explored whether or not it would be worth it to parse the common
options first, and then have separate options for each of the
sub-commands (as is done in the commit-graph builtin). But, this is
tricky, since we accept common options on either side of the sub-command
(i.e., we'd expect both 'git multi-pack-index --object-dir=... write' to
behave the same as 'git multi-pack-index write --object-dir=...').
So you could let the first call to parse_options() parse all of the
arguments, but then specialized arguments (e.g., 'repack --batch-size')
would cause the parse-options API to barf because the first call to
parse_options() doesn't recognize '--batch-size'.
I think the easiest way to do it would be to pass
PARSE_OPT_STOP_AT_NON_OPTION, and then let the subsequent calls to
parse_options() pass an array of option structs that also includes the
common options so they can be parsed on either side of the sub-command.
Obviously this leads to a lot of rather unfortunate duplication. So,
I'm content to leave it all as-is, and let the multi-pack-index
builtin check the disallowed combinations itself (e.g., if you passed
'--preferred-pack' but aren't in 'write' mode, then we should complain).
I can certainly move this piece of documentation into the 'write'
section, though, which should alleviate your immediate concern.
I may be missing something, but...
It sounds to me like you're imagining this is more complex than it is
because you don't know about some/all of parse_options_concat() or
PARSE_OPT_KEEP_*.
See e.g. cmd_{switch,restore} in builti/checkout.c, or the entire family
of diff-like commands where we do parse_options() followed by
setup_revisions(). We've got a lot of commands that parse options in a
piecemeal manner.
At no point do you need to re-parse the options. You just have the
common command parse as far as it gets, and leave anything else in
argv/argc for sub-commands like "write".
I think the problem is you read the builtin/commit-graph.c code, it
could really benefit from using parse_options_concat(), now things like
"object-directory" are copy/pasted in that file. See 2087182272
(checkout: split options[] array in three pieces, 2019-03-29) for a
commit which simplified that sort of code.
In this case you'd share the "opts_multi_pack_index" struct between the
various commands, it would just have unused fields for "write" that
aren't used by "verify" or whatever.
The PARSE_OPT_STOP_AT_NON_OPTION flag isn't for what you're doing with
"write" here, since as your test shows you're doing:
git multi-pack-index <ALL_OPTS> <SUBCOMMAND>
But PARSE_OPT_STOP_AT_NON_OPTION is for cases like "git-remote" that do:
git multi-pack-index <COMMOT_OPTS> <SUBCOMMAND> <SUBCOMMAND_OPTS>
(Or maybe you really want the latter, and the test change isn't
representative).
So then we want to stop at the first non-option, i.e. the subcommand. I
think it's good practice not to emulate how "git remote" works for new
commands, which makes things a bit simpler to implement.
You say "since we accept common options on either side of the
sub-command" but without PARSE_OPT_STOP_AT_NON_OPTION this works, since
if you can parse everything you'll have "write" left, but if you truly
have unknown options you'll have more than that in argv.
All of the above shouldn't be taken as a "your patch should change"
comment, maybe it's fine as-is.
I just replied because it sounded like you didn't spot how to easily use
parse_options() to do this sort of thing. It's actually rather easy.
A trivial cleanup series as a follow-up to my comments in
https://lore.kernel.org/git/87r1lhb6z7.fsf@evledraar.gmail.com/
Ævar Arnfjörð Bjarmason (5):
commit-graph: define common usage with a macro
commit-graph: remove redundant handling of -h
commit-graph: use parse_options_concat()
commit-graph: refactor dispatch loop for style
commit-graph: show usage on "commit-graph [write|verify] garbage"
builtin/commit-graph.c | 102 ++++++++++++++++++++++------------------
t/t5318-commit-graph.sh | 7 +++
2 files changed, 62 insertions(+), 47 deletions(-)
--
2.30.0.284.gd98b1dd5eaa7
Share the usage message between these three variables by using a
macro. Before this new options needed to copy/paste the usage
information, see e.g. 809e0327f5 (builtin/commit-graph.c: introduce
'--max-new-filters=<n>', 2020-09-18).
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
builtin/commit-graph.c | 29 +++++++++++++++--------------
1 file changed, 15 insertions(+), 14 deletions(-)
If we don't handle the -h option here like most parse_options() users
we'll fall through and it'll do the right thing for us.
I think this code added in 4ce58ee38d (commit-graph: create
git-commit-graph builtin, 2018-04-02) was always redundant,
parse_options() did this at the time, and the commit-graph code never
used PARSE_OPT_NO_INTERNAL_HELP.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
builtin/commit-graph.c | 4 ----
t/t5318-commit-graph.sh | 5 +++++
2 files changed, 5 insertions(+), 4 deletions(-)
I think it's more readable to have one if/elsif/else chain here than
the code this replaces.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
builtin/commit-graph.c | 16 +++++++---------
1 file changed, 7 insertions(+), 9 deletions(-)
Make use of the parse_options_concat() so we don't need to copy/paste
common options like --object-dir. This is inspired by a similar change
to "checkout" in 2087182272
(checkout: split options[] array in three pieces, 2019-03-29).
A minor behavior change here is that now we're going to list both
--object-dir and --progress first, before we'd list --progress along
with other options.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
builtin/commit-graph.c | 43 ++++++++++++++++++++++++------------------
1 file changed, 25 insertions(+), 18 deletions(-)
@@ -44,6 +44,21 @@ static struct opts_commit_graph {intenable_changed_paths;}opts;+staticstructoption*add_common_options(structoption*prevopts)+{+structoptionoptions[]={+OPT_STRING(0,"object-dir",&opts.obj_dir,+N_("dir"),+N_("the object directory to store the graph")),+OPT_BOOL(0,"progress",&opts.progress,+N_("force progress reporting")),+OPT_END()+};+structoption*newopts=parse_options_concat(options,prevopts);+free(prevopts);+returnnewopts;+}+staticstructobject_directory*find_odb(structrepository*r,constchar*obj_dir){
@@ -75,22 +90,20 @@ static int graph_verify(int argc, const char **argv)intfd;structstatst;intflags=0;-+structoption*options=NULL;staticstructoptionbuiltin_commit_graph_verify_options[]={-OPT_STRING(0,"object-dir",&opts.obj_dir,-N_("dir"),-N_("the object directory to store the graph")),OPT_BOOL(0,"shallow",&opts.shallow,N_("if the commit-graph is split, only verify the tip file")),-OPT_BOOL(0,"progress",&opts.progress,N_("force progress reporting")),OPT_END(),};+options=parse_options_dup(builtin_commit_graph_verify_options);+options=add_common_options(options);trace2_cmd_mode("verify");opts.progress=isatty(2);argc=parse_options(argc,argv,NULL,-builtin_commit_graph_verify_options,+options,builtin_commit_graph_verify_usage,0);if(!opts.obj_dir)
@@ -205,11 +218,8 @@ static int graph_write(int argc, const char **argv)intresult=0;enumcommit_graph_write_flagsflags=0;structprogress*progress=NULL;-+structoption*options=NULL;staticstructoptionbuiltin_commit_graph_write_options[]={-OPT_STRING(0,"object-dir",&opts.obj_dir,-N_("dir"),-N_("the object directory to store the graph")),OPT_BOOL(0,"reachable",&opts.reachable,N_("start walk at all refs")),OPT_BOOL(0,"stdin-packs",&opts.stdin_packs,
@@ -220,7 +230,6 @@ static int graph_write(int argc, const char **argv)N_("include all commits already in the commit-graph file")),OPT_BOOL(0,"changed-paths",&opts.enable_changed_paths,N_("enable computation for changed paths")),-OPT_BOOL(0,"progress",&opts.progress,N_("force progress reporting")),OPT_CALLBACK_F(0,"split",&write_opts.split_flags,NULL,N_("allow writing an incremental commit-graph file"),PARSE_OPT_OPTARG|PARSE_OPT_NONEG,
@@ -312,12 +323,8 @@ static int graph_write(int argc, const char **argv)intcmd_commit_graph(intargc,constchar**argv,constchar*prefix){-staticstructoptionbuiltin_commit_graph_options[]={-OPT_STRING(0,"object-dir",&opts.obj_dir,-N_("dir"),-N_("the object directory to store the graph")),-OPT_END(),-};+structoption*no_options=parse_options_dup(NULL);+structoption*builtin_commit_graph_options=add_common_options(no_options);git_config(git_default_config,NULL);argc=parse_options(argc,argv,prefix,
Change the parse_options() invocation in the commit-graph code to make
sense. We're calling it twice, once for common options parsing, and
then for the sub-commands.
But we never checked if we had something leftover in argc in "write"
or "verify", as a result we'd silently accept garbage in these
subcommands. Let's not do that.
Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
builtin/commit-graph.c | 10 ++++++++--
t/t5318-commit-graph.sh | 4 +++-
2 files changed, 11 insertions(+), 3 deletions(-)
@@ -261,7 +264,10 @@ static int graph_write(int argc, const char **argv)argc=parse_options(argc,argv,NULL,options,-builtin_commit_graph_write_usage,0);+builtin_commit_graph_write_usage,+PARSE_OPT_KEEP_UNKNOWN);+if(argc)+usage_with_options(builtin_commit_graph_write_usage,options);if(opts.reachable+opts.stdin_packs+opts.stdin_commits>1)die(_("use at most one of --reachable, --stdin-commits, or --stdin-packs"));
From: Taylor Blau <hidden> Date: 2021-02-15 18:53:01
On Mon, Feb 15, 2021 at 07:41:16PM +0100, Ævar Arnfjörð Bjarmason wrote:
Make use of the parse_options_concat() so we don't need to copy/paste
common options like --object-dir. This is inspired by a similar change
to "checkout" in 2087182272
(checkout: split options[] array in three pieces, 2019-03-29).
A minor behavior change here is that now we're going to list both
--object-dir and --progress first, before we'd list --progress along
with other options.
"Behavior change" referring only to the output of `git commit-graph -h`,
no?
Looking at the code (and understanding this whole situation a little bit
better), I'd think that this wouldn't cause us to parse anything
differently before or after this change, right?
@@ -75,22 +90,20 @@ static int graph_verify(int argc, const char **argv) int fd; struct stat st; int flags = 0;-+ struct option *options = NULL; static struct option builtin_commit_graph_verify_options[] = {- OPT_STRING(0, "object-dir", &opts.obj_dir,- N_("dir"),- N_("the object directory to store the graph")), OPT_BOOL(0, "shallow", &opts.shallow, N_("if the commit-graph is split, only verify the tip file")),- OPT_BOOL(0, "progress", &opts.progress, N_("force progress reporting")), OPT_END(), };+ options = parse_options_dup(builtin_commit_graph_verify_options);
Another nitpick, but I'd rather see the initialization of "options" and
its declaration be on the same line, after declaring
builtin_commit_graph_verify_options.
From: Taylor Blau <hidden> Date: 2021-02-15 18:54:18
On Mon, Feb 15, 2021 at 07:41:17PM +0100, Ævar Arnfjörð Bjarmason wrote:
I think it's more readable to have one if/elsif/else chain here than
the code this replaces.
FWIW, I find the pre-image more readable than what you are proposing
replacing it with here.
Of course, I have no doubts about the obvious correctness of this patch;
I'm merely suggesting that I wouldn't be sad to see us apply the first
three patches, and the fifth patch, but drop this one.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-02-15 19:07:30
On Mon, Feb 15, 2021 at 07:41:18PM +0100, Ævar Arnfjörð Bjarmason wrote:
Change the parse_options() invocation in the commit-graph code to make
sense. We're calling it twice, once for common options parsing, and
then for the sub-commands.
But we never checked if we had something leftover in argc in "write"
or "verify", as a result we'd silently accept garbage in these
subcommands. Let's not do that.
...Implicit in all of this is that we need to pass
PARSE_OPT_KEEP_UNKNOWN to have the sub-commands' call to parse_options()
leave extra cruft alone so we can check for its existence with an "if (argc)".
Makes sense, thanks.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-02-15 19:54:35
On Mon, Feb 15, 2021 at 01:51:35PM -0500, Taylor Blau wrote:
Another nitpick, but I'd rather see the initialization of "options" and
its declaration be on the same line, after declaring
builtin_commit_graph_verify_options.
Ignore me; the NULL initialization is important.
Thanks,
Taylor
On Mon, Feb 15, 2021 at 07:41:16PM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
Make use of the parse_options_concat() so we don't need to copy/paste
common options like --object-dir. This is inspired by a similar change
to "checkout" in 2087182272
(checkout: split options[] array in three pieces, 2019-03-29).
A minor behavior change here is that now we're going to list both
--object-dir and --progress first, before we'd list --progress along
with other options.
"Behavior change" referring only to the output of `git commit-graph -h`,
no?
Looking at the code (and understanding this whole situation a little bit
better), I'd think that this wouldn't cause us to parse anything
differently before or after this change, right?
Indeed, I just mean the "-h" or "--invalid-opt" output changed in the
order we show the options in.
@@ -44,6 +44,21 @@ static struct opts_commit_graph {intenable_changed_paths;}opts;+staticstructoption*add_common_options(structoption*prevopts)+{+structoptionoptions[]={+OPT_STRING(0,"object-dir",&opts.obj_dir,+N_("dir"),+N_("the object directory to store the graph")),+OPT_BOOL(0,"progress",&opts.progress,+N_("force progress reporting")),+OPT_END()+};
I'm nitpicking, but I wouldn't be sad to see this called "common"
instead".
Can't this also be declared statically?
It happens to work now to do that, but try it in builtin/checkout.c and
you'll see it blows up with a wall of "initializer element is not
constant".
Probably better to be consistent in parse_options() usage than make it
safe for that sort of use...
@@ -75,22 +90,20 @@ static int graph_verify(int argc, const char **argv) int fd; struct stat st; int flags = 0;-+ struct option *options = NULL; static struct option builtin_commit_graph_verify_options[] = {- OPT_STRING(0, "object-dir", &opts.obj_dir,- N_("dir"),- N_("the object directory to store the graph")), OPT_BOOL(0, "shallow", &opts.shallow, N_("if the commit-graph is split, only verify the tip file")),- OPT_BOOL(0, "progress", &opts.progress, N_("force progress reporting")), OPT_END(), };+ options = parse_options_dup(builtin_commit_graph_verify_options);
Another nitpick, but I'd rather see the initialization of "options" and
its declaration be on the same line, after declaring
builtin_commit_graph_verify_options.
As you noted in your own reply "the NULL initialization is important",
or more specifically: We're doing this dance here (and in other existing
code, e.g. checkout.c) to trampoline from the stack ot the heap.
@@ -312,12 +323,8 @@ static int graph_write(int argc, const char **argv) int cmd_commit_graph(int argc, const char **argv, const char *prefix) {- static struct option builtin_commit_graph_options[] = {- OPT_STRING(0, "object-dir", &opts.obj_dir,- N_("dir"),- N_("the object directory to store the graph")),- OPT_END(),- };+ struct option *no_options = parse_options_dup(NULL);
Hmm. Why bother calling add_common_options at all here?
I assume you mean in this line just below what you quoted:
struct option *builtin_commit_graph_options = add_common_options(no_options);
Do you mean why not do the whole thing in graph_{verify,write}() and
only show the usage if we fail here?
Yeah arguably that makes more sense, but I wanted to just focus on
refactoring existing behavior & get rid of the copy/pasted options
rather than start a bigger rewrite of "maybe we shouldn't show this
rather useless help info if we die here....".
From: Taylor Blau <hidden> Date: 2021-02-15 21:02:42
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-02-15 21:02:42
Here's a few patches that we could add to the beginning of this series,
or queue up separately.
I think that these are all fairly straightforward, but it would be good
to have Ævar take a look and make sure I'm not doing anything wrong
here.
I'll plan to send a v2 of the reverse index series in a few days with
these four new patches at the beginning.
Taylor Blau (4):
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 | 155 +++++++++++++++++++++++++++++--------
1 file changed, 124 insertions(+), 31 deletions(-)
--
2.30.0.667.g81c0cbc6fd
From: Taylor Blau <hidden> Date: 2021-02-15 21:02:42
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-02-15 21:02:43
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-02-15 21:02:43
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]);}
@@ -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;
Funnily enough we could also just do:
opts.flags = isatty(2);
Since there's a grand total of one flag it knows about, and
MIDX_PROGRESS is defined as 1.
Not the problem of this series really, just a nit: In efbc3aee08d (midx:
add MIDX_PROGRESS flag, 2019-10-21) we added this flag, and around the
same time the similar commit-graph code got refactored to have an enum
of flags in 5af80394521 (commit-graph: collapse parameters into flags,
2019-06-12).
I prefer the commit-graph way of having a clean boundary between the two
a bit more, and then just setting a flag based on an OPT_BOOL...
From: Taylor Blau <hidden> Date: 2021-02-15 21:46:02
On Mon, Feb 15, 2021 at 10:39:16PM +0100, Ævar Arnfjörð Bjarmason wrote:
On Mon, Feb 15 2021, Taylor Blau wrote:
quoted
@@ -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;
Funnily enough we could also just do:
opts.flags = isatty(2);
Since there's a grand total of one flag it knows about, and
MIDX_PROGRESS is defined as 1.
:-). I have a handful of branches that add some new flags (including the
original series I sent down-thread), so I'm not sure that I'm in favor
of this (admittedly cute) hack.
Not the problem of this series really, just a nit: In efbc3aee08d (midx:
add MIDX_PROGRESS flag, 2019-10-21) we added this flag, and around the
same time the similar commit-graph code got refactored to have an enum
of flags in 5af80394521 (commit-graph: collapse parameters into flags,
2019-06-12).
Hmm. I don't really have a strong opinion either way. I'd like to avoid
steering too far away from my original goal of multi-pack reverse
indexes, at least for now...
I prefer the commit-graph way of having a clean boundary between the two
a bit more, and then just setting a flag based on an OPT_BOOL...
Me too. But if you can part ways with it, it cuts down on the code
duplication (since callers in the sub-commands don't have to set that
bit on the flags themselves).
OTOH, we could keep half of this change and store the flags in the
options structure in addition to the progress field, then set the
appropriate bit in "flags" in cmd_builtin_multi_pack_index().
But I think at that point you're already sharing the flags field
everywhere, so you're just as well off to have something like what's
written in this patch here.
I don't have strong feelings either way.
Thanks,
Taylor
Not a new issue, but curious that in the commit-graph.c code we'll first
validate, but here write garbage into the trace2_cmd_mode() before
potentially dying.
if (!strcmp(argv[0], "repack"))
- return midx_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"))
- return write_midx_file(opts.object_dir, opts.flags);
- if (!strcmp(argv[0], "verify"))
- return verify_midx_file(the_repository, opts.object_dir, opts.flags);
- if (!strcmp(argv[0], "expire"))
- return expire_midx_packs(the_repository, opts.object_dir, opts.flags);
-
- die(_("unrecognized subcommand: %s"), argv[0]);
+ return cmd_multi_pack_index_repack(argc, argv);
+ else if (!strcmp(argv[0], "write"))
+ return cmd_multi_pack_index_write(argc, argv);
+ else if (!strcmp(argv[0], "verify"))
+ return cmd_multi_pack_index_verify(argc, argv);
+ else if (!strcmp(argv[0], "expire"))
+ return cmd_multi_pack_index_expire(argc, argv);
+ else
+ die(_("unrecognized subcommand: %s"), argv[0]);
I realize this is the existing behavior, but let's just make this die()
be the usage_with_options() we emit above in this case?
So maybe this on top?
From: Taylor Blau <hidden> Date: 2021-02-15 22:35:37
On Mon, Feb 15, 2021 at 10:54:31PM +0100, Ævar Arnfjörð Bjarmason wrote:
On Mon, Feb 15 2021, Taylor Blau wrote:
quoted
trace2_cmd_mode(argv[0]);
Not a new issue, but curious that in the commit-graph.c code we'll first
validate, but here write garbage into the trace2_cmd_mode() before
potentially dying.
Yeah, that's a good catch.
I realize this is the existing behavior, but let's just make this die()
be the usage_with_options() we emit above in this case?
So maybe this on top?
I split this into two patches: one to move the trace2_cmd_mode() calls
around, and another to replace the final 'die()' with the usage text.
Like I said in my review of your patches to the commit-graph builtin
here:
https://lore.kernel.org/git/YCrDGhIq7kU57p1s@nand.local/
I don't find the 'if (argc && ...)' style more readable, so the second
patch looks like this instead:
On Mon, Feb 15, 2021 at 10:54:31PM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
On Mon, Feb 15 2021, Taylor Blau wrote:
quoted
trace2_cmd_mode(argv[0]);
Not a new issue, but curious that in the commit-graph.c code we'll first
validate, but here write garbage into the trace2_cmd_mode() before
potentially dying.
Yeah, that's a good catch.
quoted
I realize this is the existing behavior, but let's just make this die()
be the usage_with_options() we emit above in this case?
So maybe this on top?
I split this into two patches: one to move the trace2_cmd_mode() calls
around, and another to replace the final 'die()' with the usage text.
Thanks for picking it up.
Like I said in my review of your patches to the commit-graph builtin
here:
https://lore.kernel.org/git/YCrDGhIq7kU57p1s@nand.local/
I don't find the 'if (argc && ...)' style more readable, so the second
patch looks like this instead:
*Nod* FWIW (and this is getting way to nit-y) I don't disagree with you
about the "argc &&" being not very readable,
I just lean more on the side of getting rid of duplicate branches,
you'll still need the if (!argc) usage(...) case above without that
pattern, or some replacement for it.
But we can have our cake (not re-check argc all the time) and eat it too
(not copy/paste usage_with_options()). Isn't it beautiful?
diff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c
index caf0248a98..7ff50439f8 100644
--- a/builtin/multi-pack-index.c
+++ b/builtin/multi-pack-index.c
@@ -144,12 +144,8 @@ int cmd_multi_pack_index(int argc, const char **argv,
if (!opts.object_dir)
opts.object_dir = get_object_directory();
- if (argc == 0)
- usage_with_options(builtin_multi_pack_index_usage,
- builtin_multi_pack_index_options);
-
- trace2_cmd_mode(argv[0]);
-
+ if (!argc)
+ goto usage;
if (!strcmp(argv[0], "repack"))
return cmd_multi_pack_index_repack(argc, argv);
else if (!strcmp(argv[0], "write"))
@@ -159,5 +155,7 @@ int cmd_multi_pack_index(int argc, const char **argv,
else if (!strcmp(argv[0], "expire"))
return cmd_multi_pack_index_expire(argc, argv);
else
- die(_("unrecognized subcommand: %s"), argv[0]);
+usage:
+ usage_with_options(builtin_multi_pack_index_usage,
+ builtin_multi_pack_index_options);
}
:)
From: Taylor Blau <hidden> Date: 2021-02-15 23:52:13
On Tue, Feb 16, 2021 at 12:11:08AM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
I split this into two patches: one to move the trace2_cmd_mode() calls
around, and another to replace the final 'die()' with the usage text.
Thanks for picking it up.
Of course. This has been quite a fun digression :-).
quoted
Like I said in my review of your patches to the commit-graph builtin
here:
https://lore.kernel.org/git/YCrDGhIq7kU57p1s@nand.local/
I don't find the 'if (argc && ...)' style more readable, so the second
patch looks like this instead:
*Nod* FWIW (and this is getting way to nit-y) I don't disagree with you
about the "argc &&" being not very readable,
I just lean more on the side of getting rid of duplicate branches,
you'll still need the if (!argc) usage(...) case above without that
pattern, or some replacement for it.
But we can have our cake (not re-check argc all the time) and eat it too
(not copy/paste usage_with_options()). Isn't it beautiful?
Heh; I'm not sure that I'd call adding a goto "beautiful", but I
actually do find this one more readable. I dunno, honestly, I'm happy to
squash it in to the last commit on top, but honestly I don't really care
strongly one way or another ;).
quoted
Is it OK if I use your Signed-off-by on both of those two new patches?
Yes please, should have included it to begin with.
I think this test already exists in t0012-help.sh, since it
tests bogus options for all of the builtins. (I can guarantee
that I wouldn't have thought to add the check without some
instance like that.)
Thanks,
-Stolee
On Mon, Feb 15, 2021 at 07:41:17PM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
I think it's more readable to have one if/elsif/else chain here than
the code this replaces.
FWIW, I find the pre-image more readable than what you are proposing
replacing it with here.
Of course, I have no doubts about the obvious correctness of this patch;
I'm merely suggesting that I wouldn't be sad to see us apply the first
three patches, and the fifth patch, but drop this one.
I agree with all of your points here. I think that compared to the
current code at-rest, the new version might be preferred. It's a little
dense, which is my only complaint.
The issue comes for the future: what if we need to add a third verb
to 'git commit-graph'? Then extending this new option looks worse since
we would check 'argc' three times.
The other patches solve real readability problems or reorganize the code
to use other concepts within the codebase. This one is much more optional.
Thanks,
-Stolee
On Mon, Feb 15, 2021 at 10:39:16PM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
Funnily enough we could also just do:
opts.flags = isatty(2);
Since there's a grand total of one flag it knows about, and
MIDX_PROGRESS is defined as 1.
:-). I have a handful of branches that add some new flags (including the
original series I sent down-thread), so I'm not sure that I'm in favor
of this (admittedly cute) hack.
It's also _wrong_ if the user passes in '--progress' but redirects stderr
to a file. I don't know why someone would want to do that, but they
could, and we honor that throughout all commands.
Thanks,
-Stolee
Here's a few patches that we could add to the beginning of this series,
or queue up separately.
I think that these are all fairly straightforward, but it would be good
to have Ævar take a look and make sure I'm not doing anything wrong
here.
I'll plan to send a v2 of the reverse index series in a few days with
these four new patches at the beginning.
Thanks, both, for cleaning up a mess I made as a new contributor. These
patches have been enlightening and definitely move the code into a
cleaner and more extensible direction. Thanks!
-Stolee
On Mon, Feb 15, 2021 at 07:41:17PM +0100, Ævar Arnfjörð Bjarmason wrote:
quoted
I think it's more readable to have one if/elsif/else chain here than
the code this replaces.
FWIW, I find the pre-image more readable than what you are proposing
replacing it with here.
Of course, I have no doubts about the obvious correctness of this patch;
I'm merely suggesting that I wouldn't be sad to see us apply the first
three patches, and the fifth patch, but drop this one.
I agree with all of your points here. I think that compared to the
current code at-rest, the new version might be preferred. It's a little
dense, which is my only complaint.
The issue comes for the future: what if we need to add a third verb
to 'git commit-graph'? Then extending this new option looks worse since
we would check 'argc' three times.
The other patches solve real readability problems or reorganize the code
to use other concepts within the codebase. This one is much more optional.
From: Taylor Blau <hidden> Date: 2021-02-16 14:29:56
On Tue, Feb 16, 2021 at 06:50:13AM -0500, Derrick Stolee wrote:
On 2/15/2021 4:01 PM, Taylor Blau wrote:
quoted
Here's a few patches that we could add to the beginning of this series,
or queue up separately.
I think that these are all fairly straightforward, but it would be good
to have Ævar take a look and make sure I'm not doing anything wrong
here.
I'll plan to send a v2 of the reverse index series in a few days with
these four new patches at the beginning.
Thanks, both, for cleaning up a mess I made as a new contributor. These
patches have been enlightening and definitely move the code into a
cleaner and more extensible direction. Thanks!
There was hardly a mess to clean-up, and clearly this pattern is new to
me, too :).
I'm planning on resubmitting my tb/reverse-midx series as soon as it
gets another set of reviewer eyes with these four or five patches as new
at the beginning.
I do wonder about the merge conflicts caused between this and your
chunk-format API series. I'd rather not create such conflicts for Junio,
and last I recall there were still some outstanding comments on that
series. So long as you don't think that you resolving those comments
would cause new conflicts, I would assume that Junio's rerere cache
would make applying both easy enough.
If you do think it would cause new conflicts, it may make sense for you
to rebase your branch on mine, but I'm not sure if that's something
you'd want to do or not.
Using a 'goto' is a fine way to avoid a nesting level, but I'm not sure
it "improves readability." Having the tab level makes it clear that that
code is executed only when some condition is met, in this case "if (argc),"
while with the 'goto' we need to know that execution was redirected.
I don't feel too strongly either way. If the code was presented one way or
the other, I probably wouldn't recommend changing to the other mode. In
that sense, the change isn't necessary and causes me to break the tie in
favor of leaving it where it is.
Of course, if someone else says "I like this and would prefer it be used
as an example for future contributors" then the tie is broken in the other
way.
Thanks,
-Stolee
From: Taylor Blau <hidden> Date: 2021-02-24 19:11:26
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-02-24 19:12:06
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-02-24 19:12:06
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-02-24 19:12:10
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-02-24 19:12:16
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-02-24 19:12:32
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-02-24 19:13:04
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-02-24 19:13:09
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 | 99 ++++++++++++++++++--
midx.h | 2 +-
t/t5319-multi-pack-index.sh | 39 ++++++++
7 files changed, 161 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-02-24 19:13:14
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.
Signed-off-by: Taylor Blau <redacted>
---
midx.c | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
midx.h | 1 +
2 files changed, 112 insertions(+)
@@ -826,6 +828,66 @@ 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;++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);++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-02-24 19:13:56
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-02-24 19:13:56
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-02-24 19:13:56
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-02-24 19:14:01
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 | 80 +++++++++++++++++++++++++
1 file changed, 80 insertions(+)
@@ -379,3 +379,83 @@ 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.++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.++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-02-24 19:14:13
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, 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.
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-02-24 19:14:19
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 | 39 ++++++++++++++++++++++++++++-----------
pack.h | 1 +
2 files changed, 29 insertions(+), 11 deletions(-)
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.
+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).
The other patches up to this one look good.
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.
quoted hunk
@@ -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.
All previous patches look good to me.
From: Jonathan Tan <hidden> Date: 2021-03-02 15:28:35
+== 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?)
Also, which are stored in the .rev file?
The previous patches look good to me, and I'll review the remaining
patches hopefully tomorrow.
From: Taylor Blau <hidden> Date: 2021-03-02 15:28:35
On Mon, Mar 01, 2021 at 08:21:11PM -0800, Jonathan Tan wrote:
The previous patches look good to me, and I'll review the remaining
patches hopefully tomorrow.
Thanks; I am sorely behind recent activity on the list. I had a
last-minute errand to run last weekend and I haven't managed to quite
dig out of the hole I created for myself since then.
Incidentally, I have had this code (and the tb/multi-pack-bitmaps)
running on a couple of high-traffic repositories internal to GitHub, and
so have a couple of improvements that I was hoping to squash in, too.
Thanks,
Taylor
From: Jonathan Tan <hidden> Date: 2021-03-03 06:41:56
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 :-)
I understood that the array we're searching over is an array of indexes
into the MIDX in pack-pos order, so I understood what's written here. It
might be easier for other readers if we just say that we're treating the
elements of this array not as indexes into MIDX but as their
corresponding (is-preferred-pack, pack number, offset) tuples. But I'm
fine with retaining the existing wording too.
The patch itself looks good.