Re: [PATCH v3 4/4] revision: avoid hitting packfiles when commits are in commit-graph

Patrick Steinhardt [off-list ref] writes:

Describe return-value here.  0 for not-found, !0 for found?

+static int find_object_id_in_graph(const struct object_id *id, struct commit_graph *g, uint32_t *pos)
+{
+	struct commit_graph *cur_g = g;
+	uint32_t lex_index;
+
+	while (cur_g && !bsearch_graph(cur_g, (struct object_id *)id, &lex_index))
+		cur_g = cur_g->base_graph;
+
+	if (cur_g) {
+		*pos = lex_index + cur_g->num_commits_in_base;
+		return 1;
+	}
+
+	return 0;
+}

Likewise, or as this is public, perhaps in commit-graph.h next to
its declaration.

+int find_object_in_graph(struct repository *repo, struct object *object)
+{
+	struct commit *commit;
+	uint32_t pos;
+
+	if (object->parsed) {
+		if (object->type != OBJ_COMMIT)
+			return -1;
+		return 0;

This is puzzling---at least it is not consistent with what the
function name says ("please say if you find _this_ object in the
commit-graph file"---if that is not what this function does, it
needs a comment before the implementation).

The caller had object and we has already been parsed.  If the
function were "with help from commit-graph, please tell me if you
can positively say this is a commit", the above is understandable.
If we know positively that it is not commit, we say "no, it is not a
commit" (which may be suboptimal---if the caller falls back to
another codepath, the object will still not be a commit) and if we
know it is a commit, we can say "yes, it definitely is a commit" and
the caller can stop there.

I guess my only problem with this function is that its name and what
it does does not align.  If the caller uses it for the real purpose
of the function I guessed, then the logic itself may be OK.

+	}
+
+	if (!repo->objects->commit_graph)
+		return -1;

There is no commit-graph, then we decline to make a decision, which
makes sense.

+	if (!find_object_id_in_graph(&object->oid, repo->objects->commit_graph, &pos))
+		return -1;

If it does not exist in the graph, we cannot tell, either.

And I think this one is a op-op refactoring that does not change the
behaviour of find_commit_in_graph()?  It might be easier if done in
a separate preparatory step, but it is small enough.

On Mon, Aug 02, 2021 at 01:01:03PM -0700, Junio C Hamano wrote:

Patrick Steinhardt [off-list ref] writes:

[snip]

quoted

+int find_object_in_graph(struct repository *repo, struct object *object)
+{
+	struct commit *commit;
+	uint32_t pos;
+
+	if (object->parsed) {
+		if (object->type != OBJ_COMMIT)
+			return -1;
+		return 0;

This is puzzling---at least it is not consistent with what the
function name says ("please say if you find _this_ object in the
commit-graph file"---if that is not what this function does, it
needs a comment before the implementation).

The caller had object and we has already been parsed.  If the
function were "with help from commit-graph, please tell me if you
can positively say this is a commit", the above is understandable.
If we know positively that it is not commit, we say "no, it is not a
commit" (which may be suboptimal---if the caller falls back to
another codepath, the object will still not be a commit) and if we
know it is a commit, we can say "yes, it definitely is a commit" and
the caller can stop there.

I guess my only problem with this function is that its name and what
it does does not align.  If the caller uses it for the real purpose
of the function I guessed, then the logic itself may be OK.

Fair point. The only caller for now only calls the function if the
object's type is unknown, so it really is "Resolve the commit if it is
one". I'll adjust the function's name.

quoted

 static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
 {
 	uint32_t graph_pos = commit_graph_position(item);

@@ -871,18 +913,7 @@ static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uin
 		*pos = graph_pos;
 		return 1;
 	} else {
-		struct commit_graph *cur_g = g;
-		uint32_t lex_index;
-
-		while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index))
-			cur_g = cur_g->base_graph;
-
-		if (cur_g) {
-			*pos = lex_index + cur_g->num_commits_in_base;
-			return 1;
-		}
-
-		return 0;
+		return find_object_id_in_graph(&item->object.oid, g, pos);

And I think this one is a op-op refactoring that does not change the
behaviour of find_commit_in_graph()?  It might be easier if done in
a separate preparatory step, but it is small enough.

Will do.

One thing that occurred to me this morning after waking up is that this
commit changes semantics: if we're able to look up the commit via the
commit-graph, then we'll happily consider it to exist in the repository.
But given that we don't hit the object database at all anymore, it may
be that the commit-graph was out of date while the commit got
unreachable and thus pruned. So it may not even exist anymore in the
repository.

I wonder what our stance on this is. I can definitely understand the
angle that this would be a deal breaker given that we now claim commits
exist which don't anymore. On the other hand, we update commit-graphs
via git-gc(1), which makes this scenario a lot less likely nowadays. Is
there any precedent in our codebase where we treat commits part of the
commit-graph as existing? If not, do we want to make that assumption?

Patrick

On Tue, Aug 03 2021, Patrick Steinhardt wrote:

I wonder what our stance on this is. I can definitely understand the
angle that this would be a deal breaker given that we now claim commits
exist which don't anymore. On the other hand, we update commit-graphs
via git-gc(1), which makes this scenario a lot less likely nowadays. Is
there any precedent in our codebase where we treat commits part of the
commit-graph as existing? If not, do we want to make that assumption?

I don't think there is, but don't see why given the performance benefits
it should not at least be exposed in this form for those that think they
know what they're doing.

But right now the way we write the commit graph seems guaranteed to
produce races in this area, i.e. we expire objects first, and then we
write a new graph (see cmd_gc()). I.e. something like:

 1. (Re)pack reachable objects
 2. Prune unrechable and old
 3. Write a new commit graph using discovered tips

I don't see a good reason other than just that this needs some
refactoring to not instead do:

 1. Discover reachable refs
 2. (Re)pack reachable objects from those refs
 3. Write a new commit graph using those ref tips, i.e. don't re-run
    for_each_ref() in write_commit_graph_reachable() but call
    write_commit_graph() with those OIDs directly.
 4. Prune unreachable and old

Which I think would nicely get around this particular race condition,
which also doesn't exist if you call "git commit-graph write", it's just
if we write a new graph and then expire objects without being aware that
the graph needs updating.