refs: implement skip lists for packed backend
PATCH v5 1/16 refs.c: rename `ref_filter`
In reply to Taylor BlauFrom: Jeff King <[email protected]>
The refs machinery has its own implementation of a ref_filter (used by for-each-ref), which is distinct from the ref-filter.h API (also used by for-each-ref, among other things).
Rename the one within refs.c to more clearly indicate its purpose.
--- refs.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-)
refs.c +8 -7
@@ -377,8 +377,8 @@ char *resolve_refdup(const char *refname, int resolve_flags, oid, flags); } -/* The argument to filter_refs */ -struct ref_filter { +/* The argument to for_each_filter_refs */ +struct for_each_ref_filter {const char *pattern;const char *prefix;each_ref_fn *fn;
@@ -411,10 +411,11 @@ int ref_exists(const char *refname)return refs_ref_exists (get_main_ref_store (the_repository), refname); } -static int filter_refs (const char *refname,const struct object_id *oid, -int flags,void *data) +static int for_each_filter_refs (const char *refname, +const struct object_id *oid, +int flags,void *data) { -struct ref_filter *filter = (struct ref_filter *)data; +struct for_each_ref_filter *filter = data;if (wildmatch (filter->pattern, refname,0 ))return 0 ;
@@ -571,7 +572,7 @@ int for_each_glob_ref_in(each_ref_fn fn, const char *pattern, const char *prefix, void *cb_data) { struct strbuf real_pattern = STRBUF_INIT; -struct ref_filter filter; +struct for_each_ref_filter filter;int ret;if (!prefix && !starts_with (pattern,"refs/" ))
@@ -591,7 +592,7 @@ int for_each_glob_ref_in(each_ref_fn fn, const char *pattern, filter.prefix = prefix; filter.fn = fn; filter.cb_data = cb_data; - ret =for_each_ref (filter_refs, &filter); + ret =for_each_ref (for_each_filter_refs, &filter);strbuf_release (&real_pattern);return ret;
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 2/16 ref-filter.h: provide `REF_FILTER_INIT`
In reply to Taylor BlauFrom: Jeff King <[email protected]>
Provide a sane initialization value for struct ref_filter, which in a subsequent patch will be used to initialize a new field.
In the meantime, ensure that the ref_filter struct used in the test-helper's cmd__reach() is zero-initialized. The lack of initialization is OK, since commit_contains() only looks at the single with_commit_tag_algo field that *is* initialized directly above.
So this does not fix a bug, but rather prevents one from biting us in the future.
--- builtin/branch.c | 3 +-- builtin/for-each-ref.c | 3 +-- builtin/tag.c | 3 +-- ref-filter.h | 3 +++ t/helper/test-reach.c | 2 +- 5 files changed, 7 insertions(+), 7 deletions(-)
builtin/branch.c +1 -2
@@ -702,7 +702,7 @@ int cmd_branch(int argc, const char **argv, const char *prefix)int reflog =0 , quiet =0 , icase =0 , force =0 , recurse_submodules_explicit =0 ;enum branch_track track; -struct ref_filter filter; +struct ref_filter filter =REF_FILTER_INIT ;static struct ref_sorting *sorting;struct string_list sorting_options =STRING_LIST_INIT_DUP ;struct ref_format format =REF_FORMAT_INIT ;
@@ -760,7 +760,6 @@ int cmd_branch(int argc, const char **argv, const char *prefix)setup_ref_filter_porcelain_msg (); -memset (&filter,0 ,sizeof (filter)); filter.kind =FILTER_REFS_BRANCHES ; filter.abbrev =-1 ;
builtin/for-each-ref.c +1 -2
@@ -24,7 +24,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)struct string_list sorting_options =STRING_LIST_INIT_DUP ;int maxcount =0 , icase =0 , omit_empty =0 ;struct ref_array array; -struct ref_filter filter; +struct ref_filter filter =REF_FILTER_INIT ;struct ref_format format =REF_FORMAT_INIT ;struct strbuf output =STRBUF_INIT ;struct strbuf err =STRBUF_INIT ;
@@ -61,7 +61,6 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix) };memset (&array,0 ,sizeof (array)); -memset (&filter,0 ,sizeof (filter)); format.format ="%(objectname) %(objecttype)\t%(refname)" ;
builtin/tag.c +1 -2
@@ -445,7 +445,7 @@ int cmd_tag(int argc, const char **argv, const char *prefix)struct msg_arg msg = { .buf =STRBUF_INIT };struct ref_transaction *transaction;struct strbuf err =STRBUF_INIT ; -struct ref_filter filter; +struct ref_filter filter =REF_FILTER_INIT ;struct ref_sorting *sorting;struct string_list sorting_options =STRING_LIST_INIT_DUP ;struct ref_format format =REF_FORMAT_INIT ;
@@ -504,7 +504,6 @@ int cmd_tag(int argc, const char **argv, const char *prefix)git_config (git_tag_config, &sorting_options);memset (&opt,0 ,sizeof (opt)); -memset (&filter,0 ,sizeof (filter)); filter.lines =-1 ; opt.sign =-1 ;
ref-filter.h +3 -0
@@ -92,6 +92,9 @@ struct ref_format {struct string_list bases; }; +#define REF_FILTER_INIT { \ + .points_at = OID_ARRAY_INIT, \ +}#define REF_FORMAT_INIT { \ .use_color = -1, \ .bases = STRING_LIST_INIT_DUP, \
t/helper/test-reach.c +1 -1
@@ -139,7 +139,7 @@ int cmd__reach(int ac, const char **av)printf ("%s(X,_,_,0,0):%d\n" , av[1 ],can_all_from_reach_with_flag (&X_obj,2 ,4 ,0 ,0 )); }else if (!strcmp (av[1 ],"commit_contains" )) { -struct ref_filter filter; +struct ref_filter filter =REF_FILTER_INIT ;struct contains_cache cache;init_contains_cache (&cache);
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 3/16 ref-filter: clear reachable list pointers after freeing
In reply to Taylor BlauFrom: Jeff King <[email protected]>
In reach_filter(), we pop all commits from the reachable lists, leaving them empty. But because we're operating on a list pointer that was passed by value, the original filter.reachable_from and filter.unreachable_from pointers are left dangling.
As is the case with the previous commit, nobody touches either of these fields after calling reach_filter(), so leaving them dangling is OK. But this future proofs against dangerous situations.
--- ref-filter.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)
ref-filter.c +7 -7
@@ -2418,13 +2418,13 @@ void ref_array_clear(struct ref_array *array)#define EXCLUDE_REACHED 0#define INCLUDE_REACHED 1static void reach_filter (struct ref_array *array, -struct commit_list *check_reachable, +struct commit_list **check_reachable,int include_reached) {int i, old_nr;struct commit **to_clear; -if (!check_reachable) +if (!*check_reachable)return ;CALLOC_ARRAY (to_clear, array->nr);
@@ -2434,7 +2434,7 @@ static void reach_filter(struct ref_array *array, }tips_reachable_from_bases (the_repository, - check_reachable, + *check_reachable, to_clear, array->nr,UNINTERESTING );
@@ -2455,8 +2455,8 @@ static void reach_filter(struct ref_array *array,clear_commit_marks_many (old_nr, to_clear,ALL_REV_FLAGS ); -while (check_reachable) { -struct commit *merge_commit =pop_commit (&check_reachable); +while (*check_reachable) { +struct commit *merge_commit =pop_commit (check_reachable);clear_commit_marks (merge_commit,ALL_REV_FLAGS ); }
@@ -2553,8 +2553,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned intclear_contains_cache (&ref_cbdata.no_contains_cache);/* Filters that need revision walking */ -reach_filter (array, filter->reachable_from,INCLUDE_REACHED ); -reach_filter (array, filter->unreachable_from,EXCLUDE_REACHED ); +reach_filter (array, &filter->reachable_from,INCLUDE_REACHED ); +reach_filter (array, &filter->unreachable_from,EXCLUDE_REACHED ); save_commit_buffer = save_commit_buffer_orig;return ret;
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 4/16 ref-filter: add `ref_filter_clear()`
In reply to Taylor BlauFrom: Jeff King <[email protected]>
We did not bother to clean up at all in git branch or git tag, and git for-each-ref only cleans up a couple of members.
Add and call ref_filter_clear() when cleaning up a struct ref_filter. Running this patch (without any test changes) indicates a couple of now leak-free tests. This was found by running:
$ make SANITIZE=leak
$ make -C t GIT_TEST_PASSING_SANITIZE_LEAK=check GIT_TEST_OPTS=--immediate(Note that the reachable_from and unreachable_from lists should be cleaned as they are used. So this is just covering any case where we might bail before running the reachability check.)
--- builtin/branch.c | 1 + builtin/for-each-ref.c | 3 +-- builtin/tag.c | 1 + ref-filter.c | 16 ++++++++++++++++ ref-filter.h | 3 +++ t/t0041-usage.sh | 1 + t/t3402-rebase-merge.sh | 1 + 7 files changed, 24 insertions(+), 2 deletions(-)
builtin/branch.c +1 -0
@@ -855,6 +855,7 @@ int cmd_branch(int argc, const char **argv, const char *prefix)print_columns (&output, colopts,NULL );string_list_clear (&output,0 );ref_sorting_release (sorting); +ref_filter_clear (&filter);return 0 ; }else if (edit_description) {const char *branch_name;
builtin/for-each-ref.c +1 -2
@@ -120,8 +120,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)strbuf_release (&err);strbuf_release (&output);ref_array_clear (&array); -free_commit_list (filter.with_commit); -free_commit_list (filter.no_commit); +ref_filter_clear (&filter);ref_sorting_release (sorting);strvec_clear (&vec);return 0 ;
builtin/tag.c +1 -0
@@ -659,6 +659,7 @@ int cmd_tag(int argc, const char **argv, const char *prefix) cleanup:ref_sorting_release (sorting); +ref_filter_clear (&filter);strbuf_release (&buf);strbuf_release (&ref);strbuf_release (&reflog_msg);
ref-filter.c +16 -0
@@ -2866,3 +2866,19 @@ int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)return 0 ; } + +void ref_filter_init (struct ref_filter *filter) +{ +struct ref_filter blank =REF_FILTER_INIT ; +memcpy (filter, &blank,sizeof (blank)); +} + +void ref_filter_clear (struct ref_filter *filter) +{ +oid_array_clear (&filter->points_at); +free_commit_list (filter->with_commit); +free_commit_list (filter->no_commit); +free_commit_list (filter->reachable_from); +free_commit_list (filter->unreachable_from); +ref_filter_init (filter); +}
ref-filter.h +3 -0
@@ -170,4 +170,7 @@ void filter_ahead_behind(struct repository *r,struct ref_format *format, struct ref_array *array); +void ref_filter_init (struct ref_filter *filter); +void ref_filter_clear (struct ref_filter *filter); +#endif /* REF_FILTER_H */
t/t0041-usage.sh +1 -0
@@ -5,6 +5,7 @@ test_description='Test commands behavior when given invalid argument value' GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME +TEST_PASSES_SANITIZE_LEAK=true . ./test-lib.sh test_expect_success 'setup ' '
t/t3402-rebase-merge.sh +1 -0
@@ -8,6 +8,7 @@ test_description='git rebase --merge test' GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME +TEST_PASSES_SANITIZE_LEAK=true . ./test-lib.sh T="A quick brown fox
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 5/16 ref-filter.c: parameterize match functions over patterns
In reply to Taylor BlauFrom: Jeff King <[email protected]>
match_pattern() and match_name_as_path() both take a struct ref_filter *, and then store a stack variable patterns pointing at filter->patterns.
The subsequent patch will add a new array of patterns to match over (the excluded patterns, via a new git for-each-ref --exclude option), treating the return value of these functions differently depending on which patterns are being used to match.
Tweak match_pattern() and match_name_as_path() to take an array of patterns to prepare for passing either in.
Once we start passing either in, match_pattern() will have little to do with a particular struct ref_filter * instance. To clarify this, drop it from the argument list, and replace it with the only bit of the ref_filter that we care about (filter->ignore_case).
--- ref-filter.c | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-)
ref-filter.c +10 -8
@@ -2104,12 +2104,12 @@ static int get_ref_atom_value(struct ref_array_item *ref, int atom,* matches a pattern "refs/heads/mas") or a wildcard (e.g. the same ref * matches "refs/heads/mas*", too). */ -static int match_pattern (const struct ref_filter *filter,const char *refname) +static int match_pattern (const char **patterns,const char *refname, +int ignore_case) { -const char **patterns = filter->name_patterns;unsigned flags =0 ; -if (filter->ignore_case) +if (ignore_case) flags |=WM_CASEFOLD ;/*
@@ -2134,13 +2134,13 @@ static int match_pattern(const struct ref_filter *filter, const char *refname)* matches a pattern "refs/heads/" but not "refs/heads/m") or a * wildcard (e.g. the same ref matches "refs/heads/m*", too). */ -static int match_name_as_path (const struct ref_filter *filter,const char *refname) +static int match_name_as_path (const char **pattern,const char *refname, +int ignore_case) { -const char **pattern = filter->name_patterns;int namelen =strlen (refname);unsigned flags =WM_PATHNAME ; -if (filter->ignore_case) +if (ignore_case) flags |=WM_CASEFOLD ;for (; *pattern; pattern++) {
@@ -2165,8 +2165,10 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)if (!*filter->name_patterns)return 1 ;/* No pattern always matches */ if (filter->match_as_path) -return match_name_as_path (filter, refname); -return match_pattern (filter, refname); +return match_name_as_path (filter->name_patterns, refname, + filter->ignore_case); +return match_pattern (filter->name_patterns, refname, + filter->ignore_case); }/*
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 6/16 builtin/for-each-ref.c: add `--exclude` option
In reply to Taylor BlauWhen using for-each-ref, it is sometimes convenient for the caller to be able to exclude certain parts of the references.
For example, if there are many refs/__hidden__/* references, the caller may want to emit all references *except* the hidden ones. Currently, the only way to do this is to post-process the output, like:
$ git for-each-ref --format='%(refname)' | grep -v '^refs/hidden/'
Which is do-able, but requires processing a potentially large quantity of references.
Teach git for-each-ref a new --exclude=<pattern> option, which excludes references from the results if they match one or more excluded patterns.
This patch provides a naive implementation where the ref_filter still sees all references (including ones that it will discard) and is left to check whether each reference matches any excluded pattern(s) before emitting them.
By culling out references we know the caller doesn't care about, we can avoid allocating memory for their storage, as well as spending time sorting the output (among other things). Even the naive implementation provides a significant speed-up on a modified copy of linux.git (that has a hidden ref pointing at each commit):
$ hyperfine \
'git.compile for-each-ref --format="%(objectname) %(refname)" | grep -vE "[0-9a-f]{40} refs/pull/"' \
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude refs/pull/'
Benchmark 1: git.compile for-each-ref --format="%(objectname) %(refname)" | grep -vE "[0-9a-f]{40} refs/pull/"
Time (mean ± σ): 820.1 ms ± 2.0 ms [User: 703.7 ms, System: 152.0 ms]
Range (min … max): 817.7 ms … 823.3 ms 10 runs Benchmark 2: git.compile for-each-ref --format="%(objectname) %(refname)" --exclude refs/pull/
Time (mean ± σ): 106.6 ms ± 1.1 ms [User: 99.4 ms, System: 7.1 ms]
Range (min … max): 104.7 ms … 109.1 ms 27 runs
Summary
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude refs/pull/' ran
7.69 ± 0.08 times faster than 'git.compile for-each-ref --format="%(objectname) %(refname)" | grep -vE "[0-9a-f]{40} refs/pull/"'Subsequent patches will improve on this by avoiding visiting excluded sections of the packed-refs file in certain cases.
--- Documentation/git-for-each-ref.txt | 6 +++++ builtin/for-each-ref.c | 1 + ref-filter.c | 14 ++++++++++++ ref-filter.h | 6 +++++ t/t6300-for-each-ref.sh | 35 ++++++++++++++++++++++++++++++ 5 files changed, 62 insertions(+)
Documentation/git-for-each-ref.txt +6 -0
@@ -14,6 +14,7 @@ SYNOPSIS [--points-at=<object>] [--merged[=<object>]] [--no-merged[=<object>]] [--contains[=<object>]] [--no-contains[=<object>]] + [--exclude=<pattern> ...] DESCRIPTION -----------
@@ -102,6 +103,11 @@ OPTIONS Do not print a newline after formatted refs where the format expands to the empty string. +--exclude=<pattern>:: + If one or more patterns are given, only refs which do not match + any excluded pattern(s) are shown. Matching is done using the + same rules as `<pattern>` above. + FIELD NAMES -----------
builtin/for-each-ref.c +1 -0
@@ -47,6 +47,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)OPT_INTEGER (0 ,"count" , &maxcount,N_ ("show only <n> matched refs" )),OPT_STRING (0 ,"format" , &format.format,N_ ("format" ),N_ ("format to use for the output" )),OPT__COLOR (&format.use_color,N_ ("respect format colors" )), +OPT_REF_FILTER_EXCLUDE (&filter),OPT_REF_SORT (&sorting_options), OPT_CALLBACK(0, "points-at", &filter.points_at, N_("object"), N_("print only refs which points at the given object"),
ref-filter.c +14 -0
@@ -2171,6 +2171,16 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname) filter->ignore_case); } +static int filter_exclude_match (struct ref_filter *filter,const char *refname) +{ +if (!filter->exclude.nr) +return 0 ; +if (filter->match_as_path) +return match_name_as_path (filter->exclude.v, refname, + filter->ignore_case); +return match_pattern (filter->exclude.v, refname, filter->ignore_case); +} +/* * This is the same as for_each_fullref_in(), but it tries to iterate * only over the patterns we'll care about. Note that it _doesn't_ do a full
@@ -2338,6 +2348,9 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,if (!filter_pattern_match (filter, refname))return 0 ; +if (filter_exclude_match (filter, refname)) +return 0 ; +if (filter->points_at.nr && !match_points_at (&filter->points_at, oid, refname))return 0 ;
@@ -2877,6 +2890,7 @@ void ref_filter_init(struct ref_filter *filter)void ref_filter_clear (struct ref_filter *filter) { +strvec_clear (&filter->exclude);oid_array_clear (&filter->points_at);free_commit_list (filter->with_commit);free_commit_list (filter->no_commit);
ref-filter.h +6 -0
@@ -6,6 +6,7 @@#include "refs.h" #include "commit.h" #include "string-list.h" +#include "strvec.h" /* Quoting styles */ #define QUOTE_NONE 0
@@ -59,6 +60,7 @@ struct ref_array {struct ref_filter {const char **name_patterns; +struct strvec exclude;struct oid_array points_at;struct commit_list *with_commit;struct commit_list *no_commit;
@@ -94,6 +96,7 @@ struct ref_format {#define REF_FILTER_INIT { \ .points_at = OID_ARRAY_INIT, \ + .exclude = STRVEC_INIT, \ }#define REF_FORMAT_INIT { \ .use_color = -1, \
@@ -112,6 +115,9 @@ struct ref_format {#define OPT_REF_SORT (var) \ OPT_STRING_LIST(0, "sort", (var), \ N_("key"), N_("field name to sort on")) +#define OPT_REF_FILTER_EXCLUDE (var) \ + OPT_STRVEC(0, "exclude", &(var)->exclude, \ + N_("pattern"), N_("exclude refs which match pattern"))/* * API for filtering a set of refs. Based on the type of refs the user
t/t6300-for-each-ref.sh +35 -0
@@ -447,6 +447,41 @@ test_expect_success 'exercise glob patterns with prefixes' ' test_cmp expected actual ' +cat >expected <<\EOF +refs/tags/bar +refs/tags/baz +refs/tags/testtag +EOF + +test_expect_success 'exercise patterns with prefix exclusions' ' + for tag in foo/one foo/two foo/three bar baz + do + git tag "$tag" || return 1 + done && + test_when_finished "git tag -d foo/one foo/two foo/three bar baz" && + git for-each-ref --format="%(refname)" \ + refs/tags/ --exclude=refs/tags/foo >actual && + test_cmp expected actual +' + +cat >expected <<\EOF +refs/tags/bar +refs/tags/baz +refs/tags/foo/one +refs/tags/testtag +EOF + +test_expect_success 'exercise patterns with pattern exclusions' ' + for tag in foo/one foo/two foo/three bar baz + do + git tag "$tag" || return 1 + done && + test_when_finished "git tag -d foo/one foo/two foo/three bar baz" && + git for-each-ref --format="%(refname)" \ + refs/tags/ --exclude="refs/tags/foo/t*" >actual && + test_cmp expected actual +' + cat >expected <<\EOF 'refs/heads/main' 'refs/remotes/origin/main'
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 7/16 refs: plumb `exclude_patterns` argument throughout
In reply to Taylor BlauThe subsequent patch will want to access an optional excluded_patterns array within refs/packed-backend.c that will cull out certain references matching any of the given patterns on a best-effort basis.
To do so, the refs subsystem needs to be updated to pass this value across a number of different locations.
Prepare for a future patch by introducing this plumbing now, passing NULLs at top-level APIs in order to make that patch less noisy and more easily readable.
--- ls-refs.c | 2 +- ref-filter.c | 2 +- refs.c | 32 +++++++++++++++++++------------- refs.h | 8 +++++++- refs/debug.c | 5 +++-- refs/files-backend.c | 5 +++-- refs/packed-backend.c | 5 +++-- refs/refs-internal.h | 7 ++++--- revision.c | 2 +- 9 files changed, 42 insertions(+), 26 deletions(-)
ls-refs.c +1 -1
@@ -194,7 +194,7 @@ int ls_refs(struct repository *r, struct packet_reader *request)strvec_push (&data.prefixes,"" );refs_for_each_fullref_in_prefixes (get_main_ref_store (r),get_git_namespace (), data.prefixes.v, - send_ref, &data); +NULL , send_ref, &data);packet_fflush (stdout);strvec_clear (&data.prefixes);strbuf_release (&data.buf);
ref-filter.c +1 -1
@@ -2215,7 +2215,7 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,return refs_for_each_fullref_in_prefixes (get_main_ref_store (the_repository),NULL , filter->name_patterns, - cb, cb_data); +NULL , cb, cb_data); }/*
refs.c +19 -13
@@ -1528,7 +1528,9 @@ int head_ref(each_ref_fn fn, void *cb_data)struct ref_iterator *refs_ref_iterator_begin (struct ref_store *refs, -const char *prefix,int trim, +const char *prefix, +const char **exclude_patterns, +int trim,enum do_for_each_ref_flags flags) {struct ref_iterator *iter;
@@ -1544,8 +1546,7 @@ struct ref_iterator *refs_ref_iterator_begin( } } - iter = refs->be->iterator_begin (refs, prefix, flags); - + iter = refs->be->iterator_begin (refs, prefix, exclude_patterns, flags);/* * `iterator_begin()` already takes care of prefix, but we * might need to do some trimming:
@@ -1579,7 +1580,7 @@ static int do_for_each_repo_ref(struct repository *r, const char *prefix,if (!refs)return 0 ; - iter =refs_ref_iterator_begin (refs, prefix, trim, flags); + iter =refs_ref_iterator_begin (refs, prefix,NULL , trim, flags);return do_for_each_repo_ref_iterator (r, iter, fn, cb_data); }
@@ -1601,6 +1602,7 @@ static int do_for_each_ref_helper(struct repository *r, }static int do_for_each_ref (struct ref_store *refs,const char *prefix, +const char **exclude_patterns,each_ref_fn fn,int trim,enum do_for_each_ref_flags flags,void *cb_data) {
@@ -1610,7 +1612,8 @@ static int do_for_each_ref(struct ref_store *refs, const char *prefix,if (!refs)return 0 ; - iter =refs_ref_iterator_begin (refs, prefix, trim, flags); + iter =refs_ref_iterator_begin (refs, prefix, exclude_patterns, trim, + flags);return do_for_each_repo_ref_iterator (the_repository, iter, do_for_each_ref_helper, &hp);
@@ -1618,7 +1621,7 @@ static int do_for_each_ref(struct ref_store *refs, const char *prefix,int refs_for_each_ref (struct ref_store *refs,each_ref_fn fn,void *cb_data) { -return do_for_each_ref (refs,"" , fn,0 ,0 , cb_data); +return do_for_each_ref (refs,"" ,NULL , fn,0 ,0 , cb_data); }int for_each_ref (each_ref_fn fn,void *cb_data)
@@ -1629,7 +1632,7 @@ int for_each_ref(each_ref_fn fn, void *cb_data)int refs_for_each_ref_in (struct ref_store *refs,const char *prefix,each_ref_fn fn,void *cb_data) { -return do_for_each_ref (refs, prefix, fn,strlen (prefix),0 , cb_data); +return do_for_each_ref (refs, prefix,NULL , fn,strlen (prefix),0 , cb_data); }int for_each_ref_in (const char *prefix,each_ref_fn fn,void *cb_data)
@@ -1640,13 +1643,14 @@ int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data)int for_each_fullref_in (const char *prefix,each_ref_fn fn,void *cb_data) {return do_for_each_ref (get_main_ref_store (the_repository), - prefix, fn,0 ,0 , cb_data); + prefix,NULL , fn,0 ,0 , cb_data); }int refs_for_each_fullref_in (struct ref_store *refs,const char *prefix, +const char **exclude_patterns,each_ref_fn fn,void *cb_data) { -return do_for_each_ref (refs, prefix, fn,0 ,0 , cb_data); +return do_for_each_ref (refs, prefix, exclude_patterns, fn,0 ,0 , cb_data); }int for_each_replace_ref (struct repository *r,each_repo_ref_fn fn,void *cb_data)
@@ -1663,14 +1667,14 @@ int for_each_namespaced_ref(each_ref_fn fn, void *cb_data)int ret;strbuf_addf (&buf,"%srefs/" ,get_git_namespace ()); ret =do_for_each_ref (get_main_ref_store (the_repository), - buf.buf, fn,0 ,0 , cb_data); + buf.buf,NULL , fn,0 ,0 , cb_data);strbuf_release (&buf);return ret; }int refs_for_each_rawref (struct ref_store *refs,each_ref_fn fn,void *cb_data) { -return do_for_each_ref (refs,"" , fn,0 , +return do_for_each_ref (refs,"" ,NULL , fn,0 ,DO_FOR_EACH_INCLUDE_BROKEN , cb_data); }
@@ -1740,6 +1744,7 @@ static void find_longest_prefixes(struct string_list *out,int refs_for_each_fullref_in_prefixes (struct ref_store *ref_store,const char *namespace,const char **patterns, +const char **exclude_patterns,each_ref_fn fn,void *cb_data) {struct string_list prefixes =STRING_LIST_INIT_DUP ;
@@ -1755,7 +1760,8 @@ int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,for_each_string_list_item (prefix, &prefixes) {strbuf_addstr (&buf, prefix->string); - ret =refs_for_each_fullref_in (ref_store, buf.buf, fn, cb_data); + ret =refs_for_each_fullref_in (ref_store, buf.buf, + exclude_patterns, fn, cb_data);if (ret)break ;strbuf_setlen (&buf, namespace_len);
@@ -2410,7 +2416,7 @@ int refs_verify_refname_available(struct ref_store *refs,strbuf_addstr (&dirname, refname + dirname.len);strbuf_addch (&dirname,'/' ); - iter =refs_ref_iterator_begin (refs, dirname.buf,0 , + iter =refs_ref_iterator_begin (refs, dirname.buf,NULL ,0 ,DO_FOR_EACH_INCLUDE_BROKEN );while ((ok =ref_iterator_advance (iter)) ==ITER_OK ) { if (skip &&
refs.h +7 -1
@@ -344,6 +344,7 @@ int for_each_ref(each_ref_fn fn, void *cb_data);int for_each_ref_in (const char *prefix,each_ref_fn fn,void *cb_data);int refs_for_each_fullref_in (struct ref_store *refs,const char *prefix, +const char **exclude_patterns,each_ref_fn fn,void *cb_data);int for_each_fullref_in (const char *prefix,each_ref_fn fn,void *cb_data);
@@ -351,10 +352,15 @@ int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data);* iterate all refs in "patterns" by partitioning patterns into disjoint sets * and iterating the longest-common prefix of each set. * +* references matching any pattern in "exclude_patterns" are omitted from the +* result set on a best-effort basis. +* * callers should be prepared to ignore references that they did not ask for. */ int refs_for_each_fullref_in_prefixes (struct ref_store *refs, -const char *namespace,const char **patterns, +const char *namespace, +const char **patterns, +const char **exclude_patterns,each_ref_fn fn,void *cb_data);/**
refs/debug.c +3 -2
@@ -229,11 +229,12 @@ static struct ref_iterator_vtable debug_ref_iterator_vtable = {static struct ref_iterator *debug_ref_iterator_begin (struct ref_store *ref_store,const char *prefix, -unsigned int flags) +const char **exclude_patterns,unsigned int flags) {struct debug_ref_store *drefs = (struct debug_ref_store *)ref_store;struct ref_iterator *res = - drefs->refs->be->iterator_begin (drefs->refs, prefix, flags); + drefs->refs->be->iterator_begin (drefs->refs, prefix, + exclude_patterns, flags);struct debug_ref_iterator *diter =xcalloc (1 ,sizeof (*diter));base_ref_iterator_init (&diter->base, &debug_ref_iterator_vtable,1 ); diter->iter = res;
refs/files-backend.c +3 -2
@@ -832,7 +832,8 @@ static struct ref_iterator_vtable files_ref_iterator_vtable = {static struct ref_iterator *files_ref_iterator_begin (struct ref_store *ref_store, -const char *prefix,unsigned int flags) +const char *prefix,const char **exclude_patterns, +unsigned int flags) {struct files_ref_store *refs;struct ref_iterator *loose_iter, *packed_iter, *overlay_iter;
@@ -877,7 +878,7 @@ static struct ref_iterator *files_ref_iterator_begin(* the packed and loose references. */ packed_iter =refs_ref_iterator_begin ( - refs->packed_ref_store, prefix,0 , + refs->packed_ref_store, prefix, exclude_patterns,0 ,DO_FOR_EACH_INCLUDE_BROKEN ); overlay_iter =overlay_ref_iterator_begin (loose_iter, packed_iter);
refs/packed-backend.c +3 -2
@@ -925,7 +925,8 @@ static struct ref_iterator_vtable packed_ref_iterator_vtable = {static struct ref_iterator *packed_ref_iterator_begin (struct ref_store *ref_store, -const char *prefix,unsigned int flags) +const char *prefix,const char **exclude_patterns, +unsigned int flags) {struct packed_ref_store *refs;struct snapshot *snapshot;
@@ -1150,7 +1151,7 @@ static int write_with_updates(struct packed_ref_store *refs,* list of refs is exhausted, set iter to NULL. When the list * of updates is exhausted, leave i set to updates->nr. */ - iter =packed_ref_iterator_begin (&refs->base,"" , + iter =packed_ref_iterator_begin (&refs->base,"" ,NULL ,DO_FOR_EACH_INCLUDE_BROKEN );if ((ok =ref_iterator_advance (iter)) !=ITER_OK ) iter =NULL ;
refs/refs-internal.h +4 -3
@@ -367,8 +367,8 @@ int is_empty_ref_iterator(struct ref_iterator *ref_iterator);*/ struct ref_iterator *refs_ref_iterator_begin (struct ref_store *refs, -const char *prefix,int trim, -enum do_for_each_ref_flags flags); +const char *prefix,const char **exclude_patterns, +int trim,enum do_for_each_ref_flags flags);/* * A callback function used to instruct merge_ref_iterator how to
@@ -571,7 +571,8 @@ typedef int copy_ref_fn(struct ref_store *ref_store,*/ typedef struct ref_iterator *ref_iterator_begin_fn (struct ref_store *ref_store, -const char *prefix,unsigned int flags); +const char *prefix,const char **exclude_patterns, +unsigned int flags);/* reflog functions */
revision.c +1 -1
@@ -2642,7 +2642,7 @@ static int for_each_bisect_ref(struct ref_store *refs, each_ref_fn fn,struct strbuf bisect_refs =STRBUF_INIT ;int status;strbuf_addf (&bisect_refs,"refs/bisect/%s" , term); - status =refs_for_each_fullref_in (refs, bisect_refs.buf, fn, cb_data); + status =refs_for_each_fullref_in (refs, bisect_refs.buf,NULL , fn, cb_data);strbuf_release (&bisect_refs);return status; }
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 8/16 refs/packed-backend.c: refactor `find_reference_location()`
In reply to Taylor BlauThe function find_reference_location() is used to perform a binary search-like function over the contents of a repository's $GIT_DIR/packed-refs file.
The search it implements is unlike a standard binary search in that the records it searches over are not of a fixed width, so the comparison must locate the end of a record before comparing it.
Extract the core routine of find_reference_location() in order to implement a function in the following patch which will find the first location in the packed-refs file that *doesn't* match the given pattern.
The behavior of find_reference_location() is unchanged.
--- refs/packed-backend.c | 38 ++++++++++++++++++++++---------------- 1 file changed, 22 insertions(+), 16 deletions(-)
refs/packed-backend.c +22 -16
@@ -528,22 +528,8 @@ static int load_contents(struct snapshot *snapshot)return 1 ; } -/* -* Find the place in `snapshot->buf` where the start of the record for -* `refname` starts. If `mustexist` is true and the reference doesn't -* exist, then return NULL. If `mustexist` is false and the reference -* doesn't exist, then return the point where that reference would be -* inserted, or `snapshot->eof` (which might be NULL) if it would be -* inserted at the end of the file. In the latter mode, `refname` -* doesn't have to be a proper reference name; for example, one could -* search for "refs/replace/" to find the start of any replace -* references. -* -* The record is sought using a binary search, so `snapshot->buf` must -* be sorted. -*/ -static const char *find_reference_location (struct snapshot *snapshot, -const char *refname,int mustexist) +static const char *find_reference_location_1 (struct snapshot *snapshot, +const char *refname,int mustexist) {/* * This is not *quite* a garden-variety binary search, because
@@ -589,6 +575,26 @@ static const char *find_reference_location(struct snapshot *snapshot,return lo; } +/* +* Find the place in `snapshot->buf` where the start of the record for +* `refname` starts. If `mustexist` is true and the reference doesn't +* exist, then return NULL. If `mustexist` is false and the reference +* doesn't exist, then return the point where that reference would be +* inserted, or `snapshot->eof` (which might be NULL) if it would be +* inserted at the end of the file. In the latter mode, `refname` +* doesn't have to be a proper reference name; for example, one could +* search for "refs/replace/" to find the start of any replace +* references. +* +* The record is sought using a binary search, so `snapshot->buf` must +* be sorted. +*/ +static const char *find_reference_location (struct snapshot *snapshot, +const char *refname,int mustexist) +{ +return find_reference_location_1 (snapshot, refname, mustexist); +} +/* * Create a newly-allocated `snapshot` of the `packed-refs` file in * its current state and return it. The return value will already have
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 9/16 refs/packed-backend.c: implement jump lists to avoid excluded pattern(s)
In reply to Taylor BlauWhen iterating through the packed-refs file in order to answer a query like:
$ git for-each-ref --exclude=refs/__hidden__
it would be useful to avoid walking over all of the entries in refs/__hidden__/* when possible, since we know that the ref-filter code is going to throw them away anyways.
In certain circumstances, doing so is possible. The algorithm for doing so is as follows:
- For each excluded pattern, find the first record that matches it, and the first record that *doesn't* match it (i.e. the location you'd next want to consider when excluding that pattern).
- Sort the set of excluded regions from the previous step in ascending order of the first location within the packed-refs file that matches.
- Clean up the results from the previous step: discard empty regions, and combine adjacent regions. The set of regions which remains is referred to as the "jump list", and never contains any references which should be included in the result set.
Then when iterating through the packed-refs file, if iter->pos is ever contained in one of the regions from the previous steps, advance iter->pos past the end of that region, and continue enumeration.
Note that we only perform this optimization when none of the excluded pattern(s) have special meta-characters in them. For a pattern like "refs/foo[ac]", the excluded regions ("refs/fooa", "refs/fooc", and everything underneath them) are not connected. A future implementation that handles this case may split the character class (pretending as if two patterns were excluded: "refs/fooa", and "refs/fooc").
There are a few other gotchas worth considering. First, note that the jump list is sorted, so once we jump past a region, we can avoid considering it (or any regions preceding it) again. The member jump_pos is used to track the first next-possible region to jump through.
Second, note that the jump list is best-effort, since we do not handle loose references, and because of the meta-character issue above. The jump list may not skip past all references which won't appear in the results, but will never skip over a reference which does appear in the result set.
In repositories with a large number of hidden references, the speed-up can be significant. Tests here are done with a copy of linux.git with a reference "refs/pull/N" pointing at every commit, as in:
$ git rev-list HEAD | awk '{ print "create refs/pull/" NR " " $0 }' |
git update-ref --stdin
$ git pack-refs --all, it is significantly faster to have for-each-ref jump over the excluded references, as opposed to filtering them out after the fact:
$ hyperfine \
'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"' \
'git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"' \
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"'
Benchmark 1: git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"
Time (mean ± σ): 798.1 ms ± 3.3 ms [User: 687.6 ms, System: 146.4 ms]
Range (min … max): 794.5 ms … 805.5 ms 10 runs Benchmark 2: git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
Time (mean ± σ): 98.9 ms ± 1.4 ms [User: 93.1 ms, System: 5.7 ms]
Range (min … max): 97.0 ms … 104.0 ms 29 runs
Benchmark 3: git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
Time (mean ± σ): 4.5 ms ± 0.2 ms [User: 0.7 ms, System: 3.8 ms]
Range (min … max): 4.1 ms … 5.8 ms 524 runs
Summary
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"' ran
21.87 ± 1.05 times faster than 'git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"'
176.52 ± 8.19 times faster than 'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"'(Comparing stock git and this patch isn't quite fair, since an earlier commit in this series adds a naive implementation of the --exclude option. git.prev is built from the previous commit and includes this naive implementation).
Using the jump list is fairly straightforward (see the changes to refs/packed-backend.c::next_record()), but constructing the list is not. To ensure that the construction is correct, add a new suite of tests in t1419 covering various corner cases (overlapping regions, partially overlapping regions, adjacent regions, etc.).
--- ref-filter.c | 6 +- refs.h | 4 + refs/packed-backend.c | 163 ++++++++++++++++++++++++++++++++++++-- t/helper/test-ref-store.c | 10 +++ t/t1419-exclude-refs.sh | 101 +++++++++++++++++++++++ 5 files changed, 276 insertions(+), 8 deletions(-) create mode 100755 t/t1419-exclude-refs.sh
ref-filter.c +4 -2
@@ -2210,12 +2210,14 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,if (!filter->name_patterns[0 ]) {/* no patterns; we have to look at everything */ -return for_each_fullref_in ("" , cb, cb_data); +return refs_for_each_fullref_in (get_main_ref_store (the_repository), +"" , filter->exclude.v, cb, cb_data); }return refs_for_each_fullref_in_prefixes (get_main_ref_store (the_repository),NULL , filter->name_patterns, -NULL , cb, cb_data); + filter->exclude.v, + cb, cb_data); }/*
refs.h +4 -0
@@ -343,6 +343,10 @@ int for_each_ref(each_ref_fn fn, void *cb_data);*/ int for_each_ref_in (const char *prefix,each_ref_fn fn,void *cb_data); +/* +* references matching any pattern in "exclude_patterns" are omitted from the +* result set on a best-effort basis. +*/ int refs_for_each_fullref_in (struct ref_store *refs,const char *prefix,const char **exclude_patterns,each_ref_fn fn,void *cb_data);
refs/packed-backend.c +157 -6
230 lines not on this page · raw message
t/helper/test-ref-store.c +10 -0
@@ -186,6 +186,15 @@ static int cmd_for_each_ref(struct ref_store *refs, const char **argv)return refs_for_each_ref_in (refs, prefix, each_ref,NULL ); } +static int cmd_for_each_ref__exclude (struct ref_store *refs,const char **argv) +{ +const char *prefix =notnull (*argv++,"prefix" ); +const char **exclude_patterns = argv; + +return refs_for_each_fullref_in (refs, prefix, exclude_patterns, each_ref, +NULL ); +} +static int cmd_resolve_ref (struct ref_store *refs,const char **argv) {struct object_id oid = *null_oid ();
@@ -318,6 +327,7 @@ static struct command commands[] = { { "delete-refs", cmd_delete_refs }, { "rename-ref", cmd_rename_ref }, { "for-each-ref", cmd_for_each_ref }, + { "for-each-ref--exclude", cmd_for_each_ref__exclude }, { "resolve-ref", cmd_resolve_ref }, { "verify-ref", cmd_verify_ref }, { "for-each-reflog", cmd_for_each_reflog },
t/t1419-exclude-refs.sh new file +101 -0
101 lines not on this page · raw message
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 10/16 refs/packed-backend.c: add trace2 counters for jump list
In reply to Taylor BlauThe previous commit added low-level tests to ensure that the packed-refs iterator did not enumerate excluded sections of the refspace.
However, there was no guarantee that these sections weren't being visited, only that they were being suppressed from the output. To harden these tests, add a trace2 counter which tracks the number of regions skipped by the packed-refs iterator, and assert on its value.
--- refs/packed-backend.c | 2 ++ t/t1419-exclude-refs.sh | 59 ++++++++++++++++++++++++++++------------- trace2.h | 2 ++ trace2/tr2_ctr.c | 5 ++++ 4 files changed, 49 insertions(+), 19 deletions(-)
refs/packed-backend.c +2 -0
@@ -13,6 +13,7 @@#include "../statinfo.h" #include "../wrapper.h" #include "../write-or-die.h" +#include "../trace2.h" enum mmap_strategy {/*
@@ -846,6 +847,7 @@ static int next_record(struct packed_ref_iterator *iter) iter->jump_cur++;if (iter->pos < curr->end) { iter->pos = curr->end; +trace2_counter_add (TRACE2_COUNTER_ID_PACKED_REFS_JUMPS ,1 );/* jumps are coalesced, so only one jump is necessary */ break ; }
t/t1419-exclude-refs.sh +40 -19
120 lines not on this page · raw message
trace2.h +2 -0
@@ -552,6 +552,8 @@ enum trace2_counter_id {TRACE2_COUNTER_ID_TEST1 =0 ,/* emits summary event only */ TRACE2_COUNTER_ID_TEST2 ,/* emits summary and thread events */ +TRACE2_COUNTER_ID_PACKED_REFS_JUMPS ,/* counts number of jumps */ +/* Add additional counter definitions before here. */ TRACE2_NUMBER_OF_COUNTERS };
trace2/tr2_ctr.c +5 -0
@@ -27,6 +27,11 @@ static struct tr2_counter_metadata tr2_counter_metadata[TRACE2_NUMBER_OF_COUNTER .name = "test2", .want_per_thread_events = 1, }, + [TRACE2_COUNTER_ID_PACKED_REFS_JUMPS] = { + .category = "packed-refs", + .name = "jumps_made", + .want_per_thread_events = 0, + },/* Add additional metadata before here. */ };
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 11/16 revision.h: store hidden refs in a `strvec`
In reply to Taylor BlauIn subsequent commits, it will be convenient to have a 'const char **' of hidden refs (matching transfer.hiderefs, uploadpack.hideRefs, etc.), instead of a string_list.
Convert spots throughout the tree that store the list of hidden refs from a string_list to a strvec.
Note that in parse_hide_refs_config() there is an ugly const-cast used to avoid an extra copy of each value before trimming any trailing slash characters. This could instead be written as:
ref = xstrdup(value);
len = strlen(ref);
while (len && ref[len - 1] == '/')
ref[--len] = '\0';
strvec_push(hide_refs, ref);
free(ref);but the double-copy (once when calling xstrdup(), and another via strvec_push()) is wasteful.
--- builtin/receive-pack.c | 4 ++-- ls-refs.c | 6 +++--- refs.c | 11 ++++++----- refs.h | 4 ++-- revision.c | 2 +- revision.h | 5 +++-- upload-pack.c | 10 +++++----- 7 files changed, 22 insertions(+), 20 deletions(-)
builtin/receive-pack.c +2 -2
@@ -91,7 +91,7 @@ static struct object_id push_cert_oid;static struct signature_check sigcheck;static const char *push_cert_nonce;static const char *cert_nonce_seed; -static struct string_list hidden_refs =STRING_LIST_INIT_DUP ; +static struct strvec hidden_refs =STRVEC_INIT ;static const char *NONCE_UNSOLICITED ="UNSOLICITED" ;static const char *NONCE_BAD ="BAD" ;
@@ -2621,7 +2621,7 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)packet_flush (1 );oid_array_clear (&shallow);oid_array_clear (&ref); -string_list_clear (&hidden_refs,0 ); +strvec_clear (&hidden_refs);free ((void *)push_cert_nonce);return 0 ; }
ls-refs.c +3 -3
@@ -72,7 +72,7 @@ struct ls_refs_data {unsigned symrefs;struct strvec prefixes;struct strbuf buf; -struct string_list hidden_refs; +struct strvec hidden_refs; unsigned unborn : 1; };
@@ -156,7 +156,7 @@ int ls_refs(struct repository *r, struct packet_reader *request)memset (&data,0 ,sizeof (data));strvec_init (&data.prefixes);strbuf_init (&data.buf,0 ); -string_list_init_dup (&data.hidden_refs); +strvec_init (&data.hidden_refs);git_config (ls_refs_config, &data);
@@ -198,7 +198,7 @@ int ls_refs(struct repository *r, struct packet_reader *request)packet_fflush (stdout);strvec_clear (&data.prefixes);strbuf_release (&data.buf); -string_list_clear (&data.hidden_refs,0 ); +strvec_clear (&data.hidden_refs);return 0 ; }
refs.c +6 -5
@@ -1429,7 +1429,7 @@ char *shorten_unambiguous_ref(const char *refname, int strict) }int parse_hide_refs_config (const char *var,const char *value,const char *section, -struct string_list *hide_refs) +struct strvec *hide_refs) {const char *key; if (!strcmp("transfer.hiderefs", var) ||
@@ -1440,22 +1440,23 @@ int parse_hide_refs_config(const char *var, const char *value, const char *sectiif (!value)return config_error_nonbool (var); - ref =xstrdup (value); + +/* drop const to remove trailing '/' characters */ + ref = (char *)strvec_push (hide_refs, value); len =strlen (ref);while (len && ref[len -1 ] =='/' ) ref[--len] ='\0' ; -string_list_append_nodup (hide_refs, ref); }return 0 ; }int ref_is_hidden (const char *refname,const char *refname_full, -const struct string_list *hide_refs) +const struct strvec *hide_refs) {int i;for (i = hide_refs->nr -1 ; i >=0 ; i--) { -const char *match = hide_refs->items[i].string; +const char *match = hide_refs->v[i];const char *subject;int neg =0 ;const char *p;
refs.h +2 -2
@@ -820,7 +820,7 @@ int update_ref(const char *msg, const char *refname, unsigned int flags, enum action_on_err onerr);int parse_hide_refs_config (const char *var,const char *value,const char *, -struct string_list *); +struct strvec *);/* * Check whether a ref is hidden. If no namespace is set, both the first and
@@ -830,7 +830,7 @@ int parse_hide_refs_config(const char *var, const char *value, const char *,* the ref is outside that namespace, the first parameter is NULL. The second * parameter always points to the full ref name. */ -int ref_is_hidden (const char *,const char *,const struct string_list *); +int ref_is_hidden (const char *,const char *,const struct strvec *);/* Is this a per-worktree ref living in the refs/ namespace? */ int is_per_worktree_ref (const char *refname);
revision.c +1 -1
@@ -1561,7 +1561,7 @@ void init_ref_exclusions(struct ref_exclusions *exclusions)void clear_ref_exclusions (struct ref_exclusions *exclusions) {string_list_clear (&exclusions->excluded_refs,0 ); -string_list_clear (&exclusions->hidden_refs,0 ); +strvec_clear (&exclusions->hidden_refs); exclusions->hidden_refs_configured =0 ; }
revision.h +3 -2
@@ -10,6 +10,7 @@#include "decorate.h" #include "ident.h" #include "list-objects-filter-options.h" +#include "strvec.h" /** * The revision walking API offers functions to build a list of revisions
@@ -95,7 +96,7 @@ struct ref_exclusions {* Hidden refs is a list of patterns that is to be hidden via * `ref_is_hidden()`. */ -struct string_list hidden_refs; +struct strvec hidden_refs;/* * Indicates whether hidden refs have been configured. This is to
@@ -110,7 +111,7 @@ struct ref_exclusions {*/ #define REF_EXCLUSIONS_INIT { \ .excluded_refs = STRING_LIST_INIT_DUP, \ - .hidden_refs = STRING_LIST_INIT_DUP, \ + .hidden_refs = STRVEC_INIT, \ }struct oidset ;
upload-pack.c +5 -5
@@ -69,7 +69,7 @@ struct upload_pack_data {struct object_array have_obj;struct oid_array haves;/* v2 only */ struct string_list wanted_refs;/* v2 only */ -struct string_list hidden_refs; +struct strvec hidden_refs;struct object_array shallows;struct string_list deepen_not;
@@ -127,7 +127,7 @@ static void upload_pack_data_init(struct upload_pack_data *data) {struct string_list symref =STRING_LIST_INIT_DUP ;struct string_list wanted_refs =STRING_LIST_INIT_DUP ; -struct string_list hidden_refs =STRING_LIST_INIT_DUP ; +struct strvec hidden_refs =STRVEC_INIT ;struct object_array want_obj =OBJECT_ARRAY_INIT ;struct object_array have_obj =OBJECT_ARRAY_INIT ;struct oid_array haves =OID_ARRAY_INIT ;
@@ -162,7 +162,7 @@ static void upload_pack_data_clear(struct upload_pack_data *data) {string_list_clear (&data->symref,1 );string_list_clear (&data->wanted_refs,1 ); -string_list_clear (&data->hidden_refs,0 ); +strvec_clear (&data->hidden_refs);object_array_clear (&data->want_obj);object_array_clear (&data->have_obj);oid_array_clear (&data->haves);
@@ -1170,7 +1170,7 @@ static void receive_needs(struct upload_pack_data *data,/* return non-zero if the ref is hidden, otherwise 0 */ static int mark_our_ref (const char *refname,const char *refname_full, -const struct object_id *oid,const struct string_list *hidden_refs) +const struct object_id *oid,const struct strvec *hidden_refs) {struct object *o =lookup_unknown_object (the_repository, oid);
@@ -1471,7 +1471,7 @@ static int parse_want(struct packet_writer *writer, const char *line,static int parse_want_ref (struct packet_writer *writer,const char *line,struct string_list *wanted_refs, -struct string_list *hidden_refs, +struct strvec *hidden_refs,struct object_array *want_obj) {const char *refname_nons;
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 12/16 refs.h: let `for_each_namespaced_ref()` take excluded patterns
In reply to Taylor BlauA future commit will want to call for_each_namespaced_ref() with a list of excluded patterns.
We could introduce a variant of that function, say, for_each_namespaced_ref_exclude() which takes the extra parameter, and reimplement the original function in terms of that. But all but one caller (in http-backend.c) will supply the new parameter, so add the new parameter to for_each_namespaced_ref() itself instead of introducing a new function.
For now, supply NULL for the list of excluded patterns at all callers to avoid changing behavior, which we will do in a future change.
--- http-backend.c | 2 +- refs.c | 5 +++-- refs.h | 7 ++++++- upload-pack.c | 6 +++--- 4 files changed, 13 insertions(+), 7 deletions(-)
http-backend.c +1 -1
@@ -560,7 +560,7 @@ static void get_info_refs(struct strbuf *hdr, char *arg UNUSED) }else {select_getanyfile (hdr); -for_each_namespaced_ref (show_text_ref, &buf); +for_each_namespaced_ref (NULL , show_text_ref, &buf);send_strbuf (hdr,"text/plain" , &buf); }strbuf_release (&buf);
refs.c +3 -2
@@ -1662,13 +1662,14 @@ int for_each_replace_ref(struct repository *r, each_repo_ref_fn fn, void *cb_dat DO_FOR_EACH_INCLUDE_BROKEN, cb_data); } -int for_each_namespaced_ref (each_ref_fn fn,void *cb_data) +int for_each_namespaced_ref (const char **exclude_patterns, +each_ref_fn fn,void *cb_data) {struct strbuf buf =STRBUF_INIT ;int ret;strbuf_addf (&buf,"%srefs/" ,get_git_namespace ()); ret =do_for_each_ref (get_main_ref_store (the_repository), - buf.buf,NULL , fn,0 ,0 , cb_data); + buf.buf, exclude_patterns, fn,0 ,0 , cb_data);strbuf_release (&buf);return ret; }
refs.h +6 -1
@@ -382,7 +382,12 @@ int for_each_glob_ref_in(each_ref_fn fn, const char *pattern, const char *prefix, void *cb_data);int head_ref_namespaced (each_ref_fn fn,void *cb_data); -int for_each_namespaced_ref (each_ref_fn fn,void *cb_data); +/* +* references matching any pattern in "exclude_patterns" are omitted from the +* result set on a best-effort basis. +*/ +int for_each_namespaced_ref (const char **exclude_patterns, +each_ref_fn fn,void *cb_data);/* can be used to learn about broken ref and symref */ int refs_for_each_rawref (struct ref_store *refs,each_ref_fn fn,void *cb_data);
upload-pack.c +3 -3
@@ -855,7 +855,7 @@ static void deepen(struct upload_pack_data *data, int depth)* marked with OUR_REF. */ head_ref_namespaced (check_ref, data); -for_each_namespaced_ref (check_ref, data); +for_each_namespaced_ref (NULL , check_ref, data);get_reachable_list (data, &reachable_shallows); result = get_shallow_commits(&reachable_shallows,
@@ -1392,7 +1392,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,if (advertise_refs) data.no_done =1 ;head_ref_namespaced (send_ref, &data); -for_each_namespaced_ref (send_ref, &data); +for_each_namespaced_ref (NULL , send_ref, &data);if (!data.sent_capabilities) {const char *refname ="capabilities^{}" ;write_v0_ref (&data, refname, refname,null_oid ());
@@ -1406,7 +1406,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,packet_flush (1 ); }else {head_ref_namespaced (check_ref, &data); -for_each_namespaced_ref (check_ref, &data); +for_each_namespaced_ref (NULL , check_ref, &data); }if (!advertise_refs) {
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 13/16 refs.h: implement `hidden_refs_to_excludes()`
In reply to Taylor BlauIn subsequent commits, we'll teach receive-pack and upload-pack to use the new jump list feature in the packed-refs iterator by ignoring references which are mentioned via its respective hideRefs lists.
However, the packed-ref jump lists cannot handle un-hiding rules (that begin with '!'), or namespace comparisons (that begin with '^'). Add a convenience function to the refs.h API to detect when either of these conditions are met, and returns an appropriate value to pass as excluded patterns.
--- refs.c | 24 ++++++++++++++++++++++++ refs.h | 6 ++++++ 2 files changed, 30 insertions(+)
refs.c +24 -0
@@ -1482,6 +1482,30 @@ int ref_is_hidden(const char *refname, const char *refname_full,return 0 ; } +const char **hidden_refs_to_excludes (const struct strvec *hide_refs) +{ +const char **pattern; +for (pattern = hide_refs->v; *pattern; pattern++) { +/* +* We can't feed any excludes from hidden refs config +* sections, since later rules may override previous +* ones. For example, with rules "refs/foo" and +* "!refs/foo/bar", we should show "refs/foo/bar" (and +* everything underneath it), but the earlier exclusion +* would cause us to skip all of "refs/foo". We +* likewise don't implement the namespace stripping +* required for '^' rules. +* +* Both are possible to do, but complicated, so avoid +* populating the jump list at all if we see either of +* these patterns. +*/ +if (**pattern =='!' || **pattern =='^' ) +return NULL ; + } +return hide_refs->v; +} +const char *find_descendant_ref (const char *dirname,const struct string_list *extras,const struct string_list *skip)
refs.h +6 -0
@@ -837,6 +837,12 @@ int parse_hide_refs_config(const char *var, const char *value, const char *,*/ int ref_is_hidden (const char *,const char *,const struct strvec *); +/* +* Returns an array of patterns to use as excluded_patterns, if none of the +* hidden references use the token '!' or '^'. +*/ +const char **hidden_refs_to_excludes (const struct strvec *hide_refs); +/* Is this a per-worktree ref living in the refs/ namespace? */ int is_per_worktree_ref (const char *refname);
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 14/16 builtin/receive-pack.c: avoid enumerating hidden references
In reply to Taylor BlauNow that refs_for_each_fullref_in() has the ability to avoid enumerating references matching certain pattern(s), use that to avoid visiting hidden refs when constructing the ref advertisement via receive-pack.
Note that since this exclusion is best-effort, we still need show_ref_cb() to check whether or not each reference is hidden or not before including it in the advertisement.
As was the case when applying this same optimization to upload-pack, receive-pack's reference advertisement phase can proceed much quicker by avoiding enumerating references that will not be part of the advertisement.
(Below, we're still using linux.git with one hidden refs/pull/N ref per commit):
$ hyperfine -L v ,.compile 'git{v} -c transfer.hideRefs=refs/pull receive-pack --advertise-refs .git'
Benchmark 1: git -c transfer.hideRefs=refs/pull receive-pack --advertise-refs .git
Time (mean ± σ): 89.1 ms ± 1.7 ms [User: 82.0 ms, System: 7.0 ms]
Range (min … max): 87.7 ms … 95.5 ms 31 runs Benchmark 2: git.compile -c transfer.hideRefs=refs/pull receive-pack --advertise-refs .git
Time (mean ± σ): 4.5 ms ± 0.2 ms [User: 0.5 ms, System: 3.9 ms]
Range (min … max): 4.1 ms … 5.6 ms 508 runs
Summary
'git.compile -c transfer.hideRefs=refs/pull receive-pack --advertise-refs .git' ran
20.00 ± 1.05 times faster than 'git -c transfer.hideRefs=refs/pull receive-pack --advertise-refs .git'--- builtin/receive-pack.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
builtin/receive-pack.c +3 -1
@@ -339,7 +339,9 @@ static void write_head_info(void) {static struct oidset seen =OIDSET_INIT ; -for_each_ref (show_ref_cb, &seen); +refs_for_each_fullref_in (get_main_ref_store (the_repository),"" , +hidden_refs_to_excludes (&hidden_refs), + show_ref_cb, &seen);for_each_alternate_ref (show_one_alternate_ref, &seen);oidset_clear (&seen);if (!sent_capabilities)
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 15/16 upload-pack.c: avoid enumerating hidden refs where possible
In reply to Taylor BlauIn a similar fashion as a previous commit, teach upload-pack to avoid enumerating hidden references where possible.
Note, however, that there are certain cases where cannot avoid enumerating even hidden references, in particular when either of:
- uploadpack.allowTipSHA1InWant, or
- uploadpack.allowReachableSHA1InWant
are set, corresponding to ALLOW_TIP_SHA1 and ALLOW_REACHABLE_SHA1, respectively.
When either of these bits are set, upload-pack's is_our_ref() function needs to consider the HIDDEN_REF bit of the referent's object flags. So we must visit all references, including the hidden ones, in order to mark their referents with the HIDDEN_REF bit.
When neither ALLOW_TIP_SHA1 nor ALLOW_REACHABLE_SHA1 are set, the is_our_ref() function considers only the OUR_REF bit, and not the HIDDEN_REF one. OUR_REF is applied via mark_our_ref(), and only to objects at the tips of non-hidden references, so we do not need to visit hidden references in this case.
When neither of those bits are set, upload-pack can potentially avoid enumerating a large number of references. In the same example as a previous commit (linux.git with one hidden reference per commit, "refs/pull/N"):
$ printf 0000 >in
$ hyperfine --warmup=1 \
'git -c transfer.hideRefs=refs/pull upload-pack . <in' \
'git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in' \
'git.compile -c transfer.hideRefs=refs/pull upload-pack . <in'
Benchmark 1: git -c transfer.hideRefs=refs/pull upload-pack . <in
Time (mean ± σ): 406.9 ms ± 1.1 ms [User: 357.3 ms, System: 49.5 ms]
Range (min … max): 405.7 ms … 409.2 ms 10 runs Benchmark 2: git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in
Time (mean ± σ): 406.5 ms ± 1.3 ms [User: 356.5 ms, System: 49.9 ms]
Range (min … max): 404.6 ms … 408.8 ms 10 runs
Benchmark 3: git.compile -c transfer.hideRefs=refs/pull upload-pack . <in
Time (mean ± σ): 4.7 ms ± 0.2 ms [User: 0.7 ms, System: 3.9 ms]
Range (min … max): 4.3 ms … 6.1 ms 472 runs
Summary
'git.compile -c transfer.hideRefs=refs/pull upload-pack . <in' ran
86.62 ± 4.33 times faster than 'git.compile -c transfer.hideRefs=refs/pull -c uploadpack.allowTipSHA1InWant upload-pack . <in' 86.70 ± 4.33 times faster than 'git -c transfer.hideRefs=refs/pull upload-pack . <in'
As above, we must visit every reference when uploadPack.allowTipSHA1InWant is set. But when it is unset, we can visit far fewer references.
--- upload-pack.c | 37 +++++++++++++++++++++++++++++++------ 1 file changed, 31 insertions(+), 6 deletions(-)
upload-pack.c +31 -6
@@ -602,11 +602,36 @@ static int get_common_commits(struct upload_pack_data *data, } } +static int allow_hidden_refs (enum allow_uor allow_uor) +{ +if ((allow_uor &ALLOW_ANY_SHA1 ) ==ALLOW_ANY_SHA1 ) +return 1 ; +return !(allow_uor & (ALLOW_TIP_SHA1 |ALLOW_REACHABLE_SHA1 )); +} + +static void for_each_namespaced_ref_1 (each_ref_fn fn, +struct upload_pack_data *data) +{ +const char **excludes =NULL ; +/* +* If `data->allow_uor` allows fetching hidden refs, we need to +* mark all references (including hidden ones), to check in +* `is_our_ref()` below. +* +* Otherwise, we only care about whether each reference's object +* has the OUR_REF bit set or not, so do not need to visit +* hidden references. +*/ +if (allow_hidden_refs (data->allow_uor)) + excludes =hidden_refs_to_excludes (&data->hidden_refs); + +for_each_namespaced_ref (excludes, fn, data); +} + +static int is_our_ref (struct object *o,enum allow_uor allow_uor) { -int allow_hidden_ref = (allow_uor & - (ALLOW_TIP_SHA1 |ALLOW_REACHABLE_SHA1 )); -return o->flags & ((allow_hidden_ref ?HIDDEN_REF :0 ) |OUR_REF ); +return o->flags & ((allow_hidden_refs (allow_uor) ?0 :HIDDEN_REF ) |OUR_REF ); }/*
@@ -855,7 +880,7 @@ static void deepen(struct upload_pack_data *data, int depth)* marked with OUR_REF. */ head_ref_namespaced (check_ref, data); -for_each_namespaced_ref (NULL , check_ref, data); +for_each_namespaced_ref_1 (check_ref, data);get_reachable_list (data, &reachable_shallows); result = get_shallow_commits(&reachable_shallows,
@@ -1392,7 +1417,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,if (advertise_refs) data.no_done =1 ;head_ref_namespaced (send_ref, &data); -for_each_namespaced_ref (NULL , send_ref, &data); +for_each_namespaced_ref_1 (send_ref, &data);if (!data.sent_capabilities) {const char *refname ="capabilities^{}" ;write_v0_ref (&data, refname, refname,null_oid ());
@@ -1406,7 +1431,7 @@ void upload_pack(const int advertise_refs, const int stateless_rpc,packet_flush (1 ); }else {head_ref_namespaced (check_ref, &data); -for_each_namespaced_ref (NULL , check_ref, &data); +for_each_namespaced_ref_1 (check_ref, &data); }if (!advertise_refs) {
Signature · 1 line
2.41.0.343.gdff068c469f
PATCH v5 16/16 ls-refs.c: avoid enumerating hidden refs where possible
In reply to Taylor BlauIn a similar fashion as in previous commits, teach ls-refs to avoid enumerating hidden references where possible.
As before, this is linux.git with one hidden reference per commit.
$ hyperfine -L v ,.compile 'git{v} -c protocol.version=2 ls-remote .'
Benchmark 1: git -c protocol.version=2 ls-remote .
Time (mean ± σ): 89.8 ms ± 0.6 ms [User: 84.3 ms, System: 5.7 ms]
Range (min … max): 88.8 ms … 91.3 ms 32 runs Benchmark 2: git.compile -c protocol.version=2 ls-remote .
Time (mean ± σ): 6.5 ms ± 0.1 ms [User: 2.4 ms, System: 4.3 ms]
Range (min … max): 6.2 ms … 8.3 ms 397 runs
Summary
'git.compile -c protocol.version=2 ls-remote .' ran
13.85 ± 0.33 times faster than 'git -c protocol.version=2 ls-remote .'
--- ls-refs.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
ls-refs.c +2 -1
@@ -194,7 +194,8 @@ int ls_refs(struct repository *r, struct packet_reader *request)strvec_push (&data.prefixes,"" );refs_for_each_fullref_in_prefixes (get_main_ref_store (r),get_git_namespace (), data.prefixes.v, -NULL , send_ref, &data); +hidden_refs_to_excludes (&data.hidden_refs), + send_ref, &data);packet_fflush (stdout);strvec_clear (&data.prefixes);strbuf_release (&data.buf);
Signature · 1 line
2.41.0.343.gdff068c469f
Re: [PATCH v5 00/16] refs: implement jump lists for packed backend
In reply to Taylor BlauQuoted 2 lines · Taylor Blau
Here is another reroll of my series to implement jump (née skip) lists for the packed refs backend, based on top of the current 'master'.
I've skimmed the whole set again and nothing jumped at me as an unexpected change. Let's wait for a few days to see if we have others comment on the patches and then merge it down to 'next' unless there is something spotted in there.
Thanks.
Re: [PATCH v5 00/16] refs: implement jump lists for packed backend
Quoted 11 lines · Junio C Hamano
Quoted 2 lines · Taylor Blau
Here is another reroll of my series to implement jump (née skip) lists for the packed refs backend, based on top of the current 'master'.
I've skimmed the whole set again and nothing jumped at me as an unexpected change. Let's wait for a few days to see if we have others comment on the patches and then merge it down to 'next' unless there is something spotted in there.
Thanks.
The patch series looks good to me, too, so please feel free to add my Reviewed-by. Thanks for these exciting changes!
Patrick
Re: [PATCH v5 00/16] refs: implement jump lists for packed backend
Quoted 11 lines · Patrick Steinhardt
Quoted 10 lines · Junio C Hamano
Quoted 2 lines · Taylor Blau
Here is another reroll of my series to implement jump (née skip) lists for the packed refs backend, based on top of the current 'master'.
I've skimmed the whole set again and nothing jumped at me as an unexpected change. Let's wait for a few days to see if we have others comment on the patches and then merge it down to 'next' unless there is something spotted in there.
Quoted 4 lines
Quoted 1 line
Thanks.
The patch series looks good to me, too, so please feel free to add my Reviewed-by. Thanks for these exciting changes!
Thanks.
Re: [PATCH v5 00/16] refs: implement jump lists for packed backend
Quoted 11 lines · Junio C Hamano
Quoted 9 lines
Quoted 6 lines
I've skimmed the whole set again and nothing jumped at me as an unexpected change. Let's wait for a few days to see if we have others comment on the patches and then merge it down to 'next' unless there is something spotted in there.
Thanks.
The patch series looks good to me, too, so please feel free to add my Reviewed-by. Thanks for these exciting changes!
Thanks.
Thanks, both :-).
Thanks,
Taylor