Re: invalid tree and commit object

From: René Scharfe <l.s.r@web.de>
Date: May 10, 2020, 09:07 UTC
Message-ID: <aab9512b-a70a-0f5b-5cdc-5d40acd343d0@web.de>
In-Reply-To: <xmqqh7wovoop.fsf@gitster.c.googlers.com>

Am 09.05.20 um 22:27 schrieb Junio C Hamano:

Show 19 quoted lines

> René Scharfe <l.s.r@web.de> writes:
>
>> Hmm, this could lead to quadratic behavior in the worst case, can't it?
>
> Oh, absolutely.  But as you have shown, you'd need a specially
> crafted tree with early entries that are prefixes of later ones,
> which would rather be rare, and most of the time the bottom pointer
> would advance by one every time we consume one path.
>
> So it is trading (hopefully rare) worst-case runtime with reduced
> storage cost.
>
>> We could, however, reduce the names we add to the string_list to
>> those that are possible candidates for conflict -- blobs followed by an
>> entry whose name starts with the blob name followed by a dot and trees
>> that follow an entry whose name matches in the same way.
>
> Yes, that is a valid solution that strikes a different balance
> between allocation and runtime.

fsck should ideally handle the worst cases gracefully -- I assume it has to deal with the weirdest "natural" corruptions and the "best" that pranksters and DoSers can come up with.

> We may want to survey how commonly "bad" trees appear in real
> projects.  Depending on the result, we might want to update the
> "limit re-scanning using the bottom pointer" hack we have been using
> in the unpack-trees code.

They are surprisingly common in Git's own repo. Ca. 74% of the trees in my clone had at least one candidate and the average number of candidates per tree in those was ca. 8.9. We have e.g. the t/ tree with its several tnnnn/ vs. tnnnn-foo.sh entries, or builtin/ vs. builtin.h.

In the Linux repo ca. 20% of the checked trees have at least a candidate and the average number of candidates in those is ca. 2.4.

So the patch for only adding possible candidates to the string_list is below (on top of my earlier one), but I wonder if we can do better.

When we look for a d/f name clash we don't necessarily have to look back upon finding a candidate directory -- we can also scan ahead upon finding a candidate non-directory. That could be done using repeated update_tree_entry_gently() calls on a private copy. It wouldn't require any string_list allocations, but its worst case complexity would still be quadratic, of course.

Would a stack work? When we see a candidate non-directory, we put it on the stack. When we see a candidate directory, we compare it to the entry at the top of the stack using strcmp(). Equality indicates a duplicate and we are done. If the directory name is less then we can pop the entry from the stack and check again, as we're past the point where a duplicate would be. Makes sense?

The candidate stack solution would have linear complexity and require less memory than a full list of candidates.

It would rely on the entries to be in the correct order (same as the patch below, come to think of it), but that's probably OK. We may miss DUPLICATE_ENTRIES (just like today :), but TREE_NOT_SORTED would still be reported.

---
 fsck.c | 25 +++++++++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)

diff --git a/fsck.c b/fsck.c
index f47b35fee8..7d5bfef804 100644
--- a/fsck.c
+++ b/fsck.c
@@ -569,6 +569,25 @@ static int verify_ordered(unsigned mode1, const char *name1, unsigned mode2, con
 	return c1 < c2 ? 0 : TREE_UNORDERED;
 }

+/*
+ * Consecutive entries are checked for duplicates in verify_ordered().
+ * However, there can be non-consecutive duplicates because a slash
+ * ('/') is appended implicitly to directory names during sorting, so
+ * there can be other names between a non-directory entry and a
+ * directory entry with the same name.  E.g.:
+ *
+ *    foo
+ *    foo.bar
+ *    foo/
+ *
+ */
+static int may_be_df_dup(const char *candidate, const char *interloper)
+{
+	const char *p;
+
+	return skip_prefix(interloper, candidate, &p) && '\0' < *p && *p < '/';
+}
+
 static int fsck_tree(const struct object_id *oid,
 		     const char *buffer, unsigned long size,
 		     struct fsck_options *options)
@@ -678,11 +697,14 @@ static int fsck_tree(const struct object_id *oid,
 			default:
 				break;
 			}
+			if (!S_ISDIR(o_mode) && may_be_df_dup(o_name, name))
+				string_list_append(&names, o_name);
+			if (S_ISDIR(mode) && may_be_df_dup(name, o_name))
+				string_list_append(&names, name);
 		}

 		o_mode = mode;
 		o_name = name;
-		string_list_append(&names, name);
 	}

 	nr = names.nr;
@@ -1221,7 +1243,6 @@ int fsck_finish(struct fsck_options *options)
 		free(buf);
 	}

-
 	oidset_clear(&gitmodules_found);
 	oidset_clear(&gitmodules_done);
 	return ret;
--
2.26.2