Re: invalid tree and commit object
René Scharfe <l.s.r@web.de> writes:
Show 33 quoted lines
> fsck.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++--
> t/t1450-fsck.sh | 16 +++++++++++
> 2 files changed, 86 insertions(+), 2 deletions(-)
>
> diff --git a/fsck.c b/fsck.c
> index 087a7f1ffc..8bb3ecf282 100644
> --- a/fsck.c
> +++ b/fsck.c
> @@ -523,6 +523,28 @@ int fsck_walk(struct object *obj, void *data, struct fsck_options *options)
> }
> }
>
> +struct name_stack {
> + const char **names;
> + size_t nr, alloc;
> +};
> +
> +static void name_stack_push(struct name_stack *stack, const char *name)
> +{
> + ALLOC_GROW(stack->names, stack->nr + 1, stack->alloc);
> + stack->names[stack->nr++] = name;
> +}
> +
> +static const char *name_stack_pop(struct name_stack *stack)
> +{
> + return stack->nr ? stack->names[--stack->nr] : NULL;
> +}
> +
> +static void name_stack_clear(struct name_stack *stack)
> +{
> + FREE_AND_NULL(stack->names);
> + stack->nr = stack->alloc = 0;
> +}OK, names are just pointing into tree objects' buffer, and will be there until we no longer need the stack and call stack_clear(). Good.
Show 9 quoted lines
> @@ -534,7 +556,14 @@ int fsck_walk(struct object *obj, void *data, struct fsck_options *options)
> #define TREE_UNORDERED (-1)
> #define TREE_HAS_DUPS (-2)
>
> -static int verify_ordered(unsigned mode1, const char *name1, unsigned mode2, const char *name2)
> +static int is_less_than_slash(unsigned char c)
> +{
> + return '\0' < c && c < '/';
> +}Mental note: the terminating byte does not count as "less than".
> +static int verify_ordered(unsigned mode1, const char *name1,
> + unsigned mode2, const char *name2,
> + struct name_stack *candidates)
Mental note: the caller is iterating over tree entries, and calls this helper with two adjacent entries (mode2/name2 is what it just saw). The function wants to see if name1 has duplicate in the tree object, and before this fix, we thought that it is sufficient to compare it with name2, but now we realized that an entry with the same name as name1 can come much later than name2. But it is still the same in spirit---we want to make sure name1 does not have any duplicate (name2 will get its turn by the next call to this function the caller makes).
Show 7 quoted lines
> {
> int len1 = strlen(name1);
> int len2 = strlen(name2);
> @@ -566,6 +595,41 @@ static int verify_ordered(unsigned mode1, const char *name1, unsigned mode2, con
> c1 = '/';
> if (!c2 && S_ISDIR(mode2))
> c2 = '/';Mental note: at this point, we have rejected two adjacent and identical names, and c1 and c2 are the first byte that are different between these two names; but if it is NUL at the end of the name, and the object is a tree, c1/c2 is changed to a slash.
> +
> + /*
> + * There can be non-consecutive duplicates due to the implicitly
> + * add slash, e.g.:
s/add slash/added slash/, or even "added slash at the end of the name of a tree object".
Show 13 quoted lines
> + *
> + * foo
> + * foo.bar
> + * foo.bar.baz
> + * foo.bar/
> + * foo/
> + *
> + * Record non-directory candidates (like "foo" and "foo.bar" in
> + * the example) on a stack and check directory candidates (like
> + * foo/" and "foo.bar/") against that stack.
> + */
> + if (!c1 && is_less_than_slash(c2)) {
> + name_stack_push(candidates, name1);If name1 is a blob and the name2 sorts before a hypothetical entry that is a tree object with the same name as name1, we need to remember that we saw name1. We need to keep that record until we see an entry that sorts after such a hypothetical tree.
We earlier made a mental note that c2==NUL does not count as being less than slash, but it does not matter, as we rejected !c1 && !c2 much earlier.
When we remember name1 this way, we cannot yet tell if it is duplicate, so we don't do anything unusual.
> + } else if (c2 == '/' && is_less_than_slash(c1)) {Now we are seeing a tree. Does it crash with the last "suspicious" name we saw?
> + for (;;) {
> + const char *p;
> + const char *f_name = name_stack_pop(candidates);We pop one name. We know that
- it is a name of a blob object
- all we have seen since then are blobs and commits and no tree
> + if (!f_name)
> + break;
If there is no remembered name, we are done.
> + if (!skip_prefix(name2, f_name, &p))
> + break;
If the remembered name (e.g. "foo") is not a prefix of the current name (e.g. "fop"), we cannot have "foo/" after "fop" we are seeing without violating ordering constraints that we will notice while inspecting the later entries of this tree. So "foo" can be discarded at this point.
> + if (!*p)
> + return TREE_HAS_DUPS;
If name2 and f_name are the same, we have found a duplicate.
> + if (is_less_than_slash(*p)) {If name2 (the one we are currently looking at) has f_name as its prefix, and the first byte that differs is less than slash (again, our earlier observation that NUL is not counted as less than slash does not matter here, as we just handled NUL case before this check), then it still is possible that a tree entry with the same name as f_name is hiding behind name2, so we push it back to the stack (i.e. we cannot tell f_name is a duplicat). Entries in the stack below f_name sorts earlier than f_name, are they are prefixes of f_name in the ascending order of their length (due to the "if not prefix we can pop" logic we saw earlier), and a tree with the same name as stack[n] should sort earlier than a tree with the same name as stack[n-1], so after seeing that we are not ready to determine if f_name has duplicate, we know we are not ready for the names deeper in the stack.
Side note. this is nice but is subtle. I'd need to retrace
the thoughts on this part again later to convince myself
that we are not missing anything.
> + name_stack_push(candidates, f_name);
> + break;
> + }
Otherwise, we know name2 sorts later than the hypothetical entry that is a tree with the same name as f_name, so f_name can be discarded (i.e. we do not push it again). Further, we may notice that name2 makes it impossile for other names in the stack to have entries with the same name, so we iterate.
Show 30 quoted lines
> + }
> + }
> +
> return c1 < c2 ? 0 : TREE_UNORDERED;
> }
>
> @@ -587,6 +651,7 @@ static int fsck_tree(const struct object_id *oid,
> struct tree_desc desc;
> unsigned o_mode;
> const char *o_name;
> + struct name_stack df_dup_candidates = { NULL };
>
> if (init_tree_desc_gently(&desc, buffer, size)) {
> retval += report(options, oid, OBJ_TREE, FSCK_MSG_BAD_TREE, "cannot be parsed as a tree");
> @@ -666,7 +731,8 @@ static int fsck_tree(const struct object_id *oid,
> }
>
> if (o_name) {
> - switch (verify_ordered(o_mode, o_name, mode, name)) {
> + switch (verify_ordered(o_mode, o_name, mode, name,
> + &df_dup_candidates)) {
> case TREE_UNORDERED:
> not_properly_sorted = 1;
> break;
> @@ -682,6 +748,8 @@ static int fsck_tree(const struct object_id *oid,
> o_name = name;
> }
>
> + name_stack_clear(&df_dup_candidates);
> +Show 32 quoted lines
> if (has_null_sha1)
> retval += report(options, oid, OBJ_TREE, FSCK_MSG_NULL_SHA1, "contains entries pointing to null sha1");
> if (has_full_path)
> diff --git a/t/t1450-fsck.sh b/t/t1450-fsck.sh
> index 449ebc5657..91a6e34f38 100755
> --- a/t/t1450-fsck.sh
> +++ b/t/t1450-fsck.sh
> @@ -257,6 +257,22 @@ test_expect_success 'tree object with duplicate entries' '
> test_i18ngrep "error in tree .*contains duplicate file entries" out
> '
>
> +test_expect_success 'tree object with dublicate names' '
> + test_when_finished "remove_object \$blob" &&
> + test_when_finished "remove_object \$tree" &&
> + test_when_finished "remove_object \$badtree" &&
> + blob=$(echo blob | git hash-object -w --stdin) &&
> + printf "100644 blob %s\t%s\n" $blob x.2 >tree &&
> + tree=$(git mktree <tree) &&
> + printf "100644 blob %s\t%s\n" $blob x.1 >badtree &&
> + printf "100644 blob %s\t%s\n" $blob x >>badtree &&
> + printf "040000 tree %s\t%s\n" $tree x >>badtree &&
> + badtree=$(git mktree <badtree) &&
> + test_must_fail git fsck 2>out &&
> + test_i18ngrep "$badtree" out &&
> + test_i18ngrep "error in tree .*contains duplicate file entries" out
> +'
> +
> test_expect_success 'unparseable tree object' '
> test_oid_cache <<-\EOF &&
> junk sha1:twenty-bytes-of-junk
> --
> 2.26.2
