commit-graph.c: handle corrupt commit trees

When we write a commit graph chunk, we process a given list of 'struct commit *'s and parse out the parent(s) and tree OID in order to write out its information.

We do this by calling 'parse_commit_no_graph', and then checking the result of 'get_commit_tree_oid' to write the tree OID. This process assumes that 'parse_commit_no_graph' parses the commit successfully. When this isn't the case, 'get_commit_tree_oid(*list)' may return NULL, in which case trying to '->hash' it causes a SIGSEGV.

Instead, teach 'write_graph_chunk_data' to stop when a commit isn't able to be parsed, at the peril of failing to write a commit-graph.

Quoted 4 lines · Taylor Blau

When we write a commit graph chunk, we process a given list of 'struct commit *'s and parse out the parent(s) and tree OID in order to write out its information.

Quoted 8 lines

We do this by calling 'parse_commit_no_graph', and then checking the result of 'get_commit_tree_oid' to write the tree OID. This process assumes that 'parse_commit_no_graph' parses the commit successfully. When this isn't the case, 'get_commit_tree_oid(*list)' may return NULL, in which case trying to '->hash' it causes a SIGSEGV.

Instead, teach 'write_graph_chunk_data' to stop when a commit isn't able to be parsed, at the peril of failing to write a commit-graph.

Yeah, I think it makes sense for commit-graph to bail completely if it can't parse here. In theory it could omit the entry from the commit-graph file (and a reader would just fall back to trying to access the object contents itself), but I think we're too late in the process for that. And besides, this should generally only happen in a corrupt repository.

However...

commit-graph.c static void write_graph_chunk_data(struct hashfile *f, int hash_len, · line 849

Quoted 13 lines

commit-graph.c +3 -1

index f2888c203b..6aa6998ecd 100644
@@ -843,7 +843,9 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 		uint32_t packedDate[2];
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
-		parse_commit_no_graph(*list);
+		if (parse_commit_no_graph(*list))
+			die(_("unable to parse commit %s"),
+				oid_to_hex(&(*list)->object.oid));
 		hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);

I don't think parse_commit_no_graph() returning 0 assures us that get_commit_tree() and friends will return non-NULL.

This is similar to the case discussed recently where a failed parse of a tag may leave "tag->tagged == NULL" even though "tag->obj.parsed" is set.

Here an earlier parsing error could cause (*list)->object.parsed to be true, but with (*list)->maybe_tree still NULL. Our call to parse_commit_no_graph() here would silently return "yep, already tried to parse this", and then we'd still segfault.

We _could_ check:

if (parse_commit_no_graph(*list))

	die("unable to parse...");
  tree = get_commit_tree_oid(*list);
  if (!tree)
	die("unable to get tree for %s...");

but trees are just one piece of data. In fact, the situation is much worse for parents: there a NULL parent pointer is valid data, so worse than segfaulting, we'd write invalid data to the commit graph, skipping one or more parents!

And I think there's literally no way for this function to tell the difference between "no parent" and "there was an earlier error, but we set the parsed flag anyway and the parent flag is invalid".

I think that argues against Junio's response in:

https://public-inbox.org/git/[email protected]/

about how we can use the parsed flag to look at "slightly corrupt" objects. I think we'd need at least an extra flag for "corrupt", though I think it is simpler just _not_ setting "parsed" and letting the next caller spend the extra cycles to rediscover the problem if they're interested.

(All of this presupposes that you can convince another piece of code in the same process to parse the commit buffer and ignore the error. I have no idea if that's possible or not in this case, but it sure would be nice not to have to care).

-Peff

All of this makes sense to me, so I'm wondering what part(s) of this you feel are worth addressing in this first patch series. Presumably, there is a longer series that we _could_ write which would introduce a new 'corrupt' field and then check for it here.

But, I'm hesitant to write those patches, since I only have this one call-site in mind. If we introduce 'corrupt', I feel it would be best to use it uniformly, instead of only checking it here, and relying on other bespoke mechanisms to detect corruption elsewhere.

So, I'm content to write the pseudo-code you provided above (which is to say, call and check both 'parse_commit_no_graph', _and_ 'get_commit_tree_oid'), because I think that it's expedient, and fix the issue which I'm pointing out here.

Quoted 10 lines · Taylor Blau

All of this makes sense to me, so I'm wondering what part(s) of this you feel are worth addressing in this first patch series. Presumably, there is a longer series that we _could_ write which would introduce a new 'corrupt' field and then check for it here.

But, I'm hesitant to write those patches, since I only have this one call-site in mind. If we introduce 'corrupt', I feel it would be best to use it uniformly, instead of only checking it here, and relying on other bespoke mechanisms to detect corruption elsewhere.

Quoted 4 lines

So, I'm content to write the pseudo-code you provided above (which is to say, call and check both 'parse_commit_no_graph', _and_ 'get_commit_tree_oid'), because I think that it's expedient, and fix the issue which I'm pointing out here.

I'd actually be willing to just take the patch you have here, and consider the "parsed but we saw an error" thing as an oddity of the object code. IOW, we shouldn't _have_ to be double-checking here. Looking for an error return from parse_commit() should really be all a caller needs to do. Once that's fixed, then your code would just be doing the right thing.

That said, there's another unhandled case, I think: lookup_tree() might return NULL (if somebody previously saw that oid as a non-tree), and parse_commit() wouldn't even notice and return an error!

IMHO that's also something that parse_commit() should be returning an error for. And it's probably a lot easier to trigger versus the "parsed earlier but corrupted" thing.

So it might be worth doing the NULL tree check here in the meantime. I dunno.

Below is a sketch of what I'm thinking parse_commit() should do:

- remember when an earlier parse returned an error, so we can repeat that error (this requires some unfortunate bit-field adjusting)

- notice a lookup_tree failure

- likewise, notice a lookup_parent failure

---

commit.c +30 -6

index a98de16e3d..7e415932b7 100644
@@ -391,7 +391,9 @@ const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep)
 	return ret;
 }
 
-int parse_commit_buffer(struct repository *r, struct commit *item, const void *buffer, unsigned long size, int check_graph)
+static int parse_commit_buffer_1(struct repository *r, struct commit *item,
+				 const void *buffer, unsigned long size,
+				 int check_graph)
 {
 	const char *tail = buffer;
 	const char *bufptr = buffer;

@@ -401,9 +403,6 @@ int parse_commit_buffer(struct repository *r, struct commit *item, const void *b
 	const int tree_entry_len = the_hash_algo->hexsz + 5;
 	const int parent_entry_len = the_hash_algo->hexsz + 7;
 
-	if (item->object.parsed)
-		return 0;
-	item->object.parsed = 1;
 	tail += size;
 	if (tail <= bufptr + tree_entry_len + 1 || memcmp(bufptr, "tree ", 5) ||
 			bufptr[tree_entry_len] != '\n')

@@ -412,6 +411,10 @@ int parse_commit_buffer(struct repository *r, struct commit *item, const void *b
 		return error("bad tree pointer in commit %s",
 			     oid_to_hex(&item->object.oid));
 	set_commit_tree(item, lookup_tree(r, &parent));
+	if (!item->maybe_tree)
+		return error("bad tree pointer %s in commit %s",
+			     oid_to_hex(&parent),
+			     oid_to_hex(&item->object.oid));
 	bufptr += tree_entry_len + 1; /* "tree " + "hex sha1" + "\n" */
 	pptr = &item->parents;
 

@@ -431,15 +434,19 @@ int parse_commit_buffer(struct repository *r, struct commit *item, const void *b
 		if (graft && (graft->nr_parent < 0 || grafts_replace_parents))
 			continue;
 		new_parent = lookup_commit(r, &parent);
-		if (new_parent)
-			pptr = &commit_list_insert(new_parent, pptr)->next;
+		if (!new_parent)
+			return error("bad parent %s in commit %s",
+				     oid_to_hex(&parent),
+				     oid_to_hex(&item->object.oid));
+		pptr = &commit_list_insert(new_parent, pptr)->next;
 	}
 	if (graft) {
 		int i;
 		struct commit *new_parent;
 		for (i = 0; i < graft->nr_parent; i++) {
 			new_parent = lookup_commit(r,
 						   &graft->parent[i]);
+			/* Here we ignore bogus grafts. Also should be an error? */
 			if (!new_parent)
 				continue;
 			pptr = &commit_list_insert(new_parent, pptr)->next;

@@ -453,6 +460,23 @@ int parse_commit_buffer(struct repository *r, struct commit *item, const void *b
 	return 0;
 }
 
+int parse_commit_buffer(struct repository *r, struct commit *item,
+			const void *buffer, unsigned long size,
+			int check_graph)
+{
+	int ret;
+
+	if (item->object.parsed)
+		return item->object.corrupt ? -1 : 0;
+	item->object.parsed = 1;
+
+	ret = parse_commit_buffer_1(r, item, buffer, size, check_graph);
+	if (ret < 0)
+		item->object.corrupt = 1;
+
+	return ret;
+}
+
 int repo_parse_commit_internal(struct repository *r,
 			       struct commit *item,
 			       int quiet_on_missing,

object.h +3 -2

index 0120892bbd..b83d3964ad 100644
@@ -59,7 +59,7 @@ struct object_array {
 
 /*
  * object flag allocation:
- * revision.h:               0---------10                              25----28
+ * revision.h:               0---------10                              24----27
  * fetch-pack.c:             01
  * negotiator/default.c:       2--5
  * walker.c:                 0-2

@@ -78,13 +78,14 @@ struct object_array {
  * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
-#define FLAG_BITS  29
+#define FLAG_BITS  28
 
 /*
  * The object type is stored in 3 bits.
  */
 struct object {
 	unsigned parsed : 1;
+	unsigned corrupt : 1;
 	unsigned type : TYPE_BITS;
 	unsigned flags : FLAG_BITS;
 	struct object_id oid;

revision.h +0 -0

index 4134dc6029..5c0b831b37 100644

Quoted 7 lines

revision.h +0 -0

index 4134dc6029..5c0b831b37 100644
@@ -33,7 +33,7 @@
 #define ALL_REV_FLAGS	(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR)
 

revision.h line 36

Quoted 3 lines

revision.h +1 -1

 #define TOPO_WALK_EXPLORED	(1u<<27)
-#define TOPO_WALK_INDEGREE	(1u<<28)
+#define TOPO_WALK_INDEGREE	(1u<<24)

As an aside, these flag bit modifications look fine, but would need to be explained. I'm guessing that since you are adding a bit of data to struct object you want to avoid increasing the struct size across a 32-bit boundary. Are we sure that bit 24 is not used anywhere else? (My search for "1u<<24" found nothing, and "1 << 24" found a bit in the cache-entry flags, so this seems safe.)

Quoted 7 lines · Derrick Stolee

Quoted 7 lines

revision.h +0 -0

index 4134dc6029..5c0b831b37 100644
@@ -33,7 +33,7 @@
 #define ALL_REV_FLAGS	(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR)
 

Quoted 10 lines

revision.h line 36

Quoted 3 lines

revision.h +1 -1

 #define TOPO_WALK_EXPLORED	(1u<<27)
-#define TOPO_WALK_INDEGREE	(1u<<28)
+#define TOPO_WALK_INDEGREE	(1u<<24)

As an aside, these flag bit modifications look fine, but would need to be explained. I'm guessing that since you are adding a bit of data to struct object you want to avoid increasing the struct size across a 32-bit boundary. Are we sure that bit 24 is not used anywhere else? (My search for "1u<<24" found nothing, and "1 << 24" found a bit in the cache-entry flags, so this seems safe.)

Yeah, I'd definitely break this up into several commits with explanation (though see an alternate I posted that just uses the parsed flag without any new bits).

Bit 24 isn't used according to the table in objects.h, which is _supposed_ to be the source of truth, though of course there's no compiler-level checking. (One aside: is there a reason TOPO_WALK_* isn't part of ALL_REV_FLAGS?).

Quoted 7 lines · Derrick Stolee

Quoted 7 lines

revision.h +0 -0

index 4134dc6029..5c0b831b37 100644
@@ -33,7 +33,7 @@
 #define ALL_REV_FLAGS	(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR)
 

Quoted 10 lines

revision.h line 36

Quoted 3 lines

revision.h +1 -1

 #define TOPO_WALK_EXPLORED	(1u<<27)
-#define TOPO_WALK_INDEGREE	(1u<<28)
+#define TOPO_WALK_INDEGREE	(1u<<24)

As an aside, these flag bit modifications look fine, but would need to be explained. I'm guessing that since you are adding a bit of data to struct object you want to avoid increasing the struct size across a 32-bit boundary. Are we sure that bit 24 is not used anywhere else? (My search for "1u<<24" found nothing, and "1 << 24" found a bit in the cache-entry flags, so this seems safe.)

Yeah, I'd definitely break this up into several commits with explanation (though see an alternate I posted that just uses the parsed flag without any new bits).

Bit 24 isn't used according to the table in objects.h, which is _supposed_ to be the source of truth, though of course there's no compiler-level checking. (One aside: is there a reason TOPO_WALK_* isn't part of ALL_REV_FLAGS?).

And yes, the goal was to keep things to the 32-bit boundary. But in the course of this, I discovered something interesting: 64-bit systems are now padding this up to the 8-byte boundary!

The culprit is the switch of GIT_MAX_RAWSZ for sha256. Before then, our object_id was 20 bytes for sha1. Adding 4 bytes of flags still left us at 24 bytes, which is both 4- and 8-byte aligned.

With the switch to sha256, object_id is now 32 bytes. Adding 4 bytes takes us to 36, and then 8-byte aligning the struct takes us to 40 bytes, with 4 bytes of wasted padding.

I'm sorely tempted to use this as an opportunity to move commit->index into "struct object". That would actually shrink commit object sizes by 4 bytes, and would let all object types do the commit-slab trick to store object data with constant-time lookup. This would make it possible to migrate some uses of flags to per-operation bitfields (so e.g., two traversals would have their _own_ flag data, and wouldn't risk stomping on each other's bits).

I don't think parse_commit_no_graph() returning 0 assures us that get_commit_tree() and friends will return non-NULL.

This is similar to the case discussed recently where a failed parse of a tag may leave "tag->tagged == NULL" even though "tag->obj.parsed" is set.

Here an earlier parsing error could cause (*list)->object.parsed to be true, but with (*list)->maybe_tree still NULL. Our call to parse_commit_no_graph() here would silently return "yep, already tried to parse this", and then we'd still segfault.
...
And I think there's literally no way for this function to tell the difference between "no parent" and "there was an earlier error, but we set the parsed flag anyway and the parent flag is invalid".

I think that argues against Junio's response in:

Quoted 9 lines

Here an earlier parsing error could cause (*list)->object.parsed to be true, but with (*list)->maybe_tree still NULL. Our call to parse_commit_no_graph() here would silently return "yep, already tried to parse this", and then we'd still segfault.
...
And I think there's literally no way for this function to tell the difference between "no parent" and "there was an earlier error, but we set the parsed flag anyway and the parent flag is invalid".

Quoted 1 line

I think that argues against Junio's response in:

Fair enough. Forcing later users to reattempt parsing (and failing the same way) would be safer and it should also be sufficient as we are talking about how to handle a broken repository, i.e. an error case.

Quoted 4 lines

Fair enough. Forcing later users to reattempt parsing (and failing the same way) would be safer and it should also be sufficient as we are talking about how to handle a broken repository, i.e. an error case.

One of the tricky things, and the reason I used a "corrupt" flag in my earlier sketch, is that the state after we encounter a parse error is unknown. So imagine parse_commit_buffer() sees that one of the parent lines is bogus, and we return an error. The caller gets to see whatever half-parsed state we managed to come up with.

So far so good. But now imagine we call parse_commit_buffer() again, and we re-parse. How does that interact with the half-parsed state? Some of it works OK (e.g., lookup_tree() would find the same tree). Some not so much (I think we'd keep appending parents at each call).

I guess this might not be too bad to handle. Value fields like timestamp_t are OK to overwrite. Pointers to objects likewise, since the memory is owned elsewhere. If we see existing parent pointers in an object we're parsing, we could probably free them under the assumption they're leftover cruft. Likewise for the "tag" field of "struct tag", which is owned by the struct and should be freed.

Blobs and trees don't actually parse anything into their structs. So it's really just special-casing those two items.

So far so good. But now imagine we call parse_commit_buffer() again, and we re-parse. How does that interact with the half-parsed state? Some of it works OK (e.g., lookup_tree() would find the same tree). Some not so much (I think we'd keep appending parents at each call).

I guess this might not be too bad to handle. Value fields like timestamp_t are OK to overwrite. Pointers to objects likewise, since the memory is owned elsewhere. If we see existing parent pointers in an object we're parsing, we could probably free them under the assumption they're leftover cruft. Likewise for the "tag" field of "struct tag", which is owned by the struct and should be freed.

Quoted 5 lines · Jeff King

So far so good. But now imagine we call parse_commit_buffer() again, and we re-parse. How does that interact with the half-parsed state? Some of it works OK (e.g., lookup_tree() would find the same tree). Some not so much (I think we'd keep appending parents at each call).

Quoted 6 lines

I guess this might not be too bad to handle. Value fields like timestamp_t are OK to overwrite. Pointers to objects likewise, since the memory is owned elsewhere. If we see existing parent pointers in an object we're parsing, we could probably free them under the assumption they're leftover cruft. Likewise for the "tag" field of "struct tag", which is owned by the struct and should be freed.

Yeah, or clear them before returning with .corrupt bit set?

Quoted 14 lines · Junio C Hamano

Quoted 11 lines · Jeff King

So far so good. But now imagine we call parse_commit_buffer() again, and we re-parse. How does that interact with the half-parsed state? Some of it works OK (e.g., lookup_tree() would find the same tree). Some not so much (I think we'd keep appending parents at each call).

I guess this might not be too bad to handle. Value fields like timestamp_t are OK to overwrite. Pointers to objects likewise, since the memory is owned elsewhere. If we see existing parent pointers in an object we're parsing, we could probably free them under the assumption they're leftover cruft. Likewise for the "tag" field of "struct tag", which is owned by the struct and should be freed.

Quoted 1 line

Yeah, or clear them before returning with .corrupt bit set?

This was my attempt to avoid dealing with a .corrupt bit. :)

Quoted 16 lines · Jeff King

Quoted 14 lines · Junio C Hamano

Quoted 11 lines · Jeff King

So far so good. But now imagine we call parse_commit_buffer() again, and we re-parse. How does that interact with the half-parsed state? Some of it works OK (e.g., lookup_tree() would find the same tree). Some not so much (I think we'd keep appending parents at each call).

I guess this might not be too bad to handle. Value fields like timestamp_t are OK to overwrite. Pointers to objects likewise, since the memory is owned elsewhere. If we see existing parent pointers in an object we're parsing, we could probably free them under the assumption they're leftover cruft. Likewise for the "tag" field of "struct tag", which is owned by the struct and should be freed.

Quoted 3 lines

Quoted 1 line

Yeah, or clear them before returning with .corrupt bit set?

This was my attempt to avoid dealing with a .corrupt bit. :)

Then, clear them before returning with .parsed bit clear?

Hi,

I was running some of the new 'git commit-graph' commands, and noticed that I could consistently get 'git commit-graph write --reachable' to segfault when a commit's root tree is corrupt.

I have an extremely-unfinished fix attached as an RFC PATCH below, but I wanted to get a few thoughts on this before sending it out as a non-RFC.

In my patch, I simply 'die()' when a commit isn't able to be parsed (i.e., when 'parse_commit_no_graph' returns a non-zero code), but I wanted to see if others thought that this was an OK approach. Some thoughts:

* It seems like we could write a commit-graph by placing a "filler" entry where the broken commit would have gone. I don't see any place where this is implemented currently, but this seems like a viable alternative to not writing _any_ commits into the commit-graph.

Quoted 6 lines · Taylor Blau

Hi,

I was running some of the new 'git commit-graph' commands, and noticed that I could consistently get 'git commit-graph write --reachable' to segfault when a commit's root tree is corrupt.

Quoted 7 lines

I have an extremely-unfinished fix attached as an RFC PATCH below, but I wanted to get a few thoughts on this before sending it out as a non-RFC.

In my patch, I simply 'die()' when a commit isn't able to be parsed (i.e., when 'parse_commit_no_graph' returns a non-zero code), but I wanted to see if others thought that this was an OK approach. Some thoughts:

I like the idea of completely bailing if the commit can't be parsed too. Only question: Is there a reason you chose to die() instead of BUG() like the other two places in that function? What is the criteria of choosing one over the other?

Quoted 5 lines

* It seems like we could write a commit-graph by placing a "filler" entry where the broken commit would have gone. I don't see any place where this is implemented currently, but this seems like a viable alternative to not writing _any_ commits into the commit-graph.

I would rather we didn't do this cause it will probably kick open the can of always watching for that filler when we are working with the commit-graph. Or do we already do that today? Maybe @stolee can chime in on what we do in cases of shallow clones and other potential gaps in the walk

-Garima

Quoted 4 lines

I like the idea of completely bailing if the commit can't be parsed too. Only question: Is there a reason you chose to die() instead of BUG() like the other two places in that function? What is the criteria of choosing one over the other?

I did not call 'BUG' here because 'BUG' is traditionally used to indicate an internal bug, e.g., an unexpected state or some such. On the other side of that coin, 'BUG' is _not_ used to indicate repository corruption, since that is not an issue in the Git codebase, rather in the user's repository.

Though, to be honest, I've never seen that rule written out explicitly (maybe if it were to be written somewhere, it could be stored in Documentation/CodingGuidelines?). I think that this is some good #leftoverbits material.

Hi Garima,

Quoted 16 lines · Garima Singh

Quoted 6 lines · Taylor Blau

Hi,

I was running some of the new 'git commit-graph' commands, and noticed that I could consistently get 'git commit-graph write --reachable' to segfault when a commit's root tree is corrupt.

Quoted 7 lines

I have an extremely-unfinished fix attached as an RFC PATCH below, but I wanted to get a few thoughts on this before sending it out as a non-RFC.

In my patch, I simply 'die()' when a commit isn't able to be parsed (i.e., when 'parse_commit_no_graph' returns a non-zero code), but I wanted to see if others thought that this was an OK approach. Some thoughts:

Quoted 4 lines

I like the idea of completely bailing if the commit can't be parsed too. Only question: Is there a reason you chose to die() instead of BUG() like the other two places in that function? What is the criteria of choosing one over the other?

I did not call 'BUG' here because 'BUG' is traditionally used to indicate an internal bug, e.g., an unexpected state or some such. On the other side of that coin, 'BUG' is _not_ used to indicate repository corruption, since that is not an issue in the Git codebase, rather in the user's repository.

Though, to be honest, I've never seen that rule written out explicitly (maybe if it were to be written somewhere, it could be stored in Documentation/CodingGuidelines?). I think that this is some good #leftoverbits material.

Quoted 6 lines

Quoted 5 lines

* It seems like we could write a commit-graph by placing a "filler" entry where the broken commit would have gone. I don't see any place where this is implemented currently, but this seems like a viable alternative to not writing _any_ commits into the commit-graph.

Quoted 4 lines

I would rather we didn't do this cause it will probably kick open the can of always watching for that filler when we are working with the commit-graph. Or do we already do that today? Maybe @stolee can chime in on what we do in cases of shallow clones and other potential gaps in the walk

Yeah, I think that the consensus is that it makes sense to just die here, which is fine by me.