From cbe73331812ed0ac3c3b680ab3aab4e6d22a98ad Mon Sep 17 00:00:00 2001 From: Jeff King Date: Wed, 10 Sep 2014 07:11:55 -0400 Subject: refs: speed up is_refname_available Our filesystem ref storage does not allow D/F conflicts; so if "refs/heads/a/b" exists, we do not allow "refs/heads/a" to exist (and vice versa). This falls out naturally for loose refs, where the filesystem enforces the condition. But for packed-refs, we have to make the check ourselves. We do so by iterating over the entire packed-refs namespace and checking whether each name creates a conflict. If you have a very large number of refs, this is quite inefficient, as you end up doing a large number of comparisons with uninteresting bits of the ref tree (e.g., we know that all of "refs/tags" is uninteresting in the example above, yet we check each entry in it). Instead, let's take advantage of the fact that we have the packed refs stored as a trie of ref_entry structs. We can find each component of the proposed refname as we walk through the trie, checking for D/F conflicts as we go. For a refname of depth N (i.e., 4 in the above example), we only have to visit N nodes. And at each visit, we can binary search the M names at that level, for a total complexity of O(N lg M). ("M" is different at each level, of course, but we can take the worst-case "M" as a bound). In a pathological case of fetching 30,000 fresh refs into a repository with 8.5 million refs, this dropped the time to run "git fetch" from tens of minutes to ~30s. This may also help smaller cases in which we check against loose refs (which we do when renaming a ref), as we may avoid a disk access for unrelated loose directories. Note that the tests we add appear at first glance to be redundant with what is already in t3210. However, the early tests are not robust; they are run with reflogs turned on, meaning that we are not actually testing is_refname_available at all! The operations will still fail because the reflogs will hit D/F conflicts in the filesystem. To get a true test, we must turn off reflogs (but we don't want to do so for the entire script, because the point of turning them on was to cover some other cases). Reviewed-by: Michael Haggerty Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- refs.c | 122 ++++++++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 90 insertions(+), 32 deletions(-) (limited to 'refs.c') diff --git a/refs.c b/refs.c index 27927f231..eb2262ac2 100644 --- a/refs.c +++ b/refs.c @@ -779,37 +779,32 @@ static void prime_ref_dir(struct ref_dir *dir) prime_ref_dir(get_ref_dir(entry)); } } -/* - * Return true iff refname1 and refname2 conflict with each other. - * Two reference names conflict if one of them exactly matches the - * leading components of the other; e.g., "foo/bar" conflicts with - * both "foo" and with "foo/bar/baz" but not with "foo/bar" or - * "foo/barbados". - */ -static int names_conflict(const char *refname1, const char *refname2) + +static int entry_matches(struct ref_entry *entry, const char *refname) { - for (; *refname1 && *refname1 == *refname2; refname1++, refname2++) - ; - return (*refname1 == '\0' && *refname2 == '/') - || (*refname1 == '/' && *refname2 == '\0'); + return refname && !strcmp(entry->name, refname); } -struct name_conflict_cb { - const char *refname; - const char *oldrefname; - const char *conflicting_refname; +struct nonmatching_ref_data { + const char *skip; + struct ref_entry *found; }; -static int name_conflict_fn(struct ref_entry *entry, void *cb_data) +static int nonmatching_ref_fn(struct ref_entry *entry, void *vdata) { - struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data; - if (data->oldrefname && !strcmp(data->oldrefname, entry->name)) + struct nonmatching_ref_data *data = vdata; + + if (entry_matches(entry, data->skip)) return 0; - if (names_conflict(data->refname, entry->name)) { - data->conflicting_refname = entry->name; - return 1; - } - return 0; + + data->found = entry; + return 1; +} + +static void report_refname_conflict(struct ref_entry *entry, + const char *refname) +{ + error("'%s' exists; cannot create '%s'", entry->name, refname); } /* @@ -818,21 +813,84 @@ static int name_conflict_fn(struct ref_entry *entry, void *cb_data) * oldrefname is non-NULL, ignore potential conflicts with oldrefname * (e.g., because oldrefname is scheduled for deletion in the same * operation). + * + * Two reference names conflict if one of them exactly matches the + * leading components of the other; e.g., "foo/bar" conflicts with + * both "foo" and with "foo/bar/baz" but not with "foo/bar" or + * "foo/barbados". */ static int is_refname_available(const char *refname, const char *oldrefname, struct ref_dir *dir) { - struct name_conflict_cb data; - data.refname = refname; - data.oldrefname = oldrefname; - data.conflicting_refname = NULL; + const char *slash; + size_t len; + int pos; + char *dirname; - sort_ref_dir(dir); - if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) { - error("'%s' exists; cannot create '%s'", - data.conflicting_refname, refname); + for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) { + /* + * We are still at a leading dir of the refname; we are + * looking for a conflict with a leaf entry. + * + * If we find one, we still must make sure it is + * not "oldrefname". + */ + pos = search_ref_dir(dir, refname, slash - refname); + if (pos >= 0) { + struct ref_entry *entry = dir->entries[pos]; + if (entry_matches(entry, oldrefname)) + return 1; + report_refname_conflict(entry, refname); + return 0; + } + + + /* + * Otherwise, we can try to continue our search with + * the next component; if we come up empty, we know + * there is nothing under this whole prefix. + */ + pos = search_ref_dir(dir, refname, slash + 1 - refname); + if (pos < 0) + return 1; + + dir = get_ref_dir(dir->entries[pos]); + } + + /* + * We are at the leaf of our refname; we want to + * make sure there are no directories which match it. + */ + len = strlen(refname); + dirname = xmallocz(len + 1); + sprintf(dirname, "%s/", refname); + pos = search_ref_dir(dir, dirname, len + 1); + free(dirname); + + if (pos >= 0) { + /* + * We found a directory named "refname". It is a + * problem iff it contains any ref that is not + * "oldrefname". + */ + struct ref_entry *entry = dir->entries[pos]; + struct ref_dir *dir = get_ref_dir(entry); + struct nonmatching_ref_data data; + + data.skip = oldrefname; + sort_ref_dir(dir); + if (!do_for_each_entry_in_dir(dir, 0, nonmatching_ref_fn, &data)) + return 1; + + report_refname_conflict(data.found, refname); return 0; } + + /* + * There is no point in searching for another leaf + * node which matches it; such an entry would be the + * ref we are looking for, not a conflict. + */ return 1; } -- cgit v1.2.1