From: Taylor Blau <hidden> Date: 2021-01-08 18:17:24
Hi,
This is the first of two series to introduce an on-disk alternative to the
reverse index which is currently generated once per-process and stored in
memory.
As a reminder, the reverse index is used to translate an object's position
relative to other objects within the same packfile to that object's position
relative to the pack's index.
Generating the reverse index in memory for repositories with large packs has two
significant drawbacks:
- It requires allocating sizeof(struct revindex_entry) per packed object.
- It requires us to sort the entries by their pack offset. This is implemented
in sort_revindex() using a radix sort, but still takes considerable time (as
benchmarks found in the second series demonstrate).
Both of these can be addressed by storing the reverse index in a new '.rev' file
alongside the packs. This file is written once (during pack creation), and does
not require sorting when accessed, since it is stored in a sorted order.
This series lays the groundwork necessary to introduce the file format (which is
implemented in the second series). I'm splitting these two up since I think the
changes in this series can be queued independently from those in the latter
series.
The goal of this series is to remove direct access of the `struct
revindex_entry` type, as well as `struct packed_git`'s `revindex` field. The
on-disk format will be mmap'd and accessed directly, but the format is
sufficiently different that the whole `revindex` array can't be written as-is.
Separately from our main goal, the new API that is introduced in this series is
IMHO easier to read, and more clearly describes what order the given and
returned values are relative to.
The changes are structured as follows:
- First, a new API is proposed.
- Then, uses of the old API are removed one by one and replaced with their
new counterparts.
- Finally, without any callers remaining, the old API is removed.
Thanks in advance for your review.
Taylor Blau (20):
pack-revindex: introduce a new API
write_reuse_object(): convert to new revindex API
write_reused_pack_one(): convert to new revindex API
write_reused_pack_verbatim(): convert to new revindex API
check_object(): convert to new revindex API
bitmap_position_packfile(): convert to new revindex API
show_objects_for_type(): convert to new revindex API
get_size_by_pos(): convert to new revindex API
try_partial_reuse(): convert to new revindex API
rebuild_existing_bitmaps(): convert to new revindex API
get_delta_base_oid(): convert to new revindex API
retry_bad_packed_offset(): convert to new revindex API
packed_object_info(): convert to new revindex API
unpack_entry(): convert to new revindex API
for_each_object_in_pack(): convert to new revindex API
builtin/gc.c: guess the size of the revindex
pack-revindex: remove unused 'find_pack_revindex()'
pack-revindex: remove unused 'find_revindex_position()'
pack-revindex: hide the definition of 'revindex_entry'
pack-revindex.c: avoid direct revindex access in
'offset_to_pack_pos()'
builtin/gc.c | 2 +-
builtin/pack-objects.c | 33 +++++++++++++++++-----------
pack-bitmap.c | 44 ++++++++++++++++++-------------------
pack-revindex.c | 49 +++++++++++++++++++++++++++--------------
pack-revindex.h | 10 +++------
packfile.c | 50 ++++++++++++++++++++++++++----------------
6 files changed, 109 insertions(+), 79 deletions(-)
--
2.30.0.138.g6d7191ea01
From: Taylor Blau <hidden> Date: 2021-01-08 18:17:48
In the next several patches, we will prepare for loading a reverse index
either in memory, or from a yet-to-be-introduced on-disk format. To do
that, we'll introduce an API that avoids the caller explicitly indexing
the revindex pointer in the packed_git structure.
There are four ways to interact with the reverse index. Accordingly,
four functions will be exported from 'pack-revindex.h' by the time that
the existing API is removed. A caller may:
1. Load the pack's reverse index. This involves opening up the index,
generating an array, and then sorting it. Since opening the index
can fail, this function ('load_pack_revindex()') returns an int.
Accordingly, it takes only a single argument: the 'struct
packed_git' the caller wants to build a reverse index for.
This function is well-suited for both the current and new API.
Callers will have to continue to open the reverse index explicitly,
but this function will eventually learn how to detect and load a
reverse index from the on-disk format, if one exists. Otherwise, it
will fallback to generating one in memory from scratch.
2. Convert a pack position into an offset. This operation is now
called `pack_pos_to_offset()`. It takes a pack and a position, and
returns the corresponding off_t.
3. Convert a pack position into an index position. Same as above; this
takes a pack and a position, and returns a uint32_t. This operation
is known as `pack_pos_to_index()`.
4. Find the pack position for a given offset. This operation is now
known as `offset_to_pack_pos()`. It takes a pack, an offset, and a
pointer to a uint32_t where the position is written, if an object
exists at that offset. Otherwise, -1 is returned to indicate
failure.
Unlike some of the callers that used to access '->offset' and '->nr'
directly, the error checking around this call is somewhat more
robust. This is important since callers can pass an offset which
does not contain an object.
This will become important in a subsequent patch where a caller
which does not but could check the return value treats the signed
`-1` from `find_revindex_position()` as an index into the 'revindex'
array.
Signed-off-by: Taylor Blau <redacted>
---
pack-revindex.c | 32 ++++++++++++++++++++++++++++++++
pack-revindex.h | 4 ++++
2 files changed, 36 insertions(+)
@@ -203,3 +203,35 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)returnp->revindex+pos;}++intoffset_to_pack_pos(structpacked_git*p,off_tofs,uint32_t*pos)+{+intret;++if(load_pack_revindex(p)<0)+return-1;++ret=find_revindex_position(p,ofs);+if(ret<0)+return-1;+*pos=ret;+return0;+}++uint32_tpack_pos_to_index(structpacked_git*p,uint32_tpos)+{+if(!p->revindex)+BUG("pack_pos_to_index: reverse index not yet loaded");+if(pos>=p->num_objects)+BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32,pos);+returnp->revindex[pos].nr;+}++off_tpack_pos_to_offset(structpacked_git*p,uint32_tpos)+{+if(!p->revindex)+BUG("pack_pos_to_index: reverse index not yet loaded");+if(pos>p->num_objects)+BUG("pack_pos_to_offset: out-of-bounds object at %"PRIu32,pos);+returnp->revindex[pos].offset;+}
From: Jeff King <hidden> Date: 2021-01-12 08:42:27
On Fri, Jan 08, 2021 at 01:16:43PM -0500, Taylor Blau wrote:
In the next several patches, we will prepare for loading a reverse index
either in memory, or from a yet-to-be-introduced on-disk format. To do
that, we'll introduce an API that avoids the caller explicitly indexing
the revindex pointer in the packed_git structure.
This API looks good to me. Here are a few extra thoughts:
There are four ways to interact with the reverse index. Accordingly,
four functions will be exported from 'pack-revindex.h' by the time that
the existing API is removed. A caller may:
This tells us what the new API functions do. That's useful, but should
it be in the header file itself, documenting each function?
Likewise, I think we'd want to define the concepts in that
documentation. Something like:
/*
* A revindex allows converting efficiently between three properties
* of an object within a pack:
*
* - index position: the numeric position within the list of
* sorted object ids found in the .idx file
*
* - pack position: the numeric position within the list of objects
* in their order within the actual .pack file (i.e., 0 is the
* first object in the .pack, 1 is the second, and so on)
*
* - offset: the byte offset within the .pack file at which the
* object contents can be found
*/
And then above each function we can just say that it converts X to Y
(like you have in the commit message). It may also be worth indicating
the run-time of each (some of them are constant-time once you have a
revindex, and some are log(n)).
The types here make sense. off_t is clearly needed for a pack offset,
and uint32_t is correct for the position fields, because packs have a
4-byte object count.
Separating the error return from the out-parameter makes the interface
slightly more awkward, but is needed to use the properly-sized types.
Makes sense.
This one lazy-loads the revindex for us, which seems handy...
+uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos)
+{
+ if (!p->revindex)
+ BUG("pack_pos_to_index: reverse index not yet loaded");
+ if (pos >= p->num_objects)
+ BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos);
+ return p->revindex[pos].nr;
+}
But these ones don't. I'm glad we at least catch it with a BUG(), but it
makes the API a little funny. Returning an error here would require a
similarly awkward out-parameter, I guess.
-Peff
This one lazy-loads the revindex for us, which seems handy...
quoted
+uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos)
+{
+ if (!p->revindex)
+ BUG("pack_pos_to_index: reverse index not yet loaded");
+ if (pos >= p->num_objects)
+ BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos);
+ return p->revindex[pos].nr;
+}
But these ones don't. I'm glad we at least catch it with a BUG(), but it
makes the API a little funny. Returning an error here would require a
similarly awkward out-parameter, I guess.
Having now looked at the callers through the series, I think adding an
error return to pack_pos_to_index() would be really awkward (since it
cannot currently fail).
We _could_ insist that callers of offset_to_pack_pos() also make sure
the revindex is loaded themselves. But it would be annoying and
error-prone to check the existing callers. So I'm OK with leaving this
asymmetry in the API.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-12 16:29:07
On Tue, Jan 12, 2021 at 03:41:28AM -0500, Jeff King wrote:
quoted
There are four ways to interact with the reverse index. Accordingly,
four functions will be exported from 'pack-revindex.h' by the time that
the existing API is removed. A caller may:
This tells us what the new API functions do. That's useful, but should
it be in the header file itself, documenting each function?
Mm, that's a good idea. I took your suggestion for a comment at the top
of pack-revindex.h directly, and then added some of my own commentary
above each function. I avoided documenting the functions we're about to
remove for obvious reasons.
I think that the commit message is OK as-is, since it provides more of a
rationale of what operations need to exist, rather than the specifics of
each implementation.
We'll have to update these again when the on-disk format exists (i.e.,
because all of the runtimes become constant with the exception of going
to the index), but that's a topic for another series.
The types here make sense. off_t is clearly needed for a pack offset,
and uint32_t is correct for the position fields, because packs have a
4-byte object count.
Separating the error return from the out-parameter makes the interface
slightly more awkward, but is needed to use the properly-sized types.
Makes sense.
This one lazy-loads the revindex for us, which seems handy...
quoted
+uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos)
+{
+ if (!p->revindex)
+ BUG("pack_pos_to_index: reverse index not yet loaded");
+ if (pos >= p->num_objects)
+ BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos);
+ return p->revindex[pos].nr;
+}
But these ones don't. I'm glad we at least catch it with a BUG(), but it
makes the API a little funny. Returning an error here would require a
similarly awkward out-parameter, I guess.
It is awkward, but (as you note downthread) the callers of
pack_pos_to_index() make it difficult to do so, so I didn't pursue it
here.
From: Taylor Blau <hidden> Date: 2021-01-08 18:17:48
First replace 'find_pack_revindex()' with its replacement
'offset_to_pack_pos()'. This prevents any bogus OFS_DELTA that may make
its way through until 'write_reuse_object()' from causing a bad memory
read (if 'revidx' is 'NULL')
Next, replace a direct access of '->nr' with the wrapper function
'pack_pos_to_index()'.
Signed-off-by: Taylor Blau <redacted>
---
builtin/pack-objects.c | 11 +++++++----
1 file changed, 7 insertions(+), 4 deletions(-)
From: Jeff King <hidden> Date: 2021-01-12 08:48:51
On Fri, Jan 08, 2021 at 01:16:48PM -0500, Taylor Blau wrote:
First replace 'find_pack_revindex()' with its replacement
'offset_to_pack_pos()'. This prevents any bogus OFS_DELTA that may make
its way through until 'write_reuse_object()' from causing a bad memory
read (if 'revidx' is 'NULL')
Nice. Better abstraction, and we're catching more errors.
If we believe the offset is bogus, should we print that in the error
message, too? Something like:
die("could not locate %s, expected at offset %"PRIuMAX" in pack %s",
oid_to_hex(&entry->idx.oid), (uintmax_t)offset, p->pack_name);
This "pos + 1" means we may be looking one past the end of the array.
That's OK (at least for now), because our revindex always puts in an
extra dummy value exactly for computing these kinds of byte-distances.
That might be worth documenting in the API header.
-Peff
If we believe the offset is bogus, should we print that in the error
message, too? Something like:
die("could not locate %s, expected at offset %"PRIuMAX" in pack %s",
oid_to_hex(&entry->idx.oid), (uintmax_t)offset, p->pack_name);
This "pos + 1" means we may be looking one past the end of the array.
That's OK (at least for now), because our revindex always puts in an
extra dummy value exactly for computing these kinds of byte-distances.
That might be worth documenting in the API header.
Yeah, I made sure to document that when I was touching up the last
patch. FWIW, that's a behavior that we're going to carry over even when
the reverse index is stored on-disk (not by writing four extra bytes
into the .rev file, but by handling queries for pos == p->num_objects
separately.)
This "pos + 1" means we may be looking one past the end of the array.
That's OK (at least for now), because our revindex always puts in an
extra dummy value exactly for computing these kinds of byte-distances.
That might be worth documenting in the API header.
Yeah, I made sure to document that when I was touching up the last
patch. FWIW, that's a behavior that we're going to carry over even when
the reverse index is stored on-disk (not by writing four extra bytes
into the .rev file, but by handling queries for pos == p->num_objects
separately.)
I think the only reason to look past the end like that is to compute the
size of the final entry. So we _could_ abstract that away from the
callers with a separate function like:
off_t pack_pos_to_size(struct packed_git *p, uint32_t pos);
But as long as the behavior of passing p->num_objects is documented, I
do not mind overly mind spelling it one way or the other.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-08 18:17:49
Replace a direct access to the revindex array with
'pack_pos_to_offset()'.
Signed-off-by: Taylor Blau <redacted>
---
builtin/pack-objects.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Replace find_revindex_position() with its counterpart in the new API,
offset_to_pack_pos().
Signed-off-by: Taylor Blau <redacted>
---
pack-bitmap.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Remove another caller that holds onto a 'struct revindex_entry' by
replacing the direct indexing with calls to 'pack_pos_to_offset()' and
'pack_pos_to_index()'.
Signed-off-by: Taylor Blau <redacted>
---
pack-bitmap.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
@@ -835,11 +835,11 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,oi.sizep=&size;if(pos<pack->num_objects){-structrevindex_entry*entry=&pack->revindex[pos];-if(packed_object_info(the_repository,pack,-entry->offset,&oi)<0){+off_tofs=pack_pos_to_offset(pack,pos);+if(packed_object_info(the_repository,pack,ofs,&oi)<0){structobject_idoid;-nth_packed_object_id(&oid,pack,entry->nr);+nth_packed_object_id(&oid,pack,+pack_pos_to_index(pack,pos));die(_("unable to get size of %s"),oid_to_hex(&oid));}}else{
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Avoid storing the revindex entry directly, since this structure will
soon be removed from the public interface. Instead, store the offset and
index position by calling 'pack_pos_to_offset()' and
'pack_pos_to_index()', respectively.
Signed-off-by: Taylor Blau <redacted>
---
pack-bitmap.c | 13 +++++++------
1 file changed, 7 insertions(+), 6 deletions(-)
A minor nit, but "n" isn't very descriptive. It's not in scope for very
long, so that's not too bad, but there are two positions at work in this
function: the pos/offset bit position, and the index position. Maybe
"index_pos" would be better than "n" to keep the two clear?
-Peff
From: Taylor Blau <hidden> Date: 2021-01-12 16:36:35
On Tue, Jan 12, 2021 at 03:57:59AM -0500, Jeff King wrote:
A minor nit, but "n" isn't very descriptive. It's not in scope for very
long, so that's not too bad, but there are two positions at work in this
function: the pos/offset bit position, and the index position. Maybe
"index_pos" would be better than "n" to keep the two clear?
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Replace direct accesses to the revindex with calls to
'offset_to_pack_pos()' and 'pack_pos_to_index()'.
Since this caller already had some error checking (it can jump to the
'give_up' label if it encounters an error), we can easily check whether
or not the provided offset points to an object in the given pack. This
error checking existed prior to this patch, too, since the caller checks
whether the return value from 'find_pack_revindex()' was NULL or not.
Signed-off-by: Taylor Blau <redacted>
---
builtin/pack-objects.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
Replace direct accesses to the revindex with calls to
'offset_to_pack_pos()' and 'pack_pos_to_index()'.
Since this caller already had some error checking (it can jump to the
'give_up' label if it encounters an error), we can easily check whether
or not the provided offset points to an object in the given pack. This
error checking existed prior to this patch, too, since the caller checks
whether the return value from 'find_pack_revindex()' was NULL or not.
Signed-off-by: Taylor Blau <redacted>
---
builtin/pack-objects.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
The current implementation does not return a positive value. Only
-1 on error and 0 on success. Is this "< 0" doing anything important?
Seems like it would be easiest to do
if (offset_to_pack_pos(p, ofs, &pos))
goto give_up;
- if (!nth_packed_object_id(&base_ref, p, revidx->nr))
+ if (!nth_packed_object_id(&base_ref, p,
+ pack_pos_to_index(p, pos)))
have_base = 1;
}
The current implementation does not return a positive value. Only
-1 on error and 0 on success. Is this "< 0" doing anything important?
Seems like it would be easiest to do
if (offset_to_pack_pos(p, ofs, &pos))
[snip]
Either would work, of course. I tend to find the '< 0' form easier to
read, but I may be in the minority there. For me, the negative return
value makes clear that the function encountered an error.
A secondary benefit is that if the function ever were to return a
positive value that _didn't_ indicate an error, we would already be
protected against it. That is probably a pretty weak argument, though,
since any such refactoring would probably require the callers to change,
too.
Anyway, that's all to say that I'm happy to leave it as-is, but I'm
equally happy to change it, too.
Thanks,
Taylor
The current implementation does not return a positive value. Only
-1 on error and 0 on success. Is this "< 0" doing anything important?
Seems like it would be easiest to do
if (offset_to_pack_pos(p, ofs, &pos))
[snip]
Either would work, of course. I tend to find the '< 0' form easier to
read, but I may be in the minority there. For me, the negative return
value makes clear that the function encountered an error.
I'll throw in my opinion that "< 0" to me much more clearly signals "did
an error occur". And that same form can be used consistently with
functions which _do_ have a positive return value on success, too. So I
prefer it for readability.
-Peff
From: Jeff King <hidden> Date: 2021-01-12 08:52:22
On Fri, Jan 08, 2021 at 01:17:00PM -0500, Taylor Blau wrote:
Replace direct accesses to the revindex with calls to
'offset_to_pack_pos()' and 'pack_pos_to_index()'.
Since this caller already had some error checking (it can jump to the
'give_up' label if it encounters an error), we can easily check whether
or not the provided offset points to an object in the given pack. This
error checking existed prior to this patch, too, since the caller checks
whether the return value from 'find_pack_revindex()' was NULL or not.
Yay. Happy again to see things getting more robust.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Replace direct accesses to the 'struct revindex' type with a call to
'pack_pos_to_index()'.
Likewise drop the old-style 'find_pack_revindex()' with its replacement
'offset_to_pack_pos()' (while continuing to perform the same error
checking).
Signed-off-by: Taylor Blau <redacted>
---
packfile.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
Perform exactly the same conversion as in the previous commit to another
caller within 'packfile.c'.
Signed-off-by: Taylor Blau <redacted>
---
packfile.c | 7 +++----
1 file changed, 3 insertions(+), 4 deletions(-)
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:27
'estimate_repack_memory()' takes into account the amount of memory
required to load the reverse index in memory by multiplying the assumed
number of objects by the size of the 'revindex_entry' struct.
Prepare for hiding the definition of 'struct revindex_entry' by removing
a 'sizeof()' of that type from outside of pack-revindex.c. Instead,
guess that one off_t and one uint32_t are required per object. Strictly
speaking, this is a worse guess than asking for 'sizeof(struct
revindex_entry)' directly, since the true size of this struct is 16
bytes with padding on the end of the struct in order to align the offset
field.
But, this is an approximation anyway, and it does remove a use of the
'struct revindex_entry' from outside of pack-revindex internals.
Signed-off-by: Taylor Blau <redacted>
---
builtin/gc.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
@@ -301,7 +301,7 @@ static uint64_t estimate_repack_memory(struct packed_git *pack)/* and then obj_hash[], underestimated in fact */heap+=sizeof(structobject*)*nr_objects;/* revindex is used also */-heap+=sizeof(structrevindex_entry)*nr_objects;+heap+=(sizeof(off_t)+sizeof(uint32_t))*nr_objects;/**read_sha1_file()(eitheratdeltacalculationphase,or*writingphase)alsofillsupthedeltabasecache
'estimate_repack_memory()' takes into account the amount of memory
required to load the reverse index in memory by multiplying the assumed
number of objects by the size of the 'revindex_entry' struct.
Prepare for hiding the definition of 'struct revindex_entry' by removing
a 'sizeof()' of that type from outside of pack-revindex.c. Instead,
guess that one off_t and one uint32_t are required per object. Strictly
speaking, this is a worse guess than asking for 'sizeof(struct
revindex_entry)' directly, since the true size of this struct is 16
bytes with padding on the end of the struct in order to align the offset
field.
This is so far the only not-completely-obvious change.
But, this is an approximation anyway, and it does remove a use of the
'struct revindex_entry' from outside of pack-revindex internals.
And this might be enough justification for it, but...
...outside of the estimation change, will this need another change
when the rev-index is mmap'd? Should this instead be an API call,
such as estimate_rev_index_memory(nr_objects)? That would
centralize the estimate to be next to the code that currently
interacts with 'struct revindex_entry' and will later interact with
the mmap region.
Thanks,
-Stolee
...outside of the estimation change, will this need another change
when the rev-index is mmap'd? Should this instead be an API call,
such as estimate_rev_index_memory(nr_objects)? That would
centralize the estimate to be next to the code that currently
interacts with 'struct revindex_entry' and will later interact with
the mmap region.
I definitely did consider this, and it seems that I made a mistake in
not documenting my consideration (since I assumed that it was so benign
nobody would notice / care ;-)).
The reason I didn't pursue it here was that we haven't yet loaded the
reverse index by this point. So, you'd want a function that at least
stats the '*.rev' file (and either does or doesn't parse it [1]), or
aborts early to indicate otherwise.
One would hope that 'load_pack_revindex()' would do just that, but it
falls back to load a reverse index in memory, which involves exactly the
slow sort that we're trying to avoid. (Of course, we're going to have to
do it later anyway, but allocating many GB of heap just to provide an
estimation seems ill-advised to me ;-).)
So, we'd have to expand the API in some way or another, and to me it
didn't seem worth it. As I mentioned in the commit message, I'm
skeptical of the value of being accurate here, since this is (after all)
an estimation.
Perhaps a longer response than you were bargaining for, but... :-).
Thanks,
Taylor
[1]: Likely negligible, since all "parsing" really does is verify the
internal checksum, and then assign a pointer into it.
...outside of the estimation change, will this need another change
when the rev-index is mmap'd? Should this instead be an API call,
such as estimate_rev_index_memory(nr_objects)? That would
centralize the estimate to be next to the code that currently
interacts with 'struct revindex_entry' and will later interact with
the mmap region.
I definitely did consider this, and it seems that I made a mistake in
not documenting my consideration (since I assumed that it was so benign
nobody would notice / care ;-)).
The reason I didn't pursue it here was that we haven't yet loaded the
reverse index by this point. So, you'd want a function that at least
stats the '*.rev' file (and either does or doesn't parse it [1]), or
aborts early to indicate otherwise.
In this patch, I would expect it to use sizeof(struct revindex_entry).
Later, the method would know if a .rev file exists and do the right
thing instead. (Also, should mmap'd data count towards this estimate?)
One would hope that 'load_pack_revindex()' would do just that, but it
falls back to load a reverse index in memory, which involves exactly the
slow sort that we're trying to avoid. (Of course, we're going to have to
do it later anyway, but allocating many GB of heap just to provide an
estimation seems ill-advised to me ;-).)
So, we'd have to expand the API in some way or another, and to me it
didn't seem worth it. As I mentioned in the commit message, I'm
skeptical of the value of being accurate here, since this is (after all)
an estimation.
Yes, I'm probably just poking somewhere it was easy to poke. This is
probably not worth the time I'm spending asking about it.
Feel free to disregard.
-Stolee
From: Jeff King <hidden> Date: 2021-01-12 09:29:06
On Mon, Jan 11, 2021 at 12:09:27PM -0500, Derrick Stolee wrote:
quoted
The reason I didn't pursue it here was that we haven't yet loaded the
reverse index by this point. So, you'd want a function that at least
stats the '*.rev' file (and either does or doesn't parse it [1]), or
aborts early to indicate otherwise.
In this patch, I would expect it to use sizeof(struct revindex_entry).
Later, the method would know if a .rev file exists and do the right
thing instead. (Also, should mmap'd data count towards this estimate?)
Yeah, I think if we care about memory pressure, then the mmap would
count anyway. I agree that letting the revindex code decide which to use
would be the most accurate thing, but given that this whole chunk of
code is an estimate (that does not even seem to take into account the
memory used for the delta search!), I don't think it's worth trying to
get to accurate.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Remove another instance of looking at the revindex directly by instead
calling 'pack_pos_to_index()'. Unlike other patches, this caller only
cares about the index position of each object in the loop.
Signed-off-by: Taylor Blau <redacted>
---
pack-bitmap.c | 5 ++---
1 file changed, 2 insertions(+), 3 deletions(-)
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Remove another instance of direct revindex manipulation by calling
'pack_pos_to_offset()' instead (the caller here does not care about the
index position of the object at position 'pos').
Somewhat confusingly, the subsequent call to unpack_object_header()
takes a pointer to &offset and then updates it with a new value. But,
try_partial_reuse() cares about the offset of both the base's header and
contents. The existing code made a copy of the offset field, and only
addresses and manipulates one of them.
Instead, store the return of pack_pos_to_offset twice: once in header
and another in offset. Header will be left untouched, but offset will be
addressed and modified by unpack_object_header().
Signed-off-by: Taylor Blau <redacted>
---
pack-bitmap.c | 13 +++++--------
1 file changed, 5 insertions(+), 8 deletions(-)
@@ -1069,23 +1069,21 @@ static void try_partial_reuse(struct bitmap_index *bitmap_git,structbitmap*reuse,structpack_window**w_curs){-structrevindex_entry*revidx;-off_toffset;+off_toffset,header;enumobject_typetype;unsignedlongsize;if(pos>=bitmap_git->pack->num_objects)return;/* not actually in the pack */-revidx=&bitmap_git->pack->revindex[pos];-offset=revidx->offset;+offset=header=pack_pos_to_offset(bitmap_git->pack,pos);type=unpack_object_header(bitmap_git->pack,w_curs,&offset,&size);if(type<0)return;/* broken packfile, punt */if(type==OBJ_REF_DELTA||type==OBJ_OFS_DELTA){off_tbase_offset;-intbase_pos;+uint32_tbase_pos;/**Findthepositionofthebaseobjectsowecanlookitup
From: Jeff King <hidden> Date: 2021-01-12 09:07:30
On Fri, Jan 08, 2021 at 01:17:17PM -0500, Taylor Blau wrote:
Remove another instance of direct revindex manipulation by calling
'pack_pos_to_offset()' instead (the caller here does not care about the
index position of the object at position 'pos').
Somewhat confusingly, the subsequent call to unpack_object_header()
takes a pointer to &offset and then updates it with a new value. But,
try_partial_reuse() cares about the offset of both the base's header and
contents. The existing code made a copy of the offset field, and only
addresses and manipulates one of them.
Instead, store the return of pack_pos_to_offset twice: once in header
and another in offset. Header will be left untouched, but offset will be
addressed and modified by unpack_object_header().
I had to read these second two paragraphs a few times to parse them.
Really we are just replacing revidx->offset with "header", and "offset"
retains its same role within the function.
So it's definitely doing the right thing, but it makes more sense to me
as:
Note that we cannot just use the existing "offset" variable to store
the value we get from pack_pos_to_offset(). It is incremented by
unpack_object_header(), but we later need the original value. Since
we'll no longer have revindex->offset to read it from, we'll store
that in a separate variable ("header" since it points to the entry's
header bytes).
Another option would be to just call pack_pos_to_offset() again for the
later call. Like the code it's replacing, it's constant-time anyway. But
I think the "header" variable actually makes things more readable.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-12 16:48:59
On Tue, Jan 12, 2021 at 04:06:46AM -0500, Jeff King wrote:
On Fri, Jan 08, 2021 at 01:17:17PM -0500, Taylor Blau wrote:
quoted
Somewhat confusingly, the subsequent call to unpack_object_header()
takes a pointer to &offset and then updates it with a new value. But,
try_partial_reuse() cares about the offset of both the base's header and
contents. The existing code made a copy of the offset field, and only
addresses and manipulates one of them.
Instead, store the return of pack_pos_to_offset twice: once in header
and another in offset. Header will be left untouched, but offset will be
addressed and modified by unpack_object_header().
I had to read these second two paragraphs a few times to parse them.
Really we are just replacing revidx->offset with "header", and "offset"
retains its same role within the function.
So it's definitely doing the right thing, but it makes more sense to me
as: [...]
Thanks. Reading these both back-to-back, I agree that yours is much
clearer in describing what is actually going on.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Convert another call of 'find_pack_revindex()' to its replacement
'pack_pos_to_offset()'. Likewise:
- Avoid manipulating `struct packed_git`'s `revindex` pointer directly
by removing the pointer-as-array indexing.
- Add an additional guard to check that the offset 'obj_offset()'
points to a real object. This should be the case with well-behaved
callers to 'packed_object_info()', but isn't guarenteed.
Other blocks that fill in various other values from the 'struct
object_info' request handle bad inputs by setting the type to
'OBJ_BAD' and jumping to 'out'. Do the same when given a bad offset
here.
The previous code would have segfaulted when given a bad
'obj_offset' value, since 'find_pack_revindex()' would return
'NULL', and then the line that fills 'oi->disk_sizep' would try to
access 'NULL[1]' with a stride of 16 bytes (the width of 'struct
revindex_entry)'.
Signed-off-by: Taylor Blau <redacted>
---
packfile.c | 9 +++++++--
1 file changed, 7 insertions(+), 2 deletions(-)
From: Jeff King <hidden> Date: 2021-01-12 09:12:57
On Fri, Jan 08, 2021 at 01:17:34PM -0500, Taylor Blau wrote:
Convert another call of 'find_pack_revindex()' to its replacement
'pack_pos_to_offset()'. Likewise:
- Avoid manipulating `struct packed_git`'s `revindex` pointer directly
by removing the pointer-as-array indexing.
Good.
- Add an additional guard to check that the offset 'obj_offset()'
points to a real object. This should be the case with well-behaved
callers to 'packed_object_info()', but isn't guarenteed.
Other blocks that fill in various other values from the 'struct
object_info' request handle bad inputs by setting the type to
'OBJ_BAD' and jumping to 'out'. Do the same when given a bad offset
here.
Also good. I wonder if we need to call error() here, too. The caller
will probably say something like "bad object" or whatever, but the user
will have no clue that it's related to the revindex.
That would match other parts of the function (e.g., calling into
unpack_entry() can generate lots of descriptive errors about exactly
what went wrong).
The previous code would have segfaulted when given a bad
'obj_offset' value, since 'find_pack_revindex()' would return
'NULL', and then the line that fills 'oi->disk_sizep' would try to
access 'NULL[1]' with a stride of 16 bytes (the width of 'struct
revindex_entry)'.
Yep. Again, I'm really happy to see these "should never happen" cases
converted to real errors or even BUG()s.
-Peff
From: Taylor Blau <hidden> Date: 2021-01-12 16:52:14
On Tue, Jan 12, 2021 at 04:11:59AM -0500, Jeff King wrote:
quoted
- Add an additional guard to check that the offset 'obj_offset()'
points to a real object. This should be the case with well-behaved
callers to 'packed_object_info()', but isn't guarenteed.
Other blocks that fill in various other values from the 'struct
object_info' request handle bad inputs by setting the type to
'OBJ_BAD' and jumping to 'out'. Do the same when given a bad offset
here.
Also good. I wonder if we need to call error() here, too. The caller
will probably say something like "bad object" or whatever, but the user
will have no clue that it's related to the revindex.
That would match other parts of the function (e.g., calling into
unpack_entry() can generate lots of descriptive errors about exactly
what went wrong).
Indeed, and we have the object's offset and pack name to include, too,
so our error can be quite descriptive.
Yep. Again, I'm really happy to see these "should never happen" cases
converted to real errors or even BUG()s.
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Remove direct manipulation of the 'struct revindex_entry' type as well
as calls to the deprecated API in 'packfile.c:unpack_entry()'. Usual
clean-up is performed (replacing '->nr' with calls to
'pack_pos_to_index()' and so on). Add an additional check to make
sure that 'obj_offset()' points at a valid object.
Signed-off-by: Taylor Blau <redacted>
---
packfile.c | 24 ++++++++++++++++--------
1 file changed, 16 insertions(+), 8 deletions(-)
Nice to see the error check here. As with the previous commit, we
probably want to error(), just as we would for errors below.
Do we also need to call mark_bad_packed_object()? I guess we can't,
because we only have the offset, and not the oid (the code below uses
nth_packed_object_id(), but it is relying on the revindex, which we know
just failed to work).
I'm just wondering if an error here is going to put us into an infinite
loop of retrying the lookup in the same pack over and over. Let's
see...our caller is ultimately packed_object_info(), but it too does not
have the oid. It returns an error up to do_oid_object_info_extended().
Which yes, does mark_bad_packed_object() itself. Good. So I think we are
fine, and arguably these lower-level calls to mark_bad_packed_object()
are not necessary. But they do not hurt either.
-Peff
Nice to see the error check here. As with the previous commit, we
probably want to error(), just as we would for errors below.
Yup, good call.
Do we also need to call mark_bad_packed_object()? I guess we can't,
because we only have the offset, and not the oid (the code below uses
nth_packed_object_id(), but it is relying on the revindex, which we know
just failed to work).
I'm just wondering if an error here is going to put us into an infinite
loop of retrying the lookup in the same pack over and over. Let's
see...our caller is ultimately packed_object_info(), but it too does not
have the oid. It returns an error up to do_oid_object_info_extended().
Which yes, does mark_bad_packed_object() itself. Good. So I think we are
fine, and arguably these lower-level calls to mark_bad_packed_object()
are not necessary. But they do not hurt either.
Thanks, this rationale is helpful to have. I included an abridged
version of it in the patch message.
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Now that all 'find_revindex_position()' callers have been removed (and
converted to the more descriptive 'offset_to_pack_pos()'), it is almost
safe to get rid of 'find_revindex_position()' entirely. Almost, except
for the fact that 'offset_to_pack_pos()' calls
'find_revindex_position()'.
Inline 'find_revindex_position()' into 'offset_to_pack_pos()', and
then remove 'find_revindex_position()' entirely.
This is a straightforward refactoring with one minor snag.
'offset_to_pack_pos()' used to load the index before calling
'find_revindex_position()'. That means that by the time
'find_revindex_position()' starts executing, 'p->num_objects' can be
safely read. After inlining, be careful to not read 'p->num_objects'
until _after_ 'load_pack_revindex()' (which loads the index as a
side-effect) has been called.
Signed-off-by: Taylor Blau <redacted>
---
pack-revindex.c | 29 +++++++++++------------------
pack-revindex.h | 1 -
2 files changed, 11 insertions(+), 19 deletions(-)
-int find_revindex_position(struct packed_git *p, off_t ofs)
+int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
{
int lo = 0;
- int hi = p->num_objects + 1;
- const struct revindex_entry *revindex = p->revindex;
+ int hi;
+ const struct revindex_entry *revindex;
+
+ if (load_pack_revindex(p) < 0)
+ return -1;
+
+ hi = p->num_objects + 1;
+ revindex = p->revindex;
do {
const unsigned mi = lo + (hi - lo) / 2;
if (revindex[mi].offset == ofs) {
- return mi;
+ *pos = mi;
+ return 0;
} else if (ofs < revindex[mi].offset)
hi = mi;
else
@@ -189,20 +196,6 @@ int find_revindex_position(struct packed_git *p, off_t ofs) return -1; }-int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)-{- int ret;-- if (load_pack_revindex(p) < 0)- return -1;-- ret = find_revindex_position(p, ofs);- if (ret < 0)- return -1;- *pos = ret;- return 0;-}-
Not that this is new to the current patch, but this patch made me
wonder if we should initialize *pos = -1 in the case of a failure
to find the position? A correct caller should not use the value
if they are checking for the fail-to-find case properly. But, I
could see someone making a mistake and having trouble diagnosing
the problem because their position variable was initialized to
zero or a previous successful case.
Thanks,
-Stolee
From: Taylor Blau <hidden> Date: 2021-01-11 16:28:21
On Mon, Jan 11, 2021 at 06:57:00AM -0500, Derrick Stolee wrote:
On 1/8/2021 1:17 PM, Taylor Blau wrote:
quoted
-int find_revindex_position(struct packed_git *p, off_t ofs)
+int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
{
int lo = 0;
- int hi = p->num_objects + 1;
- const struct revindex_entry *revindex = p->revindex;
+ int hi;
+ const struct revindex_entry *revindex;
+
+ if (load_pack_revindex(p) < 0)
+ return -1;
+
+ hi = p->num_objects + 1;
+ revindex = p->revindex;
do {
const unsigned mi = lo + (hi - lo) / 2;
if (revindex[mi].offset == ofs) {
- return mi;
+ *pos = mi;
+ return 0;
} else if (ofs < revindex[mi].offset)
hi = mi;
else
@@ -189,20 +196,6 @@ int find_revindex_position(struct packed_git *p, off_t ofs) return -1; }-int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)-{- int ret;-- if (load_pack_revindex(p) < 0)- return -1;-- ret = find_revindex_position(p, ofs);- if (ret < 0)- return -1;- *pos = ret;- return 0;-}-
Not that this is new to the current patch, but this patch made me
wonder if we should initialize *pos = -1 in the case of a failure
to find the position? A correct caller should not use the value
if they are checking for the fail-to-find case properly. But, I
could see someone making a mistake and having trouble diagnosing
the problem because their position variable was initialized to
zero or a previous successful case.
*pos = -1 may be more confusing than clarifying since pos is unsigned.
It would be nice if there was a clear signal beyond returning a negative
value. I guess you could take a double pointer here which would allow
you to assign NULL, but that feels rather cumbersome as a means to catch
callers who failed to check the return value.
It does raise the argument of whether or not we should allow the
program to continue at all if 'ret < 0' (i.e., 'offset_to_pack_pos()'
either 'die()'s or returns a usable uint32_t), but I'm OK with the
current behavior.
On Mon, Jan 11, 2021 at 06:57:00AM -0500, Derrick Stolee wrote:
quoted
Not that this is new to the current patch, but this patch made me
wonder if we should initialize *pos = -1 in the case of a failure
to find the position? A correct caller should not use the value
if they are checking for the fail-to-find case properly. But, I
could see someone making a mistake and having trouble diagnosing
the problem because their position variable was initialized to
zero or a previous successful case.
*pos = -1 may be more confusing than clarifying since pos is unsigned.
RIGHT. My bad.
It would be nice if there was a clear signal beyond returning a negative
value. I guess you could take a double pointer here which would allow
you to assign NULL, but that feels rather cumbersome as a means to catch
callers who failed to check the return value.
It does raise the argument of whether or not we should allow the
program to continue at all if 'ret < 0' (i.e., 'offset_to_pack_pos()'
either 'die()'s or returns a usable uint32_t), but I'm OK with the
current behavior.
I was thinking "*pos = -1" was a free way to "help" a developer
who uses the API incorrectly, but it's _not_ free. Ignore me.
Thanks,
-Stolee
From: Jeff King <hidden> Date: 2021-01-12 09:33:38
On Fri, Jan 08, 2021 at 01:17:57PM -0500, Taylor Blau wrote:
Now that all 'find_revindex_position()' callers have been removed (and
converted to the more descriptive 'offset_to_pack_pos()'), it is almost
safe to get rid of 'find_revindex_position()' entirely. Almost, except
for the fact that 'offset_to_pack_pos()' calls
'find_revindex_position()'.
Inline 'find_revindex_position()' into 'offset_to_pack_pos()', and
then remove 'find_revindex_position()' entirely.
Sounds good.
This is a straightforward refactoring with one minor snag.
'offset_to_pack_pos()' used to load the index before calling
'find_revindex_position()'. That means that by the time
'find_revindex_position()' starts executing, 'p->num_objects' can be
safely read. After inlining, be careful to not read 'p->num_objects'
until _after_ 'load_pack_revindex()' (which loads the index as a
side-effect) has been called.
Good catch. We might want to drop the initialization of "lo":
int lo = 0;
- int hi = p->num_objects + 1;
down to here:
+ hi = p->num_objects + 1;
to maintain symmetry (though it's quite a minor point).
I notice these are signed ints, but we've taken care to use uint32_t
elsewhere for positions. Shouldn't these be uint32_t, also (or at least
unsigned)?
-Peff
From: Taylor Blau <hidden> Date: 2021-01-12 17:00:45
On Tue, Jan 12, 2021 at 04:32:39AM -0500, Jeff King wrote:
Good catch. We might want to drop the initialization of "lo":
quoted
int lo = 0;
- int hi = p->num_objects + 1;
down to here:
quoted
+ hi = p->num_objects + 1;
to maintain symmetry (though it's quite a minor point).
:-). I agree it's a minor point, but I think that the symmetry is nice,
so it's worth doing.
I notice these are signed ints, but we've taken care to use uint32_t
elsewhere for positions. Shouldn't these be uint32_t, also (or at least
unsigned)?
I'll let both of these be an raw unsigned, since the midpoint is already
labeled as an unsigned.
From: Jeff King <hidden> Date: 2021-01-13 13:06:01
On Tue, Jan 12, 2021 at 11:59:42AM -0500, Taylor Blau wrote:
quoted
I notice these are signed ints, but we've taken care to use uint32_t
elsewhere for positions. Shouldn't these be uint32_t, also (or at least
unsigned)?
I'll let both of these be an raw unsigned, since the midpoint is already
labeled as an unsigned.
Yeah, I found that existing code doubly weird, since "mi" must by
definition be bounded by "lo" and "hi". :)
Looks like the bug was introduced in 92e5c77c37 (revindex: export new
APIs, 2013-10-24), which hacked up the existing loop into a new
function. We should have caught it then (back then we were a lot less
careful about types, IMHO).
Also, the subject line of that commit is giving me deja vu. ;)
-Peff
From: Taylor Blau <hidden> Date: 2021-01-08 18:18:28
Now that all spots outside of pack-revindex.c that reference 'struct
revindex_entry' directly have been removed, it is safe to hide the
implementation by moving it from pack-revindex.h to pack-revindex.c.
Signed-off-by: Taylor Blau <redacted>
---
pack-revindex.c | 5 +++++
pack-revindex.h | 5 -----
2 files changed, 5 insertions(+), 5 deletions(-)