{"thread":{"id":"37530","subject":"[PATCH] refs: speed up is_refname_available","startedAt":"2014-09-10T10:17:31Z","lastAt":"2014-09-11T18:31:43Z","messageCount":7,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"249114","messageId":"20140910101730.GA12399@peff.net","threadId":"37530","inReplyTo":null,"subject":"[PATCH] refs: speed up is_refname_available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-10T10:17:31Z","receivedAt":"2014-09-10T10:17:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our filesystem ref storage does not allow D/F conflicts; so\nif \"refs/heads/a/b\" exists, we do not allow \"refs/heads/a\"\nto exist (and vice versa). This falls out naturally for\nloose refs, where the filesystem enforces the condition. But\nfor packed-refs, we have to make the check ourselves.\n\nWe do so by iterating over the entire packed-refs namespace\nand checking whether each name creates a conflict. If you\nhave a very large number of refs, this is quite inefficient,\nas you end up doing a large number of comparisons with\nuninteresting bits of the ref tree (e.g., we know that all\nof \"refs/tags\" is uninteresting in the example above, yet we\ncheck each entry in it).\n\nInstead, let's take advantage of the fact that we have the\npacked refs stored as a trie of ref_entry structs. We can\nfind each component of the proposed refname as we walk\nthrough the trie, checking for D/F conflicts as we go. For a\nrefname of depth N (i.e., 4 in the above example), we only\nhave to visit N nodes. And at each visit, we can binary\nsearch the M names at that level, for a total complexity of\nO(N lg M). (\"M\" is different at each level, of course, but\nwe can take the worst-case \"M\" as a bound).\n\nIn a pathological case of fetching 30,000 fresh refs into a\nrepository with 8.5 million refs, this dropped the time to\nrun \"git fetch\" from tens of minutes to ~30s.\n\nThis may also help smaller cases in which we check against\nloose refs (which we do when renaming a ref), as we may\navoid a disk access for unrelated loose directories.\n\nNote that the tests we add appear at first glance to be\nredundant with what is already in t3210. However, the early\ntests are not robust; they are run with reflogs turned on,\nmeaning that we are not actually testing\nis_refname_available at all! The operations will still fail\nbecause the reflogs will hit D/F conflicts in the\nfilesystem. To get a true test, we must turn off reflogs\n(but we don't want to do so for the entire script, because\nthe point of turning them on was to cover some other cases).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe diff's a bit hard to read, because it keeps useless lines like \"{\"\nas context. I thought histogram and patience were supposed to be more\nreadable there, but they seem to produce the same thing.\n\nThis has a fairly straightforward conflict with the ref-transaction\nstuff in pu. The \"oldrefname\" parameter to is_refname_available became a\nlist of items; we resolve it by teaching entry_matches to do the same\nhere.  I pushed a proposed resolution up to:\n\n  git://github.com/peff/git.git resolution-refname-available\n\n refs.c               | 123 +++++++++++++++++++++++++++++++++++++--------------\n t/t3210-pack-refs.sh |  31 ++++++++++++-\n 2 files changed, 121 insertions(+), 33 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 27927f2..4e5639c 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -779,37 +779,32 @@ static void prime_ref_dir(struct ref_dir *dir)\n \t\t\tprime_ref_dir(get_ref_dir(entry));\n \t}\n }\n-/*\n- * Return true iff refname1 and refname2 conflict with each other.\n- * Two reference names conflict if one of them exactly matches the\n- * leading components of the other; e.g., \"foo/bar\" conflicts with\n- * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n- * \"foo/barbados\".\n- */\n-static int names_conflict(const char *refname1, const char *refname2)\n+\n+static int entry_matches(struct ref_entry *entry, const char *refname)\n {\n-\tfor (; *refname1 && *refname1 == *refname2; refname1++, refname2++)\n-\t\t;\n-\treturn (*refname1 == '\\0' && *refname2 == '/')\n-\t\t|| (*refname1 == '/' && *refname2 == '\\0');\n+\treturn refname && !strcmp(entry->name, refname);\n }\n \n-struct name_conflict_cb {\n-\tconst char *refname;\n-\tconst char *oldrefname;\n-\tconst char *conflicting_refname;\n+struct nonmatching_ref_data {\n+\tconst char *skip;\n+\tstruct ref_entry *found;\n };\n \n-static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n+static int nonmatching_ref_fn(struct ref_entry *entry, void *vdata)\n {\n-\tstruct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;\n-\tif (data->oldrefname && !strcmp(data->oldrefname, entry->name))\n+\tstruct nonmatching_ref_data *data = vdata;\n+\n+\tif (entry_matches(entry, data->skip))\n \t\treturn 0;\n-\tif (names_conflict(data->refname, entry->name)) {\n-\t\tdata->conflicting_refname = entry->name;\n-\t\treturn 1;\n-\t}\n-\treturn 0;\n+\n+\tdata->found = entry;\n+\treturn 1;\n+}\n+\n+static void report_refname_conflict(struct ref_entry *entry,\n+\t\t\t\t    const char *refname)\n+{\n+\terror(\"'%s' exists; cannot create '%s'\", entry->name, refname);\n }\n \n /*\n@@ -818,21 +813,85 @@ static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n  * oldrefname is non-NULL, ignore potential conflicts with oldrefname\n  * (e.g., because oldrefname is scheduled for deletion in the same\n  * operation).\n+ *\n+ * Two reference names conflict if one of them exactly matches the\n+ * leading components of the other; e.g., \"foo/bar\" conflicts with\n+ * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n+ * \"foo/barbados\".\n  */\n static int is_refname_available(const char *refname, const char *oldrefname,\n \t\t\t\tstruct ref_dir *dir)\n {\n-\tstruct name_conflict_cb data;\n-\tdata.refname = refname;\n-\tdata.oldrefname = oldrefname;\n-\tdata.conflicting_refname = NULL;\n+\tconst char *slash;\n+\tsize_t len;\n+\tint pos;\n+\tchar *dirname;\n \n-\tsort_ref_dir(dir);\n-\tif (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {\n-\t\terror(\"'%s' exists; cannot create '%s'\",\n-\t\t      data.conflicting_refname, refname);\n+\tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash, '/')) {\n+\t\t/*\n+\t\t * We are still at a leading dir of the refname; we are\n+\t\t * looking for a conflict with a leaf entry.\n+\t\t *\n+\t\t * If we find one, we still must make sure it is\n+\t\t * not \"oldrefname\".\n+\t\t */\n+\t\tpos = search_ref_dir(dir, refname, slash - refname);\n+\t\tif (pos >= 0) {\n+\t\t\tstruct ref_entry *entry = dir->entries[pos];\n+\t\t\tif (entry_matches(entry, oldrefname))\n+\t\t\t\treturn 1;\n+\t\t\treport_refname_conflict(entry, refname);\n+\t\t\treturn 0;\n+\t\t}\n+\n+\n+\t\t/*\n+\t\t * Otherwise, we can try to continue our search with\n+\t\t * the next component; if we come up empty, we know\n+\t\t * there is nothing under this whole prefix.\n+\t\t */\n+\t\tslash++;\n+\t\tpos = search_ref_dir(dir, refname, slash - refname);\n+\t\tif (pos < 0)\n+\t\t\treturn 1;\n+\n+\t\tdir = get_ref_dir(dir->entries[pos]);\n+\t}\n+\n+\t/*\n+\t * We are at the leaf of our refname; we want to\n+\t * make sure there are no directories which match it.\n+\t */\n+\tlen = strlen(refname);\n+\tdirname = xmallocz(len + 1);\n+\tsprintf(dirname, \"%s/\", refname);\n+\tpos = search_ref_dir(dir, dirname, len + 1);\n+\tfree(dirname);\n+\n+\t/*\n+\t * If we did find a directory, it might be a conflict.\n+\t * It is a problem if it has any ref that is not\n+\t * \"oldrefname\".\n+\t */\n+\tif (pos >= 0) {\n+\t\tstruct ref_entry *entry = dir->entries[pos];\n+\t\tstruct ref_dir *dir = get_ref_dir(entry);\n+\t\tstruct nonmatching_ref_data data;\n+\n+\t\tdata.skip = oldrefname;\n+\t\tsort_ref_dir(dir);\n+\t\tif (!do_for_each_entry_in_dir(dir, 0, nonmatching_ref_fn, &data))\n+\t\t\treturn 1;\n+\n+\t\treport_refname_conflict(data.found, refname);\n \t\treturn 0;\n \t}\n+\n+\t/*\n+\t * There is no point in searching for another leaf\n+\t * node which matches it; such an entry would be the\n+\t * ref we are looking for, not a conflict.\n+\t */\n \treturn 1;\n }\n \ndiff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh\nindex 1a2080e..3d5cb4c 100755\n--- a/t/t3210-pack-refs.sh\n+++ b/t/t3210-pack-refs.sh\n@@ -11,7 +11,9 @@ semantic is still the same.\n '\n . ./test-lib.sh\n \n-echo '[core] logallrefupdates = true' >>.git/config\n+test_expect_success 'enable reflogs' '\n+\tgit config core.logallrefupdates true\n+'\n \n test_expect_success \\\n     'prepare a trivial repository' \\\n@@ -151,4 +153,31 @@ test_expect_success 'delete ref while another dangling packed ref' '\n \ttest_cmp /dev/null result\n '\n \n+test_expect_success 'disable reflogs' '\n+\tgit config core.logallrefupdates false &&\n+\trm -rf .git/logs\n+'\n+\n+test_expect_success 'create packed foo/bar/baz branch' '\n+\tgit branch foo/bar/baz &&\n+\tgit pack-refs --all --prune &&\n+\ttest_path_is_missing .git/refs/heads/foo/bar/baz &&\n+\ttest_path_is_missing .git/logs/refs/heads/foo/bar/baz\n+'\n+\n+test_expect_success 'notice d/f conflict with existing directory' '\n+\ttest_must_fail git branch foo &&\n+\ttest_must_fail git branch foo/bar\n+'\n+\n+test_expect_success 'existing directory reports concrete ref' '\n+\ttest_must_fail git branch foo 2>stderr &&\n+\tgrep refs/heads/foo/bar/baz stderr\n+'\n+\n+test_expect_success 'notice d/f conflict with existing ref' '\n+\ttest_must_fail git branch foo/bar/baz/extra &&\n+\ttest_must_fail git branch foo/bar/baz/lots/of/extra/components\n+'\n+\n test_done\n-- \n2.1.0.373.g91ca799\n"},{"id":"249117","messageId":"20140910111155.GA14995@peff.net","threadId":"37530","inReplyTo":"20140910101730.GA12399@peff.net","subject":"[PATCH v2] refs: speed up is_refname_available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-10T11:11:55Z","receivedAt":"2014-09-10T11:11:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our filesystem ref storage does not allow D/F conflicts; so\nif \"refs/heads/a/b\" exists, we do not allow \"refs/heads/a\"\nto exist (and vice versa). This falls out naturally for\nloose refs, where the filesystem enforces the condition. But\nfor packed-refs, we have to make the check ourselves.\n\nWe do so by iterating over the entire packed-refs namespace\nand checking whether each name creates a conflict. If you\nhave a very large number of refs, this is quite inefficient,\nas you end up doing a large number of comparisons with\nuninteresting bits of the ref tree (e.g., we know that all\nof \"refs/tags\" is uninteresting in the example above, yet we\ncheck each entry in it).\n\nInstead, let's take advantage of the fact that we have the\npacked refs stored as a trie of ref_entry structs. We can\nfind each component of the proposed refname as we walk\nthrough the trie, checking for D/F conflicts as we go. For a\nrefname of depth N (i.e., 4 in the above example), we only\nhave to visit N nodes. And at each visit, we can binary\nsearch the M names at that level, for a total complexity of\nO(N lg M). (\"M\" is different at each level, of course, but\nwe can take the worst-case \"M\" as a bound).\n\nIn a pathological case of fetching 30,000 fresh refs into a\nrepository with 8.5 million refs, this dropped the time to\nrun \"git fetch\" from tens of minutes to ~30s.\n\nThis may also help smaller cases in which we check against\nloose refs (which we do when renaming a ref), as we may\navoid a disk access for unrelated loose directories.\n\nNote that the tests we add appear at first glance to be\nredundant with what is already in t3210. However, the early\ntests are not robust; they are run with reflogs turned on,\nmeaning that we are not actually testing\nis_refname_available at all! The operations will still fail\nbecause the reflogs will hit D/F conflicts in the\nfilesystem. To get a true test, we must turn off reflogs\n(but we don't want to do so for the entire script, because\nthe point of turning them on was to cover some other cases).\n\nReviewed-by: Michael Haggerty <mhagger@alum.mit.edu>\nSigned-off-by: Jeff King <peff@peff.net>\n---\nSorry for the quick v2; Michael and I crossed emails off-list, and I\nmissed some of his review. This version has some minor style and comment\nfixups.\n\n refs.c               | 122 +++++++++++++++++++++++++++++++++++++--------------\n t/t3210-pack-refs.sh |  31 ++++++++++++-\n 2 files changed, 120 insertions(+), 33 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 27927f2..eb2262a 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -779,37 +779,32 @@ static void prime_ref_dir(struct ref_dir *dir)\n \t\t\tprime_ref_dir(get_ref_dir(entry));\n \t}\n }\n-/*\n- * Return true iff refname1 and refname2 conflict with each other.\n- * Two reference names conflict if one of them exactly matches the\n- * leading components of the other; e.g., \"foo/bar\" conflicts with\n- * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n- * \"foo/barbados\".\n- */\n-static int names_conflict(const char *refname1, const char *refname2)\n+\n+static int entry_matches(struct ref_entry *entry, const char *refname)\n {\n-\tfor (; *refname1 && *refname1 == *refname2; refname1++, refname2++)\n-\t\t;\n-\treturn (*refname1 == '\\0' && *refname2 == '/')\n-\t\t|| (*refname1 == '/' && *refname2 == '\\0');\n+\treturn refname && !strcmp(entry->name, refname);\n }\n \n-struct name_conflict_cb {\n-\tconst char *refname;\n-\tconst char *oldrefname;\n-\tconst char *conflicting_refname;\n+struct nonmatching_ref_data {\n+\tconst char *skip;\n+\tstruct ref_entry *found;\n };\n \n-static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n+static int nonmatching_ref_fn(struct ref_entry *entry, void *vdata)\n {\n-\tstruct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;\n-\tif (data->oldrefname && !strcmp(data->oldrefname, entry->name))\n+\tstruct nonmatching_ref_data *data = vdata;\n+\n+\tif (entry_matches(entry, data->skip))\n \t\treturn 0;\n-\tif (names_conflict(data->refname, entry->name)) {\n-\t\tdata->conflicting_refname = entry->name;\n-\t\treturn 1;\n-\t}\n-\treturn 0;\n+\n+\tdata->found = entry;\n+\treturn 1;\n+}\n+\n+static void report_refname_conflict(struct ref_entry *entry,\n+\t\t\t\t    const char *refname)\n+{\n+\terror(\"'%s' exists; cannot create '%s'\", entry->name, refname);\n }\n \n /*\n@@ -818,21 +813,84 @@ static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n  * oldrefname is non-NULL, ignore potential conflicts with oldrefname\n  * (e.g., because oldrefname is scheduled for deletion in the same\n  * operation).\n+ *\n+ * Two reference names conflict if one of them exactly matches the\n+ * leading components of the other; e.g., \"foo/bar\" conflicts with\n+ * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n+ * \"foo/barbados\".\n  */\n static int is_refname_available(const char *refname, const char *oldrefname,\n \t\t\t\tstruct ref_dir *dir)\n {\n-\tstruct name_conflict_cb data;\n-\tdata.refname = refname;\n-\tdata.oldrefname = oldrefname;\n-\tdata.conflicting_refname = NULL;\n+\tconst char *slash;\n+\tsize_t len;\n+\tint pos;\n+\tchar *dirname;\n \n-\tsort_ref_dir(dir);\n-\tif (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {\n-\t\terror(\"'%s' exists; cannot create '%s'\",\n-\t\t      data.conflicting_refname, refname);\n+\tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {\n+\t\t/*\n+\t\t * We are still at a leading dir of the refname; we are\n+\t\t * looking for a conflict with a leaf entry.\n+\t\t *\n+\t\t * If we find one, we still must make sure it is\n+\t\t * not \"oldrefname\".\n+\t\t */\n+\t\tpos = search_ref_dir(dir, refname, slash - refname);\n+\t\tif (pos >= 0) {\n+\t\t\tstruct ref_entry *entry = dir->entries[pos];\n+\t\t\tif (entry_matches(entry, oldrefname))\n+\t\t\t\treturn 1;\n+\t\t\treport_refname_conflict(entry, refname);\n+\t\t\treturn 0;\n+\t\t}\n+\n+\n+\t\t/*\n+\t\t * Otherwise, we can try to continue our search with\n+\t\t * the next component; if we come up empty, we know\n+\t\t * there is nothing under this whole prefix.\n+\t\t */\n+\t\tpos = search_ref_dir(dir, refname, slash + 1 - refname);\n+\t\tif (pos < 0)\n+\t\t\treturn 1;\n+\n+\t\tdir = get_ref_dir(dir->entries[pos]);\n+\t}\n+\n+\t/*\n+\t * We are at the leaf of our refname; we want to\n+\t * make sure there are no directories which match it.\n+\t */\n+\tlen = strlen(refname);\n+\tdirname = xmallocz(len + 1);\n+\tsprintf(dirname, \"%s/\", refname);\n+\tpos = search_ref_dir(dir, dirname, len + 1);\n+\tfree(dirname);\n+\n+\tif (pos >= 0) {\n+\t\t/*\n+\t\t * We found a directory named \"refname\". It is a\n+\t\t * problem iff it contains any ref that is not\n+\t\t * \"oldrefname\".\n+\t\t */\n+\t\tstruct ref_entry *entry = dir->entries[pos];\n+\t\tstruct ref_dir *dir = get_ref_dir(entry);\n+\t\tstruct nonmatching_ref_data data;\n+\n+\t\tdata.skip = oldrefname;\n+\t\tsort_ref_dir(dir);\n+\t\tif (!do_for_each_entry_in_dir(dir, 0, nonmatching_ref_fn, &data))\n+\t\t\treturn 1;\n+\n+\t\treport_refname_conflict(data.found, refname);\n \t\treturn 0;\n \t}\n+\n+\t/*\n+\t * There is no point in searching for another leaf\n+\t * node which matches it; such an entry would be the\n+\t * ref we are looking for, not a conflict.\n+\t */\n \treturn 1;\n }\n \ndiff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh\nindex 1a2080e..3d5cb4c 100755\n--- a/t/t3210-pack-refs.sh\n+++ b/t/t3210-pack-refs.sh\n@@ -11,7 +11,9 @@ semantic is still the same.\n '\n . ./test-lib.sh\n \n-echo '[core] logallrefupdates = true' >>.git/config\n+test_expect_success 'enable reflogs' '\n+\tgit config core.logallrefupdates true\n+'\n \n test_expect_success \\\n     'prepare a trivial repository' \\\n@@ -151,4 +153,31 @@ test_expect_success 'delete ref while another dangling packed ref' '\n \ttest_cmp /dev/null result\n '\n \n+test_expect_success 'disable reflogs' '\n+\tgit config core.logallrefupdates false &&\n+\trm -rf .git/logs\n+'\n+\n+test_expect_success 'create packed foo/bar/baz branch' '\n+\tgit branch foo/bar/baz &&\n+\tgit pack-refs --all --prune &&\n+\ttest_path_is_missing .git/refs/heads/foo/bar/baz &&\n+\ttest_path_is_missing .git/logs/refs/heads/foo/bar/baz\n+'\n+\n+test_expect_success 'notice d/f conflict with existing directory' '\n+\ttest_must_fail git branch foo &&\n+\ttest_must_fail git branch foo/bar\n+'\n+\n+test_expect_success 'existing directory reports concrete ref' '\n+\ttest_must_fail git branch foo 2>stderr &&\n+\tgrep refs/heads/foo/bar/baz stderr\n+'\n+\n+test_expect_success 'notice d/f conflict with existing ref' '\n+\ttest_must_fail git branch foo/bar/baz/extra &&\n+\ttest_must_fail git branch foo/bar/baz/lots/of/extra/components\n+'\n+\n test_done\n-- \n2.1.0.373.g91ca799\n"},{"id":"249157","messageId":"xmqqk35bf764.fsf@gitster.dls.corp.google.com","threadId":"37530","inReplyTo":"20140910111155.GA14995@peff.net","subject":"Re: [PATCH v2] refs: speed up is_refname_available","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-09-10T22:21:39Z","receivedAt":"2014-09-10T22:21:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ...\n> Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> Sorry for the quick v2; Michael and I crossed emails off-list, and I\n> missed some of his review. This version has some minor style and comment\n> fixups.\n\nLooks sensible from a cursory read, but it conflicts heavily with\n54e696fc (refs.c: pass a skip list to name_conflict_fn, 2014-07-16)\nwhich is queued early on 'pu', and I am definitely not in the\nbusiness of re-designing that huge topic myself.\n\nI am tempted to\n\n - merge rs/ref-transaction-1 to 'master' as planned;\n\n - drop other rs/ref-transaction* topics temporarily, expecting them\n   to be rerolled like rs/ref-transaction-1 was done recently;\n\n - ask you three (or four, counting Duy as well) who seem to want to\n   touch refs to coordinate among yourselves a bit better next time\n   ;-)\n\nThanks.\n\n>\n>  refs.c               | 122 +++++++++++++++++++++++++++++++++++++--------------\n>  t/t3210-pack-refs.sh |  31 ++++++++++++-\n>  2 files changed, 120 insertions(+), 33 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index 27927f2..eb2262a 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -779,37 +779,32 @@ static void prime_ref_dir(struct ref_dir *dir)\n>  \t\t\tprime_ref_dir(get_ref_dir(entry));\n>  \t}\n>  }\n> -/*\n> - * Return true iff refname1 and refname2 conflict with each other.\n> - * Two reference names conflict if one of them exactly matches the\n> - * leading components of the other; e.g., \"foo/bar\" conflicts with\n> - * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n> - * \"foo/barbados\".\n> - */\n> -static int names_conflict(const char *refname1, const char *refname2)\n> +\n> +static int entry_matches(struct ref_entry *entry, const char *refname)\n>  {\n> -\tfor (; *refname1 && *refname1 == *refname2; refname1++, refname2++)\n> -\t\t;\n> -\treturn (*refname1 == '\\0' && *refname2 == '/')\n> -\t\t|| (*refname1 == '/' && *refname2 == '\\0');\n> +\treturn refname && !strcmp(entry->name, refname);\n>  }\n>  \n> -struct name_conflict_cb {\n> -\tconst char *refname;\n> -\tconst char *oldrefname;\n> -\tconst char *conflicting_refname;\n> +struct nonmatching_ref_data {\n> +\tconst char *skip;\n> +\tstruct ref_entry *found;\n>  };\n>  \n> -static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n> +static int nonmatching_ref_fn(struct ref_entry *entry, void *vdata)\n>  {\n> -\tstruct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;\n> -\tif (data->oldrefname && !strcmp(data->oldrefname, entry->name))\n> +\tstruct nonmatching_ref_data *data = vdata;\n> +\n> +\tif (entry_matches(entry, data->skip))\n>  \t\treturn 0;\n> -\tif (names_conflict(data->refname, entry->name)) {\n> -\t\tdata->conflicting_refname = entry->name;\n> -\t\treturn 1;\n> -\t}\n> -\treturn 0;\n> +\n> +\tdata->found = entry;\n> +\treturn 1;\n> +}\n> +\n> +static void report_refname_conflict(struct ref_entry *entry,\n> +\t\t\t\t    const char *refname)\n> +{\n> +\terror(\"'%s' exists; cannot create '%s'\", entry->name, refname);\n>  }\n>  \n>  /*\n> @@ -818,21 +813,84 @@ static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n>   * oldrefname is non-NULL, ignore potential conflicts with oldrefname\n>   * (e.g., because oldrefname is scheduled for deletion in the same\n>   * operation).\n> + *\n> + * Two reference names conflict if one of them exactly matches the\n> + * leading components of the other; e.g., \"foo/bar\" conflicts with\n> + * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n> + * \"foo/barbados\".\n>   */\n>  static int is_refname_available(const char *refname, const char *oldrefname,\n>  \t\t\t\tstruct ref_dir *dir)\n>  {\n> -\tstruct name_conflict_cb data;\n> -\tdata.refname = refname;\n> -\tdata.oldrefname = oldrefname;\n> -\tdata.conflicting_refname = NULL;\n> +\tconst char *slash;\n> +\tsize_t len;\n> +\tint pos;\n> +\tchar *dirname;\n>  \n> -\tsort_ref_dir(dir);\n> -\tif (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {\n> -\t\terror(\"'%s' exists; cannot create '%s'\",\n> -\t\t      data.conflicting_refname, refname);\n> +\tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {\n> +\t\t/*\n> +\t\t * We are still at a leading dir of the refname; we are\n> +\t\t * looking for a conflict with a leaf entry.\n> +\t\t *\n> +\t\t * If we find one, we still must make sure it is\n> +\t\t * not \"oldrefname\".\n> +\t\t */\n> +\t\tpos = search_ref_dir(dir, refname, slash - refname);\n> +\t\tif (pos >= 0) {\n> +\t\t\tstruct ref_entry *entry = dir->entries[pos];\n> +\t\t\tif (entry_matches(entry, oldrefname))\n> +\t\t\t\treturn 1;\n> +\t\t\treport_refname_conflict(entry, refname);\n> +\t\t\treturn 0;\n> +\t\t}\n> +\n> +\n> +\t\t/*\n> +\t\t * Otherwise, we can try to continue our search with\n> +\t\t * the next component; if we come up empty, we know\n> +\t\t * there is nothing under this whole prefix.\n> +\t\t */\n> +\t\tpos = search_ref_dir(dir, refname, slash + 1 - refname);\n> +\t\tif (pos < 0)\n> +\t\t\treturn 1;\n> +\n> +\t\tdir = get_ref_dir(dir->entries[pos]);\n> +\t}\n> +\n> +\t/*\n> +\t * We are at the leaf of our refname; we want to\n> +\t * make sure there are no directories which match it.\n> +\t */\n> +\tlen = strlen(refname);\n> +\tdirname = xmallocz(len + 1);\n> +\tsprintf(dirname, \"%s/\", refname);\n> +\tpos = search_ref_dir(dir, dirname, len + 1);\n> +\tfree(dirname);\n> +\n> +\tif (pos >= 0) {\n> +\t\t/*\n> +\t\t * We found a directory named \"refname\". It is a\n> +\t\t * problem iff it contains any ref that is not\n> +\t\t * \"oldrefname\".\n> +\t\t */\n> +\t\tstruct ref_entry *entry = dir->entries[pos];\n> +\t\tstruct ref_dir *dir = get_ref_dir(entry);\n> +\t\tstruct nonmatching_ref_data data;\n> +\n> +\t\tdata.skip = oldrefname;\n> +\t\tsort_ref_dir(dir);\n> +\t\tif (!do_for_each_entry_in_dir(dir, 0, nonmatching_ref_fn, &data))\n> +\t\t\treturn 1;\n> +\n> +\t\treport_refname_conflict(data.found, refname);\n>  \t\treturn 0;\n>  \t}\n> +\n> +\t/*\n> +\t * There is no point in searching for another leaf\n> +\t * node which matches it; such an entry would be the\n> +\t * ref we are looking for, not a conflict.\n> +\t */\n>  \treturn 1;\n>  }\n>  \n> diff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh\n> index 1a2080e..3d5cb4c 100755\n> --- a/t/t3210-pack-refs.sh\n> +++ b/t/t3210-pack-refs.sh\n> @@ -11,7 +11,9 @@ semantic is still the same.\n>  '\n>  . ./test-lib.sh\n>  \n> -echo '[core] logallrefupdates = true' >>.git/config\n> +test_expect_success 'enable reflogs' '\n> +\tgit config core.logallrefupdates true\n> +'\n>  \n>  test_expect_success \\\n>      'prepare a trivial repository' \\\n> @@ -151,4 +153,31 @@ test_expect_success 'delete ref while another dangling packed ref' '\n>  \ttest_cmp /dev/null result\n>  '\n>  \n> +test_expect_success 'disable reflogs' '\n> +\tgit config core.logallrefupdates false &&\n> +\trm -rf .git/logs\n> +'\n> +\n> +test_expect_success 'create packed foo/bar/baz branch' '\n> +\tgit branch foo/bar/baz &&\n> +\tgit pack-refs --all --prune &&\n> +\ttest_path_is_missing .git/refs/heads/foo/bar/baz &&\n> +\ttest_path_is_missing .git/logs/refs/heads/foo/bar/baz\n> +'\n> +\n> +test_expect_success 'notice d/f conflict with existing directory' '\n> +\ttest_must_fail git branch foo &&\n> +\ttest_must_fail git branch foo/bar\n> +'\n> +\n> +test_expect_success 'existing directory reports concrete ref' '\n> +\ttest_must_fail git branch foo 2>stderr &&\n> +\tgrep refs/heads/foo/bar/baz stderr\n> +'\n> +\n> +test_expect_success 'notice d/f conflict with existing ref' '\n> +\ttest_must_fail git branch foo/bar/baz/extra &&\n> +\ttest_must_fail git branch foo/bar/baz/lots/of/extra/components\n> +'\n> +\n>  test_done\n"},{"id":"249158","messageId":"xmqqiokvf75i.fsf@gitster.dls.corp.google.com","threadId":"37530","inReplyTo":"20140910111155.GA14995@peff.net","subject":"Re: [PATCH v2] refs: speed up is_refname_available","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-09-10T22:22:01Z","receivedAt":"2014-09-10T22:22:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ...\n> Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> Sorry for the quick v2; Michael and I crossed emails off-list, and I\n> missed some of his review. This version has some minor style and comment\n> fixups.\n\nLooks sensible from a cursory read, but it conflicts heavily with\n54e696fc (refs.c: pass a skip list to name_conflict_fn, 2014-07-16)\nwhich is queued early on 'pu', and I am definitely not in the\nbusiness of re-designing that huge topic myself.\n\nI am tempted to\n\n - merge rs/ref-transaction-1 to 'master' as planned;\n\n - drop other rs/ref-transaction* topics temporarily, expecting them\n   to be rerolled like rs/ref-transaction-1 was done recently;\n\n - try merging this and see how it goes; and\n\n - ask you three (or four, counting Duy as well) who seem to want to\n   touch refs to coordinate among yourselves a bit better next time\n   ;-)\n\nThanks.\n\n>\n>  refs.c               | 122 +++++++++++++++++++++++++++++++++++++--------------\n>  t/t3210-pack-refs.sh |  31 ++++++++++++-\n>  2 files changed, 120 insertions(+), 33 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index 27927f2..eb2262a 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -779,37 +779,32 @@ static void prime_ref_dir(struct ref_dir *dir)\n>  \t\t\tprime_ref_dir(get_ref_dir(entry));\n>  \t}\n>  }\n> -/*\n> - * Return true iff refname1 and refname2 conflict with each other.\n> - * Two reference names conflict if one of them exactly matches the\n> - * leading components of the other; e.g., \"foo/bar\" conflicts with\n> - * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n> - * \"foo/barbados\".\n> - */\n> -static int names_conflict(const char *refname1, const char *refname2)\n> +\n> +static int entry_matches(struct ref_entry *entry, const char *refname)\n>  {\n> -\tfor (; *refname1 && *refname1 == *refname2; refname1++, refname2++)\n> -\t\t;\n> -\treturn (*refname1 == '\\0' && *refname2 == '/')\n> -\t\t|| (*refname1 == '/' && *refname2 == '\\0');\n> +\treturn refname && !strcmp(entry->name, refname);\n>  }\n>  \n> -struct name_conflict_cb {\n> -\tconst char *refname;\n> -\tconst char *oldrefname;\n> -\tconst char *conflicting_refname;\n> +struct nonmatching_ref_data {\n> +\tconst char *skip;\n> +\tstruct ref_entry *found;\n>  };\n>  \n> -static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n> +static int nonmatching_ref_fn(struct ref_entry *entry, void *vdata)\n>  {\n> -\tstruct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;\n> -\tif (data->oldrefname && !strcmp(data->oldrefname, entry->name))\n> +\tstruct nonmatching_ref_data *data = vdata;\n> +\n> +\tif (entry_matches(entry, data->skip))\n>  \t\treturn 0;\n> -\tif (names_conflict(data->refname, entry->name)) {\n> -\t\tdata->conflicting_refname = entry->name;\n> -\t\treturn 1;\n> -\t}\n> -\treturn 0;\n> +\n> +\tdata->found = entry;\n> +\treturn 1;\n> +}\n> +\n> +static void report_refname_conflict(struct ref_entry *entry,\n> +\t\t\t\t    const char *refname)\n> +{\n> +\terror(\"'%s' exists; cannot create '%s'\", entry->name, refname);\n>  }\n>  \n>  /*\n> @@ -818,21 +813,84 @@ static int name_conflict_fn(struct ref_entry *entry, void *cb_data)\n>   * oldrefname is non-NULL, ignore potential conflicts with oldrefname\n>   * (e.g., because oldrefname is scheduled for deletion in the same\n>   * operation).\n> + *\n> + * Two reference names conflict if one of them exactly matches the\n> + * leading components of the other; e.g., \"foo/bar\" conflicts with\n> + * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n> + * \"foo/barbados\".\n>   */\n>  static int is_refname_available(const char *refname, const char *oldrefname,\n>  \t\t\t\tstruct ref_dir *dir)\n>  {\n> -\tstruct name_conflict_cb data;\n> -\tdata.refname = refname;\n> -\tdata.oldrefname = oldrefname;\n> -\tdata.conflicting_refname = NULL;\n> +\tconst char *slash;\n> +\tsize_t len;\n> +\tint pos;\n> +\tchar *dirname;\n>  \n> -\tsort_ref_dir(dir);\n> -\tif (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {\n> -\t\terror(\"'%s' exists; cannot create '%s'\",\n> -\t\t      data.conflicting_refname, refname);\n> +\tfor (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {\n> +\t\t/*\n> +\t\t * We are still at a leading dir of the refname; we are\n> +\t\t * looking for a conflict with a leaf entry.\n> +\t\t *\n> +\t\t * If we find one, we still must make sure it is\n> +\t\t * not \"oldrefname\".\n> +\t\t */\n> +\t\tpos = search_ref_dir(dir, refname, slash - refname);\n> +\t\tif (pos >= 0) {\n> +\t\t\tstruct ref_entry *entry = dir->entries[pos];\n> +\t\t\tif (entry_matches(entry, oldrefname))\n> +\t\t\t\treturn 1;\n> +\t\t\treport_refname_conflict(entry, refname);\n> +\t\t\treturn 0;\n> +\t\t}\n> +\n> +\n> +\t\t/*\n> +\t\t * Otherwise, we can try to continue our search with\n> +\t\t * the next component; if we come up empty, we know\n> +\t\t * there is nothing under this whole prefix.\n> +\t\t */\n> +\t\tpos = search_ref_dir(dir, refname, slash + 1 - refname);\n> +\t\tif (pos < 0)\n> +\t\t\treturn 1;\n> +\n> +\t\tdir = get_ref_dir(dir->entries[pos]);\n> +\t}\n> +\n> +\t/*\n> +\t * We are at the leaf of our refname; we want to\n> +\t * make sure there are no directories which match it.\n> +\t */\n> +\tlen = strlen(refname);\n> +\tdirname = xmallocz(len + 1);\n> +\tsprintf(dirname, \"%s/\", refname);\n> +\tpos = search_ref_dir(dir, dirname, len + 1);\n> +\tfree(dirname);\n> +\n> +\tif (pos >= 0) {\n> +\t\t/*\n> +\t\t * We found a directory named \"refname\". It is a\n> +\t\t * problem iff it contains any ref that is not\n> +\t\t * \"oldrefname\".\n> +\t\t */\n> +\t\tstruct ref_entry *entry = dir->entries[pos];\n> +\t\tstruct ref_dir *dir = get_ref_dir(entry);\n> +\t\tstruct nonmatching_ref_data data;\n> +\n> +\t\tdata.skip = oldrefname;\n> +\t\tsort_ref_dir(dir);\n> +\t\tif (!do_for_each_entry_in_dir(dir, 0, nonmatching_ref_fn, &data))\n> +\t\t\treturn 1;\n> +\n> +\t\treport_refname_conflict(data.found, refname);\n>  \t\treturn 0;\n>  \t}\n> +\n> +\t/*\n> +\t * There is no point in searching for another leaf\n> +\t * node which matches it; such an entry would be the\n> +\t * ref we are looking for, not a conflict.\n> +\t */\n>  \treturn 1;\n>  }\n>  \n> diff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh\n> index 1a2080e..3d5cb4c 100755\n> --- a/t/t3210-pack-refs.sh\n> +++ b/t/t3210-pack-refs.sh\n> @@ -11,7 +11,9 @@ semantic is still the same.\n>  '\n>  . ./test-lib.sh\n>  \n> -echo '[core] logallrefupdates = true' >>.git/config\n> +test_expect_success 'enable reflogs' '\n> +\tgit config core.logallrefupdates true\n> +'\n>  \n>  test_expect_success \\\n>      'prepare a trivial repository' \\\n> @@ -151,4 +153,31 @@ test_expect_success 'delete ref while another dangling packed ref' '\n>  \ttest_cmp /dev/null result\n>  '\n>  \n> +test_expect_success 'disable reflogs' '\n> +\tgit config core.logallrefupdates false &&\n> +\trm -rf .git/logs\n> +'\n> +\n> +test_expect_success 'create packed foo/bar/baz branch' '\n> +\tgit branch foo/bar/baz &&\n> +\tgit pack-refs --all --prune &&\n> +\ttest_path_is_missing .git/refs/heads/foo/bar/baz &&\n> +\ttest_path_is_missing .git/logs/refs/heads/foo/bar/baz\n> +'\n> +\n> +test_expect_success 'notice d/f conflict with existing directory' '\n> +\ttest_must_fail git branch foo &&\n> +\ttest_must_fail git branch foo/bar\n> +'\n> +\n> +test_expect_success 'existing directory reports concrete ref' '\n> +\ttest_must_fail git branch foo 2>stderr &&\n> +\tgrep refs/heads/foo/bar/baz stderr\n> +'\n> +\n> +test_expect_success 'notice d/f conflict with existing ref' '\n> +\ttest_must_fail git branch foo/bar/baz/extra &&\n> +\ttest_must_fail git branch foo/bar/baz/lots/of/extra/components\n> +'\n> +\n>  test_done\n"},{"id":"249194","messageId":"20140911013903.GA5525@peff.net","threadId":"37530","inReplyTo":"xmqqk35bf764.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] refs: speed up is_refname_available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-11T01:39:03Z","receivedAt":"2014-09-11T01:39:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 10, 2014 at 03:21:39PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > ...\n> > Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>\n> > Signed-off-by: Jeff King <peff@peff.net>\n> > ---\n> > Sorry for the quick v2; Michael and I crossed emails off-list, and I\n> > missed some of his review. This version has some minor style and comment\n> > fixups.\n> \n> Looks sensible from a cursory read, but it conflicts heavily with\n> 54e696fc (refs.c: pass a skip list to name_conflict_fn, 2014-07-16)\n> which is queued early on 'pu', and I am definitely not in the\n> business of re-designing that huge topic myself.\n\nDid you miss the part in v1 where I pointed to a tree with a proposed\nresolution? :)\n\nI am also happy to rebase if the other bits are coming to master soon.\n\n-Peff\n"},{"id":"249237","messageId":"xmqqy4tqdr1r.fsf@gitster.dls.corp.google.com","threadId":"37530","inReplyTo":"20140910101730.GA12399@peff.net","subject":"Re: [PATCH] refs: speed up is_refname_available","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-09-11T17:07:28Z","receivedAt":"2014-09-11T17:07:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> This has a fairly straightforward conflict with the ref-transaction\n> stuff in pu. The \"oldrefname\" parameter to is_refname_available became a\n> list of items;\n\nHmph, the trouble I had while reading the conflicts was about the\nnew \"we skip these when repacking\", not \"oldrefname\".\n\nWill check your suggested resolution later today.  Thanks.\n"},{"id":"249244","messageId":"20140911183143.GB18382@peff.net","threadId":"37530","inReplyTo":"xmqqy4tqdr1r.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] refs: speed up is_refname_available","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-11T18:31:43Z","receivedAt":"2014-09-11T18:31:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 11, 2014 at 10:07:28AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > This has a fairly straightforward conflict with the ref-transaction\n> > stuff in pu. The \"oldrefname\" parameter to is_refname_available became a\n> > list of items;\n> \n> Hmph, the trouble I had while reading the conflicts was about the\n> new \"we skip these when repacking\", not \"oldrefname\".\n> \n> Will check your suggested resolution later today.  Thanks.\n\nI didn't see any conflict related to repacking. If I am reading\n54e696fc433 correctly, the single \"oldrefname\" became a list \"skip\" in\nthe name_conflict_* code. My series dropped name_conflict_*, but gave a\nsimilar adaptation to the replacement.\n\nThe \"skip while repacking\" code is repack_without_refs, but I don't\nthink I touched anything that conflicted there.\n\n-Peff\n"}]}