Incremental use of fast-import may cause conflicting notes

Incremental use of fast-import may cause conflicting notes

[Henrik Grubbström]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1318 bytes --]

Hi.

Background: I have an incremental repository-walker creating a 
corresponding documentation repository from a source repository
that uses git-notes to store its state, a use for which notes
seem very suitable.

Problem: When the number of notes in the root of the notes branch
increases beyond a threshold, fast-import changes the fanout. This 
is as designed, but the problem is that when fast-import is restarted
it won't remember the fanout, and will start writing files in the root 
again. This means that there may be multiple notes-files for the same 
commit, eg both de/adbeef and deadbeef.

This is not what the user expects, and is not good practice, even if it in 
this case actually works, since the latter is defined to have priority.
I'm however not sure if eg fast_import.c:do_change_note_fanout() will do 
the right thing if/when the fanout is changed again.

The problem is probably due to b->num_notes not being initialized properly 
when the old non-empty root commit for the notes branch is loaded in 
parse_from()/parse_new_commit().

My workaround for now is to use filedeleteall and restore all the notes
by hand in the first new commit on the notes branch.

Version of git: 1.7.6.4 (gentoo)

Thanks,

--
Henrik Grubbström					grubba@grubba.org
Roxen Internet Software AB				grubba@roxen.com

Re: Incremental use of fast-import may cause conflicting notes

[Henrik Grubbström]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1437 bytes --]

On Wed, 23 Nov 2011, Henrik Grubbström wrote:

> Hi.
>
> Background: I have an incremental repository-walker creating a corresponding 
> documentation repository from a source repository
> that uses git-notes to store its state, a use for which notes
> seem very suitable.
>
> Problem: When the number of notes in the root of the notes branch
> increases beyond a threshold, fast-import changes the fanout. This is as 
> designed, but the problem is that when fast-import is restarted
> it won't remember the fanout, and will start writing files in the root again. 
> This means that there may be multiple notes-files for the same commit, eg 
> both de/adbeef and deadbeef.
>
> This is not what the user expects, and is not good practice, even if it in 
> this case actually works, since the latter is defined to have priority.
> I'm however not sure if eg fast_import.c:do_change_note_fanout() will do the 
> right thing if/when the fanout is changed again.
>
> The problem is probably due to b->num_notes not being initialized properly 
> when the old non-empty root commit for the notes branch is loaded in 
> parse_from()/parse_new_commit().
>
> My workaround for now is to use filedeleteall and restore all the notes
> by hand in the first new commit on the notes branch.
>
> Version of git: 1.7.6.4 (gentoo)

Oops, wrong machine... 1.7.8.rc3 (gentoo)

> Thanks,

--
Henrik Grubbström					grubba@roxen.com
Roxen Internet Software AB

Re: Incremental use of fast-import may cause conflicting notes

[Jonathan Nieder]

Hi Henrik,

Henrik Grubbström wrote:

> Background: I have an incremental repository-walker creating a corresponding
> documentation repository from a source repository
> that uses git-notes to store its state, a use for which notes
> seem very suitable.

Nice.

[...]
> when fast-import is restarted
> it won't remember the fanout, and will start writing files in the root
> again. This means that there may be multiple notes-files for the same
> commit, eg both de/adbeef and deadbeef.
[...]
> The problem is probably due to b->num_notes not being initialized properly
> when the old non-empty root commit for the notes branch is loaded in
> parse_from()/parse_new_commit().

Sounds like a bug.  Can you suggest a reproduction recipe (ideally as
a patch to t/t9301-fast-import-notes.sh), a fix, or both?

Thanks.

Regards,
Jonathan

[RFC/PATCH 0/3] fast-import: Fix incremental use of notes

[Johan Herland]

Hi,

This is a first attempt at fixing the bug reported by Henrik.

The first two patches provide testcases for the bug, and the last patch
provides a fix.

Have fun! :)

...Johan


Johan Herland (3):
  t9301: Fix testcase covering up a bug in fast-import's notes fanout handling
  t9301: Add 2nd testcase exposing bugs in fast-import's notes fanout handling
  fast-import: Fix incorrect fanout level when modifying existing notes refs

 fast-import.c                |   28 ++++++++++++++++--
 t/t9301-fast-import-notes.sh |   63 ++++++++++++++++++++++++++++++++++++++---
 2 files changed, 83 insertions(+), 8 deletions(-)

-- 
1.7.5.rc1.3.g4d7b

[RFC/PATCH 1/3] t9301: Fix testcase covering up a bug in fast-import's notes fanout handling

[Johan Herland]

There is a bug in fast-import where the fanout levels of an existing notes
tree being loaded into the fast-import machinery is disregarded. Instead, any
tree loaded is assumed to have a fanout level of 0. If the true fanout level
is deeper, any attempt to remove a note from that tree will silently fail
(as the note will not be found at fanout level 0).

However, this bug was covered up by the way in which the t9301 testcase was
written: When generating the fast-import commands to test mass removal of
notes, we appended these commands to an already existing 'input' file which
happened to already contain the fast-import commands used in the previous
subtest to generate the very same notes tree. This would normally be harmless
(but suboptimal) as the notes created were identical to the notes already
present in the notes tree. But the act of repeating all the notes additions
caused the internal fast-import data structures to recalculate the fanout,
instead of hanging on to the initial (incorrect) fanout (that causes the bug
described above). Thus, the subsequent removal of notes in the same 'input'
file would succeed, thereby covering up the bug described above.

This patch creates a new 'input' file instead of appending to the file from
the previous subtest. Thus, we end up properly testing removal of notes that
were added by a previous fast-import command. As a side effect, the notes
removal can no longer refer to commits using the marks set by the previous
fast-import run, instead the commits names must be referenced directly.

The underlying fast-import bug is still present after this patch, but now we
have at least uncovered it. Therefore, the affected subtests are labeled as
expected failures until the underlying bug is fixed.

Signed-off-by: Johan Herland <johan@herland.net>
---
 t/t9301-fast-import-notes.sh |   13 ++++++-------
 1 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/t/t9301-fast-import-notes.sh b/t/t9301-fast-import-notes.sh
index 463254c..fd08161 100755
--- a/t/t9301-fast-import-notes.sh
+++ b/t/t9301-fast-import-notes.sh
@@ -507,7 +507,7 @@ test_expect_success 'verify that non-notes are untouched by a fanout change' '
 '
 remaining_notes=10
 test_tick
-cat >>input <<INPUT_END
+cat >input <<INPUT_END
 commit refs/notes/many_notes
 committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
 data <<COMMIT
@@ -516,12 +516,11 @@ COMMIT
 from refs/notes/many_notes^0
 INPUT_END
 
-i=$remaining_notes
-while test $i -lt $num_commits
+i=$(($num_commits - $remaining_notes))
+for sha1 in $(git rev-list -n $i refs/heads/many_commits)
 do
-	i=$(($i + 1))
 	cat >>input <<INPUT_END
-N 0000000000000000000000000000000000000000 :$i
+N 0000000000000000000000000000000000000000 $sha1
 INPUT_END
 done
 
@@ -541,7 +540,7 @@ EXPECT_END
 	i=$(($i - 1))
 done
 
-test_expect_success 'remove lots of notes' '
+test_expect_failure 'remove lots of notes' '
 
 	git fast-import <input &&
 	GIT_NOTES_REF=refs/notes/many_notes git log refs/heads/many_commits |
@@ -550,7 +549,7 @@ test_expect_success 'remove lots of notes' '
 
 '
 
-test_expect_success 'verify that removing notes trigger fanout consolidation' '
+test_expect_failure 'verify that removing notes trigger fanout consolidation' '
 
 	# All entries in the top-level notes tree should be a full SHA1
 	git ls-tree --name-only -r refs/notes/many_notes |
-- 
1.7.5.rc1.3.g4d7b

[RFC/PATCH 2/3] t9301: Add 2nd testcase exposing bugs in fast-import's notes fanout handling

[Johan Herland]

The previous patch exposed a bug in fast-import where _removing_ an existing
note fails (when that note resides on a non-zero fanout level, and was added
prior to this fast-import run).

This patch demostrates the same issue when _changing_ an existing note
(subject to the same circumstances).

Discovered-by: Henrik Grubbström <grubba@roxen.com>
Signed-off-by: Johan Herland <johan@herland.net>
---
 t/t9301-fast-import-notes.sh |   54 ++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 54 insertions(+), 0 deletions(-)

diff --git a/t/t9301-fast-import-notes.sh b/t/t9301-fast-import-notes.sh
index fd08161..57d85a6 100755
--- a/t/t9301-fast-import-notes.sh
+++ b/t/t9301-fast-import-notes.sh
@@ -505,6 +505,60 @@ test_expect_success 'verify that non-notes are untouched by a fanout change' '
 	test_cmp expect_non-note3 actual
 
 '
+
+# Change the notes for the three top commits
+test_tick
+cat >input <<INPUT_END
+commit refs/notes/many_notes
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+changing notes for the top three commits
+COMMIT
+from refs/notes/many_notes^0
+INPUT_END
+
+rm expect
+i=$num_commits
+j=0
+while test $j -lt 3
+do
+	cat >>input <<INPUT_END
+N inline refs/heads/many_commits~$j
+data <<EOF
+changed note for commit #$i
+EOF
+INPUT_END
+	cat >>expect <<EXPECT_END
+    commit #$i
+    changed note for commit #$i
+EXPECT_END
+	i=$(($i - 1))
+	j=$(($j + 1))
+done
+
+test_expect_failure 'change a few existing notes' '
+
+	git fast-import <input &&
+	GIT_NOTES_REF=refs/notes/many_notes git log -n3 refs/heads/many_commits |
+	    grep "^    " > actual &&
+	test_cmp expect actual
+
+'
+
+test_expect_failure 'verify that changing notes respect existing fanout' '
+
+	# None of the entries in the top-level notes tree should be a full SHA1
+	git ls-tree --name-only refs/notes/many_notes |
+	while read path
+	do
+		if test $(expr length "$path") -ge 40
+		then
+			return 1
+		fi
+	done
+
+'
+
 remaining_notes=10
 test_tick
 cat >input <<INPUT_END
-- 
1.7.5.rc1.3.g4d7b

[RFC/PATCH 3/3] fast-import: Fix incorrect fanout level when modifying existing notes refs

[Johan Herland]

This fixes the bug uncovered by the tests added in the previous two patches.

When an existing notes ref was loaded into the fast-import machinery, the
num_notes counter associated with that ref remained == 0, even though the
true number of notes in the loaded ref was higher. This caused a fanout
level of 0 to be used, although the actual fanout of the tree could be > 0.
Manipulating the notes tree at an incorrect fanout level causes removals to
silently fail, and modifications of existing notes to instead produce an
additional note (leaving the old object in place at a different fanout level).

This patch fixes the bug by explicitly counting the number of notes in the
notes tree whenever it looks like the num_notes counter could be wrong (when
num_notes == 0). There may be false positives (i.e. triggering the counting
when the notes tree is truly empty), but in those cases, the counting should
not take long.

Signed-off-by: Johan Herland <johan@herland.net>
---
 fast-import.c                |   28 +++++++++++++++++++++++++---
 t/t9301-fast-import-notes.sh |    8 ++++----
 2 files changed, 29 insertions(+), 7 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 8d8ea3c..f4bfe0f 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -2173,6 +2173,11 @@ static uintmax_t do_change_note_fanout(
 
 		if (tmp_hex_sha1_len == 40 && !get_sha1_hex(hex_sha1, sha1)) {
 			/* This is a note entry */
+			if (fanout == 0xff) {
+				/* Counting mode, no rename */
+				num_notes++;
+				continue;
+			}
 			construct_path_with_fanout(hex_sha1, fanout, realpath);
 			if (!strcmp(fullpath, realpath)) {
 				/* Note entry is in correct location */
@@ -2379,7 +2384,7 @@ static void file_change_cr(struct branch *b, int rename)
 		leaf.tree);
 }
 
-static void note_change_n(struct branch *b, unsigned char old_fanout)
+static void note_change_n(struct branch *b, unsigned char *old_fanout)
 {
 	const char *p = command_buf.buf + 2;
 	static struct strbuf uq = STRBUF_INIT;
@@ -2390,6 +2395,23 @@ static void note_change_n(struct branch *b, unsigned char old_fanout)
 	uint16_t inline_data = 0;
 	unsigned char new_fanout;
 
+	/*
+	 * When loading a branch, we don't traverse its tree to count the real
+	 * number of notes (too expensive to do this for all non-note refs).
+	 * This means that recently loaded notes refs might incorrectly have
+	 * b->num_notes == 0, and consequently, old_fanout might be wrong.
+	 *
+	 * Fix this by traversing the tree and counting the number of notes
+	 * when b->num_notes == 0. If the notes tree is truly empty, the
+	 * calculation should not take long.
+	 */
+	if (b->num_notes == 0 && *old_fanout == 0) {
+		/* Invoke change_note_fanout() in "counting mode". */
+		b->num_notes = change_note_fanout(&b->branch_tree, 0xff);
+		*old_fanout = convert_num_notes_to_fanout(b->num_notes);
+	}
+
+	/* Now parse the notemodify command. */
 	/* <dataref> or 'inline' */
 	if (*p == ':') {
 		char *x;
@@ -2450,7 +2472,7 @@ static void note_change_n(struct branch *b, unsigned char old_fanout)
 			    typename(type), command_buf.buf);
 	}
 
-	construct_path_with_fanout(sha1_to_hex(commit_sha1), old_fanout, path);
+	construct_path_with_fanout(sha1_to_hex(commit_sha1), *old_fanout, path);
 	if (tree_content_remove(&b->branch_tree, path, NULL))
 		b->num_notes--;
 
@@ -2637,7 +2659,7 @@ static void parse_new_commit(void)
 		else if (!prefixcmp(command_buf.buf, "C "))
 			file_change_cr(b, 0);
 		else if (!prefixcmp(command_buf.buf, "N "))
-			note_change_n(b, prev_fanout);
+			note_change_n(b, &prev_fanout);
 		else if (!strcmp("deleteall", command_buf.buf))
 			file_change_deleteall(b);
 		else if (!prefixcmp(command_buf.buf, "ls "))
diff --git a/t/t9301-fast-import-notes.sh b/t/t9301-fast-import-notes.sh
index 57d85a6..83acf68 100755
--- a/t/t9301-fast-import-notes.sh
+++ b/t/t9301-fast-import-notes.sh
@@ -536,7 +536,7 @@ EXPECT_END
 	j=$(($j + 1))
 done
 
-test_expect_failure 'change a few existing notes' '
+test_expect_success 'change a few existing notes' '
 
 	git fast-import <input &&
 	GIT_NOTES_REF=refs/notes/many_notes git log -n3 refs/heads/many_commits |
@@ -545,7 +545,7 @@ test_expect_failure 'change a few existing notes' '
 
 '
 
-test_expect_failure 'verify that changing notes respect existing fanout' '
+test_expect_success 'verify that changing notes respect existing fanout' '
 
 	# None of the entries in the top-level notes tree should be a full SHA1
 	git ls-tree --name-only refs/notes/many_notes |
@@ -594,7 +594,7 @@ EXPECT_END
 	i=$(($i - 1))
 done
 
-test_expect_failure 'remove lots of notes' '
+test_expect_success 'remove lots of notes' '
 
 	git fast-import <input &&
 	GIT_NOTES_REF=refs/notes/many_notes git log refs/heads/many_commits |
@@ -603,7 +603,7 @@ test_expect_failure 'remove lots of notes' '
 
 '
 
-test_expect_failure 'verify that removing notes trigger fanout consolidation' '
+test_expect_success 'verify that removing notes trigger fanout consolidation' '
 
 	# All entries in the top-level notes tree should be a full SHA1
 	git ls-tree --name-only -r refs/notes/many_notes |
-- 
1.7.5.rc1.3.g4d7b