pack-revindex: prepare for on-disk reverse index

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

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.

---
 pack-revindex.c | 32 ++++++++++++++++++++++++++++++++
 pack-revindex.h |  4 ++++
 2 files changed, 36 insertions(+)

index ecdde39cf4..6d86a85208 100644
@@ -203,3 +203,35 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)
 
 	return p->revindex + pos;
 }
+
+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;
+}
+
+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;
+}
+
+off_t pack_pos_to_offset(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_offset: out-of-bounds object at %"PRIu32, pos);
+	return p->revindex[pos].offset;
+}

index 848331d5d6..256c0a9106 100644
@@ -13,4 +13,8 @@ int find_revindex_position(struct packed_git *p, off_t ofs);
 
 struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs);
 
+int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos);
+uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);
+off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
+
 #endif

2.30.0.138.g6d7191ea01

This API looks good to me. Here are a few extra thoughts:

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.

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

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.

Yep, exactly.

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.

Thanks,
Taylor

Does "load revindex in memory" (as opposed to "from on-disk file") mean the good old "read the forward index and make inverse map in-core", or something else?

IOW, is "We will prepare a reverse index either by computing in memory from forward index, or loading from on-disk file" what we want to say here?

OK.

Without knowing what exactly "pack position", "offset" and "index position" refer to, the above three are almost impossible to grok. Can we have one paragraph description for each? Something along the lines of...

- Pack position: a packstream consists of series of byte ranges, each of which represents an object, so the objects can be numbered from 0 (the object whose data is stored at the earliest part in the packfile) to N (the object whose data is stored at the tail end of the packfile). The number corresponding to an object in this order in the packfile is called the "pack position" of the object.

- Offset: The ofs_t distance between the beginning of a pack stream and the beginning of data that represents an object is called the "offset" of the object in the packfile.

- Index position: for a single pack stream, there is a table that maps object name to its offset and the entries in this table are sorted by the object name (this is what pack ".idx" file is). The location (counting from 0) of an object in this table is called the "index position" of the object in the packfile.

I am not sure if the above correctly reflects what you meant by "position", though.

Meaning "offset ought to point at the boundary between objects in the pack stream, and the API, unlike the direct access, makes sure that is the case"? That is a good thing.

	if (p->num_objects <= pos)
		BUG("...");

Please scratch the above. I see Peff already pointed out pretty much the same, and his phrasing looked a lot cleaner than my attempt.

Thanks.

Thanks for pointing this out. I recalled there being an "int" problem somewhere in the revindex code, but I didn't notice it on my read-through. This bug already exists (the problem is actually in the find_revindex_position() interface), and is fixed when we inline that into offset_to_pack_pos() in patch 18.

It might be worth mentioning the fix there.

-Peff

Indeed, that's what it means. I've made that clearer in the patch message by saying it explicitly.

Yep.

Yep, and I see later on in the thread that you want to discard this suggestion since Peff has suggested similar changes in pack-revindex.h, which I've applied.

Indeed, and I've called that out directly in the patch message to highlight it.

No reason, I've changed it to 'return ret' instead.

Indeed, and that is fixed in a later on patch. I'll make sure to call it out there.

Yes, and discussed a little bit more here [1]. Obviously that discussion doesn't do any good to those reading the git log in the future, so I've summarized the important detail (that some callers are equipped to deal with errors but others aren't) in the patch.

More readable, thanks.

Exactly. I added a detail about that in the patch, too.

Thanks,
Taylor

[1]: https://lore.kernel.org/git/X%[email protected]/

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()'.

---
 builtin/pack-objects.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

index 2a00358f34..03d25db442 100644
@@ -419,7 +419,7 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,
 {
 	struct packed_git *p = IN_PACK(entry);
 	struct pack_window *w_curs = NULL;
-	struct revindex_entry *revidx;
+	uint32_t pos;
 	off_t offset;
 	enum object_type type = oe_type(entry);
 	off_t datalen;

@@ -436,10 +436,13 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,
 					      type, entry_size);
 
 	offset = entry->in_pack_offset;
-	revidx = find_pack_revindex(p, offset);
-	datalen = revidx[1].offset - offset;
+	if (offset_to_pack_pos(p, offset, &pos) < 0)
+		die(_("write_reuse_object: could not locate %s"),
+		    oid_to_hex(&entry->idx.oid));
+	datalen = pack_pos_to_offset(p, pos + 1) - offset;
 	if (!pack_to_stdout && p->index_version > 1 &&
-	    check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {
+	    check_pack_crc(p, &w_curs, offset, datalen,
+			   pack_pos_to_index(p, pos))) {
 		error(_("bad packed object CRC for %s"),
 		      oid_to_hex(&entry->idx.oid));
 		unuse_pack(&w_curs);

2.30.0.138.g6d7191ea01

Nice. Better abstraction, and we're catching more errors.

      oid_to_hex(&entry->idx.oid), (uintmax_t)offset, p->pack_name);

Good idea, thanks.

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.)

Thanks,
Taylor

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

Replace direct revindex accesses with calls to 'pack_pos_to_offset()' and 'pack_pos_to_index()'.

---
 builtin/pack-objects.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

index 03d25db442..ea7df9270f 100644
@@ -866,8 +866,8 @@ static void write_reused_pack_one(size_t pos, struct hashfile *out,
 	enum object_type type;
 	unsigned long size;
 
-	offset = reuse_packfile->revindex[pos].offset;
-	next = reuse_packfile->revindex[pos + 1].offset;
+	offset = pack_pos_to_offset(reuse_packfile, pos);
+	next = pack_pos_to_offset(reuse_packfile, pos + 1);
 
 	record_reused_object(offset, offset - hashfile_total(out));
 

@@ -887,11 +887,15 @@ static void write_reused_pack_one(size_t pos, struct hashfile *out,
 
 		/* Convert to REF_DELTA if we must... */
 		if (!allow_ofs_delta) {
-			int base_pos = find_revindex_position(reuse_packfile, base_offset);
+			uint32_t base_pos;
 			struct object_id base_oid;
 
+			if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
+				die(_("expected object at offset %"PRIuMAX),
+				    (uintmax_t)base_offset);
+
 			nth_packed_object_id(&base_oid, reuse_packfile,
-					     reuse_packfile->revindex[base_pos].nr);
+					     pack_pos_to_index(reuse_packfile, base_pos));
 
 			len = encode_in_pack_object_header(header, sizeof(header),
 							   OBJ_REF_DELTA, size);

2.30.0.138.g6d7191ea01

Indeed we don't have the object name, but the pack is reuse_packfile (which is statistically initialized), so we could do something like:

index 10a16ced1e..8e40b19ee8 100644
@@ -893,8 +893,10 @@ static void write_reused_pack_one(size_t pos, struct hashfile *out,
 			struct object_id base_oid;
 
 			if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
-				die(_("expected object at offset %"PRIuMAX),
-				    (uintmax_t)base_offset);
+				die(_("expected object at offset %"PRIuMAX" "
+				      "in pack %s"),
+				    (uintmax_t)base_offset,
+				    reuse_packfile->pack_name);
 
 			nth_packed_object_id(&base_oid, reuse_packfile,
 					     pack_pos_to_index(reuse_packfile, base_pos));

Which I think would be clearer.

Thanks,
Taylor

Replace a direct access to the revindex array with 'pack_pos_to_offset()'.

---
 builtin/pack-objects.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index ea7df9270f..4341bc27b4 100644
@@ -948,7 +948,7 @@ static size_t write_reused_pack_verbatim(struct hashfile *out,
 		off_t to_write;
 
 		written = (pos * BITS_IN_EWORD);
-		to_write = reuse_packfile->revindex[written].offset
+		to_write = pack_pos_to_offset(reuse_packfile, written)
 			- sizeof(struct pack_header);
 
 		/* We're recording one chunk, not one object. */

2.30.0.138.g6d7191ea01

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.

---
 builtin/pack-objects.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 4341bc27b4..a193cdaf2f 100644
@@ -1813,11 +1813,11 @@ static void check_object(struct object_entry *entry, uint32_t object_index)
 				goto give_up;
 			}
 			if (reuse_delta && !entry->preferred_base) {
-				struct revindex_entry *revidx;
-				revidx = find_pack_revindex(p, ofs);
-				if (!revidx)
+				uint32_t pos;
+				if (offset_to_pack_pos(p, ofs, &pos) < 0)
 					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;
 			}
 			entry->in_pack_header_size = used + used_0;

2.30.0.138.g6d7191ea01

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

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

Yay. Happy again to see things getting more robust.

-Peff

Replace find_revindex_position() with its counterpart in the new API, offset_to_pack_pos().

---
 pack-bitmap.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

index d88745fb02..d6861ddd4d 100644
@@ -407,11 +407,14 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
 					   const struct object_id *oid)
 {
+	uint32_t pos;
 	off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
 	if (!offset)
 		return -1;
 
-	return find_revindex_position(bitmap_git->pack, offset);
+	if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
+		return -1;
+	return pos;
 }
 
 static int bitmap_position(struct bitmap_index *bitmap_git,

2.30.0.138.g6d7191ea01

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.

---
 pack-bitmap.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

index d6861ddd4d..80c57bde73 100644
@@ -711,21 +711,22 @@ static void show_objects_for_type(
 
 		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
 			struct object_id oid;
-			struct revindex_entry *entry;
-			uint32_t hash = 0;
+			uint32_t hash = 0, n;
+			off_t ofs;
 
 			if ((word >> offset) == 0)
 				break;
 
 			offset += ewah_bit_ctz64(word >> offset);
 
-			entry = &bitmap_git->pack->revindex[pos + offset];
-			nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
+			n = pack_pos_to_index(bitmap_git->pack, pos + offset);
+			ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
+			nth_packed_object_id(&oid, bitmap_git->pack, n);
 
 			if (bitmap_git->hashes)
-				hash = get_be32(bitmap_git->hashes + entry->nr);
+				hash = get_be32(bitmap_git->hashes + n);
 
-			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);
+			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, ofs);
 		}
 	}
 }

2.30.0.138.g6d7191ea01

Much clearer, thank you.

Thanks,
Taylor

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()'.

---
 pack-bitmap.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 80c57bde73..422505d7af 100644
@@ -835,11 +835,11 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
 	oi.sizep = &size;
 
 	if (pos < pack->num_objects) {
-		struct revindex_entry *entry = &pack->revindex[pos];
-		if (packed_object_info(the_repository, pack,
-				       entry->offset, &oi) < 0) {
+		off_t ofs = pack_pos_to_offset(pack, pos);
+		if (packed_object_info(the_repository, pack, ofs, &oi) < 0) {
 			struct object_id oid;
-			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 {

2.30.0.138.g6d7191ea01

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().

---
 pack-bitmap.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

index 422505d7af..3f5cd4e77d 100644
@@ -1069,23 +1069,21 @@ static void try_partial_reuse(struct bitmap_index *bitmap_git,
 			      struct bitmap *reuse,
 			      struct pack_window **w_curs)
 {
-	struct revindex_entry *revidx;
-	off_t offset;
+	off_t offset, header;
 	enum object_type type;
 	unsigned long size;
 
 	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_t base_offset;
-		int base_pos;
+		uint32_t base_pos;
 
 		/*
 		 * Find the position of the base object so we can look it up

@@ -1096,11 +1094,10 @@ static void try_partial_reuse(struct bitmap_index *bitmap_git,
 		 * more detail.
 		 */
 		base_offset = get_delta_base(bitmap_git->pack, w_curs,
-					     &offset, type, revidx->offset);
+					     &offset, type, header);
 		if (!base_offset)
 			return;
-		base_pos = find_revindex_position(bitmap_git->pack, base_offset);
-		if (base_pos < 0)
+		if (offset_to_pack_pos(bitmap_git->pack, base_offset, &base_pos) < 0)
 			return;
 
 		/*

2.30.0.138.g6d7191ea01

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

Thanks. Reading these both back-to-back, I agree that yours is much clearer in describing what is actually going on.

Thanks,
Taylor

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.

---
 pack-bitmap.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

index 3f5cd4e77d..24b9628dca 100644
@@ -1392,11 +1392,10 @@ uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
 
 	for (i = 0; i < num_objects; ++i) {
 		struct object_id oid;
-		struct revindex_entry *entry;
 		struct object_entry *oe;
 
-		entry = &bitmap_git->pack->revindex[i];
-		nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
+		nth_packed_object_id(&oid, bitmap_git->pack,
+				     pack_pos_to_index(bitmap_git->pack, i));
 		oe = packlist_find(mapping, &oid);
 
 		if (oe)

2.30.0.138.g6d7191ea01

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).

---
 packfile.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 86f5c8dbf6..3e3f391949 100644
@@ -1235,18 +1235,18 @@ static int get_delta_base_oid(struct packed_git *p,
 		oidread(oid, base);
 		return 0;
 	} else if (type == OBJ_OFS_DELTA) {
-		struct revindex_entry *revidx;
+		uint32_t base_pos;
 		off_t base_offset = get_delta_base(p, w_curs, &curpos,
 						   type, delta_obj_offset);
 
 		if (!base_offset)
 			return -1;
 
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
+		if (offset_to_pack_pos(p, base_offset, &base_pos) < 0)
 			return -1;
 
-		return nth_packed_object_id(oid, p, revidx->nr);
+		return nth_packed_object_id(oid, p,
+					    pack_pos_to_index(p, base_pos));
 	} else
 		return -1;
 }

2.30.0.138.g6d7191ea01

Perform exactly the same conversion as in the previous commit to another caller within 'packfile.c'.

---
 packfile.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

index 3e3f391949..7c37f9ec5c 100644
@@ -1256,12 +1256,11 @@ static int retry_bad_packed_offset(struct repository *r,
 				   off_t obj_offset)
 {
 	int type;
-	struct revindex_entry *revidx;
+	uint32_t pos;
 	struct object_id oid;
-	revidx = find_pack_revindex(p, obj_offset);
-	if (!revidx)
+	if (offset_to_pack_pos(p, obj_offset, &pos) < 0)
 		return OBJ_BAD;
-	nth_packed_object_id(&oid, p, revidx->nr);
+	nth_packed_object_id(&oid, p, pack_pos_to_index(p, pos));
 	mark_bad_packed_object(p, oid.hash);
 	type = oid_object_info(r, &oid, NULL);
 	if (type <= OBJ_NONE)

2.30.0.138.g6d7191ea01

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)'.

---
 packfile.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

index 7c37f9ec5c..469c8d4f57 100644
@@ -1537,8 +1537,13 @@ int packed_object_info(struct repository *r, struct packed_git *p,
 	}
 
 	if (oi->disk_sizep) {
-		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-		*oi->disk_sizep = revidx[1].offset - obj_offset;
+		uint32_t pos;
+		if (offset_to_pack_pos(p, obj_offset, &pos) < 0) {
+			type = OBJ_BAD;
+			goto out;
+		}
+
+		*oi->disk_sizep = pack_pos_to_offset(p, pos + 1) - obj_offset;
 	}
 
 	if (oi->typep || oi->type_name) {

2.30.0.138.g6d7191ea01

Good.

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).

Yep. Again, I'm really happy to see these "should never happen" cases converted to real errors or even BUG()s.

-Peff

Indeed, and we have the object's offset and pack name to include, too, so our error can be quite descriptive.

:-).

Thanks,
Taylor

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.

---
 packfile.c | 24 ++++++++++++++++--------
 1 file changed, 16 insertions(+), 8 deletions(-)

index 469c8d4f57..34467ea4a3 100644
@@ -1692,11 +1692,19 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 		}
 
 		if (do_check_packed_object_crc && p->index_version > 1) {
-			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-			off_t len = revidx[1].offset - obj_offset;
-			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
+			uint32_t pos, nr;
+			off_t len;
+
+			if (offset_to_pack_pos(p, obj_offset, &pos) < 0) {
+				data = NULL;
+				goto out;
+			}
+
+			len = pack_pos_to_offset(p, pos + 1) - obj_offset;
+			nr = pack_pos_to_index(p, pos);
+			if (check_pack_crc(p, &w_curs, obj_offset, len, nr)) {
 				struct object_id oid;
-				nth_packed_object_id(&oid, p, revidx->nr);
+				nth_packed_object_id(&oid, p, nr);
 				error("bad packed object CRC for %s",
 				      oid_to_hex(&oid));
 				mark_bad_packed_object(p, oid.hash);

@@ -1779,11 +1787,11 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			 * This is costly but should happen only in the presence
 			 * of a corrupted pack, and is better than failing outright.
 			 */
-			struct revindex_entry *revidx;
+			uint32_t pos;
 			struct object_id base_oid;
-			revidx = find_pack_revindex(p, obj_offset);
-			if (revidx) {
-				nth_packed_object_id(&base_oid, p, revidx->nr);
+			if (!(offset_to_pack_pos(p, obj_offset, &pos))) {
+				nth_packed_object_id(&base_oid, p,
+						     pack_pos_to_index(p, pos));
 				error("failed to read delta base object %s"
 				      " at offset %"PRIuMAX" from %s",
 				      oid_to_hex(&base_oid), (uintmax_t)obj_offset,

2.30.0.138.g6d7191ea01

Much clearer, thanks.

Yup, good call.

Thanks, this rationale is helpful to have. I included an abridged version of it in the patch message.

Thanks,
Taylor

Avoid looking at the 'revindex' pointer directly and instead call 'pack_pos_to_index()'.

---
 packfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 34467ea4a3..46c9c7ea3c 100644
@@ -2082,7 +2082,7 @@ int for_each_object_in_pack(struct packed_git *p,
 		struct object_id oid;
 
 		if (flags & FOR_EACH_OBJECT_PACK_ORDER)
-			pos = p->revindex[i].nr;
+			pos = pack_pos_to_index(p, i);
 		else
 			pos = i;
 

2.30.0.138.g6d7191ea01

'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.

---
 builtin/gc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 4c24f41852..c60811f212 100644
@@ -301,7 +301,7 @@ static uint64_t estimate_repack_memory(struct packed_git *pack)
 	/* and then obj_hash[], underestimated in fact */
 	heap += sizeof(struct object *) * nr_objects;
 	/* revindex is used also */
-	heap += sizeof(struct revindex_entry) * nr_objects;
+	heap += (sizeof(off_t) + sizeof(uint32_t)) * nr_objects;
 	/*
 	 * read_sha1_file() (either at delta calculation phase, or
 	 * writing phase) also fills up the delta base cache

2.30.0.138.g6d7191ea01

This is so far the only not-completely-obvious change.

And this might be enough justification for it, but...

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.

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?)

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

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

Now that no callers of 'find_pack_revindex()' remain, remove the function's declaration and implementation entirely.

---
 pack-revindex.c | 15 ---------------
 pack-revindex.h |  2 --
 2 files changed, 17 deletions(-)

index 6d86a85208..4e42238906 100644
@@ -189,21 +189,6 @@ int find_revindex_position(struct packed_git *p, off_t ofs)
 	return -1;
 }
 
-struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)
-{
-	int pos;
-
-	if (load_pack_revindex(p))
-		return NULL;
-
-	pos = find_revindex_position(p, ofs);
-
-	if (pos < 0)
-		return NULL;
-
-	return p->revindex + pos;
-}
-
 int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
 {
 	int ret;

index 256c0a9106..07c1a7a3c8 100644
@@ -11,8 +11,6 @@ struct revindex_entry {
 int load_pack_revindex(struct packed_git *p);
 int find_revindex_position(struct packed_git *p, off_t ofs);
 
-struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs);
-
 int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos);
 uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);
 off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);

2.30.0.138.g6d7191ea01

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.

---
 pack-revindex.c | 29 +++++++++++------------------
 pack-revindex.h |  1 -
 2 files changed, 11 insertions(+), 19 deletions(-)

index 4e42238906..9392c4be73 100644
@@ -169,16 +169,23 @@ int load_pack_revindex(struct packed_git *p)
 	return 0;
 }
 
-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;
-}
-
 uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos)
 {
 	if (!p->revindex)

index 07c1a7a3c8..b5dd114fd5 100644
@@ -9,7 +9,6 @@ struct revindex_entry {
 };
 
 int load_pack_revindex(struct packed_git *p);
-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);
 uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);

2.30.0.138.g6d7191ea01

*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.

Thanks,
Taylor

RIGHT. My bad.

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

Sounds good.

Good catch. We might want to drop the initialization of "lo":

:-). I agree it's a minor point, but I think that the symmetry is nice, so it's worth doing.

I'll let both of these be an raw unsigned, since the midpoint is already labeled as an unsigned.

Thanks,
Taylor

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

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.

---
 pack-revindex.c | 5 +++++
 pack-revindex.h | 5 -----
 2 files changed, 5 insertions(+), 5 deletions(-)

index 9392c4be73..36ef276378 100644
@@ -3,6 +3,11 @@
 #include "object-store.h"
 #include "packfile.h"
 
+struct revindex_entry {
+	off_t offset;
+	unsigned int nr;
+};
+
 /*
  * Pack index for existing packs give us easy access to the offsets into
  * corresponding pack file where each object's data starts, but the entries

index b5dd114fd5..b501a7cd62 100644
@@ -3,11 +3,6 @@
 
 struct packed_git;
 
-struct revindex_entry {
-	off_t offset;
-	unsigned int nr;
-};
-
 int load_pack_revindex(struct packed_git *p);
 
 int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos);

2.30.0.138.g6d7191ea01

That was a lot of patches to get here, but this is a very nice outcome. :)

-Peff

To prepare for on-disk reverse indexes, remove a spot in 'offset_to_pack_pos()' that looks at the 'revindex' array in 'struct packed_git'.

Even though this use of the revindex pointer is within pack-revindex.c, this clean up is still worth doing. Since the 'revindex' pointer will be NULL when reading from an on-disk reverse index (instead the 'revindex_data' pointer will be mmaped to the 'pack-*.rev' file), this call-site would have to include a conditional to lookup the offset for position 'mi' each iteration through the search.

So instead of open-coding 'pack_pos_to_offset()', call it directly from within 'offset_to_pack_pos()'.

---
 pack-revindex.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 36ef276378..2cd9d632f1 100644
@@ -178,20 +178,20 @@ int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
 {
 	int lo = 0;
 	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) {
+		off_t got = pack_pos_to_offset(p, mi);
+
+		if (got == ofs) {
 			*pos = mi;
 			return 0;
-		} else if (ofs < revindex[mi].offset)
+		} else if (ofs < got)
 			hi = mi;
 		else
 			lo = mi + 1;

2.30.0.138.g6d7191ea01

This definitely makes sense in the long run. I could take or leave it as a final patch in _this_ series (as opposed to the first patch in a subsequent series adding the rev files).

Funny enough, I have moved this patch between the two so many times before submitting this. I tend to agree that I don't think it makes a difference in which series this patch goes, so I'm just as happy to leave it where it is and stop thinking about it ;-).

If others have strong feelings, this can be dropped when queuing and I'll send it along as the first commit in the second series (which will have to be updated along with this one).

Thanks,
Taylor

On 1/8/2021 1:16 PM, Taylor Blau wrote:
...

This patch series has a clear layout that was easy to follow.

In a vacuum, the conversions from immediate struct member lookups to API calls seems like adding overhead to something that is done frequently in a loop. However, you do justify it:

Even if these method calls do add a bit of overhead to each access, it helps to not compute the table from scratch before any access is possible.

This will be particularly valuable for operations that use only a few position lookups, such as "is object A reachable from commit C?"

Operations that iterate through every object in a bitmap are more likely to notice a difference, but that will probably be visible in the next series.

My comments on this series are very minor.

I made only one comment about "if (method() < 0)" versus "if (method())" but that pattern appears in multiple patches. _If_ you decide to change that pattern, then I'm sure you can find all uses.

Thanks,
-Stolee

I have no strong opinion here, so I'm happy to defer to your or others' judgement. My very weak opinion is that I'd just as soon leave it as-is, but that if I'm rerolling and others would like to see it changed, then I'm happy to do it.

Thank you for your review. I think that I owe you some as well, somewhere in the near-2,000 emails that I still have :-/.

Thanks,
Taylor

Well, I found 782 instances of ") < 0)" in the codebase, and my initial scan of these shows they are doing exactly what you are asking. So as far as code style goes, there is plenty of precedent.

The thing that makes me react to this is that it _looks_ like an extra comparison. However, I'm sure the assembly instructions have the same performance characteristics between "!= 0" and "< 0".

Thanks,
-Stolee

Thanks for looking, I was curious about that myself after our thread, but I hadn't yet bothered to look.

It should make no difference. Both comparisons will do a 'cmp $0 ...' where '...' is probably an indirect into the current frame. The '!= 0' will use je, and the '< 0' comparison will use 'jns'. Both conditional jumps should be implemented by checking a CPU flag only (ZF and SF, respectively).

Not that any of this matters, it's just fun to look.

Thanks,
Taylor

I'd prefer to keep it that way for the human cost's point of view.

Perhaps it could be subjective but

if (func_that_signals_error_with_return_value() < 0)

is immediately recognizable as checking for an error to folks who were trained to write C in POSIX environment, as "on error, return negative" is a convention that they are familiar with. At least to me, your "if (func_that_signals_error_with_return_value())" looks unnatural and makes me look at the function to see what its return value means.

If there are helper functions that use "non-zero is an error and zero is success" convention, we should look at them to see why they do not do the usual "a negative is an error and a non-negative is success". And if the *only* reason they do so is because their normal return do not have to give more than one kind of "success", we should see if we can fix them to follow the usual "a negative is an error" convention, I would think.

Thanks.

Or thinking about it more fundamentally: any operation which touches the revindex is now O(nr_objects_in_repo), even if it only cares about a few objects. Ideally this will eventually be this O(log nr_objects_in_repo); we can't do much better than that because of object lookups (unless we replace the .idx with a perfect hash or something).

It looks good overall to me. I left a few nits around documentation and integer types that I think are worth a re-roll, but I think after addressing those it should be good.

-Peff

Thanks so much for your review. I think I addressed all of your feedback, but I'll sit on the revised patches for another day or so in case other reviewers would like to chime in before v2.

Hopefully the this re-roll is the only one we'll need, since the next series is much more interesting!

Thanks,
Taylor

Queued; seems to be killed on Windows but otherwise looking good.

https://github.com/git/git/runs/1691849288?check_suite_focus=true#step:6:164

Thanks.

Thanks.

I will look into those failures. It looks like these are all due to running 'git index-pack' when the '*.idx' file already exists (resulting in Windows being unable to write over the file).

Did you want to queue these two topics separately? It looks like you picked them up in 'seen' as one big topic in a8f367dae2 (Merge branch 'tb/pack-revindex-api' into jch, 2021-01-12), but I thought you may want to pick parts one and two up separately to allow them to progress independently of one another.

In either case, I am planning on sending a new version of the first series tomorrow to address Peff's feedback.

Thanks,
Taylor

Unless it is a reasonable amount of certainty that the bottom topic will not have to be rerolled, I'd rather not to have separate topics on top of each other.

It is tedious and error prone, having to rebase the old iteration of the top topic on top when a new iteration of the bottom topic comes out. I'd rather see that the top one get rerolled whenever the bottom one gets rerolled to make life simpler.

Even in a single topic, I would encourage people to put the foundational and preparatory work early so that we can make them solidify before review really gets to later parts of the series.

And when a series is structured like so, it is perfectly fine to say something like:

Here is a new iteration of the last 7 patches---the early 13 patches are the same as the previous round, so reset the topic to bb6414ab (packfile: prepare for the existence of '*.rev' files, 2021-01-08) and then apply these 7.

if you do not want to send all patches in a nontrivial series when it gets updated.

Thanks.

Hmm. I certainly do not want to create any tedious work for you, but I do think that we're in a situation where the bottom topic is stable and the interesting discussion will happen in the newer topic.

Indeed, my local v2 of the bottom topic requires the top topic to be rebased onto it, and so I'll plan to send a v2 of each tomorrow morning.

I am happy to do it this way if you would prefer. If so, you may want to rename this topic while queuing, since it is not just about a new revindex API, but rather about introducing the on-disk format. (I would suggest tb/on-disk-revindex, if you were looking for alternate names).

If you agree that the bottom topic is stable, I'd prefer to send the top one separately. Otherwise, I can send both together. Let me know.

Thanks,
Taylor

I do not expect the first 20 of the 20+8 patches to be stable from the beginning---in fact, after reading 01/20 myself, and seeing a few of Peff's reviews, I expect that you'll be redoing at least some of them.

When we deal with this kind of situation (not limited to these topics), let's make it a tradition to first pretend that we have a long single topic, and expect that the early rounds of review focus on two things:

(1) to identify the best ordering of the commits (topics from experienced contributors like you are likely to be already structured in a good order, so reviewers may only have to say "the ordering looks good", but sometimes they may want to say thinks like "it would be better to leave patches 5, 8 and 11 to much later in the series".

(2) to find good points to divide the series into two (or more) pieces, and spend more effort on helping the bottom part to solidify faster.

That way, the bottom part can be merged sooner to 'next' than the rest. It always is cumbersome to have some part of the series in 'next' and remainder in 'seen', so at that point, the lower half would naturally gain a different name before it gets merged to 'next', I would think.

Thanks.

They'll definitely need at least one re-roll. But I think Taylor is expecting (and I do too) that the second half will probably have a lot more back-and-forth over the on-disk format, and hence need more re-rolls.

My main concern is reviewer fatigue. 28 patches is a lot. If we can solidify the first 20 and then let people focus on the final 8 separately, that helps. If you're OK with splitting a topic and saying "this is a re-roll of just the last 8 patches", then that problem is solved. But IMHO it is easier to just point out that split from the start than it is to come up with it after the fact. It tells reviewers what to expect from the get-go.

I think we just did that preemptively. ;) In these two particular series, the first 20 (or at least the first 19) are an improvement by themselves. I think they would be worth doing even without the final 8, both to make calling code more readable and to add new error checks and assertions to revindex access.

That seems to me like it ends up being _more_ work than just making them into two branches in the first place.

So I guess I remain skeptical that ad-hoc splitting of longer series is easier than doing so up front. But you're the one who does all of the branch shuffling in the end, so if you really prefer longer series, I'm not what I think matters that much. ;)

-Peff

Indeed, I find the first ~20 patches fairly benign, and I think that the interesting discussion will and should take place over the final 8 patches.

For what it's worth, I was referring to the pending re-roll I have of the first 20 patches as the stable one. (Peff notes in [1] that he thought there wasn't much else to consider beyond his comments.)

Yes, exactly.

I agree, but I also wasn't aware that you would consider queuing part of a series. If that's the route you want to take, I'm OK with that. But I tend to agree with Peff that (in this case since a clear deliniation already exists) it may save us time to just send two separate series from the get-go.

Agreed. Junio, let me know which you'd prefer in this case (I'm not sure if the additional context has changed your mind or not).

Thanks,
Taylor

[1]: https://lore.kernel.org/git/X%[email protected]/

More work to contributors? How?

As long as each of 20-patch and 8-patch series is marked clearly to manage the risk of mistakes and confusion down to the same level as a single long series, I am perfectly OK.

Examples of help contributors could have made, which would have avoided past confusion (these are not "potential" ones, but I had to redo day's intergration in the past because of one long topic building on top of another) are:

- When sending either topic, not limited to the initial round but in all the subsequent rounds, remind that the top topic is to be applied on top of the bottom topic.

- When updating the bottom topic (e.g. 20-patch one in this case), send out the top one (e.g. 8-patch one), too (or instruct me to discard the top one tentatively).

The worst case that happened in the past was that a quite minor tweak was made to a bottom topic that was depended on another topic, so I just queued the new iteration of the bottom topic again, without realizing that the other one needed to be rebased. We ended up two copies of the bottom topic commits in 'pu' (these days we call it 'seen') as the tweak was so minor that the two topics cleanly merged into 'pu' without causing conflict. The next bad case was a similar situation with larger rewrite of the bottom topic, which caused me to look at quite a big conflict and waste my time until I realized that I was missing an updated top half.

If the inter-dependent topics that caused me trouble were managed as a single long patch series, either with "this is a full replacement of the new iteration" or "these are to update only the last 8 patches; apply them after rewinding the topic to commit f0e1d2c3 (gostak: distim doshes, 2021-01-08)", would have had a lot less risk to introduce human error on this end.

Discarding broken part of a series and only queuing a good part can happen with or without multiple topics. Merging one topic to 'next' but not the other also happens. Merging early part of a topic to 'next' while leaving the rest to 'seen' is possible but I'd prefer to avoid it. Because of the last one, a single long topic, when a bottom part stabilizes enough, would likely to gain a separate name and its tip would be merged to 'next'.

As long as the two serieses are marked as such clearly, not just in the initial round but in all subsequent rounds, it is OK. But in an unproven initial round, you may regret having to move a patch across topics, from the bottom one to the top one or vice versa, instead of just reordering inside a single topic.

Nobody suggested ad-hoc splitting. I was saying that splitting would naturally grow out of reviews toward stabilization.

Sounds good. Like I said, the last thing I want to do is create undue burden on your or anybody else when queuing or reviewing these topics.

So, I'll try to err on the side of stating the dependency between topics too often rather than not often enough. Hopefully the first ~20 patches are boring enough that they will make their way to master soon enough and we don't have to worry about it.

Ordinarily, I would have held off on the second series until more the first one had graduated, but I felt that the pure refactorings didn't make much sense on their own without the new file-based backend to motivate them.

Thanks,
Taylor

The quoted part is from me, so I'll respond: I didn't mean contributors, but it seems like more work to you. I.e., you are ending up with the same multi-branch config _and_ you have to split the branches yourself later after seeing review.

But reading what you wrote below, the advantage is that if this does not happen until the first part hits "next", then there is no chance of it being rebased at that point (and thus getting rewritten out from under the second topic).

I somehow assumed you had more automation there. On my end, since I rebase my topics aggressively, it is just a matter of pointing the branch upstream in the right place. But of course that is not your workflow at all.

I know you do have the "this branches uses" logic in your what's cooking emails. In theory it could remind you of the situation, but I'm not sure where in the workflow you'd insert it (by the time you run the WC script, it is hard to realize the rebasing that _should_ have been done earlier, unless you collate patch-ids, and even that is not 100%).

I do wonder if setting the dependent branch's @{upstream} would be helpful here. You do not rebase all of your topics, but the ones with a local-branch @{u} would be candidates for doing so.

All that said, I am also sensitive that my armchair "you could do it like this..." suggesting may not be fully informed. So take it as idle thoughts, not necessarily arguments. :)

This quote is me again. By "ad-hoc" I meant exactly this "after we see some reviews" (as opposed to drawing a line up front).

-Peff

Hi,

Here is a revision of the first of two series to prepare for and introduce an on-disk alternative for storing the reverse index.

In this revision, I addressed feedback from Junio, Peff, and Stolee. A range-diff is included below, but the main changes are:

- Error messages are improved to include the pack and offset when applicable.
- Variable names were made clearer (e.g., n -> index_pos).
- Comments were added in pack-revindex.h to introduce relevant terminology, and which methods convert between what orderings.
- int-sized lower- and upper-bounds were converted to be unsigned.

I believe that this revision should be ready for queueing. I'll send a v2 of the corresponding latter series shortly.

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 | 37 +++++++++++++++++---------
 pack-bitmap.c          | 44 +++++++++++++++----------------
 pack-revindex.c        | 51 ++++++++++++++++++++++-------------
 pack-revindex.h        | 60 +++++++++++++++++++++++++++++++++++++-----
 packfile.c             | 54 ++++++++++++++++++++++++-------------
 6 files changed, 168 insertions(+), 80 deletions(-)

Range-diff against v1:

 1:  fa6b830908 <  -:  ---------- pack-revindex: introduce a new API
 -:  ---------- >  1:  e1aa89244a pack-revindex: introduce a new API
 2:  00668523e1 !  2:  0fca7d5812 write_reuse_object(): convert to new revindex API
    @@ builtin/pack-objects.c: static off_t write_reuse_object(struct hashfile *f, stru
     -	revidx = find_pack_revindex(p, offset);
     -	datalen = revidx[1].offset - offset;
     +	if (offset_to_pack_pos(p, offset, &pos) < 0)
    -+		die(_("write_reuse_object: could not locate %s"),
    -+		    oid_to_hex(&entry->idx.oid));
    ++		die(_("write_reuse_object: could not locate %s, expected at "
    ++		      "offset %"PRIuMAX" in pack %s"),
    ++		    oid_to_hex(&entry->idx.oid), (uintmax_t)offset,
    ++		    p->pack_name);
     +	datalen = pack_pos_to_offset(p, pos + 1) - offset;
      	if (!pack_to_stdout && p->index_version > 1 &&
     -	    check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {
 3:  81ab11e18c !  3:  7676822a54 write_reused_pack_one(): convert to new revindex API
    @@ builtin/pack-objects.c: static void write_reused_pack_one(size_t pos, struct has
      			struct object_id base_oid;
      
     +			if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
    -+				die(_("expected object at offset %"PRIuMAX),
    -+				    (uintmax_t)base_offset);
    ++				die(_("expected object at offset %"PRIuMAX" "
    ++				      "in pack %s"),
    ++				    (uintmax_t)base_offset,
    ++				    reuse_packfile->pack_name);
     +
      			nth_packed_object_id(&base_oid, reuse_packfile,
     -					     reuse_packfile->revindex[base_pos].nr);
 4:  14b35d01a0 =  4:  dd7133fdb7 write_reused_pack_verbatim(): convert to new revindex API
 5:  c47e77a30e =  5:  8e93ca3886 check_object(): convert to new revindex API
 6:  3b170663dd =  6:  084bbf2145 bitmap_position_packfile(): convert to new revindex API
 7:  bc67bb462a !  7:  68794e9484 show_objects_for_type(): convert to new revindex API
    @@ pack-bitmap.c: static void show_objects_for_type(
      			struct object_id oid;
     -			struct revindex_entry *entry;
     -			uint32_t hash = 0;
    -+			uint32_t hash = 0, n;
    ++			uint32_t hash = 0, index_pos;
     +			off_t ofs;
      
      			if ((word >> offset) == 0)
    @@ pack-bitmap.c: static void show_objects_for_type(
      
     -			entry = &bitmap_git->pack->revindex[pos + offset];
     -			nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
    -+			n = pack_pos_to_index(bitmap_git->pack, pos + offset);
    ++			index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset);
     +			ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
    -+			nth_packed_object_id(&oid, bitmap_git->pack, n);
    ++			nth_packed_object_id(&oid, bitmap_git->pack, index_pos);
      
      			if (bitmap_git->hashes)
     -				hash = get_be32(bitmap_git->hashes + entry->nr);
    -+				hash = get_be32(bitmap_git->hashes + n);
    ++				hash = get_be32(bitmap_git->hashes + index_pos);
      
     -			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);
     +			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, ofs);
 8:  541fe679f3 =  8:  31ac6f5703 get_size_by_pos(): convert to new revindex API
 9:  54f4ad329f !  9:  acd80069a2 try_partial_reuse(): convert to new revindex API

@@ Commit message
'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().
+ 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).

10:  97eaa7b2d6 = 10:  569acdca7f rebuild_existing_bitmaps(): convert to new revindex API
11:  e00c434ab2 = 11:  9881637724 get_delta_base_oid(): convert to new revindex API
12:  aae01d7029 = 12:  df8bb571a5 retry_bad_packed_offset(): convert to new revindex API
13:  eab7ab1f35 ! 13:  41b2e00947 packed_object_info(): convert to new revindex API
    @@ packfile.c: int packed_object_info(struct repository *r, struct packed_git *p,
     -		*oi->disk_sizep = revidx[1].offset - obj_offset;
     +		uint32_t pos;
     +		if (offset_to_pack_pos(p, obj_offset, &pos) < 0) {
    ++			error("could not find object at offset %"PRIuMAX" "
    ++			      "in pack %s", (uintmax_t)obj_offset, p->pack_name);
     +			type = OBJ_BAD;
     +			goto out;
     +		}
14:  13c49ed40c ! 14:  8ad49d231f unpack_entry(): convert to new revindex API
    @@ Commit message
         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.
    +    'pack_pos_to_index()' and so on).
    +
    +    Add an additional check to make sure that 'obj_offset()' points at a
    +    valid object. In the case this check is violated, we cannot call
    +    'mark_bad_packed_object()' because we don't know the OID. At the top of
    +    the call stack is do_oid_object_info_extended() (via
    +    packed_object_info()), which does mark the object.
     
         Signed-off-by: Taylor Blau <[email protected]>
     
    @@ packfile.c: void *unpack_entry(struct repository *r, struct packed_git *p, off_t
     -			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
     -			off_t len = revidx[1].offset - obj_offset;
     -			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
    -+			uint32_t pos, nr;
    ++			uint32_t pack_pos, index_pos;
     +			off_t len;
     +
    -+			if (offset_to_pack_pos(p, obj_offset, &pos) < 0) {
    ++			if (offset_to_pack_pos(p, obj_offset, &pack_pos) < 0) {
    ++				error("could not find object at offset %"PRIuMAX" in pack %s",
    ++				      (uintmax_t)obj_offset, p->pack_name);
     +				data = NULL;
     +				goto out;
     +			}
     +
    -+			len = pack_pos_to_offset(p, pos + 1) - obj_offset;
    -+			nr = pack_pos_to_index(p, pos);
    -+			if (check_pack_crc(p, &w_curs, obj_offset, len, nr)) {
    ++			len = pack_pos_to_offset(p, pack_pos + 1) - obj_offset;
    ++			index_pos = pack_pos_to_index(p, pack_pos);
    ++			if (check_pack_crc(p, &w_curs, obj_offset, len, index_pos)) {
      				struct object_id oid;
     -				nth_packed_object_id(&oid, p, revidx->nr);
    -+				nth_packed_object_id(&oid, p, nr);
    ++				nth_packed_object_id(&oid, p, index_pos);
      				error("bad packed object CRC for %s",
      				      oid_to_hex(&oid));
      				mark_bad_packed_object(p, oid.hash);
15:  a3249986f9 = 15:  e757476351 for_each_object_in_pack(): convert to new revindex API
16:  7c17db7a7d = 16:  a500311e33 builtin/gc.c: guess the size of the revindex
17:  c4c88bcc3d ! 17:  67d14da04a pack-revindex: remove unused 'find_pack_revindex()'

@@ pack-revindex.h: struct revindex_entry {

-struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs); -
- int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos);
- uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);
- off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos);
+ /*
+ * offset_to_pack_pos converts an object offset to a pack position. This
+ * function returns zero on success, and a negative number otherwise. The
18: d60411d524 ! 18: 3b5c92be68 pack-revindex: remove unused 'find_revindex_position()'

    @@ Commit message
         until _after_ 'load_pack_revindex()' (which loads the index as a
         side-effect) has been called.
     
    +    Another small fix that is included is converting the upper- and
    +    lower-bounds to be unsigned's instead of ints. This dates back to
    +    92e5c77c37 (revindex: export new APIs, 2013-10-24)--ironically, the last
    +    time we introduced new APIs here--but this unifies the types.
    +
         Signed-off-by: Taylor Blau <[email protected]>
     
      ## pack-revindex.c ##
    @@ pack-revindex.c: int load_pack_revindex(struct packed_git *p)
     -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 lo = 0;
     -	int hi = p->num_objects + 1;
     -	const struct revindex_entry *revindex = p->revindex;
    -+	int hi;
    ++	unsigned lo, hi;
     +	const struct revindex_entry *revindex;
     +
     +	if (load_pack_revindex(p) < 0)
     +		return -1;
     +
    ++	lo = 0;
     +	hi = p->num_objects + 1;
     +	revindex = p->revindex;
      
    @@ pack-revindex.c: int find_revindex_position(struct packed_git *p, off_t ofs)
     -
     -	ret = find_revindex_position(p, ofs);
     -	if (ret < 0)
    --		return -1;
    +-		return ret;
     -	*pos = ret;
     -	return 0;
     -}
    @@ pack-revindex.c: int find_revindex_position(struct packed_git *p, off_t ofs)
     
      ## pack-revindex.h ##
     @@ pack-revindex.h: struct revindex_entry {
    - };
    - 
    +  * given pack, returning zero on success and a negative value otherwise.
    +  */
      int load_pack_revindex(struct packed_git *p);
     -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);
    - uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos);
    + /*
    +  * offset_to_pack_pos converts an object offset to a pack position. This

19: 7c0e4acc84 ! 19: cabafce4a1 pack-revindex: hide the definition of 'revindex_entry'
@@ pack-revindex.h
- unsigned int nr;
-};
-
- int load_pack_revindex(struct packed_git *p);
-
- int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos);
+ /*
+ * load_pack_revindex populates the revindex's internal data-structures for the
+ * given pack, returning zero on success and a negative value otherwise.
20: eada1ffcfa ! 20: 8400ff6c96 pack-revindex.c: avoid direct revindex access in 'offset_to_pack_pos()'
@@ Commit message

## pack-revindex.c ##
-@@ pack-revindex.c: int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos) +@@ pack-revindex.c: int load_pack_revindex(struct packed_git *p)
+ int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos)
{
- int lo = 0;
- int hi;
+ unsigned lo, hi;
- const struct revindex_entry *revindex;

if (load_pack_revindex(p) < 0)
return -1;

+ lo = 0;
hi = p->num_objects + 1;
- revindex = p->revindex;

2.30.0.138.g6d7191ea01

In the next several patches, we will prepare for loading a reverse index either in memory (mapping the inverse of the .idx's contents in-core), or directly from a yet-to-be-introduced on-disk format. To prepare for 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.

Any error simply calls BUG(), since the callers are not well-suited to handle a failure and keep going.

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(). The same thinking about error conditions applies here as well.

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 should always pass an offset which points at the boundary of two objects. The API, unlike direct access, enforces that that is the case.

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.

Two design warts are carried over into the new API:

- Asking for the index position of an out-of-bounds object will result in a BUG() (since no such object exists), but asking for the offset of the non-existent object at the end of the pack returns the total size of the pack.

This makes it convenient for callers who always want to take the difference of two adjacent object's offsets (to compute the on-disk size) but don't want to worry about boundaries at the end of the pack.

- offset_to_pack_pos() lazily loads the reverse index, but pack_pos_to_index() doesn't (callers of the former are well-suited to handle errors, but callers of the latter are not).

---
 pack-revindex.c | 32 +++++++++++++++++++++++++++++
 pack-revindex.h | 54 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

index ecdde39cf4..0ca3b54b45 100644
@@ -203,3 +203,35 @@ struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs)
 
 	return p->revindex + pos;
 }
+
+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 ret;
+	*pos = ret;
+	return 0;
+}
+
+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 (p->num_objects <= pos)
+		BUG("pack_pos_to_index: out-of-bounds object at %"PRIu32, pos);
+	return p->revindex[pos].nr;
+}
+
+off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos)
+{
+	if (!p->revindex)
+		BUG("pack_pos_to_index: reverse index not yet loaded");
+	if (p->num_objects < pos)
+		BUG("pack_pos_to_offset: out-of-bounds object at %"PRIu32, pos);
+	return p->revindex[pos].offset;
+}

2.30.0.138.g6d7191ea01

It is somewhat strange to see a function that yields a non-negative "position" on success and a negative value to signal a failure to have a separate pointer to the location to receive the true return value. Do we truly care the upper half of "uint32_t" (in other words, do we seriously want to support more than 2G positions in a pack)?

What I'm trying to get at is that

		int pos = offset_to_pack_pos(...);
		if (pos < 0)
			error();
		else
			use(pos);

is more natural than

		uint32_t pos;
                if (offset_to_pack_pos(..., &pos) < 0)
			error();
		else
			use(pos);

but now I wrote it down and laid it out in front of my eyes, the latter does not look too bad.

... later comes back after reading through the series ...

The new callers all looked quite nice to eyes. Because we discourage assignment inside if() condition, the converted result does not make the code more verbose than the original. In fact, it makes it even clearer that we are checking for an error return from a function call.

Quite nice.

Is it a good idea to commit to such performance characteristics as a promise to callers like this (the comment applies to all three functions)?

It depends on how a developer is helped by this comment when deciding whether to use this function, or find other ways, to implement what s/he wants to do.

I think it is easier to read if the "unlike the above function, this allows pos that is one beyond the last object" is explained next to "if out of bounds, it is an error", not as a part of the previous paragraph.

I agree that this is used commonly, but usually in the case that we are finding a position in the list _or where such an item would be inserted_. For example:

	pos = index_name_pos(istate, dirname, len);
	if (pos < 0)
		pos = -pos-1;
	while (pos < istate->cache_nr) {
		...

But that does not apply in this case. Knowing that the requested offset lies between object 'i' and object 'i + 1' isn't helpful, since the offset still does not correspond to the start of an object.

As someone who spends a decent amount of time working in C#, I also like this pattern. The APIs in C# work this way, too, such as:

	if (!set.TryGetValue(key, out value))
		return false;

	// Use 'value', which is initialized now.

Thanks,
-Stolee

I don't think that we care about that as much as we do about potential misuse of a signed return value. There are indeed a couple of spots where a potential negative return value is ignored, and then used to lookup an object in a pack, or some such.

And that's part of the goal of this API: we have strict guidelines about when the output parameter is and isn't usable. That makes it more difficult to accidentally use an uninitialized value / negative number.

OK, good :-).

Thank you :-D.

I don't mind it. If they all had the same performance characteristics, I wouldn't be for it, but since they don't, I think that it's good to know. Peff suggested this back in [1].

Thanks,
Taylor

[1]: https://lore.kernel.org/git/X%[email protected]/

Yeah, I asked for this. As somebody who has frequently worked on the code which accesses the revindex (mostly bitmap stuff), I found it useful to understand how expensive the operations were. However, I also know what their runtimes are at this point, and it is not like somebody interested cannot look at the implementation. So it may not be that important.

So I do still think it is useful, but if somebody feels strongly against it, I don't mind it being removed.

-Peff

That won't be me. It's not like you'd use pack_pos_to_index() combined with pack_pos_to_offset() instead of offset_to_pack_pos() because the latter is more expensive than using the other two functions; the comment does not help those who want to know relative performance of these functions for such a purpose.

I was just curious who the comments were meant to help, that's all.

Thanks.

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()'.

---
 builtin/pack-objects.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

index 2a00358f34..ab1fd853f1 100644
@@ -419,7 +419,7 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,
 {
 	struct packed_git *p = IN_PACK(entry);
 	struct pack_window *w_curs = NULL;
-	struct revindex_entry *revidx;
+	uint32_t pos;
 	off_t offset;
 	enum object_type type = oe_type(entry);
 	off_t datalen;

@@ -436,10 +436,15 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,
 					      type, entry_size);
 
 	offset = entry->in_pack_offset;
-	revidx = find_pack_revindex(p, offset);
-	datalen = revidx[1].offset - offset;
+	if (offset_to_pack_pos(p, offset, &pos) < 0)
+		die(_("write_reuse_object: could not locate %s, expected at "
+		      "offset %"PRIuMAX" in pack %s"),
+		    oid_to_hex(&entry->idx.oid), (uintmax_t)offset,
+		    p->pack_name);
+	datalen = pack_pos_to_offset(p, pos + 1) - offset;
 	if (!pack_to_stdout && p->index_version > 1 &&
-	    check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) {
+	    check_pack_crc(p, &w_curs, offset, datalen,
+			   pack_pos_to_index(p, pos))) {
 		error(_("bad packed object CRC for %s"),
 		      oid_to_hex(&entry->idx.oid));
 		unuse_pack(&w_curs);

2.30.0.138.g6d7191ea01

Replace direct revindex accesses with calls to 'pack_pos_to_offset()' and 'pack_pos_to_index()'.

---
 builtin/pack-objects.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

index ab1fd853f1..8e40b19ee8 100644
@@ -868,8 +868,8 @@ static void write_reused_pack_one(size_t pos, struct hashfile *out,
 	enum object_type type;
 	unsigned long size;
 
-	offset = reuse_packfile->revindex[pos].offset;
-	next = reuse_packfile->revindex[pos + 1].offset;
+	offset = pack_pos_to_offset(reuse_packfile, pos);
+	next = pack_pos_to_offset(reuse_packfile, pos + 1);
 
 	record_reused_object(offset, offset - hashfile_total(out));
 

@@ -889,11 +889,17 @@ static void write_reused_pack_one(size_t pos, struct hashfile *out,
 
 		/* Convert to REF_DELTA if we must... */
 		if (!allow_ofs_delta) {
-			int base_pos = find_revindex_position(reuse_packfile, base_offset);
+			uint32_t base_pos;
 			struct object_id base_oid;
 
+			if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
+				die(_("expected object at offset %"PRIuMAX" "
+				      "in pack %s"),
+				    (uintmax_t)base_offset,
+				    reuse_packfile->pack_name);
+
 			nth_packed_object_id(&base_oid, reuse_packfile,
-					     reuse_packfile->revindex[base_pos].nr);
+					     pack_pos_to_index(reuse_packfile, base_pos));
 
 			len = encode_in_pack_object_header(header, sizeof(header),
 							   OBJ_REF_DELTA, size);

2.30.0.138.g6d7191ea01

Replace a direct access to the revindex array with 'pack_pos_to_offset()'.

---
 builtin/pack-objects.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 8e40b19ee8..77ce5583a2 100644
@@ -952,7 +952,7 @@ static size_t write_reused_pack_verbatim(struct hashfile *out,
 		off_t to_write;
 
 		written = (pos * BITS_IN_EWORD);
-		to_write = reuse_packfile->revindex[written].offset
+		to_write = pack_pos_to_offset(reuse_packfile, written)
 			- sizeof(struct pack_header);
 
 		/* We're recording one chunk, not one object. */

2.30.0.138.g6d7191ea01

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.

---
 builtin/pack-objects.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 77ce5583a2..5b0c4489e2 100644
@@ -1817,11 +1817,11 @@ static void check_object(struct object_entry *entry, uint32_t object_index)
 				goto give_up;
 			}
 			if (reuse_delta && !entry->preferred_base) {
-				struct revindex_entry *revidx;
-				revidx = find_pack_revindex(p, ofs);
-				if (!revidx)
+				uint32_t pos;
+				if (offset_to_pack_pos(p, ofs, &pos) < 0)
 					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;
 			}
 			entry->in_pack_header_size = used + used_0;

2.30.0.138.g6d7191ea01

Replace find_revindex_position() with its counterpart in the new API, offset_to_pack_pos().

---
 pack-bitmap.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

index d88745fb02..d6861ddd4d 100644
@@ -407,11 +407,14 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
 					   const struct object_id *oid)
 {
+	uint32_t pos;
 	off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
 	if (!offset)
 		return -1;
 
-	return find_revindex_position(bitmap_git->pack, offset);
+	if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
+		return -1;
+	return pos;
 }
 
 static int bitmap_position(struct bitmap_index *bitmap_git,

2.30.0.138.g6d7191ea01

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.

---
 pack-bitmap.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

index d6861ddd4d..27a7a8ac4c 100644
@@ -711,21 +711,22 @@ static void show_objects_for_type(
 
 		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
 			struct object_id oid;
-			struct revindex_entry *entry;
-			uint32_t hash = 0;
+			uint32_t hash = 0, index_pos;
+			off_t ofs;
 
 			if ((word >> offset) == 0)
 				break;
 
 			offset += ewah_bit_ctz64(word >> offset);
 
-			entry = &bitmap_git->pack->revindex[pos + offset];
-			nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
+			index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset);
+			ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
+			nth_packed_object_id(&oid, bitmap_git->pack, index_pos);
 
 			if (bitmap_git->hashes)
-				hash = get_be32(bitmap_git->hashes + entry->nr);
+				hash = get_be32(bitmap_git->hashes + index_pos);
 
-			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);
+			show_reach(&oid, object_type, 0, hash, bitmap_git->pack, ofs);
 		}
 	}
 }

2.30.0.138.g6d7191ea01

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()'.

---
 pack-bitmap.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 27a7a8ac4c..89a528a91b 100644
@@ -835,11 +835,11 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
 	oi.sizep = &size;
 
 	if (pos < pack->num_objects) {
-		struct revindex_entry *entry = &pack->revindex[pos];
-		if (packed_object_info(the_repository, pack,
-				       entry->offset, &oi) < 0) {
+		off_t ofs = pack_pos_to_offset(pack, pos);
+		if (packed_object_info(the_repository, pack, ofs, &oi) < 0) {
 			struct object_id oid;
-			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 {

2.30.0.138.g6d7191ea01

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').

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).

---
 pack-bitmap.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

index 89a528a91b..1fdf7ce20a 100644
@@ -1069,23 +1069,21 @@ static void try_partial_reuse(struct bitmap_index *bitmap_git,
 			      struct bitmap *reuse,
 			      struct pack_window **w_curs)
 {
-	struct revindex_entry *revidx;
-	off_t offset;
+	off_t offset, header;
 	enum object_type type;
 	unsigned long size;
 
 	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_t base_offset;
-		int base_pos;
+		uint32_t base_pos;
 
 		/*
 		 * Find the position of the base object so we can look it up

@@ -1096,11 +1094,10 @@ static void try_partial_reuse(struct bitmap_index *bitmap_git,
 		 * more detail.
 		 */
 		base_offset = get_delta_base(bitmap_git->pack, w_curs,
-					     &offset, type, revidx->offset);
+					     &offset, type, header);
 		if (!base_offset)
 			return;
-		base_pos = find_revindex_position(bitmap_git->pack, base_offset);
-		if (base_pos < 0)
+		if (offset_to_pack_pos(bitmap_git->pack, base_offset, &base_pos) < 0)
 			return;
 
 		/*

2.30.0.138.g6d7191ea01

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.

---
 pack-bitmap.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

index 1fdf7ce20a..60fe20fb87 100644
@@ -1392,11 +1392,10 @@ uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
 
 	for (i = 0; i < num_objects; ++i) {
 		struct object_id oid;
-		struct revindex_entry *entry;
 		struct object_entry *oe;
 
-		entry = &bitmap_git->pack->revindex[i];
-		nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
+		nth_packed_object_id(&oid, bitmap_git->pack,
+				     pack_pos_to_index(bitmap_git->pack, i));
 		oe = packlist_find(mapping, &oid);
 
 		if (oe)

2.30.0.138.g6d7191ea01

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).

---
 packfile.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

index 86f5c8dbf6..3e3f391949 100644
@@ -1235,18 +1235,18 @@ static int get_delta_base_oid(struct packed_git *p,
 		oidread(oid, base);
 		return 0;
 	} else if (type == OBJ_OFS_DELTA) {
-		struct revindex_entry *revidx;
+		uint32_t base_pos;
 		off_t base_offset = get_delta_base(p, w_curs, &curpos,
 						   type, delta_obj_offset);
 
 		if (!base_offset)
 			return -1;
 
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
+		if (offset_to_pack_pos(p, base_offset, &base_pos) < 0)
 			return -1;
 
-		return nth_packed_object_id(oid, p, revidx->nr);
+		return nth_packed_object_id(oid, p,
+					    pack_pos_to_index(p, base_pos));
 	} else
 		return -1;
 }

2.30.0.138.g6d7191ea01

Perform exactly the same conversion as in the previous commit to another caller within 'packfile.c'.

---
 packfile.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

index 3e3f391949..7c37f9ec5c 100644
@@ -1256,12 +1256,11 @@ static int retry_bad_packed_offset(struct repository *r,
 				   off_t obj_offset)
 {
 	int type;
-	struct revindex_entry *revidx;
+	uint32_t pos;
 	struct object_id oid;
-	revidx = find_pack_revindex(p, obj_offset);
-	if (!revidx)
+	if (offset_to_pack_pos(p, obj_offset, &pos) < 0)
 		return OBJ_BAD;
-	nth_packed_object_id(&oid, p, revidx->nr);
+	nth_packed_object_id(&oid, p, pack_pos_to_index(p, pos));
 	mark_bad_packed_object(p, oid.hash);
 	type = oid_object_info(r, &oid, NULL);
 	if (type <= OBJ_NONE)

2.30.0.138.g6d7191ea01

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)'.

---
 packfile.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

index 7c37f9ec5c..bb4bb14671 100644
@@ -1537,8 +1537,15 @@ int packed_object_info(struct repository *r, struct packed_git *p,
 	}
 
 	if (oi->disk_sizep) {
-		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-		*oi->disk_sizep = revidx[1].offset - obj_offset;
+		uint32_t pos;
+		if (offset_to_pack_pos(p, obj_offset, &pos) < 0) {
+			error("could not find object at offset %"PRIuMAX" "
+			      "in pack %s", (uintmax_t)obj_offset, p->pack_name);
+			type = OBJ_BAD;
+			goto out;
+		}
+
+		*oi->disk_sizep = pack_pos_to_offset(p, pos + 1) - obj_offset;
 	}
 
 	if (oi->typep || oi->type_name) {

2.30.0.138.g6d7191ea01

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. In the case this check is violated, we cannot call 'mark_bad_packed_object()' because we don't know the OID. At the top of the call stack is do_oid_object_info_extended() (via packed_object_info()), which does mark the object.

---
 packfile.c | 26 ++++++++++++++++++--------
 1 file changed, 18 insertions(+), 8 deletions(-)

index bb4bb14671..936ab3def5 100644
@@ -1694,11 +1694,21 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 		}
 
 		if (do_check_packed_object_crc && p->index_version > 1) {
-			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-			off_t len = revidx[1].offset - obj_offset;
-			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
+			uint32_t pack_pos, index_pos;
+			off_t len;
+
+			if (offset_to_pack_pos(p, obj_offset, &pack_pos) < 0) {
+				error("could not find object at offset %"PRIuMAX" in pack %s",
+				      (uintmax_t)obj_offset, p->pack_name);
+				data = NULL;
+				goto out;
+			}
+
+			len = pack_pos_to_offset(p, pack_pos + 1) - obj_offset;
+			index_pos = pack_pos_to_index(p, pack_pos);
+			if (check_pack_crc(p, &w_curs, obj_offset, len, index_pos)) {
 				struct object_id oid;
-				nth_packed_object_id(&oid, p, revidx->nr);
+				nth_packed_object_id(&oid, p, index_pos);
 				error("bad packed object CRC for %s",
 				      oid_to_hex(&oid));
 				mark_bad_packed_object(p, oid.hash);

@@ -1781,11 +1791,11 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 			 * This is costly but should happen only in the presence
 			 * of a corrupted pack, and is better than failing outright.
 			 */
-			struct revindex_entry *revidx;
+			uint32_t pos;
 			struct object_id base_oid;
-			revidx = find_pack_revindex(p, obj_offset);
-			if (revidx) {
-				nth_packed_object_id(&base_oid, p, revidx->nr);
+			if (!(offset_to_pack_pos(p, obj_offset, &pos))) {
+				nth_packed_object_id(&base_oid, p,
+						     pack_pos_to_index(p, pos));
 				error("failed to read delta base object %s"
 				      " at offset %"PRIuMAX" from %s",
 				      oid_to_hex(&base_oid), (uintmax_t)obj_offset,

2.30.0.138.g6d7191ea01

Avoid looking at the 'revindex' pointer directly and instead call 'pack_pos_to_index()'.

---
 packfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 936ab3def5..7bb1750934 100644
@@ -2086,7 +2086,7 @@ int for_each_object_in_pack(struct packed_git *p,
 		struct object_id oid;
 
 		if (flags & FOR_EACH_OBJECT_PACK_ORDER)
-			pos = p->revindex[i].nr;
+			pos = pack_pos_to_index(p, i);
 		else
 			pos = i;
 

2.30.0.138.g6d7191ea01

I agree that it can be confusing. Unfortunately in this spot, this variable really does mean two things. If we set the FOR_EACH_OBJECT_PACK_ORDER bit in our flags, then the caller really wants the index position (and the objects to be delivered in pack order). But if we didn't set it, then the caller wants it in index order.

This suggested diff makes me think that you understand all of that, so I'm mostly saying this for the benefit of others that haven't looked at this code closely in the recent past.

I'd be happy to send a replacement patch if you would like [1], but I'm hopeful that this is clear enough since there isn't much code between the declaration, assignment(s), and use of 'pos'.

Thanks,
Taylor

[1]: I understand your general disdain for single replacement patches, but I'd like to avoid sending the other 19 patches if possible to avoid delivering more mail to list subscribers than is necessary.

I don't think "position" is a meaningful term by itself. I would say the useful terms are "pack position", "index position", and "offset" (or "pack offset" if you like). I don't think anything in the definitions added by earlier patches contradicts that, but perhaps we can make it more clear.

So "pos" in this case is not wrong. But I agree that it could stand to be more clear. Saying "nth" does not help things IMHO (there is an "nth" pack position, as well).

But maybe this makes it more clear (or possibly just the name change without the comment):

index de47c9f4f8..6035b80466 100644
@@ -2078,19 +2078,30 @@ int for_each_object_in_pack(struct packed_git *p,
 	}
 
 	for (i = 0; i < p->num_objects; i++) {
-		uint32_t pos;
+		uint32_t index_pos;
 		struct object_id oid;
 
+		/*
+		 * We are iterating "i" from 0 up to num_objects, but its
+		 * meaning may be different:
+		 *
+		 *   - in object-name order, it is the same as the index order
+		 *     given to us by nth_packed_object_id(), and we can use it
+		 *     directly
+		 *
+		 *   - in pack-order, it is pack position, which we must
+		 *     convert to an index position in order to get the oid.
+		 */
 		if (flags & FOR_EACH_OBJECT_PACK_ORDER)
-			pos = p->revindex[i].nr;
+			index_pos = p->revindex[i].nr;
 		else
-			pos = i;
+			index_pos = i;
 
-		if (nth_packed_object_id(&oid, p, pos) < 0)
+		if (nth_packed_object_id(&oid, p, index_pos) < 0)
 			return error("unable to get sha1 of object %u in %s",
-				     pos, p->pack_name);
+				     index_pos, p->pack_name);
 
-		r = cb(&oid, p, pos, data);
+		r = cb(&oid, p, index_pos, data);
 		if (r)
 			break;
 	}