From: "René Scharfe" <l.s.r@web.de>
To: Junio C Hamano <gitster@pobox.com>
Cc: Brandon Williams <bwilliamseng@gmail.com>,
git <git@vger.kernel.org>, Jeff King <peff@peff.net>
Subject: Re: invalid tree and commit object
Date: Sun, 10 May 2020 18:12:16 +0200 [thread overview]
Message-ID: <2937d635-52a9-5e69-b3d2-fbde415b7315@web.de> (raw)
In-Reply-To: <aab9512b-a70a-0f5b-5cdc-5d40acd343d0@web.de>
Am 10.05.20 um 11:07 schrieb René Scharfe:
> 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.
Here's what I mean. It seems to work, but could use some critical
thought and testing.
-- >8 --
Subject: [PATCH] fsck: report non-consecutive duplicate names in trees
Tree entries are sorted in path order, meaning that directory names get
a slash ('/') appended implicitly. Git fsck checks if trees contains
consecutive duplicates, but due to that ordering there can be
non-consecutive duplicates as well if one of them is a directory and the
other one isn't. Such a tree cannot be fully checked out.
Find these duplicates by recording candidate file names on a stack and
check candidate directory names against that stack to find matches.
Suggested-by: Brandon Williams <bwilliamseng@gmail.com>
Original-test-by: Brandon Williams <bwilliamseng@gmail.com>
Signed-off-by: René Scharfe <l.s.r@web.de>
---
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;
+}
+
/*
* The entries in a tree are ordered in the _path_ order,
* which means that a directory entry is ordered by adding
@@ -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 < '/';
+}
+
+static int verify_ordered(unsigned mode1, const char *name1,
+ unsigned mode2, const char *name2,
+ struct name_stack *candidates)
{
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 = '/';
+
+ /*
+ * There can be non-consecutive duplicates due to the implicitly
+ * add slash, e.g.:
+ *
+ * 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);
+ } else if (c2 == '/' && is_less_than_slash(c1)) {
+ for (;;) {
+ const char *p;
+ const char *f_name = name_stack_pop(candidates);
+
+ if (!f_name)
+ break;
+ if (!skip_prefix(name2, f_name, &p))
+ break;
+ if (!*p)
+ return TREE_HAS_DUPS;
+ if (is_less_than_slash(*p)) {
+ name_stack_push(candidates, f_name);
+ break;
+ }
+ }
+ }
+
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);
+
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
next prev parent reply other threads:[~2020-05-10 16:12 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-09 6:19 invalid tree and commit object Brandon Williams
2020-05-09 10:16 ` René Scharfe
2020-05-09 7:16 ` Johannes Schindelin
2020-05-09 11:51 ` René Scharfe
2020-05-09 17:28 ` Junio C Hamano
2020-05-09 19:24 ` René Scharfe
2020-05-09 20:27 ` Junio C Hamano
2020-05-10 9:07 ` René Scharfe
2020-05-10 16:12 ` René Scharfe [this message]
2020-05-11 16:25 ` Junio C Hamano
2020-05-13 16:27 ` Brandon Williams
2020-05-21 9:51 ` René Scharfe
2020-05-21 9:52 ` [PATCH 1/4] fsck: fix a typo in a comment René Scharfe
2020-05-21 10:10 ` Denton Liu
2020-05-21 11:15 ` René Scharfe
2020-05-21 9:52 ` [PATCH 2/4] t1450: increase test coverage of in-tree d/f detection René Scharfe
2020-05-21 10:20 ` Denton Liu
2020-05-21 13:31 ` René Scharfe
2020-05-21 18:01 ` Junio C Hamano
2020-05-21 9:52 ` [PATCH 3/4] t1450: demonstrate undetected in-tree d/f conflict René Scharfe
2020-05-21 9:52 ` [PATCH 4/4] fsck: detect more in-tree d/f conflicts René Scharfe
2020-05-10 16:37 ` invalid tree and commit object Junio C Hamano
2020-05-21 9:51 ` René Scharfe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2937d635-52a9-5e69-b3d2-fbde415b7315@web.de \
--to=l.s.r@web.de \
--cc=bwilliamseng@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).