{"thread":{"id":"38281","subject":"[RFC/PATCHv0 1/4] fast-import.c:do_change_note_fanout(): Remove unneeded local var 't'","startedAt":"2015-01-05T03:37:23Z","lastAt":"2015-01-05T03:39:38Z","messageCount":5,"participants":["Johan Herland"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"254287","messageId":"CALKQrgdVp7cLER2DQxwdFT82Y=Pamrx6=oa3bY=X7mWy_r3QWA@mail.gmail.com","threadId":"38281","inReplyTo":"20141223000611.GB10980@glandium.org","subject":"Re: fast-import's notemodify doesn't work the same as git notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2015-01-05T03:37:23Z","receivedAt":"2015-01-05T03:37:23Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"(sorry for the late answer, I've been away from email over the holidays)\n\nOn Tue, Dec 23, 2014 at 1:06 AM, Mike Hommey <mh@glandium.org> wrote:\n> Hi,\n>\n> There are two major differences between adding notes with fast-import\n> and git notes, one of which is a serious problem:\n>\n> - fast-import doesn't want to add notes for non commits, while git notes\n>   does.\n\nTrue. I consider this a bug in fast-import. A first draft of a patch\nseries to fix that will be posted shortly.\n\n> - fast-import and git notes have different, conflicting fanouts:\n\nYes. The relevant code in fast-import and git-notes is largely\nseparate and independent of each other.\n\nThe main reason for this, IIRC, is that fast-import uses its own data\nstructures and algorithms when building trees, and that makes it hard\nto reuse the git-notes code (fast-import.c does not even #include\nnotes.h because of this).\n\nfast-import is fundamentally built to solve a somewhat different use\ncase than the rest of the git tools, and I believe this is why it\n\"goes it alone\" and implements its own (duplicate - to a certain\ndegree) data structures and algorithms: It is heavily geared towards\ncreating a _lot_ of trees in as little time and space as possible.\n\nThe fast-import documentation states that the packs it generates are\nsub-optimal, and that you should always repack after fast-import to\nget more optimal/usable packs. Although not documented, a similar\nanalogy applies to notes trees: fast-import will import a lot of notes\nquickly and efficiently, but the resulting fanout might not be the\nsame (or as optimal) as what git-notes would produce.\n\nIMHO, it is not optimal (at least not currently) to use a workflow\nthat interleaves notes tree manipulation from fast-import and\ngit-notes, like you do below. You risk a lot of fanout churn, since\nthe fanout calculation logic is different between the two. That said,\nthere are clearly also bugs in the current fast-import behavior that\nwe should fix... :)\n\n>   - take e.g. the git repo (there needs to be a lot of commits to start\n>     to see the problem)\n>   - run the following to create notes for every commit:\n>       (echo 'blob';\n>        echo 'mark :1';\n>        echo 'data 0';\n>        echo 'commit refs/notes/foo';\n>        echo 'committer <foo> 0 +0000';\n>        echo 'data 0';\n>        git rev-list --all | awk '{print \"N :1\", $1}';\n>        echo) | git fast-import\n>   - pick a random commit. I'll pick\n>     bbcefffcea9789e4a1a2023a1c778e2c07db77a7 as it is current master as\n>     of writing. Take the first two characters of that sha1, and look at\n>     the ls-tree:\n>       git ls-tree refs/notes/foo bb/\n>     You'll see a number of blobs.\n\nOk, so fast-import yields a 2/38 fanout for ~50 000 notes (#commits in\ngit.git). fast-import keeps track of the total number of notes in the\ntree (although there are bugs, see the patch series), and divides that\nnumber repeatedly by 256 to find the fanout, so this result is\nexpected, AFAICS\n\n>   - Now, remove the note for that commit with git notes:\n>       git notes --ref foo remove bbcefffcea9789e4a1a2023a1c778e2c07db77a7\n>   - ls-tree again, you'll now see a number of trees instead of blobs,\n>     because git notes will have done a fanout. -> git notes does fanouts\n>     for much less items than fast-import does.\n\nMaybe. git-notes has a different heuristic that does not keep track of\nthe total number of notes in the tree. This is because git-notes only\nloads the required parts of the notes tree, so when you remove that\nsingle note, only the relevant parts of the notes tree (the bb/* tree)\nis loaded and manipulated. Then, git-notes looks at the density of\nnote entries in that sub-tree (see determine_fanout() in notes.c for\nthe details) to figure out if the fanout needs to be adjusted (but\nonly in that sub-tree). In this case, it looks like the heuristic\ntriggers a nested fanout within the bb/* tree. However, the other 255\n\"top-level\" trees are not loaded, and hence not \"re-balanced\" by\ngit-notes.\n\n>   - Re-add a note for that commit with fast-import:\n>       git fast-import <<EOF\n>       blob\n>       mark :1\n>       data 0\n>       commit refs/notes/foo\n>       committer <foo> 0 +0000\n>       data 0\n>       from refs/notes/foo^0\n>       N :1 bbcefffcea9789e4a1a2023a1c778e2c07db77a7\n>\n>       EOF\n>   - ls-tree again, and you'll see a number of trees and *one* blob, for\n>     bb/cefffcea9789e4a1a2023a1c778e2c07db77a7\n\nHmm... Here I'd expect fast-import to rewrite the entire notes tree,\nnot just a single entry. Not sure if this is a symptom of the bug\ndiscussed in our previous thread, or if this is a deeper problem.\n\n>   - See the thread starting with 20141126004242.GA13915@glandium.org,\n>     this type of notes branch make things very slow.\n\nI have a suggested fix for this in my upcoming patch series. Please\ntest this with your scenario to see if it makes a difference.\n\n>   - Now, if you take an even bigger repository (as long as there are more\n>     than 65536 commits, that's good ; I guess the linux kernel\n>     qualifies, I've been checking with a mozilla-central clone), and\n>     create exactly 65535 notes with git fast-import, you'll end up with\n>     a 1-level tree (2/38). Add one more note, and the entire tree turns\n>     into a 2-level tree (2/2/36). git notes would only add a level to\n>     the tree containing the added note. git notes's behavior scales\n>     better, because think about what happens on the next fanout with\n>     fast-import... adding one note would need to create millions of trees.\n\nTrue, this is a good illustration of the difference between the notes\ncode in fast-import and git-notes. It might be possible to change the\nfast-import code to work more like the git-notes code, but it's been\nquite a while since I looked closely at this, and I'm not sure it is\nas easy as it sounds.\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"254281","messageId":"1420429178-20336-1-git-send-email-johan@herland.net","threadId":"38281","inReplyTo":"CALKQrgdVp7cLER2DQxwdFT82Y=Pamrx6=oa3bY=X7mWy_r3QWA@mail.gmail.com","subject":"[RFC/PATCHv0 1/4] fast-import.c:do_change_note_fanout(): Remove unneeded local var 't'","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2015-01-05T03:39:35Z","receivedAt":"2015-01-05T03:39:35Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The struct tree_content *t variable was used as a shorthand for the\ngiven root->tree, but it was only used in the first two lines of the for\nloop, so the shorthand itself does not add much value. Furthermore,\nsince the for loop body might end up reallocating root->tree we had to\nreinitialize t at the end of the for loop body, which is ugly and brittle.\n\nSimply use root->tree directly instead, and remote the t shorthand.\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n fast-import.c | 8 ++------\n 1 file changed, 2 insertions(+), 6 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex d0bd285..04dfd50 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2153,15 +2153,14 @@ static uintmax_t do_change_note_fanout(\n \t\tchar *fullpath, unsigned int fullpath_len,\n \t\tunsigned char fanout)\n {\n-\tstruct tree_content *t = root->tree;\n \tstruct tree_entry *e, leaf;\n \tunsigned int i, tmp_hex_sha1_len, tmp_fullpath_len;\n \tuintmax_t num_notes = 0;\n \tunsigned char sha1[20];\n \tchar realpath[60];\n \n-\tfor (i = 0; t && i < t->entry_count; i++) {\n-\t\te = t->entries[i];\n+\tfor (i = 0; root->tree && i < root->tree->entry_count; i++) {\n+\t\te = root->tree->entries[i];\n \t\ttmp_hex_sha1_len = hex_sha1_len + e->name->str_len;\n \t\ttmp_fullpath_len = fullpath_len;\n \n@@ -2217,9 +2216,6 @@ static uintmax_t do_change_note_fanout(\n \t\t\t\thex_sha1, tmp_hex_sha1_len,\n \t\t\t\tfullpath, tmp_fullpath_len, fanout);\n \t\t}\n-\n-\t\t/* The above may have reallocated the current tree_content */\n-\t\tt = root->tree;\n \t}\n \treturn num_notes;\n }\n-- \n2.1.1.392.g062cc5d\n"},{"id":"254284","messageId":"1420429178-20336-2-git-send-email-johan@herland.net","threadId":"38281","inReplyTo":"1420429178-20336-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv0 2/4] fast-import.c:do_change_note_fanout(): Also apply load_tree() to initial root","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2015-01-05T03:39:36Z","receivedAt":"2015-01-05T03:39:36Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"TODO: tests!\n\ndo_change_note_fanout() recursively traverses a \"struct tree_entry\" data\nstructure. Before recursively traversing into a subtree, we make sure to\ncall load_tree() on that subtree. However, for the initial/root struct\ntree_entry object, we assumed that load_tree() had already been invoked by\nour caller. This is true, except in the following case:\n\nIf we load a previously written notes tree using 'filemodify' instead of\n'from' [1], then we do not pass the notes ref to load_branch() (which\ntakes care of calling load_tree() on the root tree_entry).\n\nWhen load_tree(root) has not been called before the first 'notemodify'\ncommand is parsed, the for loop in do_change_note_fanout() does nothing,\nand we end up not counting the existing notes, which ends up producing\na notes tree with mixed/insufficient fanout.\n\nFix this by always making sure to call load_tree() at the start of\ndo_change_note_fanout(). Since load_tree() is now called before the for loop,\nwe no longer need to call load_tree() on a subtree before recursing into it,\nthe recursive call will take care of its own load_tree().\n\n[1]: Usually, when adding notes to an existing notes tree, one would use a\n     'from' command like this:\n\n         from refs/notes/foo^0\n\n     However, if one does not want to retain notes history (i.e. one wants\n     the current refs/notes/foo commit to be build without any parents),\n     then one can replace the 'from' command with the following 'filemodify'\n     \"hack\" to pre-load the existing notes tree without using it as a parent:\n\n         M 040000 refs/notes/foo^{tree} \\n\n\nDiscovered-by: Mike Hommey <mh@glandium.org>\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n fast-import.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 04dfd50..aa7b64e 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2159,6 +2159,9 @@ static uintmax_t do_change_note_fanout(\n \tunsigned char sha1[20];\n \tchar realpath[60];\n \n+\tif (!root->tree)\n+\t\tload_tree(root);\n+\n \tfor (i = 0; root->tree && i < root->tree->entry_count; i++) {\n \t\te = root->tree->entries[i];\n \t\ttmp_hex_sha1_len = hex_sha1_len + e->name->str_len;\n@@ -2210,8 +2213,6 @@ static uintmax_t do_change_note_fanout(\n \t\t\t\tleaf.tree);\n \t\t} else if (S_ISDIR(e->versions[1].mode)) {\n \t\t\t/* This is a subdir that may contain note entries */\n-\t\t\tif (!e->tree)\n-\t\t\t\tload_tree(e);\n \t\t\tnum_notes += do_change_note_fanout(orig_root, e,\n \t\t\t\thex_sha1, tmp_hex_sha1_len,\n \t\t\t\tfullpath, tmp_fullpath_len, fanout);\n-- \n2.1.1.392.g062cc5d\n"},{"id":"254282","messageId":"1420429178-20336-3-git-send-email-johan@herland.net","threadId":"38281","inReplyTo":"1420429178-20336-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv0 3/4] fast-import: Support adding notes to non-commits","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2015-01-05T03:39:37Z","receivedAt":"2015-01-05T03:39:37Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"\"git notes\" allows adding notes to non-commit objects, but fast-import\nrestricts the 'notemodify' command to only add notes for commit objects.\nRemove that silly restriction from fast-import.\n\nSuggested-by: Mike Hommey <mh@glandium.org>\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n fast-import.c                | 12 ++++------\n t/t9301-fast-import-notes.sh | 56 ++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 60 insertions(+), 8 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex aa7b64e..b6df00b 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2498,16 +2498,12 @@ static void note_change_n(const char *p, struct branch *b, unsigned char *old_fa\n \t} else if (*p == ':') {\n \t\tuintmax_t commit_mark = parse_mark_ref_eol(p);\n \t\tstruct object_entry *commit_oe = find_mark(commit_mark);\n-\t\tif (commit_oe->type != OBJ_COMMIT)\n-\t\t\tdie(\"Mark :%\" PRIuMAX \" not a commit\", commit_mark);\n \t\thashcpy(commit_sha1, commit_oe->idx.sha1);\n \t} else if (!get_sha1(p, commit_sha1)) {\n-\t\tunsigned long size;\n-\t\tchar *buf = read_object_with_reference(commit_sha1,\n-\t\t\tcommit_type, &size, commit_sha1);\n-\t\tif (!buf || size < 46)\n-\t\t\tdie(\"Not a valid commit: %s\", p);\n-\t\tfree(buf);\n+\t\tif (!find_object(commit_sha1)) {\n+\t\t\tif (sha1_object_info(commit_sha1, NULL) < 0)\n+\t\t\t\tdie(\"Not a valid object: %s\", p);\n+\t\t}\n \t} else\n \t\tdie(\"Invalid ref name or SHA1 expression: %s\", p);\n \ndiff --git a/t/t9301-fast-import-notes.sh b/t/t9301-fast-import-notes.sh\nindex 83acf68..b8ff673 100755\n--- a/t/t9301-fast-import-notes.sh\n+++ b/t/t9301-fast-import-notes.sh\n@@ -679,4 +679,60 @@ test_expect_success \"add notes to $num_commits commits in each of $num_notes_ref\n \n '\n \n+tree4=$(git rev-parse refs/heads/master^{tree})\n+blob4=$(git rev-parse refs/heads/master:bar)\n+\n+test_tick\n+cat >input <<INPUT_END\n+commit refs/notes/noncommits\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+data <<COMMIT\n+adding notes to non-commits\n+COMMIT\n+\n+N inline $tree4\n+data <<EOF\n+note for tree object\n+EOF\n+\n+N inline $blob4\n+data <<EOF\n+note for blob object\n+EOF\n+\n+INPUT_END\n+\n+test_expect_success 'add notes to non-commits' \"\n+\n+\tgit fast-import <input &&\n+\techo 'note for tree object' >expect &&\n+\tgit notes --ref noncommits show $tree4 >actual &&\n+\ttest_cmp expect actual &&\n+\techo 'note for blob object' >expect &&\n+\tgit notes --ref noncommits show $blob4 >actual &&\n+\ttest_cmp expect actual\n+\n+\"\n+\n+test_tick\n+cat >input <<INPUT_END\n+commit refs/notes/nonobjects\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+data <<COMMIT\n+adding notes to non-objects MUST FAIL\n+COMMIT\n+\n+N inline deadbeefdeadbeefdeadbeefdeadbeefdeadbeef\n+data <<EOF\n+note for missing object\n+EOF\n+\n+INPUT_END\n+\n+test_expect_success 'cannot add notes to non-objects' \"\n+\n+\ttest_must_fail git fast-import <input\n+\n+\"\n+\n test_done\n-- \n2.1.1.392.g062cc5d\n"},{"id":"254283","messageId":"1420429178-20336-4-git-send-email-johan@herland.net","threadId":"38281","inReplyTo":"1420429178-20336-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv0 4/4] fast-import.c:note_change_n(): Rename commit_* to target_*","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2015-01-05T03:39:38Z","receivedAt":"2015-01-05T03:39:38Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Since we now allow adding notes to any kind of object (not just commits),\nrename the related variables from \"commit_*\" to \"target_*\".\n\nTODO: Also replace \"commit-ish\" with something more suitable in the\ndocumentation. However, the same needs to be done for the 'tag' command,\nand we also the BNF at the top of fast-import.c needs corresponding updates.\n\nSigned-off-by: Johan Herland <johan@herland.net>\n---\n fast-import.c | 22 +++++++++++-----------\n 1 file changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex b6df00b..4ef7a95 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -2451,7 +2451,7 @@ static void note_change_n(const char *p, struct branch *b, unsigned char *old_fa\n \tstatic struct strbuf uq = STRBUF_INIT;\n \tstruct object_entry *oe;\n \tstruct branch *s;\n-\tunsigned char sha1[20], commit_sha1[20];\n+\tunsigned char sha1[20], target_sha1[20];\n \tchar path[60];\n \tuint16_t inline_data = 0;\n \tunsigned char new_fanout;\n@@ -2489,19 +2489,19 @@ static void note_change_n(const char *p, struct branch *b, unsigned char *old_fa\n \t\t\tdie(\"Missing space after SHA1: %s\", command_buf.buf);\n \t}\n \n-\t/* <commit-ish> */\n+\t/* <object> */\n \ts = lookup_branch(p);\n \tif (s) {\n \t\tif (is_null_sha1(s->sha1))\n \t\t\tdie(\"Can't add a note on empty branch.\");\n-\t\thashcpy(commit_sha1, s->sha1);\n+\t\thashcpy(target_sha1, s->sha1);\n \t} else if (*p == ':') {\n-\t\tuintmax_t commit_mark = parse_mark_ref_eol(p);\n-\t\tstruct object_entry *commit_oe = find_mark(commit_mark);\n-\t\thashcpy(commit_sha1, commit_oe->idx.sha1);\n-\t} else if (!get_sha1(p, commit_sha1)) {\n-\t\tif (!find_object(commit_sha1)) {\n-\t\t\tif (sha1_object_info(commit_sha1, NULL) < 0)\n+\t\tuintmax_t target_mark = parse_mark_ref_eol(p);\n+\t\tstruct object_entry *target_oe = find_mark(target_mark);\n+\t\thashcpy(target_sha1, target_oe->idx.sha1);\n+\t} else if (!get_sha1(p, target_sha1)) {\n+\t\tif (!find_object(target_sha1)) {\n+\t\t\tif (sha1_object_info(target_sha1, NULL) < 0)\n \t\t\t\tdie(\"Not a valid object: %s\", p);\n \t\t}\n \t} else\n@@ -2527,7 +2527,7 @@ static void note_change_n(const char *p, struct branch *b, unsigned char *old_fa\n \t\t\t    typename(type), command_buf.buf);\n \t}\n \n-\tconstruct_path_with_fanout(sha1_to_hex(commit_sha1), *old_fanout, path);\n+\tconstruct_path_with_fanout(sha1_to_hex(target_sha1), *old_fanout, path);\n \tif (tree_content_remove(&b->branch_tree, path, NULL, 0))\n \t\tb->num_notes--;\n \n@@ -2536,7 +2536,7 @@ static void note_change_n(const char *p, struct branch *b, unsigned char *old_fa\n \n \tb->num_notes++;\n \tnew_fanout = convert_num_notes_to_fanout(b->num_notes);\n-\tconstruct_path_with_fanout(sha1_to_hex(commit_sha1), new_fanout, path);\n+\tconstruct_path_with_fanout(sha1_to_hex(target_sha1), new_fanout, path);\n \ttree_content_set(&b->branch_tree, path, sha1, S_IFREG | 0644, NULL);\n }\n \n-- \n2.1.1.392.g062cc5d\n"}]}