{"thread":{"id":"52764","subject":"[PATCH v2 0/2] Minor fixes to git notes fanout code","startedAt":"2020-02-08T20:44:10Z","lastAt":"2020-02-08T20:44:13Z","messageCount":3,"participants":["Johan Herland"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"391377","messageId":"20200208204404.5531-1-johan@herland.net","threadId":"52764","inReplyTo":null,"subject":"[PATCH v2 0/2] Minor fixes to git notes fanout code","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2020-02-08T20:44:02Z","receivedAt":"2020-02-08T20:44:10Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"No changes from v1 (except cosmetic fixes to commit messages).\n\nJohan Herland (2):\n  t3305: check notes fanout more carefully and robustly\n  notes.c: fix off-by-one error when decreasing notes fanout\n\n notes.c                 |  20 +++++---\n t/t3305-notes-fanout.sh | 107 ++++++++++++++++++++++++++++++----------\n 2 files changed, 94 insertions(+), 33 deletions(-)\n\n-- \n2.23.1\n"},{"id":"391378","messageId":"20200208204404.5531-2-johan@herland.net","threadId":"52764","inReplyTo":"20200208204404.5531-1-johan@herland.net","subject":"[PATCH v2 1/2] t3305: check notes fanout more carefully and robustly","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2020-02-08T20:44:03Z","receivedAt":"2020-02-08T20:44:11Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"In short, before this patch, this test script:\n - creates many notes\n - verifies that all notes in the notes tree has a fanout of 1\n - removes most notes\n - verifies that the notes in the notes tree now has a fanout of 0\n\nThe fanout verification only happened twice: after creating all the\nnotes, and after removing most of them.\n\nThis patch strengthens the test by checking the fanout after _each_\nadded/removed note: We assert that the switch from fanout 0 -> 1\nhappens exactly once while adding notes (and that the switch pervades\nthe entire notes tree). Likewise, we assert that the switch from\nfanout 1 -> 0 happens exactly once while removing notes.\n\nAdditionally, we decrease the number of notes left after removal,\nfrom 50 to 15 notes, in order to ensure that fanout 1 -> 0 transition\nkeeps happening regardless of external factors[1].\n\n[1]: Currently (with the SHA1 hash function and the deterministic\nobject ids of the test environment) the fanout heuristic in the notes\ncode happens to switch from 0 -> 1 at 109 notes, and from 1 -> 0 at\n59 notes. However, changing the hash function or other external\nfactors will vary these numbers, and the latter may - in theory - go\nas low as 15. For more details, please see the discussion at\nhttps://public-inbox.org/git/20200125230035.136348-4-sandals@crustytoothpaste.net/\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n t/t3305-notes-fanout.sh | 101 ++++++++++++++++++++++++++++++----------\n 1 file changed, 76 insertions(+), 25 deletions(-)\n\ndiff --git a/t/t3305-notes-fanout.sh b/t/t3305-notes-fanout.sh\nindex 831f83d211..402057c83a 100755\n--- a/t/t3305-notes-fanout.sh\n+++ b/t/t3305-notes-fanout.sh\n@@ -4,6 +4,32 @@ test_description='Test that adding/removing many notes triggers automatic fanout\n \n . ./test-lib.sh\n \n+path_has_fanout() {\n+\tpath=$1 &&\n+\tfanout=$2 &&\n+\tafter_last_slash=$((40 - $fanout * 2)) &&\n+\techo $path | grep -q \"^\\([0-9a-f]\\{2\\}/\\)\\{$fanout\\}[0-9a-f]\\{$after_last_slash\\}$\"\n+}\n+\n+touched_one_note_with_fanout() {\n+\tnotes_commit=$1 &&\n+\tmodification=$2 &&  # 'A' for addition, 'D' for deletion\n+\tfanout=$3 &&\n+\tdiff=$(git diff-tree --no-commit-id --name-status --root -r $notes_commit) &&\n+\tpath=$(echo $diff | sed -e \"s/^$modification[\\t ]//\") &&\n+\tpath_has_fanout \"$path\" $fanout;\n+}\n+\n+all_notes_have_fanout() {\n+\tnotes_commit=$1 &&\n+\tfanout=$2 &&\n+\tgit ls-tree -r --name-only $notes_commit 2>/dev/null |\n+\twhile read path\n+\tdo\n+\t\tpath_has_fanout $path $fanout || return 1\n+\tdone\n+}\n+\n test_expect_success 'creating many notes with git-notes' '\n \tnum_notes=300 &&\n \ti=0 &&\n@@ -20,7 +46,7 @@ test_expect_success 'creating many notes with git-notes' '\n \n test_expect_success 'many notes created correctly with git-notes' '\n \tgit log | grep \"^    \" > output &&\n-\ti=300 &&\n+\ti=$num_notes &&\n \twhile test $i -gt 0\n \tdo\n \t\techo \"    commit #$i\" &&\n@@ -30,34 +56,46 @@ test_expect_success 'many notes created correctly with git-notes' '\n \ttest_cmp expect output\n '\n \n-test_expect_success 'many notes created with git-notes triggers fanout' '\n-\t# Expect entire notes tree to have a fanout == 1\n-\tgit ls-tree -r --name-only refs/notes/commits |\n-\twhile read path\n+test_expect_success 'stable fanout 0 is followed by stable fanout 1' '\n+\ti=$num_notes &&\n+\tfanout=0 &&\n+\twhile test $i -gt 0\n \tdo\n-\t\techo $path | grep \"^../[0-9a-f]*$\" || {\n-\t\t\techo \"Invalid path \\\"$path\\\"\" &&\n-\t\t\treturn 1;\n-\t\t}\n-\tdone\n+\t\ti=$(($i - 1)) &&\n+\t\tif touched_one_note_with_fanout refs/notes/commits~$i A $fanout\n+\t\tthen\n+\t\t\tcontinue\n+\t\telif test $fanout -eq 0\n+\t\tthen\n+\t\t\tfanout=1 &&\n+\t\t\tif all_notes_have_fanout refs/notes/commits~$i $fanout\n+\t\t\tthen\n+\t\t\t\techo \"Fanout 0 -> 1 at refs/notes/commits~$i\" &&\n+\t\t\t\tcontinue\n+\t\t\tfi\n+\t\tfi &&\n+\t\techo \"Failed fanout=$fanout check at refs/notes/commits~$i\" &&\n+\t\tgit ls-tree -r --name-only refs/notes/commits~$i &&\n+\t\treturn 1\n+\tdone &&\n+\tall_notes_have_fanout refs/notes/commits 1\n '\n \n test_expect_success 'deleting most notes with git-notes' '\n-\tnum_notes=250 &&\n+\tremove_notes=285 &&\n \ti=0 &&\n \tgit rev-list HEAD |\n-\twhile test $i -lt $num_notes && read sha1\n+\twhile test $i -lt $remove_notes && read sha1\n \tdo\n \t\ti=$(($i + 1)) &&\n \t\ttest_tick &&\n-\t\tgit notes remove \"$sha1\" ||\n-\t\texit 1\n+\t\tgit notes remove \"$sha1\" 2>/dev/null || return 1\n \tdone\n '\n \n test_expect_success 'most notes deleted correctly with git-notes' '\n-\tgit log HEAD~250 | grep \"^    \" > output &&\n-\ti=50 &&\n+\tgit log HEAD~$remove_notes | grep \"^    \" > output &&\n+\ti=$(($num_notes - $remove_notes)) &&\n \twhile test $i -gt 0\n \tdo\n \t\techo \"    commit #$i\" &&\n@@ -67,16 +105,29 @@ test_expect_success 'most notes deleted correctly with git-notes' '\n \ttest_cmp expect output\n '\n \n-test_expect_success 'deleting most notes triggers fanout consolidation' '\n-\t# Expect entire notes tree to have a fanout == 0\n-\tgit ls-tree -r --name-only refs/notes/commits |\n-\twhile read path\n+test_expect_success 'stable fanout 1 is followed by stable fanout 0' '\n+\ti=$remove_notes &&\n+\tfanout=1 &&\n+\twhile test $i -gt 0\n \tdo\n-\t\techo $path | grep -v \"^../.*\" || {\n-\t\t\techo \"Invalid path \\\"$path\\\"\" &&\n-\t\t\treturn 1;\n-\t\t}\n-\tdone\n+\t\ti=$(($i - 1)) &&\n+\t\tif touched_one_note_with_fanout refs/notes/commits~$i D $fanout\n+\t\tthen\n+\t\t\tcontinue\n+\t\telif test $fanout -eq 1\n+\t\tthen\n+\t\t\tfanout=0 &&\n+\t\t\tif all_notes_have_fanout refs/notes/commits~$i $fanout\n+\t\t\tthen\n+\t\t\t\techo \"Fanout 1 -> 0 at refs/notes/commits~$i\" &&\n+\t\t\t\tcontinue\n+\t\t\tfi\n+\t\tfi &&\n+\t\techo \"Failed fanout=$fanout check at refs/notes/commits~$i\" &&\n+\t\tgit ls-tree -r --name-only refs/notes/commits~$i &&\n+\t\treturn 1\n+\tdone &&\n+\tall_notes_have_fanout refs/notes/commits 0\n '\n \n test_done\n-- \n2.23.1\n\n"},{"id":"391379","messageId":"20200208204404.5531-3-johan@herland.net","threadId":"52764","inReplyTo":"20200208204404.5531-1-johan@herland.net","subject":"[PATCH v2 2/2] notes.c: fix off-by-one error when decreasing notes fanout","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2020-02-08T20:44:04Z","receivedAt":"2020-02-08T20:44:13Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"As noted in the previous commit, the nature of the fanout heuristic\nin the notes code causes the exact point at which we increase or\ndecrease the notes fanout to vary with the objects being annotated.\nSince the object ids generated by the test environment are\ndeterministic (by design), the notes generated and tested by t3305\nare always the same, and we therefore happen to see the same fanout\nbehavior from one run to the next.\n\nCoincidentally, if we were to change the test environment slightly\n(say by making a test commit on an unrelated branch before we start\nthe t3305 test proper), we not only see the fanout switch happen at\ndifferent points, we also manage to trigger a _bug_ in the notes\ncode where the fanout 1 -> 0 switch is not applied uniformly across\nthe notes tree, but instead yields a notes tree like this:\n\n  ...\n  bdeafb301e44b0e4db0f738a2d2a7beefdb70b70\n  bff2d39b4f7122bd4c5caee3de353a774d1e632a\n  d3/8ec8f851adf470131178085bfbaab4b12ad2a7\n  e0b173960431a3e692ae929736df3c9b73a11d5b\n  eb3c3aede523d729990ac25c62a93eb47c21e2e3\n  ...\n\nThe bug occurs when we are writing out a notes tree with a newly\ndecreased fanout, and the notes tree contains unexpanded subtrees\nthat should be consolidated into the parent tree as a consequence of\nthe decreased fanout):\n\nSubtrees that happen to sit at an _even_ level in the internal notes\n16-tree structure (in other words: subtrees whose path - \"d3\" in the\nexample above - is unique in the first nibble - i.e. there are no\nother note paths that start with \"d\") are _not_ unpacked as part of\nthe tree writeout. This error will repeat itself in subsequent note\ntrees until the subtree is forced to be unpacked. In t3305 this only\nhappens when the d38ec8f8 note is itself removed from the tree.\n\nThe error is not severe (no information is lost, and the notes code\nis able to read/decode this tree and manipulate it correctly), but\nthis is nonetheless a bug in the current implementation that should\nbe fixed.\n\nThat said, fixing the off-by-one error is not without complications:\nWe must take into account that the load_subtree() call from\nfor_each_note_helper() (that is now done to correctly unpack the\nsubtree while we're writing out the notes tree) may end up inserting\nunpacked non-notes into the linked list of non_note entries held by\nthe struct notes_tree. Since we are in the process of writing out the\nnotes tree, this linked list is currently in the process of being\ntraversed by write_each_non_note_until(). The unpacked non-notes are\nnecessarily inserted between the last non-note we wrote out, and the\nnext non-note to be written. Hence, we cannot simply hold the\nnext_non_note to write in struct write_each_note_data (as we would\nthen silently skip these newly inserted notes), but must instead\nalways follow the ->next pointer from the last non-note we wrote.\n(This part was caught by an existing test in t3304.)\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n notes.c                 | 20 ++++++++++++--------\n t/t3305-notes-fanout.sh |  6 ++++++\n 2 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 0c79964c26..2de7f4bcfb 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -576,16 +576,16 @@ static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,\n \t\t\t * the note tree that have not yet been explored. There\n \t\t\t * is a direct relationship between subtree entries at\n \t\t\t * level 'n' in the tree, and the 'fanout' variable:\n-\t\t\t * Subtree entries at level 'n <= 2 * fanout' should be\n+\t\t\t * Subtree entries at level 'n < 2 * fanout' should be\n \t\t\t * preserved, since they correspond exactly to a fanout\n \t\t\t * directory in the on-disk structure. However, subtree\n-\t\t\t * entries at level 'n > 2 * fanout' should NOT be\n+\t\t\t * entries at level 'n >= 2 * fanout' should NOT be\n \t\t\t * preserved, but rather consolidated into the above\n \t\t\t * notes tree level. We achieve this by unconditionally\n \t\t\t * unpacking subtree entries that exist below the\n \t\t\t * threshold level at 'n = 2 * fanout'.\n \t\t\t */\n-\t\t\tif (n <= 2 * fanout &&\n+\t\t\tif (n < 2 * fanout &&\n \t\t\t    flags & FOR_EACH_NOTE_YIELD_SUBTREES) {\n \t\t\t\t/* invoke callback with subtree */\n \t\t\t\tunsigned int path_len =\n@@ -602,7 +602,7 @@ static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,\n \t\t\t\t\t path,\n \t\t\t\t\t cb_data);\n \t\t\t}\n-\t\t\tif (n > fanout * 2 ||\n+\t\t\tif (n >= 2 * fanout ||\n \t\t\t    !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {\n \t\t\t\t/* unpack subtree and resume traversal */\n \t\t\t\ttree->a[i] = NULL;\n@@ -723,13 +723,15 @@ static int write_each_note_helper(struct tree_write_stack *tws,\n \n struct write_each_note_data {\n \tstruct tree_write_stack *root;\n-\tstruct non_note *next_non_note;\n+\tstruct non_note **nn_list;\n+\tstruct non_note *nn_prev;\n };\n \n static int write_each_non_note_until(const char *note_path,\n \t\tstruct write_each_note_data *d)\n {\n-\tstruct non_note *n = d->next_non_note;\n+\tstruct non_note *p = d->nn_prev;\n+\tstruct non_note *n = p ? p->next : *d->nn_list;\n \tint cmp = 0, ret;\n \twhile (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {\n \t\tif (note_path && cmp == 0)\n@@ -740,9 +742,10 @@ static int write_each_non_note_until(const char *note_path,\n \t\t\tif (ret)\n \t\t\t\treturn ret;\n \t\t}\n+\t\tp = n;\n \t\tn = n->next;\n \t}\n-\td->next_non_note = n;\n+\td->nn_prev = p;\n \treturn 0;\n }\n \n@@ -1177,7 +1180,8 @@ int write_notes_tree(struct notes_tree *t, struct object_id *result)\n \tstrbuf_init(&root.buf, 256 * (32 + the_hash_algo->hexsz)); /* assume 256 entries */\n \troot.path[0] = root.path[1] = '\\0';\n \tcb_data.root = &root;\n-\tcb_data.next_non_note = t->first_non_note;\n+\tcb_data.nn_list = &(t->first_non_note);\n+\tcb_data.nn_prev = NULL;\n \n \t/* Write tree objects representing current notes tree */\n \tflags = FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |\ndiff --git a/t/t3305-notes-fanout.sh b/t/t3305-notes-fanout.sh\nindex 402057c83a..3b4753e1b4 100755\n--- a/t/t3305-notes-fanout.sh\n+++ b/t/t3305-notes-fanout.sh\n@@ -30,6 +30,12 @@ all_notes_have_fanout() {\n \tdone\n }\n \n+test_expect_success 'tweak test environment' '\n+\tgit checkout -b nondeterminism &&\n+\ttest_commit A &&\n+\tgit checkout --orphan with_notes;\n+'\n+\n test_expect_success 'creating many notes with git-notes' '\n \tnum_notes=300 &&\n \ti=0 &&\n-- \n2.23.1\n\n"}]}